An Accelerated Proximal Coordinate Gradient Method

Qihang Lin, Zhaosong Lu, Lin XiaoNeurIPS 2014 · OpenReview

TL;DR

This paper introduces the Accelerated Randomized Proximal Coordinate Gradient (APCG) method, a new optimization algorithm that combines the computational efficiency of coordinate descent with Nesterov-style acceleration. It achieves faster linear convergence rates for strongly convex problems and significantly outperforms state-of-the-art methods like Stochastic Dual Coordinate Ascent (SDCA) when dealing with "ill-conditioned" machine learning problems.

The Challenge of Large-Scale Optimization

In large-scale machine learning, practitioners frequently encounter composite convex optimization problems. These problems involve minimizing a function composed of two parts: a smooth, differentiable component (such as a loss function) and a non-smooth but "separable" component (such as $L_1$ regularization or box constraints).

Coordinate Descent (CD) methods are highly popular for these tasks because they are computationally inexpensive per iteration, updating only one variable or block of variables at a time. However, standard CD methods can be slow to converge. Previous attempts to "accelerate" these methods using Nesterov's techniques either only applied to smooth functions or failed to fully exploit "strong convexity"—a mathematical property that typically enables much faster, linear convergence. The authors address this gap by developing a method that is both accelerated and capable of handling non-smooth, strongly convex objectives efficiently.

The APCG Method

The authors propose APCG, which integrates randomized coordinate updates into an accelerated proximal gradient framework. Key technical highlights include:

  • Randomized Block Selection: Instead of updating all variables simultaneously, the algorithm randomly selects one block of coordinates to update in each step.
  • Proximal Mapping: It handles the non-smooth portion of the objective using a proximal operator, allowing it to support regularizations like Lasso or various constraints.
  • Acceleration Scheme: The method maintains three sequences of vectors ($x, y, z$) to achieve the "accelerated" convergence rate.
  • Efficient Implementation: A major hurdle for accelerated CD methods is that acceleration steps typically require updating the entire high-dimensional vector, defeating the purpose of coordinate descent. The authors introduce a "change of variables" trick that allows the algorithm to perform updates in $O(\text{block size})$ time rather than $O(\text{total variables})$, making it highly practical for massive datasets.

Datasets

The authors evaluated APCG on three standard binary classification datasets from the LIBSVM repository, using them to solve Empirical Risk Minimization (ERM) problems with a smoothed hinge loss.

Summary of datasets used for evaluation, including sample size, feature count, and sparsity.

Key Insights and Results

The "Square Root" Speedup

Standard coordinate descent converges at a rate related to the condition number $\kappa$. APCG, however, converges at a rate related to $\sqrt{\kappa}$. In practice, if a problem is "ill-conditioned" (meaning it is very "flat" in some directions and "steep" in others), this square root improvement makes a massive difference in training time.

Beating State-of-the-Art SDCA

Stochastic Dual Coordinate Ascent (SDCA) has long been considered a state-of-the-art approach for these problems. APCG matches or beats SDCA's complexity, particularly when the regularization parameter $\lambda$ is very small (the ill-conditioned regime). Furthermore, applying APCG to the dual of the ERM problem proves to be a highly effective way to solve the primal problem, offering a robust alternative to stochastic gradient methods.

Empirical Performance

Theoretically, APCG achieves an expected convergence rate of $O((1 - \sqrt{\mu}/n)^k)$, where $n$ is the number of blocks and $\mu$ is the strong convexity parameter. This marks the first time such an accelerated linear rate has been obtained for this general class of problems.

Convergence comparison of AFG, SDCA, and APCG across different datasets and regularization parameters.

Empirically, APCG consistently reduces the primal objective gap faster than both SDCA and the Accelerated Full Gradient (AFG) method. As shown in the convergence plots, APCG is remarkably robust to scaling. On the highly sparse news20 dataset with a small regularization ($\lambda = 10^{-8}$), APCG reached a high-precision solution in about 40-60 passes through the data, whereas SDCA struggled to make significant progress even after 100 passes.

Limitations and Future Work

  • Dual vs. Primal: While the theoretical guarantees focus on the dual optimality gap, the experiments track the primal gap. The authors note that a specific "extra primal gradient step" can guarantee primal-dual convergence, though it is not the primary focus of this paper.
  • Parameter Sensitivity: Like many accelerated methods, APCG requires knowledge of the strong convexity parameter $\mu$. If $\mu$ is unknown or zero, the algorithm reverts to a sublinear (though still accelerated) rate.
  • Block Separability: The method relies on the non-smooth part of the objective being block-separable. If the regularization or constraints couple the variables together, this specific coordinate descent approach cannot be directly applied.

Summary updated

Abstract

We develop an accelerated randomized proximal coordinate gradient (APCG) method, for solving a broad class of composite convex optimization problems. In particular, our method achieves faster linear convergence rates for minimizing strongly convex functions than existing randomized proximal coordinate gradient methods. We show how to apply the APCG method to solve the dual of the regularized empirical risk minimization (ERM) problem, and devise efficient implementations that can avoid full-dimensional vector operations. For ill-conditioned ERM problems, our method obtains improved convergence rates than the state-of-the-art stochastic dual coordinate ascent (SDCA) method.
BibTeX
@inproceedings{lin2014accelerated,
  author = {Qihang Lin and Zhaosong Lu and Lin Xiao},
  title = {{An Accelerated Proximal Coordinate Gradient Method}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=Hk-ChOb_Wr},
}
Figure