Learning theory
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: 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
-
If you have a question or want to start a discussion on a topic, post here
- Understanding Machine Learning (UML) by Shalev-Shwartz and Ben David
-
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
-
This serves as a tutorial on MP inverse - see solution below.
-
Double descent phenomenon: continuation and derivation for weak features model
Lecture by Dr Rodrigo Veiga
-
Paper on the exact solution for the weak feature model and also another sparse Fourier model.
-
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
-
We finish discussing the main idea of the mean analysis of two layer neural networks.
-
EASTER WEEK BREAK
-
Tensors 1. Motivations and examples, multi-dimensional arrays, tensor product, tensor rank.
Tensors 2. Tensor rank and decompositions, Jennrich's theorem
-
Tensors 2bis. Tensor decomposizion and Jennrich's algorithm
-
Tensors 3. Alternating least square algorithm
Tensors 4. Multilinear rank Tucker higher order singular value decomposition
-
Tensors 5. Power method and Applications: Gaussian Mixture Models, Topic models of documents
-
Tensors 6. Continuation
-
