Towards Understanding Acceleration Tradeoff between Momentum and Asynchrony in Nonconvex Stochastic Optimization
Asynchronous momentum stochastic gradient descent algorithms (Async-MSGD) have been widely used in distributed machine learning, e.g., training large collaborative filtering systems and deep neural networks. Due to current technical limit, however, establishing convergence properties of Async-MSGD for these highly complicated nonoconvex problems is generally infeasible. Therefore, we propose to analyze the algorithm through a simpler but nontrivial nonconvex problems -streaming PCA. This allows us to make progress toward understanding Aync-MSGD and gaining new insights for more general problems. Specifically, by exploiting the diffusion approximation of stochastic optimization, we establish the asymptotic rate of convergence of Async-MSGD for streaming PCA. Our results indicate a fundamental tradeoff between asynchrony and momentum: To ensure convergence and acceleration through asynchrony, we have to reduce the momentum (compared with Sync-MSGD). To the best of our knowledge, this is the first theoretical attempt on understanding Async-MSGD for distributed nonconvex stochastic optimization. Numerical experiments on both streaming PCA and training deep neural networks are provided to support our findings for Async-MSGD.
This manuscript analyzes the asymptotic  convergence of asynchronous momentum SGD (AMSGD) for streaming PCA. The fundamental claim [line 101 & 239] is that asymptotically, for streaming PCA, the delay tau is allowed to scale as     (1 - mu)^2 / sqrt(eta),  where mu is the step size and mu the momentum parameter.  Major Comments ============== Before we discuss the proof, I think the introduction is somewhat misleading. In line 76, the authors point out previous work all focus on analyzing convergence to a first order optimal solution. The readers can be confused that this paper improved the results of previous work. However, the problems studies in those paper and streaming PCA are different. As the authors also pointed out, streaming PCA is a very special case that all first order optimal solution is either global optimal or strict saddle point, but the previous work you mentioned studied more general or harder problems.  I would suggest you clarity this part clearly.   The proof has a few steps. In high level, the structure of the theoretical analysis should be improved.  Quite a few places of the presentation have inconsistency or undefined symbols.  I will mention them when discussing the proof as below.  1) Show the norm of iterates and the distance between any consecutive iterates are bounded.  2) Rewrite the ascent direction as a sum of three terms: one only involves the expectation of data matrix Sigma (m_k), and other two (beta_k and epsilon_k) contains the sample deviation (Simga_k - Simga).    The notation Simga_k was not defined, though I can infer it's X_k X_k^T. Besides, a small mistake: in line 162, equation (6), eta is a factor for all three terms m, beta and epsilon, but the momentum parameter mu wasn't rescaled.  One question I have is how to preserve the norm of v_k, as no projection step is used. Though we can see it's upper bounded, but it is not straightforward for me to see why it's also lower bounded.  3) Ignore beta and epsilon, proof that {v_k} converges to the principal eigenvector of Sigma. To show that, the authors exploits the rotation under eigenvalue decomposition and reparameterized V to H.  4) Consider the stochastic version of ODE. I'm lost in this part, as many notations are not defined. For example, in Thm 5, line 204, what is Y? In Proposition 6, what is phi? I don't have a good assessment for this part due to limited understanding.  Overall, I think this paper is solid work, but the current version might be preliminary for a publishment.  The theoretical part needs to be clarified to bring a clear and convincing analysis.    Minor Comments =============== Line 24, 30, 63: This manuscript is notation heavy. I understand you want to first state general AMSGD and then focus on streaming PCA. But if you can replace theta by v in the introduction, it will save you one parameter.   Line 32: equation (3) should be (2). (2) is MSGD and (3) is AMSGD Line 171: taht --> that Line 385 (Appendix) The hyperef to one section didn't compile.