知识卡片
精度减半需要四倍迭代
由凸优化误差界ε=RL/√T反解,达到目标误差ε需T=R²L²/ε²轮。
R、L固定时,目标误差减半意味着迭代轮数增至四倍;梯度计算成本还需另计。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第33章 机器学习算法 · 查看原书依据
T = R2L2/ϵ2. The number of iterations thus depends on the square of R and L and, most importantly, on 1/ϵ2. (The definition of L from inequality (33.21) depends on T, but we may know an upper bound on L that doesn’t depend on the particular value of T.) Thus, if you want to halve your error bound, you need to run four times as many iterations. It is quite possible that we don’t really know R and L, since you’d need to know x* in order to know R (since R = ∥x(0) – x*∥), and you might not have an explicit upper bound on the gradient, which would provide L. You can, however, interpret
参考来源
- 位置:《算法导论(第4版)》第33章《机器学习算法》(OEBPS/chapter033.xhtml,文本字符[55000,60000))。
- 结论依据:原文第33.3节梯度下降、凸性、误差界或约束投影;相关公式图已核对。
- 原始内容:T = R 2 L 2 / ϵ 2 . The number of iterations thus depends on the square of R and L and, most importantly, on 1/ ϵ 2 . (The definition of L from inequality (33.21) depends on T , but we may know an upper bound on L that doesn’t depend on the particular value of T .) Thus, if you want to halve your error bound, you need to run four times as many iterations. It is quite possible that we don’t really know R and L , since you’d need to know x * in order to know R (since R = ∥ x (0) – x * ∥ ), and you might not have an explicit upper bound on the gradient, which would provide L . You can, however, interpret