Learning theory

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: Anastasia Remizova - anastasia.remizova@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 lecture material each week. 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

GRADED HOMEWORKS: there will be 3 graded homeworks (one on each topic basically). Dates and deadlines will be announced as we go. You will usually have two weeks to hand them back. These will count for 20% of the final grade.

EXAM: its open book. You can bring your notes, printed material, the UML book. If you dont want to print you can upload your material on your laptop beforehand, and have wifi switched off. The final exam will count for 80% of the final grade.

Textbooks and notes:

• Understanding Machine Learning (UML) by Shalev-Shwartz and Ben David
  
• Bayesian Reasoning and Machine Learning by David Barber(Cambridge)
• Pattern recognition and Machine Learning by Christopher Bishop (Springer)
• A paper on double descent phenomenon
  
• Introduction to Tensor Decompositions and their Applications in Machine Learning (Ranbaser, Shchur, Gunneman)
• One lecture on two-layer neural networks

PAC learning framework. Finite classes. Uniform convergence.

Lecture this week is by Dr. Rodrigo Veiga

See chapters 3 and 4 in UML

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

No free lunch theorem.

See chapter 5 in UML

Homework 2: exercises 1 and 2 of chapter 4 + extra on proof of Hoeffding's inequality

Learning infinite classes I

Chapter 6 in UML

Homework 3 is graded. Deadline for handling 18 March.

Learning infinite classes II (VC dimension)

Chapter 6 continued

Homework 3 continued

Bias variance tradeoff and the double descent phenomenon 

We will study the double descent of generalization error based on the paper "Two models of double descent for weak features" by Belkin, Hsu, Xu

Lecture by Dr Rodrigo Veiga

Deadline for handling homework 3: 18 March

Double descent phenomenon: continuation and derivation for weak features model

Lecture by Dr Rodrigo Veiga

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

Stochastic gradient descent, application to learning

Second graded homework this week: deadline 15 April midnight.

Chapter 14 in UML

Mean field approach for two layer neural networks

based on the paper "One lecture on two layer neural networks" by A. Montanari

Tensors 1. Motivations and examples, multi-dimensional arrays, tensor product, tensor rank.

Tensors 2. Tensor rank and decompositions, Jennrich's theorem (proof of thm next time)

Graded Homework 8: deadline May Tuesday 13 May midnight.   EXTENDED Monday 19 May midnight

CLASS CANCELLED THIS WEEK. SESSION DEVOTED TO THE EXERCISES (graded hmw 8)

Tensors 2bis. Tensor decomposizion and Jennrich's algorithm

Tensors 2bis. Tensor decomposizion and Jennrich's algorithm

 Tensors 3. Alternating least square algorithm

Tensors 4. Multilinear rank Tucker higher order singular value decomposition

Here we will post old exams with solutions which will allow you to train yourself. Note that some problems (but not all) are included in the current year's material.