  We investigate a stochastic counterpart of majority votes over finite
ensembles of classifiers, and study its generalization properties. While our
approach holds for arbitrary distributions, we instantiate it with Dirichlet
distributions: this allows for a closed-form and differentiable expression for
the expected risk, which then turns the generalization bound into a tractable
training objective. The resulting stochastic majority vote learning algorithm
achieves state-of-the-art accuracy and benefits from (non-vacuous) tight
generalization bounds, in a series of numerical experiments when compared to
competing algorithms which also minimize PAC-Bayes objectives -- both with
uninformed (data-independent) and informed (data-dependent) priors.
