論文の概要: 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は、既存の方法と比較してより緩和された仮定の下で、最先端の漸近速度、漸近勾配/ヘッセン複雑性、過渡反復複雑性を達成する。
数値実験は我々の理論的な結果を検証する。
関連論文リスト
- 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) - Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
通信ネットワークのノード間で分散的に格納された凸関数の総和を最小化するタスクについて検討する。
この問題を解決するのに必要な分散通信数と(サブ)漸進計算の下位境界が確立されている。
我々は,これらの下界に適合する最初の最適アルゴリズムを開発し,既存の最先端技術と比較して理論性能を著しく向上させる。
論文 参考訳（メタデータ） (2024-05-28T10:28:45Z) - Stability and Generalization of the Decentralized Stochastic Gradient
Descent Ascent Algorithm [80.94861441583275]
本稿では,分散勾配勾配(D-SGDA)アルゴリズムの一般化境界の複雑さについて検討する。
本研究は,D-SGDAの一般化における各因子の影響を解析した。
また、最適凸凹設定を得るために一般化とバランスをとる。
論文 参考訳（メタデータ） (2023-10-31T11:27:01Z) - 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) - 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]
本稿では,分散化ネットワーク上での双方向プログラミング問題の解法として,ペナルティ関数に基づく分散化アルゴリズムを提案する。
提案アルゴリズムの重要な特徴は,ペナルティ関数の過度勾配の推定である。
我々の理論的枠組みは、様々な凸条件下での原問題の最適解に漸近的でない収束を保証する。
論文 参考訳（メタデータ） (2022-11-08T08:39:30Z) - Optimal Complexity in Non-Convex Decentralized Learning over
Time-Varying Networks [8.860889476382594]
時間変化ネットワークによる分散最適化は、機械学習の新たなパラダイムである。
大規模な深層トレーニングでは通信オーバーヘッドが大幅に削減され、特にノードの移動時の無線シナリオでは堅牢になる。
論文 参考訳（メタデータ） (2022-11-01T15:37:54Z) - DESTRESS: Computation-Optimal and Communication-Efficient Decentralized
Nonconvex Finite-Sum Optimization [43.31016937305845]
インターネット・オブ・シング、ネットワークセンシング、自律システム、有限サム最適化のための分散アルゴリズムのためのフェデレーション学習。
非有限サム最適化のためのDecentralized STochastic Recursive MethodDESTRESSを開発した。
詳細な理論的および数値的な比較は、DESTRESSが事前の分散アルゴリズムにより改善されていることを示している。
論文 参考訳（メタデータ） (2021-10-04T03:17:41Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。