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:
- Proximal Gradient Methods: These are stable but require passing through the entire dataset every iteration, making them prohibitively slow for massive datasets.
- 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.
- 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.
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.
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