論文の概要: Decentralized Gossip-Based Stochastic Bilevel Optimization over
Communication Networks
- arxiv url: http://arxiv.org/abs/2206.10870v1
- Date: Wed, 22 Jun 2022 06:38:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-23 14:46:27.774687
- Title: Decentralized Gossip-Based Stochastic Bilevel Optimization over
Communication Networks
- Title(参考訳): 分散ゴシップに基づく通信ネットワーク上の確率的バイレベル最適化
- Authors: Shuoguang Yang, Xuezhou Zhang, Mengdi Wang
- Abstract要約: 本稿では,ゴシップに基づく分散二段階最適化アルゴリズムを提案する。
エージェントはネットワークと外部の両方の問題を一度に解くことができる。
我々のアルゴリズムは最先端の効率とテスト精度を達成する。
- 参考スコア(独自算出の注目度): 42.76623191830371
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bilevel optimization have gained growing interests, with numerous
applications found in meta learning, minimax games, reinforcement learning, and
nested composition optimization. This paper studies the problem of distributed
bilevel optimization over a network where agents can only communicate with
neighbors, including examples from multi-task, multi-agent learning and
federated learning. In this paper, we propose a gossip-based distributed
bilevel learning algorithm that allows networked agents to solve both the inner
and outer optimization problems in a single timescale and share information via
network propagation. We show that our algorithm enjoys the
$\mathcal{O}(\frac{1}{K \epsilon^2})$ per-agent sample complexity for general
nonconvex bilevel optimization and $\mathcal{O}(\frac{1}{K \epsilon})$ for
strongly convex objective, achieving a speedup that scales linearly with the
network size. The sample complexities are optimal in both $\epsilon$ and $K$.
We test our algorithm on the examples of hyperparameter tuning and
decentralized reinforcement learning. Simulated experiments confirmed that our
algorithm achieves the state-of-the-art training efficiency and test accuracy.
- Abstract(参考訳): 双レベル最適化は、メタラーニング、ミニマックスゲーム、強化学習、ネストされた合成最適化など多くの応用によって、関心が高まりつつある。
本稿では,マルチタスク,マルチエージェント学習,フェデレーション学習など,エージェントが隣人とのみ通信可能なネットワーク上の分散2レベル最適化の問題について検討する。
本稿では,ネットワークエージェントが内部と外部の両方の最適化問題を単一時間スケールで解決し,ネットワーク伝搬を介して情報を共有できる,ゴシップに基づく分散二段階学習アルゴリズムを提案する。
本アルゴリズムは, 一般の非凸二レベル最適化に対して, $\mathcal{O}(\frac{1}{K \epsilon^2})$ per-agent sample complexity と $\mathcal{O}(\frac{1}{K \epsilon})$ を, 強凸目的に対して, ネットワークサイズと線形にスケールするスピードアップを達成できることを示す。
サンプルの複雑さは$\epsilon$と$K$の両方で最適である。
我々はハイパーパラメータチューニングと分散強化学習の例でアルゴリズムを検証した。
シミュレーション実験により,最先端のトレーニング効率とテスト精度が得られた。
関連論文リスト
- Faster Adaptive Decentralized Learning Algorithms [24.379734053137597]
適応学習と有限サム最適化のための高速分散非分散アルゴリズム(AdaMDOSとAdaMDOF)のクラスを提案する。
いくつかの実験結果から,アルゴリズムの有効性が示された。
論文 参考訳(メタデータ) (2024-08-19T08:05:33Z) - Federated Multi-Level Optimization over Decentralized Networks [55.776919718214224]
エージェントが隣人としか通信できないネットワーク上での分散マルチレベル最適化の問題について検討する。
ネットワーク化されたエージェントが1つの時間スケールで異なるレベルの最適化問題を解くことができる新しいゴシップに基づく分散マルチレベル最適化アルゴリズムを提案する。
提案アルゴリズムは, ネットワークサイズと線形にスケーリングし, 各種アプリケーション上での最先端性能を示す。
論文 参考訳(メタデータ) (2023-10-10T00:21:10Z) - 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) - Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。
運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
論文 参考訳(メタデータ) (2022-11-14T12:32:18Z) - Faster Adaptive Momentum-Based Federated Methods for Distributed
Composition Optimization [14.579475552088692]
非分散合成問題の解法として,高速なフェデレート合成最適化アルゴリズム(MFCGDとAdaMFCGD)を提案する。
特に、我々の適応アルゴリズム(AdaMFCGD)は、様々な適応学習率を柔軟に組み込むために統一適応行列を使用する。
論文 参考訳(メタデータ) (2022-11-03T15:17:04Z) - Fast Adaptive Federated Bilevel Optimization [14.579475552088692]
本稿では,分散二レベル最適化問題の解法として,適応型二レベル最適化アルゴリズム(AdaFBiO)を提案する。
AdaFBiOは、統一適応行列を用いて、様々な適応学習率を柔軟に組み込んで、ULおよびLL問題の変数を更新する。
AdaFBiOアルゴリズムの収束解析フレームワークを提供し、$tildeO(epsilon-3)$の複雑さと$tildeO(epsilon-2)$のコミュニケーション複雑さのサンプルが必要であることを証明した。
論文 参考訳(メタデータ) (2022-11-02T13:55:47Z) - INTERACT: Achieving Low Sample and Communication Complexities in
Decentralized Bilevel Learning over Networks [24.02913189682224]
分散化された双方向最適化問題は、ネットワーク機械学習コミュニティで注目を集めている。
低サンプリングと通信の複雑さは、未調査のままである2つの基本的な課題である。
我々の研究は、ネットワーク上の分散化された二段階最適化問題を解決するために、低サンプリングと通信の複雑さの両方を初めて解決した。
論文 参考訳(メタデータ) (2022-07-27T04:19:28Z) - On the Convergence of Distributed Stochastic Bilevel Optimization
Algorithms over a Network [55.56019538079826]
バイレベル最適化は、幅広い機械学習モデルに適用されている。
既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。
そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-06-30T05:29:52Z) - A Low Complexity Decentralized Neural Net with Centralized Equivalence
using Layer-wise Learning [49.15799302636519]
我々は、分散処理ノード(労働者)で最近提案された大規模ニューラルネットワークをトレーニングするために、低複雑性分散学習アルゴリズムを設計する。
我々の設定では、トレーニングデータは作業者間で分散されるが、プライバシやセキュリティ上の懸念からトレーニングプロセスでは共有されない。
本研究では,データが一箇所で利用可能であるかのように,等価な学習性能が得られることを示す。
論文 参考訳(メタデータ) (2020-09-29T13:08:12Z) - Communication-Efficient Distributed Stochastic AUC Maximization with
Deep Neural Networks [50.42141893913188]
本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。
我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。
いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
論文 参考訳(メタデータ) (2020-05-05T18:08:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。