Geometric Descent Method for Convex Composite Minimization
In this paper, we extend the geometric descent method recently proposed by Bubeck, Lee and Singh [1] to tackle nonsmooth and strongly convex composite problems. We prove that our proposed algorithm, dubbed geometric proximal gradient method (GeoPG), converges with a linear rate (1 − 1/ √ κ) and thus achieves the optimal rate among first-order methods, where κ is the condition number of the problem. Numerical results on linear regression and logistic regression with elastic net regularization show that GeoPG compares favorably with Nesterov's accelerated proximal gradient method, especially when the problem is ill-conditioned.
Summary: The paper extends the recent work of Bubeck et al. on the geometric gradient descent method, in order to handle non-smooth (but “nice”) objectives. Similar work can be found in [10]; however, no optimal rates are obtained in that case (in the sense of having a square root condition number in the retraction factor). The core ideas and motivation origin from the proximity operators used in non-smooth optimization in machine learning and signal processing (see e.g., lasso).
Quality: The paper is of good technical quality - for clarity see below. The results could be considered “expected” since similar results (from smooth to non-smooth convex objectives with proximal operators) have been proved in numerous papers the past decade; especially under convexity assumptions.
Technical correctness: I believe that the results I read in the main are correct.
Impact: The paper might have a good impact on the direction of demystifying Nesterov’s accelerated routines like FISTA (by proposing alternatives). I can see several ramifications based on this work, so I would say that the paper has at least some importance.
Clarity: My main concern is the balance of being succinct and being thorough. The authors tend towards the former; however, several parts of the paper are no clear (especially the technical ones). Also, the whole idea of this line of work is to provide a better understanding of accelerated methods; the paper does not provide much intuition on this front (update: there is a paragraph in the sup. material - maybe the authors should consider moving that part in the main text).
Comments:
1. Neither here, nor in the original paper of Bubeck it is clear how we get some basic arguments: E.g., I “wasted” a lot of time to understand how we get to (2.2) by setting y = x^* in (2.1). Given the restricted review time, things need to be crystal clear, even if they are not in the original paper, based on which this work is conducted.
Maybe this can be clarified by the rest of the reviewers. Assuming y = x++, this gives the bound x* \in B(x++,  2/\alpha^2 * || \nabla f(x) ||_2^2 - 2/\alpha (f(x) - f(x++))), but f(x*) \leq f(x++), so we cannot naively substitute it there. Probably I’m missing something fundamental.   
Overall: There is nothing strongly negative about the paper - I would say, apart from some clarity issues and given that proofs work through, it is a “weak accept”.