Losslessly Compressible Neural Network Parameters

To better understand complexity in neural networks, we theoretically investigate the idealised phenomenon of lossless network compressibility, whereby an identical function can be implemented with fewer hidden units. In the setting of single-hidden-layer hyperbolic tangent networks, we define the rank of a parameter as the minimum number of hidden units required to implement the same function. We give efficient formal algorithms for optimal lossless compression and computing the rank of a parameter. We also characterise the set of parameters with a given maximum rank as a union of linear subspaces. The lossless compression operations we study have implications for the approximate compressibility of nearby parameters and parameters in more complex architectures.