acceptodds
Under review as a conference paper at ICLR 2027

Non-Smooth Non-Convex Stochastic Optimization: Sign-Based Methods and Beyond

Abstract

Gradient compression algorithms, such as sign-based methods, are widely used to reduce the computational and communication overhead of large-scale optimization. However, existing studies rely on smoothness or convexity assumptions, which are frequently violated in real-world applications. To address this limitation, we initiate the study of non-smooth non-convex stochastic optimization with compressed gradients. Let denote the dimensionality. First, we develop a sign-based online method and incorporate it into the online-to-non-convex (O2NC) conversion, which yields a query complexity of . Second, we consider the zeroth-order optimization setting, where only noisy function values are accessible. In this regime, our method attains an query complexity, which simultaneously matches that of the first-order compressed setting and the optimal complexity of zeroth-order optimization without compression. The primary idea is to design a compression-estimation decoupling strategy, which constructs the gradient estimator with multiple samples and recursively applies the sign compressor over several rounds, thereby controlling the estimation and compression errors at the same time. Finally, we extend our methods to general compressors and to distributed stochastic optimization with bidirectional compression in both the first-order and zeroth-order settings.

Primary area:
optimization
Keywords:
Non-Smooth Non-Convex Optimization, Sign-Based Optimization, Distributed 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_nhEFOpenReview ↗
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
  1. 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.
  2. 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
  1. 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?
  2. 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
AuthorsOpenReview ↗

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.

MethodsD-O2NCD-O2NC-EF21DistC-O2NC(R=1R=1)DistC-O2NC
Transmitted bits9.51×10149.51 \times 10^{14}1.49×10131.49\times 10^{13}1.49×10131.49\times 10^{13}1.49×10131.49\times 10^{13}
Wall-clock time (hours)3.7633.9343.9372.119

DistC-O2NC consistently requires fewer transmitted bits than the uncompressed baseline, demonstrating the benefits of compressed communication. Moreover, to balance the RR communication rounds per parameter update, DistC-O2NC uses a batch size RR times that of the baselines, reducing the number of parameter updates per epoch to approximately 1/R1/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⌉R=\lceil\omega^{-1}\rceil 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.

  • Our theoretical analysis is based on the worst-case compression guarantee E[∣C(x)−x∣2]≤(1−ω)∣x∣2\mathbb{E}\left[\\|\mathcal{C}(\mathbf{x})-\mathbf{x}\\|^2\right]\leq(1-\omega)\\|\mathbf{x}\\|^2. For the scaled sign compressor, the worst-case compression quality is ω=1/d\omega=1/d. However, the actual compression error can be considerably smaller than this worst-case bound in practice. Consequently, a smaller RR may suffice to achieve comparable empirical performance.
  • There is a discrepancy between theoretical guarantees and generalization performance. Our theory characterizes convergence in terms of the (δ,ϵ)(\delta,\epsilon)-stationarity measure of the training objective, whereas generalization performance is evaluated by test accuracy. A small stationarity measure does not imply high test accuracy, and even a small training loss may not guarantee good generalization. Moreover, to balance the number of gradient queries and the total number of transmitted bits, our theoretical analysis uses RR gradient samples per iteration together with RR compression rounds. Consequently, the theoretical choice of R=⌈ω−1⌉R=\lceil\omega^{-1}\rceil requires a large batch size. Although larger batches can improve training performance, they may also adversely affect generalization. Therefore, the theoretical choice of RR does not necessarily yield the best empirical performance, and we tune RR in practice to balance optimization efficiency, communication cost, and generalization performance.

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 RR in our experiments.

AuthorsOpenReview ↗

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 ℓ1\ell_1 norm. Consequently, standard hard instances that rely on gradually revealing gradient information do not directly yield an additional Ω(d)\Omega(d) 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 (δ,ϵ)(\delta,\epsilon)-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

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

This paper studies gradient compression for nonsmooth, nonconvex stochastic optimization. It combines error-feedback FTRL with online-to-nonconvex conversion to find approximate Goldstein stationary points. For zeroth-order optimization, minibatch estimation and repeated residual compression jointly control estimation and compression errors, achieving O(dϵ−3δ−1)O(d\epsilon^{-3}\delta^{-1}) function-query complexity, matching the known uncompressed rate. The framework extends to general contractive compressors and distributed optimization with bidirectional compression. Experiments on online classification, nonconvex SVMs, and ResNet18 training provide empirical support.

Critical strengths
  • A notable strength is the zeroth-order guarantee, which matches the known uncompressed query complexity despite using lossy compression.
  • The framework also accommodates general contractive compressors and bidirectional distributed communication.
Critical weaknesses
  • My main concern is the paper’s novelty and theoretical contributions. Its core approach combines Follow-the-Regularized-Leader (FTRL) with error feedback. However, several key steps appear to have already been presented in Yang et al. (2026). The authors should clarify the technical differences from that work and explain the specific challenges addressed by their method. This is also the main factor influencing my overall assessment.

  • The claimed communication benefits are also not fully demonstrated by the experiments. Although Appendix D includes some results plotted against transmitted bits, the main optimization experiments primarily report performance against iterations or epochs. These results do not establish whether the proposed methods require fewer oracle queries or transmit fewer bits to reach the same accuracy.

Questions for authors
  • Gradient averaging and repeated residual compression have previously been used together. What additional technical obstacle arises in the zeroth-order nonsmooth nonconvex setting, and how does the proposed analysis overcome it?
  • Could the authors clarify the precise technical contribution beyond combining compressed FTRL with the existing O2NC framework?
  • Could the authors clarify which notion of stationarity is guaranteed by Theorems 3, 5, and 7? The first formulation in Definition 2 requires the additional centering condition E[y]=x\mathbb E[y]=x, whereas the Goldstein formulation does not, so these formulations are not generally equivalent. Since the smoothing-transfer result cited in Lemma 8 applies to Goldstein stationarity, does the analysis establish only this notion, or also the stronger centered notion?
6 comments
AuthorsOpenReview ↗

Response to Reviewer a4am (Part 1)

Thanks for the 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 & Q2. The authors should clarify the technical differences from Yang et al. (2026) and explain the specific challenges addressed by their method. Could the authors clarify the precise technical contribution beyond combining compressed FTRL with the existing O2NC framework?

Response. We acknowledge that Yang et al. (2026) are the first to incorporate the error feedback into the FTRL framework to address the coupling between compression and projection errors. While our work builds upon this technique, it goes beyond their framework by establishing convergence guarantees for non-smooth non-convex stochastic optimization. In particular, we address additional technical challenges in zeroth-order and distributed optimization through the following contributions.

  • In the single-node zeroth-order setting, directly combining C-O2NC with a gradient estimator only leads to an unsatisfactory query complexity. To address this issue, we propose ReC-O2NC, which constructs a gradient estimator using RR independent samples to reduce the norm of the estimated gradient while applying FCC for RR rounds to suppress the compression error. For the scaled sign compressor, setting R=dR=d controls both errors simultaneously and achieves an improved complexity.
  • We further generalize the compression-estimation decoupling analysis beyond the sign compressor. The main challenge is that different compressors may have different compression qualities, so the number of repeated compression rounds required to sufficiently control the compression error varies across compressors. We design an adaptive choice of the number of compression rounds that jointly balances gradient-estimation and compression effects.
  • Finally, we extend O2NC to the distributed setting. A key challenge arises from the inherent randomness in the O2NC framework. To overcome it, we synchronize the random variables in O2NC across all workers through a shared random seed. This ensures that every worker queries its local oracle at the same point, so that the averaged local gradients correspond to the gradient of the global objective.

W2. The claimed communication benefits are also not fully demonstrated by the experiments.

Response. We apologize for this omission and provide additional experimental results on image classification using the CIFAR-10 dataset, reporting test accuracy and training loss against cumulative transmitted bits in the distributed settings with 8 and 16 workers under the Rand-KK and scaled sign compressors, respectively. The details are presented in Appendix D.4, Figures 15, 16, 17 and 18 on page 23.

Our method achieves higher test accuracy and lower training loss than the compressed baselines under the same communication budget, further demonstrating its communication efficiency in practice. Moreover, all methods are evaluated using the same number of gradient queries, ensuring a fair comparison in terms of oracle-query costs.

We also report the total number of transmitted bits in the 16-worker setting with the sign compressor, as summarized below.

D-O2NCD-O2NC-EF21DistC-O2NC(R=1R=1)DistC-O2NC
Bits9.51×10149.51 \times 10^{14}1.49×10131.49\times 10^{13}1.49×10131.49\times 10^{13}1.49×10131.49\times 10^{13}

These results demonstrate that our method maintains its performance advantage over the compressed baselines under equal communication budgets, further validating its practical communication efficiency.

AuthorsOpenReview ↗

Response to Reviewer a4am (Part 2)

We also report the total number of transmitted bits required by different methods to achieve 90% training accuracy and 90% test accuracy on CIFAR-10 in the distributed settings with 8 and 16 workers with the Rand-KK and sign compressors, respectively.

8-worker setting:

MetricD-O2NCD-O2NC-EF21DistC-O2NC(R=1R=1)DistC-O2NC
Training accuracy (90%)49.95×101249.95\times10^{12}17.56×101217.56\times10^{12}12.81×101212.81\times10^{12}8.03×10128.03\times10^{12}
Testing accuracy (90%)77.47×101277.47\times10^{12}-22.06×101222.06\times10^{12}13.33×101213.33\times10^{12}

D-O2NC-EF21 does not reach 90% test accuracy, achieving a maximum of 89.42%.

16-worker setting:

MetricD-O2NCD-O2NC-EF21DistC-O2NC(R=1R=1)DistC-O2NC
Training accuracy (90%)99.24×101299.24\times10^{12}3.05×10123.05\times10^{12}2.26×10122.26\times10^{12}1.95×10121.95\times10^{12}
Testing accuracy (90%)164.30×1012164.30\times10^{12}5.60×10125.60\times10^{12}3.07×10123.07\times10^{12}2.58×10122.58\times10^{12}

As shown in the tables, DistC-O2NC consistently requires fewer transmitted bits than other methods to achieve the same training and test accuracy. In particular, compared with uncompressed D-O2NC, our method reduces the communication cost by approximately 6×6\times and 5×5\times to achieve 90% training and test accuracy in the 8-worker setting, respectively. In the 16-worker setting, these reductions increase to 50×50\times and 60×60\times, further demonstrating the efficiency of our method.


Q1. Gradient averaging and repeated residual compression have previously been used together. What additional technical obstacle arises in the zeroth-order nonsmooth nonconvex setting, and how does the proposed analysis overcome it?

Response. To the best of our knowledge, our work is the first to combine gradient averaging and repeated residual compression in non-smooth non-convex zeroth-order optimization. In this setting, the zeroth-order gradient estimator has a variance of O(dL02)O(dL_0^2), which interacts with the compression error and only leads to an unsatisfactory O(d2ϵ−3δ−1)O(d^2\epsilon^{-3}\delta^{-1}) query complexity under compression. We show that choosing R=dR=d for both gradient averaging and repeated compression simultaneously controls these two errors, yielding an improved O(dϵ−3δ−1)O(d\epsilon^{-3}\delta^{-1}) query complexity. Remarkably, this matches the query complexity of our first-order compressed method and the best-known uncompressed zeroth-order method.


Q3. Which notion of stationarity is guaranteed by Theorems 3, 5, and 7?

Response. We apologize for the imprecise statement in Definition 2. The first formulation imposes an additional condition and is therefore stronger than the standard stationarity notion, although it has also been adopted in previous work [1, 2]. Theorems 3, 5, and 7 establish convergence guarantees for the latter notion. Our proofs are based on the second definition. We have corrected Definition 2 in the revised paper.


References

[1] Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion. ICML, 2023.

[2] Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications. ALT, 2026.


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 providing the additional experiments on communication efficiency and for clarifying the stationarity notion guaranteed by the theorems. I appreciate these additions and clarifications.

However, I am still unclear about the additional technical challenges in the zeroth-order setting. I understand that your method achieves an improved query complexity, matching the best-known uncompressed rate. My remaining concern is about the technical contribution underlying this improvement. The response emphasizes choosing R=dR=d for both gradient averaging and repeated compression, but it is not yet clear to me what makes this choice technically nontrivial, or what new analysis is required to establish the resulting guarantee.

Could you clarify the specific obstacle that existing analyses cannot address and identify the key new argument that overcomes it? This would help me understand the contribution beyond the parameter choice itself.

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

This paper studies gradient compression for non-smooth non-convex stochastic optimization. The authors integrate error-feedback FTRL into the online-to-non-convex (O2NC) framework and establish convergence guarantees for first-order and zeroth-order optimization. The framework is further extended to general contractive compressors and distributed optimization with bidirectional compression.

Critical strengths
  1. Meaningful theoretical contribution. The paper addresses an important and relatively unexplored problem by extending gradient compression guarantees to general non-smooth non-convex optimization.

  2. Comprehensive theoretical results. The proposed framework covers first-order, zeroth-order, and distributed settings. In particular, the zeroth-order method achieves an O(dϵ−3δ−1)O(d \epsilon^{-3} \delta^{-1}) query complexity, matching the optimal dimension dependence of existing uncompressed methods.

Critical weaknesses
  1. The distributed methods require multiple compression rounds per iteration. For the scaled sign compressor, the theoretical choice R=dR= d can result in O(d2)O(d^2) communicated bits per iteration, potentially exceeding the cost of transmitting uncompressed gradients. The paper does not establish under what conditions the proposed methods provide actual communication savings.

  2. The zeroth-order experiments (Figures 5–6) compare methods by iteration count without accounting for the 2R2R function evaluations required per iteration. Similarly, the distributed CIFAR-10 experiments (Figures 9–12) do not report total communication costs or wall-clock time. These omissions make it difficult to assess the claimed efficiency advantages.

  3. The proposed framework builds heavily on existing techniques, including O2NC, error-feedback FTRL, and FCC. While extending these techniques to non-smooth non-convex optimization yields meaningful theoretical guarantees, the algorithmic contributions beyond their integration appear relatively limited.

  4. The discussion of high-dimensional zeroth-order optimization omits relevant studies on query-efficient gradient estimation, including but not limited to:

  • Wang et al. "Stochastic Zeroth-order Optimization in High Dimensions", AISTATS 2018,
  • Cai et al. "A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimization", ICML 2021,
  • Qiu and Tong, "Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization", ICML 2024.

These works should be discussed to better contextualize the paper's zeroth-order contributions.

Questions for authors
  1. When R=dR= d, do the proposed methods still offer communication savings over uncompressed methods?

  2. Do the improvements persist under equal function-evaluation or communication budgets?

  3. What are the key technical contributions beyond combining existing O2NC, error-feedback FTRL, and FCC techniques?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 7jT7 (Part 1)

Many thanks for the constructive reviews and your positive recognition of our paper. We have uploaded our revised paper, with the changes highlighted in blue for ease of reference.


W1 & Q1. The distributed methods require multiple compression rounds per iteration. Do the proposed methods offer communication savings over uncompressed methods?

Response. We apologize for the ambiguity in the current presentation. We want to clarify that the choice of R=dR=d is based on a worst-case theoretical analysis.

  • From the perspective of query complexity versus total bits transmitted, compressed communication methods do not theoretically reduce the total communication cost required to achieve the same error compared to uncompressed methods. This phenomenon is consistently observed in the existing gradient compression optimization literature [1, 2, 3, 4, 5].
  • As an illustrative example, consider the distributed optimization with the Top-KK compressor, which satisfies ω=K/d\omega = K/d ([1], Lemma A.1) and assume that each coordinate of a dd-dimensional vector is represented using BB bits. The total number of transmitted bits per local worker for uncompressed O2NC is O(Bdϵ−3δ−1)O(Bd\epsilon^{-3}\delta^{-1}). In contrast, the total bit cost on each local worker in DistC-O2NC is O(BKω−1ϵ−3δ−1)=O(Bdϵ−3δ−1)O(BK\omega^{-1}\epsilon^{-3}\delta^{-1})=O(Bd\epsilon^{-3}\delta^{-1}), which is the same as that of uncompressed O2NC.
  • Nevertheless, this observation does not diminish the significance of these works on distributed optimization with compressed communication. The theoretical guarantees are derived under a worst-case analysis, and in practice, achieving the same optimization error often requires less communication cost.
  • For instance, when the gradient vectors exhibit sparsity, the Top-KK compressor incurs a small compression error, thereby enabling considerable communication savings at no cost to convergence. Prior studies have shown that sign-based methods can achieve performance comparable to uncompressed methods in practice, while substantially reducing the communication cost.

W2 & Q2. The omissions make it difficult to assess the claimed efficiency advantages. Do the improvements persist under equal function-evaluation or communication budgets?

Response. We apologize for this omission. We would like to clarify that our experiments compare all methods under equal function-evaluation and communication budgets. To make this comparison more explicit, we provide additional experimental results on the CIFAR-10 image classification task, reporting test accuracy against cumulative transmitted bits in the distributed settings with 88 and 1616 workers under the Rand-KK and sign compressors. The results are presented in Appendix D.4, Figures 15–18 on page 26. We also report the total number of transmitted bits in the 16-worker setting with the sign compressor, as summarized below.

MethodsD-O2NCD-O2NC-EF21DistC-O2NC(R=1R=1)DistC-O2NC
Bits9.50×10149.50 \times 10^{14}1.48×10121.48\times 10^{12}1.48×10121.48\times 10^{12}1.48×10121.48\times 10^{12}
Wall-clock time(hours)3.763.763.933.933.933.932.122.12

These results demonstrate that our method maintains its performance advantage over the compressed baselines under equal communication budgets, further validating its practical communication efficiency.

AuthorsOpenReview ↗

Response to Reviewer 7jT7 (Part 2)

W3 & Q3. The proposed framework builds heavily on existing techniques, including O2NC, error-feedback FTRL and FCC.

Response. We acknowledge that our methods build on existing techniques. However, we would like to clarify that our work contains additional technical contributions.

  • In the single-node zeroth-order setting, directly combining C-O2NC with a gradient estimator only leads to an unsatisfactory query complexity. To address this issue, we propose ReC-O2NC, which constructs a gradient estimator using RR independent samples to reduce the norm of the estimated gradient while applying FCC for RR rounds to suppress the compression error. For the scaled sign compressor, setting R=dR=d controls both errors simultaneously and achieves an improved query complexity.
  • We further generalize the compression-estimation decoupling analysis beyond the scaled sign compressor. The main challenge is that compressors may have different compression qualities, so the number of repeated compression rounds required to sufficiently control the compression error varies across compressors. We design an adaptive choice of the number of compression rounds that jointly balances gradient-estimation and compression effects.
  • Finally, we extend O2NC to the distributed setting. A key challenge arises from the inherent randomness in the O2NC framework. To overcome it, we synchronize the random variables in O2NC across all workers through a shared random seed. This ensures that every worker queries its local oracle at the same point, so that the averaged local gradients correspond to the gradient of the global objective.

W4. The discussion of the related work.

Response. Thank you for bringing these works to our attention.

  • [6] investigate high-dimensional stochastic zeroth-order convex optimization and propose successive component selection and Lasso-based gradient estimation methods, achieving guarantees with logarithmic dependence on the dimension.
  • [7] propose a zeroth-order block coordinate descent method that leverages compressed sensing to reduce function queries and computational cost.
  • [8] develop GraCe, a query-efficient gradient estimator for smooth non-convex optimization.

While these studies establish important advances in high-dimensional zeroth-order optimization for convex or smooth loss functions, we consider the more general class of non-smooth non-convex objectives. Furthermore, we investigate zeroth-order optimization with gradient compression. By jointly controlling the gradient-estimation and compression errors, we establish an O(dϵ−3δ−1)O(d\epsilon^{-3}\delta^{-1}) query complexity, matching the best-known uncompressed zeroth-order result. We further extend the guarantees to distributed optimization with bidirectional compression.

We have incorporated these studies and clarified their connections to our work in Appendix A.


References

[1] Sparsified SGD with Memory. NeurIPS, 2018.

[2] Error Feedback Fixes SignSGD and other Gradient Compression Schemes. ICML, 2019.

[3] EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback. NeurIPS, 2021.

[4] Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression. NeurIPS, 2022.

[5] Safe-EF: Error Feedback for Non-smooth Constrained Optimization. ICML, 2025.

[6] Stochastic Zeroth-order Optimization in High Dimensions. AISTATS, 2018.

[7] A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimization. ICML, 2021.

[8] Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization. ICML, 2024.


We hope the above responses address your concerns and are happy to provide further clarification if needed.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Global Response

Dear Reviewers,

We sincerely thank you for your constructive comments and questions, which have helped us improve our manuscript. We have addressed your comments point by point in our individual responses and uploaded a revised manuscript with all changes highlighted in blue for ease of reference.

We hope that our detailed responses and revisions adequately address your concerns. We would greatly appreciate your feedback on whether our revisions have sufficiently addressed the concerns raised in your reviews. We are happy to provide further clarification or address any remaining concerns during the discussion period.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.