Breaking the Nonsmooth Barrier: A Scalable Parallel Method for Composite Optimization
Due to their simplicity and excellent performance, parallel asynchronous variants of stochastic gradient descent have become popular methods to solve a wide range of large-scale optimization problems on multi-core architectures. Yet, despite their practical success, support for nonsmooth objectives is still lacking, making them unsuitable for many problems of interest in machine learning, such as the Lasso, group Lasso or empirical risk minimization with convex constraints. In this work, we propose and analyze PROXASAGA, a fully asynchronous sparse method inspired by SAGA, a variance reduced incremental gradient algorithm. The proposed method is easy to implement and significantly outperforms the state of the art on several nonsmooth, large-scale problems. We prove that our method achieves a theoretical linear speedup with respect to the sequential version under assumptions on the sparsity of gradients and block-separability of the proximal term. Empirical benchmarks on a multi-core architecture illustrate practical speedups of up to 12x on a 20-core machine.
The main contribution of this paper is to offer a convergence proof for minimizing sum fi(x) + g(x) where fi(x) is smooth, and g is nonsmooth, in an asynchronous setting. The problem is well-motivated; there is indeed no known proof for this, in my knowledge.
A key aspect of this work is the block separability of the variable, which allows for some decomposition gain in the prox step (since the gradient of each fi may only effect certain indices of x.) This is an important practical assumption, as otherwise the prox causes locks, which may be unavoidable. (It would be interesting to see element-wise proxes, such as shrinkage, being decomposed as well.)
Their are two main theoretical results. Theorem 1 gives a convergance rate for proxSAGA, which is incrementally better than a previous result. Theorem 2 gives the rate for an asynchronous setting, which is more groundbreaking.
Overall I think it is a good paper, with a very nice theoretical contribution that is also practically very useful. I think it would be stronger without the sparsity assumption, but the authors also say that investigating asynchronosy without sparsity for nonsmooth functions is an open problem, so that is acknowledged.
potentially major comment:
 - Theorem 2 relies heavily on a result from leblond 2017, which assumes smooth g's. It is not clear in the proof that the parts borrowed from Leblond 2017 does not require this assumption. 
minor comments about paper: 
 - line 61, semicolon after "sparse"
 - line 127: "a a"
minor comments about proof (mostly theorem 1):
 - eq. (14) is backwards (x-z, not z-x)
 - line 425: do you mean x+ = x - gamma vi?
 - Lemma 7 can divide RHS by 2 (triangle inequality in line 433 is loose)
 - line 435: not the third term (4th term)
 - line 444: I am not entirely clear why EDi = I. Di has to do with problem structure, not asynchronasy?
 - eq (33) those two are identical, typo somewhere with missing Ti?
 - line 447: Not sure where that split is coming from, and the relationship between alpha i, alpha i +, and grad fi.
 - line 448: there is some mixup in the second line, a nabla f_i(x*) became nabla f_i(x).
Some of these seem pretty necessary to fix, but none of these seem fatal, especially since the result is very close to a previously proven result.
I mostly skimmed theorem 2 proof; it looks reasonable, apart from the concern of borrowing results from Leblond (assumptions on g need to be clearer)