Workshop on Spin Glasses

25 Sept 2022, 14:00 → 30 Sept 2022, 16:45 Europe/Zurich

David Belius (University of Basel), Erwin Bolthausen (University of Zürich), Giuseppe Genovese (University of Basel)

 

Thank you to all participants for a wonderful week!

 

Videos: After they have been edited videos of some lectures and talks will appear at https://swissmaprs.ch/videos.

 

How to get here

 

Timetable - Titles and abstracts (PDF) - Titles and abstracts (webpage)

 

The Workshop on Spin Glasses will take place in fall 2022 (25-30 September) and bring together researchers interested in spin glasses and related topics. It will feature a relaxed progamme with a limited number of extended lectures and talks with plenty of time for discussion.

 

Details of programme:

There will be four extended lectures of 3 hours, and 6 talks of 1 hour, as well as a contributed talk and poster session. The speakers are:

Extended lectures:

• Antonio Auffinger, Northwestern University
• Andrea Montanari, Stanford
• Eliran Subag, Weizmann Institute
• Lenka Zdeborova, EPFL

One hour talks:

• Emmanuel Abbé, EPFL 
• Jean Barbier, ICTP Trieste
• Ahmed El Alaoui, Cornell University
• Aukosh Jagannath, University of Waterloo
• Jean-Christophe Mourrat, ENS Lyon
• Pierfrancesco Urbani, CEA Saclay

The arrival day is Sunday, with the scientific programme starting Monday morning and running until Friday before lunch. Dinner Sunday and lunch Friday are included, and departure is on Friday afternoon.

For a list of all registered participants see the corresponding page.

Application to participate - Contributed talks and posters:

We invite applications to participate in the workshop and give a short talk or present a poster from any researchers with an interest in spin glasses and related topics. Please apply by filling out the form. The deadline for applications is November 15, 2021, and applications are considered on a rolling basis.

Location:

The location is the SwissMAP Research Station (SRS) in the ski resort Les Diablerets in the Swiss alps. The research station is newly opened venue for scientific meetings.

Accommodation:

Accommodation and meals for participants will be provided in the Hotel Les Sources, which houses the Research Station.

Cost:

There is no registration fee, and accommodation and meals are included for all participants thanks to generous financial support of SwissMAP.

Travel:

See this page for instructions. The Research Station is reachable by train from most locations in Europe, including from the airports of Geneva, Zurich and Basel, which have many international flights.

 

Organizers:

David Belius - University of Basel
Erwin Bolthausen - University of Zurich
Giuseppe Genovese - University of Zurich

 

We gratefully acknowledge the generous financial support provided by:

• SwissMAP
• Swiss National Science Foundation
• Swiss Academy of Sciences
• Swiss Mathematical Society
• International Association of Mathematical Physics

 

Note: Due to the pandemic the workshop has been postponed. The new dates are 25-30 Sept 2022, rather than 27 Feb-4 March as originally planned.

 

 

Sunday, 25 September

14:00 → 19:00 *: Arrival

19:00 → 21:00 Dinner

Monday, 26 September

08:55 → 09:00 Opening remarks

09:00 → 10:30 Algorithmic spin glass theory I

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.

Speaker: Andrea Montanari (Stanford)

10:30 → 11:00 coffee break

11:00 → 12:30 Overview of spin glass methodology in computational problems I

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.

Speaker: Lenka Zdeborova (EPFL)

12:45 → 14:15 Lunch

14:15 → 15:00 Mean-field disordered systems and Hamilton-Jacobi equation

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.

Speaker: Jean-Christophe Mourrat (ENS Lyon)

15:00 → 15:15 coffee break

15:15 → 16:00 Bayesian limits in structured PCA, and how to reach them

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.

Speaker: Jean Barbier (ICTP Trieste)

16:00 → 18:30 Poster Session

19:00 → 21:00 Dinner

Tuesday, 27 September

09:00 → 10:30 Algorithmic spin glass theory II

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.

Speaker: Andrea Montanari (Stanford)

10:30 → 11:00 coffee break

11:00 → 12:30 Overview of spin glass methodology in computational problems II

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.

Speaker: Lenka Zdeborova (EPFL)

12:45 → 14:15 Lunch

14:15 → 15:00 Learning sparse Boolean functions: neural networks need a hierarchical degree chain

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).

Speaker: Emmanuel Abbé (EPFL)

15:00 → 15:15 coffee break

15:15 → 16:00 Zero temperature mean field spin glass transitions in a field

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

Speaker: Pierfrancesco Urbani (CEA Saclay)

19:00 → 21:00 Dinner

Wednesday, 28 September

09:00 → 09:20 Phase diagram of Stochastic Gradient Descent in high-dimensional two-layer neural networks

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

Speaker: Bruno Louriero (EPFL)

09:20 → 09:40 Near optimal efficient decoding from pooled data

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.

Speaker: Noela Mueller (Eindhoven University of Technology)

09:40 → 10:00 Integrality gaps for vertex covers on sparse Bernoulli hypergraphs

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.

Speaker: Daniil Dmitriev (ETH Zurich)

10:00 → 10:20 Injectivity of ReLU networks: perspectives from integral geometry and statistical physics

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.

Speaker: Antoine Maillard (ETH Zurich)

10:30 → 11:00 coffee break

11:00 → 11:20 TAP variational principle for the constrained overlap multiple SSK model

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.

Speaker: Leon Fröber (University of Basel)

11:20 → 11:40 Vector Spin Models and Spherical Integrals

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.

Speaker: Justin Ko (ENS Lyon)

11:40 → 12:00 Landscape complexity of the elastic manifold

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.

Speaker: Benjamin McKenna (Harvard University)

12:00 → 12:20 Triviality of the Ising SK TAP energy up to the AT line

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.

Speaker: Francesco Concetti (University of Basel)

12:45 → 14:15 Lunch

14:15 → 19:00 *: free afternoon

19:00 → 21:00 Dinner

Thursday, 29 September

09:00 → 10:30 Parisi measures and the p+s spherical model I

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.

Speaker: Antonio Auffinger (Northwestern University)

10:30 → 11:00 coffee break

11:00 → 12:30 Free energy landscapes and a generalized TAP approach I

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.

Speaker: Eliran Subag (Weizmann Institute)

12:45 → 14:15 Lunch

14:15 → 15:00 Sampling from the SK measure via algorithmic stochastic localization

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.

Speaker: Ahmed El Alaoui (Cornell University)

15:00 → 15:15 coffee break

15:15 → 16:00 Replica Symmetry Breaking, Shattering, and Metastability

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)

Speaker: Aukosh Jagannath (University of Waterloo)

19:00 → 21:00 Dinner

Friday, 30 September

09:00 → 10:30 Parisi measures and the p+s spherical model II

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.

Speaker: Antonio Auffinger (Northwestern University)

10:30 → 11:00 coffee break

11:00 → 12:30 Free energy landscapes and a generalized TAP approach II

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.

Speaker: Eliran Subag (Weizmann Institute)

12:45 → 14:15 Lunch

14:15 → 15:15 *: Departure