# Universal approximation and model compression for radial neural networks

Iordan Ganev
Radboud University
Nijmegen, Netherlands
<EMAIL_ADDRESS>
&Twan van Laarhoven
Radboud University
Nijmegen, Netherlands
<EMAIL_ADDRESS>
&Robin Walters
Northeastern University
Boston, MA, USA
<EMAIL_ADDRESS>
###### Abstract

We introduce a class of fully-connected neural networks whose activation
functions, rather than being pointwise, rescale feature vectors by a function
depending only on their norm. We call such networks radial neural networks,
extending previous work on rotation equivariant networks that considers
rescaling activations in less generality. We prove universal approximation
theorems for radial neural networks, including in the more difficult cases of
bounded widths and unbounded domains. Our proof techniques are novel, distinct
from those in the pointwise case. Additionally, radial neural networks exhibit
a rich group of orthogonal change-of-basis symmetries on the vector space of
trainable parameters. Factoring out these symmetries leads to a practical
lossless model compression algorithm. Optimization of the compressed model by
gradient descent is equivalent to projected gradient descent for the full
model.

##  1 Introduction

Inspired by biological neural networks, the theory of artificial neural
networks has largely focused on pointwise (or “local”) nonlinear layers
(Rosenblatt, 1958; Cybenko, 1989), in which the same function
$\sigma\colon\mathbb{R}\to\mathbb{R}$ is applied to each coordinate
independently:

$\mathbb{R}^{n}\to\mathbb{R}^{n},\qquad v=(v_{1}\ ,\ \dots\ ,\ v_{n})\
\mapsto\ (\sigma(v_{1})\ ,\ \sigma(v_{2})\ ,\ \dots\ ,\ \sigma(v_{n})).$ (1.1)

In networks with pointwise nonlinearities, the standard basis vectors in
$\mathbb{R}^{n}$ can be interpreted as “neurons” and the nonlinearity as a
“neuron activation.” Research has generally focused on finding functions
$\sigma$ which lead to more stable training, have less sensitivity to
initialization, or are better adapted to certain applications (Ramachandran et
al., 2017; Misra, 2019; Milletarí et al., 2018; Clevert et al., 2015;
Klambauer et al., 2017). Many $\sigma$ have been considered, including
sigmoid, ReLU, arctangent, ELU, Swish, and others.

However, by setting aside the biological metaphor, it is possible to consider
a much broader class of nonlinearities, which are not necessarily pointwise,
but instead depend simultaneously on many coordinates. Neural networks using
such nonlinearities may yield expressive function classes with different
advantages. One example is radial basis networks (Broomhead and Lowe, 1988),
which contain nonlinearities of the form $\|v-c\|$, which depend on all
coordinates of $v$. However, each coordinate output is still independent.

In this paper, we introduce _radial_ neural networks which employ non-
pointwise nonlinearities called _radial rescaling_ activations. Freedom from
the pointwise assumption allows us to design activation functions that
maximize symmetry in the parameter space of the neural network. Such networks
enjoy several provable properties including high model compressibility,
symmetry in optimization, and universal approximation. These activations are
defined by rescaling each vector by a scalar that depends only on the norm of
the vector:

$\rho:\mathbb{R}^{n}\to\mathbb{R}^{n},\qquad v\ \mapsto\ \lambda(|v|)v,$ (1.2)

where $\lambda$ is a scalar-valued function of the norm. Whereas in the
pointwise setting, only the linear layers mix information between different
components of the latent features, for radial rescaling, all coordinates of
the activation output vector are affected by all coordinates of the activation
input vector. The inherent geometric symmetry of radial rescalings makes them
particularly useful for designing equivariant neural networks (Weiler and
Cesa, 2019; Sabour et al., 2017; Weiler et al., 2018a, b).

Figure 1: (Left) Pointwise activations distinguish a specific basis of each
hidden layer and treat each coordinate independently, see equation 1.1.
(Right) Radial rescaling activations rescale each feature vector by a function
of the norm, see equation 1.2.

In our first set of main results, we prove that radial neural networks are in
fact universal approximators. Specifically, we demonstrate that any
asymptotically affine function can be approximated with a radial neural
network, suggesting potentially good extrapolation behavior. Moreover, this
approximation can be done with bounded width. Our approach to proving these
results differs significantly from standard techniques used in the case of
pointwise activations due to the fact that coordinates cannot be treated
independently when dealing with non-pointwise activations.

In our second set of main results, we exploit parameter space symmetries of
radial neural networks to achieve model compression. Using the fact that
radial rescaling activations commute with orthogonal transformations, we
develop a practical algorithm to systematically factor out orthogonal
symmetries via iterated QR decompositions. This leads to another radial neural
network with fewer neurons in each hidden layer. The resulting model
compression algorithm is lossless: the compressed network and the original
network both have the same value of the loss function on any batch of training
data.

Furthermore, we prove that the loss of the compressed model after one step of
gradient descent is equal to the loss of the original model after one step of
_projected gradient descent_. As explained below, projected gradient descent
involves zeroing out certain parameter values after each step of gradient
descent. Although training the original network may result in a lower loss
function after fewer epochs, in many cases the compressed network takes less
time per epoch to train and is faster in reaching a local minimum.

To summarize, our main contributions are:

  * •

A formalization of radial neural networks, a new class of neural networks;

  * •

Two universal approximations results for radial neural networks: a)
approximation of asymptotically affine functions, and b) bounded width
approximation;

  * •

An implementation of a lossless model compression algorithm for radial neural
networks;

  * •

A theorem providing the precise relationship between gradient descent
optimization of the original and compressed networks.

##  2 Related work

Radial rescaling activations. Radial rescaling functions have the symmetry
property of preserving vector directions, and hence exhibit rotation
equivariance. Consequently, examples of such functions, such as the squashing
nonlinearity and Norm-ReLU, feature in the study of rotationally equivariant
neural networks (Weiler and Cesa, 2019; Sabour et al., 2017; Weiler et al.,
2018a, b; Jeffreys and Lau, 2021). However, previous works apply the
activation only along the channel dimension, and consider the orthogonal group
$O(n)$ only for $n=2,3$. In contrast, we consider a radial rescaling
activation across the entire hidden layer, and $O(n)$-equivariance where $n$
is the hidden layer dimension. Our constructions echo the vector neurons
formalism (Deng et al., 2021), in which the output of a nonlinearity is a
vector rather than a scalar. For radial basis networks, each hidden neuron is
a radial nonlinear function of the shifted input vector, but the outputs are
independent, whereas for radial rescaling functions, the outputs are also tied
together (Broomhead and Lowe, 1988).

Universal approximation. Neural networks of arbitrary width and sigmoid
activations have long been known to be universal approximators (Cybenko,
1989). Universal approximation can also be achieved by bounded width networks
with arbitrary depth (Lu et al., 2017b). Additional work has generalized to
other activation functions and neural architectures (Hornik, 1991; Yarotsky,
2022; Ravanbakhsh, 2020; Sonoda and Murata, 2017). While most work has focused
on compact domains, some recent work also considers non-compact domains
(Kidger and Lyons, 2020; Wang and Qu, 2022). The techniques used for pointwise
activation functions generalize to radial basis networks since the outputs of
each RBF are independent (Park and Sandberg, 1991), but do not easily
generalize to the radial rescaling activations considered here, because all
coordinates of the activation output vector are affected by all coordinates of
the activation input vector. As a consequence, individual radial neural
network approximators of two different functions cannot be easily combined to
give an approximator of the sum of the functions.

Groups and symmetry. Appearances of symmetry in machine learning have
generally focused on symmetric input and output spaces. Most prominently,
equivariant neural networks incorporate symmetry as an inductive bias and
feature weight-sharing constraints based on equivariance with respect to
various symmetry groups. Examples of equivariant architectures include
$G$-convolution, steerable CNN, and Clebsch-Gordon networks (Cohen et al.,
2019; Weiler and Cesa, 2019; Cohen and Welling, 2016; Chidester et al., 2018;
Kondor and Trivedi, 2018; Bao and Song, 2019; Worrall et al., 2017; Cohen and
Welling, 2017; Weiler et al., 2018b; Dieleman et al., 2016; Lang and Weiler,
2021; Ravanbakhsh et al., 2017). By contrast, our approach to radial neural
networks does not depend on symmetries of the input domain, output space, or
feedforward mapping. Instead, we exploit parameter space symmetries and thus
obtain more general results that apply to domains with no apparent symmetry.
As such, our use of the orthogonal invariance of radial neural networks is
parallel to the he “non-negative homogeneity” (or “positive scaling
invariance”) of the pointwise ReLU activation function (Armenta et al., 2021;
Dinh et al., 2017; Meng et al., 2019; Neyshabur et al., 2015).

Model compression. A major goal in machine learning is to find methods to
reduce the number of trainable parameters, decrease memory usage, or
accelerate inference and training (Cheng et al., 2017; Zhang et al., 2018).
Our approach toward this goal differs significantly from most existing methods
in that it is based on the inherent symmetry of network parameter spaces. One
prior method is _weight pruning_ , which removes redundant or small weights
from a network with little loss in accuracy (Han et al., 2015; Blalock et al.,
2020; Karnin, 1990). Pruning can be done during training (Frankle and Carbin,
2018) or at initialization (Lee et al., 2019; Wang et al., 2020). _Gradient-
based pruning_ identifies low saliency weights by estimating the increase in
loss resulting from their removal (LeCun et al., 1990; Hassibi and Stork,
1993; Dong et al., 2017; Molchanov et al., 2016). A complementary approach is
_quantization_ , which decreases the bit depth of weights (Wu et al., 2016;
Howard et al., 2017; Gong et al., 2014). Knowledge distillation identifies a
small model mimicking the performance of a larger model or ensemble of models
(Buciluǎ et al., 2006; Hinton et al., 2015; Ba and Caruana, 2013). Matrix
Factorization methods replace fully connected layers with lower rank or sparse
factored tensors (Cheng et al., 2015a, b; Tai et al., 2015; Lebedev et al.,
2014; Rigamonti et al., 2013; Lu et al., 2017a) and can often be applied
before training. Our method involves a type of matrix factorization based on
the QR decomposition; however, rather than aim for a rank reduction of linear
layers, we leverage this decomposition to reduce hidden widths via change-of-
basis operations on the hidden representations. Close to our method are
lossless compression methods which remove stable neurons in ReLU networks
(Serra et al., 2021, 2020) or exploit permutation parameter space symmetry to
remove redundant neurons (Sourek et al., 2020); our compression instead
follows from the symmetries of the radial rescaling activation. Finally, the
model compression results of (Jeffreys and Lau, 2021), while conceptually
similar to ours, are weaker, as (1) the unitary group action is on disjoint
layers instead of iteratively moving through all layers, and (2) the results
are only stated for a version of the squashing nonlinearity.

##  3 Radial neural networks

In this section, we define radial rescaling functions and radial neural
networks. Let $h:\mathbb{R}\to\mathbb{R}$ be a function. For any $n\geq 1$,
set:

$h^{(n)}:\mathbb{R}^{n}\to\mathbb{R}^{n}\qquad\qquad h^{(n)}(v)=h(\lvert
v\rvert)\frac{v}{|v|}$

for $v\neq 0$, and $h^{(n)}(0)=0$. A function
$\rho:\mathbb{R}^{n}\to\mathbb{R}^{n}$ is called a radial rescaling function
if $\rho=h^{(n)}$ for some piecewise differentiable
$h:\mathbb{R}\to\mathbb{R}$. Hence, $\rho$ sends each input vector to a scalar
multiple of itself, and that scalar depends only on the norm of the vector111A
function $\mathbb{R}^{n}\to\mathbb{R}$ that depends only on the norm of a
vector is known as a radial function. Radial rescaling functions rescale each
vector according to the radial function
$v\mapsto\lambda(|v|)=\frac{h(|v|)}{|v|}$. This explains the connection to
Equation 1.2.. It is easy to show that radial rescaling functions commute with
orthogonal transformations.

######  Example 1.

(1) Step-ReLU, where $h(r)=r$ if $r\geq 1$ and $0$ otherwise. In this case,
the radial rescaling function is given by

$\displaystyle\rho:\mathbb{R}^{n}$
$\displaystyle\rightarrow\mathbb{R}^{n},\qquad v\mapsto\begin{cases}v\
\text{\rm if $|v|\geq 1$}\\\ 0\ \text{\rm if $|v|<1$}\end{cases}$ (3.1)

(2) The squashing function, where $h(r)=r^{2}/(r^{2}+1)$. (3) Shifted ReLU,
where $h(r)=\max(0,r-b)$ for $r>0$ and $b$ is a real number. See Figure 2. We
refer to (Weiler and Cesa, 2019) and the references therein for more examples
and discussion of radial functions.

$-2$$-1.5$$-1$$-0.5$$0.5$$1$$1.5$$2$$-2$$-1.5$$-1$$-0.5$$0.5$$1$$1.5$$2$(1)
$\text{Step-ReLU}(r)$(3) Shifted ReLU(2) Squashing function Figure 2: Examples
of different radial rescaling functions in $\mathbb{R}^{1}$, see 1.

A radial neural network with $L$ layers consists of a positive integer $n_{i}$
indicating the width of each layer $i=0,1,\dots,L$; the trainable parameters,
comprising of a matrix $W_{i}\in\mathbb{R}^{n_{i}\times n_{i-1}}$ of weights
and a bias vector $b_{i}\in\mathbb{R}^{n_{i}}$ for each $i=1,\dots,L$; and a
radial rescaling function $\rho_{i}:\mathbb{R}^{n_{i}}\to\mathbb{R}^{n_{i}}$
for each $i=1,\dots,L$. We refer to the tuple
$\mathbf{n}=(n_{0},n_{1},\dots,n_{L})$ as the widths vector of the neural
network. The hidden widths vector is $\mathbf{n}^{\text{\rm
hid}}=(n_{1},n_{2},\dots,n_{L-1})$. The feedforward function
$F:\mathbb{R}^{n_{0}}\to\mathbb{R}^{n_{L}}$ of a radial neural network is
defined in the usual way as an iterated composition of affine maps and
activations. Explicitly, set $F_{0}=\text{\rm id}_{\mathbb{R}^{n_{0}}}$ and
recursively define the partial feedforward functions:

$F_{i}:\mathbb{R}^{n_{0}}\to\mathbb{R}^{n_{i}},\qquad
x\mapsto\rho_{i}\left(W_{i}\circ F_{i-1}(x)+b_{i}\right)$

for $i=1,\dots,L$. Then the feedforward function is $F=F_{L}$.

######  Remark 2.

If $b_{i}=0$ for all $i$, then the feedforward function takes the form
$F(x)=W\left(\mu(x)x\right)$ where $\mu:\mathbb{R}^{n}\to\mathbb{R}$ is a
scalar-valued function and $W=W_{L}W_{L-1}\cdots
W_{1}\in\mathbb{R}^{n_{L}\times n_{0}}$ is the product of the weight matrices.
If any of the biases are non-zero, then the feedforward function lacks such a
simple form.

##  4 Universal Approximation

In this section, we consider two universal approximation results. The first
approximates asymptotically affine functions with a network of unbounded
width. The second generalizes to bounded width networks. Proofs appear in
Appendix B. Throughout, $B_{r}(c)=\\{x\in\mathbb{R}^{n}:|x-c|<r\\}$ denotes
the $r$-ball around a point $c$, and an affine map
$\mathbb{R}^{n}\to\mathbb{R}^{m}$ is one of the from $L(x)=Ax+b$ for a matrix
$A\in\mathbb{R}^{m\times n}$ and $b\in\mathbb{R}^{m}$.

###  4.1 Approximation of asymptotically affine functions

A continuous function $f:\mathbb{R}^{n}\to\mathbb{R}^{m}$ is said to be
asymptotically affine if there exists an affine map
$L:\mathbb{R}^{n}\to\mathbb{R}^{m}$ such that, for every $\epsilon>0$, there
is a compact subset $K$ of $\mathbb{R}^{n}$ such that $|L(x)-f(x)|<\epsilon$
for all $x\in\mathbb{R}^{n}\setminus K$. In particular, continuous functions
with compact support are asymptotically affine. The continuity of $f$ and
compactness of $K$ imply that, for any $\epsilon>0$, there exist
$c_{1},\dots,c_{N}\in K$ and $r_{1},\dots,r_{N}\in(0,1)$ such that, first, the
union of the balls $B_{r_{i}}(c_{i})$ covers $K$ and, second, for all $i$, we
have $f\left(B_{r_{i}}(c_{i})\cap K\right)\subseteq B_{\epsilon}(f(c_{i}))$.
Let $N(f,K,\epsilon)$ be the minimal choice of $N$. In many cases, the
constant $N(f,K,\epsilon)$ can be bounded explicitly222For example, if $K$ is
the unit cube in $\mathbb{R}^{n}$ and $f$ is Lipschitz continuous with
Lipschitz constant $R$, then
$N(f,K,\epsilon)\leq\Bigl{\lceil}\frac{R\sqrt{n}}{2\epsilon}\Bigr{\rceil}^{n}$..

######  Theorem 3 (Universal approximation).

Let $f:\mathbb{R}^{n}\to\mathbb{R}^{m}$ be an asymptotically affine function.
For any $\epsilon>0$, there exists a compact set $K\subset\mathbb{R}^{n}$ and
a function $F:\mathbb{R}^{n}\to\mathbb{R}^{m}$ such that:

  1. 1.

$F$ is the feedforward function of a radial neural network with
$N=N(f,K,\epsilon)$ layers whose hidden widths are $(n+1,n+2,\dots,n+N)$.

  2. 2.

For any $x\in\mathbb{R}^{n}$, we have $|F(x)-f(x)|<\epsilon$.

We note that the approximation in Theorem 3 is valid on all of
$\mathbb{R}^{n}$. To give an idea of the proof, first fix
$c_{1},\dots,c_{N}\in K$ and $r_{1},\dots,r_{N}\in(0,1)$ as above. Let
$e_{1},\dots,e_{N}$ be orthonormal basis vectors extending $\mathbb{R}^{n}$ to
$\mathbb{R}^{n+N}$. For $i=1,\dots,N$ define the following affine maps:

$\displaystyle T_{i}:\mathbb{R}^{n+i-1}$
$\displaystyle\to\mathbb{R}^{n+i}\qquad$ $\displaystyle
S_{i}:\mathbb{R}^{n+i}$ $\displaystyle\to\mathbb{R}^{n+i}$ $\displaystyle z$
$\displaystyle\mapsto z-c_{i}+h_{i}e_{i}\qquad$ $\displaystyle z$
$\displaystyle\mapsto z-(1+h_{i}^{-1})\langle e_{i},z\rangle
e_{i}+c_{i}+e_{i}$

where $h_{i}=\sqrt{1-r_{i}^{2}}$ and $\langle e_{i},z\rangle$ is the
coefficient of $e_{i}$ in $z$. Setting $\rho_{i}$ to be Step-ReLU (Equation
3.1) on $\mathbb{R}^{n+i}$, these maps are chosen so that the composition
$S_{i}\circ\rho_{i}\circ T_{i}$ maps the points in $B_{r_{i}}(c_{i})$ to
$c_{i}+e_{i}$, while keeping points outside this ball the same. We now
describe a radial neural network with widths $(n,n+1,\dots,n+N,m)$ whose
feedforward function approximates $f$. For $i=1,\dots,N$ the affine map from
layer $i-1$ to layer $i$ is given by $z\mapsto T_{i}\circ S_{i-1}(z)$, with
$S_{0}=\text{\rm id}_{\mathbb{R}^{n}}$. The activation at each hidden layer is
Step-ReLU. Let $L$ be the affine map such that $|L-f|<\epsilon$ on
$\mathbb{R}^{n}\setminus K$. The affine map from layer $N$ to the output layer
is $\Phi\circ S_{N}$ where $\Phi:\mathbb{R}^{n+N}\to\mathbb{R}^{m}$ is the
unique affine map determined by $x\mapsto L(x)$ if $x\in\mathbb{R}^{n}$, and
$e_{i}\mapsto f(c_{i})-L(c_{i})$. This construction is illustrated in Figure
3.

$\mathbb{R}^{n}$$K$$c_{1}$$c_{2}$$c_{3}$$c_{4}$$c_{5}$$c_{6}$$c_{7}$$c_{8}$$c_{2}+e_{2}$$c_{2}$$S_{2}\circ\rho\circ
T_{2}$$\mathbb{R}^{m}$$f(c_{2})$$\Phi$ Figure 3:  Two layers of the radial
neural network used in the proof of Theorem 3. (Left) The compact set $K$ is
covered with open balls. (Middle) Points close to $c_{2}$ (green ball) are
mapped to $c_{2}+e_{2}$, all other points are kept the same. (Right) In the
final layer, $c_{2}+e_{2}$ is mapped to $f(c_{2})$.

###  4.2 Bounded width approximation

We now turn our attention to a bounded width universal approximation result.

######  Theorem 4.

Let $f:\mathbb{R}^{n}\to\mathbb{R}^{m}$ be an asymptotically affine function.
For any $\epsilon>0$, there exists a compact set $K\subset\mathbb{R}^{n}$ and
a function $F:\mathbb{R}^{n}\to\mathbb{R}^{m}$ such that:

  1. 1.

$F$ is the feedforward function of a radial neural network with
$N=N(f,K,\epsilon)$ hidden layers whose widths are all $n+m+1$.

  2. 2.

For any $x\in\mathbb{R}^{n}$, we have $|F(x)-f(x)|<\epsilon$.

The proof, which is more involved than that of Theorem 3, relies on using
orthogonal dimensions to represent the domain and the range of $f$, together
with an indicator dimension to distinguish the two. We regard points in
$\mathbb{R}^{n+m+1}$ as triples $(x,y,\theta)$ where $x\in\mathbb{R}^{n}$,
$y\in\mathbb{R}^{m}$ and $\theta\in\mathbb{R}$. The proof of Theorem 4
parallels that of Theorem 3, but instead of mapping points in
$B_{r_{i}}(c_{i})$ to $c_{i}+e_{i}$, we map the points in
$B_{r_{i}}((c_{i},0,0))$ to $(0,\frac{f(c_{i})-L(0)}{s},1)$, where $s$ is
chosen such that different balls do not interfere. The final layer then uses
an affine map $(x,y,\theta)\mapsto L(x)+sy$, which takes $(x,0,0)$ to $L(x)$,
and $(0,\frac{f(c_{i})-L(0)}{s},1)$ to $f(c_{i})$.

We remark on several additional results; see Appendix B for full statements
and proofs. The bound of Theorem 4 can be strengthend to $\max(n,m)+1$ in the
case of functions $f:K\to\mathbb{R}^{m}$ defined on a compact domain
$K\subset\mathbb{R}^{n}$ (i.e., ignoring asymptotic behavior). Furthermore,
with more layers, it is possible to reduce that bound to $\max(n,m)$.

##  5 Model compression

In this section, we prove a model compression result. Specifically, we provide
an algorithm which, given any radial neural network, computes a different
radial neural network with smaller widths. The resulting compressed network
has the same feedforward function as the original network, and hence the same
value of the loss function on any batch of training data. In other words, our
model compression procedure is lossless. Although our algorithm is practical
and explicit, it reflects more conceptual phenomena, namely, a change-of-basis
action on network parameter spaces (Section 5.1).

###  5.1 The parameter space

Suppose a fully connected network has $L$ layers and widths given by the tuple
$\mathbf{n}=(n_{0},n_{1},n_{2},\dots,n_{L-1},n_{L})$. In other words, the
$i$-th layer has input width $n_{i-1}$ and output width $n_{i}$. The parameter
space is defined as the vector space of all possible choices of parameter
values. Hence, it is given by the following product of vector spaces:

$\mathsf{Param}(\mathbf{n})=\left(\mathbb{R}^{n_{1}\times
n_{0}}\times\mathbb{R}^{n_{2}\times
n_{1}}\times\cdots\times\mathbb{R}^{n_{L}\times
n_{L-1}}\right)\times\left(\mathbb{R}^{n_{1}}\times\mathbb{R}^{n_{2}}\times\cdots\times\mathbb{R}^{n_{L}}\right)$

We denote an element therein as a pair of tuples $(\mathbf{W},\mathbf{b})$
where $\mathbf{W}=(W_{i}\in\mathbb{R}^{n_{i}\times n_{i-1}})_{i=1}^{L}$ are
the weights and $\mathbf{b}=(b_{i}\in\mathbb{R}^{n_{i}})_{i=1}^{L}$ are the
biases. To describe certain symmetries of the parameter space, consider the
following product of orthogonal groups, with sizes corresponding to the widths
of the hidden layers:

$O(\mathbf{n}^{\text{hid}})=O(n_{1})\times O(n_{2})\times\cdots\times
O(n_{L-1})$

There is a change-of-basis action of $O(\mathbf{n}^{\text{\rm hid}})$ on the
parameter space $\mathsf{Param}(\mathbf{n})$. Explicitly, the tuple of
orthogonal matrices $\mathbf{Q}=(Q_{i})_{i=1}^{L-1}\in O(\mathbf{n}^{\text{\rm
hid}})$ transforms the parameter values $(\mathbf{W},\mathbf{b})$ to
$\mathbf{Q}\cdot\mathbf{W}:=\left(Q_{i}W_{i}Q_{i-1}^{-1}\right)_{i=1}^{L}$ and
$\mathbf{Q}\cdot\mathbf{b}:=\left(Q_{i}b_{i}\right)_{i=1}^{L}$, where
$Q_{0}=\text{\rm id}_{n_{0}}$ and $Q_{L}=\text{\rm id}_{n_{L}}$. We write
$\mathbf{Q}\cdot(\mathbf{W},\mathbf{b})$ for
$(\mathbf{Q}\cdot\mathbf{W},\mathbf{Q}\cdot\mathbf{b})$.

###  5.2 Model compression

In order to state the compression result, we first define the reduced widths.
Namely, the reduction $\mathbf{n}^{\text{\rm red}}=(n^{\rm red}_{0},n^{\rm
red}_{1},\dots,n^{\rm red}_{L})$ of a widths vector $\mathbf{n}$ is defined
recursively by setting $n^{\rm red}_{0}=n_{0}$, then $n^{\rm
red}_{i}=\min(n_{i},n^{\rm red}_{i-1}+1)$ for $i=1,\dots,L-1$, and finally
$n^{\rm red}_{L}=n_{L}$. For a tuple
$\bm{\rho}=\left(\rho_{i}:\mathbb{R}^{n_{i}}\to\mathbb{R}^{n_{i}}\right)_{i=1}^{L}$
of radial rescaling functions, we write $\bm{\rho}^{\rm red}=\left(\rho^{\rm
red}_{i}:\mathbb{R}^{n^{\rm red}_{i}}\to\mathbb{R}^{n^{\rm red}_{i}}\right)$
for the corresponding tuple of restrictions, which are all radial rescaling
functions. The following result relies on Algorithm 1 below.

######  Theorem 5.

Let $(\mathbf{W},\mathbf{b},\bm{\rho})$ be a radial neural network with widths
$\mathbf{n}$. Let $\mathbf{W}^{\text{\rm red}}$ and $\mathbf{b}^{\text{\rm
red}}$ be the weights and biases of the compressed network produced by
Algorithm 1. The feedforward function of the original network
$(\mathbf{W},\mathbf{b},\bm{\rho})$ coincides with that of the compressed
network $(\mathbf{W}^{\text{\rm red}},\mathbf{b}^{\text{\rm
red}},\bm{\rho}^{\rm red})$.

input : $\mathbf{W},\mathbf{b}\in\mathsf{Param}(\mathbf{n})$

output : $\mathbf{Q}\in O(\mathbf{n}^{\text{\rm hid}})$ and
$\mathbf{W}^{\text{\rm red}},\mathbf{b}^{\text{\rm
red}}\in\mathsf{Param}(\mathbf{n}^{\text{\rm red}})$

$\mathbf{Q},\mathbf{W}^{\text{\rm red}},\mathbf{b}^{\text{\rm
red}}\leftarrow[\ ],[\ ],[\ ]$

// initialize output lists

$A_{1}\leftarrow\begin{bmatrix}b_{1}&W_{1}\end{bmatrix}$

// matrix of size $n_{1}\times(n_{0}+1)$

for  _$i\leftarrow 1$ to $L-1$ _ do

// iterate through layers

$Q_{i},R_{i}\leftarrow$ QR-decomp(_$A_{i}$ , mode = ‘complete’_)

// $A_{i}=Q_{i}\text{\rm Inc}_{i}R_{i}$

Append $Q_{i}$ to $\mathbf{Q}$

Append first column of $R_{i}$ to $\mathbf{b}^{\text{\rm red}}$

// reduced bias for layer $i$

Append remainder of $R_{i}$ to $\mathbf{W}^{\text{\rm red}}$

// reduced weights for layer $i$

Set $A_{i+1}\leftarrow\begin{bmatrix}b_{i+1}&W_{i+1}Q_{i}\text{\rm
Inc}_{i}\end{bmatrix}$

// matrix of size $n_{i+1}\times(n^{\rm red}_{i}+1)$

end for

Append the first column of $A_{L}$ to $\mathbf{b}^{\text{\rm red}}$

// reduced bias for last layer

Append the remainder of $A_{L}$ to $\mathbf{W}^{\text{\rm red}}$

// reduced weights for last layer

return $\mathbf{Q}$, $\mathbf{W}^{\text{\rm red}}$, $\mathbf{b}^{\text{\rm
red}}$

Algorithm 1 QR Model Compression (QR-compress)

We explain the notation of the algorithm. The inclusion matrix $\text{\rm
Inc}_{i}\in\mathbb{R}^{n_{i}\times n^{\rm red}_{i}}$ has ones along the main
diagonal and zeros elsewhere. The method QR-decomp with mode = ‘complete’
computes the complete QR decomposition of the $n_{i}\times(1+n^{\rm
red}_{i-1})$ matrix $A_{i}$ as $Q_{i}\text{\rm Inc}_{i}R_{i}$ where $Q_{i}\in
O(n_{i})$ and $R_{i}$ is upper-triangular of size $n^{\rm
red}_{i}\times(1+n^{\rm red}_{i-1})$. The definition of $n^{\rm red}_{i}$
implies that either $n^{\rm red}_{i}=n^{\rm red}_{i-1}+1$ or $n^{\rm
red}_{i}=n_{i}$. The matrix $R_{i}$ is of size $n^{\rm red}_{i}\times n^{\rm
red}_{i}$ in the former case and of size $n_{i}\times(1+n^{\rm red}_{i-1})$ in
the latter case.

$\displaystyle\mathbb{R}$$\displaystyle\mathbb{R}^{4}$$\displaystyle\mathbb{R}^{4}$$\displaystyle\mathbb{R}^{4}$$\displaystyle\mathbb{R}^{4}$$\displaystyle\mathbb{R}$$\begin{bmatrix}\bullet\\\
\bullet\\\ \bullet\\\ \bullet\end{bmatrix}$
$\rho$$\begin{bmatrix}\bullet&\bullet&\bullet&\bullet\\\
\bullet&\bullet&\bullet&\bullet\\\ \bullet&\bullet&\bullet&\bullet\\\
\bullet&\bullet&\bullet&\bullet\end{bmatrix}$
$\rho$$\begin{bmatrix}\bullet&\bullet&\bullet&\bullet\end{bmatrix}$

$\displaystyle\mathbb{R}$$\displaystyle\mathbb{R}^{2}$$\displaystyle\mathbb{R}^{2}$$\displaystyle\mathbb{R}^{4}$$\displaystyle\mathbb{R}^{4}$$\displaystyle\mathbb{R}$$\begin{bmatrix}\bullet\\\
\bullet\end{bmatrix}$ $\rho$$\begin{bmatrix}\bullet&\bullet\\\
\bullet&\bullet\\\ \bullet&\bullet\\\ \bullet&\bullet\end{bmatrix}$
$\rho$$\begin{bmatrix}\bullet&\bullet&\bullet&\bullet\end{bmatrix}$

$\displaystyle\mathbb{R}$$\displaystyle\mathbb{R}^{2}$$\displaystyle\mathbb{R}^{2}$$\displaystyle\mathbb{R}^{3}$$\displaystyle\mathbb{R}^{3}$$\displaystyle\mathbb{R}$$\begin{bmatrix}\bullet\\\
\bullet\end{bmatrix}$ $\rho$$\begin{bmatrix}\bullet&\bullet\\\
\bullet&\bullet\\\ \bullet&\bullet\end{bmatrix}$
$\rho$$\begin{bmatrix}\bullet&\bullet&\bullet\end{bmatrix}$

Figure 4: Model compression in 3 steps. Layer widths can be iteratively
reduced to 1 greater than the previous. The number of trainable parameters
reduces from 33 to 17.

######  Example 6.

Suppose the widths of a radial neural network are $(1,8,16,8,1)$. Then it has
$\sum_{i=1}^{4}(n_{i-1}+1)n_{i}=305$ trainable parameters. The reduced network
has widths $(1,2,3,4,1)$ and $\sum_{i=1}^{4}(n^{\rm red}_{i-1}+1)(n^{\rm
red}_{i})=34$ trainable parameters. Another example appears in Figure 4.

We note that the tuple of matrices $\mathbf{Q}$ produced by Algorithm 1 does
not feature in the statement of Theorem 5, but is important in the proof
(which appears in Appendix C). Namely, an induction argument shows that the
$i$-th partial feedforward function of the original and reduced models are
related via the matrices $Q_{i}$ and $\text{\rm Inc}_{i}$. A crucial
ingredient in the proof is that radial rescaling activations commute with
orthogonal transformations.

##  6 Projected gradient descent

The typical use case for model compression algorithms is to produce a smaller
version of the fully trained model which can be deployed to make inference
more efficient. It is also worth considering whether compression can be used
to accelerate training. For example, for some compression algorithms, the
compressed and full models have the same feedforward function after a step of
gradient descent is applied to each, and so one can compress before training
and still reach the same minimum. Unfortunately, in the context of radial
neural networks, compression using Algorithm 1 and then training does not
necessarily give the same result as training and then compression (see
Appendix D.6 for a counterexample). However, QR-compress does lead to a
precise mathematical relationship between optimization of the two models: the
loss of the compressed model after one step of gradient descent is equivalent
to the loss of (a transformed version of) the original model after one step of
projected gradient descent. Proofs appear in Appendix D.

To state our results, fix a tuple of widths $\mathbf{n}$ and a tuple
$\bm{\rho}=\left(\rho_{i}:\mathbb{R}^{n_{i}}\to\mathbb{R}^{n_{i}}\right)_{i=1}^{L}$
of radial rescaling functions. The loss function
$\mathcal{L}:\mathsf{Param}(\mathbf{n})\rightarrow\mathbb{R}$ associated to a
batch of training data
$\\{(x_{j},y_{j})\\}\subseteq\mathbb{R}^{n_{0}}\times\mathbb{R}^{n_{L}}$ is
defined as taking parameter values $(\mathbf{W},\mathbf{b})$ to the sum
$\sum_{j}\mathcal{C}(F(x_{j}),y_{j})$ where
$\mathcal{C}:\mathbb{R}^{n_{L}}\times\mathbb{R}^{n_{L}}\to\mathbb{R}$ is a
cost function on the output space, and
$F=F_{(\mathbf{W},\mathbf{b},\bm{\rho})}$ is the feedforward of the radial
neural network with parameters $(\mathbf{W},\mathbf{b})$ and activations
$\bm{\rho}$. Similarly, we have a loss function $\mathcal{L}_{\text{\rm red}}$
on the parameter space $\mathsf{Param}(\mathbf{n}^{\text{\rm red}})$ with
reduced widths vector. For any learning rate $\eta>0$, we obtain gradient
descent maps:

$\displaystyle\gamma:\mathsf{Param}(\mathbf{n})$
$\displaystyle\to\mathsf{Param}(\mathbf{n})\qquad$
$\displaystyle\gamma_{\text{\rm red}}:\mathsf{Param}(\mathbf{n}^{\text{\rm
red}})$ $\displaystyle\to\mathsf{Param}(\mathbf{n}^{\text{\rm red}})$
$\displaystyle(\mathbf{W},\mathbf{b})$
$\displaystyle\mapsto(\mathbf{W},\mathbf{b})-\eta\nabla_{(\mathbf{W},\mathbf{b})}\mathcal{L}\qquad$
$\displaystyle(\mathbf{V},\mathbf{c})$
$\displaystyle\mapsto(\mathbf{V},\mathbf{c})-\eta\nabla_{(\mathbf{V},\mathbf{c})}\mathcal{L}_{\text{\rm
red}}$

We will also consider, for $k\geq 0$, the $k$-fold composition
$\gamma^{k}=\gamma\circ\gamma\circ\cdots\circ\gamma$ and similarly for
$\gamma_{\text{\rm red}}$. The projected gradient descent map on
$\mathsf{Param}(\mathbf{n})$ is given by:

$\gamma_{\text{\rm
proj}}:\mathsf{Param}(\mathbf{n})\to\mathsf{Param}(\mathbf{n}),\qquad(\mathbf{W},\mathbf{b})\mapsto\mathrm{Proj}\left(\gamma(\mathbf{W},\mathbf{b})\right)$

where the map $\mathrm{Proj}$ zeroes out all entries in the bottom left
$(n_{i}-n^{\rm red}_{i})\times n^{\rm red}_{i-1}$ submatrix of
$W_{i}-\nabla_{W_{i}}\mathcal{L}$, and the bottom $(n_{i}-n^{\rm red}_{i})$
entries in $b_{i}-\nabla_{b_{i}}\mathcal{L}$, for each $i$. Schematically:

$\small{W_{i}}-\nabla_{W_{i}}\mathcal{L}=\begin{bmatrix}*&*\\\
*&*\end{bmatrix}\mapsto\begin{bmatrix}*&*\\\
0&*\end{bmatrix},\qquad{b_{i}}-\nabla_{b_{i}}\mathcal{L}=\begin{bmatrix}*\\\
*\end{bmatrix}\mapsto\begin{bmatrix}*\\\ 0\end{bmatrix}$

To state the following theorem, let $\mathbf{W}^{\text{\rm
red}},\mathbf{b}^{\text{\rm red}},\mathbf{Q}=\text{\tt{QR-
compress}}(\mathbf{W},\mathbf{b})$ be the outputs of Algorithm 1 applied to
$(\mathbf{W},\mathbf{b})\in\mathsf{Param}(\mathbf{n})$. Hence
$(\mathbf{W}^{\text{\rm red}},\mathbf{b}^{\text{\rm
red}})\in\mathsf{Param}(\mathbf{n}^{\text{\rm red}})$ are the parameters of
the compressed model, and $\mathbf{Q}\in O(\mathbf{n}^{\text{\rm hid}})$ is an
orthogonal parameter symmetry. We also consider the action (Section 5.1) of
$\mathbf{Q}^{-1}$ applied to $(\mathbf{W},\mathbf{b})$.

######  Theorem 7.

Let $\mathbf{W}^{\text{\rm red}},\mathbf{b}^{\text{\rm
red}},\mathbf{Q}=\text{\tt{QR-compress}}(\mathbf{W},\mathbf{b})$ be the
outputs of Algorithm 1 applied to
$(\mathbf{W},\mathbf{b})\in\mathsf{Param}(\mathbf{n})$. Set
$\mathbf{U}=\mathbf{Q}^{-1}\cdot\left(\mathbf{W},\mathbf{b}\right)-(\mathbf{W}^{\text{\rm
red}},\mathbf{b}^{\text{\rm red}})$. For any $k\geq 0$, we have:

$\gamma^{k}(\mathbf{W},\mathbf{b})=\mathbf{Q}\cdot\gamma^{k}(\mathbf{Q}^{-1}\cdot\left(\mathbf{W},\mathbf{b}\right))\qquad\qquad\gamma_{\text{\rm
proj}}^{k}(\mathbf{Q}^{-1}\cdot\left(\mathbf{W},\mathbf{b}\right))=\gamma_{\text{\rm
red}}^{k}(\mathbf{W}^{\text{\rm red}},\mathbf{b}^{\text{\rm
red}})+\mathbf{U}.$

We conclude that gradient descent with initial values
$(\mathbf{W},\mathbf{b})$ is equivalent to gradient descent with initial
values $\mathbf{Q}^{-1}\cdot\left(\mathbf{W},\mathbf{b}\right)$ since at any
stage we can apply the orthogonal symmetry $\mathbf{Q}^{\pm 1}$ to move from
one to the other. Furthermore, projected gradient descent with initial values
$\mathbf{Q}^{-1}\cdot\left(\mathbf{W},\mathbf{b}\right)$ is equivalent to
gradient descent on $\mathsf{Param}(\mathbf{n}^{\text{\rm red}})$ with initial
values $(\mathbf{W}^{\text{\rm red}},\mathbf{b}^{\text{\rm red}})$ since at
any stage we can move from one to the other by $\pm\mathbf{U}$.

##  7 Experiments

In addition to the theoretical results in this work, we provide an
implementation of Algorithm 1, in order to validate the claims of Theorems 5
and 7 empirically, as well as to quantify real-world performance. Full
experimental details are in Appendix E.

(1) Empirical verification of Theorem 5. We learn the function
$f(x)=e^{-x^{2}}$ from samples using a radial neural network with widths
$\mathbf{n}=(1,6,7,1)$ and activation the radial shifted sigmoid
$h(x)=1/(1+e^{-x+s})$. Applying QR-compress gives a compressed radial neural
network with widths $\mathbf{n}^{\mathrm{red}}=(1,2,3,1)$. Theorem 5 implies
that the respective neural functions $F$ and $F_{\text{\rm red}}$ are equal.
Over 10 random initializations, the mean absolute error is negligible up to
machine precision: $(1/N)\sum_{j}|F(x_{j})-F_{\text{\rm
red}}(x_{j})|=1.31\cdot 10^{-8}\pm 4.45\cdot 10^{-9}$.

(2) Empirical verification of Theorem 7. The claim is that training the
transformed model with parameters
$\mathbf{Q}^{-1}\cdot(\mathbf{W},\mathbf{b})$ and objective $\mathcal{L}$ by
projected gradient descent coincides with training the reduced model with
parameters $(\mathbf{W}^{\text{\rm red}},\mathbf{b}^{\text{\rm red}})$ and
objective $\mathcal{L}_{\mathrm{red}}$ by usual gradient descent. We verified
this on synthetic data as above. Over 10 random initializations, the loss
functions after training match:
$|\mathcal{L}-\mathcal{L}_{\mathrm{red}}|=4.02\cdot 10^{-9}\pm 7.01\cdot
10^{-9}$.

(3) The compressed model trains faster. Our compression method may be applied
before training to produce a smaller model class which _trains_ faster without
sacrificing accuracy. We demonstrate this in learning the function
$f:\mathbb{R}^{2}\to\mathbb{R}^{2}$ sending $(t_{1},t_{2})$ to
$(e^{-t_{1}^{2}},e^{-t_{2}^{2}})$ using a radial neural network with widths
$\mathbf{n}=(2,16,64,128,16,2)$ and activation the radial sigmoid
$h(r)=1/(1+e^{-r})$. Applying QR-compress gives a compressed network with
widths $\mathbf{n}^{\mathrm{red}}=(2,3,4,5,6,2)$. We trained both models until
the training loss was $\leq 0.01$. Over 10 random initializations on our
system, the reduced network trained in $15.32\pm 2.53$ seconds and the
original network trained in $31.24\pm 4.55$ seconds.

##  8 Conclusions and Discussion

This paper demonstrates that radial neural networks are universal
approximators and that their parameter spaces exhibit a rich symmetry group,
leading to a model compression algorithm. The results of this work combine to
build a theoretical foundation for the use of radial neural networks, and
suggest that radial neural networks hold promise for wider practical
applicability. Furthermore, this work makes an argument for considering the
advantages of non-pointwise nonlinearities in neural networks.

There are two main limitations of our results, each providing an opportunity
for future work. First, our universal approximation constructions currently
work only for Step-ReLU radial rescaling radial activations; it would be
desirable to generalize to other activations. Additionally, Theorem 5 achieves
compression only for networks whose widths satisfy $n_{i}>n_{i-1}+1$ for some
$i$. Neural networks which do not have increasing widths anywhere in their
architecture, such as encoders, would not be compressible.

Further extensions of this work include: First, little is currently known
about the stability properties of radial neural networks during training, as
well as their sensitivity to initialization. Second, radial rescaling
activations provide an extreme case of symmetry; there may be benefits to
combining radial and pointwise activations within a single network, for
example, through ‘block’ radial rescaling functions. Third, the parameter
space symmetries may provide a key ingredient in analyzing the gradient flow
dynamics of radial neural networks and computation of conserved quantities.
Fourth, radial rescaling activations can be used within convolutional or
group-equivariant NNs. Finally, based on the theoretical advantages laid out
in this paper, future work will explore empirically applications in which we
expect radial networks to outperform alternate methods. Such potential
applications include data spaces with circular or distance-based class
boundaries.

## Acknowledgements

We would like to thank Avraham Aizenbud, Marco Antonio Armenta, Alex Kolmus,
Niklas Smedemark-Margulies, Jan-Willem van de Meent, and Rose Yu for
insightful discussions, comments, and questions. This work was (partially)
funded by the NWO under the CORTEX project (NWA.1160.18.316) and NSF grant
#2134178. Robin Walters is supported by the Roux Institute and the Harold
Alfond Foundation.

## References

  * Armenta et al. [2021] Marco Armenta, Thierry Judge, Nathan Painchaud, Youssef Skandarani, Carl Lemaire, Gabriel Gibeau Sanchez, Philippe Spino, and Pierre-Marc Jodoin.  Neural Teleportation.  _arXiv:2012.01118 [cs]_ , August 2021.  URL http://arxiv.org/abs/2012.01118.  arXiv: 2012.01118.
  * Ba and Caruana [2013] Lei Jimmy Ba and Rich Caruana.  Do deep nets really need to be deep?  _arXiv:1312.6184_ , 2013.
  * Bao and Song [2019] Erkao Bao and Linqi Song.  Equivariant neural networks and equivarification.  _arXiv:1906.07172_ , 2019.
  * Blalock et al. [2020] Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag.  What is the state of neural network pruning?  _arXiv:2003.03033_ , 2020.
  * Broomhead and Lowe [1988] David S Broomhead and David Lowe.  Radial basis functions, multi-variable functional interpolation and adaptive networks.  Technical report, Royal Signals and Radar Establishment Malvern (United Kingdom), 1988.
  * Buciluǎ et al. [2006] Cristian Buciluǎ, Rich Caruana, and Alexandru Niculescu-Mizil.  Model compression.  In _Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , pages 535–541, 2006.
  * Cheng et al. [2015a] Yu Cheng, X Yu Felix, Rogerio S Feris, Sanjiv Kumar, Alok Choudhary, and Shih-Fu Chang.  Fast neural networks with circulant projections.  _arXiv:1502.03436_ , 2, 2015a.
  * Cheng et al. [2015b] Yu Cheng, Felix X Yu, Rogerio S Feris, Sanjiv Kumar, Alok Choudhary, and Shi-Fu Chang.  An exploration of parameter redundancy in deep networks with circulant projections.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2857–2865, 2015b.
  * Cheng et al. [2017] Yu Cheng, Duo Wang, Pan Zhou, and Tao Zhang.  A survey of model compression and acceleration for deep neural networks.  _arXiv:1710.09282_ , 2017.
  * Chidester et al. [2018] Benjamin Chidester, Minh N. Do, and Jian Ma.  Rotation equivariance and invariance in convolutional neural networks.  _arXiv:1805.12301_ , 2018.
  * Clevert et al. [2015] Djork-Arné Clevert, Thomas Unterthiner, and Sepp Hochreiter.  Fast and accurate deep network learning by exponential linear units (elus).  _arXiv preprint arXiv:1511.07289_ , 2015.
  * Cohen and Welling [2016] Taco S. Cohen and Max Welling.  Group equivariant convolutional networks.  In _International conference on machine learning (ICML)_ , pages 2990–2999, 2016.
  * Cohen and Welling [2017] Taco S Cohen and Max Welling.  Steerable CNNs.  In _Proceedings of the International Conference on Learning Representations (ICLR)_ , 2017.
  * Cohen et al. [2019] Taco S. Cohen, Maurice Weiler, Berkay Kicanaoglu, and Max Welling.  Gauge equivariant convolutional networks and the icosahedral CNN.  In _Proceedings of the 36th International Conference on Machine Learning (ICML)_ , volume 97, pages 1321–1330, 2019.
  * Cybenko [1989] George Cybenko.  Approximation by superpositions of a sigmoidal function.  _Mathematics of control, signals and systems_ , 2(4):303–314, 1989.
  * Deng et al. [2021] Congyue Deng, O. Litany, Yueqi Duan, A. Poulenard, A. Tagliasacchi, and L. Guibas.  Vector Neurons: A General Framework for SO(3)-Equivariant Networks.  _2021 IEEE/CVF International Conference on Computer Vision (ICCV)_ , 2021.  doi: 10.1109/iccv48922.2021.01198.
  * Dieleman et al. [2016] Sander Dieleman, Jeffrey De Fauw, and Koray Kavukcuoglu.  Exploiting cyclic symmetry in convolutional neural networks.  In _International Conference on Machine Learning (ICML)_ , 2016\.
  * Dinh et al. [2017] Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio.  Sharp Minima Can Generalize For Deep Nets.  In _International Conference on Machine Learning (ICML)_ , pages 1019–1028. PMLR, July 2017.  URL http://proceedings.mlr.press/v70/dinh17b.html.
  * Dong et al. [2017] Xin Dong, Shangyu Chen, and Sinno Jialin Pan.  Learning to prune deep neural networks via layer-wise optimal brain surgeon.  _arXiv preprint arXiv:1705.07565_ , 2017.
  * Frankle and Carbin [2018] Jonathan Frankle and Michael Carbin.  The lottery ticket hypothesis: Finding sparse, trainable neural networks.  _arXiv:1803.03635_ , 2018.
  * Gong et al. [2014] Yunchao Gong, Liu Liu, Ming Yang, and Lubomir Bourdev.  Compressing deep convolutional networks using vector quantization.  _arXiv:1412.6115_ , 2014.
  * Han et al. [2015] Song Han, Huizi Mao, and William J Dally.  Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding.  _arXiv:1510.00149_ , 2015.
  * Harris et al. [2020] Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant.  Array programming with NumPy.  _Nature_ , 585(7825):357–362, September 2020\.  doi: 10.1038/s41586-020-2649-2.  URL https://doi.org/10.1038/s41586-020-2649-2.
  * Hassibi and Stork [1993] Babak Hassibi and David G Stork.  _Second order derivatives for network pruning: Optimal brain surgeon_.  Morgan Kaufmann, 1993.
  * Hinton et al. [2015] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.  Distilling the knowledge in a neural network.  _arXiv:1503.02531_ , 2015.
  * Hornik [1991] Kurt Hornik.  Approximation capabilities of multilayer feedforward networks.  _Neural networks_ , 4(2):251–257, 1991.
  * Howard et al. [2017] Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam.  Mobilenets: Efficient convolutional neural networks for mobile vision applications.  _arXiv:1704.04861_ , 2017.
  * Jeffreys and Lau [2021] George Jeffreys and Siu-Cheong Lau.  Kähler Geometry of Quiver Varieties and Machine Learning.  _arXiv:2101.11487_ , 2021.  URL http://arxiv.org/abs/2101.11487.
  * Karnin [1990] Ehud D Karnin.  A simple procedure for pruning back-propagation trained neural networks.  _IEEE transactions on neural networks_ , 1(2):239–242, 1990.
  * Kidger and Lyons [2020] Patrick Kidger and Terry Lyons.  Universal approximation with deep narrow networks.  In _Conference on learning theory_ , pages 2306–2327. PMLR, 2020\.
  * Klambauer et al. [2017] Günter Klambauer, Thomas Unterthiner, Andreas Mayr, and Sepp Hochreiter.  Self-normalizing neural networks.  _Advances in neural information processing systems_ , 30, 2017.
  * Kondor and Trivedi [2018] Risi Kondor and Shubhendu Trivedi.  On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups.  In _International conference on machine learning (ICML)_ , 2018\.
  * Lang and Weiler [2021] Leon Lang and Maurice Weiler.  A Wigner-Eckart theorem for group equivariant convolution kernels.  In _International Conference on Learning Representations (ICLR)_ , 2021.
  * Lebedev et al. [2014] Vadim Lebedev, Yaroslav Ganin, Maksim Rakhuba, Ivan Oseledets, and Victor Lempitsky.  Speeding-up convolutional neural networks using fine-tuned cp-decomposition.  _arXiv:1412.6553_ , 2014.
  * LeCun et al. [1990] Yann LeCun, John S Denker, and Sara A Solla.  Optimal brain damage.  In _Advances in neural information processing systems_ , pages 598–605, 1990.
  * Lee et al. [2019] Namhoon Lee, Thalaiyasingam Ajanthan, Stephen Gould, and Philip HS Torr.  A signal propagation perspective for pruning neural networks at initialization.  _arXiv preprint arXiv:1906.06307_ , 2019.
  * Lu et al. [2017a] Yongxi Lu, Abhishek Kumar, Shuangfei Zhai, Yu Cheng, Tara Javidi, and Rogerio Feris.  Fully-adaptive feature sharing in multi-task networks with applications in person attribute classification.  In _Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR)_ , pages 5334–5343, 2017a.
  * Lu et al. [2017b] Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang.  The expressive power of neural networks: A view from the width.  _Advances in neural information processing systems_ , 30, 2017b.
  * Meng et al. [2019] Qi Meng, Shuxin Zheng, Huishuai Zhang, Wei Chen, Qiwei Ye, Zhi-Ming Ma, Nenghai Yu, and Tie-Yan Liu.  G-SGD: Optimizing ReLU Neural Networks in its Positively Scale-Invariant Space.  2019\.  URL https://www.microsoft.com/en-us/research/publication/g-sgd-optimizing-relu-neural-networks-in-its-positively-scale-invariant-space/.
  * Milletarí et al. [2018] Mirco Milletarí, Thiparat Chotibut, and Paolo E Trevisanutto.  Mean field theory of activation functions in deep neural networks.  _arXiv preprint arXiv:1805.08786_ , 2018.
  * Misra [2019] Diganta Misra.  Mish: A self regularized non-monotonic activation function.  _arXiv preprint arXiv:1908.08681_ , 2019.
  * Molchanov et al. [2016] Pavlo Molchanov, Stephen Tyree, Tero Karras, Timo Aila, and Jan Kautz.  Pruning convolutional neural networks for resource efficient inference.  _arXiv preprint arXiv:1611.06440_ , 2016.
  * Neyshabur et al. [2015] Behnam Neyshabur, Ruslan Salakhutdinov, and Nathan Srebro.  Path-SGD: path-normalized optimization in deep neural networks.  In _Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 2_ , NIPS’15, pages 2422–2430, Cambridge, MA, USA, December 2015. MIT Press.
  * Park and Sandberg [1991] Jooyoung Park and Irwin W Sandberg.  Universal approximation using radial-basis-function networks.  _Neural computation_ , 3(2):246–257, 1991.
  * Paszke et al. [2019] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  Pytorch: An imperative style, high-performance deep learning library.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems (NeurIPS) 32_ , pages 8024–8035. Curran Associates, Inc., 2019.  URL http://papers.neurips.cc/paper/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdf.
  * Ramachandran et al. [2017] Prajit Ramachandran, Barret Zoph, and Quoc V Le.  Searching for activation functions.  _arXiv preprint arXiv:1710.05941_ , 2017.
  * Ravanbakhsh [2020] Siamak Ravanbakhsh.  Universal equivariant multilayer perceptrons.  In _International Conference on Machine Learning_ , pages 7996–8006. PMLR, 2020.
  * Ravanbakhsh et al. [2017] Siamak Ravanbakhsh, Jeff Schneider, and Barnabas Poczos.  Equivariance through parameter-sharing.  In _International Conference on Machine Learning_ , pages 2892–2901. PMLR, 2017.
  * Rigamonti et al. [2013] Roberto Rigamonti, Amos Sironi, Vincent Lepetit, and Pascal Fua.  Learning separable filters.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 2754–2761, 2013.
  * Rosenblatt [1958] Frank Rosenblatt.  The perceptron: a probabilistic model for information storage and organization in the brain.  _Psychological review_ , 65(6):386, 1958.
  * Sabour et al. [2017] Sara Sabour, Nicholas Frosst, and Geoffrey E Hinton.  Dynamic routing between capsules.  _arXiv:1710.09829_ , 2017.
  * Serra et al. [2020] Thiago Serra, Abhinav Kumar, and Srikumar Ramalingam.  Lossless compression of deep neural networks.  In _International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research_ , pages 417–430. Springer, 2020.
  * Serra et al. [2021] Thiago Serra, Xin Yu, Abhinav Kumar, and Srikumar Ramalingam.  Scaling up exact neural network compression by relu stability.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Sonoda and Murata [2017] Sho Sonoda and Noboru Murata.  Neural network with unbounded activation functions is universal approximator.  _Applied and Computational Harmonic Analysis_ , 43(2):233–268, 2017.
  * Sourek et al. [2020] Gustav Sourek, Filip Zelezny, and Ondrej Kuzelka.  Lossless compression of structured convolutional models via lifting.  _arXiv preprint arXiv:2007.06567_ , 2020.
  * Tai et al. [2015] Cheng Tai, Tong Xiao, Yi Zhang, Xiaogang Wang, et al.  Convolutional neural networks with low-rank regularization.  _arXiv:1511.06067_ , 2015.
  * Wang et al. [2020] Chaoqi Wang, Guodong Zhang, and Roger Grosse.  Picking winning tickets before training by preserving gradient flow.  _arXiv preprint arXiv:2002.07376_ , 2020.
  * Wang and Qu [2022] Ming-Xi Wang and Yang Qu.  Approximation capabilities of neural networks on unbounded domains.  _Neural Networks_ , 145:56–67, 2022.
  * Weiler and Cesa [2019] Maurice Weiler and Gabriele Cesa.  General ${E}(2)$-Equivariant Steerable CNNs.  _Conference on Neural Information Processing Systems (NeurIPS)_ , 2019.
  * Weiler et al. [2018a] Maurice Weiler, Mario Geiger, Max Welling, Wouter Boomsma, and Taco Cohen.  3D steerable CNNs: Learning rotationally equivariant features in volumetric data.  _Proceedings of the 32nd International Conference on Neural Information Processing Systems (NeurIPS)_ , 2018a.
  * Weiler et al. [2018b] Maurice Weiler, Fred A Hamprecht, and Martin Storath.  Learning steerable filters for rotation equivariant CNNs.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 849–858, 2018b.
  * Worrall et al. [2017] Daniel E Worrall, Stephan J Garbin, Daniyar Turmukhambetov, and Gabriel J Brostow.  Harmonic networks: Deep translation and rotation equivariance.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 5028–5037, 2017.
  * Wu et al. [2016] Jiaxiang Wu, Cong Leng, Yuhang Wang, Qinghao Hu, and Jian Cheng.  Quantized convolutional neural networks for mobile devices.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 4820–4828, 2016.
  * Yarotsky [2022] Dmitry Yarotsky.  Universal approximations of invariant maps by neural networks.  _Constructive Approximation_ , 55(1):407–474, 2022.
  * Zhang et al. [2018] Tianyun Zhang, Shaokai Ye, Kaiqi Zhang, Jian Tang, Wujie Wen, Makan Fardad, and Yanzhi Wang.  A systematic DNN weight pruning framework using alternating direction method of multipliers.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pages 184–199, 2018.

##  Appendix A Organization of the appendices

This paper is a contribution to the mathematical foundations of machine
learning, and our results are motivated by expanding the applicability and
performance of neural networks. At the same time, we give precise mathematical
formulations of our results and proofs. The purposes of these appendices are
several:

  1. 1.

To clarify the mathematical conventions and terminology, thus making the paper
more accessible.

  2. 2.

To provide full proofs of the main results.

  3. 3.

To develop context around various construction appearing in the main text.

  4. 4.

To discuss in detail examples, special cases, and generalizations of our
results.

We now give a summary of the contents of the appendices.

Appendix B contains proofs the universal approximation results (Theorems 3 and
4) stated in Section 4 of the main text, as well as proofs of additional
bounded width results. The proofs use notation given in Appendix B.1, and rely
on preliminary topological considerations given in Appendix B.2.

In Appendix C, we give a proof of the model compression result given in
Theorem 5, which appears in Section 5. For clarity and background we begin the
appendix with a discussion of the version of the QR decomposition relevant for
our purposes (Appendix C.1). We also establish elementary properties of radial
rescaling activations (Appendix C.2).

The focus of Appendix D is projected gradient descent, elaborating on Section
6. We first prove a result on the interaction of gradient descent and
orthogonal transformations (Appendix D.1), before formulating projected
gradient descent in more detail (Appendix D.2), and introducing the so-called
interpolating space (Appendix D.3). We restate Theorem 7 in more convenient
notation (Appendix D.4) before proceeding to the proof (Appendix D.5).

Appendix E contains implementation details for the experiments summarized in
Section 7. Our implementations use shifted radial rescaling activations, which
we formulate in Appendix E.1.

##  Appendix B Universal approximation proofs and additional results

In this section, we provide full proofs of the universal approximation (UA)
results for radial neural networks, as stated in Section 4. In order to do so,
we first clarify our notational conventions (Appendix B.1), and collect basic
topological results (Appendix B.2).

###  B.1 Notation

Recall that, for a point $c$ in the Euclidean space $\mathbb{R}^{n}$ and a
positive real number $r$, we denote the $r$-ball around $c$ by
$B_{r}(c)=\\{x\in\mathbb{R}^{n}\ |\ |x-c|<r\\}$. All networks in this section
have the Step-ReLU radial rescaling activation function, defined as:

$\displaystyle\rho:\mathbb{R}^{n}$
$\displaystyle\longrightarrow\mathbb{R}^{n},\qquad
z\longmapsto\begin{cases}z&\qquad\text{\rm if $|z|\geq 1$}\\\
0&\qquad\text{\rm otherwise}\end{cases}$

Throughout, $\circ$ denotes the composition of functions. We identify a linear
map with a corresponding matrix (in the standard bases). In the case of linear
maps, the operation $\circ$ can be be identified with matrix multiplication.
Recall also that an affine map $L:\mathbb{R}^{n}\to\mathbb{R}^{m}$ is one of
the from $L(x)=Ax+b$ for a matrix $A\in\mathbb{R}^{m\times n}$ and
$b\in\mathbb{R}^{m}$.

###  B.2 Topology

Let $K$ be a compact subset of $\mathbb{R}^{n}$ and let $f:K\to\mathbb{R}^{m}$
be a continuous function.

######  Lemma 8.

For any $\epsilon>0$, there exist $c_{1},\dots,c_{N}\in K$ and
$r_{1},\dots,r_{N}\in(0,1)$ such that, first, the union of the balls
$B_{r_{i}}(c_{i})$ covers $K$; second, for all $i$, we have
$f\left(B_{r_{i}}(c_{i})\cap K\right)\subseteq B_{\epsilon}(f(c_{i}))$.

###### Proof.

The continuity of $f$ implies that for each $c\in K$, there exists $r=r_{c}$
such that $f(B_{r_{c}}(c)\cap K)\subseteq B_{\epsilon}(f(c))$. The subsets
$B_{r_{c}}(c)\cap K$ form an open cover of $K$. The compactness of $K$ implies
that there is a finite subcover. The result follows. ∎

We also prove a variation of Lemma 8 that additionally guarantees that none of
the balls in the cover of $K$ contains the center point of another ball.

######  Lemma 9.

For any $\epsilon>0$, there exist $c_{1},\dots,c_{M}\in K$ and
$r_{1},\dots,r_{M}\in(0,1)$ such that, first, the union of the balls
$B_{r_{i}}(c_{i})$ covers $K$; second, for all $i$, we have
$f\left(B_{r_{i}}(c_{i})\right)\subseteq B_{\epsilon}(f(c_{i}))$; and, third,
$|c_{i}-c_{j}|\geq r_{i}$.

###### Proof.

Because $f$ is continuous on a compact domain, it is uniformly continuous. So,
there exists $r>0$ such that $f(B_{r}(c)\cap K)\subseteq B_{\epsilon}(f(c))$
for each $c\in K$. Because $K$ is compact it has a finite volume, and so does
$B_{r/2}(K)=\bigcup_{c\in K}B_{r/2}(c)$. Hence, there exists a finite maximal
packing of $B_{r/2}(K)$ with balls of radius $r/2$. That is, a collection
$c_{1},\dotsc,c_{M}\in B_{r/2}(K)$ such that, for all $i$,
$B_{r/2}(c_{i})\subseteq B_{r/2}(K)$ and, for all $j\neq i$,
$B_{r/2}(c_{i})\cap B_{r/2}(c_{j})=\emptyset$. The first condition implies
that $c_{i}\in K$. The second condition implies that $|c_{i}-c_{j}|\geq r$.
Finally, we argue that $K\subseteq\bigcup_{i=1}^{M}B_{r}(c_{i})$. To see this,
suppose, for a contradiction, that $x\in K$ does not belong to
$\bigcup_{i=1}^{M}B_{r}(c_{i})$. Then $B_{r/2}(c_{i})\cap
B_{r/2}(x)=\emptyset$, and $x$ could be added to the packing, which
contradicts the fact that the packing was chosen to be maximal. So the union
of the balls $B_{r}(c_{i})$ covers $K$. ∎

We turn our attention to the minimal choices of $N$ and $M$ in Lemmas 8 and 9.

######  Definition 10.

Given $f:K\to\mathbb{R}^{m}$ continuous and $\epsilon>0$, let
$N(f,K,\epsilon)$ be the minimal choice of $N$ in Lemma 8, and let
$M(f,K,\epsilon)$ be the minimal choice of $M$ in Lemma 9.

Observe that $M(f,K,\epsilon)\geq N(f,K,\epsilon)$. In many cases, it is
possible to give explicit bounds for the constants $N(f,K,\epsilon)$ and
$M(f,K,\epsilon)$. As an illustration, we give the argument in the case that
$K$ is the closed unit cube in $\mathbb{R}^{n}$ and $f:K\to\mathbb{R}^{m}$ is
Lipschtiz continuous.

######  Proposition 11.

Let $K=[0,1]^{n}\subset\mathbb{R}^{n}$ be the (closed) unit cube and let
$f:K\to\mathbb{R}^{m}$ be Lipschitz continuous with Lipschitz constant $R$.
For any $\epsilon>0$, we have:

$N(f,K,\epsilon)\leq\left\lceil\frac{R\sqrt{n}}{2\epsilon}\right\rceil^{n}\qquad\text{and}\qquad
M(f,K,\epsilon)\leq\frac{\Gamma(n/2+1)}{\pi^{n/2}}\left(2+\frac{2R}{\epsilon}\right)^{n}.$

###### Proof.

For the first inequality, observe that the unit cube can be covered with
$\Bigl{\lceil}\frac{R\sqrt{n}}{2\epsilon}\Bigr{\rceil}^{n}$ cubes of side
length $\frac{2\epsilon}{R\sqrt{n}}$. Each cube is contained in a ball of
radius $\frac{\epsilon}{R}$ centered at the center of the cube. (In general, a
cube of side length $a$ in $\mathbb{R}^{n}$ is contained in a ball of radius
$\frac{a\sqrt{n}}{2}$.) Lipschitz continuity implies that, for all
$x,x^{\prime}\in K$, if $|x-x^{\prime}|<\epsilon/R$ then
$|f(x)-f(x^{\prime})|\leq R|x-x^{\prime}|<\epsilon$.

For the second inequality, let $r=\epsilon/R$. Lipschitz continuity implies
that, for all $x,x^{\prime}\in K$, if $|x-x^{\prime}|<r$ then
$|f(x)-f(x^{\prime})|\leq R|x-x^{\prime}|<\epsilon$. The $n$-dimensional
volume of the set of points with distance at most $r/2$ to the unit cube is
$\text{vol}(B_{r/2}(K))\leq(1+r)^{n}$. The volume of a ball with radius $r/2$
is $\text{vol}(B_{r/2}(0))=\frac{\pi^{n/2}}{\Gamma(n/2+1)}(r/2)^{n}$. Hence,
any packing of $B_{r/2}(K)$ with balls of radius $r/2$ consists of at most

$\frac{\text{vol}(B_{r/2}(K))}{\text{vol}(B_{r/2}(0))}\leq\frac{\Gamma(n/2+1)}{\pi^{n/2}}\left(2+\frac{2R}{\epsilon}\right)^{n}$

such balls. So there also exists a maximal packing with at most that many
balls. This packing can be used in the proof of 9, which implies that it is a
bound on $M(f,K,\epsilon)$. ∎

We note in passing that any differentiable function $f:K\to\mathbb{R}^{n}$ on
a compact subset $K$ of $\mathbb{R}^{n}$ is Lipschitz continuous. Indeed, the
compactness of $K$ implies that there exists $R$ such that
$|f^{\prime}(x)|\leq R$ for all $x\in K$. Then one can take $R$ to be the
Lipschitz constant of $f$.

###  B.3 Proof of Theorem 3: UA for asymptotically affine functions

In this section, we restate and prove Theorem 3, which proves that radial
neural networks are universal approximators of asymptotically affine
functions. We recall the definition of such functions:

######  Definition 12.

A function $f:\mathbb{R}^{n}\to\mathbb{R}^{m}$ is _asymptotically affine_ if
there exists an affine function $L:\mathbb{R}^{n}\to\mathbb{R}^{m}$ such that,
for all $\epsilon>0$, there exists a compact set $K\subset\mathbb{R}^{n}$ such
that $|L(x)-f(x)|<\epsilon$ for all $x\in\mathbb{R}^{n}\setminus K$. We say
that $L$ is the limit of $f$.

######  Remark 13.

An asymptotically linear function is defined in the same way, except $L$ is
taken to be linear (i.e., given just by applying matrix multiplication without
translation). Hence any asymptotically linear function is in particular an
asymptotically affine function, and Theorem 3 applies to asymptotically linear
functions as well.

Given an asymptotically affine function $f:\mathbb{R}^{n}\to\mathbb{R}^{m}$
and $\epsilon>0$, let $K$ be a compact set as in Definition 12. We apply Lemma
8 to the restriction $f|_{K}$ of $f$ to $K$ and produce a minimal constant
$N=N(f|_{K},K,\epsilon)$ as in Definition 10. We write simply
$N(f,K,\epsilon)$ for this constant.

See 3

###### Proof.

By the hypothesis on $f$, there exists an affine function
$L:\mathbb{R}^{n}\to\mathbb{R}^{m}$ and a compact set $K\subset\mathbb{R}^{n}$
such that $|L(x)-f(x)|<\epsilon$ for all $x\in\mathbb{R}^{n}\setminus K$.
Abbreviate $N(f,K,\epsilon)$ by $N$. As in Lemma 8, fix $c_{1},\dots,c_{N}\in
K$ and $r_{1},\dots,r_{N}\in(0,1)$ such that, first, the union of the balls
$B_{r_{i}}(c_{i})$ covers $K$ and, second, for all $i$, we have
$f\left(B_{r_{i}}(c_{i})\right)\subseteq B_{\epsilon}(f(c_{i}))$. Let
$U=\bigcup_{i=1}^{N}B_{r_{i}}(c_{i})$, so that $K\subset U$. Define
$F:\mathbb{R}^{n}\to\mathbb{R}^{m}$ as:

$F(x)=\begin{cases}L(x)&\qquad\text{\rm if $x\notin U$}\\\
f(c_{j})&\qquad\text{\rm where $j$ is the smallest index with $x\in
B_{r_{j}}(c_{j})$}\end{cases}$

If $x\notin U$, then $|F(x)-f(x)|=|L(x)-f(x)|<\epsilon$. Hence suppose $x\in
U$. Let $j$ be the smallest index such that $x\in B_{r_{j}}(c_{j})$. Then
$F(x)=f(c_{j})$, and, by the choice of $r_{j}$, we have:

$|F(x)-f(x)|=|f(c_{j})-f(x)|<\epsilon.$

We proceed to show that $F$ is the feedforward function of a radial neural
network. Let $e_{1},\dots,e_{N}$ be orthonormal basis vectors extending
$\mathbb{R}^{n}$ to $\mathbb{R}^{n+N}$. We regard each $\mathbb{R}^{n+i-1}$ as
a subspace of $\mathbb{R}^{n+i}$ by embedding into the first $n+i-1$
coordinates. For $i=1,\dots,N$, we set $h_{i}=\sqrt{1-r_{i}^{2}}$ and define
the following affine transformations:

$\displaystyle T_{i}:\mathbb{R}^{n+i-1}$
$\displaystyle\to\mathbb{R}^{n+i}\qquad$ $\displaystyle
S_{i}:\mathbb{R}^{n+i}$ $\displaystyle\to\mathbb{R}^{n+i}$ $\displaystyle z$
$\displaystyle\mapsto z-c_{i}+h_{i}e_{i}\qquad$ $\displaystyle z$
$\displaystyle\mapsto z-(1+h_{i}^{-1})\langle e_{i},z\rangle
e_{i}+c_{i}+e_{i}$

where $\langle e_{i},z\rangle$ is the coefficient of $e_{i}$ in $z$. Consider
the radial neural network with widths $(n,n+1,\dots,n+N,m)$, whose affine
transformations and activations are given by:

  * •

For $i=1,\dots,N$ the affine transformation from layer $i-1$ to layer $i$ is
given by $z\mapsto T_{i}\circ S_{i-1}(z)$, where $S_{0}=\text{\rm
id}_{\mathbb{R}^{n}}$.

  * •

The activation function at the $i$-th hidden layer is Step-ReLU on
$\mathbb{R}^{n+i}$, that is:

$\displaystyle\rho_{i}:\mathbb{R}^{n+i}$
$\displaystyle\longrightarrow\mathbb{R}^{n+i},\qquad
z\longmapsto\begin{cases}z&\qquad\text{\rm if $|z|\geq 1$}\\\
0&\qquad\text{\rm otherwise}\end{cases}$

  * •

The affine transformation from layer $i=N$ to the output layer is

$z\mapsto\Phi_{L,f,\mathbf{c}}\circ S_{N}(z)$

where $\Phi_{L,f,\mathbf{c}}$ is the affine transformation given by:

$\Phi_{L,f,\mathbf{c}}:\mathbb{R}^{n+N}\to\mathbb{R}^{m},\qquad
x+\sum_{i=1}^{N}a_{i}e_{i}\ \mapsto\
L(x)+\sum_{i=1}^{N}a_{i}(f(c_{i})-L(c_{i}))$

which can be shown to be affine when $L$ is affine. Indeed, write $L(x)=Ax+b$
where $A$ is a matrix in $\mathbb{R}^{m\times n}$ and $b\in R^{m}$ is a
vector. Then $\Phi_{L,f,\mathbf{c}}$ is the composition of the linear map
given by the matrix

$\begin{bmatrix}A&f(c_{1})-L(c_{1})&f(c_{2})-L(c_{2})&\cdots&f(c_{N})-L(c_{N})\end{bmatrix}\in\mathbb{R}^{m\times(n+N)}$

and translation by $b\in\mathbb{R}^{m}$. Note that we regard each
$f(c_{i})-L(c_{i})\in\mathbb{R}^{m}$ as a column vector in the matrix above.

We claim that the feedforward function of the above radial neural network is
exactly $F$. To show this, we first state a lemma, whose (omitted) proof is an
elementary computation.

######  Lemma 0.1.

For $i=1,\dots,N$, the composition $S_{i}\circ T_{i}$ is the embedding
$\mathbb{R}^{n+i-1}\hookrightarrow\mathbb{R}^{n+i}$.

Next, recursively define $G_{i}:\mathbb{R}^{n}\to\mathbb{R}^{n+i}$ via

$G_{i}=S_{i}\circ\rho_{i}\circ T_{i}\circ G_{i-1},$

where $G_{0}=\text{\rm id}_{\mathbb{R}^{n}}$. The function $G_{i}$ admits an
direct formulation:

######  Proposition 0.2.

For $i=0,1,\dots,N$, we have:

$G_{i}(x)=\begin{cases}x&\qquad\text{\rm if
$x\notin\bigcup_{j=1}^{i}B_{r_{j}}(c_{j})$}\\\ c_{j}+e_{j}&\qquad\text{\rm
where $j\leq i$ is the smallest index with $x\in
B_{r_{j}}(c_{j})$}\end{cases}.$

###### Proof.

We proceed by induction. The base step $i=0$ is immediate. For the induction
step, assume the claim is true for $i-1$, where $0\leq i-1<N$. There are three
cases to consider.

Case 1. Suppose $x\notin\bigcup_{j=1}^{i}B_{r_{j}}(c_{j})$. Then in particular
$x\notin\bigcup_{j=1}^{i-1}B_{r_{j}}(c_{j})$, so the induction hypothesis
implies that $G_{i-1}(x)=x$. Additionally, $x\notin B_{r_{i}}(c_{i})$, so:

$|T_{i}(x)|=|x-c_{i}+h_{i}e_{i}|=\sqrt{|x-c_{i}|+h_{i}^{2}}\geq\sqrt{r_{i}^{2}+1-r_{i}^{2}}=1.$

Using the definition of $\rho_{i}$ and Lemma 0.1, we compute:

$G_{i}(x)=S_{i}\circ\rho_{i}\circ T_{i}\circ
G_{i-1}(x)=S_{i}\circ\rho_{i}\circ T_{i}(x)=S_{i}\circ T_{i}(x)=x.$

Case 2. Suppose $x\in B_{j}\setminus\bigcup_{k=1}^{j-1}B_{r_{k}}(c_{k})$ for
some $j\leq i-1$. Then the induction hypothesis implies that
$G_{i-1}(x)=c_{j}+e_{j}$. We compute:

$|T_{i}(c_{j}+e_{j})|=|c_{j}+e_{j}-c_{i}+h_{i}e_{i}|>|e_{j}|=1.$

Therefore,

$G_{i}(x)=S_{i}\circ\rho_{i}\circ T_{i}(c_{j}+e_{j})=S_{i}\circ
T_{i}(c_{j}+e_{j})=c_{j}+e_{j}.$

Case 3. Finally, suppose $x\in
B_{i}\setminus\bigcup_{j=1}^{i-1}B_{r_{j}}(c_{j})$. The induction hypothesis
implies that $G_{i-1}(x)=x$. Since $x\in B_{r_{i}}(c_{i})$, we have:

$|T_{i}(x)|=|x-c_{i}+h_{i}e_{i}|=\sqrt{|x-c_{i}|+h_{i}^{2}}<\sqrt{r_{i}^{2}+1-r_{i}^{2}}=1.$

Therefore:

$G_{i}(x)=S_{i}\circ\rho_{i}\circ T_{i}(x)=S_{i}(0)=c_{i}+e_{i}.$

This completes the proof of the proposition. ∎

Finally, we show that the function $F$ defined at the beginning of the proof
is the feedforward function of the above radial neural network. The
computation is elementary:

$\displaystyle F_{\text{\rm feedforward}}$
$\displaystyle=\Phi_{L,f,\mathbf{c}}\circ S_{N}\circ\rho_{N}\circ T_{N}\circ
S_{N-1}\circ\rho_{N-1}\circ T_{N-1}\circ\cdots S_{1}\circ\rho_{1}\circ T_{1}$
$\displaystyle=\Phi_{L,f,\mathbf{c}}\circ G_{N}$ $\displaystyle=F$

where the first equality follows from the definition of the feedforward
function, the second from the definition of $G_{N}$, and the last from the
case $i=N$ of Proposition 0.2 together with the definition of
$\Phi_{L,f,\mathbf{c}}$. This completes the proof of the theorem. ∎

###  B.4 Proof of Theorem 4: bounded width UA for asymptotically affine
functions

We restate and prove Theorem 4, which strengthens Theorem 3 by providing a
bounded width radial neural network approximation of any asymptotically affine
function.

See 4

###### Proof.

By the hypothesis on $f$, there exists an affine function
$L:\mathbb{R}^{n}\to\mathbb{R}^{m}$ and a compact set $K\subset\mathbb{R}^{n}$
such that $|L(x)-f(x)|<\epsilon$ for all $x\in\mathbb{R}^{n}\setminus K$.
Given $\epsilon>0$, let $N=N(f,K,\epsilon)$ and use Lemma 8 to choose
$c_{1},\dots,c_{N}\in K$ and $r_{1},\dots,r_{N}\in(0,1)$ such that the union
of the balls $B_{r_{i}}(c_{i})$ covers $K$, and, for all $i$, we have
$f(B_{r_{i}}(c_{i}))\subseteq B_{\epsilon}(f(c_{i}))$. Let $s$ be the minimal
non-zero value of $|f(c_{i})-f(c_{j})|$ for $i,j\in\\{1,\dots,N\\}$, that is,
$s=\min_{i,j,f(c_{i})\neq f(c_{j})}|f(c_{i})-f(c_{j})|$.

Using the decomposition
$\mathbb{R}^{n+m+1}\cong\mathbb{R}^{n}\times\mathbb{R}^{m}\times\mathbb{R}$,
we write elements of $\mathbb{R}^{n+m+1}$ as $(x,y,\theta)$, where
$x\in\mathbb{R}^{n}$, $y\in\mathbb{R}^{m}$, and $\theta\in\mathbb{R}$. For
$i=1,\dots,N$, set:

$T_{i}:\mathbb{R}^{n+m+1}\to\mathbb{R}^{n+m+1},\qquad(x,y,\theta)\mapsto\left(x-(1-\theta)c_{i}\
,\ y-\theta\frac{f(c_{i})-L(0)}{s}\ ,\ (1-\theta)h_{i}\right)$

where $h_{i}=\sqrt{1-r_{i}^{2}}$. Note that $T_{i}$ is an invertible affine
transformation, whose inverse is given by:

$T_{i}^{-1}(x,y,\theta)=\left(x+\frac{\theta}{h_{i}}c_{i}\ ,\
y+\Bigl{(}1-\frac{\theta}{h_{i}}\Bigr{)}\frac{f(c_{i})-L(0)}{s}\ ,\
1-\frac{\theta}{h_{i}}\right)$

For $i=1,\dots,N$, define $G_{i}:\mathbb{R}^{n}\to\mathbb{R}^{n+m+1}$ via the
following recursive definition:

$G_{i}=T_{i}^{-1}\circ\rho\circ T_{i}\circ G_{i-1},$

where $G_{0}(x)=(x,0,0):{\mathbb{R}^{n}\hookrightarrow\mathbb{R}^{n+m+1}}$ is
the inclusion, and $\rho:\mathbb{R}^{n+m+1}\to\mathbb{R}^{n+m+1}$ is Step-ReLU
on $\mathbb{R}^{n+m+1}$. We claim that, for $x\in\mathbb{R}^{n}$, we have:

$G_{i}(x)=\begin{cases}(x,0,0)&\qquad\text{\rm if
$x\notin\bigcup_{j=1}^{i}B_{r_{j}}(c_{j})$}\\\
\Bigl{(}0,\frac{f(c_{j})-L(0)}{s},1\Bigr{)}&\qquad\text{\rm where $j\leq i$ is
the smallest index with $x\in B_{r_{j}}(c_{j})$}\end{cases}$

This claim can be verified by a straightforward induction argument, similar to
the one given in the proof of Proposition 0.2, and using the following key
facts:

  * •

For $x\in\mathbb{R}^{n}$,
$\bigl{|}T_{i}\bigl{(}(x,0,0)\bigr{)}\bigr{|}=\bigl{|}(x-c_{i},0,h_{i})\bigr{|}<1$
if and only if $|x-c_{i}|<r_{i}$.

  * •

$T_{i}^{-1}(0)=\Bigl{(}0,\frac{f(c_{i})-L(0)}{s},1\Bigr{)}$.

  * •

$T_{i}\biggl{(}\Bigl{(}0,\frac{f(c_{j})-L(0)}{s},1\Bigr{)}\biggr{)}=\Bigl{(}0,\frac{f(c_{j})-f(c_{i})}{s},0\Bigr{)}$,
which, by the choice of $s$, has norm at least $1$ if $f(c_{j})\neq f(c_{i})$,
and is $0$ if $f(c_{j})=f(c_{i})$.

Let $\Phi:\mathbb{R}^{n+m+1}\to\mathbb{R}^{m}$ denote the affine map sending
$(x,y,\theta)$ to $L(x)+sy$. It follows that $F=\Phi\circ G_{N}$ satisfies

$F(x)=\begin{cases}L(x)&\qquad\text{\rm if
$x\notin\bigcup_{j=1}^{N}B_{r_{j}}(c_{j})$}\\\ f(c_{j})&\qquad\text{\rm where
$j$ is the smallest index with $x\in B_{r_{j}}(c_{j})$}\end{cases}$

By construction, $F$ is the feedforward function of a radial neural network
with $N$ hidden layers whose widths are all $n+m+1$. Let $x\in\mathbb{R}^{n}$.
If $x\in K$, let $j$ be the smallest index such that $x\in B_{r_{j}}(c_{j})$.
Then $F(x)=f(c_{j})$, and, by the choice of $r_{j}$, we have
$|F(x)-f(x)|=|f(c_{j})-f(x)|<\epsilon$. Otherwise,
$x\in\mathbb{R}^{n}\setminus K$, and $|F(x)-f(x)|=|L(x)-f(x)|<\epsilon$. ∎

###  B.5 Additional result: bound of $\max(n,m)+1$

We state and prove an additional bounded width result. In contrast to the
results above, the theorem below only holds for functions defined on a compact
domain, without assumptions about the asymptotic behavior. The proof is an
adaptation of the proof of Theorem 4, so we give only a sketch.

######  Theorem 14.

Let $f:K\to\mathbb{R}^{m}$ be a continuous function, where $K$ is a compact
subset of $\mathbb{R}^{n}$. For any $\epsilon>0$, there exists
$F:\mathbb{R}^{n}\to\mathbb{R}^{m}$ such that:

  1. 1.

$F$ is the feedforward function of a radial neural network with
$N(f,K,\epsilon)$ hidden layers whose widths are all $\max(n,m)+1$.

  2. 2.

For any $x\in K$, we have $|F(x)-f(x)|<\epsilon$.

###### Sketch of proof..

The construction appearing in the proof of Theorem 4 with $L\equiv 0$ can be
used to produce a radial neural network with $N(f,K,\epsilon)$ hidden layers
with widths $n+m+1$ that approximates $f$ on $K$. (Note that the approximation
works only on $K$, as $f$ is not defined outside of $K$.) All values in the
hidden layers are of the form $(x,0,0)$ or $(0,y,1)$. We can therefore replace
$(x,y,\theta)\in\mathbb{R}^{n+m+1}$ by
$(x+y,\theta)\in\mathbb{R}^{\max(n,m)}\times\mathbb{R}\cong\mathbb{R}^{\max(n,m)+1}$
everywhere, without affecting any statements about the hidden layers. In
particular, the transformation $T_{i}$ becomes

$T_{i}:\mathbb{R}^{\max(n,m)+1}\to\mathbb{R}^{\max(n,m)+1},\qquad(x,\theta)\mapsto\left(x-(1-\theta)c_{i}-\theta\frac{f(c_{i})}{s}\
,\ (1-\theta)h_{i}\right).$

With this change the final affine map $\Phi$ sends $(x,\theta)$ to $sx$. From
the rest of the proof of Theorem 4 it follows that the feedforward function
$F$ of the radial network satisfies $|F(x)-f(x)|<\epsilon$ for all $x\in K$. ∎

###  B.6 Additional result: bound of $\max(n,m)$

In this section, we prove a different version of the result of the previous
section. Specifically, we reduce the bound on the widths to $\max(n,m)$ at the
cost of using more layers. Again, we focus on functions defined on a compact
domain without assumptions about their asymptotic behavior. Recall the
notation $M(f,K,\epsilon)$ from 9 and 10.

######  Theorem 15.

Let $f:K\to\mathbb{R}^{m}$ be a continuous function, where $K$ is a compact
subset of $\mathbb{R}^{n}$ for $n\geq 2$. For any $\epsilon>0$, there exists
$F:\mathbb{R}^{n}\to\mathbb{R}^{m}$ such that:

  1. 1.

$F$ is the feedforward function of a radial neural network with
$2M(f,K,\epsilon/2)$ hidden layers whose widths are all $\max(n,m)$.

  2. 2.

For any $x\in K$, we have $|F(x)-f(x)|<\epsilon$.

###### Proof.

We first consider the proof in the case $n=m$. Set $M=M(f,K,\epsilon)$. As in
Lemma 9, fix $c_{1},\dots,c_{M}\in K$ and $r_{1},\dots,r_{M}\in(0,1)$ such
that, first, the union of the balls $B_{r_{i}}(c_{i})$ covers $K$; second, for
all $i$, we have $f\left(B_{r_{i}}(c_{i})\right)\subseteq
B_{\epsilon/2}(f(c_{i}))$; and third, $|c_{i}-c_{j}|\geq r_{i}$ for $i\neq j$.
For $i=1,\dots,M$, set

$T_{i}:\mathbb{R}^{n}\to\mathbb{R}^{n},\qquad x\mapsto\frac{x-c_{i}}{r_{i}},$

and recursively define $G_{i}:\mathbb{R}^{n}\to\mathbb{R}^{n}$ as
$G_{i}=T_{i}^{-1}\circ\rho\circ T_{i}\circ G_{i-1},$ where $G_{0}=\text{\rm
id}_{\mathbb{R}^{n}}$ is the identity on $\mathbb{R}^{n}$ and
$\rho:\mathbb{R}^{n}\to\mathbb{R}^{n}$ is Step-ReLU.

######  Lemma 15.1.

For $i=0,1,\dots,N$, we have:

$G_{i}(x)=\begin{cases}x&\qquad\text{\rm if
$x\notin\bigcup_{j=1}^{i}B_{r_{j}}(c_{j})$}\\\ c_{j}&\qquad\text{\rm where
$j\leq i$ is the smallest index with $x\in B_{r_{j}}(c_{j})$}.\end{cases}$

We omit the full proof of Lemma 15.1, as it is a standard induction argument
similar to Proposition 0.2, relying on the following two facts. First,
$|T_{i}(x)|<1$ if and only if $x\in B_{r_{i}}(c_{i})$. Second, by the choice
of $c_{i}$, we have $|c_{i}-c_{j}|\geq r_{i}$ for all $i\neq j$. This implies
that $|T_{i}(c_{j})|\geq 1$ for $i\neq j$.

Next, perform the following loop over $i=1,\dots,M$:

  * •

Set $P_{i-1}=\\{c_{1},\dots,c_{M}\\}\cup\\{d_{1},\dots,d_{i-1}\\}$

  * •

Choose $d_{i}$ in $B_{\epsilon/2}(f(c_{i}))$ that is not colinear with any
pair of points in $P_{i-1}$. This is where we use the hypothesis that $n\geq
2$.

  * •

Let $s_{i}$ be the minimum distance between any point on the line through
$c_{i}$ and $d_{i}$ and any point in $P_{i-1}\setminus\\{c_{i}\\}$.

  * •

Let $U_{i}:\mathbb{R}^{n}\to\mathbb{R}^{n}$ be the following affine
transformation:

$U_{i}:\mathbb{R}^{n}\to\mathbb{R}^{n},\qquad
x\mapsto\frac{x-d_{i}}{s_{i}}+\left(\frac{1}{|c_{i}-d_{i}|}-\frac{1}{s_{i}}\right)\frac{\langle
x-d_{i},c_{i}-d_{i}\rangle}{|c_{i}-d_{i}|^{2}}(c_{i}-d_{i})$

  * •

Define $H_{i}:\mathbb{R}^{n}\to\mathbb{R}^{n}$ recursively as
$H_{i}=U_{i}^{-1}\circ\rho\circ U_{i}\circ H_{i-1}$, where $H_{0}=\text{\rm
id}_{\mathbb{R}^{n}}$.

We note that the transformation $U_{i}$ can also be written as
$A_{i}(x-d_{i})$ where $A_{i}$ is the linear map given by
$A_{i}=\frac{1}{s_{i}}\text{\rm proj}_{\langle
c_{i}-d_{i}\rangle^{\perp}}+\frac{1}{|c_{i}-d_{i}|}\text{\rm proj}_{\langle
c_{i}-d_{i}\rangle}$, which involves the projections onto the line spanned by
$c_{i}-d_{i}$ and onto the orthogonal complement of this line.

######  Lemma 15.2.

For $i,j=1,\dots,M$, we have:

$H_{i}(c_{j})=\begin{cases}d_{j}&\qquad\text{\rm if $j\leq i$}\\\
c_{j}&\qquad\text{\rm if $j>i$}\end{cases}$

###### Proof.

It is immediate that $U_{i}(d_{i})=0$ and $|U_{i}(c_{i})|=1/2$. It is also
straightforward to show, using the choice of $s_{i}$, that $|U_{i}(p)|\geq 1$
for all $p\in P_{i-1}\setminus\\{c_{i}\\}$. It follows that
$U_{i}^{-1}\circ\rho\circ U_{i}$ sends $c_{i}$ to $d_{i}$ and fixes all other
points in $P_{i-1}$. ∎

######  Lemma 15.3.

For $x\in K$, we have $H_{M}\circ G_{M}(x)=d_{i}$ where $i$ is the smallest
index with $x\in B_{r_{i}}(c_{i})$

###### Proof.

Let $x\in K$. By Lemma 15.1, we have that $G_{M}(x)=c_{i}$ where $i$ is the
smallest index with $x\in B_{r_{i}}(c_{i})$. (We use the fact that the balls
$\\{B_{r_{i}}(c_{i})\\}$ cover $K$.) By Lemma 15.2, we have that
$H_{M}(c_{i})=d_{i}$ for all $i$. The result follows. ∎

Set $F=H_{M}\circ G_{M}$. We see that, for $x\in K$:

$|F(x)-f(x)|=|d_{i}-f(x)|\leq|d_{i}-f(c_{i})|+|f(c_{i})-f(x)|<\epsilon/2+\epsilon/2=\epsilon$

where $i$ is the smallest index with $x\in B_{r_{i}}(c_{i})$. We show that $F$
is the feedforward function of a radial neural network with $2M$ hidden
layers, all of width equal to $n$. Indeed, take the affine transformations and
activations as follows:

  * •

For $i=1,\dots,M$ the affine transformation from layer $i-1$ to layer $i$ is
given by $x\mapsto T_{i}\circ T_{i-1}^{-1}(x)$, where $T_{0}=\text{\rm
id}_{\mathbb{R}^{n}}$.

  * •

For $i=1,\dots,M$ the affine transformation from layer $M+i-1$ to layer $M+i$
is given by $x\mapsto U_{i}\circ U_{i-1}^{-1}(x)$, where $U_{0}=T_{N}^{-1}$.

  * •

The activation at each hidden layer is Step-ReLU on $\mathbb{R}^{n}$ that is
$\rho(x)=x$ if $|x|\geq 1$ and $0$ otherwise.

  * •

Layer $2M+1$ has the affine transformation $U_{M}^{-1}$.

It is immediate from definitions that the feedforward function of this network
is $F$.

To conclude the proof, we discuss the cases where $n\neq m$. Suppose $n<m$ so
that $\max(n,m)=m$. Then we can regard $K$ as a compact subset of
$\mathbb{R}^{m}$ and apply the above constructions. Suppose $n>m$ so that
$\max(n,m)=n$. Let $\text{\rm
inc}:\mathbb{R}^{m}\hookrightarrow\mathbb{R}^{n}$. Apply the above
constructions to the function $\tilde{f}=\text{\rm inc}\circ
f:K\to\mathbb{R}^{n}$. ∎

##  Appendix C Model compression proofs

The aim of this appendix is to give a proof of Theorem 5. In order to do so,
we first (1) provide background on a relevant version of the QR decomposition,
and (2) establish basic properties of radial rescaling activations.

###  C.1 The QR decomposition

In this section, we recall the QR decomposition and note several relevant
facts. For integers $n$ and $m$, let $\left(\mathbb{R}^{n\times
m}\right)^{\text{\rm upper}}$ denote the vector space of upper triangular $n$
by $m$ matrices.

######  Theorem 16 (QR Decomposition).

The following map is surjective:

$\displaystyle O(n)\times\left(\mathbb{R}^{n\times m}\right)^{\text{\rm
upper}}$ $\displaystyle\longrightarrow\mathbb{R}^{n\times m}$ $\displaystyle
Q\ ,\ R\quad$ $\displaystyle\mapsto\quad Q\circ R$

In other words, any matrix can be written as the product of an orthogonal
matrix and an upper-triangular matrix. When $m\leq n$, the last $n-m$ rows of
any matrix in $\left(\mathbb{R}^{n\times m}\right)^{\text{\rm upper}}$ are
zero, and the top $m$ rows form an upper-triangular $m$ by $m$ matrix. These
observations lead to the following “complete” version of the QR decomposition,
which coincides with the above result when $m\geq n$:

######  Corollary 17 (Complete QR Decomposition).

The following map is surjective:

$\displaystyle\mu:O(n)\times\left(\mathbb{R}^{k\times m}\right)^{\text{\rm
upper}}$ $\displaystyle\longrightarrow\mathbb{R}^{n\times m}$ $\displaystyle
Q\ ,\ R\quad$ $\displaystyle\mapsto\quad Q\ \circ\ \text{\rm inc}\ \circ\ R$

where $k=\min(n,m)$ and $\text{\rm
inc}:\mathbb{R}^{k}\hookrightarrow\mathbb{R}^{n}$ is the standard inclusion
into the first $k$ coordinates.

We make some remarks:

  1. 1.

There are several algorithms for computing the QR decomposition of a given
matrix. One is Gram–Schmidt orthogonalization, and another is the method of
Householder reflections. The latter has computational complexity $O(n^{2}m)$
in the case of a $n\times m$ matrix with $n\geq m$. The package numpy includes
a function numpy.linalg.qr that computes the QR decomposition of a matrix
using Householder reflections.

  2. 2.

In each iteration of the loop in Algorithm 1, the method QR-decomp with mode =
‘complete’ takes as input a matrix $A_{i}$ of size $n_{i}\times(n^{\rm
red}_{i-1}+1)$, and produces an orthogonal matrix $Q_{i}\in O(n_{i})$ and an
upper-triangular matrix $R_{i}$ of size $\min(n_{i},n^{\rm
red}_{i-1}+1)\times(n^{\rm red}_{i-1}+1)$ such that $A_{i}=Q_{i}\circ\text{\rm
inc}_{i}\circ R_{i}$. Note that $n^{\rm red}_{i}=\min(n_{i},n^{\rm
red}_{i-1}+1)$.

  3. 3.

The QR decomposition is not unique in general, or, in other words, the map
$\mu$ is not injective in general. For example, if $n>m$, each fiber of $\mu$
contains a copy of the orthogonal group $O(n-m)$.

  4. 4.

The QR decomposition is unique (in a certain sense) for invertible square
matrices. To be precise, let $B_{n}^{+}$ be the subset of of
$\left(\mathbb{R}^{n\times n}\right)^{\text{\rm upper}}$ consisting of upper
triangular $n$ by $n$ matrices with positive entries along the diagonal. Both
$B_{n}^{+}$ and $O(n)$ are subgroups of the general linear group
$\mathrm{GL}_{n}(\mathbb{R})$, and the multiplication map $O(n)\times
B_{n}^{+}\to\mathrm{GL}_{n}(\mathbb{R})$ is bijective. However, the QR
decomposition is not unique for non-invertible square matrices.

###  C.2 Radial rescaling functions

We now prove the following basic facts about radial rescaling functions:

######  Lemma 18.

Let $\rho=h^{(n)}:\mathbb{R}^{n}\to\mathbb{R}^{n}$ be a radial rescaling
function on $\mathbb{R}^{n}$.

  1. 1.

The function $\rho$ commutes with any orthogonal transformation of
$\mathbb{R}^{n}$. That is, $\rho\circ Q=Q\circ\rho$ for any $Q\in O(n)$.

  2. 2.

If $m\leq n$ and $\text{\rm inc}:\mathbb{R}^{m}\hookrightarrow\mathbb{R}^{n}$
is the standard inclusion into the first $m$ coordinates, then:
$h^{(n)}\circ\text{\rm inc}=\text{\rm inc}\circ h^{(m)}.$

###### Proof.

Suppose $Q\in O(n)$ is an orthogonal transformation of $\mathbb{R}^{n}$. Since
$Q$ is norm-preserving, we have $|Qv|=|v|$ for any $v\in\mathbb{R}^{n}$. Since
$Q$ is linear, we have $Q(\lambda v)=\lambda Qv$ for any
$\lambda\in\mathbb{R}$ and $v\in\mathbb{R}^{n}$. Using the definition of
$a=h^{(n)}$ we compute:

$\displaystyle\rho(Qv)$
$\displaystyle=\frac{h(|Qv|)}{|Qv|}Qv=\frac{h(|v|)}{|v|}Qv=Q\left(\frac{h(|v|)}{|v|}v\right)=Q(\rho(v)).$

The first claim follows. The second claim is an elementary verification. ∎

More generally, the restriction of the radial rescaling function $\rho$ to a
linear subspace of $\mathbb{R}^{n}$ is a radial rescaling function on that
subspace. Given a tuple radial rescaling functions
$\bm{\rho}=\left(\rho_{i}:\mathbb{R}^{n_{i}}\to\mathbb{R}^{n_{i}}\right)_{i=1}^{L}$
suited to widths $\mathbf{n}=(n_{i})_{i=1}^{L}$, we write $\bm{\rho}^{\rm
red}=\left(\rho^{\rm red}_{i}:\mathbb{R}^{n^{\rm
red}_{i}}\to\mathbb{R}^{n^{\rm red}_{i}}\right)$ for the tuple of restrictions
suited to the reduced widths $\mathbf{n}^{\text{\rm red}}$, so that $\rho^{\rm
red}_{i}=\rho_{i}\biggr{|}_{\mathbb{R}^{n^{\rm red}_{i}}}$.

###  C.3 Proof of Theorem 5

Adopting notation from above and Section 5, we now restate and prove Theorem
5.

See 5

###### Proof.

Let $(\mathbf{W}^{\text{\rm red}},\mathbf{b}^{\text{\rm
red}},\mathbf{Q})=\text{\rm{QR-Compress}($\mathbf{W},\mathbf{b}$)}$ be the
output of Algorithm 1, so that $\mathbf{Q}\in O(\mathbf{n}^{\text{\rm hid}})$
and $(\mathbf{W}^{\text{\rm red}},\mathbf{b}^{\text{\rm
red}},\bm{\rho}^{\text{\rm red}})$ is a neural network with widths $n^{\rm
red}$ and radial rescaling activations $\rho_{i}^{\text{\rm
red}}=\rho_{i}\biggr{|}_{\mathbb{R}^{n^{\rm red}_{i}}}$. Let
$F=F_{(\mathbf{W},\mathbf{b},\bm{\rho})}$ denote the feedforward function of
the radial neural network with parameters $(\mathbf{W},\mathbf{b})$ and
activations $\bm{\rho}$. Similarly, let $F^{\text{\rm
red}}=F_{(\mathbf{W}^{\text{\rm red}},\mathbf{b}^{\text{\rm
red}},\bm{\rho}^{\rm red})}$ denote the feedforward function of the radial
neural network with parameters $(\mathbf{W}^{\text{\rm
red}},\mathbf{b}^{\text{\rm red}})$ and activations $\bm{\rho}^{\rm red}$.
Additionally, we have the partial feedforward functions $F_{i}$ and $F^{\rm
red}_{i}$. We show by induction that

$F_{i}=Q_{i}\circ\text{\rm inc}_{i}\circ F^{\rm red}_{i}$

for any $i=0,1,\dots,N$. (Continuing conventions from Sections 5.1 and 5.2, we
set $Q_{0}=\text{\rm id}_{\mathbb{R}^{n_{0}}}$, $Q_{L}=\text{\rm
id}_{\mathbb{R}^{n_{L}}}$, and $\text{\rm inc}_{i}:\mathbb{R}^{n^{\rm
red}_{i}}\to\mathbb{R}^{n_{i}}$ to be the inclusion map.) The base step $i=0$
immediate. For the induction step, let $x\in\mathbb{R}^{n_{0}}$. Then:

$\displaystyle F_{i}(x)$ $\displaystyle=\rho_{i}\left(W_{i}\circ
F_{i-1}(x)+b_{i}\right)$ $\displaystyle=\rho_{i}\left(W_{i}\circ
Q_{i-1}\circ\text{\rm inc}_{i-1}\circ F^{\rm red}_{i-1}(x)+b_{i}\right)$
$\displaystyle=\rho_{i}\left(\begin{bmatrix}b_{i}&W_{i}\circ
Q_{i-1}\circ\text{\rm inc}_{i-1}\end{bmatrix}\begin{bmatrix}1\\\ F^{\rm
red}_{i-1}(x)\end{bmatrix}\right)$
$\displaystyle=\rho_{i}\left(Q_{i}\circ\text{\rm
inc}_{i}\circ\begin{bmatrix}b_{i}^{\text{\rm red}}&W_{i}^{\text{\rm
red}}\end{bmatrix}\begin{bmatrix}1\\\ F^{\rm
red}_{i-1}(x)\end{bmatrix}\right)$ $\displaystyle=Q_{i}\circ\text{\rm
inc}_{i}\circ\rho_{i}\biggr{|}_{\mathbb{R}^{n^{\rm
red}_{i}}}\left(W_{i}^{\text{\rm red}}\circ F^{\rm
red}_{i-1}(x)+b_{i}^{\text{\rm red}}\right)$
$\displaystyle=Q_{i}\circ\text{\rm inc}_{i}\circ F^{\rm red}_{i}$

The first equality relies on the definition of the partial feedforward
function $F_{i}$; the second on the induction hypothesis; the fourth on an
inspection of Algorithm 1, noting that $R_{i}=[b_{i}^{\text{\rm red}}\
W_{i}^{\text{\rm red}}]$; the fifth on the results of Lemma 18, observing that
$\rho_{i}\circ\text{\rm inc}_{i}=\rho_{i}|_{\mathbb{R}^{n^{\rm
red}_{i}}}=\text{\rm inc}_{i}\circ\rho_{i}^{\text{\rm red}}$; and the sixth on
the definition of $F^{\rm red}_{i}$. In the case $i=L$, we have:

$F=F_{L}=Q_{L}\circ\text{\rm inc}_{L}\circ F^{\rm red}_{L}=F^{\rm red}$

since $Q_{L}=\text{\rm inc}_{L}=\text{\rm id}_{\mathbb{R}^{n_{L}}}$ and
$F^{\rm red}_{L}=F^{\rm red}$. The theorem now follows. ∎

The techniques of the above proof can be used to show that the action of the
group $O(\mathbf{n}^{\text{\rm hid}})$ of orthogonal change-of-basis
symmetries on the parameter space $\mathsf{Param}(\mathbf{n})$ leaves the
feedforward function unchanged. We do not use this result directly, but state
is precisely it nonetheless:

######  Proposition 19.

Let $(\mathbf{W},\mathbf{b},\bm{\rho})$ be a radial neural network with widths
vector $\mathbf{n}$. Suppose $\mathbf{g}\in O(\mathbf{n}^{\text{\rm hid}})$.
Then the original and transformed networks have the same feedforward function:

$F_{(\mathbf{g}\cdot\mathbf{W},\ \mathbf{g}\cdot\mathbf{b},\
\bm{\rho})}=F_{(\mathbf{W},\ \mathbf{b},\ \bm{\rho})}$

In other words, fix parameters
$(\mathbf{W},\mathbf{b})\in\mathsf{Param}(\mathbf{n})$, radial rescaling
activations $\bm{\rho}$, and $\mathbf{g}\in O(\mathbf{n}^{\text{\rm hid}})$.
Then the radial neural network with parameters $(\mathbf{W},\mathbf{b})$ has
the same feedforward function as the radial neural network with transformed
parameters $(\mathbf{g}\cdot\mathbf{W},\mathbf{g}\cdot\mathbf{b})$, where we
take radial rescaling activations $\bm{\rho}$ in both cases.

We remark that Proposition 19 is analogous to the “non-negative homogeneity”
(or “positive scaling invariance”) of the pointwise ReLU activation function
[Armenta et al., 2021, Dinh et al., 2017, Meng et al., 2019, Neyshabur et al.,
2015]. In that setting, instead of considering the product of orthogonal
groups $O(\mathbf{n}^{\text{\rm hid}})$, one considers the rescaling action of
the following subgroup of $\prod_{i=1}^{L-1}\mathrm{GL}_{n_{i}}$:

$G=\left\\{\mathbf{g}=(g_{i})\in\prod_{i=1}^{L-1}\mathrm{GL}_{n_{i}}\ |\
\text{ each $g_{i}$ is diagonal with positive diagonal entries}\right\\}$

Note that $G$ is isomorphic to the product
$\prod_{i=1}^{L-1}\mathbb{R}_{>0}^{n_{i}}$, and the action on
$\mathsf{Param}(\mathbf{n})$ is given by the same formulas as those appearing
near the end of Section 5.1. The feedforward function of a MLP with pointwise
ReLU activations is invariant for the action of $G$ on
$\mathsf{Param}(\mathbf{n})$.

##  Appendix D  Projected gradient descent proofs

In this section, we give a proof of Theorem 7, which relates projected
gradient descent for a representation with dimension $\mathbf{n}$ to (usual)
gradient descent for the corresponding reduced representation with dimension
vector $\mathbf{n}^{\text{\rm red}}$. This proof requires some set up and
background resutls.

###  D.1 Gradient descent and orthogonal symmetries

We first prove a result that gradient descent commutes with invariant
orthogonal transformations. This section is general and departs from the
specific case of radial neural networks.

####  D.1.1 Setting

Let $\mathcal{L}:V=\mathbb{R}^{p}\to\mathbb{R}$ be a smooth function.
Semantically, $V$ is a the parameter space of a neural network and
$\mathcal{L}$ the loss function with respect to a batch of training data. The
differential $d\mathcal{L}_{v}$ of $\mathcal{L}$ at $v\in V$ is row vector,
while the gradient $\nabla_{v}\mathcal{L}$ of $\mathcal{L}$ at $v$ is a column
vector333Following usual conventions, we regard column vectors as elements of
$V$ and row vectors as elements of the dual vector space $V^{*}$. The
differential $d\mathcal{L}_{v}$ of $\mathcal{L}$ at $v\in V$ is also known as
the Jacobian of $\mathcal{L}$ at $v\in V$.:

$\displaystyle
d\mathcal{L}_{v}=\begin{bmatrix}\frac{\partial\mathcal{L}}{\partial
x_{1}}\bigg{|}_{v}&\cdots&\frac{\partial\mathcal{L}}{\partial
x_{p}}\bigg{|}_{v}\end{bmatrix}\qquad\qquad\nabla_{v}\mathcal{L}=\begin{bmatrix}\frac{\partial\mathcal{L}}{\partial
x_{1}}\bigg{|}_{v}\\\ \vdots\\\ \frac{\partial\mathcal{L}}{\partial
x_{p}}\bigg{|}_{v}\end{bmatrix}$

Hence $\nabla_{v}\mathcal{L}$ is the transpose of $d\mathcal{L}_{v}$, that is:
$\nabla_{v}\mathcal{L}=(d\mathcal{L}_{v})^{T}$. A step of gradient descent
with respect to $\mathcal{L}$ at learning rate $\eta>0$ is defined as:

$\displaystyle\gamma=\gamma_{\eta}:V$ $\displaystyle\longrightarrow V$
$\displaystyle v$ $\displaystyle\longmapsto v-\eta\nabla_{v}\mathcal{L}$

We drop $\eta$ from the notation when it is clear from context. For any $k\geq
0$, we denote by $\gamma^{k}$ the $k$-fold composition of the gradient descent
map $\gamma$:

$\gamma^{k}=\overbrace{\gamma\circ\gamma\circ\cdots\circ\gamma}^{k}$

####  D.1.2 Invariant group action

Now suppose $\rho:G\to\mathrm{GL}(V)$ is an action of a Lie group $G$ on $V$
such that $\mathcal{L}$ is $G$-invariant, i.e.:

$\mathcal{L}(\rho(g)(v))=\mathcal{L}(v)$

for all $g\in G$ and $v\in V$. We write simply $g\cdot v$ for $\rho(g)(v)$,
and $g$ for $\rho(g)$.

######  Lemma 20.

For any $v\in V$ and $g\in G$, we have:

$\nabla_{v}\mathcal{L}=g^{T}\cdot(\nabla_{g\cdot v}\mathcal{L})$

###### Proof.

The proof is a computation:

$\displaystyle\nabla_{v}\mathcal{L}$
$\displaystyle=(d_{v}\mathcal{L})^{T}=(d(\mathcal{L}\circ
g)_{v})^{T}=(d\mathcal{L}_{g\cdot v}\circ dg_{v})^{T}=(d\mathcal{L}_{g\cdot
v}\circ g)^{T}=g^{T}\cdot(d\mathcal{L}_{g\cdot v})^{T}$
$\displaystyle=g^{T}\cdot(\nabla\mathcal{L}_{g\cdot v})$

The second equality relies on the hypothesis that $\mathcal{L}\circ
g=\mathcal{L}$, the third on the chain rule, and the fourth on the fact that
$dg_{v}=g$ since $g$ is a linear map. ∎

One can perform the computation of the proof in coordinates, for
$i=1,\dots,p$:

$\displaystyle\left(\nabla_{v}\mathcal{L}\right)_{i}$
$\displaystyle=\left(d\mathcal{L}_{v}\right)^{i}=\frac{\partial\mathcal{L}}{\partial
x_{i}}\biggr{|}_{v}=\frac{\partial(\mathcal{L}\circ g)}{\partial
x_{i}}\biggr{|}_{v}=\frac{\partial\mathcal{L}}{\partial
x_{j}}\biggr{|}_{gv}\frac{\partial g_{j}}{\partial x_{i}}\biggr{|}_{v}$
$\displaystyle=\left(\nabla_{gv}\mathcal{L}\right)_{j}g_{j}^{i}=(g^{T})^{j}_{i}\left(\nabla_{gv}\mathcal{L}\right)_{j}=\left(g^{T}\cdot\nabla_{gv}\mathcal{L}\right)_{i}$

####  D.1.3 Orthogonal case

Furthermore, suppose the action of $G$ is by orthogonal transformations, so
that $\rho(g)^{T}=\rho(g)^{-1}$ for all $g\in G$. Then Lemma 20 implies that

$\nabla_{g\cdot v}\mathcal{L}=g\cdot\nabla_{v}\mathcal{L}$ (D.1)

for any $v\in V$ and $g\in G$. The proof of the following lemma is immediate
from Equation D.1, together with the definition of $\gamma$. See Figure 5 for
an illustration.

Figure 5: Illustration of Lemma 21. If the loss is invariant with respect to
an orthogonal transformation $Q$ of the parameter space, then optimization of
the network by gradient descent is also invariant with respect to $Q$. (Note:
in this example, projected and usual gradient descent match; this is not the
case in higher dimensions, as explained in D.6.)

######  Lemma 21.

Suppose the action of $G$ on $V$ is by orthogonal transformations, and that
$\mathcal{L}$ is $G$-invariant. Then the action of $G$ commutes with gradient
descent (for any learning rate). That is,

$\gamma^{k}(g\cdot v)=g\cdot\gamma^{k}(v)$

for any $v\in V$, $g\in G$, and $k\geq 0$.

###  D.2 Gradient descent notation and set-up

We now turn our attention back to radial neural networks. In this section, we
recall notation from above, and introduce new notation that will be relevant
for the formulation and proof of Theorem 7.

####  D.2.1 Merging widths and biases

Let $\mathbf{n}=(n_{0},n_{1},n_{2},\dots,n_{L-1},n_{L})$ be the widths vector
of an MLP. Recall the definition of $\mathsf{Param}(\mathbf{n})$ as the
parameter space of all possible choices of trainable parameters:

$\mathsf{Param}(\mathbf{n})=\left(\mathbb{R}^{n_{1}\times
n_{0}}\times\mathbb{R}^{n_{2}\times
n_{1}}\times\cdots\times\mathbb{R}^{n_{L}\times
n_{L-1}}\right)\times\left(\mathbb{R}^{n_{1}}\times\mathbb{R}^{n_{2}}\times\cdots\times\mathbb{R}^{n_{L}}\right)$

We have been denoting an element therein as a pair of tuples
$(\mathbf{W},\mathbf{b})$ where $\mathbf{W}=(W_{i}\in\mathbb{R}^{n_{i}\times
n_{i-1}})_{i=1}^{L}$ are the weights and
$\mathbf{b}=(b_{i}\in\mathbb{R}^{n_{i}})_{i=1}^{L}$ are the biases. However,
in this appendix we adopt different notation. Observe that, placing each bias
vector as a extra column on the left of the weight matrix, we obtain matrices:

$A_{i}=[b_{i}\ W_{i}]\ \in\ \mathbb{R}^{n_{i}\times(1+n_{i-1})}.$

Thus, there is an isomorphism:

$\mathsf{Param}(\mathbf{n})\simeq\bigoplus_{i=1}^{L}\mathbb{R}^{n_{i}\times(n_{i-1}+1)}=\mathbb{R}^{n_{1}\times(n_{0}+1)}\times\mathbb{R}^{n_{2}\times(n_{1}+1)}\times\cdots\times\mathbb{R}^{n_{L}\times(n_{L-1}+1)}$

In this appendix, we regard an element of $\mathsf{Param}(\mathbf{n})$ as a
tuple of ‘merged’ matrices
$\mathbf{A}=(A_{i}\in\mathbb{R}^{n_{i}\times(1+n_{i-1})})_{i=1}^{L}$. We now
define convenient maps to translate between the merged notation and the split
notation. For each $i$, define the extension-by-one map from
$\mathbb{R}^{n_{i}}$ to
$\mathbb{R}\times\mathbb{R}^{n_{i}}\simeq\mathbb{R}^{n_{i}+1}$ as follows:

$\text{\rm ext}_{i}:\mathbb{R}^{n_{i}}\to\mathbb{R}^{n_{i}+1}\qquad
v=(v_{1},v_{2},\dots,v_{n_{i}})\mapsto(1,v_{1},v_{2},\dots,v_{n_{i}})$ (D.2)

Observe that, for any $i$ and $x\in\mathbb{R}^{n_{i-1}}$, we have

$A_{i}\circ\text{\rm ext}_{i-1}(x)=W_{i}x+b_{i}.$

Consequently, the $i$-th partial feedforward function can be defined
recursively as:

$F_{i}=\rho_{i}\circ A_{i}\circ\text{\rm ext}_{i-1}\circ F_{i-1}$ (D.3)

where $\rho_{i}:\mathbb{R}^{n_{i}}\to\mathbb{R}^{n_{i}}$ is the
activation444In this general formulation, $\rho_{i}$ can be any piece-wise
differentiable function; for most of the rest of the paper we will be
interested in the case where $\rho_{i}$ is a radial rescaling function. at the
$i$-th layer, and $F_{0}$ is the identity on $\mathbb{R}^{n_{0}}$.

####  D.2.2 Orthogonal change-of-basis action

To describe the orthogonal change-of-basis symmetries of the parameter space
in the merged notation, recall the following product of orthogonal groups,
with sizes corresponding to the widths of the hidden layers:

$O(\mathbf{n}^{\text{\rm hid}})=\mathcal{O}(n_{1})\times
O(n_{2})\times\cdots\times O(n_{L-1})$

In the merged notation, the element $\mathbf{Q}=(Q_{i})_{i=1}^{L-1}\in
O(\mathbf{n}^{\text{\rm hid}})$ transforms
$\mathbf{A}\in\mathsf{Param}(\mathbf{n})$ as:

$\mathbf{A}\quad\mapsto\quad\mathbf{Q}\cdot\mathbf{A}:=\left(Q_{i}\circ
A_{i}\circ\begin{bmatrix}1&0\\\ 0&Q_{i-1}^{-1}\end{bmatrix}\right)_{i=1}^{L}$
(D.4)

where $Q_{0}=\text{\rm id}_{n_{0}}$ and $Q_{L}=\text{\rm id}_{n_{L}}$.

####  D.2.3 Model compression algorithm

We now restate Algorithm 1 in the merged notation. We emphasize that
Algorithms 1 and 2 are mathematically equivalent; the later simply uses more
compact notation.

input : $\mathbf{A}\in\mathsf{Param}(\mathbf{n})$

output : $\mathbf{Q}\in O(\mathbf{n}^{\text{\rm hidden}})$ and
$\mathbf{V}\in\mathsf{Param}(\mathbf{n}^{\text{\rm red}})$

$\mathbf{Q},\mathbf{V}\leftarrow[\ ],[\ ]$

// initialize output matrix lists

$M_{1}\leftarrow A_{1}$

for  _$i\leftarrow 1$ to $L-1$ _ do

// iterate through layers

$Q_{i},R_{i}\leftarrow$ QR-decomp(_$M_{i}$ , mode = ‘complete’ _)

// $M_{i}=Q_{i}\circ\text{\rm inc}_{i}\circ R_{i}$

Append $Q_{i}$ to $\mathbf{Q}$

Append $R_{i}$ to $\mathbf{V}$

// reduced merged weights for layer $i$

Set $M_{i+1}\leftarrow A_{i+1}\circ\begin{bmatrix}1&0\\\ 0&Q_{i}\circ\text{\rm
inc}_{i}\end{bmatrix}\qquad\qquad$

// transform next layer

end for

Append $M_{L}$ to $\mathbf{V}$

return $\mathbf{Q}$, $\mathbf{V}$

Algorithm 2 QR Model Compression (QR-compress)

We explain the notation. As noted in Appendix B.1, the symbol ‘$\circ$’
denotes composition of maps, or matrix multiplication in the case of linear
maps. The standard inclusion ${\text{\rm inc}}_{i}:\mathbb{R}^{n^{\rm
red}_{i}}\hookrightarrow\mathbb{R}^{n_{i}}$ maps into the first $n^{\rm
red}_{i}$ coordinates. As a matrix, $\text{\rm
Inc}_{i}\in\mathbb{R}^{n_{i}\times n^{\rm red}_{i}}$ has ones along the main
diagonal and zeros elsewhere. The method QR-decomp with mode = ‘complete’
computes the complete QR decomposition of the $n_{i}\times(1+n^{\rm
red}_{i-1})$ matrix $M_{i}$ as $Q_{i}\circ\text{\rm inc}_{i}\circ R_{i}$ where
$Q_{i}\in O(n_{i})$ and $R_{i}$ is upper-triangular of size $n^{\rm
red}_{i}\times(1+n^{\rm red}_{i-1})$. The definition of $n^{\rm red}_{i}$
implies that either $n^{\rm red}_{i}=n^{\rm red}_{i-1}+1$ or $n^{\rm
red}_{i}=n_{i}$. The matrix $R_{i}$ is of size $n^{\rm red}_{i}\times n^{\rm
red}_{i}$ in the former case and of size $n_{i}\times(1+n^{\rm red}_{i-1})$ in
the latter case.

####  D.2.4 Gradient descent definitions

As in Section 6, we fix:

  * •

a widths vector $\mathbf{n}=(n_{0},n_{1},\dots,n_{L})$.

  * •

a tuple $\bm{\rho}=(\rho_{1},\dots,\rho_{L})$ of radial rescaling activations,
where $\rho_{i}:\mathbb{R}^{n_{i}}\to\mathbb{R}^{n_{i}}$ for $i=1,\dots,L$.

  * •

a batch of training data
$\\{(x_{j},y_{j})\\}\subseteq\mathbb{R}^{n_{0}}\times\mathbb{R}^{n_{L}}=\mathbb{R}^{n^{\rm
red}_{0}}\times\mathbb{R}^{n^{\rm red}_{L}}$.

  * •

a cost function
$\mathcal{C}:\mathbb{R}^{n_{L}}\times\mathbb{R}^{n_{L}}\to\mathbb{R}$

As a result, we have a loss function on $\mathsf{Param}(\mathbf{n})$:

$\mathcal{L}:\mathsf{Param}(\mathbf{n})\rightarrow\mathbb{R}\qquad\qquad\mathcal{L}(\mathbf{A})=\sum\mathcal{C}(F_{(\mathbf{A},\bm{\rho})}(x_{j}),y_{j})$

where $F_{(\mathbf{A},\bm{\rho})}$ is the feedforward of the radial neural
network with (merged) parameters $\mathbf{A}$ and activations $\bm{\rho}$. We
emphasize that the loss function $\mathcal{L}$ depends on the batch of
training data chosen above; however, for clarity, we omit extra notation
indicating this dependency since the batch of training data is fixed
throughout this discussion. Similarly, we have:

  * •

the reduced widths vector $\mathbf{n}^{\text{\rm red}}=(n^{\rm red}_{0},n^{\rm
red}_{1},\dots,n^{\rm red}_{L})$.

  * •

the restrictions $\bm{\rho}^{\rm red}=(\rho^{\rm red}_{1},\dots,\rho^{\rm
red}_{L})$, where $\rho^{\rm red}_{i}:\mathbb{R}^{n^{\rm
red}_{i}}\to\mathbb{R}^{n^{\rm red}_{i}}$ for $i=1,\dots,L$.

Using the fact that $n^{\rm red}_{0}=n_{0}$ and $n^{\rm red}_{L}=n_{L}$, there
is a loss function on $\mathsf{Param}(\mathbf{n}^{\text{\rm red}})$:

$\mathcal{L}_{\text{\rm red}}:\mathsf{Param}(\mathbf{n}^{\text{\rm
red}})\rightarrow\mathbb{R}\qquad\qquad\mathcal{L}_{\text{\rm
red}}(\mathbf{B})=\sum\mathcal{C}(F_{(\mathbf{B},\bm{\rho}^{\rm
red})}(x_{j}),y_{j})$

where $F_{(\mathbf{B},\bm{\rho}^{\rm red})}$ is the feedforward of the radial
neural network with parameters
$\mathbf{B}\in\mathsf{Param}(\mathbf{n}^{\text{\rm red}})$ and activations
$\bm{\rho}^{\rm red}$. (Again, technically speaking, the loss function
$\mathcal{L}_{\text{\rm red}}$ depends on the batch of training data fixed
above.) For any learning rate $\eta>0$, we obtain a gradient descent maps:

$\displaystyle\gamma:\mathsf{Param}(\mathbf{n})$
$\displaystyle\to\mathsf{Param}(\mathbf{n})\qquad$
$\displaystyle\gamma_{\text{\rm red}}:\mathsf{Param}(\mathbf{n}^{\text{\rm
red}})$ $\displaystyle\to\mathsf{Param}(\mathbf{n}^{\text{\rm red}})$
$\displaystyle\mathbf{A}$
$\displaystyle\mapsto\mathbf{A}-\eta\nabla_{\mathbf{A}}\mathcal{L}\qquad$
$\displaystyle\mathbf{B}$
$\displaystyle\mapsto\mathbf{B}-\eta\nabla_{\mathbf{B}}\mathcal{L}_{\text{\rm
red}}$

###  D.3 The interpolating space

In this section, we introduce a subspace $\mathsf{Param}^{\text{\rm
int}}(\mathbf{n})$ of $\mathsf{Param}(\mathbf{n})$, that, as we will later
see, interpolates between $\mathsf{Param}(\mathbf{n})$ and
$\mathsf{Param}(\mathbf{n}^{\text{\rm red}})$.

Let $\mathsf{Param}^{\text{\rm int}}(\mathbf{n})$ denote the subspace of
$\mathsf{Param}(\mathbf{n})$ consisting of those
$\mathbf{T}=(T_{1},\dots,T_{L})\in\mathsf{Param}(\mathbf{n})$ for which the
bottom left $(n_{i}-n^{\rm red}_{i})\times(1+n^{\rm red}_{i-1})$ block of
$T_{i}$ is zero for each $i$. Schematically:

$T_{i}=\begin{bmatrix}*&*\\\ 0&*\end{bmatrix}$

where the rows are divided as $n^{\rm red}_{i}$ on top and $n_{i}-n^{\rm
red}_{i}$ on the bottom, while the columns are divided as $(1+n^{\rm
red}_{i-1})$ on the left and $n_{i-1}-n^{\rm red}_{i-1}$ on the right. Let

$\iota_{1}:\mathsf{Param}^{\text{\rm
int}}(\mathbf{n})\hookrightarrow\mathsf{Param}(\mathbf{n})$

be the inclusion. The following proposition follows from an elementary
analysis of the workings of Algorithm 2 (or, equivalently, Algorithm 1).

######  Proposition 22.

Let $\mathbf{A}\in\mathsf{Param}(\mathbf{n})$ and let $\mathbf{Q}\in
O(\mathbf{n}^{\text{\rm hid}})$ be the tuple of orthogonal matrices produced
by Algorithm 2. Then $\mathbf{Q}^{-1}\cdot\mathbf{A}$ belongs to
$\mathsf{Param}^{\text{\rm int}}(\mathbf{n})$.

Define a map

$q_{1}:\mathsf{Param}(\mathbf{n})\to\mathsf{Param}^{\text{\rm
int}}(\mathbf{n})$

by taking $\mathbf{A}\in\mathsf{Param}(\mathbf{n})$ and zeroing out the bottom
left $(n_{i}-n^{\rm red}_{i})\times(1+n^{\rm red}_{i-1})$ block of $A_{i}$ for
each $i$. Schematically:

$\mathbf{A}=\left(A_{i}=\begin{bmatrix}*&*\\\
*&*\end{bmatrix}\right)_{i=1}^{L}\ \mapsto\
q_{1}(\mathbf{A})=\left(\begin{bmatrix}*&*\\\
0&*\end{bmatrix}\right)_{i=1}^{L}$

It is straightforward to check that $q_{1}$ is a well-defined, surjective
linear map. The transpose of $q_{1}$ is the inclusion $\iota_{1}$. We
summarize the situation in the following diagram:

$\textstyle{\mathsf{Param}^{\text{\rm
int}}(\mathbf{n})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{1}}$$\textstyle{\mathsf{Param}(\mathbf{n})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{q_{1}}$
(D.5)

We observe that the composition $q_{1}\circ\iota$ is the identity on
$\mathsf{Param}^{\text{\rm int}}(\mathbf{n})$.

###  D.4 Projected gradient descent and model compression

Recall from Section 6 that the projected gradient descent map on
$\mathsf{Param}(\mathbf{n})$ is given by:

$\displaystyle\gamma_{\text{\rm
proj}}:\mathsf{Param}(\mathbf{n})\to\mathsf{Param}(\mathbf{n}),\qquad\mathbf{A}\mapsto\mathrm{Proj}\left(\mathbf{A}-\eta\nabla_{\mathbf{A}}\mathcal{L}\right)$

where $\mathbf{A}=(\mathbf{W},\mathbf{b})$ are the merged parameters (Appendix
D.2), and, in the notation of the previous section, the map $\mathrm{Proj}$ is
$\iota_{1}\circ q_{1}$. To reiterate, while all entries of each weight matrix
and each bias vector contribute to the computation of the gradient
$\nabla_{\mathbf{A}}\mathcal{L}=\nabla_{(\mathbf{W},\mathbf{b})}\mathcal{L}$,
only those not in the bottom left submatrix get updated under the projected
gradient descent map $\gamma_{\text{\rm proj}}$.

Let $\mathbf{V},\mathbf{Q}=\texttt{QR-Compress}(\mathbf{A})$ be the outputs of
Algorithm 2 (which is equivalent to Algorithm 1), so that
$\mathbf{V}=(\mathbf{W}^{\text{\rm red}},\mathbf{b}^{\text{\rm
red}})\in\mathsf{Param}(\mathbf{n}^{\text{\rm red}})$ are the parameters of
the compressed model corresponding to the full model with merged parameters
$\mathbf{A}=(\mathbf{W},\mathbf{b})$, and $\mathbf{Q}\in
O(\mathbf{n}^{\text{\rm hid}})$ is an orthogonal change-of-basis symmetry of
the parameter space. Moreover, set
$\mathbf{T}=\mathbf{Q}^{-1}\cdot\mathbf{A}\in\mathsf{Param}^{\text{\rm
int}}(\mathbf{n})$, where we use the change-of-basis action from Appendix D.2
and Proposition 22. We have the following rephrasing of Theorem 7.

######  Theorem 23 (Theorem 7).

Let $\mathbf{A}\in\mathsf{Param}(\mathbf{n})$, and let
$\mathbf{V},\mathbf{Q},\mathbf{T}$ be as above. For any $k\geq 0$:

  1. 1.

$\gamma^{k}(\mathbf{A})=\mathbf{Q}\cdot\gamma^{k}(\mathbf{T})$

  2. 2.

$\gamma_{\text{\rm proj}}^{k}(\mathbf{T})=\gamma_{\text{\rm
red}}^{k}(\mathbf{V})+\mathbf{T}-\mathbf{V}.$

More precisely, the second equality is $\gamma_{\text{\rm
proj}}^{k}(\mathbf{T})=\iota(\gamma_{\text{\rm
red}}^{k}(\mathbf{V}))+\mathbf{T}-\iota(\mathbf{V})$ where
$\iota:\mathsf{Param}(\mathbf{n}^{\text{\rm
red}})\hookrightarrow\mathsf{Param}(\mathbf{n})$ is the inclusion into the top
left corner in each coordinate. Also, in the statement of Theorem 7, we have
$\mathbf{U}=\mathbf{T}-\mathbf{V}$.

We summarize this result in the following diagram. The left horizontal maps
indicate the addition of $\mathbf{U}=\mathbf{T}-\mathbf{V}$, the right
horizontal arrows indicate the action of $\mathbf{Q}$, and the vertical maps
are various versions of gradient descent. The shaded regions indicate the
(smallest) vector space to which the various representations naturally belong.

${\mathbf{V}}$${\mathbf{T}}$${\mathbf{W}}$${\gamma_{\text{\rm
red}}^{k}(\mathbf{V})}$${\gamma_{\text{\rm
proj}}^{k}(\mathbf{T})}$${\gamma^{k}(\mathbf{T})}$${\gamma^{k}(\mathbf{W})}$$+\mathbf{T}-\mathbf{V}$proj-
GD on $\mathsf{Param}(\mathbf{n})$$+\mathbf{T}-\mathbf{V}$GD on
$\mathsf{Param}(\mathbf{n}^{\text{\rm red}})$GD on
$\mathsf{Param}(\mathbf{n})$$\mathbf{Q}\cdot$$\mathbf{Q}\cdot$GD on
$\mathsf{Param}(\mathbf{n})$$\mathsf{Param}(\mathbf{n}^{\text{\rm
red}})$$\mathsf{Param}^{\text{\rm
int}}(\mathbf{n})$$\mathsf{Param}(\mathbf{n})$

###  D.5 Proof of Theorem 7

We begin by explaining the sense in which $\mathsf{Param}^{\text{\rm
int}}(\mathbf{n})$ interpolates between $\mathsf{Param}(\mathbf{n})$ and
$\mathsf{Param}(\mathbf{n}^{\text{\rm red}})$. One extends Diagram D.5 as
follows:

$\textstyle{\mathsf{Param}(\mathbf{n}^{\text{\rm
red}})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{2}}$$\textstyle{\mathsf{Param}^{\text{\rm
int}}(\mathbf{n})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{q_{2}}$$\scriptstyle{\iota_{1}}$$\textstyle{\mathsf{Param}(\mathbf{n})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{q_{1}}$

  * •

The map

$\iota_{2}:\mathsf{Param}(\mathbf{n}^{\text{\rm
red}})\hookrightarrow\mathsf{Param}^{\text{\rm int}}(\mathbf{n})$

takes $\mathbf{B}=(B_{i})\in\mathsf{Param}(\mathbf{n}^{\text{\rm red}})$ and
pad each matrix with $n_{i}-n^{\rm red}_{i}$ rows of zeros on the bottom and
$n_{i-1}-n^{\rm red}_{i-1}$ columns of zeros on the right:

$\mathbf{B}=\left(B_{i}\right)_{i=1}^{L}\ \mapsto\
\iota_{2}(\mathbf{B})=\left(\begin{bmatrix}B_{i}&0\\\
0&0\end{bmatrix}\right)_{i=1}^{L}$

It is straightforward to check that $\iota_{2}$ is a well-defined injective
linear map.

  * •

The map

$q_{2}:\mathsf{Param}^{\text{\rm
int}}(\mathbf{n})\twoheadrightarrow\mathsf{Param}(\mathbf{n}^{\text{\rm
red}})$

extracts from $\mathbf{T}$ the top left $n^{\rm red}_{i}\times(1+n^{\rm
red}_{i-1})$ matrix:

$\mathbf{T}=\left(T_{i}=\begin{bmatrix}T_{i}^{(1)}&T_{i}^{(2)}\\\
0&T_{i}^{(4)}\end{bmatrix}\right)_{i=1}^{L}\ \mapsto\
q_{2}(\mathbf{T})=\left(T_{i}^{(1)}\right)_{i=1}^{L}$

It is straightforward to check that $q_{2}$ is a surjective linear map. The
transpose of $q_{2}$ is the inclusion $\iota_{2}$.

######  Lemma 24.

We have the following:

  1. 1.

The inclusion $\iota:\mathsf{Param}(\mathbf{n}^{\text{\rm
red}})\hookrightarrow\mathsf{Param}(\mathbf{n})$ coincides with the
composition $\iota_{1}\circ\iota_{2}$, and commutes with the loss functions:

$\textstyle{\mathsf{Param}(\mathbf{n}^{\text{\rm
red}})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{1}\circ\iota_{2}=\iota}$$\scriptstyle{\mathcal{L}_{\text{\rm
red}}}$$\textstyle{\mathsf{Param}(\mathbf{n})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathcal{L}}$$\textstyle{\mathbb{R}}$

  2. 2.

The following diagram commutes:

$\textstyle{\mathsf{Param}^{\text{\rm
int}}(\mathbf{n})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{q_{2}}$$\scriptstyle{\iota_{1}}$$\textstyle{\mathsf{Param}(\mathbf{n}^{\text{\rm
red}})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{{\mathcal{L}}_{\text{\rm
red}}}$$\textstyle{\mathsf{Param}(\mathbf{n})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathcal{L}}$$\textstyle{\mathbb{R}}$

  3. 3.

For any $\mathbf{T}\in\mathsf{Param}^{\text{\rm int}}(\mathbf{n})$, we have:
$q_{1}\left(\nabla_{\iota_{1}(\mathbf{T})}{\mathcal{L}}\right)=\iota_{2}\left(\nabla_{q_{2}(\mathbf{T})}{\mathcal{L}}_{\text{\rm
red}}\right).$

###### Proof.

We have the following standard inclusions into the first coordinates and
projections onto the first coordinates, for $i=0,1,\dots,L$:

${\text{\rm inc}}_{i}=\text{\rm inc}_{n^{\rm
red}_{i},n_{i}}:\mathbb{R}^{n^{\rm
red}_{i}}\hookrightarrow\mathbb{R}^{n_{i}},\qquad\widetilde{\text{\rm
inc}}_{i}=\text{\rm inc}_{1+n^{\rm red}_{i},1+n_{i}}:\mathbb{R}^{1+n^{\rm
red}_{i}}\hookrightarrow\mathbb{R}^{1+n_{i}},$
$\pi_{i}:\mathbb{R}^{n_{i}}\twoheadrightarrow\mathbb{R}^{n^{\rm
red}_{i}},\qquad\qquad\widetilde{\pi}_{i}:\mathbb{R}^{1+n_{i}}\twoheadrightarrow\mathbb{R}^{1+n^{\rm
red}_{i}}.$

Observe that $\mathsf{Param}^{\text{\rm int}}(\mathbf{n})$ is the subspace of
$\mathsf{Param}(\mathbf{n})$ consisting of those
$\mathbf{T}=(T_{1},\dots,T_{L})\in\mathsf{Param}(\mathbf{n})$ such that:

$\left(\text{\rm id}_{n_{i}}-\text{\rm inc}_{i}\circ\pi_{i}\right)\circ
T_{i}\circ\widetilde{\text{\rm inc}}_{i-1}\circ\widetilde{\pi}_{i-1}=0$

for $i=1,\dots,L$.

By the definition of radial rescaling functions, for each $i=1,\dots,L$, there
is a piece-wise differentiable function $h_{i}:\mathbb{R}\to\mathbb{R}$ such
that $\rho_{i}=h_{i}^{(n_{i})}$. Note that $\rho^{\rm red}_{i}=h_{i}^{(n^{\rm
red}_{i})}$, and $h^{(n_{i})}\circ\text{\rm inc}_{i}=\text{\rm inc}_{i}\circ
h^{(n^{\rm red}_{i})}$.

The identity $\iota=\iota_{1}\circ\iota_{2}$ follows directly from
definitions. To prove the commutativity of the first diagram, it is enough to
show that, for any $\mathbf{X}$ in $\mathsf{Param}(\mathbf{n}^{\text{\rm
red}})$, the feedforward functions of $\mathbf{X}$ and $\iota(\mathbf{X})$
coincide. This follows easily from the fact that, for $i=1,\dots,L$, we have:

${\pi}_{i}\circ h^{(n_{i})}\circ\text{\rm inc}_{i}={\pi}_{i}\circ\text{\rm
inc}_{i}\circ h^{(n^{\rm red}_{i})}=h^{(n^{\rm red}_{i})}.$

For the second claim, let $\mathbf{T}\in\mathsf{Param}^{\text{\rm
int}}(\mathbf{n})$. It suffices to show that $\iota_{1}(\mathbf{T})$ and
$q_{2}(\mathbf{T})$ have the same feedforward function. Recall the $\text{\rm
ext}_{i}$ maps and the formulation of the feedforward function in the merged
notation given in Equation D.3. Using this set-up, the key computation is:

$\displaystyle\text{\rm inc}_{i}\circ h^{(n^{\rm
red}_{i})}\circ\pi_{i}\circ{T}_{i}\circ\text{\rm ext}_{n_{i-1}}\circ{\text{\rm
inc}}_{i-1}$ $\displaystyle=h^{(n_{i})}\circ\text{\rm
inc}_{i}\circ\pi_{i}\circ{T}_{i}\circ\widetilde{\text{\rm
inc}}_{i-1}\circ\text{\rm ext}_{n_{i-1}}$
$\displaystyle=h^{(n_{i})}\circ{T}_{i}\circ\widetilde{\text{\rm
inc}}_{i-1}\circ\text{\rm ext}_{n_{i-1}}$
$\displaystyle=h^{(n_{i})}\circ{T}_{i}\circ\text{\rm
ext}_{n_{i-1}}\circ{\text{\rm inc}}_{i-1}$

which uses the fact that $\left(\text{\rm id}_{n_{i}}-\text{\rm
inc}_{i}\circ\pi_{i}\right)\circ T_{i}\circ\widetilde{\text{\rm
inc}}_{i-1}=0$, or, equivalently, $\text{\rm inc}_{i}\circ\pi_{i}\circ
T_{i}\circ\widetilde{\text{\rm inc}}_{i-1}=T_{i}\circ\widetilde{\text{\rm
inc}}_{i-1}$, as well as the fact that $\text{\rm ext}_{i}\circ\text{\rm
inc}_{i}=\widetilde{\text{\rm inc}}_{i}\circ\text{\rm ext}_{i}$. Applying this
relation successively starting with the second-to-last layer $(i=L-1)$ and
ending in the first $(i=1)$, one obtains the result. For the last claim, one
computes $\nabla_{\mathbf{T}}({\mathcal{L}}\circ\iota_{1})$ in two different
ways. The first way is:

$\displaystyle\nabla_{\mathbf{T}}({\mathcal{L}}\circ\iota_{1})$
$\displaystyle=\left(d({\mathcal{L}}_{\mathbf{T}}\circ\iota_{1})\right)^{T}=\left(d{\mathcal{L}}_{\iota_{1}(\mathbf{T})}\circ
d_{\mathbf{T}}\iota_{1}\right)^{T}=\left(d{\mathcal{L}}_{\iota_{1}(\mathbf{T})}\circ\iota_{1}\right)^{T}$
$\displaystyle=\iota_{1}^{T}\left(d{\mathcal{L}}_{\iota_{1}(\mathbf{T})}^{T}\right)=q_{1}\left(\nabla_{\iota_{1}(\mathbf{T})}{\mathcal{L}}\right)$

where we use the fact that $\iota_{1}$ is a linear map whose transpose is
$q_{1}$. The second way uses the commutative diagram of the second part of the
Lemma:

$\displaystyle\nabla_{\mathbf{T}}({\mathcal{L}}\circ\iota_{1})$
$\displaystyle=\nabla_{\mathbf{T}}\left({\mathcal{L}}_{\text{\rm red}}\circ
q_{2}\right)=\left(d\left({\mathcal{L}}_{\text{\rm
red}}\right)_{\mathbf{T}}\circ
q_{2}\right)^{T}=\left(d\left(\mathcal{L}_{\text{\rm
red}}\right)_{q_{2}(\mathbf{T})}\circ
d\left(q_{2}\right)_{\mathbf{Z}}\right)^{T}$
$\displaystyle=\left(d\left({\mathcal{L}}_{\text{\rm
red}}\right)_{q_{2}(\mathbf{T})}\circ
q_{2}\right)^{T}=q_{2}^{T}\left(d\left({\mathcal{L}}_{\text{\rm
red}}\right)_{q_{2}(\mathbf{T})}^{T}\right)=\iota_{2}\left(\nabla_{q_{2}(\mathbf{T})}{\mathcal{L}}_{\text{\rm
red}}\right).$

We also use the fact that $q_{2}$ is a linear map whose transpose is
$\iota_{2}$. ∎

###### Proof of Theorem 7.

As above, let $\mathbf{R},\mathbf{Q}=\texttt{QR-compress}(\mathbf{A})$ be the
outputs of Algorithm 1, so that $\mathbf{V}=(\mathbf{W}^{\text{\rm
red}},\mathbf{b}^{\text{\rm red}})\in\mathsf{Param}(\mathbf{n}^{\text{\rm
red}})$ is the dimensional reduction of the merged parameters
$\mathbf{A}=(\mathbf{W},\mathbf{b})$, and $\mathbf{Q}\in
O(\mathbf{n}^{\text{\rm hid}})$. Set
$\mathbf{T}=\mathbf{Q}^{-1}\cdot\mathbf{A}\in\mathsf{Param}^{\text{\rm
int}}(\mathbf{n})$.

The action of $\mathbf{Q}\in O(\mathbf{n}^{\text{\rm hid}})$ on
$\mathsf{Param}(\mathbf{n})$ is an orthogonal transformation, so the first
claim follows from Lemma 21.

For the second claim, it suffices to consider the case $\eta=1$. The general
case follows similarly. We proceed by induction. The base case $k=0$ amounts
to Theorem 5. For the induction step, we set

$\mathbf{Z}^{(k)}=\iota(\gamma_{\text{\rm
red}}^{k}(\mathbf{V}))+\mathbf{T}-\iota(\mathbf{V}).$

Each $\mathbf{Z}^{(k)}$ belongs to $\mathsf{Param}^{\text{\rm
int}}(\mathbf{n})$, so $i_{1}(\mathbf{Z}^{(k)})=\mathbf{Z}^{(k)}$. Moreover,
$q_{2}\left(\mathbf{Z}^{(k)}\right)=\gamma_{\text{\rm red}}^{k}(\mathbf{V})$.
We compute:

$\displaystyle\gamma_{\text{\rm proj}}^{k+1}(\mathbf{Q}^{-1}\cdot\mathbf{A})$
$\displaystyle=\gamma_{\text{\rm proj}}\left(\gamma_{\text{\rm
proj}}^{k}(\mathbf{Q}^{-1}\cdot\mathbf{A})\right)$
$\displaystyle=\gamma_{\text{\rm proj}}\left(\iota(\gamma_{\text{\rm
red}}^{k}(\mathbf{V}))+\mathbf{T}-\iota(\mathbf{V})\right)$
$\displaystyle=\iota_{1}\circ q_{1}\left(\iota(\gamma_{\text{\rm
red}}^{k}(\mathbf{V}))+\mathbf{T}-\iota(\mathbf{V})-\nabla_{\iota(\gamma_{\text{\rm
red}}^{k}(\mathbf{V}))+\mathbf{T}-\iota(\mathbf{V})}{\mathcal{L}}\right)$
$\displaystyle=\iota(\gamma_{\text{\rm red}}^{k}(\mathbf{V}))-\iota_{1}\circ
q_{1}\left(\nabla_{\iota_{1}(\mathbf{Z}^{(k)})}{\mathcal{L}}\right)+\mathbf{T}-\iota(\mathbf{V})$
$\displaystyle=\iota(\gamma_{\text{\rm
red}}^{k}(\mathbf{V}))-\iota_{1}\circ\iota_{2}\left(\nabla_{q_{2}(\mathbf{Z}^{(k)})}{\mathcal{L}}_{\text{\rm
red}}\right)+\mathbf{T}-\iota(\mathbf{V})$
$\displaystyle=\iota\left(\gamma_{\text{\rm
red}}^{k}(\mathbf{V})-\nabla_{\gamma_{\text{\rm
red}}^{k}(\mathbf{V})}{\mathcal{L}}_{\text{\rm
red}}\right)+\mathbf{T}-\iota(\mathbf{V})$
$\displaystyle=\iota\left(\gamma_{\text{\rm
red}}^{k+1}(\mathbf{V})\right)+\mathbf{T}-\iota(\mathbf{V})$

where the second equality uses the induction hypothesis; the third invokes the
definition of ${\gamma}_{\text{\rm proj}}$; the fourth uses the fact that
$\mathbf{Z}^{(k)}=\iota(\gamma_{\text{\rm
red}}^{k}(\mathbf{V}))+\mathbf{T}-\iota(\mathbf{V})$ belongs to
$\mathsf{Param}^{\text{\rm int}}(\mathbf{n})$; the fifth and sixth use Lemma
24 above; and the last uses the definition of $\gamma_{\text{\rm red}}$. ∎

###  D.6 Example

We now discuss an example where projected gradient descent does not match
usual gradient descent.

Let $\mathbf{n}=(1,3,1)$ be a widths vector. The space of parameters with this
widths vector is 10-dimensional:

$\mathsf{Param}(\mathbf{n})=\mathrm{Hom}(\mathbb{R}^{2},\mathbb{R}^{3})\oplus\mathrm{Hom}(\mathbb{R}^{4},\mathbb{R})\simeq\mathbb{R}^{10}.$

We identify a choice of parameters (in the merged notation)

$\mathbf{A}=\left(\ A_{1}=\begin{bmatrix}a&b\\\ c&d\\\ e&f\end{bmatrix}\ ,\
A_{2}=\begin{bmatrix}g&h&i&j\end{bmatrix}\right)\in\mathsf{Param}((1,3,1))$
(D.6)

with the point $p=(a,b,c,d,e,f,g,h,i,j)$ in $\mathbb{R}^{10}$. To be even more
explicit, the weights for the first layer are $W_{1}=\begin{bmatrix}b\\\ d\\\
f\end{bmatrix}$, the bias in the first hidden hidden layer is $b_{1}=(a,c,e)$,
the weights for the second layer are
$W_{2}=\begin{bmatrix}h&i&j\end{bmatrix}$, and the bias for the output layer
is $b_{2}=g$.

The action of the orthogonal group $O(\mathbf{n})=O(3)$ on
$\mathsf{Param}(\mathbf{n})\simeq\mathbb{R}^{10}$ can be expressed as:

$Q\mapsto\begin{bmatrix}Q&0&0&0\\\ 0&Q&0&0\\\ 0&0&1&0\\\
0&0&0&Q\end{bmatrix},$

where the rows and columns are divided according to the partition
$3+3+1+3=10$. Consider the function555 For
$\mathbf{A}\in\mathsf{Param}(\mathbf{n})$, the neural function of the neural
network with affine maps determined by $\mathbf{A}$ and identity activation
functions is $\mathbb{R}\to\mathbb{R}$; $x\mapsto\mathcal{L}(\mathbf{W})x$.
The function $\mathcal{L}$ can appear as a loss function for certain batches
of training data and cost function on $\mathbb{R}$.:

$\displaystyle\mathcal{L}:\mathsf{Param}(\mathbf{n})$
$\displaystyle\to\mathbb{R}$ $\displaystyle p=(a,b,c,d,e,f,g,h,i,j)$
$\displaystyle\mapsto h(a+b)+i(c+d)+j(e+f)+g$

By the product rule, we have:

$\nabla_{p}{\mathcal{L}}=(h,h,i,i,j,j,1,a+b,c+d,e+f)$

One easily checks that $\mathcal{L}(Q\cdot p)=\mathcal{L}(p)$ and that
$\nabla_{Q\cdot p}{\mathcal{L}}=Q\cdot\nabla_{p}{\mathcal{L}}$ for any $Q\in
O(3)$.

The interpolating space is the eight-dimensional subspace of
$\mathsf{Param}(\mathbf{n})\simeq\mathbb{R}^{10}$ with $e=f=0$ (using the
notation of Equation D.6). Suppose $p^{\prime}=(a,b,c,d,0,0,g,h,i,j)$ belongs
to the interpolating space. Then the gradient is

$\nabla_{p^{\prime}}\mathcal{L}=(h,h,i,i,j,j,1,a+b,c+d,0)$

which does not belong to the interpolating space. So one step of usual
gradient descent, with learning rate $\eta>0$ yields:

$\displaystyle\gamma:$ $\displaystyle p^{\prime}=(a,b,c,d,0,0,g,h,i,j)\mapsto$
$\displaystyle(a-\eta h\ ,\ b-\eta h\ ,\ c-\eta i\ ,\ d-\eta i\ ,\ -\eta j\ ,\
-\eta j\ ,\ g-\eta\ ,\ h-\eta(a+b)\ ,\ i-\eta(c+d)\ ,\ j)$

On the other hand, one step of projected gradient descent yields:

$\displaystyle\gamma_{\text{\rm proj}}:p^{\prime}$
$\displaystyle=(a,b,c,d,0,0,g,h,i,j)\mapsto$ $\displaystyle(a-\eta h\ ,\
b-\eta h\ ,\ c-\eta i\ ,\ d-\eta i\ ,\ 0\ ,\ 0\ ,\ g-\eta\ ,\ h-\eta(a+b)\ ,\
i-\eta(c+d)\ ,\ j)$

Direct computation shows that the difference between the evaluation of
$\mathcal{L}$ after one step of gradient descent and the evaluation of
$\mathcal{L}$ after one step of projected gradient descent is:

$\mathcal{L}(\gamma(p^{\prime}))-\mathcal{L}(\gamma_{\text{\rm
proj}}(p^{\prime}))=2\eta j^{2}.$

##  Appendix E Experiments

As mentioned in Section 7, we provide an implementation of Algorithm 1 in
order to (1) empirically validate that our implementation satisfies the claims
of Theorems 5 and Theorem 7 and (2) quantify real-world performance. Our
implementation uses a generalization of radial neural networks, which we
explain presently.

###  E.1 Radial neural networks with shifts

In this section, we consider radial neural networks with an extra trainable
parameter in each layer that shifts the radial rescaling activation. Adding
such parameters allows for more flexibility in the model, and (as shown in
Theorem 25) the model compression of Theorem 5 holds for such networks. It is
this generalization that we use in our experiments.

Let $h:\mathbb{R}\to\mathbb{R}$ be a function. For any $n\geq 1$ and any
$t\in\mathbb{R}$, the corresponding shifted radial rescaling function on
$\mathbb{R}^{n}$ is given by:

$\rho=h^{(n,t)}:v\mapsto\frac{h(\lvert v\rvert-t)}{|v|}v$

if $v\neq 0$ and $\rho(0)=0$. A radial neural network with shifts consists of
the following data:

  1. 1.

Hyperparameters: A positive integer $L$ and a widths vector
$\mathbf{n}=(n_{0},n_{1},n_{2},\dots,n_{L})$.

  2. 2.

Trainable parameters:

    1. (a)

A choice of weights and biases
$(\mathbf{W},\mathbf{b})\in\mathsf{Param}(\mathbf{n}).$

    2. (b)

A vector of shifts $\mathbf{t}=(t_{1},t_{2},\dots,t_{L})\in\mathbb{R}^{L}$.

  3. 3.

Activations: A tuple $\mathbf{h}=(h_{1},\dots,h_{L})$ of piecewise
differentiable functions $\mathbb{R}\to\mathbb{R}$. Together with the shifts,
we have the shifted radial rescaling activation
$\rho_{i}=h_{i}^{(n_{i},t_{i})}:\mathbb{R}^{n_{i}}\to\mathbb{R}^{n_{i}}$ in
each layer.

The feedforward function of a radial neural network with shifts is defined in
the usual recursive way, as in Section 3. The trainable parameters form the
vector space $\mathsf{Param}(\mathbf{n})\times\mathbb{R}^{L}$, and the loss
function of a batch of training data
$\\{(x_{i},y_{i})\\}\subset\mathbb{R}^{n_{0}}\times\mathbb{R}^{n_{L}}$ is
defined as

$\displaystyle\mathcal{L}:\mathsf{Param}(\mathbf{n})\times\mathbb{R}^{L}\longrightarrow\mathbb{R};\qquad\qquad(\mathbf{W},\mathbf{t})\mapsto\sum_{j}\mathcal{C}(F_{(\mathbf{W},\mathbf{b},\mathbf{t},\mathbf{h})}(x_{j}),y_{j})$

where $F_{(\mathbf{W},\mathbf{b},\mathbf{t},\mathbf{h})}$ is the feedforward
function of a radial neural network with weights $\mathbf{W}$, biases
$\mathbf{b}$, shifts $\mathbf{t}$, and radial rescaling activations produced
from $\mathbf{h}$. We have the gradient descent map:

$\displaystyle\gamma:\mathsf{Param}(\mathbf{n})\times\mathbb{R}^{L}$
$\displaystyle\longrightarrow\mathsf{Param}(\mathbf{n})\times\mathbb{R}^{L}$

which updates the entries of $\mathbf{W}$, $\mathbf{b}$, and $\mathbf{t}$. The
group $O(\mathbf{n}^{\text{\rm hid}})=O(n_{1})\times\cdots\times O(n_{L-1})$
acts on $\mathsf{Param}(\mathbf{n})$ as usual (see Section 5.1), and on
$\mathbb{R}^{L}$ trivially. The neural function is unchanged by this action.
We conclude that the $O(\mathbf{n}^{\text{\rm hid}})$ action on
$\mathsf{Param}(\mathbf{n})\times\mathbb{R}^{L}$ commutes with gradient
descent $\gamma$. We now state a generalization of Theorem 5 for the case of