gd.py, which recomputes what the entry states: the script block by block · open in ColabDictionary of Applied Machine Learning: 114 machine-learning terms, each with a definition, a figure, citations and a Python demo · All terms · Demos · Start here
Updated on 2026-11-02
Readiness 100/100
See also gradient stochastic gradient descent convex
Gradient descent (GD) is an iterative algorithm for minimizing a differentiable function $f: \mathbb{R}^{d} \rightarrow \mathbb{R}$. Each iteration updates the current estimate by a step along the negative gradient, scaled by a step size $\eta$. Such a gradient step can be interpreted as the application of an operator that is parameterized by the step size and the underlying function. GD and its variants are widely used to train parametric models in deep learning.
gd.py, which recomputes what the entry states: the script block by block · open in ColabWhen training a deep net for image recognition, the average loss incurred by the network on a training set of labeled images is a function $f({\mathbf w})$ of the vector ${\mathbf w} \in \mathbb{R}^{d}$ of its model parameters, and training means minimizing that function. Many machine learning (ML) applications amount to such an optimization problem: an objective function $f: \mathbb{R}^{d} \rightarrow \mathbb{R}$ measures the quality of the model parameters ${\mathbf w}$, which are the optimization variable. Minimizing $f$ on the training set is a proxy: the goal is a small loss on data points outside it (see generalization).
In many cases, the objective function is differentiable: at every point ${\mathbf w}$ there exists a gradient $\nabla f({\mathbf w}) \in \mathbb{R}^{d}$, the vector of partial derivatives of $f$ at ${\mathbf w}$, which determines a local linear approximation of $f$ (see differentiable).
GD uses this local linear approximation to improve the current
choice of the model parameters iteratively. Starting from an
initialization ${\mathbf w}^{(0)}$, it generates a sequence of
estimates ${\mathbf w}^{(0)}, {\mathbf w}^{(1)}, {\mathbf w}^{(2)}, \ldots$ that
ideally converge to a minimum of $f$.
At each iteration $t$, GD refines the current estimate
${\mathbf w}^{(t)}$ by stepping in the direction of steepest
descent of the local linear approximation to $f$ at
${\mathbf w}^{(t)}$. This direction is the negative gradient
$\nabla f({\mathbf w}^{(t)})$, giving the update
\begin{equation}
\label{equ_def_GD_step_dict}
{\mathbf w}^{(t+1)} = {\mathbf w}^{(t)}
- \eta \nabla f({\mathbf w}^{(t)}) \text{,}
\end{equation}
where $\eta > 0$ is a step size; the update is a
gradient step with step size $\eta$.
For a sufficiently small $\eta$, each step decreases
the function value, $f({\mathbf w}^{(t+1)}) \le f({\mathbf w}^{(t)})$,
with strict decrease whenever
$\nabla f({\mathbf w}^{(t)}) \neq \mathbf{0}$
(Boyd and Vandenberghe, 2004, Sect. 9.3). GD and its variants are the
standard solvers for model training in
deep learning (Goodfellow et al., 2016).
Fig. 1 illustrates a single GD step.
Algorithm 1 states the method in full.
The convergence of the fixed-point iteration ${\mathbf w}^{(t+1)} = \mathcal{F}^{(\eta)}({\mathbf w}^{(t)})$ is governed by the properties of the GD step operator $\mathcal{F}^{(\eta)}$. Assume $f$ is convex and its gradient is $L$-Lipschitz continuous, i.e., \[\Vert {\nabla f({\mathbf w}) - \nabla f({\mathbf w}')} \Vert \le L\,\Vert {{\mathbf w} - {\mathbf w}'} \Vert \quad \text{for all } {\mathbf w}, {\mathbf w}' \in \mathbb{R}^{d} \text{.}\] For $0 < \eta \le 1/L$, the operator $\mathcal{F}^{(\eta)}$ is then a non-expansive operator with respect to the Euclidean norm $\Vert {\cdot} \Vert$: it does not increase distances between any two points ${\mathbf w}, {\mathbf w}'$, \[\Vert {\mathcal{F}^{(\eta)}({\mathbf w}) - \mathcal{F}^{(\eta)}({\mathbf w}')} \Vert \le \Vert {{\mathbf w} - {\mathbf w}'} \Vert \text{.}\] Non-expansiveness alone does not guarantee a unique fixed point (Bauschke and Combettes, 2011, Ch. 4).
P-descentAssume, moreover, that $f$ is $\mu$-strongly convex, i.e., the function $f({\mathbf w}) - (\mu/2) \Vert {{\mathbf w}} \Vert^{2}$ is still convex, so the curvature of $f$ is at least $\mu > 0$ in every direction. Then $\mathcal{F}^{(\eta)}$ is a contractive operator with respect to the same norm, \[ \Vert {\mathcal{F}^{(\eta)}({\mathbf w}) - \mathcal{F}^{(\eta)}({\mathbf w}')} \Vert \le (1 - \mu\eta)\,\Vert {{\mathbf w} - {\mathbf w}'} \Vert \text{.} \] In this case, Banach's fixed-point theorem gives a unique fixed point $\widehat{{\mathbf w}}$ (the minimizer of $f$) to which GD converges at a geometric rate (Boyd and Vandenberghe, 2004, Sect. 9.3; Bubeck, 2015, Thm. 3.10). For linear regression, these properties are explicit: the gradient of the average squared error loss is an affine function of ${\mathbf w}$, and the contraction factor of $\mathcal{F}^{(\eta)}$ is governed by the eigenvalues of the matrix ${\mathbf X}^{\top}{\mathbf X}$. Here, ${\mathbf X}$ denotes the feature matrix, whose rows are the feature vectors of the data points in the training set (see linear regression).
P-rateHow fast GD converges depends on the curvature of $f$, as quantified by the constants $L$ and $\mu$ above. Let $\widehat{{\mathbf w}}$ be a minimizer and $f^{\star} = f(\widehat{{\mathbf w}})$. For convex $f$ with $L$-Lipschitz gradient and the constant step size $\eta = 1/L$ (Beck, 2017, Ch. 10; Bubeck, 2015, Thm. 3.3), \[ f\big({\mathbf w}^{(T)}\big) - f^{\star} \le \frac{L\,\Vert {{\mathbf w}^{(0)} - \widehat{{\mathbf w}}} \Vert^{2}}{2\,T} \text{,} \] so the suboptimality after $T$ steps falls in proportion to $1/T$: halving the suboptimality requires doubling the number of iterations. If $f$ is in addition $\mu$-strongly convex, the bound improves to the geometric rate \[ f\big({\mathbf w}^{(T)}\big) - f^{\star} \le \left(1 - \tfrac{\mu}{L}\right)^{T} \big(f({\mathbf w}^{(0)}) - f^{\star}\big) \text{,} \] consistent with the contractive operator factor $1 - \mu\eta$ above (Boyd and Vandenberghe, 2004, Sect. 9.3; Bubeck, 2015, Thm. 3.10). A geometric rate means that the suboptimality shrinks by at least the constant factor $1 - \mu/L$ in every single iteration. Thus, halving the suboptimality now costs a fixed number of iterations, however small the current suboptimality already is. Momentum methods, discussed below, improve both bounds.
The iteration also has a continuous-time counterpart. Consider
shrinking the step size $\eta$ in the GD step
\(\eqref{equ_def_GD_step_dict}\) toward zero. For $\eta \to 0$, the
iterate ${\mathbf w}^{(t)}$ converges to ${\mathbf w}(t \eta)$,
the value at time $t \eta$ of the continuous-time trajectory
${\mathbf w}(\tau)$ that satisfies the ordinary differential equation
$\dot{{\mathbf w}}(\tau) = -\nabla f({\mathbf w}(\tau))$, known as
gradient flow.
In particular, GD is the explicit Euler discretization of this
gradient flow with step $\eta$ (Helmke and Moore, 1994).
Replacing the time derivative $\dot{{\mathbf w}}(\tau)$
by the difference quotient
$\big({\mathbf w}^{(t+1)} - {\mathbf w}^{(t)}\big)/\eta$
recovers the update \(\eqref{equ_def_GD_step_dict}\).
Fig. 2 illustrates how, for a
small step size, the GD iterates closely follow the
gradient flow trajectory.
pythondemos/gd.py
P-momentumMomentum methods provide another generalization of plain GD:
each update combines gradients from several past steps
rather than the current one alone. The name stems from a physical
analogy: the iterates trace a particle whose momentum accumulates
the force exerted by the negative gradient of the
objective function. One prototypical example of a momentum method is Polyak's
heavy-ball method. It adds a fraction
$\beta \in [0, 1)$ of the previous increment,
\[
{\mathbf w}^{(t+1)} = {\mathbf w}^{(t)}
- \eta \nabla f({\mathbf w}^{(t)})
+ \beta\big({\mathbf w}^{(t)} - {\mathbf w}^{(t-1)}\big)
\text{, for } t=1,\ldots.
\]
For a strongly convex quadratic $f$, this iteration converges faster than plain GD
(Polyak, 1987). Fig. 3 compares plain GD with the
heavy-ball method on a strongly convex quadratic function.
pythondemos/gd.py
See also: gradient, step size, stochastic gradient descent, subgradient descent, subgradient, gradient flow, convex, strongly convex, fixed point.
@misc{dictml_gd,
author = {Jung, Alexander},
editor = {Olioumtsevits, Konstantina and Schnoor, Ekkehard},
title = {gradient descent (GD)},
howpublished = {Dictionary of Applied Machine Learning (course edition)},
year = {2026},
doi = {10.5281/zenodo.21569296},
note = {ISBN 978-952-64-3013-3, CC BY 4.0, retrieved 2026-11-04},
url = {https://dictionaryofml.org/terms/gd.html}
}