論文の概要: On Learning Parallel Pancakes with Mostly Uniform Weights

• arxiv url: http://arxiv.org/abs/2504.15251v1
• Date: Mon, 21 Apr 2025 17:31:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-29 15:55:10.205827
• Title: On Learning Parallel Pancakes with Mostly Uniform Weights
• Title（参考訳）: ほぼ均一な重みを持つ並列パンケーキの学習について
• Authors: Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Jasper C. H. Lee, Thanasis Pittas,
• Abstract要約: k$-mixtures of Gaussians (k$-GMMs) on $mathbbRd$。 このような混合と標準ガウスの区別は SQ-hard であることが示される。
• 参考スコア（独自算出の注目度）: 42.63152235265314
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the complexity of learning $k$-mixtures of Gaussians ($k$-GMMs) on $\mathbb{R}^d$. This task is known to have complexity $d^{\Omega(k)}$ in full generality. To circumvent this exponential lower bound on the number of components, research has focused on learning families of GMMs satisfying additional structural properties. A natural assumption posits that the component weights are not exponentially small and that the components have the same unknown covariance. Recent work gave a $d^{O(\log(1/w_{\min}))}$-time algorithm for this class of GMMs, where $w_{\min}$ is the minimum weight. Our first main result is a Statistical Query (SQ) lower bound showing that this quasi-polynomial upper bound is essentially best possible, even for the special case of uniform weights. Specifically, we show that it is SQ-hard to distinguish between such a mixture and the standard Gaussian. We further explore how the distribution of weights affects the complexity of this task. Our second main result is a quasi-polynomial upper bound for the aforementioned testing task when most of the weights are uniform while a small fraction of the weights are potentially arbitrary.
• Abstract（参考訳）: 我々は$k$-mixtures of Gaussians (k$-GMMs) on $\mathbb{R}^d$の複雑さについて研究する。 このタスクは複雑性$d^{\Omega(k)}$を完全一般性で持つことが知られている。 成分数に対するこの指数的な低い境界を回避するために、GMMの学習系がさらなる構造的特性を満たすことに焦点を当てている。 自然な仮定は、成分の重みが指数関数的に小さくなく、成分が同じ未知の共分散を持つことを仮定する。 最近の研究は、このクラスのGMMに対して$d^{O(\log(1/w_{\min}))}$-timeアルゴリズムを提供しており、$w_{\min}$は最小の重みである。 最初の主な結果は統計的クエリ (SQ) の下界であり、この準多項式上界は、一様重みの特別な場合であっても、本質的には最適であることを示す。 具体的には、そのような混合と標準ガウスを区別することが SQ-hard であることが示される。 さらに、重みの分布がこのタスクの複雑さにどのように影響するかを考察する。 2つ目の結果は、上記のテストタスクの準多項式上界で、重量の大部分が均一であり、重量のごく一部が任意である場合である。

関連論文リスト

• Sum-of-squares lower bounds for Non-Gaussian Component Analysis [33.80749804695003]
  非ガウス成分分析(Non-Gaussian Component Analysis、NGCA)は、高次元データセットにおいて非ガウス方向を求める統計的タスクである。 本稿では Sum-of-Squares フレームワークにおける NGCA の複雑さについて考察する。
  論文  参考訳（メタデータ） (2024-10-28T18:19:13Z)
• Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples [9.649879910148854]
  差分プライバシー(DP)制約下におけるガウシアン混合量の推定問題について検討する。 主な結果は、$textpoly(k,d,1/alpha,1/varepsilon,log (1/delta))$サンプルが$k$ Gaussians in $mathbbRd$から$alpha$までを推定するのに十分であることです。 これは GMM の構造的仮定を一切含まない問題に対する最初の有限標本複雑性上界である。
  論文  参考訳（メタデータ） (2023-09-07T17:02:32Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
  ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
  論文  参考訳（メタデータ） (2023-02-27T16:34:21Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。 1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。 テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
  論文  参考訳（メタデータ） (2022-11-10T00:40:37Z)
• Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures [9.670578317106182]
  kgeq 2$ Gaussian 成分と未知の手段と未知の共分散(すべての成分について同一視される)の混合を考える。 混合重量が指数関数的に小さい場合にのみこのような硬さが現れることを示す。 我々は,最小混合重量の時間準多項式を用いた2乗法に基づくアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-12-10T10:51:44Z)
• Robust Model Selection and Nearly-Proper Learning for GMMs [26.388358539260473]
  学習理論では、データは有限混合モデルから生成されるという標準的な仮定がある。しかし、コンポーネントの数が事前に分かっていないときに何が起こるのか。 対数係数内の分布に適合するために必要な最小コンポーネント数を、およそ決定することができる。
  論文  参考訳（メタデータ） (2021-06-05T01:58:40Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)

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

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