Pith. sign in

REVIEW 5 minor 47 references

Near-Optimal Lower Bounds for Randomized Algorithms in Exact Value Zeroth-Order Convex Optimization

T0 review · 0 major / 5 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read This paper proves that exact scalar values, not just gradients, intrinsically make randomized convex optimization pay a factor of d in query count—up to logarithmic factors.

desk verdict A serious, important lower bound that closes the randomized exact-value gap; the proof is intricate and rests on a single technical estimate I could not fully verify. read the letter →

arxiv 2607.16558 v2 pith:WUXDSWSI submitted 2026-07-18 math.OC

Haihan Zhang , Chenheng Zhang , Zhiquan Qi , Zhouchen Lin This is my paper · ORCID
classification math.OC MSC 90C2568Q1790C56
keywords zeroth-orderoptimizationconvexlowerboundsoraclecomplexityrandomizedalgorithmsexactvalueaccessposteriormeanenergyrandomsupportfunctions
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 asks whether the extra dimension dependence paid by derivative-free methods is an unavoidable price of receiving only scalar function values rather than gradient vectors. The answer proposed is yes: for d-dimensional Lipschitz convex objectives over the Euclidean unit ball, every adaptive randomized algorithm that gets exact values needs at least c·d·min{d, ε^{-2}}/log(min{d, ε^{-2}}) queries to return an ε-suboptimal point with probability at least 1/2. This matches the best known exact-value upper bounds in both accuracy regimes: roughly d/ε² when ε is not too small, and roughly d² when ε ≤ d^{-1/2}. A sympathetic reader would therefore take the paper as establishing that the dimension penalty in zeroth-order methods is intrinsic to scalar feedback, not an artifact of the algorithms.

What carries the argument

The random support-function hard family f_Ξ(x) = max_i ⟨a_i,x⟩ with truncated-Gaussian hidden vectors, whose key identity is f_Ξ(x) ≥ (1/k)⟨s_Σ,x⟩; and the posterior mean energy method, whose core is the one-step selection bound (Theorem 14): for k independent 1-strongly log-concave blocks on affine supports, one adaptive maximum observation moves the posterior mean of their sum by at most C log(ek) in expected squared norm. This bound is iterated over the adaptive transcript to control how much information exact scalar values reveal.

What would settle it

Numerically compute the one-step posterior shift on the hard family: sample k independent standard Gaussians, observe a single maximum value and its maximizing index, and measure E||E[Σu_i | I,Y] − EΣu_i||². If this exceeds C·log(ek) for a universal constant C, Theorem 14—and the tight logarithmic factors in the main lower bound—would fail.

Watch

Extended reading notes

Core claim

The paper claims that exact scalar value access is intrinsically weaker than vector feedback by a full dimension factor d, up to logarithms. Its central object is a random hard family f_Ξ(x) = max_i ⟨a_i,x⟩ where the hidden vectors are independent truncated Gaussians scaled to norm at most 2; the aggregate direction s_Σ = Σ a_i links optimization error to posterior information. The main mechanism is a one-step selection bound: one observation of the maximum, together with the identity of the maximizer, moves the posterior mean of the sum of k strongly log-concave blocks by at most O(log(ek)) in expected squared norm. Iterating this bound through an adaptive transcript gives E||E[s_Σ|G_T]||²

Load-bearing premise

The proof's load-bearing estimate is the one-step selection bound: a single adaptive maximum observation of k independent 1-strongly log-concave blocks on affine supports moves the posterior mean of their sum by at most O(log(ek)) in expected squared norm; if that movement grows faster in k, the logarithmic factors in the main theorem break.

Editorial extensions

If this is right

  • Exact scalar value access carries an intrinsic dimension penalty: no randomized exact-value algorithm can beat the d·min{d, ε^{-2}} scale for Lipschitz convex optimization.
  • At high accuracy (ε ≤ d^{-1/2}), the query complexity saturates at Ω(d²/log d), independent of ε, matching the known d² upper bound up to logs.
  • At low accuracy (ε ≥ d^{-1/2}), the lower bound Ω(d/(ε² log(1/ε))) explains the dimension factor that earlier local-oracle lower bounds missed.
  • Combined with known upper bounds, the minimax oracle complexity for exact-value Lipschitz convex optimization is Θ̃(d·min{d, ε^{-2}}), pinning down the joint dependence on dimension and accuracy up to logarithmic factors.
  • The lower bound holds uniformly over the function class and against adaptive randomized algorithms with constant success probability, not just against deterministic ones.

Reading between the lines

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

  • Editorial inference: The same posterior-energy mechanism may transfer to other scalar oracles—such as sign comparisons or threshold queries—suggesting analogous dimension penalties in those models.
  • Editorial inference: The hard family is nonsmooth (max of linear functions), so the dimension penalty might behave differently for smooth convex functions; a natural next question is whether a smooth variant of the family preserves the same lower bound.
  • Editorial inference: The one-step selection bound hints at an information-theoretic rate of roughly k log(k)/d bits revealed per exact value query; testing this interpretation against finite-difference estimators could sharpen the constant at the transition ε ≍ d^{-1/2}.
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.

Referee Report

0 major / 5 minor

Summary. This paper establishes a near-optimal lower bound for adaptive randomized algorithms in exact-value zeroth-order Lipschitz convex optimization over the Euclidean unit ball. The main theorem (Theorem 6) states that T_eps >= c * d * min{d, eps^{-2}} / log(min{d, eps^{-2}}) for all d >= d0 and 0 < eps <= eps0, with universal constants, yielding Omega(d/(eps^2 log(eps^{-2}))) in the low-accuracy regime and Omega(d^2/log d) in the high-accuracy regime. The proof constructs a random hard family of support functions f_Xi(x) = max_i <a_i, x> with k random truncated Gaussian directions; with constant probability the optimum is of order -k^{-1/2}, and any near-optimal output must align with the aggregate direction. The information argument tracks the posterior mean of the aggregate under an augmented transcript that also reveals active indices; Theorem 14 bounds the one-step posterior-mean movement by O(log(ek)), Proposition 15 converts this into a cumulative energy bound, and Lemma 16 supplies a subgaussian residual tail. Yao's principle converts the distributional deterministic lower bound (Theorem 5) into the randomized worst-case bound. I read the proof chain in detail and did not find a load-bearing error.

Significance. If correct, this is a significant result: it closes the factor-d gap between previous randomized lower bounds and the known upper bounds for exact scalar-value convex optimization, and it is the first near-optimal lower bound that covers both accuracy regimes for arbitrary adaptive randomized algorithms. The rates match the two-point bound O(d eps^{-2}) and the value-only bound O(d^2 log d log(1/eps)) up to logarithmic factors. The paper also contributes a new proof technique: a posterior-mean energy method for adaptive max observations, with careful measure-theoretic disintegration and a one-step selection inequality. Strengths include the fixed hard distribution, the explicit use of Yao's principle, the detailed measurable posterior construction, and the honest separation of the numerical illustrations from the proof. The main residual risk is that the proof of Theorem 14 is long and intricate; I checked the main steps, but the closure through Gaussian smoothing and lower semicontinuity (Lemma 39) deserves independent scrutiny. This is a risk assessment, not a discovered error.

minor comments (5)
  1. [Lemma 9] The definition of gamma_opt should be displayed as (1/2)*sqrt(c_sv); the current typesetting 'gamma_opt := 1/2 sqrt(c_sv) = 1/4' is easy to misread as 1/(2*sqrt(c_sv)), which would make the norm calculation appear inconsistent. Please clarify the notation.
  2. [Section 6] Figure 1 is referenced but the actual figure panels are not embedded in the text I reviewed; ensure the final submission includes the figure with labeled axes. It may also help to state explicitly in the caption that the numerical illustrations are not part of the lower-bound proof and are included only to show the expected geometry and scaling.
  3. [Proof of Theorem 5] The quantity d_tail is defined as a real number (2 log 16)/eta^2 and then used in d0 = max{d_opt, d_tail}. Since d is an integer, this is harmless, but it would be cleaner to write d_tail = ceil(...) or to state that the inequality is used as a lower threshold on d.
  4. [Lemma 13] The sentence 'The definition ignores the final recorded query coordinate on transcripts that are inconsistent with the fixed algorithm' is confusing. Clarify that the posterior kernel is defined on all transcript values, while the geometric identification is claimed only on the full-measure set X_t^post, where the query coordinate agrees with chi_t.
  5. [General] There are numerous typographical artifacts, especially broken Greek letters and diacritics (e.g., 'Prékopa'), and some equations are rendered with unusual spacing. A careful proofread would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: lower bound derived from an explicit random hard distribution via Yao's principle and internal energy estimates.

full rationale

The central lower bound is self-contained against external benchmarks. Theorem 6 is obtained by a distributional deterministic-algorithm lower bound (Theorem 5) against the explicitly defined random support-function family f_Ξ(x)=max_i⟨â_i,x⟩, then converted to the randomized worst-case statement by the standard fixed-budget Yao principle (Proposition 2). The proof of Theorem 5 uses only the negative-optimum spectral event (Lemma 9/Theorem 40), the augmented posterior energy bound (Proposition 15), and the conditional subgaussian residual tail (Lemma 16). Proposition 15 applies Theorem 14, whose proof is internal: the smooth case is proven from scratch using Prékopa's theorem, Brascamp–Lieb, Mills-ratio/quantile lemmas, and a no-spike lemma, while the affine-support case is closed by Gaussian smoothing and Lemma 39; the cited external results do not contain the target lower bound. No upper bound is used in the derivation—the paper explicitly states that the upper bounds are 'Neither result is used in the lower bound proof' (Section 3.4). The construction parameter k=⌊a0 min{d,ε^{-2}}⌋ in the proof of Theorem 6 is an optimization parameter locating the desired accuracy scale; it is not fitted to the claimed rate and the bound is monotone in the chosen scale. There is no load-bearing self-citation: the authors' own prior papers appear only in general related-work contexts, and the concurrent deterministic result of Kerger (2026) is explicitly not used as an input. Numerical illustrations are explicitly described as not establishing the lower bound. The one-step selection bound (Theorem 14) is the least externally verifiable step, but that is a correctness risk, not circularity.

Assumptions & free parameters 1 free parameters · 6 assumptions · 0 invented entities

The argument is a purely mathematical proof. The only construction parameter is the hard-family size k, which is disclosed and tuned to the accuracy scale, not fit to data. The proof relies on standard external inequalities from convex analysis and probability, plus the explicit augmented-transcript device, which is an analytic abstraction rather than a new physical entity.

free parameters (1)
  • instance parameter k (number of linear pieces) = k = floor(a0 * min{d, ε^{-2}}) for a universal constant a0 > 0
    Chosen by hand to set the accuracy scale of the hard family and to keep k ≤ c_dim d. It is a proof construction parameter, not a constant fitted to external data, and it disappears from the final bound.
assumptions (6)
  • standard math Prékopa's theorem: marginals of jointly log-concave functions are log-concave
    Used in Lemmas 33, 34, and 36 to justify log-concavity and Hessian bounds after Gaussian smoothing.
  • standard math Brascamp–Lieb variance inequality for strongly log-concave measures
    Used in Lemma 35 to obtain subgaussian exponential moments for linear functionals.
  • standard math Otto–Villani / Talagrand T2 inequality for 1-strongly log-concave measures
    Used in Lemma 21 to bound lower-tail conditional barycenters through KL divergence.
  • standard math Gaussian smallest singular value concentration
    Used in Theorem 40 to ensure the random linear pieces are separated, giving the negative-optimum event in Lemma 9.
  • standard math Gaussian norm concentration
    Used in Theorem 40 to pass from unconditioned Gaussian rows to the truncated Gaussian construction.
  • standard math Yao's minimax principle in fixed-budget form
    Used in Proposition 2 to lift the distributional deterministic lower bound to randomized algorithms.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Near-Optimal Lower Bounds for Randomized Algorithms in Exact Value Zeroth-Order Convex Optimization." pith.science (2026). https://pith.science/paper/WUXDSWSI

@misc{pith2026260716558,
  author       = {Pith},
  title        = {Pith review of: Near-Optimal Lower Bounds for Randomized Algorithms in Exact Value Zeroth-Order Convex Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WUXDSWSI}},
  note         = {Machine review of arXiv:2607.16558}
}
abstract

Whether exact scalar feedback intrinsically incurs the additional dimension $d$ paid by known zeroth-order methods remains open even for Lipschitz convex optimization. For a universal Lipschitz scale, the value only bound $O(d^2\log(d+1)\log(1/\epsilon))$ and two-point bound $O(d\epsilon^{-2})$ yield the upper bound $\widetilde O\left(d\min\{d,\epsilon^{-2}\}\right)$. By contrast, prior lower bounds for arbitrary randomized algorithms give only $\Omega(\min\{d,\epsilon^{-2}\})$, leaving a factor $d$ unexplained. We close this gap, up to logarithmic factors, for arbitrary adaptive randomized algorithms minimizing a convex objective with a universal Lipschitz scale over the $d$-dimensional Euclidean unit ball, where each query returns only the exact scalar value. Let $T_\epsilon$ denote the minimum number of queries required to return an $\epsilon$-suboptimal point with probability at least $1/2$, uniformly over the function class. We prove that \[T_\epsilon\ge c\,\frac{d\min\{d,\epsilon^{-2}\}}{\log\!\bigl(\min\{d,\epsilon^{-2}\}\bigr)},\] for $d\ge d_0$ and $0<\epsilon\le\epsilon_0$, where $c,\epsilon_0>0$ and $d_0\in\mathbb N$ are universal constants. This gives $\Omega\left(\frac{d}{\epsilon^2\log(1/\epsilon)}\right)$ in the low-accuracy regime $\epsilon\ge d^{-1/2}$ and $\Omega\left(\frac{d^2}{\log d}\right)$ in the high-accuracy regime $\epsilon\le d^{-1/2}$ with the latter independent of $\epsilon$. These bounds match the corresponding upper bound up to logarithmic factors. To our knowledge, this is the first near-optimal lower bound for arbitrary adaptive randomized algorithms throughout both accuracy regimes of exact value Lipschitz convex optimization. The proof uses a random support function hard family and develops a posterior mean energy method for adaptive exact max observations, in place of first-order zero chain constructions and noise based transcript inequalities.

Figures

Figures reproduced from arXiv: 2607.16558 by the authors.

Figure 1
Figure 1. Numerical illustrations on the ran￾dom support function hard family. (a) The nor￾malized optimum scale − √ kf ⋆ A˘ remains of con￾stant order over the tested values of k, support￾ing the scale f ⋆ A˘ ≍ −k −1/2 . (b) With d fixed and ϵ −2 increasing, the observed complexity initially follows the dϵ−2 scale. Around the d 2 scale, the coordinate finite-difference analytic-center cutting-plane implementation, denoted Co… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

47 extracted references · 1 linked inside Pith

  1. [1]

    Foundations of Computational Mathematics , volume=

    Random Gradient-Free Minimization of Convex Functions , author=. Foundations of Computational Mathematics , volume=. 2017 , publisher=

    2017

  2. [2]

    Conference on Learning Theory , year =

    Efficient Convex Optimization with Membership Oracles , author =. Conference on Learning Theory , year =

  3. [3]

    2009 , publisher=

    Introduction to derivative-free optimization , author=. 2009 , publisher=

    2009

  4. [4]

    Automation and Remote Control , volume=

    Random Optimization , author=. Automation and Remote Control , volume=

  5. [5]

    Black-box optimization of noisy functions with unknown smoothness , year =

    Grill, Jean-Bastien and Valko, Michal and Munos, Remi and Munos, Remi , booktitle =. Black-box optimization of noisy functions with unknown smoothness , year =

  6. [6]

    Chen, Xiangyi and Liu, Sijia and Xu, Kaidi and Li, Xingguo and Lin, Xue and Hong, Mingyi and Cox, David , booktitle=. Z

  7. [7]

    Journal of Machine Learning Research , volume=

    An optimal algorithm for bandit and zero-order convex optimization with two-point feedback , author=. Journal of Machine Learning Research , volume=

  8. [8]

    Journal of the ACM (JACM) , volume=

    Kernel-based methods for bandit convex optimization , author=. Journal of the ACM (JACM) , volume=. 2021 , publisher=

    2021

Show all 47 references
  1. [9]

    Chen, Pin-Yu and Zhang, Huan and Sharma, Yash and Yi, Jinfeng and Hsieh, Cho-Jui , booktitle=

  2. [10]

    Hessian-Aware Zeroth-Order Optimization , year=

    Ye, Haishan and Huang, Zhichao and Fang, Cong and Li, Chris Junchi and Zhang, Tong , journal=. Hessian-Aware Zeroth-Order Optimization , year=

  3. [11]

    International Conference on Machine Learning , year=

    Structured evolution with compact architectures for scalable policy optimization , author=. International Conference on Machine Learning , year=

  4. [12]

    Clip-tuning:

    Chai, Yekun and Wang, Shuohuan and Sun, Yu and Tian, Hao and Wu, Hua and Wang, Haifeng , booktitle=. Clip-tuning:

  5. [13]

    Neural Information Processing Systems , year=

    Fine-tuning language models with just forward passes , author=. Neural Information Processing Systems , year=

  6. [14]

    Elasticzo:

    Sugiura, Keisuke and Matsutani, Hiroki , journal=. Elasticzo:

  7. [15]

    Lee and Wotao Yin and Mingyi Hong and Zhangyang Wang and Sijia Liu and Tianlong Chen , booktitle=

    Yihua Zhang and Pingzhi Li and Junyuan Hong and Jiaxiang Li and Yimeng Zhang and Wenqing Zheng and Pin-Yu Chen and Jason D. Lee and Wotao Yin and Mingyi Hong and Zhangyang Wang and Sijia Liu and Tianlong Chen , booktitle=. Revisiting Zeroth-Order Optimization for Memory-Efficient

  8. [16]

    Keyes and Di Wang , booktitle=

    Liangyu Wang and Jie Ren and Hang Xu and Junxiao Wang and Huanyi Xie and David E. Keyes and Di Wang , booktitle=. Scalable Zeroth-Order Fine-Tuning for Extremely Large Language Models with Limited

  9. [17]

    Optimal rates for zero-order convex optimization:

    Duchi, John C and Jordan, Michael I and Wainwright, Martin J and Wibisono, Andre , journal=. Optimal rates for zero-order convex optimization:. 2015 , publisher=

    2015

  10. [18]

    SIAM Journal on Optimization , volume=

    Stochastic first-and zeroth-order methods for nonconvex stochastic programming , author=. SIAM Journal on Optimization , volume=. 2013 , publisher=

    2013

  11. [19]

    2018 , publisher=

    Lectures on Convex Optimization , author=. 2018 , publisher=

    2018

  12. [20]

    Journal of Machine Learning Research , volume=

    An algorithm with optimal dimension-dependence for zero-order nonsmooth nonconvex stochastic optimization , author=. Journal of Machine Learning Research , volume=

  13. [21]

    Journal of Machine Learning Research , year =

    Ohad Shamir , title =. Journal of Machine Learning Research , year =

  14. [22]

    Lower bounds for finding stationary points

    Carmon, Yair and Duchi, John C and Hinder, Oliver and Sidford, Aaron , journal=. Lower bounds for finding stationary points. 2020 , publisher=

    2020

  15. [23]

    and Hinder, Oliver and Sidford, Aaron , title =

    Carmon, Yair and Duchi, John C. and Hinder, Oliver and Sidford, Aaron , title =. Mathematical Programming , pages =. 2021 , publisher =

    2021

  16. [24]

    arXiv preprint arXiv:1709.03594 , year=

    Lower bound for randomized first order convex optimization , author=. arXiv preprint arXiv:1709.03594 , year=

    arXiv

  17. [25]

    Finite Sample Convergence Rates of Zero-Order Stochastic Optimization Methods , year =

    Wibisono, Andre and Wainwright, Martin J and Jordan, Michael and Duchi, John , booktitle =. Finite Sample Convergence Rates of Zero-Order Stochastic Optimization Methods , year =

  18. [26]

    Neural Information Processing Systems , year=

    Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization , author=. Neural Information Processing Systems , year=

  19. [27]

    SIAM Journal on Optimization , volume=

    Efficiency of coordinate descent methods on huge-scale optimization problems , author=. SIAM Journal on Optimization , volume=. 2012 , publisher=

    2012

  20. [28]

    Convex optimization:

    Bubeck, S. Convex optimization:. Foundations and Trends in Machine Learning , volume=. 2015 , publisher=

    2015

  21. [29]

    International Conference on Machine Learning , year=

    Faster gradient-free algorithms for nonsmooth nonconvex stochastic optimization , author=. International Conference on Machine Learning , year=

  22. [30]

    Neural Information Processing Systems , year=

    Tight complexity bounds for optimizing composite objectives , author=. Neural Information Processing Systems , year=

  23. [31]

    On the complexity of finite-sum smooth optimization under the

    Bai, Yunyan and Liu, Yuxing and Luo, Luo , booktitle=. On the complexity of finite-sum smooth optimization under the

  24. [32]

    On the lower bound of minimizing

    Yue, Pengyun and Fang, Cong and Lin, Zhouchen , booktitle=. On the lower bound of minimizing. 2023 , organization=

    2023

  25. [33]

    Mathematical Programming , volume=

    Oracle complexity of second-order methods for smooth convex optimization , author=. Mathematical Programming , volume=. 2019 , publisher=

    2019

  26. [34]

    Mathematical Programming , volume=

    Lower bounds for non-convex stochastic optimization , author=. Mathematical Programming , volume=. 2023 , publisher=

    2023

  27. [35]

    Second-order information in non-convex stochastic optimization:

    Arjevani, Yossi and Carmon, Yair and Duchi, John C and Foster, Dylan J and Sekhari, Ayush and Sridharan, Karthik , booktitle=. Second-order information in non-convex stochastic optimization:

  28. [36]

    Fang, Cong and Li, Chris Junchi and Lin, Zhouchen and Zhang, Tong , booktitle=

  29. [37]

    Acta Sci

    On logarithmic concave measures and functions , author=. Acta Sci. Math. , volume=

  30. [38]

    On extensions of the

    Brascamp, Herm Jan and Lieb, Elliott H , journal=. On extensions of the. 1976 , publisher=

    1976

  31. [39]

    Transportation cost for

    Talagrand, Michel , journal=. Transportation cost for. 1996 , publisher=

    1996

  32. [40]

    Vershynin, Roman , title =

  33. [41]

    Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory , year=

    Braun, Gábor and Guzmán, Cristóbal and Pokutta, Sebastian , journal=. Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory , year=

  34. [42]

    Corrections to “

    Braun, Gábor and Guzmán, Cristóbal and Pokutta, Sebastian , journal=. Corrections to “. 2024 , volume=

    2024

  35. [43]

    2017 , publisher=

    Random measures, theory and applications , author=. 2017 , publisher=

    2017

  36. [44]

    Probabilistic computations:

    Yao, Andrew Chi-Chin , booktitle=. Probabilistic computations:. 1977 , organization=

    1977

  37. [45]

    Generalization of an inequality by

    Otto, Felix and Villani, C. Generalization of an inequality by. Journal of Functional Analysis , volume=. 2000 , publisher=

    2000

  38. [46]

    Mathematical Notes , volume=

    Algorithms for approximate calculation of the minimum of a convex function from its values , author=. Mathematical Notes , volume=. 1996 , publisher=

    1996

  39. [47]

    Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization:

    Kerger, Phillip , journal=. Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization:

Pith tools

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