Variable Metric Stochastic Approximation Theory

By Peter Sunehag, Jochen Trumpf, S. V. N. Vishwanathan, N. Schraudolph. 2009

32 citations recorded by the source corpus.

We provide a variable metric stochastic approximation theory. In doing so, we provide a convergence theory for a large class of online variable metric methods including the recently introduced online versions of the BFGS algorithm and its limited-memory LBFGS variant. We also discuss the implications of our results for learning from expert advice.

Subfields: Artificial Intelligence, Management Science and Operations Research, 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 Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods (2013, background): “In (Schrau-dolph et al., 2007; Sunehag et al., 2009) a stochastic variant of LBFGS is proposed.”
Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “Next, we study stochastic Quasi-Newton meth-ods (Schraudolph et al., 2007; Sunehag et al., 2009; Zhou et al., 2017; Liu et al., 2018; Berahas et al., 2019; Gao and Goldfarb, 2019) in the interpolation setting (Section 5).”
Minimizing finite sums with the stochastic average gradient (2013, background): “There has been a substantial amount ofwork ondeveloping stochastic variants of these algorithms, with several of the notable recent examples including [6,18,22,36,60,63].”
Global convergence of online limited memory BFGS (2014, background): “Although they improve asymptotic convergence rates, the latter methods are still often slow in practice.”
A new optimization approach for source-encoding full-waveform inversion (2013, unknown): “Stochastic gradient descent (Schraudolph et al., 2007; Sunehag et al., 2009) takes the following form: σkþ1 ¼ σk − ηk∇Jðσk;wkÞ; (11) where k is the iteration number, ηk is the step length, J is the misfit function, σk is the model at iteration k, and wk is the current randomized weight.”
A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets (2012, background): “Under certain conditions these variants are convergent with an O(1/k) rate [18].”
Projected Newton-type methods in machine learning (2011, methodology): “Variants of the L-BFGS approximation that apply in stochastic scenarios are examined in (Sunehag et al., 2009).”
11 Projected Newton-type Methods in Machine Learning (2011, methodology): “Variants of the L-BFGS approximation that apply in stochastic scenarios are examined in (Sunehag et al., 2009).”