梯度下降中梯度收敛于0的证明思路求助（满足特定条件）

嘿，别慌！我来给你捋捋这个问题的关键思路，你卡在反证法上没进展，大概率是没用到Lipschitz梯度的核心不等式，还有可能漏掉了一个常见的隐含条件——函数$f$是有下界的（没有这个条件的话，结论其实不成立，后面我会给你举反例）。

先给你梳理完整的证明方向：

第一步：推导函数值的递减不等式 #

因为$\nabla f$是L-Lipschitz连续的，对于这类函数（也叫L-smooth函数），有一个经典的不等式：
$$f(y) \leq f(x) + \nabla f(x)^T(y - x) + \frac{L}{2}|y - x|^2$$
把梯度下降的迭代式$y = x^{(i+1)} = x^{(i)} - \tau \nabla f(x^{(i)})$代入进去，计算一下：
$$
\begin{align*}
f(x^{(i+1)}) &\leq f(x^{(i)}) + \nabla f(x^{(i)})T(-\tau \nabla f(x^{(i)})) + \frac{L}{2}|-\tau \nabla f(x^{(i)})|2 \
&= f(x^{(i)}) - \tau |\nabla f(x^{(i)})|2 + \frac{L \tau^2}{2} |\nabla f(x^{(i)})|2 \
&= f(x^{(i)}) - \tau\left(1 - \frac{\tau L}{2}\right)|\nabla f(x^{(i)})|2
\end{align*}
$$
因为$\tau < \frac{1}{L}$，所以$1 - \frac{\tau L}{2} > 0$，这说明每一步迭代后函数值都是单调不增的。

第二步：结合函数有下界的条件（关键！） #

如果$f$是有下界的（比如常见的凸函数、强凸函数都满足），那单调不增的函数值序列${f(x^{{(i)})}$必然收敛到某个有限值$f}*$。

第三步：利用级数收敛的性质推导梯度收敛 #

把上面的不等式从$i=0$到$i=N-1$累加起来：
$$f(x^{(N)}) \leq f(x^{(0)}) - \tau\left(1 - \frac{\tau L}{2}\right)\sum_{i=0}^{N-1}|\nabla f(x^{(i)})|2$$
当$N \to \infty$时，$f(x^{(N)}) \to f^$，所以：
$$\sum_{i=0}^\infty |\nabla f(x^{(i)})|2 = \frac{f(x^{(0)}) - f^}{\tau\left(1 - \frac{\tau L}{2}\right)} < \infty$$
也就是说这个级数是收敛的，而级数收敛的必要条件就是通项趋于0，所以$|\nabla f(x^{(i)})| \to 0$。

对你的反证法思路的补充 #

你假设存在$\epsilon > 0$，有无穷多个$j$使得$|\nabla f(x^{(j)})| \geq \epsilon$，那这个级数里就会有无穷多个项$\geq \epsilon^2$，级数必然发散，这和我们上面得到的级数收敛结论矛盾，所以假设不成立，梯度范数必须趋于0。

补充说明：没有下界的反例 #

如果$f$没有下界，结论是不成立的，比如取$f(x) = -\frac{1}{2}|x|^2$，它的梯度$\nabla f(x) = -x$是Lipschitz连续的（$L=1$），取$\tau = \frac{1}{2} < 1/L$，梯度下降迭代式是$x^{(i+1)} = x^{(i)} - \tau(-x^{(i)}) = \frac{3}{2}x^{(i)}$，显然$|\nabla f(x^{(i)})| = |x^{(i)}|$会趋于无穷，根本不会收敛到0。所以问题里应该默认$f$是有下界的，可能你没注意到这个隐含条件~

备注：内容来源于stack exchange，提问作者user1186418