Universal Bayes consistency in metric spaces

DOI10.1214/20-AOS2029zbMATH Open1486.62324arXiv1906.09855OpenAlexW3204278298MaRDI QIDQ2054482FDOQ2054482

Authors: Steve Hanneke, Sivan Sabato, Roi Weiss, Aryeh Kontorovich 

Publication date: 3 December 2021

Published in: The Annals of Statistics (Search for Journal in Brave)

Abstract: We extend a recently proposed 1-nearest-neighbor based multiclass learning algorithm and prove that our modification is universally strongly Bayes-consistent in all metric spaces admitting any such learner, making it an "optimistically universal" Bayes-consistent learner. This is the first learning algorithm known to enjoy this property; by comparison, the $k$-NN classifier and its variants are not generally universally Bayes-consistent, except under additional structural assumptions, such as an inner product, a norm, finite dimension, or a Besicovitch-type property. The metric spaces in which universal Bayes consistency is possible are the "essentially separable" ones -- a notion that we define, which is more general than standard separability. The existence of metric spaces that are not essentially separable is widely believed to be independent of the ZFC axioms of set theory. We prove that essential separability exactly characterizes the existence of a universal Bayes-consistent learner for the given metric space. In particular, this yields the first impossibility result for universal Bayes consistency. Taken together, our results completely characterize strong and weak universal Bayes consistency in metric spaces.

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

Recommendations

• A universal prior distribution for Bayesian consistency of non parametric procedures
• Universality of Bayesian predictions
• Strong consistency of nonparametric Bayes density estimation on compact metric spaces with applications to specific manifolds
• \(L^\infty\) metric criteria for convergence in Bayesian recursive inference systems
• On the uniform consistency of Bayes estimates for multinomial probabilities
• On Consistency of Bayes Procedures
• Universality of Bayesian mixture predictors
• On the consistency of Bayes estimates

zbMATH Keywords

classificationnearest neighbormetric spaceBayes consistency

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Empirical decision procedures; empirical Bayes procedures (62C12) Statistics on metric spaces (62R20) Consistency and independence results (03E35) Probabilistic metric spaces (54E70)

Cites Work

• Functional Classification in Hilbert Spaces
• Nearest neighbor pattern classification
• Consistent nonparametric regression. Discussion
• Title not available (Why is that?)
• Understanding machine learning. From theory to algorithms
• A distribution-free theory of nonparametric regression
• Discriminatory Analysis. Nonparametric Discrimination: Consistency Properties
• Uniform Central Limit Theorems
• Rates of Convergence of the Functional $k$-Nearest Neighbor Estimate
• Set Theory
• Consistent Nonparametric Regression for Functional Data Under the Stone–Besicovitch Conditions
• Nearest neighbor classification in infinite dimension
• Title not available (Why is that?)
• Title not available (Why is that?)
• Rates of convergence of nearest neighbor estimation under arbitrary sampling
• On the kernel rule for function classification
• Exponential bounds of mean error for the nearest neighbor estimates of regression functions
• Efficient Classification for Metric Data
• Forcings with ideals and simple forcing notions
• Title not available (Why is that?)
• Nearly optimal classification for semimetrics
• Near-Optimal Sample Compression for Nearest Neighbors
• Vitali covering theorem in Hilbert space
• Active nearest-neighbor learning in metric spaces
• Title not available (Why is that?)
• Title not available (Why is that?)
• PAC-Bayesian compression bounds on the prediction error of learning algorithms for classification

Cited In (12)

• Universal regression with adversarial responses
• Convergence of a stochastic collocation finite volume method for the compressible Navier-Stokes system
• Fast convergence on perfect classification for functional data
• Distributed adaptive nearest neighbor classifier: algorithm and theory
• Nearest neighbor classification in infinite dimension
• From undecidability of non-triviality and finiteness to undecidability of learnability
• A nearest neighbor characterization of Lebesgue points in metric measure spaces
• Title not available (Why is that?)
• Finsler currents
• Non-uniform packings
• Universal consistency of the \(k\)-NN rule in metric spaces and Nagata dimension
• \(L^\infty\) metric criteria for convergence in Bayesian recursive inference systems

This page was built for publication: Universal Bayes consistency in metric spaces

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