• Refs, mostly TODO
  • MIT 6.7220 https://www.mit.edu/~gfarina/notes/
    • https://www.mit.edu/~gfarina/2024/67220s24_L12_newton/
  • Deep Learning book chapter 8 optimization
  • https://www.cs.toronto.edu/~rgrosse/courses/csc2541_2022/
• Schedule-free AdamW / The road less scheduled
• Preconditioning
• Shampoo optimizer

Second-order optimization algorithms

• Newton’s method aka Newton-Raphson: iteratively find tangent line (or quadratic, etc.) and find its root (or min for quadratic). This is for finding zeros, but apply it to the gradient to find the minimum, ie where the first derivative is 0. This requires knowledge of the second derivatives ie Hessians
  • Often uses a quadratic instead of a line, ie the second order Taylor expansion.

• BFGS/L-BFGS (source): quasi Newton's method. TODO
  • L is limited memory
  • Preconditions the gradient with curvature information
  • Covered in Deep Learning book
• Line search (source)
• Research includes Shampoo optimizer, SOAP kind-of, and Muon
• Duality
  • Given gradient G of a weights M, update M by UV', where USV' is the SVD of G. This generalizes g / ||g||
  • Muon similar but accumulates the gradient. Without this, they agree and agree with shampoo.
• K-FAC: quasi natural gradients

First-order optimization algorithms

• Coordinate descent: optimize only along individual dims at a time

  

  • Used in variational inference
  • When conditionals are easier to optimize
  • No step size. Choose dims round robin or randomly.

• Gradient descent (GD)

  • Invariant to rigid transformations (not scale)
  • Should strictly make loss go down every step (every step is a full batch epoch)

• Line search: Rather than a fixed learning rate, keep moving along the gradient direction until you minimize the objective

  • Since we are usually in a stochastic setting, this is actually not used

• Stochastic gradient descent (SGD)

  

  • vs GD is just full vs mini batch. GD is slow per step. SGD is just slow throughput.
  • The same final performance should be attainable using any batch size (See Shallue et al. 2018 and Why shouldn't the batch size be tuned to directly improve validation set performance?.

• SGD with momentum: first moment (velocity)

  

  • Nesterov momentum: update velocity first

  

• AdaGrad

  • Update each parameter differently, based on how much it has changed so far in training.
  • Intuition: if a component changed a lot (measured by the sum of its squared gradient), then it must have made a lot of progress toward the target, so slow down its effective learning rate with a larger denominator.

  

  

  • This lets you perform well if you’re in something less like a bowl and more like a valley, since you prioritize moving along the valley toward the goal instead of dropping straight to the bottom of the valley first and then moving toward the goal hi

• RMSprop (Hinton)

  • Problem with AdaGrad: it only decreases the LR
  • EWMA of square of gradient lets us increase or decrease LR, lets it forget the past