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

• URL: http://arxiv.org/abs/2512.17058v1
• Date: Thu, 18 Dec 2025 20:49:44 GMT
• Title: Universal consistency of the $k$-NN rule in metric spaces and Nagata dimension. III
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove the last remaining implication allowing to claim the equivalence of the following conditions for a complete separable metric space $X$: (1) The $k$-nearest neighbour classifier is (weakly) universally consistent in $X$, (2) The strong Lebesgue--Besicovitch differentiation property holds in $X$ for every locally finite Borel measure, (3) $X$ is sigma-finite dimensional in the sense of Nagata. The equivalence (2)$\iff$(3) was announced by Preiss (1983), while a detailed proof of the implication (3)$\Rightarrow$(2) has appeared in Assouad and Quentin de Gromard (2006). The implication (2)$\Rightarrow$(1) was established by Cérou and Guyader (2006). We prove the implication (1)$\Rightarrow$(3). The result was conjectured in the first article in the series (Collins, Kumari, Pestov 2020), and here we also correct a wrong claim made in the second article (Kumari and Pestov 2024).

Related papers

• The I3322 quantum value is attained spatially but not in finite dimension [0.0]
  Let $S$ be the quantum supremum of the $I_3322$ Bell functional in the Collins-Gisin normalization (classical bound 0; two-qubit maximum exactly 1/4)<n>We prove: (i) no finite-dimensional quantum strategy attains $S$ -- any finite local dimensions, pure or mixed states, projective or POVM measurements -- proving Pal and Vertesi (2010)<n>We also determine the dimension complexity: with $S_d$ the optimum at local dimension $le d$ and $D()=mind:S-S_d
  arXiv  Detail & Related papers  (2026-09-03T15:48:01Z)
• A Counterexample to the Tang Zhang Schatten Norm Conjecture and Sharp Positive Results [1.8051706864605614]
  Tang and Zhang conjectured an explicit formula for every finite $p>1$.<n>We prove the conjectured sharp bound for every family of rank-at-most-one summands when $2leq pinfty$.
  arXiv  Detail & Related papers  (2026-08-16T06:10:33Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in convex optimization cannot be improved by a sparse-time algorithm.<n>We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis.
  arXiv  Detail & Related papers  (2026-08-03T17:57:01Z)
• $R$-equivalence on Cubic Surfaces I: Existing Cases with Non-Trivial Universal Equivalence [2.809000787228893]
  We consider all surfaces $V$ currently known to have non-trivial $R$-equivalence.<n>By devising new methods to study $R$-equivalence, we prove that for 2-adic surfaces with all-Eckardt reductions, $R$-equivalence is trivial or of exponent 2.
  arXiv  Detail & Related papers  (2026-03-19T17:57:38Z)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  Consider a Hermitian operator $A$ acting on a complex Hilbert space of $2n$.<n>We show that when $A$ has small degree in the Pauli expansion, or in other words, $A$ is a local $n$-qubit Hamiltonian.<n>We show that whenever $A$ is $d$-local, textiti.e., $deg(A)le d$, we have the following discretization-type inequality.
  arXiv  Detail & Related papers  (2025-09-15T14:26:11Z)
• Non-representable quantum measures [55.2480439325792]
  Grade-$d$ measures on a $sigma$-algebra $mathcalAsubseteq 2X$ over a set $X$ are generalizations of measures satisfying one of a hierarchy of weak additivity-type conditions.<n>Every signed polymeasure $lambda$ on $(X,mathcalA)d$ produces a grade-$d$ measure as its diagonal $widetildelambda(A):=lambda(A,cdots,A)$.
  arXiv  Detail & Related papers  (2025-08-20T00:47:24Z)
• High-spin measurements in an arbitrary two-qudit state [0.0]
  Violation of the CHSH inequality by a bipartite quantum state is now used in many quantum applications.<n>For an arbitrary state of two spin-$s$ dimension qudits, we find that the CHSH inequality is not violated under local Alice and Bob measurements.<n>For a pure two-qudit state with a higher degree of entanglement, the maximal value of the CHSH expectation turns out to be less than for a pure two-qudit state with lower entanglement.
  arXiv  Detail & Related papers  (2024-12-04T16:57:40Z)
• Overcomplete Tensor Decomposition via Koszul-Young Flattenings [56.82556231289414]
  We give a new algorithm for decomposing an $n_times n times n_3$ tensor as the sum of a minimal number of rank-1 terms.<n>We show that an even more general class of degree-$d$s cannot surpass rank $Cn$ for a constant $C = C(d)$.
  arXiv  Detail & Related papers  (2024-11-21T17:41:09Z)
• $L^1$ Estimation: On the Optimality of Linear Estimators [64.76492306585168]
  This work shows that the only prior distribution on $X$ that induces linearity in the conditional median is Gaussian. In particular, it is demonstrated that if the conditional distribution $P_X|Y=y$ is symmetric for all $y$, then $X$ must follow a Gaussian distribution.
  arXiv  Detail & Related papers  (2023-09-17T01:45:13Z)
• Higher rank antipodality [2.7309692684728617]
  Motivated by general probability theory, we say that the set $S$ in $mathbbRd$ is emphantipodal of rank $k$.<n>We show that this problem can be connected to a classical question in computer science on finding perfect hashes.
  arXiv  Detail & Related papers  (2023-07-31T17:15:46Z)
• Rigorous derivation of the Efimov effect in a simple model [68.8204255655161]
  We consider a system of three identical bosons in $mathbbR3$ with two-body zero-range interactions and a three-body hard-core repulsion of a given radius $a>0$.
  arXiv  Detail & Related papers  (2023-06-21T10:11:28Z)
• 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)
• Two definitions of maximally $\psi$-epistemic ontological model and preparation non-contextuality [0.0]
  We argue that 1M$psi$E and 2M$psi$E capture in notion of maximal $psi$-epistemicity. This leads one to conclude that 1M$psi$E and 2M$psi$E capture in notion of maximal $psi$-epistemicity.
  arXiv  Detail & Related papers  (2020-12-27T07:02:39Z)
• 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)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)

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.