論文の概要: Value-Function-based Sequential Minimization for Bi-level Optimization

• arxiv url: http://arxiv.org/abs/2110.04974v2
• Date: Sat, 6 May 2023 12:31:38 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-10 01:33:24.999449
• Title: Value-Function-based Sequential Minimization for Bi-level Optimization
• Title（参考訳）: 二値最適化のための値関数に基づく逐次最小化
• Authors: Risheng Liu, Xuan Liu, Shangzhi Zeng, Jin Zhang, Yixuan Zhang
• Abstract要約: 勾配に基づくBi-Level Optimization (BLO)法は、現代の学習課題に広く応用されている。 機能的制約のあるBLOや悲観的なBLOなど、難解なシナリオでBLOを解くことができる勾配ベースの方法はほとんどない。 上記の問題に対処するために,BVFSM(Bi-level Value-Function-based Sequential Minimization)を提案する。
• 参考スコア（独自算出の注目度）: 52.39882976848064
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Gradient-based Bi-Level Optimization (BLO) methods have been widely applied to handle modern learning tasks. However, most existing strategies are theoretically designed based on restrictive assumptions (e.g., convexity of the lower-level sub-problem), and computationally not applicable for high-dimensional tasks. Moreover, there are almost no gradient-based methods able to solve BLO in those challenging scenarios, such as BLO with functional constraints and pessimistic BLO. In this work, by reformulating BLO into approximated single-level problems, we provide a new algorithm, named Bi-level Value-Function-based Sequential Minimization (BVFSM), to address the above issues. Specifically, BVFSM constructs a series of value-function-based approximations, and thus avoids repeated calculations of recurrent gradient and Hessian inverse required by existing approaches, time-consuming especially for high-dimensional tasks. We also extend BVFSM to address BLO with additional functional constraints. More importantly, BVFSM can be used for the challenging pessimistic BLO, which has never been properly solved before. In theory, we prove the asymptotic convergence of BVFSM on these types of BLO, in which the restrictive lower-level convexity assumption is discarded. To our best knowledge, this is the first gradient-based algorithm that can solve different kinds of BLO (e.g., optimistic, pessimistic, and with constraints) with solid convergence guarantees. Extensive experiments verify the theoretical investigations and demonstrate our superiority on various real-world applications.
• Abstract（参考訳）: グラディエントベースのBLO(Bi-Level Optimization)手法は、現代の学習タスクに広く応用されている。 しかし、既存の戦略のほとんどは制限的な仮定(例えば下層のサブプロブレムの凸性)に基づいて理論的に設計されており、高次元のタスクには適用できない。 さらに,機能制約付きBLOや悲観的BLOなど,BLOを解くための勾配法はほとんど存在しない。 本研究では,BLOを近似単一レベル問題に書き換えることにより,BVFSM(Bi-level Value-Function-based Sequential Minimization)と呼ばれる新しいアルゴリズムを提案する。 具体的には、BVFSMは一連の値関数に基づく近似を構築し、特に高次元タスクにおいて、既存のアプローチで要求される繰り返し勾配とヘッセン逆の計算を避ける。 また、BVFSMを拡張して、BLOにさらなる機能制約を加える。 さらに重要なことに、BVFSMは、これまで適切に解決されていない難解な悲観的BLOに使用できる。 理論的には、これらの種類のBLOに対するBVFSMの漸近収束を証明し、制限的な下層凸性仮定を破棄する。 我々の知る限りでは、このアルゴリズムは様々な種類のBLO(楽観的、悲観的、制約のある)を安定収束保証で解くことができる最初の勾配に基づくアルゴリズムである。 大規模な実験は理論的な研究を検証し、実世界の様々な応用において優位性を示す。

関連論文リスト

• A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [66.61399765513383]
  We developed a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints。 2つのよく知られた実世界のアプリケーションでその効果を実証する。
  論文  参考訳（メタデータ） (2024-06-14T15:59:36Z)
• Moreau Envelope for Nonconvex Bi-Level Optimization: A Single-loop and Hessian-free Solution Strategy [45.982542530484274]
  大規模非ビレベル問題(BLO)は、機械学習にますます適用されている。 これらの課題には、計算効率の確保と理論的保証が伴う。
  論文  参考訳（メタデータ） (2024-05-16T09:33:28Z)
• Constrained Bi-Level Optimization: Proximal Lagrangian Value function Approach and Hessian-free Algorithm [8.479947546216131]
  We developed a Hessian-free gradient-based algorithm-termed proximal Lagrangian Value function-based Hessian-free Bi-level Algorithm (LV-HBA) LV-HBAは特に機械学習アプリケーションに適している。
  論文  参考訳（メタデータ） (2024-01-29T13:50:56Z)
• An Introduction to Bi-level Optimization: Foundations and Applications in Signal Processing and Machine Learning [46.02026158913706]
  双方向最適化(BLO)は、信号処理(SP)と機械学習(ML)の分野でのエキサイティングな発展の中心を成している。 BLOは2つの階層(上層と下層)を含む古典的な最適化問題である。 BLOの代表的な応用は、無線システムのリソース割り当てから敵機械学習まで様々である。
  論文  参考訳（メタデータ） (2023-08-01T18:59:07Z)
• Averaged Method of Multipliers for Bi-Level Optimization without Lower-Level Strong Convexity [43.092883358935545]
  単ループ二値乗算器 (sl-BAMM) を両レベル最適化 (BLO) のために提案する。 我々は, sl-BAMMのKKT定常点への非漸近収束解析を行い, 解析の利点は強い勾配有界性仮定の欠如にある。
  論文  参考訳（メタデータ） (2023-02-07T11:29:05Z)
• Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
  本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。 また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
  論文  参考訳（メタデータ） (2021-07-26T16:18:43Z)
• A Generic Descent Aggregation Framework for Gradient-based Bi-level Optimization [41.894281911990554]
  両レベル学習タスクのための新しいBDA(Bi-level Descent Aggregation)フレームワークを開発した。 BDAは上層と下層の両方の階層的目的を集約する。 従来の勾配に基づくbiレベル法の収束結果を改善するための新しい証明法を提案する。
  論文  参考訳（メタデータ） (2021-02-16T06:58:12Z)
• A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton [49.23948907229656]
  Bi-level Descent Aggregationは、汎用的な双方向最適化のためのフレキシブルでモジュール化されたアルゴリズムフレームワークである。 LLS条件なしでBDAの収束を証明する新しい手法を導出する。 我々の研究は、BDAが特定の一階計算モジュールの検証と互換性があることも示している。
  論文  参考訳（メタデータ） (2020-06-07T05:18:50Z)

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

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