論文の概要: Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models

• arxiv url: http://arxiv.org/abs/2411.15669v2
• Date: Sat, 12 Apr 2025 04:01:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-15 16:46:33.030211
• Title: Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models
• Title（参考訳）: 暗黙の高次モーメントテンソル推定と学習潜在変数モデル
• Authors: Ilias Diakonikolas, Daniel M. Kane,
• Abstract要約: 我々は,暗黙のモーメントテンソル複雑性を表わす汎用的アルゴリズムを開発した。 暗黙のモーメント推定アルゴリズムを利用して、以下のモデルに対して最初の$mathrmpoly(d, k, 1/epsilon)$-time学習アルゴリズムを得る。
• 参考スコア（独自算出の注目度）: 39.33814194788341
• License:
• Abstract: We study the task of learning latent-variable models. A common algorithmic technique for this task is the method of moments. Unfortunately, moment-based approaches are hampered by the fact that the moment tensors of super-constant degree cannot even be written down in polynomial time. Motivated by such learning applications, we develop a general efficient algorithm for {\em implicit moment tensor computation}. Our framework generalizes the work of~\cite{LL21-opt} which developed an efficient algorithm for the specific moment tensors that arise in clustering mixtures of spherical Gaussians. By leveraging our implicit moment estimation algorithm, we obtain the first $\mathrm{poly}(d, k)$-time learning algorithms for the following models. * {\bf Mixtures of Linear Regressions} We give a $\mathrm{poly}(d, k, 1/\epsilon)$-time algorithm for this task, where $\epsilon$ is the desired error. * {\bf Mixtures of Spherical Gaussians} For density estimation, we give a $\mathrm{poly}(d, k, 1/\epsilon)$-time learning algorithm, where $\epsilon$ is the desired total variation error, under the condition that the means lie in a ball of radius $O(\sqrt{\log k})$. For parameter estimation, we give a $\mathrm{poly}(d, k, 1/\epsilon)$-time algorithm under the {\em optimal} mean separation of $\Omega(\log^{1/2}(k/\epsilon))$. * {\bf Positive Linear Combinations of Non-Linear Activations} We give a general algorithm for this task with complexity $\mathrm{poly}(d, k) g(\epsilon)$, where $\epsilon$ is the desired error and the function $g$ depends on the Hermite concentration of the target class of functions. Specifically, for positive linear combinations of ReLU activations, our algorithm has complexity $\mathrm{poly}(d, k) 2^{\mathrm{poly}(1/\epsilon)}$.
• Abstract（参考訳）: 潜在変数モデル学習の課題について検討する。 このタスクの一般的なアルゴリズム手法はモーメントの方法である。 残念なことに、モーメントベースのアプローチは、超定常次数のモーメントテンソルが多項式時間で書き下せないという事実によって妨げられている。 このような学習に動機づけられた我々は、暗黙のモーメントテンソル計算のための一般的な効率的なアルゴリズムを開発した。 球状ガウスのクラスタリング混合で生じる特定のモーメントテンソルの効率的なアルゴリズムを開発した~\cite{LL21-opt} の研究を一般化する。 暗黙のモーメント推定アルゴリズムを利用して、以下のモデルに対して最初の$\mathrm{poly}(d, k)$-time学習アルゴリズムを得る。 bf Mixtures of Linear Regressions} このタスクに対して$\mathrm{poly}(d, k, 1/\epsilon)$-timeアルゴリズムを与えます。 密度推定に$\mathrm{poly}(d, k, 1/\epsilon)$-time Learning algorithm, where $\epsilon$ is the desired total variation error, under the means lies in a ball of radius $O(\sqrt{\log k})$。 パラメータ推定には、$\mathrm{poly}(d, k, 1/\epsilon)$-time アルゴリズムを {\emOptim} の下で与え、$\Omega(\log^{1/2}(k/\epsilon))$を分離する。 * {\displaystyle {\bf\sitive Linear Combination of Non-Linear Activations} この問題に対する一般アルゴリズムを複雑度$\mathrm{poly}(d, k) g(\epsilon)$, where $\epsilon$ is the desired error and the function $g$は関数のターゲットクラスのエルミート濃度に依存する。 具体的には、ReLU活性化の正の線形結合に対して、我々のアルゴリズムは複雑性$\mathrm{poly}(d, k) 2^{\mathrm{poly}(1/\epsilon)}$を持つ。

関連論文リスト

• Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
  閾値降下を用いた単一ニューロンモデル学習のための近似境界を導出する。 線形回帰問題も研究し、$sigma(mathbfx) = mathbfx$ となる。
  論文  参考訳（メタデータ） (2024-09-05T16:59:56Z)
• Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
  本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。 具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
  論文  参考訳（メタデータ） (2024-08-21T01:39:42Z)
• A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation [6.853165736531941]
  逆数外乱の存在下でのスパース平均推定のアルゴリズム的問題について検討する。 我々の主な貢献は、$mathrmpoly(k,log d,1/epsilon)$サンプルを用いて、エフェサブクアクラティック時間で実行される頑健なスパース平均推定アルゴリズムである。
  論文  参考訳（メタデータ） (2024-03-07T18:23:51Z)
• Do you know what q-means? [50.045011844765185]
  クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。 クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。 また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• 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)
• 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)
• Near-Optimal Quantum Coreset Construction Algorithms for Clustering [15.513270929560088]
  我々は、$tildeO(sqrtnkd3/2)$クエリ複雑性を持つ$mathbbRd$で$k$-clusteringのコアセットを見つける量子アルゴリズムを与える。 私たちのコアセットは入力サイズを$n$から$mathrmpoly(kepsilon-1d)$に減らします。
  論文  参考訳（メタデータ） (2023-06-05T12:22:46Z)
• Most Neural Networks Are Almost Learnable [52.40331776572531]
  固定された$epsilon>0$とdeep $i$に対して、深さ$i$のランダムなXavierネットワークを学習するポリ時間アルゴリズムが存在することを示す。 このアルゴリズムは時間とサンプルの複雑さが$(bard)mathrmpoly(epsilon-1)$であり、$bar d$はネットワークのサイズである。 シグモイドやReLU様の活性化の場合、境界は$(bard)mathrmpolylog(eps)に改善できる。
  論文  参考訳（メタデータ） (2023-05-25T22:27:42Z)
• 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)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)

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

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