論文の概要: Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developments

• arxiv url: http://arxiv.org/abs/2303.17192v1
• Date: Thu, 30 Mar 2023 07:04:22 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-31 14:18:16.436172
• Title: Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developments
• Title（参考訳）: 漸進型手法の線形収束速度:古典的・最近の展開に関する調査
• Authors: Quoc Tran-Dinh
• Abstract要約: 外部分解性(EG)は、サドルポイント問題の解を近似するためのよく知られた方法である。 近年,機械学習の新たな応用やロバストな最適化により,これらの手法が普及している。 アルゴリズムの異なるクラスに対する統一収束解析を提供し、サブ線形のベストイテレートとラストイテレート収束率に重点を置いている。
• 参考スコア（独自算出の注目度）: 12.995632804090198
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The extragradient (EG), introduced by G. M. Korpelevich in 1976, is a well-known method to approximate solutions of saddle-point problems and their extensions such as variational inequalities and monotone inclusions. Over the years, numerous variants of EG have been proposed and studied in the literature. Recently, these methods have gained popularity due to new applications in machine learning and robust optimization. In this work, we survey the latest developments in the EG method and its variants for approximating solutions of nonlinear equations and inclusions, with a focus on the monotonicity and co-hypomonotonicity settings. We provide a unified convergence analysis for different classes of algorithms, with an emphasis on sublinear best-iterate and last-iterate convergence rates. We also discuss recent accelerated variants of EG based on both Halpern fixed-point iteration and Nesterov's accelerated techniques. Our approach uses simple arguments and basic mathematical tools to make the proofs as elementary as possible, while maintaining generality to cover a broad range of problems.
• Abstract（参考訳）: g. m. korpelevich が1976年に導入したextragradient (eg) は、鞍点問題の解とその変分不等式や単調包含物などの拡張を近似するためのよく知られた方法である。 長年にわたり、EGの多くの変種が提案され、文献で研究されてきた。 近年,機械学習やロバスト最適化の新たな応用により,これらの手法が普及している。 本研究では, 非線形方程式と包含の解を近似するためのeg法とその変種の最新展開について, 単調性と共単調性の設定に着目して検討する。 アルゴリズムの異なるクラスに対する統一収束解析を提供し、サブ線形ベストイテレートとラストイテレート収束率に重点を置いている。 また、Halpern固定点反復法とNesterov加速法の両方に基づく最近のEGの加速変種についても論じる。 我々のアプローチは、単純な議論と基本的な数学的ツールを使って証明を可能な限り基本的なものにし、幅広い問題をカバーする汎用性を維持します。

関連論文リスト

• Revisiting Extragradient-Type Methods -- Part 1: Generalizations and Sublinear Convergence Rates [6.78476672849813]
  本稿では、方程式と包摂性の両方を解くためのよく知られた指数関数法(EG法)を包括的に分析する。 アルゴリズムのクラス全体のサブ線形ベストイテレートとラストイテレートの収束率を分析する。 我々は、新しいアルゴリズムのクラスとそれに対応する収束結果を導入し、上述のEGフレームワークをモノトーンの包含に拡張する。
  論文  参考訳（メタデータ） (2024-09-25T12:14:05Z)
• Multiple Greedy Quasi-Newton Methods for Saddle Point Problems [0.0]
  ヘッセン点問題の解法としてMultiple Greedysi-SP(MGSR1-SP)法を提案する。 本手法は安定性と効率性を両立させる。 その結果、MGSR1-SPの性能は幅広い機械学習アプリケーションで確認された。
  論文  参考訳（メタデータ） (2024-08-01T02:40:37Z)
• High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise [96.80184504268593]
  グラデーション、クリッピングは、優れた高確率保証を導き出すアルゴリズムの鍵となる要素の1つである。 クリッピングは、合成および分散最適化の一般的な方法の収束を損なう可能性がある。
  論文  参考訳（メタデータ） (2023-10-03T07:49:17Z)
• SARAH-based Variance-reduced Algorithm for Stochastic Finite-sum Cocoercive Variational Inequalities [137.6408511310322]
  有限サムコヒーレンシブ変分不等式の問題を考える。 強い単調な問題に対しては、この方法を用いて解への線形収束を達成することができる。
  論文  参考訳（メタデータ） (2022-10-12T08:04:48Z)
• An Adaptive Incremental Gradient Method With Support for Non-Euclidean Norms [19.41328109094503]
  そこで本研究では,SAGAアルゴリズムの適応型を新たにいくつか提案し,解析する。 一般的な設定の下で収束保証を確立する。 我々は、非ユークリッドノルムをサポートするためにSAGAの分析を改善した。
  論文  参考訳（メタデータ） (2022-04-28T09:43:07Z)
• Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods [73.35353358543507]
  SGDA(Gradient Descent-Ascent)は、min-max最適化と変分不等式問題(VIP)を解くための最も顕著なアルゴリズムの1つである。 本稿では,多種多様な降下指数法を網羅した統合収束解析を提案する。 本研究では,新しい分散化手法 (L-SVRGDA) や,新しい分散圧縮方式 (QSGDA, DIANA-SGDA, VR-DIANA-SGDA) ,座標ランダム化方式 (SEGA-SGDA) など,SGDAの新しい変種を開発した。
  論文  参考訳（メタデータ） (2022-02-15T09:17:39Z)
• Last-Iterate Convergence of Saddle-Point Optimizers via High-Resolution Differential Equations [83.3201889218775]
  広く使われている1次サドル点最適化法は、帰納的導出時に同一の連続時間常微分方程式(ODE)を導出する。 しかし、これらの方法の収束特性は、単純な双線型ゲームでさえ質的に異なる。 いくつかのサドル点最適化法のための微分方程式モデルの設計に流体力学の研究フレームワークを採用する。
  論文  参考訳（メタデータ） (2021-12-27T18:31:34Z)
• A Discrete Variational Derivation of Accelerated Methods in Optimization [68.8204255655161]
  最適化のための異なる手法を導出できる変分法を導入する。 我々は1対1の対応において最適化手法の2つのファミリを導出する。 自律システムのシンプレクティシティの保存は、ここでは繊維のみに行われる。
  論文  参考訳（メタデータ） (2021-06-04T20:21:53Z)
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
  本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。 提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。 加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
  論文  参考訳（メタデータ） (2020-06-11T18:49:06Z)

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

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