知识卡片
凸约束下仍保留梯度误差界
设要在凸可行域S内最小化凸函数f,x*是S内最优点;初始点到x*的距离至多R,并假设各次梯度范数至多L。每轮先做普通梯度步x′(t+1)=x(t)−γ∇f(x(t)),再把x′(t+1)投影到S得到x(t+1)。
欧氏投影到凸集不会增大它到任一可行点的距离,所以
‖x(t+1)−x*‖ ≤ ‖x′(t+1)−x*‖。
无约束分析中的距离势能上界因而仍成立。取γ=R/(L√T),并返回T个迭代点的平均值;凸性保证平均值仍在S内,且其目标差至多RL/√T。这个迭代次数界还没有计入每轮求投影的计算成本。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第33章 机器学习算法 · 查看原书依据
We can now repeat the entire proof for the unconstrained case and obtain the same bounds. Lemma 33.10 with a = x*, b = x(t+1), and b′ = x′(t+1) tells us that ∥x(t+1)–x*∥2 ≤ ∥x′(t+1)–x*∥2. We can therefore derive an upper bound that matches inequality (33.31).
参考来源
- 位置:《算法导论(第4版)》第33章《机器学习算法》(OEBPS/chapter033.xhtml,文本字符[60000,65000))。
- 结论依据:原文第33.3节或章末题目、注记;相关公式图已核对,未解答书中练习。
- 原始内容:We can now repeat the entire proof for the unconstrained case and obtain the same bounds. Lemma 33.10 with a = x *, b = x ( t +1) , and b ′ = x′ ( t +1) tells us that ∥ x ( t +1) – x * ∥ 2 ≤ ∥ x′ ( t +1) – x * ∥ 2 . We can therefore derive an upper bound that matches inequality (33.31).