論文の概要: Solving stochastic weak Minty variational inequalities without increasing batch size

• arxiv url: http://arxiv.org/abs/2302.09029v1
• Date: Fri, 17 Feb 2023 17:56:26 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-20 13:59:00.710411
• Title: Solving stochastic weak Minty variational inequalities without increasing batch size
• Title（参考訳）: バッチサイズの増加を伴わない確率弱ミンティ変分不等式の解法
• Authors: Thomas Pethick, Olivier Fercoq, Puya Latafat, Panagiotis Patrinos, Volkan Cevher
• Abstract要約: 本稿では,非コンケーブ問題のクラスを対象とした,段階外型アルゴリズムのファミリを紹介する。 固定されたステップサイズを1つ維持することは可能であるが、減少していると考えられる2番目のステップサイズに過ぎず、単調な設定でも興味深いことが示される。
• 参考スコア（独自算出の注目度）: 46.71914490521821
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper introduces a family of stochastic extragradient-type algorithms for a class of nonconvex-nonconcave problems characterized by the weak Minty variational inequality (MVI). Unlike existing results on extragradient methods in the monotone setting, employing diminishing stepsizes is no longer possible in the weak MVI setting. This has led to approaches such as increasing batch sizes per iteration which can however be prohibitively expensive. In contrast, our proposed methods involves two stepsizes and only requires one additional oracle evaluation per iteration. We show that it is possible to keep one fixed stepsize while it is only the second stepsize that is taken to be diminishing, making it interesting even in the monotone setting. Almost sure convergence is established and we provide a unified analysis for this family of schemes which contains a nonlinear generalization of the celebrated primal dual hybrid gradient algorithm.
• Abstract（参考訳）: 本稿では,弱いMinty変分不等式(MVI)を特徴とする非凸非凹問題に対して,確率的外向きアルゴリズムの一群を紹介する。 モノトンセッティングにおける既存の段階的手法とは異なり、弱MVIセッティングでは段差の減少はもはや不可能である。 このことが、1イテレーションあたりのバッチサイズを増加させるといったアプローチにつながった。 対照的に,提案手法には2段階のステップがあり,反復ごとに1つの付加的なオラクル評価が必要である。 固定されたステップサイズを1つ維持することは可能であるが、減少していると考えられる第2ステップサイズのみであり、単調な設定でも興味深い。 ほぼ確実に収束が確立され、祝福された原始双対ハイブリッド勾配アルゴリズムの非線形一般化を含む一連のスキームについて統一的な解析を行う。

関連論文リスト

• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
  本稿では,一階変分法の理論解析のための統一的アプローチを提案する。 提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。 凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
  論文  参考訳（メタデータ） (2023-05-25T11:11:31Z)
• Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions [21.681130192954583]
  シングルコール・エクストラグラディエント法は、大規模なmin-max最適化問題を解くための最も効率的なアルゴリズムの1つである。 i)準強単調問題(強単調問題の一般化)と(ii)弱ミンティ変分不等式(単調とミニティVIPの一般化)の2つのクラスに対して収束保証を提供する。 我々の収束分析は、重要なサンプリングと様々なミニバッチ戦略を特別な場合として含む任意のサンプリングパラダイムの下で成り立っている。
  論文  参考訳（メタデータ） (2023-02-27T18:53:28Z)
• SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variance [33.593203156666746]
  本稿では,AdaGradが一階最適化のための適応(自己調整)手法を段階化することを示す。 低ノイズと高レジの両方で、低ノイズと高レジの両方で急激な収束率を見出す。
  論文  参考訳（メタデータ） (2023-02-17T09:46:08Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Beyond the Golden Ratio for Variational Inequality Algorithms [12.470097382737933]
  我々は,モノトーン変分不等式 (VI) と凸凹 min-max 問題の解法である $textitgolden ratio algorithm$ の理解を改善した。 我々は,黄金比アルゴリズムと文献における既存のアルゴリズムとの橋渡しを完了するために,より大きなステップサイズを使用することのできる新しい分析手法を提案する。
  論文  参考訳（メタデータ） (2022-12-28T16:58:48Z)
• Tight Last-Iterate Convergence of the Extragradient Method for Constrained Monotone Variational Inequalities [4.6193503399184275]
  制約付きモノトンおよびリプシッツの変分不等式について, 過次法の最終点収束率を示す。 我々は,2乗法プログラミングのパワーと,指数関数法更新規則の低次元性を組み合わせた新しい手法を開発した。
  論文  参考訳（メタデータ） (2022-04-20T05:12:11Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)
• Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling [34.35013145885164]
  機械学習における大規模サドルポイント問題の解法としては、段階的な手法が必須となっている。 本稿では, 単純な双線形モデルであっても, 勾配によるバニラの過度な走行は収束を阻害する可能性があることを示す。 この修正により勾配にも収束でき、誤差境界条件下での鋭い収束率を導出できることを示す。
  論文  参考訳（メタデータ） (2020-03-23T10:24:27Z)

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

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