6 / 8 Optimization Foundations

Escaping Along the Negative Curvature

f(x,y)=x2−y2f(x,y) = x^2 - y^2 has a critical point at the origin. Gradient descent with η=0.25\eta = 0.25 starts at (x0,y0)=(1, 10−3)(x_0, y_0) = (1,\ 10^{-3}):

xt+1=xt−η(2xt)=0.5 xt,yt+1=yt−η(−2yt)=1.5 ytx_{t+1} = x_t - \eta(2x_t) = 0.5,x_t, \qquad y_{t+1} = y_t - \eta(-2y_t) = 1.5,y_t

Where is the iterate after 20 steps, and what does that say about this kind of critical point?

A

Near (10−6, 10−3)(10^{-6},\ 10^{-3}): the yy gradient at y=10−3y = 10^{-3} is only −0.002-0.002, far too small to move the iterate anywhere.

B

Near (10−6, 3.3)(10^{-6},\ 3.3): xx halves every step while yy grows by 1.5x every step, so the run slides in along the positive-curvature direction and then leaves along the negative-curvature one. Only an exactly zero y0y_0 would leave it stuck.

C

At (0,0)(0, 0): the gradient vanishes there, so once gradient descent reaches such a point it has no direction to move in and stops.

D

Both coordinates blow up, because η=0.25\eta = 0.25 is past the stability limit for a curvature of magnitude 2.