Gradient Descent, Learning Rates & Convergence
“x_{k+1} = x_k - alpha grad(f), Lipschitz smoothness L, optimal step size alpha < 2/L, condition number kappa, and oscillations.”
1.Gradient Descent Dynamics & The Lipschitz Bound
§ 5.1.Gradient Descent is the workhorse algorithm of machine learning, iteratively stepping in the negative gradient direction:
x_{k+1} = x_k - alpha grad(f(x_k)).
The Lipschitz Smoothness Constant L:
A continuously differentiable function f is L-smooth if its gradient does not change arbitrarily fast:
||grad(f(x)) - grad(f(y))|| <= L ||x - y||.
For twice-differentiable functions, L = sup_x ||H(x)||_2 = lambda_{max}(H).
The Stability Threshold:
Using the Descent Lemma, setting alpha < 2 / L guarantees that the objective decreases at every iteration (f(x_{k+1}) < f(x_k)).
The Ravine Problem (Conditioning):
When kappa = lambda_{max} / lambda_{min} is large, contours are highly elongated ellipses. The gradient vector points almost perpendicular to the direction toward the true minimum, causing zig-zag oscillations.
2. Worked Practice Problem: Maximum Stable Learning Rate on Quadratic Loss
The maximum stable learning rate is alpha_max = 2 / lambda_max, NOT 1 / lambda_max.
Problem: Consider the quadratic loss function f(x, y) = 4*x^2 + y^2. (a) Find the Lipschitz constant L and the maximum stable learning rate alpha_max. (b) Trace the first Gradient Descent update starting from (x0, y0) = (1, 1) with learning rate alpha = 0.1.
Step 1: Compute Hessian matrix H:
df/dx = 8*x => d^2 f / dx^2 = 8.
df/dy = 2*y => d^2 f / dy^2 = 2.
d^2 f / dxdy = 0.
Hessian H = [ [8, 0], [0, 2] ].
Step 2: Find eigenvalues and Lipschitz constant L:
Eigenvalues are the diagonal entries: lambda1 = 8, lambda2 = 2.
Lipschitz constant L = lambda_max(H) = 8.
Condition number kappa = lambda_max / lambda_min = 8 / 2 = 4.
Step 3: Determine maximum stable learning rate alpha_max:
alpha_max = 2 / L = 2 / 8 = 0.25.
(For alpha >= 0.25, the algorithm diverges along the x-axis).
Step 4: Trace step 1 with alpha = 0.1 from (x0, y0) = (1, 1):
grad(f)(1, 1) = [ 8(1), 2(1) ]^T = [ 8, 2 ]^T.
x_1 = x_0 - alpha grad(f)_x = 1 - 0.1 8 = 1 - 0.8 = 0.2.
y_1 = y_0 - alpha grad(f)_y = 1 - 0.1 2 = 1 - 0.2 = 0.8.
Updated point: (x1, y1) = (0.2, 0.8).
Step 5: Verify descent in objective function:
Initial loss: f(1, 1) = 4(1)^2 + 1^2 = 5.0.
Updated loss: f(0.2, 0.8) = 4(0.2)^2 + (0.8)^2 = 4(0.04) + 0.64 = 0.16 + 0.64 = 0.80.
Loss decreased from 5.00 to 0.80.
Conclusion: L = 8, alpha_max = 0.25; after 1 step with alpha = 0.1, (x1, y1) = (0.2, 0.8) with loss reduced to 0.80.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.