論文の概要: Alternating Minimization Converges Super-Linearly for Mixed Linear
Regression
- arxiv url: http://arxiv.org/abs/2004.10914v2
- Date: Tue, 11 Aug 2020 18:57:59 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-10 09:02:37.672155
- Title: Alternating Minimization Converges Super-Linearly for Mixed Linear
Regression
- Title（参考訳）: 交互最小化による線形回帰の超線形化
- Authors: Avishek Ghosh, Kannan Ramchandran
- Abstract要約: 混合ランダム線形方程式を解く問題に対処する。
複数の線形回帰から得られるラベルのない観測結果があり、各観測結果は正確に1つの回帰モデルに対応する。
目標は、観測から線形回帰器を学習することである。
- 参考スコア（独自算出の注目度）: 18.275029820972517
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We address the problem of solving mixed random linear equations. We have
unlabeled observations coming from multiple linear regressions, and each
observation corresponds to exactly one of the regression models. The goal is to
learn the linear regressors from the observations. Classically, Alternating
Minimization (AM) (which is a variant of Expectation Maximization (EM)) is used
to solve this problem. AM iteratively alternates between the estimation of
labels and solving the regression problems with the estimated labels.
Empirically, it is observed that, for a large variety of non-convex problems
including mixed linear regression, AM converges at a much faster rate compared
to gradient based algorithms. However, the existing theory suggests similar
rate of convergence for AM and gradient based methods, failing to capture this
empirical behavior. In this paper, we close this gap between theory and
practice for the special case of a mixture of $2$ linear regressions. We show
that, provided initialized properly, AM enjoys a \emph{super-linear} rate of
convergence in certain parameter regimes. To the best of our knowledge, this is
the first work that theoretically establishes such rate for AM. Hence, if we
want to recover the unknown regressors upto an error (in $\ell_2$ norm) of
$\epsilon$, AM only takes $\mathcal{O}(\log \log (1/\epsilon))$ iterations.
Furthermore, we compare AM with a gradient based heuristic algorithm
empirically and show that AM dominates in iteration complexity as well as
wall-clock time.
- Abstract（参考訳）: 我々は混合ランダム線形方程式の解法について論じる。
我々は、複数の線形回帰から得られるラベルなしの観測を行い、それぞれの観測は回帰モデルのちょうど1つに対応する。
目標は、観測から線形回帰器を学習することである。
古典的には、この問題を解決するために Alternating Minimization (AM) (期待最小化 (EM) の変種である) が用いられる。
AMはラベルの推定と回帰問題を推定ラベルで繰り返し交互に解く。
実験的に、混合線形回帰を含む様々な非凸問題に対して、AMは勾配に基づくアルゴリズムよりもはるかに高速な速度で収束することが観察された。
しかし、既存の理論は、am法と勾配法で同様の収束率を示しており、この経験的振る舞いを捉えられなかった。
本稿では,2ドルの線形回帰の混合の特別な場合に対する理論と実践のギャップを閉じる。
初期化が適切に行われると、am は特定のパラメータレジームにおける収束率 \emph{super-linear} を享受できる。
私たちの知る限りでは、これは理論上 am に対してそのような速度を確立する最初の仕事です。
したがって、未知の回帰器を$\epsilon$のエラー($\ell_2$ norm)まで回復したい場合、AMは$\mathcal{O}(\log \log (1/\epsilon))$イテレーションのみを取る。
さらに、AMと勾配に基づくヒューリスティックアルゴリズムを経験的に比較し、AMが繰り返しの複雑さと壁時計時間で支配的であることを示す。
関連論文リスト
- Scaling Laws in Linear Regression: Compute, Parameters, and Data [86.48154162485712]
無限次元線形回帰セットアップにおけるスケーリング法則の理論について検討する。
テストエラーの再現可能な部分は$Theta(-(a-1) + N-(a-1)/a)$であることを示す。
我々の理論は経験的ニューラルスケーリング法則と一致し、数値シミュレーションによって検証される。
論文 参考訳（メタデータ） (2024-06-12T17:53:29Z) - Agnostic Learning of Mixed Linear Regressions with EM and AM Algorithms [22.79595679373698]
混合線形回帰は統計学と機械学習においてよく研究されている問題である。
本稿では、サンプルから混合線形回帰を学習する際のより一般的な問題について考察する。
AMアルゴリズムとEMアルゴリズムは, 集団損失最小化器に収束することにより, 混合線形回帰学習につながることを示す。
論文 参考訳（メタデータ） (2024-06-03T09:43:24Z) - Mixed Regression via Approximate Message Passing [16.91276351457051]
複数の信号と潜伏変数を持つ一般化線形モデル(GLM)における回帰問題について検討する。
混合線形回帰では、それぞれの観測は$L$信号ベクトル(回帰器)の1つから来るが、どれがどれであるかはわからない。
最大アフィン回帰では、各観測は最大で$L$アフィン関数から成り、それぞれ異なる信号ベクトルによって定義される。
論文 参考訳（メタデータ） (2023-04-05T04:59:59Z) - Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。
任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
論文 参考訳（メタデータ） (2023-01-16T02:57:37Z) - A flexible empirical Bayes approach to multiple linear regression and connections with penalized regression [8.663322701649454]
大規模多重回帰に対する新しい経験的ベイズ手法を提案する。
当社のアプローチでは、フレキシブルな"適応縮小"と変分近似の2つの主要なアイデアが組み合わさっている。
提案手法では, 後進平均値がペナル化回帰問題を解く。
論文 参考訳（メタデータ） (2022-08-23T12:42:57Z) - Matrix Completion via Non-Convex Relaxation and Adaptive Correlation
Learning [90.8576971748142]
閉形式解によって最適化できる新しいサロゲートを開発する。
そこで我々は, 上向きの相関関係を利用して, 適応的相関学習モデルを構築した。
論文 参考訳（メタデータ） (2022-03-04T08:50:50Z) - Optimal Online Generalized Linear Regression with Stochastic Noise and
Its Application to Heteroscedastic Bandits [88.6139446295537]
一般化線形モデルの設定におけるオンライン一般化線形回帰の問題について検討する。
ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。
本稿では,FTRLに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-28T08:25:26Z) - Permuted and Unlinked Monotone Regression in $\mathbb{R}^d$: an approach
based on mixture modeling and optimal transport [4.924126492174802]
回帰関数の巡回的単調性の概念は、置換/無リンク回帰モデルにおける同定と推定に十分であることを示す。
我々は,Keefer-Wolfowitz に基づく,計算効率が良く,使いやすいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-01-10T18:37:59Z) - Online nonparametric regression with Sobolev kernels [99.12817345416846]
我々は、ソボレフ空間のクラス上の後悔の上限を$W_pbeta(mathcalX)$, $pgeq 2, beta>fracdp$ とする。
上界は minimax regret analysis で支えられ、$beta> fracd2$ または $p=infty$ の場合、これらの値は(本質的に)最適である。
論文 参考訳（メタデータ） (2021-02-06T15:05:14Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - A spectral algorithm for robust regression with subgaussian rates [0.0]
本研究では, 試料の分布に強い仮定がない場合の線形回帰に対する2次時間に対する新しい線形アルゴリズムについて検討する。
目的は、データが有限モーメントしか持たなくても最適な準ガウス誤差を達成できる手順を設計することである。
論文 参考訳（メタデータ） (2020-07-12T19:33:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。