An Efficient Interior-Point Method for Minimum-Regret Learning in Online Convex Optimization

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.