Non-parametric Stochastic Approximation with Large Step sizes

By Aymeric Dieuleveut, Francis R. Bach. 2014

194 citations recorded by the source corpus.

We consider the random-design least-squares regression problem within the reproducing kernel Hilbert space (RKHS) framework. Given a stream of independent and identically distributed input/output data, we aim to learn a regression function within an RKHS $\mathcal{H}$, even if the optimal predictor (i.e., the conditional expectation) is not in $\mathcal{H}$. In a stochastic approximation framework where the estimator is updated after each observation, we show that the averaged unregularized least-mean-square algorithm (a form of stochastic gradient), given a sufficient large step-size, attains optimal rates of convergence for a variety of regimes for the smoothnesses of the optimal prediction function and the functions in $\mathcal{H}$.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, 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 Statistics and Probability

In Optimization & Training

Citations in the corpus

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].”
Communication trade-offs for Local-SGD with large step size (2019, background): “Though both of these approaches are often considered to be nearly equivalent [44, 45], fundamental differences exist in their convergence properties.”
Complexity Analysis of stochastic gradient methods for PDE-constrained optimal Control Problems with uncertain parameters (2021, methodology): “Speciﬁ-cally, we will use randomized methods known in the literature as Stochastic Approximation (SA) or Stochastic Gradient (SG) [16, 40, 41, 46, 47].”
Bridging the gap between constant step size stochastic gradient descent and Markov chains (2017, unknown): “This last term was improved to ‖Σ−1/2θ∗‖2/(γn)2 by [15, 16], showing that asymptotically, the bias term is negligible, see also [31].”
Learning with SGD and Random Features (2018, result): “In this limit, our results are also related to those in [41].”
Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance (2019, unknown): “[10] Aymeric Dieuleveut and Francis Bach.”
Exponential convergence of testing error for stochastic gradient methods (2017, unknown): “…is interesting on its own and gives an improved high-probability result which does not depend on the dimension of the problem and has a tighter dependence on the strongly convex parameter –through the effective dimension of the problem, see Caponnetto and De Vito (2007); Dieuleveut and Bach (2016).”
Generalization Properties of Learning with Random Features (2016, methodology): “procedures, including the ν-method [5, 9] and conjugate gradient [7], but also stochastic [17] and incremental [33] gradient methods, with further potential time complexity gains.”
Constant Step Size Stochastic Gradient Descent for Probabilistic Modeling (2018, methodology): “Although we can use an unregularized recursion with good convergence properties (Dieuleveut and Bach, 2016), adding a reg-ularisation by the squared Hilbertian norm is easier to analyze and more stable with limited amounts of data.”
The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure (2019, background): “Several efforts consider SGD in this oracle (Bach and Moulines, 2011; Bach, 2014; Dieuleveut and Bach, 2015; Frostig et al., 2015; Needell et al., 2016) presenting non-asymptotic results, often with iterate averaging.”
On the Equivalence between Quadrature Rules and Random Features (2015, background): “…rates for non-parametric least-squares regression (Hsu et al., 2014) but with an improved computational complexity, and a study of the consequences of our improved approximation result for online learning and stochastic approximation, in the spirit of Dai et al. (2014); Dieuleveut and Bach (2014)”
Accelerating Stochastic Gradient Descent (2017, methodology): “d Casella, 1998; van der Vaart, 2000)). Along these lines, non-asymptotic rates towards statistically optimal estimators are given by Bach and Moulines (2013); Bach (2014); D´efossez and Bach (2015); Dieuleveut and Bach (2015); Needell et al. (2016); Frostig et al. (2015b); Jain et al. (2016). Our w”
Stochastic Optimization for Large-scale Optimal Transport (2016, background): “Putting a bound on the iterates of α by projecting on B r ensures convergence [7].”