Workshop on Spin Glasses

Contribution List

10. Algorithmic spin glass theory I

Andrea Montanari (Stanford)

26/09/2022, 09:00

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

12. Overview of spin glass methodology in computational problems I

Lenka Zdeborova (EPFL)

26/09/2022, 11:00

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

1. Mean-field disordered systems and Hamilton-Jacobi equation

Jean-Christophe Mourrat (ENS Lyon)

26/09/2022, 14:15

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

2. Bayesian limits in structured PCA, and how to reach them

Jean Barbier (ICTP Trieste)

26/09/2022, 15:15

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

11. Algorithmic spin glass theory II

Andrea Montanari (Stanford)

27/09/2022, 09:00

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

13. Overview of spin glass methodology in computational problems II

Lenka Zdeborova (EPFL)

27/09/2022, 11:00

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

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

Emmanuel Abbé (EPFL)

27/09/2022, 14:15

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

4. Zero temperature mean field spin glass transitions in a field

Pierfrancesco Urbani (CEA Saclay)

27/09/2022, 15:15

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

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

Bruno Louriero (EPFL)

28/09/2022, 09:00

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

20. Near optimal efficient decoding from pooled data

Noela Mueller (Eindhoven University of Technology)

28/09/2022, 09:20

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

9. Integrality gaps for vertex covers on sparse Bernoulli hypergraphs

Daniil Dmitriev (ETH Zurich)

28/09/2022, 09:40

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.

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

Antoine Maillard (ETH Zurich)

28/09/2022, 10:00

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

23. TAP variational principle for the constrained overlap multiple SSK model

Leon Fröber (University of Basel)

28/09/2022, 11:00

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

22. Vector Spin Models and Spherical Integrals

Justin Ko (ENS Lyon)

28/09/2022, 11:20

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

24. Landscape complexity of the elastic manifold

Benjamin McKenna (Harvard University)

28/09/2022, 11:40

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

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

Francesco Concetti (University of Basel)

28/09/2022, 12:00

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

17. Parisi measures and the p+s spherical model I

Antonio Auffinger (Northwestern University)

29/09/2022, 09:00

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.

15. Free energy landscapes and a generalized TAP approach I

Eliran Subag (Weizmann Institute)

29/09/2022, 11:00

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

6. Sampling from the SK measure via algorithmic stochastic localization

Ahmed El Alaoui (Cornell University)

29/09/2022, 14:15

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

7. Replica Symmetry Breaking, Shattering, and Metastability

Aukosh Jagannath (University of Waterloo)

29/09/2022, 15:15

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

18. Parisi measures and the p+s spherical model II

Antonio Auffinger (Northwestern University)

30/09/2022, 09:00

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.

16. Free energy landscapes and a generalized TAP approach II

Eliran Subag (Weizmann Institute)

30/09/2022, 11:00

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