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

CO120, Thursday 13h to 15h lecture + 15h to 17h exercise session. Lectures will be from 13:15 to 14 and from 14:14 to 15. 

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, and to ask questions.

For questions outside of the lectures/exercise sessions scheduled time, please use the related forum here on moodle.

Content

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

• Introduction to statistical physics of computation: 2 lectures
  
• Replica method and the storage problem: 3 lectures
  
• Belief propagation and constraint satisfaction problems: 3 lectures
  
• Inference: 3 lectures
  
• Learning and generalisation: 3 lectures
  

Assessment method

Final written exam counting for 50% and 2 graded homework during the semester counting for the other 50%. Below you can find the expected dates for the graded homework: they may change, and more informations on the rules and grading policies will be provided later. Both graded homework will cover all the material seen at lecture and in exercise sessions up to the homework's date.

• First graded homework: week 5 (assigned 7/10/2024, to submit by 14/10/2024 end of day).
• Second graded homework: week 11 (assigned 25/11/2024, to submit by 2/12/2024 end of day).

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 SPOC class videos: VIDEOS.
• Mezard, Monanari, "Information, Physics, and Computation": LINK.
• Engel, "Statistical mechanics of learning": LINK.
• Nishimori, "Statistical physics of spin glasses and information processing: an introduction": LINK.

This week we will have a short introductory lecture (1h), and a longer exercise session (3h).

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, the relationship between energy, entropy and free entropy and the central limit theorem. 

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. 

This week we will start studying our first computational problem: the storage problem. We will map it on a statistical mechanics problem, look in detail at the concept of disorder, and set up the computation of an associated partition function. To this end, we will introduce the replica method.

The exercise session will focus on learning how to map constraint satisfaction problems onto statistical mechanics models.

Resources: 

• I will very loosely present some parts of Chapter 6 of Engel, "Statistical mechanics of learning": LINK. Chapter 2 and Appendix 2 will also be useful.
  
• ArXiv:0505032 is a very nice introduction to spin glass physics. Section 1 and 2 are a useful complementary reading to the lecture.
  

This week we will continue studying the storage problem, and we will derive the state equation for its order parameter using the replica method.

The exercise session will focus on some computational steps of the replica computation that we will not see in the lecture, as well as seeing how from a difficult state equation we can still extract analytical informations about phase transitions.

Resources: 

• Same as previous week
• Detailed notes on the replica computation

This week we will try to gain some physical intuition on the overlap order parameter that appeared in the replica computation (and which will appear in every non-trivial replica computation), and the related replica-symmetric (RS) ansatz. We will then discuss the binary storage problem, see how within replica theory one can assess the validity of the RS ansatz, and how to deal with broken replica symmetry.

The exercise session is dedicated to the graded homework. Exercise 5.1 reviews some classical statistical mechanics without disorder. Exercise 5.2 showcases the fact that replica computations are "compositional", meaning that changing some ingredient of the problem alters the replica computation only in certain aspects.

Resources: 

• Sections 2.5, 2.6, 2.7 and 3.3 of ArXiv:0505032 are useful to understand a bit better the physical meaning of the overlap.
  
• Section 6.3 of Engel, "Statistical mechanics of learning" (LINK) discusses more in detail the binary storage problem. I highly recommend that you read through it even if I will not cover all the aspects of replica theory mentioned there in class.

This week we will move away from the random label problem, and introduce the teacher-student framework, which will allow us to study generalisation and different learning algorithms.

The exercise session will focus on adapting the random label replica computation to the teacher-student setting. You will see that the new replica computation is, again, a minor variation of the computation we did in lecture 4. You will also derive an expression for the generalisation error of a specific learning rule, the Gibbs sampling. Finally, you will code a solver for the state equations to be able to actually plot the overlap and generalisation error as a function of the points/dimension ratio alpha.

Resources: 

• Chapter 1,2 of Engel, "Statistical mechanics of learning" (LINK).
  

This week we will look at how one can solve the classification problem in the teacher-student setting with empirical risk minimisation, and how to study this within the framework of statistical mechanics.

The exercise session will cover empirical risk minimisation for the classification of randomly labelled points.

Resources: 

• Very loosely Chapter 4 (in particular sections 4.3 and 4.4) of Engel, "Statistical mechanics of learning" (LINK).

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 look at one inference problem in high dimension, the spiked-Wigner model. We will set up replica theory for this problem, and study two phenomenologically different priors on the signal. For Gaussian prior, we will observe a second order phase transition (the Baik-Ben Arous-Péché transition). For sparse-Gaussian prior, we will observe a first order phase transition, at the core of computational-to-information-theoretic gaps.

The exercise session will focus on actually performing the associated replica computation.

Resources: 

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

This week we will continue looking at the spiked-Wigner model in high dimension. 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 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.

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. 

This week we will wrap up the discussion on AMP and hard phases by looking at last lecture material a bit more calmly.

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

Resources: 

• Chapter 5 of past years lecture notes: LECTURE NOTES. 

This week we will derive the Belief Propagation algorithm/equations for models on general tree factor graphs. We will then discuss when they can be applied on non-tree factor graphs, and showcase the Ising model on d-regular random graphs as an example.

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 discussed in the lecture.

Resources: 

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

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

Then, we will discuss the coloring problem, and its replica-symmetry-broken phase diagram. We will introduce the concept of complexity and clustered phases, and briefly discuss how to compute the free entropy in such phases.

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: I am listing a lot of content here. I do not expect you to read everything, I am just pointing out where to go to find additional information.

• Chapter 5 and 6 of past years lecture notes for the independent set problem: LECTURE NOTES. 
• Chapter 6.1, 6.2, 6.6 of past years lecture notes for the introduction to graph coloring
• Chapter 13/14 for the phase diagram of coloring, complexity, 2-level BP
• Chapter 15 for an example of RSB and complexity computation in replica formalism
• Chapter 10 for the analysis of planted coloring 

In this lecture we will conclude the discussion on the coloring problem, and wrap-up the course.