🤖 machine learning

Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise

本文提出了一种带有截断两点梯度估计器的随机零阶算法，用于在重尾噪声下求解非凸非光滑优化问题，实现了最优的维度相关复杂度，并达到了与Goldstein平稳点最佳已知精度相匹配的速率。

原作者： Zhuanghua Liu, Luo Luo

发布于 2026-05-26

📖 1 分钟阅读☕ 轻松阅读

原作者： Zhuanghua Liu, Luo Luo

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图在一片广阔、雾气弥漫且崎岖不平的山脉中找到最低点。这是机器学习中的一个常见问题：寻找模型的最佳参数以做出准确预测。

在一个理想的世界里，你会拥有一张地图和一个指南针（梯度），告诉你确切的下坡方向。但在现实世界中，尤其是面对复杂的 AI 模型时，你往往无法看清坡度。你只能在两个点上戳探地面，并问：“这里比那里高还是低？”这被称为零阶优化。

现在，想象这片山脉的天气极其恶劣。你不是在微风中前行，而是遭遇了突然、巨大且不可预测的暴风雨（称为重尾噪声）。这些风暴如此狂野，以至于标准的天气预报（通常假设风暴通常很小）完全失效。如果你试图使用一个会被这些巨大风暴吹偏方向的指南针来导航，你永远找不到谷底。

以下是论文《具有重尾噪声的零阶非凸非光滑优化》如何解决这一问题的简要说明：

1. 问题：“暴风雨”中的山脉

作者正在处理一种特定类型的山脉：

非凸：地形充满了山丘、山谷和高原，而不仅仅是一个平滑的碗状。
非光滑：地面崎岖不平、布满岩石，不像玻璃那样平滑。
重尾噪声：推动你测量的“风”（数据噪声）是不可预测的。有时它只是微风，但偶尔会是一场飓风，让你的测量结果剧烈偏离。大多数先前的方法都假设风总是温和的，但这并不符合现实。

2. 解决方案：“截断”指南针（ZOCOON）

作者提出了一种名为ZOCOON（零阶截断在线到非凸）的新算法。将其视为一种具有两个主要技巧的智能导航策略：

技巧 A：“两点戳探”
由于你看不到坡度，算法会选择两个非常接近的点，并在两处戳探地面。通过比较高度差，它推测出坡度的方向。这是在没有地图的情况下导航的标准方法。

技巧 B：“风暴护盾”（截断）
这是该论文的重大创新。当算法利用两次戳探计算坡度时，“飓风”噪声可能会让结果看起来地面是以 90 度角倾斜的（这是不可能的）。

旧方法：会相信这个疯狂的数据，并朝着错误的方向迈出巨大而灾难性的一步。
ZOCOON：使用一个“截断器”。它会说：“如果坡度看起来太陡（像飓风一样），我就将其限制在一个合理的最大值。”它忽略了由噪声引起的极端异常值。这就像戴上一顶头盔，能阻止落石将你击倒；你仍然能感受到冲击，但不会被打晕。

3. 目标：找到“足够好”的位置

由于山脉如此崎岖，从数学上证明你已到达完美的底部是不可能的。因此，作者的目标是找到一个Goldstein 驻点。

类比：他们不是寻找整个世界的最低点，而是寻找这样一个位置：如果你观察周围一个小圆圈内的地面，平均坡度是平坦的。这是一个“足够好”的休息点，你不太可能继续向下滑落。

4. 结果：为何有效

该论文从数学上证明了，即使“风暴”巨大，ZOCOON 也能发挥作用。

效率：当天气平静（没有重风暴）时，它找到这个“足够好”的位置的速度与最佳方法一样快。
鲁棒性：与其他可能在重噪声的混乱中迷失方向的方法不同，ZOCOON 保持稳步前进，因为它忽略了疯狂的异常值。
现实世界测试：作者在真实数据集（如分类电子邮件或文档）上测试了这一点。他们在数据中添加了人为的“暴风雨”噪声。ZOCOON 比先前的方法更快、更稳定地找到了解决方案，而先前的方法则被噪声搞糊涂了。

总结

将这篇论文想象为发明了一种在飓风中徒步的新方法。以前的徒步者试图正常行走，结果被吹走了。这种新方法（ZOCOON）说：“当风刮得太猛时，我们忽略风那疯狂的方向，继续朝我们能找到的最合乎逻辑的方向前进。”它使我们能够解决复杂的机器学习问题，即使数据杂乱无章且充满极端异常值。

技术摘要：含重尾噪声的零阶非凸非光滑优化

问题表述
本文研究无约束随机优化问题：
$\min_{x \in \mathbb{R}^d} f(x) = \mathbb{E}_{\xi \sim P}[F(x; \xi)]$
其中目标函数 $f$ 是非凸且非光滑的，但满足 Lipschitz 连续性。该设定为零阶，意味着算法仅能访问含噪函数值 $F(x; \xi)$ ，而无法获取梯度。

与 prior work 的关键区别在于噪声假设。许多现有分析依赖于有界方差假设（二阶矩），而本文在重尾噪声假设下开展工作。具体而言，随机分量函数的 Lipschitz 常数 $L(\xi)$ 满足有界 $p$ 阶矩条件：
$\mathbb{E}[L(\xi)^p] \leq L^p$
其中 $p \in (1, 2]$ 。当 $p < 2$ 时，方差可能无界，这刻画了重尾分布（例如 Lévy $\alpha$ -稳定分布），此类分布在深度神经网络训练和强化学习等现实机器学习应用中常见。

方法论：ZOCOON 算法
作者提出了**零阶截断在线转非凸（ZOCOON）**算法。该方法整合了三个核心组件：

在线转非凸转换框架：基于 Cutkosky 等人 [9] 建立并由 Kornowski 和 Shamir [25] 扩展的框架，该算法将在线学习问题转化为非凸优化求解器。这涉及在多轮中运行一系列更新以寻找驻点。
两点随机梯度估计器：由于梯度不可用，算法基于平滑代理函数 $f_{\delta'}(x)$ 使用零阶估计器。对于点 $x$ 和单位球面上的随机方向 $w$ ，估计器为：
$\hat{g}(x; w, \xi) = \frac{d}{2\delta'} (F(x + \delta'w; \xi) - F(x - \delta'w; \xi))w$
这提供了平滑函数梯度的无偏估计。
梯度截断：为了减轻重尾噪声的影响，算法在梯度估计器中引入了截断算子。更新步骤使用 $\hat{g}_{clipped} = \text{clip}(\hat{g}, \tau)$ ，其中 $\tau$ 是阈值参数。这防止了大且含噪的梯度破坏优化过程的稳定性。

该算法在带有重启的轮次中运行，从平均迭代点集中输出一个均匀随机点，以确保收敛保证。

主要贡献与理论结果
本文建立了寻找 $(\delta, \epsilon)$ -Goldstein 驻点的理论保证，这是通过 Goldstein $\delta$ -次微分定义的针对非光滑函数的细化近似驻点概念。

收敛复杂度：ZOCOON 算法以随机零阶 oracle 复杂度 $O\left( d^{\frac{p}{2(p-1)}} \delta^{-1} \epsilon^{-\frac{2p-1}{p-1}} \right)$ 达到 $(\delta, \epsilon)$ -Goldstein 驻点。该结果在期望意义下和高概率下均成立。
维度依赖性：对维度 $d$ 的依赖性与凸非光滑设定下随机零阶优化的已知最佳结果一致。
精度依赖性：对精度参数 $\delta$ 和 $\epsilon$ 的依赖性与含重尾噪声的非凸非光滑问题下已知最佳的随机一阶算法一致。
平滑扩展：结果自然地扩展到平滑设定。通过设定 $\delta = \epsilon/H$ （其中 $H$ 是平滑常数），该方法以匹配平滑非凸优化最优随机一阶方法的复杂度达到 $\epsilon$ -驻点。

实验验证
在真实数据集（a9a, covtype, w8a）上的非凸惩罚 SVM 问题中进行了数值实验，并人为添加了重尾噪声（Pareto 分布）。

基线：将 ZOCOON 与 GFM [26]、GFM+ [5] 和 ZOO2N [25] 进行了比较。
发现：ZOCOON 和 ZOO2N 的收敛速度显著快于 GFM 和 GFM+。ZOCOON 在大多数数据集上表现出比 ZOO2N 更稳定的性能，验证了截断机制在处理重尾噪声方面的有效性。

意义与主张
本文声称填补了文献中的关键空白：尽管重尾噪声在实践中普遍存在，但现有的非凸非光滑优化零阶方法仅限于有界方差假设或凸设定。

首创性：ZOCOON 被呈现为含重尾噪声的非凸非光滑优化的首个高效随机零阶算法。
最优性：作者指出，对 $L$ 、 $\delta$ 和 $\epsilon$ 的依赖性与该类问题最近建立的下界相匹配，表明该方法在精度参数方面接近最优。
鲁棒性：这项工作表明，在一阶方法中常见的梯度截断技术可以成功适应零阶框架，以处理无界方差，同时不牺牲维度依赖性复杂度。

文章最后承认了未解决的问题，特别是维度依赖性是否最优，以及该框架是否可以扩展到约束优化问题。

1. 问题：“暴风雨”中的山脉

2. 解决方案：“截断”指南针（ZOCOON）

3. 目标：找到“足够好”的位置

4. 结果：为何有效

总结

技术摘要：含重尾噪声的零阶非凸非光滑优化

类似论文