acceptodds
Under review as a conference paper at ICLR 2027

Zeroth-Order SGD with Momentum Resetting Achieves Dimension-Dependent Optimality in Nonsmooth Nonconvex Optimization

Abstract

We investigate the complexity of zeroth-order stochastic gradient methods with momentum for finding -stationary points of Lipschitz-continuous objectives that may be both nonsmooth and nonconvex, where the algorithm has access only to function values. Recent work has developed specialized zeroth-order schemes that achieve the best-known dependence on the key problem parameters in this setting. However, these guarantees rely on particular algorithmic constructions and do not directly apply to classical SGD-type methods, whose existing analyses typically inherit an additional dependence on the smoothness constant of the smoothed objective. In this work, we study a simple variant of zeroth-order SGD with momentum (ZO-SGDM), which retains the standard SGDM update while incorporating an epoch-wise outer loop with periodic momentum resetting. By exploiting the recursive averaging structure of momentum, we show that this ZO-SGDM-type method achieves an oracle complexity of for finding a -stationary point, matching the best-known dependence on , , and attained by specialized zeroth-order methods. Our analysis develops a new proof route that, to the best of our knowledge, is the first to isolate the dimension dependence entirely to the zeroth-order gradient estimator itself, thereby avoiding the additional dimension factor arising from the smoothness of the smoothed objective. Although the theoretical guarantee employs periodic resetting and epoch averaging, our experiments show that these mechanisms do not materially degrade performance and mainly serve as analytical devices, providing an empirical recovery of behavior closer to standard ZO-SGDM.

Primary area:
optimization
Keywords:
Optimization, Zeroth-order, SGD

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_LUpYOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies stochastic zeroth-order optimization for Lipschitz objectives that may be nonsmooth and nonconvex. It introduces ZO-SGDM-PR, which combines momentum SGD with periodic momentum resetting and epoch averaging. By exploiting the weak convexity of the randomly smoothed objective, the analysis establishes an oracle complexity of O(dδ−1ϵ−3)O(d\delta^{-1}\epsilon^{-3}) for finding a Goldstein (δ,ϵ)(\delta,\epsilon)-stationary point, matching the best known dependence on these parameters. The paper also presents a corresponding analysis using stochastic gradients and recovers O(dϵ−4)O(d\epsilon^{-4}) complexity under smoothness.

Critical strengths

The paper provides extensive references and clear comparisons with prior work, helping readers follow its motivation and understand its contributions. The detailed explanations of the algorithm and theoretical analysis make the paper easy to follow.

Critical weaknesses

The paper would benefit from a more detailed discussion of its assumptions, particularly the role and limitations of global Lipschitz continuity and the tradeoffs involved in removing smoothness, as these are central to its motivation.

Questions for authors
  1. Could the authors provide concrete examples of losses that satisfy the current assumptions but violate smoothness, preferably motivated by practical applications?

  2. What role does the global Lipschitz assumption play in the analysis, particularly in controlling smoothing error and the second moment of the estimator? Could it be relaxed to local Lipschitz continuity or suitable moment conditions?

  3. Please summarize the costs of removing smoothness, including the weaker stationarity criterion, stepsize restrictions depending on the smoothing radius, and the additional complexity term involving the weak convexity parameter.

  4. Does access to function values facilitate randomized smoothing and thus help remove the smoothness assumption? Please clarify whether this provides an advantage over methods using stochastic gradients or mainly serves as an analytical tool.

Minor corrections:

Line 58: Replace “(2)–(4) reduces” with “(2)–(4) reduce.”

Line 148: Remove the duplicated period after “dimension d.”

Line 176: Capitalize “we say” as “We say.”

Line 236: Replace the undefined L0L_0 with GG.

Lines 1221–1224: Remove the repeated statement about resetting momentum at the beginning of each epoch.

Line 1257: Replace “as algorithms convergence” with “as the algorithms converge.”

3 comments

We thank the reviewer for the constructive comments and insightful questions. We address each point below and have revised the manuscript accordingly.

Weakness and Question 1. Concrete examples of nonsmooth losses

We thank the reviewer for this suggestion. We have supplemented the experimental appendix with several concrete examples of nonsmooth loss functions that satisfy our assumptions but violate smoothness in Appendix E.1(Line 1193). These examples further illustrate the practical relevance of our theoretical setting.

Weakness and Question 2. Role and relaxation of global Lipschitz continuity

The global Lipschitz assumption plays two main roles in our analysis.

First, it controls the approximation error introduced by randomized smoothing. Specifically, GG-Lipschitz continuity guarantees ∣fν(x)−f(x)∣≤Gν|f_\nu(x)-f(x)|\le G\nu, allowing us to control the initial optimality gap of the smoothed objective in terms of the original gap Δ\Delta. Moreover, the smoothed objective has a Lipschitz-continuous gradient satisfying $\operatorname{Lip}(\nabla f_\nu) =O\left(\frac{\sqrt dG}{\nu}\right)$.

Second, it controls the second moment of the zeroth-order gradient estimator. As discussed in our analysis, the global Lipschitz assumption enables the sharp bound E∣g^ν(x)∣2=O(dG2)\mathbb E|\widehat g_\nu(x)|^2=O(dG^2), which is essential for achieving linear dimension dependence.

We emphasize that the uniform global Lipschitz assumption can be relaxed. Following [1], we can allow sample-dependent Lipschitz constants with bounded second moments without substantial modifications to our proof. Extending our guarantees to locally Lipschitz objectives is also technically feasible under additional coercivity assumptions. One possible approach is to construct an auxiliary objective using projection onto a bounded region. By the nonexpansiveness of projection, the auxiliary loss becomes globally Lipschitz, provided the original loss is Lipschitz on that region. We can then establish that the auxiliary and original updates coincide with high probability and use appropriate tail bounds to translate this into convergence guarantees in expectation. Such an extension would require additional technical arguments and represents an interesting direction for future research.

Weakness and Question 3. Costs of removing smoothness

We thank the reviewer for this suggestion. We have expanded the comparison of theoretical guarantees under the assumptions in the revised manuscript (Line 251-254) to explicitly highlight the costs of removing smoothness: (1) A weaker stationarity criterion, such as expected or Goldstein stationarity, is needed because classical gradient stationarity is generally unsuitable for nonsmooth objectives; (2) stepsize restrictions depending on the smoothing radius through the smoothness constant of the smoothed objective, and (3) an additional complexity term involving the weak convexity parameter. These clarifications make the tradeoffs between smooth and nonsmooth settings more transparent.

Question 4. Role of function-value access

Randomized smoothing serves both algorithmic and analytical purposes. Many stochastic optimization algorithms rely on gradient estimates to guide their updates. While first-order methods typically use stochastic gradients or subgradients, zeroth-order methods naturally employ randomized smoothing and function-value differences to construct an unbiased gradient estimator of the smoothed objective, without requiring gradients of the original nonsmooth loss. This provides an advantage when gradient information is unavailable or difficult to obtain, although it does not imply an inherent advantage over stochastic first-order methods when such information is accessible. Meanwhile, the smoothed objective provides a differentiable surrogate for convergence analysis, whose stationarity guarantees can be transferred to the original nonsmooth problem. Thus, randomized smoothing is not merely an analytical tool but also enables gradient-free optimization of nonsmooth objectives with theoretical guarantees.

Minor Corrections

We appreciate the reviewer's careful attention to these details. We have addressed all the identified typographical, grammatical, and notation issues, and removed the redundant discussion of momentum resetting in the revised manuscript.

We sincerely thank the reviewer once again for the thoughtful comments. The feedback has been valuable in helping us improve the clarity and rigor of our work. We hope that our responses and revisions adequately address the reviewer's concerns and provide a clearer understanding of our contributions.

[1] Kornowski, Guy, and Ohad Shamir. "An algorithm with optimal dimension-dependence for zero-order nonsmooth nonconvex stochastic optimization." Journal of Machine Learning Research 25.122 (2024): 1-14.

Thank you for your response. Since you have addressed my concerns, I will keep my score unchanged.

We greatly appreciate the reviewer's careful consideration and constructive feedback. We sincerely thank the reviewer for your positive assessment and continued support!

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

This paper studies zeroth-order non-smooth, non-convex optimization. In this scenario, the algorithm only has access to function values, via an oracle, and these function evaluations are used to construct (sub)gradient estimates. Algorithm performance is measured by the complexity (that is, number of of function evaluations) needed to find approximate (generalized) stationary points. The authors introduce an algorithm which is a variant of zeroth-order SGD with momentum (ZO-GDM), and they analyze its convergence rate and oracle complexity. Their variant of ZO-GDM involves two key features 1) it periodically resets momentum and 2) the returned parameter is a randomly selected period-averaged iterate. The convergence results they derive are notable in two regards. Firstly, it matches the oracle complexity in terms of d, \epsilon, and \delta of the best known algorithm for this setting, while having the benefit that it is not a specialized algorithm for ZO optimizaton, but rather a straight forward adaption of a first order one. Secondly, they prove that if a subgradient sample is used instead of the ZO estimate, then the dimension dependence on d no longer dominates, thus highlighting the source of the dimension dependence in the bounds.

Critical strengths

The motivation was clear and the results were also presented and explained well.

This seems like an important problem. There is a genuine need for zeroth-order optimization algorithms in settings like black-box optimization, or when derivatives are very expensive to compute. Furthermore, analyses of zeroth-order algorithms can improve understanding of first order algorithms by settings ceilings on complexity and highlighting the benefits of actual gradient information.

There seem to be substantial new results in this paper. Particularly, the authors were able to derive a complexity bound that matches the best known bound in terms of dependence on d, without the need for a particular "zeroth-order specific" algorithm. Additionally, the authors highlight how, when using genuine subgradient samples, the convergence rate improves to the best known rate for that setting.

Critical weaknesses

The title mentions dimension dependent optimality of the algorithm. This implies that the convergence rate matches a previously derived lower bound for zeroth-order nonsmooth nonconvex optimization. However, I didn't find this discussion in the paper. Only that the paper's convergence rate matches the "best known" complexity. This point could use clarification.

Questions for authors

Some minor suggestions that could improve clairty:

  • The paper could benefit from a brief discussion in preliminaries on the relation between the gradient of a function (when it exists) and the non-smooth generalizations of gradient. This would make the paper more accessible for readers that do not have background in zeroth-order methods. Some of this is already covered in Lemma 4, which is helpful.

  • I didn't see the notation underlined \tilde \leq used, although it is mentioned in the notations.

  • Conclusion: There seems to be an errant ! on O!(d...)

1 comment

We sincerely thank the reviewer for the support of our work. We greatly appreciate the thoughtful feedback and the opportunity to clarify our contributions.

Weakness. About "best-known" complexity

We thank the reviewer for raising this important point. At the time of submission, matching joint lower bounds were not yet available, although the separate optimality of the dimension and accuracy dependence had been widely conjectured in related work. We therefore adopted the conservative terminology of "best-known complexity." Recent works [1,2] have since established matching joint lower bounds under the corresponding assumptions and parameter regimes, confirming that our oracle complexity matches the lower bounds for zeroth-order nonsmooth nonconvex optimization. We have incorporated these latest references and clarified the optimality claim in Appendix A.

Questions

(1) Relation between gradients and generalized gradients. We have added a brief discussion in the Preliminaries section (Lines 164–167) to clarify the relationship between classical gradients and their nonsmooth generalizations. We hope this addition provides readers with a clearer understanding of the stationarity concepts used in our analysis and improves the accessibility of our theoretical results.

(2) Notation �0��0�. We thank the reviewer for carefully pointing this out. The notation is primarily used in the appendix rather than the main text.

(3) Typo. We apologize for this formatting error. It has now been corrected in the revised manuscript.

The reviewer's constructive suggestions have been invaluable in helping us strengthen and improve our work. We sincerely thank the reviewer once again for the valuable feedback.

[1] Zhang, Haihan, et al. "Joint lower bounds for zeroth-order nonconvex optimization on Euclidean balls." arXiv preprint arXiv:2610.00275 (2026).

[2] Xia, Yuxuan, and Xiao-Tong Yuan. "On global joint lower bounds in zeroth-order nonconvex optimization." arXiv preprint arXiv:2610.19652 (2026).

Reviewer_1tmWOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The authors analyze zeroth-order SGD with momentum for nonsmooth, nonconvex Lipschitz objectives and establish optimal known oracle complexity by periodically resetting momentum, matching specialized methods’ dependence on key problem parameters. The analysis isolates dimension dependence to the gradient estimator itself, while experiments show that the theoretical mechanisms preserve performance close to standard ZO-SGDM.

Critical strengths

The paper addresses an interesting theoretical problem in zeroth-order optimization by establishing stronger convergence guarantees for a relatively familiar optimization method.

The comparison table in Section 1 does a good job of highlighting previous results for nonsmooth, nonconvex optimization and situating the proposed method relative to existing work.

Critical weaknesses

Limited significance of contributions - My primary concern is the overall significance of the contribution. While the authors establish an improved guarantee for an SGDM-type method, the resulting oracle complexity only matches the previously established best-known rate of Kornowski and Shamir, rather than improving it. Additionally, the result is established for a modified version of ZO-SGDM; hence, I find the resulting contribution somewhat incremental.

Limited experimental validation - The title of the document discusses OPTIMALITY IN NONSMOOTH NONCONVEX OPTIMIZATION, and yet the experiments surrounding this phenomenon were lackluster. While the authors do consider a nonsmooth, nonconvex objective using hinge loss and L1 regularization, the experiment is relatively limited and does not directly evaluate the theoretical setting established in the paper. In fact, the authors acknowledge this limitation in Appendix E.2. Furthermore, the experiments do not investigate how the proposed method scales with dimension (d), despite dimension dependence being one of the paper's primary contributions.

The paper presents its proposed algorithm and zeroth-order oracle in the main text, yet all experimental results are deferred to the appendix. I believe a paper with this theoretical focus would benefit significantly from a more extensive empirical validation.

Presentation and organization - Another one of my concerns with this manuscript in its current form is its presentation. By the time any new results were identified outside of Table 1, over half the document must have already been read. Furthermore, the main paper contains no figures, with all visual results deferred to the appendix.

The abstract is one example that I believe could be significantly improved. A substantial portion is spent discussing prior methods, while the proposed methodology itself receives relatively little explanation. The final sentences are a bit repetitive as well.

Many paragraphs can be merged or referred to the appendix, and more novel developments can be placed in the main paper. Even with the current limited experimental validation, I believe some of the experiments should be brought up into the main paper with additional experiments and ablations run.

Questions for authors

Suggestions for improvements:

I would encourage the authors to expand the experimental evaluation through dimension-scaling experiments and by adding additional nonsmooth, nonconvex optimization problems. A more direct empirical comparison between the theoretical algorithm and the experimental implementations could prove beneficial.

I also recommend condensing the introductory and preliminary material, improving the abstract's emphasis on the actual contributions, and including representative experimental results within the main paper.

Questions for authors:

  1. Given that dimension-dependent optimality is the central result, could the authors provide experiments investigating how oracle complexity scales with dimension (d)?

  2. Beyond matching the existing theoretical complexity of O2NC, what practical or theoretical advantages do the authors consider most significant in the proposed method?

1 comment

We sincerely thank the reviewer for the careful evaluation and thoughtful suggestions. We greatly appreciate the opportunity to further clarify our contributions and strengthen the experimental evidence. We address the concerns in detail below.

Weakness 1. Limited significance of contributions

We thank the reviewer for this comment. We would like to emphasize that our contribution is not to improve the previously best-known oracle complexity, but to demonstrate that a slightly modified version of classical ZO-SGDM can already achieve this rate. To date, many existing methods achieving the best-known oracle complexity, including that of [1], have relied on specialized O2NC-based constructions. In contrast, our analysis establishes the same guarantee for a method that largely preserves the standard SGDM update, while avoiding the additional d\sqrt d factor introduced by conventional smoothness-based analyses. Our contribution therefore lies in extending the best-known complexity guarantee to a more conventional and widely used class of optimization methods.

We also wish to clarify our optimality claim. At the time of submission, matching joint lower bounds were not yet available, motivating our conservative emphasis on dimension-dependent optimality. Recent results by [2,3] have since established matching lower bounds in their respective settings and parameter regimes, which we have now incorporated into Appendix A. Consequently, our ZO-SGDM variant achieves not only optimal dimension dependence, but also the jointly optimal dependence on dimension and accuracy under the corresponding conditions. This further strengthens the significance of our result.

Weakness 2 and Question 1. Limited experimental validation

We agree that stronger empirical validation would benefit the paper. As our primary contribution is theoretical, the original experiments were mainly intended to illustrate the convergence behavior. We have now added dimension-scaling experiments following the settings of related work and incorporated the results (Line 511-524). To provide more comprehensive empirical evidence, we have added three additional experiments on nonsmooth nonconvex objectives (Lines 1242–1264). We would also like to clarify that the purpose of Appendix E.2 (now Appendix E.5) is not to directly validate our theoretical setting, but rather to provide intuition for why smooth and nonsmooth nonconvex optimization can be comparably challenging for our methods.

Weakness 3. Presentation and organization

We appreciate the reviewer's suggestions and regret that the original presentation made the paper difficult to follow. We have condensed the technical discussions, reorganized parts of the main text, moved some technical details to the appendix, and allocated more space to visualizations and intuitive explanations. We have also revised the abstract to eliminate repetition and highlight our main contributions more clearly.

Question 2. What practical or theoretical advantages do the authors consider most significant in the proposed method?

Our main advantage is algorithmic generality. Previous optimal-complexity guarantees relied on specialized O2NC-based methods, whereas we show that a slightly modified ZO-SGDM algorithm is already sufficient to achieve the same optimal rate. More importantly, our analysis eliminates the additional dimension dependence arising from smoothness-based arguments without relying on the O2NC framework. This suggests that the previously suboptimal dimension dependence of conventional ZO-SGD analyses is not necessarily an intrinsic limitation of SGD-type methods. Experimentally, ZO-SGDM-PR also exhibits convergence behavior comparable to standard ZO-SGD(M), supporting the practical relevance of our approach.

We are grateful to the reviewer for the constructive feedback, which has helped us improve both the presentation and empirical evaluation of our work. We hope that the additional experiments and clarifications adequately address the concerns and provide a clearer picture of our contributions.

[1] Kornowski, Guy, and Ohad Shamir. "An algorithm with optimal dimension-dependence for zero-order nonsmooth nonconvex stochastic optimization." Journal of Machine Learning Research 25.122 (2024): 1-14.

[2] Zhang, Haihan, et al. "Joint lower bounds for zeroth-order nonconvex optimization on Euclidean balls." arXiv preprint arXiv:2610.00275 (2026).

[3] Xia, Yuxuan, and Xiao-Tong Yuan. "On global joint lower bounds in zeroth-order nonconvex optimization." arXiv preprint arXiv:2610.19652 (2026).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.