Some methods of speeding up the convergence of iteration methods

By Boris Polyak. 1964

Subfields: Numerical Methods & Scientific Computing

How researchers see this paper

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

In Numerical Methods & Scientific Computing

Citations in the corpus

Semi-Supervised Sequence Modeling with Cross-View Training (2018, methodology): “The model is trained using SGD with momentum (Polyak, 1964; Sutskever et al., 2013).”
Measuring the Effects of Data Parallelism on Neural Network Training (2018, methodology): “ult of mini-batch SGD can be any of the iterates tfor which we estimate that L( t) is low using a validation data set. Variants of SGD commonly used with neural networks include SGD with momentum (Polyak, 1964; Rumelhart et al., 1986; Sutskever et al., 2013), Nesterov momentum (Nesterov, 1983; Suts”
VirTex: Learning Visual Representations from Textual Annotations (2020, background): “9 [92, 93] and weight decay 10 wrapped in LookAhead [94] with α = 0.”
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).”
FixMatch: Simplifying Semi-Supervised Learning with Consistency and Confidence (2020, methodology): “We also found that using the Adam optimizer [19] resulted in worse performance and instead use standard SGD with momentum [42, 33, 29].”
Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “For SGD, we compare against its generic version and with Polyak acceleration (Polyak, 1964), where in both cases the step size is chosen via stochastic line-search (Vaswani et al., 2019b) with the same hyperparameters, and the acceleration hyperpa-rameter is chosen via grid search.”
A Tight and Unified Analysis of Extragradient for a Whole Spectrum of Differentiable Games (2019, methodology): “On the other hand, for convex optimization problems, i.e. purely cooperative games, it is well known that adding positive momentum yields accelerated rates (Polyak, 1964).”
Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “In Appendix A, we also give upper bounds on η k if the function f i k satisﬁes the Polyak-Lojasiewicz (PL) inequality [67, 38] with constant µ ik .”
Negative Momentum for Improved Game Dynamics (2018, background): “Optimization From an optimization point of view, a lot of work has been done in the context of understanding momentum and its variants (Polyak, 1964; Qian, 1999; Nesterov, 2013; Sutskever et al., 2013).”
High-Performance Large-Scale Image Recognition Without Normalization (2021, methodology): “We employ an exponential moving average of the model parameters (similar to Polyak averaging (Polyak, 1964)), with a decay rate of 0.99999 which, following Tan & Le (2019), follows a warmup schedule where the decay is equal to min(0.99999, 1+t10+t ).”
Optimization Methods for Large-Scale Machine Learning (2016, background): “ne could argue that iterate averaging methods 20 do not neatly belong in the category of second-order methods, even though we place them there, and one could argue that gradient methods with momentum [120] or acceleration [106,107] do belong in this category, even though we discuss them separately i”
GANs Trained by a Two Time-Scale Update Rule Converge to a Nash Equilibrium (2017, methodology): “derived a discrete and stochastic version of Polyak’s Heavy Ball method [44], the Heavy Ball with Friction (HBF) [16]: θn+1 = θn − a(n+ 1)mn , (165) mn+1 = ( 1 − a(n+ 1) r(n) ) mn + a(n+ 1) r(n) ( ∇f(θn) + Mn+1 ) .”
AdaCliP: Adaptive Clipping for Private SGD (2019, methodology): “SGD and its variations such as momentum [27], Adagrad [28], or Adam [29] are used for training machine learning models.”
On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization (2019, methodology): “Momentum methods are originally proposed by Polyak in (Polyak, 1964) to minimize deterministic strongly convex quadratic functions.”
Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, methodology): “In practice, these methods are augmented with some form of momentum or acceleration [27, 25] that results in faster empirical convergence [37].”
DISCO Nets : DISsimilarity COefficients Networks (2016, methodology): “ and train only on 62,757 examples. Back-propagation is used with Stochastic Gradient Descent with a batchsize of 256. The learning rate is ﬁxed to = 0:01 and we use a momentum of m= 0:9 (see Polyak [18]). We also add L2-regularisation controlled by the parameter C. We use C= [0:0001;0:001;0:01] whi”
Text Understanding from Scratch (2015, methodology): “The algorithm used in training our model is stochastic gradient descent (SGD) with a minibatch of size 128, using momentum(Polyak, 1964)(Sutskever et al.”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “Acceleration ideas for gradient methods in convex optimization can be traced back to the work of Polyak [73] and Nesterov [68, 69].”