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

In this paper, we study a class of non-smooth non-convex problems in the form of minx[maxy∈ Yφ(x, y) - maxz∈ Zpsi(x, z)], where both Phi(x) = maxy∈ Yφ(x, y) and Psi(x)=maxz∈ Zpsi(x, z) are weakly convex functions, and φ(x, y), psi(x, z) are strongly concave functions in terms of y and z, respectively. It covers two families of problems that have been studied but are missing single-loop stochastic algorithms, i.e., difference of weakly convex functions and weakly convex strongly-concave min-max problems. We propose a stochastic Moreau envelope approximate gradient method dubbed SMAG, the first single-loop algorithm for solving these problems, and provide a state-of-the-art non-asymptotic convergence rate. The key idea of the design is to compute an approximate gradient of the Moreau envelopes of Phi, Psi using only one step of stochastic gradient update of the primal and dual variables. Empirically, we conduct experiments on positive-unlabeled (PU) learning and partial area under ROC curve (pAUC) optimization with an adversarial fairness regularizer to validate the effectiveness of our proposed algorithms.