PaperlayerView exact revision on arXiv

Source-linked AI summary

MMD Aggregated Two-Sample Test

Antonin Schrab, Ilmun Kim, Mélisande Albert, Béatrice Laurent, Benjamin Guedj, Arthur Gretton

arXiv:2110.15073v4stat.MLcs.LGmath.STstat.MEstat.TH

TL;DR

Nonparametric two-sample tests need to compare distributions without specific distributional assumptions, while existing bandwidth choices can be problematic. The paper proposes fixed-kernel and aggregated MMD tests with non-asymptotic level guarantees; MMDAgg adapts to unknown smoothness and performs strongly in synthetic and image-data experiments.

  • Problem

    Nonparametric two-sample testing compares distributions without assuming a specific distributional form, while bandwidth heuristics lack optimality guarantees and held-out kernel selection can reduce power at smaller sample sizes.

    Source: §1 · p. 3

  • Method

    The paper constructs fixed-kernel MMD tests using permutation or wild-bootstrap thresholds and aggregates across bandwidths in MMDAgg to adapt to unknown smoothness without data splitting.

    Source: §1 · pp. 4–5

  • Results

    MMDAgg significantly outperforms considered state-of-the-art MMD adaptive tests on synthetic Sobolev data and almost matches neural-network-based tests on image data.

    Source: §6 · p. 40

  • Takeaways & Limitations

    MMDAgg achieves non-asymptotic type I error control and minimax adaptivity over Sobolev balls up to an iterated logarithmic term.

    Source: §6 · p. 39

    Adapting the results to linear-time tests that learn adaptive interpretable features without data splitting remains an open challenge.

    Source: §6 · p. 40

Abstract

from arXiv · show

We propose two novel nonparametric two-sample kernel tests based on the Maximum Mean Discrepancy (MMD). First, for a fixed kernel, we construct an MMD test using either permutations or a wild bootstrap, two popular numerical procedures to determine the test threshold. We prove that this test controls the probability of type I error non-asymptotically. Hence, it can be used reliably even in settings with small sample sizes as it remains well-calibrated, which differs from previous MMD tests which only guarantee correct test level asymptotically. When the difference in densities lies in a Sobolev ball, we prove minimax optimality of our MMD test with a specific kernel depending on the smoothness parameter of the Sobolev ball. In practice, this parameter is unknown and, hence, the optimal MMD test with this particular kernel cannot be used. To overcome this issue, we construct an aggregated test, called MMDAgg, which is adaptive to the smoothness parameter. The test power is maximised over the collection of kernels used, without requiring held-out data for kernel selection (which results in a loss of test power), or arbitrary kernel choices such as the median heuristic. We prove that MMDAgg still controls the level non-asymptotically, and achieves the minimax rate over Sobolev balls, up to an iterated logarithmic term. Our guarantees are not restricted to a specific type of kernel, but hold for any product of one-dimensional translation invariant characteristic kernels. We provide a user-friendly parameter-free implementation of MMDAgg using an adaptive collection of bandwidths. We demonstrate that MMDAgg significantly outperforms alternative state-of-the-art MMD-based two-sample tests on synthetic data satisfying the Sobolev smoothness assumption, and that, on real-world image data, MMDAgg closely matches the power of tests leveraging the use of models such as neural networks.

1 Introduction

The paper develops fixed-kernel and aggregated MMD tests for nonparametric two-sample testing, with non-asymptotic level guarantees. MMDAgg adapts to unknown smoothness and performs strongly in synthetic and image-data experiments.

1 Introduction

  • Bandwidth heuristics lack optimality guarantees, while held-out kernel selection can reduce test power at smaller sample sizes.The median heuristic can have low power when the difference lengthscale diverges from the median inter-sample distance.Source: §1 · pp. 3–4
  • The theoretical guarantees cover products of one-dimensional translation-invariant characteristic kernels that are absolutely and square integrable.The introduction identifies minimax adaptivity beyond the Gaussian kernel, up to an iterated logarithmic term.Source: §1 · pp. 4–5
  • Considering multiple bandwidths makes the parameter-free MMDAgg test suited to both local and global density differences, unlike a fixed-bandwidth MMD test.The authors provide an implementation in Jax and Numpy.Source: §1 · p. 5
  • For known Sobolev smoothness, a single MMD test with a smoothness-dependent bandwidth is minimax optimal, and permutation or wild-bootstrap thresholds give it non-asymptotic level.The threshold procedures also support non-asymptotic level guarantees for MMDAgg.Source: §1 · pp. 4–5
  • MMDAgg aggregates tests across bandwidths to adapt to unknown Sobolev smoothness, controlling type I error non-asymptotically and attaining minimax optimality up to an iterated logarithmic term.The guarantees cover a wide range of kernels and both permutation and wild-bootstrap threshold estimation.Source: §1 · p. 5
  • On synthetic data satisfying the Sobolev assumption, MMDAgg significantly outperforms the considered state-of-the-art MMD adaptive tests, and on image data it almost matches tests using models such as neural networks.The reported power is retained when aggregating up to 12,000 kernels.Source: §1 · p. 5

2 Background

The background formalizes testing whether two independent samples come from distributions with equal densities and reviews non-asymptotic testing concepts. It introduces MMD as a kernel-based discrepancy and describes estimators used for testing.

2 Background

  • Two independent i.i.d. samples with densities p and q on R^d define the two-sample problem: decide whether p differs from q.The test considers H0: p = q against Ha: p ≠ q.Source: §2 · p. 6, §2.1 · p. 6

2.1 Hypothesis testing

  • A uniform separation rate describes the smallest L2 difference detectable with specified power over a class of alternatives; the minimax rate is the best lower-bound rate across level-controlled tests.For Sobolev balls, the stated minimax rate is of order (m + n)^(-2s/(4s+d)).Source: §2.1 · pp. 7–8

2.2 Maximum Mean Discrepancy

  • MMD is a kernel-based discrepancy that is zero exactly when the distributions agree for a characteristic kernel, and it admits an unbiased quadratic-time estimator.The cited estimator is also described as a minimum-variance MMD estimator.Source: §2.2 · p. 8

3 Construction of tests and bounds

This section develops fixed-bandwidth MMD tests, their non-asymptotic level and power guarantees, and their Sobolev-ball separation rates, including a minimax-optimal bandwidth dependent on smoothness. It then presents MMDAgg, which combines bandwidth-specific tests to adapt to unknown smoothness while retaining non-asymptotic level control and achieving minimax adaptation up to an iterated logarithmic factor.

3.1 Assumptions and notation

  • The analysis assumes sample sizes balanced up to a constant factor, so both must grow at the same rate in increasing-sample settings; power theory uses translation-invariant kernels.The tests are nevertheless well-defined and have non-asymptotically calibrated levels for any positive definite characteristic kernel and on any domain.Source: §3.1 · p. 10

3.2.1 Permutation approach

  • The permutation approach estimates the conditional threshold by Monte Carlo sampling uniformly from permutations of the pooled observations.It is described for the MMD estimator based on the two samples.Source: §3.2.1 · p. 11

3.2.2 Wild bootstrap approach

  • For the paired-sample estimator, the wild bootstrap uses independent Rademacher signs and corresponds to permutations that fix or swap each paired observation.This approach assumes equal sample sizes.Source: §3.2.2 · p. 12

3.2.3 Single MMD test: definition and level

  • The fixed-bandwidth MMD test controls type I error non-asymptotically at level α for any sample sizes and Monte Carlo replicate count B.The procedure estimates the conditional quantile by permutation or wild bootstrap and includes the original statistic among the simulated statistics.Source: §3.2.3 · pp. 12–13

3.3 Controlling the power of the single MMD test

  • A sufficient condition involving the MMD discrepancy ensures type II error at most β; the resulting L2-based condition depends on bandwidth and sample size.The analysis bounds the test-statistic variance and the Monte Carlo-estimated conditional quantile; the latter bound applies to any bandwidth without additional assumptions.Source: §3.3 · pp. 14–15

3.4 Uniform separation rate of the single MMD test over a Sobolev ball

  • Over Sobolev balls, the single test has a bandwidth-dependent uniform separation-rate upper bound and is minimax optimal for a specific bandwidth.That optimal bandwidth depends on the unknown smoothness parameter s.Source: §3 · p. 9, §3.4 · p. 15
  • For bandwidth λ_i=(m+n)^-2/(4s+d), the single MMD test is minimax optimal over the Sobolev ball, but this choice requires knowing s.The paper notes that the single-test optimality holds without restrictions on sample sizes m and n.Source: §3.4 · p. 16

3.5 Non-asymptotic MMDAgg test aggregating multiple bandwidths

  • MMDAgg combines single MMD tests across a finite bandwidth collection with positive weights summing to at most 1, using Romano and Wolf’s multiple-testing correction.The correction gives MMDAgg non-asymptotic level α for any probability density p, including at small fixed sample sizes.Source: §3.5 · pp. 16, 20

3.6 Uniform separation rate of MMDAgg over Sobolev balls

  • If any bandwidth-specific test at its adjusted level has type II error at most β/2, MMDAgg’s type II error is at most β.The aggregation therefore retains high power when at least one test in the bandwidth collection is effective.Source: §3.6 · p. 21
  • MMDAgg is minimax adaptive over Sobolev balls, attaining separation rate ((m+n)/ln(ln(m+n)))^-2s/(4s+d) without depending on smoothness s or radius R.This is rate-optimal up to an iterated logarithmic factor compared with the minimax rate (m+n)^-2s/(4s+d).Source: §3.6 · p. 22

4 Related work

Related approaches vary in their use of sample splitting, asymptotic calibration, and kernel scope. MMDAgg instead estimates thresholds by permutations or a wild bootstrap and supports a broader kernel class without a restrictive sample-size condition.

Other aggregated tests

  • Fromont et al. (2012, 2013) obtain adaptive minimax rates in a Poisson-sampling setting, while Albert et al. (2022) study aggregated HSIC tests for independence rather than two-sample testing.Fromont et al. also consider anisotropic Nikol’skii-Besov balls and impose an additional Fourier-domain kernel condition.Source: §4 · pp. 22–23

Comparison with Albert et al. (2022)

  • MMDAgg uses estimated thresholds to avoid a restrictive sample-size condition and extends beyond Gaussian kernels to products of one-dimensional characteristic translation-invariant kernels.Its level correction uses Monte Carlo estimates from permutations or a wild bootstrap rather than an uncomputable theoretical value.Source: §4 · p. 23

Other adaptive tests

  • Kim et al. (2022) aggregate multinomial tests across bin sizes for Hölder densities on the unit ball, rather than aggregating kernel bandwidths.Their function class and strategy differ, though they derive a similar upper bound on the uniform separation rate.Source: §4 · p. 23

Adaptive tests over Sobolev balls

  • Li and Yuan (2019) establish adaptive minimax rates for Gaussian-kernel tests only when s ≥ d/4, while MMDAgg has no such restriction and assumes only p−q lies in a Sobolev ball.Their tests rely on asymptotic distributions and assume both densities belong to a Sobolev ball.Source: §4 · p. 24

Kernel adaptation by sample splitting

  • Sample-splitting approaches select kernels using part of the data, but withholding samples for testing can reduce power when data are limited.Prior approaches use the MMD-to-standard-deviation ratio or a proxy to tune kernel choice.Source: §4 · p. 24

Kernel adaptation without data splitting

  • Post-selection calibration without data splitting requires asymptotic normality, restricting the cited approach to linear-time MMD, which experiments found less powerful than quadratic-time MMD.Kübler et al. (2020) select a linear combination of statistics using all data before testing with all data.Source: §4 · pp. 24–25

5 Experiments

The experiments compare MMDAgg variants with established MMD tests on synthetic and real-world data, covering weighting and bandwidth choices, experimental procedures, and results. They also examine performance on MNIST and image-shift detection, calibration, bootstrap choice, sample sizes, and bandwidth-range trade-offs.

5.1 Weighting strategies and fixed bandwidth collections for MMDAgg

  • The four weighting strategies encode bandwidth priorities: uniform weights are recommended without prior information, while decreasing, increasing, and centred weights prioritize smaller, larger, and middle bandwidths.Uniform weighting is more robust to changes in the bandwidth collection; the authors recommend the adaptive parameter-free test in practice.Source: §5.1 · pp. 25–26, §5.5 · p. 34

5.2 Adaptive parameter-free collection of bandwidths for MMDAgg

  • MMDAgg⋆ uses a parameter-free bandwidth collection discretized between half the minimum and twice the maximum inter-sample distances, with ten points recommended.Increasing the collection to 100 or 1,000 points leaves power unchanged; the test uses uniform weights and the same parameters across experiments.Source: §5.2 · pp. 27–28

5.3 State-of-the-art MMD-based two-sample tests

  • Comparisons include median-heuristic and split-selected single-bandwidth tests, an oracle using extra data, the linear-time OST, and AutoML.AutoML learns a witness function using an AutoGluon model, with the model depending on available compute and the prescribed training time.Source: §5.3 · pp. 28–29

5.4 Experimental procedure

  • Experiments use Gaussian and Laplace kernels, wild bootstrap calibration at level α = 0.05, and 500 repetitions to estimate power.Tests cover perturbed uniform distributions and MNIST; sample sizes are 500 per group for 1-dimensional and MNIST data, and 2,000 per group for 2-dimensional data.Source: §5.4 · p. 30

5.5 Power experiments on synthetic data

  • MMDAgg⋆ performs best across the tested synthetic settings, slightly exceeding even the oracle test, which uses extra data to select its bandwidth.Its adaptive collection also beats the four aggregated tests with specifically chosen bandwidth collections; the other tests have significantly lower power.Source: Figure 3 · p. 32, §5.5 · pp. 32–33, Figure 4 · p. 33
  • Across the synthetic experiments, added perturbations reduce power for all tests, and performance degrades substantially in two dimensions despite the larger sample size.The experiments use 1-dimensional samples of 500 per distribution and 2-dimensional samples of 2,000 per distribution.Source: §5.5 · p. 32
  • Aggregating Gaussian and Laplace kernels reaches the higher power of either alone, while adding ten other kernels preserves that power through the level-correction procedure.The expanded collection includes 12 kernel types, each with ten bandwidths.Source: §5.5 · p. 34
  • For fixed collections, increasing weights perform best when bandwidths are small, centred weights when they are intermediate, and decreasing weights when they are large.These patterns suggest whether a collection is too small or too large; the authors recommend adaptively selected bandwidths with MMDAgg⋆Laplace Gaussian in practice.Source: §5.5 · p. 34

5.6 Power experiments on the MNIST dataset

  • On MNIST digit comparisons, MMDAgg⋆ and AutoML achieve the same power and far outperform the other tests; aggregated tests often match or slightly beat oracle and significantly outperform split, ost, and median.MMDAgg⋆ performs similarly with Laplace and Gaussian kernels, while Laplace benefits the other weighting strategies; combining Laplace and Gaussian is recommended across the experiments, as it attains the better single-kernel power without the higher cost of MMDAgg⋆All. Adaptive bandwidths help address alternatives whose optimal scales differ, unlike median and split, which select a specific bandwidth.Source: §5.6 · pp. 36–37

5.7 Power experiment: continuous limit of the collection of bandwidths

  • Increasing the bandwidth count from 10 to 1000 leaves power unchanged, including for MMDAgg⋆All aggregating up to 12,000 kernels; 10 points achieve the continuous-collection power at lower computational cost.Across the experiments, MMDAgg⋆Laplace Gaussian attains the highest power of either single-kernel MMDAgg⋆ variant, while MMDAgg⋆All does not improve power and costs more computation.Source: §5.7 · p. 38

5.8 Power experiment for image shift detection

  • On MNIST and CIFAR-10 image shifts, MMDAgg⋆ variants outperform MMDAgg uniform, with Laplace best and Laplace-Gaussian nearly as powerful; they come within a few percentage points of AutoML.Aggregating many more kernels with MMDAgg⋆All matches MMDAgg⋆Laplace Gaussian. The reported power is averaged over 60 alternatives, each repeated five times.Source: §5.8 · p. 38, Table 1 · p. 39

5.9 Overview of additional experimental results

  • Appendix experiments report well-calibrated test levels, similar performance for wild bootstrap and permutations, relatively small power costs from wider bandwidth collections, and sample-size limitations for small samples and ost.With one sample size fixed small, high power is not obtained even when the other sample is very large; ost requires extremely large sample sizes to match MMDAgg uniform with 500 or 2000 samples.Source: §5.9 · p. 39

6 Conclusion and future work

MMDAgg aggregates MMD tests across kernels and bandwidths, adapts over Sobolev balls without data splitting, and is minimax optimal up to an iterated logarithmic term. The conclusion also identifies open challenges and extensions.

Conclusion

  • MMDAgg is adaptive over Sobolev balls without data splitting and achieves minimax optimality up to an iterated logarithmic term.The guarantees also hold with wild-bootstrap and permutation threshold procedures and for the stated class of product kernels.Source: §6 · p. 39
  • On synthetic Sobolev-smoothness settings, MMDAgg significantly outperforms other state-of-the-art MMD tests, while on image data it nearly matches model-based tests.The paper recommends a parameter-free bandwidth collection using Gaussian and Laplace kernels.Source: §6 · p. 40

Future work

  • Learning adaptive interpretable features without the data splitting used for feature and bandwidth selection remains an open challenge for the Jitkrittum et al. (2016) approach.The authors identify this as a direction for future work.Source: §6 · p. 40
  • The paper points to goodness-of-fit testing with MMD when the model-kernel expectation is computable, and to KSD-based testing otherwise.It also notes quadratic-time cost as a limitation of MMDAgg and describes incomplete-U-statistic variants that improve computational efficiency while quantifying the minimax-rate cost.Source: §6 · p. 40

Overview of Appendices

The appendices provide additional experiments, explain the permutation–wild-bootstrap relation, describe an efficient implementation, and present the minimax-rate proof strategy and proofs.

Overview of Appendices

  • The appendices also cover the permutation–wild-bootstrap relation, efficient MMDAgg implementation, minimax-rate proof strategy, and proofs of all results.Source: Overview of Appendices · p. 41

Appendix A. Additional experiments

  • Appendix A verifies test levels and reports power experiments on bandwidth-collection width, threshold procedures, unbalanced sample sizes, and increased sample sizes.The level experiments use Appendix A.1; the power studies occupy Appendices A.2–A.5.Source: Appendix A · p. 41

A.1 Level experiments

The level experiments estimate test levels across uniform-distribution and MNIST settings, kernels, and threshold procedures; the reported estimates are close to the target 0.05.

A.1 Level experiments

  • The level estimates use 5,000 repetitions, with specified bandwidth collections for the aggregated tests on uniform samples and MNIST.Uniform samples use Λ(−4, 0); MNIST uses Λ(10, 14) and Λ(12, 16) for Gaussian and Laplace kernels, respectively.Source: §A.1 · p. 41
  • All tests have estimated levels relatively close to the prescribed 0.05 across the considered settings, with no noticeable trend between threshold procedures.The experiments include three data types, Gaussian and Laplace kernels, and wild bootstrap or permutations.Source: §A.1 · p. 41, Table 2 · p. 42

A.2 Power experiments: widening the collection of bandwidths

Widening bandwidth collections causes little power loss for centred MMDAgg, while uniform weighting also loses power relatively slowly. Wild bootstrap and permutations yield very similar power in the reported comparisons.

A.2 Power experiments: widening the collection of bandwidths

  • Figure 7 shows only a very small power decrease for centred MMDAgg as bandwidth collections widen across the considered settings.The method retains the highest weight on the well-calibrated bandwidth at the collection centre; MNIST also shows a slight power increase with nine-bandwidth collections for both kernels.Source: Figure 7 · p. 43, §A.2 · p. 43
  • Uniform-weight MMDAgg power decays relatively slowly as the collection widens, even without using information that the central bandwidth is well calibrated.The experiments widen collections from 3 to 15 bandwidths and compare uniform and centred weighting.Source: §A.2 · pp. 42–43

A.3 Power experiments: comparing wild bootstrap and permutations

  • Figure 8 compares wild-bootstrap and permutation power on perturbed-uniform and MNIST data; their absolute difference is at most roughly 0.02 and usually smaller.The difference shows no overall bias toward either procedure; the authors suggest wild bootstrap when sample sizes match because it runs slightly faster, and permutations when they differ.Source: Figure 8 · p. 44, §A.3 · p. 44

A.4 Power experiments: using unbalanced sample sizes

With one sample fixed at 100 or 250, increasing the other to 5,000 generally did not overcome low power; balanced samples performed better in the compared settings.

A.4 Power experiments: using unbalanced sample sizes

  • The experiments compare perturbed uniform distributions in one and two dimensions with an MNIST comparison of all digits against images excluding digits 4, 6, and 8.Figure 9 considers unequal sample sizes, fixing one sample while increasing the other, and uses permutations.Source: §A.4 · pp. 44–45
  • With one sample fixed at 100 or 250, power generally plateaued at no more than 0.25 as the other sample grew to 5,000.MMDAgg⋆ on MNIST was the exception, performing much better than the other tests.Source: §A.4 · p. 45
  • The compared settings achieved significantly higher power with balanced samples of 500 or 2,000 per group than with 5,100 total samples split very unevenly.The passage concludes that, where possible, datasets should have sample sizes of the same order.Source: §A.4 · p. 45

A.5 Power experiments: increasing sample sizes for the ost test

The linear-time ost test has lower power than quadratic-time alternatives, and the experiments increase its sample sizes to match MMDAgg uniform. Matching power required much larger samples across the reported settings.

A.5 Power experiments: increasing sample sizes for the ost test

  • The ost test uses a linear-time MMD estimate and has low power relative to the other tests, which use a quadratic-time estimate.Reusing image pairs in distinct 4-tuples can still provide new data to the estimate, explaining the continued power increase at sample sizes above 70,000.Source: §A.5 · pp. 46–47
  • ost required 75,000 and 50,000 samples to match MMDAgg uniform with 500 samples on 1D perturbed uniform data, using Gaussian and Laplace kernels, respectively.For 2D data, the corresponding ost sample sizes were 1,000,000 and 500,000 to match MMDAgg uniform with 2,000 samples.Source: §A.5 · p. 46
  • On MNIST, ost required 250,000 samples to achieve power similar to MMDAgg uniform with 500 samples.The dataset contains 70,000 images, and ost power continued to increase beyond ten times that size.Source: §A.5 · p. 46

Appendix B. Relation between permutations and wild bootstrap

For equal sample sizes, the paper relates the wild bootstrap to a restricted permutation procedure for the MMD estimator. The correspondence pairs each bootstrap sign vector with a permutation that fixes or swaps each matched sample pair.

Appendix B. Relation between permutations and wild bootstrap

  • The permutation expression for the MMD estimate can be written as a quadratic form in the permuted kernel matrix and permuted label vector.The notation defines K_λ as the kernel matrix and v as the vector with +1 entries for X observations and −1 entries for Y observations.Source: Appendix B · p. 47
  • The wild-bootstrap procedure uses n independent Rademacher signs and forms the vector (ε, −ε) for the 2n observations.The sign vector maps to a permutation by fixing a pair for sign +1 and swapping it for sign −1.Source: Appendix B · pp. 48, 50
  • For equal sample sizes, the wild bootstrap is equivalent to permutations that independently fix or swap each matched pair (X_i, Y_i), with a one-to-one correspondence.The permitted permutations form a subgroup because they include the identity, are self-inverse, and are closed under composition.Source: Appendix B · pp. 47, 49

Appendix C. Efficient implementation of MMDAgg (Algorithm 1)

The implementation computes resampled MMD values efficiently across bandwidths by batching vectors and avoiding explicit kernel-matrix row and column permutations. The wild-bootstrap and permutation procedures use different batching constructions.

Appendix C. Efficient implementation of MMDAgg (Algorithm 1)

  • For Gaussian and Laplace kernels, pairwise distances are computed once before constructing the kernel matrices for all bandwidths.The permutation implementation avoids explicitly permuting kernel-matrix rows and columns because doing so is computationally expensive.Source: Appendix C · p. 50
  • The wild-bootstrap implementation batches Rademacher vectors into a matrix, appends their negatives, and includes the fixed vector (1_n, −1_n).The resulting matrix supports efficient computation of the resampled values across bandwidths.Source: Appendix C · pp. 50–51
  • The permutation implementation batches permuted versions of three vectors and computes the resampled sums without explicitly permuting kernel-matrix rows and columns.The procedure uses B1+B2 permutations and leaves the designated (B1+1)th columns unpermuted.Source: Appendix C · pp. 52–53

Appendix D. Lower bound on the minimax rate over a Sobolev ball

Appendix D concerns the minimax lower bound for two-sample testing over a Sobolev ball, with the excerpt presenting algebraic steps from the proof of Theorem 5 rather than a readable statement of the conclusion.

Appendix D. Lower bound on the minimax rate over a Sobolev ball

  • The two-sample minimax testing rate over the Sobolev ball is claimed to be n^-2s/(4s+d).The claim is stated for positive M, s, R, and dimension d, with a positive constant depending on these parameters and α, β.Source: Appendix D · p. 53

Appendix E. Proofs

  • The proofs assume comparable sample sizes, m ≤ n and n ≤ Cm, and track constants to establish their existence rather than optimize them.Appendix E says it proves the statements from Section 3 and uses constants large enough for the results to hold.Source: Appendix E · pp. 54–55

E.1 Proof of Proposition 1

  • Under the null, the MMD statistic elements used by the permutation and wild-bootstrap procedures are exchangeable.The proof states that exchangeability holds for both estimators when p = q.Source: §E.1 · p. 55

E.5 Proof of Theorem 5

  • The proof simplifies its inequalities using β∈(0,1), λ1···λd≤1, and B≥3α².It identifies C1 and C2 as the constants from Propositions 3 and 4, respectively.Source: §E.5 · pp. 67–68
  • The proof notes similar reasoning in Fromont et al. (2013, Theorem 1) and Albert et al. (2022, Theorem 1).Source: §E.5 · p. 67

E.6 Proof of Theorem 6

The proofs establish a Sobolev-based bound used to derive uniform separation rates, select bandwidths that balance the rate terms, and analyze the null case using a bisection approximation.

E.6 Proof of Theorem 6

  • Theorem 6’s proof uses the Sobolev condition on the density difference to establish a bound and derive a uniform separation-rate argument.The proof establishes the needed integrability before applying Plancherel’s theorem.Source: §E.6 · pp. 68–70

E.7 Proof of Corollary 7

  • For each dimension, choosing λ_i = (m + n)^-2/(4s+d) makes the two rate terms have the same order, (m + n)^-4s/(4s+d).The proof states that this choice gives the smallest possible order in m+n.Source: §E.7 · p. 70

E.8 Proof of Proposition 8

  • The Proposition 8 proof takes expectations under H0: p = q and uses a bisection-search approximation for λ(X_m, Y_n).Source: §E.8 · p. 71

E.9 Proof of Theorem 9

Theorem 9’s proof bounds type II error using an event whose probability is controlled, and Corollary 10 concludes that MMDAgg is minimax adaptive over Sobolev balls up to an iterated logarithmic term.

E.9 Proof of Theorem 9

  • The proof controls the probability of event A at least 1 − β/2 and uses it in bounding the type II error.The proof applies Hoeffding’s inequality and considers the type II error probability on event B.Source: §E.9 · pp. 72, 74

E.10 Proof of Corollary 10

  • Corollary 10 concludes that MMDAgg is minimax adaptive over Sobolev balls up to an iterated logarithmic term, without depending on unknown s and R.Source: §E.10 · p. 77

Related papers

Loading 2110.15073v4…