Timezone: »

 
Poster
Towards Sharper Generalization Bounds for Structured Prediction
Shaojie Li · Yong Liu

Fri Dec 10 08:30 AM -- 10:00 AM (PST) @
in Poster Session 8 »
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 $\mathcal{O}(\frac{1}{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 $\mathcal{O}(\frac{1}{\sqrt{n}})$. In each scenario, applications are provided to suggest that these conditions are easy to be satisfied.
Keywords: Theory · Graph Learning

Author Information

Shaojie Li (Renmin University of China)
Yong Liu (Renmin University of China)

More from the Same Authors