Multi-block Min-max Bilevel Optimization with Applications in Multi-task Deep AUC Maximization
Multi-block Min-max Bilevel Optimization with Applications in Multi-task Deep AUC Maximization
复制标题
DOI：
10.48550/arxiv.2206.00260
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Quanqi Hu;Yongjian Zhong;Tianbao Yang
中科院分区：
文献类型：
--
作者：
Quanqi Hu;Yongjian Zhong;Tianbao Yang
在本文中，我们研究了多块最小-最大双层优化问题，其中上层是非凸强凹极小最大目标，下层是强凸目标，并且存在多个双变量块和较低层问题。由于交织的多块最小-最大双层结构，每次迭代的计算成本可能非常高，尤其是在块数量很大的情况下。为了应对这一挑战，我们提出了一种单循环随机随机算法，该算法在每次迭代时仅需要更新恒定数量的块。在对该问题的一些温和假设下，我们确定其样本复杂度为 $O(1/\epsilon^4)$，以找到 $\epsilon$-驻点。这与一般无偏随机预言模型下求解随机非凸优化的最佳复杂度相匹配。此外，我们还提供了该方法在多任务深度 AUC（ROC 曲线下面积）最大化和多任务深度部分 AUC 最大化中的两种应用。实验结果验证了我们的理论，并证明了我们的方法在数百个任务问题上的有效性。
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.