- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper initiates the study of gradient compression in non-smooth non-convex stochastic optimization. The authors adapt error feedback to the FTRL framework to obtain C-FTRL, avoiding the cross-round coupling between projection and compression errors in OGD, and embed it into the O2NC conversion to obtain C-O2NC with O(dε⁻³δ⁻¹) query complexity under the sign compressor. In the zeroth-order setting, a compression-estimation decoupling strategy controls both errors simultaneously through multi-sample averaging and recursive compression, matching the complexity of first-order compressed and uncompressed zeroth-order optimal methods. The results extend to general compressors and distributed bidirectional compression.
Critical strengths
The strongest contribution is the first complete theoretical picture of compressed non-smooth non-convex optimization. It covers first-order, zeroth-order, general compressors, and distributed settings, with the zeroth-order complexity matching both the compressed first-order and the uncompressed zeroth-order optima, a clean compression-for-free result.
Critical weaknesses
- The experimental strength does not match the theoretical claims. The strongest decoupling and distributed bidirectional results are only validated on a9a with 8 workers, CIFAR-10 covers first-order only, and there are no large-scale training scenarios, no wall-clock time, and no end-to-end communication bytes, so the claimed efficiency lacks empirical support.
- There is a substantial gap between the theoretically sufficient number of recursive compression rounds and the values used in practice. In the distributed first-order setting, the theory requires many rounds for sign compression, whereas the CIFAR-10 experiments use only two or three. The a9a experiments also tune the number of rounds without reporting the selected value for each configuration. The paper does not explain why so few rounds suffice in practice or whether this gap results from a loose worst-case analysis.
Questions for authors
- Is the additional dimension dependence in the first-order scaled-sign setting intrinsic? Can the authors provide a compression-specific lower bound, or clarify whether removing or improving this dependence remains an open problem?
- For scaled-sign compression, the distributed theory requires many recursive compression rounds, whereas the CIFAR-10 experiments use only two or three. Why do so few rounds suffice empirically, and can the theoretical dependence on the number or quality of compression rounds be tightened?
4 comments
Response to Reviewer nhEF (Part 2)
Q1. Can the authors provide a compression-specific lower bound, or clarify whether removing or improving this dependence remains an open problem?
Response. For the scaled sign compressor, establishing a matching lower bound remains a challenging open problem. The main technical difficulty is constructing hard instances whose compressed observations are difficult to distinguish while their approximate stationary points are sufficiently separated. In particular, scaled sign preserves the sign of every nonzero coordinate, regardless of its magnitude, together with the overall norm. Consequently, standard hard instances that rely on gradually revealing gradient information do not directly yield an additional factor, since the scaled sign compressor still reveals the active coordinates at each query. Establishing a matching lower bound therefore requires constructing hard instances in which the missing relative magnitudes are essential for finding a -stationary point, while ensuring that this information cannot be recovered through adaptive queries. Determining the optimal dimension dependence for the scaled sign compressor remains an open problem.
References
[1] Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression. NeurIPS, 2022.
We hope that the above responses address your concerns, and we would be happy to answer any further questions during the discussion period.
Thank you for the clarification and additional experiments. The added communication and wall-clock results, together with the discussion of the compression rounds, have largely addressed my main concerns. I am therefore raising my score from 2 to 3.
Dear Reviewer nhEF,
Thank you for your reassessment and positive update.
Best,
Authors
Response to Reviewer nhEF (Part 1)
Thanks for your insightful feedback and your interest in our work! We have uploaded our revised paper, with the changes highlighted in blue for ease of reference.
W1. The experimental strength does not match the theoretical claims.
Response. To further validate our methods, we supplement the zeroth-order experiments with an image classification task on the MNIST dataset in the revised paper (refer to Appendix D.3 on page 22). As shown in the experimental results, our DistReC-O2NC achieves better performance than the baselines, further demonstrating its effectiveness in zeroth-order optimization.
Moreover, we supplement the CIFAR-10 experiments with results plotted against cumulative transmitted bits and wall-clock time to further evaluate the communication and computational efficiency of our methods (refer to Appendix D.4, Figures 15, 16, 17 and 18 on page 26).
We also report the total number of transmitted bits and wall-clock time for CIFAR-10 training in the 16-worker distributed setting with the sign compressor, as summarized below.
DistC-O2NC consistently requires fewer transmitted bits than the uncompressed baseline, demonstrating the benefits of compressed communication. Moreover, to balance the R communication rounds per parameter update, DistC-O2NC uses a batch size R times that of the baselines, reducing the number of parameter updates per epoch to approximately 1/R of that required by the baselines. Consequently, DistC-O2NC achieves shorter wall-clock time in our experiments.
W2 & Q2. There is a substantial gap between the theoretically sufficient number of recursive compression rounds and the values used in practice.
Response. The theoretical choice of R=⌈ω−1⌉ is sufficient to establish our convergence guarantees, but it does not necessarily yield the best empirical performance. This discrepancy can be explained from two perspectives.
A similar practice of using a small number of compression rounds has also been adopted in prior work [1]. Following their experimental setting, we tune R in our experiments.