論文の概要: 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$ のスケッチを維持することで、回帰解を迅速に更新できるようにすることである。
ラウンド毎にソリューションをスクラッチから再計算するのは非常に遅いため、新しいデザインマトリックスでソリューションを迅速に更新できるアルゴリズムを開発することが重要である。
我々の主な成果は、動的ツリーデータ構造であり、単一のマトリックスへの更新は、ツリー全体を通して素早く伝播できる。
我々のデータ構造はテンソル積回帰だけでなく、テンソル積スプライン回帰(リッジ回帰の一般化)の動的バージョンを解き、テンソル積の低ランク近似を維持するためにも利用できることを示す。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Turnstile $\ell_p$ leverage score sampling with applications [56.403488578703865]
我々は,行列$AinmathbbRntimes d$の行をサンプリングする新しいアルゴリズムを開発した。
我々のアルゴリズムはサンプル行インデックスのセットを返すだけでなく、わずかに乱れた行を $tildea_i approx a_i$ で返却し、サンプリング確率を $varepsilon$ の相対誤差に近似する。
ロジスティック回帰のために、我々のフレームワークは$を達成した最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-06-01T07:33:41Z) - How to Inverting the Leverage Score Distribution? [16.744561210470632]
ツールとして広く利用されているレバレッジスコアにもかかわらず、本論文では、新しい問題、すなわち反転レバレッジスコアについて検討する。
我々は、ニュートン法における大域収束率を確保するために反復縮小と帰納仮説を用いる。
この統計レバレッジの反転に関する重要な研究は、解釈、データリカバリ、セキュリティにおける多くの新しい応用を開放する。
論文 参考訳（メタデータ） (2024-04-21T21:36:42Z) - Solving Attention Kernel Regression Problem via Pre-conditioner [9.131385887605935]
我々は2種類の回帰問題に対するアルゴリズムを設計する:$min_xin mathbbRd|(Atop A)jx-b|$ for any positive integer $j$。
2番目のプロキシは、$exp(AAtop)$で表され、回帰$min_xin mathbbRn|exp(AAtop)xb |$で表されるグラム行列に指数的にエントリワイドを適用する。
論文 参考訳（メタデータ） (2023-08-28T04:37:38Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。