論文の概要: Subquadratic Kronecker Regression with Applications to Tensor
Decomposition
- arxiv url: http://arxiv.org/abs/2209.04876v1
- Date: Sun, 11 Sep 2022 14:24:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-13 14:18:37.475130
- Title: Subquadratic Kronecker Regression with Applications to Tensor
Decomposition
- Title(参考訳): 準二次クロネッカー回帰とテンソル分解への応用
- Authors: Matthew Fahrbach, Thomas Fu, Mehrdad Ghadiri
- Abstract要約: 我々はKronecker回帰を$(varepsilon-N)$-approximationに解くための最初の準四進時間アルゴリズムを提案する。
本手法は, スコアサンプリングと反復法を組み合わせた手法である。
合成データと実世界の画像テンソル上でのKronecker回帰アルゴリズムの高速化と精度を示す。
- 参考スコア(独自算出の注目度): 4.391912559062643
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Kronecker regression is a highly-structured least squares problem
$\min_{\mathbf{x}} \lVert \mathbf{K}\mathbf{x} - \mathbf{b} \rVert_{2}^2$,
where the design matrix $\mathbf{K} = \mathbf{A}^{(1)} \otimes \cdots \otimes
\mathbf{A}^{(N)}$ is a Kronecker product of factor matrices. This regression
problem arises in each step of the widely-used alternating least squares (ALS)
algorithm for computing the Tucker decomposition of a tensor. We present the
first subquadratic-time algorithm for solving Kronecker regression to a
$(1+\varepsilon)$-approximation that avoids the exponential term
$O(\varepsilon^{-N})$ in the running time. Our techniques combine leverage
score sampling and iterative methods. By extending our approach to block-design
matrices where one block is a Kronecker product, we also achieve
subquadratic-time algorithms for (1) Kronecker ridge regression and (2)
updating the factor matrix of a Tucker decomposition in ALS, which is not a
pure Kronecker regression problem, thereby improving the running time of all
steps of Tucker ALS. We demonstrate the speed and accuracy of this Kronecker
regression algorithm on synthetic data and real-world image tensors.
- Abstract(参考訳): クロネッカー回帰 (kronecker regression) は、高度に構造化された最小二乗問題 $\min_{\mathbf{x}} \lvert \mathbf{k}\mathbf{x} - \mathbf{b} \rvert_{2}^2}\, ここで設計行列 $\mathbf{k} = \mathbf{a}^{(1)} \otimes \cdots \otimes \mathbf{a}^{(n)}$ は因子行列のクロネッカー積である。
この回帰問題は、テンソルのタッカー分解を計算するために広く使用される交代最小二乗アルゴリズム(ALS)の各ステップで生じる。
我々は、Kronecker回帰を1+\varepsilon)$-approximationに解くための最初の準四進時間アルゴリズムを、実行時の指数項$O(\varepsilon^{-N})$を避けるために提示する。
スコアサンプリングと反復的手法を併用した手法である。
1ブロックがKronecker積であるブロック設計行列にアプローチを拡張することにより、(1)Kroneckerのリッジ回帰と(2)純粋なKronecker回帰問題ではないALSにおけるTucker分解の係数行列の更新のためのサブクワッドラティック時間アルゴリズムを実現し、Tucker ALSの全ステップの実行時間を改善する。
本研究では,合成データと実世界画像テンソルを用いて,このクロネッカー回帰アルゴリズムの速度と精度を示す。
関連論文リスト
- Convergence of Alternating Gradient Descent for Matrix Factorization [5.439020425819001]
非対称行列分解対象に一定のステップサイズを施した交互勾配降下(AGD)について検討した。
階数-r$行列 $mathbfA in mathbbRm times n$, smoothness $C$ in the complexity $T$ to be a absolute constant。
論文 参考訳(メタデータ) (2023-05-11T16:07:47Z) - 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) - Private Isotonic Regression [54.32252900997422]
部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。
約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。
上記の境界は本質的に最良であることを示す。
論文 参考訳(メタデータ) (2022-10-27T05:08:07Z) - Dynamic Tensor Product Regression [18.904243654649118]
本稿では,1つの行列に対する更新を素早く伝達できる動的ツリーデータ構造を提案する。
また、私たちのデータ構造は、製品回帰の動的バージョンだけでなく、製品スプライン回帰の動的バージョンにも利用できます。
論文 参考訳(メタデータ) (2022-10-08T08:06:00Z) - 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) - On the well-spread property and its relation to linear regression [4.619541348328937]
頑健な線形回帰モデルにおけるパラメータベクトルの一貫した回復は情報理論上不可能であることを示す。
与えられた$n$-by-d$行列が、周囲の次元で観測回数が二次的である場合、適切に証明できることが示される。
論文 参考訳(メタデータ) (2022-06-16T11:17:44Z) - Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Sampling [5.740578698172382]
リッジレバレッジスコア (ridge leverage scores) と呼ばれるランダム化数値線形代数のタッカー分解とツールの利用について検討する。
近似リッジレバレッジスコアを用いて、任意のリッジ回帰問題に対してスケッチされたインスタンスを構築する方法を示す。
本研究では, 合成データと実世界のデータの両方に対して, 大規模かつ低ランクのタッカー分解に対する近似リッジ回帰アルゴリズムの有効性を示す。
論文 参考訳(メタデータ) (2021-07-22T13:32:47Z) - Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix
Factorization [49.090785356633695]
非対称な低ランク分解問題: [mathbbRm min d , mathbfU$ および MathV$ について検討する。
論文 参考訳(メタデータ) (2021-06-27T17:25:24Z) - Coordinate Methods for Matrix Games [41.821881312775496]
我々は,MathcalX max_yinmathY ytop A x$ の $min_x 形式の双線形サドル点問題を解くための主対座標法を開発した。
提案手法は,既存のサブ線形手法を,各項目の複雑性とサンプルの複雑さの観点から限界に推し進める。
論文 参考訳(メタデータ) (2020-09-17T17:55:03Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳(メタデータ) (2020-07-16T06:44:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。