Timezone: »
Poster
Minimax Estimation of Maximum Mean Discrepancy with Radial Kernels
Ilya Tolstikhin · Bharath Sriperumbudur · Bernhard Schölkopf
Maximum Mean Discrepancy (MMD) is a distance on the space of probability measures which has found numerous applications in machine learning and nonparametric testing. This distance is based on the notion of embedding probabilities in a reproducing kernel Hilbert space. In this paper, we present the first known lower bounds for the estimation of MMD based on finite samples. Our lower bounds hold for any radial universal kernel on $\R^d$ and match the existing upper bounds up to constants that depend only on the properties of the kernel. Using these lower bounds, we establish the minimax rate optimality of the empirical estimator and its $U$-statistic variant, which are usually employed in applications.
Author Information
Ilya Tolstikhin (Google, Brain Team, Zurich)
Bharath Sriperumbudur (Penn State University)
Bernhard Schölkopf (MPI for Intelligent Systems, Tübingen)
Bernhard Scholkopf received degrees in mathematics (London) and physics (Tubingen), and a doctorate in computer science from the Technical University Berlin. He has researched at AT&T Bell Labs, at GMD FIRST, Berlin, at the Australian National University, Canberra, and at Microsoft Research Cambridge (UK). In 2001, he was appointed scientific member of the Max Planck Society and director at the MPI for Biological Cybernetics; in 2010 he founded the Max Planck Institute for Intelligent Systems. For further information, see www.kyb.tuebingen.mpg.de/~bs.
More from the Same Authors
-
2020 Workshop: Causal Discovery and Causality-Inspired Machine Learning »
Biwei Huang · Sara Magliacane · Kun Zhang · Danielle Belgrave · Elias Bareinboim · Daniel Malinsky · Thomas Richardson · Christopher Meek · Peter Spirtes · Bernhard Schölkopf -
2020 Poster: Robust Persistence Diagrams using Reproducing Kernels »
Siddharth Vishwanath · Kenji Fukumizu · Satoshi Kuriki · Bharath Sriperumbudur -
2020 Memorial: In Memory of Olivier Chapelle »
Bernhard Schölkopf · Andre Elisseeff · Olivier Bousquet · Vladimir Vapnik · Jason E Weston -
2020 Poster: Learning Kernel Tests Without Data Splitting »
Jonas M. Kübler · Wittawat Jitkrittum · Bernhard Schölkopf · Krikamol Muandet -
2020 Poster: Algorithmic recourse under imperfect causal knowledge: a probabilistic approach »
Amir-Hossein Karimi · Julius von Kügelgen · Bernhard Schölkopf · Isabel Valera -
2020 Poster: Causal analysis of Covid-19 Spread in Germany »
Atalanti Mastakouri · Bernhard Schölkopf -
2020 Spotlight: Algorithmic recourse under imperfect causal knowledge: a probabilistic approach »
Amir-Hossein Karimi · Julius von Kügelgen · Bernhard Schölkopf · Isabel Valera -
2020 Poster: Relative gradient optimization of the Jacobian term in unsupervised deep learning »
Luigi Gresele · Giancarlo Fissore · Adrián Javaloy · Bernhard Schölkopf · Aapo Hyvarinen -
2020 Poster: What Do Neural Networks Learn When Trained With Random Labels? »
Hartmut Maennel · Ibrahim Alabdulmohsin · Ilya Tolstikhin · Robert Baldock · Olivier Bousquet · Sylvain Gelly · Daniel Keysers -
2020 Spotlight: What Do Neural Networks Learn When Trained With Random Labels? »
Hartmut Maennel · Ibrahim Alabdulmohsin · Ilya Tolstikhin · Robert Baldock · Olivier Bousquet · Sylvain Gelly · Daniel Keysers -
2019 Poster: On the Fairness of Disentangled Representations »
Francesco Locatello · Gabriele Abbati · Thomas Rainforth · Stefan Bauer · Bernhard Schölkopf · Olivier Bachem -
2019 Poster: On the Transfer of Inductive Bias from Simulation to the Real World: a New Disentanglement Dataset »
Muhammad Waleed Gondal · Manuel Wuethrich · Djordje Miladinovic · Francesco Locatello · Martin Breidt · Valentin Volchkov · Joel Akpo · Olivier Bachem · Bernhard Schölkopf · Stefan Bauer -
2019 Poster: Perceiving the arrow of time in autoregressive motion »
Kristof Meding · Dominik Janzing · Bernhard Schölkopf · Felix A. Wichmann -
2019 Poster: Selecting causal brain features with a single conditional independence test per feature »
Atalanti Mastakouri · Bernhard Schölkopf · Dominik Janzing -
2019 Poster: Kernel Stein Tests for Multiple Model Comparison »
Jen Ning Lim · Makoto Yamada · Bernhard Schölkopf · Wittawat Jitkrittum -
2019 Poster: Practical and Consistent Estimation of f-Divergences »
Paul Rubenstein · Olivier Bousquet · Josip Djolonga · Carlos Riquelme · Ilya Tolstikhin -
2019 Spotlight: Perceiving the arrow of time in autoregressive motion »
Kristof Meding · Dominik Janzing · Bernhard Schölkopf · Felix A. Wichmann -
2018 Poster: Informative Features for Model Comparison »
Wittawat Jitkrittum · Heishiro Kanagawa · Patsorn Sangkloy · James Hays · Bernhard Schölkopf · Arthur Gretton -
2018 Poster: Adaptive Skip Intervals: Temporal Abstraction for Recurrent Dynamical Models »
Alexander Neitz · Giambattista Parascandolo · Stefan Bauer · Bernhard Schölkopf -
2017 Workshop: Learning on Distributions, Functions, Graphs and Groups »
Florence d'Alché-Buc · Krikamol Muandet · Bharath Sriperumbudur · Zoltán Szabó -
2017 Poster: Avoiding Discrimination through Causal Reasoning »
Niki Kilbertus · Mateo Rojas Carulla · Giambattista Parascandolo · Moritz Hardt · Dominik Janzing · Bernhard Schölkopf -
2017 Poster: Interpolated Policy Gradient: Merging On-Policy and Off-Policy Gradient Estimation for Deep Reinforcement Learning »
Shixiang (Shane) Gu · Timothy Lillicrap · Richard Turner · Zoubin Ghahramani · Bernhard Schölkopf · Sergey Levine -
2017 Poster: AdaGAN: Boosting Generative Models »
Ilya Tolstikhin · Sylvain Gelly · Olivier Bousquet · Carl-Johann SIMON-GABRIEL · Bernhard Schölkopf -
2016 Workshop: Adaptive and Scalable Nonparametric Methods in Machine Learning »
Aaditya Ramdas · Arthur Gretton · Bharath Sriperumbudur · Han Liu · John Lafferty · Samory Kpotufe · Zoltán Szabó -
2016 Poster: Convergence guarantees for kernel-based quadrature rules in misspecified settings »
Motonobu Kanagawa · Bharath Sriperumbudur · Kenji Fukumizu -
2016 Poster: Consistent Kernel Mean Estimation for Functions of Random Variables »
Carl-Johann Simon-Gabriel · Adam Scibior · Ilya Tolstikhin · Bernhard Schölkopf -
2015 Poster: Optimal Rates for Random Fourier Features »
Bharath Sriperumbudur · Zoltan Szabo -
2015 Spotlight: Optimal Rates for Random Fourier Features »
Bharath Sriperumbudur · Zoltan Szabo -
2014 Workshop: Modern Nonparametrics 3: Automating the Learning Pipeline »
Eric Xing · Mladen Kolar · Arthur Gretton · Samory Kpotufe · Han Liu · Zoltán Szabó · Alan L Yuille · Andrew G Wilson · Ryan Tibshirani · Sasha Rakhlin · Damian Kozbur · Bharath Sriperumbudur · David Lopez-Paz · Kirthevasan Kandasamy · Francesco Orabona · Andreas Damianou · Wacha Bounliphone · Yanshuai Cao · Arijit Das · Yingzhen Yang · Giulia DeSalvo · Dmitry Storcheus · Roberto Valerio -
2014 Poster: Kernel Mean Estimation via Spectral Filtering »
Krikamol Muandet · Bharath Sriperumbudur · Bernhard Schölkopf -
2013 Workshop: Modern Nonparametric Methods in Machine Learning »
Arthur Gretton · Mladen Kolar · Samory Kpotufe · John Lafferty · Han Liu · Bernhard Schölkopf · Alexander Smola · Rob Nowak · Mikhail Belkin · Lorenzo Rosasco · peter bickel · Yue Zhao -
2013 Workshop: NIPS 2013 Workshop on Causality: Large-scale Experiment Design and Inference of Causal Mechanisms »
Isabelle Guyon · Leon Bottou · Bernhard Schölkopf · Alexander Statnikov · Evelyne Viegas · james m robins -
2013 Poster: The Randomized Dependence Coefficient »
David Lopez-Paz · Philipp Hennig · Bernhard Schölkopf -
2013 Poster: PAC-Bayes-Empirical-Bernstein Inequality »
Ilya Tolstikhin · Yevgeny Seldin -
2013 Poster: Statistical analysis of coupled time series with Kernel Cross-Spectral Density operators. »
Michel Besserve · Nikos K Logothetis · Bernhard Schölkopf -
2013 Spotlight: PAC-Bayes-Empirical-Bernstein Inequality »
Ilya Tolstikhin · Yevgeny Seldin -
2013 Poster: Causal Inference on Time Series using Restricted Structural Equation Models »
Jonas Peters · Dominik Janzing · Bernhard Schölkopf -
2012 Poster: Learning from Distributions via Support Measure Machines »
Krikamol Muandet · Kenji Fukumizu · Francesco Dinuzzo · Bernhard Schölkopf -
2012 Spotlight: Learning from Distributions via Support Measure Machines »
Krikamol Muandet · Kenji Fukumizu · Francesco Dinuzzo · Bernhard Schölkopf -
2012 Poster: Semi-Supervised Domain Adaptation with Non-Parametric Copulas »
David Lopez-Paz · José Miguel Hernández-Lobato · Bernhard Schölkopf -
2012 Spotlight: Semi-Supervised Domain Adaptation with Non-Parametric Copulas »
David Lopez-Paz · José Miguel Hernández-Lobato · Bernhard Schölkopf -
2012 Poster: The representer theorem for Hilbert spaces: a necessary and sufficient condition »
Francesco Dinuzzo · Bernhard Schölkopf -
2012 Poster: Optimal kernel choice for large-scale two-sample tests »
Arthur Gretton · Bharath Sriperumbudur · Dino Sejdinovic · Heiko Strathmann · Sivaraman Balakrishnan · Massimiliano Pontil · Kenji Fukumizu -
2011 Workshop: Philosophy and Machine Learning »
Marcello Pelillo · Joachim M Buhmann · Tiberio Caetano · Bernhard Schölkopf · Larry Wasserman -
2011 Workshop: Cosmology meets Machine Learning »
Michael Hirsch · Sarah Bridle · Bernhard Schölkopf · Phil Marshall · Stefan Harmeling · Mark Girolami -
2011 Invited Talk (Posner Lecture): From kernels to causal inference »
Bernhard Schölkopf -
2011 Poster: Learning in Hilbert vs. Banach Spaces: A Measure Embedding Viewpoint »
Bharath Sriperumbudur · Kenji Fukumizu · Gert Lanckriet -
2011 Poster: Recovering Intrinsic Images with a Global Sparsity Prior on Reflectance »
Peter Gehler · Carsten Rother · Martin Kiefel · Lumin Zhang · Bernhard Schölkopf -
2011 Poster: Causal Discovery with Cyclic Additive Noise Models »
Joris M Mooij · Dominik Janzing · Tom Heskes · Bernhard Schölkopf -
2010 Spotlight: Switched Latent Force Models for Movement Segmentation »
Mauricio A Alvarez · Jan Peters · Bernhard Schölkopf · Neil D Lawrence -
2010 Poster: Space-Variant Single-Image Blind Deconvolution for Removing Camera Shake »
Stefan Harmeling · Michael Hirsch · Bernhard Schölkopf -
2010 Poster: Switched Latent Force Models for Movement Segmentation »
Mauricio A Alvarez · Jan Peters · Bernhard Schölkopf · Neil D Lawrence -
2010 Poster: Probabilistic latent variable models for distinguishing between cause and effect »
Joris M Mooij · Oliver Stegle · Dominik Janzing · Kun Zhang · Bernhard Schölkopf -
2009 Workshop: Connectivity Inference in Neuroimaging »
Karl Friston · Moritz Grosse-Wentrup · Uta Noppeney · Bernhard Schölkopf -
2009 Poster: Kernel Choice and Classifiability for RKHS Embeddings of Probability Distributions »
Bharath Sriperumbudur · Kenji Fukumizu · Arthur Gretton · Gert Lanckriet · Bernhard Schölkopf -
2009 Oral: Kernel Choice and Classifiability for RKHS Embeddings of Probability Distributions »
Bharath Sriperumbudur · Kenji Fukumizu · Arthur Gretton · Gert Lanckriet · Bernhard Schölkopf -
2009 Poster: On the Convergence of the Concave-Convex Procedure »
Bharath Sriperumbudur · Gert Lanckriet -
2009 Poster: A Fast, Consistent Kernel Two-Sample Test »
Arthur Gretton · Kenji Fukumizu · Zaid Harchaoui · Bharath Sriperumbudur -
2009 Spotlight: A Fast, Consistent Kernel Two-Sample Test »
Arthur Gretton · Kenji Fukumizu · Zaid Harchaoui · Bharath Sriperumbudur -
2008 Workshop: Causality: objectives and assessment »
Isabelle Guyon · Dominik Janzing · Bernhard Schölkopf -
2008 Mini Symposium: Computational Photography »
Bill Freeman · Bernhard Schölkopf -
2008 Poster: Characteristic Kernels on Groups and Semigroups »
Kenji Fukumizu · Bharath Sriperumbudur · Arthur Gretton · Bernhard Schölkopf -
2008 Oral: Characteristic Kernels on Groups and Semigroups »
Kenji Fukumizu · Bharath Sriperumbudur · Arthur Gretton · Bernhard Schölkopf -
2008 Poster: Nonlinear causal discovery with additive noise models »
Patrik O Hoyer · Dominik Janzing · Joris M Mooij · Jonas Peters · Bernhard Schölkopf -
2008 Poster: Effects of Stimulus Type and of Error-Correcting Code Design on BCI Speller Performance »
Jeremy Hill · Jason Farquhar · Suzanne Martens · Felix Bießmann · Bernhard Schölkopf -
2008 Poster: Bayesian Experimental Design of Magnetic Resonance Imaging Sequences »
Matthias Seeger · Hannes Nickisch · Rolf Pohmann · Bernhard Schölkopf -
2008 Spotlight: Nonlinear causal discovery with additive noise models »
Patrik O Hoyer · Dominik Janzing · Joris M Mooij · Jonas Peters · Bernhard Schölkopf -
2008 Spotlight: Bayesian Experimental Design of Magnetic Resonance Imaging Sequences »
Matthias Seeger · Hannes Nickisch · Rolf Pohmann · Bernhard Schölkopf -
2008 Spotlight: Effects of Stimulus Type and of Error-Correcting Code Design on BCI Speller Performance »
Jeremy Hill · Jason Farquhar · Suzanne Martens · Felix Bießmann · Bernhard Schölkopf -
2008 Poster: An empirical Analysis of Domain Adaptation Algorithms for Genomic Sequence Analysis »
Gabriele B Schweikert · Christian Widmer · Bernhard Schölkopf · Gunnar Rätsch -
2008 Poster: Diffeomorphic Dimensionality Reduction »
Christian Walder · Bernhard Schölkopf -
2007 Spotlight: Kernel Measures of Conditional Dependence »
Kenji Fukumizu · Arthur Gretton · Xiaohai Sun · Bernhard Schölkopf -
2007 Poster: An Analysis of Inference with the Universum »
Fabian H Sinz · Olivier Chapelle · Alekh Agarwal · Bernhard Schölkopf -
2007 Poster: Kernel Measures of Conditional Dependence »
Kenji Fukumizu · Arthur Gretton · Xiaohai Sun · Bernhard Schölkopf -
2007 Spotlight: An Analysis of Inference with the Universum »
Fabian H Sinz · Olivier Chapelle · Alekh Agarwal · Bernhard Schölkopf -
2007 Spotlight: A Kernel Statistical Test of Independence »
Arthur Gretton · Kenji Fukumizu · Choon Hui Teo · Le Song · Bernhard Schölkopf · Alexander Smola -
2007 Poster: A Kernel Statistical Test of Independence »
Arthur Gretton · Kenji Fukumizu · Choon Hui Teo · Le Song · Bernhard Schölkopf · Alexander Smola -
2006 Poster: Implicit Surfaces with Globally Regularised and Compactly Supported Basis Functions »
Christian Walder · Bernhard Schölkopf · Olivier Chapelle -
2006 Poster: Learning Dense 3D Correspondence »
Florian Steinke · Bernhard Schölkopf · Volker Blanz -
2006 Poster: A Local Learning Approach for Clustering »
Mingrui Wu · Bernhard Schölkopf -
2006 Poster: A Kernel Method for the Two-Sample-Problem »
Arthur Gretton · Karsten Borgwardt · Malte J Rasch · Bernhard Schölkopf · Alexander Smola -
2006 Poster: Correcting Sample Selection Bias by Unlabeled Data »
Jiayuan Huang · Alexander Smola · Arthur Gretton · Karsten Borgwardt · Bernhard Schölkopf -
2006 Spotlight: Correcting Sample Selection Bias by Unlabeled Data »
Jiayuan Huang · Alexander Smola · Arthur Gretton · Karsten Borgwardt · Bernhard Schölkopf -
2006 Talk: A Kernel Method for the Two-Sample-Problem »
Arthur Gretton · Karsten Borgwardt · Malte J Rasch · Bernhard Schölkopf · Alexander Smola -
2006 Poster: A Nonparametric Approach to Bottom-Up Visual Saliency »
Wolf Kienzle · Felix A Wichmann · Bernhard Schölkopf · Matthias Franz -
2006 Poster: Learning with Hypergraphs: Clustering, Classification, and Embedding »
Denny Zhou · Jiayuan Huang · Bernhard Schölkopf