  We introduce a modified version of the excess risk, which can be used to
obtain tighter, fast-rate PAC-Bayesian generalisation bounds. This modified
excess risk leverages information about the relative hardness of data examples
to reduce the variance of its empirical counterpart, tightening the bound. We
combine this with a new bound for $[-1, 1]$-valued (and potentially
non-independent) signed losses, which is more favourable when they empirically
have low variance around $0$. The primary new technical tool is a novel result
for sequences of interdependent random vectors which may be of independent
interest. We empirically evaluate these new bounds on a number of real-world
datasets.
