Abstract:

 
Prediction problems such as prediction from expert advice and
the multi-armed bandit (MAB) problem are fundamental in machine
learning, with roots in statistics and information theory.
Besides their mathematical appeal, prediction algorithms are
amongst the most applicative methods in areas ranging from
signal processing to pattern recognition and network routing.
In this talk I'll describe recent algorithmic advances, both in
terms of prediction accuracy as well as computational
efficiency, to the most basic settings of prediction.

While extremely influential, existing machine learning
algorithms focus on the worst case and perform suboptimally in
benign or oblivious settings. On the other hand, statistical
learning methods appropriate for stochastic settings are prone
to failure in adversarial scenarios. A fundamental open
question is to interpolate between the approaches, and derive
methods capable of exploiting non-adversarial environments yet
guaranteeing reasonable worst-case performance. I'll describe a
solution to this question for the problem of prediction from
expert advice. We then proceed to tackle a more general and
difficult setting of learning with partial feedback (which
includes the MAB problem), for which we give the first {\it
efficient} algorithm with optimal performance. Finally I'll
describe a new algorithm with better performance for portfolio
selection with surprising implications in the geometric
Brownian motion model for stock prices.

Based on joint work with Jacob Abernethy (UC Berkeley), Satyen
Kale (MSR) and Alexander Rakhlin (UC Berkeley)