論文の概要: Simulated annealing from continuum to discretization: a convergence
analysis via the Eyring--Kramers law
- arxiv url: http://arxiv.org/abs/2102.02339v1
- Date: Wed, 3 Feb 2021 23:45:39 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-05 18:22:58.935188
- Title: Simulated annealing from continuum to discretization: a convergence
analysis via the Eyring--Kramers law
- Title(参考訳): 連続性から離散性への模擬アニール:アイリング・クラマース法による収束解析
- Authors: Wenpin Tang and Xun Yu Zhou
- Abstract要約: 連続時間アニーリング$(X_t;, t ge 0)$とその離散化$(x_k;, k =0,1, ldots)$の収束率について検討する。
我々は、テール確率 $mathbbP(f(X_t) > min f +delta)$ (resp. $mathP(f(x_k) > min f +delta)$) が時間内に崩壊することを証明する(累積ステップサイズでは、resp. $mathP(f(x_k) > min f +delta)$)。
- 参考スコア(独自算出の注目度): 10.406659081400354
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the convergence rate of continuous-time simulated annealing $(X_t;
\, t \ge 0)$ and its discretization $(x_k; \, k =0,1, \ldots)$ for
approximating the global optimum of a given function $f$. We prove that the
tail probability $\mathbb{P}(f(X_t) > \min f +\delta)$ (resp.
$\mathbb{P}(f(x_k) > \min f +\delta)$) 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.
- Abstract(参考訳): 与えられた関数 $f$ のグローバル最適を近似するための連続時間シミュレートアニール $(X_t; \, t \ge 0)$ とその離散 $(x_k; \, k =0,1, \ldots)$ の収束速度を研究する。
テール確率 $\mathbb{P}(f(X_t) > \min f +\delta)$ (resp) が証明される。
$\mathbb{P}(f(x_k) > \min f +\delta)$) 時間の多項式を減衰させる(resp)。
累積ステップサイズでは)モデルパラメータの関数として明示的なレートを提供する。
我々の議論は、低温におけるギブス測度の機能的不等式(アイリング・クラマーズの法則)の最近の発展に適用している。
離散的な設定では、収束を保証するためにステップサイズに関する条件を得る。
関連論文リスト
- An Explicit Expansion of the Kullback-Leibler Divergence along its
Fisher-Rao Gradient Flow [8.052709336750823]
$pirhollback$が複数のモードを示すとき、$pirhollback$は、潜在的な関数とは無関係であることを示す。
私たちは$textKLの明示的な拡張を提供します。
KL。
KL。
KL。
KL。
KL。
KL。
KL。
KL。
KL。
KL。
KL。
KL。
論文 参考訳(メタデータ) (2023-02-23T18:47:54Z) - Randomized Coordinate Subgradient Method for Nonsmooth Optimization [10.366968510541952]
非平滑凸および非平滑非(非平滑弱凸)問題に対するRandomized Coordinate Subgradient Method (RCS)を提案する。
RCSは、1つのブロック座標をランダムに選択し、繰り返しごとに更新する。
本研究では, 過渡法よりもRCSの方が優れていることを示すために, いくつかの実験を行った。
論文 参考訳(メタデータ) (2022-06-30T02:17:11Z) - Asymptotic Convergence Rate and Statistical Inference for Stochastic
Sequential Quadratic Programming [59.36379287247961]
制約付き非線形最適化問題を解くために、逐次2次アルゴリズム(StoSQP)を適用する。
分布関数の収束度を定量的に測定するために、$(x_t, lambda_t)$に対してベリー・エスキーを確立する。
論文 参考訳(メタデータ) (2022-05-27T00:34:03Z) - Optimal and instance-dependent guarantees for Markovian linear
stochastic approximation [77.84027086542827]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳(メタデータ) (2021-12-23T18:47:50Z) - On quantitative Laplace-type convergence results for some exponential
probability measures, with two applications [2.9189409618561966]
密度 w.r.t ルベーグ測度 $(mathrmd pi_varepsilon)_varepsilon >0$ ルベーグ測度 $(mathrmd pi_varepsilon)_varepsilon >0$ ルベーグ測度 $(mathrmd pi_varepsilon)_varepsilon >0$ ルベーグ測度 $(mathrmd pi_varepsilon)_varepsilon >0$ ルベーグ測度 $(mathrmd)
論文 参考訳(メタデータ) (2021-10-25T13:00:25Z) - Parameter-free Statistically Consistent Interpolation:
Dimension-independent Convergence Rates for Hilbert kernel regression [0.0]
最近提案された重み付き補間近接補間法 (wiNN) はこのクラスに属する。
プラグインの余剰リスクは 2|f(x)-1/2|1-1-varepsilon) sigma(x)((n))-frac2$ 以下の任意の$に対して、$f$ は回帰関数 $xmapstomathbbE[yx]$ であることを示す。
論文 参考訳(メタデータ) (2021-06-07T05:50:02Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳(メタデータ) (2020-12-22T12:59:30Z) - On Convergence of Gradient Expected Sarsa($\lambda$) [25.983112169543375]
オフライン推定(マルチステップブートストラップ)を$mathttexpectedsarsa(lambda)$に適用することはオフポリシ学習において不安定であることを示す。
収束する$mathttgradientexpectedsarsa(lambda)$ ($mathttges(lambda)$)アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-12-14T01:27:24Z) - The Convergence Indicator: Improved and completely characterized
parameter bounds for actual convergence of Particle Swarm Optimization [68.8204255655161]
我々は、粒子が最終的に単一点に収束するか、分岐するかを計算するのに使用できる新しい収束指標を導入する。
この収束指標を用いて、収束群につながるパラメータ領域を完全に特徴づける実際の境界を提供する。
論文 参考訳(メタデータ) (2020-06-06T19:08:05Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳(メタデータ) (2020-06-04T17:51:00Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳(メタデータ) (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。