- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes Local MixVR, a distributed optimization method that combines local double-momentum, minibatch averaging, and drift correction. The authors derive a convergence bound showing that the communication complexity can be independent of the total sample size under the stated assumptions. Experiments on Fashion-MNIST and CIFAR-10 show improvements over several SGD baselines.
Critical strengths
- The O(M) communication bound is an interesting result for smooth convex optimization. In the stated regime, the number of rounds need not grow with the sample budget.
- The analysis gives a useful explanation for this result by separating noise from recent local updates from noise already averaged across workers.
Critical weaknesses
- The claim of being the first method with sample-independent communication needs to be stated more precisely. The differences in assumptions from prior work should be made clearer.
- The experiments use different hyperparameters from Theorem 2.2 without explaining the choice. Appendix G.3 also appears to use test accuracy for tuning, which raises concerns about the reported comparison.
Questions for authors
- How does the claimed O(M) communication bound relate to earlier work, such as “Distributed Stochastic Optimization via Adaptive SGD” and “Communication-efficient SGD: From Local SGD to One-Shot Averaging”, given their different assumptions?
- Appendix G.3 mentions selecting configurations based on test accuracy. Was the test set used for hyperparameter tuning?
- Why are the momentum parameters and mixing ratio in the experiments different from those in Theorem 2.2?
We thank the reviewer for the thoughtful review and valuable feedback. We appreciate the positive assessment of our sample-independent communication guarantee and are glad to read that the noise decomposition helped explain how these communication savings are achieved.
Thank you for helping us clarify both the contribution and its assumptions. Our contribution is a communication threshold of O(M), independent of the sample budget N, while retaining the optimal N−1/2 statistical scaling for fixed problem parameters. This guarantee holds for general smooth convex objectives with smooth stochastic functions. To the best of our knowledge, this is the first such guarantee that does not require bounded stochastic gradients or strong convexity. In the relevant regime, Woodworth et al. [1] establish the optimality of Minibatch ASGD under general smooth convex functions, where they note that their lower-bound oracle cannot be represented as the gradient of a random smooth function and ask whether this natural statistical-learning structure can enable better guarantees. Our result makes concrete progress in this direction: exploiting sample-level smoothness reduces the communication threshold from order N1/4 for Minibatch ASGD to order M, giving an improvement when M<N1/4 and removing dependence on the sample budget N. Following the reviewer's suggestion, we have now updated Table 1 in the revised manuscript accompanying this rebuttal to state the assumptions required by each compared method. For the two cited examples:
"Distributed Stochastic Optimization via Adaptive SGD" considers smooth convex stochastic functions, but its communication guarantee crucially relies on the assumption of bounded stochastic gradients. This restriction does not follow from smoothness; for example, a smooth convex quadratic can have arbitrarily large gradients on an unbounded domain. Our guarantee accommodates this possibility by requiring bounded variance without imposing a uniform bound on gradient magnitudes.
"Communication-efficient SGD: From Local SGD to One-Shot Averaging" obtains O(M) communication under strong convexity, suppressing condition-number dependence. Our result establishes this communication scaling for general smooth convex objectives, extending its applicability beyond the strongly convex setting.
We have also revised the Related Work discussion to explain these distinctions and make the scope of our novelty claim explicit.
We thank the reviewer for raising these points.
Regarding the hyperparameter choices. We thank the reviewer for highlighting this point. Our choices follow common practice in optimization, where convex theory guides algorithm design and practical parameters are adapted to nonconvex training. For example, Adam's convex analysis [3] uses decreasing parameter schedules at t, while its neural-network experiments use a constant base learning rate and fixed momentum. We similarly follow the fixed-parameter implementation of μ2-SGD in [2, Appendix H.3], and the common momentum choice of 0.9 for the momentum baselines.
Regarding hyperparameter selection. The original sweeps followed the selection criterion reported in Appendix G.3 and used coarse grids, with the same learning-rate grid across all methods. These sweeps were designed to identify effective hyperparameter regions for comparisons across communication budgets. We agree that validation-based selection is the appropriate protocol. In response to the reviewer's comment, we repeated hyperparameter selection using cross-validation on the training set, over the same grids. For every method and communication budget, cross-validation recovered exactly the originally selected configuration, leaving our reported test results unchanged. This agreement supports the stability of our parameter choices under validation-based selection within the grids considered. We have updated Appendix G.3 to include the cross-validation procedure.
[1] Blake Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro. The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication. COLT, 2021.
[2] Tehila Dahan and Kfir Y. Levy. Do Stochastic, Feel Noiseless: Stable Stochastic Optimization via a Double Momentum. ICLR, 2025.
[3] Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the Convergence of Adam and Beyond. ICLR, 2018.