論文の概要: 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)。
累積ステップサイズでは)モデルパラメータの関数として明示的なレートを提供する。
我々の議論は、低温におけるギブス測度の機能的不等式(アイリング・クラマーズの法則)の最近の発展に適用している。
離散的な設定では、収束を保証するためにステップサイズに関する条件を得る。
関連論文リスト
- A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳(メタデータ) (2023-09-25T17:54:19Z) - Revisiting Subgradient Method: Complexity and Convergence Beyond
Lipschitz Continuity [29.56022052936922]
次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。
本研究ではまず, 次進法における典型的な複雑性を, 対物関数の凸度と弱凸度に拡張する。
ステップサイズの適切な減少規則を用いて,非Lipschitz凸および弱凸目的関数に対する収束結果を提供する。
論文 参考訳(メタデータ) (2023-05-23T15:26:36Z) - 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) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳(メタデータ) (2023-01-01T18:51:29Z) - Statistical Inference of Constrained Stochastic Optimization via
Sketched Sequential Quadratic Programming [59.36379287247961]
この問題を解決するために,完全オンライン逐次2次プログラミング(StoSQP)手法を開発した。
最近の数値二階法の設計により、StoSQPは任意のランダムなステップサイズを適応的に選択できる。
また,2次法の計算コストを大幅に削減するため,StoSQPはランダム化反復解法を用いて2次プログラムを不正確に解けるようにした。
論文 参考訳(メタデータ) (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) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳(メタデータ) (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。