Reviews: Accelerated Stochastic Greedy Coordinate Descent by Soft Thresholding Projection onto Simplex

Paper Summary: The main idea is that Nesterov's acceleration method's and Stochastic Gradient Descent's (SGD) advantages are used to solve sparse and dense optimization problems with high-dimensions by using an improved GCD (Greedy Coordinate Descent) algorithm. First, by using a greedy rule, an l_1 -square-regularized approximate optimization problem (find a solution close to x * within a neighborhood \epsilon) can be reformulated as a convex but non-trivial to solve problem. Then, the same problem is solved as an exact problem by using the SOTOPO algorithm. Finally, the solution is improved by using both the convergence rate advantage of Nesterov's method and the "reduced-by-one-sample" complexity of SGD. The resulted algorithm is an improved GCD (ASGCD Accelerated Stochastic Greedy Coordinate Descent) with a convergence rate of O(\sqrt{1/\epsilon}) and complexity reduced-by-one-sample compared to the vanilla GCD.