Comprehensive Notes on First-Order Optimization and Gradient Descent

First-Order Condition and Differentiability

The primary advantage of zero-order optimization methods is their general applicability, but this generality acts as a limitation because they do not utilize specific function properties like continuity or differentiability. If a function is known to be differentiable, optimization can be made more efficient by leveraging the first derivative, or gradient. The first-order condition for optimality states that for a differentiable function $g : \mathbb{R}^n \rightarrow \mathbb{R}$, a point $\mathbf{w}^* \in \mathbb{R}^n$ is a potential optimum if the gradient at that point is equal to the zero vector. This is expressed as:

$\nabla g(\mathbf{w}^*) = \begin{pmatrix} \frac{\partial g}{\partial w_1}(\mathbf{w}^*) \\ \frac{\partial g}{\partial w_2}(\mathbf{w}^*) \\ \vdots \\ \frac{\partial g}{\partial w_n}(\mathbf{w}^*) \end{pmatrix} = \mathbf{0}_{n \times 1}$

In the one-dimensional case where $g : \mathbb{R} \rightarrow \mathbb{R}$, this condition simplifies to $\frac{dg}{dw}g(w^*) = 0$. Points that satisfy this condition are known as critical points or stationary points. However, the first-order condition is a necessary but not sufficient condition for optimality. While every local or global optimum must be a critical point, not every critical point is an optimum; critical points also encompass maxima, minima, inflection points (in one dimension), and saddle points. High-level examples include the function $g(w) = \sin(3w)$ or $g(w) = w^3$, where derivatives can be analyzed to identify these stationary points.

Convexity and Global Optimality

Convexity is a property that makes the first-order condition sufficient for optimality. To understand this, several definitions are required. A point is a convex combination of two points $\mathbf{x}$ and $\mathbf{y}$ if it can be expressed as $\lambda \mathbf{x} + (1 - \lambda)\mathbf{y}$ for $\lambda \in [0, 1]$. A set $S \subseteq \mathbb{R}^n$ is considered a convex set if every pair of points within the set has its convex combination also within the set. Geometrically, this means the line segment joining any two points in the set is entirely contained within the set. A function $f : S \subseteq \mathbb{R}^n \rightarrow \mathbb{R}$ is convex if its domain $S$ is a convex set and for any pair $\mathbf{x}, \mathbf{y} \in S$, the inequality $f[\lambda \mathbf{x} + (1 - \lambda)\mathbf{y}] \leq \lambda f(\mathbf{x}) + (1 - \lambda)f(\mathbf{y})$ holds for all $\lambda \in [0, 1]$. Strict convexity occurs when the inequality is strict for $\mathbf{x} \neq \mathbf{y}$ and $\lambda \in (0, 1)$.

A function is convex if and only if its linear approximation at any point is a global underestimator of the function. This is defined by the first-order condition for convexity: $f(\mathbf{y}) \geq f(\mathbf{x}) + \nabla f(\mathbf{x})^T (\mathbf{y} - \mathbf{x})$ for all $\mathbf{x}, \mathbf{y} \in S$. This relationship implies that if the gradient at a point $\mathbf{x}$ is zero ($\nabla f(\mathbf{x}) = \mathbf{0}_{n \times 1}$), then $f(\mathbf{y}) \geq f(\mathbf{x})$ for all points in the set, making $\mathbf{x}$ a global minimum. Consequently, for convex functions, any local minimum is a global minimum, and the first-order condition is both necessary and sufficient. This efficiency is why convex optimization is a dominant field. A function is concave if its negative $-f$ is convex; maximizing a concave function is equivalent to minimizing a convex function.

The Gradient Descent Algorithm

Gradient descent is a local optimization method that utilizes the property that the gradient points in the direction of steepest ascent. Conversely, the negative gradient $-\nabla g(\mathbf{w})$ points in the direction of steepest descent. By consistently moving in the direction of the negative gradient, the algorithm is guaranteed to find a descent direction at each step. The algorithm requires an initial point $\mathbf{w}_0$, a step size parameter $\alpha$, and a maximum number of steps $K$. For each step $k = 1, 2, \dots, K$, the gradient is calculated at the previous point $\mathbf{w}_{k-1}$, and the update is performed: $\mathbf{w}_k \leftarrow \mathbf{w}_{k-1} - \alpha \nabla g(\mathbf{w}_{k-1})$. The output includes the history of update steps and their corresponding function evaluations.

Matrix Differentiation Rules

Efficient computation of gradients in multi-dimensional space often employs matrix differentiation using the denominator layout convention. Key results include:

(i) If $\mathbf{y} = A\mathbf{x}$ is a linear transformation, then $\frac{\partial \mathbf{y}}{\partial \mathbf{x}} = A^T$.

(ii) For a scalar $a = \mathbf{y}^T A \mathbf{x}$, $\frac{\partial a}{\partial \mathbf{x}} = A^T \mathbf{y}$ and $\frac{\partial a}{\partial \mathbf{y}} = A \mathbf{x}$.

(iii) For a quadratic form $a = \mathbf{x}^T A \mathbf{x}$, $\frac{\partial a}{\partial \mathbf{x}} = (A + A^T)\mathbf{x}$. If $A$ is symmetric, this simplifies to $2A\mathbf{x}$.

(iv) If $a = \mathbf{y}^T \mathbf{x}$ where both are functions of a vector $\mathbf{z}$, then $\frac{\partial a}{\partial \mathbf{z}} = \frac{\partial \mathbf{y}}{\partial \mathbf{z}} \mathbf{x} + \frac{\partial \mathbf{x}}{\partial \mathbf{z}} \mathbf{y}$.

(v) For a scalar $a = \mathbf{x}^T \mathbf{x}$ where $\mathbf{x}$ is a function of vector $\mathbf{z}$, $\frac{\partial a}{\partial \mathbf{z}} = 2\frac{\partial \mathbf{x}}{\partial \mathbf{z}} \mathbf{x}$.

An example of a two-dimensional gradient descent involves minimizing $g(w_1, w_2) = w_1^2 + w_2^2 + 2$, which has a gradient $\nabla g(\mathbf{w}) = 2\mathbf{w}$. With an initial point such as $\mathbf{w}_0 = (3, 4)^T$ and $\alpha = 0.6$, the algorithm quickly settles to the global minimum.

Numerical Differentiation and Step Size Sensitivity

When analytic gradients are too complex to compute, numerical differentiation provides an approximation. While forward and backward difference quotients have significant approximation errors, the central difference quotient is preferred as errors tend to cancel. It is defined as: $f'(x) \approx \frac{f(x + h) - f(x - h)}{2h}$. In multivariate contexts, the $i$-th partial derivative is approximated using the $i$-th standard basis vector $\mathbf{e}_i$:

$\frac{\partial g}{\partial w_i}(\mathbf{w}) \approx \frac{g(\mathbf{w} + h \mathbf{e}_i) - g(\mathbf{w} - h \mathbf{e}_i)}{2h}$

A common choice for the small value $h$ is $h = \sqrt{\epsilon} \times ||\mathbf{w}||_2$, where $\epsilon$ is machine epsilon ($\text{.Machine\$double.eps}$ in R). Modern machine learning primarily uses automatic differentiation rather than numerical differentiation to avoid rounding and truncation errors.

Sensitivity to the step size $\alpha$ is critical. If $\alpha$ is too small, convergence is excessively slow because movement is minuscule. If $\alpha$ is too large, update steps may actually increase the function value, leading to divergence. Common strategies involve setting $\alpha$ as a fixed value like $10^{\gamma}$ (where $\gamma$ is a negative integer) or using a diminishing step size like $\alpha = \frac{1}{k}$.

Limitations of Gradient Descent

Gradient descent faces two major practical issues involving the direction and magnitude of the negative gradient. First, "zigzag" behavior occurs because the gradient is always perpendicular to function contours. In objective functions with narrow valleys, the directions oscillate rapidly, requiring many steps to reach the minimum. This is observable in quadratic functions of the form $g(\mathbf{w}) = \mathbf{w}^T C \mathbf{w}$, particularly when the matrix $C$ has disparate eigenvalues, creating narrow contours.

Second, "slow-crawling" behavior occurs near critical points. Since the gradient vanishes at stationary points ($||\nabla g(\mathbf{w}^*)||_2 = 0$), the magnitude of the update steps shrinks as the algorithm approaches the optimum. Because step length is calculated as $||\mathbf{w}_k - \mathbf{w}_{k-1}||_2 = \alpha ||\nabla g(\mathbf{w}_{k-1})||_2$, vanilla gradient descent makes very little progress in flat regions of the function surface.

Variants of Gradient Descent

To address standard gradient descent's weaknesses, several variants exist:

First-Order Coordinate Descent: This method simplifies high-dimensional problems into a series of one-dimensional problems. Instead of updating all coordinates at once, the algorithm cycles through each coordinate $i = 1, 2, \dots, n$, minimizing the function with respect to $w_i$ while holding other coordinates constant. The update is: $w_i^k \leftarrow w_i^{k-1*} - \alpha \frac{\partial g}{\partial w_i}(w_i^{k-1*})$, where $w_i^{k-1*}$ includes the most recent updates for all preceding dimensions.

Momentum-Based Gradient Descent: Borrows from the physical intuition of a ball rolling down a bowl. Momentum allows the update to carry forward previous descent directions, reducing oscillations. The descent direction is an exponentially weighted moving average (EWMA) of negative gradients: $\mathbf{d}_{k-1} = \beta \mathbf{d}_{k-2} + (1 - \beta)(-\nabla g(\mathbf{w}_{k-1}))$, where $\beta \in [0, 1]$ is a decay rate. The update is $\mathbf{w}_k \leftarrow \mathbf{w}_{k-1} + \alpha \mathbf{d}_{k-1}$.

Normalized Gradient Descent: Addresses the slow-crawling issue by normalizing the negative gradient, ensuring each step has a constant length $\alpha$. The update is: $\mathbf{w}_k \leftarrow \mathbf{w}_{k-1} - \alpha \frac{\nabla g(\mathbf{w}_{k-1})}{||\nabla g(\mathbf{w}_{k-1})||_2}$. In practice, a small constant $\epsilon$ (e.g., $10^{-7}$) is added to the denominator as $\mathbf{w}_k \leftarrow \mathbf{w}_{k-1} - \alpha \frac{\nabla g(\mathbf{w}_{k-1})}{||\nabla g(\mathbf{w}_{k-1})||_2 + \epsilon}$ to prevent division by zero and maintain numerical stability.

Specialized Variants in Machine Learning

Machine learning leverages numerous advanced extensions of gradient descent. Stochastic Gradient Descent (SGD) reduces redundant calculations by processing subsets of data rather than the full batch. Nesterov Accelerated Gradient (NAG) provides a refined version of momentum. AdaGrad (Adaptive Gradient Algorithm) adapts the learning rate for each parameter based on historical gradients. Adam (Adaptive Moment Estimation) combines momentum with adaptive learning rates, while RMSprop (Root Mean Squared Propagation) improves upon AdaGrad to prevent the learning rate from shrinking too quickly.