为何需要复合方法
不少优化问题具有“光滑的数据拟合项加简单的非光滑惩罚项”的形式,例如最小二乘项加上 范数的倍数。惩罚项不可微,所以不能直接用梯度下降;对惩罚项取次梯度步只能得到较慢的速率。近端梯度法利用这一结构:对光滑部分走一个梯度步,再精确处理惩罚项,只要近端映射有闭式就可直接计算。本单元以绝对值的近端映射(软阈值)、凸函数的次梯度运算,以及投影梯度单元所用的 Lipschitz 梯度下降不等式为基础。
定义与基本假设
考虑
假设:
- 为凸且可微,且 对某个 为 -Lipschitz。于是对所有 ,
- 为凸(处处有限,因而连续),但不必可微。
- 在某点 取得最小值 。
定义 9.2.1
(近端映射)
对 及 , 的近端映射定义为
该目标函数连续、强凸,且当 时趋向 ,故最小点存在且唯一。当 时,该映射逐分量作用为阈值 的软阈值;当 时为恒等映射。
引理 9.2.2
(近端映射的刻画)
当且仅当 。
证明
(强凸子问题的最优条件)
函数 为凸且有限,故 为其最小点当且仅当 属于它在 处的次微分。二次项可微,所以和的次微分为 。因此条件即 。
定义 9.2.3
(近端梯度法)
步长为 、初始点为 的近端梯度法产生
当 时就是梯度下降。当 为闭凸集的示性函数(并非处处有限,但同样的公式仍适用)时,近端映射即欧氏投影,该方法即投影梯度法。当 时,即迭代软阈值算法(ISTA)。
概念视角分析
每一步都在极小化一个二次上界模型
配方可得
这个方法只把 线性化,加上一个邻近项,而保留 不变。当 时,下降不等式使这个模型 成为 的上界,并在 处等于 ,所以 :在证明任何收敛速率之前,就已得到单调下降。
不动点即极小点
命题 9.2.4
(不动点恰好是极小点)
设 。点 极小化 当且仅当 。
证明
(两个次梯度不等式相加)
由刻画引理,不动点方程等价于 。若此式成立,则对每个 有 ,而由 为凸,。相加得 。反之,若 极小化 ,则由和法则 ,即上述包含关系。
因此该方法恰好停在极小点,且不动点集合与步长无关。
单步不等式
定理 9.2.5
(单步不等式)
设 ,,。则对每个 ,
证明
(三个不等式与一个极化恒等式)
记 (梯度映射)。对点 应用刻画引理,得 。次梯度不等式给出
由光滑性不等式及 ,
又由凸性 。将三式相加,项 与 合并为 ,恰与第一式带来的项 抵消。剩下
而 ,且 。故 ,最后一项与 抵消。
证明透视
单步不等式中每个假设用在哪里
三个不等式各用掉一个假设: 处的次梯度不等式经刻画引理使用 的凸性,下降不等式使用 Lipschitz 梯度, 处的下界使用 的凸性。步长限制只出现一次,就是把 换成 的那一步。 的线性项能够抵消,是因为三个不等式分别锚定在 、 与 ,合起来形成一个闭环。关键一步是极化恒等式:它把剩下的内积 改写成到 的距离平方之差,再减去 ,而这个负项恰好吸收下降不等式的二次项。若 ,右边会留下正的余项 ,速率证明中的裂项相消就无法闭合。
收敛速率
定理 9.2.6
(目标值差距的 O(1/k) 上界)
设 ,。则迭代满足 ,且对每个 ,
证明
(把单步不等式裂项相消)
在单步不等式中取 ,得 。取 并对 求和,距离平方项裂项相消:
由于函数值不增, 个被加项每项都至少为 。除以 即得结论。
这个上界是次线性的:要把差距减半,所需迭代次数要加倍。它只是关于目标值的陈述。证明也显示 (因为每项 非负),但没有给出距离的收敛速率。
例题
例题 9.2.7
(一步即解的标量问题)
令 ,,故 。 的极小点为 ,其中 ,且 。
取 及任意 ,则 ,故 :一步即精确。
例题 9.2.8
(同一问题,步长减半)
保留 与 ,但取 、。梯度步为 ,阈值为 。于是 ,;,;,。一般地 :只要梯度步的结果大于阈值,就有 ,即 。这里迭代几何收敛,因为 强凸,比速率定理的假设更强。在 处检验:,而上界为 。
例题 9.2.9
(稀疏分量只在极限处为零的二维 lasso)
令 ,,,。则 ,其 Lipschitz 常数为 。取 (阈值也为 ),。
梯度步给出 及 。因此第一分量每步之后都等于 ;第二分量只要 ,就有 。从 开始,迭代为
即 ,极限为 。用不动点检验最优性:,故 ,以 软阈值后得 。此例中稀疏分量只在极限处才等于零,并非在有限步内。
在 处检验速率定理。;。,故差距为 。上界为 ,成立。
常见错误与细节
常见错误
(先取近端映射再走梯度步)
近端映射作用于梯度步之后的点 ,而不是 。先对 取近端再走梯度步是另一种方法,一般而言是错的。
常见错误
(按惩罚项选择步长)
只需要 为 Lipschitz。惩罚项 可以不可微,其 Lipschitz 性质与步长无关。
常见错误
(把 O(1/k) 上界读成迭代点的结论)
是最后一次迭代目标值的上界。它并不表示迭代点收敛更快,也不表示 的支撑集在有限步后等于 的支撑集。
另外两点涉及假设本身。
- 的凸性用了两次:近端映射的唯一性,以及单步不等式中的次梯度不等式。若 非凸,近端映射可能多值,速率定理不再成立。
- 方法是否实用取决于近端映射是否便宜。软阈值以及到方盒或球上的投影有闭式;一般的 可能需要内层求解器,此时定理不适用于不精确迭代。
反例模式
步长过长可使方法发散
条件 是充分而非必要的,但必须有某种上界。取 (故 )、、、。迭代为 ,所以迭代点为 ,且 ,而 。任何 形式的上界都不可能成立。对这个 ,每个 都收敛(见下面关于步长的练习),所以定理的条件 虽然保守,却不能直接删去。
练习
快速检查
(令 ,,,。计算 并验证它极小化 。)
阈值是 乘以惩罚权重。
解答
梯度步为 ,阈值为 ,故 。验证最优性:对 ,,在 处为零( 与所用符号一致)。由于 为凸, 即极小点。
快速检查
(令 ,,,。计算 ,并判断方法是否已收敛。)
对新点作不动点检验。
解答
梯度步给出 ,故 。因为 ,点 是极小点,也是不动点:。方法一步即已收敛。
快速检查
(某问题 ,以 从满足 的点出发运行。给出 的保证上界。)
代入速率定理。
解答 · 答案
由速率定理,取 ,差距至多为 。
快速检查
(证明当 为零函数时,速率定理化为梯度下降的界 ,并写出此时的 。)
对 极小化 。
解答
若 ,则 在 处最小,故 为恒等映射,迭代为 。此时 ,速率定理正是所述的梯度下降界。
快速检查
(对 与 ,求所有使迭代从任意初始点收敛到 的步长 。)
把迭代写成乘以一个常数。
解答
此时迭代为 ,故 。它对每个 都趋向 当且仅当 ,即 。由于 ,这包含定理所保证的整个范围 ,并说明该充分条件相当保守。