論文の概要: On the Communication Complexity of Decentralized Bilevel Optimization

• arxiv url: http://arxiv.org/abs/2311.11342v4
• Date: Sat, 1 Jun 2024 18:32:08 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-04 20:21:27.518507
• Title: On the Communication Complexity of Decentralized Bilevel Optimization
• Title（参考訳）: 分散二段階最適化の通信複雑性について
• Authors: Yihan Zhang, My T. Thai, Jie Wu, Hongchang Gao,
• Abstract要約: 本稿では,更新戦略の同時および交互化に基づく2つの新しい分散二段階勾配勾配アルゴリズムを提案する。 我々のアルゴリズムは既存の手法よりも高速な収束率と通信コストを抑えることができる。 このような理論的な結果は、不均一な環境での軽微な仮定で達成されたのはこれが初めてである。
• 参考スコア（独自算出の注目度）: 40.45379954138305
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastic bilevel optimization finds widespread applications in machine learning, including meta-learning, hyperparameter optimization, and neural architecture search. To extend stochastic bilevel optimization to distributed data, several decentralized stochastic bilevel optimization algorithms have been developed. However, existing methods often suffer from slow convergence rates and high communication costs in heterogeneous settings, limiting their applicability to real-world tasks. To address these issues, we propose two novel decentralized stochastic bilevel gradient descent algorithms based on simultaneous and alternating update strategies. Our algorithms can achieve faster convergence rates and lower communication costs than existing methods. Importantly, our convergence analyses do not rely on strong assumptions regarding heterogeneity. More importantly, our theoretical analysis clearly discloses how the additional communication required for estimating hypergradient under the heterogeneous setting affects the convergence rate. To the best of our knowledge, this is the first time such favorable theoretical results have been achieved with mild assumptions in the heterogeneous setting. Furthermore, we demonstrate how to establish the convergence rate for the alternating update strategy when combined with the variance-reduced gradient. Finally, experimental results confirm the efficacy of our algorithms.
• Abstract（参考訳）: 確率的二レベル最適化は、メタラーニング、ハイパーパラメータ最適化、ニューラルアーキテクチャサーチなど、機械学習に広く応用されている。 確率的二レベル最適化を分散データに拡張するために、いくつかの分散確率的二レベル最適化アルゴリズムを開発した。 しかし、既存の手法は、不均一な環境での収束速度が遅く、通信コストも高く、現実のタスクに適用性に制限されることが多い。 これらの問題に対処するために,更新戦略の同時および交互化に基づく2つの新しい分散確率的二段階勾配勾配アルゴリズムを提案する。 我々のアルゴリズムは既存の手法よりも高速な収束率と通信コストを抑えることができる。 重要なことに、収束解析は不均一性に関する強い仮定に依存しない。 さらに重要なことは、不均一な条件下での過次性の推定に必要な追加的な通信が収束率にどのように影響するかを明らかにすることである。 我々の知る限りでは、不均一な設定で穏やかな仮定でそのような良好な理論結果が得られたのは、これが初めてである。 さらに,変分還元勾配と組み合わせることで,更新戦略の収束率を確立する方法を示す。 最後に,本アルゴリズムの有効性を実験的に検証した。

関連論文リスト

• Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learning [5.325297567945828]
  本稿では,従来の手法よりもはるかに高速な収束を実現する2段階最適化手法を提案する。 提案アルゴリズムは,様々な条件下で特徴付けられ,オンラインサンプルベース手法に特化していることを示す。
  論文  参考訳（メタデータ） (2024-05-15T19:03:08Z)
• MUSIC: Accelerated Convergence for Distributed Optimization With Inexact and Exact Methods [6.800113478497425]
  本稿では,MUSICと名づけられた高速化されたフレームワークを提案し,各エージェントが複数のローカル更新と1つの組み合わせをイテレーション毎に実行できるようにする。 そこで我々は, 線形収束を高速化し, 通信効率を向上する2つの新しいアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2024-03-05T02:02:00Z)
• Decentralized Multi-Level Compositional Optimization Algorithms with Level-Independent Convergence Rate [26.676582181833584]
  分散化されたマルチレベル最適化は、マルチレベル構造と分散通信のために困難である。 マルチレベル構成問題を最適化する2つの新しい分散最適化アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-06-06T00:23:28Z)
• Can Decentralized Stochastic Minimax Optimization Algorithms Converge Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
  分散化されたミニマックス最適化は、幅広い機械学習に応用されているため、ここ数年で活発に研究されている。 本稿では,非コンカブ問題に対する2つの新しい分散化ミニマックス最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-24T02:19:39Z)
• Communication-Efficient Federated Bilevel Optimization with Local and Global Lower Level Problems [118.00379425831566]
  我々はFedBiOAccという通信効率の高いアルゴリズムを提案する。 我々は、FedBiOAcc-Localがこの種の問題に対して同じ速度で収束していることを証明する。 実験結果から,アルゴリズムの性能が向上した。
  論文  参考訳（メタデータ） (2023-02-13T21:28:53Z)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  バイレベル最適化は、幅広い機械学習モデルに適用されている。 既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。 そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-06-30T05:29:52Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  バイレベル最適化は多くの機械学習問題に対するツールである。 Stoc-BiO という新しい確率効率勾配推定器を提案する。
  論文  参考訳（メタデータ） (2020-10-15T18:09:48Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。