- Regret Analysis of Block Coordinate Gradient Methods for Online Convex Programming Hua Xiaoqin (hccyangzhou163.com) Katomoto So (nobuoi.kyoto-u.ac.jp) Yamashita Nobuo (nobuoi.kyoto-u.ac.jp) Abstract: 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. Keywords: Cyclic rule, Random rule, Regret, Online convex programming Category 1: Applications -- OR and Management Sciences Category 2: Stochastic Programming Category 3: Nonlinear Optimization Citation: Institution address: Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Kyoto 606-8501. Month/year: 1/2015 Download: [PDF]Entry Submitted: 01/28/2015Entry Accepted: 01/28/2015Entry Last Modified: 05/12/2015Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.