Timezone: »

 
Poster
Accelerated Mini-batch Randomized Block Coordinate Descent Method
Tuo Zhao · Mo Yu · Yiming Wang · Raman Arora · Han Liu

Thu Dec 11 11:00 AM -- 03:00 PM (PST) @ Level 2, room 210D
in Poster Session »

We consider regularized empirical risk minimization problems. In particular, we minimize the sum of a smooth empirical risk function and a nonsmooth regularization function. When the regularization function is block separable, we can solve the minimization problems in a randomized block coordinate descent (RBCD) manner. Existing RBCD methods usually decrease the objective value by exploiting the partial gradient of a randomly selected block of coordinates in each iteration. Thus they need all data to be accessible so that the partial gradient of the block gradient can be exactly obtained. However, such a ``batch" setting may be computationally expensive in practice. In this paper, we propose a mini-batch randomized block coordinate descent (MRBCD) method, which estimates the partial gradient of the selected block based on a mini-batch of randomly sampled data in each iteration. We further accelerate the MRBCD method by exploiting the semi-stochastic optimization scheme, which effectively reduces the variance of the partial gradient estimators. Theoretically, we show that for strongly convex functions, the MRBCD method attains lower overall iteration complexity than existing RBCD methods. As an application, we further trim the MRBCD method to solve the regularized sparse learning problems. Our numerical experiments shows that the MRBCD method naturally exploits the sparsity structure and achieves better computational performance than existing methods.

[ PDF] 

Author Information

Tuo Zhao (Johns Hopkins University Princeton University)
Mo Yu (Johns Hopkins University)
Yiming Wang (Johns Hopkins University)
Raman Arora (Johns Hopkins University)
Han Liu (Tencent AI Lab)

More from the Same Authors