Simulated annealing from continuum to discretization: a convergence analysis via the Eyring--Kramers law
Simulated annealing from continuum to discretization: a convergence analysis via the Eyring--Kramers law
复制标题
从连续到离散的模拟退火：通过 Eyring-Kramers 定律进行收敛分析
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
X. Zhou
中科院分区：
文献类型：
--
作者：
Wenpin Tang;X. Zhou
我们研究了连续时间模拟退火（Xt; t≥0）的收敛速度及其离散化（xk; k = 0,1，…），以逼近给定函数f的全局最优。我们证明了尾部概率P(f(Xt) > min f + δ) (resp。P(f(xk) > min f+δ))随时间衰减多项式(resp。在累积步长中)，并提供一个明确的速率作为模型参数的函数。我们的论证应用了最近关于低温下吉布斯测度的函数不等式的发展——艾灵-克莱默斯定律。在离散情况下，得到了保证收敛的步长条件。
We study the convergence rate of continuous-time simulated annealing (Xt; t ≥ 0) and its discretization (xk; k = 0, 1, . . .) for approximating the global optimum of a given function f . We prove that the tail probability P(f(Xt) > min f + δ) (resp. P(f(xk) > min f+δ)) decays polynomial in time (resp. in cumulative step size), and provide an explicit rate as a function of the model parameters. Our argument applies the recent development on functional inequalities for the Gibbs measure at low temperatures – the Eyring-Kramers law. In the discrete setting, we obtain a condition on the step size to ensure the convergence.
DOI：
--
发表时间：
2019-04
期刊：
J. Mach. Learn. Res.
影响因子：
--
作者：
Xi Chen;S. Du;Xin T. Tong
通讯作者：
Xi Chen;S. Du;Xin T. Tong
影响因子：
1.4
作者：
Menz, Georg;Schlichting, André;Tang, Wenpin;Wu, Tianqi
通讯作者：
Wu, Tianqi