On Certified Generalization in Structured Prediction

Bastian Boll, Christoph Schnoerr

Introduction

In standard machine learning theory, the assumption that data points are independent and identically distributed (i.i.d.) is fundamental to deriving generalization bounds. However, in structured prediction tasks—such as image segmentation, scene graph generation, or natural language processing—this assumption is fundamentally flawed. In an image, a pixel's label is rarely independent of its neighbors; rather, it is part of a complex, interdependent structure.

Because the output space in these tasks is exponentially large, classical learning theories often suggest that an impractical amount of data is required to guarantee generalization. Yet, empirical evidence shows that models can learn effectively from relatively few examples. This paper bridges the gap between theory and practice by introducing a framework based on measure transport to model data dependencies, providing a PAC-Bayesian risk bound that scales with both the number of samples and the internal size of each sample.

The Measure Transport Framework

To move beyond the mathematical restrictions and computational intractability of traditional Markov Random Fields (MRFs), the authors propose using Measure Transport, specifically the Knothe-Rosenblatt (KR) rearrangement.

The KR rearrangement provides a way to transform a simple, independent distribution into a complex, structured one through a "triangular" map. In this construction, each variable in the structured distribution depends only on the variables that precede it in a specific ordering. This triangularity makes the underlying dependencies mathematically tractable without sacrificing the flexibility needed to represent complex real-world data distributions.

Quantifying Dependency: The Wasserstein Matrix

A central component of this framework is the Wasserstein Dependency Matrix. By analyzing the data through the lens of the KR rearrangement, the authors can quantify the influence of one part of the input (e.g., a specific pixel) on another. This matrix distills complex, non-linear dependencies into a structured format that can be used to calculate generalization guarantees.

To ensure these bounds remain tight, the authors introduce a "Bad Set" construction. This technique identifies and excludes specific inputs that exhibit extreme, non-local dependencies, allowing for a much stronger and more meaningful certificate of generalization on the remaining "good" data.

Certified Generalization Bounds

The core contribution of the research is a PAC-Bayesian risk certificate. Unlike standard bounds that only improve as the number of samples ($m$) increases, this bound also accounts for the size or dimensionality ($d$) of each sample.

Theorem 7: The Main Bound

The derived risk bound shows that the generalization gap—the difference between training error and true error—is proportional to:

$$\frac{\|D\delta\|_2}{d} \sqrt{\frac{\dots}{m}}$$

Where $D$ represents the dependency structure. In scenarios characterized by local dependency—where a variable only significantly affects a fixed number of its neighbors—the term $\|D\delta\|_2$ grows at a rate of $\sqrt{d}$. Consequently, the overall generalization gap shrinks at a rate of $1/\sqrt{d}$.

This result provides a formal proof for the intuition that "size is a substitute for quantity." In structured settings, a single, large, internally rich datum (such as a high-resolution satellite image) can provide sufficient statistical power to guarantee generalization, provided the dependencies within that datum are sufficiently local.

Discussion and Limitations

While this framework offers a promising path toward non-vacuous generalization bounds in deep learning, several challenges remain:

  1. Known Distribution Assumption: The current theory assumes the underlying data-generating process (the KR rearrangement) is known. In practice, this generative model must be learned, and it remains to be seen how errors in this learning process propagate to the final bound.
  2. Computational Complexity: Calculating the Lipschitz constants required for the dependency matrix is computationally intensive, potentially requiring quasi-Monte-Carlo methods for high-dimensional datasets.
  3. Empirical Validation: While the authors provide a numerical toy example in a 2D space to demonstrate the transport of measures and the calculation of the dependency matrix, the framework has yet to be applied to large-scale discriminative tasks like medical imaging or autonomous driving.

Conclusion

By shifting the focus from independent samples to the internal structure of data through measure transport, this work provides a new theoretical foundation for structured prediction. The insight that generalization can be certified through the "internal size" of data points offers a potential explanation for why modern deep learning models generalize well even when trained on datasets that classical theory would deem insufficient.

Summary updated

Abstract

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.
BibTeX
@inproceedings{boll2023certified,
  author = {Bastian Boll and Christoph Schnoerr},
  title = {{On Certified Generalization in Structured Prediction}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=s1jQ91yFAb},
}
Figure