Nearest-Neighbor Radii under Dependent Sampling
Nearest-neighbor radii under mixing dependence converge almost surely with polynomial mixing and have sharp moment bounds scaling with local intrinsic dimension, remaining informative for high-dimensional dependent data.
Published 2026Atlanta Poster Session 2 · Wed, Dec 9, 4:30 PM–7:30 PM local time · Hall C1arXiv ↗OpenReview ↗
Only vote on papers you've read. Sign in with GitHub to vote.
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 concentrated near lower-dimensional manifolds. Synthetic experiments and real-world time-series benchmarks support the theory, showing that nearest-neighbor geometry remains informative under dependence sampling.