## A fortnightly seminar series at IIIT Hyerabad focused on theoretical talks from computer science, communications theory, machine learning and natural sciences.

* * Tushant Jha, CSTAR, IIITH

* * 4:00PM * * 24 Jul, 2019

* * A3 117 Conf. Hall, CSTAR Corridor

How many samples do we need to observe before making a reliable prediction? This is the fundamental class of questions, called sample complexity, asked in learning theory.
In this talk, we shall review PAC Learning, an elementary and ubiquitous framework to talk about theoretical guarantees in statistics and machine learning. We shall then explore ideas from the 1971 landmark paper of Vladimir Vapnik and Alexey Chervonenkis, which proposed a combinatorial quantity (now called VC dimension) as a complexity measure for a class of binary classification models. We shall discuss how it characterizes learnability and uniform convergence, prove theorems for lower bound and upper bound of the sample complexity, and explore the relationship with empirical risk minimization algorithms.
If time allows, we shall also aim to look at, and prove corresponding results for, generalizations of VC dimension like: a) Pollard's pseudodimension (for regression), b) Natarajan dimension and Graph dimension (for multiclass classification), c) and Littlestone dimension (for online learning); which provide similar quantification in other learning frameworks.

* *
Learning Theory,
*Prereq*: basic probability theory, and complexity-theoretic reductions

*Ambition*: to build an basic intuition of Sample Complexity 101.