論文の概要: Variance Reduced Online Gradient Descent for Kernelized Pairwise
Learning with Limited Memory
- arxiv url: http://arxiv.org/abs/2310.06483v1
- Date: Tue, 10 Oct 2023 09:50:54 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-11 16:06:21.496605
- Title: Variance Reduced Online Gradient Descent for Kernelized Pairwise
Learning with Limited Memory
- Title（参考訳）: メモリ制限付きカーネル化ペアワイズ学習におけるオンライン勾配のばらつき低減
- Authors: Hilal AlQuabeh, Bhaskar Mukhoty, Bin Gu
- Abstract要約: オンラインのペアワイズ学習を扱うために、オンライン勾配降下アルゴリズム(OGD)が提案されている。
OGDアルゴリズムの最近の進歩は、オンライン勾配の計算の複雑さを減らし、O(T)$未満の複雑さを達成し、たとえ$O(1)$であるとしても達成することを目的としている。
本研究では,カーネルのオンラインペアワイズ学習に拡張し,サブ線形後悔を改善したメモリOGDアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 19.822215548822882
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Pairwise learning is essential in machine learning, especially for problems
involving loss functions defined on pairs of training examples. Online gradient
descent (OGD) algorithms have been proposed to handle online pairwise learning,
where data arrives sequentially. However, the pairwise nature of the problem
makes scalability challenging, as the gradient computation for a new sample
involves all past samples. Recent advancements in OGD algorithms have aimed to
reduce the complexity of calculating online gradients, achieving complexities
less than $O(T)$ and even as low as $O(1)$. However, these approaches are
primarily limited to linear models and have induced variance. In this study, we
propose a limited memory OGD algorithm that extends to kernel online pairwise
learning while improving the sublinear regret. Specifically, we establish a
clear connection between the variance of online gradients and the regret, and
construct online gradients using the most recent stratified samples with a
limited buffer of size of $s$ representing all past data, which have a
complexity of $O(sT)$ and employs $O(\sqrt{T}\log{T})$ random Fourier features
for kernel approximation. Importantly, our theoretical results demonstrate that
the variance-reduced online gradients lead to an improved sublinear regret
bound. The experiments on real-world datasets demonstrate the superiority of
our algorithm over both kernelized and linear online pairwise learning
algorithms.
- Abstract（参考訳）: ペアワイズ学習は、特にトレーニング例のペアで定義された損失関数に関わる問題において、機械学習において不可欠である。
オンライン勾配降下(ogd)アルゴリズムは、データが順次到着するオンラインペアワイズ学習を処理するために提案されている。
しかし,新しいサンプルの勾配計算は過去のサンプルを全て含んでいるため,問題のペアワイズ性はスケーラビリティを困難にしている。
近年のogdアルゴリズムの進歩は、オンライン勾配の計算の複雑さを低減し、o(t)$以下、さらには$o(1)$という低い複雑さを達成することを目的としている。
しかし、これらのアプローチは主に線形モデルに制限され、分散を誘導する。
本研究では,カーネルのオンラインペアワイズ学習に拡張し,サブ線形後悔を改善したメモリOGDアルゴリズムを提案する。
具体的には、オンライン勾配のばらつきと後悔との明確な関係を確立し、過去データを表すバッファが制限された$s$を持つ最新の階層化サンプルを用いてオンライン勾配を構築し、その複雑さは$o(st)$であり、カーネル近似に$o(\sqrt{t}\log{t})$ランダムフーリエ機能を用いる。
重要なこととして、我々の理論的結果は、ばらつきによって引き起こされたオンライン勾配が、改良されたサブ線形後悔境界につながることを示している。
実世界のデータセットに関する実験は、カーネル化および線形オンラインペアワイズ学習アルゴリズムに対するアルゴリズムの優位性を示している。
関連論文リスト
- Limited Memory Online Gradient Descent for Kernelized Pairwise Learning
with Dynamic Averaging [18.843097436906618]
実例の独立性を必要としない軽量なOGDアルゴリズムを導入し、カーネル対学習に一般化する。
提案アルゴリズムは,ランダムな例と過去のデータを表す移動平均に基づいて勾配を構築し,その結果,O(T)$の複雑さに縛られたサブ線形後悔が生じる。
実世界のデータセットによるいくつかの実験では、複雑性技術がオフラインおよびオンラインシナリオでカーネルと線形勾配を上回ることが示されている。
論文 参考訳（メタデータ） (2024-02-02T05:21:50Z) - Efficient Methods for Non-stationary Online Learning [67.3300478545554]
本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。
本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
論文 参考訳（メタデータ） (2023-09-16T07:30:12Z) - Ordering for Non-Replacement SGD [7.11967773739707]
我々は,アルゴリズムの非置換形式に対する収束率を改善する順序付けを求める。
我々は,強い凸関数と凸関数のステップサイズを一定かつ小さくするための最適順序付けを開発する。
さらに、注文とミニバッチを組み合わせることで、より複雑なニューラルネットワークにも適用できます。
論文 参考訳（メタデータ） (2023-06-28T00:46:58Z) - Pairwise Learning via Stagewise Training in Proximal Setting [0.0]
非平滑凸対損失関数の収束保証と、適応的なサンプルサイズとペアワイズ学習のための重要サンプリング手法を組み合わせる。
それぞれに逆のインスタンスをサンプリングすると勾配の分散が減少し、収束が加速することを示した。
論文 参考訳（メタデータ） (2022-08-08T11:51:01Z) - One-Pass Learning via Bridging Orthogonal Gradient Descent and Recursive
Least-Squares [8.443742714362521]
我々は,従来のデータポイントの予測にほとんど変化しない方向にパラメータを変更しながら,すべての新しいデータポイントに完全に適合するワンパス学習アルゴリズムを開発した。
我々のアルゴリズムは、インクリメンタル・プリンシパル・コンポーネント分析(IPCA)を用いてストリーミングデータの構造を利用して、メモリを効率的に利用する。
本実験では,提案手法の有効性をベースラインと比較した。
論文 参考訳（メタデータ） (2022-07-28T02:01:31Z) - Implicit Parameter-free Online Learning with Truncated Linear Models [51.71216912089413]
パラメータフリーアルゴリズムは、設定された学習率を必要としないオンライン学習アルゴリズムである。
そこで我々は,「単純」なフレーバーを持つ新しい更新によって,切り離された線形モデルを活用できる新しいパラメータフリーアルゴリズムを提案する。
後悔の新たな分解に基づいて、新しい更新は効率的で、各ステップで1つの勾配しか必要とせず、切り捨てられたモデルの最小値をオーバーシュートすることはない。
論文 参考訳（メタデータ） (2022-03-19T13:39:49Z) - Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise
Learning [65.54757265434465]
ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。
オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。
本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
論文 参考訳（メタデータ） (2021-11-23T18:10:48Z) - Cogradient Descent for Dependable Learning [64.02052988844301]
双線形最適化問題に対処するために,CoGDアルゴリズムに基づく信頼度の高い学習法を提案する。
CoGDは、ある変数がスパーシティ制約を持つ場合の双線形問題を解くために導入された。
また、特徴と重みの関連を分解するためにも使用できるため、畳み込みニューラルネットワーク(CNN)をより良く訓練するための我々の手法をさらに一般化することができる。
論文 参考訳（メタデータ） (2021-06-20T04:28:20Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Cogradient Descent for Bilinear Optimization [124.45816011848096]
双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。
一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。
本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
論文 参考訳（メタデータ） (2020-06-16T13:41:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。