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))(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 sEimago(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,2 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 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 Ic 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) (gjo))))))) 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). &f
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
FFC(es ((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-..))41)) 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
2/d 1/011//d1
0
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|| 2/d
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 mxxx 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(M)(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-homogeneous 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 d2l15 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). A/211 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": "Rf6Jz3Hb5wB", "reviewer": "Reviewer_w51Y", "summary": "This paper studies the induced regularization in predictor space of linear neural networks as a result of the weight decay (or $\\ell_2$) regularization on the network parameters. The authors also identify the impact of the choice of architecture and parameterization on the induced regularization.", "questions": "", "limitations": "", "rating": 6, "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": "The paper is well written and seems theoretically sound. I also believe the paper contains valuable insights to better understand the impact of architectural choices on the induced regularizers. However, there are some issues that need to be addressed as detailed below:\n\n- The paper only focuses on linear neural networks. I admit that most papers in the deep learning literature use linear networks as the theoretical surrogates of their nonlinear counterparts, however, I still believe that the authors should at least comment on the implications of this analysis for the architectures with nonlinear activations, e.g., ReLU. \n\n- I understand that this is a theory paper but I still wonder if the authors can verify some of their results via simple numerical experiments.\n\n- There are several missing references that are closely relevant and require in depth discussion. First of all, [1] extends (Gunasekar, 2018) to multi channel cases and allows arbitrary kernel sizes. Also, [2] discusses linear convolutional networks and shows that the regularized training problem can be cast as a convex optimization problem with certain regularization penalties. Similarly, [3-5] discuss the analyze the structural choices such as the number of outputs, depth, the choice of architecture and derive the induced regularization for the conventional weight decay regularized training problem. Can the authors comment on these papers and discuss the similarities/differences?\n\n__Minor comments:__\n\n- Notation: use the standard notation: $W_l$ for layer weights, $n$: number of samples, $d$: feature dim, and $L$: depth of the network.\n\n- I couldn’t find an explicit definition for $B$. Is it simply the multiplication of all layer weights?\n\n[1] Jagadeesan M et al. \"Inductive Bias of Multi-Channel Linear Convolutional Networks with Bounded Weight Norm\" \n\n[2] Pilanci M, Ergen T “Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks” \n\n[3] Ergen T, Pilanci M “Revealing the Structure of Deep Neural Networks via Convex Duality”\n\n[4] Ergen T, and Pilanci M. \" Implicit Convex Regularizers of CNN Architectures: Convex Optimization of Two- and Three-Layer Networks in Polynomial Time.\" \n\n[5] Sahiner A et al. \"Vector-output ReLU Neural Network Problems are Copositive Programs: Convex Analysis of Two Layer Networks and Polynomial-time Algorithms.\" \n\n===Post-Rebuttal Update===\n\nI have read the authors’ responses carefully. I appreciate the responses. The responses clarify some of my minor concerns, however, I still think that the main contribution of this paper is incremental due to analyzing only linear networks and considering the prior works I mentioned. Therefore, I'd like to keep my assessment.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately discussed the limitations.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "LTCuFKlfSL", "reviewer": "Reviewer_tBBM", "summary": "This paper studies the representation cost of linear neural networks. Considering a target linear function with parameter matrix $B$, the authors investigate the effect of $\\ell_2$ regularization in the predictor space. It is shown that a fully connected network regularizes the trace norm of $B$, diagonal network regularizes the $\\ell_{1,2}$ norm of $B$, convolutional network regularizes a certain norm of the discrete Fourier transform of B, etc. The authors also discuss how one can design a linear neural network architecture to achieve certain regularization effects.\n", "questions": "", "limitations": "", "rating": 6, "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": "I think this paper offers some valuable insights into the effect of different neural network architectures. Although I did not check all the proof details, the results look solid. However, I think this paper still has some weaknesses that could be addressed. I have the following detailed comments.\n\n1. The analysis in this paper stops at the calculation of the representation cost. However, it is not discussed how representation cost affects learning efficiency. It would be very helpful if the authors can give some examples of how the differences in representation cost affect the learning efficiency of linear networks.\n\n2. The paper does not offer sufficient discussions. For example, homogeneity has been mentioned many times in the paper and seems to be quite essential. The non-homogeneous cases are also highlighted in the title. However, there seems to be no discussion on how homogeneity affects the analysis.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative social impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "0rtkB9ZEbcD", "reviewer": "Reviewer_Hyxs", "summary": "This paper studies various ways to parameterize linear neural nets and explore the regularization on the linear mapping (in terms of the final function obtained by multiplying all weight layers in the linear net) induced by l2 regularization in parameter space. \n\nA large number of architectures are studied -- fully connected deep networks, diagonal networks, convolutional networks, and residual nets, with a characterization of the induced regularization for each of these settings. In addition, the paper also studies how to construct architectures to induce a particular desired regularizer. First, they study \\ell_p norms and show that the \\ell_p norm can be the induced regularizer if and only if p = 1, 2, with structural requirements on the architecture of the network. They also analyze which architectures can induce \\ell_{p, q} group norms. All of the results in this paper are for linear neural nets.", "questions": "", "limitations": "", "rating": 6, "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": "The strength of the paper is its thoroughness and attention to detail in terms of deriving precise theoretical results which characterize a variety of different settings. However, the clarity of the presentation could be improved, and the significance of these results are also unclear, since they only apply to linear networks. \n\nOriginality: The results in Section 3.1 and 3.2, which focus on characterizing the induced regularizers of various architectures, are mild generalizations of the results of [Gunasekar et al. '18], and are thus not very surprising. The results in Section 4 are, to my best knowledge, novel. \n\nQuality: The theoretical claims are sound. \n\nClarity: The paper is somewhat lacking in clarity. There is a lot of (perhaps unnecessary) complexity which probably detracts from the overall presentation of the paper; for example, Definition 1.1 appears overly complicated -- it's not quite clear why the equivalence classes are necessary. In another example of this, Section 4.2 is written abstractly in terms of general $\\ell_p$ norms, but the positive results in Theorem 10 only apply to $\\ell_1$ and $\\ell_2$ norms anyways -- it's likely more clear if the Theorem were written explicitly in terms of these norms. In addition, the results rely on abstract concepts such as mixing depths (Definition 4.2) and grouping layers (Definition 4.3). Some intuitive examples or figures would go a long way in helping convey these definitions better. \n\nSignificance: The impact of this work is limited because [Gunasekar et al. '18] already characterized a lot of the models in Sections 3.1 and 3.2 (with less generality), so the contributions in these sections alone are incremental and not enough for a strong paper. While the results in Section 4 are more novel, the stated motivation of developing architectures to induce various regularizers is not very convincing, because 1. there are probably more important concerns for architecture design, such as optimization and expressivity, and 2. an easier approach seems to be to directly regularize the desired induced regularizer. Thus, while the theory in this paper is nice, it's not clear how impactful it'll be.\n\n================================================================================================\n\nThanks to the authors for the responses to this and other reviews. My assessment of this paper is the same. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not address negative societal impact of their work -- this seems reasonable, given the theoretical nature of the work. However, the discussion of the limitations is quite lacking. The authors say that limitations are discussed in the conclusion, but the discussion appears to mostly be about extensions and future work, and not limitations of the current work.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: There is consensus among reviewers that this paper sets out in an interesting direction, and that it is thorough and precise in its analysis, but that ultimately arrives at results of limited significance. I second several of the reviewers' suggestions for work that could improve the paper in a future revision, including relating representation cost to statistical efficiency and extending its scope beyond linear networks (at least in discussion or experiments, and even if focused on specific nonlinear activations such a ReLUs).

More generally providing some experimental verification may offer another promising avenue for this work. The paper ultimately explores the regularization effects induced by architectures, but as reviewer Hyxs highlights, it is not clear how this interacts with effects induced on optimization, and exploring that empirically may clarify natural questions from the reader about practical implications of this work. Finally, I'll underscore the suggestion from reviewer Hyxs to simplify what may be unnecessarily complex definitions.
Decision: Accept (Poster)