論文の概要: The Complexity of Constrained Min-Max Optimization
- arxiv url: http://arxiv.org/abs/2009.09623v1
- Date: Mon, 21 Sep 2020 05:54:12 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-16 05:52:35.688376
- Title: The Complexity of Constrained Min-Max Optimization
- Title（参考訳）: 制約付きMin-Max最適化の複雑さ
- Authors: Constantinos Daskalakis and Stratis Skoulakis and Manolis Zampetakis
- Abstract要約: 十分大きな局所点 min-max が存在することが保証されていることを示す。
さらに重要なこととして、近似的な固定勾配 Descent/Ascent 近似が完成することを示す。
この結果は、2つの基本的な最適化問題の指数関数近似を初めて示したものである。
- 参考スコア（独自算出の注目度）: 29.57458485068705
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Despite its important applications in Machine Learning, min-max optimization
of nonconvex-nonconcave objectives remains elusive. Not only are there no known
first-order methods converging even to approximate local min-max points, but
the computational complexity of identifying them is also poorly understood. In
this paper, we provide a characterization of the computational complexity of
the problem, as well as of the limitations of first-order methods in
constrained min-max optimization problems with nonconvex-nonconcave objectives
and linear constraints.
As a warm-up, we show that, even when the objective is a Lipschitz and smooth
differentiable function, deciding whether a min-max point exists, in fact even
deciding whether an approximate min-max point exists, is NP-hard. More
importantly, we show that an approximate local min-max point of large enough
approximation is guaranteed to exist, but finding one such point is
PPAD-complete. The same is true of computing an approximate fixed point of
Gradient Descent/Ascent.
An important byproduct of our proof is to establish an unconditional hardness
result in the Nemirovsky-Yudin model. We show that, given oracle access to some
function $f : P \to [-1, 1]$ and its gradient $\nabla f$, where $P \subseteq
[0, 1]^d$ is a known convex polytope, every algorithm that finds a
$\varepsilon$-approximate local min-max point needs to make a number of queries
that is exponential in at least one of $1/\varepsilon$, $L$, $G$, or $d$, where
$L$ and $G$ are respectively the smoothness and Lipschitzness of $f$ and $d$ is
the dimension. This comes in sharp contrast to minimization problems, where
finding approximate local minima in the same setting can be done with Projected
Gradient Descent using $O(L/\varepsilon)$ many queries. Our result is the first
to show an exponential separation between these two fundamental optimization
problems.
- Abstract（参考訳）: 機械学習における重要な応用にもかかわらず、非凸非凹面目標のmin-max最適化はいまだ解明されていない。
局所的なmin-max点にさえ収束する既知の一階法が存在しないだけでなく、それらを特定する計算の複雑さもよく分かっていない。
本稿では,非凸非凸目的と線形制約を伴う制約付きmin-max最適化問題において,問題の計算複雑性と一階法の限界について考察する。
ウォームアップとして、目標がリプシッツで滑らかな微分可能関数であっても、min-max点が存在するかどうかを判断し、実際に近似min-max点が存在するかどうかを判断してもnp-hardであることを示す。
さらに重要なことは、近似が十分大きい局所的なmin-max点の存在が保証されるが、そのような点を見つけることはPPAD完全である。
勾配降下/上昇の近似不動点を計算する場合も同様である。
我々の証明の重要な副産物は、ネミロフスキー・ユーディンモデルにおける無条件硬さの結果を確立することである。
関数 $f : P \to [-1, 1] とその勾配 $\nabla f$, where $P \subseteq [0, 1]^d$ is a known convex polytope, every algorithm that finds a $\varepsilon$-approximate local min-max point to a least one of $1/\varepsilon$, $L$, $G$, $d$, where $L$ and $G$ are each smoothness and Lipschitzness of $f$ and $d$ is the dimension。
これは最小化問題とは対照的で、同じ設定で近似局所極小を見つけることは、$o(l/\varepsilon)$多くのクエリを使って投影された勾配降下でできる。
この2つの基本最適化問題の間に指数関数的分離を初めて示した結果である。
関連論文リスト
- Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。
我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文 参考訳（メタデータ） (2024-08-21T20:14:54Z) - 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) - The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。
制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
論文 参考訳（メタデータ） (2023-10-13T14:52:46Z) - 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) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - 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) - Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization
Domain [11.562923882714093]
Y f(x,y) における max_y の $min_x 形式の最適化問題における近似一階定常点の探索問題について検討する。
我々のアプローチは、関数 $f(x,cdot)$ を $k 次テイラー近似($y$ で)に置き換え、ほぼ定常点を $Y$ で見つけることに依存する。
論文 参考訳（メタデータ） (2021-10-08T07:46:18Z) - Saddle Point Optimization with Approximate Minimization Oracle [8.680676599607125]
サドル点最適化に対する主要なアプローチである$min_xmax_y f(x, y)$は、GAN(Generative Adversarial Network)によって一般化される勾配に基づくアプローチである。
対照的に、最小化問題を解くオラクルのみに依存する代替手法を解析する。
我々のアプローチでは、近似解 $x'$ と $y'$ to $min_x'f(x', y)$ を与えられた点 $(x, y)$ に配置し、これらの近似解 $(x', y)$ に更新する。
論文 参考訳（メタデータ） (2021-03-29T23:03:24Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Greedy Adversarial Equilibrium: An Efficient Alternative to
Nonconvex-Nonconcave Min-Max Optimization [28.431572772564518]
リプシッツの$varepsilon$-greedy逆数モデルは任意の出発点から$max_z f(x, z)$に収束することを示す。
また、リプシッツの$nabla_y f(x,y)$が$d$, $1/varepsilon$であり、$nabla2_y f(x,y)$上の境界は$nabla2_yであることを示す。
論文 参考訳（メタデータ） (2020-06-22T16:03:41Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。