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

Abstract

In this paper, we study a class of non-smooth non-convex problems in the form of _x[_y Y(x, y) - _z Z(x, z)], where both (x) = _y Y(x, y) and (x)=_z Z(x, z) are weakly convex functions, and (x, y), (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 , 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.

Tasks

Reproductions