On the Local Complexity of Linear Regions in Deep ReLU Networks

Niket Patel, Guido Montúfar · 2024

Read On the Local Complexity of Linear Regions in Deep ReLU Networks by Niket Patel, Guido Montúfar (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-18283.txt.

Introduction

Niket Patel and Guido Montúfar measure how chopped-up a neural network's behavior is near real data, in this 2024 paper. Networks built from ReLU units compute a different linear formula in each region of input space. The density of those regions near the data, the local complexity, says how wiggly the learned function is.

The pair prove that when a network learns low-dimensional features, its local complexity drops. That ties a property of the weight matrices to a property of the function itself. They also show local complexity caps the function's total variation over the data, which links feature learning to robustness against small attacks. Finally, they argue that training itself pushes networks toward lower local complexity. The framework gives theorists a bridge between the geometry of these networks and what they learn.

Catalog record

CREATORNiket Patel, Guido Montúfar
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE97 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-18283

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Local Complexity of Linear Regions in Deep ReLU Networks Niket Patel, Guido Montúfar 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. 1 Introduction Despite the numerous achievements of deep learning, many of the mechanisms by which deep neural networks learn and generalize remain unclear. An “Occam’s Razor” style heuristic is that we want our neural network to parameterize a simple solution after training, but it can be challenging to establish a useful metric of the complexity of a deep neural network ( Hu et al., 2021 ) . We may gain more insights in the case where we use piece-wise linear activation functions, such as ReLU, LeakyReLU, or Maxout. If \phi is a continuous piecewise linear (CPWL) activation function and A_{i}(x)=W_{i}x-\beta_{i} is a parameterized affine linear function, i=1,\ldots,L , we consider a network of the following form: \mathcal{N}_{\theta}(x)=A_{L}\circ\phi\circ A_{L-1}\cdots\phi\circ A_{1}(x),\quad x\in\mathbb{R}^{n_{0}}. (1) The network function \mathcal{N}_{\theta}\colon\mathbb{R}^{n_{0}}\to\mathbb{R}^{n_{L}} parameterized by \theta=(W_{i},\beta_{i})_{i} is then also be a CPWL function. For any fixed choice of the parameter \theta , the input domain \mathbb{R}^{n_{0}} is partitioned into linear regions where the function is linear. These partitions of the input space have been used extensively to study diverse topics such as the expressive power, decision boundaries in classification, gradients and parameter initialization, and generalization ( 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 , e.g.,) . In this work we aim to advance a theoretical framework towards better understanding the local distribution of linear regions near the data distribution and how it relates to other relevant aspects of learning such as robustness and representation learning. 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 ( Williams et al., 2019 ; Jin & Montúfar, 2023 , see, e.g.,) . 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 ( Maennel et al., 2018 ; Williams et al., 2019 ; Shevchenko et al., 2022 , e.g.,) . Characterizing the dynamics of linear regions at a theoretical level remains a significant outstanding challenge, even for shallow 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 to an increase in the model’s adversarial robustness. We replicate similar experiments in Figure 3 . In this work, we aim to develop theory to explain some of the empirical results of Humayun et al. (2024b) . Grokking describes a sudden improvement in generalization error or robustness after prolonged training, typically occurring once the training loss is near zero. It is linked to representation learning, suggesting that late generalization arises when a network develops the appropriate representations ( Liu et al., 2022 ) . This leads to our first question: 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 ; Yunis et al., 2024a ) . 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 intermediate 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-dimensional feature manifolds will generally also have fewer linear regions. Empirical results also show that networks which undergo a drop in the number of linear regions tend to be simpler, having a nearly piecewise constant structure, hinting at a 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, a natural question we concern ourselves with is: Question 2: Can we connect the local density of linear regions to the robustness of a network? We attempt to 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. Aspects in this direction have appeared in context of parameter initialization and the gradients of a network with respect to its inputs ( Hanin & Rolnick, 2018 ; Tseran & Montúfar, 2023 , e.g.,) . 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 measure 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 input space. In Section 3 we define the local complexity (LC) as the average density of non-linearites over a dataset. To capture the typical behavior of the functions, we define this measure in a way that is robust to perturbations of the bias parameters. • In Section 4 we establish theoretical connections between the proposed local complexity and

Read the complete text