Nearest-Neighbor Radii under Dependent Sampling¶

会议: NeurIPS 2026
arXiv: 2605.14343
论文: https://arxiv.org/abs/2605.14343
领域: 优化/理论
关键词: 最近邻方法, 相关采样, 强混合三角阵列, 本征维度, 非渐近矩界

一句话总结¶

首次系统建立了强混合相关采样下最近邻半径的几何理论，证明在多项式混合下半径以概率 1 收敛至支集距离，并在几何混合下推导出紧致非渐近矩界 $\mathbb{E}[R_{n,k}(x)^p] \asymp (k/n)^{p/s}$，揭示弱相关性仅改变局部集中常数而不改变由本征维度 $s$ 决定的规范尺度。

研究背景与动机¶

最近邻（Nearest-Neighbor, NN）方法是经典与现代机器学习的基石，不仅构成了分类、回归、非参数密度估计和局部平滑的基石，而且在基于图的半监督学习、流形学习、信息检索和最近邻语言建模中广泛充当自适应局域测度。在上述所有方法中，决定算法核心统计特性的关键几何量是查询点 $x$ 到样本中第 $k$ 个最近邻点的随机半径 $R_{n,k}(x) = \|\mathcal{X}_{(k)}^n(x) - x\|$。该半径直观上充当自适应带宽，从根本上决定了局部估计器的偏差-方差权衡：若半径过大，局部平均将卷入几何距离较远的样本而引入不可承受的偏差；若半径过小，邻域内有效观测数量不足导致估计方差发散。在独立同分布（i.i.d.）假设下，该几何半径的缩放规律已完全明确，在局部质量条件下收敛阶由 $(k/n)^{1/s}$ 刻画，其中 $s$ 为局部几何维度。

然而，现代机器学习所处理的实际数据很少孤立生成，普遍源于时序预测、强化学习轨迹、序列推荐、事件流以及时空传感等强依赖物理或动力学过程。在这些现实场景中，尽管边缘分布保持平稳，样本之间却存在显著的时间或空间自相关。传统依赖经验过程与独立二项集中的分析工具彻底失效，因为球内局部样本计数过程不再服从独立伯努利和的分布规律。这引出了一个长期悬而未决的基本统计问题：样本之间的相依性是否会从根本上扭曲最近邻邻域的几何尺度？如果相关性改变了半径对样本量 $n$ 和邻居数 $k$ 的缩放指数，大量构建在局部欧氏邻域假设上的机器学习方法在时序与序列数据上的理论正当性将受到动摇；反之，若弱相关仅改变常数而保留规范尺度，则为将经典局部算法无缝推广至非独立场景提供了关键理论背书。

针对这一理论空白，本文跳出传统仅分析下游估计器误差的间接路径，将最近邻半径本身作为第一性几何对象进行严谨刻画。作者在三角阵列框架下引入强混合（$\alpha$-mixing）相依结构，并解耦环境维度 $d$ 与局部本征维度 $s$。核心 idea：通过事件等价性将最近邻半径尾概率转化为相依局部计数过程的下界估计，结合 Berbee/Liebscher 型交替分块解耦技术与 Bernstein 矩母函数控制，证明几何强混合仅引入对数级集中惩罚，严格保持最近邻半径以局部本征维度为指数的规范缩放阶 $(k/n)^{1/s}$。

方法详解¶

整体框架¶

本文构建的理论体系以固定查询点 $x \in \mathbb{R}^d$ 和行强混合三角阵列 $[X_{n,i}: 1 \le i \le n, n \ge 1]$ 为基础。首先利用几何对偶性将随机半径与空间计数过程精确绑定，进而针对渐近与非渐近场景分流处理：在多项式混合弱依赖下建立分布无关的几乎必然收敛性；在几何混合指数衰减依赖下，通过分块技巧将相依序列映射至弱相关分块和，从而建立非渐近尾部指数界并积分推导出紧致非渐近矩界。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["相依观测输入与查询点设定<br/>强混合三角阵列 X_n,i 与查询点 x"] --> B["1. 几何对偶与计数过程转化<br/>R_n,k(x) > r 等价于 N_n(x,r) < k"]
    B --> C["2. 渐近收敛分析<br/>多项式衰减下几乎必然收敛至支集距离 r_x"]
    B --> D["3. 交替分块解耦机制<br/>按 b_n 长度划分保留块与丢弃间隔"]
    D --> E["4. 本征维度局部质量界定<br/>边缘测度质量受控于 c_-(r)^s 与 c_+(r)^s"]
    E --> F["5. 非渐近尾部集中与紧致矩界<br/>导出双向匹配阶 E[R_n,k^p] ≍ (k/n)^(p/s)"]

关键设计¶

1. 几何对偶与计数过程转化：将连续极值统计量转化为离散受控计数和

分析最近邻半径的核心障碍在于其作为第 $k$ 阶顺序统计量具有高度复杂的非线性分布形态。论文立足于如下基本几何对偶等价性： $$R_{n,k}(x) > r \iff N_n(x, r) < k, \quad \text{其中 } N_n(x, r) := \sum_{i=1}^n \mathbf{1}\{\|X_{n,i} - x\| \le r\}$$ 该等价关系将控制半径上界的几何问题完全等价转化为局部计数过程 $N_n(x, r)$ 的下界下偏差概率控制。在独立情形下 $N_n(x, r)$ 服从二项分布，而在相依场景下指示变量 $\mathbf{1}\{\|X_{n,i} - x\| \le r\}$ 继承了原始序列的 $\alpha$-混合性质。由于中心化变量 $Z_{n,i} = \mathbf{1}\{\|X_{n,i} - x\| \le r\} - \mu(B(x, r))$ 几乎必然有界（$|Z_{n,i}| \le 1$），可直接利用 Davydov 协方差不等式对任意相隔指标进行协方差求和，从而将相依随机变量求和的方差增长严格约束在与独立情形同阶的线性增长尺度内。

2. 渐近收敛分析：多项式混合下的分布无关几乎必然一致收敛

针对渐近一致性，论文完全抛弃了密度存在性、光滑性或局部测度正下界的强加假设，仅要求三角阵列满足多项式强混合条件 $\alpha_m \lesssim m^{-\gamma}$（$\gamma > 1$）。对于任意固定的外半径偏差 $\varepsilon > 0$，定义边缘测度质量 $p_x = \mu(B(x, r_x + \varepsilon)) > 0$（其中 $r_x = \inf_{y \in \text{supp}(\mu)} \|y - x\|$ 为 $x$ 到测度支集的欧氏距离）。当 $k/n \to 0$ 时，当 $n$ 充分大必有期望计数主导阈值 $k - np_x \le -np_x/2$。利用 Liebscher 强混合集中不等式并精细选取分块尺度 $m_n = \lfloor \frac{3np_x}{64 \log n} \rfloor$，指数衰减项达到 $\mathcal{O}(n^{-2})$，而混合余项受控于 $n m_n^{-(2+\gamma)} \lesssim (\log n)^{2+\gamma} / n^{1+\gamma}$。由于 $\gamma > 1$，两项均关于样本量 $n$ 可和，进而经由 Borel-Cantelli 引理建立几乎必然收敛： $$\lim_{n \to \infty} \|\mathcal{X}_{(k)}^n(x) - x\| = r_x \quad \text{a.s.}$$ 该结论表明即使在极弱的多项式相依扰动下，最近邻采样的几何收敛目标仍然完全忠实于测度支集本身，杜绝了任何相关性引起的极限偏移。

3. 交替分块解耦机制：几何混合下的独立化阻断与尾部集中

在非渐近场景下，为了导出精确的有限样本浓度界，论文假设 $\alpha$-混合系数呈指数衰减 $\alpha_m \le e^{-\gamma m}$。为了阻断长程时序累积相关，论文采用交替分块构造：将整个序列划分为 $M_n = \lfloor \frac{n}{2b_n} \rfloor$ 个保留块 $I_u = \{(2u-2)b_n + 1, \dots, (2u-1)b_n\}$ 与相邻的等长丢弃间隔，分块长度设为 $b_n = \lceil \frac{8}{\gamma} \log n \rceil$。由于每个保留块之间被长度为 $b_n$ 的丢弃块物理隔离，保留块统计量 $W_u(r) = \sum_{i \in I_u} \mathbf{1}\{\|X_{n,i} - x\| \le r\}$ 所构成的衍生块序列 $[Z_u = W_u - \mathbb{E}W_u]$ 成为一阶超快混合阵列，其一阶混合系数满足 $\bar{\alpha}_1 \le \alpha_{b_n} \le n^{-8}$。通过将全序列局部计数放缩为保留块和 $S_n^{\text{keep}}(r) \le N_n(x, r)$，并对块序列应用 Bernstein 集中不等式，成功消除了变量间的直接依赖耦合，将相依序列的集中分析有效化归至弱相关块变量的独立主干。

4. 本征维度局部质量界定：摆脱环境维数限制的局部几何刻画

现代高维机器学习数据多集中于低维潜空间或流形结构。为此，论文放弃对环境欧氏维度 $d$ 的全局依赖，转而在查询点 $x$ 邻域引入局部本征维度 $s > 0$ 的双向几何质量假定： $$c_- r^s \le \mu(B(x, r)) \le c_+ r^s, \quad \forall 0 < r \le r_0$$ 设定特征半径尺度 $r_*(n, k) = (8k / (c_- n))^{1/s}$，对任意二进离散半径步阶 $r_j = 2^j r_*(n, k) \le r_0$，保留块总期望质量严格放大至 $\mu_j \ge 2^{js+1}k$。这一放缩直接确保了在相依条件下偏离中心值的概率界呈现双指数级快速衰减： $$\mathbb{P}\left(R_{n,k}(x) > 2^j r_*(n,k)\right) \le 4 \exp\left(-c_0 2^{js} \frac{k}{\log n}\right) + C n^{-7}$$ 该界清楚地展示了双重核心机制的解耦：几何本征维度 $s$ 唯一控制半径对样本量的指数幂次 $1/s$，而相依混合率 $\gamma$ 仅通过分块长度 $b_n \asymp \log n$ 引入温和的对数惩罚因子 $k / \log n$。

5. 非渐近尾部集中与紧致矩界：两端夹逼确立精确阶

为了得到任意阶矩 $\mathbb{E}[R_{n,k}(x)^p]$（$p > 0$）的非渐近精确阶，论文构造了上下界的严密闭环。上界方面，假设支集直径有界（$D < \infty$），利用阶梯划分将积分分解为内半径、二进分环与外边界，结合 $k \ge K_0 \log n$ 保证项 $k/\log n$ 远离原点，可级数求和化简得 $\mathbb{E}[R_{n,k}(x)^p] \le C_{p,s} (k/n)^{p/s}$。下界方面，完全无需任何混合依赖假定，直接在球半径 $r^- = (k / (2c_+ n))^{1/s}$ 下计算期望计数 $\mathbb{E}[N_n(x, r^-)] \le k/2$，由 Markov 不等式立得 $\mathbb{P}(N_n(x, r^-) \ge k) \le 1/2$，从而 $\mathbb{P}(R_{n,k}(x) > r^-) \ge 1/2$。这直接给出了无需相依限制的严格下界 $\mathbb{E}[R_{n,k}(x)^p] \ge \frac{1}{2} (k / (2c_+ n))^{p/s}$。两者结合确立了完全匹配的精确阶： $$c_{p,s} \left(\frac{k}{n}\right)^{p/s} \le \mathbb{E}\left[R_{n,k}(x)^p\right] \le C_{p,s} \left(\frac{k}{n}\right)^{p/s}$$

实验关键数据¶

主实验¶

为了实证检验理论建立的矩收敛阶对各类非独立序列的普适性，作者构建了三种不同物理机制的相依数据生成模型（线性高斯状态空间模型 LSS、两状态隐马尔可夫模型 HMM、基于 FFT 与 RBF 核的平稳高斯过程序列 GP），在环境维度 $d \in \{1, 3, 5\}$、矩阶数 $p/d \in \{1, 2, 3, 4, 5\}$ 下，通过双对数线性回归 $\log \hat{M} = a + b \log(k/n)$ 拟合经验斜率 $b$，并与 i.i.d. 基准及理论真值 $p/d$ 进行系统对照。同时，在真实世界时间序列基准 Time Series Pile（涵盖 Informer、Monash、UCR 数据集）上对原始空间最近邻（Raw-kNN）、低维投影最近邻（PCA-kNN）与大型预训练时序基础模型 MOMENT 进行跨任务综合评估。

评估任务	性能度量指标	Raw-kNN (本文基线)	PCA-kNN (本文降维)	MOMENT (基础模型)	理论与经验结论映射
长程时序预测 (Long-horizon)	全局平均 MSE	0.628	0.627	0.617	降维未损耗局部几何，与大模型差距微弱 (<1.8%)
时序模式分类 (Classification)	91 数据集平均准确率	0.748	0.748	0.794	强相依下 NN 仍具高度判别力，PCA 保持无损几何
短程预测组内 (Within-group)	平均 sMAPE	16.199	16.488	—	弱相依场景下自适应匹配局部真实近邻质量
短程预测迁移 (Transfer)	平均 sMAPE	27.210	27.369	14.525	跨分布迁移出现退化，凸显边缘稳态假设必要性

消融实验¶

消融重点考察“相依强度（弱/中/强）”对矩收敛斜率的影响，以及“潜变量低维结构 + PCA 降维”下 Kozachenko-Leonenko 熵估计对本征维度 $s$（而非环境维度 $d=20$）的几何自适应收敛特性（模拟 1000 次 Monte Carlo，潜空间 AR(1) 参数 $\rho \in \{0, 0.3, 0.6\}$）：

实验配置	数据生成参数设定	拟合斜率 / 熵估计行为	相对理论真值偏差与物理行为
矩收敛斜率：弱依赖	LSS ($\rho=0.02$) / HMM ($p=0.7$) / GP ($\ell=1$)	斜率 $b \approx p/d$	与 i.i.d. 曲线紧密重合，证实弱相依几何无畸变
矩收敛斜率：中依赖	LSS ($\rho=0.60$) / HMM ($p=0.99$) / GP ($\ell=50$)	斜率 $b$ 产生轻度偏移	有限样本下对数惩罚常数放大，渐近趋势仍收敛
矩收敛斜率：强依赖	LSS ($\rho=0.98$) / HMM ($p=0.9995$) / GP ($\ell=200$)	斜率 $b$ 发生显著偏离	极强长记忆破坏了有限样本有效样本量 $n_{\text{eff}}$
熵估计：$s=1, d=20$	真实熵 $H_1 = 1.4189$, Oracle / PCA 估计	$n \to \infty$ 均单调收敛至 1.419	验证半径缩放由 $s=1$ 决定，避开 $d=20$ 维数灾难
熵估计：$s=3, d=20$	真实熵 $H_3 = 4.2568$, Oracle / PCA 估计	$n \to \infty$ 均平稳逼近 4.257	PCA 成功提纯本征信号，相依仅轻微拉大前期残差
熵估计：$s=5, d=20$	真实熵 $H_5 = 7.0946$, Oracle / PCA 估计	$n \to \infty$ 均渐近收敛至 7.095	表明低维嵌入操作严格保留了弱混合相依局部结构

关键发现¶

相关性与局部几何维度的正交解构得到实验印证：无论是在合成的三类动态相依系统还是真实物理时序中，弱相关序列与独立样本的半径矩斜率完全贴合理论值 $p/d$。相依强度的增加改变的是有限样本下的集中常数与波动方差，而完全没有改变由本征维度决定的幂次律基底。
降维映射对相依本征几何具有高保真性：在 $d=20, s \in \{1, 3, 5\}$ 的熵估计实验中，仅使用前 $s$ 个 PCA 主成分计算的熵估计曲线与直接在真实潜空间计算的 Oracle 曲线高度一致，且两者均随 $n$ 增长渐近收敛到真实熵理论值，实证验证了定理中 $s$ 作为局部本征维度的理论预测。
经典非参数最近邻在相依数据预测中表现稳健：在真实长程预测基准上，未经复杂深度训练的纯几何最近邻方法达到了与前沿时序大模型 MOMENT 高度匹敌的精度（0.627 vs 0.617），证实了相依样本下局部邻域依旧能够捕捉充足的局部几何流形与演化规律。

亮点与洞察¶

将最近邻半径本身作为核心对象：区别于过去文献普遍将最近邻视为下游估计器或分类器的中间黑盒、仅从经验过程层面分析泛化误差的传统做法，本文直接剖析随机半径 $R_{n,k}(x)$ 本身的几何浓度与阶数，为非参数回归、自适应带宽核估计与图神经网络构建提供了通用的一层几何理论基础设施。
本征维度与相关性的解耦洞见：敏锐地将现代表示学习中的流形假设（高维环境、低维局部几何）与时序依赖性相结合，用局域体积增长指数 $s$ 替代传统的环境维度 $d$。这使得理论对于处理神经网络隐层嵌入、多模态时序表征等具有显著低维局部流形结构的数据具有直接的指导意义。
对数依赖惩罚的本质厘清：严格阐明了条件 $k \gtrsim \log n$ 是利用 Bernstein 块解耦技术消化强混合指数衰减的必要代价，它反映的是相依样本转化为有效独立自由度时的信息衰减，而非空间几何结构本身的物理坍塌。

局限与展望¶

逐点局部保证向全支集一致收敛的拓展：当前理论均针对固定测试查询点 $x$ 展开逐点（pointwise）分析，若要为全局 $k$-NN 图连通性、谱聚类一致性或全局一致回归建立泛函极限定理，需在支撑集上对球族经验计数过程建立一致集中不等式，依赖更精细的相依经验过程熵积分工具。
长记忆过程与重尾扰动尚未覆盖：理论体系建立在多项式与指数衰减的 $\alpha$-混合假设之上，对于具有长记忆性（分形布朗运动、自回归分数整合移动平均 ARFIMA）或重尾非平稳相依系统，局部计数过程的方差增长将突破线性边界，需发展新的极值渐近工具。
邻域加权与度量学习自适应性：当前分析基于固定欧氏度量与标准 $k$-NN 计数，未考虑自适应马氏度量或注意力导向的动态权重邻域，未来可探索相依度量自适应半径的收敛界。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次从纯几何角度彻底攻克强混合相依抽样下最近邻半径的非渐近尾部与匹配矩界，理论视角极具原创性。
实验充分度: ⭐⭐⭐⭐⭐ 涵盖三类典型相依物理模型的数值模拟、低维流形熵估计验证以及覆盖近百个真实数据集的时间序列基准对比。
写作质量: ⭐⭐⭐⭐⭐ 数学论证层层递进，从几何对偶、几乎必然极限定理到分块 Bernstein 尾部估计一气呵成，结构极为清晰严整。
价值: ⭐⭐⭐⭐⭐ 为时序预测、强化学习离线评估与流形学习在非独立数据中的实际应用奠定了不可或缺的统计几何理论基石。

实验配置	数据生成参数设定	拟合斜率 / 熵估计行为	相对理论真值偏差与物理行为
矩收敛斜率：弱依赖	LSS (\(\rho=0.02\)) / HMM (\(p=0.7\)) / GP (\(\ell=1\))	斜率 \(b \approx p/d\)	与 i.i.d. 曲线紧密重合，证实弱相依几何无畸变
矩收敛斜率：中依赖	LSS (\(\rho=0.60\)) / HMM (\(p=0.99\)) / GP (\(\ell=50\))	斜率 \(b\) 产生轻度偏移	有限样本下对数惩罚常数放大，渐近趋势仍收敛
矩收敛斜率：强依赖	LSS (\(\rho=0.98\)) / HMM (\(p=0.9995\)) / GP (\(\ell=200\))	斜率 \(b\) 发生显著偏离	极强长记忆破坏了有限样本有效样本量 \(n_{\text{eff}}\)
熵估计：\(s=1, d=20\)	真实熵 \(H_1 = 1.4189\), Oracle / PCA 估计	\(n \to \infty\) 均单调收敛至 1.419	验证半径缩放由 \(s=1\) 决定，避开 \(d=20\) 维数灾难
熵估计：\(s=3, d=20\)	真实熵 \(H_3 = 4.2568\), Oracle / PCA 估计	\(n \to \infty\) 均平稳逼近 4.257	PCA 成功提纯本征信号，相依仅轻微拉大前期残差
熵估计：\(s=5, d=20\)	真实熵 \(H_5 = 7.0946\), Oracle / PCA 估计	\(n \to \infty\) 均渐近收敛至 7.095	表明低维嵌入操作严格保留了弱混合相依局部结构