論文の概要: Revisiting Extragradient-Type Methods -- Part 1: Generalizations and Sublinear Convergence Rates

• arxiv url: http://arxiv.org/abs/2409.16859v1
• Date: Wed, 25 Sep 2024 12:14:05 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-27 03:55:18.729463
• Title: Revisiting Extragradient-Type Methods -- Part 1: Generalizations and Sublinear Convergence Rates
• Title（参考訳）: 漸進型手法の再検討 -その1:一般化と線形収束率
• Authors: Quoc Tran-Dinh, Nghia Nguyen-Trung,
• Abstract要約: 本稿では、方程式と包摂性の両方を解くためのよく知られた指数関数法(EG法)を包括的に分析する。 アルゴリズムのクラス全体のサブ線形ベストイテレートとラストイテレートの収束率を分析する。 我々は、新しいアルゴリズムのクラスとそれに対応する収束結果を導入し、上述のEGフレームワークをモノトーンの包含に拡張する。
• 参考スコア（独自算出の注目度）: 6.78476672849813
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper presents a comprehensive analysis of the well-known extragradient (EG) method for solving both equations and inclusions. First, we unify and generalize EG for [non]linear equations to a wider class of algorithms, encompassing various existing schemes and potentially new variants. Next, we analyze both sublinear ``best-iterate'' and ``last-iterate'' convergence rates for the entire class of algorithms, and derive new convergence results for two well-known instances. Second, we extend our EG framework above to ``monotone'' inclusions, introducing a new class of algorithms and its corresponding convergence results. Third, we also unify and generalize Tseng's forward-backward-forward splitting (FBFS) method to a broader class of algorithms to solve [non]linear inclusions when a weak-Minty solution exists, and establish its ``best-iterate'' convergence rate. Fourth, to complete our picture, we also investigate sublinear rates of two other common variants of EG using our EG analysis framework developed here: the reflected forward-backward splitting and the golden ratio methods. Finally, we conduct an extensive numerical experiment to validate our theoretical findings. Our results demonstrate that several new variants of our proposed algorithms outperform existing schemes in the majority of examples.
• Abstract（参考訳）: 本稿では、方程式と包摂性の両方を解くためのよく知られた外部段階法(EG法)を包括的に分析する。 まず、線形方程式のEGをより広範なアルゴリズムのクラスに統一し一般化し、様々な既存のスキームと潜在的に新しい変種を包含する。 次に、アルゴリズムのクラス全体のサブ線形 ``best-iterate'' と ``last-iterate'' の収束率を分析し、2つのよく知られたインスタンスに対する新しい収束結果を導出する。 第二に、我々はEGフレームワークを「モノトーン」の包含に拡張し、新しいアルゴリズムのクラスとそれに対応する収束結果を導入する。 第三に、Tseng のフォワード・バック・フォワード・スプリッティング (FBFS) 法をより広範なアルゴリズムに統一して一般化し、弱ミティ解が存在するときの非線形包摂を解き、その 'best-iterate' 収束率を確立する。 第4に,本研究で開発されたEG分析フレームワークを用いて,他の2種類のEGの線形化率について検討した。 最後に,我々の理論的知見を検証するため,広範な数値実験を行った。 その結果,提案アルゴリズムのいくつかの新しい変種は,既存のスキームよりも多くの例で優れていることがわかった。

関連論文リスト

• Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developments [12.995632804090198]
  外部分解性(EG)は、サドルポイント問題の解を近似するためのよく知られた方法である。 近年,機械学習の新たな応用やロバストな最適化により,これらの手法が普及している。 アルゴリズムの異なるクラスに対する統一収束解析を提供し、サブ線形のベストイテレートとラストイテレート収束率に重点を置いている。
  論文  参考訳（メタデータ） (2023-03-30T07:04:22Z)
• Efficient Alternating Minimization Solvers for Wyner Multi-View Unsupervised Learning [0.0]
  本稿では,計算効率のよい解法の開発を可能にする2つの新しい定式化法を提案する。 提案した解法は, 計算効率, 理論的収束保証, ビュー数による局所最小値複雑性, 最先端技術と比較して, 例外的な精度を提供する。
  論文  参考訳（メタデータ） (2023-03-28T10:17:51Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  バイレベル最適化は、幅広い機械学習モデルに適用されている。 既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。 そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-06-30T05:29:52Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。 我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。 これらのアルゴリズムに対する漸近的理論的保証を提供する。
  論文  参考訳（メタデータ） (2022-04-07T00:11:05Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。 厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。 このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
  論文  参考訳（メタデータ） (2021-11-29T15:10:09Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  バイレベル最適化は多くの機械学習問題に対するツールである。 Stoc-BiO という新しい確率効率勾配推定器を提案する。
  論文  参考訳（メタデータ） (2020-10-15T18:09:48Z)
• A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization [16.714109768541785]
  非非状態におけるSGD不変量を満たすすべての方法について単一の解析を行う。 また、PL条件下での非非状態におけるより高速な線形収束を得るための統一解析も提供する。
  論文  参考訳（メタデータ） (2020-06-12T08:58:03Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)
• A Unified Convergence Analysis for Shuffling-Type Gradient Methods [32.8097849940763]
  有限項問題を解くための一般化勾配シャッフル型法に対する統一収束解析を提案する。 以上の結果から,特定の神経シャッフル変種でのトレーニングに適する選択が示唆された。
  論文  参考訳（メタデータ） (2020-02-19T15:45:41Z)

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

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