論文の概要: On the Communication Complexity of Decentralized Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2311.11342v3
- Date: Mon, 20 May 2024 14:29:06 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-22 00:00:07.604883
- Title: On the Communication Complexity of Decentralized Bilevel Optimization
- Title（参考訳）: 分散二段階最適化の通信複雑性について
- Authors: Yihan Zhang, My T. Thai, Jie Wu, Hongchang Gao,
- Abstract要約: 異種環境下での分散二段階勾配降下アルゴリズムを開発した。
我々の知る限りでは、これは不均一な条件下でこれらの理論結果を達成する最初のアルゴリズムである。
- 参考スコア（独自算出の注目度）: 40.45379954138305
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Decentralized bilevel optimization has been actively studied in the past few years since it has widespread applications in machine learning. However, existing algorithms suffer from large communication complexity caused by the estimation of stochastic hypergradient, limiting their application to real-world tasks. To address this issue, we develop a novel decentralized stochastic bilevel gradient descent algorithm under the heterogeneous setting, which enjoys a small communication cost in each round and a small number of communication rounds. As such, it can achieve a much better communication complexity than existing algorithms without any strong assumptions regarding heterogeneity. To the best of our knowledge, this is the first stochastic algorithm achieving these theoretical results under the heterogeneous setting. At last, the experimental results confirm the efficacy of our algorithm.
- Abstract（参考訳）: 分散二段階最適化は、機械学習に広く応用されているため、ここ数年で活発に研究されている。
しかし、既存のアルゴリズムは確率的過次性の推定によって引き起こされる通信の複雑さに悩まされ、その応用を現実のタスクに限定する。
この問題に対処するため,各ラウンドの通信コストと通信ラウンド数が少ない不均一な条件下で,分散確率的二段階勾配降下アルゴリズムを開発した。
したがって、不均一性に関する強い仮定なしに、既存のアルゴリズムよりもはるかに優れた通信複雑性を実現することができる。
我々の知る限りでは、これは不均一な条件下でこれらの理論結果を達成する最初の確率的アルゴリズムである。
最終的に実験結果により,本アルゴリズムの有効性が確認された。
関連論文リスト
- Towards Differentiable Multilevel Optimization: A Gradient-Based Approach [1.6114012813668932]
本稿では,多レベル最適化のための新しい勾配に基づくアプローチを提案する。
本手法は解の精度と収束速度を両立させながら計算複雑性を著しく低減する。
私たちの知る限りでは、これは暗黙の微分の一般的なバージョンを提供する最初のアルゴリズムの1つである。
論文 参考訳（メタデータ） (2024-10-15T06:17:59Z) - Boosting the Performance of Decentralized Federated Learning via Catalyst Acceleration [66.43954501171292]
本稿では,Catalytics Accelerationを導入し,DFedCataと呼ばれる促進型分散フェデレート学習アルゴリズムを提案する。
DFedCataは、パラメータの不整合に対処するMoreauエンベロープ関数と、アグリゲーションフェーズを加速するNesterovの外挿ステップの2つの主要コンポーネントで構成されている。
実験により, CIFAR10/100における収束速度と一般化性能の両面において, 提案アルゴリズムの利点を実証した。
論文 参考訳（メタデータ） (2024-10-09T06:17:16Z) - Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learning [5.325297567945828]
本稿では,従来の手法よりもはるかに高速な収束を実現する2段階最適化手法を提案する。
提案アルゴリズムは,様々な条件下で特徴付けられ,オンラインサンプルベース手法に特化していることを示す。
論文 参考訳（メタデータ） (2024-05-15T19:03:08Z) - Decentralized Multi-Level Compositional Optimization Algorithms with Level-Independent Convergence Rate [26.676582181833584]
分散化されたマルチレベル最適化は、マルチレベル構造と分散通信のために困難である。
マルチレベル構成問題を最適化する2つの新しい分散最適化アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-06-06T00:23:28Z) - Communication-Efficient Federated Bilevel Optimization with Local and
Global Lower Level Problems [118.00379425831566]
我々はFedBiOAccという通信効率の高いアルゴリズムを提案する。
我々は、FedBiOAcc-Localがこの種の問題に対して同じ速度で収束していることを証明する。
実験結果から,アルゴリズムの性能が向上した。
論文 参考訳（メタデータ） (2023-02-13T21:28:53Z) - On the Convergence of Distributed Stochastic Bilevel Optimization
Algorithms over a Network [55.56019538079826]
バイレベル最適化は、幅広い機械学習モデルに適用されている。
既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。
そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-06-30T05:29:52Z) - Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
バイレベル最適化は多くの機械学習問題に対するツールである。
Stoc-BiO という新しい確率効率勾配推定器を提案する。
論文 参考訳（メタデータ） (2020-10-15T18:09:48Z) - Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave
Min-Max Problems with PL Condition [52.08417569774822]
本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
論文 参考訳（メタデータ） (2020-06-12T00:32:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。