On the Local Complexity of Linear Regions in Deep ReLU Networks
Authors: Niket Nikul Patel
Guido Montufar
Venue: ICML 2025 poster (2025)
Keywords: Linear Regions
Adversarial Robustness
Implicit Bias
Representation Learning
Primary area: deep_learning->theory

Abstract: We define the *local complexity* of a neural network with continuous piecewise linear activations as a measure of the density of linear regions over an input data distribution. We show theoretically that ReLU networks that learn low-dimensional feature representations have a lower local complexity. This allows us to connect recent empirical observations on feature learning at the level of the weight matrices with concrete properties of the learned functions. In particular, we show that the local complexity serves as an upper bound on the total variation of the function over the input data distribution and thus that feature learning can be related to adversarial robustness. Lastly, we consider how optimization drives ReLU networks towards solutions with lower local complexity. Overall, this work contributes a theoretical framework towards relating geometric properties of ReLU networks to different aspects of learning such as feature learning and representation cost.

On the Local Complexity of Linear Regions in Deep ReLU Networks
Niket Patel
Guido Montúfar 123
Abstract
The network function No: Ro - R parameterized by = (W;, Be)s then also be a CPWL function. For any fixed choice of the parameter 0, the imput domain Ie is partitioned into linear regions where the function is linear. These partitions of the input space have been used exten- sively to study diverse topics such as the expressive power, decision boundaries in classification, gradients and param- eter initialization, and generalization (e.g., Montúfar et al., 2014; Raghu et al., 2017: Zhang et al., 2018; Balestriero & Baraniuk, 2018; Grigsby & Lindsey, 2022; Brandenburg et al., 2024; Telgarsky, 2016). In this work we aim ad- vance theoretical framework towards better understanding the local distribution of linear regions near the data distribu- tion and how it relates to other relevant aspects of learning such as robustness and representation learning.
We define the local complexity of a neural net- work with continuous piecewise linear activations as a measure of the density of linear regions over an input data distribution. We show theoretically that ReLU networks that learn low-dimensional feature representations have a lower local com- plexity. This allows us to connect recent empirical observations on feature learning at the level of the weight matrices with concrete properties of the learned functions. In particular, we show that the local complexity serves as an upper bound on the total variation of the function over the input data distribution and thus that feature learning can be related to adversarial robustness. Lastly, we consider how optimization drives ReLU net- works towards solutions with lower local complex- ity. Overall, this work contributes a theoretical framework towards relating geometric properties of ReLU networks to different aspects of learning such as feature learning and representation cost.
1.1. Motivation
In the kernel regime, neural networks with piecewise linear activations are observed to follow lazy training (Chizat et al., 2019) and bias towards smooth interpolants which do not significantly change the structure of linear regions during training (see, e.g., Williams et al., 2019; Jin & Montúfar, 2023). On the other hand, for networks in the active regime, which are not well approximated by linearized models, one observes significant movement of the linear regions and in some cases a bias towards interpolants that have only a small number of linear regions (e.g.. Maennel et al., 2018; Williams et al., 2019; Shevehenko et al., 2022). Character- izing the dynamics of linear regions at a theoretical level remains a significant outstanding challenge, even for shal- low networks. Recent empirical studies have demonstrated interesting dynamics of the linear regions near the training data points. In particular, Humayun et al. (2024b) have shown that in the terminal phase of training, the number of linear regions near the data drops significantly, and this drop corresponds an increase in the model's adversarial robustness. We replicate similar experiments in Figure 3. In this work, we aim to develop theory explain some of the empirical results of Humayun et al. (2024b), Grokking describes sudden improvement in generalization error or robustness after prolonged training, typically occurring once the training loss is near zero. It linked to representation learning, suggesting that late generalization arises when a network develops the appropriate representations (Liu et al.,
1. Introduction
Despite the numerous achievements of deep learning, many of the mechanisms by which deep neural networks learn and generalize remain unclear. "Occam's 's Razor" style heuristic is that want our neural network to parameterize simple solution after training, but it can be challenging to establish a useful metric of the complexity of deep neural network (Hu et al., 2021). We may gain more insights in the case where we use pisce-wise linear activation functions, such as ReLU, LeL,y or Maxout. If is a continuous piecewise linear (CPWL) activation function and A((x) =
W.c 8 is a parameterized affine linear function, 1.... L. we consider a network of the following form:
N₂(x) AL 0o AL-1 .. 6o (I)),
I I R
(1)
'Department of Mathematics, UCLA, USA *Department of Statistics & Data Science, UCLA, USA 'MPI MiS. Germany. Correspondence to: Niket Patel pnikerppccllg.uul..ddd.... Guido Montúfar <mnnuufrr ucl..ucca..du>..
Proceedings of the 4dnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
2022). This leads to our first question:
input space. In Section we define the local complex- ity (ICC) as the average density of non-linearites over a dataset. To capture the typical behavior of the func- tions, we define this measure in a way that is robust to perturbations of the bias parameters.
Question 1: How does representation learning relate to the distribution of linear regions?
Some studies indicate that networks form low-dimensional representations during grokking (Fan et al., 2024; Yunis et al., 2024b;a). So, to better understand representation learning, we study the dimension of the feature manifold as measured by the average rank of the Jacobian of the in- termediate layer representations with respect to the input. In particular, based on the structure of various theoretical bounds (Montúfar, 2017; Serra et al., 2018; Hinz, 2021), we expect that networks that learn low low-dimensional feature manifolds will generally also have fewer linear regions. Em- pirical results also show that networks which undergo a drop in the number of linear regions tend be simpler, having nearly piecewise constant structure, hinting at connection between the distribution of the linear regions and the global structure of the learned function (Humayun et al., 2024b). Related is the concept of "neural collapse", which refers to a phenomenon where, in the terminal phase of training, the within-class variance of the last layer features tends towards zero (Papyan et al., 2020). Furthermore, prior literature has suggested a connection between the size of linear regions and robustness (Croce et al., 2019). Thus, natural question we concern ourselves with is:
In Section we establish theoretical connections be- tween the proposed local complexity and the local rank, which we define as the average dimension of the fea- ture manifold intermediate layers. This offers a link between the network complexity and representation learning.
In Section 5 we demonstrate bound between the local complexity and the total variation of a network over the input space. This offers a possible path towards under- standing how the linear regions can relate to adversarial robustness and phenomena like neural collapse.
We explore links between local complexity and param- eter optimization. In Section 6 we show that the local complexity is bounded by the representation cost and by the ranks of the weight matrices, As consequence, we can relate the density of linear regions to results on the implicit regularization of the ranks of weight matrices.
Question 2:
Can we connect the local density of linear regions to the robustness of a network?
2. Related Works
Several works have studied bounds on the number of linear regions of the functions represented by deep ReLU networks (c.g., Pascanu et al., 2014; Montúfar et al., 2014; Serra et al., 2018). For deep neural networks the maximum number of linear regions will typically be polynomial in the width and exponential in the input dimension and number of layers. However, the parameters that achieve this upper bound typi- cally occupy only a small region of the parameter space. In fact, if one considers the expected number of linear regions over a probability distribution of parameters that satisfies certain reasonable conditions, one finds that this is bounded above by the number of neurons raised the input dimen- sion (Hanin & Rolnick, 2019h;a; Tseran & Montúfar, 2021). In other words, for random choice of the parameters, one is more likely to see a number of linear regions that is much smaller than the hard upper bound. Some works have ana- lyzed the distortion length of curves in the input space by ReLU networks (Raghu et al., 2017). Hanin et al. (2022) looks at how the expected length of these curves changes from input to output of network. In a similar vein, Goujon et al. (2024) estimate the typical number of non-linearity points encountered by a ID curve in the input space. Other works have studied the effect that the architecture may have on the geometry and the topology of decision boundaries in classification (Zhang et al., 2018; Grigsby & Lindsey, 2022; Alfarra et al., 2023; Brandenburg et al., 2024).
We attempt answer this question by defining a measure of the local density of linear regions, and comparing this to the total variation of the network over the input space. As- pects in this direction have appeared in context of parameter initialization and the gradients of a network with respect to its inputs (e.g., Hanin & Rolnick, 2018; Tseran & Montúfar, 2023). Lastly, we are interested in the relation between parameters and functions, and how optimization may cause networks to converge to solutions with lower complexity in terms of linear regions. To this end we compare our mea- sure of local complexity to the distribution of parameters, building on ideas that have been used to study the expected number of linear regions (Hanin& & Rolnick, 2019b), and the representation cost of a network, a quantity which has been previously linked to sparsity of weight matrices (Jacot, 2023a).
1.2. Contributions
This work takes steps towards establishing quantitative links in ReLU networks between the distribution of linear regions in the input space, representation learning, and optimization:
We introduce a novel framework for understanding model complexity based on the linear regions over the
2

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
A few works have tried to understand the local behavior and the dynamics of linear regions during training. In par- ticular, Humayun et al. (2024b) compare the phenomenon of grokking to simplification of the linear regions near the training data points. They demonstrate empirically that during the terminal phase of training, a relatively sudden drop in the number of linear regions corresponds to an im- provement in the model's ss adversarial robustness. Cohan et al. (2022) study the evolution of linear regions in the state space of networks trained for deep reinforcement learn- ing, finding a decrease in the density during training, as measured by trajectories in the state space. In a related work, Zhu et al. (2020) derive an algorithm for computing an upper bound on the number of linear regions near a data point and look into the training dynamics of the linear re- gions. Sattelberg et al. (2023) examine the linear regions local to dataset of trained networks and note that they tend to be relatively simple. Croce et al. (2019) relate the size of linear regions to adversarial robustness. Another result that links complexity of the linear regions to robustness is that of Humayun et al. (2023b), which leverages the linear region structure of ReLU networks to design an algorithm which improves adversarial robustness. Similar to some of our results, Li et al. (2022) relate adversarial robustness to model complexity as defined by the VC dimension. In a similar flavor to our definition of the local complexity,
tion bears resemblance to their definition of the geometric complexity.
3. The Local Complexity of ReLU Networks
We first aim to define a notion that captures the density of linear regions locally near a given dataset. We will consider ReLU networks defined as in (I), with input dimension no. hidden layers of widths B1s--.. PL-11 and output di- mension n = 1. Given fixed parameter & and an input n, the 9th layer feature vector pre-activation is given by vr(x) = A o Φ o Ar-1 1 o (I E R", The array of sign vectors jsgu (z) is called the activation pattern for the input 2; and the set of all inputs that share the same activation pattern is the corresponding activation region in input space, for the given parameter 0. For each fixed param- eter value, the function No has constant slope over each activation region. We make the mild assumption that no two activation regions whose activation pattern differ by one neuron will share the same slope. This is a generic property that holds true for all parameters except for a zero Lebesgue measure subset (Hanin & Rolnick, 2019b; Grigsby & Lind- sey, 2022), and implies that the activation regions coincide with the linear regions.
For fixed parameter 0, the nonlinear locus of the network Ng over the input space is given by
Gamba et al. (2022) build a complexity measure related to linear regions and propose that the exact number of linear regions may not be the best metric for model complexity, preferring instead to focus on a more robust measure. Other studies have examined knot points (non-linearities) from optimization perspective. Notably, Shevehenko et al. (2022) bounded the number of knots between training inputs for univariate shallow ReLU networks in the mean-field regime (Mei et al., 2018; Rotskoff & Handen-Eijnden 2022).
BN, (x E Ro V..oo.)) is discontinuous at z).. (2)
This partitions the input space into the linear regions.
3.1. Computing Local Complexity
We seek to define measure for the local density of linear regions that robust to small perturbations of the weights. We take the view that the average number of linear regions over a local region of parameter space can be more mean- ingful than the number of regions at a fixed parameter value. Thus, we wish to understand By, as a random object given choice of weight matrices.
We may also highlight a few of the works that look at the di- mensionality of representations, such as those of Humayun et al. (2024a); Jacot (2023a;b); Jacot et al. (2024); Scarvelis & Solomon (2024). Our definition of local rank bears simi- larity to that of Humayun et al. (2024a) and Patel & Shwartz- Ziv (2024) as well as the "Jacobian rank" introduced by Jacot (2023a). The low-rank bias of neural networks is a related idea that has been studied by Súkeník et al. (2024) and Timor et al. (2023). Several other works in this area have sought characterize the dimension of data manifolds through the use of diffusion models (Stanczuk et al., 2022). A connection between the rank of learned embeddings and the representation cost was demonstrated in the work of Ja- cot (2023a). The papers of Dherin et al. (2022); Munn et al. (2024) highlight connections between neural collapse and a quantity they called the "geometric complexity", which is generally reminiscent of the Dirichlet energy. Our definition of the total variation of network over the data distribu-
Tracking the number of linear regions for particular pa- rameters requires that one solves system of parametric equations of the form (x) = Sr.5, which can be diffi- cult. On the other hand, examples from algebraic geometry suggest that tracking expected values of the number of so- lutions to parametric systems can be easier (Malajovich, 2023). This approach and the resulting proof techniques bear resemblance to the application of the co-area formula in the work of Hanin & Rolnick (2019b) or the Kac-Rice formula, which is known for characterizing the size of level sets in random fields (Berzin et al., 2022). However, key distinction lies in our focus. In contrast to the definitions of Hanin& & Rolnick (2019b), we will consider the distribution of linear regions over the input space and the behavior de-
3

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
Figure 1. Left: Linear regions of trained neural network over two-dimensional input domain. The nonlinear locus is shown in black and linear regions colored at random. Right: Heat map of the numerically estimated local complexity density function f(x) over the domain. Precise details are provided in Appendix B.I. The figure shows that our definition of local complexity, as well as the equations derived in Theorem 2, consistent with our interpretation of this quantity local density of non-linearity over the input space.
pending on specific parameters, which are aspects that are not covered in their work.
The limit is taken with respect to the radius of a ball B. (x) around the input point a, and the normalization factor is given by the volume of the ball:
Here and in the following we will write the pre-activation of the ith unit at the tth layer as (x)) =z, Be, where Be, is the bias. The simplest model that allows us to consider expected values is to introduce additive noise 5e, and track the 0 level set (z) + òe possible to introduce additive noise to both biases and weights, but we will focus on the biases since these only translate the activation boundaries, whereas the weights affect both the position and the orientation of the activation boundaries. In Appendix В we provide numerical illustrations showcas- ing the effects of adding noise either only to the biases or adding noise to both the biases and the weights and how both models produce qualitatively similar results.
Z, vol.n ng (B. no
(4)
We illustrate this definition in Figure 1, where numeri- cally estimate the density function f over the input space for a network with two-dimensional input. We demonstrate the impact of a on the local complexity qualitatively in Appendix B.1. We now define the local complexity of our neural network as the expectation of over the input data distribution. We denote by p the probability distribution of the data over the input space IR" which will assume have density and compact support Ω
Let 0 31,,31, W2, 82. WL, be particular choice of parameters. Consider then the parameters with noisy biases 0 = (W1, 31 + 81 W2, B2 ,,....,W', + ōr.), where the noise terms are mutually independent and identically distributed zero-mean Gaussian, ō; ~ ((,, ), with some fixed standard deviation o > 0. We denote the bias with the noise term as b, = 31 + 8g. For this random variable, we consider the expected volume of the non-linear locus B,, around any input point x and define corresponding density as the limit:
Definition 1 (Local Complexity). We define the local com- plexity of a network N at parameter 0 with respect to the input data distribution
LC = E [f()]] xmp
(5)
For simplicity of notation we will omit the arguments Ng and p when there no risk of confusion. We define local complexity by taking the expectation of f over the data distribution to estimate the density of linear regions near the dataset, where model complexity is most relevant. To provide further intuition for this definition and later results, we conduct a direct computation of the local complexity for few illustrative examples in Appendix A.2.
f(x) = lim co Z.
E. 1 O (z)))), x E "o
(3)
Here the expectation is taken with respect to the random parameter 0 or more specifically the noise terms 81,..., 8t.

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
3.2. Towards Theoretical Understanding of the Local Complexity
v V280 E n0 and Enj = O ( 6 6 /n²
/n²)
such that:
We can now introduce first results in understanding this measure of the complexity of neural network with respect to the data distribution p. As before, we denote the pre-bias value of the ith neuron of the network at input x by z (1)), for i = ......E= Tig- For neuron 2; in layer I, we say that is good at x: if the computation graph of the net- work evaluated at input x contains a path of active neurons Fjot:..... z/--1 from layers I + 1 to L, where for each neu- ron in this path, 2j; (4)) > b/.- In particular, this means that the neuron 2, affects the network's 's output when evaluated at x. More details on this can be found in Appendix A. We denote by Pb. the Gaussian density function for the bias of neuron zi perturbed by 6;. We will denote by (x) the gradient of function 2; with respect to r where this is well defined. The oon-differentiable points form a null set and are inconsequential in the following results. The follow- ing theorem provides an explicit formula for computing the
LC 2
2 bias
Σ
E (222()))22266) -B-C-B-Cuue -B.grrd Obias-
newron 24 0:2mp
(8)
We note that the term B Cgrad Chias. while neces- sary inclusion based on our proof technique, may be quite small. Indeed at initialization Hanin & Rolnick (2019a, Appendix D) observe that for any neuron z and 12" P(z is good at x) 2 11 Σt 2- Thus, at initialization, B I NL 2 where N N= E, my and = miny ni, which decays exponentially with the width. Our empirical results in Appendix B.4 have shown that, for fully MLPs of rea- sonable width, B is typically measured to be constant at O. Similarly, the term En can also be small, and notably asymptotically smaller than el for large values of r).
4. Connections to the Rank of Learned Representations
local complexity, which we prove in Appendix A.3.
Theorem 2. Let Pb. (I:) N(3,,) a) be the density for the bias of neuron 24. Then the following holds:
We define the feature manifold at layer I, denoted Mr S RT to be the pre-activation values of the Ith layer when evaluated the support of the input data distribution, Ω. We proceed by introducing measure of the dimen- sion of the feature manifold, which we call the local rank. We write 2i = [.I,,,..,, [1,m,] for the vector of pre-bias pre-activations at the /th layer and Jzz((z) = a (x)...., ... Zz (z:))" for the Jacobian with respect to the input. With this notation, we can write the feature manifold as M₁ (S2).
LC= Σ E (1V2(() Pb. (z((x)) Le is good ot æ]
newrn 2, 2.
(6)
where for each neuron the expectation is taken over Ô and x
Definition (Local Rank). We define the local rank (LR) of the lth layer's features as the expectation value of the dimension of the feature manifold over the input data distri- bution:
This theorem gives us a way to compute the local complex- ity empirically by computing the gradients at each neuron and estimating (6) using samples (we leverage this in our numerical experiments in Figures 1, 2. 3). We can now introduce bounds on the local complexity, which will be useful for our later analysis because they allow to focus on the gradient terms.
LR = E [rank(J=z(<))) pmp,8
(9)
We will find it more convenient, both numerically and analytically, to work with the approximate rank, rank, = Ha 2 e: a singular value of AJ}, which satis- fies lim, LR LRR,
Corollary& 3. In the same setting as Theorem 2, let Ograd be an upper bound on the norm of the grudient of ev- ery neuron Zi. (W1,3 3 + S1,..., WL, B + ō1., let Opios = -VZro- "2na" and let B Eg Eneuron a; es not good at denote the expected number neurons that are not good. Then we have that:
[2)(())| & Cyrud for all x E Ω 0 =
LR = E frank, (J,z(()) p=pp.
(10)
xmp
A generic input point x will lie inside a linear region of 2ı, and the Jacobian matrix J. provides this linearization of 2₁. The null space of the Jacobian indicates the input dimensions that are discarded near the input x, and the rank is equal to the dimension of the set of feature values
LC S Chias
Σ
E
neurron 21 8:amup
We use the standard Big Theta notation f(x) ((g(z)) to signify that there exist C1, no such that (19(#) S f(x) S (2g(2) for all x. > zo-
Furthermore, for any n > 0 there are constants
5

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
100
40
80
Local Complexky
35-
Local Local Hank
25
Local Rank Layer
Layer
Legend Complexity
Local Rank Layer
Layer
20
10"
10a
10
10a
10'
10"
10
10'
10
10
10'
Iteration
Iteration
Figure 2. Relation hetween the local rank (10) intermediate layers and the local complexity (2) of linear regions in the terminal phase training. train a 4 layer MLP with neurons per layer to estimate a map between two multivariate Gaussians with a random cross-covariance matrix. More information can be found in Appendix B.2.
traced perturb the input x. Thus, this a meaningful measure of the rank of the learned representations.
5. Networks with Lower Local Complexity May Be More Robust
Our aim is to provide a connection between the local rank of the representations in Definition& 4 and the local complex- ity of the learned functions in Definition 1. We prove the following result in Appendix A.5, linking the two notions:
Neural networks have been shown to sometimes converge to solutions that exhibit neural collapse (Papyan et al., 2020). In this case, the networks have a low within-class variance of representations in the last hidden layer, implying that the learned function flat around the data points. We will attempt understand this specific geometric prop- erty by considering the total variation of trained neu- ral network over the data distribution, which we define as TV = Eg.--p. [|| ,.,((z)) [I]- A low expected total varia- tion indicates that the gradient of the network function is typically small over the data distribution. Consequently, these networks develop stable regions around training data points where the function is nearly constant, aligning with the characteristies of neural collapse.
Theorem 5. For any O, the local ranks across layers can be bounded in terms of the local complexity as follows:
LC
Σ
O LRi +
(11)
Tig Ohias
Moreover, in the same setting as in Corollary
Σ LR
LC+ E, + B Cgrad Chias]
(12)
Di
We remark that low total variation has implications for ad- versarial robustness. Standard methods for generating adver- sarial examples, such as Projected Gradient Descent (PGD), rely on first-order optimization techniques for constructing adversarial examples (Madry et al., 2018). Low total vari- ation with respect the data distribution makes harder for such methods to find adversarial examples, since small gradients limit the effectiveness of first-order optimization. In some settings, the total variation can be related directly to the existence of adversarial examples. Suppose we have a univariate network Ng: - for classification, with decision boundary at No = 0. For given with NO 0, point (z No(x) 0. Then we have the following proposition, which prove in Appendix A.7.
We can also make weaker claim about the exact local rank, which prove in Corollary 13 in the appendíx: LC < no Cbius Cerad Σle VLR,
We showcase the relation between the local rank and local complexity in simple example. Figure 2 shows the evolu- tion of LC and LR during training, for Gaussian input and output data. In this example both quantities appear to tightly related and we observe stark and sudden drop in the local rank late training. The information theoretic proper- ties of the rank of representations for this particular example has been studied in the prior work of Patel & Shwartz-Ziv (2024). While this behavior is not unique to this example, on other datasets the dynamics of the local rank can become much more complex, as we showcase Figure 12 in the appendix.
( is adversarial example if
Proposition Suppose our data distribution admits a den- sity function p with support Q. Consider a point & in the interior of Z with classification margin No(T) > % For
6

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
200
Accuracy
Test Accuracy
Accuracy
Vortatio
Locall Complaxity
125
Accuracy
100
0.4
0.2
50
25
0.0
10a 10
10º
10a
10' 10'
10a 10'
10/
101
10*
10"
10"
Iteration
Iteraioo
Figure 3. Drop in the expected total variation (7) and local complexity (2) of network in the terminal phase of training. We find that this corresponds to an increase the adversarial robustness of our network. Here we train a layer ML.P with neurons each layer on subset of 1000 images across all classes in the MNIST dataset. We use initialization scale that is 2x the standard He initialization. More information and an ablation on the initialization scale is available in Appendix B.3.
any with (z) E Q let = in(zeB.(E) p(z). Then TV & C.Y implies there are no adversarial examples in (T).
6. The Drop of Local Complexity, and a Connection to Grokking
In this section, we explore ways in which the local com- plexity might be implicitly minimized during training via representation cost and implicit regularization of weights.
Empirical results have shown that a drop in the local number of linear regions is accompanied by an increase in adversar- ial robustness (Humayun et al., 2024b). We can understand this by developing bound between the local complexity and the expected total variation of that network. A proof can be found in Appendix A.8.
6.1. Representation Cost
The representation cost of function f is the smallest pos- sible parameter norm needed for a neural network No to exactly compute We define this R(f) inf [ N9(x) (x) for all x E S...2 Prior works have analyzed the representation cost of shallow networks of arbitrary width (Savarese et al., 2019). The representation cost for linear networks can be explicitly calculated in certain cases, and is often connected to sparsity. For instance, in fully- connected linear networks, is a Schatten quasi norm of the end-to-end matrix (Dai et al., 2021). Deeper nonlinear networks also share connection between the representa- tion cost and sparsity in terms of rank (Jacot, 2023a). The following proposition, which we prove in Appendix A.9, provides a way to view the representation cost as metric of sparsity, this time in terms the linear regions.
Let gi denote rest of the network after the Ith layer, that No- gi p(z: bi). Let Ci denote the Lipschitz constant of gt- Then with the same setting and notations Theorem 2:
Theorem 7.
Le
TV.
maxigigL Ct En BB
B- -.grdd Cbias S LC. (13)
This bound could help explain the findings of Humayun et al. (2024b), where ReLU networks trained in classi- fication task converged to solutions that are flat near data points and the non-linear locus is concentrated around the decision boundaries. We empirically demonstrate this be- havior on the MNIST dataset Figure 3. We note however that this theoretical result may fully explain the relation- ship between the total variation and the local complexity during training. Indeed, in Appendix B.3 we illustrate that the dynamics can be more complex as consequence of the relationship between TV and the Lipschitz constants maxigIsL Ct. A more detailed empirical study analysis on the tightness of this bound can be found in Appendix B.4.
Proposition 8. In the same setting Theorem 2, where n4 is the maximum hidden layer dimension,
1-2 n10 LC < ni
L R(No))
(14)
bios
This bound provides
understanding of how weight
decay and the resulting reduction of parameter norms may
"One may also take inf, [[]]]] ||f Noll <) for appropriate norm and limit

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
play role in the simplification of linear regions that we find late in training, as we will discuss below in Corollary 10.
complexity:
t
6.2. Linking Local Complexity to Neural Network Optimization
L maxie([) WWpllop
Obias n2
7io
1-L
12-
LC
7
(16)
Humayun al. (2024b) presents empirical results that re- late grokking to a migration of the linear regions in the terminal phase of training. In particular, they find drop in the local number of linear regions near data points late in training. We aim to understand this drop of linear regions late in training as a drop in the local complexity. We can leverage as a heuristic the view of grokking provided by Lyu et al. (2024), who show grokking can be induced by dichotomy of early and late phase implicit biases. This is only a heuristic way for us to view grokking in our setting, since that work requires the network to be everywhere C² smooth, which is only true almost everywhere for our ReLUU networks. However, it may be possible to generalize their re- sult with a careful analysis with Clarke sub-differentials (Ji & Telgarsky, 2020; Clarke, 1975). Nevertheless, following Lyu al. (2024) we consider:
B V2
++1 L
S Vv2
(17)
where, 7 = l| (v TW The
WWT
We observe that the result in Proposition 9 is rigorous, but the corresponding bound only holds when our network is at the global minimum of (15). Another view we can take is by considering the norm of the weights. Lyu et al. (2024) show in the rich phase of training that [|0(t)]22 = + (llo 2)122). If we assume that this holds, using calculations in Ap- pendix A.9, we can show that the local complexity is asymp- totically bounded by the weight decay parameter X.
Corollary 10. [Informal] Suppose that [10(t)]12 θ (log 1)/42) holds. Then, in the "rich" phase of training the local complexity is bounded:
d VC((0 - 2/101|2- di
They show that networks will first operate in the "kernel" regime (Jacot et al., 2018), during which the parameters do not move far from initialization. We show in Appendix A. that this implics that the local complexity also does not change much from initialization in shallow networks. After enough time, the network will eventually enter the "rich" regime and converge in direction to KKT point of the following optimization problem; where { J:) C pe x 1 is the training dataset:
LC S O(log })
(18)
Obius
11-4
We empirically validate this claim in Figure 13, where we demonstrate that the local complexity will typically be lower for networks trained with a larger weight decay. However, it should be noted that the bound in (8) does not leverage the dependence on the data distribution, so it is likely that these bounds could be improved through more exact analysis.
min 2 1012
s.t. sNNo(1)) 2 1, Iie [n].
(15)
7. Conclusions and Future Work
Summary We presented a framework for analyzing the distribution of linear regions of the functions parametrized by neural networks with piecewise linear activations. We introduced measure of local complexity that is robust with respect to perturbations of the parameters and used this to gain insights into relevant aspects of learning such as robust- ness and representation learning. Specifically, we establish that networks that learn low-dimensional representations tend to exhibit lower local complexity. Further, we con- nected the local complexity of linear regions to the total variation of the network functions and thus to robustness. We also analyze how the local complexity can be implicitly minimized during training by connecting it to properties of the weight matrices. Overall, this work contributes a theoretical framework that illustrates interesting interrela- tions between geometric properties of ReLU networks and learning that we hope might motivate further investigations.
In this setting, Timor et al. (2023) show that the global optimum of (15) has bounded ratios between the Frobenius norm and operator norm of weight matrices. We can relate this to the local complexity and show that in this setting the local complexity is also bounded as follows.
Proposition 9. Let W)) Ro x {-1,1} be a binary classification dataset, and assume that there is E [n]] with || < 1. Assume that there is a fully-connected neural network N of width m 2 2 and depth 2 2, such that for all E [n] we have yxN(x,)) Z I, and the weight matrices W1, WI...., We of N satisfy [|,lle SB B for some B > 0. Let No be fully-connected neurul network of width m' 2 m and depth K' > k parameterized by 0. Let 8" = [Wi...., [[] be a global optimum of the above optimization problem (15). Then, assuming the same setting as Theorem 2, we have the following bound on the local
8

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
Limitations and future research We focused on the ReLU activation function but we think that our proof tech- niques could be adapted to obtain similar results for gen- eral piecewise linear activation functions. Such generaliza- tions could be approached as Tseran & Montúfar (2021)
Brandenburg, M.-C., Loho, G., and Montúfar, G. The real tropical geometry of neural networks for binary classi- fication. Transactions on Machine Learning Research, 2024. URL https: https////pppeeieeeeeeeeeeee net/ forum? id= JWW JFFTI288.22.
approached the analysis of expected complexity for maxout networks building on the work of Hanin Rolnick (2019a)
Chizat, L.., Oyallon, E., and Bach, F. On lazy training in differentiable programming. vances in Neural Information Processing Sys- tems, volume 32. Curran Associates, Inc., 2019. URL cc co//ppppeeffiilss/peer////////1 de51465776hhadd332002667622233 Paper.. pdf.
for ReLU, Though we find interesting results suggesting the proposed local complexity measure might be implicitly minimized during training, detailed analysis addressing the training dynamics of the local complexity remains open problem. Empirically, in certain settings we can of- ten observe complex interactions between local complexity and local rank, as well as between local complexity and total variation. This suggests that the explicit relationship between the local complexity and other measures of model complexity may be much richer than what is covered by our theoretical results. Another natural direction would be to construct explicit bounds on the generalization gap based on the local complexity, as one would expect that networks with a simple structure in terms of their linear regions would also generalize well.
Ad-
https://proceed.ngs neurips.
Clarke, F. H. Generalized gradients and applications. Trans- actions of the American Mathematical Society, 205:247- 262, 1975.
Cohan, S., Kim, N. H. G., Rolnick, D., and van de Panne, M. Understanding the evolution of linear regions in deep reinforcement learning. In Advances in Neural Information Processing Systems, 2022. URL https: / //oppnrevvew. www.ww..eeee................ net. wewt/ffrrmmidddeyynttttaee
Acknowledgments
Croce, F. Andriushchenko, M., and Hein, M. Prov- able robustness of ReLU networks via maximization of linear regions. In Proceedings of the Twenty- Second International Conference on Artificial Intelli- gence and Statistics, volume 89 of Proceedings of Ma- chine Learning Research, pp. 2057-2066. PMLR, 2019. URL https: /tte::/pproooe /ppppeeeeeeinn..ccceeeeeecc...ee www. mlr.press/v/9. crocel 9a html.
This project has been supported by NSF CCF-2212520, NSF DMS-2145630, DFG SPP 2298 project 464109215, and BMBF in DAAD project 57616814.
Impact Statement
This paper presents work whose goal is advance the field of machine learning and its theory. We do not foresee any particular societal impacts that must be highlighted here.
Dai, Z., Karzand, M., and Srebro, N. Representation costs of linear neural networks: Analysis and design. In Advances in Neural Information Processing Systems, 2021. URL https: //ppnr/veeeeeeewww net/ forum? i (d=3ooyjABdbe
References
Alfarra, M., Bibi, A., Hammoud, H., Gaafar, M., and Ghanem, B. On the decision boundaries of neural net- works: tropical geometry perspective. IEEE Transac- tions on Pattern Analysis and Machine Intelligence, 45(4): 5027-5037, 2023,
Dherin, B., Munn, M., Rosca, M., and Barrett, D. Why neural networks find simple solutions: The many regu- larizers of geometric complexity. Advances in Neural Information Processing Systems, 35:2333-234 2349, 2022.
doi: TLL.1//TTAA...02..3500
Balestriero, R. and Baraniuk, R. A spline theory of deep
Fan, S., Pascanu, R., and Jaggi, M. Deep grokking: Would deep neural networks generalize better? arXiv preprint NKtV:2405.19454. 2024.
learning. In Proceedings of the 35th International Confer-
ence on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 374-383, PMLR, 2018 URL htlhhtt/:/// /ttpse/es////oooedigggee. mlr www..press/vee ba balestrieroll 8b. html.
Gamba, M., ShmielewskiiAndeee A., Sullivan, J., Azizpour, H., and Bjorkman, M. Are all linear regions created equal? In Proceedings of The 25th International Confer- ence on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 6573- h/ppoceeedingss mir.press/ v 51 gamba 22a html.
Berzin, C., Latour, A., and León, J. Kac-Rice Formula: A contemporary overview of the main results and ap- plications. working paper or preprint, 2022. URL https:/ //hps: sccience/hal--36eee
6590. PMLR, 2022. URL https: /

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
Goujon, A., Etemadi, A., and Unser, M. On the number of regions of piecewise linear neural networks. Journal of
Hu, X., Chu, L., Pei, J., Liu, W., and Bian, J. Model complexity of deep learning: A survey. Knowledge and Information Systems, 63:2585-2619, 2021.
Computational and Applied Mathematics, 441:115667, 2024. https::: /wwp//wwww........o...... www.nccdiieett.cccc.... com/ sci aeilenee/attio ceeeticcccpppii /0////3377770 /007704273300700111111
Humayun, A. I., Balestriero, R., Balakrishnan, G., and Bara- niuk, R. G. Splinecam: Exact visualization and characteri- zation of deep network geometry and decision boundaries. In Proceedings of the IEEE/CVF Conference on Com- puter Vision and Pattern Recognition, pp. 3789-3798, 2023a.
Grigsby, J. E. and Lindsey, K.
On transversality of bent hyperplane arrangements and the topological expressive- ness of ReLU neural networks. SIAM Journal on Ap- plied Algebra and Geometry, 6(2):216-242, 2022. URL https: / wwri..ogg/ee 1137
Humayun, A. I., Casco-Rodriguez, J., Balestriero, R., and Baraniuk, R. Provable instance specific robust- ness via linear constraints. In The Second Workshop on New Frontiers in Adversarial Machine Learning, 2023b. URL https: http:::s////peevveiew net/ forum? id=aVbGBbM1wg
Hanin, B. and Rolnick, D. How to start training: The effect of initialization and architecture. In Advances in Neural Information Processing Sys- tems, volume 31. Curran Associates, Inc., 2018. URL
https://proocedinggs neurips.
co/paper_ patppee_iieee/ppppr///////eeeee d81 (B81199ccc2220090069922222060000 pdf.
Humayun, A. I., Amara, I., Schumann, C., Farnadi, G., Rostamzadeh, N., and Havaei, M. Understanding the local geometry of generative model manifolds, 2024a. URL htthttss///xxiv// http///axxvvv.o/ abs /a////b//////00 0000700377.
Paper.
Hanin, B. and Rolnick, D. Complexity of linear regions in deep networks. In Proceedings of the 36th Interna- tional Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2596- 2604. PMLR, 2019a, URL URI hwtphttpps.. wtt.:httss//prreeeeddee http///ooeednggg// ngs. mlr. presspressseee v9 2wt.///aaann1ggg html.
Humayun, A. I., Balestriero, R., and Baraniuk, R. Deep net- works always grok and here is why. In diggh-dieessio Learning Dynamics 2024: The Emergence of Structure and Reasoning, 2024b. URL https: pttttss://poee openreviee. net forum? NNNu
Hanin, B. and Rolnick, D. Deep ReLU networks have surprisingly few activation patterns. In Advances in Neural Information Processing Sys- tems, volume 32. Curran Associates, Inc., 2019b. URL
Jacot, A. Implicit bias of large depth networks: a no- tion of rank for nonlinear functions. In The Eleventh International Conference on Learning Representations, 2023a. URL https: /pwpnreviewwweeeeeee//e net net//orum? (d=6iDHce-0B--
cc/paper_ http:e/iiiieeepppeer/////////// (166627225003554433331c////oo663 pdf.
Jacot, A. Bottleneck structure in learned features: Low- dimension vs regularity tradeoff. In Thirty-seventh Conference on Neural Information Processing Systems, 2023b. http:: httpt:s:://ppppeeiiieee net. forum? id=QVpEk2C3Dm.
Hanin, B., Jeong, R., and Rolnick, D. Deep ReLU networks preserve expected length. In International Conference on Learning Representations, 2022. URL https:// openreview openneriew..eet//ooumma id=i wrrriiLBBBDD....
Jacot, A., Gabriel, F., and Hongler, C. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Pro- cessing Systems, volume 31. Curran Associates, Inc.. 2018. URL https::/ neurips. cc hc//paper_flessppppeeeeeee batealss3ee22bba6c6b122222222223 pdf.
Hc, K., Zhang. X., Ren, S., and Sun, J. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE inter- national conference on computer vision, pp. 1026-1034, 2015.
Hinz, P. Using activation histograms to bound the num- ber of affine regions in ReLU feed-forward neural net- works, 2021. URL htttps://arivv. org/ abs/ 2103.17174
Jacot, A., Choi, S. H., and Wen, Y. How DNNs break the curse of dimensionality: Compositionalitty and symmetry learning, 2024. URL ditps:://arxiv org abs/
0607.05664.
Howard, J. Imagenette: A smaller subset of 10 easily classi- fied classes from imagenet. GitHub, March 2019. URL https: http//ggtttuutt com/ fastai/ /iti/mmemmte.......m
Ji, Z. and Telgarsky, M. Directional convergence and align- ment in deep learning. Advances in Neural Information Processing Systems, 33:17176-17186, 2020.
10

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
Jin, H. and Montúfar, G. Implicit bias of gradient de- scent for mean squared error regression with two-layer wide neural networks. Journal of Machine Learning Research, 24(137):1-97, 2023. URL http://jjml org/papers /t//////2//// 0032.0082000000000 html.
Montúfar, G., Pascanu, R., Cho, K., and Bengio, Y. On the number of linear regions of deep neural networks. In Advances in Neural Information Pro- cessing Systems, volume 27. Curran Associates, Inc., 2014. URL cc co//sppee_iiee//ppper//////////1 1 (1922d8660f666691177266666111111 Paper. pdf.
Krizhevsky, A. and Hinton, G. Learning multiple layers of features from tiny images. Master's thesis, Department of Computer Science, University of Toronto, 2009.
Munn, M., Dherin, B., and Gonzalvo, J. The impact of geometric complexity on neural collapse in transfer learn ing, 2024. URL https: /ttx//xxvvv/v/////// org/ 15706.
Li, B., Jin, J., Zhong, H., Hopcroft, J., and Wang. L. Why robust generalization in deep learning is difficult: Perspec- tive of expressive power. Advances in Neural Information Processing Systems, 15:4370-43844 2022.
Papyan, V., Han, X., and Donoho, D. L. Prevalence of neural collapse during the terminal phase of deep learn- ing training. Proceedings of the National Academy of Sciences, 117(40) 2020.
Liu, Z., Kitouni, O., Nolte, N., Michaud, E. J., Tegmark, M., and Williams, M. Towards understanding grokking: An effective theory of representation learning. In Advances in Neural Information Processing Systems, 2022. URL https::///// htttpa://ppenrevieee http///pnnreeeeeeeeeee net/ forum? id=6at 6m.
Pascanu, R., Montúfar, G., and Bengio, Y. On the number of response regions of deep feed forward networks with piece-wise linear activations. In International Conference Learning Representations, 2014. URL https:/ / openreview net http//ooommmmiimeee 4mmot B4Lx.
Lyu, K., Jin, J., Li, Z., Du, S. S., Lee, J. D., and Hu, W. Dichotomy of early and late phase implicit bi- ases can provably induce grokking. In The Twelfth International Conference on Learning Representations, 2024. URL https::////. http//ppeeeveieeeeeeeeeeeeeeeeee hwtp:/iwww.nnntteeeeeeeeeeeeeeee forum? id=XsHqr9dEGH.
Patel, N. and Shwartz-Ziv, R. Learning to compress: Lo- cal rank and information compression in deep neural networks, 2024. URL https: http:///axxvvrroo.e /ba/ 2410. 07687.
Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018. URL https:// openreview.o http://e//frrutee o
Raghu, M., Poole, B., Kleinberg, J., Ganguli, S., and Sohl- Dickstein, On the expressive power of deep neural networks. In Proceedings of the 34th International Con- ference Machine Leurning, volume 70 of Proceedings of Machine Learning Research, pp. 2847-2854. PMLR, 2017. URL httss:/ h http:///poceeeeeeeeeeeeeee mlr. press v v 200/raguu17a.. html.
Maennel, H., Bousquet, O., and Gelly, S. Gradient descent quantizes ReLU network features, 2018. URL https: //arxivv org/ abs /atas//80..30 08367.
Rotskoff, G. and Vanden-Eijnden, E. Trainability and ac- curacy of artificial neural networks: An interacting par- ticle system approach. Communications on Pure and Applied Mathematics, 75(9):1889-1933 2022. URL http: / /xx doi org / 10 1200 wttp://p................22
Malajovich, G. On the expected number of real roots of polynomials and exponential sums. Jour- nal of Complexity, 76:101720, 2023. URL
https: www.ncedieeeeeeeeeeeeeeeeeeeeeee com/ scie httee//ee/rattcceee//////s//////
Sattelberg, B., Cavalieri, R., Kirby, M., Peterson, C., and Beveridge, R. Locally linear attributes of relu neural networks. Frontiers in Artificial Intelligence, 6, 2023. URL https: //wp:/ frontiersin. http///urrnss/sriffffclaaaeeeeee wtt.l////...39///ra...o.o 1255512....
Mei, S., Montanari, A., and Nguyen, P.-M. A mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, 115 (33), 2018 URL http::///// //xx/xxx//////////// doi pnas. 1806579115.
ttt.dddd...ggg/oo///../ org/iorrg10... 1073/
Savarese, P., Evron, Soudry, D., and Srebro, N. How do infinite width bounded norm networks look in function space? In Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Ma- chine Learning Research, pp. 2667-26997 2690. PMLR, 2019. URL https: / //ppoceeeiingss mlr. press v sava resel 9a html.
Meyer, B. Some inequalities for elementary mean values. Mathematics of computation, 42(165):193-11) 1984.
Montúfar, G. Notes on the number of linear regions of deep neural networks. SampTA 2017 Special Session Mathematics of Deep Learning, 2017.

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
Scarvelis, C. and Solomon, J. Nuclear norm regulariza- tion for deep learning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL htttp:://ppenreview net/ forum? id=eddHTvb5ee..
Tseran, H. and Montúfar, G. Expected gradients of max- out networks and consequences to parameter initializa- tion. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 34491-345322 PMIR, 2023, URL https:/ httpLhttttp//poceeeeeeeeee httpp/ppooeee...ee/eeppp mlr. wtt.:em.r....ppr...... press/ v202 2202/tseran23a html.
net//orum?
Serra, T., Tjandraatmadja, C., and Ramalingam, S. Bound- ing and counting linear regions of deep neural networks. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Ma- chine Learning Research, pp. 4558 4566. PMLR, 2018. URL httpstt////.. /ttpp//roeeeggssee/ee mlr, www.ppeess///// serral8b. html.
Turk, G. and Levoy, M. Zippered polygon meshes from range images. Proceedings of the 21 anmual confer- ence on Computer graphics and interactive techniques, 1994. URL https: / /appa.p....// sewante iesmmnnicsccooa.. ozg/CorrusID:3031522
Shevchenko, A., Kungurtsev, V., and Mondelli, M. Mean- field analysis of piecewise linear solutions for wide ReLU networks. Journal of Machine Learning Re- search, 23(130): 55, 2022. URL http:// jmnx. html.
Williams, F., Trager, M., Panozzo, D., Silva, C., Zorin, D., and Bruna, J. Gradient dynamics of shallow univariate ReLU networks. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https::/ ngs. neer cc [iaapper_iLee/ppppe/2////ELLL 1 1151198..eeeT3111100000000000343 pdf.
org/papers/v23/222
Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S., and Srebro, N. The implicit bias of gradient descent on separable data. Journal of Machine Learning Re- search, 19(70)11-57, 2018. URL htRp://::// http:/mlll..rg///. org/ papers/vl 9/1 1 1--18-1188 1888 htmll
Yunis, D., Patel, K. K., Wheeler, S., Savarese, P., Vardi, G., Livescu, K., Maire, M., and Walter, M. R. Approaching deep learning through the spectral dynamics of weights. arXiv preprint arXiv:2408. 1804, 2024a.
Stanczuk, J., Batzolis, G., Deveney, T., and Schönlieb, C.-B. Your diffusion model secretly knows the dimension of the data manifold. arXiv preprint arXiv:2212.126111 2022.
Yunis, D., Patel, K. K., Wheeler, S., Savarese, P. H. P., Vardi, G., Livescu, K., Maire, M., and Walter, M. Grokking, rank minimization and generalization in deep learning. In ICML 2024 Workshop on Mechanistic Interpretability, 2024b. URL https:ttp//t.. httphh:://pppeeeieieeeeee http:///ppeeeeeeeeeeeeeeeeeeeeee forum? id= Y
Súkeník, P., Mondelli, M., and Lampert, C. Neural col-
lapse versus low-rank bias: Is deep neural collapse really optimal? arXiv preprint arXiv:2405. 14468. 2024.
Telgarsky, M. benefits of depth in neural networks. In 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pp. 1517- 1539, Columbia University, New York, New York, USA, 2016. PMLR. URL. /ttopee::///cccddeeeee mlr. html.
Zhang, L., Naitzat, G., and Lim, L.-H. Tropical geometry of deep neural networks. In Proceedings of the 35th In- ternational Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5824- 5832. PMIRR, 2018. URL https: htt.htttss://rreeee proceedings. mir r. press vVC/ wwwzaaaaggg.. him....
Timor, N., Vardi, G., and Shamir, O. Implicit regulariza- tion towards rank minimization in ReLU networks. In Proceedings The 34th International Conference on Al- gorithmic Learning Theory, volume 201 of Proceedings of Machine Learning Research, pp. 1429-1459. PMLR, /pwpceedinggs...c/// mlr press/
Zhu, R., Lin, B., and Tang, H. Bounding the number of linear regions in local area for neural networks with ReLU activations. arXiv preprint urXiv:2007.0688 06803,, 2020.
2023. https: / v201 ittt/tmmmr2aaa html.
Tseran, H. and Montúfar, G. On the expected com- plexity of maxout networks. In Advances in Neu- ral Information Processing Systems, volume 34, pp. 28995-29008. Curran Associates, Inc., 2021. URL fttps///ppae////22///eeeee ce/ cc/paper_files 22cb28880cchaa111111111133266662 pdf.
12

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
A. Main Theoretical Results
A.I. Notation and Setup
Let V be a fully connected network with layers with input dimension no output dimension and ReLU non- non-linearity function ((x)) max (0, 2²). We denote ((v) for "o to be the ReLU function applied element-wise For simplicity, will typically make the assumption that n4 = ny for all hidden layers j [Z]. We denote by hy the post-activations after layer 1. That is,
(x WLh1(2).
Here, each h; Ro m is of the form:
h1(x) ((W Bi),
ho(x)) = v.
We will write the pre-activations at neuron j as 2z) = 1 We can then write the vector of pre-activations at layer as 2 = (21,1; #1,2; 2.,,y). We can then write
h((2) = ((2((x) B:).
We also use o denotes the j-th element of vector 3,. When it is clear, we will write B₂ = 3/. If neurons are indexed by i, such as 2,, we can write 3 = 3z, to denote the bias associated to neuron zc. We write as ((z) to denote the layer index that
neuron 2 appears.
We will typically use 3, to refer the deterministic choice of biases, and reserve b, 3, + 5g refer to the random variable representing the biases plus noise. We denote by 0 [W Wi, .,, 31] the parameters of network. We will write No to denote the network N parameterized by 8. We represent the random variable for parameters as i = [W.... Wi, ,,, When 0 is treated as random variable, we also consider (2(z)) to be a random variable, along with the corresponding quantity z (v), which represents the random variable associated with a neuron.
br].
Now define:
[x(x)= - b- = -], S. = fx E Io"
as the set points where neuron switchs from on to off. Furthermore, define
o = fx E Re V E [4] 3 neuron with ((x) = d((=(x)-b) + #0},
S.=
Then, O is the set of inputs for which there exists an open path from to the output of the function N. Thus, we can read Š₂ as the collection of points in the input space where switches between its linear regions, and this appears in the function computed by N. Notice also the case of the ReLUU activation function, we can re-write O as the following:
O = fx R
VJj E
[1] 3 neuron with 1(2) j 2(x) - b 2 0}.
We will also define By to be:
By = ER"0 1R ,-)(()) discontinuous at x).
which is the set of non-linearities of the function N. We call this the nonlinear locus of M.
ON A NEURON BEING "GOOD"
We will sometimes take path-wise representation of a ReLU network. In this case, we will first write z(0) to denote a neuron in the (th layer. Let = (71 ... 7 denote path in the computation graph of N, where each 7/ indexes a neuron in the äth layer. To clarify notation since the ith neuron in a path will always in ith layer, we will write 2y z We can also note that there is an associated sequence of weights on the edges of that computation graph, which (1-1) (0) More formally, if W is the layer weight matrix, then
:.....77..
we can denote by w "weight connecting 2 2
13

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
Wh
(1)
War We 1.70 Denote by N the set of all paths in the computation graph of A leading from the ith input to the output
node. We can now give a path-wise representation of our neural network N as:
M(x)
Σ
EII (=1
{ol (x)-b,20)) w +NO)).
In this case, neuron in y is open when 24 (z) b- 0. A neuron is good at it is contained in path y leading from the input to the output, where every neuron after is open.
A.2. Illustrative Examples of the Local Complexity
COMPUTING THE LOCAL COMPLEXITY OF SINGLE NEURON
As illustrative example, and gain some intuition for Theorem 2, compute explicitly the local complexity of single neuron. Our model is as follows, where w, B E IR, and denotes the ReLU function. Our parameters are (v, w, B), and our model is
(x(x) = vó(uz= B),
T E R.
Notice first that the breakpoint (non-linearity) of this function is always complexity density function f:
8
Now recall the definition of the local
1 Ze
(xx lim -0
E I n Bx())) R
For our setting here, (w, b) where b is Gaussian with variance o² centered at B. The normalizaiton factor is given by Ze = 2e For now consider fixing e > 0, then notice that:
1 Be(x))) E[l c(a=-extt)
IP b (x - E, + E))
w.
=
=IP(b E (wx we, wer we))
- f (b(b)db
we-wwe
lwlpb(wb)db.
Notice we gain a factor of w in the integrand through change of variables. We illustrate this because this is very similar to how the term Vz(x) shows up in the proof of Theorem 2. In particular, this is one way to see how the co-area formula which we utilize in the main proof is generalization of the typical change of variables formula. We can proceed now to see that:
f(x)
lim c-0 2c m-r
w wwlpo(wbb)d (olpo(urr))
Our local complexity for this single neuron is then given follows, where p is the data distribution:
LC = E [f(x)) = E [[w]]
(hulpo(w))) zup
zmp
Notice this is precisely what we would arrive at by direct application of Theorem 2 to our model.
COMPUTING THE LOCAL COMPLEXITY OF A 2 HIDDEN LAYER NETWORK
To illustrate how these results start to generalize to deeper networks, we show a direct computation of the local complexity for a univariate neural network with one neuron in the first hidden layer and one neuron in the second hidden layer. In
14

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
particular, consider the following network parameterized by 0 (W2, w1, 11).
N(x) - ((22<(w1 - B1) - -22).
We also will write
(x) W1I,,
and
x2(x) w2d(wix B1) (2)(21(1) -1))
Then computing derivatives on N gives that:
(x) = 1 w1
The breakpoints at which N" is not continuous are then given by these indicator functions, so then:
Bx = {x : (x) not continuous at x
b if 22 open at
bi
b2
+ bi
if open at (b2 + w2b1),
U
W1
w1
W1
W22
w
W2
Now let e > O, and suppose that 6 is normal with mean 3 and variance o² and that b2 is normal with mean 32 and variance ²². Then we have that
E b A2
[vo,,(BN, n - +e]]
E [1 c(x-e,0te) ees )2b2
b
+ 1
"2" in clx-c,ate) #1 wo + by )201
[[E[1 bi c(a-e,zte)
=2( wi 1262
by bi
[E by c(x-c,rtt)) 21 lana mt ( )26
by + by
b, 2i my
Now first compute the first term,
E 1l by E(x- c(z-c,z-c)
1 2202
Pb, (b)1 b c(xx-e,tt)) I 22 db my
bj ln
wi (x+te
Pb. (b) 22 2 db
wi(x-e)
(a+c)
|wn 1o,, (wib) b2) db.
(x-c)
So then,
1 20 )202) = El (2+e)
E 11
c(x-exx+))
I
db).
by by "i
(x-o)
From the above we can see that by taking limits we get:
1
lim
E[E[1 c(a- 22 ( 12-
=
[[ lps, (wix) (2))))) db).
Z, by in
by
15

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
Now on the other term calculate:
E 21 E(x-c,xte) 51 22 +2 +
Pbg (b)
bi }2b] db
uy wy E(x c(x-c,x-c)
22 wi my
Pbz (b)
wlng E(x---- -0 "p) #1 Ai(wing "t 1261 db
Pbz (b) DEWI 27 arte 41) 21l eellping + )2 db
us ta
Pb (b) =I( wi wi in 12bb1 db
(a+e- 41)
W Wiwpllbb (w) w2bb1 (1+ م2 db.
From the above equation, we can take limits and see that:
bi )) (=))0,))
- Ze by by wIws + b c(m--eatte) 21( w ly )obb 11 = E [[ w2lpby (ww (/ww((
lim E[
wi
We can now see that (z(()) = lol and |z)(a 1, (#)) w2). Furthermore, W W2(x ر
w2 w2(w1x - b1) 22(x)
on (x) > b. Now notice that 22 is always good at x since it is directly connected to the output layer. So then,
f(x) <=1=>(>))lo (22(x)) + (=)=(())) (21 (x)) I good at
bi
b2
E |1 Pbz (22 good at a)
(=) (z)) good at
bi
by
Which, after taking expectations over x p. is equivalent to the main result in Theorem 2.
A.3. Proof of Theorem 2
The proof of this result will follow an argument that is closely inspired in the work of Hanin Rolnick (2019a). Key to our proof use of the generalized co-area formula, which we review here for completeness.
1. GENERALIZED CO-AREA FORMULA
For with support on Ω C R where u: R R* and is Lipschitz, for I function g, we have that:
I (()))) = f Iu-10 x(=))voll_-
Where:
[[,((x)] det( de((Ju(z)Ju(()))
A.3.2. LEMMA 11
The following lemma bears strong resemblance to Proposition 9 in the work of Hanin & Rolnick (2019a).
Lemma 11. We have that almost surely:
BN U $..
Furthermore, this union is disjoint modulo null set with respect to the Hausdorff no measure.
16

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
Proof. We will first check that By
Up & neuron S2 by checking if the following equation (19) holds:
n S C CBV.
(19)
neuron
Note that this suffices since,
(U= neuron
)
ST Fix x (U2 5.)
We will now write:
2 neurrn
Z {z neurons
(=(x) - b2 0),
Z { neurons |z(x) b2 < 0},
Z { neurons
[z(x) - 6, = 0}.
Notice that on the left hand side of (19) we have finite intersection of open sets which is also open set. As consequence, the map + Z must be locally constant, and there exists some eeeighborrooo around x so that || - yll I iimplies that:
E Zy, = = UZ.
(20)
Now to prove (19) we will leverage the path-wise representation of our neural network N, following the notation in Appendix A.I.
N = Σ
20) 10 + (00).
y/ 1=1
7ET, 1=1
Now we have that, since E (U. neurrn 3.). for every path y that hits E z
ラj E [4] :2421 zz
By extension and by (20) we have that this holds in a neighborhood of a:
Vy E R || ul Sc = 210 E Zny
And for y in neighborhood of r:
L
N(y)
Σ y1 Σ
II
l1 (44 (w) (.) w + +N()))
i=1
TE,; 7527
1=1
But then notice that we also have:
2(x) - by > 0 = 2(U) - by > 0.
So then, for y close x,,
1 (2 10 b.)-
=1 (2(" b.200'
and can write:
L xC22
Nyy)
Σ y1
Σ TET,
11 m +N(().
1=1
From which it is clear that ON/Oy; is independent of Therefore, the function A is a continuous linear function in a neighborhood x and we have shown (19). We will now aim to show:
U neurea
$, BN..
(21)
First note that since our biases are admit a density with respect to the Lebesgue measure, we have that the following holds almost surely (a.s.) for j # i:
(Sa,)) 0 (a.s.).
(22)
17

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
So then (21) would follow almost surely from showing that:
U
S U S2 z'Ø3
C By-
(23)
neuron
Now pick (Uz+z Sz for some fixed neuron Note that in small enough e-neighborhood of have that
y > 2(y) is linear in y. So then follows that in this neighborhood x, S2 U S a hyperplane of co-dimension I. Pick y1 so that 0 < || yn |l S and =(y)) > b2 and y/2 that 0 < ||ar y2ll and = b2. So then it follows that separate two different activation patterns, and by assumption have that is discontinuity point of V (x)... This
proves equation (23).
Notice we have already proved that this union is (a.s.) almost everywhere disjoint with respect to the Hausdorff 7io measure in equation (22). The claim follows.
A.3.3. LEMMA 12
The following lemma is from Hanin & Rolnick (2019a) and is provided here with minor tweaks for convenience.
Lemma 12. Let 2
2n be distinct neurons in the same layer of N. Then for any compact K "o"
| 1ooolnn sE..... [K)] =/e Flll E.I (z)ll Pb (
2, good at x |dx,
where the expectation taken with respect the noise terms d; in the biases.
Proof. Let .,,..., zk be some distinct neurons in N. Let K S Reo. Then notice that:
volng (5 nk) = f Beprenss nK
dvolng-t
[ S nk
lo dvol
I 2, good dvolng-k-
Sapieee nK
First equality clear, in the second equality we use that:
( Szy nk=
nk nk= )
(As, no j=m
(N nk) no. (
$ de OK=
For the third equality, note that for all x E S....... O K, x E O implies that there a path of open neurons that connects from x to the output layer of the neural network. We also have that at x all of the neurons 25 E [k], satisfy 2,(x) - b, So then we just need that there is path from all of these neurons the output later. Now we may re-write:
21
bi
z
b
Sa.. = fx E R 2(x) -b = 0)-
Zk
bx
Then,
volng-k (5 (Snm.e 0 nk) = -
1 2, good dvolng-
18

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
For notational convenience let 33 Now recall that have the Gaussian density function Pb R [0, 1] over the biases. Then we will first take expectations over b, conditioned on the rest of the biases, which we will denote by b:
volno & ($ (Sa.... nk) b
E brupu
(24)
Jec Pb(b)
(x(x))=))( I Vg: good at ( db
(25)
Sec J Pb(z(x)) Ryj: good at d db.
(26)
(2(())=)nk
To apply co-area formula here, we take, borrowing notation from Appendix A.3.1, that:
u (b) = {=(xx) = b} K.K.
So then,
= =|K;
and
g(x) = pb(2()) ly: my good
Notice u is Lipschitz in K and is dominated by an L' function Pb so we have that we may apply the co-area formula and we get:
J J Pv(z(z)) 1y;: o, good dvolno (x) db
= =/x [12(2)] (b((x))) Bays 2y good dx.
=
We can now take expectations with respect to the remaining biases, since by the law total expectation:
Voolng (S n K)) [6] = Elvoolo (5 (S.m.... n nk)
E brups
A.3.4. PROOF OF THEBRRM 2
For the sake of readability, we restate the theorem here,
Theorem 2. Let pb, (x) = oB), be the density for the bias of neuron 24. Then the following holds:
LC Σ E [[
11 is good at z),
(6)
where for each neuron the expectation is taken over and p.
Proof. Recall first the definition of the local complexity density function f:
f(x) = lim
E ( n (.))))
(27)
c-0 Z,
19

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
Now from here, can compute, by using Lemma 11 in the second equality and using Lemma 12 fifth equality:
f(z) = lim
E
IBy (By)),
vvo
c00
Ze 8
volno-1 (
Sz, n (e)(
lim
E
<-0 Ze 8
lim
13
Σ
volng-
(52, n Bx)x
Ze
neuron
E
lim
E vol.o
(5n (5 Bc
c00
Ze
neuren
1
Σ
lim c
El <<x>\ll Pb, (2)(2)) D1 good ae Jd
Ze
(x)
2x]V2 Ph. (2)(z)) 1z good at r-
In the last equality we that the term Eg [+) Pb, (z((x)) 1,, good at =] is continuous in æ, which is consequence of taking expectation over the biases. Taking expectation over p completes the proof.
A.4. Proof of Corollary 3
Corollary In the same setting as Theorem 2, let Cgrad be an upper bound on the norm of the gradient of every
neuron Zy [V2[(=)]| S Cgrad for all x E Q θ = (W1,8 B + S1...., WL, 3 + 81), let Crios = -1_
Viza" and let B
Bij E Eneuron &, 1s, not good ot z] denote the expected number neurons that are not good. Then we have that:
LC Chins
Σ
E (x)12())
neuvon 24 Oprep
1 e nod and En = 20(e20) /12 / such that:
Furthermore, for any 1j > 0 there are constants Bias
V2no
LC
2
bias
Σ
E 0:20D
- E, Cgrad Chias-
(8)
neuron 21
Proof. For the upper bound, it clear that we can write, assuming the conclusion of the prior theorem:
LC = Σ [1)]22)) pb., (=((x)) 2, is gond at
Bizmop
neurnn
Σ
[x)]2( pb., (z))
Gizoup
neuron
Chins
Σ neuron
(x)
We take Cgrad ma [[WWWe- w...-l...Willl....
Willops which is clearly deterministic as it does not depend the biases. To
show the lower bound, we have the following bounds. Assuming the C'rad 2 22, for all neurons 2;, E Ω and Crias 2 Ps and that on average B neurons are not good at x ~ pt
B
E
F
Σ
1s good
xrop
L.z neurom
We use the standard Big Theta notation f() ((g(z)) to signify that there exist Cı, 02, zo such that c1g(x: f(x) cag(x) for
all x > Jg.
20

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
is clear then that we can bound the local complexity as:
LC
E
Σ
[x)]l po., (2(()))
E
[Vz((2)] pb., (21(z))
(28)
xmp,0
neuron
good
Σ
[z)(|l] Pb., (24 - Cgrad Obins
(29)
neuron as mmpp,
2 bias
E
[=(())]] - En - B Cgrad
(30)
neuron
2
Where for the last inequality we proceed as follows: Take neuron with Ps being the density for a Gaussian with variance centered at B. Then:
E [[IV=(=))PM<<(=))
2
E [[]))))) pb(2(x)) =(a)-MEn)
2,6
2.6
IM
inf {oo(r))
E [[][(( 1
Blnn
x.6
inf
(pa(r)]]
E [1]V2(>)]11 - E [IV=(())] |a(a)
0|50
2,0
Notice we can bound the second term here as follows, using Markov's s inequality:
V (2)2))
(
CgraulP (((((x)) - bb 17)
B (g,ū(<<(x)) - -
Cgrad
n72
By B2. (2]]))(())]11)))))))))))))) + E.y 16?
< Cgrad
112
Now since the data distribution has compact support, we have that By, [=x)))))) and E,, [b*] are uniformly bounded. This gives us that,
E -[IV=(()10-=nno.p)))
Ciis
where 0 Coms
2
Now define
V2no
E(n,o, o.N)
Σ
2(1.0,2)=0
blus
172
neuron
Taking a sum over every neuron then gives that
E
Σ
[x)]x())]| Pb.. (z((1)))]
2 31
Σ
Vz((a)]]
- E(n, E(n,o,N),
2mp66
Leeuonn
where E(n, a,N) O
We abbreviate this as & in later results. Using this result in (30) completes the proof. L
A.5. Proof of Theorem
We first recall from before that we define rank, (Jac(z;)) to be the number of singular values of Jac(z;) bigger than e. We define the approximate local rank be:
LR
E z~p
[rank, (J=2(
21

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
Theorem 5, For any O, the local ranks across layers can be bounded in terms of the local complexity as follows:
L Σ
LC
C
grad
LR +
(11)
ng Chios
1=1
Moreover, in the same setting as in Corollary 3,
ELR
LR S
LC+ B Cyrad Cbiax
(12)
Proof. Notice that we have immediately, for an by n matrix A with rank,
22 m' (A))) < ||A| Σ (A) < max (A)2 (n m2) S m0 (A)2 me.
(31)
Notice also that we have that, using that va + va + vb.
[[)((=)|===
Σ
Va(x=) <
Σ
[v)())]
Elayer!
Elayer!
So we may write that:
rank, (Jz((z)) S
Σ
[V>22))l2
nesronn 2, Elayer
Summing this over all layers [L] and taking expectation over the data distribution and 0 gives us:
ELRY
Σ
(z((2))2
2
0
Now recall that from Corollary 3 we have that:
LC 2 Cins Σ
E [+)]+ - B Cgrad Chins-
neuron
0wru
Which is equivalent to:
1 LCC + B- Crins)
E
Σ
(x)
0,z~pp
Leeuron
bias
Which gives us, as desired:
Σ LR < 2c
LC &, + B Cyrad Cbiss)
Recall that Caraa max(e[L]
[WWW
W Willop- Now, for the other inequality we need first the following two sub-claims:
Claim 1:
E [zz((Z)) S C
grad LRi + Eng.
22

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
Proof.
no
|]az(())]
Σ
of
2
o (Jaz(())) rank (ank (J)z)(a)) + em (m (J,
max (Jzz((Z)) rank. (J, + é'n
-
C grad rank, (Jzz((z)) + e
Taking expectations with respect to x ~ and gives us Ez ( < Lg + en, Now notice that Jenson's inequality gives us that (u || on both sides.
(x)]l=)) - Expp: (z) [1) which completes the proof after taking square roots
Claim 2:
[1)z((
E
ampp:
710
z,neuron layer 1 prmpp:0
Proof.
[1)(()))l> 2 [
(J)((())
71u
(x)1())
Vno vE(m)]
V (=)(2))22
V
Vno
[E[m)
Σ
IV (2)122)
no
EE|m)
This completes the proof of the subclaim after taking expectations on both sides.
Now we may prove our bound. Recall that the Local Complexity satisfies:
LC <
Obias
Σ E (z)]l)
neuron
So then we have that, using Claim (2),
LC Σ
E [z)ll
n1 Chias
IE(1] zmp;y
And then by using Claim (1),
LCS Σ
C2 LR
en
no Chius
grad
IE(T.]
Which concludes this proof.
A.6. Proof of Corollary 13
Recall that LR,- Expo (ran)(); Now we can restate the corollary:
23

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
Corollary 13. In the same setting Theorem 5:
LC S C grad
LR,
(32)
Tlg Coias
Proof. The first inequality follows from the first inequality in Theorem 5, well by application of the fact that lim LRi LRR, Then notice that:
LC
Σ
0 LRi
enn
Cgrad
LR,-
no hias
c-0
1=1
A.7. Proof of Proposition 6
Proposition 6. Suppose data distribution admits density function p with support Ω. Consider point E in the interior of S2, with classification margin No(3) "/- For any with B (x) Q let ce inf (, p(x). Then TV S cey implies there are adversarial examples in (T)
Proof. Let TV = -B. (z) and recall our original definition that,
TV 1 (x)))
Then clearly see that have the following bound:
TV S TV.
Now, via the contrapositive argument, suppose that we have x E (T) adversarial example, then,
(o(z)~Not) > >%
From here is clear that TV > y. So in particular,
TV > C.9
This completes the proof.
A.8. Proof of Theorem
Theorem Let gi denote the rest of the network after the Ith layer, so that No = 91 o Φ2 by). Let Ct denote the Lipschitz
constant of gt. Then with the same setting and notations as Theorem
Le
TV
Ct En B B-Crrad Crias S LC.
(13)
MAXI<I<L
Proof. Following the notational conventions in Appendix A.1, recall for any layer S L, that network is:
((x) gi (x)).
(33)
Where gi denotes the rest of the network after layer I. Expanding layer yields:
N(x) (() bt))
(34)
Recall from Appendix A.I that we write, where ny denotes the number of neurons at layer 1.
Whh--100) 21(xx)
iE(mi]
24

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
Computing gradients on (34), can get that:
0g ohy
VaN(x)=
Oh, dx
@ Il 11P
V 22 (x)
(n.g(((())))
iE(nd]
iE(M]
Where denote the element-wise (Hadamard) product. Now let C2 denote the minimal Lipschitz constant for gi in the image of the data support by (S2). Recall also the fact that ||ll|| |||][ ||0]22 Now write that:
E x>p
||| V
(x)
V 2 (x)
((ng(h(()))
pvp
sE(md
kE(m)
E
V (h(())))))) @
1 (19002200)
V V2 (1 (x)
#E|mu
kE(m)
< E x-pp
V hr Nn (1x
|V (z)
3E|m]
S Ci E a>p
V (2)
VE [mel
| Vize 111
< C
E amp
1E(ma
Where in the last inequality we use that Va Va+b< S Va + Vb. Now applying this inequality to each of the 7. total layers and taking the sum, we get that:
L E |V
< Σ
Ci
( (x))
amp
1=1
mmp
iE|ml
< max C
E Fmp
Σ neuron
KEK
Now take expectations over 0, and we can combine this with the bound from before in Corollary 3,
Σ
[2)2a())
<
1
LC + +E, + B Cgrad Chias].
z=p.0
Obins
Lncuron
Which then gives us:
L
1
E [IV < LC En + B Candd Crias]
SaXI CJ
p
Obias
as desired.
25

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
A.9. Proof of Proposition 8
The representation cost is defined as Ro(f) inf ((( 10 We re-state our main proposition:
Proposition 8. In the same setting as Theorem 2, where ny is the maximum hidden layer dimension,
LC S ny + 1.' R.NO)*.
(14)
Cbiar
Proof. We begin by computing that:
[zi(z) WiD,Wi-IDL-I- D,W1-
With W; denoting the 1-th layer weight matrix and Dj being a diagonal matrix of 0 and denoting the ReLU activation pattern the /-th th layer, when evaluated at Now using result from Soudry et al. (2018) and Jacot (2023a) get that, for p Y Cll |Ip denotes the Lp Schatten matrix norm):
Jzz (3) 1 L (IW; + I Dj | ... (1
(35)
$ T (IWt || 1| (/
(36)
$ 1018.
(37)
Now we recall the equivalence of the L, Schatten matrix norm to the Frobenius norm. Notice this is the same as the equivalence suffices to do this for the equivalent vectors of singular values for the respective norms. For any n x n matrices A, B:
| S Blp
Where C = - = -
Then we also have that:
n |AI| S BlB = (n + (()l)) $ <BB
Applying this to (37) gives us:
1 [2 - 1010 = ||)z(())] S n 1- 1 ( 01011
(n,
Since this holds for all parameterizations of the function learned by N. we can get that:
[| S ni 1-L L R(N)
Apply this, summing over all layers to get:
Σ [Jz(()))l S sm 1 -' R(N
Now combine this bound with (A.5) and we get:
1-4 " L R
LC n,
Cbias
26

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
A.10. Proof of Proposition 14
Canonical results on training neural networks in the lazy/kemnel regime show that the weights do not move far from their initialization by the end of training (Chizat et al., 2019). The following proposition shows that if this holds, then the local complexity will also not change much from the beginning to the end of training.
Proposition 14. Consider a 2-layer MLP of the Ng(x) = =² o(Wr - 3) with parameters 8, = (3(0), W e(0) at initialization and 0e = (3(6), W(0, olt) at time t. Suppose also that | 0.l12 I c. Denote by (C( the local complexity of parameters Or. If v + O, then, we have that there exists a constant C independent of such that,
LC((0)) - LC((0)) S Ce
Proof. First note that in the setting of this 2-layer network we can apply Theorem and see that the local complexity is,
(1
(0)
LC =
E
1
lle
V
Where we denote that wk is the k-th row of W. Then notice that,
(1 (9) 2n
1
VTTa
/2TO
So then, we can compute that
LC((0) - LC(O.)I
Ciw (0) (0)
(4)
(0) 20
E
(0)
lle
E
1w
lle
22T
amop
2
amup
k=1
R2
| || - -1120
(0)
(*)
/2ma
k=
f1
2
k=1
T1
2
A.11. Proof of Proposition 9
We first recall a theorem courtesy of Timor et al. (2023):
Theorem 15 (Timor et al., 2023). Let {(E,, y:) E R {-1,1} be binary classification dataset, and assume that there is E [n] with ||ar|]] < 1. Assume that there is fully-connected neural network N of width m 2 2 and depth k 2 2, such that for all i E [n] we have (x,(),;) 2 1, and the weight matrices W1...., We of N satisfy [[.]]r S B for some B > 0. Let Na be fully-connected neural network of width m' 2 m and depth k' > k parameterized by Let 6 = [W"....,W' Wil be global optimum of the above optimization problem (15). Namely, 8" parameterizes a minimum-norm mimimmn-noomfflllyccmmmeece fully-connectdd network of width ny and depth L. that labels the dataset correctly with margin 1. Then, we
have
W
1
V2 B
(38)
T,
W
V2
VL+1
==1
Equivalently, we have the following upper bound on the harmonic mean of the ratios
W W
L
(
B
L+1
5V2
(39)
I [|=
V2
L
===1
[ 1op
27

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
We will leverage the result in this theorem, particularly the bound on the harmonic mean of the ratios following proposition.
to prove the W
W.
Proposition 9. Let {( wi]l=1 C x {-1,1} be a binary classification dataset, and assume that there is i E [n] with | < 1. Assume that there a fully--onnected neural network N of width m 2 2 and depth 2 2, such that for all i E [n] we have (xx) 2 1, and the weight matrices W....., WR of N satisfy [[il|r Σ B for some B > be a fillly-connectdd neural network of width m' Z and depth k' parameterized by 0. Let 0" [ ..... Wi. be global optimum of the above optimization problem (15). Then, assuming the same setting Theorem we have the following bound on the local complexity:
No
710
L max Wap
Obias n2
L
-
LC
-7
(16)
4
B
L
L+1 L
I
V2.
(17)
V2
(V
where,
|| F
W
IW: Top
Proof. Following an intermediate result from Section A.9 gives us that, for K = ny 27
L 4;
n4p
LC S
Σ
[Wille)
= CCoas
no
LC)+ s Σ
||
||
Crias
K
iE[k]
Then we can see that we also would have:
1 LC)+ -
Σ
W |
L LmaateeL] [[ 1lop
Obins K
L
llop
SE[
Now via the bound controlling the difference between the arithmetic mean and the harmonic mean (Meyer, 1984), get that:
W
(N
ammax
V a/minn
|
llop
ΣL
[IW:
.E[L]
[W:
Where,
||
max O'ax
lE]K]
[ lap
and
| F [|;""] llop
Otmin
min xE(k)
But notice that, by Timor et al. (2023, Lemma 15), we have that:
|| ||
So then,
[WT (V (IIw?lle
(
(Vomaa VO
llop
||
=
and we get consequence of the bound controlling the Harmonic Mean from the prior theorem:
$
1
W ( no
LCJ+ s /2.
B
L+1
L maxielu
Chias K
22
L
28

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
A.12. Derivation of Corollary 10 (informal)
Corollary 10. [Informal] Suppose that [10(t)]l2 θ ((log 2) holds. Then, in the "rich" phase of training the local complexity is bounded:
710
LC S Oloog t)
(18)
1-h.
Suppose that []0(t)ll2 @(log 11))). Then recall by Proposition we have that:
740
LC S nl 1- - 4-+ROy R(N)
Chias
n4 1= L -- (10(t(1
= =n, 1- - 1'-000 31/2/2
ny +
r.- 0
B. More Information on Empirical Studies
B.1. On Estimation of the Local Complexity in Figure
The network in question is trained to exactly represent 2D grayscale image of the Stanford Bunny (Turk & Levoy, 1994), using the Mean Squared Error loss function and Adam optimizer with learning rate le 4. The left hand figure is an exact visualizations of the linear regions in this network computed using the implementation of Humayun et al. (2023a).
To understand how we compute the local complexity, let us first recall the key result from Theorem 2, from which we then use the trivial upper bound on the indicator function:
LC= Σ E [[V((ll (s) (zi(1)) 11,; good at a
Σ
E [ Ph, (z)(1))
(40)
2.6
neuron
neuron
Using this also get the estimate of the local complexity density function f:
f(x) S Σ
(41)
neurOn 22
We can now empirically estimate the right hand side of (41) by using computing finite samples of perturbations to the biases and taking the empirical mean. particular we use o 0.05 for Figure 1. We provide here an ablation on the choice in Figure 4. In Figure 5 we provide an example illustrating the effect of adding noise not only to the biases but also the weights.
Several of our bounds, in particular those derived from Corollary 3, rely removing the term Ps from the summand when computing the Local Complexity. We demonstrate in Figure 6, the effect of estimating the local complexity density function as:
f(x) = Σ (x)
(42)
zneuron
We show in Figure 6 what this density function looks like, and that it still bears strong qualitative resemblance to the original structure of linear regions from Figure 1.
29

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
Figure 4. Here we show the effects of estimating the local complexity density function f with varying levels of a. We show a = 0.025 (Left), 0.05 (Middle), and σ 0.1 (Right).
Figure Here we plot the local complexity density function comparing the effects of adding noise to just the biases (Left) vs adding the same amount of noise to both the biases and the weights (Right). Here we used a 0.05. As we see, the effects are qualitatively similar both cases.
Figure Effect of plotting f as defined in (42). The setup is otherwise the same that in Figure and Figure 4.
30

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
B.2. Details Figure 2
We create synthetic dataset by sampling from an isotropic Gaussian X, and a correlated isotropic Gaussian Y. The cross coss-covari matrix between X and Y is randomly generated. In these examples output dimension of 2. We train with the Adam optimizer with learning rate le 4. We show that this effect is the same across several training runs, each with a different cross-covariance matrix in Figure 7.
input dimension of 100 and
37.5
Complesity
35.0
32.5
60
30.0
Legend
Layer
Local Rank Layer
22.5
Local Rank Layer
Local Rank
20.0
10a
10a
10a
10a
104
10a
100
10a
102
10a
10*
10a
Reration
Reration
Figure 7. Here we run the same experiment as in Figure 2, 6 times, each with a different cross-covariance matrix. We demonstrate that this effect is consistent by plotting standard deviation error bars each collected data point. We find Pearson's 's correlation coefficient 0.852 between the local complexity and the local rank at layer 2, and Pcarson's 's correlation cocfficient of 0.957 and 0.985 at layers 3 4 respectfully.
B.3. More Information on Estimation in Figure 3
Here compute the local complexity in Section B. I by computing the gradients at each neuron Vz(x)) and computing mean over data points in the test dataset. Similarly, we estimate the total variation of our network by computing the mean of [z)][ at points in the test dataset.
note that we see most clearly the relationship between the total variation and the local complexity when training with a high initialization scale. Figure we initialize our weights with a standard deviation twice that of the typical He initialization scheme (He al., 2015). This approach is commonly employed in the literature when investigating grokking and the terminal phase of training (Fan al., 2024; Lyu al., 2024). Nevertheless, in Figure 8 perform ablation study on the initialization scale. In both cases we can see an increase in the adversarial accuracy late in training corresponding to drop in the local complexity, but the correlation between the local complexity and the total variation seems to break down at lower initialization scales. So, our theoretical works appear to not fully describe the dynamics in certain cases.
B.4. Remarks on Tightness of the Bounds
We observe in Figure 8 that the total variation occasionally fails to decrease alongside the local complexity, which raises questions about the tightness of the bound in Theorem 7. While the exact relationship between total variation and local complexity complex, these empirical findings do not necessarily invalidate the bound. The bound as stated depends on the term max SIST. C₁, where Ct represents the Lipschitz constant gi (the rest of the network following 1-th layer). To empirically verify this bound's validity, we need compute or estimate this term. We propose the following crude approach for estimating the Lipschitz constant term:
max C < max ||, ... Wellop- 1
1315L
The above inequality is tight there is a linear regions for which all neurons are active. Using this as an estimate for maxigist Ct, we can then compute an empirical estimate for the term:
31

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
90
Accuracy
Test Accuracy
80
Accuracy
70
Total Vaitation
60
Local Complesity
Accurory
0.6
50
40
0.4
30
0.2
20
10-
0.0
10a
10a
10'
10a
10a
10
10a
10
10'
10
10a
10*
10'
20"
Itoration
Itoration
1.0
Tain Accuracy
1400
Accuracy
Adverserial Accuraty
1200
lotal Veriation
0.6
800
600
0.4
400
200
0.0
10f
107
102
10a
10a
100
100
10P
101
107
102
10*
107
10F
Iteration
Iteration
Figure 8. Here demonstrate the results of training MLP subset of the MNIST dataset with the standard He initialization (Top) and 3r the regular He initialization. This model has the same architecture as that in Figure 3.
Le TV
Lc maai WWW ... Wo
TV-
(43)
maxIcISI CI
We visualize the relationship between this quantity and the Local Complexity in Figure 9. When comparing Equation (43) with the local complexity, we find that the observed increases in total variation during late-stage training can be attributable to larger Lipschitz constants C₁ rather than an inherent looseness the bound. This observation suggests further intriguing and unexpected behavior during the terminal phase of training that merits further investigation.
ON THE NUMBER OF NEURONS WHICH ARE NoT GoOD
Many of lower bounds also involve factor B, which define to be the expected number of neurons which good when evaluated over the data distribution. In particular, will measure,
Σ
B
E znpp
1. not good a
Lneuron
Z;
For fully connected network, a neuron would be not good at x only there is layer in the network for which every neuron is off when evaluated at z. This means that this quantity would be quite small for networks of reasonable width, as we can see Figure 10.
32

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
140
Total Varistion
Mean
Local Complexity
95% Confidence interval
120
Bound
Local Complexity and Lower Dound
Total Total Varistion
Complexity
60
1
10a
101
102
10a
10
102
30"
10a
10A
10a
10a
10*
10a
10c
Iteration
iter
Figure 9. Here train network MNIST with the He initialization scheme, 4 hidden layers each with dimension 200. We see spike the Total Variation late trainig (dotted line). left, can also see that the lower bound as estimated via equation (43) still decreases along with the local complexity in the terminal phase of training. On the right, show that this behavior reproducible by TV Le
running the same experiment times and computing confidence interval the term LC max Ci estimate the constant terms, as we find that this choice of y maximizes the tightness the lower bound from 7.
We use a v a
5
Width Width 200
Expected Number Neurons
0
10
iter
Figure Here, we plot the empirically observed value the number neurons which are not good, B, for an MLP during training on MNIST, Both networks have depth 4, and we see that for the wider network B = 0 at all timesteps.
33

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
C. Additional Figures
C.1. Clusters Weight Vectors After Drop Local Complexity
Here, in Figure 11, we demonstrate the emergence of structure in UMAP plots weight vectors late in training. This connects the concept that, in the kernel regime, networks data points without substantially altering the structure of their linear regions. However, after transitioning the rich training regime, observe intricate clustering in the weight vectors, providing evidence of feature learning.
1.0
54
Test Accuracy
46
0.8
Adversartal
60
Complexity
Total Variation
42
Accuracy
0.6
50
36
30
0.4
40
0.2
12
100
10a
10P
10a
10a
102
10a
10a
10'
102
10a
10"
10a
10F
Iteration
Iteration
UMAP of Neurons Before Drop in Local Complexity
UMMP of Neurons Mae Drop Local Complexity
Figure 11. Here we demonstrate qualitative changes in the parameters before and after the drop in local complexity. We consider here a one hidden layer MI.P trained on a subset 1000 images MNIST dataset. The hidden layer has 5000 neurons. We plot low- dimensioonn UMAP visualizations of the weight vectors associated each neuron in the hidden layer at 494 iterations (marked by dashed line) and at 1, 000, 000 iterations.
34

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
C.2. Local Rank MNIST
In Figure 12 we demonstrate the dynamics Local Rank when training with subset of 1000 images of the MNIST dataset. We note that the drop in the local rank approximately corresponds to the second drop in the local complexity, well the increase in the adversarial robustness of the network.
3.0
Tran AccurEty
Aesuracy
140
120
100
uocll Hamil Loysr
Local Rant Layer
Local Ro Layer
107
benstcn
107
100
10
10"
16'
107
10' teration
20'
105
101
10" teo0d3
10*
105
Figure 12. Local Rank Analysis the MNIST Dataset. In this figure train MLP MNIST with 3 hidden layers of 200 neurons each. We use a regular 1x initialization scale.
C.3. Local Complexity and Weight Decay
In Figure 13 we demonstrate a correlation between the weight decay parameter over several training runs, and the drop in local complexity late in training, which relates our results in Proposition 10.
4.5
4.0
3.5
Local Complexity
Local Complexity
3.0
Weight Decay
100
2.5
0.15
10a
10a
10a
10a
10
10a
Iteration
log
Figure 13, Here we demonstrate a correlation between the weight decay parameter and the drop in local complexity late in training. On carlier for higher values of the weight decay parameter. On the right, we plot the bounding
the left, note that this drop appears quantity from (18) on the a-axis, and the local complexity at the end training on the y-axis. We also plot lincar regression, and observe R² 0.6972. In these experiments, consider shallow 2 layer MLP, with hidden-layer dimension of 1000. This network trained on a subset of MNIST with the Adam optimizer and learning rate le 4.
35

---

On the Local Complexity of Linear Regions in Deep ReLU Networks
C.4. Local Complexity Other Datasets
We illustrate in Figure 14 that the primary empirical observation of this paper, that local complexity decreases and robustness to adversarial examples improves late in training, extends beyond our initial setting. Specifically, show similar trends for the CIFAR-10 10 (Krizhevsky & Hinton, 2009) and Imagenette (Howard, 2019) datasets. However, these additional results are limited in scope due to the relatively poor performance of MLPs compared to CNNs on these tasks, coupled with the challenges posed by the higher dimensionality of the input, which makes estimating local complexity computationally demanding and memory memory-intensive. intensivve
48
42
36
56-
Local Comglexity
30
24
40
18
12
10a
10a
102
10a
10a
10a
10"
10a
10a
10a
10a
Iteration
Iteration
Accuracy
Accuracy
Test Accuracy
0.5
Test Accuracy
Adversarial Accuracy
Adversarial Accuracy
0.8
0.4
0.6
Accuracy
0.3
0.0
10a
10a
10a
10a
10a
10a
10a
10a
10a
10a
10*
Iteration
(a) Training Dynamics of Local Complexity compared accuracy and adversarial performance CIFAR-10.
(b) Training Dynamics of Local Complexity compared accuracy and adversarial performance on Imagenette.
Figure 14. Here, we can see some evidence that drop in the local complexity and an increase in the adversarial robustness persists in other datasets.
36


Reviews:
[{"review_id": "zEPnIT44BH", "reviewer": "Reviewer_EDjL", "summary": "The paper studies ReLU networks and proposes local complexity that estimates the average density of gradient discontinuities under an input distribution and a parameter set. Three theorems are provided. First, it is shown that local complexity can be estimated by gradients at each neuron. Second, it is established that the local rank can be bounded in terms of local complexity where the local rank is defined as the rank of the average rank of the Jacobian. Third, local complexity can be used to bound total variation of the ReLU network if the Lipschitz constant is given under several assumptions. Since network with a lower total variation can have adversarial robustness, a lower local complexity may be an indicator of robustness. Finally, it is shown that the local complexity can be bounded by the representational cost that can be connected to weight decay, implying that local complexity might be minimized during training.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their thoughtful and detailed comments. We have addressed minor errata for the camera-ready version. \n\n> It is not clear to the reader why the local rank is deﬁned through the Jacobian. What is its relation to the rank of the weight matrix? ... Would this directly connect to the robustness mentioned in Section 5?\n\nThe rank of the Jacobian at a point quantifies the local dimension of the feature manifold, that is, the number of directions in which the input may be locally transformed. For a ReLU network, the Jacobian is given by \n$\nJf(x) = W_1 D_1 W_2 D_2 \\cdots W_L D_L,\n$\nwhere each $D_i$ is a diagonal matrix with entries in $\\{0,1\\}$ indicating which neurons are active. This implies that the rank of the Jacobian is bounded above by the smallest rank among the weight matrices. One might expect that networks mapping data to a low-dimensional manifold could exhibit simpler, and potentially more robust, decision boundaries.\n\n> Some comments on how to estimate the bound would be useful to enhance the clarity of the theorem.\n\nWe estimate the bound on local complexity by considering the operator norm of the weight matrices. In particular, we compute an upper bound via \n$\n\\max_l {|| W_l \\cdots W_1 | |}\n$\nwhich is tractable to compute and provides a useful approximation. Additional details are provided in Appendix Section $B.4$. We show also that the term including $C_\\text{grad}$ is typically $0$.\n\n> Are there more general bounds that describe the local complexity in terms of depth?\n\nWe also derive a bound that explicitly incorporates network depth via the notion of representation cost (see Proposition 8) which is valid for any parameters. We can substitute the representation cost for the $L^2$ norm of the weights as well.\n\n> ... it is not known how to use it to design a more robust model or motivate architecture design. \n\nWhile our current results do not provide a recipe for designing inherently more robust models, our findings suggest that controlling the rank of the weight matrices could be a promising direction for enhancing robustness and guiding architectural choices. We also demonstrate a connection between weight decay and local complexity, which may guide future work.\n\n> Could you highlight the difference between the definition of local complexity and the one in (Hanin & Rolnick, 2019b)?\n\nHanin & Rolnick investigate how the depth and number of neurons affect the expected number of linear regions for a generic distribution of parameters. In contrast, in our definitions and results we are concerned with how the linear regions vary for a specific choice of parameters, and we are concerned with the distribution of linear regions over the data distribution, which are aspects that are not discussed in the work of Hanin & Rolnick. We also explore properties like Local Rank and Total Variation, which are not addressed in their work.\n\n> How does $\\sigma$ affect the local complexity in Theorem 2? This parameter seems to be hidden by $\\rho_{b_i}$.\n\nThe choice of $\\sigma$ will affect the local complexity through the probability density function of the normal distribution, $\\rho_{b_i}$, as well as through the magnitude of noise that is added to the biases, as we take expectation over this in the computation of LC. We show in Figure 4 the effect of increasing this.\n\n> Are the constants in Theorem 5 and 7 the same ones deﬁned in Corollary 3?\n\nYes, these are the same constants.\n\n> If the local complexity is known, would it be possible to shed light on the hardness of reverse engineering?\n\nThis is an interesting point for further work. To our knowledge, our current framework does not directly address this, though one would expect that a low local complexity makes this easier.\n\n> If the weight noise is also used, would this change the theoretical results? For example, would it be possible to still be able to estimate the total variation?\n\nIt is possible to extend the definitions to include perturbations of the weights though this may introduce changes in the direction of the boundaries, which are naturally more complicated. In Figure 5 in the appendix, we illustrate how adding perturbations to the weight matrices does not qualitatively change our measure of the local complexity. The computation of the total variation would also be similar.\n\n> For a given ReLU network, we can create a corresponding ResNet by adding skip connections. Would this ResNet have lower local complexity?\n\nConsider a simple one-layer example where\n$\nf_{\\text{res}}(x) = f_\\theta(x) + x.\n$\nIts Jacobian is\n$\nJf_{\\text{res}}(x) = Jf_\\theta(x) + I.\n$\nHere, the discontinuities in the Jacobian $Jf_{\\text{res}}(x)$ occur only where $Jf_\\theta(x)$ is discontinuous. So, the local complexity of the ResNet does not differ markedly from that of the corresponding plain ReLU network.\n\nPlease let us know if further clarification is needed.", "claims_and_evidence": "The claims in the papers are supported by proof.", "methods_and_evaluation_criteria": "This is a theoretical paper providing insights to ReLU networks. Several results are provided to establish the notion of local complexity and how it can be used to understand robustness.", "theoretical_claims": "The reviewer did not verify the correctness of proof.", "experimental_designs_or_analyses": "The notion of local complexity is a natural way to study the density of linear regions in a ReLU network. The analysis seems fairly reasonable.", "relation_to_broader_scientific_literature": "The results shed light on ReLU networks and the findings are of interest to the broader community of machine learning.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Strengths:\n1. The notion of linear regions in ReLU network is an important concept and local complexity provides a way to estimate the density of the linear regions.\n2. Links to local rank and total variations seem to be interesting and seem to have some implications on the training dynamics of ReLU networks.\n\nWeaknesses:\n1. It is not clear to the reader why the local rank is defined through the Jacobian. What is its relation to the rank of the weight matrix? In addition, what are the implications of having lower ranks? Would this directly connected to robustness mentioned in Section 5?\n2. It seems the bound in Theorem 7 is hard to compute as it depends on the maximum Lipschitz constant across different layers of the network. Does it imply that one needs to estimate all Lipschitz constants from all of the subnetworks to estimate the total variations? How does the maximum Lipschitz constant relate to the maximum norm of the gradient $C_{grad}$? Some comments on how to estimate the bound would be useful to enhance the clarity of the theorem.\n3. Proposition 9 illustrates the relation between local complexity and depth. However, it is only valid at the global optimum of the problem in (15) which minimizes the representational cost. Are there more general bounds that describe the local complexity in terms of depth? What was the main difficulty in the analysis? \n4. Although the local complexity can be connected to total variation and thus develop some understandings of robustness, it is not known how to use it to design a more robust model or motivate architecture design.", "other_comments_or_suggestions": "1. Line 199: Is $\\sigma$ the standard deviation? Should it be $N(0,\\sigma^2I)$ In Theorem 2, should it be $N(\\beta_i,\\sigma^2)$? \n2. Line 290: to estimate the learn a map between", "questions_for_authors": "1. Could you highlight the difference between the definition of local complexity and the one in (Hanin & Rolnick, 2019b)?\n2. How does $\\sigma$ affect the local complexity in Theorem 2? This parameter seems to be hidden by $\\rho_{b_i}$.\n3. Are the constants in Theorem 5 and 7 the same ones defined in Corollary 3?\n4. Reverse engineering a ReLU network may require the knowledge of all of the discontinuities in Eq. (2). If the local complexity is known, would it be possible to shed light on the hardness of reverse engineering?\n5. If the weight noise is also used, would this change the theoretical results? For example, would it be possible to still be able to estimate the total variation?\n6. For a given ReLU network, we can create a corresponding ResNet by adding skip connections. Would this ResNet have lower local complexity?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RjeHHvP6nI", "reviewer": "Reviewer_tqhc", "summary": "The authors introduce two novel metrics, Local Complexity (LC) and Local Rank (LR), to analyze the structure of linear regions in ReLU networks. These metrics provide insights into the relationship between network complexity, feature representations, adversarial robustness, and representation cost. Theoretical bounds are established for LC and LR, and empirical experiments validate these findings, offering a new framework for studying the geometric properties of neural networks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their thoughtful and detailed comments which have helped us improve our paper, and their positive review. We have addressed your minor errata for the camera-ready version. \n\n> The method for estimating LC via bias perturbations could be better motivated, particularly regarding sensitivity to noise variance.\n\nResponse: Our theory centers around taking the expectation of a random level set of a function. Our theoretical framework builds on the analysis of the threshold at which a neuron transitions from inactive to active. The biases directly control the level at which a ReLU transitions from being inactive to being active and that is why we focus on bias perturbations. This is illustrated in the proof of Lemma 12. Perturbations of the biases control the level sets directly which makes the resulting formulas more tractable. A more in depth discussion can be found in section 3.1.\n\n> The paper would benefit from a discussion of how LC compares to standard complexity metrics like VC dimension.\n\nResponse: We agree that relating LC to traditional complexity measures such as VC dimension is an intriguing direction. However, establishing a quantitative connection between LC, which captures the local behavior and density of linear regions in the network, and global complexity measures of a family of functions such as the VC dimension is challenging. We believe that this presents an interesting avenue for future work, and we plan to include a mention to this in the discussion section for the camera-ready version.\n\n> It is known that constraining the Lipschitz constant $K$ of a neural network enhances its robustness. Following your results on robustness, do you think LC and $K$ could be correlated, and if so, in what ways?\n\nResponse: Our bounds relating the total variation (TV) of the network over the input space and the local complexity (LC) can shed some light on the relationship between the Lipschitz constant $K$ and LC. For instance, a simple bound shows that \n$\nTV = \\mathbb E_x[ || \\nabla f(x) || ] \\leq K.\n$\nThis suggests that controlling the Lipschitz constant may indirectly influence the local complexity, thereby impacting robustness.\n\nPlease let us know if any aspects of our work would benefit from further clarification.", "claims_and_evidence": "All theorems/propositions/corollaries are supported with convincing proofs detailed in the supplementary materials. Some of them are summarized below :\n\nClaim : lower Local Complexity corresponds to learned low-dimensional representations.\nEvidence : theoretical bound (Theorem 5, proved in A.5) + empirical study (Figure 2).\n\nClaim : Local Complexity is an upper bound on total variation and relates to adversarial robustness.\nEvidence : theoretical bound (Theorem 7, proved in A.8) + empirical study (Figure 3).\n\nClaim : Training dynamics drive networks toward lower local complexity solutions.\nEvidence : theoretical bounds (Proposition 9, proved in A.11, Corollary 10) + empirical study (Figure 13).", "methods_and_evaluation_criteria": "Yes : \n- The metrics LC and LR are mathematically well-defined.\n- the Stanford Bunny experiment is a good toy problem for illustrating linear regions in an interpretable 2D setting.\n- MNIST is appropriate for evaluating adversarial robustness in real-word settings.\n\nHowever, the choice of noise variance σ affects LC estimation. A sensitivity analysis on different noise levels would improve confidence in the robustness of results. For example, what happen in Figure 5. for other values of σ? \nDoes the effects remains qualitatively the same in the two setups? It is also unclear how this value is chosen : why is the middle figure in figure 4. better than its left or right counterpart ?", "theoretical_claims": "The proofs seems sound and well-structured, but I didn’t checked closely their validity.", "experimental_designs_or_analyses": "The experiments seems valid, although it would be great to give access to a github repository to reproduce the results.", "relation_to_broader_scientific_literature": "The study builds upon prior work on the expressivity and complexity of ReLU networks (Montufar et al., 2014, Pascanu et al., 2014, Serra et al., 2018…). While these previous papers were focused on counting/bounding the number of linear regions, this work is the first to introduce a notion of density of linear regions over the input space. \n\nThe discussion on grokking aligns with recent work on the training dynamics of these networks and the link with linear regions (Humayun et al., 2024, Liu et al., 2022). The paper empirically confirms findings from Humayun et al., 2024 that grokking corresponds to a reduction in the number of linear regions. The link between weight decay and reduced LC aligns with prior work on representation cost (Jacot, 2023).\n\nPrior works (Croce et al., 2019) showed that larger linear regions correlate with increased robustness. This paper formalizes that idea by proving a theoretical upper bound between local complexity and total variation, showing that networks with lower LC are more robust.", "essential_references_not_discussed": "Not to my knowledge.", "other_strengths_and_weaknesses": "Strengths :\n- The paper is well-written, clear about his assumptions, every claim is proved.\n- The contribution seems to be relevant to the field and so could impact future research.\n- The idea of using the density of linear regions instead of their number is original.\n\nWeaknesses :\n\n- The method for estimating LC via bias perturbations could be better motivated, particularly regarding sensitivity to noise variance.\n- The paper would benefit from a discussion of how LC compares to standard complexity metrics like VC dimension.", "other_comments_or_suggestions": "List of typos :\n- line 78 : “the a network” → “of the network”\n- line 155 : “is bears” → “bears”\n- line 409 : “properities” → “properties”\n- line 1790 : “intialization” → “initialization”", "questions_for_authors": "It is known that constraining the Lipschitz constant K of a neural network enhances its robustness. Following your results on robustness, do you think LC and K could be correlated, and if so, in what ways?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZBMewMv7eG", "reviewer": "Reviewer_7pCh", "summary": "This paper suggests a new measure for analyzing feedforward neural networks based on the density of points where the model’s gradient is discontinuous (“kinks”) near training samples, which they term Local Complexity (LC). It builds opton prior findings that neural networks tend to form fewer linear regions, especially in later training stages, which relates to the generalization question in over-parameterized networks. To establish their measure’s relevance, the authors connect it to: (a) the dimensions of the features manifold, as previous results suggest that networks that generalize better tend to form low-dimensional representations; (b) robustness to gradient-based adversarial attacks, and show that LC is at least as indicative than the TV of the model over the data distribution; and (c), the “representation cost”, which is the smallest possible norm of the model’s parameters needed to exactly compute some function. These connections are proved theoretically as upper and lower bounds for the LC, and empirically for toy examples.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their thoughtful and detailed comments which have helped us improve our paper. We have addressed your thorough list of minor errata for the camera-ready version. Below we address each major point raised.\n\n> The LC term was previously introduced in a paper ... This raises questions about the novelty of the concept, even though the purposes of the two papers appear to be different. \n\nResponse: We appreciate this point and wish to clarify the  novelty of our contribution. The referenced prior work introduced the LC term predominantly in an empirical context, highlighting an intriguing phenomenon without providing any theoretical analysis or claims. In contrast, our work explicitly develops a theoretical foundation for the Local Complexity. Specifically, we derive rigorous theoretical explanations and demonstrate connections between LC and other established theoretical aspects of deep learning. Therefore, while the previous paper contributed an interesting empirical observation, our paper significantly extends the theory of Local Complexity in neural networks.\n\n> ... It's not clear that it currently provides a useful novel perspective \n\nResponse: We respectfully emphasize that our theoretical framework does indeed provide a novel and valuable perspective, as it unifies different areas of study in deep learning theory under the common theme of the local complexity. We are able to derive quantitative insights into important phenomena, including adversarial robustness, grokking, and neural collapse. To the best of our knowledge, this has not been explored or established in previous literature.\n\n> It is very lacking in results / ... needs to be tested on more complex settings than MNIST.\n\nResponse: We acknowledge this feedback and note that readers seeking extensive empirical results may find Humayun et al. particularly relevant. Our paper, however, focuses primarily on the rigorous development of a theoretical framework that lays a significant foundation for understanding and analyzing related empirical phenomena. We provided experiments to better illustrate and motivate our theoretical contributions, which is the focus of our paper. Nevertheless, we will be glad to add more extensive experiments on the local complexity on CIFAR-10, CIFAR-100 and Imagenette for the camera-ready version.  \n\n> There is not much discussion on the tightness of the bounds. ... raising questions about the tightness of the theoretical bound and whether additional factors influence TV's behavior in late-stage training.\n\nResponse: We thank the reviewer for raising this important point. For an extensive on the tightness of our theoretical bounds and the conditions under which they hold, we direct the reviewer to Appendix B.4. In that appendix, we clarify the relationship between total variation (TV) and local complexity (LC), particularly addressing situations where TV increases while LC does not. We demonstrate that such discrepancies are driven by increases in the Lipschitz constants of the networks, which are explicitly accounted for in our bound, thus clarifying the precise circumstances affecting the tightness of our theoretical predictions.\n\n> Relations to Humayun et al 2024 paper should be well discussed and the additional contributions here.\n\nResponse: We agree that our paper is closely related to the work of Humayun et al. (2024). Indeed, our work aims to provide a theoretical angle on how to understand the empirical observations from their work. We are adding more discussion of the similarities and differences for the camera-ready version. \n\nPlease let us know if any aspects of our work would benefit from further clarification.", "claims_and_evidence": "Strengths\n\n1.\tIt offers an intuitive and mathematically rigorous measure for analyzing models and can be used to formalize previous results. Most, if not all, previous results referenced by this paper are only tested on very small networks (1D or 2D inputs) that can be analyzed analytically; this paper offers a method to generalize their results to more complex settings.\n\n2.\tThe math is well-developed, extensive and easy to follow.\n\n3.\tSimple and intuitive examples.\n\n4.\tThe authors provide experimental results to highlight the limitations of some connections.\n\n\nWeaknesses\n1.  The LC term was previously introduced in a paper Humayun, A. I., Balestriero, R., and Baraniuk, R. Deep networks always grok and here is why. In High-dimensional Learning Dynamics 2024: The Emergence of Structure and Reasoning, (https://openreview.net/pdf?id=NpufNsg1FP). This raises questions about the novelty of the concept, even though the purposes of the two papers appear to be different. There are quite similar ideas, definitions and illustrations.\n2.\tIt is not clear that the paper offers a new insight model generalization or otherwise. The dynamics of linear regions in the input space and their connections to the training procedures and generalization are referenced and no new insight is given, and no results demonstrate that a drop in LC correlates with a drop in the generalization error. While LC is an interesting measure, It's not clear that it currently provides a useful novel perspective.\n3.\tIt is very lacking in results. The only somewhat practical result is its connection to the adversarial robustness, which also needs to be tested on more complex settings than MNIST. While it seems that prior work in this area also lacks large-scale experiments, this paper could have used LC to demonstrate analytical results in more complex settings.\n4.\tThe paper shows that the connection to the feature’s manifold dimension only empirically holds in toy examples and breaks on MNIST, but the counterexample is in the appendix, and although referenced, is not discussed in detail. This contradicts parts of their insights and conclusion and feels \"hidden\".\n5.\tThere is not much discussion on the tightness of the bounds.\n6.\tIn the case of Total Variation (TV), both Figure 3 in the main paper and Figure 9 in the Appendix were expected to provide clear evidence that TV is bounded by Local Complexity (LC). However, the figures suggest that TV does not always remain strictly below LC, raising questions about the tightness of the theoretical bound and whether additional factors influence TV's behavior in late-stage training.", "methods_and_evaluation_criteria": "See above", "theoretical_claims": "The theory appears good, relating LC to TV. Its relevance and importance is less clear. Also novelty with respect to previous papers, as stated above.", "experimental_designs_or_analyses": "Not sufficient. Very simple networks and datasets.", "relation_to_broader_scientific_literature": "Relation to generalization properties at later stages of training, which is an important problem in DNNs.", "essential_references_not_discussed": "Relations to Humayun et al 2024 paper should be well discussed and the additonal contributions here.", "other_strengths_and_weaknesses": "see above", "other_comments_or_suggestions": "•\tContains multiple incorrect references (e.g., “Figure 5” on page 7 should reference Figure 3). Additionally, the Impact Statement is missing a period.\n\n•\tThe MNIST example was not fully clear. It did not specify how many or which classes were used for training, only stating that a very small subset of the data was taken.\n\n•\tIn Figure 2, why is there a spike rising after 1e6 iterations? Does this always happen (as it seems from Figure 7)?\n\n•\tIn Figure 2, the bounding connection between LC and LR was not completely clear when the drop occurred in each. Adding a grid might help improve readability.\n\n•\tLines 158, 307 – Missing capital letters, affecting consistency.\n\n•\tLeft paragraph, Lines 77-78 – Sentence unclear.\n\n•\tRight paragraph, Line 137 – \"that\" should be \"than\".\n\n•\tLine 290 – Unclear sentence: \"an 4\", \"to estimate the learn a map\" needs correction.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes a measure of local complexity for piecewise linear functions, corresponding to the density of linear regions over the input data distribution. This measure is connected to several aspects of ReLU networks, including low-dimensional representations, adversarial robustness, and representation cost. Theoretical results are provided to establish these connections, along with brief experimental validation.

The reviewers acknowledge that the paper offers a reasonable theoretical analysis that helps explain phenomena previously observed empirically, and extends earlier theoretical work from a global to a local perspective. Some of the concerns raised during the review process were addressed in the rebuttal phase. However, a few issues remain unresolved, particularly regarding the significance of the theoretical results, the depth of the empirical validation, and the overall level of novelty.

Nevertheless, the merits appear to outweigh the limitations. I therefore recommend acceptance and encourage the authors to consider the feedback and update the final version of the paper accordingly.
Decision: Accept (poster)