机器学习优化公式学习笔记

主题：Lipschitz 连续性、Lipschitz smoothness、quadratic upper bound（descent lemma）、strong convexity、PL inequality，以及梯度下降的一步下降、contraction、linear/geometric convergence 和 condition number。

记号约定：目标函数为 F: R^d -> R，梯度为 ∇F(x)，最优点为 x*，步长为 η > 0。这里统一用 L 表示 smoothness 常数，用 c 表示强凸或 PL 常数。

0. 总体逻辑

这些公式连接成一条证明链：

1. Lipschitz 连续梯度给出曲率上界 L。
2. 曲率上界推出 quadratic upper bound / descent lemma。
3. 梯度下降更新代入这个上界，得到每一步的函数下降量。
4. PL inequality把梯度大小和当前 optimality gap 联系起来。
5. 因此 optimality gap 每一步都按固定比例缩小，得到 contraction 和 linear/geometric convergence。
6. 比例中的 L/c 形成 condition number，它衡量问题的病态程度和收敛速度。

需要区分：smoothness 控制“梯度变化不能太快”，strong convexity 控制“函数不能太平”，而 PL inequality 直接控制“梯度是否足够大”。

---

1. Lipschitz continuity

定义

函数 F 是 Lipschitz continuous（Lipschitz 连续）的，如果存在常数 G ≥ 0，使得对任意 x,y：

|F(x) - F(y)| ≤ G ||x-y||。

如果讨论的是梯度，则常见形式是：

||∇F(x) - ∇F(y)|| ≤ L ||x-y||。

后一个性质通常称为 Lipschitz continuous gradient，也叫 L-smoothness。严格说，“函数 Lipschitz 连续”和“梯度 Lipschitz 连续”不是同一件事。

推导和思考

函数 Lipschitz 连续意味着函数值变化至多与距离成正比；梯度 Lipschitz 连续意味着局部斜率变化至多与距离成正比。

在一维情况下，如果 F' 是 L-Lipschitz：

|F'(x) - F'(y)| ≤ L |x-y|，

那么从 y 移动到 x 时，斜率的变化受到 L 的控制。这正是后面二次项 (L/2)||x-y||² 出现的原因。

直觉

• 函数 Lipschitz：图像整体不能突然竖直上升或下降。
• 梯度 Lipschitz：图像的斜率不能突然改变，曲率被 L 限制。

可以把 L 理解成“最坏情况下的弯曲程度”。

假设

• 定义域通常取凸集，方便讨论线段 y+t(x-y)。
• 若要使用梯度形式，需要 F 可微。
• Lipschitz 常数不一定是最小值；只要取一个有效上界即可。

常见易错点

1. 把 |F(x)-F(y)| ≤ G||x-y|| 和 ||∇F(x)-∇F(y)|| ≤ L||x-y|| 当成同一个条件。
2. 认为 L 越小函数值一定越小。L 描述的是曲率上界，不是函数的绝对大小。
3. 忘记范数必须前后一致；欧氏范数对应后续最常见的梯度下降推导。

例子：线性函数

令 F(x)=aᵀx+b。则 ∇F(x)=a，所以 ||∇F(x)-∇F(y)||=0，其梯度 Lipschitz 常数可以取 L=0。函数本身在欧氏范数下满足 |F(x)-F(y)|≤||a|| ||x-y||。

---

2. Lipschitz smoothness

定义

可微函数 F 是 L-smooth 的，如果：

||∇F(x)-∇F(y)|| ≤ L||x-y||

对任意 x,y 成立。

若 F 二阶可微，一个常用的充分条件是 ||∇²F(x)||op ≤ L。对凸函数，常写成 0 ⪯ ∇²F(x) ⪯ LI。

推导和思考

沿着线段定义 φ(t)=F(y+t(x-y))。则 φ'(t)=∇F(y+t(x-y))ᵀ(x-y)，并且

F(x)-F(y)=∫₀¹ ∇F(y+t(x-y))ᵀ(x-y) dt。

加上并减去 ∇F(y)，使用 Cauchy–Schwarz 和 smoothness：

F(x)-F(y) ≤ ∇F(y)ᵀ(x-y) + ∫₀¹ Lt ||x-y||² dt

= ∇F(y)ᵀ(x-y) + (L/2)||x-y||²。

这就得到下一节的 quadratic upper bound。

直觉

smoothness 不表示函数一定凸。它只说明从 y 走到 x 时，真实函数值不会超过“切平面 + 一个二次曲率缓冲项”。

假设

• F 可微；
• 梯度在所考虑的区域上是 L-Lipschitz；
• 线段上的点仍处于定义域内。

常见易错点

• smoothness 与 convexity 是不同性质：一个函数可以 smooth 但非凸。
• 二阶可微时，不能只看某一个 Hessian 元素；要控制整体算子范数。
• L 是上界，实际局部曲率可能远小于 L。

例子：二次函数

令 F(x)=1/2 xᵀAx+bᵀx+d，其中 A 对称。则 ∇F(x)=Ax+b，所以 L=||A||op 是一个有效 smoothness 常数。若 A ⪰ 0，函数还是凸的；若 A ≻ 0，它还会强凸。

---

3. Quadratic upper bound / Descent lemma

定理

若 F 是 L-smooth，则对任意 x,y：

F(x) ≤ F(y) + ∇F(y)ᵀ(x-y) + (L/2)||x-y||²。

这称为 quadratic upper bound，也常称为 descent lemma。

推导

沿线积分并拆出 ∇F(y)：

F(x)-F(y)=∫₀¹∇F(y+t(x-y))ᵀ(x-y)dt

≤ ∇F(y)ᵀ(x-y)+∫₀¹ Lt||x-y||²dt

= ∇F(y)ᵀ(x-y)+(L/2)||x-y||²。

直觉

右侧由三部分组成：当前函数值、切平面的线性预测、曲率造成的最坏情况二次修正。因此它是一个“不会低估真实函数值”的二次上界。

假设

核心假设是 L-smoothness（以及可微、线段在定义域内）。不需要 strong convexity，也不需要函数凸。

常见易错点

1. 不等号方向写反；这里是函数值小于等于二次上界。
2. 二次项系数漏掉 1/2，它来自 ∫₀¹ t dt=1/2。
3. 把 L 换成 strong convexity 常数 c；上界用 L，下界通常用 c。

例子：一维平方函数

令 F(x)=1/2 ax²，其中 a>0。此时 L=a，并且二次上界取等号，因为二次函数的曲率处处正好等于 a。

---

4. Strong convexity

定义

函数 F 是 c-strongly convex 的，如果对任意 x,y：

F(x) ≥ F(y)+∇F(y)ᵀ(x-y)+(c/2)||x-y||²，其中 c>0。

若 F 二阶可微，常用等价条件是 ∇²F(x) ⪰ cI。

从最优点得到的下界

设 x* 是全局最优点，且 ∇F(x*)=0。在定义中取 y=x*：

F(x)-F(x*) ≥ (c/2)||x-x*||²。

这说明函数值差距至少按距离的平方增长。

由强凸性推出 PL inequality

在 L-smooth、c-strongly convex 的标准设置下，可得到：

||∇F(x)||² ≥ 2c(F(x)-F(x*))。

这就是 PL inequality。对一般函数，PL 可以独立成立，并不一定要求函数本身 convex；但 strong convexity 通常能推出它。

直觉

强凸性表示函数像一个至少有固定碗底曲率的碗：不会出现无限长的平坦方向。因此最优点通常唯一，且离最优点越远，函数值差距不能太小。

假设

• c>0；
• 定义域通常为凸集；
• 若使用 Hessian 形式，需要二阶可微；
• 全局最优点 x* 存在。

常见易错点

• 凸函数只要求 c=0 的下界；强凸要求 c>0。
• c 不是函数值，也不是步长。
• 强凸性给出函数下界，不等于直接给出梯度下降更新式。
• 非凸函数也可能满足 PL，因此 PL 与 strong convexity 不能简单画等号。

例子：正定二次函数

令 F(x)=1/2 xᵀAx，其中 A ≻ 0。若 A 的最小和最大特征值分别为 λmin, λmax，则 c=λmin、L=λmax。最优点是 x*=0。

---

5. PL inequality

定义

若存在 c>0，使得对任意 x：

2c(F(x)-F(x*)) ≤ ||∇F(x)||²，

则称 F 满足 Polyak–Łojasiewicz（PL）不等式。

推导思路

PL 把两个量联系起来：左侧是当前 optimality gap，右侧是梯度平方。等价地：

F(x)-F(x*) ≤ (1/(2c))||∇F(x)||²。

所以只要函数值还离最优值很远，梯度就不能太小。梯度下降正是沿着梯度方向移动，因此这条关系可以把“梯度下降了多少”转成“函数差距下降了多少”。

直觉

PL 是梯度下降获得几何收敛所需的“梯度不会无故消失”条件。它不一定保证所有等高线都是标准凸碗，但保证了只要还没有达到最优值，梯度就保留足够大的信号。

假设

• F(x*) 是全局最优值；
• c>0；
• 若要与 descent lemma 连用，还需要 L-smoothness；
• 若从 strong convexity 推出 PL，则还需相应的强凸假设。

常见易错点

1. PL 不等于 F 本身强凸；PL 可以在某些非凸问题上成立。
2. 不要把 ||∇F(x)|| 和 ||∇F(x)||² 混用，系数 2c 会随之改变。
3. x* 表示最优点，不是当前迭代点 xt。
4. 代入负系数时要注意不等号方向。

例子：平方损失

令 F(x)=c/2 ||x||²，其最优点为 x*=0，梯度为 cx。于是 ||∇F(x)||²=c²||x||²=2cF(x)，PL 不等式在此处取等号。

---

6. 一步梯度下降的函数下降

更新规则

x_{t+1}=x_t-η∇F(x_t)，因此 x_{t+1}-x_t=-η∇F(x_t)。

从 descent lemma 开始

令 x=x_{t+1}、y=x_t：

F(x_{t+1})-F(x_t) ≤ ∇F(x_t)ᵀ(x_{t+1}-x_t) + (L/2)||x_{t+1}-x_t||²。

代入更新量：

F(x_{t+1})-F(x_t) ≤ -η||∇F(x_t)||² + (Lη²/2)||∇F(x_t)||²

= -η(1-Lη/2)||∇F(x_t)||²。

因此：

F(x_{t+1})-F(x_t) ≤ -η(1-Lη/2)||∇F(x_t)||²。

步长条件

当 0<η≤2/L 时，右侧非正，所以 F(x_{t+1})≤F(x_t)。若进一步取 0<η≤1/L，则 1-Lη/2≥1/2，结合 PL 得：

F(x_{t+1})-F(x_t) ≤ -ηc(F(x_t)-F(x*))。

注意：这里用到了负系数乘以下界时的不等号方向：

-η(1-Lη/2)||∇F(x_t)||² ≤ -η(1-Lη/2)·2c(F(x_t)-F(x*))。

直觉

梯度方向是局部下降最快的方向。第一项 -η||∇F||² 表示线性下降；第二项 +Lη²||∇F||²/2 是函数弯曲产生的代价。步长太大时，曲率代价会抵消甚至超过线性下降。

假设

• F 是 L-smooth；
• 使用 GD 更新；
• 若要得到 gap 形式，还需 PL inequality；
• 若要使用简洁的 -ηc 系数，通常取 η≤1/L。

常见易错点

• 只看到负的线性项，就断言任意步长都下降；二次项可能使结论失效。
• η≤2/L 常用于保证单步不增；η≤1/L 便于得到 contraction。
• “函数值不增加”不等于“已经收敛到最优”。

例子：一维平方函数

对 F(x)=1/2 ax²，有 L=c=a，更新为 x_{t+1}=(1-ηa)x_t。当 0<η<2/a 时函数值不增加；取 η=1/a 时一步到达 x*=0。

---

7. Contraction（收缩）

推导

在 0<η≤1/L 下，由上一节：

F(x_{t+1})-F(x_t) ≤ -ηc(F(x_t)-F(x*))。

令 Δt=F(x_t)-F(x*)。因为 F(x_{t+1})-F(x_t)=Δ_{t+1}-Δt，所以：

Δ_{t+1}-Δt ≤ -ηcΔt，

整理得到：

Δ_{t+1} ≤ (1-ηc)Δt。

这就是 contraction inequality。

直觉

每一步最多保留当前误差的 1-ηc 倍。若 0<ηc<1，这个因子位于 0 和 1 之间，误差会持续缩小。

例如 1-ηc=0.9，则每一步最多保留 90% 的当前 gap。

假设

• L-smooth；
• 满足 PL inequality（强凸函数是常见充分条件）；
• 0<η≤1/L；
• 0<ηc<1 时 contraction 因子为正且小于 1。

常见易错点

• contraction 作用在 Δt 或函数值误差上，不一定直接作用在参数距离 ||x_t-x*|| 上。
• 步长太大时，1-ηc 可能不在 (0,1) 内，不能直接套用“每次缩小固定比例”的直觉。
• Δt 通常要求 F(x*) 是全局最优值。

例子

若 Δ0=10、收缩因子为 0.8，则 Δ1≤8、Δ2≤6.4、Δ3≤5.12。

---

8. Linear / geometric convergence

迭代展开

由 Δ_{t+1}≤(1-ηc)Δt 反复应用可得：

Δt ≤ (1-ηc)^t Δ0。

即：

F(x_t)-F(x*) ≤ (1-ηc)^t [F(x_0)-F(x*)]。

这称为 linear convergence 或 geometric convergence。这里的“linear”指误差序列满足固定比例递推，不是指误差按 1/t 下降。

复杂度直觉

若希望 Δt≤εδ0，需要 (1-ηc)^t≤ε，因此：

t ≥ log(1/ε) / [-log(1-ηc)]。

当 ηc 较小时，-log(1-ηc)≈ηc，所以 t=O((1/(ηc)) log(1/ε))。取 η=1/L 时：

Δt≤(1-c/L)^tΔ0。

直觉

每一步都乘上同一个小于 1 的数，所以误差曲线呈指数衰减。相比 1/t 型的 sublinear convergence，达到高精度时 geometric convergence 通常更快。

常见易错点

• “linear convergence” 不代表图像是一条直线，也不代表 O(1/t)。
• 这是函数值 gap 的结论；若要推导参数距离，还需结合强凸性的上下界。
• 比例必须稳定小于 1；如果比例接近 1，理论上虽收敛，实际可能很慢。

例子

若 ρ=0.99，前期每步只减少约 1%；若 ρ=0.5，则每两步大约缩小到四分之一，明显更快。

---

9. Condition number

定义

在 L-smooth 且 c-strongly convex 的问题中，定义 condition number：

κ=L/c。

通常 L≥c>0，所以 κ≥1。

与收敛率的关系

取常用步长 η=1/L：

1-ηc=1-c/L=1-1/κ。

所以：

F(x_t)-F(x*) ≤ (1-1/κ)^t [F(x_0)-F(x*)]。

• κ 小：c 与 L 接近，收缩因子较小，收敛快；
• κ 大：存在很平的方向和很陡的方向，收缩因子接近 1，收敛慢。

几何直觉

对二次函数 F(x)=1/2 xᵀAx，κ=λmax(A)/λmin(A)。等高线像椭圆：κ≈1 时接近圆形；κ≫1 时是细长椭圆，梯度下降容易在狭长谷底中来回摆动。

常见易错点

• condition number 不是单纯的数据维度，也不是参数个数。
• κ 大不一定表示算法完全不能用，而是说明基础 GD 可能需要很多迭代。
• 预条件化、特征缩放、加速方法的目标之一，就是改善有效的 condition number 或减少它对迭代次数的影响。

例子

令 A=diag(1,100)。则 c=1,L=100,κ=100。使用 η=1/L=0.01 时，理论收缩因子为 1-1/κ=0.99，说明最坏方向上的理论收敛会比较慢。

---

10. 一页式公式总结

关键定义

||∇F(x)-∇F(y)||≤L||x-y||（L-smoothness）

F(x)≥F(y)+∇F(y)ᵀ(x-y)+(c/2)||x-y||²（c-strong convexity）

2c(F(x)-F(x*))≤||∇F(x)||²（PL inequality）

关键上界和递推

F(x)≤F(y)+∇F(y)ᵀ(x-y)+(L/2)||x-y||²

x_{t+1}=x_t-η∇F(x_t)

F(x_{t+1})-F(x_t)≤-η(1-Lη/2)||∇F(x_t)||²

当 0<η≤1/L 且满足 PL 时：

Δ_{t+1}≤(1-ηc)Δt

Δt≤(1-ηc)^tΔ0

当 η=1/L 时：

Δt≤(1-1/κ)^tΔ0，其中 κ=L/c。

最值得记住的推理

smoothness 给出二次上界；梯度下降代入后得到一步下降；PL 把梯度平方换成 optimality gap；于是 gap 按固定比例收缩，最终得到 geometric convergence。L/c 决定这个比例离 1 有多近。