# On the Sample Complexity of Two-Layer Networks: Lipschitz vs. Element-Wise Lipschitz Activation

arXiv: https://arxiv.org/abs/2211.09634 · HTML: https://mlsanity.com/paper/2211.09634/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 17 references that are in the map.
- First posted on arXiv 17 Nov 2022.

## Builds on (most cited first, 8 of 8)

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Deep Learning in Neural Networks: An Overview](https://mlsanity.com/paper/1404.7828/) (2014)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Generalization in Deep Networks: The Role of Distance from Initialization](https://mlsanity.com/paper/1901.01672/) (2019)
- [Generalization Bounds for Neural Networks via Approximate Description Length](https://mlsanity.com/paper/1910.05697/) (2019)
- [The Sample Complexity of One-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.06233/) (2022)

## Built on by (most cited first, 4 of 4)

- [Initialization-Dependent Sample Complexity of Linear Predictors and Neural Networks](https://mlsanity.com/paper/2305.16475/) (2023)
- [Complexity of Vector-valued Prediction: From Linear Models to Stochastic Convex Optimization](https://mlsanity.com/paper/2412.04274/) (2024)
- [Towards Initialization-dependent and Non-vacuous Generalization Bounds for Overparameterized Shallow Neural Networks](https://mlsanity.com/paper/2604.00505/) (2026)
- [Width-Robust Learnability in Mean-Field Bayesian Neural Networks](https://mlsanity.com/paper/2607.05735/) (2026)

## Abstract (arXiv)

We investigate the sample complexity of bounded two-layer neural networks using different activation functions. In particular, we consider the class  H = leftxmapsto langle v, σ circ Wb + b rangle : b∈ℝd, W ∈ ℝT× d, v ∈ ℝTright  where the spectral norm of W and v is bounded by O(1), the Frobenius norm of W is bounded from its initialization by R > 0, and σ is a Lipschitz activation function. We prove that if σ is element-wise, then the sample complexity of H has only logarithmic dependency in width and that this complexity is tight, up to logarithmic factors. We further show that the element-wise property of σ is essential for a logarithmic dependency bound in width, in the sense that there exist non-element-wise activation functions whose sample complexity is linear in width, for widths that can be up to exponential in the input dimension. For the upper bound, we use the recent approach for norm-based bounds named Approximate Description Length (ADL) by arXiv:1910.05697. We further develop new techniques and tools for this approach that will hopefully inspire future works.