論文の概要: Have ASkotch: A Neat Solution for Large-scale Kernel Ridge Regression

• arxiv url: http://arxiv.org/abs/2407.10070v2
• Date: Fri, 21 Feb 2025 22:38:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-25 22:36:55.404451
• Title: Have ASkotch: A Neat Solution for Large-scale Kernel Ridge Regression
• Title（参考訳）: Have ASkotch: 大規模カーネルリッジ回帰のためのネアットソリューション
• Authors: Pratik Rathore, Zachary Frangella, Jiaming Yang, Michał Dereziński, Madeleine Udell,
• Abstract要約: ASkotchは、線形収束を確実に得るフルKRRのスケーラブルで加速された反復的手法である。 Askotchは23の大規模KRR回帰および分類タスクのテストベッド上で最先端のKRRソルバより優れている。 我々の研究は、多くの分野にわたる完全なKRRの非想像的応用の可能性を開く。
• 参考スコア（独自算出の注目度）: 16.836685923503868
• 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, full KRR solvers are challenging to scale to large datasets: both direct (i.e., Cholesky decomposition) and iterative methods (i.e., PCG) incur prohibitive computational and storage costs. The standard approach to scale KRR to large datasets chooses a set of inducing points and solves an approximate version of the problem, inducing points KRR. However, the resulting solution tends to have worse predictive performance than the full KRR solution. In this work, we introduce a new solver, ASkotch, for full KRR that provides better solutions faster than state-of-the-art solvers for full and inducing points KRR. ASkotch is a scalable, accelerated, iterative method for full KRR that provably obtains linear convergence. Under appropriate conditions, we show that ASkotch obtains condition-number-free linear convergence. This convergence analysis rests on the theory of ridge leverage scores and determinantal point processes. ASkotch outperforms state-of-the-art KRR solvers on a testbed of 23 large-scale KRR regression and classification tasks derived from a wide range of application domains, demonstrating the superiority of full KRR over inducing points KRR. Our work opens up the possibility of as-yet-unimagined applications of full KRR across a number of disciplines.
• Abstract（参考訳）: カーネルリッジ回帰(カーネルリッジ回帰、英: Kernel ridge regression、KRR)は、計算化学から健康分析まで幅広い問題に現れ、ガウス過程の回帰において特に重要な役割を担っている。 しかしながら、完全なKRRソルバは、直接(チョレスキー分解)と反復法(PCG)の両方が禁忌な計算と記憶コストを伴って、大規模なデータセットにスケールすることが困難である。 KRRを大規模データセットにスケールする標準的なアプローチは、ポイントのセットを選択し、問題の近似バージョンを解き、ポイントKRRを誘導する。 しかし、結果として得られる解は完全なKRR解よりも予測性能が悪くなる傾向にある。 そこで本研究では,完全KRRのための新しい解法ASkotchを導入する。 ASkotchは、線形収束を確実に得るフルKRRのスケーラブルで加速された反復的手法である。 適切な条件下では、ASkotch が条件数自由線型収束を得ることを示す。 この収束解析はリッジレバレッジスコアと決定点過程の理論に基づいている。 Askotchは、23の大規模KRR回帰と広範囲のアプリケーションドメインから派生した分類タスクからなるテストベッド上で、最先端KRRソルバを上回り、KRRを誘導する点よりもフルKRRの方が優れていることを示す。 我々の研究は、多くの分野にわたる完全なKRRの非想像的応用の可能性を開く。

関連論文リスト

• Logarithmic Regret for Online KL-Regularized Reinforcement Learning [51.113248212150964]
  KL正規化は、大規模言語モデルにおけるRL微調整の効率向上に重要な役割を果たしている。 経験的優位性にもかかわらず、KL-正則化RLと標準RLの理論的相違はほとんど未探索のままである。 楽観的なKL正規化オンライン文脈帯域幅アルゴリズムを提案し,その後悔の新たな分析法を提案する。
  論文  参考訳（メタデータ） (2025-02-11T11:11:05Z)
• 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 and Saturation for Noiseless Kernel Ridge Regression [4.585021053685196]
  ノイズレスシステムにおけるカーネルリッジ回帰(KRR)の総合的研究について述べる。 KRRは有限標本から関数を学習するための基本的な方法である。 我々は、カーネルメソッドの解析に広く適用可能な、洗練された自由度の概念を導入する。
  論文  参考訳（メタデータ） (2024-02-24T04:57:59Z)
• 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)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。 ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
  論文  参考訳（メタデータ） (2023-05-28T06:33:37Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。 我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
  論文  参考訳（メタデータ） (2023-05-22T17:43:34Z)
• 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)
• Overparameterized random feature regression with nearly orthogonal data [21.97381518762387]
  本研究では,2層ニューラルネットワークによるランダム特徴リッジ回帰(RFRR)の非漸近挙動について検討した。 我々の結果は、ほぼ決定論的性質を示す様々なアクティベーション関数と入力データセットに対して成り立っている。
  論文  参考訳（メタデータ） (2022-11-11T09:16:25Z)
• Distributed Random Reshuffling over Networks [7.013052033764372]
  凸関数と滑らかな対象関数の問題を解くために分散resh-upr (D-RR) アルゴリズムを提案する。 特に、滑らかな凸対象関数に対して、D-RRはD-T収束率(T がエポック数を数える)を大域ドライブ間の距離で達成する。
  論文  参考訳（メタデータ） (2021-12-31T03:59:37Z)
• SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
  既存のKRRの実装では、すべてのデータがメインメモリに格納される必要がある。 KRRのストリーミング版であるStreaMRAKを提案する。 本稿では,2つの合成問題と2重振り子の軌道予測について紹介する。
  論文  参考訳（メタデータ） (2021-08-23T21:03:09Z)
• Oversampling Divide-and-conquer for Response-skewed Kernel Ridge Regression [20.00435452480056]
  本研究では,分割・分散手法の限界を克服するために,新しい応答適応分割戦略を開発する。 提案手法は, 従来のダックKRR推定値よりも小さい平均二乗誤差(AMSE)を有することを示す。
  論文  参考訳（メタデータ） (2021-07-13T04:01:04Z)
• 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)
• Square Root Bundle Adjustment for Large-Scale Reconstruction [56.44094187152862]
  QR分解によるランドマーク変数のnullspace marginalizationに依存するバンドル調整問題の新たな定式化を提案する。 平方根束調整と呼ばれる私たちのアプローチは、一般的に使用されるSchur補完トリックと代数的に等価です。 BALデータセットを用いた実世界での実験では、提案されたソルバが単一の精度でも平均的等しく正確なソリューションで達成できることを示す。
  論文  参考訳（メタデータ） (2021-03-02T16:26:20Z)
• 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)
• Approximation Schemes for ReLU Regression [80.33702497406632]
  我々はReLU回帰の根本的な問題を考察する。 目的は、未知の分布から引き出された2乗損失に対して、最も適したReLUを出力することである。
  論文  参考訳（メタデータ） (2020-05-26T16:26:17Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。