論文の概要: Sketching Algorithms and Lower Bounds for Ridge Regression
- arxiv url: http://arxiv.org/abs/2204.06653v1
- Date: Wed, 13 Apr 2022 22:18:47 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-15 14:34:49.715893
- Title: Sketching Algorithms and Lower Bounds for Ridge Regression
- Title（参考訳）: リッジ回帰のためのスケッチアルゴリズムと下限
- Authors: Praneeth Kacham and David P. Woodruff
- Abstract要約: リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
- 参考スコア（独自算出の注目度）: 65.0720777731368
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give a sketching-based iterative algorithm that computes $1+\varepsilon$
approximate solutions for the ridge regression problem $\min_x \|{Ax-b}\|_2^2
+\lambda\|{x}\|_2^2$ where $A \in \mathbb{R}^{n \times d}$ with $d \ge n$. Our
algorithm, for a constant number of iterations (requiring a constant number of
passes over the input), improves upon earlier work of Chowdhury et al., by
requiring that the sketching matrix only has a weaker Approximate Matrix
Multiplication (AMM) guarantee that depends on $\epsilon$, along with a
constant subspace embedding guarantee. The earlier work instead requires that
the sketching matrix have a subspace embedding guarantee that depends on
$\epsilon$. For example, to produce a $1+\varepsilon$ approximate solution in
$1$ iteration, which requires $2$ passes over the input, our algorithm requires
the OSNAP embedding to have $m= O(n\sigma^2/\lambda\varepsilon)$ rows with a
sparsity parameter $s = O(\log(n))$, whereas the earlier algorithm of Chowdhury
et al., with the same number of rows of OSNAP requires a sparsity $s =
O(\sqrt{\sigma^2/\lambda\varepsilon} \cdot \log(n))$, where $\sigma =
\|{A}\|_2$ is the spectral norm of the matrix $A$. We also show that this
algorithm can be used to give faster algorithms for kernel ridge regression.
Finally, we show that the sketch size required for our algorithm is essentially
optimal for a natural framework of algorithms for ridge regression by proving
lower bounds on oblivious sketching matrices for AMM. The sketch size lower
bounds for AMM may be of independent interest.
- Abstract（参考訳）: リッジ回帰問題に対して 1+\varepsilon$ の近似解を計算するスケッチベースの反復アルゴリズムを与える。 $\min_x \|{ax-b}\|_2^2 +\lambda\|{x}\|_2^2$ ここで$a \in \mathbb{r}^{n \times d}$ は $d \ge n$ である。
我々のアルゴリズムは、一定回数の反復(入力に一定回数のパスを要求する)に対して、Chowdhuryらの初期の作業を改善するため、スケッチ行列は、$\epsilon$に依存するより弱い近似行列乗算(AMM)保証と、一定の部分空間の埋め込み保証を必要とする。
以前の作業では、スケッチマトリックスが$\epsilon$に依存する部分空間埋め込み保証を持つ必要がある。
例えば、$$$$の反復で1+\varepsilon$の近似解を生成するには、入力に$$$のパスを必要とするが、このアルゴリズムでは、$m= o(n\sigma^2/\lambda\varepsilon)$ とスパルシティパラメータ $s = o(\log(n))$ を持つ osnap の埋め込みを必要とするが、chowdhury の以前のアルゴリズムでは、osnap の行数が同じ場合、$s = o(\sqrt{\sigma^2/\lambda\varepsilon} \cdot \log(n)$ である。
また,このアルゴリズムは,カーネルリッジ回帰の高速化にも利用できることを示した。
最後に,本アルゴリズムに必要なスケッチサイズは,ammの斜めスケッチ行列の下限を証明し,リッジ回帰アルゴリズムの自然な枠組みに本質的に最適であることを示す。
ammのスケッチサイズの下限は独立した興味を持つかもしれない。
関連論文リスト
- 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) - Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning [10.690769339903941]
我々は、$Ax = b$という形式の線形系を解くための、新しい条件付き反復法のクラスを示す。
提案手法は,低ランクなNystr"om近似をスパースランダムスケッチを用いて$A$に構築することに基づいている。
我々は、我々の手法の収束が自然平均条件数$A$に依存することを証明し、Nystr"om近似のランクとして改善する。
論文 参考訳（メタデータ） (2024-05-09T15:53:43Z) - Optimal Embedding Dimension for Sparse Subspace Embeddings [4.042707434058959]
ランダム$mtimes n$ matrix $S$は、忘れられない部分空間埋め込み(OSE)である。
mtimes n$ random matrix $S$ with $mgeq (1+theta)d$ is an oblivious subspace embedding with $epsilon = O_theta(1)$。
これを使用すれば、現在の行列乗算時間よりも早く適用できる$O(d)$埋め込み次元で、最初の難解な部分空間埋め込みを構築することができる。
論文 参考訳（メタデータ） (2023-11-17T18:01:58Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - 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) - Private Isotonic Regression [54.32252900997422]
部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。
約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。
上記の境界は本質的に最良であることを示す。
論文 参考訳（メタデータ） (2022-10-27T05:08:07Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。