# The Sample Complexity of Approximate Rejection Sampling with Applications to Smoothed Online Learning

arXiv: https://arxiv.org/abs/2302.04658 · HTML: https://mlsanity.com/paper/2302.04658/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 77 references that are in the map.
- First posted on arXiv 9 Feb 2023.

## Builds on (most cited first, 13 of 13)

- [Resampled Priors for Variational Autoencoders](https://mlsanity.com/paper/1810.11428/) (2018)
- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [Smoothed Online Learning is as Easy as Statistical Learning](https://mlsanity.com/paper/2202.04690/) (2022)
- [Smoothed Analysis of Online and Differentially Private Learning](https://mlsanity.com/paper/2006.10129/) (2020)
- [The Computational Power of Optimization in Online Learning](https://mlsanity.com/paper/1504.02089/) (2015)
- [Reparameterization Gradients through Acceptance-Rejection Sampling Algorithms](https://mlsanity.com/paper/1610.05683/) (2016)
- [Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries](https://mlsanity.com/paper/2202.08549/) (2022)
- [Local Differential Privacy Is Equivalent to Contraction of Eγ-Divergence](https://mlsanity.com/paper/2102.01258/) (2021)
- [Majorizing Measures, Sequential Complexities, and Online Learning](https://mlsanity.com/paper/2102.01729/) (2021)
- [Variational Rejection Sampling](https://mlsanity.com/paper/1804.01712/) (2018)
- [Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions](https://mlsanity.com/paper/2205.13056/) (2022)
- [Smoothed Online Learning for Prediction in Piecewise Affine Systems](https://mlsanity.com/paper/2301.11187/) (2023)
- [Approximating the Permanent with Deep Rejection Sampling](https://mlsanity.com/paper/2108.07359/) (2021)

## Built on by (most cited first, 13 of 13)

- [On the Performance of Empirical Risk Minimization with Smoothed Data](https://mlsanity.com/paper/2402.14987/) (2024)
- [Oracle-Efficient Differentially Private Learning with Public Data](https://mlsanity.com/paper/2402.09483/) (2024)
- [Some Notes on the Sample Complexity of Approximate Channel Simulation](https://mlsanity.com/paper/2405.04363/) (2024)
- [Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Training](https://mlsanity.com/paper/2511.07372/) (2025)
- [Smooth Nash Equilibria: Algorithms and Complexity](https://mlsanity.com/paper/2309.12226/) (2023)
- [Best-of-Tails: Bridging Optimism and Pessimism in Inference-Time Alignment](https://mlsanity.com/paper/2603.06797/) (2026)
- [From Curiosity to Caution: Mitigating Reward Hacking for Best-of-N with Pessimism](https://mlsanity.com/paper/2604.04648/) (2026)
- [Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks](https://mlsanity.com/paper/2504.10598/) (2025)
- [Accelerating Diffusion Sampling via Speculative Draft Trees](https://mlsanity.com/paper/2609.17691/) (2026)
- [Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness](https://mlsanity.com/paper/2602.20585/) (2026)
- [Partition Function Estimation under Bounded f-Divergence](https://mlsanity.com/paper/2602.23535/) (2026)
- [Inference-Time Nash Alignment](https://mlsanity.com/paper/2609.08082/) (2026)
- [Uniform Race: Parameter-Free Approximate Rejection Sampling](https://mlsanity.com/paper/2609.34639/) (2026)

## Abstract (arXiv)

Suppose we are given access to n independent samples from distribution μ and we wish to output one of them with the goal of making the output distributed as close as possible to a target distribution nu. In this work we show that the optimal total variation distance as a function of n is given by tildeTheta(fracDf'(n)) over the class of all pairs nu,μ with a bounded f-divergence Df(nu|μ)≤ D. Previously, this question was studied only for the case when the Radon-Nikodym derivative of nu with respect to μ is uniformly bounded. We then consider an application in the seemingly very different field of smoothed online learning, where we show that recent results on the minimax regret and the regret of oracle-efficient algorithms still hold even under relaxed constraints on the adversary (to have bounded f-divergence, as opposed to bounded Radon-Nikodym derivative). Finally, we also study efficacy of importance sampling for mean estimates uniform over a function class and compare importance sampling with rejection sampling.