On Certified Generalization in Structured Prediction

Summary

This paper proposes a PAC-Bayesian risk bound for the task of structured prediction. Under the assumption that the data is generated by Knothe-Rosenblatt rearrangement, this method distills random output variables into a Wasserstein dependency matrix, which paves the way for improved generalization bounds of generative models.

Strengths

1. The core method is based on the triangular measure transport and KR rearrangement of a tractable reference measure, which is novel and allows for flexible distillation. 2. The set of bad inputs is bounded so that the risk is more certificated. 3. The presented approach has the potential to compute risk certificates for many downstream discriminative tasks.

Weaknesses

1. My main concern is that the samples are drawn from a distribution arising from a reference measure through KR rearrangement. Can authors do some toy experiments of some popular generative models to support this assumption?

Questions

Please see the weaknesses and limitations

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

I had a rough check on the derivation and proofs, and they seem correct. My only concern is whether the assumption is valid in practice.

Summary

This paper establishes a new PAC-Bayesian risk bound for the structured prediction problem. Technically, it assumes the data are generated by the Knothe-Rosenblatt rearrangement of a factorizing reference measure, and then obtains generalization bounds with the Wasserstein dependency matrix.

Strengths

1. Different from the existing PAC-Bayesian bound with ϑ-mixing dependency matrix, this paper uses the Wasserstein dependency matrix to measure the interdependence of the data. Built upon the Wasserstein dependency matrix, novel concentration inequalities and general PAC-Bayesian risk bounds are established. 2. The Knothe-Rosenblatt rearrangement adopted in this paper is related to the measured transport and generative models, which may bring some insights into this field.

Weaknesses

1. The discussion on the existing work [1*] should be clarified. The authors argue that [1*] requires that data are generated by a Markov random field. However, their general PAC-Bayesian risk bounds (Section 5 in [1*]) do not need this assumption. The ϑ-mixing dependency matrix adopted by them exists for any distribution. [1*] only choose Markov random fields as special examples to concretely clarify the implications of their theoretical framework. Thus, PAC-Bayesian risk bounds in this paper may not be more general than that in [1*]. 2. There does not exist any theoretical example, simulation experiment, or real-world experiment in this paper. To show the superiority of the proposed framework, the authors should at least consider adding some concrete theoretical examples (e.g. Markov random field) in this paper. 3. The paper is not written very clearly. More descriptions and discussions can be added for the technical notions and definitions. For example, when I read this paper for the first time, some notions (e.g., Equation 7) confuse me, and I can not get intuitions of some definitions (e.g., Wasserstein dependency matrix). I will consider improving the score after you discuss my concerns. [1*] Ben London, Bert Huang, and Lise Getoor. Stability and generalization in structured prediction. JMLR 2016.

Questions

Please see the weaknesses comments.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

None.

Summary

This work derives a novel PAC-Baeysian risk bound for structured prediction based on generative models, a triangular and monotone transport and Wasserstein dependency matrices.

Strengths

This is technical a paper with rigorous theoretical analysis. The flow is easy to follow. The authors have made very detailed comparisons to [1], on which this work is largely based. Many examples such as image data are included to help readers understand some of the intuitions behind the derived theoretical results. [1] London, Ben, Bert Huang, and Lise Getoor. "Stability and generalization in structured prediction." The Journal of Machine Learning Research 17, no. 1 (2016): 7808-7859.

Weaknesses

There are no empirical results to showcase the tightness or usefulness of the risk bounds compared to bounds that ignore the size of the structure object. The assumptions are probably limited. See my comments on these points below.

Questions

I have a few minor concerns as follows: 1. In line 134, it is assumed that the structured loss is an additive, bounded and pointwise loss. This looks like the conclusion in this paper can only be generalized to affine losses. This assumption does not hold for, e.g., log loss, which goes to infinity, or F1 score, which is non-decomposable into components. So what family of losses can the risk bound generalize to? 2. The successful derivation of the risk bound in Theorem 7 is greatly thanks to, I believe, the introduction of the bad set. I appreciate the detailed explanations on the intuitions for this set. But in practice, how do you define bad and how can you identify those data points? As the authors suggest by themselves, one could use Equation 16 to decide on this but the Lipschitz constants $L_{ij}$ may not be easy to compute. 3. Does the learned measure transport distribution converge to the true underlying distribution asymptotically? If not, how close are they?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes, the authors have adequately discussed the limitations of their findings.

Summary

This paper develops a PAC-Bayesian bound on the risk of structured predictors which decreases with the number and size of examples. The work builds on concentration of measure results (e.g., [33]) and continues the line of work in [36] by removing the assumption that data are generated by a Markov Random Field (MRF). Instead, the present work assumes a triangular and monotone transport, a Knothe-Rosenblatt (KR) rearrangement of a reference measure, as the data model.

Strengths

**S1.** This theoretical work advances a series of works on bounding the risk of structured predictors via more recent concentration of measure results. **S2.** The submission does a great job at providing an overview of prior results and presenting new developments.

Weaknesses

**W1.** The theoretical results in this submission are presented with little connection to implications to practice. For example, L341-344 state that how closely a measure transport distribution learned from data approximates the actual (unknown) distribution of the data is an open question and thus, no empirical results are provided. I wonder if more could be said in this regard. As another example, in [36] bounds are applied to specific models. On one hand, the specifics of the model and training loss are taken into account. On the other hand, the PAC-Bayes bound is derandomized in order to apply it to a learned predictor. Are similar applications not possible for the results in the present submission? **W2.** One of the claims is that the present work “makes a preliminary step towards leveraging powerful generative models to establish generalization bounds for discriminative downstream tasks.” In my view, providing further insight into next steps in this direction would help other researchers build upon this work.

Questions

**Q1.** How are the theoretical results in this submission (perhaps given further development) to inform practice? **Q2.** In general, what would be possible progressions of developments building on this work? **Q3.** How does the restriction to atom-free data distributions limit relevance and applicability of the results in this submission, e.g., to discrete output spaces?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Limitations

Potential negative societal impact was not discussed.

Summary

This paper studies PAC-Bayesian risk bound for structured prediction using concentration of measure. Specifically, authors characterize stability and dependency with Wasserstein dependency matrix under the data assumption that data are given by Knothe-Rosenblatt (KR) rearrangement of a factorizing reference measure. PAC-Bayesian risk bound for structured prediction has been studied in the previous studies [1], [2] with different stability notions and the main contribution of this paper is to apply measure-theoretic stability notions from [3] to the problem and provide a new PAC Bayesian bound that scales with the number of examples and their dimensions. This result agrees with the PAC risk bound provided in [2] under specific conditions, giving a more generalized interpretation based on Wasserstein dependency matrix. [1] London, Ben, et al. "Collective stability in structured prediction: Generalization from one example." International Conference on Machine Learning. PMLR, 2013. [2] London, Ben, Bert Huang, and Lise Getoor. "Stability and generalization in structured prediction." The Journal of Machine Learning Research 17.1 (2016): 7808-7859. [3] Kontorovich, Aryeh, and Maxim Raginsky. "Concentration of measure without independence: a unified approach via the martingale method." Convexity and Concentration. Springer New York, 2017.

Strengths

1. New stability notion is considered for PAC bayes risk bound, providing additional analysis and interpretations up on previous works. 2. Provided examples and intuitions are helpful for readers to follow the manuscript. 3. KR rearrangement assumption on data is not that unrealistic, considering that generative models using KR rearrangement assumption have been studies recently, e.g. [4]. This entails the possibility of practical implications. [4] Irons, Nicholas J., et al. "Triangular flows for generative modeling: Statistical consistency, smoothness classes, and fast rates." International Conference on Artificial Intelligence and Statistics. PMLR, 2022.

Weaknesses

1. Definitions, notations, some lemma & theorem look pretty similar to ones in [3] --- authors may want to highlight the contribution of this paper by differentiating from [3] or giving more explanation. 2. More background on PAC Bayes risk bounds could be helpful for readers. Especially, it would be nicer if how stability and dependency affects PAC Bayes risk bounds can be discussed.

Questions

1) If measure space is discrete, can it be reduced to previously known PAC Bayes bounds? I am curious how measure-theoretic characterization can be connected with the previous results. 2) What's the intuition about "a bad set" --- is it the set possibly locally unstable? 3) Is there any possible simulation setup we can see the provided PAC Bayes bound works? 4) L151: What is $\delta_x$? --- confusion with $\delta_i$. $\delta$ is also overloaded in the probability $1-\delta$, authors may want to change the notation to reduce confusion.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

2 fair

Limitations

Limitations are properly discussed.

Thanks for thre response

Thanks for the response. The authors have provided a detailed explanation of KR rearrangement. My concerns have been addressed. I will keep my original score of 6.