Machine Learning: Theory and Algorithms

Responsable / In charge of : Neglia Giovanni (

Résumé / Abstract :
The course introduces the mathematical foundations of machine learning.
Its first goal is to formalize the main questions behind machine learning: What is learning? How can a machine learn? Is learning always possible? How do we quantify the resources needed to learn? To this purpose, the course presents the probably-approximately correct (PAC) learning paradigm. Its second goal is to present several key machine learning algorithms and show how they follow from general machine learning principles.

Prérequis / Prerequisite :
The course has a theoretical focus, and the student is assumed to be comfortable with basic notions of probability, linear algebra, analysis, and algorithms.

Objectifs / Objectives :

  • Formalize mathematically the learning problem
  • Present key machine learning algorithms

Contenu / Contents :

  • What Is Learning? When Do We Need Machine Learning? Types of Learning

  • The Statistical Learning Framework

  • Empirical Risk Minimization

  • Probably Approximately Correct (PAC) Learning, agnostic and non-agnostic case

  • Uniform Convergence

  • The Bias-Complexity Tradeoff

  • The No-Free-Lunch Theorem

  • The VC-Dimension

  • The Fundamental Theorem of PAC learning

  • Nonuniform Learnability, Structural Risk Minimization and minimum Description Length

  • Linear Predictors, Linear Regression, Logistic Regression

  • Boosting, Weak Learnability, AdaBoost

  • Model Selection and Validation

  • Convex Learning Problems, Surrogate Loss Functions


Références / References :
• Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms, available at theory-algorithms.pdf
• Video lecture from
• Lecture notes from Shai Shalev-Shwartz

Acquis / Knowledge :

  • Know the fundamental limits of machine learning
  • Know how to select machine learning models with the right complexity

Evaluation / Assessment :
30% classwork (a 10-minute test at every lesson, only 5 best marks will be considered), 30% a mid-course home assignement, 40% final exam.