論文の概要: Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity
- arxiv url: http://arxiv.org/abs/2402.05071v2
- Date: Mon, 12 Aug 2024 23:43:59 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-14 22:55:00.571338
- Title: Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity
- Title（参考訳）: Min-Max問題に対する不正確な固定点反復の再検討:確率性と構造的非凸性
- Authors: Ahmet Alacaoglu, Donghwan Kim, Stephen J. Wright,
- Abstract要約: 1L 1$は、マルチレベルなCarloイテレーションであっても、最先端の問題を改善するために使用できることを示す。
解に関する唯一のホールドが新しい1L 1$理論である場合、不正確なハルパーネス推定器を1L 1$で解析する。
- 参考スコア（独自算出の注目度）: 18.427215139020632
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We focus on constrained, $L$-smooth, potentially stochastic and nonconvex-nonconcave min-max problems either satisfying $\rho$-cohypomonotonicity or admitting a solution to the $\rho$-weakly Minty Variational Inequality (MVI), where larger values of the parameter $\rho>0$ correspond to a greater degree of nonconvexity. These problem classes include examples in two player reinforcement learning, interaction dominant min-max problems, and certain synthetic test problems on which classical min-max algorithms fail. It has been conjectured that first-order methods can tolerate a value of $\rho$ no larger than $\frac{1}{L}$, but existing results in the literature have stagnated at the tighter requirement $\rho < \frac{1}{2L}$. With a simple argument, we obtain optimal or best-known complexity guarantees with cohypomonotonicity or weak MVI conditions for $\rho < \frac{1}{L}$. First main insight for the improvements in the convergence analyses is to harness the recently proposed $\textit{conic nonexpansiveness}$ property of operators. Second, we provide a refined analysis for inexact Halpern iteration that relaxes the required inexactness level to improve some state-of-the-art complexity results even for constrained stochastic convex-concave min-max problems. Third, we analyze a stochastic inexact Krasnosel'ski\u{\i}-Mann iteration with a multilevel Monte Carlo estimator when the assumptions only hold with respect to a solution.
- Abstract（参考訳）: 我々は、制約付き$L$-smooth、潜在的に確率的かつ非凸的 min-max 問題に、$\rho$-cohypomonotonicity を満たすか、$\rho$-weakly Minty Variational Inequality (MVI) に対する解を認めるかのいずれかに焦点を当てる。
これらの問題クラスには、2つのプレイヤー強化学習、相互作用支配的なmin-max問題、古典的なmin-maxアルゴリズムが失敗する特定の合成テスト問題が含まれる。
一階法は$\rho$より大きい$\frac{1}{L}$を許容できると推測されているが、文献の既存の結果はより厳密な要求$\rho < \frac{1}{2L}$で停滞している。
簡単な議論で、$\rho < \frac{1}{L}$ に対して、コハイモノニック性あるいは弱 MVI 条件で最適あるいは最もよく知られた複雑性を保証する。
収束解析の改善に関する第一の洞察は、最近提案された$\textit{conic nonexpansiveness}$ property of operatorである。
第二に, 制約付き確率凸凸 min-max 問題においても, 必要な不正確なレベルを緩和し, 技術的複雑性を改善する不正確なHalpern 反復に対する洗練された解析を行う。
第三に、仮定が解に関してのみ成り立つとき、マルチレベルモンテカルロ推定器を用いて確率的不変Krasnosel'ski\u{\i}-Mann反復を解析する。
関連論文リスト
- Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。
我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文 参考訳（メタデータ） (2024-08-21T20:14:54Z) - Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
1次アルゴリズムは、$varepsilon-stationary pointを見つけるのに少なくとも$mathcalO(varepsilonepsilon-4)$ complexityを必要とする。
本稿では,高効率な変動複雑性を生かした新しい運動量アルゴリズムを提案する。
本手法の有効性は実世界のデータセットを用いてロジスティック回帰を用いて検証する。
論文 参考訳（メタデータ） (2024-06-18T20:14:52Z) - Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions [41.43895948769255]
非滑らかな非漸近公正問題のクラスを$min_x[yin Yphi(x, y) - max_zin Zpsix(x, z)]$の形で示す。
本稿では,これらの問題を解く最初の方法であるエンベロープ近似勾配SMAGを提案する。
論文 参考訳（メタデータ） (2024-05-28T20:52:46Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises:
High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation [22.758674468435302]
重尾雑音系では、勾配と真の速度の差は有限の$p-thモーメントを持つと仮定される。
本稿では,重み付き雑音を用いた非平滑凸最適化の包括的解析を行う。
論文 参考訳（メタデータ） (2023-03-22T03:05:28Z) - Near-Optimal Non-Convex Stochastic Optimization under Generalized
Smoothness [21.865728815935665]
2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。
しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。
本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
論文 参考訳（メタデータ） (2023-02-13T00:22:28Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Higher-order methods for convex-concave min-max optimization and
monotone variational inequalities [7.645449711892907]
制約付き凸凹 min-max 問題に対する収束率の改善と高次滑らかな単調変分不等式を提供する。
p>2$の場合、ネミロフスキーの1階ミラープロキシ法の反復複雑性を改善する。
さらに、制約のない$p=2$ケースでアルゴリズム全体をインスタンス化する。
論文 参考訳（メタデータ） (2020-07-09T03:12:33Z) - Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max
Optimization [61.66927778694731]
エポッチ勾配降下法(エポッチ勾配降下法、Epoch-GD)は、2011年にHazan and Kaleによって提唱された。
Epoch-GDA が SCSC min-max 問題の双対性ギャップに対して$O (1/T) の最適レートを達成できることを示す最初の実験である。
論文 参考訳（メタデータ） (2020-02-13T02:16:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。