Gradient descent is a first-order iterative optimization algorithm used to minimize a differentiable function by repeatedly moving in the direction of the negative gradient of the function at the current point. It is a fundamental tool in applied mathematics, machine learning, and scientific computing, employed for training models, solving inverse problems, and unconstrained optimization. The algorithm's simplicity and scalability make it particularly suitable for high-dimensional problems, though its performance depends on the choice of learning rate and the nature of the objective function.
1 Basic concept
1.1 Intuitive explanation
Imagine standing on a hillside in dense fog, wanting to descend to the valley floor. Because you can only feel the slope beneath your feet, you take a step in the steepest downhill direction. By repeating this process—feeling the local slope and stepping opposite to it—you gradually move toward the bottom. Gradient descent applies this same principle to mathematical functions: at each point, the gradient (a vector of partial derivatives) points uphill, so moving in the negative gradient direction reduces the function value.
1.2 Mathematical formulation
1.2.1 Update rule
Let \(f:\mathbb{R}^n \to \mathbb{R}\) be a differentiable function. Starting from an initial point \(\mathbf{x}_0\), gradient descent iteratively updates: \[ \mathbf{x}_{k+1} = \mathbf{x}_k - \eta \nabla f(\mathbf{x}_k), \] where \(\eta > 0\) is the learning rate (step size) and \(\nabla f(\mathbf{x}_k)\) is the gradient of \(f\) at \(\mathbf{x}_k\). The process continues until a stopping criterion is met, such as a sufficiently small gradient magnitude or a maximum number of iterations.
1.2.2 Role of the learning rate
The learning rate controls the size of each step. A very small \(\eta\) leads to slow progress; a very large \(\eta\) can cause overshooting or divergence. Choosing an appropriate learning rate is critical—too small and convergence takes too long, too large and the algorithm may oscillate or fail to converge.
1.3 Geometric interpretation
1.3.1 Steepest descent direction
At a point \(\mathbf{x}\), the negative gradient \(-\nabla f(\mathbf{x})\) is the direction of steepest descent: among all unit directions, it gives the greatest instantaneous decrease in \(f\). Thus each step of gradient descent moves directly downhill in the local linear approximation of the function.
1.3.2 Convergence to local minima
For convex functions, any local minimum is global, and gradient descent converges to that global minimum. For non-convex functions, gradient descent may converge to a local minimum or a saddle point, depending on the starting point and the shape of the function. The algorithm cannot guarantee finding the global minimum in general.
2 Variants
2.1 Batch gradient descent
2.1.1 Full dataset computation
In the context of machine learning, batch gradient descent computes the gradient using the entire training dataset. For a loss function \(L(\mathbf{w}) = \frac{1}{N}\sum_{i=1}^N \ell(\mathbf{x}_i, y_i; \mathbf{w})\), the gradient is \(\nabla L(\mathbf{w}) = \frac{1}{N}\sum_{i=1}^N \nabla \ell(\mathbf{x}_i, y_i; \mathbf{w})\). This yields a deterministic update.
2.1.2 Advantages and limitations
Batch gradient descent produces accurate gradient estimates and can be parallelized efficiently. However, for large datasets, computing the full gradient at each iteration is computationally expensive and may be impractical. It also tends to converge slowly on ill-conditioned problems.
2.2 Stochastic gradient descent (SGD)
2.2.1 Single-sample update
SGD uses a single randomly selected training example to compute the gradient at each iteration: \(\mathbf{w}_{k+1} = \mathbf{w}_k - \eta \nabla \ell(\mathbf{x}_i, y_i; \mathbf{w}_k)\). This introduces noise into the updates, which can help escape shallow local minima.
2.2.2 Stochastic approximation theory
SGD is rooted in stochastic approximation theory, notably the Robbins–Monro algorithm. Under appropriate conditions on the learning rate (e.g., \(\sum \eta_k = \infty\) and \(\sum \eta_k^2 < \infty\)), SGD converges almost surely to a local minimum.
2.3 Mini-batch gradient descent
2.3.1 Trade-off between batch and stochastic
Mini-batch gradient descent computes the gradient over a small subset (mini-batch) of the data, typically of size between 16 and 512. It balances the accuracy of batch methods with the speed of stochastic methods, and its noise can improve generalization.
2.3.2 Common mini-batch sizes
Common mini-batch sizes are powers of two (32, 64, 128, 256) for computational efficiency on modern hardware. The optimal size depends on the dataset and model architecture.
2.4 Momentum methods
2.4.1 Classical momentum
Momentum accelerates gradient descent by accumulating a velocity vector. The update is: \[ \mathbf{v}_{k+1} = \mu \mathbf{v}_k - \eta \nabla f(\mathbf{x}_k), \quad \mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{v}_{k+1}, \] where \(\mu \in [0,1)\) is the momentum coefficient. This helps dampen oscillations and speeds up convergence in directions of consistent gradient.
2.4.2 Nesterov accelerated gradient (NAG)
NAG is a variant that computes the gradient at a lookahead position: \(\mathbf{x}_k + \mu \mathbf{v}_k\). The update is: \[ \mathbf{v}_{k+1} = \mu \mathbf{v}_k - \eta \nabla f(\mathbf{x}_k + \mu \mathbf{v}_k), \quad \mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{v}_{k+1}. \] NAG often yields faster convergence than classical momentum, especially for convex functions.
2.5 Adaptive methods
2.5.1 AdaGrad
AdaGrad adapts the learning rate per parameter based on the historical sum of squared gradients. Parameters that receive large gradients get smaller learning rates, making it suitable for sparse data. However, the learning rate shrinks monotonically and can become too small.
2.5.2 RMSProp
RMSProp modifies AdaGrad by using an exponentially decaying average of past squared gradients: \[ E[g^2]_k = \beta E[g^2]_{k-1} + (1-\beta) g_k^2, \quad \mathbf{x}_{k+1} = \mathbf{x}_k - \frac{\eta}{\sqrt{E[g^2]_k + \epsilon}} g_k. \] It prevents the learning rate from diminishing too rapidly and works well for non-stationary objectives.
2.5.3 Adam (Adaptive Moment Estimation)
Adam combines momentum and RMSProp. It maintains both a first-moment estimate (mean of gradients) and a second-moment estimate (uncentered variance).
2.5.3.1 Bias correction
Because both moment estimates are initialized at zero, Adam applies bias correction: \[ \hat{m}_k = \frac{m_k}{1-\beta_1^k}, \quad \hat{v}_k = \frac{v_k}{1-\beta_2^k}. \]
2.5.3.2 Hyperparameters
Common hyperparameters are \(\beta_1 = 0.9\), \(\beta_2 = 0.999\), and \(\epsilon = 10^{-8}\). The learning rate \(\eta\) typically defaults to 0.001. Adam is widely used in deep learning due to its robustness.
3 Convergence analysis
3.1 Convex objectives
3.1.1 Lipschitz smoothness
| A function \(f\) is \(L\)-smooth if its gradient is Lipschitz continuous: \(\|\nabla f(\mathbf{x}) - \nabla f(\mathbf{y})\| \le L \|\mathbf{x}-\mathbf{y}\|\). Under this condition, gradient descent with \(\eta \le 1/L\) guarantees a decrease in function value and convergence to the optimum. |
|---|
3.1.2 Strong convexity
| If \(f\) is \(\mu\)-strongly convex, meaning \(f(\mathbf{y}) \ge f(\mathbf{x}) + \nabla f(\mathbf{x})^T(\mathbf{y}-\mathbf{x}) + \frac{\mu}{2}\|\mathbf{y}-\mathbf{x}\|^2\), then gradient descent converges linearly with rate \(1 - \mu/L\). |
|---|
3.2 Non-convex objectives
3.2.1 Saddle points and plateaus
In non-convex landscapes, gradient descent can get stuck near saddle points where the gradient is zero but the function is not locally convex. The algorithm may slow down dramatically on plateaus.
3.2.2 Escape behavior
Adding noise (as in SGD) or using momentum can help escape saddle points. Theoretically, under certain assumptions, gradient descent with random perturbations avoids strict saddle points almost surely.
3.3 Rate of convergence
3.3.1 Linear convergence
For strongly convex and smooth functions, gradient descent exhibits linear convergence: the distance to the optimum decreases by a constant factor each iteration. The rate depends on the condition number \(\kappa = L/\mu\).
3.3.2 Sublinear convergence
For convex but not strongly convex functions, gradient descent achieves sublinear convergence, typically \(O(1/k)\). For non-convex objectives, convergence to a stationary point is often \(O(1/\sqrt{k})\) in terms of gradient norm.
4 Practical considerations
4.1 Learning rate scheduling
4.1.1 Step decay
The learning rate is reduced by a factor (e.g., 0.1) at fixed intervals or when validation performance plateaus. This allows large initial steps and fine-tuning later.
4.1.2 Exponential decay
The learning rate decreases exponentially: \(\eta_k = \eta_0 \cdot \gamma^k\) with \(0<\gamma<1\). It is simple to implement but can shrink too quickly.
4.1.3 Cosine annealing
The learning rate follows a cosine curve, oscillating between a high and low value. Used in recent deep learning schedules, it can help escape local minima.
4.2 Initialization strategies
Proper initialization of parameters (e.g., Xavier or He initialization for neural networks) prevents gradients from vanishing or exploding. Poor initialization can lead to slow convergence or failure.
4.3 Gradient clipping
4.3.1 Norm clipping
| If the gradient norm exceeds a threshold \(\tau\), it is scaled down: \(g \leftarrow \frac{\tau}{\|g\|} g\). This prevents extremely large updates in deep networks. |
|---|
4.3.2 Value clipping
Individual gradient components are clipped to a range \([-\delta, \delta]\). Less common than norm clipping but useful in some recurrent architectures.
4.4 Early stopping
Training is halted when performance on a validation set stops improving. Early stopping acts as a regularizer and prevents overfitting.
4.5 Regularization and gradient descent
4.5.1 L2 regularization (weight decay)
| L2 regularization adds a penalty \(\frac{\lambda}{2}\|\mathbf{w}\|^2\) to the loss, resulting in an additional \(-\eta \lambda \mathbf{w}\) term in the update. This encourages small weights and is equivalent to weight decay. |
|---|
4.5.2 L1 regularization and proximal gradient
L1 regularization promotes sparsity. The gradient descent update for L1 involves a soft-thresholding operator. Proximal gradient methods handle non-smooth regularizers by alternating a gradient step and a proximal operator.
5 Extensions and related algorithms
5.1 Coordinate descent
Coordinate descent updates one parameter (or coordinate) at a time, using the partial derivative along that coordinate. It can be efficient when the function is separable or when coordinates interact weakly.
5.2 Natural gradient descent
Natural gradient descent uses the Fisher information matrix to adjust the update direction, accounting for the geometry of the parameter space. It is invariant to reparameterization and used in variational inference.
5.3 Conjugate gradient method
Conjugate gradient is a first-order method that constructs search directions conjugate to previous ones, achieving faster convergence for quadratic functions without storing a Hessian.
5.4 Quasi-Newton methods (e.g., L-BFGS)
Quasi-Newton methods approximate the Hessian inverse using gradient differences. L-BFGS (Limited-memory BFGS) is a popular variant for large-scale problems, offering superlinear convergence.
5.5 Adaptive subgradient methods
These extend gradient descent to non-differentiable objective functions by using subgradients. AdaGrad is one example; others include subgradient methods with decreasing step sizes.
6 Applications
6.1 Machine learning and deep learning
6.1.1 Training neural networks
Gradient descent and its variants (SGD, Adam) are the standard algorithms for training deep neural networks by minimizing loss functions like cross-entropy. Backpropagation computes the gradients efficiently.
6.1.2 Linear regression and logistic regression
For linear regression, gradient descent converges to the ordinary least squares solution. For logistic regression, it finds the maximum likelihood estimates of the parameters.
6.2 Inverse problems and signal processing
6.2.1 Image reconstruction
Gradient descent is used in computed tomography, magnetic resonance imaging, and deblurring by minimizing data-fidelity terms coupled with regularizers.
6.2.2 Sparse coding
L1-regularized problems (e.g., LASSO) are solved via proximal gradient descent to obtain sparse representations of signals.
6.3 Control theory and robotics
6.3.1 Parameter tuning
Controllers (e.g., PID controllers) often have parameters tuned by minimizing a cost function using gradient descent on simulated or real system data.
6.3.2 Reinforcement learning
Policy gradient methods in reinforcement learning use gradient ascent (the reverse of descent) on expected reward. Natural gradient and trust-region methods are related.
7 Historical development
7.1 Early contributions (Cauchy, 1847)
The method of steepest descent was first described by Augustin-Louis Cauchy in 1847. He proposed using the gradient to solve systems of linear equations by minimizing a quadratic form.
7.2 Modern resurgence in machine learning
Gradient descent gained prominence in the 1980s with the backpropagation algorithm for neural networks. The availability of large datasets and computational power in the 2000s led to widespread adoption of stochastic variants.
7.3 Key theoretical advances
Robbins and Monro (1951) laid the foundation for stochastic approximation. In the 1990s and 2000s, convergence rates for convex optimization were refined by Nesterov and others. The development of adaptive methods (AdaGrad, Adam) in the 2010s improved practical robustness.