On the Local Complexity of Linear Regions in Deep ReLU Networks

We sincerely thank the reviewer for their thoughtful and detailed comments which have helped us improve our paper. Below we address the items raised in the review.

What is the significance of the notion of Local Rank?

The relevance of the Local Rank is that it is a natural concept that we can relate to other interesting concepts. In our work, we related the Local Complexity and the Local Rank. We have updated the mentioned reference (Chechik et al.) with the more relevant (Patel & Shwartz-Ziv, 2024). The Local Rank is a definition that is closely related to ideas in differential geometry, particularly the rank of a smooth map, submersions and immersions of manifolds. Since this gives a way to quantify the rank in a non-linear manner, we think that this is a natural definition. It is also related to other notions of rank that appear in the literature. Some works look at the rank of the feature matrix, which is the $d\times n$ matrix of $d$-dimensional latent features for $n$-samples. If this matrix has rank $r < \min \{n,d\}$, then this means that the network maps input points to a low dimensional subspace. This also means that the feature manifold must have rank less than or equal to $r$, so the rank of the embedding matrix bounds the Local Rank. Another relevant way rank appears is with respect to the rank of weight matrices. If we suppose that the $l$-th layer weight matrix has rank $r$, then the Local Rank must be less than or equal to $r$, since we can compute that the Jacobian of the network to the $l$-th layer is $W_1 D_1 W_2 D_2 \cdots D_{l-1}W_l$, where $D_i$ are diagonal $0,1$ matrices corresponding to the activation patterns of the ReLU functions at the $i$-th layer.

How does the bound in proposition 8 fare against similar bounds (i.e. of Hanin et al.).

Our work develops a theoretical framework that shares similarities with the approach developed by Hanin & Rolnick to study linear regions, particularly in the application of the co-area formula. However, the bound in Proposition 8 (now Proposition 9 in the updated draft) and the bounds of Hanin & Rolnick are describing different quantities and as such are not comparable. The result in our proposition provides a view into how the local complexity relates to works on implicit regularization. This allows us to understand how the linear regions may look like after training. On the other hand, the bounds by Hanin & Rolnick describe the expectation value of the number of linear regions over the input space given a distribution over the parameters. Their work does not pursue a description of the distribution of the linear regions for a specific choice of parameters nor provides results about how the linear regions may look like after training.

As the author-reviewer discussion period is ending soon, we kindly ask if you could review our responses to your comments. If you have further questions or comments, we will do our best to address them before the discussion period ends. If our responses have resolved your concerns, we would greatly appreciate it if you could update your evaluation of our work accordingly.

How can practitioners leverage the findings on local complexity in their model design and training processes?

Our investigation leads to several actionable insights. For one, we demonstrate that robustness and the local complexity are related concepts. Following this, to improve robustness one would want to design the optimization procedure in a way that minimizes (explicitly or implicitly) the local complexity. We show that training in the kernel regime leads to limited change in the local complexity. In view of this, initialization and learning rate schemes that promote feature learning, and leave the kernel regime, would then have positive effects on the robustness of trained networks. We also provide, in Section 6.2 and Figure 12, a connection between the use of weight decay and the local complexity, showing that large values of the weight decay parameter may implicitly regularize the local complexity.

We have also made additional improvements to strengthen the paper in this regard. These include adding Proposition 6, which directly relates the total variation and the existence of adversarial examples in a simplified setting. We have also added Appendix A.10, which bounds the change in the local complexity when the change in the parameters is small. Please let us know if any aspects of our work would benefit from further clarification.

We sincerely thank the reviewer for their thoughtful and detailed comments which have helped us improve our paper. Below we address the items raised in the review.

A broader analysis across different scenarios would be necessary to ensure that the findings are not artifacts of particular experimental setups.

In the present work we aim to provide a theoretical framework to establish links between the linear regions in ReLU networks and other relevant geometric properties. Our motivation is to complement recent experimental works from a theoretical perspective. We agree that experimental analysis is valuable and that is why we also included some experimental evaluations in our work, which we will continue to expand and update in this line of investigation. At any rate we would direct to the work of Humayun et al. (2024) for a more detailed empirical study of the relations between the linear regions and adversarial robustness, including an examination across different scenarios and architectures.

can authors provide more intuitive explanations on why the noisy biases are considered instead of noisy weights?

We have revised Section 3.1 to better explain our approach. 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. Perturbations to the weight matrix introduce changes in the direction of these boundaries and are naturally more complex. However, we can also include perturbations of the weights and extend all definitions to also include perturbations of the weights. We have added Figure 5 in the appendix to illustrate how adding perturbations to the weight matrices does not qualitatively change our measure of the local complexity.

Regarding Corollary 3: can authors provide more explanations on the defined constants $c^\eta_\text{bias}$ and $\bar \xi_\eta$? What is the meaning of these quantities and how are they related to the local complexity?

These constants give us a trade-off parameterized by $\eta$ when computing a lower bound on the local complexity, which controls the tightness of the bound. In our proof, these constants serve to bound separately the cases where the noisy biases fall too far away from their mean via concentration inequalities. This trade-off can also be represented in the form $c^\eta_\text{bias} (\mathbb E\|\nabla z(x)\| - \Theta(\frac1{\eta^2}))$. We can tell that this never trivializes our bound for some choice of $\eta$, as $c^\eta_\text{bias} = \frac1{\sqrt{2\pi}\sigma} e^{\frac{\eta^2}{2\sigma^2}}$ is always positive. So we can choose $\eta$ large enough such that $\mathbb E\|\nabla z(x)\| > \frac{1}{\eta^2}$, and we get that the whole term $c^\eta_\text{bias} (\mathbb E\|\nabla z(x)\| - \Theta(\frac1{\eta^2})) > 0$, so this bound is not trivial.

Also, the definition of $\Theta$ seems missing.

We have added a footnote on page 6 that explains our use of the notation $\Theta$, which refers to the standard asymptotic notation: $f(x) = \Theta(g(x))$ if $f$ is asymptotically bounded above and below by $g$, meaning that there exist $c_1, c_2, x_0$ such that for any $x > x_0$, $c_1g(x) \leq f(x) \leq c_2g(x)$.

How do these results directly relate to existing theories on model complexity and adversarial robustness?

We think that the closest comparison of our work is the empirical study of Humayun et al. (2024). Our work complements this work by providing a theoretical framework and theoretical results. Other related works include that of Li et al. (2022), which relates adversarial robustness to the VC dimension of the function class. This is similar in flavor to our results, as they show for small enough VC dimension, one can prove robustness results. Another result that links complexity of the linear regions to robustness is that of Humayun et al. (2023), which leverages the linear region structure of ReLU networks to design an algorithm which improves adversarial robustness. Croce et al. (2019) is another relevant work, which relates the size of linear regions to adversarial robustness, and provides an algorithm which increases the size of linear regions in a way to try and improve robustness. We have added some of the missing references to the Related Works section to provide a better overview of the field. Please let us know if you are aware of any other relevant references.

We sincerely thank the reviewer for their thoughtful and detailed comments which have helped us improve our paper. Below we address the items raised in the review.

(Originality)

Our theoretical framework shares similarities with that of Hanin & Rolnick, particularly in the application of the co-area formula to discuss linear regions. However, our definitions and results differ in several key aspects. Hanin & 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 across different regions of parameters and we are concerned with the distribution of linear regions over different portions of the input space, which are aspects that are not discussed in the work of Hanin & Rolnick. These differences are reflected in our definitions, where we consider perturbations around a specific parameter and we consider the density of linear regions over the input space integrated over an input data distribution. We may also point out that the paper of Hanin & Rolnick does not pursue results describing properties such as the Local Rank or the Total Variation, which we investigate in our work. We have added a note in Section 3.1 in the revision to further highlight these differences.

(Tightness)

Regarding the tightness of theoretical bounds, we have added a new section (Appendix B.4) analyzing empirically the tightness on the bound of the Total Variation. We find that the observed increase in total variation late in training for some initializations is primarily driven by an increase in the Lipschitz constants of the layer-wise functions $g_l$, rather than a fundamental looseness in our bounds. We have empirically measured the Lipschitz constants during training, showing that the ratio between our theoretical upper bound and the observed values remains relatively stable during training. Previously we had reported an increase in the total variation late in training for some initialization scales, but observe that the theoretical result is a bound for the ratio of the Total Variation and a maximal Lipschitz constant of a subset of the layers. When this is considered, the theoretical bound tracks the experimental results as shown in Figure 9.

We would also like to note that the bounds relating the local complexity and the rank of learned representations in Section 4 are controlled in the sense that we have both an upper and lower bound connecting the local complexity to the local rank. See Theorem 5, Equations (11) and (12).

(Non-differentiable)

It is correct that ReLUs are not differentiable at 0. In our results we use the derivatives of neurons with respect to the input to the network. These functions are almost everywhere differentiable over the input space and since our results integrate over an input density, the non-differentiable points are inconsequential and have no bearing on the results. We have added a clarification to the text in Section 3.2.

We would also like to note that the total variation is well defined for many functions which do not admit a derivative. In particular, it can be defined for any $L^1$ integrable function.

(Piecewise Linear Activation)

In the present work we focus on the ReLU activation as this is the most commonly used piecewise linear activation. However, we believe that similar results should also hold for other piecewise linear activation functions. A program in that direction could follow some of the strategies from the work of Tseran and Montufar (2021) on the expected number of linear regions for maxout networks. This would be an interesting and natural generalization. We have added a note on this in the conclusion.

(Other)

As it may be of interest, we have added Proposition 6, which relates the total variation and the existence of adversarial examples in a simplified setting. We have also added a Appendix A.10, which bounds the change in the local complexity when the change in the parameters is small. Please let us know if any aspects would benefit from further clarification.

Discussion in lines 200-210 is not very clear. For example, why noise is only added to biases, and not to the input / weight matrices?

We have revised Section 3.1 to better explain our approach. Our theoretical framework is based on the analysis of the level at which a ReLU transitions from being inactive to being active. The biases directly control such transitions and that is why we focus on perturbations of the biases. It is possible to extend the definitions to include perturbations of the weights as well. Perturbations to the weight matrices introduce changes in the direction of the boundaries, which are naturally more complicated. We have added Figure 5 in the appendix to illustrate how adding perturbations to the weight matrices does not qualitatively change our measure of the local complexity.

Line 386: "our theoretical result involves several interdependent components": could you clarify this sentence?

To clarify point 4 in your review, what we mean by "several interdependent components" is that several factors play a role in our analysis. We have reworded the discussion around line 386 to be more specific.

In this context, we made additional improvements to convey the interaction between different quantities in our article. Concretely, we added Proposition 6, which directly relates the total variation and the existence of adversarial examples in a simplified setting. We also added Appendix A.10, which bounds the change in the local complexity when the change in the parameters is small. Please let us know if any aspects would benefit from further clarification.

We sincerely thank the reviewer for their thoughtful and detailed comments which have helped us improve our paper. Below we address each point raised:

Also, as authors mention themselves, proof of Theorem 2 essentially directly follows from (Hanin & Rolnick 2019a).

Our work uses a theoretical framework that shares similarities with the work of Hanin & Rolnick, particularly in the application of the co-area formula to study linear regions. We believe that it is important to give credit to Hanin & Rolnick for their ingenious application of the co-area formula to study linear regions. Kindly observe however that the co-area formula is a classic and general result in multivariate calculus and therefore that it will arise in all kinds of calculations involving a change of variables and results such as the Kac-Rice formula (see Appendix A.2 for simple example calculations of the relating our use of the co-area formula and the change of variables).

Although as we acknowledged the proof of Theorem 2 can be obtained using results from Hanin & Rolnick, overall the two articles differ substantially in their focus and range of results. Hanin & Rolnick primarily investigate how the depth and number of neurons affect the expected number of linear regions of a neural network for a generic distribution over the parameters. In contrast, our analysis explores how the linear regions vary across different regions of the parameter space, that is, we attend to specific choices of parameters. Since other works have not focused on specific choices of parameters, they do not provide a framework to compare to. Furthermore, in our work and results we are interested in the properties of the linear regions that are local to particular regions of the input space, an aspect which is not discussed in the work of Hanin & Rolnick.

Is it possible to plot / show estimates of the bounds of Theorems 4,5?

Regarding the tightness of theoretical bounds, we have added a new section (Appendix B.4) analyzing empirically the tightness on the bound for the Total Variation. We find that the observed increase in total variation late in training for some initializations is primarily driven by an increase in the Lipschitz constants of the layer-wise functions $g_l$, rather than a fundamental looseness in our bounds. We have empirically measured the Lipschitz constants during training, showing that the ratio between our theoretical upper bound and the observed values remains relatively stable during training. Previously we had reported an increase in the total variation late in training for some initialization scales, but we should point out that the theoretical result is a bound for the ratio of the Total Variation and the maximal Lipschitz constant of a subset of the layers. When this is considered, the theoretical bound tracks the experimental results as shown in Figure 9.

We would also like to note that the bounds relating the local complexity and the rank of learned representations in Section 4 are controlled in the sense that we have both an upper and lower bound connecting the local complexity to the local rank. See Theorem 5, Equations (11) and (12).

What is $R(\mathcal{N}_\theta)$ in Proposition 7?

Concerning the definition of $R(\mathcal{N}\_\theta)$ , we have revised the definition to be more precise: $R(f) = \inf\_{\theta} {\|\theta\|\_F : \mathcal{N}\_\theta(x) = f(x) \text{ for all } x \in \Omega }$, where the infimum is taken over weights $\tilde{\theta}$ that preserve the function. This quantity is non-zero in general.

We sincerely thank the reviewer for their thoughtful and detailed comments which have helped us improve our paper. Below we address the items raised in the review:

Is there any lower bound for the local complexity in the kernel regime?

In the kernel regime the weights do not move far from their initial values during training. Thus, in this setting, we expect that results that hold at initialization should also approximately hold after training. We have added a theoretical result (Proposition 17 in Appendix A.10) that shows this for a simple setting. Here we show for two layer networks that, when the parameters stay close to initialization, the local complexity stays close to the local complexity at initialization.

The tightness of the bound is not discussed by theory or experiments.

Regarding the tightness of the theoretical bounds, we have added a new section (Appendix B.4) analyzing empirically the tightness of the bound on the total variation. We find that the observed increase in total variation late in training for some initializations is primarily driven by an increase in the Lipschitz constants of the layer-wise functions $g_l$, rather than a fundamental looseness in our bounds. We have empirically measured the Lipschitz constants during training, showing that the ratio between our theoretical upper bound and the observed values remains relatively stable during training. Previously we had compared the total variation late in training for some initialization scales, but observe that the theoretical result is a bound for the ratio of the Total Variation and a maximal Lipschitz constant of a subset of the layers. When this is considered, the theoretical bound tracks the experimental results as shown in Figure 9.

We would also like to note that the bounds relating the local complexity and the rank of learned representations in Section 4 are controlled in the sense that we have both an upper and lower bound connecting the local complexity to the local rank. See Theorem 5, Equations (11) and (12).

In the revision we have included further improvements, including Proposition 6, which directly relates the total variation and the existence of adversarial examples in a simplified setting. Please let us know if any aspects would benefit from further clarification.