論文の概要: $p$-Sparsified Sketches for Fast Multiple Output Kernel Methods
- arxiv url: http://arxiv.org/abs/2206.03827v1
- Date: Wed, 8 Jun 2022 11:50:23 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-09 13:18:32.479163
- Title: $p$-Sparsified Sketches for Fast Multiple Output Kernel Methods
- Title(参考訳): 高速複数出力カーネルメソッドのための$p$-sparsified sketch
- Authors: Tamim El Ahmad, Pierre Laforgue, Florence d'Alch\'e-Buc
- Abstract要約: カーネル法(カーネルほう、英: Kernel method)は、計算上の重要な制約に悩まされながら、固い理論の基礎を享受する学習アルゴリズムである。
非適応サブサンプリングのような高速なスケッチ戦略は、アルゴリズムの保証を著しく低下させる。
我々は、統計的精度と計算効率の良好なトレードオフを達成するために、両方のアプローチの利点を組み合わせた$p$sparsifiedスケッチを紹介した。
- 参考スコア(独自算出の注目度): 5.5969337839476765
- 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, that consists in looking for solutions among a subspace of reduced
dimension, is a widely studied approach to alleviate this numerical burden.
However, fast sketching strategies, such as non-adaptive subsampling,
significantly degrade the guarantees of the algorithms, while
theoretically-accurate sketches, such as the Gaussian one, turn out to remain
relatively slow in practice. In this paper, we introduce the $p$-sparsified
sketches, that combine the benefits from both approaches to achieve a good
tradeoff between statistical accuracy and computational efficiency. To support
our method, we derive excess risk bounds for both single and multiple output
problems, with generic Lipschitz losses, providing new guarantees for a wide
range of applications, from robust regression to multiple quantile regression.
We also provide empirical evidences of the superiority of our sketches over
recent SOTA approaches.
- Abstract(参考訳): カーネル法(英: kernel method)は、計算上の重要な制限に苦しめながら、しっかりとした理論的基礎を享受する学習アルゴリズムである。
縮小次元の部分空間の解を求めることからなるスケッチは、この数値的負担を軽減するために広く研究されているアプローチである。
しかし、非適応部分サンプリングのような素早いスケッチ戦略はアルゴリズムの保証を著しく低下させるが、ガウス的スケッチのような理論的に正確なスケッチは実際には比較的遅いままである。
本稿では,統計精度と計算効率との良好なトレードオフを実現するために,両者のアプローチの利点を組み合わせた,p$-sparsified sketchsを提案する。
本手法をサポートするため,本手法は,単一出力問題と複数出力問題の両方に対する過大なリスク境界を導出し,ロバスト回帰から複数量子量回帰まで,幅広いアプリケーションに対して新たな保証を提供する。
また、最近のSOTAアプローチよりもスケッチの方が優れているという実証的な証拠も提示する。
関連論文リスト
- Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。
この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
論文 参考訳(メタデータ) (2023-11-04T11:12:24Z) - Equation Discovery with Bayesian Spike-and-Slab Priors and Efficient
Kernels [60.35011738807833]
ケルネル学習とBayesian Spike-and-Slab pres (KBASS)に基づく新しい方程式探索法を提案する。
カーネルレグレッションを用いてターゲット関数を推定する。これはフレキシブルで表現力があり、データ空間やノイズに対してより堅牢である。
我々は、ベンチマークODEとPDE発見タスクのリストにおいて、KBASSの顕著な利点を示す。
論文 参考訳(メタデータ) (2023-10-09T03:55:09Z) - Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms
for Optimization under Orthogonality Constraints [8.59102802625914]
本稿では,着陸アルゴリズムの実用化と理論的展開について述べる。
まず、この方法はスティーフェル多様体に拡張される。
また、コスト関数が多くの関数の平均である場合、分散と還元のアルゴリズムも検討する。
論文 参考訳(メタデータ) (2023-03-29T07:36:54Z) - Sketch In, Sketch Out: Accelerating both Learning and Inference for
Structured Prediction with Kernels [6.126929553818864]
サーロゲートカーネルベースの手法は、入力空間と出力空間の両方でカーネルトリックを活用することにより、構造化された出力予測に対する柔軟なソリューションを提供する。
提案手法は,入力と出力の両方の特徴写像で特徴写像の低階射影と見なされるスケッチに基づく近似を持つ。
時間とメモリの複雑さの分析によると、入力カーネルのスケッチはトレーニング時間を短縮し、出力カーネルのスケッチは推論時間を短縮する。
論文 参考訳(メタデータ) (2023-02-20T18:00:21Z) - On the Benefits of Large Learning Rates for Kernel Methods [110.03020563291788]
本稿では,カーネル手法のコンテキストにおいて,現象を正確に特徴付けることができることを示す。
分離可能なヒルベルト空間における2次対象の最小化を考慮し、早期停止の場合、学習速度の選択が得られた解のスペクトル分解に影響を及ぼすことを示す。
論文 参考訳(メタデータ) (2022-02-28T13:01:04Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。