Still no free lunches: the price to pay for tighter PAC-Bayes bounds
  "No free lunch" results state the impossibility of obtaining meaningful
bounds on the error of a learning algorithm without prior assumptions and
modelling. Some models are expensive (strong assumptions, such as as
subgaussian tails), others are cheap (simply finite variance). As it is well
known, the more you pay, the more you get: in other words, the most expensive
models yield the more interesting bounds. Recent advances in robust statistics
have investigated procedures to obtain tight bounds while keeping the cost
minimal. The present paper explores and exhibits what the limits are for
obtaining tight PAC-Bayes bounds in a robust setting for cheap models,
addressing the question: is PAC-Bayes good value for money?
