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:
- 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.
- 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.
- 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.
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\}$).
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