論文の概要: BLOKS: Scaling Kernel Solvers with Sketched Block Preconditioning

• arxiv url: http://arxiv.org/abs/2610.13382v1
• Date: Fri, 09 Oct 2026 10:57:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-13 04:06:29.543197
• Title: BLOKS: Scaling Kernel Solvers with Sketched Block Preconditioning
• Title（参考訳）: BLOKS:Sketched Block Preconditioningによるカーネルソリューションのスケーリング
• Abstract要約: 正確なカーネルリッジ回帰(KRR)は、大規模なデータセットに適用不可能な時間とメモリコストを発生させる。 ブロックヤコビ近似とスケッチを組み合わせた新しいプレコンディショナーを構築。 我々は,メモリ効率のよいGPUアクセラレーション実装を提供し,BLOKSが良好な時間/メモリの複雑さを維持しつつ,優れた精度を実現することを示す。
• 参考スコア（独自算出の注目度）: 8.682789403075404
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Kernel Ridge Regression (KRR) is a theoretically sound algorithm for nonparametric learning, which is also often used to investigate properties of deep learning. However, the exact KRR formulation incurs time and memory costs preventing applicability to large datasets, motivating the development of approximate solvers. These algorithms rely on (i) iterative methods, to avoid the computational burden of direct solutions; (ii) sketching or batching, to reduce the problem size; and (iii) preconditioning, to accelerate convergence. While crucial for fast convergence, preconditioning incurs memory costs that can be managed by lowering the number of free parameters of the model, potentially at the expense of expressivity and hence accuracy. To address this challenge, we propose BLOKS, a Conjugate Gradient-based solver for Nyström-sketched KRR built around a novel preconditioner that combines a block Jacobi approximation with sketching. The BLOKS preconditioner has memory cost independent of both the dataset size and the number of parameters, allowing scaling to large models. We provide a memory-efficient, GPU-accelerated implementation and show that BLOKS achieves excellent accuracy while retaining favorable time/memory complexity. Indeed, on standard large-scale datasets used to benchmark kernel solvers, BLOKS achieves comparable or better performances than state-of-the-art methods.
• Abstract（参考訳）: カーネルリッジ回帰(英: Kernel Ridge Regression、KRR)は、非パラメトリック学習のための理論的に健全なアルゴリズムである。 しかし、正確な KRR の定式化は、時間とメモリのコストが大きなデータセットの適用性を妨げ、近似解法の開発を動機付けている。 これらのアルゴリズムは 一 直接解の計算負担を回避するための反復方法 (二 問題の大きさを小さくするため、スケッチ又はバッチ (三)収束を早めるためのプレコンディショニング 高速収束には不可欠だが、プレコンディショニングはモデルの自由パラメータ数を減らして管理できるメモリコストを発生させる。 この課題に対処するために,Nyström-sketched KRR の共役勾配に基づく解法 BLOKS を提案する。 BLOKSプリコンディショナーは、データセットサイズとパラメータ数の両方に依存しないメモリコストを持ち、大規模モデルへのスケーリングを可能にする。 我々は,メモリ効率のよいGPUアクセラレーション実装を提供し,BLOKSが良好な時間/メモリの複雑さを維持しつつ,優れた精度を実現することを示す。 実際、カーネルソルバのベンチマークに使用される標準的な大規模データセットでは、BLOKSは最先端の手法よりも同等または優れたパフォーマンスを達成している。

関連論文リスト

• Backward-Friendly Optimization: Training Large Language Models with Approximate Gradients under Memory Constraints [14.20716202034732]
  LLM(Large Language Models)の完全な微調整は、メモリ集約性で悪名高い。 GradLiteは、正確な勾配の要求を緩和する後方フレンドリーなソリューションである。 我々はGradLiteが有界な分散を伴う不偏推定を維持し、Adamに匹敵する収束率を保証することを示す。
  論文  参考訳（メタデータ） (2025-10-26T00:50:12Z)
• Computation-Aware Gaussian Processes: Model Selection And Linear-Time Inference [55.150117654242706]
  我々は、1.8万のデータポイントでトレーニングされた計算対応GPのモデル選択が、1つのGPU上で数時間以内に可能であることを示す。 この研究の結果、ガウス過程は、不確実性を定量化する能力を著しく妥協することなく、大規模なデータセットで訓練することができる。
  論文  参考訳（メタデータ） (2024-11-01T21:11:48Z)
• Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
  本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。 我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。 RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
  論文  参考訳（メタデータ） (2022-10-21T15:56:13Z)
• Memory Safe Computations with XLA Compiler [14.510796427699459]
  XLAコンパイラ拡張は、ユーザーが指定したメモリ制限に従ってアルゴリズムの表現を調整する。 我々は,k-アネレスト近傍およびスパースガウス過程回帰法が単一デバイス上ではるかに大きなスケールで実行可能であることを示す。
  論文  参考訳（メタデータ） (2022-06-28T16:59:28Z)
• Deep Equilibrium Optical Flow Estimation [80.80992684796566]
  最近のSOTA(State-of-the-art)光フローモデルでは、従来のアルゴリズムをエミュレートするために有限ステップの更新操作を使用する。 これらのRNNは大きな計算とメモリオーバーヘッドを課し、そのような安定した推定をモデル化するために直接訓練されていない。 暗黙的層の無限レベル固定点として直接流れを解く手法として,Deep equilibrium Flow estimatorを提案する。
  論文  参考訳（メタデータ） (2022-04-18T17:53:44Z)
• SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
  既存のKRRの実装では、すべてのデータがメインメモリに格納される必要がある。 KRRのストリーミング版であるStreaMRAKを提案する。 本稿では,2つの合成問題と2重振り子の軌道予測について紹介する。
  論文  参考訳（メタデータ） (2021-08-23T21:03:09Z)
• Square Root Bundle Adjustment for Large-Scale Reconstruction [56.44094187152862]
  QR分解によるランドマーク変数のnullspace marginalizationに依存するバンドル調整問題の新たな定式化を提案する。 平方根束調整と呼ばれる私たちのアプローチは、一般的に使用されるSchur補完トリックと代数的に等価です。 BALデータセットを用いた実世界での実験では、提案されたソルバが単一の精度でも平均的等しく正確なソリューションで達成できることを示す。
  論文  参考訳（メタデータ） (2021-03-02T16:26:20Z)
• Memory and Computation-Efficient Kernel SVM via Binary Embedding and Ternary Model Coefficients [18.52747917850984]
  カーネル近似はカーネルSVMのトレーニングと予測のスケールアップに広く用いられている。 メモリ制限されたデバイスにデプロイしたい場合、カーネル近似モデルのメモリと計算コストはまだ高すぎる。 本稿では,バイナリ埋め込みとバイナリモデル係数を用いて,新しいメモリと計算効率の高いカーネルSVMモデルを提案する。
  論文  参考訳（メタデータ） (2020-10-06T09:41:54Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)

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

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