{"id":"707c89b9-58d0-4aca-8241-5d96acb3c93a","arxiv_id":"2607.13335","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"partial","parameter_count":4,"one_line_summary":"Deterministic derivative-free convex optimization needs Ω(d²/log d) exact-value queries at accuracy Θ(d^{-1/2}), matching Protasov's 1996 upper bound up to log factors.","lead":"This paper shows that when an optimizer can only ask for function values, reaching d^{-1/2} accuracy on a d-dimensional convex problem requires on the order of d² evaluations—matching the best known method up to log factors. The result closes a question open since 1996 and extends to mixed-integer problems, where each integer variable also multiplies the cost by 2.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the central continuous lower bound is internally consistent; only presentational caveats remain.","rationale":"The reader's weakest-assumption concern about Proposition 10 is reasonable as a stress point, but a detailed check shows the adversary's update rule provably limits per-query damage to one dimension reduction plus ≤α-volume truncations for all other rows; no exact value can encode enough information to destroy a constant fraction of many rows at once. The aggregate-width step then goes through. Therefore I do not share the reader's suspicion that this is where the proof would collapse. I do agree that the paper has two real presentational gaps: the Lean formal-verification claim is scoped to the d⁻³ version, not the headline d⁻¹/² result, and the mixed-integer corollary rests on an un-reproduced transfer theorem. Both are worth fixing but neither affects the internal validity of Theorem 4. Hence I recommend keeping the reader's CONDITIONAL verdict rather than upgrading to ACCEPT or downgrading to REJECT.","tokens_in":21048,"tokens_out":30960,"duration_ms":293908,"concrete_test":"Independently re-derive the normalized-volume product from Proposition 10, tracking row dimensions: after s informative and T−s noninformative updates, verify that the τ-powers cancel exactly and the product lower bound is (3/4)^T (1/(8m^{3/2}))^s, and that this yields Σ_i D_i ≤ 4T log(em). If the exponent of m differs, the Di budget in (28) and Lemma 12 collapse, and the proof would need repair.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After a careful pass over the proof of Theorem 4, I could not identify a load-bearing mathematical flaw. The reader's weakest assumption targets Proposition 10's per-query tradeoff: a single exact value might in principle destroy a constant fraction of the volume of many row uncertainty sets simultaneously, which would break Lemma 13. This concern does not land. In the adversarial update, the response y is the maximum of the row values. One row (the selected nonconstant row attaining the global quantile r) is cut by the hyperplane {ℓ_i = y}, a codimension-one reduction; every other row is truncated only by {ℓ_j ≤ y}, and because y ≥ r_j, the removed cap {ℓ_j > y} is a subset of the α-quantile cap {ℓ_j ≥ r_j}, whose volume is exactly α = 1/(4m) of that row's intrinsic volume. Thus no query can remove more than a 1/(4m) fraction of volume from any unselected row, and only one row loses a dimension. The volume budget (25)–(28) is consistent: the τ-powers cancel after normalizing by κ_{k_i}τ^{k_i}, and each informative update contributes a factor 1/(8m^{3/2}) to the product of normalized volumes, yielding a total log-loss O(T log m), which is within budget when T = O(m²/log m). The aggregate-width argument (Lemma 13) and the barycentric separation (Lemma 14) are valid; the final gap computation is arithmetically correct. The genuine caveats are presentational, not mathematical: §1.4's formal-verification claim is stronger than Appendix A's disclosure (Lean covers only the d⁻³ accuracy version, not the headline d⁻¹/² theorem), and Corollary 2 depends on the self-cited transfer theorem [15, Thm 7], whose hypotheses (e.g., independence of ρ and M from d) are not fully verified. These support keeping the CONDITIONAL verdict, but they do not threaten the central continuous lower bound.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies deterministic query complexity of minimizing a convex 1-Lipschitz function over the Euclidean ball using only exact function values. Theorem 4 gives a lower bound of Ω(d²/log d) at accuracy ε₀/√d, matching Protasov's upper bound O(d² log² d) up to logarithmic factors and thereby closing a gap dating back to 1996. The proof constructs a max-of-linear hard family f_W(x,z)=max_i{a x_i+⟨w_i,z⟩}, an adversary that maintains a Cartesian product of row uncertainty sets, and a per-query tradeoff: each informative query reduces one row's dimension and removes at most α=1/(4m) of the intrinsic volume from every other row. A volume/dimension budget shows that after O(m²/log m) queries many rows remain high-dimensional with large normalized volume; Urysohn's inequality yields a common wide direction; and taking opposite extremes in that direction produces two transcript-consistent functions whose minimizers are separated by a constant. Corollary 2 lifts the result to mixed-integer convex optimization via a published transfer theorem, giving Θ~(2ⁿ d²) complexity.","tokens_in":44,"tokens_out":25134,"duration_ms":654667,"significance":"If the proof is read with the norm-scale correction noted below, this is a substantial contribution. It establishes the first polynomial separation between deterministic exact-value and full first-order oracles on nonsmooth convex functions, and it settles the dimension dependence in the value-only model at d^{-1/2} accuracy up to logarithms. The adversary argument is self-contained and transparent, and it carefully avoids assigning finite bit content to exact real answers. The Lean formalization of the initial d^{-3}-accuracy lower bound is a useful partial machine check, though it does not cover the main d^{-1/2} refinement. I also verified the per-query tradeoff that was flagged as the weakest assumption: unselected rows are truncated only by caps above their own α-quantile, so no single exact value can destroy a constant fraction of many rows simultaneously. The main mathematical structure is sound; the issues are concentrated in a repeated normalization typo and an overstrong formal-verification claim.","major_comments":[{"comment":"There is a norm-scale inconsistency in a load-bearing step. Lemma 8's proof establishes a/√m ≤ ||p_W||₂ ≤ (a/√m)√(1+Γ^{-2}), but Eq. (11), the definition of r₀ in Lemma 14, and Eq. (38) all print r₀ = a√m. With the printed value, τ/(5r₀) = 1/(5Γm), so the RHS of the Lemma 14 display is not a positive constant and the claimed separation ||p̂₊−p̂₋||₂ > 1/600 does not follow for large m. Replacing r₀ by a/√m gives τ/(5r₀) = 1/(5Γ), and the stated inequality is valid. Because Lemma 14 provides the constant minimizer separation used in the final gap computation, this correction is load-bearing and must appear in the published version.","section":"§3.4, Lemma 14; Eq. (11); Eq. (38)"}],"minor_comments":[{"comment":"The statement that the paper provides 'formal verification of the proof of the Ω~(d²) lower bound' is stronger than what Appendix A discloses: the Lean development covers the initial d^{-3}-accuracy construction, not the d^{-1/2} refinement that is the main theorem. Please qualify the §1.4 claim to match Appendix A.","section":"§1.4 / Appendix A"},{"comment":"After the norm-scale correction, r₀ should be consistently written as a/√m. The repeated appearance of 'a√m' in (11), Lemma 14, and (38) is likely a copy-paste error, but as printed it prevents a reader from verifying the central separation argument.","section":"§3.1, §3.4"},{"comment":"The proof of Corollary 2 says 'one exact query to f_W simulates one exact query to g_W'. This is correct, but it may be worth spelling out that the simulation also requires knowing r = max{1, ||q||₂}, which is available to the algorithm from the query point alone.","section":"§4"}],"recommendation":"major_revision","confidential_remarks":"The three occurrences of 'a√m' suggest a systematic typo rather than a conceptual gap; the proof of Lemma 8 and the final numerical constants are consistent with the corrected scale a/√m. The formal-verification statement in §1.4 should be aligned with the Appendix. I would be willing to accept after the authors correct the normalization and carefully re-check the constants in Lemma 14 and in the mixed-integer lift."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline result is real: this paper closes the oracle-complexity gap for deterministic exact-value minimization on nonsmooth convex functions, giving Ω(d²/log d) at ε = 10⁻⁷/√d and matching Protasov's upper bound up to log factors. That is a genuine polynomial separation between value-only and full first-order oracles, and I don't think there's a load-bearing flaw in the continuous lower bound.\n\nThe hard family (max of d/2 linear functions), the Cartesian-product uncertainty invariant, and the aggregate-width plus barycentric-separation argument are all new and well constructed. I checked the adversary's per-query tradeoff carefully, since it's the load-bearing step: a single exact value can cut at most one row down by a dimension, and every other row loses only its upper 1/(4m)-quantile cap. That is exactly what Proposition 10 claims, and the volume accounting in (25)–(28) is consistent. Lemma 13 and Lemma 14 hold up. The stress-test concern about one value destroying many rows simultaneously does not land.\n\nThe soft spots are presentational, not mathematical. First, §1.4 says the proof is formally verified in Lean, but Appendix A correctly discloses that this only covers the earlier d⁻³-accuracy version, not the headline d⁻¹/² theorem. The main theorem is not machine-checked. That's fine, but the opening section should not oversell it. Second, Corollary 2 leans on the self-cited transfer theorem [15, Thm 7]. The result is published, but the application does not verify every hypothesis—specifically whether the Lipschitz parameter M can depend on d. That needs a careful check before the mixed-integer claim is accepted at face value. Third, in §4 the sentence about the Lipschitz constant of g_W is compressed: the conclusion (g_W is 1-Lipschitz) is correct once you account for the 1/2 factor, but the derivation as written skips a step.\n\nThis paper is for anyone working on information-based complexity, oracle complexity, or derivative-free optimization. The proof is intricate and deserves a serious referee who can spend time on the adversary argument. I'm skeptical by default of AI-assisted proofs, but here the human verification seems real: the details are explicit, the constants check out, and the transfer theorem is cited rather than re-proved. I'd bring it to my reading group, and I'd cite it if I write on zeroth-order complexity.\n\nRecommendation: send it to peer review. The referee should focus on the mixed-integer transfer theorem's hypotheses and on making the scope of the Lean verification precise in the final version.","headline":"A credible near-quadratic lower bound for deterministic exact-value convex optimization that closes a gap from 1996; the central proof looks sound and deserves full refereeing.","tokens_in":22022,"tokens_out":2591,"would_cite":true,"duration_ms":28640,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C60"],"pacs":[],"model":"deepseek-v4-flash","headline":"Minimizing a convex function from exact values alone requires ~d^2 evaluations, closing a 30-year gap with gradient queries.","keywords":["zeroth-order oracle","convex optimization","oracle complexity","nonsmooth optimization","lower bound","exact function values","mixed-integer convex optimization","derivative-free optimization"],"falsifier":"Construct a deterministic value-only algorithm for the max-affine family of Section 3 that reaches error 10^{-7}/√d in o(d^2/log d) queries, or exhibit a single admissible query whose exact response on some transcript leaves a constant fraction of several row uncertainty sets' intrinsic volume eliminated — either would break the key per-query tradeoff (Proposition 10) and invalidate the lower bound.","tokens_in":20869,"feed_emoji":"🎯","tokens_out":5898,"duration_ms":55312,"temperature":0.7,"pith_summary":"This paper settles a long-standing question in deterministic derivative-free convex optimization: how many exact function evaluations are needed to minimize a convex, 1-Lipschitz function over the unit ball to accuracy Θ(d^{-1/2})? The answer is Θ~(d^2), up to logarithmic factors. This closes the gap between the old Ω(d) lower bound and the O(d^2 log^2 d) upper bound from 1996. The proof introduces an adversarial oracle that maintains a Cartesian product of uncertainty sets for the rows of a max-affine hard family, showing that after T queries many rows retain enough volume. It also lifts the bound to mixed-integer convex optimization, giving Θ~(2^n d^2) for n binary variables and d continuous ones.","feed_headline":"Exact values alone force ~d^2 queries in convex optimization","feed_subtitle":"Near-quadratic lower bound closes the gap with gradient oracles and extends to mixed-integer problems.","key_machinery":"The load-bearing mechanism is the exact resisting oracle built from a Cartesian product invariant. The adversary maintains compact convex uncertainty sets P_i ⊆ τB^m for each row of the max-affine objective; every selection of one vector from each set reproduces the entire exact transcript. A query is answered by a quantile level that either reduces one row's dimension by one (informative update) or truncates all rows by halfspaces removing at most a 1/(4m) fraction of their intrinsic volume (noninformative update). This limits total damage after T queries to s ≤ T dimension reductions and log-volume loss O(T log m), so up to T = Θ(m^2/log m) many rows retain both high dimension and volume r","core_discovery":"The central claim is Theorem 4: for every sufficiently large dimension d, any deterministic algorithm using only exact function values needs at least c d^2 / log(d+1) queries to guarantee error ε0/√d, with ε0 = 10^{-7}; combined with the known value-only method, the complexity is Θ~(d^2). The hard functions are maxima of m = d/2 linear functions f_W(x,z) = max_i (a x_i + ⟨w_i,z⟩). The lower bound works by an exact resisting oracle: after each query the adversary keeps a product of convex uncertainty sets for the rows, consistent with the entire transcript; an informative query slices one row to a codimension-one section while shrinking every other row's volume by at most a 1/(4m) fraction. A","pith_inferences":["The adversary's product invariant shows that exact real numbers can be treated without assigning a finite bit-content to a response; similar 'volume-slicing' adversaries may yield tight lower bounds for other partial oracles (comparison, bit-limited, or noisy values).","A natural next question is whether randomized algorithms can beat the d^2 barrier; the present resisting oracle is tied to a fixed deterministic transcript and the paper notes it does not yield a hard distribution, so randomization remains genuinely open.","The manuscript reports that machine-based formal verification covers only a coarser accuracy variant (d^{-3}), not the headline d^{-1/2} theorem; the main proof relies on classical convex-geometry results that have not been machine-checked, which is a place where a subtle gap could hide.","If a single exact function value could be shown to encode a subgradient or to shrink many rows at once, the lower bound would collapse; testing small-dimensional extreme cases of the per-query tradeoff could reveal whether the adversary's chosen response is optimal."],"forward_implications":["The polynomial separation between exact values and full first-order information is now proven: at accuracy Θ(d^{-1/2}), value-only complexity is Θ~(d^2) while first-order complexity is Θ(d).","The same near-quadratic lower bound holds for every fixed polynomially smaller accuracy d^{-α} with α > 1/2 (Corollary 5).","Mixed-integer convex optimization with n binary variables and d continuous variables requires Θ~(2^n d^2) exact-value queries, even when fractional queries in the continuous coordinates are allowed.","The hard instances are explicit maxima of d/2 linear functions, so the lower bound applies to the entire class of convex 1-Lipschitz functions.","Any exact-value algorithm, however adaptive, discontinuous, or memory-rich, fails below the bound; this rules out transcript-compression or bit-counting escapes."],"fun_headline_variants":["Near-quadratic lower bound closes 1996 oracle gap in convex optimization","Exact values alone: near-optimal d^2 query bound ends 1996 gap","Value-only convex optimization: Ω(d^2/log d) queries, closing 1996 gap","Mixed-integer convex: value-only queries explode to ~d^2 2^n"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The adversary can answer every exact-value query by collapsing exactly one row's uncertainty set to a codimension-one slice while shrinking every other row by at most a 1/(4m) volume fraction; if a single exact value could destroy a constant fraction of volume of many rows at once (for instance by encoding a full subgradient), the aggregate-width argument would fail and the d^2 lower bound would no longer follow.","fun_headline_variants_meta":{"raw":{"variants":["Near-quadratic lower bound closes 1996 oracle gap in convex optimization","Exact values alone: near-optimal d^2 query bound ends 1996 gap","Value-only convex optimization: Ω(d^2/log d) queries, closing 1996 gap","Mixed-integer convex: value-only queries explode to ~d^2 2^n"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001263,"raw_usage":{"total_tokens":4999,"prompt_tokens":723,"completion_tokens":4276,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":467,"completion_tokens_details":{"reasoning_tokens":4184}},"tokens_in":467,"tokens_out":4276,"duration_ms":37177,"temperature":1.0,"reasoning_tokens":4184,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T05:31:07.551509+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a deterministic value-only algorithm for the max-affine family of Section 3 that reaches error 10^{-7}/√d in o(d^2/log d) queries, or exhibit a single admissible query whose exact response on some transcript leaves a constant fraction of several row uncertainty sets' intrinsic volume eliminated — either would break the key per-query tradeoff (Proposition 10) and invalidate the lower bound.","supporting_citations":[],"review_version":1}