一、梯度法复杂度总结

• 对于 -光滑但非凸的 ，最速下降法（Steepest Descent）收敛速率为
• 对于 -光滑且凸的 ，
• 若 还是 -强凸，则线性收敛速率

二、重球法（Heavy Ball Method）

1、适用范围

适合凸二次型函数：

其中 对称，特征值落在 ，即 是 -光滑且 -强凸。

2、迭代公式

• 第一步是梯度下降，第二项是动量项（momentum）。

3、收敛性定理（无需证明）

令

则存在常数 ，有

• 若 ，，（退化为普通梯度下降）。
• 若 ，，。

4、目标函数收敛速率

利用 -光滑性，

近似有

5、与最速下降法比较

• 若 ，则重球法每步目标函数减少三分之一 。
• 最速下降法每步仅减少 ，。
• 重球法对病态（ill-conditioned）问题优势明显。

三、Nesterov加速梯度法（Nesterov Acceleration）

3.1 算法思想

Nesterov加速法是重球法的推广，适用于一般强凸目标。

标准形式

• 与重球法的区别：梯度在 处计算。

2、收敛性定理（强凸情形）

若 -光滑且 -强凸，取

则

• 加速收敛，。
• 例如 ，Nesterov每步减少 ，而最速下降法仅 。

四、Nesterov加速法（L-光滑凸函数）

1、算法步骤

适用于 -光滑凸，L不一定已知。算法采用两组变量 ，并自适应步长。

算法流程：

1. 设 ，，，。
2. 对 ，重复：
   1. 用回溯线搜索找最小 使 令
3. 直到 足够小。

关键点

• 回溯线搜索保证步长不会太小或太大。
• 控制动量，数值上渐进变大，增加加速效果。

2、理论最优复杂度

• 该方法的迭代复杂度为 ，即达到 只需 步。
• 这是理论上最优的复杂度。

五、收敛性分析（以Nesterov加速为例）

1、主要结论

设 为 -光滑凸函数，有极小点 ，则算法产生的序列满足

因此，-最优所需迭代步数为

2、关键推导步骤（简要概述）

• 定义辅助变量 ，随 增大逐步变大。
• 通过一系列递推与凸性、不等式，建立 的范数递推关系。
• 用望远镜求和技巧，最终得出 的上界随 衰减。

六、算法直观理解

• 动量思想：通过利用前一步的信息，使得算法能够“沿谷底滑行”，减少传统梯度法的锯齿状（zig-zag）慢收敛。
• 自适应步长：当L未知时，算法自动调整步长，避免手动设置不当导致的收敛慢或不收敛。
• 理论最优：加速梯度法已达到理论上最优的迭代复杂度。