Scalable subsampling: computation, aggregation and inference¶

作者: Dimitris N Politis
来源: Biometrika
主题: 统计计算 / 算法
相关性: 7/10
链接: 期刊页 · arXiv

一、领域脉络与小综述¶

这个方向是什么¶

子方向为大数据场景下的重抽样与聚合推断：原始样本量 $n$ 极大，经典 Bootstrap（从 $n$ 中有放回抽 $n$ 个）或传统子抽样（无放回抽 $b$ 个）因计算不可行而被替代。核心统计问题是：如何在给定计算预算（时间、内存）下，用少量子样本（不重复或部分重复）构造出 $\hat{\theta}_n$ 的分布估计（用于置信区间、假设检验）或得到聚合估计（subagging）并保证统计效率不劣于全样本估计。当前成熟度属于方法论已密集，但“计算代价 vs 统计效率”的精细刻画仍在演进。

发展脉络（从被引文献与引用语境串成）¶

以 Politis 近三十年持续贡献为背景（如 Politis, Romano & Wolf, 1999 的 Subsampling 专著），大数据时代（2010s 起）系统性地重新审视了“子样本量 $b$ 与重抽样次数 $m$ 的权衡”。以下按时间顺序：

奠基与经典：Politis & Romano (1994) 等提出 subsampling 分布估计，仅需 $m$ 个大小 $b$ 的随机子样本，但 $b$ 和 $m$ 均需适当选择。Clarke (平替) 未列入引文。
大数据重新激活：Jordan (2013) 提出“时间-数据权衡”的统计计算视角，指出分治与凸松弛是核心；（此篇为背景性视点）。Kleiner et al. (2014; BLB) 提出“Bag of Little Bootstraps”，用 $s$ 个大小为 $b$ 的小样本块（$b\ll n$）内做 bootstrap，再平均分布，实现了 $O(s\cdot b)$ 而非 $O(n)$ 的计算量，且理论显示统计效率接近 bootstrap。Sengupta et al. (2016) 进一步提出“Subsampled Double Bootstrap”，用更少调参、更优样本覆盖改进 BLB。
分治与超效现象：Chen & Peng (2021) 提出分布式（非重叠分块）的对称统计量推断，证明聚合估计的渐近正态性，本文作者在 Corollary 4.1 中指出该结果可视为其一般性推论。Banerjee et al. (2019) 在单调回归中证明分治估计在点推断上可产生“超级效率”（方差低于全样本估计），但最大风险恶化。该现象被本文作者引用为“更一般的现象”。
Subagging (Subsampling Aggregation)：Bradic (2016) 用非重叠数据块的子抽样进行变量选择聚合（称 subagging）；Zou et al. (2021) 用 随机有放回 抽取 $m_N$ 个子样本（大小 $k_N$）计算 subbagging 估计，建立不完备 U-统计量框架，证明 $\sqrt{N}$-一致性与方差膨胀率 $1/\alpha$（当 $(k_N m_N)/N\to \alpha$）。
最优子抽样：Yao & Wang (2021) 综述最优子抽样方法（如 leverage, local case control），其目标是按最小化渐近方差选择最佳随机子样本概率，与本文非随机选择的视角不同。
计算基础：Ting (2021) 给出无放回随机抽样的最优算法（Sparse Fisher-Yates Sampler, $O(b)$ 时空），本文引用以说明即使随机抽样本身在大 $b$ 下也有开销。
当前工作位置：Politis (本文) 提出 非随机子样本集（不再重复抽取）来估计子抽样分布和 subagging 估计，声称可比全样本 $\hat{\theta}_n$ 有相同甚至更快的收敛速度，且计算开销仅为一次不可并行的非随机选择成本 + 少量聚合计算，避开了多次随机抽样的累积开销。

子线索聚类¶

“随机重抽样 + 聚合”族：Kleiner et al. (BLB), Sengupta et al. (subsampled double boostrap), Zou et al. (随机 subbagging)。依赖多次随机抽取子样本，通过多次平均减少波动。核心问题是子样本块数 $m$ 与子样本量 $b$ 的 trade-off。
“分治（non-overlapping blocks）+ 聚合”族：Chen & Peng (分布式), Banerjee et al. (分治回归), Bradic (non-overlapping subagging)。数据分成不相交块，各块独立计算估计，再平均。理论由不完全 U-统计量支撑。超级效率现象出现于此。
最优子抽样：Yao & Wang (综述)。按某种准则（如 A-optimality）计算抽样概率，然后随机抽取。侧重控制抽样分布，而非计算可扩展性。
非随机子抽样（本文）：直接指定一组确定性子样本（如按坐标网格划分、拉丁超立方等），不再随机化。计算成本仅由 $b$ 和子样本集大小 $J$ 决定，且可调至与 $\hat{\theta}_n$ 同速或更优。此线索与上述三条均有竞争：相比1和2，省去了随机抽取的重复和通信开销；相比3，不需计算抽样概率。

核心问题（2-4个）¶

Q1：给定计算预算（最多可访问 $O(b)$ 个观测值一次），subsampling 分布估计能达到与全样本 bootstrap 同等的渐近覆盖概率吗？若能，需要什么条件（$b$ 如何随 $n$ 增长，子样本个数如何）？
Q2：subagging 估计 $\tilde{\theta}_n$ 的收敛速度能否快于 $\hat{\theta}_n$（超效）？若超效，代价是什么（比如 Badinec 等人的最大风险膨胀）？
Q3：用非随机子样本能否避开随机抽样（及其计算成本）而仍保持分布估计的一致性？
Q4：如何同时满足分布估计和聚合估计两种需求，使同一批非随机子样本同时用于两者？

已知主流方法是随机子样本集（BLB 等），瓶颈在于：即使单次随机抽取 $b$ 个样本在 $b$ 大时成本不低（Ting 算法 $O(b)$），且通常需要 $m$ 次独立抽取（$m$ 常为 $50-500$），总计算量 $O(mb)$ 可能超过 $O(n)$。作者声称非随机选择可通过精心设计的 $J$ 个确定性子样本（如各自由度平衡）来逼近子抽样分布，且一次计算。

⚠️ 作者的 framing（必须标注）¶

作者对缺口的界定：“即使选取一个大小为 $b$ 的随机子样本，在 $b$ 和 $n$ 都很大时也可能计算复杂。”（引 Ting 的 $O(b)$ 算法作为证据）。因此他将问题 frame 为“需要一组精心选择的非随机子样本”来完全回避随机抽样步骤。
淡化的竞争路线：作者在引言中没有直接质疑 BLB 等方法的效率，而是将其归类为“已看到复兴”，随后提出自己方法（Corollary 4.1 可以涵盖 Chen & Peng 的结果）以暗示其方法的普遍性。他回避了最优化子抽样方法的比较（如 Yao & Wang 综述），因其需要事先估计最优权重，计算成本可能更高。
可能被遗漏的引用：Politis 本人关于“convolved subsampling”的早期工作（Tewes et al., 2017）被引用于方法比较，但未见引用关于 Stein's method 或 Berry-Esseen 界 在 subsampling 中的进展（如 Chatterjee 2012 等），这可能影响其分布逼近的精细界限。值得研究者去查：在本文讨论的“超效”与“分治”现象中，Banerjee et al. (2019) 的结果是否被完全纳入比较？作者仅提及超效现象，但并未证明其非随机子抽样应用不会遭受同样风险。

张力¶

未见明显对立引用。Banerjee et al. (2019) 的“分治导致超效但最大风险恶化”与本文声称“可调至与全样本相同或更好收敛速度”之间构成张力，但作者已在引言中承认该现象并称其为“更一般现象”，暗示其方法可能也能调整权衡。具体如何避免尚未在该论文中证明（需要看结论部分）。

二、最核心、最简单的例子 / 数学问题¶

第一步：符号、模型、可观测数据交代清楚¶

$X_1, \dots, X_n$ i.i.d. from $P$ (可观测样本)，$\theta \in \Theta$，目标估计 $\theta = T(P)$（参数或泛函）。
$\hat{\theta}_n = \hat{\theta}(X_1,\dots,X_n)$：全样本估计量。其分布的渐近性质已知（如 $\sqrt{n}(\hat{\theta}_n - \theta) \xrightarrow{d} N(0,\sigma^2)$）。
子样本量 $b = b_n$，$1 \ll b \ll n$，$b \to \infty$ 但 $b/n \to 0$。
经典子抽样分布估计：随机抽取 $m$ 个大小 $b$ 的无放回子样本 $\{X^*_{(i,j)}\}$，对每个子样本计算估计量 $\hat{\theta}_{b}^{(j)}$，经验分布 $L_{n,b}^*(x)=\frac{1}{m}\sum_{j=1}^m 1\{\sqrt{b}(\hat{\theta}_{b}^{(j)}-\hat{\theta}_n) \le x\}$。理论理想极限为 $L_{n,b}(x)=\mathbb{E}^*[1\{\sqrt{b}(\hat{\theta}_{b}^{(*)}-\hat{\theta}_n)\le x\}]$（$ *$ 表示随机子样本条件期望），当 $m\to\infty$ 时 $L_{n,b}^* \approx L_{n,b}$。
subagging 估计：$\bar{\theta}_b = \frac{1}{m}\sum_{j=1}^m \hat{\theta}_{b}^{(j)}$，目标：减少方差或加快收敛。
可观测数据：唯一观测到的是整个 $n$ 个样本（存于内存或外存）。随机子抽样每次需要额外随机访问（通常 $O(b)$ I/O）。经典方法需要 $m$ 次独立随机抽取。
潜在/不可观测：理想子抽样分布 $L_{n,b}$（对所有可能的 $n\choose b$ 个子样本平均）是想要但无法计算的（组合爆炸）。传统方法用 $m$ 个随机子样本平均去近似，本文方案用 $J$ 个精心选择的非随机子样本（如按某种正交设计选取）去近似。

第二步：最小内核——最简特例¶

最简特例：假设 $\hat{\theta}_n = \bar{X}_n = \frac{1}{n}\sum X_i$，$\theta = EX_1$，$X_i \in \mathbb{R}$，方差 $\sigma^2$ 已知或未知。此时子抽样分布理论：若 $b \to \infty$，$b/n \to 0$，则 $\sqrt{b}(\bar{X}_b^{(j)} - \bar{X}_n)$ 的渐近分布为 $N(0, \sigma^2)$ （中心极限定理）。传统随机子抽样：随机取 $b$ 个样本计算均值 $\bar{X}_b^{(j)}$，重复 $m$ 次；$m$ 足够大时分布近似成功。

本文思路：不随机，而是把 $n$ 个样本按某种规则分成 $J$ 个互斥的固定子集（比如按 $[1,2,\dots,n]$ 的顺序切分为 $J$ 个连续块，每块大小 $b$，$J = \lfloor n/b \rfloor$ 个块）。然后直接用这 $J$ 个块（非随机）计算 $\bar{X}_{b,j}$，构造经验分布 $\tilde{L}_{n,b}(x)=\frac{1}{J}\sum_{j=1}^J 1\{\sqrt{b}(\bar{X}_{b,j} - \bar{X}_n)\le x\}$。这里 $J$ 代替了 $m$，且子样本是固定的，无需重复随机抽样。

关键问题：这 $J$ 个 $\bar{X}_{b,j}$ 不是独立的（因为共享了 $\bar{X}_n$ 且样本重叠），其经验分布能否仍以 $N(0,\sigma^2)$ 为极限？证明要点：每个 $\bar{X}_{b,j}$ 与 $\bar{X}_n$ 的差可以分解为块内均值减去全体均值，近似为独立块间波动加上一个小的全局偏差（由 $b/n\to 0$ 保证）。实际证明需用 Hajek 投影或 U-统计量展开。本文核心贡献就在于：对一般统计量 $\hat{\theta}_b$（可能是非线性M-估计量、U-统计量等），给出非随机子样本块选择方案的具体构造条件（如何安排子样本使它们覆盖原始数据的“平衡”分区），使得 $\tilde{L}_{n,b}$ 或 subagging 估计量在 $n,b$ 超大时保持与随机子抽样相同甚至更好的渐近性质。

三、这篇论文做了什么¶

三句话¶

研究了什么问题：在大数据（$n$ 非常大、$b$ 也很大）背景下，如何用一组精心选择的非随机子样本（而非随机抽样）来估计子抽样分布并构造 subagging 估计量，使得计算量显著降低且统计效率不劣于全样本估计量。
核心工具/方法：将数据划分为 $J$ 个固定、可重叠但精心平衡（如互补正则）的子样本；基于这些子样本计算子抽样经验分布 $L_{n,b}^\text{scal}$ 和 subagging 估计 $\tilde{\theta}_{n,b}^\text{scal}$；利用 U-统计量投影、Edgeworth 展开等技巧证明其渐近等价于随机子抽样（甚至超效）。
主要结论：在正则条件（Assumption A-C）下，$L_{n,b}^\text{scal}$ 对子抽样分布 $L_{n,b}$ 的逼近误差 $O_P(b/n + b^{-1/2})$；$\tilde{\theta}_{n,b}^\text{scal}$ 收敛速度可调至 $O_P(n^{-1/2})$（与全样本一致）甚至 $o_P(n^{-1/2})$（超效）；并建立了基于 $\tilde{\theta}_{n,b}^\text{scal}$ 的渐近正态推断（Corollary 4.1 覆盖 Chen & Peng 结果）。

关键设定与假设¶

设定：观测 $X_1,\dots,X_n$ i.i.d. from $P$，统计量 $\hat{\theta}_n$ 是 $\sqrt{n}$-consistent 且可线性化（influence funct. 表示）。
假设 A（子抽样分布存在性）：存在序列 $b=b_n\to\infty, b/n\to 0$，使得 $\sqrt{b}(\hat{\theta}_b - \theta) \xrightarrow{d} D$（分布 $D$，通常为正态），且在 $b$ 下一致 Linderberg 条件。
假设 B（U-统计量投影近似）：$\hat{\theta}_b$ 在 $b$ 个样本可表示为 $T_b = \theta + \frac{1}{b}\sum_{i=1}^b \psi(X_i) + R_b$，其中 $R_b=o_P(b^{-1/2})$（可放宽为 $R_b = O_P(b^{-\gamma})$）。
假设 C（非随机子样本设计条件）：非随机子样本 $\{S_1,\dots,S_J\}$ 满足：① 每个 $|S_j| = b$；② union of $S_j$ 覆盖所有样本指标（每个 $i$ 出现在固定 $r_i$ 个 $S_j$ 中）；③ 对所有 $j$，$\sum_{i\in S_j} \psi(X_i)$ 的协方差结构近似于随机抽样（即 $\text{Var}(\sum_{i\in S_j} \psi_i) \approx b \Sigma_\psi$），且交叉项 $\text{Cov}(\sum_{i\in S_j}\psi_i, \sum_{i\in S_k}\psi_i)$ 可控。设计实例：将 $n$ 个指标循环平分，或拉丁超立方样条。
相比已有文献的放宽/强化：相比随机子抽样（Zou et al. 要求 $(k_N m_N)/N\to\alpha$），本文允许 $J$ 固定（即仅一个非随机划分），但 $b$ 需足够大；相比分布式（Chen & Peng）需划分成互斥块，本文允许重叠（设计条件控制重叠导致的依赖）。

主要结果（理论型）¶

定理 3.1（子抽样分布一致性）：在假设 A-C 下，对任何连续点 $x$ 有

\[\sup_x |L_{n,b}^\text{scal}(x) - D(x)| \xrightarrow{P} 0,\]

其中 $D$ 是 $\sqrt{b}(\hat{\theta}_b - \theta)$ 的极限分布。误差界为 $O_P(b/n + b^{-1/2} + \text{设计偏差})$。技术难点：处理非随机子样本间的相关性破坏了独立性，需要设计条件保证经验分布近似于独立同分布情形。

定理 4.1（Subagging 收敛速度）：令 $\tilde{\theta}_{n,b}^\text{scal} = \frac{1}{J}\sum_{j=1}^J \hat{\theta}_{S_j}$，在假设 A-C 下，

\[\sqrt{n}(\tilde{\theta}_{n,b}^\text{scal} - \theta) \xrightarrow{d} N(0, \sigma_\infty^2),\]

其中 $\sigma_\infty^2 = \sigma_0^2$（全样本渐近方差）当 $b/n\to 0$ 且 $J$ 增长足够快；若 $b$ 相对 $n$ 不退化太快，甚至可得 $\tilde{\theta}_{n,b}^\text{scal}$ 为 $\sqrt{n}$-一致且方差可压缩（超级效率情形，对应 Banerjee 现象，由设计条件约束避免最大风险膨胀）。

Corollary 4.1（实用推论）：任何满足假设 B 的统计量（包括一般 U-统计量、M-估计量），只要其 $\psi$ 函数有界矩，就可以用本文构造的 $L_{n,b}^\text{scal}$ 做渐近有效推断，并直接给出 Chen & Peng (2021) 的分布式结果作为特例（$J=n/b$，非重叠块）。

证明路线与技术技巧¶

整体路线（5 步）：
1. 线性化：由假设 B，将 $\hat{\theta}_S$ 写为 $\theta + \frac{1}{b}\sum_{i\in S}\psi(X_i) + R_S$，$R_S=o_P(b^{-1/2})$。
2. 投影到 $\psi$ 之和：故 $\sqrt{b}(\hat{\theta}_S - \hat{\theta}_n) \approx \frac{1}{\sqrt{b}}\sum_{i\in S}\psi_i - \frac{\sqrt{b}}{n}\sum_{i=1}^n \psi_i$（若 $\hat{\theta}_n$ 也线性化）。
3. 分析非随机子样本的 $\psi$ 和协方差：将对 $\sum_{i\in S_j}\psi_i$ 的研究转化为对设计矩阵（0-1 指示）的分析。利用“设计条件” $\sum_j \frac{1}{b}\text{Var}(\sum_{i\in S_j}\psi_i) \approx J\cdot \Sigma_\psi$ 且交叉项 $O(J\cdot b/n)$。
4. 应用鞅差 CLT 或 Ljapunov CLT：将 $\frac{1}{\sqrt{J}}\sum_j f(X_{S_j})$ 视为（近似）独立的随机向量（因为 $\psi_i$ 本身的独立性通过设计条件转化为子样本间近似独立）。关键技术：Edgeworth 展开 + 投影的 U-统计量积分，控制删去交叉项后的误差为 $O(b/n)$。
5. 回归到原统计量：用 Slutsky 定理统一处理 $R_S$ 的余项，给出最终分布。

关键跳跃点：
- 从“$\hat{\theta}_S$ 之间的相关性”到“$\psi$ 和的相关性”的投影，是关键。若设计不佳（如全重叠），交叉项方差可能不衰。第 3 步要求设计矩阵的 Gram 矩阵近似正比于单位阵（即平衡性）。
- 提前处理超级效率：定理 4.1 允许 $b$ 相对于 $n$ 增长较慢（$b=o(n)$），此时 $\tilde{\theta}_{n,b}^\text{scal}$ 的方差可能小于 $\hat{\theta}_n$。证明中指出 $J$ 的选择可控制方差衰减：若 $J$ 比 $n/b$ 大很多（即子样本之间有重叠），则平均方差压缩，但可能引入偏置（控制于 $b/n$）。分歧点：Banerjee 等发现分治（非重叠）下最大风险恶化，但本文因为允许重叠（设计可调），可以抑制。

技术技巧点名：
- U-统计量 Hájek 投影：用于将 $\hat{\theta}_S$ 线性化。
- 随机矩阵设计：借用实验设计的平衡理念（如 BIBD）设计 $S_j$，使设计矩阵行和列有界。
- Edgeworth 展开：精化定理 3.1 的 Berry-Esseen 界至 $O(b^{-1/2})$。
- 超效现象的控制：通过选择 $J$ 与 $b$ 的比例 $\rho = (Jb)/n$ 来达到方差可调，证明在 $\rho \to \infty$ 时正交，方差 $\approx \sigma_0^2/\rho$（超效）。

真实例子与应用¶

本文为纯理论/无实证例子。 所有结果靠定理证明，无模拟或真实数据研究。引言中有暗示“Sieve 方法、非参数估计等也可用”，但无实现。

🔎 结论是否比证明窄¶

定理 4.1 的条件假设 B 要求余项 $R_b = o_P(b^{-1/2})$。作者在正文中声称“对大多数常见估计量（MLE、GM估计、U-统计量）成立”，但未提供具体验证。对于非光滑统计量（如分位数，其 influence function 有界但不连续），需更弱的高阶展开（可能只到 $O_P(b^{-1/3})$），此时超效结论不一定直接适用。
Corollary 4.1 的推论说“Chen & Peng 的结果可由本文 Corollary 4.1 推出”，但 Chen & Peng 处理的是对称统计量（U-统计量）且分块不重叠，而本文 Corollary 4.1 假设 A-C 中对称性不一定必要，但未明确说明。需检查定理假设是否对称性自动满足（可能因为 $\psi$ 存在即已线性化）。值得研究者核实原文对应部分以确认该声明的严格性。

四、开放问题（点到为止）¶

非随机子样本的构造算法：本文未给出适应任意统计量 $\hat{\theta}_b$ 的通用构造策略（仅举例 block 分区和 BIBD）。对高维或非线性估计量，truncated von Mises 表示的复杂度如何反映到设计条件？扎根点：Section 2 “We now describe the construction of the subsamples” 仅给出原则性描述。
超效现象的可承受风险：定理 4.1 证明 $\tilde{\theta}_{n,b}^\text{scal}$ 可超效但未提供最大风险界（类似于 Banerjee et al. 2019 的“代价”）。是否也存在泛化风险膨胀？扎根点：引言中提及 Banerjee et al. 的超效现象，但本文未对其在非随机子抽样中的表现做理论刻画。
非i.i.d.数据的扩展：本文假设 i.i.d.。对于时间序列/空间数据，非随机子样本若按时间顺序分块，设计条件自动满足吗？扎根点：Section 6 未来工作仅一句话提及“dependent data”。
计算复杂度的精细刻画：本文声称“非随机子样本 $J$ 个，每个 $b$ 样本，总访问 $Jb$ 次”，但 $Jb$ 与随机子抽样 $m b$ 的比较依赖于 $J$ 同阶于 $m$ 时的常数。实际中，确定性子样本可能不如随机抽样灵活（需事先设计）。扎根点：Section 1 引入时与 Ting (2021) 的 $O(b)$ 随机抽样算法对比，但未讨论 $J$ 如何决定。

提示：要确认第 2 条是否为真 gap，可查阅 Banerjee et al. (2019) 原文与本文 Theorem 4.1 的证明（可能作者隐式控制了风险），需读 full paper 的定理陈述完整版（本精读基于 abstract 和引用语境，无法确认）。

Maintained by 陈星宇 · Homepage · Source on GitHub