論文の概要: Dynamic Tensor Product Regression
- arxiv url: http://arxiv.org/abs/2210.03961v1
- Date: Sat, 8 Oct 2022 08:06:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-11 19:24:42.923993
- Title: Dynamic Tensor Product Regression
- Title(参考訳): 動的テンソル製品回帰
- Authors: Aravind Reddy, Zhao Song, Lichen Zhang
- Abstract要約: 本稿では,1つの行列に対する更新を素早く伝達できる動的ツリーデータ構造を提案する。
また、私たちのデータ構造は、製品回帰の動的バージョンだけでなく、製品スプライン回帰の動的バージョンにも利用できます。
- 参考スコア(独自算出の注目度): 18.904243654649118
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: In this work, we initiate the study of \emph{Dynamic Tensor Product
Regression}. One has matrices $A_1\in \mathbb{R}^{n_1\times d_1},\ldots,A_q\in
\mathbb{R}^{n_q\times d_q}$ and a label vector $b\in \mathbb{R}^{n_1\ldots
n_q}$, and the goal is to solve the regression problem with the design matrix
$A$ being the tensor product of the matrices $A_1, A_2, \dots, A_q$ i.e.
$\min_{x\in \mathbb{R}^{d_1\ldots d_q}}~\|(A_1\otimes \ldots\otimes
A_q)x-b\|_2$. At each time step, one matrix $A_i$ receives a sparse change, and
the goal is to maintain a sketch of the tensor product $A_1\otimes\ldots
\otimes A_q$ so that the regression solution can be updated quickly.
Recomputing the solution from scratch for each round is very slow and so it is
important to develop algorithms which can quickly update the solution with the
new design matrix. Our main result is a dynamic tree data structure where any
update to a single matrix can be propagated quickly throughout the tree. We
show that our data structure can be used to solve dynamic versions of not only
Tensor Product Regression, but also Tensor Product Spline regression (which is
a generalization of ridge regression) and for maintaining Low Rank
Approximations for the tensor product.
- Abstract(参考訳): 本稿では,emph{Dynamic Tensor Product Regression}の研究を開始する。
1つは行列 $a_1\in \mathbb{r}^{n_1\times d_1},\ldots,a_q\in \mathbb{r}^{n_q\times d_q}$ とラベルベクトル $b\in \mathbb{r}^{n_1\ldots n_q}$ を持ち、目的は行列 $a$ を行列 $a_1, a_2, \dots, a_q$ のテンソル積とする回帰問題を解くことである。
各時間ステップで、1つの行列 $a_i$ がスパース変化を受け取り、目標はテンソル積 $a_1\otimes\ldots \otimes a_q$ のスケッチを維持することで、回帰解を迅速に更新できるようにすることである。
ラウンド毎にソリューションをスクラッチから再計算するのは非常に遅いため、新しいデザインマトリックスでソリューションを迅速に更新できるアルゴリズムを開発することが重要である。
我々の主な成果は、動的ツリーデータ構造であり、単一のマトリックスへの更新は、ツリー全体を通して素早く伝播できる。
我々のデータ構造はテンソル積回帰だけでなく、テンソル積スプライン回帰(リッジ回帰の一般化)の動的バージョンを解き、テンソル積の低ランク近似を維持するためにも利用できることを示す。
関連論文リスト
- In-Context Learning for Attention Scheme: from Single Softmax Regression
to Multiple Softmax Regression via a Tensor Trick [15.090593955414137]
本研究では,本研究における注意関係回帰のための2つの定式化に基づく文脈内学習について考察する。
我々の回帰問題は、ソフトマックス関連回帰に関する以前の研究と類似している。
論文 参考訳(メタデータ) (2023-07-05T16:41:01Z) - Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic
Regression [74.28017932704704]
我々は,従来の難解なスケッチとターンタイルストリーミングの結果を$ell_1$とロジスティック回帰で改善する。
また、入力空間の間隔で1+varepsilon$近似を出力するトレードオフも行います。
我々のスケッチは、データ依存正規化器が個々のロジスティック損失の分散に対応するような、正規化されたロジスティック回帰を近似するために拡張することができる。
論文 参考訳(メタデータ) (2023-03-31T18:12:33Z) - A General Algorithm for Solving Rank-one Matrix Sensing [15.543065204102714]
マトリックスセンシングの目標は、一連の測定に基づいて、mathbbRn×n$の行列$A_starを復元することである。
本稿では、このランク-$kの仮定を緩和し、より一般的な行列センシング問題を解く。
論文 参考訳(メタデータ) (2023-03-22T04:07:26Z) - A Nearly-Optimal Bound for Fast Regression with $\ell_\infty$ Guarantee [16.409210914237086]
行列 $Ain mathbbRntimes d$ とテンソル $bin mathbbRn$ が与えられたとき、 $ell_infty$ の回帰問題を考える。
このような$ell_infty$レグレッションの保証を得るためには、濃密なスケッチ行列を使わなければならない。
我々はまた、OCE(Oblivious Coordinate-wise Embedding)特性を利用した $ell_infty$ guarantee regression のための新しい分析フレームワークを開発した。
論文 参考訳(メタデータ) (2023-02-01T05:22:40Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳(メタデータ) (2022-09-30T04:15:44Z) - Subquadratic Kronecker Regression with Applications to Tensor
Decomposition [4.391912559062643]
我々はKronecker回帰を$(varepsilon-N)$-approximationに解くための最初の準四進時間アルゴリズムを提案する。
本手法は, スコアサンプリングと反復法を組み合わせた手法である。
合成データと実世界の画像テンソル上でのKronecker回帰アルゴリズムの高速化と精度を示す。
論文 参考訳(メタデータ) (2022-09-11T14:24:19Z) - On the well-spread property and its relation to linear regression [4.619541348328937]
頑健な線形回帰モデルにおけるパラメータベクトルの一貫した回復は情報理論上不可能であることを示す。
与えられた$n$-by-d$行列が、周囲の次元で観測回数が二次的である場合、適切に証明できることが示される。
論文 参考訳(メタデータ) (2022-06-16T11:17:44Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳(メタデータ) (2022-04-13T22:18:47Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳(メタデータ) (2021-11-09T00:20:01Z) - Statistical Query Lower Bounds for List-Decodable Linear Regression [55.06171096484622]
本稿では,リスト復号化可能な線形回帰問題について考察する。
我々の主な成果は、この問題に対して$dmathrmpoly (1/alpha)$の統計的クエリ(SQ)の低いバウンダリである。
論文 参考訳(メタデータ) (2021-06-17T17:45:21Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳(メタデータ) (2021-05-17T16:40:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。