Timezone: »

 
Poster
Efficient Mirror Descent Ascent Methods for Nonsmooth Minimax Problems
Feihu Huang · Xidong Wu · Heng Huang

Wed Dec 08 04:30 PM -- 06:00 PM (PST) @ Virtual
in Poster Session 4 »
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. We conduct the experiments on fair classifier and robust neural network training tasks to demonstrate the efficiency of our new algorithms.
Keywords: Theory · Deep Learning · Optimization

Author Information

Feihu Huang (University of Pittsburgh)
Xidong Wu (University of Pittsburgh)
Heng Huang (University of Pittsburgh)

More from the Same Authors