Fugu-MT 論文翻訳(概要): Robust, randomized preconditioning for kernel ridge regression

論文の概要: Robust, randomized preconditioning for kernel ridge regression

arxiv url: http://arxiv.org/abs/2304.12465v4
Date: Wed, 10 Jul 2024 19:46:15 GMT
ステータス: 処理完了
システム内更新日: 2024-07-13 00:07:09.755383
Title: Robust, randomized preconditioning for kernel ridge regression
Title（参考訳）: カーネルリッジ回帰のためのロバスト・ランダム化プレコンディショニング
Authors: Mateo Díaz, Ethan N. Epperly, Zachary Frangella, Joel A. Tropp, Robert J. Webber,
Abstract要約: 本稿では,カーネルリッジ回帰問題を解くための2つのランダム化プレコンディショニング手法について検討する。最先端のパフォーマンスを持つ2つの新しいメソッドを導入している。提案手法は広い範囲のKRR問題を解き、実用的な応用に最適である。
参考スコア（独自算出の注目度）: 3.521877014965197
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: This paper investigates two randomized preconditioning techniques for solving kernel ridge regression (KRR) problems with a medium to large number of data points ($10^4 \leq N \leq 10^7$), and it introduces two new methods with state-of-the-art performance. The first method, RPCholesky preconditioning, accurately solves the full-data KRR problem in $O(N^2)$ arithmetic operations, assuming sufficiently rapid polynomial decay of the kernel matrix eigenvalues. The second method, KRILL preconditioning, offers an accurate solution to a restricted version of the KRR problem involving $k \ll N$ selected data centers at a cost of $O((N + k^2) k \log k)$ operations. The proposed methods solve a broad range of KRR problems, making them ideal for practical applications.
Abstract（参考訳）: 本稿では,カーネルリッジ回帰(KRR)問題を中～多量のデータポイント(10^4 \leq N \leq 10^7$)で解くための2つのランダム化プレコンディショニング手法を検討した。最初の方法であるRPCholeskyプレコンディショニングは、カーネル行列固有値の十分速い多項式崩壊を仮定して、$O(N^2)$算術演算の完全データKRR問題を正確に解く。 2つ目の方法、KRILLプリコンディショニングは、$k \ll N$選択されたデータセンターを$O((N + k^2) k \log k)の演算で制限されたバージョンのKRR問題に対する正確な解決策を提供する。提案手法は広い範囲のKRR問題を解き、実用的な応用に最適である。

関連論文リスト

Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression [44.13655983242414]
最適誤差保証付きニア・ニア・ニア・リニア時間アルゴリズムの最初のサンプルを設計する。堅牢な線形回帰のために、サンプル複雑性$n = tildeO(d/epsilon2)$と、ターゲット回帰器を$ell$-$O(epsilon)$で近似するほぼ線形ランタイムを持つ最初のアルゴリズムを与える。これは、文献のオープンな疑問に答え、最適なエラー保証を達成するための最初のサンプルとタイムアルゴリズムである。
論文参考訳（メタデータ） (2023-12-04T00:31:16Z)
A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical Initialization [107.07093621337084]
正規化カット(N-Cut)は、スペクトルクラスタリングの有名なモデルである。 1)正規化ラプラシア行列の連続スペクトル埋め込みを計算する; 2)$K$-meansまたはスペクトル回転による離散化。有名な座標降下法に基づく新しいN-Cut解法を提案する。
論文参考訳（メタデータ） (2023-11-26T07:11:58Z)
A quantum central path algorithm for linear optimization [5.450016817940232]
中心経路の量子力学的シミュレーションにより線形最適化問題を解くための新しい量子アルゴリズムを提案する。このアプローチは、$m$制約と$n$変数を含む線形最適化問題を$varepsilon$-optimalityに解くアルゴリズムをもたらす。標準ゲートモデル(すなわち、量子RAMにアクセスせずに)では、我々のアルゴリズムは少なくとも$$mathcalO left( sqrtm + n textsfnnz (A) fracR_1 を用いてLO問題の高精度な解を得ることができる。
論文参考訳（メタデータ） (2023-11-07T13:26:20Z)
Oracle Complexity Reduction for Model-free LQR: A Stochastic Variance-Reduced Policy Gradient Approach [4.422315636150272]
離散時間線形擬似レギュレータ(LQR)問題に対する$epsilon$-approximateソリューションの学習問題について検討する。本手法は,二ループ分散推定アルゴリズムにおいて,一点推定と二点推定を併用する。
論文参考訳（メタデータ） (2023-09-19T15:03:18Z)
Convergence analysis of online algorithms for vector-valued kernel regression [0.42970700836450487]
オンライン学習アルゴリズムを用いて雑音の多いベクトル値データから回帰関数を近似する問題を考察する。 RKHSノルムの期待二乗誤差は$C2 (m+1)-s/(2+s)$でバウンドできることを示し、$m$は現在の処理データの数である。
論文参考訳（メタデータ） (2023-09-14T15:10:47Z)
Learning "best" kernels from data in Gaussian process regression. With application to aerodynamics [0.4588028371034406]
本稿では,ガウス過程の回帰/クリギングサロゲートモデリング手法におけるカーネルの選択/設計アルゴリズムを紹介する。アルゴリズムの最初のクラスはカーネルフローであり、機械学習の分類の文脈で導入された。アルゴリズムの第2のクラスはスペクトル核リッジ回帰と呼ばれ、近似される関数のノルムが最小となるような「最良の」カーネルを選択することを目的としている。
論文参考訳（メタデータ） (2022-06-03T07:50:54Z)
Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文参考訳（メタデータ） (2022-05-27T00:34:03Z)
Conditional Uncorrelation and Efficient Non-approximate Subset Selection in Sparse Regression [72.84177488527398]
相関性の観点からスパース回帰を考察し,条件付き非相関式を提案する。提案手法により、計算複雑性は、スパース回帰における各候補部分集合に対して$O(frac16k3+mk2+mkd)$から$O(frac16k3+frac12mk2)$に削減される。
論文参考訳（メタデータ） (2020-09-08T20:32:26Z)
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)
An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives [54.29001037565384]
本稿では,オンライン分散ロバスト最適化(DRO)のクラスを解決するための実用的なオンライン手法を提案する。本研究は,ネットワークの堅牢性向上のための機械学習における重要な応用を実証する。
論文参考訳（メタデータ） (2020-06-17T20:19:25Z)
Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文参考訳（メタデータ） (2020-02-21T17:45:32Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。