Research map / Learning theory and algorithms / Sample complexity

Nearest-Neighbor Radii under Dependent Sampling

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Density and property estimation · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Studies k-nearest-neighbor radii under strong-mixing dependent triangular arrays, proving a.s. convergence under polynomial mixing and sharp moment bounds of order (k/n)^{p/s} under geometric mixing, with experiments on synthetic dependent data and time-series benchmarks.

Problem

How dependence in observations (strong mixing along each row of a triangular array) affects the scale of k-nearest-neighbor radii around a fixed query point, which determines the locality of many nearest-neighbor learning methods.

Approach

Extends classical i.i.d. k-NN radius results to strong-mixing triangular arrays via a Bernstein-type inequality for alpha-mixing sequences and blocking, showing dependence changes concentration (log n penalty) but not the canonical scale (k/n)^{1/s}, with s a local intrinsic exponent.

Key results

• Raw-kNN and PCA-kNN average long-horizon MSE 0.628 and 0.627 vs MOMENT 0.617.
• Classification mean accuracy 0.748 for both kNN variants vs 0.794 for MOMENT across 91 UCR datasets.
• Theory: E[R^p] <= C(k/n)^{p/s} for k >= K0 log n under geometric mixing, with matching lower bound (k/(2c+ n))^{p/s}/2.

Surprising findings

• Raw-kNN and PCA-kNN perform comparably on real data, with MOMENT outperforming both on classification and long-horizon forecasting.

Limitations

• Results are pointwise at a fixed query point; uniform convergence over the support is left open.
• Non-asymptotic upper bounds require k >= K0 log n due to blocking, and compact support is assumed.
• Real-data experiments show kNN baselines underperform MOMENT, so practical utility is limited in those settings.

Experimental setup

Datasets: Time Series Pile Informer ETT/Electricity/Traffic/Weather/Exchange/ILI Monash Time Series Forecasting Archive UCR Time Series Archive synthetic linear Gaussian state-space, hidden Markov, and FFT Gaussian process sequences synthetic Gaussian AR(1) latent process

Benchmarks: Informer long-horizon forecasting datasets Monash short-horizon forecasting groups UCR classification archive (91 datasets) synthetic moment-rate and entropy experiments

Metrics: MSE MAE sMAPE accuracy empirical moment slope entropy estimate

Baselines: MOMENT Raw-kNN (ablation) PCA-kNN

Builds on: Bernstein-type inequality for alpha-mixing sequences Kozachenko-Leonenko entropy estimator MOMENT

Closest papers by meaning

• Embedding Dimension of Contrastive Learning and $k$-Nearest Neighbors (NeurIPS 2024 · similarity 0.84)
• Statistical Guarantees for High-Dimensional Stochastic Gradient Descent (NeurIPS 2025 · similarity 0.83)
• Hierarchical Integral Probability Metrics: A distance on random probability measures with low sample complexity (ICML 2024 · similarity 0.83)
• Sharp Rates in Dependent Learning Theory: Avoiding Sample Size Deflation for the Square Loss (ICML 2024 · similarity 0.83)
• Towards Theoretical Understanding of Learning Large-scale Dependent Data via Random Features (ICML 2024 · similarity 0.83)
• Optimal Sample Complexity of Contrastive Learning (ICLR 2024 · similarity 0.83)