論文の概要: A Single-Loop Algorithm for Decentralized Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2311.08945v2
- Date: Thu, 14 Dec 2023 11:30:20 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-16 03:44:20.924514
- Title: A Single-Loop Algorithm for Decentralized Bilevel Optimization
- Title(参考訳): 分散二レベル最適化のための単一ループアルゴリズム
- Authors: Youran Dong, Shiqian Ma, Junfeng Yang, Chao Yin
- Abstract要約: そこで本研究では,分散化された二段階最適化を低レベルに凸した単一ループアルゴリズムを提案する。
我々のアルゴリズムは完全に単ループであり、過次勾配を近似する際に重い行列ベクトル乗法を必要としない。
解析の結果,提案アルゴリズムはサブ線形収束率が得られることがわかった。
- 参考スコア(独自算出の注目度): 12.75011523756594
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bilevel optimization has received more and more attention recently due to its
wide applications in machine learning. In this paper, we consider bilevel
optimization in decentralized networks. In particular, we propose a novel
single-loop algorithm for solving decentralized bilevel optimization with
strongly convex lower level problem. Our algorithm is fully single-loop and
does not require heavy matrix-vector multiplications when approximating the
hypergradient. Moreover, unlike existing methods for decentralized bilevel
optimization and federated bilevel optimization, our algorithm does not require
any gradient heterogeneity assumption. Our analysis shows that the proposed
algorithm achieves a sublinear convergence rate. Experimental results on
hyperparameter optimization problem with both synthetic and MNIST data sets
demonstrate the efficiency of the proposed algorithm.
- Abstract(参考訳): バイレベル最適化は、機械学習の幅広い応用により、近年ますます注目を集めている。
本稿では,分散ネットワークにおけるバイレベル最適化について検討する。
特に, 強凸低レベル問題を用いて分散二値最適化を解くための新しい単一ループアルゴリズムを提案する。
本アルゴリズムは完全に単一ループであり,超次数近似時の重行列ベクトル乗算は不要である。
さらに,分散二レベル最適化とフェデレート二レベル最適化の既存手法とは異なり,アルゴリズムは勾配不均一性仮定を必要としない。
解析の結果,提案アルゴリズムはサブ線形収束率が得られることがわかった。
合成およびMNISTデータセットを用いたハイパーパラメータ最適化に関する実験結果から,提案アルゴリズムの有効性が示された。
関連論文リスト
- Stochastic Multi-Level Compositional Optimization Algorithms over
Networks with Level-Independent Convergence Rate [22.988563731766586]
マルチレベル関数を扱うために,2つの新しい分散アルゴリズムを開発した。
両アルゴリズムが非レベル依存問題に対する収束率を達成可能であることを示す。
最良の知識のために、これは、分散された設定の設定の下で、レベル非依存の収束率を達成する最初の研究である。
論文 参考訳(メタデータ) (2023-06-06T00:23:28Z) - A Penalty-Based Method for Communication-Efficient Decentralized Bilevel
Programming [14.35928967799696]
バイレベルプログラミングは、その幅広い応用のために、最近この文献で注目を集めている。
基礎となる双レベル最適化問題は、1台のマシンか、星型ネットワークに接続された複数のマシンのどちらかによって解決される。
本稿では,このクラスの最適化問題を理論的に保証したペナルティ関数に基づく分散アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-11-08T08:39:30Z) - Fast Adaptive Federated Bilevel Optimization [14.579475552088692]
本稿では,分散二レベル最適化問題の解法として,適応型二レベル最適化アルゴリズム(AdaFBiO)を提案する。
AdaFBiOは、統一適応行列を用いて、様々な適応学習率を柔軟に組み込んで、ULおよびLL問題の変数を更新する。
AdaFBiOアルゴリズムの収束解析フレームワークを提供し、$tildeO(epsilon-3)$の複雑さと$tildeO(epsilon-2)$のコミュニケーション複雑さのサンプルが必要であることを証明した。
論文 参考訳(メタデータ) (2022-11-02T13:55:47Z) - Decentralized Stochastic Bilevel Optimization with Improved
per-Iteration Complexity [17.870370505179014]
本稿では,一階オラクル,ヘッセンベクター,ヤコビアンベクターのみを必要とする分散二段階最適化(DSBO)アルゴリズムを提案する。
このアルゴリズムの利点は、全ヘッセン行列とヤコビ行列を推定する必要がなく、それによってイット毎の複雑性が向上するということである。
論文 参考訳(メタデータ) (2022-10-23T20:06:05Z) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文 参考訳(メタデータ) (2022-03-01T18:20:01Z) - A Fully Single Loop Algorithm for Bilevel Optimization without Hessian
Inverse [121.54116938140754]
両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。
我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
論文 参考訳(メタデータ) (2021-12-09T02:27:52Z) - 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) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳(メタデータ) (2021-06-08T21:05:30Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。