Fugu-MT 論文翻訳(概要): Learning GMMs with Nearly Optimal Robustness Guarantees

論文の概要: Learning GMMs with Nearly Optimal Robustness Guarantees

arxiv url: http://arxiv.org/abs/2104.09665v1
Date: Mon, 19 Apr 2021 22:14:54 GMT
ステータス: 処理完了
システム内更新日: 2021-04-21 13:45:48.184422
Title: Learning GMMs with Nearly Optimal Robustness Guarantees
Title（参考訳）: ほぼ最適ロバスト性保証を用いたGMM学習
Authors: Allen Liu, Ankur Moitra
Abstract要約: ロバスト性保証は多対数因子に最適である。我々のアルゴリズムの核心は、不適切な学習問題の解法に対応する方程式の系を緩和する新しい方法である。
参考スコア（独自算出の注目度）: 25.313563663123354
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this work we solve the problem of robustly learning a high-dimensional Gaussian mixture model with $k$ components from $\epsilon$-corrupted samples up to accuracy $\widetilde{O}(\epsilon)$ in total variation distance for any constant $k$ and with mild assumptions on the mixture. This robustness guarantee is optimal up to polylogarithmic factors. At the heart of our algorithm is a new way to relax a system of polynomial equations which corresponds to solving an improper learning problem where we are allowed to output a Gaussian mixture model whose weights are low-degree polynomials.
Abstract（参考訳）: この研究では、$\epsilon$-corrupted sample から $\widetilde{O}(\epsilon)$ までの高次元ガウス混合モデルと$k$の成分を、任意の定数$k$に対する全変動距離と、混合物上の軽度の仮定で頑健に学習する。この堅牢性保証は多対数因子に最適である。このアルゴリズムの核心は, 重みが低次多項式であるガウス混合モデルを出力することを許される不適切な学習問題を解くことに対応する多項式方程式系を緩和する新しい方法である。

関連論文リスト

Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文参考訳（メタデータ） (2024-05-10T09:58:47Z)
Learning general Gaussian mixtures with efficient score matching [16.06356123715737]
我々は、$d$次元で$k$ガウシアンの混合を学習する問題を研究する。我々は、下層の混合成分について分離を前提としない。我々は、ターゲット混合物から$dmathrmpoly(k/varepsilon)$サンプルを抽出し、サンプル-ポリノミカル時間で実行し、サンプリング器を構築するアルゴリズムを提案する。
論文参考訳（メタデータ） (2024-04-29T17:30:36Z)
Learning Mixtures of Gaussians Using Diffusion Models [9.118706387430883]
テレビエラーに対して$k$ Gaussiansの混合を学習するための新しいアルゴリズムを提案する。我々のアプローチは解析的であり、拡散モデルの枠組みに依存している。
論文参考訳（メタデータ） (2024-04-29T17:00:20Z)
Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games [104.74734408204749]
マルチプレイヤーの汎用正規形式ゲームにおいて,OMWU(Optimistic Multiplicative Weights Update)を用いているエージェントが全員,O(textrmpolylog(T))$(T$)$(T$)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$)であることを示す。外部の後悔から内部の後悔へと結果を拡張し、後悔を交換することで、近似した平衡に収束する非結合学習ダイナミクスを確立する。
論文参考訳（メタデータ） (2021-11-11T01:19:53Z)
Robustly Learning Mixtures of $k$ Arbitrary Gaussians [47.40835932474677]
任意の固定された$k$に対して$k$任意のガウスの混合を$mathbbRd$で頑健に推定する問題に対して、一定数の任意の汚職が存在する場合の時間アルゴリズムを与える。本研究の主なツールは,2乗法に依拠する効率的な分節クラスタリングアルゴリズムと,Frobeniusノルムおよび低ランク項の誤りを許容する新しいテンソル分解アルゴリズムである。
論文参考訳（メタデータ） (2020-12-03T17:54:03Z)
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)
Robust Learning of Mixtures of Gaussians [13.173307471333617]
我々は、$X$が任意の$d$-次元ガウス多様体の均等な重み付け混合であるときに、$poly(eps)$を総変量で誤りを犯すことを学ぶ。特に、$X$ が 2 つの任意の$d$次元ガウス多様体の均等な重み付き混合であれば、$X$ a $eps$-fraction からサンプルにアクセスする時間アルゴリズムを考案する。
論文参考訳（メタデータ） (2020-07-12T05:15:50Z)
Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文参考訳（メタデータ） (2020-05-13T16:44:12Z)
Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
論文参考訳（メタデータ） (2020-02-20T10:50:58Z)

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