随机函数的 Lipschitz 强大数定律

论文信息

标题: Lipschitzian SLLNs for random functions

作者: Lai Tian, Johannes O. Royset

发布日期: 2026-07-22

arXiv ID: 2607.20411v1

PDF 链接: 下载 PDF

3 分钟速览

研究问题：本文解决随机非凸非光滑优化中，样本平均近似（SAA）问题的平稳点是否收敛到总体问题的平稳点这一核心问题，特别关注比 Clarke 平稳点更精细的极限平稳点。
核心方法：通过建立 Lipschitz 伪度量下的强定律（Lipschitzian SLLN），直接比较 SAA 目标和总体目标函数的极限次微分及 Clarke 次微分，避免传统方法中先交换期望与次微分再处理的迂回。
关键结果：在两种结构条件下（拓扑可分性或模型论可定义性），证明了 SAA 函数与总体函数在 Lipschitz 伪度量下几乎处处收敛，进而得到极限次微分和 Clarke 次微分的均匀收敛，并给出了在某些条件下达到典型 $O_{\mathbb{P}}(\nu^{-1/2})$ 速率的结论。
主要局限：Lipschitz 伪度量的收敛本质上要求额外的结构条件，单纯的可积性与 Lipschitz 条件不足以保证（论文给出了反例）。此外，当可定义性的覆盖为无限可数个时，收敛速率可能任意慢，不再是 $\nu^{-1/2}$ 。
适合读者：研究随机优化、非光滑分析、统计学习理论，尤其是关注非凸优化中一阶方法收敛性的研究生和研究者。

论文背景和研究动机

随机优化和统计学习中的经验近似（如 SAA）被期望能保留总体问题的 “景观”。对于全局解，已有上图和一致强定律保证一致性。对于光滑非凸问题的平稳点，梯度的均匀律也提供了类似理论。然而，当目标函数 $f(\xi, \cdot)$ 非凸且非光滑时，甚至连如何正确定义一致性概念都需要小心。

传统方法多研究 “弱平稳性”，即先求期望与次微分的交换，研究 $\mathbb{E}[\overline{\partial}_x f(\bm{\xi}, \cdot)]$ 和其样本平均。这一定义较易建立一致性，但在概念上弱于直接对期望函数求次微分得到的 “平稳性”（即 $0 \in \overline{\partial}Ef(x)$ ），且弱平稳性可能在总体问题本无平稳点时仍无意义地成立。本文的目标是建立一种更强的一致性理论，直接在期望和 SAA 函数的（极限和 Clarke）次微分之间进行比较，而不依赖期望与次微分交换的规则。这引出了对更强的函数收敛模式——Lipschitz 伪度量收敛——的研究。

核心方法和技术细节

设 $f: \Xi \times \mathbb{R}^d \rightarrow \mathbb{R}$ 为随机函数， $\bm{\xi}_1, \dots, \bm{\xi}_\nu$ 为 iid 样本。记期望函数为 $Ef(x) = \mathbb{E}[f(\bm{\xi}, x)]$ ，样本平均为 $E^\nu f(x) = \frac{1}{\nu} \sum_{i=1}^\nu f(\bm{\xi}^i, x)$ 。

论文的核心是 Lipschitz 伪度量 $d_X$ 。其在集合 $X \ni 0$ 上的定义为：

d_X(h, g) = \max\{ |h(0)-g(0)|, \operatorname{g-lip}_X(h-g) \}

其中 $\operatorname{g-lip}_X(\phi)$ 是 $\phi$ 在 $X$ 上的全局 Lipschitz 模。 $d_X(h,g)$ 同时控制了函数值的差异和 Lipschitz 模的差异。关键性质在于，它直接控制了次微分的 Hausdorff 距离（见论文命题 5.2）：

\sup_{x\in X} d_l(\partial h(x), \partial g(x)) \le \sup_{x\in X} \operatorname{lip}(h-g)(x) \le d_X(h, g)

因此，若能证得 $d_X(E^\nu f, Ef) \to 0$ ，则自然地得到了极限次微分与 Clarke 次微分的均匀收敛，进而得到平稳点的一致性。

论文的核心贡献在于给出了使得 $d_X(E^\nu f, Ef) \to 0$ 几乎处处成立的两种充分条件：

拓扑可分性条件（定理 3.3）：当 $\{f(\xi,\cdot)|_X \mid \xi \in \Xi\}$ 被包含在 Lipschitz 空间 $(\operatorname{Lip}(X), \|\cdot\|_{\text{lip}})$ 的一个可分子空间中时，Lipschitzian SLLN 成立。这实质上是将 Banach 空间值随机变量的强大数律应用于该问题。一个特例是 $\Xi$ 可数，或样本空间的分布是离散的，此时条件自动满足。
模型论可定义性条件（定理 3.8 和 4.10）：这是更富技巧性的部分。论文放松了可分性要求，转而要求函数族满足某种 NIP（非独立性质）结构。具体地，定理 3.8 假定存在对 $\Xi$ 的一个覆盖，在每块上，切片 $\{f(\xi, \cdot)\}$ 在某个稠密集上的取值是某个 NIP 理论中一致可定义的。
- 技术路线：利用可定义性，将 $d_X$ 中的全局 Lipschitz 模的控制转化为一个经验过程（由商差 $\frac{f(\xi,x)-f(\xi,y)}{\|x-y\|}$ 构成的函数类）的一致收敛问题。由于 NIP 可定义性确保了相应的函数类是 VC-子图类，因此是 Glivenko-Cantelli 类，从而得到几乎处处收敛。
- 收敛速率（定理 3.9）：当覆盖的块数有限且二阶矩存在时，可将经验过程的中心极限定理（Donsker 性质）应用于此 VC-子图类，得到典型的 $O_{\mathbb{P}}(\nu^{-1/2})$ 收敛速率。
- 精细结果（定理 4.10）：论文进一步指出，在更弱的分片定义条件下（类似非一致可学习性中的技巧），即使切片仅在某个可数语言的可定义结构中点态可定义，仍能构造出满足条件的覆盖，从而保证收敛性。

创新点和贡献

首次比较极限次微分的均匀律：以往的均匀律或针对 Clarke 次微分，或通过交换期望和次微分来处理弱平稳性，或局限于次微分正则函数类。本文的 Lipschitzian SLLN 首次为一般（可能非正则）的局部 Lipschitz 随机函数，提供了直接比较 $\partial E^\nu f$ 与 $\partial Ef$ 的均匀收敛结果（见论文推论 5.3）。
对可分性和可定义性条件的统一处理：作者证明了，他们在先前工作中发现的 Lipschitzian SLLN 的反例（见论文命题 3.6）不会发生在满足这两种结构条件之一的函数类上。他们展示了传统的可分性条件和前沿学习理论中的 NIP 可定义性条件都能保证这一更强收敛模式。
有限样本解的精确识别：将 Lipschitz 伪度量的收敛应用于全局解的锐利极小性质（sharp minima）和极限平稳点的识别问题，将此前严重依赖凸性和有限支撑的有限样本识别理论推广到了更广泛的非凸函数类（见论文命题 5.5 和 5.6）。
收敛速率的正反结果：论文不仅证明了在有限覆盖可定义性下可达 $\nu^{-1/2}$ 速率（定理 3.9），还通过一个巧妙的构造说明，在仅有无穷覆盖或仅有可分性时，收敛可以任意慢（命题 3.10），深刻揭示了函数空间的复杂性与收敛速度之间的内在关系。

局限与待解决问题

该工作的局限主要源自理论框架的必要条件：

结构条件的必要性：论文充分说明了单纯依靠标准可积性和 Lipschitz 条件， $d_X(E^\nu f, Ef)$ 甚至不必收敛（见论文命题 3.6 的凸函数反例）。因此，附加的拓扑或模型论条件是无法回避的。对于那些既不满足可分性也不属于 NIP 可定义结构的函数类，本文结论不适用。
模型论条件的验证：虽然论文指出许多深度学习中的损失函数在 $\mathcal{R}_{\exp}$ （实指数域）中是可定义的，但在实践中验证一个复杂的工程化模型和整个数据生成过程是否严格满足文章所采用的精确可定义性条件是困难的。 $\mathcal{R}_{\exp}$ 可定义性排除了诸如取整函数等操作，这可能限制了部分实际场景。
速率常数的显式性：定理 3.9 虽然给出了 $O_{\mathbb{P}}(\nu^{-1/2})$ 的定性速率，但由于其基于泛函中心极限定理的定性应用，其中的绝对常数 $C_\delta$ 与问题维度 $d$ 和 VC-维数的关系并未给出显式表达，因而无法直接用于构造有限样本意义下的置信界。
可定义性中 “可数语言” 假设：定理 4.10 在将分片一致可定义性放松为分片点态可定义性时，关键依赖于所涉结构语言可数和完全 Borel 的假设。作者自己也提出，能否去除这些可数性的假设是个未解决问题，这为更一般的理论留下了开放空间。