Polyak–Łojasiewicz 条件

梯度很小，通常只说明当前位置的一阶变化不大。要把它解释为“距离全局最优值已经很近”，还需要把斜率与剩余目标差联系起来。PL条件正是这条联系；它不要求曲面处处向上弯，也不要求最小点只有一个。

形式陈述

定义与可以直接报告的量

考虑无约束优化问题 $\min_{x\in\mathbb R^d}f(x)$ ， $d\ge1$ ， $f$ 可微，最小值 $f^*$ 有限且被取得。固定欧氏内积及相应梯度。若存在 $\mu>0$ ，对全部 $x$ 都有

\frac12\|\nabla f(x)\|_2^2\ge\mu\bigl(f(x)-f^*\bigr), \tag{1}

就称 $f$ 满足参数为 $\mu$ 的Polyak–Łojasiewicz条件，简称PL条件。这里 $\mu$ 是经过证明的下界常数；有限个样本点上式(1)通过，不能证明它在整个空间成立。

式(1)立即给出函数值证书

0\le f(x)-f^*\le\frac{\|\nabla f(x)\|_2^2}{2\mu}. \tag{2}

因此梯度为零的点必是全局最小点。给定目标精度 $\varepsilon>0$ ，只需检查 $\|\nabla f(x)\|_2\le\sqrt{2\mu\varepsilon}$ 。计算这份后验上界不需要知道 $f^*$ 的数值，但需要真实梯度及有效的 $\mu$ 。

光滑条件下的梯度下降

另设梯度在整个空间为 $L$ -Lipschitz，取 $L>0$ 和 $0<\mu\le L$ 。执行精确梯度下降

x_{k+1}=x_k-\frac1L\nabla f(x_k).

则

f(x_k)-f^*\le\left(1-\frac\mu L\right)^k\bigl(f(x_0)-f^*\bigr). \tag{3}

参数 $\mu$ 可以向下缩小而仍有效。对非恒定的全局光滑PL函数，实际上必有 $\mu\le L$ ：下降引理与 $f^*\le f(x-\nabla f(x)/L)$ 给 $\|\nabla f(x)\|^2\le2L(f(x)-f^*)$ ，再在某个目标差为正的点与式(1)比较即可。恒定函数的目标差处处为零，直接结束，不用讨论一个负的“收缩因子”。

直觉

为什么一条斜率下界足够

下降引理给一次更新的实际收益：

f(x_{k+1})\le f(x_k)-\frac1{2L}\|\nabla f(x_k)\|^2.

式(1)又说，只要还剩目标差 $h_k=f(x_k)-f^*>0$ ，梯度就不能比 $\sqrt{2\mu h_k}$ 更小。两式合起来是

h_{k+1}\le h_k-\frac\mu Lh_k.

反复代入便得到式(3)。证明里没有用切平面的全局凸下界；真正需要的是每步可支付的下降量与剩余差之间有固定比例。

“几何率”指目标差乘上一个小于一的固定因子，并非说所有坐标都按同一比例收缩。若极小点组成一整条直线，同样可以迅速降低目标，却不能据此声称到达这条线上的某个指定点。

强凸性为什么足够但不是定义

若 $f$ 在全空间可微且$\mu$-强凸，其一阶下界是

f(y)\ge f(x)+\langle\nabla f(x),y-x\rangle+\frac\mu2\|y-x\|^2.

令 $y$ 为一个最小点，再把右边的二次表达式向所有位移取下界，得到

f^*\ge f(x)-\frac{\|\nabla f(x)\|^2}{2\mu}.

这就是式(1)。强凸性控制任意两点的弯曲；PL只要求当前位置的梯度足以解释它与最优值的差。后者可以在缺少前者时成立。

例子与边界

非唯一解仍有精确PL常数

令 $f(x_1,x_2)=x_1^2/2$ 。则 $f^*=0$ ， $\nabla f=(x_1,0)$ ，式(1)以 $\mu=1$ 取等。所有 $(0,c)$ 都是最小点，所以 $f$ 不强凸。

从 $(1,100)$ 以步长1更新得到 $(0,100)$ ，目标误差立即为零；它到指定最小点 $(0,0)$ 的距离仍为100。式(2)认证的是目标差，不能把它的右侧直接改名为到任意所选最小点的距离。

一个全局光滑、确实非凸的例子

考虑

f(x)=x^2+\frac32\sin^2x,\qquad f'(x)=2x+\frac32\sin2x,\qquad f''(x)=2+3\cos2x. \tag{4}

$f\ge0$ 且仅在 $x=0$ 取零。二阶导数位于 $[-1,5]$ ，所以梯度是5-Lipschitz；在 $x=\pi/2$ 处二阶导数为 $-1$ ，故它非凸。

下面不靠绘图估计PL常数。对 $0\le x\le\pi/2$ ， $\sin2x\ge0$ ，因而 $f'(x)\ge2x\ge x$ 。对 $x\ge\pi/2>3/2$ ，有 $f'(x)\ge2x-3/2\ge x$ 。 $f'$ 是奇函数，于是全实轴上 $|f'(x)|\ge|x|$ 。再用 $|\sin x|\le|x|$ ：

f(x)\le\frac52x^2, \qquad \frac12|f'(x)|^2\ge\frac12x^2\ge\frac15 f(x).

因此 $\mu=1/5$ 有效。步长 $1/5$ 的GD有收缩上界 $24/25$ ；负曲率没有破坏这份全局函数值证明。

光滑凸也可能没有全局PL常数

取 $f(x)=\sqrt{1+x^2}-1$ 。它凸、最小值为零，且 $f''(x)=(1+x^2)^{-3/2}\le1$ 。但 $|f'(x)|\le1$ ，而 $f(x)\to\infty$ 。若式(1)存在固定 $\mu>0$ ，左侧至多 $1/2$ ，右侧却无界，矛盾。

只在某个区域内成立的PL条件，只能用于留在该区域内的迭代。随机梯度也不能直接放进式(2)：一个偶然接近零的估计量不证明真实梯度小。若已有确定性误差界 $\|\widetilde g-\nabla f(x)\|\le\delta$ ，三角不等式才给可用上界 $(\|\widetilde g\|+\delta)^2/(2\mu)$ 。

推论与应用

预算与停止

若知道初始目标差上界 $H_0\ge f(x_0)-f^*$ ，记 $\rho=1-\mu/L\in(0,1)$ 。当 $H_0>\varepsilon$ 时，充分预算是

k\ge\left\lceil\frac{\log(H_0/\varepsilon)}{-\log\rho}\right\rceil.

若 $H_0\le\varepsilon$ ，零步已足够；若 $\rho=0$ ，一次更新达到最优值。预算每轮计一次梯度与 $O(d)$ 向量运算，后验停止检查若需在新点另求梯度，也应计入查询数。

式(4)从 $x_0=1$ 出发有 $H_0=5/2$ 。用有理数比较 $(5/2)(24/25)^k$ 与 $1/100$ ，最小充分整数为136。它是这份保守上界首次认证的预算，不是实际轨迹首次达标的轮数；实际梯度后验证书可能更早通过。

近似梯度的误差底

以 $\widetilde g_k=\nabla f(x_k)+e_k$ 执行步长 $1/L$ 。下降引理展开平方给

h_{k+1}\le\rho h_k+\frac{\|e_k\|^2}{2L}.

若每轮 $\|e_k\|\le\delta$ ，递推求和得到

h_k\le\rho^kh_0+\frac{\delta^2}{2\mu}(1-\rho^k).

因此恒定误差预算一般留下非零误差底。以一维 $f(x)=\mu x^2/2$ 、 $L=\mu$ 、固定误差 $e_k=\delta$ 为例，一步后停在 $-\delta/\mu$ ，目标差恰为 $\delta^2/(2\mu)$ ，说明这一项有实际机制。

历史更新的综合证书继续比较PL的函数值预算、重球的二阶模态、Anderson真实残差与删原子后的可行gap；这些停止量各自有明确前提。

参考资料

Hamed Karimi、Julie Nutini、Mark Schmidt，Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak–Łojasiewicz Condition，2016，§2、Theorem1、AppendixB，PDF pp.2–3、14。本文采用真正的梯度Lipschitz条件，非凸例的系数及常数由式(4)自行核算。

形式陈述 ​

定义与可以直接报告的量 ​

光滑条件下的梯度下降 ​

为什么一条斜率下界足够 ​

强凸性为什么足够但不是定义 ​

非唯一解仍有精确PL常数 ​

一个全局光滑、确实非凸的例子 ​

光滑凸也可能没有全局PL常数 ​

预算与停止 ​

近似梯度的误差底 ​

反向链接