論文の概要: INTERACT: Achieving Low Sample and Communication Complexities in
Decentralized Bilevel Learning over Networks
- arxiv url: http://arxiv.org/abs/2207.13283v2
- Date: Thu, 28 Jul 2022 14:34:30 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-29 11:53:15.219223
- Title: INTERACT: Achieving Low Sample and Communication Complexities in
Decentralized Bilevel Learning over Networks
- Title（参考訳）: InterACT: ネットワーク上の分散二段階学習における低サンプル・通信複雑性の実現
- Authors: Zhuqing Liu, Xin Zhang, Prashant Khanduri, Songtao Lu, and Jia Liu
- Abstract要約: 分散化された双方向最適化問題は、ネットワーク機械学習コミュニティで注目を集めている。
低サンプリングと通信の複雑さは、未調査のままである2つの基本的な課題である。
我々の研究は、ネットワーク上の分散化された二段階最適化問題を解決するために、低サンプリングと通信の複雑さの両方を初めて解決した。
- 参考スコア（独自算出の注目度）: 24.02913189682224
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In recent years, decentralized bilevel optimization problems have received
increasing attention in the networking and machine learning communities thanks
to their versatility in modeling decentralized learning problems over
peer-to-peer networks (e.g., multi-agent meta-learning, multi-agent
reinforcement learning, personalized training, and Byzantine-resilient
learning). However, for decentralized bilevel optimization over peer-to-peer
networks with limited computation and communication capabilities, how to
achieve low sample and communication complexities are two fundamental
challenges that remain under-explored so far. In this paper, we make the first
attempt to investigate the class of decentralized bilevel optimization problems
with nonconvex and strongly-convex structure corresponding to the outer and
inner subproblems, respectively. Our main contributions in this paper are
two-fold: i) We first propose a deterministic algorithm called INTERACT
(inner-gradient-descent-outer-tracked-gradient) that requires the sample
complexity of $\mathcal{O}(n \epsilon^{-1})$ and communication complexity of
$\mathcal{O}(\epsilon^{-1})$ to solve the bilevel optimization problem, where
$n$ and $\epsilon > 0$ are the number of samples at each agent and the desired
stationarity gap, respectively. ii) To relax the need for full gradient
evaluations in each iteration, we propose a stochastic variance-reduced version
of INTERACT (SVR-INTERACT), which improves the sample complexity to
$\mathcal{O}(\sqrt{n} \epsilon^{-1})$ while achieving the same communication
complexity as the deterministic algorithm. To our knowledge, this work is the
first that achieves both low sample and communication complexities for solving
decentralized bilevel optimization problems over networks. Our numerical
experiments also corroborate our theoretical findings.
- Abstract（参考訳）: 近年、ピアツーピアネットワーク(例えば、マルチエージェントメタラーニング、マルチエージェント強化学習、パーソナライズドトレーニング、ビザンチン・レジリエント学習)における分散学習問題のモデリングの汎用性により、ネットワークや機械学習コミュニティでは、分散二段階最適化の問題が注目されている。
しかしながら、計算能力と通信能力に制限のあるピアツーピアネットワーク上での分散二レベル最適化では、サンプルと通信の複雑さの低さを実現するには、2つの根本的な課題がある。
本稿では,非凸および強凸構造を持つ分散二段階最適化問題のクラスを,それぞれ外および内部のサブプロブレムに対応するものとして検討する。
本論文の主な貢献は次の2つです。
i) InterACT (inner-gradient-descent-outer-tracked-gradient) と呼ばれる決定論的アルゴリズムをまず提案する。このアルゴリズムでは,各エージェントのサンプル数と所望の定常差をそれぞれ$n$と$0$で解決するために,$\mathcal{O}(n \epsilon^{-1})$と$\mathcal{O}(\epsilon^{-1})$の通信複雑性を必要とする。
i) 各繰り返しにおける完全な勾配評価の必要性を緩和するために,決定論的アルゴリズムと同じ通信複雑性を達成しつつ,サンプルの複雑さを$\mathcal{O}(\sqrt{n} \epsilon^{-1})$に改善したInteract(SVR-INTERACT)の確率的分散還元版を提案する。
私たちの知る限りでは、この研究は、ネットワーク上の分散二レベル最適化問題を解決するために、サンプルと通信の複雑さの低さを実現する最初の方法です。
我々の数値実験も我々の理論的な結果を裏付けている。
関連論文リスト
- A Communication and Computation Efficient Fully First-order Method for Decentralized Bilevel Optimization [16.020878731214083]
本稿では,分散バイレベル最適化のための完全一階分散手法である$textC2$DFBを提案する。
$textC2$DFBは計算効率と通信効率の両方です。
論文 参考訳（メタデータ） (2024-10-18T02:00:45Z) - Can Decentralized Stochastic Minimax Optimization Algorithms Converge
Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
分散化されたミニマックス最適化は、幅広い機械学習に応用されているため、ここ数年で活発に研究されている。
本稿では,非コンカブ問題に対する2つの新しい分散化ミニマックス最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-24T02:19:39Z) - 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) - On the Convergence of Distributed Stochastic Bilevel Optimization
Algorithms over a Network [55.56019538079826]
バイレベル最適化は、幅広い機械学習モデルに適用されている。
既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。
そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-06-30T05:29:52Z) - Decentralized Gossip-Based Stochastic Bilevel Optimization over
Communication Networks [42.76623191830371]
本稿では,ゴシップに基づく分散二段階最適化アルゴリズムを提案する。
エージェントはネットワークと外部の両方の問題を一度に解くことができる。
我々のアルゴリズムは最先端の効率とテスト精度を達成する。
論文 参考訳（メタデータ） (2022-06-22T06:38:54Z) - Local Stochastic Bilevel Optimization with Momentum-Based Variance
Reduction [104.41634756395545]
具体的には、まず、決定論的勾配に基づくアルゴリズムであるFedBiOを提案する。
FedBiOの複雑性は$O(epsilon-1.5)$である。
本アルゴリズムは数値実験において,他のベースラインと比較して優れた性能を示す。
論文 参考訳（メタデータ） (2022-05-03T16:40:22Z) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳（メタデータ） (2021-10-24T04:03:00Z) - GT-STORM: Taming Sample, Communication, and Memory Complexities in
Decentralized Non-Convex Learning [11.129095449532283]
近年,分散1/2非堅牢性最適化が注目されている。
分散最適化アルゴリズムの設計における3つの基本的な課題は、サンプルコスト、通信、メモリ複雑さの削減である。
論文 参考訳（メタデータ） (2021-05-04T00:44:48Z) - A Low Complexity Decentralized Neural Net with Centralized Equivalence
using Layer-wise Learning [49.15799302636519]
我々は、分散処理ノード(労働者)で最近提案された大規模ニューラルネットワークをトレーニングするために、低複雑性分散学習アルゴリズムを設計する。
我々の設定では、トレーニングデータは作業者間で分散されるが、プライバシやセキュリティ上の懸念からトレーニングプロセスでは共有されない。
本研究では,データが一箇所で利用可能であるかのように,等価な学習性能が得られることを示す。
論文 参考訳（メタデータ） (2020-09-29T13:08:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。