Universal consistency of Wasserstein k-NN classifier: a negative and some positive results

DOI10.1093/IMAIAI/IAAD027MaRDI QIDQ6164747zbMATH OpenOpenAlexFDO

Authors

Publication date 28 July 2023

Published in Information and Inference: A Journal of the IMA (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2009.04651

zbMATH Keywords

\(k\)-NNclassificationconsistencynearest neighboursoptimal transportWasserstein

Mathematics Subject Classification ID

Optimal transportation (49Q22) Bayesian inference (62F15) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Mathematical programming (90Cxx)

Abstract: The Wasserstein distance provides a notion of dissimilarities between probability measures, which has recent applications in learning of structured data with varying size such as images and text documents. In this work, we study the $k$-nearest neighbor classifier ($k$-NN) of probability measures under the Wasserstein distance. We show that the $k$-NN classifier is not universally consistent on the space of measures supported in $(0,1)$. As any Euclidean ball contains a copy of $(0,1)$, one should not expect to obtain universal consistency without some restriction on the base metric space, or the Wasserstein space itself. To this end, via the notion of $sigma$-finite metric dimension, we show that the $k$-NN classifier is universally consistent on spaces of measures supported in a $sigma$-uniformly discrete set. In addition, by studying the geodesic structures of the Wasserstein spaces for $p=1$ and $p=2$, we show that the $k$-NN classifier is universally consistent on the space of measures supported on a finite set, the space of Gaussian measures, and the space of measures with densities expressed as finite wavelet series.

Recommendations

• On the stochastic convergence of representations based on Wasserstein metrics
• Convergence and finite sample approximations of entropic regularized Wasserstein distances in Gaussian and RKHS settings
• Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces
• Robust Wasserstein profile inference and applications to machine learning
• Consistency of multiclass empirical risk minimization methods based on convex loss
• Strong universal consistency of neural network classifiers
• A class of Wasserstein metrics for probability distributions
• A Wasserstein-Type Distance in the Space of Gaussian Mixture Models

This page was built for publication: Universal consistency of Wasserstein k-NN classifier: a negative and some positive results

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6164747)