A Generalized Alternating Method for Bilevel Learning under the Polyak-{\L}ojasiewicz Condition

• URL: http://arxiv.org/abs/2306.02422v4
• Date: Thu, 5 Oct 2023 21:57:43 GMT
• Title: A Generalized Alternating Method for Bilevel Learning under the Polyak-{\L}ojasiewicz Condition
• Authors: Quan Xiao, Songtao Lu, Tianyi Chen
• Abstract summary: 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.
• Score: 63.66516306205932
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bilevel optimization has recently regained interest owing to its applications in emerging machine learning fields such as hyperparameter optimization, meta-learning, and reinforcement learning. Recent results have shown that simple alternating (implicit) gradient-based algorithms can match the convergence rate of single-level gradient descent (GD) when addressing bilevel problems with a strongly convex lower-level objective. However, it remains unclear whether this result can be generalized to bilevel problems beyond this basic setting. In this paper, we first introduce a stationary metric for the considered bilevel problems, which generalizes the existing metric, for a nonconvex lower-level objective that satisfies the Polyak-{\L}ojasiewicz (PL) condition. We then propose a Generalized ALternating mEthod for bilevel opTimization (GALET) tailored to BLO with convex PL LL problem and establish that GALET achieves an $\epsilon$-stationary point for the considered problem within $\tilde{\cal O}(\epsilon^{-1})$ iterations, which matches the iteration complexity of GD for single-level smooth nonconvex problems.

Related papers

• Accelerated Fully First-Order Methods for Bilevel and Minimax Optimization [5.269633789700637]
  We present a novel fully first-order method in emphBilevel Optimization (BLO) For BLO under the assumption that the lower-level functions admit typical strong convexity assumption, the emphBilevel Approximation (textttPRAF$2$BA) is proposed. We also investigate the challenge finding stationary points of the hyper-level function in BLO when lower-level functions lack the typical strong convexity assumption.
  arXiv  Detail & Related papers  (2024-05-01T23:59:36Z)
• Adaptive Mirror Descent Bilevel Optimization [25.438298531555468]
  We propose a class of efficient adaptive bilevel methods based on mirror descent for non bifraclevel optimization. We provide an analysis for methods under some conditions, and prove that our methods have a fast number of iterations.
  arXiv  Detail & Related papers  (2023-11-08T08:17:09Z)
• On Penalty-based Bilevel Gradient Descent Method [40.27047651949238]
  We tackle the bilevel problem through the lens of the penalty method. We propose the penalty-based bilevel gradient descent (PBGD) algorithm. Experiments showcase the efficiency of the proposed PBGD algorithm.
  arXiv  Detail & Related papers  (2023-02-10T11:30:19Z)
• Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
  Bilevel optimization is one of the problems in machine learning. Recent developments in bilevel optimization converge on the first fundamental nonaptature multi-step analysis.
  arXiv  Detail & Related papers  (2022-02-08T07:10:06Z)
• 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)
• 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)
• Leveraging Non-uniformity in First-order Non-convex Optimization [93.6817946818977]
  Non-uniform refinement of objective functions leads to emphNon-uniform Smoothness (NS) and emphNon-uniform Lojasiewicz inequality (NL) New definitions inspire new geometry-aware first-order methods that converge to global optimality faster than the classical $Omega (1/t2)$ lower bounds.
  arXiv  Detail & Related papers  (2021-05-13T04:23:07Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  We propose a new algorithm -- the Momentum- Single-timescale Approximation (MSTSA) -- for tackling problems. MSTSA allows us to control the error in iterations due to inaccurate solution to the lower level subproblem.
  arXiv  Detail & Related papers  (2021-02-15T07:10:33Z)
• A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton [49.23948907229656]
  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.
  arXiv  Detail & Related papers  (2020-06-07T05:18:50Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  Adaptive algorithms perform gradient updates using the history of gradients and are ubiquitous in training deep neural networks. In this paper we analyze a variant of OptimisticOA algorithm for nonconcave minmax problems. Our experiments show that adaptive GAN non-adaptive gradient algorithms can be observed empirically.
  arXiv  Detail & Related papers  (2019-12-26T22:10:10Z)

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.