{"id":"e7101a43-a9d7-420a-807f-dcfa3270260a","arxiv_id":"2411.17071","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Stagger Thompson Sampler, a Hit-and-Run Thompson sampling variant with argmax-mean initialization and a log-uniform proposal, beats standard Thompson sampling, PSS, and common acquisition functions on synthetic benchmarks from 3 to 300 dimensions.","lead":"This paper introduces Stagger Thompson Sampler (STS), a new way to draw Thompson samples in Bayesian optimization that is more precise and faster than standard Thompson sampling. On nine test functions from 3 to 300 dimensions, it reports higher average performance than popular acquisition methods such as expected improvement and upper confidence bound.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1's 'stagger' proposal is not symmetric, so even a fully mixed chain does not target p*(x); the central Thompson-sampling claim is invalid.","rationale":"The reader's weakest assumption identified the lack of a mixing proof, which is a valid concern. My stress-test finds a more fundamental defect: even under perfect mixing, the sampler's stationary distribution is not p*(x) because the proposal is not symmetric and the Hastings ratio is omitted. This is an internal inconsistency, not a matter of outside consensus. The paper's strongest claim is that STS is a Thompson sampler that draws from p*(x); that claim is contradicted by a simple one-dimensional calculation. The empirical comparisons may still show that STS is a useful heuristic, and the ablation studies are informative, but the theoretical foundation for calling it Thompson sampling—and for transferring TS's regret guarantees—is broken. A revision would need to either correct the acceptance probability with the proposal ratio, replace the proposal with a genuinely symmetric one, or explicitly reframe STS as a heuristic and drop the p*-sampling claim. Because the central claim as stated is false, the appropriate verdict is REJECT rather than CONDITIONAL. The concrete test above would decisively confirm the asymmetry for the authors and reviewers.","tokens_in":8818,"tokens_out":6556,"duration_ms":59051,"concrete_test":"Compute the proposal-density ratio q(x'|x)/q(x|x') for a fixed pair, e.g., d=1, x=0.1, x'=0.5, with s_min=e^{-k}, analytically or by numerical integration; show it is not 1. Then run an idealized Metropolis chain with exact target p*(x)=1 (uniform) using Algorithm 1's proposal and exact MH acceptance (always accept). After 10^5 steps, the empirical histogram of states will be visibly non-uniform (e.g., the stationary density is not flat), confirming the chain does not target p*. If instead the histogram is flat within sampling error, the symmetry claim would be supported and the concern would be resolved.","verdict_should_be":"REJECT","load_bearing_attack":"Algorithm 1 proposes x' = x + s(x_t - x) with x_t uniform and s log-uniform. The paper says 'a log-uniform distribution is a symmetric proposal', but the induced transition kernel is not symmetric. For fixed s, the map x_t -> x' has Jacobian s^{-d}, so q(x'|x) ∝ ∫_{s_min}^1 s^{-(d+1)} 1{x_t ∈ [0,1]^d} ds, where x_t = (x' - (1-s)x)/s. The allowable s-interval depends on x and x' asymmetrically. In d=1, with x=0.1, x'=0.5, s_min→0, the forward move requires s≥0.4/0.9=0.444, giving q ∝ ∫_{0.444}^1 s^{-2} ds = 1.25; the reverse move requires s≥0.4/0.5=0.8, giving q ∝ ∫_{0.8}^1 s^{-2} ds = 0.25. Thus q(x'|x)/q(x|x') = 5 ≠ 1. Algorithm 1 accepts with min{1, p*(x')/p*(x)} and omits the Hastings correction, so the stationary distribution of the chain is not p*. For instance, if p* is uniform, the chain is not uniform: from x=0.1 it is five times more likely to move to 0.5 than back. This bias is independent of M and of mixing; even an infinitely long run samples the wrong distribution. The empirical results may describe a useful heuristic, but the paper's central theoretical justification—that STS draws from p*(x)—is false.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Stagger Thompson Sampler (STS), a Markov-chain-based acquisition method for Bayesian optimization. STS modifies Hit-and-Run with a log-uniform \"stagger\" perturbation, initializes the chain at the posterior mean maximizer, and uses a single joint Gaussian process sample to decide whether to accept a proposal. The authors claim that STS draws samples from p*(x), the probability that a point is the global maximizer under the GP model, and report that STS outperforms Thompson sampling, PSS, and several other acquisition functions on nine test functions across dimensions 3-300, while also matching PSS when used as the input to the Minimal Terminal Variance batching algorithm. The appendix provides ablations on initialization and proposal distribution and a tuning study for the iteration count M.","tokens_in":9241,"tokens_out":8965,"duration_ms":82023,"significance":"The empirical study is broad and carefully structured: nine test functions, multiple random distortions, several dimensions, multiple baselines, and error bars are included, and the ablation studies are informative. If the central sampling claim were correct, STS would be a simple and dimension-scalable Thompson sampling method, and the combination STS+MTV would be a practically useful contribution. The empirical results may indeed describe a useful heuristic, but the paper's theoretical foundation, which is the basis for calling STS a Thompson sampler, is not established and, as shown below, is in fact invalid for the algorithm as stated.","major_comments":[{"comment":"The stagger proposal is not symmetric, so the chain does not target p*(x). For a fixed s, the transformation x' = x + s(xt - x) has Jacobian s^{-d} with respect to xt, and the set of s values for which xt = (x' - (1-s)x)/s lies in [0,1]^d depends on x and x' asymmetrically. In d=1, take x=0.1, x'=0.5, and s_min -> 0. The forward move requires s >= 0.4/0.9 = 0.444, giving q(x'|x) proportional to ∫_{0.444}^{1} s^{-2} ds = 1.25; the reverse move requires s >= 0.4/0.5 = 0.8, giving q(x|x') proportional to ∫_{0.8}^{1} s^{-2} ds = 0.25. Thus q(x'|x)/q(x|x') = 5, so the proposal is not symmetric. Since Algorithm 1 accepts with min{1, p*(x')/p*(x)} and omits the Hastings correction, the chain is not reversible with respect to p* and its stationary distribution is not p*. The statement in Section 2 that 'a log-uniform distribution is a symmetric proposal' is therefore incorrect, and this affects a load-bearing claim: even a fully mixed chain following Algorithm 1 would not produce Thompson samples from p*(x).","section":"Section 2, Algorithm 1"},{"comment":"The acceptance rule uses a single joint GP sample at {x, x'} and accepts x' when y' > y. The target p*(x) is the probability that x is the global maximizer over the whole domain, but the event y' > y only compares the two points under the GP draw. Therefore the acceptance does not implement min{1, p*(x')/p*(x)} even if the proposal were symmetric; the chain has a different, unspecified stationary distribution. Appendix A's std(p_max) diagnostic is, as the paper itself acknowledges, only a necessary condition and not sufficient; it cannot establish that the samples come from p*. No mixing proof, convergence rate, or stationary-distribution analysis is provided. This is a second load-bearing gap between Algorithm 1 and the Thompson-sampling interpretation.","section":"Section 2, acceptance rule; Appendix A"},{"comment":"The hyperparameter M (the number of refinement iterations) is selected by sweeping on the same nine test functions used in the main evaluation (Figure 3), and the value M=30 is then used in the main comparisons. This constitutes model selection on the evaluation set, so the reported performance advantage may be inflated. The paper should either tune M on a separate held-out set of functions or report the main results across a range of M values to show that the conclusion is robust to this choice.","section":"Section 3.2 and Appendix B, Figure 7"},{"comment":"The empirical protocol is under-specified. No code is provided, and the GP kernel, hyperparameter handling, lengthscale bounds, noise model, and the random distortion procedure 'as in [17]' are not described. Without these details, the results of the 874,800-evaluation comparison cannot be reproduced or checked for implementation errors, which is particularly important given that the theoretical sampler claims are in question.","section":"Section 3, experimental protocol"}],"minor_comments":[{"comment":"Expected Improvement is cited as [10], but that reference is about experimental design for generalized linear models, not the EI acquisition function; the canonical citation is [12] (Mockus).","section":"Section 1, reference [10]"},{"comment":"The score definition uses the symbol M for the number of methods, but M is already used in Algorithm 1 for the number of refinement iterations; this notation collision is confusing.","section":"Section 3.1"},{"comment":"The caption calls sobol an 'optimizer' that 'proposes arms uniformly randomly'; it is a quasi-random sampling method, not an optimizer, and the wording should be corrected.","section":"Figure 5 caption"},{"comment":"The sweep over M is shown without error bars or multiple runs; the claim that performance 'stabilizes around M=30' is based on point estimates and needs statistical support.","section":"Appendix B, Figure 7"},{"comment":"The text reports '1.2 · 106' function evaluations, which appears to be a typographical error for 1.2 × 10^6.","section":"Section 3.3"},{"comment":"The paper should state explicitly that the stagger proposal is log-uniform on [10^{-6}, 1] and provide its density; the current description 's = e^{-kU}' requires the reader to infer the range and normalization.","section":"Section 2, Algorithm 1"}],"recommendation":"reject","confidential_remarks":"The paper's central theoretical claim—that STS samples from p*(x)—is invalidated by the asymmetric proposal and by the pairwise GP acceptance rule. These are not local presentation issues; they affect the title, abstract, and Section 2. The empirical results may describe a useful heuristic, but as submitted the manuscript is not sound enough for archival publication. I would encourage the authors to either (a) correct the sampler by adding a Hastings correction and re-evaluating, or (b) reframe STS as an approximate/heuristic acquisition method with careful benchmarking, and to release code and full experimental details."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: there is a real algorithm here with broad experiments, but the paper's central claim—that STS samples from p*(x)—is false as written. The stagger proposal is not symmetric, and the Metropolis step omits the Hastings correction, so even a fully mixed chain targets the wrong distribution.\n\nWhat is new and good: STS is a simple two-line modification of PSS (initialize at the GP mean's maximizer, use a log-uniform perturbation). The ablations are genuinely useful; each modification shows a measurable effect. The empirical comparison across nine test functions, several dimensions, and repeated random distortions is broad, and STS beating TS, EI, UCB, TuRBO, and others on those benchmarks is a concrete result. The MTV+STS combination is also sensible and adds value beyond a standalone acquisition.\n\nThe soft spots are real. Algorithm 1 proposes x' = x + s(xt - x) with xt uniform and s log-uniform. The paper calls the log-uniform a symmetric proposal; it is not. For fixed s the map has Jacobian s^{-d}, and the allowable s-interval depends on x and x' asymmetrically. The stress-test's one-dimensional example is correct: from x=0.1 to 0.5 is five times more likely than the reverse under a uniform target. So the chain's stationary distribution is not p*. The paper's Appendix A admits the std(p_max) diagnostic is necessary but not sufficient. That is honest, but it does not fix the math. Two smaller issues: M=30 is tuned on the same nine functions used in the evaluation, and no code is released. Those matter for reproducibility.\n\nIs the empirical result salvageable? Possibly. The sampler may be a decent heuristic for BO, but it is not Thompson sampling in the sense of drawing from p*. The paper should either add a Hastings correction to restore detailed balance (which changes the algorithm and its cost), or rewrite the claims around an empirical heuristic. As written, the title and abstract overstate what is established.\n\nWho this is for: researchers working on high-dimensional BO acquisition functions. They would get a useful heuristic and a cautionary example of why proposal symmetry matters in MCMC. It deserves a serious referee—the experiments are large and the idea concrete—but the referee should insist on resolving the convergence question and releasing code before acceptance. I would not cite it in its current form.","headline":"The algorithm is empirically promising and the ablations are solid, but the claim that STS samples from p*(x) is false: the stagger proposal is asymmetric and the Hastings correction is missing.","tokens_in":9651,"tokens_out":2803,"would_cite":false,"duration_ms":23614,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that Stagger Thompson Sampling (STS), a Hit-and-Run Markov-chain sampler with a log-uniform 'stagger' proposal and a start at the GP mean's maximizer, produces more precise Thompson samples in Bayesian optimization while…","keywords":["Thompson sampling","Bayesian optimization","Gaussian processes","Hit-and-Run sampler","Metropolis-Hastings","acquisition functions","high-dimensional optimization","batch Bayesian optimization"],"falsifier":"Take a low-dimensional GP with a known posterior, run STS for $M=30$ iterations many times, and compare the empirical distribution of arms against a high-accuracy reference for $p^*(x)$ computed by dense-grid or exhaustive Monte Carlo integration; a substantial total-variation distance, or a clear increase in a standard MCMC mixing diagnostic with the number of iterations, would refute the claim that STS samples from $p^*$. A second check would time STS against standard TS with 10,000 candidates on the same GP: if TS already achieves the same or better precision in less wall-clock time, the speed claim fails.","tokens_in":8642,"feed_emoji":"🎯","tokens_out":9152,"duration_ms":79272,"temperature":0.7,"pith_summary":"Bayesian optimization aims to find a good configuration with few measurements, and Thompson sampling (TS) draws a new arm proportionally to the probability, $p^*(x)$, that the arm is the global maximizer under the current model. This paper argues that standard TS implementations fail in continuous domains because uniform candidate points almost never land near the maximizer, especially in high dimension. It proposes Stagger Thompson Sampler (STS), a short Markov-chain walk that starts at the point maximizing the GP mean, $\\tilde{x}^*=\\arg\\max_x\\mu(x)$, and perturbs it along lines to random targets with log-uniform step lengths, accepting a move when a single joint GP draw at the proposal beats the current point. The paper's claim is that STS samples are closer to the true maximizer than TS samples, are generated faster, and make STS outperform TS, PSS, EI, UCB, GIBBON, and TuRBO on nine distorted test functions from dimension 3 to 300, while matching PSS when plugged into the MTV batch-design method.","feed_headline":"Stagger sampler outdoes Thompson sampling from 3 to 300 dimensions","feed_subtitle":"A log-uniform walk started at the GP mean finds maxima faster than standard Thompson sampling, even at 300 dimensions.","key_machinery":"The carrying object is $p^*(x)$, the probability that a position $x$ is the global maximizer of the Gaussian process model; the ideal Thompson acquisition is a draw from $p^*$, and STS is an engine for approximating those draws. The engine combines three parts: (1) a Hit-and-Run Markov chain that moves along lines from the current point to uniformly random targets inside $[0,1]^d$; (2) a 'stagger' proposal whose step length is log-uniform, $s \\sim e^{-kU}$, chosen so a single scale parameter $k=\\ln 10^{-6}$ covers both tiny and large perturbations without adaptation; and (3) a Metropolis-style acceptance step that uses one joint GP sample at the pair of points, accepting whichever has the higher draw. The whole loop runs about $M=30$ times and returns the final point as an approximate Thompson arm.","core_discovery":"The paper's central discovery is that a useful Thompson sample can be computed by a short Metropolis-Hastings walk rather than by maximizing a GP draw over a large set of i.i.d. candidates. The walk, STS, starts at $\\tilde{x}^* = \\arg\\max_x\\mu(x)$, and in each of $M \\approx 30$ iterations chooses a target $x_t \\sim U([0,1]^d)$ and a step length $s \\sim e^{-k U([0,1])}$ with $k=\\ln 10^{-6}$, proposing $x'_a = x_a + s(x_t - x_a)$. The proposal is accepted if $y' > y$ for a single joint GP sample $[y,y'] \\sim \\mathrm{GP}([x_a,x'_a])$, an approximation to the Metropolis ratio that the paper calls iterated Thompson sampling. The experiments reported in the paper are designed to show that this produces arms with smaller RMSE to the true maximizer than standard TS, at lower wall-clock cost, and that the resulting acquisition scores highest in rank-based comparisons across dimensions.","pith_inferences":["If STS's mixing assumption holds, the single-joint-GP-draw acceptance filter is a general recipe: any model with cheap paired draws could be used to build approximate Thompson samplers, so the idea is not GP-specific.","A natural test not run in the paper is to replace the single joint draw with an exact Metropolis ratio estimated by many Monte Carlo samples and compare mixing; if the exact-ratio chain does not mix materially better, the single-draw filter is not the main source of bias.","The rank-based score used in the experiments may obscure absolute objective gains; an unpublished but testable comparison is simple-regret curves (best value versus evaluations) on the same distorted test functions.","STS's lack of an initialization requirement suggests a unified acquisition for both initial design and later batches in MTV+STS, potentially removing Sobol seeding from batch BO."],"forward_implications":["Standard TS's candidate flood can be replaced by roughly 30 short walk iterations per arm, cutting per-arm computation while improving precision.","STS works without modification in dimensions 3 to 300, so high-dimensional Bayesian optimization does not require a trust region or a separate adaptation phase for this acquisition method.","STS is a drop-in replacement for PSS inside MTV: the paper reports that mtv+sts matches mtv across dimensions and batch sizes, while also performing well as a standalone sampler.","Because STS starts from $\\tilde{x}^*$ and uses log-uniform steps, its samples concentrate near the current best guess; the appendix attributes the improvement over TS to reduced scale of the sample distribution rather than to reduced bias."],"supporting_citations":[{"why":"Introduces PSS and the MTV batch-design objective that STS improves upon and is compared against as a drop-in input.","marker":"[17]"},{"why":"Provides the Hit-and-Run sampler that forms the Markov-chain basis of STS.","marker":"[19]"},{"why":"Supplies the Metropolis filter that STS approximates with a joint GP sample.","marker":"[7]"},{"why":"Contributes the stagger (log-uniform) proposal used for perturbation lengths.","marker":"[21]"},{"why":"Defines the Gaussian process model whose joint samples drive the acceptance rule and the optimization.","marker":"[16]"},{"why":"Defines Thompson sampling as drawing an arm according to the probability it is optimal, the ideal STS tries to approximate.","marker":"[22]"},{"why":"Is the standard Thompson-sampling-for-BO implementation that STS is claimed to beat in speed and precision.","marker":"[9]"},{"why":"Is the trust-region high-dimensional BO method used as a leading baseline in the experiments.","marker":"[6]"}],"fun_headline_variants":["Stagger Sampler: faster, sharper Thompson sampling for BO","30-step walk beats classic Thompson sampling in BayesOpt","Metropolis walk refines Thompson sampling for optimization","Stagger Thompson Sampler outruns TS across dimensions","Short walk to the optimum: improved Thompson sampling"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on the assumption that Algorithm 1's short Markov chain, started at the GP mean's maximizer and filtered by one joint GP draw per step, actually converges to $p^*(x)$; the paper offers no mixing proof, and its Appendix A check (low standard deviation of estimated $p_{\\max}$ values) is explicitly a necessary condition, not a sufficient one.","fun_headline_variants_meta":{"raw":{"variants":["Stagger Sampler: faster, sharper Thompson sampling for BO","30-step walk beats classic Thompson sampling in BayesOpt","Metropolis walk refines Thompson sampling for optimization","Stagger Thompson Sampler outruns TS across dimensions","Short walk to the optimum: improved Thompson sampling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000205,"raw_usage":{"total_tokens":1387,"prompt_tokens":933,"completion_tokens":454,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":549,"completion_tokens_details":{"reasoning_tokens":377}},"tokens_in":549,"tokens_out":454,"duration_ms":5140,"temperature":1.0,"reasoning_tokens":377,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:32:28.259045+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a low-dimensional GP with a known posterior, run STS for $M=30$ iterations many times, and compare the empirical distribution of arms against a high-accuracy reference for $p^*(x)$ computed by dense-grid or exhaustive Monte Carlo integration; a substantial total-variation distance, or a clear increase in a standard MCMC mixing diagnostic with the number of iterations, would refute the claim that STS samples from $p^*$. A second check would time STS against standard TS with 10,000 candidates on the same GP: if TS already achieves the same or better precision in less wall-clock time, the speed claim fails.","supporting_citations":[{"cited_title":"Optimal Initialization of Batch Bayesian Optimization","cited_arxiv_id":"2404.17997","evidence_quote":"Introduces PSS and the MTV batch-design objective that STS improves upon and is compared against as a drop-in input."},{"cited_title":"The hit-and-run sampler: a globally reaching Markov chain sampler for generating arbitrary multivariate distributions","cited_arxiv_id":null,"evidence_quote":"Provides the Hit-and-Run sampler that forms the Markov-chain basis of STS."},{"cited_title":"Gilks, S","cited_arxiv_id":null,"evidence_quote":"Supplies the Metropolis filter that STS approximates with a joint GP sample."},{"cited_title":"Stagger-and-Step Method: Detecting and Computing Chaotic Saddles in Higher Dimensions","cited_arxiv_id":null,"evidence_quote":"Contributes the stagger (log-uniform) proposal used for perturbation lengths."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the Gaussian process model whose joint samples drive the acceptance rule and the optimization."},{"cited_title":"Parallelised Bayesian Optimisation via Thompson Sampling","cited_arxiv_id":null,"evidence_quote":"Is the standard Thompson-sampling-for-BO implementation that STS is claimed to beat in speed and precision."},{"cited_title":"Scalable Global Optimization via Local Bayesian Optimization","cited_arxiv_id":null,"evidence_quote":"Is the trust-region high-dimensional BO method used as a leading baseline in the experiments."}],"review_version":1}