On last-iterate convergence of distributed Stochastic Gradient Descent algorithm with momentum

• Many typos (highlighted a few) and loosely defined quantities, which make the paper hard to read.
• Results are derived under (very) strong assumptions, assuming both Lipschitzness and boundedness of the gradients for instance, but also that iterates remain bounded almost surely (Assumption 2.4). This should be proven, as it depends on the algorithms, not assumed.
• Results are very coarse, in the sense that the impact of the distributed aspect is hardly investigated. Theorems give the same results for both D-PSGD and EASGD. This is because theorems are asymptotic, so that if one combines diminishing step-sizes with strong regularity assumptions then these distributed algorithms asymptotically behave as mini-batch SGD (the algorithms moves more and more slowly due to the step-size, but averaging is still performed at the same frequency).
• Results (both theory and experiments) make it look like the higher the momentum the better the results, with no upper bound on this.
• Experiments do not really have added value since this is a very classical setup, and the point of the paper is about last-iterate convergence, not comparing different values for momentum.

In the end, there is some value in these results, but rewriting is necessary to clarify the paper, higlight dependencies problem parameters (matrix W, momentum), and better justify the assumptions (is 2.4 technical or necessary? If technical it should be removed, otherwise it should be explained why one needs it). Non-asymptotic guarantees would also be highly appreciated.

Typos/reformulation needed:

Incorrect citations: no space and ~\citet{} instead of \citep{} Typos: 213: equation equation 7 261: low bound condition 281: equation equation many other equation equation

Definitions of convergence: not very rigorous in the way they are defined. For instance I understand that $\epsilon$-TAMS reads: for any given scalar $\epsilon > 0$, there exists $n>0$ (which depends on $\epsilon$) such that... but it's not how it's written.

Assumption 2.1: I guess "function" is missing?

What is u in Assumption 2.4 and Theorem 2.2?

$m \geq 1$, so the second term is useless in Theorem 2.2.

Figures and their legends are very small and hard to read.

a) To me, the results are not significant enough for justifying a publication in a top ML conference. Firstly, the main results Theorem 2.1 do not provide convergence rate results, it is just asymptotic convergence that is ensured. The convergence rate results in Theorem 2.2 are almost useless, see my comment c). Given that convergence and convergence rate is already established for these algorithms, just showing that the last iterate converges feels marginal.

b) Assumption 2.1(b), which states that the gradient is bounded, is quite strong; however, it is not the reason for my low score. But it means, e.g., that quadratic and strongly convex functions are not covered by the analysis.

c) The convergence rate results in Theorem 2.2 are under very strange assumptions. Firstly, Assumption 2.4 cannot be checked before running the algorithm, so it seems quite useless. Secondly, by Assumption 2.3 the function should be convex and have a unique optimizer. But it cannot be strongly convex, since by Assumption 2.1 the gradient should be bounded. I am not sure what functions satisfy these assumptions.

d) I don’t see the point with the experiment. The algorithms have already been studied and shown to converge, and numerically investigated, it is unclear what is the message? Also there any baselines and it is unclear if the assumptions of the theorems are satisfied for the considered setups.

• The proposed framework lacks sufficient novelty. It essentially extends existing algorithms by adding momentum steps, which does not introduce a significant new contribution.
• The last-iterate convergence results and the observation that the momentum term can accelerate the algorithm in the early stages are not novel and can be traced back to the work of Jin et al. (2022b). It appears that the extension is merely a straightforward modification without the introduction of any new techniques or insights..
• Limited theoretical scope: The analysis is restricted to convex functions, which significantly limits the generalizability of the results.
• Assumption 2.4 appears overly restrictive and may not hold in many practical scenarios.
• The experiments presented in the paper are overly simplistic and lack sufficient depth. The experiment only tests one kind of algorithms and its performance under different $\alpha$.
• The clarity of the presentation needs significant improvement. There are numerous typographical errors and unclear formulations throughout the paper

[1] On the convergence of mSGD and AdaGrad for stochastic optimization. In International Conference on Learning Representations, 2022b.

1. The literature review part misses some relevant works. In reviewing decentralized SGD, the authors reviewed existing works of decentralized SGD with single local update (line 94-95), and it seems that the authors are missing relevant works that allow multiple local updates such as [1] , and [2] with additional gradient tracking.
2. To establish last iterate convergence, this paper assumes bounded stochastic gradient, which is kind of strong, given that even the milder condition of gradient similarity, is not assumed in methods like SCAFFOLD [3], and gradient tracking [2]. What challenges might arise in extending the current analysis under relaxed conditions?
3. Could the authors clarify if Lemma A.2 requires convexity? If not, how does it hold for non-convex functions like $\sin x$?.
4. The writing of this paper sometimes is confusing to me that some terms coming up without definition. See my questions.
5. Could the authors provide a more detailed explanation of how Theorem 2.3 specifically relates to acceleration in the early stages, perhaps with an illustrative example or intuition, since it seems to it holds for all $n$?
6. The bounded averaged iterate assumption in Assumption 2.4 also seems to me very strong, the boundedness of the iterates should be the result of analysis, not a prior assumption. Is this assumption common in related works and how can one relax this assumption possibly?
7. The framework is proposed to subsume three special cases, so I would suggest that the authors include experiments for the other two cases or explain why chose to focus on only one case in the experiments. This would help readers better understand the generality and applicability of the proposed framework.

References

1. Li, X., Yang, W., Wang, S., & Zhang, Z. (2019). Communication efficient decentralized training with multiple local updates. stat, 1050, 21.
2. Ge, S., & Chang, T. H. (2023, December). Gradient Tracking with Multiple Local SGD for Decentralized Non-Convex Learning. In 2023 62nd IEEE Conference on Decision and Control (CDC) (pp. 133-138). IEEE.
3. Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S., Stich, S., & Suresh, A. T. (2020, November). Scaffold: Stochastic controlled averaging for federated learning. In International conference on machine learning (pp. 5132-5143). PMLR.
4. Beck, A. (2017). First-order methods in optimization. Society for Industrial and Applied Mathematics.