Optimization Online


Regret Analysis of Block Coordinate Gradient Methods for Online Convex Programming

Hua Xiaoqin (hccyangzhou***at***163.com)
Katomoto So (nobuo***at***i.kyoto-u.ac.jp)
Yamashita Nobuo (nobuo***at***i.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/2015
Entry Accepted: 01/28/2015
Entry Last Modified: 05/12/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society