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

• arxiv url: http://arxiv.org/abs/2110.04974v1
• Date: Mon, 11 Oct 2021 03:13:39 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-13 07:15:34.119305
• Title: Value-Function-based Sequential Minimization for Bi-level Optimization
• Title（参考訳）: 二値最適化のための値関数に基づく逐次最小化
• Authors: Risheng Liu, Xuan Liu, Shangzhi Zeng, Jin Zhang, Yixuan Zhang
• Abstract要約: 本稿では,BVFSM(Bi-level Value-Function-based Sequential Minimization)を導入し,機械学習の課題を解決する。 BVFSMは繰り返し勾配とヘッセン逆数の計算を避ける。 また,BVFSMを拡張して,上層および下層機能制約を付加してBLOに対処する。
• 参考スコア（独自算出の注目度）: 41.332833152175716
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Gradient-based Bi-Level Optimization (BLO) methods have been widely applied to solve modern machine learning problems. However, most existing solution 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 that can efficiently handle BLO in those challenging scenarios, such as BLO with functional constraints and pessimistic BLO. In this work, by reformulating BLO into an approximated single-level problem based on the value-function, we provide a new method, named Bi-level Value-Function-based Sequential Minimization (BVFSM), to partially address the above issues. To be specific, BVFSM constructs a series of value-function-based approximations, and thus successfully avoids the repeated calculations of recurrent gradient and Hessian inverse required by existing approaches, which are time-consuming (especially for high-dimensional tasks). We also extend BVFSM to address BLO with additional upper- and lower-level functional constraints. More importantly, we demonstrate that the algorithmic framework of BVFSM can also be used for the challenging pessimistic BLO, which has never been properly solved by existing gradient-based methods. On the theoretical side, we strictly prove the convergence of BVFSM on these types of BLO, in which the restrictive lower-level convexity assumption is completely discarded. To our best knowledge, this is the first gradient-based algorithm that can solve different kinds of BLO problems (e.g., optimistic, pessimistic and with constraints) all with solid convergence guarantees. Extensive experiments verify our theoretical investigations and demonstrate the superiority of BVFSM on various real-world applications.
• Abstract（参考訳）: 勾配に基づくBLO(Bi-Level Optimization)法は、現代の機械学習問題を解決するために広く応用されている。 しかし、既存の解戦略の多くは、理論上は制限的な仮定(例えば、低レベル部分問題の凸性)に基づいて設計されており、高次元のタスクには計算上は適用できない。 さらに、機能制約のあるBLOや悲観的なBLOなど、これらの困難なシナリオでBLOを効率的に処理できる勾配ベースの手法はほとんどない。 本稿では,この値関数に基づく単一レベル問題にbloを再構成することで,二値値関数に基づく逐次最小化(bvfsm)と呼ばれる新しい手法を提案する。 具体的に言うと、BVFSMは一連の値関数に基づく近似を構築し、特に高次元タスクにおいて)時間を要する既存のアプローチで要求される反復勾配とヘッセン逆の計算をうまく避ける。 また,BVFSMを拡張して,上層および下層機能制約を付加する。 さらに,bvfsmのアルゴリズムフレームワークは,既存の勾配に基づく手法では正しく解かれていない難解な悲観的ブロブにも利用できることを示した。 理論的には、これらの種類のBLOに対するBVFSMの収束を厳密に証明し、制限的下層凸性仮定は完全に破棄される。 我々の知る限りでは、このアルゴリズムは様々な種類のBLO問題(例えば楽観的、悲観的、制約付き)を、すべて安定収束保証で解決できる最初の勾配に基づくアルゴリズムである。 大規模な実験により、BVFSMの様々な実世界の応用における優位性を検証した。

関連論文リスト

• 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)

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

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