acceptodds
Under review as a conference paper at ICLR 2027

Distributed Optimization with Direction-Constrained Biased Compression

11 views

Abstract

Error feedback (EF) is widely used to ensure convergence in distributed optimization with biased gradient compression. However, EF requires each node to maintain at least one additional model-sized numerical vector, introducing extra memory overhead. To reduce this memory overhead, we investigate an alternative approach that controls compression errors through directional constraints rather than numerical error accumulation. Our descent analysis identifies a sufficient condition for convergence based on the alignment between the global gradient and the aggregated compression error. Specifically, we introduce ACTION (Acute-Angle CondiTION), which requires their inner product to be non-negative. Since individual nodes cannot access the current global gradient before communication, we further propose L-ACTION (Lagged ACTION), which uses the previous aggregated compressed gradient as a reference. By enforcing the directional constraints coordinatewise, L-ACTION requires retaining only the signs of this reference as auxiliary state for compression error control, substantially reducing the memory footprint compared with the numerical error states maintained by EF. We establish convergence guarantees for ACTION under generalized biased compression without requiring compressor contractivity and show that L-ACTION achieves the same convergence rate. Mainstream compression methods can be modified to satisfy the directional constraints with minor adjustments. Experiments demonstrate lower training loss, higher test accuracy, and improved communication efficiency in several settings.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Distributed Optimization, Biased Gradient, Communication-Efficient

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_Aiw9OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2(+1)
Read review
Paper summary

This paper investigates distributed nonconvex optimization under biased gradient compression, with the aim of reducing the auxiliary memory required by error-feedback (EF) methods. The proposed ACTION condition requires a nonnegative inner product between the global gradient and the aggregated compression error. Its implementable variant, L-ACTION, uses the signs of the previous aggregated compressed gradient as the reference for direction-constrained quantization and sparsification. The revision changes the claimed L-ACTION guarantee to a convergence bound with a residual term, removes the zero-reference full-precision override from Algorithm 3, and adds analyses of compression-error ratios, memory usage, and stochastic training. The central question is whether the practical L-ACTION method offers a reliable memory-communication-accuracy advantage, rather than only promising behavior under idealized ACTION.

Critical strengths

Strength 1

A substantive correction of the main theoretical and implementation issues. The revised paper no longer defends the problematic learning-rate argument from the first submission, and it explicitly qualifies the L-ACTION convergence statement with a residual. Removing the full-precision override also addresses the central communication-budget inconsistency in the original Algorithm 3. These changes make the presentation more credible and justify recognizing an improvement in technical soundness.

Strength 2

A conceptually distinct compression rule with promising results in selected settings. Rather than accumulating numerical EF states, the paper controls compression errors through coordinatewise directional constraints, using only a lagged sign reference in L-ACTION. The 4-bit ResNet18/CIFAR100 result remains notable: Table 1 reports 132 rounds for LA-Q versus 856 for standard Q to reach 30% accuracy. The Appendix G comparison also makes the potential reduction in persistent auxiliary-state footprint explicit, although this is not yet a full system-level memory measurement.

Critical weaknesses

Assessment of the Authors' Responses

Response to Question 1

The authors acknowledge the gap in the original transition from Equation (43) to Equation (44) and replace the argument in Appendix D.2. The revised Theorem 2 now states a weaker result with a residual term under rω < 1. This substantively addresses my original algebraic objection; I would not repeat that objection against the revised proof. The remaining concern is whether the new condition provides a meaningful guarantee in the evaluated high-dimensional settings.

Response to Question 2

The full-precision override for zero-reference coordinates has been removed from Algorithm 3, and the direction-constrained sparsification procedure has been clarified. This is an important correction to the implementation description. However, the communication-efficiency claims still rely primarily on rounds to target accuracy rather than measured encoded bytes, including mask, indices, scales, reconstruction information, and downlink traffic.

Response to Question 3

Appendix F now records the sign-inconsistency energy ratio R_t, the observed compression-error ratio ω_t, and their product on actual training trajectories. These are useful diagnostics. Nevertheless, the observed ω_t is not the uniform constant ω required by Definition 1 and Theorem 2. Per-round products below one do not establish rω < 1; moreover, several 4-bit configurations exceed the observed threshold.

Response to Question 4

The added DGD baselines, auxiliary-state memory comparison, and three-seed stochastic-gradient experiments improve transparency. The reported stochastic results also reveal limitations: LA-Q deteriorates in later training, while LA-S can underperform S and EF21-S. The main larger-model evaluations remain full-batch, single-seed experiments with mildly heterogeneous data. Thus, the response improves the evidence but does not fully establish the claimed practical robustness.

Critical Weaknesses

Comment 1

The experiments do not yet establish a consistent advantage for the practical L-ACTION method. The strongest positive results are concentrated in selected low-bit, full-batch settings, while the idealized ACTION results use the current uncompressed global gradient and should not be treated as direct evidence for deployable L-ACTION. Appendix L.4, Figures 20-23, reports late-stage deterioration of LA-Q under stochastic gradients; LA-S also often trails S and EF21-S in those small-CNN tests. The sparsification results are similarly mixed: in Table 9, at the 30% target and k = 0.5M, LA-S requires 397 rounds, compared with 255 for EF21-S. These results make it difficult to conclude that the proposed direction constraint consistently improves practical training. Larger-model mini-batch experiments, multiple seeds, stronger non-IID partitions, and reporting of failure cases are needed to support such a conclusion.

Comment 2

The claimed communication and memory benefits are not yet demonstrated through matched end-to-end measurements. Removing the zero-reference override resolves one important defect, but the revised DC-S still transmits indices, a mask, values, and reconstruction information. The paper primarily reports the number of communication rounds rather than the cumulative encoded payload required to reach the same target accuracy. It also does not report wall-clock training time or measured peak memory. Figure 11 in Appendix G compares the sizes of persistent INT8 sign and FP32 EF states, which supports a narrower auxiliary-storage claim, but not necessarily a corresponding reduction in total training memory. Actual uplink and downlink bytes, measured persistent and peak memory, and time-to-accuracy under matched settings would be more conclusive.

Comment 3

The current ablations do not isolate the reason for the observed optimization improvement. Direction-constrained rounding changes not only the sign of the compression error but potentially the magnitude of the compressed update. Consequently, faster loss reduction at a fixed learning rate may partly reflect a different effective update scale rather than better directional information alone. This matters because the claimed contribution is a directional error-control mechanism. The authors should compare against well-tuned learning-rate baselines and norm-matched compressed updates, and report gradient alignment together with update-norm ratios. Such tests would distinguish the intended geometric mechanism from a step-size effect.

Comment 4

The incremental novelty over more closely related aggregate-feedback compression methods needs clearer positioning. Ortega et al., "Communication Compression for Distributed Learning without Control Variates" (arXiv:2412.04538, first posted December 2024), introduced CAFe, which uses previous global aggregate information to avoid client-specific EF control variates. CAFe compresses differences relative to a historical aggregate, whereas L-ACTION uses a historical sign reference to constrain compression errors; therefore, I do not regard the two mechanisms as identical. However, the motivation of avoiding numerical client-side EF state through past aggregate information overlaps. A direct explanation of what is new at the operator and theoretical levels, together with a fair matched-budget comparison where feasible, is needed to establish the incremental contribution.

Comment 5

The link between the revised theorem, the experiments, and the supplied implementation remains incomplete. Theorem 2 assumes rω < 1 and permits a nonvanishing residual proportional to 2rωζ²/(1-rω). Appendix F tracks the realized ω_t, which is not the uniform compressor bound ω; Appendix I gives dimension-dependent bounds that may be loose for large models. The supplementary code supplied with the manuscript also appears to predate the revision and uses quantization scaling and sign-state handling that do not clearly match the revised descriptions. These observations do not establish that the new experiments are incorrect, but they prevent the presented materials from fully verifying the practical scope of the theorem and the revised implementation. A version-aligned release and a tighter theory-to-experiment analysis would help resolve this concern.

Overall Assessment

I appreciate the substantial effort in the revision and consider the original algebraic gap and zero-reference override substantially addressed. These corrections improve the soundness of the paper. Nevertheless, the main claims concern the practical L-ACTION method, for which the evidence of a robust memory-communication-accuracy advantage over appropriate alternatives remains incomplete. The uneven stochastic and sparsification results, limited end-to-end cost measurements, and insufficient comparison with closely related aggregate-feedback work continue to affect my overall assessment. I therefore retain the overall recommendation while recognizing the improvement in technical rigor.

Questions for authors

Question 1

On the end-to-end communication and memory costs. Could the authors report cumulative actually encoded uplink and downlink bytes to reach matched target accuracies, including indices, masks, scales, and reconstructed values? Could they also report wall-clock time, persistent auxiliary memory, and peak training memory against Q/S, EF21, and uncompressed DGD under comparable settings?

Question 2

On the robustness of L-ACTION in realistic training. Could the authors repeat the mini-batch experiments with multiple seeds on at least one larger architecture and vary the non-IID partition strength? In particular, under which conditions does the late-stage instability of LA-Q disappear, and when does LA-S reliably outperform S and EF21-S?

Question 3

On the specific benefit of the directional constraint. Could the authors compare against learning-rate-tuned standard compression and norm-matched compressed updates, and report the gradient-alignment cosine and compressed-to-uncompressed update norm ratio? This would help determine whether the improvement is caused by the claimed alignment effect rather than an effective step-size change.

Question 4

On novelty relative to prior aggregate-feedback methods. How does L-ACTION differ in mechanism and required communication from CAFe (Ortega et al., arXiv:2412.04538) and its later development? Could the authors add a matched communication-budget and memory comparison, or explain clearly when such a comparison would not be appropriate?

Question 5

On the validity of the revised theorem and reproducibility. Can the authors distinguish the observed ω_t from the uniform ω required by Theorem 2 and quantify whether rω < 1 can be verified with a meaningful bound on the main high-dimensional tasks? Could they also provide code consistent with the revised quantizer, INT8 sign state, and new stochastic-gradient experiments?

5 comments

We thank the reviewer for the constructive feedback and for recognizing the potential of sign-based auxiliary state. We have corrected the analysis and algorithm, expanded the empirical evaluation, and revised our claims accordingly. We have uploaded the revised PDF, with all changes marked in blue.

AuthorsOpenReview ↗

W1 & Q1: Corrected convergence for L-ACTION

We have revised the proof to remove the positive learning rate lower bound. The corrected theorem includes a residual term, and we have revised the corresponding claims throughout the paper.

The original transition from Eqs. (43) to (44) requires a positive learning-rate lower bound when r>0r>0, as the reviewer identified. It therefore does not justify the claimed choice η=Θ(1/T)\eta=\Theta(1/\sqrt{T}). Simply adding the missing lower bound would not resolve this issue.

The revised proof uses a different Young-inequality parameter to bound the inner product between the previous global gradient and the current compression error. The new sufficient conditions are

0<\eta\le \frac{1-r\omega}{4+(8-2r)\omega}\cdot\frac{1}{L}$$ For fixed uniform bounds $r$ and $\omega$ satisfying $r\omega<1$, choosing $\eta=\Theta(1/\sqrt{T})$ subject to this upper bound yields $$\mathbb{E}\\|\nabla f(\hat x^T)\\|^2 \le\mathcal{O}(1/\sqrt{T}) +\frac{2r\omega}{1-r\omega}\zeta^2.$$ This is a weaker conclusion than the original claim: it bounds the expected squared gradient norm up to a residual, rather than establishing general convergence to stationarity. The residual vanishes when $r=0$, $\omega=0$, or $\zeta=0$. The revised definition of $r$ also includes zero-reference coordinates, as explained below. The complete proof is provided in Appendix D.2. The abstract, introduction, and theoretical discussion now distinguish this guarantee from that of ACTION.
AuthorsOpenReview ↗

W2 & Q2: Zero-reference coordinates and communication cost

We have removed the full-precision override from Algorithm 3 and revised the analysis to cover the implementation used in the experiments. Zero-reference coordinates no longer require an additional transmission mechanism.

The override in the original Algorithm 3 was not implemented. We initially assumed that zero coordinates in the aggregated compressed gradient would be negligible after initialization, but this assumption was incorrect under aggressive compression. This caused a discrepancy between the algorithm description and the implementation.

The implementation handles zero-reference coordinates as follows:

  • DC-Q: apply ordinary rounding.
  • DC-S: include the coordinate in the safe set and apply the normal selection rule.

Neither method triggers additional full-precision transmission solely because the reference is zero. To analyze these rules, we now define

St−=j:[gt]j[∇f(xt)]j<0 or [gt]j=0.S_t^-=\\{j:[g^t]_j[\nabla f(x^t)]_j<0\ \text{or}\ [g^t]_j=0\\}.

Accordingly, RtR_t measures the fraction of global gradient energy on sign-reversed or zero-reference coordinates, and rr uniformly bounds this fraction. The initial iteration with a zero reference is handled separately in the proof. These changes bring Algorithm 3 and Theorem 2 into agreement with the existing implementation without changing the reported experimental trajectories.

For communication, Q, EF21-Q, and LA-Q use the same quantization-code and scale formats at a given bit width. Consequently, the reported reductions in rounds for LA-Q relative to Q and EF21-Q translate into proportional reductions in cumulative encoded uplink payload.

For DC-S, we reduce the number of explicitly transmitted entries to offset the mask overhead. The adjusted number remains positive in all evaluated configurations, so the fallback is never invoked. The two FP32 reconstruction scalars, MM and mm, add 8 bytes per client when the mask is used, which is negligible at the evaluated communication budgets.

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

The paper proposes an interesting technique to address the memory overhead typically associated with existing compression methods, which require holding a model-sized vector in memory. Specifically, the paper proposes controlling the direction of compression errors rather than accumulating them, which requires storing only the signs of the previous aggregated compressed gradient instead of a full numerical vector. Furthermore, the paper identifies a directional condition on the compression error that is sufficient to establish convergence, using either the true gradient or the previous aggregated compressed gradient as a reference, and further derive a modification for two compressors that ensure this condition is satisfied. The paper formalizes this into their algorithm ACTION (and L-ACTION), analyzes it theoretically, derives its convergence bound, and validates it empirically.

Critical strengths

The paper proposes an interesting way to mitigate the memory overhead introduced by some existing compression methods. I think this is a very important contribution.

Additionally, I appreciate the theoretical analysis and how the method was tested in various empirical settings.

The paper is very well written, well motivated, and easy to follow and understand. It was a very enjoyable read.

Critical weaknesses

Major

  • In the derivation in D.2, the transition from Eq. (43) to Eq. (44) appears unjustified. For the coefficient of the accumulated squared gradient norms to be at least η/2\eta/2, the learning rate must satisfy a quadratic inequality. The resulting admissible interval has both a lower and an upper bound, whereas Theorem 2 imposes only the upper bound. In particular, the claimed choice η=Θ(1/T)\eta=\Theta(1/\sqrt{T}) eventually violates the missing lower bound for any fixed r>0. So I'm not sure the proof establishes the O(1/T)O(1/\sqrt{T}) convergence rate.

  • The paper assumes exact non-stochastic gradients. This limits its theoretical and practical impact. In typical training settings, stochastic/minibatch gradients are used, which the setting in the paper does not capture.

  • Theorem 1 requires learning rate less than 1/(1+ω)L1/(1+\omega)L which could be very small for large ω\omega especially when the dimension is large (in some quantization schemes, ω\omega can be O(d)O(d)). It could even be smaller than 1/T1/\sqrt{T} in finite-horizon training (typical training settings often converge in a reasonable number of optimization steps). I'm sure that there are settings that the method does capture, but I wonder how it deals with these other cases.

  • The directional constraint needs special compressors in order to be satisfied, and it does not work as a "plug-and-play" framework for existing compressors. While the authors acknowledge this in the paper and propose modifications for top-k and rounding quantization, it limits the applicability of the proposed method (w.g., when using other compressors like QSGD [1], Entropy-Constrained Uniform Quantization (ECUQ) [2], and others). I understand that a single paper does not need to solve every issue or cover every case, but maybe describing a general method to adapt existing compressors to your case (if this is possible) would strengthen the paper. Additionally, for top-k, it seems that when using aggressive compression, kk might not be large enough to compensate for the additional mask, potentially increasing the overall communication cost.

  • The paper is missing discussion and comparison to existing work (especially their theoretical guarantees). Even in the generalized compressor case, the work can still be compared to existing work on contractive compressors when ω<1\omega<1. This would make the paper richer, and it could also further highlight the generality of the method compared to existing ones.

  • The experiments are conducted in the full-batch (exact gradient) setting, which is reasonable since this is what your theory provides, but I wonder how it would perform in the minibatch (stochastic gradient) setting, since this is the more popular case. Again, in my opinion the method does not have to outperform every baseline in every setting, and even a small performance degradation could be reasonable given sufficient saves in memory overhead. Still, I think testing it in a more realistic empirical setting would be nice to see.

  • The experiments used only one random seed, which makes it difficult to assess the robustness of the results. I think using at least 3 random seeds and displaying the average results along with error bars/halo would strengthen the paper. Also, it is unclear how the hyperparameters were tuned, and if the same tuning procedure was used for all baselines. (This is not a critical issue for me, but it would be cleaner to address those issues in the final version of the paper).

  • I think adding an uncompressed baseline (full uncompressed gradient descent) to all experiments is crucial, as it would also make the degradation of compression clearer (and it would only strengthen your case).

  • Additionally, the communication cost of your method (especially when using sparsification) does not seem to be uniform over all steps. Therefore, it would be nice to also see graphs of the performance (test accuracy) as a function of the communication cost (in, e.g., communicated Gbits). I think this would also strengthen the paper.

  • A similar argument goes to the memory, I think it would be better to quantify the memory overhead of your method compared to baselines (and compared to uncompressed GD). Since this is what your method addresses, I think it would also make your advantage clearer empirically too, not just theoretically.

Minor

  • Eq. (37) appears to use an incorrect upper bound on the squared norm of the previous compressed gradient, a factor of 2 is missing on both squared norms. This would affect the coefficients in the following inequalities and should be corrected.

  • Additionally, the derivation in Appendix D.2 contains several apparent inconsistencies, including the sign in Eq. (24), the use of Rt−1R_{t-1} in Eq. (28), and an exact-transmission requirement for zero-reference coordinates that is present in Algorithm 3 but absent from the assumptions of Theorem 2.

  • Also the paper seems to group EF21 [3] and EF21-SGDM [4] in the experiments section. These are two different algorithms, and it seems that the paper compares to EF21, so it would probably be best to remove EF21-SGDM from the description there.

Presentation and Typos

  • In lines 68-69 "Under non-contractive biased compression (which we refer to as generalized biased compression; Definition 1)" - This also holds for contractive compressors when (ω<1\omega<1), rephrasing it would make it clear that your method hold for contractive compressors as well (which only strengthens it).

  • In the experiments section, it is unclear which CNN model was used (and how many parameters it includes), which makes the extent of compression unclear (especially in the sparsification case). I saw this is mentioned in the appendix, but I think it would be nicer to at least mention the compression ratio in the experiments section.

  • The first paragraph in the experiments section mentions "DC-Q" and "DC-S" which I think refer to your modified to the quantization and sparsification compressors in Sec.3. It would be clearer to define those explicitly (and make it clear that DC-Q uses DC-round).

  • The beginning of Appendix C appears between the algorithms. It would look neater if it is "forced" to appear after algorithms 4-5.

  • In the first line of Theorem 1 "Assumption 1-2" should be "Assumptions 1-2" (plural), and in "let the learning rate satisfies", "satisfies" should be "satisfy".

  • Line 1015, "satisfices" should be "satisfies"

Questions for authors
  1. Can the authors clarify the issue in the proof in D.2 and whether and how it can be fixed?

  2. Can the method be extended to the stochastic gradient setting (and if so, what would be the guarantees in this case)?

  3. Can the authors discuss the implications of the restrictive learning-rate requirement in Theorem 1, especially when ω\omega is large?

  4. Can the author clarify the apparent limitation in the choice of compressors?

10 comments

We thank the reviewer for the detailed feedback and for recognizing the value of reducing auxiliary memory. We have revised the theoretical analysis, expanded the experiments, and clarified the method’s scope and limitations. We have uploaded the revised PDF, with all changes marked in blue.

AuthorsOpenReview ↗

Q1 & W1: Corrected convergence for L-ACTION

We have revised the proof to remove the positive learning rate lower bound. The corrected theorem includes a residual term, and we have revised the corresponding claims throughout the paper.

The original transition from Eqs. (43) to (44) requires a positive learning-rate lower bound when r>0r>0, as the reviewer identified. It therefore does not justify the claimed choice η=Θ(1/T)\eta=\Theta(1/\sqrt{T}). Simply adding the missing lower bound would not resolve this issue.

The revised proof uses a different Young-inequality parameter to bound the inner product between the previous global gradient and the current compression error. The new sufficient conditions are

0<\eta\le \frac{1-r\omega}{4+(8-2r)\omega}\cdot\frac{1}{L}$$ For fixed uniform bounds $r$ and $\omega$ satisfying $r\omega<1$, choosing $\eta=\Theta(1/\sqrt{T})$ subject to this upper bound yields $$\mathbb{E}\\|\nabla f(\hat x^T)\\|^2 \le\mathcal{O}(1/\sqrt{T}) +\frac{2r\omega}{1-r\omega}\zeta^2.$$ This is a weaker conclusion than the original claim: it bounds the expected squared gradient norm up to a residual, rather than establishing general convergence to stationarity. The residual vanishes when $r=0$, $\omega=0$, or $\zeta=0$. The revised $r$ bounds the fraction of global gradient energy on coordinates where the aggregated compressed gradient has the opposite sign or is zero. This removes the need for the original full-precision override on zero-reference coordinates. The complete proof is provided in Appendix D.2. The abstract, introduction, and theoretical discussion now distinguish this guarantee from that of ACTION.
AuthorsOpenReview ↗

Q2 & W2 & W6: Extension to stochastic gradients

We have added three-seed stochastic-gradient experiments and a discussion of their implications in Appendix L.4. The current theoretical guarantees remain limited to full gradients.

The method can be implemented with stochastic gradients. Under unbiasedness and bounded-variance assumptions, we expect ACTION to retain an O(1/T)\mathcal{O}(1/\sqrt{T}) rate if the interaction between stochastic noise and the directional constraint can be appropriately controlled. For L-ACTION, stochastic noise may reduce the reliability of the lagged reference and introduce larger error terms. Establishing these guarantees rigorously remains future work.

The new experiments use CNNs on MNIST and Fashion-MNIST with mini-batches of 256 samples, 2bit quantization, and sparsification with k=1000k=1000. Each setting is repeated with seeds 41, 42, and 43, and the figures show average curves and variability across runs. We compare against uncompressed DSGD, standard compression, and EF21-based compression. In the ACTION experiments, the reference is the current aggregated uncompressed stochastic gradient. ACTION achieves training loss and test accuracy comparable to or better than DSGD and outperforms the compressed baselines. In contrast, LA-Q exhibits late-stage deterioration, while LA-S generally underperforms S and EF21-S.

Appendix L.4 reports these results and discusses the limitations of the lagged reference under stochastic gradients, motivating more accurate reference-sign estimation.

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

The paper proposes directional constraints as an alternative to numerical error feedback for distributed optimization with biased compression. ACTION constrains compression errors relative to the current global gradient; its implementable variant, L-ACTION, uses the previous aggregated gradient and retains only its signs. The authors develop direction-constrained quantization and sparsification schemes, claim nonconvex convergence without compressor contractivity under additional assumptions, and evaluate full-batch distributed training on image and text classification tasks.

Critical strengths
  1. A useful approach to reducing auxiliary state. Retaining a reference sign vector instead of a numerical error-feedback vector addresses a concrete memory concern. The directional ceiling/floor rule for quantization is particularly simple and interpretable (Section 3.1, Eq. (6)). The idealized ACTION analysis provides a coherent sufficient condition for convergence under the stated assumptions (Theorem 1; Appendix D.1).

  2. Substantial reported improvements under aggressive quantization. For ResNet18/CIFAR100 with 4-bit quantization, LA-Q reaches 30% accuracy in 132 rounds, compared with 856 for Q, while EF21-Q does not reach the target within 1,000 rounds (Table 1). For Transformer/IMDB at 4 bits, reaching 60% accuracy requires 54 rounds, versus 194/107 for Q/EF21-Q (Table 2). These results support the practical potential of the approach.

Critical weaknesses
  1. The proof does not establish the claimed L-ACTION convergence rate for positive sign inconsistency. In Appendix D.2, the transition from Eq. (43) to Eq. (44) requires (1+r)Lη−(5ω+3)(Lη)2−r≥0.(1+r)L\eta-(5\omega+3)(L\eta)^2-r\geq 0. This places the learning rate between two roots, whereas Theorem 2 states only the upper bound. For any fixed r>0r>0, the omitted lower bound is strictly positive and is therefore incompatible with the subsequent choice η=Θ(T−1/2)\eta=\Theta(T^{-1/2}) as TT grows. Consequently, the central claim that L-ACTION achieves the same asymptotic rate as ACTION is not established by the supplied argument. Correcting this requires more than adding the missing lower bound: the diminishing-step-size conclusion also needs justification.

  2. The communication accounting does not reconcile an essential algorithmic safeguard with the proposed encoding. Algorithm 3, step 7, requires exact local-gradient values whenever the previous aggregate has a zero coordinate. This safeguard is also used in the proof (Appendix D.2, p. 17). However, Algorithm 4 transmits only fixed-bit codes and a shared scale, which cannot generally represent those exact replacement values. The manuscript does not explain their encoding or account for their payload. Thus, the assertion that all quantization methods have identical communication cost per round (p. 9) is insufficiently supported, and the reported reductions in rounds cannot yet be interpreted as proportional reductions in transmitted bits.

Questions for authors
  1. Can you provide a corrected proof of Theorem 2 for r>0r>0, explaining how the lower bound implied by Eqs. (43)–(44) is reconciled with η=Θ(T−1/2)\eta=\Theta(T^{-1/2})? Does the claimed rate require a stronger condition on rr?

  2. Was Algorithm 3’s exact-transmission safeguard implemented in the experiments? How are these values encoded, how frequently is the safeguard invoked, and do the communication gains persist when its payload is included? Please also make this requirement explicit in Theorem 2.

  3. What valid compression constants ω\omega apply to the evaluated DC-Q/DC-S configurations, and do the observed RtR_t values along actual training trajectories satisfy the corresponding theorem condition? Appendix F evaluates synthetic gradient samples rather than the trajectory-dependent supremum required by Theorem 2.

5 comments

We thank the reviewer for identifying issues in the convergence analysis and algorithm description. We have revised Theorem 2 and its proof, aligned the algorithm with the experimental implementation, and added compression-error bounds and training-trajectory measurements. The revised PDF has been uploaded, with changes marked in blue.

AuthorsOpenReview ↗

W1 & Q1: Corrected convergence for L-ACTION

We have revised the proof to remove the positive learning rate lower bound. The corrected theorem includes a residual term, and we have revised the corresponding claims throughout the paper.

The original transition from Eqs. (43) to (44) requires a positive learning-rate lower bound when r>0r>0, as the reviewer identified. It therefore does not justify the claimed choice η=Θ(1/T)\eta=\Theta(1/\sqrt{T}). Simply adding the missing lower bound would not resolve this issue.

The revised proof uses a different Young-inequality parameter to bound the inner product between the previous global gradient and the current compression error. The new sufficient conditions are

0<\eta\le \frac{1-r\omega}{4+(8-2r)\omega}\cdot\frac{1}{L}$$ For fixed uniform bounds $r$ and $\omega$ satisfying $r\omega<1$, choosing $\eta=\Theta(1/\sqrt{T})$ subject to this upper bound yields $$\mathbb{E}\\|\nabla f(\hat x^T)\\|^2 \le\mathcal{O}(1/\sqrt{T}) +\frac{2r\omega}{1-r\omega}\zeta^2.$$ This is a weaker conclusion than the original claim: it bounds the expected squared gradient norm up to a residual, rather than establishing general convergence to stationarity. The residual vanishes when $r=0$, $\omega=0$, or $\zeta=0$. The revised definition of $r$ also includes zero-reference coordinates, as explained below. The complete proof is provided in Appendix D.2. The abstract, introduction, and theoretical discussion now distinguish this guarantee from that of ACTION.
AuthorsOpenReview ↗

W2 & Q2: Zero-reference coordinates and communication cost

We have removed the full-precision override from Algorithm 3 and revised the analysis to cover the implementation used in the experiments. Zero-reference coordinates no longer require an additional transmission mechanism.

The override in the original Algorithm 3 was not implemented. We initially assumed that zero coordinates in the aggregated compressed gradient would be negligible after initialization, but this assumption was incorrect under aggressive compression. This caused a discrepancy between the algorithm description and the implementation.

The implementation handles zero-reference coordinates as follows:

  • DC-Q: apply ordinary rounding.
  • DC-S: include the coordinate in the safe set and apply the normal selection rule.

Neither method triggers additional full-precision transmission solely because the reference is zero. To analyze these rules, we now define

St−=j:[gt]j[∇f(xt)]j<0 or [gt]j=0.S_t^-=\\{j:[g^t]_j[\nabla f(x^t)]_j<0\ \text{or}\ [g^t]_j=0\\}.

Accordingly, RtR_t measures the fraction of global gradient energy on sign-reversed or zero-reference coordinates, and rr uniformly bounds this fraction. The initial iteration with a zero reference is handled separately in the proof. These changes bring Algorithm 3 and Theorem 2 into agreement with the existing implementation without changing the reported experimental trajectories.

For communication, Q, EF21-Q, and LA-Q use the same quantization-code and scale formats at a given bit width. Consequently, the reported reductions in rounds for LA-Q relative to Q and EF21-Q translate into proportional reductions in cumulative encoded uplink payload.

For DC-S, we reduce the number of explicitly transmitted entries to offset the mask overhead. The adjusted number remains positive in all evaluated configurations, so the fallback is never invoked. The two FP32 reconstruction scalars, MM and mm, add 8 bytes per client when the mask is used, which is negligible at the evaluated communication budgets.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Revisions and Main Contribution

We have revised the manuscript in three main areas, summarized below. The updated PDF is available with changes marked in blue.

  1. Theory and algorithm corrections. We rewrote Theorem 2 and its proof to remove the positive learning-rate lower bound. The corrected guarantee requires rω<1r\omega<1 and includes an explicit residual, which is now reflected throughout the manuscript. We also removed the unimplemented full-precision override and incorporated zero-reference coordinates into the analysis, aligning the algorithm and proof with the experimental implementation.
  2. Expanded empirical evaluation. We added uncompressed baselines, actual training-trajectory measurements of reference quality and compression error, auxiliary-memory comparisons across four models, and three-seed SGD experiments. The INT8 implementation reduces per-client auxiliary-state memory by 75% relative to EF21’s FP32 state. The revised discussion also explicitly reports L-ACTION’s instability and weaker performance in some settings.
  3. Clearer theoretical positioning and scope. We added compression-error bounds and a comparison with unbiased compression, contractive compression with EF21, and scaling-based approaches. We also discuss finite-horizon learning-rate restrictions and distinguish ACTION’s idealized guarantee from the limitations of its practical lagged implementation.

Main Contribution:

The core contribution of this work is direction-constrained communication compression. ACTION’s theory shows that, under the stated assumptions, constraining the direction of compression errors provides convergence guarantees without requiring the compressor to be contractive. Moreover, the coordinatewise constraints depend only on the reference signs, allowing L-ACTION to use sign-level auxiliary state and substantially reduce auxiliary-memory requirements compared with EF21.

In the added experiments, ACTION outperforms uncompressed DGD, further demonstrating the potential of this mechanism. L-ACTION approximates the reference using the signs of the previous aggregated compressed gradient. Its theoretical restrictions and performance gaps in some experiments reveal the limitations of this simple lagged estimate. The directional constraints require reliable global-gradient signs rather than full gradient values. Improving sign estimation while maintaining low auxiliary-memory costs therefore offers a clear research direction for narrowing the performance gap between L-ACTION and ACTION.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.