技术摘要：非凸与随机平滑优化的投影梯度法

问题表述

本文研究了在凸紧集 $X \subseteq \mathbb{R}^n$ 上最小化光滑（可能非凸）函数 $f$ 的问题：
$$f^* := \min_{x \in X} f(x)$$
假设目标函数 $f$ 连续可微，且其梯度具有 $L$-Lipschitz 连续性。关键在于，作者引入了一个下曲率参数 $l \in [0, L]$，使得 $f$ 是 $l$-弱凸的：
$$f(x) - f(y) - \langle \nabla f(y), x - y \rangle \geq -\frac{l}{2}\|x - y\|^2$$
这一统一框架允许在单一理论分析中处理凸（$l=0$）和非凸（$l>0$）问题。该研究进一步扩展到随机优化场景，其中仅可获得含噪的一阶信息（随机梯度），并在随机算子具有额外平滑性假设的情况下，扩展到方差缩减场景。

方法论

本文构建了一个投影梯度（PG）方法的层次体系，从确定性方法逐步推进到随机方法，最终到达方差缩减场景，并特别关注自调节步长策略，此类策略无需预先知道 Lipschitz 常数或进行线搜索。

1. 确定性投影梯度（PG）

作者首先分析了标准的常数步长 PG 方法。通过同时利用上曲率 $L$ 和下曲率 $l$，他们推导出了一个新颖的收敛界，统一了凸和非凸情况的复杂度。

2. 自调节投影梯度（AC-PG）

为了解决估计全局 Lipschitz 常数 $L$ 的实际困难，作者提出了AC-PG。这种无参数方法：

• 利用前次迭代的函数值和梯度等一阶信息，在每次迭代中估计局部 Lipschitz 常数 $L_t$。
• 基于过去估计值（$\hat{L}_{t-1}$）的最大值更新步长 $\gamma_t$。
• 通过将迭代划分为“段”来处理对 $L$ 的潜在低估。当局部估计急剧增加时，新的一段开始。分析表明，此类段的总数是对数级的，且由低估引起的误差是有界且可求和的。

3. 随机投影梯度（SPG）与 AC-SPG

该框架被扩展到随机场景，其中存在具有有界方差 $\sigma^2$ 的无偏随机算子 $G(x, \xi)$。

• SPG：分析了一种小批量随机 PG 方法，将下曲率 $l$ 纳入样本复杂度界中。
• AC-SPG：开发了一种无参数变体。它采用两个估计器来估计局部 Lipschitz 常数：
  • 估计器 I：局部平滑度估计值的平均值。
  • 估计器 II：基于最大值的估计器，更为保守。
    作者证明，使用估计器 II 并结合足够大的批量大小进行估计，该方法能够在随机噪声存在的情况下，保留依赖于 $l$ 的统一复杂度界。
• 高概率保证：提出了一种两阶段算法（2-AC-SPG）以获得 $(\epsilon, \delta)$-平稳解。它运行多次独立试验并选择投影梯度最小的解，在轻尾假设下，将关于置信参数 $\delta$ 的依赖关系从多项式级改进为对数级。

4. 方差缩减随机 PG（VR-SPG）与 AC-VR-SPG

为了改善样本复杂度，作者引入了适用于投影梯度方法的方差缩减技术（类似于 SVRG/Spider）。

• VR-SPG：使用递归梯度估计器，通过小批量进行更新，并每隔 $T$ 次迭代重置为全批量。
• AC-VR-SPG：一种自调节变体，无需线搜索即可动态估计局部 Lipschitz 常数。它利用双循环结构和两个不同的局部平滑度估计器来管理步长。

主要贡献与结果

1. 统一复杂度界

本文建立了新的迭代和样本复杂度界，通过显式利用下曲率参数 $l$，统一了凸和非凸优化。

• 确定性 PG：实现了 $O\left(\frac{LD_X}{\epsilon} + \frac{LlD_X^2}{\epsilon^2}\right)$ 次迭代。对于凸问题（$l=0$），这简化为 $O(LD_X/\epsilon)$，与凸 PG 的精确速率相匹配。对于非凸问题，它与加速方法的已知最佳界相匹配。
• 随机 SPG：实现了 $O\left(\frac{LD_X}{\epsilon} + \frac{LlD_X^2}{\epsilon^2} + \frac{LD_X\sigma^2}{\epsilon^3} + \frac{LlD_X^2\sigma^2}{\epsilon^4}\right)$ 的样本复杂度。这是首个将 $l$ 纳入的 SPG 结果。
• 方差缩减 VR-SPG：在随机梯度 Lipschitz 连续的假设下，样本复杂度改进为 $O\left(\frac{\bar{L}D_X}{\epsilon} + \frac{\bar{L}lD_X^2}{\epsilon^2} + \frac{\sigma^2}{\epsilon^2}\log\frac{\sigma}{\epsilon} + \dots\right)$。这是首个利用下曲率 $l$ 的非凸随机优化 $O(1/\epsilon^3)$ 复杂度界。

2. 无参数（自调节）方法

本文引入了 AC-PG、AC-SPG 和 AC-VR-SPG，它们：

• 不需要输入 $L$、$l$ 或 $\sigma$。
• 不需要线搜索或回溯。
• 实现了与其有参数对应方法相同的复杂度界（仅相差与初始估计相关的附加对数项）。
• 理论分析证明，对 Lipschitz 常数低估所产生的误差是受控的，从而确保了收敛性。

3. 高概率保证

提出的两阶段 2-AC-SPG 方法为非凸随机优化提供了高概率收敛保证，将关于失效概率 $\delta$ 的依赖关系从多项式因子改进为对数因子。

意义与主张

作者声称其工作具有以下重要意义：

• 统一性：他们提供了首个统一的梯度下降类方法复杂度分析，通过利用下曲率 $l$，无缝覆盖了凸和非凸场景。
• 无参数效率：他们证明了“自调节”方法可以在没有线搜索计算开销或无需预先知道问题参数（Lipschitz 常数）的情况下，实现最优或近最优速率。
• 随机优化进展：他们建立了随机非凸优化的新且更紧的样本复杂度界，特别是表明当利用下曲率时，即使在非凸设置下，方差缩减也能实现 $O(1/\epsilon^3)$ 速率。
• 实用性：在箱约束二次规划（box-constrained quadratic programming）和半监督 SVM 上的数值实验证实，自调节方法具有鲁棒性，即使从对 Lipschitz 常数的显著低估开始也是如此，并且方差缩减显著加速了收敛。

本文结论认为，这些方法为大规模非凸和随机优化提供了一种理论健全且实践有效的途径，弥合了理论最优性与参数调整的实际约束之间的差距。