Deep ReLU networks – injectivity capacity upper bounds
Mihailo Stojnic · 2024
Read Deep ReLU networks – injectivity capacity upper bounds by Mihailo Stojnic (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-19677.txt.
Introduction
Mihailo Stojnic wrote a 2024 mathematics paper on how wide a deep neural network must grow to keep its input recoverable. Such networks pass a signal through stacked layers, each clipping low values to zero. The test is a matching test: can the input be recovered in full from the output? A ratio marks the smallest expansion from input size to output size that keeps recovery possible.
For a single layer, that ratio was pinned down recently. Stojnic carries the same investigation up to stacked networks. A framework ties a network of L layers to a twin of a known L-fold capacity model. A chance-based machinery then analyzes the statistics of the model. Simulations put the machinery to work. The needed expansion falls fast with depth. Four layers nearly close the gap to no expansion at all, matching laboratory experience that proofs had not touched before.
Catalog record
| CREATOR | Mihailo Stojnic |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 90 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-19677
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Deep ReLU networks – injectivity capacity upper bounds Mihailo Stojnic Abstract Abstract We study deep ReLU feed forward neural networks (NN) and their injectivity abilities. The main focus is on precisely determining the so-called injectivity capacity. For any given hidden layers architecture, it is defined as the minimal ratio between number of network’s outputs and inputs which ensures unique recoverability of the input from a realizable output. A strong recent progress in precisely studying single ReLU layer injectivity properties is here moved to a deep network level. In particular, we develop a program that connects deep l -layer net injectivity to an l -extension of the \ell_{0} spherical perceptrons, thereby massively generalizing an isomorphism between studying single layer injectivity and the capacity of the so-called (1-extension) \ell_{0} spherical perceptrons discussed in [ 82 ] . Random duality theory (RDT) based machinery is then created and utilized to statistically handle properties of the extended \ell_{0} spherical perceptrons and implicitly of the deep ReLU NNs. A sizeable set of numerical evaluations is conducted as well to put the entire RDT machinery in practical use. From these we observe a rapidly decreasing tendency in needed layers’ expansions, i.e., we observe a rapid expansion saturation effect . Only 4 layers of depth are sufficient to closely approach level of no needed expansion – a result that fairly closely resembles observations made in practical experiments and that has so far remained completely untouchable by any of the existing mathematical methodologies. Index Terms: Injectivity; Deep ReLU networks; Random duality . 1 Introduction An avalanche of research in machine learning (ML) and neural networks (NN) over the last decade produced some of the very best scientific breakthroughs. These include developments of both excellent algorithmic methodologies as well as their accompanying theoretical justifications. For almost all of them a superior level of understanding of underlying mathematical principles is needed. In this paper we study such a principle called injectivity and discuss how its presence/absence impacts/limits functioning of neural nets. Just by its definition, the functional injectivity plays a critical role in studying inverse problems and is in a direct correspondence with their well- or ill-posedness. It comes as a no surprise that recent theoretical and practical studying of (nonlinear) inverse problems via neural nets heavily relies on the associated injectivities (see, e.g., [ 6 , 11 , 39 , 32 , 16 , 41 , 19 , 15 , 82 ] ). Consequently, many aspects od injectivity gained strong interest in recent years including studying Lipshitzian/stability properties, [ 20 , 30 , 37 ] , role of the injective ReLU nets in manifold densities and approximative maps [ 48 , 49 , 52 ] , algorithmic approaches to generative models [ 21 , 41 , 51 , 33 , 44 , 55 , 50 , 56 , 35 , 32 , 89 ] , deep learning compressed sensing/phase retrieval [ 11 , 39 , 41 , 15 , 16 , 32 , 44 , 34 ] , and random matrix - neural networks connections [ 43 , 46 , 42 ] . As discussed in many of the above works, characterizing analytically injectivity of a whole network is not an easy mathematical problem. It typically relates to the so-called injectivity capacity defined as the minimal ratio of the network’s number of outputs and inputs for which a unique generative input produces a realizable output. Despite a host of technical difficulties, in addition to excellent practical implementations, strong accompanying analytical results are obtained in many of the above works as well. They usually relate to the so-called qualitative performance characterizations which typically give correct dimensional orders and, as such, provide an intuitive guidance for building networks’ architectures. Since our interest is in more precise, i.e., quantitative performance characterizations, results from [ 45 , 13 , 43 , 48 , 82 ] are more closely related to ours and we discuss them throughout the presentation after the introduction of necessary technical preliminaries. 2 Mathematical preliminaries, related work, and contributions For any given positive integer l , consider sequences of positive integers m_{0},m_{1},m_{2},m_{3},\dots,m_{l} , matrices A^{(i)}\in{\mathbb{R}}^{m_{i}\times m_{i-1}} , and real maps f_{g_{i}}(\cdot):{\mathbb{R}}^{m_{i}}\rightarrow{\mathbb{R}}^{m_{i}} . The following nonlinear system of equations will be the main mathematical object of our study \displaystyle\bar{{\bf y}}^{(l)}=f_{g_{l}}\left(A^{(l)}\dots\left(A^{(4)}f_{g_{3}}\left(A^{(3)}f_{g_{2}}\left(A^{(2)}f_{g_{1}}(A^{(1)}\bar{{\bf x}})\right)\right)\right)\right). (1) Adopting the convention n\triangleq m_{0} , one has that A^{(i)} ’s are linearly transformational system matrices, f_{g_{i}}(\cdot) are (nonlinear) system functions, and \bar{{\bf x}}\in{\mathbb{R}}^{n} is a generative input vector to be recovered. A generic nature of our presentation will ensure that both developed methodologies and obtained results can be utilized in conjunction with a host of different activation functions f_{g_{i}}(\cdot) . To ensure neatness of the exposition, we consider the so-called componentwise activation functions that act in the same manner on each coordinate of their vector argument. Given their importance in studying and practical utilization of deep neural networks (DNN), we consider ReLUs as concrete activation examples \displaystyle f_{g_{i}}({\bf x})=\max({\bf x},0), (2) with \max being applied componentwise. After setting \displaystyle{\mathcal{A}}_{1:l}\triangleq[A^{(1)},A^{(2)},\dots,A^{(l)}], (3) it is then not that difficult to see that the nonlinear system from ( 1 ) becomes the so-called \hskip 0.0pt{\color[rgb]{0,0,1}\textbf{\emph{Deep ReLU system ${\mathcal{N}}_{1:l}$:}}}\hskip 14.45377pt\bar{{\bf y}}^{(l)}=\max\left(A^{(l)}\dots\left(A^{(2)}\max\left(A^{(1)}\bar{{\bf x}},0\right),0\right),0\right)\triangleq\bar{f}_{nn}(\bar{{\bf x}};{\mathcal{A}}_{1:l}). (4) We particularly focus on mathematically typically the most challenging linear (or, as often called, proportional ) high-dimensional regimes with i -th layer absolute expansion coefficients \displaystyle\alpha_{i}\triangleq\lim_{m_{0}\rightarrow\infty}\frac{m_{i}}{m_{0}},i=1,2,\dots,l. (5) These are closely connected to relative expansion coefficients \displaystyle\zeta_{i}\triangleq\lim_{m_{0}\rightarrow\infty}\frac{m_{i}}{m_{i-1}}=\frac{\alpha_{i}}{\alpha_{i-1}},i=1,2,\dots,l. (6) Clearly, the absolute expansion coefficients relate to the expansion of the whole network, whereas the relative ones relate to the expansions within each of the layers. The system in ( 4 ) is a mathematical description of a feed forward ReLU DNN with input \bar{{\bf x}} , output \bar{{\bf y}} , and the weights of the gates in the i -th hidden layer being the rows of A^{(i)} . Given the growing popularity of machine learning (ML) and neural networks (NN) concepts, the interest in ReLU DNNs picked up over the last decade as well. Various properties of ReLU gates have been the subject of extensive research including both single-layer structures (see, e.g., [ 48 , 23 , 43 , 49 , 45 , 13 ] ) as well as more complex multilayered ones (see, e.g., [ 8 , 90 , 5 , 81 , 80 ] ). Of particular interest have been the invertibility or injectivity abilities of ReLU activations as they make them a bit different from, say, more traditional sign perceptrons or other nonlinear ones. For example, just mere existence of at least m_{1}\geq m_{0} nonzero elements at the output of the first layer is sufficient to recover the generating input (a non-degenerative scenario with any subset of rows/columns of A^{(i)} being of full rank is assumed throughout the paper; in statistical contexts of our interest here, this typically happens with probability 1). While potential existence of the injectivity is relatively easy to observe, it is highly nontrivial to determine the minimal length of \bar{{\bf y}} that ensures its existence (see, e.g., [ 48 , 23 , 43 , 49 , 45 , 13 , 82 ] ). In fact, this is already very complicated to do evem for a single layer network [ 43 , 82 ] .