On Certified Generalization in Structured Prediction
This work addresses generalization bounds for discriminative tasks in structured prediction, such as image segmentation, but is incremental as it makes a preliminary step leveraging generative models.
The authors tackled the challenge of generalization in structured prediction, where output spaces are exponentially large and violate i.i.d. assumptions, by deriving a novel PAC-Bayesian risk bound that scales with both the number and size of structured examples, using a generative model assumption to distill dependencies into a Wasserstein matrix.
In structured prediction, target objects have rich internal structure which does not factorize into independent components and violates common i.i.d. assumptions. This challenge becomes apparent through the exponentially large output space in applications such as image segmentation or scene graph generation. We present a novel PAC-Bayesian risk bound for structured prediction wherein the rate of generalization scales not only with the number of structured examples but also with their size. The underlying assumption, conforming to ongoing research on generative models, is that data are generated by the Knothe-Rosenblatt rearrangement of a factorizing reference measure. This allows to explicitly distill the structure between random output variables into a Wasserstein dependency matrix. Our work makes a preliminary step towards leveraging powerful generative models to establish generalization bounds for discriminative downstream tasks in the challenging setting of structured prediction.