技术摘要：具有方差缩减特性的自适应外推近端梯度法

问题表述

本文研究复合非凸有限和最小化问题，其形式化表示为：
$$\min_{x \in \mathbb{R}^n} F(x) \triangleq f(x) + h(x), \quad \text{其中} \quad f(x) \triangleq \frac{1}{N} \sum_{i=1}^N f_i(x)$$
此处，$f(\cdot)$ 是一个可微的、可能是非凸的函数，代表经验损失；$h(\cdot)$ 是一个适当的、下半连续的函数，它可以是非凸、非光滑且非利普希茨（non-Lipschitz）的。函数 $h(x)$ 作为正则项，用于引入先验信息，如稀疏性、低秩属性或正交约束。假设 $h(x)$ 的广义近端算子是可计算的。这种问题结构在机器学习应用中广泛存在，包括稀疏相位检索、特征值问题以及带有结构化正则化的神经网络训练。

方法论

作者提出了 AEPG-SPIDER（具有 SPIDER 特性的自适应外划近端梯度法），这是一种整合了三种加速技术的创新算法：

1. 自适应步长（Adaptive Stepsizes）： 与依赖历史梯度范数的现有自适应方法（如 AdaGrad-Norm）不同，AEPG-SPIDER 根据过去迭代之间的差异（$d_t = x_{t+1} - x_t$）来更新其步长因子 $v_t$。该方法利用坐标级步长，采用对角预处理器来对更新进行缩放。这种机制为累积梯度量较小的坐标分配更大的步长，从而促进稀疏维度的快速学习。
2. Nesterov 外推（Nesterov's Extrapolation）： 该方法通过外推参数 $\sigma_t$ 引入了类似于动量的更新。文中引入了一种针对该系数的新型递归更新规则：$\sigma_t = \theta(1 - \sigma_{t-1}) \min(v_t \div v_{t+1})$，其中 $\theta \in [0, 1)$。这使得算法能够在不需要固定外推参数的情况下，利用过去的迭代实现加速。
3. 方差缩减（SPIDER）： 为了高效处理有限和结构，算法采用了 SPIDER（随机路径积分微分估计器）框架。该估计器通过平衡周期性的全梯度计算与随机小批量梯度，生成低方差的梯度估计，从而降低了与全梯度方法相比的单次迭代计算成本。

在全批次、非随机设置下，AEPG-SPIDER 简化为 AEPG，它保留了自适应和外推特性，但以确定性方式运行。

核心贡献

本文做出了以下理论与实践方面的贡献：

• 首个无利普希茨常数的最优方法： 据作者所知，AEPG 和 AEPG-SPIDER 是首批无需依赖任何利普希茨常数（Lipschitz-free）即可在复合非凸最小化问题中达到最优迭代复杂度的算法。
• 最优迭代复杂度：
  • AEPG（确定性）在寻找 $\epsilon$-近似驻点方面达到了 $O(N\epsilon^{-2})$ 的迭代复杂度。
  • AEPG-SPIDER（随机性）实现了 $O(N + \sqrt{N}\epsilon^{-2})$ 的最优复杂度。通过消除次优的对数因子，它改进了之前的方差缩减方法（如 ADA-SPIDER）。
• 非遍历收敛率（Non-Ergodic Convergence Rates）： 在 Kurdyka-Lojasiewicz (KL) 假设下，本文建立了非遍历收敛率。具体而言，若 KL 指数为 0，则方法在有限步内收敛；对于指数在 $(0, 1/2]$ 范围内的情形，表现为线性收敛；对于指数在 $(1/2, 1)$ 范围内的情形，表现为次线性收敛。
• 新型分析框架： 收敛性证明依赖于新开发的充分下降条件以及一种能够处理自适应步长、外推与方差缩减之间相互作用的递归不等式。

实验结果

作者通过两个不同问题的实验验证了所提方法：

1. 稀疏相位检索： 将 AEPG-SPIDER 与最先进的方法（ProxSARAH, SpiderBoost, SGP-SPIDER）在真实和合成数据集上进行了基准测试。结果表明，当外推参数 $\theta$ 接近但严格小于 1 时，AEPG-SPIDER 的收敛速度更快。
2. 线性特征值问题： 将 AEPG 与 APG, FOForth, 和 OptM 进行了对比。在各种数据集上，所提方法在目标函数值随时间下降方面均表现出更优越的性能。

实验结果强调，所提自适应方法在稀疏、结构化数据集上表现异常出色，而在稠密、随机生成的数据集上的表现与现有方法相当。

重要性与主张

本文声称，AEPG-SPIDER 和 AEPG 通过将自适应步长策略、Nesterov 外推和方差缩减统一在一个框架内，代表了非凸优化领域的重要进展。其主要意义在于实现了无需获知利普希茨常数的（Lipschitz-free）最优迭代复杂度，而这在实际优化中是一个常见的瓶颈。此外，在 KL 假设下建立的最后迭代（last-iterate）收敛率，比许多现有随机方法中标准的遍历收敛率提供了更强的理论保证。作者将这些算法定位为处理同时存在非凸性和非光滑性的大规模复合最小化问题的鲁棒工具。