論文の概要: Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization
Domain
- arxiv url: http://arxiv.org/abs/2110.03950v1
- Date: Fri, 8 Oct 2021 07:46:18 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-11 22:51:14.896966
- Title: Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization
Domain
- Title（参考訳）: 最小化領域を持つ非凸非凸最小値最適化
- Authors: Dmitrii M. Ostrovskii, Babak Barazandeh, Meisam Razaviyayn
- Abstract要約: Y f(x,y) における max_y の $min_x 形式の最適化問題における近似一階定常点の探索問題について検討する。
我々のアプローチは、関数 $f(x,cdot)$ を $k 次テイラー近似($y$ で)に置き換え、ほぼ定常点を $Y$ で見つけることに依存する。
- 参考スコア（独自算出の注目度）: 11.562923882714093
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of finding approximate first-order stationary points in
optimization problems of the form $\min_{x \in X} \max_{y \in Y} f(x,y)$, where
the sets $X,Y$ are convex and $Y$ is compact. The objective function $f$ is
smooth, but assumed neither convex in $x$ nor concave in $y$. Our approach
relies upon replacing the function $f(x,\cdot)$ with its $k$th order Taylor
approximation (in $y$) and finding a near-stationary point in the resulting
surrogate problem. To guarantee its success, we establish the following result:
let the Euclidean diameter of $Y$ be small in terms of the target accuracy
$\varepsilon$, namely $O(\varepsilon^{\frac{2}{k+1}})$ for $k \in \mathbb{N}$
and $O(\varepsilon)$ for $k = 0$, with the constant factors controlled by
certain regularity parameters of $f$; then any $\varepsilon$-stationary point
in the surrogate problem remains $O(\varepsilon)$-stationary for the initial
problem. Moreover, we show that these upper bounds are nearly optimal: the
aforementioned reduction provably fails when the diameter of $Y$ is larger. For
$0 \le k \le 2$ the surrogate function can be efficiently maximized in $y$; our
general approximation result then leads to efficient algorithms for finding a
near-stationary point in nonconvex-nonconcave min-max problems, for which we
also provide convergence guarantees.
- Abstract（参考訳）: 我々は、集合 $X,Y$ が凸であり、$Y$ がコンパクトであるような形式 $\min_{x \in X} \max_{y \in Y} f(x,y)$ の最適化問題において、近似的な一階定常点を求める問題を研究する。
目的関数 $f$ は滑らかであるが、convex は $x$、concave は $y$ と仮定していない。
我々のアプローチは、関数 $f(x,\cdot)$ を $k$ のテイラー近似 ($y$) に置き換えることと、結果の代理問題におけるほぼ定常点を見つけることに依存する。
その成功を保証するために、ユークリッド径の$Y$を目標精度の点で小さくする: $O(\varepsilon^{\frac{2}{k+1}})$ for $k \in \mathbb{N}$ and $O(\varepsilon)$ for $k = 0$, with the constant factors controlled by certain regularity parameters of $f$; then then any $\varepsilon$-stationary point in the surrogate problem have $O(\varepsilon)$-stationary for the initial problem。
さらに,これら上界はほぼ最適であり,y$ の直径が大きくなると,上述の還元は確実に失敗する。
0 \le k \le 2$ に対して、代理関数は$y$ で効率よく最大化することができ、その結果、非凸非凸 min-max 問題における準定常点を見つけるための効率的なアルゴリズムが導かれる。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。
制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
論文 参考訳（メタデータ） (2023-10-13T14:52:46Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Finding Second-Order Stationary Point for Nonconvex-Strongly-Concave
Minimax Problem [16.689304539024036]
本稿では,ミニマックス問題の2階定常点を求める非同相的挙動について考察する。
高次元問題に対して、降下とチェビシェフ展開による勾配の立方体部分確率を解く2階オラクルのコスト対費用について提案する。
論文 参考訳（メタデータ） (2021-10-10T14:54:23Z) - FPT Approximation for Socially Fair Clustering [0.38073142980733]
距離関数 $d(.,.)$ を持つ距離空間 $mathcalX$ において点の集合 $P$ が与えられる。
社会的に公正な$k$-median問題の目標は、すべてのグループに対する最大平均コストを最小限に抑える、セットの$CサブセットF$ of $k$センターを見つけることである。
本研究では、社会的に公正な$k$-medianと$k$-meansに対する$(5+varepsilon)$と$(33+varepsilon)$近似アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-12T11:53:18Z) - Locally Private $k$-Means Clustering with Constant Multiplicative
Approximation and Near-Optimal Additive Error [10.632986841188]
2つの新しいアルゴリズムで加算誤差の上と下の境界における$n$の指数のギャップを埋める。
局所的にプライベートな$k$-meansの問題を、定数係数乗算近似を持つ一定数のラウンドで解くことができる。
論文 参考訳（メタデータ） (2021-05-31T14:41:40Z) - 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) - 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) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。