Faster Rates of Convergence to Stationary Points in Differentially Private Optimization
We study the problem of approximating stationary points of Lipschitz and
smooth functions under $(\varepsilon,\delta)$-differential privacy (DP) in both
the finite-sum and stochastic settings. A point $\widehat{w}$ is called an
$\alpha$-stationary point of a function $F:\mathbb{R}^d\rightarrow\mathbb{R}$
if $\|\nabla F(\widehat{w})\|\leq \alpha$. We provide a new efficient algorithm
that finds an
$\tilde{O}\big(\big[\frac{\sqrt{d}}{n\varepsilon}\big]^{2/3}\big)$-stationary
point in the finite-sum setting, where $n$ is the number of samples. This
improves on the previous best rate of
$\tilde{O}\big(\big[\frac{\sqrt{d}}{n\varepsilon}\big]^{1/2}\big)$. We also
give a new construction that improves over the existing rates in the stochastic
optimization setting, where the goal is to find approximate stationary points
of the population risk. Our construction finds a
$\tilde{O}\big(\frac{1}{n^{1/3}} +
\big[\frac{\sqrt{d}}{n\varepsilon}\big]^{1/2}\big)$-stationary point of the
population risk in time linear in $n$. Furthermore, under the additional
assumption of convexity, we completely characterize the sample complexity of
finding stationary points of the population risk (up to polylog factors) and
show that the optimal rate on population stationarity is $\tilde
\Theta\big(\frac{1}{\sqrt{n}}+\frac{\sqrt{d}}{n\varepsilon}\big)$. Finally, we
show that our methods can be used to provide dimension-independent rates of
$O\big(\frac{1}{\sqrt{n}}+\min\big(\big[\frac{\sqrt{rank}}{n\varepsilon}\big]^{2/3},\frac{1}{(n\varepsilon)^{2/5}}\big)\big)$
on population stationarity for Generalized Linear Models (GLM), where $rank$ is
the rank of the design matrix, which improves upon the previous best known
rate.