Single-loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions

本文研究了一类形式为$\min_{x}[\max_{y\in Y}\phi(x, y) - \max_{z\in Z}\psi(x, z)]$的非光滑非凸问题，其中$\Phi(x) = \max_{y\in Y}\phi(x, y)$和$\Psi(x)=\max_{z\in Z}\psi(x, z)$均为弱凸函数，而$\phi(x, y)$和$\psi(x, z)$则分别是关于$y$和$z$的强凹函数。它涵盖了两个已经被研究但缺乏单循环随机算法的问题族，即弱凸函数之差和弱凸强凹min-max问题。我们提出了一种随机Moreau包络近似梯度方法SMAG，它是解决这些问题的第一个单循环算法，并提供了最先进的非渐进收敛率。设计的关键思想是仅使用原始和对偶变量的一步随机梯度更新来计算$\Phi, \Psi$的Moreau包络的近似梯度。在实证方面，我们对正样本未标记（PU）学习和带有对抗公平正则化器的部分ROC曲线下面积（pAUC）优化进行了实验，以验证我们提出的算法的有效性。

解决问题：本文旨在研究一类非光滑非凸问题，形式为$\min_{x}[\max_{y\in Y}\phi(x, y) - \max_{z\in Z}\psi(x, z)]$，其中$\Phi(x) = \max_{y\in Y}\phi(x, y)$和$\Psi(x)=\max_{z\in Z}\psi(x, z)$均为弱凸函数，而$\phi(x, y), \psi(x, z)$分别关于$y$和$z$是强凹函数。本文旨在提出一种单循环随机算法来解决这些问题。

关键思路：本文提出了一种名为SMAG的随机Moreau包络逼近梯度方法，用于解决这些问题。其设计的关键思路是仅使用一步原始和对偶变量的随机梯度更新来计算$\Phi,\Psi$的Moreau包络的近似梯度。这是第一种单循环算法来解决这些问题。

其他亮点：本文提出的SMAG算法在正面未标记（PU）学习和局部ROC曲线下面积（pAUC）优化中进行了实验，同时使用了一个对抗公平正则化器来验证算法的有效性。此外，本文提供了最先进的非渐进收敛速率。

相关研究：在这个领域中，最近的相关研究包括使用随机梯度下降的凸优化算法和使用深度学习的凸优化算法。