在线到非凸转化框架破解复合优化最优复杂度难题

随机非光滑非凸复合优化是机器学习中一类覆盖面很广的问题——带约束的训练、正则化神经网络、稀疏学习等都可以归入这个框架。它的目标函数由两部分组成：一部分是可能非光滑的非凸Lipschitz函数，另一部分是凸正则项。前者通常只能通过随机梯度或函数值来访问，后者则具有良好的凸结构。

长期以来，这类复合问题的 oracle 复杂度分析一直存在空白。据该论文所述，在一阶访问（随机梯度）条件下，此前没有任何已知的复杂度上界；而零阶访问（函数值）条件下已有的复杂度结果也并非最优。这意味着，当我们用正则化方法训练神经网络或求解约束优化时，理论上并不知道需要多少次查询才能保证找到一个满足条件的稳定点。

复合优化为什么更难分析

非凸非光滑优化本身就是一块硬骨头。经典的非凸优化通常寻找梯度为零的点，但当函数不可微时，梯度的概念需要被更广义的稳定点条件替代。对于复合目标函数，还需要额外考虑正则项的结构如何与稳定点条件交互。

一个自然的思路是把复合问题拆开：对非凸部分求梯度，对凸正则项使用次梯度或近端算子。但这种拆分在复杂度分析中会引入额外的误差项，导致最终复杂度劣于非复合情形。此前零阶方法的结果正是受此困扰，复杂度中出现了对维度和精度更不利的依赖。

Goldstein 稳定点条件：对于可微非凸函数，常用的稳定点条件是梯度范数小于 ε；但对于非光滑或复合函数，梯度可能不存在或不可用，此时需要更宽松的稳定条件。Goldstein 稳定点（又称 Goldstein 条件）要求函数在某个半径 δ 的邻域内，所有点的梯度范数下界与函数值下降量满足某一不等式；直观地说，它保证了在当前点附近不存在一个方向能让函数值持续且显著地下降。当 δ 取遍所有可能半径时，若某点满足该条件，则它一定是局部极小点。在一阶随机优化中，由于不能精确计算梯度，通常需要采用随机 Goldstein 稳定点作为收敛目标，而 δ 的引入正是为了处理梯度估计的噪声。

近端算子与次梯度：对于复合目标 f(x)+h(x)（f 非光滑非凸，h 凸），当 h 不可微时（如 L1 正则），梯度下降无法直接应用。近端算子定义为 prox_{ηh}(v) = argmin_x { h(x) + (1/(2η))||x-v||^2 }，它相当于在点 v 处对 h 做一步隐式梯度下降，且不要求 h 可微。次梯度则是凸函数在不可微点处的梯度推广，满足 f(y) ≥ f(x) + g^T(y-x)。对于非凸的 f，次梯度可能不存在或不唯一，因此分析中常对 f 使用光滑化或随机梯度，而对凸的 h 使用近端算子或次梯度。这种混合处理方式虽然直观，但在复杂度分析中会引入额外的偏差项，导致最终速率变差。

在线学习视角下的统一算法框架

论文采用的核心工具是 online-to-nonconvex conversion（在线到非凸转化）框架。这个框架最初为非复合问题设计，思路是把优化过程看作一个在线学习问题：每一步由一个在线学习器选择更新方向，学习器的累积 regret 与最终稳定点的质量之间存在理论联系。

将这一框架推广到复合场景的关键在于为学习器设计新的损失函数。作者的做法颇具巧思：新损失函数直接包含正则项本身，而不是它的线性化近似。这样做的好处是保留了正则项的完整凸结构信息，使得在线镜像下降（online mirror descent）的一个变体能够实现低 regret。

这一改动使得正则项的凸性从"需要额外处理的对象"变成了"帮助控制 regret 的资源"，从而避免了复杂度退化。

在线镜像下降与 regret：在线镜像下降（OMD）是一种在线学习算法，它利用 Bregman 散度作为距离度量，每一步在保持与当前决策接近的同时最小化即时损失。对于一个凸的、Lipschitz 连续的在线损失序列，OMD 可以保证累积 regret 上界为 O(√T) 或 O(log T)，具体取决于损失函数的性质和步长选择。在在线到非凸转化框架中，regret 直接对应最终稳定点的质量：若在线学习器能保证低 regret，则通过适当转换，可以得到非凸优化中稳定点条件的收敛速率。因此，设计一个低 regret 的在线学习器成为关键，而将正则项 h(x) 直接放入损失函数而非线性化，正是利用了 h 的凸性来构造更紧的 regret 界。

最优 oracle 复杂度与实验验证

论文给出了两类复杂度结果。在一阶访问（随机梯度查询）下，算法找到满足 Goldstein 型稳定条件点所需的查询次数为 O(δ⁻¹ε⁻³)，其中 δ 是 Goldstein 半径，ε 是稳定容差。在零阶访问（函数值查询）下，复杂度为 O(dδ⁻¹ε⁻³)，d 是问题维度。

这两个结果与非复合非光滑非凸优化问题的最优复杂度完全一致，说明额外的凸正则项并没有使 oracle 复杂度变差。论文还给出了光滑情形下的对应速率，并通过数值实验验证了理论结果。

一阶与零阶 oracle 复杂度：oracle 复杂度衡量算法为达到某一精度所需的查询次数。一阶 oracle 允许查询函数在任意点的随机梯度，零阶 oracle 只允许查询函数值（通常通过有限差分估计梯度）。在非凸优化中，目标通常是找到一个 ε-稳定点，即梯度范数或稳定条件满足不超过 ε。对于非光滑非凸问题，已知最优一阶复杂度为 O(ε^{-3})，零阶复杂度为 O(d ε^{-3})。本文的复合设定下，额外引入的 Goldstein 半径 δ 出现在复杂度中作为 O(δ^{-1} ε^{-3})，这是因为随机梯度噪声需要更小的 δ 来保证稳定点质量。当 δ 固定时，该复杂度与非复合情形完全匹配，说明凸正则项没有带来额外负担。

理论意义与实践启示

这项工作填补了复合非凸优化在 oracle 复杂度上的一个理论空白。从实践角度看，它传递了一个积极信号：常用的正则化策略——无论 L1、L2 还是更一般的凸惩罚——在复杂度层面是"免费"的，不会让优化问题变得本质上更难求解。对于依赖正则化训练大规模模型的场景而言，这为算法设计提供了更坚实的理论依据。

当然，论文的结果是渐进复杂度意义上的，常数因子和实际收敛速度仍需通过实验进一步评估。从理论到工程落地之间，仍有值得探索的空间。