$\displaystyle+\tilde{O}\left({\frac{H\left\|{{\mathcal{X}}}\right\|^{2}D^{2}}{{n_{\text{priv}}}\epsilon}+\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}\right)+O\left({\frac{GD\left\|{{\mathcal{X}}}\right\|\sqrt{\operatorname{log}\left(4/\beta\right)}}{{n_{\text{priv}}}\epsilon}}\right)$
$\displaystyle+O\left({\left({\frac{\sqrt{H}D^{2}\left\|{{\mathcal{X}}}\right\|^{2}G\sqrt{\operatorname{log}\left(1/\delta\right)}}{{n_{\text{priv}}}\epsilon}}\right)^{2/3}+\frac{H^{1/4}D\left\|{{\mathcal{X}}}\right\|\sqrt{G}\left({\operatorname{log}\left(1/\delta\right)}\right)^{1/4}L(w^{*};{\mathcal{D}})^{1/4}}{\sqrt{{n_{\text{priv}}}\epsilon}}}\right)$

The public sample complexity is,

$\displaystyle{n_{\text{pub}}}=\tilde{O}\left({\frac{(HD\left\|{{\mathcal{X}}}\right\|)^{2/3}({n_{\text{priv}}}\epsilon)^{2/3}}{G^{2/3}(\operatorname{log}\left(1/\delta\right))^{1/3}}+\frac{\sqrt{H}{n_{\text{priv}}}\epsilon\sqrt{L(w^{*};{\mathcal{D}})}}{G\sqrt{\operatorname{log}\left(1/\delta\right))}}}\right)$

This completes the first part of the theorem. For thee second part, we start
from eq. 16,

$\displaystyle L(\widehat{w};{\mathcal{D}})\leq
L(w^{*};{\mathcal{D}})+\tilde{O}{\left({\frac{\sqrt{H}D\left\|{{\mathcal{X}}}\right\|}{\sqrt{{n_{\text{priv}}}\epsilon}}+\frac{\sqrt{H}D\left\|{{\mathcal{X}}}\right\|}{\sqrt{{n_{\text{pub}}}}}+\sqrt{\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}}\right)\sqrt{L(w^{*};{\mathcal{D}})}}$
$\displaystyle+\tilde{O}\left({\frac{H\left\|{{\mathcal{X}}}\right\|^{2}D^{2}}{{n_{\text{priv}}}\epsilon}+\frac{HD^{2}\left\|{{\mathcal{X}}}\right\|^{2}}{{n_{\text{pub}}}}+\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}\right)$
$\displaystyle+O\left({GD\left\|{{\mathcal{X}}}\right\|\left({\frac{\sqrt{{n_{\text{pub}}}\operatorname{log}\left(1/\delta\right)}+\sqrt{\operatorname{log}\left(4/\beta\right)}}{{n_{\text{priv}}}\epsilon}}\right)}\right)$
$\displaystyle\leq
L(\widehat{w}^{*};{\mathcal{D}})+\tilde{O}{\left({\frac{\sqrt{H}D\left\|{{\mathcal{X}}}\right\|}{\sqrt{{n_{\text{priv}}}\epsilon}}+\frac{\sqrt{H}D\left\|{{\mathcal{X}}}\right\|}{\sqrt{{n_{\text{pub}}}}}+\sqrt{\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}}\right)\sqrt{L(\widehat{w}^{*};{\mathcal{D}})}}$
$\displaystyle+\tilde{O}\left({\frac{H\left\|{{\mathcal{X}}}\right\|^{2}D^{2}}{{n_{\text{priv}}}\epsilon}+\frac{HD^{2}\left\|{{\mathcal{X}}}\right\|^{2}}{{n_{\text{pub}}}}+\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}\right)$
$\displaystyle+O\left({GD\left\|{{\mathcal{X}}}\right\|\left({\frac{\sqrt{{n_{\text{pub}}}\operatorname{log}\left(1/\delta\right)}+\sqrt{\operatorname{log}\left(4/\beta\right)}}{{n_{\text{priv}}}\epsilon}}\right)}\right)$
$\displaystyle\leq\widehat{L}(\widehat{w}^{*};S_{\text{priv}})+\tilde{O}{\left({\frac{\sqrt{H}D\left\|{{\mathcal{X}}}\right\|}{\sqrt{{n_{\text{priv}}}\epsilon}}+\frac{\sqrt{H}D\left\|{{\mathcal{X}}}\right\|}{\sqrt{{n_{\text{pub}}}}}+\sqrt{\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}}\right)\sqrt{\widehat{L}(\widehat{w}^{*};S_{\text{priv}})}}$
$\displaystyle+\tilde{O}\left({\frac{H\left\|{{\mathcal{X}}}\right\|^{2}D^{2}}{{n_{\text{priv}}}\epsilon}+\frac{HD^{2}\left\|{{\mathcal{X}}}\right\|^{2}}{{n_{\text{pub}}}}+\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}\right)$
$\displaystyle+O\left({GD\left\|{{\mathcal{X}}}\right\|\left({\frac{\sqrt{{n_{\text{pub}}}\operatorname{log}\left(1/\delta\right)}+\sqrt{\operatorname{log}\left(4/\beta\right)}}{{n_{\text{priv}}}\epsilon}}\right)}\right)$
$\displaystyle\leq\widehat{L}(\widehat{w}^{*};S_{\text{priv}})+\tilde{O}{\left({\frac{\sqrt{H}D\left\|{{\mathcal{X}}}\right\|}{\sqrt{{n_{\text{priv}}}\epsilon}}+\sqrt{\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}}\right)\sqrt{\widehat{L}(\widehat{w}^{*};{\mathcal{D}})}}$
$\displaystyle+\tilde{O}\left({\frac{H\left\|{{\mathcal{X}}}\right\|^{2}D^{2}}{{n_{\text{priv}}}\epsilon}+\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}\right)+O\left({\frac{GD\left\|{{\mathcal{X}}}\right\|\sqrt{\operatorname{log}\left(4/\beta\right)}}{{n_{\text{priv}}}\epsilon}}\right)$
$\displaystyle+O\left({\left({\frac{\sqrt{H}D^{2}\left\|{{\mathcal{X}}}\right\|^{2}G\sqrt{\operatorname{log}\left(1/\delta\right)}}{{n_{\text{priv}}}\epsilon}}\right)^{2/3}+\frac{H^{1/4}D\left\|{{\mathcal{X}}}\right\|\sqrt{G}\left({\operatorname{log}\left(1/\delta\right)}\right)^{1/4}L(\widehat{w};{\mathcal{D}})^{1/4}}{\sqrt{{n_{\text{priv}}}\epsilon}}}\right)$

where the second inequality holds form optimality of $w*$, the third from
uniform convergence, Theorem 1 in [43] and AM-GM inequality, and the last by
plugging in the following public sample complexity.

$\displaystyle{n_{\text{pub}}}=\tilde{O}\left({\frac{(HD\left\|{{\mathcal{X}}}\right\|)^{2/3}({n_{\text{priv}}}\epsilon)^{2/3}}{G^{2/3}(\operatorname{log}\left(1/\delta\right))^{1/3}}+\frac{\sqrt{H}{n_{\text{priv}}}\epsilon\sqrt{\widehat{L}(\widehat{w}^{*};S_{\text{priv}})}}{G\sqrt{\operatorname{log}\left(1/\delta\right))}}}\right)$

This completes the proof.

∎

######  Theorem 16.

In the setting of theorem 15 with the additional assumption that the global
minimizer of risk $L$, $w^{*}$ lies in ${\mathcal{W}}$, we get that with
${n_{\text{pub}}}=\tilde{O}\left({\frac{(HD\left\|{{\mathcal{X}}}\right\|)^{2/3}({n_{\text{priv}}}\epsilon)^{2/3}}{G^{2/3}(\operatorname{log}\left(1/\delta\right))^{1/3}}}\right)$,
with probability at least $1-\beta$,

$\displaystyle L(\widehat{w};{\mathcal{D}})-L(w^{*};{\mathcal{D}})$
$\displaystyle=\tilde{O}{\left({\frac{\sqrt{H}D\left\|{{\mathcal{X}}}\right\|}{\sqrt{{n_{\text{priv}}}\epsilon}}+\sqrt{\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}}\right)\sqrt{L(w^{*};{\mathcal{D}})}}+\tilde{O}\left({\frac{H\left\|{{\mathcal{X}}}\right\|^{2}D^{2}}{{n_{\text{priv}}}\epsilon}+\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}\right)$
$\displaystyle+O\left({\frac{GD\left\|{{\mathcal{X}}}\right\|\sqrt{\operatorname{log}\left(4/\beta\right)}}{{n_{\text{priv}}}\epsilon}}\right)+O\left({\left({\frac{\sqrt{H}D^{2}\left\|{{\mathcal{X}}}\right\|^{2}G\sqrt{\operatorname{log}\left(1/\delta\right)}}{{n_{\text{priv}}}\epsilon}}\right)^{2/3}}\right)$

Further,

$\displaystyle
L(\widehat{w};{\mathcal{D}})-\widehat{L}(\widehat{w}^{*};S_{\text{priv}})$
$\displaystyle=\tilde{O}{\left({\frac{\sqrt{H}D\left\|{{\mathcal{X}}}\right\|}{\sqrt{{n_{\text{priv}}}\epsilon}}+\sqrt{\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}}\right)\sqrt{\widehat{L}(\widehat{w}^{*};S_{\text{priv}})}}+\tilde{O}\left({\frac{H\left\|{{\mathcal{X}}}\right\|^{2}D^{2}}{{n_{\text{priv}}}\epsilon}+\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}\right)$
$\displaystyle+O\left({\frac{GD\left\|{{\mathcal{X}}}\right\|\sqrt{\operatorname{log}\left(4/\beta\right)}}{{n_{\text{priv}}}\epsilon}}\right)+O\left({\left({\frac{\sqrt{H}D^{2}\left\|{{\mathcal{X}}}\right\|^{2}G\sqrt{\operatorname{log}\left(1/\delta\right)}}{{n_{\text{priv}}}\epsilon}}\right)^{2/3}}\right).$

where $w^{*}$ and $\widehat{w}^{*}$ are population and empirical minimizers
with respect to ${\mathcal{D}}$ and $S_{\text{priv}}$ respectively.

###### Proof.

The proof is almost identical to that of theorem 16. We repeat the steps
pointing out the differences and how the expressions change. We continue till
eq. 12. Next, we apply smoothness which results in the key difference between
the analyses,

$\displaystyle L(\mathring{w}^{*};{\mathcal{D}})-L(w^{*};{\mathcal{D}})$
$\displaystyle\leq L(\bar{w}^{*};{\mathcal{D}})-L(w^{*};{\mathcal{D}})$
$\displaystyle\leq\mathbb{E}\left[\left\langle{\phi_{y}^{\prime}(\left\langle{w^{*}},{x}\right\rangle)},{\left\langle{\bar{w}^{*}},{x}\right\rangle-\left\langle{w^{*}},{x}\right\rangle}\right\rangle+\frac{H}{2}\left|{\left\langle{\bar{w}^{*}},{x}\right\rangle-\left\langle{w^{*}},{x}\right\rangle}\right|^{2}\right]$
$\displaystyle\leq\left\langle{\mathbb{E}\left[\phi_{y}^{\prime}(\left\langle{w^{*}},{x}\right\rangle)x\right]},{\bar{w}^{*}-w^{*}}\right\rangle+\frac{H}{2}\mathbb{E}\left[\left|{\left\langle{\bar{w}^{*}},{x}\right\rangle-\left\langle{w^{*}},{x}\right\rangle}\right|^{2}\right]$
$\displaystyle\leq\left\langle{\nabla
L(w^{*};{\mathcal{D}})},{\bar{w}^{*}-w^{*}}\right\rangle+H\alpha^{2}$
$\displaystyle=H\alpha^{2}$

where last equality uses the fact that $\nabla L(w^{*};{\mathcal{D}})=0$ since
$w^{*}$ is the unconstrained minimizer. Continuing, we get,

$\displaystyle\left|{L(\widehat{w};{\mathcal{D}})-\widehat{L}(\widehat{w};S_{\text{priv}})}\right|+\left|{L(\mathring{w}^{*};{\mathcal{D}})-\widehat{L}(\mathring{w}^{*};S_{\text{priv}})}\right|$
$\displaystyle=\tilde{O}{\left({\frac{\sqrt{H}D\left\|{{\mathcal{X}}}\right\|}{\sqrt{{n_{\text{priv}}}\epsilon}}+\sqrt{\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}}\right)\sqrt{L(w^{*};{\mathcal{D}})}}$
$\displaystyle+\tilde{O}\left({\frac{H\left\|{{\mathcal{X}}}\right\|^{2}D^{2}}{{n_{\text{priv}}}\epsilon}+\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}\right)+O\left({GD\left\|{{\mathcal{X}}}\right\|\left({\frac{\sqrt{{n_{\text{pub}}}\operatorname{log}\left(1/\delta\right)}+H\alpha^{2}+\sqrt{\operatorname{log}\left(4/\beta\right)}}{{n_{\text{priv}}}\epsilon}}\right)}\right)$

This yields,

$\displaystyle L(\widehat{w};{\mathcal{D}})-L(w^{*};{\mathcal{D}})$
$\displaystyle=\tilde{O}{\left({\frac{\sqrt{H}D\left\|{{\mathcal{X}}}\right\|}{\sqrt{{n_{\text{priv}}}\epsilon}}+\sqrt{\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}}\right)\sqrt{L(w^{*};{\mathcal{D}})}}$
$\displaystyle+\tilde{O}\left({\frac{H\left\|{{\mathcal{X}}}\right\|^{2}D^{2}}{{n_{\text{priv}}}\epsilon}+H\alpha^{2}+\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}\right)+O\left({GD\left\|{{\mathcal{X}}}\right\|\left({\frac{\sqrt{{n_{\text{pub}}}\operatorname{log}\left(1/\delta\right)}+\sqrt{\operatorname{log}\left(4/\beta\right)}}{{n_{\text{priv}}}\epsilon}}\right)}\right)$
$\displaystyle=\tilde{O}{\left({\frac{\sqrt{H}D\left\|{{\mathcal{X}}}\right\|}{\sqrt{{n_{\text{priv}}}\epsilon}}+\sqrt{\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}}\right)\sqrt{L(w^{*};{\mathcal{D}})}}$
$\displaystyle+\tilde{O}\left({\frac{H\left\|{{\mathcal{X}}}\right\|^{2}D^{2}}{{n_{\text{priv}}}\epsilon}+\frac{HD^{2}\left\|{{\mathcal{X}}}\right\|^{2}}{{n_{\text{pub}}}}+\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}\right)+O\left({GD\left\|{{\mathcal{X}}}\right\|\left({\frac{\sqrt{{n_{\text{pub}}}\operatorname{log}\left(1/\delta\right)}+\sqrt{\operatorname{log}\left(4/\beta\right)}}{{n_{\text{priv}}}\epsilon}}\right)}\right)$
$\displaystyle=\tilde{O}{\left({\frac{\sqrt{H}D\left\|{{\mathcal{X}}}\right\|}{\sqrt{{n_{\text{priv}}}\epsilon}}+\sqrt{\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}}\right)\sqrt{L(w^{*};{\mathcal{D}})}}+\tilde{O}\left({\frac{H\left\|{{\mathcal{X}}}\right\|^{2}D^{2}}{{n_{\text{priv}}}\epsilon}+\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}\right)$
$\displaystyle+O\left({\frac{GD\left\|{{\mathcal{X}}}\right\|\sqrt{\operatorname{log}\left(4/\beta\right)}}{{n_{\text{priv}}}\epsilon}}\right)+O\left({\left({\frac{\sqrt{H}D^{2}\left\|{{\mathcal{X}}}\right\|^{2}G\sqrt{\operatorname{log}\left(1/\delta\right)}}{{n_{\text{priv}}}\epsilon}}\right)^{2/3}}\right)$

The public sample complexity is,

$\displaystyle{n_{\text{pub}}}=\tilde{O}\left({\frac{(HD\left\|{{\mathcal{X}}}\right\|)^{2/3}({n_{\text{priv}}}\epsilon)^{2/3}}{G^{2/3}(\operatorname{log}\left(1/\delta\right))^{1/3}}}\right).$

The second part follows similarly.

∎

###  C.3 Lower bounds

####  C.3.1 Proof of Theorem 5

To establish the $\frac{GD\left\|{{\mathcal{X}}}\right\|}{\sqrt{n}}$ term in
the lower bound, we consider a one-dimenisonal problem where the loss
$\phi_{y}(\widehat{y})=-Gy\widehat{y}$ and marginal distribution
${\mathcal{D}}_{x}$ as the point distribution on $\|{\mathcal{X}}\|$ such that
the overall loss is
$\underset{x,y}{\mathbb{E}}\left[\ell(w,(x,y))\right]=\underset{y}{\mathbb{E}}\left[y\cdot
w\|{\mathcal{X}}\|G\right]$. We further set ${\mathcal{W}}=[-D,D]$ and
consider ${\mathcal{D}}_{y}$ to be the distribution which as $1$ with
probability $\mathbb{P}\left[{y=1}\right]=(1+\mu)/2$ and
$\mathbb{P}\left[{y=1}\right]=(1-\mu)/2$ for some $\mu\in[-1,1]$. Note the
minimizer $w^{*}=D\frac{\mu}{|\mu|}$ achieves population risk $-\mu
GD\|{\mathcal{X}}\|$. Classic results in information theory establish if $\mu$
is sampled uniformly from $\\{\pm\frac{1}{\sqrt{6n}}\\}$, no algorithm can
estimate the sign of $\mu$ with probability better than $1/2$ (see [22,
Section 8.3]). Thus it must be that for any algorithm
$\mathbb{E}_{{\mathcal{A}},S}\left[L({\mathcal{A}}(S);{\mathcal{D}})-\min_{w\in\mathbb{R}^{d}}L(w;{\mathcal{D}})\right]=\Omega\left({\frac{GD\left\|{{\mathcal{X}}}\right\|}{\sqrt{n}}}\right).$

The
$GD\left\|{{\mathcal{X}}}\right\|\min\left\\{{\frac{1}{\sqrt{n\epsilon}},\frac{\sqrt{d}}{n\epsilon}}\right\\}$
term in the lower bound is essentially a corollary of [2, Theorem 6]. We
provide further remarks here. The loss function used is,

$\displaystyle\ell(w;(x,y))=\phi_{y}(\left\langle{w},{x}\right\rangle)=\left|{y-\left\langle{w},{x}\right\rangle}\right|.$

Define $d^{\prime}:=\min(d,n\epsilon)$ and
$p:=\min\left({1,\frac{d^{\prime}}{n\epsilon}}\right)$. The (known) marginal
distribution ${\mathcal{D}}_{{\mathcal{X}}}$ is described as: with probability
$1-p$, $x=\vec{0}$, otherwise,
$x\sim\text{Unif}\left({\left\|{{\mathcal{X}}}\right\|\left\\{{e_{j}}\right\\}_{j=1}^{d^{\prime}}}\right)$
where $e_{j}$’s are canonical basis vectors. The (unknown) conditional
distribution of the response $y$ is as follows. Sample a “fingerprinting
code”, $z^{\prime}\in\left\\{{0,1}\right\\}^{d^{\prime}}$ with mean
$\mu^{\prime}\in[0,1]^{d^{\prime}}$ where each co-ordinate
$\mu^{\prime}_{j}\sim\text{Beta}(0.0625,0.0625)$ i.i.d. Embed $z^{\prime}$ in
$d$ dimensions as $z$ and let $\mu$ be the corresponding mean vector. Finally,
define $y=\frac{D\left\langle{z},{x}\right\rangle}{\sqrt{{d^{\prime}}}}$. The
proof in [2, Theorem 6] then proceeds by lower bounding the loss by bounding
the ability of any differential private algorithm to estimate the
fingerprinting code $z$.

Since the rank of
$\underset{x\sim{\mathcal{D}}_{\mathcal{X}}}{\mathbb{E}}\left[xx^{\top}\right]=d^{\prime}$,
the result [2, Theorem 6] then yields a lower bound on the unconstrained
excess risk,

$\mathbb{E}_{{\mathcal{A}},S}\left[L({\mathcal{A}}(S);{\mathcal{D}})-\min_{w\in\mathbb{R}^{d}}L(w;{\mathcal{D}})\right]=\Omega\left({GD\left\|{{\mathcal{X}}}\right\|\min\left\\{{\frac{1}{\sqrt{n\epsilon}},\frac{\sqrt{d}}{n\epsilon}}\right\\}}\right),$

but also guarantees that the global minimizer has norm at most $D$. Thus, we
achieve the same lower bound for
$\mathbb{E}_{{\mathcal{A}},S}\left[L({\mathcal{A}}(S);{\mathcal{D}})-\min_{w\in{\mathcal{W}}}L(w;{\mathcal{D}})\right]$
by setting ${\mathcal{W}}$ to be the ball of radius $D$.

####  C.3.2 Proof of theorem 6

The proof uses the lower bound instance in the DP-SCO lower bound with public
data, theorem 1. We consider the case where ${\mathcal{D}}_{y}$ is the point
distribution on $1$. Then for any $y\in{\mathcal{Y}}$,
${\mathcal{Y}}=\left\\{{1}\right\\}$, the loss function is then
$\ell(w;(x,y))=y\left\langle{w},{x}\right\rangle=\left\langle{w},{x}\right\rangle$,
as in Theorem 1. Hence, a labeled and unlabeled sample have the same
information. We also set ${\mathcal{W}}$ to be the ball of radius $D$.

Assume by contradiction there exists an $(\epsilon,\delta)$-PA-DP algorithm,
${\mathcal{A}}$, which achieves rate
$O\left({GD\|{\mathcal{X}}\|(\frac{1}{\sqrt{{n_{\text{priv}}}}}+\frac{\sqrt{\operatorname{log}\left(1/\delta\right)}}{\sqrt{{n_{\text{priv}}}\epsilon}})}\right)$
with $o({n_{\text{priv}}}\epsilon/\operatorname{log}\left(1/\delta\right))$
public samples. Since
${n_{\text{pub}}}=o({n_{\text{priv}}}\epsilon/\operatorname{log}\left(1/\delta\right))$
and $d=\omega(n\epsilon)$, Theorem 1 gives a lower bound on
$\underset{}{\mathbb{E}}\left[{\mathcal{A}}(X_{\text{pub}},S_{\text{priv}};{\mathcal{D}})-\min_{w\in{\mathcal{W}}}\left\\{{L(w;{\mathcal{D}})}\right\\}\right]$
of

$\displaystyle\Omega\left({GD\|{\mathcal{X}}\|\min\left\\{{\frac{1}{\sqrt{{n_{\text{pub}}}}},\frac{\sqrt{d\operatorname{log}\left(1/\delta\right)}}{{n_{\text{priv}}}\epsilon}}\right\\}}\right)=\omega\left({GD\|{\mathcal{X}}\|\frac{\sqrt{\operatorname{log}\left(1/\delta\right)}}{\sqrt{{n_{\text{priv}}}\epsilon}}}\right).$

Since $\epsilon\leq 1$, this is a contradiction.

##  Appendix D Missing proofs for section 4.2

###  D.1 Proof of theorem 8

###### Proof.

The privacy proof follows from the guarantee of exponential mechanism [34]. In
particular, the sensitivity of the score function is at most
$\frac{2}{{n_{\text{priv}}}}\min{\left({B,GR}\right)}$ where the first follows
from the loss bound of $B$ and the second from the Lipschitzness and bound on
predictors. Let
$h^{*}\in\mathop{\arg\min}_{h\in{\mathcal{H}}}L(h;{\mathcal{D}})$ and
$\tilde{h}^{*}\in\mathop{\arg\min}_{h\in\tilde{\mathcal{H}}}L(h;{\mathcal{D}})$.
From standard analysis based on uniform convergence, we have

$\displaystyle L(\widehat{h};{\mathcal{D}})-L(h^{*};{\mathcal{D}})$
$\displaystyle=L(\widehat{h};{\mathcal{D}})-\widehat{L}(\widehat{h};S_{\text{priv}})+\widehat{L}(\widehat{h};S_{\text{priv}})-L(h^{*};{\mathcal{D}})$
$\displaystyle\leq\sup_{h\in{\mathcal{H}}}\left({L(h;{\mathcal{D}})-\widehat{L}(h;S_{\text{priv}})}\right)+L(\tilde{h}^{*};{\mathcal{D}})-L(h^{*};{\mathcal{D}})$
$\displaystyle+\widehat{L}(\tilde{h}^{*};S_{\text{priv}})-L(\tilde{h}^{*};{\mathcal{D}})+\widehat{L}(\widehat{h};S_{\text{priv}})-\widehat{L}(\tilde{h}^{*};S_{\text{priv}})$
(17) $\displaystyle\leq
2\sup_{h\in{\mathcal{H}}}\left|{L(h;{\mathcal{D}})-\widehat{L}(h;S_{\text{priv}})}\right|+L(\tilde{h}^{*};{\mathcal{D}})-L(h^{*};{\mathcal{D}})$
$\displaystyle+\widehat{L}(\widehat{h};S_{\text{priv}})-\min_{h\in\tilde{\mathcal{H}}}\widehat{L}(h;S_{\text{priv}})$
(18) $\displaystyle\leq
2G\mathfrak{R}_{{n_{\text{priv}}}}({\mathcal{H}})+O\left({\frac{B\sqrt{\operatorname{log}\left(4/\beta\right)}}{\sqrt{{n_{\text{priv}}}}}}\right)$
$\displaystyle+O\left({\frac{\min{(B,GR)}(\operatorname{log}\left(|\tilde{\mathcal{H}}|\right)+\operatorname{log}\left(4/\beta\right))}{{n_{\text{priv}}}\epsilon}}\right)+L(\tilde{h}^{*};{\mathcal{D}})-L(h^{*};{\mathcal{D}})$
(19)

where the above holds with probability at least $1-\beta/2$ and follows from
guarantee of exponential mechanism [34] and uniform convergence ([42], see
theorem 17). We further have that
$\operatorname{log}\left(|\tilde{\mathcal{H}}|\right)=\tilde{O}(\text{fat}_{c\alpha}({\mathcal{H}}))$
from lemma 7.

For the $L(\tilde{h}^{*};{\mathcal{D}})-L(h^{*};{\mathcal{D}})$ term, we have

$\displaystyle L(\tilde{h}^{*};{\mathcal{D}})-L(h^{*};{\mathcal{D}})$
$\displaystyle\leq L(\bar{h}^{*};{\mathcal{D}})-L(h^{*};{\mathcal{D}})$
$\displaystyle\leq G\mathbb{E}{\left|{\bar{h}^{*}(x)-h^{*}(x)}\right|}$
$\displaystyle\leq
G\sqrt{\mathbb{E}{\left|{\bar{h}^{*}(x)-h^{*}(x)}\right|^{2}}}$
$\displaystyle\leq 2G\alpha$

where the first step holds for any $\bar{h}^{*}\in\tilde{\mathcal{H}}$ by
optimaility of $\tilde{h}^{*}$ over $\tilde{\mathcal{H}}$, the second holds
from the $G$-Lipschitzness of the loss function, the third from Jensen’s
inequality. The final step holds with probability $1-\beta/2$ from lemma 1
with
${n_{\text{pub}}}=O\left({\max\left({\frac{R^{2}\operatorname{log}\left(2/\beta\right)}{\alpha^{2}},\min\left\\{{m:\text{log}^{3}(m)\mathfrak{R}_{m}^{2}({\mathcal{H}})\leq\alpha^{2}}\right\\}}\right)}\right)$
together with the fact that since $\tilde{\mathcal{H}}$ is an $\alpha$-cover
of ${\mathcal{H}}$, hence there exists $\bar{h}^{*}\in\tilde{\mathcal{H}}$
with $\left\|{\bar{h}^{*}-h^{*}}\right\|_{2,X_{\text{pub}}}\leq\alpha$.

Plugging the above in eq. 19, we get with probability at least $1-\beta$,

$\displaystyle L(\widehat{h};{\mathcal{D}})-L(h^{*};{\mathcal{D}})$
$\displaystyle\leq
2G\mathfrak{R}_{{n_{\text{priv}}}}({\mathcal{H}})+O\left({\frac{B\sqrt{\operatorname{log}\left(4/\beta\right)}}{\sqrt{{n_{\text{priv}}}}}}\right)$
$\displaystyle+O\left({\frac{\min{(B,GR)}(\text{fat}_{c\alpha}({\mathcal{H}})+\operatorname{log}\left(4/\beta\right))}{{n_{\text{priv}}}\epsilon}}\right)+2G\alpha,$

which finishes the proof. ∎

######  Theorem 17.

[42] Let ${\mathcal{H}}\subseteq[-R,R]^{{\mathcal{X}}}$. For any
$G$-Lipschitz, $B$-bounded loss function, any probability distribution
${\mathcal{D}}$ over ${\mathcal{X}}\times{\mathcal{Y}}$, given $m$ i.i.d.
samples from $S$, with probability at least $1-\beta$, the following holds for
all $h\in{\mathcal{H}}$,

$\displaystyle\left|{L(h;{\mathcal{D}})-\widehat{L}(h;S)}\right|\leq
2G\mathfrak{R}_{m}({\mathcal{H}})+O\left({B\sqrt{\frac{\operatorname{log}\left(4/\beta\right)}{m}}}\right)$

###### Proof.

This is a classical result in learning theory which follows directly Theorem
26.5 in [42] together with the contraction lemma (Lemma 26.9 in [42]) for
Lipschitz losses. ∎

######  Lemma 7.

Let $\tilde{\mathcal{H}}$ be an $\alpha$-cover of ${\mathcal{H}}$ with respect
to $\left\|{\cdot}\right\|_{2,X_{\text{pub}}}$. The size of
$\tilde{\mathcal{H}}$ is bounded as,

$\displaystyle\operatorname{log}\left(\left|{\tilde{\mathcal{H}}}\right|\right)\leq\text{fat}_{c\alpha}({\mathcal{H}})\operatorname{log}\left(\frac{2R}{\alpha}\right)$

where $c$ is an absolute constant.

###### Proof.

This follows directly from theorem 10,

$\displaystyle\operatorname{log}\left(\left|{\tilde{\mathcal{H}}}\right|\right)={\mathcal{N}}_{2}\left({{\mathcal{H}},\alpha,S_{\text{pub}}}\right)\leq{\mathcal{N}}_{2}\left({{\mathcal{H}},\alpha,{n_{\text{pub}}}}\right)\leq\text{fat}_{c\alpha}({\mathcal{H}})\operatorname{log}\left(\frac{2R}{\alpha}\right).$

∎

##### Proof of Lemma 1

For $h\in{\mathcal{H}}$, let
$\tilde{h}\in\mathop{\arg\min}_{\bar{h}\in\tilde{\mathcal{H}}}\|\bar{h}-h\|_{2,X_{\text{pub}}}$.
Since $\tilde{\mathcal{H}}$ is an $\tau$-cover, this gives us that
$\|h-\tilde{h}\|_{2,X_{\text{pub}}}\leq\tau$. We have,

$\displaystyle\|h-\tilde{h}\|_{2,{\mathcal{D}}_{\mathcal{X}}}^{2}$
$\displaystyle=\mathbb{E}\left|{h(x)-\tilde{h}(x)}\right|^{2}$
$\displaystyle=\mathbb{E}\left|{h(x)-\tilde{h}(x)}\right|^{2}-\frac{1}{{n_{\text{pub}}}}\sum_{x\in
S_{\text{pub}}}\left|{h(x)-\tilde{h}(x)}\right|^{2}+\frac{1}{{n_{\text{pub}}}}\sum_{x\in
S_{\text{pub}}}\left|{h(x)-\tilde{h}(x)}\right|^{2}$
$\displaystyle\leq\sup_{\bar{h}\in{\mathcal{H}}}\left({\mathbb{E}\left|{h(x)-\bar{h}(x)}\right|^{2}-\frac{1}{{n_{\text{pub}}}}\sum_{x\in
S_{\text{pub}}}\left|{h(x)-\bar{h}(x)}\right|^{2}}\right)+\tau^{2}.$

The first term above can be seen as uniform deviation between the empirical
and population risk, of another prediction problem, with squared loss, in the
the realizable setting (with the responses generated by $h$). The squared loss
is $\frac{1}{2}$-smooth and non-negative, so we can apply result of Theorem 1
in [43] instantiated in the realizable setting, which gives us that with
probability at least $1-\beta$,

$\displaystyle\|h-\tilde{h}\|_{2.{\mathcal{D}}_{\mathcal{X}}}^{2}=O\left({\text{log}^{3}({n_{\text{pub}}})\mathfrak{R}_{{n_{\text{pub}}}}^{2}({\mathcal{H}})+\frac{R^{2}\operatorname{log}\left(1/\beta\right)}{{n_{\text{pub}}}}}\right)+\tau^{2}.$

Choosing ${n_{\text{pub}}}$ such that
${n_{\text{pub}}}=O\left({\max\left({\frac{R^{2}\operatorname{log}\left(1/\beta\right)}{\alpha^{2}},\min\left\\{{m:\text{log}^{3}(m)\mathfrak{R}_{m}^{2}({\mathcal{H}})\leq\alpha^{2}}\right\\}}\right)}\right)$,
we get the claimed result.

###  D.2 Proof of theorem 9

We present the full statement of the theorem.

######  Theorem 18.

Algorithm 2 with $\gamma=\frac{2B}{{n_{\text{priv}}}\epsilon}$ satisfies
$\epsilon$-PA-DP. For
${n_{\text{pub}}}=O\left({\max\left({\frac{R^{2}\operatorname{log}\left(2/\beta\right)}{\alpha^{2}},\min\left\\{{m:\text{log}^{3}(m)\mathfrak{R}_{m}^{2}({\mathcal{H}})\leq\alpha^{2}}\right\\}}\right)}\right)<\infty$
and any $\alpha>0$, with probability at least $1-\beta$, we have

$\displaystyle L(\widehat{h};{\mathcal{D}})-L(h^{*};{\mathcal{D}})$
$\displaystyle=\tilde{O}\left({\sqrt{H}\mathfrak{R}_{{n_{\text{priv}}}}({\mathcal{H}})+\sqrt{H}\alpha+\sqrt{\frac{B\operatorname{log}\left(8/\delta\right)}{{n_{\text{priv}}}}}}\right)\sqrt{L(h^{*};{\mathcal{D}})}$
$\displaystyle+\tilde{O}\left({H\mathfrak{R}^{2}_{{n_{\text{priv}}}}({\mathcal{H}})+H\alpha^{2}+\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}+\frac{B(\text{fat}_{c\alpha}({\mathcal{H}})+\operatorname{log}\left(4/\beta\right))}{{n_{\text{priv}}}\epsilon}}\right)$
$\displaystyle
L(\widehat{h};{\mathcal{D}})-\widehat{L}(\widehat{h}^{*};S_{\text{priv}})$
$\displaystyle\leq\tilde{O}\left({\sqrt{H}\mathfrak{R}_{{n_{\text{priv}}}}({\mathcal{H}})+\sqrt{H}\alpha+\sqrt{\frac{B\operatorname{log}\left(8/\delta\right)}{{n_{\text{priv}}}}}}\right)\sqrt{\widehat{L}(\widehat{h}^{*};S_{\text{priv}})}$
$\displaystyle+\tilde{O}\left({H\mathfrak{R}^{2}_{{n_{\text{priv}}}}({\mathcal{H}})+H\alpha^{2}+\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}+\frac{B(\text{fat}_{c\alpha}({\mathcal{H}})+\operatorname{log}\left(4/\beta\right))}{{n_{\text{priv}}}\epsilon}}\right)$

where $h^{*}$ and $\widehat{h}^{*}$ are population and empirical minimizers
with respect to ${\mathcal{D}}$ and $S_{\text{priv}}$ respectively, and $c$ is
an absolute constant.

###### Proof of theorem 18.

The privacy proof is the same as that of theorem 8. For utility, let
$h^{*}\in\mathop{\arg\min}_{h\in{\mathcal{H}}}L(h;{\mathcal{D}})$ and
$\tilde{h}^{*}\in\mathop{\arg\min}_{h\in\tilde{\mathcal{H}}}L(h;{\mathcal{D}})$.

We start with the proof of the first part of the theorem. We have,

$\displaystyle L(\widehat{h};{\mathcal{D}})-L(h^{*};{\mathcal{D}})$
$\displaystyle=L(\widehat{h};{\mathcal{D}})-\widehat{L}(\widehat{h};S_{\text{priv}})+\widehat{L}(\widehat{h};S_{\text{priv}})-L(h^{*};{\mathcal{D}})$
$\displaystyle\leq
L(\widehat{h};{\mathcal{D}})-\widehat{L}(\widehat{h};S_{\text{priv}})+\widehat{L}(\tilde{h}^{*};S_{\text{priv}})-L(\tilde{h}^{*};{\mathcal{D}})$
$\displaystyle+L(\tilde{h}^{*};{\mathcal{D}})-L(h^{*};{\mathcal{D}})+\widehat{L}(\widehat{h};S_{\text{priv}})-\widehat{L}(\tilde{h}^{*};S_{\text{priv}})$
$\displaystyle\leq\left|{L(\widehat{h};{\mathcal{D}})-\widehat{L}(\widehat{h};S_{\text{priv}})}\right|+\left|{L(\tilde{h}^{*};{\mathcal{D}})-\widehat{L}(\tilde{h}^{*};S_{\text{priv}})}\right|$
$\displaystyle+L(\tilde{h}^{*};{\mathcal{D}})-L(h^{*};{\mathcal{D}})+\widehat{L}(\widehat{h};S_{\text{priv}})-\widehat{L}(\tilde{h}^{*};S_{\text{priv}})$
(20)

From the guarantee of exponential mechanism together with
$\operatorname{log}\left(\left|{\tilde{\mathcal{H}}}\right|\right)=\tilde{O}(\text{fat}_{c\alpha}({\mathcal{H}}))$
from lemma 7, we have that with probability at least $1-\beta/4$,

$\displaystyle\widehat{L}(\widehat{h};S_{\text{priv}})-\widehat{L}(\tilde{h}^{*};S_{\text{priv}})$
$\displaystyle\leq\widehat{L}(\widehat{h};S_{\text{priv}})-\min_{h\in\tilde{\mathcal{H}}}\widehat{L}(h;S_{\text{priv}})=O\left({\frac{{B}(\operatorname{log}\left(\left|{\tilde{\mathcal{H}}}\right|\right)+\operatorname{log}\left(4/\beta\right))}{{n_{\text{priv}}}\epsilon}}\right)$
$\displaystyle=\tilde{O}\left({\frac{{B}(\text{fat}_{c\alpha}({\mathcal{H}})+\operatorname{log}\left(4/\beta\right))}{{n_{\text{priv}}}\epsilon}}\right)$
(21)

For the $L(\tilde{h}^{*};{\mathcal{D}})-L(h^{*};{\mathcal{D}})$ term in eq.
20, we apply smoothness to get,

$\displaystyle L(\tilde{h}^{*};{\mathcal{D}})-L(h^{*};{\mathcal{D}})$
$\displaystyle\leq L(\bar{h}^{*};{\mathcal{D}})-L(h^{*};{\mathcal{D}})$
$\displaystyle\leq\mathbb{E}\left[\left\langle{\phi_{y}^{\prime}(h^{*}(x))},{\bar{h}^{*}(x)-h^{*}(x)}\right\rangle+\frac{H}{2}\left|{\bar{h}^{*}(x)-h^{*}(x)}\right|^{2}\right]$
$\displaystyle\leq\mathbb{E}\left[\left|{\phi_{y}^{\prime}(h^{*}(x))}\right|\left|{\bar{h}^{*}(x)-h^{*}(x)}\right|+\frac{H}{2}\left|{\bar{h}^{*}(x)-h^{*}(x)}\right|^{2}\right]$
$\displaystyle\leq\sqrt{\mathbb{E}\left|{\phi_{y}^{\prime}(h^{*}(x))}\right|^{2}}\sqrt{\mathbb{E}_{x\sim{\mathcal{D}}_{{\mathcal{X}}}}\left|{\bar{h}^{*}(x)-h^{*}(x)}\right|^{2}}+\frac{H}{2}\mathbb{E}_{x\sim{\mathcal{D}}_{{\mathcal{X}}}}\left|{\bar{h}^{*}(x)-h^{*}(x)}\right|^{2}$
$\displaystyle\leq
2\sqrt{H\mathbb{E}_{x\sim{\mathcal{D}}}\phi_{y}(h^{*}(x))}\sqrt{\mathbb{E}\left|{\bar{h}^{*}(x)-h^{*}(x)}\right|^{2}}+\frac{H}{2}\mathbb{E}_{x\sim{\mathcal{D}}_{{\mathcal{X}}}}\left|{\bar{h}^{*}(x)-h^{*}(x)}\right|^{2}$
$\displaystyle\leq 2\sqrt{HL(h^{*};{\mathcal{D}})}\alpha+H\alpha^{2}$ (22)

where the above holds for any $\bar{h}^{*}\in\tilde{\mathcal{H}}$. The second
inequality holds from $H$-smoothness, the third and fourth from Cauchy-
Schwarz, the fifth from self-bounding property of smooth non-negative losses
[43]. The final step holds with probability $1-\beta/2$ from lemma 1 with
${n_{\text{pub}}}=O\left({\max\left({\frac{R^{2}\operatorname{log}\left(2/\beta\right)}{\alpha^{2}},\min\left\\{{m:\text{log}^{3}(m)\mathfrak{R}_{m}^{2}({\mathcal{H}})\leq\alpha^{2}}\right\\}}\right)}\right)$
together with the fact that since $\tilde{\mathcal{H}}$ is an $\alpha$-cover
of ${\mathcal{H}}$, so there exists $\bar{h}^{*}\in\tilde{\mathcal{H}}$ with
$\left\|{\bar{h}^{*}-h^{*}}\right\|_{2,X_{\text{pub}}}\leq\alpha$.

An application of AM-GM inequality further yields,

$\displaystyle L(\tilde{h}^{*};{\mathcal{D}})\leq
2L(h^{*};{\mathcal{D}})+2H\alpha^{2}$ (23)

The first two terms in eq. 20 are bound using uniform convergence for smooth
non-negative losses, Theorem 1 in [43] and Bernstein’s inequality as follows;
with probability at least $1-\beta/4$, we have,

$\displaystyle\left|{L(\widehat{h};{\mathcal{D}})-\widehat{L}(\widehat{h};S_{\text{priv}})}\right|+\left|{L(\tilde{h}^{*};{\mathcal{D}})-\widehat{L}(\tilde{h}^{*};S_{\text{priv}})}\right|$
$\displaystyle=\tilde{O}{\left({\sqrt{H}\mathfrak{R}_{{n_{\text{priv}}}}({\mathcal{H}})+\sqrt{\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}}\right)\left({\sqrt{\widehat{L}(\widehat{h};S_{\text{priv}})}+\sqrt{L(\tilde{h}^{*};{\mathcal{D}})}}\right)}$
$\displaystyle+\tilde{O}\left({\mathfrak{R}_{{n_{\text{priv}}}}({\mathcal{H}})^{2}+\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}\right)$
$\displaystyle=\tilde{O}{\left({\sqrt{H}\mathfrak{R}_{{n_{\text{priv}}}}({\mathcal{H}})+\sqrt{\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}}\right)\left({\sqrt{\widehat{L}(\tilde{h}^{*};S_{\text{priv}})}+\sqrt{L(\tilde{h}^{*};{\mathcal{D}})}}\right)}$
$\displaystyle+\tilde{O}\left({H\mathfrak{R}_{{n_{\text{priv}}}}({\mathcal{H}})^{2}+\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}\right)+\tilde{O}\left({\frac{{B}(\text{fat}_{c\alpha}({\mathcal{H}})+\operatorname{log}\left(4/\beta\right))}{{n_{\text{priv}}}\epsilon}}\right)$
$\displaystyle=\tilde{O}{\left({\sqrt{H}\mathfrak{R}_{{n_{\text{priv}}}}({\mathcal{H}})+\sqrt{\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}}\right)\sqrt{L(\tilde{h}^{*};{\mathcal{D}})}}$
$\displaystyle+\tilde{O}\left({H\mathfrak{R}_{{n_{\text{priv}}}}({\mathcal{H}})^{2}+\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}\right)+\tilde{O}\left({\frac{{B}(\text{fat}_{c\alpha}({\mathcal{H}})+\operatorname{log}\left(4/\beta\right))}{{n_{\text{priv}}}\epsilon}}\right)$
$\displaystyle=\tilde{O}{\left({\sqrt{H}\mathfrak{R}_{{n_{\text{priv}}}}({\mathcal{H}})+\sqrt{\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}}\right)\sqrt{L(h^{*};{\mathcal{D}})}}$
$\displaystyle+\tilde{O}\left({H\mathfrak{R}_{{n_{\text{priv}}}}({\mathcal{H}})^{2}+\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}\right)+\tilde{O}\left({\frac{{B}(\text{fat}_{c\alpha}({\mathcal{H}})+\operatorname{log}\left(8/\beta\right))}{{n_{\text{priv}}}\epsilon}}\right)$

where the second equality follows from eq. 21, concavity of $x\mapsto\sqrt{x}$
and AM-GM inequality. The third equality follows concavity of
$x\mapsto\sqrt{x}$ and Bernstein’s inequality, the fourth follows from eq. 23
and AM-GM inequality.

Plugging the above, eq. 22 and eq. 21 into eq. 20 yields the following with
probability at least $1-\beta$,

$\displaystyle L(\widehat{h};{\mathcal{D}})-L(h^{*};{\mathcal{D}})$
$\displaystyle=\tilde{O}\left({\sqrt{H}\mathfrak{R}_{{n_{\text{priv}}}}({\mathcal{H}})+\sqrt{H}\alpha+\sqrt{\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}}\right)\sqrt{L(h^{*};{\mathcal{D}})}$
(24)
$\displaystyle+\tilde{O}\left({H\mathfrak{R}^{2}_{{n_{\text{priv}}}}({\mathcal{H}})+H\alpha^{2}+\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}+\frac{B(\text{fat}_{c\alpha}({\mathcal{H}})+\operatorname{log}\left(4/\beta\right))}{{n_{\text{priv}}}\epsilon}}\right)$
(25)

This completes the first part of the theorem. For the second part, we proceed
from eq. 25 onwards

$\displaystyle L(\widehat{h};{\mathcal{D}})$ $\displaystyle\leq
L(h^{*};{\mathcal{D}})+\tilde{O}\left({\sqrt{H}\mathfrak{R}_{{n_{\text{priv}}}}({\mathcal{H}})+\sqrt{H}\alpha+\sqrt{\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}}\right)\sqrt{L(h^{*};{\mathcal{D}})}$
$\displaystyle+\tilde{O}\left({H\mathfrak{R}^{2}_{{n_{\text{priv}}}}({\mathcal{H}})+H\alpha^{2}+\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}+\frac{B(\text{fat}_{c\alpha}({\mathcal{H}})+\operatorname{log}\left(4/\beta\right))}{{n_{\text{priv}}}\epsilon}}\right)$
$\displaystyle\leq
L(\widehat{h}^{*};{\mathcal{D}})+\tilde{O}\left({\sqrt{H}\mathfrak{R}_{{n_{\text{priv}}}}({\mathcal{H}})+\sqrt{H}\alpha+\sqrt{\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}}\right)\sqrt{L(\widehat{h}^{*};{\mathcal{D}})}$
$\displaystyle+\tilde{O}\left({H\mathfrak{R}^{2}_{{n_{\text{priv}}}}({\mathcal{H}})+H\alpha^{2}+\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}+\frac{B(\text{fat}_{c\alpha}({\mathcal{H}})+\operatorname{log}\left(4/\beta\right))}{{n_{\text{priv}}}\epsilon}}\right)$
$\displaystyle\leq\widehat{L}(\widehat{h}^{*};S_{\text{priv}})+\tilde{O}\left({\sqrt{H}\mathfrak{R}_{{n_{\text{priv}}}}({\mathcal{H}})+\sqrt{H}\alpha+\sqrt{\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}}}\right)\sqrt{\widehat{L}(\widehat{h}^{*};S_{\text{priv}})}$
$\displaystyle+\tilde{O}\left({H\mathfrak{R}^{2}_{{n_{\text{priv}}}}({\mathcal{H}})+H\alpha^{2}+\frac{B\operatorname{log}\left(8/\beta\right)}{{n_{\text{priv}}}}+\frac{B(\text{fat}_{c\alpha}({\mathcal{H}})+\operatorname{log}\left(4/\beta\right))}{{n_{\text{priv}}}\epsilon}}\right)$

where the second inequality follows form optimality of $h^{*}$, the third from
uniform convergence, Theorem 1 in [43] and AM-GM inequality. This completes
the proof.

∎

###  D.3 Proof of LABEL:{cor:dp-public-data-nn}

We use the result from [27], restated as theorem 12. Further, note that range
bound on the hypothesis class is simply
$R\leq\left\|{{\mathcal{X}}}\right\|\prod_{j=1}^{d}R_{j}$. Instantiating our
general result theorem 8 with the above together with the relation between
fat-shattering dimension and Rademacher complexity (theorem 11) yields the
following excess risk bound,

$\displaystyle
L(\widehat{h};{\mathcal{D}})-\min_{h\in{\mathcal{H}}}L(h;{\mathcal{D}})$
$\displaystyle=O\left({\frac{G\left\|{{\mathcal{X}}}\right\|(\sqrt{2\operatorname{log}\left(2\right)0pt}+1)\prod_{j=1}^{0}ptR_{j}}{\sqrt{{n_{\text{priv}}}}}+\frac{B\sqrt{\operatorname{log}\left(4/\beta\right)}}{\sqrt{{n_{\text{priv}}}}}+\frac{B\operatorname{log}\left(4/\beta\right)}{{n_{\text{priv}}}\epsilon}}\right)$
$\displaystyle+\tilde{O}\left({\left({\frac{BG^{2}(\sqrt{2\operatorname{log}\left(2\right)0pt}+1)^{2}\left\|{{\mathcal{X}}}\right\|^{2}(\prod_{j=1}^{0pt}R_{j})^{2}}{{n_{\text{priv}}}\epsilon}}\right)^{1/3}}\right).$

where in the above, we set
$\alpha=\left({\frac{B(\sqrt{2\operatorname{log}\left(2\right)0pt}+1)^{2}\left\|{{\mathcal{X}}}\right\|^{2}(\prod_{j=1}^{0}ptR_{j})^{2}}{G{n_{\text{priv}}}\epsilon}}\right)^{1/3}$.

The number of public samples then is

$\displaystyle{n_{\text{pub}}}$
$\displaystyle=O\left({\max\left({\frac{R^{2}\operatorname{log}\left(2/\beta\right)}{\alpha^{2}},\min\left\\{{m:\text{log}^{3}(m)\mathfrak{R}_{m}^{2}({\mathcal{H}})\leq\alpha^{2}}\right\\}}\right)}\right)$
$\displaystyle=\tilde{O}\left({\left\|{{\mathcal{X}}}\right\|^{2}(\prod_{j=1}^{0}ptR_{j})^{2}\max\left({\frac{\operatorname{log}\left(2/\beta\right)}{\alpha^{2}},\frac{0pt}{\alpha^{2}}}\right)}\right)$
$\displaystyle=\tilde{O}\left({(\left\|{{\mathcal{X}}}\right\|(\prod_{j=1}^{0}ptR_{j}))^{2/3}({n_{\text{priv}}}\epsilon)^{2/3}0pt^{1/3}\operatorname{log}\left(2/\beta\right)}\right).$

###  D.4 Proof of corollary 3

Note that $R\leq D\left\|{{\mathcal{X}}}\right\|$. Further, we have [30, 23],

$\displaystyle\mathfrak{R}_{m}({\mathcal{H}})=O\left({\frac{D\left\|{{\mathcal{X}}}\right\|}{m^{1/r}}}\right).$

Moreover, we have from theorem 11, for any
$\alpha>\mathfrak{R}_{m}({\mathcal{H}})$,

$\displaystyle\text{fat}_{\alpha}({\mathcal{H}})\leq\frac{4m\mathfrak{R}_{m}^{2}({\mathcal{H}})}{\alpha^{2}}.$

Choose $m={n_{\text{pub}}}$ and
$\alpha=\left({\operatorname{log}\left({n_{\text{pub}}}\right)}\right)^{3/2}\mathfrak{R}_{{n_{\text{pub}}}}({\mathcal{H}})$,
to get that
$\text{fat}_{\alpha}({\mathcal{H}})=\tilde{O}\left({{n_{\text{pub}}}}\right)$.
Plugging this in theorem 8, we get,

$\displaystyle
L(\widehat{w};{\mathcal{D}})-\min_{w\in{\mathcal{W}}}L(w;{\mathcal{D}})$
$\displaystyle=O\left({\frac{GD\left\|{{\mathcal{X}}}\right\|}{{n_{\text{priv}}}^{1/r}}+\frac{GD\left\|{{\mathcal{X}}}\right\|\sqrt{\operatorname{log}\left(4/\beta\right)}}{\sqrt{{n_{\text{priv}}}}}+\frac{B\sqrt{\operatorname{log}\left(4/\beta\right)}}{\sqrt{{n_{\text{priv}}}}}}\right)$
$\displaystyle+\tilde{O}\left({GD\left\|{{\mathcal{X}}}\right\|\left({\frac{{n_{\text{pub}}}}{{n_{\text{priv}}}\epsilon}+\frac{1}{{n_{\text{pub}}}^{1/r}}+\frac{\operatorname{log}\left(4/\beta\right)}{{n_{\text{priv}}}\epsilon}}\right)}\right)$
$\displaystyle=\tilde{O}\left({GD\left\|{{\mathcal{X}}}\right\|\left({\frac{1}{{n_{\text{priv}}}^{1/r}}+\frac{\sqrt{\operatorname{log}\left(4/\beta\right)}}{\sqrt{{n_{\text{priv}}}}}+\frac{\operatorname{log}\left(2/\beta\right)}{({n_{\text{priv}}}\epsilon)^{\frac{1}{r+1}}}+\frac{\operatorname{log}\left(4/\beta\right)}{{n_{\text{priv}}}\epsilon}}\right)}\right)$
$\displaystyle+O\left({\frac{B\sqrt{\operatorname{log}\left(4/\beta\right)}}{\sqrt{{n_{\text{priv}}}}}}\right),$

where in the last step, we plug in
${n_{\text{pub}}}=O\left({({n_{\text{priv}}}\epsilon)^{r/(1+r)}\operatorname{log}\left(2/\beta\right)}\right)$,
yielding
$\alpha=O\left({\frac{D\left\|{{\mathcal{X}}}\right\|}{({n_{\text{priv}}}\epsilon)^{\frac{1}{r+1}}}}\right)$.
The number of public samples simplifies as,

$\displaystyle{n_{\text{pub}}}$
$\displaystyle=O\left({\max\left({\frac{R^{2}\operatorname{log}\left(2/\beta\right)}{\alpha^{2}},\min\left\\{{m:\text{log}^{3}(m)\mathfrak{R}_{m}^{2}({\mathcal{H}})\leq\alpha^{2}}\right\\}}\right)}\right)$
$\displaystyle=\tilde{O}\left({({n_{\text{priv}}}\epsilon)^{\frac{2}{r+1}}\operatorname{log}\left(2/\beta\right)}\right).$

which is satisfied from our choice since $r\geq 2$.

###  D.5 Additional Results

######  Corollary 4.

In the setting of theorem 8 together with
${\mathcal{X}}=\left\\{{x\in{\mathbb{R}}^{d}:\left\|{x}\right\|\leq\left\|{{\mathcal{X}}}\right\|}\right\\}$
and
${\mathcal{H}}=\left\\{{x\mapsto\left\langle{w},{x}\right\rangle,x\in{\mathcal{X}},\left\|{w}\right\|\leq
D}\right\\}$. With
$\alpha=\left({\frac{D^{2}\left\|{{\mathcal{X}}}\right\|^{2}}{{n_{\text{priv}}}\epsilon}}\right)^{1/3}$
and
${n_{\text{pub}}}=\tilde{O}\left({(D\left\|{{\mathcal{X}}}\right\|)^{2/3}({n_{\text{priv}}}\epsilon)^{2/3}\operatorname{log}\left(2/\beta\right)}\right)$,
with probability at least $1-\beta$,

$\displaystyle
L(\widehat{h};{\mathcal{D}})-\min_{h\in{\mathcal{H}}}L(h;{\mathcal{D}})$
$\displaystyle=\tilde{O}\left({\frac{GD\left\|{{\mathcal{X}}}\right\|}{\sqrt{{n_{\text{priv}}}}}+G\left({\frac{D^{2}\left\|{{\mathcal{X}}}\right\|^{2}}{{n_{\text{priv}}}\epsilon}}\right)^{1/3}+\frac{B\sqrt{\operatorname{log}\left(4/\beta\right)}}{\sqrt{{n_{\text{priv}}}}}+\frac{B\operatorname{log}\left(4/\beta\right)}{{n_{\text{priv}}}\epsilon}}\right).$

###### Proof.

In this setting, we have that $R\leq D\left\|{{\mathcal{X}}}\right\|$.
Further, it is known [30],

$\displaystyle\text{fat}_{\alpha}({\mathcal{H}})=O\left({\frac{D^{2}\left\|{{\mathcal{X}}}\right\|^{2}}{\alpha^{2}}}\right),\qquad\mathfrak{R}_{n}({\mathcal{H}})=O\left({\frac{D\left\|{{\mathcal{X}}}\right\|}{\sqrt{m}}}\right).$

Pluging this in theorem 8, we get,

$\displaystyle
L(\widehat{h};{\mathcal{D}})-\min_{h\in{\mathcal{H}}}L(h;{\mathcal{D}})$
$\displaystyle=O\left({\frac{GD\left\|{{\mathcal{X}}}\right\|}{\sqrt{{n_{\text{priv}}}}}}\right)+O\left({\frac{B\sqrt{\operatorname{log}\left(4/\beta\right)}}{\sqrt{{n_{\text{priv}}}}}}\right)+\tilde{O}\left({\frac{\min{(B,GD\left\|{{\mathcal{X}}}\right\|)}D\left\|{{\mathcal{X}}}\right\|}{\alpha^{2}{n_{\text{priv}}}\epsilon}}\right)$
$\displaystyle+2G\alpha+O\left({\frac{B\operatorname{log}\left(4/\beta\right)}{{n_{\text{priv}}}\epsilon}}\right)$
$\displaystyle=\tilde{O}\left({\frac{GD\left\|{{\mathcal{X}}}\right\|}{\sqrt{{n_{\text{priv}}}}}+G\left({\frac{D^{2}\left\|{{\mathcal{X}}}\right\|^{2}}{{n_{\text{priv}}}\epsilon}}\right)^{1/3}+\frac{B\sqrt{\operatorname{log}\left(4/\beta\right)}}{\sqrt{{n_{\text{priv}}}}}+\frac{B\operatorname{log}\left(4/\beta\right)}{{n_{\text{priv}}}\epsilon}}\right).$

where in the last step, we plug in
$\alpha=\left({\frac{D^{2}\left\|{{\mathcal{X}}}\right\|^{2}}{{n_{\text{priv}}}\epsilon}}\right)^{1/3}$.
The number of public samples simplifies as,

$\displaystyle{n_{\text{pub}}}$
$\displaystyle=O\left({\max\left({\frac{R^{2}\operatorname{log}\left(2/\beta\right)}{\alpha^{2}},\min\left\\{{m:\text{log}^{3}(m)\mathfrak{R}_{m}^{2}({\mathcal{H}})\leq\alpha^{2}}\right\\}}\right)}\right)$
$\displaystyle=\tilde{O}\left({D^{2}\left\|{{\mathcal{X}}}\right\|^{2}\max\left({\frac{\operatorname{log}\left(2/\beta\right)}{\alpha^{2}},\frac{1}{\alpha^{2}}}\right)}\right)$
$\displaystyle=\tilde{O}\left({(D\left\|{{\mathcal{X}}}\right\|)^{2/3}({n_{\text{priv}}}\epsilon)^{2/3}\operatorname{log}\left(2/\beta\right)}\right).$

∎