Stochastic Gradient Descent with Exponential Convergence Rates of Expected Classification Errors

Atsushi Nitanda, Taiji Suzuki

Abstract

In binary classification within reproducing kernel Hilbert spaces (RKHS), traditional analysis often suggests that expected classification error converges sublinearly, even under low-noise conditions. This paper demonstrates that for a broad class of differentiable convex loss functions, Stochastic Gradient Descent (SGD) can achieve exponential convergence rates for classification error in its final phase. Furthermore, we show that Averaged SGD achieves this same exponential rate from the early stages of training. These theoretical findings are validated through experiments on $L_2$-regularized logistic regression using synthetic datasets.

Introduction

Machine learning models typically minimize a convex surrogate loss (like logistic or hinge loss) because the true objective, classification error (0-1 loss), is non-convex and discontinuous. While minimizing these surrogates is computationally efficient, theoretical bounds on the resulting classification error have historically been pessimistic, often yielding sublinear convergence rates such as $O(1/\sqrt{T})$.

Recent work identified that exponential convergence is possible for the squared loss under specific noise conditions. However, squared loss is often suboptimal for classification tasks. This research fills that gap by extending the proof of exponential convergence to a wider, more practical class of differentiable convex losses, including logistic and exponential loss.

Theoretical Framework

The authors analyze the behavior of SGD and its averaged variant in an RKHS, focusing on how classification error relates to surrogate risk. The analysis hinges on three main pillars:

  1. Strong Low-Noise Condition: It is assumed that conditional label probabilities are bounded away from $1/2$. This implies that data points are not overly ambiguous near the decision boundary, a condition often met in high-quality datasets.
  2. Link Functions and Stability: By utilizing Bregman divergence and stability analysis (examining the impact of individual training points on the model), the authors connect the convergence of surrogate risk to the faster convergence of classification error.
  3. The Advantage of Averaging: The theory posits that while standard SGD eventually enters an exponential convergence phase, Averaged SGD reaches this phase significantly earlier due to the stabilizing effect of the moving average on model iterates.

Experimental Methodology

To verify the theoretical results, the authors employed synthetic 2D datasets where noise levels could be precisely controlled. The data consists of two clusters in $\mathbb{R}^2$ separated by a gap.

Synthetic 2D dataset used for experiments, featuring two separable classes with a gap controlled by noise parameters.

The experiments utilized $L_2$-regularized logistic regression. A key parameter in these tests is $\delta$, representing the "low-noise" threshold. Higher values of $\delta$ indicate more certain labels and a clearer separation between classes. The test datasets were scaled to 100,000 points to ensure statistical robustness.

Key Results and Insights

The experimental results confirm the theoretical predictions across various noise levels ($\delta \in \{0.1, 0.25, 0.4\}$).

Experimental results for L2-regularized logistic regression across different noise levels (δ). The rows show surrogate loss, classification error, and the ratio of classification error to excess risk.

As shown in the figure above, while the surrogate loss (top row) decreases gradually, the classification error (middle row) drops to zero much more rapidly, especially as the noise decreases (moving from right to left). The bottom row illustrates the ratio of classification error to excess risk; the sharp decline in this ratio highlights the "acceleration" effect where classification becomes "easier" than regression.

Crucially, Averaged SGD (blue lines) consistently outperforms standard SGD (purple lines) by reaching the low-error regime much faster and with significantly less variance. This supports the claim that averaging triggers the exponential convergence phase earlier in the training process.

Conclusion and Future Work

This work establishes that exponential convergence of classification error is a general property of differentiable convex losses under low-noise conditions, rather than a quirk of the squared loss.

However, some limitations remain. The current proofs require differentiability, which excludes the Hinge loss used in Support Vector Machines. Additionally, the analysis assumes the optimal Bayes classifier resides within the chosen RKHS. Future research may explore relaxing these assumptions or investigating whether advanced variance-reduction techniques like SVRG or SAGA exhibit similar exponential behaviors.

Summary updated

Abstract

We consider stochastic gradient descent and its averaging variant for binary classification problems in a reproducing kernel Hilbert space. In the traditional analysis using a consistency property of loss functions, it is known that the expected classification error converges more slowly than the expected risk even when assuming a low-noise condition on the conditional label probabilities. Consequently, the resulting rate is sublinear. Therefore, it is important to consider whether much faster convergence of the expected classification error can be achieved. In recent research, an exponential convergence rate for stochastic gradient descent was shown under a strong low-noise condition but provided theoretical analysis was limited to the squared loss function, which is somewhat inadequate for binary classification tasks. In this paper, we show an exponential convergence of the expected classification error in the final phase of the stochastic gradient descent for a wide class of differentiable convex loss functions under similar assumptions. As for the averaged stochastic gradient descent, we show that the same convergence rate holds from the early phase of training. In experiments, we verify our analyses on the $L_2$-regularized logistic regression.
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