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

1 Introduction

• The sampling question removes the usual requirement of a uniform upper bound on the Radon–Nikodym derivative, which can be unavailable or too large to be useful.Without that bound, exact recovery may be impossible, motivating approximate sampling.Source: §1 · p. 2
• For superlinear f-divergences, the paper establishes essentially matching upper and lower bounds for approximate rejection sampling.The lower bounds make the sample complexity essentially tight as ε decreases; when f′ is bounded above, approximate sampling is impossible under only the divergence constraint.Source: §1 · pp. 2, 4
• The paper extends minimax upper bounds and two oracle-efficient no-regret algorithms to f-smoothed online learning.Earlier analyses of these algorithms do not extend beyond the standard smoothed setting.Source: §1 · p. 4
• Modified classical rejection sampling provides an upper bound on the samples needed to achieve total variation distance at most ε from ν.The paper also establishes that von Neumann’s original sampler is essentially optimal for this problem.Source: §1 · pp. 2, 4
• An instance of FTPL has regret scaling like σ^-1/4 rather than σ^-1/2, extending a result to arbitrary context spaces.The result answers an open question in Block et al. [2022].Source: §1 · pp. 4–5
• The paper gives importance-sampling bounds for estimating target means uniformly over a function class and compares them with rejection-sampling estimates for χ²-divergence.The comparison also considers earlier bounds from Chatterjee and Diaconis [2018] and Cortes et al. [2010].Source: §1 · p. 5

• An f-divergence is defined using a convex function f satisfying f(1) = f′(1) = 0.Source: §2 · p. 5
• The central question is how many independent samples from µ are needed for a selection rule to produce an output within ε total variation of ν, given finite f-divergence.Source: §2 · p. 6
• Traditional rejection sampling forms an acceptance set S, chooses from it when nonempty, and otherwise selects an index uniformly at random.Source: §2 · p. 6

• The upper bound uses a modified version of rejection sampling, and the paper gives an almost matching lower bound.Source: §3 · p. 6
• When f′ is bounded above, finite f-divergence can leave ν singular with respect to µ, so no selection rule can approximate ν arbitrarily closely in total variation.Source: §3 · p. 8
• For superlinear f, the lower bound matches the upper bound up to logarithmic factors; a fixed pair of distributions gives a uniform-in-n bound under a mild growth condition.Source: §3 · pp. 8–9
• The lower-bound proof reduces to a bounded-likelihood-ratio comparison and uses Bernoulli distributions to exhibit the required divergence and approximation trade-off.Source: §3 · p. 8
• eΘ((f′)^-1(Df(ν||µ))/ε) samples are necessary and sufficient to generate an ε-approximate sample from ν.Source: §3 · p. 9

4 Smoothed Online Learning

• For eventually linear f, a one-dimensional threshold class can still incur linear regret under an f-smooth adversary.Proposition 8 states this for every 0 < σ < 1.Source: §4 · p. 10
• The extension uses a coupling between adaptive adversary contexts and independent base-measure samples, beyond uniformly bounded Radon–Nikodym derivatives.The section states the main result for binary-valued classes while deferring the general real-valued version to the appendix.Source: §4 · p. 10
• Renyi-smoothed adversaries admit regret bounds optimal up to polylogarithmic factors, while whether KL-smoothed regret can be improved remains open.The reported cost for bounded-away-from-1 Renyi order is only a constant factor above the standard setting; the KL guarantee is weaker.Source: §4 · p. 11
• The improper oracle-efficient algorithm uses two ERM calls per round and has regret guarantees under an (f, σ)-smoothed adversary.For KL smoothing, the stated regret scales as eO(log(d)T/(σ log(T))), which is sublinear but very slow.Source: §4 · p. 11
• Examining f-smoothed adversaries answers Block et al. [2022]’s open question by improving σ′ dependence of expected regret for FTPL with a Gaussian perturbation.For λ→∞, regret improves on [Block et al., 2022, Theorem 10] in the strongly smooth regime where the adversary’s Radon–Nikodym derivative is uniformly bounded by σ′−1.Source: §4 · p. 12
• The tightness of the oracle-efficient algorithms’ regret bounds is open, and their σ dependence may be polynomial while the statistical rate is polylogarithmic.For proper FTPL, the result applies to Renyi-smoothed adversaries with λ ≥ 2; extending it to KL smoothing is left open.Source: §4 · p. 12

A Related Work

• Earlier approximate rejection-sampling work offered qualitative tradeoffs or bounds for particular distribution families; this work gives sharp quantitative guarantees for general distributions and f-divergences.The related-work discussion also situates the learning results as a generalization of prior smoothed online learning to weaker smoothness constraints.Source: A Related Work · pp. 16–17

B Comparison to Importance Sampling for Uniform Mean Estimation

• The importance-sampling bound is developed for uniformly estimating means over bounded function classes with finite bracketing integral and finite χ2(ν||µ).The section notes that finite bracketing integral and finite pseudo-dimension are distinct class-complexity conditions.Source: B Comparison to Importance Sampling… · pp. 18, 20
• If χ2(ν||µ) is infinite, importance sampling cannot achieve Θ-rate convergence to the population mean.The cited limitation concerns importance-sampling estimators under the stated divergence condition.Source: B Comparison to Importance Sampling… · p. 21
• For finite χ2(ν||µ), rejection sampling requires eΘ(χ2(ν||µ)·ε^-3) samples for uniform ε-accurate mean estimation; importance sampling suffices with O(χ2(ν||µ)·ε^-3) samples for uniform ε-accurate estimates in expectation, while rejection sampling applies to arbitrary f-divergences.The rejection-sampling analysis is described as essentially tight, whereas the importance-sampling analysis may be loose.Source: B Comparison to Importance Sampling… · pp. 21–22
• With finite pseudo-dimension, prior bounds give importance sampling a strictly better rate than the rejection-sampling rate derived here.The section leaves extending its importance-sampling result beyond χ2 divergence to future work.Source: B Comparison to Importance Sampling… · p. 22

C Sequential Complexities and Minimax Regret

• Sequential fat-shattering complexity can greatly exceed ordinary VC complexity, with an infinite gap possible; finite domains permit a reverse bound.Distribution-dependent sequential Rademacher complexity is introduced to connect adversary distributions to online regret bounds.Source: C Sequential Complexities and Minimax… · pp. 23–24

D.1 Upper Bounds

• The upper-bound argument avoids requiring a uniform likelihood-ratio bound, which the preceding rejection-sampling lemma requires.The proof instead uses the change-of-measure bound to handle the likelihood-ratio tail.Source: §D.1 · p. 25
• A change-of-measure lemma controls the target-measure probability of large likelihood ratios using the f-divergence bound.The proof emphasizes that Markov’s inequality does not directly apply because the divergence is an expectation under µ, whereas the tail probability is under ν.Source: §D.1 · pp. 25–26
• The proof constructs a truncated target and applies rejection sampling to obtain an approximate sample from the original target.The proof’s stated conclusion gives a success event of probability at least 1 − δ on which the selected sample is within ε in total variation.Source: §D.1 · pp. 26–27

D.2 Lower Bound

• A selection rule’s output has a Radon–Nikodym derivative bounded above with respect to μ, a property used to establish lower bounds.The analysis divides the lower-bound argument into linear and superlinear f cases.Source: §D.2 · pp. 27–28
• If f-divergence is too coarse a measure of similarity, approximate sampling from ν using μ can be impossible.Theorem 31 supplies the cited example.Source: §D.2 · p. 29
• For superlinear f, the proof uses Eγ-divergence to lower-bound total variation and constructs Bernoulli measures for Theorem 5.The Bernoulli construction is used to exhibit the pair of measures needed for the lower bound.Source: §D.2 · pp. 29–30
• One alternative construction requires a monotonicity condition; the proof notes that f(0) < ∞ can be avoided by placing an atom at 1/2.The initial construction may fail to have finite divergence, prompting a modification.Source: §D.2 · pp. 31, 33

E.1 Proof of Proposition 8

• Choosing δ ≤ σ/C makes each mixture p_t f-smooth when f′(∞) = C < ∞.The mixture is p_t = (1 − δ)μ + δq_t, with μ uniform on the unit interval.Source: §E.1 · pp. 33–34
• A Rademacher-driven sequence of atom locations converges almost surely to a threshold, making the constructed labels realizable.The labels are defined by whether each context falls above that limiting threshold.Source: §E.1 · p. 34

E.2 Proof of Lemma 9

• The proof of Lemma 9 samples independent base-distribution points and applies Theorem 3 conditionally on the history, using the f-divergence bound.This replaces the standard rejection-sampling bound in the referenced proof approach.Source: §E.2 · p. 34

E.3 Minimax Regret for f-Smoothed Online Learning

• For f-smoothed adversaries, Theorem 35 gives a minimax regret upper bound under a Lipschitz loss and a scale-sensitive VC-dimension condition.The theorem assumes f′(∞) = ∞ and real-valued functions in [−1, 1].Source: §E.3 · p. 34

E.4 Oracle-Efficient Algorithms

• The oracle-efficient section considers an improper algorithm using two oracle calls per round and a proper algorithm using one; its results extend to approximate ERM with additive εT.The proof exposition restricts its focus to exact oracles for simplicity.Source: §E.4 · p. 36

E.4.1 Improper Algorithm through Relaxations

• The relaxation used in prior work remains valid in the f-smoothed regime with minor modifications, and Lemma 38 establishes this for convex Lipschitz losses.Its definition uses base-distribution samples and independent Rademacher variables.Source: §E.4.1 · p. 37
• Random playout yields an oracle-efficient algorithm whose predictions can be evaluated with two ERMOracle calls per round.The construction uses sampled future base-distribution points.Source: §E.4.1 · p. 40
• Theorem 39 gives a regret guarantee for the algorithm against (f, σ)-smoothed adversaries.The proof relates the guarantee to the relaxation and the resulting bound in (11).Source: §E.4.1 · pp. 40–41

E.4.2 Proper Algorithm through FTPL

• The analysis restricts attention to binary-valued function classes and linear loss because of proof technicalities.Source: §E.4.2 · p. 41
• At each round, the FTPL procedure samples Gaussian perturbations and examples from μ, then calls an oracle to evaluate candidates.The learner plays the resulting function on the context; this is proper because the procedure does not depend on the current context.Source: §E.4.2 · p. 41
• The proper FTPL algorithm achieves no regret against a Renyi-smoothed adversary under Theorem 40’s stated conditions.The theorem considers binary-valued function classes with linear loss and a Renyi-divergence condition for some λ ≥ 2.Source: §E.4.2 · pp. 41–42
• The regret analysis separates perturbation size, stability, and generalization error.Source: §E.4.2 · p. 42