BSNotes.in — Notes for IIT Madras BS StudentsSearch your notes⌘ K
REVISION AND PRACTICE

Week 4 Quick Revision

3 min read
On this page 6 headings

Swipe long formulas, tables or code sideways to see the rest.

Start here All of Week 4 on one page: why plain gradient descent is slow, momentum, NAG, stochastic/mini-batch versions, learning-rate tips and line search.

The story in 6 lines

  1. Gradient descent steps are η×\eta \times slope → tiny steps on gentle slopes.
  2. Contour maps: lines close together == steep, far apart == gentle.
  3. Momentum: remember past gradients (ut=βut−1+∇wt)→(u_t = \beta u_{t-1} + \nabla w_t) \to fast on flat regions, but overshoots with U-turns.
  4. NAG: measure the gradient at the look-ahead point → shorter U-turns.
  5. SGD / mini-batch: update after 1 / B points → many more updates per epoch, but noisy.
  6. Learning rate: search on a log scale, decay over time, or pick per step with line search.

Key formulas

Method Update
Gradient descent wt+1=wt−η∇wtw_{t+1} = w_t - \eta \nabla w_t
Momentum ut=βut−1+∇wt;wt+1=wt−ηut(u−1=0,0≤β<1)u_t = \beta u_{t-1} + \nabla w_t; w_{t+1} = w_t - \eta u_t (u_{-1} = 0, 0 \le \beta < 1)
Momentum unrolled ut=∑τ=0tβt−τ∇wτu_t = \sum _{\tau =0}^{t} \beta ^{t-\tau } \nabla w_\tau
NAG ut=βut−1+∇(wt−βut−1);wt+1=wt−ηutu_t = \beta u_{t-1} + \nabla (w_t - \beta u_{t-1}); w_{t+1} = w_t - \eta u_t
Exponential decay η=η0e−kt\eta = \eta _{0} e^{-kt}
1/t decay η=η0/(1+kt)\eta = \eta _{0} / (1 + kt)
Step decay halve η\eta every few epochs, or when validation error rises
Sutskever momentum βt=min⁡(1−2−1−log2(⌊t/250⌋+1),βmax)\beta _t = \min (1 - 2^{-1 - log_{2}(⌊t/250⌋ + 1)}, \beta _{\mathrm{max}})

Steps per epoch

Algorithm Steps in 1 epoch
Batch (vanilla) GD 1
SGD N
Mini-batch GD N / B

Compare at a glance

Method Speed on flat regions Oscillations Cost per step
GD slow none (true gradient) full data
Momentum fast big U-turns full data
NAG fast smaller U-turns full data
SGD many cheap steps very noisy 1 point
Mini-batch balance reduced noise B points
Line search faster than fixed η\eta some (from bigηbig \eta picks) several loss evaluations

Common traps

  • In the code, η\eta is inside u(u=βu+η∇w,w=w−u)u (u = \beta u + \eta \nabla w, w = w - u); in the formula it is outside. Same result for a fixed η\eta .
  • The momentum code on the slide writes “w=w−vww = w - vw” — it should be uw (typo).
  • The exponential decay slide prints “η0−kt\eta _{0}^{-kt}”; the standard formula is η0e−kt\eta _{0}e^{-kt}.
  • β=0\beta = 0 turns momentum back into plain gradient descent.
  • A larger batch reduces, but never fully removes, the oscillations (unless B=NB = N).
  • The lecture’s title also lists AdaGrad, RMSProp and Adam, but these slides end at line search — the adaptive methods are in the next set of lectures.

Exam words: plateau, contour, momentum, exponentially weighted average, NAG, look-ahead, stochastic gradient descent, mini-batch, epoch, step, learning rate, annealing, step/exponential/1/t decay, line search.

Quick check

  1. β=0.9,∇w0=1,∇w1=1\beta = 0.9, \nabla w_{0} = 1, \nabla w_{1} = 1. Find u1u_{1}.
u0=1;u1=0.9×1+1=1.9. u_{0} = 1; u_{1} = 0.9 \times 1 + 1 = 1.9.
  1. N=500,B=50N = 500, B = 50. Steps per epoch for each algorithm?
Batch 1, SGD 500, mini-batch 10.
  1. What problem does NAG fix in momentum?
The large overshoots/oscillations — by computing the gradient at the look-ahead point it corrects course earlier.
  1. Recommended first values to try for η\eta ?
0.0001, 0.001, 0.01, 0.1, 1.0 (a log scale), then a finer search around the best one.
  1. What’s the downside of line search?
More computation per step — one loss evaluation per candidate η\eta .
YOUR STUDY PROGRESS

Finished this section? Save your progress.

Back to top ↑