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

• URL: http://arxiv.org/abs/2003.00894v2
• Date: Sun, 14 Jun 2020 17:57:08 GMT
• Title: Universal consistency of the $k$-NN rule in metric spaces and Nagata dimension
• Authors: Beno\^it Collins, Sushma Kumari, and Vladimir G. Pestov
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The $k$ nearest neighbour learning rule (under the uniform distance tie breaking) is universally consistent in every metric space $X$ that is sigma-finite dimensional in the sense of Nagata. This was pointed out by C\'erou and Guyader (2006) as a consequence of the main result by those authors, combined with a theorem in real analysis sketched by D. Preiss (1971) (and elaborated in detail by Assouad and Quentin de Gromard (2006)). 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. The generalization is non-trivial because of the distance ties being more prevalent in the non-euclidean setting, and on the way we investigate the relevant geometric properties of the metrics and the limitations of the Stone argument, by constructing various examples.

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)
• Geometric monotones of violations of quantum realism [89.99666725996975]
  Quantum realism states that projective measurements in quantum systems establish the reality of physical properties, even in the absence of a revealed outcome. This framework provides a nuanced perspective on the distinction between classical and quantum notions of realism, emphasizing the contextuality and complementarity inherent to quantum systems. We derive geometric monotones of quantum realism using trace distance, Hilbert-Schmidt distance, Schatten $p$-distances, Bures, and Hellinger distances.
  arXiv  Detail & Related papers  (2024-12-16T10:22:28Z)
• Conformal inference for regression on Riemannian Manifolds [49.7719149179179]
  We investigate prediction sets for regression scenarios when the response variable, denoted by $Y$, resides in a manifold, and the covariable, denoted by X, lies in Euclidean space. We prove the almost sure convergence of the empirical version of these regions on the manifold to their population counterparts.
  arXiv  Detail & Related papers  (2023-10-12T10:56:25Z)
• Dimension-free Remez Inequalities and norm designs [48.5897526636987]
  A class of domains $X$ and test sets $Y$ -- termed emphnorm -- enjoy dimension-free Remez-type estimates. We show that the supremum of $f$ does not increase by more than $mathcalO(log K)2d$ when $f$ is extended to the polytorus.
  arXiv  Detail & Related papers  (2023-10-11T22:46:09Z)
• Universal consistency of the $k$-NN rule in metric spaces and Nagata dimension. II [0.0]
  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.
  arXiv  Detail & Related papers  (2023-05-26T22:01:47Z)
• 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)
• Connections between graphs and matrix spaces [11.008438491376555]
  We show that the largest dimension over subspaces of $mathcalS_G$ containing only singular matrices is equal to the maximum size over subgraphs of $G$ without perfect matchings. We establish connections between acyclicity and nilpotency, between strong connectivity and irreducibility, and between isomorphism and conjugacy/congruence.
  arXiv  Detail & Related papers  (2022-06-09T23:45:15Z)
• Annihilating Entanglement Between Cones [77.34726150561087]
  We show that Lorentz cones are the only cones with a symmetric base for which a certain stronger version of the resilience property is satisfied. Our proof exploits the symmetries of the Lorentz cones and applies two constructions resembling protocols for entanglement distillation.
  arXiv  Detail & Related papers  (2021-10-22T15:02:39Z)
• A Unifying and Canonical Description of Measure-Preserving Diffusions [60.59592461429012]
  A complete recipe of measure-preserving diffusions in Euclidean space was recently derived unifying several MCMC algorithms into a single framework. We develop a geometric theory that improves and generalises this construction to any manifold.
  arXiv  Detail & Related papers  (2021-05-06T17:36:55Z)
• Constant-sized robust self-tests for states and measurements of unbounded dimension [0.0]
  We show that correlations $p_n,x$ robustly self-test the underlying states and measurements. We are the first to exhibit a constant-sized self-test for measurements of unbounded dimension.
  arXiv  Detail & Related papers  (2021-03-02T14:02:17Z)
• 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)
• 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)

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.