Exponential convergence of testing error for stochastic gradient methods

By Loucas Pillaud-Vivien, Alessandro Rudi, Francis R. Bach. 2017

36 citations recorded by the source corpus.

We consider binary classification problems with positive definite kernels and square loss, and study the convergence rates of stochastic gradient methods. We show that while the excess testing loss (squared loss) converges slowly to zero as the number of observations (and thus iterations) goes to infinity, the testing error (classification error) converges exponentially fast if low-noise conditions are assumed.

Subfields: Artificial Intelligence, Finance, Statistics and Probability, Scaling & Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Finance

In Statistics and Probability

In Scaling & Learning Theory

Citations in the corpus

Quantifying Learning Guarantees for Convex but Inconsistent Surrogates (2018, background): “[16] showing that under some low-noise assumptions even slow convergence of the surrogate objective can imply exponentially fast convergence of the task loss.”
Learning with SGD and Random Features (2018, background): “Note that numerous works have combined stochastic gradient and kernel methods with no random projections approximation [32, 33, 34, 35, 36, 5].”
Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss (2020, background): “The rate n−1/2 is suboptimal (an exponential decay of the test error is possible in this context (Pillaud-Vivien et al., 2018)), but this statement is a strong non-asymptotic bound: for the F1-max-margin classifier, d does not appear in the exponent of the ratio R/∆r(P), which characterizes the diff”