On Penalty-based Bilevel Gradient Descent Method

• URL: http://arxiv.org/abs/2302.05185v5
• Date: Mon, 06 Jan 2025 22:56:30 GMT
• Title: On Penalty-based Bilevel Gradient Descent Method
• Authors: Han Shen, Quan Xiao, Tianyi Chen,
• Abstract summary: Bilevel optimization enjoys a wide range of applications in emerging machine learning and signal processing problems. Recent progress on bilevel algorithms mainly focuses on bilevel optimization problems through the lens of the implicit-gradient method. In this work, we tackle a challenging class of bilevel problems through the lens of the penalty method.
• Score: 35.83102074785861
• License:
• Abstract: Bilevel optimization enjoys a wide range of applications in emerging machine learning and signal processing problems such as hyper-parameter optimization, image reconstruction, meta-learning, adversarial training, and reinforcement learning. However, bilevel optimization problems are traditionally known to be difficult to solve. Recent progress on bilevel algorithms mainly focuses on bilevel optimization problems through the lens of the implicit-gradient method, where the lower-level objective is either strongly convex or unconstrained. In this work, we tackle a challenging class of bilevel problems through the lens of the penalty method. We show that under certain conditions, the penalty reformulation recovers the (local) solutions of the original bilevel problem. Further, we propose the penalty-based bilevel gradient descent (PBGD) algorithm and establish its finite-time convergence for the constrained bilevel problem with lower-level constraints yet without lower-level strong convexity. Experiments on synthetic and real datasets showcase the efficiency of the proposed PBGD algorithm.

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)
• Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHF [82.73541793388]
  We introduce the first principled algorithmic framework for solving bilevel RL problems through the lens of penalty formulation. We provide theoretical studies of the problem landscape and its penalty-based gradient (policy) algorithms. We demonstrate the effectiveness of our algorithms via simulations in the Stackelberg Markov game, RL from human feedback and incentive design.
  arXiv  Detail & Related papers  (2024-02-10T04:54:15Z)
• Constrained Bi-Level Optimization: Proximal Lagrangian Value function Approach and Hessian-free Algorithm [8.479947546216131]
  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.
  arXiv  Detail & Related papers  (2024-01-29T13:50:56Z)
• 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)
• Inexact bilevel stochastic gradient methods for constrained and unconstrained lower-level problems [0.0]
  Two-level formula search optimization has become instrumental in a number of machine learning contexts. New low-rank bi-level gradient methods are developed that do not require second-order derivatives.
  arXiv  Detail & Related papers  (2021-10-01T18:20:14Z)
• Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
  We propose a bilevel optimization method based on Bregman Bregman functions. We also propose an accelerated version of SBiO-BreD method (ASBiO-BreD) by using the variance-reduced technique.
  arXiv  Detail & Related papers  (2021-07-26T16:18:43Z)
• 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)

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.