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 a single-loop randomized stochastic algorithm, which
requires updates for only a constant number of blocks at each iteration. Under
some mild assumptions on the problem, we establish its sample complexity of
$O(1/\epsilon^4)$ for finding an $\epsilon$-stationary point. This matches the
optimal complexity 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 and multi-task deep partial AUC maximization. Experimental results
validate our theory and demonstrate the effectiveness of our method on problems
with hundreds of tasks.

本文探讨了多块最小最大双层优化问题，提出了一种单循环随机算法，其样本复杂性为 O（1/ϵ^4），应用于多任务深度 AUC 最大化和多任务深度局部 AUC 最大化。