# Differential Privacy Mechanisms in Neural Tangent Kernel Regression

Jiuxiang Gu<EMAIL_ADDRESS>Adobe Research. Yingyu Liang<EMAIL_ADDRESS>The
University of Hong Kong<EMAIL_ADDRESS>University of Wisconsin-Madison.
Zhizhou Sha<EMAIL_ADDRESS>Tsinghua University Zhenmei Shi
<EMAIL_ADDRESS>University of Wisconsin-Madison. Zhao Song
<EMAIL_ADDRESS>Adobe Research.

Training data privacy is a fundamental problem in modern Artificial
Intelligence (AI) applications, such as face recognition, recommendation
systems, language generation, and many others, as it may contain sensitive
user information related to legal issues. To fundamentally understand how
privacy mechanisms work in AI applications, we study differential privacy (DP)
in the Neural Tangent Kernel (NTK) regression setting, where DP is one of the
most powerful tools for measuring privacy under statistical learning, and NTK
is one of the most popular analysis frameworks for studying the learning
mechanisms of deep neural networks. In our work, we can show provable
guarantees for both differential privacy and test accuracy of our NTK
regression. Furthermore, we conduct experiments on the basic image
classification dataset CIFAR10 to demonstrate that NTK regression can preserve
good accuracy under a modest privacy budget, supporting the validity of our
analysis. To our knowledge, this is the first work to provide a DP guarantee
for NTK regression.

###### Contents

  1. 1 Introduction
  2. 2 Related Work
  3. 3 Preliminary
    1. 3.1 Notations
    2. 3.2 Neural Tangent Kernel
    3. 3.3 NTK Regression
  4. 4 Main Results
    1. 4.1 Key Concepts
    2. 4.2 Gaussian Sampling Mechanism
    3. 4.3 Utility of Gaussian Sampling Mechanism
    4. 4.4 Main Theorem
  5. 5 Technical Overview
    1. 5.1 Sensitivity of Continuous Quadratic NTK
    2. 5.2 Bridge the gap between Continuous and Discrete Quadratic NTKs
    3. 5.3 Sensitivity of PSD Matrix
    4. 5.4 Privacy Guarantees for Private NTK Regression
    5. 5.5 Utility Guarantees for Private NTK Regression
  6. 6 Experiments
    1. 6.1 Experiment Setup
    2. 6.2 Main Results
  7. 7 Discussion
  8. 8 Conclusion
  9. A Basic Tools
    1. A.1 Probability Tools
    2. A.2 Basic Algebra Tools
    3. A.3 Differential Privacy Tools
  10. B Positive Semi-Definite Matrices
  11. C Gaussian Sampling Mechanism
  12. D Sensitivity of Neural Tangent Kernel
    1. D.1 Sensitivity of Continuous Quadratic NTK
    2. D.2 Sensitivity of Discrete Quadratic NTK
    3. D.3 Sensitivity for Privacy Guarantees
  13. E Utility Guarantees

##  1 Introduction

Artificial Intelligence (AI) applications are widely employed in daily human
life and product activities, such as face recognition [98], recommendation
systems [131], chat-based language generation [1], and many more. These
applications intrinsically run deep-learning models that are trained on broad
datasets, where many contain sensitive user information, e.g., a company
trains a model on its user information to provide better-customized service.
Consequently, there is a problem with user privacy information data leakage
[69], which affects the AI company’s reputation [67] and may cause severe
legal issues [123, 63]. Therefore, preserving the privacy of training data
becomes a fundamental problem in deep learning.

Differential Privacy (DP) [31] was proposed to measure privacy rigorously and
has been widely studied in many traditional statistical problems. Recently,
many brilliant works have applied this powerful tool to machine learning
settings. One line of work studies the classic machine learning task, e.g.,
[100] studies DP under the Support Vector Machine (SVM) model. However, these
settings are still far from practical deep neural networks nowadays. The other
line of work studies the DP in deep learning training, e.g., DP-SGD [3]
provides DP guarantees for the Stochastic Gradient Descent (SGD) training
algorithm. The issue in DP training is that the trade-off between privacy
guarantees and test accuracy will worsen as training time increases. DP
training may not be practical in today’s training paradigm, i.e., pre-training
with an adaptation in foundation models [15], as the per-training stage may
involve billions of training steps.

To bridge the gap between practical deep learning models and practical
differential privacy guarantees, in this work, we study DP Mechanisms in
Neural Tangent Kernel [62] (NTK) Regression. NTK is one of the most standard
analysis frameworks for studying optimization and generalization in over-
parameterized deep neural networks (DNN). NTK can connect the DNN training by
SGD to kernel methods by using the kernel induced by gradient around the
neural networks’ initialization. Consequently, the DNN optimization can be
viewed as NTK regression, and it retains almost the same generalization
ability [5] as kernel regression even though the DNN is in an over-
parameterization regime.

Our contributions. In this work, we use the “Gaussian Sampling Mechanism” [55]
to add a positive semi-definite noise matrix to the neural tangent kernel
matrix, and then we can show provable guarantees for both differential privacy
and test accuracy of our NTK regression, i.e.,

######  Theorem 1.1 (Main result, informal version of Theorem 4.10).

Under proper conditions, for any test data $x$, we have NTK-regression is
$(\epsilon,\delta)$-DP and has good utility under a large probability.

Furthermore, we undertake experiments using the fundamental image
classification dataset CIFAR10 to illustrate that NTK regression can maintain
high accuracy with a modest privacy budget (see Figure 1 in Section 6.2). This
effectively validates our analysis. To the best of our knowledge, this
research is the first effort to offer a differential privacy (DP) guarantee
for NTK regression.

#### Roadmap

Our paper is organized as follows. In Section 2, we provide an overview of
Differential Privacy, the Neural Tangent Kernel (NTK), and its applications
within the context of Differential Privacy. Section 3 introduces the
definitions of both continuous and discrete versions of the Neural Tangent
Kernel, along with the definition of NTK Regression. In Section 4, we provide
definitions pertinent to the Gaussian Sampling Mechanism and explain how we
modify this mechanism to render NTK Regression private. An overview of the
techniques employed in this paper is discussed in Section 5. In Section 6, we
conduct experiments on the CIFAR-10 dataset, demonstrating that our algorithm
performs effectively with a small privacy budget. In Section 7, we offer a
thorough examination of the benefits and drawbacks of introducing noise into
the kernel or gradient, along with an exploration of the proper way for adding
noise to NTK Regression. Finally, we conclude in Section 8.

##  2 Related Work

#### Differential Privacy Guarantee Analysis.

Since the introduction of the concept of differential privacy (DP) by [30], it
has emerged as a crucial standard for privacy protection, both theoretically
and empirically [33, 76, 125, 97, 122]. DP offers a robust and measurable
privacy definition that supports the design of algorithms with specific
guarantees of privacy and accuracy [36, 6, 72, 60, 44, 16, 18, 37, 25, 107,
56, 91, 92, 64, 73, 40, 41, 71, 27, 19, 28, 39, 51, 46, 75, 45, 35, 113, 32,
119, 110, 55] and many more. Furthermore, innovative mechanisms have been
developed beyond conventional Laplace, Gaussian, and Exponential methods [31].
For instance, the truncated Laplace mechanism [43] has been demonstrated to
achieve the tightest lower and upper bounds on minimum noise amplitude and
power among all $(\epsilon,\delta)$-DP distributions.

#### Neural Tangent Kernel.

Numerous recent studies suggest that the analysis of optimization and
generalization in deep learning should be closely integrated. NTK employs the
first-order Taylor expansion to examine highly over-parameterized neural
networks, from their initial states, as seen in references like [70, 87, 126,
62, 34, 12, 128, 95, 83, 93, 121, 111, 29, 11, 26, 85, 94, 4, 24, 65, 10, 22,
96, 20, 23, 127, 54, 80, 17, 129, 77, 108, 90, 86, 21, 52, 99, 112, 53, 115,
109] and others. Consequently, the optimization of neural networks can be
approached as a convex problem. The NTK technique has gained widespread
application in various contexts, including preprocessing analysis [114, 58, 8,
102, 106, 105, 53], federated learning [81], LoRA adaptation for large
language models [59, 120, 103, 48, 49, 88], and estimating scoring functions
in diffusion models [57, 117, 47, 50].

#### Differential Privacy in Machine Learning.

Differential privacy (DP) is a thriving and potent method with extensive
applications in the field of private machine learning [68]. This includes its
use during the pre-training stage [3, 97], the adaptation stage [13, 101, 74,
124, 82, 104], and the inference stage [38, 79]. Recently, [42, 84, 130] has
integrated DP into large language models, and [118] applied DP into diffusion
models. DP has also been widely used in classical machine learning and data
structure settings, e.g., near-neighbor counting [6], permutation hashing
[72], BDD tree [60], counting tree [44], Jaccard similarity [2] and many more.

##  3 Preliminary

In this section, we will first introduce some basic notations in Section 3.1.
Then, we will introduce the definitions of the neural tangent kernel, both
discrete and continuous versions in Section 3.2, the definitions and key
component of NTK regression in Section 3.3.

###  3.1 Notations

For any positive $n$, let $[n]$ denote the set $\\{1,2,\cdots,n\\}$. For any
vector $z\in\mathbb{R}^{n}$. We define the $\ell_{2}$-norm of a vector $z$ as
$\|z\|_{2}:=(\sum_{i=1}^{n}z_{i}^{2})^{1/2}$, the $\ell_{1}$-norm as
$\|z\|_{1}:=\sum_{i=1}^{n}|z_{i}|$, the $\ell_{0}$-norm as the count of non-
zero elements in $z$, and the $\ell_{\infty}$-norm as
$\|z\|_{\infty}:=\max_{i\in[n]}|z_{i}|$. The transpose of vector $z$ is
indicated by $z^{\top}$. The inner product between two vectors is denoted by
$\langle\cdot,\cdot\rangle$, such that $\langle
a,b\rangle=\sum_{i=1}^{n}a_{i}b_{i}$.

For any matrix $A\in\mathbb{R}^{m\times n}$. We define the Frobenius norm of a
matrix $A$ as $\|A\|_{F}:=(\sum_{i\in[m],j\in[n]}A_{i,j}^{2})^{1/2}$. We use
$\|A\|$ to denote the spectral/operator norm of matrix $A$.

A function $f(x)$ is said to be $L$-Lipschitz continuous if it satisfies the
condition $\|f(x)-f(y)\|_{2}\leq L\cdot\|x-y\|_{2}$ for some constant $L$. Let
${\cal D}$ represent a given distribution. The notation $x\sim{\cal D}$
indicates that $x$ is a random variable drawn from the distribution ${\cal
D}$. We employ $\operatorname*{{\mathbb{E}}}[]$ to represent the expectation
operator and $\Pr[]$ to denote probability. Furthermore, we refer to a matrix
as PSD to indicate that it is positive semi-definite.

As we have multiple indexes, to avoid confusion, we usually use $i,j\in[n]$ to
index the training data, $s,t\in[d]$ to index the feature dimension, $r\in[m]$
to index neuron number.

###  3.2 Neural Tangent Kernel

Now, we are ready to introduce our key concept, the Neural Tangent Kernel
induced by the Quadratic activation function. We will introduce Discrete
Quadratic Kernel in Definition 3.1, and Continuous Quadratic Kernel in
Definition 3.2.

Data. We have $n$ training data points ${\cal
D}_{n}=\\{(x_{i},y_{i})\\}_{i=1}^{n}=(X,Y)$, where $x\in\mathbb{R}^{d}$ and
$y\in\\{0,1\\}$. We denote $X=[x_{1},\dots,x_{n}]\in\mathbb{R}^{d\times n}$
and $Y=[y_{1},\dots,y_{n}]^{\top}\in\\{-1,+1\\}^{n}$. We assume that
$\|x_{i}\|_{2}\leq B$, $\forall i\in[n]$.

Models. We consider the two-layer neural network with quadratic activation
function and $m$ neurons

$\displaystyle f(x)=\sum_{r\in[m]}a_{r}\langle w_{r},x\rangle^{2},$

where $w_{r}\in\mathbb{R}^{d}$ and $a_{r}\in\\{-1,+1\\}$ for any $r\in[m]$.

######  Definition 3.1 (Discrete Quadratic NTK Kernel).

We draw weights $w_{r}\sim{\cal N}(0,\sigma^{2}I_{d\times d})$ for any
$r\in[m]$ and let them be fixed. Then, we define the discrete quadratic kernel
matrix $H^{\mathrm{dis}}\in\mathbb{R}^{n\times n}$ corresponding to ${\cal
D}_{n}$, such that $\forall i,j\in[n]$, we have

$\displaystyle H_{i,j}^{\mathrm{dis}}=\frac{1}{m}\sum_{r=1}^{m}\langle\langle
w_{r},x_{i}\rangle x_{i},\langle w_{r},x_{j}\rangle x_{j}\rangle.$

Note that $H^{\mathrm{dis}}$ is a PSD matrix, where a detailed proof can be
found in Lemma B.1.

######  Definition 3.2 (Continuous Quadratic NTK Kernel).

We define the continuous quadratic kernel matrix
$H^{\mathrm{cts}}\in\mathbb{R}^{n\times n}$ corresponding to ${\cal D}$, such
that $\forall i,j\in[n]$, we have

$\displaystyle H_{i,j}^{\mathrm{cts}}=\operatorname*{{\mathbb{E}}}_{w\sim{\cal
N}(0,\sigma^{2}I_{d\times d})}\langle\langle w,x_{i}\rangle x_{i},\langle
w,x_{j}\rangle x_{j}\rangle.$

###  3.3 NTK Regression

We begin by defining the classical kernel regression problem as follows:

######  Definition 3.3 (Classical kernel ridge regression [80]).

If we have the following conditions:

  * •

Let feature map $\phi:\mathbb{R}^{d}\to\mathcal{F}$.

  * •

$\lambda>0$ is the regularization parameter.

A classical kernel ridge regression problem can be written as

$\displaystyle\min_{w\in\mathbb{R}^{n}}\frac{1}{2}\|Y-\phi(X)^{\top}w\|_{2}^{2}+\frac{1}{2}\lambda\|w\|_{2}^{2}.$

Then, we are ready to introduce the NTK Regression problem as follows:

######  Definition 3.4 (NTK Regression [80]).

If the following conditions are met:

  * •

Let $\mathsf{K}(\cdot,\cdot):\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}$
be a kernel function, i.e.,
$\mathsf{K}(x,z)=\frac{1}{m}\sum_{r=1}^{m}\langle\langle w_{r},x\rangle
x,\langle w_{r},z\rangle z\rangle,\forall x,z\in\mathbb{R}^{d}.$

  * •

Let $K\in\mathbb{R}^{n\times n}$ be the kernel matrix with
$K_{i,j}=\mathsf{K}(x_{i},x_{j})$, $\forall i,j\in[n]\times[n]$.

  * •

Let $\alpha\in\mathbb{R}^{n}$ be the solution to $(K+\lambda I_{n})\alpha=Y$.
Namely, we have $\alpha=(K+\lambda I_{n})^{-1}Y$.

Then, for any data $x\in\mathbb{R}^{d}$, the NTK Kernel Regression can be
denoted as

$\displaystyle f_{K}^{*}(x)=\frac{1}{n}\mathsf{K}(x,X)^{\top}\alpha.$

##  4 Main Results

In the NTK Regression definition, we have the expression $\alpha=(K+\lambda
I)^{-1}Y$ (see also Definition 3.4).

To ensure the privacy of $\alpha$, we initially focus on privatizing $K$.
Subsequently, we demonstrate that $\alpha$ remains private through the
application of the Post-processing Lemma (see also Lemma A.6). Privatizing $K$
is non-trivial, as $K=H^{\mathrm{dis}}$, indicating that $K$ is a positive
semi-definite (PSD) matrix (see Lemma B.1). We denote $\widetilde{K}$ as the
privacy-preserving counterpart of $K$. It is essential that $\widetilde{K}$
maintains the PSD property, a condition that classical mechanisms such as the
Laplace Mechanism and Gaussian Mechanism cannot inherently guarantee for a
private matrix. In the work by [55], the “Gaussian Sampling Mechanism” is
employed to address this challenge, ensuring that the private version of the
Attention Matrix also retains PSD. Adopting the same setup from [55], we
present our findings on the privacy and utility of the “Gaussian Sampling
Mechanism” in this section.

In Section 4.1, we provide several essential definitions used in our
algorithm. In Section 4.2, we will adhere to the framework established in [55]
and elaborate on the functioning of the “Gaussian Sampling Mechanism,” along
with its primary results and requirements. In Section 4.3, we will examine the
utility implications of employing the ”Gaussian Sampling Mechanism.”
Additionally, we include a Remark that analyzes the trade-off between privacy
and utility inherent in our approach. In Section 4.4, we introduce the final
theorem of our algorithm, including both privacy guarantees and utility
guarantees.

###  4.1 Key Concepts

To begin with, we will introduce the definition of neighboring dataset used in
“Gaussian Sampling Mechanism”.

######  Definition 4.1 ($\beta$-close neighbor dataset, [55]).

If we have below conditions,

  * •

Let $B>0$ be a constant.

  * •

Let $n$ be the number of data points.

  * •

Let dataset ${\cal D}=\\{(x_{i},y_{i})\\}_{i=1}^{n}$, where
$x_{i}\in\mathbb{R}^{d}$ and $\|x_{i}\|_{2}\leq B$ for any $i\in[n]$.

We define ${\cal D^{\prime}}$ be a neighbor dataset with one data point
replacement of ${\cal D}$. Without loss of generality, we have ${\cal
D^{\prime}}=\\{(x_{i},y_{i})\\}_{i=1}^{n-1}\cup\\{(x_{n}^{\prime},y_{n})\\}$.Namely,
we have ${\cal D}$ and ${\cal D^{\prime}}$ only differ in the $n$-th item.

Additionally, we assume that $x_{n}$ and $x_{n}^{\prime}$ are $\beta$-close.
Namely, we have

$\displaystyle\|x_{n}-x_{n}^{\prime}\|_{2}\leq\beta$

There are also two essential definitions $M$ and $\Delta$ used in the privacy
proof of “Gaussian Sampling Mechanism”, which need to satisfy $M<\Delta$,
which is also the Condition 4 in Condition 4.4. We will begin by presenting
the definition of $M$.

######  Definition 4.2 (Definition of $M$, [55]).

Let $\mathcal{M}:(\mathbb{R}^{n})^{d}\to\mathbb{R}^{n\times n}$ be a
(randomized) algorithm that given a dataset of $d$ points in $\mathbb{R}^{n}$
outputs a PSD matrix. Let
$\mathcal{Y},\mathcal{Y}^{\prime}\in(\mathbb{R}^{n})^{d}$. Then, we define

$\displaystyle
M:=\|\mathcal{M}(\mathcal{Y})^{1/2}\mathcal{M}(\mathcal{Y}^{{}^{\prime}})^{-1}\mathcal{M}(\mathcal{Y})^{1/2}-I\|_{F}$

Afterward, we proceed to define $\Delta$.

######  Definition 4.3 ( Definition of $\Delta$, [55] ).

If we have the following conditions:

  * •

Let $\epsilon\in(0,1)$ and $\delta\in(0,1)$.

  * •

Let $k$ denote the number of i.i.d. samples $g_{1},g_{2},\cdots,g_{k}$ from
$\mathcal{N}(0,\Sigma_{1})$ output by Algorithm 1.

We define

$\displaystyle\Delta:=\min\bigg{\\{}\frac{\epsilon}{\sqrt{8k\log(1/\delta)}},\frac{\epsilon}{8\log(1/\delta)}\bigg{\\}}$

###  4.2 Gaussian Sampling Mechanism

In this section, we recapitulate the analytical outcomes of the “Gaussian
Sampling Mechanism” as presented in Theorem 4.5 from [55]. The associated
algorithm is detailed in Algorithm 1.

Firstly, we outline the conditions employed in the “Gaussian Sampling
Mechanism” as follows:

######  Condition 4.4.

We need the following conditions for DP:

  * •

Condition 1. Let $\epsilon\in(0,1)$, $\delta\in(0,1)$, $k\in\mathbb{N}$.

  * •

Condition 2. Let $\mathcal{Y},\mathcal{Y}^{\prime}$ denote neighboring
datasets, which differ by a single data element.

  * •

Condition 3. Let $\Delta$ be defined in Definition 4.3 and $\Delta<1$.

  * •

Condition 4. Let $M,{\cal M}$ be defined in Definition 4.2 and $M\leq\Delta$.

  * •

Condition 5. Let the input $\Sigma=\mathcal{M}(\mathcal{Y})$.

  * •

Condition 6. Let
$\rho=O(\sqrt{(n^{2}+\log(1/\gamma))/k}+(n^{2}+\log(1/\gamma))/{k})$.

Prior to delving into the primary analysis of the “Gaussian Sampling
Mechanism” , we offer a succinct overview of its underlying intuition. As
noted at the outset of Section 4, the task of obtaining a private positive
semi-definite (PSD) matrix is non-trivial.

Nevertheless, by leveraging Covariance estimation within the “Gaussian
Sampling Mechanism”, we can guarantee that the estimated matrix will remain
PSD. This is because for any $i\in[k]$, we have $g_{i}g_{i}^{\top}$ is PSD
matrix, then $(k^{-1}\sum_{i=1}^{k}g_{i}g_{i}^{\top}$ is also PSD matrix.

With this foundation, we can proceed to introduce the analysis of the
“Gaussian Sampling Mechanism” with confidence. The analysis is presented as
follows:

######  Lemma 4.5 (Analysis of the Gaussian Sampling Mechanism, Theorem 6.12
in [55], Theorem 5.1 in [7], informal version of Lemma C.1).

If all conditions hold in Condition 4.4 and Condition 4.6, then, there exists
an Algorithm 1 such that

  * •

Part 1. Algorithm 1 is $(\epsilon,\delta)$-DP.

  * •

Part 2. Outputs $\widehat{\Sigma}\in\mathbb{S}_{+}^{n}$ denotes the private
version of input $\Sigma$, such that with probabilities at least $1-\gamma$,

$\displaystyle\|\Sigma^{-1/2}\widehat{\Sigma}\Sigma^{-1/2}-I_{n}\|_{F}\leq\rho$

  * •

Part 3.

$\displaystyle(1-\rho)\Sigma\preceq\widehat{\Sigma}\preceq(1+\rho)\Sigma$

In Lemma 4.5, Part 1 claims the privacy guarantees of the “Gaussian Sampling
Mechanism”, Part 2 establishes the critical properties necessary to ensure the
utility of the “Gaussian Sampling Mechanism”, and Part 3 presents the ultimate
utility outcomes of the algorithm.

Note that in our setting, we use $\Sigma=K$, where $K$ is non-private Discrete
Quadratic NTK Matrix in NTK Regression, and we also have
$\widehat{\Sigma}=\widetilde{K}$, where $\widetilde{K}$ denotes the private
version of $K$.

Algorithm 1 The Gaussian Sampling Mechanism, [55]

1:procedure Algorithm($\Sigma,k$)

2: PSD matrix $\Sigma\in\mathbb{R}^{n\times n}$ and parameter $k\in\mathbb{N}$

3: Obtain vectors $g_{1},g_{2},\cdots,g_{k}$ by sampling
$g_{i}\sim\mathcal{N}(0,\Sigma)$, independently for each $i\in[k]$

4: Compute $\widehat{\Sigma}=\frac{1}{k}\sum_{i=1}^{k}g_{i}g_{i}^{\top}$
$\triangleright$ Covariance estimate.

5: return $\widehat{\Sigma}$

6:end procedure

We need the following conditions so that we can make Condition 4 in Condition
4.4 hold, with probability $1-\delta_{3}$. See the detailed proof in Section
5.3.

######  Condition 4.6.

We need the following conditions for the calculation of $M$ (see Definition
4.2).

  * •

Condition 1. If ${\cal D}\in\mathbb{R}^{n\times d}$ and ${\cal
D}^{\prime}\in\mathbb{R}^{n\times d}$ are neighboring dataset (see Definition
4.1)

  * •

Condition 2. Let $H^{\mathrm{dis}}$ denote the discrete NTK kernel matrix
generated by ${\cal D}$, and ${H^{\mathrm{dis}}}^{\prime}$ denotes the
discrete NTK kernel matrix generated by neighboring dataset ${\cal
D}^{\prime}$.

  * •

Condition 3. Let $H^{\mathrm{dis}}\succeq\eta_{\min}I_{n\times n}$, for some
$\eta_{\min}\in\mathbb{R}$.

  * •

Condition 4. Let $\beta=O(\eta_{\min}/\operatorname{poly}(n,\sigma,B))$, where
$\beta$ is defined in Definition 4.1.

  * •

Condition 5. Let $\psi:=O(\sqrt{n}\sigma^{2}B^{3}\beta)$.

  * •

Condition 6. Let $\delta_{1},\delta_{2},\delta_{3}\in(0,1)$. Let
$\delta_{1}=\delta_{2}/\operatorname{poly}(m)$. Let
$\delta_{2}=\delta_{3}/\operatorname{poly}(n)$.

  * •

Condition 7. Let $d=\Omega(\log(1/\delta_{1}))$.

  * •

Condition 8. Let $m=\Omega(n\cdot dB^{2}\beta^{-2}\log(1/\delta_{2}))$.

###  4.3 Utility of Gaussian Sampling Mechanism

In this section, we will provide utility guarantees under “Gaussian Sampling
Mechanism”. By Lemma 4.8, we will argue that, “Gaussian Sampling Mechanism”
provides good utility under differential privacy.

We start with introducing the necessary conditions used in proving the utility
of “Gaussian Sampling Mechanism”.

######  Condition 4.7.

We need the following conditions for Utility guarantees of “Gaussian Sampling
Mechanism”:

  * •

Condition 1. If ${\cal D}\in\mathbb{R}^{n\times d}$ and ${\cal
D}^{\prime}\in\mathbb{R}^{n\times d}$ are neighboring dataset (see Definition
4.1)

  * •

Condition 2. Let $H^{\mathrm{dis}}$ denote the discrete NTK kernel matrix
generated by ${\cal D}$ (see Definition 3.1).

  * •

Condition 3. Let $\eta_{\max}I_{n\times n}\succeq
H^{\mathrm{dis}}\succeq\eta_{\min}I_{n\times n}$, for some
$\eta_{\max},\eta_{\min}\in\mathbb{R}$.

  * •

Condition 4. Let $\widetilde{H}^{\mathrm{dis}}$ denote the private
$H^{\mathrm{dis}}$ generated by Algorithm 1 with $H^{\mathrm{dis}}$ as the
input.

  * •

Condition 5. Let
$K=H^{\mathrm{dis}},\widetilde{K}=\widetilde{H}^{\mathrm{dis}}$ in Definition
3.4. Then we have $f_{K}^{*}(x)$ and $f_{\widetilde{K}}^{*}(x)$.

  * •

Condition 6. Let $\sqrt{n}\psi/\eta_{\min}<\Delta$, where $\Delta$ is defined
in Definition 4.3.

  * •

Condition 7. Let
$\rho=O(\sqrt{(n^{2}+\log(1/\gamma))/k}+(n^{2}+\log(1/\gamma))/{k})$.

  * •

Condition 8. Let $\omega:=6d\sigma^{2}B^{4}$.

  * •

Condition 9. Let $\gamma\in(0,1)$.

We then leverage Part 3 of Lemma 4.5 to derive the error between the outputs
of the private and non-private NTK Regression, thereby demonstrating the
utility of our algorithm.

######  Lemma 4.8 (Utility guarantees of “Gaussian Sampling Mechanism”,
informal version of Lemma E.4).

If all conditions hold in Condition 4.7, then, with probability $1-\gamma$, we
have

$\displaystyle|f_{K}^{*}(x)-f_{\widetilde{K}}^{*}(x)|\leq
O(\frac{\rho\cdot\eta_{\max}\cdot\omega}{(\eta_{\min}+\lambda)^{2}})$

The interplay between privacy and utility guarantees is complex. Our algorithm
exhibits a property akin to that of other classical differential privacy
algorithms: an increase in privacy typically results in a decrease in utility,
and conversely.

We will provide a thorough explanation of the privacy-utility trade-off in the
subsequent Remark.

Algorithm 2 Private NTK Regression

1:procedure Main($X\in\mathbb{R}^{n\times d},m,k$) $\triangleright$ Theorem
4.10

2: Draw $w_{1},\cdots,w_{m}\in\mathbb{R}^{d}$ random Gaussian vectors

3: Compute $K$ such such $K_{i,j}=\mathsf{K}(x_{i},x_{j})$

4: Obtain vectors $g_{1},g_{2},\cdots,g_{k}$ by sampling $g_{i}\sim{\cal
N}(0,K)$ independently for each $i\in[k]$

5: Compute $\widetilde{K}\leftarrow\frac{1}{k}\sum_{i=1}^{k}g_{i}g_{i}^{\top}$

6: Compute
$f_{\widetilde{K}}^{*}(x)\leftarrow\mathsf{K}(x,X)^{\top}(\widetilde{K}+\lambda\cdot
I_{n})^{-1}Y$

7: return $f_{\widetilde{K}}^{*}(x)$

8:end procedure

######  Remark 4.9 (Trade-off between Privacy and Utility in Lemma 4.8).

An inherent trade-off exists between the privacy and utility guarantees of our
algorithm. Specifically, enhancing privacy typically results in a degradation
of utility. Recall that the variable $k$ represents the number of sampling
iterations in the Gaussian Sampling Mechanism.

To ensure privacy, we must adhere to Condition 4 as outlined in Condition 4.4,
which requires that $M<\Delta$. Here, $M$ is a constant defined in Definition
4.2, with its precise value calculated in Lemma 5.1. In contrast, $\Delta$ is
defined in Definition 4.3 and is dependent on the value of $k$. Consequently,
to achieve stronger privacy, namely a smaller DP parameter $\epsilon$ or
$\delta$, it is necessary to decrease $k$ to meet the $M<\Delta$ constraint.

On the other hand, for utility considerations, as defined by
$\rho=O(\sqrt{(n^{2}+\log(1/\gamma))/k}+(n^{2}+\log(1/\gamma))/k)$, a
reduction in $k$ results in an increase in $\rho$. This, in turn, leads to
diminished utility.

Due to the limitation of space, we refer the readers to Lemma E.4 in Appendix
for the details of proof of Lemma 4.8. A detailed explanation of the trade-off
between Privacy and Utility can be found in Remark 4.9.

###  4.4 Main Theorem

Then, we are ready to introduce our main result, including the privacy and
utility of our algorithm.

######  Theorem 4.10 (Main result, formal version of Theorem 1.1).

If all conditions hold in Condition 4.4, Condition 4.6, and Condition 4.7,
then, for any test data $x$, with probability $1-\delta_{3}-\gamma$, we have
that $f_{\widetilde{K}}^{*}(x)$ is $(\epsilon,\delta)$-DP and

$\displaystyle|f_{K}^{*}(x)-f_{\widetilde{K}}^{*}(x)|\leq
O(\frac{\rho\cdot\eta_{\max}\cdot\omega}{(\eta_{\min}+\lambda)^{2}}).$

It follows from directly combining Lemma 4.5, Lemma 4.8, and Lemma 5.1.

##  5 Technical Overview

In this section, we offer a succinct overview of the proof techniques employed
throughout this paper.

We begin by detailing the method for calculating the Sensitivity of the
Continuous Quadratic NTK in Section 5.1. Subsequently, in Section 5.2, we
utilize concentration inequalities, specifically Bernstein’s Inequality, to
narrow the gap between the Continuous Quadratic NTK and Discrete Quadratic
NTK. In Section 5.3, we will delve into the sensitivity of the PSD matrix $K$,
which is the matrix we aim to privatize. Concluding this overview, we present
the approaches for establishing privacy guarantees and utility guarantees in
Sections 5.4 and 5.5, respectively.

###  5.1 Sensitivity of Continuous Quadratic NTK

Given that the Discrete Quadratic NTK is defined as
$H_{i,j}^{\mathrm{dis}}=\frac{1}{m}\sum_{r=1}^{m}\langle\langle
w_{r},x_{i}\rangle x_{i},\langle w_{r},x_{j}\rangle x_{j}\rangle$ (see also
Definition 3.1), analyzing its sensitivity when a single data point is altered
in the training dataset poses a challenge. In contrast, the Continuous
Quadratic NTK, which incorporates Expectation in its definition (refer to
Definition 3.2), is significantly much easier to analyze. The discrepancy
between the Discrete and Continuous versions of the NTK can be reconciled
through Concentration inequalities. Consequently, we will start our analysis
of NTK Regression by focusing on the Continuous Quadratic NTK.

In the “Gaussian Sampling Mechanism” (see also Section 4.2), we defined the
concept of neighboring datasets being $\beta$-close (refer to Definition 4.1).
We focus on examining the Lipschitz property of individual entries within the
Continuous Quadratic NTK.

Without loss of generality, let us consider a dataset $\mathcal{D}$ of length
$n$, and let neighboring datasets $\mathcal{D}$ and $\mathcal{D^{\prime}}$
differ solely in their $n$-th data point. Consequently, as per the definition
of the Continuous Quadratic NTK, the respective kernels $H^{\mathrm{cts}}$ and
${H^{\mathrm{cts}}}^{\prime}$ will differ exclusively in their $n$-th row and
$n$-th column.

To examine the Lipschitz property for the $n$-th row and $n$-th column, we
must consider two distinct cases. Initially, we focus on the sole diagonal
entry, the $(n,n)$-th element, in the Continuous Quadratic NTK. The Lipschitz
property for this entry is given by (see also Lemma D.3):

$\displaystyle|H^{\mathrm{cts}}_{n,n}-{H^{\mathrm{cts}}_{n,n}}^{\prime}|\leq
4\sigma^{2}B^{3}\cdot\|x-x^{\prime}\|_{2}$

Subsequently, we will address the remaining $2n-2$ non-diagonal entries within
the $n$-th row and $n$-th column, for which the Lipschitz property is as
follows: (see also Lemma D.2). For all $\\{(i,j):(i=n,j\neq n)or(i\neq
n,j=n),i,j\in[n]\\}$, we have

$\displaystyle|H^{\mathrm{cts}}_{i,j}-{H^{\mathrm{cts}}_{i,j}}^{\prime}|\leq
2\sigma^{2}B^{3}\cdot\|x-x^{\prime}\|_{2}$

Moreover, we compute the sensitivity of the Continuous Quadratic NTK with
respect to $\beta$-close neighboring datasets. Leveraging the Lipschitz
properties of the diagonal and non-diagonal entries discussed earlier, we
derive the sensitivity of the Continuous Quadratic NTK as follows: (see also
Lemma D.4)

$\displaystyle\|H^{\mathrm{cts}}-{H^{\mathrm{cts}}}^{\prime}\|_{F}\leq
O(\sqrt{n}\sigma^{2}B^{3}\beta)$

###  5.2 Bridge the gap between Continuous and Discrete Quadratic NTKs

In the previous section, we established the sensitivity of the Continuous
Quadratic NTK. Here, we aim to bridge the divide between the Continuous
Quadratic NTK and Discrete Quadratic NTK.

The underlying rationale is that the number of neurons, $m$, in the Discrete
Quadratic NTK can be extremely large. With the help of this property, we
invoke the strength of concentration inequalities, specifically Bernstein’s
Inequality, to demonstrate that with high probability, the discrepancy between
the Continuous Quadratic NTK and Discrete Quadratic NTK is negligible. Namely,
we have (see also Lemma D.11)

$\displaystyle\|H^{\mathrm{dis}}-H^{\mathrm{cts}}\|_{F}\leq n\epsilon$

Further, we examine the sensitivity of the Discrete Quadratic NTK with respect
to $\beta$-close neighboring datasets. Recall that we have previously
established the sensitivity of the Continuous Quadratic NTK in Lemma D.4. We
now incorporate both Bernstein’s Inequality and the sensitivity of the
Continuous Quadratic NTK into our analysis. We have (see also Lemma D.13)

$\displaystyle\|H^{\mathrm{dis}}-{H^{\mathrm{dis}}}^{\prime}\|_{F}\leq
O(\sqrt{n}\sigma^{2}B^{3}\beta)$

###  5.3 Sensitivity of PSD Matrix

In alignment with [55], this section will present Lemma 5.1, which offers a
calculation for $M$ (refer to Definition 4.2). Utilizing this result and
noting that $\Delta$ is dependent on $k$ (see Definition 4.3), we can
subsequently refine the sampling time $k$ to satisfy Condition 4 as mentioned
in Condition 4.4.

######  Lemma 5.1 (Sensitivity of PSD Matrix $H^{\mathrm{dis}}$, informal
version of Lemma D.15).

If all conditions hold in Condition 4.6, then, with probability
$1-\delta_{3}$, we have

  * •

Part 1.

$\displaystyle\|(H^{\mathrm{dis}})^{-1/2}{H^{\mathrm{dis}}}^{\prime}(H^{\mathrm{dis}})^{-1/2}-I\|\leq\psi/\eta_{\min}$

  * •

Part 2.

$\displaystyle\|(H^{\mathrm{dis}})^{-1/2}{H^{\mathrm{dis}}}^{\prime}(H^{\mathrm{dis}})^{-1/2}-I\|_{F}\leq\sqrt{n}\psi/\eta_{\min}$

In Lemma 5.1, Part 1 and Part 2 respectively establish the bounds for $M$ (as
defined in Definition 4.2) under the spectral norm and Frobenius norm. These
findings offer insights into how to modify $k$ in order to fulfill Condition 4
as required by Condition 4.4.

###  5.4 Privacy Guarantees for Private NTK Regression

In Lemma 4.5 and under Condition 4. in Condition 4.4, we need to compute $M$
(as defined in Definition 4.2) for the Discrete Quadratic NTK.

The pivotal approach is to first utilize the sensitivity of the Discrete
Quadratic NTK (refer to Lemma D.13) to establish the inequalities for positive
semi-definite matrices (see Lemma D.14). Specifically, we obtain

$\displaystyle(1-\psi/\eta_{\min})H^{\mathrm{dis}}\preceq{H^{\mathrm{dis}}}^{\prime}\preceq(1+\psi/\eta_{\min})H^{\mathrm{dis}}$

Building on these inequalities, we can further demonstrate that (as shown in
Lemma 5.1)

$\displaystyle\|(H^{\mathrm{dis}})^{-1/2}{H^{\mathrm{dis}}}^{\prime}(H^{\mathrm{dis}})^{-1/2}-I\|_{F}\leq\sqrt{n}\psi/\eta_{\min}$

Consequently, since $\psi=O(\sqrt{n}\sigma^{2}B^{3}\beta)$, by choosing a
small $\beta$, we achieve

$\displaystyle
M=\|(H^{\mathrm{dis}})^{-1/2}{H^{\mathrm{dis}}}^{\prime}(H^{\mathrm{dis}})^{-1/2}-I\|_{F}\leq\Delta$

which fulfills the requirements of Condition 4. in Condition 4.4. Thus, by
Lemma 4.5, we establish the privacy guarantees for our algorithm.

###  5.5 Utility Guarantees for Private NTK Regression

In this section, we will present a comprehensive analysis of the utility
guarantees for our private NTK Regression.

Recall that in the definition of NTK Regression (refer to Definition 3.4), we
have

$\displaystyle f_{K}^{*}(x)=\mathsf{K}(x,X)^{\top}(K+\lambda I_{n})^{-1}Y$

We commence by establishing a bound on the spectral norm of $(K+\lambda
I_{n})^{-1}$ as follows (see also Lemma E.3)

$\displaystyle\|(K+\lambda I)^{-1}-(\widetilde{K}+\lambda I)^{-1}\|\leq
O(\frac{\rho\cdot\eta_{\max}}{(\eta_{\min}+\lambda)^{2}})$

Here, we employ the Moore-Penrose inverse (see also Lemma E.2) to address the
inversion in $(K+\lambda I_{n})^{-1}$.

Utilizing the spectral norm bound, we then derive bounds for the
$\mathcal{L}_{2}$ norms of $\mathsf{K}(x,X)$ and $Y$. After selecting a small
$\beta$, we arrive at the final result that (see also Lemma 4.8)

$\displaystyle|f_{K}^{*}(x)-f_{\widetilde{K}}^{*}(x)|\leq
O(\frac{\rho\cdot\eta_{\max}\cdot\omega}{(\eta_{\min}+\lambda)^{2}})$

Thus, we have demonstrated that our private NTK Regression maintains high
utility while simultaneously ensuring privacy.

Similar to other differential privacy algorithms, our algorithm encounters a
trade-off between privacy and utility, where increased privacy typically
results in a reduction in utility, and conversely. An in-depth examination of
this trade-off is provided in Remark 4.9.

##  6 Experiments

This section will introduce the experimental methodology employed on the
CIFAR-10 dataset. The corresponding results are visualized in Fig. 1. In
Section 6.1, we enumerate all the parameters and the experimental setup we
utilized. Section 6.2 presents a detailed analysis of the outcomes from our
experiments.

###  6.1 Experiment Setup

Dataset. Our experiments are conducted on the CIFAR-10 dataset [66], which
comprises 10 distinct classes of colored images, including subjects such as
airplanes, cats, and dogs. The dataset is partitioned into 50,000 training
samples and 10,000 testing samples, with each image measuring $32\times 32$
pixels and featuring RGB channels. Given that our NTK Regression is tailored
for binary classification, we select two random classes from the 10 available
classes to conduct the binary classification task. We randomly choose 1,000
images for training and 100 for testing.

Feature Extraction. CIFAR-10 images possess a high-dimensional nature
($32\times 32\times 3=3,072$ dimensions), which poses a challenge for NTK
Regression. To address this, we leverage the power of ResNet [61] to reduce
the dimension. Following the approach of [9], we employ ResNet-18 to encode
the images and extract features from the network’s last layer, yielding a
512-dimensional feature representation for each image.

Feature Normalization. Prior to training our NTK Regression, we normalize all
image features such that the $\mathcal{L}_{2}$ norm of each feature vector is
equal to 1.

NTK Regression Setup. For both NTK Regression and the NTK Regression Kernel
Matrix, we select $m=256$ neurons and a random Gaussian variance of
$\sigma=1$. This means that for each $r\in[m]$, the weights $w_{r}$ are drawn
from the normal distribution ${\cal N}(0,I_{d\times d})$. Additionally, we set
the regularization factor $\lambda=10$.

###  6.2 Main Results

In accordance with the experimental setup detailed in Section 6.1, we present
the results in Fig. 1.

During the execution of NTK Regression, we initially compute
$H^{\mathrm{dis}}$ (as defined in Definition 3.1) based on the quadratic
activation between the training data and $m$ neurons. As $H^{\mathrm{dis}}$ is
a symmetric matrix, it is also positive semi-definite.

Subsequently, in accordance with the notation in Definition 3.4, we define
$K=H^{\mathrm{dis}}$. We then apply the Gaussian Sampling Mechanism, as
described in Section 4, to privatize $K$, denoting the private version as
$\widetilde{K}$. Due to the properties of the Gaussian Sampling Mechanism,
$\widetilde{K}$ remains symmetric and thus positive semi-definite. Lemma 4.5
guarantees that $\widetilde{K}$ is $(\epsilon,\delta)$-DP.

We then compute the private $\alpha$, denoted as $\widetilde{\alpha}$, by
$\widetilde{\alpha}=(\widetilde{K}+\lambda I_{n\times n})^{-1}Y$. By the Post-
processing Lemma of differential privacy (refer to Lemma A.6), we confirm that
$\widetilde{\alpha}$ is also $(\epsilon,\delta)$-DP Consequently, NTK
Regression itself is $(\epsilon,\delta)$-DP.

In our experiment, we fix the differential privacy parameter $\delta=10^{-3}$.
We recall that $\Delta$ is defined in Definition 4.3, and $M$ is defined in
Definition 4.2. To satisfy Condition 5 in Condition 4.4, we must ensure
$M<\Delta$.

We select $k$ to be greater than or equal to $8\cdot\log(1/\delta)$, ensuring
that for any $\epsilon>0$, the condition
$\epsilon/\sqrt{8k\log(1/\delta)}\leq\epsilon/(8\log(1/\delta))$ holds.
Consequently, we have $\Delta=\epsilon/\sqrt{8k\log(1/\delta)}$ (see also
Definition 4.3).

Under this setup, the condition $M<\Delta$ is equivalent to:

$\displaystyle
k\leq\frac{\epsilon^{2}\eta_{\min}^{2}}{8\log(1/\delta)n^{2}\sigma^{4}B^{8}\beta^{2}}$
(1)

In our experimental setup, we have $\sigma=1$, $B=1$, $\eta_{\min}=7\times
10^{-3}$, and $n=10^{3}$. We assume $\beta=10^{-6}$. We then compute the upper
bound for $k$ using Eq. (1) and adhere to this upper bound when conducting our
experiments. The outcomes are presented in Fig. 1.

Figure 1:  The trade-off between the accuracy parameter and privacy parameter.
We conduct experiments on different privacy budget $\epsilon$, where we fixed
the $\delta=10^{-3}$, and we assume that $\beta=10^{-6}$ in our experiments.
The x-axis denotes the $\log(\epsilon_{\mathrm{dp}})$, where the $\log$
denotes $\log_{10}$. The y-axis denotes the binary classification accuracy. As
privacy budget $\epsilon_{\mathrm{dp}}$ increase, both private test acc and
private train acc approach to non-private train acc and non-private test acc,
respectively.

##  7 Discussion

DP in kernel and gradient.  In DP-SGD [3], they add Gaussian noise on the
gradient for privacy. As they are a first-order algorithm, their function
sensitivity is more robust for single-step training. However, as discussed in
Section 1, to guarantee DP for the whole training process, their DP Gaussian
noise variance will increase as $T$ becomes larger (see Theorem 1 in [3]). The
DP-SGD will not be practical when $T$ is too large. On the other hand, our NTK
regression setting is a second-order algorithm involving kernel matrix
inverse. Then, our key technical issues are (1) introducing a PSD noise matrix
to keep kernel PSD property and (2) using $L_{2}$ regularization to make the
kernel sensitivity more robust (see more details in Section 5).

Where to add noise? The proper way to add noise is a fundamental problem in
differential privacy. In the work, we add noise to the kernel function to make
the neural tangent kernel private. The other option is to add noise on the
parameter $\alpha$ in Definition 3.4, but the issue is that the sensitivity of
the matrix inverse operation is not robust, so the privacy guarantee will not
be ideal in this case.

##  8 Conclusion

In conclusion, we have presented the first DP guarantees for NTK regression.
Our algorithm provides a provable privacy-utility trade-off validated on
CIFAR-10. This work opens new avenues for privacy-preserving deep learning
using an NTK-based algorithm.

## Acknowledgement

Research is partially supported by the National Science Foundation (NSF)
Grants 2023239-DMS, CCF-2046710, and Air Force Grant FA9550-18-1-0166.

Appendix

#### Roadmap.

The Appendix is organized as follows.

In Section A, we introduce the fundamental probability, algebra, and
differential privacy tools that are utilized throughout the paper.

Section B contains the proof of the positive semi-definite (PSD) property for
the Discrete Quadratic NTK.

Section C restates the analysis results for the ”Gaussian Sampling Mechanism.”

Section D presents a comprehensive proof of the sensitivity for both the
Continuous Quadratic NTK and the Discrete Quadratic NTK, which we subsequently
employ to ensure the privacy of our Private NTK Regression.

Finally, in Section E, we discuss the utility guarantees of our algorithm.

##  Appendix A Basic Tools

In this section, we display more fundamental concepts and tools for a better
understanding of the readers.

In Section A.1, we introduce a useful tail bound for the Chi-square
distribution, as well as the classical concentration inequality.

In Section A.2, we demonstrate useful properties of Gaussian distribution and
some useful inequalities for matrix norm and vector norm.

In Section A.3, we provide an essential post-processing Lemma for Differential
Privacy.

###  A.1 Probability Tools

We state some standard tools from the literature. Firstly, we will state the
tail bound of the Chi-Squared distribution in the following Lemma.

######  Lemma A.1 (Lemma 1 in [78] ).

Let $X\sim\mathcal{X}_{k}^{2}$ be a chi-squared distributed random variable
with $k$ degrees of freedom. Each one has zero means and $\sigma^{2}$
variance.

Then, it holds that

$\displaystyle\Pr[X-k\sigma^{2}\geq(2\sqrt{dt}+2t)\sigma^{2}]\leq$
$\displaystyle~{}\exp{(-t)}$ $\displaystyle\Pr[k\sigma^{2}-X\geq
2\sqrt{dt}\sigma^{2}]\leq$ $\displaystyle~{}\exp{(-t)}$

Further if $k\geq\Omega(\epsilon^{-2}t)$ and $t\geq\Omega(\log(1/\delta))$,
then we have

$\displaystyle\Pr[|X-k\sigma^{2}|\geq\epsilon k\sigma^{2}]\leq\delta.$

Then, we will present several useful concentration inequalities.

######  Lemma A.2 (Bernstein inequality (scalar version) [14]).

Let $X_{1},\cdots,X_{n}$ be independent zero-mean random variables. Suppose
that $|X_{i}|\leq M$ almost surely, for all $i$. Then, for all positive $t$,

$\displaystyle\Pr[\sum_{i=1}^{n}X_{i}>t]\leq\exp(-\frac{t^{2}/2}{\sum_{j=1}^{n}\operatorname*{{\mathbb{E}}}[X_{j}^{2}]+Mt/3})$

######  Lemma A.3 (Markov’s inequality).

Let $x$ be a non-negative random variable and $t>0$, and let $f(x)$ be the
probability density function (pdf) of $x$. Then, we have

$\displaystyle\Pr[x\geq t]\leq\frac{\operatorname*{{\mathbb{E}}}[x]}{t}.$

###  A.2 Basic Algebra Tools

We state a standard fact for the 4-th moment of Gaussian distribution.

######  Fact A.4.

Let $x\sim{\cal N}(0,\sigma^{2})$, then it holds that
$\operatorname*{{\mathbb{E}}}_{x\sim{\cal
N}(0,\sigma^{2})}[x^{4}]=3\sigma^{2}$.

We also list some facts related to matrix norm and vector norm here.

######  Fact A.5.

We have

  * •

Let $A\in\mathbb{R}^{n\times n}$, then we have $\|A\|_{F}\leq\sqrt{n}\|A\|$.

  * •

Let $A\in\mathbb{R}^{n\times n}$, then we have $\|A\|\leq\|A\|_{F}$

  * •

For two vectors $a,b\in\mathbb{R}^{n}$, then we have
$|ab^{\top}|\leq\|a\|_{2}\cdot\|b\|_{2}$

###  A.3 Differential Privacy Tools

Here, we introduce the critical post-processing Lemma for Differential
Privacy.

######  Lemma A.6 (Post-Processing Lemma for DP, [31]).

Let $\mathcal{M}:=\mathbb{N}^{|\chi|}\rightarrow\mathbb{R}$ be a randomized
algorithm that is $(\epsilon,\delta)$-differentially private. Let
$f:\mathbb{R}\rightarrow\mathbb{R}^{\prime}$ be an arbitrarily random mapping.
Then is $f\circ\mathcal{M}:\mathbb{N}^{|\chi|}\rightarrow\mathbb{R}^{\prime}$
$(\epsilon,\delta)$-differentially private.

##  Appendix B Positive Semi-Definite Matrices

In this section, we introduce the proof for the PSD property of the Discrete
Quadratic NTK Matrix (see Definition 3.1).

######  Lemma B.1 ($H^{\mathrm{dis}}$ is PSD).

Let $H^{\mathrm{dis}}$ denote the discrete quadratic NTK matrix in Definition
3.1.

Then, we can show that $H^{\mathrm{dis}}$ is PSD.

###### Proof.

Recall in Definition 3.1, we have $H^{\mathrm{dis}}\in\mathbb{R}^{n\times n}$,
where the $(i,j)$-th entry of $H^{\mathrm{dis}}$ satisfies

$\displaystyle H_{i,j}^{\mathrm{dis}}=\frac{1}{m}\sum_{r=1}^{m}\langle\langle
w_{r},x_{i}\rangle x_{i},\langle w_{r},x_{j}\rangle x_{j}\rangle.$

Let $b_{r,i}=\langle w_{r},x_{i}\rangle x_{i}$, where for any $i\in[n]$,
$b_{r,i}\in\mathbb{R}^{d}$.

Let $B_{r}=[b_{r,1},b_{r,2},\cdots,b_{r,n}]$, where
$B_{r}\in\mathbb{R}^{n\times n}$.

Then, we have

$\displaystyle H^{\mathrm{dis}}=\frac{1}{m}\sum_{r=1}^{m}B_{r}B_{r}^{\top}$

Since $B_{r}B_{r}^{\top}$ is PSD matrix, $H^{\mathrm{dis}}$ is also PSD
matrix.

∎

##  Appendix C Gaussian Sampling Mechanism

In this section, we restate the analysis for “Gaussian Sampling Mechanism”,
which guarantees the privacy of our algorithm, and provides potential tools
for demonstrating its utility.

######  Lemma C.1 (Analysis of the Gaussian Sampling Mechanism, Theorem 6.12
in [55], Theorem 5.1 in [7], formal version of Lemma 4.5).

If we have the below conditions,

  * •

Condition 1. Let $\epsilon\in(0,1)$, $\delta\in(0,1)$, $k\in\mathbb{N}$.

  * •

Condition 2. Neighboring datasets $\mathcal{Y},\mathcal{Y}^{\prime}$ differ in
a single data element.

  * •

Condition 3. Let $\Delta$ be denoted as Definition 4.3 and $\Delta<1$.

  * •

Condition 4. Let $M,{\cal M}$ be denoted as Definition 4.2 and $M\leq\Delta$.

  * •

Condition 5. An input $\Sigma=\mathcal{M}(\mathcal{Y})$.

  * •

Condition 6.
$\rho=O(\sqrt{(n^{2}+\log(1/\gamma))/k}+(n^{2}+\log(1/\gamma))/{k})$.

Then, there exists an Algorithm 1 such that

  * •

Part 1. Algorithm 1 is $(\epsilon,\delta)$-DP.

  * •

Part 2. Outputs $\widehat{\Sigma}\in\mathbb{S}_{+}^{n}$ such that with
probabilities at least $1-\gamma$,

$\displaystyle\|\Sigma^{-1/2}\widehat{\Sigma}\Sigma^{-1/2}-I_{n}\|_{F}\leq\rho$

  * •

Part 3.

$\displaystyle(1-\rho)\Sigma\preceq\widehat{\Sigma}\preceq(1+\rho)\Sigma$

##  Appendix D Sensitivity of Neural Tangent Kernel

In this section, we provide proof of the sensitivity of the NTK Kernel Matrix.

In Section D.1, we demonstrate the sensitivity of Continuous Quadratic NTK
under $\beta$-close neighboring dataset.

Then, in Section D.2, we use concentration inequalities to bridge the gap
between Continuous Quadratic NTK and Discrete Quadratic NTK. Further we prove
the sensitivity of the Discrete Quadratic NTK under $\beta$-close neighboring
dataset.

Based on previous Section, we introduce the calculation for
$\|(H^{\mathrm{dis}})^{-1/2}{H^{\mathrm{dis}}}^{\prime}(H^{\mathrm{dis}})^{-1/2}-I\|_{F}$
in Section D.3, which plays a critical role in satisfying the requirements of
privacy guarantees.

###  D.1 Sensitivity of Continuous Quadratic NTK

We first introduce the fundamental property of the nested inner product.

######  Lemma D.1 (Nested inner product property).

For any $w,a,b\in\mathbb{R}^{d}$, we have

$\displaystyle\langle\langle w,a\rangle a,\langle w,b\rangle
b\rangle=w^{\top}aa^{\top}bb^{\top}w$

###### Proof.

$\displaystyle\langle\langle w,a\rangle a,\langle w,b\rangle b\rangle=$
$\displaystyle~{}\langle\langle w,a\rangle a,x\langle b,w\rangle\rangle$
$\displaystyle=$ $\displaystyle~{}\langle w^{\top}aa,bb^{\top}w\rangle$
$\displaystyle=$ $\displaystyle~{}w^{\top}aa^{\top}bb^{\top}w$

where the 1st step is because of $\langle w,b\rangle\in\mathbb{R}$, the 2nd
step is due to $\langle w,a\rangle=w^{\top}a$, the 3rd step is from basic
property of inner product. ∎

Then, we are ready to consider the Lipschitz property for each entry in the
Continuous Quadratic NTK Matrix. Since diagonal entries and off-diagonal
entries have different Lipschitz properties, we need to consider these two
cases separately.

We first consider the off-diagonal case.

######  Lemma D.2 (Lipschitz property for single entry (off-diagonal
entries)).

If we have the below conditions,

  * •

Let $B>0$ be a constant.

  * •

Let $n$ be the number of data points.

  * •

Let $m$ be the number of neurons.

  * •

Let dataset ${\cal D}=(X,Y)$, where $X\in\mathbb{R}^{n\times d}$ and
$Y\in\mathbb{R}^{n}$.

  * •

Let $x_{i}\in\mathbb{R}^{d}$ denote $X(i,*)$, and $\|x_{i}\|_{2}\leq B$, for
any $i\in[n]$.

  * •

Let ${\cal D^{\prime}}$ be the neighbor dataset (see Definition 4.1). Without
loss of generality, we assume that ${\cal D}$ and ${\cal D^{\prime}}$ only
differ in the $n$-th item.

  * •

Let $x:=x_{n}\in{\cal D}$ and $x^{\prime}:=x_{n}^{\prime}\in{\cal
D^{\prime}}$.

  * •

Let $H^{\mathrm{cts}}$ and ${H^{\mathrm{cts}}}^{\prime}$ be defined as
Definition 3.2, where
$H_{i,j}^{\mathrm{cts}}=\operatorname*{{\mathbb{E}}}_{w}\langle\langle
w,x_{i}\rangle x_{i},\langle w,x_{j}\rangle x_{j}\rangle$. And
${H^{\mathrm{cts}}}^{\prime}\in\mathbb{R}^{n\times n}$ is the kernel
corresponding to ${\cal D^{\prime}}$.

Then, we can show, for all $\\{(i,j):(i=n,j\neq n)or(i\neq
n,j=n),i,j\in[n]\\}$, we have

$\displaystyle|H^{\mathrm{cts}}_{i,j}-{H^{\mathrm{cts}}_{i,j}}^{\prime}|\leq
2\sigma^{2}B^{3}\cdot\|x-x^{\prime}\|_{2}$

###### Proof.

Without loss of generality, we only consider the $i=n,j\neq n$ case. The other
case follows by symmetry.

Let $v=x_{j}\in\mathbb{R}^{d}$.

Then, we have the following

$\displaystyle|H^{\mathrm{cts}}_{n,j}-{H^{\mathrm{cts}}_{n,j}}^{\prime}|=$
$\displaystyle~{}|\operatorname*{{\mathbb{E}}}_{w}[\langle\langle w,v\rangle
v,\langle w,x\rangle x\rangle]-\operatorname*{{\mathbb{E}}}_{w}[\langle\langle
w,v\rangle v,\langle w,x^{\prime}\rangle x^{\prime}\rangle]|$ $\displaystyle=$
$\displaystyle~{}|\operatorname*{{\mathbb{E}}}_{w}[\langle\langle w,v\rangle
v,\langle w,x\rangle x\rangle-\langle\langle w,v\rangle v,\langle
w,x^{\prime}\rangle x^{\prime}\rangle]|$

where the 1st step is because of the definition of $H^{\mathrm{cts}}_{i,j}$,
the 2nd step is due to the property of expectation.

Let $A:=vv^{\top}(xx^{\top}-x^{\prime}x^{\prime\top})\in\mathbb{R}^{d\times
d}$. Let $A(s,t)\in\mathbb{R}$ denotes the $(s,t)$-th entry of $A$.

Let $w(s)\in\mathbb{R}$ denote the $s$-th entry of $w\in\mathbb{R}^{d}$.

Further, we can calculate

$\displaystyle|\operatorname*{{\mathbb{E}}}_{w}[\langle\langle w,v\rangle
v,\langle w,x\rangle x\rangle-\langle\langle w,v\rangle v,\langle
w,x^{\prime}\rangle x^{\prime}\rangle]|=$
$\displaystyle~{}|\operatorname*{{\mathbb{E}}}_{w}[w^{\top}vv^{\top}(xx^{\top}-x^{\prime}x^{\prime\top})w]|$
$\displaystyle=$
$\displaystyle~{}|\operatorname*{{\mathbb{E}}}_{w}[w^{\top}Aw]|$
$\displaystyle=$
$\displaystyle~{}|\operatorname*{{\mathbb{E}}}_{w}[\sum_{s=1}^{d}w(s)^{2}A(s,s)]+\operatorname*{{\mathbb{E}}}_{w}[\sum_{s\neq
t}w(s)w(t)A(s,t)]|$ $\displaystyle=$
$\displaystyle~{}|\operatorname*{{\mathbb{E}}}_{w}[\sum_{s=1}^{d}w(s)^{2}A(s,s)]|$
$\displaystyle=$
$\displaystyle~{}|\operatorname*{{\mathbb{E}}}_{w}[\sum_{s=1}^{d}w(s)^{2}(vv^{\top}(xx^{\top}-x^{\prime}x^{\prime\top}))(s,s)]|$

where the 1st step is because of Lemma D.1 , the 2nd step is due to definition
of $A$, the 3rd step is from we separate the diagonal term and off-diagonal
term, the 4th step comes from
$\operatorname*{{\mathbb{E}}}[w(s)w(t)]=\operatorname*{{\mathbb{E}}}[w(s)]\operatorname*{{\mathbb{E}}}[w(t)]=0$
(when $w(s)$ and $w(t)$ are independent), the fifth step follows from the
definition of $A$.

Let $x(s)\in\mathbb{R}$ denotes the $s$-th entry of $x\in\mathbb{R}^{d}$. Let
$x(s)^{\prime}\in\mathbb{R}$ denotes the $s$-th entry of
$x^{\prime}\in\mathbb{R}^{d}$. Let $v(s)\in\mathbb{R}$ denotes the $s$-th
entry of $v\in\mathbb{R}^{d}$.

Then, we consider the
$\operatorname*{{\mathbb{E}}}_{w}[\sum_{s=1}^{d}w(s)^{2}(vv^{\top}xx^{\top})(s,s)]$
term. We have

$\displaystyle\operatorname*{{\mathbb{E}}}_{w}[\sum_{s=1}^{d}w(s)^{2}(vv^{\top}xx^{\top})(s,s)]=$
$\displaystyle~{}\sum_{s=1}^{d}(vv^{\top}xx^{\top})(s,s)\operatorname*{{\mathbb{E}}}_{w}[w(s)^{2}]$
$\displaystyle=$
$\displaystyle~{}\sigma^{2}\sum_{s=1}^{d}(vv^{\top}xx^{\top})(s,s)$
$\displaystyle=$
$\displaystyle~{}\sigma^{2}(v^{\top}x)\sum_{s=1}^{d}(vx^{\top})(s,s)$
$\displaystyle=$ $\displaystyle~{}\sigma^{2}(v^{\top}x)^{2}$ (2)

where the 1st step is because of the property of expectation, the 2nd step is
due to $\operatorname*{{\mathbb{E}}}_{w}[w_{i}^{2}]=\sigma^{2}$, the 3rd step
is from $v^{\top}x\in\mathbb{R}$, the 4th step comes from
$\sum_{s=1}^{d}(v\cdot x^{\top})(s,s)=v^{\top}x$.

Further, we can calculate

$\displaystyle~{}|\operatorname*{{\mathbb{E}}}_{w}[\sum_{s=1}^{d}w(s)^{2}(vv^{\top}xx^{\top}-x^{\prime}x^{\prime\top})(s,s)]|$
$\displaystyle=$
$\displaystyle~{}|\operatorname*{{\mathbb{E}}}_{w}[\sum_{s=1}^{d}w(s)^{2}(vv^{\top}xx^{\top})(s,s)]-\operatorname*{{\mathbb{E}}}_{w}[\sum_{s=1}^{d}w(s)^{2}(vv^{\top}x^{\prime}x^{\prime\top})(s,s)]|$
$\displaystyle=$
$\displaystyle~{}\sigma^{2}|(v^{\top}x)^{2}-(v^{\top}x^{\prime})^{2}|$

where the 1st step is because of linearity of expectation, the 2nd step is due
to Eq. (D.1).

Further, we can calculate

$\displaystyle\sigma^{2}|(v^{\top}x)^{2}-(v^{\top}x^{\prime})^{2}|=$
$\displaystyle~{}\sigma^{2}|v^{\top}(x+x^{\prime})|\cdot|v^{\top}(x-x^{\prime})|$
$\displaystyle\leq$
$\displaystyle~{}\sigma^{2}\|v\|_{2}\cdot\|x+x^{\prime}\|_{2}\cdot\|v\|_{2}\cdot\|x-x^{\prime}\|_{2}$
$\displaystyle\leq$ $\displaystyle~{}\sigma^{2}B\cdot 2B\cdot
B\cdot\|x-x^{\prime}\|_{2}$ $\displaystyle=$
$\displaystyle~{}2\sigma^{2}B^{3}\cdot\|x-x^{\prime}\|_{2}$

where the 1st step is because of $|a^{2}-b^{2}|=|a+b|\cdot|a-b|$ for any
$a,b\in\mathbb{R}$, the 2nd step is due to
$|v^{\top}(x+x^{\prime})|\leq\|v\|_{2}\cdot\|x+x^{\prime}\|_{2}$, the 3rd step
is from the property of inner product, the 4th step comes from $\|x\|_{2}\leq
B$, the fifth step follows from basic algebra.

Combining all components analysed above, we have

$\displaystyle|H^{\mathrm{cts}}_{i,j}-{H^{\mathrm{cts}}_{i,j}}^{\prime}|\leq
2\sigma^{2}B^{3}\cdot\|x-x^{\prime}\|_{2}$

∎

Similar to off-diagonal entries, we consider the diagonal entries case.

######  Lemma D.3 (Lipschitz of single entry (diagonal entries)).

If we have the below conditions,

  * •

Let $B>0$ be a constant.

  * •

Let $n$ be the number of data points.

  * •

Let $m$ be the number of neurons.

  * •

Let dataset ${\cal D}=(X,Y)$, where $X\in\mathbb{R}^{n\times d}$ and
$Y\in\mathbb{R}^{n}$.

  * •

Let $x_{i}\in\mathbb{R}^{d}$ denotes $X(i,*)$, and $\|x_{i}\|_{2}\leq B$, for
any $i\in[n]$.

  * •

Let ${\cal D^{\prime}}$ be the neighbor dataset. (See Definition 4.1) Without
loss of generality, we assume ${\cal D}$ and ${\cal D^{\prime}}$ only differ
in the $n$-th item.

  * •

Let $x:=x_{n}\in{\cal D}$ and $x^{\prime}:=x_{n}^{\prime}\in{\cal
D^{\prime}}$.

  * •

Let $H^{\mathrm{cts}}$ and ${H^{\mathrm{cts}}}^{\prime}$ be defined as
Definition 3.2, where
$H_{i,j}^{\mathrm{cts}}=\operatorname*{{\mathbb{E}}}_{w}\langle\langle
w,x_{i}\rangle x_{i},\langle w,x_{j}\rangle x_{j}\rangle$. And
${H^{\mathrm{cts}}}^{\prime}\in\mathbb{R}^{n\times n}$ is the kernel
corresponding to ${\cal D^{\prime}}$.

Then, we can show that

$\displaystyle|H^{\mathrm{cts}}_{n,n}-{H^{\mathrm{cts}}_{n,n}}^{\prime}|\leq
4\sigma^{2}B^{3}\cdot\|x-x^{\prime}\|_{2}$

###### Proof.

We have the following

$\displaystyle|H^{\mathrm{cts}}_{n,n}-{H^{\mathrm{cts}}_{n,n}}^{\prime}|=$
$\displaystyle~{}|\operatorname*{{\mathbb{E}}}_{w}[\langle\langle w,x\rangle
x,\langle w,x\rangle x\rangle]-\operatorname*{{\mathbb{E}}}_{w}[\langle\langle
w,x^{\prime}\rangle x^{\prime},\langle w,x^{\prime}\rangle
x^{\prime}\rangle]|$ $\displaystyle=$
$\displaystyle~{}|\operatorname*{{\mathbb{E}}}_{w}[\langle\langle w,x\rangle
x,\langle w,x\rangle x\rangle-\langle\langle w,x^{\prime}\rangle
x^{\prime},\langle w,x^{\prime}\rangle x^{\prime}\rangle]|$

where the 1st step is because of the definition of $H^{\mathrm{cts}}_{i,j}$,
the 2nd step is due to linearity of expectation.

Then, we have

$\displaystyle|\operatorname*{{\mathbb{E}}}_{w}[\langle\langle w,x\rangle
x,\langle w,x\rangle x\rangle-\langle\langle w,x^{\prime}\rangle
x^{\prime},\langle w,x^{\prime}\rangle x^{\prime}\rangle]|=$
$\displaystyle~{}|\operatorname*{{\mathbb{E}}}_{w}[w^{\top}xx^{\top}xx^{\top}w-w^{\top}x^{\prime}x^{\prime\top}x^{\prime}x^{\prime\top}w]|$
$\displaystyle=$
$\displaystyle~{}|\operatorname*{{\mathbb{E}}}_{w}[w^{\top}(xx^{\top}xx^{\top}-x^{\prime}x^{\prime\top}x^{\prime}x^{\prime\top})w]|$

where the 1st step is because of Lemma D.1 , the 2nd step is due to the basic
linear algebra.

Let
$A:=(xx^{\top}xx^{\top}-x^{\prime}x^{\prime\top}x^{\prime}x^{\prime\top})\in\mathbb{R}^{d\times
d}$. Let $A(s,t)\in\mathbb{R}$ denotes the $(s,t)$-th entry of $A$.

Let $w(s)\in\mathbb{R}$ denotes the the $s$-th entry of $w\in\mathbb{R}^{d}$.

Further, we can calculate

$\displaystyle|\operatorname*{{\mathbb{E}}}_{w}[w^{\top}(xx^{\top}xx^{\top}-x^{\prime}x^{\prime\top}x^{\prime}x^{\prime\top})w]|=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}_{w}[w^{\top}Aw]$
$\displaystyle=$
$\displaystyle~{}|\operatorname*{{\mathbb{E}}}_{w}[\sum_{s=1}^{d}w(s)^{2}A(s,s)]+\operatorname*{{\mathbb{E}}}_{w}[\sum_{s\neq
t}w(s)w(t)A(s,t)]|$ $\displaystyle=$
$\displaystyle~{}|\operatorname*{{\mathbb{E}}}_{w}[\sum_{s=1}^{d}w(s)^{2}A(s,s)]|$
$\displaystyle=$
$\displaystyle~{}|\operatorname*{{\mathbb{E}}}_{w}[\sum_{s=1}^{d}w(s)^{2}(xx^{\top}xx^{\top}-x^{\prime}x^{\prime\top}x^{\prime}x^{\prime\top})(s,s)]|$

where the 1st step is because of definition of $A$, the 2nd step is due to we
separate the diagonal and off-diagonal term, the 3rd step is from
$\operatorname*{{\mathbb{E}}}[w(s)w(t)]=\operatorname*{{\mathbb{E}}}[w(s)]\operatorname*{{\mathbb{E}}}[w(t)]=0$
(when $w(s)$ and $w(t)$ are independent), the 4th step comes from definition
of $A$.

Let $x(s)\in\mathbb{R}$ denotes the $s$-th entry of $x\in\mathbb{R}^{d}$. Let
$x(s)^{\prime}\in\mathbb{R}$ denotes the $s$-th entry of
$x^{\prime}\in\mathbb{R}^{d}$.

Then, we consider the
$\operatorname*{{\mathbb{E}}}_{w}[\sum_{s=1}^{d}w(s)^{2}(xx^{\top}xx^{\top})(s,s)]$
term. We have

$\displaystyle\operatorname*{{\mathbb{E}}}_{w}[\sum_{s=1}^{d}w(s)^{2}(xx^{\top}xx^{\top})(s,s)]=$
$\displaystyle~{}\sum_{s=1}^{d}(xx^{\top}xx^{\top})(s,s)\operatorname*{{\mathbb{E}}}_{w}[w(s)^{2}]$
$\displaystyle=$
$\displaystyle~{}\sigma^{2}\sum_{s=1}^{d}(xx^{\top}xx^{\top})(s,s)$
$\displaystyle=$
$\displaystyle~{}\sigma^{2}(x^{\top}x)\sum_{s=1}^{d}(xx^{\top})(s,s)$
$\displaystyle=$ $\displaystyle~{}\sigma^{2}(x^{\top}x)^{2}$ (3)

where the 1st step is because of linearity of expectation, the 2nd step is due
to $\operatorname*{{\mathbb{E}}}_{w}[w(s)^{2}]=\sigma^{2}$, the 3rd step is
from $x^{\top}x\in\mathbb{R}$, the 4th step comes from $\sum_{s=1}^{d}(x\cdot
x^{\top})(s,s)=x^{\top}x$.

Further, we can calculate

$\displaystyle~{}|\operatorname*{{\mathbb{E}}}_{w}[\sum_{s=1}^{d}w(s)^{2}(xx^{\top}xx^{\top}-x^{\prime}x^{\prime\top}x^{\prime}x^{\prime\top})(s,s)]|$
$\displaystyle=$
$\displaystyle~{}|\operatorname*{{\mathbb{E}}}_{w}[\sum_{s=1}^{d}w(s)^{2}(xx^{\top}xx^{\top})(s,s)]-\operatorname*{{\mathbb{E}}}_{w}[\sum_{s=1}^{d}w(s)^{2}(x^{\prime}x^{\prime\top}x^{\prime}x^{\prime\top})(s,s)]|$
$\displaystyle=$
$\displaystyle~{}\sigma^{2}|(x^{\top}x)^{2}-(x^{\prime\top}x^{\prime})^{2}|$
$\displaystyle=$
$\displaystyle~{}\sigma^{2}|\|x\|_{2}^{4}-\|x^{\prime}\|_{2}^{4}|$

where the 1st step is because of linearity of expectation, the 2nd step is due
to Eq. (D.1), the 3rd step is from $x^{\top}x=\|x\|_{2}^{2}$.

Further, we can calculate

$\displaystyle\sigma^{2}|\|x\|_{2}^{4}-\|x^{\prime}\|_{2}^{4}|=$
$\displaystyle~{}\sigma^{2}|\|x\|_{2}^{2}+\|x^{\prime}\|_{2}^{2}|\cdot|\|x\|_{2}+\|x^{\prime}\|_{2}|\cdot|\|x\|_{2}-\|x^{\prime}\|_{2}|$
$\displaystyle\leq$
$\displaystyle~{}\sigma^{2}|\|x\|_{2}^{2}+\|x^{\prime}\|_{2}^{2}|\cdot|\|x\|_{2}+\|x^{\prime}\|_{2}|\cdot\|x-x^{\prime}\|_{2}$
$\displaystyle\leq$ $\displaystyle~{}\sigma^{2}\cdot 2B^{2}\cdot
2B\cdot\|x-x^{\prime}\|_{2}$ $\displaystyle=$
$\displaystyle~{}4\sigma^{2}B^{3}\cdot\|x-x^{\prime}\|_{2}$

where the 1st step is because of $|a^{2}-b^{2}|=|a+b|\cdot|a-b|$ for any
$a,b\in\mathbb{R}$, the 2nd step is due to triangle inequality
$|\|x\|_{2}-\|x^{\prime}\|_{2}|\leq\|x-x^{\prime}\|_{2}$, the 3rd step is from
$\|x_{i}\|_{2}\leq B$, the 4th step comes from basic algebra.

Combining all components analysed above, we have

$\displaystyle|H^{\mathrm{cts}}_{n,n}-{H^{\mathrm{cts}}_{n,n}}^{\prime}|\leq
4\sigma^{2}B^{3}\cdot\|x-x^{\prime}\|_{2}$

∎

Having established the Lipschitz properties for both the diagonal and off-
diagonal entries, we are now equipped to demonstrate the sensitivity of the
Continuous Quadratic NTK Matrix with respect to $\beta$-close neighboring
datasets.

######  Lemma D.4 (Sensitivity of Continuous Quadratic NTK under $\beta$-close
neighboring dataset ).

If we have the below conditions,

  * •

Let $B>0$ be a constant.

  * •

Let $n$ be the number of data points.

  * •

We have dataset ${\cal D}=\\{(x_{i},y_{i})\\}_{i=1}^{n}$, where
$x_{i}\in\mathbb{R}^{d}$ and $\|x_{i}\|_{2}\leq B$ for any $i\in[n]$.

  * •

Let the neighbor dataset ${\cal D^{\prime}}$ be defined Definition 4.1.

  * •

Let the continuous quadratic kernel matrices $H^{\mathrm{cts}}$ and
${H^{\mathrm{cts}}}^{\prime}$ be defined as Definition 3.2, where
${H^{\mathrm{cts}}}^{\prime}\in\mathbb{R}^{n\times n}$ is the kernel
corresponding to ${\cal D^{\prime}}$. Without loss of generality, we have
${\cal D}$ and ${\cal D^{\prime}}$ only differ in the $n$-th item.

Then, we can show that

$\displaystyle\|H^{\mathrm{cts}}-{H^{\mathrm{cts}}}^{\prime}\|_{F}\leq
O(\sqrt{n}\sigma^{2}B^{3}\beta)$

###### Proof.

By Lemma D.2, we know that, for all $\\{(i,j):(i=n,j\neq n)or(i\neq
n,j=n),i,j\in[n]\\}$, we have

$\displaystyle|H^{\mathrm{cts}}_{i,j}-{H^{\mathrm{cts}}_{i,j}}^{\prime}|\leq
2\sigma^{2}B^{3}\cdot\|x-x^{\prime}\|_{2}$ (4)

By Lemma D.3, we know that

$\displaystyle|H^{\mathrm{cts}}_{n,n}-{H^{\mathrm{cts}}_{n,n}}^{\prime}|\leq
4\sigma^{2}B^{3}\cdot\|x-x^{\prime}\|_{2}$ (5)

By Definition 4.1, we have

$\displaystyle\|x-x^{\prime}\|_{2}\leq\beta$ (6)

There are $2n-2$ entries satisfy $\\{(i,j):(i=n,j\neq n)or(i\neq
n,j=n),i,j\in[n]\\}$. And there is $1$ entry satisfies $(i,j)=(n,n)$.

Therefore, we have

$\displaystyle\|H^{\mathrm{cts}}-{H^{\mathrm{cts}}}^{\prime}\|^{2}_{F}=$
$\displaystyle~{}(2n-2)(H^{\mathrm{cts}}_{i,j}-{H^{\mathrm{cts}}_{i,j}}^{\prime})^{2}+(H^{\mathrm{cts}}_{n,n}-{H^{\mathrm{cts}}_{n,n}}^{\prime})^{2}$
$\displaystyle\leq$ $\displaystyle~{}(2n-2)\cdot
4\sigma^{4}B^{6}\|x-x^{\prime}\|_{2}^{2}+16\sigma^{4}B^{6}\|x-x^{\prime}\|_{2}^{2}$
$\displaystyle\leq$ $\displaystyle~{}(2n-2)\cdot
4\sigma^{4}B^{6}\cdot\beta^{2}+16\sigma^{4}B^{6}\cdot\beta^{2}$
$\displaystyle=$ $\displaystyle~{}O(n\sigma^{4}B^{6}\beta^{2})$

where the 1st step is because of definition of $\|\cdot\|_{F}$, the 2nd step
is due to Eq. (4) and Eq. (5), the 3rd step is from Eq. (6), the 4th step
comes from basic algebra.

Therefore, we have

$\displaystyle\|H^{\mathrm{cts}}-{H^{\mathrm{cts}}}^{\prime}\|_{F}\leq
O(\sqrt{n}\sigma^{2}B^{3}\beta)$

∎

###  D.2 Sensitivity of Discrete Quadratic NTK

After calculating the sensitivity of the Continuous Quadratic NTK Matrix in
the previous section, we are going to use Bernstein Inequality to bridge the
gap between Continuous and Discrete Quadratic NTK Matrices, where eventually
we are going to demonstrate the sensitivity of Discrete Quadratic NTK under
$\beta$-close neighboring dataset.

We first introduce a fundamental and useful property of a single entry of the
Continuous Quadratic NTK Matrix.

######  Lemma D.5 (Close form of $H^{\mathrm{cts}}_{i,j}$).

If we have the below conditions,

  * •

Let $H^{\mathrm{dis}}$ be define in Definition 3.1. Namely,
$H_{i,j}^{\mathrm{dis}}=\frac{1}{m}\sum_{r=1}^{m}\langle\langle
w_{r},x_{i}\rangle x_{i},\langle w_{r},x_{j}\rangle x_{j}\rangle$.

  * •

Let $H^{\mathrm{cts}}$ be define in Definition 3.2. Namely,
$H_{i,j}^{\mathrm{cts}}=\operatorname*{{\mathbb{E}}}_{w\sim{\cal
N}(0,\sigma^{2}I_{d\times d})}\langle\langle w,x_{i}\rangle x_{i},\langle
w,x_{j}\rangle x_{j}\rangle$.

Then we have

$\displaystyle\operatorname*{{\mathbb{E}}}_{w}[H_{i,j}^{\mathrm{dis}}]=$
$\displaystyle~{}H_{i,j}^{\mathrm{cts}}$ $\displaystyle
H_{i,j}^{\mathrm{cts}}=$ $\displaystyle~{}\sigma^{2}(x_{i}^{\top}x_{j})^{2}$

###### Proof.

We have the following equation

$\displaystyle\operatorname*{{\mathbb{E}}}_{w}[H_{i,j}^{\mathrm{dis}}]=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}_{w}[\frac{1}{m}\sum_{r=1}^{m}\langle\langle
w_{r},x_{i}\rangle x_{i},\langle w_{r},x_{j}\rangle x_{j}\rangle]$
$\displaystyle=$
$\displaystyle~{}\frac{1}{m}\sum_{r=1}^{m}\operatorname*{{\mathbb{E}}}_{w_{r}}[\langle\langle
w_{r},x_{i}\rangle x_{i},\langle w_{r},x_{j}\rangle x_{j}\rangle]$
$\displaystyle=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}_{w}[\langle\langle
w,x_{i}\rangle x_{i},\langle w,x_{j}\rangle x_{j}\rangle]$ $\displaystyle=$
$\displaystyle~{}H_{i,j}^{\mathrm{cts}}$

where the 1st step is because of the definition of $H_{i,j}^{\mathrm{dis}}$,
the 2nd step is due to the linearity of expectation, the 3rd step is from
$w_{r}$ are i.i.d. , the 4th step comes from the definition of
$H_{i,j}^{\mathrm{cts}}$.

$\displaystyle H_{i,j}^{\mathrm{cts}}\leq\sigma^{2}B^{4}$

Then, we can calculate the following

$\displaystyle H_{i,j}^{\mathrm{cts}}=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}_{w}[\langle\langle
w,x_{i}\rangle x_{i},\langle w,x_{j}\rangle x_{j}\rangle]$ $\displaystyle=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}_{w}[w^{\top}x_{i}x_{i}^{\top}x_{j}x_{j}^{\top}w]|$
$\displaystyle=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}_{w}[\sum_{s=1}^{d}w(s)^{2}(x_{i}x_{i}^{\top}x_{j}x_{j}^{\top})(s,s)]+\operatorname*{{\mathbb{E}}}_{w}[\sum_{s\neq
t}w(s)w(t)(x_{i}x_{i}^{\top}x_{j}x_{j}^{\top})(s,t)]$ $\displaystyle=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}_{w}[\sum_{s=1}^{d}w(s)^{2}(x_{i}x_{i}^{\top}x_{j}x_{j}^{\top})(s,s)]$
$\displaystyle=$
$\displaystyle~{}\sigma^{2}\sum_{s=1}^{d}(x_{i}x_{i}^{\top}x_{j}x_{j}^{\top})(s,s)$
$\displaystyle=$ $\displaystyle~{}\sigma^{2}\cdot\langle
x_{i},x_{j}\rangle\sum_{s=1}^{d}(x_{i}x_{j}^{\top})(s,s)$ $\displaystyle=$
$\displaystyle~{}\sigma^{2}(\langle x_{i},x_{j}\rangle)^{2}$

where the 1st step is because of the definition of $H_{i,j}^{\mathrm{cts}}$,
the 2nd step is due to Lemma D.1, the 3rd step is from we separate the
diagonal term and off-diagonal term, the 4th step comes from
$\operatorname*{{\mathbb{E}}}[w(s)w(t)]=\operatorname*{{\mathbb{E}}}[w(s)]\operatorname*{{\mathbb{E}}}[w(t)]=0$
(when $w(s)$ and $w(t)$ are independent), the fifth step follows from
$\operatorname*{{\mathbb{E}}}_{w}[w(s)^{2}]=\sigma^{2}$, the sixth step
follows from $x_{i}^{\top}x_{j}\in\mathbb{R}$, the seventh step follows from
$\sum_{s=1}^{d}(x_{i}x_{j}^{\top})(s,s)=x_{i}^{\top}x_{j}\in\mathbb{R}$.

∎

In order to use Bernstein Inequality, we need to bound the value ranges of
random variables,as well as the variance of random variables.

We first consider the value range of $\|w_{r}\|_{2}^{2}$.

######  Lemma D.6 (Upper bound $\|w_{r}\|_{2}^{2}$ ).

If we have the below conditions,

  * •

Let $w_{r}\sim{\cal N}(0,\sigma^{2}I_{d\times d})$.

  * •

Let $\delta_{1}\in(0,1)$.

  * •

Let $t\geq\Omega(\log(1/\delta_{1}))$

Then, with probability $1-\delta_{1}$, we have

$\displaystyle\|w_{r}\|_{2}^{2}\leq 3(t+d)\sigma^{2}$

###### Proof.

Let $w_{r}(s)\in\mathbb{R}$ denotes the $s$-th entry of
$w_{r}\in\mathbb{R}^{d}$.

We consider $\|w_{r}\|_{2}^{2}$. We have

$\displaystyle\|w_{r}\|_{2}^{2}=\sum_{s=1}^{d}w_{r}(s)^{2}$

Since for each $s\in[d]$, $w_{r}(s)\sim{\cal N}(0,\sigma)$, then
$\|w_{r}\|_{2}^{2}\sim\chi^{2}_{d}$, where each one has zero means and
$\sigma^{2}$ variance.

By Chi-Square tail bound (Lemma A.1), we have

$\displaystyle\Pr[\|w_{r}\|_{2}^{2}-d\sigma^{2}\geq(2\sqrt{dt}+2t)\sigma^{2}]\leq$
$\displaystyle~{}\exp{(-t)}$ (7)

Our goal is to choose $t$ sufficiently large, such that the above quantity is
upper bounded by $\delta_{1}$.

We choose $t\geq\Omega(\log(mn/\delta_{1}))$, and substitute $t$ in Eq. (7).
Then we have

$\displaystyle\Pr[\|w_{r}\|_{2}^{2}\geq(2\sqrt{dt}+2t+d)\sigma^{2}]\leq$
$\displaystyle~{}\delta_{1}/\operatorname{poly}(m,n)$

which is equivalent to

$\displaystyle\Pr[\|w_{r}\|_{2}^{2}\leq(2\sqrt{dt}+2t+d)\sigma^{2}]\geq$
$\displaystyle~{}1-\delta_{1}/\operatorname{poly}(m,n)$

Since $(2\sqrt{dt}+2t+d)\leq 2(\sqrt{dt}+t+d)\leq 3(t+d)$, then we have

$\displaystyle\Pr[\|w_{r}\|_{2}^{2}\leq 3(t+d)\sigma^{2}]\geq$
$\displaystyle~{}1-\delta_{1}/\operatorname{poly}(m)$

∎

After calculating the value range of $\|w_{r}\|_{2}^{2}$, we are ready to
prove the value range of random variables $Z_{r}$.

######  Lemma D.7 (Upper bound $Z_{r}$ ).

If we have the below conditions,

  * •

Let $H^{\mathrm{dis}}\in\mathbb{R}^{n\times n}$ be define in Definition 3.1.
Namely, $H_{i,j}^{\mathrm{dis}}=\frac{1}{m}\sum_{r=1}^{m}\langle\langle
w_{r},x_{i}\rangle x_{i},\langle w_{r},x_{j}\rangle x_{j}\rangle$, for any
$i,j\in[n]$.

  * •

Let $\Xi_{r}:=\langle\langle w_{r},x_{i}\rangle x_{i},\langle
w_{r},x_{j}\rangle x_{j}\rangle$, where $\Xi_{r}\in\mathbb{R}$.

  * •

Let $Z_{r}:=\Xi_{r}-\operatorname*{{\mathbb{E}}}_{w_{r}}[\Xi_{r}]$, where
$\operatorname*{{\mathbb{E}}}[Z_{r}]=0$.

  * •

Let $\delta_{1}\in(0,1)$

  * •

Let $d\geq\Omega(\log(1/\delta_{1}))$

Then, with probability $1-\delta_{1}$, we have

  * •

Part 1. $|\Xi_{r}|\leq 6d\sigma^{2}B^{4}$

  * •

Part 2. $|Z_{r}|\leq 6d\sigma^{2}B^{4}$

###### Proof.

Proof of Part 1. For any $r\in[m]$, we have

$\displaystyle\Xi_{r}=$ $\displaystyle~{}\langle w_{r},x_{i}\rangle\langle
w_{r},x_{j}\rangle\langle x_{i},x_{j}\rangle$ $\displaystyle\leq$
$\displaystyle~{}\|w_{r}\|_{2}^{2}\cdot\|x_{i}\|_{2}^{2}\cdot\|x_{j}\|_{2}^{2}$
$\displaystyle\leq$ $\displaystyle~{}\|w_{r}\|_{2}^{2}\cdot B^{4}$

where the 1st step is because of $\langle a,b\rangle\leq\|a\|_{2}\|b\|_{2}$
for any $a,b\in\mathbb{R}^{d}$ holds, the 2nd step is due to
$\|x_{i}\|_{2}\leq B$.

By Lemma D.6,for any $\delta_{1}\in(0,1)$, if
$t\geq\Omega(\log(1/\delta_{1}))$ we have the following holds

$\displaystyle\Pr[\|w_{r}\|_{2}^{2}\leq 3(t+d)\sigma^{2}]\geq$
$\displaystyle~{}1-\delta_{1}$

Proof of Part 2. Then, we have

$\displaystyle\Pr[\Xi_{r}\leq 3(t+d)\sigma^{2}B^{4}]\geq$
$\displaystyle~{}1-\delta_{1}$

Since $\Xi_{r}=\langle w_{r},x_{i}\rangle\langle w_{r},x_{j}\rangle\langle
x_{i},x_{j}\rangle$, and $\langle a,b\rangle\geq 0$ holds for any
$a,b\in\mathbb{R}^{d}$, then we have

$\displaystyle\Xi_{r}\geq$ $\displaystyle~{}0$
$\displaystyle\operatorname*{{\mathbb{E}}}[\Xi_{r}]\geq$ $\displaystyle~{}0$

Then, we consider $|Z_{r}|$. We have

$\displaystyle|Z_{r}|=$
$\displaystyle~{}|\Xi_{r}-\operatorname*{{\mathbb{E}}}[\Xi_{r}]|$
$\displaystyle\leq$ $\displaystyle~{}|\Xi_{r}|$

where the 1st step is because of the definition of $Z_{r}$, the 2nd step is
due to $\Xi_{r}\geq 0$.

Combining all analyses above, we have

$\displaystyle\Pr[|Z_{r}|\leq 3(t+d)\sigma^{2}B^{4}]\geq$
$\displaystyle~{}1-\delta_{1}$

We choose $d\geq\Omega(\log(mn/\delta_{1}))$. We have

$\displaystyle\Pr[|Z_{r}|\leq 6d\sigma^{2}B^{4}]\geq 1-\delta_{1}$

∎

So far, we have bounded the value range of random variables. We are going to
bound the variance of random variables. Since we have the Expectation of
random variables are $0$, we only need to consider the second moment of random
variables.

######  Lemma D.8 (Second moment of $\Xi_{r}$).

If we have the below conditions,

  * •

Let $H^{\mathrm{dis}}\in\mathbb{R}^{n\times n}$ be define in Definition 3.1.
Namely, $H_{i,j}^{\mathrm{dis}}=\frac{1}{m}\sum_{r=1}^{m}\langle\langle
w_{r},x_{i}\rangle x_{i},\langle w_{r},x_{j}\rangle x_{j}\rangle$, for any
$i,j\in[n]$

  * •

Let $\Xi_{r}:=\langle\langle w_{r},x_{i}\rangle x_{i},\langle
w_{r},x_{j}\rangle x_{j}\rangle$, where $\Xi_{r}\in\mathbb{R}$.

Then we have

$\displaystyle\operatorname*{{\mathbb{E}}}_{w_{r}}[\Xi_{r}^{2}]=(\sum_{s=1}^{d}x_{i}(s)x_{j}(s))^{2}\cdot(3\sigma^{2}(\sum_{s=1}^{d}x_{i}(s)^{2}x_{j}(s)^{2})+2\sigma^{4}(\sum_{s\neq
t}x_{i}(s)^{2}x_{j}(t)^{2}))$

###### Proof.

Let $v(s)\in\mathbb{R}$ denotes the $s$-th entry of any $v\in\mathbb{R}^{d}$.

Then, we have

$\displaystyle\Xi_{r}=$ $\displaystyle~{}\langle\langle w_{r},x_{i}\rangle
x_{i},\langle w_{r},x_{j}\rangle x_{j}\rangle$ $\displaystyle=$
$\displaystyle~{}w_{r}^{\top}x_{i}x_{i}^{\top}x_{j}x_{j}^{\top}w$
$\displaystyle=$
$\displaystyle~{}(\sum_{s=1}^{d}x_{i}(s)w_{r}(s))\cdot(\sum_{s=1}^{d}x_{i}(s)x_{j}(s))\cdot(\sum_{s=1}^{d}x_{j}(s)w_{r}(s))$
(8)

where the 1st step is because of the definition of $\Xi_{r}$, the 2nd step is
due to Lemma D.1, the 3rd step is from $\langle
a,b\rangle=\sum_{s=1}^{d}a(s)b(s)$ holds for any $a,b\in\mathbb{R}^{d}$.

Then, we have

$\displaystyle\Xi_{r}^{2}=$
$\displaystyle~{}(\sum_{s=1}^{d}x_{i}(s)w_{r}(s))^{2}\cdot(\sum_{s=1}^{d}x_{i}(s)x_{j}(s))^{2}\cdot(\sum_{s=1}^{d}x_{j}(s)w_{r}(s))^{2}$
$\displaystyle=$ $\displaystyle~{}(\sum_{s=1}^{d}x_{i}(s)x_{j}(s))^{2}$
$\displaystyle~{}\cdot(\sum_{s=1}^{d}x_{i}(s)^{2}w_{r}(s)^{2}+\sum_{s\neq
t}x_{i}(s)x_{i}(t)w_{r}(s)w_{r}(t))$
$\displaystyle~{}\cdot(\sum_{s=1}^{d}x_{j}(s)^{2}w_{r}(s)^{2}+\sum_{s\neq
t}x_{j}(s)x_{j}(t)w_{r}(s)w_{r}(t))$ (9)

where the 1st step is because of Eq. (D.2), the 2nd step is due to we separate
the diagonal and off-diagonal term.

We reorganize Eq. (D.2), into the following format

$\displaystyle\Xi_{r}^{2}=C_{0}(T_{1}+T_{2}+T_{3}+T_{4})$

where

$\displaystyle C_{0}=$ $\displaystyle~{}(\sum_{s=1}^{d}x_{i}(s)x_{j}(s))^{2}$
$\displaystyle T_{1}=$
$\displaystyle~{}(\sum_{s=1}^{d}x_{i}(s)^{2}w_{r}(s)^{2})(\sum_{s=1}^{d}x_{j}(s)^{2}w_{r}(s)^{2})$
$\displaystyle T_{2}=$
$\displaystyle~{}(\sum_{s=1}^{d}x_{i}(s)^{2}w_{r}(s)^{2})(\sum_{s\neq
t}x_{j}(s)x_{j}(t)w_{r}(s)w_{r}(t))$ $\displaystyle T_{3}=$
$\displaystyle~{}(\sum_{s\neq
t}x_{i}(s)x_{i}(t)w_{r}(s)w_{r}(t))(\sum_{s=1}^{d}x_{j}(s)^{2}w_{r}(s)^{2})$
$\displaystyle T_{4}=$ $\displaystyle~{}(\sum_{s\neq
t}x_{i}(s)x_{i}(t)w_{r}(s)w_{r}(t))(\sum_{s\neq
t}x_{j}(s)x_{j}(t)w_{r}(s)w_{r}(t))$

We consider $T_{1}$. We have

$\displaystyle T_{1}=$
$\displaystyle~{}\sum_{s=1}^{d}x_{i}(s)^{2}x_{j}(s)^{2}w_{r}(s)^{4}+\sum_{s\neq
j}x_{i}(s)^{2}x_{j}(t)^{2}w_{r}(s)^{2}w_{r}(t)^{2}$

Then, we have

$\displaystyle\operatorname*{{\mathbb{E}}}[T_{1}]=$
$\displaystyle~{}3\sigma^{2}(\sum_{s=1}^{d}x_{i}(s)^{2}x_{j}(s)^{2})+\operatorname*{{\mathbb{E}}}[\sum_{s\neq
j}x_{i}(s)^{2}x_{j}(t)^{2}w_{r}(s)^{2}w_{r}(t)^{2}]$ $\displaystyle=$
$\displaystyle~{}3\sigma^{2}(\sum_{s=1}^{d}x_{i}(s)^{2}x_{j}(s)^{2})+\sigma^{4}(\sum_{s\neq
j}x_{i}(s)^{2}x_{j}(t)^{2})$

where the 1st step is because of
$\operatorname*{{\mathbb{E}}}[w_{r}(s)^{4}]=2\sigma^{2}$, the 2nd step is due
to $\operatorname*{{\mathbb{E}}}[W_{r}(s)^{2}]=\sigma^{2}$.

We consider $T_{2}$. We know that for each single term in $T_{2}$, it must
contain one of the following terms

  * •

$w_{r}(s)^{3}w_{r}(t)$

  * •

$w_{r}(s)w_{r}(t)^{3}$

  * •

$w_{r}(s)w_{r}(t)w_{r}(k)^{2}$

Since we have $\operatorname*{{\mathbb{E}}}[w_{r}(s)]=0$, then we can have

$\displaystyle\operatorname*{{\mathbb{E}}}[T_{2}]=0$

The same analysis can be applied to $T_{3}$. Then we have

$\displaystyle\operatorname*{{\mathbb{E}}}[T_{3}]=0$

We consider $T_{4}$. We have

$\displaystyle\operatorname*{{\mathbb{E}}}[T_{4}]=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}[(\sum_{s\neq
t}x_{i}(s)x_{i}(t)w_{r}(s)w_{r}(t))(\sum_{s\neq
t}x_{j}(s)x_{j}(t)w_{r}(s)w_{r}(t))]$ $\displaystyle=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}[\sum_{s\neq
t}x_{i}(s)^{2}x_{i}(t)^{2}w_{r}(s)^{2}w_{r}(t)^{2}]$ $\displaystyle=$
$\displaystyle~{}\sigma^{4}\cdot(\sum_{s\neq t}x_{i}(s)^{2}x_{i}(t)^{2})$

where the 1st step is because of the definition of $T_{4}$, the 2nd step is
due to similar analysis of $T_{2}$ and $T_{3}$, the 3rd step is from
$\operatorname*{{\mathbb{E}}}[w_{r}(s)]=\sigma^{2}$.

Then we consider $\Xi_{r}^{2}$. We have

$\displaystyle\operatorname*{{\mathbb{E}}}[\Xi_{r}^{2}]=$
$\displaystyle~{}C_{0}(\operatorname*{{\mathbb{E}}}[T_{1}]+\operatorname*{{\mathbb{E}}}[T_{2}]+\operatorname*{{\mathbb{E}}}[T_{3}]+\operatorname*{{\mathbb{E}}}[T_{4}])$
$\displaystyle=$
$\displaystyle~{}(\sum_{s=1}^{d}x_{i}(s)x_{j}(s))^{2}\cdot(3\sigma^{2}(\sum_{s=1}^{d}x_{i}(s)^{2}x_{j}(s)^{2})+2\sigma^{4}(\sum_{s\neq
j}x_{i}(s)^{2}x_{j}(t)^{2}))$

where the 1st step is because of linearity of expectation, the 2nd step is due
to above analysis about
$\operatorname*{{\mathbb{E}}}[T_{1}],\operatorname*{{\mathbb{E}}}[T_{2}],\operatorname*{{\mathbb{E}}}[T_{3}],\operatorname*{{\mathbb{E}}}[T_{4}]$.

∎

Since we have $Z_{r}:=\Xi_{r}-\operatorname*{{\mathbb{E}}}_{w_{r}}[\Xi_{r}]$,
then $\operatorname*{{\mathbb{E}}}[Z_{r}]=0$. We can bound variance of $Z_{r}$
by harnessing the power of the bound of second moment of $Z_{r}$, which can be
formally expressed as follows.

######  Lemma D.9 (variance of $Z_{r}$).

If we have the below conditions,

  * •

Let $H^{\mathrm{dis}}\in\mathbb{R}^{n\times n}$ be define in Definition 3.1.
Namely, $H_{i,j}^{\mathrm{dis}}=\frac{1}{m}\sum_{r=1}^{m}\langle\langle
w_{r},x_{i}\rangle x_{i},\langle w_{r},x_{j}\rangle x_{j}\rangle$, for any
$i,j\in[n]$.

  * •

Let $\Xi_{r}:=\langle\langle w_{r},x_{i}\rangle x_{i},\langle
w_{r},x_{j}\rangle x_{j}\rangle$, where $\Xi_{r}\in\mathbb{R}$.

  * •

Let $Z_{r}:=\Xi_{r}-\operatorname*{{\mathbb{E}}}_{w_{r}}[\Xi_{r}]$, where
$\operatorname*{{\mathbb{E}}}[Z_{r}]=0$.

Then, we have

$\displaystyle\mathrm{Var}[Z_{r}]\leq 6B^{8}\sigma^{4}$

###### Proof.

We consider $\operatorname*{{\mathbb{E}}}[Z_{r}^{2}]$. We have

$\displaystyle\operatorname*{{\mathbb{E}}}[Z_{r}^{2}]=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}[(\Xi_{r}-\operatorname*{{\mathbb{E}}}[\Xi_{r}])^{2}]$
$\displaystyle=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}[\Xi_{r}^{2}-2\operatorname*{{\mathbb{E}}}[\Xi_{r}]\Xi_{r}+\operatorname*{{\mathbb{E}}}[\Xi_{r}]^{2}]$
$\displaystyle=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}[\Xi_{r}^{2}]-\operatorname*{{\mathbb{E}}}[\Xi_{r}]$

where the 1st step is because of the definition of $Z_{r}$, the 2nd step is
due to basic algebra, the 3rd step is from linearity of expectation.

By Lemma D.5, we have

$\displaystyle\operatorname*{{\mathbb{E}}}[\Xi_{r}]=\sigma^{2}(\sum_{s=1}x_{i}(s)x_{j}(s))^{2}$

By Lemma D.8, we have

$\displaystyle\operatorname*{{\mathbb{E}}}[\Xi_{r}^{2}]=(\sum_{s=1}^{d}x_{i}(s)x_{j}(s))^{2}\cdot(3\sigma^{2}(\sum_{s=1}^{d}x_{i}(s)^{2}x_{j}(s)^{2})+2\sigma^{4}(\sum_{s\neq
j}x_{i}(s)^{2}x_{j}(t)^{2}))$

Then, we have

$\displaystyle\operatorname*{{\mathbb{E}}}[Z_{r}^{2}]=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}[\Xi_{r}^{2}]-\operatorname*{{\mathbb{E}}}[\Xi_{r}]$
$\displaystyle=$
$\displaystyle~{}(\sum_{s=1}^{d}x_{i}(s)x_{j}(s))^{2}\cdot(3\sigma^{2}(\sum_{s=1}^{d}x_{i}(s)^{2}x_{j}(s)^{2})+2\sigma^{4}(\sum_{s\neq
j}x_{i}(s)^{2}x_{j}(t)^{2})-\sigma^{2})$ (10)

Then, we have

$\displaystyle\mathrm{Var}[Z_{r}]=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}[Z_{r}^{2}]-(\operatorname*{{\mathbb{E}}}[Z_{r}])^{2}$
$\displaystyle=$ $\displaystyle~{}\operatorname*{{\mathbb{E}}}[Z_{r}^{2}]$
$\displaystyle=$
$\displaystyle~{}(\sum_{s=1}^{d}x_{i}(s)x_{j}(s))^{2}\cdot(3\sigma^{2}(\sum_{s=1}^{d}x_{i}(s)^{2}x_{j}(s)^{2})+2\sigma^{4}(\sum_{s\neq
j}x_{i}(s)^{2}x_{j}(t)^{2})-\sigma^{2})$

where the 1st step is because of
$\mathrm{Var}[X]=\operatorname*{{\mathbb{E}}}[X^{2}]-\operatorname*{{\mathbb{E}}}[X]^{2}$
holds for any random variable $X$, the 2nd step is due to
$\operatorname*{{\mathbb{E}}}[Z_{r}]=0$, the 3rd step is from Eq. (D.2).

Then, we have

$\displaystyle\mathrm{Var}[Z_{r}]\leq$
$\displaystyle~{}3(\sum_{s=1}^{d}x_{i}(s)x_{j}(s))^{2}\cdot(\sigma^{2}(\sum_{s=1}^{d}x_{i}(s)^{2}x_{j}(s)^{2})+\sigma^{4}(\sum_{s\neq
j}x_{i}(s)^{2}x_{j}(t)^{2}))$ $\displaystyle\leq$
$\displaystyle~{}3\|x_{i}\|_{2}^{2}\cdot\|x_{j}\|_{2}^{2}\cdot(\sigma^{2}(\sum_{s=1}^{d}x_{i}(s)^{2}x_{j}(s)^{2})+\sigma^{4}(\sum_{s\neq
j}x_{i}(s)^{2}x_{j}(t)^{2}))$ $\displaystyle\leq$
$\displaystyle~{}3B^{4}\cdot(\sigma^{2}(\sum_{s=1}^{d}x_{i}(s)^{2}x_{j}(s)^{2})+\sigma^{4}(\sum_{s\neq
j}x_{i}(s)^{2}x_{j}(t)^{2}))$ $\displaystyle\leq$
$\displaystyle~{}3B^{4}\cdot(\sigma^{2}(\sum_{s=1}^{d}x_{i}(s)^{2})(\sum_{s=1}^{d}x_{j}(s)^{2})+\sigma^{4}(\sum_{s\neq
j}x_{i}(s)^{2}x_{j}(t)^{2}))$ $\displaystyle\leq$
$\displaystyle~{}3B^{4}\cdot(\sigma^{2}(\sum_{s=1}^{d}x_{i}(s)^{2})(\sum_{s=1}^{d}x_{j}(s)^{2})+\sigma^{4}(\sum_{s=1}^{d}x_{i}(s)^{2})(\sum_{s=1}^{d}x_{j}(s)^{2}))$
$\displaystyle\leq$
$\displaystyle~{}3B^{4}\cdot(\sigma^{2}B^{4}+\sigma^{4}B^{4})$
$\displaystyle=$ $\displaystyle~{}3B^{8}(\sigma^{2}+\sigma^{4})$

where the 1st step is because of basic inequality, the 2nd step is due to
$x_{i}^{\top}x_{j}\leq\|x_{i}\|_{2}\|x_{j}\|_{2}$, the 3rd step is from
$\|x_{i}\|_{2}\leq B$, the 4th step comes from
$\sum_{s=1}^{d}x_{i}(s)^{2}x_{j}(s)^{2}\leq(\sum_{s=1}^{d}x_{i}(s)^{2})(\sum_{s=1}^{d}x_{j}(s)^{2})$,
the fifth step follows from $\sum_{s\neq
j}x_{i}(s)^{2}x_{j}(t)^{2}\leq(\sum_{s=1}^{d}x_{i}(s)^{2})(\sum_{s=1}^{d}x_{j}(s)^{2})$,
the sixth step follows from $\|x_{i}\|_{2}\leq B$, the seventh step follows
from basic algebra.

We assume $\delta^{2}\geq 1$. Then we have

$\displaystyle\mathrm{Var}[Z_{r}]\leq 6B^{8}\sigma^{4}$

∎

Since we have bounded the value range and variance of $Z_{r}$, we are ready to
adapt Bernstein inequality to each entry of the Discrete Quadratic NTK Matrix.
Therefore, we have the following Lemma.

######  Lemma D.10 (Bernstein Inequality for
$|H_{i,j}^{\mathrm{dis}}-H_{i,j}^{\mathrm{cts}}|$ ).

If we have the below conditions,

  * •

Let $H^{\mathrm{dis}}\in\mathbb{R}^{n\times n}$ be define in Definition 3.1.
Namely, $H_{i,j}^{\mathrm{dis}}=\frac{1}{m}\sum_{r=1}^{m}\langle\langle
w_{r},x_{i}\rangle x_{i},\langle w_{r},x_{j}\rangle x_{j}\rangle$, for any
$i,j\in[n]$.

  * •

Let $H^{\mathrm{cts}}\in\mathbb{R}^{n\times n}$ be define in Definition 3.2.
Namely, $H_{i,j}^{\mathrm{cts}}=\operatorname*{{\mathbb{E}}}_{w\sim{\cal
N}(0,\sigma^{2}I_{d\times d})}\langle\langle w,x_{i}\rangle x_{i},\langle
w,x_{j}\rangle x_{j}\rangle$, for any $i,j\in[n]$.

  * •

Let $\Xi_{r}:=\langle\langle w_{r},x_{i}\rangle x_{i},\langle
w_{r},x_{j}\rangle x_{j}\rangle$, where $\Xi_{r}\in\mathbb{R}$.

  * •

Let $Z_{r}:=\Xi_{r}-\operatorname*{{\mathbb{E}}}_{w_{r}}[\Xi_{r}]$, where
$\operatorname*{{\mathbb{E}}}[Z_{r}]=0$.

  * •

Let $\delta_{1},\delta_{2}\in(0,1)$. Let
$\delta_{1}=\delta_{2}/\operatorname{poly}(m)$.

  * •

Let $d=\Omega(\log(1/\delta_{1}))$

  * •

Let $m=\Omega({\epsilon_{1}}^{-2}dB^{8}\sigma^{4}\log(1/\delta_{2}))$.

Then, with probability $1-\delta_{2}$, we have

$\displaystyle|H_{i,j}^{\mathrm{dis}}-H_{i,j}^{\mathrm{cts}}|\leq{\epsilon_{1}}$

###### Proof.

Let $X_{r}:=\frac{1}{m}Z_{r}$. Then we have
$\operatorname*{{\mathbb{E}}}[X_{r}]=0$.

Let $X:=\sum_{r=1}^{m}X_{r}$.

By Lemma D.7, with probability $1-\delta_{1}$, we have

$\displaystyle|Z_{r}|\leq 6d\sigma^{2}B^{4}$

which implies

$\displaystyle|X_{r}|\leq 6d\sigma^{2}B^{4}m^{-1}\ $ (11)

By Lemma D.9, we have

$\displaystyle\mathrm{Var}[Z_{r}]\leq$ $\displaystyle~{}6B^{8}\sigma^{4}$

which implies

$\displaystyle\mathrm{Var}[X_{r}]\leq$
$\displaystyle~{}6B^{8}\sigma^{4}m^{-2}$ (12)

Applying Lemma A.2, we have

$\displaystyle\Pr[X>t]\leq\exp(-\frac{t^{2}/2}{m\operatorname*{{\mathbb{E}}}[X_{r}^{2}]+Mt/3})$
(13)

where

$\displaystyle\operatorname*{{\mathbb{E}}}[X_{r}]=$ $\displaystyle~{}0$
$\displaystyle\operatorname*{{\mathbb{E}}}[X_{r}^{2}]=$
$\displaystyle~{}6B^{8}\sigma^{4}m^{-2}$ $\displaystyle M=$
$\displaystyle~{}6d\sigma^{2}B^{4}m^{-1}$

where the first equation follows from the definition of $Z_{r}$, the second
equation follows from Eq. (12), the third equation follows from Eq. (11).

Our goal is to choose $m$ sufficiently large such that Eq. (13) satisfies

$\displaystyle\Pr[X>{\epsilon_{1}}]\leq\delta_{2}/2$

We will achieve this in two steps.

  * •

Firstly, we will find $t$ such that the probability is no larger than
$\delta_{2}/\operatorname{poly}(n)$.

  * •

Secondly, we will choose $m$ such that $t\leq{\epsilon_{1}}$.

We need to choose $t$ such that Eq. (13) satisfies

$\displaystyle\Pr[X>t]\leq\delta_{2}/2$

Firstly, we need

$\displaystyle\frac{t^{2}}{m\operatorname*{{\mathbb{E}}}[X_{r}^{2}]}=$
$\displaystyle~{}\frac{mt^{2}}{6B^{8}\sigma^{4}}$ $\displaystyle\geq$
$\displaystyle~{}\log(1/\delta_{2})$

This requires

$\displaystyle t\geq(6B^{8}\sigma^{4}m^{-1}\log(1/\delta_{2}))^{1/2}$

Secondly, we need

$\displaystyle\frac{t^{2}}{Mt/3}=$ $\displaystyle~{}\frac{3t}{M}$
$\displaystyle=$ $\displaystyle~{}\frac{mt}{6d\sigma^{2}B^{4}}$
$\displaystyle\geq$ $\displaystyle~{}\log(1/\delta_{2})$

This requires

$\displaystyle t\geq 6d\sigma^{2}B^{4}m^{-1}\log(1/\delta_{2})$

We define

$\displaystyle A_{1}=$
$\displaystyle~{}(6B^{8}\sigma^{4}m^{-1}\log(1/\delta_{2}))^{1/2}$
$\displaystyle A_{2}=$
$\displaystyle~{}6d\sigma^{2}B^{4}m^{-1}\log(1/\delta_{2})$

We should choose

$\displaystyle t\geq A_{1}+A_{2}$

Then, we need to choose $m$ sufficiently large, such that
$t\leq{\epsilon_{1}}$. Namely, we need

$\displaystyle A_{1}\leq$ $\displaystyle~{}{\epsilon_{1}}/2$ $\displaystyle
A_{2}\leq$ $\displaystyle~{}{\epsilon_{1}}/2$

Firstly, we consider $A_{1}$. We have

$\displaystyle A_{1}=$
$\displaystyle~{}(6B^{8}\sigma^{4}m^{-1}\log(1/\delta_{2}))^{1/2}$
$\displaystyle\leq$ $\displaystyle~{}{\epsilon_{1}}/2$

This requires

$\displaystyle m\geq
C_{1}B^{8}\sigma^{4}{\epsilon_{1}}^{-2}\log(1/\delta_{2})$

Secondly, we consider $A_{2}$. We have

$\displaystyle A_{2}=$
$\displaystyle~{}6d\sigma^{2}B^{4}m^{-1}\log(1/\delta_{2})$
$\displaystyle\leq$ $\displaystyle~{}{\epsilon_{1}}/2$

This requires

$\displaystyle m\geq
C_{2}d\sigma^{2}B^{4}{\epsilon_{1}}^{-1}\log(1/\delta_{2})$

Finally, we choose

$\displaystyle m\geq$
$\displaystyle~{}C_{1}B^{8}\sigma^{4}{\epsilon_{1}}^{-2}\log(1/\delta_{2})+C_{2}d\sigma^{2}B^{4}{\epsilon_{1}}^{-1}\log(1/\delta_{2})$
(14)

Therefore, By Eq. (14), we choose
$m=\Omega({\epsilon_{1}}^{-2}dB^{8}\sigma^{4}\log(1/\delta_{2}))$, then we
have

$\displaystyle\Pr[|X|\leq{\epsilon_{1}}]\geq 1-\delta_{2}/2$ (15)

We also need to consider the possibility that for each $r\in[m]$, $|X_{r}|\leq
M$ holds.

We choose $\delta_{1}=\delta_{2}/\operatorname{poly}(m)$ in Eq. (11). Then We
take union bound over $m$ entries, we have for all $r\in[m]$

$\displaystyle\Pr[|X_{r}|\leq 6d\sigma^{2}B^{4}m^{-1}]\geq$
$\displaystyle~{}1-m\delta_{1}$ $\displaystyle=$
$\displaystyle~{}1-m\delta_{2}/\operatorname{poly}(m)$ $\displaystyle\geq$
$\displaystyle~{}1-\delta_{2}/2$ (16)

We take union bound over Eq. (15) and Eq. (D.2). We have

$\displaystyle\Pr[|H_{i,j}^{\mathrm{dis}}-H_{i,j}^{\mathrm{cts}}|\leq{\epsilon_{1}}]\geq$
$\displaystyle~{}1-(\delta_{2}/2+\delta_{2}/2)$ $\displaystyle=$
$\displaystyle~{}1-\delta_{2}$

∎

As we have already proven the gap between single entry between Continuous and
Discrete Quadratic NTK Matrices in Lemma D.10, we further take union bound
over all $n^{2}$ entries, to get the gap between Continuous and Discrete
Quadratic NTK Matrices.

######  Lemma D.11 (Union Bound $\|H^{\mathrm{dis}}-H^{\mathrm{cts}}\|_{F}$ ).

If we have the below conditions,

  * •

Let $H^{\mathrm{dis}}\in\mathbb{R}^{n\times n}$ be define in Definition 3.1.
Namely, $H_{i,j}^{\mathrm{dis}}=\frac{1}{m}\sum_{r=1}^{m}\langle\langle
w_{r},x_{i}\rangle x_{i},\langle w_{r},x_{j}\rangle x_{j}\rangle$, for any
$i,j\in[n]$.

  * •

Let $H^{\mathrm{cst}}\in\mathbb{R}^{n\times n}$ be define in Definition 3.2.
Namely, $H_{i,j}^{\mathrm{cts}}=\operatorname*{{\mathbb{E}}}_{w\sim{\cal
N}(0,\sigma^{2}I_{d\times d})}\langle\langle w,x_{i}\rangle x_{i},\langle
w,x_{j}\rangle x_{j}\rangle$, for any $i,j\in[n]$.

  * •

Let $\delta_{1},\delta_{2},\delta_{3}\in(0,1)$. Let
$\delta_{1}=\delta_{2}/\operatorname{poly}(m)$. Let
$\delta_{2}=\delta_{3}/\operatorname{poly}(n)$.

  * •

Let $d=\Omega(\log(1/\delta_{1}))$

  * •

Let $m=\Omega({\epsilon_{1}}^{-2}dB^{8}\sigma^{4}\log(1/\delta_{2}))$

Then, with probability $1-\delta_{3}$, we have

$\displaystyle\|H^{\mathrm{dis}}-H^{\mathrm{cts}}\|_{F}\leq n{\epsilon_{1}}$

###### Proof.

By Lemma D.10, if we choose
$m=\Omega({\epsilon_{1}}^{-2}dB^{8}\sigma^{4}\log(1/\delta_{2}))$. Then, with
probability $1-\delta_{2}$ we have

$\displaystyle|H_{i,j}^{\mathrm{dis}}-H_{i,j}^{\mathrm{cts}}|\leq{\epsilon_{1}}$

We choose $\delta_{2}=\delta_{3}/\operatorname{poly}(n)$. Then, we take union
bound over $n^{2}$ entries. We have

$\displaystyle\Pr[\|H^{\mathrm{dis}}-H^{\mathrm{cts}}\|_{F}\leq
n\cdot{\epsilon_{1}}]\geq$ $\displaystyle~{}1-n^{2}\delta_{2}$
$\displaystyle=$ $\displaystyle~{}1-n^{2}\delta_{3}/\operatorname{poly}(n)$
$\displaystyle\geq$ $\displaystyle~{}1-\delta_{3}$

∎

With the help of Bernstein Inequality and the sensitivity of Continuous
Quadratic NTK Matrix, we are ready to present the sensitivity of Discrete
Quadratic NTK Matrix.

######  Lemma D.12 (Sensitivity of Discrete Quadratic NTK under $\beta$-close
neighboring dataset (with $n{\epsilon_{1}}$) ).

If we have the below conditions,

  * •

Let $B>0$ be a constant.

  * •

Let $n$ be the number of data points.

  * •

We have dataset ${\cal D}=\\{(x_{i},y_{i})\\}_{i=1}^{n}$, where
$x_{i}\in\mathbb{R}^{d}$ and $\|x_{i}\|_{2}\leq B$ for any $i\in[n]$.

  * •

Let the neighbor dataset ${\cal D^{\prime}}$ be defined Definition 4.1.

  * •

Let the discrete quadratic kernel matrices
$H^{\mathrm{dis}}\in\mathbb{R}^{n\times n}$ and
${H^{\mathrm{dis}}}^{\prime}\in\mathbb{R}^{n\times n}$ be defined as
Definition 3.1, where ${H^{\mathrm{dis}}}^{\prime}\in\mathbb{R}^{n\times n}$
is the kernel corresponding to ${\cal D^{\prime}}$. Without loss of
generality, we have ${\cal D}$ and ${\cal D^{\prime}}$ only differ in the
$n$-th item.

  * •

Let $\delta_{1},\delta_{2},\delta_{3}\in(0,1)$. Let
$\delta_{1}=\delta_{2}/\operatorname{poly}(m)$. Let
$\delta_{2}=\delta_{3}/\operatorname{poly}(n)$.

  * •

Let $d=\Omega(\log(1/\delta_{1}))$

  * •

Let $m=\Omega({\epsilon_{1}}^{-2}dB^{8}\sigma^{4}\log(1/\delta_{2}))$

Then, with probability $1-\delta_{3}$, we can show that

$\displaystyle\|H^{\mathrm{dis}}-{H^{\mathrm{dis}}}^{\prime}\|_{F}\leq
O(n{\epsilon_{1}}+\sqrt{n}\sigma^{2}B^{3}\beta)$

###### Proof.

Recall in Lemma D.11, Let $\delta_{2},\delta_{3}\in(0,1)$. Let
$\delta_{2}=\delta_{3}/\operatorname{poly}(n)$. Then, if we choose
$m=\Omega({\epsilon_{1}}^{-2}dB^{8}\sigma^{4}\log(1/\delta_{2}))$, then, with
probability $1-\delta_{3}$, we have

$\displaystyle\|H^{\mathrm{dis}}-H^{\mathrm{cts}}\|_{F}\leq n{\epsilon_{1}}$
(17)

By Lemma D.4, we have

$\displaystyle\|H^{\mathrm{cts}}-{H^{\mathrm{cts}}}^{\prime}\|_{F}\leq
C\sqrt{n}\sigma^{2}B^{3}\beta$ (18)

Then, we have the following

$\displaystyle\|H^{\mathrm{dis}}-{H^{\mathrm{dis}}}^{\prime}\|_{F}=$
$\displaystyle~{}\|(H^{\mathrm{dis}}-H^{\mathrm{cts}})+(H^{\mathrm{cts}}-{H^{\mathrm{cts}}}^{\prime})+({H^{\mathrm{cts}}}^{\prime}-{H^{\mathrm{dis}}}^{\prime})\|_{F}$
$\displaystyle\leq$
$\displaystyle~{}\|H^{\mathrm{dis}}-H^{\mathrm{cts}}\|_{F}+\|H^{\mathrm{cts}}-{H^{\mathrm{cts}}}^{\prime}\|_{F}+\|{H^{\mathrm{cts}}}^{\prime}-{H^{\mathrm{dis}}}^{\prime}\|_{F}$
$\displaystyle\leq$
$\displaystyle~{}2n{\epsilon_{1}}+\|H^{\mathrm{cts}}-{H^{\mathrm{cts}}}^{\prime}\|_{F}$
$\displaystyle\leq$
$\displaystyle~{}C(n{\epsilon_{1}}+\sqrt{n}\sigma^{2}B^{3}\beta)$

where the 1st step is because of basic algebra, the 2nd step is due to
$\|a+b\|_{F}\leq\|a\|_{F}+\|b\|_{F}$ holds for any $a,b\in\mathbb{R}^{d\times
d}$, the 3rd step is from Eq. (17), the 4th step comes from Eq. (18).

∎

We choose an appropriate ${\epsilon_{1}}$ to have the final sensitivity of the
Discrete Quadratic NTK Matrix.

######  Lemma D.13 (Sensitivity of Discrete Quadratic NTK under $\beta$-close
neighboring dataset ).

If we have the below conditions,

  * •

Let $B>0$ be a constant.

  * •

Let $n$ be the number of data points.

  * •

We have dataset ${\cal D}=\\{(x_{i},y_{i})\\}_{i=1}^{n}$, where
$x_{i}\in\mathbb{R}^{d}$ and $\|x_{i}\|_{2}\leq B$ for any $i\in[n]$.

  * •

Let the neighbor dataset ${\cal D^{\prime}}$ be defined Definition 4.1.

  * •

Let the discrete quadratic kernel matrices
$H^{\mathrm{dis}}\in\mathbb{R}^{n\times n}$ and
${H^{\mathrm{dis}}}^{\prime}\in\mathbb{R}^{n\times n}$ be defined as
Definition 3.1, where ${H^{\mathrm{dis}}}^{\prime}\in\mathbb{R}^{n\times n}$
is the kernel corresponding to ${\cal D^{\prime}}$. Without loss of
generality, we have ${\cal D}$ and ${\cal D^{\prime}}$ only differ in the
$n$-th item.

  * •

Let $\delta_{1},\delta_{2},\delta_{3}\in(0,1)$. Let
$\delta_{1}=\delta_{2}/\operatorname{poly}(m)$. Let
$\delta_{2}=\delta_{3}/\operatorname{poly}(n)$.

  * •

Let $d=\Omega(\log(1/\delta_{1}))$.

  * •

Let $m=\Omega(n\cdot dB^{2}\beta^{-2}\log(1/\delta_{2}))$.

  * •

Let ${\epsilon_{1}}=O(n^{-1/2}\sigma^{2}B^{3}\beta)$.

Then, with probability $1-\delta_{3}$, we can show that

$\displaystyle\|H^{\mathrm{dis}}-{H^{\mathrm{dis}}}^{\prime}\|_{F}\leq
O(\sqrt{n}\sigma^{2}B^{3}\beta)$

###### Proof.

By Lemma D.12, with probability $1-\delta_{3}$, we have

$\displaystyle\|H^{\mathrm{dis}}-{H^{\mathrm{dis}}}^{\prime}\|_{F}\leq
O(n{\epsilon_{1}}+\sqrt{n}\sigma^{2}B^{3}\beta)$

Since we choose ${\epsilon_{1}}=O(n^{-1/2}\sigma^{2}B^{3}\beta)$, we have

$\displaystyle O(n{\epsilon_{1}})=O(\sqrt{n}\sigma^{2}B^{3}\beta)$

Also, since we choose ${\epsilon_{1}}=O(n^{-1/2}\sigma^{2}B^{3}\beta)$, we
have

$\displaystyle m=\Omega(n\cdot dB^{2}\beta^{-2}\log(1/\delta_{2}))$

Then, we are done.

∎

###  D.3 Sensitivity for Privacy Guarantees

Recall that, we have defined $M$ in Definition 4.2. And we have defined
neighboring dataset $\mathcal{D}$ and $\mathcal{D}^{\prime}$ in Definition
4.1.

Then, we have

$\displaystyle M:=\|\mathcal{M}({\cal D})^{1/2}\mathcal{M}({\cal
D}^{\prime})^{-1}\mathcal{M}({\cal D})^{1/2}-I_{n\times n}\|_{F}$

In this section, we demonstrate that ${\cal M}(D)=H^{\mathrm{dis}}$ satisfies
the assumption specified in Condition 5 of Theorem C.1 for ${\cal M}(D)$.
Namely, we want to prove that $M\leq\Delta$, for some $\Delta$.

In order to calculate $M$, we need the PSD inequality tools, which is proved
in the following Lemma.

######  Lemma D.14 (PSD Inequality).

If we have the below conditions,

  * •

Let ${\cal D}\in\mathbb{R}^{n\times d}$ and ${\cal
D}^{\prime}\in\mathbb{R}^{n\times d}$ are neighboring dataset (see Definition
4.1)

  * •

Let $H^{\mathrm{dis}}$ denotes the discrete NTK kernel matrix generated by
${\cal D}$, and ${H^{\mathrm{dis}}}^{\prime}$ denotes the discrete NTK kernel
matrix generated by neighboring dataset ${\cal D}^{\prime}$.

  * •

Let $H^{\mathrm{dis}}\succeq\eta_{\min}I_{n\times n}$, for some fixed
$\eta_{\min}\in\mathbb{R}$.

  * •

Let $\beta=O(\eta_{\min}/\operatorname{poly}(n,\sigma,B))$, where $\beta$ is
defined in Definition 4.1.

  * •

Let $\psi:=O(\sqrt{n}\sigma^{2}B^{3}\beta)$.

  * •

Let $\delta_{1},\delta_{2},\delta_{3}\in(0,1)$. Let
$\delta_{1}=\delta_{2}/\operatorname{poly}(m)$. Let
$\delta_{2}=\delta_{3}/\operatorname{poly}(n)$.

  * •

Let $d=\Omega(\log(1/\delta_{1}))$.

  * •

Let $m=\Omega(n\cdot dB^{2}\beta^{-2}\log(1/\delta_{2}))$.

Then, with probability $1-\delta_{3}$, we have

$\displaystyle(1-\psi/\eta_{\min})H^{\mathrm{dis}}\preceq{H^{\mathrm{dis}}}^{\prime}\preceq(1+\psi/\eta_{\min})H^{\mathrm{dis}}$

###### Proof.

We need to calculate the spectral norm. Namely, we need
$\|{H^{\mathrm{dis}}}^{\prime}-H^{\mathrm{dis}}\|$.

By Fact A.5, we have

$\displaystyle\|{H^{\mathrm{dis}}}^{\prime}-H^{\mathrm{dis}}\|\leq\|{H^{\mathrm{dis}}}^{\prime}-H^{\mathrm{dis}}\|_{F}$

By Lemma D.13, we have

$\displaystyle\|H^{\mathrm{dis}}-{H^{\mathrm{dis}}}^{\prime}\|_{F}\leq
O(\sqrt{n}\sigma^{2}B^{3}\beta)$

Combining the two analysis mentioned above, we have

$\displaystyle\|H^{\mathrm{dis}}-{H^{\mathrm{dis}}}^{\prime}\|\leq
O(\sqrt{n}\sigma^{2}B^{3}\beta)$ (19)

Since we have $\psi=O(\sqrt{n}\sigma^{2}B^{3}\beta)$ and
$\beta=O(\eta_{\min}/\operatorname{poly}(n,\sigma,B))$.

Therefore, we have

$\displaystyle\psi/\eta_{\min}<1$

Then, we have

$\displaystyle{H^{\mathrm{dis}}}^{\prime}\succeq$
$\displaystyle~{}H^{\mathrm{dis}}-\psi I_{n\times n}$ $\displaystyle\succeq$
$\displaystyle~{}(1-\psi/\eta_{\min})H^{\mathrm{dis}}$

where the 1st step is because of Eq. (19), the 2nd step is due to
$H^{\mathrm{dis}}\succeq\eta_{\min}I_{n\times n}$.

∎

Then, we are ready to calculate the exact value of $M$ based on the Lemma
proved above.

######  Lemma D.15 (Sensitivity of PSD Matrix of $H^{\mathrm{dis}}$, formal
version of Lemma 5.1).

If we have the below conditions,

  * •

If ${\cal D}\in\mathbb{R}^{n\times d}$ and ${\cal
D}^{\prime}\in\mathbb{R}^{n\times d}$ are neighboring dataset (see Definition
4.1)

  * •

Let $H^{\mathrm{dis}}$ denotes the discrete NTK kernel matrix generated by
${\cal D}$, and ${H^{\mathrm{dis}}}^{\prime}$ denotes the discrete NTK kernel
matrix generated by neighboring dataset ${\cal D}^{\prime}$.

  * •

Let $H^{\mathrm{dis}}\succeq\eta_{\min}I_{n\times n}$, for some
$\eta_{\min}\in\mathbb{R}$.

  * •

Let $\beta=O(\eta_{\min}/\operatorname{poly}(n,\sigma,B))$, where $\beta$ is
defined in Definition 4.1.

  * •

Let $\psi:=O(\sqrt{n}\sigma^{2}B^{3}\beta)$.

  * •

Let $\delta_{1},\delta_{2},\delta_{3}\in(0,1)$. Let
$\delta_{1}=\delta_{2}/\operatorname{poly}(m)$. Let
$\delta_{2}=\delta_{3}/\operatorname{poly}(n)$.

  * •

Let $d=\Omega(\log(1/\delta_{1}))$.

  * •

Let $m=\Omega(n\cdot dB^{2}\beta^{-2}\log(1/\delta_{2}))$.

Then, with probability $1-\delta_{3}$, we have

  * •

Part 1.

$\displaystyle\|(H^{\mathrm{dis}})^{-1/2}{H^{\mathrm{dis}}}^{\prime}(H^{\mathrm{dis}})^{-1/2}-I\|\leq\psi/\eta_{\min}$

  * •

Part 2.

$\displaystyle\|(H^{\mathrm{dis}})^{-1/2}{H^{\mathrm{dis}}}^{\prime}(H^{\mathrm{dis}})^{-1/2}-I\|_{F}\leq\sqrt{n}\psi/\eta_{\min}$

###### Proof.

Proof of Part 1. By Lemma D.14, we have

$\displaystyle(1-\psi/\eta_{\min})H^{\mathrm{dis}}\preceq{H^{\mathrm{dis}}}^{\prime}\preceq(1+\psi/\eta_{\min})H^{\mathrm{dis}}$

which implies

$\displaystyle(1-\psi/\eta_{\min})I_{n\times
n}\preceq(H^{\mathrm{dis}})^{1/2}{H^{\mathrm{dis}}}^{\prime}(H^{\mathrm{dis}})^{1/2}\preceq(1+\psi/\eta_{\min})I_{n\times
n}$

which implies

$\displaystyle-\psi/\eta_{\min}I_{n\times
n}\preceq(H^{\mathrm{dis}})^{1/2}{H^{\mathrm{dis}}}^{\prime}(H^{\mathrm{dis}})^{1/2}-I_{n\times
n}\preceq\psi/\eta_{\min}I_{n\times n}$

which implies

$\displaystyle\|(H^{\mathrm{dis}})^{-1/2}{H^{\mathrm{dis}}}^{\prime}(H^{\mathrm{dis}})^{-1/2}-I\|\leq\psi/\eta_{\min}$
(20)

Proof of Part 2. By Fact A.5, for any $A\in\mathbb{R}^{n\times n}$, we have

$\displaystyle\|A\|_{F}\leq\sqrt{n}\|A\|$ (21)

Combining Eq. (20) and Eq. (21), we have

$\displaystyle\|(H^{\mathrm{dis}})^{-1/2}{H^{\mathrm{dis}}}^{\prime}(H^{\mathrm{dis}})^{-1/2}-I\|_{F}\leq\sqrt{n}\psi/\eta_{\min}$

We can choose $\beta$ sufficiently small, such that $\psi/\eta_{\min}<1$.

∎

##  Appendix E Utility Guarantees

In this section, we establish the utility guarantees for our algorithm. Our
proof involves employing the spectral norm of
$H^{\mathrm{dis}}-\widetilde{H}^{\mathrm{dis}}$ as a pivotal element.
Initially, we calculate the spectral norm of $(K+\lambda I)^{-1}$.
Subsequently, we determine the $\mathcal{L}_{2}$ norms for $\mathsf{K}(x,X)$
and $Y$, ultimately leading to the assessment of our algorithm’s utility.

We begin by calculating the spectral norm of
$H^{\mathrm{dis}}-\widetilde{H}^{\mathrm{dis}}$.

######  Lemma E.1 ( Spectral norm of
$H^{\mathrm{dis}}-\widetilde{H}^{\mathrm{dis}}$).

If we have the below conditions,

  * •

If ${\cal D}\in\mathbb{R}^{n\times d}$ and ${\cal
D}^{\prime}\in\mathbb{R}^{n\times d}$ are neighboring dataset (see Definition
4.1)

  * •

Let $H^{\mathrm{dis}}$ denotes the discrete NTK kernel matrix generated by
${\cal D}$ (see Definition 3.1).

  * •

Let $\eta_{\max}I_{n\times n}\succeq
H^{\mathrm{dis}}\succeq\eta_{\min}I_{n\times n}$, for some
$\eta_{\max},\eta_{\min}\in\mathbb{R}$.

  * •

Let $\widetilde{H}^{\mathrm{dis}}$ denote the private $H^{\mathrm{dis}}$
generated by Algorithm 1 with $H^{\mathrm{dis}}$ as input.

  * •

Let $\rho=O(\sqrt{(n^{2}+\log(1/\gamma))/k}+(n^{2}+\log(1/\gamma))/{k})$.

  * •

Let $\gamma\in(0,1)$.

Then, with probability $1-\gamma$, we have

$\displaystyle\|H^{\mathrm{dis}}-\widetilde{H}^{\mathrm{dis}}\|\leq\rho\cdot\eta_{\max}$

###### Proof.

By Part 3 of Theorem C.1, with probability $1-\gamma$, we have

$\displaystyle(1-\rho)H^{\mathrm{dis}}\preceq\widetilde{H}^{\mathrm{dis}}\preceq(1+\rho)H^{\mathrm{dis}}$

which implies

$\displaystyle-\rho
H^{\mathrm{dis}}\preceq\widetilde{H}^{\mathrm{dis}}-H^{\mathrm{dis}}\preceq\rho
H^{\mathrm{dis}}$ (22)

Then, we have

$\displaystyle\|\widetilde{H}^{\mathrm{dis}}-H^{\mathrm{dis}}\|\leq\rho\cdot\eta_{\max}$

∎

To calculate the spectral norm of the inverse of the difference between two
matrices, we need to involve a classical technique from the literature, where
[116] presented a perturbation bound of Moore-Penrose inverse the spectral
norm,

######  Lemma E.2 ([116], Theorem 1.1 in [89]).

Given two matrices $A,B\in\mathbb{R}^{d_{1}\times d_{2}}$ with full column
rank, we have

$\displaystyle\|A^{\dagger}-B^{\dagger}\|\lesssim\max(\|A^{\dagger}\|^{2},\|B^{\dagger}\|^{2})\cdot\|A-B\|.$

With the help of the perturbation bound, we can now reach the spectral norm of
$(K+\lambda I)^{-1}$.

######  Lemma E.3 (Error control for inverse operation).

If we have the below conditions,

  * •

If ${\cal D}\in\mathbb{R}^{n\times d}$ and ${\cal
D}^{\prime}\in\mathbb{R}^{n\times d}$ are neighboring dataset (see Definition
4.1)

  * •

Let $H^{\mathrm{dis}}$ denotes the discrete NTK kernel matrix generated by
${\cal D}$ (see Definition 3.1).

  * •

Let $\widetilde{H}^{\mathrm{dis}}$ denotes the private $H^{\mathrm{dis}}$
generated by Algorithm 1 with $H^{\mathrm{dis}}$ as the input.

  * •

Let $\eta_{\max}I_{n\times n}\succeq
H^{\mathrm{dis}}\succeq\eta_{\min}I_{n\times n}$, for some
$\eta_{\max},\eta_{\min}\in\mathbb{R}$.

  * •

Let $K=H^{\mathrm{dis}},\widetilde{K}=\widetilde{H}^{\mathrm{dis}}$.

  * •

Let $\lambda\in\mathbb{R}$.

  * •

Let $\rho=O(\sqrt{(n^{2}+\log(1/\gamma))/k}+(n^{2}+\log(1/\gamma))/{k})$.

  * •

Let $\gamma\in(0,1)$.

Then, with probability $1-\gamma$, we have

$\displaystyle\|(K+\lambda I)^{-1}-(\widetilde{K}+\lambda I)^{-1}\|\leq
O(\frac{\rho\cdot\eta_{\max}}{(\eta_{\min}+\lambda)^{2}})$

###### Proof.

We consider the $\|(K+\lambda I)^{-1}\|$ term. We have

$\displaystyle\|(K+\lambda I)^{-1}\|=$
$\displaystyle~{}\sigma_{\max}((K+\lambda I)^{-1})$ $\displaystyle=$
$\displaystyle~{}\frac{1}{\sigma_{\min}((K+\lambda I))}$ $\displaystyle\leq$
$\displaystyle~{}\frac{1}{\eta_{\min}+\lambda}$ (23)

where the 1st step is because of definition of spectral norm, the 2nd step is
due to $\sigma_{\max}(A^{-1})=1/\sigma_{\min}(A)$ holds for any matrix $A$,
the 3rd step is from $K\succeq\eta_{\min}I_{n\times n}$.

Similarly, we can have

$\displaystyle\|(\widetilde{K}+\lambda
I)^{-1}\|\leq\frac{1}{\eta_{\min}+\lambda}$ (24)

Recall in Lemma E.1, we have

$\displaystyle\|H^{\mathrm{dis}}-\widetilde{H}^{\mathrm{dis}}\|\leq\rho\cdot\eta_{\max}$
(25)

Then, by Lemma E.2, we have

$\displaystyle\|(K+\lambda I)^{-1}-(\widetilde{K}+\lambda I)^{-1}\|\leq$
$\displaystyle~{}O(\max(\|(K+\lambda I)^{-1}\|^{2},\|(\widetilde{K}+\lambda
I)^{-1}\|^{2})\cdot\|K-\widetilde{K}\|)$ $\displaystyle\leq$
$\displaystyle~{}O(\frac{1}{(\eta_{\min}+\lambda)^{2}}\cdot\|K-\widetilde{K}\|)$
$\displaystyle\leq$
$\displaystyle~{}O(\frac{\rho\cdot\eta_{\max}}{(\eta_{\min}+\lambda)^{2}})$

where the 1st step is because of Lemma E.2, the 2nd step is due to Eq. (E) and
Eq. (24), the 3rd step is from Eq. (25). ∎

Then, we can finally reach the utility guarantees for Private NTK Regression,
which is discussed in the following Lemma.

######  Lemma E.4 (Error control of NTK Regression, formal version of Lemma
4.8).

If we have the below conditions,

  * •

If ${\cal D}\in\mathbb{R}^{n\times d}$ and ${\cal
D}^{\prime}\in\mathbb{R}^{n\times d}$ are neighboring dataset (see Definition
4.1)

  * •

Let $H^{\mathrm{dis}}$ denotes the discrete NTK kernel matrix generated by
${\cal D}$ (see Definition 3.1).

  * •

Let $\eta_{\max}I_{n\times n}\succeq
H^{\mathrm{dis}}\succeq\eta_{\min}I_{n\times n}$, for some
$\eta_{\max},\eta_{\min}\in\mathbb{R}$.

  * •

Let $\widetilde{H}^{\mathrm{dis}}$ denotes the private $H^{\mathrm{dis}}$
generated by Algorithm 1 with $H^{\mathrm{dis}}$ as the input.

  * •

Let $K=H^{\mathrm{dis}},\widetilde{K}=\widetilde{H}^{\mathrm{dis}}$ in
Definition 3.4. Then we have $f_{K}^{*}(x)$ and $f_{\widetilde{K}}^{*}(x)$.

  * •

Let $\sqrt{n}\psi/\eta_{\min}<\Delta$, where $\Delta$ is defined in Definition
4.3.

  * •

Let $\rho=O(\sqrt{(n^{2}+\log(1/\gamma))/k}+(n^{2}+\log(1/\gamma))/{k})$.

  * •

Let $\omega:=6d\sigma^{2}B^{4}$.

  * •

Let $\gamma\in(0,1)$.

Then, with probability $1-\gamma$, we have

$\displaystyle|f_{K}^{*}(x)-f_{\widetilde{K}}^{*}(x)|\leq
O(\frac{\rho\cdot\eta_{\max}\cdot\omega}{(\eta_{\min}+\lambda)^{2}})$

###### Proof.

We consider the $\|\mathsf{K}(x,X)\|_{2}$ term.

Let $\mathsf{K}(x,X)(s)\in\mathbb{R}$ denote the $s$ -th entry of
$\mathsf{K}(x,X)\in\mathbb{R}^{n}$. Let $\Xi_{r}:=\langle\langle
w_{r},x\rangle x,\langle w_{r},x_{i}\rangle x_{i}\rangle$.

Then, for any $s\in[n]$, we have

$\displaystyle|\mathsf{K}(x,X)(s)|=$
$\displaystyle~{}|\frac{1}{m}\sum_{s=1}^{m}\Xi_{r}|$ $\displaystyle\leq$
$\displaystyle~{}6d\sigma^{2}B^{4}$ $\displaystyle=$ $\displaystyle~{}\omega$
(26)

where the 1st step is because of the definition of $\mathsf{K}(x,X)$, the 2nd
step is due to Lemma D.7, the 3rd step is from definition of $\omega$.

Then we have

$\displaystyle\|\mathsf{K}(x,X)\|_{2}\leq$
$\displaystyle~{}\sqrt{n}|\mathsf{K}(x,X)(s)|$ $\displaystyle\leq$
$\displaystyle~{}\sqrt{n}\omega$ (27)

where the 1st step is because of the definition of $\|\cdot\|_{2}$, the 2nd
step is due to Eq. (E).

Then, we consider the $\|Y\|_{2}$.

Since we have $Y\in\\{0,1\\}^{n}$, then we have

$\displaystyle\|Y\|_{2}\leq\sqrt{n}$ (28)

Let $\rho=O(\sqrt{(n^{2}+\log(1/\gamma))/k}+(n^{2}+\log(1/\gamma))/{k})$.

By Lemma E.3, with probability $1-\gamma$, we have

$\displaystyle\|(K+\lambda I)^{-1}-(\widetilde{K}+\lambda I)^{-1}\|\leq
O(\frac{\rho\cdot\eta_{\max}}{(\eta_{\min}+\lambda)^{2}})$ (29)

Then, we consider the $|f_{K}^{*}(x)-f_{\widetilde{K}}^{*}(x)|$ term.

We have the following

$\displaystyle|f_{K}^{*}(x)-f_{\widetilde{K}}^{*}(x)|=$
$\displaystyle~{}\frac{1}{n}|\mathsf{K}(x,X)^{\top}(K+\lambda
I)^{-1}Y-\mathsf{K}(x,X)^{\top}(\widetilde{K}+\lambda I)^{-1}Y|$
$\displaystyle\leq$
$\displaystyle~{}\frac{1}{n}\|\mathsf{K}(x,X)\|_{2}\|(K+\lambda
I)^{-1}-(\widetilde{K}+\lambda I)^{-1}\|\|Y\|_{2}$ $\displaystyle\leq$
$\displaystyle~{}\frac{1}{n}\sqrt{n}\omega\cdot
O(\frac{\rho\cdot\eta_{\max}}{(\eta_{\min}+\lambda)^{2}})\cdot\sqrt{n}$
$\displaystyle=$
$\displaystyle~{}O(\frac{\rho\cdot\eta_{\max}\cdot\omega}{(\eta_{\min}+\lambda)^{2}})$
(30)

where the 1st step is because of Definition 3.4, the 2nd step is due to
$|b^{\top}Ac|\leq\|b\|_{2}\|A\|\|c\|_{2}$ holds for any
$b,c\in\mathbb{R}^{d},A\in\mathbb{R}^{d\times d}$, the 3rd step is from Eq.
(E), Eq. (28), and Eq. (29), the 4th step comes from basic algebra.

∎

## References

  * AAA+ [23] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al.  Gpt-4 technical report.  arXiv preprint arXiv:2303.08774, 2023.
  * ABS [20] Martin Aumüller, Anders Bourgeat, and Jana Schmurr.  Differentially private sketches for jaccard similarity estimation.  In Similarity Search and Applications: 13th International Conference, SISAP 2020, Copenhagen, Denmark, September 30–October 2, 2020, Proceedings 13, pages 18–32. Springer, 2020.
  * ACG+ [16] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308–318, 2016.
  * [4] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang.  Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks.  In International Conference on Machine Learning, pages 322–332. PMLR, 2019.
  * [5] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang.  On exact computation with an infinitely wide neural net.  Advances in neural information processing systems, 32, 2019.
  * AIMN [23] Alexandr Andoni, Piotr Indyk, Sepideh Mahabadi, and Shyam Narayanan.  Differentially private approximate near neighbor counting in high dimensions.  In Advances in Neural Information Processing Systems (NeurIPS), pages 43544–43562, 2023.
  * AKT+ [23] Daniel Alabi, Pravesh K Kothari, Pranay Tankala, Prayaag Venkat, and Fred Zhang.  Privately estimating a gaussian: Efficient, robust, and optimal.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 483–496, 2023.
  * ALS+ [23] Josh Alman, Jiehao Liang, Zhao Song, Ruizhe Zhang, and Danyang Zhuo.  Bypass exponential time preprocessing: Fast neural network training via weight-data correlation preprocessing.  In NeurIPS, 2023.
  * Arn [18] Josh Arnold.  Resnet-extract-image-feature-pytorch-python.  https://github.com/josharnoldjosh/Resnet-Extract-Image-Feature-Pytorch-Python, 2018.
  * AZLL [19] Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang.  Learning and generalization in overparameterized neural networks, going beyond two layers.  Advances in neural information processing systems, 32, 2019.
  * [11] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song.  A convergence theory for deep learning via over-parameterization.  In International Conference on Machine Learning, 2019.
  * [12] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song.  On the convergence rate of training recurrent neural networks.  In NeurIPS, 2019.
  * BEPP [22] Rouzbeh Behnia, Mohammadreza Reza Ebrahimi, Jason Pacheco, and Balaji Padmanabhan.  Ew-tune: A framework for privately fine-tuning large language models with differential privacy.  In 2022 IEEE International Conference on Data Mining Workshops (ICDMW), pages 560–566. IEEE, 2022.
  * Ber [24] Sergei Bernstein.  On a modification of chebyshev’s inequality and of the error formula of laplace.  Ann. Sci. Inst. Sav. Ukraine, Sect. Math, 1(4):38–49, 1924.
  * BHA+ [21] Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al.  On the opportunities and risks of foundation models.  arXiv preprint arXiv:2108.07258, 2021.
  * BLM+ [24] Arturs Backurs, Zinan Lin, Sepideh Mahabadi, Sandeep Silwal, and Jakub Tarnawski.  Efficiently computing similarities to private datasets.  arXiv preprint arXiv:2403.08917, 2024.
  * BPSW [21] Jan van den Brand, Binghui Peng, Zhao Song, and Omri Weinstein.  Training (overparametrized) neural networks in near-linear time.  In ITCS, 2021.
  * CAEM+ [22] Vincent Cohen-Addad, Alessandro Epasto, Vahab Mirrokni, Shyam Narayanan, and Peilin Zhong.  Near-optimal private and scalable $k$-clustering.  Advances in Neural Information Processing Systems, 35:10462–10475, 2022.
  * CAFL+ [22] Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, and Jakub M Tarnawski.  Near-optimal correlation clustering with privacy.  Advances in Neural Information Processing Systems, 35:33702–33715, 2022.
  * CB [20] Lenaic Chizat and Francis Bach.  Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss.  In Conference on learning theory, pages 1305–1338. PMLR, 2020.
  * CCBG [22] Yuan Cao, Zixiang Chen, Misha Belkin, and Quanquan Gu.  Benign overfitting in two-layer convolutional neural networks.  Advances in neural information processing systems, 35:25237–25250, 2022.
  * CCZG [19] Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu.  How much over-parameterization is sufficient to learn deep relu networks?  arXiv preprint arXiv:1911.12360, 2019.
  * CFW+ [20] Yuan Cao, Zhiying Fang, Yue Wu, Ding-Xuan Zhou, and Quanquan Gu.  Towards understanding the spectral bias of deep learning, 2020.
  * CG [19] Yuan Cao and Quanquan Gu.  Generalization bounds of stochastic gradient descent for wide and deep neural networks.  Advances in neural information processing systems, 32, 2019.
  * CNX [22] Justin Y Chen, Shyam Narayanan, and Yinzhan Xu.  All-pairs shortest path distances with differential privacy: Improved algorithms for bounded and unbounded weights.  arXiv preprint arXiv:2204.02335, 2022.
  * COB [19] Lenaic Chizat, Edouard Oyallon, and Francis Bach.  On lazy training in differentiable programming.  In Advances in Neural Information Processing Systems, 2019.
  * CSW+ [23] Yeshwanth Cherapanamjeri, Sandeep Silwal, David P Woodruff, Fred Zhang, Qiuyi Zhang, and Samson Zhou.  Robust algorithms on adaptive inputs from bounded adversaries.  arXiv preprint arXiv:2304.07413, 2023.
  * DCL+ [24] Wei Dong, Zijun Chen, Qiyao Luo, Elaine Shi, and Ke Yi.  Continual observation of joins under differential privacy.  Proceedings of the ACM on Management of Data, 2(3):1–27, 2024.
  * DLL+ [19] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai.  Gradient descent finds global minima of deep neural networks.  In International conference on machine learning, pages 1675–1685. PMLR, 2019.
  * DMNS [06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265–284. Springer, 2006.
  * DR [14] Cynthia Dwork and Aaron Roth.  The algorithmic foundations of differential privacy.  Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014.
  * DSWZ [23] Itai Dinur, Uri Stemmer, David P Woodruff, and Samson Zhou.  On differential privacy and adaptive data analysis with bounded space.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 35–65. Springer, 2023.
  * Dwo [08] Cynthia Dwork.  Differential privacy: A survey of results.  In International conference on theory and applications of models of computation, pages 1–19. Springer, 2008.
  * DZPS [19] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh.  Gradient descent provably optimizes over-parameterized neural networks.  In ICLR. arXiv preprint arXiv:1810.02054, 2019.
  * EKKL [20] Marek Eliáš, Michael Kapralov, Janardhan Kulkarni, and Yin Tat Lee.  Differentially private release of synthetic graphs.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 560–578. SIAM, 2020.
  * EMN [22] Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan.  Tight and robust private mean estimation with few users.  In International Conference on Machine Learning, pages 16383–16412. PMLR, 2022.
  * EMNZ [24] Alessandro Epasto, Vahab Mirrokni, Shyam Narayanan, and Peilin Zhong.  $k$-means clustering with distance-based privacy.  Advances in Neural Information Processing Systems, 36, 2024.
  * EW [24] Kennedy Edemacu and Xintao Wu.  Privacy preserving prompt engineering: A survey.  arXiv preprint arXiv:2404.06001, 2024.
  * FHS [22] Alireza Farhadi, MohammadTaghi Hajiaghayi, and Elaine Shi.  Differentially private densest subgraph.  In International Conference on Artificial Intelligence and Statistics, pages 11581–11597. PMLR, 2022.
  * FL [22] Chenglin Fan and Ping Li.  Distances release with differential privacy in tree and grid graph.  In 2022 IEEE International Symposium on Information Theory (ISIT), pages 2190–2195. IEEE, 2022.
  * FLL [24] Chenglin Fan, Ping Li, and Xiaoyun Li.  k-median clustering via metric embedding: towards better initialization with differential privacy.  Advances in Neural Information Processing Systems, 36, 2024.
  * GAW+ [22] Aditya Golatkar, Alessandro Achille, Yu-Xiang Wang, Aaron Roth, Michael Kearns, and Stefano Soatto.  Mixed differential privacy in computer vision.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8376–8386, 2022.
  * GDGK [20] Quan Geng, Wei Ding, Ruiqi Guo, and Sanjiv Kumar.  Tight analysis of privacy and utility tradeoff in approximate differential privacy.  In International Conference on Artificial Intelligence and Statistics, pages 89–99. PMLR, 2020.
  * GKK+ [23] Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, and Kewen Wu.  On differentially private counting on trees.  In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261, page 66. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2023.
  * GLL [22] Sivakanth Gopi, Yin Tat Lee, and Daogao Liu.  Private convex optimization via exponential mechanism.  In Conference on Learning Theory, pages 1948–1989. PMLR, 2022.
  * GLL+ [23] Sivakanth Gopi, Yin Tat Lee, Daogao Liu, Ruoqi Shen, and Kevin Tian.  Private convex optimization in general norms.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5068–5089. SIAM, 2023.
  * [47] Jiuxiang Gu, Chenyang Li, Yingyu Liang, Zhenmei Shi, and Zhao Song.  Exploring the frontiers of softmax: Provable optimization, applications in diffusion model, and beyond.  arXiv preprint arXiv:2405.03251, 2024.
  * [48] Jiuxiang Gu, Chenyang Li, Yingyu Liang, Zhenmei Shi, Zhao Song, and Tianyi Zhou.  Fourier circuits in neural networks: Unlocking the potential of large language models in mathematical reasoning and modular arithmetic.  arXiv preprint arXiv:2402.09469, 2024.
  * [49] Jiuxiang Gu, Yingyu Liang, Zhenmei Shi, Zhao Song, and Chiwun Yang.  Toward infinite-long prefix in transformer.  arXiv preprint arXiv:2406.14036, 2024.
  * [50] Jiuxiang Gu, Yingyu Liang, Zhenmei Shi, Zhao Song, and Yufa Zhou.  Unraveling the smoothness properties of diffusion models: A gaussian mixture perspective.  arXiv preprint arXiv:2405.16418, 2024.
  * GLW [21] Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz.  Numerical composition of differential privacy.  Advances in Neural Information Processing Systems, 34:11631–11642, 2021.
  * GMS [23] Yeqi Gao, Sridhar Mahadevan, and Zhao Song.  An over-parameterized exponential regression.  arXiv preprint arXiv:2303.16504, 2023.
  * GQSW [24] Yeqi Gao, Lianke Qin, Zhao Song, and Yitan Wang.  A sublinear adversarial training algorithm.  In ICLR, 2024.
  * GSJW [20] Mario Geiger, Stefano Spigler, Arthur Jacot, and Matthieu Wyart.  Disentangling feature and lazy training in deep neural networks.  Journal of Statistical Mechanics: Theory and Experiment, page 113301, 2020.
  * GSY [23] Yeqi Gao, Zhao Song, and Xin Yang.  Differentially private attention computation.  arXiv preprint arXiv:2305.04701, 2023.
  * HKMN [23] Samuel B Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan.  Robustness implies privacy in statistical estimation.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 497–506, 2023.
  * HRX [24] Yinbin Han, Meisam Razaviyayn, and Renyuan Xu.  Neural network-based score estimation in diffusion models: Optimization and generalization.  In The Twelfth International Conference on Learning Representations, 2024.
  * HSWZ [22] Hang Hu, Zhao Song, Omri Weinstein, and Danyang Zhuo.  Training overparametrized neural networks in sublinear time.  arXiv preprint arXiv:2208.04508, 2022.
  * HWAZ+ [21] Edward J Hu, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, Weizhu Chen, et al.  Lora: Low-rank adaptation of large language models.  In International Conference on Learning Representations, 2021.
  * HY [21] Ziyue Huang and Ke Yi.  Approximate range counting under differential privacy.  In 37th International Symposium on Computational Geometry (SoCG 2021). Schloss-Dagstuhl-Leibniz Zentrum für Informatik, 2021.
  * HZRS [16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * JGH [18] Arthur Jacot, Franck Gabriel, and Clément Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  Advances in neural information processing systems, 31, 2018.
  * JHL+ [24] Haibo Jin, Leyang Hu, Xinuo Li, Peiyan Zhang, Chonghan Chen, Jun Zhuang, and Haohan Wang.  Jailbreakzoo: Survey, landscapes, and horizons in jailbreaking large language and vision-language models.  arXiv preprint arXiv:2407.01599, 2024.
  * JLN+ [19] Christopher Jung, Katrina Ligett, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, and Moshe Shenfeld.  A new analysis of differential privacy’s generalization guarantees.  arXiv preprint arXiv:1909.03577, 2019.
  * JT [19] Ziwei Ji and Matus Telgarsky.  Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks.  In International Conference on Learning Representations, 2019.
  * KH+ [09] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * LCL+ [23] Haoran Li, Yulin Chen, Jinglong Luo, Yan Kang, Xiaojin Zhang, Qi Hu, Chunkit Chan, and Yangqiu Song.  Privacy in large language models: Attacks, defenses and future directions.  arXiv preprint arXiv:2310.10383, 2023.
  * LDS+ [21] Bo Liu, Ming Ding, Sina Shaham, Wenny Rahayu, Farhad Farokhi, and Zihuai Lin.  When machine learning meets privacy: A survey and outlook.  ACM Computing Surveys (CSUR), 54(2):1–36, 2021.
  * LGF+ [23] Haoran Li, Dadi Guo, Wei Fan, Mingshi Xu, Jie Huang, Fanpu Meng, and Yangqiu Song.  Multi-step jailbreaking privacy attacks on chatgpt.  In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 4138–4153, 2023.
  * LL [18] Yuanzhi Li and Yingyu Liang.  Learning overparameterized neural networks via stochastic gradient descent on structured data.  Advances in neural information processing systems, 31, 2018.
  * [71] Ping Li and Xiaoyun Li.  Differential privacy with random projections and sign random projections.  arXiv preprint arXiv:2306.01751, 2023.
  * [72] Xiaoyun Li and Ping Li.  Differentially private one permutation hashing and bin-wise consistent weighted sampling.  arXiv preprint arXiv:2306.07674, 2023.
  * LL [24] Ping Li and Xiaoyun Li.  Smooth flipping probability for differential private sign random projection methods.  Advances in Neural Information Processing Systems, 36, 2024.
  * LLB+ [24] Zhihao Liu, Jian Lou, Wenjie Bao, Zhan Qin, and Kui Ren.  Differentially private zeroth-order methods for scalable large language model finetuning.  arXiv preprint arXiv:2402.07818, 2024.
  * LLH+ [22] Xuechen Li, Daogao Liu, Tatsunori B Hashimoto, Huseyin A Inan, Janardhan Kulkarni, Yin-Tat Lee, and Abhradeep Guha Thakurta.  When does differentially private learning not suffer in high dimensions?  Advances in Neural Information Processing Systems, 35:28616–28630, 2022.
  * LLSY [17] Ninghui Li, Min Lyu, Dong Su, and Weining Yang.  Differential privacy: From theory to practice.  Springer, 2017.
  * LLWA [21] Kaifeng Lyu, Zhiyuan Li, Runzhe Wang, and Sanjeev Arora.  Gradient descent on two-layer nets: Margin maximization and simplicity bias.  Advances in Neural Information Processing Systems, 34:12978–12991, 2021.
  * LM [00] Beatrice Laurent and Pascal Massart.  Adaptive estimation of a quadratic functional by model selection.  Annals of Statistics, pages 1302–1338, 2000.
  * LPP+ [20] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al.  Retrieval-augmented generation for knowledge-intensive nlp tasks.  Advances in Neural Information Processing Systems, 33:9459–9474, 2020.
  * LSS+ [20] Jason D Lee, Ruoqi Shen, Zhao Song, Mengdi Wang, et al.  Generalized leverage score sampling for neural networks.  Advances in Neural Information Processing Systems, 33:10775–10787, 2020.
  * LSY [23] Xiaoxiao Li, Zhao Song, and Jiaming Yang.  Federated adversarial learning: A framework with convergence analysis.  In International Conference on Machine Learning, pages 19932–19959. PMLR, 2023.
  * LTLH [21] Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto.  Large language models can be strong differentially private learners.  In International Conference on Learning Representations, 2021.
  * LXS+ [19] Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington.  Wide neural networks of any depth evolve as linear models under gradient descent.  Advances in neural information processing systems, 2019.
  * MJW+ [22] Justus Mattern, Zhijing Jin, Benjamin Weggenmann, Bernhard Schölkopf, and Mrinmaya Sachan.  Differentially private language models for secure data sharing.  In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 4860–4873. Association for Computational Linguistics, 2022.
  * MMM [19] Song Mei, Theodor Misiakiewicz, and Andrea Montanari.  Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit.  In Conference on Learning Theory, pages 2388–2464. PMLR, 2019.
  * MOSW [22] Alexander Munteanu, Simon Omlor, Zhao Song, and David Woodruff.  Bounding the width of neural networks via coupled initialization a worst case analysis.  In International Conference on Machine Learning, pages 16083–16122. PMLR, 2022.
  * MRH+ [18] Alexander G de G Matthews, Mark Rowland, Jiri Hron, Richard E Turner, and Zoubin Ghahramani.  Gaussian process behaviour in wide deep neural networks.  In International Conference on Learning Representations, 2018.
  * MWY+ [23] Sadhika Malladi, Alexander Wettig, Dingli Yu, Danqi Chen, and Sanjeev Arora.  A kernel-based view of language model fine-tuning.  In International Conference on Machine Learning, pages 23610–23641. PMLR, 2023.