Variation Spaces for Multi-Output Neural Networks: Insights on
  Multi-Task Learning and Network Compression
This paper introduces a novel theoretical framework for the analysis of
vector-valued neural networks through the development of vector-valued
variation spaces, a new class of reproducing kernel Banach spaces. These spaces
emerge from studying the regularization effect of weight decay in training
networks with activations like the rectified linear unit (ReLU). This framework
offers a deeper understanding of multi-output networks and their function-space
characteristics. A key contribution of this work is the development of a
representer theorem for the vector-valued variation spaces. This representer
theorem establishes that shallow vector-valued neural networks are the
solutions to data-fitting problems over these infinite-dimensional spaces,
where the network widths are bounded by the square of the number of training
data. This observation reveals that the norm associated with these
vector-valued variation spaces encourages the learning of features that are
useful for multiple tasks, shedding new light on multi-task learning with
neural networks. Finally, this paper develops a connection between weight-decay
regularization and the multi-task lasso problem. This connection leads to novel
bounds for layer widths in deep networks that depend on the intrinsic
dimensions of the training data representations. This insight not only deepens
the understanding of the deep network architectural requirements, but also
yields a simple convex optimization method for deep neural network compression.
The performance of this compression procedure is evaluated on various
architectures.
Joseph Shenouda, Rahul Parhi, Kangwook Lee, Robert D. Nowak
# Vector-Valued Variation Spaces and Width Bounds for DNNs: Insights on Weight Decay Regularization

###### Abstract

Deep neural networks (DNNs) trained to minimize a loss term plus the sum of squared weights via gradient descent corresponds to the common approach of training with weight decay. This paper provides new insights into this common learning framework. We characterize the kinds of functions learned by training with weight decay for multi-output (vector-valued) ReLU neural networks. This extends previous characterizations that were limited to single-output (scalar-valued) networks. This characterization requires the definition of a new class of neural function spaces that we call vector-valued variation (VV) spaces. We prove that neural networks (NNs) are optimal solutions to learning problems posed over VV spaces via a novel representer theorem. This new representer theorem shows that solutions to these learning problems exist as vector-valued neural networks with widths bounded in terms of the number of training data. Next, via a novel connection to the multi-task lasso problem, we derive new and tighter bounds on the widths of homogeneous layers in DNNs. The bounds are determined by the effective dimensions of the training data embeddings in/out of the layers. This result sheds new light on the architectural requirements for DNNs. Finally, the connection to the multi-task lasso problem suggests a new approach to compressing pre-trained networks.

**Keywords:** deep neural networks, regularization, sparsity, variation spaces, weight decay, multi-task lasso
###### Contents

* 1 Introduction
* 2 Vector-Valued Variation Spaces and Weight Decay
	* 2.1 Scalar-Valued Variation Spaces
	* 2.2 Vector-Valued Variation Spaces
		* 2.2.1 The Effect of the Choice of Norm
		* 2.2.2 A Representer Theorem for Vector-Valued Variation Spaces
		* 2.2.3 The Curse of Dimensionality
* 3 Data-Dependent Tight Bounds on Deep Neural Network Widths
	* 3.1 Weight Decay and Multi-Task Lasso
	* 3.2 Bounds on Sparsity of Multi-Task Lasso Solutions
	* 3.3 Proof of Theorem 9
* 4 Experiments
	* 4.1 Neuron Sharing Simulation
	* 4.2 Multi-Task Lasso Experiments
	* 4.3 Experiments Compressing pre-trained DNNs
* 5 Related Works
* 6 Conclusion and Future Work
* A Proof of Lemma 4
* A.1 Connection to the Total Variation of Function
* B Proof of Theorem 5

## 1 Introduction

Training a deep neural network (DNN) with weight decay and gradient descent corresponds to regularizing with the sum of squared weights. This is a simple yet effective form of regularization that is widely used in practice with many benefits (Bartlett, 1996; Krogh and Hertz, 1991; Bos and Chug, 1996; Zhang et al., 2021; Power et al., 2021; Zhai et al., 2019; Kolesnikov et al., 2020). This paper studies the effect of weight decay on NNs and/or network layers consisting of homogeneous units such as the Rectified Linear Unit (ReLU).

We study DNNs \(f_{\mathbf{\theta}}\) that solve the weight decay objective

\[\min_{\mathbf{\theta}}\sum_{i=1}^{N}\mathcal{L}(\mathbf{y}_{i},f_{\mathbf{\theta}}(\mathbf{x} _{i}))+\frac{\lambda}{2}\|\mathbf{\theta}\|_{2}^{2}. \tag{1}\]

where \(\mathbf{\theta}\) is a vector containing all of the DNN weights and \(\mathcal{L}(\cdot,\cdot)\) is a lower semicontinuous loss function.

Often, DNNs contain many homogeneous activation functions, such as the ReLU. An activation function \(\sigma(z)\) is _homogeneous_ (of degree 1) if \(\sigma(cz)=c\sigma(z)\) for any \(c>0\). A key
observation both in theory (Grandvalet, 1998; Neyshabur et al., 2015; Parhi and Nowak, 2020; Ongie et al., 2020; Jacot, 2023) and practice (Kunin et al., 2021) is that for any DNN that solves (1) the 2-norms of the input and output weights of each homogeneous unit are balanced. This phenomenon is referred to as the neural balance theorem (NBT) (Yang et al., 2022, Theorem 1), which is summarized below.

**Theorem 1** (Neural Balance Theorem (NBT)): _Let \(f_{\mathbf{\theta}}\) be a DNN of any architecture parameterized by \(\mathbf{\theta}\in\Theta\) which solves (1). Then, the weights satisfy the following balance constraint: if \(\mathbf{w}\) and \(\mathbf{v}\) denote the input and output weights of any homogeneous unit in the DNN, then \(\|\mathbf{w}\|_{2}=\|\mathbf{v}\|_{2}\)._

While the NBT is a simple observation, it allows for an alternative perspective on the weight decay regularizer. Concretely, consider the shallow vector-valued NN mapping \(\mathbb{R}^{d}\rightarrow\mathbb{R}^{D}\) with a homogeneous activation function \(\sigma:\mathbb{R}\rightarrow\mathbb{R}\) of the form

\[f_{\mathbf{\theta}}(\mathbf{x})=\sum_{k=1}^{K}\mathbf{v}_{k}\sigma\bigg{(}\mathbf{w}_{k}^{T} \begin{bmatrix}\mathbf{x}\\ 1\end{bmatrix}\bigg{)},\quad\mathbf{x}\in\mathbb{R}^{d},\;\mathbf{\theta}=(\mathbf{v}_{k},\mathbf{w}_{k})_{k=1}^{K},\]

where \(\mathbf{v}_{k}\in\mathbb{R}^{D}\) and \(\mathbf{w}_{k}\in\mathbb{R}^{d+1}\). A consequence of the NBT is that any solution to the NN training problem with weight decay

\[\min_{\mathbf{\theta}}\sum_{i=1}^{N}\mathcal{L}(\mathbf{y}_{i},f_{\mathbf{\theta}}(\mathbf{x}_ {i}))+\frac{\lambda}{2}\sum_{k=1}^{K}\|\mathbf{w}_{k}\|_{2}^{2}+\|\mathbf{v}_{k}\|_{2} ^{2} \tag{2}\]

is also a solution to

\[\min_{\mathbf{\theta}}\sum_{i=1}^{N}\mathcal{L}(\mathbf{y}_{i},f_{\mathbf{\theta}}(\mathbf{x}_ {i}))+\lambda\sum_{k=1}^{K}\|\mathbf{w}_{k}\|_{2}\|\mathbf{v}_{k}\|_{2}. \tag{3}\]

Moreover after a rebalancing step of the weights, any solution to (3) is also a solution to (2). Thus, the problems in (2) and (3) are equivalent. We refer the reader to Yang et al. (2022) or the recent survey of Parhi and Nowak (2023b) for more details about this equivalence and its effect on training DNNs. This observation brings about many remarkable implications. In this paper we exploit this connection and bring several new results.

A novel characterization of the kinds of functions learned by NNs trained with weight decay.We propose a new class of neural function spaces called _vector-valued variation (VV) spaces_. These infinite-dimensional spaces reduce to standard variation spaces (Kurkova and Sanguineti, 2001; Mhaskar, 2004; Bach, 2017) for NNs with single outputs, but more generally VV spaces are the natural spaces associated with multi-output (vector-valued) NNs trained with weight decay; e.g., NNs in multiclass learning problems. We prove a representer theorem which states that finite-width NNs are optimal solutions to data-fitting problems in VV spaces. Analyzing the VV spaces reveals that weight decay favors solutions in which different outputs share neurons, as opposed to networks that use disjoint subsets of neurons for each output. The representer theorem also provides an upper bound on the required width of each layer, depending on the number of training examples and the output dimension of the network. Furthermore, we prove that the VV spaces are "immune" to the curse of dimensionality since they admit dimension-free approximation rates.
Tighter bounds on DNN widths.We show how the weights that solve (1) must also be solutions to a constrained convex optimization, posed over each layer in the deep neural network. Through this connection, we derive new and tighter bounds on the necessary widths of deep neural network layers. The bounds are determined by the effective dimensions of the training data embeddings in/out of the layers, which can be significantly smaller than the previously best known bound found in Jacot et al. (2022, Proposition 7). This sheds new light on architectural requirements for neural nets. Moreover, the connection to the convex optimization suggests a new approach to pruning pre-trained networks. The bounds are based on a reduction to the so-called _multi-task lasso_ problem Obozinski et al. (2006, 2010); Argyriou et al. (2008), and our results provide a novel characterization of the sparsity of multi-task lasso solutions, in general.

## 2 Vector-Valued Variation Spaces and Weight Decay

In this section, we propose a new NN Banach space which we call the vector-valued variation (VV) space. The name refers to the fact that the norm that defines the space is a new type of variation norm (related to the concept of total variation) which generalizes the standard scalar-valued variation spaces and variation norms that have previously been studied (Kurkova and Sanguineti, 2001; Mhaskar, 2004; Bach, 2017). We show that shallow, vector-valued NNs with homogeneous (of degree 1) activation functions (e.g., the ReLU) trained with weight decay are optimal functions in the VV space. To establish this result, we prove a novel _representer theorem_ that shows that finite-width vector-valued NNs are optimal solutions to data-fitting problems in the VV space. This result sheds new light on the kind of regularity that weight decay encourages. While we only focus on activation functions that are homogeneous of degree 1, it is clear how the results generalize to any positively homogeneous activation function (e.g., powers of the ReLU). The primary technical difficulty that arises when defining the VV spaces boils down to which choice of norm the space should be equipped with. Indeed, as we will see in Section 2.2 there are many choices of equivalent norms, but only one corresponds to weight decay.

### Scalar-Valued Variation Spaces

As a warm-up, before we define the vector-valued variation spaces, we first review the definition of the classical, scalar-valued variation spaces and their connection to training NNs with weight decay. The results stated in this subsection can be found in Bengio et al. (2005); Bach (2017); Parhi and Nowak (2021); Siegel and Xu (2023). The main idea is to consider shallow NNs with possibly continuously many neurons. These NNs are parameterized by a finite (Radon) measure. The scalar-valued variation space is the space of functions mapping \(\mathbb{R}^{d}\to\mathbb{R}\)

\[\mathcal{V}(\mathbb{R}^{d})\coloneqq\bigg{\{}f(\mathbf{x})=\int_{\mathbb{S}^{d}} \sigma(\mathbf{w}^{T}\overline{\mathbf{x}})\,\mathrm{d}\nu(\mathbf{w}):\;\mathbf{x}\in\mathbb{ R}^{d},\nu\in\mathcal{M}(\mathbb{S}^{d})\bigg{\}},\]

where \(\mathbb{S}^{d}\coloneqq\{\mathbf{w}\in\mathbb{R}^{d+1}:\,\|\mathbf{w}\|_{2}=1\}\) is the unit sphere, \(\overline{\mathbf{x}}\coloneqq[\mathbf{x}\ 1]^{T}\in\mathbb{R}^{d+1}\) augments \(\mathbf{x}\) to account for a bias term, and \(\mathcal{M}(\mathbb{S}^{d})\) is the space of finite (Radon) measures. Since each
function \(f\in\mathcal{V}(\mathbb{R}^{d})\) is parameterized by a measure \(\nu\in\mathcal{M}(\mathbb{S}^{d})\), we introduce the notation

\[f_{\nu}(\mathbf{x})\coloneqq\int_{\mathbb{S}^{d}}\sigma(\mathbf{w}^{T}\overline{\mathbf{x}} )\,\mathrm{d}\nu(\mathbf{w}),\quad\mathbf{x}\in\mathbb{R}^{d}. \tag{4}\]

The space \(\mathcal{V}(\mathbb{R}^{d})\) is a Banach space when equipped with the norm

\[\|f\|_{\mathcal{V}(\mathbb{R}^{d})}\coloneqq\inf_{\begin{subarray}{c}\nu\in \mathcal{M}(\mathbb{S}^{d})\\ f=f_{\nu}\end{subarray}}\|\nu\|_{\mathcal{M}(\mathbb{S}^{d})}, \tag{5}\]

where \(\|\cdot\|_{\mathcal{M}(\mathbb{S}^{d})}\) denotes the total variation norm in the sense of measures.

The requirement of the \(\inf\) in the definition of the norm arises since the dictionary of neurons \(\{\mathbf{x}\mapsto\sigma(\mathbf{w}^{T}\overline{\mathbf{x}})\}_{\mathbf{w}\in\mathbb{S}^{d}}\) is highly redundant. Thus, there are many different representations for a given \(f\in\mathcal{V}(\mathbb{R}^{d})\). By choosing the representation with the smallest total variation norm, (5) defines a valid Banach norm on \(\mathcal{V}(\mathbb{R}^{d})\). Here, we use the following definition of \(\|\cdot\|_{\mathcal{M}(\mathbb{S}^{d})}\)

\[\|\nu\|_{\mathcal{M}(\mathbb{S}^{d})}\coloneqq\sup_{\begin{subarray}{c}\mathbb{ S}^{d}=\bigcup_{i=1}^{n}A_{i}\end{subarray}}\sum_{i=1}^{n}|\nu(A_{i})|, \tag{6}\]

where \(\sup\) is taken over all partitions of \(\mathbb{S}^{d}\) (i.e., \(A_{i}\cap A_{j}=\varnothing\) for \(i\neq j\)). This definition is equal to the more conventional definition based on the Jordan decomposition of a measure or the definition as a dual norm (Diestel and Uhl, 1977; Bredies and Holler, 2020). That is,

\[\|\nu\|_{\mathcal{M}(\mathbb{S}^{d})}=\nu^{+}(\mathbb{S}^{d})+\nu^{-}(\mathbb{ S}^{d})=\sup_{\begin{subarray}{c}g\in\mathcal{C}(\mathbb{S}^{d})\\ \|g\|_{L\infty}=1\end{subarray}}\int_{\mathbb{S}^{d}}g(\mathbf{u})\,\mathrm{d}\nu (\mathbf{u}),\]

where \(\nu=\nu^{+}-\nu^{-}\) is the Jordan decomposition of \(\nu\) and \(C(\mathbb{S}^{d})\) is the space of continuous functions on \(\mathbb{S}^{d}\). We use definition in (6) as an analogous definition will play an important role in the vector-valued case.

Consider a single neuron \(\phi_{v,\mathbf{w}}(\mathbf{x})\coloneqq v\sigma(\mathbf{w}^{T}\overline{\mathbf{x}})\), \(\mathbf{x}\in\mathbb{R}^{d}\), where \(v\in\mathbb{R}\) and \(\mathbf{w}\in\mathbb{R}^{d+1}\). Since \(\sigma\) is homogeneous of degree \(1\), we have \(\phi_{v,\mathbf{w}}(\mathbf{x})=v\|\mathbf{w}\|_{2}\sigma(\mathbf{w}^{T}\overline{\mathbf{x}}/\| \mathbf{w}\|_{2})\). In this scenario, it is clear that the \(\inf\) in (5) is achieved by the one scaled Dirac measure \(v\|\mathbf{w}\|_{2}\delta_{\mathbf{w}/\|\mathbf{w}\|_{2}}\). Thus, if we have the shallow NN

\[f_{\mathbf{\theta}}(\mathbf{x})=\sum_{k=1}^{K}v_{k}\sigma(\mathbf{w}_{k}^{T}\overline{\mathbf{ x}}),\quad\mathbf{x}\in\mathbb{R}^{d},\,\mathbf{\theta}=(v_{k},\mathbf{w}_{k})_{k=1}^{K},\]

where \(v_{k}\in\mathbb{R}\) and the input weights \(\mathbf{w}_{k}\in\mathbb{R}^{d+1}\) are all unique after normalization1, we have that the \(\inf\) is achieved by

Footnote 1: i.e., \(\mathbf{w}_{k}/\|\mathbf{w}_{k}\|_{2}\), \(k=1,\ldots,K\), are unique.

\[\sum_{k=1}^{K}v_{k}\|\mathbf{w}_{k}\|_{2}\delta_{\mathbf{w}_{k}/\|\mathbf{w}_{k}\|_{2}}.\]
Therefore,

\[\|f_{\mathbf{\theta}}\|_{\mathcal{V}(\mathbb{R}^{d})} =\left\|\sum_{k=1}^{K}v_{k}\|\mathbf{w}_{k}\|_{2}\delta_{\mathbf{w}_{k}/\| \mathbf{w}_{k}\|_{2}}\right\|_{\mathcal{M}(\mathbb{S}^{d})}\] \[=\sum_{k=1}^{K}\Bigl{\|}v_{k}\|\mathbf{w}_{k}\|_{2}\delta_{\mathbf{w}_{k}/ \|\mathbf{w}_{k}\|_{2}}\Bigr{\|}_{\mathcal{M}(\mathbb{S}^{d})}\] \[=\sum_{k=1}^{K}|v_{k}|\|\mathbf{w}_{k}\|_{2}, \tag{7}\]

where in the second line we used the fact that the Dirac measures have disjoint support and in the third line we used the property that \(\|a\delta_{\mathbf{u}}\|_{\mathcal{M}(\mathbb{S}^{d})}=|a|\), where \(a\in\mathbb{R}\) and \(\mathbf{u}\in\mathbb{S}^{d}\). The quantity (7) is often referred to as the _path-norm_(Neyshabur et al., 2015). Furthermore, it is well-known that regularizing a NN with the path-norm is equivalent to the weight decay regularizer (cf., Parhi and Nowak, 2021, Theorem 8). Therefore, training a scalar-output shallow NN with weight decay penalizes the variation norm of the network. This connection is even tighter thanks to the following _Banach space representer theorem_ for the variation spaces.

**Proposition 2** (Parhi and Nowak (2021)): _Let \((\mathbf{x}_{1},y_{1}),\ldots,(\mathbf{x}_{N},y_{N})\in\mathbb{R}^{d}\times\mathbb{R}\) be a finite dataset. Then, there exists a solution to the variational problem_

\[\inf_{f\in\mathcal{V}(\mathbb{R}^{d})}\,\sum_{i=1}^{N}\mathcal{L}(y_{i},f(\mathbf{ x}_{i}))+\lambda\|f\|_{\mathcal{V}(\mathbb{R}^{d})},\quad\lambda>0, \tag{8}\]

_where the loss function \(\mathcal{L}(\cdot,\cdot)\) is lower semicontinuous in its second argument, that takes the form_

\[f^{\star}(\mathbf{x})=\sum_{k=1}^{K_{0}}v_{k}\sigma(\mathbf{w}_{k}^{T}\overline{\mathbf{x} }),\quad\mathbf{x}\in\mathbb{R}^{d},\]

_where \(K_{0}\leq N\). Here, \(v_{k}\in\mathbb{R}\) and \(\mathbf{w}_{k}\in\mathbb{S}^{d}\)._

**Remark 3**: _We note that earlier the works Rosset et al. (2007); Bach (2017) have also considered similar infinite-dimensional variational problems of this form and argue that the solutions admit a finite-parameter representation._

This representer theorem establishes, in particular, that training a sufficiently wide NN (width \(K\geq N\)) with path-norm regularization (7) to a global minimizer results in a solution to (8). By the equivalence of the path-norm regularizer with weight decay, this result says that any solution to the NN training problem

\[\min_{\mathbf{\theta}}\,\sum_{i=1}^{N}\mathcal{L}(y_{i},f(\mathbf{x}_{i}))+\frac{ \lambda}{2}\sum_{k=1}^{K}|v_{k}|^{2}+\|\mathbf{w}_{k}\|_{2}^{2},\quad\lambda>0, \tag{9}\]

is a solution to (8), so long as \(K\geq N\). We refer the reader to Parhi and Nowak (2021, Section 2.3) for more details about this correspondence. Therefore, the regularity (or "smoothness") of the solutions to (9) is exactly quantified by the \(\mathcal{V}(\mathbb{R}^{d})\)-norm. Furthermore, the
\(\mathcal{V}(\mathbb{R}^{d})\)-norm has an analytical description, via the Radon transform (Ongie et al., 2020; Parhi and Nowak, 2021, 2023a). An interesting observation is that the problem in (8) is convex, while the problem in (9) is nonconvex. Thus, by lifting the NN training problem to the space of measures, the training problem has been made convex. For this reason, NNs as in (4) are sometimes called _convex neural networks_(Bengio et al., 2005; Bach, 2017).

### Vector-Valued Variation Spaces

The tight connections between weight decay and \(\mathcal{V}(\mathbb{R}^{d})\) give key insight into the regularity of solutions to neural network training problems. Unfortunately, these results are not straightforward to extend to the vector-valued (or deep) case. In this section we properly define the vector-valued analog of the variation space such that the connection to weight decay remains. While it is clear that the vector-valued variation space is the set of functions

\[\mathcal{V}(\mathbb{R}^{d};\mathbb{R}^{D})\coloneqq\bigg{\{}f(\mathbf{x})=\int_{ \mathbb{S}^{d}}\sigma(\mathbf{w}^{T}\mathbf{\overline{x}})\,\mathrm{d}\mathbf{\nu}(\mathbf{w}) :\;\mathbf{x}\in\mathbb{R}^{d},\mathbf{\nu}\in\mathcal{M}(\mathbb{S}^{d};\mathbb{R}^{ D})\bigg{\}},\]

where \(\mathbf{\nu}\) is now a vector-valued measure (which takes values in \(\mathbb{R}^{D}\) as opposed to \(\mathbb{R}\)), the primary difficulty arises with which choice of norm to impose on the vector-valued measures \(\mathbf{\nu}\in\mathcal{M}(\mathbb{S}^{d};\mathbb{R}^{D})\) such that there remains a correspondence with weight decay. Indeed, \(\mathcal{M}(\mathbb{S}^{d};\mathbb{R}^{D})\) can be equipped with many (equivalent) norms that result in different regularizations of the NN parameters. There have been two lines of work constructing vector-valued variation spaces (Parhi and Nowak, 2022; Korolev, 2022). Unfortunately, neither of these approaches result in NN regularization that corresponds to weight decay.

By viewing \(\mathcal{M}(\mathbb{S}^{d};\mathbb{R}^{D})\) as the \(D\)-fold Cartesian product \(\bigtimes_{j=1}^{D}\mathcal{M}(\mathbb{S}^{d})\), a naive choice of norm would be the mixed norm

\[\|\mathbf{\nu}\|_{\mathcal{M},p}\coloneqq\left(\sum_{j=1}^{D}\|\nu_{j}\|_{ \mathcal{M}(\mathbb{S}^{d})}^{p}\right)^{1/p}=\left(\sum_{j=1}^{D}\left( \sup_{\begin{subarray}{c}\mathbb{S}^{d}=\bigcup_{i=1}^{p}A_{i}\\ n\in\mathbb{N}\end{subarray}}\sum_{i=1}^{n}|\nu_{j}(A_{i})|\right)^{p}\right) ^{1/p},\]

with \(p\geq 1\) and \(\mathbf{\nu}=(\nu_{1},\dots,\nu_{D})\) where each \(\nu_{j}\in\mathcal{M}(\mathbb{S}^{d})\), \(j=1,\dots,D\). A different choice of norm would be

\[\|\mathbf{\nu}\|_{p,\mathcal{M}}\coloneqq\sup_{\begin{subarray}{c}\mathbb{S}^{d}= \bigcup_{i=1}^{p}A_{i}\\ n\in\mathbb{N}\end{subarray}}\sum_{i=1}^{n}\|\mathbf{\nu}(A_{i})\|_{p}=\sup_{ \begin{subarray}{c}\mathbb{S}^{d}=\bigcup_{i=1}^{p}A_{i}\\ n\in\mathbb{N}\end{subarray}}\sum_{i=1}^{n}\left(\sum_{j=1}^{D}|\nu_{j}(A_{i}) |^{p}\right)^{1/p},\]

with \(p\geq 1\). The choice of norm in the above display is the usual definition for the total variation norm of a vector-valued measure. Furthermore, it is well-known that \((\mathcal{M}(\mathbb{S}^{d};\mathbb{R}^{D}),\|\cdot\|_{p,\mathcal{M}})\) is a Banach space. We refer the reader to the monograph of Diestel and Uhl (1977) for a full treatment of vector-valued (and more generally, Banach-valued) measures and the accompanying results.

In essence, the key difference between \(\|\cdot\|_{\mathcal{M},p}\) and \(\|\cdot\|_{p,\mathcal{M}}\) is the order of the \(p\)-norm and \(\mathcal{M}\)-norm. In typical scenarios in which a Banach space is defined by a mixed norm, changing the order of the norms results in different a Banach space2. In the present scenario, since
\(\mathbb{R}^{D}\) is finite-dimensional, it turns out that \(\|\cdot\|_{\mathcal{M},p}\) and \(\|\cdot\|_{q,\mathcal{M}}\) are equivalent norms for any \(p,q\geq 1\). This is summarized in the following lemma.

**Lemma 4**: _The norms \(\|\cdot\|_{p,\mathcal{M}}\), \(p\geq 1\), and \(\|\cdot\|_{\mathcal{M},q}\), \(q\geq 1\), are all equivalent Banach norms for \(\mathcal{M}(\mathbb{S}^{d};\mathbb{R}^{D})\)._

While this result seems obvious, we could not find a proof in the literature. We provide a proof of Lemma 4 in Appendix A. We also note that the reader can quickly verify that when \(D=1\), all norms in Lemma 4 are equal.

Thus, we can define equivalent Banach norms on \(\mathcal{V}(\mathbb{R}^{d};\mathbb{R}^{D})\) in a similar vein to (5) where we use any of the equivalent norms in Lemma 4. Analogous to (4), we introduce the notation

\[f_{\boldsymbol{\nu}}(\boldsymbol{x})\coloneqq\int_{\mathbb{S}^{d}}\sigma( \boldsymbol{w}^{T}\overline{\boldsymbol{x}})\,\mathrm{d}\boldsymbol{\nu}( \boldsymbol{w}),\quad\boldsymbol{x}\in\mathbb{R}^{d}. \tag{10}\]

Each norm on \(\mathcal{M}(\mathbb{S}^{d};\mathbb{R}^{D})\) corresponds to a different regularization of neural network parameters. We seek to define the norm

\[\|f\|_{\mathcal{V}(\mathbb{R}^{d};\mathbb{R}^{D})}\coloneqq\inf_{\begin{subarray} {c}\boldsymbol{\nu}\in\mathcal{M}(\mathbb{S}^{d};\mathbb{R}^{D})\\ f=f_{\boldsymbol{\nu}}\end{subarray}}\llbracket\boldsymbol{\nu}\rrbracket, \tag{11}\]

where \(\llbracket\boldsymbol{\cdot}\rrbracket\) is one of the equivalent norms in Lemma 4 that corresponds to weight decay. Consider a single vector-valued neuron \(\phi_{\boldsymbol{v},\boldsymbol{w}}(\boldsymbol{x})\coloneqq\boldsymbol{v} \sigma(\boldsymbol{w}^{T}\overline{\boldsymbol{x}})\), \(\boldsymbol{x}\in\mathbb{R}^{d}\), where \(\boldsymbol{v}\in\mathbb{R}^{D}\) and \(\boldsymbol{w}\in\mathbb{R}^{d+1}\). Since \(\sigma\) is homogeneous of degree \(1\), we have \(\phi_{\boldsymbol{v},\boldsymbol{w}}(\boldsymbol{x})=\boldsymbol{v}\| \boldsymbol{w}\|_{2}\sigma(\boldsymbol{w}^{T}\overline{\boldsymbol{x}}/\| \boldsymbol{w}\|_{2})\). Clearly, regardless of the choice of \(\llbracket\boldsymbol{\cdot}\rrbracket\)-norm in (11), the inf is achieved by the measure \(\boldsymbol{v}\|\boldsymbol{w}\|_{2}\delta_{\boldsymbol{w}/\|\boldsymbol{w} \|_{2}}\). This is a vector (in \(\mathbb{R}^{D}\)) multiplied by a scalar-valued Dirac measure and is therefore a vector-valued measure in \(\mathcal{M}(\mathbb{S}^{d};\mathbb{R}^{D})\). Thus, if we have the shallow vector-valued NN

\[f_{\boldsymbol{\theta}}(\boldsymbol{x})=\sum_{k=1}^{K}\boldsymbol{v}_{k} \sigma(\boldsymbol{w}_{k}^{T}\overline{\boldsymbol{x}}),\quad\boldsymbol{x} \in\mathbb{R}^{d},\,\boldsymbol{\theta}=(\boldsymbol{v}_{k},\boldsymbol{w}_{k })_{k=1}^{K}, \tag{12}\]

where \(\boldsymbol{v}_{k}\in\mathbb{R}^{D}\) and the input weights \(\boldsymbol{w}_{k}\in\mathbb{R}^{d+1}\) are all unique after normalization, we have that the inf is achieved by

\[\sum_{k=1}^{K}\boldsymbol{v}_{k}\|\boldsymbol{w}_{k}\|_{2}\delta_{\boldsymbol {w}_{k}/\|\boldsymbol{w}_{k}\|_{2}}.\]

Writing \(\boldsymbol{v}_{k}=(v_{k,1},\ldots,v_{k,D})\), a calculation reveals that

\[\left\|\sum_{k=1}^{K}\boldsymbol{v}_{k}\|\boldsymbol{w}_{k}\|_{ 2}\delta_{\boldsymbol{w}_{k}/\|\boldsymbol{w}_{k}\|_{2}}\right\|_{\mathcal{M },p} =\left(\sum_{j=1}^{D}\biggl{\|}\sum_{k=1}^{K}v_{k,j}\|\boldsymbol{w} _{k}\|_{2}\delta_{\boldsymbol{w}_{k}/\|\boldsymbol{w}_{k}\|_{2}}\biggr{\|}_{ \mathcal{M}(\mathbb{S}^{d})}^{p}\right)^{1/p}\] \[=\left(\sum_{j=1}^{D}\biggl{(}\sum_{k=1}^{K}\Bigl{\|}v_{k,j}\| \boldsymbol{w}_{k}\|_{2}\delta_{\boldsymbol{w}_{k}/\|\boldsymbol{w}_{k}\|_{2} }\Bigr{\|}_{\mathcal{M}(\mathbb{S}^{d})}\biggr{)}^{p}\right)^{1/p}\] \[=\left(\sum_{j=1}^{D}\biggl{(}\sum_{k=1}^{K}\lvert v_{k,j}\rvert \|\boldsymbol{w}_{k}\|_{2}\biggr{)}^{p}\right)^{1/p}. \tag{13}\]
Another calculation reveals that

\[\left\|\sum_{k=1}^{K}\mathbf{v}_{k}\|\mathbf{w}_{k}\|_{2}\delta_{\mathbf{w}_{k}/\|\mathbf{w}_{k}\|_ {2}}\right\|_{p,\mathcal{M}}=\sum_{k=1}^{K}\Bigl{\|}\mathbf{v}_{k}\|\mathbf{w}_{k}\|_{2 }\delta_{\mathbf{w}_{k}/\|\mathbf{w}_{k}\|_{2}}\Bigr{\|}_{p,\mathcal{M}}=\sum_{k=1}^{K} \lVert\mathbf{v}_{k}\rVert_{p}\lVert\mathbf{w}_{k}\rVert_{2}, \tag{14}\]

where we used the property that \(\lVert\mathbf{a}\mathbf{\delta}_{\mathbf{u}}\rVert_{p,\mathcal{M}}=\lVert\mathbf{a}\rVert_{p}\), where \(\mathbf{a}\in\mathbb{R}^{D}\) and \(\mathbf{u}\in\mathbb{S}^{d}\) (cf., Boyer et al., 2019, Section 4.2.3). By the equivalence between (2) and (3) from the NBT, we see that the only choice of norm on \(\mathcal{M}(\mathbb{S}^{d};\mathbb{R}^{D})\) that corresponds to weight decay is to choose \(\lVert\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!
We illustrate the types of architectures that are promoted by weight decay in Figure 1 and verify this numerically in Section 4.1. This shows that for the weight decay solution all the output experience strong variation in the same few directions corresponding to the active neurons. An architecture that exhibits neuron sharing is the most natural choice when the network must learn a dataset for which the components of the labels have some relationship or correlation. Multi-class classification tasks are a prime example of such datasets. Therefore, the phenomena of neuron sharing may provide some explanation as to why weight decay is a key ingredient for boosting generalization performance in classification tasks.

#### 2.2.2 A Representer Theorem for Vector-Valued Variation Spaces

**Theorem 5**: _Let \((\mathbf{x}_{1},\mathbf{y}_{1}),\ldots,(\mathbf{x}_{N},\mathbf{y}_{N})\in\mathbb{R}^{d}\times \mathbb{R}^{D}\) be a finite dataset. Then, there exists a solution to the variational problem_

\[\inf_{f\in\mathcal{V}(\mathbb{R}^{d};\mathbb{R}^{D})}\,\sum_{i=1}^{N}\mathcal{ L}(\mathbf{y}_{i},f(\mathbf{x}_{i}))+\lambda\|f\|_{\mathcal{V}(\mathbb{R}^{d}; \mathbb{R}^{D})},\quad\lambda>0, \tag{18}\]

_where the loss function \(\mathcal{L}(\cdot,\cdot)\) is lower semicontinuous in its second argument, which takes the form_

\[f^{\star}(\mathbf{x})=\sum_{k=1}^{K_{0}}\mathbf{v}_{k}\sigma(\mathbf{w}_{k}^{T}\mathbf{ \overline{x}}),\quad\mathbf{x}\in\mathbb{R}^{d},\]

_where \(K_{0}\leq\min\{N^{2},ND\}\). Here, \(\mathbf{v}_{k}\in\mathbb{R}^{D}\) and \(\mathbf{w}_{k}\in\mathbb{S}^{d}\)._

The proof of Theorem 5 appears in Appendix B. What is remarkable here is the bound \(K_{0}\leq N^{2}\). Indeed, for large \(D\), this bound improves the bound of \(ND+1\) predicted by Caratheodory's theorem as it is completely independent of the input and output dimensions. When \(D=1\), Theorem 5 recovers Proposition 2.

**Corollary 6**: _Let \(f_{\mathbf{\theta}}\) denote a shallow vector-valued NN as in (12) and let \(\mathcal{L}(\cdot,\cdot)\) be lower semicontinuous in its second argument. Then, any solution to the neural network training problem_

\[\min_{\mathbf{\theta}}\sum_{i=1}^{N}\mathcal{L}(\mathbf{y}_{i},f(\mathbf{x}_{i}))+\frac{ \lambda}{2}\sum_{k=1}^{K}\lVert\mathbf{v}_{k}\rVert_{2}^{2}+\lVert\mathbf{w}_{k} \rVert_{2}^{2},\quad\lambda>0, \tag{19}\]

_is a solution to the variational problem (18), so long as \(K\geq N\)._

**Proof** By Theorem 5, there always exists a solution to the variational problem (18) that takes the form of a shallow vector-valued NN with less neurons than data. Let \(\Theta_{K}\) denote the space of all NN parameters with width \(K\) such that \(K\geq N\). Thus, there always exists a solution in the space \(\{f_{\mathbf{\theta}}:\,\mathbf{\theta}\in\Theta_{K}\}\subset\mathcal{V}(\mathbb{R}^{ d};\mathbb{R}^{D})\). By (16), any solution to the neural network training problem

\[\min_{\mathbf{\theta}\in\Theta_{K}}\sum_{i=1}^{N}\mathcal{L}(\mathbf{y}_{i},f(\mathbf{x}_{ i}))+\lambda\sum_{k=1}^{K}\lVert\mathbf{v}_{k}\rVert_{2}\lVert\mathbf{w}_{k}\rVert_{2}, \quad\lambda>0,\]
is a solution to (18). The result then follows by the equivalence between the problem in the above display with (19) discussed previously. \(\blacksquare\)

**Remark 7**: _Theorem 5 can be extended to deep networks by considering compositions of functions in \(\mathcal{V}(\mathbb{R}^{d};\mathbb{R}^{D})\) using the same technique outlined in Parhi and Nowak (2022, Section 3)._

#### 2.2.3 The Curse of Dimensionality

The space \(\mathcal{V}(\mathbb{R}^{d};\mathbb{R}^{D})\) has intriguing approximation properties, which carry over from the scalar-valued case (which are well-known). Let \(\mathbb{B}^{d}_{1}\coloneqq\{\mathbf{x}\in\mathbb{R}^{d}:\;\|\mathbf{x}\|_{2}\leq 1\}\) denote the unit

Figure 1: Three neural networks with different sparsity patterns on the weights and their corresponding \(\mathcal{V}(\mathbb{R}^{d};\mathbb{R}^{D})\) norm. By the fact that weight decay minimizes the \(\mathcal{V}(\mathbb{R}^{d};\mathbb{R}^{D})\) norm we see that weight decay regularization invokes a bias towards the right-most architecture which exhibits _neuron sharing_. Each output depends on the same few neurons. This observation gives insight into the regularity of the optimal functions, if each neuron is a ReLU function then it has strong variation in one direction. Thus neuron sharing implies that all the outputs vary strongly in the same few directions. Contrast this with the middle network where each output has variation in a small number of directions, but this set of directions can be different for each output.
ball in \(\mathbb{R}^{d}\) and define

\[\mathcal{V}(\mathbb{B}^{d}_{1};\mathbb{R}^{D})\coloneqq\{f:\mathbb{B}^{d}_{1} \rightarrow\mathbb{R}^{D}:\text{ there exists }g\in\mathcal{V}(\mathbb{R}^{d};\mathbb{R}^{D})\text{ such that }g|_{\mathbb{B}^{d}_{1}}=f\}.\]

This space is a Banach space when equipped with the norm

\[\|f\|_{\mathcal{V}(\mathbb{B}^{d}_{1};\mathbb{R}^{D})}\coloneqq\inf_{\begin{subarray} {c}g\in\mathcal{V}(\mathbb{R}^{d};\mathbb{R}^{D})\\ g|_{\mathbb{B}^{d}}=f\end{subarray}}\|g\|_{\mathcal{V}(\mathbb{R}^{d};\mathbb{R }^{D})}\]

By restricting our attention to a bounded domain, we have the continuous embedding \(\mathcal{V}(\mathbb{B}^{d}_{1};\mathbb{R}^{D})\subset L^{2}(\mathbb{R}^{d}; \mathbb{R}^{D})\). For each \(f=(f_{1},\ldots,f_{D})\in\mathcal{V}(\mathbb{B}^{d}_{1};\mathbb{R}^{D})\), we have for \(j=1,\ldots,D\), \(f_{j}\in\mathcal{V}(\mathbb{B}^{d}_{1})\) (the scalar-valued variation space restricted to \(\mathbb{B}^{d}_{1}\)).

In the scalar-valued case, the Maurey-Jones-Barron lemma (Pisier, 1981; Jones, 1992; Barron, 1993) says that, given \(f_{j}\in\mathcal{V}(\mathbb{B}^{d}_{1})\), there exists a \(K\)-term approximant

\[f_{j}^{K}(\boldsymbol{x})=\sum_{k=1}^{K}v_{k,j}\sigma(\boldsymbol{w}_{k,j}^{T} \boldsymbol{\overline{x}}) \tag{20}\]

with \(v_{k,j}\in\mathbb{R}\) and \(\boldsymbol{w}_{k,j}\in\mathbb{S}^{d}\) such that

\[\|f_{j}-f_{j}^{K}\|_{L^{2}(\mathbb{B}^{d}_{1})}\leq C_{0}C_{\sigma,d}\|f_{j} \|_{\mathcal{V}(\mathbb{B}^{d}_{1})}K^{-1/2}, \tag{21}\]

where \(C_{0}>0\) is an absolute constant, independent of \(d\) and

\[C_{\sigma,d}=\sup_{\boldsymbol{w}\in\mathbb{S}^{d}}\|\boldsymbol{x}\mapsto \sigma(\boldsymbol{w}^{T}\boldsymbol{\overline{x}})\|_{L^{2}(\mathbb{B}^{d}_{ 1})}.\]

This result is remarkable since it establishes that for any function in \(\mathcal{V}(\mathbb{B}^{d}_{1})\), there exists an approximant whose error decays at a rate independent of the input dimension \(d\), although the constant depends on (essentially) the volume the domain \(\mathbb{B}^{d}_{1}\). This result has a straightforward extension to the vector-valued case. This is summarized in the following theorem which proves that for any function in \(\mathcal{V}(\mathbb{B}^{d}_{1};\mathbb{R}^{D})\), there exists a \(K\)-term approximant whose approximation error rate is \(K^{-1/2}\), independent of the input and output dimensions.

**Theorem 8**: _Given \(f\in\mathcal{V}(\mathbb{B}^{d}_{1};\mathbb{R}^{D})\), there exists a \(K\)-term approximant of the form_

\[f_{K}(\boldsymbol{x})=\sum_{k=1}^{K}\boldsymbol{v}_{k}\sigma(\boldsymbol{w}_{k }^{T}\boldsymbol{\overline{x}}),\]

_with \(\boldsymbol{v}_{k}\in\mathbb{R}^{D}\) and \(\boldsymbol{w}_{k}\in\mathbb{S}^{d}\) such that_

\[\|f-f_{K}\|_{L^{2}(\mathbb{B}^{d}_{1};\mathbb{R}^{D})}\leq C_{\sigma,d,D}\|f\| _{\mathcal{V}(\mathbb{B}^{d}_{1};\mathbb{R}^{D})}K^{-1/2},\]

_where \(C_{\sigma,d,D}>0\) depends on, at most, \(\sigma\), \(d\), and \(D\), and the \(L^{2}(\mathbb{B}^{d}_{1};\mathbb{R}^{D})\)-norm is specified by_

\[\|f\|_{L^{2}(\mathbb{B}^{d}_{1};\mathbb{R}^{D})}=\left(\int_{\mathbb{B}^{d}_{1 }}\|f(\boldsymbol{x})\|_{2}^{2}\,\mathrm{d}\boldsymbol{x}\right)^{1/2}.\]
**Proof** First notice that for any \(f=(f_{1},\ldots,f_{D})\in L^{2}(\mathbb{R}^{d};\mathbb{R}^{D})\) we have

\[\|f\|_{L^{2}(\mathbb{B}^{d}_{1};\mathbb{R}^{D})}^{2}=\int_{\mathbb{B}^{d}_{1}}\!\| f(\mathbf{x})\|_{2}^{2}\,\mathrm{d}\mathbf{x}=\int_{\mathbb{B}^{d}_{1}}\!\sum_{j=1}^{D} \lvert f_{j}(\mathbf{x})\rvert^{2}\,\mathrm{d}\mathbf{x}=\sum_{j=1}^{D}\int_{\mathbb{ B}^{d}_{1}}\lvert f_{j}(\mathbf{x})\rvert^{2}\,\mathrm{d}\mathbf{x}=\sum_{j=1}^{D}\lVert f _{j}\rVert_{L^{2}(\mathbb{B}^{d}_{1})}^{2}.\]

For any \(f\in\mathcal{V}(\mathbb{B}^{d}_{1};\mathbb{R}^{D})\) we have

\[\sum_{j=1}^{D}\lVert f_{j}\rVert_{\mathcal{V}(\mathbb{B}^{d}_{1})}^{2}\leq D \!\left(\sum_{j=1}^{D}\lVert f_{j}\rVert_{\mathcal{V}(\mathbb{B}^{d}_{1})} \right)^{2}\]

since \(\lVert\cdot\rVert_{2}\leq\sqrt{D}\lVert\cdot\rVert_{1}\) on \(\mathbb{R}^{D}\). Next,

\[\sum_{j=1}^{D}\lVert f_{j}\rVert_{\mathcal{V}(\mathbb{B}^{d}_{1})} =\sum_{j=1}^{D}\inf_{\begin{subarray}{c}\nu_{j}\in\mathcal{M}( \mathbb{S}^{d})\\ f_{j}=f_{\nu_{j}}\end{subarray}}\lVert\nu_{j}\rVert_{\mathcal{M}(\mathbb{S}^{d})}\] \[\leq\inf_{\begin{subarray}{c}\mathbf{\nu}\in\mathcal{M}(\mathbb{S}^{ d};\mathbb{R}^{D})\\ f=f_{\mathbf{\nu}}\end{subarray}}\sum_{j=1}^{D}\lVert\nu_{j}\rVert_{\mathcal{M}( \mathbb{S}^{d})}\] \[=\inf_{\begin{subarray}{c}\mathbf{\nu}\in\mathcal{M}(\mathbb{S}^{d}; \mathbb{R}^{D})\\ f=f_{\mathbf{\nu}}\end{subarray}}\lVert\mathbf{\nu}\rVert_{\mathcal{M},1}\] \[\leq C_{d,D}\inf_{\begin{subarray}{c}\mathbf{\nu}\in\mathcal{M}( \mathbb{S}^{d};\mathbb{R}^{D})\\ f=f_{\mathbf{\nu}}\end{subarray}}\lVert\mathbf{\nu}\rVert_{2,\mathcal{M}}=C_{d,D}\lVert f \rVert_{\mathcal{V}(\mathbb{B}^{d}_{1};\mathbb{R}^{D})},\]

where the equalities of the form \(f_{j}=f_{\nu_{j}}\) or \(f=f_{\mathbf{\nu}}\) are understood as a function of \(\mathbf{x}\in\mathbb{B}^{d}_{1}\). The fourth line follows by Lemma 4, where the constant \(C_{d,D}>0\) may depend on \(d\) and \(D\).

To prove the claim, given any \(f\in\mathcal{V}(\mathbb{B}^{d}_{1};\mathbb{R}^{D})\), we construct a \(K\)-term approximant \(f_{j}^{K}\) for each component \(f_{j}\), \(j=1,\ldots,D\), as in (21). We then construct the vector-valued function \(f_{DK}=(f_{1}^{K},\ldots,f_{D}^{K})\) which has, at most, \(DK\) terms. This approximant satisfies

\[\lVert f-f_{DK}\rVert_{L^{2}(\mathbb{B}^{d}_{1};\mathbb{R}^{D})}^{2} =\sum_{j=1}^{D}\lVert f_{j}-f_{j}^{K}\rVert_{L^{2}(\mathbb{B}^{d }_{1})}^{2}\] \[\leq\sum_{j=1}^{D}C_{0}^{2}C_{\sigma,d}^{2}\lVert f_{j}\rVert_{ \mathcal{V}(\mathbb{B}^{d}_{1})}^{2}K^{-1}\] \[\leq C_{0}^{2}C_{\sigma,d}^{2}K^{-1}\sum_{j=1}^{D}\lVert f_{j} \rVert_{\mathcal{V}(\mathbb{B}^{d}_{1})}^{2}\] \[\leq C_{0}^{2}C_{\sigma,d}^{2}C_{d,D}^{2}D\lVert f\rVert_{\mathcal{ V}(\mathbb{B}^{d}_{1};\mathbb{R}^{D})}^{2}K^{-1}.\]
Therefore, there exists a constant \(C_{\sigma,d,D}>0\) that depends on \(\sigma\), \(d\), and \(D\) such that

\[\|f-f_{DK}\|_{L^{2}(\mathbb{R}^{d}_{1};\mathbb{R}^{D})}\leq C_{\sigma,d,D}\|f\|_ {\mathcal{V}(\mathbb{R}^{d}_{1};\mathbb{R}^{D})}K^{-1/2},\]

where \(C_{\sigma,d,D}=C_{0}C_{\sigma,d}C_{d,D}\sqrt{D}\), which proves the theorem.

## 3 Data-Dependent Tight Bounds on Deep Neural Network Widths

In this section, by relating the weight decay optimal solution to a convex optimization we provide new and tighter bounds on the sufficient widths of neural network layers. Moreover, these bounds improve upon the previously best known bounds in Jacot et al. (2022, Proposition 7). Our bounds are determined by the effective dimensions of the training data embeddings at each layer. This sheds new light on architectural requirements for neural nets. Moreover, the connection to the convex optimization suggests a new approach to reducing the neurons in pre-trained networks.

Suppose \(\widehat{f}_{\boldsymbol{\theta}}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{D}\) is an optimal solution to (1). Let \(\boldsymbol{w}_{k}\) and \(\boldsymbol{v}_{k}\) be the input and output weights for the \(K^{\ell}\) homogeneous neurons in the \(\ell\)th layer of this network. This layer maps the \(i\)th (internal) feature representation \(\boldsymbol{\phi}_{i}^{\ell-1}\in\mathbb{R}^{K^{\ell-1}}\) (corresponding to the \(i\)th training example \(\boldsymbol{x}_{i}\)) to another feature representation \(\boldsymbol{\psi}_{i}^{\ell}\in\mathbb{R}^{K^{\ell+1}}\) by the following equation

\[\boldsymbol{\psi}_{i}^{\ell}=\sum_{k=1}^{K^{\ell}}\boldsymbol{v}_{k}\sigma( \boldsymbol{w}_{k}^{T}\overline{\boldsymbol{\phi}_{i}^{\ell-1}}), \tag{22}\]

where we recall that \(\overline{\boldsymbol{\phi}_{i}^{\ell-1}}\) appends a \(1\) to \(\boldsymbol{\phi}_{i}^{\ell-1}\) to account for a bias term. When \(\ell=1\), we define \(\boldsymbol{\phi}_{i}^{\ell-1}\coloneqq\boldsymbol{x}_{i}\), the \(i\)th training data. Theorem 5 guarantees the existence of an optimal solution with \(K^{\ell}\leq\min\{N^{2},NK^{\ell+1}\}\). This is, in general, a loose upper bound which scales with the number of training samples \(N\).

In this section, we show that there exist optimal solutions to (1) with far fewer neurons than expected from the representer theorem. More precisely, we provide a data-dependent bound on the necessary width which is a function of the intrinsic dimensions (rank) of the feature representations. Furthermore, our approach provides a constructive method for finding optimal solutions with narrow widths via a simple convex optimization. The main result is summarized as follows.

**Theorem 9**: _Assume \(\widehat{f}_{\boldsymbol{\theta}}\) is a DNN that solves (1). Then for any homogeneous layer of \(\widehat{f}_{\boldsymbol{\theta}}\) with input features \(\boldsymbol{\phi}_{i}^{\ell-1}\) and output features \(\boldsymbol{\psi}_{i}^{\ell}\) and weights \(\{\boldsymbol{w}_{k},\boldsymbol{v}_{k}\}\) such that_

\[\boldsymbol{\psi}_{i}^{\ell}=\sum_{k=1}^{K^{\ell}}\boldsymbol{v}_{k}\sigma( \boldsymbol{w}_{k}^{T}\overline{\boldsymbol{\phi}_{i}^{\ell-1}}),\ i=1,\dots,N \tag{23}\]

_there exists another representation of this layer of the form_

\[\boldsymbol{\psi}_{i}^{\ell}=\sum_{j=1}^{\widehat{K}^{\ell}}\widehat{ \boldsymbol{v}}_{j}\sigma(\boldsymbol{w}_{k_{j}}^{T}\overline{\boldsymbol{ \phi}_{i}^{\ell-1}}),\ i=1,\dots,N \tag{24}\]
_where the number of neurons \(\widehat{K}^{\ell}\) satisfies the following bound:_

\[\widehat{K}^{\ell}\leq R.\]

_Here \(R\) is the product of the dimensions of the the subspace spanned by the output features \(\{\mathbf{\psi}_{i}^{\ell}\}_{i=1}^{N}\) and the post-activation i features \(\{\mathbf{\phi}_{i}^{\ell}\}_{i=1}^{N}\) where_

\[\mathbf{\phi}_{i}^{\ell}=(\sigma(\mathbf{w}_{k}^{T}\overline{\mathbf{\phi}_{i}^{\ell-1}})) _{k=1}^{K^{\ell}}\in\mathbb{R}^{K^{\ell}}\]

_for \(i=1,\cdots,N\)._

We arrive at this result by first reducing the weight decay objective for this layer to a multi-task lasso problem over the output weights. Then by studying the multi-task lasso problem we present a novel proof that there always exists a solution where the number of active groups (corresponding to active neurons) lies within our bounds. Finally, we combine both of these insights to prove Theorem 3.2.

**Remark 10**: _Empirical evidence (Nar et al., 2019; Waleffe and Rekatsinas, 2022; Huh et al., 2023) and theoretical arguments (Papyan et al., 2020; Le and Jegelka, 2022) provide evidence that the feature representations can often be (effectively) low-rank, especially at deeper layers. These observations and Theorem 3.2 suggest that it may be sufficient in practice to use relatively narrow deeper layers. Moreover, by our definition of \(R\), we must have that \(R\leq N^{2}\) therefore even in the case when the feature embeddings are full rank our bounds improve over the upper bound of \(N(N+1)\) of Jacot et al. (2022)._

### Weight Decay and Multi-Task Lasso

Assume \(\widehat{f}_{\mathbf{\theta}}\) is a DNN that solves (1) and that its \(\ell\)th layer is homogeneous with input and output features \(\{\mathbf{\phi}_{i}^{\ell-1},\mathbf{\psi}_{i}^{\ell}\}_{i=1}^{N}\). We now relate weight decay solutions at any homogeneous layer to a (convex) multi-task lasso optimization. The key to this connection is the equivalance of the following three optimization problems (a solution to any one provides a solution to the other two):

\[\begin{split}\min_{\{\mathbf{w}_{k},\mathbf{v}_{k}\}}&\sum _{k=1}^{K^{\ell}}\left(\|\mathbf{v}_{k}\|_{2}^{2}+\|\mathbf{w}_{k}\|_{2}^{2}\right)\\ \text{s.t.}&\mathbf{\psi}_{i}^{\ell}=\sum_{k=1}^{K^{ \ell}}\mathbf{v}_{k}\sigma(\mathbf{w}_{k}^{T}\mathbf{\phi}_{i}^{\ell-1})\,\ i=1,\ldots,N\end{split} \tag{25}\]

\[\begin{split}\min_{\{\mathbf{w}_{k},\mathbf{v}_{k}\}}&\sum _{k=1}^{K^{\ell}}\|\mathbf{v}_{k}\|_{2}\|\mathbf{w}_{k}\|_{2}\\ \text{s.t.}&\mathbf{\psi}_{i}^{\ell}=\sum_{k=1}^{K^{ \ell}}\mathbf{v}_{k}\sigma(\mathbf{w}_{k}^{T}\mathbf{\phi}_{i}^{\ell-1})\,\ i=1,\ldots,N\end{split} \tag{26}\]
\[\begin{split}\min_{\{\mathbf{w}_{k},\mathbf{v}_{k}\}}& \sum_{k=1}^{K^{\ell}}\|\mathbf{v}_{k}\|_{2}\\ \text{s.t.}&\mathbf{\psi}_{i}^{\ell}=\sum_{k=1}^{K^{\ell }}\mathbf{v}_{k}\sigma(\mathbf{w}_{k}^{T}\mathbf{\phi}_{i}^{\ell-1})\text{ and }\|\mathbf{w}_{k}\|_{2}=1\\ & i=1,\ldots,N\end{split} \tag{27}\]

Note that in each of these problems, we are optimizing over the input and output weights of only the \(\ell\)th layer and not the entire DNN. The problem in (25) is the weight decay objective; any solution to this constrained optimization results in a layer that has the same objective value and input-output mappings as the original solution \(\widehat{f}_{\mathbf{\theta}}\). Its solutions are also solutions to problem (26) and vice-versa by Theorem 1. Also because the layer is homogeneous, we may constrain each \(\|\mathbf{w}_{k}\|_{2}=1\) and absorb the overall scale of the neuron into \(\mathbf{v}_{k}\), which leads to problem (27). Clearly, a solution to (26) is also a solution to (27). Moreover, any solution to (27) is also a solution to (25), after redistributing the scale so that \(\|\mathbf{w}_{k}\|_{2}=\|\mathbf{v}_{k}\|_{2}\).

Next consider a fourth optimization problem, which is a (further) constrained version of (27). Let \(\{\widehat{\mathbf{w}}_{k}\}\) denote the input weights of the \(\ell\)th layer of the original weight decay solution \(\widehat{f}_{\mathbf{\theta}}\) and consider

\[\begin{split}\min_{\{\mathbf{v}_{k}\}}& \lambda\sum_{k=1}^{K^{\ell}}\|\mathbf{v}_{k}\|_{2}\\ \text{s.t.}&\mathbf{\psi}_{i}^{\ell}=\sum_{k=1}^{K^{ \ell}}\mathbf{v}_{k}\sigma\big{(}\widehat{\mathbf{w}}_{k}^{T}\mathbf{\phi}_{i}^{\ell-1}/ \|\widehat{\mathbf{w}}_{k}\|_{2}\big{)}\\ & i=1,\ldots,N\end{split} \tag{28}\]

This optimization is like (27) but with the added constraint that the (normalized) input weight vectors are fixed to be the same as those in the original solution. Clearly \(\widehat{\mathbf{v}}_{k}=\|\widehat{\mathbf{w}}_{k}\|_{2}\widehat{\mathbf{v}}_{k}\) is a solution to (27).

Let \(\mathbf{W}\) be a matrix where the rows are the normalized input vectors of the original solution (i.e. the \(k\)th row is \(\widehat{\mathbf{w}}_{k}/\|\widehat{\mathbf{w}}_{k}\|_{2}\)) and define the matrix \(\mathbf{\Phi}^{\ell-1}\) with columns \(\overline{\mathbf{\phi}_{i}^{\ell-1}}\), \(i=1,\ldots,N\).

The post-activation input feature representations are the columns of the matrix

\[\mathbf{\Phi}^{\ell}=\sigma(\mathbf{W}\mathbf{\Phi}^{\ell-1})\.\]

Now if \(\mathbf{V}\) is a matrix where each column is an output weight, then the output feature embeddings are the columns of the matrix \(\mathbf{\Psi}^{\ell}\) where

\[\mathbf{\Psi}^{\ell}=\mathbf{V}\mathbf{\Phi}^{\ell}.\]
With this notation we can express (27) more compactly as the following _multi-task lasso_ problem:

\[\begin{split}\min_{\{\mathbf{v}_{k}\}}&\sum_{k=1}^{K^{ \ell}}\|\mathbf{v}_{k}\|_{2}\\ \text{s.t.}&\mathbf{\Psi}^{\ell}=\mathbf{V}\mathbf{\Phi}^{ \ell}.\end{split} \tag{29}\]

This problem is commonly referred to as the _multi-task lasso_ problem Obozinski et al. (2006, 2010); Argyriou et al. (2008). A solution to this problem will have each column of \(\mathbf{V}\) either entirely zero or non-zero. In our setting, each column of \(\mathbf{V}\) corresponds to a neuron and thus the number of nonzero columns in a solution to (29) determines the number of neurons in the \(\ell\)th layer.

### Bounds on Sparsity of Multi-Task Lasso Solutions

In this section we present our theorem on the sparsity of the multi-task lasso problem. Our proof relies extensively on Caratheodory's theorem (Clarke, 2013, Proposition 2.6) which we first state here

**Theorem 11** (Caratheodory): _Let \(S\) be a subset of a normed vector space with finite dimension \(R\). Then every point \(\mathbf{x}\in\text{Conv}(S)\), the convex hull of \(S\), can be represented by a convex combination of at most \(R+1\) points from \(S\)._

We next present a novel result characterizing the sparsity of the solution to the multi-task lasso problem. Since this applies to any application of the multi-task lasso problem, the result is of interest beyond the neural network setting of this paper.

**Theorem 12**: _Consider the optimization_

\[\min_{\mathbf{V}=[\mathbf{v}_{1},\cdots,\mathbf{v}_{K}]} \sum_{k=1}^{K}\|\mathbf{v}_{k}\|_{2}\] (30) s.t. \[\mathbf{\Psi}=\mathbf{V}\mathbf{\Phi},\]

_where \(\mathbf{\Psi}\in\mathbb{R}^{D\times N}\) and \(\mathbf{\Phi}\in\mathbb{R}^{K\times N}\) are matrices with ranks \(r_{\mathbf{\Phi}}\) and \(r_{\mathbf{\Psi}}\), respectively. Furthermore, assume that the row space of \(\mathbf{\Psi}\) is contained in the row space of \(\mathbf{\Phi}\) and that \(K\geq r_{\mathbf{\Psi}}\). Then, regardless of how much larger \(K\) may be, there exists a solution with at most \(r_{\mathbf{\Phi}}r_{\mathbf{\Psi}}\) nonzero columns. Furthermore, if the rows of \(\mathbf{\Phi}\) are generic points in the \(r_{\mathbf{\Psi}}\)-dimensional space they lie in, then any solution must have at least \(r_{\mathbf{\Phi}}\) nonzero columns._

**Remark 13**: _The upper and lower bounds on the number of nonzero columns has the following intuitive explanation. If every row of \(\mathbf{\Psi}\) is synthesized using the same \(r_{\mathbf{\Phi}}\) rows in \(\mathbf{\Phi}\), then the lower bound is achieved. On the other hand, if \(r_{\mathbf{\Psi}}\) rows in \(\mathbf{\Psi}\) are synthesized using different subsets of \(r_{\mathbf{\Phi}}\) rows in \(\mathbf{\Phi}\), then the upper bound is met. Our computational experiments demonstrate that the minimum number of nonzero columns in any solution may range between the upper and lower bounds depending on precise structures in \(\mathbf{\Psi}\) and \(\mathbf{\Phi}\)._
**Remark 14**: _The lower bound follows from the lower bound on the sparsity of lasso solutions (Tibshirani, 2013). The lasso optimization is equivalent to the optimization above with \(D=1\)._

The hypotheses of the theorem ensure that the feasible set is nonempty and convex. Then, since the objective is coercive, a solution is guaranteed to exist. Suppose that \(\mathbf{V}\) is a solution to our problem. Then we will show that there exists a (possibly different) solution \(\widetilde{\mathbf{V}}\) with no more than \(r_{\boldsymbol{\Phi}}r_{\boldsymbol{\Psi}}\) nonzero columns.

Let \(\mathrm{col}(\mathbf{V})\) and \(\mathrm{col}(\boldsymbol{\Psi})\) denote the column space of \(\mathbf{V}\) and \(\boldsymbol{\Psi}\) respectively. We first show that \(\mathrm{col}(\mathbf{V})=\mathrm{col}(\boldsymbol{\Psi})\). Let \(\mathbf{V}=\mathbf{A}+\mathbf{B}\), where \(\mathbf{A}\in\mathrm{col}(\boldsymbol{\Psi})\) and \(\mathbf{B}\in\mathrm{col}(\boldsymbol{\Psi})^{\perp}\), the component orthogonal to \(\mathrm{col}(\boldsymbol{\Psi})\). Then,

\[\sum_{k=1}^{K}\|\boldsymbol{v}_{k}\|_{2}=\sum_{k=1}^{K}\sqrt{\|\boldsymbol{a} \|_{2}^{2}+\|\boldsymbol{b}\|_{2}^{2}}\]

Let \(\mathbf{P}_{\mathrm{col}(\boldsymbol{\Psi})}\) be the orthogonal projection onto \(\mathrm{col}(\boldsymbol{\Psi})\). We can then express the constraint \(\boldsymbol{\Psi}=\mathbf{P}_{\mathrm{col}(\boldsymbol{\Psi})}\boldsymbol{ \Psi}=\mathbf{P}_{\mathrm{col}(\boldsymbol{\Psi})}(\mathbf{A}+\mathbf{B}) \boldsymbol{\Phi}=\mathbf{A}\boldsymbol{\Phi}\). Thus the solution must have \(\mathbf{B}=0\), since anything nonzero would increase the objective without contributing to the constraint. Therefore, \(\mathrm{col}(\mathbf{V})=\mathrm{col}(\boldsymbol{\Psi})\) and \(\mathrm{rank}(\mathbf{V})=\mathrm{rank}(\boldsymbol{\Psi})\).

Now observe that we can also express the constraint as a sum of outer products,

\[\boldsymbol{\Psi}=\sum_{k=1}^{K}\boldsymbol{v}_{k}\boldsymbol{\phi}_{k}^{T}\]

where \(\boldsymbol{v}_{k}\) are the columns of \(\mathbf{V}\) and \(\boldsymbol{\phi}_{k}^{T}\) are the rows of \(\boldsymbol{\Phi}\). Let \(\mathbf{M}_{k}=\boldsymbol{v}_{k}\boldsymbol{\phi}_{k}^{T}\). Since the \(\boldsymbol{v}_{k}\) belong to an \(r_{\boldsymbol{\Psi}}\) dimensional subspace and the \(\boldsymbol{\phi}_{k}\) belong to an \(r_{\boldsymbol{\Phi}}\) dimensional subspace, the \(\mathbf{M}_{k}\) all belong to a subspace of dimension at most \(r_{\boldsymbol{\Phi}}r_{\boldsymbol{\Psi}}\), for ease of notation let \(R=r_{\boldsymbol{\Phi}}r_{\boldsymbol{\Psi}}\).

Now, define the optimal objective value \(\gamma=\sum_{k=1}^{K}\|\boldsymbol{v}_{k}\|_{2}\) and \(\alpha_{k}=\|\boldsymbol{v}_{k}\|_{2}/\gamma\) so that \(\sum_{k=1}^{K}\alpha_{k}=1\). We can then write \(\boldsymbol{\Psi}\) as

\[\boldsymbol{\Psi}=\sum_{k=1}^{K}\alpha_{k}\left(\frac{1}{\alpha_{k}}\mathbf{M }_{k}\right)=\sum_{k=1}^{K}\alpha_{k}\widetilde{\mathbf{M}}_{k}.\]

This shows that \(\boldsymbol{\Psi}\) is in the convex hull of matrices \(\widetilde{\mathbf{M}}_{k}\) with dimension at most \(R\). Caratheodory's theorem implies that we can represent \(\boldsymbol{\Psi}\) by a convex combination of a subset \(\{\widetilde{\mathbf{M}}_{j}\}_{j\in J}\) where \(J\subset\{1,\cdots,K\}\) and \(|J|\leq R+1\). Thus we can represent \(\boldsymbol{\Psi}\) with no more than \(R+1\) nonzero columns vectors in the solution

\[\boldsymbol{\Psi}=\sum_{j\in J}\beta_{j}\widetilde{\mathbf{M}}_{j}\ =\ \sum_{j\in J}\beta_{j}\left(\frac{1}{\alpha_{j}}\boldsymbol{v}_{j} \boldsymbol{\phi}_{j}^{T}\right)\]

We now apply Caratheodory's again to show that we can satisfy the constraint with no more than \(R\) nonzero columns. Assume that \(|J|=R+1\) (otherwise we are done) and define \(\widetilde{\boldsymbol{v}}_{j}=\frac{1}{\alpha_{j}}\boldsymbol{v}_{j}\). Thus \(\boldsymbol{\Psi}\) is in the convex hull of

\[\left\{\widetilde{\boldsymbol{v}}_{j}\boldsymbol{\phi}_{j}^{T}\right\}_{j\in J}.\]
Each matrix \(\widetilde{\mathbf{v}}_{j}\mathbf{\phi}_{j}^{T}\) belongs to a subspace of dimension at most \(R\), therefore, any matrix in this set can be expressed as a linear combination of the others

\[\widetilde{\mathbf{v}}_{i}\mathbf{\phi}_{i}^{T}=\sum_{j\in J;j\neq i}c_{j} \widetilde{\mathbf{v}}_{j}\mathbf{\phi}_{j}^{T}.\]

By the subgradient optimality conditions, we will prove that we must have \(\sum_{j\in J;j\neq i}c_{j}=1\). This in turn implies that the set of matrices \(\{\widetilde{\mathbf{v}}_{j}\mathbf{\phi}_{j}^{T}\}_{j\in J}\) are not only linearly dependent but they also span an \(R-1\) dimensional affine space (i.e., an \(R-1\) dimensional hyperplane not including the origin (Rockafellar, 1997)). We can then apply Caratheodory's again to show that a convex combination of \(R\) matrices from this set suffices to satisfy the constraint.

The Lagrangian of 30 is

\[\mathcal{L}(\mathbf{V},\nu_{1},\nu_{2})=\sum_{k=1}^{K}\|\mathbf{v}_{k} \|_{2}+\nu_{1}^{T}(\mathbf{\Psi}-\mathbf{V}\mathbf{\Phi})\nu_{2}\]

with Lagrange multipliers \(\nu_{1}\in\mathbb{R}^{D}\) and \(\nu_{2}\in\mathbb{R}^{N}\). By the KKT conditions, any solution must satisfy

\[0\in\partial_{\mathbf{V}}\mathcal{L},\] \[0=\nabla_{\nu_{1},\nu_{2}}\mathcal{L}.\]

Now for our original solution \(\mathbf{V}\) we have,

\[\partial_{\mathbf{V}}\mathcal{L} =\partial\left(\sum_{k=1}^{K}\|\mathbf{v}_{k}\|_{2}\right)-\nu_{1}( \mathbf{\Phi}\nu_{2})^{T}=0 \tag{31}\] \[\nabla_{\nu_{1},\nu_{2}}\mathcal{L} =\mathbf{\Psi}-\mathbf{V}\mathbf{\Phi}=0 \tag{32}\]

Note we have no restriction of \(\nu_{1}\) and \(\nu_{2}\). Then for any \(j\in J\) (the nonzero columns of \(\mathbf{V}\)) the \(j\)th column of the subgradient of our objective is

\[\partial_{\mathbf{V}}\left(\sum_{k=1}^{K}\|\mathbf{v}_{k}\|_{2}\right) _{j}=\frac{\mathbf{v}_{j}}{\|\mathbf{v}_{j}\|_{2}}.\]

Therefore, by Equation (31) for the \(j\)th column of the subgradient we have

\[\partial\left(\sum_{k=1}^{K}\|\mathbf{v}_{k}\|_{2}\right)_{j} =\nu_{1}\nu_{2}^{T}\phi_{j} \tag{33}\] \[\implies\frac{\mathbf{v}_{j}}{\|\mathbf{v}_{j}\|_{2}} =\nu_{1}\nu_{2}^{T}\phi_{j} \tag{34}\]

where \(\phi_{j}\in\mathbb{R}^{N\times 1}\) is the \(j\)th row of \(\mathbf{\Phi}\). Now consider the \(i\)th column of Equation (31) and right-multiply both sides by \(\widetilde{\mathbf{v}}_{i}^{T}\) to obtain

\[\frac{\mathbf{v}_{i}\widetilde{\mathbf{v}}_{i}^{T}}{\|\mathbf{v}_{i}\|_{2}} =\nu_{1}\nu_{2}^{T}\mathbf{\phi}_{i}\widetilde{\mathbf{v}}_{i}^{T}.\]
By the linear dependence of the matrices \(\{\widetilde{\mathbf{v}}_{j}\mathbf{\phi}_{j}^{T}\}_{j\in J}\) for any \(i\in J\) we have \(\mathbf{\phi}_{i}\widetilde{\mathbf{v}}_{i}^{T}=\sum_{j\in J;j\neq i}c_{j}\mathbf{\phi}_{j} \widetilde{\mathbf{v}}_{j}^{T}\) for some constants \(c_{j}\), substituting this in we get

\[\frac{\mathbf{v}_{i}\widetilde{\mathbf{v}}_{i}^{T}}{\|\mathbf{v}_{i}\|_{2}} =\nu_{1}\nu_{2}^{T}\sum_{j\in J;j\neq i}c_{j}\mathbf{\phi}_{j} \widetilde{\mathbf{v}}_{j}^{T}\] \[=\sum_{j\in J;j\neq i}c_{j}\nu_{1}\nu_{2}^{T}\mathbf{\phi}_{j} \widetilde{\mathbf{v}}_{j}^{T}\] \[=\sum_{j\in J;j\neq i}c_{j}\frac{\mathbf{v}_{j}\widetilde{\mathbf{v}}_{j} ^{T}}{\|\mathbf{v}_{j}\|_{2}}\]

where the final equality follows from Equation (34). Now recall that \(\widetilde{\mathbf{v}}_{j}=\frac{1}{\alpha_{j}}\mathbf{v}_{j}=\frac{\gamma}{\|\mathbf{v}_ {j}\|_{2}}\mathbf{v}_{j}\) plugging this in on both sides and cancelling out the \(\gamma\) we have

\[\frac{\mathbf{v}_{i}\mathbf{v}_{i}^{T}}{\|\mathbf{v}_{i}\|_{2}^{2}}=\sum_{j\in J;j\neq i}c _{j}\frac{\mathbf{v}_{j}\mathbf{v}_{j}^{T}}{\|\mathbf{v}_{j}\|_{2}^{2}}.\]

Taking the trace of the left and right hand sides gives us

\[\sum_{j\neq i}c_{j}=1\]

Therefore any \(\mathbf{\phi}_{i}\widetilde{\mathbf{v}}_{i}^{T}\) is in the affine hull of the other matrices and thus the matrices \(\{\widetilde{\mathbf{v}}_{j}\mathbf{\phi}_{j}^{T}\}_{j\in J}\) form an affine set of dimension \(R-1\)(Rockafellar, 1997). This implies that the matrices do not just span an \(R\) subspace but rather an \(R-1\) dimensional hyperplane that does not pass through the origin. Thus the vector space corresponding to this set of matrices has dimension \(R-1\) and so we can apply Caratheodory's theorem again to represent the constraint as a convex combination of just \(R\) nonzero vectors

\[\mathbf{\Psi}=\sum_{j\in J^{\prime}}\widehat{\beta}_{j}\widetilde{\mathbf{v}}_{j}\bm {\phi}_{j}^{T}=\sum_{j\in J^{\prime}}\mathbf{v}_{j}^{*}\mathbf{\phi}_{j}^{T}\]

where \(\mathbf{v}_{j}^{*}:=\widehat{\beta}_{j}\widetilde{\mathbf{v}}_{j}\), \(J^{\prime}\subset\{1,\cdots,K\}\) and \(|J^{\prime}|\leq R=r_{\mathbf{\Phi}}r_{\mathbf{\Psi}}\). The coefficients \(\widehat{\beta}_{j}\) are nonnegative and sum to \(1\). Finally, it remains to show that this new representation of \(\mathbf{\Psi}\) has the same objective value as the original solution, indeed we have

\[\sum_{j\in J^{\prime}}\|\mathbf{v}_{j}^{*}\|_{2}=\sum_{j\in J^{\prime}}\frac{ \widehat{\beta}_{j}}{\alpha_{j}}\|\mathbf{v}_{j}\|_{2}=\sum_{j\in J^{\prime}} \gamma\widehat{\beta}_{j}=\gamma\]

where we recall that \(\gamma\) is the objective value obtained by our original assumed solution.

The lower bound is a direct consequence of the constraint. Assuming that the rows of \(\mathbf{\Phi}\) and \(\mathbf{\Psi}\) are generic3 each row of \(\mathbf{\Psi}\) is a linear combination of at least \(r_{\mathbf{\Phi}}\) rows of \(\mathbf{\Phi}\). This implies that each row of \(\mathbf{V}\) has at least \(r_{\mathbf{\Phi}}\) nonzero entries and thus the number of nonzero columns in \(\mathbf{V}\) must be at least \(r_{\mathbf{\Phi}}\).
### Proof of Theorem 3.1

We now combine the results from Sections 3.1 and 3.2 to prove Theorem 3.1.

**Proof** Since \(\widehat{f}_{\boldsymbol{\theta}}\) is optimal, any solution to (29) is also a solution to (26). Let \(\widehat{K}\) be the number of nonzero columns in the solution to (29). By Theorem (12) there exists a solution \(\widehat{\mathbf{V}}\) to (29) such that \(\widehat{K}\leq r_{\boldsymbol{\Phi}}r_{\boldsymbol{\Psi}}\). By balancing the output weights in the solution \(\widehat{\mathbf{V}}\) with the input weights in \(\widehat{\mathbf{W}}\) we get a solution to (25) with only \(\widehat{K}\) active neurons. Thus there exists a solution in which the \(\ell\)-th layer has only \(\widehat{K}\) neurons with optimal weights.

## 4 Experiments

In this section we present three experiments that validate our theory and demonstrate its potential utility. Our first experiment is a numerical simulation that demonstrates how weight decay encourages neurons sharing for a simple two dimensional data fitting problem. Our second set of experiments validate the bound presented for the multi-task lasso problem in Theorem Theorem 3.1 using synthetic data.

In the third set of experiments, we compress the homogenous layers of two pre-trained deep neural network models VGG19 (Simonyan and Zisserman, 2014; Wang et al., 2021) and AlexNet (Krizhevsky et al., 2017) via the multi-task lasso convex optimization problem. We show how in some cases, this principled compression approach can reduce the number of neurons in a layer 10 fold while preserving nearly the same loss on the entire training dataset as well as accuracy on the test set. Remarkably, we find that compressing sometimes helps in generalization performance.4

Footnote 4: The code for reproducing all of our experiments can be found at [https://github.com/joeshenouda/vv-spaces-nn-width](https://github.com/joeshenouda/vv-spaces-nn-width) following the guidance in Shenouda and Bajwa (2023).

### Neuron Sharing Simulation

To demonstrate the neuron sharing phenomenon induced by weight decay we trained two vector-valued shallow ReLU neural networks to fit a synthetic two-dimensional dataset. The dataset consists of fifty samples where the features are two-dimensional vectors sampled from a multivariate normal distribution and the labels are also two-dimensional, generated by passing these feature vectors through a randomly initialized ReLU neural network with five neurons. For both networks that we train we initialize them with one hundred neurons. One of the networks is trained with a small amount of regularization and the other with no regularization. Both were trained with full batch gradient descent and a learning rate of 2e-1 for one million iterations.

For the regularized network, due to the equivalence between weight decay and (3), we directly regularize the VV norm of the network with a small regularization parameter of 5e-5. We employ the proximal gradient algorithm proposed in Yang et al. (2022) to speed up training. The results are in Figure 2. We see that the regularized network is not only sparser - in terms of the number of active neurons - but also exhibits strong neuron sharing. In contrast without any regularization, many of the neurons are not shared and only contribute to a single output.
Figure 2: We train a two output two-dimensional ReLU neural network of the form \(f(x)=\sum_{k=1}^{K}\mathbf{v}_{k}\sigma(\mathbf{w}_{k}^{T}\mathbf{x}+b_{k})\) both with and without weight decay. We plot the location of the active neurons contributing to each of the outputs of the network where the size of the point indicates the weight of the neuron. The figures in (a-b) show the neuron locations/weight for the network trained with weight decay whereas (c-d) shows the neuron locations/weight for the network trained without weight decay. We see that in the case of weight decay, we have fewer active neurons, and those neurons that remain are shared across both outputs.
### Multi-Task Lasso Experiments

We solve the multi-task lasso problem in Theorem 12 on randomly generated matrices \(\mathbf{\Phi}\) and \(\mathbf{\Psi}\) using CVXPy (Diamond and Boyd, 2016). Our experiments illustrate that while our bounds hold, the exact number of nonzero columns depends heavily on the data itself. In Figure (3) we show histograms for the distribution of non-zero columns over 100 randomly generated pairs of \(\mathbf{\Phi}\) and \(\mathbf{\Psi}\).

We perform a similar set of experiments in Figure (4) but alter the underlying rank of \(\mathbf{\Phi}\). This validates our bound showing that the sparsity of the solution can be much lower depending on the rank of \(\mathbf{\Phi}\). We again see that the distribution is highly dependent on the data and difficult to predict exactly. We note however that we never achieve our upper bound which may indicate that they can be further tightened.

To demonstrate that the sparsest solutions to the multi-task lasso problem in Theorem (12) depends heavily on the data matrices \(\mathbf{\Phi}\) and \(\mathbf{\Psi}\) we also ran a small-scale experiment

Figure 4: Distribution of the number of active columns for the solutions to the multi-task lasso problem on randomly generated matrices of varying sizes. In this case, we have that \(\mathbf{\Phi}\) is low rank while \(\mathbf{\Psi}\) remains at a rank of \(D\). The red lines indicate the bounds from Theorem 12

Figure 3: Distribution of the number of active columns for the solutions to the multi-task lasso problem on randomly generated matrices of varying sizes. In all these cases \(r_{\mathbf{\Phi}}=N\) and \(r_{\mathbf{\Psi}}=D\) so we expect \(N\leq\widehat{K}\leq ND\). The red lines indicate the bounds from Theorem 12. The wide gap suggests that our upper bound can be tightened.
similar to the one in 4.2. However, in these experiments, we exhaustively searched over all \(2^{K}\) sparsity patterns that the solution may have. We arrive at the same conclusion as we did in 4.2 observing that the sparsest solution can lie anywhere within our bound as shown in Figure (5).

### Experiments Compressing pre-trained DNNs

As a practical application of our theory we conduct experiments compressing real deep neural networks pre-trained on the CIFAR-10 dataset. We first consider a pre-trained VGG19 architecture trained with weight decay. This model consists of various convolutional and batch norm layers followed by a fully connected ReLU layer containing 512 neurons.

The output of this layer is \(\mathbf{\Psi}\in\mathbb{R}^{10\times N}\) due to having just 10 classes and therefore \(\operatorname{rank}(\mathbf{\Psi})\leq 10\). Moreover, we found that for the post-activation feature representation at this layer the first 10 singular values account for 99% of the energy of the signal (Figure 6), thus \(\operatorname{rank}(\mathbf{\Phi})\approx 10\). Therefore, our bounds suggest that there exists an alternative optimal representation that is exactly equivalent on the _training_ data, with no more than 100 neurons in this layer. We validate this by applying the multi-task lasso problem (30) on the last fully connected ReLU layer. The results in Table 1 show that we can compress the final ReLU layer down to just 47 neurons while preserving nearly the same loss on the training data and achieving the same generalization performance.

Next, we consider the AlexNet architecture which is also composed of multiple convolutional layers followed by three fully connected ReLU layers with 9216, 4096, and 4096 neurons. We apply our multi-task lasso optimization to compress each of these layers in a parallel fashion and report the training loss and test accuracy with the compressed layers replaced individually and all at once. The results are on Table 1. For all four cases, we notice almost no change in the training loss and even better accuracy on the test data in some cases. This is due to the fact that our constraint only enforces that the network remains the same on the training data, while it may behave differently on data it was not trained on. Finally, we highlight that in all these cases no retraining is required to achieve comparable performance.

Figure 5: Distribution of number of nonzero columns for the solutions to the multi-task lasso problem. We ran this experiment over 1000 randomly generated matrices \(\mathbf{\Phi}\) and \(\mathbf{\Psi}\). We see that the sparsest solution is dependent on the data and can vary between our bounds. The red lines indicate the bounds from Theorem 12
The minor discrepancies between the training losses of the original models and the compressed models are due to numerical issues when practically enforcing the constraint in in (28). In practice the constraint in (28) is approximated by formulating the solving the regularized version of the problem (35) and optimizing using proximal gradient descent. These results show us that our connection between weight decay and the multi-task lasso problem can hint at a principled approach to model compression that is also computationally efficient.

\[\min_{\{\mathbf{v}_{k}\}}\|\mathbf{V}\mathbf{\Phi}-\mathbf{\Psi}\|_{2}^{2}+ \lambda\sum_{k=1}^{K}\|\mathbf{v}_{k}\|_{2} \tag{35}\]

## 5 Related Works

In this section, we highlight some related works and discuss how our work fits into the current literature.

\begin{table}
\begin{tabular}{l l l l l} \hline Network Name & Original Width & New Width & Orig. Train Loss (Test Acc.) & New Training Loss (Test Acc.) \\ \hline VGG-19 (last layer) & 512 & 47 & 0.0104 (93.92\%) & 0.0112 (93.88\%) \\ AlexNet (last layer) & 4096 & 797 & 0.2203 (72.17\%) & 0.2213 (72.22\%) \\ AlexNet (penultimate layer) & 4096 & 677 & 0.2203 (72.17\%) & 0.2184 (72.48\%) \\ AlexNet (first linear layer) & 9216 & 4896 & 0.2203 (72.17\%) & 0.2325 (72.28\%) \\ \hline AlexNet (last 3 layers) & (4096,4096,9216) & (797,677,4896) & 0.2203 (72.17\%) & 0.2417(72.02\%) \\ \hline \end{tabular}
\end{table}
Table 1: Compressing Models Pre-trained on CIFAR-10

Figure 6: Cumulative plot of the singular values of the post-activation feature representations of the last layer of a pre-trained VGG19 on the entire CIFAR-10 dataset. We see that a large majority of the signal is captured by just the first few singular values, indicating that the representations are approximately low rank.
Variation Spaces and Representer Theorems for NNs.Understanding NNs by studying the variation space associated with taking their widths to infinity has been explored in the past (Kurkova and Sanguineti, 2001; Mhaskar, 2004; Bach, 2017). Representer theorems for showing that finite width networks are solutions to variational data-fitting problems posed over these spaces have also been developed (Parhi and Nowak, 2021, 2022; Unser, 2023; Bartolucci et al., 2023). However, most of these were restricted in that they only develop theories for shallow and scalar output NNs. Moreover, the norm associated with these variation spaces does not always coincide with regularizers used in practice such as weight decay. We are the first to study the \(\mathcal{V}(\mathbb{R}^{d};\mathbb{R}^{D})\)-space and develop a novel representer theorem for variational problems posed over such _vector-valued_ function spaces.

Weight Decay and Width.Numerous works have observed that weight decay is biased towards solutions with fewer neurons (Savarese et al., 2019; Ongie et al., 2020; Parhi and Nowak, 2021; Yang et al., 2022). Empirically, Yang et al. (2022) showed that training NNs with weight decay for many iterations induces sparsity on the neurons of the network. Moreover, Jacot et al. (2022); Parhi and Nowak (2021) provide bounds on the required width for a DNNs that solve the weight decay objective. Our bounds improve upon the ones presented in both of these works. Moreover, our setting is a more general one, instead of only considering homogeneous DNNs our theory holds for the homogeneous layers of _any_ DNN architecture. Recently, a line of work by Ergen and Pilanci (2021); Mishkin et al. (2022) has shown that training shallow ReLU NNs with weight decay can be recast as a convex program. Their reformulation reveals a sparse regularizer showing how weight decay induces solutions with few neurons. A similar observation was later extended to vector-valued neural networks in Sahiner et al. (2021).

Low-Rank Features.It has been observed that DNNs are biased toward learning low-rank features. This has been shown to be true in theory (Du et al., 2018; Le and Jegelka, 2022; Ji and Telgarsky, 2019) for scalar output linear and nonlinear NNs. Moreover, Radhakrishnan et al. (2021) extended the theory for vector-valued linear NNs. Empirical evidence has also shown that the internal representations of deep neural networks are low rank (Huh et al., 2023; Nar et al., 2019; Waleffe and Rekatsinas, 2022). (Huh et al., 2023; Nar et al., 2019). In particular, Waleffe and Rekatsinas (2022) observe that the effective dimensions of hidden post-activation feature embeddings of trained NNs are often much smaller than the actual layer width. The authors utilize this insight to reduce the number of parameters using principal component analysis during training. In contrast, our theory and experiments indicate that narrower networks can be found without complicated procedures during training by instead applying the multi-task lasso as in Section 3.1.

## 6 Conclusion and Future Work

In this work we proposed the VV function space which gives insight into the type of NNs solutions that weight decay encourages. Moreover, we proved a new representer theorem for this space showing that finite-width vector-valued NNs are solutions to the variational data-fitting problem over this space. We then developed a novel connection between training DNNs with weight decay and multi-task lasso to prove the sharpest known bounds on
network widths. Finally, we presented some experimental results showing the validity and potential utility of our theory.

The authors thank Ryan Tibshirani for helpful discussions regarding the lasso and related methods, especially the use of Caratheodory's theorem for characterizing the sparsity of solutions. JS was supported by the ONR MURI grant N00014-20-1-2787. RP was supported by the European Research Council (ERC Project FunLearn) under grant 101020573. KL was supported by the NSF grant DMS-2023239. RN was supported in part by the NSF grants DMS-2134140 and DMS-2023239, the ONR MURI grant N00014-20-1-2787, and the AFOSR/AFRL grant FA9550-18-1-0166, as well as the Keith and Jane Nosbusch Professorship.

## Appendix A Proof of Lemma 4

We prove the following result which corresponds to Lemma 4 by choosing \(\Omega=\mathbb{S}^{d}\).

**Lemma 15**: _Let \(\Omega\) be any locally compact Hausdorff space. The norms \(\left\|\cdot\right\|_{p,\mathcal{M}}\), \(p\geq 1\), and \(\left\|\cdot\right\|_{\mathcal{M},q}\), \(q\geq 1\) (appropriately defined on \(\mathcal{M}(\Omega;\mathbb{R}^{D})\)) are all equivalent Banach norms for \(\mathcal{M}(\Omega;\mathbb{R}^{D})\)._

We first observe that for any \(p,q\geq 1\), the norms \(\left\|\cdot\right\|_{\mathcal{M},p}\) and \(\left\|\cdot\right\|_{\mathcal{M},q}\) are equivalent by the equivalence of \(p\)-norms in finite dimensions. Similarly, for any \(p,q\geq 1\), the norms \(\left\|\cdot\right\|_{p,\mathcal{M}}\) and \(\left\|\cdot\right\|_{q,\mathcal{M}}\) are equivalent. Thus, it suffices to show that \(\left\|\cdot\right\|_{\mathcal{M},p}\) and \(\left\|\cdot\right\|_{q,\mathcal{M}}\) are equivalent for some \(p,q\geq 1\).

We have for any \(\boldsymbol{\nu}\in\mathcal{M}(\Omega;\mathbb{R}^{D})\)

\[\|\boldsymbol{\nu}\|_{\mathcal{M},1} =\sum_{j=1}^{D}\|\nu_{j}\|_{\mathcal{M}(\Omega)}\] \[=\sum_{j=1}^{D}\sup_{\Omega\stackrel{{\Omega\to \bigcup_{i=1}^{n}}}{{n\in\mathbb{N}}}}A_{i}\sum_{i=1}^{n}|\nu_{j}(A_{i})|\] \[\geq\sup_{\Omega\stackrel{{\Omega\to\bigcup_{i=1}^ {n}}}{{n\in\mathbb{N}}}}A_{i}\sum_{j=1}^{D}\sum_{i=1}^{n}|\nu_{j}(A_{i})|\] \[=\sup_{\Omega\stackrel{{\Omega\to\bigcup_{i=1}^{n} }}{{n\in\mathbb{N}}}}A_{i}\sum_{i=1}^{n}\sum_{j=1}^{D}|\nu_{j}(A_{i})|\] \[=\sup_{\Omega\stackrel{{\Omega\to\bigcup_{i=1}^{n} }}{{n\in\mathbb{N}}}}A_{i}\sum_{i=1}^{n}\|\boldsymbol{\nu}(A_{i})\|_{1}=\| \boldsymbol{\nu}\|_{1,\mathcal{M}}. \tag{36}\]

Since the inclusion/identity map

\[\iota:(\mathcal{M}(\Omega;\mathbb{R}^{D}),\left\|\cdot\right\|_{\mathcal{M}, 1})\rightarrow(\mathcal{M}(\Omega;\mathbb{R}^{D}),\left\|\cdot\right\|_{1, \mathcal{M}})\]
is obviously a bijection and satisfies the continuity bound (36), the bounded inverse theorem (Folland, 1999, Corollary 5.11) guarantees that the inverse \(\iota^{-1}\) is also bounded. In other words, there exists a constant \(C>0\) (which may depend on \(\Omega\) and \(D\)) such that for all \(\boldsymbol{\nu}\in\mathcal{M}(\Omega;\mathbb{R}^{D})\),

\[\|\boldsymbol{\nu}\|_{\mathcal{M},1}=\|\iota^{-1}\boldsymbol{\nu}\|_{ \mathcal{M},1}\leq C\|\boldsymbol{\nu}\|_{1,\mathcal{M}}.\]

Therefore, we have shown that \(\|\cdot\|_{\mathcal{M},1}\) and \(\|\cdot\|_{1,\mathcal{M}}\) are equivalent, which proves the lemma.

### Connection to the Total Variation of Function

The total variation of a measure is different than the total variation of a function, but the ideas are tightly linked. In the univariate case, consider a Radon measure \(\mu\in\mathcal{M}(\mathbb{R})\) and suppose there exists a function \(g_{\mu}:\mathbb{R}\to\mathbb{R}\) such that

\[\int_{\mathbb{R}}f(x)\,\mathrm{d}\mu(x)=\int_{\mathbb{R}}f(x)\, \mathrm{d}g_{\mu}(x),\]

where \(f\) is any bounded continuous function and the integral on the right-hand side is a Riemann-Stieltjes integral. If \(g_{\mu}\) is differentiable and its derivative, denoted by \(g_{\mu}^{\prime}\), is in \(L^{1}(\mathbb{R})\), then we have the equality

\[\|\mu\|_{\mathcal{M}(\mathbb{R})}=\|g_{\mu}^{\prime}\|_{L^{1}(\mathbb{R})}.\]

The quantity on the right-hand side is referred to as the _total variation_ of the function \(g_{\mu}\). Furthermore, if \(g_{\mu}\) is not differentiable in the classical sense, its distributional derivative can be identified with the Radon measure \(\mu\), i.e., \(g_{\mu}^{\prime}=\mu\), where equality is understood in \(\mathcal{M}(\mathbb{R})\). In this case, \(\|g_{\mu}^{\prime}\|_{\mathcal{M}(\mathbb{R})}=\|\mu\|_{\mathcal{M}(\mathbb{R})}\) is the total variation of the function \(g_{\mu}\).

This correspondence extends to higher dimensions. Indeed, given a function \(g:\mathbb{R}^{d}\to\mathbb{R}\), if its distributional gradient \(\nabla g\) can be identified with a vector-valued finite Radon measure, then the _isotropic total variation_ of \(g\) is

\[\mathrm{TV}_{\mathrm{iso}}(g)\coloneqq\|\nabla g\|_{2,\mathcal{M}},\]

while the _anisotropic total variation_ of \(g\) is

\[\mathrm{TV}_{\mathrm{aniso}}(g)\coloneqq\|\nabla g\|_{1,\mathcal{M}}.\]

These two notions of total variation in multiple dimensions are often used in image processing problems. Finally, the isotropic total variation is equivalently specified by

\[\mathrm{TV}_{\mathrm{iso}}(g)=\sup_{\begin{subarray}{c}\varphi\in\mathcal{D} (\mathbb{R}^{d};\mathbb{R}^{d})\\ \|\varphi\|_{L^{\infty}(\mathbb{R}^{d};\mathbb{R}^{d})}=1\end{subarray}}\int_ {\mathbb{R}^{d}}g(\boldsymbol{x})\,\mathrm{div}\varphi(\boldsymbol{x})\, \mathrm{d}\boldsymbol{x},\]

where the \(L^{\infty}(\mathbb{R}^{d};\mathbb{R}^{d})\)-norm is specified by

\[\|\varphi\|_{L^{\infty}(\mathbb{R}^{d};\mathbb{R}^{d})}\coloneqq\operatorname {ess\,sup}_{\boldsymbol{x}\in\mathbb{R}^{d}}\|\varphi(\boldsymbol{x})\|_{2},\]

and \(\mathcal{D}(\mathbb{R}^{d};\mathbb{R}^{d})\) denotes the space of infinitely differentiable compactly supported functions mapping \(\mathbb{R}^{d}\to\mathbb{R}^{d}\). We refer the reader to the book of Evans and Gariepy (2015) for more details about the total variation of a function.
## Appendix B Proof of Theorem 5

Proof.: From the definition of the \(\mathcal{V}(\mathbb{R}^{d};\mathbb{R}^{D})\)-norm (15), it follows from a standard argument (cf., Bartolucci et al., 2023, Proposition 3.7) that the problem in (18) is equivalent to the problem

\[\inf_{\boldsymbol{\nu}\in\mathcal{M}(\mathbb{S}^{d};\mathbb{R}^{D})}\,\sum_{i=1 }^{N}\mathcal{L}\bigg{(}\boldsymbol{y}_{i},\int_{\mathbb{S}^{d}}\sigma( \boldsymbol{w}^{T}\overline{\boldsymbol{x}}_{i})\,\mathrm{d}\boldsymbol{\nu} (\boldsymbol{w})\bigg{)}+\lambda\|\boldsymbol{\nu}\|_{2,\mathcal{M}} \tag{37}\]

in the sense that their infimal values are the same and if \(\boldsymbol{\nu}^{\star}\) is a solution to (37), then

\[f_{\boldsymbol{\nu}^{\star}}(\boldsymbol{x})=\int_{\mathbb{S}^{d}}\sigma( \boldsymbol{w}^{T}\overline{\boldsymbol{x}}_{i})\,\mathrm{d}\boldsymbol{\nu} ^{\star}(\boldsymbol{w})\]

is a solution to (18). We now proceed in four steps to prove the theorem.

Step (i): Existence of solutions to (37).Define

\[\mathcal{J}(\boldsymbol{\nu})\coloneqq\sum_{i=1}^{N}\mathcal{L}\bigg{(} \boldsymbol{y}_{i},\int_{\mathbb{S}^{d}}\sigma(\boldsymbol{w}^{T}\overline{ \boldsymbol{x}}_{i})\,\mathrm{d}\boldsymbol{\nu}(\boldsymbol{w})\bigg{)}+ \lambda\|\boldsymbol{\nu}\|_{2,\mathcal{M}}\]

Given an arbitrary \(\boldsymbol{\nu}_{0}\in\mathcal{M}(\mathbb{S}^{d};\mathbb{R}^{D})\), let \(C_{0}\coloneqq\mathcal{J}(\boldsymbol{\nu}_{0})\). Then, we can transform (37) into the constrained problem

\[\inf_{\boldsymbol{\nu}\in\mathcal{M}(\mathbb{S}^{d};\mathbb{R}^{D})}\, \mathcal{J}(\boldsymbol{\nu})\quad\text{s.t.}\quad\|\boldsymbol{\nu}\|_{2, \mathcal{M}}\leq C_{0}/\lambda. \tag{38}\]

This transformation is valid since any measure that does not satisfy the constraint will have an objective value strictly larger than \(\boldsymbol{\nu}_{0}\) and therefore will not be in the solution set. Next, we note that we can write

\[\mathcal{J}(\boldsymbol{\nu})=\sum_{i=1}^{N}\mathcal{L}(\boldsymbol{y}_{i}, \mathrm{H}_{i}\{\boldsymbol{\nu}\})+\lambda\|\boldsymbol{\nu}\|_{2,\mathcal{M}}\]

where

\[\mathrm{H}_{i}\{\boldsymbol{\nu}\}\coloneqq\begin{bmatrix}\langle \boldsymbol{\nu},h_{i,j}\rangle\\ \vdots\\ \langle\boldsymbol{\nu},h_{i,D}\rangle\end{bmatrix}\in\mathbb{R}^{D} \tag{39}\]

with \(h_{i,j}(\boldsymbol{w})\coloneqq\sigma(\boldsymbol{w}^{T}\overline{ \boldsymbol{x}}_{i})\boldsymbol{e}_{j}\), where \(\boldsymbol{e}_{j}\in\mathbb{R}^{D}\) is the \(j\)th canonical unit vector. Clearly \(h_{i,j}\in C(\mathbb{S}^{d};\mathbb{R}^{D})\), the space of continuous functions on \(\mathbb{S}^{d}\) taking values in \(\mathbb{R}^{D}\). In (39), \(\langle\,\cdot,\,\cdot\,\rangle\) denotes the duality pairing5 between \(C(\mathbb{S}^{d};\mathbb{R}^{D})\) and \(\mathcal{M}(\mathbb{S}^{d};\mathbb{R}^{D})\). Thus, for \(i=1,\ldots,N\), \(\mathrm{H}_{i}\) is component-wise weak\({}^{*}\) continuous on \(\mathcal{M}(\mathbb{S}^{d};\mathbb{R}^{D})\). Since \(\mathcal{L}(\cdot\,,\,\cdot)\) is lower semicontinuous in its second argument combined with the fact that every norm is weak\({}^{*}\) continuous on its corresponding Banach space, we have that \(\mathcal{J}\) is weak\({}^{*}\) continuous on \(\mathcal{M}(\mathbb{S}^{d};\mathbb{R}^{D})\). By the Banach-Alaoglu theorem (Rudin, 1991, Chapter 3), the constraint set of (38) is weak\({}^{*}\) compact. Thus, (38) is the minimization of a weak\({}^{*}\) continuous functional over a weak\({}^{*}\) compact set. By the Weierstrass extreme value theorem on general topological spaces (Kurdila and Zabarankin, 2006, Chapter 5), there exists a solution to (38) (and subsequently of (37)).
Step (ii): Recasting (37) as an interpolation problem.Let \(\widetilde{\mathbf{\nu}}\) be a (not neccesarily unique) solution to (37), which is guaranteed to exist by the previous argumentation. For \(i=1,\ldots,D\), define

\[\mathbf{z}_{i}=\mathrm{H}_{i}\{\widetilde{\mathbf{\nu}}\}\in\mathbb{R}^{D}.\]

Then, \(\widetilde{\mathbf{\nu}}\) must satisfy

\[\widetilde{\mathbf{\nu}}\in\operatorname*{arg\,min}_{\mathbf{\nu}\in\mathcal{M}( \mathbb{S}^{d};\mathbb{R}^{D})}\|\mathbf{\nu}\|_{2,\mathcal{M}}\quad\text{s.t.} \quad\mathrm{H}_{i}\{\mathbf{\nu}\}=\mathbf{z}_{i},\,i=1,\ldots,N. \tag{40}\]

To see this, we note that if this were not the case, it would contradict the optimality of \(\widetilde{\mathbf{\nu}}\). This reduction implies that any solution to the interpolation problem (40) will also be a solution to (37).

Step (iii): The form of the solution.We can rewrite the interpolation problem as

\[\min_{\mathbf{\nu}\in\mathcal{M}(\mathbb{S}^{d};\mathbb{R}^{D})}\|\mathbf{\nu}\|_{2, \mathcal{M}}\quad\text{s.t.}\quad\langle\mathbf{\nu},h_{i,j}\rangle=\mathbf{z}_{i,j}, \,i=1,\ldots,N\text{ and }j=1,\ldots,D. \tag{41}\]

This is the vector-valued analogue of the classical (Radon) measure recovery problem with \(ND\) weak\({}^{*}\) continuous measurements. By the abstract representer theorem of Unser (2021, Theorems 2 and 3) (see also Boyer et al., 2019; Bredies and Carioni, 2020), there always exists a solution to (41) that takes the form

\[\mathbf{\nu}^{\star}=\sum_{k=1}^{K}c_{k}\mathbf{e}_{k}\]

with \(K\leq ND\), \(c_{k}\in\mathbb{R}\setminus\{0\}\) where for \(k=1,\ldots,k\), \(\mathbf{e}_{k}\) is an extreme point of the unit regularization ball

\[B\coloneqq\{\mathbf{\nu}\in\mathcal{M}(\mathbb{S}^{d};\mathbb{R}^{D}):\;\|\mathbf{\nu }\|_{2,\mathcal{M}}\leq 1\}.\]

From Werner (1984, Theorem 2), the extreme points of \(B\) take the form \(\mathbf{a}\delta_{\mathbf{w}}\) with \(\mathbf{a}\in\mathbb{R}^{D}\), \(\|\mathbf{a}\|_{2}=1\), and \(\mathbf{w}\in\mathbb{S}^{d}\). Thus, we can write

\[\mathbf{\nu}^{\star}=\sum_{k=1}^{K}c_{k}\mathbf{a}_{k}\delta_{\mathbf{w}_{k}}\]

with \(\mathbf{a}_{k}\in\mathbb{R}^{D}\) and \(\mathbf{w}_{k}\in\mathbb{S}^{d}\). By the equivalence between (37) and (18), we find that there exists a solution to (18) that takes the form

\[\widehat{f}(\mathbf{x})=\sum_{k=1}^{\widehat{K}}\widehat{\mathbf{v}}_{k}\sigma( \widehat{\mathbf{w}}_{k}^{T}\overline{\mathbf{x}}),\quad\mathbf{x}\in\mathbb{R}^{d},\]

where \(\widehat{K}\leq ND\), \(\widehat{\mathbf{v}}_{k}\coloneqq c_{k}\mathbf{a}_{k}\in\mathbb{R}^{D}\) and \(\widehat{\mathbf{w}}_{k}\in\mathbb{S}^{d}\).
Step (iv): Sharpening the sparsity bound.Step (iii) establishes that there exists an optimal solution with \(\widehat{K}\leq ND\) neurons. Thus, we can apply Theorem 3.2 to find another solution where the number of neurons is bounded by the product of the rank of the labels \(\mathbf{Y}\in\mathbb{R}^{D\times N}\) with the rank of the post-activation feature matrix \(\mathbf{\Phi}\in\mathbb{R}^{\widehat{K}\times N}\). From the dimensions of these matrices, we see that the product of the ranks is \(\leq N^{2}\). Thus, by Theorem 3.2, there exists a solution to (18) that takes the form

\[f^{\star}(\mathbf{x})=\sum_{k=1}^{K_{0}}\mathbf{v}_{k}\sigma(\mathbf{w}_{k}^{T}\overline{ \mathbf{x}}),\quad\mathbf{x}\in\mathbb{R}^{d},\]

where \(K_{0}\leq N^{2}\), \(\mathbf{v}_{k}\in\mathbb{R}^{D}\) and \(\mathbf{w}_{k}\in\mathbb{S}^{d}\). Thus, we can always find a solution to (18) with \(\min\{N^{2},ND\}\) neurons. \(\blacksquare\)
