TowardsSharperGeneralizationBoundsfor StructuredPrediction

Specifically,inPAC-Bayesian approach, [45,26,4,22]provide the generalization bounds of order O( 1 n). In implicit embedding approach, [12, 13, 52, 11, 58, 7] provide the convergence rate of orderO( 1n1/4), and [53] of orderO( 1 n). In the factor graph decomposition approach, [18, 51] present the generalization upper bounds of orderO( 1 n).