Statistical physics of computation

This course covers the statistical physics approach to computer science problems ranging from graph theory and constraint satisfaction to inference, information theory, and machine learning. In particular we will study the replica and belief propagation methods, message-passing algorithms, and analysis of the related phase transitions in several computational problems. 

Where / When

GCC330, Thursday 8:15h to 10h lecture + 10:15h to 12h exercise session.  

Teaching format

2h lecture + 2h exercise session per week. 

Lectures will be frontal, and will be recorded.

In exercise sessions (not recorded) you will work on your own on guided problem sheets that complement the lectures and allow you to practice solving problems. The professor and TA will be around to answer questions during the exercise sessions. Exercise sessions are an integral part of the course and are part of the exam's material, so we warmly encourage you to solve the exercise session problems without looking at the solutions, and to ask questions.

Recordings: 

https://mediaspace.epfl.ch/playlist/dedicated/30617/0_dtqkgjmx/0_nxzxr8m8

Moodle 

All important announcements will be posted on moodle, please keep an eye on the "Announcement" section.

For questions (even simple ones!) outside of the lectures/exercise sessions scheduled time, please use the related forum here on moodle. 

To provide us feedback, please use the "Anonymous feedback" form. If you want to refer to a specific lecture/exercise session, please add the date. Feel free to give us feedback on the selection of topics, speed of lectures, quality of lectures and of the exercise sessions. We try to take that into account to improve the course as the semester unfolds.

Content

Here is a rough outline of the course. The topics are not definitive and may change as we go.

• Introduction (1 lecture)
  
• The statistical physics toolbox: the Curie-Weiss model (1 lecture)
  
• Inference and information theoretic bounds: the spiked-Wigner model, replica theory and approximate message passing (5 lectures)
• MIDTERM
• Random matrix theory with replicas (1 lecture)
• Constraint satisfaction problems on sparse graphs (2 lectures)
• Empirical risk minimisation: compressed sensing (2 lectures)
• More on approximate message passing (1 lecture)

Notice that the content will depart significantly from last year's edition of the course, mostly being presented in a different (and hopefully better) order, and in certain cases changing completely.

Assessment method

Final written exam counting for 70% and 1 midterm during the semester counting for the other 30%. 

• Written midterm on 6th November.  Material covered: first 7 lectures, exercise sessions included.
• Written exam. Material covered: all lectures, , exercise sessions included.

The midterm and exam will try to evaluate your overall comprehension of the lecture content, including the examples and exercises seen during the exercise sessions. This includes also the ability of actually performing the computations we saw, and to generalise what you learned to previously unseen examples. 

Rules:

• Bring an ID document and your Camipro card for identification.
  
• You will be allowed to bring one A4 sheet of personal notes, recto/verso. The notes can be handwritten or printed. For the exam, no need to include the full BP equations there (lecture notes section 5.2.2): we will provide them on the exam sheet for your reference. 
  
• The midterm/exam should be written in pen (no pencil please).

Materials

The course will not follow a single book or series of lecture notes. Below are some general suggestions for resources, but more precise references will be given lecture by lecture.

• Past years lecture notes: LECTURE NOTES. These lecture notes were prepared for previous versions of this course, including a doctoral version, and cover more material than what we will cover in this semester's edition. Please do not hesitate to report mistakes, typos, inconsistencies, clarity issues.
• 2024 and 2025 SPOC class videos: VIDEOS.
• Mezard, Monanari, "Information, Physics, and Computation": LINK.
• Nishimori, "Statistical physics of spin glasses and information processing: an introduction": LINK.
• Castellani, Cavagna, "Spin glass theory for pedestrians": LINK.
• Potters, Bouchaud, "A first course in random matrix theory": LINK.

I will discuss the logistic elements of the class, and then give you an overall idea of the topics and questions we will address during the semester.

The exercise session will focus on basic but fundamental tools that you should revise: the saddle point approximation (on the real axis) and the relationship between energy, entropy and free entropy. You can also find a facultative exercise on the saddle point approximation on the complex plane.

This week we will cover the Curie Weiss model of magnetisation. We will use it to review the statistical mechanics style of analysis, the concept of phase transitions and their order, and the concept of order parameters. 

The exercise session will let you apply the same concepts to another model for magnetic material, the Blume-Capel model.

Resources: LECTURE NOTES, Chapter 1. I will not follow the exact same reasoning outlines in the notes, but the content is nonetheless very relevant. Sections 1.3, 1.4, and 1.C can be skipped. 

Nice video on the topic (with interactive simulation): https://www.youtube.com/watch?v=itRV2jEtV8Q&t=1258s

This week we will look at inference problems, and the Bayes optimal setting.

The exercise session will let you practice the new concepts, namely working with posterior distributions and the Nishimori conditions, and will make you work through a simple scalar example before we jump to the high-dimensional limit.

Resources: Chapter 7 of past years lecture notes: LECTURE NOTES. 

This week we will introduce the spiked-Wigner inference problem and see how to study it analytically with the replica method. 
The exercise session is focused on the spectral properties of the observation matrix in the spiked-Wigner model, and its relationship with inference.

Resources: Chapter 8 of past years lecture notes: LECTURE NOTES. 
For the replica method: Chapter 2 of past years lecture notes: LECTURE NOTES + Spin glass theory for pedestrians LINK.

This week we will solve the spiked-Wigner model using the replica method (only commenting on the main steps), and we will comment on the physical meaning of the resulting state equations. The exercise session guides you to redo the replica computation on your own, with all details and steps performed explicitly. 

Resources: Chapter 8 of past years lecture notes: LECTURE NOTES. 

We will use the so-called "cavity method" to re-derive the state equation for the problem, gaining some physical intuition behind the equation. The cavity method will also allow us to motivate and discuss Approximate Message Passing (AMP) algorithms next week and their state evolution equations, which are conjectured to be optimal among efficient algorithms to estimate the mean of the posterior, and to discuss algorithmic hard phases.

The exercise session will focus on solving analytically the state equation for spiked-Wigner model for Gaussian prior (as seen in the previous lecture), and solving numerically the state equation for sparse 0/1 prior using AMP's state evolution iteration scheme, observing a first order phase transition in the recovery performance.

Resources: Chapter 9 of past years lecture notes: LECTURE NOTES

This week we will motivate and discuss Approximate Message Passing (AMP) algorithms and their state evolution equations, which are conjectured to be optimal among efficient algorithms to estimate the mean of the posterior, and to discuss algorithmic hard phases. We will also go back to the previous lecture to highlight the important concepts.

The exercise session involves coding and running AMP in practice, and providing an interpretation for the BO estimator for spiked-Wigner model with Gaussian priors.

Resources: Chapter 9, 12 of past years lecture notes: LECTURE NOTES. Chapter 9 covers the cavity method and the derivation of AMP. Chapter 12 is more of an advanced read: it looks at AMP in full generality, and derives rigorously the state evolution equations. 

Below you can find the solution of the midterm. Please, go through it, and then revise/learn everything that you did not do correctly.
I consider all these questions/exercise as a showcase of the fundamental concepts we saw in class, and they are the core that you must know to pass the exam (for the content up to now, of course). Feel free to come ask questions in class, or write on moodle. 

If you would like to see your midterm, please write me a mail.

This week we will discuss random matrices. The aim will be to explain/derive analytically the spectral behaviour of Wigner matrices we observed experimentally in exercise 4. We will introduce the concept of spectral density and Stieltjes transform, and see that the latter can be interpreted yet again as a partition function of a stat mech system, allowing for explicit computations using the replica method (which you will execute in detail in the exercise session). Then, we will discuss the effect of the rank-1 spike. We will derive the so-called Baik-Ben Arous-Peché spectral transition, and explicitly verify the fact that the PCA estimator (leading eigenvector) is Bayes-optimal (which we hinted to in exercise 7).

Resources:

• Lecture notes: LECTURE NOTES. Chapter 3.
• Potters, Bouchaud, "A first course in random matrix theory": LINK. Sections 2.3, 13.1, 14.2

This week we will start speaking about factor graph representations for probability measures, and the ideas underlying the Belief Propagation algorithm, an algorithmic way to compute partition functions and marginals on sparse systems. We will derive the Belief Propagation algorithm/equations for models on general tree factor graphs and will then discuss when they can be applied on non-tree factor graphs.

The exercise session will focus on representing computational problems as factor graphs, and writing the corresponding BP equations. You will also derive the solution to the Ising model on d-regular random graphs.

Resources: Chapter 5 and 6 of past years lecture notes: LECTURE NOTES. 

This week we will introduce random constraint satisfaction problems, and will apply BP to the independent set problem that you saw in the previous exercise session in detail, and derive the corresponding SAT/UNSAT transition.

The exercise session will focus on applying BP to the matching problem, in an analogous way as to the independent set problem discussed in class.

Resources: Chapter 5 and 6 of past years lecture notes: LECTURE NOTES. 

Today we will start covering the last topic of the course: learning. We will introduce the teacher-student framework, which will allow us to study generalisation and to discuss empirical risk minimisation. We will then discuss ridge regression in detail.

The exercise session will span 2 weeks this time (so it is supposed to be worked on today and next week), and will cover in detail the replica formalism for the teacher student setting, both for the Bayes optimal estimator and for empirical risk minimisation.

Resources: Chapter 1,2 of Engel, "Statistical mechanics of learning" (LINK), and loosely Chapter 4

This week we will consider a very nice problem in sensing and inference: compressed sensing. Given a hidden (teacher) sparse vector, how many linear noiseless measurements do we need to infer back the teacher (i.e. perfect generalization)?  We will discuss the behaviour and the ideas behind 4 algorithms: Bayes optimal, empirical risk minimization (LASSO), message passing (BP/AMP) and spatially coupled BP. 

The exercise session is the continuation of exercise 12 (no new content/questions).

Resources:
- notes, ch. 16. A very similar exposition with a bit more context is given in https://arxiv.org/abs/2306.16097
- to dig deeper in the spatial coupling technique: https://arxiv.org/abs/1206.3953 (section 5 and 6), https://arxiv.org/abs/1310.2121 (for the coupling and nucleation phenomenon in curie-weiss model).

This week we will look back at the full course and highlight the major themes and topics we studied.

The exercise session involves solving last year's written exam.