論文の概要: Online Min-Max Optimization: From Individual Regrets to Cumulative Saddle Points

• arxiv url: http://arxiv.org/abs/2602.10565v1
• Date: Wed, 11 Feb 2026 06:29:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-12 21:44:01.509619
• Title: Online Min-Max Optimization: From Individual Regrets to Cumulative Saddle Points
• Title（参考訳）: オンライン最小最適化:個々のレグレットから累積サドルポイントへ
• Authors: Abhijeet Vyas, Brian Bullins,
• Abstract要約: 本研究では,コンベックス・コンケーブ設定を超える様々な性能対策の下で,累積サドル点に基づくmin-max最適化のオンラインバージョンについて検討する。 個々人の後悔と相反する後悔の動的な概念について、両面のPolyak-ojasiewicz (PL)条件の下で境界を導出する。
• 参考スコア（独自算出の注目度）: 9.267347813727824
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose and study an online version of min-max optimization based on cumulative saddle points under a variety of performance measures beyond convex-concave settings. After first observing the incompatibility of (static) Nash equilibrium (SNE-Reg$_T$) with individual regrets even for strongly convex-strongly concave functions, we propose an alternate \emph{static} duality gap (SDual-Gap$_T$) inspired by the online convex optimization (OCO) framework. We provide algorithms that, using a reduction to classic OCO problems, achieve bounds for SDual-Gap$_T$~and a novel \emph{dynamic} saddle point regret (DSP-Reg$_T$), which we suggest naturally represents a min-max version of the dynamic regret in OCO. We derive our bounds for SDual-Gap$_T$~and DSP-Reg$_T$~under strong convexity-strong concavity and a min-max notion of exponential concavity (min-max EC), and in addition we establish a class of functions satisfying min-max EC~that captures a two-player variant of the classic portfolio selection problem. Finally, for a dynamic notion of regret compatible with individual regrets, we derive bounds under a two-sided Polyak-Łojasiewicz (PL) condition.
• Abstract（参考訳）: 本研究では, コンベックス・コンケーブ設定を超える様々な性能対策の下で, 累積サドル点に基づく min-max 最適化のオンライン版を提案し, 検討する。 まず,オンライン凸最適化(OCO)フレームワークにインスパイアされた,(静的)ナッシュ均衡(SNE-Reg$_T$)と強い凸-強凸関数に対しても個々の後悔を伴わない不整合性(SNE-Reg$_T$)を初めて観測した後,代替の \emph{static} 双対性ギャップ(SDual-Gap$_T$)を提案する。 我々は,従来のOCO問題への還元を用いて,SDual-Gap$_T$~と,DSP-Reg$_T$の新たなサドル点後悔(DSP-Reg$_T$)の限界を達成するアルゴリズムを提案する。 我々は、SDual-Gap$_T$~および DSP-Reg$_T$~を強い凸性-強凸性の概念と指数的凸性の概念(min-max EC)の下で導いており、また、古典的ポートフォリオ選択問題の2プレーヤ変種を捉えるmin-max EC~を満たす関数のクラスを確立する。 最後に、個々人の後悔と相反する後悔の動的な概念に対して、両側のポリアック・ジョジャシエヴィチ(PL)条件の下で境界を導出する。

関連論文リスト

• Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization [68.22688819802622]
  我々は、(ほぼ)$レベルのKKTソリューションを見つけるために、$O(/epsilon)$の最先端の複雑さを新たに提案する。 O(/epsilon)$ の(ほぼ) $ レベルの KKT ソリューションを見つけるための技術的複雑さを適用することで、(ほぼ) $ レベルの KKT ソリューションを見つけるための $O(/epsilon)$ の最先端の複雑さを新たに達成する。
  論文  参考訳（メタデータ） (2025-06-03T06:31:59Z)
• Bridging the Gap Between General and Down-Closed Convex Sets in Submodular Maximization [8.225819874406238]
  Mualem citemualem23re は、この手法がダウンクローズド制約と非ダウンクローズド制約の間を滑らかにできないことを示す。 本研究では,物体を2つの異なる凸体に自然分解した新しいオフラインおよびオンラインアルゴリズムを提案する。 また、3つのオフラインおよび2つのオンラインアプリケーションにまたがる提案アルゴリズムの優位性を実証的に示す。
  論文  参考訳（メタデータ） (2024-01-17T14:56:42Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  非定常環境におけるオンライン凸最適化について検討する。 パフォーマンス指標として動的後悔を選択します。 本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-07T14:10:57Z)

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

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