Gradient Descent

Let $L:\mathbb{R}^p\to\mathbb{R}$ be a loss function and let $\theta_t\in\mathbb{R}^p$ be the current parameter vector. Under the standard Euclidean inner product, the gradient

$$\nabla_\theta L(\theta_t)$$

points in the direction of steepest local increase. Gradient descent uses the update

$$\theta_{t+1} = \theta_t - \eta \nabla_\theta L(\theta_t),$$

where $\eta > 0$ is the learning rate.

If $L$ is differentiable near $\theta$ and $\nabla L(\theta)\neq 0$, the first-order Taylor approximation says

$$L(\theta-\eta\nabla L(\theta)) \approx L(\theta)-\eta\|\nabla L(\theta)\|^2.$$

That is the local reason stepping against the gradient should reduce the loss. The learning rate controls how much you trust this local approximation. If $\eta$ is too small, training makes slow progress. If $\eta$ is too large, the update can jump across a valley or even increase the loss. On a quadratic loss, this tradeoff is governed by curvature: steep directions demand smaller stable steps than flat directions.

At a stationary point, $\nabla L(\theta)=0$, so this first-order decrease argument disappears. In a nonconvex loss, such a point might be a minimum, a saddle, or a maximum.

For the quadratic used below,

$$L(\theta)=\frac12\theta^{\mathsf T}A\theta,$$

with $A$ symmetric positive definite, the gradient is $\nabla L(\theta)=A\theta$. In an eigen-direction of $A$ with curvature $\lambda_i$, the update becomes

$$z_{i,t+1}=(1-\eta\lambda_i)z_{i,t}.$$

Fixed-step descent is stable only when $|1-\eta\lambda_i|<1$ for every direction, so

$$0<\eta<\frac{2}{\lambda_{\max}}.$$

This is the stability bound used by the code and the demo.

In deep learning, the exact gradient over the whole dataset is often too expensive. For a training set of $n$ examples, define the empirical risk

$$L_{\mathrm{emp}}(\theta)=\frac1n\sum_{i=1}^n \ell(f_\theta(x_i),y_i).$$

For a mini-batch $B_t$, we instead compute

$$g_t = \nabla_\theta\left(\frac{1}{|B_t|}\sum_{i\in B_t}\ell(f_\theta(x_i),y_i)\right).$$

With uniform sampling, $g_t$ estimates $\nabla L_{\mathrm{emp}}(\theta_t)$. That turns gradient descent into stochastic gradient descent. The update is the same shape, but the direction is noisy:

$$\theta_{t+1} = \theta_t - \eta g_t.$$