随机函数的 Lipschitz 强大数定律

论文信息

标题: Lipschitzian SLLNs for random functions

作者: Lai Tian, Johannes O. Royset

发布日期: 2026-07-22

arXiv ID: 2607.20411v1

PDF 链接: 下载 PDF

研究背景与动机

在随机优化和统计学习中，样本平均近似（SAA）是处理期望值目标函数的核心方法。其核心思想是用有限样本的经验期望替代总体期望，然后求解近似问题。经典理论已充分建立了全局解的一致性：若经验函数在恰当拓扑下收敛于总体函数，则近似解收敛到真实解。然而，对于非凸非光滑问题，平稳点（stationary points）的一致性理论远未完备。

平稳点是指满足 $0 \in \partial Ef(x)$ 的点，其中 $\partial Ef$ 是某种次微分映射。在非光滑优化中，存在多种次微分概念——Clarke 次微分、极限次微分等，其精细程度不同。现有大多数一致性结果绕开了对 $Ef$ 的直接次微分分析，转而研究弱平稳性：交换期望与次微分运算，考虑 $0 \in \mathbb{E}[\partial_x f(\xi, x)]$ 。然而，弱平稳点往往比真实平稳点多得多，甚至可能包含所有点（如文中所举的分段常数示例），使得这个概念在应用中空洞无用。另一方面，直接比函数（而非先微分的函数）的次微分的一致性理论，由于集合映射的复杂性，长期缺乏进展。

本文作者此前的工作 [Tian and Royset, 2025] 已经表明，在标准条件下，即使对凸函数，Clarke 次微分的均匀收敛也可能失败。因此，需要寻找新的结构条件，保证更强的收敛模式，从而建立极限平稳点的一致性理论。这就引出了本文的核心目标：建立一种称为 Lipschitzian 强大数定律 的收敛结果，用以统一控制函数值和全局 Lipschitz 模量，进而导出次微分的一致收敛和有限样本解识别。

核心概念：Lipschitz 伪度量与平稳性

论文引入的关键工具是 Lipschitz 伪度量 $d_X(h,g)$ 。对于定义在集合 $X \subset \mathbb{R}^d$ 上的函数 $h$ 和 $g$ ，该伪度量定义为

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

其中 $\operatorname{g-lip}_X(\cdot)$ 是函数在 $X$ 上的全局 Lipschitz 模量。这一度量不仅控制函数在单点的偏差，还控制整个函数差分的 Lipschitz 常数，从而对函数的一阶结构施加了极强的约束。

正是这种 “同时控制函数值和斜率变化” 的能力，使得 $d_X$ 与次微分建立了直接联系。文中证明了关键不等式：

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

其中 $\mathrm{dl}$ 是 Hausdorff 距离， $\partial$ 可以是极限次微分或 Clarke 次微分。这意味着，只要样本平均函数 $E^\nu f$ 与总体期望 $Ef$ 在 Lipschitz 伪度量下收敛，其极限次微分和Clarke 次微分就会在 Hausdorff 距离下均匀收敛。这一观察使得作者能够将次微分的一致收敛问题转化为在 Lipschitz 空间中建立强大数定律的问题。

主要理论结果：两条路径建立强收敛

文章在温和的积分性和 Lipschitz 假设下，沿着两条截然不同的路径建立了 $d_X(E^\nu f, Ef) \to 0$ 的几乎必然收敛。

路径一：拓扑可分离性。 假设切片族 $\{f(\xi,\cdot)|_X : \xi \in \Xi\}$ 位于 $(\mathrm{Lip}(X), \|\cdot\|_{\mathrm{lip}})$ 的一个可分子空间中。这一条件在 $\Xi$ 为可数集时自然成立，例如分布为离散的情形；或者当 $X$ 紧致且每个切片连续可微时也成立。在此条件下，作者将映射 $\xi \mapsto f(\xi,\cdot)|_X$ 视为取值于可分 Banach 空间的随机元，应用 Banach 值强大数定律直接得到结论。

路径二：模型论可定义性。 提出一种 “分段均匀可定义性” 条件，涵盖了比联合可定义性更广的函数类。该条件要求存在可数覆盖 $\{\Xi_\ell\}$ ，使得在每个 $\Xi_\ell$ 上，切片函数在某个具有 NIP（非独立性性质）的扩张结构 $\mathcal{M}_\ell$ 中可被同一个公式定义。NIP 结构包括所有 o-极小结构（如实指数域 $\mathcal{R}_{\exp}$ ），而后者能表达现代深度学习中大量损失函数。在此条件下，证明依赖于将 Lipschitz 模量的控制转化为一类差商函数的 Glivenko–Cantelli 性质，通过 Vapnik–Chervonenkis 理论和经验过程技术得到收敛。

两条路径互不包含，但都能排除此前工作中发现的失败现象。特别地，对于 o-极小结构中可定义的函数（如由 $\exp$ 、多项式、分段线性等构成的组合），不论分布是否连续，均能保证 Lipschitzian SLLN 成立。文章还进一步讨论了收敛速率：有限覆盖情形下，若二阶矩存在，则得到标准速率 $O_{\mathbb{P}}(\nu^{-1/2})$ ；但若允许无穷覆盖，则收敛可任意慢，这一点通过构造与缺失质量（missing mass）问题相关的反例得以证明。

创新点与贡献

本研究的主要创新可归纳为三个方面：

提出 Lipschitzian 强大数定律并建立与次微分收敛的桥梁。 该定律比通常的一致收敛或上图收敛更强，能够统一控制函数值及其整体 Lipschitz 斜率，从而直接导出极限次微分（非凸值）的 Hausdorff 一致收敛。这填补了非凸非光滑情形下，不交换期望与次微分而直接比较次微分的一致收敛理论的空白。
引入模型论工具，揭示了 NIP 性质在随机函数逼近中的作用。 利用 NIP 结构定义的函数类构成 VC-子图类，从而触发均匀收敛，巧妙地将统计学习理论与非光滑优化联系起来。这使得一大批实际中的非光滑非凸函数（包括深度学习损失函数）在 SAA 框架下获得强一致性保证，而无需传统假设如凸性或次微分正则性。
提供了清晰的可分离性条件，并阐明了不可能定理的边界。 离散分布或连续可微切片的情形自然满足可分离性，收敛成立；而连续分布的一般 1-Lipschitz 凸函数却可能不收敛。通过正反例的对比，作者精确界定了使 Lipschitzian SLLN 成立的结构条件，为后续研究提供了明确指引。

实践应用与启示

尽管本文是纯理论论文，但其结果对实际随机优化算法设计具有直接启示。

深度学习中的损失景观分析。 现在已知许多神经网络的训练损失是 o-极小结构可定义的。根据本文结果，在适当 Lipschitz 条件下，经验损失的极限次微分几乎必然一致逼近总体损失的极限次微分。这意味着，基于 SAA 找到的极限平稳点在大样本下是可靠的，不会出现 “弱平稳但非真平稳” 的陷阱。
离散化与量化。 当分布为离散时（例如样本有限或经过量化处理），可分离性自动满足。这为量化后的随机优化问题提供了强一致性理论支撑，表明将连续分布离散化不仅简化计算，还能提升收敛的稳健性。
有限样本解识别。 在 sharpness 条件下，论文证明了全局解和极限平稳点的有限样本识别性质：一旦样本量足够大，近似问题的解就必定是真实问题的解。这为非凸问题的精确解认证提供了理论依据，可结合验证算法设计早期停止准则。
非光滑优化算法。 传统算法常依靠弱平稳性来判断收敛，可能停滞在伪平稳点。本文的收敛结果提示，可以通过监控经验函数的 Lipschitz 模量变化来评估近似的质量，并设计更可靠的终止条件。

未来发展方向

本文开启了许多有趣的研究方向：

构造性收敛速率。 在 NIP 条件下，收敛速率的常数依赖于 VC 维数，但本文未给出显式界。开发出可计算的速率界，将大大提升理论的实用价值。
超越 NIP 结构。 有些实用函数类（如涉及正弦、分形等）可能不满足 NIP，能否找到更弱的组合条件依然保证 Lipschitzian SLLN？
自适应采样与方差缩减。 如果将 Lipschitz 伪度量的收敛与重要性采样或随机方差缩减梯度方法结合，或许能加速经验函数的逼近。
二阶与更高阶信息。 能否类似地建立 Hessian 或更高阶近似的强收敛理论，从而为非光滑非凸问题的二阶算法奠定基础？

总结

《Lipschitzian SLLNs for random functions》一文为非凸非光滑随机优化提供了全新的收敛理论框架。通过引入 Lipschitz 伪度量，作者成功架起了函数空间收敛与次微分一致收敛之间的桥梁，并利用可分离性和模型论 NIP 性质两条独立路径建立了强大数定律。这一成果不仅能解释现有算法中弱平稳性的缺陷，还为深度学习等现代应用中广泛出现的可定义函数类提供了强一致性保证。文章在数学深度与应用广度之间取得了精妙的平衡，无疑将激发统计学习、随机优化和模型论交叉领域的进一步研究。