Efficient Mirror Descent Ascent Methods for Nonsmooth Minimax Problems

In the paper, we propose a class of efficient mirror descent ascent methods to solve the nonsmooth nonconvex-strongly-concave minimax problems by using dynamic mirror functions, and introduce a convergence analysis framework to conduct rigorous theoretical analysis for our mirror descent ascent methods. For our stochastic algorithms, we first prove that the mini-batch stochastic mirror descent ascent (SMDA) method obtains a gradient complexity of O(\kappa 3\epsilon {-4}) for finding an \epsilon -stationary point, where \kappa denotes the condition number. Further, we propose an accelerated stochastic mirror descent ascent (VR-SMDA) method based on the variance reduced technique. We prove that our VR-SMDA method achieves a lower gradient complexity of O(\kappa 3\epsilon {-3}) . For our deterministic algorithm, we prove that our deterministic mirror descent ascent (MDA) achieves a lower gradient complexity of O(\sqrt{\kappa}\epsilon {-2}) under mild conditions, which matches the best known complexity in solving smooth nonconvex-strongly-concave minimax optimization.