6.883: Online Methods in Machine Learning
Theory and Applications
MW 2:30-4, Room 32-124
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, real-time 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 real-world problems.
-
Prerequisites: Probability and Linear Algebra.
Target audience: graduate students or advanced undergraduates.
Topics
Tentative list of topics:
- Introduction
- Mind-reading 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.
- Online-to-batch conversion. Bias-variance 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 Vapnik-Chervonenkis 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, follow-the-perturbed-leader.
- 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
- Multi-armed bandits, contextual bandits. Ad placement.
- Dynamic pricing, partial monitoring.
- Online regression
- Minimax analysis, algorithms.
- Adaptive online learning methods, data-dependent 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. Shalev-Shwartz and S. Ben-David
- Prediction, learning, and games, G. Lugosi and N. Cesa-Bianchi
Datasets
Contact
Office hours: 32-D630, Tue 1:30-2:30pm, or by appointment