論文の概要: Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations

• arxiv url: http://arxiv.org/abs/2405.15545v1
• Date: Fri, 24 May 2024 13:33:30 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-27 13:59:53.566592
• Title: Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations
• Title（参考訳）: Freya PAGE:不均一非同期計算を用いた大規模非凸有限和最適化のための最初の最適時間複雑性
• Authors: Alexander Tyurin, Kaja Gruntkowska, Peter Richtárik,
• Abstract要約: 実用的な分散システムでは、労働者は概して均質ではなく、非常に多様な処理時間を持つ。 本稿では、任意に遅い計算を扱うための新しい並列手法Freyaを提案する。 Freyaは従来の手法と比較して,複雑性の保証が大幅に向上していることを示す。
• 参考スコア（独自算出の注目度）: 92.1840862558718
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: In practical distributed systems, workers are typically not homogeneous, and due to differences in hardware configurations and network conditions, can have highly varying processing times. We consider smooth nonconvex finite-sum (empirical risk minimization) problems in this setup and introduce a new parallel method, Freya PAGE, designed to handle arbitrarily heterogeneous and asynchronous computations. By being robust to "stragglers" and adaptively ignoring slow computations, Freya PAGE offers significantly improved time complexity guarantees compared to all previous methods, including Asynchronous SGD, Rennala SGD, SPIDER, and PAGE, while requiring weaker assumptions. The algorithm relies on novel generic stochastic gradient collection strategies with theoretical guarantees that can be of interest on their own, and may be used in the design of future optimization methods. Furthermore, we establish a lower bound for smooth nonconvex finite-sum problems in the asynchronous setup, providing a fundamental time complexity limit. This lower bound is tight and demonstrates the optimality of Freya PAGE in the large-scale regime, i.e., when $\sqrt{m} \geq n$, where $n$ is # of workers, and $m$ is # of data samples.
• Abstract（参考訳）: 実用分散システムでは、ワーカは概して均一ではなく、ハードウェア構成やネットワーク条件が異なるため、処理時間が非常に異なる場合がある。 本稿では、このセットアップにおけるスムーズな非凸有限サム問題(経験的リスク最小化)を考察し、任意に不均一かつ非同期な計算を扱うために設計された新しい並列手法Freya PAGEを導入する。 ストラグラー」に頑健であり、遅い計算を適応的に無視することで、Freya PAGEは、Asynchronous SGD、Rennala SGD、SPIDER、PAGEを含む従来のすべてのメソッドと比較して、大幅に改善された時間複雑性を保証する。 このアルゴリズムは、理論上の保証を持つ新しい一般確率勾配収集戦略に依存しており、これはそれ自体が興味を持ち、将来の最適化手法の設計に使用される可能性がある。 さらに、非同期セットアップにおける滑らかな非凸有限サム問題に対する下界を確立し、時間的複雑性の基本的な制限を提供する。 この下限は厳密で、大規模システムにおけるFreya PAGEの最適性を示す。例えば$\sqrt{m} \geq n$, where $n$ is # of workers, and $m$ is # of data sampleである。

関連論文リスト

• Asynchronous Distributed Optimization with Delay-free Parameters [9.062164411594175]
  本稿では,2つの分散アルゴリズム,Prox-DGDとDGD-ATCの非同期バージョンを開発し,無方向性ネットワーク上でのコンセンサス最適化問題を解く。 代替アルゴリズムとは対照的に,我々のアルゴリズムは,遅延に依存しないステップサイズを用いて,同期アルゴリズムの固定点集合に収束することができる。 また、2つの非同期メソッドの収束速度は、最悪の場合に制約されるのではなく、実際の非同期レベルに適応することを示した。
  論文  参考訳（メタデータ） (2023-12-11T16:33:38Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• SYNTHESIS: A Semi-Asynchronous Path-Integrated Stochastic Gradient Method for Distributed Learning in Computing Clusters [7.968142741470549]
  ulstochastic gradulient ulsearchは、同期および非同期分散学習アルゴリズムの制限を克服するために開発された。 algnameアルゴリズムは(O(sqrtNepsilon-2(Delta+1) d+N))と(O(sqrtNepsilon-2(+1) d+N))を持つ (エプシロン)分散共有メモリアーキテクチャにおける非デルタ学習の定常点
  論文  参考訳（メタデータ） (2022-08-17T17:42:33Z)
• Implementation of Parallel Simplified Swarm Optimization in CUDA [2.322689362836168]
  最適化コンピューティングでは、インテリジェントなSwarmアルゴリズム(SIAs)が並列化に適している。 本稿では,計算能力と汎用性を考慮したGPUに基づくSimplified Swarm Algorithm Optimization (PSSO)を提案する。 結果から,Nの次数による時間複雑性の低減が達成され,資源プリエンプションの問題は完全に回避された。
  論文  参考訳（メタデータ） (2021-10-01T00:15:45Z)
• The Minimax Complexity of Distributed Optimization [0.0]
  分散最適化に適用可能な古典的なオラクルフレームワークの拡張である「グラフオラクルモデル」を紹介します。 私は「間欠的コミュニケーション設定」の具体例に焦点をあてる コンベックス設定におけるSGD(Local Descent)アルゴリズムの理論的特性を解析する。
  論文  参考訳（メタデータ） (2021-09-01T15:18:33Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  機械学習に多くの応用がある非SBO問題を考察する。 本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-05T18:28:42Z)

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

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