2020

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

Banerjee, Arindam, Chen, Tiancong, Zhou, Yingxue

Understand

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.

Built on

An Investigation into Neural Net Optimization via Hessian Eigenvalue Density
Original
B. Ghorbani, S. Krishnan, and Y. Xiao · 1901
Earlier work this paper cites.
Sulla determinazione empirica delle leggi di probabilita
F. P. Cantelli · 1933
Earlier work this paper cites.
Sulla determinazione empirica delle leggi di probabilita
V. Glivenko · 1933
Earlier work this paper cites.
On the uniform convergence of relative frequencies of events to their probabilities
V. Vapnik · 1968
Earlier work this paper cites.
On the density of families of sets
N. Sauer · 1972
Earlier work this paper cites.
A theory of the learnable
L. G. Valiant · 1984
Earlier work this paper cites.
Nonuniform learnability
G. Benedek and A. Itai · 1988
Earlier work this paper cites.
Learnability and the Vapnik-Chervonenkis dimension
A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth · 1989
Earlier work this paper cites.
Transforming neural-net output levels to probability distributions
J. S. Denker and Y. LeCun · 1991
Earlier work this paper cites.
A practical bayesian framework for backpropagation networks
D. J. MacKay · 1992
Earlier work this paper cites.
Principles of risk minimization for learning theory
V. Vapnik · 1992
Earlier work this paper cites.
Nonuniform learnability
G. Benedek and A. Itai · 1994
Earlier work this paper cites.
The weighted majority algorithm
N. Littlestone and M. Warmuth · 1994
Earlier work this paper cites.
Bounding the vapnik-chervonenkis dimension of concept classes parameterized by real numbers
P. W. Goldberg and M. R. Jerrum · 1995
Earlier work this paper cites.
Flat minima
S. Hochreiter and J. Schmidhuber · 1997
Earlier work this paper cites.
A PAC analysis of a Bayesian estimator
J. Shawe-Taylor and R. C. Williamson · 1997
Earlier work this paper cites.
Almost linear VC dimension bounds for piecewise polynomial networks
P. L. Bartlett, V. Maiorov, and R. Meir · 1999
Earlier work this paper cites.
An overview of statistical learning theory
V. N. Vapnik · 1999
Earlier work this paper cites.
Rademacher processes and bounding the risk of function learning
V. Koltchinskii and D. Panchenko · 2000
Earlier work this paper cites.
Bounds for averaging classifiers
J. Langford and M. Seeger · 2001
Earlier work this paper cites.
Rademacher and Gaussian complexities: Risk bounds and structural results
P. L. Bartlett and S. Mendelson · 2002
Earlier work this paper cites.
Concentration inequalities and empirical processes theory applied to the analysis of learning algorithms
O. Bousquet · 2002
Earlier work this paper cites.
Stability and generalization
O. Bousquet and A. Elisseeff · 2002
Earlier work this paper cites.
(Not) bounding the true error
J. Langford and R. Caruana · 2002
Earlier work this paper cites.
PAC-Bayesian generalisation error bounds for Gaussian process classification
M. Seeger · 2002
Earlier work this paper cites.
PAC-Bayes & margins
J. Langford and J. Shawe-Taylor · 2003
Earlier work this paper cites.
Simplified PAC-Bayesian margin bounds
D. McAllester · 2003
Earlier work this paper cites.
Local Rademacher complexities
P. L. Bartlett, O. Bousquet, S. Mendelson, et al · 2005
Earlier work this paper cites.

Similar

Theory of classification: A survey of some recent advances
S. Boucheron, O. Bousquet, and G. Lugosi · 2005
Cited alongside, same era.
Tutorial on practical prediction theory for classification
J. Langford · 2005
Cited alongside, same era.
On Bayesian bounds
A. Banerjee · 2006
Cited alongside, same era.
PAC-Bayesian supervised classification: the thermodynamics of statistical learning
O. Catoni · 2007
Cited alongside, same era.
PAC-Bayes bounds for the risk of the majority vote and the variance of the gibbs classifier
A. Lacasse, F. Laviolette, M. Marchand, P. Germain, and N. Usunier · 2007
Cited alongside, same era.
PAC-Bayesian learning of linear classifiers
P. Germain, A. Lacasse, F. Laviolette, and M. Marchand · 2009
Cited alongside, same era.
Learnability, Stability and Uniform Convergence
S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan · 2010
Cited alongside, same era.
Information theory and dynamical system predictability
R. Kleeman · 2011
Cited alongside, same era.
A tail inequality for quadratic forms of subgaussian random vectors
D. Hsu, S. Kakade, T. Zhang, et al · 2012
Cited alongside, same era.
PAC-Bayes bounds with data dependent priors
E. Parrado-Hernández, A. Ambroladze, J. Shawe-Taylor, and S. Sun · 2012
Cited alongside, same era.
Sparse single-index model
P. Alquier and G. Biau · 2013
Cited alongside, same era.
Concentration Inequalities: A Nonasymptotic Theory of Independence
S. Boucheron, G. Lugosi, and P. Massart · 2013
Cited alongside, same era.

Then

Exploring generalization in deep learning
B. Neyshabur, S. Bhojanapalli, D. McAllester, and N. Srebro · 2017
Later among the works it cites.
Empirical analysis of the Hessian of over-parametrized neural networks
Original
L. Sagun, U. Evci, V. U. Guney, Y. Dauphin, and L. Bottou · 2017
Later among the works it cites.
Understanding deep learning requires rethinking generalization
C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals · 2017
Later among the works it cites.
Stronger generalization bounds for deep nets via a compression approach
S. Arora, R. Ge, B. Neyshabur, and Y. Zhang · 2018
Later among the works it cites.
How many samples are needed to estimate a convolutional neural network?
S. S. Du, Y. Wang, X. Zhai, S. Balakrishnan, R. R. Salakhutdinov, and A. Singh · 2018
Later among the works it cites.
Size-independent sample complexity of neural networks
N. Golowich, A. Rakhlin, and O. Shamir · 2018
Later among the works it cites.
Implicit bias of gradient descent on linear convolutional networks
S. Gunasekar, J. D. Lee, D. Soudry, and N. Srebro · 2018
Later among the works it cites.
Deep linear networks with arbitrary loss: All local minima are global
T. Laurent and J. Brecht · 2018
Later among the works it cites.
On tighter generalization bound for deep neural networks: Cnns, resnets, and beyond
Original
X. Li, J. Lu, Z. Wang, J. Haupt, and T. Zhao · 2018
Later among the works it cites.
Foundations of machine learning
M. Mohri, A. Rostamizadeh, and A. Talwalkar · 2018
Later among the works it cites.
A PAC-Bayesian approach to spectrally-normalized margin bounds for neural networks
B. Neyshabur, S. Bhojanapalli, and N. Srebro · 2018
Later among the works it cites.
The Full Spectrum of Deepnet Hessians at Scale: Dynamics with SGD Training and Sample Size
Original
V. Papyan · 2018
Later among the works it cites.
A Bayesian perspective on generalization and stochastic gradient descent
S. L. Smith and Q. V. Le · 2018
Later among the works it cites.
The implicit bias of gradient descent on separable data
D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro · 2018
Later among the works it cites.
High-dimensional probability: An introduction with applications in data science , volume 47
R. Vershynin · 2018
Later among the works it cites.
Understanding generalization and optimization performance of deep CNNs
P. Zhou and J. Feng · 2018
Later among the works it cites.
Nearly-tight VC-dimension and Pseudodimension Bounds for Piecewise Linear Neural Networks
P. L. Bartlett, N. Harvey, C. Liaw, and A. Mehrabian · 2019
Later among the works it cites.
A generalization theory of gradient descent for learning over-parameterized deep ReLU networks
Original
Y. Cao and Q. Gu · 2019
Later among the works it cites.
Entropy-SGD: Biasing gradient descent into wide valleys
P. Chaudhari, A. Choromanska, S. Soatto, Y. LeCun, C. Baldassi, C. Borgs, J. Chayes, L. Sagun, and R. Zecchina · 2019
Later among the works it cites.
Gradient descent provably optimizes over-parameterized neural networks
S. S. Du, X. Zhai, B. Poczos, and A. Singh · 2019
Later among the works it cites.
Algorithm-dependent generalization bounds for overparameterized deep residual networks
S. Frei, Y. Cao, and Q. Gu · 2019
Later among the works it cites.
Wide neural networks of any depth evolve as linear models under gradient descent
J. Lee, L. Xiao, S. Schoenholz, Y. Bahri, R. Novak, J. Sohl-Dickstein, and J. Pennington · 2019
Later among the works it cites.
Size-free generalization bounds for convolutional neural networks
Original
P. M. Long and H. Sedghi · 2019
Later among the works it cites.
Measurements of three-level hierarchical structure in the outliers in the spectrum of deepnet Hessians
V. Papyan · 2019
Later among the works it cites.
Fast-rate PAC-Bayes generalization bounds via shifted Rademacher processes
J. Yang, S. Sun, and D. M. Roy · 2019
Later among the works it cites.
Hessian based analysis of SGD for deep nets: Dynamics and generalization
X. Li, Q. Gu, Y. Zhou, T. Chen, and A. Banerjee · 2020
Closest in time.
In defense of uniform convergence: Generalization via derandomization with an application to interpolating predictors
J. Negrea, G. K. Dziugaite, and D. M. Roy · 2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…