The sampling complexity of learning invertible residual neural networks

• URL: http://arxiv.org/abs/2411.05453v1
• Date: Fri, 08 Nov 2024 10:00:40 GMT
• Title: The sampling complexity of learning invertible residual neural networks
• Authors: Yuanyuan Li, Philipp Grohs, Philipp Petersen,
• Abstract summary: 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. We consider the question of whether the sampling complexity can be improved by restricting the specific neural network architecture. Our main result shows that the residual neural network architecture and invertibility do not help overcome the complexity barriers encountered with simpler feedforward architectures.
• Score: 9.614718680817269
• License:
• Abstract: 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.

Related papers

• Residual Random Neural Networks [0.0]
  Single-layer feedforward neural network with random weights is a recurring motif in the neural networks literature. We show that one can obtain good classification results even if the number of hidden neurons has the same order of magnitude as the dimensionality of the data samples.
  arXiv  Detail & Related papers  (2024-10-25T22:00:11Z)
• Generalization and Estimation Error Bounds for Model-based Neural Networks [78.88759757988761]
  We show that the generalization abilities of model-based networks for sparse recovery outperform those of regular ReLU networks. We derive practical design rules that allow to construct model-based networks with guaranteed high generalization.
  arXiv  Detail & Related papers  (2023-04-19T16:39:44Z)
• Global quantitative robustness of regression feed-forward neural networks [0.0]
  We adapt the notion of the regression breakdown point to regression neural networks. We compare the performance, measured by the out-of-sample loss, by a proxy of the breakdown rate. The results indeed motivate to use robust loss functions for neural network training.
  arXiv  Detail & Related papers  (2022-11-18T09:57:53Z)
• Data-driven emergence of convolutional structure in neural networks [83.4920717252233]
  We show how fully-connected neural networks solving a discrimination task can learn a convolutional structure directly from their inputs. By carefully designing data models, we show that the emergence of this pattern is triggered by the non-Gaussian, higher-order local structure of the inputs.
  arXiv  Detail & Related papers  (2022-02-01T17:11:13Z)
• Generalization Error Bounds for Iterative Recovery Algorithms Unfolded as Neural Networks [6.173968909465726]
  We introduce a general class of neural networks suitable for sparse reconstruction from few linear measurements. By allowing a wide range of degrees of weight-sharing between the layers, we enable a unified analysis for very different neural network types.
  arXiv  Detail & Related papers  (2021-12-08T16:17:33Z)
• Robust lEarned Shrinkage-Thresholding (REST): Robust unrolling for sparse recover [87.28082715343896]
  We consider deep neural networks for solving inverse problems that are robust to forward model mis-specifications. We design a new robust deep neural network architecture by applying algorithm unfolding techniques to a robust version of the underlying recovery problem. The proposed REST network is shown to outperform state-of-the-art model-based and data-driven algorithms in both compressive sensing and radar imaging problems.
  arXiv  Detail & Related papers  (2021-10-20T06:15:45Z)
• Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks [79.74580058178594]
  We analyze the performance of training a pruned neural network by analyzing the geometric structure of the objective function. We show that the convex region near a desirable model with guaranteed generalization enlarges as the neural network model is pruned.
  arXiv  Detail & Related papers  (2021-10-12T01:11:07Z)
• A Sparse Coding Interpretation of Neural Networks and Theoretical Implications [0.0]
  Deep convolutional neural networks have achieved unprecedented performance in various computer vision tasks. We propose a sparse coding interpretation of neural networks that have ReLU activation. We derive a complete convolutional neural network without normalization and pooling.
  arXiv  Detail & Related papers  (2021-08-14T21:54:47Z)
• Modeling the Nonsmoothness of Modern Neural Networks [35.93486244163653]
  We quantify the nonsmoothness using a feature named the sum of the magnitude of peaks (SMP) We envision that the nonsmoothness feature can potentially be used as a forensic tool for regression-based applications of neural networks.
  arXiv  Detail & Related papers  (2021-03-26T20:55:19Z)
• Compressive sensing with un-trained neural networks: Gradient descent finds the smoothest approximation [60.80172153614544]
  Un-trained convolutional neural networks have emerged as highly successful tools for image recovery and restoration. We show that an un-trained convolutional neural network can approximately reconstruct signals and images that are sufficiently structured, from a near minimal number of random measurements.
  arXiv  Detail & Related papers  (2020-05-07T15:57:25Z)
• Beyond Dropout: Feature Map Distortion to Regularize Deep Neural Networks [107.77595511218429]
  In this paper, we investigate the empirical Rademacher complexity related to intermediate layers of deep neural networks. We propose a feature distortion method (Disout) for addressing the aforementioned problem. The superiority of the proposed feature map distortion for producing deep neural network with higher testing performance is analyzed and demonstrated.
  arXiv  Detail & Related papers  (2020-02-23T13:59:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.