The Restricted Isometry of ReLU Networks: Generalization through Norm Concentration

Abstract

While regression tasks aim at interpolating a relation on the entire input space, they often have to be solved with a limited amount of training data. Still, if the hypothesis functions can be sketched well with the data, one can hope for identifying a generalizing model. In this work, we introduce with the Neural Restricted Isometry Property (NeuRIP) a uniform concentration event, in which all shallow $\mathrm{ReLU}$ networks are sketched with the same quality. To derive the sample complexity for achieving NeuRIP, we bound the covering numbers of the networks in the Sub-Gaussian metric and apply chaining techniques. In case of the NeuRIP event, we then provide bounds on the expected risk, which hold for networks in any sublevel set of the empirical risk. We conclude that all networks with sufficiently small empirical risk generalize uniformly.

arXiv comment27 pages, 5 figures

References in corpus (7)

• On the Number of Linear Regions of Deep Neural Networks
• The Loss Surfaces of Multilayer Networks
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Diverse Neural Network Learns True Target Functions
• Generic Error Bounds for the Generalized Lasso with Sub-Exponential Data
• The Mismatch Principle: The Generalized Lasso Under Large Model Uncertainties
• Empirical Risk Minimization in the Interpolating Regime with Application to Neural Network Learning