Machine Learning Theory CS6783
News :
  1. Course added to Piazza, please join at LINK.
  2. Welcome to first day of class!


Location and Time : Location : Hollister Hall, 110
Time : Tue-Thu 1:25 PM to 2:40 PM
Teaching Assistant: Dylan J. Foster
Office Hours : Wed, 2-3pm

Description : We will discuss both classical results and recent advances in both statistical (iid batch) and online learning theory. We will also touch upon results in computational learning theory. The course aims at providing students with tools and techniques to understand inherent mathematical complexities of learning problems, to analyze and prove performance gaurantees for machine learning methods and to develop theoretically sound learning algorithms.


Pre-requisite : Student requires a basic level of mathematical maturity and ease/familiarity with theorems and proofs style material. Familiarity with probability theory, basics of algorithms and an introductory course on Machine Learning (CS 4780 or equivalent) are required. M.Eng. and undergraduate students require permission of instructor.


Tentative topics :

    1. Introduction
    Overview of the learning problem : statistical and online learning frameworks.
    PAC and agnostic PAC models, online learning protocol, (adaptive/ oblivious adversaries, various notions of regret) connections to optimization and statistical estimation

    2. Minimax formulation for learning, distribution free and adversarial learning settings, uniform guarantees and no free lunch theorems

    3. Statistical Learning Framework
    . Empirical risk minimization and Regularized empirical risk minimization
    . Uniform convergence (iid data)
    . finite classes, PAC Bayes theorem, compression bounds
    . VC dimension and growth function
    . Rademacher complexity, covering numbers, Dudley integral bounds, fat-shattering dimension
    . Supervised learnability : necessary and sufficient conditions via uniform convergence (iid)
    . Local Rademacher analysis and fast rates

    4. Online Learning Framework (sequential prediction/decision making)
    . Learning with expert advice, perceptron, winnow
    . Sequential minimax analysis for online learning
    . Uniform convergence over martingales
    . Sequential Rademacher complexity, sequential covering numbers, Sequential fat-shattering dimension
    . Supervised online learnability : necessary and sufficient conditions via martingale uniform convergence

    5. Deriving algorithms through relaxation and minimax analysis for online learning

    6. Additional topics
    . Connections between learning and approximation algorithms
    . Connections between learning and optimization
    . Algorithmic stability tools
    . Statistical estimation Vs statistical learning Vs Stochastic optimization

Grading :
Assignments : There will be a total of 5 assignments covering 55% of your grade.

Term project :
    There will be a small term project due by the end of the course. The project is worth 40% of your grade. The project could be one of :
    1. Your choice of research problem approved by me for which you will submit a report by end of term or,
    2. Completing problems worth up to 10 stars from a list of problems which shall be provided soon. (number of stars for a given problem will depend on its difficulty)
Project proposal/approval of project due on Thursday, March 15th.

Email: sridharan at cs dot cornell dot edu