ABSTRACT

Machine learning is concerned with the design of algorithms that are able to predict future data based on past observations. Machine learning is a standard tool in applications involving intelligent data analysis (extraction of patterns from data, data categorization and clustering, decision-making and adaptive control), and has been applied to domains such as vision, natural language, biology, web, and others. The theoretical foundations of machine learning have a double nature: statistical and game-theoretic. In the course we take advantage of both paradigms to introduce and investigate a number of basic topics, including mistake bounds and risk bounds, empirical risk minimization, online linear optimization, compression bounds, linear learning and kernels, overfitting and regularization. The ultimate goal of the course is to provide a sound mathematical framework within which one can answer to questions such as: How much training data should one provide in order to attain a certain predictive performance? What is the weakest set of assumptions about the data ensuring the existence of a learning algorithm?

DAY 1
Binary classification and regression. Learning algorithm. Training set and test set. Hypothesis space (or model class). Training error and test error. Loss functions. k-NN and the Perceptron. The phenomenon of overfitting. The statistical data model. Statistical risk. Bayes function and Bayes risk. Bias-variance decomposition.

DAY 2
Chernoff bounds. Test error risk estimate. Risk bound for finite classes. Bounded differences inequality. Rademacher bound. Rademacher complexity of linear classes.

S. Boucheron, O. Bousquet, and G. Lugosi
Theory of Classification: a Survey of Recent Advances
ESAIM: Probability and Statistics, 9:323-375, 2005.

DAY 3
The game-theoretic data model. Online gradient descent. Perceptron mistake bound. From loss bounds to risk bounds.

M. Zinkevich
Online convex programming and generalized infinitesimal gradient ascent
International Conference on Machine Learning (ICML) 2003.

N. Cesa-Bianchi, A. Conconi, and C. Gentile
On the generalization ability of on-line learning algorithms
IEEE Transactions on Information Theory, 50(9):2050-2057, 2004.

DAY 4
Mirror descent. Strongly convex losses. Application to classification. Prediction with expert advice and game playing.

N. Cesa-Bianchi and G. Lugosi
Potential-based algorithms in on-line prediction and game theory
Machine Learning, 51(3):239-261, 2003. (Section 4.3)

S. Shalev-Shwartz and Y. Singer
Logarithmic regret algorithms for strongly convex repeated games
Technical Report, The Hebrew University of Jerusalem, 2007.

Y. Freund and R. Schapire
Adaptive game playing using multiplicative weights
Games and Economic Behaviour, 29(1-2):79-103, 1999.

DAY 5
The nonstochastic bandit problem.

P. Auer, N. Cesa-Bianchi, Y. Freund, and R.E. Schapire
The nonstochastic multiarmed bandit problem
SIAM Journal on Computing, 32(1):48-77, 2002.

EXAM

In order to pass the exam you have to write a research note summarizing on one or more papers. Your note will typically be 10 page long and will include:

• motivation and explanation of the problem,
• rigorous illustration of the most important results (including the formal definitions necessary to understand the results),
• at least one significant proof carried out in detail,
• description of previous and follow-up results (use Google Scholar to track down follow-up results),
• a final section mentioning what are, in your opinion, strengths and weaknesses of the results' contributions.

You can also propose a paper you are interested in. In any case, contact me before starting.

Alternatively, you can write a note describing the results of experiments obtained by running one or more learning algorithms on real-world data (which I can provide). Given that coding is involved, these projects can be carried out by a team of two people. If you choose this option for the exam, contact me and I will suggest an application domain. If you are interested in a specific topic, send me a proposal and I will approve it.

PAPERS FOR THE EXAM

S.M. Kakade, K. Sridharan, and A. Tewari
On the complexity of linear prediction: Risk bounds, margin bounds, and regularization
Advances in Neural Information Processing Systems, 2008.
Uses convex analysis methods to derive Rademacher bounds for linear prediction and more. Elegant, simple and broad.

A.D. Flaxman, A.T. Kalai, and H.B. McMahan
Online convex optimization in the bandit setting: gradient descent without a gradient
Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, 2005.
It solves the problem of performing gradient descent when nobody gives you the gradient. A cool application of the bandit framework.

P. Auer, N. Cesa-Bianchi, and C. Gentile
Adaptive and self-confident on-line learning algorithms
Journal of Computer and System Sciences, 64(1):48-75, 2002.
It solves the problem of adaptive tuning in mirror descent algorithms and expert algorithms.

K. Crammer and Y. Singer
Pranking with ranking
Advances in neural information processing systems, 2002.
An early work on ranking using online learning algorithms. Easy and pleasant. You will be tempted to run it on your data.

V. Dani, T. Hayes, and S.M. Kakade
The price of bandit information for online optimization
Advances in Neural Information Processing Systems, 2008.
It generalizes the Exp3 algorithm to the case when actions are points of a linear space and the loss function is linear. Tricky and math-intensive. But it contains cool applications to routing and more.

H.B McMahan and M. Streeter
Tighter Bounds for Multi-Armed Bandits with Expert Advice
Proceedings of the 22nd Annual Conference on Learning Theory, 2009.

G. Lugosi, O. Papaspiliopoulos and G. Stoltz
Online Multi-task Learning with Hard Constraints
Proceedings of the 22nd Annual Conference on Learning Theory, 2009.
A multitask application of the prediction with expert advice problem. Elegant math.

M. Streeter, D. Golovin, and A. Krause
Online learning of assignments
Proceedings of the 22nd Annual Conference on Learning Theory, 2009.
It extends bandits to the case when rewards are submodular functions. Several cool applications of the bandit problem.

S. Shalev-Shwartz and A. Tewari
Stochastic Methods for L1 Regularized Loss Minimization
International Conference on Machine Learning, 2009
Online learning convex analysis approaches to the solution of the classical L1 batch minimization problem. Contains algorithms and experiments. Go for it if you are interested in sparsity.

A. Tewari, S. Shalev-Shwartz and S. Kakade
Efficient Bandit Algorithms for Online Multiclass Prediction
International Conference on Machine Learning, 2008
Application of bandits to multiclass learning: what if the feedback of a multiclass prediction is just YES/NO instead of "the right class is...".