Learning Implicitly with Noisy Data in Linear Arithmetic

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