acceptodds
Under review as a conference paper at ICLR 2027

Local MixVR: Breaking the Communication-Sample Dependence in Distributed Learning

Abstract

Communication overhead is a crucial bottleneck in scalable distributed learning. While existing methods aim to efficiently utilize data points, such as Local SGD, Minibatch SGD, and their accelerated variants, they still exhibit communication-round complexity that scales with the total number of samples . In this paper, we introduce Local MixVR, a distributed framework that integrates local updates with variance-reduction techniques to mitigate local noise. We show that Local MixVR is the first distributed method to eliminate the dependence of communication complexity on , achieving a complexity that scales only with the number of workers . In common regimes where , Local-MixVR outperforms the state-of-the-art Minibatch Accelerated SGD baseline, bridging a long-standing gap in distributed optimization and establishing a new paradigm for communication-efficient training.

Primary area:
optimization
Keywords:
distributed learning, stochastic optimization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_7Mi1OpenReview ↗
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
  1. 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.
  2. The analysis gives a useful explanation for this result by separating noise from recent local updates from noise already averaged across workers.
Critical weaknesses
  1. 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.
  2. 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
  1. 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?
  2. Appendix G.3 mentions selecting configurations based on test accuracy. Was the test set used for hyperparameter tuning?
  3. Why are the momentum parameters and mixing ratio in the experiments different from those in Theorem 2.2?
1 comment

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.

  1. Regarding the novelty claim and comparison with prior work.

Thank you for helping us clarify both the contribution and its assumptions. Our contribution is a communication threshold of O(M)O(M), independent of the sample budget NN, while retaining the optimal N−1/2N^{-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/4N^{1/4} for Minibatch ASGD to order MM, giving an improvement when M<N1/4M<N^{1/4} and removing dependence on the sample budget NN. 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)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.

  1. Regarding the hyperparameters.

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 tt, while its neural-network experiments use a constant base learning rate and fixed momentum. We similarly follow the fixed-parameter implementation of μ2\mu^2-SGD in [2, Appendix H.3], and the common momentum choice of 0.90.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.

Reviewer_dY18OpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Local MixVR, a distributed method for stochastic convex optimization with intermittent communication. It combines three components: local μ2\mu^2-SGD (anytime averaging + STORM), a minibatch accumulation phase at the end of each round (a fraction α\alpha of the per-round budget KK), and a drift-correction step that re-centers each worker's STORM estimator at the synchronized point before averaging. Under the random smooth-function model (each f(⋅;z)f(\cdot; z) is LL-smooth), the authors prove

E[f(xˉT)]−f(x⋆)≤O(LD2KR+σ~DKR+σ~DMKR).\mathbb{E}[f(\bar{x}_T)] - f(x^\star) \le O\left(\frac{LD^2}{KR} + \frac{\tilde{\sigma} D}{\sqrt{K}R} + \frac{\tilde{\sigma} D}{\sqrt{MKR}}\right).

This implies that the minimum number of rounds needed to reach the statistical rate is Rmin⁡=Ω(M)R_{\min} = \Omega(M), independent of the sample size NN. This improves on Minibatch ASGD (Rmin⁡=Ω(N1/4)R_{\min} = \Omega(N^{1/4})) when M≲N1/4M \lesssim N^{1/4}. The key technical step is an error decomposition: noise from rounds before the last synchronization is averaged over the MM workers, and only the O(Kloc)O(K_{\mathrm{loc}}) steps of the current round stay un-averaged. Experiments on Fashion-MNIST (LeNet) and CIFAR-10 (ResNet-18) show that Local MixVR outperforms Local SGD and Local Momentum across communication budgets.

Critical strengths
  1. Clean and interesting theoretical result. A communication complexity that depends only on MM and not on NN is a strong statement. It gives a concrete (if partial) answer to the open question raised by Woodworth et al. (2021) about whether the random smooth-function structure can be exploited to beat Minibatch ASGD.

  2. Insightful error decomposition. Lemma E.1 / Lemma 2.1 separate the stochastic error into a globally-averaged part (from rounds before the last synchronization) and a bounded local part (from the current round). With βt=1/t\beta_t = 1/t, the local part stays O(Klocσ~2)O(K_{\mathrm{loc}} \tilde{\sigma}^2) and does not grow with tt. Accumulating with Kavg∝KK_{\mathrm{avg}} \propto K brings the drift term Kloc2/KavgK_{\mathrm{loc}}^2 / K_{\mathrm{avg}} back down to O(K)O(K). This mechanism is simple and could be reused in other local methods. I checked the main proofs (Lemmas C.3, D.1–D.3, E.1, and Theorem 2.2) and did not find errors.

  3. Consistent empirical gains among local methods. Local MixVR beats Local SGD and Local Momentum at every tested RR, and the gap widens as MM increases.

Critical weaknesses
  1. The comparison with baselines is not proper, and the "optimal rate" claim needs qualification.

    • Different oracle and assumptions. Local MixVR queries the same sample zz at two points (in STORM and in the accumulation/drift correction). This two-point oracle is the real structural reason the Woodworth et al. lower bound does not apply, and it doubles the gradient computation. The baselines in Table 1, however, are analyzed under weaker assumptions with a single-point oracle.
    • Missing STORM-based baselines. Distributed methods that use the same two-point oracle (e.g., CE-LSGD of Patel et al. 2022, STEM, BVR-L-SGD) should be compared to support the "first to eliminate NN-dependence" claim.
    • The rate is not optimal in general. Since σ~=Θ(σ+σLD)\tilde{\sigma} = \Theta(\sigma + \sigma_L D) with σL\sigma_L up to LL, the statistical term is (σ+σLD)D/N(\sigma + \sigma_L D) D / \sqrt{N}. This is worse than the minimax σD/N\sigma D / \sqrt{N} whenever σLD≫σ\sigma_L D \gg \sigma, and in that case Rmin⁡R_{\min} becomes Ω(M(σ~/σ)2)\Omega\big(M (\tilde{\sigma}/\sigma)^2\big) rather than Ω(M)\Omega(M). Table 1 hides this by setting σ=O(1)\sigma = O(1).
  2. Missing comparison with Federated Accelerated SGD (FedAc, Yuan & Ma 2020). FedAc is cited in the related work but is absent from both Table 1 and the experiments. This is a notable omission for two reasons:

    • It is the most direct prior work on the paper's central question. FedAc is an accelerated local-update method designed to reduce communication rounds in exactly this homogeneous convex setting, so it targets the same question the paper claims to address: whether local methods can beat Minibatch ASGD.
    • It already beats Minibatch ASGD under additional structure. Under extra regularity (e.g., third-order smoothness), FedAc is known to improve on Minibatch ASGD. Local MixVR likewise relies on an assumption stronger than the Woodworth et al. setting.

    The paper should position its assumption (random smooth functions with a two-point oracle) relative to FedAc's, compare the resulting Rmin⁡R_{\min}, and include FedAc as an experimental baseline.

  3. The experiments do not test the analyzed algorithm or the main claim.

    • Parameter mismatch. The theory uses βt=1/t\beta_t = 1/t, γt=2/(t+2)\gamma_t = 2/(t+2), ηt=tη\eta_t = t\eta, and α=1/2\alpha = 1/2. The experiments use constant β=0.1\beta = 0.1, constant γ=0.9\gamma = 0.9 (essentially no anytime averaging), and α∈{0.01,0.05,0.1}\alpha \in \{0.01, 0.05, 0.1\}. In the experimental regime Kloc2/Kavg≫KK_{\mathrm{loc}}^2 / K_{\mathrm{avg}} \gg K, which is exactly where the drift control in Eq. (11) breaks.
    • The main claim is not tested. NN is never varied, so the claim that Rmin⁡R_{\min} is independent of NN goes unchecked.
    • Minibatch baselines look under-tuned. For example, Minibatch ASGD reaches only about 73% on CIFAR-10 at R=750R = 750 with a pretrained ResNet-18. The learning-rate grid is capped at 0.30.3 with no warmup, and Local MixVR alone gets an extra α\alpha sweep.
    • Understated communication cost. Each round needs two sequentially dependent all-reduces (parameters, then estimators). That is twice the communication volume and twice the synchronization barriers of Local SGD, but the experiments only report round counts.
Questions for authors
  1. The comparison with baselines is not apples-to-apples, and the "optimal rate" claim needs qualification.

    • Different oracle and assumptions. Local MixVR queries the same sample zz at two points (in STORM and in the accumulation/drift correction). This two-point oracle is the real structural reason the Woodworth et al. lower bound does not apply, and it doubles the gradient computation. The baselines in Table 1, however, are analyzed under weaker assumptions with a single-point oracle.
    • Missing baselines. STORM-based distributed methods that use the same oracle (e.g., CE-LSGD of Patel et al. 2022, STEM, BVR-L-SGD) should be compared to support the "first to eliminate NN-dependence" claim.
    • The rate is not optimal in general. Since σ~=Θ(σ+σLD)\tilde{\sigma} = \Theta(\sigma + \sigma_L D) with σL\sigma_L up to LL, the statistical term is (σ+σLD)D/N(\sigma + \sigma_L D) D / \sqrt{N}. This is worse than the minimax σD/N\sigma D / \sqrt{N} whenever σLD≫σ\sigma_L D \gg \sigma, and in that case Rmin⁡R_{\min} becomes Ω(M(σ~/σ)2)\Omega\big(M (\tilde{\sigma}/\sigma)^2\big) rather than Ω(M)\Omega(M). Table 1 hides this by setting σ=O(1)\sigma = O(1).
  2. The experiments do not test the analyzed algorithm or the main claim.

    • Parameter mismatch. The theory uses βt=1/t\beta_t = 1/t, γt=2/(t+2)\gamma_t = 2/(t+2), ηt=tη\eta_t = t\eta, and α=1/2\alpha = 1/2. The experiments use constant β=0.1\beta = 0.1, constant γ=0.9\gamma = 0.9 (essentially no anytime averaging), and α∈{0.01,0.05,0.1}\alpha \in \{0.01, 0.05, 0.1\}. In the experimental regime Kloc2/Kavg≫KK_{\mathrm{loc}}^2 / K_{\mathrm{avg}} \gg K, which is exactly where the drift control in Eq. (11) breaks.
    • The main claim is not tested. NN is never varied, so the claim that Rmin⁡R_{\min} is independent of NN goes unchecked.
    • Minibatch baselines look under-tuned. For example, Minibatch ASGD reaches only about 73% on CIFAR-10 at R=750R = 750 with a pretrained ResNet-18. The learning-rate grid is capped at 0.30.3 with no warmup, and Local MixVR alone gets an extra α\alpha sweep.
  3. Per-round communication cost is understated. Each round needs two sequentially dependent all-reduces: first the parameters, then the corrected estimators, with gradient computation at xˉt\bar{x}_t in between. That is twice the communication volume and twice the synchronization barriers of Local SGD, which matters in exactly the latency-bound settings the paper uses as motivation (e.g., DiLoCo).

4 comments

Thank you for your valuable feedback. We appreciate your recognition of the strength of our communication guarantee, which depends only on MM, and its contribution toward answering the question raised by Woodworth et al. (2021). We are also glad you see potential for our error decomposition to inform the design of future local methods. We have carefully considered your concerns and address them below.

  1. The comparison with baselines.
  • Regarding the oracle and assumptions. Thank you for raising this point and helping us clarify the comparison. Indeed, Local MixVR evaluates the same sample at two points. As in other STORM-based algorithms, these paired evaluations allow us to exploit sample-level smoothness, a natural assumption in statistical learning. Our contribution is to show how this structure translates into a provable communication advantage. Woodworth et al. [1] asked whether additional statistical-learning structure can enable better guarantees, noting that their lower-bound oracle cannot be represented as the gradient of a random smooth function. Our result gives an affirmative answer in the two-point setting: we reduce the communication threshold for retaining the optimal statistical rate from order N1/4N^{1/4} for Minibatch ASGD to order MM. This improves the guarantee when M<N1/4M<N^{1/4} and makes the required communication independent of the sample budget, while the constant-factor increase in gradient computation does not change this asymptotic communication advantage. Following the reviewer's suggestion, we have updated Table 1 to state each method's assumptions explicitly.

  • Regarding comparisons with two-point-oracle methods. Thank you for pointing us to CE-LSGD [1], STEM [2], and BVR-L-SGD [3]. We agree that these are relevant works and have expanded our related-work discussion accordingly. They provide guarantees for nonconvex stationarity, and their guarantees yield communication thresholds of R≳MN1/3R\gtrsim MN^{1/3} for CE-LSGD and BVR-L-SGD, and R≳N2/3R\gtrsim N^{2/3} for STEM, to retain the N−2/3N^{-2/3} stationarity rate. Our contribution is therefore to provide the first guarantee retaining the optimal convex statistical rate with O(M)O(M) communication rounds, independent of the sample budget.

  • Regarding optimality and noise dependence. Our focus is on improving dependence on training iterations and communication rounds, as shown by our final rate and communication complexity. For fixed problem parameters, our guarantee retains the optimal N−1/2N^{-1/2} statistical scaling while making the communication threshold independent of NN. In addition, the same effective-noise dependence, σ~=Θ(σ+σLD)\tilde{\sigma}=\Theta(\sigma+\sigma_LD), already similarly appears in the centralized μ2\mu^2-SGD guarantee [2, Theorem 4.2], where there is no worker drift. Our distributed analysis preserves this dependence while allowing infrequent communication.

  1. Comparison with Federated Accelerated SGD (FedAc, Yuan & Ma, 2020). Thank you for highlighting this important and closely related work. We have added FedAc's guarantees and assumptions to Table 1 in the revised manuscript. Indeed, FedAc exploits third-order smoothness and bounded fourth moments to obtain improved guarantees. For the general convex setting considered here, Table 1 and Theorem E.3 give the following sufficient communication threshold for attaining the optimal statistical rate: R=O(max⁡{N1/4,M1/3N1/6}),R=O(\max\{N^{1/4},M^{1/3}N^{1/6}\}), where N=MTN=MT and TT is the number of gradient evaluations per worker. This bound retains an N1/4N^{1/4} term, so it does not establish a smaller communication threshold than Minibatch ASGD in this setting. Our experiments focused on standard SGD and momentum baselines for nonconvex neural-network training. We agree that a direct empirical comparison with FedAc would be interesting and will make an effort to include it in the final version.
  1. The experiments.
  • Regarding the parameter mismatch. 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 tt, while its neural-network experiments use a constant base learning rate and fixed momentum. We similarly follow the fixed-parameter implementation of μ2\mu^2-SGD in [2, Appendix H.3], and the common momentum choice of 0.90.9 for the momentum baselines.

  • Regarding the empirical validation of the main claim. We thank the reviewer for raising this point. The sample-independent communication guarantee is established by Theorem 2.2, while our experiments evaluate its practical motivation: achieving better performance with less communication. At matched sample budgets, our results show higher accuracy for the same communication budget.

  • Regarding baseline tuning. Thank you for raising this concern. In our original CIFAR-10 sweep, the best learning rate for Minibatch ASGD was 0.01 at R=750R=750, below the upper limit of 0.3. Nevertheless, to address the concern, we expanded the grid to include 0.003, and 0.006. This identified a better learning-rate choice of 0.006 for Minibatch ASGD at R=750R=750, while the selected learning rates for the other methods remained unchanged. We appreciate the reviewer's comment, which helped us improve the baseline tuning and empirical comparison. All methods used the same learning-rate grid without warmup, providing a controlled comparison under a shared training protocol. Local MixVR's additional α\alpha sweep tunes its method-specific mixing ratio, as documented in Appendix G.3.

  • Regarding the Per-round communication cost. We thank the reviewer for this helpful comment. We agree that equal sample budgets do not imply equal communication costs, and we appreciate the suggestion to make this comparison more explicit. Our method indeed synchronizes three parameter-sized vectors per round. We have therefore updated the plots to compare accuracy against total communication volume, measured as parameter-sized vectors per round × communication rounds (see the updated figures in the revised rebuttal). Our method continues to achieve higher accuracy at the same communication budget, showing that its advantage persists after accounting for the additional communication volume.


[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.

Thank you for the detailed response and for updating Table 1 with explicit assumptions and FedAc. The discussion of CE-LSGD/STEM/BVR-L-SGD and FedAc addresses my concerns on those points. A few issues remain:

  1. Scope of the answer to Woodworth et al. Their open question concerns whether random smooth-function structure can be exploited under a standard (single-point) stochastic gradient oracle. The result here holds under a strictly stronger two-point oracle, so I suggest stating the claim explicitly as "under a two-point oracle" in the abstract, introduction, and conclusion. Relatedly, under the same two-point oracle in the convex setting, what Rmin⁡R_{\min} do simpler variance-reduced baselines (e.g., minibatch μ2\mu^2-SGD, possibly accelerated) achieve? This would clarify how much of the improvement comes from local updates rather than from the stronger oracle.

  2. Noise dependence. I agree that the σ~=Θ(σ+σLD)\tilde{\sigma} = \Theta(\sigma + \sigma_L D) dependence is inherited from centralized μ2\mu^2-SGD. My point is about the claims: when σLD≫σ\sigma_L D \gg \sigma, the statistical term is not σD/N\sigma D/\sqrt{N}, and the threshold becomes Rmin⁡=Ω(M(σ~/σ)2)R_{\min} = \Omega\big(M(\tilde{\sigma}/\sigma)^2\big). Please qualify "optimal statistical rate" accordingly and make σ~\tilde{\sigma} explicit in Table 1 rather than setting σ=O(1)\sigma = O(1).

We thank the reviewer for the helpful comments, which have helped strengthen the presentation of our work.

1. a. Oracle model. Local MixVR exploits sample-level smoothness by evaluating two gradients on the same sample, following well-known stochastic optimization approaches such as STORM [1], SVRG [2], and SPIDER [3]. These paired evaluations yield gradient differences whose variance decreases as the query points become closer, allowing us to control stochastic error during local updates and to properly exploit the sample-level smoothness structure. Arjevani et al. [4] also observe that all methods known at the time to achieve the optimal non-convex complexity under sample-level smoothness use shared-sample queries, while achieving this rate with a single-point oracle is left as an open question in their work. Although their discussion concerns nonconvex optimization, it highlights the established role of shared-sample queries in exploiting this smoothness structure, as Local MixVR does. We have expanded the related work to clarify this motivation and its role (see page 3, lines 160-176).

1. b. Minibatch baselines. For N=MKRN=MKR total samples, minibatching the guarantees in Theorems 4.2 and 5.2 of Dahan and Levy [5] yields:

Minibatch μ2\mu^2-SGD:

\leq O\left(\frac{LD^2}{R}+\frac{\widetilde{\sigma}D}{\sqrt{MKR}}\right).$$ Minibatch $\mu^2$-ExtraSGD: $$\mathbb{E}[f(x_{\mathrm{out}})-f^*] \leq O\left(\frac{LD^2}{R^2}+\frac{\widetilde{\sigma}D}{\sqrt{MKR}}\right).$$ Balancing the optimization and statistical terms gives communication thresholds $R\gtrsim N^{1/2}$ and $R\gtrsim N^{1/4}$, respectively, with problem parameters suppressed. Thus, their dependence on sample budget and communication rounds matches minibatch SGD and minibatch ASGD. Therefore, Local MixVR achieves a communication improvement beyond straightforward minibatching of these methods in common regimes when $M\lesssim N^{1/4}$. Following the reviewer's suggestion, we have added a note to Table 1 to make this comparison explicit. **2.** Thank you for raising this great point. **Local MixVR reaches its statistical term after $R_{\min}=\Theta(M)$ communication rounds, with no additional dependence on noise or smoothness parameters in this threshold.** To see this, substituting $N=MKR$ into our bound gives $$\Delta_T\lesssim \frac{LD^2M}{N} +\frac{\tilde{\sigma}D}{\sqrt N} \left(1+\sqrt{\frac{M}{R}}\right).$$ The communication-dependent contribution is at most the statistical term precisely when $$\frac{\tilde{\sigma}D}{\sqrt N}\sqrt{\frac{M}{R}} \leq \frac{\tilde{\sigma}D}{\sqrt N} \quad\Longleftrightarrow\quad R\geq M.$$ Thus, $\tilde{\sigma}$ cancels from the balancing condition. For comparison, under third-order smoothness with constant $Q$ the communication threshold for FedAc [6] gives, $$R_{\mathrm{drift}}^{\mathrm{FedAc-II}} \asymp \max\left\\{ \left(\frac{LD}{\sigma}\right)^{1/2}N^{1/4}, \quad \left(\frac{QD^2}{\sigma}\right)^{1/3}M^{1/3}N^{1/6} \right\\}.$$ Thus, even under third-order smoothness, the threshold obtained from FedAc's bound depends on the sample budget and problem parameters. Local MixVR's communication instead scales only with the number of workers $M$, with no additional dependence on the total sample budget, noise, or smoothness parameters. We have now highlighted this additional advantage in the introduction of the revised paper (see page 3, lines 139-142). --- [1] A. Cutkosky and F. Orabona. Momentum-Based Variance Reduction in Non-Convex SGD. NeurIPS, 2019. [2] R. Johnson and T. Zhang. Accelerating Stochastic Gradient Descent using Predictive Variance Reduction. NeurIPS, 2013. [3] C. Fang, C. J. Li, Z. Lin, and T. Zhang. SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path-Integrated Differential Estimator. NeurIPS, 2018. [4] Y. Arjevani, Y. Carmon, J. C. Duchi, D. J. Foster, N. Srebro, and B. Woodworth. Lower Bounds for Non-Convex Stochastic Optimization. Mathematical Programming, 2023. [5] T. Dahan and K. Y. Levy. Do Stochastic, Feel Noiseless: Stable Stochastic Optimization via a Double Momentum Mechanism. ICLR, 2025. [6] Honglin Yuan and Tengyu Ma. Federated Accelerated Stochastic Gradient Descent. NeurIPS, 2020.
Reviewer_L5B3OpenReview ↗
Rating
3(+1)
Confidence
1
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Local MixVR, combining local double momentum, minibatch accumulation, and drift correction for distributed stochastic optimization. Under homogeneous smooth convex assumptions, it derives a sample-independent communication threshold in the stated worker regime and reports gains on Fashion-MNIST and CIFAR-10.

Critical strengths
  • I like the theoretical objective of reducing communication while retaining the statistical convergence rate. Theorem 2.2 gives a meaningful improvement over the stated Minibatch ASGD bound when the number of workers is sufficiently small.

  • The three variance-reduction components have clear roles, and Lemma 2.1 separates local noise from noise shared across workers. This makes the communication benefit easier to understand beyond the final convergence bound.

Critical weaknesses
  • Equal sample budgets do not imply equal computation or communication cost here: Algorithms 1–3 use paired gradient evaluations and separate parameter and estimator reductions. Accuracy versus rounds therefore does not establish the practical training-time advantage.

  • Appendix G.3 selects each configuration by its highest mean test accuracy and gives Local MixVR an additional mixing-ratio sweep. This can bias the reported comparison; hyperparameters should be selected on validation data before reporting test results.

Questions for authors
  1. Do the gains remain with validation-selected hyperparameters and comparable tuning budgets?
  2. What are the total gradient evaluations, communicated bytes, and wall-clock costs at matched accuracy?
1 comment

Thank you for your constructive feedback and for recognizing the significance of our theoretical result. The question of whether local computation can outperform accelerated minibatching motivated our work, and we are glad that you found this contribution valuable. Our result answers this question while preserving the optimal statistical rate with only O(M)O(M) communication rounds, independent of the sample size.

Regarding the training-time advantage.

We thank the reviewer for this helpful comment. We agree that equal sample budgets do not imply equal communication costs, and we appreciate the suggestion to make this comparison more explicit. Our method indeed synchronizes three parameter-sized vectors per round. We have therefore updated the plots to compare accuracy against total communication volume, measured as parameter-sized vectors per round × communication rounds (please see the updated figures in the rebuttal revised version). Our method continues to achieve higher accuracy at the same communication budget, showing that its advantage persists after accounting for the additional communication volume.

We also agree that the paired gradient evaluations increase local computation. Nevertheless, our paper targets settings where communication overhead is the dominant training cost. In this regime, the additional gradient computation may contribute relatively little to the overall runtime, while reducing the synchronization rounds needed to reach a target accuracy can yield substantial time savings. Thus, two gradient evaluations per local step may still lead to faster overall training. Both our theoretical analysis and empirical results support the communication-efficiency advantage underlying this potential speedup.

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.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.