- 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 for finding a Goldstein -stationary point, matching the best known dependence on these parameters. The paper also presents a corresponding analysis using stochastic gradients and recovers 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
-
Could the authors provide concrete examples of losses that satisfy the current assumptions but violate smoothness, preferably motivated by practical applications?
-
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?
-
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.
-
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 with .
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
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!
We thank the reviewer for the constructive comments and insightful questions. We address each point below and have revised the manuscript accordingly.
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.
The global Lipschitz assumption plays two main roles in our analysis.
First, it controls the approximation error introduced by randomized smoothing. Specifically, G-Lipschitz continuity guarantees ∣fν(x)−f(x)∣≤Gν, allowing us to control the initial optimality gap of the smoothed objective in terms of the original gap Δ. 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), 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.
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.
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.
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.