Public-data Assisted Private Stochastic Optimization: Power and Limitations

Authors: enayat  ullah
michael  menart
raef  bassily
cristóbal  guzmán
raman  arora
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-09 21:49:55

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.

Main paper: 
 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]. However, it is often the case that, in addition to a collection of privacy-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, ABM19, BCM + 20, ZWB21, BKS22, AGM + 22, NMT + 23]. 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 + 22a, BWZK22], and prior work has even identified a specific problem instance where public and private data used in tandem leads to better rates than is possible using only the public or private datasets in isolation [GHN + 23]. Despite this surge of work, theory has struggled to 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, a small amount of public data, n pub ≤ n /d, leads to no rate improvement, where n = n pub + n priv and n priv 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 [LW19, SCZ + 20, PAE + 17]. 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 n pub = Ω(n priv ) 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 [CH11, BNS13] .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 ( , δ)-PA-DP 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.We outline our primary contributions in the following.Optimization with Public Data. First, we show a tight lower bound for the problem of differentially-private 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 Ω min1 √ npub , 1 √ n + √ d non the excess population risk for this problem. When d ≥ n and n pub ≤ n log(1/δ) , we further improve this lower bound to Ω min1 √ npub , 1 √ n + √ d log(1/δ) n. 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 a reduction of mean estimation to SCO. We note that previous work [LLHR23] , on this problem either focused on the pure PA-DP case when n pub ≤ n /d, or, in the approximate PA-DP case, did not obtain the dimension dependence. Our mean estimation lower bound uses a novel analysis of fingerprinting codes [BUV14] , and our SCO reduction further builds on ideas from [BST14, CWZ21] . We also show that, when d ≥ n , our lower bounds for approximate PA-DP SCO directly imply a tight lower bound for pure PA-DP.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 GLMs, they do not preclude settings where the public data is less informative. In particular, in the setting where the public data is unlabeled, it makes sense to even consider n pub ≥ n priv . In this setting, we provide the following results.• For (Euclidean) GLMs we develop an efficient algorithm which, given Õ(n priv ) unlabeled public data points, achieves the dimension independent rate Õ 1 √ npriv + 1 √ npriv . We obtain this result via 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 to identify a low dimensional subspace, which under the appropriate metric acts as a cover for the higher dimensional space. We elucidate 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 [SSTT21, 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.• By observing that the key requirement in our 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 a 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 [SST10] . However, it is known that they are not learnable privately in high dimensions d ≥ (n ) 2 [BST14] . In contrast, in the PA-DP setting, we show that it is possible to properly learn such classes with a rate of roughly O R npriv (H) + inf α>0 fatα(H) npriv + α , where R npriv (H) denotes the Rademacher complexity of H and fat α (H) denotes its fat-shattering dimension at scale α (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. In particular, for depth M feed-forward neural networks with weights bounded as W j F ≤ R j and 1-Lipschitz positive homogeneous activation, we achieve an excess risk bound of essen-tially Õ √ M M j=1 Rj √ npriv + M ( M j=1 Rj ) 2 npriv 1/3. For non-Euclidean GLMs, our guarantees are dimension-independent which is not known to be achievable, as of yet, even in the unconstrained setting with no public data (unlike Euclidean GLMs).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 of Ω min1 √ npub , 1 √ n + 1 nfor approximate PA-DP mean-estimation/SCO. We note that our results for approximate PA-DP crucially obtain a dependence on d that is the key "price" paid for privacy in this setting. [LLHR23] also show a lower bound of Ω min1 √ npub , 1 √ n + d non a pure PA-DP mean estimation/SCO, but this result only holds when d ≤ n npub . As such, their result is orthogonal to our result in the pure PA-DP setting, which operates in the regime d ≥ n . In both cases, our proof technique is fundamentally different than theirs. 3Tangentially, [BKS22] showed a small amount of public data is useful in pure-DP mean estimation when the range parameters on the data are unknown.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 [BNS13] . The works of [BNS13, BTGT18, ABM19] showed that given access to a small unlabelled public data, it is possible to go beyond this limitation and privately learn VC classes, essentially by reducing a hypothesis class with finite VC dimension to a finite hypothesis class A number of works have studied the impact of public data in applied settings as well. A common technique is to use public data to reduce the problem dimension in some way [ZWB21, YZCL21, PHYS24] . The work of [GHN + 23] 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 is 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. 
preliminaries: 
 Here, we describe the concepts and assumptions used in the rest of this paper. In this work, • always denotes the 2 norm unless stated otherwise.Public-Data Assisted Differential Privacy. We first present the traditional notion of differential privacy (DP). Let n, d ∈ N and X be some data domain. When no public data is present, we say that an algorithm A satisfies ( , δ)-differential privacy (DP) if for all datasets S and S differing in one data point and all events E in the range of A,P [A(S) ∈ E] ≤ e P [A(S ) ∈ E] + δ [DMNS06].In our work, we denote the number of public samples in the dataset, S = (S pub , S priv ) ∈ X n , as n pub and the number of private samples as n priv , such that n = n pub + n priv . In keeping with previous work [BNS13, BCM + 20], we define public data assisted differentially private algorithms in the following way 4 .Definition 1 (PA-DP). An algorithm A is ( , δ) public-data assisted differentially private (PA-DP) algorithm with public sample size n pub and private sample size n priv if for any public dataset S pub ∈ X npub , and any pair of private datasets S priv , S priv ∈ X npriv differing in at most one entry, it holds for any event E that P [A(S pub , S priv ) ∈ E] ≤ e P[A(S pub , S priv ) ∈ E] + δ. When δ = 0, we refer to this notion as pure PA-DP, denoted as -PA-DP. ∼ D. For a datset S we also define the empirical loss L(w; S) = 1 |S| x∈S (w; x). 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 × Y and D X and D Y denote the respective marginal distributions. Let H ⊆ R X be a hypothesis class of real-valued predictors, and let fat α (H) denote its fat shattering dimension at scale α. Consider the loss function : H × X × Y → R, such that (h; x, y) = φ y (h(x)) for some function φ y . We assume that the map φ y : R → R is G-Lipschitz for all y ∈ Y and is B-bounded. Further, we assume that sup x∈X |h(x)| ≤ R and define sup x∈X x = X . GLMs are a special case of supervised learning setting where the hypothesis class is that of linear predictors, H = W ⊆ R d , over X ⊆ R d , and h(x) = w x. We refer to the public dataset of unlabeled feature vectors as X pub .Covering numbers, fat-shattering and Rademacher Complexity Given X = (x 1 , x 2 , • • • , x m ) the p distance between two hypothesis h 1 , h 2 ∈ H with respect to the empirical measure over X, isdefined as, h 1 -h 2 p,X = 1 m x∈X |h 1 (x) -h 2 (x)| p 1/p .Similarly, the distance with respect to the population, is given by h1 -h 2 p,D X = (E x∼D X |h 1 (x) -h 2 (x)| p ) 1/p . The coveringnumber of H at scale α > 0 and given dataset X, denoted as N p (H, α, X) is the size of the minimal set of hypothesis, H, such that for any h ∈ H there exists h with h -h p,X ≤ α. We define N p (H, α, m) = sup X:|X|=m N p (H, α, X), the covering number with respect to all datasets of size m. We define fat-shattering dimension below.Definition 2. [BLW94] Let H ⊆ R X and α > 0. We say that H α-shatters X = {x 1 , x 2 , . . . , x m } if sup r∈R m min y∈{-1,1} m sup h∈H min i∈[m] y i (h(x i ) -r i ) ≥ α.The fat-shattering dimension, fat α (H), is the size of the largest α-shattered set.We define R m (H), the worst-case Rademacher complexity of H with respect to m data points, asR m (H) = sup X:|X|=m E σi sup h∈H 1 m m i=1 σ i h(x i ). An important example is that of norm- bounded linear predictors H = {w : x → w, x : w ≤ D} over X = {x : x ≤ X }. Herein, fat α (H) = Θ D 2 X 2 α 2 and R m (H) = Θ D X √ m [KST08, SST10]. 
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, n pub = Θ(n) and n pub = o(n), although our results hold regardless. Further, recall that an upper bound for this problem of O R min1 √ npub , 1 √ n + √ d log(1/δ) ncan 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 as private [BFTGT19] . As we will see, this strategy is essentially optimal.We start by stating our lower bound for public-data assisted differentially private SCO. Theorem 1. Let δ ≤ 1 16nd , ≤ 1, and d be larger than some universal constant. For any ( , δ)-PA-DP algorithm, there exists a distribution D, and a G-Lipschitz loss such that E L(A(S pub , S priv ); D) -min w: w ≤D {L(w; D)} = Ω (GD • Ψ(n pub , n, d, , δ)), where for some universal constant c,Ψ(n pub , n, d, , δ) =      min 1 √ npub , 1 √ n + √ d log(1/δ) n , d ≥ cn , n pub ≤ n c log(1/[ √ ndδ]) min 1 √ npub , 1 √ n + √ d n , elseThe function Ψ is defined to avoid repetitive notation in the rest of this section. Barring the mild restriction on n pub , even though the log (1/δ) term is only obtained when d ≥ n , the "aggregate" lower bound is tight for all d / ∈ [ n 2 log(1/δ) , n ] since when d ≤ n 2 log(1/δ) the non-private 1 √ n lower bound dominates. It is also pertinent to our results in Section 4 that the problem construction used to achieve this lower bound is 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 δ ≤ 1 16nd , ≤ 1. For any ( , δ)-PA-DP algorithm there exists a distribution D, λ-strongly convex and G-Lipschitz loss such that E L(A(S pub , S priv ); D) -minw: w ≤D {L(w; D)} = Ω G 2 λ Ψ 2 (n pub , n, , δ) .The crux of the proofs for both the above results lies in establishing new mean estimation lower bounds for PA-DP mean estimation, which we give in Appendix B.1. These mean estimation lower bound use a novel application of a construction known as fingerprinting codes. In particular, the introduction of public data introduces significant challenges in the traditional analysis of fingerprinting codes. As these challenges are more technical in nature, we defer their discussion to Appendix B.2.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 to 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 B.3.Lower Bound for Pure DP Case. While not the primary focus of this work, the previous lower bound directly leads to a lower bound for pure PA-DP SCO. Since any -DP algorithm is ( , δ)-DP for any δ > 0, we can use the above theorem to obtain a non-trivial lower bound for the pure DP case by setting δ small. Specifically, by setting δ such that log (1/δ) = n 120 2 npub , one immediately obtains a lower bound of Ω min{  
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 in the prior section.We start with learning linear predictors with convex loses a.k.a. convex generalized learning models. We propose Algorithm 1, 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 of a set of vectors and dim to denote the dimension of a subspace. The dataset of public unlabeled feature vectors is denote as X pub . Our algorithm projects the private feature vectors onto the subspace spanning W ∩ span(X pub ) to get dim(span(X pub ) ∩W)-dimensional representation of the private feature vectors. It then reparametrizes the loss function so that its domain is dim(span(S pub ) ∩W)dimensional and applies a private subroutine in the lower dimensional space. The output of the subroutine is then embedded back in R d . Algorithms similar to Algorithm 1 have appeared in the literature (e.g. [PHYS24] ). We emphasize that our 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.Algorithm 1 Efficient PA-DP learning of GLMs with unlabeled public data Input: Private labeled dataset S priv , public unlabeled dataset X pub , privacy parameters , δ > 0.1: Let U ∈ R d×dim(W∩span(Xpub)) denote the orthogonal projection onto span(X pub ) ∩ W.2: Define Spriv = (U x i , y i ) npriv i=1 and let W = U w : w ∈ W . 3: Apply ( , δ)-DP subroutine, Ã, on loss function w → φ y ( w, x ) with dataset Spriv over the constraint set W, to get w ∈ R dim(W∩span(Spub)) . Output: w = U w.Our main result for convex Lipschitz losses is the following. Theorem 3. Let > 0, δ > 0 and ≤ log (1/δ). For a G-Lipschitz, B-bounded convex loss function, Algorithm 1 satisfies ( , δ)-PA-DP. If the private subroutine Ã guarantees the following, with probability at least 1 -β, L( Ã( Spriv ); Spriv ) -minw∈ W L(w; Spriv ) = O GD X n pub log (1/δ) + log (1/β) n priv (1)then with n pub = Õ npriv (log(2/β)+log(1/δ)) 1/2 , with probability at least 1 -β, L( w; D) -L(w * ; D) is O GD X log (4/β) √ n priv + (log (2/β) + log (1/δ)) 1/4 √ n priv + B log (4/β) √ n priv .We note that DP algorithms such as projected noisy SGD [BST14] and the regularized exponential mechanism [GLL22] , both of which can be implemented efficiently, are can be used to achieve (1), since the projected problem is at most n pub dimensional.The above result shows that in the usual regime of = Θ(1), there is no price of privacy, thereby obtaining the non-private rate of O 1 √ npriv . We contrast this with the rate ofO 1 √ npriv + √ d npriv, achievable without public data. Our result is better when d ≥ n priv , which is the interesting regime since herein the private error dominates the non-private error. Further, our lower bound (Theorem 4 below) shows that this is the non-trivial regime (for any = O(1)), 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 w can have very large norm and so may lie outside W[ABG + 22].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 to linear predictors in Section 4.2 after Theorem 7. The full proof of this result is 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 a 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, δ ≤ and A be an ( , δ)-DP algorithm. There exists a G-Lipschitz convex GLM loss function, and joint distribution D such that given a dataset S comprising n i.i.d. samples from D and full knowledge of the marginal distribution D X , we have the following:E A,S L(A(S); D) -min w: w ≤D L(w; D) = Ω GD X 1 √ n + min 1 √ n , √ d n .We note that the bound with √ d npriv can be achieved without using any public data via standard results [BFTGT19, ABG + 22]. This result is largely a corollary of [ABG + 22, Theorem 6]. We provide full details in Appendix C.3.1.To establish optimality of public sample complexity, we give the following lower bound which shows that Ω(n priv ) samples are necessary to achieve the above rate. See Appendix C.3.2 for proof. Theorem 5. Let n priv , n pub , d ∈ N, ≤ 1, δ < 1 16dn and d = ω(n priv ). If there exists an ( , δ)-PA-DP algorithm A, which, for any G-Lispschitz convex GLM, achieves excess riskE L(A(X pub , S priv ); D) -min w: w ≤D L(w; D) = O GD X 1 √ npriv + √ log(1/δ) √ npriv, forS priv ∼ D npriv and X pub ∼ D npub X , then n pub = Ω( npriv log(1/δ) ).Optimistic rates. We now consider additional assumptions that the loss function is non-negative and H-smooth, such as in the case of linear regression where φ y (a) = (a -y) 2 . This is a well-studied setting [SST10] 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.Theorem 6. Let > 0, δ > 0 and ≤ log (1/δ). For a G-Lipschitz, B-bounded non-negative Hsmooth loss function, Algorithm 1 satisfies ( , δ)-PA-DP. If the private subroutine Ã guarantees Equation (1) with probability at least 1-β, then with npub = Õ (HD X ) 2/3 (n priv ) 2/3G 2/3 (log(1/δ)) 1/3 + √ Hn priv √ L( w * ;S priv ) G √ log(1/δ)), with probability at least 1 -β,L( w; D) -L( w * ; Spriv) = Õ √ HD X √ npriv + B npriv L( w * ; Spriv) + H 1/4 D X √ G L( w * ; Spriv) 1/4 √ npriv + Õ GD X npriv + √ HD 2 X 2 G npriv 2/3 + H X 2 D 2 npriv + B nprivwhere w * is the minimizer of L w.r.t S priv and Õ hides poly(log (1/δ) , log (1/β)) terms.A similar result as above can be obtained with L( w * ; S priv ) replaced by L(w * ; D) above -see Theorem 14 for the full theorem statement. This rate, in the worst-case, is essentially the same as that of Theorem 3, which is Õ1 √ npriv + 1 √ npriv. However, optimistically, when L(w * ; D) or L( w * ; S priv ) is small, we get a faster rate of Õ 1 npriv + 1 (npriv ) 2/3 . We note that this is seemingly weaker than what is known in the unconstrained setting, where [ABG + 22] obtained a worst-case rate of Õ 1 √ npriv + 1 (npriv ) 2/3 . We show that we can recover this faster rate under an extra assumption that the global minimizer of the risk, lies in 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 Ã that realize the above theorem statements.In this section, we consider a general supervised learning setting with fat-shattering hypothesis classes and potentially non-convex losses, with unlabeled public data. Our proposed algorithm is similar to that of [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 the 2 distance of predictions on the public data points. We then use the exponential mechanism to privately select a hypothesis using the empirical loss on 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 X pub and S priv , privacy parameter > 0, scale of cover α > 0, γ > 0.1: Construct H, a minimal α-cover of H, with respect to the following metrich 1 -h 2 2,Xpub = 1 n pub x∈Xpub (h 1 (x) -h 2 (x)) 2 2: Return h sampled with probability p(h) ∝ exp -γ L(h; S priv ) over h ∈ HOur main result for the Lispchitz setting is the following.Theorem 7. Algorithm 2 with γ = 2 min(B,GR) npriv satisfies -PA-DP. For any α > 0 andn pub = O max R 2 log(2/β) α 2 , min m : log 3 (m)R 2 m (H) ≤ α 2 < ∞, with probability at least 1 -β, we have L( h; D) -min h∈H L(h; D) is at most 2GR npriv (H) + O B log (4/β) √ n priv + Õ min (B, GR)(fat cα (H) + log (4/β)) n priv + 2Gα,where c is an absolute constant.Our result shows that the model of PA-DP with unlabeled public data allows for obtaining nontrivial rates for supervised learning with any fat-shattering class, as is the case in the non-private setting. Further, in many standard settings, such as that of (Euclidean) GLMs, the Rademachercomplexity is R m (H) = O 1 √ m which implies that fat α (H) = O 1 α 2 (see Theorem 9). In those cases, our guarantee simplifies to essentially yield a rate of O R npriv (H) + 1 (npriv ) 1/3 + 1 √ npriv -see Corollary 4 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 is a cover of H with respect to the empirical distance on public feature vectors, • 2,Xpub , then with enough public feature vectors, it is also a cover with respect to the population distance • 2,D X . This is captured in the following result.Lemma 1. Let H be a τ -cover of H with respect to • 2,Xpub .Forn pub = O max R 2 log(1/β) α 2 , min m : log 3 (m)R 2 m (H) ≤ α 2 < ∞, for every h ∈ H, with probability at least 1 -β, there exists h ∈ H such that h -h 2,D X ≤ α + τ .This result allows us to appropriately approximate a 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 H of size | H| = Õ(fat τ (H)).For linear predictors with convex losses, as in Theorem 3, we show that the span(X pub ) ∩ W is a valid 0-cover w.r.t. • 2,Xpub . 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.In this section, we instantiate our general result to give a guarantee for learning feed-forward neural networks in the PA-DP setting. We use the result of [GRS18] but note that other results which give bounds on the Rademacher complexity of neural networks, such as [BFT17, Sel23] can also be used.We consider a depth M feed-forward neural network which implements the function x → W M (σ(W M -1 . . . σ(W 1 x)) . . .). Here, W 1 , W 2 , . . . , W M are the weight matrices and σ is a (nonlinear) activation function. We consider 1-Lipschtiz positive-homogeneous activation such as the ReLU function, σ(z) = max(0, z), applied coordinate-wise. Our main result is the following.Corollary 2. Let (R j ) M j=1 be a sequence of scalars and M ∈ N. In the setting of Theorem 7 withX = x ∈ R d : x ≤ Xand H being the class of depth M feed-forward neural networks, with 1-Lipschitz positive-homogenous activation, and weight matrices, bounded asW j F ≤ R j , with n pub = Õ ( X ( M j=1 R j )) 2/3 (n priv ) 2/3 M 1/3 log (2/β) , with probability at least 1 -β, L( h; D) -min h∈H L(h; D) is at most O G X √ M M j=1 Rj √ npriv + B log (4/β) √ npriv + B log (4/β) npriv + Õ   BG 2 M X 2 ( M j=1 Rj) 2 npriv 1/3   .We note that the above result has a polynomial dependence on the depth M , which is a consequence of the (non-private) Rademacher complexity of [GRS18] . It 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 [Sel23] . Further, a similar result follows for non-negative smooth losses from [SST10] , but we omit this extension for brevity.In the non-Euclidean GLM setting, we consider (X, • ) as a d dimensional (where d ∈ N ∪ {∞}) Banach space, and (W, • * ) is its dual space. The feature vectors x are bounded as X = {x ∈ X : x ≤ X } and W ⊆ {w ∈ W : ∆(w) ≤ D r } where ∆ is a r-uniformly convex function6 with respect to • * . A canonical example is the ( p , q )-setup [KST08, FGV17], wherein the functions ∆(w) = log(d) The GLM loss function (w; x, y) = φ y ( w, x ) where •, • : X × W → R is a duality pairing. In this case, the Rademacher complexity of linear functions, is bounded as O D X m 1/r , where s is the conjugate of r i.e. 1 r + 1 s = 1 (see, e.g. [FGV17] ). We obtain the following result by instantiating Theorem 7 with the Rademacher complexity and fat-shattering dimension of non-Euclidean GLMs. Corollary 3. In the setting of Theorem 7, together withX = x ∈ R d : x ≤ X and H = {x → w, x , x ∈ X , ∆(w) ≤ D r } . Given n pub = Õ (n priv ) r/(r+1) log (2/β) , with probability at least 1 -β, L( w; D) -min w∈W L(w; D) is at most Õ GD X 1 n priv 1/r + log (4/β) √ n priv + log (2/β) (n priv ) 1 r+1 + log (4/β) n priv + B log (4/β) √ n priv .The above yields guarantees for the special case of ( p , q )-setup with r = max {2, p}. We remind that in the (constrained) convex Euclidean GLM setting, our dimension-independent rate in Theorem 3, 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 polyhedralsetting with w 1 ≤ D constraint, resulting in a O log(d) npriv + log(d) npriv 1/3 rate. We note that [BGM21] showed a rate of Õ log(d) n + √ log(d) √ nfor this setting, with convex losses without public data. Importantly, for the other cases, i.e. p > 1, p = 2, there are no such (nearly) dimensionindependent analogs of our result without public data, as of yet.Theorem 8. [RS12, Theorem 12.7] For H ⊆ [-R, R] X , m ∈ N, p ≥ 1, 0 < α ≤ R, we have that N 2 (H, α, m) ≤ 2R α Cfat cα (H).Further, for any τ ∈ (0, 1), log (N ∞ (H, α, m)) ≤ C fat(H, c τ α) log Rm fat(H, c τ α)α log τ m fat(H, c τ α) ,W j F ≤ R j is bounded as, R m (H) ≤ X ( 2 log (2) M + 1) M j=1 R j √ m .Here • F denotes the Frobenius norm. Lemma 2. [DSS + 15, Implied by Lemmas 5 and 14] Let f :{±1} n → R and define g : [-1, 1] → R as g(p) = E S∼D n p [f (S)], where D p is as defined in Appendix B. Then for a, b ∈ R, b > a, and µ ∼ Unif([a, b]), E µ,S f (S) • x∈S (x -µ)] = E µ g (µ)(1 -µ 2 ) = 1 -E µ µ 2 + (g(b) -b)(1 -b 2 ) 1 |b -a| -(g(a) -a)(1 -a 2 ) 1 |b -a| + 2E µ [(g(µ) -µ)µ] . Lemma 3. [FS17, Lemma A.1] Fix µ, , δ, ∆ ∈ R. Let X and Y be random variables supported on [µ -∆, µ + ∆]. Suppose that X and Y are ( , δ)-indistinguishable, that is for any E ⊆ R, e -(P [X ∈ E] -δ) ≤ P [Y ∈ E] ≤ e P [X ∈ E] + δ. Then |E [X] -E [Y ] | ≤ (e -1)E [|X -µ|] + 2δ∆.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 2 ball of radius R > 0. We define the mean of D as µ(D). Our lower bound for PA-DP mean estimation follows much the same form as our SCO bound. Theorem 11. Let δ ≤ 1 16nd , ≤ 1. For any ( , δ)-PA-DP algorithm, there exists a distributionD such that E [ A(S pub , S priv ) -µ(D) ] = Ω (R • Ψ(n pub , n, , δ)).We 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 used to recover the optimal non-private lower bound for mean estimation. This allows us to create a 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 a given datapoint is considered public or private. Combining these upper and lower bounds on correlation yields the claimed result.To obtain the log (1/δ) 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, DSS + 15]. Towards this end, for any vector µ ∈ [-1, 1] d we define D µ as the product distribution where, for any j ∈ [d], a sample has its j'th coordinate as 1 with probability (1 + µ j )/2 and as -1 with probability (1 -µ j )/2. As shorthand, we denote R √ d D µ as the distribution which samples a vector from D µ and then scales it by R √ d . For notational convenience, for a set E, we will also use Unif(E) to denote the uniform 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 √ n statistical lower bound that holds even non-privately. The first theorem we present holds for a larger range of parameters but does not achieve the dependence on log (1/δ). Theorem 12. Let > 0, δ ≤ 1 16n and A be an ( , δ)-PA-DP algorithm. For any setting of min√ d npriv , 1 √ npub ≤ M ≤ 1, if µ ∼ Unif([-M, M ] d ) and (S pub , S priv ) ∼ R √ d D n µ it holds that E A,S,µ [ A(S pub , S priv ) -µ(D) ] = Ω R min 1 √ n pub , √ d n(e -1).In application to Theorem 11, we use (e -1) ≤ 2 whenever ≤ 1. The second theorem requires d ≥ n but has the benefit of scaling with log (1/δ). Theorem 13. Let δ ≤ 1 3dn , ≤ 1, d ≥ 120 2 n , andn pub ≤ n 120 2 log(1/[ √ ndδ]) , and A an ( , δ)-PA-DP algorithm. Then there existsM > 0 such for µ ∼ Unif([-M, M ] d ) and (S priv , S pub ) ∼ R √ d D n µ it holds that E A,S,µ [ A(S pub , S priv ) -µ(D) ] = Ω R min 1 √ n pub , d log (1/δ) n .A crucial part of the analysis is leveraging the so called fingerprinting lemma, which roughly states that any accurate algorithm given a dataset sampled from D µ 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 µ be sampled uniformly from[-M, M ] d . Let A satisfy E S∼D n µ [ A(S) -µ ] ≤ α (for any µ ∈ [-1, 1] d ). Then one has E A,S,µ n i=1 A(S), x i -µ ≥ 2d 3 - α √ d M -2M √ dα.Proof. In the following we treat A as a deterministic function and bound E S,µ [ n i=1 A(S), x i -µ ]. This is sufficient to bound E A,S,µ(x i -µ) (i) = E µ g (µ)(1 -µ 2 ) (ii) ≥ 1 -E µ 2 + 2E µ [(g(µ) -µ)µ] - |g(-M ) + M | + |g(M ) -M | 2M ≥ 2/3 + 2E µ [(g(µ) -µ)µ] - |g(-M ) + M | + |g(M ) -M | 2M .Above, (i) comes from [DSS + 15, Lemma 5] and (ii) comes from [DSS + 15, Lemma 14], which we have collectively restated in Lemma 2. We now haveE S,µ A(S) n i=1 (x i -µ) ≥ 2/3 + |g(-M ) + M | + |g(M ) -M | 2M + 2E µ [(g(µ) -µ)µ] ≥ 2/3 + |g(-M ) -M | + |g(M ) -M | 2M -2E µ [|g(µ) -µ| • |µ|] ≥ 2/3 - |E S∼D -M [A(S)] + M | + |E S∼D M [A(S)] -M | 2M -2M E µ E S∼Dµ [A(S)] -µ .Above we use the fact that |µ| ≤ M and the definition of g.We can now extend the above analysis to higher dimensions. For µ ∈ R d , the above holds for eachµ j , j ∈ [d]. For convenience define M = (M, . . . , M ) ∈ R d . Summing over d dimensions we have E S,µ A(S), n i=1 (x i -µ) ≥ 2d 3 - 1 2M E S∼D -M [A(S)] + M 1 - 1 2M E S∼D M [A(S)] -M 1 -2M E µ E S∼Dµ [A(S)] -µ 1 ≥ 2d 3 - 1 2M E S∼D -M A(S) + M 1 - 1 2M E S∼D M A(S) -M 1 -2M E S,µ [ A(S) -µ 1 ] ≥ 2d 3 - √ d 2M E S∼D -M A(S) + M 2 - √ d 2M E S∼D M A(S) -M 2 -2 √ dM E S,µ [ A(S) -µ 2 ] ≥ 2d 3 - α √ d M -2M √ dα.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} d , and as such the 2 bound on the data is √ d. The final result will follow from rescaling by R √ d . Let S = {x 1 , x 2 , . . . x n } = (S pub , S priv ) ∼ D n µ be the concatenation of the public and private datasets. We also define α = E [ A(S pub , S priv ) -µ ] for notational convenience.Define the following statistics,Z i = A(S pub , S priv ) -µ, x i -µ Z i = A(S pub , S ∼i ) -µ, x i -µ .where S ∼i is the dataset formed by replacing i-th data point of S priv with x i ∼ D µ . We have,E A,S,µ n i=1 Z i = E npub i=1 Z i + E n i=npub+1 Z i .(2)The lower bound proceeds by providing upper and lower bounds on the above sum. We first haveE A(S pub , S priv ) -µ, npub i=1 (x i -µ) ≤ E[ A(S pub , S priv ) -µ 2 ]E npub i=1 (x i -µ) 2 ≤ α √ dn.where the first inequality used Cauchy-Schwartz.For the second term in Equation (2), we utilize differential privacy. Specifically, [FS17, Lemma A.1], restated in Lemma 3, gives thatE n i=npub+1 Z i ≤ n i=npub+1 E[Z i ] + 2(e -1) Var(Z i ) + 8δd≤ 4n priv (e -1)α + 8n priv δd.Above we use that Var(Z i ) ≤ 4α 2 since x i -µ ∞ ≤ 4. Plugging the above two in Equation (2) yields,E n i=1Z i ≤ (4n priv (e -1)α + 8n priv δd) + α dn pub .We now use the fingerprinting lemma, Lemma 4, to lower bound the correlation. In this regard, noteE S,µ [ µ, n i=1 (x i -µ) ] = 0. Thus E n i=1 Z i = E A(S pub , S priv ), n i=1 x i -µ ≥ 2d 3 - α √ d 2M -2M √ dα.Plugging the obtained upper bound on the left hand side gives us,4n priv (e -1)α + 8n priv δd + α dn pub ≥ 2d 3 - α √ d M -2M √ dα =⇒ 4n priv (e -1)α + α dn pub ≥ d 6 - α √ d M -2M √ dα =⇒ α 4n priv (e -1) + dn pub + √ d M + 2M √ d ≥ d 6 =⇒ α ≥ 1 24 min d n priv (e -1) , √ d √ n pub , M √ d, √ d M =⇒ α ≥ 1 24 min d n priv (e -1) , √ d √ n pub , M √ d .Above the first implication uses the assumption that δ ≤ 1 16npriv . The last implication uses the fact that M√ d ≤ √ d M since M ≤ 1. Rescaling by a R √ d factor yields the bound E A,S,µ [ A(S pub , S priv ) -µ ] ≥ R 24 min √ d n priv (e -1) , 1 √ n pub , M .Observe that any setting of M ≥ min√ d npriv , 1 √ npubrealizes the bound claimed in the theorem statement.We now turn towards achieving a dependence on δ to prove Theorem 13. To do this, we leverage the the idea of filling a dataset with copies of each fingerprinting code seen in previous work [SU15, CWZ21] . 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. . Let k = 1 3 log 1/[ √ dnδ] . Let m = n k . We set M = 4 √ d (α * + d m ). Let µ ∼ Unif([-M, M ] d ), S z = {z 1 , ..., z m } ∼ D µ .Sample S priv , S pub ∼ Unif ({z 1 , ..., z m }) and denote the combined dataset as S = {x 1 , . . . , x n } = (S pub , S priv ). Note that as in the proof of Theorem 12, we are starting by showing a lower bound for the case where the data is drawn from D µ instead of R √ d D µ , 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 S z . We will also introduce a clipping procedure which helps better control the upper bound on correlation. In this regard, for each j ∈ [m] define Z j = A(S pub , S priv ) M , z j -µ , where v M denotes the operation of clipping every element of v to [-M, M ]. In the following, we will provide upper and lower bounds on E m j=1 Z i and use this to show that α ≤ α * implies a contradiction.We now want to lower bound E m j=1 Z j . Towards this end, we can apply fingerprinting lemma, Lemma 4, to the algorithm which outputs the clipping. For α > 0, ifE A,S [ A(S pub , S priv ) M -µ ] ≤ α, then this yields, E A,S,µ   m j=1 Z i   ≥ 2d 3 - α √ d M -2M √ d α.E [ A(S pub , S priv ) M -µ ] ≤ E [ A(S pub , S priv ) -µ ] ≤ E A(S pub , S priv ) - 1 m z∈Sz z + E 1 m z∈Sz z -µ ≤ α * + d mIn the last step we use the assumed contradiction that α ≤ α EQUATION)Bounding the Number of Copies in the Dataset We now turn towards the more involved process of upper bounding E S,µ[ n i=1 Z i ].To do this however, it will be first helpful to show that no datapoint in S z is copied into S too many times. The first step is showing that no point is copied too many times into S.For j ∈ [m], let Z j = {i ∈ [n] : x i = z j }. Observe P [∃j ∈ [m] : |Z j | ≥ (τ + 1)k] ≤ m j=1 P [|Z j | ≥ (τ + 1)k] ≤ m exp - 3τ 2 n 4m(1 -1/n) ≤ m exp - 3τ 2 log (1/δ) 8 .The second inequality follows from Bernstein's inequality for the sum of n Bernoulli random variables with mean 1/m and the fact thatE [|Z j |] = n m = k. Set τ = 8 log(dm)3 log(1/δ) and note since ≤ 1 and log (dm) ≤ log (dn) ≤ log (1/δ) (since δ ≤ 1 dn ), we have that τ ≤ 2. Thus, denoting E as the event where no point in S z is copied into S more than 3k times, we establishEQUATIONUpper Bound on Correlation Under our model, we assume that A must treat all data in S priv as private. We will in fact only need to use the privacy property for a subset of samples in S priv to prove the correlation upper bound. Let I priv ⊆ [m] denote the set of indices s.t. j ∈ I priv if every copy of z j sampled into the overall dataset is in the private dataset S priv ; that isI priv = {j : (∀x ∈ S pub ) x = z j }. Let I pub = [m] \ I priv .Observe that I priv may contain indices for points in S z which are never sampled into S. We will see this does not affect our analysis.We haveE   m j=1 Z i   = E   j∈Ipriv A(S pub , S priv ) M , z j -µ + j∈Ipub A(S pub , S priv ) M , z j -µ   .The first term on the RHS can be bounded using the privacy property of A. For any fixed j ∈ I priv , let S priv denote the dataset which replaces every instance of z j in S priv with a copied fresh sample from D µ . By the above analysis, conditional on the event E, at most 3k such points need to be replaced conditional on the event E. Since A(S pub , S priv ) is independent of z j , by the Chernoff Hoeffding bound,P A(S pub , S priv ) M , z j -µ ≥ τ | E ≤ exp - τ 2 8dM 2 .(5)Since A satisfies k-group privacy with parameters ≤ 3k and δ = e 3k δ, we haveP [ A(S pub , S priv ) M , z j -µ ≥ τ | E] ≤ exp - τ 2 2dM 2 + δ. Setting τ = M d log (1/δ), we obtain E [Z j | E] ≤ τ + 2dP [Z j ≥ τ | E] ≤ M d log (1/δ) + 2de δ + δ ≤ M d log (1/δ) + 3de 3k δ ≤ 4M d log (1/δ).The last inequality comes from the setting of k = 1 3 log 1 √ dnδ and the fact that M ≥ 1 √ n . Repeating this argument for each j ∈ I we getE j∈Ipriv Z j ≤ E j∈Ipriv Z j E P [E] + mM dP [E c ] ≤ 5mM d log (1/δ).The last inequality uses the bound established on each E [Z j | E], j ∈ I priv , above and the bound on P [E c ] from Eqn. (4). To bound the correlation over the remaining vectors, we haveE   j∈Ipub Z j   ≤ E[ A(S pub , S priv ) M 2 ]E j∈Ipub (z j -µ) 2 ≤ 2M d √ n pub .Above we have used the fact that |I pub | ≤ n pub because i ∈ I pub only if at least one copy of z i is sampled into S pub . Combining the above we haveE   m j=1 Z i   ≤ 5mM d log (1/δ) + 5M d √ n pub .Combining Bounds:The previously derived lower bound in Eqn.(3) establishes thatE j∈Ipriv Z j + j∈Ipub Z j ≥ d 3 .Using the above derived upper bounds we have the following manipulations,EQUATION⇐⇒ (α * + d/m) m log (1/δ) + dn pub ≥ d 60 ⇐⇒ mα log (1/δ) + α * dn pub ≥ d 60 -d log (1/δ) m -d n pub m .The second line above uses that M = 4 We here provide more details on why the particular lower bound techniques we present were chosen. Our aim for the following discussion is to elucidate 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.1 is ensuring that the correlation sum, traditionally defined as E x∈S A(S), x -µ , scales with the accuracy, α, of the algorithm. Previous work, such as [CWZ21] , achieves this by setting the underlying distribution, D, to be a mixture distribution which, for some p = o(1), samples a 0 vector with probability (1 -p) and samples from the non-trivial distribution, D µ , with probability p. However, now the variance satisfiesE x∼D x -E [x] 2 ≤ 2pR 2 meaning that when public data is present it holds that E 1 npub x∈Spub x -E x∼D [x] ≤ 2pR √ npub = o R√ npub , and one cannot hope to achieve the desired lower bound. Alternatively, by instead analyzing the sum E x∈S A(S) -µ, x -µ , as seen for example in [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 to still ensure µ(D) = 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 log (1/δ) improvement in Theorem 13, the property E [ A(S) -µ ] ≤ α does little to help establish the needed tail bound; see Eqn. + E [L(A(S); D) -L(w * ; D)|E ] P[E ] ≥ 1 2 E [L(A(S); D) -L(w * ; D)|E] .Thus it suffices to lower bound the conditional excess risk.The optimal solution under the aforementioned loss is w * = -µ µ , since the constraint set is a ball of radius 1. We can see thatEQUATION)We will now lower bound A(S) -w * by using the lower bound for mean estimation developed in Theorem 11. Let the mean estimate candidate is μ(S) = μ = -2 3 M A(S). Under the event E,EQUATION)The above follows from the definition of w * and since the algorithm's output is considered in a ball of radius 1, so A(S) ≤ 1.Combining the above inequalities ( 6) and ( 7) then taking expectation we have,EQUATION)To bound E μ -µ 2 |E , observeE[ μ -µ 2 ] = E[ μ -µ 2 |E]P[E] + E µ,S [ μ -µ 2 |E ]P[E ] ≤ E[ μ - 2 |E] + 4M 2 P[E ].Rearranging we haveEQUATION)We will finish the bound by applying either Theorem 12 or Theorem 13. √ d n priv , 1 √ n pub .Via Theorem 13: In Theorem 13, the setting of M used isM = 4 1 125 min d log (1/δ) n , 1 n pub + log 1/[ √ dnδ] n ≤ 1 30 min d log (1/δ) n , 1 n pub .The inequality holds under the conditions d ≥ 120 2 n and n pub ≤n 120 2 log(1/[ √ ndδ]) . Thus we have under this setting of M that E [ μ -µ ] ≥ M 8 . Applying Eqns. ( 9) and (8) as in the previous case we have (providing the above conditions on d and n pub hold)E [L(A(S); D) -L(w * ; D)] = Ω (M ) = Ω min d log (1/δ) n , 1 n pub . Lemma 5. For z ∼ Unif([-1, 1] d ), we have that z ∈ √ 2d √ 3 ± √ 3 ln (1/γ) 2, with probability at least 1 -γ.Proof. This follows from standard concentration of norm results. We have that,E z 2 = dEz 2 1 = 2d 3 .As in [Ver18, proof of Theorem 3.1.1], we use the simple fact that |x -1| > δ =⇒ x 2 -1 > max(δ, δ 2 ) for any x, δ ≥ 0, to get,P z - √ 2d √ 3 > √ 2dδ √ 3 = P √ 3 z √ 2d -1 > δ = P 3 z 2 2d -1 > max(δ, δ 2 ) = P 1 d d i=1 z 2 i - 2 3 > max (2/3)δ, ((2/3)δ) 2 .We substitute δ = 2δ 3 and apply Bernstein's inequality for i.i.d sub-exponential random variables z 2 i . Since, z i ∈ [-1, 1], the sub-exponential norm ≤ 1. Applying Corollary 2.8.3 from [Ver18], we get that,P 1 d d i=1 z 2 i - 2 3 > max δ, ( δ) 2 ≤ exp -2 δ2 d = exp -8δ 2 d/9 .This gives us thatP z - √ 2d √ 3 > √ 2dδ √ 3 ≤ exp -8δ 2 d/9 .Hence, with probability, at least 1 -γ, we have that z ∈√ 2d √ 3 ± √ 3 ln (1/γ) 2, which completes the proof.Proof of Theorem 2. We use the squared loss instance as in [BST14, Section 5.2];(w; z) = λ 2 w -z 2 , with z ≤ G 2λ .The loss is G-Lipschitz and λ strongly convex on the domain of unit ball at zero of radius G 2λ . Given a datasets S = {z 1 , z 2 , . . . , z n }, the population risk minimizer is simply the population mean µ(D). Further, it is straightforward to verify that the excess population risk a re-scaling of the mean estimation errorE[L(A(S)) -min w L(w)] = λ 2 E A(S) -µ(D) 2 .Substituting the mean estimation lower bounds, Theorem 11, completes the proof.Define the orthogonal projection matrix P Xpub = U U . Note that the feature vectors in Spriv = (U x i , y i ) npriv i=1 are bounded. In particular U x 2 = x (U U )x = x P Xpub x ≤ x 2 , since P Xpub is an orthogonal projection onto span(W ∩ S pub ). Further, since w ∈ W, we have that there exists ẘ ∈ W such that w = U ẘ. Finally, w = U w = U U ẘ = P Xpub ẘ ∈ W since the range of P Xpub ⊆ W.The privacy guarantee follows from the privacy guarantee of sub-routine Ã. For utility, we define w * ∈ arg min w∈W L(w; D) and w * ∈ arg min w∈ W L(w; U D), where U D denotes the distribution which first samples from D then project using U . Let ẘ * ∈ W such that ẘ * = U w * .Note that from the GLM structure, L( w * ; U D) = L( ẘ * ; D). We have,EQUATIONwith probability at least 1 -β/4. In the above, we control the generalization gap via uniform convergence and concentration for the fixed ẘ * with respect to S priv .The last term L( w; Spriv )-min w∈ W L(w; Spriv ) is bounded by the guarantee of the private sub-routine with probability at least 1 -β/4, L( Ã( Spriv ); Spriv ) -minw∈ W L( Ã( Spriv ); Spriv ) = Õ GD X n pub log (1/δ) + log (4/β) n priv .Finally, for any w * such that w * ∈ U W, with probability at least 1 -β/2, from G-Lipschitznes, we haveL(ẘ * ; D) -L(w * ; D) ≤ L( w * ; D) -L(w * ; D) ≤ G w * -w * 2,D X ≤ Gα,where the last inequality follows essentially from Lemma 6 and Lemma 1 forn pub = O max R 2 log(2/β) α 2 , min m : log 3 (n pub )R 2 npub (H) ≤ α 2 .To elaborate, the first step holds since ẘ * = U w * and w * is the the minimizer of risk over W. Now, Lemma 1 guarantees that for any w * ∈ W, there exists a w * in its α-cover with respect to • 2,Xpub , with w * -w * 2,D X ≤ α. To argue why span(X pub ) is an α-cover, from Lemma 6, we have that from any α-cover W, of W w.r.t.• 2,Xpub , we can remove elements which do not lie in span(S pub ) and still have an α-cover. Hence, the superset used in Algorithm 1, which essentially is, W = P Xpub W, is indeed an α-cover.The n pub we get is,n pub = O max R 2 log (1/β) α 2 , min m : log 3 (m)R 2 m (H) ≤ α 2 = Õ D 2 X 2 max log (2/β) α 2 , 1 α 2where in the above, we plug in the Rademacher complexity of bounded linear predictor, R m (H) = Θ D X m . Plugging the above in Equation (10),L( w; D) -L(w * ; D) = O GD X √ n priv + GD X log (4/β) √ n priv + B log (4/β) √ n priv + O GD X n pub log (1/δ) + log (4/β) n priv + Gα = O GD X log (4/β) √ n priv + GD 2 X 2 log (2/β) + log (1/δ) αn priv + B log (4/β) √ n priv + Gα = O GD X log (4/β) √ n priv + (log (2/β) + log (1/δ)) 1/4 √ n priv + B log (4/β) √ n privwhere the above follows by setting α = D X (log(1/δ)+log(2/β)) 1/4√ npriv. This yields the claimed rate. The resulting public sample complexity isn pub = Õ D 2 X 2 max log (2/β) α 2 , 1 α 2 = Õ n priv (log (2/β) + log (1/δ)) 1/2 .This completes the proof. Lemma 6. Let H be a α-cover of H with respect • 2,Xpub . Then, H = H ∩ span(X pub ) is also an α-cover.Proof. Given two h 1 , h 2 ∈ H, we have,h 1 -h 2 2,Xpub = 1 n pub npub i=1 (h 1 (x i ) -h 2 (x i )) 2 = 1 √ n pub (w 1 -w 2 ) X pub X pub (w 1 -w 2 )where w 1 and w 2 are the vectors corresponding to linear functions h 1 and h 2 and X pub denote the matrix of public feature vectors.Given any h ∈ H, let h denote the element closest to it in the cover H; we have, h -h 2,Xpub ≤ α.Consider the singular value decomposition, X pub = V ΣU , where U and V are orthogonal matrices and Σ is a diagonal matrix. Define h = P Xpub ( h) = U U h. Note that U is an orthogonal projection onto span(X pub ) and P Xpub is the corresponding projection matrix. We have,h -h 2 2,Xpub = 1 n pub (h -h) X pub X pub (h -h) = 1 n pub (h -P Xpub ( h)) U Σ 2 U (h -P Xpub ( h)) = 1 n pub (h -h) U (U U )Σ 2 (U U )U (h -h) = 1 n pub (h -h) U Σ 2 U (h -h) = 1 n pub (h -h) X pub X pub (h -h) ≤ α 2Since by construction h also lies in span(X pub ), this proves the claim.We state the complete version of this theorem and then present its proof. Theorem 14. Let > 0, δ > 0 and ≤ log (1/δ). For a G-Lipschitz, B-bounded non-negative H-smooth loss function, Algorithm 1 satisfies ( , δ)-DP. If the private subroutine Ã guarantees Equation (1) with probability at least 1 -β, then withn pub = Õ (HD X ) 2/3 (npriv ) 2/3 G 2/3 (log(1/δ)) 1/3 + √ Hnpriv √ L(w * ;D) G √ log(1/δ)), with probability at least 1-β, L( w; D)-L(w * ; D)is at most Õ √ HD X √ npriv + B log (8/β) npriv L(w * ; D) + H X 2 D 2 npriv + B log (8/β) npriv + GD X log (4/β) npriv + Õ   √ HD 2 X 2 G log (1/δ) npriv 2/3 + H 1/4 D X √ G (log (1/δ)) 1/4 L(w * ; D) 1/4 √ npriv   Further, with n pub = Õ (HD X ) 2/3 (npriv ) 2/3 G 2/3 (log(1/δ)) 1/3 + √ Hnpriv √ L( w * ;Spriv) G √ log(1/δ)), with probability at least 1 -β, for any w ∈ W, L( w; D) -L( w * ; S priv ) is at mostÕ √ HD X √ npriv + B log (8/β) npriv L( w * ; Spriv) + H X 2 D 2 npriv + B log (8/β) npriv + GD X log (4/β) npriv + Õ   √ HD 2 X 2 G log (1/δ) npriv 2/3 + H 1/4 D X √ G (log (1/δ)) 1/4 L( w; Spriv) 1/4 √ npriv   .where w * and w * are population and empirical minimizers with respect to D and S priv respectively.Proof of Theorem 14. The privacy guarantee follows from the privacy guarantee of sub-routine Ã. The proof of the utility guarantee proceeds similar to that of Theorem 3. We define EQUATIONThe last term L( w; Spriv ) -min w∈ W L(w; Spriv ) is bounded by the guarantees of the private subroutine with probability at least 1 -β/4, L( w; Spriv ) -minEQUATIONTo bound the term L(ẘ * ; D) -L(w * ; D) in Equation (11), we apply smoothness to get,EQUATIONwhere the above holds for any w * ∈ H such that w * ∈ U W by optimality of w * 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 in [SST10] ). The final step holds with probability 1 -β/2 from Lemma 1 with n pub = O max R 2 log(2/β) α 2 , min m : log 3 (m)R 2 m (H) ≤ α 2 togetherEQUATION)where the second equality follows from Equation (12), instantiating the Rademacher complexity of linear predictors, concavity of x → √ x and AM-GM inequality. The third equality follows concavity of x → √ x and Bernstein's inequality, the fourth follows from Equation ( 14) and AM-GM inequality.Plugging the above, Equation (13) and Equation (12) into Equation (11), we get that withn pub = O max X 2 D 2 log(2/β) α 2, min m : log 3 (n pub )R 2 npub (H) ≤ α 2 , the following holds with probability at least 1 -β, L( w; D) -L(w * ; D)= Õ √ HD X √ n priv + √ Hα + B log (8/β) n priv L(w * ; D) + Õ H X 2 D 2 n priv + Hα 2 + B log (8/β) n priv + O GD X n pub log (1/δ) + log (4/β) n priv = Õ √ HD X √ n priv + √ HD X √ n pub + B log (8/β) n priv L(w * ; D) + Õ H X 2 D 2 n priv + HD 2 X 2 n pub + B log (8/β) n priv + O GD X n pub log (1/δ) + log (4/β) n priv (16) = Õ √ HD X √ n priv + B log (8/β) n priv L(w * ; D) + Õ H X 2 D 2 n priv + B log (8/β) n priv + O GD X log (4/β) n priv + O   √ HD 2 X 2 G log (1/δ) n priv 2/3 + H 1/4 D X √ G (log (1/δ)) 1/4 L(w * ; D) 1/4 √ n priv  The public sample complexity is,n pub = Õ (HD X ) 2/3 (n priv ) 2/3 G 2/3 (log (1/δ)) 1/3 + √ Hn priv L(w * ; D) G log (1/δ))This completes the first part of the theorem. For thee second part, we start from Equation (16),L( w; D) ≤ L(w * ; D) + Õ √ HD X √ n priv + √ HD X √ n pub + B log (8/β) n priv L(w * ; D) + Õ H X 2 D 2 n priv + HD 2 X 2 n pub + B log (8/β) n priv + O GD X n pub log (1/δ) + log (4/β) n priv ≤ L( w * ; D) + Õ √ HD X √ n priv + √ HD X √ n pub + B log (8/β) n priv L( w * ; D) + Õ H X 2 D 2 n priv + HD 2 X 2 n pub + B log (8/β) n priv + O GD X n pub log (1/δ) + log (4/β) n priv ≤ L( w * ; S priv ) + Õ √ HD X √ n priv + √ HD X √ n pub + B log (8/β) n priv L( w * ; S priv ) + Õ H X 2 D 2 n priv + HD 2 X 2 n pub + B log (8/β) n priv + O GD X n pub log (1/δ) + log (4/β) n priv ≤ L( w * ; S priv ) + Õ √ HD X √ n priv + B log (8/β) n priv L( w * ; D) + Õ H X 2 D 2 n priv + B log (8/β) n priv + O GD X log (4/β) n priv + O   √ HD 2 X 2 G log (1/δ) n priv 2/3 + H 1/4 D X √ G (log (1/δ)) 1/4 L( w; D) 1/4 √ n priv  where the second inequality holds form optimality of w * , the third from uniform convergence, Theorem 1 in [SST10] and AM-GM inequality, and the last by plugging in the following public sample complexity.n pub = Õ   (HD X ) 2/3 (n priv ) 2/3 G 2/3 (log (1/δ)) 1/3 + √ Hn priv L( w * ; S priv ) G log (1/δ))  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 in W, we get that with n pub = Õ (HD X ) 2/3 (npriv ) 2/3G 2/3 (log(1/δ)) 1/3, with probability at least1 -β, L( w; D) -L(w * ; D) = Õ √ HD X √ n priv + B log (8/β) n priv L(w * ; D) + Õ H X 2 D 2 n priv + B log (8/β) n priv + O GD X log (4/β) n priv + O   √ HD 2 X 2 G log (1/δ) n priv 2/3   Further, L( w; D) -L( w * ; S priv ) = Õ √ HD X √ n priv + B log (8/β) n priv L( w * ; S priv ) + Õ H X 2 D 2 n priv + B log (8/β) n priv + O GD X log (4/β) n priv + O   √ HD 2 X 2 G log (1/δ) n priv 2/3   .where w * and w * are population and empirical minimizers with respect to D and S priv respectively.Proof. The proof is almost identical to that of Theorem 15. We repeat the steps pointing out the differences and how the expressions change. We continue till Equation (12). Next, we apply smoothness which results in the key difference between the analyses,L(ẘ * ; D) -L(w * ; D) ≤ L( w * ; D) -L(w * ; D) ≤ E φ y ( w * , x ), w * , x -w * , x + H 2 | w * , x -w * , x | 2 ≤ E φ y ( w * , x )x , w * -w * + H 2 E | w * , x -w * , x | 2 ≤ ∇L(w * ; D), w * -w * + Hα 2 = Hα 2where last equality uses the fact that ∇L(w * ; D) = 0 since w * is the unconstrained minimizer. + Õ H X 2 D 2 n priv + HD 2 X 2 n pub + B log (8/β) n priv + O GD X n pub log (1/δ) + log (4/β) n priv = Õ √ HD X √ n priv + B log (8/β) n priv L(w * ; D) + Õ H X 2 D 2 n priv + B log (8/β) n priv + O GD X log (4/β) n priv + O   √ HD 2 X 2 G log (1/δ) n priv 2/3  The public sample complexity is,n pub = Õ (HD X ) 2/3 (n priv ) 2/3 G 2/3 (log (1/δ)) 1/3 .The second part follows similarly.To establish the GD X √ n term in the lower bound, we consider a one-dimenisonal problem where the loss φ y ( y) = -Gy y and marginal distribution D x as the point distribution on X such that the overall loss is E The proof uses the lower bound instance in the DP-SCO lower bound with public data, Theorem 1. We consider the case where D y is the point distribution on 1. Then for any y ∈ Y, Y = {1}, the loss function is then (w; (x, y)) = y w, x = w, x , as in Theorem 1. Hence, a labeled and unlabeled sample have the same information. We also set W to be the ball of radius D.Assume by contradiction there exists an ( , δ)-PA-DP algorithm, A, which achievesrate O GD X ( 1 √ npriv + √ log(1/δ) √ npriv) with o(n priv / log (1/δ)) public samples. Sincen pub = o(n priv / log (1/δ)) and d = ω(n ), Theorem 1 gives a lower bound on E [A(X pub , S priv ; D) -min w∈W {L(w; D)}] of Ω GD X min 1 √ n pub , d log (1/δ) n priv = ω GD X log (1/δ) √ n priv .Since ≤ 1, this is a contradiction.Proof. The privacy proof follows from the guarantee of exponential mechanism [MT07] . In particular, the sensitivity of the score function is at most 2 npriv min (B, GR) where the first follows from the loss bound of B and the second from the Lipschitzness and bound on predictors. Let h * ∈ arg min h∈H L(h; D) and h * ∈ arg min h∈ H L(h; D). From standard analysis based on uniform convergence, we haveEQUATIONwhere the above holds with probability at least 1 -β/2 and follows from guarantee of exponential mechanism [MT07] and uniform convergence ( [SSBD14] , see Theorem 16). We further have that log | H| = Õ(fat cα (H)) from Lemma 7.For the L( h * ; D) -L(h * ; D) term, we haveL( h * ; D) -L(h * ; D) ≤ L( h * ; D) -L(h * ; D) ≤ GE h * (x) -h * (x) ≤ G E h * (x) -h * (x) 2 ≤ 2Gαwhere the first step holds for any h * ∈ H by optimaility of h * over H, the second holds from the G-Lipschitzness of the loss function, the third from Jensen's inequality. The final step holds with probability 1 -β/2 from Lemma 1 with where c is an absolute constant.n pub = O max R 2 log(2/β) α 2 , min m : log 3 (m)R 2 m (H) ≤Proof. This follows directly from Theorem 8,log H = N 2 (H, α, S pub ) ≤ N 2 (H, α, n pub ) ≤ fat cα (H) log 2R α . Proof of Lemma 1 For h ∈ H, let h ∈ arg min h∈ H h -h 2,Xpub . Since H is an τ -cover, this gives us that h -h 2,Xpub ≤ τ . We have, h -h 2 2,D X = E h(x) -h(x) 2 = E h(x) -h(x) 2 - 1 n pub x∈Spub h(x) -h(x) 2 + 1 n pub x∈Spub h(x) -h(x) 2 ≤ sup h∈H   E h(x) -h(x) 2 - 1 n pub x∈Spub h(x) -h(x) 2   + τ 2 .The first term above can be seen as uniform deviation between the empirical and population risk, of another prediction problem, with squared loss, in the the realizable setting (with the responses generated by h). The squared loss is 1 2 -smooth and non-negative, so we can apply result of Theorem 1 in [SST10] instantiated in the realizable setting, which gives us that with probability at least 1-β, h -h 2 2.D X = O log 3 (n pub )R 2 npub (H) + R 2 log (1/β) n pub + τ 2 .Choosing n pub such thatn pub = O max R 2 log(1/β) α 2 , min m : log 3 (m)R 2 m (H) ≤ α 2, we get the claimed result.Algorithm 2 achieves optimistic rates on risk depending on realizability/interpolation conditions, that is, whenever L(h * ; D) or L( h; S priv ) is small. We start with the proof of the first part of the theorem. We have, where the second equality follows from Equation (21), concavity of x → √ x and AM-GM inequality. The third equality follows concavity of x → √ x and Bernstein's inequality, the fourth follows from Equation (23) and AM-GM inequality.Theorem 17. Algorithm 2 with γ = 2B npriv satisfies -PA-DP. For n pub = O max R 2 log(2/β) α 2 , min m : log 3 (m)R 2 m (H) ≤ α 2 < ∞EQUATIONThe number of public samples then isn pub = O max R 2 log (2/β) α 2 , min m : log 3 (m)R 2 m (H) ≤ α 2 = Õ   X 2 ( M j=1 R j ) 2 max log (2/β) α 2 , M α 2   = Õ   ( X ( M j=1R j )) 2/3 (n priv ) 2/3 M 1/3 log (2/β)   .Note that R ≤ D X . Further, we have [KST08, FGV17] , . The number of public samples simplifies as,R m (H) = O D X m 1/n pub = O max R 2 log (2/β) α 2 , min m : log 3 (m)R 2 m (H) ≤ α 2 = Õ (n priv ) 2 r+1 log (2/β) .which is satisfied from our choice since r ≥ 2. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: No such assets are used as a part of this research.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses for existing assets Question: 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?Answer: [NA] Justification: No such assets.Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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.We note that concurrently and independently, version 2 of[LLHR23],[LLHR24], obtained a lower bound of Ω min1 √ n pub , 1 √ n + √ d n, but their lower bound is limited to symmetric procedures.The term semi-DP algorithm has also been used in some works.This claim is based on a simplification of their theorem statement. Specifically, because npub ≤ n /d, which also implies d ≤ n , their lower bound Ω R min1 √ n pub , d n + 1 √ nsimplifies.A differentiable map Ψ is r-uniformly convex w.r.t. • , if Ψ(u ) ≥ Ψ(u) + ∇Ψ(u), u -u + 1 r u -u r . 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.

The main contributions of this work are:
1. 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.
2. 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$.
strength_weakness: strength_weakness: 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.
2. 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.
questions: 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: limitations: No additional limitations need to be discussed.
paper_summary: paper_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.
strength_weakness: strength_weakness: N/A
questions: 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: limitations: Refers to the weakness and questions.
paper_summary: paper_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.
In 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).
strength_weakness: strength_weakness: - 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.
- 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.
- 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.
- 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?
- Corollaries 2 and 3 are frankly hard to interpret, and their significance is unclear to me. Maybe more effort is needed in this section.
- 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).

Minor:
- 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).
- There are minor formatting issues like a broken reference line 359 and some typos.
- In the discussion following Cor.3, how do the $log d$ terms appear?
questions: questions: Please see questions in the weaknesses.
limitations: limitations: As mentioned above, the paper should be clearer about its assumptions, regimes in which its bounds are tight, etc.

Comments: title: Response to rebuttal
comment: Thank you for your rebuttal! I will keep my score.
Thank you for your response. We will add the discussion about Corollary 2 and 3 to the paper. We will also fix the typo regarding $n_{pub}$. 

To further clarify Theorems 3, 6, and 7, there are alternative ways to the state the condition on $n_{pub}$. For example,  we can either state it as 1) "There exists some​ number $n_{pub} = \tilde{O}(n_{priv} \epsilon)$ such that ..."  or  2) "There is a constant c > 0 s.t. for any​ $n_{pub} \geq c n_{priv} \epsilon$, we have ..."  To be clear, our intention for what is written in the paper is *not* an upper bound of the form "for any $n_{pub} = \tilde{O}(n_{priv} \epsilon)$ but rather an upper bound on the number of samples the algorithm would ever need. To make it more clear, we can replace what is in the paper with "Then there exists some  $n_{pub} = \tilde{O}(n_{priv} \epsilon)$..." or "Then there exists a universal constant c such that for any $n_{pub} \geq c n_{priv} \epsilon$..." 

With regards to the message of the paper, we are happy to be more explicit about our claims in the abstract. Specifically, we can say that our claim applies to the problem of stochastic convex optimization of Lipschitz functions and our claim is made with respect to asymptotic rates. Please let us know if there are other assumptions worth enumerating in the abstract.
Thank you for the response and clarifications.

- The discussion about Corollary 2 and 3 is helpful and should be expanded in the paper.

> Theorems 3, 6, and 7 claim the rate is achievable given access to some number of public samples

- Do you mean that there should be a lower bound on $n_{pub}$ (in addition to the upper bound) that is missing from the statements of these theorems? Please clarify.

- Regarding the non trivial regime: It appears there is a typo in the paper that led to my misunderstanding (both conditions applied to $n_{pub}$, instead of $n_{pub},n_{priv}$...) It is clear now (but please make sure to correct the typo).

- Regarding the message of the paper: are the authors willing to rephrase some of the statements made in the paper? For example, the abstract claims that "the simple strategy of either treating all data as private or discarding the private data, is optimal". This should be properly qualified. Similarly for the statement "more sophisticated attempts at leveraging public data will yield no benefit".
Thank you for the clarification. I will maintain my current score.