> ## Documentation Index
> Fetch the complete documentation index at: https://aegean.ai/llms.txt
> Use this file to discover all available pages before exploring further.

# Diffusion as a gradient flow

> Diffusion as steepest descent of a free energy in Wasserstein space.

[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/pantelis/eng-ai-agents/blob/main/notebooks/diffusion/gradient-flow/gradient_flow.ipynb)

## Free energy as the selecting principle

The [Fokker-Planck section](https://aegean.ai/aiml-common/lectures/diffusion/fokker-planck/fokker_planck.md) measured the Ornstein-Uhlenbeck density path and found that it is not the geodesic between its endpoints. Its normalized action $\bar{\mathcal{A}}$ is almost four times $W_2^2(p_0, p_T)$, so least action does not select it. This section names the principle that does: the path descends a free energy as steeply as the Wasserstein geometry allows.

You first see this on Gaussians, where the geometry is an ordinary plane and the descent can be drawn. The same statement then carries over to all densities on the line, where it can be solved one implicit step at a time.

The running example is the one of the Fokker-Planck section: the three-component mixture $p_0$, the forward process $dX_t = -X_t\,dt + \sqrt{2}\,dW_t$, and the horizon $T = 4$. The density $p_t$ is a closed-form mixture, and the score is a responsibility-weighted sum of component scores. Free energies, actions and Fisher information come from quadrature, the Gaussian gradient flow from an ordinary differential equation solver, and the implicit steps from numerical optimization.

```python theme={null}
import numpy as np
import matplotlib.pyplot as plt
from scipy.special import logsumexp
from scipy.stats import norm

# p_0 is the phase 1 Gaussian mixture. The forward process is dX = -X dt + sqrt(2) dW, so D = 1.
PI = np.array([0.3, 0.5, 0.2])
MU = np.array([-2.0, 1.0, 3.5])
SIGMA = np.array([0.4, 0.6, 0.3])
U_CLIP = 1e-12  # quantile levels are clipped to [U_CLIP, 1 - U_CLIP]


def mixture_pdf(x, pi=PI, mu=MU, sigma=SIGMA):
    x = np.asarray(x, dtype=float)[..., None]
    return np.sum(pi * norm.pdf(x, mu, sigma), axis=-1)


def mixture_cdf(x, pi=PI, mu=MU, sigma=SIGMA):
    x = np.asarray(x, dtype=float)[..., None]
    return np.sum(pi * norm.cdf(x, mu, sigma), axis=-1)


def mixture_ppf(u, pi=PI, mu=MU, sigma=SIGMA, iters=64):
    """Quantile function F_1^{-1}(u) by vectorized bisection on the mixture CDF.

    The root lies between the smallest and the largest component quantile at level u.
    """
    u = np.clip(np.asarray(u, dtype=float), U_CLIP, 1 - U_CLIP)
    q = mu + sigma * norm.ppf(u)[..., None]
    lo, hi = q.min(axis=-1), q.max(axis=-1)
    for _ in range(iters):
        mid = 0.5 * (lo + hi)
        below = mixture_cdf(mid, pi, mu, sigma) < u
        lo = np.where(below, mid, lo)
        hi = np.where(below, hi, mid)
    return 0.5 * (lo + hi)


def ou_components(t, pi=PI, mu=MU, sigma=SIGMA):
    """Weights, means mu e^{-t} and standard deviations of the components of p_t."""
    pi, mu, sigma = (np.asarray(a, dtype=float) for a in (pi, mu, sigma))
    decay = np.exp(-t)
    return pi, mu * decay, np.sqrt(sigma**2 * decay**2 + 1 - decay**2)


def p_t(x, t, **mix):
    """Density of the Ornstein-Uhlenbeck process at time t, started from the mixture."""
    return mixture_pdf(x, *ou_components(t, **mix))


def score(x, t, **mix):
    """d/dx log p_t, a responsibility-weighted sum of component scores (log-sum-exp weights).

    Never computed as (dp/dx) / p, so it stays finite far in the tails.
    """
    pi, m, s = ou_components(t, **mix)
    x = np.asarray(x, dtype=float)[..., None]
    log_w = np.log(pi) + norm.logpdf(x, m, s)
    resp = np.exp(log_w - logsumexp(log_w, axis=-1, keepdims=True))
    return np.sum(resp * (-(x - m) / s**2), axis=-1)


def velocity(x, t, **mix):
    """Probability flow velocity v_t(x) = f(x) - D d/dx log p_t(x) with f(x) = -x, D = 1."""
    return -np.asarray(x, dtype=float) - score(x, t, **mix)


def quantile_t(u, t, **mix):
    """F_t^{-1}(u), the quantile function of p_t."""
    return mixture_ppf(u, *ou_components(t, **mix))


def w2_squared_between(qa, qb):
    """Mean of squared quantile differences, for quantiles on a midpoint u grid."""
    return float(np.mean((np.asarray(qa) - np.asarray(qb)) ** 2))


# Horizon T from the contraction bound W_2(p_t, N(0, 1)) <= e^{-t} W_2(p_0, N(0, 1)).
U_MID = (np.arange(20000) + 0.5) / 20000   # midpoint grid on (0, 1)


def w2_to_gaussian(t, **mix):
    """W_2(p_t, N(0, 1)) from quantile functions."""
    return np.sqrt(w2_squared_between(quantile_t(U_MID, t, **mix), norm.ppf(U_MID)))


def bound(t, **mix):
    """Contraction bound e^{-t} W_2(p_0, N(0, 1))."""
    return np.exp(-t) * w2_to_gaussian(0.0, **mix)


T_TOL = 0.05
T = float(next(n for n in range(1, 50) if bound(n) < T_TOL))   # smallest whole-number horizon
```

```python theme={null}
print(f"horizon T = {T:g}   contraction bound at T {bound(T):.4f}   computed W_2(p_T, N(0, 1)) {w2_to_gaussian(T):.4f}")
```

```output theme={null}
horizon T = 4   contraction bound at T 0.0225   computed W_2(p_T, N(0, 1)) 0.0110
```

## Gradient descent and its implicit step

Gradient flow moves a point $z$ downhill on a function $E$ with $\dot z = -\nabla E(z)$. Its implicit Euler step with time step $\tau$ is

$$
z_{k+1} = \arg\min_z \; E(z) + \frac{\lVert z - z_k \rVert^2}{2\tau} .
$$

Setting the gradient of the right side to zero gives $(z_{k+1} - z_k)/\tau = -\nabla E(z_{k+1})$, the backward Euler update. The minimization uses only the function and the distance, so the step can be written on any space that has a distance, including a space of probability densities with the distance $W_2$.

| Euclidean space | Densities with $W_2$ |
| - | - |
| point $z$ | density $p$ |
| function $E(z)$ | functional $\mathcal{F}(p)$ |
| distance $\lVert z - z' \rVert$ | distance $W_2(p, p')$ |
| gradient flow | Wasserstein gradient flow |
| implicit (proximal) step | JKO step |

## Gaussians as a plane

For two Gaussians on the line the Wasserstein distance has a closed form,

$$
\begin{aligned}
&W_2^2\bigl(\mathcal{N}(m_1, \sigma_1^2), \mathcal{N}(m_2, \sigma_2^2)\bigr) \\
&\quad = (m_1 - m_2)^2 + (\sigma_1 - \sigma_2)^2 .
\end{aligned}
$$

The family of Gaussians is therefore the half plane of points $(m, \sigma)$ with $\sigma > 0$, and $W_2$ is the ordinary Euclidean distance in that plane. Geodesics are straight segments.

Take as free energy the KL divergence to the standard normal $\gamma = \mathcal{N}(0, 1)$. On Gaussians it is

$$
\mathcal{F}(m, \sigma) = \tfrac12 \bigl(m^2 + \sigma^2 - 1 - 2 \log \sigma\bigr) ,
$$

with its minimum $0$ at $(0, 1)$. The gradient is $(m, \sigma - 1/\sigma)$, so the gradient flow in the plane is

$$
\dot m = -m, \qquad \dot \sigma = \frac{1}{\sigma} - \sigma .
$$

Its solution is $m_t = m_0 e^{-t}$ and $\sigma_t = \sqrt{1 + (\sigma_0^2 - 1) e^{-2t}}$. These are the mean and the standard deviation of the Ornstein-Uhlenbeck process started from $\mathcal{N}(m_0, \sigma_0^2)$, whose variance is $\sigma_0^2 e^{-2t} + 1 - e^{-2t}$. The process maps Gaussians to Gaussians, so on this family it is the gradient flow of the KL divergence in the plane.

To check this, the gradient flow is integrated numerically from $(m_0, \sigma_0) = (2.5, 0.3)$ over $[0, T]$ and compared with the closed-form Ornstein-Uhlenbeck moments.

```python theme={null}
from scipy.integrate import solve_ivp


def gaussian_free_energy(m, s):
    """KL(N(m, s^2) || N(0, 1)) = (m^2 + s^2 - 1 - 2 log s) / 2."""
    return 0.5 * (m**2 + s**2 - 1 - 2 * np.log(s))


def gaussian_flow(m0, s0, t):
    """Closed-form mean and standard deviation of the Ornstein-Uhlenbeck process from N(m0, s0^2)."""
    return m0 * np.exp(-t), np.sqrt(1 + (s0**2 - 1) * np.exp(-2 * t))


def minus_grad_free_energy(t, z):
    """Right-hand side of the gradient flow in the (m, s) plane: -grad F = (-m, 1/s - s)."""
    m, s = z
    return [-m, 1 / s - s]


M0, S0 = 2.5, 0.3
T_PLANE = np.linspace(0, T, 401)
sol = solve_ivp(minus_grad_free_energy, (0, T), [M0, S0], t_eval=T_PLANE,
                method="DOP853", rtol=1e-12, atol=1e-12)
num_flow = sol.y.T                                           # integrated gradient flow
closed_flow = np.stack(gaussian_flow(M0, S0, T_PLANE), axis=1)  # Ornstein-Uhlenbeck mean and std
print(f"largest |integrated gradient flow - Ornstein-Uhlenbeck (m_t, s_t)| on [0, T]: "
      f"{np.max(np.abs(num_flow - closed_flow)):.1e}")
```

```output theme={null}
largest |integrated gradient flow - Ornstein-Uhlenbeck (m_t, s_t)| on [0, T]: 3.8e-12
```

```python theme={null}
# Gaussian plane: integrating the gradient of F reproduces the OU mean and std
assert np.max(np.abs(num_flow - closed_flow)) < 1e-6
```

The two agree to the tolerance of the integrator.

The plane also shows the difference between a gradient flow and a geodesic. Both paths start at $z_0 = (m_0, \sigma_0)$ and end at the Ornstein-Uhlenbeck point $z_T = (m_T, \sigma_T)$. The geodesic is the straight segment traversed at constant speed, and its normalized action is $\lVert z_T - z_0 \rVert^2$. Along the gradient flow, $\frac{d}{dt}\mathcal{F}(z_t) = \nabla \mathcal{F} \cdot \dot z = -\lVert \dot z \rVert^2$, so its action in physical time equals the drop $\mathcal{F}(z_0) - \mathcal{F}(z_T)$. The normalized action is $T$ times that, as in the Fokker-Planck section.

```python theme={null}
mT, sT = gaussian_flow(M0, S0, T)
z0, zT = np.array([M0, S0]), np.array([mT, sT])


def plane_geodesic(t):
    """Constant-speed straight line from (m_0, s_0) at t = 0 to (m_T, s_T) at t = T."""
    return z0 + (np.asarray(t)[..., None] / T) * (zT - z0)


# Action in physical time: integral of |dz/dt|^2. Along the flow dz/dt = -grad F exactly.
t_fine = T * np.linspace(0, 1, 4001) ** 2                    # denser near t = 0
m_f, s_f = gaussian_flow(M0, S0, t_fine)
plane_A_flow = np.trapezoid(m_f**2 + (1 / s_f - s_f) ** 2, t_fine)
plane_dF = gaussian_free_energy(M0, S0) - gaussian_free_energy(mT, sT)
plane_W2_sq = float(np.sum((zT - z0) ** 2))                  # normalized action of the straight line
print(f"flow:     T x action = {T * plane_A_flow:.4f}   (action {plane_A_flow:.4f}, F(z_0) - F(z_T) = {plane_dF:.4f})")
print(f"geodesic: T x action = {plane_W2_sq:.4f}   (= |z_T - z_0|^2 = W_2^2)")
print("KL to N(0, 1) along each path:")
for t in (0.0, 0.25, 0.5, 1.0, 2.0, T):
    kl_f = gaussian_free_energy(*gaussian_flow(M0, S0, t))
    kl_g = gaussian_free_energy(*plane_geodesic(t))
    print(f"  t = {t:4.2f}   flow {kl_f:.4f}   geodesic {kl_g:.4f}")
```

```output theme={null}
flow:     T x action = 15.4917   (action 3.8729, F(z_0) - F(z_T) = 3.8729)
geodesic: T x action = 6.5129   (= |z_T - z_0|^2 = W_2^2)
KL to N(0, 1) along each path:
  t = 0.00   flow 3.8740   geodesic 3.8740
  t = 0.25   flow 2.0209   geodesic 3.3802
  t = 0.50   flow 1.1860   geodesic 2.9283
  t = 1.00   flow 0.4271   geodesic 2.1367
  t = 2.00   flow 0.0573   geodesic 0.9522
  t = 4.00   flow 0.0010   geodesic 0.0010
```

![Contour plot of the free energy in the plane of mean and standard deviation, with closed level curves around the point (0, 1). A solid blue curve runs from the start at (2.5, 0.3) up and to the left, reaching a standard deviation near 1 by mean 1 and then running almost horizontally to the end point near (0.05, 1). A dashed orange straight line joins the same two points. Circle, square and triangle markers at times 0.5, 1 and 2 sit much farther along the blue curve than along the orange line.](https://mintcdn.com/aegeanaiinc/_3YkDHya7LTDeZHX/aiml-common/lectures/diffusion/gradient-flow/images/cell_7_output_1.png?fit=max\&auto=format\&n=_3YkDHya7LTDeZHX\&q=85\&s=79e8a359c77087dbb96baff197a8769c)

*Level sets of the free energy in the plane of Gaussians. The solid curve is the gradient flow from $(2.5, 0.3)$, the dashed line the geodesic to the same endpoint. Markers of the same shape mark the same time on both paths.*

The gradient flow crosses each level set at a right angle, which is what steepest descent means in a Euclidean plane. At the start its direction is steeper than that of the geodesic: the standard deviation grows at $3.0$ per unit time while the mean falls at $2.5$. By $t = 1$ the flow has $\sigma_t = 0.94$ and from then on it mostly moves the mean. The geodesic changes both at a constant rate. The flow has a lower KL at every printed time between the endpoints: $1.19$ against $2.93$ at $t = 0.5$, and $0.057$ against $0.95$ at $t = 2$. It pays for that with a normalized action of $15.49$, more than twice the $6.51$ of the straight line.

## Free energy on densities

The free energy of a density $p$ on the line is the KL divergence to $\gamma$,

$$
\begin{aligned}
\mathcal{F}(p) &= \int p \log p\,dx + \int \frac{x^2}{2}\,p\,dx + \log\sqrt{2\pi} \\
&= D_{\mathrm{KL}}(p \,\|\, \gamma) .
\end{aligned}
$$

The first term is the negative entropy and the second a potential energy. The constant $\log \sqrt{2\pi}$ has no effect on the flow. For a Gaussian, $\mathcal{F}$ reduces to the formula of the plane.

In one dimension the quantile function $Q = F^{-1}$ turns all three ingredients into simple integrals over $u \in (0, 1)$. Substitute $x = Q(u)$. Then $p(Q(u))\,Q'(u) = 1$ and $p\,dx = du$, so

$$
\begin{aligned}
\int p \log p\,dx &= -\int_0^1 \log Q'(u)\,du , \\
\int \frac{x^2}{2}\,p\,dx &= \int_0^1 \frac{Q(u)^2}{2}\,du , \\
W_2^2(p, q) &= \int_0^1 \bigl(Q_p - Q_q\bigr)^2 du .
\end{aligned}
$$

The last line says that $W_2$ is the ordinary $L^2$ distance between quantile functions. A Wasserstein gradient flow on the line is therefore an ordinary $L^2$ gradient flow of $\mathcal{F}$, written as a functional of $Q$ on the set of increasing functions (Santambrogio, 2015). The plane of Gaussians is the special case $Q(u) = m + \sigma\,\Phi^{-1}(u)$, with $\Phi$ the standard normal CDF.

The same flow can be written on the density. The first variation of $\mathcal{F}$ is $\log p + x^2/2 + 1$. A Wasserstein gradient flow moves mass with the velocity $v = -\partial_x$ of the first variation, so

$$
v_t(x) = -\partial_x\Bigl(\log p_t + \frac{x^2}{2}\Bigr) = -x - \partial_x \log p_t .
$$

This is the probability flow velocity of the Fokker-Planck section. The continuity equation $\partial_t p_t + \partial_x(p_t v_t) = 0$ with this velocity is $\partial_t p_t = \partial_x(x\,p_t) + \partial_x^2 p_t$, the Fokker-Planck equation of the Ornstein-Uhlenbeck process. The density path of diffusion is the Wasserstein gradient flow of the KL divergence to its equilibrium.

All quantile computations on this page use one grid of levels. The levels are $u_i = \Phi(z_i)$ with $z_i$ equally spaced, which puts more levels in the tails. On that grid, $Q'$ is the finite difference on each interval and the integrals use the trapezoid rule.

```python theme={null}
LOG_SQRT_2PI = 0.5 * np.log(2 * np.pi)
U_MIN, N_U = 1e-8, 400


def quantile_grid(n_u=N_U, u_min=U_MIN):
    """Quantile levels u_i = Phi(z_i) with z_i equally spaced, from u_min to 1 - u_min."""
    z_max = -norm.ppf(u_min)
    return norm.cdf(np.linspace(-z_max, z_max, n_u))


def trapezoid_weights(u):
    """Weights w_i so that sum_i w_i g(u_i) is the trapezoid rule for the integral of g over u."""
    du = np.diff(u)
    w = np.zeros_like(u)
    w[:-1] += du / 2
    w[1:] += du / 2
    return w


def free_energy_quantile(Q, u):
    """F = -int log Q'(u) du + int Q(u)^2 / 2 du + log sqrt(2 pi), on the grid u.

    Q' is the finite difference on each interval, so the spacings of Q must be positive.
    """
    du = np.diff(u)
    return float(-np.sum(du * np.log(np.diff(Q) / du))
                 + np.sum(trapezoid_weights(u) * Q**2 / 2) + LOG_SQRT_2PI)


X_F = np.linspace(-12, 12, 24001)


def log_p_t(x, t, **mix):
    """log p_t(x) by log-sum-exp over the components."""
    pi, m, s = ou_components(t, **mix)
    x = np.asarray(x, dtype=float)[..., None]
    return logsumexp(np.log(pi) + norm.logpdf(x, m, s), axis=-1)


def kl_to_gaussian(t, **mix):
    """F(p_t) = KL(p_t || N(0, 1)) = int p log p + int x^2/2 p + log sqrt(2 pi), quadrature on [-12, 12]."""
    lp = log_p_t(X_F, t, **mix)
    p = np.exp(lp)
    return float(np.trapezoid(p * (lp + X_F**2 / 2), X_F) + LOG_SQRT_2PI)


U_GRID = quantile_grid()
print(f"quantile grid: N_U = {N_U} levels, u_min = {U_GRID[0]:.1e}, 1 - u_max = {1 - U_GRID[-1]:.1e}")
for t in (0.0, 1.0):
    print(f"t = {t:g}: F(p_t) from the quantile form {free_energy_quantile(quantile_t(U_GRID, t), U_GRID):.5f}"
          f"   from x quadrature {kl_to_gaussian(t):.5f}")
```

```output theme={null}
quantile grid: N_U = 400 levels, u_min = 1.0e-08, 1 - u_max = 1.0e-08
t = 0: F(p_t) from the quantile form 1.44292   from x quadrature 1.44842
t = 1: F(p_t) from the quantile form 0.05853   from x quadrature 0.05839
```

```python theme={null}
# quantile ends stay finite on the JKO grid
assert np.all(np.isfinite(quantile_t(U_GRID[[0, -1]], 0.0)))
```

At $t = 0$ the quantile form of $\mathcal{F}$ is about $5 \times 10^{-3}$ below the integral in $x$, because the narrow components and the gaps between them are hardest to resolve. The error falls when the grid is refined (see the numerical checks).

## Dissipation equals action

Along the flow the free energy falls at a rate fixed by the velocity. Differentiate $\mathcal{F}(p_t)$ in time, substitute the continuity equation, and integrate by parts:

$$
\begin{aligned}
\frac{d}{dt}\mathcal{F}(p_t)
&= \int \partial_t p_t \Bigl(\log p_t + \frac{x^2}{2} + 1\Bigr) dx \\
&= \int p_t\,v_t\,\partial_x\Bigl(\log p_t + \frac{x^2}{2}\Bigr) dx \\
&= -\int p_t\,v_t^2\,dx .
\end{aligned}
$$

Since $v_t = -\partial_x \log(p_t/\gamma)$, the last integral is the relative Fisher information $I(p_t \,\|\, \gamma) = \int p_t\,\lvert \partial_x \log(p_t/\gamma) \rvert^2\,dx$. Integrating from $0$ to $T$ gives

$$
\mathcal{F}(p_0) - \mathcal{F}(p_T) = \int_0^T \!\! \int p_t\,v_t^2\,dx\,dt = \mathcal{A} ,
$$

the physical-time action of the Fokker-Planck section. The Benamou-Brenier formula bounds $W_2^2$ by the normalized action $\bar{\mathcal{A}} = T\mathcal{A}$ (Benamou & Brenier, 2000), so

$$
W_2^2(p_0, p_T) \le T\,\bigl[\mathcal{F}(p_0) - \mathcal{F}(p_T)\bigr] .
$$

Numerically, $\mathcal{F}(p_t)$ comes from quadrature on $[-12, 12]$ with $\log p_t$ computed by log-sum-exp. Its time derivative comes from central differences with step $10^{-4}$, at 41 times in $[0.01, T]$, and is compared with the Fisher information computed from the exact velocity. The action integrates the Fisher information over 801 times, spaced more densely near $t = 0$.

```python theme={null}
def fisher(t, **mix):
    """Relative Fisher information I(p_t || N(0, 1)) = int p_t v_t^2 dx, quadrature on [-12, 12]."""
    return float(np.trapezoid(p_t(X_F, t, **mix) * velocity(X_F, t, **mix) ** 2, X_F))


H_FD = 1e-4
T_DISS = np.linspace(0.01, T, 41)
dFdt_numeric = np.array([(kl_to_gaussian(t + H_FD) - kl_to_gaussian(t - H_FD)) / (2 * H_FD) for t in T_DISS])
fisher_vals = np.array([fisher(t) for t in T_DISS])
F0, FT = kl_to_gaussian(0.0), kl_to_gaussian(T)
T_A = T * np.linspace(0, 1, 801) ** 2                         # times, denser near t = 0
A = float(np.trapezoid([fisher(t) for t in T_A], T_A))        # physical-time action, full real line
U_W = (np.arange(20000) + 0.5) / 20000
W2_sq = w2_squared_between(quantile_t(U_W, 0.0), quantile_t(U_W, T))
print(f"largest |dF/dt (differences) + I(p_t || N(0, 1))| over {len(T_DISS)} times: "
      f"{np.max(np.abs(dFdt_numeric + fisher_vals)):.1e}")
print(f"F(p_0) - F(p_T) = {F0 - FT:.4f}   A = {A:.4f}   relative difference {abs(F0 - FT - A) / A:.1e}")
print(f"W_2^2(p_0, p_T) = {W2_sq:.4f} <= T [F(p_0) - F(p_T)] = {T * (F0 - FT):.4f}")
```

```output theme={null}
largest |dF/dt (differences) + I(p_t || N(0, 1))| over 41 times: 2.5e-06
F(p_0) - F(p_T) = 1.4484   A = 1.4484   relative difference 1.1e-05
W_2^2(p_0, p_T) = 1.5008 <= T [F(p_0) - F(p_T)] = 5.7934
```

```python theme={null}
# the Fokker-Planck page truncated its quantile integrals to u in [0.001, 0.999]; same range here
U_LO, U_HI = 0.001, 0.999


def fisher_truncated(t, n_x=4001):
    x = np.linspace(*quantile_t(np.array([U_LO, U_HI]), t), n_x)
    return np.trapezoid(p_t(x, t) * velocity(x, t) ** 2, x)


A_trunc = float(np.trapezoid([fisher_truncated(t) for t in T_A], T_A))
U_TR = U_LO + (U_HI - U_LO) * (np.arange(1000) + 0.5) / 1000
W2_sq_trunc = (U_HI - U_LO) * w2_squared_between(quantile_t(U_TR, T), quantile_t(U_TR, 0.0))
print(f"on u in [{U_LO}, {U_HI}]: A = {A_trunc:.4f}   W_2^2 = {W2_sq_trunc:.4f}")
```

```output theme={null}
on u in [0.001, 0.999]: A = 1.4454   W_2^2 = 1.4998
```

```python theme={null}
# dissipation: dF/dt = -int p v^2, pointwise in t and integrated
assert np.max(np.abs(dFdt_numeric - (-fisher_vals))) < 1e-4
assert abs((F0 - FT) - A) < 1e-4 * A
assert W2_sq <= T * (F0 - FT) + 1e-9
```

The rate of change of $\mathcal{F}$ matches the Fisher information at every time, and the drop $\mathcal{F}(p_0) - \mathcal{F}(p_T) = 1.4484$ matches the action to five digits. The Fokker-Planck section reported $\mathcal{A} = 1.4454$ and $W_2^2 = 1.4998$ because it restricted the $u$ integrals to $[0.001, 0.999]$. On that same range the computation here gives the same two numbers. Over the whole line the tails add $0.003$ to $\mathcal{A}$ and $0.001$ to $W_2^2$. The bound holds with room to spare: $1.50 \le 5.79$. The difference between the two sides is the excess action $\bar{\mathcal{A}} - W_2^2$ of the Fokker-Planck section.

## The JKO step

The implicit step of the first table, written with $\mathcal{F}$ and $W_2$, is the JKO step (Jordan et al., 1998):

$$
p_{k+1} = \arg\min_p \; \mathcal{F}(p) + \frac{W_2^2(p, p_k)}{2\tau} .
$$

Jordan, Kinderlehrer and Otto proved that as $\tau \to 0$ these steps converge to the solution of the Fokker-Planck equation. Each step trades a lower free energy against the cost of moving mass, without using a velocity or a score.

On the line the step is a minimization over quantile functions,

$$
\begin{aligned}
Q_{k+1} = \arg\min_Q \; & -\int_0^1 \log Q'\,du + \int_0^1 \frac{Q^2}{2}\,du \\
& + \frac{1}{2\tau} \int_0^1 (Q - Q_k)^2\,du .
\end{aligned}
$$

Every experiment uses the same discretization on the grid above. The unknowns are $Q(u_0)$ and the logarithms of the spacings $Q(u_{i+1}) - Q(u_i)$, so the computed $Q$ is increasing by construction. In these variables the entropy term is linear. The minimization uses L-BFGS with the exact gradient, warm-started from the previous step. The error of step $k$ is the $W_2$ distance on the grid between $Q_k$ and the exact quantile function at time $k\tau$.

The first test starts from the Gaussian $(m_0, \sigma_0) = (2.5, 0.3)$, where the exact answer is $(m_t, \sigma_t)$ from the plane. It runs to $T$ with $\tau = 0.1$ and $\tau = 0.05$.

```python theme={null}
from scipy.optimize import minimize

TAUS = (0.1, 0.05)
JKO_TOL = 1e-12        # ftol and gtol of the optimizer


def jko_step(Q_prev, u, tau, tol=JKO_TOL, return_result=False):
    """One JKO step on quantile functions: argmin_Q F(Q) + sum_i w_i (Q_i - Q_prev_i)^2 / (2 tau).

    The variables are Q(u_0) and the logs of the spacings Q_{i+1} - Q_i, so Q is increasing
    by construction. The entropy term is linear in the log-spacings.
    """
    du, w = np.diff(u), trapezoid_weights(u)

    def unpack(y):
        return y[0] + np.concatenate([[0.0], np.cumsum(np.exp(y[1:]))])

    def objective(y):
        Q = unpack(y)
        J = (-np.sum(du * (y[1:] - np.log(du))) + np.sum(w * Q**2) / 2
             + np.sum(w * (Q - Q_prev) ** 2) / (2 * tau) + LOG_SQRT_2PI)
        g = w * Q + w * (Q - Q_prev) / tau                    # dJ/dQ_i
        tail = np.cumsum(g[::-1])[::-1]                       # tail[i] = sum over k >= i of g_k
        grad = np.empty_like(y)
        grad[0] = tail[0]
        grad[1:] = np.exp(y[1:]) * tail[1:] - du
        return J, grad

    y0 = np.concatenate([[Q_prev[0]], np.log(np.diff(Q_prev))])
    res = minimize(objective, y0, jac=True, method="L-BFGS-B",
                   options=dict(ftol=tol, gtol=tol, maxiter=50000, maxcor=30))
    return (unpack(res.x), res) if return_result else unpack(res.x)


def w2_on_grid(Qa, Qb, u):
    """W_2 between two quantile functions on the grid u (trapezoid rule)."""
    return float(np.sqrt(np.sum(trapezoid_weights(u) * (Qa - Qb) ** 2)))


def run_jko(Q_init, u, tau, exact_quantile, tol=JKO_TOL):
    """JKO steps over [0, T]. Returns the iterates, the W_2 error of each, and the optimizer results."""
    Qs, errors, results = [Q_init], [], []
    for k in range(1, int(round(T / tau)) + 1):
        Q, res = jko_step(Qs[-1], u, tau, tol, return_result=True)
        Qs.append(Q)
        results.append(res)
        errors.append(w2_on_grid(Q, exact_quantile(k * tau, u), u))
    return np.array(Qs), np.array(errors), results


def step_density(Q, u, x):
    """Density of a piecewise-linear quantile function, Delta u / Delta Q, interpolated at x."""
    return np.interp(x, 0.5 * (Q[1:] + Q[:-1]), np.diff(u) / np.diff(Q))


def gaussian_quantile(t, u):
    m, s = gaussian_flow(M0, S0, t)
    return m + s * norm.ppf(u)


jko_gauss_err, jko_gauss_err_end, jko_results = {}, {}, []
for tau in TAUS:
    _, errs, results = run_jko(gaussian_quantile(0.0, U_GRID), U_GRID, tau, gaussian_quantile)
    jko_gauss_err[tau], jko_gauss_err_end[tau] = errs.max(), errs[-1]
    jko_results += results
    print(f"Gaussian start, tau = {tau:<4g}: largest W_2 error over the steps {errs.max():.4f} (step at t = {(np.argmax(errs) + 1) * tau:g})   at t = T {errs[-1]:.1e}")
```

```output theme={null}
Gaussian start, tau = 0.1 : largest W_2 error over the steps 0.0510 (step at t = 0.5)   at t = T 9.5e-03
```

```output theme={null}
Gaussian start, tau = 0.05: largest W_2 error over the steps 0.0269 (step at t = 0.35)   at t = T 4.7e-03
```

```python theme={null}
# JKO on a Gaussian start: error against gaussian_flow shrinks with tau
assert jko_gauss_err[TAUS[1]] < jko_gauss_err[TAUS[0]]          # TAUS = (0.1, 0.05)
```

Halving $\tau$ halves the largest error, from $0.051$ to $0.027$. This is the first-order accuracy of an implicit Euler step. At both time steps the largest error occurs within the first half unit of time, where the narrow start widens fastest.

The same steps then run from the mixture $p_0$, and each step is compared with the exact $p_{k\tau}$.

```python theme={null}
jko_mix_Q, jko_mix_w2 = {}, {}
for tau in TAUS:
    jko_mix_Q[tau], jko_mix_w2[tau], results = run_jko(quantile_t(U_GRID, 0.0), U_GRID, tau,
                                                       lambda t, u: quantile_t(u, t))
    jko_results += results
    print(f"mixture start, tau = {tau:<4g}: largest W_2(JKO step k, exact p_(k tau)) {max(jko_mix_w2[tau]):.4f} (step at t = {(np.argmax(jko_mix_w2[tau]) + 1) * tau:g})")
X_GAP, T_GAP = -0.5, 0.2      # a point in the gap between the left and middle components
print(f"density at x = {X_GAP}, t = {T_GAP}: exact {p_t(X_GAP, T_GAP):.4f}   " + "   ".join(
    f"JKO tau = {tau:g} {step_density(jko_mix_Q[tau][int(round(T_GAP / tau))], U_GRID, X_GAP):.4f}" for tau in TAUS))
print(f"optimizer: {sum(r.success for r in jko_results)} of {len(jko_results)} steps converged, "
      f"most iterations in one step {max(r.nit for r in jko_results)}")
```

```output theme={null}
mixture start, tau = 0.1 : largest W_2(JKO step k, exact p_(k tau)) 0.0304 (step at t = 0.2)
```

```output theme={null}
mixture start, tau = 0.05: largest W_2(JKO step k, exact p_(k tau)) 0.0164 (step at t = 0.2)
density at x = -0.5, t = 0.2: exact 0.0988   JKO tau = 0.1 0.0795   JKO tau = 0.05 0.0880
optimizer: 240 of 240 steps converged, most iterations in one step 4605
```

```python theme={null}
# JKO on the mixture: W2 to the exact p_{k tau} small at the smaller tau
assert max(jko_mix_w2[TAUS[1]]) < 0.05
# optimizer converged on every step
assert all(res.success for res in jko_results)
```

![Density against x at times 0, 0.2, 0.5, 1 and 2. Solid lines are the exact densities: three peaks at time 0 that merge into one broad bump by time 2. Dots from the JKO steps lie on the lines at every time, with the largest visible gap at time 0.2 between x = -1 and x = 0, where the dots sit below the line.](https://mintcdn.com/aegeanaiinc/_3YkDHya7LTDeZHX/aiml-common/lectures/diffusion/gradient-flow/images/cell_17_output_1.png?fit=max\&auto=format\&n=_3YkDHya7LTDeZHX\&q=85\&s=78cf1e229c1cedaa890f0fec1d26f666)

*JKO steps at $t = 0, 0.2, 0.5, 1, 2$ with $\tau = 0.05$ from the mixture (dots, the density $\Delta u / \Delta Q$ of each step) and the exact Ornstein-Uhlenbeck density at the same time (lines).*

The largest $W_2$ error over all steps is $0.030$ at $\tau = 0.1$ and $0.016$ at $\tau = 0.05$. The steps differ most from the exact density in the gap between the left and middle components, which fills quickly at the start. At $x = -0.5$ and $t = 0.2$ the exact density is $0.099$, against $0.080$ for $\tau = 0.1$ and $0.088$ for $\tau = 0.05$. The steps lag behind the exact path there, as implicit Euler steps do, and the lag shrinks roughly in proportion to $\tau$; doubling the grid leaves it unchanged. To within these errors, a sequence of minimizations that uses only $\mathcal{F}$ and $W_2$ reproduces the diffusion density path.

## Geodesic or gradient flow

The plane of Gaussians showed two paths between the same endpoints. The same comparison works for the mixture. Over $t \in [0, T]$, the Ornstein-Uhlenbeck marginals run beside the constant-speed displacement interpolation from $p_0$ to $p_T$, whose quantile function is $(1 - t/T)\,Q_0 + (t/T)\,Q_T$. Along the geodesic the KL comes from the quantile form of $\mathcal{F}$, since the interpolation is defined through its quantile function.

```python theme={null}
Z_FINE = np.linspace(norm.ppf(U_MIN), -norm.ppf(U_MIN), 20001)
U_FINE = norm.cdf(Z_FINE)
Q0_f, QT_f = quantile_t(U_FINE, 0.0), quantile_t(U_FINE, T)
dQ0_f, dQT_f = 1 / p_t(Q0_f, 0.0), 1 / p_t(QT_f, T)               # exact Q'(u) = 1 / p(Q(u))
W_FINE = trapezoid_weights(U_FINE)


def kl_geodesic(t):
    """KL to N(0, 1) of the displacement interpolation at time t, from the quantile form with exact Q'."""
    s = t / T
    Q = (1 - s) * Q0_f + s * QT_f
    dQ = (1 - s) * dQ0_f + s * dQT_f
    return float(np.sum(W_FINE * (-np.log(dQ) + Q**2 / 2)) + LOG_SQRT_2PI)


T_KL = np.linspace(0, T, 81)
kl_curve = np.array([kl_to_gaussian(t) for t in T_KL])            # along the Ornstein-Uhlenbeck path
kl_geo = np.array([kl_geodesic(t) for t in T_KL])
print(f"shared endpoints: KL(p_0) {kl_curve[0]:.5f} vs {kl_geo[0]:.5f}   KL(p_T) {kl_curve[-1]:.2e} vs {kl_geo[-1]:.2e}")
print("KL to N(0, 1):")
for t in (0.25, 0.5, 1.0, 2.0, 3.0):
    i = int(np.argmin(np.abs(T_KL - t)))
    print(f"  t = {T_KL[i]:4.2f}   gradient flow {kl_curve[i]:.4f}   geodesic {kl_geo[i]:.4f}")
inner = slice(1, -1)
print(f"gradient flow below the geodesic at all {len(T_KL) - 2} interior times: {np.all(kl_curve[inner] < kl_geo[inner])}")
log_rate = -np.gradient(np.log(kl_curve), T_KL)                  # local decay rate of the KL
print("local decay rate -d log KL / dt along the gradient flow: " + "   ".join(
    f"t = {t:g}: {log_rate[int(np.argmin(np.abs(T_KL - t)))]:.2f}" for t in (0.5, 1.0, 2.0, 3.0, 3.5)))
print(f"normalized actions: gradient flow T A = {T * A:.4f}   geodesic W_2^2 = {W2_sq:.4f}")
```

```output theme={null}
shared endpoints: KL(p_0) 1.44842 vs 1.44842   KL(p_T) 6.06e-05 vs 6.07e-05
KL to N(0, 1):
  t = 0.25   gradient flow 0.5608   geodesic 1.3006
  t = 0.50   gradient flow 0.2613   geodesic 1.1600
  t = 1.00   gradient flow 0.0584   geodesic 0.9002
  t = 2.00   gradient flow 0.0040   geodesic 0.4670
  t = 3.00   gradient flow 0.0005   geodesic 0.1551
gradient flow below the geodesic at all 79 interior times: True
local decay rate -d log KL / dt along the gradient flow: t = 0.5: 3.00   t = 1: 2.96   t = 2: 2.36   t = 3: 2.06   t = 3.5: 2.02
normalized actions: gradient flow T A = 5.7935   geodesic W_2^2 = 1.5008
```

```python theme={null}
# KL decreases along the OU path
assert np.all(np.diff(kl_curve) < 0)
```

![Two standard transport heatmaps with time from 0 to 4 on the horizontal axis. On the left, the gradient flow: the three bands of p\_0 merge into one band before t = 1.5, and the quantile trajectories bend sharply at the start and are flat afterwards. Its title reports kinetic action 5.793. On the right, the geodesic: the trajectories are straight lines, the three bands stay apart until close to t = 4, and the title reports kinetic action 1.501.](https://mintcdn.com/aegeanaiinc/_3YkDHya7LTDeZHX/aiml-common/lectures/diffusion/gradient-flow/images/cell_20_output_1.png?fit=max\&auto=format\&n=_3YkDHya7LTDeZHX\&q=85\&s=0434cb0b4cc177d94bdf375d2e1a5461)

*Left, the Ornstein-Uhlenbeck path, which is the gradient flow, with quantile trajectories at 25 levels. Right, the geodesic between the same $p_0$ and $p_T$, with straight trajectories. Each title reports the normalized action: $T\mathcal{A}$ on the left and $W_2^2$ on the right.*

![KL divergence to the standard normal against time on a log scale. The solid gradient flow curve falls from about 1.4 at t = 0 along a nearly straight line to about 6e-5 at t = 4. The dashed geodesic curve stays above it, falling slowly to about 0.15 at t = 3 and then dropping steeply to the same final value at t = 4.](https://mintcdn.com/aegeanaiinc/_3YkDHya7LTDeZHX/aiml-common/lectures/diffusion/gradient-flow/images/cell_21_output_1.png?fit=max\&auto=format\&n=_3YkDHya7LTDeZHX\&q=85\&s=7b9d071598c34d952e2b6e68fc1b7fc8)

*KL divergence to $\mathcal{N}(0, 1)$ against time along the gradient flow (solid) and the geodesic (dashed), on a log scale.*

The two paths share their endpoints and differ everywhere in between. The gradient flow has the lower KL at every one of the 79 interior times: $0.26$ against $1.16$ at $t = 0.5$, and $0.004$ against $0.47$ at $t = 2$. The local decay rate $-\frac{d}{dt}\log D_{\mathrm{KL}}$ of the flow falls from about $3.0$ at $t = 1$ to $2.1$ at $t = 3$, so the late decay is close to $e^{-2t}$. The geodesic loses its KL more steadily: from $1.45$ to $0.47$ at $t = 2$ and $0.155$ at $t = 3$, about $90\%$ of it by $3T/4$. It looks slow on the log scale because the axis spans down to about $6 \times 10^{-5}$. Over the last unit of time it drops from $0.155$ to $6 \times 10^{-5}$. The geodesic has the smaller normalized action, $1.50$ against $5.79$.

Each path is optimal for a different problem. A geodesic joins two prescribed densities with the least action, and it needs both of them to be defined. A gradient flow needs only a starting density and a free energy. It follows the steepest descent of $\mathcal{F}$, and the endpoint is wherever the flow has reached at time $T$. This flow approaches $\gamma$ only as $t \to \infty$ and never reaches it in finite time. For that reason the Fokker-Planck section used the true endpoint $p_T$ throughout.

## Back to the three levels

The Fokker-Planck section opened with three levels of description. Both paths of this section can now be placed on all three.

| Level | Diffusion | Geodesic |
| - | - | - |
| Particles | forward SDE or probability flow ODE | straight lines at constant speed |
| Density | Fokker-Planck equation | continuity equation of the interpolation |
| Principle | steepest descent of $\mathcal{F}$ in $W_2$ | least action between fixed endpoints |

Once the principle is fixed, so is the density path: the gradient flow from $p_0$ has one solution, and so does the geodesic from $p_0$ to $p_T$. The density path does not fix the particles, as the family of dynamics with shared marginals showed in the Fokker-Planck section. Diffusion and the geodesic differ in the principle, and that difference accounts for the factor of almost four between their actions.

## Numerical checks

The JKO results depend on three numerical choices. Each one is varied separately, for the mixture with $\tau = 0.05$. The optimizer tolerance changes from $10^{-12}$ to $10^{-9}$. The quantile grid doubles from $N_U$ to $2N_U$ levels. The time step takes both values of $\tau$, for both starting densities.

```python theme={null}
tau = TAUS[1]
mix_exact = lambda t, u: quantile_t(u, t)
# 1. optimizer tolerance
Q_loose, err_loose, res_loose = run_jko(quantile_t(U_GRID, 0.0), U_GRID, tau, mix_exact, tol=1e-9)
tol_change = max(w2_on_grid(a, b, U_GRID) for a, b in zip(Q_loose, jko_mix_Q[tau]))
Q_tight, _, _ = run_jko(quantile_t(U_GRID, 0.0), U_GRID, tau, mix_exact, tol=1e-14)
tight_change = max(w2_on_grid(a, b, U_GRID) for a, b in zip(Q_tight, jko_mix_Q[tau]))
# 2. quantile grid refinement
U_GRID2 = quantile_grid(2 * N_U)
Q_fine, err_fine, res_fine = run_jko(quantile_t(U_GRID2, 0.0), U_GRID2, tau, mix_exact)
print(f"JKO from the mixture, tau = {tau:g}, largest W_2 error over the steps:")
print(f"  optimizer tolerance 1e-12: {max(jko_mix_w2[tau]):.5f}   tolerance 1e-9: {max(err_loose):.5f}   "
      f"largest W_2 between the two runs {tol_change:.1e}")
print(f"  tolerance 1e-14 (near double precision): largest W_2 to the 1e-12 iterates {tight_change:.1e}")
print(f"  N_U = {N_U}: {max(jko_mix_w2[tau]):.5f}   N_U = {2 * N_U}: {max(err_fine):.5f}")
k_gap = int(round(T_GAP / tau))
print(f"  density at x = {X_GAP}, t = {T_GAP}: N_U = {N_U} {step_density(jko_mix_Q[tau][k_gap], U_GRID, X_GAP):.4f}   "
      f"N_U = {2 * N_U} {step_density(Q_fine[k_gap], U_GRID2, X_GAP):.4f}   exact {p_t(X_GAP, T_GAP):.4f}")
print("  time step:")
for t_ in TAUS:
    print(f"    tau = {t_:<4g}  mixture {max(jko_mix_w2[t_]):.5f}   Gaussian {jko_gauss_err[t_]:.5f}")
print(f"  error ratio tau = {TAUS[0]:g} over tau = {TAUS[1]:g}: mixture "
      f"{max(jko_mix_w2[TAUS[0]]) / max(jko_mix_w2[TAUS[1]]):.2f}   Gaussian "
      f"{jko_gauss_err[TAUS[0]] / jko_gauss_err[TAUS[1]]:.2f}")
F_q1 = free_energy_quantile(quantile_t(U_GRID, 0.0), U_GRID)
F_q2 = free_energy_quantile(quantile_t(U_GRID2, 0.0), U_GRID2)
print(f"  F(p_0) from the quantile form: N_U = {N_U}: {F_q1:.5f}   "
      f"N_U = {2 * N_U}: {F_q2:.5f}   x quadrature {kl_to_gaussian(0.0):.5f}")
print(f"  all steps converged in these runs: {all(r.success for r in res_loose + res_fine)}")
```

```output theme={null}
JKO from the mixture, tau = 0.05, largest W_2 error over the steps:
  optimizer tolerance 1e-12: 0.01644   tolerance 1e-9: 0.01651   largest W_2 between the two runs 1.4e-03
  tolerance 1e-14 (near double precision): largest W_2 to the 1e-12 iterates 1.4e-04
  N_U = 400: 0.01644   N_U = 800: 0.01664
  density at x = -0.5, t = 0.2: N_U = 400 0.0880   N_U = 800 0.0878   exact 0.0988
  time step:
    tau = 0.1   mixture 0.03042   Gaussian 0.05099
    tau = 0.05  mixture 0.01644   Gaussian 0.02690
  error ratio tau = 0.1 over tau = 0.05: mixture 1.85   Gaussian 1.90
  F(p_0) from the quantile form: N_U = 400: 1.44292   N_U = 800: 1.44735   x quadrature 1.44842
  all steps converged in these runs: True
```

```python theme={null}
# convergence: the tolerance and the grid change the error by far less than tau does
assert abs(max(err_loose) - max(jko_mix_w2[tau])) < 0.05 * max(jko_mix_w2[tau])
assert tight_change < 0.1 * max(jko_mix_w2[tau])
# the quantile form of F converges to x quadrature: doubling the grid more than halves the error
assert abs(F_q2 - kl_to_gaussian(0.0)) < abs(F_q1 - kl_to_gaussian(0.0)) / 2
assert abs(max(err_fine) - max(jko_mix_w2[tau])) < 0.1 * (max(jko_mix_w2[TAUS[0]]) - max(jko_mix_w2[TAUS[1]]))
```

The time step dominates the error. Halving $\tau$ lowers the largest $W_2$ error by about $0.014$ for the mixture and $0.024$ for the Gaussian, close to a factor of two in both cases. Loosening the optimizer tolerance by three orders of magnitude moves the iterates by about $10^{-3}$ in $W_2$ and changes the largest error by less than $10^{-4}$. Tightening it to $10^{-14}$, near the limit of double precision, moves them by about $10^{-4}$, so the reference iterates are converged far below the time-step error. Doubling the grid changes the largest error by $2 \times 10^{-4}$, leaves the density in the gap unchanged, and brings the quantile-form free energy of $p_0$ from $5.5 \times 10^{-3}$ to $1.1 \times 10^{-3}$ below quadrature in $x$.

## References

* Benamou, J., Brenier, Y. (2000). *A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem*. Numer. Math. (Heidelb.). [DOI](https://doi.org/10.1007/s002110050002)
* Jordan, R., Kinderlehrer, D., Otto, F. (1998). *The variational formulation of the Fokker--Planck equation*. SIAM J. Math. Anal. [DOI](https://doi.org/10.1137/s0036141096303359)
* Santambrogio, F. (2015). *Optimal transport for applied mathematicians – calculus of variations, PDEs and modeling*.

***

Found an error on this page? [Report an issue](https://github.com/aegean-ai/eaia-feedback/issues/new?template=page-issue.yml\&page=/aiml-common/lectures/diffusion/gradient-flow/gradient_flow).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.