Algorithmic spin glass theory I

• Andrea Montanari (Stanford)

A substantial amount of mathematical work has been devoted to studying structural properties of mean-field spin glasses, and in particular, geometric properties of the Gibbs measure. Over the last ten years, ideas from spin glass theory have spurred dramatic advances in the field of random combinatorial optimization and random constraint satisfaction problems (CSPs), allowing to characterize some key structural properties of the latter (eg the satisfiability threshold in random CSPs). Can spin glass ideas also lead to the construction of efficient algorithms for these problems? I will describe recent progress on the last question.

Overview of spin glass methodology in computational problems I

• Lenka Zdeborova (EPFL)

In this mini-lecture, I will give a subjective overview of some of the main application areas of methods from spin glasses in computational problems. We will see how to view a variety of problems studied in combinatorics, optimization, inference and learning under the same umbrella. Paying attention to what is known mathematically rigorously, I will discuss both the statistical (static) and algorithmic (dynamical) results that are known for two specific settings encompassing a broad range of applications -- the low-rank matrix estimation and the generalized linear model. I will also present numerous associated open questions.

Mean-field disordered systems and Hamilton-Jacobi equation

• Jean-Christophe Mourrat (ENS Lyon)

A new approach to the identification of the limit free energy of mean-field disordered systems, based on Hamilton-Jacobi equations, has started to emerge. The goal of this talk will be to review the results obtained so far with this method, as well as the challenges ahead. The models considered will be either fully connected spin glasses, or models from statistical inference, including the community detection problem on a random graph with bounded average degree. Based on joint works with Hong-Bin Chen, Tomás Dominguez, and Jiaming Xia.

Bayesian limits in structured PCA, and how to reach them

• Jean Barbier (ICTP Trieste)

I will present recent results concerning the Bayesian estimation of low-rank matrices corrupted by structured noise, namely rotational invariant noise with generic spectrum. Using the replica method we derive the optimal performance limit. This is possible by exploiting the low-rank structure of the matrix signal implying that we can reduce the model to an effective quadratic model of the Ising type. Secondly, we show that the Approximate Message Passing (AMP) algorithm currently proposed in the literature for Bayesian estimation is sub-optimal. Exploiting the theory of Adaptive Thouless-Anderson-Palmer equations by Opper et al. we explain the reason for this sub-optimality and as a consequence we deduce an optimal Bayesian AMP algorithm with a rigorous state evolution matching the replica prediction.

Algorithmic spin glass theory II

• Andrea Montanari (Stanford)

A substantial amount of mathematical work has been devoted to studying structural properties of mean-field spin glasses, and in particular, geometric properties of the Gibbs measure. Over the last ten years, ideas from spin glass theory have spurred dramatic advances in the field of random combinatorial optimization and random constraint satisfaction problems (CSPs), allowing to characterize some key structural properties of the latter (eg the satisfiability threshold in random CSPs). Can spin glass ideas also lead to the construction of efficient algorithms for these problems? I will describe recent progress on the last question.

Overview of spin glass methodology in computational problems II

• Lenka Zdeborova (EPFL)

In this mini-lecture, I will give a subjective overview of some of the main application areas of methods from spin glasses in computational problems. We will see how to view a variety of problems studied in combinatorics, optimization, inference and learning under the same umbrella. Paying attention to what is known mathematically rigorously, I will discuss both the statistical (static) and algorithmic (dynamical) results that are known for two specific settings encompassing a broad range of applications -- the low-rank matrix estimation and the generalized linear model. I will also present numerous associated open questions.

Learning sparse Boolean functions: neural networks need a hierarchical degree chain

• Emmanuel Abbé (EPFL)

We consider the problem of learning sparse functions with uniform inputs on the Boolean hypercube. It is shown that algorithms based on the training of 2-layer mean-field neural networks with stochastic gradient descent can “optimally” learn such functions “iff" the function has a hierarchical property called the staircase property, which consists of having chains in the Fourier coefficients of increasing degree. This implies two separation results: (i) such neural networks outperform kernel methods, (ii) SQ algorithms outperform such neural networks. Based on joint works with E. Boix (MIT) and T. Misiakiewicz (Stanford).

Zero temperature mean field spin glass transitions in a field

• Pierfrancesco Urbani (CEA Saclay)

I will consider a recently introduced soft spin glass model, named the KHGPS model, in which soft spins are subjected to a local random anharmonic quartic potential and an external magnetic field, and interact through the usual SK-like random pairwise term. Depending on the control parameters, at zero temperature the model undergoes to a spin glass transition that can be in two different universality classes. In the first universality class, at the transition, the spin glass susceptibility is divergent. Approaching the critical point from the simple (replica symmetric) phase, the ground state gets a fat tail of soft modes in the spectrum of the Hessian and therefore the transition is driven by an abundance of soft linear excitations. On the other hand one can have a transition where, coming from the simple phase, the spin glass susceptibility is not divergent. In this case the transition is driven by the appearance of a finite density of non-linear excitations which are captured by full replica symmetry breaking and not by the Hessian analysis. I will discuss how these mechanisms change in finite dimensions and develop a zero temperature field theory to address this problem and discuss its universal properties. Based on the following works: Bouchbinder, Lerner, Rainone, Urbani, Zamponi, Phys. Rev. B 103, 174202 (2021) Folena, Urbani, J. Stat. Mech. (2022) 053301 Urbani 2022 J. Phys. A: Math. Theor. 55 335002

Phase diagram of Stochastic Gradient Descent in high-dimensional two-layer neural networks

• Bruno Louriero (EPFL)

Despite the non-convex optimization landscape, over-parametrized shallow networks are able to achieve global convergence under gradient descent. The picture can be radically different for narrow networks, which tend to get stuck in badly-generalizing local minima. Here we investigate the cross-over between these two regimes in the high-dimensional setting, and in particular investigate the connection between the so-called mean-field/hydrodynamic regime and the seminal approach of Saad & Solla. Focusing on the case of Gaussian data, we study the interplay between the learning rate, the time scale, and the number of hidden units in the high-dimensional dynamics of stochastic gradient descent (SGD). Our work builds on a deterministic description of SGD in high-dimensions from statistical physics, which we extend and for which we provide rigorous convergence rates. Based on: https://arxiv.org/abs/2202.00293

Near optimal efficient decoding from pooled data

• Noela Mueller (Eindhoven University of Technology)

Consider n items, each of which is characterized by one of d+1 possible features in {0,...,d}. We study the inference task of learning these types by queries on subsets, or pools, of the items that only reveal a form of coarsened information on the features - in our case, the sum of all the features in the pool. Related prominent problems are the quantitative group testing problem, of which it is a generalization, as well as the compressed sensing problem, of which it is a special case. We are interested in the minimum number of queries needed to efficiently infer the features, in the setting where the feature vector is chosen uniformly while fixing the frequencies, and one of the features, say 0, is dominant in the sense that the number k = n θ, θ ∈ (0, 1), of non-zero features among the items is much smaller than n. It is known that in this case, all features can be recovered in exponential time using no more than O(k) queries. However, so far, all efficient inference algorithms required at least Ω(k ln) queries, and it was unknown whether this gap is artificial or of a fundamental nature. We provide an efficient algorithm that succeeds with high probability and employs no more than O(k) measurements. This also solves a prominent open question for the quantitative group testing problem. This is joint work with Max Hahn-Klimroth.

Integrality gaps for vertex covers on sparse Bernoulli hypergraphs

• Daniil Dmitriev (ETH Zurich)

For the standard vertex cover problem, linear relaxation has integrality gap 2. In our work, we explore an extension of this problem by considering i) random hyperedges and ii) low degree vertices. We conjecture the value of the integrality gap and prove almost tight upper and lower bounds. Based on joint work with N. Grometto, G. Arpino, R. Barboni and A. Bandeira.

Injectivity of ReLU networks: perspectives from integral geometry and statistical physics

• Antoine Maillard (ETH Zurich)

We consider the well-posedness of inferring the input of a randomly-initialized large ReLU neural network from its output, i.e. characterizing injectivity. Focusing on layerwise injectivity properties, we discuss recent work connecting this question to spherical integral geometry, and present a conjecture for a sharp injectivity threshold (in terms of the expansivity of the layer) based on a transition in the expected Euler characteristic of a particular random set. Showing that injectivity is also equivalent to a property of the ground state of a spherical perceptron in statistical physics, we then leverage the non-rigorous replica symmetry breaking theory to obtain analytical equations satisfied by the injectivity threshold. Efficiently solving the zero-temperature full replica symmetry breaking equations yields a conjectured threshold at odds with the integral geometry approach described above. Finally, using a classical approach based on Gordon's min-max theorem, we show that the replica symmetric calculation, although non-exact, can already disprove the Euler characteristic threshold, leaving open to understand the discrepancy between these predictions.

TAP variational principle for the constrained overlap multiple SSK model

• Leon Fröber (University of Basel)

Spin glass models involving multiple replicas with constrained overlaps have been studied by (among others) Franz, Parisi, Talagrand, Panchenko and Ko. The latter three authors have shown that the limiting free energy is given by a Parisi type minimization. In this talk we will discuss how for the spherical Sherrington-Kirkpatrick (SSK, i.e. 2−spin) model it can also be expressed in terms of a TAP variational principle. The derived variational formula confirms that this model is replica symmetric, a fact which is natural but not obvious from the Parisi formula for the model. Joint work with David Belius and Justin Ko.

Vector Spin Models and Spherical Integrals

• Justin Ko (ENS Lyon)

In this talk we consider the asymptotics of spherical integrals of sublinear rank. In this regime, the spherical integrals are approximately the products of 1-dimensional spherical integrals. This extends the results for finite dimensional spherical integrals proven by Guionnet, Husson and Maïda. These spherical integrals will allow us to study the spherical SK vector spin model when the number of replicas are dependent on the dimension. This is joint work with Jonathan Husson.

Landscape complexity of the elastic manifold

• Benjamin McKenna (Harvard University)

The Kac-Rice formula allows one to study the complexity of high-dimensional Gaussian random functions (meaning asymptotic counts of critical points) via the determinants of large random matrices. We present new results on determinant asymptotics for non-invariant random matrices, and use them to compute the (annealed) complexity of the elastic manifold. This is a classical disordered elastic system, studied for example by Fisher (1986) in fixed dimension, and by Mézard and Parisi (1992) in the high-dimensional limit. We confirm recent formulas of Fyodorov and Le Doussal (2020) on the model in the Mézard-Parisi setting, identifying the boundary between simple and glassy phases. Joint work with Gérard Ben Arous and Paul Bourgade.

Triviality of the Ising SK TAP energy up to the AT line

• Francesco Concetti (University of Basel)

We study the (weak) triviality of the Ising Sherrington-Kirkpatrick TAP energy in the high temperature regime, up to the AT line. Applying the Kac-Rice formula and large deviation techniques, we obtain a variational formula for the TAP complexity of the form sup(q,A)∈[0,1]×R G(q, A) for certain function G(q, A). For any β and h, we consider the solution (q∗, A∗) of the usual fixed point equa- tion for this model. We prove that (q∗, A∗) is a local maximum of the complexity function G(q, A) up to the AT line, and G(q∗, A∗) = 0. Moreover, we prove that for β and h satisfying the AT condition the global maximum of G(q, A) is located in a compact set around (q∗, A∗). Hereupon, for many combinations of β, h up to the AT line, we check numerically that that the global maximum in the compact set is indeed (q∗, A∗), confirming that the TAP complexity is 0. Joint work with David Belius and Giuseppe Genovese.

Parisi measures and the p+s spherical model I

• Antonio Auffinger (Northwestern University)

In these lectures, we will overview the tools used to analyze the functional ordered parameter of mean field spin glasses at positive and zero temperature. We will also describe recent results on the p+s spherical model.

Free energy landscapes and a generalized TAP approach I

• Eliran Subag (Weizmann Institute)

In their seminal `77 paper, Thouless, Anderson and Palmer (TAP) proposed their famous free energy for the SK model. The main focus of these talks is a related but different free energy, whose definition is guided in a natural way by properties of the Gibbs measure. It was introduced for spherical mixed p-spin models (arXiv:1804.10576) and in a joint work with Wei-Kuo Chen and Dmitry Panchenko (arXiv:1812.05066) for Ising models, and I will discuss both types of models in a unified way. Like the TAP free energy, this free energy is a function defined over the convex hull of the configuration space, which is equal to the energy plus a deterministic function. Under some conditions it coincides with the TAP free energy, but in general it only lower bounds it. It satisfies two principles: 1. its maximum over certain radii is equal to the free energy of the model; 2. its maximizers are exactly the barycenters of pure/ancestral states, or subsets that are similar to them in an appropriate sense. The first principle yields a different representation for the free energy for any overlap in the support of the limiting overlap distribution (the order parameter), that generalizes the TAP representation which only corresponds to the largest overlap in the support. If time permits, I will also discuss important properties of this free energy like uniform concentration (self-averaging), its value on the vertices of the ultrametric tree, and how it can be used to compute the free energy of the spherical pure p-spin models and their multi-species version. Based in part on a joint work with Wei-Kuo Chen and Dmitry Panchenko.

Sampling from the SK measure via algorithmic stochastic localization

• Ahmed El Alaoui (Cornell University)

I will present an algorithm which efficiently samples from the Sherrington-Kirkpatrick measure with no external field at high temperature. The approach uses a discretized version of the stochastic localization process of Eldan, together with a subroutine for computing the mean vector, or magnetization, of a family of SK measures tilted by an appropriate external field. Our analysis shows that the algorithm outputs a sample with vanishing rescaled Wasserstein distance to the SK measure, for all inverse temperatures beta < 1/2. In a recent development, Celentano (2022) shows that our algorithm succeeds up to the critical temperature beta < 1. Conversely, we show that in the RSB regime beta >1, no 'stable' algorithm can approximately sample from the SK measure. This crucially exploits the property of disorder chaos exhibited by SK in this regime. This settles the computational tractability of sampling from SK for all temperatures except the critical one. This is based on a joint work with Andrea Montanari and Mark Sellke.

Replica Symmetry Breaking, Shattering, and Metastability

• Aukosh Jagannath (University of Waterloo)

The statics and dynamics of mean-field models of spin glasses have been studied in-depth by the physics community since the '70s. At the heart of this is the trade-off between the notions of replica symmetry breaking, shattering, and metastability. I will survey the current mathematical understanding of these ideas in the “simple” case of the spherical p-spin model. I will start by recalling how the landscape complexity can be used to understand of the “replica symmetry breaking” phase following the work of Auffinger–Ben Arous–Cerny and Subag. I'll then turn to our recent joint work with Ben Arous on the “replica symmetric” phase. Here we prove the existence of a shattering phase and show that metastable states exist up to an even higher temperature as predicted by Barrat–Burioni–Mezard. This latter work is based on a Thouless–Anderson–Palmer decomposition which builds on the ideas of Subag. I will end by presenting a series of open questions and conjectures surrounding sharp phase boundaries for shattering and metastability. This talk will touch on joint work with: A. Auffinger (Northwestern), G. Ben Arous (Courant), R. Gheissari (Northwestern), and I. Tobasco (UIC)

Parisi measures and the p+s spherical model II

• Antonio Auffinger (Northwestern University)

In these lectures, we will overview the tools used to analyze the functional ordered parameter of mean field spin glasses at positive and zero temperature. We will also describe recent results on the p+s spherical model.

Free energy landscapes and a generalized TAP approach II

• Eliran Subag (Weizmann Institute)

In their seminal `77 paper, Thouless, Anderson and Palmer (TAP) proposed their famous free energy for the SK model. The main focus of these talks is a related but different free energy, whose definition is guided in a natural way by properties of the Gibbs measure. It was introduced for spherical mixed p-spin models (arXiv:1804.10576) and in a joint work with Wei-Kuo Chen and Dmitry Panchenko (arXiv:1812.05066) for Ising models, and I will discuss both types of models in a unified way. Like the TAP free energy, this free energy is a function defined over the convex hull of the configuration space, which is equal to the energy plus a deterministic function. Under some conditions it coincides with the TAP free energy, but in general it only lower bounds it. It satisfies two principles: 1. its maximum over certain radii is equal to the free energy of the model; 2. its maximizers are exactly the barycenters of pure/ancestral states, or subsets that are similar to them in an appropriate sense. The first principle yields a different representation for the free energy for any overlap in the support of the limiting overlap distribution (the order parameter), that generalizes the TAP representation which only corresponds to the largest overlap in the support. If time permits, I will also discuss important properties of this free energy like uniform concentration (self-averaging), its value on the vertices of the ultrametric tree, and how it can be used to compute the free energy of the spherical pure p-spin models and their multi-species version. Based in part on a joint work with Wei-Kuo Chen and Dmitry Panchenko.