Following the Steepest Direction
In which we explore the basics of gradient descent.
· · AI 2/4 (assisted) · #optimization · PDF · Org · earlier versions 2025–2026
1 Following the steepest direction
Suppose that you want to solve the problem
\[\umin{x \in [-1,1]^{d}} f(x) ,\]and you want to achieve a \(\epsilon\)-precision on the objective function \(f\), i.e., you want to obtain an estimate \(\hat x \in [-1,1]^d\) such that \(f(\hat x)-f(x^{\star}) \leq \epsilon\), where \(x^{\star}\) is a minimizer of \(f\) over \([-1,1]^d\). Since \(f\) is continuous, you cannot have access to all values \(f(x)\) when \(x\) describes the constraints \([-1,1]^{d}\), but you can allow yourself multiples calls to the “oracle” \(f(x)\) in order to achieve this precision. A naive way to do so is to consider a discretization of \([-1,1]\) of precision \(\epsilon\), that is
\[G_{\epsilon} = \setcond{k \epsilon}{k \in \set{-\lfloor \epsilon^{-1} \rfloor, \dots, \lfloor \epsilon^{-1} \rfloor}} ,\]and \(G_{\epsilon}^{d} = G_{\epsilon} \times \dots \times G_{\epsilon}\) its counterpart in dimension \(d\).
Black-box discretization
Proposition 1: Grid-search guarantee
Let \(0<\epsilon\leq 1\) and let \(f:[-1,1]^d\to\RR\) be \(L\)-Lipschitz, where \(L>0\). Let \(x^\star\) be any minimizer of \(f\) on \([-1,1]^d\), and let \(\hat x\) be any minimizer of \(f\) over the finite grid \(G_\epsilon^d\). Then
\[0\leq f(\hat x)-f(x^\star)\leq L\sqrt{d}\,\epsilon.\]Thus, for a prescribed objective-value tolerance \(\delta>0\), choosing \(\epsilon\leq\min\{1,\delta/(L\sqrt{d})\}\) guarantees \(f(\hat x)-f(x^\star)\leq\delta\).
Proof
Lipschitz continuity implies continuity, so a minimizer \(x^\star\) exists on the compact cube; a grid minimizer exists because the grid is finite and nonempty. For each coordinate, define
\[z_i=\epsilon\,\operatorname{sign}(x_i^\star) \left\lfloor\frac{|x_i^\star|}{\epsilon}\right\rfloor, \qquad i=1,\dots,d,\]with \(\operatorname{sign}(0)=0\). Since \(|x_i^\star|\leq 1\), we have \(z\in G_\epsilon^d\) and \(|z_i-x_i^\star|<\epsilon\) for every \(i\). Consequently, \(\norm{z-x^\star}\leq\sqrt{d}\,\epsilon\). By global optimality of \(x^\star\), grid optimality of \(\hat x\), and Lipschitz continuity,
\[0\leq f(\hat x)-f(x^\star) \leq f(z)-f(x^\star) \leq L\norm{z-x^\star} \leq L\sqrt{d}\,\epsilon.\]This is a bound on objective values, rather than on \(\norm{\hat x-x^\star}\). Lipschitz continuity alone cannot guarantee proximity to a chosen minimizer: for \(f\equiv 0\), every grid point is a minimizer, including points far from \(x^\star=0\).
The issue is that the size of \(G_{\epsilon}^{d}\) grows exponentially fast with the dimension \(d\). In dimension 1, one needs to perform \(2 \lfloor \epsilon^{-1} \rfloor+1\) evaluations of \(f\), but in dimension \(d\), one needs \((2 \lfloor \epsilon^{-1} \rfloor+1)^d\)! This quantity gets prohibilitively large in a too fast manner: say you look at a very modest precision of \(\epsilon = 10^{-2}\), then in dimension \(d=1\), 201 computations of \(f\) are needed, whereas in dimension \(d=10\), you already need \(201^{10}=107636749520976961802001\) evaluations (about \(1.08\times 10^{23}\)).
This is known as the curse of dimensionality, a term introduced by Bellman (1961, Chapter 5) for optimal control and (over)used since then in the optimization, statistics and machine learning communities (Donoho, 2000). Summary: we need to be (slightly) more clever.
1.1 Descent direction
Consider the class of algorithms of the form
\[x^{(t+1)} = x^{(t)} + \eta^{(t)} u^{(t+1)} ,\]how to “optimaly choose” the direction \(u^{(t+1)}\) such that \(x^{(t+1)}\) is closer to a minimum of \(f\)?
Definition 2
Let \(f: \RR^{d} \to \RR\). A descent direction \(u \in \RR^{d}\) of \(f\) at \(x \in \RR^{d}\) is vector such that
\[\exists \epsilon > 0, \forall \eta \in (0, \epsilon), \quad f(x + \eta u) < f(x) .\]Nonsmooth descent cone
Rotate the direction u. Dashed boundary directions are excluded from the strict descent cone.
Observe that if \(f\) is differentiable, \(\dotp{\nabla f(x)}{u} < 0\) implies this property, but the converse need not hold.
For example, \(f(z)=-z^2\) at \(x=0\) has the descent direction \(u=1\), but \(f'(0)u=0\).
The negative gradient \(-\nabla f(\bar x)\) is the direction of steepest descent at the point \(\bar x\) when \(\nabla f(\bar x)\neq 0\).
Proposition 3: The antigradient is the steepest direction
Let \(f: \RR^{d} \to \RR\) be a differentiable function at \(\bar x \in \RR^{d}\). Assume that \(\nabla f(\bar x)\neq 0\). Then, the problem
\[\min_{\norm{u} = 1} \dotp{\nabla f(\bar x)}{u}\]has a unique solution \(u^{\star} = - \frac{\nabla f(\bar x)}{\norm{\nabla f(\bar x)}}\) .
Proof
Let \(u \in \RR^{d}\) such that \(\norm{u} = 1\). Consider the function \(\phi_{u}: \RR \to \RR\) defined by
\[\phi_{u}(t) = f(\bar x + t u).\]The function \(\phi_u\) is differentiable at \(0\) and its derivative reads \(\phi_{u}'(0) = \dotp{\nabla f(\bar x)}{u}\). Denoting \(\theta\) the angle between \(\nabla f(\bar x)\) and \(u\), we have that \(\phi_{u}'(0) = \norm{\nabla f(\bar x)} \cos \theta\). Hence, minimizing \(\dotp{\nabla f(\bar x)}{u}\) is equivalent to finding the minimum of \(\cos \theta\), that is \(\theta = (2k+1) \pi\) for some \(k \in \ZZ\). Thus, we have
\[u^{\star} = - \frac{\nabla f(\bar x)}{\norm{\nabla f(\bar x)}} \quad \text{ and } \quad \dotp{\nabla f(\bar x)}{u^\star} = - \norm{\nabla f(\bar x)}.\]1.2 The gradient descent (GD) algorithm
Proposition 3 gives birth to what is known as the gradient descent algorithm or gradient descent method.
- Input: Initialization \(x^{(0)} \in \RR^{d}\), step-size policy \(\eta^{(t)} > 0\).
- for \(t=0, \cdots\) do
\[
\begin{equation} \tag{GD} x^{(t+1)} = x^{(t)} - \eta^{(t)} \nabla f(x^{(t)}) . \end{equation}\]
The choice of the step-sizes \(\eta^{(k)}\) is crucial, and there is several way to do it.
- Predetermined. In this case, the sequence \((\eta^{(t)})\) is chosen beforehand, either with a constant step size \(\eta^{(t)} = \eta \in \RR_{>0}\) or with a given function of \(t\), \(\eta^{(t)} = g(t)\), e.g., \(g(t) = \eta (t+1)^{-1/2}\) for some \(\eta > 0\). For some classes of optimization problem, it is possible to provide guarantees depending on the choice of \(g\).
Oracle. This is the “optimal” descent that a gradient descent method can produce, defined by
\[ \eta_{\text{oracle}}^{(t)} \in \uargmin{\eta \geq 0} f(x^{(t)} - \eta \nabla f(x^{(t)})) . \]Remark that this choice is only theoretical since it involves a new optimization problem that may be nonsolvable in closed form.
This choice assumes that the line-search minimum is attained; this need not hold for a general \(f\).
Backtracking rule. Start with a trial step-size and check whether the proposed gradient step decreases the objective sufficiently. If it does not, shrink the step-size by a fixed factor, for example divide it by two, and try again. Repeat until the test passes, then take the step. A common test is the Armijo condition
\[ f(x^{(t)}-\eta\nabla f(x^{(t)})) \leq f(x^{(t)})-c\eta\norm{\nabla f(x^{(t)})}^{2}, \qquad 0<c<1. \]This adapts the step-size to the local behavior of the function without requiring its smoothness constant in advance.
1.3 Explicit analysis of the gradient descent: ordinary least-squares
All norms in the following gradient descent analysis are Euclidean.
Let \(n, p \geq 1\), \(A \in \mathbb{R}^{n \times p}\) and \(y \in \mathbb{R}^{n}\). The least-square estimator is defined by the problem
The objective \(f\) is twice differentiable, its gradient reads
\[\nabla f(x) = \frac{1}{n}A^{\top}(Ax - y) \in \mathbb{R}^{p} ,\]and its Hessian is constant on the whole space:
\[\nabla^{2} f(x) = H = \frac{1}{n} A^{\top} A \in \mathbb{R}^{p \times p} .\]Note that there is at least one minimizer to the problem (1). The first-order condition for a potential minimizer \(x^{\star}\) is given by
\[H x^{\star} = \frac{1}{n} A^{\top} y .\]A necessary, and sufficient condition, to have exactly one minimizer is that \(H\) is invertible.
The following lemma shows that, providing the knowledge of \(H\), the \(t\)-iterates of the gradient descent with fixed step-size is computable in closed-form.
Lemma 4: Closed-form expression of the gradient descent step
For all \(t \in \NN\), we have
Proof
Using the expression of the gradient and (GD), we have for any minimizer \(x^{\star}\)
\begin{align*} x^{(t+1)} &= x^{(t)} - \frac{\eta}{n} A^{\top}(A x^{(t)} - y) \\ &= x^{(t)} - \eta H (x^{(t)} - x^{\star}) . \end{align*}Substracting \(x^{\star}\) from both side gives
\[x^{(t+1)} - x^{\star} = (I - \eta H)(x^{(t)} - x^{\star}) .\]This identity is linear recursion, and unrolling it leads to the result.
Convergence in norm
We denote by \(\mu\) the smallest eigenvalue of \(H\), \(L\) its largest. If \(L=0\), then \(A=0\), \(f\) is constant and the GD iterates are stationary. In what follows, assume \(L>0\), and let \(\kappa=L/\mu\) when \(\mu>0\), and \(\kappa=+\infty\) when \(\mu=0\). We have \(0 \leq \mu \leq L\) and \(\kappa \geq 1\).
Small condition number
Large condition number
Both plots use the same initial point and minimizer, with μ = 1 and η = 2/(μ + L).
Using (2), we have
\[\| x^{(t)} - x^{\star} \|^{2} = \langle x^{(0)} - x^{\star} , (I - \eta H)^{2t} (x^{(0)} - x^{\star}) \rangle .\]Remark that the eigenvalues of \((I - \eta H)^{2t}\) are exactly given by \((1-\eta \lambda)^{2t}\) where \(\lambda\) is an eigenvalue of \(H\). Since all eigenvalues of \(H\) are contained in \([\mu,L]\), one also can bound any \(\rho \in \mathrm{eigen}((I - \eta H)^{2t})\) by
\[|\rho| \leq \left( \max_{\lambda \in [\mu,L]} | 1 - \eta \lambda | \right)^{2t} .\]Suppose that there is multiple minimizers. In this case, \(H\) is not invertible and the smallest eigenvalue \(\mu\) is equal to 0. Hence, there exists \(v\neq 0\) such that \((I - \eta H)v = v\). Choose \(x^{\star}\) a minimizer. Using \(x^{(0)} = v + x^{\star}\), we have
\[\| x^{(t)} - x^{\star} \|^{2} = \langle v + x^{\star} - x^{\star} , (I - \eta H)^{2t} (v + x^{\star} - x^{\star}) \rangle = \langle v , (I - \eta H)^{2t} v \rangle = \| v \|_{2}^{2} .\]Hence, the method does not necessarly converge to this chosen \(x^\star\): here \(x^{(t)}=x^{(0)}\) is already a minimizer. For \(0<\eta<2/L\), the iterates do converge to a minimizer, depending on the initialization.
The situation is different when we assume that there is a unique minimizer.
Proposition 5: Convergence in norm
Assume that (1) has a unique minimizer \(x^{\star}\). Then, the gradient descent iterates \(x^{(t)}\) with constant step-size \(\eta^{(t)} = \eta = \frac{2}{\mu + L}\) converges linearly in norm
\[\norm{x^{(t)} - x^{\star}}^{2} \leq \left( \frac{\kappa - 1}{\kappa + 1} \right)^{2t} \norm{x^{(0)} - x^{\star}}^{2} .\]Proof
Since there is a unique minimizer \(x^{\star}\), we have \(\mu > 0\). Observe that (using a spectral norm bound)
\[\langle x^{(0)} - x^{\star} , (I - \eta H)^{2t} (x^{(0)} - x^{\star}) \rangle \leq \left( \max_{\lambda \in [\mu,L]} | 1 - \eta \lambda | \right)^{2t} \| x^{(0)} - x^{\star} \|_{2}^{2} .\]Observe that \(\max_{\lambda \in [\mu,L]} | 1 - \eta \lambda |\) is minimized for \(\eta = \frac{2}{\mu + L}\), and value is \(\frac{\kappa - 1}{\kappa + 1} \in [0,1)\). Indeed,
\[\max_{\lambda \in [\mu,L]} | 1 - \eta \lambda | = \max \left( | 1 - \eta \mu |, | 1 - \eta L | \right) .\]If \(\mu=L\), this maximum is \(|1-\eta L|\), minimized at \(\eta=1/L\). For the following equivalences, assume \(\mu<L\).
Optimal constant step size
Hence,
\[\min_{\eta > 0} \max_{\lambda \in [\mu,L]} | 1 - \eta \lambda | = \min_{\eta > 0} \max \left( | 1 - \eta \mu |, | 1 - \eta L | \right) .\]Moreover, we have the following set of equivalence
\begin{align*} | 1 - \eta L | &\leq | 1 - \eta \mu | \\ (1 - \eta L)^{2} &\leq (1 - \eta \mu)^{2} \\ \eta L^{2} - 2L &\leq \eta \mu^{2} - 2 \mu \\ \eta &\leq \frac{2}{L + \mu} . \end{align*}This minima is achieved when the two curve \(| 1 - \eta L |\) and \(| 1 - \eta \mu |\) intersect.
Choice independant from the strong-convexity constant \(\mu\): It is possible to chose a smaller or equal stepsize (hence no faster) by taking the value \(\eta = 1/L\). In this case, we get
\[\max_{\lambda \in [\mu,L]} | 1 - \eta \lambda | = 1 - \frac{\mu}{L} = 1 - \frac{1}{\kappa} .\]In both cases, we obtained a linear (or geometric, or exponential depending on the community) rate
\[\| x^{(t)} - x^{\star} \|^{2} \leq c^{2t} \| x^{(0)} - x^{\star} \|^{2} ,\]where \(c = \frac{\kappa - 1}{\kappa + 1}\) or \(c = 1 - \frac{1}{\kappa}\) depending on the choice of the step-size.
It is possible to also speaks in term of iteration complexity. Assuming the choice of \(\eta = 1/L\), observe that
\[\left( 1 - \frac{1}{\kappa} \right)^{2t} \leq \exp(-\frac{1}{\kappa})^{2t} = \exp(-\frac{2t}{\kappa}) .\]Thus, to obtain a fraction \(\epsilon \| x^{(0)} - x^{\star} \|^{2}\) for \(0<\epsilon<1\), it is sufficient to perform \(t\) iterations with
\[t \geq \left\lceil \frac{\kappa}{2} \log \frac{1}{\epsilon} \right\rceil .\]Convergence in value
As we say, if \(\mu = 0\), the iterates need not converge to a chosen minimizer, although they converge to a minimizer for \(0<\eta<2/L\). But the story is different for the convergence in value.
Proposition 6: Convergence in value
Let \(x^{\star}\) any solution of (1), assume \(L>0\), and let \(t\geq 1\). The gradient descent iterates \(x^{(t)}\) with constant step-size \(\eta^{(t)} = \eta = \frac{1}{L}\) converges with a \(O(1/t)\) rate
\[f(x^{(t)}) - f(x^{\star}) \leq \frac{1}{4t\eta} \norm{x^{(0)} - x^{\star}}_{2}^{2} .\]If moreover, (1) has a unique solution, the convergence is linear:
\[f(x^{(t)}) - f(x^\star) \leq \left( 1 - \frac{1}{\kappa} \right)^{2t} (f(x^{(0)}) - f(x^\star)) .\]Proof
Observe that \(f\) has an exact Taylor expansion of order 2. Indeed, for any \(x \in \mathbb{R}^{p}\) and any minimizer \(x^{\star}\):
Using the (exact) Taylor expansion (3) of \(f\), we have
\[f(x^{(t)}) - f(x^\star) = \frac{1}{2} \langle x^{(t)} - x^\star, H (x^{(t)} - x^{\star}) \rangle .\]Using (2), we have
\[f(x^{(t)}) - f(x^\star) = \frac{1}{2} \langle (I - \eta H)^{t} (x^{(0)} - x^{\star}) , H (I - \eta H)^{t} (x^{(0)} - x^{\star}) \rangle .\]Since \((I - \eta H)\) is symmetric, we have
\[f(x^{(t)}) - f(x^\star) = \frac{1}{2} \langle x^{(0)} - x^{\star} , (I - \eta H)^{2t} H (x^{(0)} - x^{\star}) \rangle .\]Using the fact that for a symmetric positive semidefinite matrix \(B\), we have \(\langle B w,w\rangle\leq\|B\|_{sp}\|w\|^2\), with \(B=(I-\eta H)^{2t}\) and \(w=H^{1/2}(x^{(0)}-x^\star)\), and that \(B\) commutes with \(H\), we have
\[f(x^{(t)}) - f(x^\star) \leq \left\| (I - \eta H)^{2t} \right\| \frac{1}{2} \langle x^{(0)} - x^{\star} , H (x^{(0)} - x^{\star}) \rangle .\]Using again (3), we have
\[f(x^{(t)}) - f(x^\star) \leq \left\| (I - \eta H)^{2t} \right\| (f(x^{(0)}) - f(x^\star)) .\]Case \(\mu > 0\). Now, we have according to the previous section, the following linear rate.
\[f(x^{(t)}) - f(x^\star) \leq \left( 1 - \frac{1}{\kappa} \right)^{2t} (f(x^{(0)}) - f(x^\star)) .\]Case \(\mu = 0\). Let’s study the eigenvalues of1 \((I - \eta H)^{2t} H\). We keep our analysis restricted to \(0<\eta \leq \frac{1}{L}\).
\begin{align*} | \lambda (1 - \eta \lambda)^{2t} | &\leq \lambda \exp(-\eta \lambda)^{2t} \\ &= \lambda \exp(-2t\eta\lambda) \\ &= \frac{1}{2t\eta} 2t\eta\lambda \exp(-2t\eta\lambda) & \text{insert the term } 2t\eta \\ &\leq \frac{1}{2t\eta} \sup_{\rho \geq 0} \rho \exp(-\rho) & \text{crude bound} \\ &= \frac{1}{2et\eta} & \text{maximum at } \rho = 1 \\ &\leq \frac{1}{4t\eta} & e > 2 . \end{align*}Hence, we obtain the claimed \(O(1/t)\) rate.
1.4 Convergence of gradient descent for nonconvex functions
Unfortunately, not every functions are quadratic, and we need to deep diver in the analysis of the gradient descent algorithm to understand its behavior on generic function. We are going to explore several class of functions that leads to different rates, either in norm or in objective values.
Coercive continuously differentiable function
The following proposition show a very weak result without any quantification of the rate of convergence of gradient descent.
Proposition 7: Convergence of (GD) for coercive \(C^{1}\) functions
Let \(f: \RR^{d} \to \RR\) be a coercive function and assume moreover that it is continuously differentiable. For any initial guess \(x^{(0)}\), the oracle GD iterates \(x^{(t)}\) converge up to a subsequence towards a critical point of \(f\).
Proof
(i) The value sequence is (strictly)decreasing (unless it reaches a critical point). We recall that the oracle GD chose the step-size \(\eta^{(t)}\) as
\[\begin{gathered}\phi^{(t)}(\eta) \eqdef f(x^{(t)}-\eta\nabla f(x^{(t)})),\qquad \eta^{(t)}\in\uargmin{\eta\geq 0}\phi^{(t)}(\eta) . \end{gathered}\]If \(\nabla f(x^{(t)})\neq 0\), coercivity implies \(\phi^{(t)}(\eta)\to+\infty\) as \(\eta\to+\infty\), so the oracle step exists. If the gradient is zero, the line-search objective is constant and the iterate stays unchanged.
Hence, evaluating \(\phi^{(t)}\) at \(\eta^{(t)}\) and 0 leads to
\[f(x^{(t+1)}) = \phi^{(t)}(\eta^{(t)}) {\,\leq\,} \phi^{(t)}(0) = f(x^{(t)}) .\]Suppose that \(f(x^{(t+1)}) = f(x^{(t)})\). Thus, 0 is a minimizer of \(\phi^{(t)}\) and therefore its one-sided first-order condition reads \(\frac{d}{d \eta}\phi^{(t)}(0) \geq 0\). Given \(\eta \geq 0\), we have
\[\frac{d}{d \eta}\phi^{(t)}(\eta) = \dotp{-\nabla f(x^{(t)})}{\nabla f (x^{(t)} - \eta \nabla f(x^{(t)}))} .\]Evaluating this expression at \(\eta = 0\) gives us \(- \norm{\nabla f(x^{(t)})}^2\geq 0\), hence \(\nabla f(x^{(t)}) = 0\) that means \(x^{(t)}\) is a critical point.
(ii) The iterates sequence is converging (up to a subsequence). Consider the set \(S = \setcond{x \in \RR^{d}}{f(x) \leq f(x^{(0)})}\). Remark that:
- \(f\) is continuous, thus \(S\) is closed;
- \(f\) is coercive, thus \(S\) is bounded.
Hence, \(S\) is compact. Observe that for all \(t \geq 0\), \(x^{(t)} \in S\). Using Bolzano–Weierstrass theorem, we get that the sequence \((x^{(t)})\) has a convergent subsequence towards some \(x^{*}\). Let us denote it by \((x^{(\psi(t))})_{t \geq 0}\) where \(\psi : \NN \to \NN\) is increasing.
The value sequence is decreasing and bounded below, so it converges to \(\ell\). By continuity, \(\ell=f(x^*)\).
(iii) The limit of the iterates sequence is a critical point. Suppose that \(x^{*}\) is not a critical point. Using (i), we now that \(x^{**}\) defined as \(x^{**} = x^{*} - \eta^{*} \nabla f(x^{*}) \neq x^{*}\), where \(\eta^{*} > 0\) is the oracle step, is such that \(f(x^{**}) < f(x^{*})\). Consider the sequence \(y^{(t)} = x^{(\psi(t))}\) converging to \(x^{*}\). Remark that, using the continuity of the map \(z \mapsto z - \eta^{*} \nabla f(z)\) for a contiously differentiable function \(f\), we have
By definition of \(\phi^{(t)}\), we also have for all \(t \geq 0\) that
\[\phi^{(\psi(t))}(\eta^{*}) \geq \phi^{(\psi(t))}(\eta^{(\psi(t))}) \geq \ell=f(x^{*}).\]Hence,
\[f(y^{(t)} - \eta^{*} \nabla f(y^{(t)})) \geq f(x^{*})\]Using (4), we get that \(f(x^{**}) \geq f(x^{*})\), that is a contradiction. In conclusion, \(x^{*}\) is a critical point.
The same argument applies to any convergent subsequence.
Remark that if in addition \(f\) has a unique critical point, which is then its unique global minimizer, then \(x^{(t)}\) converges to this global minimizer.
Corollary 8
Let \(f: \RR^{d} \to \RR\) be a coercive, continuously differentiable function with a unique critical point \(x^{\star}\). For any initial guess \(x^{(0)}\), the oracle GD iterates \(x^{(t)}\) converge towards \(x^{\star}\)
Proof
See Exercise 2.
Smooth function bounded from below
Consider a function \(f: \RR^{d} \to \RR\) that is \(L\)-smooth, but not necessarly convex. In addition, we suppose that \(f\) has full domain and is bounded below on \(\RR^{d}\). The following proposition gives a \(O(1/\sqrt{T})\) rate for the 1st-order optimality using a constant step-size. A similar proof is doable for the oracle or the backtracking gradient descent.
Proposition 9: Convergence of (GD) for \(L\)-smooth functions
Let \(f: \RR^{d} \to \RR\) be a \(L\)-smooth function with \(L>0\), bounded from below by \(\bar f \in \RR\). For any initial guess \(x^{(0)}\), the GD iterates \(x^{(t)}\) with step-size \(\eta^{(t)} = \eta \in (0,2/L)\) satisfy \(\nabla f(x^{(t)})\to 0\), and moreover
\[\min_{0 \leq t \leq T} \norm{\nabla f(x^{(t)})} \leq \frac{1}{\sqrt{T+1}} \left( \omega^{-1} L (f(x^{(0)}) - \bar f) \right)^{1/2} ,\]where \(\omega = 2 \alpha (1-\alpha)\), \(0<\alpha<1\), and \(\eta = \frac{2\alpha}{L}\).
Proof
(i) Bound on one step of gradient descent. For \(x \in \RR^{d}\), let \(y = x - \eta \nabla f(x)\). Using Proposition 17, we have that
\begin{align*} f(y) &\leq f(x) + \dotp{\nabla f(x)}{y - x} + \frac{L}{2} \norm{y - x}^{2} \\ &=f(x) + \dotp{\nabla f(x)}{-\eta \nabla f(x)} + \frac{L}{2} \norm{\eta \nabla f(x)}^{2} \\ &=f(x) - \eta \norm{\nabla f(x)}^{2} + \frac{L \eta^{2}}{2} \norm{\nabla f(x)}^{2} \\ &=f(x) - \eta(1 - \frac{L\eta}{2}) \norm{\nabla f(x)}^{2} . \end{align*}To ensure that \(f(y) \leq f(x)\), we need to require that \(\eta(1 - \frac{L\eta}{2}) \geq 0\) that is \(0\leq\eta\leq\frac{2}{L}\). We can parameterize \(\eta\) as \(\eta = \frac{2 \alpha}{L}\) with \(\alpha \in (0,1)\). Hence, we get the descent
(ii) Convergence of 1st-order optimality. Applying (5) to \(x = x^{(t)}\) and \(y = x^{(t+1)}\), we get that
Summing inequality (6) for \(t = 0 \dots T\), we obtain
\begin{equation*} \sum_{t=0}^{T} f(x^{(t)}) - f(x^{(t+1)}) \geq \frac{2 \alpha(1-\alpha)}{L} \sum_{t=0}^{T }\norm{\nabla f(x^{(t)})}^{2} . \end{equation*}Observing that the l.h.s. telescopes, we have
by definition of \(\bar f\). Since (7) is true for all \(T \in \NN\), we get \(\nabla f(x^{(t)})\) converges towards 0.
(iii) Rate of convergence. Using the fact that for all \(t = 0 \dots T\), we have
\[\min_{0\leq s\leq T}\norm{\nabla f(x^{(s)})}\leq\norm{\nabla f(x^{(t)})}\]for each \(0\leq t\leq T\), we have from (7) that
\[\frac{2 \alpha(1-\alpha)}{L} (T+1) \min_{0 \leq t \leq T} \norm{\nabla f(x^{(t)})}^{2} \leq f(x^{(0)}) - \bar f ,\]Hence, the claimed result.
Note that we cannot say anything in this context about the rate of convergence of \(f(x^{(t)})\) or \((x^{(t)})\)! One can show that \(\eta = \frac{1}{L}\) is the optimal step-size with respect to the bound in (5).
1.5 Convergence of gradient descent for convex functions
Convex \(L\)-smooth function
When \(f\) is supposed to be convex, we can have a rate of convergence in objective values.
Proposition 10: Rate of (GD) for convex \(L\)-smooth functions
Let \(f: \RR^{d} \to \RR\) be a convex \(L\)-smooth function with \(L>0\) and at least one minimizer. For any initial guess \(x^{(0)}\), the GD iterates \(x^{(t)}\) with step-size \(\eta^{(t)} = \eta \in (0,\frac{2}{L})\) converge towards an optimal point \(x^{\star}\) of \(f\), and moreover
\[f(x^{(t)}) - f^{\star} \leq \frac{ 2(f(x^{(0)}) - f^{\star}) \norm{x^{(0)} - x^{\star}}^{2} }{ t \eta (2 - L \eta) (f(x^{(0)}) - f^{\star}) + 2 \norm{x^{(0)} - x^{\star}}^{2} } .\]If \(x^{(0)}\) is a minimizer, the iterates are stationary and the first bound is understood as zero.
Moreover, if \(\eta = \frac{1}{L}\), then
\[f(x^{(t)}) - f^{\star} \leq \frac{2 L \norm{x^{(0)} - x^{\star}}^{2}}{t + 4} .\]Proof
Let \(x^{\star}\) a minimizer of \(f\).
If \(f(x^{(0)})=f(x^\star)\), the iterates are stationary and the bounds are understood as zero. Otherwise \(r^{(0)}>0\). In the following divisions, assume \(\delta^{(t+1)}>0\); if an iterate is a minimizer, all later iterates stay there and the claimed bounds are immediate.
We consider \(r^{(t)} = \norm{x^{(t)} - x^{\star}}\) the lack of optimality2. We have
\begin{align*} (r^{(t+1)})^{2} &= \norm{x^{(t)} - x^{\star} - \eta \nabla f(x^{(t)})}^{2} \\ &= (r^{(t)})^{2} - 2\eta \dotp{\nabla f(x^{(t)})}{x^{(t)} - x^{\star}} + \eta^{2} \norm{\nabla f(x^{(t)})}^{2} \end{align*}Using the co-coercivity of the gradient (Proposition 18), we have that
\begin{equation*} \dotp{\nabla f(x^{(t)}) - \underbrace{\nabla f(x^{\star})}_{=0}}{x^{(t)} - x^{\star}} \geq \frac{1}{L} \norm{\nabla f(x^{(t)}) - \underbrace{\nabla f(x^{\star})}_{=0}}^{2} . \end{equation*}Thus,
\[(r^{(t+1)})^{2} \leq (r^{(t)})^{2} - \eta(\frac{2}{L} - \eta) \norm{\nabla f(x^{(t)})}^{2} .\]In particular, we get that \(r^{(t)} \leq r^{(0)}\) for all \(t \geq 0\).
Using the smoothness of \(f\), Proposition 17 gives us the bound
\begin{align*} f(x^{(t+1)}) &\leq f(x^{(t)}) + \dotp{\nabla f(x^{(t)})}{x^{(t+1)} - x^{(t)}} + \frac{L}{2} \norm{x^{(t+1)} - x^{(t)}}^{2} \end{align*}Using the gradient descent update, we have that
\begin{equation*} f(x^{(t+1)}) \leq f(x^{(t)}) - \eta(1 - \frac{L\eta}{2}) \norm{\nabla f(x^{(t)})}^{2} . \end{equation*}Now, let \(\delta^{(t)} = f(x^{(t)}) - f(x^{\star})\). Using the differential characterization of convexity (Proposition 16), we have
\[\delta^{(t)} \leq \dotp{\nabla f(x^{(t)})}{x^{(t)} - x^{\star}} .\]Using Cauchy–Schwarz inequality, we have
\[\delta^{(t)} \leq \norm{\nabla f(x^{(t)})} \norm{x^{(t)} - x^{\star}} = r^{(t)} \norm{\nabla f(x^{(t)})} \leq r^{(0)} \norm{\nabla f(x^{(t)})} .\]Hence, we have
\[\delta^{(t+1)} \leq \delta^{(t)} - \frac{q}{(r^{(0)})^{2}} (\delta^{(t)})^{2} ,\]where \(q = \eta(1 - \frac{L\eta}{2})\). Multiplying both side by \(\frac{1}{\delta^{(t)}\delta^{(t+1)}} > 0\), we get that
\[\frac{1}{\delta^{(t)}} \leq \frac{1}{\delta^{(t+1)}} - \frac{q}{(r^{(0)})^{2}} \frac{\delta^{(t)}}{\delta^{(t+1)}} .\]Since \((f(x^{(t)}))\) is nonincreasing, we have \(\frac{\delta^{(t)}}{\delta^{(t+1)}} \geq 1\), hence
\[\frac{1}{\delta^{(t+1)}} \geq \frac{1}{\delta^{(t)}} + \frac{q}{(r^{(0)})^{2}} .\]Summing \(T\) inequalities of this type, we obtain
\[\frac{1}{\delta^{(T)}} \geq \frac{1}{\delta^{(0)}} + T \frac{q}{(r^{(0)})^{2}} .\]We conclude using a bit of computation:
\begin{equation*} \delta^{(T)} \leq \left(\frac{1}{\delta^{(0)}} + T \frac{q}{(r^{(0)})^{2}} \right)^{-1} = \left( \frac{(r^{(0)})^{2} + T q \delta^{(0)}}{\delta^{(0)}(r^{(0)})^{2}} \right)^{-1} = \frac{\delta^{(0)}(r^{(0)})^{2}}{(r^{(0)})^{2} + T q \delta^{(0)}} \end{equation*}Replacing \(q\), \(r^{(0)}\) and \(\delta^{(0)}\) by their expression gives the result.
Maximizing the descent \(\eta(2 - L\eta)\) gives the optimal step-size \(\eta = \frac{1}{L}\). Injecting this value, we get that
\[\delta^{(T)} \leq \frac{2L\delta^{(0)}(r^{(0)})^{2}}{2L(r^{(0)})^{2} + T\delta^{(0)}} .\]Using the smoothness (Proposition 17), we have
\[f(x^{(0)}) \leq f^{\star} + \dotp{\nabla f(x^{\star})}{x^{(0)} - x^{\star}} + \frac{L}{2} (r^{(0)})^{2} = f^{\star} + \frac{L}{2} (r^{(0)})^{2}\]Thus,
\[2L (r^{(0)})^{2} + T \delta^{(0)} \geq (4 + T) \delta^{(0)} ,\]which is the claimed result.
Finally, the nonincreasing distances to any minimizer make the iterates bounded. A convergent subsequence exists, and the value bound and continuity show that its limit \(\bar x\) is a minimizer. Since \(\|x^{(t)}-\bar x\|\) is nonincreasing and tends to zero along that subsequence, the whole sequence converges to \(\bar x\).
Strongly convex \(L\)-smooth function
We now prove the linear convergence of (GD) when dealing with strongly convex functions.
Proposition 11: Rate of (GD) for strongly convex smooth functions
Let \(f: \RR^{d} \to \RR\) be a \(\mu\)-strongly convex \(L\)-smooth function with \(0<\mu\leq L\). For any initial guess \(x^{(0)}\), the GD iterates \(x^{(t)}\) with step-size \(\eta^{(t)} = \eta \in (0,\frac{2}{\mu + L}]\) converge towards an optimal point of \(f\), and moreover
\[\norm{x^{(t)} - x^{\star}}^{2} \leq \left( 1 - \frac{2 \eta \mu L}{\mu + L} \right)^{t} \norm{x^{(0)} - x^{\star}}^{2} .\]Moreover, if \(\eta = \frac{2}{\mu + L}\), then
\begin{align*} \norm{x^{(t)} - x^{\star}}^{2} & \leq \left( \frac{K_{f} - 1}{K_{f} + 1} \right)^{2t} \norm{x^{(0)} - x^{\star}}^{2} \\ f(x^{(t)}) - f^{\star} &\leq \frac{L}{2} \left( \frac{K_{f} - 1}{K_{f} + 1} \right)^{2t} \norm{x^{(0)} - x^{\star}}^{2} , \end{align*}where \(K_{f} = L / \mu\).
Proof
Let \(r^{(t)} = \norm{x^{(t)} - x^{\star}}\). We start like the proof of Proposition 10:
\begin{align*} (r^{(t+1)})^{2} &= \norm{x^{(t)} - x^{\star} - \eta \nabla f(x^{(t)})}^{2} \\ &= (r^{(t)})^{2} - 2\eta \dotp{\nabla f(x^{(t)})}{x^{(t)} - x^{\star}} + \eta^{2} \norm{\nabla f(x^{(t)})}^{2} \end{align*}Using Proposition 19, we have
\[\dotp{\nabla f(x^{(t)}) - \nabla f(x^{\star})}{x^{(t)} - x^{\star}} \geq \frac{\mu L }{\mu + L} \norm{x^{(t)}-x^{\star}}^{2} + \frac{1}{\mu + L} \norm{\nabla f(x^{(t)}) - \nabla f(x^{\star})}^{2} ,\]that is
\[\dotp{\nabla f(x^{(t)}) - \nabla f(x^{\star})}{x^{(t)} - x^{\star}} \geq \frac{\mu L }{\mu + L} (r^{(t)})^{2} + \frac{1}{\mu + L}\norm{\nabla f(x^{(t)})}^{2} .\]Hence,
\begin{align*} (r^{(t+1)})^{2} &\leq \left( 1 - \frac{2 \eta \mu L}{\mu + L} \right) (r^{(t)})^{2} + \eta \left( \eta - \frac{2}{\mu + L} \right) \norm{\nabla f(x^{(t)})}^{2} . \end{align*}Since \(\eta - \frac{2}{\mu + L} \leq 0\), we can drop it and we obtain the recursion \((r^{(t+1)})^{2} \leq (1-q) (r^{(t)})^{2}\) with \(q = \frac{2 \eta \mu L}{\mu + L}\), that proves the first claim (linear rate).
Let \(\eta = \frac{2}{\mu + L}\). We have
\[1 - q = 1 - \frac{4\mu L}{(\mu+L)^{2}} = \frac{(L - \mu)^{2}}{(L+\mu)^{2}} = \left( \frac{K_{f} - 1}{K_{f} + 1} \right)^{2}.\]The last inequality is yet another use of Proposition 17.
Gradient descent does not reach the best rates that a first-order method can achieve, namely \(1/t^{2}\) for smooth convex functions and a linear rate governed by \(\sqrt{K_{f}}\) instead of \(K_{f}\) for smooth strongly convex ones, as shown in Introduction to lower bounds in optimization.
Polyak assumption
1.6 An invitation to flow
The joint study of ordinary differential equations and iterative algorithms is very fruitful. Imagine that the iterate \(x^{(t)}\) can be viewed as “snapshot” \(x^{(t)} = x(t \eta)\) of a smooth curve \(x:[0,+\infty)\to\RR^d\), for some learning rate \(\eta>0\). Let \(\tau = t \eta\), observe that
\[x(\tau + \eta) = x^{(t+1)} = x^{(t)} - \eta \nabla f(x^{(t)}) = x(\tau) - \eta \nabla f(x(\tau)) .\]Reorganizing the terms, we get that
\[\frac{1}{\eta} \left( x(\tau + \eta) - x(\tau) \right) = - \nabla f(x(\tau)) .\]Assuming enough regularity, we can let \(\eta\) goes to 0, and we obtain the ODE
\[\dot x(\tau) = - \nabla f(x(\tau)) ,\]where \(\dot x(\tau) = \frac{dx}{d\tau}(\tau)\) is the derivative of \(x\) along the time. The Cauchy problem
is known as the gradient flow of \(f\). One can thus interpret the step-size (or learning rate) \(\eta\) as the discretization precision of the gradient flow. It is possible to derive a similar convergence result for (GF) as for the gradient descent.
Theorem 12: Convergence of the gradient flow
Let \(f: \RR^{d} \to \RR\) be convex, continuously differentiable, and have at least one minimizer. Then, for any initial point \(x^{(0)}\), the dynamics \(\tau \mapsto x(\tau)\) converges towards an optimal point \(x^{\star}\) of \(f\), and moreover, for all \(\tau>0\), one has
\[f(x(\tau)) - f(x^\star) \leq \frac{\norm{x^{(0)} - x^{\star}}^{2}}{2\tau} .\]Proof
Let \(z\) a minimizer of \(f\). By convexity, we have
\[\frac{d}{d\tau}\frac12\norm{x(\tau)-z}^2 =-\dotp{\nabla f(x(\tau))}{x(\tau)-z} \leq -(f(x(\tau))-f(z))\leq 0.\]The continuous vector field gives a local solution. Its distance to \(z\) is nonincreasing, so it stays bounded and extends to all \(\tau\geq 0\). Monotonicity of \(\nabla f\) makes the distance between two solutions with the same starting point nonincreasing, so the solution is unique. Moreover,
\[\frac{d}{d\tau}f(x(\tau))=-\norm{\nabla f(x(\tau))}^2\leq 0.\]Integrating the first inequality and using this monotonicity, we obtain
\[\tau(f(x(\tau))-f(z)) \leq\int_0^\tau(f(x(s))-f(z))\,ds \leq\frac12\norm{x^{(0)}-z}^2.\]Hence, the claimed value bound holds for any minimizer \(z\). Since the trajectory is bounded, it has a limit point \(\bar x\) along a sequence of times tending to infinity. The value bound and continuity show that \(\bar x\) is a minimizer. Its distance to the trajectory is nonincreasing and tends to zero along that sequence, so \(x(\tau)\) converges to \(\bar x\). Taking \(z=\bar x=x^\star\) gives the displayed bound.
1.7 Complements
Optimization for multinomial regression
We study here a method for classification with \(K\) classes called the multinomial logistic regression or softmax classification. The objective function reads for \(W \in \RR^{p \times K}\),
where
\begin{equation*} \hat p(y_{i} = k \mid x_{i}) = \frac{\exp(x_{i}^{\top} W_{k})}{\sum_{l=1}^{K} \exp(x_{i}^{\top} W_{l})} . \end{equation*}Here \(x_i\in\RR^p\), \(y_i\in\{1,\dots,K\}\), \(W_k\) denotes the \(k\)-th column of \(W\), and \(\lambda\geq 0\).
The softmax function \(\sigma: \RR^{K} \to \RR^{K}\) is defined as
\[\sigma(x) = (\sigma_{1}(x),\dots,\sigma_{K}(x))^{\top} \quad \text{where} \quad \sigma_{i}(x) = \frac{e^{x_{i}}}{\sum_{j=1}^{K} e^{x_{j}}} .\]We also introduce the negative log-softmax functions \(\psi_{i}: \RR^{K} \to \RR\) defined as
\[\psi_{k}(x) = -\log \sigma_{k}(x) .\]Thus, our loss is expressed as
\[f(W) = \sum_{i=1}^{n} \sum_{k=1}^{K} \mathbf{1}_{y_{i} = k} \psi_k(W^\top x_i) + \lambda \norm{W}_{\text{Fro}}^{2} ,\]Lemma 13: Jacobian of the softmax
Let \(x \in \RR^{K}\),
\[\Jaco{\sigma}(x) = \diag(\sigma(x)) - \sigma(x) \sigma(x)^{\top} .\]Proof
Observe that for \(j \in \{1, \dots, K \}\), we have
\[\frac{\partial \left( \sum_{k=1}^{K} e^{x_{k}} \right)^{-1}}{\partial x_{j}} = - \frac{1}{\left( \sum_{k=1}^{K} e^{x_{k}} \right)^{2}} \frac{\partial \left( \sum_{k=1}^{K} e^{x_{k}} \right)}{\partial x_{j}} = - \frac{e^{x_{j}}}{\left( \sum_{k=1}^{K} e^{x_{k}} \right)^{2}} = - \frac{1}{\sum_{k=1}^{K} e^{x_{k}}} \sigma_{j}(x).\]Now, take \(i,j \in \{ 1,\dots, K \}\). Then, two cases occurs:
If \(i \neq j\). We have
\[\frac{\partial \sigma_{i}}{\partial x_{j}}(x) = e^{x_{i}} \frac{\partial \left( \sum_{k=1}^{K} e^{x_{k}} \right)^{-1}}{\partial x_{j}} = - \sigma_{i}(x) \sigma_{j}(x) .\]If \(i = j\).
\[\frac{\partial \sigma_{j}}{\partial x_{j}}(x) = e^{x_{j}} \frac{\partial \left( \sum_{k=1}^{K} e^{x_{k}} \right)^{-1}}{\partial x_{j}} + e^{x_{j}} \left( \sum_{k=1}^{K} e^{x_{k}} \right)^{-1} = \sigma_{j}(x) (1 - \sigma_{j}(x)) .\]Lemma 14: Gradient of the negative logsoftmax
Let \(i \in \{1,\dots,K\}\) and \(x \in \RR^{K}\). Then,
\[\nabla \psi_{i}(x) = \sigma(x) - e_{i} \quad \text{and} \quad \nabla^{2} \psi_{i}(x) = \Jaco{\sigma}(x) .\]Proof
Let \(k \in \{1,\dots,K\}\). Then,
\[\frac{\partial \psi_{i}(x)}{\partial x_{k}} = - \frac{1}{\sigma_{i}(x)} \frac{\partial \sigma_{i}(x)}{\partial x_{k}} = \begin{cases} \sigma_{k}(x) & \text{if } i \neq k \\ \sigma_{k}(x) - 1 & \text{if } i = k. \end{cases}\]Differentiating \(\nabla\psi_i(x)=\sigma(x)-e_i\) gives \(\nabla^2\psi_i(x)=\Jaco{\sigma}(x)\).
Lemma 15: Convexity of the negative logsoftmax
For all \(k \in \{1, \dots, K\}\), \(\psi_{k}\) is convex.
Proof
Using the preceding lemma, we have for any \(v\in\RR^K\)
\[v^\top\nabla^2\psi_k(x)v =\sum_{j=1}^K\sigma_j(x)v_j^2 -\left(\sum_{j=1}^K\sigma_j(x)v_j\right)^2 =\sum_{j=1}^K\sigma_j(x)(v_j-\bar v)^2\geq 0,\]where \(\bar v=\sum_{j=1}^K\sigma_j(x)v_j\), since \(\sum_j\sigma_j(x)=1\). Hence, \(\psi_k\) is convex.
1.8 Exercises
Exercise 1
Consider the problem
\[\min_{x \in \RR^{d}} f(x) = \frac{1}{2} \| A x - b \|^{2} ,\]where \(A\in\RR^{n\times d}\), \(n,d\geq 1\), \(b\in\RR^n\), and the entries \(A_{i,j}\sim\Nn(0,1)\) are independent and identically distributed. Explain why:
- for \(d\geq 2\), bad conditioning is possible, even though the entries of \(A\) are Gaussian
- almost surely, \(f\) satisfies the Polyak–Łojasiewicz inequality \(\norm{\nabla f(x)}^2\geq 2\mu_+(f(x)-f^\star)\), where \(\mu_+\) is the smallest positive eigenvalue of \(A^\top A\)
Exercise 2
Prove Corollary 8.
Answer (of Exercise 2)
Proof by contradiction. Suppose that \(x^{(t)}\) does not converge towards \(x^{\star}\), i.e.,
\[\exists \epsilon > 0, \forall T \in \NN, \exists t \geq T, \quad \norm{x^{(t)} - x^{\star}} > \epsilon .\]Using boundedness from step \((ii)\), extract a convergent subsequence staying at distance at least \(\epsilon\) from \(x^\star\). By step \((iii)\), its limit is a critical point distinct from \(x^\star\). Conclude that you have two critical points.
Exercise 3
Show that the coefficient \(2\alpha(1-\alpha)/L\) in (5) is maximized for \(\alpha = \frac{1}{2}\).
A Propositions used from Lecture 1
We recall here the propositions from Lecture 1 used in this lecture. All norms in this appendix are Euclidean.
Proposition 16: Differential characterization of convexity
Let \(f\) be a differentiable function on an open set \(\Omega\subseteq\RR^p\), and \(C\subseteq\Omega\) a convex subset of \(\Omega\). Then \(f\) is convex on \(C\) if, and only if,
\[\forall x,\bar x\in C,\quad f(x)\geq f(\bar x)+\dotp{\nabla f(\bar x)}{x-\bar x}.\]Proposition 17: Quadratic upper-bound
Let \(f\) a \(L\)-smooth function, with \(L>0\). Then, for all \(x,y\in\mathrm{dom}f\),
Moreover, if \(\mathrm{dom}f\) is convex, then (9) is equivalent to
\[f(y)\leq f(x)+\dotp{\nabla f(x)}{y-x}+\frac{L}{2}\norm{x-y}^2, \quad\forall x,y\in\mathrm{dom}f.\]Proposition 18: Co-coercivity of the gradient
Let \(f\) be a full-domain convex \(L\)-smooth function, with \(L>0\). Then, \(\nabla f\) is \(1/L\)-co-coercive, i.e.,
\[\forall x,y\in\RR^n,\quad \dotp{\nabla f(x)-\nabla f(y)}{x-y} \geq\frac{1}{L}\norm{\nabla f(x)-\nabla f(y)}^2.\]Proposition 19: Strengthened co-coercivity
Let \(f:\RR^n\to\RR\) have full effective domain and be \(L\)-smooth and \(\mu\)-strongly convex, where \(0<\mu\leq L\). For any \(x,y\in\RR^n\), we have
\[\dotp{\nabla f(x)-\nabla f(y)}{x-y} \geq\frac{\mu L}{\mu+L}\norm{x-y}^2 +\frac{1}{\mu+L}\norm{\nabla f(x)-\nabla f(y)}^2.\]References
Footnotes
AI disclosure
The first version from 2024 was written from handwritten notes. The 2026 update was proofread by GPT-6 Astra, and the interactive figures were entirely generated by the same model from the non-interactive TikZ version. The org-mode conversion from tex was also done by AI.