Poster
An Efficient Interior-Point Method for Minimum-Regret Learning in Online Convex Optimization
Elad Hazan · Nimrod Megiddo

Tue Dec 8th 07:00 -- 11:59 PM @ None #None
in Poster Session »

A new algorithm for regret minimization in online convex optimization is described. The regret of the algorithm after T time periods is almost the minimum possible. However, in n-dimensional space, during each iteration the new algorithm essentially solves a system of linear equations of order n, whereas previous algorithms have to solve some constrained convex optimization problem in n dimensions and possibly many constraints. Thus, the new algorithm improves the running time by a factor of at least the square root of n, and much more for nontrivial domains. This new method is also adaptive, in the sense that the regret bounds hold not only for the time periods 1,...,T but also for every sub-interval s, s+1, ... , t.

Author Information

Elad Hazan (Princeton University)
Nimrod Megiddo (IBM Almaden Research Center)

More from the Same Authors