{"id":"b23331ea-945c-437b-af7e-249dc6b3fb61","arxiv_id":"2607.16558","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Any randomized adaptive exact-value algorithm needs Ω(d min{d, ε^{-2}} / log(min{d, ε^{-2}})) queries for ε-optimal Lipschitz convex optimization, matching upper bounds up to log factors.","lead":"This paper proves that randomized algorithms which only see exact function values must pay a dimension penalty: at least about d²/log d queries in high accuracy and d/(ε² log(1/ε)) in low accuracy for Lipschitz convex optimization. It closes a long-standing factor-d gap between known upper and lower bounds for exact zeroth-order convex optimization.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The paper's central claim is the near-optimal randomized lower bound for exact-value zeroth-order convex optimization. The proof's most delicate and least independently checkable component is Theorem 14, the one-step selection bound, which the reader also identified. I focused my stress-test there. The smooth full-dimensional case is supported by a coherent chain: Lemma 18 handles the max-selection tail structure via the probability integral transform; Theorem 19 and Lemma 21 control winner-slice and loser-tail barycenters using strong log-concavity and the no-spike lemma; and Proposition 17 combines these with the product posterior structure. The closure to affine supports and nonsmooth laws is handled by Gaussian smoothing (Lemma 36) plus lower semicontinuity of conditional-mean energy (Lemma 39). I checked the key limit step: if u_n->u in L2 and W_n->W a.s., then for every bounded continuous phi, E< u_n-E u_n, phi(W_n)> -> E< u-E u, phi(W)> and E|phi(W_n)|^2 -> E|phi(W)|^2, so the variational characterization yields the needed liminf inequality. No circularity or missing integrability surfaced. The application of Theorem 14 to adaptive queries is valid because each conditional block law is a product of 1-strongly log-concave measures on affine supports, and the query direction is deterministic conditionally on the past transcript. The subsequent martingale orthogonality, energy bound, conditional subgaussian residual tail, and Yao reduction all scale correctly. I therefore found no concrete defect. The only honest concern is that Theorem 14, despite being well-motivated, is not machine-checked; a targeted numerical verification of the one-step bound would increase confidence further, but the absence of that verification does not by itself undermine the verdict.","tokens_in":56386,"tokens_out":23553,"duration_ms":249610,"concrete_test":"Monte-Carlo check of Theorem 14: for d=200, k in {16,64,256,1024}, sample independent N(0,I_d) blocks (and a variant with one block restricted to a random 1-D affine subspace), fix v=e1, and compute the empirical expected squared posterior-mean shift E|E[s|I,Y]-E s|^2 over 10^5 draws. Verify it is bounded by C log(ek) with a universal constant C<100 and that the bound does not grow with d. This directly tests the estimate all later arguments rely on.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I read the central argument in good faith and could not identify a concrete load-bearing failure. The result genuinely hinges on Theorem 14's O(log(ek)) one-step selection bound, and the reader is right that this is the least externally verifiable step: it combines Gaussian smoothing, deterministic priority tie-breaking, and lower-semicontinuity (Lemma 39). I checked the algebraic chain: Proposition 17's winner-slice and loser-tail estimates are consistent with Lemma 18's probability-integral-transform bound; the closure from smooth bounded-Hessian laws to affine-support strongly log-concave laws via Lemma 36 and Lemma 39 is logically coherent; and the scaling into Proposition 15, Theorem 5, and Theorem 6 is consistent. The proof is intricate and not machine-checked, so residual risk exists, but no specific false step or missing assumption surfaced. This is an honest non-finding.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":56584,"tokens_out":22034,"duration_ms":238576,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Lemma 9"},{"comment":"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.","section":"Section 6"},{"comment":"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.","section":"Proof of Theorem 5"},{"comment":"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.","section":"Lemma 13"},{"comment":"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.","section":"General"}],"recommendation":"accept","confidential_remarks":"The manuscript is within scope for math.OC and the central claim is credible. I did not find a specific false step. My only caveat for the editor is the standard one for long analytic proofs: Theorem 14 and its Gaussian-smoothing/lower-semicontinuity closure are intricate and not machine-checked. If the journal can arrange an additional independent check of Section 5.2, that would increase confidence. I recommend acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's what you should know: this paper claims the first near-optimal lower bound for arbitrary adaptive randomized algorithms in exact-value zeroth-order convex optimization. The bound is T_epsilon ≥ c d min{d, ε^{-2}} / log(min{d, ε^{-2}}), matching the known upper bounds up to log factors in both the low-accuracy regime (d/ε²) and the high-accuracy regime (d²). If correct, it closes the factor-d gap left by Braun et al. and extends the concurrent deterministic result of Kerger to randomized algorithms and to both regimes.\n\nWhat's genuinely new: the random support-function hard family and the posterior-mean energy method. The construction is clean: with constant probability the optimum of f_Ξ is ~ -1/√k, and every point satisfies f_Ξ(x) ≥ (1/k)⟨s_sc, x⟩. So any ε-optimal output must substantially align with the hidden aggregate direction. The information analysis then shows that T exact scalar queries move the posterior mean of s_sc by at most O(T log k / d) in squared norm, and that the residual is subgaussian. The Yao reduction is textbook. The paper is honest that the numerical section is illustrative.\n\nThe soft spot is Theorem 14, the one-step selection bound. It states that one adaptive max observation moves the posterior mean of the sum of k independent 1-strongly log-concave blocks on affine supports by at most O(log(ek)) in expected squared norm. That single estimate powers the energy bound; if it fails, the log factors break. The proof goes through smooth bounded-Hessian approximations, Gaussian smoothing, deterministic tie-breaking perturbations, and a lower-semicontinuity step. I could not machine-verify every estimate, and neither, in effect, did the stress-test — it found no specific false step, which is an honest non-finding. But this is where I'd send a referee. The rest of the architecture is transparent and the dependence on standard tools (Prékopa, Brascamp–Lieb, Talagrand T2) checks out.\n\nNo circularity: the lower bound is derived against an explicit hard distribution and converted to worst-case via Yao; it never invokes the upper bounds it matches. The only tuned parameter is k, set to a constant multiple of min{d, ε^{-2}}.\n\nWho this is for: anyone working on oracle complexity or zeroth-order optimization. The proof is long, but the main theorem and the proof sketch in Section 5 are accessible. I'd bring it to reading group and I'd cite it. It deserves a serious referee: the result is important enough that the referee time is justified, and the risk is concentrated in one technical estimate that a careful referee can check.\n\nRecommendation: send it to peer review, with explicit instruction to scrutinize Theorem 14 and the smoothing closure. If it holds up, it's a major advance; if it fails there, it's still a framework worth publishing.","headline":"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.","tokens_in":57028,"tokens_out":2920,"would_cite":true,"duration_ms":31715,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","68Q17","90C56"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["zeroth-order optimization","convex optimization","lower bounds","oracle complexity","randomized algorithms","exact value access","posterior mean energy","random support functions"],"falsifier":"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.","tokens_in":56306,"feed_emoji":"🎯","tokens_out":4457,"duration_ms":49860,"temperature":0.7,"pith_summary":"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.","feed_headline":"Exact-value queries cost convex optimization a factor of d","feed_subtitle":"Proved lower bound matches known upper bounds up to logs for randomized algorithms in both low- and high-accuracy regimes.","key_machinery":"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.","core_discovery":"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]||²","pith_inferences":["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}."],"forward_implications":["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."],"fun_headline_variants":["Exact-value queries force d factor in convex optimization lower bound","Proved: exact scalar feedback costs a full d factor in convex opt","Exact values make zeroth-order convex optimization d times harder","Near-optimal lower bound proves exact values cost a d factor","Exact-value oracle: closing the d gap in zeroth-order convex optimization"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Exact-value queries force d factor in convex optimization lower bound","Proved: exact scalar feedback costs a full d factor in convex opt","Exact values make zeroth-order convex optimization d times harder","Near-optimal lower bound proves exact values cost a d factor","Exact-value oracle: closing the d gap in zeroth-order convex optimization"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000806,"raw_usage":{"total_tokens":3486,"prompt_tokens":967,"completion_tokens":2519,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":711,"completion_tokens_details":{"reasoning_tokens":2428}},"tokens_in":711,"tokens_out":2519,"duration_ms":17100,"temperature":1.0,"reasoning_tokens":2428,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T20:34:47.111703+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}