当样本均值欺骗你：Lipschitzian 强大数定律如何守住非凸非光滑优化的底线

小凯 · 2026-07-24T00:46:37+00:00

论文概要研究领域: ML 作者: Lai Tian, Johannes O. Royset 发布时间: 2026-07-24 arXiv: 2507.18390 中文摘要我们证明了局部Lipschitz函数在Lipschitz伪度量下的强大数定律。我们的结果在拓扑条件或模型理论条件下成立，后者涵盖了在o-minimal结构中联合可定义的函数，但远远超出了这一类。应用包括极限和Clarke次微分的均匀收敛以及解的有限样本识别。因此，我们确定了广泛的函数类，对于我们之前负面结果中揭示的失败现象[Tian和Royset, arXiv:2511.16568, 2025]不会发生。原文摘要 We prove strong laws of large numbers for locally Lipschitz functions in the Lipschitz pseudometric. Our results hold under either a topological or a model-theoretic condition, with the latter…

一个反直觉的陷阱

假设你在训练一个深度学习模型。损失函数 $f(\xi, x)$ 依赖于随机数据 $\xi$ 和参数 $$x$$ 。你没法计算期望损失 $\mathbb{E}[f(\xi, x)]$ ，所以你用样本均值 $\frac{1}{n}\sum_{i=1}^n f(\xi_i, x)$ 来近似它。当 $n \to \infty$ ，样本均值收敛到期望值——这是 Kolmogorov 强大数定律（SLLN）告诉我们的。

但问题来了：你真正关心的不是"函数值收敛不收敛"，而是"样本平均问题的驻点是否收敛到总体问题的驻点"。对于凸函数，这没问题——局部最优就是全局最优。对于光滑非凸函数，也没问题——梯度一致收敛。但如果函数既非凸又非光滑呢？

这正是 Lai Tian 和 Johannes O. Royset 在论文《Lipschitzian SLLNs for random functions》中解决的核心问题。

弱驻点 vs. 真驻点：一个关键区分

先理解为什么非凸非光滑情况会出问题。考虑 Clarke 次微分 $\partial Ef(x)$ ——它是非光滑分析中替代梯度的对象。对于总体问题，驻点满足 $0 \in \partial Ef(x)$ ；对于样本问题，驻点满足 $0 \in \partial E^n f(x^n)$ 。

我们希望：如果 $x^n \to x$ 且 $\text{dist}(0, \partial E^n f(x^n)) \to 0$ ，那么 $0 \in \partial Ef(x)$ 。

但大多数现有结果不敢直接处理 $\partial E^n f$ 和 $\partial Ef$ 这两个集值映射。它们绕了条弯路：先交换期望和次微分，研究 $\frac{1}{n}\sum \partial_x f(\xi_i, \cdot)$ 和 $\mathbb{E}[\partial_x f(\xi, \cdot)]$ 。这叫"弱驻点"。

问题在于， $\partial Ef(x) \subset \mathbb{E}[\partial_x f(\xi, x)]$ ，反向包含一般不成立。也就是说，弱驻点可能不是真驻点。论文给出了一个精巧的例子： $f(\xi, x) = \frac{1}{2}x + \xi \phi(x)$ ，其中 $\phi$ 是 1-Lipschitz 函数， $\partial \phi(x) = [-1, 1]$ 。在这个例子中，弱驻点集远大于真驻点集——用弱驻点会给你一堆"假阳性"。

Lipschitz 伪度量：一个更强的收敛模式

论文的核心创新是使用 Lipschitz 伪度量来衡量 $$E^n f$$ 和 $$Ef$$ 的接近程度：

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

这比传统的逐点收敛或一致收敛更强。它不仅要求函数值接近，还要求函数的"变化率"也接近。直觉上：如果两个函数的差值本身是 Lipschitz 的，且 Lipschitz 常数趋于零，那么它们的"形状"在收敛——不只是值在收敛。

这种收敛模式直接保证了驻点的一致性。如果 $$E^n f$$ 在 Lipschitz 伪度量下收敛到 $$Ef$$ ，那么 $$E^n f$$ 的近似驻点就是 $$Ef$$ 的真驻点。这是"epigraphical SLLN"和"uniform SLLN"做不到的。

两条路径：可分性与可定义性

论文给出了两类条件来保证 Lipschitzian SLLN 成立。

路径一：可分性

定理 3.3（可分性）：如果函数族 $\{f(\xi, \cdot)|_X \mid \xi \in \Xi\}$ 包含在 Lipschitz 空间的一个可分子空间中，那么 $d_X(E^n f, Ef) \to 0$ 几乎必然成立。

可分性意味着存在可数稠密子集。最简单的满足方式是 $\Xi$ 可数——即随机变量是离散分布的。这覆盖了场景法、量化等常见应用。

但可分性并不总是成立。论文给出了一个反例： $f(\xi, x) = |x - \xi|$ ， $\xi \sim \text{Uniform}[0,1]$ 。对于任意两个不同的 $\xi, \xi'$ ， $\|f(\xi, \cdot) - f(\xi', \cdot)\|_{\text{lip}} = 2$ 。这意味着函数族不可分——每个元素之间都隔着固定距离，没法用可数集逼近。

路径二：可定义性

当可分性失败时，论文提供了第二条路径：可定义性（definability）。这涉及模型论中的 NIP（Non-Independence Property）结构和 o-极小性。

直觉上，"可定义"意味着函数可以用某种"良好"的公式描述——多项式、指数函数、对数函数等，以及它们的有限组合。这些函数虽然可能不可数，但它们的"复杂度"受到结构限制，使得大数定律仍然成立。

论文证明了三类可定义函数满足条件： 1. 联合可定义函数： $f(\xi, x)$ 整体在某个 NIP 结构中可定义 2. 切片可定义函数：每个 $f(\xi, \cdot)$ 可定义，且定义公式参数化地依赖于 $\xi$ 3. 分段可定义函数：函数在有限多个可定义区域上分段定义

o-极小结构是 NIP 结构的重要特例。实数域上的半代数函数、全局半代数函数、受限解析函数等都是 o-极小可定义的。这覆盖了大量实际应用中的函数类。

为什么这很重要

这篇论文的意义在于填补了非凸非光滑优化理论的一个空白。

对机器学习的意义：深度学习中的 ReLU 网络、损失函数中的 $\ell_1$ 正则化、支持向量机的铰链损失——这些都是非凸非光滑的。当你用 SGD 训练这些模型时，你实际上在用样本平均近似期望损失。论文的结果告诉你：在什么条件下，你找到的近似驻点是可靠的。

对随机优化的意义：场景法是随机规划的常用工具——用有限场景近似不确定参数。论文的结果为场景法的收敛性提供了更精细的理论保证：不只是最优解收敛，驻点也收敛。

对统计学习的意义：经验风险最小化（ERM）的理论基础是统一收敛。但统一收敛只保证函数值接近，不保证"优化景观"接近。Lipschitzian SLLN 保证了景观本身在收敛——这意味着局部最优、鞍点、驻点的结构都在收敛。

一个更深的洞察

论文揭示了一个深层联系：函数空间的几何性质（可分性）和逻辑性质（可定义性）都能保证统计一致性。这不是巧合——可分性和可定义性都在限制函数族的"复杂度"，只是从不同角度。

可分性说：函数族不能太"分散"，必须能被可数集逼近。可定义性说：函数族不能太"野"，必须能用有限公式描述。两者都在说同一件事：统计一致性需要函数族有界复杂度。

这和机器学习中的偏差-方差权衡呼应：模型容量越大，越可能过拟合。这里的故事是：函数族越"野"，样本平均越可能欺骗你。Lipschitzian SLLN 给出了"不欺骗"的精确条件。

结语

Lai Tian 和 Johannes Royset 的工作为非凸非光滑优化的统计一致性提供了一个统一框架。Lipschitz 伪度量是连接概率论（大数定律）、优化理论（驻点一致性）和模型论（可定义性）的桥梁。

论文的技术细节很硬核——涉及 Bochner 积分、NIP 结构、o-极小性等。但核心直觉很简单：当样本均值在"形状"上收敛到期望时（不只是值），你找到的驻点才是可靠的。这个"形状收敛"就是 Lipschitz 伪度量，而保证它的条件是可分性或可定义性。

对于做优化和机器学习理论的人来说，这篇论文值得仔细读。它不只是推广了 Kolmogorov SLLN，更重要的是给出了一个思考"统计一致性"的新视角：不要只看值，要看形状。