PHYS-512 / 4 credits

Teacher(s): Krzakala Florent Gérard, Zdeborová Lenka

Language: English


Summary

This course covers the statistical physics approach to computer science problems ranging from graph theory and constraint satisfaction to inference and machine learning. In particular the replica and cavity methods, message passings algorithms, and analysis of the related phase transitions.

Content

Learning Prerequisites

Important concepts to start the course

Basic notions in probability. For physics students Statistical physics I, II, III or analogous will be a very useful background. This lecture is also accessible to non-physicists with some background in high-dimensional statistics, probability, signal processing or learning, without any previous training in statistical physics.

Learning Outcomes

By the end of the course, the student must be able to:

  • Analyze theoretically a range of problems in computer science and learning.
  • Derive algorithms for a range of computational problems using technics stemming from statistical physics.

Teaching methods

2h of lecture + 2h of excercise

Assessment methods

Final written exam counting for 50% and several graded homeworks during the semester counting for the other 50%.

Resources

Bibliography


Information, Physics and Computation (Oxford Graduate Texts), 2009, M. Mézard, A. Montanari

 

Statistical Physics of inference: Thresholds and algorithms, Advances in Physics 65, 5 2016, L. Zdeborova & F. Krzakala, available at https://arxiv.org/abs/1511.02476

 

 

Notes/Handbook

Policopié "Statistical Physics methods in Optimization & Machine Learning" by L. Zdeborova & F. Krzakala (available as pdf on the course website)

In the programs

  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Statistical physics of computation
  • Lecture: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Statistical physics of computation
  • Lecture: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Statistical physics of computation
  • Lecture: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Statistical physics of computation
  • Lecture: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks

Reference week

 MoTuWeThFr
8-9     
9-10     
10-11     
11-12     
12-13     
13-14   CHB331 
14-15    
15-16   CHB331 
16-17    
17-18     
18-19     
19-20     
20-21     
21-22     

Thursday, 13h - 15h: Lecture CHB331

Thursday, 15h - 17h: Exercise, TP CHB331