Constrained Bi-Level Optimization: Proximal Lagrangian Value function Approach and Hessian-free Algorithm

• URL: http://arxiv.org/abs/2401.16164v1
• Date: Mon, 29 Jan 2024 13:50:56 GMT
• Title: Constrained Bi-Level Optimization: Proximal Lagrangian Value function Approach and Hessian-free Algorithm
• Authors: Wei Yao, Chengming Yu, Shangzhi Zeng, and Jin Zhang
• Abstract summary: We develop a Hessian-free gradient-based algorithm-termed proximal Lagrangian Value function-based Hessian-free Bi-level Algorithm (LV-HBA) LV-HBA is especially well-suited for machine learning applications.
• Score: 8.479947546216131
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: This paper presents a new approach and algorithm for solving a class of constrained Bi-Level Optimization (BLO) problems in which the lower-level problem involves constraints coupling both upper-level and lower-level variables. Such problems have recently gained significant attention due to their broad applicability in machine learning. However, conventional gradient-based methods unavoidably rely on computationally intensive calculations related to the Hessian matrix. To address this challenge, we begin by devising a smooth proximal Lagrangian value function to handle the constrained lower-level problem. Utilizing this construct, we introduce a single-level reformulation for constrained BLOs that transforms the original BLO problem into an equivalent optimization problem with smooth constraints. Enabled by this reformulation, we develop a Hessian-free gradient-based algorithm-termed proximal Lagrangian Value function-based Hessian-free Bi-level Algorithm (LV-HBA)-that is straightforward to implement in a single loop manner. Consequently, LV-HBA is especially well-suited for machine learning applications. Furthermore, we offer non-asymptotic convergence analysis for LV-HBA, eliminating the need for traditional strong convexity assumptions for the lower-level problem while also being capable of accommodating non-singleton scenarios. Empirical results substantiate the algorithm's superior practical performance.

Related papers

• A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [66.61399765513383]
  We develop a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints. We demonstrate its effectiveness on two well-known real-world applications.
  arXiv  Detail & Related papers  (2024-06-14T15:59:36Z)
• Moreau Envelope for Nonconvex Bi-Level Optimization: A Single-loop and Hessian-free Solution Strategy [45.982542530484274]
  Large-scale non Bi-Level (BLO) problems are increasingly applied in machine learning. These challenges involve ensuring computational efficiency and providing theoretical guarantees.
  arXiv  Detail & Related papers  (2024-05-16T09:33:28Z)
• A Generalized Alternating Method for Bilevel Learning under the Polyak-{\L}ojasiewicz Condition [63.66516306205932]
  Bilevel optimization has recently regained interest owing to its applications in emerging machine learning fields. Recent results have shown that simple alternating iteration-based iterations can match interest owing to convex lower-level objective.
  arXiv  Detail & Related papers  (2023-06-04T17:54:11Z)
• A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima [49.320758794766185]
  We propose a new approach, which convert the bilevel problem to an equivalent constrained optimization, and then the primal-dual algorithm can be used to solve the problem. Such an approach enjoys a few advantages including (a) addresses the multiple inner minima challenge; (b) fully first-order efficiency without Jacobian computations.
  arXiv  Detail & Related papers  (2022-03-01T18:20:01Z)
• Value-Function-based Sequential Minimization for Bi-level Optimization [52.39882976848064]
  gradient-based Bi-Level Optimization (BLO) methods have been widely applied to handle modern learning tasks. There are almost no gradient-based methods able to solve BLO in challenging scenarios, such as BLO with functional constraints and pessimistic BLO. We provide Bi-level Value-Function-based Sequential Minimization (BVFSM) to address the above issues.
  arXiv  Detail & Related papers  (2021-10-11T03:13:39Z)
• A Value-Function-based Interior-point Method for Non-convex Bi-level Optimization [38.75417864443519]
  Bi-level optimization model is able to capture a wide range of complex learning tasks with practical interest. We propose a new interior Bi-level Value-based Interior-point scheme, we penalize the regularized value function of the lower level problem into the upper level objective.
  arXiv  Detail & Related papers  (2021-06-15T09:10:40Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.