November 25, Wednesday 14:15, Room 303, Jacobs Building

Efficient learning algorithms for structured decision-making problems

Lecturer : Elad Hazan

Lecturer homepage : http://www.cs.princeton.edu/~ehazan/

Affiliation : IBM Almaden CS theory group

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, to the most basic settings
of decision making.

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.