On Certified Generalization in Structured Prediction
Authors: Bastian Boll
Christoph Schnoerr
Venue: NeurIPS 2023 poster (2023)
Keywords: Structured Prediction
PAC-Bayes
Concentration Inequalities
Statistical Learning Theory
Knothe-Rosenblatt Rearrangement

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.

On Certified Generalization in Structured Prediction
Bastian Boll
Christoph Schnörr
Image Pattern Analysis Group
Image & Pattern Analysis Group
Heidelherg University
Heidelberg University
bastian. bastian.boll@ivr uni saadheidebberg.de
schnoerrOmath uni meri-heidebberg.co
Abstract
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 applications such image segmentation novel PAC-Bayesian risk bound for structured prediction wherein the rate of gener- alization 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 generated by the Rooee--Rssenblat rearrangement of factorizing reference measure. This allows to explicitly distill the structure between random output variables into Wasserstein dependency matrix. Our work makes preliminary step towards leveraging powerful generative models to establish gener- alization bounds for discriminative downstream tasks in the challenging setting of structured prediction.
scene graph generation. We present
Introduction
1.1
Overview
Structured prediction is the task of predicting an output which itself contains internal structure. As an example, consider the problem of image segmentation. The output to be predicted is assignment of semantic classes to each image pixel. However, the segmentation problem is not merely pixelwise classification, because each pixel not independently assigned a semantic class. If two pixels adjacent in the image plane, it is more likely that they belong to the same class than to different ones. way to remedy this problem is to enumerate all possible segmentations of image and treat the problem as classification. However, the output space of this classification is now exponentially large. This exponential (in the number pixels) size of the output space indicates a much more difficult problem than the unstructured case of classification. In fact, it also presents an immediate challenge for any statistical learning theory which requires assumptions on the number of output classes [4
From a practical perspective, structured prediction problems present a challenge of label aquisition. For instance, dense manual segmentation of an image is significantly more labour intensive than manual classification. In turn, one would expect that pixelwise segmentation of an image contains much richer information be exploited in supervised learning. However, this is not represented in typical statistical learning theory which assumes all data to be independently drawn from the true underlying distribution. In the extreme case of only single structured example being available for training, these statistical learning theories can not make any meaningful statement on generalization.
Addressing this point in particular, 38 presents analysis of the dependency structure in the output and proves a risk certificate which decays in both the number of structured examples m and their size d. Refering back to the example of image segmentation, this amounts the fraction of misslabeled pixels which decays with the number of labeled pixels observed during training opposed merely the number of segmented images.
high-probability bound on
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

At the core of statistical learning theory lies the concentration of measure phenomenon which posits that a stable function of a large number of weakly dependent random variables will take values close This is relevant because model risk, the expected loss on unseen data, is the mean of empirical risk under the draw of the sample. Learning theories can thus be built on concentration of measure results. In the present work, we focus on PAC-Bayesian learning theory [51 42 For an overview of PAC- AaC-Bayesian theory we refer to 13 27
to its mean 37 9
In addition to a concentration result such as a moment-generating function (MGF) bound, PAC- Bayesian arguments employ change of measure, typically via Donsker and Varadhan's 's variational formula. In particular, stochastic predictors, i.e. distributions over hypothesis class of models are considered. A core objective to construct generalization bounds which hold uniformly over all stochastic predictors called PAC-Bayes posteriors. Model complexity is then measured as relative entropy to a reference stochastic predictor called PPC-Bayes, prior. As this terminology alludes to, the PAC-Bayes posterior is informed by more data than the PAC-Bayes prior. Note however, that PAC- CaC-Bayesian theory generalizes Bayesian theory because prior and posterior are not typically connected via likelihood.
PAC-Bayesian theory has gained considerable attention in recent years due the demonstration of non-vacuous risk certificates in deep learning [23] Since then, a line of research has succeeded in
tightening the risk bounds of deep classifiers [8 47 [6]. addition, multiple authors have studied
ways to weaken underlying assumptions of bounded loss
[29 28
and i..d. data [].
The majority of recent works in this field focuses on classification or regression. Structured prediction has received comparatively little recent attention, an exception being the work [1]] which provides a PAC-Bayesian perspective the implicit loss embedding framework for structured prediction [15]
1.2
Related Work
Here, we continue a line of research started by [39 40 38 which aims to construct PAC-Bayesil risk bounds for structured prediction that account for generalization from a single (but large) structured datum. Instrumental their analysis is the stability of inference and quantified dependence in the data distribution. The latter is expressed in terms of s--ixxig coefficients, the total variation distance between data distributions conditioned on fixed values of subset of variables. For structured prediction with Hamming loss, a coupling of such conditional measures can be constructed [24] such that 9-mixing coefficients yield upper-bound bound that allows to invoke concentration of measure arguments (36). The result is an MGF bound which the authors employ in a subsequent PAC-Bayesian construction achieving generalization from single datum.
The underlying assumption of these previous works is that data are generated by a Markov random field (MRF). This model assumption is somewhat limiting because Markov properties, certain conditional independences. likely do not hold for many real-world data distributions. In addition, MRFs are difficult to work with computationally. Exact inference in MRFs is NP-hard [57] and thus lcarning, which often contains inference as a subproblem, presents significant computational roadblocks. Even once MRF has been found which represents data reasonably well, numerical evaluation of the PAC-Bayesian risk certificate proposed in 38 will again be computationally difficult.
Nevertheless, we share the sentiment of previous authors that some assumption on the data-generating process is required in structured prediction. This is because conditional data distributions, the distribution of data conditioned on a fixed set of values for a subset of variables, are central to establishing concentration of measure via the martingale method [35). Consider again the example of image segmentation. Once we have fixed a sufficiently large number of pixels to arbitrary values (and class labels), even large dataset will not contain an abundance of data which match these values and thus provide statistical power to learn the conditional distribution. This problem is well-known in conditional density estimation [56]
1.3 Contribution, Organization
In this work, we propose to instead assume triangular and monotone transport, Knothe-Rosenbles
(KR) rearrangement 32 40 41 of reference measure as data model. This choice is attractive for multiple reasons. First, any data distribution which does not contain atoms can be represented

---

uniquely in this way [6] which should suffice to represent many distributions of practical interest. With regard conditional distributions, the KR-rearrangement has the convenient property that conditioning on fixed value for a subset of variables can again be represented by KRrrearrangement. We will use this property in our construction of coupling measures between conditional distributions. Specifically,
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.
Based on data generated by KK-rearrangement of a tractable reference measure, we distill relevant structure of the data distribution into a Wasserstein dependency matrix. Our analysis hinges on state-of- of-the-art results in concentration theory [35] which serve to bound moment- generating functions by properties of the Wasserstein dependency matrix. We subsequently invoke a PAC-Bayesian argument to derive the desired risk certificate.
We also propose to leverage construction of bad input data as computational tool to find entries of the Wasserstein dependency matrix.
We stress the fact that many established approaches to generative modelling can be seen as instances
of measure transport. For instance, it includes normalizing flows [54 [3
33
46
50 diffusion
models [52] 30). generative adversarial networks and variational autoencoders TO 26 While most
measure transport models which currently enjoy empirical success are PRrraarrangem,tss we hope that the methods presented here can lay the foundation of leveraging powerful generative models to build risk certificates for discriminative downstream tasks.
Organization The central concepts of concentration theory and measure transport are described in the preliminary Sections 2 and 3 The main results are presented in Section 4 In Section 5 we present a first discussion of computational aspects related to the presented framework. The paper closes discussion of limitations in Section G and a conclusion in Section 7
Basic Notation For any d E N, denote [d] = {I.....,d] .d. If E 2d is a vector, we refer to the subvector of entries with index in set I C [d] as z In particular, index sets of interest will be half-open and closed intervals (i, d] S [d] and [ d] S [d]. Analogously, we will index the output of vector-valued functions f and marginal measures /rt For a set B C zd, we denote its complement in 2 by B 2d B and for measure μ on 2d we denote the conditional measure given 1 as 11 If Z is random variable with distribution 1a 2d and J.J C [d]] are disjoint index sets with TUJ J = [d]. we denote the conditional law of 2 given 7 2 as 1=d2
Concentration of Measure and Generalization
Let X' denote an input space and y denote an output space. Let μu be a distribution on z' (X' x y)d There are two restrictions inherent to this setup. First, input is always paired with output and thus the number of inputs needs to match the number of outputs. Second, all structured data will be drawn from fa and thus the size of each structured datum will be the same. Otherwise, X' and y can in principle be arbitrary sets which admit metrics. For concreteness, think of X' [0, [1] C IR as being of gray values and y = R containing signed distances from semantic boundary 45 in an image with d pixels. In this case, zd contains all binary segmentations of grayvalue images.
The goal of learning is to find parameters 0 which define predictor Φu: d + yrd such that the risk
R(0)= = ((xx))
with respect to some loss function L: ydd x yrd + R is minimized. However, the true risk |I typically intractable because μ is unknown. related tractable quantity is the empirical risk
is
Rm (0, Dm)) = 1 Σ ((((((()), y(0)
(2)
m kc(m)
3

---

of sample D.. = (X)()), y()) drawn from pmm. We further assume that the loss of structured outputs is the mean of bounded pointwise loss e: y x y + [0, 1]
1 d
Σ ie/d
()) (K)) D4
In PAC-Bayesian constructions, we consider stochastic predictors Ç. i.e. measures on a hypothesis space 7. of predictors Φo x + )d as identified with measures on the underlying parameter space from which 0 is selected. We then take the above notions of risk and empirical risk in expectation over parameter draws
R(C) = (R)))
R.m (C, Dm,) Ey~c RRm (0, Dm))]-
The expected value of empirical risk with respect to the sample is the true risk. For this reason, central tool for the study of generalization is the concentration of measure phenomenon. Informally, it states that stable function of many weakly dependent random variables concentrates on its mean. We will invoke line of reasoning put forward (35 and propose novel approach to structured prediction based on the measure-transport framework outlined in Section [ To this end, we first define the following formal notions of stability and dependence.
Let be metric such that Z has finite diameter
||lll
P(E,E') oo E.''Ez
sup
(5)
and let 2=(2,2)) = Eie(d p(z,, 2 denote the corresponding product metric on Zd
Definition (Local oscillation). Let f: 2d + R be Lipschitz with respect p². Then the quantities
[f(=) f(=)))(=)))
6.(
sup
i E [d]
p(z;,2))
2.2/ (aac" F
are called the local oscillations of f-
The vector local oscillations gives a granular account of stability. In order to discuss interdepen- dence of data probability space (z p, 2.), define the Markov kernels
K (2, dw) -git-11 (dw 11) pli (dw
i [d]
as well as k(d+1) (1, dw) = 82 (dw) and their action on functions
k 0 f(=) / (1)) dw) = / (( ) d (dw
(8)
where in the edge case 1, the condition on 2(t-1] 20 is removed. Here (700 dw) is Borel measure for every z and (8) computes the expected value of f at z, conditioned on the fixed realization of the subvector 2 turns out that the effect of the kernel (7) on local oscillations
serves to quantify dependence of data with joint distribution μ.
Definition (Wasserstein matrix). For E (d + 1), let K00 denote the Markov kernel (i) E IR d'xd is called Wasserstein matrix (25) for K6,, if
8 matrix
20
(x (1) S Σ
V 1,(f)
Vkeld
JE(4
for any function f: gd which is Lipschitz with respect to p².
The two concepts defined above will be used Section construct moment-generating function bound via the martingale method.

---

3 Triangular Measure Transport
Suppose a structured output is composed of > O unstructured data in space 2. Then the target measure of interest is measure on 2d which does not factorize into simpler distributions. A popular method of representing complex joint distributions interdependent random variables is to define a map T: 2d + 2d which transports tractable factorizing reference measure bd the target measure
J4, i.e. T,vá 14. This abstract framework encompasses many generative models such as normalizing
flows [54]] 53
33
46
50], diffusion models (52) 30], generative adversarial networks and variational
autoencoders 10
26 Here, we focus on transport maps 7 which are monotone and triangular in
the sense that T(2); only depends on the inputs 2 and each [(2(i-1] 11, -); is an increasing function.
49 12 41. both va and have no atoms then the KR rearrangement exists and is unique 66 In particular, normal distribution / and any absolutely continuous (with respect to the Lebesgue measure) distribution μ meet these criteria. The KR rearrangement has the useful property that certain conditional distributions have simple representation.
Such map called a Knothe-Rosenblltt (KR) rearrangement [32
Lemma (Lemma of [41]. Let zd + zd be the KR-rearrangemen which satisfies Tzydd μ.. For arbitrary E [d]. let 200 E Z' be fixed. Then
u(dwltid) |21b)) = (id (z ))
(10)
where z is the unique element of z such that Ti = =
Numerical realization of KR rearrangements has recently received attention [5] and more broadly, variety of triangular transport architectures exists 20]211 However, we do not focus on numerical
considerations in the present theoretical work.
One may wonder if data generated by (R-rearrangement implicitly restricts the choice of possible input and output spaces since the monotonicity requirement on 7 can only be satisfied if the underlying set 2 ordered. However, many feature spaces of practical interest are still permissible for what follows. In particular, both X' and Y' may be Euclidean spaces hypercubes. Inkeeping with the introductory image segmentation example, suppose X' [0, 1]s contains RGB color values and )' [-1, i] contains signed distance from semantic boundary in the image plane. Then we can interpret 2 ((0, 1 x [-1, 1))d as product of compact intervals in R4d which is clearly permissible as underlying space for eeareaarangemmnt All presented results hold irrespective of whether 2 contains such internal dimensions as long natural ordering of the set 2 is induced.
PAC-Bayesian Risk Certificate
In this section we present a novel PAC-Bayesian risk bound for structured prediction which combines three main ingredients.
(1) A concentration of measure theorem for dependent data (Theorem 4 which builds on the notion of a Wasserstein dependency matrix;
(2) simple construction of coupling measures between conditional distributions (Lemma 5 which serves to represent the Wasserstein dependency matrix;
(3) PAC-Bayesian argument (Theorem 7 employing Saasker-arrahan''s variational formula in concert with concentration of measure results.
The first theorem summarizes key results from [55] on the concentration of measure phenomenon for dependent random variables. We have slightly generalized by augmenting the underlying Doob martingale construction with the inclusion of 5 of bad inputs. For inputs in this set, data stability requirements do not necessarily hold. We call the complement B = z B the set of good inputs. The concept of good and bad inputs as well as related proof techniques were originally proposed by
38
Here, we incorporate them into the more general concentration of measure formalism of [35 full proof of the following theorem deferred to Appendix A
Theorem 4 geneeanggen function (MGF) bound for good inputs). Let C 2d be
measurable set of bad inputs. Suppose for each i E [d + 1), ( is Wasserstein matrix for the
5

---

Markov kernel K defined in 7 on the set of good inputs, that is
o (k(K()) f)
VKg 8f()),
(1)
Ak [d]
(11)
JE(d
for all Lipschitz (with respect to p² funcciinnss
f: B + R. Define the Wasserstein dependency matrix E Raxd
I |
(12)
Then for all
f: 2d + R. the following MGF bound holds
( X²
BE
(exp
S <exp -)) (T8(DI1))
(13)
An upper bound on the moment generating function will be used in the PAC-Bayesian argument concluding this section. The function f in question will be the loss of structured datum z. Regarding (13), our goal is to bound the norm [[ through properties of the data distribution. We will use the fact that data is represented by measure transport establish such bound after the following preparatory lemma.
Lemma (Coupling from transport). Let be reference measure on 2d and F, G: 2d + zd be measurable maps. Define the map (F, G) by
GF, 2d - 2d 2d, Then (F, G) is a coupling of Fir and Gira.
= (F()),
(14)
Proof. Let A C zd be measurable, then
(F, (F, (A, 2d) ((F,
((F = (A)
(15)
which shows that FA is the first marginal of (F, G), An analogous argument for the second marginal shows the assertion.
By assuming μi to be represented via KR-rearrangement of a factorizing reference measure, Lemmal gives explicit representation of KRrrearrangemeet for conditional distributions. From there, invoke Lemma 5 to construct a coupling between conditional distributions and subsequently follow a line of reasoning put forward in [35] to explicitly construct Wasserstein matrices for the kernels (7)
which yield a bound on (13) by Theorem 4
This leads to the following proposition. A full proof is
deferred Appendix A
Proposition 6 (Wasserstein dependency matrix from KR-rearrangement), Let (Z", ,E, (1) be probability space with p= -TT for the AR-rearrangement T: 2d - 2d and a reference measure yd on 2d, Let each Z be equipped with a metric p and have finite diameter ||p|| < oc. Let s: 2d TR sipschitz.uncctio function with respect to the product metric pa Let B z" denote set of bad inputs be a Lipschitz
and define the corresponding set A == T- (BB) S zd. Let T be the unique KR-rearrangement that satisfies Trud= = AA and denote T = T T. Suppose there exist constants Lig such that for all v, E B with uldltss = =!dM/i it holds
B (p(T T)2 To4 (2 r),}] S Lisp(U;, 21)
(16)
where 7l and g00 are uniquely defined through Tit (bli) = ol and (2) = 200) Then =
lell D is Wasserstein dependency matrix for pl BB with d
ifi
Dij =
ifi=j,
(17)
Lij i
We remark that I' indeed distills the dependency structure of μ. To illustrate this, let n() be independent from μdú)t for some E [d]. j E (i. d]. Then conditioning different value of v() does not change the distribution μ(()) Thus,
(i.d (1 ,)5 (( (z(t), T) and the choice Laj = satisfies (6). It directly follows that Tıj = 0.
V 2(,,) _4400 =4M0, jE (i. (18)
The following theorem states the main result of the present work.

---

Theorem 7 (PAC-Bayesian risk certificate for structured prediction). Fix ò E (0, (x,exp(-e-)) )), let I be a data distribution on 2d with T, = the Knothe-Rosenblan rearrangement for a reference measure v on z and fix a measurable set B S 2d of bad inputs with μ(B) S &. Fix a PAC-Bayes prior т on a hypothesis class H. of functions o: X - yd and a loss function E which assumes values in [0, 1). Define the oscillation vector 5 by
8 sup 8, (L(h, (L(b,)))oc). Bc); e NEH
(19)
where L(h, denotes the restriction of L(h..)) 2d N, B. Suppose all oscillations ö, are finite, suppose the condition (16) is satisfied and denote by D the matrix with entries (17). Then, with
probability least 1 over realizations of a training set D,n. - (Z yk= drawn drownfrrm (n)BBeym
holds for all PAC-Bayes posteriors ( on H that
R(C) & (m, Dm) - 2 !lell
log 1 + KL[C T]
d |188lay
+
(20)
2m
Note that the generalization gap on the right hand side of (0pp decays with d. This accounts for generalization from a single example. In fact, if only m = structured example is available, but
d >>>>>>>>>> 1, Theorem 7 still certifies risk. This effect can however be negated by the norm D If structured data contain strong global dependence, then |D will not be bounded independently of d and thus, in the worst case of || |6] E (d)) the assertion is no stronger than PAC- PAC-Bayesian bounds for unstructured data. The same point was observed in 38
The measure of the bad set under the data distribution j is assumed to be bounded by g. This is to account for small number of data which contain strong dependence. In order to prevent these bad data from dominating D, thereby negating the decay of the bound in d as described above, is preferable to exclude them from the sample, reduce the sample size m and pay the penalty & in (20).
To prove Theorem 7 we broadly follow the argument put forward in (38) This augments typical PAC-Bayesing constructions in the literature by the inclusion of a set of bad inputs. We first reconcile the data being conditioned on B with risk certification for unconditioned data, leading the addition of & on the right hand side of (20). The model complexity term KL[( œ] is due to Donsker and Varadhand's 's variational formula. Subsequently, the moment generating function bound of Theorem is instantiated through the Wasserstein dependency matrix constructed in Proposition [ Markov s inequality then gives pointwise risk bound for fixed value of a free parameter. In order to optimize this parameter, the bound is made uniform on discrete set of values through union bound. A full proof presented Appendix A
In Theorem we combine the PAC-Bayesian construction of 38 with the more general concentration
of measure theory of (35). Crucially, concentration of measure results used in (38) are predicated on the assumption of data generated by a Markov random field (57 34 Our work is more flexible in two major ways.
(1) Our assumption on the data-generating distribution is likely more representative of world data as measure transport models have repeatedly been shown to yield convincing data generators.
(2) Markov random fields are difficult handle computationally because inference in general Markov random fields is NP-hard [57] such that one is forced to learn based on approximate inference
procedures 31 22 55].
Our work also allows for more general metrics as opposed to the singular choice of Hamming norm required in [38). Additionally, the key results of (38] are constructed to ensure all data drawn from the unconditioned distribution are in the good set. This reduces the probability of correctness 1 by mg. Instead, we assume data drawn from ju BB, effectively reducing the number of available samples by factor of &. but keeping the probability of correctness high. This allows the set of bad inputs to be used more effectively as computational tool in Section
Comparing the dependency of (20) on d with the respective result in [38]. it first appears as though our bound decays with a faster rate (d instead of Vd). However, this will not typically be the case in practice because |D88l2 grows with rate vd in most situations. To this, consider the case of local
7

---

dependency in the sense that
1,
Lij
(21)
O, else
for local neighborhoods Ms S [d] which contain a fixed number of e celements and let 5; = a for all i [d] and some constant value > 0. Then
D
(aINi1)² = cavd.
(22)
EEId
Clearly, dependence is localized and the oscillations do not decay in d, then |o contains a factor that grows with rate vd, leading to the same asymptotic rate of (20 already observed in [38]
Note that 38 additionally allows for set of bad hypotheses By H. which do not conform to stability assumptions. our construction, this means restricting the bound (19) to oscillations on the set of good hypotheses. We omit this extension for clarity of exposition, but do not expect it to necessitate major changes to the presented proofs. The same applies to the derandomization strategy proposed by (38 which is based on hypothesis stability.
Further, considers large number of applicable orderings for random variables by introducing filtration of their index set. This notion is not easily compatible with our assumption of KR- rearrangement, because triangularity of transport depends on the order of variables.
Bounding the Bad Set
With regard to numerical risk certificates, a key technical aspect of Section 4 concerns the quantities Lij in (16). Here, we propose way to use the set of bad inputs as computational tool this end. Suppose we assign arbitrary fixed values to Lij and subsequently define B S 2d as the set of inputs on which the condition (16) fails. Then we have fulfilled the prerequisites of Proposition 6 by construction and are left with bounding (BB). Note that
p(B) = Pzz Z E B) Ez u [12 B}]
(23)
and the indicator function assumes values in the bounded set {0, 1}. Therefore, Hoeffding's inequality gives the following.
Proposition 8 (Upper bound on the bad set). Let be data distribution and let D,, pm be sample of size n. Fix an error probability e E (0, 1). Then
n(B)= S TO
Σ E [
log
(24)
2n
ZED.
with probability at least over the sample.
Checking the condition Z E 8 requires evaluating 16 which comes down to finding Lipschitz constant for a one-dimensional function. this computationally feasible for the given data model, then the concentration argument (24 can be used to bound μ(B) with high probability. Because (24) decays only in the number of structured examples (V) it can not be used to show generalization from single structured example. However, PAC- AAC-Bayesian risk certificates are typically dominated by the KL complexity term in (20) which decays with the size of structured examples as well. Thus, Proposition
should should still be useful in practice.
Note that Proposition & makes a pointwise statement about fixed value of L,j which has limited utility for learning Lij from data. To remedy this problem, we can first define discrete set L ( of candidate matrices and select error probabilities EK for each of the events
2
( 2
Σ 11 B(L ZED
log
(25)
2n
EN
such that ΣkEN E = c. Then, by union bound with probability at least - e over the sample none of the events (55) occurs. We have thus constructed uniform bound over the set of candidate matrices which allows to select the one which minimizes the generalization gap in 20
8

---

In order to make this strategy most effictive, domain knowledge on the application at hand should be applied when constructing candidate matrices and assigning error probabilities. For instance, the limited empirical findings of [14] on ImageNet [7] indicate that the majority of natural images contain mostly local signal. image segmentation, this is conducive to concentration, because can lead to many small values in an optimal Wasserstein dependency matrix. In particular, if dependency decays with distance in the image domain, one should select configurations (() in which ( is small if is distant from j in the image domain and allowed to assume larger values if i is close to in the image domain.
We give an intuitive interpretation of the relationship between Proposition g and Theorem 7 as follows. Suppose the majority of samples from a structured data distribution contain mostly local signal. The locality of signal in samples indicates weak global dependence of random variables which in turn manifests in small entries of a Wasserstein dependency matrix. However, small number of bad data may contain only weak local signal. For instance, an image in which every pixel has learner if it is doubled in size. Even worse,
the same value does not give more information small (but not null) set of bad data will dominate the Wasserstein dependency matrix and prevent generalization that scales with d. Proposition 8 thus estimates an upper bound on the likelihood of bad data under which are then excluded from the concentration argument underlying the bound (20.. This relationship is further illustrated numerical toy example in Appendix
6 Limitations
We assume that structured data are drawn from a distribution μ which arises from a reference measure through KR-rrarrangemeett This is motivated by the fact that large class of data distributions can be represented in this way and that some assumption on the date-gener distribution is required in order to make statements on conditional distributions required to quantify dependence. However, it is an open question how closely measure transport distribution learned from data approximates the unknown distribution from which the data are drawn. A first step towards this goal is made in the recent work [4), but a non-asymptotic theory of generalization for generative models left for future work. Accordingly, we do not present any empirical results on real-world data.
We describe how dependency in the data distribution which is relevant for generalization of dis- criminative models can be written as properties of the Xe-rearrangement through a Wasserstein dependency matrix. Section 5 further outlines how the construction of bad data can be used a computational tool to this end. We do not cover how to compute the involved Lipschitz constants Lij in (6).. In practice, this will require nontrivial numerical machinery because deterministic bound on the expected value under the reference distribution appears needed. One possible approach Munsi-Monte-CCe
methods [1]]8]] [8] which come with deterministic error bounds and have recently been applied to PAC-Bayesian certification of ordinary (non-structured) classification risk 77). This entails a fine-grained stability analysis of the involved integrands and likely to be computationally expensive because deterministic error bounds tend to be pessimistic compared to their stochastic counterparts.
to employ
7 Conclusion
We have presented a PAC-Bayesian risk certificate for structured prediction. Compared to earlier work, we make the assumption of data generated by Kerrearrangemmet of a reference measure. This approach is able to represent all atom-free data distributions and yields an explicit quantification of dependence via Wasserstein dependency matrices. It also indicates way of leveraging powerful generative models to compute risk certificates for downstream discriminative tasks.
Acknowledgments and Disclosure of Funding
This work is funded by the Deutsche Forschungsgemminnchaatt (DFG), grant SCHN 457/17-1, within the priority programme SPP 2298: "Theoretical Foundations of Deep Learning". This work is funded by the Deutsche Forschungsgemeinschattt (DFG) under Germany's Excellence Strategy EXC-2181/1 390900948 (the Heidelberg STRUCTURES Excellence Cluster).

---

References
[1] Pierre Alquier. User-friendly introduction pac-bayes bounds.
arXiv preprint
arXiv:2110.1222 1/216,,, 2021.
[2] Pierre Alquier. User-friendly introduction to pac-bayes bounds, 2023,
[3] Pierre Alquier and Benjamin Guedj. Simpler pac-bayesian bounds for hostile data. Machine Learning, (07(5))887-902) 2018.
[4] Ricardo Baptista, Bamdad Hosseini, Nikola B Kovachki, Youssef M Marzouk, and Amir Sagiv,
An approximation theory framework for measure-transport sampling algorithms. arXiv preprint arXiv:2302. 13965, 2023.
[5] Ricardo Baptista, Youssef Marzouk, and Olivier Zahm. On the representation and learning of monotone triangular transport maps, July 2022. arXiv:2009. 10300 [es, math, stat].
[6] V I Bogachev, A V Kolesnikov, and K V Medvedev. Triangular transformations of measures. Sbornik:
Mathematics, 196(3):309, apr 2005.
[7] B. Boll, A. Zeilmann, S. Petra, and C. Schnörr. Self-Certifying Classification by Linearized Deep Assignment. PAMM: Proc. Appl. Math. Mech., 23(1):202220119) 2023.
[8] N. Bonnotte. From Knothe's ' Rearrangement to Brenier's Optimal Transport Map. SIAM J. Math. Anal., 45(1):64 87, 2013.
[9] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, February 2013.
[10] O. Bousquet, S. Gelly, Tolstikhin, C.-J Simon-Gabriel, and Schölkopf. From optimal transport to generative modeling: the VEGAN cookbook. preprint arXiv: 705.07642, 2017.
[11] Théophile Cantelobre, Benjamin Guedj, María Pérez-Ortiz, and John ShaworTaylor, A pac- bayesian perspective on structured prediction with implicit loss embeddings. arXiv preprint arXiv:2012.03378, 2020.
[12] G. Carlier, A. Galichon, and Santambrogio. From Knothe's Transport to Brenier's Map and Continuation Method for Optimal Transport. SIAM Journal Mathematical Analysis, 2156)22554 2010.
[13] O. Catoni. PAC-Bayesian Supervised Classification: The Thermodynamies of Statistical Learn- ing. Institute of Mathematical Statistics, 2007.
[14] Carlo Ciliberto, Francis Bach, and Alessandro Rudi. Localized Structured Prediction. In
H. Wallach, H. Larochelle, A. Beygelzimer. d' Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[15] Carlo Ciliberto, Lorenzo Rosasco, and Alessandro Rudi. general framework for consistent structured prediction with implicit loss embeddings. The Journal of Machine Learning Research, 21(1):3852-391 2020.
[16] Eugenio Clerico, George Deligiannidis. and Arnaud Doucet. Conditionally gaussian pac-bayes bayes. In International Conference on Artificial Intelligence and Statistics, pages 231 2311-2329. PMLR, 2022.
[17] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248-255. IEEE, 2009.
[18] Josef Dick, Frances Y Kuo, and Ian H Sloan. High-dimensional integration: the quasi-monte carlo way. Acta Numerica, 22: 133-88888 2013.
[19] Josef Dick and Friedrich Pillichshammer. Digital nets and sequences: discrepancy theory and quasi-Monte Carlo integration. Cambridge University Press, 2010.
[20] Laurent Dinh, David Krueger, and Yoshua Bengio. NICE: Non-linear Independent Components Estimation, April 2015. 141.:1111..8516 [cs].
[21] Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density estimation using real nvp,
2017.
[22] Domke. Learning Graphical Model Parameters with Approximate Marginal Inference. IEEE
Trans. Pattern Analysis and Machine Intelligence, 35(10):2454-2467 2013.
10

---

[23] Gintare Karolina Dziugaite and Daniel M Roy. Pata-dependent pac-bayes priors via differential privacy. In Advances in Neural Information Processing Systems, volume 31 of NIPS. Curran Associates, Inc., 2018.
[24] Doris Fiebig. Mixing properties of a class of bernoulli-processee Transactions of the American Mathematical Society, (16()):479443, 1993.
[25] H. Föllmer. Tail structure of markov chains on infinite product spaces, Zeitschrift für Wahrschein- lichkeitstheorie und Verwandte Gebiete, 50(3):273-285, Jan 1979.
[26] A. Genevay, G. Peyré, and M. Cuturi. GAN and VAE from Optimal Transport Point of View.
preprini arXiv: 0001.000000000 000000887700 2017.
[27] B. Guedj. A Primer on PAC- PAC-Bayesian Learning. CoRR abs/1901.055 003353,, 2019.
[28]
Benjamin Guedj and Louis Pujol. Still No Free Lunches: The Price to Pay for Tighter PAC-
Bayes Bounds. Entropy, 23(1 129, November 2021.
[29] Maxime Haddouche, Benjamin Guedj, Omar Rivasplata, and John Shawe-Taylor Pac-bayes unleashed: Generalisation bounds with unbounded losses. Entropy, 23(1)),333,, 2021.
[30] J. Ho, C. Saharia, W. Chan, D. J. Fleet, M. Norouzi, and T. Salimans. Cascaded Diffusion Models for High Fidelity Image Generation. J. Machine Learning Research, 23:1-33, 2022.
[31] M. Jordan, T. Ghahramani, Z. abd Jaakkola, and L. K. Saul. An Introduction to Variational Methods for Graphical Models. Machine Learning, 57:183-233 1999.
[32] Herbert Knothe. Contributions to the theory of convex bodies. Michigan Mathematical Journal,
4(1):39-52, 1957.
[33] Kobyzev, S.J. D. Prince, and M. A. Brubaker. Normalizing Flows: Introduction and Review of Current Methods. IEEE Trans. Pattern Anal. Mach. Intell., 43(1 ((:31))::64499999 2021.
[34] D. Koller and N. Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT Press, 2009.
[35] Aryeh Kontorovich and Maxim Raginsky, Concentration of Measure Without Independence: Unified Approach Via the Martingale Method. In Eric Carlen, Mokshay Madiman, and Elisabeth M. Werner, editors, Convexity and Concentration, volume 161, pages 183-210. Springer New York, New York, NY, 2017. Series Title: The IMA Volumes Mathematics and its Applications.
[36] Leonid (Aryeh) Kontorovich and Kavita Ramanan. Concentration inequalities for dependent random variables via the martingale method. The Annals of Probability, 36(6):2125) 211-2288. 2008.
[37] M. Ledoux. The Concerntration of Measure Phenomenon. Amer. Math. Soc., 2001.
[38] Ben London, Bert Huang, and Lise Getoor. Stability and generalization in structured prediction. Journal of Machine Learning Research, 17(221):1-52, 2016.
[39] Ben London, Bert Huang, Ben Taskar, and Lise Getoor. Collective stability in structured prediction: Generalization from one example. In International Conference on Machine Learning. pages 828-836. PMLR, 2013.
[40] Ben London, Bert Huang, Ben Taskar, and Lise Getoor. Pac-hayesian collective stability. In Artificial Intelligence and Statistics, pages 585-594. PMLR, 2014.
[41] Youssef Marzouk, Tarek Moselhy, Matthew Parno, and Alessio Spantini. Sampling via Measure Transport: An Introduction. In Roger Ghanem, David Higdon, and Houman Owhadi, editors, Handbook of Uncertainty Quantification, pages 1-41. Springer International Publishing, Cham, 2016.
[42] David A McAllester. Pac-bayesian model averaging. In Proceedings of the twelfth annual conference on Computational learning theory, pages 164-170, 1999.
[43] David A. McAllester. Some pac-bayesian theorems. Machine 37(:::n5577333355553:3333333 Dec 1999.
[44] Waleed Mustafa, Yunwen Lei, Antoine Ledent, and Marius Kloft. Fine-grained analysis of structured output prediction. International Joint Conferences on Artificial Intelligence, 2021.
[45] Stanley Osher and Ronald Fedkiw. Level set methods and dynamic implicit surfaces. Springer, 2003.
11

---

[46] G. Papamakarios. E. Nalisnick, D.J. Rezende, S. Mohamed, and B. Lakshminarayanan. Nor- malizing Flows for Probabilistic Modeling and Inference. J. Machine Learning Research, 22(57):1-64, 2021.
[47] Maria Perez-Ortiz, Omar Rivasplata, Benjamin Guedj, Matthew Gleeson, Jingyu Zhang, John Shawe-Taylor, Miroslaw Bober, and Josef Kittler. Learning pac-bayes priors for probabílistic neural networks. arXiv preprint arXiv:2109.10333
2021.
[48] Maria Pérez-Ortiz, Omar Rivasplata, John Shawe-Taylor, and Csaba Szepesvári. Tighter Risk Certificates for Neural Networks. Journal of Machine Learning Research, 22(227):1-40, 2021.
[49] Murray Rosenblatt, Remarks multivariate transformation. The annals of mathematical statistics, 23(3):470-472, 1952.
[50] I.. Ruthotto and E. Haber. An Introduction Deep Generative Modeling. GAMM Milt., 44(2)224
pages, 2021.
[51] John Shawe-Taylor and Robert C Williamson. A pac analysis of bayesian estimator. In Proceedings of the tenth annual conference Computational learning theory, pages 2-9, 1997.
[52] Y. Song, J. Sohl-Dickstein, D. P. Kingma, A. Kumar, S. Ermon, and B. Poole. Score-Based Generative Modeling Through Stochastic Differential Equations. ICLR, 2021.
[53] Esteban G Tabak and Cristina Turner. family of nonparametrie density estimation algo-
rithms. Communications on Pure and Applied Mathematics, 66(2):145-164, 2013.
[54] Esteban G Tabak and Eric Vanden- Eijnden. Density estimation by dual ascent of the log- likelihood. Communications in Mathematical Sciences, 8(1):217-233, 2010.
[55] Vera Trajkovska, Paul Swoboda, Freddie Åström, and Stefania Petra. Graphical model parameter learning by inverse linear programming. In François Lauze, Yiqiu Dong, and Anders Bjorholm Dahl, editors, Scale Space and Variational Methods in Computer Vision, pages 323-334, Cham, 2017. Springer International Publishing.
[56] Brian Trippe and Richard Turner. Conditional Density Estimation with Bayesian Normal- ising Flows, February 2018. arXiv: 1802.04908 [stat].
[57] M.J. Wainwright and M.I. Jordan. Graphical Models, Exponential Families, and Variational Inference. Found. Trends Mach. Learn., 1(1-2):1-305, 2008
12

---

A Full Proofs of Presented Results
In this appendix, we present full proofs of all results which are not already complete in the main text.
Proof of Theorem For any E [d] and & E 2d define
M Ez (2) I = اا ( B zli = )
(26)
with the edge case
( = 1f : Z1 = - Ex -61-12111118888
(27)
Due to B2-r(f(2) Z =2] = f2) for 2 E B we have
f Ezzn (2) Σ MO
(28)
Since the conditions z14 NM generate nested sequence of o-algebras, the quantities
k(+11) f() (x z _ are Doob martingale and (26) martingale differ-
ence sequence. order bound the moment generating function of f. we will bound every ( from above and below and apply the Azuma- Hoeaa-Ho theorem I0 We have
M (( z =10]- B,If(Z) zli = 2(i-11]
(29a)
Ezff(Z)|BB Z 21 EEIEEii(Z))BB , 21t-11, _1-11,Z,11 Zi)|BS Z 2|t-11]
(29b)
=ʃ (i |210, ,))
f(210) (ia ) (1 12li-1) wi. B²)) ((duo 12) Br))
(29c)
by the tower property of conditional expectations. Because (ddultid |21 zli-1), B²) is a probability measure, it holds
f ((elhwissd) ((dd (10,,9)) / (/ (adda B²) uldrool BB)
(30)
and we find
( = / [(dwwl-e1)/(-1)) BB) (ʃ f(zli (0 (adul B3)
-f (1 w. By)
(31)
Now bound A < M0) < B(i) almost surely with
A = / B))
(ʃ (es(--))zu((dd (uduttii) BB)
inf
/ (addl 121-11) wa, ,,)) (32a)
B(0 / (((dwilid1/)k-11 Br)
sup (alt-)) (ʃ s(ali-)) (nd B3)
-f 5(2l) (udd
w;, By) (32b)
where (2lf-11) contains all Z such that there exist g((,0)] zd with (21i-1) 2, (f.d)) B Because every realization of a random variable conditioncd on B is in the set of good inputs, the difference ||000 1 can be written as
/
(F (1d |111 (0B1,1)) B²) - /
sup ol:
,B) (33)
13

---

By seeing this expression in terms of oscillation of the kernel action K (++1)) f, we find
|B | S Iool),((
s [Iel(v((+)) - (TS(T))
(34)
where /: 8 IR is the restriction of f to B The assertion then follows from the Azuma-Hoeffding Hoeffding
theorem 135 Theorem 4.1] which we recite as Theorem 10 to make this paper self-contained.
Proof of Proposition 6
For arbitrary 2, E z holds
(f(=) - f(=') s 6,00)(z5)))))
Vield
(35)
and thus, by summing over all indices we get
15(z) - ((>)) 1 Σ o)(0)(25))2)) jE[d
(36)
Let u E gd with vldh()) = 2d4M) be given for some E [d]. Recall the action ( of Markov kernels (*++1) is an expected value with respect to conditional distributions , (d loll))
Because vd has no atoms, IA also has no atoms. Therefore, there unique KR-rearrangement T with T, = vMI. Then T T T is a Kerrearrangemmet with
Tue B
(37)
by Lemma 9 and we have T() U. Lemma implies
(dw (dd 1 =l0) = T(ab)) )yud=
(38)
An analogous expression holds for the distribution conditioned on z. We have therefore found two transport functions pushing the reference measure to the respective conditional distributions. By Lemma 5 a coupling of the conditional distributions is then given by
pld (7 (- ,), 7(.d
F (z
(39)
Using a change of measure we find
k-(+1) f(v) - k((+1)((2)
= / p!d P! (dulia)) ( dulbdd) (f((l))t f(=l))(hd)))
(40)
/ ((ool)77h (+l1,,
r)) -(:l) (211), T)) ()))a(i(7))
(41)
< (f) (1) + Σ 8,(0)
/ ((Tie.d) ر)ار ( (-)
(42)
jE(rdd)
8,(
< plvi, 21) + Σ
d Tapp(u;,2))
(43)
jE(i,d
which shows
8, (K((+)) f) S 7
(b((T++ mn0,(()
(44)
jE(i,d)
for good inputs. We have thus found a Wasserstein matrix ((++1) for KT(+1) with entries
if
((++)
d
if j
(45)
ij
d
Lis
i
in row i which shows the assertion.
14

---

Proof of Theorem 7 For any hypothesis h E H. we have
R(h) Rm (h, Dm) = Ez~pl [L,, 2) Rm (1,, Dm)]
(46a)
Ezzu (L(t, (h, Dm)) ) $ B}]
+ EZzz [1(1h: 2) Rm (h, Dm)) 112 E B3]
(46b)
S BzzZ (I((h (h, Dm)) 1 $ B3} +
(46c)
I B2 [L 2)] - RRm (h, Pm) +
(46d)
where in (46c) we have used that pointwise loss is in [0, 1]. Note that the underlying distribution of
the risk R(h) is 14, while Dm are drawn from μ B". The above inequality reconciles this such that a concentration argument for the conditional distribution becomes applicable. For any PAC-Bayes
posterior distribution ( and any 3 > O, this implies
R() Rm (S. Dm) = B Ra [1,, 7) Rm (h, Dnn)
(47a)
s 5 BZ B= (h, 2)] Rm (h, Pm)] +
(47b)
= En [3(EZ~p185 (h,, Z)] Rm (h, Dmn)]] +
(47c)
3
$ log ENN exp (3(Rz~u B= [T.(h, 2) -Rm (h, Pm)))
+ KL :
+
(47d)
B
by Donsker and Varadhan's 's variational formula
2
Lemma 2.2). Focusing on the first term, we find
exp (3(BZ~n1B8 (L 2)] R. (h, Pm))) exp
Σ
(Ez~nl Bc [L 2)] Lth, 2(x))
m kE|m]
(48a)
B B2z [Lh,, 2)] L(h, 2 (())))
exp
km|m]
(48b)
Each structured datum ((k) is drawn independently from BL By Proposition 6 there exists Wasserstein dependency matrix || for n/ where D has entries (7). Then
3
E D (B)
exp II
B (B [T(h, 2)] - I(h, 2(5)))
kgim
E Ezw exp 3 (B2~pIB (L(h, 231 (1h,)) L(h, 2()1)
kE(m)
(49a)
3 (B (T(h, 2)) - I(h, ((b))((())))))))))))
II km[m]
E 11
exp
(49b)
32
8m [1 )0133 by Theorem +
<
exp
(49c)
kE [m)]
82
exp
1 (L,, 1]
(49d)
8m
< exp
r
(49e)
8m
Denote the shorthand
U = E (m) [exp (3(E [Lh,, Z)] RRm(h, Pm)))
(50)
15

---

By Markov's inequality it holds
P PD P (e]
exp (3(E2~niB-(4) (Lhh 2) -Rm (h, Pm))) 2 8
S
(51)
and combining this with 49 have
exp (B(Ez-u) (hh 2)] - Rm (h, Dm))) -
1
exp
||
(52)
8m
with probability at least 8 over the sample. Using (47
we thus have
R(() Rm (S, Dm) -
1
log EN
exp
|| ]
KI[S æ1) +
(53a)
B
8m
[
log
KLKS Ø1) +
(53b)
8m
Ideally, we would minimize the right hand side with respect to 3. However, this would mean to have depend on C and we thus would not have uniform bound for all posterior distributions.
Instead, [3 approaches the problem by defining a sequence of constant (8,, B, JeNN and bounding the probability that the bound does not hold for any sequence element. Since in the opposite (high-
probability) case, the bound holds for sequence elements, an optimal one can subsequently be chosen dependent on the posterior.
For all E No, define
8m log g
6, = (2-()
Bj -22 2d
V
(54)
|
which are independent of Ç. Now consider the event E, that
8 8m
exp (3,(Ez-nizs [8(h, 2)] - Rm (h, Dmm 2 exp
|
(55)
5j
By the above argument leading up to (52). the probability for E' under random sample of the conditioned data distribution yu B is at most 5,. Therefore, the probability that any Es occurs is bounded by
P( JENo
((F))
Σ 6, JEN
(56)
JEN.
Thus, for all posteriors Ç with probability at least none of the events (55) occurs. We may therefore select an index j dependent on obtain a sharper risk certificate which still holds with probability at least - 8 over the sample conditioned on the good set. For fixed posterior Ç. the optimizer of (53b) would be
8
8m 8
+ KL[S m])
(57)
[
Equating this to (55 and rounding down to the nearest integer gives
logz (1 KLL T]
(58)
log 8
Denote this number before rounding by r. i.e. j = [r]. For any real number r it holds r 1 < [r] I Therefore
1
KT[C: m
[L[C: m))
2" 20 -"-
(59)
2 log
log
which gives the following bounds on Uyy
8m alogg 1 + KLKS x))
Sm(log 1 KL[Ş m))
< ug- 5
(60)
2
|
||
16

---

Likewise, we bound
2
KL[S: x + log 8z-
KT[(S: T] + log
- + log 2
(61a)
8
2
log 2
KL T
S KL[S: m] + log
1og2 (1 (1+
log 2
(61b)
8
log 3
1
1
KL T
-KLSS |] + log
log
1
+
(61c)
8
2
log 3/
1
1
1 + KLLS =1) log log 1
KL[S : T| + log
log
log
(61d)
8
2
8
5
The assumption S exp( ( +) yields - log log 3/ we find
S and because x + 1 S exp(x) for all a E R.
KT,SK : T] + log 65-
1
< KT|S: = + log
5 2 log (log " + KT.ss :)) + +1)
+
(62a)
KLKS
+ log
[og + KLKS m))
(62b)
3 (log
1
KL[S m])
(62c)
2
8
We can now use the bounds 66cc
and
(60
in (53b)
to bound the expected generalization error
R()) - (S, 2m) I
log
KL[S m1) E
(63a)
8m
85-
Uyy
|
+ 2uh-
3
log 3
+ KT[S Tt) +
(63h)
8m
loog 1/2 + KLLS T
3
loog t + KL[S : T]
<
|
+
+
(63c)
2
2m
2
2m
log 1/ + KLIS : अ|
2| 12
+
(63d)
2m
Note that 3 would attain the optimal value
KL[S n] + log 8
R(C) Rm (S, Pm) S ||r8|21
+
(64)
2m
which only differs from the above uniform bound by factor of two. Finally, recall r Mel D where D has entries 17
d
B Additional Lemmata
Lemma 9. Let T: Ω + Ω be a measurable function on a measurable space (9, Σ) and let v, be measures Ω with Typ = μ.. Let B E. be a fixed set with μ(B) 0 and A T-1(1) (B) its preimage under T. Then
T:(1|A) B.
(65)
Proof. Let S E be arbitrary and let j = (y(1A)). Then
((S)) = (u)A)(T- = ((T
(66)
v(A)
well
(n[B)(S) mISn B) ((S B))
(67)
M(B)
v(A)
Note that 2 E (B) thus (B=)))) B) and consequently (i(S) (n) (S)). Since S was arbitrary, this shows the assertion.
+ T(2) E ( & T(z) ESB B + =ET B) (68)
17

---

The following theorem exists in various forms in the literature. To make this paper self self-contained, we recite the version in [35] which is used bound moment geenrrting functions Proposition Note that we only use the MGF bound (69) in our analysis. However, the concentration inequality (70) also holds analogously under the assumptions of Proposition 4 which may be independent interest.
Theorem 10 (Azuma-Hoeffding [3, Theorem 4.1]). Let )emm, be a martingale difference
sequence with respect to a filtration (Ei)ce(m) of sigma algebras. Suppose that for each E (m)] there
exist Σ ---e-measurable random variables A B(i) such that A I M I B(3) almost surely.
Then for all X E R. it holds that
M00] exp (A²
X2
exp (A Σ
Σ
[ - 100
(69)
8 sc|m]
:E[ml
and consequently, for any 1.
212
Σ
M
2
S 2exp
(70)
ig|m)
[B()
A
[m]
C Numerical Toy Example
Figure 1: KR rearrangement T(=) = (2,, T2)1, transports uniform reference mea- sure 2² on the unit cube [0, 1J to multimodal distribution (right).
1.00
1.0
bad set prob.
0.75
0.50
0..
0.0
0.4
0.6
largest L12
Figure 2: Construction of a good set in toy example. Left: L for all inputs. Center: size of an excluded bad set under the data distribution for corresponding largest values of L12. Right: L12 for good inputs.
To illustrate the concept of transport stability discussed in Proposition 6 as well as the bad set construction of Section we devised toy example of wwo-dimensional transport. As reference distribution, we choose the uniform distribution on the unit cube [0. 1|2, i...
[0, 1]. The metric pd, is chosen as the e -i-itaancce (2,,²') || z'Il1 = 1 zil + 222 2/1. The KR
transport map has component functions T(21, 22) (T (2 (2(21, 22)) We make a polynomial ansatz, defining
(2(2))
/
Σ (T),
T2(211 = 1(
Σ
B2))
(71)
10.z1) sE(5)
[0,220 (E(2)
18

---

where BT denotes the i-th Bernstein polynomial of degree m. B 2 O are parameters and (positive) coefficient functions (21 are again parameterized combination of Bernstein polynomials (degree 8). Because Bernstein polynomials assume non-negative values on [o, 1], the components in (71) define valid Kerraarrangemmnt The resulting measure transport is illustrated in Figure In order to evaluate the bound of Theorem 7
we need to compute the Lipschitz constant L12 according to
equation (66)
(72) 72 for each input 21) [0, 1]2. The sought Lipschitz constant is the largest of these values. In order to avoid regions with large values, Theorem allows for the exclusion of bad inputs. The probability & of this bad under the data distribution is incurred bad sets to exclude large values and consider their probability under the data distribution Figure 2 (middle). Finally, the exclusion of such bad is shown the right of Figure 2
Ex-uy ( (Z1. - T=(xí, - L12/21 =1
for all good imputs 21, 21. Figure (left) shows the values of L12 satisfying
penalty in equation (20). We thus construct
19


Reviews:
[{"review_id": "iBAIJuHup5", "reviewer": "Reviewer_zkw9", "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.\n\n[1] London, Ben, et al. \"Collective stability in structured prediction: Generalization from one example.\" International Conference on Machine Learning. PMLR, 2013.\n\n[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.\n\n[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.", "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.\n2) What's the intuition about \"a bad set\" --- is it the set possibly locally unstable?\n3) Is there any possible simulation setup we can see the provided PAC Bayes bound works?\n4) 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.\n", "limitations": "Limitations are properly discussed.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "1. New stability notion is considered for PAC bayes risk bound, providing additional analysis and interpretations up on previous works.\n2. Provided examples and intuitions are helpful for readers to follow the manuscript.\n3. 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.\n\n\n[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.\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Thank you for your careful reading of our manuscript and insightful review\n\n1.\nWe do not claim to make a contribution to the mathematical literature on measure concentration with respect to functions of dependent random variables. Rather, we contribute to machine learning by applying the concepts devised in [3] to *structured* prediction based on the class of generative data models (normalizing flows) based on KR rearrangement. Thus our work extends the recent line of research on tight PAC bounds for deep learning to structured prediction, based on a probabilistic data model which covers many practical scenarios.\n\n2.\nWe refer in Section 1.1, line 43 to works which survey and introduce to PAC-Bayes theory. The influence of stability and dependency on our novel PAC-bound is discussed in the paragraph directly after the main Theorem 7, lines 245-250: bounded dependency and large size d of data points can compensate for smaller numbers m of samples in order to achieve tight bounds, which is important for scenarios of *structured* predicion.\n\n\n# Response to Reviewer Questions\n\n1. \nSince our approach relies on a generative data model (normalizing flows) via KR rearrangement, which comprises an invertible architecture and measure transport in both directions (training and sampling), we assume that both the reference and the target (data) distribution are atom-free, according to the mathematical theory underlying KR-based measure transport. This excludes discrete spaces. On the other hand, due to the well-established theory of quantization of probability distributions, discrete scenarios can be implicitly modeled using atom-free measures, too - see, e.g., the scenario mentioned in the lines 127-128.\n\nThe format of our novel PAC bound, eq. (20), clearly connects to prior known PAC bounds. The right-hand side has the ususal format comprising the empirical risk and a complexity term. The essential difference is that the latter term depends also on the norm of the Wasserstein dependency matrix times the oscillation vector, which enables to learn and reliably predict even from few examples (small m) provided the internal dependencies are bounded and the size d of each data point is large.\n\n2.\nThe intuition about the bad set are rare data points whose internal dependency and structure, which we explore to learn and certify structured prediction from few examples, does *not* conform to the quantitative assessment of this internal dependencies, according to Proposition 6. The bad set contains data points with `unusually' pronounced internal dependencies, causing instability under data perturbations. Thus, the concept of a bad set enables to quantify expected internal data dependencies in a sensible way (Proposition 6) so as to make tight the novel PAC-Bayes risk bound for structured prediction (Theorem 7), for any typical (= good) data point.\n\n3.\nWe evaluated eq. (16) or Proposition 6 for a 2D-toy scenario and defined the bad set as suggested in the first paragraph of Section 5, line 297, in order to demonstrate that the theory is amenable to numerical evaluations. Please see the PDF attached for an illustration. As mentioned in the paper, the development of dedicated numerical methods and experiments is beyond the scope of the paper.\n\n4.\nWe agree and are aware that the symbol $\\delta$ is overloaded, which is acceptable if both the argument and sub- or superscripts disambiguate the interpretation. In the present case, $\\delta_{x}$ with a vector as subscript denotes a Dirac measure in order to make Markov kernels well-defined in connection with conditional probability laws (eq. (7)) and expectation (eq. (8)). On the other hand, $\\delta_{i}$ with a number in $[d]$ as subscript and a function as argument (e.g. eqns. (6) and (9)) uniquely refer to the local oscillation of the argument.\n"}, {"review_id": "elQ6hw27e1", "reviewer": "Reviewer_kVX1", "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.", "questions": "**Q1.** How are the theoretical results in this submission (perhaps given further development) to inform practice?\n\n**Q2.** In general, what would be possible progressions of developments building on this work?\n\n**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?\n", "limitations": "Potential negative societal impact was not discussed.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "**S1.** This theoretical work advances a series of works on bounding the risk of structured predictors via more recent concentration of measure results.\n\n**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.\n\nAs 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?\n\n**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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Thank you for your careful reading of our manuscript and insightful review\n\n# W1 & Q2\nThe recent work of [Baptista] discusses a parametric class of monotone triangular maps which can serve as approximations of KR rearrangement. A possible direction of future work is to specialize this construction to functions which in addition provide a tractable form of the Lipschitz constants in Eq. (16).\n\nThe derandomization proposed in [London, Proposition 4] is built on an assumption on hypothesis stability. This is orthogonal to the assumptions on input stability made in our work and thus applies analogously in concert with our PAC-Bayesian construction. We have omitted this step as well as the consideration of bad hypotheses proposed by [London] for ease of exposition (see lines 289-290). We will add reference to this after line 290 \"The same applies to the derandomization strategy proposed by [London] which is based on hypothesis stability.\"\n\n\n# W2 & Q1\nOur work connects state of the art PAC-Bayesian learning theory (the only theory which is currently able to achieve tight bounds in deep learning) to plausible assumptions about concrete generative data models used in practice and realized via KR-based measure transport. In particular, our work addresses the challenging case of structured prediction and the ability to learn from few samples due to the dependency caused by internal structure.\n\nA specific use of this theory is to improve training procedures based on a better understanding of generalization. Because tight risk certificates are now available in PAC-Bayesian learning, it has become possible to directly optimize a (tight) bound on the generalization error (out-of-sample) rather than merely optimizing empirical risk (in-sample) [Clerico] [Perez]. Our work is towards extending this to structured prediction scenarios. As an example, node-classification with graph neural networks can not currently be studied with established PAC-Bayesian methods because, although labels are available on a subset of graph nodes, all data are dependent (m = 1). \n\n# Q3.\nDue to invertible architectures and measure transport in both directions, the assumption of atom-free data distributions is required by the theory of measure transport based on KR rearrangements and hence at the core of corresponding popular normalizing flow models used today (such as RealNVP [Dinh], FFJORD [Grathwohl], Invertible ResNet [Behrmann]). This excludes discrete output spaces. On the other hand, due to the well-established theory of quantization of probability distributions, discrete scenarios can be implicitly modeled using atom-free measures, too - see, e.g., the scenario mentioned in the lines 127-128.\n\n[London] London, B., Huang, B., & Getoor, L. (2016). Stability and generalization in structured prediction. The Journal of Machine Learning Research, 17(1), 7808-7859.\n\n[Baptista] Baptista, R., Marzouk, Y., & Zahm, O. (2020). On the representation and learning of monotone triangular transport maps. arXiv preprint arXiv:2009.10303.\n\n[Clerico] Clerico, E., Deligiannidis, G., & Doucet, A. (2022, May). Conditionally gaussian pac-bayes. In International Conference on Artificial Intelligence and Statistics (pp. 2311-2329). PMLR.\n\n[Perez] Pérez-Ortiz, M., Rivasplata, O., Shawe-Taylor, J., & Szepesvári, C. (2021). Tighter risk certificates for neural networks. The Journal of Machine Learning Research, 22(1), 10326-10365.\n\n[Dinh] Dinh, L., Sohl-Dickstein, J., & Bengio, S. (2016). Density estimation using real nvp. arXiv preprint arXiv:1605.08803.\n\n[Grathwohl] Grathwohl, W., Chen, R. T., Bettencourt, J., Sutskever, I., & Duvenaud, D. (2018). Ffjord: Free-form continuous dynamics for scalable reversible generative models. arXiv preprint arXiv:1810.01367.\n\n[Behrmann] Behrmann, J., Grathwohl, W., Chen, R. T., Duvenaud, D., & Jacobsen, J. H. (2019, May). Invertible residual networks. In International conference on machine learning (pp. 573-582). PMLR.\n"}, {"review_id": "318rUeMJ8h", "reviewer": "Reviewer_uxkb", "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.", "questions": "I have a few minor concerns as follows:\n\n1. 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?\n\n2. 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.\n\n3. Does the learned measure transport distribution converge to the true underlying distribution asymptotically? If not, how close are they?\n", "limitations": "Yes, the authors have adequately discussed the limitations of their findings.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\n\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Thank you for your careful reading of our manuscript and insightful review\n\nBounds which ignore the size of the structured object can not make any useful statement on generalization from a single example. For instance, the typical setting of node classification with graph neural networks considers a single graph, with training labels available on a subset of the nodes. In this case, all available data is part of a single structured object (the graph) and PAC-Bayesian learning theory (the only theory which is currently able to achieve tight bounds in deep learning) can not make a useful statement about generalization if the internal structure is ignored (m = 1).\n\n\n# Response to Reviewer Questions\n\n(1)\nThe assumptions made on the loss function are common in the PAC-Bayesian literature.  Recent works have aimed to relax them with some success. We refer to these works [3,27,28] in Section 1.1, line 56, an even more recent example is [Haddouche]. However, generalization to unbounded losses requires nontrivial extensions to our proofs.\nDecomposition of the loss into a sum of component losses is usually assumed in PAC-Bayesian constructions as a prerequisite to underlying concentration of measure results (such as Hoeffding's inequality, which makes a statement about the sum of independent variables). Since we use more general concentration of measure theory which handles dependent data, our results can more easily generalize to losses which do not decompose (but are still bounded).\n\nNote that PAC-Bayesian theory also offers opportunities. For example, the construction does not require differentiable loss. Thus, some loss functions (such as the 01 loss which is particularly natural in classification) can actually be available for PAC-Bayesian risk certification even though they are not typically useful for the training of deep networks. An example is the model of [Clerico] which enables direct optimization of expected generalization error in the sense of 01 loss. Beyond 01 loss, it has been proposed to certify the confusion matrix of classifiers using PAC-Bayesian methods [Adams].\n\n\n(2)\nWe evaluated eq. (16) of Proposition 6 for a 2D-toy scenario and defined the bad set as suggested in the first paragraph of Section 5, line 297, in order to demonstrate that the theory is amenable to numerical evaluations in principle. Please see the PDF attached for an illustration. As mentioned in the paper, the development of dedicated numerical methods and experiments is beyond the scope of the paper, however.\n\n(3)\nUnder the assumptions adopted in the paper, the measure transport can be realized via KR rearrangement, in principle; see, e.g., [6] (mentioned in line 90). Convergence rates for finite sample regimes, however, define an open research problem. A step in this direction was recently made in [4]. This is mentioned in the \"Limitations\" Section, line 341.\n\n[Haddouche] Haddouche, M., & Guedj, B. (2023). Wasserstein PAC-Bayes Learning: A Bridge Between Generalisation and Optimisation. arXiv preprint arXiv:2304.07048.\n\n[Clerico] Clerico, E., Deligiannidis, G., & Doucet, A. (2022, May). Conditionally gaussian pac-bayes. In International Conference on Artificial Intelligence and Statistics (pp. 2311-2329). PMLR.\n\n[Adams] Adams, R., Shawe-Taylor, J., & Guedj, B. (2022). Controlling confusion via generalisation bounds. arXiv preprint arXiv:2202.05560.\n"}, {"review_id": "hb9dDwWuRx", "reviewer": "Reviewer_dT9a", "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.", "questions": "Please see the weaknesses comments.", "limitations": "None.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\n2. 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.\n", "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*].\n\n2. 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.\n\n3. 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).\n\nI will consider improving the score after you discuss my concerns.\n\n[1*] Ben London, Bert Huang, and Lise Getoor. Stability and generalization in structured prediction. JMLR 2016.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Thank you for your careful reading of our manuscript and insightful review\n\n\n(1)\nWe agree that, in their most abstract form, the results of [1*] do not require an MRF assumption. However, in our view, the key issue which reduces the relevance of this theory to practitioners is computability. This is the case especially since *tight* generalization bounds for deep learning via PAC-Bayesian theory have been more recently demonstrated [Dziugaite & Roy], [Perez], [Clerico] for finite sets of independent data. For example, [Clerico] certifies CIFAR-10 classification risk of at most 20.66% with probability at least 96.5% over the draw of the sample for a model with empirical test-set error of 19.52 +- 0.2 %. Thus, data dependency appears as the only remaining roadblock in structured prediction.\n\nWith the more ambitious goal of tight, finite sample risk certificates in mind, the next step in our view is to instantiate abstract results of learning theory for concrete data models. Here, [1*] focuses on MRF data and all of the more concrete results in [1*] make this assumption. The authors explicitly leave the question of estimating ϑ-mixing coefficients from data for future work [1*, Section 7] and point to the preliminary work of [McDonald] on β-mixing. We are not aware of works which have pursued this for ϑ-mixing. In Section 2.1, we argue that this may not be possible without an explicit assumption on the data-generating process.\n\nThis is the starting point of our current work, we choose a specific, very general data model (measure transport by KR rearrangement) and construct an analogous PAC-Bayesian bound from related concentration of measure results which play particularly nicely with this data model.\nMore specifically, the key technical differences between our mathematical framework and theirs are (a) the choice of coupling measure between conditional distributions and (b) the choice of metric on the data space. They use the coupling measure construction of [Fiebig] and the Hamming distance which allows to distill dependency into a ϑ-mixing dependency matrix [1*, Lemma 6 in Appendix A.2]. We construct the required coupling from properties of the KR rearrangement (Lemma 5 and Lemma 3) and apply the concentration of measure results of [Kontorovich] without choosing a specific metric. Our approach is thus specifically geared towards measure transport models by essentially translating data dependency into a property of the transport map (the Lipschitz constants $L_{ij}$ in Eq. (16), Proposition 6).\n\n(2)\nWe evaluated eq. (16) of Proposition 6 for a 2D-toy scenario and defined the bad set as suggested in the first paragraph of Section 5, line 297, in order to demonstrate that the theory is amenable to numerical evaluations in principle. Please see the PDF attached for an illustration. As mentioned in the paper, the development of dedicated numerical methods and experiments is beyond the scope of the paper, however.\n\n(3)\nRegarding eq. (7), we will add the following explanatory text to line 152:\nHere $K^{(i)}(x,dy)$ is a Borel measure for every $x$ and (8) computes the expected value of $f$ at x, conditioned on the fixed realization of the subvector $x^{[i-1]}$.\n\nThe subsequent sentence in the paper, preceding Definition 2, clarifies the role of the Wasserstein matrix: \"It turns out that the effect of the kernel (7) on local oscillations serves to quantify dependence of data with joint distribution $\\mu$.\"\n\n\n[1*] London, B., Huang, B., & Getoor, L. (2016). Stability and generalization in structured prediction. The Journal of Machine Learning Research, 17(1), 7808-7859.\n\n[Dziugaite & Roy] Dziugaite, G. K., & Roy, D. M. (2018). Data-dependent PAC-Bayes priors via differential privacy. Advances in neural information processing systems, 31.\n\n[Perez] Pérez-Ortiz, M., Rivasplata, O., Shawe-Taylor, J., & Szepesvári, C. (2021). Tighter risk certificates for neural networks. The Journal of Machine Learning Research, 22(1), 10326-10365.\n\n[Clerico] Clerico, E., Deligiannidis, G., & Doucet, A. (2022, May). Conditionally gaussian pac-bayes. In International Conference on Artificial Intelligence and Statistics (pp. 2311-2329). PMLR.\n\n[McDonald] Mcdonald, D., Shalizi, C., & Schervish, M. (2011, June). Estimating beta-mixing coefficients. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics (pp. 516-524). JMLR Workshop and Conference Proceedings.\n\n[Fiebig] Fiebig, D. (1993). Mixing properties of a class of Bernoulli-processes. Transactions of the American Mathematical Society, 338(1), 479-493.\n\n[Kontorovich] Kontorovich, A., & Raginsky, M. (2017). Concentration of measure without independence: a unified approach via the martingale method. In Convexity and Concentration (pp. 183-210). Springer New York.\n"}, {"review_id": "0SY50THfd6", "reviewer": "Reviewer_H5Qp", "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.", "questions": "Please see the weaknesses and limitations", "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. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "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. \n\n2. The set of bad inputs is bounded so that the risk is more certificated.\n\n3. 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?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Thank you for your careful reading of our manuscript and insightful review\n\nIt has been shown by [Bogachev2005] that any atom-free data distribution can be represented as the unique KR rearrangement of an atom-free reference distribution (such as the normal distribution or uniform distribution). This is a rather flexible model. For instance, every data distribution which has a density with respect to the Lebesgue measure satisfies these assumptions. As toy models, this includes all multivariate normal distributions and all Gaussian mixture models. \n\nDue to invertible architectures and measure transport required in both directions, these same assumptions are also at the core of many popular normalizing flow models, such as RealNVP [Dinh], FFJORD [Grathwohl], Invertible ResNet [Behrmann] and their conditional variants [Trippe], [Atanov].\nThese models have been successfully used as surrogates for real data in multiple applications [Altekruger], [Kousha], [Lugmayr], [Horvat], [Wang] which empirically supports the assumption of an atom-free data distribution.\n\n\n[Dinh] Dinh, L., Sohl-Dickstein, J., & Bengio, S. (2016). Density estimation using real nvp. arXiv preprint arXiv:1605.08803.\n\n[Grathwohl] Grathwohl, W., Chen, R. T., Bettencourt, J., Sutskever, I., & Duvenaud, D. (2018). Ffjord: Free-form continuous dynamics for scalable reversible generative models. arXiv preprint arXiv:1810.01367.\n\n[Behrmann] Behrmann, J., Grathwohl, W., Chen, R. T., Duvenaud, D., & Jacobsen, J. H. (2019, May). Invertible residual networks. In International conference on machine learning (pp. 573-582). PMLR.\n\n[Trippe] Trippe, B. L., & Turner, R. E. (2018). Conditional density estimation with bayesian normalising flows. arXiv preprint arXiv:1802.04908.\n\n[Atanov] Atanov, A., Volokhova, A., Ashukha, A., Sosnovik, I., & Vetrov, D. (2019). Semi-conditional normalizing flows for semi-supervised learning. arXiv preprint arXiv:1905.00505.\n\n[Altekruger] Altekrüger, F., Denker, A., Hagemann, P., Hertrich, J., Maass, P., & Steidl, G. (2023). PatchNR: learning from very few images by patch normalizing flow regularization. Inverse Problems, 39(6), 064006.\n\n[Kousha] Kousha, S., Maleky, A., Brown, M. S., & Brubaker, M. A. (2022). Modeling srgb camera noise with normalizing flows. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 17463-17471).\n\n[Lugmayr] Lugmayr, A., Danelljan, M., Van Gool, L., & Timofte, R. (2020). Srflow: Learning the super-resolution space with normalizing flow. In Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part V 16 (pp. 715-732). Springer International Publishing.\n\n[Horvat] Horvat, C., & Pfister, J. P. (2021). Denoising normalizing flow. Advances in Neural Information Processing Systems, 34, 9099-9111.\n\n[Wang] Wang, C., Zhu, Y., & Yuan, C. (2022, October). Diverse Image Inpainting with Normalizing Flow. In European Conference on Computer Vision (pp. 53-69). Cham: Springer Nature Switzerland.\n"}]

Author rebuttal:

# We thank all reviewers for their insightful and constructive reviews. 

We respond in detail to each reviewer in the corresponding sections. Below, we summarize our responses to points which were raised by at least two reviewers.

# Connections/implications to practice, KR-based generative models and real data distributions.
Our work connects the recent line of research on tight PAC bounds for deep learning to *structured* prediction, based no generative models via KR-arrangements. The latter can cover any atom-free real data distribution in theory and a broad range of realistic scenarios in practice (our detailed response provides more references). Approximation bounds for finite sample scenarios is the subject of ongoing research, see, e.g., [4] for a step towards this goal.

# Discrete spaces
KR-based generative models require measure transport in both directions and assume atom-free reference and target distributions; see, e.g., [11]. We do not consider this as a serious restriction since discrete scenarios can be represented through the quantization of probability distributions.

# Toy experiments, intuition about bad sets
We evaluated a toy experiment to demonstrate that our approach is amenable to numerical evaluation, in principle. Please see the PDF sheet attached. The design of a dedicated numerical algorithm and experiments is beyond the scope of the paper, however.


Meta-review: This paper tackles learning theory problems in structured prediction, a more challenging setting for theoretical results compared to standard binary or multiclass classification. The goal is to provide generalization bounds that incorporate the richness of the structures of the samples. In particular, in such problems there is a tradeoff between the number of independent samples and the "size" of each sample, where component parts are not necessarily independent.

The authors effectively generalize existing results in this area by relying on a weaker assumption on the data generating process. The generalization is reasonably strong (moving from requiring Markov random fields to a much more general class of distributions). The authors overcome a number of technical hurdles in order to be able to do this. This culminates in a nice PAC-Bayes result, the central result of the paper.

While the result is purely theoretical, it will be appreciated by researchers in structured prediction and is likely to be a useful building block for future learning theory results in the area. As the authors note, it is also a good step towards building practical results for downstream use.

For these reasons, I recommend acceptance. Additionally, all reviewers also leam accept and had their questions resolved by the authors during the rebuttal stage.
Decision: Accept (poster)