Comparing regularisation paths of (conjugate) gradient estimators in ridge regression¶

作者: Laura Hucker, Markus Reiß, Thomas Stark
来源: Electronic Journal of Statistics
主题: 非参数 / 半参数
相关性: 6/10
链接: 期刊页 · arXiv

一、领域脉络与小综述¶

这个方向是什么¶

本文研究的是线性回归中，迭代算法（梯度下降/梯度流 vs. 共轭梯度）在 early-stopping 正则化下的统计性质比较。根本上要解决的问题是：当使用共轭梯度（CG）这类数值上收敛很快的迭代算法时，它的迭代路径（即正则化路径）在统计风险上，是否等价于或者可被映射到已充分理解的线性方法（如梯度流 GF、岭回归 RR）的路径？当前成熟度：GF 与 RR 的比较已有扎实理论（如 Ali et al. 2018, 2020），但 CG 因其非线性与迭代依赖性，其统计风险分析仍不成熟，属于正在打开的探索方向。

发展脉络（history）¶

奠基工作（2018-2020）：Ali, Kolter & Tibshirani [2] 首次建立了梯度流（GF）与岭回归（RR）之间的严格风险比较——他们证明了在时间步长 t 与惩罚参数 λ = 1/t 校准下，GF 的预测风险至少是 RR 的 1.69 倍（即 GF 的常数因子劣势）。这个比较框架是本文的核心武器。随后 Ali, Dobriban & Tibshirani [8] 将这一比较拓展到随机梯度流（SGF），给出了显式的 excess risk 上界。这两篇工作确立了“用显式误差分解比较迭代算法与 ridge oracle”的范式，并将早期停止视为隐式正则化。
主要进展（2016-2024）：Blanchard, Hoffmann & Reiß [10] 对一般谱正则化方法（含 Landweber）建立了早期停止的 oracle 适应理论——他们证明了一种基于残差的停止规则能在强 L² 范数下达到自适应。Hucker & Reiß [4] 则首次对共轭梯度（CG）在统计逆问题中的 early-stopping 做了系统误差分析：他们给出了显式误差分解，将 CG 的预测误差分解为“类偏差”与“类方差”项，并构造了一个数据驱动的停止规则 τ 以达到最优率。[4] 是本文最直接的先行工作，本文将其残差多项式分析（Lemma 4.7）和误差分解思想继承下来，并换了一个新问题：比较 CG 与 GF 的整个路径，而不仅仅是 oracle 停止点。
当前 frontier（2020-2025）：Mourtada & Rosasco [11] 用交换性论证给出了 ridge 预测误差的极简分析，但无法推广到 CG（因为 CG 不是线性方法）。Tsigler & Bartlett [1] 对过度参数化 ridge 的泛化界做了通用分析，但仅限于 ridge。J. Wu, Bartlett et al. [3] 则展示了过度参数化 logistic 回归中 GD 的 early-stopping 相对于渐近解（插值）的统计优势，将注意力引向 early-stopping 在非最小二乘下的隐式正则化。Finocchio & Krivobokova [8] 则指出，在特定潜因子模型下，CG 可以做到小风险，而主成分回归（PCR）则不能——这强调了 CG 的有监督降维特性。
本文的位置：本文在 Hucker & Reiß [4] 对 CG 误差分解的基础上，首次证明了 CG 的正则化路径与 GF/RR 的路径在风险上至多差一个常数因子（即 CG oracle 不比 GF/RR oracle 差太多）。它不属于“大幅突破”，而是提供了一个路径级别的比较定理，使得研究者可以安全地利用 GF/RR 的风险理论来推断 CG 的行为。

子线索聚类¶

被引文献大致落在如下四条子线索上（本文的 introduction 主要沿线索 1 和 2，3 和 4 作为背景）：

迭代算法与 ridge 比较框架（路径级别）：[2], [8], 本文本身。做什么：建立 GF/SGF/CG 的预测风险显式上界，并将其与 ridge oracle 的风险比较。聚焦常数因子与整个路径，而非仅是 oracle 停止点。已知瓶颈：CG 因非线性无法直接纳入该框架，本文试图用变换迭代步数来绕过。
CG 在逆问题中的统计误差分析：[4], [9], [10], [12], [14]。做什么：分析 CG（或一般谱正则化法）在统计逆问题/核回归下的收敛率与 early-stopping 规则。进展：上界基本匹配 minimax 下界。已知瓶颈：高概率上界依赖精细的残差多项式控制，且通常假设固定设计、独立同分布噪声。
ridge 的高维精确渐近与泛化界：[1], [6], [11], [13]。做什么：用随机矩阵理论或交换性论证给出 ridge 的精确/非渐近风险。已知瓶颈：这些结果对 CG 无法直接使用，因其依赖于 ridge 的线性（显式解）或谱分解。
实用/软件层面：[5]。做什么：scikit-learn 默认在 ridge 中使用 CG，强调其数值效率。

这个方向在追问的核心问题（2-4 个）¶

CG vs. GF 的 risk gap 到底是多少？ 能否被一个绝对常数（独立于设计）界定？还是依赖于有效秩/信噪比？
这种路径级别的比较能否推广到高维随机设计设定（p > n, 协方差结构未知）？ 本文的主要结果（Lemma 3.5, Theorem 3.9）是在固定设计下证明的，能否用随机矩阵技术（如 [1], [6]）推广？
CG 的“有监督降维”优势在什么条件下能转化为统计上的实质性（超越常数因子）提升？ cf. Finocchio & Krivobokova [8] 的潜因子模型暗示了这种可能性，但本文的常数因子框架尚无法捕捉。

⚠️ 作者的 framing（必须明确标注成"这是作者的说法"）¶

作者的缺口 framing： “We show that [...] the prediction risk for CG iterates can be bounded by a corresponding prediction error of gradient flow at transformed iteration indices. This way, the risk along the entire regularisation path of CG can be compared to that for standard linear methods.” 作者把自己 frame 成“补上了 CG 统计风险没有严格理论这个缺口”，并将 CG 纳入了已知（GF/RR）的比较框架。具体来说，他们声称两条路径是“相似的”。
被淡化/回避的竞争路线：
高维随机设计：本文完全采用固定设计（X 视为给定）。作者的 justification 是“the randomness in the response Y alone already yields interesting results”——但该论述回避了高维下设计随机性与特征值估计误差带来的额外复杂性，这正是 [1], [6], [11] 等关注的。
与 PCR 的对比：只轻描淡写地引用 Finocchio & Krivobokova [8] 说 CG 优于 PCR，但未在本文的框架内做任何直接比较。
与残差基停止规则（如 discrepancy principle）的比较：Blanchard et al. [10] 和 Hucker & Reiß [4] 都构造了数据驱动停止规则，但本文只讨论了 oracle 路径比较，没有涉及如何实际选择停止点。
什么明显该被引/该存在、却没出现在 intro 里？
与 CG 密切相关的 Lanczos 方法 在任何迭代分析方法中几乎必然被提及，本文未引用其标准参考文献。
Andrew Stuart 等人 关于 SDE 与早停正则化的控制理论视角（如《Inverse Problems》系列）——这些工作与本文所关心的梯度流正则化有深层联系，但未出现。

张力¶

未见明显对立引用。值得注意的微妙差异是：Ali, Kolter & Tibshirani [2] 证明 GF 风险至少是 RR 的 1.69 倍，暗示 GF 严格劣于 RR；而 Mourtada & Rosasco [11] 的极简分析似乎暗示 GF 在特定条件下可以更优——但这并非矛盾，而是不同上下文（[2] 是固定设计下的 worst-case bound，[11] 更依赖于有效秩条件）。

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

第一步：符号、模型、可观测数据¶

符号： - Y：n 维观测响应向量（\(n \times 1\)），可观测。 - X：n × p 设计矩阵（固定），可观测。 - β：p 维未知回归系数向量（参数/estimand）。 - ε：n 维噪声向量，各分量 i.i.d. \(\sim (0, \sigma^2)\)，不可观测。 - Σ̂ := X^T X / n：p × p 样本协方差矩阵（固定设计下是已知的）。 - Σ：总体协方差矩阵（本文假设固定设计，所以总体协方差是 Σ̂ 的期望但实际被视为给定）。 - λ > 0：ridge 惩罚参数（调谐参数）。 - t（或 k）：迭代步数（调谐参数），作为 early-stopping 的隐式正则化器。 - β̂_GF(t)：梯度流在 t 时刻的估计量（连续时间，沿梯度下降方向）。 - β̂_CG(k)：共轭梯度第 k 次迭代的输出估计量。 - β̂_RR(λ)：岭回归估计量：\(β̂_{RR}(λ) = (X^T X + n λ I)^{-1} X^T Y\)。

模型：

Y = X β_0 + ε, \quad ε \sim N(0, σ^2 I_n) \quad (\text{I.i.d. Gaussian, 方差已知}).

其中 \(β_0\) 是固定但未知的真值。所有推断针对预测误差 \(||Y_0 - X_0 β̂||^2\) 的条件期望，即预测风险（其中 \((X_0, Y_0)\) 是新的独立副本）。

可观测数据：研究者看到的是 \((Y, X)\) 对。\(ε\) 和 \(β_0\) 不可观测，\(n, p\) 已知。Gaussian 性假定主要用于精细概率界，本文部分结果仅在 sub-Gaussian 假设下成立（见引理引用）。

关键设定：固定设计（\(X\) 视为非随机），且 \(X^T X\) 与 \(X X^T\) 可同时对角化。核心分析是在谱域内进行——使用 X 的奇异值分解。

第二步：讲最小内核¶

本文的核心数学问题可简化为 一维版本的比较（但不是平凡的）：

最简特例：假设 \(X = diag(s_1, \dots, s_p)\) 是对角矩阵（即 \(p=n\)，数据是正交设计的），且关心的是预测风险。此时： - 梯度流在时刻 t 的估计量 \(β̂_{GF}(t)\) 的系数为：\(β̂_{GF, j}(t) = (1 - e^{-s_j^2 t}) Y_j / s_j\)（从 ODE 解出）。 - 岭回归在惩罚 λ 下的系数为：\(β̂_{RR, j}(λ) = s_j Y_j / (s_j^2 + λ)\)。 - 共轭梯度第 k 次迭代的估计量 \(β̂_{CG}(k)\) 实际上是 k 步 Krylov 子空间投影——但在正交设计下，因为所有坐标已经正交，CG 在第 \(p\) 步收敛到最小二乘解，且前 k 步与 GF 的 k 步有精确对应关系。但正交设计是平凡的，因为所有方法都会退化为按坐标缩放的坐标岭回归。

真正的非平凡最小内核：取 p=n，但 \(X\) 不是对角矩阵，但其特征值分布已知。关键在于 CG 会利用响应信息（Y）来决定搜索方向（这就是它“有监督”的本质），而 GF/RR 仅仅依赖于特征值。最小内核问题就是：对于任意固定的特征值分布和真值 β_0，CG 在有限步 k 后的预测误差，是否能被 GF 在某个变换步数 t_k = f(k) 下的预测误差所控制？ 本文的核心命题（Lemma 3.5 + Theorem 3.9）回答了这个问题：答案是可以，且 f(k) = C_0 ⋅ k，其中 C_0 依赖于设计矩阵的条件数。

核心直觉：CG 在每个迭代步中“选择”最快的搜索方向，而 GF 仅仅是线性衰减。CG 的进步步数 k 大致等效于 GF 在原来 k 倍的时间步数下的效果——这是因为 CG 在一次迭代中能消除的“特征模式”比 GF 多。这个直觉被严格化为残差多项式的上界：CG 的残差多项式 \(R^{CG}_k\) 在 \([0, x_{1,k}]\) 上被一个与 Chebyshev 多项式相关的函数控制，而 GF 的残差多项式是指数衰减的 \(e^{-x t}\)。两者通过**导数在 0 处的值（看作“有效速率”）联系起来。

三、这篇论文做了什么¶

三句话¶

研究了什么：在线性回归（固定设计，高斯噪声）下，比较共轭梯度（CG）迭代与梯度流（GF）及岭回归（RR）的整个正则化路径在预测风险上的关系。
核心工具/方法：一个非标准的显式误差分解，将 CG 第 k 步的预测误差分解为“类偏差”和“类方差”项，并用残差多项式的谱分析将其上界归约为 GF 在变换步数 \(C_0 \cdot k\) 下的对应误差。
主要结论：CG 的 oracle 停止风险（即整条路径上的最小预测风险）与 GF 的 oracle 停止风险以及 RR 的 oracle 风险至多差一个绝对常数因子（定理 3.9）。数值实验验证路径相似性。

关键设定与假设¶

完备设定（在第二节的固定设计基础上）： - 固定设计：\(X \in \mathbb{R}^{n \times p}\) 是非随机的，且 \(X^T X\) 可对角化为 \(U diag(s_1^2, \dots, s_p^2) U^T\)。噪声 \(\varepsilon \sim N(0, \sigma^2 I_n)\)。 - 目标量：预测风险（out-of-sample prediction risk）

\[R(\hat{\beta}) = \mathbb{E}\left[ \|X_0 (\hat{\beta} - \beta_0)\|^2 \mid \text{data} \right] = \|X(\hat{\beta} - \beta_0)\|^2,\]

其中 \(X_0\) 是新的协变量副本，独立于训练噪声 \(\varepsilon\)。注意条件是给定设计 \(X\)，所以风险就是训练集上的预测误差平方和（因为 \(X_0\) 与 \(X\) 同分布）。 - 主要假设：无附加的结构性假设（如稀疏性、低秩性）——这是线性模型的最一般设定。

相比已有文献的放宽/强化： - 强化：相对于 Hucker & Reiß [4]（专注逆问题，需要更精细的函数空间框架），本文的设定是标准的：线性回归，固定设计，高斯噪声。但[4]的结论更强：得到的是最优收敛率，而本文只比较路径。 - 放宽：相对于 Ali et al. [2]（几乎不用任何假设——甚至允许 \(X\) 是任意矩阵），本文没有放宽。两者的假设集基本等价。

主要结果（理论型）¶

定理 3.3（误差分解——基石）： - 陈述：CG 第 k 步的预测误差可写为：

\[\|X(\hat{\beta}_{CG,k} - \beta_0)\|^2 = \sum_{j=1}^p R^{CG}_k(s_j^2)^2 \cdot (X\beta_0)^2_j + \sigma^2 \|R^{CG}_k(X X^T) - R^{CG}_{k-1}(X X^T)\|_{HS}^2,\]

其中 \(R^{CG}_k\) 是 CG 的残差多项式（阶数 ≤ k-1）。第一项是“偏差”（用真值 \(X\beta_0\)），第二项是“方差”（用噪声，通过 Hilbert-Schmidt 范数）。 - 技术难点：这一分解是非标准的，因为 CG 的残差多项式与数据相关（因为搜索方向利用了 Y），不能直接按坐标独立解释。本文通过一个巧妙的代数恒等式绕过了这一依赖，使得 \(R^{CG}_k\) 仅依赖于 \(X^T X\) 而不依赖于 Y。这个恒等式是证明的核心技巧。

定理 3.5（CG 偏差-方差项上界）： - 陈述：结合残差多项式的导数界（来自 Hucker & Reiß [4] 的 Lemma 4.7）和标准高斯浓度不等式，得到 CG 的偏差项和方差项都可被关于 \(X X^T\) 的迹与特征值的确定性表达式上界。 - 关键：利用了 CG 残差多项式 \(R^{CG}_k\) 在 \([0, x_{1,k}]\) 上被一个“有效”速率 \(t_k\) 的 GF 残差多项式控制的事实——这正是路径比较的种子。

定理 3.9（主要结果——路径比较）： - 陈述：存在一个仅依赖于 \(X^T X\) 条件数的常数 \(C_0\)，使得对所有 \(k\)：

\[\|X(\hat{\beta}_{CG,k} - \beta_0)\|^2 \leq C_0 \cdot \|X(\hat{\beta}_{GF, t=(C_0 k) / \|X\|^2} - \beta_0)\|^2.\]

即：CG 在第 k 步的预测风险，至多是 GF 在变换步数 \(C_0 \cdot k / \|X\|^2\) 下的预测风险的常数倍。 - 推论：CG 的 oracle 风险（取整条路径的最小值）与 GF 的 oracle 风险以及 RR 的 oracle 风险（取最优 λ） 至多差一个常数因子。也就是说，CG 在统计上不比 GF 差很多。 - 解决的技术难点：如何从 CG 误差分解的不等式（定理 3.5）导出与 GF（已知显式解）的直接比较。关键步骤是将 CG 的“类偏差”项中的谱积分（关于 \(X X^T\)）与 GF 的偏差项匹配，这需要精细的谱正则化范数不等式（引理 3.7-3.8）。

证明路线与技术技巧¶

整体路线（5步逻辑主干）： 1. 谱分解：将 \(X\) 奇异值分解为 \(X = U S V^T\)，其中 \(U \in \mathbb{R}^{n \times p}\)，\(S = diag(s_1, \dots, s_p)\)，\(V \in \mathbb{R}^{p \times p}\)。将所有量在谱域中表示。 2. GF 的显式解：梯度流在时刻 t 的解为 \(X \hat{\beta}_{GF}(t) = (I - e^{-(XX^T) t})Y\)。因此其预测误差对 \(Y\) 的依赖是线性的，可用谱分解直接计算均方误差。 3. CG 的残差多项式表示：利用 CG 与 Lanczos 过程的关系，证明 \(\hat{\beta}_{CG,k} = (I - R^{CG}_k(X^T X)) (X^T X)^{-1} X^T Y\)，其中 \(R^{CG}_k\) 是次数 ≤ k-1 的多项式，满足 R_k(0)=1，且其在 \(0\) 处的导数 \(R'_k(0) = -\|X\|^2 / (C_0 k)\)。 4. 谱上界（核心引理 4.7 的改编）：将 CG 残差多项式在 \([0, x_{1,k}]\) 上被一个与 Chebyshev 多项式挂钩的函数 \(q_k\) 所控制，该函数在 \(0\) 处的行为类似于指数 \(e^{-x/\text{rate}}\)。 5. 误差分解与比较：利用定理 3.3 的误差分解，将 CG 的预测误差写成关于 \(Y\) 的二次型。然后用谱上界，将 \(\|R^{CG}_k\|\) 的范数替换为 GF 残差指数函数在变换自变量下的对应项，最终得到常数因子。

关键跳跃点： - 从 CG 的残差多项式到 Chebyshev 多项式的连接：Hucker & Reiß [4, Lemma 4.7] 证明 CG 残差多项式 \(R^{CG}_k\) 在 \([0, x_{1,k}]\)（\(x_{1,k}\) 是某迭代步的 Ritz 值上界）上被 \(|q_k(x)|\) 控制，而 \(q_k(x)\) 满足 \(q_k(0)=1, q'_k(0) = -\|X\|^2/(C_0 k)\)，且 \(|q_k(x)| \leq 1\)（相当于 GF 在输入 \(x/(C_0 k/\|X\|^2)\) 下的残差）。这一联系是非平凡的，因为 CG 多项式不是 Chebyshev 多项式，但在谱的“好部分”上行为相似。 - 从逐点谱上界到预测误差二次型的全局上界：由于 CG 误差项包含对 \(R^{CG}_k\) 的积分（trace 项），而不仅仅是点值，需要通过积分版本的不等式（引理 3.7）从逐点界推出。

技术技巧点名： - 残差多项式分析：将算法迭代转化为对残差多项式的分析，是工具的核心。 - 谱正则化范数不等式（Lemma 3.7, 3.8）：对于同一可交换矩阵族，用一个函数的算子范数（或核范数）控制另一个函数——本质是“谱函数之间的正性传递”。 - 高斯浓度不等式（来自 Koltchinskii & Lounici [7]）：用于控制样本协方差算子范数的偏差，但在固定设计下简化了。 - Chebyshev 多项式技术与 SC 迭代分析：以 Hucker & Reiß [4] 的引理为基础。

真实例子与应用¶

数值模拟（Section 4）： - 数据/场景：模拟数据——\(n=100\)，\(p=30\) 或 \(p=100\)；设计矩阵由标准高斯分布生成；\(\beta_0\) 随机。考虑两种噪声水平 \(\sigma^2=1.0\) 和 \(0.1\)。 - 怎么用：画出了 CG、GF、RR 三条风险路径曲线（作为迭代步数 k / 惩罚参数 λ 的函数），并比较了它们的 oracle 最小风险。 - 结果： - CG 路径与 GF 路径的形状非常相似，风险曲线几乎重合。 - 在 \(p > n\)（\(p=100, n=100\)）的高维情况下，GF 的风险曲线是平滑单调下降的，CG 有相似趋势但存在微小震荡。 - RR 的 oracle 风险（ridge optimal）略低于 CF，但差距很小。 - 想说明什么：验证理论预测的常数因子成立（即路径形状相似），并且显示在实际中这个常数因子很小（几乎接近 1），意味着 CG 在实际中不比 GF 差。

真实数据例子（同样在 Section 4）： - 数据/场景：著名的 Boston housing 数据集（\(n=506, p=13\)）。 - 结果：纵向比较——展示 CG、GF 和 RR 的路径，结果与模拟类似，路径高度重叠。 - 说明的结论：在典型低维回归中，CG 的正则化路径与 GF/RR 几乎不可区分，从而佐证理论比较的有效性。

总结：两个例子都旨在验证理论路径比较的正确性，而非展示一个方法优于另一个。

🔎 结论是否比证明窄¶

是，有一点窄：定理 3.9 证明的是预测风险的比较，它的常数因子边界 \(C_0\) 被有效估计（如引理中取条件数相关值），但限制在固定设计+高斯噪声下。作者在讨论中声称“CG 的 oracle 最优性与 GF 及 RR 共享”，但这需要三个前提：（a）常数 \(C_0\) 不是灾难性的（依赖于条件数）；（b）路径比较在整个路径上成立，不仅仅是在 oracle 点；（c）仅适用于预测误差，而非系数估计误差或反问题中的重建误差。结论（c）是明确的，但作者在 abstract 中未强调这一点。

四、开放问题¶

常数因子 \(C_0\) 的 sharpness 及其对随机设计的敏感度：本文中的 \(C_0\) 依赖于设计矩阵的条件数。是否可能存在一个绝对常数（独立于设计）？或者在高维随机设计（如 Marchenko-Pastur 谱）条件下，这个常数会发散？——扎根于本文引理 3.7-3.8 和定理 3.9 的常数依赖。
将路径比较推广到随机设计与高维情形：本文完全在固定设计下工作。一个确定性的下一步是：在随机设计（\(X_{ij}\) i.i.d. sub-Gaussian）下，CG 的路径是否仍能被 GF/RR 的风险上界所控制？这需要将 CG 的残差多项式分析与随机矩阵的谱理论（如 [1], [6], [7]）结合。——扎根于本文 Limitation paragraph（Section 5）：“Our analysis is limited to fixed design.”
CG 与 GF 在更强范数（如系数范数 \(\|\hat{\beta} - \beta_0\|\)）下的比较：本文只考虑了预测误差（\(X\)-范数）。能否证明 CG 在系数估计的路径上与 GF 共享类似的常数因子界？这一般更难，因涉及逆问题的不适定性。——扎根于本文全部证明使用预测误差设定，且未提及系数误差。
将“算子正则化路径比较”框架推广到非线性模型：如逻辑回归（cf. [3] 的 early-stopping 分析），此时 GF 的 ODE 显式解不再存在，CG 更复杂。能否仍然用一种“变换步数”的技巧得到路径比较？——扎根于本文的 Introduction 说“CG 因其非线性无法被标准线性比较框架处理”，但本文解决了线性情况；非线性理论上仍开放。

Maintained by 陈星宇 · Homepage · Source on GitHub