在机器学习和运筹学的世界里，教科书式的问题通常假设数据来自单一的、静态的分布。你训练模型，数据表现得很“听话”，然后你找到了最优解。

但现实世界很少如此配合。金融市场波动，用户偏好漂移，传感器网络经历环境变化。在这些场景中，生成数据的潜在概率分布会随时间发生变化。这就是时变分布 (time-varying distributions) 的领域。

当你将这种不断变化的景观与复杂的非光滑 (尖锐/有折点) 和非凸 (有多个低谷) 目标函数结合起来时，标准的优化算法通常会失效。它们要么收敛得太慢，因为使用了太多旧数据；要么根本无法收敛，因为它们无法处理函数在数学上的“尖锐性”。

在这篇文章中，我们将深入探讨 Ye、Cui 和 Wang 在 2025 年发表的一篇研究论文，该论文正好解决了这一系列交叉挑战。他们提出了一种新方法: 使用自适应采样策略的在线随机近端凸差算法 (Online Stochastic Proximal Difference-of-Convex Algorithm, ospDCA) 。

我们将探索他们如何解决获取非光滑函数精确梯度的问题，以及他们如何设计一种算法，使其能够“知道”何时增加样本量以保持准确性，同时不浪费计算资源。

问题所在: 非光滑、非凸且非平稳

让我们正式定义一下我们要驯服的这头猛兽。我们面对的是一个凸差 (Difference-of-Convex, DC) 优化问题。DC 规划非常强大，因为几乎任何非凸函数都可以表示为两个凸函数之差。

目标是在凸集 \(C\) 的约束下最小化函数 \(f(x)\):

一般问题表述，显示两个期望函数 G 和 H 之间的差。

这里，\(G(x, \xi)\) 和 \(H(x, \zeta)\) 是凸函数，但它们的差 \(f(x)\) 是非凸的。变量 \(\xi\) 和 \(\zeta\) 代表随机数据向量。

这里有三个不同层面的困难:

  1. 随机性 (Stochastic) : 我们无法精确计算期望值 \(g(x)\) 和 \(h(x)\)；我们必须使用采样数据来估计它们。
  2. 非光滑性 (Nonsmooth) : 函数 \(G\) 和 \(H\) 可能没有光滑的导数 (想想绝对值函数 \(|x|\) 或 ReLU) 。这意味着我们要处理的是次梯度 (有效斜率的集合) ，而不是单一的梯度向量。
  3. 时变性 (Time-Varying) : 分布 \(P_\xi\) 和 \(P_\zeta\) 随时间变化。在时刻 \(t=1\) 收集的数据在时刻 \(t=100\) 可能会产生误导。

衡量偏移

为了处理时变分布，我们需要一种方法来衡量我们脚下的“基本事实 (ground truth) ”移动了多少。作者使用了Wasserstein-1 距离 , 通常被称为“推土机距离 (Earth Mover’s Distance) ”。它有效地衡量了将一个概率分布转换为另一个概率分布所需的工作量。

两个分布之间 Wasserstein-1 距离的定义。

这项工作所做的假设是，虽然分布会发生变化，但它们不会无限快地变化。随时间的累积偏移是有界的，这意味着环境最终会稳定下来，或者移动得足够慢，让算法能够跟上。

理论突破: 次微分收敛

在介绍算法之前，我们需要解决一个主要的理论障碍。在光滑随机优化中，我们知道如果对采样梯度取平均值，该平均值会非常快地收敛到真实梯度。具体来说，平方误差以 \(O(1/n)\) 的速率下降。

光滑梯度的标准收敛率，与 1/n 成正比。

然而，处理非光滑函数要困难得多。当函数有一个“折点”时，导数不是一个单一的数字，而是一组数字 (次微分) 。当我们从非光滑函数中采样次梯度时，简单地对它们取平均值并不能保证像光滑情况那样具有良好的收敛行为。

以前的工作通常需要限制性的假设，比如要求次梯度有一个特定的“可测选择器 (measurable selector) ”，这在代码中很难实现。

使用支撑函数

这篇论文的作者推导了集值映射的样本均值近似 (SAA) 的新收敛率。他们使用豪斯多夫距离 (Hausdorff distance) 来衡量误差，该距离量化了两个集合 (估计的次微分集合与真实的次微分集合) 之间的距离。

使用豪斯多夫距离定义的 SAA 误差。

为了解决这个问题，他们利用了一种叫做支撑函数 (support function) \(\sigma(u, S)\) 的数学工具。他们不直接比较集合，而是比较集合的支撑函数。利用赫尔曼德公式 (Hörmander’s formula) ，他们将集合之间的距离转换为了单位向量上的最大化问题。

通过支撑函数计算豪斯多夫距离。

结果: 匹配光滑情况的速率

通过这种几何方法，作者证明了一个强有力的定理。他们表明，次微分映射的期望平方误差以大约 \(O(1/n)\) 的速率收敛。

主定理显示非光滑次微分的平方误差界限与 1/n 成正比。

这为什么重要? 这是一个理论上的重磅炸弹。它证明了对非光滑函数进行次梯度采样在统计上与对光滑函数进行梯度采样一样高效。这一结果允许算法从样本集中选取任何有效的次梯度 (计算上很容易) ，而不需要寻找特定的数学选择 (计算上很难) ，同时仍然保证快速收敛。

核心方法: 自适应 ospDCA

既然理论保证了我们的样本是可靠的，让我们来看看算法本身。

经典的DC 算法 (DCA) 通过利用 \(f(x) = g(x) - h(x)\) 的结构来工作。由于 \(h(x)\) 是凸的，我们可以将其线性化。在每一步，我们找到 \(h(x)\) 的一个次梯度，画一条接触 \(h(x)\) 的线 (或面) ，并将困难的非凸问题替换为一系列较容易的凸问题。

随机模型

在时间步 \(t\)，算法抽取一批样本来近似函数。它构建了一个凸近似模型 \(\bar{M}_t(d)\)。注意，他们不使用旧样本。他们只使用来自当前分布的新数据，以避免分布偏移带来的偏差。

近似模型 M_t 结合了采样的 g、线性化的 h 和近端正则化项。

这里，\(\bar{y}_t\) 是凹部分 \(h\) 的估计次梯度。项 \(\frac{1}{2}\mu_t \|d\|^2\) 是近端正则化项，用于防止新步长 \(d\) 偏离太远，从而确保稳定性。

每次迭代需要求解的子问题变为:

凸子问题最小化。

自适应采样策略

随机优化的标准方法是以固定速率 (例如 \(t^2\) 或线性) 增加样本量，以随着算法的进行减少方差。

然而，固定的时间表是低效的。

  1. 训练早期: 我们离解还很远。步长很大。我们不需要高精度就知道大概往哪个方向走。小样本量就足够了。
  2. 训练晚期: 我们接近临界点。步长很小。梯度的噪声可能导致我们在最优解附近跳来跳去。我们需要高精度 (大样本量) 。

作者提出了一种自适应策略。他们将所需的样本量 (\(N_{g,t}\) 和 \(N_{h,t}\)) 与步长 \(\|\bar{d}_t\|^2\) 联系起来。

如果算法建议一个较大的步长 \(\|\bar{d}_t\|\)，这意味着当前点不是临界点，所以我们可以容忍更粗略的估计。如果步长很小，我们很可能是在精炼解，因此我们通过要求更多样本来强制执行更严格的误差界限。

他们推导出的确保收敛的条件是:

步长范数条件，将步长 d 与所需的样本量 N_g 和 N_h 联系起来。

这个不等式起到了调节器的作用。左侧代表进展 (步长的大小) 。右侧代表误差容忍度，随着 \(N\) 的增加而缩小。随着步长 \(\|\bar{d}_t\|\) 趋近于零 (收敛) ，必须增加 \(N\) 以满足不等式。

收敛性分析

这真的有效吗？作者提供了严格的证明，表明该算法几乎必然收敛到 DC 临界点。

分析依赖于充分下降性质 。 在确定性优化中，我们期望目标值每一步都下降。在随机、时变的设置中，我们只能期望在期望值上实现这一点，并且我们必须考虑采样和分布偏移 (Wasserstein 距离) 引入的误差。

期望中的下降不等式，考虑了采样误差和分布偏移。

上面的方程显示，预期的改进取决于步长 (好的部分) ，减去采样误差 (\(C/N^\alpha\) 项) 和分布偏移 (\(W_1\) 项) 。

通过确保累积分布偏移是有限的 (环境稳定下来) 并自适应地增加样本量，误差项比步长消失得更快。

步长 d_t 在期望中收敛到零。

这个结果证明了算法生成的迭代序列最终将停止移动，这意味着它找到了一个目标函数各方“力量”平衡的驻点。

实验与结果

为了验证理论，作者将自适应 ospDCA 应用于在线稀疏鲁棒回归问题。

目标是找到一个使预测误差最小化的稀疏向量 \(\beta\)。

  • 鲁棒性: 他们使用绝对误差 (L1 损失) 而不是平方误差来处理异常值。
  • 稀疏性: 他们使用截断 L1 惩罚 (一种非凸 DC 函数) 来强制许多系数为零。
  • 在线性: 数据以流的形式到达，且分布不断变化。

问题表述如下:

鲁棒回归目标函数。

性能比较

实验将自适应 ospDCA (蓝色) 与非自适应版本 (绿色/洋红色) 和其他基线进行了比较。

在下面的图表中，Y 轴是到最优解的距离 (对数刻度) 。自适应算法明显优于其他算法，更快地实现了更低的误差。

性能比较图显示自适应 ospDCA 比基线收敛得更快。

自适应采样的行为

最具启发性的结果是样本量随时间变化的图表。

看下面图表中的蓝色虚线。

  • 阶段 1: 在前 60-80 次迭代中，样本量保持非常低 (Y 轴上接近零) 。算法迈着大步，轻松取得进展。
  • 阶段 2: 随着它接近解，样本量急剧上升 (末尾的尖峰) 。

样本量演变显示仅在优化的最后阶段样本量急剧增加。

这直观地展示了为什么自适应方法是高效的。标准方法 (绿线) 逐渐增加样本量，在不需要的时候浪费了早期的计算资源，而在后期可能又没有足够的精度。自适应方法将“计算预算”留到了最后阶段，因为在那时，精度对于锁定精确解至关重要。

结论与启示

论文《An Online Adaptive Sampling Algorithm for Stochastic Difference-of-convex Optimization with Time-varying Distributions》为现代优化问题提供了一个稳健的框架。

核心要点:

  1. 非光滑也没问题: 多亏了次微分新的 \(O(\sqrt{p/n})\) 逐点收敛率，我们可以像处理光滑函数一样高效地处理目标函数中的尖锐折点。
  2. 自适应致胜: 将样本量与优化步长挂钩，使得算法在探索时计算成本低廉，仅在精炼时才昂贵。
  3. 对偏移的鲁棒性: 只要总的“漂移”是有界的，该算法在理论上就能处理时变分布。

这项工作弥合了理论非光滑分析与实际在线学习之间的差距。对于学生和从业者来说，它提供了一个设计算法的蓝图: 算法不应盲目地消耗数据，而应根据距离目标的远近来调整其“食欲”。