論文の概要: On the Convergence of Distributed Stochastic Bilevel Optimization
Algorithms over a Network
- arxiv url: http://arxiv.org/abs/2206.15025v2
- Date: Mon, 27 Mar 2023 16:09:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-29 03:13:30.239064
- Title: On the Convergence of Distributed Stochastic Bilevel Optimization
Algorithms over a Network
- Title（参考訳）: ネットワーク上の分散確率二値最適化アルゴリズムの収束について
- Authors: Hongchang Gao, Bin Gu, My T. Thai
- Abstract要約: バイレベル最適化は、幅広い機械学習モデルに適用されている。
既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。
そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
- 参考スコア（独自算出の注目度）: 55.56019538079826
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bilevel optimization has been applied to a wide variety of machine learning
models, and numerous stochastic bilevel optimization algorithms have been
developed in recent years. However, most existing algorithms restrict their
focus on the single-machine setting so that they are incapable of handling the
distributed data. To address this issue, under the setting where all
participants compose a network and perform peer-to-peer communication in this
network, we developed two novel decentralized stochastic bilevel optimization
algorithms based on the gradient tracking communication mechanism and two
different gradient estimators. Additionally, we established their convergence
rates for nonconvex-strongly-convex problems with novel theoretical analysis
strategies. To our knowledge, this is the first work achieving these
theoretical results. Finally, we applied our algorithms to practical machine
learning models, and the experimental results confirmed the efficacy of our
algorithms.
- Abstract（参考訳）: バイレベル最適化は様々な機械学習モデルに適用され、近年は確率的バイレベル最適化アルゴリズムが数多く開発されている。
しかし、既存のアルゴリズムの多くは、分散データを処理できないように、シングルマシン設定に焦点を絞っている。
この問題に対処するために,ネットワークを構成するすべての参加者がネットワーク内でピアツーピア通信を行うように設定し,勾配追従通信機構と2つの異なる勾配推定器に基づく2つの新しい分散確率二レベル最適化アルゴリズムを開発した。
さらに, 新たな理論解析戦略により, 非凸-強凸問題に対する収束率を確立した。
私たちの知る限り、これはこれらの理論的結果を達成する最初の作品です。
最後に,本アルゴリズムを実用的な機械学習モデルに適用し,実験結果から本アルゴリズムの有効性を確認した。
関連論文リスト
- On the Communication Complexity of Decentralized Bilevel Optimization [40.45379954138305]
本稿では,更新戦略の同時および交互化に基づく2つの新しい分散二段階勾配勾配アルゴリズムを提案する。
我々のアルゴリズムは既存の手法よりも高速な収束率と通信コストを抑えることができる。
このような理論的な結果は、不均一な環境での軽微な仮定で達成されたのはこれが初めてである。
論文 参考訳（メタデータ） (2023-11-19T14:56:26Z) - A Single-Loop Algorithm for Decentralized Bilevel Optimization [11.67135350286933]
そこで本研究では,分散化された二段階最適化を低レベルに凸した問題で解くための新しい単一ループアルゴリズムを提案する。
提案手法は,反復毎に2つの行列ベクトル乗算のみを用いることで,過勾配を近似する完全単ループ法である。
解析により,提案アルゴリズムは二段階最適化アルゴリズムにおいて最もよく知られた収束率を実現することを示す。
論文 参考訳（メタデータ） (2023-11-15T13:29:49Z) - Decentralized Multi-Level Compositional Optimization Algorithms with Level-Independent Convergence Rate [26.676582181833584]
分散化されたマルチレベル最適化は、マルチレベル構造と分散通信のために困難である。
マルチレベル構成問題を最適化する2つの新しい分散最適化アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-06-06T00:23:28Z) - Stochastic Unrolled Federated Learning [85.6993263983062]
本稿では,UnRolled Federated Learning (SURF)を導入する。
提案手法は,この拡張における2つの課題,すなわち,非学習者へのデータセット全体の供給の必要性と,フェデレート学習の分散的性質に対処する。
論文 参考訳（メタデータ） (2023-05-24T17:26:22Z) - Can Decentralized Stochastic Minimax Optimization Algorithms Converge
Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
分散化されたミニマックス最適化は、幅広い機械学習に応用されているため、ここ数年で活発に研究されている。
本稿では,非コンカブ問題に対する2つの新しい分散化ミニマックス最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-24T02:19:39Z) - On the Convergence of Momentum-Based Algorithms for Federated Stochastic
Bilevel Optimization Problems [22.988563731766586]
特に,このような問題を最適化するための運動量に基づく2つのアルゴリズムを開発した。
我々はこれらの2つのアルゴリズムの収束率を確立し、それらのサンプルと通信の複雑さを提供した。
論文 参考訳（メタデータ） (2022-04-28T06:14:21Z) - Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。
厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。
このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
論文 参考訳（メタデータ） (2021-11-29T15:10:09Z) - Bilevel Optimization for Machine Learning: Algorithm Design and
Convergence Analysis [12.680169619392695]
この論文は、2レベル最適化アルゴリズムに対する総合収束率解析を提供する。
問題に基づく定式化では、AIDおよびITDに基づく2レベルアルゴリズムの収束率解析を行う。
そこで我々は,ゆるやかな仮定で形状収束解析を行う加速バイレベルアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-07-31T22:05:47Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Parallelization Techniques for Verifying Neural Networks [52.917845265248744]
検証問題に基づくアルゴリズムを反復的に導入し、2つの分割戦略を探索する。
また、ニューラルネットワークの検証問題を単純化するために、ニューロンアクティベーションフェーズを利用する、高度に並列化可能な前処理アルゴリズムも導入する。
論文 参考訳（メタデータ） (2020-04-17T20:21:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。