論文の概要: Learning Polynomials of Few Relevant Dimensions
- arxiv url: http://arxiv.org/abs/2004.13748v1
- Date: Tue, 28 Apr 2020 18:00:18 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-08 22:41:58.648132
- Title: Learning Polynomials of Few Relevant Dimensions
- Title（参考訳）: 関連する次元の少ない多項式の学習
- Authors: Sitan Chen, Raghu Meka
- Abstract要約: 多項式回帰は学習と統計の基本的な原始である。
およそ$N = O_r,d(n log2(1/epsilon) (log n)d)$と$O_r,d(N n2)$である。
- 参考スコア（独自算出の注目度）: 12.122488725065388
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Polynomial regression is a basic primitive in learning and statistics. In its
most basic form the goal is to fit a degree $d$ polynomial to a response
variable $y$ in terms of an $n$-dimensional input vector $x$. This is extremely
well-studied with many applications and has sample and runtime complexity
$\Theta(n^d)$. Can one achieve better runtime if the intrinsic dimension of the
data is much smaller than the ambient dimension $n$? Concretely, we are given
samples $(x,y)$ where $y$ is a degree at most $d$ polynomial in an unknown
$r$-dimensional projection (the relevant dimensions) of $x$. This can be seen
both as a generalization of phase retrieval and as a special case of learning
multi-index models where the link function is an unknown low-degree polynomial.
Note that without distributional assumptions, this is at least as hard as junta
learning.
In this work we consider the important case where the covariates are
Gaussian. We give an algorithm that learns the polynomial within accuracy
$\epsilon$ with sample complexity that is roughly $N = O_{r,d}(n
\log^2(1/\epsilon) (\log n)^d)$ and runtime $O_{r,d}(N n^2)$. Prior to our
work, no such results were known even for the case of $r=1$. We introduce a new
filtered PCA approach to get a warm start for the true subspace and use
geodesic SGD to boost to arbitrary accuracy; our techniques may be of
independent interest, especially for problems dealing with subspace recovery or
analyzing SGD on manifolds.
- Abstract（参考訳）: 多項式回帰は学習と統計の基本的な原始である。
最も基本的な形式では、次数 $d$ 多項式を$n$-次元の入力ベクトル $x$ という観点で応答変数 $y$ に適合させることである。
これは多くのアプリケーションで非常によく研究されており、サンプルとランタイムの複雑さが$\Theta(n^d)$である。
もしデータの内在的な次元が環境次元$n$よりもずっと小さいなら、より良いランタイムを実現できますか?
具体的には、不明なr$-次元射影(関連する次元)において、$(x,y)$が最大$d$多項式の次数である場合のサンプル$(x,y)$が与えられる。
これは位相探索の一般化と、リンク関数が未知の低次多項式であるようなマルチインデックスモデルを学習する特別な場合の両方と見なすことができる。
分布的仮定がなければ、これは少なくともjunta学習と同じくらい難しいことに注意してください。
この研究では、共変項がガウス的である重要な場合を考える。
多項式を精度良く学習するアルゴリズムとして、$n = o_{r,d}(n \log^2(1/\epsilon) (\log n)^d)$ とランタイム $o_{r,d}(n n^2)$ がある。
我々の研究に先立ち、$r=1$の場合でさえそのような結果は知られていなかった。
我々は,真の部分空間を暖かく開始し,測地SGDを用いて任意の精度を向上する新しいPCA手法を提案し,特に部分空間の回復や多様体上のSGD解析の問題に対して,我々の技術は独立した関心を持つ可能性がある。
関連論文リスト
- 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) - Learning Hierarchical Polynomials with Three-Layer Neural Networks [56.71223169861528]
3層ニューラルネットワークを用いた標準ガウス分布における階層関数の学習問題について検討する。
次数$k$s$p$の大規模なサブクラスの場合、正方形損失における階層的勾配によるトレーニングを受けた3層ニューラルネットワークは、テストエラーを消すためにターゲット$h$を学習する。
この研究は、3層ニューラルネットワークが複雑な特徴を学習し、その結果、幅広い階層関数のクラスを学ぶ能力を示す。
論文 参考訳（メタデータ） (2023-11-23T02:19: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) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Private and polynomial time algorithms for learning Gaussians and beyond [13.947461378608525]
本稿では,$(varepsilon, delta)$differentially private (DP) 統計的推定を非私的推定に還元する枠組みを提案する。
我々は、(制限のない)ガウスの堅牢な学習のための$(varepsilon, delta)$-DPアルゴリズムを初めて提供する。
論文 参考訳（メタデータ） (2021-11-22T16:25:51Z) - 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) - Average-case Complexity of Teaching Convex Polytopes via Halfspace
Queries [55.28642461328172]
平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。
我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
論文 参考訳（メタデータ） (2020-06-25T19:59:24Z) - Learning sums of powers of low-degree polynomials in the non-degenerate
case [2.6109033135086777]
我々は、ある非退化条件が成立すれば、同じモデルに対する下界から算術回路モデルの学習アルゴリズムを与える。
本アルゴリズムは,同じモデルに対する下界から算術回路モデルの学習アルゴリズムを得るためのスキームに基づいている。
論文 参考訳（メタデータ） (2020-04-15T06:18:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。