Timezone: »

 
Poster
Multi-block Min-max Bilevel Optimization with Applications in Multi-task Deep AUC Maximization
Quanqi Hu · YONGJIAN ZHONG · Tianbao Yang

Wed Nov 30 02:00 PM -- 04:00 PM (PST) @ Hall J #537
in Poster Session 4 »
In this paper, we study multi-block min-max bilevel optimization problems, where the upper level is non-convex strongly-concave minimax objective and the lower level is a strongly convex objective, and there are multiple blocks of dual variables and lower level problems. Due to the intertwined multi-block min-max bilevel structure, the computational cost at each iteration could be prohibitively high, especially with a large number of blocks. To tackle this challenge, we present two single-loop randomized stochastic algorithms, which require updates for only a constant number of blocks at each iteration. Under some mild assumptions on the problem, we establish their sample complexity of $\mathcal{O}(1/\epsilon^4)$ for finding an $\epsilon$-stationary point. This matches the optimal complexity order for solving stochastic nonconvex optimization under a general unbiased stochastic oracle model. Moreover, we provide two applications of the proposed method in multi-task deep AUC (area under ROC curve) maximization. Experimental results validate our theory and demonstrate the effectiveness of our method.
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Quanqi Hu (Texas A&M University)
YONGJIAN ZHONG (University of Iowa)
Tianbao Yang (Texas A&M University)

More from the Same Authors