On the Sample Complexity of One Hidden Layer Networks with Equivariance, Locality and Weight Sharing

• URL: http://arxiv.org/abs/2411.14288v1
• Date: Thu, 21 Nov 2024 16:36:01 GMT
• Title: On the Sample Complexity of One Hidden Layer Networks with Equivariance, Locality and Weight Sharing
• Authors: Arash Behboodi, Gabriele Cesa,
• Abstract summary: Weight sharing, equivariance, and local filters, as in convolutional neural networks, are believed to contribute to the sample efficiency of neural networks. We obtain lower and upper sample complexity bounds for a class of single hidden layer networks. We show that the bound depends merely on the norm of filters, which is tighter than using the spectral norm of the respective matrix.
• Score: 12.845681770287005
• License:
• Abstract: Weight sharing, equivariance, and local filters, as in convolutional neural networks, are believed to contribute to the sample efficiency of neural networks. However, it is not clear how each one of these design choices contribute to the generalization error. Through the lens of statistical learning theory, we aim to provide an insight into this question by characterizing the relative impact of each choice on the sample complexity. We obtain lower and upper sample complexity bounds for a class of single hidden layer networks. It is shown that the gain of equivariance is directly manifested in the bound, while getting a similar increase for weight sharing depends on the sharing mechanism. Among our results, we obtain a completely dimension-free bound for equivariant networks for a class of pooling operations. We show that the bound depends merely on the norm of filters, which is tighter than using the spectral norm of the respective matrix. We also characterize the trade-off in sample complexity between the parametrization of filters in spatial and frequency domains, particularly when spatial filters are localized as in vanilla convolutional neural networks.

Related papers

• Sampling weights of deep neural networks [1.2370077627846041]
  We introduce a probability distribution, combined with an efficient sampling algorithm, for weights and biases of fully-connected neural networks. In a supervised learning context, no iterative optimization or gradient computations of internal network parameters are needed. We prove that sampled networks are universal approximators.
  arXiv  Detail & Related papers  (2023-06-29T10:13:36Z)
• Understanding the Covariance Structure of Convolutional Filters [86.0964031294896]
  Recent ViT-inspired convolutional networks such as ConvMixer and ConvNeXt use large-kernel depthwise convolutions with notable structure. We first observe that such learned filters have highly-structured covariance matrices, and we find that covariances calculated from small networks may be used to effectively initialize a variety of larger networks.
  arXiv  Detail & Related papers  (2022-10-07T15:59:13Z)
• On the Shift Invariance of Max Pooling Feature Maps in Convolutional Neural Networks [0.0]
  Subsampled convolutions with Gabor-like filters are prone to aliasing, causing sensitivity to small input shifts. We highlight the crucial role played by the filter's frequency and orientation in achieving stability. We experimentally validate our theory by considering a deterministic feature extractor based on the dual-tree complex wavelet packet transform.
  arXiv  Detail & Related papers  (2022-09-19T08:15:30Z)
• On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias [50.84569563188485]
  We show that gradient flow converges in direction when labels are determined by the sign of a target network with $r$ neurons. Our result may already hold for mild over- parameterization, where the width is $tildemathcalO(r)$ and independent of the sample size.
  arXiv  Detail & Related papers  (2022-05-18T16:57:10Z)
• Deep Learning for the Benes Filter [91.3755431537592]
  We present a new numerical method based on the mesh-free neural network representation of the density of the solution of the Benes model. We discuss the role of nonlinearity in the filtering model equations for the choice of the domain of the neural network.
  arXiv  Detail & Related papers  (2022-03-09T14:08:38Z)
• The Sample Complexity of One-Hidden-Layer Neural Networks [57.6421258363243]
  We study a class of scalar-valued one-hidden-layer networks, and inputs bounded in Euclidean norm. We prove that controlling the spectral norm of the hidden layer weight matrix is insufficient to get uniform convergence guarantees. We analyze two important settings where a mere spectral norm control turns out to be sufficient.
  arXiv  Detail & Related papers  (2022-02-13T07:12:02Z)
• Implicit Equivariance in Convolutional Networks [1.911678487931003]
  Implicitly Equivariant Networks (IEN) induce equivariant in the different layers of a standard CNN model. We show IEN outperforms the state-of-the-art rotation equivariant tracking method while providing faster inference speed.
  arXiv  Detail & Related papers  (2021-11-28T14:44:17Z)
• Unrolling Particles: Unsupervised Learning of Sampling Distributions [102.72972137287728]
  Particle filtering is used to compute good nonlinear estimates of complex systems. We show in simulations that the resulting particle filter yields good estimates in a wide range of scenarios.
  arXiv  Detail & Related papers  (2021-10-06T16:58:34Z)
• Spatially Adaptive Inference with Stochastic Feature Sampling and Interpolation [72.40827239394565]
  We propose to compute features only at sparsely sampled locations. We then densely reconstruct the feature map with an efficient procedure. The presented network is experimentally shown to save substantial computation while maintaining accuracy over a variety of computer vision tasks.
  arXiv  Detail & Related papers  (2020-03-19T15:36:31Z)
• Revisiting Spatial Invariance with Low-Rank Local Connectivity [33.430515807834254]
  We show that relaxing spatial invariance improves classification accuracy over both convolution and locally connected layers. In experiments with small convolutional networks, we find that relaxing spatial invariance improves classification accuracy over both convolution and locally connected layers.
  arXiv  Detail & Related papers  (2020-02-07T18:56:37Z)

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.