  We present a general approach to deriving bounds on the generalization error
of randomized learning algorithms. Our approach can be used to obtain bounds on
the average generalization error as well as bounds on its tail probabilities,
both for the case in which a new hypothesis is randomly generated every time
the algorithm is used - as often assumed in the probably approximately correct
(PAC)-Bayesian literature - and in the single-draw case, where the hypothesis
is extracted only once. For this last scenario, we present a novel bound that
is explicit in the central moments of the information density. The bound
reveals that the higher the order of the information density moment that can be
controlled, the milder the dependence of the generalization bound on the
desired confidence level. Furthermore, we use tools from binary hypothesis
testing to derive a second bound, which is explicit in the tail of the
information density. This bound confirms that a fast decay of the tail of the
information density yields a more favorable dependence of the generalization
bound on the confidence level.
