Statistical physics for optimization & learning

PHYS-642

Media

6a, Spin glass game

31.03.2023, 13:46

PHYS-642 Statistical physics for optimization & learning 23

11b

30.05.2023, 09:58

11a

30.05.2023, 09:56

TD5, Information theory

23.05.2023, 10:41

10, Random Constraint Satisfaction Problem

12.05.2023, 14:24

9b, Applications of GAMP

05.05.2023, 12:17

9a, GAMP

05.05.2023, 11:00

8b, Generalized Linearized Models

28.04.2023, 15:02

8a, A proof technique for the spiked model

28.04.2023, 11:03

7b, Spiked Wigner model

21.04.2023, 12:04

7a, AMP & State Evolution

21.04.2023, 11:05

TD4b, Replica for the p-spin model

04.04.2023, 11:12

TD4a, Maximum of Gaussians

04.04.2023, 11:10

6b, TAP & Intro to AMP

31.03.2023, 13:50

6a, Spin glass game

31.03.2023, 13:46

5b, Open problems

24.03.2023, 13:23

5a, Graphical models

24.03.2023, 13:22

4b, REM - Replica Symmetry Breaking

17.03.2023, 13:48

4a, Random Energy Model - Full solution & Condensation

17.03.2023, 13:44

TD3b, Potts model & Erdös-Renyi degree

17.03.2023, 08:24

TD3a, RFIM on random graphs

17.03.2023, 08:23

TD2a, RFIM

14.03.2023, 19:02

3b, RFIM on sparse graphs & Population dynamics

10.03.2023, 12:18

3a, RFIM on a tree & BP

10.03.2023, 11:09

TD2b, Stieltjes transform with the replica method

09.03.2023, 17:34

2b, RFIM - Cavity and Replica method

03.03.2023, 13:48

2a, RFIM - Variational method

03.03.2023, 11:08

TD1b, Large deviations

02.03.2023, 14:34

TD1a, Intro to Julia & HW1 correction

02.03.2023, 14:34

1. Curie Weiss Model

24.02.2023, 14:28

In this lecture, the main focus is studying the Curie-Weiss model. The topics are:
  • Introduction to Statistical Physics
  • Computation of the probability of having a magnetisation.
  • Computation of the free entropy and large deviation theory perspective.
  • Exploration of the free energy functional for different values of the parameters.
  • Computing observables and moment-generating functions.
  • Cavity method for the CW model.

5a, Graphical models

24.03.2023, 13:22

TD1b, Large deviations

02.03.2023, 14:34

2a, RFIM - Variational method

03.03.2023, 11:08

7b, Spiked Wigner model

21.04.2023, 12:04

4b, REM - Replica Symmetry Breaking

17.03.2023, 13:48

6b, TAP & Intro to AMP

31.03.2023, 13:50

7b, Spiked Wigner model

21.04.2023, 12:04

1. Curie Weiss Model

24.02.2023, 14:28

In this lecture, the main focus is studying the Curie-Weiss model. The topics are:
  • Introduction to Statistical Physics
  • Computation of the probability of having a magnetisation.
  • Computation of the free entropy and large deviation theory perspective.
  • Exploration of the free energy functional for different values of the parameters.
  • Computing observables and moment-generating functions.
  • Cavity method for the CW model.

5b, Open problems

24.03.2023, 13:23

TD2b, Stieltjes transform with the replica method

09.03.2023, 17:34

3b, RFIM on sparse graphs & Population dynamics

10.03.2023, 12:18

4a, Random Energy Model - Full solution & Condensation

17.03.2023, 13:44

TD2b, Stieltjes transform with the replica method

09.03.2023, 17:34

8a, A proof technique for the spiked model

28.04.2023, 11:03

7a, AMP & State Evolution

21.04.2023, 11:05

TD1a, Intro to Julia & HW1 correction

02.03.2023, 14:34

7a, AMP & State Evolution

21.04.2023, 11:05

3a, RFIM on a tree & BP

10.03.2023, 11:09

2b, RFIM - Cavity and Replica method

03.03.2023, 13:48

7a, AMP & State Evolution

21.04.2023, 11:05

8b, Generalized Linearized Models

28.04.2023, 15:02


Media

6a, Spin glass game

31.03.2023, 13:46

PHYS-642 Statistical physics for optimization & learning 23

11b

30.05.2023, 09:58

11a

30.05.2023, 09:56

TD5, Information theory

23.05.2023, 10:41

10, Random Constraint Satisfaction Problem

12.05.2023, 14:24

9b, Applications of GAMP

05.05.2023, 12:17

9a, GAMP

05.05.2023, 11:00

8b, Generalized Linearized Models

28.04.2023, 15:02

8a, A proof technique for the spiked model

28.04.2023, 11:03

7b, Spiked Wigner model

21.04.2023, 12:04

7a, AMP & State Evolution

21.04.2023, 11:05

TD4b, Replica for the p-spin model

04.04.2023, 11:12

TD4a, Maximum of Gaussians

04.04.2023, 11:10

6b, TAP & Intro to AMP

31.03.2023, 13:50

6a, Spin glass game

31.03.2023, 13:46

5b, Open problems

24.03.2023, 13:23

5a, Graphical models

24.03.2023, 13:22

4b, REM - Replica Symmetry Breaking

17.03.2023, 13:48

4a, Random Energy Model - Full solution & Condensation

17.03.2023, 13:44

TD3b, Potts model & Erdös-Renyi degree

17.03.2023, 08:24

TD3a, RFIM on random graphs

17.03.2023, 08:23

TD2a, RFIM

14.03.2023, 19:02

3b, RFIM on sparse graphs & Population dynamics

10.03.2023, 12:18

3a, RFIM on a tree & BP

10.03.2023, 11:09

TD2b, Stieltjes transform with the replica method

09.03.2023, 17:34

2b, RFIM - Cavity and Replica method

03.03.2023, 13:48

2a, RFIM - Variational method

03.03.2023, 11:08

TD1b, Large deviations

02.03.2023, 14:34

TD1a, Intro to Julia & HW1 correction

02.03.2023, 14:34

1. Curie Weiss Model

24.02.2023, 14:28

In this lecture, the main focus is studying the Curie-Weiss model. The topics are:
  • Introduction to Statistical Physics
  • Computation of the probability of having a magnetisation.
  • Computation of the free entropy and large deviation theory perspective.
  • Exploration of the free energy functional for different values of the parameters.
  • Computing observables and moment-generating functions.
  • Cavity method for the CW model.

5a, Graphical models

24.03.2023, 13:22

TD1b, Large deviations

02.03.2023, 14:34

2a, RFIM - Variational method

03.03.2023, 11:08

7b, Spiked Wigner model

21.04.2023, 12:04

4b, REM - Replica Symmetry Breaking

17.03.2023, 13:48

6b, TAP & Intro to AMP

31.03.2023, 13:50

7b, Spiked Wigner model

21.04.2023, 12:04

1. Curie Weiss Model

24.02.2023, 14:28

In this lecture, the main focus is studying the Curie-Weiss model. The topics are:
  • Introduction to Statistical Physics
  • Computation of the probability of having a magnetisation.
  • Computation of the free entropy and large deviation theory perspective.
  • Exploration of the free energy functional for different values of the parameters.
  • Computing observables and moment-generating functions.
  • Cavity method for the CW model.

5b, Open problems

24.03.2023, 13:23

TD2b, Stieltjes transform with the replica method

09.03.2023, 17:34

3b, RFIM on sparse graphs & Population dynamics

10.03.2023, 12:18

4a, Random Energy Model - Full solution & Condensation

17.03.2023, 13:44

TD2b, Stieltjes transform with the replica method

09.03.2023, 17:34

8a, A proof technique for the spiked model

28.04.2023, 11:03

7a, AMP & State Evolution

21.04.2023, 11:05

TD1a, Intro to Julia & HW1 correction

02.03.2023, 14:34

7a, AMP & State Evolution

21.04.2023, 11:05

3a, RFIM on a tree & BP

10.03.2023, 11:09

2b, RFIM - Cavity and Replica method

03.03.2023, 13:48

7a, AMP & State Evolution

21.04.2023, 11:05

8b, Generalized Linearized Models

28.04.2023, 15:02


This file is part of the content downloaded from Statistical physics for optimization & learning.
Course summary

Summary

This course covers the statistical physics approach to computer science problems, with an emphasis on heuristic & rigorous mathematical technics, ranging from graph theory and constraint satisfaction to inference to machine learning, neural networks and statitics.

Where

Lectures are in room CM011. Main lectures are on Friday 10.15 -> 12.00 while exercices are on Thrusday 10.15-> 12.00

The video channel of the course is here

The website of the lecture is here

Grading


Your grade will be the average of
- either your 4 best homeworks
- or your 2 best homeworks + a 15-minute presentation of your progress on the open problem

Content

Powerful Mathematical techniques from statistical physics and spin glass theory have been applied with increasing success on various problems ranging from computer science, statistics to machine learning. In the last decades, in particular, there has been increasing convergence of interest and methods between theoretical physics and much theoretical and applied work in statistical physics and computer science has relied on the use of message-passing algorithms and their connection to the statistical physics of glasses and spin glasses.This course will cover this rich and active interdisciplinary research landscape.

 

A particular emphasis will be given to high-dimensional problems. Indeed modern data analysis uses complex statistical models with massive numbers of parameters In some cases, the high-dimensional limit is analogous to the "thermodynamic limit" of a certain (disordered) statistical mechanics system. Building on mathematical ideas from the mean-field theory of disordered systems, exact asymptotic can thus be computed for high-dimensional problems. We shall discuss examples in statistics, coding theory, and machine learning.

 

While the course is designed to be a follow up of PHYS-512, it is also intendeded to stand on its own, and to be accessible to mathematically-minded graduate students and researchers from engineering, computer science and mathematics disciplines with a knowledge of probability and analysis. The course is aimed at theory-minded students, interested in the use of powerful methods originating in statistical physics, and their connection to open problems in modern high-dimensional statistics, computer science and machine learning.

Show more 


Welcome to the first week of the course.

Today, we discussed the simplest model of statistical physics, the "Curie-Weiss" model, following part of chap.1 of the lecture notes.

The video of the lecture is here: 

Few remarks :

1) I had some questions on the link with probability theory, and Chernow bounds. I have a short introduction to the very basics of these bounds on these short videos here :(all of probability part1, part2, part3). This is very useful to know

2) About the relation between free energy and large deviation, I wrote about this in section 1.2.2 and section 1.2.3 


 You can access at the exercice list below and submit your solutions before next week, thursday morning, directly on moodle (link below). Ideally, submit a notebook (for codes) or a latex/pdf file (for computations). Exercices are due before 2/2, 10am

The videos of the first TD is published!
- TD1a: Guillaume helped us taking our first steps in Julia and corrected HW1.
- TD1b: Short introduction by Yatin on large deviations theory and its link with statistical physics.


This week, we shall discuss our first non trivial problem, the random field ising model. The lectures follows chap 2 of the notes The videos of the lectures are here: part1 and part2. The slides I used on replica method are here

 Exercices are due before 9/2, 10am

The videos of the second TD are out:

- TD2a: Guillaume corrects HW2 and digs into the variational approach for the RFIM

- TD2b: Luca computes the Stieltjes transofrm of a Wigner matrix with the replica method


This week, we shall move to more interesting topology, and discuss tree and random graphs (and belief propagation), using again the example of the rabdom energy model.

The lectures notes for this chapter are here and the videos are poster: part1 and part2

The exercise is the population dynamics exercise 4.2 here , it is due before 16/2, 10am!




This week, we finish our tour of statistical physics technics by the very important concept of replica symmetry breaking! An idea is so important that our beloved mentor and master Giorgio Parisi received the Nobel prize last year for its development. I strongly recommend going again through chapt 14 in the notes to make sure you understand the concepts.

The exercises for next week are the two following ones. You may do both but it is ok if you just focus on one of them!

* Exercise 14.1: REM as a p-spin model

* Exercice 14.3: Maximum of Ω Gaussians numbers and denoising

 

The videos of the lecture on the Random Energy Model are out! Part1 & Part2

This week we shall study open problems! Check out the amazing list here! 

We are arriving at the important moment of choosing your open problem:
You can fill up your preferences for the open problems here, and chose which problem you will work on in compagny of your fellow students: https://docs.google.com/spreadsheets/d/1guW79xOLy_fOBGnfnI6lmXtH2IMZAlom-1hMBxD-rAw/edit?usp=sharing

For this week, the exercise is quite simple: Exercise 4.1: Representing problems by graphical models and Belief Propagation


The videos of the lectures are here!

This week we start studying inference problems.

The videos of the lectures are out:

6a: The spin glass game

6b: AMP

This week we study the State Evolution characterization of the AMP algorithm.

Videos of the lectures: 7a, 7b

This week we study the State Evolution characterization of the AMP algorithm.

Videos of the lectures: 7a, 7b


This week we study the State Evolution characterization of the AMP algorithm.

Videos of the lectures: 7a, 7b


This week we study an interesting proof technique and Generalized Linear Models.

Videos of the lectures: 8a, 8b

This week we analyze GAMP.


Videos of the lectures 9a and 9b on the mediaspace channel

This week we analyze Random Constraint Satisfaction Problem.


The video of the lecture 10 is on the mediaspace channel


The lectures 11a & 11b are published on the Mediaspace channel!