論文の概要: Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization

• arxiv url: http://arxiv.org/abs/2610.04944v1
• Date: Sun, 04 Oct 2026 04:38:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-11 07:39:53.367052
• Title: Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization
• Title（参考訳）: 有限サム非凸-ストロングリ-コンケーブ極小最適化の近似的複素性
• Abstract要約: インクリメンタルな1次アルゴリズムをゼロ参照する場合、複雑性は$tildeO(n+sqrtn,Lvarepsilon-2)$で、クエリ予算は固定される。
• 参考スコア（独自算出の注目度）: 1.6921396880325779
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We characterize, up to logarithmic factors, the minimax expected query complexity of finite-sum nonconvex-strongly-concave optimization under mean-squared averaged smoothness. For randomized zero-respecting incremental first-order algorithms, the complexity is $\tildeΘ(n+\min\{\sqrt{n}\,κ,n^{3/4}\sqrtκ\}\,LΔ\varepsilon^{-2})$ throughout $κ=L/μ\ge1$, under exact dual initialization and for $0<\varepsilon^2\le c_0LΔ$, where $c_0>0$ is universal. This characterization is our main result. A dual-chain construction provides the lower bound and matches the existing Catalyst upper bound for $κ\ge\sqrt{n}$. For $1\leκ\le\sqrt{n}$, we introduce recursive proximal descent-ascent (RPDA), which retains a recursive gradient estimator across proximal subproblems and attains $\tilde{O}(n+\sqrt{n}\,κLΔ\varepsilon^{-2})$ with a fixed query budget. Both upper bounds guarantee an expected squared primal gradient at most $\varepsilon^2$. Under individual smoothness, we also prove $Ω(n+\min\{κ,\sqrt{nκ}\}\,LΔ\varepsilon^{-2})$ for every $κ\ge1$. It matches the polynomial upper rate for a bilinear subclass when $κ\ge n$; the intermediate-condition-number gap remains open.
• Abstract（参考訳）: 対数的因子に限り、平均2乗な滑らかさの下での有限サム非凸-強凸-凹最適化の最小のクエリ複雑性を特徴づける。 ランダム化されたゼロ・リスペクトインクリメンタルな1次アルゴリズムの場合、複雑さは$\tildee(n+\min\{\sqrt{n}\,κ,n^{3/4}\sqrtκ\}\,LΔ\varepsilon^{-2})$ throughout $κ=L/μ\ge1$, under exactly dual initialization and for $0<\varepsilon^2\le c_0LΔ$, for $c_0>0$。 この特徴が主な成果です。 二重鎖構成は下界を提供し、既存の触媒上界に$κ\ge\sqrt{n}$と一致する。 $1\leκ\le\sqrt{n}$に対して、我々は、近位サブプロブレムにわたる再帰的勾配推定器を保持する再帰的近位降下指数 (RPDA) を導入し、固定されたクエリ予算で$\tilde{O}(n+\sqrt{n}\,κLΔ\varepsilon^{-2})$を得る。 両方の上界は、期待される2乗原始勾配を最大$\varepsilon^2$で保証する。 個々の滑らかさの下では、すべての$κ\ge1$に対して$Ω(n+\min\{κ,\sqrt{nκ}\}\,LΔ\varepsilon^{-2}) も証明する。 これは$κ\ge n$のときの双線型部分クラスに対する多項式上率と一致し、中間条件数ギャップは開のままである。

関連論文リスト

• Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization [55.29259818039367]
  凸閉集合上の逆オンライン非負の非単調DR-部分モジュラ函数について検討する。 学習者は、目的を観察する前に各アクションを学習し、後から最高の固定アクションと競合する。 定数対物列は、最適に多くの1次クエリでオフラインの$(4/9-varepsilon)$近似を生成する。
  論文  参考訳（メタデータ） (2026-09-30T18:26:29Z)
• Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization [1.6921396880325779]
  我々は,SAPD+の決定論的複雑性における線形条件数依存性が,非連続性最適化に必要であることを証明した。
  論文  参考訳（メタデータ） (2026-09-25T06:34:04Z)
• Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness [8.428362872515416]
  我々は、各$_maxgeq 3$に対して、個々の滑らかさの下で下界に一致することを証明した。 また、各$_maxgeq 3$に対して、個々の滑らかさの下で下界が一致することを証明する。
  論文  参考訳（メタデータ） (2026-08-30T02:47:24Z)
• Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting [0.9023847175654603]
  c_mathrmF(T_n),c_2(T_n)=(log(n+1)3/2)$を符号、空間性、正方性制限なしで証明する。 純粋な$varepsilon$-DP行列力学クラスでは、最適化された最大誤差と平均二乗誤差の両方が$(varepsilon-2log3(n+1))$である。
  論文  参考訳（メタデータ） (2026-07-30T14:41:34Z)
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
  論文  参考訳（メタデータ） (2025-08-09T08:28:06Z)
• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。 我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。 また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
  論文  参考訳（メタデータ） (2024-06-07T08:26:31Z)
• Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity [22.615156512223763]
  本研究では,有限サム構造を目的とする分散楽観的すべり(SVOGS)法を提案する。 我々は$mathcal O(delta D2/varepsilon)$、$mathcal O(n+sqrtndelta D2/varepsilon)$、$tildemathcal O(n+sqrtndelta+L)D2/varepsilon)$の局所呼び出しを証明している。
  論文  参考訳（メタデータ） (2024-05-25T08:34:49Z)
• 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)
• On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimization [21.334985032433778]
  分散最適化問題 $min_bf xinmathbb Rd f(bf x)triq frac1msum_i=1m f_i(bf x)triq frac1nsum_j=1n。
  論文  参考訳（メタデータ） (2022-10-25T11:37:11Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。