Privacy at Interpolation: Precise Analysis for Random and NTK Features

We thank the reviewer for the careful analysis of our work. We address all comments below.

---

(1) The lower bound of eq (12) is inadequate to characterize the attacker’s power

While it is true that the bound in (12) is not necessarily tight (because of the variance of $f(z_1^m, \theta^*)$), it still provides a worst-case estimate of the recovery power of the attacker. Specifically, if the generalization error is small, then provably the loss of the attacker cannot be better than random guessing.

To address the comment of the reviewer, in the revision we also provide another bound that does not neglect the variance of $f(z_1^m, \theta^*)$. By assuming that both the labels and the predictor are balanced ($\mathbb E_{x_1}[g_1]=0$ and $\mathbb E_x[f(z_1^m, \theta^*_{-1})]=0$), we have

$$\mathbb E_x[\mathcal L]\ge \mathbb E_x[\mathcal L_0] +\gamma_\varphi^2\mathcal R_{Z_{-1}}-2\gamma_\varphi\sqrt{\mathcal R_{Z_{-1}}}\sqrt{{\rm Var}(g_1)},$$

where $\mathcal L_0=\mathbb E_{x_1, y_1}[(f(z_1^m, \theta^*_{-1})-g_1)^2]$ denotes the loss of an attacker that has no information available on the true label $g_1$. We note that, when the generalization error is small, the RHS is close to $\mathbb E_x[\mathcal L_0] -2\gamma_\varphi\sqrt{\mathcal R_{Z_{-1}}}\sqrt{{\rm Var}(g_1)}$, which is similar to the lower bound in eq (12). We have added this new bound at the end of Section 4 and deferred its proof to Appendix F.

---

(2) Would the authors be willing to recast the paper as a study of stability rather than privacy?

Yes, we agree with the reviewer and have revised accordingly. In particular:

• We have removed “Privacy” from the title, replacing it with “Stability” and “Information Retrieval”.
• We have removed the sentence “Our analysis provides the first theoretical privacy guarantees for ERM algorithms interpolating the data".
• We have rephrased the sentence “The combination of Theorem 5.4 and Lemma 4.1 shows the proportionality between stability and privacy” as “The combination of Theorem 5.4 and (10) shows that the more the algorithm is stable (and, therefore, capable of generalizing), the smaller is the statistical dependency between the query of the attacker and the true label”.
• We have rephrased the sentence “We provide a quantitative characterization of the accuracy of a family of powerful information recovery attacks” as “We study the accuracy of a family of powerful information recovery attacks for models trained via empirical risk minimization, in the interpolation regime”.
• Several other changes in this direction have been made to the abstract, introduction, discussion after the main theorem statements, and conclusions.

All these changes are in red color to facilitate the reviewing process.

We would like to highlight that these modifications only concern how to interpret our technical results. The technical content of the paper remains unchanged. The only exception is the additional bound on the loss of the attacker discussed above.

---

(3) Can the authors carefully review work on stability in linear regression? In particular connections to [1] and related work.

We thank the reviewer for pointing the related work [1], which describes the role of the Hat matrix to estimate the influence of a single data point in linear regression.

We remark that the Hat matrix $H := X (X^\top X)^{-1} X^\top$ can be defined when $X^\top X$ is invertible, which requires (in our notation) $p \leq N$. As we consider the overparameterized regime ($p > N$), this condition cannot be satisfied.

In the underparameterized regime, following 5.5 in [1], we get (using our notation)

$f(z_1, \theta^*) - f(z_1, \theta^*_{-1}) = h_1 r_1 / (1 - h_1),$

where $h_1$ is the first element in the diagonal of $H$, and $r_1$ is the residual on the first sample, i.e.,

$r_1 = g_1 - f(z_1, \theta^*).$

At interpolation, $r_1 = 0$ and the leave-one-out stability has to be derived alternatively.

We agree with the reviewer that our analysis leverages projectors having a similar form, such as $P_{\Phi} = \Phi^\top (\Phi \Phi^\top)^{-1} \Phi$. However, Lemma 4.1, which uses $P_{\Phi_{-1}}^\perp$ to describe the leave-one-out stability of overparameterized generalized linear models, is – to the best of our knowledge – novel.

In the revision, we mention the related work [1] in Section 2, and then we discuss it more in detail right after the statement of Lemma 4.1.

(Question 3) I'm probably missing something but if the feature alignment $F_{\rm RF}$ is in $[-1, 1]$ and $0<\gamma_{\rm RF}<1$, the results in 5.4 doesn't seem to convey too much information? The result basically says these 2 values are a constant away from each other.

The role of Theorem 5.4 is to prove that $\mathcal F(z_1, z_1^m)$ concentrates to a constant bounded away from 0. In principle, the value of $\mathcal F(z_1, z_1^m)$ could converge to 0. In this case, the recovery attack wouldn’t allow the attacker to retrieve any information, as suggested by (12).

In Theorem 5.4 and 6.3, we show that, for RF and NTK models respectively, a strictly positive geometric overlap ($\alpha > 0$) guarantees a strictly positive feature alignment. This in turn guarantees the attacker the possibility to recover information about the original data, as long as the generalization error is not 0, as discussed in (10).

We clarify this point in the new discussion paragraph at the end of Section 6 of the revision.

We thank the Reviewer for the positive evaluation of our work. We address all comments below.

---

(Weaknesses) The paper would probably benefit from having a section that describes and discusses the results of the experiments. [...] I also think some discussion on the results of Theorem 5.4 and Theorem 6.3 are needed.

As suggested, we have included the following paragraph at the end of Section 6, providing more intuition both on our experimental and theoretical results:

“As (12) suggests, if the value of $\mathcal F_\varphi(z_1, z_1^m)$ converges to 0, no information can be recovered by the attacker. However, our Theorems 5.4 and 6.3 show that, for RF and NTK models respectively, a strictly positive geometric overlap ($\alpha > 0$) guarantees a strictly positive feature alignment. This in turn guarantees the attacker the possibility to recover information about the original data, as long as the generalization error is not 0, as discussed in (10). Our experiments both on synthetic and real datasets confirm these findings. First, in Figures 3, 4 and 5, we see a decrease in the attack accuracy as generalization improves, as discussed in Section 4. This behaviour is displayed also by neural networks, as shown in Figure 1. Additionally, our experiments confirm the characterizations of $\gamma_{\rm RF}$ ($\gamma_{\rm NTK}$) in terms of $\alpha$ and the Hermite coefficients of the activation (its derivative). The expected dependence is displayed also on real datasets (see Figure 5), where functions with higher order Hermite coefficients lead to models that are more resistant to the attack.”

To make space for it, as suggested by the reviewer, we have moved the sketch of the proof for NTK regression at the beginning of Appendix E.

---

(Question 1) In the experiments, the activation function that is composed of the Hermite polynomial is only used for experiments with synthetic data, is it possible to run that activation on real datasets? Also, how did the author create the synthetic data?

Yes, we can verify the dependence of the attack accuracy on real data. As suggested by the reviewer, we have repeated the experiments for NTK regression on MNIST and CIFAR-10 with two different activation functions, $\phi_2$ and $\phi_8$, so that their derivatives are respectively $\phi_2’ = h_0 + h_1$ and $\phi_8’ = h_0 + h_7$, where $h_i$ denotes the $i$-th Hermite polynomial.

The second activation puts more weight on higher order Hermite coefficients and, according to our analysis, it should lead to models that are more resistant to the recovery attack. This is verified in Figure 5 of the revision (see Section 6), which allows to appreciate a trade-off between test accuracy and attack accuracy given by the choice of the activation function, for both datasets.

Previous experiments were performed on synthetic datasets, where the samples are taken i.i.d. from a standard Gaussian distribution and the ground truth label is set to be $g_i = sign(u^\top x_i)$, for a fixed vector $u \in \mathbb R^{d_x}$. We refer to the caption of Figure 3 for these details.

---

(Question 2) I think the experiments right now mainly support that generalization improves privacy but it's quite hard to see where the feature alignments part comes into play here. Maybe the authors can try varying the level of alignment or $\alpha=d_y/d to see how it affects the attack's efficiency.

We would like to thank the reviewer for the question and the helpful suggestion. First of all, let us point out that the role of $\alpha$ and of the Hermite coefficients of the activation can be appreciated in the second subplot of Figures 3 and 4: $\alpha=1/2$ (red lines) leads to a more successful attack than $\alpha=1/4$ (black lines); an activation function with dominant low-order Hermite coefficients leads to a more successful attack; neither $\alpha$ nor the specific choice of the activation influence much the test accuracy. This experimentally confirms the findings of our main theoretical results.

In Figure 5 of the revision (also discussed above), the effect of the activation on the accuracy of the attack is displayed for MNIST and CIFAR-10.

Finally, to address the reviewer’s comment, we have performed an additional experiment with synthetic data in which we plot the test and attack accuracies as a function of $\alpha$. The results are presented in Figure 6 contained in Appendix G: the test accuracy does not depend on $\alpha$, while the accuracy of the attack monotonically grows with $\alpha$. This is again in agreement with the results of Theorem 5.4 and 6.3.

We thank the reviewer for the comments on our work. We have fixed the minor issues and typos in the revised version, and we address the weaknesses below.

---

(1) My main problem with the paper is that it seems to be an extremely limited scenario: linear model with squared error and invertible kernel. Why is this kind of model of use in the current era? The attack also seems quite specific. A narrow example is given (a person in a compromising environment) but do the conclusions of your method apply to more general forms of realistic attacks? How?

The study of generalized linear models in the over-parameterized regime constitutes a well-established line of research in deep learning theory. In particular, the behavior of RF and NTK models in this regime ($N = o(p)$) has been the object of extensive study e.g. in the context of optimization [1, 2, 3], generalization [4, 5] and robustness [6, 7].

While it is true that state-of-the-art deep learning models may be far from the NTK regime, the theoretical analysis of such objects still provides useful insights also in practice [8, 9]. Furthermore, even if our formal attack description requires a clear distinction between useful information $x$ and background noise $y$, our analysis provides a solid theoretical foundation to the family of attacks in which the attacker has partial knowledge about the training samples, and aims to retrieve information about the rest.

This is particularly relevant in the context of hallucinations in language models. As mentioned at the end of Section 3, sensitive information ($x$) about an individual ($y$) could be stored in a textual dataset. The attacker could guess that $y$ was mentioned in the training dataset, and can try to recover $x$ by querying the model with the prompt

“The address of $y$ is…”

These experiments have been considered e.g. for question-answering tasks [10]. Specifically, in [10], the authors mask the tokens containing the information which is relevant to solve the task, and they verify that the trained model can still hallucinate the correct answer on the “masked” training samples (see Table 1 of [10]).

While the precise formulation of more realistic problems might differ, our approach offers a solid ground to mathematically formulate different instances of this general problem in machine learning.

---

(2) Second, I feel that differential privacy has been generally accepted as the gold standard for privacy, and there are carefully reasoned arguments for this choice. You use the word "privacy guarantee". Why should we be interested in this new notion of privacy? Could you relate your ideas more to DP?

We agree with the reviewer that our work does not provide any formal privacy guarantee according to the formalism of Differential Privacy (DP). To better represent our contribution, we have modified what before we were addressing as “privacy guarantees” to “resistance to the attack” in the revised version of our work. In this regard, as suggested by Reviewer 4po4, we have also modified the first part of the title, replacing “Privacy at Interpolation” with “Stability and Information Retrieval”, as well as several sentences in the abstract, introduction, conclusions and right after the statements of the main theorems. We believe that these modifications better frame our technical contributions. We consider the analysis of DP training methods using the formalism developed in this work as an exciting avenue for future research.

Let us conclude by addressing directly the question of the reviewer: “Why should we be interested in this new notion of privacy?” The problem of information retrieval in over-parameterized ML models is pressing in practice. Our analysis aims to characterize those situations in which DP training is not deployed, but the application would still benefit from being resistant to black-box information retrieval attacks. This is prominent in the case of LLMs [10, 11] (see also our response to the previous point) and in individual recognition in computer vision (see also Section 3 of the paper).

(3) The intro says "the accuracy of the attack grows with generalization error". If this is the main point of the paper, it seems, if not trivial, not especially surprising. A model that can perfectly fit the data and has high generalization error clearly can easily memorize arbitrary points, which means privacy is low and the attack should be easy.

The reviewer is right in pointing out that a model that can perfectly fit the data and has high generalization error could be simply memorizing arbitrary points. This, in fact, also suggests that the attack should be easy, and it is in line with the empirical evidence in [10], where overfitting is seen to correlate with the success of the recovery attack. The results of our work are a formal mathematical description of this phenomenon, through the analysis of the concentration of the feature alignment to a strictly positive quantity, in the settings of RF and NTK regression.

As described by Theorems 5.4 and 6.3 and shown in Figures 3-5, our analysis also links the power of the attack to the specific choice of the model and its activation function. This connection (exemplified in the second subplot of Figures 3 and 4, as well as in Figure 5 added in the revision) is highly non-intuitive, and it comes purely from our analysis.

To conclude, as mentioned in Section 7, characterizing the concentration of the feature alignment of more complex feature maps would allow to compare different models and establish which of those are the most resistant to recovery attacks, thus allowing a principled design of privacy-preserving ML models.

---

[1] Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of over-parameterized shallow neural networks. IEEE Transactions on Information Theory, 65(2):742–769, 2018.

[2] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via overparameterization. ICML, 2019.

[3] Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. ICML, 2019.

[4] Andrea Montanari and Yiqiao Zhong. The interpolation phase transition in neural networks: Memorization and generalization under lazy training. The Annals of Statistics, 2022.

[5] Zhichao Wang, Yizhe Zhu. Overparameterized random feature regression with nearly orthogonal data. AISTATS, 2023

[6] Zhenyu Zhu, Fanghui Liu, Grigorios Chrysos, and Volkan Cevher. Robustness in deep learning: The good (width), the bad (depth), and the ugly (initialization). NeurIPS, 2022.

[7] Elvis Dohmatob. Fundamental tradeoffs between memorization and robustness in random features and neural tangent regimes. arXiv preprint arXiv:2106.02630, 2022.

[8] Noel Loo, Ramin Hasani, Alexander Amini, and Daniela Rus. Evolution of neural tangent kernels under benign and adversarial training. NeurIPS, 2022.

[9] Nikolaos Tsilivis and Julia Kempe. What can the neural tangent kernel tell us about adversarial robustness? NeurIPS, 2022.

[10] Simone Bombari, Alessandro Achille, Zijian Wang, Yu-Xiang Wang, Yusheng Xie, Kunwar Yashraj, Singh, Srikar Appalaraju, Vijay Mahadevan, and Stefano Soatto. Towards differential relational privacy and its use in question answering. arXiv preprint arXiv:2203.16701, 2022.

[11] Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom B. Brown, Dawn Xiaodong Song, Ulfar Erlingsson, Alina Oprea, and Colin Raffel. Extracting training data from large language models. In USENIX Conference on Security Symposium, 2021.

Thank you for the detailed rebuttal, and for amending the paper so that it doesn't confusingly conflate stability with privacy.

I still feel that the scenario is limited, and the conclusion is not too surprising. But I acknowledge that there is a significant research community interested in this sort of theory. In the spirit of not letting the review too strongly reflect my own biases, I will raise the score to 6, noting that my confidence is still only 2. If the other two, more confident, reviewers are willing to argue for acceptance, then I will not object.