論文の概要: Robust, randomized preconditioning for kernel ridge regression
- arxiv url: http://arxiv.org/abs/2304.12465v1
- Date: Mon, 24 Apr 2023 21:48:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-26 22:36:24.622968
- Title: Robust, randomized preconditioning for kernel ridge regression
- Title（参考訳）: カーネルリッジ回帰のためのロバスト・ランダム化プレコンディショニング
- Authors: Mateo D\'iaz, Ethan N. Epperly, Zachary Frangella, Joel A. Tropp, and
Robert J. Webber
- Abstract要約: 最初の方法であるRPCholeskyプリコンディショニングは、$O(N2)$算術演算で全データKRR問題を正確に解くことができる。
第2の手法であるKRILLプリコンディショニングは、k ll N$選択されたデータセンターを含むKRR問題の制限されたバージョンに対する正確な解決策を提供する。
- 参考スコア（独自算出の注目度）: 0.31806743741013654
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper introduces two randomized preconditioning techniques for robustly
solving kernel ridge regression (KRR) problems with a medium to large number of
data points ($10^4 \leq N \leq 10^7$). The first method, RPCholesky
preconditioning, is capable of accurately solving 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 and overcome the
failure modes of previous KRR preconditioners, 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問題を解くとともに,従来の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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。