# Beyond the Universal Law of Robustness: Sharper Laws for Random Features and
Neural Tangent Kernels

Simone Bombari , Shayan Kiyani , Marco Mondelli11footnotemark: 1 Institute of
Science and Technology Austria (ISTA). Emails: {simone.bombari,
<EMAIL_ADDRESS>of Pennsylvania. Email:
<EMAIL_ADDRESS>
###### Abstract

Machine learning models are vulnerable to adversarial perturbations, and a
thought-provoking paper by Bubeck and Sellke has analyzed this phenomenon
through the lens of over-parameterization: interpolating smoothly the data
requires significantly more parameters than simply memorizing it. However,
this “universal” law provides only a necessary condition for robustness, and
it is unable to discriminate between models. In this paper, we address these
gaps by focusing on empirical risk minimization in two prototypical settings,
namely, random features and the neural tangent kernel (NTK). We prove that,
for random features, the model is not robust for any degree of over-
parameterization, even when the necessary condition coming from the universal
law of robustness is satisfied. In contrast, for even activations, the NTK
model meets the universal lower bound, and it is robust as soon as the
necessary condition on over-parameterization is fulfilled. This also addresses
a conjecture in prior work by Bubeck, Li and Nagaraj. Our analysis decouples
the effect of the kernel of the model from an “interaction matrix”, which
describes the interaction with the test data and captures the effect of the
activation. Our theoretical results are corroborated by numerical evidence on
both synthetic and standard datasets (MNIST, CIFAR-10).

##  1 Introduction

Despite the deployment of deep neural networks in a wide set of applications,
these models are known to be vulnerable to adversarial perturbations [7, 42],
which raises serious concerns about their robustness guarantees. To address
these issues, a wide variety of adversarial training methods has been
developed [19, 27, 30, 36, 50]. In a parallel effort, a recent line of
theoretical work has focused on providing a principled understanding to the
phenomenon of adversarial robustness, see e.g. [14, 53, 26, 16] and the review
in Section 2. Specifically, the recent paper by [10] has highlighted the role
of over-parameterization as a _necessary_ condition to achieve robustness:
while interpolation requires the number of parameters $p$ of the model to be
at least linear in the number of data samples $N$, _smooth_ interpolation
(namely, robustness) requires $p>dN$, where $d$ is the input dimension. We
note that the law of robustness put forward by [10] is “universal” in the
sense that it holds for _any_ parametric model. Furthermore, an earlier
conjecture by [9] posits that there exists a model of two-layer neural network
such that robustness is successfully achieved with this minimal number of
parameters; i.e., the condition $p>dN$ is both _necessary_ and _sufficient_
for robustness. This state of affairs leads to the following natural question:

When does over-parameterization become a sufficient condition to achieve
adversarial robustness?

In this paper, we consider a _sensitivity_ 111The sensitivity can be
interpreted as the non-robustness. measure proportional to
$\left\|\nabla_{z}f(z,\theta)\right\|_{2}$, where $z$ is the test data point
and $f$ is the model with parameters $\theta$ whose robustness is
investigated. This quantity is closely related to notions of sensitivity
appearing in related works [14, 15, 10], and it leads to a more stringent
requirement on the robustness than the perturbation stability considered by
[53], see also the discussion in Section 3. For such a sensitivity measure, we
show that the answer to the question above depends on the specific model at
hand. Specifically, we will focus on the solution yielded by empirical risk
minimization (ERM) in two prototypical settings widely analyzed in the
theoretical literature: _(i)_ Random Features (RF) [38], and the _(ii)_ Neural
Tangent Kernel (NTK) [24].

#### Main contribution.

Our key results are summarized below.

  * •

For random features, we show that ERM leads to a model which is _not robust_
for _any_ degree of over-parameterization. Specifically, we tackle a regime in
which the universal law of robustness by [10] trivializes, and we provide a
more refined bound.

  * •

For NTK with an even activation function, we give an upper bound on the ERM
solution that _matches_ the lower bound by [10]. As the NTK model approaches
the behavior of gradient descent for a suitable initialization [12], this also
shows that a class of two-layer neural networks has sensitivity of order
$\sqrt{Nd/p}$. This addresses Conjecture 2 of [9], albeit for a slightly
different notion of sensitivity (see the comparison in Section 3).

At the technical level, our analysis involves the study of the spectra of RF
and NTK random matrices, and it provides the following insights.

  * •

We introduce in (4.11) a new quantity, dubbed the _interaction matrix_.
Studying this matrix in isolation is a key step in all our results, as its
different norms are intimately related to the sensitivity of both the RF and
the NTK model. To the best of our knowledge, this is the first time that
attention is raised over such an object, which we deem relevant to the
theoretical characterization of adversarial robustness.

  * •

Our analytical characterization captures the role of the activation function:
it turns out that a specific symmetry (e.g., being even) boosts the
adversarial robustness of the models.

Finally, we experimentally show that the robustness behavior of both synthetic
and standard datasets (MNIST, CIFAR-10) agrees well with our theoretical
results.

##  2 Related work

From the vast literature studying adversarial examples, we succintly review
related works focusing on linear models, random features and NTK models.

#### Linear regression.

In light of the universal law of robustness, in the interpolation regime,
linear regression cannot achieve adversarial robustness (as $p=d$). For linear
models, [16, 26] have focused on adversarial training (as opposed to ERM,
which is considered in this work), showing that over-parameterization hurts
the robust generalization error. We also point out that, in some settings,
even the standard generalization error is maximized when the model is under-
parametrized [22]. Precise asymptotics on the robust error in the
classification setting are provided in [25, 43]. A different approach is
pursued by [46], who study a linear model that exhibits a trade-off between
generalization and robustness.

#### Random features (RF).

The RF model introduced by [38] can be regarded as a two-layer neural network
with random first layer weights, and it solves the lack of freedom in the
number of trainable parameters, which is constrained to be equal to the input
dimension for linear regression. The popularity of random features derives
from their analytical tractability, combined with the fact that the model
still reproduces behaviors typical of deep learning, such as the double-
descent curve [31]. Our analysis crucially relies on the spectral properties
of the kernel induced by this model. Such properties have been studied by
[28], and tight bounds on the smallest eigenvalue of the feature kernel have
been provided by [35] for ReLU activations. Theoretical results on the
adversarial robustness of random features have been shown for both adversarial
training [21] and the ERM solution [14, 15]. We will discuss the comparison
with [14, 15] in the next paragraph.

#### Neural tangent kernel (NTK).

The NTK can be regarded as the kernel obtained by linearizing the neural
network around the initialization [24]. A popular line of work has analyzed
its spectrum [18, 3, 49] and bounded its smallest eigenvalue [41, 35, 33, 8].
The behavior of the NTK is closely related to memorization [33], optimization
[4, 17] and generalization [5] properties of deep neural networks. The NTK has
also been recently exploited to identify non-robust features learned with
standard training [45] and gain insight on adversarial training [29]. More
closely related to our work, the robustness of the NTK model is studied in
[53, 15, 14]. Specifically, [53] analyze the interplay between width, depth
and initialization of the network, thus improving upon results by [23, 51].
However, the perturbation stability considered by [53] captures an average
robustness, rather than an adversarial one (see the detailed comparison in
Section 3), which makes these results not immediately comparable to ours. In
contrast, our notion of sensitivity is close to that analyzed in [15, 14],
which establish trade-offs between robustness and memorization for both the RF
and the NTK model. However, [15] study a teacher-student model with quadratic
teacher and infinite data, which also does not allow for a direct comparison.
Finally, [14] studies the ERM solution and focuses on _(i)_ infinite-width
networks, and _(ii)_ finite-width networks where the number of neurons scales
linearly with the input dimension. We remark that this last setup does not
lead to lower bounds on the sensitivity tighter than those by [10], and our
results on the NTK model provide the first upper bounds on the sensitivity
(which also match the lower bounds by [10]).

##  3 Preliminaries

#### Notation.

Given a vector $v$, we indicate with $\left\|v\right\|_{2}$ its Euclidean
norm. Given a matrix $A$, let $\left\|A\right\|_{\mathrm{op}}$ be its operator
norm, $\left\|A\right\|_{F}$ its Frobenius norm and $\lambda_{\rm
min}\left(A\right)$ and $\lambda_{\rm max}\left(A\right)$ its smallest and
largest eigenvalues respectively. We denote by
$\left\|\varphi\right\|_{\mathrm{Lip}}$ the Lipschitz constant of the function
$\varphi$. All the complexity notations $\Omega(\cdot)$, $\mathcal{O}(\cdot)$,
$o(\cdot)$ and $\Theta(\cdot)$ are understood for sufficiently large data size
$N$, input dimension $d$, number of neurons $k$, and number of parameters $p$.
We indicate with $C,c>0$ numerical constants, independent of $N,d,k,p$.

#### Generalized linear regression.

Let $(X,Y)$ be a labelled training dataset, where
$X=[x_{1},\ldots,x_{N}]^{\top}\in\mathbb{R}^{N\times d}$ contains the training
samples on its rows and $Y=(y_{1},\ldots,y_{N})\in\mathbb{R}^{N}$ contains the
corresponding labels. Let $\Phi:\mathbb{R}^{d}\to\mathbb{R}^{p}$ be a generic
_feature map_ , from the input space to a feature space of dimension $p$. We
consider the following _generalized linear model_

$f(x,\theta)=\Phi(x)^{\top}\theta,$ (3.1)

where $\Phi(x)\in\mathbb{R}^{p}$ is the feature vector associated with the
input sample $x$, and $\theta\in\mathbb{R}^{p}$ is the set of the trainable
parameters of the model. Our supervised learning setting involves solving the
optimization problem

$\mathop{\rm
min}\nolimits_{\theta}\left\|\Phi(X)^{\top}\theta-Y\right\|_{2}^{2},$ (3.2)

where $\Phi(X)\in\mathbb{R}^{N\times p}$ is the feature matrix, containing
$\Phi(x_{i})$ in its $i$-th row. From now on, we use the shorthands
$\Phi:=\Phi(X)$ and $K:=\Phi\Phi^{\top}\in\mathbb{R}^{N\times N}$, where $K$
denotes the kernel associated with the feature map. If we assume $K$ to be
invertible (i.e., the model is able to fit any set of labels $Y$), it is well
known that gradient descent converges to the interpolator which is the closest
in $\ell_{2}$ norm to the initialization, see e.g. [20]. In formulas,

$\theta^{*}=\theta_{0}+\Phi^{\top}K^{-1}(Y-f(X,\theta_{0})),$ (3.3)

where $\theta^{*}$ is the gradient descent solution, $\theta_{0}$ is the
initialization and $f(X,\theta_{0})=\Phi(X)^{\top}\theta_{0}$ is the output of
the model (3.1) at initialization.

#### Sensitivity.

We measure the robustness of a model $f(z,\theta)$ as a function of the test
sample $z$. In particular, we are interested in a quantity that expresses how
_sensitive_ is the output when small perturbations are applied to the input
$z$. More specifically, we could imagine an adversarial example “built around”
$z$ as

$z_{\textup{adv}}=z+\Delta_{\textup{adv}},\quad\mbox{with
}\left\|\Delta_{\textup{adv}}\right\|_{2}\leq\delta\left\|z\right\|_{2}.$
(3.4)

Here, $\Delta_{\textup{adv}}$ is a _small_ adversarial perturbation, in the
sense that its $\ell_{2}$ norm is only a fraction $\delta$ of the $\ell_{2}$
norm of $z$. Crucially, we expect $\delta$ not to depend on the scalings of
the problem. For example, if $z$ represents an image with $d$ pixels, this can
correspond to perturbing every pixel by a given amount. In this case, the
robustness depends on the amount of perturbation per pixel, and not on the
number of pixels $d$. This in turn implies that $\delta$ is a numerical
constant independent of $d$.

We are interested in the response of the model to $z_{\textup{adv}}$, and how
this relates to the natural scaling of the output, which we assume to be
$\Theta(1)$.222This is a natural choice, as e.g. the output label is not
expected to grow with the input dimension. However, any scaling is in
principle allowed and would not change our final results.  Up to first order,
we can write

$\displaystyle\left|f(z_{\textup{adv}},\theta)-f(z,\theta)\right|$
$\displaystyle\simeq\left|\nabla_{z}f(z,\theta)^{\top}\Delta_{\textup{adv}}\right|$
(3.5)
$\displaystyle\leq\left\|\Delta_{\textup{adv}}\right\|\left\|\nabla_{z}f(z,\theta)\right\|_{2}$
$\displaystyle\leq\delta\left\|z\right\|_{2}\left\|\nabla_{z}f(z,\theta)\right\|_{2}.$

The first inequality is saturated if the attacker builds an adversarial
perturbation that perfectly aligns with $\nabla_{z}f(z,\theta)$, and the
second inequality follows from (3.4). Hence, we define the _sensitivity_ of
the model evaluated in $z$ as

$\mathcal{S}_{f_{\theta}}(z):=\left\|z\right\|_{2}\left\|\nabla_{z}f(z,\theta)\right\|_{2}.$
(3.6)

Recall that both $\delta$ and the output of the model are constants,
independent of the scaling of the problem. Hence, a robust model needs to
respect $\mathcal{S}_{f_{\theta}}(z)=\mathcal{O}\left(1\right)$ for its test
samples $z$. In contrast, if $\mathcal{S}_{f_{\theta}}(z)\gg 1$ (e.g., the
sensitivity grows with the number of pixels of the image), we expect the model
to be adversarially vulnerable when evaluated in $z$. In a nutshell, the goal
of this paper is to provide bounds on $\mathcal{S}_{f_{\theta}}(z)$ for random
features and NTK models, thus establishing their robustness.

#### Related notions of sensitivity.

Measures of robustness similar to (3.6) have been used in the related
literature. In particular, [15] study $\mathbb{E}_{z\sim
P_{X}}[\mathcal{S}^{2}_{f_{\theta}}(z)]$ in the context of a teacher-student
setting with a quadratic target. [14] considers the model obtained from
solving the generalized regression problem (3.2) and characterizes a
sensitivity measure given by the Sobolev semi-norm. This quantity is again
similar to $\mathbb{E}_{z\sim P_{X}}[\mathcal{S}^{2}_{f_{\theta}}(z)]$, the
only difference being that the gradient is projected onto the sphere (namely,
onto the data manifold) before taking the norm. [53] study a notion of
perturbation stability given by
$\mathbb{E}_{z,\hat{z},\theta}\left|\nabla_{z}f(z,\theta)^{\top}(z-\hat{z})\right|$,
where $z$ is sampled from the data distribution and $\hat{z}$ is uniform in a
ball centered at $z$ with radius $\delta$. This would be similar to averaging
over $\Delta_{\textup{adv}}$ in (3.5), instead of choosing it adversarially.
Hence, [53] capture a weaker notion of _average robustness_ , as opposed to
this work which studies the _adversarial robustness_. Finally, [9, 10]
consider $\left\|f(z,\theta)\right\|_{\text{Lip}}$, where the Lipschitz
constant is with respect to $z$, which is equivalent to $\mathop{\rm
max}\nolimits_{z}\mathcal{S}_{f_{\theta}}(z)$. While this is a more stringent
condition than (3.6), we remark that the adversarial robustness corresponds to
choosing adversarially $\Delta_{\textup{adv}}$ (and not $z$), as done in
(3.5). We also note that our main results will hold with high probability over
the distribution of $z$.

#### Robustness of generalized linear regression.

For generalized linear models with feature map $\Phi$, plugging (3.1) in (3.6)
gives

$\mathcal{S}_{f_{\theta}}(z)=\left\|z\right\|_{2}\left\|\nabla_{z}\Phi(z)^{\top}\theta\right\|_{2}.$
(3.7)

This expression can also provide the sensitivity of the model trained with
gradient descent. Let us assume that $f(x,\theta_{0})=0$ for all
$x\in\mathbb{R}^{d}$ and, as before, that the kernel of the feature map is
invertible. Then, by plugging the value of $\theta^{*}$ from (3.3) in the
previous equation, we get

$\mathcal{S}_{f_{\theta^{*}}}(z)=\left\|z\right\|_{2}\left\|\nabla_{z}\Phi(z)^{\top}\Phi^{\top}K^{-1}Y\right\|_{2}.$
(3.8)

##  4 Main Result for Random Features

In this section, we provide our law of robustness for the _random features_
model. In particular, we will show that, for a wide class of activations, the
sensitivity of random features is $\gg 1$ and, therefore, the _model is not
robust_.

We assume the data labels $Y\in\mathbb{R}^{N}$ to be given by
$Y=g(X)+\epsilon$. Here, $g:\mathbb{R}^{d}\to\mathbb{R}$ is the ground-truth
function applied row-wise to $X\in\mathbb{R}^{N\times d}$ and
$\epsilon\in\mathbb{R}^{N}$ is a noise vector independent of $X$, having
independent sub-Gaussian entries with zero mean and variance
$\mathbb{E}[\epsilon_{i}^{2}]=\varepsilon^{2}$ for all $i$. The _random
features (RF) model_ takes the form

$f_{\textup{RF}}(x,\theta)=\Phi_{\textup{RF}}(x)^{\top}\theta,\qquad\Phi_{\textup{RF}}(x)=\phi(Vx),$
(4.1)

where $V$ is a $k\times d$ matrix, such that
$V_{i,j}\mathbin{\overset{}{\sim}}_{\rm i.i.d.}\mathcal{N}(0,1/d)$, and $\phi$
is an activation function applied component-wise. The number of parameters of
this model is $k$, as $V$ is fixed and $\theta\in\mathbb{R}^{k}$ contains the
trainable parameters. We initialize the model at $\theta_{0}=0$ so that
$f_{\textup{RF}}(x,\theta_{0})=0$ for all $x$. After training, we can write
the sensitivity using (3.8), which gives

$\displaystyle\mathcal{S}_{\textup{RF}}(z)$
$\displaystyle=\left\|z\right\|_{2}\left\|\nabla_{z}\Phi_{\textup{RF}}(z)^{\top}\Phi_{\textup{RF}}^{\top}K_{\textup{RF}}^{-1}Y\right\|_{2},$
(4.2)

where we use the shorthands
$\Phi_{\textup{RF}}:=\Phi_{\textup{RF}}(X)=\phi(XV^{\top})\in\mathbb{R}^{N\times
k}$ for the RF map and
$K_{\textup{RF}}:=\Phi_{\textup{RF}}\Phi_{\textup{RF}}^{\top}\in\mathbb{R}^{N\times
N}$ for the RF kernel. We will show that the kernel is in fact invertible in
the argument of our main result, Theorem 1. Throughout this section, we make
the following assumptions.

######  Assumption 1 (Data distribution).

The input data $(x_{1},\ldots,x_{N})$ are $N$ i.i.d. samples from the
distribution $P_{X}$, which satisfies the following properties:

  1. 1.

$\left\|x\right\|_{2}=\sqrt{d}$, i.e., the data are distributed on the sphere
of radius $\sqrt{d}$.

  2. 2.

$\mathbb{E}[x]=0$, i.e., the data are centered.

  3. 3.

$P_{X}$ satisfies the _Lipschitz concentration property_. Namely, there exists
an absolute constant $c>0$ such that, for every Lipschitz continuous function
$\varphi:\mathbb{R}^{d}\to\mathbb{R}$, we have
$\mathbb{E}|\varphi(X)|<+\infty$, and for all $t>0$,

$\mathbb{P}\left(\left|\varphi(x)-\mathbb{E}_{X}[\varphi(x)]\right|>t\right)\leq
2e^{-ct^{2}/\left\|\varphi\right\|_{\mathrm{Lip}}^{2}}.$ (4.3)

The first two assumptions can be achieved by simply pre-processing the raw
data. For the third assumption, we remark that the family of Lipschitz
concentrated distributions covers a number of important cases, e.g., standard
Gaussian [47], uniform on the sphere and on the unit (binary or continuous)
hypercube [47], or data obtained via a Generative Adversarial Network (GAN)
[40]. The third requirement is common in the related literature [35, 8] and it
is equivalent to the isoperimetry condition required by [10]. Finally, we note
that the three conditions of Assumption 1 are often replaced by a stronger
requirement (e.g., data uniform on the sphere), see [33, 14].

######  Assumption 2 (Activation function).

The activation function $\phi$ satisfies the following properties:

  1. 1.

$\phi$ is a non-linear $L$-Lipschitz function.

  2. 2.

Its first and second order derivatives $\phi^{\prime}$ and
$\phi^{\prime\prime}$ are respectively $L_{1}$ and $L_{2}$-Lipschitz
functions.

These requirements are satisfied by common activations, e.g. smoothed ReLU,
sigmoid, or $\tanh$.

######  Assumption 3 (Over-parameterization).

$\displaystyle N\log^{3}N=o(k),$ (4.4) $\displaystyle d=o(k/\log^{4}k).$ (4.5)

In words, the number of neurons $k$ scales faster than the input dimension $d$
and the number of data points $N$. Such an over-parameterized setting allows
to _(i)_ perfectly interpolate the data (this follows directly from the
invertibility of the kernel, which can be readily deduced from the proof of
Theorem 1), and _(ii)_ achieve minimum test error, see [31]. This is also in
line with the current trend of heavily over-parametrized deep-learning models
[34].

Figure 1: Sensitivity as a function of the number of parameters $k$, for an RF
model with synthetic data sampled from a Gaussian distribution with input
dimension $d=1000$. Different curves correspond to different values of the
sample size $N\in\\{400,800,1600\\}$. We plot the average over $20$
independent trials and the confidence interval at $1$ standard deviation. The
values of the sensitivity are significantly larger for $\phi(x)=\tanh(x)$
(left) than for $\phi(x)=x^{2}$ (right).

######  Assumption 4 (High-dimensional data).

$\displaystyle N\log^{3}N=o\left(d^{3/2}\right),$ (4.6)
$\displaystyle\log^{8}k=o(d).$ (4.7)

While the second condition is rather mild, the first one lower bounds the
input dimension $d$ in a way that appears to be crucial to prove our main
Theorem 1. Understanding whether (4.6) can be relaxed is left as an open
question.

At this point, we are ready to state our main result for random features.

######  Theorem 1.

Let Assumptions 1, 2, 3 and 4 hold, let $z\sim P_{X}$ be a test sample
independent from the training set $(X,Y)$, and let the derivative of the
activation function satisfy
$\mathbb{E}_{\rho\sim\mathcal{N}(0,1)}[\phi^{\prime}(\rho)]\neq 0$. Define
$\mathcal{S}_{\textup{RF}}(z)$ as in (4.2). Then,

$\mathcal{S}_{\textup{RF}}(z)=\Omega\left(\sqrt[6]{N}\right)\gg 1,$ (4.8)

with probability at least $1-\exp(-c\log^{2}N)$ over $X$, $z$, $V$ and
$\epsilon$.

In words, Theorem 1 shows that a vast class of over-parameterized RF models is
not robust against adversarial perturbations. A few remarks are now in order.

#### Beyond the universal law of robustness.

We recall that the results by [10] give a lower bound on the sensitivity of
order $\sqrt{Nd/k}$. A lower bound of the same order is obtained by [14],
whose results in the finite-width setting require $N,d,k$ to follow a
proportional scaling (i.e., $N=\Theta(d)=\Theta(k)$). This leaves as an open
question the characterization of the robustness for sufficiently over-
parameterized random features (i.e., when $k\gg Nd$). Our Theorem 1 resolves
this question by showing that the RF model is in fact not robust for _any_
degree of over-parameterization (as long as $k\gg N,d$ and Assumption 4 is
satisfied).

Figure 2: Sensitivity as a function of the number of parameters $k$, for an RF
model with inputs taken from two classes of the MNIST (left) and CIFAR-10
(right) datasets. We pre-process the data normalizing the pixel values from 0
to 1. Different curves correspond to different values of the sample size
$N\in\\{400,800,1600\\}$ and to different activations ($\phi(x)=\tanh(x)$ or
$\phi(x)=x^{2}$). We plot an average over $20$ independent trials and the
confidence interval at $1$ standard deviation. Again, $\phi(x)=x^{2}$ leads to
a model which is more robust (or, equivalently, less sensitive) than
$\phi(x)=\tanh(x)$.

#### Impact of the activation function and numerical results.

For the result of Theorem 1 to hold, we require the additional assumption
$\mathbb{E}_{\rho\sim\mathcal{N}(0,1)}[\phi^{\prime}(\rho)]\neq 0$. This may
not be just a technical requirement. In fact, if
$\mathbb{E}_{\rho\sim\mathcal{N}(0,1)}[\phi^{\prime}(\rho)]=0$, then a key
term appearing in the lower bound for the sensitivity (i.e., the Frobenius
norm of the _interaction matrix_ defined in (4.11)) has a drastically
different scaling, see Theorem 4 in the proof outline below. The importance of
the condition $\mathbb{E}_{\rho\sim\mathcal{N}(0,1)}[\phi^{\prime}(\rho)]\neq
0$ is also confirmed by our numerical simulations in the synthetic setting
considered in Figure 1. The left plot (corresponding to $\phi(x)=\tanh(x)$
s.t. $\mathbb{E}_{\rho\sim\mathcal{N}(0,1)}[\phi^{\prime}(\rho)]\neq 0$)
displays values of the sensitivity which are significantly larger than those
in the right plot (corresponding to $\phi(x)=x^{2}$ s.t.
$\mathbb{E}_{\rho\sim\mathcal{N}(0,1)}[\phi^{\prime}(\rho)]=0$). Furthermore,
the sensitivity for $\phi(x)=\tanh(x)$ appears to reach a plateau for large
values of $k$, while it keeps decreasing in $k$ when $\phi(x)=x^{2}$. A
similar impact of the activation function can be observed when considering
standard datasets (MNIST and CIFAR-10), see Figure 2.

###  4.1 Outline of the Argument of Theorem 1

The proof of Theorem 1 can be divided into three steps. It will be convenient
to define the shorthand

$A(z):=\nabla_{z}\Phi_{\textup{RF}}(z)^{\top}\Phi_{\textup{RF}}^{\top}K_{\textup{RF}}^{-1}\in\mathbb{R}^{d\times
N}.$ (4.9)

#### Step 1. Fitting the noise lower bounds the sensitivity.

First, we lower bound the sensitivity of our trained model with a quantity
which does not depend on the labels and grows proportionally with the noise.

######  Theorem 2.

Let Assumptions 1, 2, 3 and 4 hold. Define $A(z)$ as in (4.9). Then, we have

$\mathcal{S}_{\textup{RF}}(z)\geq\frac{\varepsilon}{2}\|z\|_{2}\left\|A(z)\right\|_{F},$
(4.10)

with probability at least
$1-\exp\left(-c\left\|A(z)\right\|_{F}^{2}/\left\lVert
A(z)\right\rVert_{\textup{op}}^{2}\right)$ over $\epsilon$, where $c$ is a
numerical constant.

The proof exploits the independence between $g(X)$ and $\epsilon$ and the
Hanson-Wright inequality. The details are contained in Appendix C.1.

Theorem 2 removes the labels from the expression, and reduces the problem of
estimating the robustness to characterizing the Frobenius norm of $A(z)$ (as
long as $\left\|A(z)\right\|_{F}\gg\left\lVert
A(z)\right\rVert_{\textup{op}}$, so that (4.10) holds with high probability).
This is in line with [10, 14], which provide upper bounds on the robustness of
models fitting the data below noise level.

#### Step 2. Splitting between interaction and kernel components.

Next, we split the matrix $A(z)$ into two separate objects. The first is the
interaction matrix given by

$\mathcal{I}_{\textup{RF}}(z):=\nabla_{z}\Phi_{\textup{RF}}(z)^{\top}\tilde{\Phi}_{\textup{RF}}^{\top},$
(4.11)

where we use the shorthand
$\tilde{\Phi}_{\textup{RF}}:=\Phi_{\textup{RF}}-\mathbb{E}_{X}[\Phi_{\textup{RF}}]\in\mathbb{R}^{N\times
k}$. The second is the _centered kernel_
$\tilde{K}_{\textup{RF}}:=\tilde{\Phi}_{\textup{RF}}\tilde{\Phi}_{\textup{RF}}^{\top}$,
whose spectrum can be studied separately.

######  Theorem 3.

Let Assumptions 1, 2, 3 and 4 hold. Define $A(z)$ as in (4.9). Then, we have

$\displaystyle\left\|A(z)\right\|_{F}\geq\lambda_{\mathop{\rm
max}\nolimits}^{-1}\left(\tilde{K}_{\textup{RF}}\right)\left\|\mathcal{I}_{\textup{RF}}(z)\right\|_{F}-C\sqrt{N+d}/d,$
(4.12) $\displaystyle\left\|A(z)\right\|_{F}\leq\lambda_{\mathop{\rm
min}\nolimits}^{-1}(\tilde{K}_{\textup{RF}})\left\|\mathcal{I}_{\textup{RF}}(z)\right\|_{F}+C\sqrt{N+d}/d,$

which implies

$\displaystyle\left\|A(z)\right\|_{F}\geq
C_{1}\frac{d}{kN}\left\|\mathcal{I}_{\textup{RF}}(z)\right\|_{F}-C\sqrt{N+d}/d,$
(4.13) $\displaystyle\left\|A(z)\right\|_{F}\leq
C_{2}k^{-1}\left\|\mathcal{I}_{\textup{RF}}(z)\right\|_{F}+C\sqrt{N+d}/d,$

with probability at least $1-\exp(-c\log^{2}N)$ over $X$ and $V$, where $c$,
$C$, $C_{1}$ and $C_{2}$ are absolute constants.

_Proof sketch._ To prove the claim, first we characterize the extremal
eigenvalues of the kernel
$K_{\textup{RF}}:=\Phi_{\textup{RF}}\Phi_{\textup{RF}}^{\top}$ and of its
centered counterpart
$\tilde{K}_{\textup{RF}}:=\tilde{\Phi}_{\textup{RF}}\tilde{\Phi}_{\textup{RF}}^{\top}$,
with
$\tilde{\Phi}_{\textup{RF}}=\Phi_{\textup{RF}}-\mathbb{E}_{X}\Phi_{\textup{RF}}$,
see Appendix C.2. Then, we perform a delicate centering step on the matrix
$A(z)$ defined in (4.9). Informally, we show that

$\|\nabla_{z}\Phi_{\textup{RF}}(z)^{\top}\Phi_{\textup{RF}}^{\top}K_{\textup{RF}}^{-1}\|_{F}\approx\|\nabla_{z}\Phi_{\textup{RF}}(z)^{\top}\tilde{\Phi}_{\textup{RF}}^{\top}\tilde{K}_{\textup{RF}}^{-1}\|_{F},$
(4.14)

see Lemma C.13 for a precise statement. This is the key technical ingredient,
since the rank-one components coming from the average feature matrix have a
large operator norm, which would trivialize the lower bound on the
sensitivity. More specifically, the centering leads to two rank-one terms
which are successively removed via the Sherman-Morrison formula and a number
of ad-hoc estimates, see Appendix C.3. Finally, the proof of (4.12)-(4.13)
follows by combining (4.14) with the bounds on the smallest/largest
eigenvalues of $\tilde{K}_{\textup{RF}}$, and it appears at the end of
Appendix C.3. ∎

Theorem 3 unveils the crucial role played by the interaction matrix
$\mathcal{I}_{\textup{RF}}(z)$ on the robustness of the model. This term is
the only one containing the test sample $z$, and it depends on how the term
$\nabla_{z}\Phi_{\textup{RF}}(z)$ aligns (or “interacts”) with the centered
feature map of the training data $\tilde{\Phi}_{\textup{RF}}$.

#### Step 3. Estimating $\left\|\mathcal{I}_{\textup{RF}}(z)\right\|_{F}$.

Finally, we provide a precise estimate on the norm of the interaction matrix
$\left\|\mathcal{I}_{\textup{RF}}(z)\right\|_{F}$. To do so, we assume that
the test point $z$ is independently sampled from the data distribution
$P_{X}$.

######  Theorem 4.

Let Assumptions 1, 2, 3 and 4 hold. Let $z\sim P_{X}$ be sampled independently
from the training set $(X,Y)$, and $\mathcal{I}_{\textup{RF}}(z)$ be defined
as in (4.11). Then,

$\left|\left\|\mathcal{I}_{\textup{RF}}(z)\right\|_{F}-\mathbb{E}_{\rho}^{2}[\phi^{\prime}(\rho)]\frac{k\sqrt{N}}{\sqrt{d}}\right|=o\left(\frac{k\sqrt{N}}{\sqrt{d}}\right),$
(4.15)

with probability at least $1-\exp(-c\log^{2}k)$ over $X$, $z$ and $V$, where
$c$ is an absolute constant.

_Proof sketch._ A direct calculation gives that

$\left\|\mathcal{I}_{\textup{RF}}(z)\right\|_{F}^{2}=\sum_{i=1}^{N}\left\|V^{\top}\text{diag}\left(\phi^{\prime}(Vz)\right)\tilde{\phi}(Vx_{i})\right\|_{2}^{2},$

and we bound separately each term of the sum. Note that the three terms
$V^{\top}$, $\text{diag}\left(\phi^{\prime}(Vz)\right)$ and
$\tilde{\phi}(Vx_{i})$ are correlated by the presence of $V$. However, $V$
contributes to the last two terms only via a single projection (along the
direction of $z$ and $x_{i}$, respectively). Hence, the key idea is to use a
Taylor expansion to split $\text{diag}\left(\phi^{\prime}(Vz)\right)$ and
$\tilde{\phi}(Vx_{i})$ into a component correlated with $V$ and an independent
one. The correlated components are computed exactly and the remaining
independent term is shown to have a negligible effect. The details are in
Appendix C.4. ∎

At this point, the proof of Theorem 1 follows by combining the results of
Theorems 2-4. The details are in Appendix C.5.

We note that the results of Theorems 2-4 do not require the assumption
$\mathbb{E}_{\rho\sim\mathcal{N}(0,1)}[\phi^{\prime}(\rho)]\neq 0$. In fact,
the role of this additional condition is clarified by the statement of Theorem
4: if $\mathbb{E}_{\rho\sim\mathcal{N}(0,1)}[\phi^{\prime}(\rho)]\neq 0$, then
$\left\|\mathcal{I}_{\textup{RF}}(z)\right\|_{F}$ is of order
$\Theta(k\sqrt{N/d})$; otherwise,
$\left\|\mathcal{I}_{\textup{RF}}(z)\right\|_{F}$ is drastically smaller. This
provides an explanation to the qualitatively different behavior of the
sensitivity for $\phi(x)=\tanh(x)$ and $\phi(x)=x^{2}$ displayed in Figures
1-2. To conclude, the interaction matrix appears to be the key quantity
capturing the impact of the activation function on the robustness of the ERM
solution.

##  5 Main Result for NTK Regression

In this section, we provide our law of robustness for the _NTK_ model. In
particular, we will show that, for a class of _even_ activations, the
sensitivity of NTK can be $\mathcal{O}\left(1\right)$ and, therefore, the
_model is robust_ for some scaling of the parameters.

We consider the following two-layer neural network

$f_{\textup{NN}}(x,w)=\sum_{i=1}^{k}\phi\left(W^{1}_{i:}x\right)-\sum_{i=1}^{k}\phi\left(W^{2}_{i:}x\right).$
(5.1)

Here, the hidden layer contains $2k$ neurons; $\phi$ is an activation function
applied component-wise; $W^{1},W^{2}\in\mathbb{R}^{k\times d}$ denote the
first and second half of the weights of the hidden layer, respectively; for
$j\in\\{1,2\\}$, $W^{j}_{i:}$ denotes the $i$-th row of $W^{j}$; the first $k$
weights of the second layer are set to $1$, and the last $k$ weights to $-1$.
We indicate with $w$ the vector containing the parameters of this model, i.e.,
$w=[\text{vec}(W^{1}),\text{vec}(W^{2})]\in\mathbb{R}^{p}$, with $p=2kd$. For
convenience, we initialize the network so that its output is $0$. This has
been shown to be necessary to have a robust model after lazy training [15,
48]. Specifically, we let
$w_{0}=[\text{vec}(W_{0}^{1}),\text{vec}(W_{0}^{2})]$ be the vector of the
parameters at initialization, where we take
$[W^{1}_{0}]_{i,j}\mathbin{\overset{}{\sim}}_{\rm i.i.d.}\mathcal{N}(0,1/d)$
and $W^{2}_{0}=W^{1}_{0}$. This readily implies that
$f_{\textup{NN}}(x,w_{0})=0$, for all $x$.

Now, the _NTK regression model_ takes the form

$f_{\textup{NTK}}(x,\theta)=\Phi_{\textup{NTK}}(x)^{\top}\theta,\,\,\Phi_{\textup{NTK}}(x)=\nabla_{w}f_{\textup{NN}}(x,w)|_{w=w_{0}}.$
(5.2)

Here, the vector trainable parameters is $\theta\in\mathbb{R}^{p}$, again with
$p=2kd$, which is initialized with $\theta_{0}=w_{0}$. This is the same model
considered by [15, 33]. We remark that $f_{\textup{NTK}}(x,\theta)$ is
equivalent to the linearization of $f_{\textup{NN}}(x,w)$ around the initial
point $w_{0}$, see e.g. [24, 6].

An application of the chain rule gives

$\Phi_{\textup{NTK}}(x)=\left[x\otimes\phi^{\prime}(W^{1}_{0}x),-x\otimes\phi^{\prime}(W^{2}_{0}x)\right]=:\left[\Phi_{\textup{NTK}}^{\prime}(x),-\Phi_{\textup{NTK}}^{\prime}(x)\right],$
(5.3)

where the last equality follows from the fact that $W^{1}_{0}=W^{2}_{0}$, and
the definition
$\Phi_{\textup{NTK}}^{\prime}(x):=x\otimes\phi^{\prime}(W^{1}_{0}x)$. Thus,
since
$\theta_{0}=w_{0}=[\text{vec}(W^{1}_{0}),\text{vec}(W^{2}_{0})]=[\text{vec}(W^{1}_{0}),\text{vec}(W^{1}_{0})]$,
we have

$f_{\textup{NTK}}(x,\theta_{0})=\Phi_{\textup{NTK}}(x)^{\top}\theta_{0}=\left[\Phi_{\textup{NTK}}^{\prime}(x),-\Phi_{\textup{NTK}}^{\prime}(x)\right]^{\top}[\text{vec}(W^{1}_{0}),\text{vec}(W^{1}_{0})]=0.$
(5.4)

This means that our model’s output is 0 at initialization. Then, we can use
(3.8) to express the sensitivity of the trained NTK regression model as

$\mathcal{S}_{\textup{NTK}}(z)=\left\|z\right\|_{2}\left\|\nabla_{z}\Phi_{\textup{NTK}}(z)^{\top}\Phi_{\textup{NTK}}^{\top}K_{\textup{NTK}}^{-1}Y\right\|_{2},$
(5.5)

where $\Phi_{\textup{NTK}}\in\mathbb{R}^{N\times p}$ contains in its $i$-th
row the feature map of the $i$-th training sample $\Phi_{\textup{NTK}}(x_{i})$
and $K_{\textup{NTK}}=\Phi_{\textup{NTK}}\Phi_{\textup{NTK}}^{\top}$. The
invertibility of the kernel will again follow from the proof of our main
result, Theorem 5. Throughout this section, we make the following assumptions.

######  Assumption 5 (Activation function).

The activation function $\phi$ satisfies the following properties:

  1. 1.

$\phi$ is a non-linear, even function.

  2. 2.

Its first order derivative $\phi^{\prime}$ is an $L$-Lipschitz function.

We restrict our analysis to an even activation function, as this requirement
significantly simplifies the derivations. The impact of the activation on the
robustness will also be discussed at the end of this section.

######  Assumption 6 (Minimum over-parameterization).

$N\log^{8}N=o(kd).$ (5.6)

Eq. (5.6) provides the weakest possible requirement on the number of
parameters of the model capable to guarantee interpolation for generic data
points, as it leads to a lower bound on the smallest eigenvalue of
$K_{\textup{NTK}}$ [8].

######  Assumption 7 (High-dimensional data).

$k=\mathcal{O}\left(d\right).$ (5.7)

This requirement is purely technical, and we leave as a future work the
interesting problem of characterizing the sensitivity of the NTK regression
model when $d=o(k)$.

We will still use Assumption 1 on the data distribution $P_{X}$, and the only
assumption on the labels is that $\left\|Y\right\|_{2}=\Theta(\sqrt{N})$,
which corresponds to the natural requirement that the output is $\Theta(1)$.
At this point, we are ready to state our main result for NTK regression.

######  Theorem 5.

Let Assumptions 1, 5, 6 and 7 hold. Then, we have

$\mathcal{S}_{\textup{NTK}}(z)=\mathcal{O}\left(\log
k\left(1+\sqrt{\frac{N}{k}}\right)\sqrt{\frac{N}{k}}\right),$ (5.8)

with probability at least $1-Ne^{-c\log^{2}k}-e^{-c\log^{2}N}$ over $X$ and
$w_{0}$. Furthermore, when $N=\mathcal{O}\left(k\right)$, (5.8) simplifies to

$\mathcal{S}_{\textup{NTK}}(z)=\mathcal{O}\left(\log
k\sqrt{\frac{Nd}{p}}\right),$ (5.9)

where $p=2dk$ denotes the number of parameters of the model.

_Proof sketch._ As for the RF model, we crucially separate the contribution of
the interaction matrix and of the kernel of the model. Specifically, we upper
bound the RHS of (5.5) with

$\left\|z\right\|_{2}\left\lVert\nabla_{z}\Phi_{\textup{NTK}}(z)^{\top}\Phi_{\textup{NTK}}^{\top}\right\rVert_{\textup{op}}\left\lVert
K_{\textup{NTK}}^{-1}\right\rVert_{\textup{op}}\left\|Y\right\|_{2}.$ (5.10)

Now, each term in (5.10) is treated separately. First, by assumption,
$\left\|Y\right\|_{2}=\Theta(\sqrt{N})$. Next, we have that $\left\lVert
K_{\textup{NTK}}^{-1}\right\rVert_{\textup{op}}=\lambda_{\mathop{\rm
min}\nolimits}^{-1}(K_{\textup{NTK}})=\mathcal{O}\left((dk)^{-1}\right)$,
which can be deduced from [8], see Lemma D.1. Finally, the bound on
$\left\lVert\nabla_{z}\Phi_{\textup{NTK}}(z)^{\top}\Phi_{\textup{NTK}}^{\top}\right\rVert_{\textup{op}}$
is computed explicitly through an application of the chain-rule (see Lemma
D.3), and it critically depends on the data being 0-mean and on the activation
being even. ∎

Figure 3: Sensitivity as a function of the number of parameters $p=dk$, for an
NTK model with synthetic data sampled from a Gaussian distribution with fixed
input dimension $d=1000$. Different curves correspond to different values of
the sample size $N\in\\{400,800,1600\\}$. We plot the average over $20$
independent trials and the confidence interval at $1$ standard deviation. The
values of the sensitivity are significantly larger for $\phi(x)=\tanh(x)$
(left) than for $\phi(x)=x^{2}$ (right).

In words, Theorem 5 shows that, for even activations and $k$ scaling super-
linearly in $N$, $\mathcal{S}_{\textup{NTK}}(z)=\mathcal{O}\left(1\right)$,
namely, the NTK model is robust against adversarial perturbations. A few
remarks are now in order.

#### Saturating the lower bound from the universal law of robustness.

We highlight that our upper bound on the sensitivity in (5.9) exhibits the
same scaling as the lower bound by [10], thus saturating the universal law of
robustness. A lower bound on the sensitivity of the same order is also
provided by [14], albeit restricted to the setting in which $k=\Theta(d)$ and
$k=\mathcal{O}\left(N\right)$. Note that Theorem 5 upper bounds the
sensitivity of the model obtained by running gradient descent (over $\theta$)
on $f_{\textup{NTK}}(x,\theta)$. It is well known, see e.g. [12], that a
similar solution is obtained by running gradient descent (over $w$) on
$f_{\textup{NN}}(x,w)$. This result holds after suitably rescaling the
initialization of $f_{\textup{NN}}(x,w)$, and the rescaling does not affect
our Theorem 5. As a result, Theorem 5 proves that a class of two-layer neural
networks has sensitivity of order $\sqrt{Nd/p}$ (up to logarithmic factors),
thus resolving in the affirmative Conjecture 2 of [9].

#### Impact of the activation function and numerical results.

Theorem 5 applies to even activation functions. At the technical level, the
symmetry in $\phi$ directly “centers” the kernel in the expression (5.5) of
the sensitivity, which largely simplifies our argument. We conjecture that
this symmetry may in fact be fundamental to guarantee the robustness of the
model. In fact, the right plot of Figure 3 shows that, for $\phi(x)=x^{2}$,
the sensitivity keeps decreasing, as the number of neurons $k$ (and,
therefore, the number of parameters $p$) grows. In contrast, for
$\phi(x)=\tanh(x)$, the sensitivity plateaus at a value which is an order of
magnitude larger than for $\phi(x)=x^{2}$ (see the left plot of Figure 3).
This difference is still visible even for real-world datasets (MNIST,
CIFAR-10), see Figure 4.

Figure 4: Sensitivity as a function of the number of parameters $p=dk$, for an
NTK model with data taken from two classes of the MNIST (left) and CIFAR-10
(right) datasets. We pre-process the data normalizing the pixel values from 0
to 1. Different curves correspond to different values of the sample size
$N\in\\{400,800,1600\\}$ and to different activations ($\phi(x)=\tanh(x)$ or
$\phi(x)=x^{2}$). We plot an average over $20$ independent trials and the
confidence interval at $1$ standard deviation. Again, $\phi(x)=x^{2}$ leads to
a model which is more robust (or, equivalently, less sensitive) than
$\phi(x)=\tanh(x)$.

##  6 Conclusions

Our paper provides a precise and quantitative characterization of how the
robustness of the solution obtained via empirical risk minimization depends on
the model at hand: for random features and non-even activations, over-
parameterization does not help, and we provide bounds tighter than the
universal law of robustness proposed by [10]; for NTK regression and even
activations, the model is robust as soon as $p>dN$, i.e., the universal law of
robustness is saturated. Numerical results on synthetic and standard datasets
confirm the impact of the model on the robustness of the solution. The present
contribution focuses on empirical risk minimization, which represents the
cornerstone of deep learning training algorithms. In contrast, a number of
recent papers has focused on adversarial training, considering the trade-off
between generalization and robust error, see e.g. [37, 52, 13, 11, 32, 21] and
references therein. We conclude by mentioning that the technical tools
developed in this work could be applied also to the models deriving from
adversarial training, and we leave such an analysis as future work.

## Acknowledgements

Simone Bombari and Marco Mondelli were partially supported by the 2019 Lopez-
Loreta prize, and the authors would like to thank Hamed Hassani for helpful
discussions.

## References

  * [1] Radoslaw Adamczak.  A note on the Hanson-Wright inequality for random vectors with dependencies.  Electronic Communications in Probability, 20:1–13, 2015.
  * [2] Radoslaw Adamczak, Alexander E Litvak, Alain Pajor, and Nicole Tomczak-Jaegermann.  Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling.  Constructive Approximation, 34(1):61–88, 2011.
  * [3] Ben Adlam and Jeffrey Pennington.  The neural tangent kernel in high dimensions: Triple descent and a multi-scale theory of generalization.  In International Conference on Machine Learning (ICML), 2020.
  * [4] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song.  A convergence theory for deep learning via over-parameterization.  In International Conference on Machine Learning (ICML), 2019.
  * [5] 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 (ICML), 2019.
  * [6] Peter L Bartlett, Andrea Montanari, and Alexander Rakhlin.  Deep learning: a statistical viewpoint.  Acta numerica, 30:87–201, 2021.
  * [7] Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Šrndić, Pavel Laskov, Giorgio Giacinto, and Fabio Roli.  Evasion attacks against machine learning at test time.  In Machine Learning and Knowledge Discovery in Databases, pages 387–402, 2013.
  * [8] Simone Bombari, Mohammad Hossein Amani, and Marco Mondelli.  Memorization and optimization in deep neural networks with minimum over-parameterization.  In Advances in Neural Information Processing Systems (NeurIPS), 2022\.
  * [9] Sébastien Bubeck, Yuanzhi Li, and Dheeraj M Nagaraj.  A law of robustness for two-layers neural networks.  In Conference on Learning Theory (COLT), pages 804–820, 2021.
  * [10] Sebastien Bubeck and Mark Sellke.  A universal law of robustness via isoperimetry.  In Advances in Neural Information Processing Systems (NeurIPS), 2021\.
  * [11] Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Percy S Liang.  Unlabeled data improves adversarial robustness.  In Advances in Neural Information Processing Systems (NeurIPS), 2019\.
  * [12] Lenaic Chizat, Edouard Oyallon, and Francis Bach.  On lazy training in differentiable programming.  In Advances in Neural Information Processing Systems (NeurIPS), 2019\.
  * [13] Edgar Dobriban, Hamed Hassani, David Hong, and Alexander Robey.  Provable tradeoffs in adversarially robust classification.  arXiv preprint arXiv:2006.05161, 2020.
  * [14] Elvis Dohmatob.  Fundamental tradeoffs between memorization and robustness in random features and neural tangent regimes.  arXiv preprint arXiv:2106.02630, 2022.
  * [15] Elvis Dohmatob and Alberto Bietti.  On the (non-) robustness of two-layer neural networks in different learning regimes.  arXiv preprint arXiv:2203.11864, 2022.
  * [16] Konstantin Donhauser, Alexandru Tifrea, Michael Aerni, Reinhard Heckel, and Fanny Yang.  Interpolation can hurt robust generalization even when there is no noise.  In Advances in Neural Information Processing Systems (NeurIPS), 2021\.
  * [17] Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai.  Gradient descent finds global minima of deep neural networks.  In International Conference on Machine Learning (ICML), 2019.
  * [18] Zhou Fan and Zhichao Wang.  Spectra of the conjugate kernel and neural tangent kernel for linear-width neural networks.  In Advances in Neural Information Processing Systems (NeurIPS), 2020\.
  * [19] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  In International Conference on Learning Representations (ICLR), 2015\.
  * [20] Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro.  Implicit regularization in matrix factorization.  In Advances in Neural Information Processing Systems (NeurIPS), 2017\.
  * [21] Hamed Hassani and Adel Javanmard.  The curse of overparametrization in adversarial training: Precise analysis of robust generalization for random features regression.  arXiv preprint arXiv:2201.05149, 2022.
  * [22] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani.  Surprises in high-dimensional ridgeless least squares interpolation.  The Annals of Statistics, 50(2):949–986, 2022.
  * [23] Hanxun Huang, Yisen Wang, Sarah Erfani, Quanquan Gu, James Bailey, and Xingjun Ma.  Exploring architectural ingredients of adversarially robust deep neural networks.  In Advances in Neural Information Processing Systems (NeurIPS), 2021\.
  * [24] Arthur Jacot, Franck Gabriel, and Clément Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  In Advances in Neural Information Processing Systems (NeurIPS), 2018\.
  * [25] Adel Javanmard and Mahdi Soltanolkotabi.  Precise statistical analysis of classification accuracies for adversarial training.  The Annals of Statistics, 50(4):2127–2156, 2022.
  * [26] Adel Javanmard, Mahdi Soltanolkotabi, and Hamed Hassani.  Precise tradeoffs in adversarial training for linear regression.  In Conference on Learning Theory (COLT), 2020.
  * [27] Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio.  Adversarial machine learning at scale.  In International Conference on Learning Representations (ICLR), 2017\.
  * [28] Zhenyu Liao and Romain Couillet.  On the spectrum of random features maps of high dimensional data.  In International Conference on Machine Learning (ICML), 2018.
  * [29] Noel Loo, Ramin Hasani, Alexander Amini, and Daniela Rus.  Evolution of neural tangent kernels under benign and adversarial training.  In Advances in Neural Information Processing Systems (NeurIPS), 2022\.
  * [30] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  In International Conference on Learning Representations (ICML), 2018\.
  * [31] Song Mei and Andrea Montanari.  The generalization error of random features regression: Precise asymptotics and the double descent curve.  Communications on Pure and Applied Mathematics, 75(4):667–766, 2022\.
  * [32] Yifei Min, Lin Chen, and Amin Karbasi.  The curious case of adversarially robust models: More data can help, double descend, or hurt generalization.  In Uncertainty in Artificial Intelligence (UAI), 2021.
  * [33] Andrea Montanari and Yiqiao Zhong.  The interpolation phase transition in neural networks: Memorization and generalization under lazy training.  The Annals of Statistics, 50(5):2816–2847, 2022.
  * [34] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever.  Deep double descent: Where bigger models and more data hurt.  In International Conference on Learning Representations (ICLR), 2020\.
  * [35] Quynh Nguyen, Marco Mondelli, and Guido Montufar.  Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep ReLU networks.  In International Conference on Machine Learning (ICML), 2021.
  * [36] Aditi Raghunathan, Jacob Steinhardt, and Percy Liang.  Certified defenses against adversarial examples.  In International Conference on Learning Representations (ICLR), 2018\.
  * [37] Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John C Duchi, and Percy Liang.  Adversarial training can hurt generalization.  arXiv preprint arXiv:1906.06032, 2019.
  * [38] Ali Rahimi and Benjamin Recht.  Random features for large-scale kernel machines.  In Advances in Neural Information Processing Systems (NIPS), 2007\.
  * [39] Holger Sambale.  Some notes on concentration for $\alpha$-subexponential random variables.  arXiv preprint arXiv:2002.10761, 2020.
  * [40] Mohamed El Amine Seddik, Cosme Louart, Mohamed Tamaazousti, and Romain Couillet.  Random matrix theory proves that deep learning representations of GAN-data behave as gaussian mixtures.  In International Conference on Machine Learning (ICML), 2020.
  * [41] Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee.  Theoretical insights into the optimization landscape of over-parameterized shallow neural networks.  IEEE Transactions on Information Theory, 65(2):742–769, 2018.
  * [42] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  In International Conference on Learning Representations (ICLR), 2014\.
  * [43] Hossein Taheri, Ramtin Pedarsani, and Christos Thrampoulidis.  Asymptotic behavior of adversarial training in binary classification.  arXiv preprint arXiv:2010.13275, 2020.
  * [44] Joel Tropp.  User-friendly tail bounds for sums of random matrices.  Foundations of Computational Mathematics, page 389–434, 2012.
  * [45] Nikolaos Tsilivis and Julia Kempe.  What can the neural tangent kernel tell us about adversarial robustness?  In Advances in Neural Information Processing Systems (NeurIPS), 2022\.
  * [46] Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry.  Robustness may be at odds with accuracy.  In International Conference on Learning Representations (ICLR), 2019\.
  * [47] Roman Vershynin.  High-dimensional probability: An introduction with applications in data science.  Cambridge university press, 2018.
  * [48] Yunjuan Wang, Enayat Ullah, Poorya Mianjy, and Raman Arora.  Adversarial robustness is at odds with lazy training.  In Advances in Neural Information Processing Systems (NeurIPS), 2022\.
  * [49] Zhichao Wang and Yizhe Zhu.  Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks.  arXiv preprint arXiv:2109.09304, 2021.
  * [50] Eric Wong and Zico Kolter.  Provable defenses against adversarial examples via the convex outer adversarial polytope.  In International Conference on Machine Learning (ICML), 2018.
  * [51] Boxi Wu, Jinghui Chen, Deng Cai, Xiaofei He, and Quanquan Gu.  Do wider neural networks really help adversarial robustness?  In Advances in Neural Information Processing Systems (NeurIPS), 2021\.
  * [52] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan.  Theoretically principled trade-off between robustness and accuracy.  In International Conference on Machine Learning (ICML), 2019.
  * [53] Zhenyu Zhu, Fanghui Liu, Grigorios Chrysos, and Volkan Cevher.  Robustness in deep learning: The good (width), the bad (depth), and the ugly (initialization).  In Advances in Neural Information Processing Systems (NeurIPS), 2022\.

##  Appendix A Additional Notations and Remarks

Given a sub-exponential random variable $X$, let
$\|X\|_{\psi_{1}}=\inf\\{t>0\,\,:\,\,\mathbb{E}[\exp(|X|/t)]\leq 2\\}$.
Similarly, for a sub-Gaussian random variable, let
$\|X\|_{\psi_{2}}=\inf\\{t>0\,\,:\,\,\mathbb{E}[\exp(X^{2}/t^{2})]\leq 2\\}$.
We use the analogous definitions for vectors. In particular, let
$X\in\mathbb{R}^{n}$ be a random vector, then
$\left\|X\right\|_{\psi_{2}}:=\sup_{\left\|u\right\|_{2}=1}\left\|u^{\top}X\right\|_{\psi_{2}}$
and
$\left\|X\right\|_{\psi_{1}}:=\sup_{\left\|u\right\|_{2}=1}\left\|u^{\top}X\right\|_{\psi_{1}}$.
Notice that if a vector has independent, mean 0, sub-Gaussian (sub-
exponential) entries, then its sub-Gaussian (sub-exponential). This is a
direct consequence of Hoeffding’s inequality and Bernstein’s inequality (see
Theorems 2.6.3 and 2.8.2 in [47]). It is useful to also define the generic
Orlicz norm of order $\alpha$ of a real random variable $X$ as

$\left\|X\right\|_{\psi_{\alpha}}:=\inf\\{t>0\,\,:\,\,\mathbb{E}[\exp(|X|^{\alpha}/t^{\alpha})]\leq
2\\}.$ (A.1)

From this definition, it follows that
$\left\||X|^{\gamma}\right\|_{\psi_{\alpha/\gamma}}=\left\|X\right\|_{\psi_{\alpha}}^{\gamma}$.
Finally, we recall the property that if $X$ and $Y$ are scalar random
variables, we have
$\left\|XY\right\|_{\psi_{1}}\leq\left\|X\right\|_{\psi_{2}}\left\|Y\right\|_{\psi_{2}}$.

We say that a random variable respects the Lipschitz concentration property if
there exists an absolute constant $c>0$ such that, for every Lipschitz
continuous function $\varphi:\mathbb{R}^{d}\to\mathbb{R}$, we have
$\mathbb{E}|\varphi(X)|<+\infty$, and for all $t>0$,

$\mathbb{P}\left(\left|\varphi(x)-\mathbb{E}_{X}[\varphi(x)]\right|>t\right)\leq
2e^{-ct^{2}/\left\|\varphi\right\|_{\mathrm{Lip}}^{2}}.$ (A.2)

When we state that a random variable or vector $X$ is sub-Gaussian (or sub-
exponential), we implicitly mean
$\left\|X\right\|_{\psi_{2}}=\mathcal{O}\left(1\right)$, i.e. it doesn’t
increase with the scalings of the problem. Notice that, if $X$ is Lipschitz
concentrated, then $X-\mathbb{E}[X]$ is sub-Gaussian. If $X\in\mathbb{R}$ is
sub-Gaussian and $\varphi:\mathbb{R}\to\mathbb{R}$ is Lipschitz, we have that
$\varphi(X)$ is sub-Gaussian as well. Also, if a random variable is sub-
Gaussian or sub-exponential, its $p$-th momentum is upper bounded by a
constant (that might depend on $p$).

In general, we indicate with $C$ and $c$ absolute, strictly positive,
numerical constants, that do not depend on the scalings of the problem, i.e.
input dimension, number of neurons, or number of training samples. Their value
may change from line to line.

Given a matrix $A$, we indicate with $A_{i:}$ its $i$-th row, and with
$A_{:j}$ its $j$-th column. Given two matrices $A,B\in\mathbb{R}^{m\times n}$,
we denote by $A\circ B$ their Hadamard product, and by $A\ast
B=[(A_{1:}\otimes B_{1:}),\ldots,(A_{m:}\otimes
B_{m:})]^{\top}\in\mathbb{R}^{m\times n^{2}}$ their row-wise Kronecker product
(also known as Khatri-Rao product). We denote $A^{*2}=A\ast A$. We say that a
matrix $A\in\mathbb{R}^{n\times n}$ is positive semi definite (p.s.d.) if it’s
symmetric and for every vector $v\in\mathbb{R}^{n}$ we have $v^{\top}Av\geq
0$.

##  Appendix B Useful Lemmas

######  Lemma B.1.

Let $Z$ be a matrix with rows $z_{i}\in\mathbb{R}^{n}$, for $i\in[N]$, such
that $N=o(n/\log^{4}n)$. Assume that $\\{z_{i}\\}_{i\in[N]}$ are independent
sub-exponential random vectors with $\psi=\mathop{\rm
max}\nolimits_{i}\left\|z_{i}\right\|_{\psi_{1}}$. Let
$\eta_{\textup{min}}=\mathop{\rm min}\nolimits_{i}\left\|z_{i}\right\|_{2}$
and $\eta_{\textup{max}}=\mathop{\rm
max}\nolimits_{i}\left\|z_{i}\right\|_{2}$. Set $\xi=\psi K+K^{\prime}$, and
$\Delta:=C\xi^{2}N^{1/4}n^{3/4}$. Then, we have that

$\lambda_{\rm
min}\left(ZZ^{\top}\right)\geq\eta_{\textup{min}}^{2}-\Delta,\qquad\lambda_{\rm
max}\left(ZZ^{\top}\right)\leq\eta_{\textup{max}}^{2}+\Delta$ (B.1)

holds with probability at least

$1-\exp\left(-cK\sqrt{N}\log\left(\frac{2n}{N}\right)\right)-\mathbb{P}\left(\eta_{\text{max}}\geq
K^{\prime}\sqrt{n}\right),$ (B.2)

where $c$ and $C$ are numerical constants.

###### Proof.

Following the notation in [2], we define

$B:=\sup_{u\in\mathbb{R}^{N}:\left\|u\right\|_{2}=1}\left|\left\|\sum_{i=1}^{N}u_{i}z_{i}\right\|_{2}^{2}-\sum_{i=1}^{N}u_{i}^{2}\left\|z_{i}\right\|_{2}^{2}\right|^{\frac{1}{2}}.$
(B.3)

Then, for any $u\in\mathbb{R}^{N}$ with unit norm, we have that

$\begin{split}\left\|Zu\right\|_{2}^{2}&=\left\|\sum_{i=1}^{N}u_{i}z_{i}\right\|_{2}^{2}-\sum_{i=1}^{N}u_{i}^{2}\left\|z_{i}\right\|_{2}^{2}+\sum_{i=1}^{N}u_{i}^{2}\left\|z_{i}\right\|_{2}^{2}\geq\mathop{\rm
min}\nolimits_{i}\left\|z_{i}\right\|_{2}^{2}-B^{2},\end{split}$ (B.4)

which implies that

$\lambda_{\rm
min}\left(ZZ^{\top}\right)=\inf_{u\in\mathbb{R}^{N}:\left\|u\right\|_{2}=1}\left\|Zu\right\|_{2}^{2}\geq\mathop{\rm
min}\nolimits_{i}\left\|z_{i}\right\|_{2}^{2}-B^{2}.$ (B.5)

In the same way, it can also be proven that

$\lambda_{\rm max}\left(ZZ^{\top}\right)\leq\mathop{\rm
max}\nolimits_{i}\left\|z_{i}\right\|_{2}^{2}+B^{2}.$ (B.6)

In our case, $z_{i}\in\mathbb{R}^{n}$. In the statement of Theorem 3.2 of [2],
let’s fix $r=1$, $m=N$, and $\theta=(N/n)^{1/4}<1/4$. Then, we have that the
condition required to apply Theorem 3.2 is satisfied, i.e. ,

$N\log^{2}\left(2\sqrt[4]{\frac{n}{N}}\right)\leq\sqrt{Nn}.$ (B.7)

By combining (B.5) and (B.6) with the upper bound on $B$ given by Theorem 3.2
of [2], the desired result readily follows. ∎

######  Lemma B.2.

Let $\\{x_{i}\\}_{i=1}^{N}$ be random variables in $\mathbb{R}$ such that they
all respect

$\mathbb{P}(|x_{i}|>t)<2e^{-ct^{\gamma}}.$ (B.8)

Then, we have

$\mathop{\rm max}\nolimits_{i}|x_{i}|\leq\log^{2/\gamma}{N},$ (B.9)

with probability at least $1-2\exp(-c\log^{2}N)$, where $c$ is a numerical
constant.

###### Proof.

For any $i\in[N]$,

$\mathbb{P}(|x_{i}|>\log^{2/\gamma}N)<2\exp(-c\log^{2}N),$ (B.10)

which gives

$\displaystyle\mathbb{P}(\mathop{\rm
max}\nolimits_{i}|x_{i}|>\log^{2/\gamma}N)<N\mathbb{P}(|x_{1}|>\log^{2/\gamma}N)<2\exp(\log
N-c\log^{2}N)<2\exp(-c_{1}\log^{2}N),$ (B.11)

where the second step is obtained through a union bound. This gives the
desired result. ∎

######  Lemma B.3.

Let $z\sim P_{Z}$ be a mean-0 and Lipschitz concentrated random vector (see
(A.2)). Consider

$\Gamma(z)=z\otimes z-\mathbb{E}_{z}\left[z\otimes z\right].$ (B.12)

Then,

$\left\|\Gamma(z)\right\|_{\psi_{1}}<C.$ (B.13)

where $C$ is a numerical constant.

###### Proof.

We have that

$\left\|\Gamma(z)\right\|_{\psi_{1}}=\sup_{\left\|u\right\|_{2}=1}\left\|u^{\top}\Gamma(z)\right\|_{\psi_{1}}=\sup_{\left\|U\right\|_{F}=1}\left\|z^{\top}Uz-\mathbb{E}_{x}\left[z^{\top}Uz\right]\right\|_{\psi_{1}}.$
(B.14)

Since $z$ is mean-0 and Lipschitz concentrated, we can apply the version of
the Hanson-Wright inequality given by Theorem 2.3 in [1]:

$\mathbb{P}\left(|z^{\top}Uz-\mathbb{E}_{x}\left[z^{\top}Uz\right]|>t\right)<2\exp\left(-\frac{1}{C_{1}}\mathop{\rm
min}\nolimits\left(\frac{t^{2}}{\left\|U\right\|^{2}_{F}},\frac{t}{\left\lVert
U\right\rVert_{\textup{op}}}\right)\right),$ (B.15)

where $C_{1}$ is a numerical constant. Thus, by Lemma 5.5 of [41], and using
$\left\|U\right\|_{F}\geq\left\lVert U\right\rVert_{\textup{op}}$, we conclude
that

$\left\|\Gamma(z)\right\|_{\psi_{1}}<C\left\|U\right\|_{F}=C,$ (B.16)

for some numerical constant $C$, which gives the desired result. ∎

######  Lemma B.4.

Let $z\in\mathbb{R}^{d}$ be a sub-Gaussian vector such that
$\left\|z\right\|_{\psi_{2}}=K$. Set
$\Sigma=\mathbb{E}\left[zz^{\top}\right]$. Then,

$\left\lVert\Sigma\right\rVert_{\textup{op}}\leq CK^{2},$ (B.17)

where $C$ is a numerical constant.

###### Proof.

Let $w$ be the unitary eigenvector associated to the maximum eigenvalue of
$\Sigma$. Then,

$\left\lVert\Sigma\right\rVert_{\textup{op}}=w^{\top}\Sigma
w=\mathbb{E}\left[w^{\top}zz^{\top}w\right]=\mathbb{E}\left[(w^{\top}z)^{2}\right].$
(B.18)

Furthermore, we have that

$\left\|z\right\|_{\psi_{2}}:=\sup_{w^{\prime}\text{s.t.}\left\|w^{\prime}\right\|_{2}=1}\left\|(w^{\prime})^{\top}z\right\|_{\psi_{2}}\geq\left\|w^{\top}z\right\|_{\psi_{2}}\geq\frac{1}{C}\sqrt{\mathbb{E}\left[(w^{\top}z)^{2}\right]},$
(B.19)

where $C$ is a numerical constant, and the last inequality comes from Eq.
(2.15) of [47]. By combining (B.18) and (B.19) we get our desired result. ∎

######  Lemma B.5.

Let $Z$ be an $N\times n$ matrix whose rows $z_{i}$ are i.i.d. mean-0 sub-
Gaussian random vectors in $\mathbb{R}^{n}$. Let
$K=\left\|z_{i}\right\|_{\psi_{2}}$ the sub-Gaussian norm of each row. Then,
we have

$\left\lVert
ZZ^{\top}\right\rVert_{\textup{op}}=K^{2}\mathcal{O}\left(N+n\right),$ (B.20)

with probability at least $1-2\exp(-cn)$, for some numerical constant $c$.

###### Proof.

The result is equivalent to Lemma B.7 of [8]. ∎

######  Lemma B.6.

Let $\\{Y_{i}\\}_{i=1}^{n}$ be independent real random variables such that
$\left\|Y_{i}\right\|_{\psi_{\alpha}}\leq K$ for every $i$ (see (A.1)), with
$\alpha\in(0,2]$. Then, for every $t>0$ we have,

$\mathbb{P}\left(\sum_{i=1}^{n}\left(Y_{i}-\mathbb{E}[Y_{i}]\right)>t\right)<2\exp\left(-c\left(\frac{t}{K\sqrt{n}\log^{1/\alpha}n}\right)^{\alpha}\right),$
(B.21)

where $c$ is an absolute constant.

###### Proof.

Let $Y$ be the vector containing the $Y_{i}$’s in its entries. Then, an
application of Cauchy–Schwarz inequality gives that the function

$f(Y):=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}Y_{i}$ (B.22)

is 1-Lipschitz.

By Lemma 5.6 of [39], we also have that

$\left\|\mathop{\rm max}\nolimits_{i}|Y_{i}|\right\|_{\psi_{\alpha}}\leq
CK\log^{1/\alpha}n,$ (B.23)

where $C$ is a numerical constant (that might depend on $\alpha$). Thus, as
$f$ is also convex, we can apply Proposition 3.1 of [39], obtaining

$\mathbb{P}\left(\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\left(Y_{i}-\mathbb{E}[Y_{i}]\right)>t\right)<2\exp\left(-c\frac{t^{\alpha}}{K^{\alpha}\log
n}\right).$ (B.24)

Rescaling $t$ gives the thesis. ∎

##  Appendix C Proofs for Random Features

In this section, we will indicate with $X\in\mathbb{R}^{N\times d}$ the data
matrix, such that its rows are sampled independently from $P_{X}$ (see
Assumption 1). We will indicate with $V\in\mathbb{R}^{k\times d}$ the random
features matrix, such that $V_{ij}\mathbin{\overset{}{\sim}}_{\rm
i.i.d.}\mathcal{N}(0,1/d)$. The feature vectors will be therefore indicated by
$\phi(XV^{\top})$, where $\phi$ is the activation function, applied component-
wise to the pre-activations $XV^{\top}$. We will also use the shorthands
$\Phi:=\phi(XV^{\top})\in\mathbb{R}^{N\times k}$ and
$K:=\Phi\Phi^{\top}\in\mathbb{R}^{N\times N}$. We also define
$\tilde{\Phi}:=\Phi-\mathbb{E}_{X}[\Phi]$ and
$\tilde{K}:=\tilde{\Phi}\tilde{\Phi}^{\top}$. Notice that, for compactness, we
dropped the subscripts “RF” from these quantities, as this section will only
treat the proofs related to Section 4. Again for the sake of compactness, we
will not re-introduce such quantities in the statements or the proofs of the
following lemmas.

###  C.1 Proof of Theorem 2

###### Proof of Theorem 2.

We have

$\left\|AY\right\|_{2}^{2}=\left\|A\left(g(X)+\epsilon\right)\right\|_{2}^{2}=\epsilon^{\top}A^{\top}A\epsilon+g(X)^{\top}A^{\top}Ag(X)+2g(X)^{\top}A^{\top}A\epsilon.$
(C.1)

As $\epsilon$ is sub-Gaussian, we have
$\left\|A\epsilon\right\|_{\psi_{2}}\leq C\left\lVert
A\right\rVert_{\textup{op}}$, where $C$ is a numerical constant. Indicating
with $M:=\left\|Ag(X)\right\|_{2}$, we can write

$\mathbb{P}(|g(X)^{\top}A^{\top}A\epsilon|>t)<2\exp\left(-c\frac{t^{2}}{M^{2}\left\lVert
A\right\rVert_{\textup{op}}^{2}}\right).$ (C.2)

Setting $t=y\left\lVert A\right\rVert_{\textup{op}}M$ in the previous
equation, we readily get

$\mathbb{P}(|g(X)^{\top}A^{\top}A\epsilon|<y\left\lVert
A\right\rVert_{\textup{op}}M)>1-2\exp\left(-cy^{2}\right).$ (C.3)

We will condition on this event for the rest of the proof.

On the other hand, a direct application of Theorem 6.3.2 in [47], gives

$\left\|\left\|A\epsilon\right\|_{2}-\varepsilon\left\|A\right\|_{F}\right\|_{\psi_{2}}\leq
C_{1}\left\lVert A\right\rVert_{\textup{op}},$ (C.4)

where $C_{1}$ is an absolute constant (that depends on $\varepsilon$). This
means that

$\mathbb{P}\left(\left|\left\|A\epsilon\right\|_{2}-\varepsilon\left\|A\right\|_{F}\right|>z\left\lVert
A\right\rVert_{\textup{op}}\right)<2\exp\left(-c_{1}z^{2}\right).$ (C.5)

This also implies

$\mathbb{P}\left(\left\|A\epsilon\right\|_{2}\geq\varepsilon\left\|A\right\|_{F}/\sqrt{2}\right)>1-2\exp\left(-c_{2}\frac{\left\|A\right\|_{F}^{2}}{\left\lVert
A\right\rVert_{\textup{op}}^{2}}\right).$ (C.6)

We will condition also on this other event for the rest of the proof.

Using the triangle inequality, (C.1) gives

$\left\|AY\right\|_{2}^{2}\geq\epsilon^{\top}A^{\top}A\epsilon+M^{2}-2y\left\lVert
A\right\rVert_{\textup{op}}M\geq\epsilon^{\top}A^{\top}A\epsilon-y^{2}\left\lVert
A\right\rVert_{\textup{op}}^{2}\geq\frac{\varepsilon^{2}}{2}\left\|A\right\|_{F}^{2}-y^{2}\left\lVert
A\right\rVert_{\textup{op}}^{2},$ (C.7)

where the second inequality is obtained through minimization over $M$. Setting
$y=\left\|A\right\|_{F}/(2\left\lVert A\right\rVert_{\textup{op}})$ we get

$\left\|AY\right\|_{2}\geq\frac{\varepsilon}{2}\left\|A\right\|_{F},$ (C.8)

with probability at least
$1-\exp\left(-c_{3}\left\|A\right\|_{F}^{2}/\left\lVert
A\right\rVert_{\textup{op}}^{2}\right)$, which concludes the proof. ∎

###  C.2 Bounds on the Extremal Eigenvalues of the Kernel

######  Lemma C.1.

Let $v\in\mathbb{R}^{d}$ be distributed as $V_{j:}$, for some $j\in[k]$,
independent from $X$. Then, we have

$\left\|\phi(Xv)\right\|_{\psi_{2}}=\mathcal{O}\left(\sqrt{N}\right),$ (C.9)

where the sub-Gaussian norm is intended over the probability space of $v$.
This result holds with probability $1$ over $X$.

###### Proof.

By triangular inequality, we have

$\left\|\phi(Xv)\right\|_{\psi_{2}}\leq\left\|\phi(Xv)-\mathbb{E}_{v}\left[\phi(Xv)\right]\right\|_{\psi_{2}}+\left\|\mathbb{E}_{v}\left[\phi(Xv)\right]\right\|_{\psi_{2}}.$
(C.10)

Let’s bound the two terms separately. As $\phi$ is an $L$-Lipschitz function,
and $\sqrt{d}v$ is a Lipschitz concentrated random vector, we have

$\left\|\phi(Xv)-\mathbb{E}_{v}\left[\phi(Xv)\right]\right\|_{\psi_{2}}\leq
CL\frac{\left\lVert X\right\rVert_{\textup{op}}}{\sqrt{d}}\leq
CL\frac{\left\|X\right\|_{F}}{\sqrt{d}}=CL\sqrt{N},$ (C.11)

where in the last equality we used the fact that
$\left\|x_{i}\right\|_{2}=\sqrt{d}$.

For the second term of (C.10), we have

$\left\|\mathbb{E}_{v}\left[\phi(Xv)\right]\right\|_{\psi_{2}}\leq
C\left\|\mathbb{E}_{v}\left[\phi(Xv)\right]\right\|_{2}.$ (C.12)

Let $(\phi(Xv))_{i}$ denote the $i$-th component of the vector $\phi(Xv)$. As
$v$ is a Gaussian vector with covariance $I/d$ and since
$\left\|x_{i}\right\|=\sqrt{d}$ for all $i\in[N]$, we have
$\mathbb{E}_{v}\left[(\phi(Xv))_{i}\right]=\mathbb{E}_{\rho}[\phi(\rho)]=\mathcal{O}\left(1\right)$,
where $\rho$ is a standard Gaussian random variable, and the last equality is
true since $\phi$ is Lipschitz. Thus, we have

$\left\|\mathbb{E}_{v}\left[\phi(Xv)\right]\right\|_{\psi_{2}}=\mathcal{O}\left(\sqrt{N}\right).$
(C.13)

Putting together (C.10), (C.11), and (C.13), we get the thesis. ∎

######  Lemma C.2.

Let $v\in\mathbb{R}^{d}$ be distributed as $V_{j:}$, for some $j\in[k]$,
independent from $X$. Then, we have

$\left\|\phi(Xv)-\mathbb{E}_{X}\left[\phi(Xv)\right]\right\|_{\psi_{2}}=\mathcal{O}\left(\sqrt{N}\right),$
(C.14)

where the sub-Gaussian norm is intended over the probability space of $v$.
This result holds with probability $1$ over $X$.

###### Proof.

By triangle inequality, we have

$\left\|\phi(Xv)-\mathbb{E}_{X}\left[\phi(Xv)\right]\right\|_{\psi_{2}}\leq\left\|\phi(Xv)\right\|_{\psi_{2}}+\left\|\mathbb{E}_{X}\left[\phi(Xv)\right]\right\|_{\psi_{2}}.$
(C.15)

The first term is $\mathcal{O}\left(\sqrt{N}\right)$, due to Lemma C.1.

For the second term, by Jensen inequality, we have

$\left\|\mathbb{E}_{X}\left[\phi(Xv)\right]\right\|_{\psi_{2}}\leq\mathbb{E}_{X}\left[\left\|\phi(Xv)\right\|_{\psi_{2}}\right]\leq
C\mathbb{E}_{X}\left[\sqrt{N}\right]=\mathcal{O}\left(\sqrt{N}\right).$ (C.16)

Thus, the thesis readily follows. ∎

######  Lemma C.3.

Let $Y:=\left(X^{*2}+(\alpha-1)\mathbb{E}_{X}\left[X^{*2}\right]\right)$ for
some $\alpha\in\mathbb{R}$, where $*$ refers to the Khatri-Rao product,
defined in Section 3. Then, we have

$\lambda_{\rm min}\left(YY^{\top}\right)=\Omega(d^{2}),$ (C.17)

with probability at least $1-\exp(-c\log^{2}N)$ over $X$.

###### Proof.

First, we want to compare $YY^{\top}$ with $\tilde{Y}\tilde{Y}^{\top}$, where

$\tilde{Y}:=X^{*2}-\mathbb{E}_{X}\left[X^{*2}\right].$ (C.18)

Let’s also define
$\bar{Y}:=\mathbb{E}_{X}\left[X^{*2}\right]:=\mathbf{1}\mu^{\top}$, where
$\mathbf{1}\in\mathbb{R}^{N}$ denotes a vector full of ones, and
$\mu:=\mathbb{E}\left[x_{1}\otimes x_{1}\right]$. We will refer to the $i$-th
row of $X$ with $x_{i}$. It is straightforward to verify that
$Y=\tilde{Y}+\alpha\bar{Y}$. Thus, we can write

$\displaystyle YY^{\top}$
$\displaystyle=\tilde{Y}\tilde{Y}^{\top}+\alpha^{2}\bar{Y}\bar{Y}^{\top}+\alpha\tilde{Y}\bar{Y}^{\top}+\alpha\bar{Y}\tilde{Y}^{\top}$
(C.19)
$\displaystyle=\tilde{Y}\tilde{Y}^{\top}+\alpha^{2}\left\|\mu\right\|_{2}^{2}\mathbf{1}\mathbf{1}^{\top}+\alpha\Lambda\mathbf{1}\mathbf{1}^{\top}+\alpha\mathbf{1}\mathbf{1}^{\top}\Lambda$
$\displaystyle=\tilde{Y}\tilde{Y}^{\top}+\left(\alpha\left\|\mu\right\|_{2}\mathbf{1}+\frac{\Lambda\mathbf{1}}{\left\|\mu\right\|_{2}}\right)\left(\alpha\left\|\mu\right\|_{2}\mathbf{1}+\frac{\Lambda\mathbf{1}}{\left\|\mu\right\|_{2}}\right)^{\top}-\frac{\Lambda\mathbf{1}\mathbf{1}^{\top}\Lambda}{\left\|\mu\right\|_{2}^{2}}$
$\displaystyle\succeq\tilde{Y}\tilde{Y}^{\top}-\frac{\Lambda\mathbf{1}\mathbf{1}^{\top}\Lambda}{\left\|\mu\right\|_{2}^{2}},$

where we define $\Lambda$ as a diagonal matrix such that
$\Lambda_{ii}=\mu^{\top}\tilde{Y}_{i:}$.

Since $\tilde{Y}_{i:}=x_{i}\otimes x_{i}-\mathbb{E}[x_{i}\otimes
x_{i}]=x_{i}\otimes x_{i}-\mu$, where $x_{i}$ is mean-0 and Lipschitz
concentrated, by Lemma B.3, we have that
$\left\|\tilde{Y}_{i:}\right\|_{\psi_{1}}\leq C$, for some numerical constant
$C$. Furthermore, we have that

$\left|\left\|\tilde{Y}_{i:}\right\|_{2}-d\right|=\left|\left\|\tilde{Y}_{i:}\right\|_{2}-\left\|x_{i}\otimes
x_{i}\right\|_{2}\right|\leq\left\|\tilde{Y}_{i:}-x_{i}\otimes
x_{i}\right\|_{2}=\left\|\mu\right\|_{2}.$ (C.20)

where the second step follows from triangle inequality. We can upper-bound the
RHS with the following argument:

$\left\|\mu\right\|_{2}=\left\|\mathbb{E}_{x_{1}}\left[x_{1}x_{1}^{\top}\right]\right\|_{F}\leq\sqrt{d}\left\lVert\mathbb{E}_{x_{1}}\left[x_{1}x_{1}^{\top}\right]\right\rVert_{\textup{op}}=\mathcal{O}\left(\sqrt{d}\right),$
(C.21)

where the last equality is justified by Lemma B.4, since $x_{i}$ is sub-
Gaussian. Then, plugging this last relation in (C.20), we have that, for all
$i\in[N]$,

$\left\|\tilde{Y}_{i:}\right\|_{2}=\Theta(d)<C_{y}d,$ (C.22)

for some numerical constant $C_{y}$.

Note that $\tilde{Y}$ has $N$ independent rows in $\mathbb{R}^{d^{2}}$ such
that $\left\|\tilde{Y}_{i:}\right\|_{\psi_{1}}\leq C$ for all $i$ and
$\mathop{\rm min}\nolimits_{i}\left\|\tilde{Y}_{i:}\right\|_{2}=\Omega(d)$.
Assumption 4 directly implies $N=o(d^{2}/\log^{4}d^{2})$. Thus, we can apply
Lemma B.1, setting $K=1$ and $K^{\prime}=C_{y}$ in the statement, and we get

$\lambda_{\rm
min}\left(\tilde{Y}\tilde{Y}^{\top}\right)=\Omega(d^{2})-cN^{1/4}d^{3/2}=\Omega(d^{2}),$
(C.23)

with probability at least $1-\exp(-c\sqrt{N})$ over $X$, where $c$ is a
numerical constant.

To conclude the proof, we have to control the last term of (C.19). As
$\Lambda_{ii}=\mu^{\top}\tilde{Y}_{i:}$ and
$\left\|\tilde{Y}_{i:}\right\|_{\psi_{1}}\leq C$, we can write

$\mathbb{P}(|\Lambda_{ii}|/\left\|\mu\right\|_{2}>t)<2\exp(-c_{1}t),$ (C.24)

where $c_{1}$ is a numerical constant, and the probability is intended over
$X$. After applying Lemma B.2 with $\gamma=1$, the last relation implies that

$\left\lVert\Lambda/\left\|\mu\right\|_{2}\right\rVert_{\textup{op}}=\mathcal{O}\left(\log^{2}N\right),$
(C.25)

with probability at least $1-2\exp(-c_{2}\log^{2}N)$ over $X$, where $c_{2}$
is a numerical constant.

Plugging (C.23) and (C.25) in (C.19), we get that, with probability at least
$1-\exp(-c_{3}\log^{2}N)$,

$\lambda_{\rm min}\left(YY^{\top}\right)\geq\lambda_{\rm
min}\left(\tilde{Y}\tilde{Y}^{\top}\right)-\left\lVert\frac{\Lambda\mathbf{1}\mathbf{1}^{\top}\Lambda}{\left\|\mu\right\|_{2}^{2}}\right\rVert_{\textup{op}}=\Omega(d^{2})-N\mathcal{O}\left(\log^{4}N\right)=\Omega(d^{2}).$
(C.26)

where the last equality is again consequence of Assumption 4. ∎

######  Lemma C.4.

We have that

$\lambda_{\rm min}\left(\mathbb{E}_{V}\left[K\right]\right)=\Omega(k),$ (C.27)

with probability at least $1-\exp(-c\log^{2}N)$ over $X$, where $c$ is an
absolute constant.

###### Proof.

We have

$\mathbb{E}_{V}\left[K\right]=\mathbb{E}_{V}\left[\sum_{i=1}^{k}\phi(XV_{i:}^{\top})\phi(XV_{i:}^{\top})^{\top}\right]=k\mathbb{E}_{v}\left[\phi(Xv)\phi(Xv)^{\top}\right]:=kM,$
(C.28)

where we used the shorthand $v$ to indicate a random variable distributed as
$V_{1:}$. We will also indicate with $x_{i}$ the $i$-th row of $X$.

Exploiting the Hermite expansion of $\phi$, we can write

$M_{ij}=\mathbb{E}_{v}\left[\phi(x_{i}^{\top}v)\phi(x_{j}^{\top}v)\right]=\sum_{n=0}^{+\infty}\mu_{n}^{2}\frac{\left(x_{i}^{\top}x_{j}\right)^{n}}{d^{n}}=\sum_{n=0}^{+\infty}\mu_{n}^{2}\frac{\left[\left(X^{*n}\right)\left(X^{*n}\right)^{\top}\right]_{ij}}{d^{n}},$
(C.29)

where $\mu_{n}$ is the $n$-th Hermite coefficient of $\phi$. Notice that the
previous expansion was possible since $\left\|x_{i}\right\|=\sqrt{d}$ for all
$i\in[N]$. As $\phi$ is non-linear, there exists $m\geq 2$ such that
$\mu_{m}^{2}>0$. In particular, we have $M\succeq\mu_{m}^{2}M_{m}$ in a p.s.d.
sense, where we define

$M_{m}:=\frac{1}{d^{m}}\left(X^{*n}\right)\left(X^{*n}\right).$ (C.30)

Let’s consider the case $m=2$. Then, since all the rows of $X$ are mean-0,
independent and Lipschitz concentrated, such that
$\left\|x_{i}\right\|=\sqrt{d}$, we can apply Lemma C.3 with $\alpha=1$ to
readily get

$\lambda_{\rm min}\left(M_{m}\right)=\Omega(1),$ (C.31)

with probability at least $1-\exp(-c\log^{2}N)$ over $X$.

Let’s now consider the case $m\geq 3$. For $i\neq j$ we can exploit again the
fact that $x_{i}$ is sub-Gaussian and independent from $x_{j}$, obtaining

$\mathbb{P}\left(\left|x_{i}^{\top}x_{j}\right|>t\sqrt{d}\right)<\exp\left(-c_{1}t^{2}\right).$
(C.32)

Performing a union bound we also get

$\mathbb{P}\left(\mathop{\rm
max}\nolimits_{i,j}\left|x_{i}^{\top}x_{j}\right|>t\sqrt{d}\right)<N^{2}\exp\left(-c_{1}t^{2}\right).$
(C.33)

Then, by Gershgorin circle theorem, we have that

$\lambda_{\rm min}\left(M_{m}\right)\geq 1-\mathop{\rm
max}\nolimits_{i}\sum_{j\neq
i}\frac{\left|\left(x_{i}^{\top}x_{j}\right)^{m}\right|}{d^{m}}\geq
1-\frac{N}{d^{m}}\mathop{\rm
max}\nolimits_{i,j}\left|(x_{i}^{\top}x_{j})^{m}\right|\geq
1-\frac{Nt^{m}}{d^{m/2}},$ (C.34)

where the last inequality holds with probability
$1-N^{2}\exp\left(-c_{1}t^{2}\right)$. Setting $t=\log N$, we get

$\lambda_{\rm min}\left(M_{m}\right)\geq
1-\frac{N\log^{m}N}{d^{m/2}}=1-\frac{N\log^{3}N}{d^{3/2}}\frac{\log^{m-3}N}{d^{m-3/2}}=1-o\left(\frac{N\log^{3}N}{d^{3/2}}\right)=1-o(1),$
(C.35)

where the last inequality is a consequence of Assumption 4. This result holds
with probability at least $1-N^{2}\exp\left(-c_{1}\log^{2}N\right)\geq
1-\exp\left(-c_{2}\log^{2}N\right)$, and the thesis readily follows. ∎

######  Lemma C.5.

We have that

$\lambda_{\rm min}\left(K\right)=\Omega(k).$ (C.36)

with probability at least $1-\exp\left(-c\log^{2}N\right)$ over $V$ and $X$,
where $c$ is an absolute constant.

###### Proof.

First we define a truncated version of $\Phi$, which we call $\bar{\Phi}$.
Over such truncated matrix, we will be able to use known concentrations
results, to prove that $\lambda_{\rm
min}\left(\bar{\Phi}\bar{\Phi}^{\top}\right)=\Omega(\lambda_{\rm
min}\left(\bar{G}\right))$, where we define
$\bar{G}:=\mathbb{E}_{V}\left[\bar{\Phi}\bar{\Phi}^{\top}\right]$. Finally, we
will prove closeness between $\bar{G}$ and $G$, which is analogously defined
as $G:=\mathbb{E}_{V}\left[\Phi\Phi^{\top}\right]$. Let’s introduce the
shorthand $v_{i}:=V_{i:}$. To be precise, we define

$\bar{\Phi}_{:j}=\phi(Xv_{j})\chi\left(\left\|\phi(Xv_{j})\right\|_{2}^{2}\leq
R\right),$ (C.37)

where $\chi$ is the indicator function. In this case, $\chi=1$ if
$\left\|\phi(Xv_{j})\right\|^{2}_{2}\leq R$, and $\chi=0$ otherwise. As this
is a column-wise truncation, it’s easy to verify that

$\Phi\Phi^{\top}\succeq\bar{\Phi}\bar{\Phi}^{\top}.$ (C.38)

Denoting with $v$ a generic weight $v_{i}$, we can also write

$G=k\mathbb{E}_{v}\left[\phi\left(Xv\right)\phi\left(Xv\right)^{\top}\right],$
(C.39)
$\bar{G}=k\mathbb{E}_{v}\left[\phi\left(Xv\right)\phi\left(Xv\right)^{\top}\chi\left(\left\|\phi\left(Xv\right)\right\|^{2}_{2}\leq
R\right)\right].$ (C.40)

Since all the columns of $\bar{\Phi}$ have limited norm with probability one,
we can use Matrix Chernoff Inequality (see Theorem 1.1 of [44]). In
particular, for $\delta\in[0,1]$, we have,

$\mathbb{P}\left(\lambda_{\rm
min}\left(\bar{\Phi}\bar{\Phi}^{\top}\right)\leq(1-\delta)\lambda_{\rm
min}\left(\bar{G}\right)\right)\leq
N\left(\frac{e^{-\delta}}{(1-\delta)^{1-\delta}}\right)^{\lambda_{\rm
min}\left(\bar{G}\right)/R},$ (C.41)

where we used the fact that $\lambda_{\rm
max}\left(\bar{\Phi}_{:j}\bar{\Phi}_{:j}^{\top}\right)\leq R$ and
$\bar{\Phi}\bar{\Phi}^{\top}=\sum_{j}\bar{\Phi}_{:j}\bar{\Phi}_{:j}^{\top}$.
Setting $\delta=1/2$ in the previous equation gives

$\mathbb{P}\left(\lambda_{\rm
min}\left(\bar{\Phi}\bar{\Phi}^{\top}\right)\leq\lambda_{\rm
min}\left(\bar{G}\right)/2\right)\leq\exp\left(-c\lambda_{\rm
min}\left(\bar{G}\right)/R+c_{1}\log N\right),$ (C.42)

where this probability is over $V$.

Finally, we prove that the matrices $G$ and $\bar{G}$ are “close”. In
particular, we have

$\displaystyle\left\lVert G-\bar{G}\right\rVert_{\textup{op}}$
$\displaystyle=k\left\lVert\mathbb{E}_{v}\left[\phi\left(Xv\right)\phi\left(Xv\right)^{\top}\chi\left(\left\|\phi\left(Xv\right)\right\|^{2}_{2}>R\right)\right]\right\rVert_{\textup{op}}$
(C.43) $\displaystyle\leq
k\mathbb{E}_{v}\left[\left\lVert\phi\left(Xv\right)\phi\left(Xv\right)^{\top}\chi\left(\left\|\phi\left(Xv\right)\right\|^{2}_{2}>R\right)\right\rVert_{\textup{op}}\right]$
$\displaystyle=k\mathbb{E}_{v}\left[\left\|\phi\left(Xv\right)\right\|_{2}^{2}\chi\left(\left\|\phi\left(Xv\right)\right\|^{2}_{2}>R\right)\right]$
$\displaystyle=k\int_{s=0}^{\infty}\mathbb{P}_{v}\left(\left\|\phi\left(Xv\right)\right\|_{2}\chi\left(\left\|\phi\left(Xv\right)\right\|^{2}_{2}>R\right)>\sqrt{s}\right)\mathrm{d}s$
$\displaystyle=k\int_{s=0}^{\infty}\mathbb{P}_{v}\left(\left\|\phi\left(Xv\right)\right\|_{2}>\mathop{\rm
max}\nolimits(\sqrt{R},\sqrt{s})\right)\mathrm{d}s,$

where we applied Jensen inequality in the second line. Let’s define
$\psi:=\left\|\phi\left(Xv\right)\right\|_{\psi_{2}}$, where the sub-Gaussian
norm is intended over the probability space of $v$. We have

$\displaystyle\left\lVert G-\bar{G}\right\rVert_{\textup{op}}$
$\displaystyle\leq k\int_{s=0}^{\infty}\exp\left(-c_{2}\frac{\mathop{\rm
max}\nolimits(R,s)}{\psi^{2}}\right)\mathrm{d}s$ (C.44) $\displaystyle\leq
k\int_{s=0}^{\infty}\exp\left(-c_{2}\frac{R+s}{2\psi^{2}}\right)\mathrm{d}s$
$\displaystyle=Ck\psi^{2}\exp\left(-c_{2}\frac{R}{2\psi^{2}}\right),$

where the first inequality follows from the definition of sub-Gaussian random
variable, and the second one from $\mathop{\rm max}\nolimits(R,s)\geq(R+s)/2$.

By Lemma C.1, we have $\psi=\mathcal{O}\left(\sqrt{N}\right)$. Then, setting
$R=k/\log^{2}N$, we get

$\left\lVert G-\bar{G}\right\rVert_{\textup{op}}\leq
Ck\psi^{2}\exp\left(-c\frac{R}{2\psi^{2}}\right)\leq
C_{1}k\exp\left(-c_{2}\frac{k}{N\log^{2}N}+\log N\right)=o(k),$ (C.45)

where the last equality is a consequence of Assumption 3. Notice that this
happens with probability 1 over $v$.

Due to Lemma C.4, we have that $\lambda_{\rm min}\left(G\right)=\Omega(k)$,
with probability at least $1-\exp\left(-c_{3}\log^{2}N\right)$ over $X$.
Conditioning on such event, we have

$\lambda_{\rm min}\left(\bar{G}\right)\geq\lambda_{\rm
min}\left(G\right)-\left\lVert
G-\bar{G}\right\rVert_{\textup{op}}=\Omega(k)-o(k)=\Omega(k).$ (C.46)

To conclude, looking back at (C.42), we also get $\lambda_{\rm
min}\left(\bar{\Phi}\bar{\Phi}^{\top}\right)=\Omega(k)$ with probability (over
$V$) at least

$1-\exp\left(-c\lambda_{\rm min}\left(\bar{G}\right)/R+c_{1}\log N\right)\geq
1-\exp\left(-c_{4}\frac{k\log^{2}N}{k}+c_{1}\log N\right)\geq
1-\exp\left(-c_{5}\log^{2}N\right).$ (C.47)

This concludes the proof. ∎

######  Lemma C.6.

We have that

$\lambda_{\rm
min}\left(\mathbb{E}_{V}\left[\tilde{K}\right]\right)=\Omega(k),$ (C.48)

with probability at least $1-\exp(-c\log^{2}N)$ over $X$, where $c$ is an
absolute constant.

###### Proof.

Indicating with $x_{i}$ the $i$-th row of $X$, and with
$\tilde{\phi}(x_{i}^{\top}v):=\phi(x_{i}^{\top}v)-\mathbb{E}_{X}\left[\phi(x_{1}^{\top}v)\right]$,
we can write

$\mathbb{E}_{V}\left[\tilde{\Phi}\tilde{\Phi}^{\top}\right]=\mathbb{E}_{V}\left[\sum_{i=1}^{k}\tilde{\phi}(XV_{i:}^{\top})\tilde{\phi}(XV_{i:}^{\top})^{\top}\right]=k\mathbb{E}_{v}\left[\tilde{\phi}(Xv)\tilde{\phi}(Xv)^{\top}\right]:=kM,$
(C.49)

where we use the shorthand $v$ to indicate a random variable distributed as
$V_{1:}$.

Exploiting the Hermite expansion of $\phi$, we can write

$\displaystyle M_{ij}$
$\displaystyle=\mathbb{E}_{v}\left[\tilde{\phi}(x_{i}^{\top}v)\tilde{\phi}(x_{j}^{\top}v)\right]$
(C.50)
$\displaystyle=\mathbb{E}_{v}\left[\left(\phi(x_{i}^{\top}v)-\mathbb{E}_{z}\left[\phi(z^{\top}v)\right]\right)\left(\phi(x_{j}^{\top}v)-\mathbb{E}_{y}\left[\phi(y^{\top}v)\right]\right)\right]$
$\displaystyle=\mathbb{E}_{vzy}\left[\phi(x_{i}^{\top}v)\phi(x_{j}^{\top}v)+\phi(z^{\top}v)\phi(y^{\top}v)-\phi(x_{i}^{\top}v)\phi(y^{\top}v)-\phi(x_{j}^{\top}v)\phi(z^{\top}v)\right]$
$\displaystyle=\mathbb{E}_{zy}\left[\sum_{n=0}^{+\infty}\mu_{n}^{2}\frac{\left(x_{i}^{\top}x_{j}\right)^{n}+\left(z^{\top}y\right)^{n}-\left(x_{i}^{\top}y\right)^{n}-\left(x_{j}^{\top}z\right)^{n}}{d^{n}}\right],$

where $\mu_{n}$ is the $n$-th Hermite coefficient of $\phi$, and $z\sim P_{X}$
and $y\sim P_{X}$ are two independent random variables, distributed as the
data and independent from them. Notice that the previous expansion was
possible since $\left\|x_{i}\right\|=\sqrt{d}$ for all $i\in[N]$. As $\phi$ is
non-linear, there exists $n\geq 2$ such that $\mu_{n}^{2}>0$. Let $m$ denote
one of such $n$’s (i.e, $m$ is such that $\mu_{m}^{2}>0$), and define
$\phi^{*}$ as the function that shares the same Hermite expansion as $\phi$,
but with its $m$-th coefficient being $0$. We have

$\displaystyle M_{ij}$
$\displaystyle=\mathbb{E}_{zy}\left[\sum_{n=0}^{+\infty}\mu_{n}^{2}\frac{\left(x_{i}^{\top}x_{j}\right)^{n}+\left(z^{\top}y\right)^{n}-\left(x_{i}^{\top}y\right)^{n}-\left(x_{j}^{\top}z\right)^{n}}{d^{n}}\right]$
(C.51) $\displaystyle=\mathbb{E}_{zy}\left[\sum_{n\neq
m}\mu_{n}^{2}\frac{\left(x_{i}^{\top}x_{j}\right)^{n}+\left(z^{\top}y\right)^{n}-\left(x_{i}^{\top}y\right)^{n}-\left(x_{j}^{\top}z\right)^{n}}{d^{n}}\right]$
$\displaystyle\qquad+\frac{\mu_{m}^{2}}{d^{m}}\left(\left(x_{i}^{\top}x_{j}\right)^{m}+\mathbb{E}_{zy}\left[\left(z^{\top}y\right)^{m}-\left(x_{i}^{\top}y\right)^{m}-\left(x_{j}^{\top}z\right)^{m}\right]\right)$
$\displaystyle=\mathbb{E}_{v}\left[\tilde{\phi}^{*}(x_{i}^{\top}v)\tilde{\phi}^{*}(x_{j}^{\top}v)\right]+\frac{\mu_{m}^{2}}{d^{m}}\left(\left(x_{i}^{\top}x_{j}\right)^{m}+\mathbb{E}_{zy}\left[\left(z^{\top}y\right)^{m}-\left(x_{i}^{\top}y\right)^{m}-\left(x_{j}^{\top}z\right)^{m}\right]\right)$
$\displaystyle=:\mathbb{E}_{v}\left[\tilde{\phi}^{*}(Xv)\tilde{\phi}^{*}(Xv)^{\top}\right]_{ij}+\mu_{m}^{2}\left[M_{m}\right]_{ij}.$

From the last equation we deduce that $M\succeq\mu_{m}^{2}M_{m}$, since
$\mathbb{E}_{v}\left[\tilde{\phi}^{*}(Xv)\tilde{\phi}^{*}(X^{\top}v)\right]$
is PSD. Proving the thesis becomes therefore equivalent to prove that
$\lambda_{\rm min}\left(M_{m}\right)=\Omega(1)$.

Let’s consider the case $m=2$. We can write

$\displaystyle\left[M_{m}\right]_{ij}$
$\displaystyle=\frac{1}{d^{2}}\mathbb{E}_{zy}\left[\left(x_{i}^{\top}x_{j}-z^{\top}x_{j}+x_{i}^{\top}y-z^{\top}y\right)\left(x_{i}^{\top}x_{j}+z^{\top}x_{j}-x_{i}^{\top}y-z^{\top}y\right)\right]$
(C.52)
$\displaystyle=\frac{1}{d^{2}}\mathbb{E}_{zy}\left[\left((x_{i}-z)^{\top}(x_{j}+y)\right)\left((x_{i}+z)^{\top}(x_{j}-y)^{\top}\right)\right],$

as the cross-terms will be linear in at least one between $y$ and $z$, and
$\mathbb{E}[x]=\mathbb{E}[z]=0$.

Going back in matrix notation, we can write

$M_{m}=\frac{1}{d^{2}}\mathbb{E}_{ZY}\left[\left((X+Z)(X-Y)^{\top}\circ(X-Z)(X+Y)^{\top}\right)\right],$
(C.53)

where $Y$ and $Z$ are $N\times d$ matrices respectively containing $N$ copies
of $y$ and $z$ in their rows.

We can now expand this term as

$\displaystyle M_{m}$
$\displaystyle=\frac{1}{d^{2}}\mathbb{E}_{ZY}\left[\left((X-Z)*(X+Z)\right)\left((X+Y)*(X-Y)\right)^{\top}\right]$
(C.54)
$\displaystyle=\frac{1}{d^{2}}\mathbb{E}_{Z}\left[(X-Z)*(X+Z)\right]\mathbb{E}_{Y}\left[(X+Y)*(X-Y)\right]^{\top}.$

Since $\mathbb{E}[Y]=\mathbb{E}[Z]=0$, the cross-terms cancel out again,
giving

$\mathbb{E}_{Z}\left[(X-Z)*(X+Z)\right]=X*X-\mathbb{E}_{Z}\left[Z*Z\right]=X*X-\mathbb{E}_{X}\left[X*X\right],$
(C.55)

where the last equality is because all the rows of $Z$ are distributed
accordingly to $P_{X}$. The same equation holds for the term with $Y$ in
(C.54). Thus, we can conclude that

$\lambda_{\rm min}\left(M_{m}\right)=\frac{1}{d^{2}}\lambda_{\rm
min}\left(TT^{\top}\right),$ (C.56)

where we defined $T=X*X-\mathbb{E}_{X}\left[X*X\right]$. As all the rows of
$X$ are mean-0, independent and Lipschitz concentrated, such that
$\left\|x_{i}\right\|=\sqrt{d}$, we can apply Lemma C.3 with $\alpha=0$ to
readily get

$\lambda_{\rm min}\left(M_{m}\right)=\Omega(1),$ (C.57)

with probability at least $1-\exp(-c\log^{2}N)$ over $X$.

Let’s now consider the case $m\geq 3$. Since $x$ is a sub-Gaussian random
variable, we have that
$\left\|\frac{x^{\top}y}{\sqrt{d}}\right\|_{\psi_{2}}=C$ in the probability
space of $x$. Notice that this holds for all $y$, as
$\left\|y\right\|_{2}=\sqrt{d}$. Then, its $m$-th momentum its bounded by
$m^{m/2}$, up to a multiplicative constant. As $m$ doesn’t depend by the
scalings of the problem, we can simply write

$\mathbb{E}_{x}\left[\left(\frac{x^{\top}y}{\sqrt{d}}\right)^{m}\right]=\mathcal{O}\left(1\right).$
(C.58)

In the same way, we can prove that

$\mathbb{E}_{x}\left[\left(\frac{x^{\top}x_{i}}{\sqrt{d}}\right)^{m}\right]=\mathcal{O}\left(1\right),\qquad\mathbb{E}_{y}\left[\left(\frac{y^{\top}x_{j}}{\sqrt{d}}\right)^{m}\right]=\mathcal{O}\left(1\right).$
(C.59)

Also, for $i\neq j$ we can exploit again the fact that $x_{i}$ is sub-Gaussian
and independent from $x_{j}$, obtaining

$\mathbb{P}\left(\left|x_{i}^{\top}x_{j}\right|>t\sqrt{d}\right)<\exp\left(-ct^{2}\right).$
(C.60)

Performing a union bound we also get

$\mathbb{P}\left(\mathop{\rm max}\nolimits_{i\neq
j}\left|x_{i}^{\top}x_{j}\right|>t\sqrt{d}\right)<N^{2}\exp\left(-ct^{2}\right).$
(C.61)

By Gershgorin circle theorem, and setting $t=\log N$, we have that

$\displaystyle\lambda_{\rm min}\left(M_{m}\right)$ $\displaystyle\geq
1-\mathcal{O}\left(d^{-m/2}\right)-\mathop{\rm max}\nolimits_{i}\sum_{j\neq
i}\frac{\left|\left(x_{i}^{\top}x_{j}\right)^{m}+\mathbb{E}_{xy}\left[\left(x^{\top}y\right)^{m}-\left(x_{i}^{\top}y\right)^{m}-\left(x_{j}^{\top}x\right)^{m}\right]\right|}{d^{m}}$
(C.62) $\displaystyle\geq 1-\mathcal{O}\left(d^{-m/2}\right)-N\mathop{\rm
max}\nolimits_{i\neq
j}\frac{\left|\left(x_{i}^{\top}x_{j}\right)^{m}+\mathbb{E}_{xy}\left[\left(x^{\top}y\right)^{m}-\left(x_{i}^{\top}y\right)^{m}-\left(x_{j}^{\top}x\right)^{m}\right]\right|}{d^{m}}$
$\displaystyle\geq
1-\mathcal{O}\left(Nd^{-m/2}\right)-\frac{N\log^{m}N}{d^{m/2}}=1-o(1),$

where the third inequality holds with probability at least
$1-N^{2}\exp\left(-c\log^{2}N\right)=1-\exp\left(-c_{1}\log^{2}N\right)$, and
the last equality is a consequence of Assumption 4. This concludes the proof.
∎

######  Lemma C.7.

We have that

$\lambda_{\rm min}\left(\tilde{K}\right)=\Omega(k),$ (C.63)

with probability at least $1-\exp(-c\log^{2}N)$ over $V$ and $X$, where $c$ is
an absolute constant.

###### Proof.

The proof follows the same exact path as Lemma C.5. The only difference is
that now $\psi$ (defined right before (C.44)) will be
$\psi:=\left\|\phi\left(Xv\right)-\mathbb{E}_{X}\left[\phi\left(Xv\right)\right]\right\|_{\psi_{2}}$.
To successfully conclude the proof, we have to show that
$\psi=\mathcal{O}\left(\sqrt{N}\right)$, which is done in Lemma C.2. ∎

######  Lemma C.8.

We have that

$\left\lVert\tilde{K}\right\rVert_{\textup{op}}=\mathcal{O}\left(\frac{k}{d}(N+d)\right),$
(C.64)

with probability at least $1-k\exp(-cd)$ over $V$ and $X$.

###### Proof.

We have that

$\tilde{K}=\tilde{\Phi}\tilde{\Phi}^{\top}=\sum_{i=1}^{\lceil
k/d\rceil}\tilde{\Phi}^{i}(\tilde{\Phi}^{i})^{\top},$ (C.65)

where we define $\tilde{\Phi}^{i}$ as the $N\times d$ matrix containing the
columns of $\tilde{\Phi}$ between $(i-1)d+1$ and $id$. If $i=\lceil
k/d\rceil$, we have that the number of columns is $k-d(\lceil k/d\rceil-1)\leq
d$.

Every $\tilde{\Phi}^{i}$ has mean-0, i.i.d. rows $\tilde{\phi}(V^{i}x_{j})$
(in the probability space of $X$), where $V^{i}$ contains the rows of $V$
between $(i-1)d+1$ and $id$. Notice that, besides corner cases, $V^{i}$ is a
$d\times d$ matrix.Since the $x_{j}$ are Lipschitz concentrated, we also have

$\left\|\tilde{\phi}(V^{i}x_{j})\right\|_{\psi_{2}}\leq C\left\lVert
V^{i}\right\rVert_{\textup{op}}=\mathcal{O}\left(1\right),$ (C.66)

where the last equality follows from Theorem 4.4.5 of [47] and from the fact
that both dimensions of $V^{i}$ are less or equal than $d$, and holds with
probability $1-\exp(-cd)$ over $V^{i}$. Conditioning on such event, a
straightforward application of Lemma B.5 gives

$\left\lVert\tilde{\Phi}^{i}(\tilde{\Phi}^{i})^{\top}\right\rVert_{\textup{op}}=\mathcal{O}\left(N+d\right),$
(C.67)

with probability at least $1-\exp(-c_{1}d)$ over $X$.

Thus, performing a union bound over the $i$-s, we get

$\mathop{\rm
max}\nolimits_{i}\left\lVert\Phi^{i}(\tilde{\Phi}^{i})^{\top}\right\rVert_{\textup{op}}=\mathcal{O}\left(N+d\right),$
(C.68)

with probability at least $1-k\exp(-c_{2}d)$. Conditioning over such event, we
have

$\left\lVert\tilde{K}\right\rVert_{\textup{op}}\leq\sum_{i=1}^{\lceil
k/d\rceil}\left\lVert\tilde{\Phi}^{i}(\tilde{\Phi}^{i})^{\top}\right\rVert_{\textup{op}}=\mathcal{O}\left(\frac{k}{d}(N+d)\right),$
(C.69)

which gives the thesis. ∎

###  C.3 Centering and Estimate of $\left\|A(z)\right\|_{F}$

In the following section it will be convenient to define
$E(z):=\nabla_{z}\phi(Vz)^{\top}\phi(XV^{\top})^{\top}$. Notice that this
gives $A(z)=E(z)K^{-1}$. Furthermore, we will use the notation $\tilde{\cdot}$
to indicate quantities involving a centering with respect to the random
variable $X$. In particular, we indicate

$\tilde{\Phi}=\Phi-\mathbb{E}_{X}[\Phi],\qquad\tilde{K}=\tilde{\Phi}\tilde{\Phi}^{\top},\qquad\tilde{E}:=\nabla_{z}\phi(Vz)^{\top}\tilde{\Phi}^{\top},\qquad\tilde{A}=\tilde{E}\tilde{K}^{-1}.$
(C.70)

For the sake of compactness, we will not re-introduce any of these quantities
in the statements or the proofs of the following lemmas, and we will drop the
dependence on $z$ of $A$, $\tilde{A}$, $E$ and $\tilde{E}$.

Note the results of this section will be applied only when
$\nu:=\mathbb{E}_{x_{i}}\left[\phi(Vx_{i})\right]$ is not the all-0 vector.
Therefore, we will assume $\left\|\nu\right\|_{2}>0$ through all the proofs
here. Along the section it will be convenient to recall that
$\nabla_{z}\phi(Vz)^{\top}=V^{\top}\text{diag}\left(\phi^{\prime}(Vz)\right)$.

######  Lemma C.9.

Let $\mathbf{1}\in\mathbb{R}^{N}$ denote a vector full of ones. Then, the
kernel matrix $K$ can be written as

$K=\tilde{K}+\eta\eta^{\top}-\lambda\lambda^{\top},$ (C.71)

where

$\eta:=\left\|\nu\right\|_{2}\mathbf{1}+\tilde{\Phi}\frac{\nu}{\left\|\nu\right\|_{2}}=\Phi\frac{\nu}{\left\|\nu\right\|_{2}},$
(C.72) $\lambda:=\tilde{\Phi}\frac{\nu}{\left\|\nu\right\|_{2}}.$ (C.73)

###### Proof.

Note that $\Phi=\tilde{\Phi}+\mathbf{1}\nu^{\top}$. Then,

$\displaystyle K$
$\displaystyle=\left(\tilde{\Phi}+\mathbf{1}\nu^{\top}\right)\left(\tilde{\Phi}+\mathbf{1}\nu^{\top}\right)^{\top}$
(C.74)
$\displaystyle=\tilde{\Phi}\tilde{\Phi}^{\top}+\tilde{\Phi}\nu\mathbf{1}^{\top}+\mathbf{1}\nu^{\top}\tilde{\Phi}^{\top}+\left\|\nu\right\|_{2}^{2}\mathbf{1}\mathbf{1}^{\top}$
$\displaystyle=\tilde{\Phi}\tilde{\Phi}^{\top}+\left(\left\|\nu\right\|_{2}\mathbf{1}+\frac{\tilde{\Phi}\nu}{\left\|\nu\right\|_{2}}\right)\left(\left\|\nu\right\|_{2}\mathbf{1}+\frac{\tilde{\Phi}\nu}{\left\|\nu\right\|_{2}}\right)^{\top}-\frac{\tilde{\Phi}\nu\nu^{\top}\tilde{\Phi}}{\left\|\nu\right\|_{2}^{2}}$
$\displaystyle=\tilde{\Phi}\tilde{\Phi}^{\top}+\eta\eta^{\top}-\lambda\lambda^{\top}.$

∎

######  Lemma C.10.

We have that

$\left|\left\|EK^{-1}\right\|_{F}-\left\|\tilde{E}K^{-1}\right\|_{F}\right|=\mathcal{O}\left(\frac{\sqrt{N+d}}{d}\right),$
(C.75)

with probability at least $1-\exp(-c\log^{2}N)-k\exp(-cd)$ over $X$ and $V$,
where $c$ is a numerical constant.

###### Proof.

We have

$E=\tilde{E}+\nabla_{z}\phi(Vz)^{\top}\nu\mathbf{1}^{\top}.$ (C.76)

By triangle inequality, we can write

$\left|\left\|EK^{-1}\right\|_{F}-\left\|\tilde{E}K^{-1}\right\|_{F}\right|\leq\left\|\nabla_{z}\phi(Vz)^{\top}\nu\mathbf{1}^{\top}K^{-1}\right\|_{F}=\left\|\nabla_{z}\phi(Vz)^{\top}\nu\right\|_{2}\left\|K^{-1}\mathbf{1}\right\|_{2}.$
(C.77)

Let’s look at the two factors separately. The first one can be upper bounded
as follows

$\left\|\nabla_{z}\phi(Vz)^{\top}\nu\right\|_{2}=\left\|V^{\top}\text{diag}\left(\phi^{\prime}(Vz)\right)\nu\right\|_{2}\leq\left\lVert
V\right\rVert_{\textup{op}}L\left\|\nu\right\|_{2}=\mathcal{O}\left(\sqrt{\frac{k}{d}}\left\|\nu\right\|_{2}\right),$
(C.78)

where the first inequality holds as $\phi$ is $L$-Lipschitz, and the second
equality holds with probability at least $1-e^{-cd}$ due to (C.183). Notice
that from (C.72) and (C.73), we can write

$\mathbf{1}=\frac{\eta}{\left\|\nu\right\|_{2}}-\frac{\lambda}{\left\|\nu\right\|_{2}}.$
(C.79)

By plugging this in the second factor of (C.77) and applying the triangle
inequality, we have

$\left\|K^{-1}\mathbf{1}\right\|_{2}=\frac{1}{\left\|\nu\right\|_{2}}\left\|K^{-1}\left(\eta-\lambda\right)\right\|_{2}\leq\frac{1}{\left\|\nu\right\|_{2}}\left(\left\|K^{-1}\eta\right\|_{2}+\left\|K^{-1}\lambda\right\|_{2}\right).$
(C.80)

Again, let’s control these last two terms separately. Since we can write
$\eta=\Phi\nu/\left\|\nu\right\|_{2}$, we get

$\left\|K^{-1}\eta\right\|_{2}=\left\|K^{-1}\Phi\nu/\left\|\nu\right\|_{2}\right\|_{2}\leq\left\lVert
K^{-1}\Phi\right\rVert_{\textup{op}}=\left\lVert\Phi^{+}\right\rVert_{\textup{op}}=\lambda_{\rm
min}\left(K\right)^{-1/2}=\mathcal{O}\left(\sqrt{\frac{1}{k}}\right),$ (C.81)

where the last equality holds with probability at $1-\exp(-c\log^{2}N)$, due
to Lemma C.5. We will condition on such event for the rest of the proof. For
the second term, we have

$\left\|K^{-1}\lambda\right\|_{2}=\left\|K^{-1}\tilde{\Phi}\nu/\left\|\nu\right\|_{2}\right\|_{2}\leq\left\lVert
K^{-1}\right\rVert_{\textup{op}}\left\lVert\tilde{\Phi}\right\rVert_{\textup{op}}=\lambda_{\rm
min}\left(K\right)^{-1}\mathcal{O}\left(\sqrt{\frac{k(N+d)}{d}}\right)=\mathcal{O}\left(\sqrt{\frac{N+d}{kd}}\right),$
(C.82)

where the first equality holds due to Lemma C.8 with probability at least
$1-k\exp(-c_{1}d)$. Let’s condition on this event too. Therefore, putting
together (C.80), (C.81) and (C.82), we have

$\left\|K^{-1}\mathbf{1}\right\|_{2}=\frac{1}{\left\|\nu\right\|_{2}}\left(\mathcal{O}\left(\sqrt{\frac{1}{k}}\right)+\mathcal{O}\left(\sqrt{\frac{N+d}{kd}}\right)\right)=\frac{1}{\left\|\nu\right\|_{2}}\mathcal{O}\left(\sqrt{\frac{N+d}{kd}}\right).$
(C.83)

By combining this last expression with (C.77)-(C.78), we conclude

$\left|\left\|EK^{-1}\right\|_{F}-\left\|\tilde{E}K^{-1}\right\|_{F}\right|=\mathcal{O}\left(\sqrt{\frac{k}{d}}\left\|\nu\right\|_{2}\right)\frac{1}{\left\|\nu\right\|_{2}}\mathcal{O}\left(\sqrt{\frac{N+d}{kd}}\right)=\mathcal{O}\left(\frac{\sqrt{N+d}}{d}\right),$
(C.84)

which gives the thesis. ∎

######  Lemma C.11.

We have that

$\left|\left\|\tilde{E}K^{-1}\right\|_{F}-\left\|\tilde{E}\left(K+\lambda\lambda^{\top}\right)^{-1}\right\|_{F}\right|=\mathcal{O}\left(\frac{\sqrt{N+d}}{d}\right),$
(C.85)

with probability at least $1-\exp(-c\log^{2}N)-k\exp(-cd)$ over $X$ and $V$,
where $c$ is a numerical constant.

###### Proof.

A direct application of the Sherman-Morrison formula gives

$\left(K+\lambda\lambda^{\top}\right)^{-1}=K^{-1}-\frac{K^{-1}\lambda\lambda^{\top}K^{-1}}{1+\lambda^{\top}K^{-1}\lambda}.$
(C.86)

By triangle inequality we know that
$\left|\left\|a\right\|_{2}-\left\|b\right\|_{2}\right|\leq\left\|a-b\right\|_{2}$.
This implies

$\left|\left\|\tilde{E}K^{-1}\right\|_{F}-\left\|\tilde{E}\left(K+\lambda\lambda^{\top}\right)^{-1}\right\|_{F}\right|\leq\left\|\tilde{E}K^{-1}-\tilde{E}\left(K+\lambda\lambda^{\top}\right)^{-1}\right\|_{F}=\left\|\tilde{E}\frac{K^{-1}\lambda\lambda^{\top}K^{-1}}{1+\lambda^{\top}K^{-1}\lambda}\right\|_{F},$
(C.87)

where the last equality is a consequence of (C.86). This term can be bounded
as

$\left\|\tilde{E}\frac{K^{-1}\lambda\lambda^{\top}K^{-1}}{1+\lambda^{\top}K^{-1}\lambda}\right\|_{F}\leq\left\lVert\tilde{E}\right\rVert_{\textup{op}}\left\|\frac{K^{-1}\lambda\lambda^{\top}K^{-1}}{1+\lambda^{\top}K^{-1}\lambda}\right\|_{F}=\left\lVert\tilde{E}\right\rVert_{\textup{op}}\frac{\lambda^{\top}K^{-2}\lambda}{1+\lambda^{\top}K^{-1}\lambda}.$
(C.88)

The first factor can be bounded as follows

$\displaystyle\left\lVert\tilde{E}\right\rVert_{\textup{op}}$
$\displaystyle=\left\lVert\nabla_{z}\phi(Vz)^{\top}\tilde{\Phi}^{\top}\right\rVert_{\textup{op}}\leq\left\lVert
V^{\top}\text{diag}\left(\phi^{\prime}(Vz)\right)\right\rVert_{\textup{op}}\left\lVert\tilde{\Phi}\right\rVert_{\textup{op}}$
(C.89)
$\displaystyle=\mathcal{O}\left(\sqrt{\frac{k}{d}}\right)\mathcal{O}\left(\sqrt{\frac{k(N+d)}{d}}\right)=\mathcal{O}\left(k\frac{\sqrt{N+d}}{d}\right),$

with probability at least $1-k\exp(-cd)$. Here, we used the fact that $\phi$
is Lipschitz, and we applied Lemma C.8 and Equation (C.183). Furthermore,
since $\left\lVert M\right\rVert_{\textup{op}}M-M^{2}$ is PSD for every
symmetric PSD matrix $M$, the following relation holds

$\lambda^{\top}K^{-2}\lambda\leq\left\lVert
K^{-1}\right\rVert_{\textup{op}}\lambda^{\top}K^{-1}\lambda.$ (C.90)

Thus,

$\frac{\lambda^{\top}K^{-2}\lambda}{1+\lambda^{\top}K^{-1}\lambda}\leq\left\lVert
K^{-1}\right\rVert_{\textup{op}}\frac{\lambda^{\top}K^{-1}\lambda}{1+\lambda^{\top}K^{-1}\lambda}\leq\left\lVert
K^{-1}\right\rVert_{\textup{op}}=\frac{1}{\lambda_{\rm
min}\left(K\right)}=\mathcal{O}\left(\frac{1}{k}\right),$ (C.91)

where the last equality holds with probability at least $1-\exp(-c\log^{2}N)$,
because of Lemma C.5. Plugging the last equation in (C.88) together with
(C.89), and comparing with (C.87), gives the desired result. ∎

######  Lemma C.12.

We have that

$\left|\left\|\tilde{E}\left(\tilde{K}+\eta\eta^{\top}\right)^{-1}\right\|_{F}-\left\|\tilde{E}\tilde{K}^{-1}\right\|_{F}\right|=\mathcal{O}\left(\frac{\sqrt{N+d}}{d}\right),$
(C.92)

with probability at least $1-\exp(-c\log^{2}N)-k\exp(-cd)$ over $X$ and $V$,
where $c$ is a numerical constant.

###### Proof.

An application of the Sherman-Morrison formula gives

$\left(\tilde{K}+\eta\eta^{\top}\right)^{-1}=\tilde{K}^{-1}-\frac{\tilde{K}^{-1}\eta\eta^{\top}\tilde{K}^{-1}}{1+\eta^{\top}\tilde{K}^{-1}\eta}.$
(C.93)

This implies

$\left|\left\|\tilde{E}\left(\tilde{K}+\eta\eta^{\top}\right)^{-1}\right\|_{F}-\left\|\tilde{E}\tilde{K}^{-1}\right\|_{F}\right|\leq\left\|\tilde{E}\left(\tilde{K}+\eta\eta^{\top}\right)^{-1}-\tilde{E}\tilde{K}^{-1}\right\|_{F}=\left\|\tilde{E}\frac{\tilde{K}^{-1}\eta\eta^{\top}\tilde{K}^{-1}}{1+\eta^{\top}\tilde{K}^{-1}\eta}\right\|_{F},$
(C.94)

where the last equality is a consequence of (C.93). This term can be bounded
as

$\left\|\tilde{E}\frac{\tilde{K}^{-1}\eta\eta^{\top}\tilde{K}^{-1}}{1+\eta^{\top}\tilde{K}^{-1}\eta}\right\|_{F}\leq\left\lVert\tilde{E}\right\rVert_{\textup{op}}\left\|\frac{\tilde{K}^{-1}\eta\eta^{\top}\tilde{K}^{-1}}{1+\eta^{\top}\tilde{K}^{-1}\eta}\right\|_{F}=\left\lVert\tilde{E}\right\rVert_{\textup{op}}\frac{\eta^{\top}\tilde{K}^{-2}\eta}{1+\eta^{\top}\tilde{K}^{-1}\eta}.$
(C.95)

The first factor can be bounded as in (C.89), in Lemma C.11, giving
$\left\lVert\tilde{E}\right\rVert_{\textup{op}}=\mathcal{O}\left(k\frac{\sqrt{N+d}}{d}\right)$
with probability at least $1-k\exp(-cd)$. Similarly to (C.90), we can write

$\eta^{\top}\tilde{K}^{-2}\eta\leq\left\lVert\tilde{K}^{-1}\right\rVert_{\textup{op}}\eta^{\top}\tilde{K}^{-1}\eta.$
(C.96)

Thus,

$\frac{\eta^{\top}\tilde{K}^{-2}\eta}{1+\eta^{\top}\tilde{K}^{-1}\eta}\leq\left\lVert\tilde{K}^{-1}\right\rVert_{\textup{op}}\frac{\eta^{\top}\tilde{K}^{-1}\eta}{1+\eta^{\top}\tilde{K}^{-1}\eta}\leq\left\lVert\tilde{K}^{-1}\right\rVert_{\textup{op}}=\frac{1}{\lambda_{\rm
min}\left(\tilde{K}\right)}=\mathcal{O}\left(\frac{1}{k}\right),$ (C.97)

where the last equality holds with probability at least $1-\exp(-c\log^{2}N)$,
because of Lemma C.7. Plugging the last equation in (C.95) together with the
bound on $\left\lVert\tilde{E}\right\rVert_{\textup{op}}$, and comparing with
(C.94), gives the desired result. ∎

######  Lemma C.13.

We have that

$\left|\left\|A\right\|_{F}-\left\|\tilde{A}\right\|_{F}\right|=\mathcal{O}\left(\frac{\sqrt{N+d}}{d}\right),$
(C.98)

with probability at least $1-\exp(-c\log^{2}N)-k\exp(-cd)$ over $X$ and $V$,
where $c$ is a numerical constant.

###### Proof.

Recalling that $A=EK^{-1}$ and $\tilde{A}=\tilde{E}\tilde{K}^{-1}$, by
triangle inequality we have

$\displaystyle\left|\left\|A\right\|_{F}-\left\|\tilde{A}\right\|_{F}\right|$
$\displaystyle\leq\left|\left\|EK^{-1}\right\|_{F}-\left\|\tilde{E}K^{-1}\right\|_{F}\right|$
(C.99)
$\displaystyle\qquad+\left|\left\|\tilde{E}K^{-1}\right\|_{F}-\left\|\tilde{E}\left(K+\lambda\lambda^{\top}\right)^{-1}\right\|_{F}\right|$
$\displaystyle\qquad+\left|\left\|\tilde{E}\left(\tilde{K}+\eta\eta^{\top}\right)^{-1}\right\|_{F}-\left\|\tilde{E}\tilde{K}^{-1}\right\|_{F}\right|$
$\displaystyle=\mathcal{O}\left(\frac{\sqrt{N+d}}{d}\right)$

where the inequality holds because of Lemma C.10, Lemma C.11, and Lemma C.12,
each of them with probability at least $1-\exp(-c\log^{2}N)-k\exp(-cd)$ over
$X$ and $V$. This gives the thesis. ∎

At this point, we are ready to prove Theorem 3.

###### Proof of Theorem 3.

We have

$\displaystyle\left\|A(z)\right\|_{F}$
$\displaystyle\leq\left\|\nabla_{z}\Phi(z)^{\top}\tilde{\Phi}^{\top}\tilde{K}^{-1}\right\|_{F}+\mathcal{O}\left(\sqrt{N+d}/d\right)$
(C.100)
$\displaystyle\leq\left\|\nabla_{z}\Phi(z)^{\top}\tilde{\Phi}^{\top}\right\|_{F}\left\lVert\tilde{K}^{-1}\right\rVert_{\textup{op}}+\mathcal{O}\left(\sqrt{N+d}/d\right)$
$\displaystyle=\lambda_{\mathop{\rm
min}\nolimits}^{-1}(K)\mathcal{I}(z)+\mathcal{O}\left(\sqrt{N+d}/d\right),$

where the first inequality is justified by Lemma C.13 and holds with
probability at least $1-\exp(-c\log^{2}N)-k\exp(-cd)$ over $X$ and $V$. For
the other bound of the first equation, we have

$\displaystyle\left\|A(z)\right\|_{F}$
$\displaystyle\geq\left\|\nabla_{z}\Phi(z)^{\top}\tilde{\Phi}^{\top}\tilde{K}^{-1}\right\|_{F}-\mathcal{O}\left(\sqrt{N+d}/d\right)$
(C.101)
$\displaystyle\geq\left\|\nabla_{z}\Phi(z)^{\top}\tilde{\Phi}^{\top}\right\|_{F}\lambda_{\mathop{\rm
min}\nolimits}\left(\tilde{K}^{-1}\right)-\mathcal{O}\left(\sqrt{N+d}/d\right)$
$\displaystyle=\lambda_{\mathop{\rm
max}\nolimits}^{-1}(\tilde{K})\mathcal{I}(z)-\mathcal{O}\left(\sqrt{N+d}/d\right),$

where the first inequality is justified again by Lemma C.13, and holds with
probability at least $1-\exp(-c\log^{2}N)-k\exp(-cd)$ over $X$ and $V$.

The second equation directly follows from Lemma C.8 and Lemma C.6. ∎

###  C.4 Estimate of $\left\|\mathcal{I}_{\textup{RF}}(z)\right\|_{F}$

The goal of this sub-Section is to estimate the value of the Frobenius norm of
the Interaction Matrix $\left\|\mathcal{I}_{\textup{RF}}\right\|_{F}$, defined
in (4.11). To do so, we will estimate the squared $\ell_{2}$ norms of its
columns. In particular, we define

$\mathcal{I}_{x}:=\left\|\nabla_{z}\phi(Vz)^{\top}\tilde{\phi}(Vx)\right\|_{2}.$
(C.102)

Thus, we have
$\left\|\mathcal{I}_{\textup{RF}}\right\|_{F}^{2}=\sum_{i}\mathcal{I}^{2}_{x_{i}}$.
In this section, with $x\sim P_{X}$ we refer to a generic input data, where we
drop the index for compactness. Also, we will assume $z\sim P_{X}$,
independent from the training set.

Recalling that

$\nabla_{z}\phi(Vz)^{\top}=V^{\top}\text{diag}\left(\phi^{\prime}(Vz)\right),$
(C.103)

we have

$\mathcal{I}_{x}=\left\|V^{\top}\text{diag}\left(\phi^{\prime}(Vz)\right)\tilde{\phi}(Vx)\right\|_{2}.$
(C.104)

Along the proof, the following shorthands and notations will be useful

$\mathcal{X}_{-jl}=\sum_{m\neq
j}V_{lm}x_{m},\qquad\mathcal{X}_{l}=\sum_{m=1}^{d}V_{lm}x_{m},$ (C.105)
$\mathcal{Z}_{-jl}=\sum_{m\neq
j}V_{lm}z_{m},\qquad\mathcal{Z}_{l}=\sum_{m=1}^{d}V_{lm}z_{m},$ (C.106)
$I_{j}=\sum_{l=1}^{k}V_{lj}\phi^{\prime}\left(\mathcal{Z}_{l}\right)\tilde{\phi}\left(\mathcal{X}_{l}\right),$
(C.107)

which imply

$\mathcal{I}^{2}_{x}=\sum_{j=1}^{d}I_{j}^{2}.$ (C.108)

It will also be convenient to use the following notation

$B_{-jl}:=\left(\phi^{\prime\prime}\left(\mathcal{Z}_{-jl}\right)\tilde{\phi}\left(\mathcal{X}_{-jl}\right)z_{j}+\phi^{\prime}\left(\mathcal{Z}_{-jl}\right)\phi^{\prime}\left(\mathcal{X}_{-jl}\right)x_{j}\right),$
(C.109)
$B_{jl}:=\left(\phi^{\prime\prime}\left(\mathcal{Z}_{l}\right)\tilde{\phi}\left(\mathcal{X}_{l}\right)z_{j}+\phi^{\prime}\left(\mathcal{Z}_{l}\right)\phi^{\prime}\left(\mathcal{X}_{l}\right)x_{j}\right).$
(C.110)

For compactness, we will not necessarily re-introduce such quantities in the
statements or the proofs of the lemmas in this section.

######  Lemma C.14.

Indicating with $c$ a numerical constant, the following statements hold

$\mathop{\rm
max}\nolimits_{l}\left|\tilde{\phi}(\mathcal{X}_{l})\right|=\mathcal{O}\left(\log
k\right),$ (C.111)

with probability at least $1-\exp(-c\log^{2}k)$, over $x$ and $V$;

$\mathop{\rm
max}\nolimits_{l}\left|\tilde{\phi}(\mathcal{X}_{-jl})\right|=\mathcal{O}\left(\log
k\right),$ (C.112)

with probability at least $1-\exp(-c\log^{2}k)$, over $x$ and
$\\{V_{li}\\}_{i\neq j,1\leq l\leq k}$;

$\left|\sum_{l=1}^{k}V_{lj}\phi^{\prime}\left(\mathcal{Z}_{-jl}\right)\tilde{\phi}\left(\mathcal{X}_{-jl}\right)\right|=o\left(\frac{k}{d}\right),$
(C.113)

with probability at least $1-\exp(-c\log^{2}k)$, over $x$ and $V$.

###### Proof.

For the first result, as $\phi$ is Lipschitz and centered with respect to $x$,
its sub-Gaussian norm (in the probability space of $x$) is
$\mathcal{O}\left(\left\|V_{l:}\right\|_{2}\right)=\mathcal{O}\left(1\right)$,
where the last equality holds with probability at least $1-e^{-c_{0}d}$ over
$V_{l:}$, because of Theorem 3.1.1 in [47]. In particular, with a union bound
over $V_{l:}$, we have $\mathcal{O}\left(\mathop{\rm
max}\nolimits_{l}\left\|V_{l:}\right\|_{2}\right)=\mathcal{O}\left(1\right)$
with probability at least $1-ke^{-c_{0}d}\geq 1-e^{-c_{1}d}$, where the last
inequality is justified by Assumption 4. Thus, by Lemma B.2, $\mathop{\rm
max}\nolimits_{l}\left|\tilde{\phi}(\mathcal{X}_{l})\right|=\mathcal{O}\left(\log
k\right)$, with probability at least
$1-\exp(-c_{1}d)-\exp(-c_{2}\log^{2}k)\geq 1-\exp(-c_{3}\log^{2}k)$, over $x$
and $V$.

Notice that, with the same argument, we can prove that $\mathop{\rm
max}\nolimits_{l}\left|\tilde{\phi}(\mathcal{X}_{-jl})\right|=\mathcal{O}\left(\log
k\right)$, with probability at least $1-\exp(-c_{4}\log^{2}k)$, over $x$ and
$\\{V_{li}\\}_{i\neq j,1\leq l\leq k}$. We will condition on such event for
the rest of the proof.

For the last statement, we have

$\sum_{l=1}^{k}V_{lj}\phi^{\prime}\left(\mathcal{Z}_{-jl}\right)\tilde{\phi}\left(\mathcal{X}_{-jl}\right)=:V_{:j}^{\top}u,$
(C.114)

where $u$ is a vector independent from $V_{:j}$ such that

$\left\|u\right\|_{2}\leq\sqrt{k}L\mathop{\rm
max}\nolimits_{l}\left|\tilde{\phi}\left(\mathcal{X}_{-jl}\right)\right|=\mathcal{O}\left(\log(k)\sqrt{k}\right).$
(C.115)

Since $\left\|V_{:j}\right\|_{\psi_{2}}\leq C/\sqrt{d}$, we have

$\mathbb{P}\left(\left|\sum_{l=1}^{k}V_{lj}\phi^{\prime}\left(\mathcal{Z}_{-jl}\right)\tilde{\phi}\left(\mathcal{X}_{-jl}\right)\right|>\frac{\sqrt{d}}{\sqrt{k}/\log^{2}k}\frac{k}{d}\right)<\exp(-c_{5}\log^{2}k),$
(C.116)

where the probability is intended over $V_{:j}$. Thus, using Assumption 3, we
readily get the desired result. ∎

######  Lemma C.15.

We have that

$\left\|\mathbb{E}_{x}\left[\phi^{\prime}\left(\mathcal{X}_{-jl}\right)x_{j}\right]\right\|_{\psi_{2}}=\mathcal{O}\left(\frac{1}{\sqrt{d}}\right),$
(C.117)

where the norm is intended over the probability space of $\\{V_{li}\\}_{i\neq
j}$.

###### Proof.

Let’s define an auxiliary random variable $\rho\sim\mathcal{N}(0,1/d)$,
independent from any other random variable in the problem. Let’s also define
$V^{\prime}_{l:}$ as the copy of $V_{l:}$ where we replaced the $j$-th
component with $\rho$. Notice that $V^{\prime}_{l:}$ is a Gaussian vector with
covariance $I/d$. Let’s also define $\mathcal{X}^{\prime}_{l}$ in the same
way, i.e., replacing $V_{lj}$ with $\rho$ in its expression. All the tail
norms $\left\|\cdot\right\|_{\psi_{r}}$ in the proof will be referred to the
probability space of $V^{\prime}_{l:}$.

Since $\phi^{\prime}$ is a Lipschitz function, we can write

$\left|\mathbb{E}_{x}\left[\phi^{\prime}\left(\mathcal{X}_{-jl}\right)x_{j}\right]-\mathbb{E}_{x}\left[\phi^{\prime}\left(\mathcal{X}^{\prime}_{l}\right)x_{j}\right]\right|\leq
L_{1}\mathbb{E}_{x}\left[|\rho|x_{j}^{2}\right]\leq C|\rho|,$ (C.118)

where we used the fact that $x_{j}$ is sub-Gaussian in the last inequality,
and where $C$ is a numerical constant. Let’s now look at the function

$\varphi(v):=\mathbb{E}_{x}\left[\phi^{\prime}\left(v^{\top}x\right)x_{j}\right].$
(C.119)

We have

$\displaystyle\left|\varphi(v+v^{\prime})-\varphi(v)\right|$
$\displaystyle=\left|\mathbb{E}_{x}\left[\left(\phi^{\prime}\left((v+v^{\prime})^{\top}x\right)-\phi^{\prime}\left(v^{\top}x\right)\right)x_{j}\right]\right|$
(C.120)
$\displaystyle\leq\mathbb{E}_{x}\left[\left|\left(\phi^{\prime}\left((v+v^{\prime})^{\top}x\right)-\phi^{\prime}\left(v^{\top}x\right)\right)\right||x_{j}|\right]$
$\displaystyle\leq\mathbb{E}_{x}\left[L_{1}|v^{\prime\top}x||x_{j}|\right].$

Since $x$ is sub-Gaussian (and therefore also $x_{j}$ is) we have that
$|v^{\prime\top}x||x_{j}|$ is sub-exponential with norm (with respect to the
probability space of $x$) upper bounded by
$C_{1}\left\|v^{\prime}\right\|_{2}$. Then, we have

$\left|\varphi(v+v^{\prime})-\varphi(v)\right|\leq\mathbb{E}_{x}\left[L_{1}|v^{\prime\top}x||x_{j}|\right]\leq
C_{2}\left\|v^{\prime}\right\|_{2}.$ (C.121)

This implies that $\left\|\varphi\right\|_{\text{Lip}}\leq C_{2}$.

As $V^{\prime}_{l:}$ is Gaussian (and hence Lipschitz concentrated) with
covariance $I/d$, we can write

$\left\|\varphi(V^{\prime}_{l:})-\mathbb{E}_{V^{\prime}_{l:}}\left[\varphi(V^{\prime}_{l:})\right]\right\|_{\psi_{2}}=\mathcal{O}\left(\frac{1}{\sqrt{d}}\right).$
(C.122)

Furthermore,

$\mathbb{E}_{V^{\prime}_{l:}}\left[\varphi(V^{\prime}_{l:})\right]=\mathbb{E}_{x}\left[x_{j}\mathbb{E}_{V^{\prime}_{l:}}\left[\phi^{\prime}\left({V^{\prime}_{l:}}^{\top}x\right)\right]\right]=\mathbb{E}_{x}\left[x_{j}\right]\mathbb{E}_{\rho^{\prime}}\left[\phi^{\prime}\left(\rho^{\prime}\right)\right]=0,$
(C.123)

where $\rho^{\prime}$ is a standard Gaussian distribution independent of $x$.
Note that the second step holds since $\left\|x\right\|_{2}=\sqrt{d}$, and the
last step is justified by $\mathbb{E}[x]=0$.

This last equation implies

$\displaystyle\left\|\mathbb{E}_{x}\left[\phi^{\prime}\left(\mathcal{X}_{-jl}\right)x_{j}\right]\right\|_{\psi_{2}}$
$\displaystyle\leq\left\|\mathbb{E}_{x}\left[\phi^{\prime}\left(\mathcal{X}_{-jl}\right)x_{j}\right]-\mathbb{E}_{x}\left[\phi^{\prime}\left(\mathcal{X}^{\prime}_{l}\right)x_{j}\right]\right\|_{\psi_{2}}+\left\|\mathbb{E}_{x}\left[\phi^{\prime}\left(\mathcal{X}^{\prime}_{l}\right)x_{j}\right]\right\|_{\psi_{2}}$
(C.124) $\displaystyle\leq
C\left\|\rho\right\|_{\psi_{2}}+\left\|\varphi(V^{\prime}_{l:})\right\|_{\psi_{2}}=\mathcal{O}\left(\frac{1}{\sqrt{d}}\right),$

where the first term in the last line is justified by (C.118). In fact, the
random variable on the LHS is (with probability one) upper bounded by
$C|\rho|$. Then, the bound subsists also between their tail norms.

Thus,

$\mathbb{P}_{\\{V_{li}\\}_{i\neq
j}}\left(\left|\mathbb{E}_{x}\left[\phi^{\prime}\left(\mathcal{X}_{-jl}\right)x_{j}\right]\right|>t\right)=\mathbb{P}_{V^{\prime}_{l:}}\left(\left|\mathbb{E}_{x}\left[\phi^{\prime}\left(\mathcal{X}_{-jl}\right)x_{j}\right]\right|>t\right)<2\exp\left(-cd\,t^{2}\right),$
(C.125)

where with $\mathbb{P}_{\\{V_{li}\\}_{i\neq j}}$ we refer to the probability
space of $\\{V_{li}\\}_{i\neq j}$. Note that the first equality is true as the
statement in the probability does not depend on the value of $\rho$. From
this, we readily get the thesis. ∎

######  Lemma C.16.

We have that

$\left|I_{j}-\sum_{l}V_{lj}^{2}\left(\phi^{\prime\prime}\left(\mathcal{Z}_{-jl}\right)\tilde{\phi}\left(\mathcal{X}_{-jl}\right)z_{j}+\phi^{\prime}\left(\mathcal{Z}_{-jl}\right)\phi^{\prime}\left(\mathcal{X}_{-jl}\right)x_{j}\right)\right|=o\left(\frac{k}{d}\right).$
(C.126)

with probability at least $1-\exp(-c\log^{2}k)$ over $x$, $z$ and $V$, where
$c$ is an absolute constant.

###### Proof.

Exploiting Taylor’s Theorem, and the fact that both $\phi^{\prime}$ and
$\phi^{\prime\prime}$ are Lipschitz, we can write

$\phi^{\prime}\left(\mathcal{Z}_{l}\right)=\phi^{\prime}\left(\mathcal{Z}_{-jl}\right)+\phi^{\prime\prime}\left(\mathcal{Z}_{-jl}\right)V_{lj}z_{j}+a_{1lj},$
(C.127)
$\tilde{\phi}\left(\mathcal{X}_{l}\right)=\phi\left(\mathcal{X}_{-jl}\right)+\phi^{\prime}\left(\mathcal{X}_{-jl}\right)V_{lj}x_{j}+a_{2lj}-\mathbb{E}_{x}\left[\phi\left(\mathcal{X}_{-jl}\right)+\phi^{\prime}\left(\mathcal{X}_{-jl}\right)V_{lj}x_{j}+a_{2lj}\right],$
(C.128)

where $|a_{1lj}|=\mathcal{O}\left(V_{lj}^{2}z_{j}^{2}\right)$ and
$|a_{2lj}|=\mathcal{O}\left(V_{lj}^{2}x_{j}^{2}\right)$. In the previous two
equations, we expanded $\phi^{\prime}$ around $\mathcal{Z}_{-jl}$ and $\phi$
around $\mathcal{X}_{-jl}$. For the rest of the proof (except from when
expectations with respect to $x$ are taken) we condition on the events that
both $|x_{j}|$ and $|z_{j}|$ are $\mathcal{O}\left(\log k\right)$. As they are
sub-Gaussian, this happens with probability at least $1-e^{-c_{1}\log^{2}k}$
over $x$ and $z$.

Invoking Lemma B.6, and setting $t=k/d^{1/\alpha}$, we can write (for
$\alpha\in(0,2]$)

$\sum_{l=1}^{k}|V_{lj}|^{2/\alpha}=\mathcal{O}\left(\frac{k}{d^{1/\alpha}}\right),$
(C.129)

with probability at least $1-\exp(-c_{2}k^{\alpha/2}/\log k)$. This is true
since $\mathbb{E}_{\rho}\left[\rho^{2/\alpha}\right]=C_{\alpha}$, where $\rho$
is a standard Gaussian random variable. Thus, with probability at least
$1-\exp(-c_{3}k^{1/5}/\log k)$ over $V$, we jointly have

$\sum_{l=1}^{k}|V_{lj}|^{2}=\mathcal{O}\left(\frac{k}{d}\right),\qquad\sum_{l=1}^{k}|V_{lj}|^{3}=\mathcal{O}\left(\frac{k}{d^{3/2}}\right),\qquad\sum_{l=1}^{k}|V_{lj}|^{5}=\mathcal{O}\left(\frac{k}{d^{5/2}}\right).$
(C.130)

We will condition on these events too. It will also be convenient to condition
on the high probability events described by Lemma C.14. Thus, our discussion
is now restricted to a probability space over $x$, $z$ and $V$ of measure at
least $1-e^{-c_{4}\log^{2}k}-e^{-c_{5}d}$.

We are now ready to estimate the cross terms of the product
$V_{lj}\phi^{\prime}\left(\mathcal{Z}_{l}\right)\tilde{\phi}\left(\mathcal{X}_{l}\right)$,
exploiting the expansions in (C.127) and (C.128). Let’s control the sums over
$l$ of all of them separately.

  1. (a)

$\phi^{\prime}\left(\mathcal{Z}_{l}\right)\left(a_{2lj}-\mathbb{E}_{x}\left[a_{2lj}\right]\right)$

$\displaystyle\left|\sum_{l=1}^{k}V_{lj}\phi^{\prime}\left(\mathcal{Z}_{l}\right)\left(a_{2lj}-\mathbb{E}_{x}\left[a_{2lj}\right]\right)\right|\leq
C_{1}\sum_{l=1}^{k}|V_{lj}|L\left(|a_{2lj}|+\mathbb{E}_{x}\left[|a_{2lj}|\right]\right)$
(C.131) $\displaystyle\qquad\leq
C_{2}\left(x_{j}^{2}+1\right)\sum_{l=1}^{k}|V_{lj}|^{3}=\mathcal{O}\left(\frac{k\log^{2}k}{d^{3/2}}\right)=o\left(\frac{k}{d}\right),$

where the second inequality is justified by the fact that $x_{j}$ is sub-
Gaussian, and the last equality by Assumption 4.

  2. (b)

$\tilde{\phi}\left(\mathcal{X}_{l}\right)a_{1jl}$

$\displaystyle\left|\sum_{l=1}^{k}V_{lj}\tilde{\phi}\left(\mathcal{X}_{l}\right)a_{1jl}\right|\leq
C_{3}z_{j}^{2}\sum_{l=1}^{k}|V_{lj}|^{3}\left|\tilde{\phi}\left(\mathcal{X}_{l}\right)\right|\leq
C_{3}z_{j}^{2}\mathop{\rm
max}\nolimits_{l}\left|\tilde{\phi}\left(\mathcal{X}_{l}\right)\right|\sum_{l=1}^{k}|V_{lj}|^{3}$
(C.132)
$\displaystyle\qquad=\mathcal{O}\left(\log^{2}(k)\log(k)\frac{k}{d^{3/2}}\right)=o\left(\frac{k}{d}\right),$

where the second to last equality follows from Lemma C.14, and the last from
Assumption 4.

  3. (c)

$a_{1lj}\left(a_{2lj}-\mathbb{E}_{x}\left[a_{2lj}\right]\right)$ (as we
counted it twice)

$\left|\sum_{l=1}^{k}V_{lj}a_{1lj}\left(a_{2lj}-\mathbb{E}_{x}\left[a_{2lj}\right]\right)\right|\leq
C_{4}\left(x_{j}^{2}+1\right)z^{2}_{j}\sum_{l=1}^{k}|V_{lj}|^{5}=\mathcal{O}\left(\log^{4}(k)\frac{k}{d^{5/2}}\right)=o\left(\frac{k}{d}\right).$
(C.133)

  4. (d)

$\phi^{\prime}\left(\mathcal{Z}_{-jl}\right)\tilde{\phi}\left(\mathcal{X}_{-jl}\right)$

$\left|\sum_{l=1}^{k}V_{lj}\phi^{\prime}\left(\mathcal{Z}_{-jl}\right)\tilde{\phi}\left(\mathcal{X}_{-jl}\right)\right|=o\left(\frac{k}{d}\right),$
(C.134)

as it directly follows from Lemma C.14.

  5. (e)

$\left(\phi^{\prime}\left(\mathcal{Z}_{-jl}\right)+\phi^{\prime\prime}\left(\mathcal{Z}_{-jl}\right)V_{lj}z_{j}\right)\mathbb{E}_{x}\left[\phi^{\prime}\left(\mathcal{X}_{-jl}\right)V_{lj}x_{j}\right]$

$\displaystyle\left|\sum_{l=1}^{k}V_{lj}\left(\phi^{\prime}\left(\mathcal{Z}_{-jl}\right)+\phi^{\prime\prime}\left(\mathcal{Z}_{-jl}\right)V_{lj}z_{j}\right)V_{lj}\mathbb{E}_{x}\left[\phi^{\prime}\left(\mathcal{X}_{-jl}\right)x_{j}\right]\right|$
(C.135) $\displaystyle\qquad\leq\mathop{\rm
max}\nolimits_{l}\left|\phi^{\prime}\left(\mathcal{Z}_{-jl}\right)+\phi^{\prime\prime}\left(\mathcal{Z}_{-jl}\right)V_{lj}z_{j}\right|\mathop{\rm
max}\nolimits_{l}\left|\mathbb{E}_{x}\left[\phi^{\prime}\left(\mathcal{X}_{-jl}\right)x_{j}\right]\right|\sum_{l=1}^{k}|V_{lj}|^{2}$
$\displaystyle\qquad\leq\left(L+L_{1}\mathop{\rm
max}\nolimits_{l}\left|V_{lj}\right||z_{j}|\right)\mathop{\rm
max}\nolimits_{l}\left|\mathbb{E}_{x}\left[\phi^{\prime}\left(\mathcal{X}_{-jl}\right)x_{j}\right]\right|\sum_{l=1}^{k}|V_{lj}|^{2}$
$\displaystyle\qquad=\mathcal{O}\left(\left(1+\frac{\log^{2}k}{\sqrt{d}}\right)\frac{\log
k}{\sqrt{d}}\right)\mathcal{O}\left(\frac{k}{d}\right)=o\left(\frac{k}{d}\right),$

where the second to last equality comes from the fact that both
$\left\|V_{lj}\right\|_{\psi_{2}}$ and
$\left\|\mathbb{E}_{x}\left[\phi^{\prime}\left(\mathcal{X}_{-jl}\right)x_{j}\right]\right\|_{\psi_{2}}$
are $\mathcal{O}\left(\frac{1}{\sqrt{d}}\right)$ (see Lemma C.15) and holds
with probability at least $1-e^{-c_{6}\log^{2}k}$ over $V$. The last equality
is true for Assumption 4.

  6. (f)

$\phi^{\prime\prime}\left(\mathcal{Z}_{-jl}\right)V_{lj}z_{j}\phi^{\prime}\left(\mathcal{X}_{-jl}\right)V_{lj}x_{j}$
As $\phi$ and $\phi^{\prime}$ are Lipschitz

$\left|\sum_{l=1}^{k}V_{lj}\phi^{\prime\prime}\left(\mathcal{Z}_{-jl}\right)V_{lj}z_{j}\phi^{\prime}\left(\mathcal{X}_{-jl}\right)V_{lj}x_{j}\right|\leq
LL_{1}|x_{j}z_{j}|\sum_{l=1}^{k}|V_{lj}|^{3}=\mathcal{O}\left(\log^{2}k\frac{k}{d^{3/2}}\right)=o\left(\frac{k}{d}\right).$
(C.136)

Then, we are left only with two cross terms, and we can write

$I_{j}=\sum_{l}V_{lj}^{2}\left(\phi^{\prime\prime}\left(\mathcal{Z}_{-jl}\right)\tilde{\phi}\left(\mathcal{X}_{-jl}\right)z_{j}+\phi^{\prime}\left(\mathcal{Z}_{-jl}\right)\phi^{\prime}\left(\mathcal{X}_{-jl}\right)x_{j}\right)+\textup{rest},$
(C.137)

where $|\textup{rest}|$ can be upper-bounded by the sum of the terms (a)-(f),
which gives

$\left|I_{j}-\sum_{l}V_{lj}^{2}\left(\phi^{\prime\prime}\left(\mathcal{Z}_{-jl}\right)\tilde{\phi}\left(\mathcal{X}_{-jl}\right)z_{j}+\phi^{\prime}\left(\mathcal{Z}_{-jl}\right)\phi^{\prime}\left(\mathcal{X}_{-jl}\right)x_{j}\right)\right|=o\left(\frac{k}{d}\right)$
(C.138)

with probability at least $1-\exp(-c_{5}d)-\exp(-c_{7}\log^{2}k)$ over $x$,
$z$ and $V$. Hence, the thesis follows after using Assumption 4. ∎

######  Lemma C.17.

We have that

$\left|\sum_{l=1}^{k}V_{lj}^{2}B_{-jl}-\frac{1}{d}\sum_{l=1}^{k}B_{-jl}\right|=o\left(\frac{k}{d}\right),$
(C.139)

with probability at least $1-\exp(-c\log^{2}k)$ over $x$, $z$ and $V$, where
$c$ is an absolute constant.

###### Proof.

We have

$\sum_{l=1}^{k}V_{lj}^{2}B_{-jl}=\sum_{l=1}^{k}\left(V_{lj}^{2}-\mathbb{E}_{V}\left[V_{lj}^{2}\right]\right)B_{-jl}+\frac{1}{d}\sum_{l=1}^{k}B_{-jl},$
(C.140)

since $\mathbb{E}_{V}\left[V_{lj}^{2}\right]=1/d$ for all $l,j$.

We call $v_{l}:=V_{lj}^{2}-\mathbb{E}_{V}\left[V_{lj}^{2}\right]$. Then,
$v=(v_{1},\ldots,v_{k})$ is a mean-0 vector with independent and sub-
exponential entries with norm $\mathcal{O}\left(1/d\right)$. This implies
$\left\|v\right\|_{\psi_{1}}=\mathcal{O}\left(1/d\right)$. Thus,

$\mathbb{P}_{v}\left(|v^{\top}u|>t\right)<2\exp\left(-c\frac{dt}{\left\|u\right\|_{2}}\right),$
(C.141)

for every vector $u$ independent from $v$. If we define $u_{l}:=B_{-jl}$, we
have

$\left\|u\right\|_{2}\leq\sqrt{k}\left(\mathop{\rm
max}\nolimits_{l}|B_{-jl}|\right)\leq\sqrt{k}\left(L^{2}|x_{j}|+L_{1}|z_{j}|\mathop{\rm
max}\nolimits_{l}\left|\tilde{\phi}(\mathcal{X}_{-jl})\right|\right)=\mathcal{O}\left(\log^{2}(k)\sqrt{k}\right),$
(C.142)

where the last equality comes from the fact that $x_{j}$ and $z_{j}$ are sub-
Gaussian, and from the second statement in Lemma C.14. This holds with
probability at least $1-e^{-c_{1}d}-e^{-c_{2}\log^{2}k}$ over $x$, $z$ and
$\\{V_{li}\\}_{i\neq j,1\leq l\leq k}$, and we will condition on this event.

Then, merging this last result with (C.141) and setting
$t=\log^{4}k\sqrt{k}/d$ we have

$\mathbb{P}_{v}\left(|v^{\top}u|>\frac{\log^{4}k\sqrt{k}}{d}\right)<2\exp\left(-c_{3}\log^{2}k\right).$
(C.143)

Performing a union bound gives the thesis. ∎

######  Lemma C.18.

We have that

$\left|\sum_{l=1}^{k}B_{-jl}-\sum_{l=1}^{k}B_{jl}\right|=o(k),$ (C.144)

with probability at least at least $1-\exp(-c\log^{2}k)$ over $x$, $z$ and
$V$, where $c$ is an absolute constant.

###### Proof.

Let’s condition on

$|x_{j}|=\mathcal{O}\left(\log k\right),\qquad|z_{j}|=\mathcal{O}\left(\log
k\right),\qquad\mathop{\rm
max}\nolimits_{l}|V_{lj}|=\mathcal{O}\left(\frac{\log k}{\sqrt{d}}\right).$
(C.145)

These events happen with probability at least $1-\exp(-c\log^{2}k)$, as
$\left\|x_{j}\right\|_{\psi_{2}}=\mathcal{O}\left(1\right)$,
$\left\|z_{j}\right\|_{\psi_{2}}=\mathcal{O}\left(1\right)$ and
$\left\|V_{jl}\right\|_{\psi_{2}}=\mathcal{O}\left(1/\sqrt{d}\right)$. The
probability is over $x$, $z$ and $V$. Also, we have $\mathop{\rm
max}\nolimits_{l}\left|\tilde{\phi}(\mathcal{X}_{-jl})\right|=\mathcal{O}\left(\log
k\right)$ with probability at least $1-e^{-c_{1}\log^{2}k}$ over $x$, $z$ and
$V$, for the second statement in Lemma C.14. Let’s condition on these high
probability events for the rest of the proof, whenever we do not take
expectations with respect to $x$.

Exploiting that $\phi$, $\phi^{\prime}$ and $\phi^{\prime\prime}$ are all
Lipschitz,

$\mathop{\rm
max}\nolimits_{l}\left|\phi^{\prime\prime}\left(\mathcal{Z}_{-jl}\right)-\phi^{\prime\prime}\left(\mathcal{Z}_{l}\right)\right|=\mathcal{O}\left(\frac{\log^{2}k}{\sqrt{d}}\right),$
(C.146) $\displaystyle\mathop{\rm
max}\nolimits_{l}\left(\left|\phi\left(\mathcal{X}_{-jl}\right)-\phi\left(\mathcal{X}_{-jl}\right)\right|+\left|\mathbb{E}_{x}\left[\phi\left(\mathcal{X}_{-jl}\right)-\phi\left(\mathcal{X}_{-jl}\right)\right]\right|\right)$
(C.147)
$\displaystyle\qquad\leq\mathcal{O}\left(\frac{\log^{2}k}{\sqrt{d}}\right)+\mathop{\rm
max}\nolimits_{l}|V_{lj}|\mathbb{E}_{x}[|x_{j}|]=\mathcal{O}\left(\frac{\log^{2}k}{\sqrt{d}}\right),$
$\mathop{\rm
max}\nolimits_{l}\left|\phi^{\prime}\left(\mathcal{Z}_{-jl}\right)-\phi^{\prime}\left(\mathcal{Z}_{l}\right)\right|=\mathcal{O}\left(\frac{\log^{2}k}{\sqrt{d}}\right),$
(C.148) $\mathop{\rm
max}\nolimits_{l}\left|\phi^{\prime}\left(\mathcal{X}_{-jl}\right)-\phi^{\prime}\left(\mathcal{X}_{-jl}\right)\right|=\mathcal{O}\left(\frac{\log^{2}k}{\sqrt{d}}\right).$
(C.149)

Then, controlling all the cross terms, we get

$\mathop{\rm
max}\nolimits_{l}|B_{-jl}-B_{jl}|=\mathcal{O}\left(\frac{\log^{4}k}{\sqrt{d}}\right),$
(C.150)

where this scaling is justified by the leading term

$\mathop{\rm
max}\nolimits_{l}\left|\phi^{\prime\prime}\left(\mathcal{Z}_{-jl}\right)-\phi^{\prime\prime}\left(\mathcal{Z}_{l}\right)\right|\mathop{\rm
max}\nolimits_{l}\left|\tilde{\phi}(\mathcal{X}_{-jl})\right||z_{j}|=\mathcal{O}\left(\frac{\log^{2}k}{\sqrt{d}}\log
k\log k\right).$ (C.151)

Thus, we can conclude