The sampling complexity of learning invertible residual neural networks
This is an incremental result for researchers in deep learning theory, showing that architectural restrictions like invertibility do not alleviate fundamental complexity barriers in neural network approximation.
The paper tackled the problem of whether invertible residual neural networks can reduce the sampling complexity for high uniform accuracy approximation from point samples, and found that they still suffer from the curse of dimensionality, similar to simpler feedforward architectures.
In recent work it has been shown that determining a feedforward ReLU neural network to within high uniform accuracy from point samples suffers from the curse of dimensionality in terms of the number of samples needed. As a consequence, feedforward ReLU neural networks are of limited use for applications where guaranteed high uniform accuracy is required. We consider the question of whether the sampling complexity can be improved by restricting the specific neural network architecture. To this end, we investigate invertible residual neural networks which are foundational architectures in deep learning and are widely employed in models that power modern generative methods. Our main result shows that the residual neural network architecture and invertibility do not help overcome the complexity barriers encountered with simpler feedforward architectures. Specifically, we demonstrate that the computational complexity of approximating invertible residual neural networks from point samples in the uniform norm suffers from the curse of dimensionality. Similar results are established for invertible convolutional Residual neural networks.