Machine learning is a branch of artificial intelligence that deals with the design of algorithms that improve their efficiency based on empirical data. The key challenge of machine learning is how to ensure that the model generalizes well. The theory of statistical machine learning studies the generalization capabilities of algorithms with the aim of better understanding existing algorithms and developing better algorithms. The course provides an introduction to the theory of statistical learning and an overview of its applications to classical and modern machine learning algorithms. The course content is divided into three parts. The first part studies the basic concepts and tools of statistical learning theory. In the second part, these tools are applied to classical classification and regression algorithms. The third part studies more advanced techniques of statistical learning theory and applications to deep learning models.

Learning outcomes of the course "Machine Learning 1" (FER) or a similar course. Learning outcomes of the courses "Mathematical Analysis 1", "Mathematical Analysis 2", "Discrete Mathematics", "Linear Algebra", "Probability and Statistics", and "Information Theory", or similar courses. Good knowledge of programming in Python. Desirable, but not essential: learning outcomes of the course "Deep Learning 1" (FER) or a similar course.

1. Explain the fundamental concepts of statistical learning theory, including PAC learnability, empirical risk minimization, and the bias-variance tradeoff
2. Apply core statistical learning theory principles to explain the behavior and properties of regularization techniques and optimization algorithms
3. Analyze the generalization capabilities of ensemble methods like boosting and random forests, relating them to concepts such as stability and complexity
4. Differentiate between various complexity measures (e.g., VC dimension, Rademacher complexity) and derive their application in establishing generalization bounds for learning models
5. Evaluate advanced theoretical frameworks such as PAC-Bayes theory and compression bounds, assessing their relevance for understanding generalization in complex learning scenarios
6. Explain the theoretical assumptions, advantages, and limitations of sparse kernel machines
7. Explain the main approaches to semisupervised machine learning and list their advantages and disadvantages
8. Synthesize current theoretical understanding of deep learning phenomena, including training dynamics, and implicit regularization
9. Explain open problems in deep learning generalization and efficiency, informed by advanced statistical learning theory

Lectures

Lectures are given for 13 weeks in one three-hour session per week.

Seminars and workshops

Presenting one selected scientific paper.

Exercises

Recitations are given in one-hour sessions as needed, spanning 13 weeks.

Independent assignments

Preparatory reading of textbook chapters. Reading selected scientific papers.

Laboratory

Programming assignments, demonstrated to the instructor or teaching assistant.

1. Introduction and course organization. Overview of statistical learning theory. Course goals and expectations.
2. PAC learning framework. Generalization bounds. Sample complexity. No free lunch theorem.
3. Empirical risk minimization. Bias-variance tradeoff. Model selection. Uniform convergence.
4. VC dimension. The fundamental theorem of statistical learning.
5. Regularization techniques. L1 and L2 regularization. Early stopping. Overfitting and underfitting revisited.
6. Optimization for machine learning. Gradient descent variants. Stochastic gradient descent. Convergence properties.
7. Kernel methods and reproducing kernel Hilbert spaces (RKHS). Theoretical foundations of kernels. Feature maps.
8. Midterm exam
9. Weak learnability. Boosting. AdaBoost algorithm. Gradient boosting.
10. Decision trees. Random forests. Ensemble methods. Sample complexity.
11. Rademacher complexity. VC dimension. Generalization bounds for deep learning.
12. PAC-Bayes theory. Derivations and applications. Bayesian neural networks.
13. Compression bounds. Minimum description length (MDL) principle. Learnability from a compression perspective.
14. Theoretical foundations of modern deep learning. Training dynamics. Implicit regularization.
15. Final exam