論文の概要: Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials
- arxiv url: http://arxiv.org/abs/2211.05274v1
- Date: Thu, 10 Nov 2022 00:40:37 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-11 14:47:22.361241
- Title: Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials
- Title（参考訳）: 低次多項式に対するテンソル分解の平均ケース複雑性
- Authors: Alexander S. Wein
- Abstract要約: 多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
- 参考スコア（独自算出の注目度）: 93.59919600451487
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Suppose we are given an $n$-dimensional order-3 symmetric tensor $T \in
(\mathbb{R}^n)^{\otimes 3}$ that is the sum of $r$ random rank-1 terms. The
problem of recovering the rank-1 components is possible in principle when $r
\lesssim n^2$ but polynomial-time algorithms are only known in the regime $r
\ll n^{3/2}$. Similar "statistical-computational gaps" occur in many
high-dimensional inference tasks, and in recent years there has been a flurry
of work on explaining the apparent computational hardness in these problems by
proving lower bounds against restricted (yet powerful) models of computation
such as statistical queries (SQ), sum-of-squares (SoS), and low-degree
polynomials (LDP). However, no such prior work exists for tensor decomposition,
largely because its hardness does not appear to be explained by a "planted
versus null" testing problem.
We consider a model for random order-3 tensor decomposition where one
component is slightly larger in norm than the rest (to break symmetry), and the
components are drawn uniformly from the hypercube. We resolve the computational
complexity in the LDP model: $O(\log n)$-degree polynomial functions of the
tensor entries can accurately estimate the largest component when $r \ll
n^{3/2}$ but fail to do so when $r \gg n^{3/2}$. This provides rigorous
evidence suggesting that the best known algorithms for tensor decomposition
cannot be improved, at least by known approaches. A natural extension of the
result holds for tensors of any fixed order $k \ge 3$, in which case the LDP
threshold is $r \sim n^{k/2}$.
- Abstract（参考訳）: n$-dimensional order-3 対称テンソル $t \in (\mathbb{r}^n)^{\otimes 3} が与えられ、これは $r$ ランダムランク-1 項の和であるとする。
ランク-1成分を回収する問題は、r \lesssim n^2$ でも多項式時間アルゴリズムは、r \ll n^{3/2}$でしか知られていない。
同様の「統計計算ギャップ」は、多くの高次元推論タスクで発生し、近年は、統計クエリ(SQ)、総和(SoS)、低次多項式(LDP)といった計算の制限された(より強力な)モデルに対する下界を証明し、これらの問題における明らかな計算硬さを説明する研究が盛んに行われている。
しかしながら、テンソル分解の先行研究は存在せず、その硬さは「種対ヌル」テスト問題によって説明されないことが大きな理由である。
1つの成分が他の成分よりもわずかに大きい(対称性を破る)ランダムオーダー3テンソル分解のモデルを考え、その成分はハイパーキューブから一様に描画される。
テンソル成分の$O(\log n)$-次多項式関数は、$r \ll n^{3/2}$のとき最も大きい成分を正確に推定できるが、$r \gg n^{3/2}$のとき失敗する。
これは、テンソル分解の最もよく知られたアルゴリズムは、少なくとも既知のアプローチによって改善できないことを示す厳密な証拠を与える。
結果の自然な拡張は任意の固定順序 $k \ge 3$ のテンソルに対して成り立ち、この場合 LDP 閾値は $r \sim n^{k/2}$ となる。
関連論文リスト
- 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) - Identification of Mixtures of Discrete Product Distributions in
Near-Optimal Sample and Time Complexity [6.812247730094931]
任意の$ngeq 2k-1$に対して、サンプルの複雑さとランタイムの複雑さをどうやって達成するかを示す(1/zeta)O(k)$。
また、既知の$eOmega(k)$の下位境界を拡張して、より広い範囲の$zeta$と一致させる。
論文 参考訳（メタデータ） (2023-09-25T09:50:15Z) - 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-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor
Decompositions [51.19236668224547]
テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。
テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。
さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
論文 参考訳（メタデータ） (2022-07-15T11:55:09Z) - 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) - The Complexity of Sparse Tensor PCA [1.90365714903665]
1leq leq k$の場合、我々のアルゴリズムは信号対雑音比$lambda geq tildemathcalO (sqrtt cdot (k/t)p/2)$のスパースベクトルを時間内に回収する。
PCAの制限されたケースでさえ、既知のアルゴリズムは、$lambda geq tildemathcalO(k cdot r)のスパースベクトルのみを復元する一方、我々のアルゴリズムは$lambda geを必要とする。
論文 参考訳（メタデータ） (2021-06-11T10:57:00Z) - On $O( \max \{n_1, n_2 \}\log ( \max \{ n_1, n_2 \} n_3) )$ Sample
Entries for $n_1 \times n_2 \times n_3$ Tensor Completion via Unitary
Transformation [20.854908850239035]
本稿では,$n_3$低ランク$n_3$低ランク$n_3$マトリックススライスの非一貫性条件について検討する。
このような低ランクテンソルは高い確率で正確に復元できることを示す。
論文 参考訳（メタデータ） (2020-12-16T08:03:48Z) - Exact nuclear norm, completion and decomposition for random overcomplete
tensors via degree-4 SOS [0.7233897166339269]
次数4$SOSにインスパイアされた単純な半定値プログラムは、ランダムな非対称成分を持つテンソル上のテンソル核ノルム、テンソル分解、テンソル完備化問題を正確に解くことができることを示す。
これらの半定値プログラムは、$(ntimes ntimes n)$-tensor $mathcalT$と$mleq n3/2/polylog(n)$ランダム非対称成分の核ノルムと成分を正確に見つけることができることを示す。
論文 参考訳（メタデータ） (2020-11-18T17:27:36Z) - Beyond Lazy Training for Over-parameterized Tensor Decomposition [69.4699995828506]
過度なパラメータ化対象の勾配勾配は遅延学習体制を超え、データ中の特定の低ランク構造を利用する可能性があることを示す。
以上の結果から,過パラメータ化対象の勾配勾配は遅延学習体制を超え,データ中の特定の低ランク構造を利用する可能性が示唆された。
論文 参考訳（メタデータ） (2020-10-22T00:32:12Z) - Statistical Query Lower Bounds for Tensor PCA [10.701091387118023]
Richard と Montanari が導入した PCA 問題では、$n$サンプル $mathbbEmathbfT_1:n$ of i.d. Perkins Gaussian tensors of order $k$ からなるデータセットが与えられ、$mathbbEmathbfT_1:n$ はランク 1 である。
目標は$mathbbE mathbfT_1$を見積もることである。
最適なサンプルの複雑さを鋭く分析する。
論文 参考訳（メタデータ） (2020-08-10T13:14:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。