基于Polyak步长的动量方法

Polyak Step-Size for Momentum Method

摘要: 近年来，动量方法广泛地应用在机器学习训练中。本文基于Polyak步长和移动平均动量(MAG)方法提出了一个新的动量方法(LAGP)，并将其与随机梯度结合，提出SLAGP方法。建立了LAGP方法在半强凸条件下的线性收敛性，以及SLAGP算法在半强凸条件下的线性收敛性。数值实验表明LAGP和SLAGP与其他流行算法相比有明显优势。

Abstract: Recently, momentum methods have been widely adopted in training machine learning. In this paper, based on the Polyak step-size and the Moving Average Gradient (MAG) method, a new momentum method (LAGP) is proposed. By combining it with the stochastic gradient, the SLAGP method is developed. The linear convergence of the LAGP method under the semi-strongly convex condition, and the linear convergence of the SLAGP algorithm under the semi-strongly convex condition are established. Numerical experiments show that LAGP and SLAGP have significant advantages compared with other popular algorithms.

1. 引言

机器学习被认为是人工智能(Artificial Intelligence, AI)领域中最前沿、最能够 体现智能、发展最快速的一个分支，它是人工智能的核心，是计算机获得“智能”的根本途径[1] [2]。机器学习中的大多数问题可归结为求解如下优化问题：

$\underset{x\in {ℝ}^d}{\min }f\left(x\right)=\frac{1}{n}{\displaystyle \sum _{i=1}^n{f}_i}\left(x\right),$

其中每个$f_i\left(x\right)$ 是损失函数。移动平均梯度(MAG)广泛用于求解上述优化问题, 其迭代格式为

$m_k=\nabla f\left(x_k\right)+\beta m_{k-1},x_{k+1}=x_k-\eta m_k,$

其中$\eta >0,\beta \in \left(0,1\right)$ 。当前主流的自适应动量方法如Adam、RMSProp等，通过结合历史梯度信息动态调整学习率，显著提升了非凸优化问题的训练效率。然而，这些方法在强凸或半强凸问题中可能存在收敛速度不足或超参数敏感性问题。MAG方法通过引入移动平均梯度有效缓解了噪声干扰，但步长固定限制了其泛化能力。

2. LAGP和SLAGP

首先，基于MAG算法提出LAG算法

$m_k={\beta }_1\nabla f\left(x_k\right)+{\beta }_2{m}_{k-1},x_{k+1}=x_k-\eta m_k,$

其中$\eta >0,{\beta }_1>0,{\beta }_2\in \left(0,1\right)$ 。借鉴Polyak步长[3] [4]的思想，求解

$\underset{{\eta }_k}{\min }{\Vert x_{k+1}\left({\eta }_k\right)-x^{*}\Vert }^2,$

得到

${\eta }_k=\frac{\langle m_k,x_k-x^{*}\rangle }{{\Vert m_k\Vert }^2},$

其中$x^{*}$ 是不可得的。所以，根据f的凸性，

${\Vert x_{k+1}-x^{*}\Vert }^2\le {\Vert x_k-x^{*}\Vert }^2-2{\beta }_1{\eta }_k\left[f\left(x_k\right)-f^{*}\right]+{\eta }_k^2{\Vert m_k\Vert }^2$

求解上式右边的最小值得到

${\eta }_k={\beta }_1\frac{f\left(x_k\right)-f^{*}}{{\Vert m_k\Vert }^2},$

其中$f^{*}=inff\left(x\right)$ 。结合LAG和上述步长提出LAGP算法，见算法1。与Adam通过一阶矩和二阶矩估计调整步长不同，LAGP直接利用Polyak步长公式动态计算最优步长，避免了二阶矩估计带来的计算开销。此外，LAGP的半强凸收敛性保证使其在条件数较大的问题上更具鲁棒性。

算法1：LAGP

输入：$x_0,{\beta }_1>0,{\beta }_2\in \left(0,1\right),m_0=0,T.$

1： for $t=1,2,\cdots ,T$ do

2： $m_k={\beta }_1\nabla f\left(x_k\right)+{\beta }_2{m}_{k-1}.$

3： ${\eta }_k={\beta }_1\frac{f\left(x_k\right)-f^{*}}{{\Vert m_k\Vert }^2},$

4： $x_{k+1}=x_k-{\eta }_k{m}_k$

5：end for

输出：$x_T.$

3. 收敛性分析

3.1. 确定优化

首先，给出两个关键的引理。

引理1 假设$m_k={\beta }_1\nabla f\left(x_k\right)+{\beta }_2{m}_{k-1},$ $m_{-1}=0,{\beta }_1>0,{\beta }_2\in \left(0,1\right)$ 。那么

${\Vert m_k\Vert }^2\le \frac{{\beta }_1^2}{1-{\beta }_2}{\displaystyle \sum _{j=0}^k{\beta }_2^{k-j}}{\Vert \nabla f\left(x_j\right)\Vert }^2$

且

${\displaystyle \sum _{k=0}^T{\Vert m_k\Vert }^2}\le \frac{{\beta }_1^2}{{\left(1-{\beta }_2\right)}^2}{\displaystyle \sum _{k=0}^T{\Vert \nabla f\left(x_k\right)\Vert }^2}。$

引理2 令f是凸的，并且$x^{*}$ 是最优解，那么对于LAGP生成的${\left\{x_i\right\}}_{i=0}^k,{\eta }_i\le {\beta }_1\left(f\left(x_i\right)-f^{*}\right)/{\Vert m_i\Vert }^2$ ，有$\langle m_{k-1},x_k-x^{*}\rangle \ge 0。$

进一步，如果f是L-光滑的，那么

$\langle m_{k-1},x_k-x^{*}\rangle \ge \frac{{\beta }_1}{2L}{\displaystyle \sum _{j=0}^{k-1}{\beta }_2^{k-1-j}}{\Vert \nabla f\left(x_j\right)\Vert }^2。$

定理1 假设f是L-光滑和μ-半强凸的，那么T步后，LAGP的迭代满足

${\Vert x_T-x^{*}\Vert }^2\le {\left(1-\frac{\left(1-{\beta }_2\right)\mu }{2L}\right)}^T{\Vert x_0-x^{*}\Vert }^2。$

证明：根据引理1和引理2，

$\begin{array}{c}{\Vert x_{k+1}-x^{*}\Vert }^2={\Vert x_k-x^{*}\Vert }^2-2\langle {\eta }_k{m}_k,x_k-x^{*}\rangle +{\Vert {\eta }_k{m}_k\Vert }^2\\ ={\Vert x_k-x^{*}\Vert }^2-2{\beta }_1{\eta }_k\langle \nabla f\left(x_k\right),x_k-x^{*}\rangle -2{\beta }_2{\eta }_k\langle m_{k-1},x_k-x^{*}\rangle +{\beta }_1{\eta }_k\left(f\left(x_k\right)-f^{*}\right)\\ \le {\Vert x_k-x^{*}\Vert }^2-2{\beta }_1{\eta }_k\left(f\left(x_k\right)-f^{*}+\frac{1}{2L}{\Vert \nabla f\left(x_k\right)\Vert }^2\right)\\ -2{\beta }_2{\eta }_k\langle m_{k-1},x_k-x^{*}\rangle +{\beta }_1{\eta }_k\left(f\left(x_k\right)-f^{*}\right)\\ \le {\Vert x_k-x^{*}\Vert }^2-{\beta }_1{\eta }_k\left(f\left(x_k\right)-f^{*}\right)-\frac{{\beta }_1{\eta }_k}{L}{\Vert \nabla f\left(x_k\right)\Vert }^2-2{\beta }_2{\eta }_k\frac{{\beta }_1}{2L}{\displaystyle \sum _{j=0}^{k-1}{\beta }_2^{k-1-j}}{\Vert \nabla f\left(x_j\right)\Vert }^2\\ ={\Vert x_k-x^{*}\Vert }^2-{\beta }_1{\eta }_k\left(f\left(x_k\right)-f^{*}\right)-\frac{{\beta }_1{\eta }_k}{L}{\displaystyle \sum _{j=0}^k{\beta }_2^{k-j}}{\Vert \nabla f\left(x_j\right)\Vert }^2\\ ={\Vert x_k-x^{*}\Vert }^2-{\beta }_1{\eta }_k\left(f\left(x_k\right)-f^{*}\right)-\frac{{\beta }_1^2\left(f\left(x_k\right)-f^{*}\right)}{L{\Vert m_k\Vert }^2}{\displaystyle \sum _{j=0}^k{\beta }_2^{k-j}}{\Vert \nabla f\left(x_j\right)\Vert }^2\\ \le {\Vert x_k-x^{*}\Vert }^2-\left({\beta }_1{\eta }_k+\frac{1-{\beta }_2}{L}\right)\left(f\left(x_k\right)-f^{*}\right)。\end{array}$

最后，根据f的μ-半强凸性，

${\Vert x_{k+1}-x^{*}\Vert }^2\le \left(1-\frac{\mu }{2}\left({\eta }_k+\frac{1-{\beta }_2}{L}\right)\right){\Vert x_k-x^{*}\Vert }^2\le \left(1-\frac{\left(1-{\beta }_2\right)\mu }{2L}\right){\Vert x_k-x^{*}\Vert }^2。$

证毕。

3.2. 随机优化

定义

$f_{s_k}\left(x\right)=\frac{1}{\left|s_k\right|}{\displaystyle \sum _{i\in s_k}f}\left(x;{\xi }_i\right),\nabla f_{s_k}\left(x\right)=\frac{1}{\left|s_k\right|}{\displaystyle \sum _{i\in s_k}\nabla }f\left(x;{\xi }_i\right)$

并且$\mathbb{E}{f}_{s_k}\left(x\right)=f\left(x\right)$ 和${\Vert x_{k+1}-x^{*}\Vert }^2\le \left(1-\frac{\mu }{2}\left({\eta }_k+\frac{1-{\beta }_2}{L}\right)\right){\Vert x_k-x^{*}\Vert }^2\le \left(1-\frac{\left(1-{\beta }_2\right)\mu }{2L}\right){\Vert x_k-x^{*}\Vert }^2$ ，以及$f_{s_k}^{*}=in{f}_x{f}_{s_k}\left(x\right)$ 。

结合随机梯度提出SLAGP，

$m_k={\beta }_1\nabla f_{s_k}\left(x_k\right)+{\beta }_2{m}_{k-1},$

${\eta }_k=\min \left\{{\beta }_1\frac{f\left(x_k\right)-f_{s_k}^{*}}{c{\Vert m_k\Vert }^2},{\eta }_{\max }\right\},$

$x_{k+1}=x_k-{\eta }_k{m}_k,$

其中$c>0,{\eta }_{\max }>0$ 。c用于控制随机梯度步长的衰减速率，${\eta }_{\max }$ 为避免步长过大导致发散的经验阈值。

假设1 ${\sigma }^2=\mathbb{E}\left[f_{s_k}\left(x^{*}\right)-f_{s_k}^{*}\right]\le \infty$ 。

引理3 对于凸函数, 如果步长${\eta }_k\le {\beta }_1\left(f_{s_k}\left(x_k\right)-f_{s_k}^{*}\right)/{\Vert m_k\Vert }^2$ ，那么对于任意的k大于等于1，LAGP的迭代满足

$\langle m_{k-1},x_k-x^{*}\rangle \ge {\beta }_1\left(1-\frac{1}{c}\right){\displaystyle \sum _{j=0}^{k-1}{\beta }_2^{k-1-j}}\left(f_{s_j}\left(x_j\right)-f_{s_j}^{*}\right)-{\beta }_1{\displaystyle \sum _{j=0}^{k-1}{\beta }_2^{k-1-j}}\left(f_{s_j}\left(x^{*}\right)-f_{s_j}^{*}\right)。$

定理2 假设$f_i$ 是L-光滑和μ-半强凸的，$\eta =\max {\left\{{\beta }_1\frac{f_{s_k}\left(x_k\right)-f_{s_k}^{*}}{{\Vert m_k\Vert }^2}\right\}}_{k=0}^T<\infty$ ，那么T步后，SLAGP的迭代满足

$\mathbb{E}{\Vert x_T-x^{*}\Vert }^2\le {\left(1-a_1\right)}^T{\Vert x_0-x^{*}\Vert }^2+\frac{2{\beta }_1\eta {\sigma }^2}{a_1\left(1-{\beta }_2\right)}，$

其中$a_1=\frac{\left(1-{\beta }_2\right)\left(c-1\right)\mu }{2c^{2}L}$ 。

证明：

$\begin{array}{c}{\Vert x_{k+1}-x^{*}\Vert }^2={\Vert x_k-x^{*}\Vert }^2-2{\eta }_k\langle m_k,x_k-x^{*}\rangle +{\Vert {\eta }_k{m}_k\Vert }^2\\ ={\Vert x_k-x^{*}\Vert }^2-2{\eta }_k\langle {\beta }_1\nabla f_{s_k}\left(x_k\right)+{\beta }_2{m}_{k-1},x_k-x^{*}\rangle +{\Vert {\eta }_k{m}_k\Vert }^2\\ \le {\Vert x_k-x^{*}\Vert }^2-2{\beta }_1{\eta }_k\left(f_{s_k}\left(x_k\right)-f_{s_k}\left(x^{*}\right)\right)-2{\beta }_2{\eta }_k\langle m_{k-1},x_k-x^{*}\rangle +{\Vert {\eta }_k{m}_k\Vert }^2\\ \le {\Vert x_k-x^{*}\Vert }^2-{\beta }_1{\eta }_k\left(2-\frac{1}{c}\right)\left(f_{s_k}\left(x_k\right)-f_{s_k}^{*}\right)+2{\beta }_1{\eta }_k\left(f_{s_k}\left(x^{*}\right)-f_{s_k}^{*}\right)\\ \le {\Vert x_k-x^{*}\Vert }^2-2{\beta }_1{\eta }_k\left(1-\frac{1}{c}\right){\displaystyle \sum _{j=0}^k{\beta }_2^{k-j}}\left(f_{s_j}\left(x_j\right)-f_{s_j}^{*}\right)+2{\beta }_1{\eta }_k{\displaystyle \sum _{j=0}^k{\beta }_2^{k-j}}\left(f_{s_j}\left(x^{*}\right)-f_{s_j}^{*}\right)。\end{array}$

根据光滑性，

${\displaystyle \sum _{j=0}^k{\beta }_2^{k-j}}\left(f_{s_j}\left(x_j\right)-f_{s_j}^{*}\right)\ge \frac{1}{2L}{\displaystyle \sum _{j=0}^k{\beta }_2^{k-j}}{\Vert \nabla f_{s_j}\left(x_j\right)\Vert }^2。$

又根据引理3，

$\begin{array}{c}{\eta }_k{\displaystyle \sum _{j=0}^k{\beta }_2^{k-j}}\left(f_{s_j}\left(x_j\right)-f_{s_j}^{*}\right)=\frac{{\beta }_1\left(f_{s_k}\left(x_k\right)-f_{s_k}^{*}\right)}{c{\Vert m_k\Vert }^2}{\displaystyle \sum _{j=0}^k{\beta }_2^{k-j}}\left(f_{s_j}\left(x_j\right)-f_{s_j}^{*}\right)\\ \ge \frac{\left(1-{\beta }_2\right)\left(f_{s_k}\left(x_k\right)-f_{s_k}^{*}\right)}{c{\beta }_1{\displaystyle \sum _{j=0}^k{\beta }_2^{k-j}}{\Vert \nabla f\left(x_j\right)\Vert }^2}\frac{1}{2L}{\displaystyle \sum _{j=0}^k{\beta }_2^{k-j}}{\Vert \nabla f_{s_j}\left(x_j\right)\Vert }^2\\ =\frac{\left(1-{\beta }_2\right)\left(f_{s_k}\left(x_k\right)-f_{s_k}^{*}\right)}{2cL{\beta }_1}。\end{array}$

那么，

$\begin{array}{c}{\Vert x_{k+1}-x^{*}\Vert }^2\le {\Vert x_k-x^{*}\Vert }^2-\frac{\left(c-1\right)\left(1-{\beta }_2\right)}{c^{2}L}\left(f_{s_k}\left(x_k\right)-f_{s_k}^{*}\right)+2{\beta }_1{\eta }_k{\displaystyle \sum _{j=0}^k{\beta }_2^{k-j}}\left(f_{s_j}\left(x^{*}\right)-f_{s_j}^{*}\right)\\ \le \left(1-\frac{\left(c-1\right)\left(1-{\beta }_2\right)\mu }{2c^{2}L}\right){\Vert x_k-x^{*}\Vert }^2+2{\beta }_1\eta {\displaystyle \sum _{j=0}^k{\beta }_2^{k-j}}\left(f_{s_j}\left(x^{*}\right)-f_{s_j}^{*}\right)。\end{array}$

对上述不等式取期望，

$\begin{array}{c}\mathbb{E}{\Vert x_{k+1}-x^{*}\Vert }^2\le \left(1-\frac{\left(c-1\right)\left(1-{\beta }_2\right)\mu }{2c^{2}L}\right)\mathbb{E}{\Vert x_k-x^{*}\Vert }^2+2{\beta }_1\eta {\displaystyle \sum _{j=0}^k{\beta }_2^{k-j}}{\sigma }^2\\ \le {\left(1-\frac{\left(c-1\right)\left(1-{\beta }_2\right)\mu }{2c^{2}L}\right)}^{k+1}{\Vert x_0-x^{*}\Vert }^2+\frac{4c^{2}L{\beta }_1\eta {\sigma }^2}{\left(c-1\right){\left(1-{\beta }_2\right)}^2\mu }。\end{array}$

证毕。

4. 数值实验

4.1. 最小二乘问题

考虑最小二乘问题：

$f\left(x\right)=\frac{1}{2}{\Vert Ax-b\Vert }^2$

其中$A\in {ℝ}^{d_1\times d}$ 是正定的，$b\in {ℝ}^{d_1}$ 。设置$d_1=d=1000$ 文以及$A^{T}A$ 的条件数$\kappa$ 是10,000。下面是与一些流行算法的对比，算法LAGP是明显优于其他算法的。

4.2. 逻辑回归问题

考虑逻辑回归损失：

$f_{Log\mathrm{Re}g}\left(w\right)=\frac{1}{n}{\displaystyle \sum _{i=1}^n\log \left(1+\exp \left(-y_i{x}_i^{T}w\right)\right)}$

其中$x_i\in {ℝ}^d,y_i\in \left\{-1,+1\right\}$ 。下面是在合成数据集上的算法对比图。实验参数设置如下：$c=5,{\eta }_{\max }=100$ ，与[4]中保持一致以确保公平性。

5. 总结

基于MAG算法提出LAG算法，并基于Polyak步长为LAG设计自适应步长，提出LAGP算法。计算大规模机器学习问题时，借助随机梯度，应用SLAGP算法。分析了不同条件下的算法收敛性，数值实验证明了有效性。实验结果表明，LAGP在最小二乘和逻辑回归任务中均显著优于一些流行的自适应算法。这表明基于Polyak步长的自适应策略能有效平衡方向更新与步长调整，为大规模机器学习优化提供了新思路。

NOTES

^*通讯作者。