論文の概要: 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反復を解析する。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - Robust Approximation Algorithms for Non-monotone $k$-Submodular
Maximization under a Knapsack Constraint [0.0]
2つの決定論的近似アルゴリズムは、knapsack制約の下での非単調な$k$-部分モジュラー複雑性の問題に対して提案される。
提案アルゴリズムは,非単調な目的に対して,O(nk)$クエリの計算量内で一定の近似比を提供する。
論文 参考訳(メタデータ) (2023-09-21T12:42:52Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳(メタデータ) (2023-06-30T08:34:29Z) - 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) - An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum
Optimization [25.21457349137344]
私たちは、DEARESTが少なくとも$mathcal O(+sqrtmnLvarepsilon-2)$ 1次オラクル(IFO)コールと$mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$通信ラウンドを必要とすることを示す証拠を示します。
論文 参考訳(メタデータ) (2022-10-25T11:37:11Z) - 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) - Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax
Optimization [47.27237492375659]
双線型結合されたミニマックス問題:$min_x max_y f(x) + ytop A x - h(y)$, ここでは$f$と$h$はどちらも強凸滑らかな関数である。
Omega(sqrtfracL_xmu_x + frac|A|sqrtmu_x,mu_y) log(frac1vareps) の低い複雑性境界を達成した1次アルゴリズムは知られていない。
論文 参考訳(メタデータ) (2022-01-19T05:56:19Z) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳(メタデータ) (2020-06-24T04:41:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。