Learning Implicitly with Noisy Data in Linear Arithmetic

Alexander P. Rader, Ionela G. Mocanu, Vaishak Belle, Brendan Juba

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Robust learning in expressive languages with realworld 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 firstorder 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 polynomialtime 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.
Original languageEnglish
Title of host publicationProceedings of 30th International Joint Conference on Artificial Intelligence (IJCAI-21)
PublisherIJCAI Inc
Number of pages8
ISBN (Electronic)978-0-9992411-9-6
Publication statusPublished - 19 Aug 2021
Event30th International Joint Conference on Artificial Intelligence - Montreal, Canada
Duration: 19 Aug 202126 Aug 2021


Conference30th International Joint Conference on Artificial Intelligence
Abbreviated titleIJCAI 2021
Internet address

Keywords / Materials (for Non-textual outputs)

  • Constraints and SAT
  • Constraints and Data Mining
  • Constraints and Machine Learning


Dive into the research topics of 'Learning Implicitly with Noisy Data in Linear Arithmetic'. Together they form a unique fingerprint.

Cite this