De-randomized PAC-Bayes Margin Bounds: Applications to Non-convex and Non-smooth Predictors

Abstract

In spite of several notable efforts, explaining the generalization of deterministic non-smooth deep nets, e.g., ReLU-nets, has remained challenging. Existing approaches for deterministic non-smooth deep nets typically need to bound the Lipschitz constant of such deep nets but such bounds are quite large, may even increase with the training set size yielding vacuous generalization bounds. In this paper, we present a new family of de-randomized PAC-Bayes margin bounds for deterministic non-convex and non-smooth predictors, e.g., ReLU-nets. Unlike PAC-Bayes, which applies to Bayesian predictors, the de-randomized bounds apply to deterministic predictors like ReLU-nets. A specific instantiation of the bound depends on a trade-off between the (weighted) distance of the trained weights from the initialization and the effective curvature (`flatness') of the trained predictor. To get to these bounds, we first develop a de-randomization argument for non-convex but smooth predictors, e.g., linear deep networks (LDNs), which connects the performance of the deterministic predictor with a Bayesian predictor. We then consider non-smooth predictors which for any given input realized as a smooth predictor, e.g., ReLU-nets become some LDNs for any given input, but the realized smooth predictors can be different for different inputs. For such non-smooth predictors, we introduce a new PAC-Bayes analysis which takes advantage of the smoothness of the realized predictors, e.g., LDN, for a given input, and avoids dependency on the Lipschitz constant of the non-smooth predictor. After careful de-randomization, we get a bound for the deterministic non-smooth predictor. We also establish non-uniform sample complexity results based on such bounds. Finally, we present extensive empirical results of our bounds over changing training set size and randomness in labels.

References in corpus (17)

• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks
• Empirical Analysis of the Hessian of Over-Parametrized Neural Networks
• Sharp Minima Can Generalize For Deep Nets
• Uniform convergence may be unable to explain generalization in deep learning
• Eigenvalues of the Hessian in Deep Learning: Singularity and Beyond
• An Investigation into Neural Net Optimization via Hessian Eigenvalue Density
• Norm-Based Capacity Control in Neural Networks
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Sparse single-index model
• A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descent
• Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resilience
• The Full Spectrum of Deepnet Hessians at Scale: Dynamics with SGD Training and Sample Size
• Measurements of Three-Level Hierarchical Structure in the Outliers in the Spectrum of Deepnet Hessians
• Understanding Generalization and Optimization Performance of Deep CNNs
• Algorithm-Dependent Generalization Bounds for Overparameterized Deep Residual Networks
• Fast-rate PAC-Bayes Generalization Bounds via Shifted Rademacher Processes

Cited by in corpus (3)

• Generalization bounds for deep learning
• Generalisation under gradient descent via deterministic PAC-Bayes
• Risk Bounds for Learning via Hilbert Coresets