On the Sample Complexity of One Hidden Layer Networks with Equivariance, Locality and Weight Sharing
cs.LG, math.ST, stat.ML, stat.TH
Submitted: 2024-11-21
Updated: 2025-01-23
Comments: 48 pages, TMLR accepted
Journal ref: Transactions on Machine Learning Research, 2025
License: http://creativecommons.org/licenses/by/4.0/
The gist: Weight sharing, equivariance, and local filters, as in convolutional neural networks, are believed to contribute to the sample efficiency of neural networks.
Terminology
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 contributes to the generalization error. Through the lens of statistical learning theory, we aim to provide 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. For a large class of activation functions, the bounds depend merely on the norm of filters and are dimension-independent. We also provide bounds for max-pooling and an extension to multi-layer networks, both with mild dimension dependence. We provide a few takeaways from the theoretical results. It can be shown that depending on the weight-sharing mechanism, the non-equivariant weight-sharing can yield a similar generalization bound as the equivariant one. We show that locality has generalization benefits, however the uncertainty principle implies a trade-off between locality and expressivity. We conduct extensive experiments and highlight some consistent trends for these models.
Sources
- Non-Vacuous Generalisation Bounds for Shallow Neural Networks
- Geometric and Physical Quantities Improve E(3) Equivariant Message Passing
- Geometric Algebra Transformer
- Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges
- A General Theory of Equivariant CNNs on Homogeneous Spaces
- Group Equivariant Convolutional Networks
- Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
- Generalization bounds for deep convolutional neural networks
- On the Benefits of Invariance in Neural Networks
- In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictors
- The role of invariance in spectral complexity-based generalization bounds
- Approximation-Generalization Trade-offs under (Approximate) Group Equivariance
- Clifford Group Equivariant Neural Networks
- Tensor field networks: Rotation- and translation-equivariant neural networks for 3D point clouds
- Generalization bounds for deep learning
- The Sample Complexity of One-Hidden-Layer Neural Networks
- Coordinate Independent Convolutional Networks -- Isometry and Gauge Equivariant Convolutions on Riemannian Manifolds
- Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin
- Theoretical Analysis of Inductive Biases in Deep Convolutional Networks
Related papers
- A Physics-Regulated Neural Framework for Learning 3D Grain Growth Dynamics
- FlexMoE: Learning One-for-All Multi-Budget Expert Pruning for Flexible MoE Deployment
- OptiMind: Improving Small Language Models for Optimization Modeling through Formulation Guidance and Multi-Turn Learning
- Staying in the Sweet Spot: Boost Reasoning Evolution via Responsive Rollout Difficulty Manipulation
- Examining the Impact of Data and Training Methods on Emergent and Subliminal Misalignment
- Rethinking Black-Box On-Policy Distillation: A Rubric-based Analysis