Technical Summary: Nearest-Neighbor Radii under Dependent Sampling

Problem Statement

Nearest-neighbor (NN) methods are foundational to both classical and modern machine learning, underpinning tasks ranging from $k$-NN classification and regression to manifold learning and information retrieval. The performance of these methods relies heavily on the geometric properties of the local neighborhoods they construct. Specifically, the distance from a query point $x$ to its $k$-th nearest neighbor, denoted as the radius $R_{n,k}(x)$, determines the scale of the local neighborhood and governs the bias-variance tradeoff.

While the behavior of $R_{n,k}(x)$ is well-understood under independent and identically distributed (i.i.d.) sampling—where the canonical scale is $(k/n)^{1/s}$ with $s$ being the local intrinsic dimension—many real-world learning problems involve dependent data (e.g., time series, reinforcement learning trajectories, spatiotemporal sensing). In such settings, observations are often strongly dependent even if their marginal distribution is stable. The central question addressed in this paper is: How does dependence affect the geometry of nearest-neighbor neighborhoods? Specifically, does dependence fundamentally alter the scaling of the nearest-neighbor radius, or does the canonical geometric scale remain robust?

Methodology and Setup

The authors analyze a triangular array of $\mathbb{R}^d$-valued random variables $[X_{n,i} : 1 \le i \le n, n \ge 1]$ defined on a common probability space.

• Marginal Distribution: All observations share a common marginal law $\mu$.
• Dependence Structure: The paper assumes strong mixing (α-mixing) dependence along each row of the array. The mixing coefficients $\alpha_m$ quantify the decay of dependence between segments of the sequence separated by $m$ indices.
• Object of Study: The radius $R_{n,k}(x) = \|X_{n}^{(k)}(x) - x\|$, where $X_{n}^{(k)}(x)$ is the $k$-th nearest neighbor of a fixed query point $x$ among $n$ observations.

The analysis distinguishes between two regimes of mixing:

1. Polynomial Mixing: $\alpha_m \lesssim m^{-\gamma}$ for some $\gamma > 1$.
2. Geometric (Exponential) Mixing: $\alpha_m \le e^{-\gamma m}$ for some $\gamma > 0$.

Theoretical results are formulated using a local exponent $s > 0$ rather than the ambient dimension $d$. This exponent characterizes the local mass accumulation near $x$ (i.e., $\mu(B(x,r)) \asymp r^s$), allowing the theory to apply to data concentrated near lower-dimensional manifolds.

Key Contributions and Results

1. Distribution-Free Almost Sure Convergence

Under polynomial $\alpha$-mixing, the authors establish a distribution-free almost sure convergence theorem.

• Result: If $k/n \to 0$, then $R_{n,k}(x) \xrightarrow{a.s.} r_x$, where $r_x$ is the distance from $x$ to the support of $\mu$.
• Implication: If $x$ is in the support of $\mu$, the radius converges to 0 almost surely. This result extends classical i.i.d. consistency to dependent triangular arrays without requiring density or smoothness assumptions, demonstrating that weak dependence does not alter the limiting geometric behavior.

2. Non-Asymptotic Moment Bounds under Geometric Mixing

Under the stronger assumption of geometric $\alpha$-mixing and local mass conditions (Assumptions 2 and 3), the paper derives sharp non-asymptotic bounds.

• Tail Bounds: The authors prove a tail bound showing that $R_{n,k}(x)$ concentrates around the canonical scale $(k/n)^{1/s}$. The concentration exponent includes an additional $\log n$ factor, which is the "price" paid for decoupling dependent observations into independent blocks (a standard technique in mixing sequence analysis).
• Moment Upper Bound: For the regime $k \gtrsim \log n$, the paper establishes the sharp moment upper bound:
  $$\mathbb{E}[R_{n,k}(x)^p] \lesssim \left(\frac{k}{n}\right)^{p/s}$$
• Moment Lower Bound: Under a matching local upper-mass condition, a matching lower bound is derived:
  $$\mathbb{E}[R_{n,k}(x)^p] \gtrsim \left(\frac{k}{n}\right)^{p/s}$$
• Exact Order Characterization: Combining these, the paper proves that under geometric mixing, the exact order of the moments is:
  $$\mathbb{E}[R_{n,k}(x)^p] \asymp \left(\frac{k}{n}\right)^{p/s}$$

3. Interpretation of the Local Exponent

A critical feature of the theory is its reliance on the local exponent $s$ rather than the ambient dimension $d$. This aligns with modern high-dimensional learning scenarios where data often lie near lower-dimensional manifolds. The results confirm that the scaling of the NN radius is determined by the intrinsic dimension of the distribution near the query point, not the ambient space, even in the presence of dependence.

Experimental Validation

The paper supports its theoretical findings with synthetic and real-world experiments:

1. Moment Convergence Rate: Experiments on linear Gaussian state-space models, Hidden Markov Models (HMM), and stationary Gaussian processes (RBF kernel) confirm that the estimated slope of the log-moment vs. log($k/n$) relationship aligns with the theoretical $p/s$ rate. Weak dependence stays close to the i.i.d. baseline, while medium/strong dependence introduces deviations consistent with the theoretical concentration penalty.
2. Entropy Estimation: Using Kozachenko–Leonenko entropy estimators, the study shows that when data has an intrinsic dimension $s$ but is observed in a higher dimension $d$, the estimator converges to the entropy of the intrinsic process. This holds even under temporal dependence, provided the local geometry is preserved (e.g., via PCA).
3. Real-World Benchmarks: The authors evaluate Raw-kNN and PCA-kNN on time-series forecasting and classification tasks from the Time Series Pile (including Informer, Monash, and UCR datasets). The results indicate that nearest-neighbor methods remain informative on real dependent data. PCA-kNN performs comparably to Raw-kNN, suggesting that dimension reduction can preserve the local structure necessary for neighborhood-based prediction even under dependence.

Significance and Claims

The paper claims a simple but significant message: Under weak dependence, nearest-neighbor geometry remains essentially the same as in the independent case at the level of its canonical scale.

• Theoretical Impact: The work provides a geometric control principle for learning methods under dependent sampling. It isolates the effect of dependence, showing that while dependence alters concentration constants and introduces a logarithmic penalty, it does not change the fundamental exponent $(k/n)^{1/s}$.
• Practical Implication: This finding justifies the transfer of geometric intuition and local-method design principles (e.g., bandwidth selection, neighborhood size tuning) from the i.i.d. regime to substantially broader dependent settings. It suggests that many heuristics developed for i.i.d. data remain applicable to time-series and other dependent data, provided the dependence is not too strong to invalidate the mixing assumptions.

The authors emphasize that their results are modest in scope regarding uniform convergence (focusing on pointwise analysis) but robust in their geometric interpretation, offering a foundational building block for future analyses of nonparametric and graph learning algorithms under dependence.