論文の概要: Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nyström Method

• arxiv url: http://arxiv.org/abs/2506.17556v1
• Date: Sat, 21 Jun 2025 02:50:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-24 19:06:36.472447
• Title: Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nyström Method
• Title（参考訳）: Block-Nyström法による高速低ランク近似とカーネルリッジ回帰
• Authors: Sachin Garg, Michał Dereziński,
• Abstract要約: Block-Nystr"omはブロック対角構造をNystr"omメソッドに注入するアルゴリズムである。 第二次最適化のための改良されたプレコンディショナー構築にBlock-Nystr"omが利用できることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Nystr\"om method is a popular low-rank approximation technique for large matrices that arise in kernel methods and convex optimization. Yet, when the data exhibits heavy-tailed spectral decay, the effective dimension of the problem often becomes so large that even the Nystr\"om method may be outside of our computational budget. To address this, we propose Block-Nystr\"om, an algorithm that injects a block-diagonal structure into the Nystr\"om method, thereby significantly reducing its computational cost while recovering strong approximation guarantees. We show that Block-Nystr\"om can be used to construct improved preconditioners for second-order optimization, as well as to efficiently solve kernel ridge regression for statistical learning over Hilbert spaces. Our key technical insight is that, within the same computational budget, combining several smaller Nystr\"om approximations leads to stronger tail estimates of the input spectrum than using one larger approximation. Along the way, we provide a novel recursive preconditioning scheme for efficiently inverting the Block-Nystr\"om matrix, and provide new statistical learning bounds for a broad class of approximate kernel ridge regression solvers.
• Abstract（参考訳）: Nystr\"om法は、カーネル法や凸最適化で生じる大きな行列に対する一般的な低ランク近似手法である。 しかし、データが重み付きスペクトル崩壊を示すと、問題の有効次元が大きくなるため、Nystr\"om 法でさえ計算予算の外にある可能性がある。 そこで我々は,ブロック対角構造をNystr\"om法に注入するアルゴリズムであるBlock-Nystr\"omを提案する。 そこで,Block-Nystr\"omは2次最適化のための改良されたプレコンディショナーの構築や,Hilbert空間上の統計的学習のためのカーネルリッジ回帰を効率的に解くために利用できることを示す。 我々の重要な技術的洞察は、同じ計算予算の中で、いくつかの小さなNystr\"om近似を組み合わせることで、入力スペクトルの尾部推定が、1つの大きな近似を使用するよりも強くなるということである。 その過程でBlock-Nystr\"om行列を効率よく反転させる新しい再帰的事前条件付きスキームを提供し、カーネルリッジ回帰解法の幅広いクラスに対して新しい統計的学習境界を提供する。

関連論文リスト

• Symmetric Rank-One Quasi-Newton Methods for Deep Learning Using Cubic Regularization [0.5120567378386615]
  アダムやアダグラッドのような一階降下や他の一階変種は、ディープラーニングの分野で一般的に使われている。 しかし、これらの手法は曲率情報を活用しない。 準ニュートン法は、以前計算された低ヘッセン近似を再利用する。
  論文  参考訳（メタデータ） (2025-02-17T20:20:11Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• The Stochastic Conjugate Subgradient Algorithm For Kernel Support Vector Machines [1.738375118265695]
  本稿では,カーネルサポートベクトルマシン(SVM)に特化して設計された革新的な手法を提案する。 イテレーション毎のイテレーションを高速化するだけでなく、従来のSFO技術と比較して収束度も向上する。 実験の結果,提案アルゴリズムはSFO法のスケーラビリティを維持できるだけでなく,潜在的に超越していることが示された。
  論文  参考訳（メタデータ） (2024-07-30T17:03:19Z)
• Efficient Computation of Sparse and Robust Maximum Association Estimators [0.4588028371034406]
  ロバスト統計推定器は経験的精度を提供するが、しばしば高次元スパース設定において計算的に困難である。 現代のアソシエーション推定手法は、他のロバストな手法に対してレジリエンスを課すことなく、外れ値に利用される。
  論文  参考訳（メタデータ） (2023-11-29T11:57:50Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Boosting Nystr\"{o}m Method [0.688204255655161]
  Nystr"om法は、大きな行列の低ランク近似を生成する効果的なツールである。 我々は,複数の弱い'Nystr'om近似を反復的に生成するNystr"omを高速化する新しいアルゴリズム群を提案する。 我々は、Nystr"omアルゴリズムの高速化により、カーネル行列に対するより効率的で正確な低ランク近似が得られることを示した。
  論文  参考訳（メタデータ） (2023-02-21T22:20:55Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning [48.08663378234329]
  カーネル・リッジ・レグレッションやガウシアン・プロセスのようなカーネル・ベース・モデルは機械学習の応用においてユビキタスである。 既存のスパース近似法は計算コストを大幅に削減することができる。 我々は,Nystr"om法と疎変動ガウス過程近似法に対して,新しい信頼区間を提供する。
  論文  参考訳（メタデータ） (2022-02-08T17:22:09Z)
• Scalable Variational Gaussian Processes via Harmonic Kernel Decomposition [54.07797071198249]
  汎用性を維持しつつ高い忠実度近似を提供する,スケーラブルな変分ガウス過程近似を導入する。 様々な回帰問題や分類問題において,本手法は変換やリフレクションなどの入力空間対称性を活用できることを実証する。 提案手法は, 純粋なGPモデルのうち, CIFAR-10 の最先端化を実現する。
  論文  参考訳（メタデータ） (2021-06-10T18:17:57Z)
• Progressive Batching for Efficient Non-linear Least Squares [31.082253632197023]
  ガウス・ニュートンの基本的な改良のほとんどは、基礎となる問題構造の空間性を保証するか、あるいは活用して計算速度を上げることである。 我々の研究は、機械学習と統計の両方からアイデアを借用し、収束を保証するとともに、必要な計算量を大幅に削減する非線形最小二乗に対するアプローチを提案する。
  論文  参考訳（メタデータ） (2020-10-21T13:00:04Z)

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

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