Gradient Descent

§The model

The surface is a quadratic bowl,

$$f(x,y) = \tfrac{1}{2}\left(a x^2 + b y^2\right), \qquad a, b > 0,$$

whose only minimum is at the origin, and whose gradient is $\nabla f = (a x,\; b y)$. Gradient descent moves against the gradient by a fixed fraction $\eta$ of its size — the learning rate — at every step:

$$\mathbf{p}_{n+1} = \mathbf{p}_n - \eta\,\nabla f(\mathbf{p}_n).$$

§When it works, and when it does not

For this bowl the two coordinates do not interact, and each step simply multiplies $x$ by $(1 - \eta a)$ and $y$ by $(1 - \eta b)$. So the iteration converges exactly when both factors are smaller than one in magnitude, that is, when

$$\eta < \frac{2}{\max(a, b)}.$$

If a factor is negative but still smaller than one in size, that coordinate overshoots the bottom and lands on the other side at each step, shrinking all the while: oscillation. If a factor reaches one in magnitude the steps stop shrinking and the point leaves the frame: divergence. A bowl that is much steeper one way than the other ($a \ll b$) is the awkward case, because the rate that is safe for the steep direction is slow for the shallow one.

Everything above is true of this quadratic. For a general non-convex function gradient descent is only guaranteed, at best, a local minimum, and whether it reaches even that depends on the function and the learning rate.