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.
| Comments: | 33 pages |
| Subjects: | Machine Learning (cs.LG); Statistics Theory (math.ST); Machine Learning (stat.ML) |
| Cite as: | arXiv:2605.14343 [cs.LG] |
| (or arXiv:2605.14343v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2605.14343 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Zhexiao Lin [view email]
[v1]
Thu, 14 May 2026 04:07:05 UTC (103 KB)