Universal consistency of the $k$-NN rule in metric spaces and Nagata dimension. II

• URL: http://arxiv.org/abs/2305.17282v5
• Date: Wed, 20 Mar 2024 17:25:52 GMT
• Title: Universal consistency of the $k$-NN rule in metric spaces and Nagata dimension. II
• Authors: Sushma Kumari, Vladimir G. Pestov,
• Abstract summary: We show that the rule is strongly universally consistent in such spaces in the absence of ties. One deduces that the $k$-NN rule is universally consistent in metric spaces having finite dimension in the sense of de Groot.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We continue to investigate the $k$ nearest neighbour ($k$-NN) learning rule in complete separable metric spaces. Thanks to the results of C\'erou and Guyader (2006) and Preiss (1983), this rule is known to be universally consistent in every such metric space that is sigma-finite dimensional in the sense of Nagata. Here we show that the rule is strongly universally consistent in such spaces in the absence of ties. Under the tie-breaking strategy applied by Devroye, Gy\"{o}rfi, Krzy\.{z}ak, and Lugosi (1994) in the Euclidean setting, we manage to show the strong universal consistency in non-Archimedian metric spaces (that is, those of Nagata dimension zero). Combining the theorem of C\'erou and Guyader with results of Assouad and Quentin de Gromard (2006), one deduces that the $k$-NN rule is universally consistent in metric spaces having finite dimension in the sense of de Groot. In particular, the $k$-NN rule is universally consistent in the Heisenberg group which is not sigma-finite dimensional in the sense of Nagata as follows from an example independently constructed by Kor\'anyi and Reimann (1995) and Sawyer and Wheeden (1992).

Related papers

• Entanglement in Typical States of Chern-Simons Theory [0.0]
  We compute various averages over bulk geometries of quantum states prepared by the Chern-Simons path integral. We find that the typical state is unentangled across any bipartition of the tori defining the boundary Hilbert space. We show that this averaged state is a separable state, which implies that different boundary tori only share classical correlations for complex enough bulk geometries.
  arXiv  Detail & Related papers  (2025-03-27T18:11:55Z)
• Variance Norms for Kernelized Anomaly Detection [2.389598109913754]
  We present a unified theory for Mahalanobis-type anomaly detection on Banach spaces. We introduce the notion of a kernelized nearest-neighbour Mahalanobis distance for semi-supervised anomaly detection. In an empirical study on 12 real-world datasets, we demonstrate that the kernelized nearest-neighbour Mahalanobis distance outperforms the traditional kernelized Mahalanobis distance.
  arXiv  Detail & Related papers  (2024-07-16T15:59:49Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems. We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
  arXiv  Detail & Related papers  (2023-02-03T03:19:14Z)
• On the relation between completely bounded and $(1,cb)$-summing maps with applications to quantum XOR games [65.51757376525798]
  We show that given a linear map from a general operator space into the dual of a C$*$-algebra, its completely bounded norm is upper bounded by a universal constant times its $(''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  arXiv  Detail & Related papers  (2021-12-09T21:06:52Z)
• Dimension Free Generalization Bounds for Non Linear Metric Learning [61.193693608166114]
  We provide uniform generalization bounds for two regimes -- the sparse regime, and a non-sparse regime. We show that by relying on a different, new property of the solutions, it is still possible to provide dimension free generalization guarantees.
  arXiv  Detail & Related papers  (2021-02-07T14:47:00Z)
• Entangled subspaces and generic local state discrimination with pre-shared entanglement [0.0]
  Local state discrimination is closely related to the topic of entangled subspaces. We introduce $r$-entangled subspaces, which naturally generalize previously studied spaces to higher multipartite entanglement.
  arXiv  Detail & Related papers  (2020-10-06T16:57:40Z)
• Universal consistency of Wasserstein $k$-NN classifier: Negative and Positive Results [0.0]
  Wasserstein distance provides a notion of dissimilarities between probability measures. We show that the $k$-NN classifier is not universally consistent on the space of measures supported in $(0,1)$.
  arXiv  Detail & Related papers  (2020-09-10T03:05:05Z)
• Metrizing Weak Convergence with Maximum Mean Discrepancies [88.54422104669078]
  This paper characterizes the maximum mean discrepancies (MMD) that metrize the weak convergence of probability measures for a wide class of kernels. We prove that, on a locally compact, non-compact, Hausdorff space, the MMD of a bounded continuous Borel measurable kernel k, metrizes the weak convergence of probability measures if and only if k is continuous.
  arXiv  Detail & Related papers  (2020-06-16T15:49:33Z)
• A learning problem whose consistency is equivalent to the non-existence of real-valued measurable cardinals [0.0]
  We show that the $k$-NN classifier is universally consistent in every metric space whose separable subspaces are sigma-finite dimensional. Results were inspired by an example sketched by C'erou and Guyader in 2006 at an intuitive level of rigour.
  arXiv  Detail & Related papers  (2020-05-04T23:40:28Z)
• Quantum Geometric Confinement and Dynamical Transmission in Grushin Cylinder [68.8204255655161]
  We classify the self-adjoint realisations of the Laplace-Beltrami operator minimally defined on an infinite cylinder. We retrieve those distinguished extensions previously identified in the recent literature, namely the most confining and the most transmitting.
  arXiv  Detail & Related papers  (2020-03-16T11:37:23Z)
• Universal consistency of the $k$-NN rule in metric spaces and Nagata dimension [0.0]
  The $k$ nearest neighbour learning rule is universally consistent in every metric space $X$ that is sigma-finite dimensional in the sense of Nagata. We show that it is possible to give a direct proof along the same lines as the original theorem of Charles J. Stone (1977) about the universal consistency of the $k$-NN classifier in the finite dimensional Euclidean space.
  arXiv  Detail & Related papers  (2020-02-28T14:59:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.