{"id":"8988dd00-5fba-4b7c-9859-df5884a20bd0","arxiv_id":"1908.07980","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":9,"one_line_summary":"ProSRS is a tree-based radial-basis surrogate optimizer with zoom-in/out and restarts; it is proven to eventually evaluate near the global optimum and benchmarks as orders of magnitude cheaper than Bayesian optimization.","lead":"This paper introduces ProSRS, a parallel surrogate optimization method that builds a cheap radial-basis model, zooms into promising regions, and occasionally restarts, to tune expensive noisy functions such as machine learning hyperparameters.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's proof assumes a uniform positive lower bound ν(ε) for candidate-point hits of the optimal ball, but ProSRS's p<0.1 phase has only Type-II Gaussian candidates and the bound is not re-derived for that phase or for zoomed domains.","rationale":"The central claim of the paper is the convergence guarantee in Theorem 1 together with the empirical speed/cost advantage. The most load-bearing piece of the theoretical argument is the positive lower bound ν(ε) on the probability that a candidate point lands near the global minimizer. The proof imports this bound from [25] and applies it to ProSRS's candidate generation without re-deriving it for the two novel complications: the p<0.1 all-Type-II phase and the zoom-in/zoom-out tree. If the imported bound only covers uniformly sampled points, then there are whole phases of the algorithm where the proof's key probability estimate is unjustified, and Theorem 1 falls. This is exactly the weakest assumption flagged by the reader. The empirical results are suggestive but are not formal evidence for the theorem, and the paper itself concedes that the returned noisy argmin is not the object of the theorem. Since the concern is a proof gap rather than a demonstrated counterexample, and the algorithm could likely be repaired with an explicit uniform lower bound for Type-II candidates, the appropriate verdict remains CONDITIONAL as the reader recommended. No change to the reader's verdict is needed.","tokens_in":15540,"tokens_out":11247,"duration_ms":113529,"concrete_test":"Inspect Regis-Shoemaker [25], Section 2, and determine whether the lemma giving ν(ε) is stated for uniformly sampled (Type I) candidate points only or also for Gaussian-perturbation (Type II) candidates. If it is Type-I-only, Theorem 1's L(ε) step is unsupported in the p<0.1 phase. To make the check quantitative, for a representative benchmark (e.g., Ackley10) compute the infimum over x*∈D of P(N(x*,σ^2 diag(l_i^2))∈B(x_opt,δ)∩D) with σ=0.0125 using a fine grid or adaptive integration; if the infimum is zero, or if [25]'s lemma is Type-I-only, the theorem lacks a valid proof as written.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 1 (Appendix A) defines L(ε)=ν(ε)^t and asserts, citing Regis-Shoemaker [25] Section 2, that a candidate point generated at the root node, 'of either Type I or Type II', falls in B(x_opt,δ)∩D with probability at least ν(ε)>0. This is the engine of the block argument: every block of Δ iterations has probability at least h(ε) of containing an evaluation in the optimal ball. But ProSRS's Algorithm 2 has a phase with p<0.1 in which the candidate set contains zero Type I (uniform) points; all candidates are Type II Gaussian perturbations around the current best x*. In that phase the imported uniform-sampling lower bound need not apply. A positive uniform bound for Type II would have to hold over all possible x*∈D and σ values down to σ_crit/2 (σ is halved before the zoom/restart check, so σ=0.0125 occurs), and the paper does not derive it. Moreover, in zoomed child domains not containing x_opt, Type I candidates have probability zero of hitting the ball, so the proof's E2 escape must zoom all the way to the root before applying L(ε); but if the reached root state is in the p<0.1 phase, the same Type-I-only gap reappears. If ν(ε) is not valid in this phase, the bound P(A_i|...)≤1−h(ε) is unsupported and Theorem 1 is unproven. Section 3 also acknowledges that the returned point is the lowest noisy y, not the x_n of the theorem, so the practical output guarantee is weaker even if the proof is repaired.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces ProSRS, a parallel surrogate optimization algorithm for noisy expensive black-box problems. ProSRS combines a tree-based 'zoom strategy' that recursively restricts attention to subdomains, a weighted radial-basis-function regression surrogate, and a stochastic response-surface candidate-generation step mixing uniform (Type I) and Gaussian-perturbation (Type II) points. The authors prove a convergence theorem (Theorem 1) claiming that, with probability converging to one, the best point among all evaluations by iteration n approaches the global minimizer. They also report numerical experiments on twelve benchmark functions and two hyperparameter-tuning problems, comparing ProSRS with three parallel Bayesian optimization methods (GP-EI-MCMC, GP-LP-LCB, GP-LP-EI) and claiming significantly faster convergence per iteration and one to four orders of magnitude lower computational cost.","tokens_in":15870,"tokens_out":12096,"duration_ms":131138,"significance":"If Theorem 1 and the empirical results hold, ProSRS would be a practically attractive alternative to Gaussian-process Bayesian optimization for expensive noisy parallel problems, especially when surrogate-building cost matters. The paper contributes a concrete algorithmic design, an explicit convergence theorem, public code, and a broad benchmark suite including real hyperparameter-tuning tasks. The central theoretical claim, however, depends on a bound imported from earlier work that is not re-derived for ProSRS's specific dynamics, and the proof's zoom-out argument has an unaccounted interruption mechanism. These issues are substantial but appear repairable, so the result is not yet established as stated.","major_comments":[{"comment":"The proof asserts that 'the probability that a candidate point generated in the root node (of either Type I or Type II) is located within the domain B(x_opt,δ(ε))∩D can be shown to be bounded from below by some positive ν(ε)' and cites Section 2 of Regis and Shoemaker [25]. This is the engine of the block argument leading to Eq. (8), but it is not established for ProSRS's actual candidate-generation dynamics. When p<0.1, Algorithm 2 generates zero Type I candidates and all candidates are Type II Gaussian perturbations around the current best x*, with σ potentially as low as σ_crit before a zoom/restart decision, and x* can be any evaluated point in the domain. A lower bound uniform over all such states and over root nodes reached after zoom-out is not derived in the manuscript. If the bound fails in any reachable state, the inequality P(A_i | A_1∩...∩A_{i-1}) ≤ 1−h(ε) is unsupported and Theorem 1 is not proven. I recommend adding an explicit lemma that derives a uniform positive lower bound for Type-II candidate distributions over all reachable (σ, x*) pairs, or modifying the algorithm so that a constant positive fraction of Type I points is always maintained.","section":"Appendix A, proof of Theorem 1, first paragraph after the definition of δ(ε)"},{"comment":"In the E2 case, the proof lower-bounds the probability of reaching the root node by (β_min)^{z_{i-1}}, assuming the algorithm 'decide[s] to zoom out' for z_{i-1} consecutive iterations and that this returns it to the root. However, a zoom-out decision at Line 21 does not by itself decrease the zoom level if a zoom-in occurred earlier in the same iteration (Lines 12–17): zoom-in followed by zoom-out leaves the current node unchanged. The proof does not lower-bound the probability of avoiding such interruptions for z_{i-1} consecutive iterations, so the claimed bound P(A_i | ... ∩ E2) ≥ L(ε)(β_min)^{z_{i-1}} is not justified as written. This is a second load-bearing gap in the proof of Theorem 1.","section":"Appendix A, case E2"}],"minor_comments":[{"comment":"The phrase 'a fraction of 1/10⌊10p⌋' is ambiguous; it should be written as (1/10)⌊10p⌋ or equivalent. As typeset, it could be read as 1/(10⌊10p⌋), which would contradict the later statement that all candidate points are Type II when p<0.1.","section":"Section 2.3, candidate-point mixture"},{"comment":"Theorem 1 concerns x_n, the point with the minimum true objective F among evaluations, whereas Algorithm 1 returns the point with the lowest noisy y. The authors acknowledge this gap in Section 3 and suggest posterior selection, but the abstract's phrase 'at least one point among all the evaluations' should be kept consistently in the conclusion as well, to avoid implying a guarantee on the returned point.","section":"Section 3 and abstract"},{"comment":"The empirical claim of 'significantly faster' convergence is not supported by statistical significance tests or confidence intervals beyond standard-deviation error bars; adding a paired test or a similar comparison would strengthen the claim.","section":"Section 4.1 and 4.2"},{"comment":"The restart condition is written inline and is easy to misread; presenting it as a displayed equation with the exact definition of l_i(Ω) and the role of n would improve clarity.","section":"Section 2.5, restart condition (Eq. 4)"}],"recommendation":"major_revision","confidential_remarks":"The proof gap regarding ν(ε) is the main issue. I believe it is fixable within the manuscript's scope, because a positive lower bound for Type-II Gaussian candidates likely holds when σ is bounded below by σ_crit (relative to the current domain length), but the authors need to prove it explicitly rather than citing [25]. The E2 interruption issue also needs a more careful event definition or a revised blocking argument. I would not recommend rejection on the basis of these gaps, but the theorem as currently stated and proved is not yet reliable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper is worth a read, but the headline theorem is not yet proven. ProSRS is a real algorithmic contribution: the zoom tree, weighted RBF regression, and mixed Type I/II candidate generation are a sensible evolution of the SRS line, and the empirical cost savings (1–4 orders of magnitude over GP-based baselines) are plausible and worth taking seriously.\n\nThe problem is Theorem 1. The proof imports from Regis–Shoemaker a positive lower bound ν(ε) on the probability that a candidate point falls in the ball around the global minimizer. That bound is derived for candidate sets that include a positive fraction of uniformly sampled points. But ProSRS has a phase, explicitly described in Algorithm 2 and Section 2.4, where p<0.1 and all candidates are Type II Gaussian perturbations around the current best point. Nothing in the paper shows that a uniform lower bound holds in that phase, especially when σ is halved down to 0.0125 or when the current best point is far from the optimum. The proof also assumes that after zooming out to the root, the root's candidate generation enjoys the bound; but if the root is in the Type-II-only phase, that is unsupported. So Theorem 1, as stated, is unproven. The paper itself acknowledges a related gap: the algorithm returns the lowest noisy y, not the x_n in the theorem, so the practical convergence guarantee is weaker even if the proof is repaired.\n\nThe empirical work is decent. The benchmarks cover a reasonable range, and the two hyperparameter-tuning problems give a real flavor of the cost advantage. But the comparison uses one hand-set configuration for ProSRS, no sensitivity analysis, and incomplete reporting of the GP baselines' hyperparameters. Those are fixable in revision. The modeling-capability study (RBF vs GP) is a nice supporting analysis, though not decisive.\n\nOverall: a novel method, a plausible empirical story, and a proof with a significant gap. The right verdict is conditional: send it to review, but require the authors to either prove the bound for the Type-II-only phase (or revise the algorithm to retain a positive fraction of uniform samples), or restate Theorem 1 with a corrected proof. The empirical contribution can stand on its own if the proof is fixed or the claim is softened.","headline":"ProSRS is a genuinely useful method with a compelling cost story, but Theorem 1's proof has a real gap in the Type-II-only candidate phase.","tokens_in":16443,"tokens_out":5043,"would_cite":true,"duration_ms":46506,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C56","90C15","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"ProSRS, a tree-based radial-basis surrogate method, provably reaches near-global minima at far lower cost than Bayesian optimization.","keywords":["noisy optimization","parallel surrogate optimization","radial basis function","stochastic response surface","zoom strategy","Bayesian optimization","convergence guarantee","hyperparameter tuning"],"falsifier":"Run ProSRS on a smooth noisy benchmark with a unique global minimizer, such as Ackley10 with the paper's noise level, and record for a fixed epsilon whether, over many runs, the best noisy evaluation enters the epsilon-ball around the global minimizer and whether the empirical frequency tends to one; alternatively, compute the minimum over iterations of the probability that a proposed point falls in that ball under the algorithm's own candidate dynamics. If that probability drops to zero for some epsilon, the imported lower-bound assumption fails.","tokens_in":15273,"feed_emoji":"🌳","tokens_out":5897,"duration_ms":56056,"temperature":0.7,"pith_summary":"ProSRS is a new parallel surrogate optimization algorithm for noisy, expensive black-box functions. It builds a weighted radial-basis surrogate, proposes candidate points through a stochastic response surface method, and uses a tree-based 'zoom strategy' that concentrates evaluations in promising subdomains. The paper's central theoretical claim is that, under mild continuity assumptions, some point among all evaluations will almost surely approach the global minimum as the algorithm runs. The paper's empirical claim is that ProSRS reaches good solutions faster per iteration and is one to four orders of magnitude cheaper in compute time than three Bayesian optimization baselines, on twelve benchmark functions and two machine-learning hyperparameter tuning tasks.","feed_headline":"Tree-based ProSRS provably reaches near-global minima","feed_subtitle":"A surrogate method using radial-basis fits and a zoom tree beats Bayesian optimization and costs far less.","key_machinery":"The load-bearing machinery is a weighted multiquadric radial-basis surrogate fitted by L2-regularized, exploitively weighted regression, paired with a stochastic response surface (SRS) candidate generator that mixes uniform Type-I points with Gaussian perturbations around the current surrogate best (Type-II). The tree-based zoom strategy shrinks the domain around the current best point by a factor rho and creates a child node; zoom-out happens with small probability beta, and a restart fires when the zoom level would make the domain resolution finer than r. The proof works because the zoom level is bounded by the restart rule and because, at every level, candidate generation is assumed to give a lower-bounded probability of hitting a small ball around the global minimizer.","core_discovery":"The paper's core claim is Theorem 1: for a continuous objective with a unique global minimizer, the best evaluated point (measured by the true function) converges almost surely to that minimizer. The proof combines a bounded tree depth, forced by the restart resolution parameter, with a positive lower bound on the chance that an iteration's candidate pool contains a point near the optimum. The practical companion claim is that this convergence comes at very low computational price: weighted radial-basis regression and discrete candidate scoring keep per-iteration cost nearly flat, whereas Gaussian-process training and acquisition maximization grow quickly with evaluation count.","pith_inferences":["The theorem concerns the best point by the true expected function, whereas the algorithm returns the point with lowest noisy value; the paper itself notes that a posterior ranking-and-selection step is needed, so the practical guarantee for the returned point is weaker than the theorem.","The proof gives no convergence rate, so the paper's finite-budget advantage rests entirely on the empirical benchmarks; one should not infer that the zoom tree accelerates convergence in the asymptotic regime.","The same zoom-on-demand idea could be grafted onto other surrogate families, such as local Gaussian-process fits, which might inherit the cost savings while keeping Bayesian uncertainty estimates; this is an extension the paper does not test.","If the one-to-four-orders-of-magnitude cost gap holds in practice, it suggests that for many hyperparameter-tuning pipelines the surrogate's own compute, not the model training, is the real bottleneck."],"forward_implications":["With enough iterations, ProSRS is guaranteed to have evaluated a point arbitrarily close to the global minimum, making it a viable fallback for noisy expensive problems where random search is the only competitor.","The per-iteration cost stays roughly constant over time because zooming and restarting keep the local evaluation set small, which is what makes the algorithm one to four orders of magnitude cheaper than GP-based parallel Bayesian optimization.","Because multiple points are proposed per iteration and evaluated in parallel, wall-clock progress is not limited by the surrogate fitting step.","The cross-validation procedure for the RBF regularization lets the surrogate adapt to data without Gaussian-process prior assumptions, which the paper argues explains much of the performance gain."],"supporting_citations":[{"why":"Supplies the stochastic response surface candidate-generation framework and the positive lower-bound probability argument that Theorem 1 builds on.","marker":"[25]"},{"why":"Extends SRS to parallel point proposals and provides the weight-pattern scoring procedure that ProSRS adopts.","marker":"[26]"},{"why":"Introduces the GP-EI-MCMC baseline used for comparison and the practical Bayesian optimization approach for machine learning algorithms.","marker":"[29]"},{"why":"Introduces the batch Bayesian optimization via local penalization (GP-LP) baseline used for comparison.","marker":"[12]"},{"why":"Provides the simple-random-search convergence argument used at the end of the proof of Theorem 1.","marker":"[30]"}],"fun_headline_variants":["ProSRS provably reaches global minima, cheaply","Tree-based ProSRS beats Bayesian, with proof","Zoom-tree surrogate proves global convergence at low cost","ProSRS: proven global minimum, 1-4x cheaper","Surrogate optimizer converges to global min, costs little"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The convergence proof assumes that in every iteration a candidate point has at least a fixed positive probability of landing inside a small ball around the global minimizer, and that this guarantee is not destroyed by the zoom tree, the Type-II-only phase, or restarts.","fun_headline_variants_meta":{"raw":{"variants":["ProSRS provably reaches global minima, cheaply","Tree-based ProSRS beats Bayesian, with proof","Zoom-tree surrogate proves global convergence at low cost","ProSRS: proven global minimum, 1-4x cheaper","Surrogate optimizer converges to global min, costs little"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000365,"raw_usage":{"total_tokens":1882,"prompt_tokens":777,"completion_tokens":1105,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":393,"completion_tokens_details":{"reasoning_tokens":1025}},"tokens_in":393,"tokens_out":1105,"duration_ms":51430,"temperature":1.0,"reasoning_tokens":1025,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:53:29.197157+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run ProSRS on a smooth noisy benchmark with a unique global minimizer, such as Ackley10 with the paper's noise level, and record for a fixed epsilon whether, over many runs, the best noisy evaluation enters the epsilon-ball around the global minimizer and whether the empirical frequency tends to one; alternatively, compute the minimum over iterations of the probability that a proposed point falls in that ball under the algorithm's own candidate dynamics. If that probability drops to zero for some epsilon, the imported lower-bound assumption fails.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the stochastic response surface candidate-generation framework and the positive lower-bound probability argument that Theorem 1 builds on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Extends SRS to parallel point proposals and provides the weight-pattern scoring procedure that ProSRS adopts."},{"cited_title":"Snoek, H","cited_arxiv_id":null,"evidence_quote":"Introduces the GP-EI-MCMC baseline used for comparison and the practical Bayesian optimization approach for machine learning algorithms."},{"cited_title":"González, Z","cited_arxiv_id":null,"evidence_quote":"Introduces the batch Bayesian optimization via local penalization (GP-LP) baseline used for comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the simple-random-search convergence argument used at the end of the proof of Theorem 1."}],"review_version":1}