論文の概要: A Communication and Computation Efficient Fully First-order Method for Decentralized Bilevel Optimization

• arxiv url: http://arxiv.org/abs/2410.14115v1
• Date: Fri, 18 Oct 2024 02:00:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-21 14:26:08.524524
• Title: A Communication and Computation Efficient Fully First-order Method for Decentralized Bilevel Optimization
• Title（参考訳）: 分散二段階最適化のための通信・計算効率の良い完全一階法
• Authors: Min Wen, Chengchang Liu, Ahmed Abdelmoniem, Yipeng Zhou, Yuedong Xu,
• Abstract要約: 本稿では,分散バイレベル最適化のための完全一階分散手法である$textC2$DFBを提案する。 $textC2$DFBは計算効率と通信効率の両方です。
• 参考スコア（独自算出の注目度）: 16.020878731214083
• License:
• Abstract: Bilevel optimization, crucial for hyperparameter tuning, meta-learning and reinforcement learning, remains less explored in the decentralized learning paradigm, such as decentralized federated learning (DFL). Typically, decentralized bilevel methods rely on both gradients and Hessian matrices to approximate hypergradients of upper-level models. However, acquiring and sharing the second-order oracle is compute and communication intensive. % and sharing this information incurs heavy communication overhead. To overcome these challenges, this paper introduces a fully first-order decentralized method for decentralized Bilevel optimization, $\text{C}^2$DFB which is both compute- and communicate-efficient. In $\text{C}^2$DFB, each learning node optimizes a min-min-max problem to approximate hypergradient by exclusively using gradients information. To reduce the traffic load at the inner-loop of solving the lower-level problem, $\text{C}^2$DFB incorporates a lightweight communication protocol for efficiently transmitting compressed residuals of local parameters. % during the inner loops. Rigorous theoretical analysis ensures its convergence % of the algorithm, indicating a first-order oracle calls of $\tilde{\mathcal{O}}(\epsilon^{-4})$. Experiments on hyperparameter tuning and hyper-representation tasks validate the superiority of $\text{C}^2$DFB across various typologies and heterogeneous data distributions.
• Abstract（参考訳）: 双レベル最適化は、ハイパーパラメータチューニング、メタラーニング、強化学習に不可欠であり、分散化フェデレートラーニング(DFL)のような分散学習パラダイムでは検討されていない。 通常、分散化された双レベル法は、上層モデルの過次度を近似するために勾配とヘッセン行列の両方に依存している。 しかし、第2次オラクルの取得と共有は計算と通信に重きを置いている。 この情報を共有すると、大きな通信オーバーヘッドが発生します。 これらの課題を克服するため,本研究では,分散化バイレベル最適化のための完全一階分散手法である$\text{C}^2$DFBを導入し,計算効率と通信効率を両立させた。 $\text{C}^2$DFB では、各学習ノードは min-min-max 問題を最適化し、勾配情報のみを用いることで過次性を近似する。 低レベルの問題を解決するために、$\text{C}^2$DFBはローカルパラメータの圧縮残差を効率的に伝送するための軽量通信プロトコルを組み込んでいる。 %であった。 厳密な理論解析はアルゴリズムの収束率を保証し、$\tilde{\mathcal{O}}(\epsilon^{-4})$の1次オラクル呼び出しを示す。 超パラメータチューニングと超表現タスクの実験は、様々な型と不均一なデータ分布にまたがる$\text{C}^2$DFBの優位性を検証した。

関連論文リスト

• Boosting the Performance of Decentralized Federated Learning via Catalyst Acceleration [66.43954501171292]
  本稿では,Catalytics Accelerationを導入し,DFedCataと呼ばれる促進型分散フェデレート学習アルゴリズムを提案する。 DFedCataは、パラメータの不整合に対処するMoreauエンベロープ関数と、アグリゲーションフェーズを加速するNesterovの外挿ステップの2つの主要コンポーネントで構成されている。 実験により, CIFAR10/100における収束速度と一般化性能の両面において, 提案アルゴリズムの利点を実証した。
  論文  参考訳（メタデータ） (2024-10-09T06:17:16Z)
• Memory-Efficient Gradient Unrolling for Large-Scale Bi-level Optimization [71.35604981129838]
  従来の勾配に基づく二段階最適化アルゴリズムは、大規模アプリケーションの要求を満たすには不適である。 両レベル最適化のためのメタ勾配の偏りのない近似を実現するための$(textFG)2textU$を導入する。 $(textFG)2textU$は本質的に並列コンピューティングをサポートするように設計されており、大規模分散コンピューティングシステムを効果的に活用することができる。
  論文  参考訳（メタデータ） (2024-06-20T08:21:52Z)
• Asynchronous Distributed Bilevel Optimization [20.074079852690048]
  本稿では,双方向最適化問題に対処するため,非同期分散双レベル(ADBO)アルゴリズムを提案する。 ADBOが$epsilon$-定常点を得る複雑さは$mathcalO(frac1epsilon 2)$によって上界される。
  論文  参考訳（メタデータ） (2022-12-20T07:44:48Z)
• DIAMOND: Taming Sample and Communication Complexities in Decentralized Bilevel Optimization [27.317118892531827]
  我々は、DIAMOND(運動量と勾配追跡を伴う分散単時間スケール近似)と呼ばれる新しい分散二段階最適化を開発する。 我々はDIAMONDが$mathcalO(epsilon-3/2)$をサンプルと通信の複雑さで楽しむことを示し、$epsilon$-stationaryソリューションを実現する。
  論文  参考訳（メタデータ） (2022-12-05T15:58:00Z)
• A Penalty-Based Method for Communication-Efficient Decentralized Bilevel Programming [14.35928967799696]
  本稿では,分散化ネットワーク上での双方向プログラミング問題の解法として,ペナルティ関数に基づく分散化アルゴリズムを提案する。 提案アルゴリズムの重要な特徴は,ペナルティ関数の過度勾配の推定である。 我々の理論的枠組みは、様々な凸条件下での原問題の最適解に漸近的でない収束を保証する。
  論文  参考訳（メタデータ） (2022-11-08T08:39:30Z)
• INTERACT: Achieving Low Sample and Communication Complexities in Decentralized Bilevel Learning over Networks [24.02913189682224]
  分散化された双方向最適化問題は、ネットワーク機械学習コミュニティで注目を集めている。 低サンプリングと通信の複雑さは、未調査のままである2つの基本的な課題である。 我々の研究は、ネットワーク上の分散化された二段階最適化問題を解決するために、低サンプリングと通信の複雑さの両方を初めて解決した。
  論文  参考訳（メタデータ） (2022-07-27T04:19:28Z)
• Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learning [58.79085525115987]
  ローカル手法は通信時間を短縮する有望なアプローチの1つである。 局所的データセットが局所的損失の滑らかさよりも小さい場合,通信の複雑さは非局所的手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-02-12T15:12:17Z)
• DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization [43.31016937305845]
  インターネット・オブ・シング、ネットワークセンシング、自律システム、有限サム最適化のための分散アルゴリズムのためのフェデレーション学習。 非有限サム最適化のためのDecentralized STochastic Recursive MethodDESTRESSを開発した。 詳細な理論的および数値的な比較は、DESTRESSが事前の分散アルゴリズムにより改善されていることを示している。
  論文  参考訳（メタデータ） (2021-10-04T03:17:41Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge Computing [113.52575069030192]
  セキュリティ要件の高いアプリケーションを含むビッグデータは、モバイルデバイスやドローン、車両など、複数の異種デバイスに収集され、格納されることが多い。 通信コストとセキュリティ要件の制限のため、核融合センターにデータを集約するのではなく、分散的に情報を抽出することが最重要となる。 分散エッジノードを介してデータを局所的に処理するマルチエージェントシステムにおいて,モデルパラメータを学習する問題を考える。 分散学習モデルを開発するために,乗算器アルゴリズムの最小バッチ交互方向法(ADMM)のクラスについて検討した。
  論文  参考訳（メタデータ） (2020-10-02T10:41:59Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。 我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。 いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
  論文  参考訳（メタデータ） (2020-05-05T18:08:23Z)

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

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