PaperlayerView exact revision on arXiv

Source-linked AI summary

An overview of gradient descent optimization algorithms

Sebastian Ruder

arXiv:1609.04747v2cs.LG

TL;DR

Gradient descent optimizers are widely used as black boxes because practical explanations of their strengths and weaknesses are limited. This article provides intuitions through an overview of variants, challenges, optimization algorithms, distributed approaches, and additional strategies, highlighting methods and strategies for improving gradient descent in practice.

  • Problem

    Practical explanations of gradient descent optimizers’ strengths, weaknesses, and learning-rate challenges are limited, despite their widespread use.

  • Method

    The article surveys gradient descent variants, training challenges, common optimization algorithms, distributed architectures, and additional improvement strategies.

  • Results

    The overview covers Momentum, Nesterov accelerated gradient, Adagrad, Adadelta, RMSprop, Adam, AdaMax, Nadam, asynchronous SGD, and strategies including curriculum learning and batch normalization.

  • Takeaways & Limitations

    The article offers practical intuitions for understanding and applying different gradient descent optimization algorithms.

  • Takeaways & Limitations

    Adagrad’s accumulated squared gradients can shrink its learning rate until it becomes infinitesimally small and prevents further learning.

Abstract

from arXiv · show

Gradient descent optimization algorithms, while increasingly popular, are often used as black-box optimizers, as practical explanations of their strengths and weaknesses are hard to come by. This article aims to provide the reader with intuitions with regard to the behaviour of different algorithms that will allow her to put them to use. In the course of this overview, we look at different variants of gradient descent, summarize challenges, introduce the most common optimization algorithms, review architectures in a parallel and distributed setting, and investigate additional strategies for optimizing gradient descent.

1 Introduction

The article explains gradient descent optimization algorithms that are often used as black-box optimizers, providing practical intuitions about their behavior, strengths, and weaknesses. It covers gradient-descent variants, training challenges, common optimizers, parallel and distributed architectures, and additional optimization strategies.

  • 1 Introduction: The article aims to provide intuitions about different optimization algorithms so readers can apply them rather than treating them as black boxes.It responds to the difficulty of finding practical explanations of algorithmic strengths and weaknesses.
  • 1 Introduction: The overview proceeds from gradient-descent variants and training challenges to common optimizers, parallel and distributed architectures, and additional optimization strategies.The stated organization introduces optimizers through the challenges they are motivated to resolve.
  • 1 Introduction: Gradient descent minimizes an objective by updating parameters opposite the gradient, with the learning rate controlling step size toward a local minimum.The process follows the downhill slope of the objective surface until reaching a valley.

2 Gradient descent variants

Gradient descent has three variants that trade parameter-update accuracy against update time according to how much data determines each gradient. Batch, stochastic, and mini-batch methods differ in computational cost, update variance, online capability, and convergence behavior.

  • Variants: The three gradient-descent variants differ in how much data is used to compute each objective-function gradient, trading update accuracy against update time.The variants are batch, stochastic, and mini-batch gradient descent.
  • Batch gradient descent: Batch gradient descent computes each gradient over the entire training dataset, making it slow, memory-intractable for oversized datasets, and unable to learn online.It computes one update after processing the whole dataset.
  • Batch gradient descent: Batch gradient descent converges to the global minimum on convex error surfaces and to a local minimum on non-convex surfaces.The learning rate determines the size of each parameter update.
  • Stochastic gradient descent: SGD updates parameters for each training example, removing redundant computation, usually running faster, supporting online learning, and causing high-variance objective fluctuations.Its fluctuations can help it jump to potentially better local minima but complicate convergence to the exact minimum.
  • Mini-batch gradient descent: Mini-batch gradient descent reduces update variance for more stable convergence and exploits efficient matrix operations; common mini-batch sizes range between 50 and 256.It is typically the algorithm of choice for neural-network training, and “SGD” often refers to it.

3 Challenges

Vanilla mini-batch gradient descent does not guarantee good convergence, and choosing an appropriate learning rate is difficult because rates that are too small slow convergence while rates that are too large hinder or destabilize it.

  • General challenge: Vanilla mini-batch gradient descent does not guarantee good convergence and presents challenges that require additional remedies.
  • Learning-rate selection: Choosing a proper learning rate is difficult: rates that are too small cause painfully slow convergence, whereas rates that are too large can hinder convergence, cause loss fluctuations, or lead to divergence.Learning rate schedules adjust the rate during training through annealing or when objective changes between epochs fall below a threshold.

4 Gradient descent optimization algorithms … 4.3 Adagrad

The section presents practical gradient-based optimizers, focusing on Momentum, Nesterov accelerated gradient, and Adagrad as methods for addressing difficult optimization landscapes and adapting updates. It emphasizes their mechanisms, benefits, and limitations, while excluding methods infeasible for high-dimensional data.

  • 4 Gradient descent optimization algorithms: The overview focuses on algorithms widely used in deep learning and excludes methods, such as Newton’s method, that are infeasible for high-dimensional data.The section frames the discussion around practical optimization algorithms rather than computationally impractical second-order methods.
  • 4.1 Momentum: SGD oscillates across ravine slopes and makes hesitant progress along the bottom toward local optima.Ravines are regions where the surface curves much more steeply in one dimension than another and commonly occur around local optima.
  • 4.1 Momentum: Momentum accelerates SGD in relevant directions and dampens oscillations by adding a fraction γ of the previous update vector to the current update.The momentum term increases updates when gradients point consistently in the same direction and reduces updates when gradient directions change.
  • 4.2 Nesterov accelerated gradient: Nesterov accelerated gradient looks ahead by evaluating the gradient at an approximate future parameter position.It first moves in the direction of the previous accumulated gradient, measures the gradient, and then applies a correction.
  • 4.2 Nesterov accelerated gradient: NAG’s anticipatory update prevents excessive speed and results in increased responsiveness.The momentum term γ is set to a value of around 0.9, similarly to Momentum.
  • 4.3 Adagrad: Adagrad adapts learning rates to individual parameters, making larger updates for infrequent parameters and smaller updates for frequent parameters.This makes Adagrad well-suited for sparse data, and Dean et al. found that it greatly improved SGD robustness in large-scale neural-network training at Google.
  • 4.3 Adagrad: Adagrad accumulates squared past gradients per parameter, uses a smoothing term usually on the order of 1e-8, and performs much worse without the square root.The accumulated squared gradients are represented along the diagonal of G_t, while ϵ prevents division by zero.
  • 4.3 Adagrad: Adagrad eliminates manual learning-rate tuning; most implementations use a default value of 0.01.Its main weakness is that accumulating positive squared gradients continually shrinks the learning rate until it can become infinitesimally small.

4.4 Adadelta

Adadelta extends Adagrad by replacing its monotonically decreasing accumulation of all past squared gradients with a decaying average over a fixed effective window. It also scales updates using previous parameter-update magnitudes, eliminating the need to set a default learning rate.

  • Method: Adadelta limits accumulated past squared gradients to a fixed-size window, reducing Adagrad’s aggressive, monotonically decreasing learning rate.The window is implemented through a recursively defined decaying average rather than storing all previous squared gradients.
  • Method: The method replaces Adagrad’s diagonal gradient accumulator with the decaying average E[g2]t over past squared gradients.This substitution produces an RMS-based gradient normalization criterion.
  • Method: Adadelta defines an exponentially decaying average of squared parameter updates to address the units mismatch between updates and parameters.The corresponding root mean squared parameter-update quantity is used to scale the update.
  • Update rule: Adadelta approximates the unknown current RMS parameter update with the previous-step RMS, replacing the learning rate in the update rule.This construction yields the final Adadelta update rule.
  • Result: Adadelta eliminates the default learning rate from its update rule.No default learning-rate value needs to be set.

4.5 RMSprop · 4.6 Adam · 4.7 AdaMax

RMSprop adapts learning rates using an exponentially decaying average of squared gradients, while Adam additionally tracks gradient means and corrects initialization bias. AdaMax replaces Adam’s second-moment scaling with an infinity-norm-based value that avoids bias correction for that term and is more stable for large-norm behavior.

  • 4.5 RMSprop: RMSprop and Adadelta were independently developed to address Adagrad’s radically diminishing learning rates, and RMSprop matches Adadelta’s first update vector.
  • 4.5 RMSprop: RMSprop divides the learning rate by an exponentially decaying average of squared gradients, with suggested γ = 0.9 and η = 0.001.
  • 4.6 Adam: Adam computes parameter-specific adaptive learning rates by tracking exponentially decaying averages of past squared gradients and past gradients.
  • 4.6 Adam: Adam’s moment estimates are biased toward zero initially because both vectors start at zero, especially when β1 and β2 are close to 1.
  • 4.6 Adam: Adam uses bias-corrected first- and second-moment estimates before applying its update rule.
  • 4.6 Adam: Adam’s proposed defaults are β1 = 0.9, β2 = 0.999, and 10^-8 for ϵ, and experiments show favorable practical comparisons with other adaptive methods.
  • 4.7 AdaMax: AdaMax uses an ℓ∞-constrained value for the second-moment factor because infinity norms generally remain stable, unlike large-p norms that can become numerically unstable.
  • 4.7 AdaMax: Because AdaMax’s max-based ut is not as susceptible to zero bias as Adam’s mt and vt, it requires no bias correction for ut; defaults are η = 0.002, β1 = 0.9, and β2 = 0.999.

4.8 Nadam

Nadam combines Adam with Nesterov accelerated gradient by modifying Adam’s momentum term. Its update uses the bias-corrected current momentum estimate rather than the previous one, while leaving the bias-corrected squared-gradient estimate unchanged.

  • 4.8 Nadam: Nadam combines Adam and Nesterov accelerated gradient by modifying Adam’s momentum term.Adam combines RMSprop’s exponentially decaying average of squared gradients with momentum’s exponentially decaying average of gradients, while NAG improves the gradient step.
  • 4.8 Nadam: NAG updates parameters using a look-ahead momentum vector, replacing the previous momentum vector with the current one.Dozat’s modification applies the look-ahead momentum vector directly to the parameter update rather than applying the momentum step twice.
  • 4.8 Nadam: Nadam replaces Adam’s bias-corrected previous momentum estimate ˆm_t−1 with the bias-corrected current estimate ˆm_t.This substitution produces the Nadam update rule while preserving Adam’s bias-corrected squared-gradient estimate ˆv_t.

4.9 Visualization of algorithms · 4.10 Which optimizer to use?

The visualizations show that adaptive learning-rate methods generally converge effectively and escape saddle points more readily than SGD, Momentum, and NAG. For optimizer selection, sparse inputs favor adaptive methods, while vanilla SGD can require more careful initialization and learning-rate scheduling.

  • 4.9 Visualization of algorithms: Adagrad, Adadelta, and RMSprop head directly toward the Beale-function minimum and converge similarly quickly, whereas Momentum and NAG initially veer off course.NAG corrects its course sooner because its look-ahead responsiveness improves tracking.
  • 4.9 Visualization of algorithms: At a saddle point, SGD, Momentum, and NAG struggle to break symmetry, while Adagrad, RMSprop, and Adadelta quickly descend along the negative slope.Momentum and NAG eventually escape, with Adadelta leading the adaptive methods.
  • 4.9 Visualization of algorithms: Adagrad, Adadelta, RMSprop, and Adam are most suitable and provide the best convergence in the visualized scenarios.The paper identifies these as adaptive learning-rate methods.
  • 4.10 Which optimizer to use?: For sparse input data, adaptive learning-rate methods likely achieve the best results and generally work well with the default learning-rate value.Their additional benefit is that learning-rate tuning is not required.
  • 4.10 Which optimizer to use?: RMSprop extends Adagrad by addressing radically diminishing learning rates, while Adadelta differs in its numerator update and Adam adds bias correction and momentum.RMSprop, Adadelta, and Adam are described as similar algorithms that perform well in similar circumstances.
  • 4.10 Which optimizer to use?: Bias correction helps Adam slightly outperform RMSprop toward the end of optimization.This comparison is attributed to Kingma et al.
  • 4.10 Which optimizer to use?: Vanilla SGD can find a minimum, but may take significantly longer, depend more on robust initialization and annealing, and get stuck at saddle points.The passage notes that many recent papers nevertheless use SGD without momentum with a simple learning-rate annealing schedule.

5 Parallelizing and distributing SGD

Section 5 explains how SGD can be parallelized and distributed to improve speed, while highlighting the tradeoff between asynchronous efficiency, communication quality, and convergence. It introduces methods that coordinate parallel updates through shared memory, parameter servers, delay adaptation, or elastic averaging.

  • Motivation: Distributed SGD addresses the slowness of inherently sequential optimization on large datasets, but asynchronous execution can trade faster computation for poorer convergence when communication is suboptimal.SGD progresses step-by-step toward a minimum; asynchronous variants are faster, but worker communication may limit convergence.
  • Parallel SGD: Hogwild! performs lock-free parallel SGD updates on shared CPU memory and achieves almost an optimal convergence rate when the input data is sparse.Sparsity limits each update to a fraction of the parameters, reducing the likelihood that processors overwrite useful information.
  • Asynchronous SGD: Downpour SGD runs model replicas asynchronously on data subsets, sending updates to a parameter server distributed across machines that store and update parameter fractions.The passage notes that replicas do not communicate directly, such as by sharing weights.
  • Delay-tolerant optimization: Delay-tolerant AdaGrad algorithms adapt to both past gradients and update delays in parallel settings and have been shown to work well in practice.McMahan and Streeter developed this extension of AdaGrad for parallel optimization.
  • Elastic averaging: Elastic Averaging SGD links asynchronous workers to a center variable with an elastic force, enabling greater parameter exploration that empirically improves performance by finding new local optima.The center variable is stored by the parameter server, while local variables can fluctuate farther from it.

6 Additional strategies for optimizing SGD

Additional SGD strategies include shuffling data, curriculum learning, batch normalization, early stopping, and gradient noise. These methods address ordering bias, normalization drift, validation performance, and difficult optimization landscapes.

  • Data ordering: Shuffling training data after every epoch helps avoid bias from presenting examples in a meaningful order.Meaningful ordering can instead help progressively harder problems through Curriculum Learning.
  • Data ordering: A mixed Curriculum Learning strategy outperformed the naive strategy that sorts examples by increasing difficulty and enabled LSTM training on simple program evaluation.Zaremba and Sutskever reported that Curriculum Learning was necessary for their LSTM training setting.
  • Normalization: Batch normalization reestablishes normalization for every mini-batch, enabling higher learning rates, reducing initialization sensitivity, and sometimes reducing the need for Dropout.It incorporates normalization into the model architecture and backpropagates changes through the operation.
  • Training control: Early stopping monitors validation error during training and stops optimization when the error fails to improve sufficiently, allowing some patience.The recommendation is framed as a way to prevent continued training without meaningful validation improvement.
  • Gradient noise: Adding Gaussian noise to gradient updates improves robustness to poor initialization and helps train particularly deep and complex networks.The authors suspect noise gives models more chances to escape and find new local minima, which occur more often in deeper models.

7 Conclusion

The article surveys gradient descent variants, optimization algorithms for SGD, asynchronous SGD methods, and additional strategies for improving SGD.

  • Gradient descent and SGD: The conclusion recaps three gradient descent variants, identifying mini-batch gradient descent as the most popular.It then frames the broader survey of methods for optimizing and improving SGD.
  • Optimization algorithms: The reviewed SGD optimizers include Momentum, Nesterov accelerated gradient, Adagrad, Adadelta, RMSprop, Adam, AdaMax, and Nadam.The article also investigates algorithms for optimizing asynchronous SGD.
  • Additional strategies: Additional strategies considered for improving SGD include shuffling, curriculum learning, and batch normalization.These strategies are presented alongside the surveyed gradient descent variants and optimization algorithms.
Loading 1609.04747v2…