Self-Balancing Sequential Sampling: Fast Convergence with Controlled Predictability

• URL: http://arxiv.org/abs/2607.20818v1
• Date: Thu, 23 Jul 2026 01:10:42 GMT
• Title: Self-Balancing Sequential Sampling: Fast Convergence with Controlled Predictability
• Abstract summary: sequential sampling rules that adaptively bias sampling probabilities in order to achieve faster convergence of the empirical distribution to a desired target law.<n>Self-balancing sampler is simple to implement, arises naturally among a class of Markovian samplers.<n>Results support a practical framework for reducing repeated selections and long gaps in coverage without making future selections overly predictable.
• Score: 0.7734726150561088
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Amortized Bandwidth Learning for Kernel Density Estimation under Logarithmic Score [0.0]
  An amortized framework is proposed that learns mapping across a distribution of density-estimation tasks by optimizing the logarithmic score.<n>Experiments under Gaussian sampling, a multi-family benchmark, and randomized Gaussian-mixture training show that the amortized selector consistently and substantially outperforms Silverman's rule.
  arXiv  Detail & Related papers  (2026-08-20T15:56:59Z)
• Precise: SDE-Consistent Stochastic Sampling for RL Post-Training of Flow-Matching Models [56.67321805551389]
  Reinforcement learning (RL) has become an effective way to improve prompt alignment and perceptual quality in diffusion and flow-matching generators.<n>The sampler, controlling the exploration behavior and denoising dynamics, is thus part of the policy.<n>We propose a new sampler that balances effective exploration with stability.
  arXiv  Detail & Related papers  (2026-05-22T11:37:22Z)
• Bridge Matching Sampler: Scalable Sampling via Generalized Fixed-Point Diffusion Matching [38.70740405520393]
  Bridge Matching Sampler (BMS) enables learning a transport map between arbitrary prior and target distributions with a single, scalable, and stable objective.<n>We demonstrate that our method enables sampling at unprecedented scales while preserving mode diversity, achieving state-of-the-art results on complex synthetic densities and high-dimensional molecular benchmarks.
  arXiv  Detail & Related papers  (2026-02-28T08:00:38Z)
• Sharp Convergence Rates for Masked Diffusion Models [53.117058231393834]
  We develop a total-variation based analysis for the Euler method that overcomes limitations.<n>Our results relax assumptions on score estimation, improve parameter dependencies, and establish convergence guarantees.<n>Overall, our analysis introduces a direct TV-based error decomposition along the CTMC trajectory and a decoupling-based path-wise analysis for FHS.
  arXiv  Detail & Related papers  (2026-02-26T00:47:51Z)
• Learnable Chernoff Baselines for Inference-Time Alignment [64.81256817158851]
  We introduce Learnable Chernoff Baselines as a method for efficiently and approximately sampling from exponentially tilted kernels.<n>We establish total-variation guarantees to the ideal aligned model, and demonstrate in both continuous and discrete diffusion settings that LCB sampling closely matches ideal rejection sampling.
  arXiv  Detail & Related papers  (2026-02-08T00:09:40Z)
• Wedge Sampling: Efficient Tensor Completion with Nearly-Linear Sample Complexity [9.42598427201735]
  We introduce Wedge Sampling, a new non-adaptive sampling scheme for low-rank tensor completion.<n>We study recovery of an order-$k low-rank tensor of dimension $n times cdots times n$ from a subset of its entries.
  arXiv  Detail & Related papers  (2026-02-05T16:47:13Z)
• Achieving $\varepsilon^{-2}$ Dependence for Average-Reward Q-Learning with a New Contraction Principle [13.418969441591882]
  We present the convergence rates of synchronous and asynchronous Q-learning for average-reward Markov decision processes.<n>At the core of our analysis is the construction of an instance-dependent seminorm and showing that, after a lazy transformation of the Markov decision process, the Bellman operator becomes one-step contractive under this seminorm.
  arXiv  Detail & Related papers  (2026-01-29T05:54:31Z)
• Can Continuous-Time Diffusion Models Generate and Solve Globally Constrained Discrete Problems? A Study on Sudoku [0.0]
  We use completed Sudoku grids as a controlled testbed, treating them as a subset of a continuous relaxation space.<n>We show that score-based samplers are the most reliable among continuous-time methods, and DDPM-style ancestral sampling achieves the highest validity overall.
  arXiv  Detail & Related papers  (2026-01-28T08:26:54Z)
• Scaling Adversarial Training via Data Selection [0.0]
  We propose emphSelective Adversa Training, which perturbs only a subset of critical samples in each minibatch.<n>Experiments on MNIST and CIFAR-10 show that the proposed methods achieve robustness comparable to, or even exceeding, full PGD adversarial training.
  arXiv  Detail & Related papers  (2025-12-26T15:50:33Z)
• Flipping Against All Odds: Reducing LLM Coin Flip Bias via Verbalized Rejection Sampling [59.133428586090226]
  Large language models (LLMs) can often accurately describe probability distributions using natural language.<n>This mismatch limits their use in tasks requiring reliableity, such as Monte Carlo methods, agent-based simulations, and randomized decision-making.<n>We introduce Verbalized Rejection Sampling (VRS), a natural-language adaptation of classical rejection sampling.
  arXiv  Detail & Related papers  (2025-06-11T17:59:58Z)
• Theory on Score-Mismatched Diffusion Models and Zero-Shot Conditional Samplers [49.97755400231656]
  We present the first performance guarantee with explicit dimensional dependencies for general score-mismatched diffusion samplers.<n>We show that score mismatches result in an distributional bias between the target and sampling distributions, proportional to the accumulated mismatch between the target and training distributions.<n>This result can be directly applied to zero-shot conditional samplers for any conditional model, irrespective of measurement noise.
  arXiv  Detail & Related papers  (2024-10-17T16:42:12Z)
• Breaking the Spurious Causality of Conditional Generation via Fairness Intervention with Corrective Sampling [77.15766509677348]
  Conditional generative models often inherit spurious correlations from the training dataset. This can result in label-conditional distributions that are imbalanced with respect to another latent attribute. We propose a general two-step strategy to mitigate this issue.
  arXiv  Detail & Related papers  (2022-12-05T08:09:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.