Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function

Peter Richtárik, Martin TakácMath. Program 2014 · OpenReview

TL;DR

This paper introduces a novel randomized block-coordinate descent (RCDC) method for optimizing composite functions (smooth plus nonsmooth parts). It achieves faster convergence rates than previous methods, works without needing to regularize the objective function (a key improvement), and scales to problems with billions of variables, demonstrating its practical utility.

What Problem Does This Paper Address?

Many real-world optimization problems involve minimizing a function that's a sum of two parts: a smooth part (like a squared error term) and a nonsmooth part (like an L1-norm penalty that encourages sparsity). These problems can be enormous, with billions of variables, making traditional optimization methods too slow or memory-intensive. Existing methods for such "composite" problems often rely on regularizing the objective function to make it strongly convex, which introduces unknown parameters and makes the theoretical guarantees less direct. This paper aims to develop an efficient RCDC method for composite functions that directly tackles the problem without regularization, offers improved theoretical guarantees, and scales to massive datasets.

Methods

The core contribution is a Randomized Block-Coordinate Descent (RCDC) algorithm. The key ideas are:

  • Block-Coordinate Descent: Instead of updating all variables at once, RCDC updates one "block" of variables at a time, keeping others fixed. This is crucial for large-scale problems.
  • Randomization: The block to be updated is chosen randomly at each iteration. This is shown to be more robust and easier to analyze than deterministic strategies.
  • Composite Objective Handling: The method is specifically designed for functions that are a sum of a smooth and a block-separable nonsmooth convex function.
  • No Regularization: Unlike prior work, this method achieves its theoretical guarantees without adding a quadratic regularization term to the objective. This is a significant practical advantage as it avoids unknown parameters.
  • Improved Complexity: The paper provides theoretical bounds on the number of iterations needed to reach a certain accuracy. These bounds are improved by a factor of 4 compared to related work and have a more favorable logarithmic term.
  • General Norms and Probabilities: The analysis holds for arbitrary norms and allows for flexible probability distributions for selecting blocks, not just uniform or Lipschitz-constant-proportional choices.

Datasets

The paper uses synthetic datasets for experiments, specifically for:

  • Sparse Regression / Lasso: Problems of size up to $m=10^7$ and $n=10^6$ variables, with up to $5 \times 10^7$ nonzeros in the matrix $A$. They also test with a matrix $A$ having 20 billion nonzeros.
  • Linear Support Vector Machines (SVM):
    • Small scale: The rcv1.binary dataset (47,236 features, 20,242 training, 677,399 testing instances).
  • Large scale: The kdd2010 (bridge to algebra) dataset (29,890,095 features, 19,264,097 training, 748,401 testing instances).

Key Insights and Ideas

  • Direct Optimization is Possible: The most significant insight is demonstrating that strong theoretical guarantees for RCDC on composite functions can be achieved without resorting to regularization. This simplifies the method and removes the need to tune regularization parameters.
  • Randomization's Power: The paper reinforces the idea that randomized approaches, particularly for block selection, can lead to better theoretical bounds and practical performance, especially for large-scale problems.
  • Block-Coordinate Lipschitz Constants Matter: The analysis highlights that using individual block-coordinate Lipschitz constants ($L_i$) for each block leads to better complexity than using a single global Lipschitz constant.
  • Scalability to Billions: The numerical experiments showcasing the method's ability to solve problems with billions of variables are a major practical takeaway, suggesting RCDC is a viable tool for extreme-scale optimization.
  • "Shrinking" Heuristic: The paper introduces a "shrinking" heuristic for probability vectors that adaptively focuses on blocks that are likely to contain non-zero elements, significantly speeding up convergence in practice.

Key Results

  • Theoretical Guarantees: The RCDC method achieves an $\epsilon$-accurate solution with probability at least $1-\rho$ in $O(n \log(1/\rho) / \epsilon)$ iterations for composite functions, and linear convergence for strongly convex functions. These bounds are an improvement over prior work.
  • Practical Performance:
    • The method successfully solves sparse regression problems with up to a billion variables.
  • For a problem with $10^6$ variables, it achieves a $10^{-18}$ reduction in the objective residual in about 1.5 minutes.
  • For a problem with a billion variables, it reduces the residual by a factor of $10^{29}$ in about 139 seconds.
  • SVM training on large datasets (e.g., kdd2010) is achieved in minutes.
  • The "shrinking" heuristic provides a significant speedup, achieving a 70% saving for certain accuracy levels.

Limitations and Future Work

  • "Vacuous Updates": The paper notes that RCDC, as presented, can spend time updating coordinates that are already zero, which is inefficient. The "shrinking" heuristic is proposed as a way to mitigate this.
  • Regularization Constants: While the main method doesn't require regularization, the alternative approach discussed in Section 3.3 uses regularization, and the constants are not known in advance, limiting its practical applicability.
  • Future Work: The paper mentions that a more detailed report on the study of (Sparse) Group Lasso problems will be provided separately. The "shrinking" heuristic is presented as a promising direction for further research. The authors also suggest that adaptively changing probabilities could be further explored.

Summary updated

Abstract

In this paper we develop a randomized block-coordinate descent method for minimizing the sum of a smooth and a simple nonsmooth block-separable convex function and prove that it obtains an $$\varepsilon $$ -accurate solution with probability at least $$1-\rho $$ in at most $$O((n/\varepsilon ) \log (1/\rho ))$$ iterations, where $$n$$ is the number of blocks. This extends recent results of Nesterov (SIAM J Optim 22(2): 341–362, 2012), which cover the smooth case, to composite minimization, while at the same time improving the complexity by the factor of 4 and removing $$\varepsilon $$ from the logarithmic term. More importantly, in contrast with the aforementioned work in which the author achieves the results by applying the method to a regularized version of the objective function with an unknown scaling factor, we show that this is not necessary, thus achieving first true iteration complexity bounds. For strongly convex functions the method converges linearly. In the smooth case we also allow for arbitrary probability vectors and non-Euclidean norms. Finally, we demonstrate numerically that the algorithm is able to solve huge-scale $$\ell _1$$ -regularized least squares problems with a billion variables.
BibTeX
@inproceedings{richtarik2014iteration,
  author = {Peter Richtárik and Martin Takác},
  title = {{Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function}},
  booktitle = {Math. Program},
  year = {2014},
  url = {https://openreview.net/forum?id=XLolbpEt1OB},
}
Figure