論文の概要: Cost-efficient Gaussian Tensor Network Embeddings for Tensor-structured
Inputs
- arxiv url: http://arxiv.org/abs/2205.13163v1
- Date: Thu, 26 May 2022 05:27:31 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-28 04:43:34.309275
- Title: Cost-efficient Gaussian Tensor Network Embeddings for Tensor-structured
Inputs
- Title（参考訳）: テンソル構造入力に対するコスト効率のよいガウステンソルネットワーク埋め込み
- Authors: Linjian Ma and Edgar Solomonik
- Abstract要約: 我々はネットワーク埋め込みを用いてテンソルネットワーク構造入力の次元的低減を行う。
このような埋め込みを用いて、入力データを効率的にスケッチするアルゴリズムを提供する。
列車のラウンドリングのための既存のアルゴリズムの最適性を示す。
- 参考スコア（独自算出の注目度）: 2.737640280995564
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This work discusses tensor network embeddings, which are random matrices
($S$) with tensor network structure. These embeddings have been used to perform
dimensionality reduction of tensor network structured inputs $x$ and accelerate
applications such as tensor decomposition and kernel regression. Existing works
have designed embeddings for inputs $x$ with specific structures, such that the
computational cost for calculating $Sx$ is efficient. We provide a systematic
way to design tensor network embeddings consisting of Gaussian random tensors,
such that for inputs with more general tensor network structures, both the
sketch size (row size of $S$) and the sketching computational cost are low.
We analyze general tensor network embeddings that can be reduced to a
sequence of sketching matrices. We provide a sufficient condition to quantify
the accuracy of such embeddings and derive sketching asymptotic cost lower
bounds using embeddings that satisfy this condition and have a sketch size
lower than any input dimension. We then provide an algorithm to efficiently
sketch input data using such embeddings. The sketch size of the embedding used
in the algorithm has a linear dependence on the number of sketching dimensions
of the input. Assuming tensor contractions are performed with classical dense
matrix multiplication algorithms, this algorithm achieves asymptotic cost
within a factor of $O(\sqrt{m})$ of our cost lower bound, where $m$ is the
sketch size. Further, when each tensor in the input has a dimension that needs
to be sketched, this algorithm yields the optimal sketching asymptotic cost. We
apply our sketching analysis to inexact tensor decomposition optimization
algorithms. We provide a sketching algorithm for CP decomposition that is
asymptotically faster than existing work in multiple regimes, and show
optimality of an existing algorithm for tensor train rounding.
- Abstract（参考訳）: 本研究ではテンソルネットワーク構造を持つランダム行列(S$)であるテンソルネットワーク埋め込みについて述べる。
これらの埋め込みはテンソルネットワーク構造入力の次元的還元を$x$で行い、テンソル分解やカーネル回帰のようなアプリケーションを加速するために使われてきた。
既存の研究は、特定の構造を持つ入力に対して$x$の埋め込みを設計しており、$Sx$を計算する計算コストは効率的である。
より一般的なテンソルネットワーク構造を持つ入力に対して、スケッチサイズ(ローサイズ:$S$)とスケッチ計算コストの両方が低いような、ガウスランダムテンソルからなるテンソルネットワーク埋め込みを体系的に設計する方法を提供する。
我々は、スケッチ行列の列に還元できる一般的なテンソルネットワーク埋め込みを解析する。
このような埋め込みの精度を定量化し、この条件を満たし、どの入力次元よりもスケッチサイズが小さい埋め込みを用いて、漸近的コスト低下境界を導出するのに十分な条件を提供する。
そして、そのような埋め込みを用いて入力データを効率的にスケッチするアルゴリズムを提供する。
アルゴリズムで使用される埋め込みのスケッチサイズは、入力のスケッチ次元の数に線形に依存する。
テンソルの縮約が古典的密度行列乗算アルゴリズムを用いて行われると仮定すると、このアルゴリズムは、$O(\sqrt{m})$のコストローバウンドで漸近コストを達成し、$m$はスケッチサイズである。
さらに、入力中の各テンソルがスケッチが必要な次元を持つ場合、このアルゴリズムは最適なスケッチの漸近コストを得る。
スケッチ解析を不正確なテンソル分解最適化アルゴリズムに適用する。
cp分解のためのスケッチアルゴリズムは,複数領域の既存処理よりも漸近的に高速であり,既存のテンソルトレインラウンドングアルゴリズムの最適性を示す。
関連論文リスト
- Adapting Newton's Method to Neural Networks through a Summary of
Higher-Order Derivatives [0.0]
関数 $boldsymboltheta$ に適用した勾配に基づく最適化法を考える。
このフレームワークは、勾配降下によるニューラルネットワークのトレーニングなど、多くの一般的なユースケースを含んでいる。
論文 参考訳（メタデータ） (2023-12-06T20:24:05Z) - 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) - Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。
我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。
RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
論文 参考訳（メタデータ） (2022-10-21T15:56:13Z) - Latent Matrices for Tensor Network Decomposition and to Tensor
Completion [8.301418317685906]
テンソルを小さく分解し,アルゴリズムの計算を高速化する新しい高階テンソル分解モデルを提案する。
LMTN-PAM, LMTN-SVD, LMTN-ARの3つの最適化アルゴリズムを開発し, テンソル補完タスクに適用した。
実験の結果, LMTN-SVDアルゴリズムはFCTN-PAMアルゴリズムの3～6倍高速であり, 1.8ポイントの精度低下しか得られなかった。
論文 参考訳（メタデータ） (2022-10-07T08:19:50Z) - 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) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Complex-to-Real Sketches for Tensor Products with Applications to the
Polynomial Kernel [15.535749953841274]
p$ベクトルの積のランダム化されたスケッチは、統計効率と計算加速度のトレードオフに従う。
本稿では、実乱射影を複素射影に置き換える、よく知られたスケッチの単純な複素対Real (CtR) 修正を提案する。
本手法は,文献の他のランダム化近似と比較して,精度と速度の面で最先端の性能を達成することを示す。
論文 参考訳（メタデータ） (2022-02-04T09:15:43Z) - Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via
GDPA Linearization [59.87663954467815]
アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。
本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。
実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
論文 参考訳（メタデータ） (2021-09-10T07:01:15Z) - Beyond Lazy Training for Over-parameterized Tensor Decomposition [69.4699995828506]
過度なパラメータ化対象の勾配勾配は遅延学習体制を超え、データ中の特定の低ランク構造を利用する可能性があることを示す。
以上の結果から,過パラメータ化対象の勾配勾配は遅延学習体制を超え,データ中の特定の低ランク構造を利用する可能性が示唆された。
論文 参考訳（メタデータ） (2020-10-22T00:32:12Z) - Streaming Coresets for Symmetric Tensor Factorization [9.181791777532608]
ストリーミング環境でテンソルを効率的に分解する方法を示す。
本稿では,オンラインフィルタリングとカーネル化という2つの新しいアルゴリズム手法を紹介する。
単一トピックモデリング学習におけるアルゴリズムの適用例を示す。
論文 参考訳（メタデータ） (2020-06-01T19:55:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。