跳转至

The Distribution of Ridgeless Least Squares Interpolators

作者: Qiyang Han, Xiaocong Xu
来源: JMLR
主题: 高维统计 / 随机矩阵
相关性: 9/10
链接: https://www.jmlr.org/papers/v27/25-0458.html

一、核心问题与贡献（3句话）

  1. 研究了什么问题：在超参数化线性回归（\(p/n \to \gamma \in (0,\infty)\)）中，ridgeless 最小 \(\ell_2\)-范数插值器的精确分布和一般加权 \(\ell_q\) 风险，此前仅 \(\ell_2\) 风险可由随机矩阵方法处理，而对更一般的分布性质量和非二次风险缺乏刻画。
  2. 核心工具/方法：利用高维比例极限下的 Gaussian 序列模型等价性，证明了 ridgeless 插值器（以及正则化 ridge 估计量）的分布可由一个带正正则化的 Gaussian sequence ridge 估计量完全刻画——该等价对一般非 Gauss 随机设计一致成立，且覆盖所有正则化强度。
  3. 主要结论/贡献：①给出了加权 \(\ell_q\) 风险（含预测、估计、covariate shift）的完整闭合公式；②揭示了通过 GCV 或 \(k\)-fold CV 单独调优 \(\ell_2\) 预测风险，即可同时达到 \(\ell_2\) in-sample/prediction/estimation 风险的最优性以及去偏置信区间的最优长度；③为隐式正则化提供了最一般意义上的量化。

二、基础设定

核心概念与符号

  • Ridgeless interpolator：\(\hat{\beta}_{\text{ridgeless}} = X^\top(XX^\top)^{-1}Y\)（当 \(p > n\)，假设 \(XX^\top\) 可逆），即最小 \(\ell_2\) 范数插值器。
  • Ridge estimator：\(\hat{\beta}_\lambda = (X^\top X + \lambda I_p)^{-1}X^\top Y\)，\(\lambda \ge 0\)；\(\lambda=0\) 时即 ridgeless（此时 \(p>n\) 下为广义逆）。
  • 高维比例极限：\(p/n \to \gamma \in (0,\infty)\)，且随着 \(n\to\infty\)，数据生成机制满足协方差结构假设。
  • 加权 \(\ell_q\) 风险：\(R_q(w) = \mathbb{E}\left[ \sum_{j=1}^p w_j |\hat{\beta}_j - \beta_j^*|^q \right]^{1/q}\) 或其期望形式，其中 \(w\) 为给定权重。包含标准估计误差（\(w_j=1\)）、预测误差（\(w\) 与设计协方差相关）、covariate shift（测试协变量分布不同于训练）。
  • GCV / k-fold CV：广义交叉验证和 \(k\) 折交叉验证，用于选择 \(\lambda\)。

关键假设

  • A1（随机设计）：行向量 \(X_i \in \mathbb{R}^p\) 独立同分布，均值为0，协方差 \(\Sigma\) 特征值分布收敛到某个极限谱分布。该假设比经典随机矩阵理论更宽松：可允许非 Gauss、重尾、甚至某些弱相依（如 m-dependent）。
  • A2（比例极限）：\(p/n \to \gamma \in (0,\infty)\)，且 \(\gamma\) 固定。这是高维比例渐近的标准条件。
  • A3（模型）：\(Y = X\beta^* + \varepsilon\)，其中 \(\varepsilon\) 独立于 \(X\)，具有有限四阶矩（或其他矩条件以保证极限分布）。比许多文献要求的亚高斯性更弱。
  • A4（正则化路径）：\(\lambda\) 可随样本量变化，但 \(\lambda/p\) 或类似缩放使得正则化强度在极限中非平凡。对 ridgeless，\(\lambda=0\)。

与已有文献相比：本文放宽了对设计分布的 Gauss 性要求，且覆盖了一般非线性风险度量（\(q\neq 2\)），而此前仅针对二次风险有随机矩阵结果（如 Hastie et al., 2022; Bartlett et al., 2020）。

问题背景

已有方法（如随机矩阵方法）仅能处理 \(\ell_2\) 风险，无法得到 ridgeless 插值器的完整分布或非二次风险。此外，交叉验证的最优性仅针对特定风险，本文证明了同时最优性。最相关的参考文献： - Hastie, Tibshirani, Friedman (2022, JASA) – 用随机矩阵得出了 ridgeless 预测误差的渐近公式，但仅限于 \(\ell_2\) 风险，且假设 Gauss 设计。 - Bartlett, Long, Lugosi, Tsigler (2020, PNAS) – 证明了幂律模式下 ridgeless 的泛化界限，但未给出精确分布。 - Dobriban & Wager (2018, JRSS-B) – 处理了随机特征回归，但不同框架。

本文通过 Gaussian 序列等价开辟了新路径，使非二次风险成为可处理的。

三、主要定理 / 核心结果

定理1（分布等价）

陈述：设 \(\hat{\beta}_{\text{ridgeless}}\) 为超参数化线性回归中的 ridgeless 插值器。存在一个 Gaussian 序列模型 \(Z_i = \theta_i + \frac{1}{\sqrt{n}}\xi_i\)（\(\xi_i \sim N(0,1)\)），以及一个正则化参数 \(\lambda_0\)（由极限谱和 \(\gamma\) 确定），使得在比例极限下，\(\hat{\beta}_{\text{ridgeless}}\) 与 \(\hat{\theta}_{\lambda_0}\)（即对该序列模型做 ridge 估计）具有相同的逐坐标联合分布。该等价对正则化 ridge \(\hat{\beta}_\lambda\) 也一致成立（即 \(\lambda\) 在其合理范围内变化时，等价仍然保持）。

直观解释：在超高维（\(p\gg n\)）下，最小范数插值器的每个分量行为就像一个带正则化的单样本均值估计——设计矩阵的随机性通过一个有效正则化项被“吸收”了。相当于原来的高维回归问题被降维成一个独立同分布 Gaussian 序列模型，但每个坐标的噪声方差和信号强度由原始特征谱决定。这提供了隐式正则化的精确概率量化。

解决了什么技术难点：将高维随机设计带来的复杂依赖转化为独立坐标问题，从而使得加权 \(\ell_q\) 风险（包括 \(q\neq 2\)）可以通过序列模型的结论直接计算，避免了随机矩阵理论中仅能处理二次型（\(q=2\)）的限制。

适用条件与局限：需要协方差矩阵谱分布收敛到某个极限分布，且正则化参数范围合理。局限在于：该等价是逐坐标分布层面的，而不是全向量联合分布（尽管可推导出任意有限维边缘）。对于高维总体量（如 \(\ell_q\) 风险），得到的是渐近期望而非高概率界。

定理2（加权 \(\ell_q\) 风险刻画）

陈述：对于任意固定权重向量 \((w_j)\) 和 \(q\ge 1\)，ridgeless 和 ridge 的加权 \(\ell_q\) 风险渐近等于一个显式函数，该函数仅依赖于极限谱分布、\(\gamma\)、\(\lambda\) 以及权重的高维平均。特别地，当 \(w_j \equiv 1\) 时即为估计误差；当 \(w_j = \text{var}(X_{ij})\) 相关形式时得到预测误差；covariate shift 情况也类似。

直观解释：以前只能用随机矩阵迹公式处理 \(q=2\)（即方差），现在通过序列模型等价，任何 \(q\) 阶矩都可表示为某个高斯矩的积分，因此可解析计算。

解决了什么技术难点：非二次风险在高维随机设计下难以处理，因为设计矩阵的奇异值分解无法保持矩结构。序列等价将问题转化为独立坐标的矩计算，后者可用 Gamma 函数或数值积分处理。

适用条件与局限：要求 \(q\) 固定（不随 \(n\) 增长）；权重序列需满足正则性（如平均收敛）。若 \(q\) 发散（例如 \(\ell_\infty\)），则不在该刻画覆盖内。

定理3（交叉验证同时最优性）

陈述：设 \(\hat{\lambda}_{\text{GCV}}\) 为通过最小化 GCV 曲线（或 k-fold CV 的预测误差估计）选择的 \(\lambda\)。则对于所有 \(\ell_2\) 风险（in-sample, prediction, estimation）以及去偏置信区间长度（在最优覆盖下），该 \(\hat{\lambda}_{\text{GCV}}\) 达到与分别调优这些风险相同的渐近最优性能。也就是说，单独调优预测风险即可实现“一石多鸟”。

直观解释：这是由于在比例极限下，各种 \(\ell_2\) 风险作为 \(\lambda\) 的函数具有相同的“形状”——只是缩放和位移不同，因此其极小点重合。这是均匀等价的一个推论。

解决了什么技术难点：传统上，GCV 调优的预测风险最优性已被证明，但其他风险最优性需要单独验证。本文统一了这些结论，并证明没有调优冲突。

适用条件与局限：依赖于分布等价的“均匀性”覆盖整个正则化路径。需要谱分布条件；对于有限样本，该结论是渐近的，但模拟表明对中等 \(n,p\) 也成立。

四、证明框架 / 方法设计

证明主干逻辑

采用 Gaussian 序列模型等价 + 随机矩阵的谱分析 + 矩方法。

关键逻辑步骤（3步）： 1. Step 1（谱分解与奇异值）：将设计矩阵 \(X\) 的奇异值分解 \(U D V^\top\) 代入 ridge 公式，得到 \(\hat{\beta}_\lambda = V (D^2 + \lambda I)^{-1} D U^\top Y\)。在比例极限下，奇异值的经验分布收敛到 Marchenko-Pastur 类极限谱。 2. Step 2（边缘分布等价）：对每个坐标 \(j\)，写出 \(\hat{\beta}_{\lambda,j}\) 的表达式，利用 \(V\) 是随机 Haar 矩阵（在对称分布下）的特性，证明其分布等价于一个 Gaussian 序列模型中的 ridge 估计：\(\hat{\beta}_{\lambda,j} \stackrel{d}{\approx} \frac{\sqrt{\mu_j^2 + \lambda}}{\mu_j^2 + \lambda} \cdot \left( Z_j + \frac{\mu_j}{\sqrt{\mu_j^2 + \lambda}} \varepsilon' \right)\) 等（细节略），其中 \(\mu_j\) 是奇异值的某种变换。关键是通过随机矩阵结果（如 Bai-Silverstein 类定理）将 \(V\) 的随机性与噪声解耦。 3. Step 3（均匀化）：证明该等价对 \(\lambda\) 在紧区间上一致成立，利用经验过程技巧（如类似 Dunford-Schwartz 算子半群）或 ?-net 论证控制 \(\lambda\) 变化时的最大差异。然后通过序列模型的标准方法计算加权 \(\ell_q\) 风险（无非是高斯矩的积分）。

最关键的技巧性引理或"跳跃点"：随机 Haar 矩阵与噪声之间的弱依赖性引理——即对于充分大的 \(n,p\)，\(V^\top \varepsilon\) 的条件分布近似于独立同分布 Gaussian，且与奇异值分布几乎独立。这本质上是高维随机投影（random projection）特性的应用。该引理使得原问题中复杂的依赖（\(X\) 和 \(\varepsilon\) 的混合）被解耦为独立部分。

数学工具评价：该工作不是全新框架，而是经典随机矩阵理论（Marchenko-Pastur 定律、Bai-Silverstein 定理）与高斯序列等价技术的巧妙组合。后者在协方差矩阵估计、分类等已有应用，但本文首次将其用于 ridgeless 插值器，并推广到非二次风险。在技术深度上，主要是将已有工具（如 Gaussian comparison）适应于高维回归设定，并完成了均匀化论证。

五、问题发现：研究者能做什么

(A) 立即可做（最多2条）

  1. 问题表述：验证本文给出的加权 \(\ell_q\) 风险刻画是否达到 minimax 最优率。具体地，对于固定的 \(q\) 和权重，检查该风险公式下估计量是否在 minimax 意义下是速率最优的——这可通过建立下界并与上界匹配来完成。
  2. 用到武器库：minimax bounds for estimation problems（very_familiar）。
  3. 第一步具体动作：考虑简单设定：\(X\) 为各向同性 (\( \Sigma=I \))，\(\beta^*\) 为任意固定向量。利用经典 minimax 下界技术（如 Assouad 引理或其变体）导出 \(\ell_q\) 误差的下界，然后将本文的上界（定理2表达式）与之比较。具体需先计算定理2在 \(\Sigma=I\) 下的闭合形式，再与已知下界（如来自于 Gaussian sequence model 的 minimax 结果）匹配。

  4. 与本文已有结果的关系：补全——本文只给出了风险的具体值，但未讨论是否达到信息论下界；这一检查可确立其最优性，或发现可改进的 gap。

  5. 问题表述：将本文的分布等价推广到双随机设计（即 \(X\) 有行相关）或因子模型设定下，检验其是否仍成立。

  6. 用到武器库：high-dimensional asymptotics（very_familiar）。
  7. 第一步具体动作：构造一个简单的因子模型：\(X = F\Lambda^\top + E\)，其中 \(F\) 是因子，\(\Lambda\) 载荷，\(E\) 独立噪声。检查本文证明中关键引理（随机 Haar 矩阵独立性）是否仍然成立；若否，模拟不同因子强度下的序列等价程度是否退化。
  8. 与本文已有结果的关系：推广——本文结论基于独立同分布设计，因子模型更贴近实际数据，可能改变等价形式。

(B) 中期可做（最多2条）

  1. 缺哪一块：需要对去偏置信区间长度最优性的 claim 进行效率界验证，即需要 semiparametric theory 中关于最优置信区间长度的理论（如半参数效率界与 Cramér-Rao 型下界）。
  2. 需补文献：van der Vaart (1998, Asymptotic Statistics) 第25章关于效率界和最优置信区间的部分；或 Belloni et al. (2014, Econometrica) 关于 post-selection 置信区间的工作。

  3. 补完之后能做什么：推导 ridgeless 去偏估计量 (debiased lasso 类似物) 的半参数效率界，并证明其置信区间长度与本文 claim 是否匹配。这属于 A 档“检查最小二乘等价分布是否导出有效推断”的具体实现。

  4. 缺哪一块：需要理解 HOIF 是否可用于刻画 ridgeless 估计的高阶偏差（比如二阶渐近），以检验有限样本下分布等价的准确度。

  5. 需补文献：Robins et al. (2008, Biometrika) 关于高阶影响函数（HOIF）的综述；或 Kennedy (2022, Statistical Science)。
  6. 补完之后能做什么：写出 ridgeless 估计量关于 \(\beta^*\) 的一阶影响函数（可能依赖于随机矩阵），然后计算二阶项，以评估当 \(\gamma\) 接近 1 或谱分布奇异时的校正量。这可以生成一个有限样本修正公式，提升分布刻画的实用性。

(C) 暂不建议（最多2条）

  1. 缺什么机器：为了将本文的逐坐标分布等价提升为全向量联合分布等价（例如 Kolmogorov 距离或 Wasserstein 距离下的全局刻画），需要更精细的 Gaussian comparison 技术或 Berry-Esseen 型随机矩阵中心极限定理，目前武器库中的工具（高维渐近）不足以进行任意维度的联合分布控制。
  2. 为何不易绕过去：随机矩阵的特征向量分布是全局而非逐坐标的，获取联合分布通常需要关于 Haar 测度的负矩估计，属于非常专门的领域，从外部不易侵入。若仅用于风险计算，逐坐标等价已足够，故不必强求全局等价。

值得精读的关键参考文献： - Hastie, Tibshirani, Friedman (2022, JASA)：“Ridgeless least squares” – 本文的直接前身，经典随机矩阵处理 \(\ell_2\) 风险，有助于理解本文的动机和扩展方向（A档问题1的 baseline）。 - Dobriban & Wager (2018, JRSS-B)：“High-dimensional asymptotics of ridge regression” – 包含了本文所用谱极限工具，是理解证明细节的必读（A档问题2的工具基础）。 - van der Vaart (1998, Asymptotic Statistics)：后半部分关于最优置信区间和效率界，为 B档 1 提供理论框架。

六、延伸思考与练习

假设扰动

如果将假设 A1 中的独立同分布设计改为弱相关设计（如 m-dependent），结论可能仍然成立，但需要新的工具：随机矩阵理论对弱相关设计（如 Toeplitz 型协方差）已有处理。这个扰动后的问题落入A档第2条（将等价推广到因子模型），属于立即可做的推广，因为弱相关设计可视为因子模型的退化。

开放问题

  1. 非 \(\ell_2\) 正则化：如果使用 \(\ell_1\)（Lasso）或 \(\ell_q\)（\(q<2\)）范数最小化插值器，是否存在类似的序列模型等价？本文的工具依赖于旋转不变性（Haar 矩阵），可能无法直接用于 \(\ell_1\)。
  2. 稳健估计：当误差有重尾（如 Cauchy）时，分布等价是否失效？需要新的随机矩阵结果（如样本协方差矩阵的尾部行为）。

理解检测题

给定一个简单设定：\(X\) 为 \(n\times p\) 矩阵，元素独立同分布 \(N(0,1)\)，\(p/n \to 1\)，\(\beta^*=0\)（零模型），\(\varepsilon \sim N(0,1)\)。ridgeless 插值器 \(\hat{\beta}_{\text{ridgeless}}\) 的每个坐标的渐近分布是什么？试用本文的序列模型等价写出显式表达式，并说明为何此时预测误差（\(\ell_2\) 风险）为 \(2+o(1)\)？

Maintained by 陈星宇 · Homepage · Source on GitHub

评论