論文の概要: SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2411.14166v1
- Date: Thu, 21 Nov 2024 14:23:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-22 15:20:00.588433
- Title: SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimization
- Title(参考訳): SPARKLE: 分散バイレベル最適化のための統一された単一ループプリマルデュアルフレームワーク
- Authors: Shuchen Zhu, Boao Kong, Songtao Lu, Xinmeng Huang, Kun Yuan,
- Abstract要約: 本稿では,複数のエージェントが協調して,近傍通信によるネスト最適化構造に関わる問題を解く分散二段階最適化について検討する。
SPARKLE(Single-loop Primal-dual AlgoRithm frameworK)を提案する。
本稿では,SPARKLEの統一収束解析を行い,既存の分散二段階アルゴリズムと比較して,最先端の収束率を持つ全変種に適用する。
- 参考スコア(独自算出の注目度): 35.92829763686735
- License:
- Abstract: This paper studies decentralized bilevel optimization, in which multiple agents collaborate to solve problems involving nested optimization structures with neighborhood communications. Most existing literature primarily utilizes gradient tracking to mitigate the influence of data heterogeneity, without exploring other well-known heterogeneity-correction techniques such as EXTRA or Exact Diffusion. Additionally, these studies often employ identical decentralized strategies for both upper- and lower-level problems, neglecting to leverage distinct mechanisms across different levels. To address these limitations, this paper proposes SPARKLE, a unified Single-loop Primal-dual AlgoRithm frameworK for decentraLized bilEvel optimization. SPARKLE offers the flexibility to incorporate various heterogeneitycorrection strategies into the algorithm. Moreover, SPARKLE allows for different strategies to solve upper- and lower-level problems. We present a unified convergence analysis for SPARKLE, applicable to all its variants, with state-of-the-art convergence rates compared to existing decentralized bilevel algorithms. Our results further reveal that EXTRA and Exact Diffusion are more suitable for decentralized bilevel optimization, and using mixed strategies in bilevel algorithms brings more benefits than relying solely on gradient tracking.
- Abstract(参考訳): 本稿では,複数のエージェントが協調して,近傍通信によるネスト最適化構造に関わる問題を解く分散二段階最適化について検討する。
既存の文献の多くは、EXTRAやExact Diffusionのような他のよく知られた不均一性補正技術を探ることなく、データ不均一性の影響を軽減するために勾配追跡を利用する。
さらに、これらの研究は上層と下層の両方の問題に対して同一の分散戦略を採用することが多く、異なるレベルの異なるメカニズムを活用することは無視される。
これらの制約に対処するため,SPARKLEという単一ループPrimal-Dual AlgoRithm frameworKをアジュラライズしたbilEvel最適化のために提案する。
SPARKLEは様々な異種補正戦略をアルゴリズムに組み込む柔軟性を提供する。
さらに、SPARKLEは、上層と下層の問題を解決するための異なる戦略を可能にする。
本稿では,SPARKLEの統一収束解析を行い,既存の分散二段階アルゴリズムと比較して,最先端の収束率を持つ全変種に適用する。
さらに, EXTRA と Exact Diffusion は分散二段階最適化に適しており,二段階アルゴリズムに混合戦略を用いることで,勾配追跡のみに頼らずに利益が得られることを示した。
関連論文リスト
- A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [66.61399765513383]
We developed a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints。
2つのよく知られた実世界のアプリケーションでその効果を実証する。
論文 参考訳(メタデータ) (2024-06-14T15:59:36Z) - On the Communication Complexity of Decentralized Bilevel Optimization [40.45379954138305]
本稿では,更新戦略の同時および交互化に基づく2つの新しい分散二段階勾配勾配アルゴリズムを提案する。
我々のアルゴリズムは既存の手法よりも高速な収束率と通信コストを抑えることができる。
このような理論的な結果は、不均一な環境での軽微な仮定で達成されたのはこれが初めてである。
論文 参考訳(メタデータ) (2023-11-19T14:56:26Z) - A Single-Loop Algorithm for Decentralized Bilevel Optimization [11.67135350286933]
そこで本研究では,分散化された二段階最適化を低レベルに凸した問題で解くための新しい単一ループアルゴリズムを提案する。
提案手法は,反復毎に2つの行列ベクトル乗算のみを用いることで,過勾配を近似する完全単ループ法である。
解析により,提案アルゴリズムは二段階最適化アルゴリズムにおいて最もよく知られた収束率を実現することを示す。
論文 参考訳(メタデータ) (2023-11-15T13:29:49Z) - 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) - Asynchronous Distributed Bilevel Optimization [20.074079852690048]
本稿では,双方向最適化問題に対処するため,非同期分散双レベル(ADBO)アルゴリズムを提案する。
ADBOが$epsilon$-定常点を得る複雑さは$mathcalO(frac1epsilon 2)$によって上界される。
論文 参考訳(メタデータ) (2022-12-20T07:44:48Z) - On the Convergence of Distributed Stochastic Bilevel Optimization
Algorithms over a Network [55.56019538079826]
バイレベル最適化は、幅広い機械学習モデルに適用されている。
既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。
そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-06-30T05:29:52Z) - Resource Allocation via Model-Free Deep Learning in Free Space Optical
Communications [119.81868223344173]
本稿では,自由空間光学(FSO)通信におけるチャネルフェージング効果の緩和のための資源配分の一般的な問題について検討する。
本フレームワークでは,FSO資源割り当て問題を解決する2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-07-27T17:38:51Z) - A Generic First-Order Algorithmic Framework for Bi-Level Programming
Beyond Lower-Level Singleton [49.23948907229656]
Bi-level Descent Aggregationは、汎用的な双方向最適化のためのフレキシブルでモジュール化されたアルゴリズムフレームワークである。
LLS条件なしでBDAの収束を証明する新しい手法を導出する。
我々の研究は、BDAが特定の一階計算モジュールの検証と互換性があることも示している。
論文 参考訳(メタデータ) (2020-06-07T05:18:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。