2023/06/04 by Quan Xiao, Xiao, Quan, Songtao Lu +3 · 3 citations
Engineering · Medicine · Computer Science · #Sparse and Compressive Sensing Techniques #Bone and Joint Diseases #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2306.02422
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 ε-stationary point for the considered problem within \cal O(ε-1) iterations, which matches the iteration complexity of GD for single-level smooth nonconvex problems.