論文の概要: Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees

• arxiv url: http://arxiv.org/abs/2109.04522v2
• Date: Mon, 3 Apr 2023 17:53:20 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-05 01:50:29.779733
• Title: Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees
• Title（参考訳）: 最適化における非同期イテレーション:新しいシーケンス結果とシャーパアルゴリズム保証
• Authors: Hamid Reza Feyzmahdavian and Mikael Johansson
• Abstract要約: 並列および分散最適化アルゴリズムの解析に現れる非同期反復に対する新しい収束結果を紹介する。 結果は簡単に適用でき、非同期の度合いが反復の収束率にどのように影響するかを明確に見積もることができる。
• 参考スコア（独自算出の注目度）: 10.984101749941471
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce novel convergence results for asynchronous iterations that appear in the analysis of parallel and distributed optimization algorithms. The results are simple to apply and give explicit estimates for how the degree of asynchrony impacts the convergence rates of the iterates. Our results shorten, streamline and strengthen existing convergence proofs for several asynchronous optimization methods and allow us to establish convergence guarantees for popular algorithms that were thus far lacking a complete theoretical understanding. Specifically, we use our results to derive better iteration complexity bounds for proximal incremental aggregated gradient methods, to obtain tighter guarantees depending on the average rather than maximum delay for the asynchronous stochastic gradient descent method, to provide less conservative analyses of the speedup conditions for asynchronous block-coordinate implementations of Krasnoselskii-Mann iterations, and to quantify the convergence rates for totally asynchronous iterations under various assumptions on communication delays and update rates.
• Abstract（参考訳）: 本稿では並列および分散最適化アルゴリズムの解析に現れる非同期反復に対する新しい収束結果を提案する。 結果は簡単に適用でき、非同期度が反復の収束率にどのように影響するかを明確に見積もることができる。 その結果,既存の非同期最適化手法の収束証明の短縮,合理化,強化が可能となり,これまで完全に理論的理解を欠いていた一般的なアルゴリズムに対する収束保証を確立することができた。 Specifically, we use our results to derive better iteration complexity bounds for proximal incremental aggregated gradient methods, to obtain tighter guarantees depending on the average rather than maximum delay for the asynchronous stochastic gradient descent method, to provide less conservative analyses of the speedup conditions for asynchronous block-coordinate implementations of Krasnoselskii-Mann iterations, and to quantify the convergence rates for totally asynchronous iterations under various assumptions on communication delays and update rates.

関連論文リスト

• Asynchronous Distributed Optimization with Delay-free Parameters [9.062164411594175]
  本稿では,2つの分散アルゴリズム, Prox-DGD と DGD-ATC の非同期バージョンを開発し,無方向性ネットワーク上でのコンセンサス最適化問題を解く。 代替アルゴリズムとは対照的に,我々のアルゴリズムは,遅延に依存しないステップサイズを用いて,同期アルゴリズムの固定点集合に収束することができる。
  論文  参考訳（メタデータ） (2023-12-11T16:33:38Z)
• AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms [45.90015262911875]
  不均一な環境で分散SGDのための非同期型アルゴリズムを解析する。 また,本分析の副産物として,ランダムなきついSGDのような勾配型アルゴリズムの保証を示す。
  論文  参考訳（メタデータ） (2023-10-31T13:44:53Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Breaking the Convergence Barrier: Optimization via Fixed-Time Convergent Flows [4.817429789586127]
  本稿では, 固定時間安定力学系の概念に基づいて, 加速を実現するための多言語最適化フレームワークを提案する。 提案手法の高速化された収束特性を,最先端の最適化アルゴリズムに対して様々な数値例で検証する。
  論文  参考訳（メタデータ） (2021-12-02T16:04:40Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。 ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。 我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
  論文  参考訳（メタデータ） (2021-10-20T02:25:25Z)
• Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization [47.03235286622727]
  我々は,従来の非加速法と同じ線形高速化条件を必要とすることを証明した。 我々の中心となるアルゴリズム発見は、スパース更新を伴う新しい加速SVRG変種である。
  論文  参考訳（メタデータ） (2021-09-30T17:36:32Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• Decentralized Optimization with Heterogeneous Delays: a Continuous-Time Approach [6.187780920448871]
  非同期アルゴリズムを解析するための新しい連続時間フレームワークを提案する。 我々は,スムーズな凸関数と強い凸関数の和を最小化するために,完全に非同期な分散アルゴリズムを記述する。
  論文  参考訳（メタデータ） (2021-06-07T13:09:25Z)
• Stochastic Optimization with Laggard Data Pipelines [65.20044914532221]
  共通最適化手法の「データ抽出」拡張は同期手法よりも優れた性能を示すことを示す。 具体的には、ミニバッチによる凸最適化において、データエコーは、最適統計率を維持しながら収束率の曲率に支配される部分の高速化をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-10-26T14:55:31Z)
• A Hybrid-Order Distributed SGD Method for Non-Convex Optimization to Balance Communication Overhead, Computational Complexity, and Convergence Rate [28.167294398293297]
  通信負荷の少ない分散勾配降下法(SGD)を提案する。 各イテレーションにおける計算複雑性を低減するために、ワーカノードは、方向微分をゼロ階勾配推定で近似する。
  論文  参考訳（メタデータ） (2020-03-27T14:02:15Z)

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

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