Fugu-MT 論文翻訳(概要): Primal Dual Alternating Proximal Gradient Algorithms for Nonsmooth Nonconvex Minimax Problems with Coupled Linear Constraints

論文の概要: Primal Dual Alternating Proximal Gradient Algorithms for Nonsmooth Nonconvex Minimax Problems with Coupled Linear Constraints

arxiv url: http://arxiv.org/abs/2212.04672v1
Date: Fri, 9 Dec 2022 05:32:30 GMT
ステータス: 翻訳完了
システム内更新日: 2022-12-12 14:46:00.136260
Title: Primal Dual Alternating Proximal Gradient Algorithms for Nonsmooth Nonconvex Minimax Problems with Coupled Linear Constraints
Title（参考訳）: 結合線形制約を持つ非滑らかな非凸ミニマックス問題に対する原始双対交互近勾配アルゴリズム
Authors: Huiling Zhang, Junlin Wang, Zi Xu, Yu-Hong Dai
Abstract要約: 本稿では,DAPGアルゴリズムと非線形最小制約アルゴリズムを提案する。対応する複雑性は$calOleftであることが証明されている。我々の知る限り、これらは2つのミニマックス問題を解くための最初の2つのアルゴリズムである。
参考スコア（独自算出の注目度）: 3.871148938060281
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Nonconvex minimax problems have attracted wide attention in machine learning, signal processing and many other fields in recent years. In this paper, we propose a primal dual alternating proximal gradient (PDAPG) algorithm and a primal dual proximal gradient (PDPG-L) algorithm for solving nonsmooth nonconvex-strongly concave and nonconvex-linear minimax problems with coupled linear constraints, respectively. The corresponding iteration complexity of the two algorithms are proved to be $\mathcal{O}\left( \varepsilon ^{-2} \right)$ and $\mathcal{O}\left( \varepsilon ^{-3} \right)$ to reach an $\varepsilon$-stationary point, respectively. To our knowledge, they are the first two algorithms with iteration complexity guarantee for solving the two classes of minimax problems.
Abstract（参考訳）: 非凸ミニマックス問題は近年、機械学習、信号処理など多くの分野で注目されている。本稿では,非滑らかな非凸強凸および非凸線形ミニマックス問題を解くためのpdapg(primal dual alternating proximal gradient)アルゴリズムとpdpg-l(primal dual proximal gradient)アルゴリズムを提案する。 2つのアルゴリズムの対応する反復複雑性は、それぞれ$\mathcal{O}\left( \varepsilon ^{-2} \right)$と$\mathcal{O}\left( \varepsilon ^{-3} \right)$であると証明される。我々の知る限り、これらはミニマックス問題の2つのクラスを解くために、反復複雑性を保証する最初の2つのアルゴリズムである。

関連論文リスト

Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization [64.99236464953032]
我々は、(ほぼ)$レベルのKKTソリューションを見つけるために、$O(/epsilon)$の最先端の複雑さを新たに提案する。 O(/epsilon)$ の(ほぼ) $ レベルの KKT ソリューションを見つけるための技術的複雑さを適用することで、(ほぼ) $ レベルの KKT ソリューションを見つけるための $O(/epsilon)$ の最先端の複雑さを新たに達成する。
論文参考訳（メタデータ） (2025-06-03T06:31:59Z)
Stochastic Compositional Minimax Optimization with Provable Convergence Guarantees [14.301500851291989]
合成ミニマックス問題は、機械学習において存在するが、このクラスの問題の収束に関してのみ確立されている。本稿では,ミニマックス損失を合成構造で最適化するミニマックス問題の形式的定義を提案する。
論文参考訳（メタデータ） (2024-08-22T16:00:31Z)
Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文参考訳（メタデータ） (2024-08-21T20:14:54Z)
Zeroth-Order primal-dual Alternating Projection Gradient Algorithms for Nonconvex Minimax Problems with Coupled linear Constraints [3.898056433020865]
線形制約付きミニマックス問題に対する2つのゼロ階正則複雑性アルゴリズムを提案する。我々の知る限りでは、彼らは最初の2つのゼロオーダーのアルゴリズムであり、非局所的な複雑さに最適である。
論文参考訳（メタデータ） (2024-01-26T11:22:13Z)
An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problems [0.4910937238451484]
我々は、非凹小問題の解法として、正規化モーメント降下アルゴリズム(FORMDA)を高速化する。有界アルゴリズムの最大の複雑さは、客観性関数の停止下での非可逆ミニマックス問題の解法である。
論文参考訳（メタデータ） (2023-10-24T01:45:11Z)
Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。本稿では,2種類のミニマックスアルゴリズムを提案する。そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文参考訳（メタデータ） (2023-02-08T01:42:45Z)
A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文参考訳（メタデータ） (2023-01-10T20:43:29Z)
HSVI can solve zero-sum Partially Observable Stochastic Games [7.293053431456775]
2-player 0-sum不完全なゲームを解くための最先端の手法は、線形プログラミングや動的後悔の最小化に依存している。本稿では,線形プログラミングや反復的手法に依存した手法を補完する,有望なアプローチの新たなファミリーを提案する。
論文参考訳（メタデータ） (2022-10-26T11:41:57Z)
Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysis [23.80683445944524]
PLDAの新たな解析手法を導入し,その鍵となるのは,新たに開発された非滑らかかつ二重なエラー反復である。 PLDA が $thetain [0,12]$ のとき、緩やかな仮定の下で最適な $mathcalO()$ を達成する。
論文参考訳（メタデータ） (2022-09-22T07:12:48Z)
Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
論文参考訳（メタデータ） (2022-06-17T12:58:58Z)
Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文参考訳（メタデータ） (2021-10-20T02:57:21Z)
Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problems [9.173866646584031]
本稿では,非滑らかなゼロ次ミニマックス問題に対するアルゴリズムを提案する。また,非コンケーブミニマックス問題に対処できることを示す。
論文参考訳（メタデータ） (2021-08-01T15:23:49Z)
Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文参考訳（メタデータ） (2021-06-02T22:03:36Z)
Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
定常点に収束する一般化外空間を提案する。このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
論文参考訳（メタデータ） (2020-10-31T21:35:42Z)
A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems [33.83671897619922]
非con-max問題は、このロバストな問題を解決するために、ポイントワイズな非函数の集合を最小化するなど、多くのアプリケーションで発生する。 A.A.アルゴリズムは、有限個の非函数の集合に対して$(/A-O-)の$(/A-O-)を達成できる。
論文参考訳（メタデータ） (2020-10-29T17:13:46Z)
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)
On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
論文参考訳（メタデータ） (2019-06-02T03:03:45Z)

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