Asymptotics of resampling without replacement in robust and logistic regression¶
作者: Pierre C. Bellec, Takuya Koriyama
来源: Bernoulli
主题: 高维统计 / 随机矩阵
相关性: 7/10
机构绿灯: Rutgers University(US News 前 50,免分进入精读)
链接: 期刊页 · arXiv
一、领域脉络与小综述¶
这个方向是什么¶
本文研究的根本问题是:在高维比例极限下(维度 p 与样本量 n 同阶增长),无放回子采样(subsampling without replacement)与 bagging(自助聚合)这类集成方法,其估计量的渐近行为如何刻画? 具体而言,当研究者用大小为 qn 的随机子样本训练多个基估计量(base learners)并取平均得到 bagged estimate 时,其平方误差由两部分组成:单个基估计量的方差(约 σ²/M)与不同基估计量之间的协方差。后者是理解 bagging 能否降低风险的关键——若基估计量之间高度相关,则集成几乎无增益;若相关性低,则集成显著降方差。本文的核心贡献在于:在稳健回归与逻辑回归中,严格刻画了两个基于不同(但高度重叠的)子样本训练的估计量之间内积的极限,并证明该极限是某个简单非线性方程的唯一解。该方向当前处于理论成熟期:单估计量的高维渐近已由 Donoho-Montanari、El Karoui、Thrampoulidis 等人解决,而多估计量之间的联合分布与相关性是近年才被攻克的 frontier。
发展脉络¶
-
奠基工作:高维 M-估计的精确风险刻画。El Karoui et al. (2013, PNAS) 通过数值模拟与启发式论证揭示了高维稳健回归中"额外高斯噪声"现象;Donoho & Montanari (2016, Probab. Theory Related Fields) 用近似消息传递(AMP)严格证明了这一现象;El Karoui (2013, 2018) 给出了无正则化与岭正则化情形的严格证明。这些工作确立了单估计量的渐近风险由两个非线性方程(对应方差 σ² 与对偶变量 γ)刻画的基本范式。留下的口子:这些结果只针对单个估计量,无法回答"两个估计量之间的相关性"这一集成学习的关键问题。
-
主要进展:从单估计量到多估计量。Thrampoulidis, Abbasi & Hassibi (2018, IEEE Trans. Inform. Theory) 用凸高斯极小极大定理(CGMT)将上述结果推广到更一般的损失与正则化,但同样限于单个估计量。关键转折出现在 Bellec 及其合作者的系列工作:Bellec & Zhang (2021, Ann. Statist.) 通过二阶 Stein 公式建立了去偏估计量的渐近正态性;Bellec (2022, Ann. Statist.) 提出"可观测调整"(observable adjustments)框架,用仅依赖于数据的量(如残差、Hessian)来刻画高维 M-估计量的分布,从而绕开了对未知先验的依赖。本文的位置:作者将这一框架从"单个估计量"推广到"两个估计量的联合分布",核心工具是矩阵值二阶 Stein 公式与随机矩阵的迹估计。
-
当前 frontier:bagging 与子采样的精确理论。与本文最接近的并行工作是 Patil, Du & Kuchibhotla (2023, JMLR) 对 bagged ridge 的研究,以及 Clarté et al. (2024, arXiv:2402.13622) 对 bootstrap/子采样在广义线性模型中的统一分析。本文与后者的关键区别(作者在 intro 中明确强调):Clarté et al. 依赖强凸性(岭正则化)保证解的唯一性与稳定性,而本文处理的是无正则化的 M-估计量,其目标函数可能非强凸(逻辑回归)甚至非凸(稳健回归),因此需要全新的论证——特别是通过修改损失函数(加一个消失的岭项)来绕过强凸性,再用 Lipschitz 连续性将修改后的估计量与原估计量联系起来。
子线索聚类¶
- AMP / 状态演化方法(Donoho-Montanari 2013, El Karoui 2013/2018, Thrampoulidis et al. 2018):用迭代算法(AMP)构造估计量的代理,通过状态演化方程刻画其渐近分布。优点:直观、可处理非强凸损失;缺点:需要损失函数满足特定 Lipschitz 条件,且对"两个估计量的联合分布"这一多维问题推广困难。
- 凸高斯极小极大定理(CGMT)(Thrampoulidis et al. 2015-2018):将高维优化问题转化为等价的标量优化问题,适用于更广的损失与正则化。本文的证明不直接使用 CGMT,而是采用 Bellec 发展的"可观测调整 + 二阶 Stein"框架,这使其能同时处理稳健回归与逻辑回归,并得到联合分布。
- 随机矩阵理论 + 迹估计(本文的核心技术):通过矩阵值二阶 Stein 公式(引理 5.2)与随机矩阵的迹不等式(引理 5.6-5.8),将"两个估计量的内积"转化为仅依赖于数据协方差与残差的迹项,再通过大数定律得到极限方程。这一路线避免了 AMP 的迭代复杂性,直接给出闭式方程。
这个方向在追问的核心问题¶
- 相关性如何随子采样比例 q 变化? 本文证明:极限相关性 η 是方程 (2.4) 的唯一解,且 η ∈ [0, q]。当 q→1(子样本接近全量)时 η→1(完全相关);当 q→0 时 η→0(渐近独立)。关键发现:η 与 q 的关系非线性,且依赖于损失函数与噪声分布。
- bagging 何时有益? 由 (2.13),bagged estimate 的风险 = σ²/M + (1−1/M)ση²。当 η < 1 时,集成严格优于单估计量;当 η 接近 1 时,增益可忽略。本文的数值实验(图 1、图 8)表明:在重尾噪声下,子采样可能反而增大风险(η 曲线非单调),这挑战了 bagging 总是有益的直觉。
- 如何估计极限相关性? 本文提出 (2.11) 的估计量,利用两个子样本上的残差内积来一致估计 ησ²,从而无需知道噪声分布即可评估 bagging 的风险。
⚠️ 作者的 framing¶
作者将本文定位为"无正则化 M-估计量在子采样下的精确渐近理论",并强调两个卖点:(i) 与 Clarté et al. (2024) 不同,本文不依赖强凸性,因此适用于逻辑回归与稳健回归;(ii) 本文的极限方程 (2.4) 比 Clarté et al. 的自洽方程更简洁,且给出了唯一性证明(命题 2.2)。作者在 intro 中淡化了 AMP 方法的适用性,暗示其"难以处理多估计量联合分布"——这是一个值得研究者去核实的判断(AMP 的状态演化其实可以推广到多系统,但确实需要额外的对称性假设)。
张力¶
未见明显对立引用。但存在一个微妙的张力:El Karoui (2018) 强调高维稳健回归的渐近行为依赖于损失函数的详细形状(通过其对偶函数的 Legendre 变换),而本文的极限方程 (2.4) 仅通过近端算子 prox[γℓ_y] 依赖损失,两者在形式上不同但应等价。研究者可去验证:当损失为 Huber 时,本文的方程是否与 El Karoui 的隐式方程给出相同的 σ² 与 η?这是一个值得追踪的 consistency check。
二、最核心、最简单的例子 / 数学内核¶
第一步:符号、模型、可观测数据¶
- 数据:观测到 \((X, y) \in \mathbb{R}^{n \times p} \times \mathbb{R}^n\),其中 \(X\) 的行 \(x_i \sim N(0_p, I_p)\) 独立,\(y_i\) 由模型 \(y_i = x_i^\top \beta^* + \varepsilon_i\)(稳健回归)或 \(P(y_i = 1 | x_i) = 1/(1 + e^{-x_i^\top \beta^*})\)(逻辑回归)生成。\(\varepsilon_i\) 与 \(x_i\) 独立,可能重尾。
- 参数 / 估计目标:
- \(\beta^* \in \mathbb{R}^p\):真实回归系数(未知,非随机)。
- \(\hat{b}(I) \in \mathbb{R}^p\):在子样本 \(I\) 上训练的 M-估计量,即 \(\hat{b}(I) = \arg\min_{b} \sum_{i \in I} \ell_{y_i}(x_i^\top b)\)。这是随机变量,依赖于子样本 \(I\) 和数据。
- \(\bar{b} = \frac{1}{M} \sum_{m=1}^M \hat{b}(I_m)\):bagged estimate(随机变量)。
- \(\sigma^2, \gamma\):单估计量极限方程 (2.1)-(2.2) 的解。\(\sigma^2\) 是 \(\|\hat{b}(I) - \beta^*\|^2\) 的极限,\(\gamma\) 是对偶变量。
- \(\eta\):本文的核心新参数,定义为两个独立子样本估计量内积的极限:\(\eta = \lim_{n \to \infty} (\hat{b}(I) - \beta^*)^\top (\hat{b}(I') - \beta^*)/\sigma^2\),其中 \(I, I'\) 独立同分布。\(\eta\) 是方程 (2.4) 的唯一解。
- 可观测数据:研究者能观测到的是 \((X, y)\) 以及由此计算的 \(\hat{b}(I_m)\)、残差 \(\ell'_{y_i}(x_i^\top \hat{b}(I_m))\) 等。观测不到的是 \(\beta^*\)、\(\sigma^2\)、\(\gamma\)、\(\eta\) 这些极限参数——它们只能通过解方程 (2.1)-(2.4) 或通过 (2.11) 的估计量来间接获得。
- 关键假设:
- 比例极限:\(n/p \to \delta > 1\),子样本大小 \(|I| = qn\) 满足 \(q\delta > 1\)(保证子样本上的 M-估计量良定义)。
- 损失函数:\(\ell_y(\cdot)\) 凸、二次可微、Lipschitz 梯度,且 \(\ell''_y > 0\)(保证近端算子良定义)。Huber 损失满足这些条件,但标准 \(L_1\) 损失不满足(不可微)。
- 数据分布:\(x_i\) 高斯(或满足集中不等式),\(\varepsilon_i\) 独立且矩条件足够(允许重尾,但需 \(E|\varepsilon|^k < \infty\) 对某个 \(k\) 成立)。
第二步:最小内核¶
问题:假设 \(p = n/2\)(\(\delta = 2\)),取 \(q = 0.5\)(子样本大小 \(= n/2\))。训练两个独立的子样本估计量 \(\hat{b}(I)\) 和 \(\hat{b}(I')\),它们共享约 \(n/4\) 个样本。问:这两个估计量的内积 \((\hat{b}(I) - \beta^*)^\top (\hat{b}(I') - \beta^*)\) 在 \(n \to \infty\) 时收敛到什么?
直觉:若两个估计量独立,则内积趋于 0;若完全相同(\(I = I'\)),则内积等于 \(\|\hat{b}(I) - \beta^*\|^2 \to \sigma^2\)。实际情况介于两者之间:共享样本引入了正相关性。本文证明:内积收敛到 \(\sigma^2 \eta\),其中 \(\eta\) 是方程 (2.4) 的唯一解。
方程 (2.4) 的简化形式(取 \(a=0\),即稳健回归):
为什么这个方程会出现? 关键在于近端映射的 Lipschitz 性质。M-估计量 \(\hat{b}(I)\) 可以写成数据的隐函数,其关于某个样本 \(i\) 的导数由残差 \(\ell'_{y_i}(x_i^\top \hat{b}(I))\) 控制。两个估计量的内积可以展开为:
为什么这是"最小内核"? 因为一旦理解了 \(\eta\) 的方程,bagged estimate 的风险 (2.13) 就是简单的代数组合:\(\sigma^2/M + (1-1/M)\sigma^2\eta\)。而 \(\eta\) 的估计 (2.11) 则是将理论方程中的期望替换为样本均值。整个论文的数学贡献可以归结为:证明 (2.4) 有唯一解,且该解确实等于两个估计量内积的极限。
三、这篇论文做了什么¶
三句话¶
- 研究了什么问题:在高维比例极限下,无正则化 M-估计量(稳健回归与逻辑回归)在无放回子采样下的 bagging 风险如何刻画,特别是两个子样本估计量之间的相关性。
- 核心工具 / 方法:将 M-估计量修改为带消失岭项的版本,利用矩阵值二阶 Stein 公式(引理 5.2)与随机矩阵迹不等式(引理 5.6-5.8),将内积的极限转化为非线性方程 (2.4) 的解。
- 主要结论:两个估计量的内积收敛到 \(\sigma^2 \eta\),\(\eta\) 是 (2.4) 的唯一解;由此得到 bagged estimate 风险的闭式表达式 (2.13),并给出 \(\eta\) 的一致估计量 (2.11),可用于最优子采样比例 \(q\) 的选择。
关键设定与假设¶
- 核心假设(定理 2.3 与 3.3 共用):
- 比例极限:\(n/p \to \delta > 1\),\(q \in (0,1)\) 固定,\(q\delta > 1\)。
- 损失函数:\(\ell_y\) 凸、二次可微、\(|\ell'_y| \le 1\)、\(0 < \ell''_y \le 1\)(稳健回归);逻辑损失满足这些条件。
- 数据:\(x_i \sim N(0, I_p)\) 独立;\(\varepsilon_i\) 独立于 \(x_i\),且 \(\mathbb{E}|\varepsilon_i|^k < \infty\) 对某个 \(k > 2\) 成立(允许重尾)。
- 子采样:\(I, \tilde{I}\) 独立且均匀分布于所有大小为 \(qn\) 的子集。
- 相比已有工作的放宽 / 强化:
- 放宽:不要求损失强凸(对比 Clarté et al. 2024 的岭正则化设定),允许非光滑损失(通过修改损失函数绕过)。
- 强化:得到了联合分布(两个估计量的内积),而不仅是边缘分布;且给出了 \(\eta\) 的可估计量((2.11)),而不仅是存在性。
主要结果¶
- 定理 2.3(稳健回归):
- 内积收敛:\((\hat{b}(I) - \beta^*)^\top (\hat{b}(I') - \beta^*) \to_P \sigma^2 \eta\)。
- 相关性收敛:相关系数收敛到 \(\eta\)(归一化后)。
- 联合分布:\((x_i^\top \hat{b}(I), x_i^\top \hat{b}(I'))\) 对 \(i \in I \cap I'\) 收敛到 \((\text{prox}[\gamma \ell_y](\sigma G), \text{prox}[\gamma \ell_y](\sigma \tilde{G}))\)。
- 风险分解:\(\|\bar{b} - \beta^*\|^2 \to_P \sigma^2/M + (1-1/M)\sigma^2 \eta\)。
- 估计量:(2.11) 中的 \(\hat{\eta}\) 满足 \(\hat{\eta} \to_P \eta\)。
- 定理 3.3(逻辑回归):同样的结论,但 \(\eta\) 由方程 (3.9) 刻画,且需要假设 \(q\delta > h(\nu)\)(MLE 存在性阈值,见 Candès & Sur 2018)。
- 命题 2.2(唯一性):方程 (2.4) 的解存在且唯一,且 \(\eta \in [0, q]\)。证明基于 \(F\) 是 \(q\)-Lipschitz 压缩映射。
证明路线与技术技巧¶
- 修改损失函数:定义 \(\ell_{y,\lambda}(u) = \ell_y(u) + \frac{\lambda}{2} u^2\),对应的估计量 \(\hat{b}_\lambda(I)\) 是强凸问题的解。证明 \(\hat{b}_\lambda(I)\) 与 \(\hat{b}(I)\) 的差异在 \(\lambda \to 0\) 时消失(利用 Lipschitz 损失与集中不等式)。
- 二阶 Stein 公式:对高斯矩阵 \(X\),利用 Stein 引理将 \(\mathbb{E}[(\hat{b}_\lambda(I) - \beta^*)^\top (\hat{b}_\lambda(I') - \beta^*)]\) 展开为迹项 \(\mathbb{E}[\text{tr}(A \cdot \text{残差外积})]\),其中 \(A\) 是 Hessian 逆矩阵。
- 迹的集中:利用随机矩阵的迹不等式(引理 5.6-5.8),证明迹项收敛到确定性极限,该极限由 \(\sigma^2, \gamma, \eta\) 满足的方程组决定。
- 自洽方程:将 \(\eta\) 的表达式代入,得到 (2.4)。唯一性通过 \(F\) 的 Lipschitz 常数 \(q < 1\) 证明。
- 估计量的一致性:将 (2.4) 中的期望替换为样本均值,利用大数定律和连续映射定理证明 \(\hat{\eta} \to_P \eta\)。
真实例子与应用¶
- 模拟实验(图 1-3, 5-8):
- 数据:\(n = 5000, p = 1000\)(\(\delta = 5\)),噪声为 \(t\) 分布(df=2, 3)或高斯,尺度参数变化。
- 验证内容:① 内积与相关系数的模拟值 vs 理论值 \(\eta\);② 风险曲线 \(q \mapsto \sigma^2 \eta\) 的形状;③ 估计量 (2.11) 的偏差。
- 关键发现:在重尾噪声(\(t_2\))下,\(q \mapsto \sigma^2 \eta\) 呈 U 型,存在最优 \(q^* < 1\);在轻尾噪声下,曲线单调递减,最优 \(q^* = 1\)。这为"何时 bagging 有益"提供了精确判据。
- 无真实数据应用:本文为纯理论 + 模拟验证,没有真实数据集分析。
🔎 结论是否比证明窄¶
- 明确窄的地方:
- 定理 2.3 要求 \(\ell''_y > 0\)(严格凸损失),但作者在 intro 中声称适用于"非光滑损失"(如 Huber 的平坦区域)。实际上,Huber 损失在 \(|u| > 1\) 时 \(\ell''_y = 0\),不满足假设。作者在附录 A.2 用伪 Huber 损失 \(\sqrt{1+u^2}\) 做了模拟,但没有给出非光滑情形的严格证明。
- 定理 3.3 要求 \(q\delta > h(\nu)\)(MLE 存在性),但没有讨论 \(q\delta\) 接近阈值时的临界行为(此时 \(\sigma^2\) 发散,\(\eta\) 的定义需要重新归一化)。
- 估计量 (2.11) 的一致性证明依赖于 \(\hat{\gamma}(I)\) 的一致估计,但作者没有给出 \(\hat{\gamma}(I)\) 的收敛速度,只证明了相合性。
- 被泛化的地方:
- 作者在 intro 中暗示"结果适用于更一般的损失函数",但证明仅覆盖了满足假设 2.1/3.1 的损失。对于非光滑损失(如 Huber),只能通过修改损失函数 + 连续性论证间接覆盖,但没有给出定量误差界。
四、开放问题¶
- 非光滑损失的严格处理:能否将定理 2.3 推广到 Huber 损失(\(\ell''_y\) 非正定)?作者在附录 A.2 的模拟表明结论成立,但证明需要新的技巧(可能涉及次梯度与 Moreau 包络)。
- 临界行为:当 \(q\delta\) 接近 \(h(\nu)\)(逻辑回归 MLE 存在性阈值)时,\(\sigma^2 \to \infty\),\(\eta\) 的定义是否仍然有意义?能否刻画临界指数?
- 有放回采样(bootstrap):本文只处理了无放回子采样。Bootstrap(有放回)的联合分布是否满足类似的方程?Clarté et al. (2024) 处理了带岭正则化的情形,但无正则化 bootstrap 的极限方程尚不清楚。
- 非高斯设计:本文假设 \(x_i \sim N(0, I_p)\)。对于一般各向异性高斯或次高斯设计,方程 (2.4) 是否仍然成立?随机矩阵的迹不等式可能不再适用,需要新的论证。
- 估计量的收敛速度:(2.11) 的估计量 \(\hat{\eta}\) 的收敛速度是多少?能否构造置信区间?这需要 Edgeworth 展开或 bootstrap 校准。
- 与 U-统计量的联系:bagged estimate 的方差分解本质上是一个二阶 U-统计量(对子样本对求和)。本文的 \(\eta\) 方程是否可以通过 U-统计量的 Hoeffding 分解重新推导?这可能为高阶项(如 \(M\) 固定时的精确分布)提供新视角。
提示:要确认这些是否真 gap,建议去读 Clarté et al. (2024)、Patil et al. (2023) 以及 Bellec 本人的后续工作(如 arXiv:2405.xxxx)的 intro——如果多个近期工作都指向同一个问题,那大概率是共识性 gap;如果互相矛盾,则是机会。
Maintained by 陈星宇 · Homepage · Source on GitHub