論文の概要: Accelerating Min-Max Optimization via Power-Law Stepsizes

• arxiv url: http://arxiv.org/abs/2606.01764v1
• Date: Mon, 01 Jun 2026 06:45:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-02 21:34:31.416523
• Title: Accelerating Min-Max Optimization via Power-Law Stepsizes
• Title（参考訳）: Power-Law StepsizesによるMin-Max最適化の高速化
• Authors: Yue Wu, Weiqiang Zheng, Yang Cai, Haipeng Luo,
• Abstract要約: 本稿では,非拘束的ビファインmin-max最適化に対するEG法(Extragradient)の収束保証を再検討する。 決定論的動的段階化スケジュールは、任意の$varepsilon > 0$に対して、EGの収束速度を$mathcalO(T-2/3+varepsilon)$に加速させることを示す。 次に、外挿と更新の異なるステップ化を許すことで、ほぼ最適の$mathcalO(T-1+varepsilon)$への収束率がさらに向上することを示す。
• 参考スコア（独自算出の注目度）: 46.20699762747848
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We revisit the convergence guarantees of the Extragradient (EG) method for unconstrained biaffine min-max optimization. It is known that EG with a fixed stepsize achieves a $Θ(T^{-1/2})$ last-iterate convergence rate, which is slower than the optimal $\mathcal{O}(T^{-1})$ rate attainable by incorporating additional mechanisms such as anchoring. Motivated by recent advances showing that dynamic stepsizes alone can significantly accelerate gradient descent, we ask whether dynamic stepsizes can similarly accelerate the last-iterate convergence of EG. We present the first positive result in this direction. Specifically, we provide a deterministic dynamic stepsize schedule that accelerates the convergence rate of EG to $\mathcal{O}(T^{-2/3+\varepsilon})$ for any $\varepsilon > 0$. We also show that this rate is tight when the extrapolation and update steps of EG use the same stepsize. We then show that allowing different stepsizes for the extrapolation and update steps further improves the convergence rate to the near-optimal $\mathcal{O}(T^{-1+\varepsilon})$. Our analysis reduces stepsize scheduling to an optimization problem, whose solution leads to a stepsize schedule that follows (a discretization of) a power-law distribution. Our proposed stepsize schedules and analysis extend to other methods, such as Optimistic Gradient (OG), and suggest broader applicability to general min-max optimization problems.
• Abstract（参考訳）: 本稿では,非拘束的ビファインmin-max最適化に対するEG法(Extragradient)の収束保証を再検討する。 固定段数を持つ EG は、最適化された $\mathcal{O}(T^{-1})$ よりも遅く、アンカリングのような追加の機構を組み込むことで達成できる$(T^{-1/2})$終点収束率を達成することが知られている。 近年の進歩により、動的段階化単独で勾配降下を著しく加速できることが示され、動的段階化がEGの終点収束をも同様に加速できるかどうかを問う。 この方向に最初の肯定的な結果を示す。 具体的には、任意の$\varepsilon > 0$に対して、EGの収束速度を$\mathcal{O}(T^{-2/3+\varepsilon})$に加速する決定論的動的段階化スケジュールを提供する。 また、EGの外挿と更新のステップが同じステップサイズを使用する場合、このレートが厳密であることも示します。 すると、外挿と更新の異なる段階化を許すことで、ほぼ最適の $\mathcal{O}(T^{-1+\varepsilon})$ への収束率がさらに改善されることが示される。 本分析では, 段階的なスケジューリングを最適化問題に還元し, 解法は, 正則分布に追従する(離散化)段階的なスケジュールを導出する。 提案手法は,OG(Optimistic Gradient)などの他の手法に拡張し,一般のmin-max最適化問題に適用可能であることを示唆する。

関連論文リスト

• Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression [20.35967769410065]
  線形分離可能なデータを用いた$ell$-regularized logistic regressionの段差が一定である勾配降下(GD)について検討した。 これは、単に大きなステップサイズを使用することで、$widetildemathcalO(sqrtkappa)$に加速できることを示す。
  論文  参考訳（メタデータ） (2025-06-03T00:21:22Z)
• Anytime Acceleration of Gradient Descent [92.02082223856479]
  エム収束保証による勾配勾配勾配の段階的加速度について検討する。 滑らかな(強くない)凸最適化のために、任意の停止時間に対して、勾配降下が$O(T-1.119)$の収束保証を達成できる段階的なスケジュールを提案する。
  論文  参考訳（メタデータ） (2024-11-26T18:29:44Z)
• Formal guarantees for heuristic optimization algorithms used in machine learning [6.978625807687497]
  グラディエント・Descent(SGD)とその変種は、大規模最適化機械学習(ML)問題において支配的な手法となっている。 本稿では,いくつかの凸最適化手法の形式的保証と改良アルゴリズムの提案を行う。
  論文  参考訳（メタデータ） (2022-07-31T19:41:22Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
  論文  参考訳（メタデータ） (2021-02-15T07:10:33Z)
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints [10.578409461429626]
  本研究では、滑らかで強可変なゲームやイテレーションのための一階法に積分二次的制約理論を適用する。 我々は、負の運動量法(NM)に対して、既知の下界と一致する複雑性$mathcalO(kappa1.5)$で、初めて大域収束率を与える。 一段階のメモリを持つアルゴリズムでは,バッチ毎に1回だけ勾配を問合せすれば,高速化は不可能であることを示す。
  論文  参考訳（メタデータ） (2020-09-23T20:02:00Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)

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

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