論文の概要: Decentralized Bilevel Optimization: A Perspective from Transient Iteration Complexity
- arxiv url: http://arxiv.org/abs/2402.03167v3
- Date: Mon, 31 Mar 2025 16:15:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-02 14:13:11.033077
- Title: Decentralized Bilevel Optimization: A Perspective from Transient Iteration Complexity
- Title（参考訳）: 分散二段階最適化:過渡的反復複雑性の観点から
- Authors: Boao Kong, Shuchen Zhu, Songtao Lu, Xinmeng Huang, Kun Yuan,
- Abstract要約: 分散二段階最適化(SBO)は機械学習においてますます不可欠になりつつある。
本稿では,分散一ループバイレベルアルゴリズムフレームワークであるD-SOBAを紹介する。
総合的な非漸近収束解析を行い、D-SOBAの過渡的複雑性を確立する。
- 参考スコア（独自算出の注目度）: 35.92829763686735
- License:
- 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, most decentralized SBO algorithms focus solely on asymptotic convergence rates, overlooking transient iteration complexity-the number of iterations required before asymptotic rates dominate, which results in limited understanding of the influence of network topology, data heterogeneity, and the nested bilevel algorithmic structures. To address this issue, this paper introduces D-SOBA, a Decentralized Stochastic One-loop Bilevel Algorithm framework. D-SOBA comprises two variants: D-SOBA-SO, which incorporates second-order Hessian and Jacobian matrices, and D-SOBA-FO, which relies entirely on first-order gradients. We provide a comprehensive non-asymptotic convergence analysis and establish the transient iteration complexity of D-SOBA. This provides the first theoretical understanding of how network topology, data heterogeneity, and nested bilevel structures influence decentralized SBO. Extensive experimental results demonstrate the efficiency and theoretical advantages of D-SOBA.
- Abstract（参考訳）: SBO(Stochastic bilevel optimization)は、ネストされた構造を扱うための汎用性のため、機械学習においてますます重要になっている。
大規模SBOに対処するため,ノードが中央サーバを使わずに隣接ノードと通信する効果的なパラダイムとして分散化アプローチが登場し,通信効率が向上し,アルゴリズムの堅牢性も向上した。
しかし、ほとんどの分散SBOアルゴリズムは、漸近的収束率にのみ焦点をあて、過渡的な反復の複雑さを見越す - 漸近的速度が支配される前に必要となるイテレーションの回数は、ネットワークトポロジ、データ不均一性、ネストされた二段階のアルゴリズム構造の影響を限定的に理解する結果となる。
この問題に対処するため,D-SOBAは分散一ループバイレベルアルゴリズムフレームワークである。
D-SOBAは二階ヘッセン行列とヤコビ行列を含むD-SOBA-SOと、全一階勾配に依存するD-SOBA-FOの2つの変種からなる。
非漸近収束解析を包括的に提供し、D-SOBAの過渡反復複雑性を確立する。
これは、ネットワークトポロジ、データ不均一性、ネストされた二層構造が分散SBOにどのように影響するかに関する最初の理論的理解を提供する。
大規模実験により, 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。