Robust learning of halfspaces under log-concave marginals
Jane Lange, Arsen Vasilyan
We say that a classifier is $\text{\emph{adversarially robust}}$ to perturbations of norm $r$ if,with high probability over a point $x$ drawn from the input distribution, there is no point within distance $\le r$ from $x$ that is classified differently. The $\text{\emph{boundary volume}}$ is the probability that a point falls within distance $r$ of a point with a different label.This work studies the task of learning a hypothesis with small boundary volume, where the input is distributed as a subgaussian isotropic log-concave distribution over $\mathbb{R}^d$.Linear threshold functions are adversarially robust; they have boundary volume proportional to $r$.Such concept classes are efficiently learnable by polynomialregression, which produces a polynomial threshold function (PTF), but PTFs in general may have boundary volume $\Omega(1)$, even for $r \ll 1$.We give an algorithm that agnostically learns linear threshold functions and returns a classfier with boundary volume $O(r+\varepsilon)$ atradius of perturbation $r$.The time and sample complexity of $d^{\tilde{O}(1/\varepsilon^2)}$ matches the complexity of polynomial regression.Our algorithm augments the classic approach of polynomial regression with three additional steps:\$\quad$ a) performing the $\ell_1$-error regression under $\ell_1$ noise sensitivity constraints,\$\quad$ b) a structured partitioning and rounding step that returns a Boolean classifier with error $\mathrm{opt} + O(\varepsilon)$ and noise sensitivity $O(r+\varepsilon)$ simultaneously, and \$\quad c)$ a local corrector that ``smooths'' a function with low noise sensitivity into a function that is adversarially robust.