論文の概要: Stochastic Multi-Level Compositional Optimization Algorithms over Networks with Level-Independent Convergence Rate

• arxiv url: http://arxiv.org/abs/2306.03322v1
• Date: Tue, 6 Jun 2023 00:23:28 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-07 17:53:27.845261
• Title: Stochastic Multi-Level Compositional Optimization Algorithms over Networks with Level-Independent Convergence Rate
• Title（参考訳）: レベル非依存収束率をもつネットワーク上の確率的マルチレベル合成最適化アルゴリズム
• Authors: Hongchang Gao
• Abstract要約: マルチレベル関数を扱うために,2つの新しい分散アルゴリズムを開発した。 両アルゴリズムが非レベル依存問題に対する収束率を達成可能であることを示す。 最良の知識のために、これは、分散された設定の設定の下で、レベル非依存の収束率を達成する最初の研究である。
• 参考スコア（独自算出の注目度）: 22.988563731766586
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastic multi-level compositional optimization problems cover many new machine learning paradigms, e.g., multi-step model-agnostic meta-learning, which require efficient optimization algorithms for large-scale applications. This paper studies the decentralized stochastic multi-level optimization algorithm, which is challenging because the multi-level structure and decentralized communication scheme may make the number of levels affect the order of the convergence rate. To this end, we develop two novel decentralized optimization algorithms to deal with the multi-level function and its gradient. Our theoretical results show that both algorithms can achieve the level-independent convergence rate for nonconvex problems under much milder conditions compared with existing single-machine algorithms. To the best of our knowledge, this is the first work that achieves the level-independent convergence rate under the decentralized setting. Moreover, extensive experiments confirm the efficacy of our proposed algorithms.
• Abstract（参考訳）: 確率的多段階合成最適化問題は、大規模アプリケーションに効率的な最適化アルゴリズムを必要とするマルチステップモデルに依存しないメタラーニングなど、多くの新しい機械学習パラダイムをカバーする。 本稿では,分散確率的マルチレベル最適化アルゴリズムについて検討する。マルチレベル構造と分散化通信方式は,レベル数を収束率の順序に影響を及ぼす可能性があるため,課題である。 この目的のために,マルチレベル関数とその勾配を扱う2つの分散最適化アルゴリズムを開発した。 理論的には, 従来の単機械アルゴリズムと比較して, 非凸問題に対するレベル非依存収束率を実現することができる。 私たちの知る限りでは、これは分散設定下でレベル独立な収束率を達成する最初の仕事です。 さらに,提案手法の有効性を検証する実験を行った。

関連論文リスト

• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。 本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。 合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
  論文  参考訳（メタデータ） (2024-11-07T17:05:31Z)
• 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)
• Federated Multi-Level Optimization over Decentralized Networks [55.776919718214224]
  エージェントが隣人としか通信できないネットワーク上での分散マルチレベル最適化の問題について検討する。 ネットワーク化されたエージェントが1つの時間スケールで異なるレベルの最適化問題を解くことができる新しいゴシップに基づく分散マルチレベル最適化アルゴリズムを提案する。 提案アルゴリズムは, ネットワークサイズと線形にスケーリングし, 各種アプリケーション上での最先端性能を示す。
  論文  参考訳（メタデータ） (2023-10-10T00:21:10Z)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  バイレベル最適化は、幅広い機械学習モデルに適用されている。 既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。 そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-06-30T05:29:52Z)
• 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)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  バイレベル最適化は多くの機械学習問題に対するツールである。 Stoc-BiO という新しい確率効率勾配推定器を提案する。
  論文  参考訳（メタデータ） (2020-10-15T18:09:48Z)

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

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