論文の概要: A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse

• arxiv url: http://arxiv.org/abs/2112.04660v1
• Date: Thu, 9 Dec 2021 02:27:52 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-10 15:30:48.700390
• Title: A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse
• Title（参考訳）: ヘシアン逆数のない二値最適化のための完全単ループアルゴリズム
• Authors: Junyi Li, Bin Gu, Heng Huang
• Abstract要約: 両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。 我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
• 参考スコア（独自算出の注目度）: 121.54116938140754
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we propose a new Hessian inverse free Fully Single Loop Algorithm (FSLA) for bilevel optimization problems. Classic algorithms for bilevel optimization admit a double loop structure which is computationally expensive. Recently, several single loop algorithms have been proposed with optimizing the inner and outer variable alternatively. However, these algorithms not yet achieve fully single loop. As they overlook the loop needed to evaluate the hyper-gradient for a given inner and outer state. In order to develop a fully single loop algorithm, we first study the structure of the hyper-gradient and identify a general approximation formulation of hyper-gradient computation that encompasses several previous common approaches, e.g. back-propagation through time, conjugate gradient, \emph{etc.} Based on this formulation, we introduce a new state variable to maintain the historical hyper-gradient information. Combining our new formulation with the alternative update of the inner and outer variables, we propose an efficient fully single loop algorithm. We theoretically show that the error generated by the new state can be bounded and our algorithm converges with the rate of $O(\epsilon^{-2})$. Finally, we verify the efficacy our algorithm empirically through multiple bilevel optimization based machine learning tasks.
• Abstract（参考訳）: 本稿では,二値最適化問題に対する新しいヘッセン逆自由完全ループアルゴリズム(fsla)を提案する。 双レベル最適化のための古典的なアルゴリズムは計算コストのかかる二重ループ構造を持つ。 近年,インナー変数とアウター変数を交互に最適化する単一ループアルゴリズムが提案されている。 しかし、これらのアルゴリズムは完全な単一ループを達成していない。 それらを見渡すと、ループは与えられた内部状態と外部状態の過勾配を評価する必要がある。 完全な単一ループアルゴリズムを開発するために、まずハイパー勾配の構造を研究し、時間によるバックプロパゲーション、共役勾配、emph{etcなどのいくつかの一般的なアプローチを含む超勾配計算の一般的な近似式を同定する。 この定式化に基づき、歴史的過次情報を維持するための新しい状態変数を導入する。 新しい定式化と内部変数と外部変数の代替更新を組み合わせることで,効率的な完全単一ループアルゴリズムを提案する。 理論的には、新しい状態によって生成された誤差は有界であり、我々のアルゴリズムは$O(\epsilon^{-2})$と収束する。 最後に、複数の二段階最適化に基づく機械学習タスクにより、アルゴリズムの有効性を実証的に検証する。

関連論文リスト

• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。 本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。 合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
  論文  参考訳（メタデータ） (2024-11-07T17:05:31Z)
• A Single-Loop Algorithm for Decentralized Bilevel Optimization [11.67135350286933]
  そこで本研究では,分散化された二段階最適化を低レベルに凸した問題で解くための新しい単一ループアルゴリズムを提案する。 提案手法は,反復毎に2つの行列ベクトル乗算のみを用いることで,過勾配を近似する完全単ループ法である。 解析により,提案アルゴリズムは二段階最適化アルゴリズムにおいて最もよく知られた収束率を実現することを示す。
  論文  参考訳（メタデータ） (2023-11-15T13:29:49Z)
• Will Bilevel Optimizers Benefit from Loops [63.22466953441521]
  AID-BiOとITD-BiOの2つの一般的な双レベルマトリクスは、自然に1つまたは2つのサブプロブレムを解決する。 AID-BiO と ITD-BiO の両ループ実装選択に適用可能な統合収束解析をまず確立する。
  論文  参考訳（メタデータ） (2022-05-27T20:28:52Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)
• Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization [21.555331273873175]
  ネットワークのノードにまたがるスムーズな凸関数の和を分散化最小化する作業について検討する。 本稿では,この分散最適化問題に対する2つの新しいアルゴリズムを提案し,複雑性を保証する。
  論文  参考訳（メタデータ） (2020-06-21T11:23:20Z)

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

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