論文の概要: Fast Kernel Methods for Generic Lipschitz Losses via $p$-Sparsified Sketches

• arxiv url: http://arxiv.org/abs/2206.03827v7
• Date: Mon, 6 Nov 2023 12:41:16 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-08 01:55:02.544821
• Title: Fast Kernel Methods for Generic Lipschitz Losses via $p$-Sparsified Sketches
• Title（参考訳）: $p$-sparsified Sketchesによるジェネリックリプシッツ損失の高速カーネル法
• Authors: Tamim El Ahmad, Pierre Laforgue, Florence d'Alch\'e-Buc
• Abstract要約: カーネル法(カーネルほう、英: Kernel method)は、計算上の重要な制約に悩まされながら、固い理論の基礎を享受する学習アルゴリズムである。 散在したガウス(およびラデマッハ)のスケッチは、理論上有意な近似を生成する。 単一および複数出力のカーネル問題に対して過剰なリスク境界を導出し、汎用的なリプシッツ損失を与える。
• 参考スコア（独自算出の注目度）: 3.3379026542599934
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Kernel methods are learning algorithms that enjoy solid theoretical foundations while suffering from important computational limitations. Sketching, which consists in looking for solutions among a subspace of reduced dimension, is a well studied approach to alleviate these computational burdens. However, statistically-accurate sketches, such as the Gaussian one, usually contain few null entries, such that their application to kernel methods and their non-sparse Gram matrices remains slow in practice. In this paper, we show that sparsified Gaussian (and Rademacher) sketches still produce theoretically-valid approximations while allowing for important time and space savings thanks to an efficient \emph{decomposition trick}. To support our method, we derive excess risk bounds for both single and multiple output kernel problems, with generic Lipschitz losses, hereby providing new guarantees for a wide range of applications, from robust regression to multiple quantile regression. Our theoretical results are complemented with experiments showing the empirical superiority of our approach over SOTA sketching methods.
• Abstract（参考訳）: カーネル法(英: kernel method)は、計算上の重要な制限に苦しめながら、しっかりとした理論的基礎を享受する学習アルゴリズムである。 縮小次元の部分空間の解を求めることからなるスケッチは、これらの計算負担を軽減するためのよく研究されたアプローチである。 しかし、ガウスのスケッチのような統計的に正確なスケッチは、通常はヌルエントリをほとんど含んでおらず、カーネルメソッドや非疎グラム行列への応用は、実際には遅いままである。 本稿では,スパルサライズド・ガウス(およびラデマッハ)のスケッチが理論的に有価な近似を生成する一方で,効率の良い \emph{decomposition trick} による重要な時間と空間の節約を可能にしていることを示す。 提案手法をサポートするため,本手法では,ロバスト回帰からマルチクォンタイル回帰まで,幅広いアプリケーションに対して新たな保証を提供することにより,汎用リプシッツ損失を伴う単一および複数出力カーネル問題に対する過大なリスク境界を導出する。 我々の理論結果は,SOTAスケッチ法に対するアプローチの実証的優位性を示す実験と補完される。

関連論文リスト

• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。 この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
  論文  参考訳（メタデータ） (2023-11-04T11:12:24Z)
• Stochastic Gradient Descent for Gaussian Processes Done Right [86.83678041846971]
  emphdone right -- 最適化とカーネルコミュニティからの具体的な洞察を使用するという意味で -- が、勾配降下は非常に効果的であることを示している。 本稿では,直感的に設計を記述し,設計選択について説明する。 本手法は,分子結合親和性予測のための最先端グラフニューラルネットワークと同程度にガウス過程の回帰を配置する。
  論文  参考訳（メタデータ） (2023-10-31T16:15:13Z)
• Equation Discovery with Bayesian Spike-and-Slab Priors and Efficient Kernels [57.46832672991433]
  ケルネル学習とBayesian Spike-and-Slab pres (KBASS)に基づく新しい方程式探索法を提案する。 カーネルレグレッションを用いてターゲット関数を推定する。これはフレキシブルで表現力があり、データ空間やノイズに対してより堅牢である。 我々は,効率的な後部推論と関数推定のための予測伝搬予測最大化アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-10-09T03:55:09Z)
• Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints [9.301728976515255]
  本稿では,着陸アルゴリズムの実用化と理論的展開について述べる。 まず、この方法はスティーフェル多様体に拡張される。 また、コスト関数が多くの関数の平均である場合の分散還元アルゴリズムについても検討する。
  論文  参考訳（メタデータ） (2023-03-29T07:36:54Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Skyformer: Remodel Self-Attention with Gaussian Kernel and Nystr\"om Method [35.62926659320816]
  モデルトレーニングを安定させるために,ソフトマックス構造をガウスカーネルに置き換えるSkyformerを導入し,計算を高速化するためにNystr"om法を適用した。 Long Range Arenaベンチマークの実験では、提案手法は完全な自己注意よりも同等かそれ以上の性能を得るのに十分であることが示された。
  論文  参考訳（メタデータ） (2021-10-29T18:28:49Z)
• Progressive Batching for Efficient Non-linear Least Squares [31.082253632197023]
  ガウス・ニュートンの基本的な改良のほとんどは、基礎となる問題構造の空間性を保証するか、あるいは活用して計算速度を上げることである。 我々の研究は、機械学習と統計の両方からアイデアを借用し、収束を保証するとともに、必要な計算量を大幅に削減する非線形最小二乗に対するアプローチを提案する。
  論文  参考訳（メタデータ） (2020-10-21T13:00:04Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。 MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
  論文  参考訳（メタデータ） (2020-10-12T17:41:44Z)
• On Distributed Non-convex Optimization: Projected Subgradient Method For Weakly Convex Problems in Networks [13.385373310554327]
  Moreau subgradient 法は、機械学習における線形シャープネス問題を収束させる。 理論的保証を伴う下位段階法の分散実装を提案する。
  論文  参考訳（メタデータ） (2020-04-28T01:01:49Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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