# Initialization-Dependent Sample Complexity of Linear Predictors and Neural Networks

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 22 references that are in the map.
- First posted on arXiv 25 May 2023.

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

- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Gradient Descent Maximizes the Margin of Homogeneous Neural Networks](https://mlsanity.com/paper/1906.05890/) (2019)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (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)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [A vector-contraction inequality for Rademacher complexities](https://mlsanity.com/paper/1605.00251/) (2016)
- [On the Power of Over-parametrization in Neural Networks with Quadratic Activation](https://mlsanity.com/paper/1803.01206/) (2018)
- [Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back](https://mlsanity.com/paper/1608.04414/) (2016)
- [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)
- [Max-Margin Works while Large Margin Fails: Generalization without Uniform Convergence](https://mlsanity.com/paper/2206.07892/) (2022)
- [On the Sample Complexity of Two-Layer Networks: Lipschitz vs. Element-Wise Lipschitz Activation](https://mlsanity.com/paper/2211.09634/) (2022)

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

- [The Dimension Strikes Back with Gradients: Generalization of Gradient Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2401.12058/) (2024)
- [Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification](https://mlsanity.com/paper/2505.22359/) (2025)
- [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)

## Abstract (arXiv)

We provide several new results on the sample complexity of vector-valued linear predictors (parameterized by a matrix), and more generally neural networks. Focusing on size-independent bounds, where only the Frobenius norm distance of the parameters from some fixed reference matrix W0 is controlled, we show that the sample complexity behavior can be surprisingly different than what we may expect considering the well-studied setting of scalar-valued linear predictors. This also leads to new sample complexity bounds for feed-forward neural networks, tackling some open questions in the literature, and establishing a new convex linear prediction problem that is provably learnable without uniform convergence.