---
title: Numerical Optimization and Gradient Descent
module: Mathematical Algorithms
moduleNumber: 10
lessonNumber: 7
order: 1007
summary: |
  Most of this course chases **discrete** optima over finite structures; here the
  search space is **continuous** and the objective $f$ is differentiable. The
  **gradient** points uphill, so stepping against it —
  $x_{t+1} = x_t - \eta\,\nabla f(x_t)$ — walks downhill. **Convexity** makes every
  local minimum global; for convex $L$-smooth $f$ gradient descent converges at
  $O(1/t)$, and **geometrically** under strong convexity. **Newton's method** uses
  the Hessian for local quadratic convergence, and **bisection** is the robust
  bracketing fallback for roots.
topics: [Number Theory]
sources:
  - book: CLRS
    ref: "Ch. — (numerical methods; Newton's method for root-finding)"
  - book: Skiena
    ref: "§ — Numerical Problems / Optimization"
  - book: Erickson
    ref: "Ch. — (convexity, continuous optimization notes)"
practice:
  - title: 'Sqrt(x)'
    slug: sqrtx
    difficulty: Easy
  - title: 'Find Peak Element'
    slug: find-peak-element
    difficulty: Medium
  - title: 'Koko Eating Bananas'
    slug: koko-eating-bananas
    difficulty: Medium
  - title: 'Minimize Max Distance to Gas Station'
    slug: minimize-max-distance-to-gas-station
    difficulty: Hard
---

Almost every optimization in this course has been **discrete**: pick the best subset, the
shortest path, the cheapest spanning tree, the longest common subsequence. The search space
is finite (if astronomically large), and the tools are combinatorial — exchange arguments,
dynamic programming, network flow. This lesson changes the setting. The variable $x$ ranges
over $\mathbb{R}^n$, a **continuum**, and the objective $f:\mathbb{R}^n\to\mathbb{R}$ is a
smooth, differentiable function we want to **minimize**. There is no finite set to enumerate
and no subproblem table to fill. Instead we use **calculus**: the derivative tells us which
way is downhill, and we keep stepping that way. This method underlies curve
fitting, logistic regression, and the training of every neural network, and it rests on
the gradient.

## The continuous problem

We are given a differentiable $f:\mathbb{R}^n\to\mathbb{R}$ and want a point $x^\star$ where
$f$ is smallest:

$$
x^\star = \arg\min_{x\in\mathbb{R}^n} f(x).
$$

In one dimension, calculus says a minimum of a smooth $f$ occurs where the slope vanishes,
$f'(x)=0$, and the curve bends upward, $f''(x)\ge 0$. In $n$ dimensions the slope becomes a
vector, the **gradient**

$$
\nabla f(x) = \parens{\frac{\partial f}{\partial x_1},\,\dots,\,\frac{\partial f}{\partial x_n}},
$$

and a minimum requires $\nabla f(x)=0$. Solving $\nabla f(x)=0$ in closed form is possible
only for the simplest $f$ (a quadratic gives a linear system). For everything else we need an
**iterative** method that starts somewhere and improves, step by step. Every such
method starts from the geometry of the gradient.

## The gradient points uphill

Fix a point $x$ and ask: among all unit directions $u$, which one increases $f$ the fastest?
The first-order Taylor expansion answers it. Moving a small distance $\varepsilon$ along $u$,

$$
f(x + \varepsilon u) \approx f(x) + \varepsilon\,\langle \nabla f(x),\, u\rangle,
$$

so the rate of change in direction $u$ is the inner product $\langle \nabla f(x), u\rangle$.
By Cauchy–Schwarz this is largest when $u$ aligns with $\nabla f(x)$ and most negative when
$u$ points the opposite way. So **the gradient is the direction of steepest ascent**, and its
negation $-\nabla f(x)$ is the direction of steepest **descent**. The gradient is also
**perpendicular** to the level curve $\{x : f(x) = c\}$ through the point: along the level
curve $f$ does not change, so the steepest-change direction must be orthogonal to it.

$$
% caption: The gradient $\nabla f$ at a point is perpendicular to the level curve through it
%          and points toward higher values; the descent direction is $-\nabla f$.
\begin{tikzpicture}[
  every node/.style={font=\small},
  >=stealth, scale=1.0]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1A8F4C}
  % three nested level curves (closed loops) as smooth plots
  \draw[acc!25, thick] plot[smooth cycle, tension=0.7] coordinates {(-2.6,0) (-1.3,1.5) (1.4,1.7) (2.7,0) (1.3,-1.6) (-1.4,-1.6)};
  \draw[acc!45, thick] plot[smooth cycle, tension=0.7] coordinates {(-1.7,0) (-0.8,1.0) (0.9,1.1) (1.8,0) (0.8,-1.0) (-0.9,-1.0)};
  \draw[acc!65, thick] plot[smooth cycle, tension=0.7] coordinates {(-0.8,0) (-0.4,0.5) (0.45,0.5) (0.85,0) (0.4,-0.5) (-0.45,-0.5)};
  \fill[acc] (0,0) circle (1.5pt);
  \node[acc, anchor=north, font=\footnotesize] at (0,-0.18) {minim\/um};
  % a point on the middle level curve
  \fill[black] (1.8,0) circle (1.6pt);
  \node[anchor=south west, font=\footnotesize] at (1.7,0.55) {point};
  % outward gradient arrow (uphill)
  \draw[->, acc, very thick] (2.0,0) -- (3.2,0);
  \node[acc, anchor=south, font=\footnotesize] at (2.6,0.1) {uphill};
  % inward descent arrow
  \draw[->, green, very thick] (1.6,0) -- (0.5,0);
  \node[green, anchor=south, font=\footnotesize] at (1.05,0.1) {downhill};
\end{tikzpicture}
$$

## Gradient descent

The algorithm follows directly. Start at any $x_0$. At each step, move a little in the
steepest-descent direction:

$$
x_{t+1} \;=\; x_t \;-\; \eta\,\nabla f(x_t),
$$

where $\eta > 0$ is the **learning rate** (or step size). Each step strictly decreases $f$
for small enough $\eta$, because the first-order change is
$f(x_{t+1}) - f(x_t) \approx -\eta\,\lVert\nabla f(x_t)\rVert^2 \le 0$. We stop when the
gradient is nearly zero — the slope has flattened, and we are at (or near) a stationary point.

```algorithm
caption: $\textsc{Gradient-Descent}(f, x_0, \eta)$ — step against the gradient until flat
number: 1
$x \gets x_0$
while $\lVert \nabla f(x) \rVert > \varepsilon$ do      // not yet flat
  $g \gets \nabla f(x)$                                 // steepest-ascent direction
  $x \gets x - \eta \cdot g$                            // step downhill
return $x$
```

::impl{algo="gradient_descent"}

The method has one free parameter, and it matters.

> **Definition (Learning rate).** The scalar $\eta>0$ in $x_{t+1}=x_t-\eta\nabla f(x_t)$ that
> scales each step. Too small and progress is slow; too large and the iterate overshoots
> the minimum and can oscillate or diverge.

If $\eta$ is **too small**, the iterates creep toward the minimum, needing huge numbers of
steps. If $\eta$ is **too large**, a step can jump clear over the valley floor and land
higher than it started; successive overshoots then bounce between the walls, oscillating,
or spiral outward and **diverge**. Much of first-order optimization comes down to
choosing (or adapting) $\eta$.

**Worked example (three learning rates on a parabola).** Minimize $f(x) = x^2$, for
which $f'(x) = 2x$ and the update is $x_{t+1} = x_t - \eta\cdot 2x_t = (1 - 2\eta)x_t$
— each step multiplies the iterate by the fixed contraction factor $r = 1 - 2\eta$.
Starting from $x_0 = 1$, the behaviour is decided entirely by $|r|$:

- $\eta = 0.1$ gives $r = 0.8$: the iterates $1,\ 0.8,\ 0.64,\ 0.512,\dots$ shrink
  steadily to $0$ — healthy convergence.
- $\eta = 0.9$ gives $r = -0.8$: $1,\ -0.8,\ 0.64,\ -0.512,\dots$ still converges,
  but **oscillates** in sign, overshooting the minimum each step before creeping in.
- $\eta = 1.1$ gives $r = -1.2$: $1,\ -1.2,\ 1.44,\ -1.728,\dots$ grows without
  bound — the step is so large it lands **farther** from the minimum each time, and
  the method **diverges**.

The threshold is exactly $\eta < 1$ here (so that $|1 - 2\eta| < 1$); more generally,
for an $L$-smooth objective the safe range is $\eta < 2/L$, and $\eta = 1/L$ is the
textbook choice. The condition $r = 1 - 2\eta$ is a one-line preview of why the
strong-convexity rate below is _geometric_: a fixed multiplicative shrink per step.

$$
% caption: A well-chosen $\eta$ (left) descends steadily to the minimum; too large an $\eta$
%          (right) overshoots and oscillates across the valley.
\begin{tikzpicture}[
  every node/.style={font=\small},
  >=stealth, scale=1.0]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1A8F4C}
  \definecolor{red}{HTML}{C0392B}
  % LEFT: small step, steady convergence
  \begin{scope}[shift={(-3.4,0)}]
    \draw[black, very thick] plot[smooth, domain=-1.85:1.85, samples=60] (\x, {0.7*\x*\x});
    \draw[->, thick] (-2.2,0) -- (2.2,0) node[right, font=\footnotesize] {$x$};
    \fill[green] (0,0) circle (1.8pt);
    \node[green, anchor=north, font=\footnotesize] at (0.05,-0.14) {minim\/um};
    % iterates on the bowl, joined by straight steps
    \foreach \x in {-1.6,-0.85,-0.42,-0.18} \fill[acc] (\x,{0.7*\x*\x}) circle (1.7pt);
    \draw[->, acc, thick] (-1.6,{0.7*1.6*1.6}) -- (-0.85,{0.7*0.85*0.85});
    \draw[->, acc, thick] (-0.85,{0.7*0.85*0.85}) -- (-0.42,{0.7*0.42*0.42});
    \draw[->, acc, thick] (-0.42,{0.7*0.42*0.42}) -- (-0.18,{0.7*0.18*0.18});
    \node[acc, anchor=south, font=\footnotesize] at (-0.7,2.35) {steady descen\/t};
  \end{scope}
  % RIGHT: large step, overshoot and oscillation
  \begin{scope}[shift={(3.4,0)}]
    \draw[black, very thick] plot[smooth, domain=-1.85:1.85, samples=60] (\x, {0.7*\x*\x});
    \draw[->, thick] (-2.2,0) -- (2.2,0) node[right, font=\footnotesize] {$x$};
    \fill[green] (0,0) circle (1.8pt);
    \node[green, anchor=north, font=\footnotesize] at (0.05,-0.14) {minim\/um};
    % iterates bounce across the valley with growing amplitude
    \foreach \x in {-0.7,1.1,-1.55} \fill[red] (\x,{0.7*\x*\x}) circle (1.7pt);
    \draw[->, red, thick] (-0.7,{0.7*0.7*0.7}) -- (1.1,{0.7*1.1*1.1});
    \draw[->, red, thick] (1.1,{0.7*1.1*1.1}) -- (-1.55,{0.7*1.55*1.55});
    \node[red, anchor=south, font=\footnotesize] at (0.1,2.35) {overshoot};
  \end{scope}
\end{tikzpicture}
$$

## Convexity, and why local is global

Gradient descent finds a point where the gradient vanishes — a **stationary** point. For a
general nonconvex $f$ that could be a local minimum, a saddle, or a poor local optimum far
from the best value. **Convexity** eliminates this problem.

> **Definition (Convex function).** $f$ is convex if its graph lies below every chord: for
> all $x,y$ and $\lambda\in[0,1]$,
> $$f(\lambda x + (1-\lambda) y) \le \lambda f(x) + (1-\lambda) f(y).$$
> Equivalently, for differentiable $f$, the graph lies above each tangent:
> $f(y) \ge f(x) + \langle \nabla f(x), y-x\rangle$.

A convex function is a single bowl with no false bottoms, so local information
determines the global optimum.

> **Theorem (Local optima are global).** If $f$ is convex, every local minimum is a global
> minimum, and the set of minimizers is convex. In particular any stationary point
> ($\nabla f(x)=0$) is a global minimizer.

> **Proof.** Suppose $x$ is a local minimum and some $y$ has $f(y)<f(x)$. Convexity gives, for
> small $\lambda>0$, $f(x+\lambda(y-x)) \le (1-\lambda)f(x)+\lambda f(y) < f(x)$. Points
> $x+\lambda(y-x)$ lie arbitrarily close to $x$, contradicting that $x$ is a local minimum.
> If additionally $\nabla f(x)=0$, the tangent inequality $f(y)\ge f(x)+\langle 0, y-x\rangle
> = f(x)$ holds for every $y$, so $x$ is global. $\qed$

So on a convex objective, gradient descent's "walk downhill until flat" cannot get trapped:
the only flat spot is the bottom.

$$
% caption: A convex bowl: the graph lies above every tangent and below every chord, so the
%          single stationary point is the global minimum.
\begin{tikzpicture}[
  every node/.style={font=\small},
  >=stealth, scale=1.0]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1A8F4C}
  \draw[acc, very thick] plot[smooth, domain=-2.1:2.1, samples=70] (\x, {0.55*\x*\x});
  % a chord joining two points on the graph — the graph lies below it
  \draw[red, thick, dashed] (-1.7,{0.55*1.7*1.7}) -- (1.5,{0.55*1.5*1.5});
  \fill[red] (-1.7,{0.55*1.7*1.7}) circle (1.7pt);
  \fill[red] (1.5,{0.55*1.5*1.5}) circle (1.7pt);
  \node[red, anchor=south, font=\footnotesize] at (-0.1,1.55) {chord above};
  % the x-axis is the tangent at the minimum
  \draw[green, very thick] (-2.6,0) -- (2.7,0) node[right, font=\footnotesize, black] {$x$};
  \node[green, anchor=north, font=\footnotesize] at (1.9,-0.18) {tangent below};
  \fill[green] (0,0) circle (1.9pt);
  \node[green, anchor=south west, font=\footnotesize] at (0.16,0.14) {global min};
\end{tikzpicture}
$$

## A convergence guarantee

How fast does gradient descent reach the bottom? The answer depends on two regularity
constants. We say $f$ is **$L$-smooth** if its gradient does not change too abruptly,
$\lVert\nabla f(x)-\nabla f(y)\rVert \le L\lVert x-y\rVert$ — equivalently $f$ is bounded
above by a quadratic of curvature $L$. We say $f$ is **$\mu$-strongly convex** if it is
bounded **below** by a quadratic of curvature $\mu>0$ (a bowl that curves at least as much as
$\tfrac{\mu}{2}\lVert x\rVert^2$). With these two constants the rate is classical.

> **Theorem (Convergence of gradient descent).** Let $f$ be convex and $L$-smooth, and run
> gradient descent with fixed step $\eta = 1/L$ from $x_0$. Then after $t$ steps
> $$f(x_t) - f(x^\star) \;\le\; \frac{L\,\lVert x_0 - x^\star\rVert^2}{2t} \;=\; O\!\parens{\tfrac{1}{t}}.$$
> If $f$ is additionally $\mu$-strongly convex, convergence is **geometric** (linear): with
> condition number $\kappa = L/\mu$,
> $$\lVert x_t - x^\star\rVert^2 \;\le\; \parens{1 - \tfrac{1}{\kappa}}^{t}\,\lVert x_0 - x^\star\rVert^2.$$

> **Proof sketch.** $L$-smoothness gives the descent inequality
> $f(x_{t+1}) \le f(x_t) - \tfrac{1}{2L}\lVert\nabla f(x_t)\rVert^2$, so each step buys a
> decrease proportional to the squared gradient. Convexity bounds the suboptimality by the
> gradient, $f(x_t)-f(x^\star) \le \langle\nabla f(x_t), x_t-x^\star\rangle$; telescoping the
> per-step decrease over $t$ steps and averaging yields the $O(1/t)$ bound. Under strong
> convexity the suboptimality is itself bounded below by a multiple of
> $\lVert\nabla f\rVert^2$, turning the additive decrease into a **multiplicative** one, which
> contracts the distance by a constant factor $(1-1/\kappa)$ each step — geometric
> convergence. $\qed$

To reach error $\epsilon$, the convex case needs $O(1/\epsilon)$ steps, while
the strongly convex case needs only $O(\kappa\log(1/\epsilon))$ — exponentially fewer. The
**condition number** $\kappa=L/\mu$ is the elongation of the bowl: a round bowl ($\kappa\approx
1$) converges in a few steps; a long thin valley ($\kappa$ large) makes gradient descent
zig-zag slowly down the narrow axis. Contrast this with the **discrete** optimization of the
rest of the course, where "rate" is measured in the input size $n$ (see
[asymptotic analysis](/algorithms/foundations/asymptotic-analysis)); here the iteration count
depends on the **conditioning** of $f$ and the target accuracy $\epsilon$, not on a
combinatorial size.

## Stochastic gradient descent

In machine learning the objective is an **average over data**,
$f(x)=\tfrac{1}{m}\sum_{i=1}^m f_i(x)$, where $f_i$ is the loss on the $i$-th of $m$ training
examples. The exact gradient $\nabla f$ sums $m$ per-example gradients — one full sweep over
the dataset per step, which is ruinous when $m$ is in the millions. **Stochastic gradient
descent** (SGD) replaces the full gradient with a cheap, noisy estimate from a small random
**mini-batch** $B$:

$$
x_{t+1} = x_t - \eta\,\nabla f_B(x_t), \qquad \nabla f_B(x) = \frac{1}{|B|}\sum_{i\in B}\nabla f_i(x).
$$

Each step costs $|B|\ll m$ gradients, so SGD takes vastly more, vastly cheaper steps. The
mini-batch gradient is an **unbiased** estimate of the true gradient, so on average it points
downhill; the variance is noise that jitters the path.

> **Remark (The noise/speed trade-off).** Smaller batches mean cheaper, noisier steps; larger
> batches mean costlier, smoother ones. The noise prevents the clean geometric convergence of
> exact gradient descent — SGD with a fixed step bounces around the optimum rather than
> settling — so the step size is usually **decayed** over time to let the iterate settle. The
> same noise is often beneficial in nonconvex training: it can shake the iterate out of sharp,
> poor minima. SGD trains essentially every modern neural network.

::impl{algo="stochastic_gradient_descent"}

## Second order: Newton's method

Gradient descent uses only the **slope**. Newton's method also uses the **curvature** — the
matrix of second derivatives, the **Hessian** $\nabla^2 f(x)$ — to take a better-scaled step.
Approximate $f$ near $x_t$ by its second-order Taylor expansion (a quadratic) and jump
straight to that quadratic's minimum. Setting the gradient of the approximation to zero gives

$$
x_{t+1} = x_t - \brackets{\nabla^2 f(x_t)}^{-1}\nabla f(x_t).
$$

Where gradient descent crawls down a long thin valley, Newton's method rescales by the
curvature and heads straight for the bottom — and on a quadratic it reaches the exact minimum
in **one** step. Near a minimum its convergence is **quadratic**: the number of correct digits
roughly doubles each iteration.

```algorithm
caption: $\textsc{Newton}(f, x_0)$ — second-order steps; quadratic local convergence
number: 2
$x \gets x_0$
while $\lVert \nabla f(x) \rVert > \varepsilon$ do
  $g \gets \nabla f(x)$                         // gradient
  $H \gets \nabla^2 f(x)$                        // Hessian (curvature)
  $x \gets x - H^{-1} g$                         // solve $H\,\Delta = g$, then step
return $x$
```

::impl{algo="newtons_method"}

> **Theorem (Local quadratic convergence).** If $f$ is twice continuously differentiable with
> $\nabla^2 f$ invertible and Lipschitz near a minimizer $x^\star$, then for $x_0$ close
> enough to $x^\star$ Newton's method satisfies
> $\lVert x_{t+1}-x^\star\rVert \le C\,\lVert x_t-x^\star\rVert^2$ for a constant $C$ — the
> error squares each step.

The cost per step is high. Each step forms the $n\times n$ Hessian and **solves a linear system**
with it, costing $\Theta(n^3)$ (or $\Theta(n^2)$ memory just to store $H$) — prohibitive for
the high-dimensional problems of machine learning. And the quadratic convergence is only
**local**: started far away, Newton's step can overshoot wildly. Practical solvers therefore
use **quasi-Newton** methods (BFGS), which approximate $H^{-1}$ from successive gradients, and
add a line search or trust region for global safety.

## One dimension: Newton–Raphson and bisection

The cleanest case of Newton's method is **root-finding** in one variable: solve $g(x)=0$.
Replacing the Hessian with the scalar derivative, the update becomes the classic
**Newton–Raphson** iteration

$$
x_{t+1} = x_t - \frac{g(x_t)}{g'(x_t)}.
$$

Geometrically, follow the **tangent** at $x_t$ down to where it crosses the axis, and take
that crossing as the next guess. (Minimizing $f$ is finding a root of $g=f'$; this is the same
iteration applied to the derivative.) It converges quadratically when it converges — computing
$\sqrt{a}$ as a root of $g(x)=x^2-a$ gives the famous
$x_{t+1}=\tfrac{1}{2}(x_t + a/x_t)$, doubling correct digits each step. _Sqrt(x)_ asks for
this iteration verbatim.

$$
% caption: Newton–Raphson: the tangent at $x_t$ meets the axis at $x_{t+1}=x_t-g(x_t)/g'(x_t)$,
%          leaping toward the root.
\begin{tikzpicture}[
  every node/.style={font=\small},
  >=stealth, scale=1.0]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1A8F4C}
  \draw[->] (-0.3,0) -- (4.4,0) node[right, font=\footnotesize] {$x$};
  % curve g(x), increasing through a root near x=1.4
  \draw[acc, very thick] plot[smooth, domain=0.2:4.0, samples=60] (\x, {0.42*(\x-1.4)*(\x+0.6)});
  % root
  \fill[green] (1.4,0) circle (1.8pt);
  \node[green, anchor=north, font=\footnotesize] at (1.4,-0.12) {ro\/ot};
  % current guess x_t = 3.4, point on curve
  \fill[black] (3.4,{0.42*(3.4-1.4)*(3.4+0.6)}) circle (1.5pt);
  \draw[acc!40, dashed] (3.4,0) -- (3.4,{0.42*(3.4-1.4)*(3.4+0.6)});
  \node[anchor=north, font=\footnotesize] at (3.4,-0.1) {$x_t$};
  % tangent line at x_t down to the axis (next guess ~ 2.3)
  \draw[green, thick] (3.4,{0.42*(3.4-1.4)*(3.4+0.6)}) -- (2.05,0);
  \fill[black] (2.05,0) circle (1.4pt);
  \node[anchor=north, font=\footnotesize] at (2.05,-0.1) {$x_{t+1}$};
  \node[green, anchor=south west, font=\footnotesize] at (2.5,1.0) {tangent};
\end{tikzpicture}
$$

::impl{algo="newton_raphson"}

Newton–Raphson is fast but **fragile**: a near-zero derivative sends the tangent nearly
horizontal and flings the next guess far away, and a bad start may not converge at all. When
robustness matters more than speed, use **bisection**. If $g$ is continuous and changes sign
across an interval $[a,b]$ — that is, $g(a)$ and $g(b)$ have opposite signs — the intermediate
value theorem guarantees a root inside. Test the midpoint, keep the half-interval that still
**brackets** the sign change, and repeat. The bracket halves every step.

$$
% caption: Bisection maintains a sign-changing bracket $[a,b]$; testing the midpoint $m$ keeps
%          the half that still brackets the root, halving the interval each step.
\begin{tikzpicture}[
  every node/.style={font=\small},
  >=stealth, scale=1.0]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1A8F4C}
  \definecolor{red}{HTML}{C0392B}
  % number line
  \draw[thick] (-3.2,0) -- (3.2,0);
  % the true root
  \fill[green] (0.5,0) circle (1.8pt);
  \node[green, anchor=south, font=\footnotesize] at (0.5,0.14) {ro\/ot};
  % step 1 bracket a..b
  \draw[acc, very thick] (-3.0,-0.7) -- (3.0,-0.7);
  \fill[acc] (-3.0,-0.7) circle (1.6pt) node[below, font=\footnotesize, black] {$a$};
  \fill[acc] (3.0,-0.7) circle (1.6pt) node[below, font=\footnotesize, black] {$b$};
  \fill[red] (0.0,-0.7) circle (1.5pt) node[above, font=\footnotesize, black] {$m$};
  % step 2: kept right half (root in [m,b])
  \draw[acc, very thick] (0.0,-1.5) -- (3.0,-1.5);
  \fill[acc] (0.0,-1.5) circle (1.6pt);
  \fill[acc] (3.0,-1.5) circle (1.6pt);
  \fill[red] (1.5,-1.5) circle (1.5pt) node[above, font=\footnotesize, black] {$m$};
  % step 3: kept left half (root in [m_prev, m])
  \draw[acc, very thick] (0.0,-2.3) -- (1.5,-2.3);
  \fill[acc] (0.0,-2.3) circle (1.6pt);
  \fill[acc] (1.5,-2.3) circle (1.6pt);
  \node[anchor=west, font=\footnotesize] at (3.3,-1.5) {hal\/ve eac\/h step};
\end{tikzpicture}
$$

::impl{algo="bisection"}

Bisection converges **linearly** — one bit of accuracy per step, $O(\log\tfrac{b-a}{\epsilon})$
steps to width $\epsilon$ — slower than Newton's quadratic doubling, but it cannot fail on a
continuous sign-changing function. It is, in disguise, the **monotone binary search** behind
the discrete answer-search problems _Koko Eating Bananas_ and _Minimize Max Distance to Gas
Station_: a feasibility predicate is monotone in the answer, so bracket the threshold and halve.
The robust strategy in practice is **hybrid** — Newton steps when they stay inside the bracket,
a bisection step as a safe fallback when they do not.[^skiena-opt]

## Modern optimizers and neural-network training

The optimizers that actually train modern models are refinements of plain
gradient descent.

**Momentum and adaptive rates.** The zig-zag down a long thin valley (large
condition number $\kappa$) is the central weakness of vanilla gradient descent.
**Momentum** damps it by accumulating a velocity, $v_{t+1} = \beta v_t +
\nabla f(x_t)$, $x_{t+1} = x_t - \eta v_{t+1}$, so consistent directions build speed
while oscillating ones cancel; **Nesterov's accelerated gradient** sharpens this to
the optimal $O(1/t^2)$ rate for smooth convex $f$, a provable improvement over the
$O(1/t)$ derived above.[^nesterov] **Adaptive** methods — AdaGrad, RMSProp, and
especially **Adam** — give each coordinate its own effective step size from a running
estimate of gradient magnitudes, which is why Adam is the default optimizer for deep
networks.[^adam] All of them are still $x_{t+1} = x_t - (\text{step})$; only the step
changes.

**Backpropagation is the chain rule.** Training a neural network minimizes a loss
$f(x)$ over millions of parameters $x$, and gradient descent needs $\nabla f$. The
gradient is computed by **backpropagation** — the multivariate chain rule applied in
reverse across the network's computation graph — which yields all partial derivatives
in a single backward pass costing the same order as one forward evaluation. This is
**reverse-mode automatic differentiation**, and it is what makes gradient descent
tractable in millions of dimensions where forming the Hessian for Newton's method
(the $\Theta(n^3)$ cost above) is infeasible.[^rumelhart]

**Non-convex reality.** The clean "local is global" guarantee holds only for convex
$f$; neural-network losses are highly non-convex. Several
empirical facts explain why training still works: in very high dimension most critical points are **saddles**, not bad
local minima, and the stochastic noise of SGD helps the iterate slip off them; and
the many minima that do exist tend to have similar loss values, so finding _a_ good
one suffices. Understanding why first-order methods succeed on non-convex deep
networks remains an active research question, but the working answer — SGD plus
momentum plus a well-tuned schedule — trains essentially every model in use today.

## Takeaways

- **Continuous optimization** minimizes a differentiable $f$ over $\mathbb{R}^n$ with calculus,
  not enumeration. The **gradient** $\nabla f$ is the steepest-ascent direction and is
  orthogonal to level sets; its negation points downhill.
- **Gradient descent** iterates $x_{t+1}=x_t-\eta\nabla f(x_t)$. The **learning rate** $\eta$ is
  the one critical parameter: too small is slow, too large overshoots and diverges.
- **Convexity** makes every local minimum global, so "descend until flat" finds the true
  optimum. For convex $L$-smooth $f$ the rate is $O(1/t)$; under $\mu$-strong convexity it is
  **geometric**, $O(\kappa\log\tfrac{1}{\epsilon})$ steps with $\kappa=L/\mu$.
- **Stochastic gradient descent** estimates $\nabla f$ from a random mini-batch — far cheaper,
  noisier steps; the noise/speed trade-off and step decay make it the standard method for
  neural-network training.
- **Newton's method** uses the Hessian for **quadratic** local convergence but costs
  $\Theta(n^3)$ per step; in 1-D it is **Newton–Raphson** root-finding, with **bisection** the
  robust linear-time bracketing fallback.[^skiena-opt]

[^skiena-opt]: **Skiena**, § — Numerical Problems / Optimization, and **CLRS**, Ch. — Newton's method for root-finding: gradient descent, Newton–Raphson, and bisection, and the trade-off between fast-but-fragile and slow-but-robust convergence.
[^nesterov]: Y. Nesterov, "A method of solving a convex programming problem with convergence rate $O(1/k^2)$," _Soviet Mathematics Doklady_ **27**, 1983; and Nesterov, _Introductory Lectures on Convex Optimization_, Springer, 2004.
[^adam]: D. P. Kingma and J. Ba, "Adam: A method for stochastic optimization," _ICLR_ 2015; J. Duchi, E. Hazan, Y. Singer, "Adaptive subgradient methods," _JMLR_ **12**, 2011 (AdaGrad).
[^rumelhart]: D. E. Rumelhart, G. E. Hinton, R. J. Williams, "Learning representations by back-propagating errors," _Nature_ **323**, 1986 — backpropagation as reverse-mode differentiation for training neural networks.