論文の概要: A Penalty Based Method for Communication-Efficient Decentralized Bilevel
Programming
- arxiv url: http://arxiv.org/abs/2211.04088v1
- Date: Tue, 8 Nov 2022 08:39:30 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-09 17:21:13.822257
- Title: A Penalty Based Method for Communication-Efficient Decentralized Bilevel
Programming
- Title(参考訳): 通信効率の高い分散bilevelプログラミングのためのペナルティベース手法
- Authors: Parvin Nazari, Ahmad Mousavi, Davoud Ataee Tarzanagh, and George
Michailidis
- Abstract要約: 本稿では,分散化ネットワーク上での双方向プログラミング問題の解法として,ペナルティ関数に基づく分散化アルゴリズムを提案する。
提案アルゴリズムの重要な特徴は,行列ベクトル積の分散計算とベクトル通信によるペナルティ関数の過次性を推定することである。
この結果から,ミニマックスや合成最適化を含む多種多様なコンセンサス問題に対する収束率が得られる。
- 参考スコア(独自算出の注目度): 9.782137749673934
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Bilevel programming has recently received attention in the literature, due to
a wide range of applications, including reinforcement learning and
hyper-parameter optimization. However, it is widely assumed that the underlying
bilevel optimization problem is solved either by a single machine or in the
case of multiple machines connected in a star-shaped network, i.e., federated
learning setting. The latter approach suffers from a high communication cost on
the central node (e.g., parameter server) and exhibits privacy vulnerabilities.
Hence, it is of interest to develop methods that solve bilevel optimization
problems in a communication-efficient decentralized manner. To that end, this
paper introduces a penalty function based decentralized algorithm with
theoretical guarantees for this class of optimization problems. Specifically, a
distributed alternating gradient-type algorithm for solving consensus bilevel
programming over a decentralized network is developed. A key feature of the
proposed algorithm is to estimate the hyper-gradient of the penalty function
via decentralized computation of matrix-vector products and few vector
communications, which is then integrated within our alternating algorithm to
give the finite-time convergence analysis under different convexity
assumptions. Owing to the generality of this complexity analysis, our result
yields convergence rates for a wide variety of consensus problems including
minimax and compositional optimization. Empirical results on both synthetic and
real datasets demonstrate that the proposed method works well in practice.
- Abstract(参考訳): 強化学習やハイパーパラメータ最適化など、幅広い応用によって、近年、バイレベルプログラミングが文献で注目を集めている。
しかし,星型ネットワークに接続された複数のマシン,すなわちフェデレーション学習環境において,基礎となる二段階最適化問題は一つのマシンで解決されると広く考えられている。
後者のアプローチは、中央ノード(例えばパラメータサーバ)での通信コストが高く、プライバシー上の脆弱性がある。
したがって、双方向最適化問題を通信効率のよい分散方式で解決する手法の開発が注目される。
そこで本稿では,このような最適化問題に対する理論的保証を備えたペナルティ関数に基づく分散アルゴリズムを提案する。
具体的には,分散ネットワーク上でのコンセンサス二レベル計画の解法として,分散交互勾配型アルゴリズムを開発した。
提案アルゴリズムの重要な特徴は,行列ベクトル積の分散計算とベクトル通信によってペナルティ関数の過度な勾配を推定することであり,これは異なる凸性仮定の下で有限時間収束解析を行うための交互アルゴリズムに統合される。
この複雑性解析の汎用性から,この結果は,ミニマックスや構成最適化を含む多種多様なコンセンサス問題に対する収束率をもたらす。
合成データと実データの両方に対する実験結果から,提案手法が実際に有効であることを示す。
関連論文リスト
- On the Communication Complexity of Decentralized Bilevel Optimization [44.19286981781694]
異種環境下での分散二段階勾配降下アルゴリズムを開発した。
我々の知る限りでは、これは不均一な条件下でこれらの理論結果を達成する最初のアルゴリズムである。
論文 参考訳(メタデータ) (2023-11-19T14:56:26Z) - A Single-Loop Algorithm for Decentralized Bilevel Optimization [12.75011523756594]
そこで本研究では,分散化された二段階最適化を低レベルに凸した単一ループアルゴリズムを提案する。
我々のアルゴリズムは完全に単ループであり、過次勾配を近似する際に重い行列ベクトル乗法を必要としない。
解析の結果,提案アルゴリズムはサブ線形収束率が得られることがわかった。
論文 参考訳(メタデータ) (2023-11-15T13:29:49Z) - Federated Multi-Level Optimization over Decentralized Networks [55.776919718214224]
エージェントが隣人としか通信できないネットワーク上での分散マルチレベル最適化の問題について検討する。
ネットワーク化されたエージェントが1つの時間スケールで異なるレベルの最適化問題を解くことができる新しいゴシップに基づく分散マルチレベル最適化アルゴリズムを提案する。
提案アルゴリズムは, ネットワークサイズと線形にスケーリングし, 各種アプリケーション上での最先端性能を示す。
論文 参考訳(メタデータ) (2023-10-10T00:21:10Z) - Stochastic Multi-Level Compositional Optimization Algorithms over
Networks with Level-Independent Convergence Rate [22.988563731766586]
マルチレベル関数を扱うために,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) - 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) - Optimal Algorithms for Decentralized Stochastic Variational Inequalities [113.43047601775453]
この作業は、ますます重要になるが十分に理解されていない分散的な設定に集中する。
通信と局所的な繰り返しの両方の下位境界を示し、これらの下位境界に一致する最適なアルゴリズムを構築する。
我々のアルゴリズムは、分散化されたケースだけでなく、決定論的で非分散的な文献でも利用できる。
論文 参考訳(メタデータ) (2022-02-06T13:14:02Z) - 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) - Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
バイレベル最適化は多くの機械学習問題に対するツールである。
Stoc-BiO という新しい確率効率勾配推定器を提案する。
論文 参考訳(メタデータ) (2020-10-15T18:09:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。