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

2025/03/24 by Zhang, Ruijia, Lei, Mingxi, Ding, Meng +3 · 3 citations
#FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2503.18317

Abstract

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-Lojasiewicz condition, here we mainly focus on the nonconvex-strongly-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₂-norm of the gradient for the empirical risk function is upper bounded by O(\fracd^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 O(\fracd^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.

Cited by

• Attributing Data for Sharpness-Aware Minimization
• Differentially Private Sparse Linear Regression with Heavy-tailed Responses
• Second-Order Convergence in Private Stochastic Non-Convex Optimization

Related

• Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates
• Stability and Generalization of Differentially Private Minimax Problems
• Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimization
• Differentially Private SGDA for Minimax Problems
• Output Perturbation for Differentially Private Convex Optimization: Faster and More General