論文の概要: On the Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization with Exact Proximal Oracles
- arxiv url: http://arxiv.org/abs/2611.04806v1
- Date: Tue, 03 Nov 2026 12:40:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-09 13:20:38.645276
- Title: On the Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization with Exact Proximal Oracles
- Title(参考訳): 有限和非凸-ストロングリ-コンケーブ極小最適化の特殊近位オラクルによる複雑性について
- Abstract要約: 有限サム非強弱極小問題は、敵の訓練や分布的に頑健な学習で生じる。
既知の下界は、線形スパンアルゴリズム、ゼロ反射アルゴリズム、あるいは制限された近位プロトコルのみをカバーする。
適応性も正確な近さも複雑さを改善できない。
- 参考スコア(独自算出の注目度): 8.428362872515416
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Finite-sum nonconvex-strongly-concave minimax problems arise in adversarial training and distributionally robust learning. Their known lower bounds cover only linear-span algorithms, zero-respecting algorithms, or a restricted proximal protocol. They leave open the power of exact component proximal steps, whose responses are global saddle points of regularized component problems and can expose directions that gradients do not reveal. We show that neither unrestricted adaptivity nor exact proximal access improves the polynomial complexity. We consider $n$ components with joint mean-squared smoothness $L$ and condition number $κ$, started from a point with primal gap at most $Δ$ and joint gradient norm at most $\sqrt{2LΔ}$. For $\varepsilon^2/(LΔ)$ below a universal constant, every randomized adaptive algorithm with exact component values, gradients, and proximal responses needs $Ω(n+\min\{\sqrt n\,κ,n^{3/4}\sqrtκ\}LΔ/\varepsilon^2)$ component queries in the worst case to find an $\varepsilon$-stationary point of the value function. A method using only component gradients attains this rate up to a factor $\log^2(2+κ)$, including initialization. Zhou (arXiv:2610.04944) concurrently proves the same rate for zero-respecting first-order methods. In our hard instances, every component admits proximal steps with the same step sizes, and a response for a component reveals hidden directions only up to the first one assigned to another component.
- Abstract(参考訳): 有限サム非凸非凸非凸極小問題(英語版)は、逆行訓練や分布論的に堅牢な学習において生じる。
既知の下界は、線形スパンアルゴリズム、ゼロ反射アルゴリズム、あるいは制限された近位プロトコルのみをカバーする。
正則成分問題に対する応答が大域的サドル点であり、勾配が明らかにしない方向を明らかにすることができる。
制限のない適応性も、正確な近位アクセスも、多項式の複雑さを改善できないことを示す。
結合平均二乗滑らか度 $L$ および条件数 $κ$ を持つ$n$成分は、最大で$Δ$ の原始ギャップを持つ点から始まり、最大で $\sqrt{2LΔ}$ の合同勾配ノルムから始まる。
普遍定数以下の$\varepsilon^2/(LΔ)$の場合、正確な成分値、勾配、および近似応答を持つ任意のランダム化適応アルゴリズムは、値関数の$\varepsilon$定常点を見つけるために最悪の場合、$Ω(n+\min\{\sqrt n\,κ,n^{3/4}\sqrtκ\}LΔ/\varepsilon^2)$コンポーネントクエリを必要とする。
成分勾配のみを用いる手法は、初期化を含む係数 $\log^2(2+κ)$ に達する。
Zhou (arXiv:2610.04944) は 0-respecting 1次法に対して、同時に同じレートを証明している。
ハードインスタンスでは、すべてのコンポーネントが同じステップサイズで近いステップを許可し、コンポーネントに対するレスポンスは、他のコンポーネントに割り当てられた最初のステップにのみ、隠れた方向を示す。
関連論文リスト
- Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex $(L_0,L_1)$-Smooth Functions [50.90629146297993]
期待値において精度$varepsilon$に達する複雑さを導出する。
上界は提案手法YETIにより達成される。
下界は、任意の一階法で困難であるインスタンスの族を明示的に構成することで得られる。
論文 参考訳(メタデータ) (2026-11-03T02:01:46Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳(メタデータ) (2023-07-24T14:37:22Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Derivative-free Alternating Projection Algorithms for General
Nonconvex-Concave Minimax Problems [9.173866646584031]
本稿では,非滑らかなゼロ次ミニマックス問題に対するアルゴリズムを提案する。
また,非コンケーブミニマックス問題に対処できることを示す。
論文 参考訳(メタデータ) (2021-08-01T15:23:49Z) - The Complexity of Nonconvex-Strongly-Concave Minimax Optimization [43.07732143522183]
本稿では,非強凹型(nc-sc)滑らかなミニマックス問題の近似定常点を求めるための複雑さを確立する。
提案された$Omega-strong$lyconcaveサブ2問題を一般複雑性と平均複雑性の両方で展開する。
提案する有限和設定では,提案するアルゴリズムは条件数にほぼ依存している。
論文 参考訳(メタデータ) (2021-03-29T18:53:57Z) - Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results
and Construction [18.65143269806133]
我々は、個々のコンポーネントごとに勾配および近位オラクルにアクセスできる近位インクリメンタルファーストオーダー(PIFO)アルゴリズムを検討する。
古典的な例の三対角行列を$n$群に分割する逆問題を構築するための新しいアプローチを開発する。
論文 参考訳(メタデータ) (2021-03-15T11:20:31Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳(メタデータ) (2020-05-13T16:44:12Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳(メタデータ) (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。