# On Certified Generalization in Structured Prediction

arXiv: https://arxiv.org/abs/2306.09112 · HTML: https://mlsanity.com/paper/2306.09112/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 58 references that are in the map.
- First posted on arXiv 15 Jun 2023.

## Builds on (most cited first, 24 of 24)

- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Density estimation using Real NVP](https://mlsanity.com/paper/1605.08803/) (2016)
- [Normalizing Flows for Probabilistic Modeling and Inference](https://mlsanity.com/paper/1912.02762/) (2019)
- [Cascaded Diffusion Models for High Fidelity Image Generation](https://mlsanity.com/paper/2106.15282/) (2021)
- [NICE: Non-linear Independent Components Estimation](https://mlsanity.com/paper/1410.8516/) (2014)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [A Primer on PAC-Bayesian Learning](https://mlsanity.com/paper/1901.05353/) (2019)
- [Tighter risk certificates for neural networks](https://mlsanity.com/paper/2007.12911/) (2020)
- [An Introduction to Deep Generative Modeling](https://mlsanity.com/paper/2103.05180/) (2021)
- [Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priors](https://mlsanity.com/paper/1712.09376/) (2017)
- [Conditional Density Estimation with Bayesian Normalising Flows](https://mlsanity.com/paper/1802.04908/) (2018)
- [Simpler PAC-Bayesian Bounds for Hostile Data](https://mlsanity.com/paper/1610.07193/) (2016)
- [PAC-Bayes unleashed: generalisation bounds with unbounded losses](https://mlsanity.com/paper/2006.07279/) (2020)
- [From optimal transport to generative modeling: the VEGAN cookbook](https://mlsanity.com/paper/1705.07642/) (2017)
- [On the representation and learning of monotone triangular transport maps](https://mlsanity.com/paper/2009.10303/) (2020)
- [A General Framework for Consistent Structured Prediction with Implicit Loss Embeddings](https://mlsanity.com/paper/2002.05424/) (2020)
- [Learning PAC-Bayes Priors for Probabilistic Neural Networks](https://mlsanity.com/paper/2109.10304/) (2021)
- [GAN and VAE from an Optimal Transport Point of View](https://mlsanity.com/paper/1706.01807/) (2017)
- [Still no free lunches: the price to pay for tighter PAC-Bayes bounds](https://mlsanity.com/paper/1910.04460/) (2019)
- [Learning Graphical Model Parameters with Approximate Marginal Inference](https://mlsanity.com/paper/1301.3193/) (2013)
- [Conditionally Gaussian PAC-Bayes](https://mlsanity.com/paper/2110.11886/) (2021)
- [Localized Structured Prediction](https://mlsanity.com/paper/1806.02402/) (2018)
- [Self-Certifying Classification by Linearized Deep Assignment](https://mlsanity.com/paper/2201.11162/) (2022)
- [A PAC-Bayesian Perspective on Structured Prediction with Implicit Loss Embeddings](https://mlsanity.com/paper/2012.03780/) (2020)

## Abstract (arXiv)

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.