論文の概要: Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks

• arxiv url: http://arxiv.org/abs/2405.18031v1
• Date: Tue, 28 May 2024 10:28:45 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-29 19:08:25.399311
• Title: Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks
• Title（参考訳）: 時変ネットワーク上の非平滑凸分散最適化のための下界と最適アルゴリズム
• Authors: Dmitry Kovalev, Ekaterina Borodich, Alexander Gasnikov, Dmitrii Feoktistov,
• Abstract要約: 通信ネットワークのノード間で分散的に格納された凸関数の総和を最小化するタスクについて検討する。 この問題を解決するのに必要な分散通信数と(サブ)漸進計算の下位境界が確立されている。 我々は,これらの下界に適合する最初の最適アルゴリズムを開発し,既存の最先端技術と比較して理論性能を著しく向上させる。
• 参考スコア（独自算出の注目度）: 57.24087627267086
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the task of minimizing the sum of convex functions stored in a decentralized manner across the nodes of a communication network. This problem is relatively well-studied in the scenario when the objective functions are smooth, or the links of the network are fixed in time, or both. In particular, lower bounds on the number of decentralized communications and (sub)gradient computations required to solve the problem have been established, along with matching optimal algorithms. However, the remaining and most challenging setting of non-smooth decentralized optimization over time-varying networks is largely underexplored, as neither lower bounds nor optimal algorithms are known in the literature. We resolve this fundamental gap with the following contributions: (i) we establish the first lower bounds on the communication and subgradient computation complexities of solving non-smooth convex decentralized optimization problems over time-varying networks; (ii) we develop the first optimal algorithm that matches these lower bounds and offers substantially improved theoretical performance compared to the existing state of the art.
• Abstract（参考訳）: 通信ネットワークのノード間で分散的に格納された凸関数の総和を最小化するタスクについて検討する。 この問題は、目的関数が滑らかな場合や、ネットワークのリンクが時間内に固定されている場合、あるいはその両方において比較的よく研究されている。 特に、分散化された通信数と(サブ)漸進的な計算の下位境界が、一致する最適アルゴリズムと共に確立されている。 しかしながら、時間的変化のあるネットワーク上での非平滑な分散最適化の残りかつ最も困難な設定は、下限や最適アルゴリズムが文献で知られていないため、ほとんど探索されていない。 私たちは以下の貢献でこの根本的なギャップを解決します。 i) 時間変動ネットワーク上での非平滑凸分散最適化問題の解法において, 通信と下降計算の複雑さについて, 第一の下位境界を確立する。 (II)これらの下界に適合し,既存の最先端技術と比較して理論性能を著しく向上させる,最初の最適アルゴリズムを開発する。

関連論文リスト

• Federated Multi-Level Optimization over Decentralized Networks [55.776919718214224]
  エージェントが隣人としか通信できないネットワーク上での分散マルチレベル最適化の問題について検討する。 ネットワーク化されたエージェントが1つの時間スケールで異なるレベルの最適化問題を解くことができる新しいゴシップに基づく分散マルチレベル最適化アルゴリズムを提案する。 提案アルゴリズムは, ネットワークサイズと線形にスケーリングし, 各種アプリケーション上での最先端性能を示す。
  論文  参考訳（メタデータ） (2023-10-10T00:21:10Z)
• Adaptive Consensus: A network pruning approach for decentralized optimization [0.5432724320036953]
  ネットワーク内の各ノードが局所関数を持つネットワークベースの分散最適化問題を考える。 目的は、すべての局所関数の和を最小化するコンセンサス解を集合的に達成することである。 本稿では,通信量を削減する適応的ランダム化通信効率アルゴリズムフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-09-06T00:28:10Z)
• Can Decentralized Stochastic Minimax Optimization Algorithms Converge Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
  分散化されたミニマックス最適化は、幅広い機械学習に応用されているため、ここ数年で活発に研究されている。 本稿では,非コンカブ問題に対する2つの新しい分散化ミニマックス最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-24T02:19:39Z)
• Decentralized Inexact Proximal Gradient Method With Network-Independent Stepsizes for Convex Composite Optimization [39.352542703876104]
  本稿では,非方向および接続ネットワーク上での分散凸複合最適化について考察する。 CTA(Combine-Then-Adapt)に基づく新しい分散アルゴリズムは、非協調的なネットワーク非依存の定数ステップサイズの下で提案される。
  論文  参考訳（メタデータ） (2023-02-07T03:50:38Z)
• Optimal Complexity in Non-Convex Decentralized Learning over Time-Varying Networks [8.860889476382594]
  時間変化ネットワークによる分散最適化は、機械学習の新たなパラダイムである。 大規模な深層トレーニングでは通信オーバーヘッドが大幅に削減され、特にノードの移動時の無線シナリオでは堅牢になる。
  論文  参考訳（メタデータ） (2022-11-01T15:37:54Z)
• DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization [43.31016937305845]
  インターネット・オブ・シング、ネットワークセンシング、自律システム、有限サム最適化のための分散アルゴリズムのためのフェデレーション学習。 非有限サム最適化のためのDecentralized STochastic Recursive MethodDESTRESSを開発した。 詳細な理論的および数値的な比較は、DESTRESSが事前の分散アルゴリズムにより改善されていることを示している。
  論文  参考訳（メタデータ） (2021-10-04T03:17:41Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)

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

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