Efficient Algorithms for Reliable Machine Learning

Algorithms for supervised learning typically require some sort of distributional assumption (e.g., Gaussianity), in contrast to the traditional worst-case analysis paradigm from theoretical computer science. This leads to algorithms that succeed only under hard-to-verify assumptions, undermining the very notion of provable correctness.

In this talk, I will describe new learning models where an algorithm either certifies the accuracy of its output classifier or abstains when a distributional assumption has been violated. We will show how this framework leads to the first provably efficient algorithms for learning with distribution shift (with no assumptions on the target domain) and also introduces new techniques that resolve longstanding open problems in supervised learning with contamination.