6.883: Online Methods in Machine Learning
Theory and Applications
MW 2:304, Room 32124
Instructor: Alexander Rakhlin
TA: Arthur Flajolet
Course description:
 In a growing number of machine learning applications—such as problems of advertisement placement, movie recommendation, and node or link prediction in evolving networks—one must make online, realtime decisions and continuously improve performance with the sequential arrival of data. The course aims to provide a foundation for the development of such online methods and for their analysis.

The course will have three interleaved components:
 fundamental theoretical tools for analyzing online methods
 algorithmic techniques for developing computationally efficient methods, and
 applications to realworld problems.

Prerequisites: Probability and Linear Algebra.
Target audience: graduate students or advanced undergraduates.
Topics
Tentative list of topics:
 Introduction
 Mindreading machine. Bit prediction. Cover's result.
 Online methods for i.i.d. data
 Stochastic approximation and sample average approximation.
 Stochastic gradient descent. Sparse updates.
 Minibatching. Acceleration.
 Pegasos. SGD for Kernel SVM. Perceptron.
 Logistic regression. Multiclass learning.
 Neural nets. Backprop via SGD.
 Onlinetobatch conversion. Biasvariance tradeoff and early stopping.
 Online methods for dynamic environments
 Online prediction as an optimization problem.
 Bit prediction. Dynamic programming. Prediction with side information.
 Learning in static networks. Laplacian regularization.
 Probabilistic toolkit
 Stochastic processes, martingales, maximal inequalities, symmetrization.
 Sequential complexity measures: random averages, covering numbers, combinatorial parameters.
 Comparison to the VapnikChervonenkis theory.
 Optimization toolkit
 Online convex optimization.
 Gradient descent, mirror descent, dual averaging, exponential weights.
 Minimax analysis
 Learning with absolute loss. Multiclass classification. Online linear optimization.
 Algorithmic toolkit
 The general relaxation framework. Approximate dynamic programming.
 Relaxations for i.i.d. covariates. Transductive learning.
 Algorithms for online classification and regression.
 The magic of random playout: general techniques, followtheperturbedleader.
 Examples: linear classes, kernel methods, static experts, online shortest path.
 Relaxations for multiclass learning.
 Approximation algorithms for online relaxations.
 Learning in evolving networks
 Online prediction of user attributes; node and link classification.
 Random playout for evolving graphs.
 Experiments with social network data.
 Online collaborative filtering and movie rating prediction.
 Parital information problems
 Multiarmed bandits, contextual bandits. Ad placement.
 Dynamic pricing, partial monitoring.
 Online regression
 Minimax analysis, algorithms.
 Adaptive online learning methods, datadependent bounds
 Scoring online competitions: tracking performance of adaptively chosen hypotheses
Lecture notes
 Feb 3: Lecture 01
 Feb 8: Lecture 02
 Feb 10: Lecture 03
 Feb 17: Lecture 04
 Feb 22: Lecture 05
 Feb 24: Lecture 06
 Feb 29: Lecture 07 (Guest lecture by Suvrit)
 Mar 02: Lecture 08
 Mar 07: Lecture 09
 Mar 09: Lecture 10
 Mar 14: Lecture 11
 Mar 16: Lecture 12
 Mar 28: Lecture 13
 Mar 30: Lecture 14
 Apr 04: Lecture 15
 Apr 06: Lecture 16
 Apr 11: Lecture 17
 Apr 13: Lecture 18
 Apr 20: Lecture 19
 Apr 25: Lecture 20
 May 02: Lecture 21
 May 04: Lecture 22
 May 09: Lecture 23
 May 11: Lecture 24
Recitation notes (by Arthur)
Assignments
Projects
 Homework 1 posted on Stellar, due April 4
 Homework 2 posted on Stellar, due April 25
 Homework 3 posted on Stellar, due May 06
 Final project guidelines
References
Tutorial on online supervised learning with applications to node classification in social networks.
Books (not required)
 Understanding Machine Learning: From Theory to Algorithms, S. ShalevShwartz and S. BenDavid
 Prediction, learning, and games, G. Lugosi and N. CesaBianchi
Datasets
Contact
Office hours: 32D630, Tue 1:302:30pm, or by appointment