Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin

Abstract

We study the problem of {\em properly} learning large margin halfspaces in the agnostic PAC model. In more detail, we study the complexity of properly learning $d$-dimensional halfspaces on the unit ball within misclassification error $\alpha \cdot {\mathrm{OPT}}_{\gamma }+\epsilon$, where ${\mathrm{OPT}}_{\gamma }$ is the optimal $\gamma$-margin error rate and $\alpha \ge 1$ is the approximation ratio. We give learning algorithms and computational hardness results for this problem, for all values of the approximation ratio $\alpha \ge 1$, that are nearly-matching for a range of parameters. Specifically, for the natural setting that $\alpha$ is any constant bigger than one, we provide an essentially tight complexity characterization. On the positive side, we give an $\alpha =1.01$-approximate proper learner that uses $O(1/({\epsilon }^2{\gamma }^2))$ samples (which is optimal) and runs in time $\mathrm{poly}(d/\epsilon )\cdot 2^{\tilde{O}(1/{\gamma }^2)}$. On the negative side, we show that {\em any} constant factor approximate proper learner has runtime $\mathrm{poly}(d/\epsilon )\cdot 2^{(1/\gamma {)}^{2-o(1)}}$, assuming the Exponential Time Hypothesis.

References in corpus (6)

• Sever: A Robust Meta-Algorithm for Stochastic Optimization
• Adversarial examples from computational constraints
• Adversarial Robustness May Be at Odds With Simplicity
• VC Classes are Adversarially Robustly Learnable, but Only Improperly
• Improved Approximation of Linear Threshold Functions
• Degree-$d$ Chow Parameters Robustly Determine Degree-$d$ PTFs (and Algorithmic Applications)

Cited by in corpus (2)

• Generalized Resilience and Robust Statistics
• Learning and Certification under Instance-targeted Poisoning