Complexity, Statistical Risk, and Metric Entropy of Deep Nets Using Total Path Variation

2019/02/02 by Andrew R. Barron, Barron, Andrew R., Jason M. Klusowski +1 · 2 citations
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #Graph theory and applications #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Stochastic Gradient Optimization Techniques #VLSI and FPGA Design Techniques

paper · pdf · doi:10.48550/arxiv.1902.00800

openalex publication_date 2019/02/02 · openalex created_date 2019/02/21 · openalex updated_date 2026/07/28

Abstract

For any ReLU network there is a representation in which the sum of the absolute values of the weights into each node is exactly 1, and the input layer variables are multiplied by a value V coinciding with the total variation of the path weights. Implications are given for Gaussian complexity, Rademacher complexity, statistical risk, and metric entropy, all of which are shown to be proportional to V. There is no dependence on the number of nodes per layer, except for the number of inputs d. For estimation with sub-Gaussian noise, the mean square generalization error bounds that can be obtained are of order V √(L + log d)/√(n), where L is the number of layers and n is the sample size.

Cited by

• Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets
• Non-Vacuous Generalization Bounds: Can Rescaling Invariances Help?

Related

• Approximation and Estimation for High-Dimensional Deep Learning Networks
• Global Capacity Measures for Deep ReLU Networks via Path Sampling
• Trajectory growth lower bounds for random sparse deep ReLU networks
• Theoretical Issues in Deep Networks: Approximation, Optimization and Generalization
• Adversarial Examples in Multi-Layer Random ReLU Networks