In this paper, we propose two block coordinate gradient (BCG) methods for the online convex programming: the BCG method with the cyclic rule and the BCG method with the random rule. The proposed methods solve a low dimensional problem at each iteration, and hence they are efficient for large scale problems. For the proposed methods, under usual assumptions for the online programming, we show that their regret bounds are $O(\sqrt{T})$, where $T$ is the number of time steps. These results are natural extensions of that for the greedy projection method by Zinkevich.
Citation
Institution address: Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Kyoto 606-8501. Month/year: 1/2015
Article
View Regret Analysis of Block Coordinate Gradient Methods for Online Convex Programming