A Stochastic Approximation Method

By H. Robbins. 1951

Subfields: 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 Statistics and Probability

In Optimization & Training

Citations in the corpus

Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods (2013, methodology): “The second approach is to use a variant of Stochastic Gradient Descent (SGD) (Robbins & Monro, 1951; Bottou, 1991).”
ADADELTA: An Adaptive Learning Rate Method (2012, methodology): “ negative gradient for each new sample or batch of samples chosen from the dataset gives a local estimate of which direction minimizes the cost and is referred to as stochastic gradient descent (SGD) [1]. While often simple to derive the gradients for each parameter analytically, the gradient descen”
No more pesky learning rates (2012, background): “Originally proposed as η ( t ) = O ( t − 1 ) in (Robbins & Monro, 1951), this form was recently analyzed in (Xu, 2011; Bach & Moulines, 2011) from a non-asymptotic perspective to understand how hyper-parameters like η 0 and γ aﬀect the convergence speed.”
Training Compute-Optimal Large Language Models (2022, neutral): “Finally, given that it corresponds to early stopping in stochastic ﬁrst order methods, the third term should scale as the convergence rate of these methods, which is lower-bounded by 1 𝐷 1 / 2 (Robbins and Monro, 1951) (and may attain the bound).”
Meta-Learning for Low-Resource Neural Machine Translation (2018, methodology): “We maximize the meta-objective function using stochastic approximation (Robbins and Monro, 1951) with gradient descent.”
Measuring the Effects of Data Parallelism on Neural Network Training (2018, background): “-dierentiable, and extending our setup to this end is straightforward. 5 2.2 Algorithms The dominant algorithms for training neural networks are based on mini-batch stochastic gradient descent (SGD, Robbins and Monro, 1951; Kiefer et al., 1952; Rumelhart et al., 1986; Bottou and Bousquet, 2008; LeCu”
Gradient Descent Happens in a Tiny Subspace (2018, methodology): “We used SGD with a mini-batch size of 64 and η = 0 .”
Don't Decay the Learning Rate, Increase the Batch Size (2017, background): “It is often stated that to reach the minimum of a strongly convex function we should decay the learning rate, such that (Robbins & Monro, 1951): i denotes the learning rate at the i th gradient update.”
On Empirical Comparisons of Optimizers for Deep Learning (2019, methodology): “SGD is due to Robbins and Monro (1951), M OMENTUM to Polyak (1964), N ESTEROV to Nesterov (1983), RMSP ROP to Tieleman and Hinton (2012), RMS TEROV is our own, A DAM to Kingma and Ba (2015), and NA DAM to Dozat (2016).”
Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour (2017, background): “Minibatch Stochastic Gradient Descent [31], usually referred to as simply as SGD in recent literature even though it operates on minibatches, performs the following update: Here B is a minibatch sampled from X and n = |B| is the minibatch size . η is the learning rate and t is the iteration index.”
Learning Energy-Based Spatial-Temporal Generative ConvNets for Dynamic Patterns (2019, methodology): “The convergence of the algorithm has been studied by [26], [58].”
Learning Non-Convergent Non-Persistent Short-Run MCMC Toward Energy-Based Model (2019, methodology): “The above estimating equation can be solved by Robbins-Monro’s stochastic approximation [38], as long as we can generate independent fair samples from qθ .”
Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution (2022, background): “Therefore, it is natural to expect a similar behavior for SPS, if 1 /c k saﬁsﬁes the usual Robbins-Monro conditions [27]: P P We show that this is not the case : quite interestingly, f ( x k ) converges to a biased solution due to the correlation between r f i k and � k . we show this formally, in…”
Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, background): “Stochastic gradient descent (SGD) (Robbins & Monro, 1951; Nemirovski & Yudin, 1978; 1983; Nemirovski et al., 2009; Hardt et al., 2016; Gower et al., 2019; 2020; Loizou et al., 2020) is the workhorse for training supervised machine learning problems.”
Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, methodology): “Stochastic gradient descent (SGD) (Robbins and Monro, 1951; Nemirovski and Yudin, 1978, 1983; Shalev-Shwartz et al., 2007; Nemirovski et al., 2009; Hardt et al., 2016), is the workhorse for training supervised machine learning problems that have the generic form (1).”
Reducing Noise in GAN Training with Variance Reduced Extragradient (2019, methodology): “These iterative methods handle large training datasets by computing estimates of the said gradient on mini-batches instead of using all the samples at every step, resulting in a method called stochastic gradient descent (SGD) (Robbins and Monro, 1951; Bottou, 2010).”
Coulomb GANs: Provably Optimal Nash Equilibria via Potential Fields (2017, background): “To achieve true mathematical convergence, Heusel et. al [19] assume decaying learning rates to anneal the random ﬂuctuations, similar to Robbins-Monro’s original convergence proof for SGD [37].”
Variance Reduced Stochastic Gradient Descent with Neighbors (2015, background): “While SGD requires asymptotically vanishing learning rates, often chosen to be O(1/t) [7], these more recent methods introduce corrections that ensure convergence for constant learning rates.”
High-Performance Large-Scale Image Recognition Without Normalization (2021, methodology): “We train using the categorical softmax cross-entropy loss with label smoothing of 0.1 (Szegedy et al., 2016b), and optimize our networks using stochastic gradient descent (Robbins & Monro, 1951) with Nesterov’s momentum (Nesterov, 1983; Sutskever et al., 2013), using a momentum coefficient of 0.9.”
Learning to Learn with Generative Models of Neural Network Checkpoints (2022, positive): “SGD and Adam use tuned learning rates and weight decays.”