論文の概要: Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimization

• arxiv url: http://arxiv.org/abs/2206.02953v1
• Date: Tue, 7 Jun 2022 00:37:37 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-09 05:54:27.118889
• Title: Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimization
• Title（参考訳）: 置換のないサンプリングは有限サム最小値最適化の高速化につながる
• Authors: Aniket Das, Bernhard Sch\"olkopf, Michael Muehlebach
• Abstract要約: 滑らかな有限サム最小値最適化のための勾配アルゴリズムの収束速度を解析する。 このようなアルゴリズムの多くは、置換のないサンプリングポイントが、置換したサンプリングよりも高速な収束をもたらすことを示している。
• 参考スコア（独自算出の注目度）: 12.794526174053134
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We analyze the convergence rates of stochastic gradient algorithms for smooth finite-sum minimax optimization and show that, for many such algorithms, sampling the data points without replacement leads to faster convergence compared to sampling with replacement. For the smooth and strongly convex-strongly concave setting, we consider gradient descent ascent and the proximal point method, and present a unified analysis of two popular without-replacement sampling strategies, namely Random Reshuffling (RR), which shuffles the data every epoch, and Single Shuffling or Shuffle Once (SO), which shuffles only at the beginning. We obtain tight convergence rates for RR and SO and demonstrate that these strategies lead to faster convergence than uniform sampling. Moving beyond convexity, we obtain similar results for smooth nonconvex-nonconcave objectives satisfying a two-sided Polyak-{\L}ojasiewicz inequality. Finally, we demonstrate that our techniques are general enough to analyze the effect of data-ordering attacks, where an adversary manipulates the order in which data points are supplied to the optimizer. Our analysis also recovers tight rates for the incremental gradient method, where the data points are not shuffled at all.
• Abstract（参考訳）: 本研究では,スムーズな有限サム最小値最適化のための確率勾配アルゴリズムの収束速度を解析し,多くのアルゴリズムにおいて,置換のないデータ点のサンプリングは,置換によるサンプリングよりも高速な収束をもたらすことを示す。 滑らかで強凸な凹面設定では、勾配勾配の上昇と近点法を考慮し、各エポックごとにデータをシャッフルするRandom Reshuffling(RR)と、開始時にのみシャッフルするSingle Shuffling or Shuffle Once(SO)という2つの一般的な非置換サンプリング戦略を統一的に分析する。 rr等に対する密接な収束率を求め,この手法が一様サンプリングよりも高速に収束することを示す。 凸性を超えて、両面のPolyak-{\L}ojasiewicz不等式を満たす滑らかな非凸非凸目的に対して同様の結果が得られる。 最後に,提案手法はデータ順序付け攻撃の効果を解析するのに十分であり,敵がデータポイントをオプティマイザに供給する順序を操作できることを示す。 我々の分析は、データポイントが全くシャッフルされないインクリメンタル勾配法に対して、タイトなレートを回復する。

関連論文リスト

• Robust Stochastic Optimization via Gradient Quantile Clipping [6.2844649973308835]
  グラディエントDescent(SGD)のための量子クリッピング戦略を導入する。 通常のクリッピングチェーンとして、グラデーション・ニュー・アウトリージを使用します。 本稿では,Huberiles を用いたアルゴリズムの実装を提案する。
  論文  参考訳（メタデータ） (2023-09-29T15:24:48Z)
• Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Data [7.513100214864646]
  収束$tildeO(t-1/4)$とMoreautildeO(vareps-4)$がスムーズな非最適化のために最悪の場合の複雑性を示す。 適応的なステップサイズと最適収束度を持つ投影勾配法に基づく従属データに対する最初のオンライン非負行列分解アルゴリズムを得る。
  論文  参考訳（メタデータ） (2022-03-29T17:59:10Z)
• Nesterov Accelerated Shuffling Gradient Method for Convex Optimization [15.908060383231371]
  このアルゴリズムは,統一シャッフル方式を用いて,$mathcalO (1/T)$の改善率を示す。 我々の収束解析は有界領域や有界勾配条件に関する仮定を必要としない。 数値シミュレーションはアルゴリズムの効率を実証する。
  論文  参考訳（メタデータ） (2022-02-07T21:23:17Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。 ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。 我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
  論文  参考訳（メタデータ） (2021-10-20T02:25:25Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。 2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
  論文  参考訳（メタデータ） (2021-06-29T09:48:46Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• SGD with shuffling: optimal rates without component convexity and large epoch requirements [60.65928290219793]
  我々はRandomShuffle(各エポックの開始時のシャッフル)とSingleShuffle(1回だけシャッフル)を考える。 我々はこれらのアルゴリズムの最小収束速度をポリログ係数ギャップまで確立する。 我々は、すべての先行芸術に共通する欠点を取り除くことにより、RandomShuffleの厳密な収束結果をさらに強化する。
  論文  参考訳（メタデータ） (2020-06-12T05:00:44Z)

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

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