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

Area of Science:

• Machine Learning
• Statistical Inference
• Computational Statistics

Background:

• The maximum mean discrepancy (MMD) is a powerful statistical tool for two-sample hypothesis testing.
• High computational complexity (O(N^2d)) limits MMD's application in large-scale datasets.

Purpose of the Study:

• To develop an efficient algorithm, FastMMD, for accelerating MMD calculations.
• To reduce the time complexity of MMD estimation for large-scale applications.

Main Methods:

• Developed FastMMD by transforming MMD with shift-invariant kernels into amplitude expectation using Bochner's theorem and Fourier transform.
• Leveraged Fourier transform sampling to achieve O(LN d) time complexity.
• Applied Fastfood technique for spherically invariant kernels, achieving O(LN log d) complexity.
• Provided a geometric interpretation: ensemble of circular discrepancy.

Main Results:

• FastMMD reduces MMD calculation time complexity significantly compared to the standard approach.
• Theoretical proof of uniform convergence for both unbiased and biased estimates.
• Experimental results show FastMMD accuracy comparable to MMD.
• FastMMD demonstrates faster computation and lower variance than existing MMD approximation methods.

Conclusions:

• FastMMD offers an efficient and accurate solution for large-scale MMD-based two-sample testing.
• The geometric insight may inspire new metrics for two-sample tests.
• FastMMD enhances the practical applicability of MMD in data-intensive fields.