More Like this

1. Learning Implicitly with Noisy Data in Linear Arithmetic

   https://doi.org/10.24963/ijcai.2021/195  

   Rader, Alexander; Mocanu, Ionela G; Belle, Vaishak; Juba, Brendan (August 2021, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence)

   null (Ed.)

   Robust learning in expressive languages with real-world data continues to be a challenging task. Numerous conventional methods appeal to heuristics without any assurances of robustness. While probably approximately correct (PAC) Semantics offers strong guarantees, learning explicit representations is not tractable, even in propositional logic. However, recent work on so-called “implicit learning has shown tremendous promise in terms of obtaining polynomial-time results for fragments of first-order logic. In this work, we extend implicit learning in PAC-Semantics to handle noisy data in the form of intervals and threshold uncertainty in the language of linear arithmetic. We prove that our extended framework keeps the existing polynomial-time complexity guarantees. Furthermore, we provide the first empirical investigation of this hitherto purely theoretical framework. Using benchmark problems, we show that our implicit approach to learning optimal linear programming objective constraints significantly outperforms an explicit approach in practice. 

   more » « less
2. Implicitly Learning to Reason in First-Order Logic

   Belle, Vaishak; Juba, Brendan (December 2019, Advances in neural information processing systems)

   We consider the problem of answering queries about formulas of first-order logic based on background knowledge partially represented explicitly as other formulas, and partially represented as examples independently drawn from a fixed probability distribution. PAC semantics, introduced by Valiant, is one rigorous, general proposal for learning to reason in formal languages: although weaker than classical entailment, it allows for a powerful model theoretic framework for answering queries while requiring minimal assumptions about the form of the distribution in question. To date, however, the most significant limitation of that approach, and more generally most machine learning approaches with robustness guarantees, is that the logical language is ultimately essentially propositional, with finitely many atoms. Indeed, the theoretical findings on the learning of relational theories in such generality have been resoundingly negative. This is despite the fact that first-order logic is widely argued to be most appropriate for representing human knowledge. In this work, we present a new theoretical approach to robustly learning to reason in first-order logic, and consider universally quantified clauses over a countably infinite domain. Our results exploit symmetries exhibited by constants in the language, and generalize the notion of implicit learnability to show how queries can be computed against (implicitly) learned first-order background knowledge. 

   more » « less
3. Probably Approximate Safety Verification of Hybrid Dynamical Systems

   https://doi.org/10.1007/978-3-030-32409-4_15  

   Xue, Bai; Fränzle, Martin; Zhao, Hengjun; Zhan, Naijun; Easwaran, Arvind (January 2019, International Conference on Formal Engineering Methods)

   In this paper we present a method based on linear programming that facilitates reliable safety verification of hybrid dynamical systems subject to perturbation inputs over the infinite time horizon. The verification algorithm applies the probably approximately correct (PAC) learning framework and consequently can be regarded as statistically formal verification in the sense that it provides formal safety guarantees expressed using error probabilities and confidences. The safety of hybrid systems in this framework is verified via the computation of so-called PAC barrier certificates, which can be computed by solving a linear programming problem. Based on scenario approaches, the linear program is constructed by a family of independent and identically distributed state samples. In this way we can conduct verification of hybrid dynamical systems that existing methods are not capable of dealing with. Some preliminary experiments demonstrate the performance of our approach. 

   more » « less
4. Nearly Optimal Algorithms for Level Set Estimation

   Mason, Blake; Jain, Lalit; Mukherjee, Subhojyoti; Camilleri, Romain; Jamieson, Kevin; Nowak, Robert (March 2022, International Conference on Artificial Intelligence and Statistics)

   The level set estimation problem seeks to find all points in a domain  where the value of an unknown function 𝑓:→ℝ exceeds a threshold 𝛼 . The estimation is based on noisy function evaluations that may be acquired at sequentially and adaptively chosen locations in  . The threshold value 𝛼 can either be explicit and provided a priori, or implicit and defined relative to the optimal function value, i.e. 𝛼=(1−𝜖)𝑓(𝐱∗) for a given 𝜖>0 where 𝑓(𝐱∗) is the maximal function value and is unknown. In this work we provide a new approach to the level set estimation problem by relating it to recent adaptive experimental design methods for linear bandits in the Reproducing Kernel Hilbert Space (RKHS) setting. We assume that 𝑓 can be approximated by a function in the RKHS up to an unknown misspecification and provide novel algorithms for both the implicit and explicit cases in this setting with strong theoretical guarantees. Moreover, in the linear (kernel) setting, we show that our bounds are nearly optimal, namely, our upper bounds match existing lower bounds for threshold linear bandits. To our knowledge this work provides the first instance-dependent, non-asymptotic upper bounds on sample complexity of level-set estimation that match information theoretic lower bounds. 

   more » « less
5. Generalization Bounds for Data-Driven Numerical Linear Algebra

   Bartlett, P.; Indyk, P.; Wagner, T. (January 2022, Conference on Learning Theory)

   Data-driven algorithms can adapt their internal structure or parameters to inputs from unknown application-specific distributions, by learning from a training sample of inputs. Several recent works have applied this approach to problems in numerical linear algebra, obtaining significant empirical gains in performance. However, no theoretical explanation for their success was known. In this work we prove generalization bounds for those algorithms, within the PAC-learning framework for data-driven algorithm selection proposed by Gupta and Roughgarden (SICOMP 2017). Our main results are closely matching upper and lower bounds on the fat shattering dimension of the learning-based low rank approximation algorithm of Indyk et al.~(NeurIPS 2019). Our techniques are general, and provide generalization bounds for many other recently proposed data-driven algorithms in numerical linear algebra, covering both sketching-based and multigrid-based methods. This considerably broadens the class of data-driven algorithms for which a PAC-learning analysis is available. 

   more » « less