論文の概要: Decentralized Bilevel Optimization over Graphs: Loopless Algorithmic
Update and Transient Iteration Complexity
- arxiv url: http://arxiv.org/abs/2402.03167v2
- Date: Mon, 26 Feb 2024 11:30:42 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-27 18:40:09.520131
- Title: Decentralized Bilevel Optimization over Graphs: Loopless Algorithmic
Update and Transient Iteration Complexity
- Title(参考訳): グラフ上の分散バイレベル最適化:ループレスアルゴリズム更新と過渡反復複雑性
- Authors: Boao Kong, Shuchen Zhu, Songtao Lu, Xinmeng Huang, Kun Yuan
- Abstract要約: 単一ループ分散SBO(D-SOBA)アルゴリズムを導入し,その過渡的複雑性を確立する。
D-SOBAは、より緩和された仮定の下で、最先端の速度、勾配/ヘッセンの複雑さ、過渡的な反復の複雑さを達成する。
- 参考スコア(独自算出の注目度): 38.54552875789929
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Stochastic bilevel optimization (SBO) is becoming increasingly essential in
machine learning due to its versatility in handling nested structures. To
address large-scale SBO, decentralized approaches have emerged as effective
paradigms in which nodes communicate with immediate neighbors without a central
server, thereby improving communication efficiency and enhancing algorithmic
robustness. However, current decentralized SBO algorithms face challenges,
including expensive inner-loop updates and unclear understanding of the
influence of network topology, data heterogeneity, and the nested bilevel
algorithmic structures. In this paper, we introduce a single-loop decentralized
SBO (D-SOBA) algorithm and establish its transient iteration complexity, which,
for the first time, clarifies the joint influence of network topology and data
heterogeneity on decentralized bilevel algorithms. D-SOBA achieves the
state-of-the-art asymptotic rate, asymptotic gradient/Hessian complexity, and
transient iteration complexity under more relaxed assumptions compared to
existing methods. Numerical experiments validate our theoretical findings.
- Abstract(参考訳): SBO(Stochastic bilevel optimization)は、ネスト構造を扱う汎用性のため、機械学習においてますます重要になっている。
大規模SBOに対処するため,ノードが中央サーバを使わずに隣接ノードと通信する効果的なパラダイムとして分散化アプローチが登場し,通信効率が向上し,アルゴリズムの堅牢性が向上した。
しかし、現在の分散SBOアルゴリズムは、高価なインナーループ更新や、ネットワークトポロジ、データ不均一性、ネストされた双レベルアルゴリズム構造の影響の不明な理解など、課題に直面している。
本稿では、単一ループ分散SBO(D-SOBA)アルゴリズムを導入し、その過渡反復複雑性を確立し、ネットワークトポロジとデータヘテロジニティが分散二段階アルゴリズムに与える影響を初めて明らかにする。
D-SOBAは、既存の方法と比較してより緩和された仮定の下で、最先端の漸近速度、漸近勾配/ヘッセン複雑性、過渡反復複雑性を達成する。
数値実験は我々の理論的な結果を検証する。
関連論文リスト
- On the Communication Complexity of Decentralized Bilevel Optimization [44.19286981781694]
異種環境下での分散二段階勾配降下アルゴリズムを開発した。
我々の知る限りでは、これは不均一な条件下でこれらの理論結果を達成する最初のアルゴリズムである。
論文 参考訳(メタデータ) (2023-11-19T14:56:26Z) - Stability and Generalization of the Decentralized Stochastic Gradient
Descent Ascent Algorithm [80.94861441583275]
本稿では,分散勾配勾配(D-SGDA)アルゴリズムの一般化境界の複雑さについて検討する。
本研究は,D-SGDAの一般化における各因子の影響を解析した。
また、最適凸凹設定を得るために一般化とバランスをとる。
論文 参考訳(メタデータ) (2023-10-31T11:27:01Z) - Stochastic Multi-Level Compositional Optimization Algorithms over
Networks with Level-Independent Convergence Rate [22.988563731766586]
マルチレベル関数を扱うために,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) - DIAMOND: Taming Sample and Communication Complexities in Decentralized
Bilevel Optimization [27.317118892531827]
我々は、DIAMOND(運動量と勾配追跡を伴う分散単時間スケール近似)と呼ばれる新しい分散二段階最適化を開発する。
我々はDIAMONDが$mathcalO(epsilon-3/2)$をサンプルと通信の複雑さで楽しむことを示し、$epsilon$-stationaryソリューションを実現する。
論文 参考訳(メタデータ) (2022-12-05T15:58:00Z) - A Penalty-Based Method for Communication-Efficient Decentralized Bilevel
Programming [14.35928967799696]
バイレベルプログラミングは、その幅広い応用のために、最近この文献で注目を集めている。
基礎となる双レベル最適化問題は、1台のマシンか、星型ネットワークに接続された複数のマシンのどちらかによって解決される。
本稿では,このクラスの最適化問題を理論的に保証したペナルティ関数に基づく分散アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-11-08T08:39:30Z) - Optimal Complexity in Non-Convex Decentralized Learning over
Time-Varying Networks [8.860889476382594]
時間変化ネットワークによる分散最適化は、機械学習の新たなパラダイムである。
大規模な深層トレーニングでは通信オーバーヘッドが大幅に削減され、特にノードの移動時の無線シナリオでは堅牢になる。
論文 参考訳(メタデータ) (2022-11-01T15:37:54Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳(メタデータ) (2021-06-08T15:54:44Z) - Communication-Efficient Distributed Stochastic AUC Maximization with
Deep Neural Networks [50.42141893913188]
本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。
我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。
いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
論文 参考訳(メタデータ) (2020-05-05T18:08:23Z) - Quantized Decentralized Stochastic Learning over Directed Graphs [52.94011236627326]
有向グラフ上で通信する計算ノード間でデータポイントが分散される分散学習問題を考える。
モデルのサイズが大きくなるにつれて、分散学習は、各ノードが隣人にメッセージ(モデル更新)を送信することによる通信負荷の大きなボトルネックに直面します。
本稿では,分散コンセンサス最適化におけるプッシュサムアルゴリズムに基づく有向グラフ上の量子化分散学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-23T18:25:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。