Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins

Abstract

We analyze the properties of gradient descent on convex surrogates for the zero-one loss for the agnostic learning of linear halfspaces. If $\mathsf{OPT}$ is the best classification error achieved by a halfspace, by appealing to the notion of soft margins we are able to show that gradient descent finds halfspaces with classification error $\tilde{O}({\mathsf{OPT}}^{1/2})+\epsilon$ in $\mathrm{poly}(d,1/\epsilon )$ time and sample complexity for a broad class of distributions that includes log-concave isotropic distributions as a subclass. Along the way we answer a question recently posed by Ji et al. (2020) on how the tail behavior of a loss function can affect sample complexity and runtime guarantees for gradient descent.

arXiv comment25 pages, 1 table

References in corpus (10)

• Risk bounds for statistical learning
• Contextual Bandit Algorithms with Supervised Learning Guarantees
• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• Learning One-hidden-layer ReLU Networks via Gradient Descent
• Minimizing The Misclassification Error Rate Using a Surrogate Convex Loss
• Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginals
• Approximation Schemes for ReLU Regression
• Learning Halfspaces with Tsybakov Noise
• Efficient Learning of Linear Separators under Bounded Noise
• Gradient descent follows the regularization path for general losses

Cited by in corpus (3)

• Provable Robustness of Adversarial Training for Learning Halfspaces with Noise
• Normal approximations for the multivariate inverse Gaussian distribution and asymmetric kernel smoothing on $d$-dimensional half-spaces
• Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noise