Abstract
We consider the problem of minimizing the sum of two convex functions: one is smooth and given by a gradient oracle, and the other is separable over blocks of coordinates and has a simple known structure over each block. We develop an accelerated randomized proximal coordinate gradient (APCG) method for minimizing such convex composite functions. For strongly convex functions, our method achieves faster linear convergence rates than existing randomized proximal coordinate gradient methods. Without strong convexity, our method enjoys accelerated sublinear convergence rates. We show how to apply the APCG method to solve the regularized empirical risk minimization (ERM) problem, and devise efficient implementations that 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.
Introduction
In the era of big data, large-scale machine learning requires optimization algorithms that can handle millions of features and samples efficiently. The standard approach involves minimizing a "composite" objective function: a smooth loss function (e.g., logistic loss) combined with a non-smooth regularizer (e.g., $L_1$ norm or box constraints).
Traditionally, practitioners have relied on two main families of algorithms: Full Gradient Methods and Coordinate Descent (CD). While Full Gradient Methods can be "accelerated" using Nesterov’s techniques to reduce the number of iterations, their per-iteration cost is prohibitive for high-dimensional data. Conversely, Randomized Coordinate Descent methods are computationally cheap per iteration but often struggle with "ill-conditioned" problems—where the objective function is highly sensitive in certain directions—leading to slow convergence. This paper introduces the Accelerated Proximal Coordinate Gradient (APCG) method, bridging the gap between these two approaches by bringing Nesterov-style acceleration to the randomized coordinate descent framework.
The APCG Framework
The APCG method is designed to minimize functions of the form: $$\min_{x \in \mathbb{R}^N} \phi(x) \stackrel{\text{def}}{=} f(x) + \Psi(x)$$ where $f$ is a smooth convex function and $\Psi$ is a block-separable convex function (possibly non-smooth). The method integrates three core components:
- Randomized Block Selection: At each iteration, the algorithm randomly selects a block of coordinates to update. This ensures that the computational cost per iteration remains low, proportional to the size of the block rather than the full dimension $N$.
- Proximal Mapping: This operator allows the algorithm to handle the non-smooth component $\Psi$ efficiently, making it suitable for regularized problems like Lasso or SVMs.
- Nesterov Acceleration: APCG maintains three distinct sequences of vectors ($x, y, z$). By calculating a specific linear combination of these sequences, the algorithm effectively "looks ahead" in the search space, which significantly speeds up convergence.
Efficient Implementation
A significant challenge in accelerating coordinate descent is the "look-ahead" step. In a naive implementation, updating the auxiliary sequences would require $O(N)$ operations, negating the efficiency gains of coordinate descent. The authors overcome this by introducing a "change of variables" technique. This allows the algorithm to perform updates in $O(\text{sparsity of the block})$ time, making the acceleration computationally "free" relative to standard coordinate descent.
Theoretical Contributions
The primary theoretical breakthrough of this work is the proof of accelerated linear convergence for strongly convex functions.
- Complexity Comparison: For a problem with condition number $\kappa$, standard non-accelerated methods like Stochastic Dual Coordinate Ascent (SDCA) require $O((n+\kappa)\log(1/\epsilon))$ iterations.
- APCG Advantage: APCG achieves a complexity of $O(n\sqrt{\kappa}\log(1/\epsilon))$.
In scenarios where the problem is ill-conditioned (i.e., $\kappa > n$), APCG provides a substantial theoretical speedup. For non-strongly convex problems, the method still maintains an accelerated sublinear convergence rate of $O(1/k^2)$.
Empirical Performance
The authors validated APCG using three large-scale binary classification datasets from the LIBSVM repository: RCV1, covtype, and News20. These datasets vary in sparsity and scale, providing a comprehensive testing ground for the algorithm.
Key findings from the experiments include:
- Ill-Conditioned Success: The performance gap between APCG and other methods is most pronounced when the regularization parameter ($\lambda$) is very small. In these ill-conditioned settings, APCG reaches high-precision solutions significantly faster than SDCA or Accelerated Full Gradient (AFG) methods.
- News20 Results: On the News20 dataset with $\lambda = 10^{-8}$, APCG achieved convergence in approximately 80 passes through the data, while competing methods remained orders of magnitude away from the optimal solution.
- Primal-Dual Gap: APCG demonstrated a superior ability to reduce the primal-dual gap, a rigorous metric for solution quality, compared to state-of-the-art solvers.
Conclusion and Limitations
APCG represents a significant advancement in randomized optimization, offering the first method to achieve accelerated linear convergence for strongly convex composite functions. Its efficient implementation makes it a practical choice for high-dimensional, ill-conditioned empirical risk minimization problems.
However, the method does have constraints. The non-smooth regularizer $\Psi$ must be block-separable; if the variables are tightly coupled in the non-smooth term, the coordinate descent approach is not directly applicable. Additionally, achieving the optimal linear rate requires knowledge of the strong convexity parameter $\mu$. While the authors provide a variant for unknown $\mu$, it only guarantees sublinear acceleration. Future work may explore extending these efficient acceleration techniques to distributed systems or non-separable regularizers.
Summary updated