Percolation Dynamics in Optimization : Variance Cascades and Discrete Scale Invariance

AI summary

Overview

Research area: Optimization theory for deep learning, specifically the implicit bias of Stochastic Gradient Descent (SGD), adaptive optimizers (Adam, AdamW), stochastic differential equations, applied topology (Reeb graphs), and percolation theory.

Technical level: Advanced. The paper relies on Itô stochastic calculus, infinitesimal generators, supermartingale arguments, Doob's maximal inequality, Reeb graph topology, and percolation theory. The empirical section is more accessible than the theory.

Scope: The paper proposes that the way SGD collapses neural networks onto simpler, symmetric subnetworks can be modeled as a percolation process whose transitions produce geometric ("discrete scale invariant") variance cascades, and extends this account to Adam and AdamW under a heavy-tailed noise model.

What This Paper Is About

SGD is known to push deep networks toward invariant sets that behave like much simpler subnetworks, but how the network travels to those sets over time is not well understood. This paper models that journey as a percolation process in which architectural symmetries force groups of parameters to merge in discrete simultaneous blocks rather than one edge at a time. The goal is to explain why training can show sudden, discrete transitions—such as grokking—and to identify a measurable signature (variance spikes in a macroscopic order parameter) that reveals them.

Key Contributions

1. A percolation model of topological condensation. The authors map stochastic gradient flow near invariant sets onto a graph tracking merges and splits (a Reeb graph), which is then renormalized into a percolation process. Architectural symmetries cause discrete simultaneous block-merges instead of continuous edge attachment, and the authors determine the precise condition under which this discontinuity survives as the network grows large rather than vanishing as a finite-size artifact.

2. Variance divergence and topological cascades. Using the relative variance of an order parameter across training trajectories to isolate discrete microtransitions, the authors derive that multi-body block-merges yield Discrete Scale Invariance (DSI), turning the phase transition into a geometrically scaling cascade.

3. Extension to Adam and AdamW. The trapping mechanism and the DSI cascade are shown to extend to Adam and AdamW under an explicit heavy-tailed noise model, with an elementwise-squaring argument narrowing the admissible symmetry group from general orthogonal transformations to coordinate permutations (which still contain the neuron-permutation symmetry used for SGD).

4. Empirical observations. The framework is tested in toy models with shifting data distributions, on tabular classification with UCI datasets, on vision benchmarks, and on grokking in Transformers trained on modular arithmetic.

Main Findings

• Percolation, not Erdős–Rényi, attachment. Classical percolation grows components by independent single-edge attachments. Under symmetry group $S_n$, the neural percolation graph instead forbids continuous edge attachment and forces simultaneous group-wise bindings, producing a jump $\Delta \mathcal{O}(p) = (n-1)i/N$ in the order parameter at each microtransition merging components of size $i$.

• Discontinuity survives only for macroscopic merges. The jump is a genuine discontinuity in the thermodynamic limit ($N \to \infty$) precisely when the merging components are already macroscopic at the moment of the merge ($i = \Theta(N)$). When the merging components are microscopic ($i = O(1)$), the jump vanishes as $N \to \infty$ and the transition is asymptotically continuous.

• Relative variance diverges at microtransitions. At a structural microtransition, the relative variance $R_v(p)$ of the order parameter diverges proportionally to the squared jump amplitude $(\Delta \mathcal{O})^2$, and does so preceding the critical global connectivity threshold $p_c$.

• Discrete Scale Invariance with geometric cascade. Under the $S_n$ constraint, component growth is restricted to the discrete mapping $C_1 \to nC_1$, locking critical microtransition densities into a geometric cascade: $\lim_{i\to\infty} (p_c - p_{ni})/(p_c - p_i) = 1/\lambda^{(n)}$ with $\lambda^{(n)} \equiv n^{\sigma}$.

• Toy model confirms the predicted baseline. In a controlled toy setting adapting Chen et al. (2023), pairwise subnetwork merges are predicted at magnification $\lambda = 2$. A constrained $K=3$ baseline and an unconstrained $K=6$ SGD optimization both match this prediction ($\lambda \approx 2.00$) via localized $R_v$ divergences, and a task shift at $t = 3000$ confirms the predicted reversibility, producing a reactive fragmentation peak.

• Grokking coincides with a 3-peak DSI cascade. In a Transformer trained on modular arithmetic, delayed generalization coincides with a 3-peak DSI cascade immediately preceding the performance spike, with $\lambda = 2.11$ and a phase-randomized spectral null false positive rate (FPR) of $0.1%$. The authors explicitly do not claim this cascade is the sole driver of the transition.

• Same cascade structure on benchmarks. The cascade structure appears, with fractional scaling factors consistent with pairwise or higher-order merges, across UCI tabular classification (UCI Heart Disease) and vision benchmarks (FMNIST).

• Adam and AdamW trap under stated conditions. Under a heavy-tailed noise model (there exist $p \in (1,2]$ and $\sigma > 0$ such that $\mathbb{E}|g_{t,i}|^p \le \sigma^p$ for every coordinate $i$ and every $t$), a truncated process yields a residual $R_t = O(b_t + L_m \tau_2 \Delta_{max} + L \tau_t \sqrt{\epsilon})$, and the stopped transverse process is a non-negative local supermartingale when the drift margin dominates that residual.

• Same magnification factor for adaptive optimizers. On the stopped time interval $t \le \tau_\epsilon^{\mathrm{blk}} \wedge \tau_E$, the Adam- or AdamW-trained trajectory admits a percolation graph satisfying Generalized Discrete Scale Invariance with the same magnification factor $\lambda^{(n)} = n^{\sigma}$ as in the SGD case; the scalar $c(\boldsymbol{\theta}_t)$ cancels in the ratio defining $\lambda^{(n)}$.

Methodology in Plain English

The authors start from the standard view that SGD can be approximated continuously by a stochastic differential equation (a stochastic gradient flow) that separates the deterministic full-batch gradient drift from zero-mean mini-batch noise. Architectural symmetries—such as the freedom to permute neurons without changing the network function—create flat, degenerate regions in parameter space that act as traps. The authors define such regions as invariant sets and formalize when a set is "stochastically attractive," meaning the inward pull of the gradient beats the outward push of the noise.

They then treat each subnetwork as a node and ask when two nodes become effectively the same, defining an equivalence relation based on the probability that both trajectories stay inside the trap. These equivalences are assembled into a Reeb graph—a topological object whose vertices are equivalence classes and whose merges and splits record the network's structural history. Because gradient noise constantly breaks and reforms these connections on a fast timescale, the authors apply a temporal renormalization over a slower timescale to collapse the fluctuations and obtain a monotone percolation graph with an edge density $p$ running from 0 to 1.

Connectivity in that graph is measured by the order parameter $\mathcal{O}(p)$, the fractional size of the largest connected component. Because symmetry forces many parameters to merge at once, the order parameter jumps rather than growing smoothly. To see these jumps despite noise-driven shifts in where they occur, the authors compute the relative variance of the order parameter across an ensemble of training seeds—reasoning that near a jump the ensemble splits bimodally between pre-jump and post-jump states, so the variance spikes. The geometric spacing of these spikes is the DSI signature. For Adam and AdamW, they add a heavy-tailed noise assumption, truncate the gradients, analyze the momentum and second-moment recursions via the one-sided z-transform, and show the preconditioner is close to a positive scalar multiple of the identity within a permutation-symmetric block—enough to preserve the trapping and cascade structure. Empirically, they replace distance-based clustering with Spectral Effective Rank, the exponentiated Shannon entropy of a weight matrix's singular value spectrum, to track soft dimensionality collapse in large networks.

Why This Matters

Impact on research. The paper reframes implicit bias as a dynamical, topological process rather than a static property of endpoints, giving a mechanistic vocabulary—percolation, Reeb graphs, order parameters, discrete scale invariance—for phenomena such as grokking that smooth-optimization accounts handle poorly. If correct, it also implies that some training transitions are genuinely discontinuous in the large-network limit, but only when merges involve macroscopic components, which sharpens what should and should not be expected to scale.

Potential real-world applications (the paper does not report deployed applications; these follow from its stated claims and suggested directions):

• Learning-rate scheduling. The authors explicitly propose using DSI variance spikes ($R_v$) to guide learning rate scheduling, which would mean scheduling driven by an online structural diagnostic rather than a fixed decay.
• Diagnosing delayed generalization. The 3-peak cascade preceding the Transformer grokking performance spike, with $\lambda = 2.11$ and an FPR of $0.1%$, suggests a monitoring signal that could flag an imminent transition before accuracy moves.
• Model compression and sparsity. Because collapse is toward sparse, low-rank representations generated by architectural symmetry, understanding when blocks merge bears on how much structure can be pruned without loss.
• Tabular and vision pipelines. The cascade is reported on UCI Heart Disease tabular classification and FMNIST image classification, indicating the diagnostic is not restricted to sequence models.

Industry relevance. The paper states that most large-scale training uses adaptive optimizers, which is exactly why the Adam and AdamW extension matters: the trapping and cascade results could apply to the optimizer actually used in production, not only to plain SGD. That said, the extension is labeled preliminary and is validated only through the grokking experiment, with a systematic study at large scale left open.

Future Directions

• Test whether the discontinuities persist at practical network widths. The authors list this explicitly, referencing Corollary C.18, which identifies the regime where the order-parameter jump survives the thermodynamic limit ($i = \Theta(N)$) versus vanishing ($i = O(1)$).
• Extend the framework to curved invariant manifolds. The current derivation relies on affine invariant sets, for which principal curvatures vanish; curved sets would require reworking the transverse diffusion analysis.
• Extend to extreme hyperparameter regimes. The stated conditions—heavy-tailed noise with $p \in (1,2]$, non-degeneracy $\hat{v}_i(\boldsymbol{\theta}t) \ge v{\min} > 0$, and block scaling $n(N)/N \to c \in (0,1]$—mark the boundaries of the current theory.
• Derive scaling laws from the percolation model. The authors connect the DSI cascade to empirical scaling laws (Remark C.26) and suggest a route to deriving new scaling relations directly from the percolation model.
• Systematically study the adaptive-optimizer extension at large scale. The AdamW extension is described as preliminary, validated through grokking only.

Target Audience

This paper is best suited to optimization researchers and theoreticians working on implicit bias, stochastic dynamics of training, and loss landscape geometry; to machine learning researchers studying grokking and delayed generalization; and to practitioners with a strong mathematical background who are interested in training diagnostics. Readers without comfort in stochastic calculus, martingale theory, and algebraic topology will find the main theoretical sections demanding, though the empirical results in Section 6 and the conceptual framing are more broadly accessible.

Authors’ abstract

We study the dynamics of Stochastic Gradient Descent (SGD), which is known to steer deep neural networks toward invariant sets that correspond to simpler subnetworks. How this steering unfolds over time remains poorly understood. We answer this by modeling the stochastic gradient flow (SGF) as a percolation process, in which architectural symmetries force subnetworks to merge in discrete simultaneous blocks rather than one at a time. These structural transitions register as variance spikes in a macroscopic order parameter, echoing physical phase transitions. We further show this trapping mechanism and its associated scaling cascade extend to Adam and AdamW under an explicit heavy-tailed noise model.