Mirror Descent Algorithms with Nearly Dimension-Independent Rates for
  Differentially-Private Stochastic Saddle-Point Problems
Tomás González Cristóbal Guzmán Courtney Paquette
We study the problem of differentially-private (DP) stochastic
(convex-concave) saddle-points in the polyhedral setting. We propose
$(\varepsilon, \delta)$-DP algorithms based on stochastic mirror descent that
attain nearly dimension-independent convergence rates for the expected duality
gap, a type of guarantee that was known before only for bilinear objectives.
For convex-concave and first-order-smooth stochastic objectives, our algorithms
attain a rate of $\sqrt{\log(d)/n} + (\log(d)^{3/2}/[n\varepsilon])^{1/3}$,
where $d$ is the dimension of the problem and $n$ the dataset size. Under an
additional second-order-smoothness assumption, we improve the rate on the
expected gap to $\sqrt{\log(d)/n} + (\log(d)^{3/2}/[n\varepsilon])^{2/5}$.
Under this additional assumption, we also show, by using bias-reduced gradient
estimators, that the duality gap is bounded by $\log(d)/\sqrt{n} +
\log(d)/[n\varepsilon]^{1/2}$ with constant success probability. This result
provides evidence of the near-optimality of the approach. Finally, we show that
combining our methods with acceleration techniques from online learning leads
to the first algorithm for DP Stochastic Convex Optimization in the polyhedral
setting that is not based on Frank-Wolfe methods. For convex and
first-order-smooth stochastic objectives, our algorithms attain an excess risk
of $\sqrt{\log(d)/n} + \log(d)^{7/10}/[n\varepsilon]^{2/5}$, and when
additionally assuming second-order-smoothness, we improve the rate to
$\sqrt{\log(d)/n} + \log(d)/\sqrt{n\varepsilon}$. Instrumental to all of these
results are various extensions of the classical Maurey Sparsification Lemma,
which may be of independent interest.