# Stochastic Gradient Descent with Exponential Convergence Rates of Expected Classification Errors

arXiv: https://arxiv.org/abs/1806.05438 · HTML: https://mlsanity.com/paper/1806.05438/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jun 2018.

## Built on by (most cited first, 6 of 6)

- [A Scaling Law for Synthetic-to-Real Transfer: How Much Is Your Pre-training Effective?](https://mlsanity.com/paper/2108.11018/) (2021)
- [Multiclass learning with margin: exponential rates with no bias-variance trade-off](https://mlsanity.com/paper/2202.01773/) (2022)
- [Exponential Error Convergence in Data Classification with Optimized Random Features: Acceleration by Quantum Machine Learning](https://mlsanity.com/paper/2106.09028/) (2021)
- [A Case of Exponential Convergence Rates for SVM](https://mlsanity.com/paper/2205.10055/) (2022)
- [From Weakly Supervised Learning to Active Learning](https://mlsanity.com/paper/2209.11629/) (2022)
- [Error Exponent in Agnostic PAC Learning](https://mlsanity.com/paper/2405.00792/) (2024)

## Abstract (arXiv)

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 L2-regularized logistic regression.