Sharper Bounds on the Metric Entropies of Margin Classifiers

Room A008

This talk deals with the characterization of the generalization performance of margin multi-category classifiers, addressed through the derivation of upper bounds on their capacity. The central measures of this capacity are metric entropies. The upper bounds on these measures provided by the literature are unsatisfactory, primarily because they do not handle efficiently the margin parameter. We establish new bounds based on a scale-sensitive combinatorial dimension dedicated to the classifiers of interest: the margin Natarajan dimension. They prove sharper than the state-of-the-art ones for the smallest values of the margin parameter.