Tester-Learners for Halfspaces: Universal Algorithms
Aravind Gollakota Adam R. Klivans Konstantinos Stavropoulos Arsen Vasilyan
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}) + \epsilon$ on any labeled distribution that
the tester accepts, and moreover, the tester accepts whenever the marginal is
any distribution that satisfies a Poincar\'e 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\'e distributions includes all strongly log-concave
distributions, and, assuming the Kannan--L\'{o}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} + \epsilon$ 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\'e distributions are
certifiably hypercontractive in the SOS framework.