Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin
This work addresses the computational efficiency of robust halfspace learning for machine learning practitioners, offering tight theoretical guarantees but is incremental as it builds on existing margin-based learning frameworks.
The paper tackles the problem of properly learning large margin halfspaces in the agnostic PAC model, providing nearly tight bounds on sample and computational complexity for constant approximation ratios, with an algorithm using O(1/(ε²γ²)) samples and runtime poly(d/ε) * 2^{Õ(1/γ²)} and a hardness result showing runtime poly(d/ε) * 2^{(1/γ)^{2-o(1)}} under the Exponential Time Hypothesis.
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 $α\cdot \mathrm{OPT}_γ + ε$, where $\mathrm{OPT}_γ$ is the optimal $γ$-margin error rate and $α\geq 1$ is the approximation ratio. We give learning algorithms and computational hardness results for this problem, for all values of the approximation ratio $α\geq 1$, that are nearly-matching for a range of parameters. Specifically, for the natural setting that $α$ is any constant bigger than one, we provide an essentially tight complexity characterization. On the positive side, we give an $α= 1.01$-approximate proper learner that uses $O(1/(ε^2γ^2))$ samples (which is optimal) and runs in time $\mathrm{poly}(d/ε) \cdot 2^{\tilde{O}(1/γ^2)}$. On the negative side, we show that {\em any} constant factor approximate proper learner has runtime $\mathrm{poly}(d/ε) \cdot 2^{(1/γ)^{2-o(1)}}$, assuming the Exponential Time Hypothesis.