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.
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.
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