論文の概要: Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization

• arxiv url: http://arxiv.org/abs/2210.07863v1
• Date: Fri, 14 Oct 2022 14:34:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-17 18:12:45.533451
• Title: Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization
• Title（参考訳）: スムースおよび非凸確率分散最適化のための最適収束率の再検討
• Authors: Kun Yuan, Xinmeng Huang, Yiming Chen, Xiaohan Zhang, Yingya Zhang, Pan Pan
• Abstract要約: 分散最適化は、大規模機械学習におけるコミュニケーションの節約に有効である。 本稿では,一般重量行列を用いた最適収束アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 25.831902182404388
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Decentralized optimization is effective to save communication in large-scale machine learning. Although numerous algorithms have been proposed with theoretical guarantees and empirical successes, the performance limits in decentralized optimization, especially the influence of network topology and its associated weight matrix on the optimal convergence rate, have not been fully understood. While (Lu and Sa, 2021) have recently provided an optimal rate for non-convex stochastic decentralized optimization with weight matrices defined over linear graphs, the optimal rate with general weight matrices remains unclear. This paper revisits non-convex stochastic decentralized optimization and establishes an optimal convergence rate with general weight matrices. In addition, we also establish the optimal rate when non-convex loss functions further satisfy the Polyak-Lojasiewicz (PL) condition. Following existing lines of analysis in literature cannot achieve these results. Instead, we leverage the Ring-Lattice graph to admit general weight matrices while maintaining the optimal relation between the graph diameter and weight matrix connectivity. Lastly, we develop a new decentralized algorithm to nearly attain the above two optimal rates under additional mild conditions.
• Abstract（参考訳）: 分散最適化は、大規模機械学習におけるコミュニケーションの節約に有効である。 理論的な保証と経験的成功で多くのアルゴリズムが提案されているが、分散最適化における性能限界、特にネットワークトポロジーとその関連する重み行列が最適収束率に与える影響は、完全には理解されていない。 Lu と Sa, 2021) は近年,線形グラフ上で定義された重み行列を用いた非凸確率分散最適化の最適速度を提供してきたが,一般重み行列を用いた最適速度はいまだ不明である。 本稿では,非凸確率分散最適化を再検討し,一般重み行列による最適収束率を確立する。 さらに,非凸損失関数がPolyak-Lojasiewicz (PL) 条件をさらに満たす場合の最適速度も確立する。 既存の文献分析の系統に従うと、これらの結果が得られない。 代わりに、Ring-Latticeグラフを利用して、グラフの直径と重み行列接続の最適関係を維持しながら、一般的な重み行列を許容する。 最後に,より穏やかな条件下で上述の2つの最適速度をほぼ満たす新しい分散アルゴリズムを開発した。

関連論文リスト

• Composite Optimization Algorithms for Sigmoid Networks [3.160070867400839]
  線形化近位アルゴリズムと乗算器の交互方向に基づく合成最適化アルゴリズムを提案する。 フランク関数のフィッティングに関する数値実験により、提案アルゴリズムは十分堅牢に機能することを示した。
  論文  参考訳（メタデータ） (2023-03-01T15:30:29Z)
• Decentralized Inexact Proximal Gradient Method With Network-Independent Stepsizes for Convex Composite Optimization [39.352542703876104]
  本稿では,非方向および接続ネットワーク上での分散凸複合最適化について考察する。 CTA(Combine-Then-Adapt)に基づく新しい分散アルゴリズムは、非協調的なネットワーク非依存の定数ステップサイズの下で提案される。
  論文  参考訳（メタデータ） (2023-02-07T03:50:38Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。 本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。 3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
  論文  参考訳（メタデータ） (2022-09-27T09:06:37Z)
• Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares [68.8204255655161]
  非最適化近似問題を考える。 本稿では,最優先計算を保証するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-04-11T09:37:04Z)
• Generalization Properties of Stochastic Optimizers via Trajectory Analysis [48.38493838310503]
  本稿では,Fernique-Talagrand関数と局所パワーローの両方が一般化性能の予測可能であることを示す。 本稿では,Fernique-Talagrand関数と局所パワーローの両方が一般化性能の予測可能であることを示す。
  論文  参考訳（メタデータ） (2021-08-02T10:58:32Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  バイレベル最適化は多くの機械学習問題に対するツールである。 Stoc-BiO という新しい確率効率勾配推定器を提案する。
  論文  参考訳（メタデータ） (2020-10-15T18:09:48Z)
• Stochastic Coordinate Minimization with Progressive Precision for Stochastic Convex Optimization [16.0251555430107]
  凸最適化のための反復座標最小化(CM)に基づくフレームワークを開発した。 最適精度制御と結果の順序-最適後悔性能を確立する。 提案アルゴリズムは,大規模最適化のためのCMのスケーラビリティと並列性特性を継承し,オンライン実装に適したアルゴリズムである。
  論文  参考訳（メタデータ） (2020-03-11T18:42:40Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  適応性は現代最適化理論において重要であるが、研究されていない性質である。 提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
  論文  参考訳（メタデータ） (2020-02-13T05:42:27Z)

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

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