NeurIPS 2020

Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization

Meta Review

The main result in the paper extends a classical result of Hazan et al to a $O(1/T)$ convergence bound for the duality gap of non-smooth strongly convex-strongly concave min-max problem (instead of the objective gap), proposing a min-max adaptation of the algorithm (Epoch-GDA). They also provide a related bound for finding approximate stationary points in weakly convex-strongly concave problems. Overall the reviewers found the contribution to be a significant and challenging extension over the existing result of Hazan et al. with specific challenges to be overcome in the duality gap version. The authors are strongly recommended to make the promised revisions in the rebutttal as they will embellish the paper.