Order in Chaos: Why Drunk Optimizers Generalize Better — Sharpness Dimension and Edge of Stability

> Analysis of: arXiv:2604.19740 — Generalization at the Edge of Stability > Authors: Mario Tuci, Caner Korkmaz, Umut Şimşekli, Tolga Birdal (INRIA, Imperial College London)

1. An Uncomfortable Fact

When training neural networks with a large learning rate, the optimizer starts oscillating—stumbling across the loss surface like a drunk person. Instability should hurt learning, yet models trained this way often generalize better. This Edge of Stability (EoS) phenomenon has been observed countless times, but classical theory fails to explain it.

The traditional story says models should converge to a "flat" minimum: wider valleys generalize better. But flat minima do not always generalize well, sharp ones are not always bad, and sharpness metrics (Hessian trace, spectral norm) correlate with generalization unreliably.

This paper's claim: the field is asking the wrong question.

2. Not Converging to a Point, but Landing on an Attractor

Classical theory assumes the optimizer settles on a parameter point, like a ball resting in a valley. In reality, especially at large learning rates, parameters never stop—they oscillate and explore, drawing a complex, never-repeating trajectory on the loss surface.

The paper's insight: treat the optimizer as a Random Dynamical System (RDS). Under this view, parameters do not converge to a point but to an attractor—a fractal, self-similar set. The authors prove that in the EoS regime, the trajectory indeed lands on a fractal attractor whose intrinsic dimension is far smaller than the parameter-space dimension.

3. Sharpness Dimension (SD)

Inspired by Lyapunov dimension theory from chaos dynamics, the authors define the Sharpness Dimension:

• Compute the full Hessian spectrum
• Find the largest j* such that the sum of the top j* eigenvalues ≥ 0
• SD = j* + a weighted contribution of the remaining eigenvalues

Intuition: in EoS, the largest Hessian eigenvalue is positive (at least one expanding direction), but most directions contract. The balance of expansion and contraction defines an effective dimension of the explored set.

Key finding: in EoS, SD is strictly less than d. Generalization is governed by SD, not the parameter count. A million-parameter model whose attractor has an effective complexity of ~100 dimensions behaves, generalization-wise, like a 100-dimensional model. This explains why overparameterized models generalize: they dance on low-dimensional strange attractors rather than resting in flat minima.

4. Proven Generalization Bound

The authors establish a worst-case generalization bound:

\[\mathcal{G}_S(\mathcal{A}(\omega)) \leq 2L\delta + 2B\sqrt{\frac{4 \cdot \text{SD} \cdot \log(1/\delta)}{n}} + \text{mutual-information term} + \text{constant}\]

Generalization error scales with SD/√n. The proof works because SD upper-bounds the Minkowski (box-counting) dimension of the attractor, which controls covering numbers—how many distinct functions the model can cover. Steps: (1) use Hessian singular values to determine ellipsoid principal axes, (2) compute covering numbers of these ellipsoids, (3) show SD governs the attractor's geometric complexity.

5. Experiments

Validated on MLPs and GPT-2:

• SD correlates strongly with generalization gap—more consistently than Hessian trace, spectral norm, or Fisher-Rao norm, across learning rates, widths, and depths.
• SD explains grokking: before grokking occurs, SD suddenly drops—the model transitions to a lower-dimensional attractor, suddenly focusing on a "thin" but effective solution space.

6. Critical Assessment

Is "flat minima generalize well" cargo cult? Arguably yes. Flatness is a proxy; the true controlling quantity is the attractor's effective dimension. Trace and spectral norm fail because they compress the Hessian to a single number, while generalization depends on the full spectral structure—which directions expand, which contract, and in what proportion. SD is the first complexity measure incorporating the complete spectrum.

Limitations: 1. Computation: full Hessian spectra are expensive; stochastic Lanczos quadrature helps but scaling to very large models remains hard. 2. Adaptive optimizers: theory mainly covers SGD; Adam/AdamW dynamics may yield different attractor structures. 3. Regularity assumptions: nonsingularity, integrability, and bounded distortion need verification in real training.

7. What This Means

• For practitioners: oscillation is not necessarily bad—what matters is whether the oscillation lands on a low-dimensional attractor. SD may become a core metric for automatic hyperparameter tuning.
• For theorists: a paradigm shift from point analysis (minima geometry) to set analysis (attractor dynamics).
• Model size matters less than effective dimension: future techniques may "sculpt" attractors so models explore only a low-dimensional, sufficiently expressive subset of parameter space.

Quick Reference

• arXiv: 2604.19740
• SD < d in the EoS regime; λ₁ > 0 marks at least one expanding direction
• Grokking: SD drops sharply beforehand
• Validation: MLP + GPT-2; scalable SD estimation via stochastic Lanczos quadrature
• Inspiration: Lyapunov dimension theory + random dynamical systems

Closing Thought

The most striking contribution is the shift of perspective. For a decade we hunted for flat valleys; this paper says the treasure lies in the dancer's never-repeating trajectory. The optimizer is not a ball seeking rest but a dancer creating order—fractal order emerging from chaotic steps—and the secret of generalization hides in that order's "thinness."