論文の概要: EMC$^2$: Efficient MCMC Negative Sampling for Contrastive Learning with Global Convergence
- arxiv url: http://arxiv.org/abs/2404.10575v1
- Date: Tue, 16 Apr 2024 13:53:58 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-17 16:34:29.965505
- Title: EMC$^2$: Efficient MCMC Negative Sampling for Contrastive Learning with Global Convergence
- Title（参考訳）: EMC$^2$:グローバル収束型コントラスト学習のための効率的なMCMC負サンプリング
- Authors: Chung-Yiu Yau, Hoi-To Wai, Parameswaran Raman, Soumajyoti Sarkar, Mingyi Hong,
- Abstract要約: 対照的学習における鍵となる課題は、正のサンプルと対照的に大きなサンプルセットから負のサンプルを生成することである。
コントラスト学習のための効率的なマルコフ連鎖モンテカルロ陰性サンプリング法(EMC$2$)を提案する。
EMC$2$は,バッチサイズの選択に関係なく,グローバル収束(定常性)を示す最初のアルゴリズムであることを示す。
- 参考スコア（独自算出の注目度）: 43.96096434967746
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A key challenge in contrastive learning is to generate negative samples from a large sample set to contrast with positive samples, for learning better encoding of the data. These negative samples often follow a softmax distribution which are dynamically updated during the training process. However, sampling from this distribution is non-trivial due to the high computational costs in computing the partition function. In this paper, we propose an Efficient Markov Chain Monte Carlo negative sampling method for Contrastive learning (EMC$^2$). We follow the global contrastive learning loss as introduced in SogCLR, and propose EMC$^2$ which utilizes an adaptive Metropolis-Hastings subroutine to generate hardness-aware negative samples in an online fashion during the optimization. We prove that EMC$^2$ finds an $\mathcal{O}(1/\sqrt{T})$-stationary point of the global contrastive loss in $T$ iterations. Compared to prior works, EMC$^2$ is the first algorithm that exhibits global convergence (to stationarity) regardless of the choice of batch size while exhibiting low computation and memory cost. Numerical experiments validate that EMC$^2$ is effective with small batch training and achieves comparable or better performance than baseline algorithms. We report the results for pre-training image encoders on STL-10 and Imagenet-100.
- Abstract（参考訳）: 対照的な学習における重要な課題は、データのより優れたエンコーディングを学ぶために、正のサンプルと対照的に、大きなサンプルセットから負のサンプルを生成することである。
これらの負のサンプルは、トレーニングプロセス中に動的に更新されるソフトマックス分布に従うことが多い。
しかし、この分布からのサンプリングは、分割関数の計算に高い計算コストがかかるため、簡単ではない。
本稿では,コントラスト学習のための効率的なマルコフ連鎖モンテカルロ陰性サンプリング法(EMC$^2$)を提案する。
本稿では, 適応型メトロポリス・ハスティングス・サブルーチンを利用するEMC$^2$を提案する。
EMC$^2$ が $\mathcal{O}(1/\sqrt{T})$-stationary point of the global contrastive loss in $T$ iterations であることを示す。
以前の研究と比較すると、EMC$^2$は、計算量やメモリコストを低く抑えながらバッチサイズの選択によらず、グローバル収束(定常性)を示す最初のアルゴリズムである。
数値実験により、EMC$^2$は小規模なバッチトレーニングで有効であることが検証され、ベースラインアルゴリズムよりも同等または優れた性能が得られる。
STL-10とImagenet-100の事前学習画像エンコーダについて報告する。
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Testable Learning with Distribution Shift [9.036777309376697]
分散シフトを伴うテスト可能学習と呼ばれる新しいモデルを定義する。
テスト分布上の分類器の性能を証明可能なアルゴリズムを得る。
ハーフスペースやハーフスペースの交点,決定木といった概念クラスを学ぶ上で,いくつかの肯定的な結果が得られる。
論文 参考訳（メタデータ） (2023-11-25T23:57:45Z) - Compressed Sensing: A Discrete Optimization Approach [5.877778007271621]
本稿では, 2次円錐緩和を強化し, 独自の分岐結合アルゴリズムを開発する半定緩和法を提案する。
マルチラベル分類アルゴリズムの構成要素として用いられる場合,提案手法は,ベンチマーク圧縮センシング法よりも高い分類精度を実現する。
論文 参考訳（メタデータ） (2023-06-05T01:29:24Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳（メタデータ） (2022-03-18T18:50:52Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳（メタデータ） (2021-10-09T21:13:48Z) - Tightening the Dependence on Horizon in the Sample Complexity of
Q-Learning [59.71676469100807]
この研究は、同期Q-ラーニングのサンプルの複雑さを、任意の$0varepsilon 1$に対して$frac|mathcalS| (1-gamma)4varepsilon2$の順序に絞る。
計算やストレージを余分に必要とせずに、高速なq-learningにマッチするvanilla q-learningの有効性を明らかにした。
論文 参考訳（メタデータ） (2021-02-12T14:22:05Z) - SCE: Scalable Network Embedding from Sparsest Cut [20.08464038805681]
大規模ネットワーク埋め込みは、教師なしの方法で各ノードの潜在表現を学習することである。
このような対照的な学習手法の成功の鍵は、正と負のサンプルを引き出す方法である。
本稿では, 負のサンプルのみを用いた教師なしネットワーク埋め込みのためのSCEを提案する。
論文 参考訳（メタデータ） (2020-06-30T03:18:15Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。