The Sound of APALM Clapping: Faster Nonsmooth Nonconvex Optimization with Stochastic Asynchronous PALM
We introduce the Stochastic Asynchronous Proximal Alternating Linearized Minimization (SAPALM) method, a block coordinate stochastic proximal-gradient method for solving nonconvex, nonsmooth optimization problems. SAPALM is the first asynchronous parallel optimization method that provably converges on a large class of nonconvex, nonsmooth problems. We prove that SAPALM matches the best known rates of convergence -among synchronous or asynchronous methods -on this problem class. We provide upper bounds on the number of workers for which we can expect to see a linear speedup, which match the best bounds known for less complex problems, and show that in practice SAPALM achieves this linear speedup. We demonstrate state-of-the-art performance on several matrix factorization problems.
The paper proposes an asynchronous proximal gradient descent algorithm and provides a proof of its guaranteed convergence to a local optimal solution. The main contribution is the finding that the prox function for nonconvex problems defines a set which in turn induces a measurable space and to interpret the unchecked asynchronous updates of variables as a source of noise when computing the gradient. In doing so, the distributed computation can be seen as an instance of stochastically altered gradient descent algorithm. The authors report convergence behavior under two different noise regimes resulting in constant and decreasing step sizes respectively.
I find the approach rather interesting, especially the broad and general definition of the problem makes the approach applicable to a wide range of problems. However, I was surprised by the absence of any reference to the seminal Robbins/Munro paper and also to the recent developments in stochastic gradient descent based sampling (see below). The authors do local gradient descent updates of coordinate blocks by computing partial gradients and adding noise in each asynchronous step. I was wondering, how this relates to the "usual" stochastic gradient descent update, i.e., given that the locally computed partial gradient will be based on delayed (noisy) variable states, a sequence of these noisy partial gradients would converge to the true partial gradient as well.  Further, recent SGD based sampling has shown that adding noise to the variable states obtained by noisy gradient updates (as the authors do as well) provides good samples of the distribution underlying the optimal variable setting also in a non-convex setting.  That being said, the work handed in remains valid, but it would have been interesting to compare the proposed approach to well established stochastic gradient methods. The overall procedure is laid out well and comprehensible. The chosen examples in the experiments section are well suited to demonstrate the scalability benefits of the algorithm.  Minor to that, I have a few remarks on style and the overall rationale: - line 60: "each" is unnecessary here when m = 1 - line 69: k is not yet defined as are g, and \nu - line 106: the notation using y is probably wrong, shouldn't it read argmin_{x_{j_k}^k} r_{j_k} (x_{j_k}^k) + ... ? - Algorithms 1 and 2 lack a break condition and output - Table 1: I assume the timing is in seconds?  Literature: Robbins, H., & Monro, S. (1951). A stochastic approximation method. The Annals of Mathematical Statistics, 400–407. Welling, M., & Teh, Y.-W. (2011). Bayesian learning via stochastic gradient Langevin dynamics (pp. 681–688). Presented at the Proceedings of the 28th International Conference on Machine Learning.