Smooth Primal-Dual Coordinate Descent Algorithms for Nonsmooth Convex Optimization
We propose a new randomized coordinate descent method for a convex optimization template with broad applications. Our analysis relies on a novel combination of four ideas applied to the primal-dual gap function: smoothing, acceleration, homotopy, and coordinate descent with non-uniform sampling. As a result, our method features the first convergence rate guarantees among the coordinate descent methods, that are the best-known under a variety of common structure assumptions on the template. We provide numerical evidence to support the theoretical results with a comparison to state-of-the-art algorithms.
The authors propose a new smooth primal-dual randomized coordinate descent method for the three composite problem F(x) = f(x) + g(x) + h(Ax), where f is smooth, g is non-smooth, separable and has a block-wise proximal operator, and h is a general nonsmooth function. The method is basically a generalization of the accelerated, parallel, and proximal coordinate descent method of Fercoq and Richtarik, and the coordinate descent method with arbitrary sampling of Qu and Richtarik to the three composite case. The difficulty of this extension lies in the non-smoothness of the function h composed with a linear operator A. The authors provide an efficient implementation by breaking up full vector updates. They show that the algorithm achieves the best known O(n/k) convergence rate. Restart schemes are also used to improve practical performance. Special cases of the three composite problem are considered and analyzed. 
The contributions are clearly stated and overall, this is a nice paper. It is applicable to many different objective functions and employs all the "tricks" to make this a fast and efficient method.
Comments:
- The smoothing and non-uniform sampling techniques of Algorithm 1 are clearly described in Section 2, but the homotopy and acceleration techniques are not described anywhere, they are just directly used in Alg 1. This makes Alg. 1 a little cryptic if you are unfamiliar with the structure of these methods -- I think Alg. 1 needs to be better explained either in words or indicating what method/approach each step corresponds to.
- Following from the previous comment, ll 9 of Algorithm 1 - where does this formula for \tau come from?, ll 153 - where does the adapted \tau formula come from for the strongly convex case? This is not clear.
- What are the values of \hat{x}, \tilde{x} and \bar{x} initialized to in Alg 1?
- What is the "given" value of \dot{y} (re: line 73 and equation (6))?
- Unknown reference in line 165.
============ 
POST REBUTTAL
============ 
I have read the author rebuttal and the other reviews. I thank the authors for addressing my comments/questions, as well as the comments/questions of the other reviewers. My recommendation stands, I think this paper should be accepted.