論文の概要: 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の全ステップの実行時間を改善する。
本研究では,合成データと実世界画像テンソルを用いて,このクロネッカー回帰アルゴリズムの速度と精度を示す。
関連論文リスト
- Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。
具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
論文 参考訳（メタデータ） (2024-08-21T01:39:42Z) - Regression for matrix-valued data via Kronecker products factorization [0.5156484100374059]
我々は、パラメータ $beta_1k サブセット Rep times q_1$ および $beta_2k サブセット Rep times q$ を推定するための推定アルゴリズム KRO-PRO-FAC を提案する。
シミュレーションおよび実データに関する数値的研究は,提案手法が既存の手法と比較して,推定誤差と予測精度の両方において競合的であることを示している。
論文 参考訳（メタデータ） (2024-04-30T02:44:41Z) - How to Inverting the Leverage Score Distribution? [16.744561210470632]
ツールとして広く利用されているレバレッジスコアにもかかわらず、本論文では、新しい問題、すなわち反転レバレッジスコアについて検討する。
我々は、ニュートン法における大域収束率を確保するために反復縮小と帰納仮説を用いる。
この統計レバレッジの反転に関する重要な研究は、解釈、データリカバリ、セキュリティにおける多くの新しい応用を開放する。
論文 参考訳（メタデータ） (2024-04-21T21:36:42Z) - 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。