随机自适应优化方法的末点迭代与几乎必然收敛统一理论框架

《Artificial Intelligence》：A unified theoretical framework for the last-iterate convergence of stochastic adaptive optimization

本文提出一种名为“AdaFamily”的通用理论分析框架，为一系列非凸场景下的随机自适应优化算法（如带有有界自适应步长的随机动量法和有界梯度的随机Adam法）建立了末点迭代与几乎必然收敛的保证。该框架不依赖于算法更新方向与有效步长的具体形式，旨在弥合理论分析与实际应用之间的差距，为深度学习领域的优化算法设计提供了新的理论见解。

　　

研究亮点

• •
  我们为一系列在非凸场景下的随机优化方法建立了一个统一的末点迭代与几乎必然收敛分析框架。如第3节所示，我们的分析框架不要求算法的搜索方向和有效步长更新具有特定形式。我们同时也利用提出的框架分析了两种自适应方法的收敛性：带有有界自适应步长的随机动量法和有界梯度的随机Adam法，证明了其有效性。主要的收敛结果在表1中做了简要总结。
• •
  对于非凸目标，我们重点关注自适应方法梯度序列的收敛表现。如表2、表3最后一列所示，我们的分析表明，末点迭代的梯度范数在期望意义下收敛，即 lim_T→∞E[‖?F(x_T)‖] = 0，这比现有关于最小迭代和随机迭代的研究更具实际意义。此外，我们还为最小迭代输出了一个几乎必然收敛速率 o(1/T^1/2-ε)。
• •
  对于Polyak-?ojasiewicz (PL) 函数，我们研究了末点迭代处函数值的几乎必然收敛行为。特别地，我们提供了确保函数值几乎必然收敛于目标函数下界的充分条件，即 lim_T→∞F(x_T) = F^*a.s.。此外，本文获得的几乎必然收敛速率可以无限接近 o(1/T)，与之前的期望结果相当。另外，我们还表明，在更灵活的步长选择α_t= Θ(1/t^p)（p ∈ (0, 1]）下，自适应算法在期望意义下以 O(1/T^p) 的速率收敛。

结论

本文提出了一个新颖的理论框架，用于分析在非凸场景下随机优化方法的收敛性。具体来说，我们的分析框架独立于搜索方向和有效步长的具体迭代形式，因此可应用于各种随机算法。通过利用所提出的框架，我们为一系列随机自适应方法建立了末点迭代与几乎必然收敛的保证。与之前聚焦于最小迭代和随机迭代输出的工作相比，我们证明了在更贴近实际算法实现的末点迭代输出下，梯度范数在期望意义下收敛于零。同时，我们首次获得了最小迭代梯度范数的几乎必然收敛速率。对于满足Polyak-?ojasiewicz (PL)条件的函数，我们证明了末点迭代的函数值几乎必然收敛于最优值，并获得了函数值的期望和几乎必然收敛速率。