An Alternating Optimization Method for Bilevel Problems under the Polyak-Łojasiewicz Condition
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-Ł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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Generalized Alternating Method for Bilevel Learning under the Polyak-Łojasiewicz Condition
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 …
Bilevel OptimizationHyperparameter OptimizationMeta-LearningOn Momentum-Based Gradient Methods for Bilevel Optimization with Nonconvex Lower-Level
Bilevel optimization is a popular two-level hierarchical optimization, which has been widely applied to many machine learning tasks such as hyperparameter learning, meta learning and continual learning. Although many bil…
Bilevel OptimizationContinual LearningMeta-LearningRepresentation LearningAlternating Implicit Projected SGD and Its Efficient Variants for Equality-constrained Bilevel Optimization
Stochastic bilevel optimization, which captures the inherent nested structure of machine learning problems, is gaining popularity in many recent applications. Existing works on bilevel optimization mostly consider either…
Bilevel OptimizationOptimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimization
Bilevel optimization is widely applied in many machine learning tasks such as hyper-parameter learning, meta learning and reinforcement learning. Although many algorithms recently have been developed to solve the bilevel…
Bilevel OptimizationMeta-LearningRepresentation LearningOnline Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods
This paper introduces \textit{online bilevel optimization} in which a sequence of time-varying bilevel problems is revealed one after the other. We extend the known regret bounds for online single-level algorithms to the…
Bilevel Optimization