Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization

In this paper, we study the problem of (finite sum) minimax optimization in the Differential Privacy (DP) model. Unlike most of the previous studies on the (strongly) convex-concave settings or loss functions satisfying the Polyak-Łojasiewicz condition, here we mainly focus on the nonconvexstrongly-concave one, which encapsulates many models in deep learning such as deep AUC maximization. Specifically, we first analyze a DP version of Stochastic Gradient Descent Ascent (SGDA) and show that it is possible to get a DP estimator whose l 2 -norm of the gradient for the empirical risk function is upper bounded by Õ( d 1/4 (nϵ) 1/2 ), where d is the model dimension and n is the sample size. We then propose a new method with less gradient noise variance and improve the upper bound to Õ( d 1/3 (nϵ) 2/3 ), which matches the best-known result for DP Empirical Risk Minimization with non-convex loss. We also discussed several lower bounds of private minimax optimization. Finally, experiments on AUC maximization, generative adversarial networks, and temporal difference learning with real-world data support our theoretical analysis. Recently, DP (finite sum) minimax optimization has been widely studied (see the related work section for details). However, compared to DP Empirical Risk Minimization (Wang et al., 2017 (Wang et al., , 2021;; Wang and Xu, 2019b) , DP Minimax optimization is still in its early stages of development. Specifically, most of the previous work focuses on the case where