論文の概要: SQ Lower Bounds for Learning Bounded Covariance GMMs
- arxiv url: http://arxiv.org/abs/2306.13057v1
- Date: Thu, 22 Jun 2023 17:23:36 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-23 13:26:55.748763
- Title: SQ Lower Bounds for Learning Bounded Covariance GMMs
- Title（参考訳）: 境界共分散GMM学習のためのSQ下界
- Authors: Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis
- Abstract要約: P= sum_i=1k w_i MathcalN(boldsymbol mu_i,mathbf Sigma_i)$ という形で、分離されたガウスの混合を $mathbbRd$ で学習することに焦点を当てる。
この問題に対する統計的クエリ(SQ)アルゴリズムは、少なくともdOmega (1/epsilon)$の複雑さを必要とすることを証明している。
- 参考スコア（独自算出の注目度）: 46.289382906761304
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the complexity of learning mixtures of separated Gaussians with
common unknown bounded covariance matrix. Specifically, we focus on learning
Gaussian mixture models (GMMs) on $\mathbb{R}^d$ of the form $P= \sum_{i=1}^k
w_i \mathcal{N}(\boldsymbol \mu_i,\mathbf \Sigma_i)$, where $\mathbf \Sigma_i =
\mathbf \Sigma \preceq \mathbf I$ and $\min_{i \neq j} \| \boldsymbol \mu_i -
\boldsymbol \mu_j\|_2 \geq k^\epsilon$ for some $\epsilon>0$. Known learning
algorithms for this family of GMMs have complexity $(dk)^{O(1/\epsilon)}$. In
this work, we prove that any Statistical Query (SQ) algorithm for this problem
requires complexity at least $d^{\Omega(1/\epsilon)}$. In the special case
where the separation is on the order of $k^{1/2}$, we additionally obtain
fine-grained SQ lower bounds with the correct exponent. Our SQ lower bounds
imply similar lower bounds for low-degree polynomial tests. Conceptually, our
results provide evidence that known algorithms for this problem are nearly best
possible.
- Abstract（参考訳）: 未知有界共分散行列を持つ分離ガウスの混合学習の複雑さについて検討した。
具体的には、$\mathbb{R}^d$ 上のガウス混合モデル (GMMs) について、$P= \sum_{i=1}^k w_i \mathcal{N}(\boldsymbol \mu_i,\mathbf \Sigma_i)$ ここで、$\mathbf \Sigma_i = \mathbf \Sigma \preceq \mathbf I$ と $\min_{i \neq j} \| \boldsymbol \mu_i\| \geq k^\epsilon$ を学習する。
このGMMの族に対する学習アルゴリズムは、複雑さ$(dk)^{O(1/\epsilon)}$を持つ。
本研究では,この問題に対する統計的クエリ (SQ) アルゴリズムが,少なくとも$d^{\Omega(1/\epsilon)}$の複雑性を必要とすることを証明した。
分離が$k^{1/2}$の順序である特別な場合、正しい指数を持つきめ細かい SQ の下界も得られる。
我々のSQ下限は、低次多項式テストに類似した下限を暗示する。
概念的には、この問題の既知のアルゴリズムが可能な限り最善であることを示す。
関連論文リスト
- Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models [37.42736399673992]
シングルインデックスモデル (SIM) は $sigma(mathbfwast cdot mathbfx)$ という形式の関数であり、$sigma: mathbbR to mathbbR$ は既知のリンク関数であり、$mathbfwast$ は隠れ単位ベクトルである。
適切な学習者が$L2$-error of $O(mathrmOPT)+epsilon$。
論文 参考訳（メタデータ） (2024-11-08T17:10:38Z) - Statistical Query Lower Bounds for Learning Truncated Gaussians [43.452452030671694]
この問題のSQアルゴリズムの複雑さは、$dmathrmpoly (1/epsilon)$であり、クラス$mathcalC$が単純である場合でも、$mathrmpoly(d/epsilon)が情報理論的に十分であることを示す。
論文 参考訳（メタデータ） (2024-03-04T18:30:33Z) - SQ Lower Bounds for Learning Mixtures of Linear Classifiers [43.63696593768504]
この問題に対する既知のアルゴリズムは、一様混合の特別な場合であっても、本質的には最善であることを示す。
重要な技術的要素は、独立した関心を持つかもしれない球面設計の新たな構築である。
論文 参考訳（メタデータ） (2023-10-18T10:56:57Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。