論文の概要: Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexity

• arxiv url: http://arxiv.org/abs/2210.12839v2
• Date: Wed, 31 May 2023 23:36:56 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-03 01:21:53.525375
• Title: Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexity
• Title（参考訳）: 分極化確率的二値最適化
• Authors: Xuxing Chen, Minhui Huang, Shiqian Ma, Krishnakumar Balasubramanian
• Abstract要約: 本稿では,一階オラクル,ヘッセンベクター,ヤコビアンベクターのみを必要とする分散二段階最適化(DSBO)アルゴリズムを提案する。 このアルゴリズムの利点は、全ヘッセン行列とヤコビ行列を推定する必要がなく、それによってイット毎の複雑性が向上するということである。
• 参考スコア（独自算出の注目度）: 17.870370505179014
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bilevel optimization recently has received tremendous attention due to its great success in solving important machine learning problems like meta learning, reinforcement learning, and hyperparameter optimization. Extending single-agent training on bilevel problems to the decentralized setting is a natural generalization, and there has been a flurry of work studying decentralized bilevel optimization algorithms. However, it remains unknown how to design the distributed algorithm with sample complexity and convergence rate comparable to SGD for stochastic optimization, and at the same time without directly computing the exact Hessian or Jacobian matrices. In this paper we propose such an algorithm. More specifically, we propose a novel decentralized stochastic bilevel optimization (DSBO) algorithm that only requires first order stochastic oracle, Hessian-vector product and Jacobian-vector product oracle. The sample complexity of our algorithm matches the currently best known results for DSBO, and the advantage of our algorithm is that it does not require estimating the full Hessian and Jacobian matrices, thereby having improved per-iteration complexity.
• Abstract（参考訳）: 最近、メタラーニング、強化学習、ハイパーパラメータ最適化といった重要な機械学習問題の解決に成功しているため、バイレベル最適化は大きな注目を集めている。 二階問題の単一エージェントトレーニングを分散化設定に拡張することは自然な一般化であり、分散二階最適化アルゴリズムの研究が盛んに行われている。 しかし、確率最適化のために sgd に匹敵するサンプル複雑性と収束率を持つ分散アルゴリズムをどのように設計するか、また、正確なヘッセン行列やヤコビ行列を直接計算することなく設計するかは不明である。 本稿では,そのようなアルゴリズムを提案する。 具体的には,一階確率オラクル,ヘシアンベクトル製品,ヤコビアンベクトル製品オラクルのみを必要とする分散確率双レベル最適化(DSBO)アルゴリズムを提案する。 我々のアルゴリズムのサンプル複雑性はdsboの現在知られている結果と一致しており、このアルゴリズムの利点は、全ヘッセン行列とジャコビアン行列を推定する必要がなく、イテレーション毎の複雑さが向上していることである。

関連論文リスト

• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。 本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。 合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
  論文  参考訳（メタデータ） (2024-11-07T17:05:31Z)
• Faster Adaptive Decentralized Learning Algorithms [24.379734053137597]
  適応学習と有限サム最適化のための高速分散非分散アルゴリズム(AdaMDOSとAdaMDOF)のクラスを提案する。 いくつかの実験結果から,アルゴリズムの有効性が示された。
  論文  参考訳（メタデータ） (2024-08-19T08:05:33Z)
• 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)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。 本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。 3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
  論文  参考訳（メタデータ） (2022-09-27T09:06:37Z)
• ES-Based Jacobian Enables Faster Bilevel Optimization [53.675623215542515]
  バイレベル最適化(BO)は多くの現代の機械学習問題を解決する強力なツールとして生まれてきた。 既存の勾配法では、ヤコビアンあるいはヘッセンベクトル計算による二階微分近似が必要となる。 本稿では,進化戦略(ES)に基づく新しいBOアルゴリズムを提案し,BOの過勾配における応答ヤコビ行列を近似する。
  論文  参考訳（メタデータ） (2021-10-13T19:36:50Z)
• 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)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  バイレベル最適化は多くの機械学習問題に対するツールである。 Stoc-BiO という新しい確率効率勾配推定器を提案する。
  論文  参考訳（メタデータ） (2020-10-15T18:09:48Z)

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

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