Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins

Spencer Frei, Yuan Cao, Quanquan Gu

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}) + \varepsilon$ in $\mathrm{poly}(d,1/\varepsilon)$ 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.

Introduction

In machine learning, finding a linear classifier (halfspace) that minimizes misclassification—the zero-one loss—is a fundamental task. However, because the zero-one loss is non-convex and discontinuous, direct optimization is NP-hard. Practitioners circumvent this by using convex surrogates, such as logistic or hinge loss, and optimizing them via gradient descent (GD). While empirically successful, the theoretical justification for using convex surrogates in "agnostic" settings (where data is noisy or not perfectly separable) has been limited. This paper bridges this gap by providing the first theoretical guarantees for standard GD on convex surrogates in agnostic learning.

The Soft Margin Framework

The core contribution of this work is the introduction of the Soft Margin Function, $\phi(\gamma)$. This function quantifies the probability mass of a distribution near the decision boundary. By using this concept, the authors create a mathematical bridge between the surrogate risk (which is easy to optimize) and the zero-one loss.

The analysis involves:

  1. Surrogate-to-Error Decomposition: The surrogate risk is decomposed into components representing misclassified points, points near the boundary (the soft margin), and points correctly classified with high confidence.
  2. Optimization Analysis: Standard convex optimization tools are used to prove that GD and online Stochastic Gradient Descent (SGD) efficiently minimize the surrogate risk.
  3. Distributional Classes: The results apply to broad classes of distributions, including log-concave isotropic distributions (e.g., Gaussians), sub-exponential distributions, and those with hard margins.

Key Results and Insights

The authors demonstrate that the tail behavior of the loss function is critical; exponentially tailed losses (like logistic loss) lead to superior sample complexity by pushing weights faster to achieve larger margins.

For log-concave distributions, GD achieves a classification error of $\tilde{O}(\text{OPT}^{1/2}) + \epsilon$. In cases with a hard margin $\gamma$, the error is $\tilde{O}(\text{OPT}/\gamma) + \epsilon$, matching known lower bounds. These results are summarized in the table below.

Table 1: Comparison of population risk guarantees for Gradient Descent algorithms under various distributional assumptions.

Discussion

This work justifies the use of vanilla gradient descent for agnostic learning under reasonable distributional assumptions, showing it is sufficient without needing specialized non-convex algorithms. However, a gap remains: while $\tilde{O}(\text{OPT}^{1/2})$ is a strong guarantee, it is not as tight as the $O(\text{OPT})$ error achieved by some complex non-convex methods. Future research may focus on closing this gap and extending the soft margin framework to analyze more complex models like deep neural networks.

Summary updated

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}) + \varepsilon$ in $\mathrm{poly}(d,1/\varepsilon)$ 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.
BibTeX
@inproceedings{frei2021agnostic,
  author = {Spencer Frei and Yuan Cao and Quanquan Gu},
  title = {{Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=l6W1t0or5Qa},
}
Figure