Fast Rerandomization for Balancing Covariates in Randomized Experiments: A Metropolis-Hastings Framework

• URL: http://arxiv.org/abs/2602.07613v1
• Date: Sat, 07 Feb 2026 16:40:27 GMT
• Title: Fast Rerandomization for Balancing Covariates in Randomized Experiments: A Metropolis-Hastings Framework
• Abstract summary: We propose an algorithm that achieves speedups ranging from 10 to 10,000 times while maintaining exact and validity.<n>Our proposed algorithm, PSRSRR, achieves speedups ranging from 10 to 10,000 times while maintaining exact and validity.
• Score: 12.297315057225532
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Balancing covariates is critical for credible and efficient randomized experiments. Rerandomization addresses this by repeatedly generating treatment assignments until covariate balance meets a prespecified threshold. By shrinking this threshold, it can achieve arbitrarily strong balance, with established results guaranteeing optimal estimation and valid inference in both finite-sample and asymptotic settings across diverse complex experimental settings. Despite its rigorous theoretical foundations, practical use is limited by the extreme inefficiency of rejection sampling, which becomes prohibitively slow under small thresholds and often forces practitioners to adopt suboptimal settings, leading to degraded performance. Existing work focusing on acceleration typically fail to maintain the uniformity over the acceptable assignment space, thus losing the theoretical grounds of classical rerandomization. Building upon a Metropolis-Hastings framework, we address this challenge by introducing an additional sampling-importance resampling step, which restores uniformity and preserves statistical guarantees. Our proposed algorithm, PSRSRR, achieves speedups ranging from 10 to 10,000 times while maintaining exact and asymptotic validity, as demonstrated by simulations and two real-data applications.

Related papers

• Efficient expectation value estimation for quantum circuits via extended stabilizer frameworks and adaptive variance estimation [8.759476252485507]
  We introduce an efficient simulation framework that integrates the sum-over-Clifford method with quasi-probability-based stabilizer simulation.<n>To optimize efficiency, we incorporate a circuit-adaptive reduction via variance estimation protocol.<n>We explicitly prove the sample-complexity reduction for random quantum circuits and T-doped Clifford circuits.
  arXiv  Detail & Related papers  (2026-09-13T03:08:19Z)
• Beyond Optimal Rates in Stochastic Optimization: Trajectory-Adaptive Stopping Rules [42.38093055717409]
  We develop new confidence-sequence techniques and a general time-uniform empirical Bernstein inequality for adapted processes.<n>We show that the resulting stopping rules can require several orders of fewer than natural gradient horizons.
  arXiv  Detail & Related papers  (2026-08-26T09:02:46Z)
• From Atoms to Entropy: Optimal Noise Allocation for Diffusion Training in the Convex Regime [52.459513910242485]
  We develop a general statistical framework for studying optimal noise-level allocation in diffusion training.<n>We show that the optimized training schedule admits an atomic minimizer, concentrated on finitely many noise levels.<n>We then evaluate the entropic schedule in larger-scale experiments, where full schedule optimization is currently intractable.
  arXiv  Detail & Related papers  (2026-07-10T20:59:06Z)
• Stabilizing Recurrent Dynamics for Test-Time Scalable Latent Reasoning in Looped Language Models [24.301295080069476]
  Looped Language Models (LoopLMs) enable efficient latent reasoning through depth recurrence, yet exhibit unreliable test-time scaling behavior.<n>We propose STARS (ST-driven Recurrent Scaling), a training framework that constrains latent states to approach reductionally stable fixed points.
  arXiv  Detail & Related papers  (2026-05-26T09:11:12Z)
• Taming the Instability: A Robust Second-Order Optimizer for Federated Learning over Non-IID Data [77.19117648492104]
  We present Federated Robust Curvature Optimization (FedRCO), a novel second-order optimization framework designed to improve convergence speed and reduce communication cost.<n>FedRCO addresses these challenges by integrating an efficient approximate curvature with a provable stability mechanism.<n>We show that FedRCO achieves superior robustness against diverse non-IID scenarios while achieving higher accuracy and faster convergence than both state-of-the-art first-order and second-order methods.
  arXiv  Detail & Related papers  (2026-03-30T11:37:46Z)
• Towards Anytime-Valid Statistical Watermarking [63.02116925616554]
  We develop the first e-value-based watermarking framework, Anchored E-Watermarking, that unifies optimal sampling with anytime-valid inference.<n>Our framework can significantly enhance sample efficiency, reducing the average token budget required for detection by 13-15% relative to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2026-02-19T18:32:26Z)
• RI-Loss: A Learnable Residual-Informed Loss for Time Series Forecasting [13.117430904377905]
  Time series forecasting relies on predicting future values from historical data.<n>MSE has two fundamental weaknesses: its point-wise error fails to capture temporal relationships, and it does not account for inherent noise in the data.<n>We introduce the Residual-Informed Loss (RI-Loss), a novel objective function based on the Hilbert-Schmidt Independence Criterion (HSIC)
  arXiv  Detail & Related papers  (2025-11-13T09:36:00Z)
• Penalized Empirical Likelihood for Doubly Robust Causal Inference under Contamination in High Dimensions [0.720409153108429]
  We propose a doubly robust estimator for the average treatment effect in low sample size equations.<n>We show that the proposed confidence interval remain efficient compared to those competing estimates.
  arXiv  Detail & Related papers  (2025-07-23T11:58:54Z)
• Simulation-Based Inference for Adaptive Experiments [38.841210420855276]
  Multi-arm bandit experimental designs are increasingly being adopted over standard randomized trials.<n>We propose a simulation-based approach for conducting hypothesis tests and constructing confidence intervals for arm specific means.<n>Our results show that our approach achieves the desired coverage while reducing confidence interval widths by up to 50%, with drastic improvements for arms not targeted by the design.
  arXiv  Detail & Related papers  (2025-06-03T13:46:59Z)
• Relaxed Quantile Regression: Prediction Intervals for Asymmetric Noise [51.87307904567702]
  Quantile regression is a leading approach for obtaining such intervals via the empirical estimation of quantiles in the distribution of outputs.<n>We propose Relaxed Quantile Regression (RQR), a direct alternative to quantile regression based interval construction that removes this arbitrary constraint.<n>We demonstrate that this added flexibility results in intervals with an improvement in desirable qualities.
  arXiv  Detail & Related papers  (2024-06-05T13:36:38Z)
• An Experimental Design for Anytime-Valid Causal Inference on Multi-Armed Bandits [0.0]
  This paper introduces the Mixture Adaptive Design (MAD), a new experimental design for multi-armed bandit (MAB) algorithms. MAD enables anytime-valid inference on the Average Treatment Effect (ATE) for emphany MAB algorithm.
  arXiv  Detail & Related papers  (2023-11-09T23:57:32Z)
• Semi-Parametric Inference for Doubly Stochastic Spatial Point Processes: An Approximate Penalized Poisson Likelihood Approach [3.085995273374333]
  Doubly-stochastic point processes model the occurrence of events over a spatial domain as an inhomogeneous process conditioned on the realization of a random intensity function. Existing implementations of doubly-stochastic spatial models are computationally demanding, often have limited theoretical guarantee, and/or rely on restrictive assumptions.
  arXiv  Detail & Related papers  (2023-06-11T19:48:39Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  We consider the non-AL equilibrium nonconptotic objective function in two-player zero-sum continuous games. Our novel insights into the particle-based algorithms for continuous distribution strategies are presented.
  arXiv  Detail & Related papers  (2023-03-02T05:08:15Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  We study optimization of areas under precision-recall curves (AUPRC), which is widely used for imbalanced tasks. We develop novel momentum methods with a better iteration of $O (1/epsilon4)$ for finding an $epsilon$stationary solution. We also design a novel family of adaptive methods with the same complexity of $O (1/epsilon4)$, which enjoy faster convergence in practice.
  arXiv  Detail & Related papers  (2021-07-02T16:21:52Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)

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.