On Size-Independent Sample Complexity of ReLU Networks

Mark Sellke
6/3/2023
cs.LGstat.ML

No confident code implementation found for this paper.

Abstract

We study the sample complexity of learning ReLU neural networks from the point of view of generalization. Given norm constraints on the weight matrices, a common approach is to estimate the Rademacher complexity of the associated function class. Previously Golowich-Rakhlin-Shamir (2020) obtained a bound independent of the network size (scaling with a product of Frobenius norms) except for a factor of the square-root depth. We give a refinement which often has no explicit depth-dependence at all.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

On the Local Complexity of Linear Regions in Deep ReLU Networks

87% match2024

Approximation Error and Complexity Bounds for ReLU Networks on Low-Regular Function Spaces

86% match2024

Optimization dependent generalization bound for ReLU networks based on sensitivity in the tangent bundle

85% match2023

Norm-based Generalization Bounds for Compositionally Sparse Neural Networks

85% match2023

Training Neural Networks is NP-Hard in Fixed Dimension

84% match2023

Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy

84% match2023

Cite this paper

@article{sellke2023sizeindependent,
  title  = {On Size-Independent Sample Complexity of ReLU Networks},
  author = {Mark Sellke},
  year   = {2023},
  eprint = {2306.01992},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2306.01992v3}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2306.01992.svg)](https://codeofpaper.com/paper/2306.01992)

Discussion