Public-data Assisted Private Stochastic Optimization: Power and
  Limitations
Enayat Ullah Michael Menart Raef Bassily Cristóbal Guzmán Raman Arora
We study the limits and capability of public-data assisted differentially
private (PA-DP) algorithms. Specifically, we focus on the problem of stochastic
convex optimization (SCO) with either labeled or unlabeled public data. For
complete/labeled public data, we show that any $(\epsilon,\delta)$-PA-DP has
excess risk
$\tilde{\Omega}\big(\min\big\{\frac{1}{\sqrt{n_{\text{pub}}}},\frac{1}{\sqrt{n}}+\frac{\sqrt{d}}{n\epsilon}
\big\} \big)$, where $d$ is the dimension, ${n_{\text{pub}}}$ is the number of
public samples, ${n_{\text{priv}}}$ is the number of private samples, and
$n={n_{\text{pub}}}+{n_{\text{priv}}}$. These lower bounds are established via
our new lower bounds for PA-DP mean estimation, which are of a similar form. Up
to constant factors, these lower bounds show that the simple strategy of either
treating all data as private or discarding the private data, is optimal. We
also study PA-DP supervised learning with \textit{unlabeled} public samples. In
contrast to our previous result, we here show novel methods for leveraging
public data in private supervised learning. For generalized linear models (GLM)
with unlabeled public data, we show an efficient algorithm which, given
$\tilde{O}({n_{\text{priv}}}\epsilon)$ unlabeled public samples, achieves the
dimension independent rate $\tilde{O}\big(\frac{1}{\sqrt{{n_{\text{priv}}}}} +
\frac{1}{\sqrt{{n_{\text{priv}}}\epsilon}}\big)$. We develop new lower bounds
for this setting which shows that this rate cannot be improved with more public
samples, and any fewer public samples leads to a worse rate. Finally, we
provide extensions of this result to general hypothesis classes with finite
fat-shattering dimension with applications to neural networks and non-Euclidean
geometries.