論文の概要: A Decentralized Alternating Gradient Method for Communication-Efficient
Bilevel Programming
- arxiv url: http://arxiv.org/abs/2211.04088v2
- Date: Fri, 2 Jun 2023 20:26:54 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-07 04:03:21.878507
- Title: A Decentralized Alternating Gradient Method for Communication-Efficient
Bilevel Programming
- Title（参考訳）: コミュニケーション効率の良いバイレベルプログラミングのための分散交代勾配法
- 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（参考訳）: 強化学習やハイパーパラメータ最適化など、幅広い応用によって、近年、バイレベルプログラミングが文献で注目を集めている。
しかし,星型ネットワークに接続された複数のマシン,すなわちフェデレーション学習環境において,基礎となる二段階最適化問題は一つのマシンで解決されると広く考えられている。
後者のアプローチは、中央ノード(例えばパラメータサーバ)での通信コストが高く、プライバシー上の脆弱性がある。
したがって、双方向最適化問題を通信効率のよい分散方式で解決する手法の開発が注目される。
そこで本稿では,このような最適化問題に対する理論的保証を備えたペナルティ関数に基づく分散アルゴリズムを提案する。
具体的には,分散ネットワーク上でのコンセンサス二レベル計画の解法として,分散交互勾配型アルゴリズムを開発した。
提案アルゴリズムの重要な特徴は,行列ベクトル積の分散計算とベクトル通信によってペナルティ関数の過度な勾配を推定することであり,これは異なる凸性仮定の下で有限時間収束解析を行うための交互アルゴリズムに統合される。
この複雑性解析の汎用性から,この結果は,ミニマックスや構成最適化を含む多種多様なコンセンサス問題に対する収束率をもたらす。
合成データと実データの両方に対する実験結果から,提案手法が実際に有効であることを示す。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。