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

• arxiv url: http://arxiv.org/abs/2106.04469v1
• Date: Tue, 8 Jun 2021 15:54:44 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-09 15:37:10.350170
• Title: Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks
• Title（参考訳）: 時変ネットワーク上の滑らかかつ強凸分散最適化のための下限と最適アルゴリズム
• Authors: Dmitry Kovalev, Elnur Gasanov, Peter Richt\'arik, Alexander Gasnikov
• Abstract要約: 通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
• 参考スコア（独自算出の注目度）: 79.16773494166644
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network whose links are allowed to change in time. We solve two fundamental problems for this task. First, we establish the first lower bounds on the number of decentralized communication rounds and the number of local computations required to find an $\epsilon$-accurate solution. Second, we design two optimal algorithms that attain these lower bounds: (i) a variant of the recently proposed algorithm ADOM (Kovalev et al., 2021) enhanced via a multi-consensus subroutine, which is optimal in the case when access to the dual gradients is assumed, and (ii) a novel algorithm, called ADOM+, which is optimal in the case when access to the primal gradients is assumed. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
• Abstract（参考訳）: 本稿では,リンク変更を許す通信ネットワークのノード間を分散的に格納するスムーズで強い凸関数の和を最小化するタスクについて検討する。 この課題の根本的な問題は2つある。 まず、分散化された通信ラウンド数と$\epsilon$-accurate の解を見つけるのに必要な局所計算数について、最初の下限を確立する。 第2に、この下界を達成する2つの最適アルゴリズムをデザインする: (i) 最近提案されたアルゴリズム adom (kovalev et al., 2021) の変種は、双対勾配へのアクセスが想定される場合に最適であるマルチコンセンサスサブルーチンを介して拡張され、 (ii) 主勾配へのアクセスが想定された場合に最適な新しいアルゴリズム adom+ を設計。 これらのアルゴリズムの理論的効率を,既存の最先端手法との実験的比較によって検証する。

関連論文リスト

• Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
  通信ネットワークのノード間で分散的に格納された凸関数の総和を最小化するタスクについて検討する。 この問題を解決するのに必要な分散通信数と(サブ)漸進計算の下位境界が確立されている。 我々は,これらの下界に適合する最初の最適アルゴリズムを開発し,既存の最先端技術と比較して理論性能を著しく向上させる。
  論文  参考訳（メタデータ） (2024-05-28T10:28:45Z)
• A Single-Loop Algorithm for Decentralized Bilevel Optimization [11.67135350286933]
  そこで本研究では,分散化された二段階最適化を低レベルに凸した問題で解くための新しい単一ループアルゴリズムを提案する。 提案手法は,反復毎に2つの行列ベクトル乗算のみを用いることで,過勾配を近似する完全単ループ法である。 解析により,提案アルゴリズムは二段階最適化アルゴリズムにおいて最もよく知られた収束率を実現することを示す。
  論文  参考訳（メタデータ） (2023-11-15T13:29:49Z)
• Can Decentralized Stochastic Minimax Optimization Algorithms Converge Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
  分散化されたミニマックス最適化は、幅広い機械学習に応用されているため、ここ数年で活発に研究されている。 本稿では,非コンカブ問題に対する2つの新しい分散化ミニマックス最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-24T02:19:39Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization [43.31016937305845]
  インターネット・オブ・シング、ネットワークセンシング、自律システム、有限サム最適化のための分散アルゴリズムのためのフェデレーション学習。 非有限サム最適化のためのDecentralized STochastic Recursive MethodDESTRESSを開発した。 詳細な理論的および数値的な比較は、DESTRESSが事前の分散アルゴリズムにより改善されていることを示している。
  論文  参考訳（メタデータ） (2021-10-04T03:17:41Z)
• Fast block-coordinate Frank-Wolfe algorithm for semi-relaxed optimal transport [26.245086561385282]
  最適輸送(OT)問題は、厳密な大量保存制約を持つ線形プログラミングの解を必要とする。 スパース解を与える高速ブロック座標Frank-Wolfe (BCFW) アルゴリズムを提案する。 色伝達問題における数値的な評価は,提案アルゴリズムが異なる設定で最先端のアルゴリズムより優れていることを示す。
  論文  参考訳（メタデータ） (2021-03-10T03:46:29Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization [21.555331273873175]
  ネットワークのノードにまたがるスムーズな凸関数の和を分散化最小化する作業について検討する。 本稿では,この分散最適化問題に対する2つの新しいアルゴリズムを提案し,複雑性を保証する。
  論文  参考訳（メタデータ） (2020-06-21T11:23:20Z)

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

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