Accelerated Stochastic Greedy Coordinate Descent by Soft Thresholding Projection onto Simplex

Chao-Bing Song, Shaobo Cui, Yong Jiang, Shu-Tao Xia

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

Abstract

In this paper we study the well-known greedy coordinate descent (GCD) algorithm to solve $\ell_1$-regularized problems and improve GCD by the two popular strategies: Nesterov's acceleration and stochastic optimization. Firstly, we propose a new rule for greedy selection based on an $\ell_1$-norm square approximation which is nontrivial to solve but convex; then an efficient algorithm called ``SOft ThreshOlding PrOjection (SOTOPO)'' is proposed to exactly solve the $\ell_1$-regularized $\ell_1$-norm square approximation problem, which is induced by the new rule. Based on the new rule and the SOTOPO algorithm, the Nesterov's acceleration and stochastic optimization strategies are then successfully applied to the GCD algorithm. The resulted algorithm called accelerated stochastic greedy coordinate descent (ASGCD) has the optimal convergence rate $O(\sqrt{1/\epsilon})$; meanwhile, it reduces the iteration complexity of greedy selection up to a factor of sample size. Both theoretically and empirically, we show that ASGCD has better performance for high-dimensional and dense problems with sparse solution.
BibTeX
@inproceedings{song2017accelerated,
  author = {Chao-Bing Song and Shaobo Cui and Yong Jiang and Shu-Tao Xia},
  title = {{Accelerated Stochastic Greedy Coordinate Descent by Soft Thresholding Projection onto Simplex}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=Byb3Kwbd-H},
}
Figure