††footnotetext: E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
# Intrinsic dimensionality and generalization properties of the
$\mathcal{R}$-norm inductive bias

Navid Ardeshir  Columbia University  Daniel Hsu  Columbia University  Clayton
Sanford  Columbia University

###### Abstract

We study the structural and statistical properties of $\mathcal{R}$-norm
minimizing interpolants of datasets labeled by specific target functions. The
$\mathcal{R}$-norm is the basis of an inductive bias for two-layer neural
networks, recently introduced to capture the functional effect of controlling
the size of network weights, independently of the network width. We find that
these interpolants are intrinsically multivariate functions, even when there
are ridge functions that fit the data, and also that the $\mathcal{R}$-norm
inductive bias is not sufficient for achieving statistically optimal
generalization for certain learning problems. Altogether, these results shed
new light on an inductive bias that is connected to practical neural network
training.

##  1 Introduction

The study of inductive biases in neural network learning is important for
theoretical understanding and for developing practical guidance in network
training. Recent theories of generalization rely on inductive biases of
training algorithms to explain how neural nets that (nearly) interpolate
training data can be accurate out-of-sample (Neyshabur et al., 2015; Zhang et
al., 2021). When inductive biases are made explicit and their effects are
elucidated, they can be incorporated into training procedures when deemed
appropriate for a problem at hand.

In this paper, we study the inductive bias for two-layer neural networks
implied by a variational norm called the _$\mathcal{R}$ -norm_, introduced by
Savarese et al. (2019) and Ongie et al. (2019) to capture the functional
effect of controlling the size of network weights. (A definition is given in
Section 2.2.) We focus on the _approximation_ and _generalization_
consequences of preferring networks with small $\mathcal{R}$-norm in the
context of learning explicit target functions. It is well-known that the size
of the weights can play a critical role in generalization properties of neural
networks (Bartlett, 1996), and weight-decay regularization is a common
practice in gradient-based training (Hinton, 1987; Hanson and Pratt, 1988).
Thus, explicating the consequences of the $\mathcal{R}$-norm inductive bias
may advance our understanding of generalization in practical settings.

We investigate the $d$-dimensional variational problem (VP), which seeks a
neural net $g\colon\varOmega\to\mathbb{R}$ of minimum $\mathcal{R}$-norm among
those that perfectly fit a given labeled dataset
$\\{(x_{i},y_{i})\\}_{i\in[n]}\subset\varOmega\times\mathbb{R}$:

$\displaystyle\inf_{g\colon\varOmega\to\mathbb{R}}\left\|g\right\|_{\mathcal{R}}$
$\displaystyle\quad\text{s.t.}\quad\;\;g(x_{i})=y_{i}$ $\displaystyle\forall
i\in[n];$ (VP) as well as a variant ($\epsilon$-VP) that only requires $g$ to
uniformly approximate labels up to error $\epsilon\in(0,1)$:
$\displaystyle\inf_{g\colon\varOmega\to\mathbb{R}}\left\|g\right\|_{\mathcal{R}}$
$\displaystyle\quad\text{s.t.}\quad\left|g(x_{i})-y_{i}\right|\leq\epsilon$
$\displaystyle\forall i\in[n].$ ($\epsilon$-VP)

Here, $\varOmega\subset\mathbb{R}^{d}$ is a $d$-dimensional domain of
interest. We study structural and statistical properties of solutions to these
problems for datasets labeled by specific target functions in high dimensions.

The recent introduction of the $\mathcal{R}$-norm and its connections to
weight-decay regularization have catalyzed research on the foundational
properties of solutions to (VP). In particular, solutions in the one-
dimensional ($d=1$) setting have been precisely characterized and their
generalization properties are now well-understood by their connections to
splines (Debarre et al., 2022; Savarese et al., 2019; Parhi and Nowak, 2021a;
Hanin, 2021). However, far less is known about the solutions of
$\mathcal{R}$-norm-minimizing interpolants for the general $d$-dimensional
case.

##### Key message.

Inductive biases based on certain variational norms, such as the
$\mathcal{R}$-norm, are believed to offer a way around the curse of
dimensionality suffered by kernel methods, because they are adaptive to low-
dimensional structure. Researchers have pointed to this adaptivity property in
non-parametric settings (Bach, 2017; Parhi and Nowak, 2021b) and specific
learning tasks with low-dimensional structure (Wei et al., 2019) as
mathematical evidence of the statistical advantage of neural networks over
kernel methods. One may hypothesize that the $\mathcal{R}$-norm inductive bias
achieves this advantage by favoring functions with low-dimensional structure.
Indeed, many other forms of inductive bias used in statistics and machine
learning are known to explicitly identify relevant low-dimensional structure
(Candès et al., 2006; Donoho, 2006; Candès and Recht, 2009; Bhojanapalli et
al., 2016; Barak et al., 2022; Damian et al., 2022; Frei et al., 2022;
Mousavi-Hosseini et al., 2022; Galanti et al., 2022). Our results provide
theoretical evidence that this is not always the case with the
$\mathcal{R}$-norm inductive bias, in a very strong sense that becomes more
pronounced in higher dimensions.

We show that, even in cases where the dataset can be perfectly fit by an
intrinsically one-dimensional function, the solutions $g$ to (VP) or
($\epsilon$-VP) are not necessarily the piecewise-linear ridge functions
described in previous works (Savarese et al., 2019; Hanin, 2021). Rather, the
$\mathcal{R}$-norm is far better minimized by a _multi-directional_ 111By a
multi-directional function, we mean a function that does not _only_ depend on
a one-dimensional projection of its input—i.e., a function that is not a ridge
function (defined in Section 2.1). neural network $g$ that averages several
ridge functions pointing in different directions, each of which approximates a
small fraction of the data.

###  1.1 Our contributions

Our results are summarized by the following informal theorems concerning the
structural and generalization properties of $\mathcal{R}$-norm interpolation.
Together, they show that the $\mathcal{R}$-norm inductive bias (1) leads to
interpolants that are qualitatively different from those that minimize width
or intrinsic dimensionality of the learned network, and (2) is insufficient
for obtaining optimal generalization for a well-studied learning problem.

######  Informal Theorem 1 ($\mathcal{R}$-norm minimizers of the parity
dataset are not ridge functions).

Suppose the dataset $\\{(x_{i},y_{i})\\}_{i\in[n]}\subset\\{\pm
1\\}^{d}\times\\{\pm 1\\}$ used in (VP) and ($\epsilon$-VP) is the complete
dataset of $2^{d}$ examples labeled by the $d$-variable parity function.

  * •

The optimal value of (VP) is $\Theta(d)$.

  * •

The optimal value of ($\epsilon$-VP) for any $\epsilon\in[0,1/2)$—with the
additional constraint that $g$ be a ridge function—is $\Theta(d^{3/2})$.

This result is presented formally in Section 3. In Section 3.1, we show that
every ridge function satisfying the constraints of ($\epsilon$-VP) has
$\mathcal{R}$-norm at least $\Omega(d^{3/2})$; this bound is tight for ridge
functions, as there is a matching upper bound. Using an averaging strategy, we
show in Section 3.2 the existence of multi-directional interpolants $g$ of the
parity dataset with $\left\|g\right\|_{\mathcal{R}}=O(d)$, and we also
establish the optimality of this construction in Section 3.3. These results
characterize the optimal value of (VP) in terms of the dimension $d$, and also
establish the $\mathcal{R}$-norm-suboptimality of ridge function interpolants.
(In Section 5, we extend the averaging strategy to other types of target
functions, expanding the scope of our structural findings.)

######  Informal Theorem 2 (Min-$\mathcal{R}$-norm interpolation is sub-
optimal for learning parities).

Suppose the dataset
$\\{({\mathbf{x}}_{i},\chi({\mathbf{x}}_{i}))\\}_{i\in[n]}\subset\\{\pm
1\\}^{d}\times\\{\pm 1\\}$ used in (VP) is an i.i.d. sample, where
${\mathbf{x}}_{i}\sim\operatorname{Unif}(\\{\pm 1\\}^{d})$ is labeled by the
$d$-variable parity function $\chi$ for all $i\in[n]$. If the sample size is
$n=o(d^{2}/\sqrt{\log d})$, then with probability at least $1/2$, every
solution to (VP) has mean squared error at least $1-o(1)$ for predicting
$\chi$ over $\operatorname{Unif}(\\{\pm 1\\}^{d})$.

This result is presented formally in Section 4.1, and it is complemented by a
sample complexity upper bound in Section 4.2. The results are stated for the
parity function on all $d$ variables, but the same holds for any parity
function over $\Omega(d)$ variables. It is well-known that an i.i.d. sample of
size $O(d)$ is sufficient for learning parity functions exactly (Helmbold et
al., 1992; Fischer and Simon, 1992), and hence we conclude that the
$\mathcal{R}$-norm inductive bias is insufficient for achieving the
statistically optimal sample complexity for this learning problem.

###  1.2 Related work

##### Variational norms and inductive biases of optimization methods.

Many variational norms (such as $\mathcal{R}$-norm) from functional analysis
can be regarded as representational costs that induce topologies on the space
of infinitely-wide neural networks with certain activation functions. Prior
works have analyzed these norms for homogeneous activation functions like ReLU
(e.g., Kurková and Sanguineti, 2001; Mhaskar, 2004; Bach, 2017; Savarese et
al., 2019; Ongie et al., 2019); see Siegel and Xu (2021) and references
therein for a comparison. In particular, the work of Ongie et al. (2019)
provided analytical descriptions of $\mathcal{R}$-norm in terms of the Radon
transform of the function itself. This work was extended to higher powers of
ReLU by Parhi and Nowak (2021a).

The variational norms are also connected to the implicit biases of
optimization methods for training neural networks. In the context of
univariate functions, the dynamics of gradient descent was shown to be biased
towards (adaptive) linear or cubic spline depending on the optimization regime
(Williams et al., 2019; Shevchenko et al., 2021; Maennel et al., 2018), and
these results have been partially extended to the multivariate case (Jin and
Montúfar, 2020). For classification problems, the implicit bias of gradient
descent was connected to a variational problem related to $\mathcal{R}$-norm
with margin constraints on the data (Bach and Chizat, 2021).

##### Solutions to the variational problem.

Debarre et al. (2022) and Hanin (2021) fully characterized the form of all
solutions of (VP) for one-dimensional datasets (as discussed above). However,
pinning down even a single solution for general multidimensional datasets
appears to be difficult; Ergen and Pilanci (2021) was able to do so for rank-
one datasets, where all the feature vectors lie on a line. The datasets we
study do not satisfy the rank-one condition of Ergen and Pilanci (2021), and
thus we require different techniques to analyze multi-directional functions.

##### Adaptivity.

In the context of non-parametric regression, it is well-known that (deep)
neural networks achieve minimax-optimal rates in the presence of low-
dimensional structure in the target function (e.g., Schmidt-Hieber, 2020;
Bauer and Kohler, 2019; Kohler and Krzyżak, 2005; Györfi et al., 2002). The
convergence rates in these works depend only on the intrinsic dimension of the
target function (and not the ambient dimension) and are achieved by optimally
trading off accuracy and regularization in certain deep neural network
architectures. Recent works (Klusowski and Barron, 2016; Parhi and Nowak,
2021b; Bach, 2017) consider two-layer neural networks with variational norm
(similar to $\mathcal{R}$-norm) regularization, which also allows for
adaptivity to low-dimensional structure. That is, a function
$g\colon\mathbb{R}^{d}\to\mathbb{R}$ depending only on a $k$-dimensional
projection of its input $x$, i.e., $g(x)=\phi(Ux)$ for some
$U\in\mathbb{R}^{k\times d}$ (with orthonormal rows) and
$\phi\colon\mathbb{R}^{k}\to\mathbb{R}$ has variational norm no greater than
that of the corresponding low-dimensional function $\phi$ (Bach, 2017). In
particular, Bach (2017) and Klusowski and Barron (2016) studied minimax rates
under ridge target functions where $k=1$. Our results on generalization are of
a different flavor: rather than striking a careful balance between fitting and
regularization to achieve minimax rates, we study the behavior of
$\mathcal{R}$-norm-minimizing interpolation.

Regularization based on weight decay (equivalent to $\mathcal{R}$-norm for
shallow networks) has also been used to obtain minimax rates for learning
smooth target functions. Parhi and Nowak (2021b) do so by drawing analogies to
spline theory, while Wang and Lin (2021) consider a connection to the Group
Lasso. Zhang and Wang (2022) exploits depth to promote stronger sparsity
regularizes. This is distinct from the low-dimensional structures studied in
this work and mentioned above.

##### Learning ridge functions and parity functions with neural nets.

Target functions that depend on low-dimensional projections of the input (of
which ridge functions are the simplest case) have been long studied in
statistics (see, e.g., Li, 2018), and learning such functions is one of the
simplest problems where neural network training demonstrates adaptivity. Such
demonstrations typically require going beyond the neural tangent kernel regime
and have been used to explain the “feature learning” ability of neural
networks (Frei et al., 2022; Damian et al., 2022; Mousavi-Hosseini et al.,
2022; Bietti et al., 2022). Several recent works have considered the prospects
of learning (sparse) parity functions by training neural nets with gradient-
based algorithms (Abbe and Sandon, 2020; Daniely and Malach, 2020; Malach et
al., 2021; Barak et al., 2022; Telgarsky, 2022). The positive results express
parities as low-weight linear combinations of (random) ReLUs, which motivates
our focus on the variational norm of approximating neural nets. Our sample
complexity lower bound shows that, even if computational and optimization
considerations are set aside, the inductive bias imposed by the
$\mathcal{R}$-norm may lead to suboptimal statistical performance.

##### Averaging and ensembling.

Neural networks have been interpreted as forms of averaging or ensemble
methods to explain their statistical properties (e.g., Bartlett, 1996; Baldi
and Sadowski, 2013; Gal and Ghahramani, 2016; Olson et al., 2018). Our use of
averaging is different in that it serves as an approximation-theoretic
mechanism for achieving smaller $\mathcal{R}$-norm.

##### Weight lower bounds for other explicit functions.

Representation costs for two-layer neural networks to approximate other
explicit functions have been explored in several prior works (Martens et al.,
2013; Daniely, 2017; Safran and Shamir, 2017; Safran et al., 2019). These
works establish exponential lower-bounds on the width of two-layer networks
needed to approximate functions that are represented more compactly by three-
layer networks. These results also imply lower-bounds on the size of second-
layer weights in a two-layer network after fixing the width of the network. In
contrast, our results hold for networks of unbounded width and for a target
function that can be exactly represented by a two-layer networks of
$\operatorname*{poly}(d)$ width.

##  2 Preliminaries

###  2.1 Notation

In this work, we consider real-valued functions over the radius-$\sqrt{d}$
Euclidean ball $\varOmega:=\\{x\in\mathbb{R}^{d}:\|x\|_{2}\leq\sqrt{d}\\}$.
Let $\chi_{S}\colon\varOmega\to\\{\pm 1\\}$ denote the multi-linear monomial
$\chi_{S}(x):=\prod_{i\in S}x_{i}$ over variables indexed by $S\subseteq[d]$,
and let $\chi:=\chi_{[d]}$. On input $x\in\\{\pm 1\\}^{d}$, $\chi_{S}(x)$
computes the _parity_ of $\\{x_{i}:i\in S\\}$. We say
$g\colon\varOmega\to\mathbb{R}$ is a _ridge function_ if
$g(x)=\phi(v^{\scriptscriptstyle{\mathsf{T}}}x)$ for some unit vector
$v\in\mathbb{S}^{d-1}$ and function
$\phi\colon[-\sqrt{d},\sqrt{d}]\to\mathbb{R}$. A function $\phi$ is _$\rho$
-periodic_ if $\phi(z+\rho)=\phi(z)$ for all $z\in\mathbb{R}$.

We consider two-layer neural networks (of infinite and finite width) with ReLU
activations $\varphi_{\operatorname{r}}(z):=\max\\{0,z\\}$. Let $\mathcal{M}$
denote the space of signed measures over
$\mathbb{S}^{d-1}\times[-\sqrt{d},\sqrt{d}]$. For $\mu\in\mathcal{M}$, let
$g_{\mu}:\varOmega\to\mathbb{R}$ denote the infinite-width neural network
given by

$g_{\mu}(x):=\int_{\mathbb{S}^{d-1}\times[-\sqrt{d},\sqrt{d}]}\varphi_{\operatorname{r}}(w^{\scriptscriptstyle{\mathsf{T}}}x+b)\,\mu(\operatorname{d\\!}w,\operatorname{d\\!}b).$

The total variation norm of $\mu$ is
$\left|\mu\right|:=\int_{\mathbb{S}^{d-1}\times[-\sqrt{d},\sqrt{d}]}\left|\mu\right|(\operatorname{d\\!}w,\operatorname{d\\!}b)$,
where $\left|\mu\right|(\operatorname{d\\!}w,\operatorname{d\\!}b)$ is the
corresponding total variation measure (somewhat abusing notation). The
width-$m$ neural network $g_{\theta}$ with parameters
$\theta=(a^{(j)},w^{(j)},b^{(j)})_{j\in[m]}\in(\mathbb{R}\times\mathbb{S}^{d-1}\times[-\sqrt{d},\sqrt{d}])^{m}$
is given by

$g_{\theta}(x):=\sum_{j=1}^{m}a^{(j)}\varphi_{\operatorname{r}}(w^{(j){\scriptscriptstyle{\mathsf{T}}}}x+b^{(j)}).$

We regard $g_{\theta}$ as an infinite-width neural network with the “sparse”
atomic measure

$\mu_{\theta}=\sum_{j=1}^{m}a^{(j)}\delta_{(w^{(j)},b^{(j)})}.$

Observe that $g_{\theta}=g_{\mu_{\theta}}$ and
$\left|\mu_{\theta}\right|=\sum_{j=1}^{m}|a^{(j)}|=\|a\|_{1}$.

Our constructions frequently use sawtooth functions, a family of ridge
functions that are composed of $t+1$ repetitions of a triangular wave that
draw inspiration from a construction of Yehudai and Shamir (2019, Proposition
4.2). For $t\in\\{0,\dots d\\}$ with $t\equiv d\pmod{2}$ and $w\in\\{\pm
1\\}^{d}$, let
$s_{w,t}(x):=\smash{(-1)^{d-t}\chi(w)\phi_{t}(w^{\scriptscriptstyle{\mathsf{T}}}x)}$
where $\phi_{t}:\mathbb{R}\to\mathbb{R}$ is a function that forms a piecewise
affine interpolation between the points $(-t-1,0)$,
$\smash{\\{(t-2\tau,(-1)^{\tau})\\}_{\tau\in\\{0,\dotsc,t\\}}}$, $(t+1,0)$,
and $\phi_{t}(z)=0$ for all $z\leq-t-1$ and $z\geq t+1$. We refer to $t$ as
the _width_ of the sawtooth function $s_{w,t}$. Note that $s_{w,t}$ is
$\sqrt{d}$-Lipschitz and
$s_{w,t}(x)=\chi(x)\mathbbm{1}\left\\{\left|w^{\scriptscriptstyle{\mathsf{T}}}x\right|\leq
t\right\\}$ for all $x\in\\{\pm 1\\}^{d}$. Also, $s_{w,t}$ can be expressed as
a neural network $g_{\theta}$ with width $m\leq O(t+1)$ and $|a^{(i)}|\leq
O(\sqrt{d})$ for each $i\in[m]$.

Let $\nu:=\operatorname{Unif}(\\{\pm 1\\}^{d})$ denote the uniform
distribution on $\\{\pm 1\\}^{d}$, and let $\boldsymbol{\nu}_{n}$ denote the
empirical distribution on
${\mathbf{x}}_{1},\dotsc,{\mathbf{x}}_{n}\sim_{\operatorname{iid}}\nu$. We use
the following inner products and norms over the vector space of real-valued
functions on $\\{\pm 1\\}^{d}$ with respect to a distribution $\nu_{0}$ (such
as $\nu$ or $\boldsymbol{\nu}_{n}$):

$\left\langle
g,h\right\rangle_{L^{2}(\nu_{0})}:=\operatorname{\mathbb{E}}\displaylimits_{{\mathbf{x}}\sim\nu_{0}}[g({\mathbf{x}})h({\mathbf{x}})],\quad\left\|g\right\|_{L^{2}(\nu_{0})}:=\left\langle
g,g\right\rangle_{L^{2}(\nu_{0})}^{1/2},\quad\left\|g\right\|_{L^{\infty}(\nu_{0})}:=\max_{x\in\operatorname{supp}(\nu_{0})}|g(x)|.$

###  2.2 $\mathcal{R}$-norm and attainment of the infimum

We now recall the definition of the $\mathcal{R}$-norm of a function
$g\colon\varOmega\to\mathbb{R}$, presented here in a variational form as the
minimum cost of representing $g$ as an infinite-width neural network with a
“skip-connection”:

$\left\|g\right\|_{\mathcal{R}}:=\inf_{\mu\in\mathcal{M},v\in\mathbb{R}^{d},c\in\mathbb{R}}\left|\mu\right|\quad\text{s.t.}\quad
g(x)=g_{\mu}(x)+v^{\scriptscriptstyle{\mathsf{T}}}x+c\ \ \forall
x\in\varOmega.$ ($\mathcal{R}$-norm)

Indeed, $\left\|\cdot\right\|_{\mathcal{R}}$ is a semi-norm on the space of
functions with finite $\mathcal{R}$-norm. It was initially introduced by Ongie
et al. (2019) along with explicit characterizations in terms of the Radon
transform. See the works of Ongie et al. (2019), Parhi and Nowak (2021a), and
Siegel and Xu (2021) for more discussion about the $\mathcal{R}$-norm and its
connections to other function spaces.

The appearance of the affine component $v^{\scriptscriptstyle{\mathsf{T}}}x+c$
in the definition of $\mathcal{R}$-norm has implications for how the bias
terms are treated. Notice that a neuron
$x\mapsto\varphi_{\operatorname{r}}(w^{\scriptscriptstyle{\mathsf{T}}}x+b)$
with bias $\left|b\right|\geq\sqrt{d}$ behaves as an affine function over the
domain of interest $\varOmega$, so it can be absorbed into the “free” affine
component (in the definition of $\mathcal{R}$-norm) so as to not be counted
towards the $\mathcal{R}$-norm. Other works (e.g., Siegel and Xu, 2021)
consider a different variational norm,
$\left\|\cdot\right\|_{\mathscr{V}_{2}}$, which does not have “free” affine
components, but instead permits biases $b$ to be in the larger range
$[-2\sqrt{d},2\sqrt{d}]$. These differences in the way affine components are
accommodated do not lead to different function spaces (see Parhi and Nowak,
2021b, Theorem 6), and the results of this paper for $\mathcal{R}$-norm also
hold for these other variational norms, as we demonstrate in Appendix C.

Although the $\mathcal{R}$-norm is defined in terms of an infimum, it has been
shown by Parhi and Nowak (2021b, Lemma 2; see also Proposition 1 in Appendix
B) that the infimum is always achieved by a particular signed measure
$\mu\in\mathcal{M}$. Since the total variation norm is sparsity-inducing, the
objective in (VP) favors finite-width networks. It can be shown, using an
extension of Caratheodory’s theorem (Rosset et al., 2007), that (VP) in fact
always has a finite-width solution. That is, (VP) is solved by the sum of an
affine function $x\mapsto v^{\scriptscriptstyle{\mathsf{T}}}x+c$ and a
width-$m$ neural network, for some $m\leq\max\\{0,n-(d+1)\\}$. This claim is
formalized as Theorem 20 and proved in Appendix B. Thus, considering finite-
width neural networks is sufficient to determine the value of (VP).222We note
that the finite-width solution to (VP) is not necessarily unique; Hanin (2021)
discusses this issue in the one-dimensional case ($d=1$) under general data
models.

The following lemma, which is a minor elaboration on Lemma 25 of Parhi and
Nowak (2021a), relates the $\mathcal{R}$-norm of a finite-width network to the
$\ell_{1}$-norm of its top-layer weights.

######  Lemma 1.

Let $v\in\mathbb{R}^{d}$, $c\in\mathbb{R}$, and
$\theta=(a^{(j)},w^{(j)},b^{(j)})_{j\in[m]}\in(\mathbb{R}\times\mathbb{S}^{d-1}\times[-\sqrt{d},\sqrt{d}])^{m}$
be the set of parameters of a finite neural network where
$(w^{(i)},b^{(i)})\neq(w^{(j)},b^{(j)})$ for all $i\neq j$.

  1. (i)

The $\mathcal{R}$-norm of the sum of $g_{\theta}$ and an affine function
$v^{\scriptscriptstyle{\mathsf{T}}}x+c$ satisfies

$\left\|g_{\theta}(x)+v^{\scriptscriptstyle{\mathsf{T}}}x+c\right\|_{\mathcal{R}}\leq\left\|a\right\|_{1}=|a^{(1)}|+\dotsb+|a^{(m)}|.$
(1)

  2. (ii)

Moreover, if the measure $\mu_{\theta}$ is even in a distributional sense
(i.e., $\mu_{\theta}(w,b)=\mu_{\theta}(-w,-b)$), then the inequality in (1)
holds with equality.

Note that our assumption that $\mu_{\theta}$ is even in Lemma 1(ii) precludes
the case where $a^{(i)}=-a^{(j)}$ and $(w^{(i)},b^{(i)})=(-w^{(j)},-b^{(j)})$
for some $i\neq j$. This is needed because if such a case were allowed, we
would have
$a^{(i)}\varphi_{\operatorname{r}}(w^{(i){\scriptscriptstyle{\mathsf{T}}}}x+b^{(i)})+a^{(j)}\varphi_{\operatorname{r}}(w^{(j){\scriptscriptstyle{\mathsf{T}}}}x+b_{j})=a^{(i)}(w^{(i){\scriptscriptstyle{\mathsf{T}}}}x+b^{(i)})$
for all $x\in\varOmega$—an affine function. After ruling out these cases, we
can apply the argument of Parhi and Nowak (2021a) to prove Lemma 1(ii).

###  2.3 $\mathcal{R}$-norm of ridge functions

Prior works illuminate precise formulations of the $\mathcal{R}$-norm, and
characterize solutions to (VP), albeit only for the one-dimensional setting
(Hanin, 2021; Savarese et al., 2019; Ergen and Pilanci, 2021). These results
are nevertheless useful for analyzing ridge functions in $d$-dimensional
space.

######  Theorem 2.

For any ridge function $g\colon\varOmega\to\mathbb{R}$ of the form
$g(x)=\phi(w^{\scriptscriptstyle{\mathsf{T}}}x)$ where $w\in\mathbb{S}^{d-1}$
and $\phi\colon[-\sqrt{d},\sqrt{d}]\to\mathbb{R}$ is Lipschitz, we have

$\left\|g\right\|_{\mathcal{R}}=\left\|\phi^{\prime}\right\|_{\operatorname{TV}}\coloneqq\operatorname*{ess\,sup}_{-\sqrt{d}\leq
t_{0}<t_{1}<\dotsb<t_{r}\leq\sqrt{d};\,r\in\mathbb{N}}\sum_{i=1}^{r}\left|\phi^{\prime}(t_{i})-\phi^{\prime}(t_{i-1})\right|,$

where $\phi^{\prime}$ is a right continuous derivative of $\phi$.333Take
$\phi^{\prime}(u)=\lim_{t\downarrow 0}{\frac{\phi(u+t)-\phi(u)}{t}}$; the
limit exists almost everywhere by Rademacher’s theorem.

######  Remark 1.

If $\phi$ is twice differentiable, then
$\left\|g\right\|_{\mathcal{R}}=\int_{-\sqrt{d}}^{\sqrt{d}}{|\phi^{\prime\prime}(u)|\operatorname{d\\!}u}=\left\|\phi^{\prime\prime}\right\|_{1}$.
Intuitively, this $\ell_{1}$-norm penalty induces sparsity in the second
derivative, leading to representations that use few neurons. In contrast,
minimizing the $\ell_{2}$-norm penalty
$\left\|\phi^{\prime\prime}\right\|_{2}$ on the second derivative yields a
cubic spline (Kimeldorf and Wahba, 1971).

###### Proof.

Without loss of generality, $g$ only depends on the first coordinate $x_{1}$
due to the invariance of the $\mathcal{R}$-norm to rotation (cf. Proposition
11 of Ongie et al., 2019). The result then follows from Remark 4 of Parhi and
Nowak (2021b). ∎

This bound on the $\mathcal{R}$-norm for ridge functions (and univariate
functions) is critical for analyses of the solutions to (VP) for $d=1$ (Hanin,
2021; Savarese et al., 2019). It suggests a potential approach for our high-
dimensional setting: project the dataset to every one-dimensional subspace,
interpolate the data with a ridge function that points in that direction,
directly compute the $\mathcal{R}$-norm of each using Theorem 2, and return
the ridge function with the lowest $\mathcal{R}$-norm. In the sequel, we
examine the optimality of this approach, and find that ridge functions cannot
be optimal solutions to (VP), even when the dataset can be perfectly fit by a
ridge function.

##  3 Solutions to the variational problem for parity are multi-directional

In this section, we study the $\mathcal{R}$-norm of neural networks that solve
VP or $\epsilon$-VP for the (full) _parity dataset_ $\\{(x,\chi(x)):x\in\\{\pm
1\\}^{d}\\}$, which has size $n=2^{d}$. For simplicity, the labels are
provided by the parity function $\chi$ over all $d$ variables, although the
same quantitative results (up to constant factor differences) hold for any
$\chi_{S}$ with $|S|=\Theta(d)$.

The high level message is that, despite the fact that this dataset can be
exactly fit using ridge functions, the solutions to (VP) and ($\epsilon$-VP)
are _not_ ridge functions and instead must be multi-directional.

###  3.1 Every ridge parity interpolant has $\mathcal{R}$-norm
$\Omega(d^{3/2})$

We first show that any $\epsilon$-approximate interpolant of the parity
dataset _that is also a ridge function_ must have $\mathcal{R}$-norm
$\Omega(d^{3/2})$. This lower-bound is established even for $\epsilon=1/2$.

######  Theorem 3.

For $d\geq 2$, let $\operatorname{Ridge}_{d}$ be the set of functions
$g\colon\varOmega\to\mathbb{R}$ such that
$g(x)=\phi(w^{\scriptscriptstyle{\mathsf{T}}}x)$ for some
$w\in\mathbb{S}^{d-1}$ and Lipschitz continuous
$\phi\colon[-\sqrt{d},\sqrt{d}]\to\mathbb{R}$. Then

$\inf\\{\left\|g\right\|_{\mathcal{R}}:g\in\operatorname{Ridge}_{d},\,\left\|g-\chi\right\|_{L^{\infty}{(\nu)}}\leq
1/2\\}\geq d^{3/2}/(2\sqrt{2}).$

The proof constructs a labeled dataset of $d+1$ points, and shows that any
ridge function $g(x)=\phi(w^{\scriptscriptstyle{\mathsf{T}}}x)$ that
approximates that dataset must have many high-magnitude oscillations. These
oscillations imply a lower bound on
$\left\|\phi^{\prime}\right\|_{\operatorname{TV}}$, which proves the claim by
way of Theorem 2.

###### Proof.

Take any $g\in\operatorname{Ridge}_{d}$ of the form
$g(x)=\phi(w^{\scriptscriptstyle{\mathsf{T}}}x)$ for some function $\phi$ and
vector $w$ satisfying the approximation constraint
$\left\|g-\chi\right\|_{L^{\infty}{(\nu)}}\leq 1/2$. Suppose for sake of
contradiction that $w_{i}=0$ for some $i\in[d]$. Then, there exists a pair of
points $x,x^{\prime}\in\\{-1,1\\}^{d}$ that are identical except in the $i$-th
positions, $x_{i}$ and $x^{\prime}_{i}$. Thus, $\chi(x)=-\chi(x^{\prime})$,
but
$w^{\scriptscriptstyle{\mathsf{T}}}x=w^{\scriptscriptstyle{\mathsf{T}}}x^{\prime}$
and hence $g(x)=g(x^{\prime})$; this contradicts the approximation constraint.
So, we may henceforth assume that $w_{i}\neq 0$ for all $i\in[d]$.

For each $i\in\\{0,1,\dotsc,d\\}$, define

$x^{(i)}:=(\operatorname{sign}(w_{1}),\dots,\operatorname{sign}(w_{i}),-\operatorname{sign}(w_{i+1}),\dots,-\operatorname{sign}(w_{d})).$

Because the parity of $x^{(i)}$ alternates with $i$, i.e.,
$\chi(x^{(i)})\neq\chi(x^{(i+1)})$, $\operatorname{sign}(g(x^{(i)}))$ also
alternates because $g$ satisfies the approximation constraint. Furthermore,
again due to the approximation constraint, we have
$|g(x^{(i)})-g(x^{(i+1)})|\geq 1$. We claim that, because $\phi$ interpolates
$d+1$ well-separated data points
$(w^{\scriptscriptstyle{\mathsf{T}}}x^{(i)},\phi(w^{\scriptscriptstyle{\mathsf{T}}}x^{(i)}))$
that satisfy
$w^{\scriptscriptstyle{\mathsf{T}}}x^{(i)}<w^{\scriptscriptstyle{\mathsf{T}}}x^{(i+1)}$
for all $i\in\\{0,1,\dotsc,d-1\\}$, there must be a large cost for
representing $\phi$ using a neural network. By Theorem 2, it suffices to
obtain a lower bound on $\left\|\phi^{\prime}\right\|_{\operatorname{TV}}$,
since this will imply a lower bound on $\left\|g\right\|_{\mathcal{R}}$.

By Lemma 22 (in Appendix D.1; essentially the mean value theorem), for every
$i\in\\{0,1,\dotsc,d-1\\}$, there exists
$A_{i}\subseteq[w^{\scriptscriptstyle{\mathsf{T}}}x^{(i)},w^{\scriptscriptstyle{\mathsf{T}}}x^{(i+1)}]$
with Lebesgue measure $\operatorname{Leb}(A_{i})>0$ such that, for every
$z^{(i)}\in A_{i}$, we have

$|\phi^{\prime}(z^{(i)})|\geq\frac{1}{2}\cdot\frac{|\phi(w^{\scriptscriptstyle{\mathsf{T}}}x^{(i+1)})-\phi(w^{\scriptscriptstyle{\mathsf{T}}}x^{(i)})|}{w^{\scriptscriptstyle{\mathsf{T}}}x^{(i+1)}-w^{\scriptscriptstyle{\mathsf{T}}}x^{(i)}},$

and
$\smash{\operatorname{sign}\left(\phi^{\prime}(z^{(i)})\right)=\operatorname{sign}\left(\phi(w^{\scriptscriptstyle{\mathsf{T}}}x^{(i+1)})-\phi(w^{\scriptscriptstyle{\mathsf{T}}}x^{(i)})\right)}$.
The fact that the signs of $\phi(w^{\scriptscriptstyle{\mathsf{T}}}x^{(i)})$
alternate with $i$ implies that the signs of $\phi^{\prime}(z^{(i)})$ also
alternate with $i$. We now lower-bound the total variation of $\phi^{\prime}$
using the fact that $\prod_{i=1}^{d}\operatorname{Leb}(A_{i})>0$ and taking
advantage of the alternating signs:

$\displaystyle 2\left\|\phi^{\prime}\right\|_{\operatorname{TV}}$
$\displaystyle=2\operatorname*{ess\,sup}_{-\sqrt{d}\leq
t_{0}<t_{1}<\dotsb<t_{r}\leq\sqrt{d};\,r\in\mathbb{N}}\sum_{i=1}^{r}\left|\phi^{\prime}(t_{i})-\phi^{\prime}(t_{i-1})\right|$
$\displaystyle\geq
2\sum_{i=1}^{d-1}|\phi^{\prime}(z^{(i)})-\phi^{\prime}(z^{(i-1)})|=2\sum_{i=1}^{d-1}(|\phi^{\prime}(z^{(i)})|+|\phi^{\prime}(z^{(i-1)})|)\geq
2\sum_{i=0}^{d-1}|\phi^{\prime}(z^{(i)})|$
$\displaystyle\geq\sum_{i=0}^{d-1}\frac{|\phi(w^{\scriptscriptstyle{\mathsf{T}}}x^{(i+1)})-\phi(w^{\scriptscriptstyle{\mathsf{T}}}x^{(i)})|}{w^{\scriptscriptstyle{\mathsf{T}}}x^{(i+1)}-w^{\scriptscriptstyle{\mathsf{T}}}x^{(i)}}\geq\sum_{i=0}^{d-1}\frac{1}{w^{\scriptscriptstyle{\mathsf{T}}}x^{(i+1)}-w^{\scriptscriptstyle{\mathsf{T}}}x^{(i)}}$
$\displaystyle\geq\frac{d^{2}}{\sum_{i=0}^{d-1}w^{\scriptscriptstyle{\mathsf{T}}}x^{(i+1)}-w^{\scriptscriptstyle{\mathsf{T}}}x^{(i)}}=\frac{d^{2}}{w^{\scriptscriptstyle{\mathsf{T}}}x^{(d)}-w^{\scriptscriptstyle{\mathsf{T}}}x^{(0)}}\geq\frac{d^{2}}{\|w\|_{2}\|x^{(d)}-x^{(0)}\|_{2}}=\frac{d^{3/2}}{\sqrt{2}}.$

The second-to-last inequality is a consequence of Cauchy-Schwarz: for any
$a_{1},\dots,a_{d}>0$,
$d^{2}=\smash{(\sum_{i}\sqrt{a_{i}}/\sqrt{a_{i}})^{2}\leq(\sum_{i}a_{i})(\sum_{i}1/a_{i})}$.
Therefore,
$\left\|g\right\|_{\mathcal{R}}=\left\|\phi^{\prime}\right\|_{\operatorname{TV}}\geq
d^{3/2}/(2\sqrt{2})$. ∎

The lower-bound in Theorem 3 is tight up to constants, because the sawtooth
function $s_{\vec{1},d}$ satisfies the constraints of (VP) and has
$\left\|s_{\vec{1},d}\right\|_{\mathcal{R}}=O(d^{3/2})$.

###  3.2 Existence of a multi-directional parity interpolant with
$\mathcal{R}$-norm $O(d)$

We now show that the $\Omega(d^{3/2})$ $\mathcal{R}$-norm lower-bound from
Theorem 3 for ridge functions can be avoided by neural networks that are not
ridge functions. The main idea is to employ an _averaging strategy_ that
combines a collection of distinct ridge functions, each of which perfectly
fits a small fraction of the parity dataset—those on the “equator” relative to
the ridge direction—while ignoring the “outliers” in that direction. Because
all points on the cube are “outliers” for some directions and on the “equator”
for others, this strategy ultimately ensures that every example is perfectly
fit.

######  Theorem 4.

For any even444Our results also hold for odd $d$, but the proofs are more
tedious. $d$, there exists a neural network $g:\varOmega\to\mathbb{R}$ having
$g(x)=\chi(x)$ for all $x\in\\{\pm 1\\}^{d}$ such that
$\left\|g\right\|_{\mathcal{R}}\leq O(d)$.

###### Proof.

Recall that the sawtooth function $s_{w,0}:\varOmega\to\mathbb{R}$ satisfies
$s_{w,0}(x)=\chi(x)\mathbbm{1}\left\\{w^{\scriptscriptstyle{\mathsf{T}}}x=0\right\\}$
for all $x\in\\{\pm 1\\}^{d}$. By construction, $s_{w,0}$ is a ridge function
that is a single “bump” around zero in the direction of $w$, and
$\|s_{w,0}\|_{\mathcal{R}}\leq\smash{O(\sqrt{d})}$. Consider
${\mathbf{w}}\sim\operatorname{Unif}(\\{\pm 1\\}^{d})$. By symmetry,
$\operatorname{\mathbb{P}}\left[{\mathbf{w}}^{\scriptscriptstyle{\mathsf{T}}}x=0\right]=\operatorname{\mathbb{P}}\left[{\mathbf{w}}^{\scriptscriptstyle{\mathsf{T}}}x^{\prime}=0\right]$
for all $x,x^{\prime}\in\\{\pm 1\\}^{d}$, so

$\operatorname{\mathbb{E}}\left[s_{{\mathbf{w}},0}(x)\right]=\chi(x)\cdot\operatorname{\mathbb{P}}\left[{\mathbf{w}}^{\scriptscriptstyle{\mathsf{T}}}x=0\right]=\chi(x)\cdot
2^{-d}\cdot|\\{v\in\\{\pm
1\\}^{d}:v^{\scriptscriptstyle{\mathsf{T}}}x=0\\}|=\chi(x)\cdot q,$

where $q:=\binom{d}{d/2}/2^{d}=\Theta(1/\sqrt{d})$. Define
$g(x):=\frac{1}{q2^{d}}\sum_{w\in\\{\pm 1\\}^{d}}s_{w,0}(x)$. Then
$g(x)=\frac{1}{q}\operatorname{\mathbb{E}}\left[s_{{\mathbf{w}},0}(x)\right]=\chi(x)$
for each $x\in\\{\pm 1\\}^{d}$, i.e., $g$ interpolates the parity dataset.
Finally, we bound the $\mathcal{R}$-norm:

$\left\|g\right\|_{\mathcal{R}}\leq\frac{1}{q2^{d}}\sum_{w\in\\{\pm
1\\}^{d}}\left\|s_{w,0}\right\|_{\mathcal{R}}\leq\frac{1}{q}\cdot
O(\sqrt{d})\leq O(d).\qed$

While Theorem 4 successfully exhibits a neural network $g$ that perfectly fits
the parity dataset with $\left\|g\right\|_{\mathcal{R}}=O(d)$, the width of
$g$ is $\Omega(2^{d})$. We next show that by allowing non-zero
$L^{\infty}{(\nu)}$ error in the approximation, we can achieve a construction
with both $O(d)$ $\mathcal{R}$-norm and $\operatorname*{poly}(d)$ width.

######  Theorem 5.

There is a universal constant $c>0$ such that the following holds. For any
even $d$, any $\epsilon\in(0,1)$, and any even $t\in\\{0,2,\dotsc,d\\}$, there
exists a function $g\colon\varOmega\to\mathbb{R}$ that can be represented by a
width-$m$ neural network such that
$\left\|g-\chi\right\|_{L^{\infty}{(\nu)}}\leq\epsilon$, where

$\displaystyle m$ $\displaystyle\leq
O(d^{3/2}\sqrt{\log(1/\epsilon)}/\epsilon^{2})$
$\displaystyle\text{and}\quad\left\|g\right\|_{\mathcal{R}}$
$\displaystyle\leq O(d\log(1/\epsilon))$ $\displaystyle\text{if $t\leq
c\sqrt{d\log(1/\epsilon)}$};$ $\displaystyle m$ $\displaystyle\leq
O(d^{2}/(\epsilon t))$
$\displaystyle\text{and}\quad\left\|g\right\|_{\mathcal{R}}$
$\displaystyle\leq O(t\sqrt{d})$ $\displaystyle\text{otherwise}.$

Moreover, $g$ can be expressed as a linear combination of width-$t$ sawtooth
functions.

######  Remark 2.

Suppose $\epsilon$ is a constant. Using $t=\Theta(d)$, we obtain a neural
network of width $m=O(d)$ and $\left\|g\right\|_{\mathcal{R}}=O(d^{3/2})$,
matching the properties of the sawtooth (ridge function) interpolant
$s_{w,d}$. Using $t=\Theta(1)$, we obtain a neural network of width
$m=O(d^{3/2})$ and $\left\|g\right\|_{\mathcal{R}}=O(d)$, matching the
properties of the interpolant from Theorem 4 but with almost exponentially
smaller width.

A more detailed version of Theorem 5 (which also specifies the _intrinsic
dimensionality_ of $g$) is stated and proved in Appendix D.2. The proof uses a
similar technique as that of Theorem 4, but instead averages randomly sampled
sawtooth functions $s_{{\mathbf{w}}^{(1)},t},\dots,s_{{\mathbf{w}}^{(k)},t}$
for ${\mathbf{w}}^{(j)}\sim\operatorname{Unif}(\\{\pm 1\\}^{d})$ of width $t$.
We show that for sufficiently large $k$, every $x\in\\{\pm 1\\}^{d}$ lies the
in the “active” region of about the same number of sawtooth functions; this
yields a good approximation of $\chi(x)$ for all $x$.

###  3.3 Every parity interpolant has $\mathcal{R}$-norm $\Omega(d)$

Finally, we show that $\mathcal{R}$-norm upper-bounds from Theorems 4 and 5
are tight. That is, we show that every solution to ($\epsilon$-VP) for the
parity dataset has $\mathcal{R}$-norm $\Omega(d)$, even for constant
$\epsilon$. This is implied by the following stronger result, which requires
only $L^{2}{(\nu)}$ approximation, as opposed to $L^{\infty}{(\nu)}$.

######  Theorem 6.

For any $d\geq 8$ and $\alpha\in(0,1)$,
$\inf\\{\left\|g\right\|_{\mathcal{R}}:\left\|g-\chi\right\|_{L^{2}{(\nu)}}\leq
1-\alpha\\}\geq\alpha d/8$.

The core of the proof of Theorem 6 (given in Appendix D.3) is an upper-bound
on the correlation of any fixed ReLU neuron with the parity function $\chi$.

We note that a result analogous to Theorem 6 also holds for most _sampled
parity datasets_ (defined in Section 4). This result is stated and proved in
Appendix D.4.

##  4 Generalization properties of solutions to the variational problem

In this section, we consider the generalization properties of a learning
algorithm that returns a solution to (VP) for a _sampled parity dataset_
$\\{({\mathbf{x}}_{i},\chi({\mathbf{x}}_{i})):i\in[n]\\}$ for
${\mathbf{x}}_{1},\dotsc,{\mathbf{x}}_{n}\sim_{\operatorname{iid}}\nu$.
(Again, for simplicity, we label data using $\chi$, but the same results hold
for any $\chi_{S}$ with $|S|=\Theta(d)$.)

We show that $n=o(d^{2}/\sqrt{\log d})$ results in a predictor with nearly
trivial accuracy. Note that information-theoretically, $n\geq O(d)$ is
sufficient for learning any parity function (Helmbold et al., 1992; Fischer
and Simon, 1992). This means that the inductive bias based on
$\mathcal{R}$-norm is not sufficient to achieve statistically optimal sample
complexity for learning parity functions.

###  4.1 Poor generalization with $n\ll d^{2}/\sqrt{\log d}$ samples

We first give a lower bound on the sample size needed for non-trivial
generalization for learning parity functions by solving (VP) with the sampled
parity dataset.

######  Theorem 7.

If $n=o(d^{2}/\sqrt{\log d})$, then with probability at least $1/2$, every
solution ${\mathbf{g}}\colon\varOmega\to\mathbb{R}$ to (VP) for the sampled
parity dataset has $\left\|{\mathbf{g}}-\chi\right\|_{L^{2}{(\nu)}}\geq
1-o(1)$.

Its proof relies on the following approximation lemma, which shows the
existence of a low-$\mathcal{R}$-norm network ${\mathbf{g}}$ that perfectly
fits all $n$ samples. The lemma (which is proved in Appendix E.1) defines
${\mathbf{g}}$ with the same “cap construction” used in Theorem 1 of Bubeck et
al. (2021).

######  Lemma 8.

There is an absolute constant $c>0$ such that the following holds. If $n\leq
cd^{2}$, and
${\mathbf{x}}_{1},\dotsc{\mathbf{x}}_{n}\sim_{\operatorname{iid}}\nu$, then
with probability at least $1/2$, there exists
${\mathbf{g}}\colon\varOmega\to\mathbb{R}$ with
${\mathbf{g}}({\mathbf{x}}_{i})=\chi({\mathbf{x}}_{i})$ for all $i\in[n]$ and
$\left\|{\mathbf{g}}\right\|_{\mathcal{R}}\leq\smash{4n\sqrt{\ln d}/d}$.

We conclude that generalization fails in this low-sample regime because
Theorem 6 shows that no network with sufficiently small $\mathcal{R}$-norm can
correlate with parity.

###### Proof of Theorem 7.

Let $\alpha:=\smash{64n\sqrt{\ln d}/d^{2}}$, so $\alpha=o(1)$ by assumption on
$n$. By Theorem 6, every $g\colon\varOmega\to\mathbb{R}$ with
$\left\|g-\chi\right\|_{L^{2}{(\nu)}}\leq 1-\alpha$ has
$\left\|g\right\|_{\mathcal{R}}\geq\alpha d/8\geq 8n\sqrt{\ln d}/d$. However,
by Lemma 8, with probability at least $1/2$, every solution ${\mathbf{g}}$ to
(VP) for the dataset
$\\{({\mathbf{x}}_{i},\chi({\mathbf{x}}_{i}))\\}_{i\in[n]}$ has
$\left\|{\mathbf{g}}\right\|_{\mathcal{R}}\leq\smash{4n\sqrt{\ln d}/d}$. In
this event, the solutions ${\mathbf{g}}$ have
$\left\|{\mathbf{g}}-\chi\right\|_{L^{2}{(\nu)}}\geq 1-\alpha=1-o(1)$. ∎

###  4.2 Good generalization with $n\gtrsim d^{3}$ samples

We complement the lower-bound in Theorem 7 with the following sample
complexity upper-bound.

######  Theorem 9.

There is an absolute constant $C>0$ such that the following holds. For any
$\epsilon\in(0,1)$ and $\delta\in(0,1)$, if $n\geq
C(\log(1/\delta)+d^{3}/\epsilon^{2})$, then with probability at least
$1-\delta$, every solution ${\mathbf{g}}\colon\varOmega\to\mathbb{R}$ to (VP)
for the sampled parity dataset satisfies
$\left\|\chi-\operatorname{clip}\circ\,{\mathbf{g}}\right\|_{L^{2}{(\nu)}}^{2}\leq\epsilon$,
where $\operatorname{clip}(t):=\min\\{\max\\{t,-1\\},1\\}$.

For technical reasons, we only bound the $L^{2}{(\nu)}$ error of the natural
truncation of a solution to (VP). The proof in Appendix E.2 is based on
standard Rademacher complexity arguments.

We note that there is a gap between our lower bound (Theorem 7) and upper
bound (Theorem 9): roughly a factor of $d\sqrt{\log d}$. We believe that this
gap could be narrowed if one resolves the open question raised by Bubeck et
al. (2021) about the minimum Lipschitz constant achievable by two-layer ReLU
networks of width $m$ networks that interpolate a sample of size $n$; Lemma 8
is derived from a theorem that produces networks with smoothness conjectured
to be sub-optimal. Nevertheless, our lower bound in Theorem 7 is already high
enough to establish the statistical suboptimality of solutions to (VP).

##  5 Generality of the averaging technique for minimizing $\mathcal{R}$-norm

In this section, we show how the benefit of averaging goes beyond the parity
dataset. We consider an _$f$ -dataset_ $\\{(x,f(x)\\}_{x\in\\{\pm 1\\}^{d}}$,
a generalization of the parity dataset where
$f(x)=\phi(v^{\scriptscriptstyle{\mathsf{T}}}x)$ is a ridge function with
$L$-Lipschitz and $\rho$-periodic $\phi$. For another dataset generated by
oscillatory ridge functions, we prove the same contrast between
minimum-$\mathcal{R}$-norm interpolation with and without ridge constraints,
so long as the periodicity $\rho$ is not too small (specifically, $\rho\geq
1/\sqrt{d}$). More concretely, suppose the dataset
$\\{(x_{i},f(x_{i}))\\}_{i\in[n]}\subset\\{\pm 1\\}^{d}\times\\{\pm 1\\}$ used
in (VP) and ($\epsilon$-VP) is the _$f$ -dataset_, where
$v\in\\{\pm\frac{1}{\sqrt{d}}\\}^{d}$ and $\phi$ is $\rho$-periodic and
$\frac{1}{\rho}$-Lipschitz. Then we have the following:

  * •

The optimal value of ($\epsilon$-VP) for constant $\epsilon\in(0,1/2)$ is
$\tilde{O}(\sqrt{d}/\rho)$. (Theorem 10)

  * •

The optimal value of ($\epsilon$-VP) for constant $\epsilon\in(0,1/2)$—with
the additional constraint that $g$ be a ridge function—is
$\Omega(\sqrt{d}/\rho^{2})$. (Theorem 11)

Because the parity dataset is an $f$-dataset with a $1/{\sqrt{d}}$-periodic
and $\sqrt{d}$-Lipschitz choice of $\phi$, the above results closely match
those of Informal Theorem 1. We give both results, starting with an upper
bound on the minimum-$\mathcal{R}$-norm approximate interpolant, which
parallels Theorem 5.

######  Theorem 10.

Suppose $f\colon\varOmega\to[-1,1]$ is given by
$f(x)=\phi(v^{\scriptscriptstyle{\mathsf{T}}}x)$ for some unit vector
$v\in\mathbb{S}^{d-1}$ and some $\phi\colon[-\sqrt{d},\sqrt{d}]\to[-1,1]$ that
is $L$-Lipschitz and $\rho$-periodic for
$\rho\in[\left\|v\right\|_{\infty},1]$. Fix any $\epsilon\in(0,1)$. There
exists a function $g\colon\varOmega\to\mathbb{R}$ represented by a width-$m$
neural network such that:

$\left\|f-g\right\|_{L^{\infty}{(\nu)}}\leq\epsilon;\quad m\leq
dL\operatorname*{polylog}(1/\epsilon)\sqrt{\rho\|v\|_{1}}/\epsilon^{2};\quad\left\|g\right\|_{\mathcal{R}}\leq
L^{2}\operatorname*{polylog}(d/\epsilon)\rho\|v\|_{1}/\epsilon.$

######  Remark 3.

Suppose $f(x)=\cos(\frac{2\pi}{\rho}v^{\scriptscriptstyle{\mathsf{T}}}x)$ for
$v\in\\{\pm\frac{1}{\sqrt{d}}\\}^{d}$ and $\rho\in[\frac{1}{\sqrt{d}},1]$.
Theorem 10 implies that there exists an $\epsilon$-approximate interpolating
neural network $g$ of width
$\smash{\tilde{O}(\frac{d^{5/4}}{\sqrt{\rho}\epsilon^{2}})}$ and
$\smash{\left\|g\right\|_{\mathcal{R}}=\tilde{O}(\frac{\sqrt{d}}{\rho\epsilon})}$.
If $d$ is even and $\rho=4/\sqrt{d}$, then $f(x)=\chi(x)$ for $x\in\\{\pm
1\\}^{d}$, and the width and $\mathcal{R}$-norm bounds of Theorem 5 for small
$t$ are approximately recovered.

A detailed version of Theorem 10 appears in Appendix F.1. The construction is
more delicate than that in Theorem 5 due to the potential lack of symmetries
that had existed in the parity dataset.

We give the lower bound on the $\mathcal{R}$-norm of all approximately
interpolanting ridge functions, whose proof in Appendix F.2 relies a reduction
to the argument of Theorem 3.

######  Theorem 11.

Assume $d$ is even. Let $\operatorname{Ridge}_{d}$ be the set of functions
$g\colon\varOmega\to\mathbb{R}$ such that
$g(x)=\phi(w^{\scriptscriptstyle{\mathsf{T}}}x)$ for some
$w\in\mathbb{S}^{d-1}$ and Lipschitz continuous
$\phi\colon[-\sqrt{d},\sqrt{d}]\to\mathbb{R}$. Let $\rho:=4q/\sqrt{d}$ for
$q\in\\{1,2,\dots,\lfloor\sqrt{d}/4\rfloor\\}$ and
$f(x):=\cos((2\pi/(\rho\sqrt{d}))\vec{1}^{\scriptscriptstyle{\mathsf{T}}}x)$.
Then

$\inf\\{\left\|g\right\|_{\mathcal{R}}:g\in\operatorname{Ridge}_{d},\
\left\|g-f\right\|_{L^{\infty}{(\nu)}}\leq 1/2\\}=\Omega(\sqrt{d}/\rho^{2}).$

######  Remark 4.

By contrasting the above result to the
$\tilde{O}(\frac{\sqrt{d}}{\rho\epsilon})$ $\mathcal{R}$-norm of the
averaging-based construction from Remark 3, ridge functions are suboptimal
solutions to $\epsilon$-VP for constant $\epsilon$.

######  Remark 5.

Lemma 31 (in Appendix F.1) implies the existence of a neural network
$g_{\operatorname{Ridge}}\in\operatorname{Ridge}_{d}$ that point-wise
approximates $f$ (i.e.,
$\left\|g_{\operatorname{Ridge}}-f\right\|_{L^{\infty}{(\nu)}}\leq\epsilon$)
and has
$\smash{\|g_{\operatorname{Ridge}}\|_{\mathcal{R}}={O}(\frac{\sqrt{d}}{\rho^{2}\epsilon})}$.
Hence, the lower bound in Theorem 11 is tight when $\epsilon$ is constant.

##  6 Conclusion and future work

In this work, we shed light on the $\mathcal{R}$-norm inductive bias for
learning neural networks, but numerous questions remain. We are particularly
interested in understanding the solutions to (VP) for other datasets, as well
as the generality of the averaging techniques used in our constructions.
Extensions of the $\mathcal{R}$-norm to deeper networks and analyzing
solutions to (VP) for other high dimensional datasets could also be useful for
proving depth-separation results that focus on variational norm, complementing
existing works that focus on width (Telgarsky, 2016; Eldan and Shamir, 2016;
Martens et al., 2013; Daniely, 2017; Safran and Shamir, 2017; Safran et al.,
2019). Finally, our work suggests that minimizing $\mathcal{R}$-norm yields
neural networks that are intrinsically high-dimensional, and we are interested
in whether this phenomenon is borne out in architectures beyond two-layer
fully-connected networks.

#### Acknowledgements

This work was supported in part by NSF grants CCF-1740833 and IIS-1563785, a
JP Morgan Faculty Award, and an NSF Graduate Research Fellowship.

## References

  * Abbe and Sandon [2020] Emmanuel Abbe and Colin Sandon.  Poly-time universality and limitations of deep learning.  _arXiv preprint arXiv:2001.02992_ , 2020.
  * Bach [2017] Francis Bach.  Breaking the curse of dimensionality with convex neural networks.  _Journal of Machine Learning Research_ , 18(1):629–681, 2017.
  * Bach and Chizat [2021] Francis Bach and Lenaïc Chizat.  Gradient descent on infinitely wide neural networks: Global convergence and generalization.  _arXiv preprint arXiv:2110.08084_ , 2021.
  * Baldi and Sadowski [2013] Pierre Baldi and Peter J Sadowski.  Understanding dropout.  In _Advances in Neural Information Processing Systems 26_ , 2013.
  * Barak et al. [2022] Boaz Barak, Benjamin L. Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang.  Hidden progress in deep learning: SGD learns parities near the computational limit.  _arXiv preprint arXiv:2207.08799_ , 2022.
  * Bartlett [1996] Peter L Bartlett.  For valid generalization the size of the weights is more important than the size of the network.  In _Advances in Neural Information Processing Systems 9_ , 1996.
  * Bauer and Kohler [2019] Benedikt Bauer and Michael Kohler.  On deep learning as a remedy for the curse of dimensionality in nonparametric regression.  _The Annals of Statistics_ , 47(4):2261–2285, 2019.
  * Bhojanapalli et al. [2016] Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro.  Global optimality of local search for low rank matrix recovery.  _Advances in Neural Information Processing Systems_ , 29, 2016.
  * Bietti et al. [2022] Alberto Bietti, Joan Bruna, Clayton Sanford, and Min Jae Song.  Learning single-index models with shallow neural networks.  _arXiv preprint arXiv:2210.15651_ , 2022.
  * Boucheron et al. [2013] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart.  _Concentration Inequalities - A Nonasymptotic Theory of Independence_.  Oxford University Press, 2013.
  * Bubeck et al. [2021] Sébastien Bubeck, Yuanzhi Li, and Dheeraj M Nagaraj.  A law of robustness for two-layers neural networks.  In _Conference on Learning Theory_ , 2021.
  * Candès and Recht [2009] Emmanuel J Candès and Benjamin Recht.  Exact matrix completion via convex optimization.  _Foundations of Computational Mathematics_ , 9(6):717–772, 2009.
  * Candès et al. [2006] Emmanuel J Candès, Justin Romberg, and Terence Tao.  Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information.  _IEEE Transactions on information theory_ , 52(2):489–509, 2006.
  * Damian et al. [2022] Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi.  Neural networks can learn representations with gradient descent.  In _Conference on Learning Theory_ , 2022.
  * Daniely [2017] Amit Daniely.  Depth separation for neural networks.  In _Conference on Learning Theory_ , 2017.
  * Daniely and Malach [2020] Amit Daniely and Eran Malach.  Learning parities with neural networks.  In _Advances in Neural Information Processing Systems 33_ , 2020.
  * Debarre et al. [2022] Thomas Debarre, Quentin Denoyelle, Michael Unser, and Julien Fageot.  Sparsest piecewise-linear regression of one-dimensional data.  _Journal of Computational and Applied Mathematics_ , 406:114044, 2022.
  * Donoho [2006] David L Donoho.  Compressed sensing.  _IEEE Transactions on Information Theory_ , 52(4):1289–1306, 2006.
  * E et al. [2019] Weinan E, Chao Ma, and Lei Wu.  The Barron space and the flow-induced function spaces for neural network models.  _arXiv preprint arXiv:1906.08039_ , 2019.
  * Eldan and Shamir [2016] Ronen Eldan and Ohad Shamir.  The power of depth for feedforward neural networks.  In _Conference on Learning Theory_ , 2016.
  * Ergen and Pilanci [2021] Tolga Ergen and Mert Pilanci.  Convex geometry and duality of over-parameterized neural networks.  _Journal of Machine Learning Research_ , 22(212):1–63, 2021.
  * Fischer and Simon [1992] Paul Fischer and Hans-Ulrich Simon.  On learning ring-sum-expansions.  _SIAM Journal on Computing_ , 21(1):181–192, 1992\.
  * Frei et al. [2022] Spencer Frei, Niladri S Chatterji, and Peter L Bartlett.  Random feature amplification: Feature learning and generalization in neural networks.  _arXiv preprint arXiv:2202.07626_ , 2022.
  * Gal and Ghahramani [2016] Yarin Gal and Zoubin Ghahramani.  Dropout as a Bayesian approximation: Representing model uncertainty in deep learning.  In _International Conference on Machine Learning_ , 2016.
  * Galanti et al. [2022] Tomer Galanti, Zachary S. Siegel, Aparna Gupte, and Tomaso Poggio.  SGD and weight decay provably induce a low-rank bias in neural networks.  _arXiv preprint arXiv:2206.05794_ , 2022.
  * Györfi et al. [2002] László Györfi, Michael Köhler, Adam Krzyżak, and Harro Walk.  _A distribution-free theory of nonparametric regression_ , volume 1.  Springer, 2002.
  * Hanin [2021] Boris Hanin.  Ridgeless interpolation with shallow ReLU networks in $1d$ is nearest neighbor curvature extrapolation and provably generalizes on Lipschitz functions.  _arXiv preprint arXiv:2109.12960_ , 2021.
  * Hanson and Pratt [1988] Stephen Hanson and Lorien Pratt.  Comparing biases for minimal network construction with back-propagation.  In _Advances in Neural Information Processing Systems 1_ , 1988.
  * Helmbold et al. [1992] David Helmbold, Robert Sloan, and Manfred K Warmuth.  Learning integer lattices.  _SIAM Journal on Computing_ , 21(2):240–266, 1992\.
  * Hinton [1987] Geoffrey E Hinton.  Learning translation invariant recognition in a massively parallel networks.  In _International Conference on Parallel Architectures and Languages Europe_ , 1987.
  * Jin and Montúfar [2020] Hui Jin and Guido Montúfar.  Implicit bias of gradient descent for mean squared error regression with wide neural networks.  _arXiv preprint arXiv:2006.07356_ , 2020.
  * Kakade et al. [2008] Sham M Kakade, Karthik Sridharan, and Ambuj Tewari.  On the complexity of linear prediction: Risk bounds, margin bounds, and regularization.  In _Advances in Neural Information Processing Systems 21_ , 2008.
  * Kimeldorf and Wahba [1971] George Kimeldorf and Grace Wahba.  Some results on Tchebycheffian spline functions.  _Journal of mathematical analysis and applications_ , 33(1):82–95, 1971.
  * Klusowski and Barron [2016] Jason M Klusowski and Andrew R Barron.  Risk bounds for high-dimensional ridge function combinations including neural networks.  _arXiv preprint arXiv:1607.01434_ , 2016.
  * Kohler and Krzyżak [2005] Michael Kohler and Adam Krzyżak.  Adaptive regression estimation with multilayer feedforward neural networks.  _Nonparametric Statistics_ , 17(8):891–913, 2005\.
  * Kurková and Sanguineti [2001] Vera Kurková and Marcello Sanguineti.  Bounds on rates of variable-basis and neural-network approximation.  _IEEE Transactions on Information Theory_ , 47(6):2659–2665, 2001.
  * Li [2018] Bing Li.  _Sufficient dimension reduction: Methods and applications with R_.  CRC Press, 2018.
  * Maennel et al. [2018] Hartmut Maennel, Olivier Bousquet, and Sylvain Gelly.  Gradient descent quantizes ReLU network features.  _arXiv preprint arXiv:1803.08367_ , 2018.
  * Malach et al. [2021] Eran Malach, Pritish Kamath, Emmanuel Abbe, and Nathan Srebro.  Quantifying the benefit of using differentiable learning over tangent kernels.  _arXiv preprint arXiv:2103.01210_ , 2021.
  * Martens et al. [2013] James Martens, Arkadev Chattopadhya, Toni Pitassi, and Richard Zemel.  On the representational efficiency of restricted Boltzmann machines.  In _Advances in Neural Information Processing Systems 26_ , 2013.
  * Meir and Zhang [2003] Ron Meir and Tong Zhang.  Generalization error bounds for Bayesian mixture algorithms.  _Journal of Machine Learning Research_ , 4(Oct):839–860, 2003.
  * Mhaskar [2004] Hrushikesh Narhar Mhaskar.  On the tractability of multivariate integration and approximation by neural networks.  _Journal of Complexity_ , 20(4):561–590, 2004\.
  * Mitzenmacher and Upfal [2017] Michael Mitzenmacher and Eli Upfal.  _Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis_.  Cambridge University Press, 2017.
  * Mousavi-Hosseini et al. [2022] Alireza Mousavi-Hosseini, Sejun Park, Manuela Girotti, Ioannis Mitliagkas, and Murat A Erdogdu.  Neural networks efficiently learn low-dimensional representations with sgd.  _arXiv preprint arXiv:2209.14863_ , 2022.
  * Neyshabur et al. [2015] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro.  In search of the real inductive bias: On the role of implicit regularization in deep learning.  In _ICLR Workshop_ , 2015.
  * Olson et al. [2018] Matthew Olson, Abraham Wyner, and Richard Berk.  Modern neural networks generalize on small data sets.  In _Advances in Neural Information Processing Systems 31_ , 2018.
  * O’Neil [1971] Patrick E. O’Neil.  Hyperplane cuts of an $n$-cube.  _Discrete Mathematics_ , 1(2):193–195, 1971.
  * Ongie et al. [2019] Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro.  A function space view of bounded norm infinite width ReLU nets: The multivariate case.  In _International Conference on Learning Representations_ , 2019.
  * Parhi and Nowak [2021a] Rahul Parhi and Robert D Nowak.  Banach space representer theorems for neural networks and ridge splines.  _Journal of Machine Learning Research_ , 22(43):1–40, 2021a.
  * Parhi and Nowak [2021b] Rahul Parhi and Robert D Nowak.  Near-minimax optimal estimation with shallow ReLU neural networks.  _arXiv preprint arXiv:2109.08844_ , 2021b.
  * Rosset et al. [2007] Saharon Rosset, Grzegorz Swirszcz, Nathan Srebro, and Ji Zhu.  $\ell_{1}$ regularization in infinite dimensional feature spaces.  In _Conference on Learning Theory_ , 2007.
  * Safran and Shamir [2017] Itay Safran and Ohad Shamir.  Depth-width tradeoffs in approximating natural functions with neural networks.  In _International Conference on Machine Learning_ , 2017.
  * Safran et al. [2019] Itay Safran, Ronen Eldan, and Ohad Shamir.  Depth separations in neural networks: What is actually being separated?  In _Conference on Learning Theory_ , 2019.
  * Savarese et al. [2019] Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro.  How do infinite width bounded norm networks look in function space?  In _Conference on Learning Theory_ , 2019.
  * Schmidt-Hieber [2020] Johannes Schmidt-Hieber.  Nonparametric regression using deep neural networks with relu activation function.  _The Annals of Statistics_ , 48(4):1875–1897, 2020.
  * Shevchenko et al. [2021] Alexander Shevchenko, Vyacheslav Kungurtsev, and Marco Mondelli.  Mean-field analysis of piecewise linear solutions for wide ReLU networks.  _arXiv preprint arXiv:2111.02278_ , 2021.
  * Siegel and Xu [2021] Jonathan W Siegel and Jinchao Xu.  Characterization of the variation spaces corresponding to shallow neural networks.  _arXiv preprint arXiv:2106.15002_ , 2021.
  * Telgarsky [2016] Matus Telgarsky.  Benefits of depth in neural networks.  In _Conference on Learning Theory_ , 2016.
  * Telgarsky [2022] Matus Telgarsky.  Feature selection with gradient descent on two-layer networks in low-rotation regimes.  _arXiv preprint arXiv:2208.02789_ , 2022.
  * Vershynin [2018] Roman Vershynin.  _High-dimensional probability: An introduction with applications in data science_.  Cambridge University Press, 2018.
  * Wang and Lin [2021] Huiyuan Wang and Wei Lin.  Harmless overparametrization in two-layer neural networks.  _arXiv preprint arXiv:2106.04795_ , 2021.
  * Wei et al. [2019] Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma.  Regularization matters: Generalization and optimization of neural nets vs their induced kernel.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Williams et al. [2019] Francis Williams, Matthew Trager, Daniele Panozzo, Claudio Silva, Denis Zorin, and Joan Bruna.  Gradient dynamics of shallow univariate ReLU networks.  In _Advances in Neural Information Processing Systems 32_ , 2019.
  * Yehudai and Shamir [2019] Gilad Yehudai and Ohad Shamir.  On the power and limitations of random features for understanding neural networks.  In _Advances in Neural Information Processing Systems 32_ , 2019.
  * Zhang et al. [2021] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning (still) requires rethinking generalization.  _Communications of the ACM_ , 64(3):107–115, 2021\.
  * Zhang and Wang [2022] Kaiqi Zhang and Yu-Xiang Wang.  Deep learning meets nonparametric regression: Are weight-decayed dnns locally adaptive?  _arXiv preprint arXiv:2204.09664_ , 2022.

##  Appendix A Additional preliminaries

###  A.1 Additional definitions and notations

We say that $g:\varOmega\to\mathbb{R}$ is $k$-index if there exists a matrix
$U\in\mathbb{R}^{k\times d}$ and $\phi:\mathbb{R}^{k}\to\mathbb{R}$ such that
$g(x)=\phi(Ux)$ for all $x\in\varOmega$. A ridge function is 1-index.

For a matrix $M\in\mathbb{R}^{m\times n}$, we denote the $i$-th largest
singular value of $M$ by $\sigma_{i}(M)$ for $i=1,\dotsc,\min\\{m,n\\}$.

A random variable ${\mathbf{u}}$ is $c$-_subgaussian_ if
$\left\|{\mathbf{u}}\right\|_{\psi_{2}}:=\inf\\{t\geq
0:\operatorname{\mathbb{E}}[\exp({\mathbf{u}}^{2}/t^{2})]\leq 2\\}\leq c$, and
a random vector ${\mathbf{v}}$ is $\sigma^{2}$-_subgaussian_ if every one-
dimensional projection of ${\mathbf{v}}$ is $c$-subgaussian.

The _bias-corrected network_ $\bar{g}_{\mu}$ obtained from the (infinite-
width) neural network $g_{\mu}$ is given by
$\bar{g}_{\mu}(x):=g_{\mu}(x)-g_{\mu}(0)$; equivalently,
$\bar{g}_{\mu}(x)=\int{(\varphi_{\operatorname{r}}(w^{\scriptscriptstyle{\mathsf{T}}}x+b)-\varphi_{\operatorname{r}}(b))\,\mu(\operatorname{d\\!}w,\operatorname{d\\!}b)}$.

The asymptotics implied in the Landau notation (big-$O$, big-$\Omega$, etc.)
regard all quantities as potentially increasing functions (e.g., $t$) or
decreasing functions (e.g., $\epsilon$, $\delta$, $\alpha$, $\rho$) of the
dimension $d$. The soft-$O$ notation $\tilde{O}(\cdot)$ (only used informally)
suppresses terms that are poly-logarithmic in those that appear. Some of our
theorems and lemmas contain an “if clause” that uses Landau notation, such as
“if $n\geq O(d^{2})$, […]”. The interpretation of such a clause is: “there
exists $n_{0}(d)\in O(d^{2})$ such that if $n\geq n_{0}(d)$, […]”. (And, of
course, an analogous interpretation should be used when “$O(d^{2})$” is
replaced by other expressions using Landau notation.)

###  A.2 Concentration inequalities

Our proofs make extensive use of textbook probability concentration
inequalities. We provide those results below.

######  Lemma 12 (Hoeffding’s inequality; Theorem 2.8 in Boucheron et al.,
2013).

Let ${\mathbf{u}}_{1},\dots,{\mathbf{u}}_{n}$ be independent, mean-zero random
variables such that ${\mathbf{u}}_{i}$ takes value in $[a_{i},b_{i}]$ almost
surely for all $i\in[n]$. Then, for any $t>0$,

$\operatorname{\mathbb{P}}\left[\sum_{i=1}^{n}{\mathbf{u}}_{i}\geq
t\right]\leq\exp\left(-\frac{2t^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right).$

######  Lemma 13 (Multiplicative Chernoff bound; Theorem 4.4 in Mitzenmacher
and Upfal, 2017).

Let ${\mathbf{u}}_{1},\dots,{\mathbf{u}}_{n}$ be independent Bernoulli random
variables with
$\operatorname{\mathbb{P}}\left[{\mathbf{u}}_{i}=1\right]=p\in[0,1]$ for all
$i\in[n]$. Then, for any $\eta\in(0,1]$,

$\operatorname{\mathbb{P}}\left[\sum_{i=1}^{n}{\mathbf{u}}_{i}\geq(1+\eta)p\right]\leq\exp\left(-\frac{p\eta^{2}}{3}\right).$

######  Lemma 14 (Bernstein’s inequality; Corollary 2.11 in Boucheron et al.,
2013).

Let ${\mathbf{u}}_{1},\dots,{\mathbf{u}}_{n}$ be independent, mean-zero random
variables with ${\mathbf{u}}_{i}\leq K$ almost surely for all $i\in[n]$, and
let $v\coloneqq\sum_{i=1}^{n}\operatorname{\mathbb{E}}[{\mathbf{u}}_{i}^{2}]$.
Then, for any $t>0$,

$\operatorname{\mathbb{P}}\left[\sum_{i=1}^{n}{\mathbf{u}}_{i}\geq
t\right]\leq\exp\left(-\frac{t^{2}}{2(v+Kt/3)}\right).$

######  Lemma 15 (McDiarmid’s inequality; Theorem 6.2 in Boucheron et al.,
2013).

Let ${\mathbf{u}}_{1},\dots,{\mathbf{u}}_{n}$ be independent random variables,
and let $f$ be a measurable function. Suppose, for each $i\in[n]$, the value
of $f(u_{1},\dots,u_{n})$ can change by at most $c_{i}\geq 0$ by changing the
value of $u_{i}$. Then, for any $t>0$,

$\operatorname{\mathbb{P}}\left[f({\mathbf{u}}_{1},\dots,{\mathbf{u}}_{n})-\operatorname{\mathbb{E}}\left[f({\mathbf{u}}_{1},\dots,{\mathbf{u}}_{n})\right]\geq
t\right]\leq\exp\left(-\frac{2t^{2}}{\sum_{i=1}^{n}c_{i}^{2}}\right).$

######  Lemma 16 (Properties of subgaussian random variables).

Let ${\mathbf{u}}_{1},\dots,{\mathbf{u}}_{n}$ be independent random variables
with $\left\|{\mathbf{u}}_{i}\right\|_{\psi_{2}}<\infty$ for all $i\in[n]$.
There is a universal constant $C>0$ such that the following hold.

  1. (i)

(Concentration; Section 2.5.2 in Vershynin, 2018) For any $t>0$,
$\operatorname{\mathbb{P}}\left[\left|{\mathbf{u}}_{1}\right|\geq t\right]\leq
2\exp(-t^{2}/(C\left\|{\mathbf{u}}_{1}\right\|_{\psi_{2}}))$.

  2. (ii)

(Maximum; Exercise 2.5.10 in Vershynin, 2018)
$\operatorname{\mathbb{E}}\left[\max_{i\in[n]}\left|{\mathbf{u}}_{i}\right|\right]\leq
C\sqrt{\ln n}\max_{i\in[n]}\|{\mathbf{u}}_{i}\|_{\psi_{2}}$.

  3. (iii)

(Averaging: Proposition 2.6.1 in Vershynin, 2018)
$\|\sum_{i=1}^{n}{\mathbf{u}}_{i}\|_{\psi_{2}}^{2}\leq
C\sum_{i=1}^{n}\|{\mathbf{u}}_{i}\|_{\psi_{2}}^{2}$.

  4. (iv)

(Centering; Lemma 2.6.8 in Vershynin, 2018)
$\left\|{\mathbf{u}}_{1}-\operatorname{\mathbb{E}}\left[{\mathbf{u}}_{1}\right]\right\|_{\psi_{2}}\leq
C\left\|{\mathbf{u}}_{1}\right\|_{\psi_{2}}$.

  5. (v)

(Lipschitzness) For any $1$-Lipschitz function
$\phi\colon\mathbb{R}\to\mathbb{R}$ with $\phi(0)=0$,
$\left\|\phi({\mathbf{u}}_{1})\right\|_{\psi_{2}}\leq\left\|{\mathbf{u}}_{1}\right\|_{\psi_{2}}$.

###### Proof.

The only property not already proved in [Vershynin, 2018] is (v). Since $\phi$
is $1$-Lipschitz and $\phi(0)=0$,

$|\phi({\mathbf{u}}_{1})|=|\phi({\mathbf{u}}_{1})-\phi(0)|\leq|{\mathbf{u}}_{1}-0|=|{\mathbf{u}}_{1}|.$

Hence

$\operatorname{\mathbb{E}}\left[\exp(\phi({\mathbf{u}}_{1})^{2}/\|{\mathbf{u}}_{1}\|_{\psi_{2}}^{2})\right]\leq\operatorname{\mathbb{E}}\left[\exp({\mathbf{u}}_{1}^{2}/\|{\mathbf{u}}_{1}\|_{\psi_{2}}^{2})\right]\leq
2,$

which implies
$\|\phi({\mathbf{u}}_{1})\|_{\psi_{2}}\leq\|{\mathbf{u}}_{1}\|_{\psi_{2}}$. ∎

######  Lemma 17 (Singular values of random matrices; Theorem 4.6.1 in
Vershynin, 2018).

There is a positive constant $C>0$ such that the following holds. Let
${\mathbf{A}}$ be a $m\times n$ random matrix whose rows are independent,
mean-zero, $v$-subgaussian random vectors in $\mathbb{R}^{n}$. For any $t\geq
0$, with probability at least $1-2e^{-t}$, the singular values
$\sigma_{1}({\mathbf{A}}),\sigma_{2}({\mathbf{A}}),\dotsc,\sigma_{n}({\mathbf{A}})$
of ${\mathbf{A}}$ satisfy

$\sqrt{m}-Cv(\sqrt{n}+\sqrt{t})\leq\sigma_{i}({\mathbf{A}})\leq\sqrt{m}+Cv(\sqrt{n}+\sqrt{t})\quad\text{for
all $i\in[n]$}.$

######  Lemma 18 (Moment generating function for $\operatorname{Unif}(\\{\pm
1\\})$; Lemma 2.2 in Boucheron et al., 2013).

If ${\mathbf{u}}\sim\operatorname{Unif}(\\{\pm 1\\})$, then
$\operatorname{\mathbb{E}}[\exp(t{\mathbf{u}})]\leq\exp(t^{2}/2)$ for all
$t\in\mathbb{R}$.

###  A.3 Covering numbers

Let $\mathcal{N}(\epsilon,A,\gamma)$ denote the covering number over a metric
space $A$ with metric $\gamma:A\times A\to\mathbb{R}_{+}$. That is,
$\mathcal{N}(\epsilon,A,d)=\min|\mathcal{N}_{\epsilon}|$ for
$\mathcal{N}_{\epsilon}\subset A$ such that for all $x\in A$, there exists
$x^{\prime}\in\mathcal{N}_{\epsilon}$ with $\gamma(x,x^{\prime})\leq\epsilon$.
Note that
$\mathcal{N}(\epsilon,[-1,1],\left|\cdot\right|)\leq\frac{2}{\epsilon}$.

######  Lemma 19 (Covering numbers of $\mathbb{S}^{d-1}$; Corollary 4.2.13 in
Vershynin, 2018).

For any $\epsilon>0$,
$\mathcal{N}(\epsilon,\mathbb{S}^{d-1},\left\|\cdot\right\|_{2})\leq(\frac{2}{\epsilon}+1)^{d}$.
If $\epsilon\in[0,1]$, then
$\mathcal{N}(\epsilon,\mathbb{S}^{d-1},\left\|\cdot\right\|_{2})\leq(\frac{3}{\epsilon})^{d}$.

##  Appendix B Additional properties of $\mathcal{R}$-norm

###  B.1 Existence and sparsity of the solution to VP

######  Proposition 1 (Lemma 2 in Parhi and Nowak, 2021b).

For any $g:\varOmega\to\mathbb{R}$ with
$\left\|g\right\|_{\mathcal{R}}<\infty$, there exists an even Radon
measure555Evenness of $\mu$ should interpreted in the distributional sense,
but it roughly means $\mu(w,b)=\mu(-w,-b)$ when $\mu$ has a density. $\mu$
over $\mathbb{S}^{d-1}\times[-\sqrt{d},\sqrt{d}]$, and
$v\in\mathbb{R}^{d},c\in\mathbb{R}$, such that $g$ admits an integral of the
form

$g(x)=\int_{\mathbb{S}^{d-1}\times[-\sqrt{d}\times\sqrt{d}]}{\varphi_{\operatorname{r}}(w^{\scriptscriptstyle{\mathsf{T}}}x+b)\,\mu(\operatorname{d\\!}w,\operatorname{d\\!}b)}+v^{\scriptscriptstyle{\mathsf{T}}}x+c\quad\forall
x\in\varOmega.$

Moreover, $\mu$ attains the ($\mathcal{R}$-norm), i.e.,
$\left\|g\right\|_{\mathcal{R}}=\left|\mu\right|$.

The following theorem of Parhi and Nowak [2021b] formalizes the fact that the
$\mathcal{R}$-norm-minimizing interpolant of a $d$-dimensional dataset can be
represented as a finite-width neural network.

######  Theorem 20.

For any dataset $\\{(x_{i},y_{i})\\}_{i\in[n]}$ from
$\varOmega\times\mathbb{R}$, the infimum in (VP) is achieved by the sum of an
affine function $x\mapsto v^{\scriptscriptstyle{\mathsf{T}}}x+c$ and a finite-
width neural network $g$ of the form

$g(x)=\sum_{j=1}^{m}{a^{(j)}\varphi_{\operatorname{r}}(w^{(j)}x+b^{(j)})}+v^{\scriptscriptstyle{\mathsf{T}}}x+c,$

with $m\leq\max\\{0,n-(d+1)\\}$ and
$(w_{j},b_{j})\in\mathbb{S}^{d-1}\times[-\sqrt{d},\sqrt{d}]$ for all
$i\in[m]$.

###### Proof.

By Theorem 5 of Parhi and Nowak [2021b] (see also the proof of Theorem 1 of
Parhi and Nowak [2021a] which covers the interpolation form of the
optimization problem), there exists a neural network
$x\mapsto\sum_{j=1}^{m^{\prime}}a^{(j)}\varphi_{\operatorname{r}}(w^{(j){\scriptscriptstyle{\mathsf{T}}}}x+b^{(j)})$
of width $m^{\prime}\leq n-(d+1)$, and an affine function $x\mapsto
v^{(0){\scriptscriptstyle{\mathsf{T}}}}x+c^{(0)}$, such that their sum
achieves the infimum in (VP). We can divide neurons of the neural network into
two sets based on whether their corresponding bias term is smaller or larger
than $\sqrt{d}$ in absolute value. Since every $x\in\varOmega$ satisfies
$\|x\|_{2}\leq\sqrt{d}$, without loss of generality (by possibly flipping the
sign of some $a^{(j)}$ and $w^{(j)}$), assume the first $m$ neurons satisfy
$\left|b^{(j)}\right|\leq\sqrt{d}$ and the rest satisfy $b^{(j)}>\sqrt{d}$.
Then we have

$\displaystyle g(x)$
$\displaystyle=\sum_{j=1}^{m}{a^{(j)}\varphi_{\operatorname{r}}(w^{(j){\scriptscriptstyle{\mathsf{T}}}}x+b^{(j)})}+\sum_{j=m+1}^{m^{\prime}}{a^{(j)}\varphi_{\operatorname{r}}(w^{(j){\scriptscriptstyle{\mathsf{T}}}}x+b^{(j)})}+v^{(0){\scriptscriptstyle{\mathsf{T}}}}x+c^{(0)}$
$\displaystyle=\sum_{j=1}^{m}{a^{(j)}\varphi_{\operatorname{r}}(w^{(j){\scriptscriptstyle{\mathsf{T}}}}x+b^{(j)})}+\sum_{j=m+1}^{m^{\prime}}{a^{(j)}(w^{(j){\scriptscriptstyle{\mathsf{T}}}}x+b^{(j)})}+v^{(0){\scriptscriptstyle{\mathsf{T}}}}x+c^{(0)}$
$\displaystyle=\sum_{j=1}^{m}{a^{(j)}\varphi_{\operatorname{r}}(w^{(j){\scriptscriptstyle{\mathsf{T}}}}x+b^{(j)})}+\Bigl{(}\underbrace{v^{(0)}+\sum_{j=m+1}^{m^{\prime}}{a^{(j)}w^{(j)}}}_{=:v}\Bigr{)}^{\scriptscriptstyle{\mathsf{T}}}x+\underbrace{\sum_{j=m+1}^{m^{\prime}}{b^{(j)}}+c^{(0)}}_{=:c}.$

Therefore, $g$ has the desired form with $m\leq m^{\prime}\leq n-(d+1)$. ∎

##  Appendix C Extending our results to a different variational norm

This paper considers the approximation and generalization implications of
bounding the complexity of shallow neural networks with the
$\mathcal{R}$-norm. However, $\mathcal{R}$-norm is not the only weight-based
complexity measurement, and other works employ slightly different norms for
similar purposes. This appendix demonstrates that our results are not
peculiarities of our formulation of $\mathcal{R}$-norm and extend to other
variational norms. One alternative—which we refer to as the
$\mathcal{V}_{2}$-norm—omits the linear component of the neural network whose
measure determines the $\mathcal{R}$-norm and instead permits ReLU neurons
whose thresholds lie outside the domain $\varOmega$.

We first introduce notation for an infinite-width neural network that permits
such thresholds. Let $\mathcal{M}^{\prime}$ denote the space of probability
measures over $\mathbb{S}^{d-1}\times[-2\sqrt{d},2\sqrt{d}]$. For some measure
$\tilde{\mu}\in\mathcal{M}^{\prime}$, let
$\tilde{g}_{\mu}:\varOmega\to\mathbb{R}$ be an infinite-width neural network
with

$\tilde{g}_{\tilde{\mu}}(x)=\int_{\mathbb{S}^{d-1}\times[-2\sqrt{d},2\sqrt{d}]}\varphi_{\operatorname{r}}(w^{\scriptscriptstyle{\mathsf{T}}}x+b)\,\tilde{\mu}(\operatorname{d\\!}w,\operatorname{d\\!}b),$

which has total variation norm
$\left|\tilde{\mu}\right|=\int_{\mathbb{S}^{d-1}\times[-2\sqrt{d},2\sqrt{d}]}\left|\tilde{\mu}\right|(\operatorname{d\\!}w,\operatorname{d\\!}b)$.
Now, we introduce the $\mathcal{V}_{2}$-norm for some
$g:\varOmega\to\mathbb{R}$:

$\left\|g\right\|_{\mathscr{V}_{2}}=\inf_{\tilde{\mu}\in\mathcal{M}^{\prime}}{\left|\tilde{\mu}\right|}\quad\text{s.t.}\quad
g(x)=\tilde{g}_{\tilde{\mu}}(x),\quad\forall x\in\varOmega.$
($\mathcal{V}_{2}$-norm)

In the same spirit as Lemma 1, for a discrete network $g(x)=g_{\theta}(x)$
with
$\theta=(a^{(j)},w^{(j)},b^{(j)})_{j\in[m]}\in(\mathbb{R}\times\mathbb{S}^{d-1}\times[-2\sqrt{d},2\sqrt{d}])^{m}$,
we have $\left\|g\right\|_{\mathscr{V}_{2}}\leq\left\|a\right\|_{1}$.

Our definition of the $\mathcal{V}_{2}$-norm was introduced by Siegel and Xu
[2021] as the norm corresponding to their variation space $\mathbb{P}_{1}$
with constants $c_{1}=-2\sqrt{d}$ and $c_{2}=2\sqrt{d}$. They relate the
$\mathcal{V}_{2}$-norm to the _Barron norm_ of E et al. [2019] and the Radon
norm of Ongie et al. [2019]. We show that the $\mathcal{V}_{2}$-norm and the
$\mathcal{R}$-norm are closely related and that all of our bounds apply
equivalently to the $\mathcal{V}_{2}$-norm. We first place upper and lower
bounds on the $\left\|g\right\|_{\mathscr{V}_{2}}$ in terms of
$\left\|g\right\|_{\mathcal{R}}$ and then explain why each of our results
transfers to this new variational norm.

######  Theorem 21.

Suppose $g:\varOmega\to\mathbb{R}$ has
$\left\|g\right\|_{\mathcal{R}}<\infty$. Then,
$\left\|g\right\|_{\mathcal{R}}\leq\left\|g\right\|_{\mathscr{V}_{2}}$. If $g$
is bounded near the origin (i.e., $\left|g(x)\right|\leq K$ for all $x$ with
$\left\|x\right\|_{2}\leq 1$), then $\left\|g\right\|_{\mathscr{V}_{2}}\leq
12\left\|g\right\|_{\mathcal{R}}+18K$.

As a result, all of our results that apply to the $\mathcal{R}$-norm translate
modulo constants to the $\mathcal{V}_{2}$-norm. Because
$\left\|g\right\|_{\mathscr{V}_{2}}\geq\left\|g\right\|_{\mathcal{R}}$ always
holds, every theorem that places lower bounds on an $\mathcal{R}$-norm exactly
translates to $\left\|g\right\|_{\mathscr{V}_{2}}$, including Theorems 3, 6,
25, and 9. The upper-bounds hold up to constants by observing that every
target function we consider is bounded by some $K$ on $\varOmega$.

  * •

Because every sawtooth $s_{w,t}$ is bounded by 1, the averages of sawtooths
$g$ in Theorems 4 and 5 are bounded by $K=\frac{1}{q}=O(\sqrt{d})$. Hence,
$\left\|g\right\|_{\mathscr{V}_{2}}=O(d)$, just like
$\left\|g\right\|_{\mathcal{R}}$.

  * •

For the “cap” construction ${\mathbf{g}}$ of Theorem 7, there are
$k=O(n\log(d)/d)$ neurons, none of which are active at the origin. Their
biases are negative and—under the “good event”—their weight norms are
$O(1/\log d)$. Thus, no neuron can output a value greater than $O(1/\log d)$,
so even if all $k$ neurons activate, every $x$ with $\left\|x\right\|_{2}\leq
1$ has $\left|{\mathbf{g}}(x)\right|=O(n/d)$, which is dominated by the
$\mathcal{R}$-norm of $O(n\sqrt{\log d}/d)$.

  * •

The construction $g$ of Theorem 10 computes an average of functions bounded on
$[-1,1]$. Therefore, ${\mathbf{g}}$ is bounded by 1, and its
$\mathcal{V}_{2}$-norm is no more than its $\mathcal{R}$-norm.

###### Proof of Theorem 21.

We show separately that
$\left\|g\right\|_{\mathscr{V}_{2}}\geq\left\|g\right\|_{\mathcal{R}}$, and
then that $\left\|g\right\|_{\mathscr{V}_{2}}\leq
12\left\|g\right\|_{\mathcal{R}}+18K$ under the additional hypothesis that
$|g(x)|\leq K$ for all $x\in\varOmega$ such that $\|x\|_{2}\leq 1$.

Lower bound on $\mathcal{V}_{2}$-norm: Fix any $\xi>0$. By the definition of
$\mathcal{V}_{2}$-norm, there exists $\tilde{\mu}\in\mathcal{M}^{\prime}$ such
that $g(x)=\tilde{g}_{\tilde{\mu}}(x)$ for all $x\in\varOmega$ and
$|\tilde{\mu}|\leq\left\|g\right\|_{\mathscr{V}_{2}}+\xi$.666This relies on
the assumption that $\left\|g\right\|_{\mathscr{V}_{2}}<\infty$, but if it is
not, then the claim trivially follows because
$\left\|g\right\|_{\mathcal{R}}<\infty$. We show that there exists $g_{\mu}$
(where $\mu$ is $\tilde{\mu}$ with the support of $b$ restricted to
$[-\sqrt{d},\sqrt{d}]$), $v$, and $c$ such that
$\tilde{g}_{\tilde{\mu}}(x)=g_{\mu}(x)+v^{\scriptscriptstyle{\mathsf{T}}}x+c$
for all $x\in\varOmega$. Observe that for any $x\in\varOmega$,
$w^{\scriptscriptstyle{\mathsf{T}}}x+b>0$ if $b>\sqrt{d}$ and
$w^{\scriptscriptstyle{\mathsf{T}}}x+b<0$ if $b<-\sqrt{d}$.

$\displaystyle\tilde{g}_{\tilde{\mu}}(x)$
$\displaystyle=\int_{\mathbb{S}^{d-1}\times[-2\sqrt{d},-\sqrt{d}]}\varphi_{\operatorname{r}}(w^{\scriptscriptstyle{\mathsf{T}}}x+b)\tilde{\mu}(\operatorname{d\\!}w,\operatorname{d\\!}b)+\int_{\mathbb{S}^{d-1}\times[-\sqrt{d},\sqrt{d}]}\varphi_{\operatorname{r}}(w^{\scriptscriptstyle{\mathsf{T}}}x+b)\tilde{\mu}(\operatorname{d\\!}w,\operatorname{d\\!}b)$
$\displaystyle\quad+\int_{\mathbb{S}^{d-1}\times[\sqrt{d},2\sqrt{d}]}\varphi_{\operatorname{r}}(w^{\scriptscriptstyle{\mathsf{T}}}x+b)\tilde{\mu}(\operatorname{d\\!}w,\operatorname{d\\!}b)$
$\displaystyle=0+\int_{\mathbb{S}^{d-1}\times[-\sqrt{d},\sqrt{d}]}\varphi_{\operatorname{r}}(w^{\scriptscriptstyle{\mathsf{T}}}x+b)\mu(\operatorname{d\\!}w,\operatorname{d\\!}b)+\int_{\mathbb{S}^{d-1}\times[\sqrt{d},2\sqrt{d}]}(w^{\scriptscriptstyle{\mathsf{T}}}x+b)\tilde{\mu}(\operatorname{d\\!}w,\operatorname{d\\!}b)$
$\displaystyle=g_{\mu}(x)+\sum_{i=1}^{d}x_{i}\underbrace{\int_{\mathbb{S}^{d-1}\times[\sqrt{d},2\sqrt{d}]}w_{i}\tilde{\mu}(\operatorname{d\\!}w,\operatorname{d\\!}b)}_{\coloneqq
v_{i}}+\underbrace{\int_{\mathbb{S}^{d-1}\times[\sqrt{d},2\sqrt{d}]}b\tilde{\mu}(\operatorname{d\\!}w,\operatorname{d\\!}b)}_{\coloneqq
c}$ $\displaystyle=g_{\mu}(x)+v^{\scriptscriptstyle{\mathsf{T}}}x+c.$

As a result,
$\left\|g\right\|_{\mathcal{R}}\leq\left|\mu\right|\leq|\tilde{\mu}|\leq\left\|g\right\|_{\mathscr{V}_{2}}+\xi$.
Because the argument holds simultaneously for all $\xi>0$, we conclude that
$\left\|g\right\|_{\mathcal{R}}\leq\left\|g\right\|_{\mathscr{V}_{2}}$.

Upper bound on $\mathcal{V}_{2}$-norm: By Proposition 1, there exist
$\mu\in\mathcal{M}^{\prime}$, $v\in\mathbb{R}^{d}$, and $c\in\mathbb{R}$ such
that $g(x)=g_{\mu}(x)+v^{\scriptscriptstyle{\mathsf{T}}}x+c$ for all
$x\in\varOmega$ and $\left|\mu\right|=\left\|g\right\|_{\mathcal{R}}$. We
construct $\tilde{\mu}\in\mathcal{M}^{\prime}$ such that
$g_{\mu}(x)+v^{\scriptscriptstyle{\mathsf{T}}}x+c=\tilde{g}_{\tilde{\mu}}(x)$
for all $x\in\varOmega$:777In the event that $v=\vec{0}$, we use
$\frac{v}{\left\|v\right\|_{2}}:=\frac{1}{\sqrt{d}}\vec{1}\in\mathbb{S}^{d-1}$.

$\tilde{\mu}(w,b)=\begin{cases}\mu(w,b)&\text{if
$b\in[-\sqrt{d},\sqrt{d}]$};\\\
\left(-3\left\|v\right\|_{2}+\frac{2c}{\sqrt{d}}\right)\delta\left(\left(w,b\right)-\left(v,2\sqrt{d}\right)\right)\\\
\quad+\left(4\left\|v\right\|_{2}-\frac{2c}{\sqrt{d}}\right)\delta\left(\left(w,b\right)-\left(v,\frac{3}{2}\sqrt{d}\right)\right)&\text{otherwise}.\end{cases}$

Fix any $x\in\varOmega$. Then:

$\displaystyle\tilde{g}_{\tilde{\mu}}(x)-g_{\mu}(x)$
$\displaystyle=\left(-3\left\|v\right\|_{2}+\frac{2c}{\sqrt{d}}\right)\varphi_{\operatorname{r}}\left(\frac{v^{\scriptscriptstyle{\mathsf{T}}}}{\left\|v\right\|_{2}}x+2\sqrt{d}\right)$
$\displaystyle\quad+\left(4\left\|v\right\|_{2}-\frac{2c}{\sqrt{d}}\right)\varphi_{\operatorname{r}}\left(\frac{v^{\scriptscriptstyle{\mathsf{T}}}}{\left\|v\right\|_{2}}x+\frac{3}{2}\sqrt{d}\right)$
$\displaystyle=\left(-3\left\|v\right\|_{2}+\frac{2c}{\sqrt{d}}\right)\left(\frac{v^{\scriptscriptstyle{\mathsf{T}}}}{\left\|v\right\|_{2}}x+2\sqrt{d}\right)+\left(4\left\|v\right\|_{2}-\frac{2c}{\sqrt{d}}\right)\left(\frac{v^{\scriptscriptstyle{\mathsf{T}}}}{\left\|v\right\|_{2}}x+\frac{3}{2}\sqrt{d}\right)$
$\displaystyle=v^{\scriptscriptstyle{\mathsf{T}}}x+c.$

Therefore,
$|\tilde{\mu}|\leq\left|\mu\right|+|-3\left\|v\right\|_{2}+\frac{2c}{\sqrt{d}}|+|4\left\|v\right\|_{2}-\frac{2c}{\sqrt{d}}|\leq\left|\mu\right|+7\|v\|_{2}+\frac{4\left|c\right|}{\sqrt{d}}$.
It suffices to bound $\left\|v\right\|_{2}$ and $\left|c\right|$.

  * •

Let $x_{0}\coloneqq\frac{v}{\left\|v\right\|_{2}}$. By boundedness, the
triangle inequality, and several applications of Holder’s inequality:

$\displaystyle\left|g(x_{0})-g(0)\right|$
$\displaystyle\geq\left|v^{\scriptscriptstyle{\mathsf{T}}}x_{0}\right|-\left|g_{\mu}(x_{0})-g_{\mu}(0)\right|$
$\displaystyle=\left\|v\right\|_{2}-\left|\int_{\mathbb{S}^{d-1}\times[-\sqrt{d},\sqrt{d}]}(\varphi_{\operatorname{r}}(w^{\scriptscriptstyle{\mathsf{T}}}x_{0}+b)-\varphi_{\operatorname{r}}(b))\mu(\operatorname{d\\!}w,\operatorname{d\\!}b)\right|$
$\displaystyle\geq\left\|v\right\|_{2}-\int_{\mathbb{S}^{d-1}\times[-\sqrt{d},\sqrt{d}]}\left|\varphi_{\operatorname{r}}(w^{\scriptscriptstyle{\mathsf{T}}}x_{0}+b)-\varphi_{\operatorname{r}}(b)\right|\left|\mu\right|(\operatorname{d\\!}w,\operatorname{d\\!}b)$
$\displaystyle\geq\left\|v\right\|_{2}-\|x_{0}\|_{2}\left|\mu\right|=\left\|v\right\|_{2}-\left|\mu\right|.$

Hence,
$\left\|v\right\|_{2}\leq\left|g(x_{0})-g(0)\right|+\left|\mu\right|\leq
2K+\left|\mu\right|$.

  * •

We similarly employ our bound on $g(0)$:

$\displaystyle K$
$\displaystyle\geq\left|g(0)\right|\geq\left|c\right|-\left|\int_{\mathbb{S}^{d-1}\times[-\sqrt{d},\sqrt{d}]}\varphi_{\operatorname{r}}(b)\mu(\operatorname{d\\!}w,\operatorname{d\\!}b)\right|\geq\left|c\right|-\left|\mu\right|\sqrt{d}.$

As a result, $\left|c\right|\leq K+\left|\mu\right|\sqrt{d}$.

Therefore, $\left\|g\right\|_{\mathscr{V}_{2}}\leq|\tilde{\mu}|\leq
12\left|\mu\right|+18K\leq 12\left\|g\right\|_{\mathcal{R}}+18K$. ∎

##  Appendix D Proofs for Section 3

###  D.1 Proofs for Section 3.1

The proof of Theorem 3 relies on the following lemma, which is essentially a
robust version of the mean value theorem.

######  Lemma 22.

Suppose $\phi:\mathbb{R}\to\mathbb{R}$ is Lipschitz continuous on the interval
$[t_{1},t_{2}]$ with $\phi(t_{1})\neq\phi(t_{2})$. Define

$A:=\biggl{\\{}t\in[t_{1},t_{2}]:\text{$\phi^{\prime}(t)$ exists},\\\
\left|\phi^{\prime}(t)\right|\geq\frac{1}{2}\cdot\frac{\left|\phi(t_{2})-\phi(t_{1})\right|}{t_{2}-t_{1}},\
\operatorname{sign}\left(\phi^{\prime}(t)\right)=\operatorname{sign}\left(\phi(t_{2})-\phi(t_{1})\right)\biggr{\\}}.$

(The factor $1/2$ in the definition of $A$ can be replaced by any constant in
$(0,1)$.) Then, $\operatorname{Leb}(A)>0$, where $\operatorname{Leb}$ is the
Lebesgue measure.

###### Proof.

Recall that $\phi^{\prime}$ denotes the right continuous derivative of $g$ (or
the right-hand Dini derivative) which is guaranteed to exist except on a null
set by Rademacher’s theorem. Let
$s:=\operatorname{sign}\left(\phi(t_{2})-\phi(t_{1})\right)$. By the
assumption $\phi(t_{1})\neq\phi(t_{2})$ and the Fundamental Theorem of
Calculus, we have

$0<|\phi(t_{2})-\phi(t_{1})|=s\left(\phi(t_{2})-\phi(t_{1})\right)=\int_{t_{2}}^{t_{1}}s\phi^{\prime}(z)\operatorname{d\\!}z\leq(t_{2}-t_{1})\operatorname*{ess\,sup}_{z\in[t_{1},t_{2}]}s\phi^{\prime}(z).$

Recall that, by definition,

$\operatorname*{ess\,sup}_{z\in[t_{1},t_{2}]}s\phi^{\prime}(z)=\inf\left\\{a:\operatorname{Leb}(\\{z\in[t_{1},t_{2}]:\text{$\phi^{\prime}(z)$
exists},\ s\phi^{\prime}(z)>a\\})=0\right\\},$

and thus

$B:=\left\\{z\in[t_{1},t_{2}]:\text{$\phi^{\prime}(z)$ exists},\
s(\phi(t_{2})-\phi(t_{1}))\leq 2\cdot(t_{2}-t_{1})s\phi^{\prime}(z)\right\\}$

satisfies $\operatorname{Leb}(B)>0$. Observe that $B=A$, so
$\operatorname{Leb}(A)>0$, concluding the proof. ∎

###  D.2 Proofs for Section 3.2

######  Theorem 23 (Detailed version of Theorem 5).

There exists a universal constant $C$ such that for any even $d$, even
sawtooth width $t\in\left\\{0,2,\dots d\right\\}$, and accuracy
$\epsilon\in(0,\frac{1}{2})$, there exists a $k$-index (see Appendix A.1)
width-$m$ neural network $g$ with
$\left\|g-\chi\right\|_{L^{\infty}{(\nu)}}\leq\epsilon$ such that:

  1. 1.

If $t\leq C\sqrt{d\ln\frac{1}{\epsilon}}$, then
$k=O(\frac{d^{3/2}}{t+1}\cdot\frac{\log^{1/2}\epsilon}{\epsilon^{2}})$,
$m=O(d^{3/2}\frac{\log^{1/2}\epsilon}{\epsilon^{2}})$, and
$\left\|g\right\|_{\mathcal{R}}=O(d\log\frac{1}{\epsilon})$.

  2. 2.

Otherwise, $k=O(\frac{d^{2}}{\epsilon t^{2}})$, $m=O(\frac{d^{2}}{\epsilon
t})$, and $\left\|g\right\|_{\mathcal{R}}=O(t\sqrt{d})$.

###### Proof.

For
${\mathbf{w}}^{(1)},\dots,{\mathbf{w}}^{(k)}\sim_{\operatorname{iid}}\operatorname{Unif}(\\{\pm
1\\}^{d})$ and
$q:=\operatorname{\mathbb{P}}\left[\left|{\mathbf{w}}^{(1){\scriptscriptstyle{\mathsf{T}}}}x\right|\leq
t\right]$ (for any $x\in\\{\pm 1\\}^{d}$), let

${\mathbf{g}}(x):=\frac{1}{kq}\sum_{j=1}^{k}s_{{\mathbf{w}}^{(j)},t}(x).$

Because
$\operatorname{\mathbb{E}}\left[s_{{\mathbf{w}},t}(x)\right]=q\cdot\chi(x)$,
we have $\operatorname{\mathbb{E}}\left[{\mathbf{g}}(x)\right]=\chi(x)$.
Following the arguments in the proof of Theorem 4, we have
$\left\|{\mathbf{g}}\right\|_{\mathcal{R}}=O(\frac{(t+1)\sqrt{d}}{q})$, and
${\mathbf{g}}$ has width $O(k(t+1))$.

It remains to place a lower bound on $q$ and to show that with non-zero
probability, ${\mathbf{g}}$ uniformly approximates $\chi$. By applying a union
bound, it suffices to show that
$\operatorname{\mathbb{P}}\left[\left|{\mathbf{g}}(x)-\chi(x)\right|\geq\epsilon\right]\leq\frac{1}{2^{d+1}}$
for any fixed $x\in\\{\pm 1\\}^{d}$.

For fixed $x$, let
${\mathbf{r}}(x):=|\\{j\in[k]:|x^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{w}}^{(j)}|>t\\}|$.
We upper-bound the accuracy of approximation of $\chi(x)$ by ${\mathbf{g}}(x)$
in terms of ${\mathbf{r}}(x)$:

$\left|{\mathbf{g}}(x)-\chi(x)\right|=\left|\frac{1}{qk}\sum_{j=1}^{k}\mathbbm{1}\\{|x^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{w}}^{(j)}|\leq
t\\}-q\right|\\\
=\left|\frac{(k-{\mathbf{r}}(x))(1-q)}{qk}-\frac{{\mathbf{r}}(x)q}{qk}\right|=\left|\frac{1-q}{q}-\frac{{\mathbf{r}}(x)}{qk}\right|.$

Define $T:=2\lceil\sqrt{(d/2)\ln(8/\epsilon)}\rceil$, and note that
$\operatorname{\mathbb{P}}\left[|{\mathbf{w}}^{\scriptscriptstyle{\mathsf{T}}}x|\geq
T\right]\leq\frac{\epsilon}{4}$. The proof naturally divides into two cases,
depending on the value of $t$.

Case 1: $t\leq T$. We first lower-bound $q$. Because
${\mathbf{w}}^{\scriptscriptstyle{\mathsf{T}}}x$ is a shifted symmetric
binomial distribution around
${\mathbf{w}}^{\scriptscriptstyle{\mathsf{T}}}x=0$, if
$\left|t^{\prime}\right|\geq\left|t\right|$ and $t^{\prime}\equiv t\pmod{2}$,
then
$\operatorname{\mathbb{P}}\left[{\mathbf{w}}^{\scriptscriptstyle{\mathsf{T}}}x=t^{\prime}\right]\leq\operatorname{\mathbb{P}}\left[{\mathbf{w}}^{\scriptscriptstyle{\mathsf{T}}}x=t\right]$.
Then, for any $t\leq T$:

$\displaystyle q$
$\displaystyle=\sum_{\tau=-t/2}^{t/2}\operatorname{\mathbb{P}}\left[{\mathbf{w}}^{\scriptscriptstyle{\mathsf{T}}}x=2\tau\right]=(t+1)\cdot\frac{1}{t+1}\sum_{\tau=-t/2}^{t/2}\operatorname{\mathbb{P}}\left[{\mathbf{w}}^{\scriptscriptstyle{\mathsf{T}}}x=2\tau\right]$
$\displaystyle\geq(t+1)\cdot\frac{1}{T+1}\sum_{\tau=-T/2}^{T/2}\operatorname{\mathbb{P}}\left[{\mathbf{w}}^{\scriptscriptstyle{\mathsf{T}}}x=2\tau\right]=\frac{t+1}{T+1}\operatorname{\mathbb{P}}\left[|{\mathbf{w}}^{\scriptscriptstyle{\mathsf{T}}}x|\leq
T\right]$
$\displaystyle\geq\frac{(t+1)(1-\frac{\epsilon}{2})}{2\sqrt{d\ln\frac{4}{\epsilon}}}\geq\frac{t+1}{4\sqrt{d\ln\frac{4}{\epsilon}}}.$

Now, we bound ${\mathbf{r}}(x)$ by Bernstein’s inequality (Lemma 14) by taking
$k\geq\frac{Cd^{3/2}\sqrt{\ln\frac{1}{\epsilon}}}{\epsilon^{2}(t+1)}$:

$\displaystyle\operatorname{\mathbb{P}}\left[|{\mathbf{g}}(x)-\chi(x)|>\epsilon\right]$
$\displaystyle=\operatorname{\mathbb{P}}\left[\left|{\mathbf{r}}(x)-\operatorname{\mathbb{E}}[{\mathbf{r}}(x)]\right|>\epsilon
qk\right]$ $\displaystyle\leq
2\exp\left(-\frac{\epsilon^{2}q^{2}k^{2}}{2(kq(1-q)+\epsilon qk/3)}\right)$
$\displaystyle\leq
2\exp\left(-\frac{\epsilon^{2}k(t+1)}{8(1+\epsilon/3)\sqrt{d\ln\frac{4}{\epsilon}}}\right)\leq\frac{1}{2^{d+1}}.$

Case 2: $t\geq T$. By Hoeffding’s inequality (Lemma 12) and the assumption on
$t$, we have $q\geq 1-2\exp(-\frac{2t^{2}}{d})\geq 1-\epsilon/4\geq 3/4$.
Observe that
$\operatorname{\mathbb{E}}\left[{\mathbf{r}}(x)\right]=(1-q)k\leq\frac{\epsilon
k}{4}$.

We show that
$\left|{\mathbf{g}}(x)-\chi(x)\right|=|\frac{1-q}{q}-\frac{{\mathbf{r}}(x)}{qk}|\leq\epsilon$
by showing that ${\mathbf{r}}(x)\leq(1-q)k+\epsilon qk$ and
${\mathbf{r}}(x)\geq(1-q)k-\epsilon qk$. Because $1-q\leq\frac{\epsilon}{4}$
and $q\geq\frac{3}{4}$, $(1-q)k-\epsilon qk\leq-\frac{\epsilon}{2}k$, so the
second inequality is always satisfied because ${\mathbf{r}}(x)\geq 0$. For the
former inequality, it suffices to show that
${\mathbf{r}}(x)\leq\frac{3\epsilon k}{4}$ with probability at least
$1-2^{-(d+1)}$. We take $k\geq\frac{Cd^{2}}{\epsilon t^{2}}$, which implies
$k\geq C(\frac{d}{2\epsilon}+\frac{de^{-2t^{2}/d}}{2\epsilon^{2}})\geq
C(\frac{d}{2\epsilon}+\frac{d(1-q)}{4\epsilon^{2}})$ by the bounds on $t$ and
$q$. Then, by Bernstein’s inequality (Lemma 14), we have

$\displaystyle\operatorname{\mathbb{P}}\left[|{\mathbf{g}}(x)-\chi(x)|>\epsilon\right]$
$\displaystyle=\operatorname{\mathbb{P}}\left[\left|{\mathbf{r}}(x)-\operatorname{\mathbb{E}}[{\mathbf{r}}(x)]\right|>\frac{3\epsilon
k}{4}\right]$ $\displaystyle\leq
2\exp\left(-\frac{9\epsilon^{2}k^{2}/16}{2(kq(1-q)+\epsilon
k/4)}\right)\leq\frac{1}{2^{d+1}},$

so the claim follows. ∎

###  D.3 Proofs for Section 3.3

See 6

###### Proof.

Consider any measure $\mu$ over
$\mathbb{S}^{d-1}\times[-2\sqrt{d},2\sqrt{d}]$, $v\in\mathbb{R}^{d}$, and
$c\in\mathbb{R}$ such that
$g(x)=g_{\mu}(x)+v^{\scriptscriptstyle{\mathsf{T}}}x+c=\int_{\mathbb{S}^{d-1}\times\mathbb{R}}\varphi_{\operatorname{r}}(w^{\scriptscriptstyle{\mathsf{T}}}x+b)\mu(\operatorname{d\\!}w,\operatorname{d\\!}b)$
for all $\left\|x\right\|_{2}\leq d$. We prove the claim by showing that
$\left|\mu\right|\geq\frac{\alpha d}{8}$ for any such $\mu$.

By Fact 1, $\|g-\chi\|_{L^{2}{(\nu)}}\leq 1-\alpha$ implies that $\left\langle
g,\chi\right\rangle\geq\alpha.$ We show that this inner product bound is only
possible if $\left|\mu\right|$ is sufficiently large. By Lemma 24, any fixed
neuron
$r_{w,b}(x):=\varphi_{\operatorname{r}}(w^{\scriptscriptstyle{\mathsf{T}}}x+b)$
has $\left|\left\langle r_{w,b},\chi\right\rangle\right|\leq\frac{8}{d}$.
Because the inner-product over $\\{\pm 1\\}^{d}$ is a discrete sum and $\chi$
is orthogonal to any affine function (such as $x\mapsto
v^{\scriptscriptstyle{\mathsf{T}}}x+c$), we can upper-bound the ability of $g$
to correlate with $\chi$ as follows:

$\displaystyle\left\langle g,\chi\right\rangle_{L^{2}{(\nu)}}$
$\displaystyle=\int_{\mathbb{S}^{d-1}\times\mathbb{R}}\left\langle
r_{w,b},\chi\right\rangle_{L^{2}{(\nu)}}\mu(\operatorname{d\\!}w,\operatorname{d\\!}b)+\operatorname{\mathbb{E}}\left[(v^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{x}}+c)\chi({\mathbf{x}})\right]$
$\displaystyle\leq\int_{\mathbb{S}^{d-1}\times\mathbb{R}}\left|\left\langle
r_{w,b},\chi\right\rangle_{L^{2}{(\nu)}}\right|\left|\mu(\operatorname{d\\!}w,\operatorname{d\\!}b)\right|$
$\displaystyle\leq\frac{8}{d}\int_{\mathbb{S}^{d-1}\times\mathbb{R}}\left|\mu(\operatorname{d\\!}w,\operatorname{d\\!}b)\right|=\frac{8\left|\mu\right|}{d}.$

Thus, $\left\langle g_{\mu},\chi\right\rangle\geq\alpha$ only if
$\left|\mu\right|\geq\frac{\alpha d}{8}$. ∎

######  Fact 1.

For any measure $\nu_{0}$ over $\\{\pm 1\\}^{d}$, $g\in L^{2}(\nu_{0})$,
$h:\\{\pm 1\\}^{d}\to\\{\pm 1\\}$, and $\alpha\in(0,1)$, if
$\left\|g-h\right\|_{L^{2}(\nu_{0})}\leq 1-\alpha$, then $\left\langle
g,h\right\rangle_{L^{2}(\nu_{0})}\geq\alpha$.

###### Proof.

The claim is a consequence of the fact $\left\langle
h,h\right\rangle_{L^{2}(\nu_{0})}=1$ and Cauchy-Schwarz:

$\displaystyle\left\langle g,h\right\rangle_{L^{2}(\nu_{0})}$
$\displaystyle=\left\langle h,h\right\rangle_{L^{2}(\nu_{0})}+\left\langle
g-h,h\right\rangle_{L^{2}(\nu_{0})}$ $\displaystyle=1+\left\langle
g-h,h\right\rangle_{L^{2}(\nu_{0})}$ $\displaystyle\geq
1-\left\|g-h\right\|_{L^{2}(\nu_{0})}$ $\displaystyle\geq
1-(1-\alpha)=\alpha.\qed$

######  Lemma 24.

For $d\geq 8$, $w\in\mathbb{R}^{d}$ with $\left\|w\right\|_{2}\leq 1$, and
$b\in[-2\sqrt{d},2\sqrt{d}]$, the neuron
$r_{w,b}(x):=\varphi_{\operatorname{r}}(w^{\scriptscriptstyle{\mathsf{T}}}x+b)$
satisfies $\left|\left\langle
r_{w,b},\chi\right\rangle\right|\leq\frac{8}{d}$.

######  Remark 6.

Lemma 24 is asymptotically tight. For even $d$, consider the “single-blade”
sawtooth function

$s_{\vec{1},0}(x)=\sqrt{d}(r_{\vec{1}/\sqrt{d},1/\sqrt{d}}(x)-2r_{\vec{1}/\sqrt{d},0}(x)+r_{\vec{1}/\sqrt{d},-1/\sqrt{d}}(x))$

that satisfies
$s_{\vec{1},0}(x)=\chi(x)\mathbbm{1}\\{\vec{1}^{\scriptscriptstyle{\mathsf{T}}}x=0\\}$.
Then,

$\langle s_{\vec{1},0},\chi\rangle_{L^{2}{(\nu)}}=\frac{1}{2^{d}}{d\choose
d/2}\geq\frac{1}{\sqrt{2d}},$

and thus there exists $b$ with $|\langle
r_{\vec{1}/\sqrt{d},b},\chi\rangle_{L^{2}{(\nu)}}|\geq\frac{1}{4\sqrt{2}d}$.

###### Proof.

We directly bound the inner product by showing that we can bound a discrete
second derivative. For any $x\in\\{\pm 1\\}^{d}$, let $x^{j}\in\\{\pm
1\\}^{d}$ denote $x$ with a flipped $j$th bit. That is,
$x^{j}_{i}=(-1)^{\mathbbm{1}\left\\{i=j\right\\}}x_{i}$. Observe that
$\chi(x)=-\chi(x^{j})$.

$\displaystyle\left|\left\langle r_{w,b},\chi\right\rangle\right|$
$\displaystyle=\frac{1}{2^{d}}\left|\sum_{x}r_{w,b}(x)\chi(x)\right|$
$\displaystyle=\frac{1}{4\cdot
2^{d}}\left|\sum_{x}(r_{w,b}(x)\chi(x)+r_{w,b}(x^{j})\chi(x^{j})+r_{w,b}(x^{j^{\prime}})\chi(x^{j^{\prime}})+r_{w,b}(x^{j,j^{\prime}})\chi(x^{j,j^{\prime}}))\right|$
$\displaystyle=\frac{1}{4\cdot
2^{d}}\left|\sum_{x}\chi(x)(r_{w,b}(x)-r_{w,b}(x^{j})-r_{w,b}(x^{j^{\prime}})+r_{w,b}(x^{j,j^{\prime}}))\right|$
$\displaystyle\leq\frac{1}{4\cdot
2^{d}}\sum_{x}|r_{w,b}(x)-r_{w,b}(x^{j})-r_{w,b}(x^{j^{\prime}})+r_{w,b}(x^{j,j^{\prime}})|.$

We say that $(x,x^{j})$ is cut and denote $(x,x^{j})\in C_{j}$ if $x$ and
$x^{j}$ lie on the opposite side of the “hinge” of the neuron $r_{w,b}$, that
is
$\text{sign}(w^{\scriptscriptstyle{\mathsf{T}}}x-b)\neq\text{sign}(w^{\scriptscriptstyle{\mathsf{T}}}x^{j}-b)$.
Let $S_{x,j,j^{\prime}}=\\{x,x^{j},x^{j^{\prime}},x^{j,j^{\prime}}\\}$
represent a “square” in $\\{\pm 1\\}^{d}$, and let $S_{x,j,j^{\prime}}\in
C_{j,j^{\prime}}$ if any of its edges
$(x,x^{j}),(x,x^{j^{\prime}}),(x^{j},x^{j,j^{\prime}}),(x^{j^{\prime}},x^{j,j^{\prime}})$
are cut. We bound the term inside the sum by considering two cases.

  1. 1.

If $S_{x,j,j^{\prime}}\not\in C_{j,j^{\prime}}$, then
$|r_{w,b}(x)-r_{w,b}(x^{j})-r_{w,b}(x^{j^{\prime}})+r_{w,b}(x^{j,j^{\prime}})|=0$.

  2. 2.

Otherwise, the quantity is bounded by Lipschitzness:

$\displaystyle|r_{w,b}(x)-r_{w,b}(x^{j})-r_{w,b}(x^{j^{\prime}})+r_{w,b}(x^{j,j^{\prime}})|$
$\displaystyle\leq|r_{w,b}(x)-r_{w,b}(x^{j})|+|r_{w,b}(x^{j^{\prime}})-r_{w,b}(x^{j,j^{\prime}})|$
$\displaystyle\leq|w^{\scriptscriptstyle{\mathsf{T}}}x-w^{\scriptscriptstyle{\mathsf{T}}}x^{j}|+|w^{\scriptscriptstyle{\mathsf{T}}}x^{j^{\prime}}-w^{\scriptscriptstyle{\mathsf{T}}}x^{j,j^{\prime}}|=4|w_{j}|.$

Therefore, $|\langle r_{w,b},\chi\rangle|\leq\min_{j\neq
j^{\prime}}\frac{1}{2^{d}}\left|C_{j,j^{\prime}}\right||w_{j}|$. It remains to
bound $\left|C_{j,j^{\prime}}\right|$ and $|w_{j}|$ for some $j$ and
$j^{\prime}$. By employing a bound on the total number of cut edges [O’Neil,
1971]:

$\displaystyle\frac{1}{d}\sum_{j=1}^{d}\left|C_{j}\right|$
$\displaystyle\leq\frac{1}{2d}\cdot\left\lceil\frac{d}{2}\right\rceil{d\choose\left\lfloor
d/2\right\rfloor}\leq\frac{2^{d}}{2\sqrt{d}}.$

As a result, at most $\frac{d}{2}$ choices of $j$ satisfy $|C_{j}|\geq
2^{d}/\sqrt{d}$. Because $\left\|w\right\|_{2}\leq 1$, at most $\frac{d}{4}$
coordinates $j$ have $|w_{j}|\geq 2/\sqrt{d}$. Thus, there exist at least
$\frac{d}{4}$ coordinates $j$ satisfying both $|C_{j}|\leq 2^{d}/\sqrt{d}$ and
$|w_{j}|\leq 2/\sqrt{d}$. Assuming $d\geq 8$, let $j,j^{\prime}$ be two of
those coordinates. Since $|C_{j,j^{\prime}}|\leq 2|C_{j}|+2|C_{j^{\prime}}|$,
we conclude that $|C_{j,j^{\prime}}|\leq 4\cdot 2^{d}/\sqrt{d}$, which gives
the desired bound on the inner product. ∎

###  D.4 $\mathcal{R}$-norm lower bound for sampled parity datasets

######  Theorem 25.

Fix any $\delta\in(0,1)$ and $\alpha=\omega(1/d)$, and assume $n\geq
O(d^{3}(\log d+\log(1/\delta)))$. With probability at least $1-\delta$,
$\inf\\{\left\|g\right\|_{\mathcal{R}}:\left\|g-\chi\right\|_{L^{2}{(\boldsymbol{\nu}_{n})}}\leq
1-\alpha\\}\geq\Omega(\alpha d)$.

###### Proof.

Let $g$ be a function with finite $\mathcal{R}$-norm which satisfies the
$L^{2}(\boldsymbol{\nu}_{n})$ approximability condition, which admits an
integral representation due to Proposition 1. That is,

$g(x)=\int_{\mathbb{S}^{d-1}\times[-\sqrt{d},\sqrt{d}]}{(\varphi_{\operatorname{r}}(w^{\scriptscriptstyle{\mathsf{T}}}x+b)-\varphi_{\operatorname{r}}(b))\mu(\operatorname{d\\!}w,\operatorname{d\\!}b)}+c+v^{\scriptscriptstyle{\mathsf{T}}}x\quad\forall
x\in\varOmega$

for some measure $\mu$ and $v\in\mathbb{R}^{d},c=g(0)$. Moreover, $g$ can be
represented compactly as
$g(x)=\bar{g}_{\mu}(x)+v^{\scriptscriptstyle{\mathsf{T}}}x+c$ where
$\bar{g}_{\mu}(x)=g_{\mu}(x)-g_{\mu}(0)$.

By Fact 1, $\left\|g-\chi\right\|_{L^{2}{(\boldsymbol{\nu}_{n})}}\leq
1-\alpha$ only if $\left\langle
g,\chi\right\rangle_{L^{2}{(\boldsymbol{\nu}_{n})}}\geq\alpha$. We use this
correlation to prove lower bounds on $\left|\mu\right|$ (the total variation
of measure $\mu$). At a high level, we upper-bound

$\left\langle
g,\chi\right\rangle_{L^{2}{(\boldsymbol{\nu}_{n})}}=\left\langle\bar{g}_{\mu},\chi\right\rangle_{L^{2}{(\boldsymbol{\nu}_{n})}}+\left\langle
v^{\scriptscriptstyle{\mathsf{T}}}x+c,\chi(x)\right\rangle_{L^{2}{(\boldsymbol{\nu}_{n})}}$

in terms of $\left|\mu\right|$ by relating quantities in
$L^{2}(\boldsymbol{\nu}_{n})$ with their $L^{2}(\nu)$ counterparts. We show
that each component of the sum is small for sufficiently large $n$ and $d$.

We first bound the correlation of the linear combination of neurons with
parity, proving upper bounds on $\left\langle
g,\chi\right\rangle_{L^{2}{(\boldsymbol{\nu}_{n})}}$. We denote
$\bar{r}_{w,b}(x)=\varphi_{\operatorname{r}}(w^{\scriptscriptstyle{\mathsf{T}}}x+b)-\varphi_{\operatorname{r}}(b)$
to be the adjusted ReLU. By the triangle inequality,

$\displaystyle\left\langle\bar{g}_{\mu},\chi\right\rangle_{L^{2}{(\boldsymbol{\nu}_{n})}}$
$\displaystyle\leq\int_{\mathbb{S}^{d-1}\times[-\sqrt{d},\sqrt{d}]}{\left|\left\langle\bar{r}_{w,b},\chi\right\rangle_{L^{2}{(\boldsymbol{\nu}_{n})}}\right|\left|\mu\right|(dw,db)}$
$\displaystyle\leq\left|\mu\right|\sup_{\begin{subarray}{c}w\in\mathbb{S}^{d-1},b\in[-\sqrt{d},\sqrt{d}]\end{subarray}}{\left|\left\langle\bar{r}_{w,b},\chi\right\rangle_{L^{2}{(\boldsymbol{\nu}_{n})}}\right|}.$

Lemmas 24 and 28 together bound the correlation of any neuron $\bar{r}_{w,b}$
with $\chi$. That is, for any $w\in\mathbb{S}^{d-1}$ and
$b\in[-\sqrt{d},\sqrt{d}]$, with probability at least $1-\delta/3$:

$\left|\left\langle\bar{r}_{w,b},\chi\right\rangle_{L^{2}{(\boldsymbol{\nu}_{n})}}\right|\leq\left|\left\langle\bar{r}_{w,b},\chi\right\rangle_{L^{2}{(\nu)}}\right|+C_{1}\sqrt{\frac{d(\ln{n}+\ln(3/\delta))}{n}}\leq\frac{8}{d}+2C_{1}\sqrt{\frac{d\ln{n}}{n}}\leq\frac{C_{2}}{d},$

where $C_{1}$ is the constant from Lemma 28 and
$n>C(d^{3}(\log{d}+\log(1/\delta)))$ by assumption.

We now show that the linear components cannot be substantially correlated with
the parity function and bound $\left\langle
v^{\scriptscriptstyle{\mathsf{T}}}x+c,\chi\right\rangle_{L^{2}{(\boldsymbol{\nu}_{n})}}$.
Because no linear term correlates with the full parity dataset, Lemma 27
provides an upper bound on the inner product between the linear perturbation
and sampled parity dataset and implies the following bound with probability at
least $1-\delta/3$:

$\displaystyle\left|\left\langle
v^{\scriptscriptstyle{\mathsf{T}}}x+c,\chi\right\rangle_{L^{2}{(\boldsymbol{\nu}_{n})}}\right|$
$\displaystyle\leq
8\max\\{\left|\mu\right|,1\\}\sup_{\begin{subarray}{c}\left|c\right|\leq 1\\\
\left\|v\right\|_{2}\leq 1\end{subarray}}{\left|\left\langle
v^{{\scriptscriptstyle{\mathsf{T}}}}x+c,\chi\right\rangle_{L^{2}{(\boldsymbol{\nu}_{n})}}\right|}$
$\displaystyle=8\max\\{\left|\mu\right|,1\\}\left(\left|\frac{1}{n}\sum_{i=1}^{n}{{\mathbf{y}}_{i}}\right|+\left\|\frac{1}{n}\sum_{i=1}^{n}{{\mathbf{y}}_{i}{\mathbf{x}}_{i}}\right\|_{2}\right).$

By Lemma 26 and our assumptions on $n$, we bound the two data-dependent terms
with probability at least $1-\frac{\delta}{3}$ for some absolute constant
$C_{2}$:

$\displaystyle\left|\left\langle
v^{\scriptscriptstyle{\mathsf{T}}}x+c,\chi\right\rangle_{L^{2}{(\boldsymbol{\nu}_{n})}}\right|$
$\displaystyle\leq
8\max\\{\left|\mu\right|,1\\}\left(\sqrt{\frac{2\ln(12/\delta)}{n}}+2\sqrt{\frac{d}{n}}\right)$
$\displaystyle\leq\frac{C_{2}}{d}\max\\{\left|\mu\right|,1\\}.$

Combining both bounds, we have with probability at least $1-\delta$,

$\displaystyle\alpha\leq\left\langle\bar{g}_{\mu}(x)+v^{{\scriptscriptstyle{\mathsf{T}}}}x+c,\chi\right\rangle_{L^{2}{(\boldsymbol{\nu}_{n})}}\leq\frac{C_{2}}{d}\left(\left|\mu\right|+\max\\{\left|\mu\right|,1\\}\right)\leq\frac{2C_{2}}{d}\max\\{\left|\mu\right|,1\\}.$

Therefore, we conclude

$\left|\mu\right|\geq\frac{\alpha d}{2C_{2}}-1.\qed$

######  Lemma 26.

Fix any $\delta\in(0,1)$. Assume $n\geq O(\log(1/\delta))$ and $n=\omega(d)$,
let $\\{({\mathbf{x}}_{i},{\mathbf{y}}_{i})\\}_{i\in[n]}$ be the sampled
parity dataset (where ${\mathbf{y}}_{i}=\chi({\mathbf{x}}_{i})$ for all
$i\in[n]$), and let ${\mathbf{X}}\in\mathbb{R}^{n\times d}$ be the data matrix
containing all samples. All of the following hold with probability $1-\delta$:

  1. (i)

$\left|\frac{1}{n}\sum_{i=1}^{n}{{\mathbf{y}}_{i}}\right|\leq\sqrt{\frac{2\ln(4/\delta)}{n}}$;

  2. (ii)

$\left\|\frac{1}{n}\sum_{i=1}^{n}{{\mathbf{x}}_{i}}\right\|_{2}\leq
2\sqrt{\frac{d}{n}}$;

  3. (iii)

$\left\|\frac{1}{n}\sum_{i=1}^{n}{{\mathbf{y}}_{i}{\mathbf{x}}_{i}}\right\|_{2}\leq
2\sqrt{\frac{d}{n}}$; and

  4. (iv)

$\frac{3}{4}\sqrt{n}\leq\sigma_{d}({\mathbf{X}})\leq\sigma_{1}({\mathbf{X}})\leq
2\sqrt{n}.$

###### Proof.

Claim (i) holds with probability at least $1-\frac{\delta}{2}$ as a result of
a standard application of Hoeffding’s inequality (Lemma 12) to a sum of
Rademacher random variables.

Claim (iv) also holds with probability at least $1-\frac{\delta}{2}$, since
Lemma 17 and the assumptions on $n$ imply that

$\sigma_{1}({\mathbf{X}})\leq\sqrt{n}+C\left(\sqrt{d}+\sqrt{\ln\frac{2}{\delta}}\right)\leq
2\sqrt{n}$

and

$\sigma_{d}({\mathbf{X}})\geq\sqrt{n}-C\left(\sqrt{d}-\sqrt{\ln\frac{2}{\delta}}\right)\geq\frac{3}{4}\sqrt{n}.$

Claims (ii) and (iii) follow from the singular value bounds on ${\mathbf{X}}$.

$\displaystyle\left\|\frac{1}{n}\sum_{i=1}^{n}{{\mathbf{x}}_{i}}\right\|_{2}$
$\displaystyle\leq\frac{1}{n}\sqrt{\operatorname{tr}({\mathbf{X}}^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{X}})}\leq\frac{1}{n}\cdot
2\sqrt{nd}=2\sqrt{\frac{d}{n}};$
$\displaystyle\left\|\frac{1}{n}\sum_{i=1}^{n}{{\mathbf{y}}_{i}{\mathbf{x}}_{i}}\right\|_{2}$
$\displaystyle\leq\frac{1}{n}\sqrt{{\mathbf{y}}^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{X}}{\mathbf{X}}^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{y}}}\leq\frac{1}{n}\cdot\sigma_{1}({\mathbf{X}})\sqrt{d}\leq
2\sqrt{\frac{d}{n}}.\qed$

######  Lemma 27.

Fix any $\delta\in(0,1)$. Assume $n\geq O(\log(1/\delta))$ and $n=\omega(d)$.
With probability at least $1-\delta$ over the random measure
$\boldsymbol{\nu}_{n}$, if $\mu\in\mathcal{M}$ satisfies
$\left\|g_{\mu}({\mathbf{x}})+c+v^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{x}}-\chi({\mathbf{x}})\right\|_{L^{2}{(\boldsymbol{\nu}_{n})}}\leq
1$, then $\max\\{\left|c+g_{\mu}(0)\right|,\left\|v\right\|_{2}\\}\leq
8\max\\{\left|\mu\right|,1\\}.$

###### Proof.

We draw inspiration from the fact that the full parity dataset is orthogonal
to any linear term and can never be well-approximated with large linear
components. In other words, the square loss on approximating the full parity
dataset with a linear function is minimized by the constant-zero function and
strictly worsens as the linear terms increase. That is, orthogonality ensures
that
$\|c+v^{\scriptscriptstyle{\mathsf{T}}}x-\chi(x)\|_{L^{2}{(\nu)}}^{2}=1+|c|^{2}+\|v\|_{2}^{2}$.
Thus, having an upper bound on the squared error imposes similar upper bounds
on the norms of the linear terms. We make a similar argument for the sampled
parity dataset, where we replace $\nu$ with $\boldsymbol{\nu}_{n}$.

Without loss of generality, we incorporate $g_{\mu}(0)$ into $c$ and define
$\bar{g}_{\mu}(x)=g_{\mu}(x)-g_{\mu}(0)$ which can be also represented as
$\bar{g}_{\mu}(x)=\int{\bar{r}_{w,b}(x)\mu(dw,db)}$ where
$\bar{r}_{w,b}=\varphi_{\operatorname{r}}(w^{\scriptscriptstyle{\mathsf{T}}}x+b)-\varphi_{\operatorname{r}}(b)$.
Let ${\mathbf{X}}\in\mathbb{R}^{n\times d}$ be the collection of samples
${\mathbf{x}}_{i}$ and let ${\mathbf{y}}_{i}=\chi({\mathbf{x}}_{i})$. We bound
the squared loss of the linear component
$v^{\scriptscriptstyle{\mathsf{T}}}x+c$, ignoring the neural network
$\bar{g}_{\mu}$:

$\displaystyle\left\|c+v^{\scriptscriptstyle{\mathsf{T}}}x-\chi(x)\right\|_{L^{2}{(\boldsymbol{\nu}_{n})}}^{2}$
$\displaystyle=1+c^{2}+v^{{\scriptscriptstyle{\mathsf{T}}}}\left(\frac{1}{n}\sum_{i=1}^{n}{{\mathbf{x}}_{i}{\mathbf{x}}_{i}^{{\scriptscriptstyle{\mathsf{T}}}}}\right)v-\frac{2}{n}v^{{\scriptscriptstyle{\mathsf{T}}}}\left(\sum_{i=1}^{n}{({\mathbf{y}}_{i}-c){\mathbf{x}}_{i}}\right)-\frac{2c}{n}\sum_{i=1}^{n}{\mathbf{y}}_{i}$
$\displaystyle\geq
1+c^{2}+\frac{1}{n}\left\|v\right\|_{2}^{2}\sigma_{d}({\mathbf{X}})^{2}$
$\displaystyle\quad-2\left\|v\right\|_{2}\left(\left\|\frac{1}{n}\sum_{i=1}^{n}{{\mathbf{y}}_{i}{\mathbf{x}}_{i}}\right\|_{2}+\left|c\right|\left\|\frac{1}{n}\sum_{i=1}^{n}{{\mathbf{x}}_{i}}\right\|_{2}\right)-2\left|c\right|\left|\frac{1}{n}\sum_{i=1}^{n}{{\mathbf{y}}_{i}}\right|.$

With probability $1-\delta$, all events of Lemma 26 hold, and we use them to
lower-bound the squared loss.

$\displaystyle\left\|c+v^{\scriptscriptstyle{\mathsf{T}}}x-\chi(x)\right\|_{L^{2}{(\boldsymbol{\nu}_{n})}}^{2}$
$\displaystyle\geq
1+c^{2}+\frac{9}{16}\left\|v\right\|_{2}^{2}-4\sqrt{\frac{d}{n}}(1+\left|c\right|)\left\|v\right\|_{2}-\frac{2\sqrt{2\ln(8/\delta)}}{\sqrt{n}}\left|c\right|$
$\displaystyle\geq\frac{1}{4}\max\\{\left|c\right|,\left\|v\right\|_{2}\\}^{2}.$

where we have used the assumptions on $n$ and the AM/GM inequality. We now
provide upper bounds on the square loss based on measure $\mu$ using the
triangle inequality:

$\left\|c+v^{\scriptscriptstyle{\mathsf{T}}}x-\chi(x)\right\|_{L^{2}{(\boldsymbol{\nu}_{n})}}\leq\left\|\bar{g}_{\mu}\right\|_{L^{2}{(\boldsymbol{\nu}_{n})}}+\left\|\bar{g}_{\mu}(x)+c+v^{{\scriptscriptstyle{\mathsf{T}}}}x-\chi(x)\right\|_{L^{2}{(\boldsymbol{\nu}_{n})}}\leq\left\|\bar{g}_{\mu}\right\|_{L^{2}{(\boldsymbol{\nu}_{n})}}+1.$

We may now connect $L^{2}(\boldsymbol{\nu}_{n})$ norm of $\bar{g}_{\mu}$ to
its variational norm. We bound the output of $\bar{g}_{\mu}$ on a single input
${\mathbf{x}}_{i}$ by employing Cauchy-Schwarz:

$\displaystyle\bar{g}_{\mu}({\mathbf{x}}_{i})^{2}$
$\displaystyle\leq\left(\int{|\bar{r}_{w,b}({\mathbf{x}}_{i})|\left|\mu\right|(\operatorname{d\\!}w,\operatorname{d\\!}b)}\right)^{2}$
$\displaystyle\leq\left|\mu\right|\int{\bar{r}_{w,b}({\mathbf{x}}_{i})^{2}\left|\mu\right|(\operatorname{d\\!}w,\operatorname{d\\!}b)}.$

We sum over all $i$ to bound the norm of $\bar{g}_{\mu}$:

$\displaystyle\left\|\bar{g}_{\mu}(x)\right\|_{L^{2}{(\boldsymbol{\nu}_{n})}}^{2}$
$\displaystyle\leq\left|\mu\right|\int{\left\|\bar{r}_{w,b}(x)\right\|_{L^{2}{(\boldsymbol{\nu}_{n})}}^{2}}\left|\mu\right|(\operatorname{d\\!}w,\operatorname{d\\!}b)\leq\left|\mu\right|^{2}\sup_{\begin{subarray}{c}w\in\mathbb{S}^{d-1},|b|\leq\sqrt{d}\end{subarray}}{\left\|\bar{r}_{w,b}\right\|_{L^{2}{(\boldsymbol{\nu}_{n})}}^{2}}$
$\displaystyle\leq\left|\mu\right|^{2}\sup_{w\in\mathbb{S}^{d-1}}{\frac{1}{n}\sum_{i=1}^{n}{|w^{{\scriptscriptstyle{\mathsf{T}}}}{\mathbf{x}}_{i}|^{2}}}=\left|\mu\right|^{2}\frac{\sigma_{1}({\mathbf{X}})^{2}}{n}\leq
4\left|\mu\right|^{2}.$

The second inequality relies on the Lipschitzness of
$\varphi_{\operatorname{r}}$. Combining all the above,

$\frac{1}{2}\max\\{\left|c\right|,\left\|v\right\|_{2}\\}\leq\left\|c+v^{\scriptscriptstyle{\mathsf{T}}}x-\chi(x)\right\|_{L^{2}{(\boldsymbol{\nu}_{n})}}\leq
1+\left\|g_{\mu}\right\|_{L^{2}{(\boldsymbol{\nu}_{n})}}<2+2\left|\mu\right|.\qed$

######  Lemma 28.

For
$\bar{r}_{w,b}(x)=\varphi_{\operatorname{r}}(w^{{\scriptscriptstyle{\mathsf{T}}}}x+b)-\varphi_{\operatorname{r}}(b)$
and $n\geq d$, there exists an absolute constant $C$ such that for any
$\delta\in(0,1)$ with probability at least $1-\delta$,

$\left|\left\langle\bar{r}_{w,b},\chi\right\rangle_{L^{2}{(\boldsymbol{\nu}_{n})}}\right|\leq\left|\left\langle\bar{r}_{w,b},\chi\right\rangle_{L^{2}{(\nu)}}\right|+C\sqrt{\frac{d(\ln{n}+\ln(1/\delta))}{n}},$

for all $w\in\mathbb{S}^{d-1},b\in[-\sqrt{d},\sqrt{d}]$.

###### Proof.

Observe that the inner product over the sampled parity dataset is an unbiased
estimate of the inner product over the full parity dataset,

$\operatorname{\mathbb{E}}\left[\left\langle\bar{r}_{w,b},\chi\right\rangle_{L^{2}{(\boldsymbol{\nu}_{n})}}\right]=\left\langle\bar{r}_{w,b},\chi\right\rangle_{L^{2}{(\nu)}}.$

Let ${\mathbf{Z}}_{w,b}$ denote the deviation from the mean, i.e.

${\mathbf{Z}}_{w,b}=\left\langle\bar{r}_{w,b},\chi\right\rangle_{L^{2}{(\boldsymbol{\nu}_{n})}}-\left\langle\bar{r}_{w,b},\chi\right\rangle_{L^{2}{(\nu)}}.$

We use standard concentration of measure techniques for the following steps:

  1. 1.

${\mathbf{Z}}_{w,b}$ is Lipschitz in terms of its parameterization $(w,b)$ in
the sense that
$\left|{\mathbf{Z}}_{w_{1},b_{1}}-{\mathbf{Z}}_{w_{2},b_{2}}\right|\leq
4\sqrt{d}\gamma((w_{1},b_{1}),(w_{2},b_{2}))$, where $\gamma$ is a distance
defined later on.

  2. 2.

${\mathbf{Z}}_{w,b}$ is $O(\frac{1}{\sqrt{n}})$-subgaussian for fixed $w,b$.

  3. 3.

$\operatorname{\mathbb{E}}\left[\sup_{w\in\mathbb{S}^{d-1},b\in[-\sqrt{d},\sqrt{d}]}{\left|{\mathbf{Z}}_{w,b}\right|}\right]=O(\sqrt{\frac{d}{n}})$
using a covering argument.

  4. 4.

The maximum of $\left|{\mathbf{Z}}_{w,b}\right|$ is close to its expectation
due to the bounded difference inequality.

(Step 1) Using the fact that $\varphi_{\operatorname{r}}$ is 1-Lipschitz and
triangle inequality,

$\displaystyle\left|{\mathbf{Z}}_{w_{1},b_{1}}-{\mathbf{Z}}_{w_{2},b_{2}}\right|$
$\displaystyle\leq\left|\left\langle\bar{r}_{w_{1},b_{1}},\chi\right\rangle_{L^{2}{(\boldsymbol{\nu}_{n})}}-\left\langle\bar{r}_{w_{2},b_{2}},\chi\right\rangle_{L^{2}{(\boldsymbol{\nu}_{n})}}\right|+\left|\left\langle\bar{r}_{w_{1},b_{1}},\chi\right\rangle_{L^{2}{(\nu)}}-\left\langle\bar{r}_{w_{2},b_{2}},\chi\right\rangle_{L^{2}{(\nu)}}\right|$
$\displaystyle\leq
2\left\|\bar{r}_{w_{1},b_{1}}-\bar{r}_{w_{2},b_{2}}\right\|_{L^{\infty}{(\nu)}}$
$\displaystyle\leq
2(\left\|\bar{r}_{w_{1},b_{1}}-\bar{r}_{w_{2},b_{1}}\right\|_{L^{\infty}{(\nu)}}+\left\|\bar{r}_{w_{2},b_{1}}-\bar{r}_{w_{2},b_{2}}\right\|_{L^{\infty}{(\nu)}})$
$\displaystyle\leq 2\left(\max_{x\in\\{\pm
1\\}^{d}}(w_{1}-w_{2})^{{\scriptscriptstyle{\mathsf{T}}}}x+2\left|b_{1}-b_{2}\right|\right)$
$\displaystyle\leq
4\sqrt{d}\left(\left\|w_{1}-w_{2}\right\|_{2}+\frac{|b_{1}-b_{2}|}{\sqrt{d}}\right)\eqqcolon
4\sqrt{d}\gamma((w_{1},b_{1}),(w_{2},b_{2})).$

Thus ${\mathbf{Z}}_{w,b}$ is $4\sqrt{d}$-Lipschitz with respect to $\gamma$.

(Step 2) We bound the subgaussianity of ${\mathbf{Z}}_{w,b}$.

$\displaystyle\left\|{\mathbf{Z}}_{w,b}\right\|_{\psi_{2}}$ $\displaystyle\leq
C_{1}\left\|\left\langle\bar{r}_{w,b},\chi\right\rangle_{L^{2}{(\boldsymbol{\nu}_{n})}}\right\|_{\psi_{2}}=C_{1}\left\|\sum_{i=1}^{n}{\mathbf{y}}_{i}(\varphi_{\operatorname{r}}(w^{{\scriptscriptstyle{\mathsf{T}}}}{\mathbf{x}}_{i}+b)-\varphi_{\operatorname{r}}(b))\right\|_{\psi_{2}}$
$\displaystyle\leq\frac{C_{2}}{\sqrt{n}}\left\|{\mathbf{y}}_{1}(\varphi_{\operatorname{r}}(w^{{\scriptscriptstyle{\mathsf{T}}}}{\mathbf{x}}_{1}+b)-\varphi_{\operatorname{r}}(b))\right\|_{\psi_{2}}$
$\displaystyle\leq\frac{C_{2}}{\sqrt{n}}\left\|\varphi_{\operatorname{r}}(w^{{\scriptscriptstyle{\mathsf{T}}}}{\mathbf{x}}_{1}+b)-\varphi_{\operatorname{r}}(b)\right\|_{\psi_{2}}$
$\displaystyle\leq\frac{C_{2}}{\sqrt{n}}\left\|w^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{x}}_{1}\right\|_{\psi_{2}}\leq\frac{2C_{2}}{\sqrt{n}}$

The first, second, and fourth inequalities rely on the centering, averaging,
and Lipschitzness properties of subgaussian random variables in Lemma 16. The
third inequality follows from $\left|{\mathbf{y}}_{1}\right|=1$, and the final
is due to the 2-subgaussianity of a vector with i.i.d. Rademacher components.

(Step 3) Let $\mathcal{N}_{\epsilon}$ be an $\epsilon$-covering of
$\mathbb{S}^{d-1}\times[-\sqrt{d},\sqrt{d}]$ with respect to $\gamma$. We
bound its size using the standard $\epsilon$-net result in Lemma 19 for
$\epsilon\leq 2$.

$\displaystyle\mathcal{N}\left(\epsilon,\mathbb{S}^{d-1}\times[-\sqrt{d},\sqrt{d}],\gamma\right)$
$\displaystyle\leq\mathcal{N}\left(\frac{\epsilon}{2},\mathbb{S}^{d-1},\|\cdot\|_{2}\right)\times\mathcal{N}\left(\frac{\epsilon}{2},[-1,1],|\cdot|\right)$
$\displaystyle\leq\left(\frac{6}{\epsilon}\right)^{d}\cdot\frac{4}{\epsilon}\leq\left(\frac{6}{\epsilon}\right)^{d+1}.$

We bound the expected maximum deviation over all $w$ and $b$ by employing a
bound on the expected maximum of subgaussian random variables (Lemma 16),
applying the covering numbers argument, letting
$\pi(w,b)=\operatorname*{arg\,min}_{(w^{\prime},b^{\prime})\in\mathcal{N}_{\epsilon}}\gamma((w,b),(w^{\prime},b^{\prime}))$,
and setting $\epsilon\coloneqq 1/\sqrt{n}$.

$\displaystyle\operatorname{\mathbb{E}}\left[\sup_{\begin{subarray}{c}w\in\mathbb{S}^{d-1},b\in[-\sqrt{d},\sqrt{d}]\end{subarray}}{\left|{\mathbf{Z}}_{w,b}\right|}\right]$
$\displaystyle\leq\operatorname{\mathbb{E}}\left[\sup_{w,b}{\left|{\mathbf{Z}}_{w,b}-{\mathbf{Z}}_{\pi(w,b)}\right|}\right]+\operatorname{\mathbb{E}}\left[\sup_{(w,b)\in\mathcal{N}_{\epsilon}}{\left|{\mathbf{Z}}_{w,b}\right|}\right]$
$\displaystyle\leq
4\sqrt{d}\epsilon+\frac{2C_{2}}{\sqrt{n}}\sqrt{\ln\mathcal{N}\left(\epsilon,\mathbb{S}^{d-1}\times[-\sqrt{d},\sqrt{d}],\gamma\right)}$
$\displaystyle\leq
4\sqrt{d}\epsilon+2C_{2}\sqrt{\frac{d+1}{n}\ln\frac{6}{\epsilon}}\leq
C_{3}\sqrt{\frac{d\ln n}{n}}.$

(Step 4) We conclude by showing that
$\sup_{w,b}\left|{\mathbf{Z}}_{w,b}\right|$ is close to its expectation with
high probability due to the McDiarmid’s inequality (Lemma 15). Consider a
perturbation where ${\mathbf{x}}_{i}$ is replaced by some
${\mathbf{x}}_{i}^{\prime}\in\\{\pm 1\\}^{d}$ with
${\mathbf{y}}_{i}^{\prime}=\chi({\mathbf{x}}_{i}^{\prime})$, and let
${\mathbf{Z}}_{w,b}^{i}$ denote the resulting deviation term.

$\displaystyle\left|\sup_{w,b}\left|{\mathbf{Z}}_{w,b}\right|-\sup_{w,b}\left|{\mathbf{Z}}_{w,b}^{i}\right|\right|$
$\displaystyle\leq\sup_{w,b}\left|{\mathbf{Z}}_{w,b}-{\mathbf{Z}}_{w,b}^{i}\right|=\frac{1}{n}\sup_{w,b}\left|{\mathbf{y}}_{i}\bar{r}_{w,b}({\mathbf{x}}_{i})-{\mathbf{y}}_{i}^{\prime}\bar{r}_{w,b}({\mathbf{x}}_{i}^{\prime})\right|$
$\displaystyle\leq\frac{1}{n}\sup_{w,b}\left[\left|\bar{r}_{w,b}({\mathbf{x}}_{i})-\bar{r}_{w,b}({\mathbf{x}}_{i}^{\prime})\right|+\left|({\mathbf{y}}_{i}-{\mathbf{y}}_{i}^{\prime})\bar{r}_{w,b}({\mathbf{x}}_{i})\right|\right]$
$\displaystyle\leq\frac{1}{n}\left[\left\|{\mathbf{x}}_{i}-{\mathbf{x}}_{i}^{\prime}\right\|_{2}+2\left\|{\mathbf{x}}_{i}\right\|_{2}\right]\leq\frac{4\sqrt{d}}{n}$

Hence, with probability at least $1-\delta$:

$\sup_{w,b}\left|{\mathbf{Z}}_{w,b}\right|\leq\sqrt{\frac{8d\ln
1/\delta}{n}}+\operatorname{\mathbb{E}}\left[\sup_{w,b}\left|{\mathbf{Z}}_{w,b}\right|\right]\leq
C_{4}\sqrt{\frac{d(\ln n+\ln 1/\delta)}{n}}.$

The bound in the lemma statement immediately follows. ∎

##  Appendix E Proofs for Section 4

###  E.1 Proofs for Section 4.1

######  Lemma 29.

Fix $S\subseteq[d]$ with $|S|\geq 3$, and let
${\mathbf{x}}\sim\operatorname{Unif}(\\{\pm 1\\}^{d})$. Conditional on the
value of $\chi_{S}({\mathbf{x}})$, the random vector ${\mathbf{x}}$ is mean-
zero, isotropic, and satisfies

$\operatorname{\mathbb{E}}\left[\exp(u^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{x}})\mid\chi_{S}({\mathbf{x}})\right]\leq\exp(\|u\|_{2}^{2})$

for all $u=(u_{1},\dotsc,u_{d})\in\mathbb{R}^{d}$.

###### Proof.

The assumption $|S|\geq 3$ implies that, conditioned on
$\chi_{S}({\mathbf{x}})$, the $\\{{\mathbf{x}}_{i}\\}_{i\in[d]}$ are mean-zero
and pairwise uncorrelated. So it remains to show that, for any vector
$u=(u_{1},\dotsc,u_{d})\in\mathbb{R}^{d}$,

$\operatorname{\mathbb{E}}\left[\exp(u^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{x}})\mid\chi_{S}({\mathbf{x}})\right]\leq\exp(\|u\|_{2}^{2}).$

So fix $u$, and fix any $i\in S$. Let $u_{-i}$ (respectively,
${\mathbf{x}}_{-i}$) be the vector obtained from $u$ (respectively,
${\mathbf{x}}$) by removing the $i$-th entry. Observe that
${\mathbf{x}}_{-i}\mid\chi_{S}({\mathbf{x}})\sim\operatorname{Unif}(\\{\pm
1\\}^{d-1})$, and also that
${\mathbf{x}}_{i}\mid\chi_{S}({\mathbf{x}})\sim\operatorname{Unif}(\\{\pm
1\\})$. (But, of course, ${\mathbf{x}}_{-i}$ and ${\mathbf{x}}_{i}$ are not
conditionally independent given $\chi_{S}({\mathbf{x}})$.) Therefore, using
Cauchy-Schwarz,

$\displaystyle\operatorname{\mathbb{E}}\left[\exp(u^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{x}})\mid\chi_{S}({\mathbf{x}})\right]$
$\displaystyle=\operatorname{\mathbb{E}}\left[\exp(u_{-i}^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{x}}_{-i})\exp(u_{i}{\mathbf{x}}_{i})\mid\chi_{S}({\mathbf{x}})\right]$
$\displaystyle\leq\sqrt{\operatorname{\mathbb{E}}\left[\exp(2u_{-i}^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{x}}_{-i})\mid\chi_{S}({\mathbf{x}})\right]}\sqrt{\operatorname{\mathbb{E}}\left[\exp(2u_{i}{\mathbf{x}}_{i})\mid\chi_{S}({\mathbf{x}})\right]}$
$\displaystyle\leq\sqrt{\exp(\|2u_{-i}\|_{2}^{2}/2)}\sqrt{\exp((2u_{i})^{2}/2)}$
$\displaystyle=\exp(\|u\|_{2}^{2}).$

Above, the second inequality uses the moment generating function bound from
Lemma 18, as well as the conditional independence of
$\\{{\mathbf{x}}_{j}:j\neq i\\}$ given $\chi({\mathbf{x}})$. ∎

See 8

###### Proof.

Throughout, we take $C>0$ to be a suitably large constant, and we assume
$n\leq d^{2}/C$. The construction of
${\mathbf{g}}\colon\varOmega\to\mathbb{R}$ is based on typical statistical
behavior of the random examples
$({\mathbf{x}}_{1},{\mathbf{y}}_{1}),\dotsc,({\mathbf{x}}_{n},{\mathbf{y}}_{n})$,
where ${\mathbf{y}}_{i}:=\chi_{S}({\mathbf{x}}_{i})$ for each $i\in[n]$. We
may assume that $n\geq d$, since otherwise the examples can be perfectly fit
with a linear function ${\mathbf{g}}$, and this function has
$\left\|{\mathbf{g}}\right\|_{\mathcal{R}}=0$. So, combining the assumption
$n\geq d$ with the assumption $n\leq d^{2}/C$ implies that $d\geq C$. Observe
that ${\mathbf{y}}_{1},\dotsc,{\mathbf{y}}_{n}$ are i.i.d.
$\operatorname{Unif}(\\{\pm 1\\})$ random variables. Since $n\geq d\geq C$, it
follows by standard binomial tail bounds that with probability at least $5/6$
over the realizations of ${\mathbf{y}}_{1},\dotsc,{\mathbf{y}}_{n}$, the
number of ${\mathbf{y}}_{i}$ that are equal to $1$ is at least $n/3$, and also
that the number of ${\mathbf{y}}_{i}$ that are equal to $-1$ is also at least
$n/3$. We henceforth condition on this “good event” (which depends only on
${\mathbf{y}}_{1},\dotsc,{\mathbf{y}}_{n}$).

To help define our construction of ${\mathbf{g}}\colon\varOmega\to\mathbb{R}$
and set up the rest of the analysis, we partition $[n]$ into disjoint groups
$G_{1},G_{2},\dotsc,G_{m}$ so that for each $j\in[m]$, (i) the size
$n_{j}:=|G_{j}|$ of the $j$-th group is between $c_{1}d/\ln d$ and
$2c_{1}d/\ln d$, and (ii) all ${\mathbf{y}}_{i}$ for $i\in G_{j}$ are the same
(i.e., all $+1$ or all $-1$). Here, with foresight, we set $c_{1}:=1/256$; by
using $d\geq C$, we ensure that each group is non-empty, and also that
$n_{j}<d$. The feasibility of this partitioning is ensured because, in the
“good event” (and using $d\geq C$), the number of $i\in[n]$ with
${\mathbf{y}}_{i}=1$ is at least $n/3\geq d/3\geq c_{1}d/\ln d$, and same for
the number of $i\in[n]$ with ${\mathbf{y}}_{i}=-1$. Let $z^{(j)}$ denote the
common ${\mathbf{y}}_{i}$ value for all $i\in G_{j}$. Finally, note that the
number of groups $m$ satisfies $m\leq n\ln(d)/(c_{1}d)$.

We now define our construction of ${\mathbf{g}}\colon\varOmega\to\mathbb{R}$.
Let ${\mathbf{A}}_{j}$ denote the random $n_{j}\times d$ matrix whose rows are
the ${\mathbf{x}}_{i}^{\scriptscriptstyle{\mathsf{T}}}$ for $i\in G_{j}$, and
define the random vector
${\mathbf{w}}^{(j)}:={\mathbf{A}}_{j}^{{\dagger}}(z^{(j)}\vec{1})$. Observe
that ${\mathbf{w}}^{(j)}$ is a least squares solution to the system of linear
equations
$\\{{\mathbf{x}}_{i}^{\scriptscriptstyle{\mathsf{T}}}w={\mathbf{y}}_{i}:i\in
G_{j}\\}$, since ${\mathbf{y}}_{i}=z^{(j)}$ for all $i\in G_{j}$. We define
${\mathbf{g}}$ as follows:

${\mathbf{g}}(x)=\sum_{j=1}^{m}z^{(j)}\varphi_{\operatorname{r}}(2z^{(j)}{\mathbf{w}}^{(j){\scriptscriptstyle{\mathsf{T}}}}x-1).$

To analyze our construction, we consider the realizations of
${\mathbf{x}}_{1},\dotsc,{\mathbf{x}}_{n}$, and establish some basic
properties that hold with sufficiently high probability (conditional on the
“good event”). Note that within a group $G_{j}$, the
$\\{{\mathbf{x}}_{i}\\}_{i\in G_{j}}$ are (conditionally) iid, and the
realizations across groups are also (conditionally) independent.

We claim that with probability at least $5/6$ (conditional on the “good
event”),

  * •

(P1)
${\mathbf{w}}^{(j){\scriptscriptstyle{\mathsf{T}}}}{\mathbf{x}}_{i}={\mathbf{y}}_{i}$
for all $j\in[m]$ and $i\in G_{j}$;

  * •

(P2) $\|{\mathbf{w}}^{(j)}\|_{2}\leq 2\sqrt{n_{j}/d}$ for all $j\in[m]$.

To establish this claim, we lower-bound the $n_{j}$-th largest singular value
$\sigma_{n_{j}}({\mathbf{A}}_{j})$. Note that
$\sigma_{n_{j}}({\mathbf{A}}_{j})$ is at least the corresponding singular
value of the $n_{j}\times(d-1)$ submatrix ${\mathbf{B}}_{j}$ obtained from
${\mathbf{A}}_{j}$ by removing the $t$-th column of ${\mathbf{A}}_{j}$ for
some $t\in S$. (If $S$ is empty, we may remove any column.) Since the rows of
${\mathbf{A}}_{j}$ are independent, and since the entries of
${\mathbf{x}}_{i}$ after removing the $t$-th one are iid
$\operatorname{Unif}(\\{\pm 1\\})$ random variables, it follows that the
$n_{j}\times(d-1)$ entries of ${\mathbf{B}}_{j}$ are iid
$\operatorname{Unif}(\\{\pm 1\\})$ random variables. Hence, the rows of
${\mathbf{B}}_{j}^{\scriptscriptstyle{\mathsf{T}}}$ are independent, mean-
zero, isotropic, and $O(1)$-subgaussian. By Lemma 17 and a union bound, with
probability at least $1-2m\exp(-\min_{j\in[m]}\\{n_{j}\\})$,

$\sigma_{n_{j}}({\mathbf{A}}_{j})\geq\sigma_{n_{j}}({\mathbf{B}}_{j}^{\scriptscriptstyle{\mathsf{T}}})\geq\sqrt{d-1}-C_{2}\sqrt{n_{j}}\geq\left(\sqrt{1-\frac{1}{d}}-C_{2}\sqrt{\frac{c_{1}}{\ln
d}}\right)\sqrt{d}\quad\text{for all $j\in[m]$},$

where $C_{2}>0$ is twice the absolute constant from Lemma 17, and the final
inequality uses the upper-bound on $n_{j}$. The fact $d\geq C$ and the upper-
bounds on $m$ and $n$ altogether imply that the probability of the above event
is at least $5/6$, and also that $\sqrt{1-1/d}-C_{2}\sqrt{c_{1}/\ln d}\geq
1/2$. So in this event, for each $j\in[m]$, the column space of
${\mathbf{A}}_{j}$ has rank $n_{j}$, so the system of linear equations
defining ${\mathbf{w}}^{(j)}$ is feasible, and

$\|{\mathbf{w}}^{(j)}\|_{2}=\|{\mathbf{A}}_{j}^{\dagger}(z^{(j)}\vec{1})\|_{2}\leq\sigma_{1}({\mathbf{A}}_{j}^{\dagger})\|\vec{1}\|_{2}=\frac{\sqrt{n_{j}}}{\sigma_{n_{j}}({\mathbf{A}}_{j})}\leq
2\sqrt{\frac{n_{j}}{d}}.$

This establishes P1 and P2 in the event as claimed.

We further claim that with probability at least $5/6$ (conditional on the
“good event”),

  * •

(P3) $|{\mathbf{w}}^{(j){\scriptscriptstyle{\mathsf{T}}}}{\mathbf{x}}_{i}|\leq
4\|{\mathbf{w}}^{(j)}\|_{2}\sqrt{\ln d}$ for all $j\in[m]$ and
$i\in[n]\setminus G_{j}$.

To establish this claim, first observe that ${\mathbf{x}}_{i}$ and
${\mathbf{w}}^{(j)}$ are independent for $i\notin G_{j}$. Moreover, by Lemma
29, conditional on ${\mathbf{w}}^{(j)}$ (with $G_{j}\not\ni i$),
${\mathbf{x}}_{i}^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{w}}^{(j)}$ is a
mean-zero random variable satisfying

$\operatorname{\mathbb{E}}\left[\exp({\mathbf{w}}^{(j){\scriptscriptstyle{\mathsf{T}}}}{\mathbf{x}})\mid\chi_{S}({\mathbf{x}}),{\mathbf{w}}^{(j)}\right]\leq\exp(\|{\mathbf{w}}^{(j)}\|_{2}^{2}).$

So, by Markov’s inequality and a union bound, we have with probability at
least $5/6$,

$|{\mathbf{w}}^{(j){\scriptscriptstyle{\mathsf{T}}}}{\mathbf{x}}_{i}|\leq(\sqrt{2}\|{\mathbf{w}}^{(j)}\|_{2})\sqrt{2\ln(12mn)}\quad\text{for
all $j\in[m]$ and $i\in[n]\setminus G_{j}$}.$

Using $d\geq C$ and the upper-bounds on $m$ and $n$, we obtain
$\sqrt{\ln(12mn)}\leq 2\sqrt{\ln d}$, and hence we deduce P3 from the above
inequality.

So, by a union bound, with probability at least $2/3$ (conditional on the
“good event”), the properties P1, P2, and P3 all hold simultaneously. We can
now establish the desired properties of ${\mathbf{g}}$. Using $d\geq C$, P2,
and the upper-bounds on $m$ and $n$, we obtain

$\left\|{\mathbf{g}}\right\|_{\mathcal{R}}\leq
2\sum_{j=1}^{m}\|{\mathbf{w}}^{(j)}\|_{2}\leq
4\sum_{j=1}^{m}\sqrt{\frac{n_{j}}{d}}\leq
4\sqrt{m\sum_{j=1}^{m}\frac{n_{j}}{d}}=4\sqrt{\frac{mn}{d}}\leq\frac{4n\sqrt{\ln
d}}{d}.$

Furthermore, by P1, we have for any $j\in[m]$ and $i\in G_{j}$,

$2z^{(j)}{\mathbf{w}}^{(j){\scriptscriptstyle{\mathsf{T}}}}{\mathbf{x}}_{i}-1=2z^{(j)}{\mathbf{y}}_{i}-1=1.$

And by P2, P3, and the upper-bound on $n_{j}$, we have for any $j\in[m]$ and
$i\in[n]\setminus G_{j}$,

$2z^{(j)}{\mathbf{w}}^{(j){\scriptscriptstyle{\mathsf{T}}}}{\mathbf{x}}_{i}-1\leq
2|{\mathbf{w}}^{(j){\scriptscriptstyle{\mathsf{T}}}}{\mathbf{x}}_{i}|-1\leq
16\sqrt{\frac{n_{j}\ln d}{d}}-1\leq 16\sqrt{c_{1}}-1=0,$

and hence
$\varphi_{\operatorname{r}}(2z^{(j)}{\mathbf{w}}^{(j){\scriptscriptstyle{\mathsf{T}}}}{\mathbf{x}}_{i}-1)=0$.
Therefore, for any $i\in[n]$, if $i\in G_{j}$,