Convex upper bounds: Consider the $0$-semi-DP throw-away algorithm that
discards $X_{\text{priv}}$ and runs $n_{\text{priv}}$ steps of one-pass SGD
(stochastic approximation) using $X_{\text{pub}}$. This algorithm has excess
risk $O\left(LD/\sqrt{n_{\text{pub}}}\right)$ [NY83]. To obtain the second
term in the convex $\varepsilon$-semi-DP upper bound, use the $\varepsilon$-DP
(hence semi-DP) regularized exponential mechanism of [GTU22]. The second term
in the convex $(\varepsilon,\delta)$-semi-DP upper bound can be attained, e.g.
by $(\varepsilon,\delta)$-DP-SGD [BFTT19].

Strongly convex upper bounds: Consider the $0$-semi-DP throw-away algorithm
that discards $X_{\text{priv}}$ and runs $n_{\text{priv}}$ steps of one-pass
SGD (stochastic approximation) using $X_{\text{pub}}$. This algorithm has
excess risk $O\left(\frac{L^{2}}{\mu n_{\text{pub}}}\right)$ [NY83]. To obtain
the second term in the storngly convex $\varepsilon$-semi-DP upper bound, one
can use, e.g. the $\varepsilon$-DP (hence semi-DP) iterated exponential
mechanism of [GTU22]. The second term in the convex
$(\varepsilon,\delta)$-semi-DP upper bound can be attained, e.g. by
$(\varepsilon,\delta)$-DP-SGD [LR23a]. ∎

####  C.3.1 Semi-DP SCO with an “Even More Optimal” Gradient Estimator

In this section, we provide an $(\varepsilon,\delta)$-semi-DP algorithm for
SCO. Our Algorithm 1 is a noisy stochastic gradient method that uses the “even
more optimal” Weighted-Gaussian estimator 4 to estimate $\nabla F(w_{t})$ in
iteration $t$.666In Algorithm 1, we re-parameterize by setting
$r=\frac{\alpha}{K_{\text{priv}}}$ for $\alpha\in[0,1]$. In Algorithm 1,
$\text{clip}_{C}(x):=\operatorname*{argmin}_{y\in\mathbb{R}^{d},\|y\|\leq
C}\|x-y\|$ is the Euclidean projection onto the centered $\ell_{2}$-ball of
radius $C$.

Algorithm 1 Semi-DP-SGD via Weighted-Gaussian Gradient Estimators

1: Input: $T\in\mathbb{N},$ clip threshold $C>0$, stepsizes
$\\{\eta_{t}\\}_{t\in[T]}$, batch sizes $K_{\text{priv}}\in[n_{\text{priv}}]$,
$K_{\text{pub}}\in[n_{\text{pub}}]$, weight parameter $\alpha\in[0,1]$, noise
parameter $\sigma^{2}>0$.

2: Initialize $w_{0}\in\mathcal{W}$.

3: for $t\in\\{0,1,\cdots,T-1\\}$ do

4: Draw random batch of $K_{\text{priv}}$ private samples $B_{t}^{priv}$
uniformly from $X_{\text{priv}}$.

5: Draw random batch of $K_{\text{pub}}$ public samples $B_{t}^{pub}$
uniformly from $X_{\text{pub}}$.

6: Draw privacy noise
$v_{t}\sim\mathcal{N}\left(0,\sigma^{2}\mathbf{I}_{d}\right)$.

7: $\widetilde{g}_{t}\leftarrow\alpha\left[\frac{1}{K_{\text{priv}}}\sum_{x\in
B_{t}^{priv}}\text{clip}_{C}(\nabla
f(w_{t},x))+v_{t}\right]+\frac{1-\alpha}{K_{\text{pub}}}\sum_{x\in
B_{t}^{pub}}\nabla f(w_{t},x)$.

8: Update $w_{t+1}:=\Pi_{\mathcal{W}}[w_{t}-\eta_{t}\widetilde{g}_{t}]$.

9: end for

10: Output: $w_{T}$ or a weighted average of the iterates
$\\{w_{t}\\}_{t\in[T]}$.

######  Proposition 32.

  1. 1.

Suppose we sample with replacement in line 4 of Algorithm 1. Then, there exist
constants $c_{1},c_{2}$ such that for any
$\varepsilon<c_{1}\left(\frac{K_{\text{priv}}}{n_{\text{priv}}}\right)^{2}T$,
Algorithm 1 is $(\varepsilon,\delta)$-semi-DP for any $\delta>0$ if we choose
$\sigma^{2}\geq
c_{2}\frac{C^{2}\ln(1/\delta)T}{\varepsilon^{2}n_{\text{priv}}^{2}}$.

  2. 2.

Suppose we sample without replacement in line 4 and choose
$T\leq\frac{n}{K_{\text{priv}}}$. Then Algorithm 1 is $\rho$-semi-zCDP if
$\sigma^{2}\geq\frac{2C^{2}}{\rho K_{\text{priv}}^{2}}$.

###### Proof.

Note that the $\ell_{2}$-sensitivity of the private stochastic gradient query
is

$\Delta=\sup_{X_{\text{priv}}\sim
X_{\text{priv}}^{\prime}}\left\|\frac{\alpha}{K_{\text{priv}}}\sum_{x\in
B_{t}^{priv}}\text{clip}_{C}(\nabla
f(w_{t},x))-\frac{\alpha}{K_{\text{priv}}}\sum_{x^{\prime}\in
B_{t}^{priv}}\text{clip}_{C}(\nabla
f(w_{t},x^{\prime}))\right\|_{2}\leq\frac{2\alpha C}{K_{\text{priv}}}.$

1\. Consider sampling with replacement. Then we are randomly subsampling from
the private data uniformly with sampling ratio $K_{\text{priv}}/a$. Thus, the
theorem follows from [ACG+16, Theorem 1].

2\. Consider sampling without replacement. Then by the $\rho$-zCDP guarantee
of the Gaussian mechanism [BS16, Proposition 1.6] and the sensitivity bound
above, $\widetilde{g}_{t}$ is $\rho$-semi-zCDP for every $t$. Moreover, since
we are sampling without replacement, the privacy of every $x\in
X_{\text{priv}}$ is only affected by $\widetilde{g}_{t}$ for a single
$t\in[T]$. Thus, semi-zCDP of Algorithm 1 follows by parallel composition
[McS09]. ∎

By Proposition 8, there exists a choice of $\alpha$ such that the variance of
our unbiased estimator in line 7 is always less than the variance of both the
throw-away gradient estimator $\frac{1}{K_{\text{pub}}}\sum_{x}\nabla
f(w_{t},x)$ and the DP-SGD estimator
$\frac{1}{K_{\text{priv}}+K_{\text{pub}}}\sum_{x\in B_{t}}\nabla
f(w_{t},x)+u_{t}$, where $u_{t}$ is appropriately scaled (to ensure DP)
Gaussian noise. Consequently, if we choose $T$ and
$K=K_{\text{priv}}+K_{\text{pub}}$ such that $n=TK$ and sample without
replacement (i.e. one pass), then  Algorithm 1 always has smaller excess risk
than both the throw-away SCO algorithm and one-pass DP-SGD. Moreover, if the
loss function has Lipschitz continuous gradient, then one can combine the
stochastic gradient estimator of line 7 with acceleration [GL12] to obtain a
linear-time semi-DP algorithm that always outperforms the accelerated DP
algorithm of [LR23a]. The algorithm of [LR23a] has the smallest excess risk
among linear-time (one-pass) DP algorithms whose privacy analysis does not
require convexity. Thus, our algorithm can be used for deep learning. In our
numerical experiments, we implement the with-replacement sampling version of
Algorithm 1.

We also note that near-optimal excess risk bounds for non-convex loss
functions that satisfy the (Proximal) PL inequality [Pol63, KNS16] can be
derived by combining a proximal variation of Algorithm 1 with the techniques
of [LGR23a]. Further, if $f(\cdot,x)$ is not uniformly Lipschitz, but has
stochastic gradients with bounded $k$-th order moment for some $k\geq 2$, then
excess risk bounds can still be derived for Algorithm 1 via techniques in
[LR23b]. Our algorithm can also be extended to a variation of noisy stochastic
gradient descent ascent, which could be used, e.g. for fair semi-DP model
training [LGR23b]. We leave it as future work to explore these and other
potential applications of our gradient estimator in efficiently training
private ML models with public data.

Finally, we note that Algorithm 1 is essentially equivalent to the “efficient
approximation” of public-data-assisted DP-mirror-descent (PDA-MD) proposed in
[AGM+22, Equation 1]. The work [AGM+22] uses this “efficient approximation” to
train semi-DP non-convex models, but does not analyze the algorithm
theoretically. We became aware of this overlap while we were finalizing our
manuscript. Interestingly, our work and [AGM+22] derive Algorithm 1 in two
orthogonal ways: we derive the algorithm as an application of our “even more
optimal” mean estimator, while [AGM+22] derives it as an approximation of
their PDA-MD algorithm.

##  Appendix D Optimal Locally Private Learning with Public Data

Notation and Setup: Following [DR19], we permit algorithms to be fully
interactive. That is, algorithms may adaptively query the same individual $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}$. Person $i$’s message
$Z_{i,t}\in\mathcal{Z}$ in round $t$ may depend on all previous communications
$B^{(t)}:=(Z_{\leq n,t},B^{(t-1)})$ and on $i$’s own data: $Z_{i,t}\sim
Q_{i,t}(\cdot|x_{i},Z_{<i,t},B^{(t-1)})$. If $i$’s data is private, then
$Z_{i,t}$ is a randomized view of $x_{i}$ distributed (conditionally)
according to $Q_{i,t}$. If $i$’s data is public, then $Z_{i,t}$ may be
deterministic. Full interactivity is the most general notion of interactivity.
If $T=1$, then we say the algorithm is sequentially interactive. If, in
addition, each person’s message $Z_{i,1}$ depends only on $x_{i}$ and not on
$x_{j\neq i}$, then we say the algorithm is non-interactive. Semi-LDP
(Definition 14) essentially requires that the messages
$\\{Z_{i,t}\\}_{t\in[T]}$ be DP for all private $x_{i}\in X_{\text{priv}}$.

###  D.1 Optimal Semi-LDP Mean Estimation

######  Theorem 33 (Re-statement of Theorem 15).

There exist absolute constants $c$ and $C$, with $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\\}.$

###### Proof.

Lower bound: We will actually prove a more general lower bound than the one in
Theorem 15; namely, we will show a lower bound on the minimax $\ell_{1}$-error
for estimation of distributions on $\mathcal{X}_{r}=\\{\pm r\\}^{d}$ for
$r>0$. To that end, let $\gamma\in(0,1)$ and

$P_{1}:=\begin{cases}r&\mbox{with probability}\frac{1+\gamma}{2}\\\
-r&\mbox{with probability}\frac{1-\gamma}{2}\end{cases}$

and

$P_{-1}:=\begin{cases}r&\mbox{with probability}\frac{1-\gamma}{2}\\\
-r&\mbox{with probability}\frac{1+\gamma}{2}\end{cases}.$

We define our hard distribution on $\mathcal{X}_{r}$ by first drawing
$V\sim\text{Unif}(\\{\pm 1\\}^{d})$ and then—conditional on $V=v$—drawing
$X_{i,j}\sim P_{v}=\Pi_{j=1}^{d}P_{v_{j}}$ for $i\in[n],j\in[d]$, where
$P_{v}$ denotes the product distribution. We have Markov chains $V_{j}\to
X_{i,j}\to Z$ for all $j\in[d],i\in[n]$, where $Z$ is the semi-LDP transcript.
Note that
$\left|\ln\left(\frac{dP_{1}}{dP_{-1}}\right)\right|\leq\ln\left(\frac{1+\gamma}{1-\gamma}\right)\triangleq
b$ and $e^{b}\leq 3$ for any $\gamma\in(0,1/2]$. Now we will use the following
lemma from Duchi & Rogers (2019):

######  Lemma 34.

[DR19, Lemma 24] Let $V\to X\to Z$ be a Markov chain, where $X\sim P_{v}$
conditional on $V=v$. If
$\left|\ln\frac{dP_{v}}{dP_{v^{\prime}}}\right|\leq\alpha$ for all
$v,v^{\prime}$, then

$I(V;Z)\leq 2(e^{\alpha}-1)^{2}I(X;Z).$

Thus, for $V_{j}\sim\text{Unif}(\\{\pm 1\\})$, Lemma 34 implies
$I(V_{j};Z)\leq\frac{8\gamma^{2}}{(1-\gamma)^{2}}I(X_{i,j};Z)$. Hence the
strong data processing constant [DR19, Definition 9] is
$\beta:=\beta(P_{1},P_{-1})\leq\frac{8\gamma^{2}}{(1-\gamma)^{2}}$.

Now, $\theta_{v_{j}}:=\mathbb{E}_{x\sim P_{v_{j}}}[x]=\gamma rv_{j}$ for any
$v_{j}\in\\{\pm 1\\}$. Moreover, letting
$\theta_{v}=(\theta_{v_{1}},\cdots,\theta_{v_{d}})$ for $v\in\\{\pm 1\\}^{d}$
and $\theta\in\mathbb{R}^{d},$ we have

$\|\theta-\theta_{v}\|_{1}=\sum_{j=1}^{d}|\theta_{j}-r\gamma
v_{j}|=r\gamma\sum_{j=1}^{d}\left|\frac{\theta_{j}}{r\gamma}-v_{j}\right|\geq
r\gamma\sum_{j=1}^{d}\mathbbm{1}_{\\{\text{sign}(\theta_{j})\neq v_{j}\\}}.$

Thus, $\\{\pm 1\\}^{d}$ induces an $r\gamma$-Hamming separation, so Assouad’s
lemma [DJW18, Lemma 1] yields

$\inf_{\mathcal{A}\in\mathbb{A}_{\varepsilon}^{\text{loc}}}\sup_{P\in\mathcal{P}_{r}}\mathbb{E}\|\mathcal{A}(X)-\theta(P)\|_{1}\geq
r\gamma\sum_{j=1}^{d}\inf_{\hat{V}}\mathbb{P}(\hat{V}_{j}(Z)\neq V_{j}),$

where $Z$ is the communication transcript of $\mathcal{A}$, the infimum on the
RHS is over all estimators of $V$, $\theta(P)=\mathbb{E}_{x\sim P}[x]$, and
$\mathcal{P}_{r}$ is the set of distributions on $\mathcal{X}_{r}$

Assume WLOG that the private samples are the first $n_{\text{priv}}$ samples
of $X$: $X_{\text{priv}}=(x_{1},\cdots,x_{n_{\text{priv}}})$. To lower bound
$\sum_{j=1}^{d}\inf_{\hat{V}}\mathbb{P}(\hat{V}_{j}(Z)\neq V_{j})$, we use a
slight extension of [DR19, Theorem 10]:

$\sum_{j=1}^{d}\inf_{\hat{V}}\mathbb{P}(\hat{V}_{j}(Z)\neq
V_{j})\geq\frac{d}{2}\left[1-\sqrt{\frac{7(e^{b}+1)}{d}\beta\left(I(X_{\text{priv}};Z|V)+I(X_{\text{pub}};Z|V)\right)}\right].$

This follows since $V\to X_{\text{priv}}\to Z$ and $V\to X_{\text{pub}}\to Z$
are both Markov chains and the other assumptions in [DR19, Theorem 10] all
hold. Combining this bound with Assouad’s lemma [DJW18, Lemma 1] and
substituting the definitions of $b$ and $\beta$ given above gives us

$\inf_{\mathcal{A}\in\mathbb{A}_{\varepsilon}^{\text{loc}}}\sup_{P\in\mathcal{P}_{r}}\mathbb{E}\|\mathcal{A}(X)-\theta(P)\|_{1}\geq\frac{r\gamma
d}{2}\left[1-\sqrt{\frac{896}{d}\gamma^{2}\left(I(X_{\text{priv}};Z|V)+I(X_{\text{pub}};Z|V)\right)}\right]$

for any $\gamma\in(0,1/2]$. It remains to upper bound the conditional mutual
information $I(X_{\text{priv}};Z|V)$ and $I(X_{\text{pub}};Z|V)$.

Now for any $\varepsilon$-semi-LDP algorithm with communication transcript
$Z$, we have $I(X_{\text{priv}};Z|V)\leq
n_{\text{priv}}\min(\varepsilon,4\varepsilon^{2})$, by an easy extension of
[DR19, Lemma 12]. Also, $I(X_{\text{pub}};Z|V)\leq
H(X_{\text{pub}}|V)\leq\log(|\mathcal{X}^{n_{\text{pub}}}|)=dn_{\text{pub}}$,
where $H(\cdot|\cdot)$ denotes conditional entropy. Thus,

$\inf_{\mathcal{A}\in\mathbb{A}_{\varepsilon}^{\text{loc}}}\sup_{P\in\mathcal{P}_{r}}\mathbb{E}\|\mathcal{A}(X)-\theta(P)\|_{1}\geq\frac{r\gamma
d}{2}\left[1-\sqrt{\frac{4000}{d}\gamma^{2}\left(n_{\text{priv}}\min(\varepsilon,\varepsilon^{2})+dn_{\text{pub}}\right)}\right].$

Choosing
$\gamma^{2}=c\min\left(\frac{1}{n_{\text{pub}}},\frac{d}{n_{\text{priv}}\min(\varepsilon,\varepsilon^{2})}\right)$
for some small constant $c>0$ yields

$\inf_{\mathcal{A}\in\mathbb{A}_{\varepsilon}^{\text{loc}}}\sup_{P\in\mathcal{P}_{r}}\mathbb{E}\|\mathcal{A}(X)-\theta(P)\|_{1}\gtrsim
rd\min\left(\frac{1}{\sqrt{n_{\text{pub}}}},\sqrt{\frac{d}{n_{\text{priv}}\min(\varepsilon,\varepsilon^{2})}}\right),$

whence

$\inf_{\mathcal{A}\in\mathbb{A}_{\varepsilon}^{\text{loc}}}\sup_{P\in\mathcal{P}_{r}}\mathbb{E}\|\mathcal{A}(X)-\theta(P)\|_{2}\gtrsim
r\sqrt{d}\min\left(\frac{1}{\sqrt{n_{\text{pub}}}},\sqrt{\frac{d}{n_{\text{priv}}\min(\varepsilon,\varepsilon^{2})}}\right).$

By applying the non-private mean estimation lower bound, we get

$\inf_{\mathcal{A}\in\mathbb{A}_{\varepsilon}^{\text{loc}}}\sup_{P\in\mathcal{P}_{r}}\mathbb{E}\|\mathcal{A}(X)-\theta(P)\|_{2}\gtrsim
r\sqrt{d}\min\left(\frac{1}{\sqrt{n_{\text{pub}}}},\sqrt{\frac{d}{n_{\text{priv}}\min(\varepsilon,\varepsilon^{2})}}+\frac{1}{\sqrt{n}}\right).$

Choosing $r=1/\sqrt{d}$ ensures that
$\mathcal{P}_{r}\subset\mathcal{P}(\mathbb{B})$ and yields

$\inf_{\mathcal{A}\in\mathbb{A}_{\varepsilon}^{\text{loc}}}\sup_{P\in\mathcal{P}(\mathbb{B})}\mathbb{E}\|\mathcal{A}(X)-\theta(P)\|_{2}\gtrsim\min\left(\frac{1}{\sqrt{n_{\text{pub}}}},\sqrt{\frac{d}{n\min(\varepsilon,\varepsilon^{2})}}+\frac{1}{\sqrt{n}}\right).$

Applying Jensen’s inequality completes the proof of the lower bound in Theorem
15.

Upper bound: The first term in the minimum can be realized by the algorithm
that throws away the private data and returns
$\mathcal{A}(X)=\frac{1}{n_{\text{pub}}}\sum_{x\in X_{\text{pub}}}x$, which is
$0$-semi-LDP. Also,

$\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}\leq\frac{1}{n_{\text{pub}}}.$

The second term in the upper bound can be realized by an appropriate choice of
$(p,\gamma)$ in PrivUnit [BDF+18] (Algorithm 2). The work [BDF+18] shows that
PrivUnit is $\varepsilon$-LDP (hence $\varepsilon$-semi-LDP) and has worst-
case MSE that is upper bounded by
$O\left(\frac{d}{n\min(\varepsilon,\varepsilon^{2})}+\frac{1}{n}\right)$. ∎

Algorithm 2 $\text{PrivUnit}(p,\gamma)$[BDF+18]

1: Input: $v\in\mathbb{S}^{d-1}$, $\gamma\in[0,1]$, $p\in[0,1]$.
$B(\cdot;\cdot,\cdot)$ below is the incomplete Beta function
$B(x;a,b)=\int_{0}^{x}t^{a-1}(1-t)^{b-1}\textrm{d}t$ and $B(a,b)=B(1;a,b)$.

2: Draw $z\sim\text{Bernoulli}(p)$

3: if $z=1$ then

4: Draw $V\sim\text{Unif}\\{u\in\mathbb{S}^{d-1}:\langle
u,v\rangle\geq\gamma\\}$

5: else

6: Draw $V\sim\text{Unif}\\{u\in\mathbb{S}^{d-1}:\langle u,v\rangle<\gamma\\}$

7: end if

8: Set $\alpha=\frac{d-1}{2}$ and $\tau=\frac{1+\gamma}{2}$

9: Calculate normalization constant
$m=\frac{(1-\gamma^{2})^{\alpha}}{2^{d-2}(d-1)}\left(\frac{p}{B(\alpha,\alpha)-B(\tau;\alpha,\alpha)}+\frac{1-p}{B(\tau;\alpha,\alpha)}\right)$

10: Return $\frac{1}{m}\cdot V$

####  D.1.1 An “Even More Optimal” Semi-LDP Estimator

######  Lemma 35 (Re-statement of Lemma 17).

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

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

###### Proof.

We have

$\displaystyle\mathbb{E}_{\mathcal{A},X\sim P^{n}}\|\mathcal{A}_{\text{semi-
PrivU}}(X)-\mathbb{E}x\|^{2}$ $\displaystyle\leq
2\mathbb{E}\|\bar{X}-\mathbb{E}x\|^{2}+2\mathbb{E}\|\mathcal{A}_{\text{semi-
PrivU}}(X)-\bar{X}\|^{2}$
$\displaystyle\leq\frac{2}{n}+\frac{2}{n^{2}}\sum_{x\in
X_{\text{priv}}}\mathbb{E}\|\text{PrivUnit}(x)-x\|^{2}$
$\displaystyle\leq\frac{2}{n}+2C^{2}\frac{n_{\text{priv}}}{n}\frac{d}{n\min(\varepsilon,\varepsilon^{2})},$

∎

######  Proposition 36 (Re-statement of 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
randomizer 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}}}\|\mathcal{A}_{\text{semi-
PrivU}}(X)-\bar{X}\|^{2}\leq\sup_{X\in\left(\mathbb{S}^{d-1}\right)^{n}}\mathbb{E}_{\mathcal{A}}\|\mathcal{A}(X)-\bar{X}\|^{2}.$

###### Proof.

First, Asi et al. [AFT22, Proposition 3.4] showed that PrivUnit (with a proper
choice of $(p,\gamma)$) has the smallest worst-case variance among all
unbiased $\varepsilon$-LDP randomizers:

$\sup_{x\in\mathbb{S}^{d-1}}\mathbb{E}\|\mathcal{R}(x)-x\|^{2}\geq\sup_{x\in\mathbb{S}^{d-1}}\mathbb{E}\|\text{PrivUnit}(x)-x\|^{2}$
(34)

for all $\varepsilon$-LDP randomizers $\mathcal{R}$ such that
$\mathbb{E}[\mathcal{R}(x)]=x$ for all $x\in\mathbb{S}^{d-1}$.

Now, let $\mathcal{R}$ be a $\varepsilon$-LDP randomizer and
$\mathcal{M}_{\text{priv}}$ and $\mathcal{M}_{\text{pub}}$ be aggregation
protocols such that the assumptions in Proposition 18 are satisfied. We claim
that there exists an unbiased $\varepsilon$-LDP randomizer
$\mathcal{R}^{\prime}:\mathbb{S}^{d-1}\to\mathcal{Z}$ such that

$\sup_{X\in\left(\mathbb{S}^{d-1}\right)^{n}}\mathbb{E}_{\mathcal{A}}\left\|n\mathcal{A}(X)-\sum_{x\in
X}x\right\|^{2}\geq\sup_{X\in\left(\mathbb{S}^{d-1}\right)^{n}}\mathbb{E}_{\mathcal{R}^{\prime}}\left\|\sum_{x\in
X_{\text{priv}}}\mathcal{R}^{\prime}(x)-\sum_{x\in
X_{\text{priv}}}x\right\|^{2}.$ (35)

To prove 35, we follow the idea in the proof of [AFT22, Proposition 3.3]. Let
$P$ denote the uniform distribution on $\mathbb{S}^{d-1}$. We have

$\displaystyle\sup_{X\in\left(\mathbb{S}^{d-1}\right)^{n}}\mathbb{E}_{\mathcal{A}}\left\|n\mathcal{A}(X)-\sum_{x\in
X}x\right\|^{2}\geq\mathbb{E}_{X\sim
P^{n},\mathcal{A}}\left\|n\mathcal{A}(X)-\sum_{x\in X}x\right\|^{2}$
$\displaystyle\geq$
$\displaystyle\mathbb{E}\left\|\mathcal{M}_{\text{priv}}(\mathcal{R}(x_{1}),\cdots,\mathcal{R}(x_{n_{\text{priv}}}))-\sum_{x\in
X_{\text{priv}}}x\right\|^{2}+\mathbb{E}\left\|\mathcal{M}_{\text{pub}}(X_{\text{pub}})-\sum_{x\in
X_{\text{pub}}}x\right\|^{2},$

since the cross-term (inner product) vanishes by independence of
$X_{\text{pub}}$ and $X_{\text{priv}}$, and unbiasedness of
$\mathcal{M}_{\text{pub}}$. Now, [AFT22, Lemma A.1] shows that there exist
$\varepsilon$-LDP randomizers $\\{\hat{\mathcal{R}}_{x}\\}_{x\in
X_{\text{priv}}}$ such that $\mathbb{E}[\hat{\mathcal{R}}_{x}(v)]=v$ for all
$v\in\mathbb{S}^{d-1}$ and

$\mathbb{E}_{X_{\text{priv}}\sim
P^{n_{\text{priv}}}}\left\|\mathcal{M}_{\text{priv}}(\mathcal{R}(x_{1}),\cdots,\mathcal{R}(x_{n_{\text{priv}}}))-\sum_{x\in
X_{\text{priv}}}x\right\|^{2}\geq\sum_{x\in X_{\text{priv}}}\mathbb{E}_{v\sim
P}\|\hat{\mathcal{R}}_{x}(v)-v\|^{2}.$

Hence

$\sup_{X\in\left(\mathbb{S}^{d-1}\right)^{n}}\mathbb{E}_{\mathcal{A}}\left\|n\mathcal{A}(X)-\sum_{x\in
X}x\right\|^{2}\geq\sum_{x\in X_{\text{priv}}}\mathbb{E}_{v\sim
P}\|\hat{\mathcal{R}}_{x}(v)-v\|^{2}.$

Define $\mathcal{R}^{\prime}_{x}(v):=U^{T}\hat{\mathcal{R}}_{x}(Uv)$ for
$v\in\mathbb{S}^{d-1}$, where $U$ is a uniformly random rotation matrix such
that $U^{T}U=\mathbf{I}_{d}$. Note that $\mathcal{R}^{\prime}_{x}$ is an
$\varepsilon$-LDP randomizer such that $\mathbb{E}[\mathcal{R}^{\prime}(v)]=v$
for all $v\in\mathbb{S}^{d-1},x\in X_{\text{priv}}$. Moreover, for any fixed
$v\in\mathbb{S}^{d-1},x\in X_{\text{priv}}$, we have

$\displaystyle\mathbb{E}\|\mathcal{R}_{x}^{\prime}(v)-v\|^{2}$
$\displaystyle=\mathbb{E}_{U}\|\hat{\mathcal{R}}_{x}(Uv)-Uv\|^{2}$
$\displaystyle=\mathbb{E}_{v^{\prime}\sim
P}\|\hat{\mathcal{R}}_{x}(v^{\prime})-v^{\prime}\|^{2}$

Let $x^{*}:=\operatorname*{argmin}_{x\in
X_{\text{priv}}}\sup_{v\in\mathbb{S}^{d-1}}\mathbb{E}\|\mathcal{R}_{x}^{\prime}(v)-v\|^{2}$
and $\mathcal{R}^{\prime}(v):=\mathcal{R}_{x^{*}}^{\prime}(v)$. Then putting
the pieces together, we have

$\displaystyle\sup_{X\in\left(\mathbb{S}^{d-1}\right)^{n}}\mathbb{E}_{\mathcal{A}}\left\|n\mathcal{A}(X)-\sum_{x\in
X}x\right\|^{2}$ $\displaystyle\geq\sum_{x\in
X_{\text{priv}}}\sup_{v\in\mathbb{S}^{d-1}}\mathbb{E}\|\mathcal{R}_{x}^{\prime}(v)-v\|^{2}$
$\displaystyle\geq
n_{\text{priv}}\sup_{v\in\mathbb{S}^{d-1}}\mathbb{E}\|\mathcal{R}^{\prime}(v)-v\|^{2}$
$\displaystyle=\sup_{X_{\text{priv}}\in(\mathbb{S}^{d-1})^{n_{\text{priv}}}}\mathbb{E}_{\mathcal{R}^{\prime}}\left\|\sum_{x\in
X_{\text{priv}}}\mathcal{R}^{\prime}(x)-\sum_{x\in
X_{\text{priv}}}x\right\|^{2},$

by conditional independence of $\\{\mathcal{R}^{\prime}(x)\\}_{x\in
X_{\text{priv}}}$ given $X$. This establishes 35. Thus,

$\displaystyle
n^{2}\sup_{X\in\left(\mathbb{S}^{d-1}\right)^{n}}\mathbb{E}_{\mathcal{A}}\left\|\mathcal{A}(X)-\bar{X}\right\|^{2}$
$\displaystyle=\sup_{X\in\left(\mathbb{S}^{d-1}\right)^{n}}\mathbb{E}_{\mathcal{A}}\left\|n\mathcal{A}(X)-\sum_{x\in
X}x\right\|^{2}$
$\displaystyle\geq\sup_{X\in\left(\mathbb{S}^{d-1}\right)^{n}}\mathbb{E}_{\mathcal{R}^{\prime}}\left\|\sum_{x\in
X_{\text{priv}}}\mathcal{R}^{\prime}(x)-\sum_{x\in
X_{\text{priv}}}x\right\|^{2}$
$\displaystyle\geq\sup_{X\in\left(\mathbb{S}^{d-1}\right)^{n}}\mathbb{E}\left\|\sum_{x\in
X_{\text{priv}}}\text{PrivUnit}(x)-\sum_{x\in X_{\text{priv}}}x\right\|^{2}$
$\displaystyle=n^{2}\sup_{X\in\left(\mathbb{S}^{d-1}\right)^{n}}\mathbb{E}_{\mathcal{A}_{\text{semi-
PrivU}}}\|\mathcal{A}_{\text{semi-PrivU}}(X)-\bar{X}\|^{2},$

where we used 34 in the last inequality. Dividing both sides of the above
inequality by $n^{2}$ completes the proof. ∎

###  D.2 Optimal Semi-LDP Stochastic Convex Optimization

######  Theorem 37 (Complete statement of Theorem 19).

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

$cLD\min\left\\{\frac{1}{\sqrt{n_{\text{pub}}}},\sqrt{\frac{d}{n\min(\varepsilon,\varepsilon^{2})}}+\frac{1}{\sqrt{n}}\right\\}\leq\mathcal{R}_{\text{SCO}}^{\text{loc}}(\varepsilon,n_{\text{priv}},n,d,L,D)\leq
CLD\min\left\\{\frac{1}{\sqrt{n_{\text{pub}}}},\sqrt{\frac{d}{n\min(\varepsilon,\varepsilon^{2})}}+\frac{1}{\sqrt{n}}\right\\},$

and

$cLD\min\left\\{\frac{1}{n_{\text{pub}}},\frac{d}{n\min(\varepsilon,\varepsilon^{2})}+\frac{1}{n}\right\\}\leq\mathcal{R}_{\text{SCO}}^{\text{loc}}(\varepsilon,n_{\text{priv}},n,d,L,D,\mu)\leq
C\frac{L^{2}}{\mu}\min\left\\{\frac{1}{n_{\text{pub}}},\frac{d}{n\min(\varepsilon,\varepsilon^{2})}+\frac{1}{n}\right\\}.$

###### Proof.

Lower bounds: Let $\mathcal{A}$ be $\varepsilon$-semi-LDP and denote
$w_{\text{priv}}=\mathcal{A}(X)$.

Strongly convex lower bound: We begin with the strongly convex lower bounds,
which can be proved straightforwardly by reducing strongly convex SCO to mean
estimation and applying Theorem 15. 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}.$
(36)

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 15 (and its proof, to account for the re-scaling).
Specifically, there is a distribution $P$ on $\mathcal{X}$ such that

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

Combining this with 36 leads to the desired excess risk lower bound.

Convex lower bound: 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$.

Let $\mathcal{W}=\mathbb{B}$,
$\mathcal{X}=\left\\{\pm\frac{1}{\sqrt{d}}\right\\}^{d}$, and

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

which is convex and $1$-uniformly-Lipschitz in $w$ on $\mathcal{X}$. For any
$\varepsilon$-semi-LDP $\mathcal{A}^{\prime}(X)=w_{\text{priv}}^{\prime}$ and
any $\gamma\in(0,1)$, the proof of Theorem 15 constructs a distribution
$P_{\gamma}$ on $\mathcal{X}$ with mean $\mathbb{E}_{x\sim
P_{\gamma}}[x]=\theta\in\\{\pm\frac{\gamma}{\sqrt{d}}\\}^{d}$ such that

$\mathbb{E}_{w_{\text{priv}}^{\prime},X\sim
P_{\gamma}^{n}}\left[\left\|w_{\text{priv}}^{\prime}-\theta\right\|^{2}\right]\geq\frac{\gamma^{2}}{4}\left[1-\sqrt{4000\gamma^{2}\left(\frac{n_{\text{priv}}\min(\varepsilon,\varepsilon^{2})}{d}+n_{\text{pub}}\right)}\right].$
(37)

Now, let $F_{\gamma}(w)=\mathbb{E}_{x\sim P_{\gamma}}[f(w,x)]$ and
$w^{*}_{\gamma}=\operatorname*{argmin}_{w\in\mathcal{W}}F_{\gamma}(w)=\frac{\theta}{\|\theta\|}$.
A direct calculation (see e.g. [KLZ22, Equation 14]) shows

$\displaystyle\mathbb{E}F_{\gamma}(w)-F_{\gamma}^{*}$
$\displaystyle\geq\frac{1}{2}\mathbb{E}\left[\|\theta\|\|w-w^{*}_{\gamma}\|^{2}\right]$
$\displaystyle\geq\frac{1}{2\|\theta\|}\mathbb{E}\left[\|w^{\prime}-\theta\|^{2}\right]$
$\displaystyle=\frac{1}{2\gamma}\mathbb{E}\left[\|w^{\prime}-\theta\|^{2}\right]$
(38)

for any $w\in\mathcal{W},w^{\prime}:=w\|\theta\|$. Note that
$\mathcal{A}(X)=w_{\text{priv}}$ is $\varepsilon$-semi-DP if and only if
$\mathcal{A}^{\prime}(X)=w_{\text{priv}}^{\prime}:=\|\theta\|w_{\text{priv}}=\gamma
w_{\text{priv}}$ is $\varepsilon$-semi-DP, by post-processing. Thus, 37 and
D.2 together imply that any $\varepsilon$-semi-DP $w_{\text{priv}}^{\prime}$
has worst-case excess risk that is lower bounded by

$\displaystyle\mathbb{E}[F_{\gamma}(w_{\text{priv}}^{\prime})-F_{\gamma}^{*}]\geq\frac{\gamma}{8}\left[1-\sqrt{4000\gamma^{2}\left(\frac{n_{\text{priv}}\min(\varepsilon,\varepsilon^{2})}{d}+n_{\text{pub}}\right)}\right].$

Choosing
$\gamma^{2}=c\min\left(\frac{d}{n_{\text{priv}}\min(\varepsilon,\varepsilon^{2})},\frac{1}{n_{\text{pub}}}\right)$
for some small $c\in(0,1/16000)$ implies

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

for some $c^{\prime}>0$. This proves the desired lower bound for the case when
$L=D=1$. In the general case, we scale our hard instance, as in the proof of
Theorem 5: 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)]$, $\theta:=\mathbb{E}_{x\sim
P}[x]$,
$w^{*}:=\operatorname*{argmin}_{w\in\mathcal{W}}F(w)=\frac{\theta}{\|\theta\|}$,
$\widetilde{F}(\widetilde{w})=\mathbb{E}_{\widetilde{x}\sim\widetilde{P}}[f(\widetilde{w},\widetilde{x})]$,
$\widetilde{w}=Dw$, and
$\widetilde{\theta}:=\mathbb{E}_{\widetilde{x}\sim\widetilde{P}}[\widetilde{x}]=L\theta$,
then
$\widetilde{w}^{*}=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{\theta}\rangle+\langle\widetilde{w}^{*},\widetilde{\theta}\rangle$
$\displaystyle=D\langle\widetilde{\theta},w^{*}-w\rangle$
$\displaystyle=LD\langle\theta,w^{*}-w\rangle$
$\displaystyle=LD\left[F(w)-F^{*}\right].$

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

##### Upper bounds:

The first term in each of the upper bounds ($LD/\sqrt{n_{\text{pub}}}$ for
convex, and $L^{2}/(\mu n_{\text{pub}})$ for strongly convex) is attained by
the throw-away algorithm that runs $n_{\text{pub}}$ steps of (one-pass) SGD on
$X_{\text{pub}}$ [NY83].

The second term in the convex upper bound follows from the $\varepsilon$-LDP
(hence semi-LDP) upper bound of [DJW13, Proposition 3]: although their upper
bound only holds for $\varepsilon\leq 1$, if we replace their LDP randomizer
with PrivUnit, then we get the upper bound stated in Theorem 19.

For the second term in the strongly convex upper bound, we run
$\varepsilon$-LDP-SGD as in [DJW13] but with their LDP randomizer replaced by
PrivUnit. We also return a non-uniform weighted average $\hat{w}_{n}$ of the
iterates $w_{1},\ldots,w_{n}$ as in [RSS12] to obtain

$\mathbb{E}F(\hat{w}_{n})-F^{*}\leq C\frac{G^{2}}{\mu n},$

where $G^{2}=\sup_{t\in[n]}\mathbb{E}\|\text{PrivUnit}(\nabla
f(w_{t},x_{t}))\|^{2}\lesssim
L^{2}\left(1+\frac{d}{\varepsilon}+\frac{d}{(e^{\varepsilon}-1)^{2}}\right)$
[BDF+18, Proposition 4]. Thus,

$\mathbb{E}F(\hat{w}_{n})-F^{*}\leq
C^{\prime}\frac{L^{2}}{\mu}\left(\frac{d}{n\min(\varepsilon,\varepsilon^{2})}+\frac{1}{n}\right).$

This completes the proof. ∎

####  D.2.1 An “Even More Optimal” Semi-LDP Algorithm for SCO

Algorithm 3 Semi-LDP-SGD

1: Input: clip threshold $C>0$, stepsize $\eta$, PrivUnit parameters
$(p,\gamma)$.

2: Initialize $w_{0}\in\mathcal{W}$.

3: for $t\in\\{0,1,\cdots,n-1\\}$ do

4: Draw random sample $x_{t}$ from $X$ without replacement.

5: if $x_{t}\in X_{\text{priv}}$ then

6: $\widetilde{g}_{t}\leftarrow\text{PrivUnit}(\text{clip}_{C}(\nabla
f(w_{t},x_{t})))$, where PrivUnit is defined in Algorithm 2.

7: else

8: $\widetilde{g}_{t}\leftarrow\nabla f(w_{t},x_{t})$

9: end if

10: Update $w_{t+1}:=\Pi_{\mathcal{W}}[w_{t}-\eta\widetilde{g}_{t}]$.

11: end for

12: Output: $\bar{w}_{n}=\frac{1}{n}\sum_{i=1}^{n}w_{i}$.

######  Proposition 38 (Re-statement of Proposition 20).

Let $f\in\mathcal{F}_{L,D}$ and $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\\}.$

###### Proof.

Privacy: Since PrivUnit is an $\varepsilon$-LDP randomizer and we are applying
PrivUnit to all the private samples $x\in X_{\text{priv}}$, Algorithm 3 is
$\varepsilon$-semi-LDP.

##### Excess risk:

Choose $C>L$: i.e. we don’t clip, since stochastic subgradients are already
uniformly bounded by the $L$-Lipschitz assumption. By the classical analysis
of the stochastic subgradient method (see e.g. [B+15]), we can obtain

$\displaystyle\mathbb{E}F(\bar{w}_{n})-F^{*}$
$\displaystyle\leq\frac{1}{n}\sum_{t=1}^{n}\mathbb{E}[\widetilde{g}_{t}^{T}(w_{t}-w^{*})]$
$\displaystyle\leq\frac{D^{2}}{\eta
n}+\frac{\eta}{n}\left(n_{\text{priv}}G_{a}^{2}+n_{\text{pub}}G_{b}^{2}\right),$

where $G_{a}^{2}:=\sup_{t}\mathbb{E}\|\text{PrivUnit}(\nabla
f(w_{t},x_{t}))\|^{2}$ and $G_{b}^{2}:=\sup_{t}\mathbb{E}\|\nabla
f(w_{t},x_{t})\|^{2}$. By the uniform Lipschitz assumption, we have
$G_{b}^{2}\leq L^{2}$. By [BDF+18, Proposition 4], we have $G_{a}^{2}\leq
c^{2}L^{2}\frac{d}{\min(\varepsilon,\varepsilon^{2})}$ for some absolute
constant $c>0$. Thus, choosing
$\eta=\frac{D}{L}\min\left(\sqrt{\frac{\min(\varepsilon,\varepsilon^{2})}{n_{\text{priv}}c^{2}d}},\frac{1}{\sqrt{n_{\text{pub}}}}\right)$
yields

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

This completes the proof. ∎

##  Appendix E Numerical Experiments

Code for all of the experiments is available here:
https://github.com/optimization-for-data-driven-science/DP-with-public-data.

###  E.1 Central Semi-DP Experiments

####  E.1.1 Semi-DP Linear Regression with Gaussian Data

##### Data Generation:

We implement Algorithm 1 on synthetic data designed for a linear regression
problem of dimension $2,000$, using the squared error loss: $f(w,x)=(\langle
w,x^{(1)}\rangle-x^{(2)})^{2}$, where $x^{(1)}\in\mathbb{R}^{d}$ denotes the
feature vector and $x^{(2)}\in\mathbb{R}$ is the target. Here, $d=2,000$. Our
synthetic dataset consists of $n=75,000$ training samples, $18,750$ validation
samples, and $10,000$ test samples. The feature vectors $x_{i}:=x^{(1)}_{i}$
and the optimal parameter vector $w^{*}$ are drawn i.i.d. from a multivariate
Gaussian distribution $\mathcal{N}\left(0,\mathbf{I}_{2000}\right)$. We
generate predicted values $x^{(2)}_{i}$ from a Gaussian distribution
$\mathcal{N}\left(\langle w^{*},x_{i}\rangle,0.5\right)$. Thus, the optimal
linear regression model has which ensures an optimal mean squared error of
$0.25$.

##### Experimental Setup:

Our experiments investigate two phenomena: 1) the effect of the ratio
$\frac{n_{\text{pub}}}{n}$ on test loss when $\varepsilon\in\\{1,2\\}$ is
fixed, for values of $\frac{n_{\text{pub}}}{n}$ ranging from $0.03$ to $0.95$;
and 2) the effect of privacy (quantified by $\varepsilon$) on test loss, for
fixed $\frac{n_{\text{pub}}}{n}\in\\{0.03,0.04\\}$, and varying
$\varepsilon\in\\{0.1,0.5,1.0,2.0,4.0,8.0\\}$. We maintain the privacy
parameter $\delta$ at a constant value of $10^{-5}$ throughout out
experiments. All algorithms undergo extensive hyperparameter tuning using the
validation dataset, and the performance of each tuned algorithm is
subsequently assessed using the test dataset. (See “Hyperparameter Tuning”
paragraph below for details on the tuning process.) The plots in Section 4
show the test loss for each algorithm with standard error bars computed over 5
independent trials.

##### Details on Implementations of Algorithms:

We compare four different semi-DP algorithms: 1. Throw-away. 2\. DP-SGD
[ACG+16, DBH+22]. 3\. PDA-MD [AGM+22, Algorithm 1]. 4\. Our Algorithm
1—specifically, the sample-with-replacement version of our algorithm. The
Throw-away algorithm simply returns a minimizer $w_{\text{pub}}$ of the public
loss:
$w_{\text{pub}}=(X_{\text{pub}}^{T}X_{\text{pub}})^{-1}X_{\text{pub}}^{T}y_{\text{pub}}$.
DP-SGD adds noise to all (public or private) gradients. We use the state-of-
the-art (for image classification) implementation of DP-SGD of [DBH+22]. We
adopt the re-parameterization of DP-SGD in [DBH+22, Equation 3] to ease the
hyperparameter tuning. For PDA-MD, we implement [AGM+22, Algorithm]. We use
their exact Mirror descent form by multiplying the inverse of the hessian
$X_{\text{pub}}^{T}X_{\text{pub}}$ by the private gradient [AGM+22]. In their
original implementation, they added a small constant, Hessian Regularization,
times the identity matrix to the Hessian before calculating the inverse for
numerically stable. We choose the hessian regularization constant as $0.01$,
the same value in their original implementation.

Effect of hessian regularization parameter on PDA-MD: Upon reproducing the
results of PDA-MD, we discovered a high sensitivity to the choices of Hessian
Regularization, especially when the ratio of the largest and the smallest
eigenvalue of the data matrix is large. We test PDA-MD on the dataset proposed
in the original study as well as on our own dataset. The results of these
tests are displayed in Fig. 6. We see PDA-MD is sensitive to hessian
regularization parameter, which requires extra tuning on complicated tasks. We
implement PDA-MD with the optimal regularization value of $0.01$.

Details on warm-start: In our evaluation, we adopt a “warm start” strategy for
all algorithms: we first find a minimizer $w_{\text{pub}}$ of the public loss,
and then initialize the training process with $w_{\text{pub}}$. Note that the
minimizer $w_{\text{pub}}$ of the public loss can be obtained via
$w_{\text{pub}}=\left(X_{\text{pub}}^{T}X_{\text{pub}}\right)^{-1}X_{\text{pub}}^{T}y_{\text{pub}}$.

Clipping public gradients improves performance: We have empirically found that
a slight modification of Algorithm 1 offers performance benefits. Namely, it
is beneficial to project the public gradients onto the $\ell_{2}$-sphere of
radius $C$; that is, we re-scale the public gradients to have $\ell_{2}$-norm
equal to $C$. Note that semi-DP still holds regardless of whether or not the
public gradients are re-scaled. Re-scaling the public gradients helps balance
the effects of the public and private gradients on the optimization
trajectory. In the original method stated in Algorithm 1, if unclipped public
gradients and the private gradient are of very different magnitudes, then one
gradient direction might dominate the optimization procedure, leading to a
sub-optimal model. Thus, our public gradient re-scaling technique promotes a
more balanced update, which gracefully combines the public and private data in
each iteration. To the best of our knowledge, this technique is novel.

Privacy accounting: We compute the privacy loss of each algorithm by using the
moments acccountant of Abadi et al. [ACG+16]. For a fixed clip threshold $C$,
privacy level $(\varepsilon,\delta)$ is determined by three parameters: the
variance of privacy noise $\sigma^{2}$, the private sampling ratio
$q:=K_{\text{priv}}/n_{\text{priv}}$, and the total number of iterations $T$.
In our setting, the privacy parameters $(\varepsilon,\delta)$ are given, and
we use the moments accountant to compute an approximation of $\sigma^{2}$ for
any choice of hyperparameters $T$ and $q$. We utilize the implementation of
the privacy accountant provided by the Pytorch privacy framework, Opacus.

##### Hyperparameter Tuning:

The results reported are for each algorithm with the hyperparameters (step
size, number of epochs and $\alpha$ in Semi-DP) that attain the best
performance for a given experiment. For simplicity and computation efficiency,
we keep clip threshold $C=1$ for all of our experiments. Preliminary
experiments found that a clip threshold of $C=1$ worked well for all
algorithms. To tune Algorithm 1, we use Bayesian hyperparameter optimization.
That is, we build a probability model of the objective function and use it to
select the most promising hyperparameters to evaluate in the true objective
function. We find that both DP-SGD and PDA-MD are relatively insensitive to
hyperparameters. Therefore, to save time, we use grid search to tune them. We
also randomly select some setups and apply both tuning methods. It turns out
that Bayesian hyperparameter optimization and grid search yield very similar
results. See Tables 1 and 2 in Section E.3 for detailed descriptions of the
hyperparameter search grids.

Figure 6: Loss v.s. PDA-MD Regularization Parameter. Left: Results on proposed
dataset in [AGM+22]. Right: Results on our dataset. PDA-MD is sensitive to
hessian regularization parameter, which requires extra tuning on complicated
tasks.

####  E.1.2 Semi-DP Logistic Regression with CIFAR-10

We evaluate the performance of Algorithm 1 in training a logistic regression
model to classify digits in the CIFAR-10 dataset [KH+09]. We compare Algorithm
1 against DP-SGD and throw-away. Note that PDA-MD does not have an efficient
implementation for logistic regression. This is because there does not exist a
closed form update rule for the mirror descent step. Thus, we do not compare
against PDA-MD.

We flatten the images and feed them to the logistic (softmax) model. Cross-
entropy loss is used here; therefore, the model is convex. Implementations of
the algorithms are similar to the linear regression case. However, in this
case, throw-away consists of running non-private SGD on $X_{\text{pub}}$ to
find an approximate minimizer $w_{\text{pub}}$. For all three algorithms, we
fixed batch-size 256 and privacy parameter $\delta=10^{-6}.$ The remaining
hyperparameters are tuned by grid search, using the same grid for each
algorithm. Also, in contrast to the linear regression experiments, we do not
use warm-start for any of the algorithms and we use GD instead of SGD for all
algorithms in these experiments. See Table 3 in Section E.3 for detailed
descriptions of the hyperparameter search grids.

Results are reported in Figs. 7, 8, 9 and 10. Our Algorithm 1 always
outperforms the baselines in terms of minimizing test accuracy/error. The
advantage of Algorithm 1 over these baselines is even more pronounced than it
was for linear regression. This might be partially due to the fact that we did
not use warm-start.

Figure 7: Test error rate vs. $\frac{n_{\text{pub}}}{n}$. Left:
$\varepsilon=0.1$. Middle: $\varepsilon=0.5$. Right: $\varepsilon=1.0$

Figure 8: Test error rate vs. $\frac{n_{\text{pub}}}{n}$. Left:
$\varepsilon=2.0$. Middle: $\varepsilon=4.0$. Right: $\varepsilon=8.0$

Figure 9: Test error rate vs. $\varepsilon$. Left:
$\frac{n_{\text{pub}}}{n}=0.01$. Middle: $\frac{n_{\text{pub}}}{n}=0.02$.
Right: $\frac{n_{\text{pub}}}{n}=0.04$

Figure 10: Test error rate vs. $\varepsilon$. Left:
$\frac{n_{\text{pub}}}{n}=0.1$. Middle: $\frac{n_{\text{pub}}}{n}=0.2$. Right:
$\frac{n_{\text{pub}}}{n}=0.3$

###  E.2 Semi-Local DP Experiments

In this section, we empirically evaluate our semi-LDP Algorithm 3 on linear
regression. While running the experiments, we observed that the noisy clipped
private gradients $\text{PrivUnit}(\text{clip}_{C}(\nabla f(w_{t},x_{t})))$
and the public gradients $\nabla f(w_{t},x_{t})$ had very different
magnitudes. This made it challenging for our algorithm to utilize both the
public and private data in the most effective way possible. To overcome this
difficulty, we scale $\nabla f(w_{t},x_{t})$, so that it is of a similar
magnitude as $\text{PrivUnit}(\text{clip}_{C}(\nabla f(w_{t},x_{t})))$. In
more detail, at the beginning of the algorithm, we randomly take the first
private sample $x_{0}\in X_{\text{priv}}$, apply the update rule and record
the norm of the noisy gradient. That is, at Line 6 of Algorithm 3,
additionally we perform once
$L_{\text{pub}}\leftarrow\|\text{PrivUnit}(\text{clip}_{C}(\nabla
f(w_{0},x_{0})))\|_{2}$. Then for all the public samples later on, we scale
their gradient to $L_{\text{pub}}$. That is at Line 8 of Algorithm 3, we do
$\widetilde{g}_{t}\leftarrow\frac{L_{\text{pub}}\nabla
f(w_{t},x_{t})}{\|\nabla f(w_{t},x_{t})\|_{2}}$.

####  E.2.1 Semi-LDP Linear Regression with Gaussian Data

We use the same experimental setup and data generation process as described
above in Section E.1.1 but
$\frac{n_{\text{pub}}}{n}\in\\{0.03,0.05,0.1,0.2\\}$, and
$\varepsilon\in\\{16.0,32.0,64.0,128.0\\}$. We compare three linear-time semi-
LDP algorithms: 1) LDP-SGD [DJW13], which is optimal up to constants for semi-
LDP SCO (by Theorem 19). 2) Throw-away: This algorithm runs SGD on the public
data. 3) Our Algorithm 3, which has smaller worst-case error than LDP-SGD
theoretically, according to Proposition 20. For fairness of comparison, we run
each of the three algorithms for the same total number of iterations
(stochastic gradient evaluations) $T$, with
$T=n=n_{\text{priv}}+n_{\text{pub}}$ (i.e. one epoch). Due to the small number
of iterations, warm-start is used. Hence all three algorithm start from
$w^{*}_{pub}$, a minimizer of the public loss. The range of hyperparameter
search is detailed in Table 4 in Section E.3.

We use PrivUnitG [AFT22] instead of PrivUnit in line 6 of our implementation
of Algorithm 3. PrivUnitG is an approximation of PrivUnit that can be easier
to implement and tune. Also, we use PrivUnitG in our implementation of LDP-
SGD, even though [DJW13] proposes using a different, suboptimal (in terms of
constants) LDP randomizer. We make this improvement to LDP-SGD so that the
only difference between LDP-SGD and semi-LDP-SGD occurs in lines 7-8 of
Algorithm 3. This allows us to isolate the role of semi-LDP vs. LDP in
determining the accuracy of the trained model.

Results are shown in Figs. 11, 12, 13 and 14. As we can see, semi-LDP SGD
achieves the smallest test error consistently across different experimental
settings.

Figure 11: Test loss vs. $\frac{n_{\text{pub}}}{n}$. Left: $\varepsilon=16$.
Right: $\varepsilon=32$.

Figure 12: Test loss vs. $\frac{n_{\text{pub}}}{n}$. Left: $\varepsilon=64$.
Right: $\varepsilon=128$.

Figure 13: Test loss vs. $\varepsilon$. Left: $\frac{n_{\text{pub}}}{n}=0.03$.
Right: $\frac{n_{\text{pub}}}{n}=0.05$.

Figure 14: Test loss vs. $\varepsilon$. $\frac{n_{\text{pub}}}{n}=0.1$.
$\frac{n_{\text{pub}}}{n}=0.2$.

###  E.3 Hyperparameters Search Grids

hyperparameter | private_epochs | learning-rate
---|---|---
value | $10,15,20,\ldots,55$ | $0,1,2,\ldots,160$
Table 1: Grid used for hyperparameter search for PDA-MD and DP-SGD in Section E.1.1 hyperparameter | private_epochs | learning-rate | $\alpha$
---|---|---|---
value | $[10,55]$ | $[0,160]$ | [0,1]
Table 2: Range used for Bayesian hyperparameter search for Semi-DP in Section E.1.1. We only allow interger values for private_epochs and learning-rate. hyperparameter | value
---|---
iterations | $2000,4000,6000,\ldots,20000$
learning-rate | $0.005,0.01,0.05,0.1,0.15,0.2,0.25,0.5,0.75,1,1.5,2,3,4,5$
$\alpha$ | $0,0.1,0.2,\ldots,1$
Table 3: Grid used for hyperparameter search for DP-SGD and Semi-DP in Section E.1.2 hyperparameter | learning-rate |  $p$ in PrivUnitG
---|---|---
value | $[10^{-5},1]$ | [0,1]
Table 4: Range used for Bayesian hyperparameter search for LDP and Semi-LDP in
Section E.2.

##  Appendix F Limitations

Limitations of Theoretical Results: Our theoretical results rely on certain
assumptions (e.g convex, Lipschitz loss, i.i.d. data for SCO), that may be
violated in certain applications. We leave it as future work to investigate
the questions considered in this work under different assumptions (e.g. non-
convexity, semi-DP SCO with out-of-distribution public data). Also, we
reiterate that our theoretical results describe the optimal worst-case error.
It might be the case that the worst-case distributions we construct in our
lower bound proofs are unlikely to appear in practice. Thus, another
interesting direction for future work would be to analyze “instance-optimal”
[AD20b, AD20a] semi-DP error rates.

##### Limitations of Experiments:

It is important to note that pre-processing and hyperparameter tuning were not
done in a DP manner, since we did not want to detract focus from evaluation of
the (fully tuned) semi-DP algorithms.777See, e.g. [LT19, PS22] and the
references therein for discussion of DP hyperparameter tuning. As a
consequence, the overall privacy loss for the entire experimental process is
higher than the $\varepsilon$ indicated in the plots: the $\varepsilon$
indicated in the plots solely reflects the privacy loss from running the
algorithms with fixed hyperparameters and (pre-processed) data.

##  Appendix G Broader Impacts

Our work provides algorithms for protecting the privacy of individuals who
contribute training data. Privacy is commonly regarded in a positive light and
is even enshrined as a fundamental right in various legal systems. However,
there is a risk that corporations or governments could exploit our algorithms
for nefarious purposes, such as unauthorized collection of personal data.
Furthermore, the use of semi-privately trained models may result in decreased
accuracy compared to non-private models, which can have adverse consequences.
For instance, if a semi-DP model is utilized to forecast the effects of
pollution, but yields less precise and overly optimistic outcomes, it could
provide pretext for a government to unjustly dismantle environmental
safeguards. Nonetheless, we firmly believe that the dissemination of privacy-
preserving machine learning algorithms, coupled with enhanced understanding of
these algorithms, ultimately offers a net benefit to society.

Another potential misuse of our work would be using the accuracy benefits of
public data to argue for less stringent data privacy policies, laws, or
regulations. However, we want to emphasize that even though public data can
enhance the accuracy of models, we firmly believe that privacy laws and
corporate policies should not be weakened. Differentially private synthetic
data generation [TKP19, VTB+20, BSV22, HVZ23] is one possible avenue for
generating public data in an ethical, privacy-preserving manner.