論文の概要: Sharp analysis of EM for learning mixtures of pairwise differences
- arxiv url: http://arxiv.org/abs/2302.10066v2
- Date: Thu, 22 Jun 2023 16:22:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-23 17:31:19.270932
- Title: Sharp analysis of EM for learning mixtures of pairwise differences
- Title(参考訳): ペアワイズ差の混合学習のためのemの鋭い解析
- Authors: Abhishek Dhawan, Cheng Mao, Ashwin Pananjady
- Abstract要約: 線形回帰とランダムサンプルの対称混合をペア比較設計から検討する。
我々は、列が線形収束することを証明し、反復数の推定誤差に対して$ell_infty$-normの保証を与える。
EMシーケンスの極限は$ell$-normにおける推定の急激な速度を達成し、情報理論の最適定数と一致することを示す。
- 参考スコア(独自算出の注目度): 14.01151780845689
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a symmetric mixture of linear regressions with random samples
from the pairwise comparison design, which can be seen as a noisy version of a
type of Euclidean distance geometry problem. We analyze the
expectation-maximization (EM) algorithm locally around the ground truth and
establish that the sequence converges linearly, providing an $\ell_\infty$-norm
guarantee on the estimation error of the iterates. Furthermore, we show that
the limit of the EM sequence achieves the sharp rate of estimation in the
$\ell_2$-norm, matching the information-theoretically optimal constant. We also
argue through simulation that convergence from a random initialization is much
more delicate in this setting, and does not appear to occur in general. Our
results show that the EM algorithm can exhibit several unique behaviors when
the covariate distribution is suitably structured.
- Abstract(参考訳): 線形回帰とランダムなサンプルの対称な混合をペア比較設計から考えると、ユークリッド距離幾何学のタイプのノイズのあるバージョンと見なすことができる。
予測最大化(EM)アルゴリズムを地平線周辺で局所的に解析し、その列が線形に収束することを証明し、反復数の推定誤差に対して$\ell_\infty$-norm保証を与える。
さらに,em系列の極限は$\ell_2$-norm において,情報理論上最適定数に適合する鋭い推定率が得られることを示す。
また、この設定では、ランダム初期化からの収束がはるかに繊細であり、一般には発生しないというシミュレーションを通じて論じる。
その結果,共変量分布が適切に構成された場合,EMアルゴリズムはいくつかのユニークな挙動を示すことがわかった。
関連論文リスト
- Unveiling the Cycloid Trajectory of EM Iterations in Mixed Linear Regression [5.883916678819683]
2成分混合線形回帰(2MLR)における反復の軌跡と期待最大化(EM)アルゴリズムの収束率について検討する。
近年, ノイズレスおよび高SNR環境下での2MLRにおけるEMの超線形収束が確立されている。
論文 参考訳(メタデータ) (2024-05-28T14:46:20Z) - Convergence of Expectation-Maximization Algorithm with Mixed-Integer Optimization [5.319361976450982]
本稿では,特定の種類のEMアルゴリズムの収束を保証する一連の条件を紹介する。
本研究では,混合整数非線形最適化問題の解法として,反復アルゴリズムの新しい解析手法を提案する。
論文 参考訳(メタデータ) (2024-01-31T11:42:46Z) - Precise Asymptotics for Spectral Methods in Mixed Generalized Linear Models [31.58736590532443]
混合一般化線形モデルにおいて、統計的に独立な2つの信号を推定する問題を考える。
我々の特徴付けは、ランダム行列、自由確率、および近似メッセージパッシングアルゴリズムの理論からのツールの混合を利用する。
論文 参考訳(メタデータ) (2022-11-21T11:35:25Z) - Stochastic Mirror Descent for Large-Scale Sparse Recovery [13.500750042707407]
本稿では,2次近似の高次元スパースパラメータの統計的推定への応用について論じる。
提案アルゴリズムは, 回帰器分布の弱い仮定の下で, 推定誤差の最適収束を実現する。
論文 参考訳(メタデータ) (2022-10-23T23:23:23Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳(メタデータ) (2021-12-29T18:46:52Z) - Sharp global convergence guarantees for iterative nonconvex
optimization: A Gaussian process perspective [30.524043513721168]
回帰モデルのクラスに対する反復アルゴリズムの収束を解析するための一般的なレシピを開発する。
決定論的には、有限サンプル状態におけるアルゴリズムの収束率と最終的なエラーフロアの両方を正確にキャプチャする。
我々は、更新の交互化に基づく高次アルゴリズムと、下位次数に基づく一次アルゴリズムの両方に対して、鋭い収束率を示す。
論文 参考訳(メタデータ) (2021-09-20T21:48:19Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳(メタデータ) (2021-09-08T18:00:05Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳(メタデータ) (2021-06-30T17:51:36Z) - Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
帰納バイアスは 経験的に過剰フィットを防げる中心的存在です
この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。
我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
論文 参考訳(メタデータ) (2021-03-23T17:15:53Z) - The Connection between Discrete- and Continuous-Time Descriptions of
Gaussian Continuous Processes [60.35125735474386]
我々は、一貫した推定子をもたらす離散化が粗粒化下での不変性を持つことを示す。
この結果は、導関数再構成のための微分スキームと局所時間推論アプローチの組み合わせが、2次または高次微分方程式の時系列解析に役立たない理由を説明する。
論文 参考訳(メタデータ) (2021-01-16T17:11:02Z) - Asymptotic Analysis of an Ensemble of Randomly Projected Linear
Discriminants [94.46276668068327]
[1]では、ランダムに投影された線形判別式のアンサンブルを用いてデータセットを分類する。
我々は,計算コストのかかるクロスバリデーション推定器の代替として,誤分類確率の一貫した推定器を開発する。
また、実データと合成データの両方で投影次元を調整するための推定器の使用を実証する。
論文 参考訳(メタデータ) (2020-04-17T12:47:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。