跳转至

Improving Implicit Regularization of SGD with Preconditioning for Least Square Problems

作者: Junwei Su, Chuan Wu, Le Zheng, Difan Zou
来源: SIAM Journal on Mathematics of Data Science
主题: 统计计算 / 算法
相关性: 5/10
机构绿灯: University of Hong Kong(US News 前 50,免分进入精读)
链接: 期刊页 · arXiv


一、领域脉络与小综述

这个方向是什么

本文研究的核心问题是:在最小二乘问题中,随机梯度下降(SGD)的隐式正则化效应能否通过预条件(preconditioning)得到增强,从而使其泛化性能与显式正则化的岭回归(ridge regression)相当甚至更优? 这是一个典型的"算法正则化"(algorithmic regularization)问题——即不显式地在目标函数中加入惩罚项,而是通过优化算法的内在动力学(如SGD的随机噪声、步长、迭代次数等)实现对模型复杂度的隐式控制。该方向处于优化理论、统计学习理论与高维统计的交叉地带,其成熟度处于"理论刻画已初步建立、但机制理解与算法设计仍有大量开放问题"的阶段。

发展脉络

该方向的研究脉络可以清晰地分为三条相互交织的线索:

线索一:SGD的隐式正则化与岭回归的等价性。 这是本文最直接的理论背景。Zou et al. (2021a) 的奠基性工作首次在实例层面(instance-wise)比较了SGD与岭回归的过剩风险(excessive risk),发现SGD的隐式正则化与岭回归的显式L2正则化存在深刻联系,但SGD在某些问题实例上会显著落后于岭回归。这一发现直接引出了本文的核心问题:能否通过预条件来弥补这一差距? 同时,Bartlett et al. (2019) 关于良性过拟合(benign overfitting)的工作为理解"为什么过参数化模型仍能泛化"提供了理论框架,其核心结论是:当数据协方差矩阵的本征谱在"重要方向"上集中时,最小范数插值解可以接近最优预测误差。这一结论为SGD隐式正则化的有效性提供了理论支撑。

线索二:SGD动力学的精确刻画。 Paquette et al. (2022) 通过随机微分方程(SDE)逼近,在高维极限下精确刻画了SGD的"学习轨迹"与"风险轨迹",揭示了SGD的隐式正则化实际上是一种"隐式条件化"(implicit conditioning)——即SGD在协方差矩阵本征值较大的方向上学习更快,从而隐式地优先拟合"重要方向"。这一机制与岭回归的显式收缩不同,但两者在特定条件下可以等价。本文的预条件设计正是对这一机制的主动利用:通过预条件矩阵G来主动调整SGD在不同方向上的学习速率,从而实现对隐式正则化的"定制"。

线索三:预条件技术的统计与计算效应。 预条件在优化领域是加速收敛的标准技术(Benzi, 2002),但在统计学习中的隐式正则化效应此前未被系统研究。Gonen et al. (2016) 将 sketching 预条件用于加速岭回归求解,但其目标纯粹是计算效率,而非泛化性能。本文首次将预条件与隐式正则化联系起来,揭示了预条件不仅影响收敛速度,更本质地改变了SGD所对应的隐式正则化强度与方向。

本文的位置:在上述脉络中,本文处于一个承上启下的位置。它上承 Zou et al. (2021a) 的实例级比较框架,将"预条件"作为弥合SGD与岭回归差距的机制性工具;下启 预条件SGD作为一类新的算法正则化器,其设计原则(基于协方差矩阵本征谱的逆)与经典的"统计-计算权衡"(statistical-computational tradeoff)问题产生了深刻联系——预条件本质上是在用计算资源(预条件矩阵的估计成本)换取统计效率(更优的泛化性能)。

子线索聚类

  1. SGD隐式正则化的理论刻画(Zou et al., 2021a, 2021b, 2023; Bartlett et al., 2019; Paquette et al., 2022):这一簇工作的核心是建立SGD过剩风险的精确上下界,并揭示其与数据协方差本征谱、步长、迭代次数等关键量的依赖关系。其共同的技术工具是谱分解 + 偏差-方差分解。
  2. 岭回归在高维下的精确风险分析(Tsigler & Bartlett, 2023; Dobriban & Wager, 2015; Hastie et al., 2022):这一簇工作为岭回归提供了非渐近或渐近精确的风险刻画,其核心结论是岭回归的风险由"有效秩"和"信号-噪声比"共同决定。本文的定理4.1直接建立在这一框架之上。
  3. 预条件优化算法的统计效应(Gonen et al., 2016; Woodruff, 2014; Xu et al., 2023):这一簇工作关注预条件对优化收敛速度的影响,但未涉及其对泛化性能(隐式正则化)的影响。本文填补了这一空白。

核心问题

该方向当前追问的核心问题是:

  1. SGD的隐式正则化是否"最优"? 即是否存在某种SGD变体(如预条件SGD),其泛化性能可以匹配甚至超越显式正则化的最优方法(如调参后的岭回归)?
  2. 隐式正则化的"强度"如何刻画与控制? 步长、批大小、迭代次数、预条件矩阵等算法超参数如何映射到隐式正则化的强度与方向?
  3. 隐式正则化与显式正则化的"等价性"边界在哪里? 在什么条件下,SGD的隐式正则化可以精确等价于某种显式正则化?在什么条件下这种等价性失效?

已知瓶颈:SGD的隐式正则化依赖于数据协方差矩阵的完整本征谱,而实际中只能获得有限样本估计;此外,SGD的随机噪声带来的方差项在高维下可能主导风险,如何在不增加方差的前提下增强隐式正则化是一个核心困难。

⚠️ 作者的 framing

这是作者的说法:作者将缺口 frame 为"SGD的隐式正则化可以通过预条件得到增强,从而弥合其与岭回归的性能差距"。具体而言,作者声称:(1) 现有理论(Zou et al., 2021a)表明SGD在某些实例上落后于岭回归,而这一差距源于SGD在协方差矩阵"平坦方向"上的学习不足;(2) 通过设计预条件矩阵G = (βH + I)^{-1},可以主动放大"重要方向"的信号强度,从而将SGD的隐式正则化"校准"到与岭回归相当的水平;(3) 这一预条件矩阵可以从有限无标签数据中稳健估计,从而在实践中有可行性。

被作者淡化或回避的竞争路线: - 显式正则化的直接调参:作者没有与"最优调参的岭回归"进行全面的实例级比较,而是与"固定λ的岭回归"比较。一个自然的竞争路线是:直接使用交叉验证选择最优λ的岭回归,其性能是否仍然被预条件SGD匹配? - 其他SGD变体:如带动量的SGD、Adam等自适应方法,其隐式正则化效应是否也能达到类似效果?作者在引言中提到了Adam泛化性能差的观察(Zhou et al., 2020),但未将其纳入理论比较框架。 - 核方法或随机特征方法:这些方法通过显式特征映射实现类似预条件的效果,作者未讨论与这些方法的联系。

什么明显该被引 / 该存在、却没出现在 intro 里? - 随机特征(Random Features):Rahimi & Recht (2007) 及其后续工作表明,随机特征映射可以近似核方法,其隐式正则化效应与谱变换密切相关。这与本文的预条件思想高度相关,但未被引用。 - 隐式正则化的SDE视角:除 Paquette et al. (2022) 外,Li et al. (2019) 关于SGD的SDE逼近工作也值得引用,它为理解预条件如何改变SGD的"噪声-曲率"相互作用提供了更精细的视角。 - 分布偏移下的泛化:本文的过剩风险分析假设训练与测试分布一致,但实际中预条件矩阵的估计误差可能引入分布偏移,这一鲁棒性问题未被讨论。

张力

被引工作之间未见明显对立引用。但存在一个微妙的张力:Zou et al. (2021a) 表明SGD在某些实例上落后于岭回归,而 Bartlett et al. (2019) 的良性过拟合理论则表明最小范数插值(SGD的一种极限情况)可以是最优的。本文的预条件设计可以看作是对这一张力的调和:通过预条件,SGD可以"选择"其隐式正则化的强度,从而在不同实例上都接近最优。


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

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

数据生成机制:设输入 \(x \in \mathcal{H}\)(可分希尔伯特空间,维度 \(d\) 可为无穷),输出 \(y \in \mathbb{R}\)。数据服从线性模型:

\[y = \langle x, w^* \rangle + \epsilon,\]
其中 \(w^* \in \mathcal{H}\) 是未知的真实参数,\(\epsilon\) 是均值为零、方差为 \(\sigma^2\) 的噪声,且与 \(x\) 独立。

核心记号: - \(H = \mathbb{E}[xx^\top]\):输入数据的二阶矩矩阵(协方差矩阵),是已知的总体量(在理论分析中)或可从无标签数据估计的量(在实践部分)。 - \(\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_d > 0\):\(H\) 的特征值,按降序排列。 - \(w^*\):真实参数,是要估计的未知量(非随机但未知)。 - \(\epsilon\):噪声,是随机变量。 - \(N\):训练样本量。 - \(\eta > 0\):SGD步长。 - \(G\):预条件矩阵(对称正定),是算法设计参数。 - \(eH = G^{1/2} H G^{1/2}\):预条件后的协方差矩阵,其特征值记为 \(\tilde{\lambda}_1 \ge \tilde{\lambda}_2 \ge \dots\)。 - \(\tilde{w}^* = G^{-1/2} w^*\):预条件后的真实参数。 - \(w_{sgd}(N, G; \eta)\):SGD经过 \(N\) 次迭代后的输出(tail-averaged)。 - \(w_{ridge}(N, M; \lambda)\):岭回归的解。

可观测数据: - 训练数据:\(\{(x_i, y_i)\}_{i=1}^N\),独立同分布。 - 无标签数据:\(\{\tilde{x}_i\}_{i=1}^M\),用于估计 \(H\)(在实践部分)。

参数 vs 估计量: - 参数(固定但未知):\(w^*\)、\(H\)(在理论分析中视为已知)、\(\sigma^2\)。 - 估计量(随机):\(w_{sgd}\)、\(w_{ridge}\)。 - 算法参数(用户选择):\(\eta\)、\(G\)、\(\lambda\)、\(\beta\)。

目标量(estimand):过剩风险(excess risk)

\[E(w) := \mathbb{E}_{(x,y)}[(y - \langle w, x \rangle)^2] - \mathbb{E}_{(x,y)}[(y - \langle w^*, x \rangle)^2] = \|w - w^*\|_H^2.\]
即估计量 \(w\) 与真实参数 \(w^*\) 在 \(H\)-范数下的距离平方。

第二步:最小内核

核心问题:给定 \(N\) 个样本,SGD(预条件)和岭回归的过剩风险各是多少?预条件能否让SGD的过剩风险一致地(即对所有问题实例)不超过岭回归?

最简特例:考虑 \(d=2\) 维情形,协方差矩阵为对角阵 \(H = \text{diag}(\lambda_1, \lambda_2)\),且 \(\lambda_1 \gg \lambda_2\)(即"病态"问题)。真实参数 \(w^* = (w^*_1, w^*_2)\)。

为什么这个例子是核心:Zou et al. (2021a) 发现,标准SGD(\(G=I\))的过剩风险可以分解为偏差项和方差项。偏差项在"小特征值方向"(即方向2)上衰减极慢,因为SGD在该方向上的"有效步长" \(\eta \lambda_2\) 很小。这导致SGD需要极多的迭代才能在该方向上"学到位",从而产生较大的偏差。相比之下,岭回归通过显式收缩直接控制了该方向的方差,但代价是引入偏差。预条件的思想是:通过选择 \(G\) 来放大方向2上的有效步长,从而加速SGD在该方向上的学习,减少偏差。

在这个特例下,定理4.3的证明思路: 1. 设定:取 \(G = (\beta H + I)^{-1}\),其中 \(\beta = 1/\lambda_2\)。则预条件后的特征值为 \(\tilde{\lambda}_1 = \lambda_1/(\beta\lambda_1 + 1) \approx 1/\beta\),\(\tilde{\lambda}_2 = \lambda_2/(\beta\lambda_2 + 1) = \lambda_2/2\)。此时 \(\tilde{\lambda}_1 \approx \tilde{\lambda}_2\),即预条件拉平了协方差谱。 2. SGD偏差项:在预条件后,SGD在两个方向上的有效步长 \(\eta \tilde{\lambda}_i\) 变得相近,因此偏差项在两个方向上同步衰减。通过选择 \(\eta = 1/\text{tr}(eH)\),可以保证偏差项在 \(N\) 次迭代后衰减到与岭回归偏差项相同的量级。 3. SGD方差项:预条件不改变总信号强度(引理B.1),因此方差项与标准SGD相同,且与岭回归方差项匹配。 4. 结论:通过精心选择 \(\beta\) 和 \(\eta\),可以使得 \(E(w_{sgd}) \lesssim E(w_{ridge})\)。

这个例子说明的数学本质:预条件SGD的过剩风险由预条件后的协方差谱 \(\{\tilde{\lambda}_i\}\) 决定。通过设计 \(G\),我们可以"重塑"谱,使得SGD的偏差-方差权衡与岭回归的最优权衡相匹配。定理4.3的核心就是证明:对于任何问题实例,都存在一个 \(\beta\) 使得这种匹配成立。


三、这篇论文做了什么

三句话

  1. 研究了什么问题:在最小二乘问题中,预条件能否增强SGD的隐式正则化,使其过剩风险一致地(实例-wise)匹配或优于岭回归?
  2. 核心工具/方法:建立了预条件SGD和预条件岭回归的过剩风险上/下界(定理4.1、4.2),并基于这些界构造了一个简单的预条件矩阵 \(G = (\beta H + I)^{-1}\)(定理4.3、4.4)。
  3. 主要结论:存在一个基于协方差矩阵的简单预条件设计,使得预条件SGD的过剩风险与标准岭回归相当;即使预条件矩阵是从有限无标签数据中估计的,该结论依然成立(定理4.5、4.6)。

关键设定与假设

  • 设定:线性回归,平方损失,特征 \(x\) 的协方差矩阵 \(H\) 严格正定且迹有限。SGD为单遍(single-pass)或有限遍,常数步长,tail-averaging。
  • 假设:
  • 假设3.1(正则性):\(H\) 严格正定且 \(\text{tr}(H) < \infty\)。这保证了问题的良定性。
  • 假设3.2(四阶矩有界):存在常数 \(\alpha\) 使得 \(\mathbb{E}[xx^\top A xx^\top] \preceq \alpha \text{tr}(AH) H\) 对所有PSD矩阵 \(A\) 成立。这是控制SGD方差项的技术性假设,比次高斯假设略弱。
  • 假设3.3(噪声有界):\(\mathbb{E}[\epsilon^2 xx^\top] \preceq \sigma^2 H\)。这控制了噪声对SGD方差项的贡献。
  • 与已有文献的比较:这些假设与 Zou et al. (2021b) 和 Tsigler & Bartlett (2023) 的假设基本一致,没有额外加强。因此,本文的结论是在与已有工作相同的条件下取得的,具有直接可比性。

主要结果

定理4.1(预条件岭回归过剩风险下界):给出了预条件岭回归的过剩风险下界,其形式为:

\[\text{RidgeRisk} \gtrsim \underbrace{\frac{\tilde{\lambda}^2}{N^2} \|\tilde{w}^*\|^2_{\tilde{H}^{-1}_{0:k^*}}}_{\text{Bias}} + \underbrace{\sigma^2 \left( \frac{k^*}{N} + \frac{N}{\tilde{\lambda}^2} \sum_{i>k^*} \tilde{\lambda}_i^2 \right)}_{\text{Variance}},\]
其中 \(\tilde{\lambda} = \lambda + \sum_{i>k^*} \tilde{\lambda}_i\),\(k^* = \min\{k : N \tilde{\lambda}_k \lesssim \tilde{\lambda}\}\)。这个下界表明,岭回归的风险由"有效维度" \(k^*\) 和"尾部谱" \(\sum_{i>k^*} \tilde{\lambda}_i^2\) 共同决定。

定理4.2(预条件SGD过剩风险上界):给出了预条件SGD的过剩风险上界,其形式为:

\[\text{SGDRisk} \lesssim \underbrace{\frac{1}{\eta^2 N^2} \|e^{-\eta N \tilde{H}} \tilde{w}^*\|^2_{\tilde{H}^{-1}_{0:k_1}} + \|\tilde{w}^*\|^2_{\tilde{H}_{k_1:\infty}}}_{\text{Bias}} + \underbrace{(\sigma^2 + \|\tilde{w}^*\|^2_{\tilde{H}}) \left( \frac{k_2}{N} + N\eta^2 \sum_{i>k_2} \tilde{\lambda}_i^2 \right)}_{\text{Variance}},\]
其中 \(k_1, k_2\) 是任意正整数。这个上界表明,SGD的偏差项在"前 \(k_1\) 个方向"上指数衰减,而在"尾部方向"上仅由初始误差决定;方差项则由"有效维度" \(k_2\) 和"尾部谱"决定。

定理4.3(预条件SGD vs 标准岭回归):核心定理。证明了对于任何可泛化的岭回归解(即过剩风险趋于零),都存在 \(\beta^*\) 和 \(\eta^*\) 使得预条件SGD的过剩风险满足:

\[\mathbb{E}[E(w_{sgd}(N, G; \beta^*, \eta^*))] \lesssim \mathbb{E}[E(w_{ridge}(N, I; \lambda))].\]
证明思路:选择 \(\beta^* = 1/\lambda_{k^*}\)(其中 \(k^*\) 是岭回归的有效维度),使得预条件后的谱 \(\tilde{\lambda}_i\) 在 \(i \le k^*\) 时被"拉平"到 \(\approx 1/\beta^*\),在 \(i > k^*\) 时保持不变。然后选择 \(\eta^* = 1/\text{tr}(\tilde{H})\),使得SGD的偏差项和方差项分别与岭回归的偏差项和方差项匹配。关键的技术步骤是引理B.1(总信号强度不变)和引理B.2-B.3(谱变换的性质)。

定理4.4(预条件SGD vs 预条件岭回归):将定理4.3推广到预条件岭回归。证明了对于任何预条件岭回归解,都存在对应的SGD预条件设计使其过剩风险匹配。

定理4.5、4.6(有限样本估计):当协方差矩阵 \(H\) 未知时,可以用无标签数据估计 \(\hat{H}\),并构造 \(\hat{G} = (\beta\hat{H} + I)^{-1}\)。证明了只要无标签样本量 \(M\) 足够大(\(M = \Omega(\text{tr}(H)/\lambda_{k^*})\)),预条件SGD的过剩风险依然与岭回归相当。

证明路线与技术技巧

整体路线: 1. 谱变换:将预条件SGD和预条件岭回归的问题,通过变量替换转化为标准SGD和标准岭回归在变换后的协方差矩阵 \(\tilde{H} = G^{1/2} H G^{1/2}\) 下的问题。 2. 偏差-方差分解:分别对SGD和岭回归的过剩风险进行偏差-方差分解,并利用谱分解将每个方向上的贡献分离。 3. 逐方向比较:对于每个特征方向 \(i\),比较SGD和岭回归在该方向上的偏差项和方差项。通过选择 \(\beta\) 和 \(\eta\),使得SGD在每个方向上的贡献都不超过岭回归。 4. 汇总:将所有方向上的贡献相加,得到整体的过剩风险比较。

关键引理: - 引理B.1(信号强度不变):\(\|\tilde{w}^*\|^2_{\tilde{H}} = \|w^*\|^2_H\)。这个引理保证了预条件不改变问题的"总难度"。 - 引理B.2(谱变换):\(\tilde{H}\) 与 \(H\) 有相同的特征向量,特征值满足 \(\tilde{\lambda}_i = \lambda_i / (\beta\lambda_i + 1)\)。这个引理给出了预条件对谱的精确影响。 - 引理B.3(单调性):\(\tilde{\lambda}_i\) 是 \(\lambda_i\) 的单调递增函数。这个引理保证了预条件不改变特征方向的排序。

技术技巧: - tail-averaging:使用tail-averaging而非简单平均,以降低SGD的方差项。 - 谱截断:在分析中引入 \(k^*\) 作为"有效维度"的截断点,将谱分解为"重要方向"和"尾部方向"两部分,分别处理。 - 矩阵不等式:大量使用矩阵的迹不等式和特征值不等式来控制偏差和方差项。

真实例子与应用

实验设置:高斯最小二乘问题,维度 \(d=200\),协方差矩阵特征值 \(\lambda_i = i^{-1}\) 或 \(\lambda_i = i^{-2}\),真实参数 \(w^*[i] = 1\)、\(i^{-1}\) 或 \(i^{-10}\)。比较四种方法:SGD、预条件SGD(PreSGD)、岭回归、预条件岭回归。

实验结果: - 当 \(w^*[i] = 1\)(信号均匀分布)时,标准SGD的过剩风险显著高于岭回归,而PreSGD的过剩风险与岭回归相当。 - 当 \(w^*[i] = i^{-10}\)(信号集中在少数方向)时,标准SGD已经表现良好,PreSGD进一步提升。 - PreSGD-Est(用无标签数据估计协方差矩阵)的性能与PreSGD(用真实协方差矩阵)几乎相同,说明预条件矩阵的估计是稳健的。

实验想说明什么:实验结果验证了理论预测——预条件可以弥合SGD与岭回归之间的性能差距,且这种改进在实际中可以通过有限无标签数据实现。

🔎 结论是否比证明窄

是的,存在明显的"证明窄于结论"的情况: 1. 定理4.3的证明依赖于 \(\beta^* = 1/\lambda_{k^*}\) 的精确选择,这需要知道协方差矩阵的完整谱。虽然定理4.5、4.6表明可以从有限样本估计,但估计误差对 \(\beta^*\) 选择的敏感度分析并未给出。 2. 证明中假设了 \(N\) 足够大("sufficiently large training sample size"),但未给出 \(N\) 的具体下界。在有限样本下,SGD的方差项可能比上界所暗示的更大。 3. 结论声称"comparable to standard ridge regression",但证明中只给出了上界匹配,没有给出下界匹配。这意味着可能存在PreSGD显著优于岭回归的实例,但定理没有排除PreSGD显著劣于岭回归的实例。 4. 实验部分仅考虑了高斯设计,对于非高斯设计(如重尾特征)或模型误设定情况,理论是否成立未经验证。


四、开放问题

  1. 预条件矩阵的"最优"选择:本文证明了 \(G = (\beta H + I)^{-1}\) 可以匹配岭回归,但这是否是最优的预条件?是否存在其他预条件设计可以使SGD的过剩风险严格优于岭回归?这需要建立SGD过剩风险的下界,并寻找达到下界的预条件。(扎根于:定理4.3只证明了"匹配",没有证明"超越"。)

  2. 有限样本下的精细分析:本文的定理要求 \(N\) 足够大,但未给出具体下界。在有限样本下,预条件SGD的过剩风险与岭回归的差距如何随 \(N\)、维度 \(d\)、谱衰减速度变化?能否给出非渐近的、可操作的 \(\beta^*\) 选择准则?(扎根于:定理4.3的证明中"sufficiently large"的表述。)

  3. 非线性模型的推广:本文的分析强烈依赖于最小二乘的线性结构(谱分解、偏差-方差分解)。对于广义线性模型或浅层神经网络,预条件SGD的隐式正则化效应如何刻画?是否存在类似 \(G = (\beta H + I)^{-1}\) 的简单设计?(扎根于:附录E.2中关于ReLU回归的讨论,作者仅给出了初步的扩展思路。)

  4. 预条件与自适应方法的比较:本文只比较了预条件SGD与岭回归。但实践中更常用的是Adam、AdaGrad等自适应方法,它们也可以视为一种"自适应预条件"。预条件SGD与这些方法在隐式正则化效应上的异同是什么?(扎根于:引言中对Adam泛化性能差的观察,但未展开理论分析。)

  5. 估计误差的传播:定理4.5、4.6表明预条件矩阵可以从有限无标签数据估计,但未分析估计误差如何影响过剩风险。具体地,\(\hat{H}\) 的估计误差对 \(\beta^*\) 的选择有多敏感?能否给出 \(\beta^*\) 的自适应选择方法?(扎根于:定理4.5、4.6的证明中假设 \(M\) 足够大。)

提醒:要确认上述问题是否为真 gap,建议去读该子领域近期约5篇论文的引言(例如 Zou et al. 2021a, 2021b, 2023; Paquette et al. 2022; Tsigler & Bartlett 2023 的后续工作)。如果多篇论文的引言都指向同一个问题,那很可能是共识性的 gap;如果各篇论文对同一问题的表述相互矛盾,那可能是一个更值得深挖的"张力点"。


Maintained by 陈星宇 · Homepage · Source on GitHub

评论