論文の概要: Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms

• arxiv url: http://arxiv.org/abs/2601.05157v1
• Date: Thu, 08 Jan 2026 17:47:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-09 17:01:53.311921
• Title: Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms
• Title（参考訳）: 高次元スパースフーリエ変換による混合モデルの学習
• Authors: Alkis Kalavasis, Pravesh K. Kothari, Shuchen Li, Manolis Zampetakis,
• Abstract要約: 我々は、$d$次元で$k$球面分布の混合のパラメータを効率的に学習する、$rm poly(d,k)$ time and sampleアルゴリズムを提供する。 クラスタ分布が十分に重い尾を持つ特性関数を持つ場合,本手法は成功する。
• 参考スコア（独自算出の注目度）: 13.490333761774542
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we give a ${\rm poly}(d,k)$ time and sample algorithm for efficiently learning the parameters of a mixture of $k$ spherical distributions in $d$ dimensions. Unlike all previous methods, our techniques apply to heavy-tailed distributions and include examples that do not even have finite covariances. Our method succeeds whenever the cluster distributions have a characteristic function with sufficiently heavy tails. Such distributions include the Laplace distribution but crucially exclude Gaussians. All previous methods for learning mixture models relied implicitly or explicitly on the low-degree moments. Even for the case of Laplace distributions, we prove that any such algorithm must use super-polynomially many samples. Our method thus adds to the short list of techniques that bypass the limitations of the method of moments. Somewhat surprisingly, our algorithm does not require any minimum separation between the cluster means. This is in stark contrast to spherical Gaussian mixtures where a minimum $\ell_2$-separation is provably necessary even information-theoretically [Regev and Vijayaraghavan '17]. Our methods compose well with existing techniques and allow obtaining ''best of both worlds" guarantees for mixtures where every component either has a heavy-tailed characteristic function or has a sub-Gaussian tail with a light-tailed characteristic function. Our algorithm is based on a new approach to learning mixture models via efficient high-dimensional sparse Fourier transforms. We believe that this method will find more applications to statistical estimation. As an example, we give an algorithm for consistent robust mean estimation against noise-oblivious adversaries, a model practically motivated by the literature on multiple hypothesis testing. It was formally proposed in a recent Master's thesis by one of the authors, and has already inspired follow-up works.
• Abstract（参考訳）: 本研究では,$d$次元の球面分布の混合のパラメータを効率的に学習するための,${\rm poly}(d,k)$時間とサンプルアルゴリズムを提案する。 従来の手法とは異なり、我々の手法は重み付き分布に適用され、有限共分散をもたない例を含む。 クラスタ分布が十分に重い尾を持つ特性関数を持つ場合,本手法は成功する。 そのような分布はラプラス分布を含むが、ガウス分布を極端に除外する。 それまでの混合モデルの学習方法は、暗黙的あるいは暗黙的に低度モーメントに依存していた。 ラプラス分布の場合であっても、そのようなアルゴリズムは超ポリノミカルな多くのサンプルを使わなければならない。 そこで本手法はモーメントの手法の限界をバイパスする手法の短いリストに追加する。 驚くべきことに、我々のアルゴリズムはクラスタ間の最小限の分離を必要としない。 これは、最小$\ell_2$-セパレーションが情報理論においても確実に必要である球状ガウス混合とは対照的である [Regev and Vijayaraghavan '17]。 提案手法は,各成分が重み付き特性関数を持つ場合や,軽み付き特性関数を持つ準ガウス的テールを有する場合の「両世界のベスト」保証を得ることが可能である。 本アルゴリズムは,高速な高次元スパースフーリエ変換を用いた混合モデルの学習手法に基づく。 我々は,この手法が統計的推定により多くの応用をもたらすと信じている。 一例として、複数の仮説テストに関する文献によって実質的に動機づけられたモデルである、雑音に満ちた敵に対する一貫したロバストな平均推定法を提案する。 これは、著者の1人による最近のマスター論文で正式に提案され、既にフォローアップ作品にインスピレーションを与えている。

関連論文リスト

• 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の混合をTVエラー$varepsilon$、quasi-polynomial$O(ntextpoly,logleft(fracn+kvarepsilonright)$で学習するための新しいアルゴリズムを提供する。 結果は、混合分布が一定半径の$k$球の和で支持されるガウスの連続混合に拡張される。
  論文  参考訳（メタデータ） (2024-04-29T17:00:20Z)
• Semi-Bandit Learning for Monotone Stochastic Optimization [16.921694787482213]
  一般的なオンライン学習アルゴリズムは「モノトーン」問題のクラスのために開発されている。 当社のフレームワークは,預言不平等やPandoraのボックス,単一リソースの収益管理,ポスト価格など,いくつかの基本的な問題に適用しています。
  論文  参考訳（メタデータ） (2023-12-24T07:46:37Z)
• Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
  Langevin Monte Carlo Thompson Sampling (LMC-TS) が提案されている。 提案アルゴリズムは,文脈的帯域幅の特別な場合において,最高のトンプソンサンプリングアルゴリズムと同じサブ線形残差を達成できることを示す。
  論文  参考訳（メタデータ） (2022-06-22T17:58:23Z)
• A Robust and Flexible EM Algorithm for Mixtures of Elliptical Distributions with Missing Data [71.9573352891936]
  本稿では、ノイズや非ガウス的なデータに対するデータ計算の欠如に対処する。 楕円分布と潜在的な欠落データを扱う特性を混合した新しいEMアルゴリズムについて検討した。 合成データの実験的結果は,提案アルゴリズムが外れ値に対して頑健であり,非ガウスデータで使用可能であることを示す。
  論文  参考訳（メタデータ） (2022-01-28T10:01:37Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)

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

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