Oracle-Efficient Differentially Private Learning with Public Data

Authors: adam  block
mark  bun
rathin  desai
abhishek  shetty
zhiwei steven wu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 22:21:50

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.

Main paper: 
 introduction: 
 Differential privacy (DP) [Dwork et al., 2006 ] is a standard guarantee of individual-level privacy for statistical data analysis. Algorithmic research on differential privacy aims to understand what statistical tasks are compatible with the definition, and at 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 the real numbers [Bun et al., 2015 , Alon et al., 2019] .Motivated in part by such barriers to full-fledged private learning, many papers have considered relaxing the model to allow the use of auxiliary "public" data Balcan and Feldman [2013] , Bassily et al. [2019 Bassily et al. [ , 2020b Bassily et al. [ , 2022 Bassily et al. [ , 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 et al. [2024] . In this model, a learning algorithm is given n "private" samples from a joint distribution D over example-label 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 a class F with a VC-dimension vc(F), these papers showed that in the presence of O(vc(F)) public unlabeled samples, every concept class F is agnostically learnable with O(vc(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 a 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 following 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 algorithms are available. More specifically, our main result is generic semi-private algorithms for regression 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 1 (Informal version of Theorem 2). Fix a function class F : X → [-1, 1]. Then there is an oracle-efficient, (ε, δ)-differentially private algorithm (Algorithm 2) using poly(sup m G m (F)) labeled private samples (where, G m (F) denotes the Gaussian complexity of function class F), unlabeled public samples, and calls to an empirical risk minimization oracle for F that learns an approximately optimal predictor f ∈ F.While Theorem 1 captures extremely broad learning settings, the polynomials governing its sample complexity are rather large. We identify several important cases in which the sample complexity can be improved and the number of oracle calls is only 2. In the case where the function class F is convex, we give a variant of Algorithm 2, inspired by follow-the-regularized-leader, with significantly improved sample complexity as a 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, Algorithm 4), which requires the private sample size to grow at the rate of O((vc(F)) 2 ). Prior work of Bassily et al. [2018] gave an oracle-efficient 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 algorithm, 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 F that have a 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 to design an oracle-efficient private learner for any function class F with bounded VC-dimension.In fact, our results also address a somewhat more general setting than the semi-private model described so far. Specifically, our results automatically handle the setting where there may be a 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-ture space have a density ratio bounded by σ. 1 The standard semi-private setting corresponds to the special case where σ = 1. Taking this view, we can interpret our results as oracle-efficient private 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.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 F that admits small universal identification sets [Neel et al., 2019] , synthetic 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 et al., 2020] . Oracle-efficiency is also well-established approach in online learning [Kalai and Vempala, 2005 , Hazan and Koren, 2016 , Kozachinskiy and Steifer, 2023 , Haghtalab et al., 2022a , Block and Simchowitz, 2022 , Block and Polyanskiy, 2023 , Block et al., 2023a,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-private learning algorithm Algorithm 2 adapts a follow-the-perturbed-leader inspired algorithm [Block et al., 2022] from the setting of smoothed online learning.DP learning and release with public (unlabelled) data Our results contribute to a 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 to the work in this direction we discussed above, several recent papers Bassily et al. [2022 Bassily et al. [ , 2023] ] developed efficient algorithms for private learning with domain adaptation from a public source. That work accommodates a 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 to remove statistical barriers in private query release [Bassily et al., 2020a] and density estimation Bie et al. [2022] , Ben-David et 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.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 et al., 2022 , Haghtalab et al., 2022a , Block and Simchowitz, 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 , Cesa-Bianchi et al., 2023] and its assumptions have been relaxed [Block and Polyanskiy, 2023] . 
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 = [-1, 1], 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 D with n examples from X × Y to a predictor in a function class F. We require A to satisfy differential privacy, defined below.Definition 1 (Differential Privacy Dwork et al. [2006] ). Let A : (X × Y) n → F be a randomized algorithm and D, D ′ ∈ (X × Y) n be data sets. We say that D and D ′ are neighboring if |D \ D ′ | = |D ′ \ D| ≤ 1, i.e. they differ in at most one datum. We say that A is (ε, δ)-differentially private if for all neighboring datasets D, D ′ , and for all measurable G ⊂ F, it holds thatP (A(D) ∈ G) ≤ e ε • P (A(D ′ ) ∈ G) + δ. If δ = 0, we say that A is ε-(purely) differentially private.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) n → F be a randomized algorithm. We say that A is an (α, β)learner with respect to a measure ν on X × Y and loss functionL : F → [-1, 1] if, for D sampled independently from ν, it holds that P (L(A(D)) ≤ inf f ∈F L(f ) + α) ≥ 1 -β.For regression problems, we consider the loss function L to be induced by a function ℓ :Y × Y → [0, 1], convex and λ-Lipschitz in the first argument, such that L(f ) = E (X,Y )∼ν [ℓ(f (X), Y )].For simplicity, we will denote the empirical loss on a data set D asL D (f ) = 1 n • (Xi,Yi)∈D ℓ(f (X i ), Y i ).We emphasize that in contradistinction to the standard notion of PAClearnability [Valiant, 1984] , our requirement is weaker in that we only require distribution-dependent learning, i.e., the algorithm A is allowed to depend on ν in some to-be-specified way. This is necessary in our setting as it is well known that distribution-independent differentially private PAC learning is possible only for very restricted classes of functions F with bounded Littlestone dimension [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 ν: Definition 3. Given a measure µ ∈ ∆(X ) and a parameter σ ∈ (0, 1], we say that ν x is σ-smooth with respect to µ if dνx dµ ∞ ≤ 1σ . We suppose that the learner has access to m samples Z 1 , . . . , Z m ∼ µ 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 D f (ν x ||µ) ≤ 1 σ as in Block and Polyanskiy [2023] , where D f (•||•) is a sufficiently strong f -divergence2 . In this case, the statistical rates presented below will be worse and depend on f , but the algorithms and privacy guarantees will remain unchanged. Critically, we do not require that our algorithms are private with respect to Z 1 , . . . , Z m , which we treat as 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 we suppose access to the following ERM oracle: Definition 4. Given a function class F : X → R, a data set D = {x 1 , . . . , x m } ⊂ X and loss functions ℓ 1 , . . . , ℓ m : R → R, we define the empirical risk minimization oracle ERM :F → R such that ERM(F, L D ) ∈ argmin f ∈F L D (f ), where L D (f ) = xi∈D ℓ i (f (x i )).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 et 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 as 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 in [Block et al., 2022] . We remark that applying Neel et al. [2019, Theorem 8] gives a 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.Algorithm 1: Perturb: An algorithm for perturbing a function with noise on public data.1: Input Function f ∈ F, distribution Q ∈ ∆(R), scale γ ≥ 0, public data D x = {Z 1 , . . . , Z m }. 2: Sample ζ 1 , . . . , ζ m ∼ Q. 3: Define R(f ) = f -f -γ • ζ 2 m . 4: Output f = ERM(R, F).It is well-known that even absent differential privacy guarantees, learning arbitrary function classes is impossible; we now 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 a set of points x 1 , . . . ,x d ∈ X shatters F if for all ε 1:d ∈ {0, 1} d , there is some f ε such that f ε (x i ) = ε i for all i.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] be a function class and x 1 , . . . , x m ∈ X be arbitrary points. We let ω m : F → R be the canonical Gaussian process on F, i.e.,EQUATIONwhere ξ i are independent standard Gaussians. We define the (data-dependent) Gaussian complexity of F to be E sup f ∈F ω m (f ) , the average Gaussian complexity as G m (F) =E Z E[sup f ∈F ω m (f )],and the worst-case Gaussian complexity ofF to be G m (F) = sup x1,...,xm∈X E sup f ∈F ω m (f ) .Both vc(F) and G m (F) are well known measures of complexity from learning theory and their relationships to other notions of complexity like covering number are well-understood [Mendelson and Vershynin, 2003 , Wainwright, 2019 , Van Handel, 2014] . In particular, it is well-known that G m (F) = O( vc(F)) [Dudley, 1969, Mendelson and Vershynin, 2003] and that standard PAClearning is possible if and only if , 2019 , Van Handel, 2014] . We remark that different texts use different scalings for G m (F), with some replacing the m -1/2 factor in (1) with m -1 and others omitting it entirely; our choice of scaling is motivated by the fact that a natural complexity measure for many (Donsker [Wainwright, 2019] ) function classes that our algorithms depend on is sup m G m (F), which is most compactly represented with the present scaling.G m (F) = o( √ m) [WainwrightNotation. We always reserve P and E for probability and expectation with respect to measures that are clear from the context. We denote by ∆(X ) the space of measures on some X and for any µ ∈ ∆(X ) we let ∥•∥ µ denote the L 2 (µ) norm, i.e., ∥f ∥2 µ = E Z∼µ [f (Z) 2 ]. Similarly, for m points Z 1 , . . . , Z m ∈ X , we let ∥•∥ m denote the empirical L 2 norm on these points so that ∥f ∥ 2 m = m -1 • m i=1 f (Z i ) 2 .We reserve ω m for the canonical empirical Gaussian process on F as in (1) and L for a functional on F. 
algorithms for differentially private learning: 
 In this section, we provide a general template for constructing differentially private learning algorithms 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 to convex classes but has an 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 ∥•∥ m ; (ii) Output f as the function that minimizes f -f -γ • ζ m , where γ ≥ 0 is a scale and ζ = (ζ 1 , . . . , ζ m ) is a vector of independent random variables sampled according to some distribution Q. The second step is accomplished through Algorithm 1 and is the same across our algorithms. The first step, however, Algorithm 2: Oracle Efficient Private Learner (Perturbation) 1: Input Oracle ERM, perturbation parameter η > 0, public data setD x = {Z 1 , . . . , Z m }, private data set D = {(X i , Y i )|1 ≤ i ≤ n}, function class F, loss function ℓ, noise level γ > 0, number of iterations J ∈ N, noise distribution Q ∈ ∆(R). 2: for j = 1, 2, . . . , J do 3: Sample ξ (j) 1 , . . . , ξ (j)m ∼ N (0, 1).Define ω(j) m : F → R such that ω (j) m (f ) = 1 √ m • m i=1 ξ i • f (Z i ).(2) 5:Define L (j) : F → R such that L (j) (f ) = (Xi,Yi)∈D ℓ(f (X i ), Y i ) + η • ω (j)m (f ).Define fj = ERM(L (j) , F) end7: Define f = 1 J • J j=1 fj . 8: Output f = Perturb( f , Q, γ, D x )▷ By running Algorithm 1 is algorithm-specific 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 a good learner, note that if Z i ∼ µ are independent and m is sufficiently large, then∥•∥ m ≈ ∥•∥ µ . Thus if γ is small, then f -f µ ≪ 1 and E µ L( f ) -E µ [L( f )] ≪ 1whenever ℓ is Lipschitz. By smoothness, a similar guarantee holds for expectations with respect to ν and thus f is a good learner. To see why f is differentially private, note that by choosing Q to be a standard Gaussian, we can ensure that the likelihood ratios of choosing f given f versus f ′ are controlled by ff ′ m . Thus, if f is stable with respect to ∥•∥ 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 a perturbed version of the empirical risk minimization problem and then averaging. Specifically, for j ∈ [J], we define L (j) : F → R as a sample path of a noncentred Gaussian process in (2) and let fj denote the minimizer of L (j) over F. We then output f as the average of f1 , . . . , fJ . 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 ν x is σ-smooth with respect to µ. Theorem 2. Suppose that F :X → [-1, 1] is a function class and µ ∈ ∆(X ) is a measure such that inf f ∈F ∥f ∥ µ ≥ 2 3 . Let ℓ : [-1, 1] × [-1, 1] → [0,1] be a loss function that is convex and λ-Lipschitz in its first argument. If Q = N (0, 1) in Algorithm 1, then for any ε, δ, α, β ∈ (0, 1), there are choices of η, γ > 0 and J, m ∈ N, all polynomial in problem parameters and given in Appendix C.6, such that ifn = poly sup m G m (F), log 1 δ , log 1 β , λ • ε -3 • α -14 ,then the f returned by Algorithm 2 is (ε, δ)-differentially private. If ν x is σ-smooth with respect to µ, then f is an (α, β)-learner with respect to ν x and ℓ.We emphasize that Algorithm 2 is always differentially private, independent of ν; however, our algoirthm is only a good learner if ν x is smooth with respect to µ. We remark that all of the conditions in Theorem 2 are standard with the exception of the assumption that ∥f ∥ µ ≥ 2/3 for all f ∈ F. This condition is easy to ensure by setting µ = µ+2•δ z ⋆ Algorithm 3: Oracle Efficient Private Learner (Regularization)1: Input Oracle ERM, perturbation parameter η > 0, public data setD x = {Z 1 , . . . , Z m }, private data set D = {(X i , Y i )|1 ≤ i ≤ n}, function class F, loss function ℓ, noise level γ > 0, number of iterations J ∈ N, noise distribution Q ∈ ∆(R). 2: Define L : F → R such that L(f ) = (Xi,Yi)∈D ℓ(f (X i ), Y i ) + η • ∥f ∥ 2 m .(3)3: Define f = ERM(L, F) 4: Output f = Perturb( f , Q, γ, D x ) ▷ By running Algorithm 1We further remark that it is classical that the complexity notion sup m G m (F) is upper bounded by vc(F) for binary function classes and log(|F|) 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 G m (F) = ω(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 complexity is a large polynomial of the desired accuracy. Indeed, the sample complexity of Algorithm 2 scales like O vc(F) • ε -3 • α -14 , which is significantly worse than the O vc(F) • α -2 sample complexity that a non-private algorithm such as ERM can achieve [Wainwright, 2019] or even the O vc(F) • α -2 • ε -2 sample complexity achievable by private, inefficient algorithms with public data [Bassily et al., 2020b] . Furthermore, we are unable to achieve a pure differential privacy guarantee 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 we still use Algorithm 1 as a subroutine, in Algorithm 3, motivated by the difference between Follow the Perturbed Leader (FTPL) and Follow 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 ω to be a strongly convex regularizer instead of a Gaussian Process perturbation. More specifically, we define L in (3) as the empirical loss regularized by ∥•∥ and output f = ERM(L, F). We have the following result:Theorem 3. Suppose that F : X → [-1, 1] is a convex function class and ℓ : [-1, 1] × [-1, 1] → [0, 1]is convex and λ-Lipschitz in its first argument. Suppose that Z 1 , . . . , Z m ∼ µ are independent and Q = N (0, 1). Then there are η, γ, m polynomial in problem parameters and given in Appendix C.6 such that, ifn = poly log β -1 , log δ -1 , λ • (sup m G m (F)) 2 • ε -1 • α -5 then the f returned by Algorithm 3 is (ε, δ)-differentially private. If ν x is σ-smooth with respect to µ, then f is an (α, β)-learner with respect to ν x and ℓ. Furthermore, if Q = Lap(1), and n = poly sup m G m (F), log β -1 , λ • ε -1 • α -6 ,then Algorithm 3 is ε-purely differentially private and an (α, β)-PAC learner for any σ-smooth ν x .As in the case of Theorem 2, we can easily generalize Theorem 3 to apply to function classes F where G m (F) = ω(1) at the cost of worse polynomial dependence in 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 α -2 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 3 can be applied to conv(F), the convex hull of F, if we assume the learner has access to ERM ′ , a stronger ERM oracle that can optimize over conv(F). In this case, Theorem 3 supercedes Theorem 2 as it is easy to see that G m (F) = G m (conv(F)) and thus the sample complexity of Algorithm 3 is strictly better than that of Algorithm 2 and the pure differential privacy result applies. 
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 if Q is a standard Gaussian (resp. exponential) then stability of f with respect to ∥•∥ m can be translated into differential privacy. The second shows that f will be stable with respect to ∥•∥ m . Similarly, the proof that f is a good learner first shows that f is a good learner and then that f and f are close. We begin with the more technically novel parts and show that, under standard assumptions, Algorithms 2 and 3 result in f that are stable in ∥•∥ m . 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 ∥•∥ m can be boosted to a differential privacy guarantee using the Gaussian and Laplace Mechanisms [Dwork et al., 2006] . Finally, we apply standard learning theoretic techniques to show that f is a good learner.In this section, we explain how to prove that Algorithms 2 and 3 are stable with respect to ∥•∥ m . 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 techniques. We begin by describing the stability analysis of Algorithm 2. The key lemma underlying the stability of Algorithm 2 is an improved version of a 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 ∥•∥ induced by an inner product ⟨•, •⟩ and let m, m ′ : F → R be measurable functions such that ∥m -m ′ ∥ ∞ ≤ τ . If ω is a centred Gaussian process on F with covariance kernel given by ⟨•, •⟩, Ω(f ) = m(f ) + η • ω(f ), f = argmin f ∈F Ω(f ),and Ω ′ and f ′ are defined similarly, then for any ρ, τ > 0, it holds thatP f -f ′ > ρ ≤ 8τ ρ 4 κ 2 η • E sup f ∈F ω(f ) , where κ 2 = inf f ∈F E ω(f ) 2 .The proof proceeds in a similar way to that of Lemma 33 from Block et al. [2022] , but involves a tighter analysis in several steps in order to improve the bound. The intuition for the result is straightforward: if f is the minimizer of the Gaussian process Ω, then with reasonable probability, almost minimizers of Ω (as measured by the tolerance τ ) are within a radius ρ of f as long as the Gaussian process is nontrivial in the sense that all indices f have sufficiently high variance.Moreover, the quantitative control on the probability of this event depends in a natural way both on τ and ρ as well as on the Gaussian process ω: more complex spaces F and lower variance processes lead to a 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-concentration is tighter by polynomial factors in ρ, η, and κ.Like essentially all anti-concentration results [Chernozhukov et al., 2015] , Proposition 1 holds only with moderate probability in the sense that the guarantee is polynomial in the scale ρ; 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 1 to show that if fj is as in Line 6 of Algorithm 2 and f ′ j is defined analogously with respect to D ′ , then with moderate probability fjf ′ j m is small. Using Jensen's inequality and a standard chernoff bound, we can then boost this moderate probability guarantee into a high probability guarantee to show that if J is sufficiently large, then ff ′ m 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 ℓ : [-1, 1] ×2 → [0, 1]is a bounded loss function. Suppose that D, D ′ are neighboring datasets and let f be as in Line 5 of Algorithm 2 and f ′ be defined analogously with respect to D ′ . Then for any ρ, δ > 0, with probability at least 1 -δ, over the Gaussian processes ω(j) , f -f ′ m ≤ 2 (η•n) 1/3 κ 2/3 • E sup f ∈F ω m (f ) 1/3 + log( 1 δ ) J .We note that the worse dependence on η in Lemma 1 as compared to Proposition 1 arises from integrating the tail bound to obtain the control on fjf ′ j m in expectation necessary to apply Jensen's inequality; details can be found in Appendix C.1.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 ℓ is convex and λ-Lipschitz in its first argument. Let D, D ′ denote neighboring data sets and let f denote the output of Line 3 in Algorithm 3 and f ′ be the analogous output evaluated onD ′ . If F is convex, then, f -f ′ m ≤ 2 √ η•n .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 η in Lemma 2 is improved, which in turn leads to the better sample complexity exhibited in Theorem 3. With stability of Algorithms 2 and 3 thus established, we proceed to analyze the effect of the output perturbation.We now turn to the analysis of Algorithm 1. In order to boost a stability-in-norm 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 sufficiently large as to 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 et al., 2011 , Neel et al., 2019] , with the bound on the size of the output perturbation following from standard tail bounds on Gaussian and Laplace random vectors. The privacy guarantees are similarly standard and summarized in the following lemma: Lemma 3. Suppose f ∈ F is the output of an algorithm A : D → F that is ρ-stable with respect to ∥•∥ m , i.e., for any neighboring data set D ′ , it holds that ∥A(D) -A(D ′ )∥ m ≤ ρ.Then applying Algorithm 1 with Q = N (0, 1) to f results in an (ε, δ)-private algorithm ifm 2γ 2 1 + γ • log 1 δ ρ ≤ ε. Similarly, if Q = Lap(γ), then the algorithm is ε-purely private if m 3/2 /γ • ρ ≤ ε.This standard result is proved in 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 tradeoff is dictated by the number of labelled samples, not m.The balance between privacy and learning is quantified in the choices of m and γ. If γ is too large, then f will be private but a poor learner, whereas the opposite occurs if γ is too small. Similarly, if m is too large then privacy is reduced whereas if m is too small then ∥•∥ m is a poor approximation for ∥•∥ µ .By combining Lemma 1 (resp. Lemma 2) with Lemma 9, we can establish the privacy of Algorithm 2 (resp. Algorithm 3) as long as the tuning parameters m, γ, η, 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 ∥•∥ m is a good approximation for ∥•∥ µ : Lemma 4. Let F : X → [-1, 1] be a bounded function class and let Z 1 , . . . , Z m ∼ µ be independent samples. Then for any β > 0 it holds with probability at least 1 -β that for all f ∈ F,∥f ∥ µ ≤ 2 • ∥f ∥ m + O G m (F )+ √ log(1/β) √ m .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 L D (f ) ≈ L(f ) for all f ∈ F. The final step is the following simple lemma, which ensures that if η is not too large, then L D ( f ) ≈ L D (f ERM ): Lemma 5. Let F : X → [-1, 1] be a bounded function class and let R : F → R be an arbitrary, possibly random, regularizer. Letf ERM ∈ argmin f ∈F L D (f ) and f ∈ argmin f ∈F L D (f ) + R(f ). Then, L D ( f ) ≤ L D (f ERM ) + sup f,f ′ ∈F R(f ) -R(f ′ ). Lemma 5 is a simple computation proved in Appendix C.5. Letting R(f ) be either η • ω (j) m (f ) in Algorithm 2 or η • ∥f ∥ 2 m inAlgorithm 3 demonstrates that if η is not too large, then f performs similarly to f ERM . To prove that Algorithms 2 and 3 produce good learning algorithms then, it suffices to combine these three components, observing first that L( f ) is close to optimal if n ≫ 1 and η is not too large, second that ∥ f -f ∥ µ ≪ 1 if m ≫ 1 and γ is sufficently small, and third that|L( f ) -L( f )| ≲ ∥ f -f ∥ µ if ν x is σ-smooth with respect to µ and ℓ is λ-Lipschitz in its first argument. Combining these results concludes the proofs of Theorems 2 and 3. A detailed and rigorous argument for both proofs is presented in Appendix C. As a 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 5 in Algorithm 2 to be proven a good learner, we apply Jensen's and the above argument that ensures that fj is a good learner. Interestingly, on the other hand, convexity in ℓ is irrelevant to the learning guarantee of Algorithm 3 while it is essential to the privacy guarantee. Further understanding the role that such structural assumptions play in allowing privacy is an interesting direction for future work. In the previous section, we presented a private algorithm for general, real-valued loss functions.Here, we turn to the special case of classification, where we provide an algorithm with improved rates. Formally, binary classification is a special case of Definition 2, where F : X → {0, 1} and ℓ is 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 a 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 perturbation and return any f that agrees with f on the public data. This is accomplished by carefully choosing the initial perturbation to the ERM objective (see ( 4)) so that the predictions of f on the public data satisfy differential privacy without ensuring some form of stability in norm. As a result, 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) DrawInput ERM oracle ERM, dataset D = {(X i , Y i ) | 1 ≤ i ≤ n},EQUATION) Get f = ERM(F, L ξ,D, D ). Output f = Perturb( f , Q, γ = 0, Dx ) ▷ By running Algorithm 1 Theorem 4. Suppose that F : X → Y is a function class of VC dimension d and ℓ : Y ×Y → {0, 1}is the indicator loss. Suppose that Z 1 , . . . , Z m ∼ µ and ξ 1 , . . . , ξ m ∼ Lap(2m/ε) are independent.Then there is a choice of m polynomial in the problem parameters such that ifn = Ω(d 2 ε -1 α -5 log(β -1 )),then the f returned by Algorithm 4 is ε-pure differentially private. If ν x is σ-smooth with respect to µ, then f is an (α, β)-learner with respect to ν x and ℓ. Furthermore, for some C > 0, if ξ 1 , . . . , ξ m ∼ N (0, C m log(1/δ)/ε) then there is a choice of m polynomial in the problem parameters such that ifn = Ω(d 2 ε -1 α -4 log 1/2 (1/δ) log(β -1 )),then the f returned by Algorithm 4 with Gaussian perturbations is (ε, δ)-differentially private and is an (α, β)-PAC learner with respect to any σ-smooth ν x .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 ⋆ ∈ F perfectly predicts the Y from the X, we get a sample complexity of n = Ω(d 2 ε -1 α -3 log(β -1 )) for ε-pure differential privacy and n = Ω(d 2 ε -1 α -2.5 log 1/2 (1/δ) log(β -1 )) for (ε, δ)-differential privacy.We emphasize that Theorem 4 attains the improved O(α -5 ) sample complexity (even O(α -4 for approximate differential privacy)), which is significantly better than the O(α -14 ) from Theorem 2. While this is a major improvement, it still falls short of the desired O(α -2 ) statistical rates achievable by inefficient algorithms from [Bassily et 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.While the privacy of Algorithms 2 and 3 is proven in two steps, by first demonstrating stability and then leveraging the output perturbation to ensure privacy, the privacy of Algorithm 4 is proven directly. Our approach is motivated by techniques from Neel et al. [2019] , which adapt the earlier notion of separator sets from Goldman et al. [1993] , Syrgkanis et al. [2016] , Dudík et al. [2020] to the setting of differential privacy. Unlike those works, however, we do not require the strong assumption that F 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 Dx is private with respect to D, where we letF| Dx = {(f (Z i )) 1≤i≤m |f ∈ F}.We have the following privacy guarantee for f ( Dx ) ∈ F| Dx :Lemma 6. (Privacy over Projection) Let D, D ′ be arbitrary datasets containing n points each. Let Dx be a set of m points Z 1 , . . . , Z m ∈ X . Let Ỹ1 , . . . , Ỹm ∈ {0, 1} be the set of corresponding labels. Then for all measurable H ⊆ F | DxP(ERM(F| Dx , L ξ,D, D ) ∈ H) ≤ e ε • P(ERM(F| Dx , L ξ,D ′ , D ) ∈ H),where L ξ,D, D is defined as in (4).With the above lemma in hand, the privacy of Algorithm 4 follows immediately from the postprocessing property of differential privacy. We provide a full proof of Lemma 6 in Appendix D and now turn to the accuracy guarantee.Proving that Algorithm 4 is an (α, β)-learner whenever ν x is σ-smooth with respect to µ 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 intermediate f is driven up, while the difference between f and f is driven down, thereby requiring a careful balance; here, however, we do not also need to account for the balancing of the variance γ.We provide a full proof of the accuracy guarantee in Appendix D.In this section we present and prove a 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 1 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 a function. Let K : T × T → R be a covariance kernel in the sense that for any t 1 , . . . , t n ∈ T , the matrix (K(t i , t j )) i,j∈[n] is positive semi-definite. We say that ω : T → R is a Gaussian process with mean function m and covariance kernel K if for any t 1 , . . . , t n ∈ T , the random vector (ω(t i )) i∈[n] is Gaussian with mean (m(t i )) i∈[n] and covariance matrix (K(t i , t j )) i,j∈ [n] . We say that ω is a centered Gaussian process if m is identically zero.Note that by Le Gall [2016, Theorem 1.11 ] such a process always exists given m, K. Furthermore, we note that K induces a semi-metric d on T by letting d(t, t ′ ) 2 = E (ω(t) -ω(t ′ )) 2 . We now prove the following result, which is a tighter version of Block et al. [2022, Lemma 33] .Theorem 5 (Gaussian Anti-concentration). Let T be a set, m : T → R be a mean function and K : T × T → R be a covariance kernel (in the sense of being positive definite). Let d denote the metric induced by K and suppose that m is continuous with respect to d, and the metric space (T, d) is separable and compact. Let ω denote a Gaussian process on T with covariance K and for η > 0, letΩ(t) = m(t) + η • ω(t)be an offset Gaussian process. We further suppose that ω is taken to be a version with almost surely continuous paths t → ω(t) and that 0 < κ ≤ K(t, t) ≤ 1 for all t ∈ T . Lett ⋆ = argmin t∈T Ω(t),and,E(ρ, τ ) = there exists s ∈ T such that K(s, t ⋆ ) K(t ⋆ , t ⋆ ) ≤ 1 -ρ 2 and Ω(s) ≤ Ω(t ⋆ ) + τ ,for ρ, τ > 0. The following holds:P (E(ρ, τ )) ≤ τ ρ 2 ηκ 2 • E sup t∈T ω(t) .Note that K(s,t) K(t,t) is a measure of how close s and t are to each other; indeed, in the special case where κ = 1 this is precisely the correlation and thus s and t are more closely related the closer this quantity is to 1. Thus the event E(ρ, τ ) can be interpreted to mean that there exists some point s far from t ⋆ (as governed by ρ) such that Ω(s) is almost minimal (as governed by τ ); in other words, Theorem 5 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.Proof of Theorem 5. Note that by compactness of T and almost sure continuity of Ω, a minimizer of Ω exists almost surely; furthermore, by [Kim and Pollard, 1990, Lemma 2.6 ], t ⋆ is almost surely unique. As T is separable and Ω has almost surely continuous sample paths, it suffices to replace T with a countable dense subset. We will hereafter suppose without loss of generality that T is countable. For each t ∈ T , define the setA(t) = s ∈ T K(s, t) K(t, t) ≤ 1 -ρ 2 and Ω(s) ≤ Ω(t) + τ .It then suffices to lower bound the probability that A(t ⋆ ) = ∅. We computeP (|A(t ⋆ )| = 0) = t∈T P (t ⋆ = t and |A(t)| = 0) = t∈T E y P t ⋆ = t and inf K(s,t)≤(1-ρ 2 )K(t,t) Ω(s) ≥ y + τ |Ω(t) = y ,where the expectation is taken over the distribution of Ω(t). Now, fix t and let Ω t,y denote the Gaussian process Ω conditioned on the event that Ω(t) = y. Let m t,y and η 2 • K t denote the mean and covariance processes of Ω t,y . Critically, note that K t is independent of y and for all s ̸ = t, we havem t,y (s) = m(s) + K(s, t) K(t, t) (y -m(t)) .Define the functionsEQUATIONWe also have that b(s) ≥ 0 for all s by the fact that K(s, t) ≤ K(s, s) • K(t, t) and K(s, s) ∨ K(t, t) ≤ 1. Furthermore, for all s, it holds that m t,y+ τ ρ 2 (s) = m t,y (s) + a(s).Thus, for fixed t ∈ T and y ∈ R, we haveP t ⋆ = t and inf K(s,t)≤(1-ρ 2 )K(t,t) Ω(s) ≥ y + τ |Ω(t) = y ≥ P t ⋆ = t and inf K(s,t)≤(1-ρ 2 )K(t,t) Ω(s) -b(s) ≥ y|Ω(t) = y = P t ⋆ = t and inf K(s,t)≤(1-ρ 2 )K(t,t) Ω(s) -b(s) -a(s) + a(s) ≥ y|Ω(t) = y = P t ⋆ = t and inf K(s,t)≤(1-ρ 2 )K(t,t) Ω(s) + a(s) ≥ y + τ ρ 2 |Ω(t) = y = P t ⋆ = t and inf K(s,t)≤(1-ρ 2 )K(t,t) Ω(s) ≥ y + τ ρ 2 |Ω(t) = y + τ ρ 2 ≥ P t ⋆ = t and inf K(s,t)≤(1-ρ 2 )K(t,t) Ω(s) ≥ y + τ ρ 2 |Ω(t) = y + τ ρ 2 ,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 K t is independent of y. Now, denoteq t (y) = (2πK(t, t)) -1 2 exp - (y -m(t)) 2 2η 2 K(t, t) ,the density of Ω(t) and note that we haveP (|A(t ⋆ )| = 0) = t∈T ∞ -∞ q t (y)P t ⋆ = t and inf K(s,t)≤1-ρ 2 Ω(s) ≥ y + τ |Ω(t) = y dy ≥ t∈T ∞ ∞ q t (y)P t ⋆ = t and inf K(s,t)≤1-ρ 2 Ω(s) ≥ y + τ ρ 2 |Ω(t) = y + τ ρ 2 dy. (7) We then compute ∞ -∞ q t (y)P t ⋆ = t and inf K(s,t)≤1-ρ 2 Ω(s) ≥ y + τ ρ 2 |Ω(t) = y + τ ρ 2 dy (8) = ∞ -∞ q t (y)P t ⋆ = t and inf K(s,t)≤1-ρ 2 Ω(s) ≥ y|Ω(t) = y dy + ∞ -∞ q t (y) -q t y - τ ρ 2 • P t ⋆ = t and inf K(s,t)≤1-ρ 2 Ω(s) ≥ y|Ω(t) = y dy,where we added and subtracted the first term and then made the variable substitution y + τ ρ 2 → y for the latter integral. Note thatP t ⋆ = t and inf K(s,t)≤1-ρ 2 Ω(s) ≥ y|Ω(t) = y = P (t ⋆ = t|Ω(t) = y)as Ω(s) ≥ Ω(t ⋆ ) for all s ∈ T by definition. Combining this observation with ( 7) and (8) yieldsP (|A(t ⋆ )| = 0) ≥ t∈T ∞ -∞ q t (y)P (t ⋆ = t|Ω(t) = y) dy - t∈T ∞ -∞ q t (y) -q t y - τ ρ 2 • P (t ⋆ = t|Ω(t) = y) dy.For the first term, we havet∈T ∞ -∞ q t (y)P (t ⋆ = t|Ω(t) = y) dy = t∈T P (t ⋆ = t) = 1.For the second term, using the fact that 1 -e x ≤ x for all x, we haveq t (y) -q t y - τ ρ 2 = q t (y)   1 -exp    (y -m(t)) 2 2η 2 K(t, t) - y -m(t) -τ ρ 2 2 2η 2 K(t, t)       ≤ q t (y)    (y -m(t)) 2 2η 2 K(t, t) - y -m(t) -τ ρ 2 2 2η 2 K(t, t)    ≤ q t (y) 2η 2 κ 2 • 2τ ρ 2 (y -m(t)) . Thus we haveP (|A(t ⋆ )| > 0) = 1 -P (|A(t ⋆ )| = 0) ≤ t∈T ∞ -∞ q t (y) 2η 2 κ 2 • 2τ ρ 2 (y -m(t)) • P (t ⋆ = t|Ω(t) = y) dy = τ ρ 2 η 2 κ 2 t∈T ∞ -∞ (y -m(t))q t (y)P (t ⋆ = t|Ω(t) = y) dy = τ ρ 2 η 2 κ 2 • E [Ω(t ⋆ ) -m(t ⋆ )] ≤ τ ρ 2 η 2 κ 2 • E sup t∈T Ω(t) -m(t) .The result follows by noting that η • ω(t) = Ω(t) -m(t) for all t ∈ T .We now prove a corollary of Theorem 5 that will be useful in the proof of Proposition 1 and which makes the relationship between E(ρ, τ ) and the intuition of distance between t ⋆ and s more explicit. Corollary 1. Suppose that we are in the situation of Theorem 5 with the additional conditions that T is a subset of a real vector space and that d(s, t) = K(s -t, s -t). Let m ′ : T → R denote a mean function such that sup t∈T |m(t) -m ′ (t)| ≤ τ and let Ω ′ denote the corresponding shifted Gaussian process. If t ⋆ ′ = argmin t∈T Ω ′ (t), thenP d(t ⋆ , t ⋆ ′ ) > ρ ≤ 8τ ρ 4 ηκ 2 • E sup t∈T ω(t) . Proof. Note that d(s, t) 2 = K(s -t, s -t) = K(s, s) + K(t, t) -2K(s, t).Let M = max(K(t ⋆ , t ⋆ ), K(t ⋆ ′ , t ⋆ ′ )) ≤ 1 and note that the above implies:d(t ⋆ , t ⋆ ′ ) 2 ≤ 2M 1 - K(t ⋆ ′ , t ⋆ ) M .Thus,P d(t ⋆ , t ⋆ ′ ) > ρ ≤ P 2M 1 - K(t ⋆ , t ⋆ ′ ) M > ρ ≤ P 1 - K(t ⋆ , t ⋆ ′ ) M > ρ 2 2 ≤ 2    τ ρ 2 2 2 ηκ 2 • E sup t∈T ω(t)    = 8τ ρ 4 ηκ 2 • E sup t∈T ω(t) ,where the last inequality follows by applying a union bound and Theorem 5 to the Gaussian processes Ω and Ω ′ after observing thatΩ ′ (t ⋆ ) ≤ Ω ′ (t ⋆ ′ ) + τand similarly for Ω(t ⋆ ′ ).We are now ready to prove Proposition 1 using Corollary 1.Proof of Proposition 1. Let T = F, and observe thatd(f, f ′ ) 2 = K(f -f ′ , f -f ′ ) = E ω(f ) -ω(f ′ ) 2 = ∥f -f ′ ∥ 2 .The result then follows immediately by applying Corollary 1 to the Gaussian processΩ(f ) = m(f ) + η • ω(f ).In this section we provide the full proofs for Theorems 2 and 3, as well as more general statements under different measures of the complexity of the function class F. We begin the section by stating formal bounds on the learning and differential privacy guarantees for each algorithm. In Appendix C.1, we prove Lemma 1, 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 ∥•∥ m can be boosted to 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 Algorithm 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 theorems in Appendix C.6. Finally, for the sake of completeness, we prove a norm comparison lemma in Appendix C.7 that was deferred from Appendix C.5 for the purpose of continuity.We break the proof into two parts. First, we integrate the tail bound from Proposition 1 to get control on E fjf ′ j m for any j ∈ [J]. We then apply a Jensen's inequality and a Chernoff bound to get high probability control on ff ′ . We begin with the following lemma: Lemma 7. Let fj be as in in Line 6 of Algorithm 2 and f ′ j is defined analogously with respect to D ′ , a neighboring dataset to D. ThenE fj -f ′ j 2 m ≤ 2 (n • η) 1/3 κ 2/3 • E sup f ∈F ω m (f ) 1/3, where the expectation is with respect to ξ (j) .D (f ) -L D ′ (f )| ≤ 1n for all f ∈ F. Thus, if f (1) and f (1) ′ are as in the statement of the corollary, thenL D ( f (1) ′ ) + η • ω (1) m ( f (1) ′ ) ≤ L D ( f (1) ) + η • ω (1) m ( f (1) ) + 1 n .Plugging in τ = 1 n and applying Proposition 1 yieldsP fj -f ′ j m > ρ ≤ 8 nρ 4 κ 2 η • E sup f ∈F ω m (f ) .Now, we can integrate the tail bound to get for any ζ > 0,E f -f ′ 2 m ≤ ζ + 1 ζ 2ρP f -f ′ m > ρ dρ ≤ ζ + 2 • 1 ζ ρ • 8 nρ 4 κ 2 η • E sup f ∈F ω m (f ) dρ ≤ ζ + 8 nζ 2 κ 2 η • E sup f ∈F ω m (f ) • log 1 ζ .Minimizing over ζ yields the result.We now apply a Jensen's inequality and a Chernoff bound to get high probability control on ff ′ .Proof of Lemma 1. By Jensen's inequality and the definition of f , it holds thatP f -f ′ m > ρ = P   1 J J j=1 fj -f ′ j m > ρ   = P    1 J J j=1 fj -f ′ j 2 m > ρ 2    ≤ P   1 J J j=1 fj -f ′ j 2 m > ρ 2   .Finally, by Hoeffding's inequality [Wainwright, 2019 , Van Handel, 2014 ] and Lemma 7, we have thatδ ≥ P   1 J J j=1 fj -f ′ j 2 m > E f1 -f ′ 1 m + log 1 δ J   ≥ P   1 J J j=1 fj -f ′ j 2 m > 2 (n • η) 1/3 κ 2/3 • E sup f ∈F ω m (f ) 1/3 + log 1 δ J   .The result follows.In this section we prove Lemma 2 based on a technique borrowed from online learning and the analysis of Follow the Regularized Leader (FTRL) [Gordon, 1999, Cesa-Bianchi and Lugosi, 2006] .Proof of Lemma 2. Let L be as in (3) and L ′ be defined similarly but with D replaced by Rockafellar, 2015] . Thus, by convexity of F , it holds thatD ′ . Note that ∥•∥ 2 m is strongly convex with respect to ∥•∥ m [L( f ′ ) ≥ L( f ) + η 2 f -f ′ 2 m . On the other hand, L( f ′ ) = L ′ ( f ′ ) + L( f ′ ) -L ′ ( f ′ ) ≤ L ′ ( f ) + L( f ′ ) -L ′ ( f ′ ) = L( f ) + L( f ′ ) -L ′ ( f ′ ) + L ′ ( f ) -L( f ) ≤ L( f ) + 2 n .Combining this with the previous display and rearranging yields:η • f -f ′ 2 m ≤ 4 n .Rearranging again proves the result.C.3 Boosting Stability to Differential Privacy: Proofs from Section 4.2In this section, we analyze Algorithm 1 and prove that if f is stable in ∥•∥ m then applying the output perturbation yields a differentially private algorithm for standard choices of perturbation distribution Q. We also show that Algorithm 1 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 = N (0, 1) and let f = Perturb( f , Q, γ, D x ) be as in Algorithm 1. Then with probability at least 1 -β,EQUATION)EQUATION)Proof. By construction, it holds thatf -f -γ • ζ m ≤ f -f -γ • ζ m = γ • ∥ζ∥ m .By the triangle inequality, it holds thatf -f m ≤ f -f -γ • ζ m + γ • ∥ζ∥ m ≤ 2γ • ∥ζ∥ m .Thus it suffices to bound ∥ζ∥ m . Bounds on this quantity when ζ ∼ N (0, 1) or ζ ∼ Lap(1) are 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 privacy.Lemma 9. Let Perturb be as in Algorithm 1 and suppose that f , f ′ ∈ F. If D x = {Z 1 , . . . , Z m } ⊂ X is arbitrary and Q = N (0, 1), then for any δ > 0 and any measurable G ⊂ F, it holds thatP Perturb( f , Q, γ, D x ) ∈ G ≤ e m 2γ 2 1+γ• log( 1 δ ) •∥ f -f ′ ∥ m • P Perturb( f ′ , Q, γ, D x ) ∈ G + δ.On the other hand, if Q = Lap(1), thenP Perturb( f , Q, γ, D x ) ∈ G ≤ e m 3/2 γ •∥ f ′ -f ∥ m • P Perturb( f ′ , Q, γ, D x ) ∈ G Proof.To prove the first statement, let B δ denote the event that ∥ζ∥ m ≤ γ • log 1 δ and letp(u) = (2πγ 2 ) -m 2 • exp - 1 2γ 2 • ∥u∥ 2 mbe the density of γ • ζ. Note that P (B c δ ) ≤ δ by Lemma 8. We compute:P Perturb( f , Q, γ, D x ) ∈ G = u∈R m P Perturb( f , Q, γ, D x ) ∈ G|γ • ζ = u p(u)du = u∈R m I [B δ ] • P Perturb( f , Q, γ, D x ) ∈ G|γ • ζ = u p(u)du + u∈R m I [B c δ ] P Perturb( f , Q, γ, D x ) ∈ G|γ • ζ = u p(u)du ≤ δ + u∈R m I [B δ ] • P Perturb( f , Q, γ, D x ) ∈ G|γ • ζ = u p(u)du.For the second term, we compute:u∈R m I [B δ ] • P Perturb( f , Q, γ, D x ) ∈ G|γ • ζ = u p(u)du = u∈R m I [B δ ] • P Perturb( f ′ , Q, γ, D x ) ∈ G|γ • ζ = u + f ′ -f p(u)du = u∈R m I [B δ ] • P Perturb( f ′ , Q, γ, D x ) ∈ G|γ • ζ = u p(u) • e m 2γ 2 ∥u-f ′ ∥ 2 m -∥u-f ∥ 2 m du ≤ u∈R m I [B δ ] • P Perturb( f ′ , Q, γ, D x ) ∈ G|γ • ζ = u p(u) • e m 2γ 2 (1+∥u∥ m )•∥ f f ′ ∥ m du ≤ u∈R m I [B δ ] • P Perturb( f ′ , Q, γ, D x ) ∈ G|γ • ζ = u p(u) • e m 2γ 2 1+γ• log( 1 δ ) •∥ f -f ′ ∥ m du ≤ e m 2γ 2 1+γ• log( 1 δ ) •∥ f -f ′ ∥ m • P Perturb( f ′ , Q, γ, D x ) ∈ G .The first claim follows. To prove the second claim, we may repeat the same argument with Q = Lap(1) and δ = 0. Indeed, observe that ifq(u) = γ -m • e - ∥u∥ ℓ 1 γ then q(u + f ′ -f ) q(u) ≤ e ∥ f ′ -f ∥ ℓ 1 γ ≤ e m 3/2 γ •∥ f ′ -f ∥ m ,where the second inequality follows from Cauchy-Schwarz. Plugging this ratio into the above argument yields the second claim.In this section, we combine the results from Appendix C.3 with the stability results from Appendix C.6 to prove the differential privacy guarantees of Algorithm 2 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 a uniform lower bound on ∥f ∥ µ whereas Lemma 1 requires a uniform lower bound on ∥•∥ m . We apply a result from Appendix C.5 below to reconcile this discrepancy.Lemma 10 (Differential Privacy Guarantee for Algorithm 2). Suppose that F : X → [-1, 1] is a function class and let µ ∈ ∆(X ) such that ∥f ∥ 2 ≥ 2 3 for all f ∈ F. Suppose further that ℓ is bounded in [0, 1]. Let δ > 0 and suppose that m, γ, η, and J are such thatm 2γ 2 1 + γ • log 2 δ   4 (n • η) 1/3 • E sup f ∈F ω m (f ) + log 2 δ J   ≤ ε and C   log 2 (m) √ m • G m (F) + log log(m) + log 1 δ m   ≤ 1 6 .Then Algorithm 2 is (ε, δ)-differentially private for Q = N (0, 1).Proof. The result follows immediately by combining Lemmas 1 and 9 assuming we have a lower bound on κ. Indeed, by Lemma 12, it holds with probability at least 1 -δ that inf f ∈F ∥f ∥ m ≥ 1 4 . The result follows.We also have a guarantee for the more specialized algorithm.Lemma 11 (Differential Privacy Guarantee for Algorithm 3). Suppose that F : X → [-1, 1] is a convex function class and suppose that ℓ is convex and λ-Lipschitz in its first argument. If δ > 0 and m, γ, η are such thatm 2γ 2 1 + γ • log 2 δ • 2 √ η • n ≤ ε,then Algorithm 3 run with Q = N (0, 1) is (ε, δ)-differentially private. On the other hand, if δ = 0 andm 3/2 γ • 2 √ η • n ≤ ε, then Algorithm 3 run with Q = Lap(1) is ε-purely differentially private.Proof. This follows immediately by combining Lemmas 2 and 9.These results show that for any choice of ν, Algorithms 2 and 3 are differentially private. In the next section we show that if ν is σ-smooth with respect to µ, then the algorithms are also PAC learners with respect to ν.The previous sections have shown that Algorithms 2 and 3 are differentially private, which comprises the main difficulty of our analysis. Here we apply standard learning theoretic techniques to show that if ν is σ-smooth with respect to µ, then the algorithms are also PAC learners with respect to ν. This proof rests on three main results: first, we recall a norm comparison guarantee in high probability that allows us to relate ∥•∥ µ to ∥•∥ m ; second, we recall a classical uniform deviations bound for empirical processes; and third, we show that the perturbed empirical minimizer f has similar loss to the empirical minimizer f ERM of a loss function as long as the perturbation is not too large. Combining all three results will result in a PAC learning guarantee for Algorithms 2 and 3.We begin with the following lemma, which is a fairly standard result in learning theory. To state the lemma, we recall from Definition 6 that the worst-case Gaussian complexity is defined asG m (F) = sup Z1,...,Zm E sup f ∈F ω m (f ) ,We then have the following control on ∥•∥ µ in terms of ∥•∥ m :Lemma 12. Suppose that F : X → [-1, 1] is a function class and let µ ∈ ∆(X ) with Z 1 , . . . , Z m ∼ µ independent. Then for any β > 0, it holds with probability at least 1 -β that for all f, f ′ ∈ F, ∥f -f ′ ∥ µ ≤ 2 • ∥f -f ′ ∥ m + C     log 2 (m) √ m • G m (F) + log log(m) + log 1 β m     .Because the proof is relatively standard [Bousquet, 2002 , Rakhlin et al., 2017] , but also a technical digression, we defer it to Appendix C.7 and continue with our arguments.Our second lemma is a standard uniform deviation bound for empirical processes: Lemma 13. Let F : X → [-1, 1] be a bounded function class and let D denote a data set of (X i , Y i ) ∼ ν be independent. Then for any β > 0, with probability at least 1 -β, it holds thatsup f ∈F |L D (f ) -L(f )| ≤ 6 √ n • E sup f ∈F ω n (f ) + 2 log 1 β n .Proof. This follows immediately from combining Wainwright [2019, Theorem 4.10] with Van Handel [2014, Lemma 7.4 ].Finally, we show that the perturbed empirical minimizer f has similar loss to the empirical minimizer f ERM of a loss function as long as the perturbation is not too large. Lemma 14. Let F : X → [-1, 1] denote a function class and let ℓ : [-1, 1] ×2 → [0, 1] denote a bounded loss function convex in the first argument and let D denote a dataset of size n. For η > 0, let f be as in Line 5 of Algorithm 2. Then for any β > 0, with probability at least 1 -β,EQUATIONIf instead we let f be as in Line 3 of Algorithm 3, then almost surely,EQUATIONProof. Applying Lemma 5 and noting that f , f ERM ∈ F and applying Lemma 13 yieldsL( f ) -inf f ∈F L(f ) ≤ 12 √ n • E sup f ∈F ω n (f ) + 2 • 2 log 1 β n + sup f,f ′ ∈F R(f ) -R(f ′ ).The second statement follows immediately by noting that 0 ≤ ∥f ∥ m ≤ 1 for all f ∈ F and lettingR(f ) = η • ∥f ∥ m .For the first statement, we note that by convexity of ℓ, it holds thatL D ( f ) ≤ 1 J • J j=1 L D ( fj ) ≤ L D (f ERM ) + η J • J j=1 sup f ∈F ω (j) (f ) -inf f ′ ∈F ω (j) (f ′ ).To prove the second statement, we observe that by the Borell-Tsirelson-Ibragimov-Sudakov inequality (see, e.g., Wainwright [2019, Example 2.30] ) and the fact that E ω(j) m (f ) 2 ≤ 1 for all f ∈ F, that for all j ∈ [J], with probability at least 1 -β, it holds that sup f ∈F ω (j) m (f ) ≤ E sup f ∈F ω (j) m (f ) + 2 log 1 β .Applying symmetry and a Chernoff bound tells us that with probability at least 1 -β it holds that1 J • J j=1 sup f ∈F ω (j) m (f ) -inf f ∈F ω (j) m ≤ 2 • E sup f ∈F ω (j) m (f ) + 2 • log 1 β J .The result follows.Before continuing, we prove Lemma 5 from Section 4:Proof of Lemma 5. For an arbitrary regularizer R :F → R, if we let f ∈ argmin f ∈F L D (f ) + R(f ), then by definition L D ( f ) + R( f ) ≤ L D (f ERM ) + R(f ERM ) and so L D ( f ) ≤ L D (f ERM ) + sup f,f ′ ∈F R(f ) -R(f ′ ),wheref ERM ∈ argmin f ∈F L D (f ) is the ERM.Combining these three lemmas yields the following PAC learning guarantee for Algorithm 2. Lemma 15 (PAC Learning Guarantee for Algorithm 2). Suppose that F : X → [-1, 1] is a function class and ℓ : [-1, 1] ×2 → [0, 1] is a bounded loss function λ-Lipschitz and convex in the first argument. Let µ ∈ ∆(X ) and suppose that ν is σ-smooth with respect to µ. For any β > 0 it holds with probability at least 1 -β thatL( f ) -inf f ∈F L(f ) ≤ 12 √ n • E sup f ∈F ω n (f ) + 2 • log 1 β n + 2η •     E sup f ∈F ω (j) m (f ) + log 1 β J     + 4λγ σ • log 1 β + Cλ σ •     log 3 (m) √ m • G m (F) + log log(m) + log 1 β m     .for f returned by Algorithm 2 with Q = N (0, 1) and D a dataset of size n.Proof. We compute:L( f ) = L( f ) + L( f ) -L( f ) ≤ L( f ) + λ • f -f ν X ≤ L( f ) + λ σ • f -f µ ,where the first inequality uses Jensen's and the second usesthe fact that ν is σ-smooth. We now observe that by Lemma 8, with probability at least 1 -β,f -f µ ≤ 2γ • log 1 β .Combining this with Lemma 14 yieldsL( f ) -inf f ∈F L(f ) ≤ 12 √ n • E sup f ∈F ω n (f ) + 2 • log 1 β n + 2η •     E sup f ∈F ω (j) m (f ) + log 1 β J     + 4λγ σ • log 1 β + λ σ f -f µ -f -f m .Applying Lemma 12 concludes the result.Similarly, we have a result for Algorithm 3; note that while convexity of ℓ is required to demonstrate that Algorithm 2 is a 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 3 is a PAC learner while it is necessary for the privacy guarantee in Lemma 11.Lemma 16 (PAC Guarantees for Algorithm 3). Suppose thatF : X → [-1, 1] is a convex function class and ℓ : [-1, 1] ×2 → [0, 1] is a bounded loss function λ-Lipschitz in the first argument. Let µ ∈ ∆(X )and suppose that ν is σ-smooth with respect to µ. For any β > 0 it holds with probability at least 1 -β thatL( f ) -inf f ∈F L(f ) ≤ 12 √ n • E sup f ∈F ω n (f ) + 2 • log 1 β n + η + 4λγ σ • log 1 β + Cλ σ •     log 3 (m) √ m • G m (F) + log log(m) + log 1 β m     .for f returned by Algorithm 3 with Q = N (0, 1) and D a dataset of size n. Similarly, if we replace Q = Lap(1), then with probability at least 1 -β,L( f ) -inf f ∈F L(f ) ≤ 12 √ n • E sup f ∈F ω n (f ) + 2 • log 1 β n + η + 4λγ σ • log 1 β • √ m + Cλ σ •     log 3 (m) √ m • G m (F) + log log(m) + log 1 β m     .Proof. The proof of the first statement is identical to that of Lemma 15 with the exception of replacing ( 11) 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 to conclude the proofs of the main theorems is to tune the hyperparameters and control the complexity terms. We do this in the next section.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 a more detailed version of Theorem 2:Theorem 6. Suppose that F : X → [-1, 1] is a function class such that G m (F) = O √ d for some d ∈ N and ℓ : [-1, 1] ×2 → [0, 1] is convex and λ-Lipschitz in the first argument. If we let Q = N (0, 1) in Algorithm 1 and set γ = Θ     σα λ • log 1 β     , η = Θ( α √ d ), m = Θ   d ∨ log 1 β σ 2 α 2 • λ 2   J = Ω   d log 1 β α 2 ∨ λ 8 d 2 log 4 1 β log 1 δ σ 8 α 8 ε 2 ∨ d 2 λ 6 log 3 1 β log 2 1 δ σ 6 α 6 ε 2   and n = Ω   λ 12 d 5 log 6 1 β σ 12 ε 3 α 14 ∨ d 5 λ 9 log 9/2 1 β log 3/2 1 δ σ 9 ε 3 α 10   ,then Algorithm 2 is (ε, δ)-differentially private and an (α, β)-PAC learner with respect to any ν that is σ-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 3:Theorem 7. Suppose that F : X → [-1, 1] is a convex function class such that G m (F) = O √ d for some d ∈ N and ℓ : [-1, 1] ×2 → [0, 1] is convex and λ-Lipschitz in the first argument. If we let Q = N (0, 1) in Algorithm 1 and set γ = Θ     σα λ • log 1 β     , η = Θ(α), m = Θ   d ∨ log 1 β σ 2 α 2 • λ 2   and n = Ω   λ 5 d log 2 1 β εσ 4 α 5 ∨ λ 4 d log 3/2 1 β log 1/2 1 δ εσ 3 α 4   ,then Algorithm 3 is (ε, δ)-differentially private and an (α, β)-PAC learner with respect to any ν that is σ-smooth with respect to µ.On the other hand, if we set Q = Lap(1) in Algorithm 1 and setγ = Θ     α 2 σ λ 2 • d log 1 β ∧ log 1 β     , η = Θ(α), m = Θ   d ∨ log 1 β σ 2 α 2 • λ 2   and n = L λ 6 σ 5 εα 6 • d 2 log 1 β ∨ log 5/2 1 βthen Algorithm 3 is ε-purely differentially private and an (α, β)-PAC learner with respect to any σ-smooth ν.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.As a final remark, we note that Lemmas 15 and 16 are both phrased entirely in terms of G m (F) and thus apply to function classes F such that G m (F) = ω(1). Such non-donsker [Wainwright, 2019 , Van Handel, 2014] classes can still be learned in the PAC framework, albeit with slower rates. Indeed, it is immediate from the above results that as long as G m (F) = o( √ m), then appropriately tuning the hyperparamters results Algorithms 2 and 3 being differentially private PAC learners with respect to ν. It is well-known that (with our scaling) G m (F) = o( √ m) is a 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.Replacing F by F -F = {f -f ′ |f, f ′ ∈ F} and noting that the uniform bound only increases by a factor of 2 and the Rademacher complexity increases at most by a factor of 2, we observe that it suffices to prove the result for f ′ = 0. We thus instead prove the notationally simpler claim that with probability at least 1 -β, for all f ∈ F,∥f ∥ µ ≤ 2 • ∥f ∥ m + C   log 3 (m) √ m • G m (F) + log log(m) + log 1 β m  We first note that by Bousquet [2002, Theorem 6 .1], with probability at least 1 -β, it holds that for all f ∈ F, ∥f ∥EQUATIONfor some universal constant C, withEQUATION)Taking square roots on both sides of (13) shows that it suffices to upper bound r. 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 a function class and ∥•∥ m,∞ the the L ∞ norm on the empirical measure on Z 1 , . . . , Z m ∈ X , i.e., ∥f ∥ m,∞ = max i∈[m] |f (Z i )|. We say that f 1 , . . . , f N is an ε-cover with respect to ∥•∥ m,∞ if for all f ∈ F there is some f j such that ∥f -f j ∥ m,∞ ≤ ε. We then let N m,∞ (F, ε) denote the size of the smallest ε-cover of F with respect to ∥•∥ m,∞ .The notion of a 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 m,∞ (F, u) denote the covering number of the function class F with respect to ∥•∥ m,∞ at scale u > 0. We then claim that r can be upper bounded by any r satisfyingEQUATION)We also claim that for any r > G m (F), the following holds:EQUATIONfor some universal constant C. We now suppose that ( 15) and ( 16) hold and setr = Cm -1/2 • log 3 (m) • G m (F).Then it is immediate that r is a member of the set in ( 14).We now prove the two claims.Proof that a solution to (15) is an upper bound on r. By a standard Dudley Chaining argument [Van Handel, 2014 , Wainwright, 2019] , it holds thatEQUATIONLetting f 1 , . . . , f M ∈ F ∩ ∥f ∥ 2 m ≤ r 2 be a proper u-cover of F ∩ ∥f ∥ 2 m ≤ r 2 with respect to ∥•∥ m,∞ at scale s ≤ r and π : F → {f i } be projection to the cover, we havef 2 -π(f ) 2 2 m ≤ s 2 • ∥f + π(f )∥ 2 m ≤ 4s 2 r 2 by factoring f 2 -π(f ) 2 = (f -π(f ))(f + π(f )). In particular, N m,2 (F 2 ∩ ∥f ∥ 2 m ≤ r 2 , 2ur) ≤ N m,∞ (F ∩ F 2 ∩ ∥f ∥ 2 m ≤ r 2 , u) ≤ N m,∞ (F, u),where we used the fact that a proper covering at scale ε has size bounded by a covering at scale ε/2 by the triangle inequaltiy. Substituting into (17) and rescaling yields the claim.Proof that (16) holds. This proof goes through fat shattering numbers, a complexity measure taking a function class and a scale u > 0 and returns fat(F, u) ∈ N [ Bartlett et al., 1994] . We do not need the full definition of fat shattering numbers and defer to [Bartlett et al., 1994 , Srebro et al., 2010 , Rudelson and Vershynin, 2006] for details. We only need the following two properties. First, for any u > 0, it holds by Rudelson and Vershynin [2006] thatEQUATIONSecond, by Srebro et al. [2010, Lemma A.2] , for all r > m -1/2 • G m (F),r 2 • fat(F, r) ≤ 4 • G m (F) 2 .(19) Plugging ( 18) into the left hand side of ( 16) and then applying (19) concludes the proof of the claim.In this section, we provide full proofs for the guarantees of Algorithm 4. In Section D.1, we describe the concept of universal identification sets and the result of Neel et al. [2019] which plays a crucial role in the privacy analysis of our algorithm. In Section D.2, we formally prove Lemma 6 which is the technical lemma used for the proof of differential privacy based on Neel et al. [2019] . We then continue in Section D.3 by applying standard learning theoretic techniques to demonstrate that our algorithm is an accurate classifier.In this section, we formally define universal identification sets and informally describe the algorithm used in Neel et al. [2019] . Intuitively, a universal identification set captures the combinatorial property of a 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 ⊆ X is a universal identification set for a hypothesis class F if for all pairs of functions f, f ′ in the hypothesis class F, there is a x ∈ U such that:f (x) ̸ = f ′ (x).Additionally, if |U| = m, we say that F has a universal identification set of size m.Assuming the existence of a universal identification set for the function class F of size m denoted by U = {U 1 , . . . , U m }, Neel et al. [2019] showed that the following algorithm(called RSPM) is an εpure differentially private and (α, β)-accurate algorithm.Algorithm 5: RSPM 1: Input ERM oracle ERM, dataset D = {(X i , Y i ) | 1 ≤ i ≤ n},L ξ,D,U (f ) = n i=1 ℓ(f (X i ), Y i ) + m i=1 ξ i • ℓ(f (U i ), Ỹi ). 5: Get f = ERM(F, L ξ,D,U ).RSPM roughly simulates "Report-Noisy-Min" (Dwork et al. [2014] ) attempting to output a function that minimizes a perturbed estimate, where the perturbation is sampled from a Laplace distribution. A straight forward implementation of "Report-Noisy-Min" 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 evaluations via an augmented dataset. The proof of privacy thus exploits the structure of the universal identification set.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.In this section, we prove that Algorithm 4 is differentially private. A notion that we will need is that of a projection of a hypothesis class onto a set of points from the domain.Definition 10. (Projection) Given a hypothesis class F ⊆ Y |X | and a subset Z = {z 1 , . . . z m } of the feature space X , we define the projection of F onto Z to be F| Z = {(f (z 1 ), . . . , f (z m )) : f ∈ F}.In the following sections, we will interchangeably think of the projection of a hypothesis class onto a set of points Z as a set of functions on Z or as a set of vectors in Y |Z| . By construction, F| Z has the property that any two distinct functions f ̸ = f ′ ∈ F| Z must disagree on at least one point z ∈ Z. We encapsulate this as the following lemma.Lemma 17. Let F be a hypothesis class and let Z = {z 1 , . . . , z m } be a set of points in the instance space X . Then, for all f ̸ = f ′ ∈ F| Z , there exists z ∈ Z such that f (z) ̸ = f ′ (z).Remark 2. This property is analogous to the notion of a 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 F| Z .We first provide an informal sketch of the proof of privacy. In the later sections, we formalize these ideas. Let f ∈ F be any arbitrary function and let D, D ′ be any pair of neighbouring datasets. We show that P(RRSPM(D) = f ) ≤ e ε P(RRSPM(D ′ ) = f ). By the definition of the projection, there is some f ∈ F | Dx that is consistent with the labelling of the selected function f . P(ERM(F, L ξ,D, D ) = f ) ≤ e ε P(ERM(F, L ξ,D ′ , D ) = f ) since privacy for f follows from the post-processing property of differential privacy.We now provide with a proof sketch for the main technical lemma showing that the privacy is preserved over the projected function class. Optimizing a loss function perturbed by Laplace-weighted examples implicitly tries to implement "Report-Noisy-Min" algorithm outputting a 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 D is a universal identification 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 to D ′ . This intuition is made precise in Lemma 18. L ξ,D, D (f ) = n i=1 ℓ(f (X i ), Y i ) + m i=1 ξ i • ℓ(f (Z i ), Ỹi ). Let ξ = {ξ 1 , . . . , ξ m } such that ξ i ∼ Lap(2m/ε). Given a fixed f D ∈ F| Dx , define a mapping Ψ f D (ξ) : R m → R m on noise vectors as follows: 1. if ℓ(f D (Z i ), Ỹi ) = 1, Ψ f D (ξ) i = ξ i -2 2. if ℓ(f D (Z i ), Ỹi ) = 0, Ψ f D (ξ) i = ξ i + 2 Equivalently, Ψ f D (ξ) i = ξ i + 2(1 -2ℓ(f D (Z i ), Ỹi )). Let ξ ∈ E f D , D, D where f D ∈ ERM(F| Dx , L ξ,D, D ). Then Ψ f D (ξ) ∈ E(f D , D ′ , D). Proof. Let Ψ f D (ξ) = ξ ′ = (ξ ′ 1 , . . . ξ ′ m ). Our goal is to show that for every f ∈ F| Dx such that f ̸ = f D , we have L ξ ′ ,D ′ , D (f ) > L ξ ′ ,D ′ , D (f D ).First, recall that by our assumption for all f ∈ F| Dx , we haveEQUATION) We now argue that L ξ ′ ,D ′ , D (f )-L ξ ′ ,D ′ , D (f D ) is strictly positive for all f ∈ F| Dx such that f D ̸ = f .To see this we calculate,L ξ ′ ,D ′ , D (f ) -L ξ ′ ,D ′ , D (f D ) = (X,Y )∈D ′ ℓ(f (X), Y ) + m i=1 ξ ′ i • ℓ(f (Z i ), Ỹi ) - (X,Y )∈D ′ ℓ(f D (X), Y ) - m i=1 ξ ′ i • ℓ(f D (Z i ), Ỹi ) ≥ L ξ,D, D (f ) -1 + m i=1 ξ ′ i • ℓ(f (Z i ), Ỹi ) -ξ i • ℓ(f (Z i ), Ỹi ) -L ξ,D, D (f D ) -1 - m i=1 ξ ′ i • ℓ(f D (Z i ), Ỹi ) + ξ i • ℓ(f D (Z i ), Ỹi ) > -2 + m i=1 (ξ ′ i -ξ i ) ℓ(f (Z i ), Ỹi )) -ℓ(f D (Z i ), Ỹi ) ,where the second inequality follows from the fact that D and D ′ differ in only one entry and ℓ is 1sensitive. The last equation follows from statement 20.We know from Lemma 17 that there exists aZ ∈ D such that f (Z) ̸ = f D (Z). Recall that ξ ′ i = ξ i + 2(1 -2ℓ(f D (Z i ), Ỹi )). By construction, each term is non-negative. Therefore, m i=1 (ξ ′ i -ξ i ) ℓ(f (Z i ), Ỹi )) -ℓ(f D (Z i ), Ỹi ) > 2.To wrap up, we can boundL ξ ′ ,D ′ , D (f ) -L ξ ′ ,D ′ , D (f D ) > 0. This proves that Ψ f D (ξ) ∈ E(f D , D ′ , D).Lemma 19 (Laplace shift). Let ξ = {ξ 1 , . . . , ξ m } such that ξ i ∼ Lap(2m/ε). Fix some noise realization r ∈ R m and fix a hypothesis in the projection set f ∈ F| Dx . Then,P(ξ = r) ≤ e ε P(ξ = Ψ f (r)),where Ψ f (ξ) i = ξ i + 2(1 -2ℓ(f (Z i ), Ỹi )) as defined in Lemma 18.Proof. Let i ∈ [m] be any index and let r ∈ R m . Since ξ i ∼ Lap(2m/ε), we knowEQUATIONFor any t, t ′ ∈ R such that |t -t ′ | ≤ 2, we getP(ξ i = t ′ ) ≤ exp(ε/m)P(ξ i = t) Since for all i ∈ [d], |Ψ f (r) i -r i | ≤ 2, we get P(ξ = Ψ f (r)) P(ξ = r) = m i=1 P(ξ i = Ψ f (r) i ) P(ξ i = r i ) ≤ m i=1 exp(ε/m) = exp(ε).Our proof of privacy also makes use of the following lemma, which says that minimizers are unique with probability 1 [Neel et al., 2019, Lemma 4 ]. Lemma 20. Let D = ( Dx , Dy ) ∈ (X × {0, 1}) m . Consider F| Dx , where F| Dx is the projection of F on Dx . For every dataset D, there is a subset B ⊆ R m such that:• P(ξ ∈ B) = 0 and• On the restricted domain R m \ B, there is a unique minimizer f ∈ arg min f ∈F | Dx L ξ,D, D (f ).Using standard results about Laplace perturbations stated in Lemma 19 and Lemma 20 and using the perturbation coupling bound in 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, D ′ be arbitrary datasets containing n points each. Let D = ( Dx , Dy ) ∈ (X × {0, 1}) m . Then,P(ERM(F| Dx , L ξ,D, D ) = f ) ≤ e ε P(ERM(F| Dx , L ξ,D ′ , D ) = f ).Proof. We calculate,P(ERM(F| Dx , L ξ,D, D ) = f ) = P(ξ ∈ E(f, D, D)) = R m P(ξ)1(ξ ∈ E(f, D, D))dξ = R m \B P(ξ)1(ξ ∈ E(f, D, D))dξ B has 0 measure by Lemma 20 ≤ R m \B P(ξ)1(Ψ f (ξ) ∈ E(f, D ′ , D))dξ Lemma 18 ≤ R m \B e ε P(Ψ f (ξ))1(Ψ f (ξ) ∈ E(f, D ′ , D))dξ Lemma 19 ≤ R m \Ψ f (B) e ε P(ξ)1(ξ ∈ E(f, D ′ , D)) ∂Ψ f ∂ξ dξ Change of variables ξ → Ψ f (ξ) = R m e ε P(ξ)1(ξ ∈ E(f, D ′ , D))dξ Ψ f (B) has 0 measure, ∂Ψ f ∂ξ = 1 = e ε P(ξ ∈ E(f, D ′ , D)) = e ε P(ERM(F| Dx , L ξ,D ′ , D ) = f ).Theorem 8. Algorithm 4 is ε-pure differentially private.Proof. Let D and D ′ be any neighbouring datasets. Fix any function f ∈ F. We now show thatP(RRSPM(D) = f ) ≤ e ε P(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 a unique function in the projection say,f ∈ F| Dx such that f (Z i ) = f (Z i ) for all i ∈ [m].Using Lemma 21, we know thatP(ERM(F| Dx , L ξ,D, D ) = f ) ≤ e ε P(ERM(F| Dx , L ξ,D ′ , D, Dy ) = f ).As defined in the algorithm, letL(f ) = m i=1 ℓ(f (Z i ), f (Z i )).From the definition of L, it follows that f ∈ arg min f ∈F L(f ). Following the post-processing guarantee of differential privacy, it is easy to see that P(RRSPM(D) = f ) ≤ e ε P(RRSPM(D ′ ) = f ).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 ν i.e. f * ∈ arg min f ∈F L ν (f ). Let f denote the output hypothesis of our algorithm. We show that the loss of f is close to f * with respect to the data generating distribution ν.As in the algorithm description, let f be the function that minimizes the perturbed loss. Our algorithm outputs f whose labelling is consistent with f on the public dataset Dx . Since Dx is sampled from the base distribution, it follows from VC theorem that f and f are close under the base distribution µ. We show in Lemma 22 that f and f are close under ν by leveraging that ν x is a σ-smooth distribution. Using standard results about Laplace perturbations, we show that f ′ is close to 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 ν.We now state the VC theorem below which we use in our analysis. Theorem 9. Let D = {(X 1 , Y 1 ), . . . , (X n , Y n )} where for all i ∈ [n], (X i , Y i ) ∈ X × {0, 1} are sampled from a fixed distribution ν.Let L D (f ) = 1 n |{i : f (X i ) ̸ = Y i }| and let L ν (f ) = E (X,Y )∼ν [1(f (X) ̸ = Y ]. If the function class F has V C dimension d then, P sup f ∈F |L D (f ) -L ν (f )| ≤ O d + log(1/β) m ≥ 1 -β.In particular if f * ∈ arg min . First we show that | L( f )X∼µ Y = f (X) -L( f ) X∼µ Y = f (X)| ≤ 2α ′ with probability at least 1 -β. Consider the dataset D = {(X 1 , f (X 1 ), . . . , (X m , f (X m ))} we minimize over and output f . Using Theorem 9 we know that,P   | L( f ) X∼µ Y = f (X) -L( f ) X∼µ Y = f (X) | ≤ 2α ′ + |L D ( f ) -L D ( f )|    ≥ 1 -β.Since L( f ) We now show that P X∼νx ( f (x) ̸ = f (x)) ≤ 2α ′ /σ with probability at least 1 -β.P X∼νx ( f (x) ̸ = f (x)) = E X ∼ ν x [1( f (x) ̸ = f (x))] = X∈X P(ν x = X)1( f (x) ̸ = f (x)) ≤ 1 σ X∈X P(µ = X)1( f (x) ̸ = f (x)) Since dν x dµ ≤ 1 σ = 1 σ E X ∼ µ[1( f (x) ̸ = f (x))] = 1 σ P X∼µ ( f (x) ̸ = f (x)) ≤ 2α σ Using Eq 21Having shown that with probability at least 1 -β,EQUATIONwe now prove that with probability at least 1 -β,| L( f ) X∼νx Y ∼νy|X -L( f ) X∼νx Y ∼νy|X | ≤ 2α ′ /σ.which is equivalent to the theorem statement. Using the triangle inequality we get| L( f ) X∼νx Y ∼νy|X -L( f ) X∼νx Y ∼νy|X | ≤ E X∼νx P Y ∼νy|X ( f (X) ̸ = Y ) -P Y ∼νy|X ( f (X) ̸ = Y ) = E X∼νx [1( f (X) ̸ = f (X))] = 2α ′ /σ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 1 and the last equation follows from Equation 22.Substituting the value of α ′ proves that with probability 1 -β, 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. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Does not apply.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: Does not apply.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.In fact, this condition can be further relaxed to only assuming the two distributions have a bounded fdivergence.These divergences include the well-known KL divergence and Renyi divergence. For a comprehensive introduction to f -divergences, seePolyanskiy and Wu [2022+]., where z ⋆ is a distinguished point such that f (z ⋆ ) = 1 for all f ∈ F; note that this process deflates σ at most by a factor of 3 while ensuring the lower bound on the norm of f . Replacing µ by µ then suffices to ensure that Theorem 2 holds.m 
 
 Appendix:  


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

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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
1. 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?
2. 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?
3. 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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: See weaknesses.
limitations: limitations: I don't identify significant limitations.
paper_summary: paper_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. 

In 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).
strength_weakness: strength_weakness: 1. The resulting sample complexity, though being polynomial, is much higher than previous work. 
2. 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.
questions: 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)?
2. 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: limitations: Discussed.
paper_summary: paper_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.

The 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.

The 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.
strength_weakness: strength_weakness: No weaknesses to discuss from my side.
questions: 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?
- 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: limitations: No concerns from me.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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:
(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?
(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?
(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.
(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?
questions: questions: Please refer to the Weaknesses above.
limitations: limitations: Yes.

Comments: comment: Thanks for the response. I will maintain my evaluation.
Thank you for the response to my questions. I will maintain the positive score.
Thank you for your response, which has addressed my questions. I decide to maintain my positive score.