論文の概要: Homeomorphic-Invariance of EM: Non-Asymptotic Convergence in KL Divergence for Exponential Families via Mirror Descent

• arxiv url: http://arxiv.org/abs/2011.01170v3
• Date: Mon, 28 Feb 2022 00:43:11 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-30 11:21:33.622020
• Title: Homeomorphic-Invariance of EM: Non-Asymptotic Convergence in KL Divergence for Exponential Families via Mirror Descent
• Title（参考訳）: ミラー降下による指数関数族kl発散におけるem:非漸近収束の同相-不変性
• Authors: Frederik Kunstner, Raunak Kumar, Mark Schmidt
• Abstract要約: 指数関数的な家族分布の一般的な設定では、EMをミラー降下アルゴリズムと見なすとクルバック・リーブラー分岐の収束率につながることを示す。 以前の研究とは対照的に、分析はパラメトリゼーションの選択に関係しており、最小限の仮定で成り立つ。
• 参考スコア（独自算出の注目度）: 18.045545816267385
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Expectation maximization (EM) is the default algorithm for fitting probabilistic models with missing or latent variables, yet we lack a full understanding of its non-asymptotic convergence properties. Previous works show results along the lines of "EM converges at least as fast as gradient descent" by assuming the conditions for the convergence of gradient descent apply to EM. This approach is not only loose, in that it does not capture that EM can make more progress than a gradient step, but the assumptions fail to hold for textbook examples of EM like Gaussian mixtures. In this work we first show that for the common setting of exponential family distributions, viewing EM as a mirror descent algorithm leads to convergence rates in Kullback-Leibler (KL) divergence. Then, we show how the KL divergence is related to first-order stationarity via Bregman divergences. In contrast to previous works, the analysis is invariant to the choice of parametrization and holds with minimal assumptions. We also show applications of these ideas to local linear (and superlinear) convergence rates, generalized EM, and non-exponential family distributions.
• Abstract（参考訳）: 期待最大化 (EM) は確率モデルを欠落変数や潜伏変数に適合させるデフォルトのアルゴリズムであるが、その非漸近収束特性の完全な理解は欠如している。 従来の研究は、勾配降下の収束条件をEMに適用すると仮定して、少なくとも勾配降下の速度で「EM収束」の線に沿って結果を示す。 このアプローチはゆるいだけでなく、 EM が勾配のステップよりも多くの進歩を達成できるのを捉えないという点で、ガウス混合のような EM の教科書の例に対して仮定は成り立たない。 本研究は,指数関数系分布の共通設定において,EMをミラー降下アルゴリズムとみなしてクルバック・リーブラー(KL)の偏差の収束率を導出することを示す。 次に、KLの発散がブレグマン発散による一階定常性とどのように関係しているかを示す。 以前の研究とは対照的に、解析はパラメトリゼーションの選択に不変であり、最小の仮定で成り立つ。 また、これらのアイデアを局所線型(および超線型)収束率、一般化EMおよび非指数族分布に適用する。

関連論文リスト

• Generalizing Stochastic Smoothing for Differentiation and Gradient Estimation [59.86921150579892]
  アルゴリズム,演算子,シミュレータ,その他の微分不可能関数の微分可能緩和に対する勾配推定の問題に対処する。 我々は、微分可能なソートとランキングのための分散化戦略、グラフ上の微分可能なショートパス、ポーズ推定のための微分可能なレンダリング、および微分可能なCryo-ETシミュレーションを開発する。
  論文  参考訳（メタデータ） (2024-10-10T17:10:00Z)
• Understanding Stochastic Natural Gradient Variational Inference [12.800664845601197]
  グローバル収束率$mathcalO(frac1)$は暗黙的にNGVIの非漸近収束率を示す。 速度は降下(ブラックボックス変分推論)よりも悪くなく、一定の依存性がある。
  論文  参考訳（メタデータ） (2024-06-04T00:45:37Z)
• Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence [25.717501580080846]
  本稿では、現代の非最適化設定における勾配フォワードミラー(SMD)の収束を再考する。 トレーニングのために,線形ネットワーク問題に対する確率収束アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-02-27T17:56:49Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。 我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
  論文  参考訳（メタデータ） (2023-06-29T01:20:44Z)
• Convergence and concentration properties of constant step-size SGD through Markov chains [0.0]
  定常段差勾配勾配(SGD)を用いた滑らかで強凸な目標の最適化について検討する。 緩やかに制御された分散を伴う不偏勾配推定に対して、反復は全変動距離の不変分布に収束することを示す。 全ての結果は無症状であり、その結果はいくつかのアプリケーションを通して議論されている。
  論文  参考訳（メタデータ） (2023-06-20T12:36:28Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• Convergence Rates for the MAP of an Exponential Family and Stochastic Mirror Descent -- an Open Problem [33.74484936098467]
  最大推定値の対数的部分最適度を上界化することの問題点を考察する。 驚いたことに、この問題に対する一般的な解決策は文献には見つからなかった。
  論文  参考訳（メタデータ） (2021-11-12T17:18:06Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。 一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
  論文  参考訳（メタデータ） (2020-04-09T17:54:18Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。