Weekly outline

  • This master class on learning theory covers the classical PAC framework for learning, stochastic gradient descent, tensor methods. We also touch upon topics from the recent literature on mean field methods for NN and the double descent phenomenon.

    Teacher: Nicolas Macris: nicolas.macris@epfl.ch  -  with also some lectures by Rodrigo Veiga: rodrigo.veiga@epfl.ch

    Teaching Assitant: Anand Jerry Georges -  anand.george@epfl.ch

    Courses: Mondays 8h15-10h in presence Room INM202; Exercises: Tuesdays 17h15-19h in presence Room INR219.

    We will use this moodle page to distribute homeworks, solutions and also collect graded ones. As well as use the discussion and questions forum. Dont hesitate to actively use this forum.

    Lectures are in presence. If you miss a lecture an old recorded version is accessible here  https://mediaspace.epfl.ch/channel/CS-526+Learning+theory/29761 however the material, instructors and order of lectures might be slightly different this year

    EXAM: its open book. You can bring your notes, printed material, book(s). But no electronic material! 

  • 19 - 20 February

    This week

    PAC learning framework. Finite classes. Uniform convergence. 

    See chapters 3 and 4 in UML

    Homework 1: exercises 1, 3, 7, 8 of Chapter 3.

  • 26 - 27 February

    No free lunch theorem.

    See chapter 5 in UML

    Homework 2: exercises 1 and 2 of chapter 4

  • 4 - 5 March

    Learning infinite classes I

    Chapter 6 in UML

    Graded hmw 3 due date Monday 18 March 23h59

  • 11 - 12 March

    Learning infinite classes II (VC dimension)

    Chapter 6 continued

    graded hmw 3 continued due date monday 18 March 23h59

  • 18 - 19 March

    Bias variance tradeoff and the double descent phenomenon

    Homework 4: exercise 3 of chapter 6 and XXXXXXXX

  • 25 - 26 March

    Gradient descent (convexity, Lipshitzness, Approach to optimal solution)

    Chapter 14 in UML

  • 1 - 2 April

    Easter week break
  • 8 - 9 April

    Stochastic gradient descent, application to learning

    Mean field approach for two layer neural networks (based on a paper by A. Montanari and S. Mei)

    Chapter 14 in UML continued.

    Graded hmw 6 due date monday 21th April at 23h59

  • 15 - 16 April

    Mean field approach for two layer neural networks continued

    graded hmw 6 continued (due monday 22nd April at 23h59)


  • 22 - 23 April

    Tensors 1. Motivations and examples, multi-dimensional arrays, tensor product, tensor rank.
  • 29 - 30 April

    Tensors 2. Tensor decompositions and rank, Jennrich's theorem

    Graded hmw 8 due date 13 may 23h59

  • 6 - 7 May

    Tensors 3. Matricizations and Alternating Least Squares algorithm

  • 13 -14 May

    Tensors 4. Multilinear rank Tucker higher order singular value decomposition

    Graded hmw 10 due date 27th may at 23h59

  • 20 - 21 May

    Monday 20 holiday

    Tuesday 21: exercise session -  Q&A.

    The hmw 11 below is an extra hmw that reviews the tensor whitening process

  • 27 - 28 May

    Tensors 5. Power method and Applications: Gaussian Mixture Models, Topic models of documents


  • Further lecture notes