arXiv:2605.14343 · v2

Nearest-Neighbor Radii under Dependent Sampling

首次提交 2026-05-14 12:07

版本更新 2026-11-09 05:31

雷达观测 2026-11-10 13:19

摘要

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.

作者备注：Accepted to 40th Conference on Neural Information Processing Systems (NeurIPS 2026)