Towards Sharper Generalization Bounds for Structured Prediction

In this paper, we investigate the generalization performance of structured prediction learning and obtain state-of-the-art generalization bounds. Our analysis is based on factor graph decomposition of structured prediction algorithms, and we present novel margin guarantees from three different perspectives: Lipschitz continuity, smoothness, and space capacity condition. In the Lipschitz continuity scenario, we improve the square-root dependency on the label set cardinality of existing bounds to a logarithmic dependence. In the smoothness scenario, we provide generalization bounds that are not only a logarithmic dependency on the label set cardinality but a faster convergence rate of order O(1/root n) on the sample size n. In the space capacity scenario, we obtain bounds that do not depend on the label set cardinality and have faster convergence rates than O(1/root n). In each scenario, applications are provided to suggest that these conditions are easy to be satisfied.