Efficient Testable Agnostic Learning for Halfspaces

We give the first efficient algorithm for learning halfspaces in the testable agnostic learning model recently defined in [RV23]. In this model, a learner certifies that the accuracy of its output hypothesis is near optimal whenever the training set passes an associated test, and training sets drawn from some target distribution -- e.g., the Gaussian -- must pass the test. This model is more challenging than the distribution-specific agnostic noise model where the learner is allowed to fail arbitrarily if the distributional assumption does not hold.

We consider the setting where the target distribution is Gaussian (or more generally any strongly log-concave distribution) in d dimensions and the noise model is adversarial (agnostic). Our testable agnostic learning algorithm obtains error O(opt)+ϵ in polynomial time, where opt is the smallest classification error achievable by a halfspace.

Joint work with Aravind Gollakota, Adam R. Klivans and Konstantinos Stavropoulos.