• Calendar

November 17, Tuesday
12:00 – 14:00

Decision-making in the face of uncertainty over future outcomes is a fundamental machine learning problem, with roots in statistics and information theory, and applications to signal processing, network routing and finance. In this talk I'll describe recent algorithmic advances, both in terms of accuracy as well as computational efficiency. We describe the first efficient algorithm for the problem of online linear optimization in the limited-feedback (bandit) setting which achieves the optimal regret bound. This resolves an open question since the work of Awerbuch and Kleinberg in 2004, and is made possible via a new technique for controlling the exploration-exploitation tradeoff, inspired by convex optimization. Next we describe new online learning algorithms which attain optimal regret bounds in both worst case and stochastic scenarios. Tight performance bounds for decision making which interpolate between the worst-case and stochastic approaches were considered a fundamental open question. Based on work with Jacob Abetnethy, Satyen Kale and Alexander Rakhlin.