IE613: Online Machine Learning, Jan-April 2017

Aim of this course is to study learning algorithms and analyze their performance.

Lecture Hours

Tuesday 3.35-5pm
Friday 3.35-5pm



Teaching Assistants

Sandhya Tripati

TA Hours

Timings: 2-4pm
Venue : Room 201, IEOR building


Introduction to batch learning: PAC learning, bias-variance tradeoff, VC-dimension, supervised learning algorithms, brief discussion on clustering methods.

Online learning: adversarial and stochastic settings, online learning with expert feedback, bandit feedback.

Multi-Armed Bandits: Algorithms for simple and cumulative regret (expected and high probability), and their analysis.

Online learning with side information (known and unknown feedback structure).


Assignment 1; dataset 1, dataset 2
Assignment 2
Assignment 3
A final project List


Midterm, Solution
Final, Solution

Course Grades

20 points: Midterm
30 points: 3 Coding assingments
30 points: Final exam
20 points: Final project

Reference texts

  • S. Shalev-Shwartz and S. Ben-David, ``Understanding Machine Learning:From Theory to Algorithms,'' Cambridge University Press, 2014, Download.
  • T. Hastie, R. Tibshirani and J. Friedman, ``Elements of statistical machine learning,'' Springer series in statistics, 2009, Download.
  • S. Shalev-Shwartz, ``Online Learning and Online Convex Optimization,'' NOW publisher, 2012,Download.
  • S. Bubeck and N. Cesa-Bianchi, ``Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems,'' NOW publisher, 2012, Download.
  • N. Cesa-Bianchi and G. Lugosi, ``Prediction, Learning, and Games, Cambridge University Press, 2006, Download.
  • Class notes

    Lecture 1: Welcome
    Lecture 2: Introduction to Supervised learning
    Lecture 3: PAC learnability
    Lecture 4: A-PAC learnability
    Lecture 5: Bias-complexity tradeoff
    Lecture 6: Bias-complexity tradeoff contd.
    Lecture 7: VC-dimesnion and its properties
    Lecture 8: Fundamental theorem of satisitical learning
    Lecture 9: Linear predictors: Halfspaces,Linear regression, Logistic regression
    Lecture 10: Soft-SVM, Hard-SVM
    Lecture 11: Boosting
    Lecture 12: Introduction to Online Learning
    Lecture 13: Online Learning-Consitent algorithm, Little-dimension
    Lecture 14: Halving and Standard Optimal Algorithm (SOA)
    Lecture 15: Weighted Majority (WM) algorithm
    Lecture 16: Online Convex Optimization (OCO), Follow the Leader (FTL)
    Lecture 17: Follow the Regualized Leader (FTRL), Online Gradient Descent (OCD)
    Lecture 18: Adversarial multi-armed bandits: EXP3
    Lecture 19: Adversarial multi-armed bandits: EXP3.P, EXP-IX
    Lecture 20: Adversarial multi-armed bandits: with side information
    Lecture 21: Adversarial multi-armed bandits: feedback graphs
    Lecture 22: Stochastic multi-armed bandits, UCB algorithm
    Lecture 23: Regret bound of UCB1, Lower bounds
    Lecture 24: Guest lecture by Prof. Shivram Kalyanakrishnan:, CSE, IITB