Oracle-Efficient Differentially Private Learning with Public Data
Authors: Adam Block
Mark Bun
Rathin Desai
Abhishek Shetty
Steven Wu
Venue: NeurIPS 2024 poster (2024)
Keywords: Oracle Efficiency
Differential Privacy
PAC learning
Primary area: privacy
TL;DR: We provide oracle-efficient algorithms capable of differentially private PAC learning any learnable function classes in the presence of public, unlabelled data.

Abstract: Due to statistical lower bounds on the learnability of many function classes under privacy constraints, there has been recent interest in leveraging public data to improve the performance of private learning algorithms. In this model, algorithms must always guarantee differential privacy with respect to the private samples while also ensuring learning guarantees when the private data distribution is sufficiently close to that of the public data.  Previous work has demonstrated that when sufficient public, unlabelled data is available, private learning can be made statistically tractable, but the resulting algorithms have all been computationally inefficient.  In this work, we present the first computationally efficient, algorithms to provably leverage public data to learn privately whenever a function class is learnable non-privately, where our notion of computational efficiency is with respect to the number of calls to an optimization oracle for the function class.  In addition to this general result, we provide specialized algorithms with improved sample complexities in the special cases when the function class is convex or when the task is binary classification.

Oracle-Efficient Differentially Private Learning with Public Data
Adam Block Department of Mathematics
Mark Bun
Department of Computer Science
MIT Cambridge, MA 02139
Boston University Boston, MA 02215
ablock@mit edu
mbun@bu. edu
Rathin Desai
Abhishek Shetty
Department of Computer Science
Department of Computer Science University of California, Berkeley
Boston University Boston, MA 02215
Berkeley, CA 94720 shett sherty@berkeley. edu
rathin@bu. edu
Zhiwei Steven Wu School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 zstevennvu@cuu edu
Abstract
Due to statistical lower bounds on the learnability of many function classes un- der privacy constraints, there has been recent interest in leveraging public data to improve the performance of private learning algorithms. In this model, algo- rithms must always guarantee differential privacy with respect to the private sam- ples while also ensuring learning guarantees when the private data distribution is sufficiently close to that the public data. Previous work has demonstrated that when sufficient public, unlabelled data is available, private learning can be made statistically tractable, but the resulting algorithms have all been computationally inefficient. In this work, we present the first computationally efficient, algorithms to provably leverage public data to learn privately whenever function class learnable non-privately, where our notion of computational efficiency is with re- spect to the number calls to an optimization oracle for the function class. addition to this general result, we provide specialized algorithms with improved sample complexities in the special cases when the function class is convex or when the task is binary classification.
Introduction
Differential privacy (DP) [Dwork al., 2006] is standard guarantee individual-level privacy for statistical data analysis. Algorithmic research on differential privacy aims to understand what statis- tical tasks are compatible with the definition, and what cost, e.g.. in terms of sample complexity or computational efficiency. Unfortunately. it is known that some tasks may become more expensive or outright impossible to conduct with differential privacy. For example, in the setting of binary classification, there is no differentially private algorithm for solving the simple problem of learning a one-dimensional classifier over real numbers [Bun et al., 2015, Alon al., 2019].
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Motivated in part by such barriers to full-fledged private learning, many papers have considered relaxing the model allow the use of auxiliary "public" data Balcan and Feldman [2013]. Bassily et al. [2019, 2020b, 2022, 2023], Kairouz et al. [2021], Amid et al. [2022], Lowy et al. [2023]. Such data may be available if individuals can voluntarily opt-in to share or sell their information to enable a particular task. Alternatively, a data analyst might have background knowledge about the underlying data distribution from the results of previous analyses, or hold a plausible generative model for it. These situations are captured by semi-private learning, first discussed by Balcan and Feldman [2013], formally introduced by Beimel et al. [2014] and subsequently studied by Bassily et al. [2019], Hopkins al. [2024]. In this model, a learning algorithm is given n "private" samples from a joint distribution D over example-labe pairs, as well as m unlabeled "public" samples from the same marginal distribution over examples. The algorithm must be differentially private with respect to its private dataset, but can depend arbitrarily on its public samples. For learning a binary classifier over class F with a VC-dimension vc(F), these papers showed that in the presence of (vc(F)) public unlabeled samples, every concept class F is agnostically learnable with (Fv((F) private labeled samples, matching what is achievable without privacy guarantees.
While these results essentially resolve the statistical complexity of semi-private learning, they do not address the question of computational efficiency. These algorithms proceed by drawing enough public samples to construct a cover for the class F with respect to the target marginal distribution on examples, and then using the exponential mechanism [McSherry and Talwar, 2007] to select hypothesis from this cover that fits the private dataset. As the size of this cover is exponential in vc(F), constructing it explicitly is computationally expensive. This paper aims to address the fol- lowing question: Is such computational overhead really necessary if F exhibits additional structure that make non-private learning tractable?
In this work, we give new semi-private learners that are efficient whenever fast non-private algo- rithms are available. More specifically, our main result is generic semi-private algorithms for regres- sion and classification that are oracle-efficient in that they run in polynomial time given an oracle solving the non-private empirical risk minimization problem for F, and have sample complexity polynomial in the usual parameters such as Gaussian complexity and VC dimension.
Theorem (Informal version of Theorem 2). Fix a function class F:X - 1-1, Then there is an oracle-efficient, (e, deifffrrrrrl private algorithm (Algorithm 2) using poly(sup m Gm())) labeled private samples (where, (m) denotes the Gaussian complexity of function class F), un- labeled public samples, and calls to an empirical risk minimization oracle for F that learns an approximately optimal predictor f E F.
While Theorem captures extremely broad learning settings, the polynomials governing its sample complexity are rather large. We identify several important cases which the sample complexity can be improved and the number of oracle calls is only 2. In the case where the function class FF convex, we give a variant of Algorithm 2. inspired by gellow-therrggllaiizee -leade, with signif- icantly improved sample complexity as function of the desired error (Theorem 3, Algorithm 3). Finally, in the special case of binary classification (i.e.. Boolean F under the 0-1 loss), we give a completely different oracle-efficient algorithm with improved sample complexity (Theorem 4, Al- gorithm 4), which requires the private sample size to grow at the rate of O (vv(F)))? Prior work of Bassily et al. [2018) gave an oracle-efficien algorithm in this setting with somewhat better sample complexity than ours, based on a reduction to private classification. Meanwhile, our algorithm has the advantage of being able to guarantee pure (rather than only approximate) differential privacy al- gorithm, as well as making only two oracle calls as opposed to the polynomially many as a function of and the target accuracy. Our results in the binary classification setting can also be viewed as an extension of Neel et al. [2019], which gives oracle-efficient private learners for structured function classes JF that have small universal identification set [Goldman et al., 1993]. Our results relax this stringent combinatorial condition by leveraging a small public unlabelled dataset, which allows us private learner for any function class F with bounded VC-dimension.
to design
In fact, our results also address a somewhat more general setting than the semi-private model de- scribed so far. Specifically, our results automatically handle the setting where there may be bounded distribution shift between the public and private data. In particular, all of our results hold as long as the public unlabelled data distribution and the private marginal distribution over the fea-
2

---

ture space have density ratio bounded by o. The standard semi aimi-private setting corresponds to the special case where o I. Taking this view, we can interpret our results as oracle-efficient pri- vate learning in the smoothed learning setting. Our algorithms achieve accurate learning provided that the private marginal distribution does not deviate too much from a public reference distribution. However, our privacy guarantees hold even if the private data distribution has unbounded distribution shift from the public data.
1.1 Related Work
Our work brings together ideas and techniques from multiple literatures.
Oracle efficiency in private and online learning. Our notion of oracle-efficiency is standard in (theoretical) machine learning to model reductions in a world where worst-case hardness abounds, but optimization heuristics (e.g., integer programming solvers, non-convex optimization) often enjoy success. Within the differential privacy literature, oracle-efficient algorithms are known for binary classification with classes Jf that admits small universal identification sets [Neel et al., 2019], syn- thetic data generation [Gaboardi et al., 2014, Nikolov et al., 2013, Neel et al.. 2019, Vietri et al., 2020], and certain types of non-convex optimization problems [Neel al., 2020J. Oracle-efficiency is also well-established approach in online learning [Kalai and Vempala, 2005, Hazan and Ko- ren, 2016, Kozachinskiy and Steifer, 2023, Haghtalab et al., 2022a, Block and Simchowitz, 2022, Block and Polyanskiy, 2023, Block et al., 20.3a,b]. an area with deep connections to differential privacy [Alon et al., 2019, Abernethy et al., 2019, Bun et al., 2020, Ghazi et al., 2021], Indeed, our new semi-priee unii-triatte learning algorithm Algorithm 2 adapts a follow-the sellow-thepertuueed-leeee perturbed-leader inspired algorithm [Block al., 2022] from the setting of smoothed online learning.
DP learning and release with public (unlabelled) data Our results contribute to long line of theoretical work that leverages public data for private data analysis. In particular, our work provides general computationally efficient algorithms (in the oracle efficiency sense) for semi-private learning (Beimel et al., 2014]. In addition the work in this direction we discussed above, several recent papers Bassily et al. [2022, 2023] developed efficient algorithms for private learning with domain adaptation from a public source. That work accommodates more general notion of distribution shift than ours, but makes essential use of labeled public data, as well as handling only restricted concept classes or loss functions. There has also been work that leverages public data remove statistical barriers in private query release [Bassily et al., 2020a] and density estimation Bie et al. al. [2023]. Papernot et al. [2018], Yu et al. [2022], Golatkar et al. [2022], Zhou et al. [2021] and Liu et al. [2021a,b] give empirical guarantees to the problem of private learning and private synthetic data from public samples respectively.
[2022], Ben-David
Smoothed Analysis in Online Learning. Smoothed analysis was pioneered in Spielman and Teng [2004) for the purpose of explaining the empirical success of algorithms whose worst-case behavior is provably intractable. More recently, the framework has come to online learning [Rakhlin et al., 2011, Haghtalab et al., 2020, 2022b, Block al., 2022, Haghtalab et al., 2022a, Block and Sim- chowitz, 2022, Block et al., 2023a,b] in order to circumvent the strong statistical [Rakhlin et al., 2015] and computational [Hazan and Koren, 2016] lower bounds that worst-case data can induce. The assumption of smoothness has also been used in learning more broadly [Durvasula et al., 2023, Disa-Bianchi et al., 2023] and its assumptions have been relaxed [Block and Polyanskiy, 2023].
2 Preliminaries
In this section, we formally introduce our setting. Let X' denote the feature space and y be the label space. In general, we consider y = [-,, but in the special case of binary classification setting, we have y {0, 1). In general, we study learning algorithms A that map a dataset with n examples from X' x y to a predictor in a function class F. We require A to satisfy differential privacy, defined below.
In fact, this condition can be further relaxed to only assuming the two distributions have a bounded f- divergence.
3

---

Definition 1 (Differential Privacy Dwork et al. [2006]]. Let A: (X x V))" - F be randomized 3) be data sets. We say that D and D' are neighboring (D) D
algorithm and D, D' E (X i.e. they differ in at most one datum. We say that A is (e, 8)-iffeerentiill private for all neighboring datasets D, D', and for all measurable 9 C F. it holds that TP (A(D) E g) S ef P (A((D)) E 9) + 5. If 5 = O, we say that A is e-(purely) differentially private.
(D' D I
As defined, it is trivial to construct algorithms that are differentially private by outputting functions independent of the data set; for an algorithm to be useful, however, we also require that it learns in a meaningful sense. Thus, in the context of learning, we consider the following accuracy desideratum.
Definition 2. Let A : (& x y)" + F be a randomized algorithm. We say that A is an (a, 3)- leamer with respect to measure on X x y and loss function L F - [-1, 1] if, for D sampled independently from v. it holds that P (L(((D)) S JeF L(f) + a) 2 1 1116 B. For regression
problems, we consider the loss function I. to be induced by function e ) [0. 1), convex and X- X-Lipschitz in the first argument, such that L(f)- = (((((),)
For simplicity, we will denote the empirical loss on a data set D as LD(f) = 1 Exx,y) (X(,,, Yi). We emphasize that in contradistinction to the standard notion of PÁC- leamability [Valiant, 1984], our requirement is weaker in that we only require instribution-dependae learning, i.c. the algorithm A is allowed to depend on // in some bo-be-peecifid way. This is nec- essary in setting as it is well known that distrbbttion-indeeeneent differentially private PAC learning is possible only for very restricted classes of functions F with bounded Littlestone dimen- sion [Alon et al., 2019, Bun et al., 2020]. To make private learning statistically tractable for broader classes of functions, we consider the following restriction on v:
Definition 3. Given measure μ
A(X) and parameter
(0, 1]. say that V is or- 1. We suppose that the learner has access to m samples
smooth with respect to if dy'
Zi...., Zm ~ μr that are independent of each other and the training data D and thus A may depend on these samples.
We remark that Definition 3 can be significantly relaxed by assuming only that (f(v=ll)) I as in Block and Polyanskiy [2023], where (-Il-) is a sufficiently strong f-divergence*. In this case, the statistical rates presented below will be worse and depend on J, but the algorithms and privacy guarantees will remain unchanged. Critically, we do not require that our algorithms are private with respect to
which we treat public, unlabelled data. The key reason that this public data helps us circumvent the lower bounds is that it gives us access (albeit indirectly) to a small subclass of the hypothesis set that still has approximately good hypotheses. Since our primary focus is to design computationally efficient private learners, we cannot directly handle either the original hypothesis class or the small proxy that the public data gives us access. Instead suppose access to the following ERM oracle:
Definition 4. Given a function class F X + R, data set D = tII,..., Imb C X' and loss functions fi..... Lm : R + R, we define the empirical risk minimization oracle ERM : F + R such that ERM(F, LD) argmin (D (f), where Lo(f) (f (x)())))
ERM oracles are standard computational models in many learning domains such as online learning [Kalai and Vempala, 2005, Hazan and Koren, 2016, Block et al., 2022, Haghtalab et al., 2022a] and Reinforcement Learning [Foster and Rakhlin, 2020, Foster et al., 2021, Mhammedi al., 2023b.a] Assuming access to ERM allows us to disentangle the computational challenges of optimizing over specific function classes from the specific challenge of differentially private learning as well to avoid the well-known intractability results for nonconvex optimization [Blum and Rivest, 1988] that do not accurately reflect the realities of modern optimization techniques (e.g., integer program solvers, SGD). We note that our algorithms also work in the case of ERM oracles with additive error by minor modification to the analysis similar to the one [Block et al., 2022]. We remark that applying Neel et al. [2019, Theorem 8] gives black-box robustification procedure for purely private, oracle-efficient algorithms, which ensures that the privacy guarantees continue to hold even when the oracle may fail to optimize the objective. In particular, Algorithms 3 and 4 below, when run in their pure DP forms can be made robust at a minimal cost on accuracy. We defer to Neel et al. [2019] for further discussion on this topic.
'These divergences include the well- known KL divergence and Renyi divergence. For comprehensive introduction f-divergences, see Polyanskiy and Wu [2022+].
4

---

Algorithm 1: Perturb: An algorithm for perturbing function with noise on public data.
1: Input Function f F, distribution A(R), scale 7 2 0, public data D ?Zi...., Zm
2: Sample S1...., Sm ~ Q.
3: Define R(f) = | - -
4: Output f = ERM
is well-known that even absent differential privacy guarantees, learning arbitrary function classes impossible; we introduce the notions of complexity that are relevant to our results. We begin with the standard notion of VC dimension:
Definition 5. Let F X' - {0, 1} be a function class. We say that set of points æ1, ................................ Fd X shatters F if for all Eidd E {0, 1J", there is some fe such that fz(())
e; for all The VC dimension of F, denoted vc(F), is the largest d such that there exists a set of d points shattering F.
In addition to VC dimension, we also use the Gaussian complexity of a function class:
Definition 6. Let F X' + 1-1, 1] be a function class and 01....;2 Im E 2' be arbitrary points. We let Wm, F - IR be the canonical Gaussian process on F, i...,
Wmn wm)(f)
Σ E. f(x;),
(1)
mm
where & are independent standard Gaussians. We define the (data-dependent) Gaussian complexity of F to be E Wm([)) the average Gaussian complexity as (m. =
Esupse fer (f)l. and the worst-case Gaussian complexity of F be Gm(
sup SuP2,... Fm E supper wm (f)]-
Both vc(F) and Gm are well known measures of complexity from learning theory and their relationships to other notions of complexity like covering number well-understood [Mendelson and Vershynin, 2003, Wainwright, 2019, Van Handel, 2014]. In particular, it is well-known that (m(F) = O /vc(F) [Dudley, 1969, Mendelson and Vershynin, 2003] and that standard PAC- learning is possible if and only if Gm (F) of mm)) [Wainwright, 2019, Van Handel, 2014]. We remark that different texts use different scalings for Gm,),, with some replacing the m 11/2 factor choice of scaling is motivated by the fact that natural complexity measure for many (Donsker [Wainwright, 2019]) function classes that our algo- rithms depend on is sup,, 9m (F), which most compactly represented with the present scaling.
in (1) with m1 and others omitting it entirely;
Notation. We always reserve IP and E for probability and expectation with respect to measures that are clear from the context. We denote by A(X) the space of measures on some X' and for any l E A(X) we let |l-11g denote the (²((u) norm, i.c., [[ = (z>))f(Z) Similarly, for m points Zi,..., 7m E X, let Il-IIm denote the empirical 1,2 norm these points that [ = m 1, Emh f(Z,)². We reserve wm for the canonical empirical Gaussian process on as in (1) and L for a functional on F.
3 Algorithms for Differentially Private Learning
In this section, we provide a general template for constructing differentially private learning algo- rithms with public data and instantiate this template with two oracle-efficient algorithms. Our first algorithm applies to arbitrary bounded function classes, whereas the second algorithm only applies convex classes but has improved sample complexity. Our general template is broken into the following two steps: (i) Use ERM (cf. Definition 4) and the public data to construct an initial estimate f that is a good learner and satisfies stability with respect to II- (ii) Output f as the function that minimizes - of independent random variables sampled according to some distribution Q. The second step accomplished through Algorithm 1 and is the same across our algorithms. The first step, however,
<l),,, where 2 0 is scale and Ç= (Çi,..., Sm is vector
5

---

Algorithm 2:
Oracle Efficient Private Learner (Perturbation)
1: Input Oracle ERM, perturbation parameter 7 > public data set D= iI,...., Zm J. private data set D = (X,, Y 1 I S n), function class F, loss function noise level ? > 0, number of iterations J E N, noise distribution Q ARR).
2: for = ..2......JJ do
Sample (0)
........ Sm eGi (0.
3:
4: Define wht) :F + R such that
())
1
Σ f(Z). i=1
(2)
Vm
5: Define ( - Th such that (() Σ (X,Y)DD (((()), Y.) + n. w.w.m (f).
Define f, = LI-MMM
end
7: Define J fj. 8: Output f Perturbbf (.)
By running Algorithm
algorithm-sper -ppecffcc and is the primary factor affecting the sample complexity. The intuition for our template is as follows. We need to show that f is both a learner and is differentially private. To see why the template produces good learner, note that if Z, ~ μ are independent and m is sufficiently large, then Il-Ilm I1-1lp- Thus if y is small, then - << and En [ En(l(f)
whenever is Lipschitz. By smoothness, a similar guarantee holds for expectations with respect to and thus [ a good learner. To see why is differentially private, note that by choosing Q to be a standard Gaussian, we can ensure that the likelihood ratios of choosing ʃ given versus f' are controlled by - I|ff Thus, if is stable with respect to I1-1l,m then f will be private. The intuition of the stability of f is discussed in Section 4.
We now make the above intuition precise by instantiating this template in our most general setting in Algorithm 2. We construct f by running ERM on perturbed version of the empirical risk minimization problem and then averaging. Specifically, for j E [J], we define _ F + R as sample path of noncentred Gaussian process in (2) and let f, denote the minimizer of L()) over F. We then output f as the average of f1,..., f.. f.. We present motivation for the particular choice of f. as well as the analogue in Algorithm 3, in the subsequent section. The following theorem shows that if Q is chosen correctly, this algorithm is an oracle-efficient differentially private learner whenever V smoohhh with respect μ..
Theorem 2. Suppose that F X > [-1, 1) is function class and μ E ((X) is a measure such 1]-,,1] x [1,1]] + [0,1] be a loss function that is convex and
that inf feF Ilʃ 2 3. Let é X-Lipschitz in its first argument. Q = 1) in Algorithm 1, then for any e, 8, a, E (0, 1), there are choices of n. > and m N, all polynomial problem parameters and given in Appendix C.6, such that if
n. = poly ( log (1)
( ,log (1)
=olo
then the e returned by Algorithm 2 is (e,,)-differenticn private. v is o-smooth with respect to μ, then is an (a., -learee with respect to V. and
We emphasize that Algorithm 2 is always differentially private, independent of v; however, our al- goirthm is only good learner if v, is smooth with respect to j.. We remark that all of the conditions in Theorem are standard with the exception of the assumption that || > 2/3 for all f F.
This condition is easy to ensure by setting ā -+2 where z" is distinguished point such that f(=*)= = 1 for all f E F; note that this process deflates most by a factor of 3 while ensuring the lower bound on the norm of Replacing μ by then suffices ensure that Theorem holds.

---

Algorithm 3: Oracle Efficient Private Learner (Regularization)
1: Input Oracle ERM, perturbation parameter 7 > public data set D= iI,,..., Zm J. private data set D = {X,, Y 1 S E S n), function class F, loss function l, noise level ? > 0, number of iterations J E N, noise distribution Q ARR).
2:
Define F + I such that
L()=
E (X,,YJED
(.) + +- 11
(3)
3: Define f ERM(L,F)
4: Output ʃ
By running Algorithm
We further remark that it is classical that the complexity notion supm In (F) is upper bounded by /Vc(F) for binary function classes and [log([FF for finite classes [Wainwright, 2019], ensuring that the proven sample complexity is polynomial in all standard notions of function class complexity. For even more complex function classes, where 7T (F) w(1), similar results hold, although with worse rates; further dicussion, as well as the precise polynomial dependence of hyperparameters and sample complexity, can be found in Appendix C.
While Algorithm 2 succeeds in our desiderata under general assumptions, the sample complex- ity is a large polynomial of the desired accuracy. Indeed, the sample complexity of Algorithm scales like O (vc(F) E-3 a -1),, which is significantly worse than the O (vc(F) a =) sample complexity that non non-private algorithm such ERM can achieve (Wainwright, 2019]
the O (vc(F) a -2 -²2 sample complexity achievable by private, inefficient algorithms with public unable to achieve pure differential privacy guar-
data [Bassily et al., 2020b]. Furthermore, antee with this algorithm. We now address both issues by providing an improved algorithm in the special case that the function class F is convex. While still use Algorithm 1 as subroutine, in Algorithm 3, motivated by the difference between Follow the Perturbed Leader (FTPL) and Fol- low the Regularized Leader (FTRL) [Kalai and Vempala, 2005, Cesa-Bianchi and Lugosi, 2006] in online learning, we modify the way in which we choose our initial estimator f- In particular, we eliminate the averaging step and redefine w be a strongly convex regularizer instead of a Gaussian Process perturbation. More specifically, we define L in (3) as the empirical loss regularized by I1-11 and output f = ERM(C, F). We have the following result:
Theorem 3. Suppose that F : X [- is convex function class and é: [-1, x [-1.1]
[0, 1] is convex and X-Lipschitz in its first argument. Suppose that Zi...., Zm ~ I are indepen- dent and Q NN, 1). Then there n, 7i, polynomial in problem parameters and given in Appendix C.6 such that, if
poly (log (8-1) log (8-1),2) (F))
then the I returned by Algorithm 3 is (e, diifffernttl private. If Vs is a -mmoth with respect to μ. then I is an (0,,3) B))-larnerr with respect to Us and E. Furthermore, if Q = Lap(1), and
n = poly
(8-1),
then Algorithm is e-purely differentially private and an (a, PPC learner for any a-smooth Vz-
As in the case of Theorem 2, we can easily generalize Theorem 3 to apply to function classes F where (F) = (1) at the cost of worse polynomial dependence the sample complexity. We again omit this case for the sake of simplicity. While the sample complexity of Algorithm 3 is a marked improvement over that of Algorithm 2, it remains a far cry from the desired O (a--) rates of non-private learning that computationally inefficient private algorithms leveraging public data are able to achieve [Bassily et al., 2019]; we leave the interesting question of producing an oracle-efficient private algorithm with optimal sample complexity to future work.
Finally, we remark that even in the case where F is not convex, Algorithm can applied to cFnv(F), the convex hull of F. if we assume the learner has access to ERM', stronger ERM oracle
7

---

that can optimize over conv(F). In this case, Theorem 3 supercedes Theorem 2 as it is easy to see that Gm( = Im (conv( (F) and thus the sample complexity of Algorithm 3 is strictly better than that of Algorithm and the pure differential privacy result applies.
4 Analysis Techniques
In this section, we outline the proofs of our main results, with full details deferred to Appendix C. As is suggested by our template, the proof of the privacy part of Theorem 2 rests on two results: the first shows that Q is a standard Gaussian (resp. exponential) then stability of f with respect to Il-llm can be translated into differential privacy. The second shows that f will be stable with respect to Il- Similarly, the proof that f is a good learner first shows that that and f are close. We begin with the more technically novel parts and show that, under standard assumptions, Algorithms 2 and result in f that are stable in IIll In our proof of Theorem 2, we provide an improved analysis of the Gaussian anti-concentration result from Block et al. [2022], which may be of independent interest. We prove the stability of Algorithm 3 using a technique common in online learning. We then show that stability in II-Il can be boosted to differential privacy guarantee using the Gaussian and Laplace Mechanisms [Dwork et al., 2006]. Finally, we apply standard learning theoretic techniques to show that is a good learner.
a good learner and then
4.1 Stability Analysis
In this section, we explain how to prove that Algorithms 2 and 3 are stable with respect to Il-IIm- Our stability results further cement the connections between differential privacy and online learning noted in Abernethy et al. [2019] as both algorithms are primarily motivated by online learning tech- niques. We begin by describing the stability analysis of Algorithm 2. The key lemma underlying the stability of Algorithm is an improved version of Gaussian anti-concentration result from Block et al. [2022], which may be of independent interest.
Proposition 1. Let F denote a subspace of the unit ball with respect to a norm ||-I| induced by an inner product (..)) and let m, u' :F IR be measurable functions such that [|m - mm' m''llo S T. Ifw is a centred Gaussian process on FF with covariance kernel given by (-.)). {2(f) m ((fff+++))) (f), = argmin yer (2))), and S' and f are defined similarly, then for any P. > 0, holds that P f[ p)
87 pai2n
E (APFErw(()) where n²² = inf JeF E (f))
The proof proceeds in similar way to that of Lemma 33 from Block al. [2022], but involves a tighter analysis in several steps in order to improve the bound. The intuition for the result is straightforward: f is the minimizer of the Gaussian process 22 then with reasonable probability, almost minimizers of Ω (as measured by the tolerance r) are within a radius of f as long as the Gaussian process nontrivial in the sense that all indices f have sufficiently high variance. Moreover, the quantitative control on the probability of this event depends in natural way both on T and P as well as on the Gaussian process w: more complex spaces F. and lower variance processes lead to worse anti-concentration guarantee. Finally, we note that Proposition 1 is an improvement of Lemma 33 from Block et al. [2022] in that the quantitative bound on the probability of anti-concentrattinn is tighter by polynomial factors in p, and K.
Like essentially all cnte-concentration results [Chernozhukov et al., 2015], Proposition holds only with moderate probability in the sense that the guarantee is polynomial in the scale p; this fact is in contradistinction to concentration inequalities which tend to hold with high probability exponential in the scale. This discrepancy is precisely what motivates the averaging in Line 7 of Algorithm 2. Indeed, we can use Proposition to show that if f, is as in Line 6 of Algorithm 2 and S is defined analogously with respect to D', then with moderate probability ||5, - -f is small. Using Jensen's 's inequality and a standard chernoff bound, we can then boost this moderate probability guarantee into high probability guarantee to show that if J sufficiently large, then /| I'll is small with high probability. We formalize this argument in the following lemma:
Lemma 1 (Stability of Algorithm 2). Suppose that F X [-1.1] is a function class and E: 1- x2 > [0, 1] is a bounded loss function. Suppose that D, D, are neighhoring datasets and let f be as in Line 5 of Algorithm 2 and J be defined analogously with respect to D'. Then
8

---

for any 2. > O, with probability at least 1 - 5, over the Gaussian processes w(), ||f f' S
2
(E (upprerwm(()) 1/3
log
We note that the worse dependence y in Lemma as compared to Proposition arises from integrating the tail bound to obtain the control on || -J Il expectation necessary to apply -
Jensen's inequality; details can be found in Appendix C.I.
We now turn to the stability of Algorithm 3. The proof is based on a technique borrowed from online learning and the analysis of the Follow the Regularized Leader (FTRL) algorithm [Gordon, 1999, Cesa-Bianchi and Lugosi, 2006].
Lemma 2 (Stability of Algorithm 3). Suppose that l is convex and X- X-Lipschitz in its first argument. Let D, D' denote neighboring data sets and let f denote the output of Line in Algorithm and f be the analogous output evaluated on DD 1f is convex, then, [ f'll...
v
The proof of Lemma 2 can be found in Appendix C.2 and rests on elementary properties of strongly convex functions. We note that relative to Lemma 1, the dependence on 1) in Lemma 2 improved, which in turn leads to the better sample complexity exhibited in Theorem 3. With stability of Algo- rithms 2 and 3 thus established, we proceed to analyze the effect of the output perturbation.
4.2 Output Perturbation Analysis
We now turn to the analysis of Algorithm 1. In order to boost a stability guarantee into one for differential privacy while remaining a good learner, we require the output perturbation to be sufficiently small as to not not affect the learning guarantee of f while at the same time being ensure privacy. We balance these two competing objectives by tuning the variance of the added noise. This part of the analysis is relatively standard in the differential privacy literature [Chaudhuri al., 201 I, Neel et al., 2019], with the bound on the size of the output pertur- bation following from standard tail bounds on Gaussian and Laplace random vectors. The privacy guarantees are similarly standard and summarized in the following lemma:
sufficiently large
Lemma 3. Suppose f F the output of an algorithm A D - F that is p-stable with respect to I1-IImm i.e., for any neighboring data set D', it holds that A(D)) S p. Then applying Algorithm I with Q = (N 1) to ʃ results in (e, ()-rivtre algorithm if
(1 + .. 1..voog log (t) SSS.. Similarly, if Q Lop(r)) then the algorithm is E-purely private if //3/2/7.00 PSS..
2y²
3/2
This standard result is proved Appendix C.3. Note that, perhaps counterintuitively, the privacy loss increases with the public data. This relationship occurs because the algorithm is implicitly discretizing the function class, where more public data leads to a finer discretization; though finer discretizations lead to higher accuracy, they also leads to more privacy loss. Furthermore, note that even were the whole marginal distribution known, the privacy-accuracy tradcoff is dictated by the number of labelled samples, not
The balance between privacy and learning is quantified in the choices of m and
y. If is too large, then f will be private but poor learner, whereas the opposite occurs if y is too small. Similarly, if m is too large then privacy is reduced whereas m is too small then ||- is a poor approximation for I1-11p.-
4.3 Learning Guarantees and Concluding the Proof
By combining Lemma 1 (resp. Lemma 2) with Lemma 9, we can establish the privacy of Algo- rithm 2 (resp. Algorithm 3) as long as the tuning parameters m, 7, 77, and J are chosen correctly. We now sketch the proof that these algorithms comprise good learners in the sense of Definition 2. We break our proof into three components, the first two of which are standard learning theoretic results. The first lemma says that if m > 1, then Il is a good approximation for ||-11,--
Lemma 4. Let F X + 1-1, 1] be a bounded function class and let Zi, Zm ~ μ be inde- pendent samples. Then for any $ >> 0 it holds with probability at least 1 - 3 that for all f E F,
||, < 2- Il + + (..(F)+ / (1g(1/))
vm

---

Lemma 4 is a standard bound from learning theory [Bousquet, 2002, Rakhlin et al., 2017] and is proved in Appendix C.7 for the sake of completeness. The second component is given by Lemma 13 in Appendix C.5, which amounts to a classical uniform deviations bound for the empirical process, ensuring that if n > 1, then T.p (J) R L(f) for all f F. The final step the following simple lemma, which ensures that if 1) is not too large, then [f( = (JERM))
Lemma 5. Let F= X + [-1.1] be bounded function class and let R ::F== F R be an arbitrary, possibly random, regularizer. Let FERM E argmin LD(f) and f E argminges LD(f)+ R(f). Then, LD(f) & (D(fERM) + sups. R(f) - R(f").
Lemma 5 is a simple computation proved in Appendix C.5. Letting R(f) be either 1) with (f) in Algorithm 2 or 17- Il in Algorithm demonstrates that if 1j is not too large, then f performs similarly fERM- To prove that Algorithms 2 and 3 produce good learning algorithms then, suffices to combine these three components, observing first that L(f) is close to optimal if n > and 17 is not too large, second that I| fll. & 1 if m > 1 and y is sufficently small, and third that IL( - L(JI & I| - All if vs is o-smooth with respect to μ and is X-Lipschitz in its first argument. Combining these results concludes the proofs of Theorems and 3. A detailed and rigorous argument for both proofs is presented
Appendix C. As final remark, we note that in the case of Algorithm 2, convexity of in the first argument is irrelevant to the privacy guarantee despite being necessary for learning. Indeed, for f returned by Line in Algorithm to be proven good learner, we apply Jensen's 's and the above argument that ensures that fy is good learner. Interestingly, on the other hand, convexity in is irrelevant to the learning guarantee of Algorithm while it is essential the privacy guarantee. Further understanding the role that such structural assumptions play in allowing privacy is an interesting direction for future work.
Acknowledgments and Disclosure of Funding
AB acknowledges support from the National Science Foundation Graduate Research Fellowship under Grant No. 112377 as well as the Simons Foundation and the National Science Foundation through awards DMS-203 183 and DMS-1953181. MB acknowledges support from the National Science Foundation through award NSF CNS-2046425 and from Sloan Research Fellowship. RD acknowledges support from the National Science Foundation through award NSF CNS-2046425 AS acknowledges support from the Apple AI+ML fellowship. AB also would like to thank Satyen Kale and Claudio Gentile for helpful discussions. Z.S.W. W. was in part supported by NSF Awards # #1763786 and #2339775.
References
Jacob D Abernethy, Young Hun Jung, Chansoo Lee, Audra McMillan, and Ambuj Tewari. Online learning via the differential privacy lens. Advances in Neural Information Processing Systems, 32, 2019.
Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies fi- nite littlestone dimension. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 852-860. ACM, 2019. doi: 10.1145/3313276:311331 URL https://doi. org/ 10. 1145/131112222 3316312.
Ehsan Amid, Arun Ganesh, Rajiv Mathews, Swaroop Ramaswamy, Shuang Song, Thomas Steinke, Vinith M Suriyakumar, Om Thakkar, and Abhradeep Thakurta. Public data-assisted mirror de- scent for private model training. In International Conference on Machine Learning, pages 517- 535. PMLR, 2022.
Maria-Florina F Balean and Vitaly Feldman. Statistical active learning algorithms. Advances in neural information processing systems, 26, 2013.
Peter L Bartlett, Philip M Long, and Robert C 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.
10

---

Raef Bassily, Om Thakkar, and Abhradeep Guha Thakurta. Model-agnostic private learning. Ad- vances in Neural Information Processing Systems, 31, 2018.
Raef Bassily, Shay Moran, and Noga Alon. Limits of private learning with access to public data. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: An- nual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8- 14, 2019, Vancouver, BC, Canada, pages 10342-10352, 2019. URL https:://ppooooooo /pppceeeeccc.s.... neurips. cc/paper/2019 http///hhh///e/ http:///aaaaaaaa..55777777777/20 -a0.:00000a.111--ttaatttta html.
Raef Bassily, Albert Cheu, Shay Moran, Aleksandar Nikolov, Jonathan R. Ullman, and Zhi- wei Steven Wu. Private query release assisted by public data. Proceedings of the 37th In- ternational Conference on Machine Learning. ICML 2020, 13-18 July 2020, Virtual Event, vol- ume 119 of Proceedings of Machine Learning Research, pages 695-703. PMLR, 2020a. URL http:////coeeeeeia./mmm mlr. mlr.press/va. press/vv19// httess//11//basslyy0000 batp//assslyla...... html.
Raef Bassily, Shay Moran, and Anupama Nandi. Learning from mixtures of private and public populations. Advances in Neural Information Processing Systems, 33:2947-2999 2957, 2020b.
Raef Bassily, Mehryar Mohri, and Ananda Theertha Suresh. Private domain adaptation from a public source. arXiv preprint arXiv:2208. 06135, 2022.
Raef Bassily, Mehryar Mohri, and Ananda Theertha Suresh. Principled approaches for private adap- tation from a public source. In International Conference on Artificial Intelligence and Statistics, pages 8405-8432. PMLR, 2023.
Amos Beimel, Kobbi Nissim, and Uri Stemmer. Learning privately with labeled and unlabeled ex- amples. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 461-477. SIAM, 2014.
Shai Ben-David, Alex Bie, Clément L Canonne, Gautam Kamath, and Vikrant Singhal. Private distribution learning with public data: The view from sample compression. arXiv preprint arXiv:2308. 06239, 2023.
Alex Bie, Gautam Kamath, and Vikrant Singhal. Private estimation with public data. Advances in Neural Information Processing Systems, 15:18653-18666, 2022.
Adam Block and Yury Polyanskiy. The sample complexity of approximate rejection sampling with applications to smoothed online learning. In Gergely Neu and Lorenzo Rosasco, ed- itors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceed- ings of Machine Learning Research, pages 228-273. PMLR, 12-15 Jul 2023. URL https: html.
// //proceedings.r mlr htt.a//.w.....eee/////////....
Adam Block and Max Simchowitz. Efficient and near-optimal smoothed online learning for gen- eralized linear functions. Advances in Neural Information Processing Systems, 35:7477-7489, 2022.
Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as easy statistical learning. In Conference on Learning Theory, pages 1716-1786 PMLR, 2022.
Adam Block, Max Simchowitz, and Alexander Rakhlin. Oracle-efficient smoothed online learn- ing for piecewise continuous decision making. In Gergely Neu and Lorenzo Rosasco, edi- tors. Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 1618-1665. PMLR, 12-15 Jul 2023a. URL https: // //proceedings. mlr, htt..peees//11//boocke/
html.
Adam Block, Max Simchowitz, and Russ Tedrake. Smoothed online learning for prediction in piece- wise affine systems. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2023b. URL https: /ttp:::////p/e//e/eeeee wtt./eettdddddaaaiidna (idet/ptDddd--11t700017111
Avrim Blum and Ronald Rivest. Training a 3-node neural network np-complete. Advances in neural information processing systems, 1, 1988.

---

Olivier Bousquet. Concentration inequalities and empirical processes theory applied to the analysis of learning algorithms. PhD thesis, École Polytechnique: Department of Applied Mathematics Paris, France, 2002.
Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learn- ing of threshold functions. In 2015 IEEE 56th Anmual Symposium on Foundations of Computer IEFE, 2015.
Science, pages
Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 389-402. IEEE, 2020.
Nicolo Cesa-Biance and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Nicolò Cesa-Bianchi, Tommaso R Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. Repeated bilateral trade against a smoothed adversary. In The Thirty Sixth Annual Conference on Learning Theory, pages 1095-1130. PMLR, 2023.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
Victor Chernozhukov, Denis Chetverikov, and Kengo Kato. Comparison and anti-concentration bounds for maxima of gaussian random vectors. Probability Theory and Related Fields, 162: 47-70, 2015.
Miroslav Dudík, Nika Haghtalab, Haipeng Luo, Robert E Schapire, Vasilis Syrgkanis, and Jen- nifer Wortman Vaughan. Oracle-efficient online learning and auction design. Journal of the ACM (JACM), 67(5):1-57, 2020.
Richard Mansfield Dudley. The speed of mean glivenko-cantelli convergence. The Annals of Math- ematical Statistics, 40(1):40-50, 1969.
Naveen Durvasula, Nika Haghtalab, and Manolis Zampetakis. Smoothed analysis of online non- parametric auctions. In Proceedings of the 24th ACM Conference on Economics and Computa- tion, pages 540-560, 2023.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise sensitiv- ity in private data analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography. Third Theory of Cryptography Conference, TCC 2006, New York. NY. USA, March 4-7, 2006, Proceed- ings, volume 3876 of Lecture Notes in Computer Science, pages 265-284. Springer, 2006. doi: 10. 10.1007/11681 16000//16818788 14. URL attpp:://dot http://doooooog///// org/10. 10000000011111770
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, 9(3-4)2211-077 2014.
Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pages 3199-3210, PMLR, 2020.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprini arXiv:21 /2. 13487, 2021.
Marco Gaboardi, Emilio Jesús Gallego Arias, Justin Hsu, Aaron Roth, and Zhiwei Steven Wu. Dual query: Practical private query release for high dimensional data. In International Conference on Machine Learning, pages 1 178. PMLR, 2014.
Badih Ghazi, Noah Golowich, Ravi Kumar, and Pasin Manurangsi. Sample-efficient proper pac learning with approximate differential privacy. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 183-196, 2021.
Aditya Golatkar, Alessandro Achille, Yu-Xiang Wang, Aaron Roth, Michael Kearns, and Stefano Soatto. Mixed differential privacy in computer vision.
In CVPR 2022, 2022.
URI. https: htops://www. amazon. www.oo..gcienc/ htt.:///cccccccee/eceeetttt..oo. mixed-die didd-dfffeeettilll Liffereentill-privacyy privacy- in- computer vision.
12

---

Sally A Goldman, Michael Kearns, and Robert E Schapire. Exact identification of read-once formulas using fixed points of amplification functions. SIAM Journal on Computing. 22(():705- 726, 1993.
Geoffrey Gordon. Regret bounds for prediction problems. In Proceedings of the twelfth annual conference on Computational learning theury, pages 29-40, 1999.
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis online and differ- entially private learning. Advances in Neural Information Processing Systems, 53:9203-9215, 2020.
Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang. Oracle-efficient online learning for smoothed adversaries. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 4072-4084. Curran Associates, Inc., 2022a. URL https: pttp://0222iie//000ff00000ll2l12 Paper hatp://pbebbpppppe--ooeeeeeeeeee
neurips cc/ pappparppprrr files/ pdf.
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis with adaptive adver saries. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 942-953. IEEE, 2022b.
Elad Hazan and Tomer Koren. The computational power of optimization in online learning. In Proceedings of the figth-eighth annual ACM symposium on Theory of Computing, pages 128- 141, 2016
Max Hopkins, Daniel M. Kane, Shachar Lovett, and Gaurav Mahajan. Realizable learning is all you need. TheoretiCS, 3, 2024.
Peter Kairouz, Monica Ribero Diaz, Keith Rush, and Abhradeep Thakurta. (Nearly) dimension independent private with adagrad rates via publicly estimated subspaces. In Conference Learning Theory, pages 2717-2746. PMLR, 2021.
Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291-307, 2005.
Jeankyung Kim and David Pollard. Cube root asymptotics. The Annals of Statistics, pages 191-219, 1990.
Alexander Kozachinskiy and Tomasz Steifer. Simple online learning with consistency oracle. arXiv preprint arXiv:2308. 08055, 2023.
Jean-François Le Gall. Brownian motion, martingales, and stochastic calculus. Springer, 2016.
Terrance Liu, Giuseppe Vietri, Thomas Steinke, Jonathan Ullman, and Steven Wu. Leveraging public data for practical private query release. In International Conference Machine Learning, pages 6968-6977. PMLR, 2021a.
Terrance Liu, Giuseppe Vietri, and Steven Wu. Iterative methods for private synthetic data: Unifying framework and new methods. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, viriual, pages 690-702, 2021 URL http:: httpp::/ h/proe/ee/ococceo/.eooo..o neurips iee. cc/
hataaa677555220667772224433333a3 www.e//tttteaaaaa...eaa.a. html.
Andrew Lowy, Zeman Li, Tianjian Huang, and Meisam Razaviyayn. Optimal differentially private learning with public data. arXiv preprint arXiv:2306. 15056, 2023.
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 94-103. IEEE Computer Society, 2007. doi: 10.1109/FOCS.200 41. URL httph: http::://dooooooo./o/// orgg10g01100 10. 1109/FOCS...../ 2007 .41.
Shahar Mendelson and Roman Vershynin. Entropy and the combinatorial dimension. Inventiones mathematicae, 152(1):37-55, 2003.
13

---

Zakaria Mhammedi, Adam Block, Dylan J Foster, and Alexander Rakhlin. Efficient model-free exploration in low-rank mdps. arXiv preprint wxXv:2337.03397, 2023a.
Zakaria Mhammedi, Dylan Foster, and Alexander Rakhlin. Representation learning with multi- step inverse kinematics: An efficient and optimal approach to rich-observation rl. arXiv preprint arXiv:2304.05889, 2023b.
Seth Neel, Aaron Roth, Giuseppe Vietri, and Zhiwei Steven Wu. Oracle efficient private non- convex optimization. In Proceedings of the 37th International Conference on Machine Learning, ICMI. 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 7243-7252. PMLR, 2020. URL http:/ / http:///oooeeeen....// mlr press/v119/ neel20a. html.
Seth V Neel, Aaron L Roth, and Zhiwei Steven Wu. How to use heuristics for differential privacy. In 2019 IEEE 60th Annual Symposium Foundations of Computer Science (FOCS), pages 72-93. IEEE, 2019.
Aleksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. In Proceedings of the forty-fisth annual ACM symposium on Theory of computing, pages 351-360, 2013.
Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Fr- lingsson. Scalable private learning with PATE. In 6th International Conference on Learning Rep- resentations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Pro- ceedings. OpenReview.net, 2018. URL attps://opp opwp//veeeeeeeeeeooeoee weteeewweeeeeeeeeeeee net/ httpe/oooommdddddioeeee
Yury Polyanskiy and Yihong Wu. Information Theory: From Coding to Learning. Cambridge University Press, 2022+.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Stochastic, constrained, and smoothed adversaries. Advances in neural information processing systems, 24, 2011.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning via sequential complex- ities. J. Mach. Learn. Res., 16(1):155-186, 2015.
Alexander Rakhlin, Karthik Sridharan, and Alexandre B Tsybakov. Empirical entropy, minimax regret and minimax risk. Bermoulli, pages 789-824, 2017.
Ralph Tyrell Rockafellar. Convex Analysis: Princeton university press, 2015.
Mark Rudelson and Roman Vershynin. Combinatories of random processes and sections of convex bodies. Annals of Mathematics, pages 603-648, 2006.
Daniel Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM), 51(3):385 463, 2004.
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. Ad- vances in neural information processing systems, 23, 2010.
Vasilis Syrgkanis, Akshay Krishnamurthy, and Robert Schapire. Efficient algorithms for adversarial contextual learning. In International Conference on Machine Learning, pages 2159-2168, PMLR, 2016.
Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134-112) 1984.
Ramon Van Handel. Probability in high dimension. Lecture Notes (Princeton University), 2014.
Giuseppe Vietri, Grace Tian, Mark Bun, Thomas Steinke, and Steven Wu. New oracle-efficient algorithms for private synthetic data release. In International Conference on Machine Learning, pages 9765-9774. PMLR, 2020.
Martin Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cam- bridge university press, 2019.
14

---

Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, al. Differentially private fine-tuning of language models. In International Conference on Learning Representations (ICLR), 2022.
Yingxue Zhou, Steven Wu, and Arindam Banerjee. Bypassing the ambient dimension: Private SGD with gradient subspace identification. In 9th International Conference Learning Rep- resentations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL https://openrevview net fortt//oumm?? www.oorummdddddmmmaaeeee d=7dpm1kBuJFC.
Contents
1 Introduction
1.1 Relatedd Work
2 Preliminaries
3 Algorithms for Differentially Private Learning
Analysis Techniques
4.1
Stability Analysis
8
4.2
Output Perturbation Analysis
4.3
Learning Guarantees and Concluding the Proof
A Differentially Private Classification
15
Privacy Analysis of Algorithm
16
A.2 Concluding the Proof of Theorem 4
17
B Gaussian Anti-Concentrattin and Proof of Lemma
17
Analysis of Algorithms and 3
21
C.I Stability of Algorithm 2 and Proof of Lemma
21
C,2 Stability of Algorithm 3 and Proof of Lemma
22
C33 Boosting Stability to Differential Privacy: Proofs from Section 4.2
23
C.4 Concluding the Proofs of Differential Privacy
24
C.5 PAC guarantees for Algorithms 2 and
25
C.6 Concluding Proofs of Theorems and
28
C.7 Proof of Lemma 12
29
Classification and Analysis of RRSPM
31
D.I Universal Identification Set based Algorithm
D.2 Privacy Analysis
31
D.3 Accuracy Analysis
35
A Differentially Private Classification
In the previous section, we presented a private algorithm for general, real-valued loss functions. Here, turn to the special case of classification, where provide algorithm with improved
15

---

rates. Formally, binary classification is a special case of Definition 2. where F: - {0, 1] and & the indicator loss.
Much like Algorithms 2 and 3, our approach to classification in Algorithm 4 relies on minimizing a perturbed empirical loss over F and projecting the output f onto the public data. Unlike in these earlier algorithms, which require further perturbation of the output in order to boost stability into differential privacy, in the special case of classification we are able to circumvent this second per- turbation and return any that agrees with on the public data. This is accomplished by carefully choosing the initial perturbation the ERM objective (see (4)) so that the predictions of on the public data satisfy differential privacy without ensuring some form of stability in norm. As a re- sult, our improved rates then follow from lack of a second perturbation. We present the following guarantee for our classification algorithm, whose pseudo-code can be found in Algorithm 4.
Algorithm 4: Rounded Report Separator Perturbed Minimum Algorithm (RRSPM)
Input ERM oracle ERM, dataset D = {(X,, Yi 1 1 i < n), hypothesis class F, smoothness parameter o, loss function é x y {0, 1}. arbitrary 2 E ARR)
Draw D = (Dz, Dy) where D3 = [Zi,.... Zm and D, = (Yi...., Pn such that Zi ~ μ
and Y2 ~ Uni( 1)), for all E [m]-
Draw weights = (E1, ...,.... Em) such that & Lap(2m/e).
Define L F - IR such that
C [.D.,(()==
Σ (U(x)),
Σ & (((())) 1=1
(4)
Get / ERM(F, L.) Output Perturb( -,2,7= 0.)
By running Algorithm
Theorem 4. Suppose that F X > >Y a function class of VC dimension d and E: y'y + {0. is the indicator loss. Suppose that Zi..... Zm ~ and fi...., ~ Lap(2m/2 are independent. Then there is a choice of m polynomial in the problem parameters such that if
n = oo log((
then the f returned by Algorithm is E-pure differentially private. vf is o-smooth with respect to μs, then f is an (o, 3)--earner with respect to Us and f. Furthermore, for some C > 0, if fi,..., , ~ N00, C /m log(1/8)/e) then there is a choice of m. polynomial in the problem parameters such that if
n = -ide "1g00
then the f returned by Algorithm 4 with Gaussian perturbations is (e, (e)ffefffrrentiillly private and is an (a, PPC learner with respect to any o-smooth V---
Remark 1. Note that the sample complexity we get in the above theorems is in the general, agnostic
setting. In the realizable setting, where some f* E F perfectly predicts the Y from the X, get sample complexity of e a log(B-1)) for E-pure differential privacy and e 22. 2.5 (1 (og()-1)) for ( diffferrentia privacy.
We emphasize that Theorem attains the improved ((a-5) sample complexity (even O(a-1 for approximate differential privacy)), which is significantly better than the O(a-14) from Theorem 2. While this is major improvement, it still falls short of the desired (a) statistical rates achiev- able by inefficient algorithms from [Bassily al., 2019]. We leave the interesting question of whether improved sample complexity is possible to future work. We now briefly sketch the proof of Theorem 4.
A.1 Privacy Analysis of Algorithm
While the privacy of Algorithms and proven in two steps, by first demonstrating stability and then leveraging the output perturbation ensure privacy, the privacy of Algorithm 4 is proven
16

---

directly. Our approach is motivated by techniques from Neel et al. [2019], which adapt the earlier notion of separator sets from Goldman al. [1993], Syrgkanis al. [2016], Dudik al. [2020] to the setting of differential privacy. Unlike those works, however, we do not require the strong assumption that has a small separator set and our results hold for general VC function classes. The main technical result that ensures privacy of Algorithm 4 demonstrates that the projection F to the public data set D, is private with respect to D, where we let Fla. [(((())) F}. We have the following privacy guarantee for f(Dx) Flp,:
Lemma 6. (Privacy over Projection) Let D'
D' be arbitrary datasets contaiming n points each. Let Dr be set of m points 71.... 7 E X. Let Vi,..., Yn E {0,1} be the of corresponding labels. Then for all measurable H [ Flo.
P(ERM(F), b., P., (g.,,) E HH) S < (g,Dr,) E H),
where E.DDD is defined as in (4).
With the above lemma in hand, the privacy of Algorithm 4 follows immediately from the post- processing property of differential privacy. We provide a full proof of Lemma 6 in Appendix D and now turn to the accuracy guarantee.
A.2 Concluding the Proof of Theorem 4
Proving that Algorithm 4 is (a, -e-aererer whenever Vr is o-smooth with respect μ is similar to the approach taken in Section 4.3, with the critical difference that in the absence of the second perturbation, we are able to achieve a stronger guarantee on the difference between f and f. Indeed, much as in the previous analysis, we observe that as m increases, the suboptimality of the inter- mediate f is driven up, while the difference between f and ff is driven down, thereby requiring a careful balance; here, however, do not also need to account for the balancing of the variance y We provide a full proof of the accuracy guarantee in Appendix D.
B Gaussian
and Proof of Lemma
In this section we present and prove more general version of Proposition 1. We begin by defining a Gaussian process and then state and prove the result. We then show how Proposition follows as an immediate corollary. To begin, we recall the formal definition of a Gaussian process.
Definition 7. Let T be an index set and m T + R be function. Let K TXT R be covariance kernel in the sense that for any 41, 41,..., In E T, the matrix positive semi-definite. We say that w. : T -> R is a Gaussian process with mean function m and covariance kernel K if for any f1,..., fn T, the random vector (w(t;)) is Gaussian with mean (m((4)) and covariance matrix (K (44,44)) We say that w is a centered Gaussian process m is identically zero.
is
Note that by Le Gall [2016, Theorem 1.11] such process always exists given m, K. Furthermore, we note that K induces a semi- semi-metric d on T by letting d(t, t¹)² E ((w(t = We now prove the following result, which is tighter version of Block et al. [2022, Lemma 33].
Theorem 5 (Gaussian Anti-concentratiinn) Let T be a set, m T + R be a mean function and K. : T x T + R be a covariance kernel (in the sense of being positive definite). Let d denote the metric induced by and suppose that m continuous with respect is separable and compact. Let w denote a Gaussian process on T with covariance K and for n) 0. let
and the metric space (T, d)
(t) = m(t + +t)
be an offset Gaussian process. We further suppose that w is taken to be a version with almost surely continuous paths i ++ w(t and that 0 < K (t,t) t) < 1 for all E T. Let
argmin (1t)) EET
17

---

and,
ksstt))
E(P,T) = there exists E T such that
I 1 - p² and 20((') +TJ.
K(t*, t*)
for P, > O. The following holds:
P(E(PTT)) S ppmp?
E
supw(() IET
(t.t)) is measure of how close and are to each other; indeed, in the special case where K = 1 this is precisely the correlation and thus and are more closely related the closer this quantity is to 1. Thus the event (p, 7) can be interpreted to mean that there exists some point s far from 1* (as governed by p) such that (ss) is almost minimal (as governed by 7); in other words, Theorem puts an upper bound on the probability that almost-minimizers of a Gaussian process lie far from the true minimizer. We now prove Theorem 5.
Note that (s,d)
Proof of Theorem 5. Note that by compactness of T and almost sure continuity of Ω minimizer of Q exists almost surely; furthermore, by [Kim and Pollard, 1990, Lemma 2.6]. t" is almost surely unique. As I" is separable and Ω has almost surely continuous sample paths, it suffices to replace T' with countable dense subset. We will hereafter suppose without loss of generality that T is countable. For each & E T, define the set
A(I) = E K(s,t) k(L,t) 2 31 p² and 2(s) S 2(1) + +7J.
It then suffices to lower bound the probability that A(t*) 0. We compute
P (IA(tt)] 0)
ΣE
(t
and [A(t) 0)
tET
((s) 2 y 7((()) -w){
Σ
Ey P t" and
inf ((s.))((1)))KK.)))
where the expectation is taken over the distribution of O(t). Now, fix t and let Gr,y denote the Gaussian process Ω conditioned on the event that 2?(1) = y. Let my, and 1/2 K, denote the mean and covariance processes of Pt.y- Critically, note that K, is independent of y and for all I, have
K(s,1)
ms,y(s) ms))
(y -(())-
ktt,t)
Define the functions
K(s,t)
a(s) p² k(t,t)
and
b(s) = $2 - a(s).
Now, note that if (s, (1 0²) K Ktt,t), then
[ K(s,t) k(t,t)
b(s) p²
2 3 p2-2
(5)
We also have that b(s) 0 for all by the fact that K(s,t) S (K(s,s) K(t,t) and K(s, V
K (1, 1) < 1. Furthermore, for all 8, it holds that
may+ 3, (8) = =m),y(s) + a(s).
(6)
18

---

Thus, for fixed t E T and y E I, we have
P c- = t and
inf
((8) 2 =v)
2 P t* === and
inf K(c.05((-p")K(()))
Q(s) - b(s) 2 (lQ(1) =
= P
t* = t and
inf ((,,)g(L-
2(8) - b(s) a(s) + a(s) 2 v/((()) = VV)
P
[* -= I and
inf (K)()) ((8) + a(s) 2 4 [
0 (2(1))
7
P
t' and
inf ((s) 2 y
[((t) y p²
2 P t and
inf K(,.05(1-p)K(1)))
((s) 2 y
7 [2(() y
where the first inequality follows from (5), the second equality follows from the construction, and the last equality follows from (6) and the fact that Kr is independent of y. Now, denote
(-(y-m(1) -())
qe (v) = (t, ()), exp
2n
the density of (t))) and note that we have
P ([AA(t)) = 0) =
Σ
(v))L t" = t and
inf k(e.0)=1-p²
{(s) 2 2 + = dy
tET
Σ
tt and
inf K(s.0))1pp
A(s) 2 y - [((() y /
-/ dy-
tET
We then compute
T (Q(t) = + T
t' = t and
inf K(s.))51-p²
((s) 2 4 + p2
02) dy
(8)
(v 1- = t. and
inf K(e.t)$1-p'
2((s) y/S(() y dy
+ (1(()) qe y p²
)
= and
inf 2(s) 2 v/s2(t) = dy. k(s.0)11-p²
where we added and subtracted the first term and then made the variable substitution y + fr + y for the latter integral. Note that
P
l- l and
inf k(xA)))-
0(s) 2 y/((()) - PP (C* = ([(((() = v)
as 2(s)= 2 r1t*) for all s E T by definition. Combining this observation with (7) and (8) yields
((A(t))) = N
(v) (t* = =t|(((t) = y) dy
tET
qc(v) - 91 y (²) ) IP (t =t(((t)) = v) dy.
EE
For the first term, we have
Σ ET
(( (t* = =t(((t)= = y) dy = Σ -t+==))==
ET
19

---

For the second term, using the fact that 1 - E" S x for all z, we have
(u-m(t)- )²
(y vy-min m(t) (1)
(v( - 90 11 ( 72)
= =ce(u)
1-exp
(1, (t,2 t)
(v- - m()))
S (6())
(t,)
(v)
(pz (v m(tt))
(T
$ 2n²²x²
Thus have
P(IA(E)) > 0) = P ([A(t))] -0)
00
(x())
(27 (y ((v-m(tt)) P( = +|s((t) = y) dy
1
(02
2rp2R2
1T
(y- ((())()))PP (12(11) = v) dy
1ET
E (2(1)) m(())
E
sup
S(t) si(() mlt)
1TR2
LIET
The result follows by noting that 1 w() 22(1 ml) for all 1 T.
We now prove a corollary of Theorem that will be useful the proof of Proposition and which makes the relationship between E(p,7) T) and the intuition of distance between t* and more explicit. Corollary 1. Suppose that we are in the situation of Theorem 5 with the additional conditions that T is subset of real vector space and that d(ss, t) / /K(s t,s t). Let m' ' R denote a mean function such that supier (m(() 'm' S t and let E2 denote the corresponding shifted Gaussian process. if argminger (1)),, then
TP (((t 1 (1)))>1) P)
8r
[Suppcco
E
pmn
lET
Proof. Note that
d(s, 1)2 K(s - 1,8 - = K(s, 8) K(l, - 2K(s, 1).
Let M = mmxxm((" ()), K(L', ((')) < 1 and note that the above implies:
d(tr, U(0,0'0 < 2M (1- K(t',, ,t') ,t*)
M
Thus,
K(t,,t"))
P ((((t,())) > 0) SP 2M 1
>D
M
K(r,t*
P?
IP
M
2
2
T
E
support)
2
02
LET
87
E
sup LET
0 0''nk22
20

---

where the last inequality follows by applying union bound and Theorem 5 to the Gaussian pro- cesses and Q2' after observing that
((+)))(())+=
and similarly for (2(1")..
We now ready prove Proposition 1 using Corollary 1.
Proof of Proposition 1. Let T = F, and observe that
a(s. K( - f'. =
R (w( w(') |s M'
The result then follows immediately by applying Corollary 1 the Gaussian process O2( m(f) - wff).
C Analysis of Algorithms 2 and 3
In this section provide the full proofs for Theorems 2 and 3, well more general state- ments under different measures of the complexity of the function class F. We begin the section by stating formal bounds the learning and differential privacy guarantees for each algorithm. In Appendix C.I. we prove Lemma I, which is a key technical lemma in the differential privacy guarantee of Algorithm 2: we then continue in Appendix C.2 by proving Lemma 2, which plays an analogous role except in the analysis of Algorithm 3. In Appendix C.3, we prove that algorithmic stability in II-Ilm, can be boosted differential privacy through Algorithm 1. In Appendix C.4 we combine the previous results to give guarantees on the differential privacy of Algorithm 2 and AI- gorithm 3. We continue in Appendix C.5 by applying more standard learning theoretic techniques to demonstrate that both algorithms are PAC learners before concluding the proofs of the main the- orems in Appendix C.6. Finally, for the sake of completeness, we prove norm comparison lemma in Appendix C.7 that was deferred from Appendix C.5 for the purpose of continuity.
C.1 Stability of Algorithm 2 and Proof of Lemma 1
We break the proof into two parts. First, we integrate the tail bound from Proposition I to get control on [ - filmm for any j E [J]. We then apply Jensen's 's inequality and a Chernoff bound to get high probability control on || f'll- We begin with the following lemma:
Lemma 7. Let fú be as in in Line of Algorithm and f/ is defined analogously with respect to D', a neighboring dataset to D. Then
E [115, -1
2
sup win (5) lEF
cn)
1/3
IE
(n n)) 13
where the expectation is with respect to c(,).
Proof. By boundedness of e, holds that [TD(J) - -T S for all ʃ f E.F. Thus, if f()) and Fay are as in the statement of the corollary, then I.D (J())) + n with (((a))) < Lo( n
(1) (F() + L. Plugging in = _ and applying Proposition yields
PP (115, -1 > >)) n2
8 E
sup wm (f)
feF
21

---

Now, we can integrate the tail bound to get for any Ç > 0.
x 5 {
E ||
2pP (1f - fl > p) dp
8
+
P.
mptr22
E
sup wm (f)
dp
feF
8
(
+ +
E
sup wml
.log
n(2x22)
SET
Minimizing over ( yields the result.
We now apply a Jensen's inequality and a Chernoff bound to get high probability control on fl.
Proof of Lemma 1. By Jensen's inequality and the definition of f. it holds that
J
P (1] - fl > >p)
=P =
Σ f,
83
>
P
j=1
2
1
P
Σ j=1
8
P3
>
p²
J Σ
S
P
|1
P11
p²
Finally, by Hoeffding's inequality [Wainwright, 2019, Van Handel, 2014] and Lemma 7, we have that
>BlIIi Filml + log (tt
8 820
P
Σ
f
J
j=l
} Σ 1 1
Fill
2
sup wm (1) FEF
(1))
1/3
log (1) J
2 P
E
(n 71) 13
The result follows.
C.2 Stability of Algorithm 3 and Proof of Lemma 2
In this section prove Lemma based on technique borrowed from online learning and the analysis of Follow the Regularized Leader (FTRL) [Gordon, 1999, Cesa-Bianchi and Lugosi, 2006).
Proof Lemma 2. Let be in (3) and L' be defined similarly but with replaced by D'. Note that || 11 strongly convex with respect II [Rockafellar, 2015]. Thus, by convexity of F. holds that
C(F) 2 ((F) + 7 -
On the other hand,
((F) -(F') -(F) C((')
< CC(++ ((0)+
=(() -AP) C'() C()
2 <c(() +
22

---

Combining this with the previous display and rearranging yields:
7) |1f MI I
Rearranging again proves the result.
C.3 Boosting Stability to Differential Privacy: Proofs from Section 4.2
In this section, we analyze Algorithm I and prove that if i' stable in Il-Ilm then applying the output
perturbation yields a differentially private algorithm for standard choices of perturbation distribution Q. We also show that Algorithm returns f close to the f with high probability. This first claim is implied by the following standard concentration bound.
Lemma 8. Suppose that Q NO, 1) and let f = Perturb(f, 2, Dz)) be as in Algorithm 1. Then with probability at least 1 3.
| 27 log
1
(9)
3
If Q = Lap(1), then with probability at least 1 - B,
1
f- - 2n log
vm.
(10)
3
Proof. By construction, it holds that
1 s $11ʃ
7..m = -.
1|5ll
By the triangle inequality, it holds that
1i < +7 Il5ll 2 ||5ll
Thus it suffices to bound ||<|| Bounds this quantity when NN 1) Lap(1) standard and can be found in, for example Wainwright [2019]. The result follows.
We now prove the main property of Algorithm 1, namely that it boosts stability to differential pri- vacy.
Lemma 9, Let Perturb be as in Algorithm and suppose that f. F. If = (Zi..... Zm } C X is arbitrary and Q = -N 1). then for any 6 >> 0 and any measurable G F,F it holds that
P [eetuurb[F, 2, D.) EG) S 27 (trr/05(1) -15-)) I11-
(enrturbFP,....000 EQ +
On the other hand, if Q Lap(1), then
(Perturb(F. F.auurbbF,,,,,... Da)) E g) s e
1 1I (Pettub(FF,0,,,10 E {
m3/2
Proof. To prove the first statement, let B3 denote the event that ||S|I.. S7 Voog (1) and let
1
puu)= = =2 exp
222
be the density of 7 Ç. Note that P (B3)) < by Lemma 8. We compute:
[Perturb(f. 2,,, D.)) E)) = uErm
TP (Perturb(J, 2,,, E egr C u) p(u)du
I [[Bs] -P (Perturb(f, 0,7, D.) Gly ( = u) p(u)du
"ER"
I [B P (Perturb(f. (f, G/y < 1) p(u)du
< 8
I [[ab] (Perturb(JJ E667 Ç u) p(u)du.
23

---

For the second term, we compute:
I [Ba) IP (Perturb(f, 2. D.) e 5 u) p(u)du
11 [Br]] F [Perturb(f',,,,, E gr s- = = f) p(u)du
MERR
II [B&g] P (Perturb((.2nn,,D) E gh Ç (= p(u) - -.x (1u- -1u- 11 du
JUER"
/ mM
[[38]] P (Perturb(f' 2,,,) gh ( = u) p(u) E (1+11all
du
/ TI [BBs) P (Perturb[",, gh 5 = 1) p(u) . कラ (1+3)//oR(+)) 115-51 du
L log ||5- P Perturb(f"' 2, 7, D2) E EG
The first claim follows. To prove the second claim, we may repeat the same argument with Q Lap(1) and 8 Indeed, observe that
q(u)= 7 mm 1
then
g(u + P'
< -1la 3/2 11
quu)
where the second inequality follows from Cauchy-Schwarc Plugging this ratio into the above argu- ment yields the second claim.
C.4 Concluding the Prool's of Differential Privacy
In this section, we combine the results from Appendix C.3 with the stability results from Ap- pendix C.6 prove the differential privacy guarantees of Algorithm and Algorithm 3. We separate this section into two lemmas, each corresponding to one of the algorithms. We begin with the more general result. Note that this lemma does not quite follow immediately from combining the stability guarantee with the results of Appendix C.3 as we wish to assume uniform lower bound on lf whereas Lemma requires a uniform lower bound on I|. We apply result from Appendix C.5 below to reconcile this discrepancy.
[-1, is a function class and let μ ((X) such that |[ 2 3 for all J E F. Suppose further that is bounded in [0, 1). Let 8 > 0 and suppose that m, T, and J are such that
Lemma 10 (Differential Privacy Guarantee for Algorithm 2). Suppose that X
m
1 1
log (
)2)
(
(n-
1/3
4
E
sup Wm (5) JEF
+
log ( J
S
and
log (m)( Vm
log log(m) + log (3)
1
C
(F) +
<
6
Then Algorithm 2 is (e, difffeerrntl private for Q = A 1).
Proof. The result follows immediately by combining Lemmas and 9 assuming we have lower bound on k. Indeed, by Lemma 12, it holds with probability at least - 5 that inf || fll 2 i The result follows.
We also have a guarantee for the more specialized algorithm.
24

---

The previous sections have shown that Algorithms 2 and differentially private, which comprises the main difficulty of our analysis. Here we apply standard learning theoretic techniques to show that if is o-smooth with respect to μs, then the algorithms are also PAC learners with respect to Lemma 11 (Differential Privacy Guarantee for Algorithm 3), Suppose that F. X - [-1,1] is convex function class and suppose that is convex and X-Lipschitz in its first argument. If 8 >> 0 and m, ? are such that
(3))
2
2
1 1
log
E, n
27²
V
then Algorithm run with Q = =N(00,1) is (c, difffereenti private. On the other hand, if and
3/2
2
S
E,
Y
V
then Algorithm run with Q Lap(1) is e-purely differentially private.
Proof. This follows immediately by combining Lemmas 2 and 9.
These results show that for any choice of v, Algorithms 2 and are differentially private. In the next section show that if is a-smooth with respect μr, then the algorithms also PAC learners with respect to v.
C.5
PAC guarantees for Algorithms 2 and
v. This proof rests on three main results: first, we recall a norm comparison guarantee in high probability that allows us to relate ||-I1,r Il-II second, we recall a classical uniform deviations bound for empirical processes; and third, we show that the perturbed empirical minimizer / has similar loss to the empirical minimizer fERM of loss function as long as the perturbation large. Combining all three results will result in a PAC learning guarantee for Algorithms 2 and 3.
too
We begin with the following lemma, which is fairly standard result in learning theory. To state the lemma, we recall from Definition 6 that the worst-case Gaussian complexity defined as
(m(
sup Zi.....um
E
sup wi ( fET
We then have the following control on |1-11p in terms of I1-IImi
Lemma 12. Suppose that F X - [-1, 1] a function class and let μ E A(X) with Zi...., Zm ~ P independent. Then for any B > 0, it holds with probability at least 1 B that for all f F.
log"(m)
log log(m) log
|/ - -l, 22 11'l +C
(F) + Vm
m
Because the proof is relatively standard [Bousquet, 2002, Rakhlin al., 2017], but also technical digression, we defer it to Appendix C.7 and continue with our arguments.
Our second lemma is standard uniform deviation bound for empirical processes:
Lemma 13. Let F X + [-1,1] be bounded function class and les 'D denote data set of (X,, Y.) be independent. Then for any > O, with probability least B, holds that
2og
sup JEF
LD(f) =(f) Vn
E
sup wn(
+
FEF
25

---

Proof. This follows immediately from combining Wainwright [2019, Theorem 10] with Van Han- del [2014, Lemma 7.4].
Finally, we show that the perturbed empirical minimizer f has similar loss to the empirical minimizer JERM loss function as long as the perturbation is not too large.
Lemma 14. Let F X - [-1,]] denote a function class and let é: [-1,1]x + [0. 1] denote
bounded loss function convex in the first argument and let DD denote dataset of size n. For > 0, let be in Line of Algorithm 2. Then for any B O, with probability at least B.
log
1 5 log
L() inf L() S FEF
12 Vn
E
sup win (1) + SEF
+ 2n
E
sup
m (
(1)
+
FET
(11)
If instead we let f be as in Line 3 of Algorithu 3, then almost surely.
log
1
L(F) inf L(f) S 12.28 E FEF
sup (n( |EF
+ 2
17.
(12)
Proof. Applying Lemma and noting that f. fERM E and applying Lemma 13 yields
2 log
12 Vn
L(f) inf L(f) S fEF
sup (n + sEt
+ sup f.EET
R(f) R(f").
n
The second statement follows immediately by noting that Il for all f E and letting R(f) [l
For the first statement, we note that by convexity of f, it holds that
Lo(f)s } Σ ( s (D(FERM) + ? > sup w ( inf (f) inequal-
j=1 JEF
feFF
To prove the second statement, we observe that by the Tinell--Tiielsoo--brrinnooo ity (see, e.g., Wainwright [2019, Example 2.30J) and the fact that E that for all j E [J]. with probability at least 1 9, it holds that
(i) wm (nr < for all f F,
(2)
sup ( <
())
E
sup w (f)
2 log
JEF
/EF
Applying symmetry and Chernoff bound tells us that with probability at least - 3 it holds that
log 1
1
Σ sup (f) inf
wit 2
sup w 1 (f) +2 / FEF
J
FEF
JEF
The result follows.
Before continuing, we prove Lemma from Section 4:
Proof of Lemma 5. For an arbitrary regularizer R : FF + R, if we let e argmin LD(f) + R(J), then by definition LD( + R()) S LD(JERM) + R(JERM) and
L & (D(JERM) + sup R() R(f'),
S.EE
where fERM E argmin LD(f) is the ERM.
26

---

Combining these three lemmas yields the following PAC learning guarantee for Algorithm 2.
Lemma 15 (PAC Learning Guarantee for Algorithm 2). Suppose that X x x-I, [-,11]ar is a function class and & : 1-1, -111] 1],1|x + [0.1] is bounded loss function X-Lipschitz and convex in the first argument. Let je ( and suppose that v a-smooth with respect to p.. For any B > 0 holds with probability at least B that
log 3
12
L(f) inf L(f) - fet
E
sup wn (f)
+ 2.
\
vn
lEF
log (2]
4Ay
1
+ 211
E
sup |EF
(1)
+
+
log
m
J
B
log log(m) log (1)
CA
log2(m)
+
(m)
mm
for f returned by Algorithm 2 with N0, and D a dataset of size n.
Proof. We compute:
= -1
< 2
3-
where the first inequality uses Jensen's 's and the second usesthe fact that is o-smooth. We now observe that by Lemma 8, with probability at least 1 3,
| -
S 27 | log 3
Combining this with Lemma 14 yields
log (1)
log #
12
I(F)
inf I(f) JEF
S
sup (f)
+ \
+ 2n
sup (F) SEt
Vn
lEt
n
4xr
f ] - 1155-111 -
=11m)
log
Applying Lemma 12 concludes the result.
Similarly, we have a result for Algorithm 3; note that while convexity of f required to demonstrate that Algorithm 2 is PAC learner, although is irrelevant to the privacy guarantee in Lemma 10, the situation for Algorithm 3 is reversed in that convexity is not required to demonstrate that Algorithm PAC learner while it is necessary for the privacy guarantee in Lemma 11.
Lemma (PAC Guarantees for Algorithm 3). Suppose that F X + [-1, is a convex function class and []1, [0 is a bounded loss function X-Lipschitz in the first argument. Let E A (X') and suppose that u is a-smooth with respect to μ. For any 3 >> 0 it holds with probability at least B that
log (
12
4hy
L(F)
inf L(f) <
E
sup wn, (f)
+ |
17
/
logg
FEF
Vn
JEF
n
log log(m) ) + log (1)
CA
log (m)
I (F)
σ
mm
m
27

---

for f returned by Algorithm 3 with Q (N 1) and D a dataset of size n. Similarly, if we replace Q Lap(1), then with probability least 3.
12 vi
log 3 4)y 1 +
log (b) vm
I(f)
inf L(f) FEF
E
sup (apwi(f) (f) leF
+
n
o
CA +
log2(m) m
log log(m)
- -log
(3)
σ
m
Proof. The proof the first statement is identical to that of Lemma 15 with the exception re- placing (1 by (12) in the invocation of Lemma 14. The second statement is also identical but now replacing (9) by (10) when applying Lemma 8.
With these results in hand, along with those from Appendix C.4, all that remains conclude the proofs of the main theorems is to tune the hyperparameters and control the complexity terms. We do this in the next section.
C.6 Concluding the Proofs of Theorems 2 and 3
In this section, we combine the results from Appendices C.4 and C.5 to prove the main theorems. The main theorems in the text, Theorems 2 and 3, follow immediately from the following two results. We begin by stating more detailed version of Theorem 2:
Theorem 6. Suppose that F X [-1, is function class such that Gm(F) - (Va) for
some d E N and f: [-1,1]x2 > [0, 1] is convex and X-Lipschitz in the first argumens. If we let Q = (0, in Algorithm and set
d V log (b) X2
7
v VIoB log (5)
σa
7 = O
a Vd
m H
0²a²
A
dog (1)
dd log"
1
log (+)
d 1
log" (t)
3
J == á
a²
08
and
g log
(1)
do 1og 1/2
(1)
(3) log 3/2 3/g (1)
n Ω
allg3al1
then Algorithm is (e, d)difefrrettillly private and an (a, PPC learner with respect to any v that is o-smooth with respect to μ.
Proof. This follows by combining Lemma 10 with Lemma 15 and plugging in the parameter choices.
We also have a result for Algorithm
Theorem 7. Suppose that F : X [-1, is convex function class such that (F) = 0 for some d e N and f: 1_1, [0, 1] is convex and X-Lipschitz in the first argument. If we let Q N0, 1) in Algorithm and set
d Vog
7 =
σa
" = ((a),
m = θ
o2a²
log
28

---

and
log 5
B, holds that for X dodoog 3/2
(3) log 1/2 (1)
5
then Algorithm 3 is (e, -)diffferettially private and an (ox, B)-PAC learner with respect to any v that a-smooth with respect to μ..
On the other hand, if we set = Lap(1) 1) Algorithm and set
dv log 3 o²a²
a²o
y == θ
7 =)(a,, m= m=
)2
12
d log
A log (1)
and
E
2 @sea
( (ovi
(t)
5/2
5/2
then Algorithum 3 is e-purely differentially private and an (a, P)-PAC learner with respect to any a-smooth V.
Proof. This follows immediately by combining Lemma 11 with Lemma 16 and plugging in the parameter choices, with the pure differential privacy guarantees coming from the second halves of each lemma.
L
As a final remark, we note that Lemmas and 16 are both phrased entirely terms of 9 (F) and thus apply to function classes such that 9., (J) w(1). Such non-donsker (Wainwright, 2019, Van Handel, 2014] classes can still be learned in the PAC framework, albeit with slower rates. Indeed, it immediate from the above results that as long as 9., (F) = of (mmm), then appropriately tuning the hyperparamters results Algorithms and being differentially private PAC learners with respect to v. It is well-known that (with our scaling) (F) o is necessary condition for PAC learnability even absent a privacy condition (Wainwright, 2019, Van Handel, 2014] and thus our results qualitatively demonstrate that private learnability with public data is possible whenever non-private learning is possible.
C.7 Proof of Lemma 12
and noting that the uniform bound only increases by factor of and the Rademacher complexity increases most by factor of 2, we observe that suffices to prove the result for f' 0. We thus instead prove the notationally simpler claim that with probability at least B, for all fEJ.
Replacing F F - --===U
log"(m) mm
log log(mm) + log (8b
|| 2 |1 +C
m
We first note that by Bousquet [2002, Theorem 6.1], with probability at least all F.
log
+ log log(m)
| < 2- 11 +
200
p2
+
3
(13)
for some universal constant C, with
1 m
,2
r S inf
r > F
sup
E.f Z2)22
$
(14)
JEF
m
LI
29

---

Taking square roots on both sides of (13) shows that it suffices to upper bound 7. For the remainder of the proof, we do this.
In order to proceed, we recall the following standard definition of covering numbers.
Definition 8. Let F be function class and |1-Ilm.c the the - norm on the empirical measure on max]e[m] (f()) We say that f1...., IN is 8-cover with
......, 7m X, i.e., II ml respect to ml-llm.o for all f F there is some fy such that Il fy mm I E. We then let Nm. (F, denote the size of the smallest E-cover of with respect to Il-llm,,o
e-cover
The notion of cover is standard throughout learning theory and can be used to control the Rademacher and Gaussian complexities [Dudley, 1969, Van Handel, 2014, Wainwright, 2019]. We will use it to control r.
Proceeding with the proof, let,N (F, u) denote the covering number of the function class F with respect to |I-Il at scale u > 0. We then claim that 7 can be upper bounded by any satisfying
50
[
vm J1/16
Vlo Nm, oo (F, ujdu S r.
(15)
We also claim that for any Fm (F). the following holds:
[
(
cm log
r/16 V Jog.Nm.o. u)du S C CVlog(m)-
du
9m
(16)
for some universal constant C. We now suppose that (15) and (16) hold and set r Cm-1/2 log((m)- (F). Then it is immediate that r is member of the set in (14).
We now prove the two claims.
Proof that a solution to (15) is an upper bound on r. [Van Handel, 2014, Wainwright, 2019], it holds that
By a standard Dudley Chaining argument
1 m
12 m
S. Vog of {l1fIRm 5T²] waddu
Eg
sup fEF LIISE ZT2
Σ (z(()))
I inf us0
4u +
(17)
Letting fu....,fM fM Fn [1fl I r²2 be proper u-cover of Fn [11f12 $T²
with respect
to |l at scale S and F + (Ji) be projection to the cover, we have
|| = 3² || +() < 4s2,22 + T (f)). In particular,
by factoring T()² (J +s))(
[1 S x²) 2ur) s Nm, (F { {ISI < {(²]]] u) S No, u), 2F²
where we used the fact that a proper covering at scale has size bounded by a covering scale e/2 by the triangle inequaltiy. Substituting into (17) and rescaling yields the claim.
Proof that (16) holds. This proof goes through fat shattering numbers, complexity measure taking a function class and a scale u > and returns fat(F, u) E N [Bartlett et al., 1994]. We do need the full definition of fat shattering numbers and defer [Bartlett al., 1994, Srebro al., 2010, Rudelson and Vershynin, 2006] for details. We only need the following two properties. First, for any 0, it holds by Rudelson and Vershynin [2006] that
log Nm. (F, u) S C fat(F, cu) llo(m)) llog fat(F,
m
(18)
Second, by Srebro et [2010, Lemma A.2], for all m 1/2 J. (F).
, fat(F,r) r) S 4 (F)
(19)
Plugging (18) into the left hand side of (16) and then applying (19) concludes the proof of the claim.
30

---

D Classification and Analysis of RRSPM
In this section, we provide full proofs for the guarantees of Algorithm 4. Scction D.I, we describe the concept of universal identification sets and the result of Neel et al. [2019] which plays a crucial role the privacy analysis our algorithm. the technical lemma used for the proof of differential privacy based on Neel et al. [2019]. We then continue Section D.3 by applying standard learning theoretic techniques to demonstrate that our algorithm is an accurate classifier.
Section D.2, we formally prove Lemma 6 which is
D.1 Universal Identification Set based Algorithm
In this section, we formally define universal identification sets and informally describe the algo- rithm used in Neel et al. [2019]. Intuitively, a universal identification set captures the combinatorial property of function class that all distinct functions in the function class disagree on at least one point from the data universe. For many natural classes, the size of the universal identification set is proportional to the VC dimension of the function class.
We now describe the algorithm from Neel et al. [2019] and explain the usefulness of universal identification sets. First, we formally define the notion of universal identification set.
Definition 9. (Universal Identification Set) A set U S X is universal identification set for hypothesis class for all pairs of functions f in the hypothesis class F, there is a E 2 such that:
f(x) + (z)
Additionally, if [4] m, we say that has universal identification set of size m.
Assuming the existence of universal identification set for the function class F of size m denoted by [UI...., |m Neel et al. [2019] showed that the following algorithm(called RSPM) an E- pure differentially private and (a, (3 -cccurate algorithm.
Algorithm 5: RSPM
Input ERM oracle ERM, dataset D {(x,, Y,) S i S n). hypothesis class F, universal identification set l (UI.... Um }, loss function L y x y + 1}.
2: Draw weights { = (fi..... ... Em] such that &, Lap(2m/e)
3: Draw labels y (Vi...., Ym) such that V, (ni 1)).
4: Define LEDD. F + IR such that
LE.D = Σ (U(()). & (U(U)),
1=
5: Get f ERM(F, Lg.D.).
RSPM roughly simulates Noiport-ooisyMMinnDDD that minimizes a perturbed estimate, where the perturbation is sampled from Laplace distribution. straight forward implementation of "Report-Nossy-iin to minimize over all perturbed estimates of functions, it'd have to check for all functions in F and thus the computational complexity would depend on the size of F. RSPM avoids this problem by implicitly perturbing the function evalu- ations via augmented dataset. The proof of privacy thus exploits the structure of the universal identification set.
et al. [2014]) attempting to output a function
Although many natural function classes have bounded universal identification sets, their existence is not as general as having bounded VC dimension. In our work, we only assume finite VC dimension of the function class.
D.2 Privacy Analysis
In this section, we prove that Algorithm 4 is differentially private. A notion that we will need is that of projection of hypothesis class onto set of points from the domain.
31

---

Definition 10. (Projection) Given a hypothesis class F - feature space X, we define the projection of JF onto Z to be F z ((f(z))...... f(mm) F).
y and a subset Z = {zI.... 2m of the
In the following sections, we will interchangeably think of the projection of hypothesis class onto a set of points as a set of functions on Z or as a set of vectors y)
By construction, Flz has the property that any two distinct functions + S' E FFlz must disagree on at least one point z E Z. We encapsulate this as the following lemma.
Lemma 17. Let F be a hypothesis class and let Z {......; 2m) be a of points in the instance space X. Then, for all f f E F 2, there exists z E Z such that f(z) + f2)..
the notion of universal identification set considered in Neel et al. [2019]. In particular, the above lemma can be seen as the statement that the set Z is a universal identification set for the class Flz.
Remark 2. This property is analogous
We first provide an informal sketch of the proof of privacy. In the later sections, we formalize these ideas. Let E F be any arbitrary function and let D, D' be any pair of neighbouring datasets. We show that ((RRSPM(D) = f) S <fP(RRSMM(D)) jection, there is some f Fl.. that is consistent with the labelling of the selected function f- P(ERM(F, ((E.M(F.Cg.D.D) = f) I eFP(ERM(FF pust-processing property of differential privacy.
f). By the definition of the pro-
= since privacy for f follows from the
We now provide with proof sketch for the main technical lemma showing that the privacy is pre- served over the projected function class. Optimizing a loss function perturbed by Laplace-weighted examples implicitly tries implement "Report-Noisy-Min" algorithm outputting function that minimizes a perturbed estimate. For any neighbouring datasets D and D', the evaluation of any function f can differ by at most 1. We show that the set of public points is a universal identifica- tion set for the set of functions projected onto D and leverage this to prove that whenever the shift in the noise vectors is bounded by 2 in every coordinate, then f is the minimizing function when switching from D D'. This intuition is made precise in Lemma 18.
Lemma 18. Let D'D' be two neighbouring data sets, and let D (D,,D,) E (X x {o. 13)m where D=r {Z1,..., 7,m} and Dy (Y,..., Ynn. Define E(G. D,D) =
{5: ERM(F) f..D,)) [s8]. where fgDD. is a functional as defined below:
n C CgDD,b(f== Σ e(f(x)) + Σ & ((f(Z)))
Let E = (61,.... .mm} such that & ~ Lap(2m/s). Given a fixed fö E F..., define mapping
V 1. (E) Rm + R.m on noise vectors as follows:
1. (//(U((()))))) 1, / /b(()) (E); E. 2
2. (f((ff(Z)), 8,) = 0, 0, (1(s() (E); = E, +2
Equivalently, 1 (E); & + 2(1 - 2e(fo(Z)), Let g E (fo: where fo
(R, Then v 1 (E) E Elfb, D',D).
Proof. Let (iz(E) E' -h S.m. Our goal is show that for every E Flö, such that f # fō. we have (g) C..r) First, recall that by our assumption for all E Flo, we have
(.D, > ((pb))
(20)
32

---

We now argue that c D' (o,,o()) -- E, (f is strictly positive for all f E FlB. such that fo + f. To see this we calculate,
m
Cg)Dr,(()) Lg.
E (((X))))+
Σ
E ((f(Z)))
(X-))D
E (F(()))))
Σ
& (((f(2)))))))
(XYY)D
m
2 E.D.D(f) 1+ Σ
4 ((f(())) Yi) - E ((((2)))
-E - - Σ & ((f((z)))))))))))))))))))(())))) Y)) (....(/(Z.))..... Y.)
i=1
> 22 Σ (4) - Ei)
where the second inequality follows from the fact that DD and D' differ in only one entry and E is 1 sensitive. The last equation follows from statement 20.
We know from Lemma 17 that there exists Z E D such that f(Z) * fz(Z). Recall that E + 2(1 (Z())(Z)), Y.). By construction, each term is non-negative. Therefore,
(Ef E.)
2.
To wrap up, bound
Le,D) - C (e,o) 0.
This proves that v i (E) E D'
Lemma 19 (Laplace shift). Let E= (.i,..., such that & Lap(2m/e). Fix some noise realization I and fix hypothesis in the projection set f Flo. Then,
IP(E = r) S P (x)),,
where V (E(E); -:: 2(1 -((((2)) Y.)) defined in Lemma 18.
Proof. Let E [m] be any index and let R Since ~ Lap(2m/e), we know
|rile
P(E: = rr) =
exp
4m
2m
For any t E R such that It - t'l < 2. we get
P(C, = t') S exp(E/m)P(GG t)
Since for all E [d]. (r); - rıl < 2, we get
P = 1/ (r))
P = (r(r)))
<
exp(e/mmg = exp(s).
PC = r)
PPE rT)
1=1
33

---

Our proof of privacy also makes use of the following lemma, which says that minimizers are unique with probability [Neel al., 2019, Lemma 4].
Lemma 20. Let D (D Dy) (X {0, 13)m Consider Flo., where Fld, the projection of F on Dr.. For every dataset D, there is subset B S IRm such that:
(P E B) and
On the restricted domain RT arg fingsls,, f.p.b(().
B, there is a unique minimizer
Using standard results about Laplace perturbations stated in Lemma 19 and Lemma 20 and using the perturbation coupling bound Lemma 18, we get the our formal statement of privacy for optimizing over the projected function class as follows:
Lemma 21. (Privacy over Projection) Let D, be arbitrary datasets containing n points each.
Let D = (D., D2)= E (X x {0, m. Then,
P(ERM(Fl6,
f) (FP(ER((F).. C. f).
Proof. We caleulate,
P(ERM(FI, D., Lg.D.D) = -(,E),
P(E)1(E E(f,D,D)
P(E) E D,
B has 0 measure by Lemma 20
RTAB /
P(E) E(J,D',D))
Lemma 18
RBAB
C'P( (5) E E(f,D', D(f,D',D)cck D))
Lemma 19
RTAB
0v de
(F(ELLEE E E(f,D', ('F,D',D)) DD) O
Change of variables & + V (E)
(
NVV
( E(f, (',))D
L has measure,
0
EE E(F, @FP(ERM(F) (F,, f).
Theorem 8. Algorithm 4 is e-pure differentially private.
Proof. Let D and D' be any neighbouring datasets. Fix any function f F. We show that P(RRSPM(D) = f) < ((RRSPM((D) f),
where the probability is taken over the randomness of the algorithm. From the definition of the projection, we know that there exists unique function in the projection say, f Fl... such that f(z.) f(Z,) for all i [m]. Using Lemma 21, we know that
P(ERM( b., f...))))))= = (PEMM F...D. f).
As defined in the algorithm, let ž(f)= (Z,) f(z)). From the definition of Ž, it follows that f E arg min Z(F). Following the posi-processing guarantee of differential privacy, it is easy to feF
that
34

---

P(RRSPM(D) Î) S <T((RSSPM()) f..
D.3 Accuracy Analysis
In this section we analyze the accuracy of our algorithm. Let f denote the function in the hypothesis
class that minimizes the loss with respect to the distribution v i.e. f E arg mrgg Let denote
fer
the output hypothesis of our algorithm. We show that the loss of f is close to f with respect to the data generating distribution v.
As in the algorithm description, let f be the function that minimizes the perturbed loss. Our algo- rithm outputs whose labelling consistent with f on the public dataset Dz. Since D is sampled from the base distribution, follows from VC theorem that f and f are close under the base distri- bution Js. We show in Lemma 22 that f and f are close under v by leveraging that v2 a-smooth distribution. Using standard results about Laplace perturbations, we show that f close f in Lemma 23, where f" is the empirical risk minimizer over D. Using the VC theorem, it is easy to see that f' is close to f* and consequently using the triangle inequality we finish the proof by showing that f and f are close under 1/.
We now state the VC theorem below which we use in our analysis.
Theorem 9. Let DD = {(X1, Vi),..., (X,,, Yn)} where for all i E [n], Y) E X x {0. 1) sampled from fixed distribution Let LD(f) = 1 Ki f(X)) Yi)l and let (f) Exx,y)=ol[(f(X) # Y). If the function class FF has VC dimension d then,
(V (d+1og(11)) log(118) (
)
P
sup fer
LD(f) -o))
2 21-B.
In particular if f E mig [s) then,
fEF
(V
d + log (1/3)
P
Lx(f))
arg L. (f)
21-8.
fEF
m
Lemma 22. Let Ug be a a--mmooth distribution that is fined in Desintion 2. Let f be the hypothesis returned by algorithm and let j E ERM(FF f..D.5) Then,
dur dy
< 4. Let Lu be the loss function as de-
mul) - $0 (vat
log(1/3)
mo²
with probability B.
Proof. Let a'' =0 =0
d++loR(1/B) m
First we show that
L(J) L(Ā) I 2a' with probability
X~H
X~p
x=f(x)
y=f(x)
least B. Consider dataset ò ((X), ((X)), output f. Using Theorem 9 we know that,
(Xm; f(Xm)) we minimize over and
P L(f) - L(F) 2 + (Lo(f) - - 21-B
X~u
XNu
Y=f(X)
x=(()
Since T(() 0 and |T-(s) T.D(f)) = 0 and we get that with probability at least 1 - B
X~p
y=f(X)
35

---

Px-u(f(x) # f(z)) - 2a'. now show that Px-u, (f(x) + f(x)) S 20 /a with probability at least 3.
(21)
Px~u, (f(x) # f(x))
Ex v 1 (f(x)) # f(x))
Σ
P(u. = (f(x)(()) + f(x))
XEx
1
Σ P(u= x))(f(x) + f(x))
Since
duz dp
S
Xex
1
[xx ((((f(z) # [(w)))
(Px=u(f(x) + f(x)))
2a
Using Eq 21
Having shown that with probability at least - 3,
Px (f(x) + f(x)) s 20' 20'/a,
(22)
prove that with probability least 1 - 3,
L(f)
L(f) 1 20' 20'/o.
X-Mx y You,Ix
X~ve You,ix
which is equivalent to the theorem statement. Using the triangle inequality we get
L(f) - L(f) IS Ex (F(x, + + - PY xx (f(X) +r) Y yoaoli
=(xx) 22
where the second equation follows from the observation that for any value of X, if f(X) f(x) then the difference of the probabilities equate to 0 and if f(X) * f(X) then the difference of the probabilities equate to and the last equation follows from Equation 22.
Substituting the value of a' proves that with probability 3,
(vat
d ud+logih log(1/3) mo²
-
Lemma 23. Let F. be a function class with VC dimension Let (X),, (Xn, Y2) and DT = {Zi...., Zmn where Ze ~ p. Let Lp be the loss function as defined Definion Let f' E ERM([F,F Lp) and let ERM(F, (F, then,
4m log(m/33
Lo(f) Lp(f)<
EN
with probability 1 B.
Proof. Following the algorithm we know that for all i E [m], ~ Lap(2m/s). Using Chernoff's bound and union bound we get that with probability B.
2m log(m/3)
Vi E [m).16/l= <
36

---

Since f(Z.) E {0,1) for all Z, E D, with probability 1- 3, (.D,D(f)= 2 Cx(f) m 2m log(m// (m/3)
Similarly, (f) - LD(f) + m 2m log(m/8)
Dividing by and combining the bounds we
get,
4m log(m/3))
Lo(f) -D()))) 2 EY1
with probability 1 1-3.
Theorem 10. Let be as defined in Algorithm with D sampled from some distribution v such that duz dy
$ o. Suppose the function class has VC-dimension d then setting
m = m -0(1 (0( log(1/3)
yields an 8- pure differentially private (or, B)-learner as long as
d (og((1/))
2 Ω
where Et hides log factors.
Proof. Let v be the distribution from which the given dataset 'D is sampled where be the output of our algorithm, f' E arg minC f be the target function from our function JEF
dv. du
1 Let
class F and E arg mrgminn We wish to compare the guarantee of the function f with
JEF
respect to the function f with respect to the distribution i.e. [L, - ()()
In our analysis below, we break the loss function several times using triangle inequality and bound each term using previously stated results via a union bound.
(L,(f) - (f))l (f) Lo(f) + (L,(F) LD(f) ( LD(f')+ (D+ -
d ++ log(1/3)
d (va+ttg log(1/3)
m (og(m/3)
d log 1/3)
+0
+0
pm
n
en
n
Lemmna
Thearem
Lemma
Theorem
=0
d log(1/3)
d log(1/3)
m² log(m//3
a2m
7
en
Setting
d (og(1)) ( 2²02
(c (Plgd log(1/3) a
m = O
n2 0
and combining the guarantee from Theorem we get that RRSPM (Algorithm 4) is a 8- pure differ- entially private (a, leameer
37

---

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:
The abstract and introduction accurately captures all the contributions of the paper. All the claims formally stated in the main body and the appendix of the paper.
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 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 as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The limitations are that the work requires public, unlabelled data and that the statistical rates of our efficient algorithms do not match those achievable by inefficient methods. Both limitations stated clearly and repeatedly throughout the text.
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, asympiotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because 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 ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best 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 not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
38

---

Answer:
[Yes]
Justification: Proof sketches are provided in the main body and detailed arguments are 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 or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: Did not run experiments.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a 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 a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can accomplished various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
also be provided via
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new 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 a way re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which thors are welcome to describe 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., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
39

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
Did not run experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips) cc/
sublic/guidees/DdeeSutiiii iocc for more details.
While we encourage the release code and data, we understand that this might not be possible, so "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a 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: //nips.co. wwwpppplccggpuicceecooooooppppee /eggdde/Cooeeuummmi Codeeubmi ssi siioiiiiyy for more details.
The authors should provide instructions on data access and preparation, including how to 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. only a subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as 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: Did not run 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 appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
Did not run experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the 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, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
40

---

The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard emror of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
error bars are reported in tables or plots, The authors should explain 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 execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
Did not run experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or 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 or failed experiments that didn't 't make it 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 https: /ttpa://////.u../eee/
Answer: [Yes]
Justification: Evident.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code 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., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Evident.
Guidelines:
The answer NA means that there 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 spe- cific groups), privacy considerations, and security considerations.
41

---

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 mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to 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:
Does not apply.
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 re- quiring that users adhere usage guidelines or restrictions 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 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: Does not apply.
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.
assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, paperswi tecodhhoodee com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense 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.
42

---

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 documenta- tion provided alongside the assets?
Answer: [NA]
Justification: Does not apply.
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 per include the full text instructions given to participants and sereenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification:
Does not apply.
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 contri- bution 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, cura- tion, or other labor should be paid at least the minimum wage 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 the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Does not apply.
Guidelines:
The answer NA means that the paper does involve crowdsoureing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) 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.
43


Reviews:
[{"review_id": "ofkTQeSH4J", "reviewer": "Reviewer_21sV", "summary": "This paper addresses the problem of identifying a particular class of functions which can be learnt efficiently with unlabelled public and labeled private samples maintaining privacy with respect to the private samples only. The authors propose an algorithmic framework for privately learning such function classes with public unlabelled data. For the general category of functions, if the expectation of the function with respect to the measure is greater than a certain value, the learning is done in two stages. First they learn the unlabelled data by minimizing the loss function with respect to the labeled private data and then add a noisy gaussian process using the function output of the unlabelled data. Then they simply privatize it by using the private output perturbation method. The algorithm can be further simplified for convex functions by simply using L2 regularizer with respect to the function outputs of the unlabelled data instead of using a Gaussian process in case of the general category. They mainly provide the theoretical guarantees by using tools from existing work on Gaussian anti concentration to bound the stability of the learning algorithm on perturbed datasets in terms of the worst case Gaussian complexity of the function class. Then they use the bound on the stability to get a differential privacy guarantee of the output perturbation method. Finally, they show the fact that the algorithm can learn using standard learning theory arguments. These proposed algorithms are oracle efficient in the sense that they only require a polynomial number of calls to the ERM oracle.", "questions": "The paper is theoretically sound and makes sense from the perspective of getting an oracle efficient algorithm for private learning with public data but the intuition behind algorithm 1 is not completely clear. There is part of the algorithm in which the authors add \\omega which is the weighted gaussian sum of the function values of the auxiliary data. I have some questions regarding that\n1. Why was there a need to create a gaussian process with respect to the auxiliary data in the first place? How would the analysis have gone differently or learnability would have been hampered simply by running ERM on the standard loss function with respect to the private data?\n2. Following up with the first question, can the authors emphasize on the point in the analysis where we got an advantage due to using the public data in the mentioned algorithm? Where did we consider the additional information from the public data in the analysis?\n3. Can the authors also give an example or maybe give a specific reference to a paper in which they could mention a particular learning problem which would not be privately learnable but can be learnt with public data? Does this algorithm ensure that the particular example problem can be learnt in polynomial time?", "limitations": "The authors have mentioned the limitations of their work multiple times within their text and have provided some open problems to further the direction of research in this topic.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. This work contributes to the area of learning theory and differential privacy in two ways. First it identifies certain classes of functions which can be learnt privately with public data in polynomial calls to the ERM oracle. Secondly, it provides the first algorithm with conditional polynomial time learning and privacy guarantee for these classes of functions.\n2. The main novelty in this paper is tightening the result by Block et. Al. [1] to get the stability guarantees for the gaussian process which this algorithm follows paving way for making analysis easier for works which use a similar kind of a framework to learn using auxiliary data.\n3. This paper is very self-contained in terms of the content and all the proofs have been reiterated, with the necessary changes, to ensure that a beginner in the area of learning theory and differential privacy can develop a good understanding of the paper.\n4. The arguments in this paper are mostly direct and easy to follow, while some more complex arguments like the anti concentration expressions are self contained and do not require any additional references.\n\n[1] Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as easy as statistical learning. In Conference on Learning Theory, pages 1716–1786. PMLR, 2022.", "weaknesses": "The main weakness in the paper is not discussing a clear intuition of the role of public data in the algorithm and how it helps to learn when private learning is not possible. The questions regarding the paper mentioned below also follow the same theme. It would be very helpful if the authors can add a specific and detailed discussion on the role of public data answering the questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review and their helpful comments! Please see responses to individual questions below.\n\n> Why was there a need to create a gaussian process with respect to the auxiliary data in the first place? How would the analysis have gone differently or learnability would have been hampered simply by running ERM on the standard loss function with respect to the private data?\n\nNote that adding the gaussian process serves to ensure privacy and does not help (and could potentially hurt) the learning.  Indeed, our learning analysis is concerned with ensuring that our algorithm does not output a hypothesis that is significantly worse than simply running ERM.  The reason to add the perturbation is to ensure *privacy*.  As discussed in Lines 204-207, our privacy analysis follows by ensuring the first step is stable in $L^2$ of the empirical measure *on the public data*  (Lemma 1) and then boosting that stability guarantee into a privacy guarantee (Lemma 3); if we did not have public data and were to only use ERM, then such an approach is meaningless.  We could still ensure label privacy in this way by dong the same procedure and treating the features as public, unlabelled data, but this would still leak information about these features, thereby precluding a privacy guarantee.\n\n> Following up with the first question, can the authors emphasize on the point in the analysis where we got an advantage due to using the public data in the mentioned algorithm? Where did we consider the additional information from the public data in the analysis?\n\nSee previous answer.\n\n> Can the authors also give an example or maybe give a specific reference to a paper in which they could mention a particular learning problem which would not be privately learnable but can be learnt with public data? Does this algorithm ensure that the particular example problem can be learnt in polynomial time?\n\nTwo papers that discuss this are [1] and [2], cited in our work.  Note that any class with infinite Littlestone dimension but finite VC dimension (such as that of linear thresholds in Euclidean space) is PAC learnable but not privately learnable.  These classes are privately learnable *with public data* however, and our paper provides oracle-efficient algorithms for learning them.\n\n\n\n[1]  Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite littlestone dimension. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 852–860. ACM, 2019.\n\n[2] Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learning of threshold functions. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 634–649. IEEE, 2015.", "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": "tHIKwZSgqi", "reviewer": "Reviewer_Fe9c", "summary": "The paper investigates oracle-efficient semi-private learning. It provides a general framework for transforming an efficient non-private learner into an oracle-efficient semi-private learner for smooth data distributions. For convex and Lipschitz loss functions, as well as binary classification loss, they instantiate the general framework and provide an implementable algorithm with polynomial oracle calls. The output of the proposed algorithm achieves high accuracy with high probability for any hypothesis class with a bounded VC dimension under smooth data distributions. Although the initial algorithm does not achieve optimal sample complexity, the authors introduce a second algorithm inspired by the Follow-the-Regularized-Leader approach from online learning. This improved algorithm enhances the sample complexity bound and requires only two oracle calls.", "questions": "See weaknesses.", "limitations": "I don't identify significant limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is clearly written. \n- The proposed methods not only have theoretical guarantees, but are of practical relevance due to its efficiency. For example, algorithm 3 requires only 2 calls of the ERM oracle. \n- The results hold under slight distribution shift between the public and private data.", "weaknesses": "The sample complexity bounds rely on the assumption of a $\\sigma$-smooth data distribution. For instance, in Theorem 6, the public sample complexity is given by $m = \\tilde{\\Theta}(1/\\sigma)$ and $n = \\tilde{\\Omega}(1/\\sigma^{12})$. Could you discuss whether it's possible to improve this dependence on $\\sigma$? Additionally, could you elaborate on the necessity of assuming a smooth data distribution? Understanding the implications and possible relaxations of this assumption would be beneficial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review and their helpful comments! Please see responses to individual questions below.\n\n> Could you discuss whether it's possible to improve this dependence on $\\sigma$. \n\nWe believe that it is likely that the precise polynomial dependence on problem parameters can be improved.  Certainly in an information theoretic sense this is possible simply by constructing an $\\epsilon$-net on the function class using the public data as we discuss in Lines 39-46, although the resulting algorithm is impractical.  We leave as an interesting open question the challenge of designing oracle-efficient algorithms with improved sample complexity.\n\n> Additionally, could you elaborate on the necessity of assuming a smooth data distribution? Understanding the implications and possible relaxations of this assumption would be beneficial.\n\nRegarding the necessity of assuming a smooth data distribution, at the price of quantitatively worse rates, we can replace the notion of smoothness (uniformly bounded Radon NIkodym derivative) with the weaker notion of bounded $f$-divergence.  This point was addressed in [1] in the context of smoothed online learning and similar techniques could likely be applied here.  Please see the discussion in Lines 149-152 for the relevant remark.  Unfortunately, due to the lower bounds in works such as [2,3], one cannot remove such an assumption altogether.\n\n\n\n\n[1] Adam Block and Yury Polyanskiy. The sample complexity of approximate rejection sampling with applications to smoothed online learning. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 228–273. PMLR, 12–15 Jul 2023.\n\n[2] Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite littlestone dimension. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 852–860. ACM, 2019.\n\n[3] Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learning of threshold functions. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 634–649. IEEE, 2015.", "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": "Lex8UHFeWp", "reviewer": "Reviewer_3FxP", "summary": "This paper studies the problem of semi-private learning. In this setting, both public and private data are given while the learning algorithm only has to satisfy differential privacy with respect to the private part. Previous work has showed that leveraging the sample complexity of private learning can be improved by leveraging public data, though the methods are computationally inefficient. \n\nIn this work, the authors propose the first oracle-efficient algorithm for this task, which requires only a polynomial number of calls of  an ERM oracle. Furthermore, they consider the special cases where the functions are convex or the problem is binary classification and obtain algorithms with improved sample complexity and number of oracle calls, and can satisfy strong privacy property (pure DP).", "questions": "1. The algorithms construct semi-private learner using ERM oracles. Is it possible to construct it directly using non-private learners (which may not minimize the empirical risk)?\n2. On line 64, page 2, it is said that \"Prior work of Bassily et al.[2018] gave an oracle-efficient algorithm in this setting with somewhat better sample complexity\". Can you elaborate more on this? It looks like their work only guarantees an error of $c\\cdot OPT + \\alpha$ in the agnostic setting, which is weaker than the result obtained in this paper.", "limitations": "Discussed.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper is the first to give an oracle-efficient semi-private learning algorithm. Oracle efficiency could be useful in practice due to the fact that many algorithms have large theoretical bounds but work quite well in practice. An oracle-efficient algorithm can directly use them as black-boxes. Previous work, though attains better sample complexity, fails to exploit such a fact.\n2. The algorithms work as long as the distribution of private data is smooth w.r.t. that of public data, i.e., the two distributions are not required to be exactly the same.\n3. The algorithms are simple and easy to implement.", "weaknesses": "1. The resulting sample complexity, though being polynomial, is much higher than previous work. \n2. The algorithm requires calls to an ERM oracle. For many tasks, one may only be able to find an approximate minimizer with a small excess risk. It is not clear whether the conclusion still holds if we only have an approximate ERM oracle but not an exact one.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review and their helpful comments! Please see responses to individual questions below.\n\n>  The resulting sample complexity, though being polynomial, is much higher than previous work.\n\nWe agree that the precise polynomial in the sample complexity guarantee for our most general algorithm is higher than what is information theoretically optimal in the absence of computational constraints.  On the other hand, our guarantees are the first to hold for *oracle-efficient* algorithms in this generality. We leave as an interesting open question the challenge of designing oracle-efficient algorithms with improved sample complexity.\n\n> The algorithm requires calls to an ERM oracle. For many tasks, one may only be able to find an approximate minimizer with a small excess risk. It is not clear whether the conclusion still holds if we only have an approximate ERM oracle but not an exact one.\n\nThis is an excellent point that we will clarify in the camera ready version.  We note that our analysis in the case of Theorem 2 (corresponding to Algorithm 2) can be modified slightly to handle the case of approximate minimizers.  Indeed, the learning guarantees proceed virtually unchanged.   For the privacy guarantees, observe that privacy follows directly from stability of the first stage estimator $\\overline f$ in the respective algorithms.  By inspecting the proof of Theorem 5 we may see that a similar conclusion holds for approximate minimizers.  A quantitatively weaker version of this result that allows for such approximate minimizers can be found in [1].  In the case of the other two algorithms studied, we believe that similar minor modifications to the current analysis will yield similarly graceful weakening of our privacy guarantees as the additive error in the approximate ERM oracle increases.\n\n> The algorithms construct semi-private learner using ERM oracles. Is it possible to construct it directly using non-private learners (which may not minimize the empirical risk)?\n\nThis is a good question.  Note that our analysis really shows that any non-private learner undergoing a similar perturbation as we describe will remain a good learner after applying Algorithm 1, so the question is really if such learners can also be made private.  Here the answer depends on whether the non-private learner in question is stable with respect to the $L^2$ on the empirical measure of the public data; if so then our analysis guarantees privacy, but if not then we cannot ensure privacy.\n\n\n> On line 64, page 2, it is said that \"Prior work of Bassily et al.[2018] gave an oracle-efficient algorithm in this setting with somewhat better sample complexity\". Can you elaborate more on this? It looks like their work only guarantees an error of $c \\cdot \\textrm{OPT} + \\alpha$ in the agnostic setting, which is weaker than the result obtained in this paper.\n\nThank you for this point; you are correct and we will update our discussion accordingly.\n\n\n\n[1]  Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as easy as statistical learning. In Conference on Learning Theory, pages 1716–1786. PMLR, 2022.", "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": "8B23VLtkwT", "reviewer": "Reviewer_CX9N", "summary": "This paper considers the setting of differentially private learning when there is some amount of public data available. A downside of existing algorithms is that they generally use the public data to build a cover which ends up being inefficient. A natural question is to design more efficient algorithms that do make use of public data.\n\nThe main result of this paper is to show that when the Gaussian complexity of the hypothesis class is small then there is a poly-time algorithm for the problem. Furthermore, if the hypothesis class is well-structured (here they use convexity as the structure) then there is an FTRL-type algorithm that is significantly more efficient and also works under pure DP. The authors also mention that their results hold in the setting where the public data and private data may be different and they quantify this via the ratio between the cdf's.\n\nThe actual algorithms themselves actually appear quite simply and practical. In particular, one defines either a noisy or regularized ERM problem and then solve another noisy ERM problem.", "questions": "- In Theorem 1, I am not sure what $d$ refers to. Is it a dimension or it refers to something else? In particular, is there a need for the square root since you just write poly after? Also, why not use $\\mathcal{G}$ for the Gaussian complexity here as you do later in the paper?\n- I wonder if the authors have a sense what about what happens if their CDF ratio assumption in Line 73 fails to hold everywhere but does hold in all except maybe $\\delta$ fraction of the time. I'm thinking in particular if maybe the public data has an exponential tail whereas the private data has a Gaussian tail (or vice-versa). So in particular, the distributions might be fairly similar in most places except in the tail where the ratio can be wildly different. Is this captured in the remark after Definition 3 in line 149?", "limitations": "No concerns from me.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "Overall, I think this a solid contribution to the DP literature. It considers the reasonably well-studied problem of private learning with public data but provides new and simple algorithms for the setting. While I have only looked briefly at the proof techniques, they seem interesting and I think researchers working in this area will be interested to learn about them (e.g. the use of FTRL and anti-concentration type of arguments).", "weaknesses": "No weaknesses to discuss from my side.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review and their helpful comments! Please see responses to individual questions below.\n\n> In Theorem 1, I am not sure what $d$ refers to. Is it a dimension or it refers to something else? In particular, is there a need for the square root since you just write poly after? Also, why not use $\\mathcal G$ for the Gaussian complexity here as you do later in the paper?\n\nThank you for pointing out this confusing passage.  Here the $d$ is supposed to be the VC dimension.  We agree that this would be substantially clearer if we replaced it by the Gaussian complexity and will do this in the camera ready version.\n\n>I wonder if the authors have a sense what about what happens if their CDF ratio assumption in Line 73 fails to hold everywhere but does hold in all except maybe $\\delta$ fraction of the time. I'm thinking in particular if maybe the public data has an exponential tail whereas the private data has a Gaussian tail (or vice-versa). So in particular, the distributions might be fairly similar in most places except in the tail where the ratio can be wildly different. Is this captured in the remark after Definition 3 in line 149?\n\nThis is a good question.  The specific example raised is not technically covered by the remark in line 149 because the relevant $f$-divergences might not be bounded between exponential and gaussian tails.  Note that the smoothness assumption is only used in ensuring that the perturbed ERMs remain good learners on the marginal distribution over private features and thus any assumption that ensures this will lead to a bound on how well our algorithms learn.  In the case of the $\\delta$ fraction not having bounded Radon Nikodym derivative, as long as the loss function is uniformly bounded, minor modification to our analysis ensures that we simply pay a n additive term of $\\delta$ in the loss.  We emphasize that the smoothness assumption is not required to ensure privacy of the algorithm and thus our privacy guarantees hold unconditionally.", "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": "nuC2UXN94S", "reviewer": "Reviewer_b8gT", "summary": "This paper explores methods for private learning by leveraging public unlabeled data. Previous work in this area utilized public data to construct an $\\alpha$-covering and then employed an exponential mechanism to output a hypothesis privately. However, the primary drawback of this approach was its exponential running time in both building the covering and sampling from the exponential mechanism. In contrast, this work assumes the availability of an Empirical Risk Minimization (ERM) oracle, which can find the minimizer of a function class given a loss function. The authors propose new private and oracle-efficient algorithms with polynomial complexity in terms of Gaussian complexity, objective error $\\alpha$, and other parameters.", "questions": "Please refer to the Weaknesses above.", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The inefficiency of previous methods highlights the importance of this problem. This paper makes significant progress by designing private algorithms that achieve oracle efficiency, addressing a crucial gap in the literature.", "weaknesses": "I find it hard to understand the intuitions behind the algorithm design and, hence, hard to appreciate the results, possibly because I am not an expert in learning theory. Several areas remain unclear to me:\n(1). If we already have the strong convexity and assume the L is differentiable, can we compute the gradient, run the gradient descent, and reduce the problem to the convex optimization?\n(2) What is the main motivation for considering Gaussian complexity rather than the VC dimension? Can the results from previous studies be extended to Gaussian complexity?\n(3) There is a lack of discussion on sample complexity. For instance, Theorem 2 requires $n\\ge \\Omega(1/\\alpha^{14})$. It is helpful to discuss the origin of this term.\n(4) What is the state-of-the-art (SOTA) performance without public data? Does the proposed approach with public data outperform current methods in terms of sample complexity?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review and their helpful comments! Please see responses to individual questions below.\n\n> If we already have the strong convexity and assume the L is differentiable, can we compute the gradient, run the gradient descent, and reduce the problem to the convex optimization?\n\nWe would like to distinguish between strong convexity of the loss function and strong convexity with respect to a parameter belonging to some subset of Euclidean space.  Note that taking a gradient and running gradient descent does not make sense in the context of our paper as we are working with arbitrary function classes that do not necessarily live in a space where it is meaningful to take gradients.  The loss function is a function on real numbers and thus strong convexity does make sense.  By way of analogy, if we are training a neural network with square loss, the loss function itself may be strongly convex with respect to the *output* of the neural network, but is certainly *not* convex with respect to the parameters.  \n\n> What is the main motivation for considering Gaussian complexity rather than the VC dimension? Can the results from previous studies be extended to Gaussian complexity? \n\nGaussian complexity is a standard notion of complexity in learning theory and is equivalent to Rademacher complexity up to polylogarithmic factors.  There are many known relationships between these notions of complexity and VC dimension, but Gaussian complexity is strictly more general as VC dimension requires binary-valued function classes.  To the best of our knowledge, our work is the first to produce oracle-efficient algorithms in the semi-private setting that are provably effective in this level of generality.\n\n> There is a lack of discussion on sample complexity. For instance, Theorem 2 requires $n \\geq \\Omega(1/\\alpha^{14})$. It is helpful to discuss the origin of this term.\n\nWe agree that the precise polynomial in the sample complexity guarantee for our most general algorithm is higher than what is information theoretically optimal in the absence of computational constraints.  Certainly in an information theoretic sense sample complexity can be improved simply by constructing an  $\\epsilon$-net on the function class using the public data as we discuss in Lines 39-46, although the resulting algorithm is impractical. On the other hand, our guarantees are the first to hold for oracle-efficient algorithms in this generality. We leave as an interesting open question the challenge of designing oracle-efficient algorithms with improved sample complexity.\n\n>  What is the state-of-the-art (SOTA) performance without public data? Does the proposed approach with public data outperform current methods in terms of sample complexity?\n\nBy works such as [1] and [2], we know that private learning in the absence of public data is not always possible.  To be more precise, any class with infinite Littlestone dimension but finite VC dimension (such as that of linear thresholds in Euclidean space) is PAC learnable but not privately learnable. These classes are privately learnable with public data however, and our paper provides oracle-efficient algorithms for learning them.  \n\n[1] Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite littlestone dimension. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 852–860. ACM, 2019.\n\n[2] Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learning of threshold functions. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 634–649. IEEE, 2015.", "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:

Meta-review: This paper addresses the problem of improving private learning algorithms by leveraging public (unlabelled) data. It proposes the first computationally efficient algorithm(s) that guarantee differential privacy with respect to private samples while also achieving learning guarantees when the private data distribution is close to the public data distribution. The main results include a general framework for efficiently leveraging public data, while specialized algorithms are proposed for convex functions and binary classification tasks (with improved sample complexity bounds). 

The reviewers found the paper novel and the contributions solid in both privacy and learning guarantees. The reviewers also found the presentation clear.  As feedback for improvement, the paper could benefit from discussing further the potential improvements and/or trade-offs regarding sample complexity. Also, the paper could benefit from further discussions on how the results generalize beyond the the assumptions of the work (e.g., closeness of public and private data distributions). Overall, the reviewers found the paper novel with clear contributions, and they provided feedback for further improving the quality of the work.
Decision: Accept (poster)