Mixing Complexity and its Applications to Neural Networks
This addresses the problem of understanding learning capabilities under memory constraints for neural network researchers, but appears incremental as it applies an existing notion to a new context.
The paper tackles the problem of analyzing neural networks through space constraints, introducing mixing complexity to measure learning limitations with bounded-memory algorithms, and obtains new results on what can and cannot be learned using neural networks.
We suggest analyzing neural networks through the prism of space constraints. We observe that most training algorithms applied in practice use bounded memory, which enables us to use a new notion introduced in the study of space-time tradeoffs that we call mixing complexity. This notion was devised in order to measure the (in)ability to learn using a bounded-memory algorithm. In this paper we describe how we use mixing complexity to obtain new results on what can and cannot be learned using neural networks.