論文の概要: Learning sums of powers of low-degree polynomials in the non-degenerate
case
- arxiv url: http://arxiv.org/abs/2004.06898v2
- Date: Tue, 16 Jun 2020 08:57:22 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-13 04:25:03.005958
- Title: Learning sums of powers of low-degree polynomials in the non-degenerate
case
- Title（参考訳）: 非退化の場合における低次多項式のパワーの学習和
- Authors: Ankit Garg, Neeraj Kayal, and Chandan Saha
- Abstract要約: 我々は、ある非退化条件が成立すれば、同じモデルに対する下界から算術回路モデルの学習アルゴリズムを与える。
本アルゴリズムは,同じモデルに対する下界から算術回路モデルの学習アルゴリズムを得るためのスキームに基づいている。
- 参考スコア（独自算出の注目度）: 2.6109033135086777
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We develop algorithms for writing a polynomial as sums of powers of low
degree polynomials. Consider an $n$-variate degree-$d$ polynomial $f$ which can
be written as $$f = c_1Q_1^{m} + \ldots + c_s Q_s^{m},$$ where each $c_i\in
\mathbb{F}^{\times}$, $Q_i$ is a homogeneous polynomial of degree $t$, and $t m
= d$. In this paper, we give a $\text{poly}((ns)^t)$-time learning algorithm
for finding the $Q_i$'s given (black-box access to) $f$, if the $Q_i's$ satisfy
certain non-degeneracy conditions and $n$ is larger than $d^2$. The set of
degenerate $Q_i$'s (i.e., inputs for which the algorithm does not work) form a
non-trivial variety and hence if the $Q_i$'s are chosen according to any
reasonable (full-dimensional) distribution, then they are non-degenerate with
high probability (if $s$ is not too large).
Our algorithm is based on a scheme for obtaining a learning algorithm for an
arithmetic circuit model from a lower bound for the same model, provided
certain non-degeneracy conditions hold. The scheme reduces the learning problem
to the problem of decomposing two vector spaces under the action of a set of
linear operators, where the spaces and the operators are derived from the input
circuit and the complexity measure used in a typical lower bound proof. The
non-degeneracy conditions are certain restrictions on how the spaces decompose.
- Abstract（参考訳）: 低次多項式のパワーの和として多項式を記述するアルゴリズムを開発した。
f = c_1Q_1^{m} + \ldots + c_s Q_s^{m},$$ ここで各$c_i\in \mathbb{F}^{\times}$, $Q_i$は次数$t$の斉次多項式で、$tm = d$と書くことができる。
本稿では、$q_i$が特定の非退化条件を満たし、$n$が$d^2$より大きい場合、$f$を求めるための$\text{poly}((ns)^t)$-time learningアルゴリズムを与える。
退化した$q_i$'s(すなわちアルゴリズムが動作しない入力)の集合は非自明な多様体を形成し、従って$q_i$'s が任意の妥当な(フル次元)分布に従って選択された場合、高い確率で非退化する($s$ が大きすぎる場合)。
本アルゴリズムは,特定の非退化条件が保たれれば,同一モデルの下限から算術回路モデルの学習アルゴリズムを得るためのスキームに基づいている。
このスキームは、2つのベクトル空間を線型作用素の集合の作用の下で分解する問題に学習問題を還元し、空間と作用素は入力回路から導出され、典型的な下限証明で使われる複雑性測度である。
非退化条件は空間の分解に関する一定の制限である。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth [8.66267734067296]
制限しきい値関数を演算する境界を持つ定数深さ回路のクラスについて検討する。
十分大きな$mathsfbPTFC0[k]$の場合、$mathsfbPTFC0[k]は$mathsfTC0[k]を含む。
論文 参考訳（メタデータ） (2024-08-29T09:40:55Z) - 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) - 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) - Pseudo Polynomial-Time Top-k Algorithms for d-DNNF Circuits [0.0]
我々は,最大値w.r.$$$の内,$C$のモデルを計算するアルゴリズムを提案する。
また、d-DNNF回路に$C$を変換する擬似時間アルゴリズムを、上位の$k$に値を持つ$C$のモデルによって正確に満たされる。
論文 参考訳（メタデータ） (2022-02-11T23:53:43Z) - The Fine-Grained Hardness of Sparse Linear Regression [12.83354999540079]
この問題に対して、より優れたブルートフォースアルゴリズムは存在しないことを示す。
また,予測誤差が測定された場合,より優れたブラトフォースアルゴリズムが不可能であることを示す。
論文 参考訳（メタデータ） (2021-06-06T14:19: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) - 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) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。