Stochastic Approximation and Recursive Algorithms and Applications

By Harold J. Kushner, George Yin. 2003

2,534 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, 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 Computer Networks and Communications

In Optimization & Training

Citations in the corpus

Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution (2022, background): “That is, we consider � k = min We note that, in the SGD case, simply picking e.g. k = � 0 / p k + 1 would guarantee convergence of f ( x k ) to f ( x ⇤ ) , in expectation and with high probability [20, 23].”
IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures (2018, background): “…the usual Robbins-Munro conditions: for each state x , The proof is a straightforward application of the convergence result for stochastic approximation algorithms to the ﬁxed point of a contraction operator, see e.g. Dayan & Sejnowski (1994); Bertsekas & Tsitsiklis (1996); Kushner & Yin (2003).”
Train faster, generalize better: Stability of stochastic gradient descent (2015, background): “In fact, we can drive the exponent arbitrarily close to 1/2 while preserving the non-convexity of the problem.”
Minimizing finite sums with the stochastic average gradient (2013, methodology): “• AFG: A variant of the accelerated full gradient method of Nesterov [1983], where iterations of (3) with a step size of 1/L are interleaved with an extrapolation step.”
Learning explanations that are hard to vary (2020, neutral): “2Similar results hold for SGD [Daneshmand et al., 2018, Kushner and Yin, 2003], momentum [Jin et al., 2017], and adaptive methods including Adam [Barakat and Bianchi, 2019] and Adagrad [Ward et al., 2019].”
Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning (2016, background): “For textbook references on stochastic approximation, please see (Kushner and Yin, 2003; Benveniste et al., 2012; Borkar, 2008; Bertsekas and Tsitsiklis, 1989).”
On Convergence of Emphatic Temporal-Difference Learning (2015, methodology): “If 1 t+ 1 t∑ k=0 ψk a.s.→ 0 (B.5) for the respective {ψk}, then the conditions (B.1)-(B.4) hold for stepsizes satisfying αt = O(1/t) and αt−αt+1αt = O(1/t) (see Kushner and Yin, 2003, Example 6.1, p. 171).”
Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization (2011, background): “In terms of related work, we note that the performance of SGD in a stochastic setting has been extensively re-searched in stochastic approximation theory (see for instance (Kushner & Yin, 2003)).”
New Insights and Perspectives on the Natural Gradient Method (2014, background): “There are other relevant results in the vast literature on general strongly convex functions, such as Kushner and Yin (2003) and the references therein, and Moulines and Bach (2011).”
Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes (2012, background): “In terms of theoretical analysis, SGD has been studied for decades (for instance, see Kushner & Yin (2003) and references therein), but perhaps surprisingly, there are still important gaps left in our understanding of this method.”
Stochastic Gradient Descent as Approximate Bayesian Inference (2017, methodology): “The idea of analyzing stochastic gradient descent with stochastic differential equations is well established in the stochastic approximation literature (Kushner and Yin, 2003; Ljung et al., 2012).”