Classification Accuracy as a Proxy for Two Sample Testing

By Aaditya Ramdas, Aarti Singh, Larry A. Wasserman. 2016

95 citations recorded by the source corpus.

When data analysts train a classifier and check if its accuracy is significantly different from chance, they are implicitly performing a two-sample test. We investigate the statistical properties of this flexible approach in the high-dimensional setting. We prove two results that hold for all classifiers in any dimensions: if its true error remains $\epsilon$-better than chance for some $\epsilon>0$ as $d,n \to \infty$, then (a) the permutation-based test is consistent (has power approaching to one), (b) a computationally efficient test based on a Gaussian approximation of the null distribution is also consistent. To get a finer understanding of the rates of consistency, we study a specialized setting of distinguishing Gaussians with mean-difference $\delta$ and common (known or unknown) covariance $\Sigma$, when $d/n \to c \in (0,\infty)$. We study variants of Fisher's linear discriminant analysis (LDA) such as "naive Bayes" in a nontrivial regime when $\epsilon \to 0$ (the Bayes classifier has true accuracy approaching 1/2), and contrast their power with corresponding variants of Hotelling's test. Surprisingly, the expressions for their power match exactly in terms of $n,d,\delta,\Sigma$, and the LDA approach is only worse by a constant factor, achieving an asymptotic relative efficiency (ARE) of $1/\sqrt{\pi}$ for balanced samples. We also extend our results to high-dimensional elliptical distributions with finite kurtosis. Other results of independent interest include minimax lower bounds, and the optimality of Hotelling's test when $d=o(n)$. Simulation results validate our theory, and we present practical takeaway messages along with natural open problems.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Failing Loudly: An Empirical Study of Methods for Detecting Dataset Shift (2018, methodology): “Analyzing the simple case where one wishes to test the means of two Gaussians, [17] recently made the intriguing discovery that the power of a classification-based strategy using Fisher’s Linear Discriminant Analysis (LDA) classifier achieves minimax rate-optimal performance.”
Learning Deep Kernels for Non-Parametric Two-Sample Tests (2020, background): “The most common performance metric is the accuracy (Lopez-Paz & Oquab, 2017); this scheme is fairly common among practitioners, and Ramdas & Wasserman (2016) showed it to be rate-optimal in one extremely limited setting (linear discriminant analysis between high-dimensional Gaussians with identical…”