REVIEW 3 major objections 4 minor 35 references
A sequential sampling rule that downweights recently drawn outcomes converges to any target distribution at the optimal O(1/n) rate while keeping the next draw hard to anticipate.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
T0 review · deepseek-v4-flash
2026-08-01 09:17 UTC pith:ZBPL5L3F
load-bearing objection The O(1/n) convergence theorem and the OU diffusion limits are solid and new; the general-d predictability claims are honest but unfinished and currently oversold in the abstract. the 3 major comments →
Self-Balancing Sequential Sampling: Fast Convergence with Controlled Predictability
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The central claim is that the self-balancing sampler—defined recursively by sampling from the current distribution, then downweighting the sampled outcome's probability by a factor α∈(0,1) and renormalizing—converges at the optimal rate: E||μ(n)-p*||_TV = O(1/n), with worst-case O(log n/n) almost surely, compared with the Θ(1/√n) of iid sampling. The same rule is shown to be the unique solution of an entropy-regularized convex optimization problem that trades one-step reduction of a quadratic count-imbalance loss against the entropy of the next draw, and equivalently a step of entropic stochastic mirror descent. In the weak-biasing regime β→0, the centered counts converge to an Ornstein-Uhle
What carries the argument
The engine of the paper is the exponential softmax form p_i(n) ∝ p_i(0) e^{-β_i N_i(n)}, where N_i(n) is the number of times outcome i has been drawn. This single formula is the 'downweight the selected outcome and renormalize' update; it makes the sampling probabilities depend on raw, unbounded counts rather than proportions, which yields a positive-recurrent centered-count chain and is what allows the empirical distribution to converge at 1/n. The same formula is identified as the unique potential-based sampler satisfying a translation-invariance property, as the maximizer of H(q) - β·(one-step imbalance increase), and as an entropic mirror-descent step—three characterizations of the same
Load-bearing premise
The general-d predictability conclusions (Θ(√β) excess for tied maximizers, exponentially small gap for a unique maximizer) rest on Section 3.2's non-rigorous assumption that the centered counts' stationary fluctuations are Gaussian and that the softmax map is linearizable around the target law; if either fails, those predictability predictions are unsupported.
What would settle it
For d=3 with a target law that has two tied maximal probabilities, simulate the self-balancing sampler in the weak-bias regime and measure the adversary's long-run excess accuracy above max_i p*_i as β→0; the paper predicts a Θ(√β) scaling (equivalently √(log(1/α))), so a clearly different scaling such as Θ(β) would falsify the Gaussian-linearization heuristic behind Section 3.2. A complementary check is to estimate the stationary distribution of the projection-centered counts numerically and compare its standardized fluctuations to the predicted N(0, ω) Gaussian at small β.
If this is right
- Audit and inspection schedules can be randomized yet still guarantee that long-run testing frequencies approach any target distribution at the same asymptotic speed as a fixed round-robin list.
- In citizen-assembly and representative-sampling problems, the sampler offers a way to satisfy demographic balance constraints while preserving nearly uniform individual inclusion probabilities, avoiding the rare-class exclusion seen in deterministic quota methods.
- The explicit β-dependence of the convergence constants gives practitioners a dial: larger β (stronger biasing) improves balance, while smaller β preserves more unpredictability; time-inhomogeneous β interpolates between the IID and deterministic regimes.
- The adversarial predictability results imply that when the target law has a unique most-frequent outcome, an observer gains essentially nothing from the structure of the sampler, but tied most-likely outcomes leak information at a Θ(√β) rate.
- With fixed bias, the sampler sees every outcome in Θ(d log log d) steps, only slightly worse than deterministic and far better than coupon-collector Θ(d log d).
Where Pith is reading between the lines
- The same exponential-tilting mechanism should extend to covariate balancing by replacing counts with a cumulative covariate imbalance vector; the resulting sequential analog of the Gram-Schmidt walk would likely inherit the O(1/n) convergence whenever the tilted potential separates in the sense of Proposition 3.5, though the paper leaves this open.
- The 1/2-offset appearing in the greedy optimization (Theorem 2.9) is reminiscent of a midpoint discretization of a continuous-time control problem; a testable prediction is that a continuous-time version of the sampler would remove the offset and match the OU diffusion predictions exactly.
- The Θ(√β) excess predictability for tied maximizers is an asymptotic weak-bias statement; a practical check would be whether this scaling already appears at moderate β, which the paper's simulations only partially address.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies a sequential sampling rule in which each outcome is sampled with probability proportional to p_i(0) e^{-\beta_i N_i(n)}, so that overrepresented outcomes are downweighted. The central claims are: (i) the empirical distribution converges to the target p_i^* \propto \beta_i^{-1} at the optimal O(1/n) rate in expectation (Theorem 2.5), with O(\log n/n) almost surely (Theorem 2.7); (ii) the rule is characterized by invariance and by entropy-regularized optimization problems (Theorems 2.8--2.11); (iii) the cover time is \Theta(d\log\log d) (Theorem 2.12); and (iv) in the weak-biasing regime, centered counts converge to Ornstein--Uhlenbeck diffusions (Propositions 3.1--3.2), which are then used heuristically to derive predictability scalings for an adversarial guesser (Section 3.2). The main proofs are in Appendix B. The paper is well written and the convergence part is supported by substantial, genuine arguments.
Significance. If the central convergence theorem holds, the result is significant: it shows that a simple adaptive random rule attains the deterministic O(1/n) rate of convergence of the empirical distribution while retaining randomness, and with explicit dependence on the biasing parameters. The optimization characterizations and the cover-time result are also valuable, and the diffusion limits provide a useful framework for biased-coin designs. The paper also ships simulation code and gives an extended citizen's-assembly application, which strengthens the practical relevance. The main weakness is that the advertised 'controlled predictability' results for general d are only heuristic; only the d=2 tied-maximizer case is stated as a lemma, and even that proof uses unquantified approximations. The paper's genuine contributions are the convergence theorems and the optimization/diffusion structure, not the general-d predictability scalings as rigorous statements.
major comments (3)
- [Section 3.2 and Appendix A.2] The general-d predictability scalings are not established. The argument beginning 'Using the fact \langle Z,p^*\rangle=0' replaces the stationary law of the centered counts by the Gaussian N(0,\omega) and then linearizes the softmax map; the text itself labels this non-rigorous. There is no theorem controlling either the error in the stationary-distribution approximation or the O(h) remainder in p(c_\beta+\sqrt{h}Z)=p^*+\sqrt{h}J_\beta Z+O(h) when h=\beta. Since the tied-maximizer excess is first order in \sqrt{\beta}, a non-Gaussian stationary fluctuation or a non-uniform Taylor remainder could change the constant or the exponent. Appendix A.2 ('we showed these scalings') therefore overstates what is proved. Either prove the claims (for example, via a stationary CLT plus Edgeworth or Stein-type bounds) or state them explicitly as conjectures and adjust the abstract and Section 3.2 accor
- [Appendix B.6, Lemma 3.4] Even the d=2 tied case is not proven rigorously as written. The proof expands 1/(1+e^x) and then says a 'standard Riemann sum comparison' implies that the discrete stationary law is well approximated by a continuous mixture, Y \approx \xi/2 + \beta^{-1/2}G, after which folded-normal moments are used. No error bounds are supplied for either the Riemann-sum approximation or the moment asymptotics. Because Lemma 3.4 is the only formal finite-d result behind the \Theta(\sqrt{\beta}) predictability claim, the proof should be completed with explicit estimates (for example, via Poisson summation or discrete normal tail bounds).
- [Section 3.2, unique-maximizer claim] The exponential gap for a unique maximizer is asserted but not proved in any form. The text reasons heuristically that Z_i must be of order \Delta^*/\sqrt{h} and then uses a Gaussian tail estimate. There is no theorem, and no control of the event that the true stationary law deviates from the OU law on this large-deviation scale. If this claim remains in the introduction as an advertised result, it needs a proof or an explicit conjecture label.
minor comments (4)
- [Section 3.2] The scaling variable h is not defined in this section. The diffusion results use h as the time-step parameter with h\to 0, while the predictability formulas seem to substitute h=\beta. This should be made explicit, since the two limits are not interchangeable without additional argument.
- [Appendix A.2] The phrase 'we showed these scalings' is too strong for results that are labeled non-rigorous in Section 3.2. Please use 'we heuristically argued' or 'our simulations are consistent with'.
- [Section 2.4, Theorem 2.9] The optimizer in Theorem 2.9 is the 1/2-offset policy p_i(n)\propto p_i(0)e^{-\beta_i(N_i(n)+1/2)}, not the original sampler. This is explained in the text, but the wording 'is the self-balancing sampling method' could mislead; consider calling it the 'offset self-balancing policy' throughout.
- [Appendix B.5, proof of Proposition 3.1] The notation p^{\beta h}_i is introduced without definition; it is evidently the sampling probability under the rescaled parameters \beta h. Please define it.
Circularity Check
No circular derivation found: the O(1/n) theorem, optimization characterizations, and diffusion limits are self-contained formal results; the non-rigorous general-d predictability heuristics are explicitly disclaimed and are not fits of the quantities they predict.
full rationale
The paper's central convergence theorem (Thm 2.5) is proved in App. B.2 by a self-contained Foster–Lyapunov drift argument with an explicit quantitative specialization of Pemantle–Rosenthal. The proof does not assume the O(1/n) rate, and p* enters only as the centering target defined from β; the TV distance is expressed as ||Y(n)||_1/(2n) and bounded through a drift condition on E||Y||. Similarly, Thm 2.7 is a Borel–Cantelli argument on log-odds ratios; Prop. 2.1 is a local uniqueness theorem with its own proof; Thms 2.8–2.11 are direct optimization calculations; Thm 3.5 assumes a general exponential-family condition and proves the same rate. No step fits parameters to the quantity being predicted: the β parameters are design choices, and p* is defined from them, not estimated. The general-d predictability claims rest on Section 3.1/3.2, which explicitly say "This section is non-rigorous" and "Again, the following section is non-rigorous, but aims to add some heuristic evidence"; the Gaussian/softmax linearization is presented as a heuristic ansatz rather than hidden in a citation. App. A provides simulations that check the scaling predictions but do not fit the constants and then call them predictions. The only concerns are rigor/overstatement (e.g., App. A.2 says "we showed" the Θ(√β)/exponential scalings when Sec. 3.2 is labeled non-rigorous, and the d≥3 diffusion approximation is uncontrolled), which are correctness risks, not circularity. There are no self-citations or prior-work uniqueness theorems invoked as external facts. Accordingly the circularity score is 0.
Axiom & Free-Parameter Ledger
free parameters (2)
- β_i (or α_i = e^{-β_i}) biasing parameters =
not fitted; user-chosen, with max_i β_i ≤ 1 used in Theorem 2.5
- p(0) initial sampling distribution =
not fitted; user-chosen in the full-support simplex
axioms (6)
- domain assumption Full-support initial distribution p(0) ∈ Δ^d_+
- domain assumption Log-convexity or log-concavity of potentials in Proposition 2.1
- standard math Standard Markov chain drift criteria (Foster-Lyapunov, Pemantle-Rosenthal)
- standard math Ergodic theorem for irreducible positive-recurrent countable Markov chains
- standard math Diffusion approximation theorem (Durrett §8.7)
- ad hoc to paper Stationary Gaussian approximation for centered counts in Section 3.2
read the original abstract
Many instances of sequential sampling, including audit and inspection scheduling, representative sampling, and treatment assignment, require selections to be distributed evenly without becoming easy to anticipate or exploit. We study a family of sequential sampling rules that adaptively bias sampling probabilities in order to achieve faster convergence of the empirical distribution to a desired target law, while keeping the resulting samples as unpredictable as possible. The resulting self-balancing sampler is simple to implement, arises naturally among a class of Markovian samplers sharing a certain invariance property, and admits a stochastic mirror-descent interpretation. Our main results show that (i) this self-balancing sampler converges at the fastest possible $O(n^{-1})$ rate with explicit dependence on biasing parameters, beating the standard $O(n^{-1/2})$ rate of IID sampling, (ii) it is the unique solution to a natural entropy-regularized optimization problem which balances the convergence rate of the empirical law and the unpredictability of the samples, and (iii) in the weak-biasing regime, the properly centered counts process converges to an Ornstein-Uhlenbeck process in the diffusive limit. Together, these results support a practical framework for reducing repeated selections and long gaps in coverage without making future selections overly predictable.
Figures
Reference graph
Works this paper leans on
-
[1]
Rosenthal , title =
Robin Pemantle and Jeffrey S. Rosenthal , title =. Stochastic Processes and their Applications , volume =. 1999 , doi =
1999
-
[2]
Probability Surveys , volume =
Pemantle, Robin , title =. Probability Surveys , volume =. 2007 , month =. doi:10.1214/07-PS094 , url =
-
[3]
Etheridge , title =
Alison M. Etheridge , title =. 2011 , doi =
2011
-
[4]
1996 , isbn =
Richard Durrett , title =. 1996 , isbn =
1996
-
[5]
Bertsekas , title =
Dimitri P. Bertsekas , title =
-
[6]
Advances in Neural Information Processing Systems , editor =
Todorov, Emanuel , title =. Advances in Neural Information Processing Systems , editor =. 2006 , url =
2006
-
[7]
2025 , eprint =
Ajinkya Bhole and Mohammad Mahmoudi Filabadi and Guillaume Crevecoeur and Tom Lefebvre , title =. 2025 , eprint =
2025
-
[8]
Journal of Machine Learning Research , volume =
Haoran Wang and Thaleia Zariphopoulou and Xun Yu Zhou , title =. Journal of Machine Learning Research , volume =
-
[9]
Theodorou , title =
Oswin So and Ziyi Wang and Evangelos A. Theodorou , title =. 2022 , eprint =
2022
-
[10]
2018 , eprint =
Tuomas Haarnoja and Aurick Zhou and Pieter Abbeel and Sergey Levine , title =. 2018 , eprint =
2018
-
[11]
2022 , eprint =
Emanuele Sansone , title =. 2022 , eprint =
2022
-
[12]
2017 , eprint =
Giacomo Zanella , title =. 2017 , eprint =
2017
-
[13]
Ortega and Daniel A
Pedro A. Ortega and Daniel A. Braun and Justin Dyer and Kee-Eung Kim and Naftali Tishby , title =. 2015 , eprint =
2015
-
[14]
Fair algorithms for selecting citizens' assemblies , journal =
Bailey Flanigan and Paul G. Fair algorithms for selecting citizens' assemblies , journal =. 2021 , doi =
2021
-
[15]
Spielman and Peng Zhang , title =
Christopher Harshaw and Fredrik Sävje and Daniel A. Spielman and Peng Zhang , title =. Journal of the American Statistical Association , volume =. 2024 , publisher =. doi:10.1080/01621459.2023.2285474 , URL =
arXiv 2024
-
[16]
Theory of Computing , volume =
Nikhil Bansal and Daniel Dadush and Shashwat Garg and Shachar Lovett , title =. Theory of Computing , volume =. 2019 , doi =
2019
-
[17]
Lauritzen, Fredrik and Holden, Geir , year=. Intelligence-based doping control planning improves testing effectiveness: Perspectives from a national anti-doping organisation , journal =. doi:https://doi.org/10.1002/dta.3435 , url =
-
[18]
Buchholz, U. and Run, G. and Kool, J. L. and Fielding, J. and Mascola, L. , title =. Journal of Food Protection , year =. doi:10.4315/0362-028X-65.2.367 , pmid =
-
[19]
Pocock, S. J. and Simon, R. , title =. Biometrics , year =
-
[20]
Shan, Guogen and Li, Yilong and Lu, Xiaohan and Zhang, Yifan and Wu, S. S. , title =. BMC Medical Research Methodology , year =. doi:10.1186/s12874-024-02151-3 , pmid =
-
[21]
Advances in Applied Probability , author=
Linear de-preferential urn models , volume=. Advances in Applied Probability , author=. 2018 , pages=. doi:10.1017/apr.2018.55 , number=
-
[22]
Advances in Applied Mathematics , volume=
Negatively reinforced balanced urn schemes , author=. Advances in Applied Mathematics , volume=. 2019 , publisher=
2019
-
[23]
2024 , eprint=
Self-Repellent Random Walks on General Graphs -- Achieving Minimal Sampling Variance via Nonlinear Markov Chains , author=. 2024 , eprint=
2024
-
[24]
Rafael A. Rosales and Fernando P.A. Prado and Benito Pires , keywords =. Vertex reinforced random walks with exponential interaction on complete graphs , journal =. 2022 , issn =. doi:https://doi.org/10.1016/j.spa.2022.03.007 , url =
-
[25]
Forcing a Sequential Experiment to be Balanced , urldate =
Bradley Efron , journal =. Forcing a Sequential Experiment to be Balanced , urldate =
-
[26]
Smith , journal =
Richard L. Smith , journal =. Sequential Treatment Allocation Using Biased Coin Designs , urldate =
-
[27]
Atkinson, Anthony C. , title =. Journal of the Royal Statistical Society: Series A (Statistics in Society) , volume =. doi:https://doi.org/10.1111/1467-985X.00564 , url =. https://rss.onlinelibrary.wiley.com/doi/pdf/10.1111/1467-985X.00564 , abstract =
-
[28]
Journal of the Royal Statistical Society: Series C (Applied Statistics) , volume =
Antognini, Alessandro Baldi and Giovagnoli, Alessandra , title =. Journal of the Royal Statistical Society: Series C (Applied Statistics) , volume =. doi:https://doi.org/10.1111/j.1467-9876.2004.00436.x , url =. https://rss.onlinelibrary.wiley.com/doi/pdf/10.1111/j.1467-9876.2004.00436.x , abstract =
arXiv 2004
-
[29]
Rosenberger , title =
Tigran Markaryan and William F. Rosenberger , title =. The Annals of Statistics , number =. 2010 , doi =
2010
-
[30]
Donsker, M. D. and Varadhan, S. R. S. , title =. Communications on Pure and Applied Mathematics , volume =. doi:https://doi.org/10.1002/cpa.3160280102 , url =. https://onlinelibrary.wiley.com/doi/pdf/10.1002/cpa.3160280102 , year =
-
[31]
Mirror descent and nonlinear projected subgradient methods for convex optimization , journal =
Amir Beck and Marc Teboulle , keywords =. Mirror descent and nonlinear projected subgradient methods for convex optimization , journal =. 2003 , issn =. doi:https://doi.org/10.1016/S0167-6377(02)00231-6 , url =
-
[32]
Nemirovski, A. and Juditsky, A. and Lan, G. and Shapiro, A. , title =. SIAM Journal on Optimization , volume =. 2009 , doi =. https://doi.org/10.1137/070704277 , abstract =
-
[33]
1996 , isbn =
Hannes Risken , title =. 1996 , isbn =
1996
-
[34]
Proceedings of the 24th International Conference on Artificial Intelligence and Statistics , series =
Husain, Hisham and Ciosek, Kamil and Tomioka, Ryota , title =. Proceedings of the 24th International Conference on Artificial Intelligence and Statistics , series =
-
[35]
and Tweedie, Richard L
Meyn, Sean P. and Tweedie, Richard L. , title =
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.