Introduction
In large-scale optimization, particularly within machine learning, practitioners frequently encounter a trade-off between speed and sparsity. Randomized Coordinate Descent (RCD) is computationally efficient because it updates one random variable at a time and can be combined with Nesterov's acceleration to reach solutions rapidly. Conversely, Greedy Coordinate Descent (GCD) selects the optimal variable to update at each step, making it vastly superior at finding sparse solutions where most variables are zero.
However, GCD has traditionally suffered from two major drawbacks: it converges slowly at a rate of $O(1/\epsilon)$, and it is computationally expensive because it requires calculating the full gradient of all variables to make its greedy selection. Furthermore, standard greedy selection rules are non-convex, which has historically made them incompatible with Nesterov’s acceleration techniques.
This paper introduces Accelerated Stochastic Greedy Coordinate Descent (ASGCD), a novel algorithm that successfully brings Nesterov’s acceleration and stochastic optimization to GCD. By reformulating the greedy selection process, the authors achieve the optimal $O(1/\sqrt{\epsilon})$ convergence rate while significantly reducing the computational overhead of greedy selection.
Methodology
To bridge the gap between greedy selection and acceleration, the authors introduce three major innovations:
1. A Convex Greedy Rule
The critical mechanism enabling acceleration is the shift from a standard cardinality constraint (picking 1 out of $d$ coordinates) to an $\ell_1$-norm square approximation. This transforms a traditionally non-convex selection problem into a convex one, unlocking the mathematical foundation necessary to apply Nesterov’s acceleration.
2. The SOTOPO Algorithm
Solving this new convex greedy rule is non-trivial. To address this, the authors developed SOTOPO (Soft Thresholding Projection onto Simplex), an efficient algorithm designed to solve the resulting subproblem exactly. SOTOPO reformulates the problem into a projection onto a simplex. By utilizing a novel filtering technique (detailed in the paper's Lemma 5), the algorithm can ignore many irrelevant variables during the sorting process. As a result, SOTOPO operates with a complexity of $O(d + |Q| \log |Q|)$, where $d$ is the total dimension and $|Q|$ is the number of "active" coordinates—a number often much smaller than $d$.
3. The ASGCD Framework
The authors integrate SOTOPO into the state-of-the-art "Katyusha" framework, an accelerated stochastic variance reduction method. This integration allows ASGCD to leverage mini-batches of data (stochasticity) and momentum (acceleration) without sacrificing the sparsity benefits of greedy coordinate selection.
The $L_1$ vs. $L_2$ Advantage
A key theoretical insight of this work lies in smoothness constants. Theoretical bounds for standard accelerated methods typically depend on the $L_2$-smoothness constant. In contrast, ASGCD's bounds depend on the $L_1$-smoothness constant. In high-dimensional, dense problems where the underlying solution is sparse, the $L_1$ constant can be significantly smaller than $L_2$ (up to a factor of $d$). This provides ASGCD with a massive theoretical and practical advantage.
Experiments and Results
The authors evaluated ASGCD on the Lasso problem using three well-known real-world datasets from the LIBSVM library:
- LEUKEMIA: A high-dimensional biological dataset (38 samples, 7,129 features).
- GISETTE: A handwritten digit recognition challenge dataset (6,000 samples, 5,000 features).
- MNIST: The classic digit dataset (60,000 samples, 780 features).
Key Findings: * Optimal Convergence: ASGCD successfully achieves the optimal convergence rate of $O(1/\sqrt{\epsilon})$, matching the best theoretical performance limits for first-order methods. * Empirical Speedup: Both the stochastic and deterministic versions of ASGCD consistently outperformed non-accelerated greedy methods (CGD) and standard accelerated full gradient methods (AFG). * High-Dimensional Dominance: ASGCD was particularly dominant on the LEUKEMIA and GISETTE datasets. For example, on GISETTE with a regularization parameter $\lambda = 10^{-2}$, ASGCD reached high accuracy significantly faster than the standard Katyusha algorithm.
Limitations and Future Directions
While ASGCD represents a significant step forward, the authors note a few limitations and areas for future research:
- Problem Scope: The current framework is specifically tailored for $\ell_1$-regularized problems, such as Lasso or $\ell_1$-logistic regression. Its applicability to other forms of regularization remains unexplored.
- Sorting Overhead: Although SOTOPO drastically reduces sorting costs, it still requires a sort operation bounded by $O(|Q| \log |Q|)$. Future research could explore randomized median-finding algorithms to potentially reduce the selection step to a linear-time complexity of $O(d)$.
- Parameter Sensitivity: As is common with accelerated stochastic methods, ASGCD's performance can be sensitive to hyperparameter choices (such as the $p$ parameter in $p$-norm divergence), though the paper provides specific tuning recommendations to mitigate this.
Summary updated