論文の概要: Will Bilevel Optimizers Benefit from Loops

• arxiv url: http://arxiv.org/abs/2205.14224v2
• Date: Tue, 31 May 2022 16:33:13 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-01 11:42:30.177646
• Title: Will Bilevel Optimizers Benefit from Loops
• Title（参考訳）: 双方向最適化はループから利益を得るか
• Authors: Kaiyi Ji, Mingrui Liu, Yingbin Liang, Lei Ying
• Abstract要約: AID-BiOとITD-BiOの2つの一般的な双レベルマトリクスは、自然に1つまたは2つのサブプロブレムを解決する。 AID-BiO と ITD-BiO の両ループ実装選択に適用可能な統合収束解析をまず確立する。
• 参考スコア（独自算出の注目度）: 63.22466953441521
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bilevel optimization has arisen as a powerful tool for solving a variety of machine learning problems. Two current popular bilevel optimizers AID-BiO and ITD-BiO naturally involve solving one or two sub-problems, and consequently, whether we solve these problems with loops (that take many iterations) or without loops (that take only a few iterations) can significantly affect the overall computational efficiency. Existing studies in the literature cover only some of those implementation choices, and the complexity bounds available are not refined enough to enable rigorous comparison among different implementations. In this paper, we first establish unified convergence analysis for both AID-BiO and ITD-BiO that are applicable to all implementation choices of loops. We then specialize our results to characterize the computational complexity for all implementations, which enable an explicit comparison among them. Our result indicates that for AID-BiO, the loop for estimating the optimal point of the inner function is beneficial for overall efficiency, although it causes higher complexity for each update step, and the loop for approximating the outer-level Hessian-inverse-vector product reduces the gradient complexity. For ITD-BiO, the two loops always coexist, and our convergence upper and lower bounds show that such loops are necessary to guarantee a vanishing convergence error, whereas the no-loop scheme suffers from an unavoidable non-vanishing convergence error. Our numerical experiments further corroborate our theoretical results.
• Abstract（参考訳）: バイレベル最適化は、さまざまな機械学習問題を解決する強力なツールとして生まれました。 現在一般的な2レベル最適化ツールである aid-bio と itd-bio の2つは、自然に1つまたは2つのサブプロブレムを解決し、その結果、これらの問題をループ(多くのイテレーションが必要)で解決するか、ループ(数回のイテレーションしか要らない)なしで解決するかは、全体的な計算効率に大きな影響を与えます。 文献における既存の研究は、これらの実装選択のいくつかのみをカバーしており、利用可能な複雑さの境界は、異なる実装間で厳密な比較を可能にするには不十分である。 本稿では,まず,AID-BiOとITD-BiOの両方に対して,ループのすべての実装選択に適用可能な統一収束解析を確立する。 次に、各実装の計算複雑性を特徴付けるために結果の専門化を行い、その比較を明示する。 その結果,aid-bioでは,内部関数の最適点を推定するループは全体の効率に有益であるが,更新ステップごとに複雑度が高くなり,外層ヘッセン逆ベクトル積を近似するループは勾配複雑性を減少させることがわかった。 itd-bioでは、2つのループは常に共存しており、上界と下界の収束は、そのようなループが消滅する収束誤差を保証するために必要であることを示している。 我々の数値実験は我々の理論結果をさらに裏付ける。

関連論文リスト

• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。 本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。 合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
  論文  参考訳（メタデータ） (2024-11-07T17:05:31Z)
• Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimization [25.438298531555468]
  双レベル最適化は、ハイパーラーニング、メタラーニング、強化ラーニングなど、多くの機械学習タスクに広く適用されている。 最適収束$frac1TT(Hessian/BiO法)を軽度条件下で提案する。 バイレベルゲーム超定常数値収束に関するいくつかの実験を行う。
  論文  参考訳（メタデータ） (2024-07-25T07:25:06Z)
• SPABA: A Single-Loop and Probabilistic Stochastic Bilevel Algorithm Achieving Optimal Sample Complexity [5.046146134689904]
  SPABAを実装する際には,双レベル最適化と単レベル最適化の間に複雑性解析のギャップがないことが示されている。 本稿では,複雑性解析の状況を改善するために,他の2ループあるいはネストした2レベルアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-29T05:36:03Z)
• A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse [121.54116938140754]
  両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。 我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
  論文  参考訳（メタデータ） (2021-12-09T02:27:52Z)
• 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)
• Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters [152.03852111442114]
  モデルに依存しないメタラーニング(MAML)は非常に成功したアルゴリズムメタラーニングの実践であるが、高い計算複雑性を持つ。 本稿では,その複雑さがANILの全体的な収束性能に大きく影響することを示す。
  論文  参考訳（メタデータ） (2020-06-16T19:57:48Z)

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

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