論文の概要: Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models

• arxiv url: http://arxiv.org/abs/2012.07774v1
• Date: Mon, 14 Dec 2020 18:14:08 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-08 14:12:33.300929
• Title: Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models
• Title（参考訳）: 多項式の近傍ゼロ集合の小さな被覆と潜在変数モデルの学習
• Authors: Ilias Diakonikolas and Daniel M. Kane
• Abstract要約: 我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
• 参考スコア（独自算出の注目度）: 56.98280399449707
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Let $V$ be any vector space of multivariate degree-$d$ homogeneous polynomials with co-dimension at most $k$, and $S$ be the set of points where all polynomials in $V$ {\em nearly} vanish. We establish a qualitatively optimal upper bound on the size of $\epsilon$-covers for $S$, in the $\ell_2$-norm. Roughly speaking, we show that there exists an $\epsilon$-cover for $S$ of cardinality $M = (k/\epsilon)^{O_d(k^{1/d})}$. Our result is constructive yielding an algorithm to compute such an $\epsilon$-cover that runs in time $\mathrm{poly}(M)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models with hidden variables. These include density and parameter estimation for $k$-mixtures of spherical Gaussians (with known common covariance), PAC learning one-hidden-layer ReLU networks with $k$ hidden units (under the Gaussian distribution), density and parameter estimation for $k$-mixtures of linear regressions (with Gaussian covariates), and parameter estimation for $k$-mixtures of hyperplanes. Our algorithms run in time {\em quasi-polynomial} in the parameter $k$. Previous algorithms for these problems had running times exponential in $k^{\Omega(1)}$. At a high-level our algorithms for all these learning problems work as follows: By computing the low-degree moments of the hidden parameters, we are able to find a vector space of polynomials that nearly vanish on the unknown parameters. Our structural result allows us to compute a quasi-polynomial sized cover for the set of hidden parameters, which we exploit in our learning algorithms.
• Abstract（参考訳）: v$ を多変量次数-d$ 等質多項式の任意のベクトル空間とし、k$ 以上の余次元を持つものとし、s$ を、v$ {\em almost} 内のすべての多項式が消えるような点の集合とする。 我々は、$\ell_2$-norm において、$\epsilon$-covers のサイズで定性的に最適な上限を $s$ で定める。 大まかに言えば、濃度$M = (k/\epsilon)^{O_d(k^{1/d})}$の$S$に対して$\epsilon$-coverが存在することを示す。 私たちの結果は、$\mathrm{poly}(m)$で実行される$\epsilon$-coverを計算するためのコンストラクティブなアルゴリズムです。 構造的結果に基づいて,隠れ変数を持ついくつかの基本的高次元確率モデルの学習アルゴリズムを改良した。 これらには、球状ガウス多様体の密度とパラメータ推定(共通共分散を持つ)、400$隠れ単位を持つPAC学習単層ReLUネットワーク(ガウス分布の下で)、リニア回帰の$k$混合に対する密度とパラメータ推定(ガウス共変量を含む)、超平面の$k$混合に対するパラメータ推定が含まれる。 我々のアルゴリズムはパラメータ $k$ で時間 {\em quasi-polynomial} で実行される。 これらの問題の前のアルゴリズムは、$k^{\Omega(1)}$で指数関数的に実行された。 隠れたパラメータの低次モーメントを計算することで、未知のパラメータ上でほぼ消滅する多項式のベクトル空間を見つけることができます。 構造的な結果により、隠れパラメータの集合に対して準多項式サイズのカバーを計算でき、学習アルゴリズムで利用できます。

関連論文リスト

• Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians [7.04316974339151]
  本研究では,サンプルが未知の集合に落下した場合にのみ,分布パラメータの推定を行う。 我々は,PAC学習から,正・負のサンプルによるPAC学習まで,独立したツールを開発する。
  論文  参考訳（メタデータ） (2024-10-02T15:21:07Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。 SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• 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)
• Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes [23.94542304111204]
  勾配降下法と切断平面法の間に正のトレードオフを与えるアルゴリズムの第一級は、$epsilonleq 1/sqrt d$である。 規則$epsilon leq d-Omega(d)$では、$p=d$のアルゴリズムが情報理論の最適メモリ利用を実現し、勾配降下のオラクル-複雑度を改善する。
  論文  参考訳（メタデータ） (2023-06-16T17:00:51Z)
• 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)
• List-Decodable Covariance Estimation [1.9290392443571387]
  共分散推定アルゴリズムを初めて提案する。 この結果から,リスト復号化可能な線形回帰と部分空間復元のための初となるエンフェクサクタクティックアルゴリズムが提案された。
  論文  参考訳（メタデータ） (2022-06-22T09:38:06Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)
• Learning Polynomials of Few Relevant Dimensions [12.122488725065388]
  多項式回帰は学習と統計の基本的な原始である。 およそ$N = O_r,d(n log2(1/epsilon) (log n)d)$と$O_r,d(N n2)$である。
  論文  参考訳（メタデータ） (2020-04-28T18:00:18Z)

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

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