  We analyze a family of supervised learning algorithms based on sample
compression schemes that are stable, in the sense that removing points from the
training set which were not selected for the compression set does not alter the
resulting classifier. We use this technique to derive a variety of novel or
improved data-dependent generalization bounds for several learning algorithms.
In particular, we prove a new margin bound for SVM, removing a log factor. The
new bound is provably optimal. This resolves a long-standing open question
about the PAC margin bounds achievable by SVM.
