{"id":"7dbb713e-8e67-4b87-a78b-1ef0beff4596","arxiv_id":"2502.04290","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"ECP is a no-regret global optimization algorithm for Lipschitz black-box functions with unknown constant, achieving minimax-optimal regret via an expanding acceptance region.","lead":"A new black-box optimizer, ECP, maximizes expensive functions without knowing their Lipschitz constant by growing an acceptance region that skips unpromising samples. It comes with no-regret and minimax-rate guarantees, and it wins the most benchmark problems among 11 methods, though not on every task.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 6's induction has an unhandled case where the first post-hitting-time evaluation already exceeds the threshold y, so the level-set containment X_y subset X_{k,t} can fail; the off-by-one in Lemma 2 places the claimed hitting time exactly at that fragile round.","rationale":"After reading the paper and proofs, the main theoretical claims appear substantially sound. The most fragile point is Proposition 6, which is the bridge between ECP's acceptance process and the PRS-based bound of Theorem 3. The reader's weakest_assumption identifies a genuine gap: the level-set containment that drives the induction is only shown for thresholds y above the running maximum, yet the running maximum includes points accepted after i*, and the proposition's threshold condition does not cover them. However, this gap is not a counterexample to the theorem; it is a case-split oversight. On the event that the running max is already at least y, the target event holds trivially; on the complementary event, all evaluated points are below y and the containment follows from Lipschitzness and epsilon_t >= k. The off-by-one in Lemma 2 does not change the rate or the validity of the theorem, since the theorem uses the exact i* rather than its upper bound; it only shifts a logarithmic constant in Table 5. Empirically, the abstract's 'outperforms' is stronger than Table 1's 'most top-1 placements' (13/30), but this is a framing issue, not a technical flaw. The reader's CONDITIONAL verdict, with requests to fix the proof gap, correct the off-by-one, and soften the empirical claims, is appropriate, so we see no reason to move the verdict.","tokens_in":36278,"tokens_out":19919,"duration_ms":189486,"concrete_test":"Re-derive the induction in Proposition 6 (Appendix C.12) with an explicit case split: on the event that max_{i=i*,...,t} f(x_i) >= y, the target event holds; on the complementary event, verify that every evaluated point through t has value < y, and hence X_y subset X_{k,t} and A_{epsilon_t,t} superset X_y hold. Then check the base case t = i* with epsilon_{i*} = k and f(x_{i*}) > y: does the chain P(f(x_{i*}) >= y) >= mu(X_y)/mu(X) hold? If yes, confirm that replacing Lemma 2's bound by ceil(log_tau(k/epsilon1))+1 leaves the rate in Theorem 3 unchanged, shifting only the constant. Optionally, run a 1D simulation with f(x)=max(0,1-|x|), epsilon1=0.5, tau=2, n=3 to confirm the tail distribution still dominates PRS.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Appendix C.12 (Proposition 6) establishes the stochastic dominance that Theorem 3 converts into the finite-budget regret bound. The induction relies on the containment X_y subset X_{k,t} on the event that the running best is below y. The proposition's threshold condition only requires y >= max_{i=1,...,i*-1} f(x_i); it does not control f(x_{i*}), the point accepted exactly when epsilon first reaches k. If f(x_{i*}) >= y, the event is already achieved, but the proof's displayed equality P(f(x_{i*}) >= y) = E[mu(A_{epsilon,i*} intersect X_y)/mu(A_{epsilon,i*})] and the subsequent lower bound E[mu(X_{k,i*} intersect X_y)/mu(X)] are not justified, because X_y subset X_{k,i*} can fail when the new point exceeds y. The same issue recurs at the induction step, where A_{epsilon_n,n} superset X_y is used on the event {max_{i=i*,...,n} f(x_i) < y} without conditioning on f(x_i) values at times after i*. Lemma 2 (Appendix C.10) upper-bounds i* by ceil(log_tau(k/epsilon1)), but the deterministic growth epsilon_t >= epsilon1 tau^{t-1} gives i* >= ceil(log_tau(k/epsilon1))+1 when the logarithm is not integral; the stated bound is therefore off by one, placing the claimed hitting time exactly at the first round where the new point can violate containment. These are repair-able gaps: a case split on whether the running max already exceeds y fixes the induction. But as written, the proof of Theorem 3 is incomplete.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces ECP, an adaptive sampling algorithm for global maximization of Lipschitz black-box functions when the Lipschitz constant is unknown. In each round ECP samples uniformly from the search space but evaluates a point only if it lies in an acceptance region A_{ε_t,t}, where ε_t grows both deterministically after evaluations and stochastically when rejections accumulate. The paper claims that ECP is no-regret in the infinite-budget setting, achieves the minimax-optimal finite-budget regret rate O(k n^{-1/d}) without knowing k, has polynomial computational complexity, and outperforms 10 benchmarks on 30 synthetic and real-world problems.","tokens_in":36577,"tokens_out":7882,"duration_ms":81347,"significance":"If the theoretical claims were fully established, this would be a strong contribution to Lipschitz global optimization. The algorithm is simple, publicly implemented, and avoids the space-filling exploration used by AdaLIPO to estimate the Lipschitz constant. The claimed finite-budget regret bound matches the minimax lower bound, and the empirical study is broad, with ablations over the three hyperparameters. However, the proof of the key stochastic-dominance lemma is incomplete, the hitting-time lemma contains an off-by-one error, and the empirical claim of universal superiority is overstated. The significance of the paper is therefore conditional on the repair of these load-bearing points.","major_comments":[{"comment":"The proof of stochastic dominance does not justify the containment X_y ⊆ X_{k,i⋆} used in the base case. At time i⋆, the set X_{k,i⋆} is defined with max_{j≤i⋆} f(x_j), which includes the newly evaluated point x_{i⋆}. For z ∈ X_y, Lipschitzness only gives f(x_i) + k∥z−x_i∥ ≥ f(z) ≥ y; if f(x_{i⋆}) ≥ y, this does not imply z ∈ X_{k,i⋆}, and the displayed lower bound E[µ(X_{k,i⋆}∩X_y)/µ(X)] is not justified. The same gap appears at the induction step, where X_y ⊆ X_{k,n} is used conditionally on max_{i=i⋆,...,n} f(x_i) < y without controlling the value at the next evaluated point. A case split on whether the running maximum has already exceeded y can likely repair the argument, but as written Proposition 6 is unproven, and Theorem 3, which relies on Proposition 6, is therefore not established.","section":"Appendix C.12 (Proposition 6)"},{"comment":"The stated upper bound i⋆ ≤ ceil(log_τ(k/ε1)) is off by one when log_τ(k/ε1) is an integer. Since ε_t ≥ ε1 τ^{t−1}, if k/ε1 = τ^m with integer m, then ε_{m+1} ≥ k while ε_m < k, so i⋆ ≥ m+1 = ceil(log_τ(k/ε1))+1. For example, ε1=1, τ=2, k=4 gives i⋆=3, while the lemma as stated gives i⋆≤2. The correct minimal bound is ceil(log_τ(k/ε1)) when the logarithm is non-integral and ceil(log_τ(k/ε1))+1 when it is integral. This timing is exactly what Proposition 6's base case needs, so the lemma must be corrected and its consequences for Proposition 6 and Theorem 3 re-derived.","section":"Appendix C.10 (Lemma 2)"},{"comment":"The proof of the no-regret claim is not a proof. It argues that once ε_t > k, Proposition 2 gives P_{k,t} ⊆ A_{ε_t,t}, and then concludes that 'the search space uniformly recovers all the potential maximizers and beyond.' This does not establish that max_{i≤n} f(x_i) converges in probability to max_X f, because no quantitative statement is made about the probability that accepted points fall near a maximizer as n grows. The no-regret conclusion is a central advertised contribution and needs a rigorous argument, for instance by invoking the stochastic dominance in Proposition 6 or by giving a direct covering argument for the acceptance region.","section":"Appendix C.11 (Theorem 2)"},{"comment":"The claim that ECP 'outperforms 10 benchmark algorithms' across 30 problems is stronger than the reported data. In Table 1 with n=50, ECP is Top-1 on 13 of 30 problems, and it is not the best on several named problems (e.g., autoMPG, concrete, housing, yacht, Bukin, Easom, Langermann). The violin plot supports a good median ranking, but it does not support universal dominance. The abstract, introduction, and Section 7 should be reworded to say that ECP is competitive and often best, with a precise definition of the aggregate comparison, and ideally with statistical significance tests.","section":"Section 6, Table 1, and Abstract"}],"minor_comments":[{"comment":"There are numerous typos and grammatical slips, including 'intersting', 'unkown', 'Morever', 'potentailly', 'arbitraly', and running headers such as 'F unctions'; these should be corrected in a revision.","section":"Throughout"},{"comment":"The ablation text says 'keeping τ = 10^{-3}', but τ must be > 1 in the algorithm; the text and captions should consistently state a valid value such as τ = 1.001.","section":"Appendix E.4"},{"comment":"The notation for the exploration event is inconsistent: the text first says E=1 denotes an exploitation phase, then says 'during exploration (E=1) a point is never rejected'; the conditional probability statement P(R | E=0) is also unclear. Please define the event and its complement coherently.","section":"Appendix C.6 (Proposition 7)"},{"comment":"Tables 2 and 4 omit several baselines that appear in Table 1 (Botorch, SMAC3, A-GP-UCB), so the comparisons at n=25, n=100, and n=300 are not against the same set of methods; the captions should state this explicitly or the tables should be completed.","section":"Appendix A, Tables 2 and 4"},{"comment":"The use of h_{t+1} both as a counter of rejections at round t and as an index in the pseudocode is confusing; renaming the counter to something like r_t would make the growth condition and the reset rule easier to follow.","section":"Algorithm 1"},{"comment":"The proof applies Lemma 4 with the stated constant diam(X), but the standard uniform-sampling regret bound for Lipschitz functions contains an additional constant depending on the covering number of X; if Lemma 4 is quoted from Malherbe and Vayatis (2017), the exact constant should be checked and stated explicitly.","section":"Appendix C.13 (Theorem 3)"}],"recommendation":"major_revision","confidential_remarks":"This paper is a borderline case. The algorithm and experimental setup are solid, and the claimed minimax-optimal rate is the main selling point. However, the proof of Proposition 6 is genuinely incomplete, Lemma 2 has an off-by-one error, and the no-regret proof is only a sketch. These issues are repairable but load-bearing, so a major revision is appropriate. If the authors fix the stochastic-dominance argument and temper the empirical claims, the paper could be acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, quick take on arXiv:2502.04290. ECP is a genuinely useful twist on LIPO: instead of estimating the Lipschitz constant, it grows an acceptance-region parameter and uses rejections to trigger growth. That removes the space-filling exploration AdaLIPO needs, and the finite-budget regret bound is the right target. The empirical work is solid and extensive – 30 problems, multiple budgets, ablations, public code. I believe the algorithm works.\n\nBut the proof of Theorem 3 is not complete as written. The stochastic-dominance step in Proposition 6 (Appendix C.12) has an unhandled case at the base: the threshold y only dominates the first i*-1 evaluations, while the point x_{i*} is not controlled. If f(x_{i*}) ≥ y, the event is already achieved, but the containment X_y ⊆ X_{k,i*} can fail, so the displayed equality/lower bound isn't justified. A case split on whether the running max already exceeded y repairs this; the induction step is fine because it conditions on the running max being below y. Also, Lemma 2's bound is off by one: ε_t ≥ ε_1 τ^{t-1} gives hitting time at most ceil(log_τ(k/ε_1))+1, not ceil(···). Moreover, the paper's indexing conflates ε_t used at iteration t with the evaluation index; x_{t+1} is evaluated under ε_t, so the hitting time for evaluations is shifted. These are all fixable, but a referee needs to see a corrected proof.\n\nThe abstract's claim of outperforming 10 methods across 30 problems is stronger than Table 1 supports: ECP has the most top-1 placements, but Bayesian methods (Botorch, SMAC3, A-GP-UCB) win on several problems and dominate some. The median ranking story is fair; 'outperforms' is too absolute.\n\nBottom line: this is a meaningful incremental advance for Lipschitz optimization and deserves peer review, but as a conditional accept requiring the proof gap to be closed and the empirical claims softened. If you work on expensive black-box optimization, it's worth reading.","headline":"ECP is a useful parameter-free Lipschitz optimizer with a legitimate new twist, but the paper's central finite-budget regret proof has a fixable gap and an off-by-one that need attention.","tokens_in":37169,"tokens_out":7142,"would_cite":true,"duration_ms":67424,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C56"],"pacs":[],"model":"deepseek-v4-flash","headline":"A black-box optimizer claims minimax-optimal regret without ever estimating the Lipschitz constant.","keywords":["global optimization","Lipschitz continuous functions","unknown Lipschitz constant","black-box optimization","no-regret","minimax regret","acceptance region","expensive function evaluations"],"falsifier":"Fix a simple $1$-$\\mathrm{D}$ Lipschitz function with a known $k$, e.g. $f(x)=k x$ on $[0,1]$, and run ECP with known $\\varepsilon_1$ and $\\tau$ so that $i^\\star=\\lceil \\log_\\tau(k/\\varepsilon_1)\\rceil$. Record whether, for every threshold $y\\ge \\max_{i<i^\\star} f(x_i)$, the maximum value of accepted points from rounds $i^\\star$ through $n$ stochastically dominates $n-i^\\star+1$ independent uniform samples. A single $y$-level or seed where $P(\\max_{i=i^\\star,\\dots,n} f(x_i)\\ge y) < P(\\max \\text{uniform}\\ge y)$ would disprove Proposition 6 and with it the current proof of Theorem 3.","tokens_in":36025,"feed_emoji":"🎯","tokens_out":10262,"duration_ms":99831,"temperature":0.7,"pith_summary":"This paper proposes ECP, a global optimization algorithm for black-box functions that are Lipschitz continuous with an unknown Lipschitz constant. The central claim is that by screening every sampled point through a growing acceptance region, ECP spends function evaluations only on potential maximizers, never on uniform sampling to estimate $k$, and yet achieves no-regret behavior and minimax-optimal finite-budget regret. This matters for expensive evaluations: users need no estimate of $k$, no separate exploration calls, and no hand-tuned local smoothness, and the same method works across many non-convex benchmarks. If the theory holds, ECP closes the gap between methods that need $k$ and adaptive methods that waste calls estimating it.","feed_headline":"Optimizer skips the Lipschitz constant, still hits minimax regret","feed_subtitle":"ECP screens every function call as a potential maximizer and beats 10 baselines on small budgets.","key_machinery":"The central object is the acceptance region $A_{\\varepsilon_t,t}=\\{x\\in\\mathcal{X}: \\min_{i\\le t}(f(x_i)+\\varepsilon_t\\|x-x_i\\|_2)\\ge \\max_{j\\le t} f(x_j)\\}$. It is the set of points consistent with at least one $k$-Lipschitz function matching the observed evaluations once $\\varepsilon_t=k$, so it tracks the paper's notion of potential maximizers. The mechanism is the monotone interplay: the region expands as $\\varepsilon_t$ grows and shrinks as $t$ grows; ECP deliberately grows $\\varepsilon_t$ faster than rejection rates explode, guaranteeing eventual acceptance with polynomial complexity. The hitting time $i^\\star$ is when $\\varepsilon_t\\ge k$, after which the region provably contains every level set above the current best.","core_discovery":"The paper's discovery is that a purely threshold-driven acceptance rule can carry the full weight of Lipschitz optimization. At round $t$, ECP accepts a uniformly sampled point $x$ only if $\\min_i (f(x_i)+\\varepsilon_t\\|x-x_i\\|_2) \\ge \\max_j f(x_j)$; the tolerance $\\varepsilon_t$ grows geometrically with $\\tau_{n,d}>1$ and also whenever rejections pile up. Because $\\varepsilon_t$ eventually reaches the unknown constant $k$, the acceptance region catches every potential maximizer, and Proposition 6 asserts that after that hitting time $i^\\star$ ECP's evaluations stochastically dominate independent uniform samples. Consequently Theorem 3 gives $R_{\\mathrm{ECP},f}(n) \\le \\mathrm{diam}(\\mathcal{X})\\, (i^\\star)^{1/d}\\, k\\, (\\ln(1/\\delta)/n)^{1/d}$ with probability at least $1-\\delta$, matching the minimax lower bound $\\Omega(k n^{-1/d})$ recalled in Proposition 1.","pith_inferences":["The proof of Proposition 6 depends on the level-set containment $\\{x: f(x)\\ge y\\}\\subseteq A_{\\varepsilon_t,t}$ holding exactly at $i^\\star$; if the off-by-one in Lemma 2 is a genuine gap, the bound likely survives with $i^\\star+1$, so the minimax rate is probably intact even if the stated constant is not.","The same acceptance-rule idea extends to local smoothness via a semi-metric $\\ell(x^\\star,x)$, as the paper's Remark 1 sketches, and could be tested on structured or discrete search spaces where the uniform-volume rejection bound changes.","Because ECP's advantage concentrates at small budgets, a natural hybrid is to run ECP early and hand off to a surrogate-based or evolutionary method once enough evaluations accumulate; the paper's own large-budget tables hint this could be beneficial.","The ablations suggest performance improves with smaller $\\varepsilon_1$, smaller $\\tau$, and larger $C$ at higher computational cost; an adaptive schedule that sets these from the observed rejection rate, without knowing $k$, is a direct testable extension."],"forward_implications":["For a fixed budget $n$, ECP's regret is $O(k n^{-1/d})$ with no separate term for estimating $k$, so every evaluation counts toward the objective rather than toward exploration.","ECP is no-regret over all $k$-Lipschitz functions for any choices of $\\varepsilon_1>0$, $\\tau_{n,d}>1$, and $C>1$, because $\\varepsilon_t$ deterministically crosses $k$.","When $\\varepsilon_1\\ge k$ and $\\tau_{n,d}=1$, ECP reduces to the known-constant method LIPO, giving the same regret bound; thus ECP is a strict generalization.","Computational complexity is polynomial in $n$ with high probability, and the growth condition prevents the infinite rejection loops that can stall AdaLIPO and AdaLIPO+.","In the empirical comparison on 30 problems at budget 50, ECP ranks first most often among the 11 methods, and it keeps a strong edge at smaller and larger budgets."],"supporting_citations":[{"why":"Supplies the LIPO/AdaLIPO acceptance-condition framework, the identity $A_{k,t}=P_{k,t}$, and the uniform-sampling regret bound that ECP's Theorem 3 builds on.","marker":"Malherbe and Vayatis (2017)"},{"why":"Provides the minimax lower bound $\\Omega(k n^{-1/d})$ that ECP's regret rate is claimed to match.","marker":"Bull (2011)"},{"why":"Provides AdaLIPO+, the recent adaptive Lipschitz baseline, along with rejection-probability bounds that ECP compares against and empirically beats.","marker":"Serré et al. (2024)"},{"why":"Motivates the active subset of consistent functions from which Definition 3 and potential maximizers are drawn.","marker":"Dasgupta (2011)"},{"why":"Supplies the same active-learning concept of consistent functions used to define potential maximizers.","marker":"Hanneke (2011)"},{"why":"Supplies the real-world hyperparameter-tuning testbed (kernel ridge regression) used in the empirical comparison.","marker":"Malherbe et al. (2016)"}],"fun_headline_variants":["No Lipschitz guess: ECP hits minimax regret","Threshold rule only: ECP matches optimal regret","ECP skips Lipschitz, beats 10 baselines","Every call counts: ECP's geometric rule wins"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire finite-budget guarantee rests on the assertion that once $\\varepsilon_t$ reaches the unknown Lipschitz constant $k$, every point at least as good as the current best passes ECP's acceptance test, so the later evaluations are at least as good as uniform random samples; if that containment fails at the claimed round, the regret bound is not proven.","fun_headline_variants_meta":{"raw":{"variants":["No Lipschitz guess: ECP hits minimax regret","Threshold rule only: ECP matches optimal regret","ECP skips Lipschitz, beats 10 baselines","Every call counts: ECP's geometric rule wins"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000168,"raw_usage":{"total_tokens":1259,"prompt_tokens":944,"completion_tokens":315,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":560,"completion_tokens_details":{"reasoning_tokens":248}},"tokens_in":560,"tokens_out":315,"duration_ms":3941,"temperature":1.0,"reasoning_tokens":248,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T22:53:37.415651+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix a simple $1$-$\\mathrm{D}$ Lipschitz function with a known $k$, e.g. $f(x)=k x$ on $[0,1]$, and run ECP with known $\\varepsilon_1$ and $\\tau$ so that $i^\\star=\\lceil \\log_\\tau(k/\\varepsilon_1)\\rceil$. Record whether, for every threshold $y\\ge \\max_{i<i^\\star} f(x_i)$, the maximum value of accepted points from rounds $i^\\star$ through $n$ stochastically dominates $n-i^\\star+1$ independent uniform samples. A single $y$-level or seed where $P(\\max_{i=i^\\star,\\dots,n} f(x_i)\\ge y) < P(\\max \\text{uniform}\\ge y)$ would disprove Proposition 6 and with it the current proof of Theorem 3.","supporting_citations":[],"review_version":1}