論文の概要: A Penalty-Based Method for Communication-Efficient Decentralized Bilevel Programming
- arxiv url: http://arxiv.org/abs/2211.04088v4
- Date: Thu, 10 Oct 2024 08:05:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-11 14:27:39.673401
- Title: A Penalty-Based Method for Communication-Efficient Decentralized Bilevel Programming
- Title（参考訳）: コミュニケーション効率の良い分散バイレベルプログラミングのためのペナルティに基づく一手法
- Authors: Parvin Nazari, Ahmad Mousavi, Davoud Ataee Tarzanagh, George Michailidis,
- Abstract要約: 本稿では,分散化ネットワーク上での双方向プログラミング問題の解法として,ペナルティ関数に基づく分散化アルゴリズムを提案する。
提案アルゴリズムの重要な特徴は,ペナルティ関数の過度勾配の推定である。
我々の理論的枠組みは、様々な凸条件下での原問題の最適解に漸近的でない収束を保証する。
- 参考スコア（独自算出の注目度）: 14.35928967799696
- License:
- Abstract: Bilevel programming has recently received attention in the literature due to its 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., in a federated learning setting. The latter approach suffers from a high communication cost on the central node (e.g., parameter server). Hence, there is an interest in developing 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 the estimation of the hyper-gradient of the penalty function through decentralized computation of matrix-vector products and a few vector communications. The estimation is integrated into an alternating algorithm for solving the penalized reformulation of the bilevel optimization problem. Under appropriate step sizes and penalty parameters, our theoretical framework ensures non-asymptotic convergence to the optimal solution of the original problem under various convexity conditions. Our theoretical result highlights improvements in the iteration complexity of decentralized bilevel optimization, all while making efficient use of vector communication. Empirical results demonstrate that the proposed method performs well in real-world settings.
- Abstract（参考訳）: バイレベルプログラミングは、強化学習やハイパーパラメータ最適化を含む幅広い応用のために、最近この文献で注目を集めている。
しかし、二段階最適化の根底にある問題は、一つの機械で解決されるか、あるいは複数の機械が星型ネットワークに接続されている場合、すなわちフェデレートされた学習環境で解決されると広く想定されている。
後者のアプローチでは、中央ノード(例えばパラメータサーバ)での通信コストが高くなる。
したがって、コミュニケーション効率のよい分散的な方法で二段階最適化問題を解決する手法の開発に関心がある。
そこで本稿では,このような最適化問題に対して理論的に保証されたペナルティ関数に基づく分散アルゴリズムを提案する。
具体的には、分散化されたネットワーク上でのコンセンサスバイレベルプログラミングを解くための分散交互勾配型アルゴリズムを開発した。
提案アルゴリズムの重要な特徴は,行列ベクトル積の分散計算とベクトル通信によるペナルティ関数の過次性の推定である。
この推定は、二段階最適化問題のペナル化を解くための交互アルゴリズムに統合される。
適切なステップサイズとペナルティパラメータの下で、我々の理論的枠組みは、様々な凸条件下での元の問題の最適解に漸近的でない収束を保証する。
我々の理論的結果は、ベクトル通信を効率的に利用しながら、分散化された二段階最適化の反復複雑性の改善を強調している。
実験結果から,提案手法は実環境において良好に動作することが示された。
関連論文リスト
- Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
通信ネットワークのノード間で分散的に格納された凸関数の総和を最小化するタスクについて検討する。
この問題を解決するのに必要な分散通信数と(サブ)漸進計算の下位境界が確立されている。
我々は,これらの下界に適合する最初の最適アルゴリズムを開発し,既存の最先端技術と比較して理論性能を著しく向上させる。
論文 参考訳（メタデータ） (2024-05-28T10:28:45Z) - A Single-Loop Algorithm for Decentralized Bilevel Optimization [11.67135350286933]
そこで本研究では,分散化された二段階最適化を低レベルに凸した問題で解くための新しい単一ループアルゴリズムを提案する。
提案手法は,反復毎に2つの行列ベクトル乗算のみを用いることで,過勾配を近似する完全単ループ法である。
解析により,提案アルゴリズムは二段階最適化アルゴリズムにおいて最もよく知られた収束率を実現することを示す。
論文 参考訳（メタデータ） (2023-11-15T13:29:49Z) - Adaptive Consensus: A network pruning approach for decentralized
optimization [0.5432724320036953]
ネットワーク内の各ノードが局所関数を持つネットワークベースの分散最適化問題を考える。
目的は、すべての局所関数の和を最小化するコンセンサス解を集合的に達成することである。
本稿では,通信量を削減する適応的ランダム化通信効率アルゴリズムフレームワークを提案する。
論文 参考訳（メタデータ） (2023-09-06T00:28:10Z) - Decentralized Multi-Level Compositional Optimization Algorithms with Level-Independent Convergence Rate [26.676582181833584]
分散化されたマルチレベル最適化は、マルチレベル構造と分散通信のために困難である。
マルチレベル構成問題を最適化する2つの新しい分散最適化アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-06-06T00:23:28Z) - On the Convergence of Distributed Stochastic Bilevel Optimization
Algorithms over a Network [55.56019538079826]
バイレベル最適化は、幅広い機械学習モデルに適用されている。
既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。
そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-06-30T05:29:52Z) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文 参考訳（メタデータ） (2022-03-01T18:20:01Z) - DESTRESS: Computation-Optimal and Communication-Efficient Decentralized
Nonconvex Finite-Sum Optimization [43.31016937305845]
インターネット・オブ・シング、ネットワークセンシング、自律システム、有限サム最適化のための分散アルゴリズムのためのフェデレーション学習。
非有限サム最適化のためのDecentralized STochastic Recursive MethodDESTRESSを開発した。
詳細な理論的および数値的な比較は、DESTRESSが事前の分散アルゴリズムにより改善されていることを示している。
論文 参考訳（メタデータ） (2021-10-04T03:17:41Z) - Bilevel Optimization for Machine Learning: Algorithm Design and
Convergence Analysis [12.680169619392695]
この論文は、2レベル最適化アルゴリズムに対する総合収束率解析を提供する。
問題に基づく定式化では、AIDおよびITDに基づく2レベルアルゴリズムの収束率解析を行う。
そこで我々は,ゆるやかな仮定で形状収束解析を行う加速バイレベルアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-07-31T22:05:47Z) - Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。
また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
論文 参考訳（メタデータ） (2021-07-26T16:18:43Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。