論文の概要: On the Theoretical Properties of the Exchange Algorithm
- arxiv url: http://arxiv.org/abs/2005.09235v4
- Date: Thu, 19 Aug 2021 04:28:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-01 13:58:36.509009
- Title: On the Theoretical Properties of the Exchange Algorithm
- Title（参考訳）: 交換アルゴリズムの理論的性質について
- Authors: Guanyang Wang
- Abstract要約: この交換は、2重に抽出可能な分布からサンプリングするメトロポリス・ハスティングスアルゴリズムの最も一般的な拡張の1つである。
本稿では,交換アルゴリズムの理論的性質について,分散と収束速度の観点から検討する。
本結果は,交換アルゴリズムの理論的有用性を正当化するものである。
- 参考スコア（独自算出の注目度）: 0.76146285961466
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The exchange algorithm is one of the most popular extensions of the
Metropolis--Hastings algorithm to sample from doubly-intractable distributions.
However, the theoretical exploration of the exchange algorithm is very limited.
For example, natural questions like `Does exchange algorithm converge at a
geometric rate?' or `Does the exchange algorithm admit a Central Limit
Theorem?' have not been answered yet. In this paper, we study the theoretical
properties of the exchange algorithm, in terms of asymptotic variance and
convergence speed. We compare the exchange algorithm with the original
Metropolis--Hastings algorithm and provide both necessary and sufficient
conditions for the geometric ergodicity of the exchange algorithm. Moreover, we
prove that our results can be applied to various practical applications such as
location models, Gaussian models, Poisson models, and a large class of
exponential families, which includes most of the practical applications of the
exchange algorithm. A central limit theorem for the exchange algorithm is also
established. Our results justify the theoretical usefulness of the exchange
algorithm.
- Abstract（参考訳）: 交換アルゴリズムは、二重抽出可能な分布からサンプリングするメトロポリス・ハスティングスアルゴリズムの最も一般的な拡張の一つである。
しかし、交換アルゴリズムの理論的な探索は非常に限られている。
例えば、'Does exchange algorithm converge at a geometry rate?'や'Does the exchange algorithm admit a Central Limit Theorem?'といった自然問題はまだ答えられていない。
本稿では,漸近的分散と収束速度の観点から,交換アルゴリズムの理論的性質について検討する。
交換アルゴリズムをオリジナルのメトロポリス・ヘイスティングスアルゴリズムと比較し,交換アルゴリズムの幾何学的エルゴード性に対する必要条件と十分条件の両方を提供する。
さらに, 位置モデル, ガウスモデル, ポアソンモデル, および交換アルゴリズムの実用的応用のほとんどを含む指数関数群など, 様々な実用的応用に適用可能であることを証明した。
交換アルゴリズムの中央極限定理も確立されている。
この結果は交換アルゴリズムの理論的有用性を正当化する。
関連論文リスト
- A quantum algorithm for advection-diffusion equation by a probabilistic imaginary-time evolution operator [0.0]
本稿では, 線形対流拡散方程式を, 新しい近似確率的想像時間進化(PITE)演算子を用いて解く量子アルゴリズムを提案する。
我々は, 対流拡散方程式から得られるハミルトニアンの想像時間進化を実現するために, 明示的な量子回路を構築した。
我々のアルゴリズムは、Harrow-Hassidim-Lloyd (HHL)アルゴリズムに匹敵する結果を与える。
論文 参考訳（メタデータ） (2024-09-27T08:56:21Z) - Bregman-divergence-based Arimoto-Blahut algorithm [53.64687146666141]
本稿では,Arimoto-BlahutアルゴリズムをBregman-Diversergenceシステム上で定義された一般関数に一般化する。
本稿では,古典的および量子速度歪み理論に適用可能な凸最適化自由アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-08-10T06:16:24Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Improved resource-tunable near-term quantum algorithms for transition
probabilities, with applications in physics and variational quantum linear
algebra [1.7404865362620803]
遷移確率を計算するための3つの関連アルゴリズムを提案する。
まず,2つの入力状態が非直交状態となるように,前述した半深度アルゴリズムを拡張した。
第二に、回路評価の少ないトロタライゼーションとリチャードソン外挿に基づくより深いアルゴリズムを導出する。
第三に、回路深度と測定の複雑さのトレードオフを可能にするチューナブルアルゴリズムを導入する。
論文 参考訳（メタデータ） (2022-06-28T18:00:05Z) - Bregman divergence based em algorithm and its application to classical
and quantum rate distortion theory [61.12008553173672]
本稿では,Bregman分散系における指数サブファミリーと混合サブファミリー間のBregman分散の最小化問題に対処する。
このアルゴリズムを量子設定を含む歪みとその変種の評価に適用する。
論文 参考訳（メタデータ） (2022-01-07T13:33:28Z) - Quantum algorithms for group convolution, cross-correlation, and
equivariant transformations [9.134244356393665]
群畳み込みと相互相関は、与えられた問題設定に固有の対称性を解析または活用するために一般的に数学で使用される。
ここでは,量子状態として格納されたデータの線形群畳み込みと相互相関を行うための効率的な量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-23T12:21:31Z) - Fractal Structure and Generalization Properties of Stochastic
Optimization Algorithms [71.62575565990502]
最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。
さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
論文 参考訳（メタデータ） (2021-06-09T08:05:36Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
適応性は現代最適化理論において重要であるが、研究されていない性質である。
提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
論文 参考訳（メタデータ） (2020-02-13T05:42:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。