Reliable learning in challenging environments
It addresses the need for reliable machine learning with guarantees in adversarial and shifted settings, which is incremental as it extends learning theory to more specific but practical scenarios.
The paper tackles the problem of designing learners with provably correct predictions in challenging test-time environments like adversarial attacks and natural distribution shifts, resulting in a reliable learner with provably optimal guarantees and strong performance on examples such as linear separators under log-concave distributions.
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 computationally feasible 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.