PAC-Bayesian Transportation Bound
  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.
