acceptodds
Under review as a conference paper at ICLR 2027

Accelerated Methods for Nonconvex Optimization Using Comparisons

Abstract

We study the problem of finding stationary points of non-convex functions when access to the objective is provided only through a comparison oracle that, given two points, outputs which has the larger function value. For a twice differentiable with Lipschitz gradient and Hessian, we develop an algorithm that outputs a list of points containing at least one -stationary point using queries, matching the state-of-the-art result of zeroth-order methods with function evaluations. To the best of our knowledge, our algorithm is the first one that achieves Nesterov-type acceleration with comparison queries. Technically, our approach combines restarted accelerated gradient descent with comparison-based estimates of gradient directions. Specifically, we design a geometric grid of guesses for gradient norms at reference points and an anchor-based procedure for estimating gradient norm ratios, enabling accelerated updates under controlled errors without direct access to gradient magnitudes.

Primary area:
optimization
Keywords:
optimization, acceleration, stationary point, comparison

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_2iPWOpenReview ↗
Rating
1
Confidence
3
Informativeness
3
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies finding an ϵ\epsilon-first-order stationary point of a lower-bounded, nonconvex function with Lipschitz gradient and Hessian, using only noiseless comparisons of function values. Its main claim is a randomized algorithm returning a list containing at least one stationary point, with comparison complexity

\frac{n\sqrt L\,\rho^{1/4}\Delta}{\epsilon^{7/4}} +\frac{n\sqrt L}{(\rho\epsilon)^{1/4}} \right).$$ The goal is to obtain accelerated dependence on accuracy while retaining nearly linear dependence on dimension. The method adapts restarted accelerated gradient descent by decomposing each gradient into an anchor magnitude, a relative magnitude, and a direction. It enumerates geometric guesses for anchor magnitudes and estimates magnitude ratios from gradient directions at endpoints and their midpoint.
Critical strengths

[1] The research question is significant. Establishing nonconvex acceleration from comparisons alone would clarify how much numerical information accelerated optimization actually requires.

[2] The anchor-based decomposition is a useful idea. Estimating relative magnitudes could avoid enumerating a new magnitude guess at every iteration. Lemma 11 identifies a meaningful geometric relationship and explicitly exposes its conditioning requirements.

Critical weaknesses

[1] The rank-one reconstruction in Algorithm 4 seems incorrect.

Theorem 2 defines \texttt{ComparisonGE} as returning a unit-vector estimate of the normalized gradient. Consequently, Algorithm 4, line 4, computes

\frac{\widehat g_+-\widehat g_-} {\|\widehat g_+-\widehat g_-\|},$$ where \$ \widehat g_\pm \$ estimate normalized gradients. Subtracting these directions generally does not recover the direction obtained by subtracting the full gradients. Therefore, it seems possible that Algorithm 4 fails to supply its direction-accuracy hypothesis, needed Theorem 6 in Theorem 7. [2] The gradient-magnitude grid need not contain a valid guess. Algorithm 1 and Corollary 1 use $G_{max}=2L$, but the stated assumptions do not imply $\|\nabla f(x)\|\le2L$.
Questions for authors

[1] What is the intended rank-one reconstruction algorithm? Please reconcile Algorithm 4 and prove a quantitative conditioning bound sufficient for Theorem 6

[2] What justifies the magnitude-grid upper bound (2L)? If large gradients are handled separately, where is that case included in the algorithm and global proof ?

[3] Which result establishes that the actual anchors and precision choices make the ratio estimates satisfy Assumption 1 throughout an epoch ?

[4] Should Algorithm 5 use a normalized step of length (R) rather than (1/L) ?

1 comment

Thank you so much for these constructive questions and kindly pointing out non-rigorousness in our paper.

For your question [1]: We have reconstructed the rank-one-search framework with a series of line search (Algorithm 4). In each line search process we try two directions: the gradient and the dominant eigen direction of Jacobian, and prove that at least one of them aligns with eigenvector at a constant precision, which is enough. We have provided thorough error analysis about how to get a min⁡{constant,χ/λ}\min\{\text{constant},\sqrt{\chi/\lambda}\} precision (Lemma 3) and why it meets Theorem 6's requirement (Lemma 16). The revised proof therefore does not rely on the original local conditioning constant CgeoC_{\mathrm{geo}}.

For your question [2]: Thank you for pointing out that non-rigorousness! In fact the NormEstimator only apply to anchor norm guessing, thus we can bound their norm under constant scale. We have added a discussion in Remark 2 of the revised manuscript.

For your question [3]: We have added an analysis of how our precision choice can satisfy Assumption 1 in Lemma 2 of new version paper. About anchor choice, we added Appendix C.1 to guarantee an anchor set with at most eight directions and proved that at least one pair in this set can meet the requirement of Assumption 1.

For your question [4]: Thank you so much for pointing out this typo. We should use stepsize R=Θ(ϵ/ρ)R=\Theta(\sqrt{\epsilon/\rho}).

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

The paper studies nonconvex optimization using an exact comparison oracle. Under Lipschitz-gradient and Lipschitz-Hessian assumptions, the proposed algorithm Compasison-RAGD achieves a O~(nϵ−7/4)\tilde{O}(n\epsilon^{-7/4}) complexity bound for returning a list containing an ϵ\epsilon-stationary point. It combines restarted acceleration, gradient-scale guesses, and norm-ratio estimates. The paper provides theoretical analysis only.

Critical strengths
  1. The method combines scale guesses and midpoint-based norm ratios with restarted acceleration. These ingredients address a central obstacle in using comparison feedback.
Critical weaknesses
  1. The rank-one recovery guarantee is incomplete. Algorithm 4, line 4, differs from the reconstruction in Appendix D.1. The formula may be corrected, but the proof still needs an error bound. The appendix does not bound the conditioning factor CgeoC_{\mathrm{geo}}. It also does not show that the terms involving n κ/λ\sqrt n\,\kappa/\lambda and n ρr/λ\sqrt n\,\rho r/\lambda satisfy Theorem 6’s accuracy requirement under Theorem 7’s assumptions.

  2. Lemma 10 analyzes centered Hessian images, rather than the algorithm’s anchor gradients. Lemma 11 requires angular separation and small errors. The paper does not establish these conditions along the trajectory, especially for the midpoint approximation. Appendix B assumes a fixed effective stepsize and controlled gradient errors. Algorithm 2’s selection rule is not shown to satisfy these assumptions.

Questions for authors
  1. What is the intended rank-one reconstruction? Can you bound its conditioning and show that it meets Theorem 6’s accuracy requirement throughout Theorem 7’s regime?
1 comment

Thank you so much for raising these important weaknesses and questions!

We have reconstructed the rank-one-search framework with a series of line search (Algorithm 4). In each line search process we try two directions: the gradient and the dominant eigen direction of Jacobian, and prove that at least one of them aligns with eigenvector at a constant precision, which is enough. We have provided thorough error analysis about how to get a min⁡{constant,χ/λ}\min\{\text{constant},\sqrt{\chi/\lambda}\} precision (Lemma 3) and why it meets Theorem 6's requirement (Lemma 16). The revised proof therefore does not rely on the original local conditioning constant CgeoC_{\mathrm{geo}}.

About the second weakness: thank you very much for pointing out this critical bug: the original anchor choice based on sampling cannot achieve enough precision. We have replaced the anchor choosing process with the idea to project the probes into a subspace with at most 4 dimension, and gave a proof of why it is enough for our algorithm (Lemma 13). You can refer to Appendix C.1 for more details, and it's application in algorithm is in lines 3-5 of Algorithm 5.

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

This paper studies a class of zeroth-order optimization problem that uses only the comparison oracle, which, given two points x,yx,y, only determines whether f(x)≥f(y)f(x) \ge f(y) or f(x)≤f(y)f(x) \le f(y). They propose an algorithm which outputs an ϵ\epsilon-stationary point using O~(n/ϵ7/4)\tilde{O}(n/\epsilon^{7/4}) oracle queries for function f ⁣:Rn→Rf\colon \mathbb{R}^n \to \mathbb{R} with Lipschitz continuous gradient and Hessian.

Critical strengths

I am not an expert in zeroth-order optimization, and the fact that one can perform an inexact version of restarted accelerated gradient descent using only the comparison oracle to approximate the gradient was interesting to me. The paper assembles the right-looking technical contents needed for their Comparison-RAGD and the illustration of the path toward algorithm design is pretty clear (around lines 126-143).

Critical weaknesses

I think there are several technical gaps in the exposition that makes the soundness of the paper difficult to judge.

First, Line 4 of Algorithm 4 computes u^=±g^+−g^−∣g^+−g^−∣\widehat{u} = \pm\frac{\widehat{g}_+ - \widehat{g}_-}{\\|\widehat{g}_+ - \widehat{g}_-\\|} for direction recovery, but g^+\widehat{g}_+ and g^−\widehat{g}_- are outputs of ComparisonGE, so they are approximations of normalized gradients at x0±rvx_0 \pm rv, not the raw gradients. This should be reflected into the algorithm design. I think the proof of Lemma 2 in the appendix is handling this aspect correctly, but there still is another problem. It explains that the reconstruction map is locally Lipschitz without proving it and providing a quantitative formula for CgeoC_\mathrm{geo}. Then, it upper bound min⁡∣u^−u∣,∣u^+u∣\min\\{ \\|\widehat{u} - u \\| , \\|\widehat{u} + u \\| \\} using CgeoC_\mathrm{geo}, which would depend on the input uu as it is a local Lipschitz constant near uu. In the statement of Lemma 2, however, this is treated as a universal constant CC that is independent of the input.

Second, proof argument for Theorem 7 in the lines 453-454 refer to Theorem 6, which requires the min⁡∣u^−u∣,∣u^+u∣≤ηu≤ϵ32LR\min\\{ \\|\widehat{u} - u \\| , \\|\widehat{u} + u \\| \\} \le \eta_u \le \frac{\epsilon}{32LR}. However, substituting the choice of parameters in Theorem 6 into the bound on min⁡∣u^−u∣,∣u^+u∣\min\\{ \\|\widehat{u} - u \\| , \\|\widehat{u} + u \\| \\} in Lemma 2 gives the residual terms proportional to n\sqrt{n} that do not vanish with ϵ\epsilon, so it is uncertain whether the argument actually goes through.

Lastly, I am not sure what the authors means by "We deal with this case by choosing two initial points with separated gradient directions, thus we can guarantee that at least one of the initial point gradient is separated from the current point gradient, and choosing the better one gives a better decrease than the exact AGD update." in lines 338-341. Isn't there a possibility that choosing a 'better one', which presumably means the choice with smaller objective value, would have a larger error in gradient that does not meet Assumption 1?

While these points may be fixable, I think the technical proofs might require rewriting in general. There are many imprecise arguments that look hand-wavy and make the paper difficult to follow for readers, even if they are ultimately correct.

Questions for authors

Please refer to the Weaknesses section above.

1 comment

Thank you so much for pointing out these gaps and constructive questions!

For your first question: A bug in original eigenvector direction recovery framework is that, if we want the recovery to be accurate enough, we need σ2(H)\sigma_2(H) to be small enough, thus there is a gap between the threshold σ2(H)\sigma_2(H) of two cases. So we replaced the framework with a series of line search (Algorithm 4). In each line search process we try two directions: the gradient and the dominant eigen direction of Jacobian, and prove that at least one of them aligns with eigenvector at a constant precision, which is enough. We have provided thorough error analysis about how to get a min⁡{constant,χ/λ}\min\{\text{constant},\sqrt{\chi/\lambda}\} precision (Lemma 3) and why it is enough (Lemma 16). The revised proof therefore does not rely on the original local conditioning constant CgeoC_{\mathrm{geo}}.

For your second question: Sorry for that computing error. Equation (8) accounts for the n\sqrt{n} factor by choosing the probe radius rJr_J and direction precision δJ\delta_J so that the columnwise errors yield the operator-norm bound in Eq. (9). Since the query cost of ComparisonGE depends only logarithmically on 1/δJ1/\delta_J, this adjustment preserves the stated O~\widetilde O query bound.

For your third question, we agree that a smaller objective value alone does not guarantee a smaller gradient estimation error. We have clarified the anchor selection rule in Algorithm 2. At each momentum point yky_k, line 6 selects the anchor that maximizes the product of its estimated gradient norm and the sine of the estimated angle between its gradient and the gradient at yky_k. Lines 7–8 then use this anchor to estimate the norm ratio and perform the update. For a suitable anchor pair and scale guess, Lemma 2 and its proof in Appendix C.3 show that, unless an ϵ\epsilon-stationary candidate has already been retained, the updates satisfy Assumption 1 at the actual iterates with a single fixed step size hh. Thus the analysis does not require tracking the exact AGD trajectory. Algorithm 5 compares objective values only after collecting the epoch's candidates (lines 9–10). If one trajectory yields the required decrease, the selected candidate inherits that decrease.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.