論文の概要: Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits

• arxiv url: http://arxiv.org/abs/2105.01751v1
• Date: Tue, 4 May 2021 20:45:07 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-06 23:40:41.403147
• Title: Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits
• Title（参考訳）: 低域テンソルと深さ3多重線形回路の再構成アルゴリズム
• Authors: Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
• Abstract要約: 深さ$3$の算術回路のクラスに対して、新しい効率的なブラックボックス再構成アルゴリズムを提供する。 我々のアルゴリズムは、すべてのフィールド特性 0 以上の大きな特性に作用する。
• 参考スコア（独自算出の注目度）: 4.129484350382891
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give new and efficient black-box reconstruction algorithms for some classes of depth-$3$ arithmetic circuits. As a consequence, we obtain the first efficient algorithm for computing the tensor rank and for finding the optimal tensor decomposition as a sum of rank-one tensors when then input is a constant-rank tensor. More specifically, we provide efficient learning algorithms that run in randomized polynomial time over general fields and in deterministic polynomial time over the reals and the complex numbers for the following classes: (1) Set-multilinear depth-$3$ circuits of constant top fan-in $\Sigma\Pi\Sigma\{\sqcup_j X_j\}(k)$ circuits). As a consequence of our algorithm, we obtain the first polynomial time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank tensors. This result holds for $d$ dimensional tensors for any $d$, but is interesting even for $d=3$. (2) Sums of powers of constantly many linear forms ($\Sigma\wedge\Sigma$ circuits). As a consequence we obtain the first polynomial-time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank symmetric tensors. (3) Multilinear depth-3 circuits of constant top fan-in (multilinear $\Sigma\Pi\Sigma(k)$ circuits). Our algorithm works over all fields of characteristic 0 or large enough characteristic. Prior to our work the only efficient algorithms known were over polynomially-sized finite fields (see. Karnin-Shpilka 09'). Prior to our work, the only polynomial-time or even subexponential-time algorithms known (deterministic or randomized) for subclasses of $\Sigma\Pi\Sigma(k)$ circuits that also work over large/infinite fields were for the setting when the top fan-in $k$ is at most $2$ (see Sinha 16' and Sinha 20').
• Abstract（参考訳）: 深さ3$の算術回路のクラスに対して,新しい効率的なブラックボックス再構成アルゴリズムを提案する。 その結果、入力が定数ランクテンソルである場合に、テンソルランクを計算し、最適テンソル分解をランク1テンソルの和として求めるための最初の効率的なアルゴリズムが得られる。 より具体的には、一般の場上でランダム化された多項式時間と実数および以下のクラスの複素数に対して決定論的多項式時間で実行される効率的な学習アルゴリズムを提供する: (1) 定数トップファンイン$\Sigma\Pi\Sigma\{\sqcup_j X_j\}(k)$回路のセット・マルチ線形深さ-$3$。 その結果、テンソル階数計算と定数ランクテンソルの最適テンソル分解のための第1多項式時間アルゴリズムが得られた。 この結果は任意の$d$に対して$d$ 次元テンソルを持つが、$d=3$でも興味深い。 2) 常に多くの線形形式(Sigma\wedge\Sigma$ circuits)のパワーの和。 その結果、テンソル階数計算と定数ランク対称テンソルの最適テンソル分解のための第1多項式時間アルゴリズムが得られた。 (3) 定数トップファンインのマルチリニア深さ3回路(マルチリニア$\Sigma\Pi\Sigma(k)$回路)。 我々のアルゴリズムは、標数 0 または十分な特性を持つすべてのフィールドに作用する。 我々の研究に先立ち、既知の効率的なアルゴリズムは多項式サイズの有限体上のみであった(参照)。 Karnin-Shpilka 09')。 我々の研究に先立ち、最大ファンイン$k$が最大$$(シンハ16'とシンハ20'参照)のとき、大/無限フィールド上でも動作する$\sigma\pi\sigma(k)$のサブクラスの多項式時間または副指数時間アルゴリズム(決定的またはランダム化)が知られている。

関連論文リスト

• 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)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。 1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。 テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
  論文  参考訳（メタデータ） (2022-11-10T00:40:37Z)
• 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)
• Learning Polynomial Transformations [41.30404402331856]
  ガウスの高次元二次変換を学習する問題を考察する。 我々の結果はガウス分布だけでなく、任意の不変な入力分布にまで拡張される。 また、テンソル環分解の証明可能な保証を持つ最初の分解時間アルゴリズムを与える。
  論文  参考訳（メタデータ） (2022-04-08T17:59:31Z)
• A Robust Spectral Algorithm for Overcomplete Tensor Decomposition [10.742675209112623]
  オーバーコンプリートオーダー4テンソルを分解するスペクトルアルゴリズムを提案する。 我々のアルゴリズムは、有界スペクトルノルムの逆摂動に対して頑健である。 本アルゴリズムは半定値プログラミングを回避し,一連の線形代数演算として実装することができる。
  論文  参考訳（メタデータ） (2022-03-05T17:25:37Z)
• Fast algorithm for overcomplete order-3 tensor decomposition [7.638467133689933]
  我々は、O(d3/2/polylog(d))までのランクRd上のランダムな3階テンソルを分解する最初の高速スペクトルアルゴリズムを開発した。 我々のアルゴリズムは、現在の行列乗算時間の下で全成分を時間O(d6.05)で復元することができる。
  論文  参考訳（メタデータ） (2022-02-14T00:31:34Z)
• 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)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Streaming Coresets for Symmetric Tensor Factorization [9.181791777532608]
  ストリーミング環境でテンソルを効率的に分解する方法を示す。 本稿では,オンラインフィルタリングとカーネル化という2つの新しいアルゴリズム手法を紹介する。 単一トピックモデリング学習におけるアルゴリズムの適用例を示す。
  論文  参考訳（メタデータ） (2020-06-01T19:55:34Z)

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

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