Central Limit Theorems for Stochastic Gradient Descent Quantile Estimators¶

作者: Ziyang Wei, Jiaqi Li, Likai Chen, Wei Biao Wu
来源: IEEE Transactions on Information Theory
主题: 数理统计 / 假设检验
相关性: 8/10
链接: 期刊页 · arXiv

一、领域脉络与小综述¶

这个方向是什么¶

这个子方向研究的是随机梯度下降（SGD）估计量的渐近分布理论，特别是当目标函数非光滑、非强凸时，SGD 迭代能否以及如何收敛到正态分布，从而为基于 SGD 的在线推断（如构造置信区间、假设检验）提供理论基础。当前该领域在光滑强凸目标下的渐近理论已相对成熟，但在非光滑（如分位数损失、Huber 损失）和非强凸设定下，理论结果仍非常有限，是当前的前沿。

发展脉络（history）¶

奠基工作：SGD 的渐近正态性。Robbins & Monro (1951) 提出随机逼近框架，奠定了 SGD 的收敛性基础。Chung (1954) 和 Sacks (1958) 在递减学习率下建立了 SGD 估计量的渐近正态性。这些工作假设目标函数光滑且强凸，学习率按特定速率衰减（如 \(\eta_t \propto 1/t\)）。
主要进展：恒定学习率下的渐近理论。Polyak & Juditsky (1992) 开创性地证明了，对于光滑强凸目标，恒定学习率 SGD 的迭代平均（Polyak-Ruppert 平均）同样具有渐近正态性，且渐近方差达到 Cramér-Rao 下界。这一结果极大地推动了 SGD 在统计推断中的应用。后续工作（如 Ruppert 1988）进一步巩固了这一方向。
当前 frontier：非光滑与非强凸设定。近年来，研究者开始将 SGD 渐近理论推广到更一般的损失函数。例如，Chen et al. (2020) 针对光滑但非强凸的目标（如过参数化线性模型）建立了 CLT。Su & Zhu (2022) 和 Fang et al. (2018) 则分别针对非光滑但强凸的损失（如支持向量机、Huber 回归）进行了探索。然而，同时非光滑且非强凸的设定——如分位数回归——仍是空白。分位数损失（pinball loss）在分位点处不可导，且整体非强凸（仅在分位点附近有线性增长），传统基于梯度平滑性或强凸性的分析工具均失效。
本文的位置：本文直接填补上述空白。作者将分位数 SGD 迭代视为一个不可约、周期且正常返的马尔可夫链，利用特征函数和平稳方程推导其平稳分布的精确形式，并证明当学习率 \(\eta \to 0\) 时，中心化与标准化的平稳分布收敛到高斯分布。这是首个针对恒定学习率分位数 SGD 估计量的 CLT 类型理论保证。

子线索聚类¶

这些被引文献大致落在两条子线索上： 1. 递减学习率 SGD 的渐近理论：以 Robbins-Monro 框架为代表，强调学习率衰减以保证几乎必然收敛，但渐近方差通常较大，且难以用于在线推断。代表工作：Robbins & Monro (1951), Chung (1954), Sacks (1958)。 2. 恒定学习率 SGD 的渐近理论：以 Polyak-Ruditsky 平均为代表，强调通过迭代平均获得最优渐近方差，且更适用于在线推断。代表工作：Polyak & Juditsky (1992), Ruppert (1988)。本文属于此线索，但将目标函数从光滑强凸推广到非光滑非强凸。

这个方向在追问的核心问题¶

SGD 估计量的渐近分布是什么？ 对于给定的损失函数和学习率调度，能否证明中心极限定理（CLT）？
如何构造有效的在线置信区间？ 基于 CLT，能否设计出递归、计算高效的推断算法，避免存储全部历史数据？
非光滑与非强凸设定下的技术障碍是什么？ 传统基于梯度 Lipschitz 或强凸性的工具（如 Lyapunov 函数、Smoothness 不等式）失效时，需要哪些新工具（如马尔可夫链分析、特征函数方法）？

⚠️ 作者的 framing¶

作者的缺口 frame：作者将缺口 frame 成“分位数损失同时非光滑且非强凸，现有 SGD 渐近理论无法直接适用”。他们强调，现有工作要么假设光滑（如 Polyak & Juditsky 1992），要么假设强凸（如 Su & Zhu 2022），而分位数损失两者都不满足。因此，本文的马尔可夫链 + 特征函数方法成为“显然的下一步”。
被淡化或回避的竞争路线：作者淡化了递减学习率路线。递减学习率 SGD 在非光滑设定下也有收敛性结果（如广义 Robbins-Monro），但作者选择恒定学习率，因为后者更适用于在线推断（无需存储全部数据，且渐近方差更易刻画）。作者未讨论Polyak-Ruppert 平均在非光滑设定下的适用性——平均操作能否平滑非光滑性？这是一个值得研究者去查的问题。
什么明显该被引 / 该存在、却没出现在 intro 里？ 作者未引用 Bach & Moulines (2013) 关于非强凸 SGD 收敛速度的工作，也未引用 Dieuleveut et al. (2017) 关于恒定学习率 SGD 在非强凸设定下渐近方差的精细刻画。这些工作虽不直接处理分位数损失，但提供了非强凸 SGD 的通用分析框架。研究者可去查这些文献，看它们是否与本文的结论互补或矛盾。

张力¶

未见明显对立引用。所有被引工作均支持“光滑/强凸是现有 SGD CLT 理论的关键假设”这一共识，本文则试图打破这一共识。

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

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

符号：
\(\theta \in \mathbb{R}\)：待估的分位数参数（为简化，本文主要考虑一维情形；多维可类似推广）。这是参数。
\(X_t \in \mathbb{R}\)：第 \(t\) 次迭代时的随机样本（来自某个分布 \(P\)）。这是随机变量。
\(\tau \in (0,1)\)：目标分位点（如 \(\tau=0.5\) 对应中位数）。这是已知常数。
\(\rho_\tau(u) = u(\tau - \mathbb{I}\{u < 0\})\)：分位数损失函数（pinball loss）。它在 \(u=0\) 处不可导。
\(\psi_\tau(u) = \tau - \mathbb{I}\{u < 0\}\)：分位数损失的次梯度（subgradient）。它在 \(u=0\) 处不连续。
\(\eta > 0\)：恒定学习率（常数）。这是算法超参数。
\(\theta_t\)：第 \(t\) 次迭代后的 SGD 估计量。这是随机过程。
\(\pi_\eta\)：SGD 迭代 \(\{\theta_t\}\) 的平稳分布（当 \(t \to \infty\) 时）。这是目标分布。
\(\mu_\eta\)：平稳分布 \(\pi_\eta\) 的均值。
\(\sigma_\eta^2\)：平稳分布 \(\pi_\eta\) 的方差。
\(\theta^*\)：真实分位数，即满足 \(P(X \le \theta^*) = \tau\) 的总体参数。这是目标 estimand。
模型：
数据生成机制：样本 \(X_t \sim P\)，独立同分布（i.i.d.）。\(P\) 是某个未知分布，其分位数 \(\theta^*\) 是我们要估计的。
统计模型：我们假设 \(P\) 在 \(\theta^*\) 附近有正的密度 \(f(\theta^*) > 0\)（这是分位数估计的标准假设，用于保证渐近正态性）。
算法模型：SGD 迭代公式为：
\[\theta_{t+1} = \theta_t - \eta \cdot \psi_\tau(\theta_t - X_{t+1}) = \theta_t - \eta \cdot \left( \tau - \mathbb{I}\{\theta_t < X_{t+1}\} \right)\]
其中 \(\psi_\tau\) 是分位数损失的次梯度。注意，由于 \(\psi_\tau\) 在 \(\theta_t = X_{t+1}\) 处不连续，\(\theta_t\) 的更新是离散跳跃的。
可观测数据：
研究者实际能观测到的是：样本序列 \(\{X_1, X_2, \dots, X_T\}\)，以及由此生成的 SGD 迭代序列 \(\{\theta_1, \theta_2, \dots, \theta_T\}\)。
想要但观测不到的是：真实分位数 \(\theta^*\)，以及 SGD 迭代的平稳分布 \(\pi_\eta\)。\(\pi_\eta\) 是理论构造，无法直接观测，只能通过 \(\theta_t\) 的长期行为来推断。

第二步：讲最小内核¶

最简特例：假设 \(\tau = 0.5\)（中位数），且样本 \(X_t\) 来自对称分布（如标准正态分布 \(N(0,1)\)）。此时真实中位数 \(\theta^* = 0\)。

在这个特例下，分位数损失退化为绝对值损失 \(\rho_{0.5}(u) = |u|/2\)，次梯度为 \(\psi_{0.5}(u) = \text{sign}(u)/2\)（取 \(0\) 处为 \(0\)）。SGD 迭代简化为：

\[\theta_{t+1} = \theta_t - \frac{\eta}{2} \cdot \text{sign}(\theta_t - X_{t+1})\]

核心思路：这个迭代可以看作一个随机游走：当 \(\theta_t > X_{t+1}\) 时，\(\theta_t\) 向下移动 \(\eta/2\)；当 \(\theta_t < X_{t+1}\) 时，向上移动 \(\eta/2\)。由于 \(X_{t+1}\) 是随机的，\(\theta_t\) 的更新方向也是随机的。

要证的命题：当 \(\eta \to 0\) 时，中心化与标准化的 \(\theta_t\)（即 \(\frac{\theta_t - \mu_\eta}{\sigma_\eta}\)）的平稳分布 \(\pi_\eta\) 收敛到标准正态分布 \(N(0,1)\)。

为什么这个特例能体现核心困难： 1. 非光滑性：\(\text{sign}\) 函数在 \(0\) 处跳跃，导致 SGD 更新不是连续的。传统基于泰勒展开或梯度 Lipschitz 的分析失效。 2. 非强凸性：绝对值损失在远离 \(0\) 处是线性的，不是二次的。这意味着 SGD 的“收缩”效应是线性的（每次更新步长固定），而不是指数衰减的。这导致 \(\theta_t\) 的方差可能不随 \(t\) 衰减，而是趋于一个常数（即平稳分布有非零方差）。 3. 马尔可夫链视角：由于更新只依赖于 \(\theta_t\) 和 \(X_{t+1}\)，且 \(X_{t+1}\) 独立于过去，\(\{\theta_t\}\) 是一个马尔可夫链。其转移核为：

\[P(\theta_{t+1} \in A \mid \theta_t = \theta) = P\left( \theta - \frac{\eta}{2} \cdot \text{sign}(\theta - X) \in A \right)\]

这个链是周期为 2 的（因为 \(\theta_t\) 的奇偶性可能影响下一步的符号），但作者证明它是正常返的，从而存在唯一的平稳分布 \(\pi_\eta\)。

关键想法：作者不直接分析 \(\theta_t\) 的分布，而是分析其特征函数 \(\phi_\eta(s) = \mathbb{E}_{\pi_\eta}[e^{is\theta}]\)。利用平稳方程（即 \(\pi_\eta\) 是转移核的不动点），可以推导出 \(\phi_\eta(s)\) 满足一个函数方程。通过求解这个方程，可以得到 \(\phi_\eta(s)\) 的精确形式（在特例下是一个简单函数），然后证明当 \(\eta \to 0\) 时，\(\phi_\eta(s/\sigma_\eta) \to e^{-s^2/2}\)，即标准正态分布的特征函数。

一句话总结：本文的核心数学贡献是：将非光滑 SGD 的渐近分布问题转化为马尔可夫链平稳分布的特征函数方程求解问题，并通过精确求解该方程（在分位数损失下）证明了 CLT。

三、这篇论文做了什么¶

三句话¶

研究了什么问题：在恒定学习率下，分位数回归 SGD 估计量的渐近分布，特别是其平稳分布是否收敛到正态分布。
核心工具 / 方法：马尔可夫链分析（不可约、周期、正常返）、特征函数与平稳方程、矩母函数与尾概率的精细界。
主要结论：证明了当学习率 \(\eta \to 0\) 时，中心化与标准化的平稳分布依分布收敛到高斯分布；并基于此提出了递归置信区间构造算法。

关键设定与假设¶

设定：
一维分位数回归（可推广到多维，但本文主要处理一维）。
恒定学习率 \(\eta\)。
样本 \(X_t\) i.i.d. 来自分布 \(P\)，其累积分布函数 \(F\) 在真实分位数 \(\theta^*\) 处连续且具有正密度 \(f(\theta^*) > 0\)。
SGD 使用分位数损失的次梯度 \(\psi_\tau(u) = \tau - \mathbb{I}\{u < 0\}\)。
关键假设：
假设 1（正则性）：\(F\) 在 \(\theta^*\) 的邻域内连续，且 \(f(\theta^*) > 0\)。这是分位数估计的标准假设，用于保证 \(\theta^*\) 是可识别的，且渐近方差存在。
假设 2（矩条件）：\(\mathbb{E}[|X|^p] < \infty\) 对某个 \(p > 0\) 成立。这是为了控制尾概率，保证平稳分布的存在性。
相比已有文献的放宽：本文不要求损失函数光滑（即梯度 Lipschitz），也不要求强凸。这是与 Polyak & Juditsky (1992) 等工作的关键区别。

主要结果¶

定理 1（平稳分布的存在性与周期性）：对于任意固定的 \(\eta > 0\)，SGD 迭代 \(\{\theta_t\}\) 构成一个不可约、周期为 2、正常返的马尔可夫链，从而存在唯一的平稳分布 \(\pi_\eta\)。该分布是循环平稳的（即 \(\theta_t\) 的分布随 \(t\) 的奇偶性周期变化，但收敛到两个不同的分布，它们的混合是平稳的）。
直觉：由于次梯度 \(\psi_\tau\) 是离散的（取值只有 \(\tau\) 和 \(\tau-1\)），\(\theta_t\) 的更新步长固定为 \(\eta\) 的倍数，导致链的奇偶性影响分布。但链是正常返的，所以长期行为由平稳分布描述。
技术难点：证明正常返性需要构造 Lyapunov 函数，但由于损失非强凸，传统二次型 Lyapunov 函数失效。作者利用分位数损失的线性增长特性，构造了一个分段线性的 Lyapunov 函数。
定理 2（平稳分布的特征函数形式）：平稳分布 \(\pi_\eta\) 的特征函数 \(\phi_\eta(s)\) 满足一个函数方程，其解可以显式写出（涉及 \(F\) 的某种变换）。在 \(F\) 对称且 \(\tau=0.5\) 的特例下，\(\phi_\eta(s)\) 有简洁的闭式。
直觉：平稳方程 \(\pi_\eta = \pi_\eta \cdot P\) 在特征函数域下变成一个线性方程，其解由 \(F\) 和 \(\eta\) 决定。
技术难点：求解该函数方程需要处理 \(\psi_\tau\) 的不连续性。作者通过将积分区域按 \(\theta\) 与 \(X\) 的大小关系拆分，将方程转化为一个差分方程，然后求解。
定理 3（中心极限定理）：设 \(\mu_\eta\) 和 \(\sigma_\eta^2\) 分别为 \(\pi_\eta\) 的均值和方差。则当 \(\eta \to 0\) 时，
\[\frac{\pi_\eta - \mu_\eta}{\sigma_\eta} \xrightarrow{d} N(0, 1)\]
即中心化与标准化的平稳分布收敛到标准正态分布。
直觉：当学习率很小时，SGD 的每次更新步长很小，\(\theta_t\) 的随机游走近似于一个扩散过程，其平稳分布近似于高斯分布。
必要条件：\(\eta \to 0\) 且 \(f(\theta^*) > 0\)。若 \(f(\theta^*) = 0\)（即密度在分位点处为零），则收敛速度可能不同，CLT 可能不成立。
技术难点：证明特征函数 \(\phi_\eta(s/\sigma_\eta) \to e^{-s^2/2}\) 需要精确控制 \(\sigma_\eta\) 的渐近行为。作者证明 \(\sigma_\eta^2 \sim \frac{\eta \tau(1-\tau)}{2f(\theta^*)}\)（与经典分位数估计的渐近方差一致），然后利用特征函数方程证明收敛。
定理 4（递归置信区间）：基于定理 3，作者提出一个递归算法来构造 \(\theta^*\) 的置信区间：在每次迭代后，利用当前 \(\theta_t\) 和估计的渐近方差更新置信区间。该算法无需存储历史数据，计算复杂度为 \(O(1)\)。
量化结论：模拟实验显示，当 \(\eta\) 足够小（如 \(\eta=0.01\)）且样本量 \(T\) 足够大（如 \(T=10^4\)）时，覆盖概率接近名义水平（如 95%）。

证明路线与技术技巧¶

整体路线（3-5 步逻辑主干）：
建立马尔可夫链结构：证明 \(\{\theta_t\}\) 是不可约、周期为 2、正常返的马尔可夫链，从而存在唯一平稳分布 \(\pi_\eta\)。这一步使用分段线性 Lyapunov 函数（Drift 条件）证明正常返性。
推导特征函数方程：利用平稳方程 \(\pi_\eta = \pi_\eta \cdot P\)，写出 \(\pi_\eta\) 的特征函数 \(\phi_\eta(s)\) 满足的积分方程。通过将积分区域按 \(\theta\) 与 \(X\) 的大小关系拆分，将积分方程转化为一个一阶线性差分方程。
求解特征函数方程：求解差分方程，得到 \(\phi_\eta(s)\) 的显式表达式（涉及 \(F\) 的某种变换）。这一步需要处理 \(F\) 的连续性，但不需要 \(F\) 的具体形式。
分析渐近行为：计算 \(\mu_\eta\) 和 \(\sigma_\eta^2\) 的渐近展开（当 \(\eta \to 0\) 时）。证明 \(\mu_\eta \to \theta^*\)，\(\sigma_\eta^2 \sim \frac{\eta \tau(1-\tau)}{2f(\theta^*)}\)。
证明 CLT：将 \(\phi_\eta(s/\sigma_\eta)\) 代入特征函数方程，利用 \(\sigma_\eta\) 的渐近行为，证明 \(\phi_\eta(s/\sigma_\eta) \to e^{-s^2/2}\)。这一步需要精细的尾概率控制（矩母函数界），以确保特征函数的收敛是 uniform 的。
关键跳跃点：
跳跃点 1：从平稳方程到特征函数方程的转化。难点在于 \(\psi_\tau\) 的不连续性导致积分方程不是标准的。作者通过引入指示函数 \(\mathbb{I}\{\theta < X\}\) 的积分表示，将方程转化为一个可处理的差分方程。
跳跃点 2：求解特征函数方程。得到的差分方程的解涉及 \(F\) 的某种累积变换，其形式并不直观。作者通过变量替换和积分换序，将解表达为 \(F\) 的简单函数。
跳跃点 3：证明 \(\sigma_\eta^2\) 的渐近行为。这需要计算 \(\pi_\eta\) 的二阶矩，而 \(\pi_\eta\) 的精确形式复杂。作者利用特征函数的二阶导数在 \(s=0\) 处的值，结合特征函数方程，推导出 \(\sigma_\eta^2\) 的渐近展开。
技术技巧点名：
马尔可夫链 Drift 条件：用于证明正常返性。构造的 Lyapunov 函数是分段线性的，利用了分位数损失的线性增长。
特征函数与平稳方程：核心技巧。将分布收敛问题转化为特征函数收敛问题，利用平稳方程得到特征函数的函数方程。
矩母函数界与尾概率控制：用于证明特征函数的一致收敛性。作者证明 \(\pi_\eta\) 的矩母函数在某个区间内有界，从而尾概率指数衰减。
差分方程求解：用于得到特征函数的显式形式。

真实例子与应用¶

本文包含模拟实验，但无真实数据例子。 - 模拟场景：生成来自标准正态分布、\(t\) 分布（厚尾）和混合分布（双峰）的样本。目标分位点 \(\tau\) 取 0.25, 0.5, 0.75。学习率 \(\eta\) 取 0.1, 0.05, 0.01。 - 方法应用：运行分位数 SGD 迭代 \(T=10^4\) 次，记录 \(\theta_t\) 序列。利用递归算法构造 95% 置信区间。 - 结果： - 当 \(\eta\) 较小时（如 0.01），\(\theta_t\) 的直方图近似正态分布，与定理 3 一致。 - 置信区间的覆盖概率接近 95%（如 93%-96%），且区间宽度随 \(T\) 增大而缩小。 - 与基于递减学习率的 SGD 相比，恒定学习率 SGD 的置信区间更窄（因为渐近方差更小）。 - 例子想说明什么：验证理论结果（CLT 成立）和算法有效性（递归置信区间可行）。同时展示恒定学习率 SGD 在在线推断中的优势（无需存储数据，计算高效）。

🔎 结论是否比证明窄¶

窄化 1：定理 3 的 CLT 是在 \(\eta \to 0\) 的渐近意义下成立的。对于固定的 \(\eta\)，平稳分布不一定接近正态。作者在模拟中展示了 \(\eta=0.1\) 时分布已有明显偏态，这符合理论预期。
窄化 2：定理 3 只证明了平稳分布的 CLT，而非有限样本 \(\theta_t\) 的 CLT。由于 \(\theta_t\) 的分布随 \(t\) 周期变化（周期 2），其有限样本分布可能偏离平稳分布。作者在模拟中展示了 \(t\) 较大时（如 \(t>1000\)），\(\theta_t\) 的分布已接近平稳分布，但未给出理论上的 mixing 速率。
窄化 3：本文主要处理一维分位数。作者在结论中声称“可推广到多维”，但未给出具体证明。多维分位数 SGD 的马尔可夫链结构更复杂（状态空间为 \(\mathbb{R}^d\)），特征函数方程也更难求解。这是一个conjecture，而非严格证明。

四、开放问题¶

多维分位数 SGD 的 CLT：本文的马尔可夫链 + 特征函数方法能否推广到 \(d > 1\) 的情形？多维分位数损失的非光滑性更强（次梯度是一个向量），平稳分布的特征函数方程将是一个偏微分方程，求解难度剧增。扎根点：论文结论部分“The theoretical tools developed in this study are of independent interest for investigating general SGD algorithms... particularly in non-strongly convex and non-smooth settings”，但未给出多维推广的具体步骤。
Polyak-Ruppert 平均在非光滑设定下的 CLT：本文研究的是原始 SGD 迭代的平稳分布。若对 \(\theta_t\) 进行 Polyak-Ruppert 平均（即 \(\bar{\theta}_T = \frac{1}{T} \sum_{t=1}^T \theta_t\)），其渐近分布是否仍为高斯？平均操作能否“平滑”非光滑性，从而得到更快的收敛速度？扎根点：作者在引言中提及 Polyak & Juditsky (1992) 的工作，但未讨论其在非光滑设定下的适用性。
非 i.i.d. 数据下的 CLT：本文假设样本 \(X_t\) 是 i.i.d. 的。若数据是时间序列（如 ARMA 过程）或马尔可夫链，分位数 SGD 的平稳分布是否仍存在？CLT 是否仍成立？扎根点：论文假设 1 要求 \(X_t\) i.i.d.，但许多实际应用（如金融数据）中数据是序列相关的。
学习率选择的自适应方法：本文的 CLT 要求 \(\eta \to 0\)，但实际中 \(\eta\) 是固定的。如何自适应地选择 \(\eta\)，使得置信区间既准确（覆盖概率接近名义水平）又窄（统计效率高）？扎根点：模拟实验中，\(\eta=0.01\) 表现良好，但 \(\eta=0.1\) 时覆盖概率偏低。作者未给出 \(\eta\) 的选择准则。

Maintained by 陈星宇 · Homepage · Source on GitHub