16 Simulated annealing: optimization by cooling

16.1 Temperature becomes an instrument

The previous lecture’s Metropolis chain has one parameter. The Metropolis chain samples \(p \propto e^{-E/T}\) at whatever temperature we choose, using only energy differences, and its cost is mixing: the autocorrelation time \(\tau\) that diverges at critical points and grows exponentially in glassy landscapes. Throughout that lecture the temperature stayed fixed, as part of the problem statement. Today we change it while the chain runs. Hot, the walker of Figure 15.2 crosses barriers and moves over the whole landscape; cold, it stays in one basin and refines downhill. Start hot and cool slowly, and the chain rides the Boltzmann distribution’s own concentration onto low-energy states all the way down to the ground state. A sampler, cooled, becomes an optimizer; this is simulated annealing, and it is Module 3’s second theme: the dynamics of the sampler as a subject in itself.

The name describes a laboratory procedure. A metallurgist who wants a defect-free crystal — the global minimum of the lattice energy — heats the metal and cools it slowly, so that at every stage the atoms stay near thermal equilibrium and settle collectively into ever-lower-energy arrangements. Cool the same melt fast — a quench — and it freezes wherever it happens to be: a glass, disordered, trapped in a local minimum of the energy, held there by barriers it no longer has the thermal energy to cross. In 1983 Kirkpatrick, Gelatt, and Vecchi took this procedure literally (Kirkpatrick, Gelatt, and Vecchi 1983): replace the metal’s energy by any cost function, the atoms’ thermal motion by a Metropolis chain, and the furnace schedule by a programmed temperature \(T(t)\), and the metallurgical procedure becomes a general-purpose optimizer. (The course has met the first author before: this is the same Scott Kirkpatrick who co-wrote Solvable Model of a Spin-Glass (Sherrington and Kirkpatrick 1975) — a spin-glass physicist recognizing that the frustrated, rugged landscapes of Section 11.4 and the cost surfaces of hard optimization problems are the same terrain, and that physics already had a method for exploring them. Independently and almost simultaneously, Černý (1985) built the same algorithm around the travelling salesman.) A year later, Geman and Geman (1984) supplied the theorem: cooled slowly enough, the chain is found in the global minimum with probability tending to one, with a precise meaning of “slowly enough” that this lecture states in full.

Finding the global minimum of a rugged landscape is hard for both familiar methods. Gradient descent stops in the first local minimum downhill of its start. Sampling at a fixed low temperature concentrates on the right answer in principle but cannot get there — the previous lecture’s mixing failure at its worst. The resolution is the schedule, which balances two failures: cooling too slowly takes impractically long, and cooling too fast quenches into a glass. In machine learning the scheduled temperature has another name, the learning rate, and decaying a learning rate is a form of annealing (Week 9).

Take-home 1

Cooling a Metropolis chain turns a sampler into an optimizer: as \(T \to 0\) the Boltzmann distribution concentrates on the global minima, and a chain that tracks equilibrium while cooling is carried onto the ground state. Slow cooling (annealing) reaches it; cooling too fast (a quench) freezes the chain in a local minimum, a glass.

Figure 16.1 summarizes the argument: one rugged landscape, one family of Boltzmann distributions above it, and two possible fates below.

Figure 16.1: Annealing and quenching. Top: the Boltzmann distribution \(p_T \propto e^{-E(x)/T}\) over one rugged landscape at three temperatures — hot, the mass spreads over every basin (exploration); warm, it concentrates in the deep wells; cold, only the global minimum survives. Bottom: the two fates of a cooled chain. Annealing — cooling slowly enough to stay near equilibrium at every temperature — tracks the concentrating distribution into the global minimum (the crystal); a quench — cooling faster than the chain can mix — strands it in a local minimum (a glass), exactly as in metallurgy.

16.2 Cooling concentrates the distribution

One landscape, a family of distributions. Fix the energy \(E(x)\) and let the temperature vary: Equation 1.2 becomes a one-parameter family

\[ p_T(x) \;=\; \frac{e^{-E(x)/T}}{Z_T}, \qquad Z_T = \sum_x e^{-E(x)/T}, \]

interpolating from the uniform distribution (\(T \to \infty\), where the exponent flattens completely) toward something increasingly selective as \(T\) falls. How selective it becomes follows from comparing any state to the best one, and in that ratio the intractable \(Z_T\) cancels, as in the previous lecture.

The concentration ratio. Let \(x^*\) be a global minimum of the energy, \(E^* = \min_x E(x)\), and let \(x\) be any state with \(E(x) > E^*\). Then

\[ \boxed{\; \frac{p_T(x)}{p_T(x^*)} \;=\; e^{-\left(E(x) - E^*\right)/T} \;\xrightarrow{\;T \to 0\;}\; 0 \;} \tag{16.1}\]

the \(T \to 0\) concentration

for every non-optimal state, however small its excess energy: any fixed gap \(E(x) - E^* > 0\) is eventually enormous compared to \(T\). All probability moves onto the global minima, and in the limit

\[ p_T \;\xrightarrow{\;T \to 0\;}\; \text{uniform on } \operatorname*{arg\,min}_x E(x) \]

— a single point mass if the minimum is unique, and the uniform distribution over all \(g\) ground states if it is \(g\)-fold degenerate (our spin-glass example below has \(g = 2\), the two global spin flips of one configuration). Temperature sets how sharply the Boltzmann distribution prefers low energy, and at \(T \to 0\) it prefers only the lowest — so a single sample from the zero-temperature limit is a certificate of global optimality. Optimization has become a sampling problem.

The free-energy reading. Week 1’s decomposition \(F = \langle E \rangle - TS\) says the same thing thermodynamically. At high temperature the entropy term dominates: the free energy is minimized by spreading — many states, all basins, exploration favored by the \(-TS\) term. As \(T\) falls, the entropic reward shrinks and the energy term takes over: the mass must commit to the lowest states, however few. Annealing follows this balance as \(T\) moves from one regime to the other, and the concentration Equation 16.1 is its destination. Figure 16.2 makes the statement quantitative on the very spin glass the worked example will anneal: sixteen spins, \(2^{16} = 65{,}536\) states enumerated exactly, and the total Boltzmann weight of the two ground states rising from \(0.17\%\) at \(T = 2\) (already a \(55\)-fold enhancement over the uniform \(2/65{,}536 \approx 0.003\%\)) through one half at \(T \approx 0.34\) to \(99\%\) by \(T \approx 0.12\).

Show code

N = 16

def make_glass(seed):
    rng = np.random.default_rng(seed)
    J = rng.normal(0, 1 / np.sqrt(N), (N, N))
    J = (J + J.T) / np.sqrt(2)
    np.fill_diagonal(J, 0.0)
    return J

J_a = make_glass(3)
S_all = np.array([[(c >> i & 1) * 2 - 1 for i in range(N)] for c in range(2**N)], dtype=float)
E_all = -0.5 * np.einsum("ci,ij,cj->c", S_all, J_a, S_all)
Estar_a = E_all.min()
is_ground = np.isclose(E_all, Estar_a)
gap = np.sort(np.unique(np.round(E_all - Estar_a, 9)))[1]

fig, (a1, a2) = plt.subplots(1, 2, figsize=(10.4, 4.0))

Ts = np.linspace(0.02, 2.0, 400)
for dE, ls in zip([0.2, gap, 2.0], [":", "-", "--"]):
    a1.plot(Ts, np.exp(-dE / Ts), color=NAVY, ls=ls, lw=2.2,
            label=rf"$\Delta E = {dE:.2f}$" + ("  (this glass's gap)" if np.isclose(dE, gap) else ""))
a1.set_xlabel(r"temperature $T$")
a1.set_ylabel(r"$p_T(x)\,/\,p_T(x^*) = e^{-\Delta E/T}$")
a1.set_title("weight of an excited state relative to the optimum", fontsize=12)
a1.legend(frameon=False, fontsize=10, loc="upper left")

Pg = [np.exp(-(E_all - Estar_a) / T)[is_ground].sum() / np.exp(-(E_all - Estar_a) / T).sum()
      for T in Ts]
a2.plot(Ts, Pg, color=ORANGE, lw=2.6)
a2.axhline(0.5, color=GRAY, ls=":", lw=1)
a2.annotate(r"$P = 1/2$ at $T \approx 0.34$", xy=(0.34, 0.5), xytext=(0.75, 0.58),
            color=GRAY, fontsize=10.5,
            arrowprops=dict(arrowstyle="->", color=GRAY, lw=1))
a2.annotate(r"$0.17\%$ at $T = 2$", xy=(2.0, Pg[-1]), xytext=(1.35, 0.22),
            color=ORANGE, fontsize=10.5,
            arrowprops=dict(arrowstyle="->", color=ORANGE, lw=1))
a2.set_xlabel(r"temperature $T$")
a2.set_ylabel(r"$P_T(\mathrm{ground\ states})$")
a2.set_title("mass on the ground states", fontsize=12)
a2.set_ylim(-0.02, 1.05)
fig.tight_layout()
plt.show()

Figure 16.2: Concentration, exactly, on the spin glass of the worked example (\(N = 16\) spins, couplings \(J_{ij} \sim \mathcal{N}(0, 1/N)\), all \(65{,}536\) states enumerated). Left: the boxed ratio Equation 16.1 for three energy gaps — the middle curve uses this instance’s actual first excitation gap \(\Delta E = 0.71\). Every non-optimal state’s relative weight vanishes as \(T \to 0\), faster for larger gaps. Right: the total Boltzmann probability of the two degenerate ground states against temperature. At \(T = 2\) they carry \(0.17\%\) of the mass; the curve crosses \(1/2\) at \(T \approx 0.34\) and reaches \(99\%\) by \(T \approx 0.12\) — a sample from the cold distribution is, with overwhelming probability, the exact optimum. What remains is whether a chain can *follow* this curve down.

16.3 Cooling schedules and the quench

Why you cannot simply set \(T = 0\). Put \(T = 0\) into the previous lecture’s acceptance rule Equation 15.3: every uphill acceptance \(e^{-\Delta E/T}\) vanishes, and the chain accepts only moves that lower the energy — greedy descent. Such a chain stops, permanently, at the first configuration from which every move goes uphill: a local minimum, and almost never the global one. Our sixteen-spin glass has \(28\) of these single-flip-stable states, and greedy descent from a random start reaches the true ground state in only \(29\%\) of runs — the other \(71\%\) end in one of the \(26\) non-global minima. Sampling at \(T = 0\) is precisely the trapping we set out to avoid; the zero-temperature limit is a destination to approach, never an operating point. So the chain must start hot, where barriers are crossable, and cool: run Metropolis with a time-dependent temperature \(T(t)\), decreasing from exploration to commitment. Everything now hangs on how fast.

The constraint is the previous lecture’s mixing time. The concentration argument of Section 16.2 is a statement about equilibrium at each temperature; the chain inherits its benefits only if it actually equilibrates as it cools. Equilibration at temperature \(T\) requires the mixing time \(\tau(T)\) — and \(\tau(T)\) grows as \(T\) falls, because barrier crossings are exponentially suppressed: a barrier of height \(\Delta B\) takes of order \(e^{\Delta B/T}\) attempts (the Arrhenius law W9 will derive from Langevin dynamics; today it is the previous lecture’s uphill-acceptance rule read as a waiting time). Cooling therefore competes with a relaxation time that grows as the temperature falls, with two possible outcomes. Cool within the clock, and the chain stays near \(p_{T(t)}\) at every moment and is carried onto the ground state. Outrun the clock, and the chain falls out of equilibrium and freezes wherever it stands — the quench, and the frozen result is a glass in exactly the metallurgist’s sense: a configuration held in place because the moves that would improve it have become exponentially rare.

The excess free energy of a quench. “Frozen wherever it stands” can be made quantitative with Week 1’s free-energy decomposition and the previous lecture’s adjoint kernel (Welling, Lu, and Holdijk 2026, ch. 10 on stochastic thermodynamics). Define the nonequilibrium free energy of whatever distribution \(\rho\) the chain currently carries, \(F[\rho] = \langle E \rangle_\rho - T\, S[\rho]\) — Week 1’s decomposition, now evaluated off equilibrium. Two lines relate it to the equilibrium value \(F_T = -T \log Z_T\): since \(-\log p_T(x) = E(x)/T + \log Z_T\),

\[ F[\rho] - F_T \;=\; \langle E \rangle_\rho + T \langle \log \rho \rangle_\rho + T \log Z_T \;=\; T\, \big\langle \log \rho - \log p_T \big\rangle_\rho \;=\; T\; D_\mathrm{KL}\big(\rho \,\|\, p_T\big) \;\geq\; 0 . \tag{16.2}\]

excess free energy = KL to equilibrium

Every distribution sits above equilibrium by an excess free energy, and the excess is its Kullback–Leibler divergence to the Boltzmann distribution, in units of \(T\). Relaxation decreases this excess monotonically, and the proof needs only the machinery from the previous lecture. Write the joint law of one chain step in two ways: seeded at \(\rho\), it is \(P_\rho(x, x') = \rho(x)\, W(x \to x')\); seeded at equilibrium, \(P_\mathrm{eq}(x, x') = p_T(x)\, W(x \to x')\). In the ratio \(P_\rho/P_\mathrm{eq}\) the kernels cancel, so \(D_\mathrm{KL}(P_\rho \| P_\mathrm{eq}) = D_\mathrm{KL}(\rho \| p_T)\). Now decompose the same divergence by conditioning on the endpoint instead: the marginals are \(\rho W\) and \(p_T W = p_T\), the equilibrium conditional \(P_\mathrm{eq}(x \mid x')\) is the previous lecture’s adjoint kernel (Equation 15.4, making its second appearance), and the chain rule for KL gives

\[ D_\mathrm{KL}(\rho \| p_T) \;=\; D_\mathrm{KL}\big(\rho W \,\|\, p_T\big) + \underbrace{\big\langle D_\mathrm{KL}\big( P_\rho(\cdot \mid x') \,\|\, P_\mathrm{eq}(\cdot \mid x') \big) \big\rangle_{\rho W}}_{\geq\, 0} \;\;\Longrightarrow\;\; D_\mathrm{KL}\big(\rho W \,\|\, p_T\big) \;\leq\; D_\mathrm{KL}\big(\rho \,\|\, p_T\big) . \]

Each sweep of the chain lowers the excess free energy, with equality only at equilibrium — a discrete H-theorem, and the information theorist’s data-processing inequality in physical units. An anneal is then a sequence of such relaxations toward moving targets: at each stage the chain reduces its divergence to \(p_{T_k}\), and the cooling step then sharpens the target and increases the divergence that remains. Ending the schedule before relaxation completes and freezes in the residual \(D_\mathrm{KL}(\rho_\text{end} \| p_{T_\text{end}})\): by Equation 16.2 it is exactly the glass’s excess free energy over the crystal, and the quench trace of Figure 16.4 flattening above the dotted ground-state line is this residual, seen in its energy component. Week 9 takes this monotone descent to continuous time, where it becomes the H-theorem of the Fokker–Planck equation, and Week 11 refines the accounting to single trajectories, where the decrease in divergence acquires the name entropy production and the frozen residual returns as the dissipated work of a finite-time protocol.

The guaranteed schedule. Geman and Geman (1984) made “slow enough” precise:

\[ T(t) \;\geq\; \frac{c}{\log(1 + t)} \quad \Longrightarrow \quad P\big(X_t \in \operatorname*{arg\,min} E\big) \to 1 \tag{16.3}\]

logarithmic cooling (guaranteed)

where the constant \(c\) must be at least the depth of the deepest barrier around a non-global minimum — that sharp, necessary-and-sufficient value is Hajek (1988)’s; Geman and Geman (1984)’s original proof guaranteed convergence for a larger \(c \sim N\Delta\) (sites times energy range) — and the schedule must additionally send \(T(t) \to 0\), since a constant temperature satisfies the inequality as written yet converges to nothing. The convergence is in probability: with \(c\) at Hajek’s value the chain still leaves the ground state infinitely often, but the probability of finding it there tends to one. The theorem is genuine, but it does not help in practice: inverting the schedule, reaching temperature \(T\) takes \(t \sim e^{c/T}\) steps, the same exponential as the barrier crossings the schedule must wait for, and far beyond any practical budget. What practice uses instead is

\[ T_{k+1} = \alpha\, T_k, \qquad \alpha \in (0.8,\, 0.99) \tag{16.4}\]

geometric cooling (practical)

— a fixed multiplicative decay per stage, fast, tunable, and backed by no theorem at all. The schedule with the proof is unusable, and the schedule in use is unproven. Simulated annealing is a powerful heuristic — it beats greedy descent wherever barriers matter — but it is not a guaranteed global optimizer at any practical cooling rate, and results obtained with it should be reported with that in mind. (A notational flag: \(\alpha\) here is the cooling factor, not Week 2’s storage load, and \(T(t)\) is now prescribed by the schedule, with \(\beta = 1/T\) increasing as it runs.)

Trap

\(T = 0\) is a limit, and the guarantee is impractical. ① Sampling at \(T = 0\) is greedy descent: on the example glass it fails \(71\%\) of the time. The optimizer is the cooling schedule, and a chain held at any fixed low \(T\) inherits the previous lecture’s exponential mixing time. ② The logarithmic guarantee Equation 16.3 requires \(t \sim e^{c/T}\) steps with \(c\) set by the deepest barrier — a valid but unusable bound. Every practical anneal is a heuristic, and a reported “optimum” from geometric cooling is the best configuration found, with no certificate.

Take-home 2

Cooling must proceed no faster than the chain mixes at each temperature, and the mixing time grows as \(e^{\Delta B/T}\). Cooling faster than mixing is a quench, which freezes the chain in a glass where mixing is worst: through \(T_c\) and in rugged landscapes.

16.4 The bridge: the learning rate is a temperature

High temperature favors exploration: the chain accepts uphill moves and visits basins it would never enter greedily. Low temperature favors exploitation: it refines the basin it is in. Annealing moves from one to the other, and stated this way the idea is not specific to spins; every stochastic optimizer faces the same trade-off, and deep learning already schedules a parameter that controls it.

Consider noisy gradient descent on a loss \(L(\theta)\), with the noise injected deliberately:

\[ \theta_{t+1} \;=\; \theta_t \;-\; \eta\, \nabla L(\theta_t) \;+\; \sqrt{2\,\eta\, T}\; \xi_t, \qquad \xi_t \sim \mathcal{N}(0, \mathbb{1}), \]

a downhill step of size \(\eta\) plus a Gaussian kick. This is the discretization of Langevin dynamics, and Week 9 (the Fokker–Planck equation) will prove what today we only state: its stationary distribution is \(\propto e^{-L(\theta)/T}\) — a Boltzmann distribution over the loss landscape, with the loss as energy. Run at \(T = 1\) with mini-batch gradients, this is precisely stochastic gradient Langevin dynamics (Welling and Teh 2011), a sampler for Bayesian posteriors built from an optimizer. Now delete the injected noise and run plain SGD. The randomness does not vanish — the mini-batch gradient is itself a noisy estimate, with a covariance set by the data and the batch size, independent of \(\eta\). Carried through the same dynamics, drift scales as \(\eta\) while the noise’s variance scales as \(\eta^2\), and the ratio that plays the role of temperature comes out proportional to the step size:

\[ \boxed{\; T_\text{eff} \;\propto\; \eta \;} \tag{16.5}\]

temperature ↔︎ learning rate

Decaying \(\eta_t\) over training is annealing on the loss (Figure 16.3): the large early steps are the hot phase, roaming among basins; the small late steps are the cold phase, committing to one and refining it. The step decays and cosine schedules of deep-learning practice are cooling schedules (the learning-rate warm-up that often precedes them is a brief heating stage), and the quench has a training counterpart: dropping the learning rate too early freezes the run in whichever basin it happens to occupy. One caveat: for SGLD the Boltzmann stationary distribution is a theorem (in the decreasing-step limit; at a fixed step there is an \(\mathcal{O}(\eta)\) discretization bias); for plain SGD, \(T_\text{eff} \propto \eta\) is today a scaling argument, and turning it into a precise statement — what exactly SGD’s mini-batch noise does, when the Boltzmann form holds, and what it says about flat minima and generalization — is the subject of Week 9. (Two further pointers: parallel tempering, the modern cure for glassy annealing — run replicas at a ladder of temperatures and swap them, so cold chains borrow the hot chains’ mobility; and annealed importance sampling, Week 11, where a cooling schedule is used not to optimize but to estimate \(Z\) itself.)

Figure 16.3: One parameter in two settings. Left: simulated annealing schedules a temperature \(T(t)\) downward; the chain samples \(\propto e^{-E(x)/T}\) and passes from exploration to exploitation. Right: plain SGD with a decaying learning rate \(\eta_t\) does the same on a loss landscape — its mini-batch noise sets an effective temperature \(T_\text{eff} \propto \eta\), so the learning-rate schedule acts as a cooling schedule. (SGLD differs: its temperature \(T\) is injected by hand, independently of \(\eta\).) Week 9 derives the correspondence.

Take-home 3

Temperature balances exploration against exploitation, and in learning this role is played by the learning rate: Langevin dynamics has stationary distribution \(\propto e^{-L/T}\) (SGLD, Welling and Teh (2011)), and plain SGD’s mini-batch noise gives \(T_\text{eff} \propto \eta\). Dropping the rate too early is a quench.

16.5 Example: anneal versus quench, on sixteen spins

We take the spin glass of Figure 16.2 — \(N = 16\), \(J_{ij} \sim \mathcal{N}(0, 1/N)\), all \(65{,}536\) states enumerated, ground-state energy \(E^*/N = -0.610\) (doubly degenerate, the global flip) and \(28\) local minima — and anneal it with Metropolis under geometric cooling from \(T = 2.0\) to \(0.02\), giving the schedule different total durations. Every run uses the same schedule shape; only the clock changes. For contrast, we use a second, harder instance from the same ensemble (“glass B”, \(E^*/N = -0.599\)). Fifty independent runs per point; Figure 16.4 shows the traces and the verdict, and the fractions of runs that end in the true ground state are (the greedy column from separate random-order descent runs):

total sweeps	3	10	30	100	300	1000	3000	greedy (\(T=0\))
glass A	\(0.10\)	\(0.28\)	\(0.50\)	\(0.66\)	\(0.88\)	\(0.98\)	\(1.00\)	\(0.29\)
glass B	\(0.10\)	\(0.16\)	\(0.16\)	\(0.26\)	\(0.24\)	\(0.44\)	\(0.60\)	\(0.20\)

Slower cooling improves the result, up to the sampling error of \(50\) runs (about \(\pm 0.07\)): on glass A the success rate climbs from \(10\%\) for a three-sweep quench to certainty at three thousand sweeps — the anneal–quench crossover of Section 16.3 as a measured curve. The greedy column calibrates both ends: pure descent manages \(29\%\), roughly a third of a patient anneal’s success rate, yet still beats the fastest quenches — which end their schedule before they have finished descending at all. Glass B shows the instance dependence: same size, same ensemble, and the success rates are lower throughout — at three thousand sweeps, where glass A is solved, glass B still fails four times in ten. By Hajek’s theorem the required schedule is set exponentially by the deepest barrier, so no single cooling rate is “slow enough” in general, which is why Equation 16.3’s guarantee had to be logarithmic and why annealing remains a heuristic. In the traces (left panel), the quench’s median energy flattens at \(-0.56\) per spin, an excited glass, while the anneal’s median lands on the dotted ground-state line at \(-0.610\).

Show code

def anneal_ensemble(J, sweeps, runs, T0=2.0, T1=0.02, seed=0, trace=False):
    """`runs` independent Metropolis chains, cooled geometrically from T0 to T1."""
    rng = np.random.default_rng(seed)
    s = rng.choice([-1.0, 1.0], (runs, N))
    E = -0.5 * np.einsum("ri,ij,rj->r", s, J, s)
    alpha = (T1 / T0) ** (1 / max(sweeps - 1, 1))
    T = T0
    traces = [E.copy()]
    for k in range(sweeps):
        for _ in range(N):                       # one sweep = N attempted flips
            i = rng.integers(N, size=runs)
            dE = 2 * s[np.arange(runs), i] * np.einsum("rj,rj->r", J[i], s)
            acc = (dE <= 0) | (rng.random(runs) < np.exp(-np.clip(dE, 0, None) / T))
            s[np.arange(runs), i] = np.where(acc, -s[np.arange(runs), i], s[np.arange(runs), i])
            E = np.where(acc, E + dE, E)
        T *= alpha
        if trace:
            traces.append(E.copy())
    return (np.array(traces), E) if trace else E

J_b = make_glass(4)   # ground state via the S_all enumeration of the previous cell
Estar_b = (-0.5 * np.einsum("ci,ij,cj->c", S_all, J_b, S_all)).min()

fig, (a1, a2) = plt.subplots(1, 2, figsize=(10.4, 4.1))

tr_slow, _ = anneal_ensemble(J_a, 1000, 50, seed=1, trace=True)
tr_fast, _ = anneal_ensemble(J_a, 10, 50, seed=1, trace=True)
for tr, sw, col, lab in [(tr_fast, 10, RED, "quench (10 sweeps)"),
                         (tr_slow, 1000, NAVY, "anneal (1000 sweeps)")]:
    x = np.linspace(0, 1, sw + 1)
    lo, mid, hi = np.percentile(tr / N, [25, 50, 75], axis=1)
    a1.fill_between(x, lo, hi, color=col, alpha=0.18)
    a1.plot(x, mid, color=col, lw=2.4, label=lab)
a1.axhline(Estar_a / N, color=GRAY, ls=":", lw=1.2)
a1.text(0.99, Estar_a / N + 0.012, r"ground state $E^*/N = -0.610$",
        color=GRAY, fontsize=10, ha="right")
a1.set_xlabel(r"fraction of cooling schedule ($T: 2.0 \to 0.02$)")
a1.set_ylabel(r"energy per spin $E/N$")
a1.set_title("same schedule shape, different clock", fontsize=12)
a1.legend(frameon=False, fontsize=10, loc="upper right")

budgets = [3, 10, 30, 100, 300, 1000, 3000]
for J, Estar, col, lab in [(J_a, Estar_a, NAVY, "glass A"),
                           (J_b, Estar_b, ORANGE, "glass B (harder instance)")]:
    fr = [np.isclose(anneal_ensemble(J, sw, 50, seed=7), Estar).mean() for sw in budgets]
    a2.semilogx(budgets, fr, "o-", color=col, lw=2, ms=6, label=lab)
a2.axhline(1.0, color=GRAY, ls=":", lw=1)
a2.set_xlabel("total sweeps in the schedule (cooling time)")
a2.set_ylabel(r"fraction of runs reaching $E^*$")
a2.set_title("slower cooling, better crystal", fontsize=12)
a2.set_ylim(0, 1.08)
a2.legend(frameon=False, fontsize=10, loc="lower right")
fig.tight_layout()
plt.show()

Figure 16.4: Anneal versus quench on glass A (\(N = 16\); exact \(E^*/N = -0.610\) from enumeration; geometric cooling \(T: 2.0 \to 0.02\)). Left: median energy per spin with interquartile band over \(50\) runs, plotted against the *fraction* of the schedule — the quench (red, \(10\) sweeps total) and the anneal (navy, \(1000\) sweeps) follow identical schedule shapes with different clocks. The quench freezes at \(-0.56\) per spin, an excited local minimum; the anneal tracks equilibrium and lands on the ground state. Right: the fraction of \(50\) runs ending in the true ground state against the total schedule length, for glass A and for a second, harder instance. Slower cooling helps, within sampling error; glass B still fails \(40\%\) of the time at a budget that solves glass A completely.

Annealing optimizes by cooling slowly enough to stay near equilibrium; a quench freezes the chain in a glass.

16.6 Outlook: from cooling to training

The previous lecture established that the Boltzmann distribution can be sampled without its normalizer, limited by mixing; today the temperature became a schedule, and the mixing limitation reappeared as the quench. Every claim of this lecture was ultimately a claim about mixing within a finite time. That the resulting algorithm was invented by a spin-glass physicist is not incidental: the rugged landscapes where annealing is both necessary and hard are the same ones Weeks 2 and 6 mapped, and the metallurgical vocabulary — crystal, glass, quench — has been the course’s vocabulary for memory and optimization since Figure 3.1.

The claim \(T_\text{eff} \propto \eta\) was offered as a scaling argument; Week 9 supplies the machinery — Langevin dynamics as the continuum limit of noisy descent, the Fokker–Planck equation as its law of motion, and the Boltzmann distribution over the loss as its stationary state — and with it the consequences: why SGD’s noise favors flat minima, how that relates to generalization, and why the training hyperparameters act as thermodynamic variables.

The longer thread runs to the course’s title. Cooling as a computational principle does not end with optimization: Week 11 anneals to estimate the very \(Z\) this module avoids computing (annealed importance sampling — a bridge of intermediate temperatures between a tractable distribution and the target), and Week 12’s diffusion models are an annealing schedule run as a generative process — noise added along a schedule and removed along the reverse one, with a learned denoiser standing where the Metropolis rule stands today. The annealing framework, introduced in a 1983 Science paper, remains active through the final lecture.