MONK -- Outlier-Robust Mean Embedding Estimation by Median-of-Means

Abstract

Mean embeddings provide an extremely flexible and powerful tool in machine learning and statistics to represent probability distributions and define a semi-metric (MMD, maximum mean discrepancy; also called N-distance or energy distance), with numerous successful applications. The representation is constructed as the expectation of the feature map defined by a kernel. As a mean, its classical empirical estimator, however, can be arbitrary severely affected even by a single outlier in case of unbounded features. To the best of our knowledge, unfortunately even the consistency of the existing few techniques trying to alleviate this serious sensitivity bottleneck is unknown. In this paper, we show how the recently emerged principle of median-of-means can be used to design estimators for kernel mean embedding and MMD with excessive resistance properties to outliers, and optimal sub-Gaussian deviation bounds under mild assumptions.

arXiv commentICML-2019: camera-ready paper. Code: https://bitbucket.org/TimotheeMathieu/monk-mmd

References in corpus (18)

• Equivalence of distance-based and RKHS-based statistics in hypothesis testing
• Generative Moment Matching Networks
• Distinguishing cause from effect using observational data: methods and benchmarks
• Geometric median and robust estimation in Banach spaces
• Training generative neural networks via Maximum Mean Discrepancy optimization
• Domain Generalization by Marginal Transfer Learning
• Persistence weighted Gaussian kernel for topological data analysis
• The Multiscale Laplacian Graph Kernel
• Information Theoretical Estimators Toolbox
• Learning from Distributions via Support Measure Machines
• Kernel Belief Propagation
• Testing for Homogeneity with Kernel Fisher Discriminant Analysis
• A Linear-Time Kernel Goodness-of-Fit Test
• Dimension-free PAC-Bayesian bounds for matrices, vectors, and linear least squares regression
• Kernel Mean Shrinkage Estimators
• Fast Mean Estimation with Sub-Gaussian Rates
• Bayesian Approaches to Distribution Regression
• Post Selection Inference with Kernels

Cited by in corpus (5)

• A Prototype-Oriented Framework for Unsupervised Domain Adaptation
• When OT meets MoM: Robust estimation of Wasserstein Distance
• Exponential Concentration for Geometric-Median-of-Means in Non-Positive Curvature Spaces
• Generalization Bounds in the Presence of Outliers: a Median-of-Means Study
• Robust Density Estimation under Besov IPM Losses