論文の概要: Fast Second-Order Online Kernel Learning through Incremental Matrix Sketching and Decomposition

• arxiv url: http://arxiv.org/abs/2410.11188v1
• Date: Tue, 15 Oct 2024 02:07:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-16 14:01:41.982823
• Title: Fast Second-Order Online Kernel Learning through Incremental Matrix Sketching and Decomposition
• Title（参考訳）: インクリメンタルマトリックススケッチと分解による高速2次オンラインカーネル学習
• Authors: Dongxie Wen, Xiao Zhang, Zhewei Wei,
• Abstract要約: オンライン学習(OKL)は、ストリーミング環境での予測性能が期待できるため、かなりの研究関心を集めている。 既存の2次OKLアプローチは、予め設定された予算に関して、少なくとも2次時間の複雑さに悩まされている。 本稿では,2次OKLに適した高速増分行列スケッチと分解手法FORTSを提案する。
• 参考スコア（独自算出の注目度）: 22.39048660630147
• License:
• Abstract: Online Kernel Learning (OKL) has attracted considerable research interest due to its promising predictive performance in streaming environments. Second-order approaches are particularly appealing for OKL as they often offer substantial improvements in regret guarantees. However, existing second-order OKL approaches suffer from at least quadratic time complexity with respect to the pre-set budget, rendering them unsuitable for meeting the real-time demands of large-scale streaming recommender systems. The singular value decomposition required to obtain explicit feature mapping is also computationally expensive due to the complete decomposition process. Moreover, the absence of incremental updates to manage approximate kernel space causes these algorithms to perform poorly in adversarial environments and real-world streaming recommendation datasets. To address these issues, we propose FORKS, a fast incremental matrix sketching and decomposition approach tailored for second-order OKL. FORKS constructs an incremental maintenance paradigm for second-order kernelized gradient descent, which includes incremental matrix sketching for kernel approximation and incremental matrix decomposition for explicit feature mapping construction. Theoretical analysis demonstrates that FORKS achieves a logarithmic regret guarantee on par with other second-order approaches while maintaining a linear time complexity w.r.t. the budget, significantly enhancing efficiency over existing approaches. We validate the performance of FORKS through extensive experiments conducted on real-world streaming recommendation datasets, demonstrating its superior scalability and robustness against adversarial attacks.
• Abstract（参考訳）: オンラインカーネル学習(OKL)は、ストリーミング環境での予測性能が期待できるため、かなりの研究関心を集めている。 2階のアプローチは、しばしば後悔の保証を大幅に改善するので、特にOKLにアピールする。 しかし、既存の2次OKLアプローチは、事前設定された予算に関して少なくとも2次時間複雑さに悩まされており、大規模なストリーミングレコメンデータシステムのリアルタイム要求を満たすには不適当である。 明示的な特徴写像を得るのに必要な特異値分解も、完全な分解過程のため計算コストがかかる。 さらに、カーネル空間を管理するためのインクリメンタルアップデートが存在しないため、これらのアルゴリズムは、敵環境や実世界のストリーミングレコメンデーションデータセットでパフォーマンスが悪くなる。 これらの問題に対処するために,2次OKLに適した高速増分行列スケッチと分解手法FORTSを提案する。 FORKSは、カーネル近似のためのインクリメンタルマトリクススケッチと明示的な特徴マッピング構築のためのインクリメンタルマトリクス分解を含む、2階のカーネル化勾配降下のためのインクリメンタルメンテナンスパラダイムを構築する。 理論的解析により、ForKSは他の2階のアプローチと同等の対数的後悔の保証を達成し、予算の線形時間複雑性を維持し、既存のアプローチよりも効率を著しく向上させることが示されている。 我々は、実世界のストリーミングレコメンデーションデータセットで行った広範な実験を通じて、ForceKSの性能を検証し、その優れたスケーラビリティと敵攻撃に対する堅牢性を実証した。

関連論文リスト

• Efficient Second-Order Neural Network Optimization via Adaptive Trust Region Methods [0.0]
  SecondOrderAdaptive (SOAA) は、従来の二階法の限界を克服するために設計された新しい最適化アルゴリズムである。 私たちは、SOAAが1次近似よりも速く、より安定した収束を達成することを実証的に実証します。
  論文  参考訳（メタデータ） (2024-10-03T08:23:06Z)
• Short-Long Convolutions Help Hardware-Efficient Linear Attention to Focus on Long Sequences [60.489682735061415]
  本稿では,状態空間モデルを短時間の畳み込みに置き換えたCHELAを提案する。 提案手法の有効性を示すために,Long Range Arenaベンチマークと言語モデリングタスクについて実験を行った。
  論文  参考訳（メタデータ） (2024-06-12T12:12:38Z)
• OptEx: Expediting First-Order Optimization with Approximately Parallelized Iterations [12.696136981847438]
  ほぼ並列化されたイテレーション (OptEx) で高速化された一階最適化を導入する。 OptExは、並列コンピューティングを活用して、その反復的ボトルネックを軽減することで、FOOの効率を高める最初のフレームワークである。 我々は、カーネル化された勾配推定の信頼性とSGDベースのOpsExの複雑さを理論的に保証する。
  論文  参考訳（メタデータ） (2024-02-18T02:19:02Z)
• Fast Dual-Regularized Autoencoder for Sparse Biological Data [65.268245109828]
  本研究では,近傍正規化行列補完問題に対する浅層オートエンコーダを開発する。 本研究は, 薬物と薬物の相互作用と薬物の放出関連性を予測する上で, 既存の最先端技術に対するアプローチの速度と精度の優位性を実証する。
  論文  参考訳（メタデータ） (2024-01-30T01:28:48Z)
• Conditional Denoising Diffusion for Sequential Recommendation [62.127862728308045]
  GAN(Generative Adversarial Networks)とVAE(VAE)の2つの顕著な生成モデル GANは不安定な最適化に苦しむ一方、VAEは後続の崩壊と過度に平らな世代である。 本稿では,シーケンスエンコーダ,クロスアテンティブデノナイジングデコーダ,ステップワイズディフューザを含む条件付きデノナイジング拡散モデルを提案する。
  論文  参考訳（メタデータ） (2023-04-22T15:32:59Z)
• Optimal Regularized Online Allocation by Adaptive Re-Solving [16.873430173722994]
  本稿では、正規化されたオンラインリソース割り当て問題を解決するために、デュアルベースのアルゴリズムフレームワークを提案する。 資源制約を適応的に更新する戦略の下で、提案手法は経験的二重問題に対する近似解をある程度の精度で要求するのみである。 驚いたことに、二重目的関数の微妙な解析により、後悔境界における悪名高いログ係数を排除できる。
  論文  参考訳（メタデータ） (2022-09-01T12:23:26Z)
• SCORE: Approximating Curvature Information under Self-Concordant Regularization [0.0]
  本稿では,新たな入力を受信するたびに最小化速度を更新する自己調和正規化アルゴリズム(GGN-SCORE)を提案する。 提案アルゴリズムはヘッセン行列の2階情報構造を利用して計算オーバーヘッドを削減する。
  論文  参考訳（メタデータ） (2021-12-14T13:03:04Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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