論文の概要: Two Completely Parameter-Free Alternating Gradient Projection Algorithms for Nonconvex-(strongly) Concave Minimax Problems
- arxiv url: http://arxiv.org/abs/2407.21372v1
- Date: Wed, 31 Jul 2024 06:54:24 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-01 18:32:01.742944
- Title: Two Completely Parameter-Free Alternating Gradient Projection Algorithms for Nonconvex-(strongly) Concave Minimax Problems
- Title(参考訳): 非凸(強い)凹極小問題に対する2つの完全パラメータ自由交互勾配射影アルゴリズム
- Authors: Junnan Yang, Huiling Zhang, Zi Xu,
- Abstract要約: そこで本研究では,スムーズな非(強い)ミニマックス問題を解くために,完全にパラメータフリーな反復アルゴリズムを提案する。
最小値問題に対するPF-AGPアルゴリズムを求める呼び出しの総数は、勾配呼び出しの総数より多いことを示す。
数値計算により提案したPF-AGPアルゴリズムが検証される。
- 参考スコア(独自算出の注目度): 1.141545154221656
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Due to their importance in various emerging applications, efficient algorithms for solving minimax problems have recently received increasing attention. However, many existing algorithms require prior knowledge of the problem parameters in order to achieve optimal iteration complexity. In this paper, we propose a completely parameter-free alternating gradient projection (PF-AGP) algorithm to solve the smooth nonconvex-(strongly) concave minimax problems using a backtracking strategy, which does not require prior knowledge of parameters such as the Lipschtiz constant $L$ or the strongly concave constant $\mu$. The PF-AGP algorithm utilizes a parameter-free gradient projection step to alternately update the outer and inner variables in each iteration. We show that the total number of gradient calls of the PF-AGP algorithm to obtain an $\varepsilon$-stationary point for nonconvex-strongly concave minimax problems is upper bounded by $\mathcal{O}\left( L\kappa^3\varepsilon^{-2} \right)$ where $\kappa$ is the condition number, while the total number of gradient calls to obtain an $\varepsilon$-stationary point for nonconvex-concave minimax problems is upper bounded by $\mathcal{O}\left( L^4\varepsilon^{-4} \right)$. As far as we know, this is the first completely parameter-free algorithm for solving nonconvex-strongly concave minimax problems, and it is also the completely parameter-free algorithm which achieves the best iteration complexity in single loop method for solving nonconvex-concave minimax problems. Numerical results validate the efficiency of the proposed PF-AGP algorithm.
- Abstract(参考訳): 様々な新興アプリケーションにおいて重要であるため、ミニマックス問題を解くための効率的なアルゴリズムが近年注目されている。
しかし、多くの既存のアルゴリズムは、最適なイテレーションの複雑さを達成するために、問題パラメータの事前の知識を必要とする。
本稿では,リプシッチ定数$L$や強いコンケーブ定数$\mu$といったパラメータの事前知識を必要としないバックトラック戦略を用いて,スムーズな非凸(強)凹小マックス問題を解くために,完全にパラメータフリーな交互勾配射影(PF-AGP)アルゴリズムを提案する。
PF-AGPアルゴリズムはパラメータフリーの勾配投影ステップを使用して、各イテレーションの外側変数と内側変数を交互に更新する。
PF-AGPアルゴリズムの勾配呼び出しの総数は、非凸-強凸ミニマックス問題に対する$\varepsilon$-定常点を、$\mathcal{O}\left(L\kappa^3\varepsilon^{-2} \right)$で上界、$\kappa$を条件数とし、$\varepsilon$-定常点を非凸-凸ミニマックス問題に対する$\varepsilon$-定常点を、$\mathcal{O}\left(L^4\varepsilon^{-4} \right)$で上界とすることを示した。
われわれが知る限り、このアルゴリズムは非凸凸極小問題を解くための最初の完全パラメータフリーアルゴリズムであり、また、非凸凸極小問題を解くための単一ループ法において、最高の反復複雑性を達成する完全パラメータフリーのアルゴリズムでもある。
提案したPF-AGPアルゴリズムの有効性を数値計算により検証した。
関連論文リスト
- A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problems with Optimal Iteration Complexity [2.815239177328595]
凸凹極小最適化問題の解法として,Lipschitz-free Cubal regularization (LF-CR)アルゴリズムを提案する。
また,この問題のパラメータを必要としない完全パラメータフリー立方正則化(FF-CR)アルゴリズムを提案する。
我々の知る限り、FF-CRアルゴリズムは凸凹極小最適化問題の解法として初めて完全にパラメータフリーな2次アルゴリズムである。
論文 参考訳(メタデータ) (2024-07-04T01:46:07Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - A Newton-CG based barrier-augmented Lagrangian method for general
nonconvex conic optimization [77.8485863487028]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳(メタデータ) (2023-01-10T20:43:29Z) - Primal Dual Alternating Proximal Gradient Algorithms for Nonsmooth Nonconvex Minimax Problems with Coupled Linear Constraints [4.70696854954921]
非近位ミニマックス問題は近年、機械学習、信号処理など多くの分野に注目が集まっている。
そこで本稿では,非平滑な非畳み込みミニマックス問題の解法としてDAPアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-12-09T05:32:30Z) - The First Optimal Algorithm for Smooth and
Strongly-Convex-Strongly-Concave Minimax Optimization [88.91190483500932]
本稿では,スムーズで強靭なミニマックス最適化問題を再考する。
既存の最先端メソッドは、下限の$Omegaleft(sqrtkappa_xkappa_ylog3 (kappa_xkappa_y)logfrac1epsilonright)$にマッチしない。
我々は、$mathcalOleft( sqrtkappa_xkappa_ylog)で最初のアルゴリズムを提供することで、この根本的な問題を解決する。
論文 参考訳(メタデータ) (2022-05-11T17:33:07Z) - Derivative-free Alternating Projection Algorithms for General
Nonconvex-Concave Minimax Problems [9.173866646584031]
本稿では,非滑らかなゼロ次ミニマックス問題に対するアルゴリズムを提案する。
また,非コンケーブミニマックス問題に対処できることを示す。
論文 参考訳(メタデータ) (2021-08-01T15:23:49Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳(メタデータ) (2020-07-10T05:20:02Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳(メタデータ) (2020-06-16T17:55:46Z) - A Unified Single-loop Alternating Gradient Projection Algorithm for
Nonconvex-Concave and Convex-Nonconcave Minimax Problems [8.797831153231664]
提案手法は,理論上の一般凸目標保証を用いた最小値問題の解法である。
提案アルゴリズムは,ノンカベエプシロン・コンケーブ(強)と(強)コンベックス・ノン・コンケーブ(強)のミニマックス問題を解くために利用できることを示す。
論文 参考訳(メタデータ) (2020-06-03T04:00:52Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳(メタデータ) (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。