Can a One-Point Feedback Zeroth-order Algorithm Achieve Linear Dimension Dependent Sample Complexity?

Haishan Ye; Xiangyu Chang

REVIEW 2 major objections 3 minor 1 cited by

Can a One-Point Feedback Zeroth-order Algorithm Achieve Linear Dimension Dependent Sample Complexity?

T0 review · 2 major / 3 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims a one-point feedback zeroth-order algorithm can achieve linear dimension dependence in sample complexity for convex optimization, matching two-point methods.

desk verdict Abstract claims a real open-problem resolution, but with only the abstract in hand the proof and the exact assumptions are a black box, so this is a 'must referee when complete' rather than a verified result. read the letter →

arxiv 2508.12228 v1 pith:CCQJM2GJ submitted 2025-08-17 math.OC

Haishan Ye , Xiangyu Chang This is my paper · ORCID

classification math.OC MSC 90C2590C56

keywords zeroth-orderoptimizationone-pointfeedbacksamplecomplexitydimensiondependenceconvexderivative-free

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper addresses the long-standing question of whether one-point feedback zeroth-order algorithms—methods that see only a single noisy function evaluation per query—can achieve the same linear dimension dependence in sample complexity as two-point methods. The author claims they can: the paper constructs an algorithm whose oracle complexity scales linearly with the dimension $d$ for convex objectives, where previous one-point methods typically scaled quadratically or worse. If correct, this closes a gap between one-point and two-point zeroth-order optimization and shows that the single-evaluation constraint is not inherently costly in dimension dependence.

What carries the argument

The central object is the one-point feedback zeroth-order optimization model, in which each oracle call returns one noisy function value at a chosen point. The paper's contribution is a new algorithm within this model—not named in the abstract—whose query strategy and estimation procedure keep the dimension dependence linear.

What would settle it

Run the proposed algorithm on a sequence of convex, $L$-smooth objectives in dimensions $d = 10, 20, 40, \ldots$ using a legitimate one-point noisy oracle and measure the number of evaluations needed to reach a fixed accuracy $\epsilon$; if the required evaluations grow faster than linearly in $d$, the central claim is false. A rigorous lower bound showing every one-point feedback algorithm needs $\Omega(d^2)$ evaluations on some such function family would also settle it.

Watch

Extended reading notes

Core claim

The central discovery is an affirmative answer to the open question: there exists a one-point feedback zeroth-order algorithm for convex optimization whose sample complexity has linear dimension dependence, matching the optimal $O(d/\epsilon^2)$-type rates of two-point methods. The paper presents this algorithm as a counterexample to the prevailing intuition that one-point feedback necessarily incurs at least quadratic dimension overhead.

Load-bearing premise

The claimed linear dimension dependence rests on the standard one-point stochastic oracle assumptions—convexity and smoothness of the objective plus unbiased, bounded-variance noise—which the abstract states only as 'convex'.

Editorial extensions

If this is right

The open question of matching two-point dimension dependence is resolved affirmatively for convex problems.
One-point feedback algorithms become viable in high-dimensional derivative-free settings where only single noisy evaluations are available.
The quadratic-or-worse dimension dependence previously seen as a one-point bottleneck is shown not to be an inherent property of the model.
The new algorithm provides a benchmark for subsequent one-point methods to match or beat.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the algorithm's construction hinges on a specific variance-reduction or smoothing technique, that technique may transfer to related settings such as stochastic nonconvex or constrained zeroth-order optimization, where the same quadratic gap appears.
A natural testable extension is to verify whether the linear dimension dependence persists under weaker assumptions than $L$-smoothness, such as merely Lipschitz convexity.
The result raises the possibility that other known gaps between one-point and two-point methods—for example in regret bounds of bandit convex optimization—can likewise be closed.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You asked what I make of arXiv:2508.12228. The headline: it claims to answer an actual open question - one-point feedback zeroth-order methods can match the linear dimension dependence of two-point methods for convex problems. That is a meaningful if true; existing one-point methods land quadratic or worse in dimension. The abstract states the question clearly and asserts an affirmative answer. Good. But we only have the abstract. So the honest summary is: interesting claim, no visible proof, and one specific red flag that needs checking. The red flag is assumptions. Standard one-point gradient estimators need L-smoothness to control bias from the smoothing radius. The abstract only says 'convex problems.' Two-point methods don't need smoothness for their dimension dependence. If the new algorithm needs smoothness, then it does not actually match two-point methods over the same problem class. That would be a weaker result than advertised. I'm not saying it's wrong; I'm saying the abstract omits the hypotheses that would tell us whether the match is real. The other issue is simply that we can't verify anything without the full text. No derivations, no theorem statement, no supplementary code. The reader's low-confidence, unverdictable take is the right one. There's no evidence of circularity from the abstract, but there is also no evidence of correctness beyond the claim itself. I do give credit where it's due: the question is genuinely open (as far as the abstract's characterization goes), the claimed rate is a clear improvement if proven, and the abstract is professionally written without overclaiming beyond the affirmative answer. The stress-test note's concern about smoothness is on point and should be the first thing a referee checks. For the practical question: if a full manuscript exists, it deserves peer review. The significance is high enough that referees should look at it, even if they expect heavy revision or find a fatal gap. For us, I'd wait for the full text before citing it; an abstract-level claim isn't enough to put in a reference list. But I'd take a look at the full version in a reading group if one shows up. Recommendation: put it through peer review if the authors have actually supplied the proof; desk rejection would be wrong for a claim of this importance. Set my own verdict as undetermined until I see the proof.

Referee Report

2 major / 3 minor

Summary. The manuscript, available here only as an abstract (arXiv:2508.12228), addresses the open question of whether one-point feedback zeroth-order optimization can achieve the same linear dimension dependence in sample complexity as two-point methods for convex problems. The abstract asserts an affirmative answer, claiming a one-point algorithm with a single noisy function evaluation per query achieves linear dimension dependence. No algorithm details, theorem statements, assumptions, or proofs are accessible in the submitted text.

Significance. If the construction and analysis are correct, the result would close a known gap in zeroth-order convex optimization and is of clear interest to the derivative-free optimization community. The claim is falsifiable and would be significant for settings where only one function evaluation per iteration is possible. However, because only the abstract is provided, no verification of the mathematical content is possible; the significance is therefore conditional on a full proof that cannot be assessed here. I explicitly credit the authors for posing a clear, high-impact question and for a concrete claimed answer, but the submission as provided does not contain the supporting evidence.

major comments (2)

[Abstract] The abstract states the result for 'convex problems' without specifying the regularity and noise assumptions. Standard one-point gradient surrogates require L-smoothness and bounded-variance unbiased noise to control bias-variance tradeoffs (e.g., bias O(Lδ) and variance O(d^2/δ^2)); balancing these to obtain linear dimension dependence imposes hypotheses stronger than plain convexity. If the theorem needs such assumptions, the claimed 'matching' to two-point methods is narrower than advertised. Please state the exact assumptions (smoothness, noise model, boundedness, etc.) and compare them with the hypotheses of the two-point lower/upper bounds in question.
[General] The submitted text is only an abstract; the algorithm, theorem statements, proofs, and any numerical experiments are missing. Consequently the central claim — that a one-point feedback algorithm can match the optimal linear dimension dependence of two-point methods — cannot be checked. This is not a claim of an error but a lack of assessable content. A full manuscript is required before the result can be evaluated.

minor comments (3)

[Abstract] Please define 'linear dimension dependence' precisely (e.g., O(d/ε^2) up to logarithmic factors) and specify the dependence on the accuracy ε and problem constants. The current phrase is ambiguous.
[Abstract] State explicitly whether the result covers both smooth and non-smooth convex objectives, or only one of these classes. This is relevant for comparing with two-point methods.
[Abstract] Clarify whether the 'answer' is a new upper bound, a matching lower bound, or both; the phrase 'match the optimal ... achieved by two-point methods' suggests an upper-bound result, but the formal status should be explicit.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity evident in abstract-only review; no load-bearing step reduces to its own input.

full rationale

The manuscript is available only at abstract level, so the derivation chain cannot be inspected. The abstract's claim is that a one-point feedback zeroth-order algorithm achieves linear dimension-dependent sample complexity, presented as an algorithmic construction with a complexity bound. There is no fitted parameter renamed as a prediction, no definitional equivalence between the input and output, and no load-bearing self-citation visible. A possible concern that the abstract omits smoothness or noise assumptions under which the bound holds is a correctness or scope issue, not a circularity issue. Under the hard rule that circularity must be exhibited by quoting the paper and showing a specific reduction, and absent any such evidence, the appropriate honest finding is no significant circularity.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

Since only the abstract is available, the formal assumptions are unknown. The two axioms listed are the minimum conditions implied by the abstract's description of the problem and the standard setting of one-point feedback zeroth-order optimization.

assumptions (2)

domain assumption The objective function is convex.
Abstract states the problem 'even for convex problems', so convexity is the function class assumed.
domain assumption The function evaluation is noisy but provides an unbiased estimate of the function value with bounded variance, as is standard for one-point feedback models.
Implied by 'single noisy function evaluation' and by the need for stochastic gradient estimation; not explicitly stated in the abstract.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Can a One-Point Feedback Zeroth-order Algorithm Achieve Linear Dimension Dependent Sample Complexity?." pith.science (2026). https://pith.science/paper/CCQJM2GJ

@misc{pith2026250812228,
  author       = {Pith},
  title        = {Pith review of: Can a One-Point Feedback Zeroth-order Algorithm Achieve Linear Dimension Dependent Sample Complexity?},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CCQJM2GJ}},
  note         = {Machine review of arXiv:2508.12228}
}

read the original abstract

We revisit the one-point feedback zeroth-order (ZO) optimization problem, a classical setting in derivative-free optimization where only a single noisy function evaluation is available per query. Compared to their two-point counterparts, existing one-point feedback ZO algorithms typically suffer from poor dimension dependence in their sample complexities -- often quadratic or worse -- even for convex problems. This gap has led to the open question of whether one-point feedback ZO algorithms can match the optimal \emph{linear} dimension dependence achieved by two-point methods. In this work, we answer this question \emph{affirmatively}.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Accelerating Evolutionary Strategy via Rao-Blackwellizing Realization of Uncertain Input
math.OC 2026-08 conditional novelty 5.0 of 10

Using the observed realized input (the phenotype) in Evolutionary Strategy gradient estimation is a Rao-Blackwellization that provably lowers estimator variance and speeds up convergence in Optimization under Input Un...

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.