## Statistical Learning Theory

### Course Syllabus

• Complexity bounds: Bias complexity trade-off, Rademacher complexity, VC-dimension
• Classification: Multiclass classification, decision trees, nearest neighbours
• Estimation: Parameter estimation and nonparametric regression
• Optimization: Stochastic gradient descent
• Decision theory: Statistical decision theory, Large-sample asymptotics
• Information theoretic bounds: Mutual information method and lower bound via hypothesis testing, Entropic bounds for statistical estimation, Strong data processing inequality

### Prerequisite

Instructor’s approval is required for crediting this course. Course requires a background in the first graduate course in probability theory and random processes.

### Description

The aim of this course is to provide performance guarantees on various data driven algorithms for classification, estimation, and decision problems under uncertainty. The guarantees are provided by the upper and lower bounds on the algorithm accuracy as a function of the number of samples. The upper bounds are derived from the classical complexity results and the lower bounds follow from information theoretic techniques.

### Teams/GitHub/Overleaf Information

#### Teams

We will use Microsoft Teams for all the course related communication.
Please do not send any email regarding the course.
You can signup for the course team Statistical-Learning-2024 using the following code TBD.

#### Overleaf

All the crediting students have access to the Overleaf project Statistica-Learning. Please follow the guidelines in the sampleLecture.tex, and save it with another name for creating a new lecture. Here is a good online resource to learn Overleaf.

### Instructor

Parimal Parag
Office: EC 2.17
Hours: By appointment.

### Teaching Assistants

TBD
Email: TBD
Hours: By appointment.

### References

Information Theory: From Coding to Learning, Yury Polyanskiy and Yihong Wu, Cambridge University Press, 2023.

Information-theoretic Methods for High-dimensional Statistics, Yihong Wu, Lecture notes.

High-Dimensional Statistics: A Non-asymptotic Viewpoint, Martin Wainwright, Cambridge University Press, 2019.

Foundations of Machine Learning, Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, 2nd edition, MIT Press, 2018.

Introduction to Statistical Learning Theory, Olivier Bousquet, Stephane Boucheron, and Gabor Lugosi, Lecture notes.