Gradient descent inference in empirical risk minimization

作者: Qiyang Han, Xiaocong Xu
主题: 高维统计 / 随机矩阵
相关性: 7/10
链接: https://doi.org/10.1214/25-aos2600

---

一、领域脉络与小综述

• 这个方向是什么：本文研究的是高维统计中一个基础且核心的问题：当我们用迭代算法（如梯度下降）求解经验风险最小化（ERM）问题时，算法迭代的中间产物（即迭代点本身）能否直接用于对未知参数进行统计推断？传统观点认为，只有算法收敛到（正则化）经验风险最小化器后，才能基于该估计量进行推断。本文挑战了这一观点，试图证明在"均值场"（mean-field）或"比例"（proportional）极限下，算法迭代的每一步本身都携带了足够的信息，经过适当的去偏处理后，可以构造出渐近正态的估计量，从而进行有效的统计推断。这个方向的核心张力在于：算法的"计算轨迹"（computational trajectory）与"统计最优性"（statistical optimality）之间是否存在本质的联系？本文的答案是肯定的，且这种联系可以通过状态演化（state evolution）理论精确刻画。

• 发展脉络（history）：

  • 奠基工作：该方向的根基在于近似消息传递（AMP） 算法及其状态演化理论。[BM11, JM13, BLM15, BMN20] 等文献为理解迭代算法在高维随机问题中的行为提供了精确的渐近刻画工具。这些工作表明，AMP 类算法的迭代轨迹可以被一个标量参数（如均方误差）的确定性递推所描述，即状态演化。本文作者在 [Han25a] 中将这些工具推广到了更一般的一阶方法（GFOM），为本文的理论提供了直接基础。
  • 主要进展：在凸正则化估计的推断方面，[JM14a, JM14b, MM21, CMW23, BZ23, Bel25] 等文献建立了"去偏"（debiasing）框架，证明了通过沿损失函数梯度方向进行一阶修正，可以将正则化估计量转化为渐近正态的估计量，从而进行推断。这些工作为"去偏"这一核心思想提供了理论依据。本文作者在 [Han25a] 中建立的 GFOM 状态演化理论，是本文的直接技术起点。
  • 当前 frontier：将推断从"最终估计量"拓展到"算法轨迹"是当前的一个前沿方向。[BT24, TB24] 等近期工作开始探索在特定模型（如线性模型）下，利用梯度下降迭代进行推断的可能性。本文在此基础上，将这一思路推广到了更一般的非凸损失和非高斯数据设定，并提供了非渐近的误差界。
  • 本文的位置：本文站在上述两条线的交汇点：它利用 [Han25a] 的 GFOM 状态演化理论，将 [BT24, TB24] 中"利用迭代进行推断"的思想推广到了更一般的模型（1.1），并系统地解决了去偏系数的估计问题，从而提出了一个通用的、数据驱动的推断框架。

• 子线索聚类：

  • 算法动力学与状态演化：这条线索关注迭代算法的宏观行为，用低维状态变量（如误差的均方）来描述高维迭代的统计特性。代表工作包括 [BM11, BLM15, BMN20, Fan22, BHX25, Han25a]。本文的理论贡献主要集中于此。
  • 高维去偏推断：这条线索关注如何从有偏的正则化估计量出发，构造无偏或渐近无偏的估计量以进行推断。代表工作包括 [JM14a, JM14b, MM21, CMW23, BZ23, Bel25]。本文的推断框架（Algorithm 1）是这一思想在迭代算法上的延伸。
  • 迭代算法的隐式正则化与泛化：这条线索关注算法早停（early stopping）带来的正则化效应，以及迭代轨迹的泛化误差。[ADT20] 是其中的代表。本文的泛化误差估计（Theorem 3.3）与此相关，但更侧重于推断而非预测。

• 这个方向在追问的核心问题：

  1. 迭代轨迹的分布刻画：在高维比例极限下，梯度下降的迭代点（或其线性变换）的联合分布是什么？本文的核心定理（Theorem 2.2）回答了这个问题，指出其分布由高斯过程（由状态演化参数决定）所刻画。
  2. 去偏的可行性：如何利用可观测的数据（梯度、迭代点）构造出去偏系数，使得去偏后的迭代点渐近正态？本文的 Algorithm 1 和 Theorem 3.1 回答了这个问题。
  3. 推断与泛化的关系：沿着算法轨迹，统计推断的质量（如置信区间长度）与泛化误差如何变化？它们的最优点是否一致？本文通过数值实验（Section 6）探讨了这个问题，并指出二者不一定对齐。

• ⚠️ 作者的 framing（必须明确标注成"这是作者的说法"）：作者将缺口 frame 成：现有的去偏推断方法（如 [JM14a, JM14b, MM21, CMW23, BZ23, Bel25]）主要针对凸正则化估计量，且通常需要算法收敛到最优解。然而，在实际应用中，尤其是在非凸问题中，算法往往不会收敛，或者我们有意提前停止（early stopping）以避免过拟合。因此，作者认为，一个自然的、尚未被系统解决的问题是：能否直接利用未收敛的迭代点进行推断？ 本文声称给出了肯定的答案。作者淡化了其他竞争路线，例如：

  • 基于收敛后估计量的传统推断：作者认为这需要算法收敛，且在处理非凸损失时存在困难。
  • 完全贝叶斯方法：作者没有讨论，但这类方法通常计算代价高昂，且对先验敏感。
  • 其他基于轨迹的推断方法：如 [BT24, TB24]，作者认为它们局限于特定模型（如线性模型），而本文的方法更通用。 什么明显该被引 / 该存在、却没出现在 intro 里？ 作者在讨论非凸优化时，没有引用关于高维非凸 landscape 的几何性质的文献（如 [SQW16] 等关于 strict saddle 性质的工作），这些工作为梯度下降在非凸问题中的收敛性提供了理论基础。此外，关于随机梯度下降（SGD）的隐式正则化的文献（如 [NTS15]）也未被提及，尽管本文的框架在原理上可以扩展到 SGD。

• 张力：被引文献之间未见明显对立。[Han25a] 的理论是本文的直接基础，而 [BT24, TB24] 是本文的直接竞争对手。本文与 [BT24, TB24] 的张力在于：后者可能更早地提出了"利用迭代推断"的想法，但本文声称在通用性（非凸损失、非高斯数据）和理论深度（非渐近、逐点分布刻画）上更胜一筹。这是一个"谁更一般、谁更深入"的竞争，而非根本性的矛盾。

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

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

• 符号：

  • 参数 / 估计目标：
  • µ* ∈ Rⁿ：未知的真实信号向量，是推断的目标。
  • µ⁽ᵗ⁾ ∈ Rⁿ：梯度下降算法在第 t 步产生的迭代点（随机向量）。
  • µ⁽ᵗ⁾_db ∈ Rⁿ：去偏后的迭代点，是用于推断的最终估计量。
  • b⁽ᵗ⁾_db ∈ R：去偏迭代点的渐近均值中的乘数（bias 系数）。
  • σ⁽ᵗ⁾_db ∈ R：去偏迭代点的渐近标准差。
  • 随机变量 / 样本：
  • A ∈ R^{m×n}：设计矩阵，行是协变量 Aᵢ，其元素独立、零均值、次高斯，方差为 1/n。
  • Y ∈ R^m：响应向量，Yᵢ 由模型 Yᵢ = F(⟨Aᵢ, µ*⟩, ξᵢ) 生成。
  • ξ ∈ R^m：噪声向量，独立于 A。
  • Z⁽ᵗ⁾ ∈ R^m、W⁽ᵗ⁾ ∈ Rⁿ：状态演化理论中的高斯随机向量，用于描述迭代点的分布。
  • 指标 / 维度：
  • n：信号维度。
  • m：样本量。
  • t：迭代次数。
  • φ = m/n：样本量与维度之比（固定常数，即比例极限）。
  • 函数 / 算子：
  • F: R² → R：模型函数，连接线性预测器和噪声。
  • L: R² → R：损失函数，L(x, y) 衡量预测值 x 与真实值 y 的差异。
  • f: R → R：正则化函数。
  • prox_f(·)：近端算子，prox_f(x) = argmin_z { ||x-z||²/2 + f(z) }。
  • ∂₁L(x, y)：损失函数关于第一个参数（预测值）的偏导数。
  • τ⁽ᵗ⁾、ρ⁽ᵗ⁾：状态演化中的系数矩阵，刻画迭代点之间的相关性。

• 模型： 数据生成机制为 Yᵢ = F(⟨Aᵢ, µ*⟩, ξᵢ)。这是一个半参数模型，F 的具体形式可以未知，但需要满足一定的光滑性条件。观测数据为 (A, Y)，目标是推断 µ*。

• 可观测数据： 研究者能观测到的是设计矩阵 A、响应向量 Y，以及算法运行过程中产生的所有迭代点 {µ⁽ˢ⁾} 和对应的损失梯度 {∂₁L(Aµ⁽ˢ⁾, Y)}。观测不到的是真实信号 µ*、噪声 ξ，以及状态演化中的"真实"参数（如 τ⁽ᵗ⁾、ρ⁽ᵗ⁾、δ⁽ᵗ⁾），这些参数需要通过 Algorithm 1 从数据中估计。

• 第二步：讲最小内核

本文的最小内核可以归结为以下三个递推关系（以线性模型、平方损失、无正则化为例，即 F(x, ξ) = x + ξ, L(x, y) = (x-y)²/2, f = 0）：

1. 迭代更新：µ⁽ᵗ⁾ = µ⁽ᵗ⁻¹⁾ - η Aᵀ(Aµ⁽ᵗ⁻¹⁾ - Y)。这是最朴素的梯度下降。

2. 状态演化（分布刻画）：在高维极限下，Aµ⁽ᵗ⁾ 和 µ⁽ᵗ⁾ 的联合分布可以由一个高斯过程精确描述。具体来说，存在高斯向量 Z⁽ᵗ⁾ 和 W⁽ᵗ⁾，使得对任意"足够光滑"的测试函数，有：

   • Aµ⁽ᵗ⁾ ≈ Z⁽ᵗ⁾，其中 Z⁽ᵗ⁾ 的协方差由矩阵 τ⁽ᵗ⁾ 决定。
   • µ⁽ᵗ⁾ ≈ W⁽ᵗ⁾ + δ⁽ᵗ⁾µ*，其中 W⁽ᵗ⁾ 是独立于 µ* 的高斯噪声，δ⁽ᵗ⁾ 是信号保留系数。 这里的 τ⁽ᵗ⁾ 和 δ⁽ᵗ⁾ 就是状态演化参数，它们通过一个确定性的递推关系（由损失函数和数据的统计量决定）从初始值开始演化。

3. 去偏（Debiasing）：由于 µ⁽ᵗ⁾ 是 µ* 的"收缩"版本（δ⁽ᵗ⁾ < 1），直接使用它进行推断会产生偏差。本文的核心思想是，通过减去过去所有迭代点的损失梯度方向的线性组合，可以消除这个偏差： µ⁽ᵗ⁾_db = µ⁽ᵗ⁾ + Σ_{s=1}^{t} ω_{t,s} · η Aᵀ ∂₁L(Aµ⁽ˢ⁻¹⁾, Y)， 其中系数 ω_{t,s} 正是由状态演化参数 τ⁽ᵗ⁾ 和 ρ⁽ᵗ⁾ 构造的（即 ω⁽ᵗ⁾ = (τ⁽ᵗ⁾)⁻¹）。经过这样的修正后，µ⁽ᵗ⁾_db 在分布上逼近 µ* + σ⁽ᵗ⁾_db · Z，其中 Z 是标准高斯向量，从而实现了渐近正态性。

这个最小内核说明了什么？ 它说明，梯度下降的每一步迭代，都可以看作是对真实信号 µ* 的一个"有偏但信息丰富"的观测。状态演化理论精确地告诉我们这个偏差有多大（由 δ⁽ᵗ⁾ 刻画），以及噪声的分布是什么（由 τ⁽ᵗ⁾ 刻画）。去偏过程则是利用这些信息，通过一个可计算的线性变换，将"有偏观测"转化为"无偏观测"。因此，统计推断可以沿着算法的轨迹进行，而不必等待算法收敛。

三、这篇论文做了什么

• 三句话：

  1. 研究了什么问题：在高维均值场极限下，如何直接利用（可能未收敛的）梯度下降迭代点对 ERM 问题中的未知信号 µ* 进行统计推断（构造置信区间等）。
  2. 核心工具 / 方法：基于 [Han25a] 的 GFM 状态演化理论，建立了迭代点及其去偏统计量的非渐近联合高斯刻画；提出了一个数据驱动的"梯度下降推断算法"（Algorithm 1），用于估计状态演化参数（即去偏系数）。
  3. 主要结论：证明了去偏后的梯度下降迭代点 µ⁽ᵗ⁾_db 在分布上逼近均值为 b⁽ᵗ⁾_db · µ*、方差为 (σ⁽ᵗ⁾_db)²Iₙ 的高斯分布（Theorem 2.3, 3.2），从而可以构造渐近有效的置信区间。该框架适用于凸和非凸损失，且对模型误设定具有鲁棒性。同时，还提供了每一步迭代的泛化误差估计（Theorem 3.3）。

• 关键设定与假设：

  • 均值场（比例）极限：m/n → φ ∈ (0, ∞)，这是整个理论成立的基石。
  • 数据假设：设计矩阵 A 的行是独立同分布的次高斯随机向量，协方差为 Iₙ/n。噪声 ξ 独立于 A。
  • 光滑性假设：损失函数 L 和模型函数 F 需要满足一定的光滑性条件（如三阶导数有界），以保证状态演化理论的适用性。
  • 初始化假设：初始化 µ⁽⁰⁾ 可以是任意的，但需要与 µ* 独立，且其范数有界。
  • 正则化：允许存在近端正则化项 f，但理论主要针对光滑或非光滑但可分解的正则化器。
  • 相比已有文献的放宽/强化：相比 [BT24, TB24]，本文放宽了对损失函数和数据的限制（允许非高斯、非凸），并提供了非渐近的误差界。相比 [CCM21, GTM+24] 等纯算法分析，本文强化了结论，将其用于统计推断，而不仅仅是预测误差分析。

• 主要结果：

  • Theorem 2.2（核心分布刻画）：给出了 Aµ⁽ᵗ⁾ 和 µ⁽ᵗ⁾ 的联合分布与高斯过程 Z⁽ᵗ⁾、W⁽ᵗ⁾ 的逼近误差。这个误差以 n^{-c} 的速度衰减，其中 c 依赖于问题的维度和光滑性参数。这个定理是后续所有推断结果的基础。
  • Theorem 2.3（去偏迭代的渐近正态性）：证明了去偏后的迭代点 µ⁽ᵗ⁾_db 在分布上逼近 N(b⁽ᵗ⁾_db · µ*, (σ⁽ᵗ⁾_db)²Iₙ)。这个结果直接给出了构造置信区间的方法。
  • Theorem 3.1（算法一致性）：证明了 Algorithm 1 输出的估计量 bτ⁽ᵗ⁾、bρ⁽ᵗ⁾ 以高概率逼近真实的状态演化参数 τ⁽ᵗ⁾、ρ⁽ᵗ⁾。这是将理论结果转化为实际推断算法的关键一步。
  • Theorem 3.3（泛化误差估计）：证明了提出的泛化误差估计量 bE⁽ᵗ⁾_H 以高概率逼近真实的泛化误差 E⁽ᵗ⁾_H。这为模型选择（如早停）提供了理论依据。
  • Proposition 4.3 & 5.4（特例简化）：在平方损失线性模型和平方损失广义线性模型中，给出了状态演化参数和偏差项的显式表达式，使得推断过程更加简洁。

• 证明路线与技术技巧：

  • 整体路线：
    1. 问题转化：将梯度下降迭代（2.1）重写为 GFV 的标准形式（见 Theorem 2.2 证明的 Step 1），使其满足 [Han25a] 中定理的条件。
    2. 状态演化：利用 [Han25a] 的核心定理，得到迭代点的高斯刻画（即 (2.3)）。
    3. 去偏构造：通过分析状态演化方程，发现去偏系数恰好是状态演化参数 τ⁽ᵗ⁾ 的逆，从而构造出 µ⁽ᵗ⁾_db。
    4. 误差控制：利用 Theorem 2.2 的误差界，控制去偏过程中的累积误差，最终得到 Theorem 2.3 的结论。
    5. 算法设计：将状态演化参数的递推关系转化为 Algorithm 1 中的估计步骤，并利用类似的技巧证明其一致性（Theorem 3.1）。
  • 关键跳跃点：
    • 从"迭代轨迹"到"高斯过程"的跳跃：这是整个理论的基石，直接引用 [Han25a] 的结论。难点在于验证本文的算法（2.1）满足 [Han25a] 中 GFV 的抽象条件。
    • 从"分布刻画"到"去偏"的跳跃：难点在于发现 ω⁽ᵗ⁾ = (τ⁽ᵗ⁾)⁻¹ 这个关键联系。这需要对状态演化方程有深刻的理解。
    • 从"理论参数"到"数据驱动估计"的跳跃：难点在于设计出 Algorithm 1 中的递推估计，并证明其误差可控。这涉及到对状态演化方程中各个量的可观测替代物的构造。
  • 技术技巧点名：
    • 状态演化（State Evolution）：核心工具，用于描述迭代轨迹的分布。
    • 高斯插值 / 条件高斯技术：用于证明迭代点与高斯过程的逼近。
    • Lindeberg 交换技巧：用于处理非高斯数据，证明 universality（见 Lemma B.1）。
    • 截断与集中不等式：用于控制估计误差，得到非渐近界。
    • 矩阵扰动分析：用于分析状态演化参数估计的误差传播。

• 真实例子与应用：

  • 线性回归：平方损失，高斯或次高斯设计。验证了去偏梯度下降与去偏 Lasso 在分布上的一致性（Proposition 4.3）。
  • 单指标模型：非凸损失，验证了方法在非凸问题中的有效性（Section 4）。
  • 广义逻辑回归：验证了方法在分类问题中的有效性，并展示了使用误设的平方损失带来的计算优势（Section 5）。
  • 数值实验：在多种设计（高斯、t分布、伯努利）和多种损失（平方、逻辑、Huber）下验证了置信区间的覆盖率和计算效率，并与 LOOCV 进行了对比，展示了显著的速度优势（Section 6, Appendix C）。

• 🔎 结论是否比证明窄：

  • 是的，存在这种情况。作者在摘要和引言中声称方法适用于"广义逻辑回归"（Example 1.2），但 Theorem 5.1 的证明依赖于一个关键的平滑化技巧，且对损失函数和噪声分布有额外的技术假设（如 (5.2)）。作者在 Remark 2 和 Section 5 中承认，对于非光滑的损失（如 hinge loss），理论需要额外的处理。因此，"广义逻辑回归"的结论是在特定技术条件下证明的，并非对所有逻辑回归变体都无条件成立。
  • 另一个例子是，作者在引言中强调方法的"非渐近"特性，但 Theorem 2.2 的误差界依赖于常数 c_t，这个常数对 t 的依赖是指数级的（虽然作者声称可以显式追踪，但未给出具体形式）。因此，"非渐近"的实用性在迭代次数很大时可能受限，尽管作者在数值实验中展示了良好的有限样本表现。

四、开放问题

1. 随机梯度下降（SGD）的扩展：本文的理论框架针对确定性梯度下降（或近端梯度下降）。将状态演化推断推广到小批量 SGD 或带噪声的梯度下降，是一个自然且重要的开放问题。这需要处理额外的随机性来源，并可能改变状态演化的形式。（扎根于 Section 1.6.2 中对 SGD 文献的讨论，以及作者在结论中未明确提及 SGD。）
2. 自适应与加速方法的推断：本文的方法是否可以扩展到 Adam、Nesterov 加速梯度等自适应或加速算法？这些算法的状态演化方程更为复杂，其去偏系数的估计可能更具挑战性。（扎根于作者在 Section 1.6.1 中仅对比了标准 GD 与 AMP，未讨论加速方法。）
3. 更一般的模型误设定：本文的鲁棒性结果（Theorem 3.3）主要针对损失函数与模型不匹配的情况。如果数据生成过程本身偏离了假设的独立同分布次高斯结构（例如，存在相关设计或重尾噪声），状态演化理论是否依然成立？这是一个重要的开放问题。（扎根于作者在 Section 1.4 中声称的"对模型误设定的鲁棒性"，但未明确其边界。）
4. 高维推断的最优性：本文的去偏方法是否达到了半参数有效性的下界？即，基于去偏梯度下降构造的置信区间是否是最短的？这需要与半参数效率理论进行更深入的对比。（扎根于作者在 Section 1.1 中与去偏 Lasso 的对比，但未讨论效率最优性。）
5. 超参数（步长、正则化）的选择：本文的理论对步长 η 和正则化参数 λ 有一定的条件（如 (A3)）。如何在实际中数据自适应地选择这些超参数，以优化推断质量（如置信区间长度），是一个实用且开放的问题。（扎根于 Algorithm 1 的输入参数和 Section 6 中固定步长的实验设置。）

提示：要确认上述问题是否为真 gap，建议去读近 2-3 年 NeurIPS、COLT、AoS 上关于"算法轨迹推断"或"状态演化"的论文，看它们是否已经解决了这些问题。如果多篇论文都指向同一问题，那它很可能是一个共识性的开放问题。

---

Maintained by 陈星宇 · Homepage · Source on GitHub

评论