Model Compression via Symmetries of the Parameter Space
Authors: Iordan Ganev
Robin Walters
Venue: ICLR 2022 Submitted (2022)
Keywords: symmetry
orthogonal group
quiver representation
representation theory
model compression
parameter optimization
projected gradient descent

Abstract: We provide a theoretical framework for neural networks in terms of the representation theory of quivers, thus revealing symmetries of the parameter space of neural networks. An exploitation of these symmetries leads to a model compression algorithm for radial neural networks based on an analogue of the QR decomposition. The algorithm is lossless; the compressed model has the same feedforward function as the original model. If applied before training, optimization of the compressed model by gradient descent is equivalent to a projected version of gradient descent on the original model. 

Under review as a conference paper at ICLR 2022
MODEL COMPRESSION VIA SYMMETRIES OF THE PA- RAMETER SPACE
Anonymous authors Paper under double-blind review
ABSTRACT
We provide theoretical framework for neural networks in terms of the represen- tation theory quivers, thus revealing symmetries of the parameter space of neu- ral networks. An exploitation of these symmetries leads to a model compression algorithm for radial neural networks based on an analogue the QR decomposi- tion. The algorithm is lossless; the compressed model has the same feedforward function as the original model. If applied before training, optimization the com- pressed model by gradient descent is equivalent to projected version of gradient descent on the original model.
INTRODUCTION
Recent work has shown that representation theory, the formal study of symmetry, provides the foundation for various innovative techniques in deep learning (Cohen & Welling) 2016 Kondor & Trivedi 2018 RRaanbakkss al. 2017 Cohen Welling 2017). Much of this previous work con- siders symmetries inherent to the input and output spaces, as well distributions and functions that respect these symmetries. By contrast, in this paper, we expose broad class of symmetrics intrinsic to the parameter space of the neural networks themselves. We use these parameter space symmetries to devise a model compression algorithm that reduces the widths of the hidden layers, and hence the number of parameters. Unlike pnrresentation-thhoreee techniques in the setting of equivariant neu- ral networks, our methods are applicable to deep learning models with non-symmetric domains and non-equívariant functions, and hence pertain some degree to all neural networks.
Specifically, we formulate a theoretical framework for neural networks inspired by quiver represen- tation theory, mathematical field with connections to symplectic geometry and Lie theory (Kir-) illov Jr 2016 Nakajima et al. 1998). This approach builds on that of Armenta & Jodoin (2020) and of Wood & Shawe-Taylor (1996), but is arguably simpler and encapsulates larger symmetry groups. Formally, quiver is another name for a finite directed graph, and a representation of a quiver is the assignment of a vector space each vertex and a compatible linear map each edge.
Our starting point is to regard the vector space of parameters for neural network as representation of a particular quiver, namely, the neural quiver (Figure []. The advantage of this viewpoint that representations of quivers carry rich symmetry groups via change-of- basis transformations; such operations can viewed as symmetries of the neural network parameter space.
Moreover, these symmetries may be factored out without affecting the feedforward function, making our method a lossless model compression algorithm (Serra et al. 2020 Model compression has
Figure (a) Left: the neural quiver. Each vertex in the top row represents layer of the neural network and each arrow indicates a linear mapping. The bottom vertex is the "bias" vertex. (b) Right: a quiver with skip connections.

---

Under review as a conference paper at ICLR 2022
become critically important models have grown billions of parameters; with compression, enormous models may be reduced and run on smaller systems with faster inference (Buciluà et al, 2006 Cheng al.] 2017; Frankle & Carbin 2018: Zhang al., 2018). Whereas many previous approaches to model compression are based on weight pruning, quantization, matrix factorization, or knowledge distillation, similar to Sourek al. (2020), our approach exploits symmetries of neural network parameter spaces.
The size of the parameter space symmetry group is determined by properties of the activation func- tions. We focus on radial activation functions, as in WWeiler & Cesa (2019); [Sabour et al. (2017); Weiler et (2018 8a b); these interact favorably with certain QR decompositions, and, consequently, the model compression is significant compared to the more common pointwise (or 'local') activa- tions. We refer to neural networks with radial activation functions as radial neural networks.
Given radial neural network, our results produce a new network with fewer neurons in each hidden layer and the same feedforward function, and hence the same loss for any batch of training data. Moreover, the value of the loss function after a step of gradient descent applied to the compressed model the same as the value the loss function after a step of projected grudient descent applied to the original model. As explain below, in projected gradient descent, one subtracts trunca- tion of the gradient, rather than the full gradient. When the compression is significant enough, the compressed model takes less time per epoch train and reaches local minima faster.
To state these results slightly more precisely, recall that the parameters of a neural network with layer widths (no, A1...... n consist of n, X (M,-1+1) matrix W, of weights for each layer where include the bias as an extra column. These are grouped into tuple W (W; xm= r+1)).
We define the reduced widths recursively as ngdd min (n:, red + 1) for i 1..... L 1, with
n = n2 and z red = nn. Note that nodd < n2 for all é. Theorem 1.1 (Informal version of Theorems 4.3 and 4.7j. Suppose a neural network has L layers with widths (mo....,,n) parameters W, and radial activation functions. finictoion,functiooss. Let fw: R8 - RR. be the feedforward function of the network.
1. There exists an algorithm to produce reduced radial neural network with layer widths (no: nied "".,,. parameters R, and the same feedforward function fn fww
2. Training fn with gradient descent is an equivalent optimization problem to training fw with projected gradient descent.
This theorem can be interpreted model compression result: the reduced (or compressed) neural network R has the same accuracy as the original neural network W, and there is an explicit relation- ship between the gradient descent optimization problems for the two neural networks. This result is not just theoretical; it emerges from a practical and efficient algorithm depending on successive QR decompositions. We describe this procedure below (Algorithm) T and implement it in Python.
To summarize, our contributions are as follows:
1. A theoretical framework for neural networks based on quiver representation theory;
2. A QR decomposition for radial neural networks;
3. An implementation of a lossless model compression algorithm for radial neural networks;
4. A theorem relating gradient descent optimization of the original and compressed networks.
We view this work step in the direction of improving learning algorithms by exploiting symme- try inherent to neural network parameter spaces. As such, we expect our framework and results to generalize in several ways, including: (1) further reductions of the hidden widths, (2) incorporating certain non-radial activation functions, (3) encapsulating networks beyond MLPs, such as convolu- tional, recurrent, and graph neural networks, (4) integration of regularization techniques. We include a detailed discussion of the limitations of our results, as well as future directions, in Section
2 RELATED WORK
Quiver Representation Theory and Neural Networks. Armenta & Jodoin 2020) give an ap- proach understanding neural networks in terms of quiver representations. Our work generalizes
2

---

Under review as a conference paper at ICLR 2022
their approach it (1) accommodates both pointwise and non non-pointwise activation functions, (2) taps into larger symmetry groups, and (3) connects more naturally to gradient descent. Jeffreys & Lau (202T) and Manin & Marcolli (2020) also place quivers in the context of neural networks; our and categorical perspectives, but differs in our emphasis on practical consequences for optimization techniques at the core of machine learning.
approach is inspired by similar algebro-geometee
These works have a number of precursors. One is the study of the "non-negative homogeneity" (also known as "positive scaling invariance") property of ReLU activation functions (Dinh et al. 2017 Neyshabur et al. 2015; Meng et al. 2019), which is special case of the symmetry studied in this paper. [Wood& & Shawe- Taylor (1996) regard layers in a neural network as representations of finite groups and consider only pointwise activation functions; by contrast, our framework captures Lie groups as well as non-pointwise activations. Our quiver approach to neural networks shares parallels with the "algebraic neural networks" of o their formalism amount to representations of quivers over base rings beyond R. such as the ring of polynomials. In somewhat different data-analytie context, [Cindris & Kline (202I) use quiver representation theory in order to untangle point clouds; though they do not use neural networks.
& Ribeiro) and special cases of
Equivariant Neural Networks. Previously, representation theory has been used to design neu- ral networks which incorporate symmetry as an inductive bias. A variety of architectures such as G-convolution, steerable CNN, and Clebsch-Gordan networks are constrained by various weight- sharing schemes to be equivariant or invariant to various symmetry groups (Cohen et al. 12019] Weiler & Cesa. 2019 Cohen& Welling 2 Chidester et al. 2018, Kondor & Trrivedi [0118] Bao & | Worrall et al.) [017]] Cohen & Welling, [017] Weiler et al. [0188]] Dieib//iielmann et al.
contrast, does not rely on symmetry of the input domain, output space, or mapping. Rather, our method exploits symmetry of the parameter space and thus applies more generally to domains with no obvious symmetry. From the point of view of model compression, equivariant networks do achieve reduction in the num- ber of trainable parameters through weight-sharing for fixed hidden dimension widths; however, in practice, they may use larger layer widths and consequently have larger memory requirements than non-equivariant models. Sampling or summing over large symmetry groups may make equivariant models computationally slow as well (Finzi al. 2020 Kondor & Trivedi 2018).
2016
Lang & Weiler 2021] Ravanbakhsh et al. Our approach,
Model Compression and Weight Pruning. A major goal in machine learning is to find methods for compressing models in order reduce the number of trainable parameters, decrease memory usage, or accelerate inference and training (Cheng et al., 2017). Our approach toward this goal differs significantly from most existing methods in that it based on the inherent symmetry of neural network parameter spaces. One prior model compression method is weight pruning, which removes redundant, small, or unnecessary weights from a network with little loss accuracy (Han) et al. 2015 Blalock et al. 2020; Karnin 1990). Recent work has shown pruning can be done during training by identifying and removing weights of less relevance and reverting other weights to earlier values (Frankle& & Carbin 2018). Related work shows effective pruning may be done at initialization
(Lee et al. 2019]] Wang et al.) 2020). trndient-based pruning identifies low saliency weights by estimating the increase in loss resulting from their removal (LeCun et al.) 1990 Hassibi & Stork
1993 Dong et al. 2017 Molchanov et al.] (0066). A complementary approach is quantiization in which the bit depth of weights is decreased (Wu al., 2016 Howard et al. 2017 Gong al. 2014).
Knowledge distillation works by training a small model to mimie the performance of a larger model or ensemble of models (Buciluă et al. 2006; Hinton et al., 2015) [a & Caruana 2013). Matrix Factorization methods replace fully connected layers with lower rank or sparse factored tensors (Cheng et al., 22015a (b) Tai et al., 2015 |013) [ebedev et al., 2014, Rigamonti et al. 2013 Lu al. 2017) and can often be applied before training. Our method involves generalized QR decomposition, which is a type of matrix factorization; however, rather than aim for a rank reduction of linear layers, we leverage this decomposition in order to reduce hidden layer widths via change-of-bass operations on the hidden representations. Closest to our method are lossless compression methods. Serra et al. [2021 2020 identify and remove stable neurons in ReLU networks. [Sourkk et al. (2020) also exploit symmetry in parameter space to remove redundant neuron. However, their symmetries are induced from permutation equivariance; ours follow from the symmetries of the radial activation.
3

---

Under review as a conference paper at ICLR 2022
3 NEURAL NETWORKS AS QUIVER REPRESENTATIONS
We turn attention to quivers and their representations. Neural networks may be viewed repre- sentations specific quiver with the additional data of activation functions; backpropogation can also be formulated in these terms. The advantage of such perspectives is that representations come equipped with symmetry groups. We provide proofs and context for this section in Appendix D
3.1 QUIVER REPRESENTATIONS
quiver finite directed graph. dimension vector for quiver consists of a non-negative
integer for every vertex, that is, a tuple d = (d:); indexed by the vertices of Q. A representation of Q with dimension vector d consists of a matrix for each edge, where the matrix Ag corresponding
to an edge ف must be of size de d.. In other words, a representation is tuple of matrices (Ae)e indexed by the edges of Q, with sizes constrained by the dimension vector. Note that each A, defines a linear map Rd R The space of representations Rep( Q, d) is defined as the set of all possible representations of quiver Q with dimension vector d. This space can be expressed
as the product of matrix spaces: Rep( Q, d) = Ileeg Rdde)xddto)) Here E is the edge set of Q, and
s(e) and t(e) denote the source and target vertices of an edge c.
3.2 THE NEURAL QUIVER
For the remainder of the paper, focus on particular quiver. Let L be positive integer. The neural quiver Q₂ is the quiver with L+ vertices shown in Figure [ The vertices in the top row are L. The first vertex (i = in the top row is called the input vertex, the indexed from i = 0 to
last vertex (i = L) is the output vertex, and every other vertex (1 < S I, -- 1) in the top row is a hidden vertex. The vertex at the bottom is called the bias vertex and connected each vertex in the top row except for = O. When discussing representations of the neural quiver, we exclusively consider dimension vectors whose value at the bias vertex is Hence, a dimension vector for the neural quiver will refer to an (L + 1t-tup of positive integers n (Mo...., n.))
With these conventions in hand, we observe that, by definition, a representation of the neural quiver with dimension vector consists of an n, X R2:11 matrix A; and a vector b, E R": for each i 1, .......... L. Correspondingly, there is an affine map W; R -> R given by + A, + bi. and an n, x (1 + ni-1) matrix given by W = [b, A.J. As a result, we have:
Lemma 3.1. A representation of QL with dimension vector n is equivalent to the data of an affine map I 1 - I for each = =,...., There an isomorphism of vector spaces:
Rep( Q2, ~ R (1+
[m2x(I+01)
REE 1).
Notation:
We henceforth denote representation of Qr. as tuple W = (W:) where each W; belongs to (1++())))))) and denote the corresponding affine maps as W; Ra--1 + Rd,
3.3 CHANGE-OF OF-BSSS SYMMETRY
Recall that the general linear group GL,, (R) consists of the set of invertible n by n matrices. The unit the identity n by n matrix, denoted id,, There is a linear action of the general linear group GL, (R) on the vector space I² given by matrix multiplication: स + Gø for G E GL, (R) and IR.. This action encodes change-of-basis transformations: the entries of the vector G7 are the coefficients when expressing the original vector z in the basis specified by the columns of G-1.
Given a dimension vector n for the neural quiver, the parameter symmetry group defined as:
GL hidden GL,n (R) GImy (R)
GImg (IR)
An element of this group consists of the choice of a transformation of R for each hidden vertex and results in a corresponding transformation of the matrices W; appearing any representation W of the neural quiver with dimension vector To be explicit, particular choice G (G)
4

---

Under review as a conference paper at ICLR 2022
of transformations results in the following linear transformation of representation
W = (Wi + G.W = ( G. G.W., W. G =²1)=,.
(3.1)
where Go = idng and G idm-. In other words: there a linear action of the parameter symmetry group GL, hidden on the vector space Rep( Q2, n) of representations of the neural quiver.
3.4 NEURAL NETWORKS
For simplicity, in the body of this paper, we focus on the most basic neural network architecture, namely that of multi-layee perceptrons (MLPs). These the neural networks whose underlying archi- tecture is specified by the neural quiver. We include a discussion of more complex quivers (such as
that in Figure (p) in the appendix. We begin with the following somewhat abstract definition:
Definition 3.2. An Or neural network consists of the following:
1. Hyperparameters. A positive integer L and a dimension vector = (no, f1,, 722 TL. for the neural quiver Qr.
2. Trainable parameters. A representation W IW..... Wr) of the neural Or. with dimension vector n. So each W; is matrix in (1xx
3. Activation functions. Piece-wise differentiable functions a; R R for
1,..., L. These are grouped into a tuple = (a))
For the remainder of this paper, unless specified otherwise, "neural network" will refer to "Qr- neural network". We emphasize, however, that there is general notion of a Q-neural network for any acyclic quiver Q with unique sink (see Appendix D). Additionally, as indicated above, in the case of the neural quiver, neuneu network equivalent to MLP.
We denote by Neur QL, n) the vector space neural networks with layers and dimension vector n, and regard elements therein pairs (W, a). The neural function (or feedforward function) of a -eeuel network (W, a) is defined as:
f(Wa)
RL
H ar WL W.....oa W2 o aa (z)
where W; R- Rt is the affine map corresponding W; (see Section 3.2
The optimization problem for neural networks can be formulated in terms of representations of the neural quiver. Fix dimension vector for Qr. and activation functions To batch of training data {(T 7,) 1 Ra,, the associated loss function on the space Rep( Q1. n) is defined as
f: Rep( Qr, + R
L(W) = Σ C (J(w.a) (7,))
where C: Ru Rur + R is a cost function. The map
ReRRR n) + Rep (e.(Q2.n)
W = W - WWW
performs one step of gradient descent with learning rate 7). Hence, the backpropogation algorithm can be regarded as taking place on the space Rep( Q) of representations of the neural quiver.
4 MAIN THEORETICAL RESULTS
In this section, first define radial neural networks. Then, adopting the framework developed in the previous section, we proceed to state a QR decomposition for such networks, present an algorithm compute the decomposition, and relate the decomposition to gradient descent.
For each i, the matrix 1
0
G is block diagonal with one x block consisting of the single entry
11', and n ni-1 black consisting of the inverse of the matrix G,-1 E GT (R).

---

Under review as a conference paper at ICLR 2022
4.1 RADIAL NEURAL NETWORKS
We begin by stating the definition of radial functions. A piece-wise differentiable function a R" IR called radial if a(v) = h((el) fo for some h R + R. Hence, sends each input
vector e E R to a scalar multiple of itself, and that scalar depends only on the norm of the vector.
Example 4.1. (I) The squashing function, where h(r) ,² T ReLU(( b) for 0 real number b. See Weiler & Cesa (2019) and the references therein for
(2) Shifted ReLU, where h(r)
more examples and discussion of radial functions. See Figure 2
Let n be a dimension vector for the neural quiver Qr. neural network (W, a) Neur n) is radial neural network if each a; is radial function on R", Hence, there are functions h; I + R such that a,(v) (1,(v)) ! for each Let (n)) denote the following product of the orthogonal groups:
25
RelUi--1
RelUir11)
((n) = Om1)) O(n2) x x O(nL-1).
1.0
Note that (n) a subgroup of the parameter symmetry group GL hidden and hence acts on Rep( Q, n). Radial func- tions have the flexibility of defining the activation functions of a neural network with arbitrary dimension vector. To be more explicit:
Figure 2: Different radial radial activations.
Construction 4.2. Suppose h (hi...., h2) is tuple of functions
is R R. and suppose n
dimension vector for 2r. Consider the tuple of activation functions: an (m) [
(m1)
...., ... (mz)
Any representation W of Oz with dimension vector defines neural network (W, an Definition
(m)
in
3.2
We write simply (W, h) for this network and f(w,h) for its neural function.
4.2
THE QR DECOMPOSITION
We now formulate the QR decomposition for representations of the neural quiver, which interacts favorably with radial neural networks. Proofs and further context appear in Appendix E
The first step is to associate a 'reduced' dimension vector to each dimension vector of the neu- ral quiver. Let (no red ................................ ndd is defined recursively Fl by setting ni = ni. then need min(n;, n + 1) We abbreviate Rep( n) by Rep(n) and Rep(Oz, n by Re Observe that nited < n, for each i. Therefore, taking a representa- tion with dimension vector nd i.e., a certain tuple of matrices, one can pad each matrix with the necessary number of rows of zeros below and columns of zeros the right in order produce representation with dimension vector n. Thus we have an inclusion: i: Rep(n ndd) + Rep(n).
(Ro, P1..... m be dimension vector for Qz. Its reduction n
for i = L,...,L L 1, and finally nz =
Fix tuple (fi,..., h1) of functions h; R + R. As in Construction 4.2 attach radial neural network (and hence a neural function) to every representation of Qr.-
Theorem 4.3. Let n be dimension vector and fix as above. For any W E Rep(n) there exist:
Q
R = -Ri...... RI) E Rep(n
and
U @Rep(n),
such that:
1. The matrices RI....,LL are upper triangular.
2. The following equality holds: = =
3. The networks defined by W and R have identical neural function:: f(w,)) f(R,h)-
We assume each h; picce-wise differentiable and the limit lim, kx(r)) exists.
'For neural networks without bias vectors, one defines the reduced dimension vector ne using instead the recursion n. min(n,, 3nd ). See Appendix H.1

---

Under review as a conference paper at ICLR 2022
In the the second point above, we identify R with its image in Rep(n) under and invoke the action of (n) on Rep(n). We say that R is the reduced representation corresponding to W. The proof of Theorem 4.3 (appearing in Appendix E.2) relies on Algorithm constructive algorithm proceeding layer by layer and computing a QR decomposition at each stage.
Remark 4.4. Part (2) of Theorem 4.3 is quiver representation analogue of the usual QR decompo- sition (c.f. Section [.2); indeed, each matrix (except possibly the last) in R. is upper triangular and Q is tuple of orthogonal matrices.
Algorithm 1: QR Dimensional Reduction (ORDimRed)
input :W E Rep(n)
output : QQ R, U from Theorem 4.3
Q.R, U - [],[],10]
// initialize output matrix lists
V1 W1
// next layer transformed weights // iterate through layers
for i + 1 to L --11 do
in < n, then
Q, R2 QR-decomp (V, mode complete)
11 V Qi inc; R4
else
Q, R, QR-decomp (V))
// V Q R
end
Append Q to Q Append R; to R
// reduced weights for layer i
1
0
1
0
Append W W+1
0
Q
o
Pi
0
Q
to U
// matrix multiplication
1
0
Set Vi+ < Wi+1
Qi
inc;
// transform next layer
end
Append V2 R
return Q, R. and U
Notation: The symbol 'o' denotes matrix multiplication. We initialize U as list with a single element: the zero n2 x (1 + no) matrix. For i = L...., 1, we have the standard inclusions + I and inc; inC
I 4 Ri+n; into the first ne and 1 + nood coordinates, respectively. As matrices, they have ones along the main diagonal and zeros elsewhere. The map Rr + IR+++1 zeros the first 1 1 n coordinates and leaves the remaining coordinates unchanged. As matrix, pt is block diagonal with two square blocks; the top block is the zero matrix of size n + 1, and the bottom is the identity matrix of size n, mood.
inc; inc,,eed, ,,; R ted
By definition, either nedd = - + or nedd = ny In the former case, n: + 1 S n4 and QR QR-decomp with 'mode = complete computes the QR decomposition of the ne x (1 + m
matrix V; as Q; o inc; R, where Qi E O(n;) and RG is upper-triangular of size rade x noed In the
red +1 2 n, and decoccomp computes the QR decomposition of the n, x (1 (1+n)ed) latter case, me
matrix V2 as Qi R. where Q; E On:)) and R₁ is upper-triangular of size n; (1 + red
Figure 3: Parameter reduction in 3 steps. Since the activation function radial, commutes with orthogonal transformations. This example has no bias and thus has n (1, 1, instead of 21, 1). (See Footnote 3) The number of trainable parameters reduces from 24 3.
Example 4.5. Suppose the dimension vector is (1,8, 16, 8, 1), so the original radial neural network model has ( + 1)m, 305 trainable parameters. The reduced dimension vector

---

Under review as a conference paper at ICLR 2022
is n (1,2,3,4,7 4) One computes that the compressed model has (x + 1) 34 trainable parameters. Another example appears in Figure
4.3 PROJECTED GRADIENT DESCENT
In this section, we use the QR decomposition of Theorem 4.3 to relate projected gradient descent for representation (usual) gradient descent for the corresponding reduced representation. Proofs and further context appear in Appendix
We adopt the notation of the previous sections. In particular, we fix tuple h ..i,.... hr) ): as in Construction 4.2, this can be used to define a neural network for any representation of 2t. with any dimension vector. Furthermore, we fix batch of training data in Re R Using h, we obtain loss functions L (ep(n) + R and Leed Rep(n"" - I (see Section 3.4. For a fixed learning rate, there are resulting one-step gradient descent maps given by:
Rep(n) + Rep(n) W + W -1 77. VWC
Rep(n ro)) - Rep(n
X X n VxLed
Definition 4.6. Define Pr Rep(n) Rep(n) be the map that, given a representation Rep(n), zeros the bottom left (n, nidd) x (1 + m submatrix of T;, for each i. Schematically,
Pr(T) ((o
Pr: T
i=1
The one-step projected gradient descent map on Rep(n) at learning rate > is defined as:
Ppruj Rep(n) -> Rep(n)
W W 7 Pr CW
Hence, while all entries of each matrix W, in the representation W contribute to the computation of the gradient Ww only those not in the bottom left submatrix get updated under the projected gradient descent map "proj- To ease notation in the statement of the following result, we identify elements of Rep(n with their images in Rep(n) under t.
Theorem 4.7. Let W E Rep(n) and let Q, R, and U be the outputs of Algorithm rate 1) For any O, have:
Fix a learning
* (W) = Q 7 (Q W)
and
A Peaj
(Q -1 W) = k R + Q--Q1
-1 U.
While the proof of the second statement Theorem 4.7 is quite technical, the proof of the first relies basic interaction of orthogonal transformations with gradient descent, which we briefly illustrate (Appendices C and IF contain more details). Let
R - IR be function, and let 7: R - R be the gradient descent map with respect L. Suppose Q O(p) an orthogonal transformation of R2 that preserves the level sets of L, that is, L(Q(v)) = L(v) for all o E IRP. Then Q commutes with gradient descent, i.e. (Q(()) Q(T(v)) for all v Rº See Figure
Figure 4: 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. In this example, projected and usual gradient descent match; this is not the case in higher dimensions, as explained through examples in the appendix (see F.4 and H.I
8

---

Under review as a conference paper at ICLR 2022
5 EXPERIMENTS
In addition to the theoretical results in this work, we provide an implementation of QRDimRed as described in Algorithm I We (1) empirically validate that our implementation satisfies the claims of Theorems 4.3 and Theorem 4.7 and (2) quantify real-world performance.
Empirical verification of Theorem
4.3 We verify the Theorem using a small model and synthetic
data. We learn the function fx) = E using N = 121 samples x; = -3 -3+ j//0 for 0 S j < 121.
We model fw as radial neural network with layer widths n (1, 6, 7. and activation the radial shifted sigmoid l((z) = 1/(1+ -x+b), Applying QRDimRed gives a radial neural network fR with widths n red (1, 3. 1). Theorem 4.3 implies that the neural functions of fw and fR are equal.
Over 10 random initializations of W, the mean absolute error (1/N) Σ, [f,((z) - fR [zzz)] 1.31 10- + 4.45 10-9. Thus fw and fR agree up to machine precision.
Empirical verification of Theorem 4.7 Similarly, we verify the conclusions of Theorem 4.7 using synthetic data. The claim is that training fQ-1.w with objective L by projected gradient descent coincides with training fR with objective Lred by usual gradient descent. We verified this for 3000 epochs learning rate 0.01. Over 10 random initializations of W. the loss functions match up to machine precision with [C Lred = 4.02 10 9 + 7.01 10
Reduced model trains faster. Due to the relation between projected gradient descent of the full network W and gradient descent of the reduced network R. our method may be applied before training to produce a smaller model class which trains faster without sacrificing accuracy. We test this hypothesis in learning the function f IR2 R² sending x = (t1, t2) to (e "i, e +2) using 121 samples ( (-3+ j/20, 3 k/20) for 0 S j.k < 121. We model fw as radial neural network with layer widths n = (2, 16, 64, 128, 16, and activation the radial sigmoid h(r) = 1/(1 + eTT). Applying QRDimRed gives radial neural network fR with widths n = (2, 3, 4, 5, 6, 2). We trained both models until the training loss was S 0.01. Running on a system with an Intel i5-8257U@) 1.40GHz and 8GB of RAM and averaged over 10 random initializations, the reduced network trained in 15.32 + 2.53 seconds and the original network trained in 31.24 + 4.55 seconds.
6 CONCLUSIONS AND FUTURE WORK
In this paper, have adopted the formalism of quiver representation theory in order to establish a theoretical framework for neural networks. While drawing inspiration from previous work, our approach is novel in that it (1) reveals a large group of symmetries of neural network parameter spaces, (2) leads to a version of the QR decomposition in the context of radial neural networks, and (3) precipitates an algorithm to reduce the widths of the hidden layers in such networks.
Our main results, namely Theorems 4.3 and 4.7 may potentially generalize in several ways. First, these theorems are only meaningful if n4 > 7h-11 + for some i (otherwise ned n). Many net- works such as decoders, super-resolution mappings, and GANs fulfill this criteria, but others do not. Our techniques may achieve meaningful width reductions in other cases. Second, the hypothesis that the activation functions are radial is crucial for our results, as they commute with orthogonal matri- ces, and hence interact favorably with QR decompositions. However, similar dimensiionll-rdduction procedures may well be possible for other activation functions which relate to other matrix decom- positions. In particular, the bottleneck effect discovered by /Serra et al. 2018) for ReLU networks bears a striking similarity our ascending condition. Third, though Theorem 4.7 does not hold for deordinate-dependeet optimizers like Adam, other optimizers in the same spirit may be compatible. Fourth, there may be enhancements of our results that incorporate regularization and assert prov- able improvements to generalization. For example, the loss function of a radial neural network with dimension vector n remains invariant for the O(n) action after adding 1,2 regularization term. Finally, the conceptual flexibility of quiver representation theory can encapsulate neural networks beyond MLPs, including CNNs, equivariant neural networks, RNNs, GNNs, and others.
Our result in Theorem 4.7 relates projected gradient descent Yproj for the original network to gradient descent y for the reduced network. In order to make theoretical conclusions about optimization of the original versus the reduced network, it is necessary to relate gradient descent on both spaces. To realize this, we conjecture, based on preliminary experimental evidence, that our version projected gradient descent is first-order approximation of usual gradient descent; we are pursuing work to make this relationship precise.

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
Our work primarily focused on theoretical foundations of machine learning, however, it does have direct application in the form model compression. Model compression is largely beneficial to the world since it allows for inference to run on smaller systems which use less energy. On the other hand, when models may be run on smaller systems such as smartphones, models covertly, for example, for facial recognition and surveillance. This may make abuses of deep learning technology easier hide.
easier use deep
REPRODUCIBILITY STATEMENT
The theoretical results of this paper, namely Theorem 4.3 and Theorem 4.7 may be independently verified through their proofs, which we include in their entirety in Appendices F and F including all necessary definitions, lemmas, and hypotheses in precise and complete mathematical language. The empirical verification of Section 5 may be reproduced using the code included with the supple- mentary materials. In addition, Algorithm i written in detailed pseudocode, allowing readers to recreate our algorithm in a programming language of their choosing.
REFERENCES
Marco Antonio Armenta and Pierre-Marc Jodoin. The Representation Theory of Neural Networks. 1XXiv:2007.12213 2020.
htlgg//bs/00000 12213
Lei Jimmy Ba and Rich Caruana. Do deep nets really need be deep? arXiv:1112.6118,,2 2013.
Erkao Bao and Linqi Song. Equivariant neural networks and equivarification. arXiv:1906.07177 2019.
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state of neural network pruning? arXiv:2003.03033, 2020.
Cristian Buciluă, Rich Caruana, and Alexandru Niculescu-Mizil. Model compression. In Proceed- ings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 535-541, 2006.
Yu Cheng, X Yu Felix, Rogerio S Feris, Sanjiv Kumar, Alok Choudhary, and Shih-Fu Chang. Fast neural networks with circulant projections. 1rxXiv:552.0344 2, 2015a.
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, pp. 2857-2865, 2015b.
Yu Cheng, Duo Wang, Pan Zhou, and Tao Zhang. A survey of model compression and acceleration for deep neural networks, arXiv: 111..7000.0..2.. 2017.
Benjamin Chidester, Minh N. Do. and Jian Ma. Rotation equivariance and invariance in convolu- tional neural networks. arXiv: /805. /2301, 2018.
Calin Chindris and Daniel Kline. Simultaneous robust subspace recovery and semi-stability of quiver representations. Journal of Algebra, 577:210 236, 2021. ISSN 0021-8693. doi: 10. jalgebra.2021.033...
http://wwwwwwennnciccccccccc com/ wtt.m//cceeennaaattiileee
p11/s00218693211 00138
Taco S. Cohen and Max Welling. Group equivariant convolutional networks. In International
conference on machine learning (ICML), pp. 2990-2999 2016.
Taco S Cohen and Max Welling. Steerable CNNs. In Proceedings of the International Conference Learning Representations (ICLR), 2017.
Taco S. Cohen, Maurice Weiler, Berkay Kicanaoglu, and Max Welling. Gauge equivariant convo- lutional networks and the icosahedral CNN. Proceedings of the 36th International Conference Machine Learning (ICMI), volume 97, pp. 1321-1330, 2019.
10

---

Under review as a conference paper at ICLR 2022
Sander Dieleman, Jeffrey De Fauw, and Koray Kavukcuoglu. Exploiting cyclic symmetry in convo- lutional neural networks. In International Conference on Machine Learning (ICML), 2016.
Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp Minima Can General- ize For Deep Nets. In International Conference on Machine Learning (ICML), pp. 1019-1028. PMLR, July 2017. URL
mir press/pres//vv http:///////nn///////// html
Xin Dong, Shangyu Chen, and Sinno Jialin Pan. Learning prune deep neural networks via layer- wise optimal brain surgeon. arXiv preprint arXiv:1705.0756: 2017.
David S. Dummit and Richard M. Foote. Abstract Algebra. John Wiley & Sons, July 2003. ISBN 978-0-471-4333--.
Mare Finzi, Samuel Stanton, Pavel Izmailov, and Andrew Gordon Wilson. Generalizing convolu- tional networks for equivariance to lie groups on arbitrary continuous data. In Proceedings of the International Conference Machine Vision and Machine Learning, 2020.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv: 1803. 03635, 2018.
Yunchao Gong, Liu Liu, Ming Yang, and Lubomir Bourdev. Compressing deep convolutional net- works using vector quantization. arXiv:1412.6115, 2014.
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. 1rXiv:1510.00019,, 2015.
Babak Hassibi and David G Stork. Second order derivatives for network pruning: Optimal brain surgeon. Morgan Kaufmann, 1993.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv:1503.02531, 2015.
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.0466,, 2017.
George Jeffreys and Siu-Cheong Lau. Kähler Geometry of Quiver Varieties and Machine Learning. arXiv:2101.11487 2021.
11487
Ehud D Karnin. A simple procedure for pruning brok-propng trained neural networks. IEEE transactions on neural networks, 1(2):239-242. 1990.
Alexander Kirillov Jr. Quiver representations and quiver varieties, volume 174. American Mathe- matical Soc., 2016.
Risi Kondor and Shubhendu Trivedi. On the Generalization of Equivariance and Convolution in Neural Networks the Action of Compact Groups. In International conference on machine learning (ICML), 2018.
Lcon Lang and Maurice Weiler. A Wigner-Eckart theorem for group equivariant convolution ker- nels. In International Conference on Learning Representations (ICLR), 2021.
Vadim Lebedev, Yaroslav Ganin, Maksim Rakhuba, Ivan Oseledets, and Victor Lempitsky. Speeding-up convolutional neural networks using fine-tuned ap-ecopppoto. arXiv: 1412.6555 2014.
Yann LeCun, John S Denker, and Sara A Solla. Optimal brain damage. In Advances in neural information processing systems, pp. 598 598-55985555 605, 1990.
Namhoon Lee, Thalaiyasingam Ajanthan, Stephen Gould, and Philip HS Tor. A signal propagation perspective for pruning neural networks at initialization. arXiv preprint arXiv:1906 06307, 2019.
Yongxi Lu, Abhishek Kumar, Shuangfei Zhai, Yu Cheng, Tara Javidi, and Rogerio Feris. Fully- adaptive feature sharing in multi-tae task networks with applications in person attribute classification. In Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR), pp- 5334-5343, 2017.
11

---

Under review as a conference paper at ICLR 2022
Yuri Manin and Matilde Marcolli. Homotopy Theoretic and Categorical Models of Neural Informa- tion Networks. arXiv:2006. 15136, 2020. htlLhhttp///xxaee org/ abs/ w0wp:////.abbb....ooo.bo 15136
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 http:///wwww..lloooooo....//////
mi
Pavlo Molchanov, Stephen Tyree, Tero Karras, Timo Aila, and Jan Kautz. Pruning convolutional neural networks for resource efficient inference. arXiv preprint arXiv: 2016.
Hiraku Nakajima et al. Quiver varieties and Kac-Moody algebras. Duke Mathematical Journal, 91 (3):515-500, 1998.
Behnam Neyshabur, Ruslan Salakhutdinov, and Nathan Srebro. Path-GG: path path-normalized opti- mization in deep neural networks. In Proceedings of the 28th International Conference on Neural Information Processing Systems Volume 2, NIPS 15, pp. 2422 2430, Cambridge, MA, USA, December 2015. MIT Press.
Alejandro Parada-Mayorga and Alejandro Ribeiro. Algebraic Neural Networks: Stability to Defor- mations. arXiiv:009.01433v3
Kaare Brandt Petersen, Michael Syskind Pedersen. Jan Larsen, Korbinian Strimmer, Lars Chris- tiansen, Kai Hansen, Liguo He, Loic Thibaut, Miguel Barão, Stephan Hattinger, Vasile Sima, and We The. The Matrix Cookbook. Technical report, 2012.
Benjamin C Pierce. Basic category theory for computer scientists. MIT press, 1991.
Alfio Quarteroni, Riccardo Sacco, and Fausto Saleri. Numerical Mathematics. Texts in Applied Mathematics. Springer-Verlag, Berlin Heidelberg, 2 edition, 2007. ISBN 978-3-994----0034655866 doi: 10.1007/698885. URL https: //ttps://www. spr i inger. httmm///pbooox///5433333333
Siamak Ravanbakhsh, Jeff Schneider, and Barnabas Poczos. Equivariance through parameter- sharing. International Conference on Machine Learning, pp. 2892-2901. PMLR, 2017.
Roberto Rigamonti, Amos Sironi, Vincent Lepetit, and Pascal Fua. Learning separable filters. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 2754 2761, 2013.
Sara Sabour, Nicholas Frosst, and Geoffrey E Hinton. arXiv:1710.09822 2017.
Dynamic routing between capsules.
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. In International Conference on Machine Learning, pp. 4558- 4566. PMLR, 2018.
Thiago Serra, Abhinav Kumar, and Srikumar Ramalingam. Lossless compression of deep neural networks. In International Conference on Integration of Constraint Programming, Artificial In- telligence, and Operations Research, pp. 417-430. Springer, 2020.
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.
Gustav Sourek, Filip Zelezny, and Ondrej Kuzelka. Lossless compression of structured convolu- tional models via lifting. arXiv preprint arXiv:2007.06566 2020.
Cheng Tai, Tong Xiao, Yi Zhang, Xiaogang Wang, al. Convolutional neural networks with low- rank regularization. arXiv:1511.06067 2015.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. arXiv preprint arXiv:2002.0737, 2020.
Maurice Weiler and Gabriele Cesa. General E Equivariat Steerable CNNs. Conference on Neural Information Processing Systems (NeurIPS), 2019.
12

---

Under review as a conference paper at ICLR 2022
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 Neural Information Processing Systems (NeurIPS), 2018a.
Maurice Weiler, Fred Hamprecht, and Martin Storath. Learning steerable filters for rotation equivariant CNNs. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 849-858, 2018b.
Jeffrey Wood and John Shawe-Tayle Taylor. Representation theory and invariant neural networks. Discrete Applied Mathematics, 69(1):33-660 August 1996. ISSN 0166-218X. doi: 10. 0016000666-188000000075333
URL httpt:::////t h sciencedirect. com science///////c
arricle/p1110016211885550
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), pp. 5028-5037, 2017.
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 Puttern Recognition (CVPR), pp. 4820-4828, 2016.
Tianyun Zhang, Shaokai Ye, Kaiqi Zhang. Jian Tang, Wujic 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), pp. 184-199, 2018.
13

---

Under review as a conference paper at ICLR 2022
A ORGANIZATION OF APPENDICES
This paper is 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, use precise mathematical formalism throughout, and emphasize the rich abstract structures underlying neural networks. The purposes of these appendices are several:
1. To clarify the mathematical conventions and terminology, thus making the paper more accessible.
2. To provide full proof' of the main results.
3. To develop context around various constructions appearing in the main text.
4. To discuss in detail examples, special cases, and generalizations of our results.
We now give summary of the contents of the appendices. Appendix B consists of preliminary material. We first review the necessary background on linear algebra and group theory, and then state the version of the QR decomposition that is relevant for this paper.
Appendix C serves to establish notation used the context of gradient descent, and to prove an interaction between gradient descent and orthogonal transformations (Proposition
Appendix D supplements 3 Specifically, Appendix D we provide expanded foundations for our proposed framework of neural networks quiver representations. In particular, give proof of Lemma 3.1 explain symmetries on the space of all neural networks with a specified dimension vector, and prove equivariance results. Finally, explain how the "non-negative homogeneity" property pointwise ReLU activation functions is special case of our results (c.f Proposition D.5 and Remark D.7).
In Appendix we first establish elementary results related to radial functions and radial neural networks in Section E.1 and then give proof of the QR Decomposition result (Theorem 4.3) in
Section E.2 The proof relies on Algorithm
In Appendix F we focus on projected gradient descent. Specifically, we first introduce an 'interpo- lating space" that relates the space of representations with a given dimension vector to the space of representations with the reduced dimension vector (Section F.T Using the interpolating space, we define projected version of gradient descent (Section F22) and give proof of Theorem 4.7 which relates projected gradient descent and the QR decomposition for radial neural networks.
We devote Appendices H and to special cases and generalizations of the constructions and results of the main text. Specifically, consider version our results for neural networks with no biases (Section H.I), generalization involving shifts in radial functions (Section H.2), and formulation and generalization of our results using the language of category theory (Appendix)
B LINEAR ALGEBRA
In this appendix, we first review basic notation and concepts from linear algebra, group theory, and representation theory. We then state version of the QR decomposition. References include include|Petersen et al. 2012), Quarteroni et al. (007)), and Dummit & Foote (2003).
B.1 BASICS
For positive integers m and n, Hom(R." R²) or Ruxn denote the vector space n by m matrices with entries in R, that is, the vector space of linear functions (also known as homomor- phisms) from IRm to R", The general linear group GL,, consists of the set of invertible n by matrices, with the operation of matrix multiplication. Equivalently, GL,, (IR) consists of all linear automorphisms R" with the operation of composition. Such automorphisms are given precisely by change-of-basie transformations. The unit is the identity by matrix, denoted id,, The orthog- onal group O(n) is the subgroup of GL,, (R) consisting of matrices Q such that QTQ Q = id,,- Such matrix is called an orthogonal transformation.
14

---

Under review as a conference paper at ICLR 2022
Let G be group. An action (or representation) of G the vector space R" is the data of an invertible n by n matrix p(g) for every group element E G, such that (1) for all g. E G, the matrix p(gh) is the product of the matrices p(g) and p(h), and (2) for the identity element lG E G, we have p(1@)= = idn- In other words, an action amounts to group homomorphism p: G (R). We often abbreviate p(g)(v) simply g v, for g E G and R A function f: IR" R (non-linear in general) is invariant for the action of G if f(g o) = f(v) for all g E G and IR"
Ind denotes the standard inclusion into the first m Suppose m S n. Then inCm,n R coordinates:
(Ui...., Um) Y (U1...., Cm ...... 0)
The standard projection Tn.m RR _ Rm onto the first m coordinates is defined as:
(01, Um, Um+1 mn) H> (V1,.... 6m)
An affine map from R I" is one of the form
x Ar + b
for some n x m matrix and n-dimensional vector b. The set of affine maps from RT to Ik" can be identified with the vector space (Rom(Rm-1 R"), now explain. First, given and b as above, we form the n x (m + 1) matrix [b A]. Conversely, the affine map corresponding to W e HomeR m+1 R" given by
W = W a extm
RRm
R";
I W (extm (z:)),
where ext, is defined as follows:
Definition B.1. For m 2 1, let
exim IR" Rm+1
be the map taking v (V1, 02.....
Un) E I to (1, 01, U2 Um) E Rm+1
B.2 THE QR DECOMPOSITION
In this section, we recall the QR decomposition and note several relevant facts. For integers n and m, let Hom "pper (R" R") denote the vector space of upper triangular by matrices.
Theorem B.2 (QR Decomposition). The following map is surjective:
((n) x Hom upper (IR m
,RR")
Hom (R ,R))
Q. R
Q
In other words, any matrix can be written as the product of an orthogonal matrix and upper- triangular matrix. When m S n, the last n m rows of any matrix in HomoPer R!) are zero, and the top rows form upper-triangulat m by m matrix. These observations lead to the following special case of the QR decomposition:
Corollary B.3. Suppose S The following map is surjective:
:: (n) X Hom upper (R" th RT)
Hom R") H Q inc o
Q R
We make some remarks;
1. There several algorithms for computing the QR decomposition of given matrix. One is
orthogonalization, and another the method of Householder reflections. The latter has computational complexity O(n²m) m) in the case of n 2 m. The package numpy includes a function minal..inalg... or that computes the
matrix with
QR decomposition of matrix using Householder reflections.
2. The QR decomposition is not unique in general, or, in other words, the map ja is not injec- tive in general. For example, if m, each fiber of y contains copy of O(n ( m).
15

---

Under review as a conference paper at ICLR 2022
3. The QR decomposition is unique (in certain sense) for invertible square matrices. To be precise, let t be the subset of Hom "Pmm (R" ,R) consisting of upper triangular matrices with positive entries along the diagonal. If
then both B and O(n) are subgroups of GL (IR), and the multiplication map (nn) x B, + GT (IR) is bijective. However, the QR decomposition is not unique for non-invertible square matrices.
C SYMMETRY AND GRADIENT DESCENT
In this appendix, establish gradient descent formalism that appears throughout the paper. Addi- tionally, we explain the interaction between gradient descent and orthogonal transformations, which a key aspect of main results.
Fix positive integer p. Let V = IR and L V - IR be a differentiable function Semantically, is the parameter space, and C is the loss function
p is the number of independent parameters, associated to a batch of training data. We write elements of V as tuples, c.g. = (el,....22) Up), or as column vectors. We write elements of the dual vector space / as row vectors. The differential and gradient of L are defined as:
dC : V - HommV, (),
VL:V -V
0C
ac Oxp
U + doL= =
ac
BC Jap
U V
dz
Remark C.1. Suppose that L is in fact a linear map. Then L belongs to V and dC is the constant map taking each E V L. That is, d,L L as maps V + R.
A step of gradient descent with respect L at learning rate 0 is the function
In V -V V BH 1-Uー1 1) VoL
Hence, gradient descent updates the i-th coordinate of v to e 1] da, lo. for i = 1w 1,....P p. When is clear from context, we abbreviate Y, by For any k 2 O, the k-fold composition of y is y* 7000 %,, with 70 being the identity map on V.
ac
Throughout the appendices, all proofs involving gradient descent reduce to the n case. The arguments for general > () and can be obtained either by inserting the scalar 1) where necessary, or by rescaling the function L.
Proposition C.2. Let Q be orthogonal transformation of IR. such that Lo c C. Then, for any v E V and k 2 O, we have:
(V VQ(uf
and
= =
Proof. We give a proof in the case 17 = 1. The general case follows similarly. The hypothesis L o Q L implies that:
V.C (d,2)² ( Q)) Co (o) 2F ()T
= (V))(
where do(w) Q = Q since Q is linear map. The fact that Q is an orthogonal transformation implies
that Q = QT. The first claim follows. For the second claim, we first compute:
(Q()) Q(v) Vo Q(v) CVV.C) Q(v -of--vpp v,C) = (()())
Inductive reasoning shows that 10 (Q(x)) = (()*(()) for all k 2 0.
The following two results are not necessary for the results of the current paper, but may be of interest to readers. We omit the proofs (which are straightforward).
"This discussion extends easily the where L piece-wise differentiable.
16

---

Under review as a conference paper at ICLR 2022
Proposition C.3. Suppose that a group G acts V by orthogonal transformations and that C is
G-invariant. Then there is a well-defined gradient descent map on the set of G-orbits on V
V:V/G + V/G.
Proposition C.4. Let M be a linear endomorphism V = RR such that L M = L.
1. For any V, we huve: V (V
2. M = is an orthogonal projection, i.e. p2 = P= = P then, for any v E V and k: 2 0,
we have:
(t))= p(o) P(0))+((((())))
D THE NEURAL QUIVER
In this appendix, we expand on Section of the main text. We explain in more detail the relation between representations of the neural quiver and affine maps, describe an action of GL hidden on the space of neural networks Neur( Q2, and prove equivariance results related this action. References for general quiver representation theory include (Nakajima et al.) 1998) and (Kirillov Jr. 2016
D.1 THE NEURAL QUIVER
We begin by recalling the definition of the neural quiver. For positive integer L, the neural quiver O2 is the following quiver with 2 vertices:
The vertices in the top row are indexed from i = 0 to i = row the sole input vertex, the last vertex (i L) is the output vertex, and every other vertex (1 < < - 1) in the top row is a hidden vertex. The vertex at the bottom is the sole bias vertex and is connected to each vertex in the top row except for for whose value at the bias vertex is equal to 1. Hence, dimension vector for QL will refer to an (no; RI:..., We now restate and give full proof of
L. The first vertex (i 0) in the top
We only consider dimension vectors
(L+1) 1)-ule of positive integers
Lemma 3.1
A representation of Q1 with dimension vector n is equivalent to the data of affine map - R for each I....,L. L. There is isomorphism of vector spaces:
Lemma D.1. (Lemma 3.1
Rep(O1. n) Hom (R-- I.R.)..
1=1
Proof. By definition, a representation of 2t with dimension vector n consists of the data of matrix A; E Hom "L-1 R" and vector b, E R for each = 1...., . L. For each i, the corresponding A;x b. Conversely, given the data of an affine map
affine map W; R - Th is given by R=.-- - R for each i, the linear part defines an element of Hom(RR (R)) and the translation
part defines an element _ This proves the first claim.
The second claim follows from the discussion of affine maps appearing in Section B Explicitly, given an affine map I + A₁æ b. from Ra to R for each 1,... L, one defines an element of D Hoom(R1tm_2) R*) whose i-th factor is the matrix W, [b, A.). Conversely, pre-composing matrix in Hom(R 1+m,-1, RT)) with the map ext,,., RR: R 1l+ gives an affine map W, from m to g
Notation: In light of the preceding lemma, we henceforth denote representation 2, as a tuple W (W.)& where each W; belongs Hom foom[R1+n.-) 1++ Rm.).
17

---

Under review as a conference paper at ICLR 2022
Recall that the parameter symmetry group GLD Gindden is defined as the product of the groups GLn, (IR) as runs over the hidden vertices of the neural quiver Qz:
L-1
GL
hidden
= II GLm, (R)). i=1
Hence an element of GT hidden consists of the choice of transformation of R for each hidden vertex i. There an action of GL hidden on Rep(QL; n) given by
1
L
W (Wi
g.
9i W.
0
95
i=1
where g
(=)
1-1 an element of GL GLiiddon,
hidden and go id and gL id
D.2 NEURAL NETWORKS
Recall the following definition, which appears as Definition 3.2 in Section 3.4 of the main text, and a special case of the more general Definition appearin below Appendix
Definition D.2. Let L be positive integer. An -u-neural network consists of the following:
1. Hyperparameters. A dimension vector = (no: Ri...., .RL) for the neural quiver QL.
2. Trainable parameters. A representation W (WI, Wr) of the neural quiver
Qr. with dimension vector n. So, for = 1,..., L, we have matrix W; Hom(R (-.-11
3. Activation functions. Piece-wise differentiable functions R
R for
1, 1,... L. These are grouped into a tuple (aI,.... ar.)
As in Section 3.4 we denote by Neur Qr, n) the vector space neural networks with layers and dimension vector n, and define the neural function of neural network (W, a) as:
f(w.): I + R
I ト ar WL 0..00 .2 o W2 o an o Wi(x)
where W, Rm R is the affine map corresponding to W,.
There is an action of the group GL hidden on Neur (2r n) given as follows. The element g = (g.) (o))=== f-1
E GL hidden transforms (W,a)= E Neur(Qu. n) as:
aW + g (W,,a) = ( i
0 9.
L
(0
(D.1)
where 90 idno and 9r. id,,. The following lemma shows that the neural function unchanged by the GI, hidden action, that is, if two neural networks are related by the action of an element in GL hidden then their neural functions are the same.
Lemma D.3. For any neural network (W, a) in Neur(Q1, and any in GI hidden the neural functions of (W, a) and g. a) coincide: (w.) f(W.a)
hidden transforms W. W ext 9, W ext,,., o - and o; to 9i 0; o 9: for 1 1.... I. (where go idn, and gr. idn,). Thus, g transforms the composition definition of the neural function.
Proof. The element g (g:) E GLhhiddo
W; to the compasition g, o W, 9 The result now follows from the
1 0 is block diagonal with one block of size 1 x 0;-1
As in the main text, for each i, the matrix consisting of the single entry '1', and block of size n;-1 n4-1 consisting of the matrix g;-)
0
18

---

Under review as a conference paper at ICLR 2022
We now define certain subgroup of GL hidden that will feature in later discussion.
Definition D.4. The stabilizer in GL GLiiddeen of choice of activation functions is defined
hidden
(a) = (g = -(x) E GT hidden
9: o a2 o Dr = 0g for all = 1....,,..
'n
Note that each a; is function from R to I each gi, so the equality gi a, 9: as is as functions from Ih to I As a subgroup of G hidden the stabilizer ((a) acts on Rep n).
We now recall from Section the formulation of the optimization problem for neural networks in the language of quiver representations. For the remainder of this section, we fix dimension vector for the the neural quiver Qt. and activation functions
(aI...., ar)). ). To a batch of training C 1 x I there is an associated loss function on Rep( (Q,, n) defined as
data X {Z0,, {;)}
L Lx : Rep( QL, n)
((W) = ((((aa)(z)).
where C R R I is a cost function on R Following the formalism of Appendix we obtain a gradient descent map
7: Rep( Qr, n) - Rep((r..
for any learning rate 77 0. Hence:
+ Upshot: the backpropogation algorithm can be regarded as taking place on the vector space Rep( (2. n) of representations the neural quiver Q
To conclude this section, demonstrate that the loss function is invariant for the action of the group (a).
Proposition D.5. Let a be activation functions, and let L be the loss function associated to batch of training data. Then, for all g E (a) and W E Rep(p2 Qt, n), we have:
L(g W) = L(W).
Proof. One first verifies using the definition of Z(a) that:
(g. W, a) = -g ..g....... (W,a)
for any g E Z(a) and W E Rep( Qn, n), where the left-hand side invokes the action of Z(a) on
Rep( Qr., n). while the right-hand side invokes the action of ((a) on Neur(Qr, n). Using this fact
and Lemma D.3 we see that: Jig.W.a) = (g.(W.a) = S(W.a) and hence, for any g E Z ((a) and
E Rep( n.. we have:
C(g Cgg.W) W) = Σ (1) = Σ
L(W).
Remark D.6. An alternative proof is as follows. The loss function can be written as the composition
Rep( Qr., n) "n, Neur(Qr., n) - RR
where the first map takes W to (W, (and hence is a section of the natural projection from Neur( n) Rep( (2 n)), and the second map sends (W, a) to the sum Σ, C(f:w.)) (2,,). yy)- One verifies directly that 5a is equivariant for the action of the group Z(a), while the second map is invariant for GL hidden of which Z Zaa) is a subgroup.
Remark D.7. Suppose a; " R is pointwise ReLU for each i. Then Z(a) consists of those g (g:) GT. hidden such that each g: GT.,; (TR) diagonal matrix with positive entries along the diagonal. In symbols:
L-1
((a)= = II (RRy))
i=1
Hence, the "non-negative homogeneity" (or "positive scaling invariance") property of pointwise
ReLU activation functions appearing in DDin et al. (2017); Neyshhuur et al. (2015); [Mng et al.
2019) emerges special case of Proposition D.5
19

---

Under review as a conference paper at ICLR 2022
E RADIAL NEURAL NETWORKS AND THE QR DECOMPOSIITONN
In this appendix, we give a proof of the main theoretical result (Theorem 4.3 involving a QR de- composition for radial neural networks. To this end, we first collect results about radial functions and radial neural networks.
E.1 RADIAL FUNCTIONS
We first recall the definition of radial functions from Section 4. above. Let h R - R be piece-wise differentiable function such that lim A(r) exists. For any n 2 1, set:
(m) R R";
h (v) = h((vl) |0|
function a 12 + R called radial if h(m) for some R R. Lemma E.1. Let ((())
I + R radial function on IR".
1. The radial function commutes with any orthogonal transformation Rf. for any E (n).
R". In symbols:
Q Qoa
2. m S n and in Im + I nh is the standard inclusion, then:
(m) o inCm,n inCm.n o h (m))
Proof. Suppose Q (nn) is orthogonal transformation of R" Since Q is norm norm-preserving have [Qul = |u] for any v E R". Since Q is linear, we have Q(xv) = XQu for any e and v E R.. Using the definition of a = (n) we compute:
h( Q=l)
h((vl)
|0] 8 (
(b((lo)) Q(a(v)).
a(Qu)=
Qu
Qu Qu=Q
Quul
|o]
The first claim follows. The second claim is an clementary verification.
Remark E.2. More generally, it is straightforward to show that the restriction of the radial function a to a linear subspace of IR" a radial function on that subspace.
Next, we recall the definition of radial neural network (as stated in Section positive integer and be a dimension vector for the neural quiver QL. neural network (W, a) e Neur Qr, n) is said to be radial neural network if each activation function is radial function on R Let (n) denote the following product of the orthogonal groups:
Let L be
(nn) = =(1)) X O(n2) x ... X ((n1-1).
Note that (n) is a subgroup of GT, hidden and hence acts on Rep Qt. n). The following proposition involves the loss function associated a batch of training data as formulated in Section 3.4
Proposition E.3, For any radial neural network Neur (2, 1) and any batch of training data, the loss function L Rep( Q2, n) - R is invariant for the action of Onn).
Proof. Let g (9....., 9L-1) E O(n). Lemma E.1 implies that the orthogonal transformation
9: E ((z)) commutes with the radial function a; = 144,,, for each i, or, equivalently: g:oa, og, ag Hence (n) is subgroup of the centralizer (a), and apply Proposition D.5
For clarity, we restate Construction 4.2 which illustrates the flexibility of radial functions in defin- ing the activation functions of neural network for any given representation of 2g with arbitrary dimension vector.
Construction E.4. Suppose h (hi...., hL) is tuple of functions h4 IR + R, and suppose n n2) a dimension vector for Q1. Consider the tuple of activation functions:
(n) (nn) (nx.)
Any representation W of Qr. with dimension vector defines neural network (W, a (m)) in Definition 3.2 We write simply (W,h) for this network and f(w,)) for its neural function. We assume each b; picce-wise differentiable and the limit lim hxfr) exists.
20

---

Under review as a conference paper at ICLR 2022
E.2 PROOF OF THEOREM 4.3
In this section, we give a proof of the QR decomposition appearing in Theorem 4.3 In order to do so, we make recollections from Section 4.2
Given a dimension vector n = (no: Ri,....,u, nL) for the neural quiver 2r, recall that its reduc- tion nod [njed _njed ....,LLL m is defined recursively by setting n no. then nidd min(n; n 1) for i
1,.... L 1, and finally n nr. We abbreviate Rep( Qr. n) by (ep(n) and Rep( 22. ndd by Rep(n
We also had in Section 4.2 the inclusion e Rep(n - Rep(n), which can be understood in terms of padding matrices with rows and columns of zeros. Another description is as follows. Let X x (X Xz) E Rep(n Then uX); inc; o X; o ;;-1. Indeed, post-composing X; with inc; amounts adding n, n. rows of zeros on the bottom, while pre-composing X, with TT-1
amounts adding n4-1 n columns of zeros on the right.
Fix a tuple h = (fi,..., h of functions h4 R + R. As in Construction 4.2 we attach radial neural network (and hence neural function) every representation of Qr. As reminder, restate Theorem 4.3
Theorem E.S. (Theorem W Rep(n) there exist:
Let n be a dimension vector for QL and fix as above. For any
QE),n,;
.Ri...., R1) E Rep(n
and
U Rep((n)
such that:
1. The malrices R....., Ri.-1 are upper Iriangular.
2. The following equality holds: W = =Q-1 QQ)(R)-
3. The neural networks defined by W and R. have identical neural functions: f(w h)) f(R.)).
Before stating the proof, first adopt all notational conventions of Section 4.2 especially those listed after the statement of Algorithm Additionally, we note the projection maps:
T
R
RTM
# RR+n
R 1
onto the first ned and + nod coordinates, respectively. We also have the identity:
idn,+1 Pt-1 + inc; 7
(E.1)
Next, we collect the following basic identities related to the map ext, R" > 1 (see Definition B.I) taking (V1,..., vn. to (1, ,,, U.)) Their proofs are elementary.
Lemma E.6. For S have: ext, incm.. inc 1,141 extm-
1 0
Lemma E.7. For any m matrix A, we have ext, A
A
extm
Proof of Theorem 4.3 We claim that the outputs Q. R. and U of Algorithm I satisfy the required
conditions. The matrices Ri...., R2-1 are upper-triangular by construction, so the first part of the theorem holds.
To show that the neural functions of (W, h) and (R, h) coincide, we first show that, for all i 1,..., L, we have:
(m)) o W, o Qi-1 inc, 1 = Q; a inc, o (xt o R
(E.2)
"The matrix :o
0 A (n 1) 1)x (m 1), so the top right abbreviates of and the bottom
left abhreviates column of
21

---

Under review as a conference paper at ICLR 2022
where Qu id and Q2 idn..- The justification is computation:
1/m) W, Qi-1 inc;-1 = (1)) W; extn;-1 Qi-1 inc;-1
= =h(nd Wi
0
inc ext
Qi-1
= (m)) Qi o inc, o R4 ext, ext = Qi o inc; o h (m o R.
The first equality uses the definition of W. in terms of W;; the second uses the commutativity properties of ext stated in Lemmas E.6 and E.7 the third uses the definitions of Qi, R4, and Vi; and the fourth uses the commutativity properties of radial functions as well as the definition of R. The fact that h) /R.. h) now follows from the definition of the neural function and iterative applications of Equation F.2. noting that Qo inc, = id and QL o inc, idna.
Finally, to show that W Q (R) + U. we compute, for i = 1....,,. L:
(Q (R) U) (Q 1 (R.) + U;
1
1
0
Qi inc; R, -
0
0-11
W3
0
Qi-1
Pi--1
0
Q
0
1
0
W
0
Qi-1
inc, T
Q
0
1
0
+ W.
Qi-1
Pi-18
W
1
0
[inc,-1 o 7 Pi-1
1
0
Qi-1
0
Q
0
11 0 Q
1 0
W2
id +m
Qi-1
The first two equalities follow from definitions; the third uses the definitions of Qi, R. and V;; the fourth uses the distributive law; and the fifth appeals to the Equation E.1
F PROJECTED GRADIENT DESCENT
In this section, we give proof of Theorem 4.7 which relates projected gradient descent for repre- sentation with dimension to (usual) gradient descent for the corresponding reduced representation with dimension vector ned
We adopt all notational conventions from Section In particular, we fix:
a tuple h = (hi,..., hz) of functions, where h;;
R for = 1,..., L. These can be used define neural function f(w,b) (resp. ((x,h) for every representation W in Rep(n) (resp. X in ())). See Construction 4.2 for more details.
batch of training data {(rj 15)) C RR.00 R Red x RoE
a cost function R x _ + R
As result, we have loss functions on Rep(n) and Rep(n given by:
L: W + Σ ECUfwn)(E)))
Rep(n) + IR
Lied Rnd(n I
as in Section 3.4 Fixing learning rate 17 > 0, there are resulting gradient descent maps on Rep(n)
and Rep n given by:
Rep(n) + Rep(n)
Tre Rep(n - Red(
W. ト W 1 VwL
X - X 11 Vx
22

---

Under review as a conference paper at ICLR 2022
F.1 THE INTERPOLATING SPACE
In this section, we introduce subspace Rep ntt (n) of Rep(n). that, as we will later see, interpolates between Rep(n and Rep(n).
Recall the standard inclusions and projections, for = 1, 1,...,,.:
inc; inc az mn
Ra
RR
inc; inc 1tn, R Rl
< IR tm;
Wy R
R
म. R R R
Definition F.1. Let Rep"h((n (n) denote the subspace of Rep(n) consisting of those T (T....., TT) E Rep(n) such that:
(idn, inc; me) T; inc;- 1 m:-1
for 1, 1,...,,. Write 4 Rep int (n) + Rep(n) for the natural inclusion.
In other words, the space Rep int (n) consists of representations T .T....,TT)) Rep(n) for which the bottom left (n, ne
x (1 (1+17 -n block T; is zero for each i:
T;
We omit the proof of the following proposition, as it involves an elementary analysis of the workings of Algorithm
Proposition F22 Let W E Rep(n) and let Q R, and U be the outputs of Algorithm so W Q U. Then the representation Q-1 -. = (R) + Q-' U belongs to Rep int (n).
Definition F.3. Define map
91 : Rep(n) - Rep (n) by taking T E Rep(n) the representation whose i-th slot
W (idn; inc, o n;) o W inc;-1 #;-1-
is straightforward to check that is well-defined, i.e., that the resulting representation belongs to Rep" (n) and that di surjective linear map. The transpose of is the inclusion 41- We summarize the situation in the following diagram:
Rep int (n)
Rep(n)
(FI)
We observe that the composition o is the identity on Rep" (n), while the endomorphism 41 o Q1 of Rep(n) takes representation W E Rep(n) and, for each i, zeros all entries in the bottom left (n; nedd x (1 + nted)) submatrix of W,.
F.2 PROJECTED GRADIENT DESCENT AND THE QR DECOMPOSITION
In this section, we define the projected gradient descent map and state a theorem relating projected gradient descent on Rep(n) with usual gradient descent on Rep(n
Definition F.4. The projected gradient descent map on Rep(n) with respect to Rep (n) at learning rate 7 < 0 is defined as:
Yproj: Rep(n) + Rep(n)
W W -n Pr(V
where Pr Q1.
23

---

Under review as a conference paper at ICLR 2022
One verifies easily that the above definition of projected gradient descent is the same that given in Definition 4.6 To reiterate, while all entries of each matrix W; the representation W contribute to the computation of the gradient Vw only those not in the bottom left submatrix get updated under the projected gradient descent map "praj-
We now restate Theorem 4.7 To ease notation, we identify elements Rep(n with their images in Rep(n) under
Theorem F.S. (Theorem 4.7 Let W E Rep(n) and let Q R, and U be the outputs of Algorithm ? Fix a learning rate 7) > For any 2 0, we have:
* (W) Q 7 (Q-1 W)
and
(Q- W) = * (R) + QQ- Pou
k
We summarize this result in the following diagram. The left horizontal maps indicate the addition of Q Q-11_01000000 U, the right horizontal arrows indicate the action of Q, and the vertical maps are various versions gradient descent. The shaded regions indicate the (smallest) vector space to which the various representations naturally belong.
Rep(n
Rep int
(n)
Rep(n)
+Q +Q-1. 11-1.
Q
R
GD Rep(n (l)
Proj-GD Rep(n)
GD Rep(n)
GD on Rep(n)
(
Q
W)
* (Q W)
> >g (W)
/ed
1,
proj
Remark F6. The map Rep(n) + Rep(n) taking W to Q Pproji W) is projected gradient
descent map on Rep(n) with respect to the subspace of Rep(n) formed by translating Rep"" (n) by the action of Q i.e. the subspace Q "ep (n) Q T T
F.3 PROOF OF THEOREM
We begin by explaining the sense in which Rep int (n) interpolates between Rep(n) and Rep(n
One extends Diagram F.I as follows:
41
Rep(n
Rep
int nn)
Rep(n)
92
91
The map
22 Red(n + Rep"" (n)
takes X to the representation whose i-th coordinate ine; o Is straightforward to check that is well-defined injective linear map.
The map
/2 Repin
int (n) - Rep(n
takes T the representation whose i-th slot is T; inc;-1- check that is surjective linear map. The transpose of q2 is the inclusion
1. It is straightforward
Lemma F.7. We have the following:
24

---

Under review as a conference paper at ICLR 2022
1. The inclusion R - Rep(n) coincides with the composition i1 bg and com- mutes with the loss functions:
Rep(n
06g
(n)(n)
Lnd
2. The following diagram commutes:
Rep
(n)
92
Rep( (n tdd
Exd
(np(n)
4
R
3. For any T E Rep""((), we have: q1 (V,,(T)C) 12 (T)
Proof. The identity = 41 o l2 follows directly from definitions. To prove the commutativity of the diagram, is enough to show that, for any X in Rep(n the neural functions of X and ((X) coincide. This follows easily from the fact that, for = -1, 1,..., I., we have:
ng h (24) inc; n. inc; h(()))) h (m("")))
For the second claim, let T Rep int (n). It suffices to show that 41 (T) and (T) have the same neural function. The key computation is:
inc, h ((( mm T. inc; (14) inc; m. ext,,- inc;-1
h(ms) inc, T, inc o ext
h(me) inc; o exta;-1
(m.) Ti ext o inc;-1
(m4) T, inc;
which uses the fact that (id.,; inc, o 7,) o oine;- 0, or, equivalently, inc, o m oT inc, o
T, o inc Applying this relation successively starting with the second-to-last layer (i = 1) and ending in the first (i = 1), one obtains the result. For the last claim, one computes Vr(Cou)
in two different ways. The first way is:
Vr (dr (Con))² (d) oodu)) (ou))
= (()) qı (VarryC)
where use the fact that i is linear map whose transpose Qı The second way uses the commutative diagram of the second part of the Lemma:
Vr(Con) = V (Cred o 92) = (dr (Cred q2)) = (T) dzg2)"
(dga Frod o 02)² = ob (ree) = 12 (Vos(T)Lro))
We also use the fact that Ø2 is a linear map whose transpose is 12.
Proof of Theorem 4.7 The action of Q O(n) on Rep(n) is an orthogonal transformation, so the first claim follows from Proposition C.2 For the second claim, it suffices to consider the case = 1. The general case follows similarly. We proceed by induction. The base case h 0 amounts to For the induction step, we set
Theorem 4.3
(k) 1 (R)) + --1 U.
25

---

Under review as a conference paper at ICLR 2022
Each ( belongs to Rep int (m)) so 1 (Z = (h) Moreover, 92 (Z - (R). We compute:
(n),
R++1 proj
(Q
QQ_ W) Prroj (1 (Q W))
Pproj (1(7hol (R)) -- U)
( (R)) + Q-- U 91 (V (1)+
((Trea (R)) ub (V (V.(2()) C) Q-1QQ.1. .
(Thied (R)) 1 (g)) fee) +Q +Q-
(The (R) V (R) Q
k+1 1. (Trell (R)) + U
where the second equality uses the induction hypothesis, the third invokes the definition of "peuj- the fourth uses the relation between the gradient and orthogonal transformations, the fifth and sixth use Lemma F.7 above, and the last uses the definition of Tred.
F.4 EXAMPLE
We now discuss an example where projected gradient descent does not match usual gradient descent.
Let (1,3, 1) be dimension vector for the neural quiver Qz. The space of representations with this dimension vector is 10-dimensional:
Rep(Qu, n) Hom IR? R²) @ Hom R) R0.
We identify a representation
Fa
b7
11) Rep(Qr, (1,
w = Wo
=
c
d
W = 9 h
(1,33)
f]
with the point (a, b, c, d, f, i, in Ro
The action of the orthogonal group O(n) =
0(3) on Rep( n) R110 can be expressed as:
0
Q
0
0
0
0
Q
Consider the function
L: Rep(p Qr.. + R
p= p= b, c, d, e, f.g. h, + h(a + b) + i(c + +j(e+ tg
By the product rule, we have:
vpC
+,
One easily checks that L(Q p) = L(p) and that VorC= Q vpL for any Q E 0(3).
The interpolating space the subspace of Rep( Qr, n) ~ R with = f Suppose p' (a, b, d, 0. 0, h, belongs to the interpolating space. Then the gradient is
vp (h, h, i, i. 1, + b, e + d,
which does not belong to the interpolating space. So one step of usual gradient descent, with learning rate 77 > yields:
p' = b. c, d, 0, h, i, +
nh. b nh c ni 1pi 7j
75 9 17 h 1/aa + b) 7/cc + d) j)
For W E Rep(@z. n). the neural function of the neural network with affine maps determined by W and identity activation functions is R + R; L(W)x. zr. The function C can appear loss function for certain batches of training data and function IR.
26

---

Under review as a conference paper at ICLR 2022
On the other hand, step of projected gradient descent yields: Pproj p' = (a, c, d, 0, 0, 9. h, i, (a (a- nh. b 1//,
171 d -
r 6), i- --ccc ,
Direct computation shows that the difference between the evaluation of after one step of gradient descent and the evaluation of L after one step of projected gradient descent is:
L(>(p)) (Pirro (p') 2nj².
G QUIVER NEURAL NETWORKS IN GENERAL
In this section, we generalize some of our main results to a larger class of quivers beyond the neural quiver. These more general quivers are known as "neural-adapted quivers", defined presently.
G.1 NEURAL-ADAPTED QUIVERS
Definition G.I. A neural-adapted quiver is a quiver Q = F)) together with partition / In BUUUUU H {iar] the vertex set such that the following hold:
1. The quiver Q is acyclic and no two edges share the same source and target.
2. The vertex oor the unique sink of Q. This the output vertex.
3. The set Ii is non-empty, and every vertex therein source of Q. These are the input vertices.
4. Every vertex in B is source of Q. These the bias vertices.
5. Every vertex in H is neither source nor sink, and admits path from input vertex. These are the hidden vertices.
Given a quiver satisfying condition (1) above, and with unique sink, one can partition its vertex set in order to give it the structure of a neural-adapted quiver. This can be done, for example, by setting In to be the set of sinks, // to be the non-sink and non-source vertices, and B to be empty. In general, there are many possible partitions, since some sources can be input vertices and some can be bias vertices (keeping in mind that any hidden vertex must admit path from a input vertex). As a final note, we observe that an acyclic directed graph with unique sink must be connected. Example G.2. We list examples of neural-adan -daptedd quivers:
1. The neural quiver with five layers:
One can see that there is a unique ccural-adapted structure on this quiver. Namely, the unique sink is the output vertex, the source on the far left is the sole input vertex, and the source on the bottom the sole bias vertex. All other vertices hidden vertices, and each admits a unique path from the input vertex.
2. The no-bias neural quiver with five layers:
There is unique neural-adapted structure on this quiver, and it has the property that the set of bias vertices is empty.
3. A skip-connection neural quiver with five layers:
Once again, there unique neural-adapted structure this quiver.
27

---

Under review as a conference paper at ICLR 2022
Given neural adapted quiver, exclusively considers dimension vectors whose value the bias vertices is equal to 1. Thus, dimension vector for neural addaaed quiver amounts to a tuple non- negative integers indexed by the vertices in / B In UH U (fom). We abbreviate dm := Σier, d; and dam == diaa.
Remark G.3. As a directed acyclic graph, a neural-adapted Q has a "topological ordering" of the vertices. In what follows, we will be implicitly be choosing enumeration {ii..... }زri of the set of vertices that is compatible with the topological ordering. That is, if i < ē in the topologiaal ordering, then j < j'. In particular, iil) fout- Furthermore, will assume all source vertices (that is, those in Im U B) appear before all non-source vertices. Hence,
= Yout)
an enumeration of the non-source vertices.
Additionally, whenever necessary, we will implicitly fix an enumeration of the edges (e El1) For example, this occurs in the following definition:
Definition G.4. Let W be a representation of a neural-adapted quiver Q with dimension vector d. For each vertex in H U (row), set W; to be the following matrix:
W; = [ W...
where fel,..., = (i) is is the set of edges whose target is i. Note that the size W; is d2 x (dj + dj.).
Lemma G.5. Let be quive and fix an enumeration of the edges. Specifying a representation of Q with dimension vector d is the same specifying a d, x (dj, t... dz.) matrix for every non-source vertex i.
G.2 --NEURAL NETWORKS
We now define the notion of Q-neural network, that is, neural network whose underlying archi- tecture is specified by a neural-aae cauaae- quiver. Definition G.6. Let Q be a neural-adapted quiver. Q-neural network consists of the following:
1. Hyperparameters. dimension vector for the quiver Q
2. Trainable parameters. A representation W of Q with dimension vector d.
3. Activation functions. Piece-wise differentiable functions a; : Rdd Rd. for H }. These are grouped into a tuple a.
We denote by Neur( d) the vector space of Q-neural networks layers and dimension vector d, and regard elements therein as pairs a). The neural function (also known the feedforward function) Q-neural network defined recursively, as explained
following definition.
Definition G.7. Let Q be neural- adapted quiver. Let (W.a) be Q-neural network with dimen- sion vector d. For every non-bias vertex E I, define function:
(.) ft 12 gd
by setting:
If is an input vertex, fo is the projection map.
If is bias vertex, fi = is the constant function at 1 E Rd: IR.
For all other vertices, we use the recursive definition: fi(x) a; (Iyse Wo Sz(x))
The neural function of the neural network (W,a) is defined as:
f(w,)) := fr.. Rd ddo
"This works for any quiver, and particular for neural-adanted quivers
28

---

Under review as a conference paper at ICLR 2022
Note that the neural function is well-defined due the topological ordering of neural-adapted quiver, regarded as a connected directed acyclic graph. Indeed, one can implement this definition using ordering of the vertices compatible with the topological ordering (see Remark (.3).
Definition G.8. Let W be representation of neural-adapted quiver Q with dimension vector d. Let be a non-source vertex 1o of 2. Let (ei....,e,, e t- (i) be the (ordered) set of edges whose target is and let ji be the source of e1, f2 of e2, and so forth.
1. Set W; to be the following matrix:
W; [Wa, We,1
Note that the size of W; is de (dj, +... + dz.).
2. For x E RR,, set f. (a) be the following vector:
fn (x)
(x))
[3,((t)
Hence, f1"((() is column vector of dimension (di +... + dj.).
The proof of the following lemma is elementary.
Lemma G.9. Let (W, a) be a representation of a neural-adapted quiver Q. For any non-source
vertex E I, we have:
(z) = We 1 (W.)) (x)
G.3 SYMMETRY GROUP
Throughout this section, we fix neural-adapted quiver Q with partition / - 7n LLUUUU {fame) of the vertex set as described above.
Definition G.10. The parameter symmetry group for representations of neural-adapted quiver Q with dimension vector is:
GL
hidden
II GLd,
iE
This group acts on Rep( Q, d) as:
W = (r(e)) W. gate)
This group acts on Neur( Q, d) as:
g (W, = (((e) We gole) (g: a; 9, 9;
In both cases, by convention, have 9: idd, for any non-hidden vertex i.
Remark G.11. Following the notation appearing Definition G.4 we have that g E GL hidden transforms the matrix W; corresponding to vertex i to:
9 0
0
0
9
0
W,
95r
We have the following generalization of Lemma D.3
Lemma G.12. For any neural network (W, a) in Neur Q, d) and any in GL functions of (W, a) and g (W,a) a) coincide:
hidden the neural
(W.)) = f(w.))
The non-source vertices precisely H (fom).
29

---

Under review as a conference paper at ICLR 2022
Sketch of proof. It suffices show that: (W.a; 9: (W..) for all vertices i, where, by convention, 9: = ids, for non-hidden vertices. One proceeds by induction using the topological ordering of the quiver, viewed connected directed acyclic graph. The base step is when is bias or input vertex. The induction step involves the following calculation:
(s) = = aa oi
Eg jSi
gi We o o o gj Ssiwaa)(x)
= 9: o a, Σ S
We (s(waa(o)) 91 ())
Alternatively, one can use the matrices W; and Lemma G.9
Definition G.13. The stabilizer in GL
hidden of choice of activation functions is defined as:
(a) {g (g:)
GLa
hiddee
9: o a 9; a; for every hidden vertex i}.
Note that each a; is a function from Rdd to R as is each gi, so the equality gi o a; 9; = a, is as functions from I4 to R As a subgroup of GL
hidden the stabilizer ((a) acts on Rep(2,d).
G.4 THE LOSS FUNCTION
For the remainder of this section, we fix neural- addptee quiver Q and a dimension vector for Q. Furthermore, fix activation functions a (a, Rd - IR4) one for each hidden vertex, and one for output vertex. To a batch of training data = {(x). vi)3 C Rda x Rda, there an associated loss function on Rep( Q d) defined as
L = Lx Rep(2, +R
c(W) = Σ (CU(aa)(t)))s)))
where C Rdm x Rd
IR a cost function. Following the formalism of Appendix C we obtain
gradient descent map
Y : Rep( Q, d) - Rep(Q., d)
for any learning rate 17 >
We demonstrate that the loss function is invariant for the action of the group Z(a). We omit a proof
of the following proposition, as is completely analogous that of Proposition D.5
Proposition G.14. Let be activation functions, and let L. be the loss function associated to batch of training data. Then, for all g E 7(a) and W E Rep( Q, d), we have:
A(g. W) = L(W).
G.5 RADIAL Q-NEURAL NETWORKS
Suppose h = (hi,..., hL) is tuple of functions h; - R, and suppose d is dimension vector for neural-adapted quiver Q. Consider the tuple of activation functions:
(n) = h (d.)
where runs over H U fiouth Any representation W of Q with dimension vector d defines radial neural network (W, a( (())). We write simply (W, h) for this radial neural network and f(w,)) for its neural function.
The following definition implicitly invokes the topological ordering neural-adapted quiver, re- garded directed acyclic graph. Recall that, as always, the dimension vector of neural-adapted quiver has value 1 on each bias vertex.
We assume each b; piece-wise differentiable and the limit lim Bxfr)) exists.
30

---

Under review as a conference paper at ICLR 2022
Definition G.15. Given dimension vector d for neural-adapted quiver Q, one defines the duced dimension vector d as follows. First, diat d, for every In U B. Next, for any hidden vertex i, recursively set didh be minimum of d, and Ejer, dood Finally, doed dow for the output vertex.
There is an inclusion & Rep(Q. 2, d - Rep(2 Q, d).
Definition G.16. Let d be dimension vector for a neural-adapted quiver @. Define subgroup of GL. hidden follows:
O(d) II O(d). iE
We state the following conjecture:
Conjecture G.17. Ler d be dimension vector fora neural-adapted quiver Q and fix h as above. For any W E Rep(Q, Q, d) there exist:
Q O()),
R = (R1, ........ Rt)= E Rep(Q, d
and
U E Rep(R. Q, d),
such that:
1. The matrix R; is upper triangular for any hidden vertex i.
2. The following equality holds: W = Q Q
3. The neural networks defined by W and R. have identical neural functions: f(w.)) = f(R.b)-
Moreover, we conjecture that a generalization of Algorithm T produces R, Q and U from W. We first make the following notes:
Fix an enumeration i 1 the set / of vertices that is compatible with the topo- logical ordering, as in Remark G.3 Furthermore, we will assume all source vertices (that is, those Im in U B) appear before all non-source vertices. Hence,
is enumeration of the hidden vertices.
Fix an enumeration of the edges of Q. Hence, a representation of Q with a specified dimension vector can be regarded either as tuple W (We)e of matrices indexed by the edges, or as a tuple of matrices W (W₂), of matrices indexed by the vertices (see Lemma G.5 We use the latter formulation in the algorithm, except for one step.
It is enough produce R. and Q, subsequently set: U W Q R.
31

---

Under review as a conference paper at ICLR 2022
Algorithm 2: General version of QR Dimensional Reduction (@RDimRed)
input W E Rep(Q, d)
output : QQ, R
Q. < [],[]
// initialize output matrix lists
for j < Lil + [B] + to 11 do
// iterate through hidden vertices
i i- 1
// current vertex
if cided < d, then
Q,, R₁ + QR QR-decomp (V, mode complete)
// V = Q; o inc, R
else
Q1, R, + QR-decomp (V))
// V, Q1 R
end
Append Q; to Q Append R; to for such that s(e) do
// reduced weights for layer i // update next layers
We - W&Q. Q
end end
Append Wi.. to R return Q.R
"In terms delexing-by-vertien have that (()) gets updated the product of Wi(e) and the block di- agonal matrix Diag(id,... ., Q.,...,id id), with the identity matrix (of the appropriate size) in cach block, except for the block corresponding to which has Q; Note that we have fixed an ordering of the edges.
H DISCUSSION
In this section, we first consider how framework specializes to the of no bias, and then how generalizes to shifts within the radial functions.
H.1 SPECIAL CASE: NO-BIAS VERSION
We now consider neural networks with only linear maps between successive layers, rather than the more general setting of affine maps. In other words, there are no bias vectors.
Let L be a positive integer. The no-bias neural quiver Qg is the following quiver with vertices:
A representation of this quiver with dimension vector n (no. nL) consists of linear map from " to RD for i 1,... L; hence Rep(Qr, n) + + Hom R ,*)). The corre- sponding no-bias reduced dimension vector ne (n ned ................................ n is defined recursively 1. and finally فلा ng- Since Dz.0 < n: for all i, we have an obvious inclusion Rep Q2, r + Rep Q2, and identify Rep( Qr T red with its image in Rep( (Q, n). Given functions h (fu ,,,,,, ), one adapts Con- struction
by setting Thp no. then नाप min(n; (eيn) for i I,...,
4.2 to define a radial neural network for every representation of ęt. where the trainable parameters define linear maps rather than affine maps.
Proposition H.1. Theorem 4.3 holds with the neural quiver replaced by the no-bias neural quiver Ωr. and the reduced dimension vector replaced by the no-bias reduced dimension vector n red
We illustrate an example of the reduction for no-bias radial neural networks in Figure 5 (which is the same as Figure 3). Versions of Algorithm and Theorem 4.7 also hold in the no-bias case, where one uses projected gradient descent with respect to the subspace Rep (Qz, n) of representations T having the lower left (n: mddd) (n block of each T; equal to zero.
32

---

Under review as a conference paper at ICLR 2022
Figure 5: Parameter reduction in 3 steps. Since the activation function radial, it commutes with orthogonal transformations. This example has I. 3, (1,4, 4, 1), and no bias. The reduced dimension vector n 11,1,1,1 1). The number of trainable parameters reduces from 24 to 3.
Example H.2. We give an example where projected gradient descent does not match usual gradient descent. This example is simpler version of that appearing in F.4
Let n (1. 2, 1) be a dimension vector for the no-bias quiver Qr. The space of representations with this dimension vector is 4-dimensional:
Rep( Qz, n) Hom((R, RR² @ Hom (R², R) R
We identify a representation
a b
Wi |c d) Rep( (i,, (1,2,1)
W
Wo
with the point p (a, b, c, d) in R..
The action of the orthogonal group O(n) O(2)
Rep n) ~ R² is the diagonal action:
0 0
Q +
To be explicit: Q = cos 0)
00)
is an orthogonal transformation, then Q (a, b, b.
sin (0)
cos( ())
(a cos(O) b (inn(()) (i))(()) + b cos( (0), c (0) (sin dcoss))).
Consider the function
C Rep Q, Rep(@2. n)
= (a, b, d) + ac + bd
By the product rule, we have:
V,C (c (c, d, b)
One easily checks that L(Q L(p) and that V = Q Vpf for any Q E (()).
The reduced dimension vector is ee 11, R22 The reduced version of L is given by:
1,,11,), 1), so Rep Or, m Hom (R, IR) ( Hom (R, R) =
Lred Rep( Qr,, m + R
(a,c)
The QR decomposition of the representation W corresponding p = (a, b, c, d) is:
(va2+ 0, ac bd
0) + (0. 0, abd + b²c
a²d abc
ba,b,c,d) QQ
Va² + b2 .
a² + b2 a² + 82
a b
where Q Va
The interpolating space is the subspace of Rep Cr. n) R² with 0. Suppose p' = (a, c, belongs the interpolating space. Then the gradient is
v d, 0)
Fo W E Rep(@z,, n). the neural function of the neural network with affine maps determined by W and identity activation functions is R R; J. L(W)... The function C can appear loss function for certain batches of training data and function IR.
33

---

Under review as a conference paper at ICLR 2022
which does not belong to the interpolating space. So one step of usual gradient descent, with learning rate 7j > 0 yields:
Y ::p (a, 0, c, d) (a ncc -njd c nja d)
On the other hand, one step of projected gradient descent yields:
Prrjj p' (a, 6, c, d) + (a TJc, 0, The difference between the evaluation of after one step of gradient descent and the evaluation of L after step of projected gradient descent is: L(v(p')) - (p')) )) ac r7(a² + c² d²) + (ac) ac n1a² + +²) (f(()) =nd?
d)
H.2 GENERALIZATION RADIAL NEURAL NETWORKS WITH SHIFTS
In this section we consider radial neural networks with an extra trainable parameter in each layer which shifts the radial function. Adding such parameters allows for more flexibility in the model, and (as shown in Theorem H.4) the QR decomposition Theorem 4.3 holds for such radial neural networks.
Let h : R + R be a function 13 For any n 2 and any E R, the corresponding shifted radial function Ri given by:
((.d) M[Iu] 1)
The following definition is a modification of Definition 3.2
Definition H.3. radial neural network with shifts consists of the following data:
1. Hyperparameters. positive integer L and a dimension vector (no, 11, 72..... nL)) for the neural quiver Qr.
2. Trainable parameters.
(a) representation W (WI,.... W of the quiver Qr with dimension vector n. So, for i = 1,..., L, we have a matrix W. E RRm,
(b) A vector of shifts (f1, tL) R
3. Radial activation functions. tuple h (h1, he,..., ht., where h; : R R. The activation function in the i-th layer is given by a; ((n.)) TR Rd for 1,..-;4. L.
The neural function of radial neural network with shifts is defined as: f(w.th) : IR + R"
+ (o) o Wt o ... (ma.ta) W₂ o h (mndt)) o W (x)
where W, = W; ext,... R + R is the affine map corresponding to W, The trainable parameters form the vector space Rep(n) + RL, and the loss function of a batch of training data is defined as
L= Lx Rep
R R;
(W,t) - Σ [C(fwam((z)))
We have the gradient descent map:
? Rep(n) + R- - Rep(n) + R
which updates the entries of both W and The group O(n) = 0(m) x x O(nL-1) acts on Rep(n) as usual (see Section 4.1 and on R. trivially. The neural function is unchanged by this action. We conclude that the (n)) action on Rep(n) @ R4 commutes with gradient descent 7.
We now state a generalization of Theorem 4.3 for the case of radial neural networks with shifts. We omit a proof, as uses the same techniques as the proof of Theorem 4.3
We also assume h is piece-wise differentiable and exclude those for which the limit lim, A(r-t) does exist.
34

---

Under review as a conference paper at ICLR 2022
Theorem H.4. Let be dimension vector for Qn and fix functions h (hi,.... h2) above. For any W E Rep(n) there exist:
Q QEO(n),
R = (Bl...., R1) E Rep(n"
and
Rep(n),
such that:
1. The matrices By...., RL-1 are upper triangular.
2. The following equality holds: (W,t) (R,,,t)+(U,))
3. The neural functions defined by (W, t. h) and (R, t. h) coincide: f(w,t,)) = ((R,t,h)-
One can use the output of Algorithm to obtain the Q. R. and U appearing in Theorem H.4
Theorem 4.7 also generalizes to the setting of radial neural networks with shifts, using projected (ep""((n
gradient descent with respect to the subspace Rep" (n) @ Re of Rep(n) R..
I CATEGORICAL FORMULATION
In this appendix, we summarize a category- -hhooreticc approach toward the main results of the paper. While there no substantial difference the proofs, the language of category theory provides conceptual clarity that leads to generalizations of these results. References for category theory include Pierce [991]); Dummit & Foote (2003).
1.1 THE CATEGORY OF QUIVER REPRESENTATIONS
In this section, we recall the category of representations of quiver. Background references include Kirillov Jr (2016); Nakajima et al. 1998).
As in Section let O (T, F)) be quiver with source and target maps 8, E T, and let 1 Zoo. + de be a dimension vector for Q. Recall that a representation of Q with dimension vector consists of tuple A (Ae)eE of linear maps, where
Ae RAto Rdd))
Let A and B be representations of the quiver Q, with dimension vectors d dim( and = dim(B). A morphism of representations from A B consists of the data of linear map
a : R + R
for every E I, subject to the condition that the following diagram commutes for every e E E:
Bdo)
R.dete)
aa(e)
aste)
R kote)
B.
Rektte)
The resulting category R(Q) is known the category of representations of Q.
I.2 THE CATEGORY I(QL)
In this section, we define a certain subcategory I(Ωr) of the category R(Q2). Its objects are the same the objects of R(Qr), that representations of the neural quiver, while morphisms in I(Qr) are given by isometries.
Let L be a positive integer, and recall the neural quiver 2, from Section 3.2
35

---

1-1, the linear map a, R" R. is norm-preserving, i.e. la:(v)] |u] Under review as a conference paper at ICLR 2022
As reminder, the vertices in the top row indexed from to i L. and we only consider dimension vectors whose value at the bias vertex is equal to 1. So a dimension vector for Oz will refer to tuple (No, R1. ......,......................... nr)..
Recall the isomorphism
(ep n)
Hom 11-1 R")
from Lemma 3.1 We denote representation of Qr as tuple W = (W;) where each W; belongs to Hom , I... Let X = (X;) be a representation of 2, with dimension vector m. Tracing through the proof of Lemma [.1] and the definitions in Section I.1 we see that
morphism X - W in R(Q1, consists of the following data:
a linear map Oi IR + R"; for = 0, 1,... L, and
a scalar ag E R at the bias vertex,
making the following diagram commute, for i 1, 1....,,I. L:
R R1+mp-1
g
0
W.
12
Definition I.1. We define a subcategory I(Q)) ) of R(Q2) as follows. The objects of I((2) are the same as the objects of R Q2), that is, representations of Qz. Let X and W be such representations, with dimension vectors m and n, respectively. A morphism a X - W in R(2r.) belongs to I(Qr.) if the following hold:
ng mg and or is the identity on R
n my and az is the identity on R
for
for all I and
0b 1.
Remark 1.2. A norm com-preeerrvnng map is called an isometry, which explains the notation I(Qr).
Lemma I.3. We have:
1. The category I(Q,) a well-defined subcategory of R..
2. Let a W be morphism in I(Qt). Fori 0, ..... LT the linear map og R
IR is injective.
Proof. The claims follow from the facts that (1) the composition of two norm-preserving maps is norm-preserving, and (2) any linear norm-preserving map is injective.
Definition 1.4. Let a X W be morphism in I(Qr.,, and let dim (X) and dim (W) be the dimension vectors. An orthogonal factorization of a; is an element Q = (Q......0) QL-1) of ((n) (mz)
O(nL-1) such that
0; Q inc
for 1, I....,L L 1. The correction term corresponding orthogonal factorization is:
U- W Q x.
The correction term belongs to Rep n).
Remark L.5. Orthogonal factorizations always exist, since any norm- comm-rreseriin linear map R. I can be written the composition incm,, for some orthogonal E O(n).
36

---

Under review as a conference paper at ICLR 2022
Remark L6. Suppose is morphism in I I(Q)). For i (l,...,L - 1}, the map a; is an isomorphism and only m, = n4. In this case, the choice of Q; unique and U/+1 = 0. Conversely, a; is not isomorphism if and only if m, n2. In this case, there are O(n m,) choices for Qi-
R for ....,, L. Hence we obtain radial functions h( R" R for any π 2 1. We group the h into tuple h (hi..... hL). Given h, we attach neural network (and hence a neural function) to every object in I(QL) as Construction 4.2
Fix functions h4
Proposition 1.7. Let X and W be representations of QL. Suppose there is a morphism in I(QL)
from X to W. Then the neural functions of the radial neural networks (X, h) and (W, h) coincide:
f(x f(w,h)-
Sketch of proof. The key is show that, for 1,.... L, we have:
h (mx) W
0 a h (m.) X;
0:-1
where W; and X, are the affine map corresponding to W; and X,, The first step in the verification of this identity is to choose an orthogonal factorization of a. The rest of the proof proceeds along the same lines as the proof of Equation F.2 in Section F.2
1.3 PROJECTED GRADIENT DESCENT: SET-UP
In this section, we collect notation necessary to state results about projected gradient descent.
Let m = (mo...., .... m.) and n (Mo...., be dimension vectors for Qr. We write m
mg no and m, = nL
m; S n, for i = 1,..., L 1.
Consequently, a X + W is a morphism in I(Qr), then the dimension vectors satisfy dim(X) N dim(W) For n, we make the following abbreviations, for i 0, 1,...,,.
inc; = incm.m. R. + R
inc; inc Rl+me - 2+
R Th + Rm.
n. 1+n 1+m
Using these maps, one defines an inclusion u: Rep(m) + Rep(n) taking X = (Xi,...,Xp E Rep(m) the representation with v(X); inc, X, 7
Recall the functions h (hi,.... h1). As in Construction 4.2 these define activation functions
(h(m)) hh.... (mz) (resp. [h] (m)))) ..... h (m2)) for representation with dimension n (resp. m).
Finally, we fix a batch of training data {(x,, 3j)} S Ro R F x RL Using the activation functions defined by h, we have loss functions on Rep(n) and Rep(m) (see Section 3.4
Ln Rep(n) + R
Lm Rep(m) + R
W + Σ ((f(w.)(zz)).)))
X Σ (((())(())))))
Fixing learning rate r7 > there are resulting gradient descent maps on Rep (n) and Rep(m) given by:
in Rep(n) + Rep(n)
Rep(m) + Rep((m)
W w 1) Ww
X 17 Vx
The verification of the following lemma is analogous to the proof of Part of Lemma Lemma 188. We have that Lu fm-
37

---

Under review as a conference paper at ICLR 2022
1.4 THE INTERPOLATING SPACE
We first define space that interpolates between (mp(m) and Rep(n). The discussion of this section completely analogous that Sections F.1 and F.2
Definition 1.9. Let Rep" (m, n) denote the subspace of Rep(n) consisting of those T
(Tı,..., T2) E Rep(n) such that, for i 1..... ........ L, we have:
(idn, inc, Te) inc o - O.
Just as in Section F. the space Rep (m, n) consists of representations T = (Ti,..., Tr) (ep(n) for which the bottom left (n, m,) x (1 + n block of T. is zero for each Consider the maps:
(ep(m)
Rep
(m, n)
Rep(n)
The map : Rep int
m, n) + Rep(n) n) is the natural inclusion.
The map Rep(n) Rep" int (m, n) takes T E Rep(n) to the representation whose i-th slot
W; (id,, - inc, o Ti) o W; o inc; o 7;-1-
The map : Rep(m) + Rep int (m, n) is defined by taking X to the representation whose i-th coordinate is inc; X; T1
The map 92 Rep" (n) (n) Rep(m) defined by taking T to the representation whose i-th slot T. o T3 o inc;-1-
Definition I.10. The projected gradient descent map Rep(n) with respect to Rep"" n) and learning rate > 0 is defined as:
nn Rep(n) -> Rep(n)
W - W - n 0 o
We now state the main result of this appendix. We omit proof, as it follows the same ideas as the proof of Theorem 4.7 given in Section F3 The main difference that all appearances of red must be replaced by m.
Theorem L.1. Let X + W be morphism in I(Q2). Let Q be orthogonal factorizaionn of a and set U W Q.
1. The representation
Q g-1.W W X Q U belongs to Rep"" (m, n).
2. For any 2 0, we have
(W) Q
3. For any k 2 0, we have
オ ( 1 W) = (X) Q- U.
1.5 RELATION TO ALGORITHIM
this final section, we relate the general categorical results of this appendix to Algorithm I Recall that, in Section 4.2 we associated reduced dimension vector n to any dimension vector of the neural quiver 2..-
Proposition I.12. Let W be a representation of Qt. with dimension vector n. Then W admits a morphism in I(Q..) from representation with dimension vector n red
38

---

Under review as a conference paper at ICLR 2022
Proof. We proceed by induction the number N of i {l....,L L 1} such that n.nd N = 0. there is nothing to show. Otherwise, let j be the smallest element of {1...., - 1} such that nndd < nz. Then nedd nj-1 + 1. Let W Q inc mm1-1,, R be QR decomposition of W. where Q (n,)) and R is upper-triangular ný-1 + by n5-1 + 1 matrix. Consider the representation of 2n given by:
n, If -
1 0
X
W1 W R, W o
inc m W
WL
Q
Then
a= ( (id id ny Q inc inc1+ny-1.ng id idne)
morphism form to W. The dimension vector of X is (ng ...., n - red nj+1.-... nt. and has one less coordinate that n not equal to ndd, so the induction hypothesis applies.
Consequently, Theorems 4.3 and 4.7 can viewed as corollaries of Proposition L.7 Theorem and Proposition 1.12
Remark I.1.. Let Q. R and U be the outputs of Algorithm applied to representation W of dimension vector n. Then R defines representation of dimension vector n and Q defines morphism in I(Qr.) from R to W. Indeed, for = 1,... L, Algorithm | provides the equality
1 :
W;
inc; V; Qi inc; Ri: Qi-1
0
(where Qo = idn, = inco and QL idnz = inc which implies that the following diagram commutes:
R:
12
red
1 O
0
int
oincc
R
1+h-11
W.
R Th
39


Reviews:
[{"review_id": "vPCASZrBpwd", "reviewer": "Reviewer_6ipT", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I found the paper well-written, and presenting an seemingly interesting observation on neural networks whose activation function commutes with change of basis (orthogonal linear maps). However, I have serious concerns regarding the “radial” assumption on the non-linearity, and I was not convinced by the utility of the introduction of an elaborate mathematical framework to demonstrate a phenomenon which can simply (and plainly) be explained through some standard linear algebra. I believe that the authors could greatly improve the paper by either 1) demonstrating some further insight from the view of the network as a representation of a quiver, or 2) writing the paper in straightforward fashion through standard linear algebra arguments. Additionally, I feel that the overall results in this paper are not surprising (given the assumption on the activation functions), and I fail to see how such a phenomenon may generalize to typical activations encountered in practice. Detailed comments can be found below.\n\n**On the “radial activation” assumption and generalizing to further activation functions.**\nThe authors introduce an assumption on the activation function that it is “radial”. At first glance, this seems to me to render the network essentially linear up to a scaling factor. Indeed, the radial assumption means that $\\sigma(x) = ax$ for some scalar $a$ (which may depend on $x$), and thus for a two layer with weights $W_1, W_2$ we have $W_2 \\sigma(W_1 x) = a W_2 W_1 x$, and the network is thus a deep linear networks with some (scalar) scaling factor. Given this fact, it is not surprising that a reduced representation is possible, but this identity also significantly jeopardizes the expressive power of the network. The authors indicate that they expect their work to extend “non-radial activation functions”. I believe that such an extension is essential given the strong limits of the radial assumption. However, it also appears to me that the assumption that the activation commutes with orthogonal linear transforms is central to the proposed procedure, which places strong constraints on the expressivity of the network and does not seem generalizable to networks used in practice.\n\n**On the mathematical formalism and arguments.**\nThe authors make use of a fairly new formalism of viewing neural networks as representation of quivers. However, it is not clear to me that this view provides any specific insight into the claims of the paper, and it seems that it would only hinder accessibility of the results to a wider audience. Indeed, I believe that the claimed result can be obtained (in a very similar fashion) through a proof by induction (on the number of layers) and standard linear algebra arguments. Given this, I believe that the authors should either leverage the proposed formalism to obtain insights specific to that formalism, or abandon the formalism altogether.\n\n**On the gradient algorithm.**\nIn addition to the reduced representation, the authors show that projected gradient descent as applied to the reduced representation is equivalent to gradient descent in the original space, due to the fact that the gradient commutes with orthogonal transforms. However, this is not the case for many methods used in practice (e.g. Adam, RMSprop etc.), which explicitly depend on the choice of coordinates as they compute axis-aligned normalization quantities. It would be helpful for the authors to address these practicalities if possible.\n\nTypos: p. 3: Clebsh-Gordan", "summary_of_the_paper": "The authors make use of a theoretical framework for viewing neural networks as representation of quivers to introduce a reparametrization strategy for neural networks with radial activation functions. This reparametrization is based on a QR decomposition, and leads to a lossless compression of the number of parameters by factoring redundant symmetries of the model. A corresponding gradient descent algorithm is derived on the compressed parameter space corresponding to gradient descent in the original space.", "summary_of_the_review": "The paper presents some potentially interesting ideas. However, I believe that the unnecessary usage of an esoteric formalism and the constraining assumptions do not warrant publication at this time.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "SeNnJPliVMD", "reviewer": "Reviewer_uaQ7", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Comments on novelty and related work\n\nWhat the authors regard as reduced widths, which represent the dimensions of a radial neural network after compression, has an evident relationship to dimensionality loss of the affine transformations along the neural network. I believe that the authors should point out at related work on neural networks regarding the bottleneck effect on the outputs caused by the width and number of activated ReLUs [1].\n\nThe paper somewhat implies this work as the first lossless compression approach of neural networks: \"leading to a lossless model compression algorithm [...] Whereas previous approaches to model compression are based on weight pruning, quantization, matrix factorization, or knowledge distillation.\" However, there were three papers published on the topic in the last couple of years [2-4].\n\nThe comment regarding the classic LTH paper is inaccurate: \"Recent work has shown pruning can be done before training by identifying certain key network structures (Frankle & Carbin, 2018).\" In fact, that first LTH paper does pruning while training by (1) doing a few steps of training, (2) identifying lesser relevant weights, and (3) rewinding to the original parameters while excluding those parameters, which is not the same thing as pruning before training. However, the authors may (and perhaps should) cite subsequent work that does prune before training [5-8].\n\nAs a survey, Blalock et al. (2020) also describes gradient-based pruning as the typical (and competitive) alternative to weight pruning. That stream of work is classic and widely known, but it is completely ignored by the authors [7,9-16].\n\n# Comments on improving the paper\n\nI could not understand the necessity and relevance of quivers for what the authors did. I am not saying that there is not one, and in fact deep learning has benefited a lot from the many approaches brought in from other disciplines, but I believe that the paper would benefit immensely from an even smoother introduction of the topics that are not commonly used in our literature. To mention one example of that being done in a masterful way, I would recommend that the authors look at how [17] describes tropical algebra before applying it to neural network.\n\nIn Example 5.1, for the shifted ReLU as h(r) = ReLU(r-b) for b positive, I believe you should be explicit about r being nonnegative. By checking the reference cited, I actually found out the definition of a Norm-ReLU as h(|f(x)|) = ReLU(|f(x)|-b) for b positive, which is actually easier to understand. \n\nI also missed some figures illustrating what is it that makes an activation useful for your approach. I spent some time playing around with your definitions to make sense of it, which is how I got some intuition for the results that you obtained and why they should be valid. Please consider including examples like this one:\n\nhttps://www.wolframalpha.com/input/?i=plot+%7C%7Cx%7C+-+5%7C\n\nWhile playing with it, I also started wondering that perhaps there is no need to require b to be positive in the case of what you call a shifted ReLU. Is it not true that your approach would work with the function below?\n\nhttps://www.wolframalpha.com/input/?i=plot+%7C%7Cx%7C+%2B1%7C\n\n# References cited\n\n[1] https://arxiv.org/abs/1711.02114\n\n[2] https://arxiv.org/abs/2001.00218\n\n[3] https://arxiv.org/abs/2007.06567\n\n[4] https://arxiv.org/abs/2102.07804\n\n[5] https://arxiv.org/abs/1810.02340\n\n[6] https://arxiv.org/abs/1906.06307\n\n[7] https://arxiv.org/abs/2002.07376\n\n[8] https://arxiv.org/abs/2006.05467\n\n[9] https://proceedings.neurips.cc/paper/1989/file/6c9882bbac1c7093bd25041881277658-Paper.pdf\n\n[10] https://proceedings.neurips.cc/paper/1992/file/303ed4c69846ab36c2904d3ba8573050-Paper.pdf\n\n[11] https://arxiv.org/abs/1506.02515\n\n[12] https://arxiv.org/abs/1611.06440\n\n[13] https://arxiv.org/abs/1705.07565\n\n[14] https://arxiv.org/abs/1810.02340\n\n[15] https://arxiv.org/abs/1905.05934\n\n[16] https://arxiv.org/abs/2004.14340\n\n[17] https://arxiv.org/abs/1805.07091", "summary_of_the_paper": "This paper presents a dimensionality reduction technique that can preserve the model of a neural network by leveraging radial symmetry. Consequently, when the required conditions apply, they also show that training the compressed model is equivalent to training the original model on a particular projection of the parameter space.\n\nThe first two sections of the paper are very clear and well written, although some definitions would have helped (more on that later), but the sudden change of pace starting at section 3 makes it difficult to follow if you do not have the same background. I believe that I have captured the gist of their results, which seem to be intuitively correct, but I cannot comment on how they were derived. Hence, what follows is a description in my own words and perspective of what they did.\n\nThe authors present a method that would reduce the width of each layer of the neural network to the smallest width of any preceding layer, including the input layer. That is possible in radial neural networks because (1) the activation function involves the entire layer as opposed to each neuron individually and (2) the activation function is symmetric along any direction considered. ", "summary_of_the_review": "# Final comments\n\nThere are two items affecting my score at this point:\n\n1) How applicable is this result? In other words, how often would we consider using radial neural networks in practice, or how much of this paper could be applied in a broader sense?\n\n2) It is not easy to follow this paper when it gets more technical. I know that many reviewers would not be willing to reassess their score if the authors put the effort of rewriting the paper considerably, but you have my word that I would reread the paper and reconsider my assessment in case you do that.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "L1G8ulAIYoD", "reviewer": "Reviewer_EGB6", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The proposed neural quiver is a nice application of matrix representations in NNs, which have been studied in the literature as reviewed in the paper. The proposed paper employs them to study compression of models. However, the proposed theoretical and experimental results should be improved to justify the proposed main claim, which is proposing a framework for efficient model compression. \n\nTo sum up, there are two major issues with the paper:\n\nFirst, the proposed main theoretical results have been studied in various previous works for training NNs on Stiefel or low-rank matrices. In addition, additional works employed more efficient retractions (e.g. Cholesky decomp.) than QR decomposition for optimization (e.g. projected or Riemannian GD) on low-rank matrices or orthonormal matrices. Therefore, the theoretical novelty of the proposed method is limited.\n\nSecond, the main claim (also the title) of the paper is about model compression. Therefore, the proposed methods should be compared with the other model compression methods (at least, with those which employ PGD on low-rank parameters as proposed in this paper) experimentally on benchmark datasets in detail. \n\nSome minor comments:\n\nIn Fig. 1, is the bias shared among layers? If it is, then does the proposed neural quiver represent a particular class of NNs?\n\nPlease define R in Theorem 1. How do you compress W to obtain R?\n\n", "summary_of_the_paper": "This paper provides a framework to study compression of NN models by analyses of symmetry properties of their parameter spaces. For lossless model compression, an algorithm employing QR decomposition for parameter compression is proposed. In the theoretical analyses, the decomposition of the proposed neural quiver is studied. The proposed methods were experimentally analyses in synthetic datasets.", "summary_of_the_review": "The paper proposes a theoretical framework to study compression of NNs employing the representation theory of quivers. However, the proposed theory and its experimental analyses are incomplete.\n\nTo improve theoretical results, I recommend first explicating the theoretical results in comparison with the related work. Second, experimental analyses should be extended by applying the theoretical framework for the target model compression tasks in comparison with the related state-of-the-art.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Authors developed a reparameterization scheme using QR decomposition to reveal symmetries in networks with radial activation. While I welcome new ideas and formalisms from other fields, the ideas presented in this manuscript are fairly straightforward under the radial activation assumption. Although the authors claim that the results may generalize, no evidence was provided. The practical contributions are marginal and lacks comparisons with related DNN compression schemes. Through the review process, the paper has been greatly improved, but unfortunately, this interesting paper does not meet ICLR's standard as is.
Decision: Reject