- Rating
- 1
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies stochastic nonsmooth nonconvex–nonconcave minimax optimization under a uniform projected-PL condition on the inner problem. The authors propose ZOFOSGDA, combining zeroth-order randomized smoothing, first-order gradient ascent, and SPIDER variance reduction. It achieves expected blockwise Goldstein stationarity and projected Goldstein stationarity of the value function, with oracle complexities of for stochastic function evaluations and for stochastic inner-gradient evaluations. Numerical experiments on classification and AUC maximization are provided. I have not identified a clear mathematical error in the main arguments examined.
My main concern is the limited novelty. W. Shi et al. (2026) have already studied a closely related hybrid zeroth- and first-order method for nonsmooth minimax optimization. The present work uses SPIDER instead of momentum, considers projected-PL inner geometry, and provides an additional Goldstein stationarity guarantee for the original value function. While these are meaningful technical extensions, the main ingredients build on established techniques (e.g., Chen et al., 2023; Xu et al., 2023). Overall, I find the conceptual contribution largely incremental.
Shi, Wanli, et al. "Hybrid Zeroth-and First-Order Method for Stochastic Nonsmooth Minimax Optimization." (2026). Chen, Lesi, Jing Xu, and Luo Luo. "Faster gradient-free algorithms for nonsmooth nonconvex stochastic optimization." International Conference on Machine Learning. PMLR, 2023. Xu, Zi, et al. "Zeroth-order alternating gradient descent ascent algorithms for a class of nonconvex-nonconcave minimax problems." Journal of Machine Learning Research 24.313 (2023): 1-25.
Critical strengths
The main strength is the extension of convergence guarantees to nonsmooth minimax problems with a potentially nonconcave inner objective satisfying a projected-PL condition. In particular, the analysis also establishes Goldstein stationarity of the original value function.
Critical weaknesses
My primary concern is the limited novelty. W. Shi et al. (2026) have already proposed a closely related hybrid zeroth- and first-order method for nonsmooth minimax optimization with a similar blockwise Goldstein stationarity guarantee. The use of SPIDER variance reduction and PL-based analysis also builds on established techniques (Chen et al., 2023; Xu et al., 2023). Although the extensions require some technical effort, I find the conceptual and algorithmic contributions largely incremental.
The experimental validation is also not fully convincing. The paper lacks a direct comparison with the closely related hybrid method of W. Shi et al. (2026), making it difficult to assess the practical benefit of SPIDER relative to this existing alternative.
Questions for authors
Assumption 3.2 can be viewed as a projected-gradient analogue of the KL inequality with exponent . Is this exponent essential to the analysis, or could the convergence guarantees be extended to a more general projected-gradient inequality with exponent , possibly with different convergence rates? Clarifying this would help assess the generality of the theoretical results.
10 comments
Part 2
Averaging over gives . Therefore, for ,
y_\delta^ *(x)=\frac{\sin\delta}{\delta}\sin x.$$ For example, at $x=0$, the smoothed maximizer is $y_ \delta^ *(0)=0$, whereas $y^ *(\delta u)=\sin(\delta u)$ is nonzero for almost every sampled $u$. **The asserted identity therefore fails even under strong concavity.** The distinction is consequential because smoothing and maximization generally do not commute. The example satisfies the cited assumptions. On the stated domain, valid constants are $L=2\sqrt{13}$, $L_{fy}=2\sqrt2$, $L_{fxy}=2$, and strong-concavity parameter $\tau=2$. A deterministic oracle has zero variance, and $\max_y f_\delta(x,y)=(\sin\delta/\delta)^2\sin^2x\ge0$, so the oracle and lower-boundedness assumptions also hold. **This false identity is used repeatedly across the paper's theoretical analysis, and its consequences propagate to the main convergence and complexity proofs.** It appears directly in the smoothness argument, Eq. (43) (p. 17), and the outer-gradient tracking argument, Eq. (51) (p. 18). The resulting estimates enter Eq. (86), the Lyapunov recursion Eq. (89), and the final convergence bound Eq. (100) in the proof of Theorem 5.10. Remark 5.11 derives the query complexity from that bound. Thus, the theoretical guarantees used in your comparison depend on this invalid identification of two different maximizing responses. **(b) Shi et al.'s specified estimator is biased, contrary to their Lemma 5.4.** Shi et al. specify a two-point estimator with coefficient $d_1/(2\delta)$ and directions uniform inside the unit ball (p. 5, lines 270–274 and the sampling description on that page). Their Lemma 5.4 claims that this estimator is unbiased for $\nabla_x f_\delta$, with the claimed identity derived in their Eq. (34). **That unbiasedness claim is false for the stated sampling distribution.** To check this claim under the specified distribution, consider $$f(x,y)=\psi(a^\top x)-y^2,\qquad \psi(t)=\max\\{-1,\min\\{t,1\\}\\},\quad a\ne0,\quad y\in[-1,1].$$ This objective is globally Lipschitz on the stated domain and $2$-strongly concave in $y$, with inner gradient $-2y$ and an outer directional derivative independent of $y$. Its deterministic oracle has zero variance, and $\max_y f_\delta(x,y)\ge-1$. At $x=0$, choose $\delta\|a\|<1$. All sampled perturbations then lie in the linear region of $\psi$, and $\nabla_x f_\delta(0,y)=a$. Shi et al.'s stated estimator therefore gives $$\mathbb E\widehat g_x(0,y) =d_1\mathbb E[uu^\top]a =\frac{d_1}{d_1+2}a \ne a=\nabla_x f_\delta(0,y).$$ **The factor $d_1/(d_1+2)$ proves that the specified estimator is biased.** Averaging multiple samples does not remove this bias. The proof additionally assumes $\|u\|=1$ (p. 16), which contradicts the stated ball-sampling distribution. Sphere sampling would give the standard unbiased estimator for ball smoothing, but would change the distribution specified for the method. The stated estimator and its unbiasedness proof are therefore inconsistent. These counterexamples establish errors in two key ingredients of the cited theory, including an identity used repeatedly in the convergence analysis and an unbiasedness claim that fails for the specified estimator. **It is therefore unjustified to use a manuscript with these theoretical errors as an established baseline for concluding that our contribution is incremental.** That comparison credits the cited work with guarantees its analysis does not establish. **3. A finite-query theory for the original nonsmooth minimax objective.** **Our contribution is a framework that provably attains projected Goldstein stationarity of the original nonsmooth value function $\Phi(x)=\max_y f(x,y)$ under nonconcave projected-PL inner geometry, with explicit SZO and SFO query guarantees.** The method obtains this certificate using stochastic function values and inner gradients at approximate inner responses, allowing the maximizing response to be nonunique. The comparison with Shi et al. explains the problem it covers, the objective it certifies, and the analysis needed to attain it.part 3
(a) A theory for nonconcave inner optimization with nonunique maximizing responses. Our framework controls inner-response error under the uniform projected-PL condition of the original problem. Lemma 4.5 bounds distance to the full solution set , and Lemma 4.6 establishes averaged-gap control with an explicit smoothing correction. These estimates make it possible to analyze nonsmooth minimax optimization with nonconcave inner objectives and nonunique maximizers without assuming that smoothing preserves PL. Shi et al. impose strong concavity and build their analysis around a unique maximizing response. That analysis does not cover the inner geometry addressed by our theory.
(b) A stationarity certificate for the original worst-case objective. We prove projected Goldstein stationarity of , certifying the outer decision against its maximizing response while accounting for the error in the auxiliary inner iterate. Shi et al. claim blockwise generalized Goldstein stationarity at a pair , and their Eq. (16) analyzes . Our value-function certificate requires control of . Smoothing and maximization generally do not commute, so the two smoothed objectives differ even when the inner problems are solved exactly. Lemmas D.4 and D.6 control this discrepancy through gradient tracking and establish the transfer to the original . Our theory therefore certifies the original minimax objective itself, a result that the cited blockwise guarantee does not establish. The framework also proves the blockwise stationarity guarantee.
(c) A stochastic algorithm proved to attain this certificate at a quantified query cost. Our coupled SPIDER analysis controls both stochastic estimator errors together with the inner-response tracking error as both variables move. This joint control establishes that the available hybrid queries suffice to attain the original value-function certificate. Corollaries 5.7–5.8 prove both expected stationarity guarantees, including . Under the stated assumptions, including the uniform initial-potential-gap bound , the query costs are
Q_{\mathrm{SZO}}=\widetilde O\left(\Delta_{\mathrm{pot}}d_1^{3/2}\delta^{-1}\epsilon^{-3}\right),\\ Q_{\mathrm{SFO}} =\widetilde O\left(\Delta_{\mathrm{pot}}d_1^{1/2}\delta^{-1}\epsilon^{-3}\right). \end{aligned}$$ Both costs include the work needed to obtain sufficiently accurate inner responses. For $\delta=c_\delta\epsilon$ with sufficiently small fixed $c_\delta$, both bounds have accuracy dependence $\epsilon^{-4}$. In comparison, Shi et al.'s momentum method reports $\widetilde O(d_1^{3/2}\delta^{-1}\epsilon^{-4})$ SZO queries in Remark 5.11, giving $\epsilon^{-5}$ after the same radius scaling, under its stated assumptions. As shown in point 2, that reported bound is not established by the supplied proof. **Our algorithm has a proved finite-query guarantee for the original value-function certificate under nonconcave inner geometry, together with a lower SZO accuracy exponent than the one claimed in Shi et al.** The averaged-gap, gradient-tracking, and coupled stochastic estimates are essential to establishing this guarantee. **The contribution is a proved finite-query theory for the original nonsmooth minimax objective under nonconcave inner geometry.** Shi et al.'s claimed blockwise result under strong concavity does not establish this guarantee. It is unjustified to dismiss our contribution by treating an unpublished manuscript with the demonstrated mathematical errors as an established theoretical benchmark. The cited work cannot be credited with guarantees that its analysis does not establish, and ICLR's guidelines explicitly prohibit using the missing preprint comparison as a basis for rejection. We therefore ask you to reassess this concern based on the guarantees actually established by the respective analyses. The revised Appendix I provides the detailed comparison.
Reponse (Part 1)
Thank you for your careful review and for raising these concerns about the relationship to prior work, the technical contribution, and the generality of our results. Below, we respond to each point in turn, explain the supporting analysis, and describe the corresponding revisions to the manuscript.
W1: Limited novelty relative to Shi et al. (2026) and lack of a direct comparison
Thank you for pointing us to the related hybrid method of Shi et al. We have carefully examined the cited manuscript. It is inappropriate to treat an unpublished manuscript containing demonstrable theoretical errors as an established benchmark for judging our contribution to be incremental. We also disagree with using the missing comparison as a basis for rejection. Our response has three parts.
Policy. Using the missing preprint comparison as a rejection ground violates ICLR's reviewer guidelines.
Errors in the cited analysis. Two counterexamples expose theoretical errors that undermine its use as an established baseline for assessing our contribution.
Our contribution. We establish a finite-query theory for stationarity of the original nonsmooth minimax value function under nonconcave projected-PL inner geometry, a guarantee that Shi et al.'s analysis does not provide.
We explain each point in detail below.
1. The policy violation and the correction we request.
(a) ICLR explicitly excludes this missing comparison as a rejection ground.
The [ICLR 2027 Reviewer Guidelines], under the question about very recent and non-peer-reviewed work, state
The guideline makes three distinct points. Authors are not required to compare with the specified contemporaneous or unpublished work. Authors who know of relevant preprints are strongly encouraged to cite them. Reviewers may suggest such work, but “the lack of such comparisons cannot be a basis for rejection.” The final clause explicitly restricts which grounds may support a rejection recommendation. A suggestion to add a comparison must therefore remain consistent with that restriction.
(b) The cited manuscript is unpublished, so the above policy applies.
The [manuscript by Shi et al. you cite] is unpublished and therefore falls within the scope of the above policy. The absence of a direct experimental comparison with this manuscript cannot be a basis for rejection. Following the guideline's encouragement to cite relevant preprints, we have added the citation in Related Work and a dedicated discussion in Appendix I of the revised manuscript, explaining the differences in assumptions, analysis, and guarantees.
(c) Your review uses the missing comparison in the way the guideline prohibits.
In your review, under “Critical Weaknesses,” you write
Your review explicitly uses the missing comparison to conclude that our experimental validation is “not fully convincing” and lists this under “Critical Weaknesses.” This makes the absence of the preprint comparison part of the justification for rejection, contrary to the quoted guideline. We therefore ask you to exclude this point as a basis for rejection.
We next examine whether the cited guarantees provide a sound theoretical baseline for your novelty assessment, then explain the additional guarantees established by our work.
2. Errors in the cited paper's theoretical analysis.
Your review cites “a similar blockwise Goldstein stationarity guarantee” in support of the assessment that our contribution is incremental. Using the cited manuscript as an established theoretical baseline is unjustified because its analysis contains two explicit errors in the derivation of those guarantees. We give counterexamples to the maximizer identity and estimator unbiasedness, then show how these errors affect the supplied proofs.
(a) A false maximizer identity is used repeatedly in the theoretical analysis.
Lemma B.1 of the cited version (p. 16, lines 848–850) identifies the maximizer of the averaged objective with the maximizer at an individual perturbed point,
=\arg\max_{y\in\mathcal Y}\mathbb E_u f(x+\delta u,y).$$ To see why this identity fails under their assumptions, consider $$f(x,y)=-y^2+2y\sin x,\qquad x\in\mathbb R,\quad y\in[-2,2],\quad u\sim\operatorname{Unif}[-1,1].$$