Representation Costs of Linear Neural Networks: Analysis and Design
Authors: Zhen Dai
Mina Karzand
Nathan Srebro
Venue: NeurIPS 2021 Poster (2021)
Keywords: Overparameterized Learning
Regularization
Representation Cost
Linear Neural Networks

Abstract: For different parameterizations (mappings from parameters to predictors), we study the regularization cost in predictor space induced by $l_2$ regularization on the parameters (weights).  We focus on linear neural networks as parameterizations of linear predictors.  We identify the representation cost of certain sparse linear ConvNets and residual networks.  In order to get a better understanding of how the architecture and parameterization affect the representation cost, we also study the reverse problem, identifying which regularizers on linear predictors (e.g., $l_p$ norms, group norms, the $k$-support-norm, elastic net) can be the representation cost induced by simple $l_2$ regularization, and designing the parameterizations that do so.

Representation Costs of Linear Neural Networks: Analysis and Design
Zhen Dai
Mina Karzand
Committee on Computational and Applied Mathematics University of Chicago
Department of Statistics University California, Davis
Chicago, IL 60637 zhen9@uchicago.com
Davis, CA 95616
mkarzand@ucdavias edu
Nathan Srebro
Toyota Technological Institute at Chicago Chicago, IL 60637
nati@ttic.edh
Abstract
For different parameterizations (mappings from parameters predictors), study the regularization cost in predictor space induced by la regularization on the param- eters (weights). We focus on linear neural networks as parameterizations of linear predictors. We identify the representation cost of certain sparse linear ConvNets and residual networks. In order to get better understanding of how the architee- ture and parameterization affect the representation cost, we also study the reverse problem, identifying which regularizers group quasi-norms, the k-support-noo -oupport-norm, elastic net) can be the representation cost induced by simple la regularization, and designing the parameterizaatons that do so.
linear predictors (c.g., 4p quasi-norms,
Introduction
In class of parameterized models, penalizing the l2 norm of the parameters induces regularization on function space which can be interpreted as complexity measure on the class of learned functions. In this paper, we study how different parameterizations induce different complexity measures.
We consider parameterized mappings f X' x R - RT. from input æ E X and parameters Iº to predictions f(z; w). We denote the predictor implemented with parameters by F(w): :X - IR defined as (x)) == f(z; w). Then image F)) is the set functions from X' to Th which can be obtained from this class of parameterized models. We will use F to denote set of functions from X' to Rm
The 12 regularization parameters, either explicitly or implicitly, is common phenomenon. As an example, deep learning, explicit la regularization on parameters (a.k.a. weight decay) improves generalization 20 37).. Implicit regularization of l norm of parameters appears when we use
gradient descent (GD) to train the model (22 35 33 19 23
32 14 25 9 [8). In particular, GD on
homogeneous neural networks with logistic loss implicitly regularizes norm weights [23 32).
The representation cost
(15 31 27
of function g in image(F)) under the parametrization
RF(g) min F(w) = g}.
(1)
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Consider learning predictor F(w) with some loss function L(-) while controlling the l2 nomn of parameters by minimizing
min L(F(w) + A/|w||22
(2)
WEBP
This is clearly equivalent to learning function g in imago(F) by controlling Rr(g) defined in Eq.
min sEimage(F) FF)
L(g) + XRF
In other words, the representation cost under the parameterization F, RF(+), captures the regular- ization on function space image(F)) F)) induced by la regularization on parameter space. In this paper, we are interested in understanding how different parameterizations, regularize the function space differently. Since GD on homogeneous neural networks with logistic loss implicitly regularizes l2 representation cost induced by l2 regularization in weight space captures the implicit regularization in homogeneous models, but not necessarily in non-homogeneous models. Thus, representation costs predictors parameterized by homogeneous models are arguably more related to implicit regularization, while representation costs of predictors parameterized by both homogeneous and non- -omo-oomgeeuuuss models are related to explicit regularization. In this paper, we first develop results for homogeneous neural networks. Then we reduce the non-homogeneous neural network to the homogeneous ones by arguing that the asymptotic behavior of its representation cost can be captured by the representation cost of some homogeneous subnetwork of the non-hooogeneous network.
norm on weights 23 22
One way to motivate the study of representation cost is by considering the popularity of the over- parameterized models, in which the number of parameters greater than the number of samples. Surprisingly, it has been observed that in the overparameterized regime, interpolative predictor generalizes well [7] 39 16 3) One way to explain this is that although there are many predictors which perfectly fit the training data, gradient based algorithms choose the one with the smallest representation cost (I55, (23). In these cases, representation cost operates as a regularization in the function space which enables good generalization. Thus, understanding representation cost helps us understand the generalization of the model. In particular, representation cost of predictors induces ordering the space of predictors. Since representation cost determined by the specific parametrization, each parameterization induces an ordering on the function space. This can be interpreted an induced complexity measure of the predictor space, where penalizing the cost is the same as minimizing the complexity.
Definition 1.1 (Induced complexity measure). Let F be a set of functions from X to 8 and F be the set of all functions from F to I. We define the equivalence relation in J such that hı and (i.e., h1, h2 : F > R) are equivalent (h1 _ h2) if there exists a strictly increasing function h2. Let F = be the set of equivalence classes of F under _
he E F sb R R h1
Given a parameterization F RP + F. let F be image(F), In this case, for each value of parameter w E RR, F(w) E F is a mapping from X' to Lee the representation cost Rr under parameterization F be as in Eq. [.. We say that an equivalence class F / is the induced complexity measure of the parameterization F if for any representative (i.e., element) h in class h, RF is a strictly increasing function of h.
We study the dependence of induced complexity measures on parameterizations from two perspectives: First, given a parameterization F, we analyze its representation cost. Second, given a regularizer on function space, we study when and how it be the induced complexity measure of some parametrizations. In this paper, we start answering these questions by focusing on linear predictors parameterized by linear neural networks. Note that for linear networks with single outputs, the function space being parameterized does not depend on the architecture. Thus, the change in architecture only changes the induced complexity measure. This makes it appealing for highlighting and understanding what the effect of changing the architecture is in changing the induced complexity measure.
In the first part of the paper (Section 3. we identify the representation costs of various architectures. Specifically, we look into fully connected networks and convolutional networks with multiple outputs. In addition, we show how the representation cost of convolutional networks with restricted filter
In other words, F² 2 is a partition of F into classes with the following property: given a class h E F²/ 2, any two elements h1, ha E h are equivalent (i.e. h1 o h2).

---

Architectures (of depth d)
Induced Complexity Measures
Fully Connected Network with multiple outputs
Schatten 2/d quasi-norm
Diagonal Network with multiple outputs
Matrix /2/4,22 quasi-norm
Convolutional Network with multiple outputs
Matrix 12/2,2 quasi-norm Fourier domain
Residual Network
An interpolation between two quasi-norms
Table I: From Architecture to Induced Complexity Measure
Induced
Complexity
Conditions
Architectures
Measure
Ip quasi-norms
if and only 2f E
Diagonal networks
k-support norms
if and only if k: E [n]
h-balanced networks (Fig. la
lp.g group quasi-norms Elastic nets
if 2/p, 2/q N and 2/p 2/9 None None
Group networks (Fig.
None
4.. with
None
overlapping groups
Table 2: From Induced Complexity Measure to Architecture
width changes their filter width changes. Then, show that the representation cost of residual networks interpolates between the representation costs of two of their component networks. Finally, we give characterizations of the representation costs of depth-two neural networks. The results of this part are summarized in Table
In the second part (Section 4 given few regularizers, study when and how they be the induced complexity measure of some architectures. Specifically, we show that Ip quasi-norm can be the induced complexity measure induced by 12 regularization and only if 2/p is an integer. Moreover, when 2/p is an integer, we characterize all the architectures whose induced complexity measures are 4p quasi-norms. In addition, we design architectures whose induced complexity measures are k-support-norm and lp.g group quasi-norms. Then, we show that elastic nets and lp.q quasi-norm with overlapping groups cannot the induced complexity measure of any linear neural network. On the contrary, we show that there exist homogeneous parametrizations whose induced induced complexity measures are elastic nets and lp.4 quasi-norn norm with overlapping groups. The results of this part are summarized in Table 2 Finally, in the conclusion. we discuss some interesting future directions.
some linear neural networks if
Further related works: Some previous work focuses on the expressive power image F)) of the model 22 29 38 21. However, discussed in (6) 24], some other capacity control, different from network size, plays a role in deep learning. This motivates the study of representation cost and its relation parametrizations.
Representation cost has been studied before under various models. [5] showed that the representation cost of a linear convolutional neural network of depth is strictly increasing in the Schatten-22 quasi-norm on the Fourier domain, whereas the representation cost of a linear fully connected network of depth d is strictly increasing in the la norm. [3] and (27 studied depth-two fully connected
(a)
(b)
Figure 1: k-bblanced and Group networks: architectures for 1p.q quasi-norms. Figure 1b induces 12,1 norm. Figure induces /2/2222/ 2/d, /d, quasi-norm. Figure ld induces 12/d, 2/( quasi-norm. In all plots, nodes in same color are in same group.

---

network with infinite width and ReLU activation. They show that the representation cost of any continuous function depends on the Laplacian of that function.
Parallel to our work, [8] studies the representation cost of linear convolutional neural network with restricted filter width (a.k.a. kernel size) and multiple channels using anlaytical tools from semidefinite programming. In spite of different approaches between our work and [18] the results on CNN with restricted filter width are similar in two papers.
Another line of work studies the relationship between neural networks with by regularization on weights and convex optimization problems [28 I2 II 30]. In
12 [1] [0], the authors showed that training a neural network with explicit l2 regularization on weights is equivalent to a convex regularized optimization problem in some higher dimensional space. In contrast, motivated by the
28
literature on implicit regularization of gradient descent 22 35 33
18 we looked into the induced regularization of weight decay function space. Some of the results in 30] are similar to the results in our work. For instance, the results on linear convolutional
23
32
25
28 12
neural network in [28] I2 [ [30] suggest that explicit l2 regularization on weight space related to l regularization on the Fourier transform of the predictor. This result was also discovered in [55 and generalized to multiple output and restricted filter width (a.k.a. kernel size) case in our work and in [8]. On the other hand, we considered other architectures beyond fully connected and convolutional neural networks. For instance, we studied architectures that induce k-support norms and architectures that induce 1..9 group quasi-norma. which are not included in 22 12 [1]
As another related work, (36) studied the equivalence between l2 regularization on weights and some sparsity-inducing regularization on the function space for various architectures. They considered the architecture which induces 22, /2/d,2 group quasi-norms the function space, for any d E N. We also studied similar question in section 4.1.2 However, we found architectures that induce 4p.g group quasi-norms for both the case p q and the case p < q. In addition, we showed that in the case p < b quasi-norm can be induced by some linear neural network as induced complexity measure if and only if 2/p, 2/9 E N and designed architectures that do so.
2 Setup
RP + RT is homogeneous of degree L if [æ;; Aw) = A- w). for all À > O. A feedforward neural network [N with weights (parameters) w = (W1...., Wa) (ejo))))))) Note that when the activation function a is homogeneous (i.c. (Ax)) = X (z) for some L > 0), the feedforward neural network fy is also homogencous. In particular, with ReLU activation (i.e. (xx) = max(0, x)) or identity activation (i.e. (x) = x). fx is homogeneous.
A parameterized mapping ʃ X' XR
and activation function is defined as fxr(;; w) = o (Waat (Waar
A linear neural network is neural network with identity activation function. When X = R" and g is a linear function, we identify g with the matrix 3 E Rm such that g(x) = Br. In particular, in the case of one-dimensional output space, we identify g with the vector 3 E R" such that g(x) = 3 x. In this paper, we mainly focus on linear neural networks. A more general definition of linear neural networks in terms of directed acyclic graphs will be useful in our work.
Let G (V, F.) be weighted directed acyclic graph, with sources U1, U .. Un (i.e. vertices with in-degree zero) and m sinks u1, ......., Un (i.e. vertices with out-degree zero). The weight of edge e E F, is denoted by g(e). Given parameters assigns parameters to edges such that g(e) = w[{((e)] for all e E E.
Definition 2.1.
RRP function /b E [p]
The pair (G, v) gives construction of a linear feedforward neural network ''' corresponding to a linear predictor (=)::w) : IR" + R as follows: Let Φ(v) E R be the output flow of the node
V. Given z E IR", let ((v;) x²|] for all input nodes i E [n]]. Then, Φ(v) for other nodes is
defined recursively such that the output flow of each node is a weighted sum of its input flow using the weights of the graph: Φ(v)= = Σ Eustu (()) Then Φ(u) for sink nodes give the linear predictor (a; w) (Φ(u1). &
Let Fx be the parametrization associated with fN defined as Fx(w)(x)= := (x;
The depth d of linear feedforward neural network (G, 1/) is defined as the length of the longest path from the source to the sink. We say that a linear feedforward neural network is homogeneous every path from the source to the sink have the same length. We say that linear feedforward neural

---

network is without shared weights if the map db is bijection. We call Ui...., UI...., Um the output nodes, and E V the nodes of the network A.
. Un the input nodes,
Without loss of generality, we assume that for all V. there exist directed path from to some output node u, and a directed path from some input node v; to v. Otherwise, removing e would not change fv. For each E V, let
S. {i E [x] there exists a directed path from Ui to v}.
(4)
By assumption, for all u V, |S 2 1.
Note that if linear feedforward neural network / is homogeneous, then we can define its /th layer Ni as the set of vertices whose distance to any input node v; I. Note that this is well-defined since the length length of any path from any input node to any output node is constant in homogeneous linear feedforward neural networks.
Let V be a depth homogeneous feedforward linear neural network without shared weights. Then, the weights of the edges between the Ith and / + Ith layer of .V can be identified as a matrix Wi- In this case, the parameters w is a sequence of matrices W1, Wg,..., Wa with some fixed sparsity pattern, i.. supp(Wi) Sy for each I [d]. where S determined by N. The parameterized map fN and the parametrization Fx are given by
d
fx(a; w) = (x( = III W. Wa-141)r, 1=1
(5)
for x E TR, where (W1, W2,.... Wa). Note that Eq. (5) is equivalent definition of fA and Fxr when A is homogeneous and without shared weights.
In the rest of the paper, unless stated otherwise, we will use / to denote single output depth d ho- mogeneous feedforward linear neural network without shared weights. Note that fx is homogeneous of degree d. Let No [n]] denote the input layer (we identify Ui,..., Un with [r]) and Na { denote the output layer. With slight abuse of notation, let Fx((w) E R" be the vector corresponding to the linear predictor generated by on N. Let Rx == RF denote the representation cost (Eq. [ under Fx. We say that h is the induced complexity measure N if it the induced complexity measure of FN as defined in Def I.]
Notation: We will use B E TR." denote column vector, and B3 or B[i]] to denote the i-th component
of B. We will use 3 to denote the discrete Fourier transform of B. For groups G1, G2 ..., G₁ S [n].
we use the definition of the lp.g group quasi-norm, || p.g -E₃ ErEc, 18,19) p/q 1/p
Unless
stated otherwise, G1, Gg .... and G form a partition of [m] 21, n}. We will use G E Rxxx
to denote a matrix and B k] to denote the element in the j-th row and k-th column of B.
3 Representation cost analysis
To understand the dependence of induced complexity measure on architectures, we analyze the representation costs of some commonly used architectures. The authors in [15) studied single output fully connected network, diagonal network, and convolutional neural network (CNN) with full filter width. In this section, we first generalize their results to multiple output case. Then, we look into the non-homogeneous residual neural network and observe that its representation cost interpolates between the representation costs of two of its component networks. Finally, we characterize the representation costs of depth-two neural network in two ways.
3.1 Multiple output networks
3.1.1
Linear fully connected network
In linear fully connected neural network,
d
FF ((W))
W W
1=1
5

---

where w (W1. 22, .W)) is the weights of the network. For i E [d], the matrix W; is in R" where n; 2 min (m, n),, n, and ni+1 = m. Let " RF (2-..))411) be the representation cost under PFO(n,
defined in Eq. O.
Theorem 1. Suppose that n, 2 min(m, n) for all E [d + 11, where and Rd+1 = m. Then, for any Rmx"
Re (B) d
0
2/d 1/011//d1
where 01, 02, or are the positive singular values of B and || 1/112/d
1ii= 0: /// the
Schatten 2/d dd-uuasinorm of B. In particular, with a single output.
dl|
d1| 2 ||
The above result is similar result in [8]. They studied layer multiple output convolutional neural network with filter width (a.k.a kernel size) one, and showed that its induced complexity measure is the nuclear norm.
3.1.2 Linear diagonal network
In linear diagonal network,
d FDNN(W)= W. II diag (wa+1-i);
where = (w1, "..-1. Wa) is the parameters of a diagonal neural network. For i E [d 1]. wy E R and Wa E RRmx,, So diagonal network consists of some diagonal layers followed by fully connected layer. Let RDNN == RFONN be the representation cost under FDNN defined in Eq.
Theorem 2. For any B = (3(1), _(2),.... ... 3(m) E Rmxn
RDNN( = d Σ [3(0) 1
2/d
11
where [|3] |/312//222 (E ||366] 2/d //2 is the matrix l2,2/a quasi-norm. In particular, with single output
RDNN(B) d|l
2/d 2||
2/4 = ||
3.1.3 Linear convolutional neural network (CNN)
In linear Convolutional neural network (CNN) with filter width g. the parameters w (Wi, W2, ... Wd-1, Wa). where w; E Rº x (0)--g and Wa E mpxxn Let h E R" be the out- puts of the nodes in the ith layer. For i [d - 1], the transformation from the ith layer the i + 1th layer is given by h [i] vo Σx= Wi+1 [k]] + + -- mod n] =: (wi+1 & h.)bi. The last layer is fully connected and ha Waha-1- Then, the linear map given by fCN (w, (CNN(w) Wa(wa-1 (wa-1 @ (... wy @ (w) @ .)). Equivalently,
d
FONN()) (1c)
W Wat1-b II
1=1
where for each i E [d 1), w: w3[00] my(n) and W.(j,k] k] wi wilkk - 1) mod n)/ Vni is the
circulant matrix with respect to wy; Let RONNGy (3) == R (3) be the representation cost
under FONN()) defined in Eq. (1) filter width q-
Let F E C be the discrete Fourier transform matrix defined by F(j,A] Vn
1
-w/ (f-1)(k-)) where
Wn. 2xi/n, For B E mxn let á = BF.

---

Theorem 3. For any B E mm let B == BF and B(4) be the i-th column of B. Then.
RCNN(N)(3)
=d Σ
2/d
3
2//222
==1
2/d yd12 the matrix 2,2/3 quasi-norm. In particular, with a single
where [
2/d,2 (E==
((0)
=
output
- =d[3] 2/d = 1
The result for d 2 was also discovered in 18
Results on linear CNN with restricted filter width g < n and some variations of CNN such as CNN with sum pooling and CNN with multiple channels can be found in the supplementary materials.
3.2 Linear non-homogeneoos residual neural networks
Let V be a linear homogeneous feedforward neural network without shared weights. Suppose that each hidden layer of N contains n nodes. Let d be the depth of W. Let J1, T2,.... . T S [d] such that
|Tyl = dj for each E [k) For each E [R). let I (J1,j2..... -d,, J where ji < ja < Jdy.
For each w = (W1, , Wa) and E [k], let
dj
FN, (w)
II Wia, St, an and EN Σ FNr (w).
(6)
be the parameterization for a residual neural network (ResNet). Let RessNet == RF Re be the representation cost under ENReNNar and Rg == REN, the representation cost under FN, for each j E [k).
Theorem 4. Suppose that dj < d2 RR R4 (A3) + 1 as A + cc.
dy Then, RReeNe(A8))/R((A)) - 11 as and
Note that the model considered here includes sum of homogeneous models without shared weights, which is studied in 32 concrete example can be found the supplementary materials.
3.3 Depth neural networks
In this section, characterize the representation costs of depth homogeneous feedforward neural networks in two ways. We will use these two characterizations to find architectures that induce k-support norms (6) and (2,1 norms as induced complexity measures.
Let 2. Note that the definition given Eq. becomes S₁. = (i No (1, E E), for each h N₂ Nu.
Lemma 5. For a depth-two linear homogeneous feedforward neural network N without shared weights, R3) 2 min ||wx||2 supp(wι) C Sn. EnEN, 3).
In the above lemma, each vector U) corresponds to the linear predictor generated by the part of the network which includes the hidden node and its neighbors. Lemma jimplies that R-((-) (-) is a norm. Let (-)()) be its dual norm. Now, give characterization of (x(().
Lemma For a depth-two linear homogeneous feedforward neural network N without shared NH).
weights, (3) max (EEss, 3/)
By Lemma 6 there exists h4 h2 NH such that h1 # h2 and Sh, S Shy. then removing h from N would not change the representation cost since Eiesh, 3² EieSh, 33

---

Parameterization design
In order to further understand the dependence of induced complexity measure on architectures, we study when and how regularizers can be induced the induced complexity measure by some architectures.
In this section, we study a few regularizers such as Ip quasi-norms, 4..q group quasi-norms with and without overlapping between groups, k suspor norms, and elastic nets.
4.1
Architecture design
First, we design architectures that induce ip quasi-norms, 1.. quasi-norms without overlapping groups, and s-sppp norms as induced complexity measures respectively.
4.1.1 hp quasi-norms
In this section, we study architectures that induce lp quasi-norm, which is defined as || (E 13,P) where B E IR.
Theorem 7. There exists linear homogeneous feedforward neural network N without shared weights that induces ln quasi-norm if and only if 2/p E N. In particular, diagonal network of depth 2/p induces hp quasi-norm.
turns that we can capture all the architectures that induce l, quasi-norms using simple combinatorial measure called mixing depths. Roughly speaking, for any S C [rr]. the mixing depth (S) 5) the index of the first layer that contains node such that S S S.. where S. is defined in Eq. (4p.
A linear homogeneous feedforward neural network // without shared weights induces 1p quasi- and only if (S) = 2/p. for all S S [m], |S] 2 2. The details can be found in supplementary materials mixing depths and proofs in supplementary materials for 1p quasi-norms.
4.1.2 ln. group quasi-norms
Similar the previous sections, we want know and when 1.g group quasi-norm is the in- duced complexity measure of M. Remember the definition of of 1.. quasi-norm, ||
(E Evec, (8)1))//))/>, where G₁, G2.... Gy form partition of [n].
Unlike the results for l, quasi-norms, do not find all the values of p and q such that lp.q group quasi-norms without overlapping groups can be induced by some homogencous feedforward linear neural networks without shared weights.
Theorem 8. If there exists a linear homogeneous feedforward neural network N without shared weights that induces 1,.9 group quasi-norms, then 2/p, 2/q N. On the other hand, 2/.p 2/q E N and 2/p 2 2/q - 1, then there exists linear shared weights that induces hp.g group quasi-norms.
neural network N without
Next, we will design group nefworks that induce 1p.g group quasi-norms. The design of group networks uses insights from subnetworks. Roughly speaking, a subnetwork is a restriction of the original network to some input nodes. The induced complexity measure of subnetwork is tightly related to that of the original network. This relationship. together with the results in Section 4.1.J inform how certain subnetworks of group network look like, which indicates certain properties of the group network. The details can be found in supplementary materials.
Group networks consists of some diagonal layers followed by grouping layer and then followed by a diagonal network (Section 3.1.2). Two examples of such networks are in Figures [c grouping layer is the first layer that mixes information from different input nodes. Depending on whether < or p > q.B we define two types of grouping layers:
and and [d] The
Definition 4.1 (Type I and II Grouping Layers). For each E [d], N, is type I grouping layer if Nj is diagonal for all j < i, [N.] = k. where le is the number of groups, and for each j E [k]] there exists N, such that S,, = Gj--
When p q. 4p. quasi-norm becomes quasi- norm which already studied.

---

For each E [d], N; is rype Il grouping layer if Nj is diagonal for all j < i, Na = MT Ggl+ where k is the number of groups, and for each E
J= Gg. there exists u E N, such that S. - h.
Next, we compute the representation costs of networks with these two types of grouping layers. For d1, d2 N with d2 > d1, let AIdd de be the architecture with d1 diagonal layers, followed by type grouping layer (Def 4.1), and then followed by diagonal network of depth d2 di (Section 3.1.2p. See Figure Tc for example of this kind of group network.
Theorem 9. Les G1, G2 ... Gg be partition of [m)]. Let Sa, be the projection of B Gj. Then for d2 d1, dy (B) d2 ンラ= || l d2 d2ll/912//2.2 2//4
2/dg
= 2/de2//d
The same architecture when di = 1 is also discovered in (36] They also showed that in the group network A1l1,, la regularization weights translate to 12/d2.2 regularization in the function space. Our result stronger than the results in [36 two ways. First, we found the architecture Ml which induces 2/dd; quasi-norms for all d1, d2 E [m], while they only did it for d₁ = 1. Second, we proved that these are all the values of p, q such that lp.g group quasi-norms can be induced as induced complexity measures for some linear neural network, when
For d1, d2 E with d2 > d1, let 222:,, denote the architecture consisting of diagonal layers. followed by a type II grouping layer (Def(4.1), and then followed by diagonal network of depth d2 d1 (Section 3.1.2). Figure Id is an example of A2;dd,dd,
In particular, when d1 = and d2 2 (as Figure 1b). 2/211.2 induces 22,1 norm. This can be proved the dual characterization of representation cost of depth-two networks in Lemma and the fact that || = ||
2/dz Theorem 10. When d2 d1 + 1, Ry (3) d21101 2/42 = =1/8112/d,
This theorem implies that 2/dd de induces 12/d, quasi-norm when d2 d1 + 1. Surprisingly, ACt:d da does not induce 2/d2 quasi-norm when d2 di 1. The details are in supplementary materials.
4.1.3 The k-support norms
In [ the k-support norm is defined as || = min (in((E ||rll2 supp(er) S T, Eseg 8), for A E [n]. where Ga is the set of subsets of [n] of size at most k.
To design an architecture which induces k-support-norm, we introduce the k-balanced networks. A two layer neural network is k- k-balanced network, if it contains (+) nodes in the hidden layer such that for each subset 7 C [n] of size k there a node the hidden layer which connects to input nodes in J. See Figure Ta for example with
and =
Theorem 11. For any k E [n), there exists homogeneous feedforward depth two linear neural network without shared weights that induces k-support norm as induced complexity measure. In particular, k-balanced network induces k-support norm.
The proof of the above theorem is an application of Lemma 5 which characterizes the representation cost of depth-two networks.
4.2 Limitations of homogeneous neural networks
Theorem 8 and Theorem 11 give architectures that induce lp., quasi-norms and k-support norms. Then, it is natural to consider two regularizers related to k-support norms and (p.9 quasi-norms. Elastic nets] is defined as | EN = || + all B11 and (p.9 quasi-norms with overlapping groups is defined as in Section 4.1.2 except that G1, G2 G might overlap. Contrary to the results of k-support norm and lp.q qursi-norms, elastic nets and lp.g quasi-norms with overlapping groups are not induced complexity measure of any architecture N without shared weights. The detail can be found in supplementary materials.
Elastic nets and k-support norms both interpolations between 4 and /2 norms.

---

Given these negative results, it is natural to look at non-homogeneous residual networks. We use the same definition residual networks in Section 3.2 Theorem characteriizs the asymptotic behavior of the representation costs of residual networks. The proof of the following theorem uses Theorem
Theorem 12. Suppose that dj < <...... dy- Let h R" - R be homogeneous function. If ENR induces h as induced complexity measure, then FN, also induces induced complexity measure.
This theorem implies that the negative results clastic nets, lp.0 quasi-norm with overlapping groups, and lp quasi-norms when 2/p & N still hold even in the case non-homogeneous residual networks. As next step looking beyond homogeneous networks, we look into general form of homogeneous parameterizations which might not be associated with any networks. Surprisingly, homogeneous parameterizations can indeed induce elastic nets and l,.g quasi-norms with overlapping groups for all p, q > O, as induced complexity measure. The details are in supplementary materials.
5 Conclusion
In this paper, we take the first steps in studying the dependency of induced complexity measure on the choice of parametrization. We do so by analyzing the induced complexity measures of some well-known architectures and designing architectures that induce some common regularizers on linear predictors. These directions are important for two reasons. First, it helps us understand why certain architectures generalize. Second, if we have a desired regularizer in mind, this helps design an architecture which induces this regularizer as induced complexity measure.
For the first reason, many of the representation costs we study, when used regularizers in learning problems, have good generalization properties. This includes 1p.g group quasi-norms, especially in
the context of multi-task or multi-class learning [33 [7], k-support norm (6), elastic net [10 40).
nuclear norm [4, 34 [1,,, and lp quasi-norm for p S 1 in order to promote sparsity [8]. Thus, this existing understanding and analysis, together with the results in our work, explain for the benefit of using the corresponding architectures.
For the second reason, do not mean designing architecture from seratch based on fully specified regularizer (as we do in section 4). Instead, we believe that building out our understanding in this regard can help with making architectural choices about complex architectures. In these setups, we do not understand the exact representation cost, and cannot write it down and use explicitly; but might want change representation cost nudge it in particular directions through some modification of the architecture.
Answering these two questions of design and analysis in a broad sense is an important step in understanding generalization and improving our current models. The limitation our work includes the fact that linear models. So our study is mostly meant to build tools and understanding and set the stage for understanding more complex non- linear models. But linear models might behave very differently, and so we should be cautious about how many of our insights carry over.
considering only rather specific
of architectures, and in particular only
To move beyond, there are still many unanswered questions for the linear models. For instance, for p, q E N such that 2/p 2/g does there exist an architecture that induce 1p.9 quasi-norm?
Next step would be looking beyond linear predictors. For example, the question of analyzing representation cost for neural networks with non-lincar activation functions such as ReLU an open problem for most architectures. The other possible direction is studying the same questions (analysis and design) for functions with multiple outputs.
6 Acknowledgement
Zhen Dai was funded by DARPA (grant number: HR0011219000 and NSF (grant DMS 1854831).
10

---

7 Funding Transparency Statement
Funding in direct support of this work: DARPA grant (grant number: HR001 121 12190040); NSF grant (grant DMS 1854831).
References
[1] Jacob Abemethy, Francis Bach, Theodoros Evgeniou, and Lean-Phillippo Vert. new approach to collaborative filtering: Operator estimation with spectral regularization. Journal of Machine Learning Research, 10(3), 2009.
[2] Alnur Ali, J Zico Kolter, and Ryan Tibshirani. A continuous time view early stopping for least squares regression. In The 22nd International Conference Artificial Intelligence and Statistics, pages 1370-1378. PMLR, 2019.
[3] Zeyuan Allen-Zhu Yuanzhi Li, and Yingyu Liang. Learning and generalization in overpa- rameterized neural networks, going beyond two layers. arXiv preprint arXiv:181 181.0991 2018.
[4] Yonatan Amit, Michael Fink, Nathan Srebro, and Shimon Ullman. Uncovering shared structures in multiclass classification. Proceedings of the 24th international conference on Machine learning, pages 17-24, 2007.
[5] Andreas Argyriou, Theodoros Evgeniou, and Massimiliano Pontil. Convex multi-task feature learning. Machine learning, 73(3):243-22) 2008.
[6] Andreas Argyriou, Rina Foygel, and Nathan Srebro. Sparse prediction with the k-support norm. 2012.
arXiv preprint
[7] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical varinnar trade-off. Proceedings of the National Academy of Sciences, 116632):15849-1588 2019.
[8] Rick Chartrand. Exact reconstruction of sparse signals via nonconvex minimization. IEEE Signal Processing Letters, 14(10):707-710, 2007.
[9] Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on Learning Theory, pages 1305-1338. PMLR, 2020.
[10] Christine De Mol, Ernesto De Vito, and Lorenzo Rosasco. Elastic-net regularization in learning theory. Journal of Complexity, 25(2):201-25 2009.
[11] Tolga Ergen and Mert Pilanci. Implicit convex regularizers of cnn architectures: Convex opti- mization of two-and three-layer networks polynomial time. arXiv preprint arXiv:2006.14798, 2020.
[12] Tolga Ergen and Mert Pilanci. Revealing the structure of deep neural networks via convex duality, pages 3004-3014, 2021.
[13] An Exgeniou and Massimiliano Pontil. Multi-task feature learning. Advances in neural information processing systems, 19:41, 2007.
[14] Suriya Gunasckar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. pages 1832-1841, 2018.
[15] Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Implicit bias of gradient descent on linear convolutional networks. arXiv preprint arXiv:1806.0044 2018.
[16] Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generalization gap large hatch training of neural networks. arXiv preprint urXiv:1705.088 2017.

---

[17] Yaohua Hu, Chong Li, Kaiwen Meng, Jing Qin, and Xiaoqi Yang. Group sparse optimization via lp. q regularization. The Journal of Machine Learning Research, 18(1):96010011 2017.
[18] Meena Jagadeesan, Ilya Razenshteyn, and Suriya Gunasekar. Inductive bias of multi-channel linear convolutional networks with bounded weight norm. arXiv preprint arXiv:2102. 2021.
[19] Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint
2018.
[20] Anders Krogh and John A Hertz. A simple weight decay can improve generalization. In Advances in neural information processing systems, pages 950-957, 1992.
[21] Hongzhou Lin and Stefanie Jegelka. Resnet with one-neuron hidden layers is a universal approximator. arXiv preprint arXiv:1806.10900 2018.
[22] Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: view from the width. arXiv preprint arXiv: 770.00550, 2017.
[23] Kaifeng Lyu and Jian Li, Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint 1rXiv:1906.05890 2019.
[24] Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro. Exploring generalization in deep learning, arXiv preprint arXiv: 08947, 2017.
[25] Behnam Neyshabur, Ryota Tomioka, Ruslan Salakhutdinov, and Nathan Srebro. Geometry of optimization and implicit regularization in deep learning. arXiv preprint arXiv:1705.03077.
2017.
[26] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: the role of implicit regularization in deep learning. arXiv preprint arXiv:1412.6611 26.4, 2014.
[27] Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. function space view of bounded norm infinite width relu nets: The multivariate case. arXiv preprint arXiv:1910.01635 2019.
[28] Mert Pilanci and Tolga Ergen. Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks. pages 7695-7705, 2020.
[29] David Rolnick and Max Tegmark. The power of deeper networks for expressing natural functions. arXiv preprint 1rXiiv1705.0055 2017.
[30] Arda Sahiner, Tolga Ergen, John Pauly, and Mert Pilanci. Vector-output relu neural network problems are copositive programs: Convex analysis of two layer networks and polynomial-time algorithms. arXiv preprint arXiv:2012.13.: 13329, 2020.
[31] Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? pages 2667-26990 2019.
[32] Mor Shpigel Nacson, Suriya Gunasekar, Jason D Lee, Nathan Srebro, and Daniel Soudry. Lexicographic and depth-sensitive margins in homogeneous and non-homogeneous deep models. arXiv e-prints, pages arXiv-1905, 2019.
[33] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent separable data. The Journal of Machine Learning Research, 19(1):2822-287.. 2018.
[34] Nathan Srebro, Jason DM Rennie, and Tommi Jaakkola. Maximum-mann margin matrix factoriza- tion. In NIPS, volume 17, pages 1329 1336. Citeseer, 2004.
[35] Arun Suggala, Adarsh Prasad, and Pradeep K Ravikumar. Connecting optimization and regularization paths. Advances in Neural Information Processing Systems, 31:10608--105 10619, 2018.
[36] Ryan J Tibshirani. Equivalences between sparse models and neural networks. 2021.
12

---

[37] Colin Wei, Jason Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. 2019.
[38] Dmitry Yarotsky. Optimal approximation of continuous functions by very deep relu networks. In Conference on Learning Theory, pages 639-649. PMLR, 2018.
[39] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint 16
2016.
[40] Hui Zou and Trevor Hastie. Regularization and variable selection via the elastic net. Journal of the royal statistical society: series B (statistical methodology), 67(2):301-320, 2005.
13


Reviews:
[{"review_id": "vJwzfzrlwg7", "reviewer": "Reviewer_n4py", "summary": "This paper investigates the correspondence between the architecture of a linear neural network and the complexity measure induced by putting $l_2$ regularization on the weights. On one hand, the authors study the complexity measure induced by fully-connected networks, diagonal networks, convolutional networks with full or limited filter width, as well as residual networks. On the other hand, the authors also present the architectures that induce $l_p$, $l_{p, q}$ as well as $k$-support norms as complexity measures.", "questions": "", "limitations": "", "rating": 6, "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": "To my knowledge, this work is a novel and nice contribution that extends previous work on the norms corresponding to linear neural networks with simpler architectures. The results are both mathematically interesting and potentially helpful for better understanding the implicit regularizations in linear neural networks. The writing is mostly clear.\n\nIn addition to the examples given on page 5, it could be helpful to give more examples of linear functions (matrices) whose relative complexities depend on what architectures we choose, e.g. convolutional versus fully-connected versus diagonal.\n\nSince the authors refer to [1] as a prior work that studies similar linear neural network models with single outputs or full convolutional filter widths, could the authors comment on how similar the techniques are between the two papers?\n\nAre there scenarios where grouping layers may be interesting practically? \n\n\nReference: 1. Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Implicit bias of gradient descent on linear convolutional networks.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "qlN0acZ0jEt", "reviewer": "Reviewer_o8fi", "summary": "The paper studies representation costs of linear networks and their induced complexity measures. First the representation costs of some standard architecture are given (fullly-connected nets, diagonal nets, convolutional nets, and residual nets), then for shallow networks a general formula for the representation cost (and its dual norm, given that the representation cost is convex) of any network is given. The second part of the paper is dedicated to the characterization of which complexity measures can appear from the representation cost of a neural network. Though this question is not answered in general, the authors study a number of related questions: a characterization of which $l_p$ can be represented by a neural network is given, then some example architectures are given to obtain group $l_{p,q}$ norms or $k$-support norms, then it is shown that $l_{p,q}$ group norm with overlapping groups and elastic nets cannot be recovered by a neural network representation cost (though it is possible for the representation cost of a general homogeneous parametrization). ", "questions": "", "limitations": "", "rating": 7, "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": "This paper gives a quite complete overview of the representation costs induced by linear networks. It is well-written though the statements of some Lemmas/Theorems (on finite filter width conv nets, the description of the grouping layers for example) are quite technical but no intuition/explanation is given, to help understand them (I imagine that this is due to a lack of space: this paper is made up of a large number of results, and there is not enough room to discuss the smaller ones).\n\nThe results of Section 3 are mostly slight generalizations/improvements of known results, as noted by the authors. The description of the \"residual nets\" is new though if I understand well, it represent the case of multiple parallel networks which is quite different to the traditional residual nets, so maybe it would be best to not call it residual networks. While this section lacks novelty it offers a good overview.\n\nSection 4 contains more novel results: to my knowledge the description of architectures leading to the $l_p$ norm, group $l_{p,q}$ norm and $k$-support norm are new. The discussion of negative results (norms that cannot be represented by a linear network) is also new and important to obtain a complete characterization of the complexity measures induced by DNNs, though this paper is only a first step in this direction.\n\nOverall, the strength of this paper is that it gives a good overview of the complexity measures induced by linear networks, what types of measures can and cannot be represented. Recent results have shown the important role that the representation cost of neural network plays, and this paper is a good step towards a characterization of the complexity measures induced by linear networks.\n\nThe weakness of this paper is that it is a collection of a many results, some of them small or not so novel and maybe some of the results could be dropped (for example the discussion of finite filter width conv nets is quite long and technical, yet it did not give me any particular insight on the effect of the finite width of the filter).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper is theoretical and as such has no direct societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "hWBaJ3w6Oj", "reviewer": "Reviewer_ZwDT", "summary": "This paper studies the representation cost in the setting of linear networks. It is shown that an l^2 regularization on the parameters corresponds to adding a penalty on the functional space governed by the representation cost. This paper shows how the representation cost depends on the architecture and how the bias depends on the representation cost. ", "questions": "", "limitations": "", "rating": 7, "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": "This is an interesting paper. The dictionaries between architectures and complexity measures are interesting. In particular, we see that certain penalty functions such as elastic net cannot be viewed as representation costs of certain architectures. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No societal impact", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "AVjQNYX2NN", "reviewer": "Reviewer_GxMP", "summary": "This paper studies the representation cost under different neural network models and the design of parameterization that leads to $l_2$ regularization.", "questions": "", "limitations": "", "rating": 8, "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": "This is a well-written paper with solid theoretical contributions. It first analyzes the representation cost (proposed in [1,2,3]) of different neural network models: \n\n1) fully connected network (Prop. 1 in Sec. 3.1.3); \n2) diagonal network (Prop. 2 in Sec. 3.1.2); \n3) convolutional network (Prop. 3 in Sec. 3.1.3);\n4) linear convolutional network (Thm. 4-6 in Sec. 3.2);\n5) linear non-homogeneous residual network (Thm. 7 in Sec. 3.3);\n6) depth 2 network (Lemma 8-9 in Sec. 3.4).\n\nThen the paper studies the design of parameterization that leads to certain regulations:\n\n1) $l_p$ norm (Thm. 10 and Prop. 11 in Sec 4.2);\n2) $l_{p,q}$ (Thm. 12 and 13 in Sec. 4.3);\n3) $k-$support norms (Thm. 14 in Sec 4.4);\n4) some other induced complexity measures (Sec. 4.5-4.6). \n\nComments:\nThe contents of this work are very solid and intense, it would have been great if the authors can spend more effort to build better connections between the results in different models. For example, how do the results in section 3 connect with each other in terms of assumptions/representation loss, perhaps the authors can provide a table or some experiments for better presentation. \n\nQuestions:\nHow does the result in section 3.4 relate to the result in section 3.1? It seems that the results in section 3.1 have already characterized the cases for general homogeneous networks with widths larger than 2, why do we need extra results on $d=2$?\n\ncitation:\n\n[1] Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Implicit bias of gradient descent on linear convolutional networks. arXiv preprint arXiv:1806.00468, 2018.\n\n[2] Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width relu nets: The multivariate case. arXiv preprint arXiv:1910.01635, 2019.\n\n[3] Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? pages 2667–2690, 2019.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As described in the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper gives a fairly complete list of results covering the representation cost for linear networks of many different architectures. The paper then studies how to design parametrization to encourage certain regularization effects. The reviewers find the results to be a solid theoretical contribution to the understanding of different parametrization.
Decision: Accept (Poster)