Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound
This work provides improved theoretical guarantees for SVM and other learning algorithms, which is significant for researchers in machine learning theory, though it is incremental in refining existing bounds.
The paper tackles the problem of deriving tighter generalization bounds for supervised learning algorithms by introducing stable sample compression schemes, and it proves a new optimal margin bound for SVM that removes a log factor, resolving a long-standing open question.
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.