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
• 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

• Comments on the recent improvements of the MRRW bounds [59.04174294928297]
  We present the OpenAI proof in the language and context of coding theory, as an extension of the spectral method in which the single vector attached to a codeword is replaced by a subspace.<n>We also present the OpenAI proof in the language and context of coding theory, as an extension of the spectral method in which the single vector attached to a codeword is replaced by a subspace.
  arXiv  Detail & Related papers  (2026-09-01T20:43:23Z)
• Dimension Reduction for Curves: Simplified and Generalized [56.23281156053955]
  We revisit random projections for reducing the dimension of high-dimensional polygonal curves.<n>We give a simplified proof of the known $O(varepsilon-2log(nm))$ bound on the target dimension of a random projection.<n>Our proof is based on the concept of sparse oblivious subspace embeddings.
  arXiv  Detail & Related papers  (2026-07-03T08:48:35Z)
• Geometric Measurements of the Axiom of Choice in Neural Proof Embeddings [0.2538209532048866]
  We use Lean 4's kernel-level tracking of axiom dependence to show that the axiom of choice has a measurable geometric correlate in proof space.<n>We show that the signature survives length, file, author, and topic controls, and replicates under full-source encoders trained on normalised proof source.
  arXiv  Detail & Related papers  (2026-06-26T19:57:00Z)
• Uniform Laws of Large Numbers in Product Spaces [60.22626971185653]
  We study uniform convergence phenomena in cartesian product spaces.<n>We show that a uniform law of large numbers holds for a family of events if and only if the linear VC dimension of the family is finite.
  arXiv  Detail & Related papers  (2026-03-25T16:36:09Z)
• Dimension-Independent Convergence of Underdamped Langevin Monte Carlo in KL Divergence [50.719298242863744]
  Underdamped Langevin dynamics (ULD) is a widely-used sampler for Gibbs distributions $propto e-V$.<n>We prove the first dimension-free KL divergence bounds for discretized ULD.
  arXiv  Detail & Related papers  (2026-03-02T22:14:38Z)
• Riemannian Zeroth-Order Gradient Estimation with Structure-Preserving Metrics for Geodesically Incomplete Manifolds [57.179679246370114]
  We construct metrics that are geodesically complete while ensuring that every stationary point under the new metric remains stationary under the original one.<n>An $$-stationary point under the constructed metric $g'$ also corresponds to an $$-stationary point under the original metric $g'$.<n>Experiments on a practical mesh optimization task demonstrate that our framework maintains stable convergence even in the absence of geodesic completeness.
  arXiv  Detail & Related papers  (2026-01-12T22:08:03Z)
• Universal consistency of the $k$-NN rule in metric spaces and Nagata dimension. III [0.0]
  We prove the last remaining implication allowing to claim the equivalence of the following conditions for a complete separable metric space $X$.<n>The result was conjectured in the first article in the series.
  arXiv  Detail & Related papers  (2025-12-18T20:49:44Z)
• A General Metric-Space Formulation of the Time Warp Edit Distance (TWED) [0.0]
  We define a Generalized TWED (GTWED) that remains a true metric under mild assumptions.<n>This note focuses on the theoretical structure of GTWED and its implications for extending elastic distances beyond time series.
  arXiv  Detail & Related papers  (2025-11-06T13:25:23Z)
• Non-Euclidean Broximal Point Method: A Blueprint for Geometry-Aware Optimization [55.002497070656624]
  Broximal Point Method (BPM) offers an idealized optimization framework based on iteratively minimizing the objective function over norm balls centered at the current iterate.<n>It enjoys striking global convergence guarantees, converging linearly and in a finite number of steps for proper, closed and convex functions.<n>In this note, we ask whether the convergence theory of BPM can be extended to this more general, non-Euclidean setting.
  arXiv  Detail & Related papers  (2025-10-01T12:32:52Z)
• 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)
• Asymptotic Theory of Geometric and Adaptive $k$-Means Clustering [0.0]
  We revisit Pollard's classical result on consistency for $k$-means clustering in Euclidean space.<n>We show that all clustering procedures described above are strongly consistent.
  arXiv  Detail & Related papers  (2022-02-27T18:56:41Z)
• 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.