論文の概要: Fast convergence of the Expectation Maximization algorithm under a logarithmic Sobolev inequality
- arxiv url: http://arxiv.org/abs/2407.17949v1
- Date: Thu, 25 Jul 2024 11:08:53 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-26 14:18:40.993920
- Title: Fast convergence of the Expectation Maximization algorithm under a logarithmic Sobolev inequality
- Title(参考訳): 対数的ソボレフ不等式下での期待最大化アルゴリズムの高速収束
- Authors: Rocco Caprio, Adam M Johansen,
- Abstract要約: 我々は、ユークリッド空間上の交互最小化アルゴリズムを理解するためによく用いられる分析手法を、期待最大化(EM)アルゴリズムに拡張する。
対数ソボレフ不等式の自然な一般化の下で有限サンプル誤差境界とEMアルゴリズムの指数収束を求める。
- 参考スコア(独自算出の注目度): 1.1510009152620668
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: By utilizing recently developed tools for constructing gradient flows on Wasserstein spaces, we extend an analysis technique commonly employed to understand alternating minimization algorithms on Euclidean space to the Expectation Maximization (EM) algorithm via its representation as coordinate-wise minimization on the product of a Euclidean space and a space of probability distributions due to Neal and Hinton (1998). In so doing we obtain finite sample error bounds and exponential convergence of the EM algorithm under a natural generalisation of a log-Sobolev inequality. We further demonstrate that the analysis technique is sufficiently flexible to allow also the analysis of several variants of the EM algorithm.
- Abstract(参考訳): 近年開発されたワッサーシュタイン空間上の勾配流構築ツールを利用することで、ユークリッド空間上の交互最小化アルゴリズムを、そのユークリッド空間の積とNeal and Hinton (1998)による確率分布の空間の座標ワイド最小化として表現することで、期待最大化(EM)アルゴリズムへと拡張する。
このようにして、対数ソボレフ不等式の自然な一般化の下で、有限サンプル誤差境界とEMアルゴリズムの指数収束を得る。
さらに,解析手法が十分に柔軟であることから,EMアルゴリズムのいくつかの変種も解析可能であることを実証した。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳(メタデータ) (2024-09-07T06:37:23Z) - Taming the Interacting Particle Langevin Algorithm -- the superlinear case [0.0]
我々は、この非線型性の下で、タグ付き相互作用粒子ランゲヴィンアルゴリズム(tIPLA)と呼ばれる新しい安定なクラスを開発する。
We obtain non-asymptotic convergence error estimates in Wasserstein-2 distance for the new class under an optimal rate。
論文 参考訳(メタデータ) (2024-03-28T17:11:25Z) - A Note on High-Probability Analysis of Algorithms with Exponential,
Sub-Gaussian, and General Light Tails [34.465259431606405]
このようなアルゴリズムの解析はブラックボックス方式で削減でき、対数係数の損失はわずかである。
このアプローチは指数関数、準ガウス分布、より一般的な高速分解分布を含む任意の光尾ランダム化にも同時に適用される。
論文 参考訳(メタデータ) (2024-03-05T11:38:20Z) - Convergence of Expectation-Maximization Algorithm with Mixed-Integer Optimization [5.319361976450982]
本稿では,特定の種類のEMアルゴリズムの収束を保証する一連の条件を紹介する。
本研究では,混合整数非線形最適化問題の解法として,反復アルゴリズムの新しい解析手法を提案する。
論文 参考訳(メタデータ) (2024-01-31T11:42:46Z) - Distributed Markov Chain Monte Carlo Sampling based on the Alternating
Direction Method of Multipliers [143.6249073384419]
本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。
我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。
シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
論文 参考訳(メタデータ) (2024-01-29T02:08:40Z) - Robust empirical risk minimization via Newton's method [9.797319790710711]
実験的リスク最小化のためのニュートン法の新しい変種について検討した。
目的関数の勾配と Hessian は、ロバストな推定器に置き換えられる。
また,共役勾配法に基づくニュートン方向のロバストな解を求めるアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-30T18:54:54Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳(メタデータ) (2021-12-29T18:46:52Z) - On Asymptotic Linear Convergence of Projected Gradient Descent for
Constrained Least Squares [22.851500417035947]
この写本は、制約最小二乗の文脈における射影勾配降下の解析のための統一的な枠組みを提示する。
本稿では,PGDの収束解析のレシピを提示し,このレシピを4つの基本的な問題に応用して実証する。
論文 参考訳(メタデータ) (2021-12-22T09:49:51Z) - Fractal Structure and Generalization Properties of Stochastic
Optimization Algorithms [71.62575565990502]
最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。
さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
論文 参考訳(メタデータ) (2021-06-09T08:05:36Z) - Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector
Problems [78.95866278697777]
本研究では,多元的固有ベクトルを分散制約で同時に計算するTruncated Orthogonal Iterationの2つの変種を提案する。
次に,我々のアルゴリズムを適用して,幅広いテストデータセットに対するスパース原理成分分析問題を解く。
論文 参考訳(メタデータ) (2021-03-24T23:11:32Z) - Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。
本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
論文 参考訳(メタデータ) (2020-12-09T20:19:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。