MAP545 Revision Site

Optimization Extensions II and Deep-Learning Optimizers

Optimization Extensions II

← RNNs and Embeddings Back to Index Index →

Chapter Overview

This final optimization chapter finishes the taxonomy with coordinate methods, adaptive step-size ideas, and the optimizer recipes used in deep-learning libraries. It also includes the wrap-up perspective on why modern deep-learning optimizers combine several ingredients at once.

It matters because the course stops treating optimizers as purely theoretical objects and starts comparing them as practical engineering compromises: stochasticity, coordinate dependence, momentum, adaptivity, and acceptable low precision.

The key message is that optimizer design is compositional. Adagrad, RMSprop, and Adam are not magical black boxes: they are stochastic gradient methods equipped with coordinate-dependent adaptive scaling, and sometimes momentum.

Important Definitions

  • Coordinate method. Optimization method updating only one coordinate or one coordinate-wise scaled component at a time.
  • Coordinate-dependent step size (CDSS). Use a separate step size for each coordinate.
  • Coordinate gradient descent (CGD). Randomly sample one coordinate and update only that coordinate according to the partial derivative.
  • Exact coordinate descent (ECD). Update one coordinate by minimizing exactly along that coordinate direction.
  • Polyak step size. Adaptive step size based on the current objective gap and gradient norm.
  • Barzilai-Borwein step size. Adaptive step size based on the last displacement and the last gradient difference.
  • Adagrad. Coordinate-dependent stochastic method with cumulative squared gradients in the denominator.
  • RMSprop. Adagrad-style method replacing cumulative sums by an exponential moving average.
  • Adam. RMSprop-like second-moment adaptation plus an exponential moving average of the gradients themselves, i.e. momentum.

Key Concepts and Intuition

  • Coordinate methods lower the cost of one iteration. The lecture compares them to GD by emphasizing that a coordinate update can be roughly d times cheaper while still following a meaningful descent direction.
  • Adaptivity estimates local curvature without Hessians. Polyak and Barzilai-Borwein are both motivated by wanting larger, less pessimistic step sizes than the universal 1/L.
  • Deep-learning optimizers aim at low-to-medium precision efficiently. The lecture's summary slide explicitly classifies Adagrad, RMSprop, and Adam as stochastic, coordinate-dependent, adaptive, and suited to low precision.
  • Optimizer recipes combine ingredients. In practice one often wants stochastic gradients for scale, momentum for directional persistence, and coordinate-wise adaptation because gradient magnitudes can differ a lot across layers and parameters.
  • Loss landscapes in deep learning justify pragmatism. The lecture ties optimizer choice to nonconvexity, scale, and the fact that training rarely requires extremely high deterministic precision.

Mathematical Content

Coordinate methods.

\[\text{CDSS:} \theta_{t+1} = \theta_{t} - \eta \odot d \nabla f(\theta_{t})\]
\[\text{CGD:} update only coordinate j_{t}, ( \theta_{t+1} )_{j} = ( \theta_{t} )_{j} - \eta_{j}( \nabla f(\theta_{t}) )_{j}\]

The lecture motivates coordinate methods through diagonal quadratic structure: if curvature is essentially coordinate-wise, scaling coordinates separately makes immediate sense.

\[\text{CGD theorem slide:} \mathbb{E}[f(\theta_{t+1}) - f(\theta^*)] \le d/(1+t) ( f(\theta_{0}) - f(\theta^*) + (1/2)\|\theta_{0} - \theta^*\|^{2}_{L} )\]

Polyak step size.

\[\eta_{t}^{PS} = 2( f(\theta_{t}) - f(\theta^*) ) / \|\nabla f(\theta_{t})\|^{2}\]

The lecture emphasizes that this step size is larger than the pessimistic 1/L but requires knowledge of the optimal function value f*.

Barzilai-Borwein step size.

\[\eta_{t}^{BB} = \langle \theta_{t} - \theta_{t-1}, \nabla f(\theta_{t}) - \nabla f(\theta_{t-1}) \rangle / \|\nabla f(\theta_{t}) - \nabla f(\theta_{t-1})\|^{2}\]

Generic deep-learning optimizer template.

\[\theta_{t} = \theta_{t-1} - \eta_{t} d g_{t}(\theta_{t-1}) + \beta_{t}(\theta_{t-1} - \theta_{t-2})\]

This single template is used in the lecture to explain Adagrad, RMSprop, and Adam as combinations of stochastic gradients, coordinate dependence, adaptation, and sometimes momentum.

Adagrad.

\[\eta_{t} = \gamma_{0} / sqrt( \sum_{τ=1}^{t} (g_{τ}(\theta_{τ-1}))^{2} + \epsilon )\]

The division is coordinate-wise. Large accumulated gradients shrink future learning rates on those coordinates.

RMSprop.

\[v_{t} = \alphav_{t-1} + (1 - \alpha)(g_{t}(\theta_{t-1}))^{2}\]
\[\eta_{t}^{RMSprop} = \gamma_{0} / \sqrt{v_{t} + \epsilon}\]

Adam.

\[m_{t} = (1 - \beta_{1}) g_{t}(\theta_{t-1}) + \beta_{1} m_{t-1}\]
\[v_{t} = \alphav_{t-1} + (1 - \alpha)(g_{t}(\theta_{t-1}))^{2}\]
\[\theta_{t} = \theta_{t-1} - (\gamma_{0} / \sqrt{v~_{t} + \epsilon}) m~_{t}\]
\[m~_{t} = m_{t} / (1 - \beta_{1}^{t}), v~_{t} = v_{t} / (1 - \alpha^{t})\]

The lecture presents Adam as RMSprop plus a momentum-like first-moment estimate and bias correction.

Distinctions and Comparisons

  • Coordinate descent vs full-gradient descent. Coordinate methods reduce iteration cost and can fit anisotropic structure, but they do not use all gradient information at once.
  • Polyak vs Barzilai-Borwein. Both are adaptive and larger than a worst-case 1/L rule, but Polyak needs the optimal value f*, while BB only uses the last two iterates and gradients.
  • Adagrad vs RMSprop. Adagrad accumulates all past squared gradients and can become too conservative; RMSprop uses a moving window through an exponential average.
  • RMSprop vs Adam. Adam adds a momentum-style first-moment average on top of RMSprop's second-moment normalization.
  • Theoretical optimizer taxonomy vs library names. The lecture keeps reminding that these named optimizers are combinations of more primitive design choices.

Exam-Oriented Understanding

  • For adaptive methods, explain the motivation: larger local step sizes than the globally pessimistic 1/L, not just "better in practice".
  • For Adam-like methods, describe the ingredients explicitly: stochastic gradients, coordinate-wise scaling, adaptivity, and momentum.
  • For large-scale nonconvex deep-learning problems, the lecture's practical ranking logic favors adaptive stochastic methods because they cope with scale and only low precision is typically required.
  • When asked to rank methods or justify fit, mention both the advantage and the drawback. Memory cost, curvature handling, dependence on n and d, and target precision all matter.

Source References

  • Optimization Lecture 3 (APM52445-Optimization-Lect3.pdf), slides 47-54: Coordinate methods, coordinate-wise descent variants, theory and cost comparison.
  • Optimization Lecture 3 (APM52445-Optimization-Lect3.pdf), slides 58-63: Adaptive step sizes, Polyak and Barzilai-Borwein heuristics.
  • Optimization Lecture 3 (APM52445-Optimization-Lect3.pdf), slides 67-77: Loss landscape in deep learning, optimizer recipes in libraries, Adagrad, RMSprop, Adam, summary of deep-learning methods.
Only lecture PDFs are used as content sources here. The sample exam is used only to choose emphasis and exam-answer style.

Relevant Exam Alignment

The sample exam asks about method choice under poor conditioning, large-scale finite sums, variance reduction, and ranking of optimizers for a large nonconvex deep-learning problem. This chapter provides the vocabulary needed to justify such rankings instead of guessing them.

A good answer does not stop at naming a method. It says why that method matches the regime: large n, large d, poor conditioning, moderate precision, or nonconvex deep-network training.

← RNNs and Embeddings Back to Index Index →