Accelerated Mini-batch Randomized Block Coordinate Descent Method

Tuo Zhao, Mo Yu, Yiming Wang, Raman Arora, Han LiuNeurIPS 2014 · OpenReview

Introduction

In modern "Big Data" analysis, researchers frequently solve regularized Empirical Risk Minimization (ERM) problems. This involves finding model parameters that minimize a loss function (like least squares) combined with a penalty (like the $L_1$ norm for sparsity).

Historically, researchers have faced a strict trade-off between three optimization approaches:

  1. Proximal Gradient Methods: These are stable but require passing through the entire dataset every iteration, making them prohibitively slow for massive datasets.
  2. Stochastic Proximal Gradient (SPG): These methods are fast per iteration because they use small "mini-batches" of data. However, the inherent noise (variance) in sampling leads to slow, sublinear convergence.
  3. Randomized Block Coordinate Descent (RBCD): These are efficient for sparse problems because they update only a subset of coordinates at a time. Unfortunately, they still require a full pass of the data to calculate the partial gradient for those specific coordinates.

This paper introduces the Accelerated Mini-batch Randomized Block Coordinate Descent (MRBCD) method, a "doubly stochastic" optimization algorithm designed for large-scale sparse learning. By combining mini-batch data sampling with randomized block coordinate updates and a variance-reduction scheme, MRBCD achieves linear convergence rates while significantly reducing the computational cost per iteration.

The MRBCD Methodology

The core innovation of MRBCD is its use of "double stochasticity": in each iteration, the algorithm randomly selects a block of coordinates to update and estimates the gradient using only a mini-batch of data.

To prevent the noise of mini-batching from destroying the convergence rate, the authors implement two key enhancements:

  • Variance Reduction (MRBCD-II): Borrowing from semi-stochastic optimization techniques like SVRG, the algorithm uses a nested loop structure. An "outer loop" calculates an exact full gradient periodically, which is then used in the "inner loop" to correct the mini-batch estimates. This correction allows the algorithm to achieve a linear convergence rate despite using noisy samples.
  • Active Set Strategy (MRBCD-III): For sparse learning, many parameters eventually become zero. The authors use a "proximal gradient pilot" step at the start of each outer loop to identify which blocks of coordinates are likely to be non-zero (the "active set"). The inner loops then focus exclusively on these blocks, drastically reducing unnecessary computation.

Key Results and Performance

The paper evaluates the algorithms on two main tasks: a synthetic high-dimensional Lasso problem designed to test sparse signal recovery, and real-world text classification using the rcv1 dataset (Elastic-net regularized logistic regression).

Faster, Linear Convergence

By combining coordinate descent with variance-reduced mini-batching, MRBCD avoids the "batch" bottleneck of traditional coordinate descent while maintaining the fast convergence that simple stochastic methods lack. In simulations, MRBCD-II reached high precision significantly faster than standard Proximal Gradient (BPG) or standard Block Coordinate Descent (BRBCD). Unlike naive stochastic methods that plateau, MRBCD demonstrated a clear linear descent.

Convergence comparison showing MRBCD-II achieving a steep linear descent compared to baseline methods.

Scalability and Sparsity on Real Data

On the rcv1 dataset, MRBCD-III (utilizing the active set strategy) outperformed the Stochastic Proximal Variance Reduced Gradient (SPVRG) method. It successfully exploited the underlying sparsity of the text data to reach the optimal solution with far fewer computations. The "Active Set" strategy demonstrates that optimization doesn't just produce a sparse result; it can use that emerging sparsity to accelerate itself mid-run.

Comparison of partial gradient estimates required across different regularization indices, highlighting MRBCD-III's efficiency.

Limitations and Future Work

While MRBCD offers significant theoretical and practical advantages, there are a few limitations to consider:

  • Strong Convexity Requirement: The most impressive theoretical guarantees (like linear convergence) rely on the problem being strongly convex. While the authors suggest a perturbation approach for non-strongly convex problems, performance may vary.
  • Hyperparameter Tuning: The algorithm introduces parameters such as the update frequency and step size. While theoretical guidance is provided, practical performance often requires tuning these values for specific datasets.
  • Block Selection: The current method assumes a fixed partition of coordinates into blocks. Future work could explore dynamic or adaptive blocking strategies to further improve efficiency.

Summary updated

Abstract

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."
BibTeX
@inproceedings{zhao2014accelerated,
  author = {Tuo Zhao and Mo Yu and Yiming Wang and Raman Arora and Han Liu},
  title = {{Accelerated Mini-batch Randomized Block Coordinate Descent Method}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=BJV-xvb_Wr},
}
Figure