A two-sample test using graph total variation maximum mean discrepancy

Maximum mean discrepancies (MMDs) have emerged as a flexible and powerful tool for measuring the difference between two sets of samples. This talk discusses a new empirical MMD based on graph total variation (graph TV). Using a graph makes the MMD computationally tractable, while the connection to TV leads to a test with notably different operating characteristics from some more commonly studied tests based on kernel MMDs.

Specifically, I will show that, asymptotically, the graph TV MMD converges to a population-level metric between distributions: the dual norm of a density-weighted analog to total variation. This motivates the study of a nonparametric two-sample testing problem where, under the alternative, distributions are well separated according to this probability metric. A two-sample test based on graph TV MMD is found to be rate-optimal, in a minimax sense, for this testing problem, whereas a prototypical test involving kernel MMD is suboptimal. The reason is a familiar one: kernel methods are not locally adaptive and cannot detect spatially localized departures from the null, whereas the graph TV MMD can.