論文の概要: Improved Bound for Mixing Time of Parallel Tempering
- arxiv url: http://arxiv.org/abs/2304.01303v1
- Date: Mon, 3 Apr 2023 19:03:22 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-05 16:35:26.406431
- Title: Improved Bound for Mixing Time of Parallel Tempering
- Title（参考訳）: 並列テンパリングにおける混合時間境界の改善
- Authors: Holden Lee, Zeyu Shen
- Abstract要約: パラレルテンパリングのための新しい下限を、$log L$を除く全てのパラメータにマルチモーダル依存を持つスペクトルギャップ上で提示する。
これにより、モードの数に指数関数的に依存する最良の既存の境界が改善される。
スペクトルギャップ上の仮定上界は$log L$に指数関数依存しており、ある意味では我々の境界は密であることを示す。
- 参考スコア（独自算出の注目度）: 4.68299658663016
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In the field of sampling algorithms, MCMC (Markov Chain Monte Carlo) methods
are widely used when direct sampling is not possible. However, multimodality of
target distributions often leads to slow convergence and mixing. One common
solution is parallel tempering. Though highly effective in practice,
theoretical guarantees on its performance are limited. In this paper, we
present a new lower bound for parallel tempering on the spectral gap that has a
polynomial dependence on all parameters except $\log L$, where $(L + 1)$ is the
number of levels. This improves the best existing bound which depends
exponentially on the number of modes. Moreover, we complement our result with a
hypothetical upper bound on spectral gap that has an exponential dependence on
$\log L$, which shows that, in some sense, our bound is tight.
- Abstract（参考訳）: サンプリングアルゴリズムの分野では、直接サンプリングが不可能な場合にはMCMC(Markov Chain Monte Carlo)法が広く用いられている。
しかし、ターゲット分布の多様性はしばしば収束と混合を遅くする。
一般的な解決策は並列テンパリングである。
実際には極めて効果的であるが、その性能に関する理論的保証は限られている。
本稿では,各パラメータに多項式依存を持つスペクトルギャップ上での並列テンパリングのための新しい下限を,$(L + 1)$がレベル数であるような$\log L$を除いて提示する。
これにより、モード数に指数関数的に依存する最善のバウンダリが改善される。
さらに、スペクトルギャップ上の仮定上界は$\log L$に指数関数依存しており、ある意味では我々の境界は密であることを示す。
関連論文リスト
- A Fast, Robust Elliptical Slice Sampling Implementation for Linearly Truncated Multivariate Normal Distributions [12.800664845601197]
スライススサンプリング(スライスススライスススライスススライスススライスス)は、マルコフ連鎖モンテカルロ法である。
本論文の主な新規性は,$mathcalO(m log m)$時間で交点を計算するアルゴリズムである。
このアルゴリズムに基づく実装により、数値安定性が向上し、実行時間を短縮し、複数のマルコフ連鎖を起動するために並列化が容易であることを示す。
論文 参考訳（メタデータ） (2024-07-15T05:40:11Z) - Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel [10.840582511203024]
我々のアルゴリズムは、$widetilde O(log2 d)$ parallel roundsでのみ実行できるように並列化可能であることを示す。
また、我々のアルゴリズムは、$widetilde O(log2 d)$ parallel roundsでしか実行できないことを示す。
論文 参考訳（メタデータ） (2024-06-03T01:34:34Z) - A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization [6.314057999212246]
ランダムリシャッフル技術は、ニューラルネットワークのような大規模アプリケーションで使用される。
本稿では,ノルムPRRが生成するランダムリシャッフル型反復が線形設定に収束することを示す。
最後に,提案手法に適用可能な最終収束率を導出する。
論文 参考訳（メタデータ） (2023-12-02T07:12:00Z) - Distributed Extra-gradient with Optimal Complexity and Communication
Guarantees [60.571030754252824]
複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。
モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。
そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
論文 参考訳（メタデータ） (2023-08-17T21:15:04Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning [3.655021726150368]
マルチエージェント強化学習(MARL: Multi-Agent Reinforcement Learning)では、複数のエージェントが共通の環境と相互作用し、シーケンシャルな意思決定において共有問題を解く。
我々は、MARLで有用な分散非線形近似スキームの族を反復する新しい法則を導出する。
論文 参考訳（メタデータ） (2021-10-27T08:01:17Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳（メタデータ） (2021-10-20T02:25:25Z) - Lower Bounds on Metropolized Sampling Methods for Well-Conditioned
Distributions [29.314919044203926]
我々は、実際に最もポピュラーなサンプリング手法であるランゲヴィンアルゴリズム(MALA)とマルチステップのハミルトンモンテカルロ(HMC)の2つの性能に低い限界を与える。
我々の主な結果は、指数的に暖かい開始からMALAの混合時間における$widetildeOmega(kappa d)$のほぼ28の低い境界である。
論文 参考訳（メタデータ） (2021-06-10T03:47:39Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-30T19:10:32Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z) - SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。
実験では最先端のアルゴリズムよりも優れています。
論文 参考訳（メタデータ） (2020-02-22T01:03:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。