Efficient Estimations from a Slowly Convergent Robbins-Monro Process

By David Ruppert. 1988

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

Citations in the corpus

Emerging Properties in Self-Supervised Vision Transformers (2021, methodology): “Indeed, we observe that this teacher performs a form of model ensembling similar to Polyak-Ruppert averaging with an exponential decay [51, 59].”
Model soups: averaging weights of multiple fine-tuned models improves accuracy without increasing inference time (2022, background): “Most applications study models along the same optimization trajectory, e.g. (Ruppert, 1988; Polyak, 1990; Szegedy et al., 2016; Izmailov et al., 2018; Zhang et al., 2019; Kaddour et al., 2022; Junczys-Dowmunt et al., 2016).”
Communication trade-offs for synchronized distributed SGD with large step size (2019, methodology): “This problem has received attention from various communities over the last fifty years in optimization, stochastic approximation, and machine learning (Polyak and Juditsky, 1992; Ruppert, 1988; Fabian, 1968; Nesterov and Vial, 2008; Nemirovski et al., 2009; Shalev-Shwartz et al., 2009; Zhang, 2004).”
Local SGD Converges Fast and Communicates Little (2018, background): “Convergence proofs for SGD [20] typically rely on averaging of the iterates [14, 18, 21], tough also convergence of the last iterate can be proven [25].”
Averaging Weights Leads to Wider Optima and Better Generalization (2018, background): “Although the general idea of maintaining a running average of weights traversed by SGD dates back to Ruppert [1988], this procedure is not typically used to train neural networks.”
Efficient and Scalable Bayesian Neural Nets with Rank-1 Factors (2020, methodology): “If a single set of weights is sufﬁ-cient (as opposed to a distribution for model uncertainty), there are also empirically successful averaging techniques such as Polyak-Ruppert (Ruppert, 1988), checkpointing, and stochastic weight averaging (Izmailov et al., 2018).”
Sparsified SGD with Memory (2018, background): “Convergence proofs for SGD [29] typically rely on averaging the iterates [23, 27, 30], though convergence of the last iterate can also be proven [34].”
Lookahead Optimizer: k steps forward, 1 step back (2019, background): “While the idea of following the trajectory of weights dates back to Ruppert [36], Polyak and Juditsky [34], averaging weights in neural networks has not been carefully studied until more recently.”
Connecting Generative Adversarial Networks and Actor-Critic Methods (2016, neutral): “Historical averaging is also closely related to PolyakRuppert averaging and extensions [14, 15].”
On the rates of convergence of parallelized averaged stochastic gradient algorithms (2017, background): “In order to improve the convergence, [9,10] introduced the Averaged Stochastic Gradient Descent (ASGD for short).”
An Overview of Stochastic Approximation (2015, background): “Iterate averaging, which takes the average of all iterates as the output as opposed to the final iterate, was the earliest proposal [31, 34].”
Boulevard: Regularized Stochastic Gradient Boosted Trees and Their Limiting Distribution (2018, methodology): “Similarly, among classic stochastic gradient methods, Ruppert-Polyak (Polyak and Juditsky, 1992; Ruppert, 1988) averaging implies asymptotic normality for model parameter estimators by averaging the gradient descent history.”
Quantitative Central Limit Theorems for Discrete Stochastic Processes (2019, result): “…Tη(x) is not Gaussian, and second, the diffusion matrix in (5) varies with x. Finally, this work is also motivated by results such as those due to Ruppert (1988), Polyak and Juditsky (1992), Fan et al. (2018), which show that iterates of the stochastic gradient algorithm with diminishing step…”
Statistical inference for model parameters in stochastic gradient descent (2016, methodology): “When x̄n is adopted as the solution, the algorithm is referred to as the averaged SGD (ASGD), and such an averaging step is known as the Polyak-Ruppert averaging (Ruppert, 1988; Polyak and Juditsky, 1992).”
The statistical evaluation of social network dynamics (2001, methodology): “However, Polyak (1990), Ruppert (1988), and Yin (1991) (as discussed also by Pflug, 1996, Section 5.1.3, and Kushner and Yin, 1997) showed that if all eigenvalues of the matrix of partial derivatives, (∂EθZ/∂θ), have positive real parts and certain regularity conditions are satisfied, then…”
Parallelizing Stochastic Approximation Through Mini-Batching and Tail-Averaging (2016, methodology): “We split the work related to this paper’s contributions into several algorithm classes: Stochastic Approximation: Seminal works of Ruppert [15], and Polyak and Juditsky [8] showed that averaging iterates of SGD applied to stochastic optimization problems like stochastic least squares regression achi”
Reinforcement Learning: An Introduction (1998, background): “The notions of momentum (Derthick, 1984), of Polyak-Ruppert averaging (Polyak, 1991; Ruppert, 1988; Polyak and Juditsky, 1992), or further extensions of these ideas may significantly help.”