論文の概要: Min-Max Optimization Requires Exponentially Many Queries
- arxiv url: http://arxiv.org/abs/2605.13806v1
- Date: Wed, 13 May 2026 17:34:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-14 23:30:28.207919
- Title: Min-Max Optimization Requires Exponentially Many Queries
- Title（参考訳）: Min-Max Optimizationは指数的に多くのクエリを必要とする
- Authors: Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Alexandros Hollender,
- Abstract要約: 非min-nonconcave 関数 $f$ $[0,1] のクエリ複雑性。
f$ へのクエリとその勾配点が 1 ord$ で指数関数的な点を成さなければならないことを示す。
- 参考スコア（独自算出の注目度）: 71.85811744604827
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the query complexity of min-max optimization of a nonconvex-nonconcave function $f$ over $[0,1]^d \times [0,1]^d$. We show that, given oracle access to $f$ and to its gradient $\nabla f$, any algorithm that finds an $\varepsilon$-approximate stationary point must make a number of queries that is exponential in $1/\varepsilon$ or $d$.
- Abstract（参考訳）: 非凸非凸関数 $f$ over $[0,1]^d \times [0,1]^d$ の min-max 最適化のクエリ複雑性について検討する。
オラクルが$f$と勾配$\nabla f$にアクセスすると、$\varepsilon$-approximate 定常点を見つけるアルゴリズムは、$/\varepsilon$または$d$で指数関数的なクエリを生成しなければならない。
関連論文リスト
- Near-optimal Active Regression of Single-Index Models [5.081060114892763]
この研究は、$tildeO(dfracp2vee 1/varepsilonpvee 2)$エントリを$b$にクエリすることで、$(1+varepsilon)$-approximationソリューションを提供する最初のアルゴリズムを示す。
論文 参考訳（メタデータ） (2025-02-25T13:58:06Z) - 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) - 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) - 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) - Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss [41.17536985461902]
オラクルの複雑さを$Omega(Nepsilon-2/3)$として証明し、N$への依存が多対数因子に最適であることを示す。
非滑らかな場合、$tildeO(Nepsilon-2/3 + sqrtNepsilon-8/3)$と$tildeO(Nepsilon-2/3 + sqrtNepsilon-1)$の複雑さ境界を改善した手法を開発する。
論文 参考訳（メタデータ） (2021-05-04T21:49:15Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。