Fugu-MT 論文翻訳(概要): Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models

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

arxiv url: http://arxiv.org/abs/2411.15669v1
Date: Sat, 23 Nov 2024 23:13:24 GMT
ステータス: 翻訳完了
システム内更新日: 2024-11-26 14:22:22.348309
Title: Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models
Title（参考訳）: 暗黙の高次モーメントテンソル推定と学習潜在変数モデル
Authors: Ilias Diakonikolas, Daniel M. Kane,
Abstract要約: 潜在変数モデル学習の課題について検討する。このような応用により、暗黙のモーメント計算のための一般化されたアルゴリズムを開発した。一般的なアルゴリズムを利用して, 以下のモデルに対する初等学習者を得る。
参考スコア（独自算出の注目度）: 39.33814194788341
License:
Abstract: We study the task of learning latent-variable models. An obstacle towards designing efficient algorithms for such models is the necessity of approximating moment tensors of super-constant degree. Motivated by such applications, we develop a general efficient algorithm for implicit moment tensor computation. Our algorithm computes in $\mathrm{poly}(d, k)$ time a succinct approximate description of tensors of the form $M_m=\sum_{i=1}^{k}w_iv_i^{\otimes m}$, for $w_i\in\mathbb{R}_+$--even for $m=\omega(1)$--assuming there exists a polynomial-size arithmetic circuit whose expected output on an appropriate samplable distribution is equal to $M_m$, and whose covariance on this input is bounded. Our framework broadly 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 general algorithm, we obtain the first polynomial-time learners for the following models. * Mixtures of Linear Regressions. We give a $\mathrm{poly}(d, k, 1/\epsilon)$-time algorithm for this task. The previously best algorithm has super-polynomial complexity in $k$. * Learning Mixtures of Spherical Gaussians. We give a $\mathrm{poly}(d, k, 1/\epsilon)$-time density estimation algorithm, under the condition that the means lie in a ball of radius $O(\sqrt{\log k})$. Prior algorithms incur super-polynomial complexity in $k$. We also give a $\mathrm{poly}(d, k, 1/\epsilon)$-time parameter estimation algorithm, under the {\em optimal} mean separation of $\Omega(\log^{1/2}(k/\epsilon))$. * PAC Learning Sums of ReLUs. We give a learner with complexity $\mathrm{poly}(d, k) 2^{\mathrm{poly}(1/\epsilon)}$. This is the first algorithm for this task that runs in $\mathrm{poly}(d, k)$ time for subconstant values of $\epsilon = o_{k, d}(1)$.
Abstract（参考訳）: 潜在変数モデル学習の課題について検討する。このようなモデルの効率的なアルゴリズムを設計する上での障害は、超定常度のモーメントテンソルを近似する必要があることである。このような応用により、暗黙のモーメントテンソル計算のための一般的なアルゴリズムを開発した。我々のアルゴリズムは、$\mathrm{poly}(d, k)$ time a succinct approximate description of tensors of the form $M_m=\sum_{i=1}^{k}w_iv_i^{\otimes m}$, for $w_i\in\mathbb{R}_+$-even for $m=\omega(1)$--仮定すると、適切なサンプリング可能な分布に対して期待される出力が$M_m$であり、この入力に対する共分散が有界である多項式サイズの演算回路が存在する。球状ガウスのクラスタリング混合で生じる特定のモーメントテンソルの効率的なアルゴリズムを開発した~\cite{LL21-opt} の研究を、我々のフレームワークは広く一般化している。一般アルゴリズムを利用して,次のモデルに対する最初の多項式時間学習者を得る。 ※線形回帰の混合この問題に対して$\mathrm{poly}(d, k, 1/\epsilon)$-timeアルゴリズムを与える。これまでで最高のアルゴリズムは、$k$の超多項式複雑性を持つ。 ※球面ガウスの混合を習う。我々は、半径$O(\sqrt{\log k})$の球にあるという条件の下で、$\mathrm{poly}(d, k, 1/\epsilon)$-time density estimationアルゴリズムを与える。以前のアルゴリズムは$k$で超多項式複雑性を発生させる。また、$\Omega(\log^{1/2}(k/\epsilon))$の分離平均の下で、$\mathrm{poly}(d, k, 1/\epsilon)$-timeパラメータ推定アルゴリズムを与える。 ※ PAC Learning Sums of ReLUs 複雑性を持つ学習者には$\mathrm{poly}(d, k) 2^{\mathrm{poly}(1/\epsilon)}$を与える。これは$\mathrm{poly}(d, k)$ time for subconstant value of $\epsilon = o_{k, d}(1)$である。

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

関連論文リスト