An Efficient Interior-Point Method for Online Convex Optimization
This work provides an efficient method for online convex optimization, which is incremental as it builds on existing interior-point approaches to improve computational aspects.
The paper tackles regret minimization in online convex optimization by introducing a new algorithm that achieves an optimal regret bound of O(√(T log T)) and is adaptive to sub-intervals, with a running time that involves solving linear equations instead of constrained 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(\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.