# Optimal Differentially Private Learning with Public Data

Andrew Lowy University of Southern California<EMAIL_ADDRESS>Zeman Li
University of Southern California<EMAIL_ADDRESS>Tianjian Huang University
of Southern California<EMAIL_ADDRESS>Meisam Razaviyayn University of
Southern California<EMAIL_ADDRESS>
###### Abstract

Differential Privacy (DP) ensures that training a machine learning model does
not leak private data. However, the cost of DP is lower model accuracy or
higher sample complexity. In practice, we may have access to auxiliary public
data that is free of privacy concerns. This has motivated the recent study of
what role public data might play in improving the accuracy of DP models. In
this work, we assume access to a given amount of public data and settle the
following fundamental open questions: 1\. What is the optimal (worst-case)
error of a DP model trained over a private data set while having access to
side public data? What algorithms are optimal? 2. How can we harness public
data to improve DP model training in practice? We consider these questions in
both the local and central models of DP. To answer the first question, we
prove tight (up to constant factors) lower and upper bounds that characterize
the optimal error rates of three fundamental problems: mean estimation,
empirical risk minimization, and stochastic convex optimization. We prove that
public data reduces the sample complexity of DP model training. Perhaps
surprisingly, we show that the optimal error rates can be attained (up to
constants) by either discarding private data and training a public model, or
treating public data like it’s private data and using an optimal DP algorithm.
To address the second question, we develop novel algorithms which are “even
more optimal” (i.e. better constants) than the asymptotically optimal
approaches described above. For local DP mean estimation with public data, our
algorithm is optimal including constants. Empirically, our algorithms show
benefits over existing approaches for DP model training with side access to
public data.

##  1 Introduction

Training machine learning (ML) models on people’s data can leak sensitive
information, violating their privacy [FJR15, SSSS17, CTW+21]. Differential
Privacy (DP) prevents such leaks by providing a rigorous guarantee that no
attacker can learn too much about any individual’s data [DMNS06]. DP has been
successfully deployed by various companies [App16, TVV+17, UEPK14, DKY17], and
by government agencies such as the U.S. Census Bureau [U.S20]. However, a
major hindrance to more widespread adoption of DP in training ML models is
that DP models are less accurate than their non-private counterparts.

Leveraging public data—that is free of privacy concerns—is a promising and
practically important avenue for closing the accuracy gap between DP and non-
private models [PAE+17, AKZ+17, FMTT18, AGM+22]. Public data may be provided
by people who volunteer their data (e.g. product developers or early testers)
[Chu05, FMTT18] or by people who receive incentives in exchange for their
data. Data that is generated synthetically [TKP19, VTB+20, BSV22, HVZ23] or
released through a legal process [KY04] may serve as additional sources of
public data.

A recent line of work has sought to understand the role of public data in DP
learning [BTGT18, FMTT18, KDRT21, WZ20, ZWB20, LTLH21, LVS+21, PAE+17, PSM+18,
YZCL21, ABM19, BKS22, FGK21, AGM+22]. Despite progress on both the theoretical
and empirical fronts, important fundamental questions about DP learning with
public data remain open. In this work, we consider the following fundamental
questions:

Question 1. What is the optimal (minimax) error of DP learning with public
data? Question 2. Can we provide improved performance (e.g. smaller error
including constants) over the asymptotically optimal algorithms?

##### Contributions:

To address Question 1, we characterize the optimal minimax error (up to
constants) of semi-DP [BNS13, ABM19] learning algorithms—algorithms that are
DP with respect to private data, but not necessarily DP w.r.t. public data
(Definition 4). We provide tight (up to constants) lower and upper bounds for
three fundamental problems: mean estimation, empirical risk minimization
(ERM), and stochastic convex optimization (SCO). The ERM problem corresponds
to minimizing the training loss of a ML model, while SCO corresponds to
minimizing test loss. We consider both the local [KLN+11, DJW13] and central
[DMNS06] models of (pure and approximate) DP. For population mean estimation
and SCO, we assume access to in-distribution public data. For ERM, the public
data may be out-of-distribution.

Our results reveal both the limitations and power of using public data for DP
model training. On the negative side, our lower bounds show that obtaining
asymptotic improvements beyond the optimal DP rates (without public data) is
impossible if the number of public samples $n_{\text{pub}}$ is small (e.g.
$n_{\text{pub}}=O(1)$), or if $d/\varepsilon$ is small relative to the total
number of samples $n=n_{\text{pub}}+n_{\text{priv}}$.111Here $d$ denotes the
number of model parameters and $\varepsilon$ is the DP parameter; smaller
$\varepsilon$ provides more privacy. On the positive side, we show that with
enough public samples or in high privacy regime (small $\varepsilon$),
asymptotic improvements over the optimal DP rates are indeed possible. For
example, without public data, if $d=n$ and $\varepsilon=1$, then no
$\varepsilon$-DP algorithm can estimate the mean of a bounded random variable
with $\ell_{2}$-accuracy better than $\Theta(1)$. On the other hand, we show
that with $n_{\text{pub}}=\sqrt{n}$ or $n_{\text{pub}}=0.01n$ public samples
at our disposal, the minimax error of DP estimation improves significantly to
$\Theta(1/\sqrt{n})$ or $\Theta(1/n)$. Note that $\Theta(1/n)$ is the best
achievable rate even without any privacy constraints. More generally—for
population mean estimation and SCO, with either central or local DP—we get
“privacy for free” (up to constants) whenever $n_{\text{pub}}\geq cn$ for some
absolute constant $c$. See Fig. 1 for some of the minimax optimal error rates
for semi-DP and semi-LDP learning in this paper.

Figure 1: Minimax optimal error rates for $\varepsilon$-semi-DP and
$\varepsilon$-semi-LDP. *Semi-DP mean estimation and SCO lower bounds are only
tight if $n_{\text{pub}}=O(n\varepsilon/d)$ or $d=O(1)$. Dependence on range
and Lipschitz parameters, constraint set diameter omitted. See main
text/Appendix for $\delta>0$ and strongly convex SCO results.

In all of the cases that we study—mean estimation, ERM, and SCO under both
local and central semi-DP—tight upper bounds on the error can be obtained by
taking the minimum of two errors: 1) the error of the optimal DP algorithm
that privatizes all of the data including public data (e.g. DP-SGD for DP SCO
[BFTT19]); and 2) the error of an appropriate “throw-away” algorithm that
discards the private data and uses an optimal non-private algorithm (e.g. SGD
for SCO) on the public data. Neither of these algorithms seems to leverage the
full data set in the most effective way: throw-away completely ignores
valuable private data, while standard DP algorithms (intuitively) seem to be
adding more noise than necessary to privatize public data. This observation
leads us to Question 2.

To address Question 2, we develop novel semi-DP algorithms that are (central
or local) DP w.r.t. the private samples, but not DP in the traditional sense.
Our algorithms add less noise than would be necessary to privatize the full
data set (including public). By doing so, we are able to harness the public
data and achieve optimal error bounds with significantly improved constants
over the asymptotically optimal algorithms discussed above. In the case of
locally DP mean estimation, our algorithm is truly optimal including
constants. We also support this finding empirically, showing that our
algorithms outperform the asymptotically optimal algorithms discussed above,
even when the optimal DP algorithm is pre-trained on the public data.

In Appendix A, we give an overview of our techniques and further discussion of
related work.

###  1.1 Preliminaries and Notation

Let $\|\cdot\|$ be the $\ell_{2}$ norm and $\mathcal{X}$ denote a data
universe. Function $g:\mathcal{W}\to\mathbb{R}$ is $\mu$-strongly convex if
$g(\alpha w+(1-\alpha)w^{\prime})\leq\alpha
g(w)+(1-\alpha)g(w^{\prime})-\frac{\alpha(1-\alpha)\mu}{2}\|w-w^{\prime}\|^{2}$
for all $\alpha\in[0,1]$ and all $w,w^{\prime}\in\mathcal{W}$. If $\mu=0,$ we
say $g$ is convex. Function $f:\mathcal{W}\times\mathcal{X}\to\mathbb{R}$ is
uniformly $L$-Lipschitz in $w$ if
$\sup_{x\in\mathcal{X}}|f(w,x)-f(w^{\prime},x)|\leq L\|w-w^{\prime}\|$.
$\mathbb{B}=\\{x\in\mathbb{R}^{d}|\|x\|\leq 1\\}$ denotes the unit
$\ell_{2}$-ball in $\mathbb{R}^{d}$.

######  Definition 1 (Differential Privacy [DMNS06]).

Let $\varepsilon\geq 0,~{}\delta\in[0,1).$ A randomized algorithm
$\mathcal{A}:\mathcal{X}^{n}\to\mathcal{W}$ is
$(\varepsilon,\delta)$-differentially private (DP) if for all pairs of
adjacent data sets $X,X^{\prime}\in\mathcal{X}^{n}$ and all measurable subsets
$S\subseteq\mathcal{W}$, we have $\mathbb{P}(\mathcal{A}(X)\in S)\leq
e^{\varepsilon}\mathbb{P}(\mathcal{A}(X^{\prime})\in S)+\delta$.

Definition 1 ensures that no attacker can learn much more about any person’s
data than they could have learned had that person’s data never been used for
training. If $\delta=0$, we write $\varepsilon$-DP.

######  Definition 2 (Zero-Concentrated Differential Privacy (zCDP) [BS16]).

A randomized algorithm $\mathcal{A}:\mathcal{X}^{n}\to\mathcal{W}$ satisfies
$\rho$-zero-concentrated differential privacy ($\rho$-zCDP) if for all pairs
of adjacent data sets $X,X^{\prime}\in\mathcal{X}^{n}$ and all
$\alpha\in(1,\infty)$, we have
$D_{\alpha}(\mathcal{A}(X)||\mathcal{A}(X^{\prime}))\leq\rho\alpha$, where
$D_{\alpha}(\mathcal{A}(X)||\mathcal{A}(X^{\prime}))$ is the $\alpha$-Rényi
divergence222For distributions $P$ and $Q$ with probability density/mass
functions $p$ and $q$, $D_{\alpha}(P||Q):=\frac{1}{\alpha-1}\ln\left(\int
p(x)^{\alpha}q(x)^{1-\alpha}dx\right)$ [Rén61, Eq. 3.3]. between the
distributions of $\mathcal{A}(X)$ and $\mathcal{A}(X^{\prime})$.

zCDP is weaker than $\varepsilon$-DP, but stronger than
$(\varepsilon,\delta)$-DP ($\delta>0$) in the following sense:

######  Proposition 3.

[BS16, Proposition 1.3] If $\mathcal{A}$ is $\rho$-zCDP, then $\mathcal{A}$ is
$(\rho+2\sqrt{\rho\log(1/\delta)},\delta)$ for any $\delta>0$.

We now define semi-DP [BNS13, ABM19], a relaxation of DP that only requires
$\mathcal{A}$ to preserve the privacy of a pre-specified subset of people’s
data $\mathcal{X}_{\text{priv}}\subset\mathcal{X}$:

######  Definition 4 (Semi-Differential Privacy [BNS13, ABM19]).

For $x_{i}\in\mathcal{X}$, say two data sets $X,X^{(i)}\in\mathcal{X}^{n}$ are
$x_{i}$-adjacent if they differ only in the data point $x_{i}$: $X\Delta
X^{(i)}=\\{x_{i},x^{\prime}_{i}\\}$ for some $x^{\prime}_{i}\in\mathcal{X}$.
Algorithm $\mathcal{A}:\mathcal{X}^{n}\to\mathcal{W}$ is (centrally)
$(\varepsilon,\delta)$-semi-DP if for all private samples
$x_{i}\in\mathcal{X}_{\text{priv}}$, all pairs of $x_{i}$-adjacent data sets
$X,X^{(i)}\in\mathcal{X}^{n}$, and all measurable $S\subset\mathcal{W}$, we
have

$\mathbb{P}(\mathcal{A}(X)\in S)\leq
e^{\varepsilon}\mathbb{P}(\mathcal{A}(X^{(i)})\in S)+\delta.$

We can define $\rho$-semi-zCDP analogously. We define semi-LDP in Section 3,
which is a similar relaxation of local DP (LDP) [KLN+11, DJW13]. Local DP is a
stronger notion of DP that does not allow data to be leaked even to the data
scientist or central server. To distinguish Definition 4 from semi-LDP, we
sometimes refer to algorithms that satisfy Definition 4 as centrally semi-DP.

###  1.2 Roadmap

We begin by studying the central model of semi-DP in Section 2. We give tight
error bounds (up to constants) for mean estimation in Section 2.1 and provide
a novel algorithm with better constants than the asymptotically optimal
algorithms. In Section 2.2 and Section 2.3, we characterize the optimal excess
risk of semi-DP ERM and SCO respectively. We give an improved semi-DP
algorithm for SCO in Section C.3.1. In Section 3, we turn to the local model
of semi-DP. We characterize the optimal error rates (up to constants) for mean
estimation in Section 3.1 and SCO in Section 3.2. Along the way, we develop
novel semi-LDP algorithms with smaller error than the asymptotically optimal
algorithms. We present experimental evaluations of our algorithms in Sections
4 and E.

##  2 Optimal Centrally Private Learning with Public Data

###  2.1 Optimal Semi-DP Mean Estimation

In this section, we determine the minimax optimal semi-DP error rates for
estimating the mean of an unknown bounded distribution.333Our analysis also
extends to unbounded distributions with bounded $k$-th order moment for some
$k\geq 2$. Proofs are deferred to Section C.1.2.

Consider the following problem: given $n_{\text{priv}}$ private samples
$X_{\text{priv}}\subseteq\mathbb{B}$ and $n_{\text{pub}}$ public samples
$X_{\text{pub}}\subseteq\mathbb{B}$, drawn from an unknown distribution $P$ on
$\mathbb{B}$, estimate the population mean
$\mathcal{A}(X)\approx\mathbb{E}_{x\sim P}[x]$ subject to the constraint that
$\mathcal{A}$ satisfies semi-DP. Defining $n=n_{\text{priv}}+n_{\text{pub}}$,
we will characterize the minimax squared error of population mean estimation
under $(\varepsilon,\delta)$-semi-DP:

$\mathcal{M}_{\text{pop}}(\varepsilon,\delta,n_{\text{priv}},n,d):=\inf_{\mathcal{A}\in\mathbb{A}_{\varepsilon,\delta}(\mathbb{B})}\sup_{P}\mathbb{E}_{\mathcal{A},X\sim
P^{n}}\left[\|\mathcal{A}(X)-\mathbb{E}_{x\sim P}[x]\|^{2}\right],$ (1)

where $\mathbb{A}_{\varepsilon,\delta}(\mathbb{B})$ denotes the set of all
$(\varepsilon,\delta)$-semi-DP estimators
$\mathcal{A}:\mathbb{B}^{n}\to\mathbb{B}$, and
$|X_{\text{priv}}|=n_{\text{priv}}$.

######  Theorem 5.

Let $\varepsilon\leq d/8$ and either
$n_{\text{pub}}\lesssim\frac{n\varepsilon}{d}$ or $d\lesssim 1$. Then, there
exist absolute constants $c$ and $C$, with $0<c\leq C$, such that

$c\min\left\\{\frac{1}{n_{\text{pub}}},\frac{d^{2}}{n^{2}\varepsilon^{2}}+\frac{1}{n}\right\\}\leq\mathcal{M}_{\text{pop}}(\epsilon,\delta=0,n_{\text{priv}},n,d)\leq
C\min\left\\{\frac{1}{n_{\text{pub}}},\frac{d^{2}}{n^{2}\varepsilon^{2}}+\frac{1}{n}\right\\}.$
(2)

The upper bound in 2 holds for any $n_{\text{pub}},d$. Further, for any
$n_{\text{pub}},d$ and any $\delta\in[0,\varepsilon]$, we have

$c\min\left\\{\frac{1}{n_{\text{pub}}},\frac{1}{n^{2}\varepsilon^{2}}+\frac{1}{n}\right\\}\leq\mathcal{M}_{\text{pop}}(\epsilon,\delta,n_{\text{priv}},n,d)\leq
C\min\left\\{\frac{1}{n_{\text{pub}}},\frac{d\ln(1/\delta)}{n^{2}\varepsilon^{2}}+\frac{1}{n}\right\\}.$
(3)

If $n_{\text{pub}}>\frac{n^{2}\varepsilon^{2}}{d^{2}}$, then the
$\varepsilon\text{-semi-DP}$ upper bound in 2 is $O(1/n_{\text{pub}})$, which
improves over the optimal $\varepsilon$-DP MSE of
$\Theta(\min(1,(d/n\varepsilon)^{2})$. If $n_{\text{pub}}=\Theta(n)$ (e.g.
$n_{\text{pub}}=.01n$), then we get “privacy for free”: the semi-DP error
rates match the optimal non-private rate $\Theta(1/n)$ (up to constants). This
is also the case for semi-DP SCO in Section 2.3, semi-LDP mean estimation in
Section 3.1, and semi-LDP SCO in Section 3.2. We conjecture that the upper
bound in 3 is tight for all $d$, but proving a tight lower bound for the
$\delta>0,d\gg 1$ case is challenging.

To prove our lower bounds, we develop a new technique: Theorem 23 in Section
C.1.2, which is a semi-DP analogue of Fano’s inequality [Yu97, Duc21]. For the
upper bounds, the first term in each minima is attained by the throw-away
estimator $\mathcal{A}(X)=\frac{1}{n_{\text{pub}}}\sum_{x\in
X_{\text{pub}}}x$. The second terms in the minima 2 and 3 are attained by the
DP (hence semi-DP) Laplace and Gaussian mechanisms, respectively [DR+14].

In the next subsection, we show that the asymptotically optimal algorithms
discussed above have suboptimal constants. In particular, we provide improved
semi-DP estimators with smaller error.

####  2.1.1 An “Even More Optimal” Semi-DP Algorithm for Mean Estimation

Before presenting our improved semi-DP algorithms, we precisely describe the
worst-case error of the optimal algorithms discussed in the preceding
subsection. We will consider $\rho$-semi-zCDP, which facilitates a sharp
characterization of the privacy of the Gaussian mechanism. Note that the lower
bound in 3 also holds for semi-zCDP, since
$\varepsilon^{2}/\ln(1/\delta)$-zCDP implies $(O(\varepsilon),\delta)$-DP, by
Proposition 3.

######  Definition 6.

Let $\mathcal{P}(B,V)$ be the collection of all distributions $P$ on
$\mathbb{R}^{d}$ such that for any $x\sim P$, we have $\text{Var}(x)=V^{2}$and
$\|x\|\leq B$, $P$-almost surely.

######  Lemma 7.

The error of the $\rho$-semi-zCDP throw-away algorithm
$\mathcal{A}(X)=\frac{1}{n_{\text{pub}}}\sum_{x\in X_{\text{pub}}}x$ is

$\sup_{P\in\mathcal{P}(B,V)}\mathbb{E}_{X\sim
P^{n}}\left[\|\mathcal{A}(X)-\mathbb{E}_{x\sim
P}[x]\|^{2}\right]=\frac{V^{2}}{n_{\text{pub}}}.$

Further, let $\bar{X}$ be the average of the public and private samples. The
minimax error of the $\rho$-zCDP Gaussian mechanism
$\mathcal{G}(X)=\bar{X}+\mathcal{N}\left(0,\sigma^{2}\mathbf{I}_{d}\right)$ is

$\inf_{\rho\text{-zCDP}~{}\mathcal{G}}\sup_{P\in\mathcal{P}(B,V)}\mathbb{E}_{\mathcal{G},X\sim
P^{n}}\left[\|\mathcal{G}(X)-\mathbb{E}_{x\sim
P}[x]\|^{2}\right]=\frac{2dB^{2}}{\rho n^{2}}+\frac{V^{2}}{n}.$

Intuitively, it seems like the estimators in Lemma 7 do not harness the public
and private data in the most effective way possible, despite being optimal up
to constants. Throw-away fails to utilize the private data at all, while the
Gaussian mechanism gives equal weight to $X_{\text{priv}}$ and
$X_{\text{pub}}$ (regardless of $\rho,d,n_{\text{priv}}$), and provides
unnecessary privacy for $X_{\text{pub}}$. We now present a $\rho$-semi-zCDP
estimator that is “even more optimal” than the estimators in Lemma 7, meaning
our estimator has smaller worst-case error (accounting for constants). We
define the family of Weighted-Gaussian estimators:

$\mathcal{A}_{r}(X):=\sum_{x\in X_{\text{priv}}}rx+\sum_{x\in
X_{\text{pub}}}\left(\frac{1-n_{\text{priv}}r}{n_{\text{pub}}}\right)x+\mathcal{N}(0,\sigma_{r}^{2}\mathbf{I}_{d}),$
(4)

for $r\in[0,1/n_{\text{priv}}]$. This estimator can recover both the throw-
away and standard Gaussian mechanisms by choosing $r=0$ or $r=1/n$.
Intuitively, as $\rho/d$ shrinks, the accuracy cost of adding privacy noise
grows, so we should choose smaller $r$ to reduce the sensitivity of
$\mathcal{A}_{r}$. On the other hand, smaller $r$ increases the variance of
$\mathcal{A}_{r}$ on $X_{\text{pub}}$. By choosing $r$ optimally (depending on
$\rho,d,n_{\text{priv}},B,V$), $\mathcal{A}_{r}$ achieves smaller MSE than
both throw-away and the Gaussian mechanism:

######  Proposition 8.

There exists $r>0$ such that, with proper choice of $\sigma_{r}$,
$\mathcal{A}_{r}$ is $\rho$-semi-zCDP, and

$\sup_{P\in\mathcal{P}(B,V)}\mathbb{E}_{X\sim
P^{n}}\left[\|\mathcal{A}_{r}(X)-\mathbb{E}_{x\sim
P}[x]\|^{2}\right]<\min\left(\frac{V^{2}}{n_{\text{pub}}},\frac{2dB^{2}}{\rho
n^{2}}+\frac{V^{2}}{n}\right).$ (5)

Further, if $\frac{V^{2}}{n_{\text{pub}}}\leq\frac{2dB^{2}}{\rho n^{2}}$, then
the quantitative advantage of $\mathcal{A}_{r}$ is

$\sup_{P\in\mathcal{P}(B,V)}\mathbb{E}_{X\sim
P^{n}}\left[\|\mathcal{A}_{r}(X)-\mathbb{E}_{x\sim
P}[x]\|^{2}\right]\leq\left(\frac{q^{2}+qs^{2}}{q^{2}+2qs^{2}+s^{4}}\right)\min\left(\frac{V^{2}}{n_{\text{pub}}},\frac{2dB^{2}}{\rho
n^{2}}+\frac{V^{2}}{n}\right),$ (6)

where $q=2+\frac{n_{\text{priv}}\rho V^{2}}{dB^{2}}$ and
$s=\frac{Vn_{\text{priv}}\sqrt{\rho}}{B\sqrt{dn_{\text{pub}}}}$.

Let us consider some numerical examples to understand the advantage of our
Weighted-Gaussian over the asymptotically optimal baselines (throw-away and
the Gaussian mechanism).

######  Example 9.

Consider 6 and assume $n=10,000$ in the following examples:

  * •

The role of $d/\rho$: Fix $n_{\text{pub}}=0.01n$ and $B=25V$. If $\rho=1$ and
$d=n$, then the MSE of our Weighted Gaussian $\mathcal{A}_{r}$ is smaller than
the MSE of the throw-away and standard Gaussian baselines by a factor of
$\approx 1.08$. If $d$ changes to $d=n/10$ or $\rho$ changes to $\rho=10$,
then the MSE of $\mathcal{A}_{r}$ is $\approx 1.78$ times smaller than that of
the baselines.

  * •

The role of $n_{\text{pub}}$ and $d/\rho$: Fix $d=\sqrt{n}=n/100$ and $B=25V$.
If $\rho=0.1$ and $n_{\text{pub}}=0.01n$, then the MSE of our Weighted
Gaussian $\mathcal{A}_{r}$ is smaller than the MSE of throw-away and standard
Gaussian by a factor of $\approx 1.78$. If $n_{\text{pub}}$ changes to
$n_{\text{pub}}=0.008n$, then the MSE of $\mathcal{A}_{r}$ is $\approx 1.98$
times smaller than that of the baselines. If $n_{\text{pub}}=n^{1/4}=0.001n$
and $\rho=0.01$, then the MSE of $\mathcal{A}_{r}$ is $\approx 1.80$ times
smaller than that of the baselines.

  * •

The role of $B$, $n_{\text{pub}}$, and $d/\rho$: Fix $B=500V$ and $\rho=1$. If
$n_{\text{pub}}=n^{1/4}$ and $d=\sqrt{n}$, then the MSE of our Weighted
Gaussian $\mathcal{A}_{r}$ is $\approx 1.20$ times smaller than the MSE of
throw-away and standard Gaussian. If $n_{\text{pub}}$ shrinks to
$n_{\text{pub}}=n^{1/10}$, then the MSE of $\mathcal{A}_{r}$ is $\approx 1.80$
times smaller than the baselines. If $B$ shrinks to $B=1$ and
$n_{\text{pub}},d$ increase to $n_{\text{pub}}=n/2$ and $d=n$, then the MSE of
our algorithm is $1.2$ times smaller than the MSE of the baselines.

For $\varepsilon\text{-semi-DP}$, using Laplace noise instead of Gaussian
noise in 4 yields an estimator with smaller error than the $\varepsilon$-DP
Laplace mechanism and throw-away.

###  2.2 Optimal Semi-DP Empirical Risk Minimization

For a given
$X=(X_{\text{priv}},X_{\text{pub}})\in\mathcal{X}_{\text{priv}}^{n_{\text{priv}}}\times\mathcal{X}_{\text{pub}}^{n_{\text{pub}}}$
and parameter domain $\mathcal{W}$, consider the ERM problem:

$\min_{w\in\mathcal{W}}\left(\widehat{F}_{X}(w):=\frac{1}{n}\sum_{j=1}^{n}f(w,x_{j})\right),$

where $f(\cdot,x)$ is a loss function (e.g. squared loss for linear
regression). Here, we do not assume that $X_{\text{priv}}$ and
$X_{\text{pub}}$ are independent or drawn from the same distribution. We
measure the (in-sample) performance of a training algorithm
$\mathcal{A}:\mathcal{X}^{n}\to\mathcal{W}$ by its excess empirical risk

$\mathbb{E}_{\mathcal{A}}\widehat{F}_{X}(\mathcal{A}(X))-\widehat{F}_{X}^{*}=\mathbb{E}_{\mathcal{A}}\widehat{F}_{X}(\mathcal{A}(X))-\min_{w^{\prime}\in\mathcal{W}}\widehat{F}_{X}(w^{\prime}).$

######  Definition 10.

Let $\mathcal{F}_{\mu,L,D}$ be the set of all functions
$f:\mathcal{W}\times\mathcal{X}\to\mathbb{R}$ that are uniformly $L$-Lipschitz
and $\mu$-strongly convex ($\mu\geq 0$) in $w$ for some convex compact
$\mathcal{W}\subset\mathbb{R}^{d}$ with $\ell_{2}$-diameter bounded by $D>0$
and some
$\mathcal{X}=\mathcal{X}_{\text{priv}}\bigcup\mathcal{X}_{\text{pub}}$. Let
$\mathcal{F}_{L,D}=\mathcal{F}_{\mu=0,L,D}$.

Also, define the minimax excess empirical risk of $\varepsilon$-semi-DP
(strongly) convex ERM as

$\mathcal{R}_{\text{ERM}}(\varepsilon,n_{\text{priv}},n,d,L,D,\mu):=\inf_{\mathcal{A}\in\mathbb{A}_{\varepsilon}}\sup_{f\in\mathcal{F}_{\mu,L,D}}\sup_{\left\\{X_{\text{priv}}\in\mathcal{X}_{\text{priv}}^{n_{\text{priv}}},X_{\text{pub}}\in\mathcal{X}_{\text{pub}}^{n_{\text{pub}}}\right\\}}\mathbb{E}_{\mathcal{A}}\widehat{F}_{X}(\mathcal{A}(X))-\widehat{F}_{X}^{*},$
(7)

where $\mathbb{A}_{\varepsilon}$ is the set of all $\varepsilon\text{-semi-
DP}$ algorithms $\mathcal{A}:\mathcal{X}^{n}\to\mathcal{W}$ for some
$\mathcal{X},\mathcal{W}$.

######  Theorem 11.

There exist absolute constants $c$ and $C$, with $0<c\leq C$, such that

$cLD\min\left\\{\frac{n_{\text{priv}}}{n},\frac{d}{n\varepsilon}\right\\}\leq\mathcal{R}_{\text{ERM}}(\epsilon,n_{\text{priv}},n,d,L,D,\mu=0)\leq
CLD\min\left\\{\frac{n_{\text{priv}}}{n},\frac{d}{n\varepsilon}\right\\}.$ (8)

See Section C.2 for the strongly convex result. We prove the lower bound in
Theorem 11 by reducing ERM to empirical mean estimation [BST14] and then lower
bounding the semi-DP MSE of empirical mean estimation with a packing argument.
The upper bound is achieved by two algorithms: The first term in the minimum
is achieved by the throw-away algorithm
$\mathcal{A}(X)\in\operatorname*{argmin}_{w\in\mathcal{W}}\sum_{x\in
X_{\text{pub}}}f(w,x)$. The second term is achieved by the $\varepsilon$-DP
exponential mechanism [BST14].

In the absence of public data, the minimax optimal excess risk of convex DP
ERM is $\Theta\left(LD\min(1,d/(n\varepsilon))\right)$ [BST14]; the “trivial
algorithm” that returns $\mathcal{A}(X)=w_{0}\in\mathcal{W}$ independent of
$X$ has excess risk $\leq LD$. Thus, public data reduces the error of DP ERM
whenever $n_{\text{priv}}<d/\varepsilon$, or equivalently
$n_{\text{pub}}>n-d/\varepsilon$. This improvement is possible because the
throw-away algorithm outperforms the trivial algorithm (and, if
$n_{\text{pub}}$ or $d/\varepsilon$ is large enough, the exponential
mechanism). On the other hand, if $n_{\text{pub}}\leq n-d/\varepsilon$, then
public data does not allow for improved accuracy (asymptotically) over the
optimal $\varepsilon$-DP exponential mechanism.

######  Remark 12.

The same minimax risk bound 8 holds up to a logarithmic factor if we replace
$\mathcal{F}_{\mu=0,L,D}$ by set of all Lipschitz non-convex loss functions in
the definition 7. However, the optimal semi-DP algorithms are inefficient for
non-convex loss functions. See Section C.2 for details.

###  2.3 Optimal Semi-DP Stochastic Convex Optimization

In stochastic convex optimization (SCO), we are given $n$ i.i.d. samples from
an unknown distribution $X\sim P^{n}$ (with $n_{\text{priv}}$ of them being
private), and aim to approximately minimize the expected population loss
$F(w):=\mathbb{E}_{x\sim P}[f(w,x)]$. We measure the quality of a learner
$\mathcal{A}$ by its excess population risk

$\mathbb{E}_{\mathcal{A},X\sim
P^{n}}F(\mathcal{A}(X))-F^{*}:=\mathbb{E}_{\mathcal{A},X\sim
P^{n}}\mathbb{E}_{x\sim
P}[f(\mathcal{A}(X),x)]-\min_{w^{\prime}\in\mathcal{W}}\mathbb{E}_{x\sim
P}f(w^{\prime},x).$

Denote the minimax optimal excess population risk of semi-DP SCO by

$\mathcal{R}_{\text{SCO}}(\varepsilon,\delta,n_{\text{priv}},n,d,L,D,\mu):=\inf_{\mathcal{A}\in\mathbb{A}_{\varepsilon,\delta}}\sup_{f\in\mathcal{F}_{\mu,L,D}}\sup_{P}\mathbb{E}_{\mathcal{A},X\sim
P^{n}}F(\mathcal{A}(X))-F^{*},$ (9)

where $\mathbb{A}_{\varepsilon,\delta}$ contains all
$(\varepsilon,\delta)$-semi-DP algorithms
$\mathcal{A}:\mathcal{X}^{n}\to\mathcal{W}$ for some
$\mathcal{X},\mathcal{W}$, and $|X_{\text{priv}}|=n_{\text{priv}}$.

######  Theorem 13.

Let $\varepsilon\leq d/8$ and either
$n_{\text{pub}}\lesssim\frac{n\varepsilon}{d}$ or $d\lesssim 1$. Then, there
exist absolute constants $0<c\leq C$ such that

$cLD\min\left\\{\frac{1}{\sqrt{n_{\text{pub}}}},\frac{d}{n\varepsilon}+\frac{1}{\sqrt{n}}\right\\}\leq\mathcal{R}_{\text{SCO}}(\epsilon,\delta=0,n_{\text{priv}},n,d,L,D,\mu=0)\leq
CLD\min\left\\{\frac{1}{\sqrt{n_{\text{pub}}}},\frac{d}{n\varepsilon}+\frac{1}{\sqrt{n}}\right\\}.$

The above upper bound holds for any $n_{\text{pub}},d$.

We provide the $\mu$-strongly convex and $\delta>0$ results in Section C.3.
The main tool that we use to prove the lower bound is our semi-DP Fano’s
method (Theorem 23).

Let us compare the $\varepsilon$-semi-DP bound for SCO in Theorem 13 with the
ERM bound in Theorem 11. Fix $d=1=L=D$ for simplicity. Depending on the values
of $\varepsilon$ and $n_{\text{priv}}$, the minimax excess population risk
(“test loss”) of SCO may either be larger or smaller than the excess empirical
risk (“training loss”) of ERM. For example, if $\varepsilon\approx 1$, then
the semi-DP excess empirical risk $\Theta(1/n)$ is smaller than the excess
population risk $\Theta(1/\sqrt{n})$. On the other hand, suppose
$\varepsilon\approx 1/n$ and $n_{\text{priv}}\approx n^{2/3}$: then the semi-
DP excess empirical risk $\Theta(1/n^{1/3})$ is larger than the excess
population risk $\Theta(1/\sqrt{n})$. This is surprising: for both non-private
learning and DP learning (with $n_{\text{pub}}=0$), the optimal error of ERM
is never larger than that of SCO. While it may seem counter-intuitive that
minimizing the training loss can be harder than minimizing test loss, there is
a natural explanation: For SCO, a small amount of public data gives us free
information about the private data, since $X\sim P^{n}$ is i.i.d. by
assumption. By contrast, for ERM, the public data does not give us any
information about the private data, since $X$ is arbitrary (not necessarily
i.i.d.). Thus, the (appropriate) throw-away algorithm is more effective at
minimizing $F$ than $\widehat{F}_{X}$ when $n_{\text{pub}}$ is small but
positive.

In Section C.3.1, we give a noisy stochastic gradient Algorithm 1 for semi-DP
SCO that uses 4 to estimate $\nabla F(w)$ in each iteration. Our algorithm has
smaller excess risk (accounting for constants) than the state-of-the-art
linear-time algorithm for DP-SCO whose privacy analysis does not require
convexity [LR23a]. We empirically evaluate our algorithm in Sections 4 and E.

##  3 Optimal Locally Private Learning with Public Data

We now turn to a stronger privacy notion that we refer to as semi-local DP
(semi-LDP, Definition 14). Semi-LDP guarantees privacy for each private
$x_{i}$, without requiring person $i$ to trust anyone else (e.g. data
scientist). Semi-LDP generalizes LDP [KLN+11, DJW13], which has been deployed
in industry [App16, UEPK14, DKY17].

Following [DR19], we permit algorithms to be fully interactive: algorithms may
adaptively query the same person $i$ multiple times over the course of $T$
“communication rounds.” We denote $i$’s message in round $t$ by
$Z_{i,t}\in\mathcal{Z}$. Full interactivity is the most general notion of
interactivity. If $T=1$, then the algorithm is sequentially interactive
[DJW13]. Essentially, semi-LDP requires the messages $\\{Z_{i,t}\\}_{t\in[T]}$
to be DP for all $x_{i}\in X_{\text{priv}}$:

######  Definition 14 (Semi-Local Differential Privacy).

The $T$-round algorithm $\mathcal{A}:\mathcal{X}^{n}\to\mathcal{W}$ is
$(\varepsilon,\delta)$-semi-LDP if the full transcript of communications
$Z=\\{Z_{i,t}\\}_{i\leq n,t\leq T}$ is $(\varepsilon,\delta)$-semi-DP: i.e.
for all private $x_{i}\in\mathcal{X}_{\text{priv}}$, all pairs of
$x_{i}$-adjacent data sets $X,X^{(i)}\in\mathcal{X}^{n}$, and all
$S\subset\mathcal{Z}^{nT}$, we have

$\mathbb{P}(Z\in S|X)\leq e^{\varepsilon}\mathbb{P}(Z\in S|X^{(i)})+\delta.$

###  3.1 Optimal Semi-LDP Mean Estimation

We will characterize the minimax squared error of $\varepsilon$-semi-LDP
$d$-dimensional mean estimation:

$\mathcal{M}^{\text{loc}}_{\text{pop}}(\varepsilon,n_{\text{priv}},n,d):=\inf_{\mathbb{A}^{\text{loc}}_{\varepsilon}(\mathbb{B})}\sup_{P}\mathbb{E}_{\mathcal{A},X\sim
P^{n}}\left[\|\mathcal{A}(X)-\mathbb{E}_{x\sim P}[x]\|^{2}\right],$ (10)

where $\mathbb{A}^{\text{loc}}_{\varepsilon}(\mathbb{B})$ contains all (fully
interactive) $\varepsilon$-semi-LDP estimators
$\mathcal{A}:\mathbb{B}^{n}\to\mathbb{B}$, and
$|X_{\text{priv}}|=n_{\text{priv}}$.

######  Theorem 15.

There are absolute constants $0<c\leq C$ such that

$c\min\left\\{\frac{1}{n_{\text{pub}}},\frac{d}{n\min(\varepsilon,\varepsilon^{2})}+\frac{1}{n}\right\\}\leq\mathcal{M}^{\text{loc}}_{\text{pop}}(\epsilon,n_{\text{priv}},n,d)\leq
C\min\left\\{\frac{1}{n_{\text{pub}}},\frac{d}{n\min(\varepsilon,\varepsilon^{2})}+\frac{1}{n}\right\\}.$

Compared with LDP mean estimation, semi-LDP allows for improved error if
$n_{\text{pub}}>\frac{\min(\varepsilon,\varepsilon^{2})n}{d}$. If
$n_{\text{pub}}\geq\frac{n^{2}\varepsilon^{2}}{d^{2}}$ as well, then the semi-
LDP error rate matches the (central) semi-DP rate in Theorem 5.

######  Remark 16.

Theorem 15 still holds if we replace $\mathbb{A}_{\varepsilon}^{\text{loc}}$
in the definition of
$\mathcal{M}^{\text{loc}}_{\text{pop}}(\epsilon,n_{\text{priv}},n,d)$ by the
set of all $(\varepsilon,\delta)$-semi-LDP estimators $\mathcal{A}$ for which
either $\delta<1/2$ and $\mathcal{A}$ is “compositional” [DR19, Assumption A2]
(e.g. sequentially interactive) or $\delta<1/2^{d}$.

Our lower bound proof constructs a Bernoulli product distribution and combines
the techniques of [DR19] with an upper bound on the mutual information between
$X$ and $\mathcal{A}(X)$ for semi-LDP $\mathcal{A}$. The upper bound is the
minimum of the error of the throw-away estimator and the optimal
$\varepsilon$-LDP (hence semi-LDP) estimator PrivUnit [BDF+18]. We recall
PrivUnit in Algorithm 2 in Appendix D.

####  3.1.1 An “Even More Optimal” Semi-LDP Estimator

By applying PrivUnit only to the private samples, we can obtain an
$\varepsilon$-semi-LDP algorithm with smaller error than the asymptotically
optimal PrivUnit. Define the Semi-LDP PrivUnit estimator by

$\mathcal{A}_{\text{semi-PrivU}}(X)=\frac{1}{n}\left[\sum_{x\in
X_{\text{priv}}}\text{PrivUnit}(x)+\sum_{x\in X_{\text{pub}}}x\right].$

######  Lemma 17.

Let $C>0$ be a constant such that $\mathbb{E}_{x\sim
P}\|\text{PrivUnit}(x)-x\|^{2}=\frac{C^{2}d}{\min(\varepsilon,\varepsilon^{2})}$.
Then,

$\mathbb{E}_{\mathcal{A},X\sim P^{n}}\left[\left\|\mathcal{A}_{\text{semi-
PrivU}}(X)-\mathbb{E}_{x\sim
P}[x]\right\|^{2}\right]\leq\frac{2}{n}+2C^{2}\frac{n_{\text{priv}}}{n}\frac{d}{n\min(\varepsilon,\varepsilon^{2})}.$

Thus, the MSE of Semi-LDP PrivUnit is smaller than that of PrivUnit, roughly
by a factor of $\frac{n_{\text{priv}}}{n}$. We can say even more about the
optimality of Semi-LDP PrivUnit: it is truly optimal—i.e. it has the smallest
MSE, including constants—among a large class of unbiased semi-LDP estimators
of $\bar{X}$.

######  Proposition 18.

Let
$\mathcal{A}(X)=\frac{1}{n}\left[\mathcal{M}_{\text{priv}}(\mathcal{R}(x_{1}),\cdots,\mathcal{R}(x_{n_{\text{priv}}}))+\mathcal{M}_{\text{pub}}(X_{\text{pub}})\right]$
be a $\varepsilon$-semi-LDP algorithm, where
$\mathcal{R}:\mathbb{S}^{d-1}\to\mathcal{Z}$ is an $\varepsilon$-LDP
randomizer444Here $\mathbb{S}^{d-1}$ denotes the unit sphere. If $\|x\|\neq
1$, then PrivUnit can be combined with an LDP scaling mechanism [BDF+18]. This
scaled PrivUnit is still optimal up to constants [DR19].  and
$\mathcal{M}_{\text{priv}}:\mathcal{Z}^{n_{\text{priv}}}\to\mathbb{R}^{d}$ and
$\mathcal{M}_{\text{pub}}:\mathcal{Z}^{n_{\text{pub}}}\to\mathbb{R}^{d}$ are
aggregation protocols such that
$\mathbb{E}_{\mathcal{M}_{\text{priv}},\mathcal{R}}\left[\mathcal{M}_{\text{priv}}(\mathcal{R}(x_{1}),\cdots,\mathcal{R}(x_{n_{\text{priv}}}))\right]=\sum_{x\in
X_{\text{priv}}}x$ and
$\mathbb{E}_{\mathcal{M}_{\text{pub}}}\left[\mathcal{M}_{\text{pub}}(X_{\text{pub}})\right]=\sum_{x\in
X_{\text{pub}}}x$ for all
$X=(X_{\text{priv}},X_{\text{pub}})\in\left(\mathbb{S}^{d-1}\right)^{n}$.
Then,

$\sup_{X\in\left(\mathbb{S}^{d-1}\right)^{n}}\mathbb{E}_{\mathcal{A}_{\text{semi-
PrivU}}}\left[\left\|\mathcal{A}_{\text{semi-
PrivU}}(X)-\bar{X}\right\|^{2}\right]\leq\sup_{X\in\left(\mathbb{S}^{d-1}\right)^{n}}\mathbb{E}_{\mathcal{A}}\|\mathcal{A}(X)-\bar{X}\|^{2}.$

Proposition 18 is proved by extending the analysis of Asi et al. [AFT22] to
the semi-LDP setting.

###  3.2 Optimal Semi-LDP Stochastic Convex Optimization

We will characterize the minimax optimal excess population risk of semi-LDP
SCO

$\mathcal{R}_{\text{SCO}}^{\text{loc}}(\varepsilon,n_{\text{priv}},n,d,L,D,\mu):=\inf_{\mathcal{A}\in\mathbb{A}_{\varepsilon}^{\text{loc}}}\sup_{f\in\mathcal{F}_{\mu,L,D}}\sup_{P}\mathbb{E}_{\mathcal{A},X\sim
P^{n}}F(\mathcal{A}(X))-F^{*},$ (11)

where $\mathbb{A}^{\text{loc}}_{\varepsilon}$ denotes the set of all
algorithms $\mathcal{A}:\mathcal{X}^{n}\to\mathcal{W}$ that are
$\varepsilon$-semi-LDP for some $\mathcal{X}$ and $\mathcal{W}$ and exactly
$n_{\text{priv}}$ samples in $X$ are private. If $\mu=0$ (convex case), we
write
$\mathcal{R}_{\text{SCO}}^{\text{loc}}(\varepsilon,n_{\text{priv}},n,d,L,D):=\mathcal{R}_{\text{SCO}}^{\text{loc}}(\varepsilon,n_{\text{priv}},n,d,L,D,\mu=0)$.
We present the result for convex loss functions in Theorem 19:

######  Theorem 19.

Let
$h(\varepsilon,n_{\text{priv}},n,d,L,D):=LD\min\left\\{\frac{1}{\sqrt{n_{\text{pub}}}},\sqrt{\frac{d}{n\min(\varepsilon,\varepsilon^{2})}}+\frac{1}{\sqrt{n}}\right\\}$.
There exist absolute constants $c$ and $C$ with $0<c\leq C$, such that

$c\
h(\varepsilon,n_{\text{priv}},n,d,L,D)\leq\mathcal{R}_{\text{SCO}}^{\text{loc}}(\varepsilon,n_{\text{priv}},n,d,L,D)\leq
C\ h(\varepsilon,n_{\text{priv}},n,d,L,D).$

See Section D.2 for the strongly convex result. The lower bound follows from
Theorem 15 and a reduction from SCO to mean estimation. The first term in the
upper bound is achieved by throwing away $X_{\text{priv}}$ and running SGD on
$X_{\text{pub}}$ [NY83]. The second term in the upper bound is achieved by the
one-pass LDP-SGD of [DJW13]. Remark 16 also applies to Theorem 19.

####  3.2.1 An “Even More Optimal” Semi-LDP Algorithm for SCO

We give a semi-LDP algorithm, called Semi-LDP-SGD, with smaller excess risk
than the optimal LDP-SGD of [DJW13]. Essentially, Semi-LDP-SGD runs as
follows: In each iteration $t\in[n]$, we draw a random sample $x_{t}\in X$
without replacement. If $x_{t}\in X_{\text{priv}}$, update
$w_{t+1}=\Pi_{\mathcal{W}}\left[w_{t}-\eta\text{PrivUnit}\left(\nabla
f(w_{t},x_{t})\right)\right]$; if $x_{t}\in X_{\text{pub}}$, instead update
$w_{t+1}=\Pi_{\mathcal{W}}\left[w_{t}-\eta\nabla f(w_{t},x_{t})\right]$. See
Algorithm 3 in Section D.2.1 for pseudocode.

######  Proposition 20.

Let $f\in\mathcal{F}_{L,D}$, let $P$ be any distribution and $\varepsilon\leq
d$. Algorithm 3 is $\varepsilon$-semi-LDP. Further, there is an absolute
constant $c$ such that the output $\mathcal{A}(X)=\bar{w}_{n}$ of Algorithm 3
satisfies

$\mathbb{E}_{\mathcal{A},X\sim P^{n}}F(\bar{w}_{n})-F^{*}\leq
c\frac{LD}{\sqrt{n}}\max\left\\{\sqrt{\frac{d}{\min(\varepsilon,\varepsilon^{2})}}\sqrt{\frac{n_{\text{priv}}}{n}},\sqrt{\frac{n_{\text{pub}}}{n}}\right\\}.$

Thus, Algorithm 3 has smaller excess risk than LDP-SGD, roughly by a factor of
$\sqrt{n_{\text{priv}}/n}$.

##  4 Numerical Experiments

In this section, we empirically assess the performance of semi-DP Algorithm 1
(see Section C.3.1). We compare four different semi-DP algorithms: 1. Throw-
away (i.e. finding a minimizer of the public loss). 2\. DP-SGD [ACG+16,
DBH+22] on the entire data. 3\. PDA-MD [AGM+22, Algorithm 1], which is the
state-of-the-art semi-DP algorithm for training convex models. 4\. Our
Algorithm 1. We evaluate all algorithms with “warm start,” which means finding
a minimizer $w_{\text{pub}}$ of the public loss and initializing training at
$w_{\text{pub}}$. The hyperparameters of each algorithm were carefully tuned.

Amid et al. [AGM+22] also gave an “efficient approximation” of their PDA-MD in
[AGM+22, Equation 1], which they used for training non-convex models. While
finalizing this manuscript, we became aware that this “efficient
approximation” is equivalent to our Algorithm 1. See Appendix A for more
details. Since [AGM+22] uses PDA-MD ([AGM+22, Algorithm 1]) for their linear
regression experiments, we compare against PDA-MD for our linear regression
experiments.

The Figures below show results for $(\varepsilon,\delta=10^{-5})$-semi-DP
linear regression with synthetic Gaussian data. Our Algorithm 1 achieves the
smallest test loss across different levels of $\varepsilon$ (privacy) and
$n_{\text{pub}}$, except for $\varepsilon=0.1$. The advantage of Algorithm 1
over the baselines is largest when $n_{\text{pub}}$ is small. See Appendix E
for details on the experimental setup and further discussion of results. Also,
we performed additional numerical experiments evaluating our algorithms in
Appendix E.

Figure 2: Test loss vs. $\frac{n_{\text{pub}}}{n}$. $\varepsilon=1$.

Figure 3: Test loss vs. $\frac{n_{\text{pub}}}{n}$. $\varepsilon=2$.

Figure 4: Test loss vs. $\varepsilon$. $\frac{n_{\text{pub}}}{n}=0.04$.

Figure 5: Test loss vs. $\varepsilon$. $\frac{n_{\text{pub}}}{n}=0.03$.

##  5 Conclusion

We considered learning models with DP for a certain subset of people in the
data set. Theoretically, we characterized the optimal error bounds (up to
constants) for three fundamental learning problems: mean estimation, empirical
risk minimization (ERM), and stochastic convex optimization (SCO). In each
case, we identified the optimal algorithms and the parameter regimes in which
public data reduces the minimax optimal error of DP learning. Algorithmically,
we developed new optimal methods for semi-DP learning that have smaller error
than the asymptotically optimal algorithms. Empirically, we demonstrated that
our algorithms are effective in training semi-DP models.

## Acknowledgements

The authors would like to thank Thomas Steinke, Gautam Kamath, and Adam Smith
for very helpful pointers and explanations related to existing lower bound
proof techniques. We thank Arnold Pereira for discussions and providing
feedback at various stages of this project. We thank Hilal Asi for sharing the
code of PrivUnitG. This work was supported in part by a gift from Meta and the
USC-Meta Center for Research and Education in AI & Learning.

## References

  * [ABM19] Noga Alon, Raef Bassily, and Shay Moran.  Limits of private learning with access to public data.  Advances in Neural Information Processing Systems, 32, 2019.
  * [ACG+16] Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Oct 2016.
  * [AD20a] Hilal Asi and John C Duchi.  Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 14106–14117. Curran Associates, Inc., 2020.
  * [AD20b] Hilal Asi and John C Duchi.  Near instance-optimality in differential privacy.  arXiv preprint arXiv:2005.10630, 2020.
  * [AFT22] Hilal Asi, Vitaly Feldman, and Kunal Talwar.  Optimal algorithms for mean estimation under local differential privacy.  In International Conference on Machine Learning, pages 1046–1056. PMLR, 2022.
  * [AGM+22] Ehsan Amid, Arun Ganesh, Rajiv Mathews, Swaroop Ramaswamy, Shuang Song, Thomas Steinke, Vinith M Suriyakumar, Om Thakkar, and Abhradeep Thakurta.  Public data-assisted mirror descent for private model training.  In International Conference on Machine Learning, pages 517–535. PMLR, 2022.
  * [AKZ+17] Brendan Avent, Aleksandra Korolova, David Zeber, Torgeir Hovden, and Benjamin Livshits.  Blender: Enabling local search with a hybrid differential privacy model.  In USENIX Security Symposium, pages 747–764, 2017.
  * [App16] Apple.  Differential privacy overview, 2016.
  * [ASZ21] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang.  Differentially private assouad, fano, and le cam.  In Algorithmic Learning Theory, pages 48–78. PMLR, 2021.
  * [B+15] Sébastien Bubeck et al.  Convex optimization: Algorithms and complexity.  Foundations and Trends® in Machine Learning, 8(3-4):231–357, 2015.
  * [BCM+20] Raef Bassily, Albert Cheu, Shay Moran, Aleksandar Nikolov, Jonathan Ullman, and Steven Wu.  Private query release assisted by public data.  In International Conference on Machine Learning, pages 695–703. PMLR, 2020.
  * [BD14] Rina Foygel Barber and John C Duchi.  Privacy and statistical risk: Formalisms and minimax bounds.  arXiv preprint arXiv:1412.4451, 2014.
  * [BDF+18] Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan Rogers.  Protection against reconstruction and its applications in private federated learning.  arXiv preprint arXiv:1812.00984, 2018.
  * [BFTT19] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta.  Private stochastic convex optimization with optimal rates.  In Advances in Neural Information Processing Systems, volume 32, 2019.
  * [BKS22] Alex Bie, Gautam Kamath, and Vikrant Singhal.  Private estimation with public data.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 18653–18666. Curran Associates, Inc., 2022.
  * [BNS13] Amos Beimel, Kobbi Nissim, and Uri Stemmer.  Private learning and sanitization: Pure vs. approximate differential privacy.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings, pages 363–378. Springer, 2013.
  * [BS16] Mark Bun and Thomas Steinke.  Concentrated differential privacy: Simplifications, extensions, and lower bounds.  In Proceedings, Part I, of the 14th International Conference on Theory of Cryptography - Volume 9985, page 635–658, Berlin, Heidelberg, 2016\. Springer-Verlag.
  * [BST14] Raef Bassily, Adam Smith, and Abhradeep Thakurta.  Private empirical risk minimization: Efficient algorithms and tight error bounds.  In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 464–473. IEEE, 2014.
  * [BSV22] March Boedihardjo, Thomas Strohmer, and Roman Vershynin.  Covariance’s loss is privacy’s gain: Computationally efficient, private and accurate synthetic data.  Foundations of Computational Mathematics, pages 1–48, 2022.
  * [BTGT18] Raef Bassily, Om Thakkar, and Abhradeep Guha Thakurta.  Model-agnostic private learning.  Advances in Neural Information Processing Systems, 31, 2018.
  * [Chu05] George M Church.  The personal genome project, 2005.
  * [CMS11] Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate.  Differentially private empirical risk minimization.  Journal of Machine Learning Research, 12(3), 2011.
  * [CTW+21] Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom B Brown, Dawn Song, Ulfar Erlingsson, et al.  Extracting training data from large language models.  In USENIX Security Symposium, volume 6, 2021.
  * [DBH+22] Soham De, Leonard Berrada, Jamie Hayes, Samuel L Smith, and Borja Balle.  Unlocking high-accuracy differentially private image classification through scale.  arXiv preprint arXiv:2204.13650, 2022.
  * [DJW13] John C. Duchi, Michael I. Jordan, and Martin J. Wainwright.  Local privacy and statistical minimax rates.  In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 429–438, 2013.
  * [DJW18] John C Duchi, Michael I Jordan, and Martin J Wainwright.  Minimax optimal procedures for locally private estimation.  Journal of the American Statistical Association, 113(521):182–201, 2018.
  * [DKY17] Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin.  Collecting telemetry data privately.  Advances in Neural Information Processing Systems, 30, 2017.
  * [DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In Theory of cryptography conference, pages 265–284. Springer, 2006\.
  * [DR+14] Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014.
  * [DR19] John Duchi and Ryan Rogers.  Lower bounds for locally private estimation via communication complexity.  In Conference on Learning Theory, pages 1161–1191. PMLR, 2019.
  * [Duc21] John Duchi.  Lecture notes for statistics 311/electrical engineering 377.  URL: https://stanford. edu/class/stats311/Lectures/full_notes.pdf, 2021.
  * [FGK21] Cecilia Ferrando, Jennifer Gillenwater, and Alex Kulesza.  Combining public and private data.  arXiv preprint arXiv:2111.00115, 2021.
  * [FJR15] Matt Fredrikson, Somesh Jha, and Thomas Ristenpart.  Model inversion attacks that exploit confidence information and basic countermeasures.  In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 1322–1333, 2015.
  * [FMMO22] Alireza Fallah, Ali Makhdoumi, Azarakhsh Malekian, and Asuman Ozdaglar.  Optimal and differentially private data acquisition: Central and local mechanisms.  In Proceedings of the 23rd ACM Conference on Economics and Computation, EC ’22, page 1141, New York, NY, USA, 2022. Association for Computing Machinery.
  * [FMTT18] Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta.  Privacy amplification by iteration.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 521–532. IEEE, 2018.
  * [GAW+22] Aditya Golatkar, Alessandro Achille, Yu-Xiang Wang, Aaron Roth, Michael Kearns, and Stefano Soatto.  Mixed differential privacy in computer vision.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8376–8386, 2022.
  * [GL12] Saeed Ghadimi and Guanghui Lan.  Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework.  SIAM Journal on Optimization, 22(4):1469–1492, 2012.
  * [GTU22] Arun Ganesh, Abhradeep Thakurta, and Jalaj Upadhyay.  Langevin diffusion: An almost universal algorithm for private euclidean (convex) optimization.  arXiv preprint arXiv:2204.01585, 2022.
  * [HT10] Moritz Hardt and Kunal Talwar.  On the geometry of differential privacy.  In Proceedings of the forty-second ACM symposium on Theory of computing, pages 705–714, 2010.
  * [HVZ23] Yiyun He, Roman Vershynin, and Yizhe Zhu.  Algorithmically effective differentially private synthetic data.  arXiv preprint arXiv:2302.05552, 2023.
  * [JYC15] Zach Jorgensen, Ting Yu, and Graham Cormode.  Conservative or liberal? personalized differential privacy.  In 2015 IEEE 31St international conference on data engineering, pages 1023–1034. IEEE, 2015.
  * [KDRT21] Peter Kairouz, Monica Ribero Diaz, Keith Rush, and Abhradeep Thakurta.  (nearly) dimension independent private erm with adagrad rates via publicly estimated subspaces.  In Conference on Learning Theory, pages 2717–2746. PMLR, 2021.
  * [KH+09] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * [KLN+11] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith.  What can we learn privately?  SIAM Journal on Computing, 40(3):793–826, 2011.
  * [KLZ22] Gautam Kamath, Xingtu Liu, and Huanyu Zhang.  Improved rates for differentially private stochastic convex optimization with heavy-tailed data.  In International Conference on Machine Learning, pages 10633–10660. PMLR, 2022.
  * [KNS16] Hamed Karimi, Julie Nutini, and Mark Schmidt.  Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition.  In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 795–811. Springer, 2016.
  * [KST20] Gavin Kerrigan, Dylan Slack, and Jens Tuyls.  Differentially private language models benefit from public pre-training.  arXiv preprint arXiv:2009.05886, 2020.
  * [KY04] Bryan Klimt and Yiming Yang.  The enron corpus: A new dataset for email classification research.  In Machine Learning: ECML 2004: 15th European Conference on Machine Learning, Pisa, Italy, September 20-24, 2004. Proceedings 15, pages 217–226. Springer, 2004.
  * [LGR23a] Andrew Lowy, Ali Ghafelebashi, and Meisam Razaviyayn.  Private non-convex federated learning without a trusted server.  In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, 2023.
  * [LGR23b] Andrew Lowy, Devansh Gupta, and Meisam Razaviyayn.  Stochastic differentially private and fair learning.  In International Conference on Learning Representations, 2023.
  * [LR21] Andrew Lowy and Meisam Razaviyayn.  Output perturbation for differentially private convex optimization with improved population loss bounds, runtimes and applications to private adversarial training.  arXiv preprint:2102.04704, 2021.
  * [LR23a] Andrew Lowy and Meisam Razaviyayn.  Private federated learning without a trusted server: Optimal algorithms for convex losses.  In International Conference on Learning Representations, 2023.
  * [LR23b] Andrew Lowy and Meisam Razaviyayn.  Private stochastic optimization with large worst-case lipschitz parameter: Optimal rates for (non-smooth) convex losses and extension to non-convex losses.  In International Conference on Algorithmic Learning Theory, pages 986–1054. PMLR, 2023.
  * [LT19] Jingcheng Liu and Kunal Talwar.  Private selection from private candidates.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 298–309, 2019.
  * [LTLH21] Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto.  Large language models can be strong differentially private learners.  arXiv preprint arXiv:2110.05679, 2021.
  * [LVS+21] Terrance Liu, Giuseppe Vietri, Thomas Steinke, Jonathan Ullman, and Steven Wu.  Leveraging public data for practical private query release.  In International Conference on Machine Learning, pages 6968–6977. PMLR, 2021.
  * [MB22] Christopher Mühl and Franziska Boenisch.  Personalized pate: Differential privacy for machine learning with individual privacy guarantees.  arXiv preprint arXiv:2202.10517, 2022.
  * [McS09] Frank D McSherry.  Privacy integrated queries: an extensible platform for privacy-preserving data analysis.  In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, pages 19–30, 2009.
  * [MTKC22] Harsh Mehta, Abhradeep Thakurta, Alexey Kurakin, and Ashok Cutkosky.  Large scale transfer learning for differentially private image classification.  arXiv preprint arXiv:2205.02973, 2022.
  * [NY83] A. Nemirovski and D. Yudin.  Problem complexity and method efficiency in optimization. Chichester, 1983.
  * [PAE+17] Nicolas Papernot, Martín Abadi, Úlfar Erlingsson, Ian Goodfellow, and Kunal Talwar.  Semi-supervised knowledge transfer for deep learning from private training data.  In International Conference on Learning Representations, 2017.
  * [Pol63] Boris T Polyak.  Gradient methods for the minimisation of functionals.  USSR Computational Mathematics and Mathematical Physics, 3(4):864–878, 1963.
  * [PS22] Nicolas Papernot and Thomas Steinke.  Hyperparameter tuning with renyi differential privacy.  In International Conference on Learning Representations, 2022.
  * [PSM+18] Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Ulfar Erlingsson.  Scalable private learning with pate.  In International Conference on Learning Representations, 2018.
  * [Rén61] Alfréd Rényi.  On measures of entropy and information.  In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, volume 4, pages 547–562. University of California Press, 1961.
  * [RSS12] Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan.  Making gradient descent optimal for strongly convex stochastic optimization.  In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 1571–1578, 2012.
  * [SSSS17] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov.  Membership inference attacks against machine learning models.  In 2017 IEEE symposium on security and privacy (SP), pages 3–18. IEEE, 2017.
  * [TKP19] Reihaneh Torkzadehmahani, Peter Kairouz, and Benedict Paten.  Dp-cgan: Differentially private synthetic data and label generation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pages 0–0, 2019.
  * [TVV+17] Abhradeep Guha Thakurta, Andrew H Vyrros, Umesh S Vaishampayan, Gaurav Kapoor, Julien Freudiger, Vivek Rangarajan Sridhar, and Doug Davidson.  Learning new words, March 14 2017.  US Patent 9,594,741.
  * [UEPK14] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova.  Rappor: Randomized aggregatable privacy-preserving ordinal response.  In Proceedings of the 21st ACM Conference on Computer and Communications Security, 2014.
  * [U.S20] U.S. Census Bureau.  Differential privacy and the 2020 census, 2020.
  * [VTB+20] Giuseppe Vietri, Grace Tian, Mark Bun, Thomas Steinke, and Steven Wu.  New oracle-efficient algorithms for private synthetic data release.  In International Conference on Machine Learning, pages 9765–9774. PMLR, 2020.
  * [WZ20] Jun Wang and Zhi-Hua Zhou.  Differentially private learning with small public data.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 6219–6226, 2020.
  * [Yu97] Bin Yu.  Assouad, fano, and le cam.  Festschrift for Lucien Le Cam: research papers in probability and statistics, pages 423–435, 1997.
  * [YZCL21] Da Yu, Huishuai Zhang, Wei Chen, and Tie-Yan Liu.  Do not let privacy overbill utility: Gradient embedding perturbation for private learning.  arXiv preprint arXiv:2102.12677, 2021.
  * [ZWB20] Yingxue Zhou, Zhiwei Steven Wu, and Arindam Banerjee.  Bypassing the ambient dimension: Private sgd with gradient subspace identification.  arXiv preprint arXiv:2007.03813, 2020.

## Appendix

##  Appendix A Techniques and Related Work

###  A.1 Overview of Our Techniques and Challenges

We use several techniques to prove our lower bounds. At a high level, our
population mean estimation lower bounds rely on classical reductions from
estimation to testing and powerful information-theoretic inequalities like
LeCam’s, Fano’s, and Assouad’s methods [Duc21], along with novel semi-DP
strengthenings of these inequalities. Several of our arguments draw
inspiration from the lower bound proofs in [HT10, BST14, BD14, DR19, FMMO22].

The key tool that we develop to prove our central DP population (mean
estimation and SCO) lower bounds is a novel “Semi-DP Fano’s method” (Theorem
23). In combination with the reduction from estimation to testing, Theorem 23
generalizes DP Fano’s method [BD14, ASZ21] and strengthens classical Fano’s
method [Yu97]. Compared with DP Fano’s inequality, the main difficulty in
proving Semi-DP Fano is that the behavior of semi-DP $\mathcal{A}$ cannot be
controlled if a public sample $x$ is exchanged with public $x^{\prime}$. It
seems challenging to get a tight semi-DP bound using the approach of [ASZ21]:
the resulting bound gets arbitrarily loose as the expected Hamming distance
between $X_{\text{pub}}$ and $X_{\text{pub}}^{\prime}$ grows, and
$X_{\text{pub}}$ and $X_{\text{priv}}$ need to be drawn from the same
distribution. Instead, we build on the tools of [BD14, Proof of Theorem 3] and
account for the probability that $X_{\text{pub}}\neq X_{\text{pub}}^{\prime}$
in our proof of Theorem 23.

Our semi-DP ERM lower bound uses a packing argument [HT10, BST14]: we
construct $2^{d/2}$ “hard” data sets with well-separated sample means, and use
the group privacy property of DP [DR+14] to show that any semi-DP algorithm
must make large error on at least one of these data sets. The main challenge
is in constructing the private and public data sets so as to force semi-DP
$\mathcal{A}$ to make large error, even when $\mathcal{A}$ has access to
public data.

For our semi-LDP lower bounds, we build directly on the sophisticated
techniques of [DR19]. The main idea of our proofs is to combine Assouad’s
method [Duc21] with bounds on the mutual information between the input and
output of semi-DP algorithms.

We develop novel algorithms to obtain smaller error (including constants) than
the asymptotically optimal algorithms (throw-away and the optimal DP
algorithm). Our algorithms are simple. For central
$(\varepsilon,\delta)$-semi-DP, we propose an estimator that puts different
weights on the private and public samples and adds (Gaussian) noise that is
calibrated to the private weight. Our estimator is inspired by the linear
Laplace estimator of [FMMO22], which was used for $1$-dimensional personalized
DP estimation. We choose the weights depending on the privacy level,
dimension, and number of public samples to trade off smaller sensitivity (less
noise) with larger variance on the public data. An optimal choice of weights
minimizes the variance of our unbiased estimator, leading to smaller error
than the optimal DP estimator. Our semi-local DP algorithm simply applies the
optimal local randomizer of [BDF+18] only to the private samples, and averages
the noisy private data with the raw public data. For model training (SCO), we
develop semi-(L)DP stochastic gradient methods that use our mean estimation
algorithms to estimate the gradient of the loss function in each iteration.

###  A.2 Related Work

##### Sample complexity bounds for semi-DP learning and estimation:

The works of [BTGT18, ABM19, BCM+20] give sample complexity bounds for DP PAC
learning and query release with access to public data in terms of the VC-
dimension of the hypothesis class. For DP $d$-dimensional Gaussian mean
estimation, [BKS22] gave sample complexity bounds that do not depend on the
range parameters of the distribution if $n_{\text{pub}}\geq d+1$; this is
known to be impossible without public data.

##### DP model training (ERM and SCO) with public data:

The works of [KDRT21, ZWB20] considered DP ERM with public data and additional
assumptions on the gradients lying in a low-rank subspace. Under these
assumptions, [KDRT21, ZWB20] show that nearly dimension-independent excess
empirical risk bounds are possible. Our lower bounds show that these
additional assumptions are strictly necessary. The work of [WZ20] used public
data to adjust the parameters of DP-SGD. Empirically, pre-training on public
data sets and privately fine-tuning the model [LTLH21, KST20, MTKC22] has
shown great promise for large-scale ML.

The work of [AGM+22] developed a public data-assisted DP mirror descent (PDA-
MD) algorithm that sometimes outperforms DP-SGD empirically in training ML
models, and theoretically in terms of excess risk for linear regression. We
use the PDA-MD of [AGM+22] as a baseline in our experiments. [AGM+22] also
gave an “efficient approximation” of their PDA-MD in [AGM+22, Equation 1],
which they used for training non-convex models. While finalizing this
manuscript, we became aware that this “efficient approximation” is equivalent
to our Algorithm 1. Our Algorithm 1 was derived in a different fashion from
the algorithm in [AGM+22, Equation 1]: we derived our algorithm as an
application of our “even more optimal” mean estimator, while theirs was
derived as an approximation of their mirror descent method. Moreover, no
theoretical analysis was provided for the “efficient approximation” in
[AGM+22].

##### Personalized DP:

A related line of work is that of personalized DP (PDP) [JYC15, GAW+22, MB22,
FMMO22], a generalization of DP in which each person may have different
privacy parameters $(\varepsilon_{i},\delta_{i})$. By letting
$\varepsilon_{i}=\infty$ for some person $i$, PDP also generalizes semi-DP. We
leverage this connection to borrow techniques from the work of [FMMO22], which
considers pure ($\delta_{i}=0$) PDP. We also note that the 1-dimensional pure
(central) PDP mean estimation bound of [FMMO22] extends easily to a
1-dimensional $\varepsilon\text{-semi-DP}$ bound. However, our $d$-dimensional
semi-DP lower bounds require a different set of techniques. Additionally, the
personalized LDP bound of [FMMO22] relies on the assumption
$\varepsilon_{i}\leq 1$ and does not seem to easily extend to the
$\varepsilon$-semi-LDP setting (even if $d=1$).

##  Appendix B Notation

We recall notation from the main body and include some additional basic
definitions below for convenience.

Let $\|\cdot\|$ be the $\ell_{2}$ norm. $\mathcal{W}$ denotes a convex,
compact subset of $\mathbb{R}^{d}$ with $\ell_{2}$ diameter $D$. $\mathcal{X}$
denotes a data universe. Function $g:\mathcal{W}\to\mathbb{R}$ is
$\mu$-strongly convex if $g(\alpha w+(1-\alpha)w^{\prime})\leq\alpha
g(w)+(1-\alpha)g(w^{\prime})-\frac{\alpha(1-\alpha)\mu}{2}\|w-w^{\prime}\|^{2}$
for all $\alpha\in[0,1]$ and all $w,w^{\prime}\in\mathcal{W}$. If $\mu=0,$ we
say $g$ is convex. For convex $f(\cdot,x)$, denote any subgradient of $f(w,x)$
w.r.t. $w$ by $\nabla f(w,x)\in\partial_{w}f(w,x)$: i.e. $f(w^{\prime},x)\geq
f(w,x)+\langle\nabla f(w,x),w^{\prime}-w\rangle$ for all
$w^{\prime}\in\mathcal{W}$. Function
$f:\mathcal{W}\times\mathcal{X}\to\mathbb{R}$ is uniformly $L$-Lipschitz in
$w$ if $\sup_{x\in\mathcal{X}}|f(w,x)-f(w^{\prime},x)|\leq L\|w-w^{\prime}\|$.
Let $\mathbb{B}=\\{x\in\mathbb{R}^{d}|\|x\|\leq 1\\}$ denote the unit
$\ell_{2}$-ball. For functions $a=a(\theta)$ and $b=b(\phi)$ of input
parameter vectors $\theta$ and $\phi$, we write $a\lesssim b$ or $a=O(b)$ if
there is an absolute constant $C>0$ such that $a\leq Cb$ for all values of
input parameter vectors $\theta$ and $\phi$.

##  Appendix C Optimal Centrally Private Learning with Public Data

###  C.1 Optimal Semi-DP Mean Estimation

We begin in Section C.1.1 with empirical mean estimation. This subsection was
omitted from the main body due to space constraints. Theorem 21 will be useful
for proving our ERM bounds (Theorem 11). Then, in Section C.1.2, we turn to
population mean estimation (i.e. the proof of Theorem 5). Section C.1.3
contains proofs for Section 2.1.1.

####  C.1.1 Estimating the Empirical Mean

For a given data set $X\subset\mathbb{B}:=\\{x\in\mathbb{R}^{d}:\|x\|\leq
1\\}$, consider the problem of estimating
$\bar{X}=\frac{1}{n}\sum_{i=1}^{n}x_{i}$ subject to the constraint that the
estimator satisfies semi-DP. We will characterize the minimax squared error of
$d$-dimensional empirical mean estimation under $\varepsilon$-semi-DP:

$\mathcal{M}_{\text{emp}}(\varepsilon,n_{\text{priv}},n,d):=\inf_{\mathcal{A}\in\mathbb{A}_{\varepsilon}(\mathbb{B})}\sup_{X\in\mathbb{B}^{n},|X_{\text{priv}}|=n_{\text{priv}}}\mathbb{E}_{\mathcal{A}}\left[\|\mathcal{A}(X)-\bar{X}\|^{2}\right],$
(12)

where $\mathbb{A}_{\varepsilon}(\mathbb{B})$ denotes the set of all
$\varepsilon$-semi-DP estimators $\mathcal{A}:\mathbb{B}^{n}\to\mathbb{B}$.

######  Theorem 21.

Let $\varepsilon>0$, $n,d\in\mathbb{N}$, $n_{\text{priv}}\in[n]$. There exist
absolute constants $c$ and $C$ with $0<c\leq C$ such that

$c\min\left\\{\frac{n_{\text{priv}}}{n},\frac{d}{n\varepsilon}\right\\}^{2}\leq\mathcal{M}_{\text{emp}}(\epsilon,n_{\text{priv}},n,d)\leq
C\min\left\\{\frac{n_{\text{priv}}}{n},\frac{d}{n\varepsilon}\right\\}^{2}.$

###### Proof.

Lower bound: We use a packing argument to prove our lower bound. Variations of
such arguments have been used to prove DP lower bounds in previous works (see
e.g. [HT10, BST14]). Denote
$\mathcal{X}=\left[\frac{-1}{\sqrt{d}},\frac{1}{\sqrt{d}}\right]^{d}$. Let
$\mathcal{A}:\mathbb{B}^{n}\to\mathbb{B}$ be $\varepsilon\text{-semi-DP}$.
Choose $K=2^{d/2}$ private data points
$\\{x_{i}\\}_{i=1}^{K}\subset\mathcal{X}$ such that $\|x_{i}-x_{j}\|\geq 1/8$
for all $i\neq j$. The existence of such a set of points is well-known (see
e.g. the Gilbert-Varshamov construction). Let $n^{*}=\frac{nd}{3\varepsilon
n_{\text{priv}}}$.

Case 1: $n\leq n^{*}$ (i.e. $d\geq 3\varepsilon n_{\text{priv}}$). In this
case, we’ll show that
$\mathbb{E}\|\mathcal{A}(X)-\bar{X}\|^{2}\gtrsim\left(\frac{n_{\text{priv}}}{n}\right)^{2}$
for some $X\in\mathcal{X}^{n}$. For $i\in[K]$, let
$X_{i}=(x_{i},\cdots,x_{i},\mathbf{0}_{n-n_{\text{priv}}})$ consist of
$n_{\text{priv}}$ copies of $x_{i}$ followed by
$n-n_{\text{priv}}=n_{\text{pub}}$ copies of $0\in\mathbb{R}^{d}$. Suppose for
the sake of contradiction that for every $i\in[K]$, with probability $\geq
1/3$ we have
$\|\mathcal{A}(X)-\bar{X}\|<\frac{1}{32}\frac{n_{\text{priv}}}{n}$. That is,
we are supposing $\mathbb{P}(\mathcal{A}(X_{i})\in\mathcal{B}_{i})\geq 1/3$
for all $i$, where
$\mathcal{B}_{i}=\\{x\in\mathbb{B}:\|x-\bar{X}_{i}\|\leq\frac{1}{32}\frac{n_{\text{priv}}}{n}\\}$.
Note that the sets $\\{\mathcal{B}_{i}\\}_{i=1}^{K}$ are disjoint by
construction. Since $\mathcal{A}$ is $\varepsilon\text{-semi-DP}$, group
privacy implies that
$\mathbb{P}(\mathcal{A}(X_{1})\in\mathcal{B}_{i})\geq\frac{1}{3}e^{-\varepsilon
n_{\text{priv}}}$ for all $i\in[K]$. Thus,

$\displaystyle K\frac{1}{3}e^{-\varepsilon
n_{\text{priv}}}\leq\sum_{i=1}^{K}\mathbb{P}(\mathcal{A}(X_{1})\in\mathcal{B}_{i})\leq
1,$

where the last inequality follows from disjointness of the balls
$\mathcal{B}_{i}$. Thus, we obtain $\ln(K/3)\leq\varepsilon n_{\text{priv}}$.
Assume for now that $d\geq 8$. (A $1$-dimensional lower bound that is tight up
to constant factors can be shown easily by following the proof of the
$d$-dimensional case but choosing $K=16$ instead of $K=2^{d/2}$.) Then
$d/2\leq d-4\leq\varepsilon n_{\text{priv}}$ implies $d\leq 2\varepsilon
n_{\text{priv}}$, contradicting the assumption made in Case 1. Thus, we
conclude that there exists a data set $X_{i}$ such that with probability at
least $2/3$,
$\|\mathcal{A}(X_{i})-\bar{X}_{i}\|>\frac{1}{32}\frac{n_{\text{priv}}}{n}$.
Squaring both sides of this inequality and applying Markov’s inequality yields
the desired lower bound.

Case 2: $n>n^{*}$.

Additionally, suppose for now that $n^{*}\leq n_{\text{priv}}$. In this case,
we’ll show that
$\mathbb{E}\|\mathcal{A}(X)-\bar{X}\|^{2}\gtrsim\left(\frac{d}{n\varepsilon}\right)^{2}$
for some $X\in\mathcal{X}^{n}$. Let
$\widetilde{X}_{i}=(x_{i},\cdots,x_{i},\mathbf{0}_{n-n^{*}})$ consist of
$n^{*}$ copies of $x_{i}$ followed by $n-n^{*}$ copies of
$0\in\mathbb{R}^{d}$.555We assume without loss of generality that
$n^{*}\in\mathbb{N}$. If $n^{*}$ is not an integer, then choosing $\lceil
n^{*}\rceil$ instead yields the same bound up to constant factors. Denoting
the mean of a dataset $X$ by $q(X):=\frac{1}{n}\sum_{x\in X}x$ for
convenience, we see that
$q(\widetilde{X}_{i})=\frac{n^{*}}{n}x_{i}=\frac{d}{3n_{\text{priv}}\varepsilon}x_{i}$.
Define the algorithm $\hat{\mathcal{A}}:\mathbb{B}^{n^{*}}\to\mathbb{B}$ by
$\hat{\mathcal{A}}(X)=\frac{n}{n^{*}}\mathcal{A}(X,\mathbf{0}_{n-n^{*}})$.
Since $\mathcal{A}$ is $\varepsilon\text{-semi-DP}$, we see that
$\hat{\mathcal{A}}$ is $\varepsilon\text{-semi-DP}$ by post-processing. Also,
the domain of $\hat{\mathcal{A}}$ is $\mathcal{X}^{n^{*}}$ and $n^{*}\leq
n^{*}$, so the argument in Case 1 applies to $\hat{\mathcal{A}}$. Thus, by
applying the result in Case 1, there exists $i\in[K]$ such that with
probability at least $2/3$,
$\|\hat{\mathcal{A}}(x_{i},\cdots,x_{i})-q(x_{i},\cdots,x_{i})\|\geq\frac{1}{32}\frac{n_{\text{priv}}}{n}$.
(Here $(x_{i},\cdots,x_{i})\in\mathcal{X}^{n*}$.) But this implies
$\|\mathcal{A}(\widetilde{X}_{i})-q(\widetilde{X}_{i})\|\geq\frac{1}{32}\frac{n_{\text{priv}}}{n}\frac{n^{*}}{n}=\frac{1}{96}\frac{d}{n\varepsilon}$
with probability at least $2/3$. Again, squaring both sides and applying
Markov yields the desired lower bound.

Next, consider the complementary subcase where $n^{*}>n_{\text{priv}}$. Define
the algorithm $\hat{\mathcal{A}}:\mathbb{B}^{n^{*}}\to\mathbb{B}$ by
$\hat{\mathcal{A}}(X)=\mathcal{A}(X,\mathbf{0}_{n-n^{*}})$. Since
$\mathcal{A}$ is $\varepsilon\text{-semi-DP}$, we see that $\hat{\mathcal{A}}$
is $\varepsilon\text{-semi-DP}$ by post-processing. Also, the domain of
$\hat{\mathcal{A}}$ is $\mathcal{X}^{n^{*}}$ and $n^{*}\leq n^{*}$, so the
argument in Case 1 applies to $\hat{\mathcal{A}}$. Thus, by applying the
result in Case 1, there exists $i\in[K]$ such that with probability at least
$2/3$,
$\|\hat{\mathcal{A}}(x_{i},\cdots,x_{i})-q(x_{i},\cdots,x_{i})\|\geq\frac{1}{32}\frac{n_{\text{priv}}}{n}$.
(Here $(x_{i},\cdots,x_{i})\in\mathcal{X}^{n*}$.) But this implies that
$\|\mathcal{A}(X_{i})-\bar{X}_{i}\|\geq\frac{1}{32}\frac{n_{\text{priv}}}{n}$
with probability at least $2/3$. Again, squaring both sides and applying
Markov yields the desired lower bound. Thus, the lower bound holds in all
cases.

Upper bound: For the first term in the minimum, consider the algorithm which
throws away the private data and outputs $\mathcal{A}(X)=\frac{1}{n}\sum_{x\in
X_{\text{pub}}}x$. Clearly, $\mathcal{A}$ is semi-DP. Moreover,

$\|\mathcal{A}(X)-\bar{X}\|^{2}=\frac{1}{n^{2}}\left\|\sum_{x\in
X_{\text{priv}}}x\right\|^{2}\leq\frac{n_{\text{priv}}}{n^{2}}\sum_{x\in
X_{\text{priv}}}\|x\|^{2}\leq\left(\frac{n_{\text{priv}}}{n}\right)^{2}.$

For the second term, consider the Laplace mechanism
$\mathcal{A}(X)=\bar{X}+(L_{1},\cdots,L_{d})$, where
$L_{i}\sim\text{Lap}(2\sqrt{d}/n\varepsilon)$ are i.i.d. mean-zero Laplace
random variables. We know $\mathcal{A}$ is $\varepsilon$-DP by [DR+14], since
the $\ell_{1}$-sensitivity is $\sup_{X\sim
X^{\prime}}\|\bar{X}-\bar{X}^{\prime}\|_{1}=\frac{1}{n}\sup_{x,x^{\prime}}\|x-x^{\prime}\|_{1}\leq\frac{2\sqrt{d}}{n}$.
Hence $\mathcal{A}$ is $\varepsilon$-semi-DP. Moreover, $\mathcal{A}$ has
error

$\mathbb{E}\|\mathcal{A}(X)-\bar{X}\|^{2}=d~{}\text{Var}(\text{Lap}(2\sqrt{d}/n\varepsilon))=\frac{8d^{2}}{n^{2}\varepsilon^{2}}.$

Combining the two upper bounds completes the proof. ∎

####  C.1.2 Estimating the Population Mean

######  Theorem 22 (Re-statement of Theorem 5).

Let $\varepsilon\leq d/8$ and either
$n_{\text{pub}}\lesssim\frac{n\varepsilon}{d}$ or $d\lesssim 1$. Then, there
exist absolute constants $c$ and $C$, with $0<c\leq C$, such that

$c\min\left\\{\frac{1}{n_{\text{pub}}},\frac{d^{2}}{n^{2}\varepsilon^{2}}+\frac{1}{n}\right\\}\leq\mathcal{M}_{\text{pop}}(\epsilon,\delta=0,n_{\text{priv}},n,d)\leq
C\min\left\\{\frac{1}{n_{\text{pub}}},\frac{d^{2}}{n^{2}\varepsilon^{2}}+\frac{1}{n}\right\\}.$
(13)

The upper bound in 2 holds for any $n_{\text{pub}},d$. Further, for any
$n_{\text{pub}},d$ and any $\delta\in[0,\varepsilon]$, we have

$c\min\left\\{\frac{1}{n_{\text{pub}}},\frac{1}{n^{2}\varepsilon^{2}}+\frac{1}{n}\right\\}\leq\mathcal{M}_{\text{pop}}(\epsilon,\delta,n_{\text{priv}},n,d)\leq
C\min\left\\{\frac{1}{n_{\text{pub}}},\frac{d\ln(1/\delta)}{n^{2}\varepsilon^{2}}+\frac{1}{n}\right\\}.$
(14)

The proof of 13 will require the following intermediate result, Theorem 23,
which can be viewed both as a “semi-DP Fano’s inequality” and as an extension
of [BD14, Theorem 3] to the semi-DP setting.

######  Theorem 23.

Let $\\{P_{v}\\}_{v\in\mathcal{V}}\subset\mathcal{P}$ be a family of
distributions on $\mathcal{X}$. Let $P_{0}$ be a distribution and $p\in[0,1]$
such that $P_{\theta_{v}}:=(1-p)P_{0}+pP_{v}\in\mathcal{P}$ for all
$v\in\mathcal{V}$. Denote $\theta_{v}:=\mathbb{E}_{x\sim P_{\theta_{v}}}[x]$
and
$\rho^{*}(\mathcal{V}):=\min\left\\{\|\theta_{v}-\theta_{v^{\prime}}\|~{}|~{}v,v^{\prime}\in\mathcal{V},v\neq
v^{\prime}\right\\}$. Let $\widehat{\theta}:\mathcal{X}^{n}\to\mathcal{X}$ be
any $\varepsilon\text{-semi-DP}$ estimator. Draw
$V\sim\text{Unif}(\mathcal{V})$; then conditional on $V=v$, draw an i.i.d.
sample $X|V=v\sim P_{\theta_{v}}^{n}$ containing $n_{\text{priv}}$ private
samples and $n_{\text{pub}}$ samples. Then,

$\frac{1}{|\mathcal{V}|}\sum_{v\in\mathcal{V}}P_{\theta_{v}}\left(\left\|\widehat{\theta}(X)-\theta_{v}\right\|\geq\rho^{*}(\mathcal{V})\right)\geq\frac{(|\mathcal{V}|-1)e^{-\varepsilon\lceil
n_{\text{priv}}p\rceil}(1-p)^{n_{\text{pub}}}}{2\left(1+(|\mathcal{V}|-1)e^{-\varepsilon\lceil
n_{\text{priv}}p\rceil}\right)}$ (15)

######  Remark 24.

Note that the right-hand-side of 15 is similar to the second term on the
right-hand-side of DP Fano’s inequality [ASZ21, Equation 5], after aligning
notation. The main differences are that 15 has an extra factor of
$(1-p)^{n_{\text{pub}}}$, and $n_{\text{priv}}$ in place of $n$.

###### Proof of Theorem 23.

The key novel element of the proof is 16, which is a semi-DP variation of
[BD14, Lemma 2]: if $A$ is a measurable set and $v,v^{\prime}\in\mathcal{V}$,
then

$P_{\theta_{v}}(\widehat{\theta}(X)\in A)\geq e^{\varepsilon\lceil
n_{\text{priv}}p\rceil}\left[P_{\theta_{v^{\prime}}}(\widehat{\theta}\in
A)-1+\frac{(1-p)^{n_{\text{pub}}}}{2}\right].$ (16)

Once we prove 16, we can obtain Theorem 23 by following the proof approach of
[BD14, Theorem 3]. Let us now prove 16: We will use upper case letters to
denote random variables and lower case letters to denote the values that the
random variables take. Let $B=\\{B_{i}\\}_{i=1}^{n}$ be i.i.d.
$\text{Bernoulli}(p)$ random variables. Assume that the random variables
$X=\\{X_{i}\\}_{i=1}^{n}$ are generated in the following way: first draw
$W_{1}^{0},\ldots,W_{n}^{0}\sim P_{0}$ i.i.d. and draw
$W_{1}^{v},\ldots,W_{n}^{v}\sim P_{v}$ i.i.d. For each $i$, if $B_{i}=0$, set
$X_{i}=W_{i}^{0}$; if $B_{i}=1$, set $X_{i}=W_{i}^{v}$. Thus, conditional on
$V=v$, the random variables $X_{i}$ are each distributed according to
$P_{\theta_{v}}=(1-p)P_{0}+pP_{v}$. For fixed $v^{\prime}\in\mathcal{V}$,
generate a different sample $X^{\prime}=\\{X^{\prime}_{i}\\}_{i=1}^{n}$ by
drawing $W_{i}^{v^{\prime}}\sim P_{v^{\prime}}$ i.i.d. and setting
$X^{\prime}_{i}=W_{i}^{0}(1-B_{i})+W_{i}^{v^{\prime}}B_{i}$. Note that if
$B_{i}=0$, then $X_{i}=X^{\prime}_{i}$. Thus, the hamming distance between $X$
and $X^{\prime}$ is

$d_{\text{ham}}(X,X^{\prime})\leq B^{T}\mathbbm{1}=\sum_{i=1}^{n}B_{i}.$

Now let $Q$ denote the conditional distribution of the
$\varepsilon\text{-semi-DP}$ estimator $\widehat{\theta}$ given input data
($X$ or $X^{\prime}$). For notational convenience, assume without loss of
generality that $X=(X_{1},\ldots,X_{n_{\text{priv}}},X_{\text{pub}})$ and
$X^{\prime}=(X^{\prime}_{1},\ldots,X^{\prime}_{n_{\text{priv}}},X_{\text{pub}}^{\prime})$.
Then, for any fixed sequence
$b=(b_{1},\ldots,b_{n_{\text{priv}}},\mathbf{0}_{n_{\text{pub}}})\in\\{0,1\\}^{n_{\text{priv}}}\times\\{0\\}^{n_{\text{pub}}}$,
we have

$\displaystyle Q(\widehat{\theta}\in
A|X_{i}=W_{i}^{0}(1-b_{i})+W_{i}^{v}b_{i}~{}\forall i\in[n])\geq
e^{-\varepsilon b^{T}\mathbbm{1}}Q(\widehat{\theta}\in
A|X^{\prime}_{i}=W_{i}^{0}(1-b_{i})+W_{i}^{v^{\prime}}b_{i}~{}\forall
i\in[n])$ (17)

by group privacy, since $b_{i}=0~{}\forall i>n_{\text{priv}}$ implies
$X_{\text{pub}}=X_{\text{pub}}^{\prime}$. Thus,

$\displaystyle P_{\theta_{v}}(\widehat{\theta}\in A)$ $\displaystyle=$
$\displaystyle\sum_{b\in\\{0,1\\}^{n}}P(B=b)\int Q(\widehat{\theta}\in
A|X_{i}=w_{i}^{0}(1-b_{i})+w_{i}^{v}b_{i}~{}\forall
i\in[n])dP_{0}^{n}(w_{1:n}^{0})dP_{v}^{n}(w_{1:n}^{v})$ $\displaystyle\geq$
$\displaystyle\sum_{\begin{subarray}{c}b\in\\{0,1\\}^{n_{\text{priv}}}\times\\{0\\}^{n_{\text{pub}}},\\\
b^{T}\mathbbm{1}\leq\lceil n_{\text{priv}}p\rceil\end{subarray}}P(B=b)\int
Q(\widehat{\theta}\in A|X_{i}=w_{i}^{0}(1-b_{i})+w_{i}^{v}b_{i}~{}\forall
i\in[n])dP_{0}^{n}(w_{1:n}^{0})dP_{v}^{n}(w_{1:n}^{v})$ $\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}b\in\\{0,1\\}^{n_{\text{priv}}}\times\\{0\\}^{n_{\text{pub}}},\\\
b^{T}\mathbbm{1}\leq\lceil n_{\text{priv}}p\rceil\end{subarray}}P(B=b)\int
Q(\widehat{\theta}\in A|X_{i}=w_{i}^{0}(1-b_{i})+w_{i}^{v}b_{i}~{}\forall
i\in[n])dP_{0}^{n}(w_{1:n}^{0})dP_{v}^{n}(w_{1:n}^{v})dP_{v^{\prime}}^{n}(w_{1:n}^{v^{\prime}})$
$\displaystyle\geq$
$\displaystyle\sum_{\begin{subarray}{c}b\in\\{0,1\\}^{n_{\text{priv}}}\times\\{0\\}^{n_{\text{pub}}},\\\
b^{T}\mathbbm{1}\leq\lceil
n_{\text{priv}}p\rceil\end{subarray}}P(B=b)\int\Big{[}e^{-\varepsilon
b^{T}\mathbbm{1}}Q(\widehat{\theta}\in
A|X^{\prime}_{i}=w_{i}^{0}(1-b_{i})+w_{i}^{v^{\prime}}b_{i}~{}\forall
i\in[n])dP_{0}^{n}(w_{1:n}^{0})$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\cdots
dP_{v}^{n}(w_{1:n}^{v})dP_{v^{\prime}}^{n}(w_{1:n}^{v^{\prime}})\Big{]}$
$\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}b\in\\{0,1\\}^{n_{\text{priv}}}\times\\{0\\}^{n_{\text{pub}}},\\\
b^{T}\mathbbm{1}\leq\lceil
n_{\text{priv}}p\rceil\end{subarray}}P(B=b)e^{-\varepsilon
b^{T}\mathbbm{1}}P_{\theta_{v^{\prime}}}\left(\widehat{\theta}\in
A|B=b\right)$ $\displaystyle\geq$
$\displaystyle\sum_{\begin{subarray}{c}b\in\\{0,1\\}^{n_{\text{priv}}}\times\\{0\\}^{n_{\text{pub}}},\\\
b^{T}\mathbbm{1}\leq\lceil
n_{\text{priv}}p\rceil\end{subarray}}P(B=b)e^{-\varepsilon\lceil
n_{\text{priv}}p\rceil}P_{\theta_{v^{\prime}}}\left(\widehat{\theta}\in
A|B=b\right)$ $\displaystyle\geq$ $\displaystyle e^{-\varepsilon\lceil
n_{\text{priv}}p\rceil}P_{\theta_{v^{\prime}}}\left(\widehat{\theta}\in
A,B_{(i>n_{\text{priv}})}=\mathbf{0}_{n_{\text{pub}}},B^{T}\mathbbm{1}\leq\lceil
n_{\text{priv}}p\rceil\right)$ $\displaystyle\geq$ $\displaystyle
e^{-\varepsilon\lceil
n_{\text{priv}}p\rceil}\left[P_{\theta_{v^{\prime}}}\left(\widehat{\theta}\in
A\right)-P\left(B_{(i>n_{\text{priv}})}\neq\mathbf{0}_{n_{\text{pub}}}\bigcup
B^{T}\mathbbm{1}>\lceil n_{\text{priv}}p\rceil\right)\right],$

where the second inequality used 17 and the last inequality used a union
bound. Now, by independence of $\\{B_{i}\\}_{i=1}^{n}$, we have

$\displaystyle
P\left(B_{(i>n_{\text{priv}})}\neq\mathbf{0}_{n_{\text{pub}}}\bigcup
B^{T}\mathbbm{1}>\lceil n_{\text{priv}}p\rceil\right)$ $\displaystyle=$
$\displaystyle
1-P\left(B_{(i>n_{\text{priv}})}=\mathbf{0}_{n_{\text{pub}}}\bigcap
B^{T}\mathbbm{1}\leq\lceil n_{\text{priv}}p\rceil\right)$ $\displaystyle=$
$\displaystyle
1-P\left(B_{(i>n_{\text{priv}})}=\mathbf{0}_{n_{\text{pub}}}\right)P\left(B^{T}\mathbbm{1}\leq\lceil
n_{\text{priv}}p\rceil\right|B_{(i>n_{\text{priv}})}=\mathbf{0}_{n_{\text{pub}}})$
$\displaystyle=$ $\displaystyle
1-P\left(B_{(i>n_{\text{priv}})}=\mathbf{0}_{n_{\text{pub}}}\right)P\left(B_{(i\leq
n_{\text{priv}})}^{T}\mathbbm{1}\leq\lceil n_{\text{priv}}p\rceil\right)$
$\displaystyle=$ $\displaystyle 1-(1-p)^{n_{\text{pub}}}P\left(B_{(i\leq
n_{\text{priv}})}^{T}\mathbbm{1}\leq\lceil n_{\text{priv}}p\rceil\right)$
$\displaystyle\leq$ $\displaystyle 1-(1-p)^{n_{\text{pub}}}\cdot\frac{1}{2},$

since the median of $B_{(i\leq
n_{\text{priv}})}^{T}\mathbbm{1}\sim\text{Binomial}(n_{\text{priv}},p)$ is no
larger than $\lceil n_{\text{priv}}p\rceil$. Putting together the pieces, we
get

$\displaystyle P_{\theta_{v}}(\widehat{\theta}\in A)\geq e^{-\varepsilon\lceil
n_{\text{priv}}p\rceil}\left[P_{\theta_{v^{\prime}}}\left(\widehat{\theta}\in
A\right)-1+(1-p)^{n_{\text{pub}}}\cdot\frac{1}{2}\right],$

establishing 16.

Now, with 16 in hand, we proceed as in the proof of [BD14, Theorem 3]: Let
$\mathbb{B}_{\alpha}(\theta):=\\{\theta^{\prime}\in\mathcal{X}:\|\theta-\theta^{\prime}\|\leq\alpha\\}$.
Note that the balls $\mathbb{B}_{\rho^{*}(\mathcal{V})}(\theta_{v})$ are
disjoint for $v\in\mathcal{V}$ by definition of $\rho^{*}(\mathcal{V})$.
Denote the average probability of success for the estimator $\widehat{\theta}$
by

$P_{\text{succ}}:=\frac{1}{|\mathcal{V}|}\sum_{v\in\mathcal{V}}P_{\theta_{v}}\left(\widehat{\theta}\in\mathbb{B}_{\rho^{*}(\mathcal{V})}(\theta_{v})\right).$

Then by a union bound and disjointness of the balls
$\\{\mathbb{B}_{\rho^{*}(\mathcal{V})}(\theta_{v})\\}_{v\in\mathcal{V}}$, we
have

$P_{\text{succ}}\leq
1-\frac{1}{|\mathcal{V}|}\sum_{v\in\mathcal{V}}\sum_{v^{\prime}\in\mathcal{V},v^{\prime}\neq
v}P_{\theta_{v}}\left(\widehat{\theta}\in\mathbb{B}_{\rho^{*}(\mathcal{V})}(\theta_{v^{\prime}})\right).$

An application of 16 yields

$\displaystyle P_{\text{succ}}$ $\displaystyle\leq
1-\frac{1}{|\mathcal{V}|}\sum_{v\in\mathcal{V}}\sum_{v^{\prime}\in\mathcal{V},v^{\prime}\neq
v}\left[e^{-\varepsilon\lceil
n_{\text{priv}}p\rceil}P_{\theta_{v^{\prime}}}\left(\widehat{\theta}\in\mathbb{B}_{\rho^{*}(\mathcal{V})}(\theta_{v^{\prime}})\right)-\left(1-\frac{(1-p)^{n_{\text{pub}}}}{2}\right)\right]$
$\displaystyle\leq 1-e^{-\varepsilon\lceil
n_{\text{priv}}p\rceil}(|\mathcal{V}|-1)P_{\text{succ}}+e^{-\varepsilon\lceil
n_{\text{priv}}p\rceil}(|\mathcal{V}|-1)\left(1-\frac{(1-p)^{n_{\text{pub}}}}{2}\right).$

Re-arranging this inequality leads to

$P_{\text{succ}}\leq\frac{1+(|\mathcal{V}|-1)\left(1-\frac{(1-p)^{n_{\text{pub}}}}{2}\right)e^{-\varepsilon\lceil
n_{\text{priv}}p\rceil}}{1+(|\mathcal{V}|-1)e^{-\varepsilon\lceil
n_{\text{priv}}p\rceil}}$

and hence

$1-P_{\text{succ}}\geq\frac{(|\mathcal{V}|-1)e^{-\varepsilon\lceil
n_{\text{priv}}p\rceil}\cdot\frac{(1-p)^{n_{\text{pub}}}}{2}}{1+(|\mathcal{V}|-1)e^{-\varepsilon\lceil
n_{\text{priv}}p\rceil}}.$

This last inequality is equivalent to the inequality stated in Theorem 23. ∎

While we state Theorem 23 for mean estimation, it holds more generally for
estimating any population statistic $\theta:\mathcal{P}\to\Theta$. However,
this additional generality will not be necessary for our purposes. With
Theorem 23 in hand, we now turn to the proof of Theorem 22.

###### Proof of Theorem 22.

Lower Bounds: We begin by proving 13. First suppose
$n_{\text{pub}}\lesssim\frac{n\varepsilon}{d}$ and $d\geq 8$.

Choose a finite subset $\mathcal{V}\subset\mathbb{R}^{d}$ such that
$|\mathcal{V}|\geq 2^{d/2}$, $\|v\|=1$, and $\|v-v^{\prime}\|\geq\frac{1}{8}$
for all $v,v^{\prime}\in\mathcal{V},v\neq v^{\prime}$. The existence of such a
set of points is well-known (see e.g. the Gilbert-Varshamov construction).
Define $P_{0}$ to be the point mass distribution on $\\{X=0\\}$ and $P_{v}$ to
be point mass on $\\{X=v\\}$ for $v\in\mathcal{V}$. For $v\in\mathcal{V}$, let
$P_{\theta_{v}}:=(1-p)P_{0}+pP_{v}$ for some $p\in[0,1]$ to be specified
later. Note that if $X\sim P_{\theta_{v}}$, then $\|X\|\leq 1$ with
probability $1$. Thus, $P_{\theta_{v}}$ is a valid distribution in the class
$\mathcal{P}$ of bounded (by $1$) distributions on $\mathbb{B}$ that we are
considering. Also, note that $\theta_{v}:=\mathbb{E}_{P_{\theta_{v}}}[X]=pv$.
Further,

$\rho^{*}(\mathcal{V}):=\min\left\\{\|\theta_{v}-\theta_{v^{\prime}}\||v,v^{\prime}\in\mathcal{V},v\neq
v^{\prime}\right\\}\geq\frac{p}{8}$

by construction.

Now we use the classical reduction from estimation to testing (see [BD14] for
details) to lower bound the MSE of any $\varepsilon\text{-semi-DP}$ estimator
$\widehat{\theta}$ by

$\displaystyle\sup_{P\in\mathcal{P}}\mathbb{E}_{X\sim
P^{n},\widehat{\theta}}\left\|\widehat{\theta}(X)-\mathbb{E}_{x\sim
P}[x]\right\|^{2}$
$\displaystyle\geq\rho^{*}(\mathcal{V})^{2}\frac{1}{|\mathcal{V}|}\sum_{v\in\mathcal{V}}P_{\theta_{v}}\left(\|\widehat{\theta}(X)-\theta_{v}\|\geq\rho^{*}(\mathcal{V})\right)$
$\displaystyle\geq\left(\frac{p}{8}\right)^{2}\frac{(|\mathcal{V}|-1)e^{-\varepsilon\lceil
n_{\text{priv}}p\rceil}(1-p)^{n_{\text{pub}}}}{2\left(1+(|\mathcal{V}|-1)e^{-\varepsilon\lceil
n_{\text{priv}}p\rceil}\right)}$
$\displaystyle\geq\frac{p^{2}}{64}\frac{(2^{d/2}-1)e^{-\varepsilon\lceil
n_{\text{priv}}p\rceil}(1-p)^{n_{\text{pub}}}}{2\left(1+(2^{d/2}-1)e^{-\varepsilon\lceil
n_{\text{priv}}p\rceil}\right)}$

where we used Theorem 23 in the second inequality. Since we assumed $d\geq 8$,
we have $2^{d/2}-1\geq e^{d/4}$ and hence

$\displaystyle\sup_{P\in\mathcal{P}}\mathbb{E}_{X\sim
P^{n},\widehat{\theta}}\left\|\widehat{\theta}(X)-\mathbb{E}_{x\sim
P}[x]\right\|^{2}$
$\displaystyle\geq\frac{p^{2}}{64}\cdot\frac{(1-p)^{n_{\text{pub}}}}{2}\cdot\frac{e^{d/4-\varepsilon\lceil
n_{\text{priv}}p\rceil}}{1+e^{d/4-\varepsilon\lceil n_{\text{priv}}p\rceil}}$
$\displaystyle\geq\frac{p^{2}}{64}\cdot\frac{(1-p)^{n_{\text{pub}}}}{4}.$

for any $p\leq\frac{d}{4n\varepsilon}-\frac{1}{n}$. Now choose

$p=\min\left(\frac{d}{4n\varepsilon}-\frac{1}{n},\frac{1}{2\sqrt{n_{\text{pub}}}}\right).$

By assumption, there exists an absolute constant $k$ such that
$n_{\text{pub}}\leq k\frac{n\varepsilon}{d}$. Thus, if $n\varepsilon\geq 2$,
then

$\displaystyle(1-p)^{n_{\text{pub}}}$
$\displaystyle\geq\left(1-\frac{d}{\varepsilon n}\right)^{kn\varepsilon/d}$
$\displaystyle=\left[\left(1-\frac{d}{\varepsilon
n}\right)^{n\varepsilon/d}\right]^{k}$
$\displaystyle\geq\left[\left(1-\frac{1}{2}\right)^{2}\right]^{k}$
$\displaystyle=\frac{1}{4^{k}}.$

On the other hand, if $n\varepsilon<2$, then $n_{\text{pub}}\leq
2k\implies(1-p)^{n_{\text{pub}}}\geq\left(1-\frac{1}{2}\right)^{2k}=\frac{1}{4^{k}}$.
Also, note that $p\geq\min\left(\frac{d}{8\varepsilon
n},\frac{1}{2\sqrt{n_{\text{pub}}}}\right)$ by the assumption that $d\geq
8\varepsilon$. Therefore,

$\sup_{P\in\mathcal{P}}\mathbb{E}_{X\sim
P^{n},\widehat{\theta}}\left\|\widehat{\theta}(X)-\mathbb{E}_{x\sim
P}[x]\right\|^{2}\geq\frac{1}{256\cdot 4^{k}}\min\left(\frac{d}{8\varepsilon
n},\frac{1}{2\sqrt{n_{\text{pub}}}}\right)^{2}.$

Combining the above inequality with the non-private lower bound of
$\Omega(1/n)$ for mean estimation proves the lower bound in 13.

Now consider the alternative case in which $d\lesssim 1$ (i.e. $d\leq k$ for
some absolute constant $k\in\mathbb{N}$), but $n_{\text{pub}}\in[n]$ is
arbitrary. Then we will prove that the lower bound in 14 holds for $d=1$, for
any $\delta\in[0,\varepsilon]$ and $\varepsilon\leq 1$. By taking a $k$-fold
product distribution, this will suffice to complete the proof of the lower
bounds in 13 and 14. To that end, we will use Le Cam’s method and the
techniques in [BD14, FMMO22]. The key novel ingredient is the following
extension of [FMMO22, Lemma 3] to the $(\varepsilon,\delta)$-semi-DP setting:

######  Lemma 25.

Let $\widehat{\theta}:\mathcal{X}^{n}\to\mathcal{X}$ be
$(\varepsilon,\delta)$-semi-DP and let $P_{1},P_{2}$ be distributions on
$\mathcal{X}$ such that $P_{1}$ is absolutely continuous w.r.t. $P_{2}$.
Denote the conditional distribution of $\widehat{\theta}$ given $X$ by $Q$ and
let $Q_{j}(A)=\int Q(\widehat{\theta}\in A|x_{1:n})dP_{j}^{n}(x_{1:n})$ for
any measurable set $A$. Then

$\|Q_{1}-Q_{2}\|_{\text{TV}}\leq\min\left\\{\sqrt{\frac{n}{2}D_{\text{KL}}(P_{1},P_{2})},~{}2\|P_{1}-P_{2}\|_{\text{TV}}~{}n_{\text{priv}}(e^{\varepsilon}-1+\delta)+\sqrt{\frac{n_{\text{pub}}}{2}D_{\text{KL}}(P_{1},P_{2})}\right\\}.$

Let us defer the proof of Lemma 25 for now. We will now use Lemma 25 to prove
the lower bound in 14 for $d=1$ and $\varepsilon\leq 1$. Define distributions
$P_{1},P_{2}$ on $\\{-1,1\\}$ as follows:

$P_{1}(-1)=P_{2}(1)=\frac{1+\gamma}{2},~{}~{}P_{1}(1)=P_{2}(-1)=\frac{1-\gamma}{2}$

for some $\gamma\in[0,1/2]$ to be chosen later. Clearly
$P_{1},P_{2}\in\mathcal{P}$ (i.e. they are bounded by $1$ with probability 1).
Also, $\mathbb{E}_{P_{1}}[x]=-\gamma$ and $\mathbb{E}_{P_{2}}[x]=\gamma$, so
$\\{P_{1},P_{2}\\}$ is a $\gamma$-packing of $\\{-1,1\\}$. Thus, by Le Cam’s
method (see [BD14] for details), for any $(\varepsilon,\delta)$-semi-DP
$\widehat{\theta}$, we have

$\sup_{P\in\mathcal{P}}\mathbb{E}_{X\sim
P^{n},\widehat{\theta}}\left\|\widehat{\theta}(X)-\mathbb{E}_{x\sim
P}[x]\right\|^{2}\geq\frac{\gamma^{2}}{8}\left(1-\|Q_{1}-Q_{2}\|_{\text{TV}}\right).$

Now, applying Lemma 25 and the assumption $\delta\leq\varepsilon\leq 1$ yields

$\displaystyle\sup_{P\in\mathcal{P}}\mathbb{E}_{X\sim
P^{n},\widehat{\theta}}\left\|\widehat{\theta}(X)-\mathbb{E}_{x\sim
P}[x]\right\|^{2}$ (18) $\displaystyle\geq$
$\displaystyle\frac{\gamma^{2}}{8}\left[1-\min\left\\{\sqrt{\frac{n}{2}D_{\text{KL}}(P_{1},P_{2})},~{}6\|P_{1}-P_{2}\|_{\text{TV}}~{}n_{\text{priv}}\varepsilon+\sqrt{\frac{n_{\text{pub}}}{2}D_{\text{KL}}(P_{1},P_{2})}\right\\}\right]$
$\displaystyle\geq$
$\displaystyle\frac{\gamma^{2}}{8}\left[1-\min\left\\{\sqrt{\frac{n}{2}3\gamma^{2}(P_{1},P_{2})},~{}6\gamma
n_{\text{priv}}\varepsilon+\sqrt{\frac{n_{\text{pub}}}{2}3\gamma^{2}}\right\\}\right]$
$\displaystyle=$
$\displaystyle\frac{\gamma^{2}}{8}\left[1-\gamma\min\left\\{\sqrt{\frac{3n}{2}},~{}6n_{\text{priv}}\varepsilon+\sqrt{\frac{3n_{\text{pub}}}{2}}\right\\}\right].$
(19)

In the second inequality we used the fact that
$\|P_{1}-P_{2}\|_{\text{TV}}=\frac{1}{2}\left(\left|\frac{1+\gamma}{2}-\frac{1-\gamma}{2}\right|\cdot
2\right)=\gamma$ and $D_{\text{KL}}(P_{1},P_{2})\leq 3\gamma^{2}$ for
$\gamma\leq 1/2$.

Now we will choose $\gamma$ to (approximately) maximize the right-hand side of
18. Suppose
$\min\left\\{\sqrt{\frac{3n}{2}},6n_{\text{priv}}\varepsilon+\sqrt{\frac{3n_{\text{pub}}}{2}}\right\\}=\sqrt{\frac{3n}{2}}$.
Then choosing $\gamma=\frac{1}{3}\sqrt{\frac{2}{3n}}$ yields

$\sup_{P\in\mathcal{P}}\mathbb{E}_{X\sim
P^{n},\widehat{\theta}}\left\|\widehat{\theta}(X)-\mathbb{E}_{x\sim
P}[x]\right\|^{2}\geq\frac{k}{n}$

for some absolute constant $k>0$. Our assumption that
$\min\left\\{\sqrt{\frac{3n}{2}},6n_{\text{priv}}\varepsilon+\sqrt{\frac{3n_{\text{pub}}}{2}}\right\\}=\sqrt{\frac{3n}{2}}$
implies that there exists $k^{\prime}>0$ such that $n\leq
k^{\prime}\max\left(n_{\text{priv}}^{2}\varepsilon^{2},n_{\text{pub}}\right)$.
Thus,
$k/n\geq\frac{k}{k^{\prime}}\min\left(\frac{1}{n_{\text{priv}}^{2}\varepsilon^{2}},\frac{1}{n_{\text{pub}}}\right)$,
which gives the desired lower bound in 14.

Suppose instead that
$\min\left\\{\sqrt{\frac{3n}{2}},6n_{\text{priv}}\varepsilon+\sqrt{\frac{3n_{\text{pub}}}{2}}\right\\}=6n_{\text{priv}}\varepsilon+\sqrt{\frac{3n_{\text{pub}}}{2}}$.
Then choose
$\gamma=\frac{2}{3}\left(6n_{\text{priv}}\varepsilon+\sqrt{\frac{3n_{\text{pub}}}{2}}\right)^{-1}$.
Then, there are constants $k,c>0$ such that

$\displaystyle\sup_{P\in\mathcal{P}}\mathbb{E}_{X\sim
P^{n},\widehat{\theta}}\left\|\widehat{\theta}(X)-\mathbb{E}_{x\sim
P}[x]\right\|^{2}$
$\displaystyle\geq\frac{\gamma^{2}}{8}\left[1-\gamma\min\left\\{\sqrt{\frac{3n}{2}},6n_{\text{priv}}\varepsilon+\sqrt{\frac{3n_{\text{pub}}}{2}}\right\\}\right]$
$\displaystyle\geq\frac{k}{n_{\text{priv}}^{2}\varepsilon^{2}+n_{\text{pub}}}$
$\displaystyle\geq
c\min\left(\frac{1}{n_{\text{priv}}^{2}\varepsilon^{2}},\frac{1}{n_{\text{pub}}}\right).$

Combining the above inequality with the non-private lower bound $\Omega(1/n)$
completes the proof of the lower bound in 14.

It remains to prove Lemma 25. To that end, fix = $k\in\\{0,n_{\text{priv}}\\}$
and denote by $\widetilde{Q}$ the marginal distribution of $\widehat{\theta}$
given $X_{1},\ldots,X_{k}\sim P_{1}$ (i.i.d.) and $X_{k+1},\ldots,X_{n}\sim
P_{2}$ (i.i.d.); i.e. for measurable $A$,

$\widetilde{Q}(A):=\int Q(\widehat{\theta}\in
A|X_{1:n}=x_{1:n})dP_{1}^{k}(x_{1:k})dP_{2}^{n-k}(x_{k+1:n}).$

Note that if $k=0$, then $\widetilde{Q}=Q_{2}$. We have

$\|Q_{1}-Q_{2}\|_{\text{TV}}\leq\underbrace{\|Q_{1}-\widetilde{Q}\|_{\text{TV}}}_{ⓐ}+\underbrace{\|\widetilde{Q}-Q_{2}\|_{\text{TV}}}_{ⓑ}.$

Also,

$\displaystyle\min_{k\in\\{0,n_{\text{priv}}\\}}\sqrt{\frac{n-k}{2}D_{\text{KL}}(P_{1},P_{2})}+2\|P_{1}-P_{2}\|_{\text{TV}}\min_{k\in\\{0,n_{\text{priv}}\\}}k(e^{\varepsilon}-1+\delta)$
(20)
$\displaystyle\;\;\;\;\leq\min\left\\{\sqrt{\frac{n}{2}D_{\text{KL}}(P_{1},P_{2})},~{}2\|P_{1}-P_{2}\|_{\text{TV}}~{}n_{\text{priv}}(e^{\varepsilon}-1+\delta)+\sqrt{\frac{n_{\text{pub}}}{2}D_{\text{KL}}(P_{1},P_{2})}\right\\},$

so it suffices to upper bound the sum of the terms of ⓐ + ⓑ by the left-hand-
side of 20. First, we deal with ⓐ: for any $k$, we have

$\displaystyle\|Q_{1}-\widetilde{Q}\|_{\text{TV}}^{2}$
$\displaystyle\leq\|P_{1}^{n}-P_{1}^{k}P_{2}^{n-k}\|_{\text{TV}}^{2}$ (21)
$\displaystyle\leq\frac{1}{2}D_{\text{KL}}\left(P_{1}^{n},P_{1}^{k}P_{2}^{n-k}\right)$
(22) $\displaystyle\leq\frac{n-k}{2}D_{\text{KL}}(P_{1},P_{2}),$ (23)

by the data processing inequality for $f$-divergences, Pinsker’s inequality,
and the chain-rule for KL-divergences (see, e.g. [Duc21] for a reference on
these facts). Thus, it remains to show

$\|\widetilde{Q}-Q_{2}\|_{\text{TV}}\leq
2\|P_{1}-P_{2}\|_{\text{TV}}\min_{k\in\\{0,n_{\text{priv}}\\}}k(e^{\varepsilon}-1+\delta)$
(24)

for $k\in\\{0,n_{\text{priv}}\\}$. If $k=0$, 24 is trivial. Assume
$k=n_{\text{priv}}$. Now, for any measurable $A$, we may write

$\widetilde{Q}(A)-Q_{2}(A)=\int_{\mathbb{R}^{n_{\text{pub}}}}\Delta(x_{n_{\text{priv}}+1:n})dP_{2}^{n_{\text{pub}}}(x_{n_{\text{priv}}+1:n}),$
(25)

where

$\Delta(x_{n_{\text{priv}}+1:n}):=\int_{\mathbb{R}^{n_{\text{priv}}}}Q(\widehat{\theta}\in
A|X_{1:n}=x_{1:n})\left(dP_{1}^{n_{\text{priv}}}(x_{1:n_{\text{priv}}})-dP_{2}^{n_{\text{priv}}}(x_{1:n_{\text{priv}}})\right).$

By 25, it suffices to show that $|\Delta(x_{n_{\text{priv}}+1:n})|\leq
2\|P_{1}-P_{2}\|_{\text{TV}}~{}n_{\text{priv}}(e^{\varepsilon}-1+\delta)$ for
all $x_{n_{\text{priv}}+1:n}\in\mathcal{X}^{n_{\text{pub}}}$. To do so, let
$x_{1:n}^{i}:=(x_{1},\ldots,x_{i-1},x_{i}^{\prime},x_{i+1},\ldots,x_{n})$ for
some $i\leq n_{\text{priv}}$. Then

$|Q(\widehat{\theta}\in A|X_{1:n}=x_{1:n})-Q(\widehat{\theta}\in
A|X_{1:n}=x_{1:n}^{i})|\leq(e^{\varepsilon}-1)Q(\widehat{\theta}\in
A|X_{1:n}=x_{1:n}^{i})+\delta$ (26)

since $\widehat{\theta}$ is $(\varepsilon,\delta)$-semi-DP. Moreover, by the
proof of [FMMO22, Lemma 3], we have

$\displaystyle\Delta(x_{n_{\text{priv}}+1:n})$
$\displaystyle=\sum_{i=1}^{n_{\text{priv}}}\int_{\mathbb{R}^{n_{\text{priv}}}}\left[Q(\widehat{\theta}\in
A|X_{1:n}=x_{1:n})-Q(\widehat{\theta}\in A|X_{1:n}=x_{1:n}^{i})\right]$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\cdots
dP_{2}^{i-1}(x_{1:i-1})\left(dP_{1}(x_{i})-dP_{2}(x_{i})\right)dP_{1}^{n_{\text{priv}}-i}(x_{i+1:n_{\text{priv}}}).$

Applying the triangle inequality and 26, we get

$\displaystyle|\Delta(x_{n_{\text{priv}}+1:n})|$ $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{n_{\text{priv}}}\int_{\mathbb{R}^{n_{\text{priv}}}}\left[(e^{\varepsilon}-1)Q(\widehat{\theta}\in
A|X_{1:n}=x_{1:n}^{i})+\delta\right]dP_{2}^{i-1}(x_{1:i-1})\left|dP_{1}(x_{i})-dP_{2}(x_{i})\right|dP_{1}^{n_{\text{priv}}-i}(x_{i+1:n_{\text{priv}}})$
$\displaystyle\leq$ $\displaystyle
2\|P_{1}-P_{2}\|_{\text{TV}}~{}n_{\text{priv}}(e^{\varepsilon}-1+\delta),$

as desired. This completes the proof of Lemma 25 and hence the proof of the
lower bounds in Theorem 22.

Upper bounds: First, the throw-away estimator
$\mathcal{A}(X)=\frac{1}{n_{\text{pub}}}\sum_{x\in X_{\text{pub}}}x$ is
clearly $(0,0)$-semi-DP and has MSE

$\displaystyle\mathbb{E}_{X\sim P^{n}}\left\|\mathcal{A}(X)-\mathbb{E}_{x\sim
P}[x]\right\|^{2}$ $\displaystyle=\mathbb{E}_{X\sim
P^{n}}\left\|\frac{1}{n_{\text{pub}}}\sum_{x\in
X_{\text{pub}}}\left(x-\mathbb{E}_{x\sim P}[x]\right)\right\|^{2}$
$\displaystyle=\frac{1}{n_{\text{pub}}^{2}}\sum_{x\in
X_{\text{pub}}}\mathbb{E}_{x\sim P}\left\|x-\mathbb{E}_{x\sim
P}[x]\right\|^{2}$ $\displaystyle\leq\frac{1}{n_{\text{pub}}}.$

To get the second term in the minimum in 13, consider the Laplace mechanism
$\mathcal{A}(X)=\bar{X}+(L_{1},\ldots,L_{d})$, where
$L_{i}\sim\text{Lap}(2\sqrt{d}/n\varepsilon)$ are i.i.d. mean-zero Laplace
random variables. We know $\mathcal{A}$ is $\varepsilon$-DP by [DR+14], since
the $\ell_{1}$-sensitivity is $\sup_{X\sim
X^{\prime}}\|\bar{X}-\bar{X}^{\prime}\|_{1}=\frac{1}{n}\sup_{x,x^{\prime}}\|x-x^{\prime}\|_{1}\leq\frac{2\sqrt{d}}{n}$.
Hence $\mathcal{A}$ is $\varepsilon$-semi-DP. Moreover, $\mathcal{A}$ has MSE

$\displaystyle\mathbb{E}_{X\sim P^{n}}\left\|\mathcal{A}(X)-\mathbb{E}_{x\sim
P}[x]\right\|^{2}$ $\displaystyle\leq
2\mathbb{E}\|\mathcal{A}(X)-\bar{X}\|^{2}+2\mathbb{E}\left\|\bar{X}-\mathbb{E}_{x\sim
P}[x]\right\|^{2}$ $\displaystyle\leq
2d~{}\text{Var}(\text{Lap}(2\sqrt{d}/n\varepsilon))+\frac{2}{n}$
$\displaystyle=\frac{16d^{2}}{n^{2}\varepsilon^{2}}+\frac{2}{n}.$

This completes the proof of 13.

To get the second term in the minimum in 14, consider the Gaussian mechanism
$\mathcal{A}(X)=\bar{X}+\mathcal{N}(0,\sigma^{2}\mathbf{I}_{d})$, where
$\sigma^{2}=\frac{8\ln(2/\delta)}{\varepsilon^{2}n^{2}}$. We know
$\mathcal{A}$ is $(\varepsilon,\delta)$-DP (by e.g. [DR+14]) since the
$\ell_{2}$-sensitivity is $\sup_{X\sim
X^{\prime}}\|\bar{X}-\bar{X}^{\prime}\|_{2}\leq\frac{2}{n}$. Hence
$\mathcal{A}$ is $(\varepsilon,\delta)$-semi-DP. Moreover, the MSE of
$\mathcal{A}$ is

$\displaystyle\mathbb{E}_{X\sim P^{n}}\left\|\mathcal{A}(X)-\mathbb{E}_{x\sim
P}[x]\right\|^{2}$ $\displaystyle\leq
2\mathbb{E}\|\mathcal{A}(X)-\bar{X}\|^{2}+2\mathbb{E}\left\|\bar{X}-\mathbb{E}_{x\sim
P}[x]\right\|^{2}$ $\displaystyle\leq
2d\frac{8\ln(2/\delta)}{\varepsilon^{2}n^{2}}+\frac{2}{n}$
$\displaystyle=\frac{16d\ln(2/\delta)}{n^{2}\varepsilon^{2}}+\frac{2}{n}.$

This completes the proof of 14. ∎

####  C.1.3 An “Even More Optimal” Semi-DP Algorithm for Mean Estimation

######  Lemma 26 (Re-statement of Lemma 7).

Recall the definition of $\mathcal{P}(B,V)$ (Definition 6): $\mathcal{P}(B,V)$
denotes the collection of all distributions $P$ on $\mathbb{R}^{d}$ such that
for any $x\sim P$, we have $\|x\|\leq B$ $P$-almost surely and
$\text{Var}(x)=V^{2}$. Then, the error of the $\rho$-semi-zCDP throw-away
algorithm $\mathcal{A}(X)=\frac{1}{n_{\text{pub}}}\sum_{x\in X_{\text{pub}}}x$
is

$\sup_{P\in\mathcal{P}(B,V)}\mathbb{E}_{X\sim
P^{n}}\left[\|\mathcal{A}(X)-\mathbb{E}_{x\sim
P}[x]\|^{2}\right]=\frac{V^{2}}{n_{\text{pub}}}.$

The minimax error of the $\rho$-semi-zCDP Gaussian mechanism
$\mathcal{G}(X)=\bar{X}+\mathcal{N}\left(0,\sigma^{2}\mathbf{I}_{d}\right)$ is

$\inf_{\rho\text{-zCDP}~{}\mathcal{G}}\sup_{P\in\mathcal{P}(B,V)}\mathbb{E}_{\mathcal{G},X\sim
P^{n}}\left[\|\mathcal{G}(X)-\mathbb{E}_{x\sim
P}[x]\|^{2}\right]=\frac{2dB^{2}}{\rho n^{2}}+\frac{V^{2}}{n}.$ (27)

###### Proof.

For throw-away, the i.i.d. data assumption implies

$\mathbb{E}\|\mathcal{A}(X)-\mathbb{E}x\|^{2}=\frac{1}{n_{\text{pub}}^{2}}\sum_{x\in
X_{\text{pub}}}\mathbb{E}\|x-\mathbb{E}x\|^{2}=\frac{V^{2}}{n_{\text{pub}}}.$

The Gaussian mechanism
$\mathcal{G}^{*}(X):=\bar{X}+\mathcal{N}\left(0,\frac{2B^{2}}{\rho
n^{2}}\mathbf{I}_{d}\right)$ is $\rho$-zCDP by [BS16, Proposition 1.6] since
the $\ell_{2}$-sensitivity is bounded by $\Delta_{2}=\sup_{X\sim
X^{\prime}}\|\bar{X}-\bar{X}^{\prime}\|_{2}\leq\frac{2B}{n}$. Moreover, this
sensitivity bound is tight: consider any $P$ such that $x=(B,0_{d-1})$ and
$x^{\prime}=(-B,0_{d-1})$ are in the support of $P$. Then fix any $y$ in the
support of $P$ and consider the adjacent data sets $X=(x,y,\cdots,y)$ and
$X^{\prime}=(x^{\prime},y,\cdots,y)$. We have
$\|\bar{X}-\bar{X}^{\prime}\|_{2}=\frac{1}{n}\|x-x^{\prime}\|_{2}=\frac{2B}{n}$.
Additionally, if the variance of the additive isotropic Gaussian noise
$\sigma^{2}$ is smaller than $\frac{\Delta_{2}^{2}}{2\rho}=\frac{2B^{2}}{\rho
n^{2}}$, then the Gaussian mechanism is not $\rho$-zCDP [BS16]. Thus,
$\mathcal{G}^{*}(X)$ is the $\rho$-zCDP Gaussian mechanism with the smallest
noise variance $\sigma^{2}$. Hence the infimum in 27 is attained by
$\mathcal{G}^{*}$. Finally, for any $P\in\mathcal{P}(B,V)$, the MSE of
$\mathcal{G}^{*}$ is

$\displaystyle\mathbb{E}_{\mathcal{G},X\sim
P^{n}}\left[\|\mathcal{G}^{*}(X)-\mathbb{E}_{x\sim P}[x]\|^{2}\right]$
$\displaystyle=\mathbb{E}\|\mathcal{G}^{*}(X)-\bar{X}\|^{2}+\mathbb{E}\left\|\frac{1}{n}\sum_{i=1}^{n}x_{i}-\mathbb{E}x_{i}\right\|^{2}$
$\displaystyle=\frac{2dB^{2}}{\rho n^{2}}+\frac{V^{2}}{n}.$

∎

######  Proposition 27 (Re-statement of Proposition 8).

Recall the definition of $\mathcal{A}_{r}$ from 4. There exists $r>0$ such
that $\mathcal{A}_{r}$ is $\rho$-semi-zCDP, and

$\sup_{P\in\mathcal{P}(B,V)}\mathbb{E}_{X\sim
P^{n}}\left[\|\mathcal{A}_{r}(X)-\mathbb{E}_{x\sim
P}[x]\|^{2}\right]<\min\left(\frac{V^{2}}{n_{\text{pub}}},\frac{2dB^{2}}{\rho
n^{2}}+\frac{V^{2}}{n}\right).$ (28)

Further, if $\frac{V^{2}}{n_{\text{pub}}}\leq\frac{2dB^{2}}{\rho n^{2}}$, then
the quantitative advantage of $\mathcal{A}_{r}$ is

$\sup_{P\in\mathcal{P}(B,V)}\mathbb{E}_{X\sim
P^{n}}\left[\|\mathcal{A}_{r}(X)-\mathbb{E}_{x\sim
P}[x]\|^{2}\right]\leq\left(\frac{q^{2}+qs^{2}}{q^{2}+2qs^{2}+s^{4}}\right)\min\left(\frac{V^{2}}{n_{\text{pub}}},\frac{2dB^{2}}{\rho
n^{2}}+\frac{V^{2}}{n}\right),$ (29)

where $q=2+\frac{n_{\text{priv}}\rho V^{2}}{dB^{2}}$ and
$s=\frac{Vn_{\text{priv}}\sqrt{\rho}}{B\sqrt{dn_{\text{pub}}}}$.

###### Proof.

Privacy: Choose $\sigma_{r}^{2}=\frac{2B^{2}r^{2}}{\rho}$. Note that the
$\ell_{2}$-sensitivity of $M(X)=\sum_{x\in X_{\text{priv}}}rx+\sum_{x\in
X_{\text{pub}}}\left(\frac{1-n_{\text{priv}}r}{n_{\text{pub}}}\right)x$ is

$\displaystyle\Delta_{2}$ $\displaystyle=\sup_{X_{\text{priv}}\sim
X_{\text{priv}}^{\prime}}\left\|\sum_{x\in X_{\text{priv}}}rx+\sum_{x\in
X_{\text{pub}}}\left(\frac{1-n_{\text{priv}}r}{n_{\text{pub}}}\right)x-\sum_{x\in
X_{\text{priv}}^{\prime}}rx-\sum_{x\in
X_{\text{pub}}}\left(\frac{1-n_{\text{priv}}r}{n_{\text{pub}}}\right)x\right\|$
$\displaystyle=\sup_{x,x^{\prime}}\|rx-rx^{\prime}\|\leq 2rB.$

Recall that the Gaussian mechanism guarantees $\rho$-zCDP whenever
$\sigma^{2}\geq\frac{\Delta_{2}^{2}}{2\rho}$ [BS16, Proposition 1.6]. Thus,
$\mathcal{A}_{r}$ is $\rho$-semi-zCDP for
$\sigma_{r}^{2}\geq\frac{(2rB)^{2}}{2\rho}=\frac{2B^{2}r^{2}}{\rho}$.

Error bounds: Let $P\in\mathcal{P}(B,V)$. We have

$\displaystyle\mathbb{E}_{X\sim
P^{n}}\left[\|\mathcal{A}_{r}(X)-\mathbb{E}_{x\sim P}[x]\|^{2}\right]$
$\displaystyle=d\sigma_{r}^{2}+\mathbb{E}\left\|\sum_{x\in
X_{\text{priv}}}r(x-\mathbb{E}x)+\sum_{x\in
X_{\text{pub}}}\left(\frac{1-n_{\text{priv}}r}{n_{\text{pub}}}\right)(x-\mathbb{E}x)\right\|^{2}$
$\displaystyle=\frac{2dB^{2}r^{2}}{\rho}+\sum_{x\in
X_{\text{priv}}}r^{2}V^{2}+\sum_{x\in
X_{\text{pub}}}\left(\frac{1-n_{\text{priv}}r}{n_{\text{pub}}}\right)^{2}V^{2}$
$\displaystyle=\frac{2dB^{2}r^{2}}{\rho}+n_{\text{priv}}r^{2}V^{2}+\frac{(1-n_{\text{priv}}r)^{2}}{n_{\text{pub}}}V^{2},$
(30)

using independence of the Gaussian noise and the data, basic properties of
variance, and the fact that the data is i.i.d.

To prove 5, let

$J(r):=\frac{2dB^{2}r^{2}}{\rho}+n_{\text{priv}}r^{2}V^{2}+\frac{(1-n_{\text{priv}}r)^{2}}{n_{\text{pub}}}V^{2}.$

We compute first and second derivatives of $J$:

$\frac{d}{dr}J(r)=2r\left(\frac{2dB^{2}}{\rho}+n_{\text{priv}}V^{2}\right)-2n_{\text{priv}}\frac{V^{2}}{n_{\text{pub}}}(1-n_{\text{priv}}r)$

and

$\frac{d^{2}}{dr^{2}}J(r)=2\left(\frac{2dB^{2}}{\rho}+n_{\text{priv}}V^{2}\right)+2n_{\text{priv}}^{2}\frac{V^{2}}{n_{\text{pub}}}.$

Since $J$ is strongly convex, it has a unique minimizer $r^{*}$ which
satisfies $\frac{d}{dr}J(r^{*})=0$. We find

$r^{*}=\frac{n_{\text{priv}}V^{2}}{n_{\text{pub}}}\left(\frac{2dB^{2}}{\rho}+n_{\text{priv}}V^{2}+\frac{n_{\text{priv}}^{2}V^{2}}{n_{\text{pub}}}\right)^{-1}.$

One can verify that $r^{*}\neq 0$ and $r^{*}\neq\frac{1}{n}$, since $1\leq
n_{\text{priv}}<n$ and $\rho<\infty$ by assumption. Thus,
$J(r^{*})<\min(J(0),J(1/n))$, which yields 5 by Lemma 7.

To prove 29, we will choose a different $r$:
$r:=\frac{K\sqrt{\rho}V}{B\sqrt{dn_{\text{pub}}}}$ for $K>0$ to be determined.
Then by Section C.1.3, we have

$\displaystyle\mathbb{E}_{X\sim
P^{n}}\left[\|\mathcal{A}_{r}(X)-\mathbb{E}_{x\sim P}[x]\|^{2}\right]$
$\displaystyle=\frac{2dB^{2}r^{2}}{\rho}+n_{\text{priv}}r^{2}V^{2}+\frac{(1-n_{\text{priv}}r)^{2}}{n_{\text{pub}}}V^{2}$
$\displaystyle=K^{2}\frac{V^{2}}{n_{\text{pub}}}\left(2+\frac{n_{\text{priv}}\rho
V^{2}}{dB^{2}}\right)+\frac{V^{2}}{n_{\text{pub}}}\left(1-\frac{KV}{B}\frac{\sqrt{\rho}n_{\text{priv}}}{\sqrt{dn_{\text{pub}}}}\right)^{2}$
$\displaystyle=\frac{V^{2}}{n_{\text{pub}}}\left(qK^{2}+\left(1-\frac{KV}{B}\frac{\sqrt{\rho}n_{\text{priv}}}{\sqrt{dn_{\text{pub}}}}\right)^{2}\right),$

where $q=2+\frac{n_{\text{priv}}\rho V^{2}}{dB^{2}}$. Now, letting
$s=\frac{Vn_{\text{priv}}\sqrt{\rho}}{B\sqrt{dn_{\text{pub}}}}$ and choosing
$K=\frac{s}{q+s^{2}}$ gives

$\displaystyle\mathbb{E}_{X\sim
P^{n}}\left[\|\mathcal{A}_{r}(X)-\mathbb{E}_{x\sim P}[x]\|^{2}\right]$
$\displaystyle\leq\frac{V^{2}}{n_{\text{pub}}}\left(qK^{2}+\left(1-\frac{KV}{B}\frac{\sqrt{\rho}n_{\text{priv}}}{\sqrt{dn_{\text{pub}}}}\right)^{2}\right)$
$\displaystyle\leq\frac{V^{2}}{n_{\text{pub}}}\left(\frac{q^{2}+qs^{2}}{q^{2}+2qs^{2}+s^{4}}\right).$

Finally, the assumption $\frac{V^{2}}{n_{\text{pub}}}\leq\frac{2dB^{2}}{\rho
n^{2}}$ implies
$\frac{V^{2}}{n_{\text{pub}}}=\min\left(\frac{V^{2}}{n_{\text{pub}}},\frac{2dB^{2}}{\rho
n^{2}}+\frac{V^{2}}{n}\right)$, completing the proof.

∎

###  C.2 Optimal Semi-DP Empirical Risk Minimization

######  Theorem 28 (Complete statement of Theorem 11).

There exist absolute constants $c_{0}$ and $C_{0}$, with $0<c_{0}\leq C_{0}$,
such that

$c_{0}LD\min\left\\{\frac{n_{\text{priv}}}{n},\frac{d}{n\varepsilon}\right\\}\leq\mathcal{R}_{\text{ERM}}(\epsilon,n_{\text{priv}},n,d,L,D,\mu=0)\leq
C_{0}LD\min\left\\{\frac{n_{\text{priv}}}{n},\frac{d}{n\varepsilon}\right\\}.$

Further, if $\mu>0$, then there exist absolute constants $0<c_{1}\leq C_{1}$
such that

$c_{1}LD\min\left\\{\frac{n_{\text{priv}}}{n},\frac{d}{n\varepsilon}\right\\}^{2}\leq\mathcal{R}_{\text{ERM}}(\epsilon,n_{\text{priv}},n,d,L,D,\mu)\leq
C_{1}\frac{L^{2}}{\mu}\min\left\\{\frac{n_{\text{priv}}}{n},\frac{d\sqrt{\ln(n)}}{n\varepsilon}\right\\}^{2}.$

###### Proof.

Lower Bounds: Given a lower bound for empirical mean estimation, Bassily et
al. [BST14] show how to prove excess risk lower bounds for convex and strongly
convex ERM by reducing these problems to mean estimation. Thus, our lower
bounds follow immediately by combining the lower bound in Theorem 21 with the
reduction in [BST14]. Roughly, the reduction works as follows:

In the strongly convex case, we simply take $f(w,x)=\frac{1}{2}\|w-x\|^{2}$ on
$\mathcal{W}=\mathcal{X}=\mathbb{B}$; $f(\cdot,x)$ is $1$-uniformly-Lipschitz
and $1$-strongly convex. Moreover, for any $\varepsilon\text{-semi-DP}$
$\mathcal{A}$ with output $w_{\text{priv}}=\mathcal{A}(X)$, we have

$\mathbb{E}\widehat{F}_{X}(w_{\text{priv}})-\widehat{F}_{X}^{*}=\frac{1}{2}\mathbb{E}\|\mathcal{A}(X)-\bar{X}\|^{2}.$

Applying Theorem 21 and then scaling $f\to\frac{L}{D}f$ and $\mathcal{W}\to
D\mathcal{W}$ and $\mathcal{X}\to D\mathcal{X}$ completes the proof.

For the convex case, we take $f(w,x)=-\langle w,x\rangle$ on
$\mathcal{W}=\mathcal{X}=\mathbb{B}$. Then
$w^{*}:=\operatorname*{argmin}_{w\in\mathcal{W}}\widehat{F}_{X}(w)=\frac{\bar{X}}{\|\bar{X}\|}$
and

$\widehat{F}_{X}(w_{\text{priv}})-\widehat{F}_{X}^{*}\geq\frac{1}{2}\|\bar{X}\|\|w_{\text{priv}}-w^{*}\|^{2}.$

Also, the proof of Theorem 21 shows that there exists a dataset
$X\in\mathcal{X}^{n}$ such that
$\|\bar{X}\|=M/n:=\min\left(\frac{n_{\text{priv}}}{n},\frac{d}{3n\varepsilon}\right)$
and
$\mathbb{E}\|\mathcal{A}^{\prime}(X)-\bar{X}\|^{2}\gtrsim\min\left(\frac{n_{\text{priv}}}{n},\frac{d}{n\varepsilon}\right)^{2}$
for any $\varepsilon\text{-semi-DP}$ $\mathcal{A}^{\prime}$. Note that
$\mathcal{A}^{\prime}:=\frac{M}{n}w_{\text{priv}}$ is $\varepsilon\text{-semi-
DP}$ by post-processing. Thus,

$\displaystyle\mathbb{E}\widehat{F}_{X}(w_{\text{priv}})-\widehat{F}_{X}^{*}$
$\displaystyle\geq\frac{M}{2n}\mathbb{E}\left[\|w_{\text{priv}}-w^{*}\|^{2}\right]$
$\displaystyle=\frac{M}{2n}\left(\frac{n}{M}\right)^{2}\mathbb{E}\left[\|\mathcal{A}^{\prime}(X)-\bar{X}\|^{2}\right]$
$\displaystyle\gtrsim\frac{n}{M}\min\left(\frac{n_{\text{priv}}}{n},\frac{d}{n\varepsilon}\right)^{2}$
$\displaystyle\gtrsim\min\left(\frac{n_{\text{priv}}}{n},\frac{d}{n\varepsilon}\right).$

A standard scaling argument (see [BST14] for details) completes the proof.

Upper Bounds: The second terms in each minimum follows by running the
$\varepsilon$-DP algorithms in [BST14]: these achieve the desired excess
empirical risk bounds and are automatically $\varepsilon\text{-semi-DP}$.

We now prove the first term in each respective minimum. Denote
$\widehat{F}_{pub}(w)=\frac{1}{n}\sum_{x\in X_{pub}}f(w,x)$ and
$\widehat{F}_{priv}(w)=\frac{1}{n}\sum_{x\in X_{priv}}f(w,x)$, so that
$\widehat{F}_{X}=\widehat{F}_{pub}+\widehat{F}_{priv}$. The algorithm we will
use simply returns any minimizer of the public empirical loss:
$\mathcal{A}(X)=w^{*}_{pub}\in\operatorname*{argmin}_{w\in\mathcal{W}}\widehat{F}_{pub}(w)$.
(It will be easy to see from the proof that any approximate minimizer would
also suffice.) $\mathcal{A}$ is clearly $\varepsilon\text{-semi-DP}$. Next, we
bound the excess risk of $\mathcal{A}$. Let
$w^{*}\in\operatorname*{argmin}_{w\in\mathcal{W}}\widehat{F}_{X}(w)$.

Convex Upper Bound: We have

$\displaystyle\widehat{F}_{X}(w^{*}_{pub})-\widehat{F}_{X}(w^{*})$
$\displaystyle=\widehat{F}_{X}(w^{*}_{pub})-\widehat{F}_{pub}(w^{*}_{pub})+\widehat{F}_{pub}(w^{*}_{pub})-\widehat{F}_{pub}(w^{*})$
$\displaystyle\;\;\;+\widehat{F}_{pub}(w^{*})-\widehat{F}_{X}(w^{*})$
$\displaystyle\leq\frac{1}{n}\sum_{x\in
X_{priv}}f(w^{*}_{pub},x)+0-\frac{1}{n}\sum_{x\in X_{priv}}f(w^{*},x)$
$\displaystyle\leq\frac{1}{n}\sum_{x\in X_{priv}}L\|w^{*}_{pub}-w^{*}\|$
$\displaystyle=L\|w^{*}_{pub}-w^{*}\|\frac{n_{\text{priv}}}{n}$
$\displaystyle\leq LD\frac{n_{\text{priv}}}{n}.$

Strongly Convex Upper Bound: By the above,
$\widehat{F}_{X}(w^{*}_{pub})-\widehat{F}_{X}(w^{*})\leq
L\|w^{*}_{pub}-w^{*}\|\frac{n_{\text{priv}}}{n}$. Now we will use strong
convexity to bound $\|w^{*}_{pub}-w^{*}\|$. To do so, we use the following
lemma, versions of which have appeared, e.g. in [LR21, CMS11]:

######  Lemma 29 ([LR21]).

Let $H(w),h(w)$ be convex functions on some convex closed set
$\mathcal{W}\subseteq\mathbb{R}^{d}$ and suppose that $H(w)$ is
$\mu_{H}$-strongly convex. Assume further that $h$ is $L_{h}$-Lipschitz.
Define $w_{1}=\arg\min_{w\in\mathcal{W}}H(w)$ and
$w_{2}=\arg\min_{w\in\mathcal{W}}[H(w)+h(w)]$. Then
$\|w_{1}-w_{2}\|\leq\frac{L_{h}}{\mu_{H}}.$

We apply the lemma with $h(w)=\widehat{F}_{priv}(w)$ and
$H(w)=\widehat{F}_{pub}(w)$. Then the conditions of the lemma are satisfied
with $L_{h}\leq\frac{n_{\text{priv}}}{n}L$ and
$\mu_{H}=\frac{n_{\text{pub}}}{n}\mu$. Thus,

$\|w^{*}-w^{*}_{pub}\|\leq\frac{L_{h}}{\mu_{H}}\leq\frac{L}{\mu}\frac{n_{\text{priv}}}{n_{\text{pub}}}$

This leads to

$\widehat{F}_{X}(w^{*}_{pub})-\widehat{F}_{X}(w^{*})\leq\frac{L^{2}}{\mu}\frac{n_{\text{priv}}^{2}}{nn_{\text{pub}}}.$

Combining the two strongly convex upper bounds with the upper bound
$LD\frac{n_{\text{priv}}}{n}\leq\frac{L^{2}}{\mu}\frac{n_{\text{priv}}}{n}$
(which holds for any convex function), we have an algorithm $\mathcal{A}$ with
the following excess risk:

$\mathbb{E}\widehat{F}_{X}(\mathcal{A}(X))-\widehat{F}_{X}^{*}\lesssim\frac{L^{2}}{\mu}\min\left(\frac{n_{\text{priv}}}{n},\frac{n_{\text{priv}}^{2}}{nn_{\text{pub}}},\frac{d^{2}\ln(n)}{n^{2}\varepsilon^{2}}\right).$
(31)

We will show that 31 is equal to the strongly convex upper bound stated in
Theorem 11 up to constant factors. First, suppose $n_{\text{pub}}\gtrsim n$:
i.e. there is a constant $k>0$ such that $n_{\text{pub}}\geq kn$ for all
$n\geq 1$. Then, clearly 31 and the strongly convex upper bound stated in
Theorem 11 are both equal to
$\Theta\left(\frac{L^{2}}{\mu}\min\left(\frac{n_{\text{priv}}^{2}}{n^{2}},\left(\frac{d}{n\varepsilon}\right)^{2}\ln(n)\right)\right)$.

Next, suppose $n_{\text{pub}}\ll n$: i.e. for any $k>0$, there exists $n\geq
1$ such that $n_{\text{pub}}<kn$. Then we claim that
$\min\left\\{\frac{n_{\text{priv}}}{n},\frac{d\sqrt{\ln(n)}}{n\varepsilon}\right\\}^{2}\gtrsim\min\left\\{1,\frac{d\sqrt{\ln(n)}}{n\varepsilon}\right\\}^{2}$.
If we prove this claim, then we are done. There are two subcases to consider:
A) $n_{\text{priv}}/n<\frac{d\sqrt{\ln(n)}}{\varepsilon n}$; and B)
$n_{\text{priv}}/n\geq\frac{d\sqrt{\ln(n)}}{\varepsilon n}$. In subcase B),
the claim is immediate. Consider subcase A): if $n_{\text{priv}}\gtrsim n$,
then we’re done. If not, then we have $n_{\text{priv}}\ll n$ and
$n_{\text{pub}}\ll n$, so $n=n_{\text{priv}}+n_{\text{pub}}\ll n$, a
contradiction. This completes the proof. ∎

######  Remark 30 (Details of Remark 12).

The same minimax risk bound 8 holds up to a logarithmic factor if we replace
$\mathcal{F}_{\mu=0,L,D}$ by the larger class of all Lipschitz non-convex (or
convex) loss functions in the definition 7: First, the lower bound in Theorem
11 clearly still holds for non-convex loss functions. For the upper bound, the
$\varepsilon$-DP (hence semi-DP) exponential mechanism achieves error
$O(LD\frac{d}{n\varepsilon}\ln(n))$ [BST14, GTU22]. Further, the proof of
Theorem 11 reveals that convexity is not necessary for the throw-away
algorithm to achieve error $O(LDn_{\text{priv}}/n)$. However, the optimal
algorithms are inefficient for non-convex loss functions: to the best of our
knowledge, all existing polynomial time implementations of the exponential
mechanism require convexity for their runtime guarantees to hold. Further,
computing
$\approx\operatorname*{argmin}_{w\in\mathcal{W}}\widehat{F}_{\text{pub}}(w)$
in the implementation of throw-away may not be tractable in polynomial time
for non-convex $\widehat{F}_{\text{pub}}$.

###  C.3 Optimal Semi-DP Stochastic Convex Optimization

######  Theorem 31 (Complete Version of Theorem 13).

Suppose $\varepsilon\leq d/8$, and either
$n_{\text{pub}}\lesssim\frac{n\varepsilon}{d}$ or $d\lesssim 1$. If $\mu=0$
(convex case), then there exist absolute constants $0<c_{0}\leq C_{0}$ such
that

$c_{0}LD\min\left\\{\frac{1}{\sqrt{n_{\text{pub}}}},\frac{d}{n\varepsilon}+\frac{1}{\sqrt{n}}\right\\}\leq\mathcal{R}_{\text{SCO}}(\epsilon,\delta=0,n_{\text{priv}},n,d,L,D,\mu=0)\leq
C_{0}LD\min\left\\{\frac{1}{\sqrt{n_{\text{pub}}}},\frac{d}{n\varepsilon}+\frac{1}{\sqrt{n}}\right\\}.$

If $\mu>0$, there are constants $0<c_{1}\leq C_{1}$ such that

$c_{1}LD\min\left\\{\frac{1}{n_{\text{pub}}},\frac{d^{2}}{n^{2}\varepsilon^{2}}+\frac{1}{n}\right\\}\leq\mathcal{R}_{\text{SCO}}(\epsilon,\delta=0,n_{\text{priv}},n,d,L,D,\mu)\leq
C_{1}\frac{L^{2}}{\mu}\min\left\\{\frac{1}{n_{\text{pub}}},\frac{d^{2}\ln(n)}{n^{2}\varepsilon^{2}}+\frac{1}{n}\right\\}.$

The above upper bounds hold for any $n_{\text{pub}},d$.

Further, for any $n_{\text{pub}},d$, and any $0\leq\delta\leq\varepsilon\leq
1$, the following holds for some absolute constants $0<c^{\prime}_{0}\leq
C^{\prime}_{0}$ and $0<c^{\prime}_{1}\leq C^{\prime}_{1}$:

$c^{\prime}_{0}LD\min\left\\{\frac{1}{\sqrt{n_{\text{pub}}}},\frac{1}{n\varepsilon}+\frac{1}{\sqrt{n}}\right\\}\leq\mathcal{R}_{\text{SCO}}(\epsilon,\delta,n_{\text{priv}},n,d,L,D,\mu=0)\leq
C^{\prime}_{0}LD\min\left\\{\frac{1}{\sqrt{n_{\text{pub}}}},\frac{\sqrt{d\ln(1/\delta)}}{n\varepsilon}+\frac{1}{\sqrt{n}}\right\\},$

and

$c^{\prime}_{1}LD\min\left\\{\frac{1}{n_{\text{pub}}},\frac{1}{n^{2}\varepsilon^{2}}+\frac{1}{n}\right\\}\leq\mathcal{R}_{\text{SCO}}(\epsilon,\delta,n_{\text{priv}},n,d,L,D,\mu)\leq
C^{\prime}_{1}\frac{L^{2}}{\mu}\min\left\\{\frac{1}{n_{\text{pub}}},\frac{d\ln(1/\delta)}{n^{2}\varepsilon^{2}}+\frac{1}{n}\right\\}.$

###### Proof.

Lower bounds: Let $\mathcal{A}$ be $(\varepsilon,\delta)$-semi-DP (for
$\delta\geq 0$) and denote $w_{\text{priv}}=\mathcal{A}(X)$.

Strongly convex lower bounds: We begin with the strongly convex lower bounds,
which can be proved straightforwardly by reducing strongly convex SCO to mean
estimation and applying Theorem 5. In a bit more detail, let
$f:\mathcal{W}\times\mathcal{X}\to\mathbb{R}$ be given by

$f(w,x)=\frac{L}{2D}\|w-x\|^{2},$

where $\mathcal{W}=\mathcal{X}=D\mathbb{B}$. Note that $f$ is $L$-uniformly
Lipschitz and $\frac{L}{D}$-strongly convex in $w$ for all $x$. Further,
$w^{*}:=\operatorname*{argmin}_{w\in\mathcal{W}}\left\\{F(w)=\mathbb{E}_{x\sim
P}\left[f(w,x)\right]\right\\}=\mathbb{E}_{x\sim P}[x]$. By a direct
calculation (see e.g. [KLZ22, Lemma 6.2]), we have

$\mathbb{E}F(w_{\text{priv}})-F(w^{*})=\frac{L}{2D}\mathbb{E}\|w_{\text{priv}}-w^{*}\|^{2}.$
(32)

We can lower bound
$\mathbb{E}\|w_{\text{priv}}-w^{*}\|^{2}=\mathbb{E}\|\mathcal{A}(X)-\mathbb{E}_{x\sim
P}[x]\|^{2}$ via Theorem 5 (and its proof, to account for the re-scaling).
Specifically, if $\delta=0$, $\varepsilon\leq\max(1,d/8)$, and either $d=O(1)$
or $n_{\text{pub}}=O(n\varepsilon/d)$, then Theorem 5 and its proof imply

$\mathbb{E}\|w_{\text{priv}}-w^{*}\|^{2}\geq
cD^{2}\min\left(\frac{1}{n_{\text{pub}}},\frac{d^{2}}{n^{2}\varepsilon^{2}}+\frac{1}{n}\right).$

Combining this with 32 leads to the desired excess risk lower bound for
$\delta=0$. On the other hand, if $\delta\in(0,\varepsilon]$, then

$\mathbb{E}\|w_{\text{priv}}-w^{*}\|^{2}\geq
cD^{2}\min\left\\{\frac{1}{n_{\text{pub}}},\frac{1}{n^{2}\varepsilon^{2}}+\frac{1}{n}\right\\},$

by Theorem 5. Again, applying 32 yields the desired excess risk lower bound
for $\delta>0$.

Convex lower bounds: We will begin by proving the lower bounds for the case in
which $L=D=1$, and then scale our construction to get the lower bounds for
arbitrary $L,D$.

First consider the case in which $\delta=0$, $\varepsilon\leq d/8$, and either
$n_{\text{pub}}\lesssim n\varepsilon/d$ or $d\lesssim 1$. Let
$\mathcal{X}=\\{0\\}\bigcup\left\\{\pm\frac{1}{\sqrt{d}}\right\\}^{d}\subset\mathbb{R}^{d}$
and $\mathcal{W}=\mathbb{B}$. Define

$f(w,x)=-\langle w,x\rangle,$

which is convex and $1$-uniformly-Lipschitz in $w$ on $\mathcal{X}$. Choose
$\mathcal{V}$ to be a finite subset of $\mathbb{R}^{d}$ such that
$|\mathcal{V}|\geq 2^{d/2}$, $\|v\|=1$ for all $v$, and $\|v-v^{\prime}\|\geq
1/8$ for all $v\neq v^{\prime}$ (see e.g. the Gilbert-Varshamov construction).
Following the proof of Theorem 5, we define $P_{\theta_{v}}=(1-p)P_{0}+pP_{v}$
for all $v\in\mathcal{V}$, where $p\in[0,1]$ will be chosen later, $P_{0}$ is
point mass on $\\{X=0\\}$ and $P_{v}$ is point mass on $\\{X=v\\}$. Denote the
mean $\theta_{v}:=\mathbb{E}_{x\sim P_{\theta_{v}}}[x]=pv$. Note that
$\|\theta_{v}\|=p$ for all $v$. Let $F_{v}(w)=\mathbb{E}_{x\sim
P_{\theta_{v}}}[f(w,x)]$ and
$w^{*}_{v}\in\operatorname*{argmin}_{w\in\mathcal{W}}F_{v}(w)=\frac{\theta_{v}}{\|\theta_{v}\|}=v$.
A direct calculation (see e.g. [KLZ22, Equation 14]) shows

$\mathbb{E}F_{v}(w)-F_{v}^{*}\geq\frac{1}{2}\mathbb{E}\left[\|\theta_{v}\|\|w-w^{*}_{v}\|^{2}\right]$
(33)

for any $w\in\mathcal{W},v\in\mathcal{V}$. Also,

$\displaystyle\rho^{*}(\mathcal{V})=\min\left\\{\|w^{*}_{v}-w^{*}_{v^{\prime}}\|:v,v^{\prime}\in\mathcal{V},v\neq
v^{\prime}\right\\}=\min\left\\{\|v-v^{\prime}\|:v,v^{\prime}\in\mathcal{V},v\neq
v^{\prime}\right\\}\geq\frac{1}{8}.$

Thus, by combining 33 with the reduction from estimation to testing and
Theorem 23 (see the proof of Theorem 5 for details), we have

$\displaystyle\sup_{v\in\mathcal{V}}\mathbb{E}\left[F_{v}(w_{\text{priv}})-F_{v}^{*}\right]$
$\displaystyle\geq\frac{1}{2}\sup_{v\in\mathcal{V}}\mathbb{E}\left[\|\theta_{v}\|\|w_{\text{priv}}-w^{*}_{v}\|^{2}\right]$
$\displaystyle=\frac{p}{2}\sup_{v\in\mathcal{V}}\mathbb{E}\left[\|w_{\text{priv}}-w^{*}_{v}\|^{2}\right]$
$\displaystyle\geq\frac{p}{2}\rho^{*}(\mathcal{V})^{2}\frac{1}{|\mathcal{V}|}\sum_{v\in\mathcal{V}}P_{\theta_{v}}\left(\|\widehat{\theta}(X)-\theta_{v}\|\geq\rho^{*}(\mathcal{V})\right)$
$\displaystyle\geq\frac{p}{128}\frac{(|\mathcal{V}|-1)e^{-\varepsilon\lceil
n_{\text{priv}}p\rceil}(1-p)^{n_{\text{pub}}}}{2\left(1+(|\mathcal{V}|-1)e^{-\varepsilon\lceil
n_{\text{priv}}p\rceil}\right)}$
$\displaystyle\geq\frac{p}{128}\frac{(2^{d/2}-1)e^{-\varepsilon\lceil
n_{\text{priv}}p\rceil}(1-p)^{n_{\text{pub}}}}{2\left(1+(2^{d/2}-1)e^{-\varepsilon\lceil
n_{\text{priv}}p\rceil}\right)}$
$\displaystyle\geq\frac{p}{512}(1-p)^{n_{\text{pub}}}\min\left\\{1,\frac{2^{d/2}-1}{e^{\varepsilon(n_{\text{priv}}p+1)}}\right\\}.$

Now, assume $d\geq 4$ so that $2^{d/2}-1\geq e^{d/4}$. Then, as detailed in
the proof of Theorem 5, choosing

$p=\min\left(\frac{d}{4n\varepsilon}-\frac{1}{n},\frac{1}{2\sqrt{n_{\text{pub}}}}\right)$

and assuming $n_{\text{pub}}\leq kn\varepsilon/d$ for some absolute constant
$k$ implies

$\sup_{v\in\mathcal{V}}\mathbb{E}\left[F_{v}(w_{\text{priv}})-F_{v}^{*}\right]\geq
c\min\left(\frac{1}{\sqrt{n_{\text{pub}}}},\frac{d}{n\varepsilon}\right)$

for some absolute constant $c>0$. Combining this with the non-private SCO
lower bound [NY83] yields

$\sup_{P}\mathbb{E}\left[F(w_{\text{priv}})-F^{*}\right]\geq
c^{\prime}\min\left(\frac{1}{\sqrt{n_{\text{pub}}}},\frac{d}{n\varepsilon}+\frac{1}{\sqrt{n}}\right),$

where $F(w):=\mathbb{E}_{x\sim P}[f(w,x)]$.

Suppose instead that $0\leq\delta\leq\varepsilon$ and $d\lesssim 1$ (i.e.
$d\leq k$ for some absolute constant $k\geq 1$), but $n_{\text{pub}}\in[n]$ is
arbitrary. We will prove the lower bound for $d=1$: by taking the $k$-fold
product distribution, this is sufficient to complete the proof of the unscaled
lower bounds. Define distributions $P_{1},P_{2}$ on $\\{-1,1\\}$ as follows:

$P_{1}(-1)=P_{2}(1)=\frac{1+\gamma}{2},~{}~{}P_{1}(1)=P_{2}(-1)=\frac{1-\gamma}{2}$

for some $\gamma\in(0,1/2]$ to be chosen later. Note
$\theta_{1}:=\mathbb{E}_{P_{1}}[x]=-\gamma$ and
$\theta_{2}:=\mathbb{E}_{P_{2}}[x]=\gamma$, so $|\theta_{j}|=\gamma$ for
$j=1,~{}2$. Let $F_{j}(w)=\mathbb{E}_{x\sim P_{j}}f(w,x)$ and
$w^{*}_{j}=\frac{\theta_{j}}{|\theta_{j}|}=\frac{\theta_{j}}{\gamma}\in\operatorname*{argmin}_{w\in\mathcal{W}}F_{j}(w)$.
Then by 33, we have

$\displaystyle\max_{j\in\\{1,2\\}}\mathbb{E}\left[F_{j}(w_{\text{priv}})-F_{j}^{*}\right]$
$\displaystyle\geq\frac{1}{2}\max_{j\in\\{1,2\\}}\mathbb{E}\left[|\theta_{j}||w_{\text{priv}}-w^{*}_{j}|^{2}\right]$
$\displaystyle=\frac{\gamma}{2}\max_{j\in\\{1,2\\}}\mathbb{E}\left[|w_{\text{priv}}-w^{*}_{j}|^{2}\right]$
$\displaystyle=\frac{1}{2\gamma}\max_{j\in\\{1,2\\}}\mathbb{E}\left[|w_{\text{priv}}^{\prime}-\theta_{j}|^{2}\right],$

where $w_{\text{priv}}^{\prime}:=\gamma w_{\text{priv}}$ is semi-DP iff
$w_{\text{priv}}$ is semi-DP (by post-processing). Thus, by applying Le Cam’s
method and Lemma 25 (see the proof of Theorem 5 for details), we get

$\displaystyle\max_{j\in\\{1,2\\}}\mathbb{E}\left[F_{j}(w_{\text{priv}})-F_{j}^{*}\right]$
$\displaystyle\geq\frac{1}{2\gamma}\left[\frac{\gamma^{2}}{8}\left(1-\gamma\min\left(\sqrt{\frac{3n}{2}},6n_{\text{priv}}\varepsilon+\sqrt{\frac{3n_{\text{pub}}}{2}}\right)\right)\right].$

Now we will choose $\gamma$ to (approximately) maximize the right-hand side of
the above inequality. If
$\min\left\\{\sqrt{\frac{3n}{2}},6n_{\text{priv}}\varepsilon+\sqrt{\frac{3n_{\text{pub}}}{2}}\right\\}=\sqrt{\frac{3n}{2}}$,
then choosing $\gamma=\frac{1}{3}\sqrt{\frac{2}{3n}}$ yields

$\max_{j\in\\{1,2\\}}\mathbb{E}\left[F_{j}(w_{\text{priv}})-F_{j}^{*}\right]\geq\frac{k}{\sqrt{n}}$

for some absolute constant $k>0$. If instead
$\min\left\\{\sqrt{\frac{3n}{2}},6n_{\text{priv}}\varepsilon+\sqrt{\frac{3n_{\text{pub}}}{2}}\right\\}=6n_{\text{priv}}\varepsilon+\sqrt{\frac{3n_{\text{pub}}}{2}}$,
then we choose
$\gamma=\frac{2}{3}\left(6n_{\text{priv}}\varepsilon+\sqrt{\frac{3n_{\text{pub}}}{2}}\right)^{-1}$.
This choice implies

$\max_{j\in\\{1,2\\}}\mathbb{E}\left[F_{j}(w_{\text{priv}})-F_{j}^{*}\right]\geq
k^{\prime}\min\left(\frac{1}{n_{\text{priv}}\varepsilon},\frac{1}{\sqrt{n_{\text{pub}}}}\right)$

for some absolute constant $k^{\prime}>0$. Combining the pieces above with the
non-private SCO lower bound [NY83] yields

$\sup_{P}\mathbb{E}\left[F(w_{\text{priv}})-F^{*}\right]\geq
c\min\left(\frac{1}{\sqrt{n_{\text{pub}}}},\frac{1}{n\varepsilon}+\frac{1}{\sqrt{n}}\right),$

where $F(w):=\mathbb{E}_{x\sim P}[f(w,x)]$.

It remains to properly scale the above constructions. For each respective
construction $(\mathcal{W},\mathcal{X},P)$, we let
$\widetilde{W}=D\mathcal{W}$, $\widetilde{X}=L\mathcal{X}$, and
$\widetilde{x}\sim\widetilde{P}\iff\widetilde{x}=Lx$ for $x\sim P$. Define
$\widetilde{f}:\widetilde{\mathcal{W}}\times\widetilde{\mathcal{X}}\to\mathbb{R}$
by
$\widetilde{f}(\widetilde{w},\widetilde{x}):=f(\widetilde{w},\widetilde{x})=-\langle\widetilde{w},\widetilde{x}\rangle$.
Then $\widetilde{f}(\cdot,\widetilde{x})$ is $L$-Lipschitz and convex.
Moreover, if $F(w)=\mathbb{E}_{x\sim P}[f(w,x)]$,
$\widetilde{F}(\widetilde{w})=\mathbb{E}_{\widetilde{x}\sim\widetilde{P}}[f(\widetilde{w},\widetilde{x})]$,
$\widetilde{w}=Dw$, and
$\widetilde{\mu}=\mathbb{E}_{\widetilde{x}\sim\widetilde{P}}[\widetilde{x}]$,
then
$Dw^{*}\in\operatorname*{argmin}_{\widetilde{w}\in\widetilde{\mathcal{W}}}\widetilde{F}(\widetilde{w})$
and

$\displaystyle\widetilde{F}(\widetilde{w})-\widetilde{F}^{*}$
$\displaystyle=-\langle\widetilde{w},\widetilde{\mu}\rangle+\langle\widetilde{w},\widetilde{\mu}\rangle$
$\displaystyle=D\langle\widetilde{\mu},w^{*}-w\rangle$
$\displaystyle=LD\langle\mu,w^{*}-w\rangle$
$\displaystyle=LD\left[F(w)-F^{*}\right].$

This shows that excess risk scales by $LD$, completing the lower bound proofs.

Upper bounds: