Oracle-Efficient Differentially Private Learning with Public Data

We thank the reviewer for their positive review and their helpful comments! Please see responses to individual questions below.

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?

We would like to distinguish between strong convexity of the loss function and strong convexity with respect to a parameter belonging to some subset of Euclidean space. Note that taking a gradient and running gradient descent does not make sense in the context of our paper as we are working with arbitrary function classes that do not necessarily live in a space where it is meaningful to take gradients. The loss function is a function on real numbers and thus strong convexity does make sense. By way of analogy, if we are training a neural network with square loss, the loss function itself may be strongly convex with respect to the output of the neural network, but is certainly not convex with respect to the parameters.

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?

Gaussian complexity is a standard notion of complexity in learning theory and is equivalent to Rademacher complexity up to polylogarithmic factors. There are many known relationships between these notions of complexity and VC dimension, but Gaussian complexity is strictly more general as VC dimension requires binary-valued function classes. To the best of our knowledge, our work is the first to produce oracle-efficient algorithms in the semi-private setting that are provably effective in this level of generality.

There is a lack of discussion on sample complexity. For instance, Theorem 2 requires $n \geq \Omega(1/\alpha^{14})$. It is helpful to discuss the origin of this term.

We agree that the precise polynomial in the sample complexity guarantee for our most general algorithm is higher than what is information theoretically optimal in the absence of computational constraints. Certainly in an information theoretic sense sample complexity can be improved simply by constructing an $\epsilon$-net on the function class using the public data as we discuss in Lines 39-46, although the resulting algorithm is impractical. On the other hand, our guarantees are the first to hold for oracle-efficient algorithms in this generality. We leave as an interesting open question the challenge of designing oracle-efficient algorithms with improved sample complexity.

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?

By works such as [1] and [2], we know that private learning in the absence of public data is not always possible. To be more precise, any class with infinite Littlestone dimension but finite VC dimension (such as that of linear thresholds in Euclidean space) is PAC learnable but not privately learnable. These classes are privately learnable with public data however, and our paper provides oracle-efficient algorithms for learning them.

[1] Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite littlestone dimension. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 852–860. ACM, 2019.

[2] Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learning of threshold functions. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 634–649. IEEE, 2015.

We thank the reviewer for their positive review and their helpful comments! Please see responses to individual questions below.

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?

Thank you for pointing out this confusing passage. Here the $d$ is supposed to be the VC dimension. We agree that this would be substantially clearer if we replaced it by the Gaussian complexity and will do this in the camera ready version.

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?

This is a good question. The specific example raised is not technically covered by the remark in line 149 because the relevant $f$-divergences might not be bounded between exponential and gaussian tails. Note that the smoothness assumption is only used in ensuring that the perturbed ERMs remain good learners on the marginal distribution over private features and thus any assumption that ensures this will lead to a bound on how well our algorithms learn. In the case of the $\delta$ fraction not having bounded Radon Nikodym derivative, as long as the loss function is uniformly bounded, minor modification to our analysis ensures that we simply pay a n additive term of $\delta$ in the loss. We emphasize that the smoothness assumption is not required to ensure privacy of the algorithm and thus our privacy guarantees hold unconditionally.

We thank the reviewer for their positive review and their helpful comments! Please see responses to individual questions below.

The resulting sample complexity, though being polynomial, is much higher than previous work.

We agree that the precise polynomial in the sample complexity guarantee for our most general algorithm is higher than what is information theoretically optimal in the absence of computational constraints. On the other hand, our guarantees are the first to hold for oracle-efficient algorithms in this generality. We leave as an interesting open question the challenge of designing oracle-efficient algorithms with improved sample complexity.

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.

This is an excellent point that we will clarify in the camera ready version. We note that our analysis in the case of Theorem 2 (corresponding to Algorithm 2) can be modified slightly to handle the case of approximate minimizers. Indeed, the learning guarantees proceed virtually unchanged. For the privacy guarantees, observe that privacy follows directly from stability of the first stage estimator $\overline f$ in the respective algorithms. By inspecting the proof of Theorem 5 we may see that a similar conclusion holds for approximate minimizers. A quantitatively weaker version of this result that allows for such approximate minimizers can be found in [1]. In the case of the other two algorithms studied, we believe that similar minor modifications to the current analysis will yield similarly graceful weakening of our privacy guarantees as the additive error in the approximate ERM oracle increases.

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)?

This is a good question. Note that our analysis really shows that any non-private learner undergoing a similar perturbation as we describe will remain a good learner after applying Algorithm 1, so the question is really if such learners can also be made private. Here the answer depends on whether the non-private learner in question is stable with respect to the $L^2$ on the empirical measure of the public data; if so then our analysis guarantees privacy, but if not then we cannot ensure privacy.

On line 64, page 2, it is said that "Prior work of Bassily et al.[2018] gave an oracle-efficient algorithm in this setting with somewhat better sample complexity". Can you elaborate more on this? It looks like their work only guarantees an error of $c \cdot \textrm{OPT} + \alpha$ in the agnostic setting, which is weaker than the result obtained in this paper.

Thank you for this point; you are correct and we will update our discussion accordingly.

[1] Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as easy as statistical learning. In Conference on Learning Theory, pages 1716–1786. PMLR, 2022.

We thank the reviewer for their positive review and their helpful comments! Please see responses to individual questions below.

Could you discuss whether it's possible to improve this dependence on $\sigma$.

We believe that it is likely that the precise polynomial dependence on problem parameters can be improved. Certainly in an information theoretic sense this is possible simply by constructing an $\epsilon$-net on the function class using the public data as we discuss in Lines 39-46, although the resulting algorithm is impractical. We leave as an interesting open question the challenge of designing oracle-efficient algorithms with improved sample complexity.

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.

Regarding the necessity of assuming a smooth data distribution, at the price of quantitatively worse rates, we can replace the notion of smoothness (uniformly bounded Radon NIkodym derivative) with the weaker notion of bounded $f$-divergence. This point was addressed in [1] in the context of smoothed online learning and similar techniques could likely be applied here. Please see the discussion in Lines 149-152 for the relevant remark. Unfortunately, due to the lower bounds in works such as [2,3], one cannot remove such an assumption altogether.

[1] Adam Block and Yury Polyanskiy. The sample complexity of approximate rejection sampling with applications to smoothed online learning. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 228–273. PMLR, 12–15 Jul 2023.

[2] Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite littlestone dimension. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 852–860. ACM, 2019.

[3] Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learning of threshold functions. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 634–649. IEEE, 2015.

We thank the reviewer for their positive review and their helpful comments! Please see responses to individual questions below.

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?

Note that adding the gaussian process serves to ensure privacy and does not help (and could potentially hurt) the learning. Indeed, our learning analysis is concerned with ensuring that our algorithm does not output a hypothesis that is significantly worse than simply running ERM. The reason to add the perturbation is to ensure privacy. As discussed in Lines 204-207, our privacy analysis follows by ensuring the first step is stable in $L^2$ of the empirical measure on the public data (Lemma 1) and then boosting that stability guarantee into a privacy guarantee (Lemma 3); if we did not have public data and were to only use ERM, then such an approach is meaningless. We could still ensure label privacy in this way by dong the same procedure and treating the features as public, unlabelled data, but this would still leak information about these features, thereby precluding a privacy guarantee.

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?

See previous answer.

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?

Two papers that discuss this are [1] and [2], cited in our work. Note that any class with infinite Littlestone dimension but finite VC dimension (such as that of linear thresholds in Euclidean space) is PAC learnable but not privately learnable. These classes are privately learnable with public data however, and our paper provides oracle-efficient algorithms for learning them.

[1] Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite littlestone dimension. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 852–860. ACM, 2019.

[2] Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learning of threshold functions. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 634–649. IEEE, 2015.