{"id":"b08296f7-16aa-41a0-97fa-67dd4b0f7365","arxiv_id":"2411.16745","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"A comparison-oracle algorithm couples comparison-based gradient direction estimation with normalized gradient descent and claims O(nD^2/epsilon^2 log(nD/epsilon)) queries for smooth strictly quasi-convex minimization, on the strength of an unattainable uniform gradient norm bound.","lead":"This paper claims a method for minimizing smooth quasi-convex functions using only pairwise comparisons of function values, with a stated comparison complexity of O(nD^2/epsilon^2 log(nD/epsilon)). The method combines a comparison-based gradient direction estimator with normalized gradient descent, but the central theorem relies on a gradient lower bound that cannot hold for smooth functions on all of R^n.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The main theorem is vacuous: strict quasi-convexity with a finite minimizer on R^n forces grad f(x*)=0, contradicting the uniform lower bound ||grad f(x)|| >= epsilon that Lemma 4.3 and Comparison-GDE require.","rationale":"The reader's weakest assumption identifies exactly the load-bearing flaw: the uniform lower bound on the gradient is not a consequence of strict quasi-convexity and is incompatible with having a finite minimizer at which the gradient must vanish. The individual lemmas are arithmetically sound under their hypotheses, but the hypothesis class for Theorem 4.4 is empty in the stated setting. This is an internal inconsistency, not a disagreement with existing consensus. A secondary issue is that D is claimed to bound ||x - x*|| for all x in R^n, which is also impossible for an unbounded domain, but the gradient lower bound alone is decisive. Since the central claim collapses under its own assumptions, the reader's REJECT verdict should stand unchanged.","tokens_in":11254,"tokens_out":5345,"duration_ms":52740,"concrete_test":"Apply Algorithm 3 to f(x) = ||x||^2 / 2 on R^n with x* = 0, L = 1, D = 1, epsilon = 0.1. Then grad f(x*) = 0, so Algorithm 3's line 1 (gamma := epsilon) and Lemma 4.3's assertion ||grad f(x)|| > epsilon for all x fail at x = x*. More generally, independently re-derive Theorem 4.4 with x1 = x*: the first call to Comparison-GDE is made at a point where its stated premise ||grad f(x1)|| >= gamma is false, so no direction-estimate guarantee applies. This settles the inconsistency.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 3 sets gamma := epsilon and Lemma 4.3 (line 2) asserts ||grad f(x)|| > epsilon for all x in R^n. But f is differentiable and attains its minimum at x*, so grad f(x*) = 0 < epsilon; hence the premise is false at x*. This is not merely a failure of Definition 2.1's 'in other words' equivalence—L-smoothness makes it generic: ||grad f(x)|| <= L||x - x*||, so the lower bound fails on the whole ball B(x*, epsilon/L). The convergence proof depends on this bound at every iterate: Theorem 3.1 only guarantees the direction estimate if ||grad f(x_k)|| >= gamma, and Lemma 4.3 explicitly invokes it. Since Algorithm 3 does not prove that its iterates avoid the neighborhood B(x*, epsilon/L), the estimate can be invalid at the very steps where the update is made. Consequently Theorem 4.4 is not established for any non-degenerate L-smooth strictly quasi-convex function with a finite minimizer; the stated hypothesis class is empty.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a comparison-oracle method for minimizing L-smooth strictly quasi-convex functions on R^n. It combines the existing Comparison-based Gradient Direction Estimation (Algorithm 2, from Zhang and Li, reference [56]) with a normalized gradient descent scheme (Algorithm 3) and claims an oracle complexity of O((nD^2/epsilon^2) log(nD/epsilon)) comparison queries to find a point x with v_f(x, x*) <= epsilon. The analysis consists of Lemma 4.2 (convergence of an idealized approximate normalized gradient descent under a direction-estimate accuracy assumption), Lemma 4.3 (application of the direction estimation within Algorithm 3), and Theorem 4.4 (the headline complexity bound).","tokens_in":11423,"tokens_out":7109,"duration_ms":56442,"significance":"If the main theorem were valid, the paper would extend comparison-based zeroth-order optimization to quasi-convex functions, a class not handled by the cited comparison-oracle literature. The idealized convergence analysis in Lemma 4.2 is a clean and correct derivation conditional on the availability of accurate unit-norm direction estimates, and the comparison-to-direction reduction is clearly credited to prior work. However, the central theorem rests on an impossible assumption: the uniform lower bound on the gradient norm required by Algorithm 3 is incompatible with differentiability at the minimizer and with L-smoothness on R^n. The hypothesis class is empty, so the claimed complexity result is vacuous over the stated problem class.","major_comments":[{"comment":"The 'in other words' in Definition 2.1 is false. Strict quasi-convexity defined as 'gradients vanish only at the global minima' is not equivalent to the existence of a uniform gamma > 0 with ||grad f(y)||_* >= gamma for all y in R^n. For any differentiable f that attains its minimum at x*, Fermat's condition gives grad f(x*) = 0, so a uniform positive lower bound over all of R^n cannot hold. This false equivalence is used verbatim in the proof of Theorem 4.4 ('there is gamma := epsilon > 0 ... such that ||grad f(x)||_* >= gamma, for all x in R^n (see Definition 2.1)'), so the theorem's premise is unsatisfiable for the class of functions under consideration.","section":"Definition 2.1"},{"comment":"The assumption stated in Lemma 4.3 via Algorithm 3's line 1, that ||grad f(x)||_* > epsilon for all x in R^n, contradicts L-smoothness on R^n. Since grad f(x*) = 0 and grad f is L-Lipschitz, ||grad f(x)||_* <= L||x - x*|| for all x, so the lower bound fails on the whole ball B(x*, epsilon/L). Algorithm 3 has no mechanism to avoid this ball, so the invocation of Theorem 3.1 to produce accurate direction estimates at every iterate is unjustified. Consequently Lemma 4.3 does not prove the claimed bound, and the proof of Theorem 4.4 collapses.","section":"Lemma 4.3 / Algorithm 3"},{"comment":"The headline complexity claim is vacuous over the stated class of objectives. As shown above, no non-degenerate L-smooth strictly quasi-convex function on R^n with a finite minimizer satisfies the uniform gradient lower bound required by Algorithm 3; hence Theorem 4.4 gives no guarantee for any function in the intended class. The problem would need a reformulation, for instance a gradient-norm lower bound only on a bounded sublevel set known to contain the iterates, or a local version of the condition, before the analysis could apply to a nonempty class.","section":"Theorem 4.4 / Abstract"}],"minor_comments":[{"comment":"There are several typographical errors: 'Comparioson' should be 'Comparison', 'Nelson-Mead' should be 'Nelder-Mead', and 'Lipchitz' should be 'Lipschitz'.","section":"Abstract and Section 1"},{"comment":"The query complexity expression in the theorem statement reads O(nD^2/epsilon^2 log(n*delta/epsilon)), whereas the proof and the abstract give O(nD^2/epsilon^2 log(nD/epsilon)); since delta = epsilon/(2D), the intended factor is log(n/delta) = log(2nD/epsilon), so the theorem statement should be corrected to match the proof.","section":"Theorem 4.4"},{"comment":"The 'Require' line states 'D > 0 such that ||x - x*|| <= D; for all x in R^n', which is impossible on unbounded R^n; the intended meaning is that D bounds the distance from x* for the initial point and all generated iterates, as stated in the abstract and used in Lemma 4.2.","section":"Algorithm 3"},{"comment":"The proof introduces h_0 = infinity and uses the telescoping sum with 1/h_k; this is acceptable but should be flagged as an abuse of notation, and the step from equation (4.2) to the telescoped inequality could be expanded slightly for readability.","section":"Lemma 4.2"}],"recommendation":"reject","confidential_remarks":"The flaw is fundamental and not a presentation issue: the main theorem is vacuously true because its assumptions cannot be satisfied by any differentiable function with a finite minimizer. I see no local fix within the manuscript's scope; a revision would require reformulating the problem class or the algorithm's assumptions. I recommend rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nHere's my read of arXiv:2411.16745. The paper assembles a known comparison-based gradient direction estimator (Zhang-Li) with normalized gradient descent and claims the first comparison-oracle complexity bound for smooth strictly quasi-convex minimization. That claim is not supported. The main theorem, Theorem 4.4, assumes a uniform lower bound on the gradient norm, ||grad f(x)|| >= epsilon for all x in R^n, and Algorithm 3 sets gamma := epsilon. But any differentiable function attaining its minimum at x* has grad f(x*) = 0, and L-smoothness forces ||grad f(x)|| <= L||x - x*||, so the lower bound fails on the entire ball B(x*, epsilon/L). The 'in other words' equivalence in Definition 2.1 is false: strict quasi-convexity only says gradients vanish at global minima, not that the gradient norm is bounded away from zero. Lemmas 4.2 and 4.3 are arithmetically correct given that premise; the problem is that the premise is impossible for any non-degenerate L-smooth function on R^n. So Theorem 4.4 is vacuous.\n\nWhat's genuinely useful here: the paper is the first to try the comparison oracle on quasi-convex functions, and the assembly is transparent. The complexity count and the telescoping-sum argument are standard, and the authors correctly attribute the gradient direction estimator to Zhang-Li. No fitted parameters, no circularity, no problematic self-citation. If the domain were restricted to exclude a neighborhood of x*, and the algorithm could keep iterates away from that neighborhood, something like the stated rate could hold. But the paper does not prove that, and with shrinking step sizes the iterates are likely to enter the bad region.\n\nThe weakness is load-bearing and it sinks the headline result. The surrounding machinery is fine, but the central assumption makes the main theorem empty.\n\nWho gets value from this? Someone working on comparison oracles might use the construction as a template, but the paper as written does not establish its advertised result. I'd recommend a desk reject, with an invitation to resubmit after a corrected hypothesis class and a proof that iterates stay in an admissible region.","headline":"The paper's main theorem is vacuous: the assumed uniform lower bound on the gradient norm is incompatible with L-smoothness on R^n, so the headline comparison-oracle complexity result holds for no non-degenerate strictly quasi-convex function.","tokens_in":12060,"tokens_out":2913,"would_cite":false,"duration_ms":27556,"reading_group":"no","serious_thinker":"yes","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C56"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that a comparison oracle suffices to minimize smooth strictly quasi-convex functions, using O((nD^2/epsilon^2) log(nD/epsilon)) comparisons to reach v_f(x,x*) <= epsilon.","keywords":["quasi-convex optimization","comparison oracle","zeroth-order methods","normalized gradient descent","derivative-free optimization","smooth nonconvex optimization","oracle complexity"],"falsifier":"Take $f(x)=x^2$ on $\\mathbb{R}$, which is $L$-smooth with $L=2$ and strictly quasi-convex in the sense that the gradient vanishes only at $x^*=0$. For any $\\varepsilon>0$, the set $\\{x:|f'(x)|<\\varepsilon\\}=\\{x:2|x|<\\varepsilon\\}$ is nonempty, so no global $\\gamma>0$ with $\\|\\nabla f(x)\\|_* \\ge \\gamma$ exists; running Algorithm 3 on this function with $\\gamma=\\varepsilon$ will eventually produce an iterate inside that set, where the direction-estimation guarantee used in Lemma 4.3 no longer applies. Checking this example directly settles whether the paper's standing assumption is compatible with its stated function class.","tokens_in":10960,"feed_emoji":"📉","tokens_out":10678,"duration_ms":93503,"temperature":0.7,"pith_summary":"The paper sets out to show that a comparison oracle — a black box that answers only 'which of these two points has the larger function value?' — is enough to minimize a smooth strictly quasi-convex function on $\\mathbb{R}^n$. It proposes Algorithm 3, which estimates the direction of the gradient by comparisons, then takes a normalized-gradient step of size $D/\\sqrt{2k}$ at iteration $k$. The main result is a query-complexity bound: $\\mathcal{O}\\left((n D^2/\\varepsilon^2)\\log(nD/\\varepsilon)\\right)$ comparisons guarantee a point with $v_f(x,x^*) \\le \\varepsilon$, where $v_f$ measures how well the normalized gradient points toward the optimum. The significance is that prior comparison-oracle results covered convex and strongly convex objectives, and this paper extends the reach of that oracle model to a broader nonconvex class used in economics, control, and geometric reconstruction. The extension is conditional on a strong global steepness assumption, stated below.","feed_headline":"Comparisons alone can minimize quasi-convex smooth functions","feed_subtitle":"Algorithm 3 reaches epsilon-accuracy with O(nD^2/eps^2 log(nD/eps)) comparison queries.","key_machinery":"The load-bearing mechanism is the comparison-based gradient direction estimation subroutine (Algorithm 2, from [56]): at a point $x$ with a known lower bound $\\gamma \\le \\|\\nabla f(x)\\|_*$, it uses directional-preference comparisons to determine the sign of each coordinate of the gradient and then binary-searches ratios to locate a unit vector $\\hat{g}$ within $\\delta$ of $\\nabla f(x)/\\|\\nabla f(x)\\|_*$, spending $O(n\\log(n/\\delta))$ comparisons. Algorithm 3 wraps this routine in normalized gradient descent with step sizes $h_k=D/\\sqrt{2k}$. The analytic core is Lemma 4.2: for any unit-norm direction estimate with error $\\delta$, the telescoping sum over squared distances to $x^*$ gives $\\min_k v_f(x_k,x^*) \\le 3D/\\sqrt{2N}+\\delta D$. Strict quasi-convexity enters through the asserted uniform lower bound on the gradient norm, which justifies calling the subroutine with $\\gamma=\\varepsilon$; without that bound, Theorem 3.1's direction estimate is not guaranteed.","core_discovery":"On its own terms, the paper's claim is that strict quasi-convexity plus $L$-smoothness makes a comparison oracle sufficient for approximate minimization. The target is not function error but $v_f(x,x^*)$, the projection of the normalized gradient onto the direction toward $x^*$; Lemma 2.2 says that for quasi-convex functions this quantity controls function suboptimality through a modulus $\\omega$. Algorithm 3 sets $\\gamma=\\varepsilon$ as a lower bound on $\\|\\nabla f(x)\\|_*$, uses the comparison-based direction estimator to get unit vectors $\\hat{g}_k$ within distance $\\delta=\\varepsilon/(2D)$ of the true normalized gradient, and updates $x_{k+1}=x_k-(D/\\sqrt{2k})\\hat{g}_k$. Lemma 4.2 telescopes the squared-distance decreases and yields $\\min_k v_f(x_k,x^*) \\le 3D/\\sqrt{2N}+\\delta D$; with $N=18D^2/\\varepsilon^2$ this becomes the advertised $\\varepsilon$ guarantee. The proof's engine is that the direction-estimation error enters only additively, so it can be absorbed by setting $\\delta$ proportional to $\\varepsilon/D$.","pith_inferences":["The paper leaves implicit that the global lower-gradient assumption is what does the work; on a bounded domain that excludes an $\\varepsilon$-neighborhood of the minimizer, or under a local lower-gradient condition, the same proof would give a valid local rate without the contradiction with smoothness.","A direct extension would be to replace the exact comparisons with noisy or stochastic comparisons and ask how the $n\\log(n/\\varepsilon)$ direction-estimation cost degrades; the paper does not address noise.","Because $v_f$ can be small even when the function value is far from optimal for quasi-convex functions with flat sublevel sets, practical use of this criterion would need an additional comparison-based stopping rule, such as checking that a step fails to decrease the value.","A natural test of tightness is whether the factor $n$ per iteration is necessary; the paper gives no lower bound for comparison-only quasi-convex minimization, so it may be possible to estimate the gradient direction with $o(n)$ comparisons using random projections."],"forward_implications":["Smooth strictly quasi-convex minimization is solvable by pairwise comparisons alone, with a total comparison budget that grows like $n/\\varepsilon^2$ times a logarithmic factor.","Each iteration of the method uses only comparisons and no gradient values, so the result applies to black-box settings where gradients are unavailable or too expensive to compute.","The convergence guarantee is expressed in terms of $v_f(x,x^*)$, the normalized-gradient progress toward the optimum, not directly in function values; converting it to function error requires the modulus $\\omega$ from Lemma 2.2.","The per-iteration comparison cost is $O(n\\log(n/\\varepsilon))$, so the dominant cost in high accuracy is the $O(D^2/\\varepsilon^2)$ iteration count.","For fixed dimension $n$, the paper's bound becomes $\\widetilde{O}(1/\\varepsilon^2)$, the same order as the normalized-gradient-descent iteration count up to logarithms."],"supporting_citations":[{"why":"supplies the comparison oracle model and the comparison-based gradient direction estimation subroutine (Algorithm 2) that every iteration calls.","marker":"[56]"},{"why":"defines the progress measure v_f and provides Lemma 2.2 linking v_f to function suboptimality for quasi-convex functions.","marker":"[41]"},{"why":"introduces normalized gradient descent for quasi-convex minimization, the algorithm adapted here to comparisons.","marker":"[43]"},{"why":"provides the telescoping-sum proof template used in Lemma 4.2 to convert per-iteration direction error into an additive term.","marker":"[30]"},{"why":"gives recent comparison-oracle algorithms for convex and nonconvex smooth problems that the paper extends to the strictly quasi-convex class.","marker":"[36]"},{"why":"supplies the terminology of strict quasi-convexity and the stochastic quasi-convex optimization setting that motivates the class.","marker":"[26]"}],"fun_headline_variants":["Only comparison queries solve quasi-convex smooth optimization","Gradient-free quasi-convex minimization via comparison oracle","Comparison oracle minimizes quasi-convex functions without gradients","Quasi-convex optimization with comparison queries only"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on the requirement that the gradient length never falls below the target accuracy $\\varepsilon$ away from the optimum, yet a smooth function on all of $\\mathbb{R}^n$ always has points arbitrarily close to the optimum where the gradient length is smaller than $\\varepsilon$, so the assumption cannot hold for the functions the theorem describes.","fun_headline_variants_meta":{"raw":{"variants":["Only comparison queries solve quasi-convex smooth optimization","Gradient-free quasi-convex minimization via comparison oracle","Comparison oracle minimizes quasi-convex functions without gradients","Quasi-convex optimization with comparison queries only"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00065,"raw_usage":{"total_tokens":3037,"prompt_tokens":1054,"completion_tokens":1983,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":670,"completion_tokens_details":{"reasoning_tokens":1935}},"tokens_in":670,"tokens_out":1983,"duration_ms":14779,"temperature":1.0,"reasoning_tokens":1935,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:04:42.804255+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $f(x)=x^2$ on $\\mathbb{R}$, which is $L$-smooth with $L=2$ and strictly quasi-convex in the sense that the gradient vanishes only at $x^*=0$. For any $\\varepsilon>0$, the set $\\{x:|f'(x)|<\\varepsilon\\}=\\{x:2|x|<\\varepsilon\\}$ is nonempty, so no global $\\gamma>0$ with $\\|\\nabla f(x)\\|_* \\ge \\gamma$ exists; running Algorithm 3 on this function with $\\gamma=\\varepsilon$ will eventually produce an iterate inside that set, where the direction-estimation guarantee used in Lemma 4.3 no longer applies. Checking this example directly settles whether the paper's standing assumption is compatible with its stated function class.","supporting_citations":[{"cited_title":"Lectures on convex optimization , Switzerland: Springer Optimization and Its Applications, 2018","cited_arxiv_id":null,"evidence_quote":"defines the progress measure v_f and provides Lemma 2.2 linking v_f to function suboptimality for quasi-convex functions."},{"cited_title":"Minimization methods for nonsmooth conve x and quasiconvex functions, Matekon, 1984, vol","cited_arxiv_id":null,"evidence_quote":"introduces normalized gradient descent for quasi-convex minimization, the algorithm adapted here to comparisons."},{"cited_title":"Online to offline conversions, universality and ad aptive minibatch sizes, in Advances in Neural Information Processing Systems, vol","cited_arxiv_id":null,"evidence_quote":"provides the telescoping-sum proof template used in Lemma 4.2 to convert per-iteration direction error into an additive term."},{"cited_title":"28, 2015","cited_arxiv_id":null,"evidence_quote":"supplies the terminology of strict quasi-convexity and the stochastic quasi-convex optimization setting that motivates the class."}],"review_version":1}