論文の概要: Fully First-Order Methods for Decentralized Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2410.19319v1
- Date: Fri, 25 Oct 2024 06:11:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-28 13:33:34.362505
- Title: Fully First-Order Methods for Decentralized Bilevel Optimization
- Title（参考訳）: 分散二段階最適化のための完全一階法
- Authors: Xiaoyu Wang, Xuxing Chen, Shiqian Ma, Tong Zhang,
- Abstract要約: 本稿では,エージェントが隣人とのみ通信する分散二段階最適化(DSBO)に焦点を当てる。
本稿では,既存の作品に広く採用されている2次オラクルよりもはるかに安価な1次オラクルのみを必要とする新しいアルゴリズムである,分散グラディエントDescent and Ascent with Gradient Tracking (DSGDA-GT)を提案する。
- 参考スコア（独自算出の注目度）: 17.20330936572045
- License:
- Abstract: This paper focuses on decentralized stochastic bilevel optimization (DSBO) where agents only communicate with their neighbors. We propose Decentralized Stochastic Gradient Descent and Ascent with Gradient Tracking (DSGDA-GT), a novel algorithm that only requires first-order oracles that are much cheaper than second-order oracles widely adopted in existing works. We further provide a finite-time convergence analysis showing that for $n$ agents collaboratively solving the DSBO problem, the sample complexity of finding an $\epsilon$-stationary point in our algorithm is $\mathcal{O}(n^{-1}\epsilon^{-7})$, which matches the currently best-known results of the single-agent counterpart with linear speedup. The numerical experiments demonstrate both the communication and training efficiency of our algorithm.
- Abstract（参考訳）: 本稿では,エージェントが隣人とのみ通信する分散確率的二段階最適化(DSBO)に焦点を当てる。
本稿では,既存の作品で広く採用されている2次オラクルよりもはるかに安価な1次オラクルのみを必要とする新しいアルゴリズムである,分散確率勾配Descent and Ascent with Gradient Tracking (DSGDA-GT)を提案する。
さらに、DSBO問題を協調的に解く$n$エージェントについて、我々のアルゴリズムで$\epsilon$-stationary pointを見つける際のサンプルの複雑さが$\mathcal{O}(n^{-1}\epsilon^{-7})$であることを示す有限時間収束解析を行った。
数値実験により,本アルゴリズムの通信効率と訓練効率の両立を実証した。
関連論文リスト
- Faster Adaptive Decentralized Learning Algorithms [24.379734053137597]
適応学習と有限サム最適化のための高速分散非分散アルゴリズム(AdaMDOSとAdaMDOF)のクラスを提案する。
いくつかの実験結果から,アルゴリズムの有効性が示された。
論文 参考訳（メタデータ） (2024-08-19T08:05:33Z) - Communication-Efficient Federated Bilevel Optimization with Local and
Global Lower Level Problems [118.00379425831566]
我々はFedBiOAccという通信効率の高いアルゴリズムを提案する。
我々は、FedBiOAcc-Localがこの種の問題に対して同じ速度で収束していることを証明する。
実験結果から,アルゴリズムの性能が向上した。
論文 参考訳（メタデータ） (2023-02-13T21:28:53Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - Decentralized Gossip-Based Stochastic Bilevel Optimization over
Communication Networks [42.76623191830371]
本稿では,ゴシップに基づく分散二段階最適化アルゴリズムを提案する。
エージェントはネットワークと外部の両方の問題を一度に解くことができる。
我々のアルゴリズムは最先端の効率とテスト精度を達成する。
論文 参考訳（メタデータ） (2022-06-22T06:38:54Z) - Finite-Time Analysis of Fully Decentralized Single-Timescale
Actor-Critic [4.94128206910124]
本稿では,アクタ,批評家,グローバル報酬推定器を交互に更新する,完全に分散化されたアクタ・クリティカル(AC)アルゴリズムを提案する。
このアルゴリズムは,Markovian サンプリングにおいて $tildemathcalO(epsilon-2)$ のサンプル複雑性を持つことを示す。
また、我々のアルゴリズムのローカルアクションプライバシ保護バージョンとその分析も提供する。
論文 参考訳（メタデータ） (2022-06-12T13:14:14Z) - Local Stochastic Bilevel Optimization with Momentum-Based Variance
Reduction [104.41634756395545]
具体的には、まず、決定論的勾配に基づくアルゴリズムであるFedBiOを提案する。
FedBiOの複雑性は$O(epsilon-1.5)$である。
本アルゴリズムは数値実験において,他のベースラインと比較して優れた性能を示す。
論文 参考訳（メタデータ） (2022-05-03T16:40:22Z) - Sample and Communication-Efficient Decentralized Actor-Critic Algorithms
with Finite-Time Analysis [27.21581944906418]
Actor-critic (AC)アルゴリズムは分散マルチエージェントシステムで広く採用されている。
我々は、プライベートでサンプルと通信効率のよい2つの分散ACと自然交流(NAC)アルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-09-08T15:02:21Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with
Near-Optimal Sample Complexity and Communication Complexity [13.100926925535578]
マルチエージェントオフポリシーTD学習のための2つの分散型TD補正(TDC)アルゴリズムを開発しています。
提案アルゴリズムは,エージェントの行動,ポリシー,報酬の完全なプライバシを保持し,サンプリングのばらつきと通信頻度を低減するためにミニバッチサンプリングを採用する。
論文 参考訳（メタデータ） (2021-03-24T12:48:08Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。