Gradient Descent

Gradient descent minimizes a differentiable objective by repeatedly moving opposite the gradient. It is the simplest first-order optimizer and the conceptual base for stochastic and adaptive deep-learning optimizers.

Defining math

For objective $f(\theta )$, the update is

$${\theta }_{t+1}={\theta }_t-\eta \nabla f({\theta }_t),$$

where $\eta >0$ is the learning rate. On a quadratic $f(x)=(x-a{)}^2$, the gradient is $2(x-a)$, so the update contracts the distance to $a$ when $0<\eta <1$:

$$x_{t+1}-a=(1-2\eta )(x_t-a).$$

In convex optimization, suitable step sizes can provide convergence guarantees. In nonconvex learning, the same update is useful but no longer guarantees a global optimum.

Worked example

Minimize $f(x)=(x-1{)}^2$ from $x_0=6$ with $\eta =0.2$. The update $x_{t+1}=x_t-\eta \cdot 2(x_t-1)$ turns, after subtracting the minimizer, into a geometric contraction with factor $1-2\eta =0.6$:

$$x_t-1=(1-2\eta {)}^t(x_0-1)=0.6^t\cdot 5.$$

After twelve steps, $x_{12}-1=0.6^{12}\cdot 5\approx 0.0109$, so $x_{12}\approx 1.0109$ and $f(x_{12})=(0.0109{)}^2\approx 1.2\times 10^{-4}$: the iterates nearly reach the minimizer, and the error shrinks by a factor of $0.6$ each step.

The path on the loss curve shows the same contraction geometrically: each step moves left toward the minimum and the vertical loss value shrinks rapidly.

Caveats

Learning rate dominates behavior. Too small wastes iterations; too large oscillates or diverges. Ill-conditioned curvature makes progress fast in steep directions and slow in flat ones, which is why scaling, momentum, and second-order information matter.

References

• Boyd and Vandenberghe, Convex Optimization
• MIT OpenCourseWare: 18.02SC Multivariable Calculus

Nav

Section — Mathematical Foundations

← Constrained Optimization Stochastic Gradient Descent →