PAC-Bayesian Transportation Bound
This work addresses a theoretical gap for researchers in statistical learning by providing a novel bound that handles deterministic predictors, though it appears incremental in extending existing PAC-Bayesian methods.
The paper tackles the limitation of PAC-Bayesian analysis, which only applies to stochastic predictors, by developing a new generalization error bound called the PAC-Bayesian transportation bound that unifies PAC-Bayesian analysis and chaining via optimal transport, enabling evaluation of de-randomization costs for predictors like neural networks.
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.