Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)

By Francis R. Bach, Eric Moulines. 2013

433 citations recorded by the source corpus.

We consider the stochastic approximation problem where a convex function has to be minimized, given only the knowledge of unbiased estimates of its gradients at certain points, a framework which includes machine learning methods based on the minimization of the empirical risk. We focus on problems without strong convexity, for which all previously known algorithms achieve a convergence rate for function values of O(1/√n) after n iterations. We consider and analyze two algorithms that achieve a rate of O(1/n) for classical supervised learning problems. For least-squares regression, we show that averaged stochastic gradient descent with constant step-size achieves the desired rate. For logistic regression, this is achieved by a simple novel stochastic gradient algorithm that (a) constructs successive local quadratic approximations of the loss functions, while (b) preserving the same running-time complexity as stochastic gradient descent. For these algorithms, we provide a non-asymptotic analysis of the generalization error (in expectation, and also in high probability for least-squares), and run extensive experiments showing that they often outperform existing approaches.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training

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

In Optimization & Training

Citations in the corpus

Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods (2013, background): “(Bach & Moulines, 2013) averages the iterates rather than the gradients.”
Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model (2019, background): “This is a classical idea in optimization, where it is known to provide improved convergence [Polyak and Juditsky, 1992, Bach and Moulines, 2013, Dieuleveut and Bach, 2016].”
Robust Aggregation for Federated Learning (2019, methodology): “We now analyze RFA where the local SGD updates are equipped with “tail-averaging” [44] so that w(t+1)i = (2/τ) ∑τ k=τ/2w (t) i,k is averaged over the latter half of the trajectory of iterates instead of line 8 of Algorithm 1.”
Communication trade-offs for synchronized distributed SGD with large step size (2019, methodology): “For quadratic functions, larger steps can be used, as pointed by Bach and Moulines (2013).”
Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition (2016, methodology): “It was recently shown using a non-trivial analysis that a stochastic Newton method could achieve an O (1 /k ) rate for least squares problems [Bach and Moulines, 2013], but our result above shows that the basic stochastic gradient method already achieves this property (although the constants are…”
Stochastic Gradient Descent as Approximate Bayesian Inference (2017, background): “Recent studies investigate the merits of adaptive step sizes (Duchi et al., 2011; Tieleman and Hinton, 2012), gradient or iterate averaging (Toulis et al., 2016; Défossez and Bach, 2015), and constant step-sizes (Bach and Moulines, 2013; Flammarion and Bach, 2015).”
On the rates of convergence of parallelized averaged stochastic gradient algorithms (2017, background): “Among the studied cases, two of them attract a lot of attention: globally strongly convex objectives [11,12], and locally strongly convex ones [13–16].”
A Variational Analysis of Stochastic Gradient Algorithms (2016, methodology): “With those settings, we can perform approximate inference by simply running constant SGD.”
Accelerating Stochastic Gradient Descent (2017, methodology): “For stochastic approximation with least squares regression Bach and Moulines (2013); Défossez and Bach (2015); Needell et al. (2016); Frostig et al. (2015b); Jain et al. (2016) provide non-asymptotic analysis of the behavior of SGD and its variants.”
Averaged Least-Mean-Squares: Bias-Variance Trade-offs and Optimal Sampling Distributions (2015, methodology): “Note also that the step-size provided by γmax is a strict improvement (see supplementary material) on the one proposed by Bach and Moulines (2013), which is equal to the supremum of the set of γ > 0 such that E [ XXT ] − γE [ (XT X)XXT ] is positive semidefinite.”
Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification (2016, methodology): “In particular, writing out the outerproduct of equation 17, we see the following inequality holds through a straightforward application of Cauchy-Shwartz inequality: The equation above is referred to as the bias-variance decomposition and is well known from previous work on Stochastic Approximation ”
A Stochastic Quasi-Newton Method for Large-Scale Optimization (2014, methodology): “A two-stage online Newton strategy is proposed in [3].”
Linear Stochastic Approximation: How Far Does Constant Step-Size and Iterate Averaging Go? (2018, methodology): “[19, 21, 20, 12] and Section 5) have been proposed as an analog of the “LMS algorithm” analyzed by Bach and Moulines [1].”
Non-parametric Stochastic Approximation with Large Step sizes (2014, neutral): “…estimation given the smoothness MSC 2010 subject classifications: Primary 60K35, 60K35; secondary 60K35 Keywords and phrases: Reproducing kernel Hilbert space, Stochastic approximation 1 of the optimal prediction function are attained for a sufficiently small Hilbert space of functions [4, 5, 6].”
Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression (2016, background): “On the other hand, the optimal variance term is proportional to σ 2d n (Tsybakov, 2003); it is known to be achieved by averaged gradient descent (Bach and Moulines, 2013), which for the bias term only achieves L‖θ0−θ∗‖ 2 n instead of L‖θ0−θ∗‖ 2 n2 .”
Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization (2018, background): “, Armijo’s line search [36]) or their approximations [37].”
Bridging the gap between constant step size stochastic gradient descent and Markov chains (2017, methodology): “Finally, we run the online-Newton algorithm [5], which performs very well but has no convergence guarantee.”
Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the O(1/T) Convergence Rate (2019, background): “For the square loss and the logistic loss, an O(1/T ) rate is attainable without strong convexity (Bach and Moulines, 2013).”