知识卡片

普通读书笔记卡 · 3710.f.2.d.2

凸约束下仍保留梯度误差界

理解等级:高级

设要在凸可行域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。这个迭代次数界还没有计入每轮求投影的计算成本。

这张卡片看不懂?

已有反馈 · 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).