You are viewing a public preview
Sign in to save your progress, do assignments, join discussions and get feedback.
Flashcards · Optimization and gradient descent
10 wordsmin L(x) over a feasible set D: choose x ∈ D to make the objective L as small as possible.
Global: L(x*) ≤ L(x) for all feasible x. Local: only for feasible x in a small ball around x*.
An interior point with ∇L = 0. Every differentiable interior local minimiser is stationary, but not every stationary point is a minimum.
For a differentiable convex L, ∇L(x) = 0 implies x is a global minimiser. Least-squares loss for an affine model is convex.
x_{k+1} = x_k − η_k ∇L(x_k). Compute every component of the gradient at the same x_k before updating.
L(x − ηg) = L(x) − η‖g‖² + o(η): a small step along −g strictly lowers L when g ≠ 0.
For L = (x − 2)², x_{k+1} − 2 = (1 − 2η)(x_k − 2). Convergence iff 0 < η < 1; η = 1 bounces, η > 1 diverges.
Test ‖g_k‖ ≤ ε for approximate stationarity. A small step η‖g‖ or small loss change can occur with a tiny η while the gradient is large.
For a quadratic with Hessian H: best step along −g is ‖g‖²/(gᵀHg); a fixed rate converges iff 0 < η < 2/λ_max.
Centering/rescaling a feature leaves the best-fitting line unchanged but reshapes the loss, changing the path and speed of gradient descent.
Work through Section 4 of Lab 2 (Calculus and Optimization, MFDS_Lab2_Calculus_Optimization.ipynb), attached to the Part II materials lesson at the start of this part.