論文の概要: Limited Memory Online Gradient Descent for Kernelized Pairwise Learning
with Dynamic Averaging
- arxiv url: http://arxiv.org/abs/2402.01146v1
- Date: Fri, 2 Feb 2024 05:21:50 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-05 16:51:29.868933
- Title: Limited Memory Online Gradient Descent for Kernelized Pairwise Learning
with Dynamic Averaging
- Title(参考訳): 動的平均化によるカーネル化ペアワイズ学習のための限定記憶オンライングラディエントDescent
- Authors: Hilal AlQuabeh, William de Vazelhes, Bin Gu
- Abstract要約: 実例の独立性を必要としない軽量なOGDアルゴリズムを導入し、カーネル対学習に一般化する。
提案アルゴリズムは,ランダムな例と過去のデータを表す移動平均に基づいて勾配を構築し,その結果,O(T)$の複雑さに縛られたサブ線形後悔が生じる。
実世界のデータセットによるいくつかの実験では、複雑性技術がオフラインおよびオンラインシナリオでカーネルと線形勾配を上回ることが示されている。
- 参考スコア(独自算出の注目度): 18.843097436906618
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Pairwise learning, an important domain within machine learning, addresses
loss functions defined on pairs of training examples, including those in metric
learning and AUC maximization. Acknowledging the quadratic growth in
computation complexity accompanying pairwise loss as the sample size grows,
researchers have turned to online gradient descent (OGD) methods for enhanced
scalability. Recently, an OGD algorithm emerged, employing gradient computation
involving prior and most recent examples, a step that effectively reduces
algorithmic complexity to $O(T)$, with $T$ being the number of received
examples. This approach, however, confines itself to linear models while
assuming the independence of example arrivals. We introduce a lightweight OGD
algorithm that does not require the independence of examples and generalizes to
kernel pairwise learning. Our algorithm builds the gradient based on a random
example and a moving average representing the past data, which results in a
sub-linear regret bound with a complexity of $O(T)$. Furthermore, through the
integration of $O(\sqrt{T}{\log{T}})$ random Fourier features, the complexity
of kernel calculations is effectively minimized. Several experiments with
real-world datasets show that the proposed technique outperforms kernel and
linear algorithms in offline and online scenarios.
- Abstract(参考訳): ペアワイズ学習は、機械学習における重要なドメインであり、メトリック学習やauc最大化を含む、トレーニング例のペアで定義された損失関数に対処する。
サンプルサイズが大きくなるにつれて、計算複雑性の二次的な成長がペアワイズ損失を伴うことを認め、研究者は拡張性を高めるためのオンライン勾配降下法(OGD)に目を向けた。
近年、OGDアルゴリズムが登場し、前例と最近の例を含む勾配計算を取り入れ、アルゴリズムの複雑さを効果的に$O(T)$に減らし、$T$は受信したサンプルの数である。
しかしこのアプローチは、サンプル到着の独立性を仮定しながら、線形モデルに限定する。
実例の独立性を必要としない軽量なOGDアルゴリズムを導入し、カーネル対学習に一般化する。
提案アルゴリズムは,ランダムな例と過去のデータを表す移動平均に基づいて勾配を構築し,その結果,O(T)$の複雑さに縛られたサブ線形後悔が生じる。
さらに、$O(\sqrt{T}{\log{T}})$ random Fourier機能を統合することで、カーネル計算の複雑さを効果的に最小化する。
実世界のデータセットによるいくつかの実験は、提案手法がオフラインおよびオンラインシナリオでカーネルと線形アルゴリズムより優れていることを示している。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳(メタデータ) (2024-09-07T06:37:23Z) - Variance Reduced Online Gradient Descent for Kernelized Pairwise
Learning with Limited Memory [19.822215548822882]
オンラインのペアワイズ学習を扱うために、オンライン勾配降下アルゴリズム(OGD)が提案されている。
OGDアルゴリズムの最近の進歩は、オンライン勾配の計算の複雑さを減らし、O(T)$未満の複雑さを達成し、たとえ$O(1)$であるとしても達成することを目的としている。
本研究では,カーネルのオンラインペアワイズ学習に拡張し,サブ線形後悔を改善したメモリOGDアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-10-10T09:50:54Z) - Ordering for Non-Replacement SGD [7.11967773739707]
我々は,アルゴリズムの非置換形式に対する収束率を改善する順序付けを求める。
我々は,強い凸関数と凸関数のステップサイズを一定かつ小さくするための最適順序付けを開発する。
さらに、注文とミニバッチを組み合わせることで、より複雑なニューラルネットワークにも適用できます。
論文 参考訳(メタデータ) (2023-06-28T00:46:58Z) - Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。
我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。
RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
論文 参考訳(メタデータ) (2022-10-21T15:56:13Z) - Pairwise Learning via Stagewise Training in Proximal Setting [0.0]
非平滑凸対損失関数の収束保証と、適応的なサンプルサイズとペアワイズ学習のための重要サンプリング手法を組み合わせる。
それぞれに逆のインスタンスをサンプリングすると勾配の分散が減少し、収束が加速することを示した。
論文 参考訳(メタデータ) (2022-08-08T11:51:01Z) - Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise
Learning [65.54757265434465]
ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。
オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。
本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
論文 参考訳(メタデータ) (2021-11-23T18:10:48Z) - Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via
GDPA Linearization [59.87663954467815]
アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。
本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。
実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
論文 参考訳(メタデータ) (2021-09-10T07:01:15Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳(メタデータ) (2020-11-09T18:32:22Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳(メタデータ) (2020-08-23T20:36:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。