Accelerated Stochastic Greedy Coordinate Descent by Soft Thresholding\n Projection onto Simplex

Chaobing Song, Shaobo Cui, Yong Jiang, Shu‐Tao Xia

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.

1. Introduction

In large-scale machine learning, efficiency is paramount. For $\ell_1$-regularized problems such as Lasso or sparse logistic regression, Greedy Coordinate Descent (GCD) is a preferred method due to its ability to identify sparse solutions rapidly by selecting the optimal coordinate for update at each iteration. However, GCD has historically faced two significant limitations: a sub-optimal convergence rate of $O(1/\epsilon)$ and a high per-iteration computational cost, as it typically requires a full gradient calculation to make a single greedy update. This bottleneck is particularly severe for high-dimensional datasets.

This paper introduces ASGCD, an algorithm that integrates Nesterov’s acceleration and stochastic optimization into the greedy coordinate descent framework. By addressing the non-convexity of traditional greedy selection rules, the authors achieve the optimal $O(\sqrt{1/\epsilon})$ convergence rate while maintaining low per-iteration costs.

2. The ASGCD Framework

The ASGCD algorithm is built upon three core innovations designed to overcome the theoretical and practical hurdles of traditional GCD.

2.1 A Convex Selection Rule

Standard greedy selection rules, such as the Gauss-Southwell rule, are non-convex because they rely on cardinality constraints (e.g., "pick exactly one coordinate"). This non-convexity prevents the application of Nesterov’s acceleration. The authors propose a new selection rule based on an $\ell_1$-norm square approximation of the objective function. This formulation is convex, providing the necessary mathematical foundation for acceleration.

2.2 The SOTOPO Solver

Solving the subproblem induced by the new convex selection rule is non-trivial. To address this, the authors developed the SOft ThreshOlding PrOjection (SOTOPO) algorithm. SOTOPO efficiently solves the $\ell_1$-regularized $\ell_1$-norm square approximation in $O(d + |Q| \log |Q|)$ time, where $d$ is the total dimension and $|Q|$ is the number of active coordinates. This efficiency ensures that the greedy selection process does not become a new computational bottleneck.

2.3 Stochastic Variance-Reduced Acceleration

ASGCD incorporates these components into the "Katyusha" framework, a state-of-the-art template for stochastic variance-reduced Nesterov acceleration. This allows the algorithm to utilize mini-batches of data rather than the full dataset for greedy choices, significantly reducing the cost per iteration for dense, high-dimensional problems.

3. Experimental Setup

The authors evaluated ASGCD against several state-of-the-art optimizers using three benchmark datasets from the LIBSVM library. These datasets represent various challenges in terms of sample size ($n$) and feature dimensionality ($d$).

Table 1: Characteristics of the datasets used in the experiments, highlighting the diversity in scale and dimensionality.

4. Results and Analysis

Empirical results demonstrate that ASGCD (particularly the stochastic version with batch size $b=1$) consistently outperforms standard GCD and other accelerated methods like Katyusha and SVRG on high-dimensional tasks.

Figure 1: Convergence performance (Log Loss vs. Number of Passes) on the Lasso problem across different datasets and regularization strengths ($\lambda$).

As illustrated in the plots, ASGCD achieves lower log-loss values with significantly fewer passes over the data. The performance advantage is most pronounced on the Leukemia and Gisette datasets, which are characterized by high dimensionality and density.

A key theoretical insight is that ASGCD’s convergence depends on the $L_1$-norm of the gradient and the $\ell_1$-norm of the optimal solution. For problems where the solution is sparse but the data is dense, this provides a much tighter bound than the $L_2$-norms used by standard accelerated gradient methods.

5. Conclusion

ASGCD successfully bridges the gap between greedy selection and Nesterov’s acceleration. While its primary advantage lies in problems where the $L_1/L_2$ smoothness ratio is favorable, it represents a significant step forward for high-dimensional optimization. Future work may focus on further optimizing the SOTOPO solver, potentially replacing the $O(|Q| \log |Q|)$ sorting step with a linear-time randomized median-finding algorithm to enhance scalability for even larger datasets.

Summary updated

Abstract

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

Loading related content...

Figure