- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies Goldstein stationarity for nonsmooth nonconvex objectives when the oracle returns noisy pairwise comparisons. It constructs an unbiased gap estimator that stops after the first change in comparison outcome. Combined with randomized smoothing and an online-to-nonconvex conversion, this gives an upper bound on the number of comparisons. A separate information-theoretic argument gives a lower bound for a smooth convex subclass. Simulations check the estimator, dimension scaling, and optimization behavior.
Critical strengths
- The run-length estimator gives an exact unbiased gap estimate with finite expected comparison cost and a controlled second moment under clear link assumptions.
- The paper connects this estimator to a Goldstein-stationarity guarantee and derives a comparison-specific lower bound. I found no decisive error in the core proof paths.
Critical weaknesses
- The lower bound covers a narrow regime. Theorem 5.1 uses a convex subclass with initial gap at most and requires . Its match with Theorem 4.2 therefore does not settle the comparison cost for general nonsmooth nonconvex objectives with larger initial gaps. The authors identify this remaining factor in Section 5.
- The experiments do not show a practical benefit from unbiased gap estimation. At matched comparison budgets, the biased plug-in within O2NC has a lower smoothed-gradient norm on Chebyshev–Rosenbrock than Comparison-O2NC (0.230 versus 0.387; Appendix C, Table 3). Sign-SGD also has lower regression loss (0.493 versus 0.518), although this comparison does not isolate unbiasedness. The results use three seeds, and the authors themselves report no practical advantage from unbiasedness at these budgets.
- The applied settings differ from the guarantee. Theorem 4.2 uses a global Lipschitz bound and specifies the step and clipping parameters. The real-task runs replace the global with a local finite-difference estimate and tune the parameters by grid search (Section 6, Appendix B). They illustrate the algorithm, but do not show how the theorem-prescribed settings perform.
Questions for authors
- Can the lower bound be extended to larger initial gaps, or can the upper bound be improved there? Which dependence on do the authors expect to be necessary?
- Can the authors test whether the unbiased estimator helps on a broader set of problems and budgets?
6 comments
Revision
We have uploaded a revised version; new and revised parts are shown in blue. In relation to your review:
- Regime of the lower bound (Section 3.3, Appendix A.12). With the improved Theorem 3.8, run with the Lipschitz constant of the hard instances, the upper bound matches the lower bound on them. For larger initial gaps the joint dependence on remains open, as for value oracles. The complementary bound is stated for smooth functions without a global Lipschitz bound.
- Practical benefit of unbiasedness (Section 5, Figure 1, Tables 3 and 4). With 10 seeds and the new radius, sign-SGD remains as good or better, and the plug-in estimator is close to ours. With three times the budget there is no crossover (Figure 2). The paper says this plainly. The new one-comparison method of Section 4 is competitive and the fastest comparison-based method on Chebyshev–Rosenbrock.
- Theorem settings (Table 5, Appendix C.3). Untuned runs with the radius and variance bound of the theorems reduce the objective substantially but stay far from the tuned runs. The explicit schedules do not fit these budgets, and the paper states what was actually run. The finite-difference constant is described as a local Lipschitz scale.
- Further experiments (Table 6). The cauchit link behaves like the logistic link. For the probit link we report all five seeds, including one that stalled, and explain it: the selected radius lies outside the range covered by the cost bound.
Thank you for your detailed response. The new radius improves the upper bound but the lower bound still covers only a very small initial gap. The new Section 4 is a useful addition but it also weakens the main contribution because by Theorem 4.3 a simple one-comparison method has the same bound at high noise and the unbiased estimator can give an advantage only at low noise. In the low-noise experiments (Table 3) the simple method is not worse. My main concerns about the significance of the contribution remain. Therefore, I keep my rating.
We thank the reviewer for the careful review and for checking the core proof paths. We are preparing a revised version that incorporates the changes described below and will post it as soon as possible; we wanted to start the discussion now.
Regime of the lower bound, and the factor Δf/(δε) (Weakness 1, Question 1). Following an observation by Reviewer K4C5, the upper bound improves. Our analysis bounded every queried gap by 2Lρ; since Δu=f(x+ρu)−f(x−ρu) is odd and 2Lρ-Lipschitz on the sphere, it concentrates at scale Lρ/d, and the cost and second moment of the estimator can be controlled direction by direction. With ρ=min�0� the estimator uses O(1) comparisons per gradient estimate, and the comparison complexity becomes O(δε3dL2Δh(1+L2δ2dτ2)). On the hard family of Theorem 5.1 this is O(dL2/ε2+d2τ2/(δ2ε2)), whose comparison-specific term equals the lower bound. So for small initial gaps the comparison cost is settled up to link-dependent constants.
The remaining question is whether Δf/(δε) multiplies the comparison term for larger initial gaps, as in our upper bound. Two facts bear on it:
Practical benefit of unbiasedness (Weakness 2, Question 2). The reviewer's reading of Table 3 is correct, and the paper reports that the experiments show no practical advantage of unbiasedness at these budgets. Unbiasedness is what makes the analysis go through. Whether it helps in practice depends on whether the bias of the alternatives exceeds the target accuracy, and with tuned radii at our budgets it did not.
For the revision we are:
One further result bears on the comparison with sign-based methods. One comparison of an antithetic pair gives the smoothed gradient up to a positive scale and a bias quadratic in the radius, for any link with σ′(0)>0. This is the mechanism behind the competitiveness of sign-SGD in our experiments. The revision adds the corresponding guarantee, with one comparison per pair and without knowledge of the link: it matches the known-link rate at high temperature and costs a factor of order L/ε at low temperature.
Theorem settings versus the experiments (Weakness 3). We agree that the real-task runs illustrate the algorithm rather than test the theorem. The revision adds, next to the tuned runs, runs with the theorem-prescribed step size, clipping parameter and radius (the latter now ρ=min�2�). It also describes the finite-difference constant as a local Lipschitz scale rather than an estimate of the global constant the theorem assumes.