論文の概要: Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis

• arxiv url: http://arxiv.org/abs/2410.05140v1
• Date: Tue, 8 Oct 2024 21:38:43 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-02 00:08:45.300137
• Title: Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis
• Title（参考訳）: チューニング自由二レベル最適化:新しいアルゴリズムと収束解析
• Authors: Yifan Yang, Hao Ban, Minhui Huang, Shiqian Ma, Kaiyi Ji,
• Abstract要約: そこで我々はD-TFBOとS-TFBOという2つの新しいチューニング自由アルゴリズムを提案する。 D-TFBOは「累積勾配ノルムの逆」戦略によって適応的に調整された段数を持つ二重ループ構造を用いる。 S-TFBOはより単純な完全な単一ループ構造で、3つの変数を同時に更新する。
• 参考スコア（独自算出の注目度）: 21.932550214810533
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bilevel optimization has recently attracted considerable attention due to its abundant applications in machine learning problems. However, existing methods rely on prior knowledge of problem parameters to determine stepsizes, resulting in significant effort in tuning stepsizes when these parameters are unknown. In this paper, we propose two novel tuning-free algorithms, D-TFBO and S-TFBO. D-TFBO employs a double-loop structure with stepsizes adaptively adjusted by the "inverse of cumulative gradient norms" strategy. S-TFBO features a simpler fully single-loop structure that updates three variables simultaneously with a theory-motivated joint design of adaptive stepsizes for all variables. We provide a comprehensive convergence analysis for both algorithms and show that D-TFBO and S-TFBO respectively require $O(\frac{1}{\epsilon})$ and $O(\frac{1}{\epsilon}\log^4(\frac{1}{\epsilon}))$ iterations to find an $\epsilon$-accurate stationary point, (nearly) matching their well-tuned counterparts using the information of problem parameters. Experiments on various problems show that our methods achieve performance comparable to existing well-tuned approaches, while being more robust to the selection of initial stepsizes. To the best of our knowledge, our methods are the first to completely eliminate the need for stepsize tuning, while achieving theoretical guarantees.
• Abstract（参考訳）: 最近、機械学習問題に多くの応用があるため、バイレベル最適化が注目されている。 しかし、既存の手法は問題パラメータの事前の知識に頼ってステップ化を決定するため、これらのパラメータが未知のときにステップ化をチューニングするのに多大な労力がかかる。 本稿では,D-TFBOとS-TFBOという2つの新しいチューニング不要アルゴリズムを提案する。 D-TFBOは「累積勾配ノルムの逆」戦略によって適応的に調整された段数を持つ二重ループ構造を用いる。 S-TFBOはより単純な完全な単一ループ構造で、3つの変数を同時に更新する。 両アルゴリズムの総合収束解析を行い、D-TFBOとS-TFBOはそれぞれ$O(\frac{1}{\epsilon})$と$O(\frac{1}{\epsilon}\log^4(\frac{1}{\epsilon})$の反復を必要とすることを示す。 様々な問題に対する実験により,提案手法は既存の高度に調整された手法に匹敵する性能を達成できる一方で,初期段階の選択に対してより堅牢であることが示された。 我々の知る限りでは、理論的な保証を達成しつつ、段階的なチューニングの必要性を完全に排除した最初の方法である。

関連論文リスト

• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• BiSLS/SPS: Auto-tune Step Sizes for Stable Bi-level Optimization [33.082961718280245]
  既存のアルゴリズムは、ハイパーグラディエントを計算する際に近似誤差の影響を受け得る2つの結合学習率を含んでいる。 線形探索(SLS)とポリアクステップサイズ(SPS)という適応的なステップサイズ法を用いて,上層と下層の両方の学習率の計算を行う。 SGDとAdamの両バージョンで利用できる新しいアルゴリズムは、最小限のチューニングで大きな学習率を見つけ、対応するバニラBOアルゴリズムよりも高速に収束させることができる。
  論文  参考訳（メタデータ） (2023-05-30T00:37:50Z)
• Dynamical softassign and adaptive parameter tuning for graph matching [0.7456521449098222]
  制約勾配アルゴリズムと呼ばれるグラフマッチング問題に対する統一的なフレームワークについて検討する。 我々の寄与する適応的なステップサイズパラメータは、基礎となるアルゴリズムの収束を保証することができる。 本稿では,ソフトアサイン制約勾配法という新しいグラフマッチングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-17T11:25:03Z)
• Formal guarantees for heuristic optimization algorithms used in machine learning [6.978625807687497]
  グラディエント・Descent(SGD)とその変種は、大規模最適化機械学習(ML)問題において支配的な手法となっている。 本稿では,いくつかの凸最適化手法の形式的保証と改良アルゴリズムの提案を行う。
  論文  参考訳（メタデータ） (2022-07-31T19:41:22Z)
• A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse [121.54116938140754]
  両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。 我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
  論文  参考訳（メタデータ） (2021-12-09T02:27:52Z)
• Bolstering Stochastic Gradient Descent with Model Building [0.0]
  勾配降下法とその変種は、優れた収束率を達成するためのコア最適化アルゴリズムを構成する。 本稿では,前方ステップモデル構築に基づく新しいアルゴリズムを用いて,線探索の代替手法を提案する。 提案アルゴリズムは、よく知られたテスト問題において、より高速な収束とより優れた一般化を実現する。
  論文  参考訳（メタデータ） (2021-11-13T06:54:36Z)
• BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
  バイレベル最適化は多くの応用のために機械学習への関心が高まっている。 制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
  論文  参考訳（メタデータ） (2021-06-21T20:16:40Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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