PaperlayerView exact revision on arXiv

Source-linked AI summary

FastMMD: Ensemble of Circular Discrepancy for Efficient Two-Sample Test

Ji Zhao, Deyu Meng

arXiv:1405.2664v2cs.AIcs.LGstat.ML

TL;DR

Exact MMD’s O(N^2d) cost hampers large-scale use. FastMMD applies Fourier-based approximation and Fastfood to spherically invariant kernels; the paper reports accuracy similar to exact MMD and significantly smaller variance than MMD-linear and B-test.

  • Problem

    Exact MMD requires O(N^2d) computation, which hampers its application to large-scale practical problems.

    Source: §1 · p. 3

  • Method

    FastMMD approximates MMD for shift-invariant kernels using Fourier transforms and, for spherically invariant kernels, Fastfood.

    Source: §1 · p. 5, §5 · p. 27

  • Results

    FastMMD has accuracy similar to exact MMD and significantly smaller variance than MMD-linear and B-test.

    Source: §1 · p. 5

  • Takeaways & Limitations

    For spherically invariant kernels, FastMMD’s O(LN log d) computation is presented as facilitating MMD’s use with large-scale data.

    Source: §1 · p. 5

    The discussed kernels are assumed to be real-valued and positive definite, and designing an effective statistic and optimal threshold remains a future challenge.

    Source: §2.2 · p. 7, §4.5 · p. 27

Abstract

from arXiv · show

The maximum mean discrepancy (MMD) is a recently proposed test statistic for two-sample test. Its quadratic time complexity, however, greatly hampers its availability to large-scale applications. To accelerate the MMD calculation, in this study we propose an efficient method called FastMMD. The core idea of FastMMD is to equivalently transform the MMD with shift-invariant kernels into the amplitude expectation of a linear combination of sinusoid components based on Bochner's theorem and Fourier transform (Rahimi & Recht, 2007). Taking advantage of sampling of Fourier transform, FastMMD decreases the time complexity for MMD calculation from $O(N^2 d)$ to $O(L N d)$, where $N$ and $d$ are the size and dimension of the sample set, respectively. Here $L$ is the number of basis functions for approximating kernels which determines the approximation accuracy. For kernels that are spherically invariant, the computation can be further accelerated to $O(L N \log d)$ by using the Fastfood technique (Le et al., 2013). The uniform convergence of our method has also been theoretically proved in both unbiased and biased estimates. We have further provided a geometric explanation for our method, namely ensemble of circular discrepancy, which facilitates us to understand the insight of MMD, and is hopeful to help arouse more extensive metrics for assessing two-sample test. Experimental results substantiate that FastMMD is with similar accuracy as exact MMD, while with faster computation speed and lower variance than the existing MMD approximation methods.

1 Introduction

MMD is used for two-sample testing, but its O(N^2d) calculation limits large-scale use. FastMMD combines Fourier-based approximation with Fastfood for spherically invariant kernels, and the paper reports accuracy similar to exact MMD, lower variance than MMD-linear and B-test, convergence guarantees, and a geometric interpretation.

1 Introduction

  • Exact MMD costs O(N^2d), while MMD-linear costs O(Nd) but has high variance from using few sample-pair interactions.Source: §1 · p. 3
  • B-test computes exact MMD within blocks while omitting inter-block pairs, yielding O(N^3/2d) complexity at the stated block-size setting.The passage describes the block size as generally set to a modest value N by experience.Source: §1 · p. 4
  • FastMMD uses Bochner’s theorem and Fastfood to reduce computation for spherically invariant kernels to O(LN log d), with sequential and parallel computation also supported.The authors say this lower complexity than current MMD approximation methods facilitates large-scale application.Source: §1 · p. 5
  • FastMMD has accuracy similar to exact MMD and significantly smaller variance than MMD-linear and B-test.Source: §1 · p. 5
  • FastMMD has theoretically proved uniform convergence for both biased and unbiased estimates, whereas MMD-linear and B-test are feasible only for unbiased cases.Source: §1 · p. 5
  • The paper gives a geometric explanation of FastMMD and suggests it may help inspire more extensive metrics for two-sample testing.Source: §1 · p. 5

2 Efficient MMD for Shift-Invariant Kernels

FastMMD approximates MMD for shift-invariant kernels by using Fourier sampling and sinusoid amplitudes, avoiding the exact statistic’s quadratic computation. The method offers faster complexity, sequential and parallel computation, and uniform convergence guarantees for biased and unbiased estimates.

2.1 Overview of MMD

  • MMD measures the discrepancy between two distributions, but its exact computation costs O(N^2d), limiting use on large-scale problems.The section considers shift-invariant kernels as a setting for accelerating this computation.Source: §2.1 · pp. 6–7

2.2 Efficient Approximation of MMD

  • Bochner’s theorem expresses a shift-invariant kernel through a Fourier measure, allowing empirical MMD to be computed as an amplitude of combined sinusoids.Sampling L frequencies and averaging their amplitudes approximates biased MMD; the unbiased estimate can be rewritten similarly.Source: §2.2 · pp. 8–9

2.3 Computational Complexity

  • FastMMD-Fourier costs O(LNd), while FastMMD-Fastfood reduces this to O(LN log d) for spherically invariant kernels.The amplitude calculation can be performed sequentially, and the method is also easy to parallelize.Source: §2.2 · p. 10, §2.3 · p. 11

2.4 Approximation Guarantees

  • Theorems give uniform convergence bounds for FastMMD-Fourier and FastMMD-Fastfood, and the bounds also apply to unbiased MMD approximations.The FastMMD approximation is described as unbiased.Source: §2.4 · pp. 11–12

Statistic

  • FastMMD approximates the kernel by using a linear combination of Dirac-delta functions to represent its Fourier distribution.The paper states that uniform convergence bounds and asymptotic distribution results for general kernels in Gretton et al. (2012a) still hold for FastMMD.Source: Statistic · p. 13

3 Ensemble of Circular Discrepancy

The section explains FastMMD geometrically through random projections onto a circle and a circular discrepancy between projected samples. Averaging discrepancies over frequencies sampled from a shift-invariant kernel’s Fourier distribution yields an efficient approximation to MMD.

3.1 Random Projection on a Unit Circle

  • For fixed ω, projected sample values can be wrapped onto a unit circle without changing the kernel, producing circular distributions supported on [0, 2π).Source: §3.1 · p. 14

3.2 Circular Discrepancy

  • For probability mass functions, the circular-discrepancy objective combines sinusoids of the same frequency, whose maximum amplitude is consistent with MMD.Source: §3.2 · p. 15
  • The circular discrepancy seeks a decision diameter that maximizes the mean margin between projected classes; maximizing and minimizing distributions are offset by π.Source: §3.2 · pp. 15–16
  • For a Gaussian kernel, the ensemble of circular discrepancy is small as the spread parameter σ approaches zero or infinity.Source: §3.2 · p. 17

3.3 Ensemble of Circular Discrepancy

  • Sampling frequencies from a shift-invariant kernel’s Fourier distribution and averaging circular discrepancies gives an efficient approximation of empirical MMD.Source: §3.3 · pp. 17–18
  • Alternative distance measurements or ensemble norms could yield two-sample metrics beyond MMD, which the authors identify as future directions.Source: §3.3 · pp. 18–19

4 Experimental Results

Across synthetic and PASCAL VOC 2007 tests, FastMMD approximates exact MMD accurately and becomes more efficient as sample size or dimension grows. Type II error decreases with more basis functions, while the bootstrap-based testing procedure remains a speed limitation.

4.1 Approximation Quality

  • As the number of basis functions increases, both FastMMD variants quickly converge to exact biased and unbiased MMD, with similar performance.Good approximation is obtained with a modest number of basis functions.Source: §4.1 · p. 20, Figure 5 · p. 21

4.2 Accuracy Test for MMD with Kernel Family

  • Across kernel bandwidths, FastMMD means match true values and its deviations are much smaller than MMD-linear and B-test.FastMMD-Fourier and FastMMD-Fastfood have similar accuracy.Source: §4.2 · p. 22, Figure 6 · p. 22

4.3 Efficiency Test on Synthetic Data

  • At d = 16 and N = 10^5, FastMMD-Fourier and FastMMD-Fastfood are respectively 2000/5x and 4000/10x faster than exact MMD/B-test.Runtime increases more slowly than MMD-linear as sample size or dimension grows.Source: Figure 7 · p. 23, §4.3 · p. 24

4.4 Efficiency Test on Large-Scale Real Data

  • FastMMD has smaller approximation error and deviation, with three orders of speedup over exact MMD on PASCAL VOC 2007.The comparison is reported in Table 1.Source: §4.4 · p. 25, Table 1 · p. 25

4.5 Type II Error

  • In the Gaussian-blob test, Type II error drops quickly as the number of basis functions increases.The reported setting uses α = 0.05 and 1,000 bootstrap shuffles.Source: §4.5 · p. 26, Figure 8 · p. 27
  • With 256 basis functions, FastMMD achieves comparable Type II error results while running faster than Bootstrap, Pearson, and spectrum.Reported runtimes were 88.7s (Bootstrap), 37.9s (Pearson), 33.2s (spectrum), 0.73s (Gamma), and 4.5s (FastMMD+Bootstrap).Source: §4.5 · pp. 26–27
  • FastMMD is less efficient than Gamma when paired with bootstrap, and designing more efficient significance thresholds remains open.The paper attributes the runtime difference to repeated MMD calculation across bootstrap shuffles.Source: §4.5 · p. 27

5 Conclusions

FastMMD approximates MMD for shift-invariant kernels using Fourier transforms. The paper proves convergence for biased and unbiased estimates and presents a geometric interpretation that may inspire broader two-sample-test metrics.

  • FastMMD is a method for efficiently calculating MMD for shift-invariant kernels.It uses the Fourier transform of shift-invariant kernels for a linear-time approximation.Source: §5 · pp. 27–28
  • The proposed method's convergence is proved for both biased and unbiased estimates.Source: §5 · p. 28
  • The geometric explanation offers insight into MMD and may inspire more extensive metrics for two-sample tests.The paper identifies this as a direction for future research.Source: §5 · p. 28

A.1 Relationship between biased and unbiased estimate of MMD

This appendix passage introduces the unbiased MMD estimate and notes how its expression is reformulated when the kernel is shift-invariant.

  • The appendix introduces the unbiased estimate of MMD.Source: §A.1 · p. 28
  • Here, m and n denote the sizes of the two index sets, and S1 and S2 are defined using within-set kernel sums.Source: §A.1 · p. 29
  • For a shift-invariant kernel, the diagonal value k0 is constant, and the estimate is then reformulated.Source: §A.1 · p. 29

A.2 Preliminary for the Proof of Theorem 3 and Theorem 4

The appendix gives preliminary claims for analyzing FastMMD's approximation, including a uniform-convergence result and an equivalent random-Fourier-feature formulation.

  • Claim 7 sets up uniform-convergence analysis for a function parameterized by a random variable on a compact domain, under a bounded-difference condition.Source: §A.2 · p. 29
  • The stated bound gives a probability greater than 1 − C(ε) that the supremum approximation error is below ε.Source: §A.2 · p. 30
  • An equivalent FastMMD formulation uses random Fourier features and has linear time complexity; the appendix uses it for convergence analysis.Algorithm 1 provides a geometric explanation, while Algorithm 2 is used for the analysis.Source: §A.2 · p. 31

A.3 Proof of Theorem 3

The proof establishes uniform convergence for both biased and unbiased MMD estimates. It uses algebraic transformations associated with Algorithm 2 and referenced results.

A.3 Proof of Theorem 3

  • The argument refers to Eqns. (18) and (19), Claim 7, and a bound denoted C(ǫ).The passage identifies C(ǫ) as the right-hand side of inequality (21).Source: §A.3 · pp. 32–33
  • The proof obtains uniform convergence for the biased MMD estimate and states that the unbiased case follows similarly.The passage also says the biased-estimate proof is complete.Source: §A.3 · p. 33
  • For the unbiased estimate of MMD, the proof treats the case according to Algorithm 2, applies an algebraically equivalent transformation, and then obtains uniform convergence for the unbiased estimate.Source: §A.3 · p. 33

A.4 Proof of Theorem 4

The proof establishes uniform convergence for biased and unbiased MMD estimates. Its argument uses bounded differences over an ǫ-net, with a Fastfood-specific bound under a stated condition.

A.4 Proof of Theorem 4

  • The proof defines f(x_i, x_j; ω) as the feature-product error and states that it is bounded by 2, has zero expectation, and is shift-invariant.The stated properties are attributed to Lemma 3 in Le et al. (2013).Source: §A.4 · p. 33
  • An ǫ-net over the compact set M∆ reduces uniform control to bounding f at net anchors and for pairs whose differences lie in net balls.The net uses at most T = (4 diam(M)/r)^d balls of radius r; the anchor event is bounded using the union bound and Hoeffding’s inequality.Source: §A.4 · p. 34
  • For Fastfood blocks of size d × d, the proof invokes a Fastfood-theorem bound and assumes (log d)/2 ≥ 1 before reformulating it using ∥x_i − x_j∥ ≤ 2r.The resulting bound is expressed in terms of the free variable r.Source: §A.4 · p. 34
  • The proof completes uniform convergence for the biased MMD estimate and says the unbiased case can be proved similarly.The proof denotes the right-hand side of inequality (26) by C(ǫ).Source: §A.4 · p. 35

A.5 Proof of Claim 5

The proof sets up an optimization over a normalized density q and uses trigonometric identities to handle sums of sinusoidal terms. It identifies atan2 as the four-quadrant arctangent.

A.5 Proof of Claim 5

  • The proof defines p1(x), p2(x), and q(y) as probability densities for X1, X2, and Y, respectively.It imposes the normalization ∫q(y)dy = 1.Source: §A.5 · p. 35
  • The argument takes the maximum of the preceding expression over all possible normalized q(y).The passage does not state the resulting maximizing density or value.Source: §A.5 · p. 35
  • The proof combines same-frequency sinusoidal terms using a trigonometric identity and identifies atan2 as the four-quadrant arctangent.The passage describes the supremum of the resulting problem but does not provide its value here.Source: §A.5 · p. 36

Related papers

Loading 1405.2664v2…