acceptodds
Withdrawn from ICLR 2027

Distributed Variance Reduction with Compressed Communication

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Sign-based methods can reduce communication costs in distributed environments, but aggregating local signs can introduce bias when data are heterogeneous. As a result, existing sign-based variance reduction algorithms fail to obtain the optimal convergence rates. In this paper, we solve this problem and obtain optimal rates for both stochastic and finite-sum optimization. We first give a counterexample showing that majority voting can fail to approach stationary points even with exact local gradients. Motivated by this limitation, we propose tracking the global gradient at the server through unbiased compression of recursive gradient increments. The proposed methods obtain the convergence rates of for the -norm and for the -norm. Here, is the iteration number, is the number of workers, is the dimension, and , with denoting the relative variance of the compressor. For finite-sum problems with components, we combine periodic exact gradient refreshes with compressed component-gradient differences. The resulting total sample complexities are and for and expected gradient norms at most , matching the corresponding bounds in centralized settings.

Primary area:
learning theory
Keywords:
Sign-base optimizaiton, variance reduction, distributed optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_ozEKOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper investigates variance reduction with compressed communication for distributed nonconvex optimization. The authors identify a potential bias caused by majority voting over local gradient signs and introduce two algorithms, DVR-Sign and DVR-Q, that maintain a global gradient estimate through compressed gradient increments. The methods are further extended to finite-sum optimization with periodic gradient refreshes. The paper provides convergence analyses for both settings and evaluates the methods using LIBSVM datasets and ImageNet classification tasks.

Critical strengths
  1. The paper presents a counterexample demonstrating that majority voting over local gradient signs may lead to a nonzero gradient floor, even when the local gradients are exact. This observation provides a useful explanation of why conventional sign-based aggregation can be problematic in distributed optimization.

  2. The authors establish convergence guarantees for stochastic and finite-sum optimization and show improvements over the theoretical bounds of SSVR-MV. The experimental results also indicate some performance gains over the selected baselines.

Critical weaknesses
  1. The novelty of the proposed methods is not sufficiently established. Several important components of the proposed algorithms, including stochastic sign compression, recursive gradient estimation, and the communication of compressed gradient differences, have already been explored in previous studies. In particular, DIANA (Mishchenko et al., 2019) and MARINA (Gorbunov et al., 2021) employ closely related ideas for distributed optimization. The periodic full-gradient refreshes combined with compressed gradient differences in Algorithm 2 also resemble the mechanism used in MARINA. However, the paper provides little discussion of these closely related approaches. The Related Work section mainly summarizes previous results without clearly establishing how the proposed algorithms differ from existing methods. As a result, it is difficult to determine whether the contribution lies in a fundamentally new algorithmic design or primarily in extending the convergence analysis of existing techniques.

  2. The practical value of the theoretical results is not convincingly demonstrated. A substantial part of the paper is devoted to convergence analysis, but the connection between these theoretical improvements and practical communication efficiency remains unclear. The paper does not sufficiently examine how compression noise affects convergence or whether the improved theoretical rates lead to meaningful communication savings in practice.

  3. The experimental evaluation is also limited. Although data heterogeneity is a central motivation, the paper does not clearly describe the Non-IID data partitioning or investigate how different levels of heterogeneity influence performance. This is an important omission since sign-based gradient updates can be sensitive to disagreement among local gradients. Furthermore, the experiments do not include closely related compressed variance-reduction methods or provide direct validation of the finite-sum variants. Consequently, the current results are insufficient to establish the practical advantages of the proposed approach.

Questions for authors
  1. What distinguishes the proposed algorithms from existing compressed variance-reduction approaches, particularly DIANA and MARINA? Can the authors clarify the main algorithmic novelty and provide comparisons with these methods?

  2. How are the training datasets distributed among workers? Can the authors evaluate the methods under different Non-IID settings to demonstrate their robustness to data heterogeneity?

  3. How does compression variance affect the performance of the proposed methods, especially for high-dimensional models? Can the authors provide a more comprehensive evaluation of communication efficiency, including the cost of periodic full-gradient refreshes and convergence to comparable accuracy levels?

Reviewer_utQ2OpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper develops distributed variance-reduced optimization methods with compressed uplink and downlink communication. It first identifies a failure mode of local-sign majority aggregation, then proposes compressing recursive gradient increments while maintaining a shared server-side estimator.

The analysis covers both online stochastic optimization and finite-sum optimization with periodic exact refreshes. Experiments compare the proposed methods with SSVR-MV, signSGD-MV, and Q-SGD on regularized logistic regression and ImageNet training.

Critical strengths
  1. The counterexample motivates a concrete algorithmic change.

Proposition 1 and Appendix A establish a persistent gradient floor for the considered majority-vote scheme, rather than merely a biased initial update. The proposed method responds by compressing variance-reduced increments and retaining a global estimator before choosing the update direction. This is a coherent connection between the identified failure mechanism and the method design.

  1. The analysis covers useful online and finite-sum settings.

The online results make the dependence on compressor variance and worker count explicit. The finite-sum extension uses exact refreshes and component-gradient differences to avoid the online bounded-gradient requirement, and the analysis counts component-gradient evaluations. The same-compressor Q-SGD control in the experiments also helps assess the value of variance reduction.

Critical weaknesses
  1. The convergence bounds do not by themselves resolve the tradeoff between compression and total communication.

For the scaled stochastic sign compressor in Eq. (8), (a=d), whereas the sufficient iteration bound for DVR-Q in Eq. (31) contains (a^{3/2}/(n\epsilon^3)). Thus, transmitting smaller messages can be accompanied by a worse sufficient iteration bound.

The analysis establishes convergence under compression, but it does not directly characterize when the same recursive estimator requires fewer total transmitted bits than its uncompressed (Q=I) version. A matched uncompressed ablation or a total-bit comparison incorporating packet size, compressor variance, and initialization would make the compression benefit clearer. This concerns the interpretation of the communication advantage, rather than the correctness of the stated convergence rate.

  1. The empirical comparison needs a more explicit common protocol.

Section 7 provides tuning grids, defines bidirectional payload, and includes SSVR-MV and a same-compressor Q-SGD control. However, it does not specify which SSVR-MV option was implemented and its quantization parameters, the worker data partition, minibatch sizes, or the experimental initialization batch (B_0).

The exact payload calculation should also explain how scale values and separately compressed initialization samples are counted. For ImageNet, the common training budget, number of runs, and meaning of the reported “±” values are unspecified. Consequently, Table 1’s final accuracies alone do not establish an accuracy-versus-communication advantage under a documented common budget. These details are important for interpreting and reproducing the empirical gains.

Questions for authors
  1. Which SSVR-MV option and quantization/projection parameters were used? Please also specify worker partitions, minibatch sizes, and the initialization batch.

  2. How are scale values and initialization messages counted in payload? What common training budget and uncertainty protocol were used for the ImageNet results?

  3. Can the authors compare against the same recursive estimator with (Q=I), or provide an explicit total-bit analysis, to isolate the benefit of compression?

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

The paper studies distributed optimization where workers send compressed messages to a server. It first shows that majority voting can fail to converge to a stationary point even when each worker computes exact gradients. It then proposes methods where the server keeps an estimate of the average gradient, updates it using compressed messages from workers, and sends either its signs or a compressed version back to them. The paper gives convergence bounds for stochastic and finite-sum problems and tests the methods on classification tasks and ImageNet.

Critical strengths
  1. The counterexample is useful. It shows that majority voting can fail to converge to a stationary point even when every worker computes exact gradients. This makes clear that the problem comes from how the workers’ gradients are combined.

  2. The proposed method is simple. It compresses messages in both directions and keeps the gradient estimate at the server, without requiring additional gradient estimates at the workers.

Critical weaknesses
  1. It is unclear what the method improves over the closest existing methods. The paper mainly compares its theory with sign-based methods, but several methods for more general compression are directly relevant.

    VR-MARINA (Gorbunov et al., 2021) already sends compressed gradient differences and occasionally recomputes the full gradient. The finite-sum method in this paper is particularly close to it. DASHA (Tyurin and Richtárik, 2023) and EF21-STORM (Fatkhullin et al., 2023) already combine compression with STORM-type variance reduction. Their original versions send full vectors from the server to the workers, so DVR’s compressed broadcast is a relevant difference.

    However, ErrorCompensatedX (Tang et al., 2021) already combines STORM with compression in both directions, although under different assumptions. Compressed Gluon (Qian et al., 2026) can also be specialized to sign updates, but occasionally sends uncompressed gradient estimates.

    The paper needs to explain what DVR gains over these methods in communication, gradient computations, or memory. The paper's stochastic analysis assumes E∥gj(x;ξ)∥22≤H2\mathbb{E}\|g_j(x;\xi)\|_2^2\le H^2. This bounds both the gradient noise and the gradients themselves, whereas DASHA and EF21-STORM do not require the latter bound. DVR’s simpler implementation and avoidance of full-gradient refreshes in the stochastic setting may be useful, but the paper does not establish how much these differences matter.

  2. The experiments do not establish an advantage over the relevant alternatives. They only compare with signSGD-MV, Q-SGD, and SSVR-MV. A comparison with existing compressed variance-reduction methods and an uncompressed variance-reduced baseline is needed. It should account for both gradient computations and communication, since each ordinary DVR step evaluates gradients at two models.

    The ImageNet results also lack basic details: batch size, number of epochs, training schedule, how data are split between workers, number of runs, and what the reported “±” means.There are also no experiments for the finite-sum methods or tests of how performance changes with the number of workers.

Questions for authors

NA

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

Related papers

Discussion (0)

Sign in to comment.