Robust Feature Learning for Multi-Index Models in High Dimensions

## Abstract

Abstract Recently, there have been numerous studies on feature learning with neural networks, specifically on learning single- and multi-index models where the target is a function of a low-dimensional projection of the input.
Prior works have shown that in high dimensions, the majority of the compute and data resources are spent on recovering the low-dimensional projection; once this subspace is recovered, the remainder of the target can be learned independently of the ambient dimension. However, implications of feature learning in adversarial settings remain unexplored.
In this work, we take the first steps towards understanding adversarially robust feature learning with neural networks. Specifically, we prove that the hidden directions of a multi-index model offer a Bayes optimal low-dimensional projection for robustness against ℓ 2 subscript ℓ 2 \ell_{2} roman_ℓ start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT -bounded adversarial perturbations under the squared loss, assuming that the multi-index coordinates are statistically independent from the rest of the coordinates.
Therefore, robust learning can be achieved by first performing standard feature learning, then robustly tuning a linear readout layer on top of the standard representations. In particular, we show that adversarially robust learning is just as easy as standard learning, in the sense that the additional number of samples needed to robustly learn multi-index models when compared to standard learning, does not depend on dimensionality.

## 1 Introduction

A crucial capability of neural networks is their ability to hierarchically learn useful features,
and to avoid the curse of dimensionality by *adapting* to potential low-dimensional structures in data through (regularized) empirical risk minimization (ERM) [, ]. Recently, a theoretical line of work has demonstrated that gradient-based training, which is not a priori guaranteed to implement ERM due to non-convexity, also demonstrates similar behavior and efficiently learns functions of low-dimensional projections [, , , , , ] or functions with certain hierarchical properties [, , ].
These theoretical insights provided a useful avenue for explaining standard feature learning mechanisms in neural networks.

On the other hand, it has been empirically observed that deep neural networks trained with respect to standard losses are susceptible to adversarial attacks; small perturbations in the input may not be detectable by humans, yet they can significantly alter the prediction performed by the model []. To overcome this issue, a popular approach is to instead minimize the adversarially robust empirical risk []. However, unlike its standard counterpart, achieving successful generalization of deep neural networks on robust test risk has been particularly challenging, and even the standard performance of the model can degrade once adversarial training is performed []. Given this, one may wonder if robust neural networks can still adapt to specific problem structures that enhance generalization. To explore this, we focus on hidden low-dimensionality, a well-known structural property, and aim to answer the following fundamental question:

*Can neural networks retain their statistical adaptivity to low-dimensional structures
when trained for robustness against adversarial perturbations?*

We answer this question positively by providing the following contributions.

- •
When considering $\ell_{2}$-constrained perturbations,
Bayes optimal predictors can be constructed by projecting the input data onto the low-dimensional subspace defined by the target function. In this sense, the optimal low-dimensional projection remains unchanged compared to standard learning.
- •
Consequently, provided that they have access to an oracle that is able to recover the low-dimensional target subspace, neural networks can achieve a sample complexity that is *independent of the ambient dimension* when robustly learning multi-index models.
This is achieved by minimizing the empirical adversarial risk with respect to the second layer.
While the basic definition of empirical adversarial risk implies computational complexity dependent on input dimension, by simply projecting the inputs onto the low-dimensional target subspace, the computational complexity can also be made independent of the input dimension.
- •
An oracle for recovering the low-dimensional target subspace can be constructed by training the first layer of a two-layer neural network with a standard loss function, as demonstrated by many prior works. By combining our results with two particular choices of oracle implementation [, ], we provide end-to-end guarantees for robustly learning multi-index models with gradient-based algorithms.

### 1.1 Related Works

#### Feature Learning for Single/Multi-Index Models.

Many recent works have focused on proving benefits of feature learning, allowing the neural network weights to travel far from initialization, as opposed to freezing weights around initialization in lazy training [] which is equivalent to using the Neural Tangent Kernel [].
When using online SGD on the squared loss, [] showed that the complexity of learning single-index models with known link function depends on a quantity called information exponent.
Gradient-based learning of single-index models with information exponent 1 was studied in [, , ], and [] considered multi-index polynomials where the equivalent of information exponent is at most 2.
For general information exponent, [] provided an algorithm for gradient-based learning using two-layer neural networks.
A feature learning analysis faithful to SGD without modifications was presented in [] for learning the XOR.
The counterpart of information exponent for multi-index models, the leap exponent, was introduced in [].
Considering SGD on the squared loss as an example of a Correlational Statistical Query (CSQ) algorithm, [] provided CSQ-optimal algorithms for learning single-index models. Further improvements to the isotropic sample complexity were achieved by either considering structured anisotropic Gaussian data [, ], or the sparsity of the hidden direction [].

More recently, it was observed that gradient-based learning can go beyond CSQ algorithms by reusing batches [, , ], or by changing the loss function []. In such cases, the algorithm becomes an instance of a Statistical Query (SQ) learner, and the sample complexity is characterized by the generative exponent of the link function [].

The above works mostly exist in a narrow-width setting where design choices guarantee that neurons do not signficantly interact with each other. Another line of research focused on the mean-field or wide limits of two-layer neural networks that takes the mean-field interaction between neurons into account [, , ] for providing learnability guarantees [, , , , , ]. In particular, the mean-field Langevin algorithm provides global convergence guarantees for two-layer neural networks [, ], leading to sample complexity linear in an effective dimension for learning sparse parities [, ] and multi-index models [].

#### Adversarially Robust Learning.

The existence of small worst-case or adversarial perturbations that can significantly change the prediction of deep neural networks was first demonstrated in []. Among many defences proposed, one effective approach is adversarial training introduced by [], which is based on solving a min-max problem to perform robust optimization. One observation regarding this algorithm is that it tends to decrease the standard performance of the model []. Therefore, the following works studied the hardness of robust learning and established a statistical separation in a simple mixture of Gaussians setting [], or computational separation by proving statistical query lower bounds []. Further studies focused on exact characterizations of the robust and standard error, as well as the fundamental and the algorithmic tradeoffs between robustness and accuracy in the context of linear regression [], mixture of Gaussians classification [], and in the random features model []. Closer to our work, [] showed that this tradeoff is mitigated when the data enjoy a low-dimensional structure. However, the focus there is on binary classification and generalized linear models, where the features live on a low-dimensional manifold. Here, we consider a multi-index model wherein the response depends on a low-dimensional projection of inputs. In addition, in [] it is assumed that the manifold structure is known and the focus is on population adversarial risk and accuracy (assuming infinite samples with fixed dimension), while here we consider algorithms for feature learning, and derive rates of convergence for adversarial risk.

In this work, we provide an alternative narrative compared to the line of work above by showing that in a high-dimensional regression setting, learning multi-index models that are robust against $\ell_{2}$ perturbations can be as easy as standard learning. We achieve this result by focusing on the feature learning capability of neural networks, i.e. their ability to capture low-dimensional projections.

#### Notation.

For Euclidean vectors, $\mathopen{}\mathclose{{}\left\langle{\cdot},{\cdot}}\right\rangle$ and $\mathopen{}\mathclose{{}\left\|{\cdot}}\right\|$ denote the Euclidean inner product and norm respectively. For tensors, $\mathopen{}\mathclose{{}\left\|{\cdot}}\right\|_{\mathrm{F}}$ and $\mathopen{}\mathclose{{}\left\|{\cdot}}\right\|$ denote the Frobenius and operator norms respectively. We use $\mathbb{S}^{k-1}$ for the unit sphere in $\mathbb{R}^{k}$, and $\tau_{k}$ denotes the uniform probability measure on $\mathbb{S}^{k-1}$.

## 2 Problem Setup: Feature Learning and Adversarial Robustness

#### Statistical Model.

Consider a regression setting where the input $\boldsymbol{x}\in\mathbb{R}^{d}$ and the target $y\in\mathbb{R}$ are generated from a distribution $(\boldsymbol{x},y)\sim\mathcal{P}$. For a prediction function $f:\mathbb{R}^{d}\to\mathbb{R}$, its population adversarial risk is defined as

$$ $\mathrm{AR}(f)\coloneqq\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[ {\max_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq \varepsilon}(f(\boldsymbol{x}+\boldsymbol{\delta})-y)^{2}}}\right],$ (2.1) $$

where the expectation is over all random variables inside the brackets. Note that under this model, the adversary can perform a worst-case perturbation on the input, with a budget of $\varepsilon$ measured in $\ell_{2}$-norm, before passing it to the model.
Given a (non-parametric) family of prediction functions $\mathcal{F}$, our goal is to learn a predictor that achieves the optimal adversarial risk given by

$$ $\mathrm{AR}^{*}\coloneqq\min_{f\in\mathcal{F}}\mathrm{AR}(f),$ (2.2) $$

We focus on learners of the form of two-layer neural networks with width $N$, given as

$$ $f(\boldsymbol{x};\boldsymbol{a},\boldsymbol{W},\boldsymbol{b})=\boldsymbol{a}^ {\top}\sigma(\boldsymbol{W}\boldsymbol{x}+\boldsymbol{b}),$ (2.3) $$

where $\boldsymbol{a}\in\mathbb{R}^{N}$ is the second layer weights and $\boldsymbol{W}\in\mathbb{R}^{N\times d}$ and $\boldsymbol{b}\in\mathbb{R}^{N}$ are the first layer weights and biases. To avoid overloading the notation we use
$\mathrm{AR}(f(\cdot;\boldsymbol{a},\boldsymbol{W},\boldsymbol{b}))=\mathrm{AR}
(\boldsymbol{a},\boldsymbol{W},\boldsymbol{b}).$
Given access to $n$ i.i.d. samples $\{\boldsymbol{x}^{(i)},y^{(i)}\}_{i=1}^{n}$ from $\mathcal{P}$, the goal is to learn the network parameters $\boldsymbol{a},\boldsymbol{W}$, and $\boldsymbol{b}$ in such a way that the quantity $\mathrm{AR}(\boldsymbol{a},\boldsymbol{W},\boldsymbol{b})$ is close to the optimal adversarial risk $\mathrm{AR}^{*}$.

A long line of recent works has shown that neural networks are particularly efficient in regression tasks when the target is a function of a low-dimensional projection of the input, see e.g. [].
We also make the same assumption that the data follows a *multi-index model*,

$$ $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{y\,|\,\boldsymbol{x}}} \right]=g(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{u}_{1}},{ \boldsymbol{x}}}\right\rangle,\ldots,\mathopen{}\mathclose{{}\left\langle{ \boldsymbol{u}_{k}},{\boldsymbol{x}}}\right\rangle),$ (2.4) $$

for all $\boldsymbol{x}\in\mathbb{R}^{d}$, where $g:\mathbb{R}^{k}\to\mathbb{R}$ is the link function, and we assume $\boldsymbol{u}_{1},\ldots,\boldsymbol{u}_{k}$ are orthonormal without loss of generality. Let $\boldsymbol{U}\in\mathbb{R}^{k\times d}$ be an orthonormal matrix whose rows are given by $(\boldsymbol{u}_{i})$; we use the shorthand notation $g(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{u}_{1}},{\boldsymbol{x}}}
\right\rangle,\ldots,\mathopen{}\mathclose{{}\left\langle{\boldsymbol{u}_{k}},
{\boldsymbol{x}}}\right\rangle):=g(\boldsymbol{U}\boldsymbol{x})$. In the special case where $k=1$, this model reduces to a *single-index model*. In this paper, we consider the setting where $k\ll d$, and in particular $k=\mathcal{O}(1)$.

#### Feature Learning.

In the context of training two-layer neural networks when learning multi-index models, feature learning refers to recovering the target directions $\boldsymbol{U}$ via the first layer weights $\boldsymbol{W}$. Successful feature learning reduces the effective dimension of the problem from the input dimension $d$ to the number of target directions $k$, and circumvents the curse of dimensionality when $k\ll d$.

The complexity of recovering $\boldsymbol{U}$ depends on multiple factors such as the choice of algorithm as well as the properties of the link function. We will provide an overview of some existing results for recovering $\boldsymbol{U}$ with neural networks in Section 4.2, along with several concrete examples.

## 3 Optimal Representations for Robust Learning

In this section, we demonstrate that under $\ell_{2}$-constrained perturbations,
the optimal low-dimensional representations for robust learning coincides with those in a standard setting, both of which are given by the target directions $\boldsymbol{U}$. Crucially, our result relies on the following assumption on the input distribution.

###### Assumption 1 .

Suppose $\tilde{\boldsymbol{U}}\in\mathbb{R}^{(d-k)\times d}$ is any orthonormal matrix whose rows complete the rows of $\boldsymbol{U}$ into a basis of $\mathbb{R}^{d}$. Then, $y$ and $\boldsymbol{U}\boldsymbol{x}$ are jointly independent from $\tilde{\boldsymbol{U}}\boldsymbol{x}$.

Introducing the notation $\boldsymbol{x}_{\parallel}\coloneqq\boldsymbol{U}\boldsymbol{x}$ and $\boldsymbol{x}_{\perp}\coloneqq\tilde{\boldsymbol{U}}\boldsymbol{x}$ for any $\boldsymbol{x}\in\mathbb{R}^{d}$, the above assumption states that the distribution of the input $\boldsymbol{x}$ is such that $\boldsymbol{x}_{\parallel}$, the coordinates that enter the statistical model, are independent from $\boldsymbol{x}_{\perp}$, the coordinates that do not.
For example, Assumption 1 holds when $\boldsymbol{x}$ is a Gaussian random vector with isotropic covariance, or more generally $\boldsymbol{x}=\boldsymbol{U}^{\top}\boldsymbol{U}\boldsymbol{z}_{1}+\tilde{
\boldsymbol{U}}^{\top}\tilde{\boldsymbol{U}}\boldsymbol{z}_{2}$ for independent vectors $\boldsymbol{z}_{1},\boldsymbol{z}_{2}\in\mathbb{R}^{d}$. Moreover, Assumption 1, specifically the fact that $y\,|\,\boldsymbol{x}_{\parallel}$ is independent of $\boldsymbol{x}_{\perp}$, automatically implies (2.4) for some $g:\mathbb{R}^{k}\to\mathbb{R}$.
We present a central result below along with its proof.

###### Theorem 1 .

Suppose Assumption 1 holds and (2.2) admits a minimizer. Then, there exists a function $f^{*}:\mathbb{R}^{d}\to\mathbb{R}$ of the form $f^{*}(\boldsymbol{x})=h(\boldsymbol{U}\boldsymbol{x})$ for some $h:\mathbb{R}^{k}\to\mathbb{R}$ such that

$$ $\mathrm{AR}(f^{*})\leq\mathrm{AR}^{*},$ (3.1) $$

with equality when $f^{*}\in\mathcal{F}$. Further, $h$ is represented as $h(\boldsymbol{z})=\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{f(
\boldsymbol{x})\,|\,\boldsymbol{U}\boldsymbol{x}=\boldsymbol{z}}}\right]$ for some $f\in\mathcal{F}$.

Remark.
To understand the significance of the above result,
define the function class $\mathcal{H}=\{\boldsymbol{z}\mapsto\operatorname{\mathbb{E}}\mathopen{}
\mathclose{{}\left[{f(\boldsymbol{x})\,|\,\boldsymbol{U}\boldsymbol{x}=
\boldsymbol{z}}}\right]\text{ for }f\in\mathcal{F}\}$,
and observe that the last statement of the theorem reads

$$ $\min_{h\in\mathcal{H}}\mathrm{AR}(h(\boldsymbol{U}\cdot))\leq\mathrm{AR}^{*}.$ $$

To achieve the optimal adversarial risk $\mathrm{AR}^{*}$, one only needs to $(i)$ learn the target directions $\boldsymbol{U}$, and $(ii)$ approximate functions in a $k$-dimensional subspace rather than $d$.
For two-layer neural networks, the first layer $\boldsymbol{W}$ recovers $\boldsymbol{U}$, and the remaining parameters $\boldsymbol{a}$ and $\boldsymbol{b}$ are used to approximate the optimal $h$.
While this recipe is general,
we provide specific implications in the next section.

Proof. We will show that for every $f\in\mathcal{F}$, $h(\boldsymbol{z})=\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{f(
\boldsymbol{x})\,|\,\boldsymbol{U}\boldsymbol{x}=\boldsymbol{z}}}\right]$ gives $\mathrm{AR}(h(\boldsymbol{U}\cdot))\leq\mathrm{AR}(f)$. Then, choosing $f$ to be some minimizer of $\mathrm{AR}$ yields the desired result.

Define the residuals $r_{y}(\boldsymbol{x}_{\parallel},\boldsymbol{\delta}_{\parallel})\coloneqq y-h
(\boldsymbol{x}_{\parallel}+\boldsymbol{\delta}_{\parallel})$, and $r_{f}(\boldsymbol{x},\boldsymbol{\delta})\coloneqq f(\boldsymbol{x}+
\boldsymbol{\delta})-h(\boldsymbol{x}_{\parallel}+\boldsymbol{\delta}_{
\parallel})$. Then, by a decomposition of the squared loss and the tower property of conditional expectation,

$$ $\displaystyle\mathrm{AR}(f)$ $\displaystyle=\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{ \operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_{\mathopen{} \mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq\varepsilon}r_{y}( \boldsymbol{x}_{\parallel},\boldsymbol{\delta}_{\parallel})^{2}+r_{f}( \boldsymbol{x},\boldsymbol{\delta})^{2}-2r_{y}(\boldsymbol{x}_{\parallel}, \boldsymbol{\delta}_{\parallel})r_{f}(\boldsymbol{x},\boldsymbol{\delta})\, \Big{|}\,\boldsymbol{x}_{\parallel},y}}\right]}}\right]$ $\displaystyle\geq\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_ {\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq\varepsilon} r_{y}(\boldsymbol{x}_{\parallel},\boldsymbol{\delta}_{\parallel})^{2}+ \operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{r_{f}(\boldsymbol{x}, \boldsymbol{\delta})^{2}\,\big{|}\,\boldsymbol{x}_{\parallel},y}}\right]-2r_{y }(\boldsymbol{x}_{\parallel},\boldsymbol{\delta}_{\parallel})\operatorname{ \mathbb{E}}\mathopen{}\mathclose{{}\left[{r_{f}(\boldsymbol{x},\boldsymbol{ \delta})\,\big{|}\,\boldsymbol{x}_{\parallel},y}}\right]}}\right]$ $\displaystyle\geq\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_ {\{\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq \varepsilon,\boldsymbol{\delta}_{\perp}=0\}}r_{y}(\boldsymbol{x}_{\parallel}, \boldsymbol{\delta}_{\parallel})^{2}+\operatorname{\mathbb{E}}\mathopen{} \mathclose{{}\left[{r_{f}(\boldsymbol{x},\boldsymbol{\delta})^{2}\,\big{|}\, \boldsymbol{x}_{\parallel},y}}\right]-2r_{y}(\boldsymbol{x}_{\parallel}, \boldsymbol{\delta}_{\parallel})\operatorname{\mathbb{E}}\mathopen{}\mathclose {{}\left[{r_{f}(\boldsymbol{x},\boldsymbol{\delta})\,\big{|}\,\boldsymbol{x}_{ \parallel},y}}\right]}}\right].$ $$

Since $y|\boldsymbol{x}_{\parallel}$ is independent from $\boldsymbol{x}_{\perp}$, for any fixed $\boldsymbol{\delta}$, we have $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{r_{f}(\boldsymbol{x},
\boldsymbol{\delta})\,|\,\boldsymbol{x}_{\parallel},y}}\right]=\operatorname{
\mathbb{E}}\mathopen{}\mathclose{{}\left[{r_{f}(\boldsymbol{x},\boldsymbol{
\delta})\,|\,\boldsymbol{x}_{\parallel}}}\right]$.
In addition, by using the notation $f(\boldsymbol{x})=f(\boldsymbol{x}_{\parallel},\boldsymbol{x}_{\perp})$, provided that $\boldsymbol{\delta}_{\perp}=0$,
Assumption 1 yields

$$ $\displaystyle h(\boldsymbol{z}+\boldsymbol{\delta}_{\parallel})=\operatorname{ \mathbb{E}}\mathopen{}\mathclose{{}\left[{f(\boldsymbol{x})\,|\,\boldsymbol{x} _{\parallel}=\boldsymbol{z}+\boldsymbol{\delta}_{\parallel}}}\right]= \operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{f(\boldsymbol{z}+ \boldsymbol{\delta}_{\parallel},\boldsymbol{x}_{\perp}+\boldsymbol{\delta}_{ \perp})}}\right]=\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{f( \boldsymbol{x}+\boldsymbol{\delta})\,|\,\boldsymbol{x}_{\parallel}=\boldsymbol {z}}}\right],$ $$

for all $\boldsymbol{z}\in\mathbb{R}^{k}$. Plugging in $\boldsymbol{z}=\boldsymbol{x}_{\parallel}$ gives $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{r_{f}(\boldsymbol{x},
\boldsymbol{\delta})\,|\,\boldsymbol{x}_{\parallel}}}\right]=0$.
Therefore,

$$ $\displaystyle\mathrm{AR}(f)$ $\displaystyle\geq\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_ {\{\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq \varepsilon,\boldsymbol{\delta}_{\perp}=0\}}r_{y}(\boldsymbol{x}_{\parallel}, \boldsymbol{\delta}_{\parallel})^{2}+\operatorname{\mathbb{E}}\mathopen{} \mathclose{{}\left[{r_{f}(\boldsymbol{x},\boldsymbol{\delta})^{2}\,|\, \boldsymbol{x}_{\parallel},y}}\right]}}\right]$ $\displaystyle\geq\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_ {\{\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq \varepsilon,\boldsymbol{\delta}_{\perp}=0\}}r_{y}(\boldsymbol{x}_{\parallel}, \boldsymbol{\delta}_{\parallel})^{2}}}\right]$ $\displaystyle=\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_{\{ \mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq\varepsilon, \boldsymbol{\delta}_{\perp}=0\}}(y-h(\boldsymbol{U}(\boldsymbol{x}+\boldsymbol {\delta})))^{2}}}\right]=\mathrm{AR}(h(\boldsymbol{U}\cdot)),$ $$

where we dropped the constraint $\boldsymbol{\delta}_{\perp}=0$ as it does not contribute. This concludes the proof.
∎

###### Assumption 1 .

###### Theorem 1 .

#### A discussion on robust/non-robust feature decomposition.

Many works on adversarial robustness in classification assume that features can be divided into robust and non-robust groups, with standard training relying on non-robust features and robust training using robust ones. This explains the performance gap between the two approaches (see e.g. [, , , ].) However, our focus is on a different phenomenon: dimensionality reduction. Unlike previous studies, we do not rely on this robust/non-robust decomposition. Instead, the $k$ relevant features for predicting $y$ can be either robust or non-robust. The robust training of the second layer ensures the model utilizes the robust subset of these $k$ features, if such a subset exists, while the first layer performs dimensionality reduction. Crucially, applying robust training to all layers in high-dimensional settings can fail to achieve dimensionality reduction, which may deteriorate the generalization performance in the setting we consider, as illustrated in Figure 1.

Before moving to the next section, we provide the following remark on proper scaling of $\varepsilon$.
Since $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{
{}\left\|{\boldsymbol{x}}}\right\|}}\right]$ grows with $\sqrt{d}$, it may seem natural to scale the adversary budget $\varepsilon$ with dimension as well. However, we provide a simple argument on the contrary.
Consider the single-index case $y=g(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{u}},{\boldsymbol{x}}}
\right\rangle)$, and let $h$ be the optimal function constructed in Theorem 1, providing the prediction function $\boldsymbol{x}\mapsto h(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{u}},{
\boldsymbol{x}}}\right\rangle)$. It can then be observed that even a constant order $\varepsilon$ can cause a significant change in the input of $h$, e.g., choosing $\boldsymbol{\delta}=\varepsilon\boldsymbol{u}$ perturbs the input of the predictor by $\varepsilon$. This justifies focusing on the regime where $\varepsilon$ is of constant order relative to the input dimension, which is the primary focus for the remainder of the paper

## 4 Learning Procedure and Guarantees

As outlined in the previous section, to robustly learn the target model, standard representations $\boldsymbol{U}$ suffice.
In this section, we present concrete examples demonstrating how combining a standard feature learning oracle with adversarially robust training in the second layer results in robust learning.
We assume access to the following *feature learning oracle* to recover $\boldsymbol{U}$. We will provide instances of practical implementations of this oracle using standard gradient-based algorithms in Section 4.2.

###### Definition 2 (DFL) .

An $\alpha$-Deterministic Feature Learner (DFL) is an oracle that for every $\zeta>0$, given $n_{\mathrm{DFL}}(\zeta)$ samples from $\mathcal{P}$, returns a weight matrix $\boldsymbol{W}=(\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{N})^{\top}\in\mathbb
{R}^{N\times d}$ such that for all $\boldsymbol{u}\in\mathrm{span}(\boldsymbol{u}_{1},\ldots,\boldsymbol{u}_{k})$ with $\mathopen{}\mathclose{{}\left\|{\boldsymbol{u}}}\right\|=1$, we have

$$ $\frac{\mathopen{}\mathclose{{}\left|{\{i:\mathopen{}\mathclose{{}\left\langle{ \boldsymbol{w}_{i}},{\boldsymbol{u}}}\right\rangle\geq 1-\zeta\}}}\right|}{N} \geq\alpha\zeta^{(k-1)/2}.$ $$

An $\alpha$-DFL oracle returns weights such that roughly an $\alpha$-proportion of them align with (and sufficiently cover) the target subspace.
By a packing argument, we can show that the best achievable ratio is $\alpha\leq c(k)$ for some constant $c(k)>0$ depending only on $k$, which is why we use the normalizing factor $\zeta^{(k-1)/2}$ above. We show in Section 4.2 that the definition above with a constant order $\alpha$ is attainable by standard gradient-based algorithms.
That said, in the multi-index setting, it is possible to improve our learning guarantees by considering the following stochastic oracle.

###### Definition 3 (SFL) .

An $(\alpha{,}\beta)$-Stochastic Feature Learner (SFL) is an oracle that for every $\zeta>0$, given $n_{\mathrm{SFL}}(\zeta)$ samples from $\mathcal{P}$, returns a random weight matrix $\boldsymbol{W}=(\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{N})^{\top}\in\mathbb
{R}^{N\times d}$, such that there exists $S\subseteq[N]$ with ${\mathopen{}\mathclose{{}\left|{S}}\right|}/{N}\geq\alpha$ satisfying $\mathopen{}\mathclose{{}\left\|{\boldsymbol{w}_{i}-\boldsymbol{U}^{\top}
\boldsymbol{U}\boldsymbol{w}_{i}}}\right\|^{2}\leq\zeta$ for $i\in S$ .
Further,
$\big{(}\!\frac{\boldsymbol{U}\boldsymbol{w}_{i}}{\mathopen{}\mathclose{{}\left
\|{\boldsymbol{U}\boldsymbol{w}_{i}}}\right\|}\!\big{)}_{i\in S}\!\!\!\!
\stackrel{{\scriptstyle\mathrm{i.i.d.}}}{{\sim}}\!\!\!\mu$,
and $\frac{\mathrm{d}\mu}{\mathrm{d}\tau_{k}}\geq\beta$,
where $\mu$ is some measure and $\tau_{k}$ is uniform, both supported on $\mathbb{S}^{k-1}$.

The above oracle essentially defines a random features model in the smaller target subspace, where a subset of the weights are sampled independently from a distribution that supports all target directions $\boldsymbol{U}$.
We note that an $(\alpha,\beta)$-SFL oracle can be used to directly implement an $\alpha$-DFL oracle; by a standard union bound argument, one can show $N=\tilde{\Theta}(1/(\alpha\beta\zeta^{(k-1)/2}))$ guarantees the output of $(\alpha,\beta)$-SFL satisfies Definition 2 with high probability.
Therefore, while its definition is slightly more involved, $(\alpha,\beta)$-SFL is a more specialized oracle compared to $\alpha$-DFL.

Once the first layer representation is provided by above oracles, we can fix the biases at some random initialization, and train the second layer weights $\boldsymbol{a}$ by minimizing the empirical adversarial risk

$$ $\widehat{\mathrm{AR}}(\boldsymbol{a},\boldsymbol{W},\boldsymbol{b})=\frac{1}{n _{\mathrm{FA}}}\sum_{i=1}^{n_{\mathrm{FA}}}\max_{\mathopen{}\mathclose{{}\left \|{\boldsymbol{\delta}^{(i)}}}\right\|\leq\varepsilon}(f(\boldsymbol{x}^{(i)}+ \boldsymbol{\delta}^{(i)};\boldsymbol{a},\boldsymbol{W},\boldsymbol{b})-y)^{2},$ (4.1) $$

where $n_{\mathrm{FA}}$ denotes the number of samples used in the function approximation phase. We formalize the training procedure with two-layer neural networks in Algorithm 1.

Figure: Algorithm 1 Adversarially robust learning with two-layer NNs.

We highlight that keeping biases at random initialization while only training the second layer $\boldsymbol{a}$ performs non-linear function approximation, and has been used in many prior works on feature learning [, , ]. Further, while $\boldsymbol{a}\mapsto\widehat{\mathrm{AR}}(\boldsymbol{a},\boldsymbol{W},
\boldsymbol{b})$ is a convex function for fixed $\boldsymbol{W}$ and $\boldsymbol{b}$ since it is a maximum over convex functions, exact training of $\boldsymbol{a}$ in practice may not be entirely straightforward since the inner maximization is not concave and does not admit a closed-form solution. In practice, some form of gradient descent ascent algorithm is typically used when training $\boldsymbol{a}$ []. In this work, we do not consider the computational aspect of solving this min-max problem, and leave that analysis as future work.

We will make the following standard tail assumptions on the data distribution.

###### Assumption 2 .

Suppose $\boldsymbol{x}$ has zero mean and $\mathcal{O}(1)$ subGaussian norm.
Furthermore, for all $r\geq 1$, it holds that $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{
{}\left|{y}}\right|^{r}}}\right]^{1/r}\leq\mathcal{O}(r^{p/2})$ for some constant $p\geq 1$.

Note that the condition on $y$ above is mild; for example, it holds for a noisy multi-index model $y=g(\boldsymbol{U}\boldsymbol{x})+\varsigma$, where $\varsigma$ has $\mathcal{O}(1)$ subGaussian norm and $g$ grows at most polynomially, i.e., $\mathopen{}\mathclose{{}\left|{g(\cdot)}}\right|\lesssim 1+|\cdot|^{p}$.
Similarly, we also keep the function class $\mathcal{F}$ quite general and
provide our first set of results for a class of pseudo-Lipschitz functions which is introduced below.

###### Assumption 3 .

We assume $\mathcal{F}$ is a class of functions that are pseudo-Lipschitz along the target coordinates. Specifically, using the notation $f(\boldsymbol{x})=f(\boldsymbol{x}_{\parallel},\boldsymbol{x}_{\perp})$ and defining $\varepsilon_{1}\coloneqq 1\lor\varepsilon$, we have

$$ $\mathopen{}\mathclose{{}\left|{f(\boldsymbol{z}_{1},\boldsymbol{x}_{\perp})-f( \boldsymbol{z}_{2},\boldsymbol{x}_{\perp})}}\right|\leq L(\boldsymbol{x}_{ \perp})\big{(}\varepsilon_{1}^{1-p}\mathopen{}\mathclose{{}\left\|{\boldsymbol {z}_{1}}}\right\|^{p-1}+\varepsilon_{1}^{1-p}\mathopen{}\mathclose{{}\left\|{ \boldsymbol{z}_{2}}}\right\|^{p-1}+1\big{)}\mathopen{}\mathclose{{}\left\|{ \boldsymbol{z}_{1}-\boldsymbol{z}_{2}}}\right\|$ $$

for all $f\in\mathcal{F}$, all $\boldsymbol{z}_{1},\boldsymbol{z}_{2}\in\mathbb{R}^{k}$, and some constants $L$ and $p\geq 1$ such that $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{L(\boldsymbol{x}_{
\perp})}}\right]\leq L$.

Remark.
The prefactor $\varepsilon_{1}^{1-p}$ is justified intuitively since the optimal function of the form $h(\boldsymbol{z})=\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{f(
\boldsymbol{x})\,|\,\boldsymbol{U}\boldsymbol{x}=\boldsymbol{z}}}\right]$ should satisfy $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_{\mathopen{}
\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq\varepsilon}(y-h(
\boldsymbol{U}(\boldsymbol{x}+\boldsymbol{\delta})))^{2}}}\right]=\mathrm{AR}^
{*}$, which is bounded, and
does not grow with $\varepsilon$ beyond a certain point.
This implies that $h$ must be sufficiently smooth while its input is perturbed, and in particular, its (local) Lipschitz constant should remain bounded while $\varepsilon$ grows. Therefore, we introduce the above prefactor to cancel the effect of $\mathopen{}\mathclose{{}\left\|{\boldsymbol{z}}}\right\|^{p-1}$ growing with $\varepsilon_{1}^{p-1}$ under adversarial attacks.

Later in Section 4.1, we focus on a subclass of predictors that are polynomials of a fixed degree $p$ to achieve refined results. The first result of this section assumes access to $\alpha\operatorname{-DFL}$ oracle.

###### Theorem 4 .

Suppose Assumptions 1,2,3 hold and ReLU activation is used. For a tolerance $\epsilon>0$ define $\tilde{\epsilon}\coloneqq\epsilon\land(\epsilon^{2}/\mathrm{AR}^{*})$, and for the adversary budget $\varepsilon$ recall $\varepsilon_{1}\coloneqq 1\lor\varepsilon$. Consider Algorithm 1 with $\text{{FL}}=\alpha\operatorname{-DFL}$ oracle, $r_{a}=\tilde{\mathcal{O}}\big{(}(\varepsilon_{1}/\sqrt{\tilde{\epsilon}})^{k+1
+1/k}/\alpha\big{)}$ and $r_{b}=\tilde{\mathcal{O}}\big{(}\varepsilon_{1}(\varepsilon_{1}/\sqrt{\tilde{
\epsilon}})^{1+1/k}\big{)}$. Then, if the number of second phase samples $n_{\mathrm{FA}}$, the number of neurons $N$, and $\alpha\operatorname{-DFL}$ error $\zeta$ satisfy

$$ $\displaystyle n_{\mathrm{FA}}\geq\tilde{\Omega}\Bigg{(}\frac{\varepsilon_{1}^{ 4}}{\alpha^{4}\epsilon^{2}}\bigg{(}\frac{\varepsilon_{1}}{\sqrt{\tilde{ \epsilon}}}\bigg{)}^{\mathcal{O}(k)}\Bigg{)},$ $\displaystyle N\geq\tilde{\Omega}\Bigg{(}\frac{1}{\alpha\zeta^{(k-1)/2}}\bigg{ (}\frac{\varepsilon_{1}}{\sqrt{\tilde{\epsilon}}}\bigg{)}^{\mathcal{O}(k)} \Bigg{)},$ $\displaystyle\zeta\leq\tilde{\mathcal{O}}\Bigg{(}\bigg{(}\frac{\tilde{\epsilon }}{\sqrt{\varepsilon_{1}}}\bigg{)}^{\mathcal{O}(k)}\Bigg{)},$ $$

we have $\mathrm{AR}(\boldsymbol{\hat{a}},\boldsymbol{W},\boldsymbol{b})\leq\mathrm{AR}
^{*}+\epsilon$ with probability at least $1-n_{\mathrm{FA}}^{-c}$ where $c$ is an absolute constant.

Remark.
The total sample complexity
of Algorithm 1 is given by the sum of complexities of
the feature learning oracle $n_{\mathrm{DFL}}(\zeta)$ and the function approximation $n_{\mathrm{FA}}$, i.e., $n_{\mathrm{total}}=n_{\mathrm{FA}}+n_{\mathrm{DFL}}(\zeta)$.
We will provides bounds on $n_{\mathrm{DFL}}(\zeta)$ in Propositions 8 and 10 to ultimately characterize $n_{\mathrm{total}}$ in Corollaries 9 and 11.

The above theorem states that once the feature learning oracle has recovered the target subspace, the number of samples and neurons needed for robust learning is independent of the ambient dimension $d$. Thus, in a high-dimensional setting, statistical complexity is dominated by the feature learning oracle, implying that adversarially robust learning is statistically as easy as standard learning.

Arguing about computational complexity is more involved. While the number of neurons required is independent of $d$, in its naive implementation, Phase 2 of Algorithm 1 needs to solve inner maximization problems over $\mathbb{R}^{d}$, which may be costly.
However, suppose that at the end of Phase 1 we know that all weights live in $\mathrm{span}(\boldsymbol{u}_{1},\ldots,\boldsymbol{u}_{k})$, implying  $\boldsymbol{w}_{j}\approx\boldsymbol{U}^{\top}\boldsymbol{U}\boldsymbol{w}_{j}$ for all $j\in[N]$. We can then directly estimate this subspace, e.g. via principal component analysis, and then project $\boldsymbol{x}$ onto this subspace since

$$ $\sum_{j=1}^{N}a_{j}\sigma(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}_ {j}},{\boldsymbol{x}}}\right\rangle+b_{j})\approx\sum_{j=1}^{N}a_{j}\sigma( \mathopen{}\mathclose{{}\left\langle{\boldsymbol{U}\boldsymbol{w}_{j}},{ \boldsymbol{U}\boldsymbol{x}}}\right\rangle+b_{j}).$ $$

With this modification, we only need to consider worst-case perturbations over $\mathbb{R}^{k}$, thus the computational complexity of Phase 2 will also be independent of the ambient dimension $d$.
Note that all weights aligning with $\mathrm{span}(\boldsymbol{u}_{1},\ldots,\boldsymbol{u}_{k})$ is stronger than the requirements in Definition 2 or 3. However, it can still be satisfied in standard settings, see Appendix A.

It is possible to remove the dependence on $\zeta$ in the number of neurons by instead assuming access to an $(\alpha{,}\beta)\operatorname{\!-SFL}$ oracle, as outlined below.

###### Theorem 5 .

Consider the same setting as Theorem 4, except that we use the $(\alpha{,}\beta)\operatorname{\!-SFL}$ oracle in Algorithm 1 with $r_{a}=\tilde{\mathcal{O}}\big{(}(\varepsilon_{1}/\sqrt{\tilde{\epsilon}})^{k+1
+1/k}/(\alpha\beta)\big{)}$. Then,
the sufficient number of second phase samples $n_{\mathrm{FA}}$, neurons $N$, and oracle error $\zeta$ are given as

$$ $\displaystyle n_{\mathrm{FA}}\geq\tilde{\Omega}\Bigg{(}\frac{\varepsilon_{1}^{ 4}}{\alpha^{4}\beta^{4}\epsilon^{2}}\bigg{(}\frac{\varepsilon_{1}}{\sqrt{ \tilde{\epsilon}}}\bigg{)}^{\mathcal{O}(k)}\Bigg{)},\quad N\geq\tilde{\Omega} \Bigg{(}\frac{\varepsilon_{1}^{4}}{\alpha\beta^{2}}\bigg{(}\frac{\varepsilon_{ 1}}{\sqrt{\tilde{\epsilon}}}\bigg{)}^{\mathcal{O}(k)}\Bigg{)},\quad\zeta\leq \tilde{\mathcal{O}}\Bigg{(}\beta^{2}\bigg{(}\frac{\tilde{\epsilon}}{\sqrt{ \varepsilon_{1}}}\bigg{)}^{\mathcal{O}(k)}\Bigg{)}$ $$

Under a Gaussian input assumption, there exist $\alpha\operatorname{-DFL}$ and $(\alpha{,}\beta)\operatorname{\!-SFL}$ oracles
that rely only on standard gradient-based training such that for a small constant $\zeta$,
$n_{\mathrm{DFL}}(\zeta)$ and $n_{\mathrm{SFL}}(\zeta)$ both scale with some polynomial of $d$, where the exponent depends on certain properties of the link function, termed as the *information or generative exponent* [, ].
We will provide explicit examples of such algorithms in Section 4.2 to characterize the total sample complexity $n_{\mathrm{total}}=n_{\mathrm{FA}}+n_{\mathrm{DFL}/\mathrm{SFL}}$.
For the interested reader, we restate Theorems 4 and 5 in Appendix B.1 with explicit exponents.

###### Definition 2 (DFL) .

###### Definition 3 (SFL) .

###### Assumption 2 .

###### Assumption 3 .

###### Theorem 4 .

###### Theorem 5 .

### 4.1 Competing against the Optimal Polynomial Predictor

In this section, we restrict $\mathcal{F}$ to only polynomials, which allows us to derive more refined bounds on the number of samples and neurons. Specifically, we make the following assumption.

###### Assumption 4 .

Suppose $\mathcal{F}$ is the class of $d$-variate polynomials of degree $p$ for some constant $p>0$. Further, $\sigma$ is either a polynomial of degree $q\geq p$, or the ReLU activation for which we define $q=(p-1)\lor 1$.

While the ReLU activation is sufficient for function approximation, we also consider polynomial activations in Assumption 4 since using those, recent works have been able to achieve sharper theoretical guarantees of recovering the target directions [];
we provide a more detailed discussion in Section 4.2.
Note that a priori we do not require a growth constraint on the coefficients of the polynomials in $\mathcal{F}$. The optimal function $h$ in Theorem 1 automatically chooses a polynomial with suitably bounded coefficients in order to avoid incurring a large robust risk.

The following result establishes the sample and computational complexity for competing against polynomial predictors when having access to $\alpha\operatorname{-DFL}$ oracle.

###### Theorem 6 .

Suppose Assumptions 1,2,4 hold. For a tolerance $\epsilon>0$ define $\tilde{\epsilon}\coloneqq\epsilon\land(\epsilon^{2}/\mathrm{AR}^{*})$, and for the adversary budget $\varepsilon$ recall $\varepsilon_{1}\coloneqq 1\lor\varepsilon$. Consider Algorithm 1 with $\alpha\operatorname{-DFL}$ oracle, $r_{a}=\tilde{\mathcal{O}}(1)$, $r_{b}=\tilde{\mathcal{O}}(\varepsilon_{1})$. If the number of second phase samples $n_{\mathrm{FA}}$, neurons $N$, and $\alpha\operatorname{-DFL}$ error $\zeta$ satisfy

$$ $\displaystyle n_{\mathrm{FA}}\geq\tilde{\Omega}\bigg{(}\frac{\varepsilon_{1}^{ 4(q+1)}}{\alpha^{4}\epsilon^{2}}\bigg{)},\quad N\geq\tilde{\Omega}\Bigg{(} \frac{\varepsilon_{1}^{q+1}}{\alpha\zeta^{\frac{k-1}{2}}\sqrt{\tilde{\epsilon} }}\Bigg{)},\quad\zeta\leq\tilde{\mathcal{O}}\Bigg{(}\frac{\tilde{\epsilon}}{ \varepsilon_{1}^{2(q+1)}}\Bigg{)},$ $$

we have $\mathrm{AR}(\boldsymbol{\hat{a}},\boldsymbol{W},\boldsymbol{b})\leq\mathrm{AR}
^{*}+\epsilon$ with probability at least $1-n_{\mathrm{FA}}^{-c}$ where $c$ is an absolute constant.

Consequently, when restricting $\mathcal{F}$ to the class of fixed degree polynomials, there is no curse of dimensionality for sample complexity, even in the latent dimension $k$. This is consistent with the standard learning setting, see e.g. []. Further, similar to the general case above, it is possible to remove the $\zeta$ dependence from $N$ when having access to an SFL oracle, thus also achieving computational complexity as a fixed polynomial independent of the latent dimension.

###### Theorem 7 .

In the setting of Theorem 6, consider using Algorithm 1 with an $(\alpha{,}\beta)\operatorname{\!-SFL}$ oracle. Then, the sufficient number of second phase samples, neurons, and oracle error are given as

$$ $\displaystyle n_{\mathrm{FA}}\geq\tilde{\Omega}\Bigg{(}\frac{\varepsilon_{1}^{ 4(q+1)}}{\alpha^{4}\beta^{4}\epsilon^{2}}\Bigg{)},\quad N\geq\tilde{\Omega} \Bigg{(}\frac{\varepsilon_{1}^{2(q+1)}}{\alpha\beta^{2}\tilde{\epsilon}}\Bigg{ )},\quad\zeta\leq\tilde{\mathcal{O}}\Bigg{(}\frac{\beta^{2}\tilde{\epsilon}}{ \varepsilon_{1}^{2(q+1)}}\Bigg{)}.$ $$

We remark that the guarantees provided in Theorem 7 are generally better than those in Theorem 6 for large $k$; yet, they are strictly worse for $k=1$.
That said, both Theorems 7 and 6 respectively achieve better sample complexity guarantees compared to their counterparts in the previous section,
namely Theorems 4 and 5, simply by restricting the function class $\mathcal{F}$ to polynomials.

###### Assumption 4 .

###### Theorem 6 .

###### Theorem 7 .

### 4.2 Oracle Implementations for Feature Learning

The task of recovering the target directions $\boldsymbol{U}$ is classical in statistics, and is known as sufficient dimension reduction [, ], with many dedicated algorithms, see e.g. [, , , ] to name a few. Here, we focus on algorithms based on neural networks and iterative gradient-based optimization.

While we only consider the case where $\boldsymbol{x}$ is an isotropic Gaussian random vector, recovering the hidden direction has also been considered for non-isotropic Gaussians [, ] where the additional anisotropic structure in the inputs can provide further statistical benefits, or non-Gaussian spherically symmetric distributions []. Our results readily extend to these settings as well.
First, we present the case of single-index polynomials.

###### Proposition 8 ( [ 37 ] ) .

Suppose $\boldsymbol{x}\sim\mathcal{N}(0,\mathbf{I}_{d})$, $k=1$, and $g$ is a polynomial of degree $p$ where $p$ is constant. Then, there exists an iterative first-order algorithm on two-layer neural networks *(see Algorithm 2)* that implements an $(\alpha{,}\beta)\operatorname{\!-SFL}$ oracle and an $\alpha\operatorname{-DFL}$ oracle, where $\alpha=\tilde{\Theta}(1)$ and $\beta=1$. Furthermore, we have $n_{\mathrm{SFL}}(\zeta)=n_{\mathrm{DFL}}(\zeta)=\tilde{\mathcal{O}}(d/\zeta^{2})$.

Combined with Theorems 4-7, we obtain the following total sample complexity guarantee for robustly learning Gaussian single-index models.

###### Corollary 9 .

Consider the data model of Proposition 8, and assume that the adversary budget is $\varepsilon=\mathcal{O}(1)$. Then, the total sample complexity of Algorithm 1 to achieve optimal adversarial risk $\mathrm{AR}^{*}$ with a tolerance $\epsilon$ using either $\alpha\operatorname{-DFL}$ or $(\alpha{,}\beta)\operatorname{\!-SFL}$ oracle in Proposition 8 is given as

- •
$n_{\mathrm{total}}=\tilde{\mathcal{O}}(d/\tilde{\epsilon}^{2})$ when choosing $\mathcal{F}$ to be polynomials of fixed degree as in Assumption 4,
- •
$n_{\mathrm{total}}=\tilde{\mathcal{O}}(d/\tilde{\epsilon}^{\mathcal{O}(1)})$ when choosing $\mathcal{F}$ to be pseudo-Lipschitz functions as in Assumption 3,

where we recall $\tilde{\epsilon}\coloneqq\epsilon\land({\epsilon^{2}}/{\mathrm{AR}^{*}})$.

When considering Gaussian single-index models beyond polynomials, we must introduce the concepts of *information* and *generative exponent* to characterize the sample complexity of recovering the target direction. Let $\gamma=\mathcal{N}(0,1)$, and for any $g:\mathbb{R}\to\mathbb{R}$ in $L^{2}(\gamma)$ (the space of square-integrable functions), let $g=\sum_{j\geq 0}\alpha_{j}\mathrm{He}_{j}$ denote its Hermite expansion, where $\mathrm{He}_{j}$ is the normalized Hermite polynomial of degree $j$. The information exponent of $g$ is defined as $s(g)\coloneqq\min\{j>0:\alpha_{j}\neq 0\}$. The generative exponent on the other hand, is defined as the minimum information exponent attainable by any transformation of $g$, i.e. $s^{*}(g)\coloneqq\min_{\mathcal{T}}s(\mathcal{T}(g))$, where the minimum is over all $\mathcal{T}\in L^{2}(g\#\gamma)$. Thus, $s^{*}(g)\leq s(g)$, and in particular, $s^{*}=1$ for all polynomials. See [, ]
for details.

There exists an algorithm based on estimating partial traces that implements a $1$-DFL (or a $(1,1)$-SFL) oracle with $n_{\mathrm{DFL}}(\zeta)=\mathcal{O}(d^{s^{*}/2}+d/\zeta^{2})$ []. While it may be possible to achieve a similar sample complexity when training neural networks with a ReLU activation, the state of the art results for ReLU neural networks so far are only able to control the sample complexity with the information exponent $s$, e.g. [] provides a gradient-based algorithm for optimizing a variant of a two-layer ReLU network that implements $1$-DFL with $n_{\mathrm{DFL}}=\mathcal{O}(d^{s}\operatorname{poly}(\zeta^{-1}))$.

Recovering $\boldsymbol{U}$ with $k>1$ is more challenging, and the general picture is that the directions in $\boldsymbol{U}$ are recovered hierarhically based on each direction’s corresponding complexity, such as in []. For simplicity, we look at a case that is sufficiently simple for all directions to be learned simultaneously, while emphasizing that in principle any guarantee for learning the subspace $\boldsymbol{U}$ can be turned into an implementation of the oracles introduced in the previous section.

###### Proposition 10 ( [ 20 ] ) .

Suppose $\boldsymbol{x}\sim\mathcal{N}(0,\mathbf{I}_{d})$, $g$ is a polynomial of degree $p$, and $p$,$k$ are constant. Further assume $\frac{\sigma_{\mathrm{max}}(\nabla^{2}g)}{\sigma_{\mathrm{min}}(\nabla^{2}g)}\geq\kappa$ for some $\kappa>0$, where $\sigma_{\mathrm{min}}$ and $\sigma_{\mathrm{max}}$ denote the minimum and maximum singular values, respectively. Then, there exists a first-order algorithm on two-layer ReLU neural networks *(see Algorithm 3)* that implements an $(\alpha{,}\beta)\operatorname{\!-SFL}$ and an $\alpha\operatorname{-DFL}$ oracle, where $\alpha=1$ and $\beta\geq c_{\kappa}$ for some constant $c_{\kappa}>0$ depending only $\kappa$. Further, we have $n_{\mathrm{SFL}}(\zeta)=n_{\mathrm{DFL}}(\zeta)=\tilde{\mathcal{O}}(d^{2}+d/
\zeta^{2})$.

Combining the above proposition with Theorems 4-7, we obtain the following total sample complexity for robustly learning Gaussian multi-index models.

###### Corollary 11 .

Under the data model of Proposition 10, assume that the adversary budget is $\varepsilon=\mathcal{O}(1)$. Then, the total sample complexity of Algorithm 1 to achieve optimal adversarial risk $\mathrm{AR}^{*}$ with a tolerance $\epsilon$ using either $\alpha\operatorname{-DFL}$ or $(\alpha{,}\beta)\operatorname{\!-SFL}$ oracle in Proposition 10 is given as

- •
$n_{\mathrm{total}}=\tilde{\mathcal{O}}(d^{2}+d/\tilde{\epsilon}^{2})$ when choosing $\mathcal{F}$ to be polynomials of fixed degree as in Assumption 4,
- •
$n_{\mathrm{total}}=\tilde{\mathcal{O}}(d^{2}+d/\tilde{\epsilon}^{\mathcal{O}(k
)})$ when choosing $\mathcal{F}$ to be pseudo-Lipschitz functions as in Assumption 3,

where we recall $\tilde{\epsilon}\coloneqq\epsilon\land({\epsilon^{2}}/{\mathrm{AR}^{*}})$.

Remark.
We highlight that the gap in the total sample complexity of Corollary 9 and Corollary 11 is due to more efficient guarantees for recovering the hidden direction for single-index polynomials. It is an open question whether such efficient recovery is also possible for multi-index polynomials.

###### Proposition 8 ( [ 37 ] ) .

###### Corollary 9 .

###### Proposition 10 ( [ 20 ] ) .

###### Corollary 11 .

## 5 Numerical Experiments

Figure: Figure 1: The adversarial test error of a two-layer ReLU network as a function of the number of adversarial training iterations, where each iteration is performed on a batch of independent 300 samples, except 500 samples for He2 with unknown direction to reduce variance. Full AD training performs adversarial training on all layers from random initialization. SD training is standard training, which provides a better initialization for $W$ before performing adversarial training. We use the adversary budget $\varepsilon=1$ for all experiments, each of which are averaged over three runs.
Refer to caption: x1.png

As a proof of concept, we also provide small-scale numerical studies to support intuitions derived from our theory(^1^11The code to reproduce the results is provided at: [https://github.com/mousavih/robust-feature-learning](https://github.com/mousavih/robust-feature-learning)). We consider a single-index setting, where the teacher non-linearity is given by either ReLU, tanh, or $\mathrm{He2}(z)=(z^{2}-1)/\sqrt{2}$ which is the normalized second Hermite polynomial.
The student network has $N=100$ neurons, and the input is sampled from $\boldsymbol{x}\sim\mathcal{N}(0,\mathbf{I}_{d})$ with $d=100$. We implement adversarial training in the following manner.
At each iteration, we sample a new batch of i.i.d. training examples. We estimate the adversarial perturbations on this batch by performing 5 steps of signed projected gradient ascent, with a stepsize of $0.1$.
We then perform a gradient descent step on the perturbed batch. To estimate the robust test risk, we fix a test set of $10{,}000$ i.i.d. samples, and use $20$ iterations to estimate the adversarial perturbation.
Because of the online nature of the algorithm, the total number of samples used is the batch size times the number of iterations taken.

The first row of Figure 1 compares the performance of three different approaches. Full AD training refers to adversarially training all layers from random initialization, where first layer weights are initialized uniformly on the sphere $\mathbb{S}^{d-1}\!$, second layer weights are initialized i.i.d. from $\mathcal{N}(0,1/N^{2})$, and biases are initialized i.i.d. from $\mathcal{N}(0,1)$. In the two other approaches, we initialize all first layer weights to the target direction $\boldsymbol{u}$. In one approach we fix this direction and do not train it, while in the other, we allow the training of first layer weights from this initialization. As can be seen from Figure 1, there is a considerable improvement in initializing from $\boldsymbol{u}$, which is consistent with our theory that this direction provides a Bayes optimal projection for robust learning.

In the practical setting where we do not have the knowledge of $\boldsymbol{u}$, we consider the following alternative. We first perform standard training on the network, i.e. assume $\varepsilon=0$ (denoted in Figure 1 by SD training). We can then either fix the first layer weights to these directions, or further train them adversarially from this initialization. Note that for a fair comparison with the full AD method, we provide the same random bias and second layer weight initializations across all methods at the beginning of the adversarial training stage. Even though this approach is not perfect at estimating the unknown direction, it still provides a considerable benefit over adversarially training all layers from random initialization, as demonstrated in the second row of Figure 1.

## 6 Conclusion

In this paper, we initiated a theoretical study of the role of feature learning in adversarial robustness of neural networks. Under $\ell_{2}$-constrained perturbations, we proved that projecting onto the latent subspace of a multi-index model is sufficient for achieving Bayes optimal adversarial risk with respect to the squared loss, provided that the index directions are statistically independent from the rest of the directions in the input space. Remarkably, this subspace can be estimated through standard feature learning with neural networks, thus turning a high-dimensional robust learning problem into a low-dimensional one. As a result, under the assumption of having access to a feature learning oracle which returns an estimate of this subspace, and can be implemented e.g. by training the first-layer of a two-layer neural network, we proved that robust learning of multi-index models is possible with a number of (additional) samples and neurons independent from the ambient dimension.

We conclude by mentioning several open questions that arise from this work.

- •
Stronger notions of adversarial attacks such as $\ell_{\infty}$-norm constraints have been widely considered in empirical works. It remains open to understand optimal low-dimensional representations under such perturbations as well as their implications on sample complexity.
- •
While our work demonstrates that standard training is sufficient for the first layer, it is unclear what kind of representation is learned when all layers are trained adversarially. In particular, Figure 1 suggests that adversarial training of the first layer may be suboptimal in this setting, even when infinitely many samples are available during training.
- •
Since our main motivation was to show independence from input dimension, the dependence of our bounds on the final robust test risk suboptimality $\epsilon$ are potentially improvable by a more careful analysis. It is an interesting direction to obtain a sharper dependency and investigate the optimality of such dependence on the tolerance $\epsilon$.

Finally, it is worth emphasizing that our theorems can be easily adapted to other standard feature learning oracles.
As such, based on the training procedure used and its complexity in feature learning, our results are amenable to further improvements in their total sample complexity.

## Acknowledgments

AJ was partially supported by the Sloan fellowship in mathematics, the NSF CAREER Award
DMS-1844481, the NSF Award DMS-2311024, an Amazon Faculty Research Award, an Adobe Faculty Research Award and an iORB grant form USC Marshall School of Business.
MAE was partially supported by the NSERC Grant [2019-06167], the CIFAR AI Chairs program, and the CIFAR Catalyst grant.

## Appendix A Gradient-Based Neural Feature Learning Algorithms

In this section, we will provide examples of implementations of the feature learner oracles introduced in Section 4 using gradient-based training of two-layer neural networks. First, we look at the algorithm provided by [], which we restate here as Algorithm 2, for the case where $g$ is a polynomial of degree $p$. Consider the following two-layer neural network with zero bias

$$ $f(\boldsymbol{x};\boldsymbol{a},\boldsymbol{W})=\sum_{j=1}^{N}a_{j}\sigma_{j}( \mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}_{j}},{\boldsymbol{x}}} \right\rangle).$ $$

Note that we allow the activation to vary based on neuron. Specifically, we let $\sigma_{j}=\sum_{l=1}^{q}\beta_{j,l}\mathrm{He}_{l}$, where $\mathrm{He}_{j}$ is the $j$th normalized Hermite polynomial, $\beta_{j,l}\stackrel{{\scriptstyle\mathrm{i.i.d.}}}{{\sim}}\textnormal{Unif}(
\{\pm r_{l}\})$ for appropriately chosen $r_{l}$, and $q\geq C_{p}$, see [, Lemma 3] for details. Now, we consider the following algorithm.

Figure: Algorithm 2 Gradient-Based Feature Learner for Single-Index Polynomials [, Algorithm 1, Phase I].

Note that $\nabla^{S}f(\boldsymbol{w})=(\mathbf{I}-\boldsymbol{w}\boldsymbol{w}^{\top})
\nabla f(\boldsymbol{w})$ denotes the spherical gradient. Essentially, Algorithm 2 takes two gradient steps on each new sample, and in the even iterations performs a certain interpolation. Proper choice of hyperparameters in the above algorithm leads to Proposition 8.

Next, we consider the algorithm of [], which we restate here as Algorithm 3, for the case where $g$ is a multi-index polynomial.

Figure: Algorithm 3 Gradient-Based Feature Learner for Multi-Index Polynomials [, Algorithm 1, Adapted]

After performing a preprocessing on data, Algorithm 3 essentially performs one gradient descent step with weight decay, when the regularizer of the weight decay is the inverse of step size, thus cancelling out initialization and leaving only gradient as the estimate. [] prove that, with a sample complexity of $n_{\mathrm{FL}}=\tilde{\mathcal{O}}(d^{2}+d/\zeta^{2})$, the output of Algorithm 3 satisfies

$$ $\mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}_{i}},{\frac{\boldsymbol{U} ^{\top}\boldsymbol{H}\boldsymbol{U}\boldsymbol{w}^{0}_{i}}{\mathopen{} \mathclose{{}\left\|{\boldsymbol{U}^{\top}\boldsymbol{H}\boldsymbol{U} \boldsymbol{w}^{0}_{i}}}\right\|}}}\right\rangle\geq 1-\zeta,\quad\,\forall i \in[N],$ $$

witi high probability, where $\boldsymbol{H}=\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\nabla^
{2}g(\boldsymbol{U}\boldsymbol{x})}}\right]$. Thus, for a full-rank $\boldsymbol{H}$, the output of Algorithm 3 satisfies the definition of a $(1,\beta)\mathrm{SFL}$ oracle for a constant $\beta>0$ depending only on the conditioning of $H$ and the number of indices $k$.

## Appendix B Additional Notations and Details of Section 4

Throughout the appendix, we will assume the activation satisfies $\sigma(0)=0$ for simplicity of presentation, without loss of generality. We will also assume that

$$ $\mathopen{}\mathclose{{}\left|{\sigma(z_{1})-\sigma(z_{2})}}\right|\leq L_{ \sigma}(\mathopen{}\mathclose{{}\left|{z_{1}}}\right|^{\bar{q}-1}+\mathopen{} \mathclose{{}\left|{z_{2}}}\right|^{\bar{q}-1}+1)\mathopen{}\mathclose{{}\left |{z_{1}-z_{2}}}\right|,$ (B.1) $$

for all $z_{1},z_{2}\in\mathbb{R}$ and some absolute constant $L_{\sigma}$. In the case of ReLU, we have $\bar{q}=1$ and $L_{\sigma}=1$. For polynomial activations, $\bar{q}$ is the same as the degree of the polynomial. For a set of parameters $\psi$ (e.g. $\psi=q,k$), we will use $C_{\psi}$ to denote a generic constant whose value depends only on $\psi$ and may change from line to line.

### B.1 Complete Versions of Theorems in Section 4

We first restate Theorem 4 with explicit exponents.

###### Theorem 12 .

Suppose Assumptions 1,2, and 3 hold. For any $\epsilon>0$, define $\tilde{\epsilon}\coloneqq\epsilon\land(\epsilon^{2}/\mathrm{AR}^{*})$, and recall $\varepsilon_{1}\coloneq 1\lor\varepsilon$. Consider Algorithm 1 with the $\alpha\operatorname{-DFL}$ oracle, $r_{a}=\tilde{\mathcal{O}}\big{(}(\varepsilon_{1}/\sqrt{\tilde{\epsilon}})^{k+1
+1/k}/\alpha\big{)}$, and $r_{b}=\tilde{\mathcal{O}}\big{(}\varepsilon_{1}(\varepsilon_{1}/\sqrt{\tilde{
\epsilon}})^{1+1/k}\big{)}$. Then, if the number of second phase samples $n_{\mathrm{FA}}$, number of neurons $N$, and $\alpha\operatorname{-DFL}$ error $\zeta$ satisfy

$$ $\displaystyle n_{\mathrm{FA}}\geq\tilde{\Omega}\Big{(}\frac{\varepsilon_{1}^{4 }}{\alpha^{4}\epsilon^{2}}\big{(}\frac{\varepsilon_{1}^{2}}{\tilde{\epsilon}} \big{)}^{2k+4+4/k}\Big{)},$ $\displaystyle N\geq\tilde{\Omega}\Big{(}\frac{1}{\alpha\zeta^{(k-1)/2}}\big{(} \frac{\varepsilon_{1}}{\sqrt{\tilde{\epsilon}}}\big{)}^{k+3+2/k}\Big{)},$ $\displaystyle\zeta\leq\tilde{\mathcal{O}}\Big{(}\big{(}\frac{\tilde{\epsilon}} {\varepsilon_{1}^{2}}\big{)}^{k+2+1/k}\Big{)},$ $$

we have $\mathrm{AR}(\boldsymbol{\hat{a}},\boldsymbol{W},\boldsymbol{b})\leq\mathrm{AR}
^{*}+\epsilon$ with probability at least $1-n_{\mathrm{FA}}^{-c}$ where $c>0$ is an absolute constant. The total sample complexity of Algorithm 1 is given by $n_{\mathrm{total}}=n_{\mathrm{FA}}+n_{\mathrm{DFL}}(\zeta)$.

Similarly, we can restate Theorem 5 with explicit exponents.

###### Theorem 13 .

Consider the same setting as Theorem 12, except that we use the $(\alpha{,}\beta)\operatorname{\!-SFL}$ oracle in Algorithm 1 with $r_{a}=\tilde{\mathcal{O}}\big{(}(\varepsilon_{1}/\sqrt{\tilde{\epsilon}})^{k+1
+1/k}/(\alpha\beta)\big{)}$. Then, if the number of second phase samples $n_{\mathrm{FA}}$, number of neurons $N$, and $\alpha\operatorname{-DFL}$ error $\zeta$ satisfy

$$ $\displaystyle n_{\mathrm{FA}}\geq\tilde{\Omega}\Big{(}\frac{\varepsilon_{1}^{4 }}{\alpha^{4}\beta^{4}\epsilon^{2}}\big{(}\frac{\varepsilon_{1}^{2}}{\tilde{ \epsilon}}\big{)}^{2k+4+4/k}\Big{)},$ $\displaystyle N\geq\tilde{\Omega}\Big{(}\frac{1}{\alpha\beta^{2}}\big{(}\frac{ \varepsilon_{1}^{2}}{\tilde{\epsilon}}\big{)}^{k+3+2/k}\Big{)},$ $\displaystyle\zeta\leq\tilde{\mathcal{O}}\Big{(}\beta^{2}\big{(}\frac{\tilde{ \epsilon}}{\varepsilon_{1}^{2}}\big{)}^{k+2+1/k}\Big{)}.$ $$

The total sample complexity in this case is given by $n_{\mathrm{total}}=n_{\mathrm{FA}}+n_{\mathrm{SFL}}(\zeta)$.

The proof of both theorems follows from combining the results of the following sections. Since both proofs are similar, we only present the proof of Theorem 12. The proof of Theorems 6 and 7 can be obtained in a similar manner.

Proof. [Proof of Theorem 12]
The proof is based on decomposing the suboptimality into generalization and approximation terms, namely

$$ $\mathrm{AR}(\boldsymbol{\hat{a}},\boldsymbol{W},\boldsymbol{b})-\mathrm{AR}^{* }=\mathrm{AR}(\boldsymbol{\hat{a}},\boldsymbol{W},\boldsymbol{b})-\mathrm{AR}( \boldsymbol{a}^{*},\boldsymbol{W},\boldsymbol{b})+\mathrm{AR}(\boldsymbol{a}^{ *},\boldsymbol{W},\boldsymbol{b})-\mathrm{AR}^{*},$ $$

where $\boldsymbol{a}^{*}\coloneqq\min_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{a
}}}\right\|\leq r_{a}/\sqrt{N}}\mathrm{AR}(\boldsymbol{a},\boldsymbol{W},
\boldsymbol{b})$, thus we can see the first term above as generalization error, and the second term as approximation error.

From Proposition 22, we have $\mathrm{AR}(\boldsymbol{\hat{a}},\boldsymbol{W},\boldsymbol{b})-\mathrm{AR}(
\boldsymbol{a}^{*},\boldsymbol{W},\boldsymbol{b})\leq\epsilon/2$ as soon as $n\geq\tilde{\Omega}(r_{a}^{4}(\varepsilon_{1}^{4}+r_{b}^{4})/\epsilon^{2})$ (recall that $q=1$ here, since we are considering the ReLU activation).
For the approximation error, we can use Proposition 36, which guarantees there exists $\boldsymbol{a}^{*}$ with $\mathopen{}\mathclose{{}\left\|{\boldsymbol{a}^{*}}}\right\|\leq r_{a}/\sqrt{N}$ such that
$\mathrm{AR}(\boldsymbol{a}^{*},\boldsymbol{W},\boldsymbol{b})-\mathrm{AR}^{*}
\leq\epsilon/2$ with $r_{a}\leq\tilde{\mathcal{O}}((\varepsilon_{1}/\sqrt{\tilde{\epsilon}})^{k+1+1/
k}/\alpha)$, as soon as

$$ $\displaystyle\zeta\leq\tilde{\mathcal{O}}\Big{(}\big{(}\frac{\tilde{\epsilon}} {\varepsilon_{1}^{2}}\big{)}^{k+2+1/k}\Big{)},$ $\displaystyle\mathrm{and}$ $\displaystyle N\geq\tilde{\Omega}\Big{(}\frac{1}{\zeta^{(k-1)/2}\alpha}\big{(} \frac{\varepsilon_{1}}{\sqrt{\tilde{\epsilon}}}\big{)}^{k+3+2/k}\Big{)},$ $$

provided that we choose $r_{b}=\tilde{\Theta}(\varepsilon_{1}(\varepsilon_{1}/\sqrt{\tilde{\epsilon}})^
{1+1/k})$. Plugging the value of $r_{a}$ and $r_{b}$ in the bound for $n$ completes the proof.
∎

###### Theorem 12 .

###### Theorem 13 .

## Appendix C Generalization Analysis

We will first focus on proving a generalization bound for bounded and Lipschitz losses, and then extend the results to cover the squared loss. In this section, we will typically use $n$ to refer to $n_{\mathrm{FA}}$, the number of Phase 2 samples.

### C.1 Generalization Bounds for Bounded Lipschitz Losses

Let us focus on a general $C_{\ell}$ Lipschitz loss $\ell(f(\cdot;\boldsymbol{a},\boldsymbol{W},\boldsymbol{b})-y)$ for now. Later, we will argue how to extend the results of this section to the squared error loss.
Our uniform convergence argument depends on the covering number of the family of adversarial loss functions. Let $\Theta\subseteq\mathbb{R}^{N}$ be the set of second layer weights, to be determined later.
This family is given by

$$ $\mathcal{L}(\boldsymbol{W},\boldsymbol{b})=\{(\boldsymbol{x},y)\mapsto\max_{ \mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq\varepsilon} \ell(f(\boldsymbol{x}+\boldsymbol{\delta};\boldsymbol{a},\boldsymbol{W}, \boldsymbol{b})-y)\,:\,\boldsymbol{a}\in\Theta\}.$ $$

For brevity, we will also use $\mathcal{L}$ to denote $\mathcal{L}(\boldsymbol{W},\boldsymbol{b})$, but we highlight that $\boldsymbol{W}$ and $\boldsymbol{b}$ are fixed at this stage. We define the following metric over this family

$$ $\forall\tilde{l},\tilde{l^{\prime}}\in\mathcal{L}(\boldsymbol{W},\boldsymbol{b }),\quad d_{\mathcal{L}}(\tilde{l},\tilde{l}^{\prime})^{2}\coloneqq\frac{1}{n} \sum_{i=1}^{n}(\tilde{\ell}(\boldsymbol{x}^{(i)},y^{(i)})-\tilde{\ell}^{\prime }(\boldsymbol{x}^{(i)},y^{(i)}))^{2}.$ $$

We say $\mathcal{S}\subseteq\mathcal{L}$ is an $\epsilon$-cover of $\mathcal{L}$ if for every $\tilde{l}\in\mathcal{L}$, there exists $\tilde{l}^{\prime}\in\mathcal{S}$ such that $d_{\mathcal{L}}(\tilde{l},\tilde{l}^{\prime})\leq\epsilon$. The $\epsilon$-covering number of $\mathcal{L}$ is the least cardinality among all $\epsilon$-covers of $\mathcal{L}$, which we denote by $\mathcal{C}(\mathcal{L},d_{\mathcal{L}},\epsilon)$.
Note that since $\mathcal{L}$ is paramterized by $\boldsymbol{a}$, constructing such a covering reduces to constructing a finite set over $\Theta$.

Therefore, we define the following metric over $\Theta$,

$$ $\forall\,\boldsymbol{a},\boldsymbol{a}^{\prime}\in\Theta,\quad d_{\Theta}( \boldsymbol{a},\boldsymbol{a}^{\prime})^{2}\coloneqq\frac{1}{n}\sum_{i=1}^{n} \max_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}^{(i)}}}\right\|\leq \epsilon}\big{(}f(\boldsymbol{x}^{(i)}+\boldsymbol{\delta}^{(i)};\boldsymbol{a },\boldsymbol{W},\boldsymbol{b})-f(\boldsymbol{x}^{(i)}+\boldsymbol{\delta}^{( i)};\boldsymbol{a}^{\prime},\boldsymbol{W},\boldsymbol{b})\big{)}^{2}.$ $$

We can similarly define the $\epsilon$-covering number of $\Theta$ with respect to the metric $d_{\Theta}$ as $\mathcal{C}(\Theta,d_{\Theta},\epsilon)$. The following lemma relates the covering numbers of $\mathcal{L}$ and $\Theta$.

###### Lemma 14 .

We have $\mathcal{C}(\mathcal{L},d_{\mathcal{L}},\epsilon)\leq\mathcal{C}(\Theta,d_{
\Theta},\epsilon/C_{\ell})$ for all $\epsilon>0$.

Proof.
We will use the following fact in the proof. For any $F_{1},F_{2}:S\to\mathbb{R}$, we have

$$ $\mathopen{}\mathclose{{}\left|{\max_{\boldsymbol{\delta}_{1}\in S}F_{1}( \boldsymbol{\delta}_{1})-\max_{\boldsymbol{\delta}_{2}\in S}F_{2}(\boldsymbol{ \delta}_{2})}}\right|\leq\max_{\boldsymbol{\delta}\in S}\mathopen{}\mathclose{ {}\left|{F_{1}(\boldsymbol{\delta})-F_{2}(\boldsymbol{\delta})}}\right|.$ (C.1) $$

This is true because

$$ $\max_{\boldsymbol{\delta}_{1}\in S}F_{1}(\boldsymbol{\delta}_{1})-\max_{ \boldsymbol{\delta}_{2}\in S}F_{2}(\boldsymbol{\delta}_{2})\leq\max_{ \boldsymbol{\delta}_{1}\in S}\big{\{}F_{1}(\boldsymbol{\delta}_{1})-F_{2}( \boldsymbol{\delta}_{1})\big{\}},$ $$

and the other direction holds by symmetry. This trick is used to relate the adversarial loss to its non-adversarial counterpart, e.g. in [, Lemma 5].

Now, we will show that an $\epsilon/C_{\ell}$ cover for $\Theta$ implies an $\epsilon$ cover for $\mathcal{L}$. We will supress dependence on the fixed $\boldsymbol{W}$ and $\boldsymbol{b}$ in the notation. Let $\mathcal{S}_{\Theta}$ be an $\epsilon/C_{\ell}$ cover of $\Theta$ with respect to the $d_{\Theta}$ metric. Then, we define $\mathcal{S}$ via

$$ $\mathcal{S}=\{(\boldsymbol{x},y)\mapsto\max_{\mathopen{}\mathclose{{}\left\|{ \boldsymbol{\delta}}}\right\|\leq\varepsilon}\ell(f(\boldsymbol{x}+\boldsymbol {\delta};\boldsymbol{a})-y):\boldsymbol{a}\in\mathcal{S}_{\Theta}\}.$ $$

To show $\mathcal{S}$ is an $\epsilon$ cover of $\mathcal{L}$, consider an arbitrary $\tilde{\ell}(\boldsymbol{x},y)=\max_{\mathopen{}\mathclose{{}\left\|{
\boldsymbol{\delta}}}\right\|\leq\varepsilon}\ell(f(\boldsymbol{x}+\boldsymbol
{\delta};\boldsymbol{a})-y)$. Suppose $\boldsymbol{a}^{\prime}$ is the closest element to $\boldsymbol{a}$ in $\mathcal{S}_{\Theta}$,
and let $\tilde{\ell}^{\prime}(\boldsymbol{x},y)=\max_{\mathopen{}\mathclose{{}\left\|{
\boldsymbol{\delta}}}\right\|\leq\varepsilon}\ell(f(\boldsymbol{x}+\boldsymbol
{\delta};\boldsymbol{a}^{\prime})-y)$. Then,

$$ $\displaystyle d_{\mathcal{L}}(\tilde{\ell},\tilde{\ell}^{\prime})^{2}$ $\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\Big{(}\max_{\|\boldsymbol{\delta}_{1}^ {(i)}\|\leq\varepsilon}\ell(f(\boldsymbol{x}+\boldsymbol{\delta}_{1}^{(i)}; \boldsymbol{a})-y^{(i)})-\max_{\|\boldsymbol{\delta}_{2}^{(i)}\|\leq \varepsilon}\ell(f(\boldsymbol{x}+\boldsymbol{\delta}^{(i)}_{2};\boldsymbol{a} ^{\prime})-y^{(i)})\Big{)}^{2}$ $\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\max_{\|\boldsymbol{\delta}^{(i)}\| \leq\varepsilon}\big{(}\ell(f(\boldsymbol{x}+\boldsymbol{\delta}^{(i)}; \boldsymbol{a})-y^{(i)})-\ell(f(\boldsymbol{x}+\boldsymbol{\delta}^{(i)}; \boldsymbol{a}^{\prime})-y^{(i)})\big{)}^{2}$ $\displaystyle\leq\frac{C_{\ell}^{2}}{n}\sum_{i=1}^{n}\max_{\mathopen{} \mathclose{{}\left\|{\boldsymbol{\delta}^{(i)}}}\right\|\leq\varepsilon}\big{( }f(\boldsymbol{x}+\boldsymbol{\delta}^{(i)};\boldsymbol{a})-f(\boldsymbol{x}+ \boldsymbol{\delta}^{(i)};\boldsymbol{a}^{\prime})\big{)}^{2}$ $\displaystyle\leq C_{\ell}^{2}d_{\Theta}(\boldsymbol{a},\boldsymbol{a}^{\prime })^{2}\leq\epsilon^{2},$ $$

where we used (C.1) for the first inequality.
∎

To construct an $\epsilon$-cover of $\Theta$, we depend on the Maurey sparsification lemma [], which has been used in the literature for providing covering numbers for linear classes [] and neural networks via matrix covering, see e.g. [].

###### Lemma 15 (Maurey Sparsification Lemma, [ 61 , Lemma 1] ) .

Let $\mathcal{H}$ be a Hilbert space with norm $\mathopen{}\mathclose{{}\left\|{\cdot}}\right\|$, let $\boldsymbol{u}\in\mathcal{H}$ be represented by $\boldsymbol{u}=\sum_{j=1}^{m}\alpha_{j}\boldsymbol{v}_{j}$, where $\alpha_{j}\geq 0$ and $\mathopen{}\mathclose{{}\left\|{\boldsymbol{v}_{j}}}\right\|\leq b$ for all $j\in[m]$, and $\alpha=\sum_{j=1}^{m}\alpha_{j}\leq 1$. Then, for every $k\geq 1$, there exist non-negative integers $k_{1},\ldots,k_{m}$, such that $\sum_{j=1}^{m}k_{j}\leq k$ and

$$ $\Big{\|}\boldsymbol{u}-\frac{1}{k}\sum_{j=1}^{m}k_{j}\boldsymbol{v}_{j}\Big{\| }\leq\frac{\alpha b^{2}-\mathopen{}\mathclose{{}\left\|{\boldsymbol{u}}}\right \|^{2}}{k}.$ $$

Then, we have the following upper bound on the the covering number of $\Theta$.

###### Lemma 16 .

Suppose $\sigma$ satisfies (B.1), $\Theta=\{\mathopen{}\mathclose{{}\left\|{\boldsymbol{a}}}\right\|_{1}\leq r_{a}\}$, and additionally $\mathopen{}\mathclose{{}\left\|{\boldsymbol{w}_{i}}}\right\|\leq r_{w}$ and $\mathopen{}\mathclose{{}\left|{b_{i}}}\right|\leq r_{b}$ for all $1\leq i\leq N$. Then we have

$$ $\log\mathcal{C}(\Theta,d_{\Theta},\epsilon)\leq\frac{C_{\bar{q}}L_{\sigma}^{2} r_{a}^{2}\log N\mathopen{}\mathclose{{}\left\{T^{(\bar{q})}_{\boldsymbol{W}, \boldsymbol{X}}+r_{w}^{2\bar{q}}\varepsilon^{2\bar{q}}+r_{b}^{2\bar{q}}+T^{(2) }_{\boldsymbol{W},\boldsymbol{X}}+r_{w}^{2}\varepsilon^{2}+r_{b}^{2}}\right\}} {\epsilon^{2}},$ $$

where $T^{(\bar{q})}_{\boldsymbol{W},\boldsymbol{X}}\coloneqq\max_{1\leq j\leq N}
\frac{1}{n}\sum_{i=1}^{n}\mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}_{
j}},{\boldsymbol{x}_{i}}}\right\rangle^{2\bar{q}}$.

Proof.
Given some positive integer $k>0$, let $\mathcal{S}_{\Theta}$ be given by the following

$$ $\mathcal{S}_{\Theta}=\Big{\{}\frac{r_{a}}{k}(k_{1}-k^{\prime}_{1},k_{2}-k^{ \prime}_{2},\ldots,k_{N}-k^{\prime}_{N})^{\top}:\forall i,\,k_{i},k^{\prime}_{ i}\geq 0,\quad\sum_{i=1}^{N}k_{i}+\sum_{i=1}^{N}k^{\prime}_{i}=k\Big{\}}.$ $$

Let $\boldsymbol{X},\boldsymbol{\Delta}\in\mathbb{R}^{n\times d}$ be the matrices with $(\boldsymbol{x}_{i})$ and $(\boldsymbol{\delta}_{i})$ as rows respectively. Let $\boldsymbol{A}=\sigma((\boldsymbol{X}+\boldsymbol{\Delta})\boldsymbol{W}^{\top
}+\mathbf{1}_{n}\boldsymbol{b}^{\top})\in\mathbb{R}^{n\times N}$. Then,

$$ $\frac{1}{n}\sum_{i=1}^{n}\big{(}f(\boldsymbol{x}^{(i)}+\boldsymbol{\delta}^{(i )};\boldsymbol{a},\boldsymbol{W},\boldsymbol{b})-f(\boldsymbol{x}^{(i)}+ \boldsymbol{\delta}^{(i)};\boldsymbol{a}^{\prime},\boldsymbol{W},\boldsymbol{b })\big{)}^{2}=\frac{1}{n}\mathopen{}\mathclose{{}\left\|{\boldsymbol{A}( \boldsymbol{a}-\boldsymbol{a}^{\prime})}}\right\|^{2}=\frac{1}{n}\mathopen{} \mathclose{{}\left\|{\sum_{i=1}^{N}\boldsymbol{A}_{i}(a_{i}-a^{\prime}_{i})}} \right\|^{2},$ $$

where $\boldsymbol{A}_{i}=\sigma((\boldsymbol{X}+\boldsymbol{\Delta})\boldsymbol{w}_{
i}+\mathbf{1}_{n}b_{i})$ is the $i$th column of $\boldsymbol{A}$. We are going to choose $\boldsymbol{a}^{\prime}$ from $\mathcal{S}_{\Theta}$. To that end, define

$$ $\boldsymbol{\tilde{A}}_{i}=\mathop{\mathrm{missing}}{sign}(a_{i})\boldsymbol{A }_{i},\quad\tilde{k}_{i}=\begin{cases}k_{i},&\mathop{\mathrm{missing}}{sign}( \boldsymbol{a}_{i})\geq 0\\ k^{\prime}_{i},&\mathop{\mathrm{missing}}{sign}(\boldsymbol{a}_{i})<0\end{ cases}.$ $$

Further, we will choose $k^{\prime}_{i}=0$ if $\mathop{\mathrm{missing}}{sign}(\boldsymbol{a}_{i})\geq 0$ and $k_{i}=0$ otherwise. Therefore, we have $\sum_{i=1}^{N}\tilde{k}_{i}=k$. By Mauery’s sparsification lemma [, Lemma 13], there exist $\tilde{k}_{i}\geq 0$ with $\sum_{i=1}^{n}\tilde{k}_{i}=k$ such that

$$ $\mathopen{}\mathclose{{}\left\|{\sum_{i=1}^{N}\mathopen{}\mathclose{{}\left|{a _{i}}}\right|\boldsymbol{\tilde{A}}_{i}-\frac{r_{a}}{k}\sum_{i=1}^{N}\tilde{k} _{i}\boldsymbol{\tilde{A}}_{i}}}\right\|^{2}\leq\frac{r_{a}^{2}b^{2}}{k},$ $$

where $\mathopen{}\mathclose{{}\left\|{\boldsymbol{A}_{i}}}\right\|\leq b$ for all $i$. Consequently, given $\boldsymbol{a}$, we have constructed $\boldsymbol{a}^{\prime}\in\mathcal{S}_{\Theta}$ such that

$$ $\frac{1}{n}\mathopen{}\mathclose{{}\left\|{\sum_{i=1}^{N}\boldsymbol{A}_{i}(a_ {i}-a^{\prime}_{i})}}\right\|^{2}\leq\frac{r_{a}^{2}b^{2}}{nk}.$ $$

Next, we provide a bound on $b$. By the assumptions on $\sigma$, we have

$$ $\displaystyle\mathopen{}\mathclose{{}\left\|{\boldsymbol{A}_{i}}}\right\|^{2}\lesssim$ $\displaystyle C_{\bar{q}}L_{\sigma}^{2}\mathopen{}\mathclose{{}\left(\mathopen {}\mathclose{{}\left\|{\boldsymbol{X}\boldsymbol{w}_{i}}}\right\|_{2\bar{q}}^{ 2\bar{q}}+\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Delta}\boldsymbol{w}_{i }}}\right\|_{2\bar{q}}^{2\bar{q}}+nb_{i}^{2\bar{q}}+\mathopen{}\mathclose{{} \left\|{\boldsymbol{X}\boldsymbol{w}_{i}}}\right\|^{2}+\mathopen{}\mathclose{{ }\left\|{\boldsymbol{\Delta}}}\right\|^{2}+nb_{i}^{2}}\right)$ $\displaystyle\lesssim$ $\displaystyle nC_{\bar{q}}L_{\sigma}^{2}\mathopen{}\mathclose{{}\left(T^{(\bar {q})}_{\boldsymbol{W},\boldsymbol{X}}+r_{w}^{2\bar{q}}\varepsilon^{2\bar{q}}+r _{b}^{2\bar{q}}+T^{(2)}_{\boldsymbol{W},\boldsymbol{X}}+r_{w}^{2}\varepsilon^{ 2}+r_{b}^{2}}\right).$ $$

Consequently, we can choose

$$ $k=\mathopen{}\mathclose{{}\left\lceil\frac{C_{\bar{q}}L_{\sigma}^{2}r_{a}^{2} \mathopen{}\mathclose{{}\left(T^{(\bar{q})}_{\boldsymbol{W},\boldsymbol{X}}+r_ {w}^{2\bar{q}}\varepsilon^{2\bar{q}}+r_{b}^{2\bar{q}}+T^{(2)}_{\boldsymbol{W}, \boldsymbol{X}}+r_{w}^{2}\varepsilon^{2}+r_{b}^{2}}\right)}{\epsilon^{2}}} \right\rceil.$ $$

Finally, we need to count $\mathopen{}\mathclose{{}\left|{\mathcal{S}_{\Theta}}}\right|$. Note that

$$ $\mathopen{}\mathclose{{}\left|{\mathcal{S}_{\Theta}}}\right|=\binom{2N+k-1}{k} \leq\mathopen{}\mathclose{{}\left(\frac{e(2N+k-1)}{k}}\right)^{k}\leq(3eN)^{k},$ $$

which concludes the proof.
∎

We can now turn the above covering number into Rademacher complexity via a chaining argument, as follows.

###### Lemma 17 .

Let $\mathfrak{R}(\mathcal{L}(\boldsymbol{W},\boldsymbol{b}))$ denote the Rademacher complexity of the class of adversarial loss functions $\mathcal{L}(\boldsymbol{W},\boldsymbol{b})$, defined via

$$ $\mathfrak{R}(\mathcal{L}(\boldsymbol{W},\boldsymbol{b}))\coloneqq\operatorname {\mathbb{E}}\mathopen{}\mathclose{{}\left[{\sup_{\boldsymbol{a}\in\Theta} \mathopen{}\mathclose{{}\left|{\frac{1}{n}\sum_{i=1}^{n}\xi_{i}\max_{\mathopen {}\mathclose{{}\left\|{\boldsymbol{\delta}^{(i)}}}\right\|\leq\varepsilon}\ell (f(\boldsymbol{x}^{(i)}+\boldsymbol{\delta}^{(i)};\boldsymbol{a},\boldsymbol{W },\boldsymbol{b}),y^{(i)})}}\right|}}\right],$ $$

where $\xi_{i}$ are i.i.d. Rademacher random variables and $\Theta=\{\boldsymbol{a}:\mathopen{}\mathclose{{}\left\|{\boldsymbol{a}}}\right
\|_{1}\leq r_{a}\}$. For simplicity, assume $C_{\ell},r_{a}\gtrsim 1$. Then we have

$$ $\mathfrak{R}(\mathcal{L}(\boldsymbol{W},\boldsymbol{b}))\lesssim\frac{C_{\ell} C_{\bar{q}}L_{\sigma}r_{a}\log n\log N\mathopen{}\mathclose{{}\left( \operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\sqrt{T^{(\bar{q})}_{ \boldsymbol{W},\boldsymbol{X}}}}}\right]+r_{w}^{\bar{q}}\varepsilon^{\bar{q}}+ r_{b}^{\bar{q}}+\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\sqrt{ T^{(2)}_{\boldsymbol{W},\boldsymbol{X}}}}}\right]+r_{w}\varepsilon+r_{b}} \right)}{\sqrt{n}}.$ $$

Proof.
Let $\mathfrak{R}_{n}(\mathcal{L}(\boldsymbol{W},\boldsymbol{b}))$ denote the empirical Rademacher complexity by

$$ $\mathfrak{R}_{n}(\mathcal{L}(\boldsymbol{W},\boldsymbol{b}))\coloneqq \operatorname{\mathbb{E}}_{\boldsymbol{\xi}}\mathopen{}\mathclose{{}\left[\sup _{\boldsymbol{a}\in\Theta}\mathopen{}\mathclose{{}\left|{\frac{1}{n}\sum_{i=1} ^{n}\xi_{i}\max_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}^{(i)}}} \right\|\leq\varepsilon}\ell(f(\boldsymbol{x}^{(i)}+\boldsymbol{\delta}^{(i)}; \boldsymbol{a},\boldsymbol{W},\boldsymbol{b}),y^{(i)})}}\right|}\right],$ $$

where the expectation is only taken w.r.t. the randomness of $\xi$ and is conditional on the training set. For simplicity, define

$$ $B\coloneqq C_{\bar{q}}L_{\sigma}\mathopen{}\mathclose{{}\left(\sqrt{T^{(\bar{q })}_{\boldsymbol{W},\boldsymbol{X}}}+r_{w}^{\bar{q}}\varepsilon^{\bar{q}}+r_{b }^{\bar{q}}+\sqrt{T^{(2)}_{\boldsymbol{W},\boldsymbol{X}}}+r_{w}\varepsilon^{2 }+r_{b}}\right).$ $$

Then, by a standard chaining argument, we have for all $\alpha>0$,

$$ $\displaystyle\mathfrak{R}_{n}(\mathcal{L}(\boldsymbol{W},\boldsymbol{b}))$ $\displaystyle\lesssim\alpha+\int_{\epsilon=\alpha}^{\infty}\sqrt{\frac{\log \mathcal{C}(\mathcal{L},d_{\mathcal{L}},\epsilon)}{n}}\mathrm{d}\epsilon$ $\displaystyle\lesssim\alpha+\frac{C_{\ell}r_{a}B\log N}{\sqrt{n}}\log\Big{(} \frac{1}{\alpha}\Big{)}.$ $$

By choosing $\alpha=1/\sqrt{n}$, we obtain

$$ $\mathfrak{R}_{n}(\mathcal{L}(\boldsymbol{W},\boldsymbol{b}))\lesssim\frac{C_{ \ell}r_{a}B\log n\log N}{\sqrt{n}}.$ $$

Taking expectations with respect to the input distribution completes the proof.
∎

Note that it remains to provide an upper bound for $T^{(\bar{q})}_{\boldsymbol{W},\boldsymbol{x}}$ introduced in Lemma 16. This is achieved by the following lemma.

###### Lemma 18 .

Suppose $\mathopen{}\mathclose{{}\left\|{\boldsymbol{w}_{i}}}\right\|\leq r_{w}$. Then, for all $\bar{q}>0$ and $N>e$, we have

$$ $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_{1\leq j\leq N} \frac{1}{n}\sum_{i=1}^{n}\mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}_{ j}},{\boldsymbol{x}^{(i)}}}\right\rangle^{2\bar{q}}}}\right]\leq C_{\bar{q}}r_ {w}^{2\bar{q}}(\log N)^{\bar{q}},$ $$

where $C_{\bar{q}}$ is a constant depending only on $\bar{q}$.

Proof.
For conciseness, let $Z_{j}\coloneqq\frac{1}{n}\sum_{i=1}^{n}\mathopen{}\mathclose{{}\left\langle{
\boldsymbol{w}_{j}},{\boldsymbol{x}^{(i)}}}\right\rangle^{2\bar{q}}$. By non-negativity of $Z_{j}$ and Jensen’s inequality, for all $t\geq 1$ we have

$$ $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_{1\leq j\leq N}Z_ {j}}}\right]\leq\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_{ 1\leq j\leq N}Z_{j}^{t}}}\right]^{1/t}\leq\Big{(}\sum_{j=1}^{N}\operatorname{ \mathbb{E}}\mathopen{}\mathclose{{}\left[{Z_{j}^{t}}}\right]\Big{)}^{1/t}\leq N ^{1/t}\big{(}\max_{1\leq j\leq N}\operatorname{\mathbb{E}}\mathopen{} \mathclose{{}\left[{Z_{j}^{t}}}\right]\big{)}^{1/t}.$ $$

Further, by Jensens’s inequality

$$ $\displaystyle\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{Z_{j}^{t} }}\right]$ $\displaystyle=\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{ \mathopen{}\mathclose{{}\left(\frac{1}{n}\sum_{i=1}^{n}\mathopen{}\mathclose{{ }\left\langle{\boldsymbol{w}_{j}},{\boldsymbol{x}^{(i)}}}\right\rangle^{2\bar{ q}}}\right)^{t}}}\right]$ $\displaystyle\leq\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\frac {1}{n}\sum_{i=1}^{n}\mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}_{j}},{ \boldsymbol{x}^{(i)}}}\right\rangle^{2\bar{q}t}}}\right]$ $\displaystyle\leq(Cr_{w})^{2\bar{q}t}(2\bar{q}t)^{\bar{q}t},$ $$

where $C>0$ is a absolute constant, and we used the moment bound of subGaussian random variables along with the fact that $\mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}_{j}},{\boldsymbol{x}}}\right\rangle$ is a centered subGaussian random variable with subGaussian norm $\mathcal{O}(r_{w})$. As a result,

$$ $\displaystyle\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_{1 \leq j\leq N}Z_{j}}}\right]\leq C_{\bar{q}}r_{w}^{2\bar{q}}N^{1/t}t^{\bar{q}} \lesssim C_{\bar{q}}r_{w}^{2\bar{q}}(\log N)^{\bar{q}},$ $$

where the last inequality follows by choosing $t=\log N$.
∎

As a consequence, if the loss is also bounded, we get the following high-probability concentration bound.

###### Corollary 19 .

Suppose $|\tilde{\ell}|\leq B_{\ell}$ for all $\tilde{\ell}\in\mathcal{L}(\boldsymbol{W},\boldsymbol{b})$. Then, with probability at least $1-\delta$ we have

$$ $\displaystyle\mathopen{}\mathclose{{}\left|{\sup_{\tilde{\ell}\in\mathcal{L}( \boldsymbol{W},\boldsymbol{b})}\operatorname{\mathbb{E}}\mathopen{}\mathclose{ {}\left[{\tilde{\ell}(\boldsymbol{x},y)}}\right]-\frac{1}{n}\sum_{i=1}^{n} \tilde{\ell}\big{(}\boldsymbol{x}^{(i)},y^{(i)}\big{)}}}\right|\lesssim$ $\displaystyle\frac{C_{\ell}r_{a}R\log n\log N+B_{\ell}\sqrt{\log(1/\delta)}}{ \sqrt{n}},$ $$

where

$$ $R\coloneqq C_{\bar{q}}L_{\sigma}(r_{w}^{\bar{q}}(\log^{q/2}N+\varepsilon^{\bar {q}})+r_{b}^{\bar{q}}+r_{w}(\log^{1/2}N+\varepsilon)+r_{b}).$ $$

###### Lemma 14 .

###### Lemma 15 (Maurey Sparsification Lemma, [ 61 , Lemma 1] ) .

###### Lemma 16 .

###### Lemma 17 .

###### Lemma 18 .

###### Corollary 19 .

### C.2 Applying the Generalization Bound to Squared Loss

To apply the generalization argument above to the squared loss, we bound it with a threshold $\tau$, and define the loss family

$$ $\mathcal{L}_{\tau}(\boldsymbol{W},\boldsymbol{b})\coloneqq\{(\boldsymbol{x},y) \mapsto\big{\{}\max_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}} \right\|\leq\varepsilon}(f(\boldsymbol{x}+\boldsymbol{\delta};\boldsymbol{a}, \boldsymbol{W},\boldsymbol{b})-y)^{2}\land\tau\,:\,\boldsymbol{a}\in\Theta\big {\}}.$ $$

We similarly define $\mathrm{AR}_{\tau}$ and $\widehat{\mathrm{AR}}_{\tau}$. Recall that our goal is to show

$$ $\mathrm{AR}(\boldsymbol{\hat{a}},\boldsymbol{W},\boldsymbol{b})\leq\widehat{ \mathrm{AR}}(\boldsymbol{\hat{a}},\boldsymbol{W},\boldsymbol{b})+\epsilon_{1}( n,N,d).$ $$

We readily have $\widehat{\mathrm{AR}}_{\tau}(\boldsymbol{\hat{a}},\boldsymbol{W},\boldsymbol{b
})\leq\widehat{\mathrm{AR}}(\boldsymbol{\hat{a}},\boldsymbol{W},\boldsymbol{b})$. Further, Corollary 19 yields

$$ $\mathopen{}\mathclose{{}\left|{\mathrm{AR}_{\tau}(\boldsymbol{\hat{a}}, \boldsymbol{W},\boldsymbol{b})-\widehat{\mathrm{AR}}_{\tau}(\boldsymbol{\hat{a }},\boldsymbol{W},\boldsymbol{b})}}\right|\lesssim\frac{\sqrt{\tau}r_{a}R\log n \log N}{\sqrt{n}}+\tau\sqrt{\frac{\log(1/\delta)}{n}},$ $$

with probability at least $1-\delta$. Thus, the remaining step is to bound $\mathrm{AR}(\boldsymbol{\hat{a}},\boldsymbol{W},\boldsymbol{b})$ and $\widehat{\mathrm{AR}}(\boldsymbol{\hat{a}},\boldsymbol{W},\boldsymbol{b})$ with their clipped versions. To do so, we first provide the following tail probability estimate.

###### Lemma 20 .

Suppose $(z_{j})_{j=1}^{N}$ are non-negative random variables with subGaussian norm $r$. Then, for any $\bar{q}>0$ and $\tau\geq C_{\bar{q}}r^{\bar{q}}$ where $C_{\bar{q}}$ is a constant depending only on $\bar{q}$, we have

$$ $\mathbb{P}\mathopen{}\mathclose{{}\left({\frac{1}{N}\sum_{j=1}^{N}z_{j}^{\bar{ q}}\geq\tau}}\right)\leq\exp\mathopen{}\mathclose{{}\left(-\frac{c\tau^{2/\bar {q}}}{r^{2}}}\right),$ $$

where $c>0$ is an absolute constant.

Proof.
For any $t\geq 1$, we have the following Markov bound,

$$ $\mathbb{P}\mathopen{}\mathclose{{}\left({\frac{1}{N}\sum_{j=1}^{N}z_{j}^{\bar{ q}}\geq\tau}}\right)=\mathbb{P}\mathopen{}\mathclose{{}\left({\Big{(}\frac{1}{ N}\sum_{j=1}^{N}z_{j}^{\bar{q}}\Big{)}^{t}\geq\tau^{t}}}\right)\leq\frac{ \operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\Big{(}\frac{1}{N}\sum _{j=1}^{N}z_{j}^{\bar{q}}\Big{)}^{t}}}\right]}{\tau^{t}}\leq\frac{ \operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\frac{1}{N}\sum_{j=1}^ {N}z_{j}^{\bar{q}t}}}\right]}{\tau^{t}},$ $$

where the last inequality follows from Jensen’s inequality. Further, by subGaussianity of $z_{j}$, we have $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{z_{j}^{\bar{q}t}}}
\right]\leq(Cr^{2}\bar{q}t)^{\bar{q}t/2}$, where $C>0$ is an absolute constant. As a result,

$$ $\mathbb{P}\mathopen{}\mathclose{{}\left({\frac{1}{N}\sum_{j=1}^{N}z_{j}^{\bar{ q}}\geq\tau}}\right)\leq\frac{(Cr^{2}\bar{q}t)^{\bar{q}t/2}}{\tau^{t}}.$ $$

The above bound is minimized at $t=\frac{\tau^{2/\bar{q}}}{Cr^{2}\bar{q}e}$. Note that $t\geq 1$ requires $\tau\geq C_{\bar{q}}r^{\bar{q}}$. Plugging this choice of $t$ in the above bound yields

$$ $\mathbb{P}\mathopen{}\mathclose{{}\left({\frac{1}{N}\sum_{j=1}^{N}z_{j}^{\bar{ q}}\geq\tau}}\right)\leq\exp\mathopen{}\mathclose{{}\left(-\frac{\tau^{2/\bar{ q}}}{2Cr^{2}e}}\right),$ $$

which completes the proof.
∎

###### Lemma 21 .

Suppose Assumption 2 holds. Let $\Theta=\{\boldsymbol{a}:\mathopen{}\mathclose{{}\left\|{\boldsymbol{a}}}\right
\|\leq r_{a}/\sqrt{N}\}$, $\mathopen{}\mathclose{{}\left\|{\boldsymbol{w}_{i}}}\right\|\leq r_{w}$, and $\mathopen{}\mathclose{{}\left|{b_{i}}}\right|\leq r_{b}$ for all $i\in[N]$. Assume $\sigma$ satisfes (B.1). Define $\varepsilon_{1}\coloneqq 1\lor\varepsilon$, and let

$$ $\varkappa\coloneqq C_{\bar{q}}r_{a}^{2}L_{\sigma}^{2}(r_{w}^{2\bar{q}} \varepsilon_{1}^{2\bar{q}}+r_{b}^{2\bar{q}}+r_{w}^{2}\varepsilon_{1}^{2}+r_{b} ^{2})+C_{p},$ $$

where $C_{\bar{q}}$ and $C_{p}$ are constants depending only on $\bar{q}$ and $p$ respectively. Then, for all

$$ $\tau\geq C\mathopen{}\mathclose{{}\left\{\varkappa\lor L_{\sigma}^{2}r_{w}^{2 \bar{q}}\log^{\bar{q}}\frac{n}{\delta}\lor\log^{p}\frac{n}{\delta}}\right\},$ $$

we have

$$ $\displaystyle\mathopen{}\mathclose{{}\left|{\mathrm{AR}(\boldsymbol{a}, \boldsymbol{W},\boldsymbol{b})-\widehat{\mathrm{AR}}(\boldsymbol{a}, \boldsymbol{W},\boldsymbol{b})}}\right|\leq$ $\displaystyle\mathopen{}\mathclose{{}\left|{\mathrm{AR}_{\tau}(\boldsymbol{a}, \boldsymbol{W},\boldsymbol{b})-\widehat{\mathrm{AR}}_{\tau}(\boldsymbol{a}, \boldsymbol{W},\boldsymbol{b})}}\right|$ $\displaystyle+C\varkappa\mathopen{}\mathclose{{}\left(\exp\Big{(}-\Omega\Big{( }\frac{\tau^{1/\bar{q}}}{L_{\sigma}^{2/\bar{q}}r_{w}^{2}}\Big{)}\Big{)}+\exp(- \Omega(\tau^{1/p}))}\right),$ $$

with probability at least $1-\delta$ uniformly over all $\boldsymbol{a}\in\Theta$.

Proof.
Since $\boldsymbol{W}$ and $\boldsymbol{b}$ are fixed, we use the shorthand notation $f(\boldsymbol{x};\boldsymbol{a})=f(\boldsymbol{x};\boldsymbol{a},\boldsymbol{W
},\boldsymbol{b})$.

In the first section of the proof, we will upper and lower bound $\mathrm{AR}(\boldsymbol{a},\boldsymbol{W},\boldsymbol{b})$ with $\mathrm{AR}_{\tau}(\boldsymbol{a},\boldsymbol{W},\boldsymbol{b})$. Note that the lower bound is trivial as $\mathrm{AR}_{\tau}(\boldsymbol{a},\boldsymbol{W},\boldsymbol{b})\leq\mathrm{AR
}(\boldsymbol{a},\boldsymbol{W},\boldsymbol{b})$, thus we move on to the upper bound. Let

$$ $\tilde{\ell}(\boldsymbol{x},y)=\max_{\mathopen{}\mathclose{{}\left\|{ \boldsymbol{\delta}}}\right\|\leq\varepsilon}(f(\boldsymbol{x}+\boldsymbol{ \delta};\boldsymbol{a})-y)^{2}.$ $$

Then,

$$ $\displaystyle\mathrm{AR}(\boldsymbol{a},\boldsymbol{W},\boldsymbol{b})$ $\displaystyle=\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\tilde{ \ell}(\boldsymbol{x},y)\mathbb{I}\mathopen{}\mathclose{{}\left[{\tilde{\ell}( \boldsymbol{x},y)\leq\tau}}\right]}}\right]+\operatorname{\mathbb{E}}\mathopen {}\mathclose{{}\left[{\tilde{\ell}(\boldsymbol{x},y)\mathbb{I}\mathopen{} \mathclose{{}\left[{\tilde{\ell}(\boldsymbol{x},y)>\tau}}\right]}}\right]$ $\displaystyle\leq\mathrm{AR}_{\tau}(\boldsymbol{a},\boldsymbol{W},\boldsymbol{ b})+\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\tilde{\ell}( \boldsymbol{x},y)^{2}}}\right]^{1/2}\mathbb{P}\mathopen{}\mathclose{{}\left({ \tilde{\ell}(\boldsymbol{x},y)\geq\tau}}\right)^{1/2}.$ $$

Further, we have the following upper bound for the adversarial loss,

$$ $\displaystyle\tilde{\ell}(\boldsymbol{x},y)$ $\displaystyle=\max_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}} \right\|\leq\varepsilon}(f(\boldsymbol{x}+\boldsymbol{\delta};\boldsymbol{a})- y)^{2}$ $\displaystyle\lesssim\max_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta} }}\right\|\leq\varepsilon}f(\boldsymbol{x}+\boldsymbol{\delta};\boldsymbol{a}) ^{2}+y^{2}$ $\displaystyle\lesssim\max_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta} }}\right\|\leq\varepsilon}\mathopen{}\mathclose{{}\left\|{\boldsymbol{a}}} \right\|^{2}\mathopen{}\mathclose{{}\left\|{\sigma(\boldsymbol{W}(\boldsymbol{ x}+\boldsymbol{\delta})+\boldsymbol{b})}}\right\|^{2}+y^{2}$ $\displaystyle\lesssim r_{a}^{2}C_{\bar{q}}L_{\sigma}^{2}\mathopen{}\mathclose{ {}\left(\frac{1}{N}\sum_{j=1}^{N}\mathopen{}\mathclose{{}\left\langle{ \boldsymbol{w}_{j}},{\boldsymbol{x}}}\right\rangle^{2\bar{q}}+r_{w}^{2\bar{q}} \varepsilon^{2\bar{q}}+r_{b}^{2\bar{q}}+\frac{1}{N}\sum_{j=1}^{N}\mathopen{} \mathclose{{}\left\langle{\boldsymbol{w}_{j}},{\boldsymbol{x}}}\right\rangle^{ 2}+r_{w}^{2}\varepsilon^{2}+r_{b}^{2}}\right)+y^{2}$ $$

Moreover, by Jensen’s inequality,

$$ $\displaystyle\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\mathopen {}\mathclose{{}\left(\frac{1}{N}\sum_{j=1}^{N}\mathopen{}\mathclose{{}\left \langle{\boldsymbol{w}_{j}},{\boldsymbol{x}}}\right\rangle^{2\bar{q}}}\right)^ {2}}}\right]$ $\displaystyle\leq\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\frac {1}{N}\sum_{j=1}^{N}\mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}_{j}},{ \boldsymbol{x}}}\right\rangle^{4\bar{q}}}}\right]$ $\displaystyle\leq(Cr_{w})^{4\bar{q}}(4\bar{q})^{2\bar{q}}\leq C_{\bar{q}}r_{w} ^{4\bar{q}}$ $$

for all $\bar{q}>0$, where $C$ is an absolute constant and we used the subGaussianity of $\mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}_{j}},{\boldsymbol{x}}}\right\rangle$ to bound its moment. As a result,

$$ $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\tilde{\ell}( \boldsymbol{x},y)^{2}}}\right]^{1/2}\lesssim r_{a}^{2}C_{\bar{q}}L_{\sigma}^{2 }(r_{w}^{2\bar{q}}(1+\varepsilon^{2\bar{q}})+r_{b}^{2\bar{q}}+r_{w}^{2}(1+ \varepsilon^{2})+r_{b}^{2})+\operatorname{\mathbb{E}}\mathopen{}\mathclose{{} \left[{y^{4}}}\right]^{1/2}.$ $$

By assumption 2, we have $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{y^{4}}}\right]^{1/2}
\leq C_{p}$.

To estimate the tail probability of $\tilde{\ell}(\boldsymbol{x},y)$. Using the assumption on $\tau$ and the upper bound on $\tilde{\ell}(\boldsymbol{x},y)$ developed above, via a union bound we have

$$ $\displaystyle\mathbb{P}\mathopen{}\mathclose{{}\left({\tilde{\ell}(\boldsymbol {x},y)\geq\tau}}\right)$ $\displaystyle\leq\mathbb{P}\mathopen{}\mathclose{{}\left({\frac{L_{\sigma}^{2} }{N}\sum_{j=1}^{N}\mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}_{j}},{ \boldsymbol{x}}}\right\rangle^{2\bar{q}}+\frac{L_{\sigma}^{2}}{N}\sum_{j=1}^{N }\mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}_{j}},{\boldsymbol{x}}} \right\rangle^{2}+y^{2}\geq\frac{\tau}{2}}}\right)$ $\displaystyle\leq\mathbb{P}\mathopen{}\mathclose{{}\left({\frac{L_{\sigma}^{2} }{N}\sum_{j=1}^{N}\mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}_{j}},{ \boldsymbol{x}}}\right\rangle^{2\bar{q}}\geq\frac{\tau}{6}}}\right)+\mathbb{P} \mathopen{}\mathclose{{}\left({\frac{L_{\sigma}^{2}}{N}\sum_{j=1}^{N}\mathopen {}\mathclose{{}\left\langle{\boldsymbol{w}_{j}},{\boldsymbol{x}}}\right\rangle ^{2}\geq\frac{\tau}{6}}}\right)+\mathbb{P}\mathopen{}\mathclose{{}\left({y^{2} \geq\frac{\tau}{6}}}\right)$ $\displaystyle\leq 2\exp\mathopen{}\mathclose{{}\left(\frac{-c\tau^{1/\bar{q}}} {L_{\sigma}^{2/\bar{q}}r_{w}^{2}}}\right)+\mathbb{P}\mathopen{}\mathclose{{} \left({y^{2}\geq\tau}}\right),$ $$

where we used Lemma 20, the fact that $\mathopen{}\mathclose{{}\left|{\mathopen{}\mathclose{{}\left\langle{
\boldsymbol{w}_{j}},{\boldsymbol{x}}}\right\rangle}}\right|$ is subGaussian with norm $\mathcal{O}(r_{w})$, and that $\bar{q}\geq 1$. Furthermore, using the moment estimate on $y$ in Assumption 2 along with the technique developed in Lemma 20, we have

$$ $\mathbb{P}\mathopen{}\mathclose{{}\left({y^{2}\geq\frac{\tau}{6}}}\right)\leq \exp\mathopen{}\mathclose{{}\left(-c\tau^{1/p}}\right),$ $$

for $\tau\geq C_{p}$, where $c>0$ is an absolute constant.

As a result, we obtain

$$ $\mathrm{AR}(\boldsymbol{a},\boldsymbol{W},\boldsymbol{b})-\mathrm{AR}_{\tau}( \boldsymbol{a},\boldsymbol{W},\boldsymbol{b})\lesssim\varkappa\mathopen{} \mathclose{{}\left(\exp\Big{(}-\frac{c\tau^{1/\bar{q}}}{L_{\sigma}^{2/\bar{q}} r_{w}^{2}}\Big{)}+\exp(-c\tau^{1/p})}\right),$ $$

for all $\boldsymbol{a}\in\Theta$.

In the next part of the proof, we will show that with probability at least $1-\delta$, we have $\widehat{\mathrm{AR}}(\boldsymbol{a},\boldsymbol{W},\boldsymbol{b})=\widehat{
\mathrm{AR}}_{\tau}(\boldsymbol{a},\boldsymbol{W},\boldsymbol{b})$ uniformly over all $\boldsymbol{a}$. Note that this is equivalent to asking $\tilde{\ell}(\boldsymbol{x}^{(i)},y^{(i)})\leq\tau$ for all $1\leq i\leq n$. For any fixed $i$, using the upper bound on $\tilde{\ell}(\boldsymbol{x}^{(i)},y^{(i)})$, we have

$$ $\displaystyle\mathbb{P}\mathopen{}\mathclose{{}\left({\tilde{\ell}(\boldsymbol {x}^{(i)},y^{(i)})\geq\tau}}\right)$ $\displaystyle\leq\mathbb{P}\mathopen{}\mathclose{{}\left({\frac{L_{\sigma}^{2} }{N}\sum_{j=1}^{N}\mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}_{j}},{ \boldsymbol{x}}}\right\rangle^{2\bar{q}}+\frac{L_{\sigma}^{2}}{N}\sum_{j=1}^{N }\mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}_{j}},{\boldsymbol{x}}} \right\rangle^{2}+y^{2}\geq\frac{\tau}{2}}}\right)$ $\displaystyle\lesssim\exp\mathopen{}\mathclose{{}\left(\frac{-c\tau^{1/\bar{q} }}{L_{\sigma}^{2/\bar{q}}r_{w}^{2}}}\right)+\exp\mathopen{}\mathclose{{}\left( -c\tau^{1/p}}\right).$ $$

Consequently, by a union bound we have

$$ $\mathbb{P}\mathopen{}\mathclose{{}\left({\max_{1\leq i\leq n}\tilde{\ell}( \boldsymbol{x}^{(i)},y^{(i)})\geq\tau}}\right)\leq n\mathopen{}\mathclose{{} \left(\exp\mathopen{}\mathclose{{}\left(\frac{-c\tau^{1/\bar{q}}}{L_{\sigma}^{ 2/\bar{q}}r_{w}^{2}}}\right)+\exp\mathopen{}\mathclose{{}\left(-c\tau^{1/p}} \right)}\right).$ $$

Choosing

$$ $\tau\geq C\mathopen{}\mathclose{{}\left\{L_{\sigma}^{2}r_{w}^{2\bar{q}}\log^{ \bar{q}}\frac{n}{\delta}\lor\log^{p}\frac{n}{\delta}}\right\}$ $$

with a sufficiently large constant $C$ ensures the above probability is at most $\delta$, finishing the proof.

∎

We are now ready to present the main result of this section.

###### Proposition 22 .

Suppose Assumption 2 holds and $\sigma$ satisfies (B.1), $\Theta=\{\boldsymbol{a}:\mathopen{}\mathclose{{}\left\|{\boldsymbol{a}}}\right
\|\leq r_{a}/\sqrt{N}\}$, $\mathopen{}\mathclose{{}\left\|{\boldsymbol{w}_{i}}}\right\|\leq 1$, and $\mathopen{}\mathclose{{}\left|{b_{i}}}\right|\leq r_{b}$ for all $1\leq i\leq N$.
Let

$$ $\varkappa\coloneqq C_{\bar{q}}r_{a}^{2}L_{\sigma}^{2}(1+\varepsilon^{2\bar{q}} +r_{b}^{2\bar{q}})+C_{p},$ $$

where $C_{\bar{q}}$ and $C_{p}$ are constants depending only on $\bar{q}$ and $p$ respectively.
Then we have

$$ $\mathrm{AR}(\boldsymbol{\hat{a}},\boldsymbol{W},\boldsymbol{b})-\min_{ \boldsymbol{a}\in\Theta}\mathrm{AR}(\boldsymbol{a},\boldsymbol{W},\boldsymbol{ b})\leq\tilde{\mathcal{O}}\mathopen{}\mathclose{{}\left(\frac{\varkappa}{\sqrt {n}}}\right),$ $$

with probability at least $1-\mathcal{O}(n^{-c})$ for some constant $c>0$.

Proof.
We can summarize the generalization bound of Corollary 19 as

$$ $\mathopen{}\mathclose{{}\left|{\mathrm{AR}_{\tau}(\boldsymbol{\hat{a}}, \boldsymbol{W},\boldsymbol{b})-\widehat{\mathrm{AR}}_{\tau}(\boldsymbol{\hat{a }},\boldsymbol{W},\boldsymbol{b})}}\right|\lesssim\sqrt{\frac{\tau\varkappa}{n }}+\tau\sqrt{\frac{\log(1/\delta)}{n}},$ $$

where

$$ $\varkappa\coloneqq C_{\bar{q}}r_{a}^{2}L_{\sigma}^{2}(1+\varepsilon^{2\bar{q}} +r_{b}^{2\bar{q}})+C_{p},$ $$

is obtained from Lemma 21 by letting $r_{w}=1$. Thanks to Lemma 21, we arrive at

$$ $\mathrm{AR}(\boldsymbol{\hat{a}},\boldsymbol{W},\boldsymbol{b})-\widehat{ \mathrm{AR}}(\boldsymbol{\hat{a}},\boldsymbol{W},\boldsymbol{b})\leq\tilde{ \mathcal{O}}\mathopen{}\mathclose{{}\left(\sqrt{\frac{\tau\varkappa}{n}}+\tau \sqrt{\frac{\log(1/\delta)}{n}}+\varkappa e^{-\Omega\big{(}\frac{\tau^{1/\bar{ q}}}{L_{\sigma}^{2/\bar{q}}}\big{)}}+\varkappa e^{-\Omega\big{(}\tau^{1/p}\big {)}}}\right).$ $$

Note that $\varkappa\gtrsim L_{\sigma}^{2}$. Choosing $\tau=C\varkappa\log^{p\lor q}(\varkappa n/\delta)$ with a sufficiently large absolute constant $C>0$ satisfies the assumption of Lemma 21. By letting $\delta=n^{-c}$ for some constant $c>0$, we obtain

$$ $\mathrm{AR}(\boldsymbol{\hat{a}},\boldsymbol{W},\boldsymbol{b})-\widehat{ \mathrm{AR}}(\boldsymbol{\hat{a}},\boldsymbol{W},\boldsymbol{b})\leq\tilde{ \mathcal{O}}\mathopen{}\mathclose{{}\left(\frac{\varkappa}{\sqrt{n}}}\right),$ $$

which holds with probability at least $1-n^{-c}$ over the randomness of the training set.

Recall $\boldsymbol{a}^{*}=\operatorname*{arg\,min}_{\boldsymbol{a}\in\Theta}\mathrm{
AR}(\boldsymbol{a},\boldsymbol{W},\boldsymbol{b})$. Similarly, Lemma 21 guarantees

$$ $\widehat{\mathrm{AR}}(\boldsymbol{a}^{*},\boldsymbol{W},\boldsymbol{b})- \mathrm{AR}(\boldsymbol{a}^{*},\boldsymbol{W},\boldsymbol{b})\leq\tilde{ \mathcal{O}}\mathopen{}\mathclose{{}\left(\frac{\varkappa}{\sqrt{n}}}\right),$ $$

on the same event as above. Finally, we have $\widehat{\mathrm{AR}}(\boldsymbol{\hat{a}},\boldsymbol{W},\boldsymbol{b})\leq
\widehat{\mathrm{AR}}(\boldsymbol{a}^{*},\boldsymbol{W},\boldsymbol{b})$ by definition of $\boldsymbol{\hat{a}}$, which concludes the proof of the proposition.
∎

###### Lemma 20 .

###### Lemma 21 .

###### Proposition 22 .

## Appendix D Approximation Analysis

Let $\Pi_{\boldsymbol{U}}\boldsymbol{w}=\frac{\boldsymbol{U}^{\top}\boldsymbol{U}
\boldsymbol{w}}{\mathopen{}\mathclose{{}\left\|{\boldsymbol{U}\boldsymbol{w}}}
\right\|}$ denote the projection of $\boldsymbol{w}\in\mathbb{S}^{d-1}$ onto $\mathrm{span}(\boldsymbol{u}_{1},\ldots,\boldsymbol{u}_{k})\cap\mathbb{S}^{d-1}$ (if $\mathopen{}\mathclose{{}\left\|{\boldsymbol{U}\boldsymbol{w}}}\right\|=0$ we can simply let $\Pi_{\boldsymbol{U}}\boldsymbol{w}=\boldsymbol{u}_{1}$). Suppose $\mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}},{\boldsymbol{u}}}\right
\rangle\geq 1-\zeta$ for some $\zeta\in(0,1)$ and $\boldsymbol{u}\in\mathrm{span}(\boldsymbol{u}_{1},\ldots,\boldsymbol{u}_{k})$ with $\mathopen{}\mathclose{{}\left\|{\boldsymbol{u}}}\right\|=1$. Then, we have the following properties for this projection:

- •
$\mathopen{}\mathclose{{}\left\langle{\Pi_{\boldsymbol{U}}\boldsymbol{w}},{
\boldsymbol{u}}}\right\rangle\geq 1-\zeta$,
- •
$\mathopen{}\mathclose{{}\left\|{\boldsymbol{w}-\Pi_{\boldsymbol{U}}\boldsymbol
{w}}}\right\|\leq\sqrt{2\zeta}$.

Let $h:\mathbb{R}^{k}\to\mathbb{R}$ be the function constructed in the proof of Theorem 1. Then,

$$ $\mathrm{AR}^{*}=\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_{ \mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq\varepsilon}( h(\boldsymbol{U}(\boldsymbol{x}+\boldsymbol{\delta}))-y)^{2}}}\right].$ $$

Let us denote $f(\boldsymbol{x})=f(\boldsymbol{x};\boldsymbol{a}^{*},\boldsymbol{W},
\boldsymbol{b})$ for conciseness. Then,

$$ $\displaystyle\mathrm{AR}(\boldsymbol{a}^{*},\boldsymbol{W},\boldsymbol{b})- \mathrm{AR}^{*}$ $\displaystyle=\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_{ \mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq\varepsilon}( f(\boldsymbol{x}+\boldsymbol{\delta})-y)^{2}-\max_{\mathopen{}\mathclose{{} \left\|{\boldsymbol{\delta}}}\right\|\leq\varepsilon}(h(\boldsymbol{U}( \boldsymbol{x}+\boldsymbol{\delta}))-y)^{2}}}\right]$ $\displaystyle\leq\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_ {\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq\varepsilon} \mathopen{}\mathclose{{}\left\{(f(\boldsymbol{x}+\boldsymbol{\delta})-y)^{2}-( h(\boldsymbol{U}(\boldsymbol{x}+\boldsymbol{\delta}))-y)^{2}}\right\}}}\right]$ $\displaystyle=\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_{ \mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq\varepsilon} \mathopen{}\mathclose{{}\left\{(f(\boldsymbol{x}+\boldsymbol{\delta})-h( \boldsymbol{U}(\boldsymbol{x}+\boldsymbol{\delta}))(\underbrace{f(\boldsymbol{ x}+\boldsymbol{\delta})+h(\boldsymbol{U}(\boldsymbol{x}+\boldsymbol{\delta}))- 2y}_{\eqqcolon\mathcal{Z}})}\right\}}}\right]$ $$

Let $\Pi_{\boldsymbol{U}}\boldsymbol{W}=(\Pi_{\boldsymbol{U}}\boldsymbol{w}_{1},
\ldots,\Pi_{\boldsymbol{U}}\boldsymbol{w}_{N})^{\top}$. Then, we have the decompositions

$$ $f(\boldsymbol{x}+\boldsymbol{\delta};\boldsymbol{a}^{*},\boldsymbol{W}, \boldsymbol{b})=f(\boldsymbol{x}+\boldsymbol{\delta};\boldsymbol{a}^{*}, \boldsymbol{W},\boldsymbol{b})-f(\boldsymbol{x}+\boldsymbol{\delta}; \boldsymbol{a}^{*},\Pi_{\boldsymbol{U}}\boldsymbol{W},\boldsymbol{b})+f( \boldsymbol{x}+\boldsymbol{\delta};\boldsymbol{a}^{*},\Pi_{\boldsymbol{U}} \boldsymbol{W},\boldsymbol{b}),$ $$

and

$$ $\displaystyle\mathcal{Z}=$ $\displaystyle f(\boldsymbol{x}+\boldsymbol{\delta};\boldsymbol{a}^{*}, \boldsymbol{W},\boldsymbol{b})-f(\boldsymbol{x}+\boldsymbol{\delta}; \boldsymbol{a}^{*},\Pi_{\boldsymbol{U}}\boldsymbol{W},\boldsymbol{b})+f( \boldsymbol{x}+\boldsymbol{\delta};\boldsymbol{a}^{*},\Pi_{\boldsymbol{U}} \boldsymbol{W},\boldsymbol{b})-h(\boldsymbol{U}(\boldsymbol{x}+\boldsymbol{ \delta}))$ $\displaystyle+2h(\boldsymbol{U}(\boldsymbol{x}+\boldsymbol{\delta}))-2y.$ $$

Plugging this decomposition into the above and using the Cauchy-Schwartz inequality yields

$$ $\mathrm{AR}(\boldsymbol{a}^{*},\boldsymbol{W},\boldsymbol{b})-\mathrm{AR}^{*} \leq(\sqrt{\mathcal{E}_{1}}+\sqrt{\mathcal{E}_{2}})^{2}+\sqrt{\mathcal{E}_{3}( \mathcal{E}_{1}+\mathcal{E}_{2})},$ (D.1) $$

where

$$ $\displaystyle\mathcal{E}_{1}$ $\displaystyle\coloneqq\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{ \max_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq \varepsilon}(f(\boldsymbol{x}+\boldsymbol{\delta};\boldsymbol{a}^{*},\Pi_{ \boldsymbol{U}}\boldsymbol{W},\boldsymbol{b})-h(\boldsymbol{U}(\boldsymbol{x}+ \boldsymbol{\delta})))^{2}}}\right],$ (D.2) $\displaystyle\mathcal{E}_{2}$ $\displaystyle\coloneqq\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{ \max_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq \varepsilon}(f(\boldsymbol{x}+\boldsymbol{\delta};\boldsymbol{a}^{*},\Pi_{ \boldsymbol{U}}\boldsymbol{W},\boldsymbol{b})-f(\boldsymbol{x}+\boldsymbol{ \delta};\boldsymbol{a}^{*},\boldsymbol{W},\boldsymbol{b}))^{2}}}\right],$ (D.3) $\displaystyle\mathcal{E}_{3}$ $\displaystyle\coloneqq 4\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left [{\max_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq \varepsilon}(h(\boldsymbol{U}(\boldsymbol{x}+\boldsymbol{\delta}))-y)^{2}}} \right]=4\mathrm{AR}^{*}.$ (D.4) $$

Under Definition 3, we have a set of good neurons $S$ to work with. To continue, we introduce a similar subset of good neurons under Definition 2.

###### Definition 23 .

Suppose the weights $\boldsymbol{W}=(\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{N})^{\top}$ are obtained from the $\alpha\operatorname{-DFL}$ oracle of Definition 2. Fix a maximal $2\sqrt{2\zeta}$-packing of $\mathbb{S}^{k-1}$ with respect to the Euclidean norm, denoted by $(\bar{\boldsymbol{v}}_{i})_{i=1}^{M}$. Define $\boldsymbol{v}_{j}\coloneqq\frac{\boldsymbol{U}\boldsymbol{w}_{j}}{\mathopen{}
\mathclose{{}\left\|{\boldsymbol{U}\boldsymbol{w}_{j}}}\right\|}$ for all $j\in[N]$, and

$$ $S_{i}\coloneqq\{j\in[N]:\mathopen{}\mathclose{{}\left\|{\boldsymbol{v}_{j}- \bar{\boldsymbol{v}}_{i}}}\right\|\leq\sqrt{2\zeta}\},$ $$

for all $i\in[M]$. Note that $(S_{i})$ are mutually exclusive. Define $S\coloneqq\bigcup_{i=1}^{M}S_{i}$. By upper and lower bounds on the surface area of the spherical cap (see e.g. [, Lemma F.11]), there are constants $c_{k},C_{k}>0$ such that $c_{k}(1/\zeta)^{(k-1)/2}\leq M\leq C_{k}(1/\zeta)^{(k-1)/2}$. Therefore, using Definition 2, we have $\mathopen{}\mathclose{{}\left|{S}}\right|/N\geq\Omega(\alpha)$.

Note that when considering the $(\alpha{,}\beta)\operatorname{\!-SFL}$ oracle, we leave $S$ unchanged from Definition 3. In either case, for every $j\notin S$, we will choose $a^{*}_{j}=0$. Then, we then have the following upper bound on $\mathcal{E}_{2}$.

###### Lemma 24 .

Suppose $a^{*}_{j}=0$ for $j\notin S$ and $\mathopen{}\mathclose{{}\left\|{\boldsymbol{a}^{*}}}\right\|\leq\tilde{r}_{a}/
\sqrt{\mathopen{}\mathclose{{}\left|{S}}\right|}$. Then,

$$ $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_{\mathopen{} \mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq\varepsilon}(f( \boldsymbol{x}+\boldsymbol{\delta};\boldsymbol{a}^{*},\Pi_{\boldsymbol{U}} \boldsymbol{W},\boldsymbol{b})-f(\boldsymbol{x}+\boldsymbol{\delta}; \boldsymbol{a}^{*},\boldsymbol{W},\boldsymbol{b}))^{2}}}\right]\lesssim L_{ \sigma}^{2}C_{\bar{q}}\tilde{r}_{a}^{2}(1+r_{b}^{2(\bar{q}-1)}+\varepsilon^{2( \bar{q}-1)})(1+\varepsilon^{2})\zeta,$ $$

where $C_{\bar{q}}$ is a constant only depending on $\bar{q}$.

Proof.
To be concise, we define $\tilde{\boldsymbol{x}}_{\boldsymbol{\delta}}\coloneqq\boldsymbol{x}+
\boldsymbol{\delta}$ and hide dependence on $\boldsymbol{a}^{*}$ and $\boldsymbol{b}$ in the following notation. By pseudo-Lipschitzness of $\sigma$,

$$ $\displaystyle f(\tilde{\boldsymbol{x}}_{\boldsymbol{\delta}};\Pi_{\boldsymbol{ U}}\boldsymbol{W})-f(\tilde{\boldsymbol{x}}_{\boldsymbol{\delta}};\boldsymbol{ W})$ $\displaystyle=\sum_{j\in S}a^{*}_{j}(\sigma(\mathopen{}\mathclose{{}\left \langle{\Pi_{\boldsymbol{U}}\boldsymbol{w}_{j}},{\tilde{\boldsymbol{x}}_{ \boldsymbol{\delta}}}}\right\rangle+b_{j})-\sigma(\mathopen{}\mathclose{{} \left\langle{\boldsymbol{w}_{j}},{\tilde{\boldsymbol{x}}_{\boldsymbol{\delta}} }}\right\rangle+b_{j}))$ $\displaystyle\leq L_{\sigma}\sum_{j\in S}\mathopen{}\mathclose{{}\left|{a^{*}_ {j}}}\right|(\mathopen{}\mathclose{{}\left|{\mathopen{}\mathclose{{}\left \langle{\Pi_{\boldsymbol{U}}\boldsymbol{w}_{j}},{\tilde{\boldsymbol{x}}_{ \boldsymbol{\delta}}}}\right\rangle+b_{j}}}\right|^{\bar{q}-1}+\mathopen{} \mathclose{{}\left|{\mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}_{j}},{ \tilde{\boldsymbol{x}}_{\boldsymbol{\delta}}}}\right\rangle+b_{j}}}\right|^{ \bar{q}-1}+1)\mathopen{}\mathclose{{}\left|{\mathopen{}\mathclose{{}\left \langle{\Pi_{\boldsymbol{U}}\boldsymbol{w}_{j}-\boldsymbol{w}_{j}},{\tilde{ \boldsymbol{x}}_{\boldsymbol{\delta}}}}\right\rangle}}\right|.$ $$

Let

$$ $\mathcal{A}_{j}\coloneqq\mathopen{}\mathclose{{}\left|{\mathopen{}\mathclose{{ }\left\langle{\Pi_{\boldsymbol{U}}\boldsymbol{w}_{j}},{\tilde{\boldsymbol{x}}_ {\boldsymbol{\delta}}}}\right\rangle+b_{j}}}\right|^{\bar{q}-1}+\mathopen{} \mathclose{{}\left|{\mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}_{j}},{ \tilde{\boldsymbol{x}}_{\boldsymbol{\delta}}}}\right\rangle+b_{j}}}\right|^{ \bar{q}-1}+1,$ $$

and

$$ $\mathcal{B}_{j}\coloneqq\mathopen{}\mathclose{{}\left|{\mathopen{}\mathclose{{ }\left\langle{\Pi_{\boldsymbol{U}}\boldsymbol{w}_{j}-\boldsymbol{w}_{j}},{ \tilde{\boldsymbol{x}}_{\boldsymbol{\delta}}}}\right\rangle}}\right|.$ $$

Then by the Cauchy-Schwartz inequality,

$$ $\displaystyle\mathcal{E}_{2}\leq L_{\sigma}^{2}\operatorname{\mathbb{E}} \mathopen{}\mathclose{{}\left[{\max_{\mathopen{}\mathclose{{}\left\|{ \boldsymbol{\delta}}}\right\|\leq\varepsilon}\Big{(}\sum_{j\in S}\mathopen{} \mathclose{{}\left|{a^{*}_{j}}}\right|\mathcal{A}_{j}\mathcal{B}_{j}\Big{)}^{2 }}}\right]$ $\displaystyle\leq\frac{L_{\sigma}^{2}\tilde{r}_{a}^{2}}{\mathopen{}\mathclose{ {}\left|{{S}}}\right|}\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{ \max_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq \varepsilon}\sum_{j\in S}\mathcal{A}_{j}^{2}\mathcal{B}_{j}^{2}}}\right]$ $\displaystyle\leq\frac{L_{\sigma}^{2}\tilde{r}_{a}^{2}}{\mathopen{}\mathclose{ {}\left|{S}}\right|}\sum_{j\in S}\operatorname{\mathbb{E}}\mathopen{} \mathclose{{}\left[{\max_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}} }\right\|\leq\varepsilon}\mathcal{A}_{j}^{2}\mathcal{B}_{j}^{2}}}\right]$ $\displaystyle\leq\frac{L_{\sigma}^{2}\tilde{r}_{a}^{2}}{\mathopen{}\mathclose{ {}\left|{S}}\right|}\sum_{j\in S}\operatorname{\mathbb{E}}\mathopen{} \mathclose{{}\left[{\max_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}} }\right\|\leq\varepsilon}\mathcal{A}_{j}^{4}}}\right]^{1/2}\operatorname{ \mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_{\mathopen{}\mathclose{{}\left \|{\boldsymbol{\delta}}}\right\|\leq\varepsilon}\mathcal{B}_{j}^{4}}}\right]^{ 1/2}.$ $$

Additionally, we have

$$ $\max_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq \varepsilon}\mathcal{A}_{j}\leq C_{\bar{q}}\mathopen{}\mathclose{{}\left( \mathopen{}\mathclose{{}\left|{\mathopen{}\mathclose{{}\left\langle{\Pi_{ \boldsymbol{U}}\boldsymbol{w}_{j}},{\boldsymbol{x}}}\right\rangle}}\right|^{ \bar{q}-1}+\mathopen{}\mathclose{{}\left|{\mathopen{}\mathclose{{}\left\langle {\boldsymbol{w}_{j}},{\boldsymbol{x}}}\right\rangle}}\right|^{\bar{q}-1}+ \varepsilon^{\bar{q}-1}+r_{b}^{\bar{q}-1}+1}\right),$ $$

and

$$ $\max_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq \varepsilon}\mathcal{B}_{j}\leq\varepsilon\mathopen{}\mathclose{{}\left\|{\Pi_ {\boldsymbol{U}}\boldsymbol{w}_{j}-\boldsymbol{w}_{j}}}\right\|+\mathopen{} \mathclose{{}\left|{\mathopen{}\mathclose{{}\left\langle{\Pi_{\boldsymbol{U}} \boldsymbol{w}_{j}-\boldsymbol{w}_{j}},{\boldsymbol{x}}}\right\rangle}}\right|.$ $$

Further, by Assumption 2, for all $\boldsymbol{v}\in\mathbb{R}^{d}$, $\mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{\boldsymbol{x}}}\right\rangle$ is a centered subGaussian random variable with subGaussian norm $\mathcal{O}(\mathopen{}\mathclose{{}\left\|{\boldsymbol{v}}}\right\|)$, therefore $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{
{}\left|{\mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{\boldsymbol{x}}
}\right\rangle}}\right|^{\bar{q}}}}\right]\leq C_{\bar{q}}\mathopen{}
\mathclose{{}\left\|{\boldsymbol{v}}}\right\|^{\bar{q}}$ for all $\bar{q}>0$. In summary,

$$ $\displaystyle\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_{ \mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq\varepsilon} \mathcal{A}_{j}^{4}}}\right]^{1/2}\leq C_{\bar{q}}(1+r_{b}^{2(\bar{q}-1)}+ \varepsilon_{1}^{2(\bar{q}-1)}),$ $\displaystyle\mathrm{and}$ $\displaystyle\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_{ \mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq\varepsilon} \mathcal{B}_{j}^{4}}}\right]^{1/2}\lesssim(1+\varepsilon^{2})\zeta,$ $$

where we used the fact that $\mathopen{}\mathclose{{}\left\|{\Pi_{\boldsymbol{U}}\boldsymbol{w}_{j}-
\boldsymbol{w}_{j}}}\right\|^{2}\leq 2\zeta$ for all $j\in S$. This completes the proof.
∎

While the term $\mathcal{E}_{1}$ defined in (D.2) is an expectation over the entire distribution of $\boldsymbol{x}$, most approximation bounds support only a compact subset of $\mathbb{R}^{d}$. The following lemma shows that approximation on compact sets is sufficient to bound $\mathcal{E}_{1}$.

###### Lemma 25 .

Suppose $a^{*}_{j}=0$ for $j\notin S$ and $\mathopen{}\mathclose{{}\left\|{\boldsymbol{a}^{*}}}\right\|\leq\tilde{r}_{a}/
\sqrt{\mathopen{}\mathclose{{}\left|{S}}\right|}$. Further, suppose $r_{z}\geq 1\lor 2\varepsilon$. Let

$$ $\epsilon_{\mathrm{approx}}\coloneqq\sup_{\mathopen{}\mathclose{{}\left\|{ \boldsymbol{U}\boldsymbol{x}}}\right\|\leq r_{z}}\mathopen{}\mathclose{{}\left |{f(\boldsymbol{x};\boldsymbol{a}^{*},\Pi_{\boldsymbol{U}}\boldsymbol{W}, \boldsymbol{b})-h(\boldsymbol{U}\boldsymbol{x})}}\right|.$ $$

Assume $h$ satisfies $\mathopen{}\mathclose{{}\left|{h(\boldsymbol{z})}}\right|\leq L_{h}(1+
\mathopen{}\mathclose{{}\left\|{\boldsymbol{z}}}\right\|^{p})$ for all $\boldsymbol{z}\in\mathbb{R}^{k}$ and some constant $p\geq 0$. Then,

$$ $\mathcal{E}_{1}\leq\epsilon_{\mathrm{approx}}^{2}+\mathopen{}\mathclose{{} \left(L_{\sigma}^{2}C_{\bar{q}}\tilde{r}_{a}^{2}(1+\varepsilon^{2\bar{q}}+r_{b }^{2\bar{q}})+L_{h}^{2}C_{p,k}(1+\varepsilon^{2p})}\right)e^{-\Omega(r_{z}^{2} )}.$ $$

Proof.
For brevity, define

$$ $\Delta_{\boldsymbol{\delta}}\coloneqq\big{(}f(\tilde{\boldsymbol{x}}_{ \boldsymbol{\delta}};\boldsymbol{a}^{*},\Pi_{\boldsymbol{U}}\boldsymbol{W}, \boldsymbol{b})-h(\boldsymbol{U}(\boldsymbol{x}+\boldsymbol{\delta}))\big{)}^{2}$ $$

where $\tilde{\boldsymbol{x}}_{\boldsymbol{\delta}}\coloneqq\boldsymbol{x}+
\boldsymbol{\delta}$.
Then,

$$ $\displaystyle\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_{ \mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq\varepsilon} \Delta_{\boldsymbol{\delta}}}}\right]$ $\displaystyle\leq\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_ {\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq\varepsilon} \Delta_{\boldsymbol{\delta}}\mathbb{I}\mathopen{}\mathclose{{}\left[{\mathopen {}\mathclose{{}\left\|{\boldsymbol{U}\tilde{\boldsymbol{x}}_{\boldsymbol{ \delta}}}}\right\|\leq r_{z}}}\right]}}\right]+\operatorname{\mathbb{E}} \mathopen{}\mathclose{{}\left[{\max_{\mathopen{}\mathclose{{}\left\|{ \boldsymbol{\delta}}}\right\|\leq\varepsilon}\Delta_{\boldsymbol{\delta}} \mathbb{I}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{{}\left\|{ \boldsymbol{U}\tilde{\boldsymbol{x}}_{\boldsymbol{\delta}}}}\right\|>r_{z}}} \right]}}\right]$ $\displaystyle\leq\epsilon_{\mathrm{approx}}^{2}+\operatorname{\mathbb{E}} \mathopen{}\mathclose{{}\left[{\max_{\mathopen{}\mathclose{{}\left\|{ \boldsymbol{\delta}}}\right\|\leq\varepsilon}\Delta_{\boldsymbol{\delta}}^{2}} }\right]^{1/2}\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_{ \mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq\varepsilon} \mathbb{I}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{{}\left\|{ \boldsymbol{U}\tilde{\boldsymbol{x}}_{\boldsymbol{\delta}}}}\right\|>r_{z}}} \right]}}\right]^{1/2}$ $\displaystyle\leq\epsilon_{\mathrm{approx}}^{2}+\operatorname{\mathbb{E}} \mathopen{}\mathclose{{}\left[{\max_{\mathopen{}\mathclose{{}\left\|{ \boldsymbol{\delta}}}\right\|\leq\varepsilon}\Delta_{\boldsymbol{\delta}}^{2}} }\right]^{1/2}\mathbb{P}\mathopen{}\mathclose{{}\left({\mathopen{}\mathclose{{ }\left\|{\boldsymbol{U}\boldsymbol{x}}}\right\|>r_{z}-\varepsilon}}\right)^{1/2}$ $\displaystyle\leq\epsilon_{\mathrm{approx}}^{2}+\operatorname{\mathbb{E}} \mathopen{}\mathclose{{}\left[{\max_{\mathopen{}\mathclose{{}\left\|{ \boldsymbol{\delta}}}\right\|\leq\varepsilon}\Delta_{\boldsymbol{\delta}}^{2}} }\right]^{1/2}\mathbb{P}\mathopen{}\mathclose{{}\left({\mathopen{}\mathclose{{ }\left\|{\boldsymbol{U}\boldsymbol{x}}}\right\|>\frac{r_{z}}{2}}}\right)^{1/2}.$ $$

Furthermore, we have

$$ $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_{\mathopen{} \mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq\varepsilon}\Delta_{ \boldsymbol{\delta}}^{2}}}\right]\lesssim\operatorname{\mathbb{E}}\mathopen{} \mathclose{{}\left[{\max_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}} }\right\|\leq\varepsilon}f(\tilde{\boldsymbol{x}}_{\boldsymbol{\delta}}; \boldsymbol{a}^{*},\Pi_{\boldsymbol{U}}\boldsymbol{W},\boldsymbol{b})^{4}}} \right]+\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_{ \mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq\varepsilon}h (\boldsymbol{U}(\boldsymbol{x}+\boldsymbol{\delta}))^{4}}}\right].$ $$

Recall the notation $\boldsymbol{v}_{j}\coloneqq\frac{\boldsymbol{U}\boldsymbol{w}_{j}}{\mathopen{}
\mathclose{{}\left\|{\boldsymbol{U}\boldsymbol{w}_{j}}}\right\|}$ and $\boldsymbol{z}\coloneqq\boldsymbol{U}\boldsymbol{x}$. Then, by Cauchy-Schwartz and Jensen inequalities,

$$ $\displaystyle\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_{ \mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq\varepsilon}f (\tilde{\boldsymbol{x}}_{\boldsymbol{\delta}};\boldsymbol{a}^{*},\Pi_{ \boldsymbol{U}}\boldsymbol{W},\boldsymbol{b})^{4}}}\right]$ $\displaystyle\leq\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_ {\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq\varepsilon} \mathopen{}\mathclose{{}\left\|{\boldsymbol{a}^{*}}}\right\|^{4}\mathopen{} \mathclose{{}\left\|{\sigma(\Pi_{\boldsymbol{U}}\boldsymbol{W}(\boldsymbol{x}+ \boldsymbol{\delta})+\boldsymbol{b})}}\right\|^{4}}}\right]$ $\displaystyle\leq\frac{\tilde{r}_{a}^{4}}{\mathopen{}\mathclose{{}\left|{S}} \right|}\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_{ \mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq\varepsilon} \Big{(}\sum_{j\in S}\sigma(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{v} _{j}},{\boldsymbol{z}+\boldsymbol{U}\boldsymbol{\delta}}}\right\rangle+b_{j})^ {4}\Big{)}}}\right]$ $\displaystyle\leq\frac{\tilde{r}_{a}^{4}L_{\sigma}^{4}C_{\bar{q}}}{\mathopen{} \mathclose{{}\left|{S}}\right|}\operatorname{\mathbb{E}}\mathopen{}\mathclose{ {}\left[{\sum_{j\in S}\mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}_{j}} ,{\boldsymbol{z}}}\right\rangle^{4\bar{q}}+\varepsilon^{4\bar{q}}+r_{b}^{4\bar {q}}}}\right]$ $\displaystyle\leq C_{\bar{q}}L_{\sigma}^{4}\tilde{r}_{a}^{4}(1+\varepsilon^{4 \bar{q}}+r_{b}^{4\bar{q}}).$ $$

Similarly we can prove

$$ $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_{\mathopen{} \mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|}h(\boldsymbol{U}( \boldsymbol{x}+\boldsymbol{\delta}))^{4}}}\right]\leq C_{p,k}L_{h}^{4}(1+ \varepsilon^{4p}).$ $$

In summary,

$$ $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\max_{\mathopen{} \mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|\leq\varepsilon}\Delta_{ \boldsymbol{\delta}}^{2}}}\right]^{1/2}\lesssim C_{\bar{q}}L_{\sigma}^{2} \tilde{r}_{a}^{2}(1+\varepsilon^{2\bar{q}}+r_{b}^{2\bar{q}})+C_{p,k}L_{h}^{2}( 1+\varepsilon^{2p}).$ $$

Finally, the probability bound

$$ $\mathbb{P}\mathopen{}\mathclose{{}\left({\mathopen{}\mathclose{{}\left\|{ \boldsymbol{U}\boldsymbol{x}}}\right\|\geq\frac{r_{z}}{2}}}\right)\leq e^{- \Omega(r_{z}^{2})}$ $$

follows from subGaussianity of $\boldsymbol{x}$ and the fact that $k=\mathcal{O}(1)$.
∎

###### Definition 23 .

###### Lemma 24 .

###### Lemma 25 .

### D.1 Approximating Univariate Functions

In this section, we recall prior results on approximating univariate functions with random biases in the infinite-width regime under ReLU and polynomial activations.

###### Lemma 26 ( [ 20 , Lemma 9, Adapted] ) .

Let $\sigma$ be the ReLU activation, $a\sim\textnormal{Unif}(\{-1,+1\})$, and $b\sim\textnormal{Unif}(-r_{b},r_{b})$. Then, there exists $f:\{-1,+1\}\times[-r_{b},r_{b}]\to\mathbb{R}$, such that for all $\mathopen{}\mathclose{{}\left|{z}}\right|\leq r_{b}$ we have

$$ $\operatorname{\mathbb{E}}_{a,b}\mathopen{}\mathclose{{}\left[2r_{b}f(b)\sigma( az+b)}\right]=h(z).$ $$

Additionally, if $h$ is a polynomial of degree $s$, we have $\sup_{a,b}\mathopen{}\mathclose{{}\left|{f(a,b)}}\right|\leq r_{b}^{(s-2)\lor 0}$.

Proof.
From integration by parts, namely

$$ $\displaystyle\operatorname{\mathbb{E}}_{a,b}\mathopen{}\mathclose{{}\left[2r_{ b}(1-a)h^{\prime\prime}(b)\sigma(az+b)}\right]$ $\displaystyle=\int_{z}^{r_{b}}h^{\prime\prime}(b)(-z+b)\mathrm{d}b$ $\displaystyle=h^{\prime}(r_{b})(-z+r_{b})-\int_{z}^{r_{b}}h^{\prime}(b)\mathrm {d}b$ $\displaystyle=h^{\prime}(r_{b})(-z+r_{b})+h(z)-h(r_{b}).$ $$

Therefore, it remains to approximate the constant and linear parts. It is straightforward to verify that

$$ $\operatorname{\mathbb{E}}_{a,b}\mathopen{}\mathclose{{}\left[\frac{6b}{r_{b}^{ 2}}\cdot\sigma(az+b)}\right]=1,\quad\operatorname{\mathbb{E}}_{a,b}\mathopen{} \mathclose{{}\left[2a\sigma(az+b)}\right]=z.$ $$

Thus, we let

$$ $f(a,b)=(1-a)h^{\prime\prime}(b)+\frac{ah^{\prime}(r_{b})}{r_{b}}-\frac{3b(h^{ \prime}(r_{b})r_{b}-h(r_{b}))}{r_{b}^{3}},$ $$

which completes the proof.
∎

Furthermore, we have the following result for infinite-width approximation with polynomial activations.

###### Lemma 27 ( [ 47 , Lemma 30, Adapted] ) .

Let $\sigma$ be a polynomial of degree $q$ and suppose $b\sim\textnormal{Unif}(-r_{b},r_{b})$ and $h$ is a polynomial of degree $p$ such that $q\geq p$, and in particular satisfies $\mathopen{}\mathclose{{}\left|{h(z)}}\right|\leq L_{h}(1+\mathopen{}\mathclose
{{}\left|{z}}\right|^{p})$. Suppose $r_{b}\geq q$. Then, there exists a function $f:[-r_{b},r_{b}]\to\mathbb{R}$ such that

$$ $\operatorname{\mathbb{E}}_{b}\mathopen{}\mathclose{{}\left[2r_{b}f(b)\sigma(z+ b)}\right]=h(z),\quad\forall z\in\mathbb{R}.$ $$

Furthermore, we have $\mathopen{}\mathclose{{}\left|{f(z)}}\right|\leq C_{\sigma,h}$ for all $z$, where $C_{\sigma,h}$ only depends on the activation and $L_{h}$.

Proof.
In order for $\sigma$ to approximate arbitrary polynomials of degree at most $q$, it is sufficient to show that $\sigma$ can approximate at least one polynomial per degree, ranging from degree 0 0 to $q$. Defining the corresponding polynomial with degree $i$ as $g_{i}(z)$, then $h$ will be in the span of $\{g_{i}\}_{i=0}^{\bar{q}}$. More specifically, suppose
$h(z)=\sum_{j=0}^{p}\alpha_{j}z^{j}$, and $g_{i}(z)=\sum_{j=0}^{i}\gamma_{i,j}z^{j}$. Then there exist $\{\beta_{i}\}_{i=0}^{\bar{q}}$ such that

$$ $\sum_{i=0}^{p}\beta_{i}g_{i}(z)=\sum_{j=0}^{p}\sum_{i=j}^{p}\gamma_{i,j}\beta_ {i}z^{j}=\sum_{j=0}^{p}\alpha_{j}z^{j}.$ $$

Indeed, we can let $\beta_{i}=0$ for all $i>p$. Additionally, note that $\gamma_{i,i}\neq 0$ for all $i\leq q$ by definition. Therefore, the solution to the above equation is given iteratively by
$\beta_{p}=\alpha_{p}/\gamma_{p,p}$ and

$$ $\beta_{p-j}=\frac{\alpha_{p-j}-\sum_{i=0}^{j-1}\gamma_{p-i,p-j}\beta_{p-i}}{ \gamma_{p-j,p-j}},$ $$

for $1\leq j\leq p$. Importantly, $\mathopen{}\mathclose{{}\left|{\beta_{i}}}\right|$ for all $i$ can be bounded polynomially by $\{\alpha_{j}\}_{j}$, $\{\gamma_{i,j}\}_{i,j}$ and $\{\gamma^{-1}_{i,i}\}_{i}$. Further, $\mathopen{}\mathclose{{}\left|{\alpha_{i}}}\right|$ can be bounded polynomially by $L_{h}$ for all $i$. Thus, it remains to construct $\{g_{i}\}$.

Following [], we define

$$ $g_{q}(z)=\int_{-q}^{0}\sigma(z+b)\mathrm{d}b.$ $$

It is straightforward to verify that $g_{q}$ has degree (exactly) $q$. We then iteratively define

$$ $g_{q-i}(z)=g_{q-(i-1)}(z+1)-g_{q-(i-1)}(z),\quad\forall\,1\leq i\leq q.$ $$

Using the definition above and by induction, one can verify $g_{i}$ has degree exactly $i$. Furthermore, expanding the definition above yields

$$ $g_{q-i}(z)=\sum_{j=0}^{i}c_{i,j}g_{q}(z+j)=\sum_{j=0}^{i}c_{i,j}\int_{-q}^{0} \sigma(z+b+j)\mathrm{d}b,$ $$

where $c_{i,j}=(-1)^{i-j}\binom{i}{j}$, i.e. the coefficients that satisfy $(z-1)^{i}=\sum_{j=0}^{i}c_{i,j}z^{j}$. In particular, we can write

$$ $g_{q-i}(z)=\sum_{j=0}^{i}c_{i,j}\int_{-q+j}^{j}\sigma(z+b)\mathrm{d}b= \operatorname{\mathbb{E}}_{b}\mathopen{}\mathclose{{}\left[2r_{b}\sum_{j=0}^{i }\mathbb{I}\mathopen{}\mathclose{{}\left[{-q+j\leq b\leq j}}\right]\sigma(z+b) }\right].$ $$

Therefore, we can define

$$ $f(b)\coloneqq\sum_{i=0}^{\bar{q}}\beta_{q-i}\sum_{j=0}^{i}c_{i,j}\mathbb{I} \mathopen{}\mathclose{{}\left[{-q+j\leq b\leq j}}\right],$ $$

which completes the proof.
∎

###### Lemma 26 ( [ 20 , Lemma 9, Adapted] ) .

###### Lemma 27 ( [ 47 , Lemma 30, Adapted] ) .

### D.2 Approximating Multivariate Polynomials

We adapt the approximation result of this section from [], modifying the proof to be consistent with our assumption on the first layer weights.

First, we remark that for any fixed $\boldsymbol{v}\in\mathbb{S}^{k-1}$ and any degree $0\leq s\leq p$, we can approximate the function $\boldsymbol{z}\mapsto\mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{
\boldsymbol{z}}}\right\rangle^{s}$ with random biases as established by Lemma 26 for the ReLU activation and Lemma 27 for the polynomial activation. Therefore, our main effort will be spent in approximating a polynomial $h(\boldsymbol{z})$ using monomials $\mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{\boldsymbol{z}}}\right
\rangle^{s}$. Note that we can represent $h$ by

$$ $h(\boldsymbol{z})=\sum_{s=0}^{p}\boldsymbol{T}^{(s)}[\boldsymbol{z}^{\otimes s }],$ $$

where $\boldsymbol{T}^{(s)}$ is a symmetric tensor of order $s$, and we use the notation

$$ $\boldsymbol{T}^{(s)}[\boldsymbol{z}^{\otimes s}]=\mathrm{vec}(\boldsymbol{T}^{ (s)})^{\top}\mathrm{vec}(\boldsymbol{z}^{\otimes s})=\sum_{i_{1},\ldots,i_{s}= 1}^{k}\boldsymbol{T}^{(s)}_{i_{1},\ldots,i_{s}}\boldsymbol{z}_{i_{1}}\ldots \boldsymbol{z}_{i_{s}}.$ $$

The approximation result relies on the following fact.

###### Lemma 28 .

Let $\boldsymbol{v}\sim\tau_{k}$. Then, the matrix $\operatorname{\mathbb{E}}_{\boldsymbol{v}\sim\tau_{k}}\mathopen{}\mathclose{{}
\left[\mathrm{vec}(\boldsymbol{v}^{\otimes s})\mathrm{vec}(\boldsymbol{v}^{
\otimes s})^{\top}}\right]$ is invertible.

Proof.
Let $\boldsymbol{T}$ be an arbitrary symmetric tensor of order $s$ with $\mathopen{}\mathclose{{}\left\|{\boldsymbol{T}}}\right\|_{\mathrm{F}}=1$. We need to find a constant $c_{s,k}>0$ such that

$$ $\mathrm{vec}(\boldsymbol{T})^{\top}\operatorname{\mathbb{E}}_{\boldsymbol{v} \sim\tau_{k}}\mathopen{}\mathclose{{}\left[\mathrm{vec}(\boldsymbol{v}^{ \otimes s})\mathrm{vec}(\boldsymbol{v}^{\otimes s})}\right]\mathrm{vec}( \boldsymbol{T})\geq c_{s,k}.$ $$

Note that

$$ $\mathrm{vec}(\boldsymbol{T})^{\top}\operatorname{\mathbb{E}}_{\boldsymbol{v} \sim\tau_{k}}\mathopen{}\mathclose{{}\left[\mathrm{vec}(\boldsymbol{v}^{ \otimes s})\mathrm{vec}(\boldsymbol{v}^{\otimes s})}\right]\mathrm{vec}( \boldsymbol{T})=\operatorname{\mathbb{E}}_{\boldsymbol{v}\sim\tau_{k}} \mathopen{}\mathclose{{}\left[\boldsymbol{T}[\boldsymbol{v}^{\otimes s}]^{2}} \right]=\operatorname{\mathbb{E}}_{\boldsymbol{w}\sim\mathcal{N}(0,\mathbf{I}_ {k})}\mathopen{}\mathclose{{}\left[\frac{\boldsymbol{T}[\boldsymbol{w}^{ \otimes s}]^{2}}{\mathopen{}\mathclose{{}\left\|{\boldsymbol{w}}}\right\|^{2s} }}\right].$ $$

Furthermore, [, Lemma 23] implies that

$$ $\operatorname{\mathbb{E}}_{\boldsymbol{w}\sim\mathcal{N}(0,\mathbf{I}_{k})} \mathopen{}\mathclose{{}\left[\boldsymbol{T}[\boldsymbol{w}^{\otimes s}]^{2}} \right]\geq c^{\prime}_{s,k},$ $$

for some constant $c^{\prime}_{s,k}>0$. Therefore, for any $r>0$, we have

$$ $\operatorname{\mathbb{E}}_{\boldsymbol{w}\sim\mathcal{N}(0,\mathbf{I}_{k})} \mathopen{}\mathclose{{}\left[\boldsymbol{T}[\boldsymbol{w}^{\otimes s}]^{2} \mathbb{I}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{{}\left\|{ \boldsymbol{w}}}\right\|>r}}\right]}\right]+\operatorname{\mathbb{E}}_{ \boldsymbol{w}\sim\mathcal{N}(0,\mathbf{I}_{k})}\mathopen{}\mathclose{{}\left[ \boldsymbol{T}[\boldsymbol{w}^{\otimes s}]^{2}\mathbb{I}\mathopen{}\mathclose{ {}\left[{\mathopen{}\mathclose{{}\left\|{\boldsymbol{w}}}\right\|\leq r}} \right]}\right]\geq c^{\prime}_{s,k}.$ $$

Note that the first term on the LHS above can become arbitrarily small by choosing $r$ sufficiently large (depending on $s$ and $k$). Thus for sufficiently large $r$ we have

$$ $\operatorname{\mathbb{E}}_{\boldsymbol{w}\sim\mathcal{N}(0,\mathbf{I}_{k})} \mathopen{}\mathclose{{}\left[\boldsymbol{T}[\boldsymbol{w}^{\otimes s}]^{2} \mathbb{I}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{{}\left\|{ \boldsymbol{w}}}\right\|\leq r}}\right]}\right]\geq\frac{c^{\prime}_{s,k}}{2}.$ $$

Finally, we have

$$ $\operatorname{\mathbb{E}}_{\boldsymbol{w}\sim\mathcal{N}(0,\mathbf{I}_{k})} \mathopen{}\mathclose{{}\left[\frac{\boldsymbol{T}[\boldsymbol{w}^{\otimes s}] ^{2}}{\mathopen{}\mathclose{{}\left\|{\boldsymbol{w}}}\right\|^{2s}}}\right] \geq\frac{1}{r^{2s}}\operatorname{\mathbb{E}}_{\boldsymbol{w}\sim\mathcal{N}(0 ,\mathbf{I}_{k})}\mathopen{}\mathclose{{}\left[\boldsymbol{T}[\boldsymbol{w}^{ \otimes s}]^{2}\mathbb{I}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{ {}\left\|{\boldsymbol{w}}}\right\|\leq r}}\right]}\right]\geq\frac{c^{\prime}_ {s,k}}{2r^{2s}}.$ $$

Therefore, taking $c_{s,k}=\frac{c^{\prime}_{s,k}}{2r^{2s}}$ completes the proof.
∎

The following lemma establishes how we can use monomials of the form $(\boldsymbol{v}^{\top}\boldsymbol{z})^{s}$ to approximate each term appearing in $h(\boldsymbol{z})$.

###### Lemma 29 ( [ 20 , Corollary 4, Adapted] ) .

There exists $f:\mathbb{S}^{k-1}\to\mathbb{R}$ such that for all $\boldsymbol{z}\in\mathbb{R}^{k}$ and non-negative integers $s\geq 0$,

$$ $\int_{\mathbb{S}^{k-1}}f(\boldsymbol{v})\mathopen{}\mathclose{{}\left\langle{ \boldsymbol{v}},{\boldsymbol{z}}}\right\rangle^{s}\mathrm{d}\tau_{k}( \boldsymbol{v})=\boldsymbol{T}^{(s)}[\boldsymbol{z}^{\otimes s}].$ $$

Further, $\mathopen{}\mathclose{{}\left|{f(\boldsymbol{v})}}\right|\leq C_{k,s}\mathopen
{}\mathclose{{}\left\|{\boldsymbol{T}^{(s)}}}\right\|_{\mathrm{F}}$ for all $\boldsymbol{v}\in\mathbb{S}^{k-1}$.

Proof.
Note that by definition, $\mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{\boldsymbol{z}}}\right
\rangle^{s}=\mathrm{vec}(\boldsymbol{v}^{\otimes s})^{\top}\mathrm{vec}(
\boldsymbol{z}^{\otimes s})$. Therefore,

$$ $\int f(\boldsymbol{v})\mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{ \boldsymbol{z}}}\right\rangle^{s}\mathrm{d}\tau_{k}(\boldsymbol{v})=\mathopen{ }\mathclose{{}\left(\int f(\boldsymbol{v})\mathrm{vec}(\boldsymbol{v}^{\otimes s })\mathrm{d}\tau_{k}(\boldsymbol{v})}\right)^{\top}\mathrm{vec}(\boldsymbol{z} ^{\otimes s}).$ $$

We need to match the first vector on the RHS above with $\mathrm{vec}(\boldsymbol{T}^{\otimes s})$, thus our choice of $f$ is

$$ $f(\boldsymbol{v})=\mathrm{vec}(\boldsymbol{v}^{\otimes s})^{\top}\operatorname {\mathbb{E}}_{\boldsymbol{v}\sim\tau_{k}}\mathopen{}\mathclose{{}\left[\mathrm {vec}(\boldsymbol{v}^{\otimes s})\mathrm{vec}(\boldsymbol{v}^{\otimes s})^{ \top}}\right]^{-1}\mathrm{vec}(\boldsymbol{T}^{(s)}).$ $$

The proof is then completed via the lower bound of Lemma 28 which gaurantees the existence of some constant $c_{s,k}>0$ such that
$\lambda_{\mathrm{min}}\mathopen{}\mathclose{{}\left({\operatorname{\mathbb{E}}
_{\boldsymbol{v}\sim\tau_{k}}\mathopen{}\mathclose{{}\left[\mathrm{vec}(
\boldsymbol{v}^{\otimes s})\mathrm{vec}(\boldsymbol{v}^{\otimes s})^{\top}}
\right]}}\right)\geq c_{s,k}$.
∎

The above result along with the univariate approximations proved earlier immediately yields the following corollary.

###### Corollary 30 .

Suppose $h$ is a polynomial of degree $p$ denoted by $h(\boldsymbol{z})=\sum_{s=0}^{p}\boldsymbol{T}^{(s)}[\boldsymbol{z}^{\otimes s}]$. Further assume the activation $\sigma$ is either ReLU or a polynomial of degree $q\geq p$. Then, there exists $\hat{h}:\mathbb{S}^{k-1}\times[-r_{b},r_{b}]\to\mathbb{R}$ such that for every $\mathopen{}\mathclose{{}\left\|{\boldsymbol{z}}}\right\|\leq r_{b}$, we have

$$ $\int_{\mathbb{S}^{k-1}\times[-r_{b},r_{b}]}\hat{h}(\boldsymbol{v},b)\sigma( \mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{\boldsymbol{z}}}\right \rangle+b)\mathrm{d}\tau_{k}(\boldsymbol{v})\mathrm{d}b=h(\boldsymbol{z}).$ $$

Furthermore, $\mathopen{}\mathclose{{}\left|{\hat{h}(\boldsymbol{v},b)}}\right|\leq C_{k,q}
\max_{s\leq p}\mathopen{}\mathclose{{}\left\|{\boldsymbol{T}^{(s)}}}\right\|_{
\mathrm{F}}$ for the polynomial activation and $\mathopen{}\mathclose{{}\left|{\hat{h}(\boldsymbol{v},b)}}\right|\leq C_{k}r_{
b}^{(p-2)\lor 0}\mathopen{}\mathclose{{}\left\|{\boldsymbol{T}^{(s)}}}\right\|
_{\mathrm{F}}$ for the ReLU activation.

Proof.
First, we consider the case where we use polynomial activations. Let

$$ $\hat{h}(\boldsymbol{v},b)=\sum_{s=0}^{p}f_{1,s}(\boldsymbol{v})f_{2,s}(b),$ $$

for $(f_{1,s})$ and $(f_{2,s})$ which we now determine. We choose $f_{2,s}$ according to and Lemma 27, then

$$ $\int_{b=-r_{b}}^{r_{b}}f_{2,s}(b)\sigma(\mathopen{}\mathclose{{}\left\langle{ \boldsymbol{v}},{\boldsymbol{z}}}\right\rangle+b)\mathrm{d}b=\mathopen{} \mathclose{{}\left\langle{\boldsymbol{v}},{\boldsymbol{z}}}\right\rangle^{s},$ $$

for all $\mathopen{}\mathclose{{}\left\|{\boldsymbol{z}}}\right\|\leq r_{b}/2$, and $\mathopen{}\mathclose{{}\left|{f_{2,s}(b)}}\right|\leq C_{s,q}$ for all $b$. Then, we choose $f_{1,s}$ according to Lemma 29, which yields

$$ $\int_{\mathbb{S}^{k-1}\times[-r_{b},r_{b}]}f_{1,s}(\boldsymbol{v})f_{2,s}(b) \sigma(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{\boldsymbol{z}}} \right\rangle+b)\mathrm{d}\tau_{k}(\boldsymbol{v})\mathrm{d}b=\int f_{1,s}( \boldsymbol{v})\mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{ \boldsymbol{z}}}\right\rangle^{s}\mathrm{d}\tau_{k}(\boldsymbol{v})= \boldsymbol{T}^{(s)}[\boldsymbol{z}^{\otimes s}],$ $$

for all $\mathopen{}\mathclose{{}\left\|{\boldsymbol{z}}}\right\|\leq r_{b}/2$. Additionally $\mathopen{}\mathclose{{}\left|{f_{1,s}(\boldsymbol{v})}}\right|\leq C_{s,k}
\mathopen{}\mathclose{{}\left\|{\boldsymbol{T}^{(s)}}}\right\|_{\mathrm{F}}$, which completes the proof of the polynomial activation case.

Now, consider the case where we use the ReLU activation. Let

$$ $\hat{h}(\boldsymbol{v},b)=\sum_{s=0}^{p}g_{s}(\boldsymbol{v},b).$ $$

where

$$ $g_{s}(\boldsymbol{v},b)=\frac{1}{2}f_{1,s}(\boldsymbol{v})\tilde{f}_{2,s}(1,b) +\frac{1}{2}f_{1,s}(-\boldsymbol{v})\tilde{f}_{2,s}(-1,b)$ $$

with $f_{1,s}$ given above and $\tilde{f}_{2,s}$ introduced below.
Since $\boldsymbol{v}$ and $-\boldsymbol{v}$ have the same distribution, we have

$$ $\displaystyle\int g_{s}(\boldsymbol{v},b)\sigma(\mathopen{}\mathclose{{}\left \langle{\boldsymbol{v}},{\boldsymbol{z}}}\right\rangle)\mathrm{d}b\,\mathrm{d} \tau_{k}(\boldsymbol{v})$ $\displaystyle=\int\frac{1}{2}\mathopen{}\mathclose{{}\left(f_{1,s}(\boldsymbol {v})\tilde{f}_{2,s}(1,b)+f_{1,s}(-\boldsymbol{v})\tilde{f}_{2,s}(-1,b)}\right) \sigma(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{\boldsymbol{z}}} \right\rangle\mathrm{d}b\,\mathrm{d}\tau_{k}(\boldsymbol{v})$ $\displaystyle=\int_{\mathbb{S}^{d-1}}f_{1,s}(\boldsymbol{v})\frac{1}{2} \mathopen{}\mathclose{{}\left\{\int_{b=-r_{b}}^{r_{b}}\tilde{f}_{2,s}(1,b) \sigma(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{\boldsymbol{z}}} \right\rangle+b)+\tilde{f}_{2,s}(-1,b)\sigma(-\mathopen{}\mathclose{{}\left \langle{\boldsymbol{v}},{\boldsymbol{z}}}\right\rangle+b)\mathrm{d}b}\right\} \mathrm{d}\tau_{k}(\boldsymbol{v})$ $\displaystyle=\int f_{1,s}(\boldsymbol{v})\mathopen{}\mathclose{{}\left\langle {\boldsymbol{v}},{\boldsymbol{z}}}\right\rangle^{s}\mathrm{d}\tau_{k}( \boldsymbol{v})=\boldsymbol{T}^{(s)}[\boldsymbol{z}^{\otimes s}].$ $$

As a result, it suffices to choose $\tilde{f}_{2,s}$ according to Lemma 26, which completes the proof of the corollary.

∎

As a last step in this section, we verify that one can indeed control $\max_{s\leq p}\mathopen{}\mathclose{{}\left\|{\boldsymbol{T}^{(s)}}}\right\|_{
\mathrm{F}}$ with an absolute constant when $h$ is the minimizer of the adversarial risk.

###### Lemma 31 .

Suppose $\mathcal{F}$ is the class of degree $p$ polynomials on $\mathbb{R}^{d}$. Let $\mathcal{H}=\{\boldsymbol{z}\mapsto\operatorname{\mathbb{E}}\mathopen{}
\mathclose{{}\left[{f(\boldsymbol{x})\,|\,\boldsymbol{U}\boldsymbol{x}=
\boldsymbol{z}}}\right]\,:\,f\in\mathcal{F}\}$, and define

$$ $h=\operatorname*{arg\,min}_{h^{\prime}\in\mathcal{H}}\operatorname{\mathbb{E}} \mathopen{}\mathclose{{}\left[{\max_{\mathopen{}\mathclose{{}\left\|{ \boldsymbol{\delta}}}\right\|\leq\varepsilon}(h^{\prime}(\boldsymbol{U}( \boldsymbol{x}+\boldsymbol{\delta}))-y)^{2}}}\right].$ $$

Denote the decomposition of $h$ by $h(\boldsymbol{z})=\sum_{s=0}^{p}\boldsymbol{T}^{(s)}[\boldsymbol{z}^{\otimes s}]$. Then, $\mathopen{}\mathclose{{}\left\|{\boldsymbol{T}^{(s)}}}\right\|_{\mathrm{F}}
\leq C_{k,y}$, where $C_{k,y}$ is a constant depending only on $k$ and the target second moment $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{y^{2}}}\right]$ (thus an absolute constant in our setting). As a consequence, we have $\mathopen{}\mathclose{{}\left|{h(\boldsymbol{z})}}\right|\leq L_{h}(1+
\mathopen{}\mathclose{{}\left\|{\boldsymbol{z}}}\right\|^{p})$ for all $\boldsymbol{z}\in\mathbb{R}^{k}$, where $L_{h}>0$ is an absolute constant.

Proof.
By comparing with the zero function, we have

$$ $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{(h(\boldsymbol{U} \boldsymbol{x})-y)^{2}}}\right]\leq\operatorname{\mathbb{E}}\mathopen{} \mathclose{{}\left[{\max_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}} }\right\|\leq\varepsilon}(h(\boldsymbol{U}(\boldsymbol{x}+\boldsymbol{\delta}) )-y)^{2}}}\right]\leq\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{y ^{2}}}\right].$ $$

Furthermore, by the Cauchy-Schwartz inequality,

$$ $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{(h(\boldsymbol{U} \boldsymbol{x})-y)^{2}}}\right]\geq\operatorname{\mathbb{E}}\mathopen{} \mathclose{{}\left[{h(\boldsymbol{U}\boldsymbol{x})^{2}}}\right]+\operatorname {\mathbb{E}}\mathopen{}\mathclose{{}\left[{y^{2}}}\right]-2\operatorname{ \mathbb{E}}\mathopen{}\mathclose{{}\left[{h(\boldsymbol{U}\boldsymbol{x})^{2}} }\right]^{1/2}\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{y^{2}}} \right]^{1/2}.$ $$

Combining the two inequalities above, we obtain $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{h(\boldsymbol{U}
\boldsymbol{x})^{2}}}\right]\leq 4\operatorname{\mathbb{E}}\mathopen{}
\mathclose{{}\left[{y^{2}}}\right]$. Let $\boldsymbol{z}\coloneqq\boldsymbol{U}\boldsymbol{x}$, and let $\mu_{\boldsymbol{z}}$ be the marginal distribution of $\boldsymbol{z}$. Then

$$ $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{h(\boldsymbol{z})^{2}} }\right]=\int h(\boldsymbol{z})^{2}\frac{\mathrm{d}\mu_{\boldsymbol{z}}}{ \mathrm{d}\mathcal{N}(0,C_{k}\mathbf{I}_{k})}(\boldsymbol{z})\mathrm{d} \mathcal{N}(0,C_{k}\mathbf{I}_{k})(\boldsymbol{z}).$ $$

Further, by subGaussianity of $\boldsymbol{x}$ and subsequent subGaussianity of $\boldsymbol{z}$, we have $\frac{\mathrm{d}\mu_{\boldsymbol{z}}}{\mathrm{d}\mathcal{N}(0,C_{k})}(
\boldsymbol{z})\leq C^{\prime}_{k}<\infty$ for all $\boldsymbol{z}$, when $C_{k},C^{\prime}_{k}$ are sufficiently large constants depending only on $k$. Therefore,

$$ $\operatorname{\mathbb{E}}_{\boldsymbol{z}\sim\mathcal{N}(0,C_{k}\mathbf{I}_{k} )}\mathopen{}\mathclose{{}\left[h(\boldsymbol{z})^{2}}\right]\leq 4C^{\prime}_ {k}\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{y^{2}}}\right].$ $$

The proof is completed by using the Hermite decomposition of $h$.
∎

###### Lemma 28 .

###### Lemma 29 ( [ 20 , Corollary 4, Adapted] ) .

###### Corollary 30 .

###### Lemma 31 .

### D.3 Approximating Multivariate Pseudo-Lipschitz Functions

We now turn to the more general problem of approximating pseudo-Lipschitz functions. Specifically, when $\mathcal{F}$ satisfies Assumption 3, functions of the form $h(\boldsymbol{z})=\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{f(
\boldsymbol{x})\,|\,\boldsymbol{U}\boldsymbol{x}=\boldsymbol{z}}}\right]$ will be $L$-pseudo-Lipschitz. The following lemma investigates approximating such functions with infinite-width two-layer neural networks.

###### Lemma 32 .

Suppose $h:\mathbb{R}^{k}\to\mathbb{R}$ is $L$-Lipschitz on $\mathopen{}\mathclose{{}\left\|{\boldsymbol{z}}}\right\|\leq r_{z}$ and $\sigma$ is the ReLU activation. Then, for every $\Delta\geq C_{k}$, there exists $\hat{h}:\mathbb{S}^{k-1}\times[-r_{b},r_{b}]\to\mathbb{R}$ such that

$$ $\mathopen{}\mathclose{{}\left|{h(\boldsymbol{z})-\int_{\mathbb{S}^{k-1}\times[ -r_{b},r_{b}]}\hat{h}(\boldsymbol{v},b)\sigma(\mathopen{}\mathclose{{}\left \langle{\boldsymbol{v}},{\boldsymbol{z}}}\right\rangle+b)\mathrm{d}\tau_{k}( \boldsymbol{v})\mathrm{d}b}}\right|\leq C_{k}Lr_{z}\mathopen{}\mathclose{{} \left\{\Big{(}\frac{\Delta}{Lr_{z}}\Big{)}^{\frac{-2}{k+1}}\log\frac{\Delta}{ Lr_{z}}+\big{(}\frac{\Delta}{r_{z}}\big{)}^{\frac{2k}{k+1}}\big{(}\frac{r_{z}} {r_{b}}\big{)}^{k}}\right\},$ $$

for all $\mathopen{}\mathclose{{}\left\|{\boldsymbol{z}}}\right\|\leq r_{z}$. Furthermore, we have $\mathopen{}\mathclose{{}\left|{\hat{h}(\boldsymbol{v},b)}}\right|\leq C_{k}L(
\Delta/Lr_{z})^{2k/(k+1)}/r_{z}$ for all $\boldsymbol{v}$ and $b$, and

$$ $\int_{\mathbb{S}^{k-1}\times[-r_{b},r_{b}]}\hat{h}(\boldsymbol{v},b)^{2} \mathrm{d}\tau_{k}(\boldsymbol{v})\mathrm{d}b\leq\frac{C_{k}\Delta^{2}}{r_{z}^ {3}}.$ $$

Proof.
Let $\tilde{\boldsymbol{z}}\coloneqq(\boldsymbol{z}^{\top},r_{z})^{\top}\in\mathbb{
R}^{k+1}$. By [, Proposition 6], we know that for all $\Delta\geq C_{k}$, there exists $p:\mathbb{S}^{k}\to\mathbb{R}$, such that $\mathopen{}\mathclose{{}\left\|{p}}\right\|_{L^{2}(\tau_{k+1})}\leq\Delta$ and

$$ $\mathopen{}\mathclose{{}\left|{h(\boldsymbol{z})-\int_{\mathbb{S}^{k}}p(\tilde {\boldsymbol{v}})\sigma\Big{(}\frac{\mathopen{}\mathclose{{}\left\langle{ \tilde{\boldsymbol{v}}},{\tilde{\boldsymbol{z}}}}\right\rangle}{r_{z}}\Big{)} \mathrm{d}\tau_{k+1}(\tilde{\boldsymbol{v}})}}\right|\leq C_{k}Lr_{z}\Big{(} \frac{\Delta}{Lr_{z}}\Big{)}^{\frac{-2}{k+1}}\log\frac{\Delta}{Lr_{z}},$ $$

for all $\mathopen{}\mathclose{{}\left\|{\boldsymbol{z}}}\right\|\leq r_{z}$. Furthermore, the proof of [, Proposition 19] demonstrated that

$$ $\mathopen{}\mathclose{{}\left|{p(\tilde{\boldsymbol{v}})}}\right|\leq C_{k}Lr_ {z}\Big{(}\frac{\Delta}{Lr_{z}}\Big{)}^{\frac{2k}{k+1}},\quad\forall\,\tilde{ \boldsymbol{v}}\in\mathbb{S}^{k}.$ $$

Let $\tilde{\boldsymbol{v}}=(\tilde{\boldsymbol{v}}_{1:k}^{\top},\tilde{v}_{k+1})^{\top}$ be the decomposition of $\tilde{\boldsymbol{v}}$ into its first $k$ and last coordinate. Then, we will use the fact that for $\tilde{\boldsymbol{v}}\sim\textnormal{Unif}(\mathbb{S}^{k})$ when conditioned on $\tilde{v}_{k+1}$, by symmetry $\frac{\boldsymbol{v}_{1:k}}{\mathopen{}\mathclose{{}\left\|{\boldsymbol{v}_{1:
k}}}\right\|}$ is uniformly distributed on $\mathbb{S}^{k-1}$.
In other words, let $\boldsymbol{v}\sim\textnormal{Unif}(\mathbb{S}^{k-1})$ and $\tilde{b}\sim\rho_{k+1}$ independently, where we choose $\rho_{k+1}$ such that $\frac{\tilde{b}}{\sqrt{1+\tilde{b}^{2}}}$ has the same marginal distribution as $\tilde{v}_{k+1}$.
Since the marginal distribution of $\tilde{v}_{k+1}$ is given by $\mathrm{d}\mathbb{P}(\tilde{v}_{k+1})\propto(1-\tilde{v}^{2}_{k+1})^{(k-2)/2}
\mathrm{d}\tilde{v}_{k+1}$, we have $\rho_{k+1}(\tilde{b})=Z_{k}(1+\tilde{b}^{2})^{-(k+1)/2}$, where $Z_{k}$ is the normalizing constant.
Then, $\tilde{\boldsymbol{v}}=\mathrm{T}(\boldsymbol{v},\tilde{b})$ is distributed uniformly on $\mathbb{S}^{k}$, where $\mathrm{T}:\mathbb{S}^{k-1}\times\mathbb{R}\to\mathbb{S}^{k}$ is given by $\mathrm{T}(\boldsymbol{v},\tilde{b})=\frac{1}{\sqrt{1+\tilde{b}^{2}}}\big{(}
\boldsymbol{v}^{\top},\tilde{b}\big{)}$. As a result,

$$ $\displaystyle\int p(\tilde{\boldsymbol{v}})\sigma\Big{(}\frac{\mathopen{} \mathclose{{}\left\langle{\tilde{\boldsymbol{v}}},{\tilde{\boldsymbol{z}}}} \right\rangle}{r_{z}}\Big{)}\mathrm{d}\tau_{k+1}(\tilde{\boldsymbol{v}})$ $\displaystyle=\int p(\mathrm{T}(\boldsymbol{v},\tilde{b}))\sigma\Big{(}\frac{ \mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{\boldsymbol{z}}}\right \rangle+\tilde{b}r_{z}}{r_{z}\sqrt{1+\tilde{b}^{2}}}\Big{)}\mathrm{d}\tau_{k}( \boldsymbol{v})\mathrm{d}\rho_{k+1}(\tilde{b})$ $\displaystyle=Z_{k}\int_{\mathbb{S}^{k-1}\times\mathbb{R}}\frac{p(\mathrm{T}( \boldsymbol{v},\tilde{b}))}{r_{z}\sqrt{1+\tilde{b}^{2}}}\cdot\frac{1}{(1+ \tilde{b}^{2})^{(k+1)/2}}\sigma(\mathopen{}\mathclose{{}\left\langle{ \boldsymbol{v}},{\boldsymbol{z}}}\right\rangle+\tilde{b}r_{z})\mathrm{d}\tau_{ k}(\boldsymbol{v})\mathrm{d}\tilde{b}$ $\displaystyle=Z_{k}\int_{\mathbb{S}^{k-1}\times\mathbb{R}}\frac{r_{z}^{k}p( \mathrm{T}(\boldsymbol{v},b/r_{z}))}{(r_{z}^{2}+b^{2})^{(k+2)/2}}\sigma( \mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{\boldsymbol{z}}}\right \rangle+b)\mathrm{d}\tau_{k}(\boldsymbol{v})\mathrm{d}b.$ $$

Therefore, our choice of $\hat{h}$ will be

$$ $\hat{h}(\boldsymbol{v},b)=Z_{k}\frac{r^{k}_{z}p(\mathrm{T}(\boldsymbol{v},b/r_ {z}))}{(r_{z}^{2}+b^{2})^{(k+2)/2}}.$ $$

Next, we bound the following error term due to cutoff of bias,

$$ $\mathcal{E}\coloneqq Z_{k}\mathopen{}\mathclose{{}\left|{\int_{\mathbb{S}^{k-1 }\times(\mathbb{R}\setminus[-r_{b},r_{b}])}\frac{r_{z}^{k}p(\mathrm{T}( \boldsymbol{v},b/r_{z}))}{(r_{z}^{2}+b^{2})^{(k+2)/2}}\sigma(\mathopen{} \mathclose{{}\left\langle{\boldsymbol{v}},{\boldsymbol{z}}}\right\rangle+b) \mathrm{d}\tau_{k}(\boldsymbol{v})\mathrm{d}b}}\right|.$ $$

We have

$$ $\displaystyle\mathcal{E}$ $\displaystyle\lesssim C_{k}Lr_{z}\big{(}\frac{\Delta}{Lr_{z}}\big{)}^{\frac{2k }{k+1}}\int_{\mathopen{}\mathclose{{}\left|{b}}\right|>r_{b}}\frac{r_{z}^{k}(r _{z}+\mathopen{}\mathclose{{}\left|{b}}\right|)}{(r_{z}^{2}+b^{2})^{(k+2)/2}} \mathrm{d}b$ $\displaystyle\lesssim C_{k}Lr_{z}\big{(}\frac{\Delta}{Lr_{z}}\big{)}^{\frac{2k }{k+1}}\int_{\mathopen{}\mathclose{{}\left|{b}}\right|>r_{b}}\frac{r_{z}^{k}}{ (r_{z}^{2}+b^{2})^{(k+1)/2}}\mathrm{d}b$ $\displaystyle\lesssim C_{k}\Delta^{\frac{2k}{k+1}}\int_{\mathopen{}\mathclose{ {}\left|{b}}\right|>r_{b}}\frac{r_{z}^{k}}{b^{k+1}}\mathrm{d}b$ $\displaystyle\lesssim C_{k}Lr_{z}\big{(}\frac{\Delta}{r_{z}}\big{)}^{\frac{2k} {k+1}}\big{(}\frac{r_{z}}{r_{b}}\big{)}^{k}.$ $$

Finally, we prove the guarantees provided for $\hat{h}$. The uniform bound on $\mathopen{}\mathclose{{}\left|{\hat{h}(\boldsymbol{v},b)}}\right|$ follows directly by plugging in the uniform bound on $p$. For the $L^{2}$ bound on $\hat{h}$, we have

$$ $\displaystyle\int_{\mathbb{S}^{k-1}\times[-r_{b},r_{b}]}\hat{h}(\boldsymbol{v} ,b)^{2}\mathrm{d}\tau_{k}(\boldsymbol{v})\mathrm{d}b$ $\displaystyle\leq\int_{\mathbb{S}^{k-1}\times\mathbb{R}}\hat{h}(\boldsymbol{v} ,b)^{2}\mathrm{d}\tau_{k}(\boldsymbol{v})\mathrm{d}b$ $\displaystyle=\int\frac{Z_{k}^{2}r_{z}^{2k}p(\mathrm{T}(\boldsymbol{v},b/r_{z} ))^{2}}{(r_{z}^{2}+b^{2})^{k+2}}\mathrm{d}\tau_{k}(\boldsymbol{v})\mathrm{d}b$ $\displaystyle=\int\frac{Z_{k}^{2}p(\mathrm{T}(\boldsymbol{v},\tilde{b}))^{2}}{ r_{z}^{3}(1+\tilde{b}^{2})^{k+2}}\mathrm{d}\tau_{k}(\boldsymbol{v})\mathrm{d} \tilde{b}$ $\displaystyle=\frac{Z_{k}}{r_{z}^{3}}\int\frac{p(\mathrm{T}(\boldsymbol{v}, \tilde{b}))^{2}}{(1+\tilde{b}^{2})^{(k+3)/2}}\mathrm{d}\tau_{k}(\boldsymbol{v} )\mathrm{d}\rho_{k+1}(\tilde{b})$ $\displaystyle=\frac{Z_{k}}{r_{z}^{3}}\int(1-\tilde{v}_{k+1}^{2})^{(k+3)/2}p( \tilde{\boldsymbol{v}})^{2}\mathrm{d}\tau_{k+1}(\tilde{\boldsymbol{v}})$ $\displaystyle\leq\frac{Z_{k}\mathopen{}\mathclose{{}\left\|{p}}\right\|^{2}_{L ^{2}(\tau_{k+1})}}{r_{z}^{3}}\leq\frac{Z_{k}\Delta^{2}}{r_{z}^{3}},$ $$

completing the proof.
∎

###### Lemma 32 .

### D.4 Discretizing Infinite-Width Approximations

In this section, we provide finite-width guarantees corresponding to the infinite-width approximations proved earlier. Define the following integral operator

$$ $\mathcal{T}\hat{h}(\boldsymbol{z})=\int_{\mathbb{S}^{k-1}\times[-r_{b},r_{b}]} \hat{h}(\boldsymbol{v},b)\sigma(\mathopen{}\mathclose{{}\left\langle{ \boldsymbol{v}},{\boldsymbol{z}}}\right\rangle+b)\mathrm{d}\tau_{k}( \boldsymbol{v})\mathrm{d}b.$ (D.5) $$

The type of discretization error depends on whether we are using the $\alpha\operatorname{-DFL}$ or the $(\alpha{,}\beta)\operatorname{\!-SFL}$ oracle. We first cover the case of $\alpha\operatorname{-DFL}$ oracles.

###### Proposition 33 (Approximation by Riemann Sum) .

Suppose $\sigma$ satisfies (B.1). Let $(\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{N})$ be the first layer weights obtained from the $\alpha\operatorname{-DFL}$ oracle (Definition 2), and define $\boldsymbol{v}_{i}=\frac{\boldsymbol{U}\boldsymbol{w}_{i}}{\mathopen{}
\mathclose{{}\left\|{\boldsymbol{U}\boldsymbol{w}_{i}}}\right\|}$ for $i\in[N]$.
Suppose $(b_{j})_{j\in[N]}\stackrel{{\scriptstyle\mathrm{i.i.d.}}}{{\sim}}\textnormal{
Unif}(-r_{b},r_{b})$, and let $\|\hat{h}\|_{\infty}\coloneqq\sup_{\boldsymbol{v},b}\mathopen{}\mathclose{{}
\left|{\hat{h}(\boldsymbol{v},b)}}\right|$. Then, there exists $\boldsymbol{a}^{*}$ such that $a^{*}_{j}=0$ for $j\notin S$ and $\mathopen{}\mathclose{{}\left|{a^{*}_{j}}}\right|\leq C_{k}\|\hat{h}\|_{\infty
}r_{b}\log(\alpha N/(\zeta\delta))/(\alpha N)$ for $j\in S$ (where $S$ is given by Definition 23), and

$$ $\mathopen{}\mathclose{{}\left|{\sum_{j\in S}a^{*}_{j}\sigma(\mathopen{} \mathclose{{}\left\langle{\boldsymbol{v}_{j}},{\boldsymbol{z}}}\right\rangle+b _{j})-\mathcal{T}\hat{h}(\boldsymbol{z})}}\right|\leq C_{\bar{q}}\|\hat{h}\|_{ \infty}L_{\sigma}r_{b}^{\bar{q}}\Big{(}r_{z}\sqrt{\zeta}+\frac{r_{b}\log(N/ \delta)}{\zeta^{(k-1)/2}\alpha N}\Big{)},$ (D.6) $$

for all $\boldsymbol{z}\in\mathbb{R}^{k}$ where $\mathopen{}\mathclose{{}\left\|{\boldsymbol{z}}}\right\|\leq r_{z}\leq r_{b}$, with probability at least $1-\delta$ over the randomness of biases.

Proof.
The proof is a multivariate version of the argument given in [, Lemma 29]. Let $\{\bar{\boldsymbol{v}}_{i}\}_{i=1}^{M}$ be the maximal $2\sqrt{2\zeta}$-packing of $\mathbb{S}^{k-1}$ from Definition 23, which is also a $2\sqrt{2\zeta}$-covering of $\mathbb{S}^{k-1}$. Recall from Definition 23 that $M\leq C_{k}(\frac{1}{\zeta})^{(k-1)/2}$.

For every $i\in[M]$, define

$$ $S_{i}\coloneqq\{j\in[N],\mathopen{}\mathclose{{}\left\|{\boldsymbol{v}_{j}- \bar{\boldsymbol{v}}_{i}}}\right\|\leq\sqrt{2\zeta}\}.$ $$

Note that by definition of packing and Definition 2, each $\boldsymbol{v}_{j}$ can only belong to exactly one of $S_{i}$ when $j\in S$, meaning that $(S_{i})$ are disjoint and $\bigcup_{i\in[M]}S_{i}=S$. In particular, $\mathopen{}\mathclose{{}\left|{S_{i}}}\right|/N\geq\zeta^{(k-1)/2}\alpha$, and $\mathopen{}\mathclose{{}\left|{S_{i}}}\right|/N\leq 1/M\leq\zeta^{(k-1)/2}/c_{k}$.

We want each group of biases $(b_{j})_{j\in S_{i}}$ to cover the interval $[-r_{b},r_{b}]$. We divide this interval into $2A$ subintervals of the form $[-r_{b}(1+\frac{l}{A}),r_{b}(1+\frac{l+1}{A}))$ for $0\leq l\leq 2A-1$.
When $b_{j}\stackrel{{\scriptstyle\mathrm{i.i.d.}}}{{\sim}}\textnormal{Unif}(-r_{b},
r_{b})$, by a union bound, the probability that there exists some subinterval and some $S_{i}$ such that the subinterval contains no element of $\{b_{j}:j\in S_{i}\}$ is at most $2A\sum_{i=1}^{M}(1-\frac{1}{2A})^{\mathopen{}\mathclose{{}\left|{S_{i}}}\right|}$.
Thus, taking $A\leq\lfloor\frac{\mathopen{}\mathclose{{}\left|{S_{i}}}\right|}{2\log(
\mathopen{}\mathclose{{}\left|{S_{i}}}\right|M/\delta)}\rfloor$ for all $i\in[M]$ guarantees that all subintervals have at least one bias from every $S_{i}$ inside them with probability at least $1-\delta$.

Next, we define $\Pi_{1}:\mathbb{S}^{k-1}\to\mathbb{S}^{k-1}$ as the projection onto the packing, i.e. $\Pi_{1}(\boldsymbol{v})=\operatorname*{arg\,min}_{\{\bar{\boldsymbol{v}}_{i}:i
\in[M]\}}\mathopen{}\mathclose{{}\left\|{\boldsymbol{v}-\bar{\boldsymbol{v}}_{
i}}}\right\|$. Further, we define $\Pi_{2}:[M]\times[-r_{b},r_{b}]\to[-r_{b},r_{b}]$ by $\Pi_{2}(i,b)=\operatorname*{arg\,min}_{\{b_{j}:j\in S_{i}\}}\mathopen{}
\mathclose{{}\left|{b-b_{j}}}\right|$. Tie braking can be performed by choosing any of the answers. By definition, we have $\mathopen{}\mathclose{{}\left\|{\boldsymbol{v}-\Pi_{1}(\boldsymbol{v})}}\right
\|\leq 2\sqrt{2\zeta}$, and additionally $\mathopen{}\mathclose{{}\left|{b-\Pi_{2}(i,b)}}\right|\leq r_{b}/A$ for all $i\in[M]$ on the event described above.

We are now ready to construct $\boldsymbol{a}^{*}$. Specifically, let

$$ $a^{*}_{j}=\begin{cases}\int\hat{h}(\boldsymbol{v},b)\mathbb{I}\mathopen{} \mathclose{{}\left[{i=\Pi_{1}(\boldsymbol{v}),b_{j}=\Pi_{2}(i,b)}}\right] \mathrm{d}\tau_{k}(\boldsymbol{v})\mathrm{d}b&\text{if }j\in S_{i}\text{ for some }i,\\ 0&\text{if }j\notin S.\end{cases}$ $$

Note that by definition,

$$ $\sum_{i=1}^{M}\sum_{j\in S_{i}}\mathbb{I}\mathopen{}\mathclose{{}\left[{i=\Pi_ {1}(\boldsymbol{v}),b_{j}=\Pi_{2}(i,b)}}\right]=1,$ $$

For conciseness, we define $E(\boldsymbol{v},i,j)=\mathbb{I}\mathopen{}\mathclose{{}\left[{i=\Pi_{1}(
\boldsymbol{v}),b_{j}=\Pi_{2}(i,b)}}\right]$. When $j\in S_{i}$, on the event $E(\boldsymbol{v},i,j)$ we have

$$ $\mathopen{}\mathclose{{}\left\|{\boldsymbol{v}-\boldsymbol{v}_{j}}}\right\| \leq\mathopen{}\mathclose{{}\left\|{\boldsymbol{v}-\bar{\boldsymbol{v}}_{i}}} \right\|+\mathopen{}\mathclose{{}\left\|{\bar{\boldsymbol{v}}_{i}-\boldsymbol{ v}_{j}}}\right\|\leq 3\sqrt{2\zeta}.$ $$

Moreover, since $\mathbb{P}_{\boldsymbol{v}\sim\tau_{k}}[\mathopen{}\mathclose{{}\left\|{
\boldsymbol{v}-\bar{\boldsymbol{v}}_{i}}}\right\|\leq 2\sqrt{2\zeta}]\leq C_{k
}\zeta^{(k-1)/2}$, for $j\in S$ we have

$$ $\mathopen{}\mathclose{{}\left|{a^{*}_{j}}}\right|\leq\frac{C_{k}\|\hat{h}\|_{ \infty}\zeta^{(k-1)/2}r_{b}}{A}\leq\frac{C_{k}\|\hat{h}\|_{\infty}r_{b}\log(N/ \delta)}{\alpha N}.$ $$

As a result,

$$ $\displaystyle\mathopen{}\mathclose{{}\left|{\sum_{j\in S}a^{*}_{j}\sigma( \mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}_{j}},{\boldsymbol{z}}} \right\rangle+b_{j})-\mathcal{T}\hat{h}(z)}}\right|$ $\displaystyle=\mathopen{}\mathclose{{}\left|{\sum_{j\in S}a^{*}_{j}\sigma( \mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}_{j}},{\boldsymbol{z}}} \right\rangle+b_{j})-\int\hat{h}(\boldsymbol{v},b)\sigma(\mathopen{}\mathclose {{}\left\langle{\boldsymbol{v}},{\boldsymbol{z}}}\right\rangle+b)\mathrm{d} \tau_{k}(\boldsymbol{v})\mathrm{d}b}}\right|$ $\displaystyle=\mathopen{}\mathclose{{}\left|{\sum_{i=1}^{M}\sum_{j\in S_{i}} \int\hat{h}(\boldsymbol{v},b)E(\boldsymbol{v},i,j)\mathopen{}\mathclose{{} \left(\sigma(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}_{j}},{ \boldsymbol{z}}}\right\rangle+b_{j})-\sigma(\mathopen{}\mathclose{{}\left \langle{\boldsymbol{v}},{\boldsymbol{z}}}\right\rangle+b)}\right)\mathrm{d} \tau_{k}(\boldsymbol{v})\mathrm{d}b}}\right|$ $\displaystyle\lesssim C_{\bar{q}}\|\hat{h}\|_{\infty}L_{\sigma}r_{b}^{\bar{q}} (r_{z}\sqrt{\zeta}+\frac{r_{b}}{A}),$ $$

for all $\mathopen{}\mathclose{{}\left\|{\boldsymbol{z}}}\right\|\leq r_{z}$, where we used the fact that $\sigma(z)$ is $\mathcal{O}(L_{\sigma}r_{b}^{\bar{q}-1})$ Lipschitz when restricted to $\mathopen{}\mathclose{{}\left|{z}}\right|\leq r_{b}$. This concludes the proof.
∎

Next, we provide a discretization guarantee when using $(\alpha{,}\beta)\operatorname{\!-SFL}$ oracles.

###### Proposition 34 .

Consider the same setting as Proposition 33, except the first-layer weights $(\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{N})$ are obtained from the $(\alpha{,}\beta)\operatorname{\!-SFL}$ oracle (Definition 3).
Then, there exists $\boldsymbol{a}^{*}$ such that $a^{*}_{i}=0$ for $i\notin S$ and $\mathopen{}\mathclose{{}\left|{a^{*}_{i}}}\right|\leq\|\hat{h}\|_{\infty}r_{b}
/(\beta\alpha N)$ for $i\in S$, and

$$ $\mathopen{}\mathclose{{}\left|{\sum_{j\in S}a^{*}_{j}\sigma(\mathopen{} \mathclose{{}\left\langle{\boldsymbol{v}_{j}},{\boldsymbol{z}}}\right\rangle+b _{j})-\mathcal{T}\hat{h}(\boldsymbol{z})}}\right|\leq\frac{C_{\bar{q}}L_{ \sigma}\|\hat{h}\|_{\infty}r_{b}^{\bar{q}+1}}{\beta}\sqrt{\frac{\log(\alpha N/ \delta)}{\alpha N}},$ $$

for all $\boldsymbol{z}\in\mathbb{R}^{k}$ with $\mathopen{}\mathclose{{}\left\|{\boldsymbol{z}}}\right\|\leq r_{b}$, with probability at least $1-\delta$ over the randomness of $(\boldsymbol{v}_{i},b_{i})_{i\in[N]}$.
Moreover, suppose $\operatorname{\mathbb{E}}_{\boldsymbol{v},b\sim\tau_{k}\otimes\textnormal{Unif
}(-r_{b},r_{b})}\mathopen{}\mathclose{{}\left[\hat{h}(\boldsymbol{v},b)^{2}}
\right]\leq M_{2}(\hat{h})^{2}$. Then, assuming $\frac{\mathrm{d}\mu}{\mathrm{d}\tau_{k}}\leq\beta^{\prime}$, we have

$$ $\displaystyle\mathopen{}\mathclose{{}\left\|{\boldsymbol{a}^{*}}}\right\|^{2} \lesssim\frac{r_{b}^{2}\beta^{\prime}M_{2}(\hat{h})^{2}}{\alpha\beta^{2}N},$ $\displaystyle\text{provided that},$ $\displaystyle N\gtrsim\frac{\|\hat{h}\|_{\infty}^{4}\log(1/\delta)}{\alpha{ \beta^{\prime}}^{2}M_{2}(\hat{h})^{4}},$ $$

which also holds with probability at least $1-\delta$.

Proof.
By definition,

$$ $\displaystyle\mathcal{T}\hat{h}(\boldsymbol{z})$ $\displaystyle=\int_{\mathbb{S}^{k-1}\times[-r_{b},r_{b}]}\hat{h}(\boldsymbol{v },b)\sigma(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{\boldsymbol{z }}}\right\rangle+b)\mathrm{d}\tau_{k}(\boldsymbol{v})\mathrm{d}b$ $\displaystyle=\int_{\mathbb{S}^{k-1}\times[-r_{b},r_{b}]}\hat{h}(\boldsymbol{v },b)\frac{\mathrm{d}\tau_{k}}{\mathrm{d}\mu}(\boldsymbol{v})\sigma(\mathopen{} \mathclose{{}\left\langle{\boldsymbol{v}},{\boldsymbol{z}}}\right\rangle+b) \mathrm{d}\mu(\boldsymbol{v})\mathrm{d}b$ $\displaystyle=\operatorname{\mathbb{E}}_{\boldsymbol{v},b\sim\mu\otimes \textnormal{Unif}(-r_{b},r_{b})}\mathopen{}\mathclose{{}\left[2r_{b}\hat{h}( \boldsymbol{v},b)\frac{\mathrm{d}\tau_{k}}{\mathrm{d}\mu}(\boldsymbol{v}) \sigma(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{\boldsymbol{z}}} \right\rangle+b)}\right].$ $$

Consider $(\boldsymbol{v}_{i},b_{i})_{i\in S}\stackrel{{\scriptstyle\mathrm{i.i.d.}}}{{
\sim}}\mu\otimes\textnormal{Unif}(-r_{b},r_{b})$ from Definition 3. Let

$$ $a^{*}_{i}=\begin{cases}\frac{2r_{b}\hat{h}(\boldsymbol{v}_{i},b_{i})}{ \mathopen{}\mathclose{{}\left|{S}}\right|}\frac{\mathrm{d}\tau_{k}}{\mathrm{d} \mu}(\boldsymbol{v}_{i})&\text{if }i\in S,\\ 0&\text{if }i\notin S.\end{cases}$ $$

Consequently

$$ $\mathopen{}\mathclose{{}\left|{a^{*}_{i}}}\right|\leq\frac{2r_{b}\|\hat{h}\|_{ \infty}}{\beta\mathopen{}\mathclose{{}\left|{S}}\right|},$ $$

for all $i\in S$. Given $\boldsymbol{z}$, define the random variable

$$ $\hat{\mathcal{T}}\hat{h}(\boldsymbol{z})=\sum_{i\in S}a^{*}_{i}\sigma( \mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}_{i}},{\boldsymbol{z}}} \right\rangle+b_{i}).$ $$

Our next step is to bound the difference between $\hat{\mathcal{T}}\hat{h}(\boldsymbol{z})$ and $\mathcal{T}\hat{h}(\boldsymbol{z})$ uniformly over all $\mathopen{}\mathclose{{}\left\|{\boldsymbol{z}}}\right\|\leq r_{b}$.

Let $(\hat{\boldsymbol{z}}_{j})_{j=1}^{M}$ be a $\Delta$-covering of $\{\boldsymbol{z}:\mathopen{}\mathclose{{}\left\|{\boldsymbol{z}}}\right\|\leq r
_{b}\}$, therefore $M\leq(3r_{b}/\Delta)^{k}$. Note that for any fixed $\boldsymbol{z}$ with $\mathopen{}\mathclose{{}\left\|{\boldsymbol{z}}}\right\|\leq r_{b}$, we have $\mathopen{}\mathclose{{}\left|{\hat{\mathcal{T}}\hat{h}(\boldsymbol{z})}}
\right|\lesssim\|\hat{h}\|_{\infty}L_{\sigma}r_{b}^{\bar{q}+1}/\beta$. Thus, by Hoeffding’s lemma,

$$ $\mathopen{}\mathclose{{}\left|{\hat{\mathcal{T}}\hat{h}(\boldsymbol{z})- \mathcal{T}\hat{h}(\boldsymbol{z})}}\right|\lesssim\frac{\|\hat{h}\|_{\infty}L _{\sigma}r_{b}^{\bar{q}+1}}{\beta}\sqrt{\frac{\log(1/\delta)}{\mathopen{} \mathclose{{}\left|{S}}\right|}},$ $$

with probability at least $1-\delta$ for a fixed $\boldsymbol{z}$. By a union bound,

$$ $\max_{j\in[M]}\mathopen{}\mathclose{{}\left|{\hat{\mathcal{T}}\hat{h}(\hat{ \boldsymbol{z}}_{j})-\mathcal{T}\hat{h}(\hat{\boldsymbol{z}}_{j})}}\right| \lesssim\frac{\|\hat{h}\|_{\infty}L_{\sigma}r_{b}^{\bar{q}+1}}{\beta}\sqrt{ \frac{\log(M/\delta)}{\mathopen{}\mathclose{{}\left|{S}}\right|}},$ $$

with probability at least $1-\delta$. For any $\boldsymbol{z}$ with $\mathopen{}\mathclose{{}\left\|{\boldsymbol{z}}}\right\|\leq r_{b}$, let $\hat{\boldsymbol{z}}$ denote the projection of $\boldsymbol{z}$ onto the covering $(\hat{\boldsymbol{z}}_{j})_{j=1}^{M}$. Then,

$$ $\displaystyle\sup_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{z}}}\right\| \leq r_{b}/2}\mathopen{}\mathclose{{}\left|{\hat{\mathcal{T}}\hat{h}( \boldsymbol{z})-\mathcal{T}\hat{h}(\boldsymbol{z})}}\right|$ $\displaystyle\leq\max_{j\in[M]}\mathopen{}\mathclose{{}\left|{\hat{\mathcal{T} }\hat{h}(\hat{\boldsymbol{z}}_{j})-\mathcal{T}\hat{h}(\hat{\boldsymbol{z}}_{j} )}}\right|+\mathopen{}\mathclose{{}\left|{\mathcal{T}\hat{h}(\hat{\boldsymbol{ z}})-\mathcal{T}\hat{h}(\boldsymbol{z})}}\right|+\mathopen{}\mathclose{{}\left |{\hat{\mathcal{T}}\hat{h}(\hat{\boldsymbol{z}})-\mathcal{T}\hat{h}( \boldsymbol{z})}}\right|$ $\displaystyle\lesssim\frac{\|\hat{h}\|_{\infty}L_{\sigma}r_{b}^{\bar{q}+1}}{ \beta}\sqrt{\frac{\log(M/\delta)}{\mathopen{}\mathclose{{}\left|{S}}\right|}}+ \frac{\|\hat{h}\|_{\infty}L_{\sigma}r_{b}^{\bar{q}}\Delta}{\beta}.$ $\displaystyle\lesssim\frac{\|\hat{h}\|_{\infty}L_{\sigma}r_{b}^{\bar{q}+1}}{ \beta}\sqrt{\frac{\log(r_{b}/(\Delta\delta))}{\mathopen{}\mathclose{{}\left|{S }}\right|}}+\frac{\|\hat{h}\|_{\infty}L_{\sigma}r_{b}^{\bar{q}}\Delta}{\beta}.$ $$

Choosing $\Delta=r_{b}/\sqrt{\mathopen{}\mathclose{{}\left|{S}}\right|}$ implies

$$ $\sup_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{z}}}\right\|\leq r_{b}/2} \mathopen{}\mathclose{{}\left|{\hat{\mathcal{T}}\hat{h}(\boldsymbol{z})- \mathcal{T}\hat{h}(\boldsymbol{z})}}\right|\lesssim\frac{\|\hat{h}\|_{\infty}L _{\sigma}r_{b}^{\bar{q}+1}}{\beta}\sqrt{\frac{\log(\mathopen{}\mathclose{{} \left|{S}}\right|/\delta)}{\mathopen{}\mathclose{{}\left|{S}}\right|}}$ $$

with probability at least $1-\delta$ over the randomness of $(\boldsymbol{v}_{i},b_{i})_{i\in[N]}$.

The last step is to bound $\mathopen{}\mathclose{{}\left\|{\boldsymbol{a}^{*}}}\right\|^{2}$. Note that,

$$ $\mathopen{}\mathclose{{}\left\|{\boldsymbol{a}^{*}}}\right\|^{2}\leq\frac{4r_{ b}^{2}}{\beta^{2}\mathopen{}\mathclose{{}\left|{S}}\right|}\sum_{i\in S}\frac{ \hat{h}(\boldsymbol{v}_{i},b_{i})^{2}}{\mathopen{}\mathclose{{}\left|{S}} \right|}.$ $$

Further, by the Hoeffding inequality,

$$ $\sum_{i\in S}\frac{\hat{h}(\boldsymbol{v}_{i},b_{i})^{2}}{\mathopen{} \mathclose{{}\left|{S}}\right|}-\operatorname{\mathbb{E}}_{\boldsymbol{v},b \sim\mu\otimes\textnormal{Unif}(-r_{b},r_{b})}\mathopen{}\mathclose{{}\left[ \hat{h}(\boldsymbol{v},b)^{2}}\right]\lesssim\|\hat{h}\|_{\infty}^{2}\sqrt{ \frac{\log(1/\delta)}{\mathopen{}\mathclose{{}\left|{S}}\right|}}$ $$

with probability at least $1-\delta$. Moreover,

$$ $\displaystyle\operatorname{\mathbb{E}}_{\boldsymbol{v},b\sim\mu\otimes \textnormal{Unif}(-r_{b},r_{b})}\mathopen{}\mathclose{{}\left[\hat{h}( \boldsymbol{v},b)^{2}}\right]$ $\displaystyle=\operatorname{\mathbb{E}}_{\boldsymbol{v},b\sim\tau_{k}\otimes \textnormal{Unif}(-r_{b},r_{b})}\mathopen{}\mathclose{{}\left[\hat{h}( \boldsymbol{v},b)^{2}\frac{\mathrm{d}\mu}{\mathrm{d}\tau_{k}}(\boldsymbol{v})}\right]$ $\displaystyle\leq\beta^{\prime}M_{2}(\hat{h})^{2}.$ $$

Thus, when $\mathopen{}\mathclose{{}\left|{S}}\right|\geq\frac{\|\hat{h}\|_{\infty}^{4}
\log(1/\delta)}{{\beta^{\prime}}^{2}M_{2}(\hat{h})^{4}}$, we have $\mathopen{}\mathclose{{}\left\|{\boldsymbol{a}^{*}}}\right\|^{2}\lesssim r_{b}
^{2}\beta^{\prime}M_{2}(\hat{h})^{2}/(\beta^{2}\mathopen{}\mathclose{{}\left|{
S}}\right|)$
with probability at least $1-\delta$, which completes the proof.
∎

###### Proposition 33 (Approximation by Riemann Sum) .

###### Proposition 34 .

### D.5 Combining All Steps

We can finally bound our original objective of this section, i.e. $\mathrm{AR}(\boldsymbol{a}^{*},\boldsymbol{W},\boldsymbol{b})-\mathrm{AR}^{*}$. Let us begin with the case where $\mathcal{F}$ is the class of polynomials of degree $p$.

###### Proposition 35 .

Suppose $\mathcal{F}$ and $\sigma$ satisfy Assumption 4 and $(b_{i})_{i\in[N]}\stackrel{{\scriptstyle\mathrm{i.i.d.}}}{{\sim}}\textnormal{
Unif}(-r_{b},r_{b})$. Recall that $\varepsilon_{1}\coloneqq 1\lor\varepsilon$, and $\tilde{\epsilon}\coloneqq\epsilon\land\frac{\epsilon^{2}}{\mathrm{AR}^{*}}$ for any $\epsilon\in(0,1)$. Using the simplification $k,q,p,L_{\sigma}\lesssim 1$ and recalling $\varepsilon_{1}\coloneqq 1\lor\varepsilon$, there exists a choice of $r_{b}=\tilde{\Theta}(\varepsilon_{1})$ such that:

- •
If $\boldsymbol{W}=(\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{N})^{\top}$ are given by the $\alpha\operatorname{-DFL}$ oracle, there exists $\boldsymbol{a}^{*}$ such that $\mathopen{}\mathclose{{}\left|{a^{*}_{i}}}\right|\leq\tilde{\mathcal{O}}(
\varepsilon_{1}/(\alpha N))$ for all $i\in[N]$, and $\mathrm{AR}(\boldsymbol{a}^{*},\boldsymbol{W},\boldsymbol{b})-\mathrm{AR}^{*}\leq\epsilon$ as soon as
$\displaystyle\zeta\leq\tilde{\mathcal{O}}\Big{(}\frac{\tilde{\epsilon}}{
\varepsilon_{1}^{2(q+1)}}\Big{)}$
and
$\displaystyle N\geq\tilde{\Omega}\Big{(}\frac{\varepsilon_{1}^{q+1}}{\alpha
\zeta^{(k-1)/2}\sqrt{\tilde{\epsilon}}}\Big{)}.$
- •
If $\boldsymbol{W}=(\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{N})^{\top}$ are given by the $(\alpha{,}\beta)\operatorname{\!-SFL}$ oracle, there exists $\boldsymbol{a}^{*}$ such that $\mathopen{}\mathclose{{}\left|{a^{*}_{i}}}\right|\leq\tilde{\mathcal{O}}(
\varepsilon_{1}/(\beta\alpha N))$ for all $i\in[N]$, and $\mathrm{AR}(\boldsymbol{a}^{*},\boldsymbol{W},\boldsymbol{b})-\mathrm{AR}^{*}\leq\epsilon$ as soon as
$\displaystyle\zeta\leq\tilde{\mathcal{O}}\Big{(}\frac{\beta^{2}\tilde{\epsilon
}}{\varepsilon_{1}^{2(q+1)}}\Big{)}$
and
$\displaystyle N\geq\tilde{\Omega}\Big{(}\frac{\varepsilon_{1}^{2(q+1)}}{\alpha
\beta^{2}\tilde{\epsilon}}\Big{)}.$

Both cases above hold with probability at least $1-n^{-c}$ for some absolute constant $c>0$ over the choice of random biases $(b_{i})_{i\in[N]}$ (and random weights $(\boldsymbol{w}_{i})$ in the case of SFL).

Proof.
Recall from (D.1) that

$$ $\mathrm{AR}(\boldsymbol{a}^{*},\boldsymbol{W},\boldsymbol{b})-\mathrm{AR}^{*} \lesssim\mathcal{E}_{1}+\mathcal{E}_{2}+\sqrt{\mathcal{E}_{3}(\mathcal{E}_{1}+ \mathcal{E}_{2})}.$ $$

By definition, $\mathcal{E}_{3}\lesssim\mathrm{AR}^{*}$. By Lemma 24, we have

$$ $\mathcal{E}_{2}\lesssim L_{\sigma}^{2}\tilde{r}_{a}^{2}(1+r_{b}^{2(\bar{q}-1)} +\varepsilon^{2(\bar{q}-1)})(1+\varepsilon^{2})\zeta.$ $$

Further, thanks to Lemma 31 we have $\mathopen{}\mathclose{{}\left|{h(\boldsymbol{z})}}\right|\lesssim 1+\mathopen{
}\mathclose{{}\left\|{\boldsymbol{z}}}\right\|^{p}$. Therefore, by Lemma 25 with $r_{z}=r_{b}$, we have

$$ $\mathcal{E}_{1}\lesssim\epsilon_{\mathrm{approx}}^{2}+\big{(}L_{\sigma}^{2} \tilde{r}_{a}^{2}(1+\varepsilon^{2\bar{q}}+r_{b}^{2\bar{q}})+1+\varepsilon^{2p }\big{)}e^{-\Omega(r_{b}^{2})}.$ $$

Let us now consider the case of $\alpha\operatorname{-DFL}$. Define $\bar{p}=(p-2)\lor 0$ if the ReLU activation is used and $\bar{p}=0$ if the polynomial activation is used. Notice that by the definition in Assumption 4, we have $\bar{q}+\bar{p}=q$. By Proposition 33, we know there exists $\boldsymbol{a}^{*}$ with $\mathopen{}\mathclose{{}\left|{a^{*}_{i}}}\right|\leq\tilde{\mathcal{O}}(r_{b}
^{1+\bar{p}}/(\alpha N))$ (we used the fact that $\max_{s\leq p}\mathopen{}\mathclose{{}\left\|{\boldsymbol{T}^{(s)}}}\right\|_{
\mathrm{F}}\lesssim 1$ from Lemma 31) such that

$$ $\epsilon_{\mathrm{approx}}\leq\tilde{\mathcal{O}}\Big{(}r_{b}^{q+1}\big{(} \sqrt{\zeta}+\frac{1}{\zeta^{(k-1)/2}\alpha N}\big{)}\Big{)},$ $$

provided that $r_{b}\gtrsim\varepsilon_{1}$ where we recall $\varepsilon_{1}=1\lor\varepsilon$, and the above statement holds with probability at least $1-\delta$ for any polynomially decaying $\delta$, e.g. $\delta=n^{-c}$ for some absolute constant $c>0$.
Therefore, we have $\tilde{r}_{a}\leq\tilde{\mathcal{O}}(r_{b}^{1+\bar{p}})$.
Further, it suffices to choose $r_{b}$ large enough such that
$r_{b}\gtrsim\varepsilon_{1}\lor\sqrt{\log(NL_{\sigma}^{2}\tilde{r}_{a}^{2}r_{b
}^{2\bar{q}}+\varepsilon_{1}^{2p})}=\tilde{\Theta}(\varepsilon_{1})$ to have

$$ $\mathcal{E}_{1}\leq\tilde{\mathcal{O}}\Big{(}r_{b}^{2(q+1)}\big{(}\zeta+\frac{ 1}{\zeta^{k-1}\alpha^{2}N^{2}}\big{)}\Big{)}.$ $$

Plugging in the values of $\tilde{r}_{a}$ and $r_{b}$, we obtain,

$$ $\displaystyle\mathcal{E}_{2}\leq\tilde{\mathcal{O}}(\varepsilon_{1}^{2(q+1)} \zeta),$ $\displaystyle\mathrm{and}$ $\displaystyle\mathcal{E}_{1}\leq\tilde{\mathcal{O}}\Big{(}\varepsilon_{1}^{2(q +1)}\zeta+\frac{\varepsilon_{1}^{2(q+1)}}{\zeta^{k-1}\alpha^{2}N^{2}}\Big{)}.$ $$

Hence, choosing

$$ $\displaystyle\zeta\leq\tilde{\mathcal{O}}\Big{(}\frac{\tilde{\epsilon}}{ \varepsilon_{1}^{2(q+1)}}\Big{)},$ $\displaystyle\mathrm{and}$ $\displaystyle N\geq\tilde{\Omega}\Big{(}\frac{\varepsilon_{1}^{q+1}}{\alpha \zeta^{(k-1)/2}\sqrt{\tilde{\epsilon}}}\Big{)}$ $$

which concludes the proof of the $\alpha\operatorname{-DFL}$ case.

In the case of $(\alpha{,}\beta)\operatorname{\!-SFL}$, we instead invoke Proposition 34, thus obtain $\mathopen{}\mathclose{{}\left|{a^{*}_{i}}}\right|\lesssim r_{b}^{1+\bar{p}}/(
\beta\alpha N)$, and

$$ $\epsilon_{\mathrm{approx}}\leq\tilde{\mathcal{O}}\Big{(}\frac{L_{\sigma}r_{b}^ {q+1}}{\beta\sqrt{\alpha N}}\Big{)},$ $$

which holds with probability at least $1-\delta$ for any polynomially decaying $\delta$ such as $\delta=n^{-c}$ for some absolute constant $c>0$. Consequently, with the same choice of $r_{b}=\tilde{\Theta}(\varepsilon_{1})$ as before, we have

$$ $\displaystyle\mathcal{E}_{2}\leq\tilde{\mathcal{O}}\Big{(}\frac{\varepsilon_{1 }^{2(q+1)}\zeta}{\beta^{2}}\Big{)},$ $\displaystyle\mathrm{and}$ $\displaystyle\mathcal{E}_{1}\leq\tilde{\mathcal{O}}\Big{(}\frac{\varepsilon_{1 }^{2(q+1)}}{\beta^{2}\alpha N}\Big{)},$ $$

which completes the proof.
∎

We can also combine approximation bounds for the more general class of pseudo-Lipschitz $\mathcal{F}$.

###### Proposition 36 .

Suppose $\mathcal{F}$ and $\sigma$ satisfy Assumption 3 and $(b_{i})_{i\in[N]}\stackrel{{\scriptstyle\mathrm{i.i.d.}}}{{\sim}}\textnormal{
Unif}(-r_{b},r_{b})$. Recall that $\varepsilon_{1}\coloneqq 1\lor\varepsilon$, and $\tilde{\epsilon}\coloneqq\epsilon\land\tfrac{\epsilon^{2}}{\mathrm{AR}^{*}}$ for any $\epsilon\in(0,1)$. Using the simplification $k,p,L\lesssim 1$, there exists a choice of $r_{b}=\tilde{\Theta}\big{(}\varepsilon_{1}(\varepsilon_{1}/\sqrt{\tilde{
\epsilon}})^{1+1/k}\big{)}$ such that:

- •
If $\boldsymbol{W}=(\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{N})^{\top}$ is given by the $\alpha\operatorname{-DFL}$ oracle, there exists $\boldsymbol{a}^{*}$ such that $\mathopen{}\mathclose{{}\left|{a^{*}_{i}}}\right|\leq\tilde{\mathcal{O}}((
\varepsilon_{1}/\sqrt{\tilde{\epsilon}})^{k+1+1/k}/(\alpha N))$ for all $i\in[N]$, and $\mathrm{AR}(\boldsymbol{a}^{*},\boldsymbol{W},\boldsymbol{b})-\mathrm{AR}^{*}\leq\epsilon$ as soon as
$\displaystyle\zeta\leq\tilde{\mathcal{O}}\Big{(}\big{(}\frac{\tilde{\epsilon}}
{\varepsilon_{1}^{2}}\big{)}^{k+2+1/k}\Big{)},$
and
$\displaystyle N\geq\tilde{\Omega}\Big{(}\frac{1}{\zeta^{(k-1)/2}\alpha}\big{(}
\frac{\varepsilon_{1}}{\sqrt{\tilde{\epsilon}}}\big{)}^{k+3+2/k}\Big{)}.$
- •
If $\boldsymbol{W}=(\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{N})^{\top}$ is given by the $(\alpha{,}\beta)\operatorname{\!-SFL}$ oracle, there exists $\boldsymbol{a}^{*}$ such that $\mathopen{}\mathclose{{}\left|{a^{*}_{i}}}\right|\leq\tilde{\mathcal{O}}\big{(
}(\varepsilon_{1}/\sqrt{\tilde{\epsilon}})^{k+1+1/k}/(\alpha\beta N)\big{)}$, and $\mathrm{AR}(\boldsymbol{a}^{*},\boldsymbol{W},\boldsymbol{b})-\mathrm{AR}^{*}\leq\epsilon$ as soon as
$\displaystyle\zeta\leq\tilde{\mathcal{O}}\Big{(}\beta^{2}\big{(}\frac{\tilde{
\epsilon}}{\varepsilon_{1}^{2}}\big{)}^{k+2+1/k}\Big{)},$
and
$\displaystyle N\geq\tilde{\Omega}\Big{(}\frac{1}{\alpha\beta^{2}}\big{(}\frac{
\varepsilon_{1}^{2}}{\tilde{\epsilon}}\big{)}^{k+3+2/k}\Big{)}.$

Both cases above hold with probability at least $1-n^{-c}$ for some absolute constant $c>0$ over the choice of random biases $(b_{i})_{i\in[N]}$ (and random weights $(\boldsymbol{w}_{i})$ in the case of SFL).

Proof.
Our starting point is once again the decomposition

$$ $\mathrm{AR}(\boldsymbol{a}^{*},\boldsymbol{W},\boldsymbol{b})-\mathrm{AR}^{*} \leq\mathcal{E}_{1}+\mathcal{E}_{2}+\sqrt{\mathcal{E}_{3}(\mathcal{E}_{1}+ \mathcal{E}_{2})}.$ $$

Given Assumption 3, it is straightforward to verify that $\mathopen{}\mathclose{{}\left|{h(\boldsymbol{z}_{1})-h(\boldsymbol{z}_{2})}}
\right|\lesssim(\varepsilon_{1}^{1-p}\mathopen{}\mathclose{{}\left\|{
\boldsymbol{z}_{1}}}\right\|^{p-1}+\varepsilon_{1}^{1-p}\mathopen{}\mathclose{
{}\left\|{\boldsymbol{z}_{2}}}\right\|^{p-1}+1)\mathopen{}\mathclose{{}\left\|
{\boldsymbol{z}_{1}-\boldsymbol{z}_{2}}}\right\|$ for $\boldsymbol{z}_{1},\boldsymbol{z}_{2}\in\mathbb{R}^{k}$. As a consequence, we have $\mathopen{}\mathclose{{}\left|{h(\boldsymbol{z})}}\right|\lesssim 1+\mathopen{
}\mathclose{{}\left\|{\boldsymbol{z}}}\right\|^{p}$ for all $\boldsymbol{z}\in\mathbb{R}^{k}$. Therefore, by Lemma 25 with a choice of $r_{z}=\tilde{\Theta}(\varepsilon_{1})$, we have $\mathcal{E}_{1}\lesssim\epsilon_{\mathrm{approx}}^{2}$. In the rest of the proof we will fix $r_{z}=\tilde{\Theta}(\varepsilon_{1})$.

We begin by considering the case of $\alpha\operatorname{-DFL}$. Unlike the proof of Proposition 35 where $\mathcal{T}\hat{h}=h$, in this case we have an additional error due to $\mathcal{T}\hat{h}$ only approximating $h$. From Lemma 32, we have

$$ $\displaystyle\|\hat{h}\|_{\infty}\leq\tilde{\mathcal{O}}\Big{(}\frac{1}{ \varepsilon_{1}}\big{(}\frac{\Delta}{\varepsilon_{1}}\big{)}^{2k/(k+1)}\Big{)}.$ $$

Thus,

$$ $\displaystyle\epsilon_{\mathrm{approx}}$ $\displaystyle\leq\sup_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{z}}}\right \|\leq r_{z}}\mathopen{}\mathclose{{}\left|{\sum_{j\in S}a^{*}_{j}\sigma( \mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}_{j}},{\boldsymbol{z}}} \right\rangle+b_{j})-\mathcal{T}\hat{h}(\boldsymbol{z})}}\right|+\mathopen{} \mathclose{{}\left|{\mathcal{T}\hat{h}(\boldsymbol{z})-h(\boldsymbol{z})}}\right|$ $\displaystyle\leq\tilde{\mathcal{O}}\Big{(}\frac{r_{b}}{\varepsilon_{1}}\big{( }\frac{\Delta}{\varepsilon_{1}}\big{)}^{\frac{2k}{k+1}}\big{(}\varepsilon_{1} \sqrt{\zeta}+\frac{r_{b}}{\zeta^{(k-1)/2}\alpha N}\big{)}\Big{)}+\tilde{ \mathcal{O}}\Big{(}\varepsilon_{1}\big{(}\frac{\Delta}{\varepsilon_{1}}\big{)} ^{-\frac{2}{k+1}}+\varepsilon_{1}\big{(}\frac{\Delta}{\varepsilon_{1}}\big{)}^ {\frac{2k}{k+1}}\big{(}\frac{\varepsilon_{1}}{r_{b}}\big{)}^{k}\Big{)},$ $$

where we bounded the first term via Proposition 33 with $\bar{q}=1$, and the second term via Lemma 32. Additionally, we have

$$ $\mathopen{}\mathclose{{}\left|{a^{*}_{j}}}\right|\leq\frac{r_{b}}{\varepsilon_ {1}\alpha N}\big{(}\frac{\Delta}{\varepsilon_{1}}\big{)}^{\frac{2k}{k+1}},$ $$

for all $j\in[N]$. To obtain $\mathrm{AR}(\boldsymbol{a}^{*},\boldsymbol{W},\boldsymbol{b})\leq\mathrm{AR}^{
*}+\epsilon$, we must choose $\Delta=\tilde{\Theta}(\varepsilon_{1}(\varepsilon_{1}/\sqrt{\tilde{\epsilon}})
^{(k+1)/2})$. Next, we choose $r_{b}=\tilde{\Theta}(\varepsilon_{1}(\varepsilon_{1}/\sqrt{\tilde{\epsilon}})^
{(k+1)/k})$. This combination ensures $\mathopen{}\mathclose{{}\left|{\mathcal{T}\hat{h}(\boldsymbol{z})-h(
\boldsymbol{z})}}\right|\lesssim\sqrt{\tilde{\epsilon}}$. To make sure $\mathopen{}\mathclose{{}\left|{\hat{\mathcal{T}}\hat{h}(\boldsymbol{z})-
\mathcal{T}\hat{h}(\boldsymbol{z})}}\right|\lesssim\sqrt{\tilde{\epsilon}}$, we should let

$$ $\displaystyle\zeta\leq\tilde{\mathcal{O}}\Big{(}\big{(}\frac{\tilde{\epsilon}} {\varepsilon_{1}^{2}}\big{)}^{k+2+1/k}\Big{)},$ $\displaystyle\mathrm{and}$ $\displaystyle N=\tilde{\Theta}\Big{(}\frac{1}{\zeta^{(k-1)/2}\alpha}\big{(} \frac{\varepsilon_{1}}{\sqrt{\tilde{\epsilon}}}\big{)}^{k+3+2/k}\Big{)}.$ $$

The above guarantees that $\epsilon_{\mathrm{approx}}\lesssim\sqrt{\tilde{\epsilon}}$ and consequently $\mathcal{E}_{1}+\sqrt{\mathcal{E}_{3}\mathcal{E}_{1}}\lesssim\epsilon$. Note that the above choices imply $\mathopen{}\mathclose{{}\left|{a^{*}_{j}}}\right|\leq\tilde{r}_{a}/\mathopen{}
\mathclose{{}\left|{S}}\right|$ for all $i\in S$ with $\tilde{r}_{a}=\tilde{\mathcal{O}}((\varepsilon_{1}/\sqrt{\tilde{\epsilon}})^{k
+1+1/k})$. From Lemma 24 with $\bar{q}=1$, we have
$\mathcal{E}_{2}\lesssim\tilde{r}_{a}^{2}\varepsilon_{1}^{2}\zeta$.
Therefore, if we let

$$ $\zeta=\tilde{\Theta}\Big{(}\big{(}\frac{\tilde{\epsilon}}{\varepsilon_{1}^{2}} \big{)}^{k+2+1/k}\Big{)},$ $$

we have $\mathcal{E}_{2}\lesssim\tilde{\epsilon}$ and consequently $\mathcal{E}_{2}+\sqrt{\mathcal{E}_{3}\mathcal{E}_{1}}\lesssim\epsilon$. This concludes the proof of the $\alpha\operatorname{-DFL}$ case.

Next, we consider the case of $(\alpha{,}\beta)\operatorname{\!-SFL}$. Note that the error $\mathopen{}\mathclose{{}\left|{\mathcal{T}\hat{h}(\boldsymbol{z})-h(
\boldsymbol{z})}}\right|$ remains unchanged. However, this time we invoke Proposition 34 for controlling $\mathopen{}\mathclose{{}\left|{\hat{\mathcal{T}}\hat{h}(\boldsymbol{z})-
\mathcal{T}\hat{h}(\boldsymbol{z})}}\right|$.
Therefore,

$$ $\displaystyle\epsilon_{\mathrm{approx}}$ $\displaystyle\leq\sup_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{z}}}\right \|\leq r_{z}}\mathopen{}\mathclose{{}\left|{\sum_{j\in S}a^{*}_{j}\sigma( \mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}_{j}},{\boldsymbol{z}}} \right\rangle+b_{j})-\mathcal{T}\hat{h}(\boldsymbol{z})}}\right|+\mathopen{} \mathclose{{}\left|{\mathcal{T}\hat{h}(\boldsymbol{z})-h(\boldsymbol{z})}}\right|$ $\displaystyle\leq\tilde{\mathcal{O}}\Big{(}\frac{r_{b}^{2}}{\beta\varepsilon_{ 1}}\big{(}\frac{\Delta}{\varepsilon_{1}}\big{)}^{\frac{2k}{k+1}}\sqrt{\frac{1} {\alpha N}}\Big{)}+\tilde{\mathcal{O}}\Big{(}\varepsilon_{1}\big{(}\frac{ \Delta}{\varepsilon_{1}}\big{)}^{-\frac{2}{k+1}}+\varepsilon_{1}\big{(}\frac{ \Delta}{\varepsilon_{1}}\big{)}^{\frac{2k}{k+1}}\big{(}\frac{\varepsilon_{1}}{ r_{b}}\big{)}^{k}\Big{)}.$ $$

Since the second term is unchanged, we have the same choices of $\Delta=\tilde{\Theta}\big{(}\varepsilon_{1}(\varepsilon_{1}/\sqrt{\tilde{
\epsilon}})^{(k+1)/2}\big{)}$ and $r_{b}=\tilde{\Theta}\big{(}\varepsilon_{1}(\varepsilon_{1}/\sqrt{\tilde{
\epsilon}})^{1+1/k}\big{)}$ as in the $\alpha\operatorname{-DFL}$ case. However, for the finite-width discretization, we should choose

$$ $N=\tilde{\Theta}\Big{(}\frac{1}{\alpha\beta^{2}}\big{(}\frac{\varepsilon_{1}^{ 2}}{\tilde{\epsilon}}\big{)}^{k+3+2/k}\Big{)}.$ (D.7) $$

Moreover, Proposition 34 implies $\mathopen{}\mathclose{{}\left|{a^{*}_{j}}}\right|\leq\tilde{r}_{a}/\mathopen{}
\mathclose{{}\left|{S}}\right|$ with $\tilde{r}_{a}=\tilde{\mathcal{O}}\big{(}(\varepsilon_{1}/\sqrt{\tilde{\epsilon
}})^{k+1+1/k}/\beta\big{)}$. As a result, to get $\mathcal{E}_{2}\lesssim\tilde{r}_{a}^{2}\varepsilon_{1}^{2}\zeta\leq\tilde{\epsilon}$ from Lemma 24 with $q=1$, we let

$$ $\zeta=\tilde{\Theta}\Big{(}\beta^{2}\big{(}\frac{\tilde{\epsilon}}{\varepsilon _{1}^{2}}\big{)}^{k+2+1/k}\Big{)},$ $$

completing the proof.

∎

###### Proposition 35 .

###### Proposition 36 .

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: - What are the assumptions on the class $\mathcal{F}$ in Theorem 1?
- In the proof of Theorem 1, is $h(x)$ assumed to be in $\mathcal{F}$?
- Does definition 2 (DFL) implicitly assume constraints on the magnitudes of $w_i$? Otherwise, DFL is trivially satisfied by scaling up the weights. How is this scaling issue consistent with Theorem 4?
soundness: 3
strengths: - The problem of obtaining theoretical guarantees on adversarial risk and the dependence on the structure of the data is well-motivated of interest to the community.
- The direction of studying the interplay between feature learning and adversarial robustness appears to be novel.
- The paper is well written and describes the setup, literature well.
- The proofs are easy to follow.
summary: The paper analyzses adversarially robust learning for two-layer neural networks trained on multi-index targets dependent on a low-dimensional subspace. The paper begins by proving that an optimal adversarially-robust predictor depends solely on the target subspace. Subsequently, the paper shows that existing guarantees for recovering the target subspace through SGD can be combined with covering number, rademacher complexity-based generalization and approximation arguments to obtain bounds on the adversarial risk. Crucially, the paper shows that the additional sample-complexity requirements for vanishing adversarial risk are independent of the ambient dimension.
weaknesses: My main criticism of the paper is that the extent of the theoretical novelty in the analysis and unexpectedness of the result is unclear in the paper's presentation. The paper would improve by emphasizing the central difficulties in combining the finite-dimensional guarantees with feature learning results. Specifically, it would be useful to know what parts of the analysis would change if one were directly studying the setup of random features on finite dimensions. It appears that the role of the low-dimensionality of the target subspace and feature learning is primarily in obtaining a second layer with dimension-independent norm ($r_a$ in Algorithm 1) that fits the target allowing for the Rademacher-complexity argument to go through. This aspect of the analysis is however, the same as generalization bounds in existing works on feature learning such as Damian et al. 2022.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: Can you discuss how this result and analysis techniques connect to other recent results in how shallow networks learn representations, such as (Collins et. al., Provable Multi-task Representation Learning by 2-Layer ReLU Neural Networks, ICML 2024) and (Wang et al, Learning Hierarchical Polynomials with Three-Layer Neural Networks, ICLR 2024) ? 

Is the first inequality of the proof of Theorem 1 actually an equality?

In the experiment section, how did you select the “direction u”? Is this a vector in R^d? I do not see where u is defined.

Can you discuss what the actionable insights are in terms of training robust models? It would be interesting to see more practical experiments of how standard feature learning followed by running adversarial training on the last layers of a network can result in a full model which is adversarially robust.
soundness: 3
strengths: The paper’s first contribution is that the ground truth latent features are in fact the optimal features in terms of adversarial robustness. This is not largely surprising, but it plays an important role in informing the kinds of algorithms one should use to achieve an adversarially robust model. They then show how to characterize the sample complexity and model complexity for just adversarially training the second layer for a broad class of target functions when given access to a feature learning oracle. Importantly, these bounds are independent of the ambient dimension as the hardness only depends on the effective dimension of the problem. These results are an interesting extension of previous works in feature learning for 2-layer neural networks which do not consider adversarial robustness.
summary: This paper addresses the challenge of learning adversarially robust models using 2-layer neural networks where the targets are a function of a latent low-dimensional projection of the inputs. Throughout the paper, they consider L2-constrained adversarial perturbations. They first prove that the optimal features in terms of adversarial robustness are in fact the true latent features of the data model. Then building off of prior work in 2-layer network feature learning, they assume access to a feature-learning oracle and analyze algorithms which query the oracle for the first-layer features and then adversarially train over the second layer’s parameters. For different function classes, they provide bounds for the number of required samples for adversarial training, neurons, and feature learning oracle error in order to achieve optimal robustness up to epsilon error with high probability. Through brief experiments, they validate their theoretical results and show that standard training followed by training just the last layer using the adversarial objective performs much better than full adversarial training.
weaknesses: The major weakness is the lack of extensive experiments. I think that the first row of figure one is not a fair comparison as the paper graphs a model trained completely using adversarial training techniques to just training the last layer using adversarial techniques while initializing the first layer to the ground truth representation. In the second row,  all models are forced to learn representations which is a more realistic scenario. However, based on the high-level result that adversarial training is no harder than standard training and that the optimal adversarially robust features are just the ground truth features, it would be interesting to see how different combinations of standard vs. adversarial training on different network layers for real-world data affects performance.  

Also, the statement of Theorem 1 is confusing. First of all it is not clear that the multi-index data model is still assumed. Also, the phrase “with equality when f^* in F” is confusing since f* in F doesn’t imply equality and that part is obvious, so stating it in this way is confusing for no reason. Also, the statement “Further, h is represented as E[]” is also confusing because it seems to mean that any h that satisfies the theorem must be represented in that way which is not true. The theorem should be restated as something like “Assume multi-index data model as explained above, Assumption 1, and (2.2) admits a min. Then there exists a function f* = h(Ux) where h = E[f] for some f in F where AR(f*) leq AR*.”

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: -	The proposed method only involves an adversarial training of the second layer. This has the benefit of achieving a robust training without requiring more samples or neurons than standard training. In addition, Figure 1 suggests that the convergence is faster compared to a full adversarial training. However, in the ReLu case (left panel), it seems that the robust test risk in the case of the full AD training is still decreasing. Given this observation and in the same setting as the paper, is there a possibility that robustly training both layers could achieve the same guarantees (sample complexity, number of neurons required) as standard training? 

-	In line 187, it is mentioned that the parameters $a, b$ are used to approximate $h$. This corresponds to roughly $N$ parameters to approximate the $k$-dimensional function $h$: can we think of the power $k$ in the bound for $N$ in Theorems 4 and 5 as a form of curse of dimensionality associated with this approximation task? If so, is there an intuitive reason why those exponents do not appear in Theorems 6 and 7 ? 

-	I am not sure about the assumptions of Proposition 8: In [Lee et. Al., 2024] Theorem 2 requires that the activation is also a polynomial with a higher degree than the link function. Is this additional assumption required for Proposition 8? Likewise, in Corollaries 9 and 11, the mention “as in Assumption 4” may be confusing: do you also make the assumptions regarding the activation? 

More precise questions and remarks:

-	In line 215, it is not clear why the expectation of the norm of $x$ is proportional to the square root of the dimension. 
-	Likewise, in line 218, the argument for choosing $\varepsilon$ of order 1 can be made clearer (is this because the scalar dot between $u$ and $x$ is also of order 1?).
-	In and before Definition 2, it is not mentioned that the columns of the weight matrix should be of unit norm. Without this detail, it seems that the definition of the DFL do not make much sense. 
-	In Definition 3, the last sentence is not very understandable and is not explained afterwards.
-	In Theorems 4 and 6, it would be nice for completeness to precise that the absolute constant c is positive. 
-	Since the results of section 4.2 do not cover the case of general activation, the discussion spanning from line 405 to 423 could be shortened. 


[Lee et. Al., 2024]: Jason D. Lee, Kazusato Oko, Taiji Suzuki, and Denny Wu. Neural network learns low-dimensional polynomials with sgd near the information-theoretic limit.
soundness: 3
strengths: -	Although I do not have any particular knowledge in robust training, I found the paper accessible and well explained. The stakes are clearly presented in the introduction. Additionally, the setup and the assumptions are generally well motivated. 
-	Despite not having read the proofs in detail, I appreciated that the proof techniques originate from diverse ideas and prior works including statistical learning, with generalization bounds provided in Appendix C1, geometrical analysis from the low-dimensional subspace assumption, approximation of functions using infinite-width neural networks, etc.
-	From the references provided in the introduction, it is clear that this paper offers new results and insights, distinguishing this work from previous research in the field.
-	The numerical experiment displayed in the main text gives a nice support to the theoretical claims of the paper.
summary: This paper demonstrates that it is possible to robustly train a multi-index model without impacting the statistical performance of the algorithm compared to standard learning methods. Assuming a low-dimensional structure in the probability distribution of the observations, the authors propose a procedure for robust learning in two-layer neural networks. This approach involves a standard learning step for the input layer aiming at recovering the relevant low-dimensional subspace, followed by a robust learning phase for the output layer in lower dimension.

In Theorems 4, 5, 6, and 7, the authors provide rigorous asymptotic bounds on the sample complexity (in the second step), number of neurons, and achievable error for the feature learning algorithm, ensuring the algorithm attains a small adversarial generalization error. These bounds are shown to be independent of the ambient dimension. Finally, using recent results on the number of observations necessary to learn the relevant low-dimensional subspace, the authors establish a scaling for the sample complexity for both single and multi-index models in Corollaries 9 and 11.
weaknesses: -	Theorems 4, 5, 6 and 7 rely on specific activations (ReLU / polynomial). What is the technical challenge arising when considering more general activations? 
-	Although it is interesting to include some proofs in the main text, the proof of Theorem 1 could be easily replaced with an outline of the proof ideas. 
-	On the other side, it would be helpful for the reader to have a paragraph or two summarizing the main steps or ideas of the proofs of the main theorems. 
-	One of the main claim of this work is that the bounds derived do not depend on the dimension. These bounds include the optimal adversarial risk (defined in equation 2.2), therefore, this quantity should not depend on the dimension. Whether this is a direct consequence of the definition or of Theorem 1, I don’t see it mentioned in the main text. 
-	Several concepts and notations are not clearly defined, and it sometimes affect the understanding of the results. My main concern is the lack of a definition for the Landau notations in the main results. As a consequence, it is not clear whether or not the obtained bounds are non-asymptotic or asymptotic and if they are, with respect to which variable.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: Second row of Figure 1: why having $W$ fixed at SD training plateaus, while continuing to train $W$ improves the performance? Doesn't it contradict the theoretical results, since according to Algorithm 1, one should not update $W$ after the first stage? 

Why for the numerical experiments Algorithms 2,3 are not used?
soundness: 3
strengths: The question of robust learning in the multi-index model is well-motivated by the authors. Authors clearly state the assumptions and limitations of their results.

As the main result, authors prove that in the multi-index model, sample complexity of adversarial training is the same as in standard training. They combine prior work on feature learning with a second stage adversarial training which requires careful technical analysis. Authors also provide experiments to support their claim.
summary: This work considers robust learning in the multi-index model for two-layer ReLU networks. In particular, authors study the setting of worst-case $\ell_2$-perturbation of the input and the problem of regression with squared loss. 

They propose the following two-stage method to find a set of parameters (weight of the first layer and readout vector):
First, algorithm finds a low-dimensional subspace, on which the target function depends. This is done using non-adversarial training, using prior feature learner methods. 
Using this subspace, adversarial training is done on the readout vector.
weaknesses: Authors highlight themselves that the result is limited to $\ell_2$ norm of perturbations. Some discussion on the extension to $\ell_\infty$ norm is lacking, i.e., why current proof techniques cannot tackle this setting.

Furthermore Theorem 1, which is central for the results of the paper, relies on the squared loss assumption. For classification tasks, which is a standard setting for adversarial robustness, logistic loss would be a more natural choice.  

Organization of the main text is hard to follow, theorems for SFL and DFL are more or less copy each other, but stated in different places. Since only one proof (out of four Theorems 4-7) is given in the Appendix, possibly a cleaner way to present the results is to combine Theorems 4&5 together, and show Theorems 6&7 as a corollary under additional assumption (with a separate proof).

Proof of Lemma 16 in the Appendix is hard to follow because of typos (line 894, should be $A_i (a_i - a'_i)$), and also $\tilde k_i$ is defined with $k_i$ and $k'_i$ in line 899, but both $k_i, k'_i$ are not defined at this point. I think what authors wanted to say is that $k_i, k'_i$ is defined with $\tilde k_i$, which is obtained through Mauery's lemma. It is confusing as it is written now.

Numerical experiments can also be improved, see Questions.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: Asked above.
soundness: 3
strengths: The contribution is good because it is a new theoretical study for adversarial feature learning for learning multi index models, which has been gaining traction recently. Their main results highlight that robust learning is achievable without a significant increase (at least for some functions) in sample complexity. Moreover, the oracles assumed for learning the target subspace can be realized by training the first layer in a 2 layered neural network. Overall, this is a well structured, theoretically sound work with a good upshot and I recommend an accept.
summary: The authors study the problem of $\ell_2$-constrained adversarial regression under a multi-index model setting. Specifically, in this setting, the conditional form of $y\vert x = g(\{\langle u_i, x\rangle\}_{i \in [k]})$ holds, where $u_i$ are the weights (or features) to be learned, $g:\mathbb R^k \to \mathbb R$ is the link function and $x,y$ are the covariates and target, respectively. 

Their main result shows that under the assumption that the model relevant co ordinates $Ux$ (for $U \in \mathbb R^{k \times d}$) and model irrelevant co ordinates $\tilde Ux$ ( $\tilde U \in \mathbb R^{(k-d)\times d}$) are statistically independent, there is a learning method that attains a Bayes optimal adversarial risk. 

This is achieved through access of oracles which can be realized through gradient based methods, with additional assumptions on the data distribution and for a certain class of prediction functions, such as variants of Lipschitz and polynomials. 

Under the assumption that the predictor is a "pseudo"-Lipschitz, the sample complexity is not dependent on the data dimension, though it has an exponential dependence on $k$; for polynomial predictors, their sample complexity results do not depend on k. 


They do not analyze the computational complexity of this problem, and provide empirical evidence by comparing training approaches including initializations based on a known $u$ and fully adversarial training.
weaknesses: I would like to reiterate a few points they already raised. Firstly, for the case of pseudo-Lipschitz functions, while the sample complexity is independent of $d$, there is an exponential dependence on $k$, which seems quite high. 

I also think that many mathematical terms could benefit with more intuitions for the first time reader. For example, a minor point of clarification would be in Theorem 1, where it would be helpful to specify the random variables with respect to which the expectation is taken in the towering property, $\mathbb E_X[\cdot] = \mathbb E_Y[\mathbb E_X[\cdot \vert x,y]$. 

It is also somewhat unclear to me what $\beta$ represents in the SFL oracle and also if a lower bound on $d\mu/d \tau_k$ connects to the Assumption 1. Moreover, I also think that Assumption 1 does not hold for natural scenarios where $x$ has a low rank structure where $\tilde Ux$ may not vary independently from $Ux$.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 4
questions: 1. Can you provide insights or intuitions about the validity of your results beyond Assumption 1? Have you numerically tested your algorithmic framework in settings that do not satisfy this assumption?

2. In lines 384-388, you claim that your results in this section can be readily extended to the setting of anisotropic Gaussian $x$, which seems to contrast with Assumption 1. Is it still possible to leverage Theorems 4-7 in this case?


3. I believe there is a typo in equation (4.1), where $y$ should instead be $y^{(i)}$.
soundness: 4
strengths: This paper
* presents results with clarity and precision, offering complete proofs, insightful comments, and remarks that make the content accessible and well-structured
* leverages previous results and introduces interesting, non-trivial findings in a rigorous framework (e.g. the possibility of performing standard feature learning to obtain optimal adversarial risk)
* validates its theoretical results with numerical simulations
* acknowledges its limitations and open problems.
summary: This paper explores the robust feature learning properties of two-layer neural networks for learning multi-index models in high-dimensional settings, under $\ell_2$-bounded perturbations. In particular, the authors show that Bayes-optimal adversarial risk can be achieved by neural networks once the input data are projected onto the low-dimensional manifold defined by the target multi-index model (first-layer feature learning) and the second layer is trained by minimizing the empirical adversarial risk. They demonstrate that the resulting sample complexity is independent of the ambient dimension. Leveraging prior results, the paper provides guarantees for robustly learning multi-index models with gradient-based algorithms and includes numerical simulations to support its findings.
weaknesses: I did not find any major weaknesses in this work. A minor issue would be the reliance of the results on the assumption of independence between the coordinates $x_\parallel$ and $x_\perp$ (Assumption 1), see also my question 1.

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 2
questions: 1.  **The assumption on the data distribution:** 
     + a) The authors mention that inputs can be Gaussian vectors with isotropic covariance, but what are other examples satisfying this assumption? For example, can we have anisotropic covariance (e.g., spiked covariance)? What if the covariance matrix and the projection matrix $U$ are aligned?
     + b) The authors mention (in Line 388) that "Our results readily extend to these settings as well," referring to non-isotropic Gaussian inputs and non-Gaussian symmetric input distributions. How so?

2. **Numerical results:** 
    + a) What is the step size for the gradient descent step on the perturbed batch for Figure 1?
    + b) What do shaded error bands denote in Figure 1? If variance, how much variance is illustrated?
    + c) Why do we see oscillating robust test risk for the two cases other than the full adversarial (full AD) training, while the robust test risk for the full adversarial training seems to be smooth in Figure 1? Furhermore, the robust test risk for full AD seems to converge fast while those for the other two cases do not seem converge even at the end of the iterations. Why so? 
    + d) The authors provide theoretical results on polynomial predictors in Section 4.1. A natural question is, "How does polynomial activation compare to ReLU activation in numerical results?". 
    + e) Prior work (Hassani & Javanmard, 2024) showed that adversary budget $\epsilon$ can significantly impact the robust test risk in their setting. How does adversary budget $\epsilon$ affect the robust test risk here? Similarly, what is the impact of dimensions and the number of samples?

3. The authors mention $\zeta^{(k-1)/2}$ as "the normalizing factor" in Line 239. But, $\zeta$ on its own deserves an explanation since it appears in most of the theorems. What does $\zeta$ intuitively correspond to?

4. **Minor issues:**
    + Some non-standard notations are used without definition. For example, soft O notation $\tilde{\mathcal{O}}$ and its counterparts for $\Omega$ and $\Theta$ should be mentioned in the "Notation" paragraph starting in Line 122.
    + There seems like a notational abuse when using the aforementioned asymptotic notations. There is asymptotic notation inside another asymptotic notation (e.g., in Theorem 4): $N \geq \tilde{\Omega}(\cdot^{\mathcal{O}(k)})$. Indeed, the authors assume $k = \mathcal{O}(1)$ in Line 154, which means $k < C$ for some $C > 0$. So, these equations can be simplified, and the notational abuse can be fixed at the expense of introducing one additional constant. Furthermore, note that the asymptotic notations are conventionally used with equality sign $(=)$ instead of $\leq$ or $\geq$.
    + In Line 135, the authors define the family of prediction functions to be "non-parametric". However, they then use two-layer neural networks as a prediction function in Line 140 or d-variate polynomials as the family of prediction functions in Section 4.1, which are "parametric" families of functions. There seems to be a contradiction here. Or am I missing something?
    + Ranges of $\alpha$ and $\beta$ are missing from Definitions 2-3.
    + Complexity results provided in Theorem 4-7 reduce the readability of main text since they include many parameters related to the setting. I think that the author can provide more insightful presentation of these results showing the essence.
soundness: 3
strengths: - **Interesting problem:** Understanding the effects of adversarial training of neural networks on the sample complexity may be significant for the deep learning literature. Furthermore, this paper combines two lines of work: 1) feature learning in two-layer neural networks and 2) adversarially robust learning in linear and random feature models.

- **Theoretical study under reasonable assumptions:** The authors study the problem under reasonable assumptions (in line with the prior work about such as Hassani & Javanmard, 2024).

- **Provides a valuable insight into the problem:** The paper shows that the adversarial training does not significantly (in the order of dimensions) affect the sample complexity in comparison to standard training.

- **Good enough presentation:** The paper answers most of the questions a reader may have, which is the main criterion when assessing the quality of the presentation. However, I think it is not an easy-to-follow paper. Instead, some parts of the paper require back-and-forth reading, which may be acceptable for such a theoretical paper.
summary: This paper studies the adversarial training of two-layer neural networks on learning multi-index target function (a function of a low-dimensional projection of the input) under squared loss. Under some assumptions, the authors first show that there exists an optimal low-dimensional projection (of inputs) for robustness against $l_2$ adversarial perturbations (Theorem 1). They then provide conditions for the first layer weights to satisfy such that the optimal low-dimensional projection matrix and the first layer matrix are partially aligned (Definition 2-3). Since there exist practical feature learning algorithms (examples given in Section 4.2) satisfying these conditions (definitions), they focus on the case where only the second layer is trained with adversarial loss while the first layer is pre-trained with a standard (not adversarial) feature learning algorithm. This simplification allows them to study the adversarial training of the second layer mainly. In this setting, the paper shows that adversarial training does not significantly affect the sample complexity of learning the target function. Specifically, the number of additional samples required for adversarial training (in comparison to standard training) is shown to be independent of the input dimension (Theorem 4-7). Thus, the authors conclude that adversarial learning in this setting is as easy as standard feature learning.
weaknesses: - **No characterization of robust test risk:** Prior works such as (Hassani & Javanmard, 2024) provide an asymptotic characterization of robust test risk for random feature models, which allows them to show how factors such as dimensions or perturbation budget $\epsilon$ impact the robust test risk. However, this work just focuses on the sample complexities and ignores the characterization of robust test risk. 

- **Significant gap to practice:** Although the assumptions are reasonable from a theoretical perspective, they differ significantly from practical adversarially robust learning.
   + **Data assumption:** Input is assumed to be subGaussian with constant subGaussian norm in Assumption 2. Furthermore, Assumption 1 imposes an implicit assumption on inputs and labels (target function), which needs further discussion (please see Question 1 about this below).
   + **The first layer is also trained with adversarial loss in practice:** While it seems like the adversarial training of the first layer hurts the robust test risk in Figure 1, this requires explanation (mentioned as future work in the conclusion). Thus, adversarial training of the first layer  is missing in this work.
   + **Limitation of $l_2$ perturbations:** The paper only studies adversarial training with $l_2$-bounded perturbations. Although $l_2$ perturbations for the adversarial training may be a good starting point considering the prior work on the theory of robust learning (Hassani & Javanmard, 2024), $l_{\infty}$ is primarily used in empirical studies as mentioned by the authors.
   + **Assumption on perturbation budget $\epsilon$:** The paper assumes constant adversary budget $\epsilon = \mathcal{O}(1)$ and justifies it by saying even this much perturbation can significantly perturb the output of the prediction function. However, as the authors noted, $\mathbb{E}[||\mathbf{x}||] = \mathcal{O}(\sqrt{d})$ and thus perturbation budget of $\epsilon = \mathcal{O}(\sqrt{d})$ is used in practice, which causes another discrepancy between the assumptions and practice.
   +  **Only polynomial and ReLU activation functions are considered.**

- **Limited numerical results and limited discussion of those results:**  
   + Most of Section 5 (Numerical Experiments) describes the experimental setting, while only one or two sentences discuss the results. There should be a more insightful discussion of the numerical results and their relation to the theoretical results.
   + There are some missing details about Figure 1 (please see Question 2.a-b below).
   + Effects of some parameters of the setting should be illustrated numerically or at least discussed: 1) activation function (polynomial vs ReLU), 2) different values for adversary budget $\epsilon$, 3) dimensions and number of samples.

Meta-review: **(a) Summarize the scientific claims and findings of the paper based on your own reading and characterizations from the reviewers.**  
The paper explores adversarially robust learning in multi-index models for two-layer neural networks. The authors demonstrate that under specific assumptions, the Bayes-optimal adversarial risk can be achieved with adversarial training focused on the second layer while leveraging standard training for the first layer. The main theoretical finding is that adversarial training does not significantly increase the sample complexity compared to standard training. The work also introduces robust feature learning formulations and supports its claims with numerical experiments, highlighting scenarios where adversarial training is as efficient as standard training.

**(b) What are the strengths of the paper?**  
- Provides a rigorous theoretical foundation linking adversarial robustness to feature learning in multi-index models.  
- Demonstrates that robust training can be accomplished without a significant sample complexity penalty.  
- Offers a novel approach that combines standard feature learning with adversarially fine-tuning the second layer.  
- Clear explanations of assumptions and limitations, accompanied by detailed proofs.  
- Numerical experiments validate theoretical results, adding practical relevance.  

**(c) What are the weaknesses of the paper? What might be missing in the submission?**  
- Limited empirical results and lack of exploration of practical scenarios beyond theoretical assumptions.  
- Focuses exclusively on \( \ell_2 \)-norm adversarial perturbations without extending to other norms like \( \ell_\infty \), which are more commonly used in practice.  
- Relies on assumptions such as statistical independence of features (Assumption 1), which may not always hold in realistic settings.  
- Limited discussion on computational complexity or real-world applicability of the proposed methods.  

**(d) Provide the most important reasons for your decision to accept/reject.**  
I recommend acceptance due to the paper’s strong theoretical contributions to understanding adversarial robustness in multi-index models and its potential to inform future work in the domain. While there are gaps in practical applicability and empirical analysis, the paper opens up promising avenues for further research and sets a robust theoretical foundation.

Decision: Accept (Poster)