Timezone: »

 
A Stochastic Momentum Method for Min-max Bilevel Optimization
Quanqi Hu · Bokun Wang · Tianbao Yang

@
in OPT 2021: Optimization for Machine Learning »
In this paper, we study nonconvex min-max bilevel optimization problem where the outer objective function is non-convex and strongly concave and the inner objective function is strongly convex. This paper develops a single loop single timescale stochastic algorithm based on moving average estimator, which only requires a general unbiased stochastic oracle with bounded variance. To the best of our knowledge, the only existing work on min-max bilevel optimization focuses on the ones with an upper objective in certain structure and only achieves an oracle complexity of $\cO(\epsilon^{-5})$. Under some mild assumptions on the partial derivatives of both outer and inner objective functions, we provide the first convergence guarantee with an oracle complexity of $\cO(\epsilon^{-4})$ for a general class of min-max bilevel problems, which matches the optimal complexity order for solving stochastic nonconvex optimization under a general unbiased stochastic oracle model.

Author Information

Quanqi Hu (University of Iowa)
Bokun Wang (The University of Iowa)
Tianbao Yang (The University of Iowa)

More from the Same Authors