Paperlane

no. 12 · Tuesday 10 November 2026

Nearest-Neighbor Radii under Dependent Sampling

Yuanyuan Gao, Yilong Hou and Zhexiao Lin

math.ST · v2

Abstract

Nearest-neighbor methods are fundamental to classical and modern machine learning, yet their geometric properties are typically analyzed under independent sampling. In this paper, we study the nearest-neighbor radii under dependent sampling. We consider strong mixing dependent observations and ask whether dependence changes the scale of nearest-neighbor neighborhoods. We establish distribution-free almost sure convergence under polynomial mixing and sharp non-asymptotic moment bounds under geometric mixing. The moment bounds depend on the local intrinsic dimension rather than the ambient dimension, making the results applicable to high-dimensional data supported on lower-dimensional manifolds. Synthetic experiments and real-world time-series benchmarks illustrate the theory, showing that nearest-neighbor geometry remains informative under dependent sampling.

comments
Accepted to 40th Conference on Neural Information Processing Systems (NeurIPS 2026)
fields
Statistics Theory
pdf ↗ page arXiv:2605.14343 ↗