Weak Convergence Rates for Partial-Sum Processes of Nonlinear Stochastic Approximation¶
作者: Xiang Li, Jiadong Liang, Zhihua Zhang
主题: 数理统计 / 假设检验
相关性: 6/10
链接: https://arxiv.org/abs/2609.40338
一、领域脉络与小综述¶
-
这个方向是什么:本文属于随机逼近(Stochastic Approximation, SA)的推断理论子方向。其根本问题是:当使用 Polyak-Ruppert 平均估计器(即对迭代序列取算术平均)时,归一化的累积估计误差过程在有限样本下以多快的速度收敛到布朗运动?这直接关系到基于 SA 的统计推断(如置信区间构造)的可靠性。当前该方向的成熟度在于:定性版本的泛函中心极限定理(FCLT)已较为完善,但定量版本(即给出显式的收敛速率)尚属前沿,尤其是针对非线性 SA 与递减步长的组合。
-
发展脉络(history):
- 奠基工作:Robbins-Monro (1951) 提出 SA 框架 [45];Polyak (1990) [43, 44] 与 Ruppert (1988) [48] 独立提出平均化技巧,证明其渐近效率。这些工作确立了 SA 的渐近正态性,但未涉及路径级收敛。
- 主要进展:Sacks (1958) [49] 与 Fabian (1968) [17] 建立了 SA 的渐近正态性理论。近年来,非渐近分析兴起:Moulins & Bach (2011) [41] 给出强凸 SGD 的均值平方误差界;Chen et al. (2020) [12, 13] 建立压缩型 SA 的 Lyapunov 框架。在分布逼近方面,Anastasiou et al. (2019) [1] 与 Shao & Zhang (2021) [54] 给出了端点估计的 Berry-Esseen 界,但仅针对终端值而非整个路径。
- 当前 frontier:将端点界的定量分析推广到路径级。作者指出,已有的定量 FCLT 工作(如 Borovkov [6]、Sakhanenko [50])主要针对独立同分布(i.i.d.)部分和,而 SA 路径因递归结构引入了额外的"算法平滑"效应,无法直接套用。本文填补的正是这一空白:在鞅差噪声与幂律递减步长下,给出 Prokhorov 距离的显式有限样本上界。
-
本文位置:作者将本文定位为对 [34, Theorem 5](其前期工作)的实质性改进。对比表显示,本文在三个关键指数(噪声振荡、算法平滑、非线性余项)上均严格优于前期结果,例如算法平滑指数从 (1−α)/3 提升至 (1−α)/2。
-
子线索聚类:
- 端点定量 CLT:Anastasiou et al. [1]、Shao & Zhang [54]、Samsonov et al. [51]、Butyrin et al. [9]——关注平均估计器终端值的分布逼近,不涉及路径。
- 路径级定性 FCLT:Lee et al. [32]、Li et al. [36]、Xie & Zhang [63]——证明弱收敛但无数率。
- 路径级定量 FCLT(本文所在):Borovkov [6]、Sakhanenko [50] 处理 i.i.d. 部分和;本文首次将其推广到非线性 SA 的递归结构。
-
SA 非渐近矩界:Moulins & Bach [41]、Chen et al. [12, 13]——为本文提供迭代误差的矩控制工具。
-
⚠️ 作者的 framing(必须明确标注成"这是作者的说法"):作者将缺口 frame 为"定性 FCLT 已存在,但定量速率缺失",从而将本文定位为"显然的下一步"。具体而言,作者声称"弱收敛本身不决定逼近速率,而速率对有限样本推断至关重要"。竞争路线被淡化之处:作者回避了 Wasserstein 距离或 Kolmogorov 距离等更精细的度量(仅在引言提及 [27, 39, 58] 的 Wasserstein 分析),而选择 Prokhorov 距离——后者对路径形状不敏感,可能低估了路径级误差。明显该被引却没出现:作者未引用高维 SA 或分布式 SA 的定量 CLT 工作(如涉及通信压缩的变体),也未引用非光滑目标函数的 SA 分析。这些可能是作者刻意划定的边界,也可能是值得研究者去查的潜在 gap。
-
张力:未见明显对立引用。但存在一个微妙的张力:作者在 Assumption 5 中要求轨迹矩界(2q 阶),而该界本身通常需要更强的噪声条件(如次高斯)才能从 p 阶噪声矩推出。作者在 3.1 节末尾承认"moment-propagation argument"不平凡,并引用 [54, 55] 作为支持,但未给出该传播的完整证明。这暗示 Assumption 5 可能比 Assumption 3 更本质,值得研究者关注。
二、最核心、最简单的例子 / 数学问题¶
第一步:符号、模型、可观测数据交代清楚
- 参数 / estimand:
- \(x^\star \in \mathbb{R}^d\):目标解,满足 \(g(x^\star) = 0\),其中 \(g(x) = \mathbb{E}[H(x, \xi)]\) 是总体均值场。
- \(G \in \mathbb{R}^{d\times d}\):\(g\) 在 \(x^\star\) 处的 Jacobian,假设 \(-G\) 是 Hurwitz 矩阵(即 \(G\) 的特征值实部为正)。
- \(S \in \mathbb{R}^{d\times d}\):极限协方差矩阵,由鞅差噪声的累积条件协方差决定。
-
\(\theta \in \mathbb{R}^d\):固定的投影方向,用于将 \(d\) 维路径投影到一维。
-
随机变量 / 样本:
- \(\xi_t\):第 \(t\) 个观测,取值于可测空间 \((\mathcal{X}, \mathcal{F})\)。
- \(x_t\):第 \(t\) 次迭代的估计值,\(x_t\) 是 \(\mathcal{F}_{t-1}\)-可测的。
- \(\epsilon_t := g(x_t) - H(x_t, \xi_t)\):鞅差噪声,满足 \(\mathbb{E}[\epsilon_t | \mathcal{F}_{t-1}] = 0\)。
- \(\Delta_t := x_t - x^\star\):迭代误差。
- \(\Phi_T(r)\):归一化部分和过程,定义在 \([0,1]\) 上,在网格点 \(n/T\) 处取值为 \(\Phi_T(n/T) = \frac{1}{\sqrt{T}}\sum_{t=1}^n (x_{t+1} - x^\star)\),网格间线性插值。
-
\(\bar{x}_T = \frac{1}{T}\sum_{t=1}^T x_{t+1}\):Polyak-Ruppert 平均估计器,注意 \(\Phi_T(1) = \sqrt{T}(\bar{x}_T - x^\star)\)。
-
维数 / 样本量等指标:
- \(d\):状态空间维数(固定)。
- \(T\):迭代总步数(样本量)。
- \(\alpha \in (1/2, 1)\):步长衰减指数,\(\eta_t = \eta t^{-\alpha}\)。
- \(p > 2\):噪声的鞅差 \(p\) 阶矩界。
-
\(q \in [1, p/2]\):轨迹误差的 \(2q\) 阶矩界。
-
潜在 / 不可观测量:
- \(x^\star\)、\(G\)、\(S\) 都是未知的,需要从数据中估计。
- 噪声 \(\epsilon_t\) 的条件分布不可观测,只能通过矩条件约束。
- 布朗运动 \(Z^\star(r) = G^{-1}S^{1/2}W^\star(r)\) 是理论极限,不可观测。
第二步:最小内核
核心问题:对于固定的投影方向 \(\theta\),\(\theta^\top \Phi_T\) 的分布与 \(\theta^\top Z^\star\) 的分布之间的 Prokhorov 距离 \(d_P(\theta^\top \Phi_T, \theta^\top Z^\star)\) 以多快的速度衰减到零?
最简特例:考虑标量线性 SA(\(d=1\),\(g(x) = x\),\(G=1\)),步长 \(\eta_t = \eta t^{-\alpha}\),噪声为 i.i.d. 标准正态(\(p = \infty\))。此时迭代为 \(x_{t+1} = (1-\eta_t)x_t + \eta_t \epsilon_t\),且 \(x_1 = 0\)。
在这个特例下,迭代可以显式求解:
部分和过程在网格点 \(n/T\) 处为:
要证的命题退化成什么:证明 \(\Phi_T\) 的分布逼近标准布朗运动 \(W^\star\)。由于噪声是高斯且独立的,\(\Phi_T\) 本身是高斯过程,因此 Prokhorov 距离完全由协方差函数的逼近误差决定。具体地,需要证明:
证明怎么走: 1. 协方差计算:利用迭代的显式解,计算 \(\mathrm{Cov}(\Phi_T(n/T))\)。由于噪声独立,协方差等于系数平方和。 2. 系数渐近:利用 \(\eta_t = \eta t^{-\alpha}\),证明系数 \(\sum_{t=j}^n \eta_j \prod_{i=j+1}^t (1-\eta_i)\) 近似等于 \(\eta_j / (\eta_j + \text{累积项})\),从而得到协方差的渐近展开。 3. 误差分解:将协方差误差分解为"初始化误差"(来自 \(x_1 = 0\))和"稳态误差"(来自系数与极限的偏差)。初始化误差为 \(O(T^{-1/2})\),稳态误差为 \(O(T^{-(1-\alpha)/2})\)。 4. 高斯耦合:由于 \(\Phi_T\) 和 \(W^\star\) 都是高斯过程,Prokhorov 距离可由协方差误差直接控制(通过 Anderson 不等式或直接的分布比较)。
为什么成立:核心原因是算法平滑——每个噪声 \(\epsilon_j\) 对后续迭代的影响以 \((1-\eta_t)\) 的乘积形式衰减,其有效影响窗口长度为 \(\eta_j^{-1} \asymp j^\alpha\)。因此,部分和过程在时间 \(r\) 处的值主要由最近 \(T^\alpha\) 个噪声决定,这比独立同分布情形(所有噪声等权重)更"平滑",但也引入了额外的协方差误差。步长衰减越快(\(\alpha\) 越大),平滑效应越强,但初始化误差衰减越慢,从而产生 trade-off。
一般情形只是"加壳":对于非线性 \(g\) 和鞅差噪声,上述线性特例的证明框架不变,但需要额外处理: - 非线性余项:用 Assumption 1 的二次余项界和 Assumption 5 的轨迹矩界,控制 \(g(x_t) - G\Delta_t\) 的累积贡献(对应 \(T^{-a_{nl}}\) 项)。 - 鞅差噪声:用 Fuk-Nagaev 不等式(Lemma 4.2)和 Scott-Huggins 嵌入(Lemma 4.5)处理非高斯噪声的尾部行为(对应 \(T^{-a_{osc}}\) 项)。 - 协方差稳定化:用 Assumption 4 控制条件协方差与极限 \(S\) 的偏差(对应 \(T^{-a_{cov}}\) 项)。
三、这篇论文做了什么¶
三句话: 1. 研究了什么问题:在非线性 SA 的 Polyak-Ruppert 平均化框架下,量化归一化部分和过程到布朗运动的 Prokhorov 距离的有限样本上界,即定量泛函中心极限定理。 2. 核心工具 / 方法:将 SA 路径分解为"前导鞅部分和 + 算法平滑余项 + 非线性余项 + 初始化余项",分别用鞅的 Fuk-Nagaev 不等式、Scott-Huggins 布朗嵌入、轨迹矩界和协方差稳定化假设控制各项,最后通过概率半径的三角不等式合并。 3. 主要结论:对固定投影方向 \(\theta\),Prokhorov 距离以 \(T^{-\gamma}\sqrt{\log T}\) 的速度衰减,其中 \(\gamma = \min\{a_{cov}, a_{osc}, a_{sm}, a_{nl}\}\),四个指数分别对应协方差稳定化、有限矩噪声、算法平滑和非线性余项。
关键设定与假设: - Assumption 1(余项界与正稳定性):\(g\) 在 \(x^\star\) 附近有二次余项界,且 \(-G\) 是 Hurwitz 矩阵。这保证了迭代的线性化误差可控,且 \(G^{-1}\) 存在。 - Assumption 2(幂律步长):\(\eta_t = \eta t^{-\alpha}\),\(\alpha \in (1/2, 1)\)。这是 Polyak-Ruppert 平均化的标准条件,保证 \(\sum \eta_t = \infty\) 且 \(\sum \eta_t^2 < \infty\)。 - Assumption 3(鞅差噪声):\(\epsilon_t\) 是鞅差序列,条件 \(p\) 阶矩有界(\(p > 2\))。这比独立同分布假设弱,允许条件异方差。 - Assumption 4(协方差稳定化):累积条件协方差以 \(T^{-3\gamma}\) 的速率逼近线性轮廓 \(rS\)。这是本文新引入的假设,用于控制前导鞅部分和的协方差误差。 - Assumption 5(轨迹矩界):\(\mathbb{E}[\|\Delta_t\|^{2q}] \lesssim \eta_t^q\),\(q \in [1, p/2]\)。这比仅要求二阶矩更强,用于控制非线性余项的累积。
相比已有文献的放宽/强化: - 放宽:噪声允许鞅差而非独立同分布;步长允许幂律衰减而非固定步长。 - 强化:要求轨迹矩界(Assumption 5)和协方差稳定化(Assumption 4),这些在定性 FCLT 中不需要,但为获得速率所必需。
主要结果: - Theorem 3.1(上界):在 Assumptions 1-5 下,对固定 \(\theta\),\(d_P(\theta^\top \Phi_T, \theta^\top Z^\star) \lesssim T^{-\gamma}\sqrt{\log T}\),其中 \(\gamma = \min\{a_{cov}, a_{osc}, a_{sm}, a_{nl}\}\)。证明分四步: 1. 初始化余项:\(\psi_0\) 以 \(O(T^{-1/2})\) 衰减(Lemma 4.7 的确定性界)。 2. 非线性余项:\(\psi_1\) 的 \(L^q\) 范数以 \(T^{-a_{nl}}\) 衰减,其中 \(a_{nl} = (\alpha - 1/2)q/(q+1)\)。关键是用 Assumption 5 控制 \(\|\Delta_t\|^2\) 的矩,再用 Minkowski 不等式求和。 3. 固定端点余项:\(\psi_2\) 的 \(L^q\) 范数以 \(T^{-a_{osc}}\) 衰减,其中 \(a_{osc} = (p-2)/(2(p+1))\)。关键是用 Fuk-Nagaev 不等式(Lemma 4.2)控制鞅的最大值。 4. 变端点余项:\(\psi_3\) 的 \(L^q\) 范数以 \(T^{-a_{sm}}\sqrt{\log T}\) 衰减,其中 \(a_{sm} = (1-\alpha)/2\)。关键是用 Scott-Huggins 嵌入(Lemma 4.5)和布朗模的尾部界(Lemma 4.6)。 最后用概率半径的次可加性(Lemma 4.1)合并四项。
- Theorem 3.3(协方差下界):构造停止布朗运动,使累积条件协方差在 \(T^{-3\gamma}\) 尺度上偏离线性轮廓,但 Prokhorov 距离仍为 \(T^{-\gamma}\)。这说明协方差稳定化假设的指数 \(a_{cov}\) 是紧的。
- Theorem 3.4(有限矩下界):构造 i.i.d. 噪声,其 \(p\) 阶矩有界但 \(p+\delta\) 阶矩无界,使 Prokhorov 距离为 \(T^{-a_{osc}}\)。这说明有限矩假设的指数 \(a_{osc}\) 是紧的。
- Theorem 3.5(算法平滑下界):标量高斯线性 SA 模型,Prokhorov 距离为 \(T^{-a_{sm}}\sqrt{\log T}\)。这说明算法平滑项的指数和对数因子都是紧的。
- Theorem 3.6(非线性下界):构造非线性 \(g\),使 Prokhorov 距离为 \(T^{-a_{nl}}\)。这说明非线性余项的指数是紧的。
- Theorem 3.7(总下界):将四个下界模型并入一个联合类,得到总下界为四项之和,与上界匹配。
证明路线与技术技巧: - 整体路线:先建立路径分解(公式 31),将 \(\Phi_T\) 分解为前导鞅部分和 \(G^{-1}M_T\) 与四个余项。然后分别控制每个余项的概率半径,最后用三角不等式合并。 - 关键技巧: 1. 概率半径(probability radius):定义 \(\mathrm{ed}(Y) = \inf\{\epsilon : P(\|Y\| > \epsilon) \le \epsilon\}\),将 Prokhorov 距离转化为对误差过程的概率控制。Lemma 4.1 给出了 \(\mathrm{ed}\) 的次可加性和与 Prokhorov 距离的关系。 2. Fuk-Nagaev 不等式(Lemma 4.2):用于控制鞅的最大值,得到 \(T^{-a_{osc}}\) 的尾部界。这是处理有限矩噪声的核心工具。 3. Scott-Huggins 嵌入(Lemma 4.5):将鞅嵌入布朗运动,使得鞅部分和可以表示为布朗运动在随机时间处的值,从而将问题转化为布朗模的估计。 4. 自适应分块(Lemma 4.10):将时间轴分成块,块内用鞅的矩界,块间用收缩性,得到 \(T^{-a_{sm}}\sqrt{\log T}\) 的界。这是处理算法平滑的关键。 5. 布朗模尾部界(Lemma 4.6):控制布朗运动在短时间间隔内的最大增量,用于处理嵌入时间的偏差。
真实例子与应用:本文为纯理论论文,无真实数据例子。但 Theorem 3.5 中的标量高斯线性 SA 模型可视为一个"玩具例子",用于展示算法平滑效应的本质。该模型在强化学习(如 TD 学习)和在线优化中有直接对应。
🔎 结论是否比证明窄: - Theorem 3.1 的常数依赖:证明中常数 \(C\) 依赖 \(d\)、\(\theta\)、\(G\)、\(S\) 以及矩常数,但论文未给出显式依赖形式。作者在 3.1 节末尾承认"dimension-free guarantee"未建立,这比定理陈述的"固定 \(d\)"更窄。 - Theorem 3.6 的局限:作者在 3.2.4 节明确说明,非线性下界的构造中,局部正则参数随 \(T\) 变化,因此"does not match the upper bound in the same sense"。这意味着非线性项的紧性只在特定意义下成立,比定理陈述的"matching"更窄。 - Assumption 5 的验证:作者在 3.1 节末尾承认,从 Assumption 3 推出 Assumption 5 需要"moment-propagation argument",但该论证未在论文中给出,仅引用 [54, 55]。这意味着定理的适用条件可能比陈述的更严格。
四、开放问题¶
-
维度依赖:Theorem 3.1 的常数依赖 \(d\),但未给出显式形式。能否建立维度一致的(dimension-free)上界?这在高维 SA(如深度学习的 SGD)中至关重要。扎根于 Theorem 3.1 陈述后的讨论:"The proof does not track these dependencies sharply. In particular, the displayed powers of T do not constitute a dimension-free guarantee or a bound uniform over all projection directions."
-
最优速率:上界中的四个指数是否同时达到?作者证明了每个指数单独紧,但未证明联合紧性。是否存在一个模型使 Prokhorov 距离同时达到四项之和?扎根于 Theorem 3.7 的证明:"Combining the four lower bounds through (20) gives the following theorem."——联合紧性未讨论。
-
矩传播的严格化:Assumption 5 的验证需要从噪声矩到轨迹矩的传播论证。作者引用 [54, 55] 但未给出完整证明。能否在更弱的条件下(如 \(p\) 阶矩而非 \(2q\) 阶矩)建立该传播?扎根于 3.1 节末尾:"This requires a moment-propagation argument under suitable stability conditions. It does not follow from independence alone."
-
更精细的度量:Prokhorov 距离对路径形状不敏感。能否在 Wasserstein 距离或 Kolmogorov-Smirnov 距离下建立类似的速率?作者在引言中提及 [27, 39, 58] 的 Wasserstein 分析,但未将其与本文的 Prokhorov 结果对比。扎根于引言:"Recent Wasserstein analyses also treat nonlinear SA [27], asynchronous averaged Q-learning [39], and the last SA iterate [58]."
-
自适应步长:本文假设步长 \(\eta_t = \eta t^{-\alpha}\) 是确定性的。对于自适应步长(如 AdaGrad、Adam),算法平滑效应如何变化?扎根于 Assumption 2 的陈述:"For constants \(\eta > 0\) and \(\alpha \in (1/2, 1)\), the step sizes are \(\eta_t = \eta t^{-\alpha}\)."
-
下界模型的统一性:四个下界模型分别隔离不同误差源,但未在单一模型中同时出现。是否存在一个自然模型(如带重尾噪声的非线性 SA)使所有误差源同时活跃?扎根于 Theorem 3.7 的证明:"Here \(\mathcal{C}_{cov}\) is understood to be empty when \(a_{cov} \ge \min\{a_{osc}, a_{sm}\}\)..."——联合紧性未讨论。
给研究者的提示:若要确认上述问题是否为真 gap,建议阅读以下近期工作(约 5 篇)的引言部分: - [34] Li, Liang, Zhang (2023) 的 arXiv 版本(本文的前期工作,可对比改进幅度) - [51] Samsonov et al. (2024) 关于线性 SA 的 Berry-Esseen 界 - [27] Kong & Srikant (2026) 关于非线性 SA 的 Wasserstein 界 - [55] Sheshukova et al. (2026) 关于非线性平均 SGD 的高斯逼近 - [9] Butyrin et al. (2025) 关于线性 SA 的改进 CLT
若这些工作的引言都指向"定量路径级 FCLT 尚未解决",则问题 1-2 很可能是共识性 gap;若互相矛盾(如有的声称 Wasserstein 界更优),则问题 4 可能是机会。
Maintained by 陈星宇 · Homepage · Source on GitHub