Tester-Learners for Halfspaces: Universal Algorithms
This provides a universal tester-learner for halfspaces, addressing a key challenge in testable learning by not being tailored to specific distributions, which is significant for machine learning theory but incremental in scope.
The paper tackles the problem of learning halfspaces with a universal algorithm that works across a broad class of structured distributions, achieving error O(opt) + ε in polynomial time for distributions satisfying a Poincaré inequality, and error opt + ε for Massart noise on log-concave distributions.
We give the first tester-learner for halfspaces that succeeds universally over a wide class of structured distributions. Our universal tester-learner runs in fully polynomial time and has the following guarantee: the learner achieves error $O(\mathrm{opt}) + ε$ on any labeled distribution that the tester accepts, and moreover, the tester accepts whenever the marginal is any distribution that satisfies a Poincaré inequality. In contrast to prior work on testable learning, our tester is not tailored to any single target distribution but rather succeeds for an entire target class of distributions. The class of Poincaré distributions includes all strongly log-concave distributions, and, assuming the Kannan--Lóvasz--Simonovits (KLS) conjecture, includes all log-concave distributions. In the special case where the label noise is known to be Massart, our tester-learner achieves error $\mathrm{opt} + ε$ while accepting all log-concave distributions unconditionally (without assuming KLS). Our tests rely on checking hypercontractivity of the unknown distribution using a sum-of-squares (SOS) program, and crucially make use of the fact that Poincaré distributions are certifiably hypercontractive in the SOS framework.