論文の概要: On the Communication Complexity of Decentralized Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2311.11342v2
- Date: Wed, 14 Feb 2024 16:08:10 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-15 19:08:45.218260
- Title: On the Communication Complexity of Decentralized Bilevel Optimization
- Title(参考訳): 分散二レベル最適化の通信複雑性について
- Authors: Yihan Zhang, My T. Thai, Jie Wu, Hongchang Gao
- Abstract要約: 異種環境下での分散二段階勾配降下アルゴリズムを開発した。
我々の知る限りでは、これは不均一な条件下でこれらの理論結果を達成する最初のアルゴリズムである。
- 参考スコア(独自算出の注目度): 44.19286981781694
- 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(参考訳): 分散二レベル最適化は、機械学習に広く応用されて以来、ここ数年で積極的に研究されてきた。
しかし、既存のアルゴリズムは確率的過次性の推定によって引き起こされる通信の複雑さに悩まされ、実際のタスクに限定する。
この問題に対処するために,不均質な設定下で分散確率的二段階勾配降下アルゴリズムを開発し,各ラウンドと少数の通信ラウンドの通信コストを低減した。
したがって、不均一性に関する強い仮定なしに、既存のアルゴリズムよりもはるかに優れた通信複雑性を実現することができる。
我々の知る限りでは、これは不均一な条件下でこれらの理論結果を達成する最初の確率的アルゴリズムである。
実験結果から,本アルゴリズムの有効性が確認された。
関連論文リスト
- Decentralized Bilevel Optimization over Graphs: Loopless Algorithmic
Update and Transient Iteration Complexity [38.54552875789929]
単一ループ分散SBO(D-SOBA)アルゴリズムを導入し,その過渡的複雑性を確立する。
D-SOBAは、より緩和された仮定の下で、最先端の速度、勾配/ヘッセンの複雑さ、過渡的な反復の複雑さを達成する。
論文 参考訳(メタデータ) (2024-02-05T16:35:30Z) - Stochastic Multi-Level Compositional Optimization Algorithms over
Networks with Level-Independent Convergence Rate [22.988563731766586]
マルチレベル関数を扱うために,2つの新しい分散アルゴリズムを開発した。
両アルゴリズムが非レベル依存問題に対する収束率を達成可能であることを示す。
最良の知識のために、これは、分散された設定の設定の下で、レベル非依存の収束率を達成する最初の研究である。
論文 参考訳(メタデータ) (2023-06-06T00:23:28Z) - Can Decentralized Stochastic Minimax Optimization Algorithms Converge
Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
分散化されたミニマックス最適化は、幅広い機械学習に応用されているため、ここ数年で活発に研究されている。
本稿では,非コンカブ問題に対する2つの新しい分散化ミニマックス最適化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-04-24T02:19:39Z) - Communication-Efficient Federated Bilevel Optimization with Local and
Global Lower Level Problems [118.00379425831566]
我々はFedBiOAccという通信効率の高いアルゴリズムを提案する。
我々は、FedBiOAcc-Localがこの種の問題に対して同じ速度で収束していることを証明する。
実験結果から,アルゴリズムの性能が向上した。
論文 参考訳(メタデータ) (2023-02-13T21:28:53Z) - A Penalty-Based Method for Communication-Efficient Decentralized Bilevel
Programming [14.35928967799696]
バイレベルプログラミングは、その幅広い応用のために、最近この文献で注目を集めている。
基礎となる双レベル最適化問題は、1台のマシンか、星型ネットワークに接続された複数のマシンのどちらかによって解決される。
本稿では,このクラスの最適化問題を理論的に保証したペナルティ関数に基づく分散アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-11-08T08:39:30Z) - On the Convergence of Distributed Stochastic Bilevel Optimization
Algorithms over a Network [55.56019538079826]
バイレベル最適化は、幅広い機械学習モデルに適用されている。
既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。
そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-06-30T05:29:52Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳(メタデータ) (2021-06-08T15:54:44Z) - Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。
提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
論文 参考訳(メタデータ) (2020-12-04T15:46:30Z) - Multi-consensus Decentralized Accelerated Gradient Descent [31.76773130271547]
分散凸最適化問題は、大規模機械学習、センサーネットワーク、制御理論に幅広い応用がある。
本稿では,最適な計算複雑性とほぼ最適な通信複雑性を実現する新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-05-02T11:10:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。