5.3.1. Gradient Descent

Gradient Descent

Gradient Descent is an optimization method used to minimize an objective (loss) function $E$ by iteratively updating model parameters in the opposite direction of the gradient. It serves as the core algorithm of modern machine learning, underlying methods from linear regression to deep neural networks, as those methods have non-linear or non-convex loss functions that do not yield a closed-form solution.

Gradient descent finds the parameter vector $w^{\ast }$ that minimizes a differentiable loss function $E(w)$, such that the objective function is
$w^{\ast }=\arg {\min }_{w\in {\mathbb{R}}^d}E(w).$

Simple gradient descent updates $w$ iteratively using the batch gradient descent algorithm, which begins at an arbitrary estimate $w^{(0)}$ and updates $w$ at each time step $t$:
$w^{(t)}=w^{(t-1)}-\eta \nabla E(w^{(t-1)}),$
where $0<\eta$ is the learning rate hyperparameter that controls step size, and $\nabla E(w)$ is the gradient of $E$ (indicating the direction of steepest increase of the loss function). Moving in the opposite direction of the gradient reduces the function value.

Batch gradient descent terminates when it has converged, i.e., when $\Vert w^{(\tau )}-w^{(\tau -1)}\Vert <\epsilon$. A maximum iteration size $T$ is also usually specified in the case that the algorithm does not converge.

However, over-reliance on $\eta$ can lead to oscillations ($\eta \gg$) or slow convergence ($\eta \ll$). As such, we introduce momentum, which picks up speed along the direction of repeated updates, decreasing the effective learning rate to stabilize gradient descent. We define velocity with a momentum hyperparameter $0\le \mu <1$,
$v^{(t)}=-\mu \nabla E(w^{(t-1)})+\mu v^{(t-1)},$
such that the update rule becomes $w^{(t)}=w^{(t-1)}+v^{(t)}.$ Note that since there is no momentum at time step $t=0$, it follows that $v^{(0)}=0$.

Convergence gradient descent is guaranteed to converge to the global minimum for convex loss functions, provided that the learning rate (and other hyperparameters) are chosen appropriately.

Note that

For non-convex loss functions, gradient descent may:

• fail to converge (e.g., due to oscillation or divergence), or
• converge to a local minimum, local maximum, or saddle point, rather than the global minimum.