优化算法的收敛速度是怎么定义的？_欧陆娱乐-欧陆注册登录中心

您好，欢迎访问这里是您的网站名称官网！

欧陆娱乐-欧陆注册登录中心

欧陆新闻

NEWS CENTER

产品中心标题六

产品中心标题六

产品中心标题五

产品中心标题五

产品中心标题四

产品中心标题四

产品中心标题三

产品中心标题三

主页 > 欧陆新闻

优化算法的收敛速度是怎么定义的？

发布时间：2024-05-20 19:05浏览次数：

假设 $\\{x^{(k)}\\}\\in R^n$ 是一个收敛到 $x^* \\in R^n$ 的序列，即 $\\lim_{k \\rightarrow \\infty}{x^k=x^*}$ ，那么我们一般这样定义收敛速度：

$\\lim_{k \\rightarrow \\infty}{\\frac{\\epsilon_{k+1}}{\\epsilon_{k}}}=\\lim_{k \\rightarrow \\infty}{\\frac{||x^{(k+1)}-x^*||}{||x^{(k)}-x^*||}}=C$

$C=0$ ，我们说 $\\{x^{(k)}\\}\\rightarrow x^*$ 是超线性收敛；
$C \\in (0, 1)$ ，我们说 $\\{x^{(k)}\\}\\rightarrow x^*$ 是线性收敛；
$C=1$ ，我们说 $\\{x^{(k)}\\}\\rightarrow x^*$ 是次线性收敛；

通常我们用两种方式量化收敛速度：

Fix step index k, upper bound $\\min_{1 \\leq t \\leq k}\\epsilon_t$

超线性收敛： $\\epsilon_k=e^{-e^{k}}$
线性收敛： $\\epsilon_k=e^{-k}$
次线性收敛： $\\epsilon_k=\\frac{1}{k}$

Fix epsilon $\\epsilon$ , how many steps needed for $\\min_{1 \\leq t \\leq k}\\epsilon_t < \\epsilon$

超线性收敛： $O(log(log(\\frac{1}{\\epsilon})))$
线性收敛： $O(log\\frac{1}{\\epsilon})$
次线性收敛： $O(\\frac{1}{\\epsilon})$ , $O(\\frac{1}{\\epsilon^2})$ , $O(\\frac{1}{\\sqrt{\\epsilon}})$ 等

当我们看论文是，作者除了说他们的算法是次线性收敛或者线性收敛，通常还会用 $O(\\frac{1}{\\epsilon})$ 或者 $O(log \\frac{1}{\\epsilon})$ 等量化收敛速度，这用的是第二种方式。

可以参考我写的一篇文章：

落落大方的发卡：收敛速度的三种形式

上一篇：协同优化算法_1

下一篇：神经网络优化器对比

Copyright © 2002-2022 欧陆娱乐-欧陆注册登录中心版权所有　备案号：ICP备********号

平台注册入口