論文の概要: Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation

• arxiv url: http://arxiv.org/abs/2306.16617v2
• Date: Mon, 10 Nov 2025 01:07:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-11 21:18:44.211413
• Title: Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation
• Title（参考訳）: 平衡計算におけるアダプティブリーマン勾配のLast-Iterate Convergence
• Authors: Yang Cai, Michael I. Jordan, Tianyi Lin, Argyris Oikonomou, Emmanouil-Vasileios Vlatakis-Gkaragkounis,
• Abstract要約: 本稿では,テクスト幾何学的強単調ゲームに対する新たな収束結果を確立する。 我々のキーとなる結果は、RGDがテクスト幾何学的手法で最終定位線形収束を実現することを示しています。 全体として、ユークリッド設定を超えるゲームに対して、幾何学的に非依存な最終点収束解析を初めて提示する。
• 参考スコア（独自算出の注目度）: 52.73824786627612
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Equilibrium computation on Riemannian manifolds provides a unifying framework for numerous problems in machine learning and data analytics. One of the simplest yet most fundamental methods is Riemannian gradient descent (RGD). While its Euclidean counterpart has been extensively studied, it remains unclear how the manifold curvature affects RGD in game-theoretic settings. This paper addresses this gap by establishing new convergence results for \textit{geodesic strongly monotone} games. Our key result shows that RGD attains last-iterate linear convergence in a \textit{geometry-agnostic} fashion, a key property for applications in machine learning. We extend this guarantee to stochastic and adaptive variants -- SRGD and FARGD -- and establish that: (i) the sample complexity of SRGD is geometry-agnostic and optimal with respect to noise; (ii) FARGD matches the convergence rate of its non-adaptive counterpart up to constant factors, while avoiding reliance on the condition number. Overall, this paper presents the first geometry-agnostic last-iterate convergence analysis for games beyond the Euclidean settings, underscoring the surprising power of RGD -- despite its simplicity -- in solving a wide spectrum of machine learning problems.
• Abstract（参考訳）: リーマン多様体上の平衡計算は、機械学習とデータ分析における多くの問題に対する統一的なフレームワークを提供する。 最も単純だが最も基本的な方法の1つはリーマン勾配降下(RGD)である。 ユークリッド形式は広く研究されているが、多様体の曲率がゲーム理論の設定においてRGDにどう影響するかは定かではない。 本稿は, textit{geodesic strong monotone} ゲームに対する新たな収束結果を確立することで, このギャップを解消する。 我々のキーとなる結果から、RGDは機械学習の応用において重要な特性である「textit{geometry-agnostic}」の手法で、最終点の線形収束を達成できることが分かる。 この保証を SRGD と FARGD という確率的かつ適応的な変種に拡張し、それを確立します。 (i)SRGDのサンプル複雑性は、形状に依存しず、ノイズに関して最適である。 (ii) FARGDは条件数に依存することなく, 適応的でない因子の収束率を一定要素まで一致させる。 本稿では、ユークリッド設定を超えるゲームに対して、その単純さにもかかわらず、RGDの驚くべきパワーを立証する、幾何学に依存しない最後の収束解析を初めて提示する。

関連論文リスト

• Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent [13.27202712518471]
  本稿では,非対称励起勾配 (APGD) と呼ばれるBurer-Monteiro因子化に基づく勾配型アルゴリズムを提案し,解析する。
  論文  参考訳（メタデータ） (2025-04-28T07:13:23Z)
• Riemannian Federated Learning via Averaging Gradient Stream [8.75592575216789]
  本稿では,RFedAGS(Federated Averaging Gradient Stream)アルゴリズムの開発と解析を行う。 合成および実世界のデータを用いて数値シミュレーションを行い,提案したRFedAGSの性能を実証した。
  論文  参考訳（メタデータ） (2024-09-11T12:28:42Z)
• Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms [18.425648833592312]
  tBMM は $O(epsilon-2)$ 内の $ilon$-定常点に収束することを示す。 軽度反復の下では、全最適性ギャップが有界である場合、各反復においてサブプロブレムが解かれるときの結果は依然として保たれる。
  論文  参考訳（メタデータ） (2024-05-05T22:53:14Z)
• Intrinsic Bayesian Cramér-Rao Bound with an Application to Covariance Matrix Estimation [49.67011673289242]
  本稿では, 推定パラメータが滑らかな多様体内にある推定問題に対して, 新たな性能境界を提案する。 これはパラメータ多様体の幾何学と推定誤差測度の本質的な概念を誘導する。
  論文  参考訳（メタデータ） (2023-11-08T15:17:13Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。 この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
  論文  参考訳（メタデータ） (2023-11-04T11:12:24Z)
• First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces [93.35384756718868]
  min-maxアルゴリズムはユークリッド設定で解析されている。 指数関数法 (RCEG) が線形速度で最終収束を補正したことを証明した。
  論文  参考訳（メタデータ） (2022-06-04T18:53:44Z)
• Differentially private Riemannian optimization [40.23168342389821]
  微分プライベートの枠組みを導入する。 現実的なリスクの問題です。 パラメータは a に制約される。 ロックフェラー多様体。 提案手法の有効性をいくつかの応用例で示す。
  論文  参考訳（メタデータ） (2022-05-19T12:04:15Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• Stochastic Zeroth-order Riemannian Derivative Estimation and Optimization [15.78743548731191]
  多様体非線型性の非線型性の難しさを克服するために、ガウス滑らか化関数のオラクル版を提案する。 ニューラルネットワークに対するロボティクスとブラックボックス攻撃に対するブラックボックス剛性制御における,結果によるアルゴリズムの適用性と実世界の応用を実証する。
  論文  参考訳（メタデータ） (2020-03-25T06:58:19Z)
• From Nesterov's Estimate Sequence to Riemannian Acceleration [52.99237600875452]
  我々は、Nesterov氏の推定シーケンス手法の代替解析を開発し、これも独立性を持つ可能性がある。 そして、この解析をリーマン集合に拡張し、非ユークリッド構造による鍵的困難をある計量歪みに局所化する」。
  論文  参考訳（メタデータ） (2020-01-24T04:17:14Z)

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

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