Local Linear Convergence of Forward-Backward under Partial Smoothness
In this paper, we consider the Forward-Backward proximal splitting algorithm to minimize the sum of two proper closed convex functions, one of which having a Lipschitz continuous gradient and the other being partly smooth relative to an active manifold M. We propose a generic framework under which we show that the Forward-Backward (i) correctly identifies the active manifold M in a finite number of iterations, and then (ii) enters a local linear convergence regime that we characterize precisely. This gives a grounded and unified explanation to the typical behaviour that has been observed numerically for many problems encompassed in our framework, including the Lasso, the group Lasso, the fused Lasso and the nuclear norm regularization to name a few. These results may have numerous applications including in signal/image processing processing, sparse recovery and machine learning.
The FBS algorithm has been rediscovered in the last 10 years along with other splitting algorithms like the Douglas-Rachford algorithm. FBS is a simple algorithm to minimize a functional which consists of the sum of a smooth function and one for which the prox-operator can be solved efficiently. It first applies a gradient descent step (thus it is a first-order method) on the smooth part after which the prox-operator of the nonsmooth part is applied. This algorithm is used in many machine learning and imaging applications and a lot of research has been done to speed it up (FISTA, Barzilai-Borwein step sizes etc.).Hence, analyzing the convergence properties of FBS which is the topic of the current paper is interesting for the NIPS community.The main contribution of this paper is to make use of the concept of partial smoothness to derive convergence results given in Theorem 3.1. Although this idea was employed before, the results seem novel and interesting. Generally, I think that the paper would have improved a lot if the authors put the convergence proof in the supplementary material and spend these two pages to discuss their results in more detail. For example, the results in Remark 3.2 are interesting but it should be made clear whether they can be found somewhere, are easy to obtain or their proof is too long to be included here. In the last sentence of the abstract, the authors mention the importance for applications but only Remark 3.4 follows this thought. A natural question is how one can make use of the finite identification property, i.e., if there is a way to identify the index K of part 2. of the proof and how the algorithm can be adapted once K is reached. One could at least experimentally analyze finite identification property. The plots provided here focus on the asymptotic behavior. The example problems considered in the paper are well-chosen since one clearly sees differences according to cases i) and ii) of the main theorem. However, showing maybe one real-world example would be beneficial. In addition, especially for readers new to the topic, it would be worthwhile to make the step from Theorem 3.1 to the examples easier by explicitly checking all conditions of the theorem, even ones which might be clear like (3.1). The last paragraph on p. 5 about the difference in the tightness of the convergence rate are very interesting and should be treated in broader detail. Is there a mathematical justification why exactly the bottom two convergence curves are less tight? (apart from the general observation on the properties of the manifold and the sign vectors)Furthermore, an outlook on generalizations (if possible) of the results presented here would be good: Do the results generalize to an infinite dimensional setting? Are they transferable to other splitting methods like the Douglas-Rachford method? Can parts of the results be carried over to the non-convex setting? How about versions of FBS which employ speed-up strategies, e.g. FISTA?Minor things:- define polyhedral gauge functions- p. 3, l. 128: define "generalized sign vector"- p. 3, l. 127: typo: subsclass - p. 5, l. 234 typo: taut string algorithm