  In the PAC-Bayesian literature, the C-Bound refers to an insightful relation
between the risk of a majority vote classifier (under the zero-one loss) and
the first two moments of its margin (i.e., the expected margin and the voters'
diversity). Until now, learning algorithms developed in this framework minimize
the empirical version of the C-Bound, instead of explicit PAC-Bayesian
generalization bounds. In this paper, by directly optimizing PAC-Bayesian
guarantees on the C-Bound, we derive self-bounding majority vote learning
algorithms. Moreover, our algorithms based on gradient descent are scalable and
lead to accurate predictors paired with non-vacuous guarantees.
