An Efficient Interior-Point Method for Online Convex Optimization
Elad Hazan Nimrod Megiddo
A new algorithm for regret minimization in online convex optimization is
described. The regret of the algorithm after $T$ time periods is $O(\sqrt{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.