Computational Complexity of Detecting Proximity to Losslessly
  Compressible Neural Network Parameters
Matthew Farrugia-Roberts
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 a smaller network. We
give an efficient formal algorithm for optimal lossless compression in the
setting of single-hidden-layer hyperbolic tangent networks. To measure lossless
compressibility, we define the rank of a parameter as the minimum number of
hidden units required to implement the same function. Losslessly compressible
parameters are atypical, but their existence has implications for nearby
parameters. We define the proximate rank of a parameter as the rank of the most
compressible parameter within a small $L^\infty$ neighbourhood. Unfortunately,
detecting nearby losslessly compressible parameters is not so easy: we show
that bounding the proximate rank is an NP-complete problem, using a reduction
from Boolean satisfiability via a geometric problem involving covering points
in the plane with small squares. These results underscore the computational
complexity of measuring neural network complexity, laying a foundation for
future theoretical and empirical work in this direction.