Reliable learning in challenging environments

Abstract:The problem of designing learners that provide guarantees that their predictions are provably correct is of increasing importance in machine learning. However, learning theoretic guarantees have only been considered in very specific settings. In this work, we consider the design and analysis of reliable learners in challenging test-time environments as encountered in modern machine learning problems: namely `adversarial' test-time attacks (in several variations) and `natural' distribution shifts. In this work, we provide a reliable learner with provably optimal guarantees in such settings. We discuss practical implementations of the learner and further show that our algorithm achieves strong positive performance guarantees on several natural examples: for example, linear separators under log-concave distributions or smooth boundary classifiers under smooth probability distributions.

ChatGPT was used in the v3 update for a technical audit. The authors independently verified the audit. The main modification is a correction of the optimization formulated in Section 4. We also fixed some relatively minor edge cases in some results in the appendices

Machine Learning (cs.LG); Cryptography and Security (cs.CR)

arXiv:2304.03370 [cs.LG]

(or arXiv:2304.03370v3 [cs.LG] for this version)