論文の概要: DIAMOND: Taming Sample and Communication Complexities in Decentralized Bilevel Optimization

• arxiv url: http://arxiv.org/abs/2212.02376v1
• Date: Mon, 5 Dec 2022 15:58:00 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-06 19:20:40.822019
• Title: DIAMOND: Taming Sample and Communication Complexities in Decentralized Bilevel Optimization
• Title（参考訳）: DIAMOND: 分散バイレベル最適化におけるサンプルと通信の複雑さ
• Authors: Peiwen Qiu, Yining Li, Zhuqing Liu, Prashant Khanduri, Jia Liu, Ness B. Shroff, Elizabeth Serena Bentley, Kurt Turck
• Abstract要約: 我々は、DIAMOND(運動量と勾配追跡を伴う分散単時間スケール近似)と呼ばれる新しい分散二段階最適化を開発する。 我々はDIAMONDが$mathcalO(epsilon-3/2)$をサンプルと通信の複雑さで楽しむことを示し、$epsilon$-stationaryソリューションを実現する。
• 参考スコア（独自算出の注目度）: 27.317118892531827
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Decentralized bilevel optimization has received increasing attention recently due to its foundational role in many emerging multi-agent learning paradigms (e.g., multi-agent meta-learning and multi-agent reinforcement learning) over peer-to-peer edge networks. However, to work with the limited computation and communication capabilities of edge networks, a major challenge in developing decentralized bilevel optimization techniques is to lower sample and communication complexities. This motivates us to develop a new decentralized bilevel optimization called DIAMOND (decentralized single-timescale stochastic approximation with momentum and gradient-tracking). The contributions of this paper are as follows: i) our DIAMOND algorithm adopts a single-loop structure rather than following the natural double-loop structure of bilevel optimization, which offers low computation and implementation complexity; ii) compared to existing approaches, the DIAMOND algorithm does not require any full gradient evaluations, which further reduces both sample and computational complexities; iii) through a careful integration of momentum information and gradient tracking techniques, we show that the DIAMOND algorithm enjoys $\mathcal{O}(\epsilon^{-3/2})$ in sample and communication complexities for achieving an $\epsilon$-stationary solution, both of which are independent of the dataset sizes and significantly outperform existing works. Extensive experiments also verify our theoretical findings.
• Abstract（参考訳）: 分散化された双レベル最適化は、ピアツーピアエッジネットワークにおける多くの新興マルチエージェント学習パラダイム(マルチエージェントメタラーニングやマルチエージェント強化学習など)の基盤的役割により、近年注目を集めている。 しかしながら、エッジネットワークの限られた計算能力と通信能力を扱うために、分散二レベル最適化技術を開発する上での課題は、サンプルと通信の複雑さを減らすことである。 これは、ダイアモンド(運動量と勾配追跡を伴う分散単時間スケール確率近似)と呼ばれる新しい分散二段階最適化を開発する動機となった。 本論文の貢献は以下のとおりである。 i)DIAMONDアルゴリズムは,2レベル最適化の自然な二重ループ構造に従わず,単一ループ構造を採用する。 二 ダイヤモンドアルゴリズムは、既存の方法と比較して、完全な勾配評価を必要としないため、試料及び計算の複雑さを更に低減する。 iii) モーメント情報と勾配追跡手法の注意深い統合により,DIAMONDアルゴリズムはサンプルおよび通信複雑度において$\mathcal{O}(\epsilon^{-3/2})$を享受し,それぞれがデータセットサイズに依存しず,既存の作業を大幅に上回っていることを示す。 大規模な実験も理論的な結果を検証する。

関連論文リスト

• Decentralized Bilevel Optimization over Graphs: Loopless Algorithmic Update and Transient Iteration Complexity [38.54552875789929]
  単一ループ分散SBO(D-SOBA)アルゴリズムを導入し,その過渡的複雑性を確立する。 D-SOBAは、より緩和された仮定の下で、最先端の速度、勾配/ヘッセンの複雑さ、過渡的な反復の複雑さを達成する。
  論文  参考訳（メタデータ） (2024-02-05T16:35:30Z)
• Decentralized Multi-Level Compositional Optimization Algorithms with Level-Independent Convergence Rate [26.676582181833584]
  分散化されたマルチレベル最適化は、マルチレベル構造と分散通信のために困難である。 マルチレベル構成問題を最適化する2つの新しい分散最適化アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-06-06T00:23:28Z)
• Stochastic Unrolled Federated Learning [85.6993263983062]
  本稿では,UnRolled Federated Learning (SURF)を導入する。 提案手法は,この拡張における2つの課題,すなわち,非学習者へのデータセット全体の供給の必要性と,フェデレート学習の分散的性質に対処する。
  論文  参考訳（メタデータ） (2023-05-24T17:26:22Z)
• Communication-Efficient Federated Bilevel Optimization with Local and Global Lower Level Problems [118.00379425831566]
  我々はFedBiOAccという通信効率の高いアルゴリズムを提案する。 我々は、FedBiOAcc-Localがこの種の問題に対して同じ速度で収束していることを証明する。 実験結果から,アルゴリズムの性能が向上した。
  論文  参考訳（メタデータ） (2023-02-13T21:28:53Z)
• INTERACT: Achieving Low Sample and Communication Complexities in Decentralized Bilevel Learning over Networks [24.02913189682224]
  分散化された双方向最適化問題は、ネットワーク機械学習コミュニティで注目を集めている。 低サンプリングと通信の複雑さは、未調査のままである2つの基本的な課題である。 我々の研究は、ネットワーク上の分散化された二段階最適化問題を解決するために、低サンプリングと通信の複雑さの両方を初めて解決した。
  論文  参考訳（メタデータ） (2022-07-27T04:19:28Z)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  バイレベル最適化は、幅広い機械学習モデルに適用されている。 既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。 そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-06-30T05:29:52Z)
• Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks [42.76623191830371]
  本稿では,ゴシップに基づく分散二段階最適化アルゴリズムを提案する。 エージェントはネットワークと外部の両方の問題を一度に解くことができる。 我々のアルゴリズムは最先端の効率とテスト精度を達成する。
  論文  参考訳（メタデータ） (2022-06-22T06:38:54Z)
• Adaptive Stochastic ADMM for Decentralized Reinforcement Learning in Edge Industrial IoT [106.83952081124195]
  強化学習 (Reinforcement Learning, RL) は, 意思決定および最適制御プロセスのための有望な解法として広く研究されている。 本稿では,Adaptive ADMM (asI-ADMM)アルゴリズムを提案する。 実験の結果,提案アルゴリズムは通信コストやスケーラビリティの観点から技術状況よりも優れており,複雑なIoT環境に適応できることがわかった。
  論文  参考訳（メタデータ） (2021-06-30T16:49:07Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• A Low Complexity Decentralized Neural Net with Centralized Equivalence using Layer-wise Learning [49.15799302636519]
  我々は、分散処理ノード(労働者)で最近提案された大規模ニューラルネットワークをトレーニングするために、低複雑性分散学習アルゴリズムを設計する。 我々の設定では、トレーニングデータは作業者間で分散されるが、プライバシやセキュリティ上の懸念からトレーニングプロセスでは共有されない。 本研究では,データが一箇所で利用可能であるかのように,等価な学習性能が得られることを示す。
  論文  参考訳（メタデータ） (2020-09-29T13:08:12Z)

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

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