論文の概要: Have ASkotch: Fast Methods for Large-scale, Memory-constrained Kernel Ridge Regression
- arxiv url: http://arxiv.org/abs/2407.10070v1
- Date: Sun, 14 Jul 2024 04:11:10 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-16 19:38:33.745284
- Title: Have ASkotch: Fast Methods for Large-scale, Memory-constrained Kernel Ridge Regression
- Title（参考訳）: Have ASkotch: 大規模でメモリ制限のあるカーネルリッジ回帰のための高速メソッド
- Authors: Pratik Rathore, Zachary Frangella, Madeleine Udell,
- Abstract要約: KRRソルバを大規模データセットにスケールすることは困難である。
我々は, KRR の反復解法における記憶と繰り返しの複雑さを低減するために ASkotch を提案する。
我々の研究は、幅広い分野にわたるKRRの非想像的応用の可能性を開く。
- 参考スコア（独自算出の注目度）: 18.055120576191204
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Kernel ridge regression (KRR) is a fundamental computational tool, appearing in problems that range from computational chemistry to health analytics, with a particular interest due to its starring role in Gaussian process regression. However, it is challenging to scale KRR solvers to large datasets: with $n$ training points, a direct solver (i.e., Cholesky decomposition) uses $O(n^2)$ storage and $O(n^3)$ flops. Iterative methods for KRR, such as preconditioned conjugate gradient (PCG), avoid the cubic scaling of direct solvers and often use low-rank preconditioners; a rank $r$ preconditioner uses $O(rn)$ storage and each iteration requires $O(n^2)$ flops. To reduce the storage and iteration complexity of iterative solvers for KRR, we propose ASkotch ($\textbf{A}$ccelerated $\textbf{s}$calable $\textbf{k}$ernel $\textbf{o}$p$\textbf{t}$imization using block $\textbf{c}$oordinate descent with $\textbf{H}$essian preconditioning). For a given block size $|b| << n$, each iteration of ASkotch uses $O(r|b| + n)$ storage and $O(n|b|)$ flops, so ASkotch scales better than Cholesky decomposition and PCG. We prove that ASkotch obtains linear convergence to the optimum, with the convergence rate depending on the square roots of the $\textit{preconditioned}$ block condition numbers. Furthermore, we solve KRR problems that were considered to be impossibly large while using limited computational resources: we show that ASkotch outperforms PCG methods with respect to generalization error on large-scale KRR (up to $n = 10^8$) and KRR classification tasks (up to $n = 10^7$) while running each of our experiments on $\textit{a single 12 GB Titan V GPU}$. Our work opens up the possibility of as-yet-unimagined applications of KRR across a wide range of disciplines.
- Abstract（参考訳）: カーネルリッジ回帰(カーネルリッジ回帰、英: Kernel ridge regression、KRR)は、計算化学から健康分析まで幅広い問題に現れ、ガウス過程の回帰において特に重要な役割を担っている。
しかし、KRRソルバを大規模なデータセットにスケールすることは困難である:$n$トレーニングポイント、直接ソルバ(チョースキー分解)は$O(n^2)$ストレージと$O(n^3)$フロップを使用する。
事前条件付き共役勾配 (PCG) のような KRR の反復的手法では、直接解法器の立方体スケーリングを回避し、しばしば低階プリコンディショナーを使用する。
KRRの反復解のストレージとイテレーションの複雑さを軽減するため、ASkotch ($\textbf{A}$ccelerated $\textbf{s}$calable $\textbf{k}$ernel $\textbf{o}$p$\textbf{t}$imization using block $\textbf{c}$oordinate descend with $\textbf{H}$essian preconditioning。
与えられたブロックサイズが $|b| <<n$ の場合、ASkotch の各反復は $O(r|b| + n)$ ストレージと $O(n|b|)$ flops を使用する。
Askotch は、$\textit{preconditioned}$ block condition number の平方根に依存する収束率で、最適に線形収束することを示した。
さらに,計算資源が限られている場合のKRR問題に対して,ASkotchは大規模KRR(最大$n = 10^8$)およびKRR分類タスク(最大$n = 10^7$)の一般化誤差に対してPCG法より優れており,実験のそれぞれが$\textit{a single 12 GB Titan V GPU}$で実行されていることを示す。
我々の研究は、幅広い分野にわたるKRRの非想像的応用の可能性を開く。
関連論文リスト
- Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation [67.8414514524356]
本稿では,MNL関数近似を用いたMDPの新しいクラスについて検討し,状態空間上の確率分布の正当性を保証する。
非線型関数の導入は、計算効率と統計効率の両方において大きな課題を提起する。
我々は,$mathcalO(1)$$コストで同じ後悔を実現するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-27T11:31:54Z) - Optimal Rates of Kernel Ridge Regression under Source Condition in Large
Dimensions [15.988264513040903]
そこで,カーネルリッジ回帰 (KRR) の大規模挙動について検討し,サンプルサイズ$n asymp dgamma$ for some $gamma > 0$について検討した。
以上の結果から,ガンマ$で変動する速度曲線は周期的台地挙動と多重降下挙動を示すことが明らかとなった。
論文 参考訳（メタデータ） (2024-01-02T16:14:35Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - On the Optimality of Misspecified Kernel Ridge Regression [13.995944403996566]
我々は、$mathcalH$がソボレフ RKHS であるとき、KRR が任意の$sin (0,1)$に対して最小値であることを示す。
論文 参考訳（メタデータ） (2023-05-12T04:12:12Z) - Robust, randomized preconditioning for kernel ridge regression [3.521877014965197]
本稿では,カーネルリッジ回帰問題を解くための2つのランダム化プレコンディショニング手法について検討する。
最先端のパフォーマンスを持つ2つの新しいメソッドを導入している。
提案手法は広い範囲のKRR問題を解き、実用的な応用に最適である。
論文 参考訳（メタデータ） (2023-04-24T21:48:24Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
我々は、$ell_4$ノルムが同じ$ell$ノルムを持つガウスベクトルと異なるプラントベクトル$v$の効率的な推定と検出について研究する。
規則$n rho gg sqrtN$ では、大クラスのスペクトル法(そしてより一般的には、入力の低次法)は、植込みベクトルの検出に失敗する。
論文 参考訳（メタデータ） (2021-05-31T16:10:49Z) - Generalization error of random features and kernel methods:
hypercontractivity and kernel matrix concentration [19.78800773518545]
特徴空間 $mathbb RN$ におけるリッジ回帰と併用したランダム特徴量法の利用について検討する。
これは、カーネルリッジ回帰(KRR)の有限次元近似、またはいわゆる遅延訓練体制におけるニューラルネットワークの様式化されたモデルと見なすことができる。
論文 参考訳（メタデータ） (2021-01-26T06:46:41Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。