Optimization Methods for Large-Scale Machine Learning

By L. Eon Bottou, Frank E. Curtis, Jorge Nocedal. 2016

3,928 citations recorded by the source corpus.

This paper provides a review and commentary on the past, present, and future of numerical optimization algorithms in the context of machine learning applications. Through case studies on text classification and the training of deep neural networks, we discuss how optimization problems arise in machine learning and what makes them challenging. A major theme of our study is that large-scale machine learning represents a distinctive setting in which the stochastic gradient (SG) method has traditionally played a central role while conventional gradient-based nonlinear optimization techniques typically falter. Based on this viewpoint, we present a comprehensive theory of a straightforward, yet versatile SG algorithm, discuss its practical behavior, and highlight opportunities for designing algorithms with improved performance. This leads to a discussion about the next generation of optimization methods for large-scale machine learning, including an investigation of two main streams of research on techniques that diminish noise in the stochastic directions and methods that make use of second-order derivative approximations.

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

Gradient Descent Happens in a Tiny Subspace (2018, methodology): “Its ubiquity in deep learning is connected to the efﬁciency at which gradients can be computed (Rumelhart et al., 1985; 1986), though its success remains somewhat of a mystery due to the highly nonlinear and nonconvex nature of typical deep learning loss landscapes (Bottou et al., 2016).”
Don't Decay the Learning Rate, Increase the Batch Size (2017, background): “…of recent works have discussed increasing the batch size during training (Friedlander & Schmidt, 2012; Byrd et al., 2012; Balles et al., 2016; Bottou et al., 2016; De et al., 2017), but to our knowledge no paper has shown empirically that increasing the batch size and decaying the learning…”
Group Normalization (2018, methodology): “In this set of experiments, we adopt the linear learning rate scaling rule [31, 4, 16] to adapt to batch size changes — we use a learning rate of 0.1 [20] for the batch size of 32, and 0.1 N/ 32 for a batch size of N .”
Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution (2022, background): “P A careful choice of � k is crucial for most applications [4, 14].”
Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, background): “…[Recht et al., 2011, Hazan and Kale, 2014, Rakhlin et al., 2012] or growth condition ( E (cid:107)∇ f i ( x ) 2 ≤ c 1 (cid:107)∇ f ( x ) 2 + c 2 ) [Bottou et al., 2018, Schmidt et al., 2017]. of shows (cid:107) (cid:107) However, a recent line work that these assumptions might be restrictive or…”
Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, methodology): “In this section, we assume a common condition used to prove convergence of SGD in the non-convex setting (Bottou et al., 2018).”
The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning (2017, methodology): “To keep the same covariance, (Bottou et al., 2016; Li, 2017; Hoffer et al., 2017) choose the step size η ∼ √ m for batch size m.”
On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima (2016, background): “These include guarantees of: (a) convergence to minimizers of strongly-convex functions and to stationary points for non-convex functions (Bottou et al., 2016), (b) saddle-point avoidance (Ge et al.”
Regularizing and Optimizing LSTM Language Models (2017, background): “SGD demonstrably performs well in practice and also possesses several attractive theoretical properties such as linear convergence (Bottou et al., 2016), saddle point avoidance (Panageas & Piliouras, 2016) and better generalization performance (Hardt et al., 2015).”
Towards Principled Methods for Training Generative Adversarial Networks (2017, background): “The noise in the curves also shows that the variance of the gradients is increasing, which is known to delve into slower convergence and more unstable behaviour in the optimization (Bottou et al., 2016).”
Sharp Minima Can Generalize For Deep Nets (2017, background): “For example, Duchi et al. (2011); Nesterov & Vial (2008); Hardt et al. (2016); Bottou et al. (2016); Go-nen & Shalev-Shwartz (2017) rely on the concept of stochastic approximation or uniform stability (Bousquet & Elisseeff, 2002).”
Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization (2020, methodology): “The analysis relies on Assumptions 1 and 2 used in the standard analysis of SGD [51] and Assumption 3 commonly used in the federated optimization literature [38, 12, 13, 20, 40, 2] to capture the dissimilarities of local objectives.”
On the Outsized Importance of Learning Rates in Local Update Methods (2020, methodology): “(2012) and Bottou et al. (2018)), combined with the results from Section 6.”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “, 2019) but instead allow the bound on the noise and the diversity to grow with the gradient norm (similar assumptions are common in the convex setting (Bottou et al., 2018)).”
Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization (2019, background): “References [10, 6] show, for strongly convex stochastic minimization, that SGD with exponentially increasing batch sizes can achieve linear convergence rate on a single machine.”
Communication Efficient Decentralized Training with Multiple Local Updates (2019, background): “The ﬁrst part is exactly the same as the optimization error bound in fully synchronous SGD [2].”
SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum (2019, background): “Finally, although momentum methods are known to achieve accelerated rates for deterministic optimization, currently the theoretical understanding of the benefits of momentum methods (both serial and parallel) is limited (Bottou et al., 2018).”
Decentralized Bayesian Learning over Graphs (2019, neutral): “This is unlike decentralized optimization and SGD based methods [15–21] where local (stochastic) gradients are computed for each instance of data and communication happens at a rate comparable to number of local updates.”