Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression

By Aymeric Dieuleveut, Nicolas Flammarion, Francis R. Bach. 2016

244 citations recorded by the source corpus.

We consider the optimization of a quadratic objective function whose gradients are only accessible through a stochastic oracle that returns the gradient at any given point plus a zero-mean finite variance random error. We present the first algorithm that achieves jointly the optimal prediction error rates for least-squares regression, both in terms of forgetting of initial conditions in O(1/n 2), and in terms of dependence on the noise and dimension d of the problem, as O(d/n). Our new algorithm is based on averaged accelerated regularized gradient descent, and may also be analyzed through finer assumptions on initial conditions and the Hessian matrix, leading to dimension-free quantities that may still be small while the " optimal " terms above are large. In order to characterize the tightness of these new bounds, we consider an application to non-parametric regression and use the known lower bounds on the statistical performance (without computational limits), which happen to match our bounds obtained from a single pass on the data and thus show optimality of our algorithm in a wide variety of particular trade-offs between bias and variance.

Subfields: Artificial Intelligence, Computational Mechanics

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 Computational Mechanics

Citations in the corpus

Communication trade-offs for Local-SGD with large step size (2019, methodology): “…non-asymptotic analysis is provided by Défossez and Bach [28], acceleration under the additive noise oracle (see Assumption A 4 below) is studied by Dieuleveut et al. [29] (without this assumption by Jain et al. [30]), and Jain et al. [20] analyze the effects of mini-batch and tail averaging.”
Accelerating Stochastic Gradient Descent (2017, methodology): “For this case, this paper provides a geometric rate of convergence to the minimizer x∗, while the results of Ghadimi and Lan (2012, 2013); Dieuleveut et al. (2016) at best indicate a O(1/n) rate.”
Exponential convergence of testing error for stochastic gradient methods (2017, unknown): “…functions described by a reproducing kernel Hilbert space, and for the square loss, the excess testing loss (equal to testing loss minus the minimal testing loss over all measurable prediction functions) is known to converge to zero at a subexponential rate typically greater than O (1 /n )…”
The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure (2019, methodology): “Dekel et al. (2012); Lacoste-Julien et al. (2012); Rakhlin et al. (2012); Ghadimi and Lan (2012, 2013b); Hazan and Kale (2014); Bubeck (2014); Dieuleveut et al. (2016) use iterate averaged SGD to achieve minimax rates for various problem classes non-asymptotically.”
On the Insufficiency of Existing Momentum Schemes for Stochastic Optimization (2018, background): “In terms of variables, we note that α in this paper’s algorithm description maps to 1 − β 1 .”