Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimization
We study differentially private (DP) algorithms for smooth stochastic minimax
optimization, with stochastic minimization as a byproduct. The holy grail of
these settings is to guarantee the optimal trade-off between the privacy and
the excess population loss, using an algorithm with a linear time-complexity in
the number of training samples. We provide a general framework for solving
differentially private stochastic minimax optimization (DP-SMO) problems, which
enables the practitioners to bring their own base optimization algorithm and
use it as a black-box to obtain the near-optimal privacy-loss trade-off. Our
framework is inspired from the recently proposed Phased-ERM method [20] for
nonsmooth differentially private stochastic convex optimization (DP-SCO), which
exploits the stability of the empirical risk minimization (ERM) for the privacy
guarantee. The flexibility of our approach enables us to sidestep the
requirement that the base algorithm needs to have bounded sensitivity, and
allows the use of sophisticated variance-reduced accelerated methods to achieve
near-linear time-complexity. To the best of our knowledge, these are the first
linear-time optimal algorithms, up to logarithmic factors, for smooth DP-SMO
when the objective is (strongly-)convex-(strongly-)concave. Additionally, based
on our flexible framework, we derive a new family of near-linear time
algorithms for smooth DP-SCO with optimal privacy-loss trade-offs for a wider
range of smoothness parameters compared to previous algorithms.