論文の概要: Efficient Uncoupled Learning Dynamics with $\tilde{O}\!\left(T^{-1/4}\right)$ Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedback

• arxiv url: http://arxiv.org/abs/2602.21436v1
• Date: Tue, 24 Feb 2026 23:27:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-26 18:19:16.640253
• Title: Efficient Uncoupled Learning Dynamics with $\tilde{O}\!\left(T^{-1/4}\right)$ Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedback
• Title（参考訳）: 帯域フィードバック下の凸集合上の双線形サドル問題における最終Iterate Convergence$\tilde{O}\!\left(T^{-1/4}\right)$Last-Iterate Convergenceを用いた効率的なアンカップリング学習ダイナミクス
• Authors: Arnab Maiti, Claire Jie Zhang, Kevin Jamieson, Jamie Heather Morgenstern, Ioannis Panageas, Lillian J. Ratliff,
• Abstract要約: 両線形サドル点問題における学習アルゴリズムの終点収束について検討する。 我々の主な貢献は、非結合学習アルゴリズムの設計であり、高い確率でナッシュ平衡への最終点収束を保証する。
• 参考スコア（独自算出の注目度）: 25.081005025442835
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study last-iterate convergence of learning algorithms in bilinear saddle-point problems, a preferable notion of convergence that captures the day-to-day behavior of learning dynamics. We focus on the challenging setting where players select actions from compact convex sets and receive only bandit feedback. Our main contribution is the design of an uncoupled learning algorithm that guarantees last-iterate convergence to the Nash equilibrium with high probability. We establish a convergence rate of $\tilde{O}(T^{-1/4})$ up to polynomial factors in problem parameters. Crucially, our proposed algorithm is computationally efficient, requiring only an efficient linear optimization oracle over the players' compact action sets. The algorithm is obtained by combining techniques from experimental design and the classic Follow-The-Regularized-Leader (FTRL) framework, with a carefully chosen regularizer function tailored to the geometry of the action set of each learner.
• Abstract（参考訳）: 本稿では,学習力学の日々の振る舞いを捉えた収束概念である,双線形サドル点問題における学習アルゴリズムの終点収束について検討する。 我々は,コンパクトな凸集合からアクションを選択し,帯域幅フィードバックのみを受信する,困難な設定に焦点をあてる。 我々の主な貢献は、非結合学習アルゴリズムの設計であり、高い確率でナッシュ平衡への最終点収束を保証する。 問題パラメータの多項式係数までの収束率を$\tilde{O}(T^{-1/4})$とする。 重要なことは、提案アルゴリズムは計算的に効率的であり、プレイヤーのコンパクトなアクションセットよりも効率的な線形最適化オラクルしか必要としない。 このアルゴリズムは、実験設計と古典的なFTRL(Follow-The-Regularized-Leader)フレームワークを、各学習者の行動集合の幾何学に合わせて慎重に選択された正規化関数と組み合わせて得られる。

関連論文リスト

• A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization [53.14532968909759]
  ALEXRと呼ばれる,効率的な単ループプリマル・デュアルブロック座標アルゴリズムを提案する。 本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。 CFCCO の ROC 曲線の下での GDRO および部分領域の実験結果から,提案アルゴリズムの有望な性能を示す。
  論文  参考訳（メタデータ） (2023-12-04T19:00:07Z)
• Learning Zero-Sum Linear Quadratic Games with Improved Sample Complexity and Last-Iterate Convergence [18.1055795175092]
  Zero-sum Linear Quadratic (LQ) ゲームは最適制御の基本である。 本研究では,より単純な入れ子ゼロ階法 (NPG) アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-08T11:47:31Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits [27.279654173896372]
  我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。 これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
  論文  参考訳（メタデータ） (2021-11-06T16:46:55Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Meta-Regularization: An Approach to Adaptive Choice of the Learning Rate in Gradient Descent [20.47598828422897]
  第一次下降法における学習率の適応的選択のための新しいアプローチであるtextit-Meta-Regularizationを提案する。 本手法は,正規化項を追加して目的関数を修正し,共同処理パラメータをキャストする。
  論文  参考訳（メタデータ） (2021-04-12T13:13:34Z)
• Efficient Projection-Free Algorithms for Saddle Point Problems [39.88460595129901]
  複雑な制約を伴う凸凸凸凹点問題に対するプロジェクションフリーアルゴリズムについて検討する。 条件勾配スライディングとMirror-Proxを組み合わせることで、バッチ設定で$tildeO (1/sqrtepsilon)$評価と$tildeO (1/epsilon2)$線形最適化しか必要としないことを示す。
  論文  参考訳（メタデータ） (2020-10-21T15:05:53Z)
• Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression [0.0]
  本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。 その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
  論文  参考訳（メタデータ） (2020-06-24T07:40:31Z)

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

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