技术摘要：依赖采样下的最近邻半径

问题陈述

最近邻（NN）方法是经典与现代机器学习的基石，支撑着从$k$-NN 分类与回归到流形学习和信息检索等各类任务。这些方法的性能高度依赖于其所构建局部邻域的几何特性。具体而言，查询点$x$到其第$k$个最近邻的距离，记为半径$R_{n,k}(x)$，决定了局部邻域的尺度并主导偏差 - 方差权衡。

虽然$R_{n,k}(x)$在独立同分布（i.i.d.）采样下的行为已为人熟知——其规范尺度为$(k/n)^{1/s}$，其中$s$为局部内蕴维数——但许多现实世界的学习问题涉及依赖数据（例如时间序列、强化学习轨迹、时空传感）。在此类设定中，即使边缘分布稳定，观测值之间往往仍存在强依赖。本文探讨的核心问题是：依赖如何影响最近邻邻域的几何结构？ 具体而言，依赖是否会根本性地改变最近邻半径的缩放规律，还是规范几何尺度依然保持稳健？

方法论与设定

作者分析了一组定义在共同概率空间上的$\mathbb{R}^d$值随机变量的三角阵列$[X_{n,i} : 1 \le i \le n, n \ge 1]$。

• 边缘分布：所有观测值共享共同的边缘律$\mu$。
• 依赖结构：本文假设阵列的每一行均遵循**强混合（$\alpha$-混合）**依赖。混合系数$\alpha_m$量化了序列中相隔$m$个索引的片段之间依赖的衰减程度。
• 研究对象：半径$R_{n,k}(x) = \|X_{n}^{(k)}(x) - x\|$，其中$X_{n}^{(k)}(x)$是$n$个观测值中固定查询点$x$的第$k$个最近邻。

分析区分了两种混合机制：

1. 多项式混合：$\alpha_m \lesssim m^{-\gamma}$，其中$\gamma > 1$。
2. 几何（指数）混合：$\alpha_m \le e^{-\gamma m}$，其中$\gamma > 0$。

理论结果利用局部指数$s > 0$而非环境维数$d$进行表述。该指数刻画了$x$附近的局部质量累积情况（即$\mu(B(x,r)) \asymp r^s$），使得理论适用于集中在低维流形附近的数据。

主要贡献与结果

1. 分布无关的几乎处处收敛

在多项式$\alpha$-混合条件下，作者建立了一个分布无关的几乎处处收敛定理。

• 结果：若$k/n \to 0$，则$R_{n,k}(x) \xrightarrow{a.s.} r_x$，其中$r_x$是$x$到$\mu$支撑集的距离。
• 推论：若$x$位于$\mu$的支撑集内，则半径几乎处处收敛于 0。该结果将经典的 i.i.d.一致性推广至依赖三角阵列，无需密度或平滑性假设，证明了弱依赖不会改变极限几何行为。

2. 几何混合下的非渐近矩界

在更强的几何$\alpha$-混合假设及局部质量条件（假设 2 和 3）下，本文推导出了精确的非渐近界。

• 尾部界：作者证明了一个尾部界，表明$R_{n,k}(x)$集中在规范尺度$(k/n)^{1/s}$附近。集中指数包含一个额外的$\log n$因子，这是将依赖观测解耦为独立块（混合序列分析中的标准技术）所付出的“代价”。
• 矩上界：对于$k \gtrsim \log n$的机制，本文建立了精确的矩上界：
  $$\mathbb{E}[R_{n,k}(x)^p] \lesssim \left(\frac{k}{n}\right)^{p/s}$$
• 矩下界：在匹配的上局部质量条件下，推导出了匹配的下界：
  $$\mathbb{E}[R_{n,k}(x)^p] \gtrsim \left(\frac{k}{n}\right)^{p/s}$$
• 精确阶刻画：结合上述结果，本文证明在几何混合下，矩的精确阶为：
  $$\mathbb{E}[R_{n,k}(x)^p] \asymp \left(\frac{k}{n}\right)^{p/s}$$

3. 局部指数的解释

该理论的一个关键特征是其依赖于局部指数$s$而非环境维数$d$。这与现代高维学习场景相吻合，在这些场景中，数据通常位于低维流形附近。结果证实，即使在依赖存在的情况下，NN 半径的缩放规律由查询点附近分布的内蕴维数决定，而非环境空间。

实验验证

本文通过合成实验和真实世界实验支持其理论发现：

1. 矩收敛率：在线性高斯状态空间模型、隐马尔可夫模型（HMM）和平稳高斯过程（RBF 核）上的实验证实，对数矩与对数$(k/n)$关系的估计斜率与理论$p/s$速率一致。弱依赖保持在接近 i.i.d.基线的水平，而中等/强依赖引入了与理论集中惩罚一致的偏差。
2. 熵估计：利用 Kozachenko–Leonenko 熵估计器，研究表明，当数据具有内蕴维数$s$但在更高维$d$中被观测时，估计器收敛于内蕴过程的熵。即使存在时间依赖，只要局部几何结构得以保持（例如通过 PCA），这一结论依然成立。
3. 真实世界基准：作者在时间序列预测和分类任务（来自 Time Series Pile，包括 Informer、Monash 和 UCR 数据集）上评估了 Raw-kNN 和 PCA-kNN。结果表明，最近邻方法在真实的依赖数据上依然具有信息量。PCA-kNN 的表现与 Raw-kNN 相当，表明降维可以在依赖存在的情况下保留基于邻域的预测所需的局部结构。

意义与主张

本文传达了一个简单但重要的信息：在弱依赖下，最近邻几何在规范尺度层面上本质上与独立情况相同。

• 理论影响：该工作为依赖采样下的学习方法提供了几何控制原则。它隔离了依赖的影响，表明虽然依赖会改变集中常数并引入对数惩罚，但并未改变基本指数$(k/n)^{1/s}$。
• 实际意义：这一发现证明了将几何直觉和局部方法设计原则（例如带宽选择、邻域大小调整）从 i.i.d.机制推广到更广泛的依赖设定是合理的。它表明，许多为 i.i.d.数据开发的启发式方法仍然适用于时间序列和其他依赖数据，前提是依赖强度不足以使混合假设失效。

作者强调，其结果在一致收敛方面范围有限（侧重于点态分析），但在几何解释上具有稳健性，为未来依赖条件下非参数和图学习算法的分析提供了基础构建模块。