論文の概要: Greedy Adversarial Equilibrium: An Efficient Alternative to
Nonconvex-Nonconcave Min-Max Optimization
- arxiv url: http://arxiv.org/abs/2006.12363v4
- Date: Tue, 4 May 2021 16:41:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-18 06:06:26.467822
- Title: Greedy Adversarial Equilibrium: An Efficient Alternative to
Nonconvex-Nonconcave Min-Max Optimization
- Title（参考訳）: 欲望の逆均衡:非凸非凸min-max最適化の効率的な代替法
- Authors: Oren Mangoubi and Nisheeth K. Vishnoi
- Abstract要約: リプシッツの$varepsilon$-greedy逆数モデルは任意の出発点から$max_z f(x, z)$に収束することを示す。
また、リプシッツの$nabla_y f(x,y)$が$d$, $1/varepsilon$であり、$nabla2_y f(x,y)$上の境界は$nabla2_yであることを示す。
- 参考スコア（独自算出の注目度）: 28.431572772564518
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Min-max optimization of an objective function $f: \mathbb{R}^d \times
\mathbb{R}^d \rightarrow \mathbb{R}$ is an important model for robustness in an
adversarial setting, with applications to many areas including optimization,
economics, and deep learning. In many applications $f$ may be
nonconvex-nonconcave, and finding a global min-max point may be computationally
intractable. There is a long line of work that seeks computationally tractable
algorithms for alternatives to the min-max optimization model. However, many of
the alternative models have solution points which are only guaranteed to exist
under strong assumptions on $f$, such as convexity, monotonicity, or special
properties of the starting point. We propose an optimization model, the
$\varepsilon$-greedy adversarial equilibrium, and show that it can serve as a
computationally tractable alternative to the min-max optimization model.
Roughly, we say that a point $(x^\star, y^\star)$ is an $\varepsilon$-greedy
adversarial equilibrium if $y^\star$ is an $\varepsilon$-approximate local
maximum for $f(x^\star,\cdot)$, and $x^\star$ is an $\varepsilon$-approximate
local minimum for a "greedy approximation" to the function $\max_z f(x, z)$
which can be efficiently estimated using second-order optimization algorithms.
We prove the existence of such a point for any smooth function which is bounded
and has Lipschitz Hessian. To prove existence, we introduce an algorithm that
converges from any starting point to an $\varepsilon$-greedy adversarial
equilibrium in a number of evaluations of the function $f$, the max-player's
gradient $\nabla_y f(x,y)$, and its Hessian $\nabla^2_y f(x,y)$, that is
polynomial in the dimension $d$, $1/\varepsilon$, and the bounds on $f$ and its
Lipschitz constant.
- Abstract（参考訳）: 目的関数 $f: \mathbb{r}^d \times \mathbb{r}^d \rightarrow \mathbb{r}$ のmin-max最適化は、敵対的設定における堅牢性の重要なモデルであり、最適化、経済学、ディープラーニングなど多くの分野に適用できる。
多くのアプリケーションにおいて、$f$ は非凸非凸であり、大域的な min-max 点を見つけることは計算的に難解である。
min-max最適化モデルに代わる計算可能なアルゴリズムを求める長い作業の行がある。
しかし、代替モデルの多くは、凸性、単調性、始点の特殊性質など、$f$ の強い仮定の下でのみ存在することを保証された解点を持っている。
最適化モデルである$\varepsilon$-greedy adversarial equilibriumを提案し,min-max最適化モデルに代わる計算可能な代替として機能することを示す。
概して、ある点 $(x^\star, y^\star)$ が $\varepsilon$-greedy 対数平衡であるとは、$y^\star$ が $\varepsilon$-approximate local maximum for $f(x^\star,\cdot)$ と $x^\star$ が $\varepsilon$-approximate local minimum for a "greedy approximation" to the function $\max_z f(x, z)$ が 2次最適化アルゴリズムを用いて効率的に推定できる。
我々はそのような点の存在を、有界でリプシッツ・ヘッシアンを持つ任意の滑らかな函数に対して証明する。
実存を証明するために,任意の出発点から$f$, max-player's gradient $\nabla_y f(x,y)$, and its hessian $\nabla^2_y f(x,y)$,すなわち$d$, $1/\varepsilon$の多項式で,$f$とそのリプシッツ定数の多くの評価において,$\varepsilon$-greedyadversarial equilibriumに収束するアルゴリズムを導入する。
関連論文リスト
- An Optimal Algorithm for Strongly Convex Min-min Optimization [79.11017157526815]
既存の最適な一階法には$mathcalO(sqrtmaxkappa_x,kappa_y log 1/epsilon)$nabla_x f(x,y)$と$nabla_y f(x,y)$の両方の計算が必要である。
我々は$mathcalO(sqrtkappa_x log 1/epsilon)$nabla_x f(x,
論文 参考訳（メタデータ） (2022-12-29T19:26:12Z) - 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) - 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) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - The Complexity of Constrained Min-Max Optimization [29.57458485068705]
十分大きな局所点 min-max が存在することが保証されていることを示す。
さらに重要なこととして、近似的な固定勾配 Descent/Ascent 近似が完成することを示す。
この結果は、2つの基本的な最適化問題の指数関数近似を初めて示したものである。
論文 参考訳（メタデータ） (2020-09-21T05:54:12Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z) - Stochastic Recursive Gradient Descent Ascent for Stochastic
Nonconvex-Strongly-Concave Minimax Problems [36.645753881826955]
本稿では,分散を利用してより効率的に推定できるRecurEnti Ascent(SREDA)という新しい手法を提案する。
この方法はこの問題でよく知られている。
論文 参考訳（メタデータ） (2020-01-11T09:05:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。