Robust learning of halfspaces under log-concave marginals

adversarial robustness linear classifiers agnostic learning

Abstract

We say that a classifier is 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

\leq r

from

x

that is classified differently. The 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

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

Ω (1)

, even for

r ≪ 1

. We give an algorithm that agnostically learns linear threshold functions and returns a classfier with boundary volume

O (r + ε)

atradius of perturbation

r

. The time and sample complexity of

d^{\tilde{O} (1/ ε^{2})}

matches the complexity of polynomial regression.

Our algorithm augments the classic approach of polynomial regression with three additional steps:

performing the $ℓ_{1}$ -error regression under $ℓ_{1}$ noise sensitivity constraints,
a structured partitioning and rounding step that returns a Boolean classifier with error $opt + O (ε)$ and noise sensitivity $O (r + ε)$ simultaneously, and
a local corrector that "smooths" a function with low noise sensitivity into a function that is adversarially robust.