summaries: 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.   A 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. 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.  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. 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.  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). 
abstractText: For different parameterizations (mappings from parameters to predictors), we study the regularization cost in predictor space induced by l2 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., lp quasi-norms, group quasi-norms, the k-support-norm, elastic net) can be the representation cost induced by simple l2 regularization, and designing the parameterizations that do so.
authors.name: Zhen Dai
authors.name: Mina Karzand
references.authors: Jacob Abernethy Francis Bach Theodoros Evgeniou Jean-Philippe Vert
references.title: A new approach to collaborative filtering: Operator estimation with spectral regularization
references.venue: Journal of Machine Learning Research,
references.authors: Alnur Ali J Zico Kolter Ryan J Tibshirani
references.title: A continuous-time view of early stopping for least squares regression
references.venue: In The 22nd International Conference on Artificial Intelligence and Statistics,
references.authors: Zeyuan Allen-Zhu Yuanzhi Li Yingyu Liang
references.title: Learning and generalization in overparameterized neural networks, going beyond two layers
references.venue: arXiv preprint arXiv:1811.04918,
references.authors: Yonatan Amit Michael Fink Nathan Srebro Shimon Ullman
references.title: Uncovering shared structures in multiclass classification
references.venue: In Proceedings of the 24th international conference on Machine learning,
references.authors: Andreas Argyriou Theodoros Evgeniou Massimiliano Pontil
references.title: Convex multi-task feature learning
references.venue: Machine learning,
references.authors: Andreas Argyriou Rina Foygel Nathan Srebro
references.title: Sparse prediction with the k-support norm
references.venue: arXiv preprint arXiv:1204.5043,
references.authors: Mikhail Belkin Daniel Hsu Siyuan Ma Soumik Mandal
references.title: Reconciling modern machinelearning practice and the classical bias–variance trade-off
references.venue: Proceedings of the National Academy of Sciences,
references.authors: Rick Chartrand
references.title: Exact reconstruction of sparse signals via nonconvex minimization
references.venue: IEEE Signal Processing Letters,
references.authors: Lenaic Chizat Francis Bach
references.title: Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss
references.venue: In Conference on Learning Theory,
references.authors: Christine De Mol Ernesto De Vito Lorenzo Rosasco
references.title: Elastic-net regularization in learning theory
references.venue: Journal of Complexity,
references.authors: Tolga Ergen Mert Pilanci
references.title: Implicit convex regularizers of cnn architectures: Convex optimization of two-and three-layer networks in polynomial time
references.venue: arXiv preprint arXiv:2006.14798,
references.authors: Tolga Ergen Mert Pilanci
references.title: Revealing the structure of deep neural networks via convex duality
references.authors: An Evgeniou Massimiliano Pontil
references.title: Multi-task feature learning
references.venue: Advances in neural information processing systems,
references.authors: Suriya Gunasekar Jason Lee Daniel Soudry Nathan Srebro
references.title: Characterizing implicit bias in terms of optimization geometry
references.authors: Suriya Gunasekar Jason Lee Daniel Soudry Nathan Srebro
references.title: Implicit bias of gradient descent on linear convolutional networks
references.venue: arXiv preprint arXiv:1806.00468,
references.authors: Elad Hoffer Itay Hubara Daniel Soudry
references.title: Train longer, generalize better: closing the generalization gap in large batch training of neural networks
references.venue: arXiv preprint arXiv:1705.08741,
references.authors: Yaohua Hu Chong Li Kaiwen Meng Jing Qin Xiaoqi Yang
references.title: Group sparse optimization via lp, q regularization
references.venue: The Journal of Machine Learning Research,
references.authors: Meena Jagadeesan Ilya Razenshteyn Suriya Gunasekar
references.title: Inductive bias of multi-channel linear convolutional networks with bounded weight norm
references.venue: arXiv preprint arXiv:2102.12238,
references.authors: Ziwei Ji Matus Telgarsky
references.title: Risk and parameter convergence of logistic regression
references.venue: arXiv preprint arXiv:1803.07300,
references.authors: Anders Krogh John A Hertz
references.title: A simple weight decay can improve generalization
references.venue: In Advances in neural information processing systems,
references.authors: Hongzhou Lin Stefanie Jegelka
references.title: Resnet with one-neuron hidden layers is a universal approximator
references.venue: arXiv preprint arXiv:1806.10909,
references.authors: Zhou Lu Hongming Pu Feicheng Wang Zhiqiang Hu Liwei Wang
references.title: The expressive power of neural networks: A view from the width
references.venue: arXiv preprint arXiv:1709.02540,
references.authors: Kaifeng Lyu Jian Li
references.title: Gradient descent maximizes the margin of homogeneous neural networks
references.venue: arXiv preprint arXiv:1906.05890,
references.authors: Behnam Neyshabur Srinadh Bhojanapalli David McAllester Nathan Srebro
references.title: Exploring generalization in deep learning
references.venue: arXiv preprint arXiv:1706.08947,
references.authors: Behnam Neyshabur Ryota Tomioka Ruslan Salakhutdinov Nathan Srebro
references.title: Geometry of optimization and implicit regularization in deep learning
references.venue: arXiv preprint arXiv:1705.03071,
references.authors: Behnam Neyshabur Ryota Tomioka Nathan Srebro
references.title: In search of the real inductive bias: On the role of implicit regularization in deep learning
references.venue: arXiv preprint arXiv:1412.6614,
references.authors: Greg Ongie Rebecca Willett Daniel Soudry Nathan Srebro
references.title: A function space view of bounded norm infinite width relu nets: The multivariate case
references.authors: Mert Pilanci Tolga Ergen
references.title: Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks
references.authors: David Rolnick Max Tegmark
references.title: The power of deeper networks for expressing natural functions
references.venue: arXiv preprint arXiv:1705.05502,
references.authors: Arda Sahiner Tolga Ergen John Pauly Mert Pilanci
references.title: Vector-output relu neural network problems are copositive programs: Convex analysis of two layer networks and polynomial-time algorithms
references.authors: Pedro Savarese Itay Evron Daniel Soudry Nathan Srebro
references.title: How do infinite width bounded norm networks look in function space
references.authors: Mor Shpigel Nacson Suriya Gunasekar Jason D Lee Nathan Srebro Daniel Soudry
references.title: Lexicographic and depth-sensitive margins in homogeneous and non-homogeneous deep models
references.authors: Daniel Soudry Elad Hoffer Mor Shpigel Nacson Suriya Gunasekar Nathan Srebro
references.title: The implicit bias of gradient descent on separable data
references.venue: The Journal of Machine Learning Research,
references.authors: Nathan Srebro Jason DM Rennie Tommi S Jaakkola
references.title: Maximum-margin matrix factorization
references.venue: In NIPS,
references.authors: Arun Suggala Adarsh Prasad Pradeep K Ravikumar
references.title: Connecting optimization and regularization paths
references.venue: Advances in Neural Information Processing Systems,
references.authors: Ryan J Tibshirani
references.title: Equivalences between sparse models and neural networks. 2021
references.authors: Colin Wei Jason Lee Qiang Liu Tengyu Ma
references.title: Regularization matters: Generalization and optimization of neural nets vs their induced kernel. 2019
references.authors: Dmitry Yarotsky
references.title: Optimal approximation of continuous functions by very deep relu networks
references.venue: In Conference on Learning Theory,
references.authors: Chiyuan Zhang Samy Bengio Moritz Hardt Benjamin Recht Oriol Vinyals
references.title: Understanding deep learning requires rethinking generalization
references.venue: arXiv preprint arXiv:1611.03530,
references.authors: Hui Zou Trevor Hastie
references.title: Regularization and variable selection via the elastic net
references.venue: Journal of the royal statistical society: series B (statistical methodology),
sections.text: For different parameterizations (mappings from parameters to predictors), we study the regularization cost in predictor space induced by l2 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., lp quasi-norms, group quasi-norms, the k-support-norm, elastic net) can be the representation cost induced by simple l2 regularization, and designing the parameterizations that do so.
sections.heading: 1 Introduction
sections.text: In a class of parameterized models, penalizing the l2 norm of the parameters induces regularization on function space which can be interpreted as a 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 × Rp −→ Rm, from input x ∈ X and parameters w ∈ Rp to predictions f(x;w). We denote the predictor implemented with parameters w by F (w) : X −→ Rm defined as F (w)(x) := f(x;w). Then image(F ) is the set of functions from X to Rm which can be obtained from this class of parameterized models. We will use F to denote a set of functions from X to Rm. The l2 regularization on parameters, either explicitly or implicitly, is a common phenomenon. As an example, in deep learning, explicit l2 regularization on parameters (a.k.a. weight decay) improves generalization ([20, 37]). Implicit regularization of l2 norm of parameters appears when we use gradient descent (GD) to train the model ([2, 35, 33, 19, 23, 32, 14, 25, 9, 18]). In particular, GD on homogeneous neural networks with logistic loss implicitly regularizes l2 norm on weights [23, 32].
  The representation cost ([15, 31, 27]) of a function g in image(F ) under the parametrization F is
  RF (g) = min{∥w∥22 : F (w) = g}. (1)
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  Consider learning a predictor F (w) with some loss function L(·) while controlling the l2 norm of parameters w by minimizing
  min w∈Rp
  L(F (w)) + λ∥w∥22 . (2)
  This is clearly equivalent to learning a function g in image(F ) by controlling RF (g) defined in Eq. (1):
  min g∈image(F ) L(g) + λRF (g). (3)
  In other words, the representation cost under the parameterization F , RF (·), captures the regularization on function space image(F ) induced by l2 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 norm on weights [23, 32], 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 of predictors parameterized by homogeneous models are arguably more related to implicit regularization, while representation costs of predictors parameterized by both homogeneous and non-homogeneous 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-homogeneous network.
  One way to motivate the study of representation cost is by considering the popularity of the overparameterized models, in which the number of parameters is 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 ([15, 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 an ordering on the space of predictors. Since representation cost is determined by the specific parametrization, each parameterization induces an ordering on the function space. This can be interpreted as 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 Rm and F∗ be the set of all functions from F to R. We define the equivalence relation in F∗ such that h1 and h2 ∈ F∗ (i.e., h1, h2 : F → R) are equivalent (h1 ∼= h2) if there exists a strictly increasing function ψ : R −→ R h1 = ψ ◦ h2. Let F∗/ ∼= be the set of equivalence classes of F∗ under ∼=. 1
  Given a parameterization F : Rp → F , let F be image(F ). In this case, for each value of parameter w ∈ Rp, F (w) ∈ F is a mapping from X to Rm. Let the representation cost RF under parameterization F be as in Eq. (1). We say that an equivalence class h̄ ∈ 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 can 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
  1In other words, F∗/ ∼= is a partition of F∗ into classes with the following property: given a class h̄ ∈ F∗/ ∼=, any two elements h1, h2 ∈ h̄ are equivalent (i.e. h1 = ψ ◦ h2).
  width changes as their filter width changes. Then, we show that the representation cost of residual networks interpolates between the representation costs of two of their component networks. Finally, we give two characterizations of the representation costs of depth-two neural networks. The results of this part are summarized in Table 1.
  In the second part (Section 4), given a few regularizers, we study when and how they can be the induced complexity measure of some architectures. Specifically, we show that lp quasi-norm can be the induced complexity measure induced by l2 regularization on some linear neural networks if 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 lp quasi-norms. In addition, we design architectures whose induced complexity measures are k-support-norm and lp,q group quasi-norms. Then, we show that elastic nets and lp,q quasi-norm with overlapping groups cannot be 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,q quasi-norm with overlapping groups. The results of this part are summarized in Table 2. Finally, in the conclusion, we discuss some interesting future directions.
  Further related works: Some previous work focuses on the expressive power image(F ) of the model [22, 29, 38, 21]. However, as discussed in [26, 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 to parametrizations.
  Representation cost has been studied before under various models. [15] showed that the representation cost of a linear convolutional neural network of depth d is strictly increasing in the Schatten-2/d quasi-norm on the Fourier domain, whereas the representation cost of a linear fully connected network of depth d is strictly increasing in the l2 norm. [31] and [27] studied depth-two fully connected
  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, [18] 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 l2 regularization on weights and convex optimization problems [28, 12, 11, 30]. In [28, 12, 11, 30], 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 literature on implicit regularization of gradient descent [2, 35, 33, 19, 23, 32, 14, 25, 9, 18], we looked into the induced regularization of weight decay on function space. Some of the results in [28, 12, 11, 30] are similar to the results in our work. For instance, the results on linear convolutional neural network in [28, 12, 11, 30] suggest that explicit l2 regularization on weight space is related to l1 regularization on the Fourier transform of the predictor. This result was also discovered in [15] and is generalized to multiple output and restricted filter width (a.k.a. kernel size) case in our work and in [18]. 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 lp,q group quasi-norms, which are not included in [28, 12, 11, 30].
  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 l2/d,2 group quasi-norms on the function space, for any d ∈ N. We also studied a similar question in section 4.1.2. However, we found architectures that induce lp,q group quasi-norms for both the case p > q and the case p < q. In addition, we showed that in the case p < q, lp,q quasi-norm can be induced by some linear neural network as induced complexity measure if and only if 2/p, 2/q ∈ N and designed architectures that do so.
sections.heading: 2 Setup
sections.text: A parameterized mapping f : X ×Rp → Rm is homogeneous of degree L if f(x;λw) = λLf(x;w), for all λ > 0. A feedforward neural network fN with weights (parameters) w = (W1, . . . ,Wd) and activation function σ is defined as fN (x;w) = σ(Wdσ(. . .W2σ(W1x))). Note that when the activation function σ is homogeneous (i.e. σ(λx) = λLσ(x) for some L > 0), the feedforward neural network fN is also homogeneous. In particular, with ReLU activation (i.e. σ(x) = max(0, x)) or identity activation (i.e. σ(x) = x), fN is homogeneous.
  A linear neural network is a neural network with identity activation function. When X = Rn and g is a linear function, we identify g with the matrix β ∈ Rm×n such that g(x) = βx. In particular, in the case of one-dimensional output space, we identify g with the vector β ∈ Rn such that g(x) = βTx. In this paper, we mainly focus on linear neural networks. A more general definition of linear neural networks in terms of a directed acyclic graphs will be useful in our work.
  Definition 2.1. Let G = (V,E) be a weighted directed acyclic graph, with n sources v1, v2, . . . vn (i.e. vertices with in-degree zero) and m sinks u1, u2, . . . , um (i.e. vertices with out-degree zero). The weight of edge e ∈ E, is denoted by g(e). Given parameters w ∈ Rp, a function ψ : E −→ [p] assigns parameters to edges such that g(e) = w[ψ(e)] for all e ∈ E. The pair (G,ψ) gives a construction of a linear feedforward neural network N corresponding to a linear predictor fN (·;w) : Rn → Rm as follows: Let ϕ(v) ∈ R be the output flow of the node v ∈ V . Given x ∈ Rn, let ϕ(vi) = x[i] for all input nodes i ∈ [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) := ∑ u:(u,v)∈E g(u)ϕ(u). Then ϕ(u) for sink nodes u give the linear predictor fN (x;w) = (ϕ(u1), ϕ(u2), . . . , ϕ(um)).
  Let FN be the parametrization associated with fN defined as FN (w)(x) := fN (x;w).
  The depth d of a linear feedforward neural network (G,ψ) 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 if every path from the source to the sink have the same length. We say that a linear feedforward neural
  network is without shared weights if the map ψ is a bijection. We call v1, . . . , vn the input nodes, u1, . . . , um the output nodes, and v ∈ V the nodes of the network N .
  Without loss of generality, we assume that for all v ∈ V , there exist a directed path from v to some output node uj and a directed path from some input node vi to v. Otherwise, removing v would not change fN . For each v ∈ V , let
  Sv = {i ∈ [n] : there exists a directed path from vi to v}. (4)
  By assumption, for all v ∈ V , |Sv| ≥ 1. Note that if a linear feedforward neural network N is homogeneous, then we can define its lth layer Nl as the set of vertices whose distance to any input node vi is l. 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 N be a depth d homogeneous feedforward linear neural network without shared weights. Then, the weights of the edges between the lth and l + 1th layer of N can be identified as a matrix Wl. In this case, the parameters w is a sequence of matrices W1,W2, . . . ,Wd with some fixed sparsity pattern, i.e. supp(Wl) = Sl for each l ∈ [d], where Sl is determined by N . The parameterized map fN and the parametrization FN are given by
  fN (x;w) := FN (w)(x) := ( d∏ l=1 Wd−l+1)x, (5)
  for x ∈ Rn, where w = (W1,W2, . . . ,Wd). Note that Eq. (5) is an equivalent definition of fN and FN when N is homogeneous and without shared weights. In the rest of the paper, unless stated otherwise, we will use N to denote a single output depth d homogeneous feedforward linear neural network without shared weights. Note that fN is homogeneous of degree d. Let N0 = [n] denote the input layer (we identify v1, . . . , vn with [n]) and Nd = {O} denote the output layer. With slight abuse of notation, let FN (w) ∈ Rn be the vector corresponding to the linear predictor generated by w on N . Let RN := RFN denote the representation cost (Eq. 1) under FN . We say that h is the induced complexity measure of N if it is the induced complexity measure of FN as defined in Def 1.1.
  Notation: We will use β ∈ Rn to denote a column vector, and βi or β[i] to denote the i-th component of β. We will use β̂ to denote the discrete Fourier transform of β. For groups G1, G2 . . . , Gk ⊆ [n],
  we use the definition of the lp,q group quasi-norm, ∥β∥p,q = (∑k j=1 (∑ i∈Gj |βi| q )p/q)1/p . Unless stated otherwise,G1, G2 . . . , andGk form a partition of [n] := {1, 2, . . . , n}. We will use β ∈ Rm×n to denote a matrix and β[j, k] to denote the element in the j-th row and k-th column of β.
sections.heading: 3 Representation cost analysis
sections.text: 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.
sections.heading: 3.1 Multiple output networks
sections.heading: 3.1.1 Linear fully connected network
sections.text: In a linear fully connected neural network,
  FFC(n1,n2,...,nd+1)(w) = d∏ i=1 Wd+1−i,
  where w = (W1,W2, · · · ,Wd) is the weights of the network. For i ∈ [d], the matrix Wi is in Rni+1×ni where ni ≥ min(m,n), n1 = n and nd+1 = m. Let RFC(n1,n2,...,nd+1) := RFFC(n1,n2,...,nd+1) be the representation cost under FFC(n1,n2,...,nd+1) defined in Eq. (1).
  Theorem 1. Suppose that ni ≥ min(m,n) for all i ∈ [d+ 1], where n1 = n and nd+1 = m. Then, for any β ∈ Rm×n,
  RFC(n1,n2,...,nd+1)(β) = d r∑ i=1 σ 2/d i ∼= ∥β∥SC2/d,
  where σ1, σ2, · · · , σr are the positive singular values of β and ∥β∥SC2/d := ( ∑r i=1 σ 2/d i )
  d/2 is the Schatten 2/d-quasi-norm of β. In particular, with a single output,
  RFC(n1,n2,...,nd+1)(β) = d∥β∥ 2/d 2 ∼= ∥β∥2.
  The above result is similar to a result in [18]. They studied two 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.
sections.heading: 3.1.2 Linear diagonal network
sections.text: In a linear diagonal network,
  FDNN (w) =Wd d∏ i=2 diag (wd+1−i),
  where w = (w1, w2, · · ·wd−1,Wd) is the parameters of a diagonal neural network. For i ∈ [d− 1], wi ∈ Rn, and Wd ∈ Rm×n. So a diagonal network consists of some diagonal layers followed by a fully connected layer. Let RDNN := RFDNN be the representation cost under FDNN defined in Eq. (1).
  Theorem 2. For any β = (β(1), β(2), · · · , β(n)) ∈ Rm×n,
  RDNN (β) = d n∑ i=1 ∥∥∥β(i)∥∥∥2/d 2 ∼= ∥β∥2/d,2,
  where ∥β∥2/d,2 := ( ∑n i=1 ∥∥β(i)∥∥2/d 2
  )d/2 is the matrix l2,2/d quasi-norm. In particular, with a single output
  RDNN (β) = d∥β∥2/d2/d ∼= ∥β∥2/d.
sections.heading: 3.1.3 Linear convolutional neural network (CNN)
sections.text: In a linear Convolutional neural network (CNN) with filter width q, the parameters w = (w1, w2, · · ·wd−1,Wd), where wi ∈ Rq × {0}n−q and Wd ∈ Rm×n. Let hi ∈ Rn be the outputs of the nodes in the ith layer. For i ∈ [d− 1], the transformation from the ith layer to the i+ 1th layer is given by hi+1[j] = 1√n ∑n k=1 wi+1[k]hi[(j + k − 1) mod n] =: (wi+1 ⊛ hi)[j]. The last layer is fully connected and hd = Wdhd−1. Then, the linear map is given by fCNN(q)(w, x) = FCNN (w)(x) =Wd(wd−1 ⊛ (wd−1 ⊛ (. . . w2 ⊛ (w1 ⊛ x) . . . ))). Equivalently,
  FCNN(q)(w) = d∏ i=1 Wd+1−i,
  where for each i ∈ [d − 1], wi[0] := wi[n] and Wi[j, k] = wi[(k − j + 1) mod n]/ √ n is the circulant matrix with respect to wi. Let RCNN(q)(β) := RFCNN(q)(β) be the representation cost under FCNN(q) defined in Eq. (1) filter width q.
  Let F ∈ Cn×n be the discrete Fourier transform matrix defined by F[j, k] = 1√ n ω (j−1)(k−1) n , where ωn = e 2πi/n. For β ∈ Rm×n, let β̂ := βF.
  Theorem 3. For any β ∈ Rm×n, let β̂ := βF and β̂(i) be the i-th column of β̂. Then,
  RCNN(n)(β) = d n∑ i=1 ∥∥∥β̂(i)∥∥∥2/d 2 ∼= ∥∥∥β̂∥∥∥ 2/d,2 ,
  where ∥∥∥β̂∥∥∥
  2/d,2 := (
  ∑n i=1 ∥∥∥β̂(i)∥∥∥2/d 2 )d/2 is the matrix l2,2/d quasi-norm. In particular, with a single
  output
  RCNN(n)(β) = d ∥∥∥β̂∥∥∥2/d
  2/d
  ∼= ∥∥∥β̂∥∥∥
  2/d .
  The same result for d = 2 was also discovered in [18].
  Results on linear CNN with restricted filter width q < n and some variations of CNN such as CNN with sum pooling and CNN with multiple channels can be found in the supplementary materials.
sections.heading: 3.2 Linear non-homogeneous residual neural networks
sections.text: Let N 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 N . Let I1, I2, . . . , Ik ⊆ [d] such that |Ij | = dj for each j ∈ [k]. For each j ∈ [k], let Ij = {j1, j2, . . . , jdj}, where j1 < j2 < · · · < jdj . For each w = (W1,W2, . . . ,Wd) and j ∈ [k], let
  FNj (w) := dj∏ i=1 Wj(dj−i+1) and FNResNet(w) := k∑ j=1 FNj (w). (6)
  be the parameterization for a residual neural network (ResNet). Let RResNet := RFNResNet be the representation cost under FNResNet , and Rj := RFNj be the representation cost under FNj for each j ∈ [k]. Theorem 4. Suppose that d1 < d2 < · · · < dk. Then, RResNet(λβ)/R1(λβ) −→ 1 as λ→ 0, and RResNet(λβ)/Rk(λβ) −→ 1 as λ→ ∞.
  Note that the model considered here includes sum of homogeneous models without shared weights, which is studied in [32]. A concrete example can be found in the supplementary materials.
sections.heading: 3.3 Depth two neural networks
sections.text: In this section, we characterize the representation costs of depth two homogeneous feedforward neural networks in two ways. We will use these two characterizations to find architectures that induce k-support norms [6] and l2,1 norms as induced complexity measures.
  Let d = 2. Note that the definition given in Eq. (4) becomes Sh = {i ∈ N0 : (i, h) ∈ E}, for each h ∈ N1 =: NH . Lemma 5. For a depth-two linear homogeneous feedforward neural network N without shared weights, RN (β) = 2min{ ∑ h∈NH ∥vh∥2 : supp(vh) ⊆ Sh, ∑ h∈NH vh = β}.
  In the above lemma, each vector vh corresponds to the linear predictor generated by the part of the network which includes the hidden node h and its neighbors. Lemma 5 implies that RN (·) is a norm. Let R∗N (·) be its dual norm. Now, we give a characterization of R∗N (·). Lemma 6. For a depth-two linear homogeneous feedforward neural network N without shared weights, R∗N (β) = 1 2 max{( ∑ i∈Sh β 2 i ) 1/2 : h ∈ NH}.
  By Lemma 6, if there exists h1, h2 ∈ NH such that h1 ̸= h2 and Sh1 ⊆ Sh2 , then removing h1 from N would not change the representation cost since ∑ i∈Sh1 β2i ≤ ∑ i∈Sh2 β2i .
sections.heading: 4 Parameterization design
sections.text: In order to further understand the dependence of induced complexity measure on architectures, we study when and how regularizers can be induced as the induced complexity measure by some architectures.
  In this section, we study a few regularizers such as lp quasi-norms, lp,q group quasi-norms with and without overlapping between groups, k−support norms, and elastic nets.
sections.heading: 4.1 Architecture design
sections.text: First, we design architectures that induce lp quasi-norms, lp,q quasi-norms without overlapping groups, and k−support norms as induced complexity measures respectively.
sections.heading: 4.1.1 lp quasi-norms
sections.text: In this section, we study architectures that induce lp quasi-norm, which is defined as ∥β∥p = ( ∑n
  i=1 |βi|p)1/p, where β ∈ Rn. Theorem 7. There exists a linear homogeneous feedforward neural network N without shared weights that induces lp quasi-norm if and only if 2/p ∈ N. In particular, diagonal network of depth 2/p induces lp quasi-norm.
  It turns out that we can capture all the architectures that induce lp quasi-norms using a simple combinatorial measure called mixing depths. Roughly speaking, for any S ⊆ [n], the mixing depth MN (S) is the index of the first layer that contains a node v such that S ⊆ Sv , where Sv is defined in Eq. (4).
  A linear homogeneous feedforward neural network N without shared weights induces lp quasi-norm if and only if MN (S) = 2/p, for all S ⊆ [n], |S| ≥ 2. The details can be found in supplementary materials on mixing depths and proofs are in supplementary materials for lp quasi-norms.
  4.1.2 lp,q group quasi-norms
  Similar to the previous sections, we want to know if and when lp,q group quasi-norm is the induced complexity measure of N . Remember the definition of of lp,q quasi-norm, ∥β∥p,q =(∑k
  j=1 (∑ i∈Gj |βi| q )p/q)1/p , where G1, G2 . . . Gk form a partition of [n].
  Unlike the results for lp quasi-norms, we 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 homogeneous feedforward linear neural networks without shared weights. Theorem 8. If there exists a linear homogeneous feedforward neural network N without shared weights that induces lp,q group quasi-norms, then 2/p, 2/q ∈ N. On the other hand, if 2/p, 2/q ∈ N and 2/p ≥ 2/q − 1, then there exists a linear homogeneous feedforward neural network N without shared weights that induces lp,q group quasi-norms.
  Next, we will design group networks that induce lp,q 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 a subnetwork is tightly related to that of the original network. This relationship, together with the results in Section 4.1.1 inform how certain subnetworks of a 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 a grouping layer and then followed by a diagonal network (Section 3.1.2). Two examples of such networks are in Figures 1c and 1d. The grouping layer is the first layer that mixes information from different input nodes. Depending on whether p < q or p > q, 2 we define two types of grouping layers: Definition 4.1 (Type I and II Grouping Layers). For each i ∈ [d], Ni is a type I grouping layer if Nj is diagonal for all j < i, |Ni| = k, where k is the number of groups, and for each j ∈ [k], there exists u ∈ Ni such that Su = Gj .
  2When p = q, lp,q quasi-norm becomes lp quasi-norm which we already studied.
  For each i ∈ [d], Ni is a type II grouping layer if Nj is diagonal for all j < i, |Ni| = ∏k
  j=1 |Gj |, where k is the number of groups, and for each h ∈ ∏k j=1Gj , there exists u ∈ Ni such that Su = h.
  Next, we compute the representation costs of networks with these two types of grouping layers.
  For d1, d2 ∈ N with d2 > d1, let N 1;d1,d2 be the architecture with d1 − 1 diagonal layers, followed by a type I grouping layer (Def 4.1), and then followed by a diagonal network of depth d2 − d1 (Section 3.1.2). See Figure 1c for an example of this kind of group network.
  Theorem 9. Let G1, G2 . . . Gk be a partition of [n]. Let βGj be the projection of β on Gj . Then for d2 > d1, RN 1;d1,d2 (β) = d2 ∑k j=1 ∥∥βGj∥∥2/d22/d1 = d2∥β∥2/d22/d2,2/d1 ∼= ∥β∥2/d2,2/d1 . The same architecture when d1 = 1 is also discovered in [36]. They also showed that in the group network N 1;1,d2 , l2 regularization on weights translate to l2/d2,2 regularization in the function space. Our result is stronger than the results in [36] in two ways. First, we found the architecture N 1;d1,d2 , which induces l2/d2,2/d1 quasi-norms for all d1, d2 ∈ [n], while they only did it for d1 = 1. Second, we proved that these are all the values of p, q such that lp,q group quasi-norms can be induced as induced complexity measures for some linear neural network, when p < q.
  For d1, d2 ∈ N with d2 > d1, let N 2;d1,d2 denote the architecture consisting of d1 − 1 diagonal layers, followed by a type II grouping layer (Def 4.1), and then followed by a diagonal network of depth d2 − d1 (Section 3.1.2). Figure 1d is an example of N 2;d1,d2 . In particular, when d1 = 1 and d2 = 2 (as in Figure 1b), N 2;1,2 induces l2,1 norm. This can be proved by the dual characterization of representation cost of depth-two networks in Lemma 6 and the fact that ∥β∥2,1 = ∥β∥ ∗ 2,∞.
  Theorem 10. When d2 = d1 + 1, RN 2;d1,d2 (β) = d2∥β∥ 2/d2 2/d1,2/d2 ∼= ∥β∥2/d1,2/d2 .
  This theorem implies that N 2;d1,d2 induces l2/d1,2/d2 quasi-norm when d2 = d1 + 1. Surprisingly, N 2;d1,d2 does not induce l2/d1,2/d2 quasi-norm when d2 > d1 + 1. The details are in supplementary materials.
  4.1.3 The k-support norms In [6], the k-support norm is defined as ∥β∥spk = min{ ∑ I∈Gk ∥vI∥2 : supp(vI) ⊆ I, ∑ I∈Gk vI = β}, for k ∈ [n], where Gk 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 a k-balanced network, if it contains ( n k ) nodes in the hidden layer such that for each subset I ⊆ [n] of size k, there is a node in the hidden layer which connects to input nodes in I . See Figure 1a for an example with n = 3 and k = 2.
  Theorem 11. For any k ∈ [n], there exists a 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.
sections.heading: 4.2 Limitations of homogeneous neural networks
sections.text: Theorem 8 and Theorem 11 give architectures that induce lp,q quasi-norms and k-support norms. Then, it is natural to consider two regularizers related to k-support norms and lp,q quasi-norms. Elastic nets 3 is defined as ∥β∥EN = ∥β∥1 + α∥β∥2, and lp,q quasi-norms with overlapping groups is defined as in Section 4.1.2 except that G1, G2 . . . Gk might overlap. Contrary to the results of k-support norm and lp,q quasi-norms, elastic nets and lp,q 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.
  3Elastic nets and k-support norms are both interpolations between l1 and l2 norms.
  Given these negative results, it is natural to look at non-homogeneous residual networks. We use the same definition of residual networks as in Section 3.2. Theorem 4 characterizes the asymptotic behavior of the representation costs of residual networks. The proof of the following theorem uses Theorem 4.
  Theorem 12. Suppose that d1 < d2 < · · · < dk. Let h : Rn −→ R be a homogeneous function. If FNResNet induces h as induced complexity measure, then FN1 also induces h as induced complexity measure.
  This theorem implies that the negative results on elastic nets, lp,q quasi-norm with overlapping groups, and lp quasi-norms when 2/p ̸∈ N still hold even in the case of non-homogeneous residual networks. As a 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 lp,q quasi-norms with overlapping groups for all p, q > 0, as induced complexity measure. The details are in supplementary materials.
sections.heading: 5 Conclusion
sections.text: 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 us design an architecture which induces this regularizer as induced complexity measure.
  For the first reason, many of the representation costs we study, when used as regularizers in learning problems, have good generalization properties. This includes lp,q group quasi-norms, especially in the context of multi-task or multi-class learning [13, 17], k-support norm [6], elastic net [10, 40], nuclear norm [4, 34, 1, 5], and lp quasi-norms for p ≤ 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, we do not mean designing an architecture from scratch based on a fully specified regularizer (as we do in section 4). Instead, we believe that building out our understanding in this regard can help us 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 it explicitly; but we might want to change representation cost or 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 of our work includes the fact that we are considering only a rather specific set of architectures, and in particular only 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 non-linear models might behave very differently, and so we should be cautious about how many of our insights carry over.
  To move beyond, there are still many unanswered questions for the linear models. For instance, for p, q ∈ N such that 2/p < 2/q − 1, does there exist an architecture that induce lp,q quasi-norm? Next step would be looking beyond linear predictors. For example, the question of analyzing representation cost for neural networks with non-linear activation functions such as ReLU is an open problem for most architectures. The other possible direction is studying the same questions (analysis and design) for functions with multiple outputs.
sections.heading: 6 Acknowledgement
sections.text: Zhen Dai was funded by DARPA (grant number: HR00112190040) and NSF (grant DMS 1854831).
sections.heading: 7 Funding Transparency Statement
sections.text: Funding in direct support of this work: DARPA grant (grant number: HR00112190040); NSF grant (grant DMS 1854831).
title: Representation Costs of Linear Neural Networks: Analysis and Design