A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton

• URL: http://arxiv.org/abs/2006.04045v2
• Date: Thu, 2 Jul 2020 10:26:42 GMT
• Title: A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton
• Authors: Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, Jin Zhang
• Abstract summary: Bi-level Descent Aggregation is a flexible and modularized algorithmic framework for generic bi-level optimization. We derive a new methodology to prove the convergence of BDA without the LLS condition. Our investigations also demonstrate that BDA is indeed compatible to a verify of particular first-order computation modules.
• Score: 49.23948907229656
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In recent years, a variety of gradient-based first-order methods have been developed to solve bi-level optimization problems for learning applications. However, theoretical guarantees of these existing approaches heavily rely on the simplification that for each fixed upper-level variable, the lower-level solution must be a singleton (a.k.a., Lower-Level Singleton, LLS). In this work, we first design a counter-example to illustrate the invalidation of such LLS condition. Then by formulating BLPs from the view point of optimistic bi-level and aggregating hierarchical objective information, we establish Bi-level Descent Aggregation (BDA), a flexible and modularized algorithmic framework for generic bi-level optimization. Theoretically, we derive a new methodology to prove the convergence of BDA without the LLS condition. Our investigations also demonstrate that BDA is indeed compatible to a verify of particular first-order computation modules. Additionally, as an interesting byproduct, we also improve these conventional first-order bi-level schemes (under the LLS simplification). Particularly, we establish their convergences with weaker assumptions. Extensive experiments justify our theoretical results and demonstrate the superiority of the proposed BDA for different tasks, including hyper-parameter optimization and meta learning.

Related papers

• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  gradient-based algorithms are widely used in bilevel optimization. We introduce a without-replacement sampling based algorithm which achieves a faster convergence rate. We validate our algorithms over both synthetic and real-world applications.
  arXiv  Detail & Related papers  (2024-11-07T17:05:31Z)
• 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)
• 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)
• Averaged Method of Multipliers for Bi-Level Optimization without Lower-Level Strong Convexity [43.092883358935545]
  We propose a single loop Bi-level Averaged Method of Multipliers (sl-BAMM) for Bi-Level Optimization (BLO) We provide non-asymptotic convergence analysis of sl-BAMM towards KKT stationary points, and the comparative advantage of our analysis lies in the absence of strong gradient boundedness assumption.
  arXiv  Detail & Related papers  (2023-02-07T11:29:05Z)
• Towards Extremely Fast Bilevel Optimization with Self-governed Convergence Guarantees [42.514612465664605]
  We propose a single-level formulation to uniformly understand existing explicit and implicit Gradient-based BLOs. A striking feature of our convergence result is that, compared to those original unaccelerated GBLO versions, the fast BAGDC admits a unified non-asymptotic convergence theory towards stationarity.
  arXiv  Detail & Related papers  (2022-05-20T09:46:10Z)
• 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)
• Towards Gradient-based Bilevel Optimization with Non-convex Followers and Beyond [37.89147034158937]
  Bi-LevelLOcation (BLO) has received extensive attentions from both learning and vision communities. We propose a new class of BLOs, named Auxiliaryization and Pessimy Truncated Gradient (IAPTT-GM) In particular, by introducing an auxiliary as to guide the optimization dynamics and designing a trunrun operation, we construct a reliable approximate version of the original BLO LLC.
  arXiv  Detail & Related papers  (2021-10-01T14:41:17Z)
• A Generic Descent Aggregation Framework for Gradient-based Bi-level Optimization [41.894281911990554]
  We develop a novel Bi-level Descent Aggregation (BDA) framework for bi-level learning tasks. BDA aggregates hierarchical objectives of both upper level and lower level. We propose a new proof recipe to improve the convergence results of conventional gradient-based bi-level methods.
  arXiv  Detail & Related papers  (2021-02-16T06:58:12Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  Bilevel optimization is a tool for many machine learning problems. We propose a novel stoc-efficientgradient estimator named stoc-BiO.
  arXiv  Detail & Related papers  (2020-10-15T18:09:48Z)

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.