知识点：Nesterov加速算法

知识点概述

Nesterov加速算法是对（近似点）梯度下降法的一种重要改进，它通过引入一个“动量”（Momentum）项，显著改善了算法的收敛速度。对于梯度利普希茨连续的凸函数，它将梯度法的收敛率从 $O (1/ k)$ 提升到了最优的 $O (1/ k^{2})$ 。

动机: 普通梯度下降法步子太“短视”，只利用当前点的梯度，导致收敛慢。
核心思想 (动量): 下一步的更新方向不仅考虑当前点的梯度，还融合了之前迭代的动量。
算法 (FISTA): FISTA (Fast Iterative Shrinkage-Thresholding Algorithm) 是Nesterov加速思想在近似点梯度法上的一个流行实现。其迭代步骤为：
1. $y_{k} = x_{k} + \frac{k - 1}{k + 2} (x_{k} - x_{k - 1})$ (动量步：在一个“预判”点上计算梯度)
2. $x_{k + 1} = prox_{{} α_{k} g} (y_{k} - α_{k} \nabla f (y_{k}))$ (标准的近似点梯度步) 直观上，算法不是在当前位置 $x_{k}$ 寻找下一步，而是在一个顺着之前方向稍微“前冲”一点的位置 $y_{k}$ 上进行梯度下降和邻近操作。
收敛速度:
- 对于凸问题，收敛率为 $O (1/ k^{2})$ 。
- 对于强凸问题，可以达到线性收敛，且收敛常数更优。