Towards Sharper Generalization Bounds for Structured Prediction
Year: 2022

Abstract:
In this paper, we investigate the generalization performance of structured prediction learning and obtain state-of-the-art generalization bounds. Our analysis is based on factor graph decomposition of structured prediction algorithms, and we present novel margin guarantees from three different perspectives: Lipschitz continuity, smoothness, and space capacity condition. In the Lipschitz continuity scenario, we improve the square-root dependency on the label set cardinality of existing bounds to a logarithmic dependence. In the smoothness scenario, we provide generalization bounds that are not only a logarithmic dependency on the label set cardinality but a faster convergence rate of order O( 1 n ) on the sample size n. In the space capacity scenario, we obtain bounds that do not depend on the label set cardinality and have faster convergence rates than O( 1 √ n ). In each scenario, applications are provided to suggest that these conditions are easy to be satisfied.

text: n ). In each scenario, applications are provided
to suggest that these conditions are easy to be satisfied.

heading: 1 Introduction
text: Structured prediction [18, 12, 17] covers a wide range of machine learning fields, such as computer vision, natural language processing, and computational biology. Several examples of structured prediction problems include part-of-speech tagging, dependency parsing, named entity recognition and machine translation in natural language understanding, image segmentation and objection recognition in computer vision, and protein folding in computational biology. An essential property of structured prediction is that the output space admits some structure, such as strings, graphs, trees, or sequences [18, 12, 13]. Meanwhile, another property common to the above tasks is that the natural loss function in each case admits a decomposition along with the output substructures. The complex output structure and corresponding loss function make structured prediction different from the widely studied binary or multi-class classification problems.
The design of structured prediction algorithms have been thrived for many years, including conditional random fields [30], structured support vector machines [61], kernel-regression algorithm [19], searchbased structured prediction [20], maximum-margin markov network [60], image segmentation [43], part-of-speech-tagging [27], and machine translation [68]. Compared to the prosperity and development of structured prediction algorithm designing, the theoretical analysis of structured prediction appears to be not sufficiently well-documented [13], especially the studying on sharper generalization bounds. However, it is known that the theoretical study of structured prediction algorithms is essential [18, 12, 13, 1].
Several theoretical studies of structured prediction consider a specific algorithm and a simple loss such as Hamming loss [60, 16, 14]. Recently, increasing work has considered the analysis of general losses. These works can be roughly cast into four categories: PAC-Bayesian approach, factor graph
∗Corresponding Author.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
decomposition approach, implicit embedding approach, and stability approach. [22, 45, 26, 4] provide PAC-Bayesian guarantees for arbitrary losses through the analysis of randomized algorithms using count-based hypotheses. [12, 13, 53, 52, 8, 11, 58, 7] use implicit loss embedding to construct a connection between discrete output of structured prediction and regression, to investigate the generalization performance of structured prediction. [18, 3, 51] present generalization bounds for general losses based on factor graph decomposition approach, which is proposed in the seminal work [18]. [41, 42, 40] use the stability tool to investigate the generalization bounds and provide interesting theoretical insights that structure prediction is possible to generalize from a few large examples, potentially even just one. A special case of structured prediction problem worth mentioning is multi-class classification [34, 33, 36, 55, 50, 65, 48, 49, 44, 31], whose scoring function can be seen as a factor graph with both factor node size and substructure size equal to one.
Although the aforementioned works have provided generalization bounds from different perspectives, there are still some problems urgently to be solved in structured prediction.
(1.) Existing generalization bounds mostly have a slow convergence rate with respect to (w.r.t.) the sample size n. Specifically, in PAC-Bayesian approach, [45, 26, 4, 22] provide the generalization bounds of order O( 1√
n ). In implicit embedding approach, [12, 13, 52, 11, 58, 7] provide the
convergence rate of order O( 1 n1/4 ), and [53] of order O( 1√ n ). In the factor graph decomposition approach, [18, 51] present the generalization upper bounds of order O( 1√
n ). Also, in stability
approach, [41, 42, 40] show the O( 1√ n ) order bounds. Therefore, this raises a question: can the convergence rate of structured prediction achieves faster order O( 1n )? (2.) In structured prediction, the number of possible labels is potentially infinite [18]. Thus it is important to obtain upper bounds that have a lower order dependency on the cardinality of possible labels. The factor graph decomposition approach can provide the explicit dependency on the properties of the factor graph and help us to explicitly show the dependency on the number of possible labels, which sheds new light on the role played by the graph in generalization [18]. Therefore, our analysis is based on the factor graph decomposition [18, 3, 51]. However, [3] focuses on the lower bound, [51] studies the specific surrogate loss, and the upper bounds in [18] show a square-root dependency on the cardinality of possible labels. If we consider the vast number of possible labels, the results in [18] may be divergent and can not explain the good performance of structured prediction algorithms in practice. Thus, can the upper bound of structured prediction presents a lower order dependency on the cardinality of possible labels or even no dependency?
(3.) Although some work in multi-class classification [36, 55, 65], a special structured prediction problem, have shown the faster convergence rate of orderO( 1n ) w.r.t. the sample size n, it is unknown in more difficult and complex structured prediction problems. Additionally, we naturally want to know whether the generalization bounds of structured prediction can combine (1) with (2) to show faster convergence rates simultaneously?
This paper intends to answer the three interesting questions. We consider the general loss and present novel margin-based theoretical analysis for structured prediction from three perspectives: Lipschitz continuity, smoothness, and space capacity condition. We first assume the loss function used in structured prediction is Lipschitz continuous and try to answer question (2). Under this condition, we improve the generalization bounds of structured prediction from a square-root dependency to a logarithmic dependency on the label set cardinality, but a slow convergence rate of order O( 1√
n )
w.r.t. the sample size n. Then, we assume the loss is smooth and intend to answer questions (1) and (3). Under this assumption, we obtain sharper bounds that not only have the faster convergence rate of order O( 1n ) on the sample size n but also have the logarithmic dependency on the label set cardinality. Furthermore, we consider the space capacity-dependent assumptions: logarithmic covering number and polynomial covering number assumptions, which are commonly used in learning theory [32, 69, 56]. This setting attempts to answer questions (1-3). Under this condition, we show that the bound can present no dependency on the label set cardinality, simultaneously with faster convergence rates thanO( 1√
n ). In the above three perspectives, we all provide applications to suggest
that these conditions are easy to be satisfied in practice.
This paper is organized as follows. In Section 2, we introduce the notations and definitions relevant to our discussion. In Section 3, we present the main results, deriving a series of new learning guarantees for structured prediction. Section 4 concludes this paper.

heading: 2 Preliminaries
text: Notations. Let P be a probability measure defined on a sample space X ×Y with X ∈ Rd being the input space and Y being the output space. A key aspect of structured prediction is that the output space may be sequences, graphs, images, or lists [18]. We thus assume that Y can be decomposed into l substructures: Y = Y1 × · · · × Yl, where Yi is the set of possible labels that can be assigned to substructure i. Take the simple webpage collective classification task for example [59], each Yi is a webpage label and Y is a joint label for an entire website. If we assume each Yi ∈ {0, 1}, the number of possible labels to Y is exponential in the number of substructures l, i.e., |Y| = 2l. Factor graphs and scoring function. In structured prediction, we aim to learn a scoring function f = X ×Y → R. Let F be a family of the scoring function. For each f ∈ F , we define the predictor f̂ as: for each x ∈ X , f̂(x) = arg maxy∈Y f(x, y). Moreover, we assume that the scoring function f can be decomposed as a sum [61, 60, 30, 18], which is standard in structured prediction and can be formulated via the notation of factor graph [18]. A factor graph G is a bipartite graph, and is represented as a tuple G = (V,H,E), where V = {1, ..., l} is a set of variables nodes, H is a set of factor nodes, and E is a set of undirected edges between a variable node and a factor node. Let N (h) be the set of variable nodes connected to the factor h by an edge and Yh be the substructure set cross-product Yh = ∏ k∈N (h) Yk. Based on the above notations, the scoring function f(x, y) can be decomposed as a sum of functions fh [18], with an element x ∈ X and an element yh ∈ Yh as arguments:
f(x, y) = ∑ h∈H fh(x, yh).
In this paper, we consider the more generally setting: for each example (xi, yi), the corresponding factor graph may be different, that is, G(xi, yi) = Gi = ([li], Hi, Ei). A special case of this setting is that, for example, when the size li of each example is allowed to vary and where the number of possible labels |Y| is potentially infinite. Figure 1 shows different examples of factor graphs. Learning. In order to measure the success of a prediction, we use a loss function L : Y × Y → R+ to measure the dissimilarity of two elements of the output space Y . A distinguishing property of structured prediction is that the natural loss function admits a decomposition along the output substructures [18], such as the Hamming loss, defined as: L(y, y′) = 1l ∑l k=1 Iyk 6=y′k for two outputs y, y′ ∈ Y , with y = (y1, ..., yl) and y = (y′1, ..., y′l), or edit-distance loss in natural language and speech processing applications, or other losses [18, 10]. Given a training set S = {(x1, y1), ..., (xn, yn)} of size n being independently drawn from the underlying distribution P , our goal is to learn a hypothesis f ∈ F with good generalization performance from the sample S by optimizing the loss L. The performance is measured by expected risk, defined as
R(f) := E(x,y)∼P [L(f̂(x), y)].
However, the above mentioned loss function f → L(f̂(x), y) is typically the 0− 1 loss of f , which is hard to handle in machine learning. Therefore, one usually consider surrogate losses [12, 13, 18].
Margin and loss function class. We now introduce the definition of standard margin and the surrogate loss. The margin of any scoring function f for an example (x, y) is defined as:
ρf (x, y) = f(x, y)−max y′ 6=y
f(x, y′).
We consider the scoring function f of the form f(x, y) = 〈w,Ψ(x, y)〉, where Ψ is a feature mapping from X × Y to RN such that Ψ(x, y) = ∑ h∈H Ψh(x, yh) due to the decomposition of f [18]. And we define the following scoring function space:
F = {x 7→ 〈w,Ψ(x, y)〉 : w ∈ RN , ‖w‖p ≤ Λp}, (1)
where ‖w‖p = ( ∑N i=1 |wi|p) 1 p . Then, the corresponding surrogate loss function class is defined as:
Lρ = {`ρ(x, y, f) := `(ρf (x, y)) : f ∈ F} ,
where `ρ is the surrogate loss of L. We assume `ρ is bounded by M , which implies that 0 ≤ L(f̂(x), y) = L(f̂(x), y)ρf (x,y)≤0 ≤ `(ρf (x, y)) ≤M since L is positive, the cost will only occur
when the margin function value is negative and the surrogate loss ` is larger than L. Additionally, we define the empirical risk of any scoring function f as
R̂(`(ρf )) := 1
n n∑ i=1 `ρ (xi, yi, f) ,
and the expected risk as R(`(ρf )) := E(x,y)∼P [`ρ(x, y, f)] .
Clearly, we have R(f) ≤ R(`(ρf )).

heading: 3 Main Results
text: This section provides sharper generalization bounds for structured prediction from three perspectives: Lipschitz continuity, smoothness, and space capacity. Finally, we obtain sharper bounds of order O( 1n ) w.r.t. the sample size n and showing a logarithmic dependency, or even no dependence, on the label set cardinality. In each case, we provide applications to suggest that these conditions are easy to be satisfied.

heading: 3.1 Lipschitz Continuity Dependent Case
text: Assumption 1 Assume that ` is µ-Lipschitz continuous, that is
|`(t)− `(s)| ≤ µ|t− s|.
Assumption 1 is a pretty mild assumption. The hinge loss `(ρf ) = (1− ρf )+ and the margin loss `(ρf ) = 1ρf≤0 + (1− ρfρ−1)10<ρf≤ρ satisfy Assumption 1 [33]. Moreover, the loss of truncated margin functions in [25] satisfies Assumption 1. The additive and the multiplicative margin loss provided by [18], which covers many existing structured prediction algorithms, satisfy Assumption 1 (see Corollary 1 for details).
Theorem 1 Under Assumption 1, for any δ > 0, with probability 1− δ over the sample S of size n, the following holds for all f ∈ F ,
R(f) ≤ R(`(ρf )) ≤ R̂(`(ρf )) +O
( µs lnn√
n
( log 1 2 (n2) + log 1 2 (sk) ) + √ log 1/δ
n
) ,
where s = maxi∈[n] |Hi|, k = maxi∈[n] |Hi|di, and where di = maxh∈|Hi| |Yh|.
Remark 1 [Sketch of Theorem 1.] Since our task is to prove bounds with better rates, that is, which decrease fast with n→∞, thus for brevity, we defer the explicit results of all theorems to the Appendix. In Theorem 1, we focus on terms in the numerator. From Theorem 1, one can see that our generalization bound has a linear dependency on the maximum factor size of a given sample set, that is s = maxi∈[n] |Hi|. The terms of order O(log(·)) is small enough and typically can be ignored. For terms log 1 2 (n2) and log 1 2 (sk), if we consider the case n2 ≥ sk, our result suggests that
in the generalization error, the influence of sample size n is larger than the label set cardinality, which implies that if the sample size n is large enough, hyper-parameter n will dominate the generalization performance of structured prediction. While for the label set cardinality, our bound has a logarithmic dependency, that is log(di) (Since the factor size s is typically far smaller than label size di [18], we just consider the label set size di in the term log 1 2 (sk)). We now compare our bound with the related work in the factor graph decomposition [18, 51]. When the function class F is assigned with p = 1 or p = 2, the generalization bounds in [18] areR(`add(ρf )) ≤ R̂(`add(ρf ))+O( s √ di
ρ √ n
+ √
log 1/δ n ) and
R(`mult(ρf )) ≤ R̂(`mult(ρf )) +O(Ms √ di
ρ √ n
+ √
log 1/δ n ) (` add and `mult are defined in Application 1). Thus the generalization bounds in [18] have a linear dependency on s but a square-root dependency on di, i.e., √ di. The term √ di may be extremely large since it is the largest label set cardinality of the factor in Hi. If we consider the extremely large number of possible labels, the bounds in [18] may be divergent. Thus, by comparison, our generalization bound has a significant improvement. [51] studies the specific surrogate loss `add, and they also provide a logarithmic dependency on the label set cardinality. Besides, by considering stationary β-mixing stochastic process [47], they also provide interesting generalization analysis for learning with weakly dependent data. Unfortunately, their generalization bounds and proof techniques are limited to this specific loss. Compared with their results, our bound is applicable for any Lipschitz continuity losses. In other words, so long as the surrogate loss is Lipschitz continuous w.r.t. the margin function, our bound is applicable. This assumption is pretty mild, as we have discussed below Assumption 1. The proof of Theorem 1 is provided in Appendix A. Additionally, the Lipschitz continuity constant µ is typically small. We present two applications for examples in the following.
Application 1. [18] provides two margin loss, the additive and the multiplicative margin losses, that can be used to guarantee many existing structured prediction algorithms, defined as:
`add(ρf (x, y)) = Φ ∗ (
max y′ 6=y L(y′, y)− 1 ρ
[f(x, y)− f(x, y′)] ) ,
`mult(ρf (x, y)) = Φ ∗ (
max y′ 6=y
L(y′, y) ( 1− 1
ρ [f(x, y)− f(x, y′)]
)) ,
where Φ∗(r) = min (maxy,y′ L(y, y′),max(0, r)) for any y, y′ ∈ Y . For the additive and the multiplicative margin losses, we show that they are 1ρ and M ρ Lipschitz continuous w.r.t. the margin function ρf respectively in Appendix B, thus we have Corollary 1.
Corollary 1 Fix ρ > 0. For any δ > 0, with probability 1 − δ over the sample S of size n, the following holds for all f ∈ F ,
R(f) ≤ R(`add(ρf )) ≤ R̂(`add(ρf )) +O
( s lnn
ρ √ n
( log 1 2 (n2) + log 1 2 (sk) ) + √ log 1/δ
n
) ,
R(f) ≤ R(`mult(ρf )) ≤ R̂(`mult(ρf )) +O
( Ms lnn
ρ √ n
( log 1 2 (n2) + log 1 2 (sk) ) + √ log 1/δ
n
) ,
where s = maxi∈[n] |Hi|, k = maxi∈[n] |Hi|di, and where di = maxh∈|Hi| |Yh|.
Application 2. In many structured prediction applications, such as natural language processing and computer vision, people may wish to take advantage of very rich features. However, using a rich family of hypotheses can lead to overfitting. In this application, we further consider to derive learning guarantees for ensembles of structured prediction rules that explicitly account for the differing complexities between families, called Voted Risk Minimization (VRM) [15, 18]. Assume that we are given p families F1, ..., Fp of functions mapping from X × Y to R. Define the ensemble family G = conv(∪pi=1Fi), that is the family of functions g of the form g = ∑T t=1 αtft, where α = (α1, ..., αT ) is in the simplex ∆ and where, for each t ∈ [1, T ], ft is in Fit for some it ∈ [1, p]. Consider the following loss function:
`addτ (ρg(x, y)) = Φ ∗ (
max y′ 6=y L(y′, y) + τ − 1 ρ
[g(x, y)− g(x, y′)] ) ,
`multτ (ρg(x, y)) = Φ ∗ (
max y′ 6=y
L(y′, y) ( 1 + τ − 1
ρ [g(x, y)− g(x, y′)]
)) ,
where τ can be seen as a margin term that acts in conjunction with ρ. We assume these families F1, ..., Fp have differing complexities. This setting is the same as [18], and under this setting we have Corollary 2 for VRM.
Corollary 2 Fix ρ > 0. For any δ > 0, with probability 1 − δ over the sample S of size n, the following holds for all g ∈ G,
R(g) ≤ R̂(`add1 (ρg)) +O ( s lnn
ρ √ n
( log 1 2 (n2) + log 1 2 (sk) ) + √ C(n, p, ρ, |Y|, δ) ) ,
R(g) ≤ R̂(`mult1 (ρg)) +O ( Ms lnn
ρ √ n
( log 1 2 (n2) + log 1 2 (sk) ) + √ C(n, p, ρ, |Y|, δ) ) ,
whereC(n, p, ρ, |Y|, δ) = d 1ρ2 log( |Y|2ρ2n 4 log p )e log p n + log 2/δ n , s = maxi∈[n] |Hi|, k = maxi∈[n] |Hi|di, and where di = maxh∈|Hi| |Yh|.
Remark 2 [Sketch of Applications 1 and 2.] Corollary 1 shows that, under the same assumption, our generalization bounds improve results in [18] from a square-root dependency √ di to a logarithmic dependency log(di). For VRM in Application 2, [18] shows that R(g) ≤ R̂(`add1 (ρg)) + O( 1ρ√n ∑T t=1 αt<G(Fkt) + √ C(n, p, ρ, |Y|, δ)) and R(g) ≤ R̂(`mult1 (ρg)) + O( M ρ √ n ∑T t=1 αt<G(Fkt) + √ C(n, p, ρ, |Y|, δ)). Thus, the generalization bounds of VRM in [18]
are dominated by term ∑T t=1 αt<G(Fkt), where <G(Fkt) is factor graph Rademacher complexity of the function class Fkt (please refer to their paper for definition). The explicit dependency of their bounds on parameter vector α reveals that learning even with highly complex hypothesis sets could be possible so long as the complexity term. However, Corollary 2 shows the explicit bounds rather than the <G(Fkt) term and suggests that the generalization bounds of VRM do not depend on the parameter vector α, which implies that a huge number of complex families are allowed. Therefore, it is feasible to use rich families in conjunction with highly complex families in structured prediction. Furthermore, in Theorem 2 of [18], the term <G(Fkt) is of order √ maxi∈[n] |Hi|2di√ n
, where di = maxh∈|Hi| |Yh|, which presents a square-root dependency on the label size, that is √ di. By comparison, our bounds are tighter. Therefore, the generalization bounds in Corollary 2 provide further insights into the learning guarantees of VRM. The complete proof of Corollary 1 and Corollary 2 is provided in Appendix B and C, respectively.
Remark 3 We now consider two examples in practical situations and further demonstrate our results.
(1.) Consider the pairwise Markov networks with a fixed number of substructures l studied by [60, 18], the corresponding factor graph in our paper has l nodes, |H|i = l, and the maximum size of Yh is di = c2 if each substructure of a pair can be assigned one of c class. c may be extremely large in some practical applications, for instance, in part-of-speech tagging. We further consider the Hamming loss L(y, y′) = 1l ∑l k=1 Iyk 6=y′k as in [60, 18]. If we apply Corollary 1 to the pairwise Markov network and divide the bound through by l to normalize the loss as in [60, 18], we obtain
generalization bounds of O (
lnn ρ √ n
( log 1 2 (n2) + log 1 2 (lc) ) + √
log 1/δ n
) , which has a logarithmic
order dependency on the output space size.
(2.) Consider the special case of structured prediction: multi-class classification, we have |H|i = 1 and di = c, where c is the number of classes. c may be extremely large since many challenging applications, such as photo and video annotation and web page categorization, can involve tens or hundreds of thousands of classes [62]. For instance, practical web page categorization datasets AmazonTitles-3M and Amazon-3M have 2,812,281 labels, which are much larger than the training samples (please refer to [5]).

heading: 3.2 Smoothness Dependent Case
text: Assumption 2 Assume that ` is β-smooth, that is |∇`(s)−∇`(t)| ≤ β|s− t|.
Assumption 2 is a pretty mild condition. Both the square hinge loss `(ρf ) = (1 − ρf )2+ and the square margin loss `(ρf ) = (1ρf≤0 + (1− ρfρ−1)10<ρf≤ρ)2 satisfy Assumption 2 [36].
Theorem 2 Under Assumption 2, ∀v > max(1, √ 2
2M ), for any δ > 0, with probability 1− δ over the sample S of size n, the following holds for all f ∈ F ,
R(f) ≤ R(`(ρf )) ≤ max { v
v − 1 R̂(`(ρf )), R̂(`(ρf )) +O ( βs2 log4 n
n
( log(n2) + log(sk) ) + log( 1δ )
n
)} ,
where s = maxi∈[n] |Hi|, k = maxi∈[n] |Hi|di, and where di = maxh∈|Hi| |Yh|.
Remark 4 [Sketch of Theorem 2.] Theorem 2 suggests that the generalization bound of structured prediction is of order O( s 2
n ) when the surrogate loss is smooth w.r.t. the margin function (we hide the logarithmic term). Since the sample size n is typically far larger than s, this bound is clearly sharper than bounds in Theorem 1. Compared with [18] whose bounds are of order √
maxi∈[n] |Hi|2di√ n
where di = maxh∈|Hi| |Yh|, our generalization bound in Theorem 2 is of order maxi∈[n] |Hi|2
n . And if we consider the case di ≥ maxi∈[n] |Hi|2 which is very possible since the label set cardinality di can be far larger than the factor size |Hi|, our bound is sharper than bounds in [18] whether in terms of the sample size n or the order of the numerator. Compared with [51], our bound has a linear convergence rate on the sample size n, which is also faster than the slower order O( 1√
n ) in [51].
Overall, Theorem 2 obtains a sharper bound not only with a faster convergence rate on the sample size n but with the logarithmic dependency on the label set cardinality. We now compare our results with the stability-based results. [41, 42, 40] use the stability tool to investigate the generalization bounds of structure prediction. Denote the number of examples as n and the size of each instance as m, under suitable assumptions and hidden logarithmic terms, the latest paper [40] provides the generalization bounds of O( 1√
nm ) by the stability and PAC-Bayes combination. Compared with
this bound, our generalization bounds decrease faster on the sample size n. If we consider the case of n > m, our bounds are tighter and have a faster convergence rate. In addition, our results are based on the factor graph decomposition approach, which is beneficial for providing the explicit dependency on the properties of the factor graph and helps us show the dependence on the number of possible labels explicitly. And our theoretical analysis reveals that structured prediction can be generalized well even if it has a vast output space and shows that there can be a tighter generalization bound under what conditions. We further compare our bounds with PAC-Bayesian-based bounds. In a seminal work, [46] provides PAC-Bayesian margin guarantees for the simplest classification task, binary classification. The generalization bounds in Corollary 1 and Theorem 3 in [46] are of slow order Õ( 1√
n ). The authors then use the PAC-Bayesian theorem to provide generalization bounds
for structured prediction tasks involving language models [45]. [26, 4, 22] further extend [45] to more complex learning scenarios of structured prediction: [26] extends [45] to the maximum loss over random structured outputs; [4] extends [45] to Maximum-A-Posteriori perturbation models; [22] extends [45] by including latent variables. However, regarding the sample size n, generalization bounds in the related work [45, 26, 4, 22] are all stated in slow order Õ( 1√
n ). Their analysis typically
build on the looser form of McAllester’s PAC-Bayesian bound [46] and the global Rademacher complexity [2], which leads to the slow order generalization bound. To our best knowledge, how to use the PAC-Bayesian framework to establish fast rates for structured prediction is still unexplored. It would be very interesting to derive sharper PAC-Bayesian guarantees for structured prediction since a salient advantage of PAC-Bayes is that this theory requires little assumptions [24]. The complete proof of Theorem 2 is provided in Appendix D. Besides, the smooth constant β is also typically small. We provide Application 3 for examples in the following.
Application 3. Consider the square hinge loss
`sh(ρf (x, y)) =
( 1− ( f(x, y)−max
y′ 6=y f(x, y′) ))2 + ,
which is β = 2 smooth w.r.t. the margin ρf , thus the generalization bound of `sh for structured prediction is immediate.
Remark 5 We now compare our results with the implicit embedding-based results [12, 13, 53, 52, 8, 11, 58, 7]. They mostly provide the convergence rate of slow order O( 1
n1/4 ) w.r.t. the sample
size n. The sharpest bound among the related work is provided by [8], which considers the implicit embedding framework from [12], and leverages the fact that learning a discrete output space is easier than learning a continuous counterpart, deriving refined calibration inequalities. Then, [8] uses exponential concentration inequalities to turn the refined results into fast rates under the generalized Massart’s or Tsybakov margin condition. Firstly, regarding the sample size n, Theorem 6 in [8] shows a excess risk bound of O(n− 1+α2 ), where α > 0 and is a parameter of generalized Tsybakov margin condition, characterizing the hardness of the discrete problem. Although [8] proposes this interesting generalization bound, the bound is presented in expectation. By comparison, our result is presented in high probability, which is beneficial to understand the generalization performance of the learned model when restricted to samples as compared to the rates in expectation. Secondly, generalization error bounds studied in [8] require stronger assumptions. For instance, Theorem 6 is proposed under Bilinear loss decomposition condition, exponential concentration inequality condition, generalized Tsybakov margin condition, bounded loss, and finite prediction space condition. Compared with [8], our bounds are presented without the margin conditions. Recently, there has been some work devoted to providing fast classification rates without standard margin conditions in binary classification, for instance, [6]. Moreover, our Lipschitz continuity condition and smoothness condition are assumed on the margin function. It is easy to construct a surrogate loss which is Lipschitz continuous or smooth w.r.t. the margin function. Finally, our generalization bounds are built upon the factor graph decomposition approach, which is beneficial for providing the explicit dependency on the number of possible labels. In our analysis, we not only improve the dependence on the sample size n, but also the dependence on the output space size, explaining that structured prediction can still generalize well in the extremely large output space.

heading: 3.3 Capacity Dependent Case
text: Definition 1 (Covering Number [70, 29]) Let F be class of real-valued fucntions, defined over a space Z and S := {z1, ..., zn} ∈ Zn of cardinality n. For any > 0, the empirical `∞-norm covering number N∞( ,F , S) w.r.t S is defined as the minimal number m of a collection of vectors v1, ...,vm ∈ Rn such that (vji is the i-th component of the vector vj)
sup f∈F min j=1,...,m max i=1,...,n
|f(zi)− vji | ≤ .
In this case, we call {v1, ...,vm} an ( , `∞)-cover of F w.r.t. S. Furthermore, the following covering number is introduced:
N ( ,F , ‖ · ‖∞) := sup n sup S N∞( ,F , S).
Before presenting Theorem 3, we use the property Ψ(x, y) = ∑ h∈H Ψh(x, yh) to decompose Ψ(x, y) and introduce the following space (different from F defined in (1)):
Fh := {Ψh(x, yh) 7→ 〈w,Ψh(x, yh)〉 : w ∈ RN , ‖w‖p ≤ Λp}. (2)
Assumptions 3 and 4 are assumptions w.r.t. the covering number bounds (space capacity) on Fh.
Assumption 3 (polynomial covering number) We assume that the function class defined in (2) satisfies that
logN ( ,Fh, ‖ · ‖∞) ≤ γp p
> 0,
where 0 < p < 2 and γp is a positive constant dependent on p.
Assumption 4 (logarithmic covering number) We assume that the function class defined in (2) satisfies that
logN ( ,Fh, ‖ · ‖∞) ≤ D logp( γ ) > 0,
where p, D and γ are three positive numbers.
We take the linear function class and the kernel function class for instances to demonstrate the two assumptions. Theorem 4 in [69] and Corollary 9 in [28] give the covering number bound of linear
function class, which satisfies Assumption 3 with p = 2. Lemma 19 in [48] extends Theorem 4 in [69] to reproducing kernel Hilbert space, which satisfies Assumption 3 with p = 2. If the linear function class is specified by the commonly used Gaussian kernel, the covering number bounds in Theorem 15 of [48] and Theorem 5 of [21] satisfy Assumption 3 with 0 < p ≤ 1. For more covering number bounds of linear function classes, please refer to [64]. Application 4 in the following provides a covering number bound satisfying Assumption 4 if the parameter w is restricted to a euclidean ball.
Remark 6 Classes that fulfill Assumption 3 are known as satisfying the uniform entropy condition [63]. The popular RKHSs of Gaussian, polynomial and finite rank kernels satisfy the polynomial covering number assumption [23]. Many popular function classes satisfy the logarithmic covering number assumption when the hypothesis class is bounded: Any function space with finite VCdimension [63, 54], including linear functions and univariate polynomials of degree k (for which d = k + 1, and p = 1) as special cases; Any RKHS based on a kernel with rank D when p = 1 [9]; Any unit ball B ⊂ RD with fixed ∈ (0, 1) [57].
Theorem 3 With different space capacity assumptions, we have the following different results: 1) Under Assumptions 1 and 3, ∀v > max(1, √ 2
2M ), for any δ > 0, with probability 1 − δ over the sample S, we have
R(f) ≤ R(`(ρf )) ≤ max { v
v − 1 R̂(`(ρf )), R̂(`(ρf )) +O
( γpµ psp
n 2 p+2
+ log( 1δ )
n
)} ,
for any f ∈ F , where 0 < p < 2, s = maxi∈[n] |Hi|, and γp is a positive constant dependent on p. 2) Under Assumptions 1 and 4, ∀v > max(1, √ 2
2M ), for any δ > 0, with probability 1 − δ over the sample S, we have
R(f) ≤ R(`(ρf )) ≤ max { v
v − 1 R̂(`(ρf )), R̂(`(ρf )) +O
( D logp(µsγ √ n)
n +
log( 1δ )
n
)} ,
for any f ∈ F , where p > 0 and s = maxi∈[n] |Hi|, and where p, D and γ are three positive numbers.
Remark 7 [Sketch of Theorem 3.] Theorem 3 suggests that, when the function space Fh satisfies the specific space capacity assumption, the generalization bound of structured prediction can have no dependency on the cardinality of the label set, just presents the dependency on the factor size: sp or logp(s). It also implies that the factor node size s can presents a lower orderO(sp) (when 0 < p < 1) or O(logp(s)) than linear dependency O(s) in Theorem 1 or square dependency O(s2) in Theorem 2. From Theorem 3, one can also see that, under the polynomial covering number assumption, this bound is sharper than results in Theorem 1 w.r.t. the sample size n when 0 < p < 2. Under the logarithmic covering number assumption, the bound presents faster order O( 1n ) w.r.t. the sample size n. Overall, Theorem 3 obtains generalization bounds that have no dependency on the cardinality of the label set and have faster convergence rates than O( 1√
n ) simultaneously. Theorem 3 in [51]
also provides a generalization bound not dependent on the label space size via algorithmic stability. However, their bound requires a convex surrogate loss w.r.t. the parameter w and considering the regularization, so that the regularized empirical risk is strongly convex w.r.t. w, which may be restrictive for margin-based surrogate losses [18]. Moreover, this bound is derived in expectation. As a comparison, our bound is obtained with high probability. The proof of Theorem 3 is provided in Appendix E. Besides, as showed in Corollary 2, the Lipschitz continuity constant µ is typically small. An example satisfying Assumption 4 is given in Application 4.
Application 4. We assume that any ‖Ψh(x, yh)‖ is bounded by B, which is a standard assumption in structured prediction. For example, [18] assumes maxi,h,yh ‖Ψh(x, yh)‖2 ≤ r2 where r2 is a constant. Thus, there holds that |〈w1,Ψh(x, yh)〉− 〈w2,Ψh(x, yh)〉| ≤ B‖w1−w2‖ for any w1, w2 and sample (x, y) ∈ X × Y , which implies that 〈w,Ψh(x, yh)〉 is B-Lipschitz w.r.t. w. Assume that for any w ∈ W ,W ⊂ RN is an unit ball. According to Lemma 1.1.8 in [57], any unit ball has the logarithmic covering number bound. Therefore, combined with the Lipschitz assumption, we have
logN ( ,Fh, ‖ · ‖∞) ≤ N log ( 3B ) , (3)
which satisfies Assumption 4. Substituting (3) into Theorem 3, the generalization bound of structured prediction in this setting is immediate.
Remark 8 [Sketch of Application 4.] To compare our bounds with the extensively studied multiclass classification task where |Hi| = 1, di = c, and where c is the number of classes of multiclass classification task, we consider our bounds in the multi-class classification case, which is O(N log(µ √ n)
n ). To the best of our knowledge, this is the first high probability bound not dependent on the label size c in multi-class classification. In related work of multi-class classification [34, 33, 36, 55, 50, 65, 48, 49, 44, 18, 35], [18] shows a convergence rate of order O( c√
n ) under 2-
norm regularization condition; [34] shows a convergence rate of order O( log 2(nc)√ n
) under `∞-norm Lipschitz continuous condition; [33] shows a convergence rate of order O( √ c n ) under `2-norm Lipschitz continuous condition; [36] shows a convergence rate of order O( √ c log3(n) n ) under `2-norm Lipschitz continuous, smoothness and low noise conditions; [35] shows a convergence rate of order O( √ c n ) under `2-norm Lipschitz continuous and decay of singular value conditions; [65] shows a convergence rate of order O( log 3(nc) n ) under `∞-norm Lipschitz continuous and strong convexity conditions (Due to length limit, we just compare our result with the recent work). However, our result shows that if the loss is µ-Lipschitz continuous w.r.t the margin function and the conditions in Application 4 are satisfied, the generalization bound of multi-class classification can show a fast convergence rate of order O(N log( √ n)
n ). Note that in this result, we do not assume strong curvature conditions: strong convexity or smoothness. If we consider the case N log( √ n) ≤ log3(nc), our bound is also sharper than the state-of-the-art generalization bound in multi-class classification, under much milder assumptions.
Excess Risk Bounds. Define f̂∗ = arg minf∈F R̂(`(ρf )) and f∗ = arg minf∈F R(`(ρf )), the excess risk of structured prediction is R(`(ρf̂∗))−R(`(ρf∗)), which demonstrates the performance of the empirical risk minimizer learned on the samples on the population level and is also an important measure for understanding the generalization performance [2, 38, 39, 66, 37, 67]. Assume that R(`(ρf ) − `(ρf∗))2 ≤ BR(`(ρf ) − `(ρf∗)) for some B > 0 and every f ∈ F , we have the following Corollary.
Corollary 3 With different space capacity assumptions, we have the following different results:
1) Under Assumptions 1 and 3, for any δ > 0, with probability 1− δ over the sample S of size n, we have
R(f) ≤ R(`(ρf̂∗)) ≤ R(`(ρf∗)) +O ( γpµ psp
n 2 p+2
+ log( 1δ )
n
) .
for any f ∈ F , where 0 < p < 2, s = maxi∈[n] |Hi|, and γp is a positive constant dependent on p. 2) Under Assumptions 1 and 4, for any δ > 0, with probability 1− δ over the sample S of size n, we have
R(f) ≤ R(`(ρf̂∗)) ≤ R(`(ρf∗)) +O ( logp(µsγ √ n)
n +
log( 1δ )
n
) .
for any f ∈ F , where p > 0, s = maxi∈[n] |Hi|, and p, D and γ are three positive numbers.
Remark 9 [Sketch of Corollary 3.] The excess risk bounds in Corollary 3 have the same order convergence rates as results in Theorem 3. And the meaning of these results has been discussed in Remark 7 and Remark 8. We provide the complete proof of Corollary 3 in Appendix F. Considering the length limit, some discussion of this paper is postponed to the appendix.

heading: 4 Conclusion
text: In this paper, we are towards sharper generalization bounds for structured prediction. The analysis is based on the factor graph decomposition approach, which can help shed new light on the role played by the graph in generalization. We present state-of-the-art generalization bounds from different perspectives. Overall, the bounds presented have answered the three questions posed in Section 1. We believe our theoretical findings can provide deep insights into the learning guarantees of structured prediction. Additionally, we are also concerned about whether the convergence rate of structured prediction can reach faster order than O(1/n)? We will investigate this problem in future work and design new algorithms based on our theoretical analysis.

heading: Acknowledgment
text: We appreciate all the anonymous reviewers, ACs, and PCs for their invaluable and constructive comments. This work is supported in part by the National Natural Science Foundation of China (No. 62076234, No.61703396, No. 62106257), Beijing Outstanding Young Scientist Program NO.BJJWZYJH012019100020098, Intelligent Social Governance Platform, Major Innovation & Planning Interdisciplinary Platform for the "Double-First Class" initiative, Renmin University of China, China Unicom Innovation Ecological Cooperation Plan, Public Computing Cloud of Renmin University of China.

Review summaries:
Authors study generalization in the context of structured prediction based on factor graphs. Their goal is to improve the rates of existing generalization bounds, among their contributions we have:  1. Under Lipschitz continuity, an improvement from square root to logarithmic dependence on the size of the output space. 2. Under a smoothness condition, a faster convergence rate of $O(1/n)$, where $n$ is the sample size. 3. Under covering number assumptions, authors show a bound with no dependency on the output space size, simultaneously with faster convergence rates than $O(1/\sqrt{n})$.

The authors consider the problem of bounding the error between the true risk and the empirical risk for structured prediction with a large number of possible labels. By adding fairly weak assumptions that are satisfied for common cases, they improve the dependence on the number of labels $d$ from $O(\sqrt{d})$ to $O(\log d)$ and/or the rate of convergence from $1/\sqrt{n}$ to $1/n$. They then analyze the generalization risk when there may be an infinite number of labels but the family of scoring functions has small complexity as defined by covering number.

The paper provides generalization bounds for structured prediction learning with a more general setting where each input is associated with its own scoring function. The scoring functions are represented using factor graphs. The authors provide three main results and improve the dependency of the generalization error either on the number of samples or factor and label size. Three classes are considered smooth loss, Lipschitz loss and functions with controlled capacity (stated in terms of their covering number).