Public-data Assisted Private Stochastic Optimization: Power and Limitations
Authors: Enayat Ullah
Michael Menart
Raef Bassily
Cristóbal A Guzmán
Raman Arora
Venue: NeurIPS 2024 poster (2024)
Keywords: Differential Privacy
Public Data
Stochastic Optimization
Generalized Linear Model
Primary area: privacy
TL;DR: We study the limits and capability of public-data assisted differentially private algorithms.

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

Public-data Assisted Private Stochastic Optimization: Power and Limitations
Enayat Ullah
Michael Menart
Meta enayat@meta.com com
Department of Computer Science & Engineering
The Ohio State University
Department of Computer Science, University of Toronto Vector Institute
menart 20rsttt.8ouueeee edu
Raef Bassily
Cristóbal Guzmán Inst. for Mathematical and Comput. Eng. Fac. de Matemáticas and Esc. de Ingenieria Pontificia Universidad Católica de Chile crguzmanpluc.co cl
Department of Computer Science & Engineering Translational Data Analytics Institute (TDAI)
The Ohio State University bassily 10osu...eee edu
Raman Arora
Department of Computer Science Johns Hopkins University
arorašcs. jhu. edu
Abstract
We study the limits and capability of public-data assisted differentially pri- vate (PA-DP) algorithms. Specifically, we focus on the problem of stochastic convex optimization (SCO) with either labeled or unlabeled public data. For complete/laheled public data, show that any (c,6)-PA-DP has excess risk á( ((min/ الحسe v + vdd )). where is the dimension, Tluu is the number of public samples, Rerii is the number of private samples, and
7ppb Ppriv- These lower bounds are established via our new lower bounds for PA-DP mean estimation, which are of similar form. Up to constant factors, these lower bounds show that the simple strategy of either treating all data as private or discarding the private data, is optimal. We also study PA-DP supervised learning with unlabeled public samples. In contrast to our previous result, we here show novel methods for leveraging public data in private supervised learning. For generalized linear models (GLM) with unlabeled public data, we show an efficient algorithm which, given Ö(mprive) unlabeled public samples, achieves the dimension independent rate O( Vipi VMyie We develop new lower bounds for this setting which shows that this rate cannot be improved with more public samples, and any fewer public samples leads to worse rate. Finally, provide extensions of this result general hypothesis classes with finite fat-shattering dimension with applications to neural networks and non-Euclioe Euclidean geometries.
"Work done while the author was at Johns Hopkins University. This work was done while M. Menart was at The Ohio State University.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Introduction
The framework of differential privacy has become the primary standard for protecting individual privacy in data analysis and machine learning. Unfortunately, this rigorous framework has also been shown to lead to worse performance on such tasks both empirically and in theory [BST14 PVX-23 23). However, it is often the case that, in addition to a collection of privacy-sensitive sensitive data points, analysts have access to a pool of public data, for which guaranteeing privacy protections is not required. This can happen, for example, when consumers deem their own data non-sensitive and opt-in to sell this data to a company. This has motivated a long line of work analyzing how public data can be leveraged in tandem with private data to provide better utility [BNS13] [AMM19] BCM 20 [WB22] [KS22]
AGM 22 NMT*231 In machine learning. for example, two commonly proposed strategies are public pretraining and using public data to identify gradient subspaces [ZWB21 KDRT21) Public pretraining, in particular, has proven effective in practice [YNB + 22al BWZK22], and prior work has even identified specific problem instance where public and private data used in tandem leads better rates than is possible using only the public or private datasets in isolation [GHN+33]. Despite this surge of work, theory has struggled show that public data leads to fundamental rate improvements more generally. Recent work has even shown that, for the problem of pure PA-DP stochastic convex optimization, small amount of public data, Pupb I ne/d, leads no rate improvement, where n popb + Apriv and Apriv is the number of private samples [LLHR23.
One particularly important version of this problem is in supervised learning when the public data is unlabeled. This setting has found importance in medical domains and deep learning more generally Notably, unlabeled data is much less time intensive to collect than labeled data. Due to this fact, and the fact that the unlabeled public data does not contain the same kind of information contained in the private data, the regime Ppuh [2(ppy ) is meaningful both in theory and in practice. We also note this setting is a stronger (in terms of privacy) version of the label-private setting, where only the labels of the dataset are considered private [CH BNSJ3]
[LW19 SCZ 20
Motivated by the importance of these settings and the lack of existing theory for them in stochastic optimization, we study fundamental limitations and applications of public data in (e. 6)-PADDP stochastic optimization. In the case where the public data is complete/labeled. we show that the application of public data is fundamentally limited. We then contrast this result with new results in the unlabeled public data setting. In this setting, we provide new results for GLMs, and extend these results to more general hypothesis classes, with finite fat-shattering dimension, and non-Euclidean geometries.
1.1 Our Contributions
We outline our primary contributions in the following.
Limits of Private Stochastic Convex Optimization with Public Data. First, we show a tight lower bound for the problem of differentially-prine privvate stochastic convex optimization (DP-SCO) assisted with complete public data, that is, the public data and private data have the same number of features
(and labels when applicable). Specifically, we show a lower bound of Ω min "mua vn + vd) on the excess population risk for this problem. When d 2 NE and 72pb S Iog(1/8)* further
vallo(1/5))) This lower bound is matched by the simple upper bound strategy which either discards the private data entirely and outputs the public mean or simply treats all data-points as private. Barring constant factors, this shows more sophisticated attempts at leveraging public data will yield no benefit. These results also hold even for generalized linear models. Our results are based on new results we establish for DP mean estimation with public data, and reduction of mean estimation to SCO. We note that previous work (LLHR23), on this problem either focused on the pure PA-DP case when pup I ne/d. d, or, in the approximate PA-DP case, did not obtain the dimension dependence. Our mean estimation lower bound uses novel analysis of fingerprinting codes [UV14], and our SCO reduction further builds on ideas from [BS114 CWZ21]. We also show that, when d nc, our lower bounds for approximate PA-DP SCO directly imply a tight lower bound for pure PA-DP.
improve this lower bound to 2( min { (yAby 1 +
vn
ne
Private Supervised Learning with Unlabeled Public Data. While the previously discussed results show there is no hope for leveraging public data in "interesting" ways, even for GL.Ms, they do not preclude settings where the public data is less informative. In particular, in the setting where the
2

---

public data is unlabeled, it makes sense to even consider Apub 2 Ngrive In this setting, we provide the following results.
For (Euclidean) GLMs we develop an efficient algorithm which, given (πprivv) unlabeled public data points, achieves the dimension independent rate Ō a dimensionality reduction procedure of the private feature vectors using the public data, and then running an efficient private algorithm in the lower dimensional space. The key idea is that public data can be used identify a low dimensional subspace, which under the appropriate metric acts as a cover for the higher dimensional space. We clucidate the tightness of our upper bound by proving two new lower bounds which show that access to a greater number of unlabeled public samples cannot improve this rate, and that any fewer public samples lead to a worse rate. While dimension independent rates for the GLMs have previously been developed in the unconstrained setting [SST121 ABG 22), in the constrained setting which we study, dependence on dimension is known to be unavoidable even for GLMs if no public data is available [BST14]. Our result thus allows us to bypass these limitations.
V Tipee / We obtain this result via
By observing that the key requirement in GLM result is the construction of an appropriate cover, we extend this result to general hypothesis classes with bounded fat-shattering dimension. In the non-private setting, it is known that finiteness of fat-shattering dimension characterizes learnability of real-valued predictors with scale-sensitive losses [BLW94] ABDCBH97). In the private setting, such result is not known, and is in fact impossible in the proper learning setting. This follows from the fact that norm bounded linear predictors, regardless of their (ambient) dimension d, have the same fat-shattering dimension [SSTTO). However, it is known that they are not learnable privately in high dimensions d 2 (ne)² [BST14). In contrast, in the PA-DP setting, we show that it is possible properly learn such classes with rate of roughly
O (Raaa (H) + infa>0 (H) + +a)): where Rugi (H) denotes the Rademacher complexity of H and (H) denotes its fat-shattering dimension at scale a (see Section 2 for preliminaries).
As applications of our result for hypothesis classes with bounded fat-shattering dimension, we obtain guarantees for learning feed-forward neural networks and non-Euclidean GLMs. par- ticular, for depth M feed-forwart neural networks with weights bounded as ||W]le S RG and 1-Lipschitz positive homogeneous activation, we achieve an excess risk bound of essen-
(II R2,)²) 1/3)
tially ò I1 R2
For non-Euclidean GLMs, our guarantees are
Plpecc
dimension-independenn which is not known to be achievable, as of yet, even in the unconstrained setting with no public data (unlike Euclidean GLMs).
1.2 Related Work
With regards to labeled public data, the most directly related work to ours is the recent work of
LLHR23 This work proves a lower bound sf (min Mighs V ne }) for approximate PA-DP DcemnesstiattionSSOO. We note that results for approximate PA-DP crucially obtain a dependence on that is the key "price" paid for privacy in this setting. [LHR223] also show a lower bound of
1
ne }} on a pure PA-DP mean estimation/SCO, but this result only holds when d < Rlgun As such, their result is orthogonal to our result in the pure PA-DP setting, which operates in the regime d > NE. In both cases, our proof technique is fundamentally different than theirs Tangentially, [2 showed a small amount of public data is useful in pure-DP mean estimation when the range parameters on the data are unknown.
Q min
{
Waai' vn + d
An important setting where public data is shown to be useful is PAC learning. Non-privately it is known that the finiteness of VC dimension characterizes learnability [VC71 BEHW89]. However, under DP, it is impossible to PAC learn even the class of thresholds, which has VC dimension of one [NST3]. The works of [BSS3, BTGTT88 ABM19 showed that given access to a small unlabelled public data, it is possible go beyond this limitation and privately learn VC classes, essentially by reducing a hypothesis class with finite VC dimension to a finite hypothesis class
We note that concurrently and independently, version 2 of LLHR23 LLHR24 obtained lower bound + vd nc )): but their lower bound is limited to symmetric procedures.
of Ω min /
3

---

A number of works have studied the impact of public data in applied settings as well. A common technique is use public data reduce the problem dimension in some way [ZWB2I] YZCL2T PHYS24). The work of 23H identified a specific problem instance which supports the method of public pretraining commonly used in practice.
With regards to unlabelled public data, there are several existing works. Transfer learning is a common approach in this setting. Besides the benefits in PAC learning, this setting also has applications in deep learning, where (empirically) unlabeled public data has been used to obtain performance improvements [PAE 17 PSM+ 18). Unlabeled public data has also yielded impressive results used for pre-training large language models [LTLH22 YNB 22b]. We also remark that, in practice, it reasonable to expect the private and public datasets to come from slightly different distributions. Accounting for this distribution shift has also been the study of several recent works [BKS22]
BDBC+23). However, in this work we focus on first characterizing the more fundamental problem where the public and private datasets are drawn i.i.d. from the same distribution.
2 Preliminaries
Here, describe the concepts and assumptions used in the rest of this paper. In this work, || always denotes the f2 norm unless stated otherwise.
Public-Data Assisted Differential Privacy. We first present the traditional notion of differential privacy (DP). Let n, E and X' be some data domain. When no public data present, we say that an algorithm A satisfies (e, -iiffeerrntii privacy (DP) if for all datasets S and S differing in one data point and all events in the range of A. P (A(S) E E] & I [A(S") E E] + [DMNS06).
In our work, we denote the number of public samples in the dataset, S = (Spubs Spri)) E X as pupb and the number of private samples as mpev. such that n = nupb + Ngriv. In keeping with previous work BBS133 BBM++20 we define public data assisted differentially private algorithms in the following way
Definition 1 (PA-DP). An algorithm A is (c,8) public-data assisted differentially private (PA- DP) algorithm with public sample size npub and private sample size upriv if for any public dataset Spub E X and any pair of private datasets Spriv: priv E X differing in at most one entry, it holds for any event E that P [A(Spub Sprit) E El ee Spri)) E E] 5. When 5 = 0. we
refer to this notion as pure PA-DP, denoted as c-PA-DP.
Stochastic Convex Optimization Let D be distribution supported on X. Given some constraint set W S & of diameter at most D, and a G Lipschitz convex loss f : W x X' - R, we are interested in minimizing the population loss, [(w; D) E [((r;))). Denote the minimizer as znD
w" min (w: D)}. We evaluate the quality of the approximate solution, w, via the excess risk, L(w; D) - L(w"; D). Specifically, we are interested in PA-DP algorithms which minimizes this quantity when given Spun. Spriv L(w; S) [s| Exes ((w:z).
i.i.d. D. For a datset S we also define the empirical loss
Supervised Learning and Generalized Linear Models (GLMs) In the supervised learning setting, in addition to the feature space X, we define the label space y) We here let D be a joint probability distribution over X x )/ and Dx and Dy denote the respective marginal distributions. Let H. R be a hypothesis class of real-valued predictors, and let (?)) denote its fat shattering dimension at scale a. Consider the loss function L: H x X x y + R. such that E(h; Ir y) = (b(()))) for some function by. We assume that the map by : IR + R is G-Lipschitz for all E y and is B-bounded. Further, we assume that suprex [h(x)] S R and define supzex ||=|||| |||]||-
GLMs are a special case of supervised learning setting where the hypothesis class is that of lincar predictors, H. = W C Rdd over X C Rdd and h(x) w x. We refer to the public dataset of unlabeled feature vectors as Xpub-
Covering numbers, fat-shattering and Rademacher Complexity Given X = (x1, Fm) the Ep distance between two hypothesis hys h2 E H with respect to the empirical measure over X, is defined as, ||/, - hallp.x ( Enex (1) - (2)) 1/p Similarly, the distance with respect
'The term semi- DP algorithm has also been used in some works.
4

---

to the population, is given by ||, - hellp... (EE-Dx (z)(2) - hz(x))1)//PP The covering number of H at scale a and given dataset X, denoted as NG, a, X) the size of the minimal set of hypothesis, H. such that for any h H there exists with || hllp. x. I a. We define Ny(PH (H, a, X), the covering number with respect to all datasets of size m. We define fat-shattering dimension below.
N a, m) supx. x NVp
Definition 2. (BLW94) Let H _ IRx and a > We say that H a-shatters X= { T2....,, Imm minye(--111) mm
suPsEи minggmm V:(h(z;) rz) 2 a. The fat-shattering dimension, (H)) h. is the size of the largest a-shattered
We define Rm (H), the worst-case Rademacher complexity of H with respect to m data points, as Rm (H) supx:]X|=n E., suPREи m 2i=1 agh(xss) An important example is that of norm- bounded linear predictors {w x (w, x) ||w||| S D} over X' {x : ||^||| s || Herein,
fat, (H) θ D= and (?)) = O DIIX
AISTO&SSSTI
mm
Private Stochastic Convex Optimization with Labeled Public Data
In this section, we present our lower bounds for private stochastic convex optimization with public data. When interpreting the following results, it is helpful to note that in the nontrivial regime, Ppub (n) and pupb = o(n), although our results hold regardless. Further, recall that an upper
can be obtained by simply either applying an optimal SCO algorithm to only the public data (and discarding the private data) or applying an optimal DP-SCO algorithm and treating the entire dataset private [BFIGT19). As will see, this strategy is essentially optimal.
bound for this problem of O [mmin VMyan vn +
(llog(1/0) nc
3.1 Lower Bound for Stochastic Convex Optimization
We start by stating our lower bound for public-data assisted differentially private SCO.
Theorem 1. Let < 16nd S 1, and d be larger than some universal constant. For any (c-D)-PA-D algorithmm, there exists distribution D, and a G-Lipschitz loss such that [[L(A(Spub: Spri): D) min (Lw; D)}] Ω (GD. (M n, d, e, 8)), where for some uni- w:ll s
versal constant
d log(1/5)
min
d 1 ene,, Npub S clog(1/[Vnd6)
L (n n, d. c,
Vn
ne
min
else
Plyss
TLC
The function V is defined to avoid repetitive notation in the rest of this section. Barring the mild restriction on Npub. even though the Vlog (1/8) term is only obtained when d 2 nc, the "aggregate" 1 lower lower bound is tight for all & (oog(1/5) ne] since when d S log(1/8) the non-private Vn
ne²
ne
bound dominates. It is also pertinent to our results in Section 4 that the problem construction used to achieve this lower bound a convex GLM, and as a result this lower bound holds even for GLMs.
Finally, similar statements can be made about strongly convex optimization. We again provide just one such statement here.
Theorem 2.
Let 8 < Tong 1. For any ()-8)PPA-DPP algorithm there exists distribution DD X-strongly convex and G-Lipschitz loss such that
EE [LL(A(Spub) Sprie); D) D)-
min w: Wo SD ED
[)w -2 (5 4 n, n,e, e)).
The crux of the proofs for both the above results lies in establishing new mean estimation lower bounds PA-DP mean estimation, which we give Appendix [.I These mean estimation lower bound use novel application of construction known as fingerprinting codes. In particular, the introduction of public data introduces significant thgilnnsntccaalllnnesss in the traditional analysis of fingerprinting codes. As these challenges more technical in nature, we defer their discussion Appendix B.2
5

---

After establishing the mean estimation lower bounds, we can adapt the reductions first used in [BST14] that show mean estimation lower bounds can be used provide lower bounds for risk minimization without public data. Full proofs for the above claims, and in particular details for the above reductions, are found in Appendix BB.3
Lower Bound for Pure DP Case. While not the primary focus of this work, the previous lower bound directly leads lower bound for pure PA-DP SCO. Since any e-DP algorithm (e. 6)-DP for any 5 > O, we can use the above theorem to obtain non-trivial lower bound for the pure DP case by setting small. Specifically, by setting such that log (1/6)
one immediately obtains
120
lower bound of 22 minf the following.
va v=haam)))
for d large enough. Simplifying this expression yields ))
Corollary 1. Let d 2 for a constant c, and A be an e-PA-DP algorithm. There exist a distribution D and G-Lipcchitz loss such that E [[A((Spub Spri)): D) min
(L(w; D)} Vippe
GD
w:||w||
The known O (GD min Viipe V
upper bound for this problem shows that this bound is tight (in the regime in which it holds). Essentially, this bound states that when d 2 nc, the public dataset is not useful (at least asymptotically). Previously [LLHR23] Theorem 31] established that (GD(4 Fer + ) holds, effectively showing that in
me
when S ne/ ne/"pubs tight lower bound of Ω
this regime the public dataset is not useful
5 We leave the remaining regime where d E (. nc) as an interesting open problem for future work. Finally, we note that similar statements can be made
about strongly convex losses using Theorem 2
4 Private Supervised Learning with Unlabeled Public Data
In this section, we consider supervised learning with real-valued predictors given labeled private data and unlabeled public data. Our results show that, in this setting, it is possible to go beyond the limitations established the prior section.
4.1 Efficient PA-DP learning of Convex Generalized Linear Models
We start with learning linear predictors with convex loses a.k.a. convex generalized learning models. We propose Algorithm which uses the public unlabeled data to perform dimensionality reduction of the private labeled feature vectors. In the following, we use span to denote the span set of vectors and dim to denote the dimension of subspace. The dataset of public unlabeled feature vectors is denote as Xpub- Our algorithm projects the private feature vectors onto the subspace spanning W A span(Xpab) feature vectors. then reparametrizes the loss function so that its domain dim(span(S dimensional and applies private subroutine in the lower dimensional space. The output of the subroutine is then embedded back in Rd Algorithms similar to Algorithm have appeared in the literature (e.g. [PHYS24]). We emphasize that key contribution is the formal analysis of this technique and the fact that we provide tight upper and lower bounds while simultaneously avoiding many of the strong assumptions seen in previous work, such as large margin assumptions.
get dim(span(XXpo
dimenniinsi representation of the private nw)-
Algorithm 1 Efficient PA-DP learning of GLMs with unlabeled public data
Input: Private labeled dataset Spriv. public unlabeled dataset Xpub. privacy parameters e, 8 > O.
1: Let U E (indsiinn
denote the orthogonal projection onto xpan(Xpur) n W.
2: Define Spmi {(UT 34, ys }"m and let W {UT w E W].
3: Apply (e, 8DP subroutine, A. on loss function w + (y((w,))) with dataset Spmi over the constraint set W, to get to E (WPppasS)))))))))))) Output: v W..
$ "This claim is based on a simplification of their theorem statement. Specifically, because Tpph S ne/d, which d.
also implics d E ne, their lower bound Ω (Rmin
+ - simplifies.

---

Our main result for convex Lipschitz losses is the following.
Theorem 3. Let 0, > 0 and I log (1/6). For G-Lipschitz. B-bounded convex loss function, Algorithm [ satisfies (c.8)-PA-DP. If the private subroutine A guaranttes the following, with probability at least 1 3,
min T(u Sprit) 00 GD ||27|| (0 wEW
VMpub log (1/6) + Vlog(1/3) (1/3) )) (1)
T.(A(Spri):: Sprit) )
Cprio
then with Topub = 0 (log(2/0)+log(1/6)))
Byme
with probability at least 1 - B, L(w; D) - L(w";; ; is
GD @GDD
Vlog Vlog(4/B) (4/3)
(log (2/B) + log (1/8))
B Bylog (4/5)
Aprri
We note that DP algorithms such as projected noisy SGD [ST and the regularized exponential mechanism [GLL22], both of which be implemented efficiently, can be used achieve (. since the projected problem is at most Npuh dimensional.
The above result shows that in the usual regime of ((). there is no price of privacy, thereby Vd
We contrast this with the rate of O achievable without public data. Our result is better when d 2 peive, which the interesting regime since herein the private error dominates the non-private error. Further, below) shows that this is the non-trin coiviaivial regime (for any e = (())). since otherwise, even with unlimited public data, the optimal rate is achieved without using any of it. We also note that the above rate is achievable without public data, but in the unconstrained setting where the output i can have very large norm and may lie outside W 2BG++2)).
obtaining the non-private rate of O Piper
( Aag lower bound (Theorem 4
Pign
The proof of the result primarily follows from the more general result with fat-shattering hypothesis classes (Theorem 7 We provide the key ideas as well as some details pertaining linear predictors
in Section 4.2 after Theorem 7 The full proof of this result deferred to Appendix C
Lower Bounds. The above rate as well as the number of public samples used are nearly-optimal. The first claim is due to the following result, which gives lower bound on excess risk of DP algorithms under full knowledge of the marginal distribution, for Lipschitz GLMs. As unlabeled public data can only reveal information about the marginal distribution, this shows that further unlabeled public samples cannot hope to improve the rate we give in Theorem 3
Theorem 4. Let < 1,8 S and A be an S)DD algorithu. There exists a G-Lipschitz convex GLM loss function, and joint distribution D such that given a dataset S comprising n i...d. samples from D and full knowledge of the marginal distribution Dx, we have the following:
EASS [L(A()):) - min L(w; D)] = S (GD || +
miin
va
We note that the bound with Vd
Aytce can be achieved without using any public data via standard results BFTGTI9 2BG+ This result is largely corollary of [ABG+22 Theorem 6). We provide full details in Appendix C.3.T
To establish optimality of public sample complexity, we give the following lower bound which shows that (Tprive)) samples are necessary to achieve the above rate. See Appendix C.3.2 for proof.
Theorem 5. Let Rpriie Ngub.
N, I 1,8 16dn and d w (Toprii If there exists an (c,5)-PA-DP algorithm A, which, for any G-Lispschitz convex GLM, achieves excess risk
[L(A(Xpb> Spri); D) min w/ SD L(w; D)]
D(GD)IX)) (T
+
Loogi/00
)), for
Spriv Dr and Xpub D "in then Tlpub 12( [og(178))
Optimistic rates. We now consider additional assumptions that the loss function is non- negatiee and H-smooth, such as in the case of linear regression where (,)(a) = (a - y)² This is a well-studied setting [SSTTO] especially since it allows for obtaining optimistic rates: those that interpolate between a slow worst-case rate and a faster rate under (near) realizability or interpolation conditions. The main result is the following.
7

---

Theorem 6. Let c > 0,8 > 0 and I log (1/8). For G-Lipschitz. B-bounded non-negative H-
smooth loss function, Algorithm| satisfies (c.8)-PA-DP. If the private subroutine A guarantees Equa-
tion with probability at least 1 - 3. then with Npua Ô (HDI) ( (m )2/3 /Bnga (pie)) G Gz/log(188)
with probability at least 1 - 3.
L(w; D) I(@";Spm)) =0
VHDING Apmo
B
v V Spri)
H H VGL(W"; Sprid )
Téprii
v Appri
+
GD
(V
2/3
H 11 2 D³
B Ppric
OppirE
VpprivE
nprive
where w' is the minimizer of w.rt Spriv and Ô hides poly(log (1/6). log (1/B) terms.
similar result as above can be obtained with T(w"; Spiv) replaced by ((w=;;) above - see Theorem 14 for the full theorem statement. This rate, in the worst-case, is essentially the same as that of Theorem which is L Spriv is small, we get faster rate of Ō Apec
However, optimistically, when I(w"; D) or
Tight
(7/0 We note that this is seemingly weaker than what is known in the unconstrained setting, where [BG obtained a worst-case rate of Ō( Mppl + (M/m)))2/33 ). We show that we can recover this faster rate under an extra assumption that the global minimizer of the risk, lies the constraint set W - note that this is trivially true in the unconstrained setup; see Theorem 15 for the statement.
We note that projected noisy SGD BST14 and the regularized exponential mechanism GLL22)
both of which can be implemented efficiently, are possible choices for the private sub-routine A that realize the above theorem statements.
4.2 PA-DP Supervised learning of Fat-Shattering Classes
In this section, we consider a general supervised learning setting with fat thatthatt hypothesis classes and potentially non-convex losses, with unlabeled public data. Our proposed algorithm is similar to that [ABM19), which uses the pubic unlabeled data to construct a small finite, yet representative, subset of the hypothesis class. Our construction uses a cover of the hypothesis class with respect to f2 distance of predictions on the public data points. We then use exponential mechanism to privately select hypothesis using the empirical loss private data as the score function.
We note that we operate under the pure DP setting (as opposed to approximate DP), Our techniques are based on selection which do not exhibit improved guarantees under approximate DP. Further, we note that, without public data, with non-convex losses, there is no separation of optimal rates between pure and approximate DP GTU23
Algorithm 2 Supervised private learning with public unlabeled data Input: Datasets Xpuh and Spive privacy parameter e > 0, scale of cover a >> 0, 7 > 0. 1: Construct H. minimal a-cover of H. with respect to the following metric
[1 - 122l2.xxx
(h1(z) - h2(x))²
Alpub
2: Return h sampled with probability p(h) x exp (~II(h; Spri)) over h E H
Our main result for the Lispehitz. setting is the following.
Theorem 7. Algorithm with 7 =
minn B. GR)
satisfies e-PA-DP. For any a > 0 and Tlpub
Nipert
O maxx
R² log(2/8) min {m- log² (m))23 (H) S a²l)) < co, with probability at least 1 - B.
a²
have L(h; D) min L(h; D) is at most he
8

---

B By log (4/3) δ
min (B, Gfa (H) log (4/81) + 2Ga,
2G (H)
Pprii
Pprive
where is absolute constant.
Our result shows that the model of PA-DP with unlabeled public data allows for obtaining non- trivial rates for supervised learning with any fat-shattering class, as is the case in the non non-private setting. Further, many standard settings, such as that of (Euclidean) GLMs, the Rademacher
complexity is Rm (H) O
which implies that (H) O ( (+t) (see Theorem 9b. In those
cases, our guarantee simplifies to essentially yield rate of O RRmc (H) (A
Vigeo
Corollary for the exact statement for GLMs.
Proof Idea. We briefly discuss some main ideas in the proof. The key is to show that if H. a cover of H with respect to the empirical distance on public feature vectors, 11-1l2.xpe" then with enough
public feature vectors, it is also a cover with respect to the population distance 11 This captured the following result.
Lemma 1. Let H be T-cover of H with respect to 11-11..x.w' For Rpub
( [2 (8100((10)) min {m (m))) ( (H) S <a²)) for every h E H. with probability
O( ((max
least 1 - B. there exists h H such that 1 hl12,D Sa
This result allows to appropriately approximate hypothesis class with enough public unlabeled points. This approximation roughly translates to the same additive error in the final bound while concurrently allowing for the use of the smaller finite hypothesis class of size H = Ōfat, (7()).
For linear predictors with convex losses, as in Theorem we show that the span puhh) n W is valid (-cover w.r.t. || 22 However, the cover being continuous and convex allows application of convex optimization techniques (as opposed to selection, as above), thereby obtaining stronger results with efficient procedures. The above procedure yields optimistic rates for non-negative and smooth losses; see Theorem 17 for details.
4.2.1 Application: Neural Networks
In this section, we instantiate our general result to give a guarantee for learning feed-forwane neural networks in the PA-DP setting. We use the result of [GRSI8] note that other results which give bounds on the Rademacher complexity of neural networks, such as [BFT17 Sel23 can also be used.
We consider depth M feed-forward neural network which implements the function xr a(W (WWiz)) Here, Wi, W2,..., WM are the weight matrices and a is a (non- linear) activation function. We consider 1-Lipschtizz pesitivehhomogeeeou activation such as the ReLU function, (2z) = max(0, 2). applied coordinate-wise Our main result is the following.
Let (z be a sequence of scalars and M E E. In the setting of Theorem 7 with X {a ERd ||ж||| S [|l|]} and being the class of depth M feed-forward neural networks, with 1-Lipschitz positive-homogenon activation, and weight matrices, bounded as [[5 S R2.
Corollary 2.
with Npub Ô ((I=11) (IT (R)) (m)nne))) 2/3 M 1/3 log (2/3)). with probability at least T(,;; - minneH T.(h; D) is at most
GIINIIIIT R2 B Bg (4/3)
B log (4/3) Tlrrnc
+ (
BGG II R2
1/3
Tipm
Dhpri
We note that the above result has polynomial dependence on the depth M, which is consequence of the (non-pri poinvari Rademacher complexity of [RSI8]. is also possible to get fully size-independent bounds by utilizing such existing results, however they require more stringent norm bounds on the weight matrices [Se123]. Further, a similar result follows for non-negative smooth losses from [SSTIO], but omit this extension for brevity.

---

4.2.2 Application: Non-Euclidean GLMs
In the non-Euclidean GLM setting, we consider (x, 11-1) as a d dimensional (where d E NU (oo}) Banach space, and (W, II-II.) is its dual space. The feature vectors z are bounded as
{a X ||=||| S ||**]| } and W C {w E W Aww) S Dr) where A is r-uniformly convex func-
tion with respect to |1-I1.. A canonical example is the (Ep. fg)-setup [SS088 FGV17I, wherein the
functions (ww) log(d) || (1/ko())))))))))) Aww) 2(p-1) I|wIl and A(w) 2n-2 I are 2, 2
p
and p-uniformly convex with respect to I1-11p for p= = 1, < S and 2 respectively.
The GLM loss function f(w; v. v) - Φ, ((w,, .)) where (:-) : x W + a duality pairing. In this case, the Rademacher complexity of linear functions, is bounded as
[ m where & the Corollary 3. In the setting of Theorem 7 logether with X' = f E R4 || < [| and H
conjugate of r i.. 1 + 5 = (see, e.g. (FGV17). We obtain the following result by instantiating Theorem 7 with the Rademacher complexity and fat-shattering dimension of non -uc-luclide GLMs.
{i + (w. x) x E 2, ((,( S D"} Given npub = Ô ((pmoc)) log (2/ B)), with probability
least L(W;D) minwew L(w; D) is most
Pepriv fr + Vlog (4/3) log (2/3)
log (4/3) Rprivc
B BV/oy log (4/3)
δ GDD
Mpri
(ppra r+1
Mppri
The above yields guarantees for the special case of (lp, Cg) sy)-se with r- max {2, p). We remind that in the (constrained) convex Euclidean GLM setting, our dimension iewprssioonnddeeeeentteeee rate Theorem with public unlabeled data recover the rates which were known to be achievable in the unconstrained setting. Further the above rate for p 1 case can be used to obtain guarantees for the polyhedral
setting with ||l||| < D constraint, resulting in a O (V
[og(d)
+ ((118)
[log(d)
1/3
rate. We note that
BGM21] showed a rate of Ô (Viestt)
v Vlgg(d) vne
for this setting, with convex losses without
public data. Importantly, for the other cases, i.e. p > 1, + 2, there are no such (nearly) dimension- independent analogs of our result without public data, as of yet.
Acknowledgments and Disclosure of Funding
R. Arora's 's and E. Ullah's 's research was supported, in part, by NSF BIGDATA award UIS-1838139 and NSF CAREER award IIS- 1943211. R. Bassily's and M. Menart's research was supported by NSF CAREER Award 2144532 and, in part, by NSF Award 21 12121... C. Guzmán's 's research was partially supported by INRIA Associate Teams project, ANID FONDECYT 1210362 grant, ANID Anillo ACT210005 grant, and National Center for Artificial Intelligence CENIA FB210017, Basal ANID.
References
[ABDCBH97] Noga Alon, Shai Ben-David, Nicolo Cesa-Bianchi, and David Haussler. Scale- sensitive dimensions, uniform convergence, and learnability. Journal of the ACM (JACM), 44(4):615-63) 631, 1997.
[ABG+22] Raman Arora, Raef Bassily, Cristóbal Guzmán, Michael Menart, and Enayat UI- lah. Differentially private generalized linear models revisited. Advances in Neural Information Processing Systems, 25:22505-225177 2022.
[ABM19] Noga Alon, Raef Bassily, and Shay Moran. Limits of private learning with access to public data. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
A differentiable map V is r-uniformly convex w.r.t ||-||, if V(u') 2 V(u)= + (VV(U), - u)
||u ul
10

---

[AGM + 22] Ehsan Amid, Arun Ganesh, Rajiv Mathews, Swaroop Ramaswamy, Shuang Song, Thomas Steinke, Thomas Steinke, Vinith M Suriyakumar, Om Thakkar, and Abhradeep Thakurta. Public data-assisted mirror descent for private model training. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 517-535. PMLR, 17-23 Jul 2022.
[BCM
Raef Bassily, Albert Cheu, Shay Moran, Aleksandar Nikolov, Jonathan Ullman, and Steven Wu. Private query release assisted by public data. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 695-703. PMLR, 13-18 Jul 2020.
[BDBC+23] Shai Ben-David, Alex Bie, Clement Louis Canonne, Gautam Kamath, and Vikrant Singhal. Private distribution learning with public data: The view from sample com- pression. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[BEHW89] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the vapnik-chervonenkis dimension. Journal of the ACM (JACM). 36(4):929-965, 1989.
[BFT17] Peter L Bartlett, Dylan J Foster, and Matus Telgarsky. pnectrall-nnommaliee margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
[BFTGT19] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. Advances in Neural Information Processing Systems, 32, 2019.
[BGM21] Raef Bassily, Cristóbal A Guzmán, and Michael Menart. Differentially private stochastic optimization: New results convex and non-convex settings. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[BKS22] Alex Bie, Gautam Kamath, and Vikrant Singhal. Private estimation with public data. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[LW94] Peter Bartlett, Philip M Long. and Robert Williamson. Fat-shattering and the learnability of real-valued functions. In Proceedings of the seventh annual conference on Computational learning theory, pages 299-310, 1994.
[BNS13] Amos Beimel, Kobbi Nissim, and Uri Stemmer. Private learning and sanitization: Pure approximate differential privacy. In Prasad Raghavendra, Sofya Raskhod- nikova, Klaus Jansen, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 363-378, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
[BST14] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk mini- mization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 464-473. IEEE, 2014.
[TGGT18] Raef Bassily, Om Thakkar, and Abhradeep Guha Thakurta. Model-agnostic private learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
and
[BUV14] Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approximate differential privacy. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC 14, page 1-10, New York, NY, USA, 2014. Association for Computing Machinery.
11

---

[BWZK22] Zhiqi Bu, Yu-X Ui-Xiang Wang, Sheng Zha, and George Karypis. Differentially private bias-term only fine-tuning of foundation models. In NeurlPS 2022 Workshop on Trustworthy and Socially Responsible Machine Learning (TSRML.), 2022.
[CHI1] Kamalika Chaudhuri and Daniel Hsu. Sample complexity bounds for differentially private learning. In Sham M. Kakade and Ulrike von Luxburg. editors, Proceedings of the 24th Annual Conference on Learning Theory. volume 19 of Proceedings of Machine Learning Research, pages 155-186, Budapest, Hungary, 09-11 Jun 2011 PMLR.
[CWZ21] T. Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics, 49(5):2825 - 2850, 2021.
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity private data analysis. In Theory of cryptography conference, pages Springer, 2006.
[DSS + 15] Cynthia Dwork, Adam Smith, Thomas Steinke, Jonathan Ullman, and Salil Vadhan. Robust traceability from trace amounts. In 2015 IEEE 56th Annual Symposium Foundations of Computer Science, pages 650-669, 2015.
[Duc23] John Duchi. Lecture notes statistics and information theory, May 2023.
[FGV17] Vitaly Feldman, Cristobal Guzman, and Santosh Vempala. Statistical query algo- rithms for mean vector estimation and stochastic convex optimization. In Proceedings of the Twenty-Eige Eighth Annual ACM-SIAM Symposium on Discrete Algorithuss, pages 1277- SIAM, 2017.
[FS17] Vitaly Feldman and Thomas Steinke. Generalization for adaptively- estimators via stable median. In Satyen Kale and Ohad Shamir, editors, Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 728 728-757. PMLR, 07-10 Jul 2017.
[GHN+23] 23] Arun Ganesh, Mahdi Haghifam, Milad Nasr, Sewoong Oh, Thomas Steinke, Om Thakkar, Abhradeep Thakurta, and Lun Wang. Why is public pretraining necessary for private model training? In International Conference on Machine Learning, 2023.
[GLL222] Sivakanth Gopi, Yin Tat Lee, and Daogao Liu. Private convex optimization via exponential mechanism. In Conference on Learning Theory, pages 1948-1989, PMLR, 2022.
[GRS18] Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Conference On Learning Theory, pages 297-299. PMLR, 2018
[GTU23] Arun Ganesh, Abhradeep Thakurta, and Jalaj Upadhyay. Universality of langevin diffusion for private optimization, with applications to sampling from rashomon sets. In The Thirty Sixth Annual Conference on Learning Theory, pages 1730-1773. PMLR, 2023.
[KDRT21] Peter Kairouz, Monica Ribero Diaz, Keith Rush, and Abhradeep Thakurta. (nearly) dimension independent private erm with adagrad rates
via publicly estimated subspaces. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Pro- ceedings of Machine Learning Research, pages 2717-2746. PMLR, 15-19 Aug 2021.
[KST08] Sham M Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. Advances neural information processing systems, 21, 2008.
12

---

[KU20] Gautam Kamath and Jonathan Ullman. A primer private statistics, arXiv preprint arXiv:2005.00010, 2020.
[LLHR23] Andrew Lowy, Zeman Li, Tianjian Huang, and Meisam Razaviyayn. Optimal differentially private learning with public data, arXiv preprint 10w.6666....1 2023.
[LLHR24] Andrew Lowy, Zeman Li, Tianjian Huang, and Meisam Razaviyayn. Optimal differ- entially private model training with public data, arXiv preprint arXiv:2306. 2024.
[LTLH22] Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto. Large language models can be strong differentially private learners. In International Conference on Learning Representations, 2022.
[LW19] Daliang Li and Junpu Wang. Fedmd: Heterogenous federated learning via model distillation, 2019.
[MT07] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Anmual IEEE Symposium on Foundations of Computer Science (FOCS'07), pages 94-103. IEEE, 2007.
23] Milad Nasr, Saeed Mahloujifar, Xinyu Tang, Prateek Mittal, and Amir Houmansadr. Effectively using public data in privacy preserving machine learning. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference Machine Learning. volume 202 Proceedings of Machine Learning Research, pages 25718-25733 PMLR, 23-29 Jul 2023.
[PAR 17] Nicolas Papernot, Martin Abadi, Ulfar Erlingsson, Ian Goodfellow, and Kunal Talwar. Semi-supervised knowledge transfer for deep learning from private training data. In International Conference on Learning Representations, 2017.
[PHYS24] Francesco Pinto, Yaxi Hu, Fanny Yang, and Amartya Sanyal. PILLAR: How to make semi-private learning more effective. In 2nd IEEE Conference on Secure and Trustworthy Machine Learning, 2024.
[PSM + 18] Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Erlingsson. Scalable private learning with PATE. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018
[PVX Natalia Ponomareva, Sergei Vassilvitskii, Zheng Xu, Brendan McMahan, Alexey Ku- rakin, and Chiyaun Zhang. How to dp-fy ml: A practical tutorial machine learning with differential privacy. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '23, page 5824, New York, NY, USA, 2023. Association for Computing Machinery.
[RS12] Alexander Rakhlin and Karthik Sridharan. Statistical learning theory and sequential prediction. Lecture Notes in University of Pennsyvania, 44, 2012.
[SCZ + 20] Dianbo Sui, Yubo Chen, Jun Zhao, Yantao Jia, Yuantao Xie, and Weijian Sun. FedED: Federated learning via ensemble distillation for medical relation extraction. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu, editors, Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages Online, November 2020. Association for Computational Linguistics.
[Sc123] Mark Sellke. On size-independent sample complexity of relu networks. arXiv preprint arXiv:2306.01991 2023.
[SSBD14] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
13

---

[SSTI0] Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Optimistic rates for learning with a smooth loss. arXiv preprint 1011:100093899 2010.
[SSTT21] Shuang Song, Thomas Steinke, Om Thakkar, and Abhradeep Thakurta. Evading the curse of dimensionality in unconstrained private glms. In International Conference on Artificial Intelligence and Statistics, pages
PMLR, 2021.
[SU15] Thomas Steinke and Jonathan Ullman. Between pure and approximate differential privacy. Journal of Privacy and Confidentiality, 7, 01 2015.
[VC71] N. Vapnik and Ya. Chervonenkis, On the uniform convergence of relative fre- quencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264, 1971.
[Ver18] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[2NB+222) Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, Sergey Yckhanin, and Huishuai Zhang. Differentially private fine-tuning of language models. In International Conference on Learning Representations, 2022.
[YNB+22b] Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, Sergey Yekhanin, and Huishuai Zhang. Differentially private fine-tuning of language models. In International Conference on Learning Representations, 2022.
[YZCL21] Da Yu, Huishuai Zhang, Wei Chen, and Tie- Yan Liu. Do not let privacy overbill utility: Gradient embedding perturbation for private learning. In International Conference on Learning Reprexentations, 2021.
[ZWB21] Yingxue Zhou, Steven Wu, and Arindam Banerjee. Bypassing the ambient dimension: Private sgd with gradient subspace identification. In International Conference Learning Representations, 2021.
14

---

A
Additional Preliminaries
Theorem 8. RS12 Theorem 12.7] For H. S [-,, m m.N.D2L..0 we have that
22 Ca (H)
a, 2
Further, for any 10,
Rm fan(H,
(fa((),)raa)
log (Noo m)) < C' CTa)
log"
where c, d, C and C' are absolute constants.
Theorem 9. ISST1O Lemma A.3] For any hypothesis class H. any sample size m and any > Rm (H), we have that,
(H) 4mH (H))
a²
M be a sequence of scalars. The Theorem 10. [GRS18 Theorem 1] Let M N and (Ri)
Rademacher complexity of the class of depth M neural networks with 1-Lipschitz, positive- homogeneous activation function, H., with weights [|W p I R2 is bounded as,
||x0|1 (/2 (2) M + 11
Rm (H) S
Vm
Here ||- || denotes the Frobenius norm.
Lemma 2. IDSS+ 15) Implied by Lemmas 5 and 14] Let f: {+1]" + R and define [-1,1] + IR as g(p) = s-DP
[f(S),, where D, is as defined in Appendix B Then for a, b IR, > a, and
~ Unif([a,bb) b)).
E
f(S)
Σ (a - m}] = (g' x2)1
a.S
FES
1
= =1
[n2]] (g(b) 0)(1 b2) b-a (g(a) a)( a²) b + 2E ((g(u) p)pp
#
Lemma 3. FS17
Lemma A. Fix μr, e, A R. Let X and Y be random variables supported on j A pz + A Suppose that and Y are (c, ji---indisiinuushablle that is for any C TR,
(P E 3 8) < PY E) S e (X E E] + 5. Then
[ - BMI < (e 1)E ||X 14] 28A
B Missing proofs from Section 3
B.1 Lower Bounds for Mean Estimation
As stated previously, our SCO result follows primarily from new lower bound for PA-DP mean estimation. Here, we consider the setting where D is supported on the & ball of radius R 0. We define the mean of D as p)D). Our lower bound for PA-DP mean estimation follows much the same form as our SCO bound.
Theorem 11. Let 8 < Tönd S For any (e, PAP--D algorithm, there exists a distribution D such that E [|| Spri)) ((D) = ( (Tipuu. n, 6, 6)).
1
present the full proof momentarily and provide a more detailed discussion on the challenges of establishing this lower bound in Appendix B.2 We highlight key ideas here. As with many other lower bounds in differential privacy, we leverage a construct known as fingerprinting codes BUV14 DSS+ 15). A key aspect of our analysis is showing that fingerprinting distributions can be
15

---

used to recover the optimal non-private lower bound for mean estimation. This allows us to create problem which is "hard" both privately and non-privately. The analysis works by first showing that any sufficiently accurate algorithm must strongly correlate with the sampled datapoints. Next, we show upper bounds on how strongly the output of the algorithm correlates with the sampled dataset. The method for upper bounding this correlation varies depending on whether given datapoint is considered public or private. Combining these upper and lower bounds on correlation yields the claimed result.
To obtain the Vlog (1/6) factor term in the lower bound, we use similar ideas to those in [SU15] CWZ21] However, the introduction of public data leads to complications in prior methods. As such, we show that by analyzing the correlation of the coordinate wise clipping of the algorithms output, we are able to get bounds that appropriately scale with the accuracy.
Proof of Theorem 11 Before proceeding, we introduce the so-called fingerprinting distribution which will be the basis of our hard instance for mean estimation [BUV14] DSSSSDSSSSS Towards this end, for any vector μ E [-1, 1] we define D,, as the product distribution where, for any j E [d]. sample has its j'th coordinate as 1 with probability (1)) and as -1 with probability (1 /22//2 As shorthand, we denote -
the distribution which samples vector from Dμ and then scales
I For notational convenience, for set &, we will also use (ni to denote the uniform it by V distribution over elements of the set.
The theorem follows from two theorems which have different restrictions on the problem parameters. In addition to the following two theorems, Theorem 11 incorporates the classic R statistical lower v bound that holds even non-privately. The first theorem we present holds for larger range of parameters but does not achieve the dependence on log (1/6).
Theorem 12. Let c
> 0, S 16n and A be an ()-D)-PA-DP algorithm. For any setting of < M < 1, if Unif([-M, M)) and (Spub, Spri)) R Dr it holds that
Va Uper
min
Vd Typbb nn(e - 1) }
E A.
[||A(S pub. Sprie) M(D) Ω Rmin
In application to Theorem 11 we use (e 1) <. 2e whenever S 1. The second theorem requires 2 ne but has the benefit of scaling with log (1/6).
TIC Theorem 13. Let 8 S 3dn C 1, d 2 1202ne, and Appb S 1200 log (1/(v)d))) and A an (c, 8P DP algorithm. Then there exists M > O such for μ Unif([-M, M) and (Sprics Sput)) R Dr
va
holds that
Vdlog (1/8) })
[1p Sprit) - ((D)]l] = Ω RRmin A.S.aa
E
Mauub
TC
crucial part of the analysis leveraging the so called fingerprinting lemma, which roughly states that any accurate algorithm given a dataset sampled from Dr must strongly correlate with vectors in the dataset. Particularly pertinent to our analysis is achieving such a correlation even when the components of the mean are much smaller than 1. Towards this end, we leverage the robust distribution framework of (DSS+15) to achieve the following version of the fingerprinting lemma.
Lemma 4 (Fingerprinting Lemma). Let M [0, 1] and p. be sampled uniformly from -M, M] [|[A(S) μIll= I a (for any μ E [-1, 1]²). Then one has
Let A satisfy IE SnDD
2 2d
avd M
E A,S,H
Σ (A(S), 14)
2M
3
Proof. In the following we treat A as deterministic function and bound E EE (A(S), p
3,1
This is sufficient to bound
E A.S.p
D (A(S), x; =1)] for randomized AA since the analysis holds for
16

---

any function (i.e. the distribution does not depend on A). Further, we start with the one dimensional case such that j R. Define g(u)
E
[A(S)]. We start by applying results developed in
S~Dn
DSS
15I.
E S.p
A(5)
a
2
1 11)
(1)) n2)]
((6)
E [x²] + +2 ((((1) - 1))1 (9(-M) + M A M
19(
2M
2 2/3 + 2183221100 (()(M) puua 19(- + MM + I9(M) M
2M
Above, (i) comes from DSS 15
Lemma 5] and (tt) comes from DSS 15 Lemma 14], which we We now have
have collectively restated in Lemma
19(-M) + M + l9(M) - MI
E S.p
A(S)
(xt
p)
2/3
+ 2E (()(u) m)
2M
19(-M) - M + 19(M) - M
2/3
2 (l ml |xd]
2M
IESDD -M [A(S)) + M + [ES.D [A(S)] M
2 2/3
2M
E [A(S)] - u4]
-2ME
SSDD,
Above we use the fact that |M| < M and the definition of
We can now extend the above analysis to higher dimensions. For μa E R the above holds for each J E [d]. For convenience define M (M..... M) Rdd. Summing over d dimensions have
3i 1t) )
E
A(S),
8,p
2d
E [A(S)] + M
1
E
[A(S) 1111, 2ME E [A(S)] [A(5)]=H[1) -111
2M
S--DMM R2
2M
#
SNDDA
2d
1
[I[A(S) + M]]
E
[[LAS)) M 11] 2M JE [|A(S) 1|11]
2M SwD 82
2M
S.DDat
S.y
2d
vd
Vd
E
[IIA(S) + M12
E
[[LA(S) M M1 22/M E [[A(S)) - m112]]
3
2M
SwD__
2M
S-.
S.
2d
avd
2M Vda.
3
M
This proves the claim.
We now turn towards proving Theorems 12 and 13 We start with the simpler proof of Theorem 12
Proof of Theorem 12 For our proof we will use a dataset of vectors in {+1}", and such the & bound on the data Vd. The final result will follow from rescaling by Vd
Let S = {xi, 22, ... (Spar, Spriv) ~ DD be the concatenation of the public and private datasets. We also define a = EE [[Suus Spric) - [M]]] for notational convenience.
Define the following statistics,
2, (A(Spubo Spriv) ,1, 11)
2 (A(S pub, Smi) - 14, 11)
17

---

where Suy is the dataset formed by replacing i-th data point of Spri with x ~ Dr We have,
E
Z
+
2,
(2)
A.S.N
T-yg +1
The lower bound proceeds by providing upper and lower bounds on the above sum. We first have
)
E
A(Sput: Sprie)
p4,
(x) 14)
B B[IlA(Spub: Sprie) 111//11
2 [x 1!)
an
where the first inequality used Cauchy-Schwartz.
For the second term in Equation
we utilize differential privacy. Specifically, FS1 Lemma A. 2
restated Lemma 3. gives that
72
Σ
Z,
Σ
B|Z + 2(e" - 11)/ Var(Z)) + 88d
È= Tipan+1
Amprio (et - 1)a + 8mpavöd.
Above that Var(Z') I 4a² since || p1 S 4. Plugging the above two in Equation yields,
E
Z: S (4mpri - 1)x + (mpp + a dMpub.
now use the fingerprinting lemma, Lemma E [(,, Ei p)) = 0. Thus
to lower bound the correlation. this regard, note
KALSyan Spic), Σ 24
))
avd
E
Z
= E
/
2 3
2M da.
2M
1=1
1=1
Plugging the obtained upper bound on the left hand side gives us,
2d
avd
4npav(E 1)x + &8 dd + a dripob
2
2M dda
3
M
d
avd
Ampri (c 1)a a dupbb
2M do
M
Vd
d
a 4Mpri -1) dupub
2M Vd
M
d
Vd
Vd
a min
Mvd,
M
Apriv (e - 1)
Mpub
d
vd
min
Mvd
24
Apriv (ee 11 nnub
Above the first implication uses the assumption that 8 that M Mvd= <
The last implication uses the fact
16/tpw
Vd M
factor yields the bound since M < 1. Rescaling by a Vi
R.
R
Vd
E. |||A(Spub Spev)) - -lll min A.S,p
24
Apeiv (er - 1)" Al
Observe that any setting of M 2 min statement.
vd Moine?
realizes the bound claimed in the theorem
18

---

We now turn towards achieving dependence on to prove Theorem 13 To do this, we leverage the the idea of filling dataset with copies of each fingerprinting code seen in previous work (SU15 CW721] However, in our case the introduction of public data makes this argument more delicate and leads to modified techniques for upper bounding the correlation statistics. See our discussion in Section B.2 for more details on why this is necessary.
Proof of Theorem 13
Let E [l|-A(Spub: Spiv)) p1ll, a² min
d (log(1/8) ne
d
and
Vigah
assume by way of contradiction that a² Let 3c
We set == - (a V m.) Let Unif[[-M, MJ S= (21,-.. km} ~ Drr Sample Spiiv Spub ~
1. log (1/lv Let
Unif ((=1,... Zm and denote the combined dataset S = (51,... , (Spub Spev). Note that as in the proof of Theorem 12 we are starting by showing a lower bound for the case where the data drawn from D, instead of R va Pus and will rescale at the end of the proof.
To prove our lower bound, we will provide upper and lower bounds on correlation statistics w.r.t. the intermediate dataset Sz. We will also introduce a clipping procedure which helps better control the upper bound correlation. In this regard, for each [m] define Zj (LA(Sppab Sprv) Mr - μt) where [t] M denotes the operation of clipping every element of to [- M, M). In the following, we will provide upper and lower bounds on E contradiction.
m Zi and use this to show that S a implies
Towards this end, we can apply fingerprinting lemma, Lemma 4 to the algorithm which outputs the clipping. For â > 0, E (lpuh, Sprve] M [all] S a, then this yields.
Lower Bound on Correlation
We now want to lower bound E Th Zj}
2d
avd
E
Z
2M AMVde Vda.
A.S.P
M
Now observe that
[AAlL Sprv) - 1|1l S E [[]AAS (punn Sprix) - -1ll
- EE
A(S A(Spub Spri))
1
Σ
+
-
Σ
m|
ZES,
ZES
< ox V
In the last step use the assumed contradiction that S a², Thus it suffices to set ā a" + +
Now by the setting M Va a and à <
Eqn.
3
implies
12
2d
d
d
E A.S.I
Z
2
80
(3)
3
4
3
Bounding the Number of Copies in the Dataset We now turn towards the more involved process
of upper bounding S. 1> Z,). To do this however, it will be first helpful to show that no datapoint
in Sg is copied into S too many times.
19

---

The first step is showing that no point is copied too many times into S. For j [m], let 2, =
{i E [n] : I, 2z}. Observe
m
F. E [m]
(T
1)M
PI (T+ 1)k)
3r2n
S m emexp
4m(1 1/m)
37 log (1/0)
mmxp
The second inequality follows from Bernstein's inequality for the sum of Bernoulli random variables
with mean 1 1/m and the fact that E 2 m k. Set V 3lo[[1/8] and note since S 1 and
8e log(dm)
log (dm) & log (dn) I log (1/5) (since S dm ) we have that r s Thus, denoting E as the event where no point in Sg is copied into S more than 3k times, we establish
P P = P E [m]: [2 2 3k} S
(4)
Upper Bound on Correlation Under our model, we assume that A must treat all data in Spriv as private. We will in fact only need to use the privacy property for subset of samples in Spri to prove the correlation upper bound. Let Ipriv S [m]] denote the set of indices s.t. j E Ipri if every copy of 2j sampled into the overall dataset is in the private dataset Sprie; that is I = {í (Vr E Spub)
zj Let Ipuh [m]] Ipri. Observe that Ipriv may contain indices for points in Sy which are never
sampled into S. We will this does not affect our analysis.
We have
E
Z
=
Σ (LA(Spab. JEZm
11)
Σ (LA(Spub Sprie M, 22 pu) SEIgih
The first term on the RHS can be bounded using the privacy property of A. For any fixed E Iprive let Spriv denote the dataset which replaces every instance of 2j in Sprie with a copied fresh sample from Dr.- By the above analysis, conditional the event E, at most 3k such points need be replaced conditional on the event F. Since A(Spub, Sprv)) is independent of 2j, by the Chernoff Hoeffding bound,
72
[<LA(Spob Spiv) (M, - 2T E] S exp
(5)
8dM2
Since A satisfies k-group privacy with parameters& < 3ke and 3 = Li we have
72
P PKIA(SSub. Spri) aa, 14) 2 E < cxp 8-
+ 3.
2dM2
Setting 5 = M /dlog (1/6), we obtain
E [2, E 5 + 2dP [2 2
M / (1/8) 2dc +
Mvd /lo (1/6) + 3ke 5 < 4M / /dlog (1/8).
The last inequality comes from the setting of k
log
and the fact that M 2 Ve.
36
Vonk
Repeating this argument for each E I we get
E
Σ
2
S
Σ Z
E P
[
mMdP [E9] 5mM /dlog (1/8).
TEI
JEI
20

---

The last inequality uses the bound established on each E [[2 E). E Iprvv above and the bound on P [E]
from Eqn. 4.
To bound the correlation the remaining vectors, have
E
Σ JEApe
Z3
<
BllLL Spriv 11
Σ jEZpun
(2j -5)
I 2M Appb.
Above have used the fact that [Zpuhl pubb because E Ipu only if at least copy of z; is sampled into Spub Combining the above we have
E
Z
$ 5mM / dlog (1/6) + 5Md
Combining Bounds:
The previously derived lower bound in Equ. establishes that
EjEz Zj +EJE, Z3
2 3 Using the above derived upper bounds we have the follow-
ing manipulations,
MVd m log (1/6) + drpub
15
(a" + vd/m) ( log (1/6) + dripub
IV
60
maylog (1/5) a" "iivddug dripub
v /dlog (1/6) m dv
Tpub
m
The second line above uses that M Vaa (a" + V Under the condition that Upub S
T202
Tppb < 120 log loggl/ (I/vvdd)) which is satisfied under by assumption in the theorem statement, we have
may log (1/6) + a" dd 2 120
v dd log (1/6) m.
Now applying the assumption d 2 1202ne
S 120 log(1/o] obtain
d
d
ma² Vlo (1/8) + a² Vd 2
120
d Vlooo (1/8)
a' 2 120 min
Tdpub
dy (og(1/8)
This establishes a contradiction, and thus 2 a
125 min
Rescaling by
R then yields the claimed result.
Vi
B.2 Discussion of Lower Bound Analysis
We here provide more details why the particular lower bound techniques present were chosen. Our aim for the following discussion is to clucidate some of the subtleties of leveraging the fingerprinting code framework when public data is present, with the hope that it will aid future work on the characterization of PA-DP problems.
One crucial challenge in developing the mean estimation lower bounds in Appendix B. is ensuring that the correlation sum, traditionally defined as [Eres (A(S), x - n)], scales with the accuracy, or of the algorithm. Previous work, such as (CWZ21) achieves this by setting the underlying distribution, D. to be mixture distribution which, for some p o(1), samples a vector with probability (1 p) and samples from the non-trivial distribution, D,,, with probability p. However,
now the variance satisfies
E z>D
||
E
[x] 2
< 2pR2 meaning that when public data present
21

---

holds that E[
x B -
2 v Piph
= o(
R < Migh
and one cannot hope to achieve the
Ryuh SESpp
anD
desired lower bound. Alternativly, by instead amalyzing the sum E Eves (A(S) μ. --)
seen for example [KU20], we are able to avoid sampling from a mixture distribution. Further, by leveraging the flexibility of the strong distribution framework from [DSS 15), we are able still
ensure [ = o(1), as needed for the SCO reduction; see Section B.3 These techniques lead to the result in Theorem 12
Unfortunately, with regards to obtaining the vlog (1/5) improvement in Theorem the property E [I)) - r0]] & does little to help establish the needed tail bound; see Eqn. (5) By clipping the
components of A(S) to to the range [aO(a), ((a),, we are able to able to obtain the desired con- centration. Unfortunately, this clipping technique in combination with the intermediate distribution, Unif leads to the restrictions that d 2 and 7pph S Idd(l/ These restrictions occur be- cause of the need for the "additional error" introduced by the intermediate distribution to be negligible. To see this, observe the intermediate distribution leads to E [I]-(()) [=ll] 2 since A(S) depends
on only m vectors from D,, and the analysis in the proof of Theorem 12 pprv 0) shows us that even non- non-private algorithms cannot do better on this distribution. We remark that [CWZ2T] avoids this issue, and hence the restriction on d and Rpub. because of the fact that one only actually needs | [A(S]] μll for the fingerprinting lemma to hold, and |E [A(S)] f4ll S E (IIAA(S) wll]-
However, after clipping is possible that | [LA(S)]M] all 2 || [A())
mll.
B.3 Missing proofs from Section
Proof of Theorem 7 We use the instance in [BST14]. f(w;z) = G x) and W {a E Rd ||ا||| $ 1..
By standard rescaling argument, we only need to consider G D 1. We
will consider the re-scaled data distribution used in Theorem 12 where {21, 2n} i.i.d. D, and the
dataset has x vā²j for j E n. Here μ ~ Unif([- M, M where M will be chosen later.
First note by Lemma we have that |P[]||||| / M 2
256 S
512 so long as d larger than some
constant. Define this event as E and E" its complement. Thus we have
E [T(((S): I(w = [TAA(S)) I(w"; D) P(F]
+B[L(A(S); D) L(w"; () E P[E')
1 BIL(A(S): D) :
2
Thus it suffices to lower bound the conditional excess risk.
The optimal solution under the aforementioned loss is w [AT since the constraint set a ball of radius 1. We can see that
L(A(S): D) L(w":D) = (A(S), p))
<-
||||| -11
11
||AAl| (1 (A(S), w²)))
||
1 - [|AA))))1
1
Il w|'1
1 1AAS)) w01l3)
2 2
|||4|| [[A(S)) ==
(6)
22

---

We will now lower bound [[A(S)) w"1 by using the lower bound for mean estimation developed in
Theorem 11
Let the mean estimate candidate is ja(S) j
MA(S). Under the event E,
7 - ml 2/33MA(5) 1
A(s)) - 14 + (V2/3M [m]])((S)|(
M
- 2M ||A(S)) - w w011² +
50
A 1
||A(S) w01 >
2M
512
The above follows from the definition of w" and since the algorithm's 's output is considered in a ball of radius 1, so ||-((S)| I
Combining the above inequalities
6 and then taking expectation we have,
|
1412
1
E -)
|a||
E
M
512
E
[|
pull
M
(8)
1024
2M
512
To bound [|| - 1 =1 observe
Blll ml]"]]
E[ll@ xll2 [|P[[]] + E,,,lll
- BB 14ll
[b + 4M2P[E")
Rearranging we have
M
Bl 1ll
[
1=11
128"
We will finish the bound by applying either Theorem 12
Theorem
13
Via Theorem 12: Set M = min
Under this setting of M, Theorem implies that
Siguh
the lower bound mean estimate distance satisfies E [l|ø
14ll]
M and thus E uul? [F] 2
2 128
Eqn. above. Plugging into Eqn.
( have
E E[L(A(S):))
L(w";
(ww: :)] Ω (M) Ω min
Upriv
/ Mpuh
Via Theorem 13
In Theorem
13
the setting of AM used is
v dog (1/0)
log
(1/LVano))
M
min
125
TEE
nopbb
nE
1
Vdl (1/8) min
<
30
nE
Reub
The inequality holds under the conditions d 2 120 and 7pub
Thus we have
120a log( log(1/[Vndd])
under this setting M that [|[p æIl] 2 M. Applying Eqns.
and (8) as the previous case
8
we have (providing the above conditions on d and Npub hold)
E EI((A(S):D) - L(w"; ; D)] Ω (M) = Ω min V log (1/8)
Y1e
Tlpub
23

---

Lemma S. For Uni we have that ||=|| E
22d
(3ln(1/2)
with probability at least
v3
1 1-7
Proof. This follows from standard concentration norm results. We have that,
2d 3
E ||=
dE
As in [ve18 proof of Theorem 3.1.1], we use the simple fact that | max( 5, 5²) for any I, 2 0, to get,
1
x² --11 1 >
V 2d
2d8
(1
v3
IP
||
=P
> 8
v3
v3
V2d
3
|211
P
1
> max 89)
2d
1
2
> max (2233)6
P
We substitute 8 = 26
and apply Bernstein's incquality for i.id sub-exponential random variables z? Since, E [-1, 1]. the sub-exponential norm S 1. Applying Corollary 2.8.3 from [Ver18], we get that,
3
P
2
max (8.(8)))
exp (-25ad) exp (-85
3
This gives us that
2d
v 2do
|2|
S exp (-88d/9)
v3
v3
Hence, with probability, at least 1 - y, we have that ||~|| E v2d + (1/7) proof.
which completes the
Proof of Theorem 2 We use the squared loss instance as in BST14 Section 5.2]; f(w; 2)
||0 = with ||||||
<
2X The loss is G-Lipschitz and X strongly convex on the domain of
unit ball at zero of radius
C Given datasets S {21 ......, 2, J. the population risk minimizer
2x.
simply the population mean (DD). Further, is straightforward to verify that the excess population risk re-scaling of the mean estimation eπror
E[L(A(S)) - min [(w)] = E [[A(()) 2=
Substituting the mean estimation lower bounds, Theorem completes the proof.
C Missing Proofs from Section
C.1 Proof of Theorem
Define the orthogonal projection matrix Px,.. = U Note that the feature vectors in Spev {UUT,, Vi, y:) Paiir are bounded. In particular ||UT z||2 = x (UUT)a )x = x Px S ||=/ since Px,. is an orthogonal projection onto span(W Spa)). Further, since t V., we have that there exists ve E W such that vi UT TT.. Finally, T Uw UUT i Px,. in E W since the range of Px W.
24

---

The privacy guarantee follows from the privacy guarantee of sub-routine A. For utility, we define w" E arg wew L(w; D) and i' E arg win Lww; U D), where D denotes the distribution which first samples from D then project using U Let i E W such that i' UW.
Note that from the GLM structure, ;(W"; D) = L(w"; D). We have,
L(ū;; D) DD) Lύū; D) Tw;; Spri)) L(w";; ;Ww"D)
+ T(w;; Spri)) - L(i"" ; D) + T(;;; Spri)) T( Spiie)
= 0 GRnmg (H) + Bv log (4/3)
Vppiv
+ ;(W"; ; + [vi;; Sprce) min Iww; Spri))
(10)
wEW
with probability at least - 8/4. In the above, control the generalization gap via uniform convergence and concentration for the fixed w" with respect to Spiv.
The last term L(w:; Spav) - min WEW L(w; Sprv)) is bounded by the guarantee of the private sub-routine with probability at least - 3/4,
[(A(Spnv): Spav) - min [(A(Spn)): Spav) (GG |.12| wEW
/VMpub log (1/8) + v log (4/3)
PprivE
Finally, for any w such that v* E UW, with probability at least -/22, from G-Lipschitznes, we have
L(W";D) L(w"; s L( D) - L(w"; (ww:D)) D) s G 1| w" w'112, S Sa,
where the last inequality follows essentially from Lemma and Lemma [ for Topub O max n² log(2/9)) min m (1puu (H) S xa² a To elaborate, the first step holds since w = Uw" and w" is the the minimizer of risk over W. Now, Lemma guarantees that for any w E W. there exists w in its a-cover with respect to |1-1| with N w" 12'1,, S a. To argue why spann-Xpub) is a-cover, from Lemma 6 we have that from any a-cover W, of W w.r.t I1-112.x,= we can remove elements which do not lie in span((ppu)) and still have an a-cover. Hence, superset used Algorithm which essentially is, Px,. W, indeed an a-cover.
The 7ppb we get is,
R log (1/3) a
min (m ( (H) S a²)))
pub = =0 max
log (2/3) 1
a oz )
= -
max D2 |
where in the above, we plug in the Rademacher complexity of bounded linear predictor, (M)
D X
Plugging the above Equation 10),
m
L
D)
DDw";D)
GD |
GD ||'|| Vlg (4/3)
B Blg (4/B)
v Tppiv
Vpriv
Tepris
Apub log (1/8) + Vlog (4/B)
GD ||-||| +0
Ga
Cpeiv
GD |X
log (4/3)
VVog (2/3) + log (1/8)
B / log (4/3)
=
+ GD2 |211
+ Ga
Tipiiv
aMirriE
v Ropie
log (A/B)
(log (2/3) + log (1/6)) 1/4
)
B
log (4/3)
=0
GD||>1|
Mprriv
V
Vpriv
25

---

where the above follows by setting a resulting public sample complexity is
This yields the claimed rate. The
log (2/3)
pub = =Ō 1>2 1| max
a²
a
=
Aprive
(log (2/3) log (1/6))2/2)
This completes the proof.
Lemma 6. Let H. be a a-cover of H. with respect 11-11,,,,m. Then, H. = H n spsan((pppl) ) is also an a-cover.
Proof.
Given two hi, h2 E H. we have,
1 Piuch
||1 h21l2,X,0
Σ
(h1(2;) - h2 2z;z))²²
(wi w2) T.. pub Pub Xpub Wyy
7dpub
where wh and w2 are the vectors corresponding to linear functions hı and h2 and Xpub denote the matrix of public feature vectors.
Given any E H. let denote the element closest to it in the cover H: we have, ||| - h1ll,,,,,. S ar Consider the singular value decomposition, Xub VEUT where U and are orthogonal matrices and Σ is diagonal matrix. Define h Pxpa. (h) UUTİ, h. Note that U is orthogonal projection onto span(Xpub) and Px,.> is the corresponding projection matrix. We have,
h T1112.x.0
1
(h T)
X Xhub- h)
Rppub
1
(h
Pxpo ( (h- Pxpo (h))
Tdub
1
(h
( (h-
Tluu
(h - 1i) UUS (h-h)
Tpuu
1
(h 1i) XT puh h))
Npuh
< a
Since by construction h also lies in span(Xpuh) this proves the claim.
C.2 Proof of Theorem
We state the complete version of this theorem and then present its proof.
Theorem 14. Let > 0, > and log (1/5). For G-Lipschitz, B-bounded satisfies (c,5)-DP. If the private sub-
non-negative H-smooth loss function, Algorithu [
routine À guarantees Equation {1) with probability at least - 3, then with Repub =
ò is most
(HD)) 2// (H L(Ww))) (1gg(()(1/66))12
with probability at least - 3, L(w; D) L(w"; D)
Gv/oo((188)
VHD |X
B log (8/3) Tiprio
H !| D
B log (8/3)
GD || / log (4/3)
[[w+; D)
Tlprie
Thpris
Tipric
VHD2 |2el G Tog (1/8)
2/3
D |2 /G (log (1/8)) 1/4 L(w" D
26

---

Ō (HD ( + VHnpmey Sprrl
Further, with npub
with probability at least
(log(1/6))
GyloR(1/0))
1 - B, for any W. L(w;; D) - [(W Sprie) is most
VHD |M
B log (8/3)
H 1 D
B log (8/3)
GD 1| Vlog (4/3)
+
+
Tppis
Dpuii
Riprir
Plrric
VHD? |2ll G log (1/8)
2/3
IT/AD [.e (log (1/8))
L(w: Spin )1/4
-
+
Dpprice
Aprice
where w² and w are population and empirical minimizers with respect to 'D and Spri respectively.
Proof of Theorem 14 The privacy guarantee follows from the privacy guarantee of sub-routine A. The proof of the utility guarantee proceeds similar to that of Theorem We define w² E arg min L(w; D) and i" E arg win L(u; DD). Let i* W such that w" U From the GLM structure, ; = L(w"; D). We have,
L(w; L(w"; = L(@; D) L(w: Sprv) + L (w; Spav) - L(w"; D)
S L(w: D) i(w; Spri)) [wi;; Sprv) :(((==:)
+ ;(w"; D) L(w"; D) + L(w;; Sprc)) ; Spri))
$ [(w;; D) L(w; Sprin) ) L( DD L(O"; Sprit)
+ L(b"; D) L(w"; D) + L(w; Sprie) min I(w; Spri)) wEW
(1I)
The last term T(ū;; Spri) min weW T.w: Spri)) is bounded by the guarantees of the private sub- routine with probability at least - 3/
V Mypb log (1/0) + /log (4/3) ))
L(w;; Sprv)) min [ww; Sprie) = GD [|
(12)
wEW
Uprive
To bound the term (D) ;(w":D) in Equation
apply smoothness to get,
L D) - L(w";
L(w" D) L(w"; D)
H
E
(,,( x)), (w0 x) - (w',z))
+ (w",, x) - (w" xx)?
2
H
E
(11 x))| 1100 x) (w²,)))+
1w0, x) (w" xx)1?
2
H
$
E
1,(("r 2)){ EENDA 110 .x) - (w0 ,.)1
+ E Kw0", .x) (w",, xx)²
H
2 HE (ww x²) /E [1 (w*,x)/
2
EDNDA 110" (10"22) ,w²,x)²²
2
< 2/ : + H
(13)
where the above holds for any 80 E H such that 8o E UW by optimality of d in W. 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 (Lemma 4.1
(SSIIO). The final step holds with probability 1- 1-3/2 from Lemma [ with nupb =
max Rd 12/()) min {m: log" (m))) (H) S a²))) together with that since W is an a-cover a
27

---

of H. together with Lemma
6 which shows that W is valid a-cover of W. Therefore, there exists
he E H. with ||A* h" 2p. a.
Further, applying AM-GM inequality, get
D) s 2I("=; + 2Ho?
(14)
The first two terms Equation (11) are bound via uniform convergence for smooth non-negative losses, (Theorem in (SSTT0) and Bernstein's 's inequality as follows; with probability at least 1 1 -3/4, we have,
[(;; D) -T(W;; Spri)) + ((w":D)) T.(w";; Spon)
=0
VHRR (H) +
log (8/3)
(VI(e) Spriv) + v L(wi"; :))
Piriiv
B log (8/3)
HO92 Tasie (H) +
ppriv
VHD 2
B log (8/3) Apriv
=
L Lii+; Sprie) + v L(wb; D)
EprivE
H 1| D
B log (8/B)
V Mpub log (1/6) + v /log (4/B) Pervv
+Õ
+ō GD 1|11
Eprive
ppeiv
VHD ||2|||
B log (8/3)
=
((
Aepriv
7prrv
H 11 D
B Blog (8/3)
VV npub log (1/6) + /og (4/3)
+
+
GD ||||||
EprivE
Πpeiv
Ppriv
VHD ||-|||
B log (8/3)
=
+ VHa+
v [(w";D)
narriv
H 1 D2
Blog (8/3)
v VPpub log (1/0)
Vlog (4/3)
+
+ Ha²
+0
GD ||||
Epriie
Rpriv
RprivE
(15)
where the second equality follows from Equation (22 instantiating the Rademacher complexity of linear predictors, concavity of x + v and AM-GM inequality. The third equality follows concavity of + v and Bernstein's inequality, the fourth follows from Equation (14) and AM-GM inequality.
Plugging the above, Equation
[3) and Equation
12 into Equation (II)
we get that with
Npub 0 (mxx D=
log(2/0) min { o²
m (Mpub) (H) s a² ) the following holds
with probability at least 3,
28

---

L( D) -[ww;;)
VHD ||
B log (8/3)
WHat
v ((w=:D)
Eprivc
npriv
H 11121 D +0
B Blog (8/3)
[VPpob log (1/6) + Vlog (4/3)
+ Ha?
+0
GD [|2||
Uprive
Aprie
Apriv
VHD ||
VHD ||
B Bog (8/3)
(l
Mpriiv
Vrppbb
Repriv
+
D H 2
HD2 1|11
B log (8/3)
0 GDD|
V Vlluh log (1/5) + log (4/B)
Uprive
7puh
Ppriv
Aprive
(16)
VHD |||||
B log (8/3)
=
/ DDw=:
Apriv
H 11 D
B (8/3)
GD ||-81| Vlog (4/3)
+
ApriiE
ppriv
P
VHD* ||11| G GV log (1/0)
2/3
/ ||-1|| /G (log (1/5)) 1/4
L(w"; 1)
+0
PprivC
The public sample complexity is,
Nlub =0 (HD 11/1)/2)// (2Pp))//(Mpriee22 (nprive22/3
VH / L(w"; D)
(2/3 (1/5))1/3
G Gvoog (1/5))
29

---

This completes the first part of the theorem. For thee second part, we start from Equation (T6).
L(ū:D) D) & L(w"; +
VHDII
VHD |
log (8/3)
VL(w=:))
Viriive
Ppri
H 1112112 D²
HD2 1111
B log (8/3)
+0
E
7ppuh
Ppriiv
v Ppub log (1/8) /log (4/3)
GD || +0
C
S [((";;) + +
VHD
VHD I
log (8/3) Uprriv
L(w=;; D)
Vmprive
Viuuh
H 11 D
HD2 ||
B log (8/3)
+
C
Npub
Apriv
v Ppub log (1/8)=
/log (4/B)
GD |||l|| +0
epriie
<
L(w"; Spriv) +
VHD |||||| Vipiiv
HDDI ||
B mpeiv
log (8/33)
)
v [[(i0; Spri))
v Apub
H |2'1| D
HD2 ||
B log (8/3)
+
E
Tppb
Tdpriv
Mpub log (1/8)
/ log (4/3)
GD ||| +0
p
VHDII ||X|||
B log (8/3)
L ("; Spriv) +
((W+)))
Vpriie
Upriv
H || D²
B log (8/3)
GD ||
log (4/3)
+0
+
Cprri c
Upriv
Depriy C
VHD2 | G Gooog (1/8)
2/3
H | VG
(log (1/5)) 1/4 L(W; D)1S4
+0
+
E
p
where the second inequality holds form optimality of w*, the third from uniform convergence, Theorem 1 in (SSTIO and AM-GM inequality, and the last by plugging in the following public sample complexity.
/ Vinpree / /i(w" Sprv)
(HD |121)))2/3 (nll) 2223 G2/3 (1/8))1/3
Apub =
Gvlog (1/8))
This completes the proof.
Theorem 15. In the setting of Theorem 14 with the additional assumption that the global minimizer of risk L, w" lies W, we get that with Tlpub Ö (
(265((((1//8)77 with probability at least
30

---

1- B,
L(W:D) =[(":D)
VHDDI |2 R
log (8/3)
H 1| DD
B Bog (8/3)
v /L(w=: +
+
Ppriir
mprive
Aprii
GD [|*1 v Vlog (4/B)
(VHLD |211 GV log (1/6)
2/3
+0
+0
EprivE
Further,
L(W;D) D) - -[(W"; Spriv)
= VHD || Ppriic
B Bog (8/3) Aprii
H ||-11 Ppprive
D2
B Blog (8/3)
Liw=; Spmi +
Upriv
GD |2 Vog (4/B) +0
(VHD2 || G /lo (1/8)
2/3
+0
Eprive
Tppri
where w" and To' are population and empirical minimizers with respect to D and Sprie respectively.
Proof. The proof is almost identical that of Theorem [5 We repeat the steps pointing out the differences and how the expressions change. We continue till Equation [2 Next, we apply smoothness which results in the key difference between the analyses.
L(ύ";)) - DD) L(w"; ;.:0D:]]))) D) L(w"; :D)
H
E (d/((10 ,x)), (w0", x) (w", ,z)) +
kw x) - (w", x))
2
(E (6 x2))x/ 10 -w") _
H
[wo x) - (w", xx)1?
(VL(W": ; D), w0 ww) Ha²
Ho²
where last equality uses the fact that VL(w": () 0 since w² is the unconstrained minimizer. Continuing, we get,
L(W;; D) - L(w;; Spri))
+ L(u";)) ;D) - :Sivv))
=
VHD ||'||
B log (8/3)
/ ((w=:))
EprivE
npriv
H 2 D2
B log (8/B)
(puhh log (1/5) + Ho² + Vlog (4/3)
+ Ô
+0
GD |||||
Uprive
Upriv
Ppriic
31

---

This yields,
L(ū; D) L(w";D)
VHD ||2||
B log (8/3) ppriv
I(w=:D)
Apriic
H 1|211 D
B log (8/3)
(Vipub log (1/8) + Vlgg (4/3)
+0
Ha?
+0
GD
Uprivv
Upriv
Oprive
VHD ||||| Aprive
log (8/3)
((w=;D)
Ppriv
H [11211211 D=
HD2 1|X|
B Blog (8/3)
Nyub log (1/0) + Mog (4/B)
+0
GD GD||
Eprriv
Upuh
Plpriv
Apriv
VHD || Upprice
log (8/3)
112111 DD
Blog (8/3)
V [(w=;:D)=
Pprriv
1priiv
Upriiv
GD ||
log (4/3)
VHD2 || G Gvlog (1/8)
2/3
+0
+0
Pprii 6
Aprive.
The public sample complexity is,
(HD) ||211)2233 (Mprin c)2/3 G2/3 (1/8))2/3
npub Ō
The second part follows similarly.
C.3 Lower bounds
C.3.1 Proof of Theorem
To establish the GDI X
term in the lower bound, we consider a one-dimenisonal problem where the loss 0,(3) Gyÿ and marginal distribution D2 the point distribution on ||-x'| such that the overall loss is E [e(w, (I, v))l = E =||x'||G). We further set W = [-D,, DJ and consider D, to
v
be the distribution which with probability [ 1] (1+ /) and ly = for some [-1, 1]. Note the minimizer w* = D [x] achieves population risk -uGD|| Classic results in information theory establish if μ is sampled uniformly from {= Von ( J. no algorithm can estimate the sign of μ with probability better than 1/2 (see [Duc23] Section 8.3]). Thus it must be that for any algorithm EAS [L(A(S);)) minwerd L(w; D)] [GD]
w)/2
The GD | min
term in the lower bound is essentially corollary of (ABG+22 Theorem 6]. We provide further remarks here. The loss function used is,
Vize
E(w; (z, y)) = on (wr, x)) = ly (w, xx)
Define d' = min ne) and p = min (1, d' ne as: with probability 1-p. 0. otherwise, vectors. The (unknown) conditional distribution of the response y is as follows. Sample "fingerprint- ing code", z' E {0, 1) with mean y' E [0, 1]dd where each co-ordinate μ', Beta(0.0625,, 0. 0.0625) i...d. Embed z' in d dimensions as z and let yu be the corresponding mean vector. Finally, define v bounding the ability of any differential private algorithm to estimate the fingerprinting code
The (known) marginal distribution Dx is described
Unif (| {e)); where e, are canonical basis
D(a,z) The proof in 22 Theorem 6] then proceeds by lower bounding the loss by
32

---

Since the rank of E [xx = d', the result [BG 22
Theorem 6] then yields a lower bound on
InDx
the unconstrained excess risk,
vd
EASS L(A(S):)) - min Lww; (w: = Ω GD ||]|
min
wER"
TE
ThE
but also guarantees that the global minimizer has norm most D. Thus, we achieve the same lower bound for EA. (L(A(S);; D) minwew L(w; D)] by setting W to be the ball of radius D.
C.3.2 Proof of Theorem
The proof uses the lower bound instance in the DP-SCO lower bound with public data, Theorem [ We consider the case where D, is the point distribution on 1. Then for any E y..== {1}, the loss function is then f(w; (I, y)) - y (w, 2) (w, æt), in Theorem Hence, labeled and unlabeled sample have the same information. We also set W to be the ball of radius D.
Assume by contradiction there exists
(e, (e.6)-PA-DP algorithm, A, which achieves rate O (ADDIZI1 1 + (ogg(1/6) with o(ppice/ / log (1/6)) public samples. Since Mip
gives a lower bound on = o/ log (1/6)) and = w(re), Theorem E [[(( puh; Spriv; D) min (I(w; D) of
papu
GD min
v log (1/8)
[GD|E2]
Vog (1/0)
npab
Epriv
v Pppric
Since S 1, this is contradiction.
D Missing proofs for Section 4.2
D.1 Proof of Theorem
Proof. The privacy proof follows from the guarantee of exponential mechanism [MT07]. In par- ticular, the sensitivity of the score function at most 2 min (B, GR) where the first follows Age
from the loss bound of B and the second from the Lipschitzness and bound predictors. Let h* E arg min L(h; D) and ht E arg min T.hh; D). From standard analysis based on uni- form convergence, we have
Lh,; D) - L( L(h; D) - TT(h;; Spav) ) + L(t,; Sprv) ( DD)
S sup NEH
(L(h; D) - L(hh; Spriv)) + L(h"; D) L(h";D)
T.(h;; ;priv) =((h"; + T.(To; Sprv)) T.(h:: :Sovn))piv))))
(17)
L(h; D) L(h;; Spav)) + L(h"; - ;
sup
hEH
-(h; Sprie)
min L(h; Spriv) NEW
(18)
B BB log (4/B)
2G (H) + O
Apriv
min (B,GR)(log (174)) log (4/3))
+ L(h::D) - D(h";D)
EprivE
(19)
where the above holds with probability at least 1- 3/2 and follows from guarantee of exponential
mechanism (MT07) and uniform convergence (SSSBD14), see Theorem 16). We further have that log (H)) Ōffataa (H)) from Lemma
33

---

For the D( (D) term, we have
I(h':D) L(h"; - L(h'; D) D()"
s h (x) (z)x
- G GVE/Eeo -1-
S 2Ga
where the first step holds for any h* H by optimaility of h over H. the sec- ond holds from the G-Lipschitzness of the loss function, the third from Jensen's in- equality. The final step holds with probability 1 3/2 from Lemma with upb O max
R² (og(33))) min {m log' ( (H) S <a²))) together with the fact that since H. is a²
an d-cover of H. hence there exists h E H with ||:- 11 2. S aa.
Plugging the above in Equation 19
we get with probability at least 1 - B,
L(h; D) - L(h"; D) < 2GR (H) + O (Bylog log (4/3)
Rpriv
min (B, GR) (fatea (H) + log (4/3)) + 2Ga,
+
éprie
which finishes the proof.
For any G-Lipschitz, B-bounded loss function, any probability distribution DD over x V. given i.i.d. samples from S, with probability at least B. the following holds for all h H.
Theorem 16. /SSBD14/ Let 7 S
[(h: D) L(h; S) < 2G (H) +0 B
log (4/3)
m
Proof. This is a classical result in learning theory which follows directly Theorem 26.5 in SSBD14 together with the contraction lemma (Lemma 26.9 (SSBD14) for Lipschitz losses.
Lemma 7. Let H. be an a-cover of H. with respect to 11-11,,x,.
The size of is bounded as,
log ((P))
2R
s fat (H) log
where e is an absolute constant.
Proof. This follows directly from Theorem g
log (ol)) = -N (H, a; Spub) S No (H, a, nppb)) I fatea(()) log
(2R
Proof Lemma 1 For H. let arg ge || hl12.Xm
Since 77 is an c-cover, this
gives us that ||/ hl12. S T. We have,
| h112pp = h(x)) - h(x))
= h(x) h(z))
Σ
((xx) T((x)
Σ
((x))
T((x)
Uppa
Uppa Spu
Spen
< sup beи
E h(xx) - T(x²)2
Σ
[k()) - h
+72
Apub
Spe
34

---

The first term above can be seen uniform deviation between the empirical and population risk, of another prediction problem, with squared loss, the the realizable setting (with the responses generated by h). The squared loss is 2 -smootth and non-negative, so we can apply result of Theorem in (STTTO) instantiated in the realizable setting, which gives us that with probability at least B,
R² log (1/3)
|/ 11-h112.0. O log" (npu) R mpn (H)
)+ -
pub
Choosing Puub such that Alpub O max the claimed result.
R² log(1/0) min { m (m) (H) S a²})) (
we get
a
D.2 Optimistic rates with smooth non-negative losses
Algorithm aachieves optimistic rates on risk depending on relizabilityfineepolaaiion conditions, that is, whenever ; :D) or [(h; Spri)) is small.
Theorem
17. Algorithu
with
2B
satisfies
e-PA-DP. For nppu
O maxx ability at least we have
R² 129(2 min m =ogg (m))9 (H) s aat)))
< oo and any > 0, with prob-
a
B log (8/6)
T.h: D) [(N: ò
VHRR (H) + HH
TT(h=: D
Aprri
B log (8/3)
B(fat (H2 + log (4/3))
+ Ö
HM9 Mywn (H) Ho² +
Ppri
nprive
I(h:D) T 5
v VHR (H) + VHa +
B Blog (8/8)
T:(fi": Spri))
Pppri
B Bog (8/3)
+ Bifat (H) + log (4/3))
+
HR? (H) + Ha²
Pepriv
Aprive
where he and ho" are population and empirical minimizers with respect to and Sprit respectively, and is absolute constant.
Proof of Theorem 17 The privacy proof is the same as that of Theorem 7 For utility, let h² E arg min Lh;; D) and h² E arg min L(h; D).
We start with the proof of the first part of the theorem. We have,
L(,;D) L(h"; D) L(h; D) L(h; Spriv) + L(hi; Spriv) (hh;D)
s Lh; D) L(h, Spric) + L(h;; Spriv) L(h"; DD)
L(h": D) L(h": D) L(h; Spri)) I(h" Spriv)
< [h:: D) i(h; Spmr) [Lhh: :D)
I[h²" :Srii)
+ L(h; D) I(N": D) L(,; Spri)) [(hh: ;(rin)ppri))
(20)
From the guarantee of exponential mechanism together with log (1il) = Ō(fatea (P() from
Lemma 7 we have that with probability at least - 3/4,
B(log (1#)) + log (4/3))
I(h; Spev) i(h"; Spiv) ) & i(h: Sprvv) min L(h; Sprc)) = O
hER
RgrivE
B(fat (H) + log (4/3))
=
(21)
PprivE
35

---

For the :(h";D) :) L term in Equation (0 we apply smoothness to get.
L(h:D)) 100---1 - - : D) D)
H
E
(x), (( (x))))
hr (x) h²(=))²
2
10 (x)) (x)) h2' (²) + H
hr* [x(x)) h((0))
$ E
H BENDx [1(xx) - h (1))
B
(h)())))) BANDA (1(x)) h (1))
H BENDx (^(x) h² (x)]
hr 2 HE (h- (t) -x))))
2/ ; Ha?
(22)
where the above holds for any h- 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 [SSTIO] The final step holds with probability 1-3/2 from Lemma [ with
nta log(2/8) min {m: log (m)9?, (H) S <a²))) together with the fact that since H is an a-cover of H. so there exists h² E H with ||=- - 1t 11112,, 12.0 aa
Ppub =0 max
An application of AM-GM inequality further yields,
: s 2L(h": + 2Ha²
(23)
The first two terms in Equation 20) bound using uniform convergence for smooth non-negative losses, Theorem in [SSTIO and Bernstein's inequality as follows; with probability at least B/4 we have,
Ll::D -T(h;; Spri)) + T,hh; ( - T((h"; Spacc)
=
v VHRR (H) +
B log (8/3)
(VI( v L(v:D)
ppri
B log (8/B)
+
Rma (72)²
Apriv
log (8/3)
θ
V HHRna (H) +
[hh Sprc) + [(ht;)))
mpriv
B log (8/3)
B(faton (H) + log (4/3))
+
HRnya (H)² +
+ Ô
npriv
Epriv
B log (8/3)
v VHR (H) +
L(h+:
Tepriv
B log (8/3)
B(fat,n (7) + log (4/3))
+ Ô
H9 (H)2
+0
upriv
TépiiE
log (8/3)
VHRnaa (H) +
D)
T2priv
B log (8/5)
B(fatcc (H) + log (8/3))
+ Ô
HDRna (H)2 +
Pprivv
Tirii
where the second equality follows from Equation 21 concavity of x + V and AM-GM inequality. The third equality follows concavity of x v and Bernstein's inequality, the fourth follows from Equation (23 and AM-GM inequality.
36

---

Plugging the above, Equation and Equation 21 into Equation 20
yields the following with
probability least 1 B.
I(h:D) D) D)
B log (8/5)
ViR (H) + VHa +
D()":D)
(24)
Upriv
Blog (8/3)
(ffatea (H) + log (4/3))
+ Ô [199 (H) Ha² +
+
(25)
Upriv
AprivE
This completes the first part of the theorem. For the second part, we proceed from Equation 25 onwards
L(::D) S L(h:D) + [VIRRRma (H) + Haa+
log (8/3)
L((h:D)
pppriv
+0 [1 (H) + 1aa2
Blog (8/8)
Bffatea (H) + log (4/
Aprriv
Uprive
$ L(h:D) + VHRR (H) + VHat
B log (8/B) Periv
v V(hrt:)
Blog (8/B)
B(fat (H)) + log (4/B))
+0
(H)
Ho
Apriv
Rprive
< L(h:; :Spriv) + (VHA (H) + V +
log (8/3)
I(hr;Spaic
Aprri
loog (8/3) B(fatea (H) + log (4/B))
+ +0
HHR (H) Ha²
Apriv
Rprive
where the second inequality follows form optimality of h², the third from uniform convergence, Theorem (SSTT) and AM-GM inequality. This completes the proof.
D.3 Proof of Corollary 2
We use the result from GRSI8 restated as Theorem 10 Further, note that range bound on the hypothesis class is simply S || = Ry. Instantiating our general result Theorem with the above together with the relation between fat-shattering dimension and Rademacher complexity (Theorem yields the following excess risk bound,
Lh::D) min L(h; D) hCH
G
|||
log (2) M 1)II M RS
B log (4/3)
B
B log (4/3)
=0
+
Vpdriv
/ipriiv
(BG2(22 log (2) M 1)2 1
(TT R2 2)
1/31
+
B( (2l2go(2)) 2111 R2)² 1/3
where in the above, we set a
Gogue
37

---

The number of public samples then is
R log (2/3)
min (m log (m J (H) S d21)
Rpub =0
a²
log (2/3) M
=
||21|
max R2)
a² a2
j=1
(1221) III
R5))
(1 Mppiv 2/33 M 1/3
log (2/3)
j=1
D.4 Proof of Corollary
Note that R < D || Further, have KSTO8 FGV17
D ||
Fmm (H)
m//r
Moreover, we have from Theorem 9 for any a > Rm (H.).
f - Rm (H)
a²
Choose Puhh and (log (Mpab)) Rops (H), to get that fat,,(H) = Ô (Npab). Plugging this Theorem we get,
GD |
GD Vlgg (4/B)
B Bog (4/B)
L( D)
min L(w; D)= =0
wEW
Upriv 1/r
Vilrriv
Perriv
GD ||
Plpub Aprive
log
(4/3)
Ppub 1/r
Pprive
Vlog (4/3)
log (2/3)
log (4/B) nppiie
)
GD ||-|||
+
Apeiv 1/r
VPpav
(nprive) r+
B / (4/3)
0
Vpriv
where the last step, we plug in 7pub
0
log (2/3)). yielding a
The number of public samples simplifies as,
(Mprr) न
Ppub = =0 -Ommxx maax
R12 log (2/3)
min {m log"(mn)) (m)orz ( (H) S a²))
a²
Ö (Rpriie) FII log (2/3))
which is satisfied from our choice since r 2 2.
D.S Additional Results
Corollary 4. In the setting of Theorem
7 together with X
{or E Rd
:||=|| S |
12
1/3
and H = ( (w,z) x X, ||w]| S D}.
With
and Tlpub
Mori
Ö ((D 2/1 (npri log (2/8)), with probability at least
3.
GD | Ppriv
(
D2 11
1/3
B (4/B)
B
B llog (4/3)
L(h D) min (hh; D) = δ
+
+
ke7t
v Aprie
Tepriv
38

---

Proof. In this setting, we have that R S D || Further, it is known KST08)
D2 121221
Ri (H) (H) =0 (2
D ||-1||
fat, (H) (H) =0
a²
vm
Plugging this Theorem 7 we get,
L(h:))
min L(h; D) BEH
=0 GD || Vpri
B B (4/B) Aprv
min (B, GD (21I ||
+0
+
B log (4/3)
+ 2Ga +
GD
(D2I1x)P))
D2 ||x1
1/3
Bylog (4/B)
B Blog (4/3)
-
+
+
v Apriv
Rgriiv
Mpri
ndpri
1/3
where in the last step, we plug in =
The number of public samples simplifies as,
R² log (2/3)
min {m log" (m) joR (H) S a o21))
Puub =0
max
a²
log (2/B) 1
D2 | max =
a²)
= = 11011111)3// (01(111211)) (1 2/3 2/33 log (2/3)
39

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Claims made are given in Sections 3 and proof's are provided in the Appendix
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The specific assumptions made are detailed in the preliminaries and theorem statements.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
40

---

Justification:
Statements are proved or cite a relevant reference. Many of these proofs can be found in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: There experimental results.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
41

---

Answer:
[NA]
Justification:
There is no associated code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /pipp/.ccppullc/guuiii http:///.......ided//deeeeeaaaaa CoodeSubeeiieeeeeeeeee ssi asiinnolle onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: There are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: There are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
42

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
There are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The theoretical nature the results means there are minimal ethical concerns.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The theoretical nature of the work means that any societal impact would be very indirect.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
43

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No such assets are used as a part of this research.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: No such assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
44

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: No such assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No human subjects were involved.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No human subjects were involved.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
45


Reviews:
[{"review_id": "BZ1rtjSZsv", "reviewer": "Reviewer_42Zi", "summary": "This paper studies the effectiveness of using public data to assist private convex optimization. Private convex optimization gives the solver query access to a convex function $f:W\\times X \\to \\mathbb{R}$ and samples $S$ drawn i.i.d. from some unknown distribution $D$. The solver is asked to find some point $w\\in W$ that minimizes the population risk $\\mathbb{E}_{x\\sim D}[f(w,x)]$, but to do so in a manner that is private with respect to the sample $S$. This is an important problem that has received much interest in the community. The notion of using public data that one expects has been drawn from the same distribution has been explored earlier, and the authors continue this line of work.\n\nThe main contributions of this work are:\n1. Stronger lower bounds than prior work showing that in the general setting even for approximate DP there is a dependence on the dimension $d$ of the sample space $X = \\mathbb{R}^d$ (typically one assumes data is drawn from some bounded $d$-dimensional ball in the DP setting). They also complement prior work and extent a lower bound for the pure DP setting that held previously only for a limited range of values. These lower bounds show that the naive approach of either treating all data (public and private) as private or ignoring the private data and using SCO on public data is asymptotically optimal.\n2. A new algorithm for the unlabelled setting showing that one can gainfully use unlabelled public data to perform dimension reduction for labelled private data and achieve a risk bound that has no dependence on the ambient dimension. This is in contrast to the labelled setting where their lower bounds showed a dependence on the ambient dimension $d$.", "questions": "There is one point that I don't understand, I think I might be confused about the nature of the results. In principle, if one treats public labelled data as unlabelled and attempts to follow a similar approach of using them to learn a good lower dimensional representation of the labelled private data, is it easy to see why this does not lead to an asymptotic improvement over ignoring the public data entirely, or treating it as private?", "limitations": "No additional limitations need to be discussed.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. I think this problem is well-motivated and of interest to the DP community.\n2. The asymptotic separation between the labelled and unlabelled settings is interesting, and the improvement of lower bounds compared to prior work is also good to see.\n3. The paper is in general well-written and easy to follow.", "weaknesses": "1. I think that in this case it becomes important to understand the exact constants that occur in the upper bound in the labelled case - even if asymptotically one does not hope to see any improvement over the naive strategies, I would imagine that in practice one still does gain some improvement in the public case. Maybe this point could be better made.\n2. Although the analyses seem to be formal and strong (and relatively assumption free), there are not necessarily any new high-level ideas in this work (if you would like to emphasize any new highlights or unexpected outcomes that would be great to see though). The technical work is still interesting however.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "* *Response to Weakness 1:*\n\nWe completely agree exact constants are important here, and we will make a note to better emphasize this. However, we do not believe this devalues the importance of characterizing the asymptotic rates,   as we do in our paper. Most of the existing understanding of (private and non-private) optimization is in terms of asymptotic rates.\n\n* *Response to Weakness 2:*\n\nMany of the novel ideas in our paper are more technical in nature. For example, in our lower bound proof, while we leverage the pre-existing framework of fingerprinting codes, our proof involves several novel steps to overcome the challenges of applying this framework to PA-DP settings. For example, we observe it is crucial to use fingerprinting distributions with small mean and also rely on a clipping analysis when getting the $\\sqrt{\\log(1/\\delta)}$ improvement in the lower bound. This analysis is different from the way fingerprinting codes have been used previously. We include further discussion of these novelties in Appendix B.2, but did not have space to include this in the main body. We can include this in the final version using the extra space given.\n\nWith regards to the proof ideas in the unlabelled public data section, while it indeed bears similarities to existing work of [[ABM19]](https://dl.acm.org/doi/pdf/10.5555/3454287.3455215), which we have acknowledged in the paper, there are several novel components in the analysis; for instance, the analysis of the size of the cover required. We perform this analysis by posing it as another supervised learning problem in the realizable setting with squared loss.\nUsing optimistic rates for the squared loss [[SST08]](https://papers.nips.cc/paper_files/paper/2010/file/76cf99d3614e23eabab16fb27e944bf9-Paper.pdf),\nwe achieve fast $1/n$ rate for this intermediate learning problem, which is crucial in achieving optimal rates. This is in contrast to the analysis in [[ABM19]](https://dl.acm.org/doi/pdf/10.5555/3454287.3455215),\nwhich is done via VC-dimension based counting arguments.\n\n* *Response to Questions:*\n\nThis could lead to an improvement over ignoring the *public* data entirely, but will not lead to an improvement over ignoring the *private* data entirely. That is, one incurs a $\\frac{1}{\\sqrt{n_{\\text{pub}}}}$ penalty due to the error in the subspace approximation made using $n_{\\text{pub}}$ points. Note that this is never better than the $O(\\frac{1}{\\sqrt{n_{\\text{pub}}}})$ rate achieved by ignoring the private dataset and running some optimal non-private optimization algorithm.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sElngQN4mQ", "reviewer": "Reviewer_VXJL", "summary": "The paper investigates a public-data-assisted differential privacy problem. Firstly, for labeled public data, the author introduces a novel mean estimation lower bound of $\\tilde{\\Omega}\\left(\\min \\left{\\frac{1}{\\sqrt{n_{\\mathrm{pub}}}}, \\frac{1}{\\sqrt{n}}+\\frac{\\sqrt{d}}{n \\epsilon}\\right}\\right)$. Secondly, when considering unlabeled public data with $n_{\\text {pub }} \\geq n_{\\text {priv }}$, the paper presents a dimension-independent rate of $\\tilde{O}\\left(\\frac{1}{\\sqrt{n_{\\text {priv }}}}+\\frac{1}{\\sqrt{n_{\\text {priv }} \\epsilon}}\\right)$ given $\\tilde{O}\\left(n_{\\text {priv }} \\epsilon\\right)$ unlabeled public data. Additionally, the results for unlabeled public data are extended to general hypothesis classes with bounded fat-shattering dimensions.", "questions": "For Algorithm 1, why does the author perform the projection before applying the differential privacy subroutine? What is the function of the projection here, or how does it help the result? I am not sure if it is because the author uses the unlabeled dataset to construct a data space.", "limitations": "Refers to the weakness and questions.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper provides a technically solid and well-structured analysis of the public-data-assisted differential privacy problem. The most intriguing part is the Private Supervised Learning with Unlabeled Public Data. In this setting, the paper leverages $n_{\\text {pub }} \\geq n_{\\text {priv }}$, showing a dimension-independent rate and demonstrating that an increasing number of unlabeled public data cannot improve the results because unlabeled public data can only reveal information about the marginal distribution.\n\n2. The emergence of the dimension-independent rate from \"public data can be used to identify a low-dimensional subspace, which under the appropriate metric acts as a cover for the higher-dimensional space,\" is particularly interesting. Could the author provide more explanations and insights on this?\n\n3. Algorithm 1 projects the private data to an orthogonal space, derives the solution, and then projects back to the original space to obtain the result. This approach is novel to me, but I have some questions below.", "weaknesses": "N/A", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "* *Response to Questions:*\n\nDifferentially private subroutines often incur some penalty proportional to the problem dimension, $d$. Thus, at a high level, the reason for performing the projection before applying the DP subroutine is to ensure that the penalty does not scale with $d$.\nIndeed, we show that one can reduce the dimension of the problem (using public data) to the extent that, no dependence on $d$ (the original dimension) shows up in the final rate. This is because the effective dimension after projection does not exceed $n_{pub}$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1KX0xHZy2P", "reviewer": "Reviewer_9k4B", "summary": "The paper presents some new lower bounds for public-data assisted private SCO, when some public examples are available, either with or without labels.\nIn the unlabeled case, a simple algorithm for GLM assisted with unlabeled public examples is presented and analyzed (and it is shown that this removes a dimension dependent term, similar to previous results).", "questions": "Please see questions in the weaknesses.", "limitations": "As mentioned above, the paper should be clearer about its assumptions, regimes in which its bounds are tight, etc.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "- The problem is important.\n- The new results shed additional light on the limits of public-data assisted private SCO.\n- In particular, they partially closes the gap between lower and upper bounds, in certain regimes of $d$ and $n_{pub}$.\n- There is good commentary following most of the results.", "weaknesses": "- The presentation is poor. Little effort was made to summarize the main results (and how they improve on previous bounds) in an easily accessible form. This could be remedied with a table summarizing assumptions, new and existing results, conditions on $n_{priv}, n_{pub}, \\epsilon, d$, ranges in which the bounds are tight, etc.\n- For example, it was unclear from the abstract and introduction in which regimes the new bounds are tight. This is only discussed later in the text. Similarly, there are boundedness assumption that should have been clarified early on.\n- In Theorems 3, 6, 7, it seems there are missing conditions on $n_{pub}$. For example, according to the theorem statement, nothing prevents one from taking $n_{pub} = 1$, or even 0, and it seems one would still get the improved bound. This should not be the case. Please clarify in the rebuttal.\n- The significance of Theorem 3 is unclear. Similar algorithms and similar improvements of dimension dependence were obtained in other works. The authors mention line 245 that their result avoids \"many of the strong assumptions seen in previous work\" without giving any details. What are these assumptions and how does Theorem 3 compare to existing results?\n- Corollaries 2 and 3 are frankly hard to interpret, and their significance is unclear to me. Maybe more effort is needed in this section.\n- The general message of the paper, that \"more sophisticated attempts at leveraging public data will yield no benefit\" (in the labeled case), should be toned down a bit. While the new bounds indeed show some fundamental limits, these come under assumptions, and improvements were in fact shown for certain classes of problems like linear regression, as in some of the papers that were cited lines 28-29, (most of these were cited without discussion unfortunately).\n\nMinor:\n- What do the authors mean by \"the non trivial regime $n_{pub} = \\Theta(n)$ and $n_{pub} = o(n)$\"? Do you mean either of these is true? (if so, it would be clearer to use or, not and).\n- There are minor formatting issues like a broken reference line 359 and some typos.\n- In the discussion following Cor.3, how do the $log d$ terms appear?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "* *Presentation:*\n\nWe will add a table to our updated version as you suggest and clarify tightness of the rates. Please see the global response PDF for this table.\n\n* *Missing conditions on $n_\\text{pub}$ :*\n \nTheorems 3, 6, and 7 claim the rate is achievable given access to *some* number of public samples which is at most $n_\\text{pub} = \\tilde{O}(n_{\\text{priv}}\\epsilon)$. We will clarify the phrasing of these theorems to make this more clear. \n\n* *The significance of Theorem 3 is unclear. Similar algorithms and similar improvements of dimension dependence were obtained in other works. The authors mention line 245 that their result avoids \"many of the strong assumptions seen in previous work\" without giving any details. What are these assumptions and how does Theorem 3 compare to existing results?*\n\nWith regards to the [[PHYS24]](https://arxiv.org/pdf/2306.03962) paper we cite, in addition to the assumptions we make, [PHYS24] additionally requires that the underlying distribution satisfies both a large margin condition and a low rank assumption (see Definition 3 and Theorem 1 of their paper). Further, they also only provide a statement for the privacy regime $\\epsilon = o(1)$. We will add these details to the revision.\n\n* *Corollaries 2 and 3 are frankly hard to interpret, and their significance is unclear to me. Maybe more effort is needed in this section.*\n\nCorollary 2 shows that with enough public data, it is possible to privately learn feed-forward neural networks without paying any explicit penalty for the network width (the rate only scales with the norm of the weights).\nCorollary 3 shows that (with access to public data) it is possible to obtain dimension-independent rates for constrained non-Euclidean GLMs. In both cases, such a width/dimension independence was previously unknown. We will add such comments to the revision.\n\n* *The general message of the paper, that \"more sophisticated attempts at leveraging public data will yield no benefit\" (in the labeled case), should be toned down a bit. While the new bounds indeed show some fundamental limits, these come under assumptions, and improvements were in fact shown for certain classes of problems like linear regression, as in some of the papers that were cited lines 28-29, (most of these were cited without discussion unfortunately).*\n\nAs with all theoretical works, our results come with certain assumptions, and our statements are made with respect to those assumptions. The class of problems we study for our lower bounds, Lipschitz losses over compact parameter space, are one of the most commonly studied classes in the DP optimization literature. Further, we do not believe the overall tone of our paper suggests that more sophisticated algorithms are useless in other settings. To the contrary, half our paper is devoted towards showing that in a slightly different setting (unlabeled public data) more sophisticated algorithms *are* useful.\n\n* *What do the authors mean by \"the non trivial regime  $n_{\\text{priv}} = \\Theta(n)$ and $n_{\\text{pub}} = o(n)$\"? Do you mean either of these is true? (if so, it would be clearer to use or, not and).* \n\nWe mean \"and\" for this statement. The regime $n_{\\text{priv}} = \\Theta(n)$ and $n_{\\text{pub}} = o(n)$ is the only non-trivial regime, at least if one is interested in asymptotics. This is because if either condition is not true, one can discard the private dataset and still have a dataset of size $\\Theta(n)$; i.e., one does not have to worry about privacy. This is obvious if $n_{\\text{pub}}=o(n)$ is not true. If $n_{\\text{priv}}=\\Theta(n)$ is not true, then it must also be the case that $n_{\\text{pub}} = \\Theta(n)$ since by definition $n = n_{\\text{pub}} + n_{\\text{priv}}$. We will elaborate in the revision.\n\n* *In the discussion following Cor.3, how do the $\\log(d)$ terms appear?* \n\n The $\\log{d}$ term appears from the choice of the function $\\Delta(w) = \\frac{\\log{d}}{2}\\Vert w \\Vert_{1+1/\\log{d}}$ -- see discussion in line 366 in the paper. This choice is standard in the $(\\ell_1,\\ell_\\infty)$-case -- see referenced work [FGV17]. We will revise the Corollary and discussion following it to make it clear.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
See the attached pdf for the lower bound table that will be added the revision.

Meta-review: The paper considers the problem of differentially private stochastic convex optimization when there is access to public data for which privacy needn't be ensured. The paper provides improved and nearly optimal lower bounds in various useful settings. In the case of unlabelled public data the paper also shows a dimension improvement. 

Overall the results of the paper were appreciated by the reviewers with only one major point of contention which is the writing. Many points have been raised by the reviewers including better presentation of the results comparison (which the authors have proposed to add) and better presentation of the required conditions on n_pub, i.e. using an O() notation or explicitly stating npub > c.n for some c. My personal recommendation is to use the latter as I agree with the reviewer that the former can lead to a different conclusion to a less careful reader. There are also other discussions and clarifications reviewers have suggested to add. 

Since fixable presentation issues are the only main issue with the paper, I recommend marginal acceptance under the hope that the authors address these before the final version.
Decision: Accept (poster)