  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.
