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. We have addressed your thorough list of minor errata for the camera-ready version. Below we address each major point raised.

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.

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

... It's not clear that it currently provides a useful novel perspective

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

It is very lacking in results / ... needs to be tested on more complex settings than MNIST.

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

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.

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

Relations to Humayun et al 2024 paper should be well discussed and the additional contributions here.

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

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, and their positive review. We have addressed your minor errata for the camera-ready version.

The method for estimating LC via bias perturbations could be better motivated, particularly regarding sensitivity to noise variance.

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

The paper would benefit from a discussion of how LC compares to standard complexity metrics like VC dimension.

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

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?

Response: 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 $TV = \mathbb E_x[ || \nabla f(x) || ] \leq K.$ This suggests that controlling the Lipschitz constant may indirectly influence the local complexity, thereby impacting robustness.

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. We have addressed minor errata for the camera-ready version.

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? ... Would this directly connect to the robustness mentioned in Section 5?

The 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 $Jf(x) = W_1 D_1 W_2 D_2 \cdots W_L D_L,$ where 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.

Some comments on how to estimate the bound would be useful to enhance the clarity of the theorem.

We estimate the bound on local complexity by considering the operator norm of the weight matrices. In particular, we compute an upper bound via $\max_l {|| W_l \cdots W_1 | |}$ which 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$.

Are there more general bounds that describe the local complexity in terms of depth?

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

... it is not known how to use it to design a more robust model or motivate architecture design.

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

Could you highlight the difference between the definition of local complexity and the one in (Hanin & Rolnick, 2019b)?

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

How does $\sigma$ affect the local complexity in Theorem 2? This parameter seems to be hidden by $\rho_{b_i}$.

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

Are the constants in Theorem 5 and 7 the same ones defined in Corollary 3?

Yes, these are the same constants.

If the local complexity is known, would it be possible to shed light on the hardness of reverse engineering?

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

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?

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

For a given ReLU network, we can create a corresponding ResNet by adding skip connections. Would this ResNet have lower local complexity?

Consider a simple one-layer example where $f_{\text{res}}(x) = f_\theta(x) + x.$ Its Jacobian is $Jf_{\text{res}}(x) = Jf_\theta(x) + I.$ Here, 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.

Please let us know if further clarification is needed.