On Zeros and Algorithms for Disordered Systems II: The Antiferromagnetic Ising Model up to Kesten-Stigum
Ferenc Bencs, Brice Huang, Daniel Z. Lee, Kuikui Liu, Guus Regts
AI 速览：作者提出首个在均匀随机 d-正则图上、对反铁磁 Ising 模型在直至 Kesten-Stigum 阈值的全部逆温度范围内以任意高精度估计配分函数的多项式时间算法。
We give the first polynomial-time algorithm to estimate the partition function of the antiferromagnetic Ising model on the uniformly random $d$-regular graph to arbitrarily high accuracy for all inverse temperatures up to the Kesten-Stigum threshold. This is the entire regime in which the model is "replica symmetric," and is conjectured to be optimal for polynomial-time counting and sampling. To achieve our algorithmic result, we establish the absence of Fisher zeros for the partition function in a constant-width strip around the interval from $0$ up to the Kesten-Stigum threshold, with high probability over the randomness of the input graph. AI Disclosure: The overarching vision and proof architecture were developed solely by the authors without AI input. GPT 5.5 Pro was used, with extensive guidance from the authors, for only a few minor technical aspects of the proof. The authors independently verified correctness and wrote everything by hand. We take full responsibility for its contents. A more detailed statement can be found in Section 1.2.
While universal approximation theorems theoretically underpin the representation capabilities of machine learning models, they have two shortcomings: They do not focus on efficient representations and they tend to be insensitive to depth and other heuristically important properties. In this work we show that these two shortcomings are intertwined. We prove that machine learning models which are deeper or have higher-order interactions can efficiently represent a larger set of functions, i.e. have larger efficient reach. It follows that deep Boltzmann machines (DBMs) have maximal efficient reach, restricted Boltzmann machines (RBMs) sub-maximal, and k-body generalizations of RBMs form a hierarchy between the two, even though all are universal. More generally, (i) we provide a full characterization of machine learning models with maximal efficient reach; (ii) we derive separations between deep and shallow models for three representation tasks; and (iii) we prove that the efficient reach of shallow models constitutes an infinite hierarchy indexed by the interaction order. The proofs draw on different methodologies, namely on (i) a recent characterization of universal spin models; (ii) computational complexity bounds for spin models; and (iii) communication complexity bounds applied to shallow models. This work shows that universal machine learning models can strongly differ in their efficient representation capabilities, and provides a theoretical foundation for heuristic observations.
Gradient descent with momentum can be viewed as a particle moving with friction in the loss landscape. In deep learning the learning rate is usually large, so training is a discrete dynamical system: in many full-batch experiments the sharpness grows to the optimizer's stability limit, the edge of stability (EoS), and training continues there. Physics-inspired optimizers change this motion; Velocity-Regularized Adam (VRAdam), for example, shrinks the step at high speed. We study kinetic maps, in which the step is the gradient of a kinetic energy of the momentum, and ask what they do beyond the EoS. (i) In a reduced model, a kinetic map creates a symmetric period-two orbit beyond the edge, strictly linearly stable if and only if the map's elasticity (the log-log slope of step length versus momentum) lies between 0 and 1; on it, training sits at an effective edge of stability. VRAdam's damper fails above twice the critical learning rate, where its kinetic energy is not convex; the Legendre dual of VRAdam's own Lagrangian is convex and passes at every learning rate. (ii) Because the sharpness rises gradually, the loss of stability is delayed, as in Neishtadt's theory of slowly swept bifurcations. In a network with a controlled sweep, the dynamics match this theory without fitted parameters, including the memory of where the sweep started and its erasure by noise. (iii) With momentum, reaching the oscillation also requires elasticity at large momentum: maps that bound the step have competing period-four and chaotic attractors already at beta1 = 0.9, while the cubic-Legendre map reached the oscillation from every sampled start up to beta1 = 0.99. Experiments on an exact quadratic problem, a full-batch MLP and ResNet-32 support the theory; on ResNet-18, much of the apparent benefit of the maps is reproduced by matching the effective learning rate.
Allowing for small fraction of errors in retrieved stored binary patterns, Hopfield-Hebbian neural network (NN) associative memory dynamics [14] achieves linearly scaled capacity. The famous proportionality constant $α_c\approx 0.14$ is obtained in a large dimensional scenario as the ratio of the number of reliably stored patterns $m$ and the patterns' length $n$ under the assumption that uniformly randomly chosen binary patterns are \emph{independent} among themselves. While such an idealized scenario is now well understood, more practical scenarios with correlated/noisy datasets remaining challenging even for classical statistical mechanics replica approaches. We consider precisely such practical settings where each \emph{archetype} pattern is replaced with $M$ correlated \emph{examples} with parameter $r$ governing the quality of correlation. We develop a powerful Random Duality Theory (RDT) based framework to analyze correlated data and already on the first level of RDT lifting obtain capacity characterizations that remarkably well match behavior exhibited through simulated dynamics. Moreover, characterizations explicitly feature correlation parameters $M$ and $r$, which allows to precisely determine their effects on phase-transitioning behavior of the underlying dynamics. Our results are also a well-fitting complement to the existing literature. Namely, to circumvent challenging statistical mechanics analyses, an alternative combination of spectral and replica methods is considered in [4]. We confirm that [4]'s elegant spectral characterizations are excellent approximations in the low correlated regime. At the same time, we also close the gap in the regimes with higher correlation levels where spectral methods deviate from the practical dynamics performance.
Stationary learning admits an ideal-gas description under restrictive noise assumptions. In neural networks whose gradient noise departs from these assumptions, however, an entropy-scaling relation resembling a Maxwell relation remains approximately valid. We ask which thermodynamic-looking relations follow from scale symmetry rather than equilibrium, and how departures from the ideal-gas description can be quantified, for discrete stochastic gradient dynamics with memory. An exact rescaling of trajectories explains the entropy relation without assuming thermal equilibrium. Within a local harmonic approximation, self-adjusting weight norms yield a spectral equation of state whose virial coefficients are set by moments of the curvature spectrum, and coupled parameter groups can sustain stationary probability currents. Our central result beyond this approximation is an exact curvature-transport identity. Together with a finite-step loss balance, it decomposes corrections to the harmonic fluctuation relation into measurable curvature changes, finite-step remainders, gradient-memory correlations and finite-window drift terms. A related displacement-weighted curvature change provides a diagnostic of the arrow of time; its mean and second moment give a lower bound on the relative entropy between forward and reversed state pairs. We also calculate the activation-boundary contribution to curvature for rectified teacher-student networks with Gaussian inputs. Tests in sphere models, teacher-student networks and convolutional networks on CIFAR-10 and CIFAR-100 support the transport description and identify limits of the harmonic and cubic-remainder approximations. These results separate symmetry-based relations from equilibrium assumptions and provide quantitative diagnostics of nonideal fluctuations in learning dynamics.
Tony Bonnaire, Raphaël Urfin, Giulio Biroli, Marc Mézard
Diffusion models have achieved remarkable success across a wide range of generative tasks. A key challenge is understanding the mechanisms that prevent their memorization of training data and allow generalization. In this work, we investigate the role of the training dynamics in the transition from generalization to memorization. Through extensive experiments and theoretical analysis, we identify two distinct timescales: an early time $τ_\mathrm{gen}$ at which models begin to generate high-quality samples, and a later time $τ_\mathrm{mem}$ beyond which memorization emerges. Crucially, we find that $τ_\mathrm{mem}$ increases linearly with the training set size $n$, while $τ_\mathrm{gen}$ remains constant. This creates a growing window of training times with $n$ where models generalize effectively, despite showing strong memorization if training continues beyond it. It is only when $n$ becomes larger than a model-dependent threshold that overfitting disappears at infinite training times. These findings reveal a form of implicit dynamical regularization in the training dynamics, which allow to avoid memorization even in highly overparameterized settings. Our results are supported by numerical experiments with standard U-Net architectures on realistic and synthetic datasets, and by a theoretical analysis using a tractable random features model studied in the high-dimensional limit.
We obtain an analytic, interpretable and predictive theory of creativity in convolutional diffusion models. Indeed, score-matching diffusion models can generate highly original images that lie far from their training data. However, optimal score-matching theory suggests that these models should only be able to produce memorized training examples. To reconcile this theory-experiment gap, we identify two simple inductive biases, locality and equivariance, that: (1) induce a form of combinatorial creativity by preventing optimal score-matching; (2) result in fully analytic, completely mechanistically interpretable, local score (LS) and equivariant local score (ELS) machines that, (3) after calibrating a single time-dependent hyperparameter can quantitatively predict the outputs of trained convolution only diffusion models (like ResNets and UNets) with high accuracy (median $r^2$ of $0.95, 0.94, 0.94, 0.96$ for our top model on CIFAR10, FashionMNIST, MNIST, and CelebA). Our model reveals a locally consistent patch mosaic mechanism of creativity, in which diffusion models create exponentially many novel images by mixing and matching different local training set patches at different scales and image locations. Our theory also partially predicts the outputs of pre-trained self-attention enabled UNets (median $r^2 \sim 0.77$ on CIFAR10), revealing an intriguing role for attention in carving out semantic coherence from local patch mosaics.
How diffusion models generalize beyond their training set is not known, and is somewhat mysterious given two facts: the optimum of the denoising score matching (DSM) objective usually used to train diffusion models is the score function of the training distribution; and the networks usually used to learn the score function are expressive enough to learn this score to high accuracy. We claim that a certain feature of the DSM objective -- the fact that its target is not the training distribution's score, but a noisy quantity only equal to it in expectation -- strongly impacts whether and to what extent diffusion models generalize. In this paper, we develop a mathematical theory that partly explains this 'generalization through variance' phenomenon. Our theoretical analysis exploits a physics-inspired path integral approach to compute the distributions typically learned by a few paradigmatic under- and overparameterized diffusion models. We find that the distributions diffusion models effectively learn to sample from resemble their training distributions, but with 'gaps' filled in, and that this inductive bias is due to the covariance structure of the noisy target used during training. We also characterize how this inductive bias interacts with feature-related inductive biases.
Jascha Sohl-Dickstein, Eric A. Weiss, Niru Maheswaranathan, Surya Ganguli
A central problem in machine learning involves modeling complex data-sets using highly flexible families of probability distributions in which learning, sampling, inference, and evaluation are still analytically or computationally tractable. Here, we develop an approach that simultaneously achieves both flexibility and tractability. The essential idea, inspired by non-equilibrium statistical physics, is to systematically and slowly destroy structure in a data distribution through an iterative forward diffusion process. We then learn a reverse diffusion process that restores structure in data, yielding a highly flexible and tractable generative model of the data. This approach allows us to rapidly learn, sample from, and evaluate probabilities in deep generative models with thousands of layers or time steps, as well as to compute conditional and posterior probabilities under the learned model. We additionally release an open source reference implementation of the algorithm.