TITLE:  Online Prediction: A Marriage of Optimization and Probability

ABSTRACT:

The talk will focus on two seemingly unrelated topics: (i) existence of prediction strategies that have a performance guarantee for all sequences and (ii) probabilistic inequalities for martingales. We will point to a certain equivalence between these two topics, with the most basic example going back to the work of T. Cover in 1965. In light of the equivalence, we will develop computationally efficient prediction methods for problems with a combinatorial benchmark, even when estimating the correct model is NP-hard. Exploiting the equivalence in the other direction, we show that tail bounds for a certain ratio-type inequality follow with ease from mirror descent with an adaptive step size.

Joint work with K. Sridharan

Bio:  Alexander (Sasha) Rakhlin is an Associate Professor of Statistics at the University of Pennsylvania, The Wharton School. He received his Bachelors from Cornell University, a Ph.D. from MIT, and joined Penn after working as a postdoctoral researcher at UC Berkeley. Sasha’s interests span a range of topics, including statistics, machine learning, online prediction, and optimization.