PAC-Bayesian Transportation Bound

Abstract

Empirically, the PAC-Bayesian analysis is known to produce tight risk bounds for practical machine learning algorithms. However, in its naive form, it can only deal with stochastic predictors while such predictors are rarely used and deterministic predictors often performs well in practice. To fill this gap, we develop a new generalization error bound, the PAC-Bayesian transportation bound, unifying the PAC-Bayesian analysis and the chaining method in view of the optimal transportation. It is the first PAC-Bayesian bound that relates the risks of any two predictors according to their distance, and capable of evaluating the cost of de-randomization of stochastic predictors faced with continuous loss functions. As an example, we give an upper bound on the de-randomization cost of spectrally normalized neural networks (NNs) to evaluate how much randomness contributes to the generalization of NNs.

References in corpus (6)

• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Adding Gradient Noise Improves Learning for Very Deep Networks
• Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach
• Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
• Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resilience
• How much does your data exploration overfit? Controlling bias via information usage

Cited by in corpus (2)

• PAC-Bayes Bounds for Meta-learning with Data-Dependent Prior
• Generalisation under gradient descent via deterministic PAC-Bayes