An Efficient Interior-Point Method for 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 O(√T log T) - which is the minimum possible up to a logarithmic term. In addition, the new algorithm is adaptive, in the sense that the regret bounds hold not only for the time periods 1,ldots,T but also for every sub-interval s,s+1,ldots,t. The running time of the algorithm matches that of newly introduced interior point algorithms for regret minimization: in n-dimensional space, during each iteration the new algorithm essentially solves a system of linear equations of order n, rather than solving some constrained convex optimization problem in n dimensions and possibly many constraints.