Stochastic Gradient Descent with Exponential Convergence Rates of Expected Classification Errors

Atsushi Nitanda, Taiji Suzuki

Abstract

We consider stochastic gradient descent (SGD) and its averaging variant for binary classification problems in a reproducing kernel Hilbert space (RKHS). In traditional analysis using a consistency property of loss functions, the classification error is shown to converge at a sublinear rate. This paper demonstrates that under a "strong low-noise condition," both SGD and its averaged version can achieve exponential convergence rates for classification errors, extending previous theoretical breakthroughs from simple squared loss to a wide range of practical functions like logistic regression.

Introduction

In machine learning, direct minimization of classification error is often computationally intractable due to its non-continuous and non-convex nature. Consequently, practitioners minimize "surrogate" losses, such as logistic or hinge loss. Traditional theoretical frameworks suggest that while surrogate risk might converge at sublinear rates (e.g., $O(1/T)$ or $O(1/\sqrt{T})$), the actual classification error—the primary metric of interest—converges even more slowly.

Recent research indicated that exponential convergence was possible under a "strong low-noise condition," where data labels are consistently distinct and not near a decision boundary. However, these proofs were largely restricted to the squared loss function. This paper bridges this gap by investigating whether these rapid exponential rates are achievable for the broader class of convex loss functions commonly employed in real-world classification tasks.

Methodology

The study analyzes SGD and Averaged SGD within the framework of Reproducing Kernel Hilbert Spaces (RKHS). The technical approach incorporates several key components:

  • General Convex Losses: The analysis moves beyond squared loss to include a broad class of differentiable convex functions, such as logistic loss and Adaboost-style exponential loss.
  • Strong Low-Noise Condition: It is assumed that the conditional probability of a label is bounded away from $1/2$ by a margin $\delta$. A larger $\delta$ (up to $0.5$) represents a "cleaner" dataset with less label noise.
  • Stability Analysis: The authors employ stability arguments to measure the sensitivity of the model to individual training points, facilitating the proof of convergence.
  • Link Functions: The relationship between the surrogate loss and the true conditional probability is utilized to establish bounds on the classification error.

Experimental Setup

The theoretical findings were validated using synthetic 2D datasets designed to isolate the impact of noise on convergence. The data consists of two clusters in $\mathbb{R}^2$, with the low-noise parameter $\delta$ varied across values of $0.1, 0.25,$ and $0.4$. Evaluation was conducted on a test set of 100,000 points to ensure statistical significance.

Synthetic 2D data clusters with label overlap controlled by the noise parameter $\delta$.

Results and Discussion

The core theoretical contribution is the derivation of convergence bounds of the form $O(\exp(-T))$, where $T$ denotes the number of iterations. Experimental results confirm several key insights:

  • Classification vs. Regression: Under low-noise conditions, classification is inherently "easier" than regression. The classification error often drops to zero well before the surrogate loss is fully minimized, as the model output only needs to be on the correct side of the decision boundary.
  • The Advantage of Averaging: While standard SGD eventually enters an exponential convergence phase, Averaged SGD typically reaches this phase significantly earlier and exhibits smoother convergence trajectories.
  • Generalization: The results demonstrate that the exponential convergence rates previously observed for squared loss generalize to a wide class of functions without theoretical degradation.
Learning curves for logistic regression across different noise levels. The middle row illustrates classification error dropping sharply as $\delta$ increases.

Conclusion and Limitations

This work establishes that SGD can achieve exponential convergence for classification errors under favorable noise conditions. However, several avenues for future research remain:

  • Non-Differentiable Losses: The current analysis requires differentiability, excluding the Hinge Loss used in Support Vector Machines.
  • Hypothesis Space Assumptions: The proof assumes the Bayes optimal classifier resides within the hypothesis space, which may not hold in complex real-world scenarios.
  • Advanced Optimizers: Future work could explore whether variance-reduced or accelerated SGD methods further enhance these convergence properties.

Summary updated

Abstract

We consider stochastic gradient descent and its averaging variant for binary classification problems in a reproducing kernel Hilbert space. In traditional analysis using a consistency property of l...
BibTeX
@inproceedings{nitanda2019stochastic,
  author = {Atsushi Nitanda and Taiji Suzuki},
  title = {{Stochastic Gradient Descent with Exponential Convergence Rates of Expected Classification Errors}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=2HjU2yQ-GWO},
}
Figure