summaries: A streaming Stochastic Block Model (SBM) is proposed as null model to analyze streaming community detection algorithms on growing graphs. A online algorithm based on Belief Propagation (BP) is proposed to estimate community membership in this setting. It is proven to achieve the same accuracy as its offline variant BP in a simplified setting.

summaries: This paper tackles a streaming version of community detection, where the vertices of a graph generated with the classical stochastic block model are revealed sequentially, in a random order.  The authors restrict themselves to what they call $R$-local algorithms, wherein the new information brought by the arrival of a vertex is only propagated at distance at most $R$ of this revealed vertex.  In the absence of side information (i.e. additional information correlated with the ground truth community of each vertex), they show that this class of algorithms is unable to yield meaningful reconstruction when $n$ goes to infinity. In contrast, when side information is present, they provide an algorithm (StreamBP) for community detection, and show that this algorithm matches the performance of the classical belief propagation algorithm (OfflineBP) on the whole graph.   Those results are complemented by experiments on both synthetic and real-world datasets, comparing the StreamBP and OfflineBP algorithms, as well as several alternatives : simple voting algorithms, and a modified version of StreamBP (StreamBP*), modified to better deal with real-world datasets while enjoying the same theoretical guarantees as the original algorithm.

summaries: This paper proposes to do community detection in a variant of the stochastic block model for which nodes arrive in a streaming fashion, and there may exists noisy estimates of the real labels. They prove that if the noise render the side information uninformative, a local streaming algorithm is equivalent to a local algorithm, which cannot achieve non-trivial accuracy. If the side information is informative, they provide a belief propagation algorithm in the streaming setting which achieves comparable accuracy to offline BP asymptotically. Offline BP has been conjectured to be optimal, so their algorithm would also be optimal if the conjecture is proven (it is in special cases). They also provide another algorithm which is in practice more consistent than StreamBP.

summaries: The paper considers the problem of recovering the communities in a streaming version of stochastic block models, using information within a bounded radius. The main technical results are the limits of recovery with no side information, and a streaming version of belief propagation which has the same reconstruction accuracy as the offline BP algorithm using side information. The algorithms are evaluated on synthetic and real networks, and show good performance.

summaries: This paper studies a dynamic version of the stochastic block model, named as streaming stochastic block model (StSBM). The authors consider a sparse regime and analyze the asymptotic behavior of the model. In particular, the authors show that without some side information about the node labels, recovery of the true labels through a R-local streaming algorithm is no better than random guessing (Corollary 1). The authors also propose a streaming R-local belief propagation algorithm (StreamBP), and show their streaming algorithm perform as good as the offline version algorithm (Theorem 2). Empirical evaluations using synthetic and real-world datasets are provided in the paper.

abstractText: The community detection problem requires to cluster the nodes of a network into a small number of well-connected ‘communities’. There has been substantial recent progress in characterizing the fundamental statistical limits of community detection under simple stochastic block models. However, in real-world applications, the network structure is typically dynamic, with nodes that join over time. In this setting, we would like a detection algorithm to perform only a limited number of updates at each node arrival. While standard voting approaches satisfy this constraint, it is unclear whether they exploit the network information optimally. We introduce a simple model for networks growing over time which we refer to as streaming stochastic block model (StSBM). Within this model, we prove that voting algorithms have fundamental limitations. We also develop a streaming belief-propagation (STREAMBP) approach, for which we prove optimality in certain regimes. We validate our theoretical findings on synthetic and real data.

title: Community detection and stochastic block models: recent developments

venue: The Journal of Machine Learning Research,

authors:
Edoardo Maria Airoldi
David M Blei
Stephen E Fienberg
Eric P Xing

title: Mixed membership stochastic blockmodels

venue: Journal of machine learning research,

authors:
Emmanuel Abbe
Afonso S Bandeira
Georgina Hall

title: Exact recovery in the stochastic block model

venue: IEEE Transactions on Information Theory,

authors:
Lada A. Adamic
Natalie S. Glance

title: The political blogosphere and the 2004 u.s. election: divided they blog

venue: In LinkKDD,

authors:
Emmanuel Abbe
Colin Sandon

title: Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery

venue: In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science,

authors:
Aaron Clauset
Mark EJ Newman
Cristopher Moore

title: Finding community structure in very large networks

venue: Physical review E,

authors:
Mário Cordeiro
Rui Portocarrero Sarmento
Joao Gama

title: Dynamic community detection in evolving networks using locality modularity optimization

venue: Social Network Analysis and Mining,

authors:
Aurelien Decelle
Florent Krzakala
Cristopher Moore
Lenka Zdeborová

title: Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications

venue: Physical Review E,

authors:
Zhou Fan
Andrea Montanari

title: How well do local algorithms solve semidefinite programs

venue: In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing,

title: Community detection in graphs

venue: Physics reports,

authors:
Roger Guimera
Luis A Nunes Amaral

title: Functional cartography of complex metabolic

venue: networks. nature,

authors:
Andrew B. Goldberg
Ming Li
Xiaojin Zhu

title: Online manifold regularization: A new learning setting and empirical study. In Machine Learning and Knowledge Discovery in Databases, European Conference, ECML/PKDD, volume

authors:
Michelle Girvan
Mark EJ Newman

title: Community structure in social and biological networks

venue: Proceedings of the national academy of sciences,

authors:
David Gamarnik
Madhu Sudan

title: Limits of local algorithms over sparse random graphs

venue: In Proceedings of the 5th conference on Innovations in theoretical computer science,

authors:
Shayan Oveis Gharan
Luca Trevisan

title: Approximating the expansion profile and almost optimal local graph clustering

venue: In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science,

authors:
Hamed Hatami
László Lovász
Balázs Szegedy

title: Limits of locally–globally convergent graph sequences

venue: Geometric and Functional Analysis,

authors:
Samuel B Hopkins
David Steurer

title: Efficient bayesian estimation from few samples: community detection and related problems

venue: IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS),

authors:
Daxin Jiang
Chun Tang
Aidong Zhang

title: Cluster analysis for gene expression data: a survey

venue: IEEE Transactions on knowledge and data engineering,

authors:
Muhammad Aqib Javed
Muhammad Shahzad Younis
Siddique Latif
Junaid Qadir
Adeel Baig

title: Community detection in networks: A multidisciplinary review

venue: Journal of Network and Computer Applications,

authors:
Varun Kanade
Elchanan Mossel
Tselil Schramm

title: Global and local information in clustering labeled block models

authors:
Brian Karrer
Mark EJ Newman

title: Stochastic blockmodels and community structure in networks

authors:
Georg Krempl
Indre Žliobaite
Dariusz Brzeziński
Eyke Hüllermeier
Mark Last
Vincent Lemaire
Tino Noack
Ammar Shaker
Sonja Sievi
Myra Spiliopoulou
Jerzy Stefanowski

title: Open challenges for data stream mining research

venue: SIGKDD Explor. Newsl.,

authors:
Andrea Lancichinetti
Santo Fortunato

title: Community detection algorithms: a comparative analysis

authors:
Russell Lyons
Yuval Peres

title: Probability on trees and networks, volume 42

title: Community detection thresholds and the weak ramanujan property

venue: In Proceedings of the forty-sixth annual ACM symposium on Theory of computing,

authors:
L-E Martinet
MA Kramer
W Viles
LN Perkins
E Spencer
CJ Chu
SS Cash
ED Kolaczyk

title: Robust dynamic community detection with applications to human brain functional networks

venue: Nature communications,

authors:
Elchanan Mossel
Joe Neeman
Allan Sly

title: Belief propagation, robust reconstruction and optimal recovery of block models

venue: In Conference on Learning Theory,

title: Reconstruction and estimation in the planted partition model

venue: Probability Theory and Related Fields,

title: A proof of the block model threshold

venue: conjecture. Combinatorica,

authors:
Sara C Madeira
Arlindo L Oliveira

title: Biclustering algorithms for biological data analysis: a survey

venue: IEEE/ACM transactions on computational biology and bioinformatics,

title: Finding one community in a sparse graph

venue: Journal of Statistical Physics,

authors:
Elchanan Mossel
Jiaming Xu

title: Local algorithms for block models with side information

venue: In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science,

authors:
Symeon Papadopoulos
Yiannis Kompatsiaris
Athena Vakali
Ploutarchos Spyridonos

title: Community detection in social media

venue: Data Mining and Knowledge Discovery,

authors:
Ryan A. Rossi
Nesreen K. Ahmed

title: The network data repository with interactive graph analytics and visualization

venue: In AAAI,

authors:
Filippo Radicchi
Claudio Castellano
Federico Cecconi
Vittorio Loreto
Domenico Parisi

title: Defining and identifying communities in networks

authors:
Karl Rohe
Sourav Chatterjee
Bin Yu

title: Spectral clustering and the highdimensional stochastic blockmodel

venue: Annals of Statistics,

title: High-dimensional probability: An introduction with applications in data science, volume 47

authors:
Ulrike Von Luxburg
Mikhail Belkin
Olivier Bousquet

title: Consistency of spectral clustering

venue: The Annals of Statistics,

authors:
Tal Wagner
Sudipto Guha
Shiva Prasad Kasiviswanathan
Nina Mishra

title: Semisupervised learning on data streams via temporal label propagation

venue: In Proceedings of the 35th International Conference on Machine Learning, ICML,

authors:
Feifan Wang
Baihai Zhang
Senchun Chai
Yuanqing Xia

title: An extreme learning machine-based community detection algorithm in complex

authors:
Xiaojin Zhu
Zoubin Ghahramani
John D. Lafferty

title: Semi-supervised learning using gaussian fields and harmonic functions

venue: Machine Learning, Proceedings of the Twentieth International Conference ICML,

authors:
Xiangxiang Zeng
Wen Wang
Cong Chen
Gary G Yen

title: A consensus communitybased particle swarm optimization for dynamic community detection

venue: IEEE transactions on cybernetics,

heading: 1 Introduction

text:
Given a single realization of a network G = (V,E), the community detection problem requires to find a partition of its vertices into a small number of clusters or ‘communities’ [GN02, MO04, JTZ04, For10, PKVS12, JYL+18].
Numerous methods have been developed for community detection on static networks [GN02, CNM04, GA05, RCC+04, LF09, VLBB08, WZCX18]. However, the network structure evolves over time in most applications. For instance, in social networks new users can join the network; in online commerce new products can be listed; see [WGKM18, GLZ08, KvB+14] for other examples. In such dynamic settings, it is desirable to have algorithms that perform only a limited number of operations each time a node joins or leaves, possibly revising the labels of nodes in a neighborhood of the new node. (These notions will be formalized below.) Several groups have developed algorithms of this type in the recent past [HS12, CSG16, ZWCY19, MKV+20]. The present paper aims at characterizing the fundamental statistical limits of community detection in the dynamic setting, and proposing algorithms that achieve those limits.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
As usual, establishing fundamental statistical limits requires introducing a statistical model for the networkG = (V,E). In the case of static networks, precise characterizations have only been achieved recently, and almost uniquely for a simple network model, namely the stochastic block model (SBM) [HLL83, ABFX08, KN11, RCY+11, DKMZ11, Mas14, ABH15, AS15, MNS18]. In this paper we build on these recent advances and study a dynamic generalization of the SBM, which we refer to as streaming SBM (StSBM).
The SBM can be defined as follows. Each vertex v is given a label τ(v) drawn independently from a fixed distribution over the set [k] = {1, 2, . . . , k}. Edges are conditionally independent given vertex labels. Two vertices u, v are connected by an edge with probability Wτ(u),τ(v). The analyst is given a realization of the graph and required to estimate the labels τ . We will assume in addition that the analyst has access to some noisy version of the vertex labels, denoted by τ̃ = (τ̃(v))v∈V . This is a mathematically convenient generalization: the special case in which no noisy observations τ̃ are available can be captured by letting τ̃ be independent of τ . Further, such a generalization is useful to model cases in which covariate information is available at the nodes [MX16].
Informally, the streaming SBM (StSBM) is a version of SBM in which nodes are revealed one at a time in random order (see below for a formal definition). In order to model the notion that only a limited number of updates is performed each time a new node joins the network, we introduce a class of ‘local streaming algorithms.’ These encompass several algorithms in earlier literature, e.g, [ZGL03, CSG16]. Our definition is inspired and motivated by the more classical definition of local algorithms for static graphs. Local algorithms output estimates for one vertex based only on a small neighborhood around it, and thus scale well to large graphs; see [Suo13] for a survey. A substantial literature studies the behavior of local algorithms for sparse graphs [GT12, HLS14, GS14, Mon15, MX16, FM17].
Our results focus on the sparse regime in which the graph’s average degree is bounded. This is the most challenging regime for the SBM, and it is also relevant for real-world applications where networks are usually sparse. We present the following contributions:
Fundamental limitations of local streaming algorithms. We prove that, in the absence of side information, in streaming symmetric SBM (introduced in Section 2), local streaming algorithms (introduced in Section 3) do not achieve any non-trivial reconstruction: their accuracy is asymptotically the same as random guessing; see Corollary 1. This holds despite the fact that there exist polynomial time non-local algorithms that achieve significantly better accuracy. From a practical viewpoint, this indicates that methods with a small ‘locality radius’ (the range over which the algorithm updates its estimates) are ineffective at aggregating information: they perform poorly unless strong local side information is available.
Optimality of streaming belief propagation. On the positive side, in Section 4 we define a streaming version of belief propagation (BP), a local streaming algorithm that we call STREAMBP, parameterized by a locality radius R. We prove that, for any non-vanishing amount of side information, STREAMBP achieves the same reconstruction accuracy as offline BP; see Theorem 2. The latter is in turn conjectured to be the optimal offline polynomial-time algorithm [DKMZ11, Abb17, HS17]. Under this conjecture, there is no loss of performance in restricting to local streaming algorithms as long as (1) local side information is available; (2) the locality radius is sufficiently large; and (3) information is aggregated optimally via STREAMBP.
Let us emphasize that we do not claim (nor do we expect) STREAMBP to outperform offline BP. We use offline BP as an ‘oracle’ benchmark (as it has the full graph information available, and is not constrained to act in a streaming fashion).
Implementation and numerical experiments. In Section 5 and Appendix A–C, we validate our results both on synthetic data, generated according to the StSBM, and on real datasets. Our empirical results are consistent with the theory; in particular, STREAMBP substantially outperforms simple voting methods. However, we observe that it can behave poorly with large locality radius R. In order to overcome this problem, we introduce a ‘bounded distance’ version of STREAMBP, called STREAMBP∗, which appears to be more robust. (STREAMBP∗ can be shown to enjoy the same theoretical guarantees as STREAMBP.)

heading: 2 Streaming stochastic block model

text:
In this section we present a formal definition of the proposed model. The streaming stochastic block model is a probability distribution StSBM(n, k, p,W, α) over triples (τ, τ̃,G) where τ ∈ [k]n is a vector of labels (here [k] , {1, . . . , k}), τ̃ ∈ [k]n are noisy observations of the labels τ , and G = (G(0), G(1), . . . , G(n)) is a sequence of undirected graphs. Here G(t) = (V (t), E(t)) is a graph over |V (t)| = t vertices and, for each 0 ≤ t ≤ n− 1, V (t) ⊆ V (t+ 1) and E(t) ⊆ E(t+ 1). We will assume, without loss of generality, that V (n) = [n], and interpret τ(v) as the label associated to vertex v ∈ [n]. For each 0 ≤ t ≤ n − 1, G(t) is the subgraph induced in G(t + 1) by V (t); equivalently, all edges in E(t+ 1) \ E(t) are incident to the unique vertex in V (t+ 1) \ V (t).
The distribution StSBM(n, k, p,W, α) is parameterized by a scalar α ∈ [0, k−1k ], a probability vector p = (p1, . . . , pk) ∈ ∆k , {x ∈ [0, 1]k, 〈x, 1〉 = 1}, and a symmetric matrix W ∈ [0, 1]k×k. We draw the coordinates of τ independently with distribution p, and set τ̃(v) = τ(v) with probability 1− α, and τ̃(v) ∼ Unif([k] \ {τ(v)}) otherwise, independently across vertices:
P ( τ(v) = s ) = ps, P (τ̃(v) = s1 | τ(v) = s0) = { 1− α if s1 = s0, α/(k − 1) if s1 6= s0.
We then construct G(n) by generating conditionally independent edges, given (τ, τ̃), with P ( (u, v) ∈ E(n) | τ, τ̃ ) = Wτ(u),τ(v). (1)
Note that the labels τ̃ provide noisy ‘side information’ about the true labels τ . This information τ̃ is conditionally independent of the graph G(n) given τ . Finally we generate the graph sequence G by choosing a uniformly random permutation of the vertices (v(1), v(2), . . . , v(n)) and setting V (t) = {v(1), . . . , v(t)} and G(t) to the graph induced by V (t). If v = v(t), then we define t as the arrival order of vertex v. Note that, for each t, G(t) is distributed according to a standard SBM with t vertices: G(t) ∼ SBM(t, k, p,W ). An equivalent description is that (conditional on τ, τ̃ ) StSBM(n, k, p,W, α) defines a Markov chain over graphs. The new graph G(t + 1) is generated from G(t) by drawing the vertex v(t + 1) uniformly at random from [n] \ V (t), and then the edges (u, v(t+ 1)), u ∈ V (t), independently with probabilities given by Equation (1).
We are interested in the behavior of large graphs with bounded average degree. In order to focus on this regime, we will consider n → ∞ and W = W (n) → 0 with W (n) = W0/n for a matrix W0 ∈ Rk×k≥0 independent of n.
A case of special interest is the streaming symmetric SBM, StSSBM(n, k, a, b, α), which corresponds to taking p = (1/k, . . . , 1/k) and W0 having diagonal elements a and non-diagonal elements b. Finally, the case α = (k − 1)/k corresponds to pure noise τ̃ : in this case we can drop τ̃ from the observations and we will drop α from the distribution parameters.
hhnni矗 鸞
ag.ci
Nine
nazis
hdnet
矗tanto 䎖矗趱
tanto
engin
tanto

heading: 2.1 Definitions and notations

text:
For two nodes v, v′ ∈ V (t), we denote by dt(v, v′) their graph dista ce in G(t), i.e., the length of the shortest path in G(t) connecting v and v′, with dt(v, v′) = ∞ if no such path exists. We also write d(v, v′) = dn(v, v′) for the graph distance in G(n). For v ∈ V (n) and R ∈ N+, let BtR(v) = (V t R(v), E t R(v)) denote the ball of radius R in G(t) centered at v, i.e., the subgraph induced in G(t) by nodes V tR(v) , {v′ ∈ V (t) : dt(v, v′) ≤ R} and edges (v1, v2) ∈ E(t) with
3
v1, v2 ∈ V tR(v). Furthermore, let DtR(v) , {v′ ∈ V (t) : d(v, v′) = R}. Throughout the paper, unless otherwise stated, we assume (v1, v2) is an undirected edge.
We consider an algorithm A that takes as input the graph G(n) and side information τ̃ , and for each v ∈ V (n) outputs A(v;G(n), τ̃) ∈ [k] as an estimate for τ(v). Note that we always assume the arrival orders of vertices are observed (i.e., by observing v ∈ [n] we also observe the unique t ∈ [n] such that v = v(t)), thus G(n) contains the arrival order of its vertices. We define the estimation accuracy of algorithm A as
Qn(A) , E max π∈Sk 1 n ∑ v∈V (n) 1 (A(v;G(n), τ̃) = π ◦ τ(v)) . (2) Here Sk is the group of permutations over [k] and the expectation is with respect to G(n), τ, τ̃ , and the randomness of the algorithm (if A is randomized).

heading: 3 Local streaming algorithms

text:
In this section we introduce local streaming algorithms, which are a generalization of local algorithms in the dynamic network setting. An R-local streaming algorithm is an algorithm that at each vertex keeps some information available to that vertex. As a new vertex v(t) joins, information within the R-neighborhood BtR(v(t)) is pulled. An estimate for τ(v) is constructed based on information available to v. In order to accommodate randomized algorithms we assume that random variables (ξv)v∈V (n)
iid∼Unif([0, 1]), independent of the graph, are part of the local information available to the algorithm.
As an example, we can consider a simple voting algorithm. At each step t, this algorithm keeps in memory the current estimates τ̂(v) ∈ [k] for all v ∈ V (t). As a new vertex v(t) joins, its estimated label is determined according to
τ̂(v(t)) = argmaxs∈[k] πt(s) πt(s) = δ 1(s = τ̃(v(t))) + ∑
(v(t),u)∈E(t)
1(s = τ̂(u)) . (3)
In words, the estimated label at v(t) is the winner of a voting procedure, where the neighbors of v(t) contribute one vote each, while the side information at v(t) contributes δ votes.
For v ∈ V (n) and t ∈ [n], we denote the subgraph accessible to v at time t by Gtv = (Vtv, Etv), with initialization G0v = ({v}, ∅). At time t, we conduct the following updates:
Vtv ,  ⋃ v′∈V tR(v(t)) Vt−1v′ for v ∈ V tR(v(t)),
Vt−1v for v /∈ V tR(v(t)).
We let Gtv be the subgraph induced in G(t) by Vtv, and denote by Ḡtv = (V̄tv, Ētv) the corresponding labeled graph with vertex labels τ̃ and randomness ξ. Namely V̄tv , {(v′, τ̃(v′), ξv′) : v′ ∈ Vtv}, Ētv , Etv. At time t, all nodes in the R neighborhood of v(t) share the same updated subgraph Gtv(t) while the rest of the subgraphs stay unchanged. Let us emphasize that the ‘neighborhoods’ Gtv are not symmetric, in the sense that we can have v1 ∈ Gtv2 but v2 6∈ G t v1 . Definition 1 (R-local streaming algorithm). An algorithm A is an R-local streaming algorithm if, at each time t and for each vertex v ∈ V (t), it outputs an estimate of τ(v) denoted by At(v;G(t), τ̃) ∈ [k], which is a function uniquely of Ḡtv .
Note that this class includes as special cases voting algorithms (which correspond to R = 1) but also a broad class of other approaches. We will compare R-local streaming algorithms with R-local algorithms (non-streaming). In order to define the latter, given a neighborhood BtR(v), we define the corresponding labeled graph as B̄tR(v) , (V̄ t R(v), E t R(v)), with V̄ t R(v) , {(v′, τ̃(v′), ξv′) : v′ ∈ V tR(v(t))}. Definition 2 (R-local algorithm). An algorithm A is an R-local algorithm if, at each time t and for each vertex v ∈ V (t), it outputs an estimate of τ(v) denoted by At(v;G(t), τ̃) ∈ [k], which is a function uniquely of B̄tR(v).
For simplicity, define the final output of an algorithm A by A(v;G(n), τ̃) , An(v;G(n), τ̃). The next theorem states that, under StSSBM, any local streaming algorithm with fixed radius behaves asymptotically as a local algorithm. Here we focus on StSSBM—extension to asymmetric cases is straightforward. Theorem 1. Let G be distributed according to StSSBM(n, k, a, b, α), and v0 ∼ Unif([n]) be a vertex chosen independently of G. Then, for any > 0, there exist n , r ∈ N+, such that for every n ≥ n with probability at least 1− , the following properties hold: (1) Gnv0 is a subgraph of B n r (v0); and (2) v0 does not belong to Gnv for any v ∈ V (n)\V nr (v0).
Under the symmetric SBM, local algorithms without side information cannot achieve non-trivial estimation accuracy as defined in (2) [KMS16]. Therefore we have the following corollary of the first part of Theorem 1. Corollary 1. Under StSSBM(n, k, a, b) with no side information, no R-local streaming algorithm A can achieve non-trivial estimation accuracy. That is, limn→∞Qn(A) = 1/k. Remark 1. Corollary 1 does not hold if side information is available. As we will see below, an arbitrarily small amount of side information (any α < (k − 1)/k) can be boosted to ideal accuracy using R-local streaming algorithms with sufficiently large R. On the other hand, for a fixed small R, a small amount of side information has only limited impact on accuracy. Our numerical simulations illustrate this for voting algorithms, which are R-local for R = 1: they do not provide substantial boost over the use of only side information (i.e., the estimated label τ̂(v) = τ̃(v) at all vertices). Remark 2. In practice we can imagine keeping a small memory containing global information and updating it each time a new vertex joins. This global information would be available at each node. For example, we could keep track of the estimated size of each community. For a suitable class of algorithms of this type, it can be shown that they cannot achieve non-trivial reconstruction in the symmetric model StSSBM(n, k, a, b) either. Due to space constraints we do not present this result here. Interested readers are referred to Section G in the appendix.

heading: 4 Streaming belief propagation

text:
In this section we focus on the symmetric model StSSBM. Notice that this model makes community detection more difficult compared to the asymmetric model, as in the latter case average degrees for vertices are different across communities, and one can obtain non-trivial estimation accuracy by simply using the degree of each vertex. For the symmetric model StSSBM(n, k, a, b, α), we proved that local streaming algorithms cannot provide any non-trivial reconstruction of the true labels if no side information is provided, i.e., if α = (k − 1)/k. We also comment that, for a fixed (small) R, accuracy achieved by any algorithm is continuous in α, and hence a small amount of side information will have a small effect.
In contrast, for any non-vanishing side information α < (k − 1)/k, we conjecture that informationtheoretically optimal reconstruction is possible using a local streaming algorithm, under two conditions: (i) the locality radius R is large enough; and (ii) the following Kesten-Stigum (KS) condition is met:
λ , (a− b)2
a+ (k − 1)b > 1 . (4)
We will refer to λ as to the ‘signal-to-noise ratio’ (SNR).
We provide evidence towards this conjecture by proposing a streaming belief propagation algorithm (STREAMBP) and showing that it achieves asymptotically the same accuracy as the standard offline BP algorithm. The latter is believed to achieve information-theoretically optimal reconstruction above the KS threshold [DKMZ11, MNS14]. We will describe STREAMBP in the setting of the symmetric model StSSBM(n, k, a, b, α), but its generalization to the asymmetric case is immediate.
The algorithm has a state which is given by a vector of messages indexed by directed edges in G(t), mt = {mtu→v,mtv→u : (u, v) ∈ E(t)}. Note that G(t) is an undirected graph, and each edge (u, v) corresponds to two messages indexed by u → v and v → u. Each message is a probability distribution over [k]:
mu→v = (mu→v(1),mu→v(2), . . . ,mu→v(k)) ∈ ∆k .
The BP update is a map BP : (∆k)∗ × [k] → ∆k, where (∆k)∗ denotes the finite sequences of elements of ∆k:
BP({mi}i≤`; τ̃)(s) := BP0(τ̃)(s)
Z
∏̀ i=1 ( b+ (a− b)mi(s) ) . (5)
Here BP0(τ̃)(s) , ( α + (k − 1 − kα)1τ̃=s ) /(k − 1) and the constant Z = Z({mi : i ≤ `}; τ̃)
is defined implicitly by the normalization condition ∑ s∈[k] BP({mi : i ≤ `}; τ̃)(s) = 1. When a message v → u is updated, we compute its new value by applying the function (5) to the incoming messages into vertex v, with the exception of u→ v (non-backtracking property):
mv→u ← BP({mw→v : w ∈ ∂v \ {u}}; τ̃(v)) . (6)
Here ∂v denotes the set of neighbors of vertex v in the current graph. When a new vertex v(t) joins at time t, we use the above rule to: (1) update all the messages incoming into v(t), i.e., w → v(t), for w a neighbor of v(t) in G(t), and (2) update all messages at distance 1 ≤ ` ≤ R from v(t) in G(t), along paths outgoing from v(t), in order of increasing distance `. The pseudocode for STREAMBP is given in Algorithm 1, and an illustration in Figure 2. For the sake of simplicity, we analyze this algorithm in the two-group symmetric model StSSBM(n, 2, a, b, α). We believe that the extension of this analysis to other cases is straightforward, but we leave it out of this presentation.
Algorithm 1 Streaming R-local belief propagation
1: for t = 1, 2, . . . , n do 2: // Update the incoming messages: 3: for w ∈ Dt1(v(t)) do 4: mw→v(t) ← BP({mu→w : u ∈ ∂w \ {v(t)}}; τ̃(w)) 5: end for 6: // Update the outgoing messages: 7: for r = 1, 2, . . . , R do 8: for v ∈ Dtr(v(t)) do 9: Let v′ ∈ Dt1(v) on a shortest path
connecting v and v(t). 10: mv′→v ← BP({mu→v′ : u ∈
∂v′ \ {v}}; τ̃(v′)) 11: end for 12: end for 13: end for 14: for u ∈ V do 15: mu ← BP({mv→u}v∈∂u; τ̃(u)) 16: Output τ̂(u) := arg maxs∈[k]mu(s) as an estimate for τ(u). 17: end for
Our main result is that STREAMBP achieves asymptotically at least the same accuracy as offline BP, as originally proposed in [DKMZ11] and analyzed, e.g., in [MX16]. Offline BP performs the updates via Equation (6) in parallel on all the edges of G(n) for R − 1 iterations, and then computes vertex estimates using mu ← BP({mv→u}v∈∂u; τ̃(u)), τ̂(u) := arg maxs∈[k]mu(s). Note that, for each R, this defines an R-local algorithm, and hence we will refer to R as its radius. Theorem 2. For v ∈ V (n), let AR(v;G(n), τ̃) ∈ [k] be the estimate of τ(v) given by Algorithm 1 (STREAMBP), and AoffR (v;G(n), τ̃) ∈ [k] be the estimate given by offline BP with radius R (equivalently, BP with parallel updates, stopped after R iterations). Under the model StSSBM(n, 2, a, b, α), STREAMBP performs at least as well as offline BP:
lim inf n→∞
( Qn(AR)−Qn(AoffR ) ) ≥ 0.
It is conjectured that, in the presence of side information, i.e., for α < (k − 1)/k, offline BP is optimal among all polynomial-time algorithms [DKMZ11] (provided R can be taken arbitrarily
large). Whenever this is the case, the above theorem implies that STREAMBP is optimal as well. In the case of the symmetric model, it is also believed that under the KS condition (Equation 4), and for α < (k − 1)/k, offline BP does indeed achieve the information-theoretically optimal accuracy. This claim has been proven in certain cases by [MX16]: we can use the results of [MX16] in conjunction with Theorem 2 to obtain conditions under which STREAMBP is information-theoretically optimal. Corollary 2. Suppose one of the following conditions holds (for a sufficiently large absolute constant C) in the two-group symmetric model StSSBM(n, k = 2, a, b, α): (1) |a− b| < 2 and α ∈ (0, 1/2); (2) (a− b)2 > C(a+ b) and α ∈ (0, 1/2); or (3) α ∈ (0, 1/C). Then Algorithm 1 achieves optimal estimation accuracy:
lim sup R→∞ lim sup n→∞
( Qn(AR)− sup
A Qn(A)
) = 0.
(Here the supremum is taken over all algorithms, not necessarily local or online.)

heading: 5 Empirical evaluation

text:
In this section, we compare the empirical performance of two versions of our streaming belief propagation algorithm (Algorithm 1) with some baselines. We consider the following streaming algorithms:
• STREAMBP: proposed algorithm in this work with radius R, outlined in Algorithm 1. • STREAMBP∗: proposed algorithm in this work, which is a ‘bounded-distance’ version of
STREAMBP. It is described in more detail in Section 5.1, and its pseudocode is given in Algorithm 2. • VOTE1X, VOTE2X, VOTE3X: simple plurality voting algorithms that give a weight δ to the
side information, as defined in Equation (3) (the numbering corresponds to δ ∈ {1, 2, 3}). Despite looking somewhat naïve, voting algorithms are common in industrial applications.
We also compare the streaming algorithms above with ORACLEBP, which is the offline belief propagation algorithm, parameterized by its radius (number of parallel iterations) R. Note that in contrast to the streaming algorithms, to which we reveal one vertex at a time (along with its side information and the edges connecting it to previously revealed vertices), ORACLEBP has access to the entire graph and the side information of all the vertices from the beginning.
Our experiments are based both on synthetic datasets (Section 5.2) and on real-world datasets (Section 5.3). Because the model considered in this paper assumes undirected graphs, in a preprocessing step we convert the input graphs of the real-world datasets into undirected graphs by simply ignoring edge directions. Table 1 shows statistics of the datasets used (after making the graphs undirected); the values used for a and b for the real-world datasets are discussed in Section 5.3.
As the measure of accuracy, we use the empirical fraction of labels correctly recovered by each algorithm, that is
Acc = Ê max π∈Sk 1 n ∑ v∈V (n) 1 (A(v;G(n), τ̃) = π ◦ τ(v)) . In synthetic data we observe that, as soon as α < (k−1)/k, the maximization over π is not necessary (as expected from theory), and hence we drop it.

heading: 5.1 Bounded-distance streaming BP

text:
In our experimental results presented below, we observed that the simple implementation in Algorithm 1 exhibits undesirable behaviors for certain graphs. We believe this is caused by two factors. First, unlike ORACLEBP, we do not have an upper bound on the radius of influence of each vertex in STREAMBP; it may indeed use long paths. Second, the number of cycles in the graph increases as a, b grow. Large values of a and b can result in many paths being cycles, which negatively affects the performance of the algorithm.
In order to overcome these problems, we use two modifications. The first one is standard: we constrain messages so that mu→v(s) ∈ [ε, 1− ε] for some fixed small ε > 0 (we essentially constrain the log-likelihood ratios to be bounded).
The second modification defines a variant, presented in Algorithm 2, which we call STREAMBP∗. Here the estimate at node v is guaranteed to depend only on the graph structure and side information within BnR(v), and not on the information outside this ball. This constraint can be implemented in a message-passing fashion, by keeping, on each edge, R+ 1 distinct messages m0u→v, . . . ,m R u→v, corresponding to different locality radii.
5.2 Synthetic datasets
Algorithm 2 STREAMBP∗: Bounded-distance streaming BP
1: for t = 1, 2, . . . , n do 2: for v ∈ Dt1(v(t)) do 3: m0v→v(t) ← 1/k 4: for i = 1, 2, . . . , R do 5: miv→v(t) ← BP({mi−1v′→v}v′∈∂v\{v(t)}; τ̃(v)) 6: end for 7: end for 8: for v ∈ Dt1(v(t)) do 9: m0v(t)→v ← 1/k
10: for i = 1, 2, . . . , R do 11: miv(t)→v ← BP({mi−1v′→v(t)}v′∈∂v(t)\{v}; τ̃(v(t))) 12: end for 13: end for 14: for r = 2, 3, . . . , R do 15: for v ∈ Dtr(v(t)) do 16: Let v′ ∈ Dt1(v) on a shortest path connecting v and v(t). 17: for i = 1, 2, . . . , R do 18: miv′→v ← BP({mi−1u→v′}u∈∂v′\{v}; τ̃(v′)) 19: end for 20: end for 21: end for 22: end for 23: // Compute the estimates: 24: for u ∈ V do 25: mu ← BP({mRv→u}v∈∂u; τ̃(u)) 26: Output τ̂(u) := arg maxsmu(s) 27: end for
Figure 3 illustrates the effect of the radius on the performance of the algorithms.1 We use various settings for k, a, b, α. We observe that voting algorithms do not perform significantly better than the baseline 1−α (dashed line). This is due both to the very small radius R = 1 of these algorithms, and to the specific choice of the update rule. For R = 1, STREAMBP and STREAMBP∗ perform significantly better than voting, showing that their update rule is preferable. Their accuracy improves with R, and is often close to the optimal accuracy (i.e. the accuracy of ORACLEBP for large R) already for R ≈ 5. In Figure 4, we study the effect of the SNR parameter λ, defined in Equation (4), on the performance of the BP algorithms. The accuracy of the algorithms improves as λ increases. It is close to the baseline 1 − α when the SNR is close to the KS threshold at λ = 1, and then it improves for large λ. This is a trace of the phase transition at the KS threshold which is blurred because of side information. For large values of R, the accuracy of our streaming algorithms STREAMBP and STREAMBP∗ nearly matches that of the optimal offline algorithm ORACLEBP.
Further experiments on synthetic datasets are reported in Appendix A. We then present in Appendix B the result of experiments where no side information is provided to the algorithms. We observe that in the streaming setting, and for small radius (R), neither STREAMBP nor STREAMBP∗ achieves high accuracy (above 1/k) in the absence of side information, as suggested by our theoretical results.
1Notice that the three voting algorithms do not depend on the radius, resulting in horizontal lines in the diagram.

heading: 5.3 Real-world datasets

text:
We further investigate the performance of our algorithms on three real-world datasets: Cora [RA15], Citeseer [RA15], and Polblogs [AG05]. Cora and Citeseer are academic citation networks: vertices represent scientific publications partitioned into k = 7 and k = 6 classes respectively; directed edges represent citations of a publication by another. The Polblogs dataset represents the structure of the political blogosphere in the United States around its 2004 presidential election: vertices correspond to political blogs, and directed edges represent the existence of hyperlinks from one blog to another. The blogs are partitioned into k = 2 classes based on their political orientation (liberal or conservative).
As mentioned in the beginning of Section 5, in a preprocessing step we convert the input graphs of the real-world datasets into undirected graphs by simply ignoring edge directions. Also, since the graphs do not stem from the models of Section 2, we use oracle estimates of parameters a and b, obtained by matching the density of intra- and inter-community edges with those in the model StSSBM(n, k, ã, b̃, α). Namely, for a graph G = (V,E), letting V1, . . . , Vk ⊆ V be the ground-truth communities, we set ã = |V | · ∑ i∈[k]
∑ (u,v)∈E 1{u, v ∈ Vi}∑ i∈[k] (|Vi| 2 ) , b̃ = |V | · ∑ {i,j}∈([k]2 ) ∑ (u,v)∈E 1{u ∈ Vi, v ∈ Vj}∑ {i,j}∈([k]2 ) |Vi||Vj | .
For each dataset, we run the streaming algorithms STREAMBP and STREAMBP∗ using the parameters a = ã and b = b̃. Notice that these estimates cannot be implemented in practice because we do not know the communities Vj to start with. However, the performances appear not to be too sensitive to these estimates; we provide empirical evidence of this in Appendix A.
Figure 5 shows the accuracy of different algorithms on these datasets, for selected values of α. Although the graphs in these datasets are not random graphs generated according to StSBM, the empirical results generally align with the theoretical results we proved for that model. Specifically, we see that our streaming algorithm STREAMBP∗ is approximately as accurate as the offline algorithm ORACLEBP, and significantly better than the voting algorithms. STREAMBP produces high-quality results for Cora and Citeseer datasets, but behaves erratically on the Polblogs dataset. As Polblogs is relatively dense compared with Cora and Citeseer thus contains more cycles, such phenomenon is likely due to the issues discussed in Section 5.1.
Appendix C provides additional details on these experiments, as well as results for other values of α.
Acknowledgments and Disclosure of Funding
A.M. and Y.W. were partially supported by NSF grants CCF-2006489, IIS-1741162 and the ONR grant N00014-18-1-2729.
J.T. has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (grant agreement No 759471).

title: Streaming Belief Propagation for Community Detection


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.

summaries: 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.

summaries: 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.

summaries: 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.

summaries: 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:
Jacob Abernethy
Francis Bach
Theodoros Evgeniou
Jean-Philippe Vert

title: A new approach to collaborative filtering: Operator estimation with spectral regularization

venue: Journal of Machine Learning Research,

authors:
Alnur Ali
J Zico Kolter
Ryan J Tibshirani

title: A continuous-time view of early stopping for least squares regression

venue: In The 22nd International Conference on Artificial Intelligence and Statistics,

authors:
Zeyuan Allen-Zhu
Yuanzhi Li
Yingyu Liang

title: Learning and generalization in overparameterized neural networks, going beyond two layers

venue: arXiv preprint arXiv:1811.04918,

authors:
Yonatan Amit
Michael Fink
Nathan Srebro
Shimon Ullman

title: Uncovering shared structures in multiclass classification

venue: In Proceedings of the 24th international conference on Machine learning,

authors:
Andreas Argyriou
Theodoros Evgeniou
Massimiliano Pontil

title: Convex multi-task feature learning

venue: Machine learning,

authors:
Andreas Argyriou
Rina Foygel
Nathan Srebro

title: Sparse prediction with the k-support norm

venue: arXiv preprint arXiv:1204.5043,

authors:
Mikhail Belkin
Daniel Hsu
Siyuan Ma
Soumik Mandal

title: Reconciling modern machinelearning practice and the classical bias–variance trade-off

venue: Proceedings of the National Academy of Sciences,

title: Exact reconstruction of sparse signals via nonconvex minimization

venue: IEEE Signal Processing Letters,

authors:
Lenaic Chizat
Francis Bach

title: Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss

authors:
Christine De Mol
Ernesto De Vito
Lorenzo Rosasco

title: Elastic-net regularization in learning theory

venue: Journal of Complexity,

authors:
Tolga Ergen
Mert Pilanci

title: Implicit convex regularizers of cnn architectures: Convex optimization of two-and three-layer networks in polynomial time

venue: arXiv preprint arXiv:2006.14798,

title: Revealing the structure of deep neural networks via convex duality

authors:
An Evgeniou
Massimiliano Pontil

title: Multi-task feature learning

venue: Advances in neural information processing systems,

authors:
Suriya Gunasekar
Jason Lee
Daniel Soudry
Nathan Srebro

title: Characterizing implicit bias in terms of optimization geometry

title: Implicit bias of gradient descent on linear convolutional networks

venue: arXiv preprint arXiv:1806.00468,

authors:
Elad Hoffer
Itay Hubara
Daniel Soudry

title: Train longer, generalize better: closing the generalization gap in large batch training of neural networks

venue: arXiv preprint arXiv:1705.08741,

authors:
Yaohua Hu
Chong Li
Kaiwen Meng
Jing Qin
Xiaoqi Yang

title: Group sparse optimization via lp, q regularization

venue: The Journal of Machine Learning Research,

authors:
Meena Jagadeesan
Ilya Razenshteyn
Suriya Gunasekar

title: Inductive bias of multi-channel linear convolutional networks with bounded weight norm

venue: arXiv preprint arXiv:2102.12238,

authors:
Ziwei Ji
Matus Telgarsky

title: Risk and parameter convergence of logistic regression

venue: arXiv preprint arXiv:1803.07300,

authors:
Anders Krogh
John A Hertz

title: A simple weight decay can improve generalization

venue: In Advances in neural information processing systems,

authors:
Hongzhou Lin
Stefanie Jegelka

title: Resnet with one-neuron hidden layers is a universal approximator

venue: arXiv preprint arXiv:1806.10909,

authors:
Zhou Lu
Hongming Pu
Feicheng Wang
Zhiqiang Hu
Liwei Wang

title: The expressive power of neural networks: A view from the width

venue: arXiv preprint arXiv:1709.02540,

authors:
Kaifeng Lyu
Jian Li

title: Gradient descent maximizes the margin of homogeneous neural networks

venue: arXiv preprint arXiv:1906.05890,

authors:
Behnam Neyshabur
Srinadh Bhojanapalli
David McAllester
Nathan Srebro

title: Exploring generalization in deep learning

venue: arXiv preprint arXiv:1706.08947,

authors:
Behnam Neyshabur
Ryota Tomioka
Ruslan Salakhutdinov
Nathan Srebro

title: Geometry of optimization and implicit regularization in deep learning

venue: arXiv preprint arXiv:1705.03071,

authors:
Behnam Neyshabur
Ryota Tomioka
Nathan Srebro

title: In search of the real inductive bias: On the role of implicit regularization in deep learning

venue: arXiv preprint arXiv:1412.6614,

authors:
Greg Ongie
Rebecca Willett
Daniel Soudry
Nathan Srebro

title: A function space view of bounded norm infinite width relu nets: The multivariate case

authors:
Mert Pilanci
Tolga Ergen

title: Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks

authors:
David Rolnick
Max Tegmark

title: The power of deeper networks for expressing natural functions

venue: arXiv preprint arXiv:1705.05502,

authors:
Arda Sahiner
Tolga Ergen
John Pauly
Mert Pilanci

title: Vector-output relu neural network problems are copositive programs: Convex analysis of two layer networks and polynomial-time algorithms

authors:
Pedro Savarese
Itay Evron
Daniel Soudry
Nathan Srebro

title: How do infinite width bounded norm networks look in function space

authors:
Mor Shpigel Nacson
Suriya Gunasekar
Jason D Lee
Nathan Srebro
Daniel Soudry

title: Lexicographic and depth-sensitive margins in homogeneous and non-homogeneous deep models

authors:
Daniel Soudry
Elad Hoffer
Mor Shpigel Nacson
Suriya Gunasekar
Nathan Srebro

title: The implicit bias of gradient descent on separable data

authors:
Nathan Srebro
Jason DM Rennie
Tommi S Jaakkola

title: Maximum-margin matrix factorization

venue: In NIPS,

authors:
Arun Suggala
Adarsh Prasad
Pradeep K Ravikumar

title: Connecting optimization and regularization paths

venue: Advances in Neural Information Processing Systems,

title: Equivalences between sparse models and neural networks. 2021

authors:
Colin Wei
Jason Lee
Qiang Liu
Tengyu Ma

title: Regularization matters: Generalization and optimization of neural nets vs their induced kernel. 2019

title: Optimal approximation of continuous functions by very deep relu networks

authors:
Chiyuan Zhang
Samy Bengio
Moritz Hardt
Benjamin Recht
Oriol Vinyals

title: Understanding deep learning requires rethinking generalization

venue: arXiv preprint arXiv:1611.03530,

authors:
Hui Zou
Trevor Hastie

title: Regularization and variable selection via the elastic net

venue: Journal of the royal statistical society: series B (statistical methodology),

heading: 1 Introduction

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.

heading: 2 Setup

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 β.

heading: 3 Representation cost analysis

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.

heading: 3.1 Multiple output networks

heading: 3.1.1 Linear fully connected network

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.

heading: 3.1.2 Linear diagonal network

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.

heading: 3.1.3 Linear convolutional neural network (CNN)

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.

heading: 3.2 Linear non-homogeneous residual neural networks

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.

heading: 3.3 Depth two neural networks

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 .

heading: 4 Parameterization design

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.

heading: 4.1 Architecture design

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.

heading: 4.1.1 lp quasi-norms

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.

heading: 4.2 Limitations of homogeneous neural networks

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.

heading: 5 Conclusion

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.

heading: 6 Acknowledgement

text: Zhen Dai was funded by DARPA (grant number: HR00112190040) and NSF (grant DMS 1854831).

heading: 7 Funding Transparency Statement

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