Noise-Aware Differentially Private Regression via Meta-Learning

The delta value of 10^-3 is large compared to the literature. Setting it at 1/N puts it into the well-known privacy violating regime where one can return a random record with no noise, violating the privacy of someone with probability 1.

This would be true if we considered any $(\epsilon, \delta)$-DP mechanism. However, for our specific mechanism, we can always adjust $\delta$, and obtain a different $\epsilon$, which will be finite, so we will not be in the privacy violating regime you describe. Making this adjustment would only change the $\epsilon$ values in our plots for DPConvCNP. We would also need to make the same adjustment for DP-SVGP, which will not be identical, since DP-SVGP is based on DP-SGD. However, we expect these differences to be small, so the adjustment would not change the conclusions from our results. To illustrate this, if we had used $\delta = 10^{-5}$ instead, which is the recommended value by NIST, we would adjust the DPConvCNP $\epsilon$ values we use according to the following table:

However, please also note that we have conducted additional experiments, attached to the pdf in the global response, which should help put your concerns about the value of $\\delta$ to rest.

The paper seems to be taking too much credit for minor things, like using Gaussian DP as a drop-in replacement in the work of Hall et al. (literally taking a theorem that was meant as a drop-in replacement of prior formulas and using it as a drop-in replacement for those formulas). That is not a contribution.

We believe our formulation in the Introduction and the rest of the paper gives appropriate credit to prior work, but are happy to hear if you can suggest a better formulation. We also point out that both reviewers Eg3Y and AqSn found this contribution to be meaningful and listed it as a strength of our work.

The most important issue for last. I am not convinced that the algorithm is differentially private at the claimed parameter levels.

We break down this paragraph and answer each of the points below.

my understanding is that nothing changes except that wherever r is needed, a noisy version is used instead.

This is correct, but we also add clipping to the signal channel to bound sensitivity.

The sensitivity calculation detailed in the appendix appears to be incorrect…

The only properties of the kernel we use in the sensitivity calculation are that $0 \leq k(x, y) \leq 1$ and $k(x, y) = k(y, x)$, which are looking at point evaluations, not integrals or sums. The sums in Eq. (19) and (27) disappear because the two datasets in the supremum only differ in one datapoint, so all but one term of the sums are zero.

The transition from the functional form that the functional mechanism releases to the evaluations on the discretised point set follows from Proposition 5 of Hall et al. (2013). We will add a corollary to Theorem 4.2 that clarifies this.

We would be happy to improve the notation if you could point out any specific part that is unclear.

The privacy properties should be provable from first principles… I would like to see a detailed privacy proof [...] that explicitly uses the discretized point set…

Here is a proof that uses the Gaussian mechanism on the discretised points directly. Let $k(x_1, x_2) = \exp(-\frac{(x_1 - x_2)^2}{\lambda})$, and let the discretised points be arbitrarily chosen $x_1, \dotsc, x_m$. Let’s look at the density channel $r_d$ first. DPConvCNP computes the vector $[r_d(x_1), \dotsc, r_d(x_m)]$, and adds Gaussian noise with covariance $\sigma_d^2 M$, where $M$ is an $m\times m$ matrix with $M_{ij} = k(x_i, x_j)$. By Lemma A.4, it suffices to find the upper bound $\Delta$ in Eq. (14) for the matrix $M$ and the vector $r_d$ taking the role of the function $f$ of the lemma. By Proposition 8 of Hall et al. (2013), the sensitivity in Eq. (14) is bounded by the RKHS sensitivity we look at in Appendix A.4, which gives the privacy guarantee we claim. The privacy of the signal channel is proven in the same way, and releasing both of them is a composition.

For more challenging problems, such as text and images, how would one create simulated data so that DPConvCNP would be competitive?

These domains are likely too high-dimensional for the ConvCNP model to be applied. More concretely, while ConvCNPs have been applied to image-based data before (see e.g. Gordon et al. (2020)) these applications have been confined to image in-painting rather than, for example, image classification. In image in-painting with meta-learning, the context set is a single partially observed image consisting of context pixels. The ConvCNP can be applied to this setting, but preserving data-point (i.e. pixel) privacy is meaningless. In image classification with meta-learning, the context set consists of several images, to which the ConvCNP cannot be readily applied. On the other hand, some amortized adaptation models (see Requeima et al. (2019)) have been developed, however these involve entirely different architectures and representations to the ConvCNP, so the functional mechanism does not apply. Overall, while very interesting and important, tackling higher dimensional data is well beyond the scope of this paper.

Reference:

James Requeima, Jonathan Gordon, John Bronskill, Sebastian Nowozin, Richard E. Turner, Fast and flexible multi-task classification using conditional neural adaptive processes, NeurIPS 2019.

Thank you for your feedback. We hope we have settled your concerns regarding the validity of our theory. Provided our comments and amendments have satisfied your concerns, we would like to invite you to consider increasing your score.

Q1 : My main question/concern with the work is how important is leveraging a powerful hyperparameter tuning library (like BayesOpt from Optuna) to adjust hyperparameters for the empirical performance of the proposed method DPConvSet?

We only use Optuna and BayesOpt on the DP-SVGP baseline. We did not perform any BayesOpt tuning on any hyperparameters of the DPConvCNP.

Instead, rather than performing BayesOpt, the DPConvCNP “tunes” the parameters (but no hyperparameters such as model size) of the backbone network as well as the NNs for parameterising the DP clipping threshold $C$ and noise weight $t$ (Section 4.3) by performing gradient descent on synthetic data. We found our procedure to work well out-of-the-box and did not make any further efforts to optimize the DPConvCNP.

Q1.5 : Related in Q1, in section 4.3, you include privacy parameters in the meta training of DPConvCNP (as far as I can tell) by re-parameterizing. Can you explain how this maintains the (epsilon, delta)-DP guarantee if the iterative meta-learning procedure is conditioned on prior trainings?

During meta-training, DPConvCNP only uses simulated data, so meta-training does not have any impact on the privacy of the real data. We include the noise addition, clipping and other privacy-related computations during meta-training in order to make the model learn the same task it will do during meta-testing, either for single privacy parameters or over a range of privacy parameters. In turn, at meta-testing, the DPSetConv ensures that the data representation of the private data is $(\\epsilon, \\delta)$-DP.

Recent work [...] touches on the importance of private tuning. Can the authors discuss the delta between untuned and tuned versions of their algorithms, to be more “honest” about the effects of hyperparameter tuning on both their baseline and their method?

Both the DPConvCNP and the DP-SVGP are trained on simulated data without any privacy cost, so the work on private hyperparameter tuning is not relevant to our setting.

Q2: It seems like a missed opportunity to discuss the shortcomings of standard supervised learners on small datasets, even a simple standard private regression [...]. Perhaps comparisons between standard learners and meta learners is not worth it in the data scenarios you explore?

Standard DP supervised learning algorithms would likely not work very well in our settings. For example, linear regression, which seems to be the only regression algorithm in the library you linked, would clearly need some nonlinear features to have any chance of working in our settings. Designing appropriate nonlinear features that work well with DP would be a non-trivial effort, to the point that we would effectively be designing a new baseline. In non-private settings, GPs are the state-of-the-art in the low-data regime, so we think the DP-SVGP is the most reasonable baseline we could use. We will further explain our choice of baseline in the revised version.

Q3: Can the authors justify their choice of privacy hyperparameters in the text? [...] Adding results for this wider range [$\\epsilon < 1$] of privacy parameters would strengthen the contribution.

As you acknowledge in your question, our privacy parameter settings are standard in the literature. Relatively few papers go below $\\epsilon = 1.$ However, following your advice we have run some further experiments for $\\epsilon < 1,$ as well as smaller $\\delta.$ We have attached these results in the additional rebuttal pdf of the "global response." There, we observe that the DPConvCNP performs well even in such stricter privacy settings, given enough data.

Thank you for your valuable feedback. If our comments and amendments have satisfied your concerns, we would like to invite you to consider increasing your score.

I am not familiar with the neural process either. [...] how it is different from a normal neural network. [...] how it is able to produce well-calibrated prediction, and how this is evaluated in the experimental results?

Here we give a brief answer to your question following the standard exposition from the literature (see e.g. Garnelo et al. (2018)). While a neural process is parameterised by neural networks (the encoder and the decoder) it differs from standard supervised neural network models in two main ways: the architecture and the training method.

In terms of architecture, all neural processes involve an encoder-decoder architecture where (a) the encoder is designed to be invariant with respect to permutations of the context points in $D^{(c)},$ i.e. permuting order of the entries in the dataset $D^{(c)}$ leaves the output representation $r$ invariant; and (b) the decoder is constructed such that, given the representation $r,$, the predictions for each target $y^{(t)}_i$ depend only on the corresponding inputs $x^{(t)}_i$ and no other variable (see Eeq. (1)). These design choices are important for ensuring Kolmogorov’s extension theorem is satisfied, in order to define a valid stochastic predictive process. We won’t delve further into this, but refer you to Kolmogorov’s extension theorem in Oksendal (2013) if you are further interested. For our purposes here, we can summarise this by saying that NPs have a particular architecture, chosen to satisfy Kolmogorov’s extension theorem.

In terms of training, a neural process is again substantially different from a simple supervised neural network. A supervised network is trained on a single supervised dataset, and as such it is prone to overfitting. By contrast a neural process is trained on a (possibly infinite) collection of datasets. During meta-training (see Aalgorithm 1), the neural process is trained to make predictions for an unseen target set $D^{(t)}$ given an observed context set $D^{(c)}.$ Because $D^{(t)}$ are unseen, the model must learn to produce not just an accurate mean prediction, but also a sensible confidence interval for these.

Our experimental results validate that the neural process predictions are well calibrated both qualitatively (e.g. see the calibrated confidence intervals in Ffigures S.2 to S.5 in the appendix) as well as quantitatively: in Figure 6 we see that the DPConvCNP performance approaches that of the perfectly calibrated oracle predictors, which can only happen if the DPConvCNP predictions are also well-calibrated. We stress that well-calibrated predictions have been demonstrated extensively in the neural process literature (see e.g. confidence intervals for the ConvCNP in Gordon et al. (2020)), and our results suggest the DPConvCNP also produces well-calibrated predictions.

B. Oksendal, Stochastic differential equations: an introduction with applications (2013)

I am not familiar with the meta-learning framework (and related works), so it's likely I misunderstood some parts and had confusion about the meta-testing part.

Meta-learning has two phases, meta-training and meta-testing. You should view meta-testing as analogous to supervised learning: the input is a dataset, and the output is a function (model) $f$ that can make predictions at arbitrary inputs. Meta-training is the process of learning an algorithm which, when given a new dataset, produces a function (model) that can be queried at arbitrary inputs to make predictions. In the neural process literature, this is achieved using the encoder-decoder architecture of Eq. (1). With this understanding let us address your points below. We will also clarify these points in the revised paper.

Can you explain why adding noise to the test stage is necessary?

Yes, here is why adding noise and clipping are necessary in the test stage. During the test stage, the DPConvCNP takes a previously unseen private dataset as its context set $D^{(c)}.$ (This would be the training data set in regular supervised learning.) Then, the DPConvCNP converts $D^{(c)}$ into a representation $r$ which is “published.” Once the representation is published, it can be passed through the rest of the architecture (the decoder) together with arbitrary test (target) inputs $x^{(t)}$ to make predictions for the corresponding test (target) outputs $y^{(t)}.$ If we do not apply noise and clipping in the test stage, then publishing $r$ would have no guarantees at all, and that could completely breach user privacy. By clipping and adding noise, we ensure that $r$ can be published with DP guarantees, and that arbitrarily many predictions (at arbitrary inputs) can be made using the decoder, without incurring any further privacy cost.

We will add a corollary to Theorem 4.2 which states that Algorithm 2 with the DPSetConv encoder is DP with respect to meta-testing context set, in order to clarify precisely which part of the algorithm is DP, to better address this point.

[...] noise is injected in both training and test stages, where the authors explained that it accounts for mismatch between training and test. This paradigm does not look optimal to me.

From our reply above, we hope it is clear why adding noise is necessary at test-time in order to preserve privacy. Let us now address meta-training time.

At meta-training, we do not strictly need to apply noise or clipping, because the meta-training data are synthetic, so training the model on them does not incur a privacy cost. For example, we can train a standard ConvCNP model on synthetic data, and then replace its SetConv encoder with a DPSetConv encoder. The $r$ published from this model would still be $(\\epsilon, \\delta)$-DP at test time. However, applying noise and clipping changes the statistics of the representation $r$ in a way that this model is not trained for, so its predictions are catastrophically poor. Our observation is that we can address this issue by simply training the model with noise and clipping in place (i.e. with the DPSetConv) at meta-train time, teaching the model to account for these operations, and eliminating the mismatch. We will clarify which data is simulated and which is real in Algorithms 1 and 2.

It looks to me that if we need to add noise in the test stage, we need to accumulate the total privacy budget epsilon as more test data are coming in. Is it true?

In our case, we assume that the meta-test context dataset is available all at once and does not change over time. This assumption is analogous to a supervised learning setting, where the training dataset (on which the supervised algorithm is applied) is fixed at the start. Just as in supervised learning, we can still make an arbitrary number of predictions at arbitrary locations, without any further privacy cost.

It would be interesting to consider the scenario where more test data come in one by one or in batches, but this is beyond the scope of our current work.

For the conditional NP, I don't see where is the conditional input, or what does the conditional mean here?

The term “conditional” neural process was introduced by Garnelo et al. (2018) to capture the fact that this meta-learning model models the conditional predictive distribution $p(y^{(t)} | x^{(t)}, D^{(c)}).$ We emphasize that we did not introduce this term, but rather the original authors of the CNP.

In Figure 4, I wonder how these lines are drawn. Do you use any analytical forms to calculate, or some libraries/packages to compute? Also, are they converted into the same (epsilon, delta)-DP notion? Because the epsilon in different DP notions are not the same (although they share the same notation).

Yes, all of the noise levels in Figure 4 are calculated via closed form expressions and, if necessary, lightweight numerical solution routines. All of them use $(\epsilon, \delta)$-DP from Definiton 3.1

In more detail, the classical line uses Theorem 3.7. The GDP line uses Definition 3.2 to convert the $(\epsilon, \delta)$-bound into a GDP $\mu$-bound by numerically solving $\mu$ from Eq. (5), and finds $\sigma$ with Theorem 4.1. For the RDP line, we get an RDP guarantee from Corollary 2 of Jiang et al. (2023), which we convert to $(\epsilon, \delta)$ with Proposition 3 of Jiang et al. (2023). RDP has the $\alpha$ parameter that can be freely chosen, so we optimise $\alpha$ to minimise $\epsilon$ for a given $\sigma$, and finally solve for $\sigma$, which gives the plotted values. Both the optimisation and finding $\sigma$ can be done analytically in this case.

I am not familiar with the neural process either. [...]

Due to the limited character count of the rebuttal, we have answered this in a separate comment below.

Thank you for your valuable feedback. If our comments and amendments have satisfied your concerns, we would like to invite you to consider increasing your score.