Towards Sharper Generalization Bounds for Structured Prediction
Authors: Shaojie Li
Yong Liu
Venue: NeurIPS 2021 Poster (2021)
Keywords: Generalization Bound
Structured Prediction
Learning Theory

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 $\mathcal{O}(\frac{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 $\mathcal{O}(\frac{1}{\sqrt{n}})$. In each scenario, applications are provided to suggest that these conditions are easy to be satisfied. 

Towards Sharper Generalization Bounds for Structured Prediction
Shaojie Li Yong Liu
'Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China BBeijing Key Laboratory of Big Data Management and Analysis Methods, Beijing, China 2020000277@ruc edu. en, w liuyonggsai pergggaairuu... edu.
Abstract
In this paper, we investigate the generalization performance of structured prediction learning and obtain statc-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. bounds that are not only a logarithmic dependency on the label set cardinality but faster convergence rate of order ( on the sample size n. scenario, we obtain bounds that do not depend on the label set cardinality and have faster convergence rates than O (.) ) In each scenario, applications are provided
the smoothness scenario, we provide generalization
space capacity
to suggest that these conditions are easy to be satisfied.
Introduction
Structured prediction [8 12 covers 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 the above tasks 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 [99] search- based structured prediction (20). maximum-margin markov network (60), image segmentation
[43. part-of-speech sarr-of-speech-taaging [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 [8 12 13
Several theoretical studies of structured prediction consider specific algorithm and simple loss such as Hamming loss [60] [6]] 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
Conresponding Author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

decomposition approach, implicit embedding approach, and stability approach. [22 45 26 4 provide PAC- PAC-Bayesian guarantees for arbitrary losses through the analysis of randomized algorithms using use implicit loss embedding to construct a connection between discrete output of structured prediction and regression, to investigate the generalization performance of structured prediction. [8] [1]] present generalization bounds for
count-based hypotheses. [12
13
53
52
g
58
7
general losses based on factor graph decomposition approach, which is proposed in the seminal work [8] [1 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 31,, whose scoring function can be seen a factor graph with both factor node size and substructure size equal to one.
is multi-class classification [34 33 36 55 50 65 48
49 44
Although the aforementioned works have provided generalization bounds from different perspectives, there are still some problems urgently to be solved in structured prediction.
(I.) 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 [2 provide the generalization bounds of order O vn
In implicit embedding approach, 12 13
58 7 provide the
convergence rate of order O (,,t)) and [53] of order O vT In the factor graph decomposition
approach, 18
51
present the generalization upper bounds of order O (
Also, in stability show the 1 (i) order bounds. Therefore, this raises a question: can the
approach, 41 42
40
convergence rate of structured prediction achieves faster order (
(2.) In structured prediction, the number of possible labels is potentially infinite [8] Thus it is important to obtain upper bounds that have 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 [8]. Therefore, our analysis focuses on the lower bound, [T]] studies the specific surrogate loss, and the upper bounds in [88 show square-rood 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 lower order dependency on the cardinality of possible labels or even no dependency?
based on the factor graph decomposition [8] 3 (1) However,
(3.) Although some work in multi-class classification [36 55 65 special structured prediction problem, have shown the faster convergence rate of order x w.r.t. the sample size n, it 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 simultancously?
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 slow convergence rate of order O Vn
w.r.t. the sample size n. Then, we assume the loss is smooth and intend to answer questions (L) and (3). Under this assumption, we obtain sharper bounds that not only have the faster convergence rate of order (()) on the sample size n but also have the logarithmic dependency on the label set cardinality. Furthermore, we consider the space -eeeedde assumptions: logarithmic covering number and polynomial covering number assumptions, which are commonly used in learning theory 32 69 (56) This setting attempts 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 than O
In the above three perspectives, we all provide applications to suggest that these conditions are easy to be satisfied in practice.
Vx
This paper is organized as follows. In Section 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.
2

---

2 Preliminaries
Notations. Let P be a probability measure defined on a sample space A' x y with X E 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 [8]. We thus assume that V can be decomposed into I substructures: Y = =)1 to substructure i. Take the simple webpage collective classification task for example [59]. each V is webpage label and y/ is a joint label for an entire website. If assume each ) E {0. 1}. the number of possible labels to )/ is exponential in the number of substructures 7, i.e., |)] = 2
3% where )/ is the set of possible labels that can be assigned
Factor graphs and scoring function. In structured prediction, we aim learn scoring function f f= X' x + R. Let F. be a family of the scoring function. For each f E F, we define the predictor if as: for each z E X, fxx arg max Eyy f(r, y). Moreover, we assume that the scoring function f can be decomposed as a sum [6] 60. 30 181, which is standard in structured prediction and can be formulated via the notation of factor graph [8]] A factor graph G is bipartite graph, and is represented as a tuple G (V, H, E), where
[1, (1.. I} is set of variables nodes, H a set of factor nodes, and E is set of undirected edges between variable node and factor node. Let (h) be the set of variable nodes connected to the factor h by an edge and 3% be the substructure set cross-product 8% [I 3%. Based on the above notations, the scoring function f(x, y) can be decomposed as a sum of functions fa [8], with an element X' and an element yn. E 3h as arguments:
f(z. v) fa
NEH
In this paper, we consider the more generally setting: for each example (æs, yr), the corresponding factor graph may be different, that is, G( G, = ([4]. Hj, E.). A special case of this setting is that, for example, when the size I, of each example is allowed to vary and where the number of possible labels [V] is potentially infinite. Figure shows different examples of factor graphs.
Learning. In order to measure the success of prediction, we use loss function L: L R. to measure the dissimilarity 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 [8]] such as the Hamming loss, defined as: L(y, v/) = Eim Fye for two outputs y, s/ E V, with y (y1.-.., 31) and y = (v/1 v/), edit-distance loss in natural language and speech processing applications, or other losses [18] [0]. Given a training set S = {(11,g1 ,....... (zn, yn)} of size being independently drawn from the underlying distribution P, our goal is to learn a hypothesis f e 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(e,n P(
However, the above mentioned loss function f [f(x), y) is typically the 0 - 1 loss of f. which hard to handle in machine learning. Therefore, one usually consider surrogate losses [3 [8]
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 (xr, y) defined as:
p,(2, v) f(x, v) max f(x, v'
We consider the scoring function f of the form f(z, y) (w, v (a, v)), where &i is feature mapping from X' x ) to R such that (x y) ΣnCH V (x. yh) due to the decomposition of f [18 And we define the following scoring function space:
= (x (w, (a, v)) w E R.W. ||ll S Ap),
where ||l||p = -Ei |ws ()) Then, the corresponding surrogate loss function class is defined as:
L, = (lp(1, = ((ps(a,))) F
where ép is the surrogate loss of L. We assume Ep is bounded by M, which implies that < L L(f(z),)) L(f(x),)) ( I E(pr(x, v)) < M since L is positive, the cost will only occur
3

---

h
h
h
(a)
(b)
(c)
Figure I: Example of factor graphs. (a) represents an example of pairwise Markov network decom- position: far y) fh, (z, y1, 92) + fhz (I, y2 ys); (b) represents example of factor graph that having sequence structure: f(x, y) = fh, (a, y1, y2) + fha (z, y2, ya) + fha (z, ya y1); ;; (c) represents tree-structured factor graph.
when the margin function value is negative and the surrogate loss e is larger than L. Additionally, define the empirical risk of any scoring fuunction f as
R(e(ps))
lo (Zi, Yi. f),
and the expected risk as
R(E(p))) (( (2,(
Clearly, we have R(F) S R(((p))).
3
Main Results
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(2) w.r.t. the sample size n and showing logarithmic dependency, or even no dependence, on the label set cardinality. In each case, provide applications to suggest that these conditions easy to be satisfied.
3.1 Lipschitz Continuity Dependent Case
Assumption Assume that é is y-Lipschitz continuous, that is
(E(l) {(+) S ullt - s/-
Assumption is a pretty mild assumption. The hinge loss E(ps) = (1 - -pr)+ and the margin loss ((pr) = Loy <o + (1 prp - satisfy Assumption
33 Morcover, the loss of truncated margin functions in [25] satisfies Assumption[] The addiuie and the multiplicative margin loss provided by [88] which covers many existing structured prediction algorithms, satisfy Assumption (see Corollary for details).
Theorem Under Assumption for any O, with probability 1 over the sample of size n, the following holds for all
us jusln In n Vn
(1og2 (n²) + log (sk) + log 1/5
R(f) < R(E(p))) < R(((p))) +
n
where s max HH) 1, max HH, and where d, max 1D/
Remark [Sketch of Theorem I Since our task is to prove bounds with better rates, that is, which decrease fast with n - oc, thus for brevity, we defer the explicit results of all theorems to the Appendix. In Theorem we focus on terms in the numerator. From Theorem [ one our generalization bound has linear dependency on the maximum factor size of a given sample set, that is mmx [.,)- The terms of order Ollog-)) is small enough and typically can be
that
ignored. For terms log (n²) and log² (sk), if we consider the case n² > 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, performance of structured prediction. While for the label set cardinality, our bound has a logarithmic dependency, that is (o,( (Since the factor size 8 is typically far smaller than label size d; [88 we
n will dominate the generalization
just consider the label set size d: in the term log (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 = or
p= = 2, the generalization bounds in 18 are R(Eadd (ps)) S A((eadd (ps)) + O (evd:
log 1/4 and
PV'
R( ((emalt (py)) S ie( f (pr)) + O( (Mevd Pvn
log 1/5 (Radd and greast are defined in Application
1). Thus the generalization bounds in [8] have a linear dependency on but a square-root dependency
on d; i.e. vd. The term vdz may be extremely large since it is the largest label set cardinality of the factor in H,. If we consider the extremely large number of possible labels, the bounds in [18] may be divergent. Thus, by comparison, our generalization bound has significant improvement. [5]] studies the specific surrogate loss gadd, and they also provide a logarithmic dependency on the label set cardinality. Besides, by considering stationary f-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 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 [ The proof of Theorem 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 guarantee many existing structured prediction algorithms, defined as:
godd (p) v)) = =
max L(V' +'
[f(x. v) - -(c../1))
p
grall (p)(z,)) = 4-
max L(y v) 1 1f - f(z, 1/ ((2.21))) 1'
P
where (r) = min (maxy.y/ L(y. y²), max(0, r)) for any y. E y. For the additive and the multiplicatiie margin losses, we show that they are 1 and M Lipschitz continuous w.r.t the margin function Ps respectively in Appendix B, thus we have Corollary []
Corollary Fix p > O. For any 8 > O, with probability 1 - 5 over the sample S of size n, the following holds for all f F,
slun pVn
log 1/6
R(J) S Regadd (pF)) < (()ad((ps)) +
(log2 + logg (sk)) + V n
MMlnnn PVn
(oogt(n)) + log log+(sk)) + llg 1/8
R(f) S R(emult (p;)) - A((mmllt O
where: 8 maxie|m] [4,) k= = max |Hyld, and where d: = max 1aa
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 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) [8). Assume that we are given p families Fi,..., F, of functions mapping from X' x y to R. Define the ensemble family G = cono(Ui_ F.). that is the family of functions g of the form g Σt= aefe, where (Q.,.... ar)) is in the simplex A and where, for each t E [1,T], fo is in F;, for some is E [1. pl. Consider the following loss function:
1
(add(1 v)) = Φx
maxx L(v', ,v) + ( g(x,, o(m,D''))
v V'
e (muit((p v)) σ-
max L(y', ,y)
[1 -
1
[o(x, 100-g(00,0 o(r.
y'
p
5

---

where T can be seen as a margin term that acts in conjunction with We assume these families Fi....,F; Fy have differing complexities. This setting is the same as [18] and under this setting we have Corollary 2 for VRM.
Corollary 2 Fix p > O. For any 8 > O, with probability 1 - ô over the sample S of size n, the following holds for all 9 E g.
s slun (logè (n²) + log (sk)) - VCn, C(
R(g)= S 1 (pa)) +0
PVn
R(g)= S (((erai (p₂)) + 0
(p²))
Mslun
(log (n²) + log (sk)) (sk)(ss)) + /C,n.
p/n
where C(n, Ps 13),8) = [ log
logg log 2/6 8 maxie|m] [Hg), k = max4e[x] HHd d,
4log
and where d, |H (3%).
Remark 2 [Sketch of Applications and 2.J Corollary shows that, under the same assump-
tion, our generalization bounds improve results in [18] from a square-root dependency /d, to a logarithmic dependency log(d.). For VRM in Application 2. (18) shows that R(g) S
R(eTad (py)) + +0( PVT Ets a.R (Fr.) + VC(n, P. P. (3), 6)) and R(g) S R((TTai (pg))
OG PVR El aOR (Fa.) + (C(n,pp,
Thus, the generalization bounds of VRM in [18
dominated by term E R where (FFx)) is factor graph Rademacher complexity of the function class Fk. (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 shows the explicit bounds rather than the RC (F&,) term and suggests that the generalization bounds of VRM do not depend on the parameter vector a, which implies that a huge number of complex families are allowed. Therefore, is feasible to use rich families in conjunction with highly complex families in structured
prediction. Furthermore, in Theorem 2 of 18] the term NC (Fi,,) ) is of order /maxig(m) Pd.
where d, MH, [iiel which presents a square-root dependency on the label size, that is /d,. 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 and Corollary 2 is provided in Appendix B and C, respectively.
VV
Remark 3 We now consider two examples in practical situations and further demonstrate our results.
(1.) Consider the pairwise Markov networks with fixed number of substructures 1 studied by 660 18. the corresponding factor graph in our paper has nodes, HH = I, and the maximum size of Va is de = è² 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') v I Iy as in [60 [8] If we apply Corollary | to the pairwise
Markov network and divide the bound through by 1 to normalize the loss as in 60 18] obtain
generalization bounds of O pvm (Iog* (n²) + log (Ie)) + = log1/6) which has logarithmic order dependency on the output space size.
(2.) Consider the special case of structured prediction: multi-class classification, we have [d] = 1 and d; = c, where c is the number of classes. 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 [22. For instance, practical web page categorization datasets AmazonTTitls--MM and Amazon-3MM have 2,812,281 labels, which are much larger than the training samples (please refer to [5))
3.2 Smoothness Dependent Case
Assumption 2 Assume that e is B-smooth, that is [V((s) ve(t)) s -|s-
Assumption 2 is pretty mild condition. Both the square hinge loss E(ps) (1 pr) and the
square margin loss {(pr) (Lpyso + (1- psp " )ocppro) satisfy Assumption 2 [36].

---

Theorem 2 Under Assumption 2 Ve > m1x for any 8 > O, with probability 1 ô over the sample S size n, the following holds for all f FFF,
/2
2M
R(F) S R(((ps)) I max
v
R((eps)), R(((()))
log" n (log(n²) + log(sk)) + log(z)
+0
n
where: s |mX [1 k- max [Hidd and where d, |H, [3%
Remark 4 [Sketch of Theorem 2 Theorem Suggesss that the generalization bound of structured
prediction is of order O 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 this bound is clearly
Compared with [8 whose bounds are of order y /maxxe(()) [H,]dd Pd.
sharper than bounds in Theorem |
Vn
where d; = max H.] [a,,, our generalization bound in Theorem is of order max,e(1] [M And
if we consider the case d, 2 [n] |H,2² which is very possible since the label set cardinality d; can be far larger than the factor size |, our bound is sharper than bounds in [18] whether in
terms of the sample size n or the order of the numerator. Compared with [5T], our bound has a linear
convergence rate on the sample size which is also faster than the slower order O (ir in (51).
Overall, Theorem obtaains 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. [4] 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 Vam by the stability and PAC-Bayes combination. Compared with this bound, our generalization bounds decrease faster on the sample size If consider the case of n > m, our bounds are tighter and have a faster convergence rate. In addition, our results are based 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 A.C-Bayesian-basee bounds. In a seminal work, [46] provides PAC-Bayesian margin guarantees for the simplest classification task, binary classification. The generalization bounds Corollary 1 and Theorem in (46) are of slow order Ō ). The authors then use the PAC-Bayesian theorem to provide generalization bounds for structured prediction tasks involving language models 45
further extend [45] to 26 extends
26
more complex learning scenarios of structured prediction:
to the maximum loss over random structured outputs; [4] extends [45] to Maximum- A-Possrrro-oottriiin perturbation models; 22] extends [45) by including latent variables. However, regarding the sample size n, generalization
45
bounds the related work [45] 26 22 are all stated slow order Ó (+) Their analysis typically
build on the looser form of McAllester's PAC-Bayesian bound [46] and the global Rademacher
complexity 22) which leads 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 derive sharper PAC-Bayesian guarantees for structured prediction since 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
11 (I-(F(e.)) max f(r v/) ) t'
Ca (p)((,))))
(f(z,))
which is B = 2 smooth w.r.t. the margin Pj. thus the generalization bound of fsh for structured prediction is immediate.
Remark 5 We now compare our results with the implicit embedding-based results 12 13 52
g. I. 58 7. They mostly provide the convergence rate of slow order O ((177) w.r.t. the sample
7

---

size The sharpest bound among the related work is provided by [ which considers the implicit embedding framework from [22], and leverages the fact that learning discrete output space is easier than learning a continuous counterpart, deriving refined calibration inequalities. Then, B 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 Theorem in [8] shows
excess risk bound of On -- where a 0 and is a parameter of generalized Tsybakov margin condition, characterizing the hardness of the discrete problem. Although g 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 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. our analysis, we not only improve the dependence on the sample size n, but also the dependence the output space size, explaining that structured prediction can still generalize well in the extremely large output space.
3.3 Capacity Dependent Case
Definition (Covering Number (70 29 (70,29 Let F be class of real-valued fucntions, defined over space Z and S == (Z,,..., ) 2 of cardinality n. For any 6 > O, the empirical lec-norm covering number Noole, wan S is defined as the minimal number of a collection of vectors T E I2" such that (v. is the i-th component of the vector va)
sup min max If(z)) v/15c.
FEF j= i=
In this case, we call {v! number is introduced:
v an (c, of F.E.t. S. Furthermore, the following covering
N(e,F,11 1lx)) St.
Before presenting Theorem we use the property (x. v) = Ene μ (2, yn) to decompose (z, y) and introduce the following space (different from F defined (I))
Fn V mn) + (w, (n, un)) RN, 1|w|l < Ap).
Assumptions 3 and are assumptions w.r.t. the covering number bounds (space capacity) on Fn--
Assumption (polynomial covering number) We assume that the function class defined satisfies that
log,N(e, Fh.
Tp 0, (1x0) <
c²
where 0 p < and "/p is positive constant dependent p.
Assumption 4 (logarithmic covering number) We assume that the function class defined in 2
satisfies that
(e, Fu,ll (1o0) (log((2) <> 0,
where p. D and ry 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 kemel Hilbert space, which satisfies Assumption 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 of 21 satisfy Assumption [ with < p S 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 if the parameter w restricted to a cuclidean ball.
Classes that fulfill Assumption 3 are known as satisfying the uniform entropy condition 633. The popular RKHSs of Gaussian, polynomial and finite rank kernels satisfy the polynomial covering number assumption [33] Many popular function classes satisfy the logarithmic covering number assumption when the hypothesis class is bounded: Any function space with finite VC- dimension 63 [4], including linear functions and univariate polynomials of degree l (for which d = k + 1, and p 1) special cases; Any RKHS based kernel with rank D when p 9
Remark 6
Any unit ball B c R with fixed E (0, 1) (57
Theorem 3 With different space capacity assumptions, we have the following different results:
1) Under Assumptions and 3 Ye > max(1, sample S, we have
). for any 8 > O, with probability 1 - ô over the 2M
v2
{ v R(E(p))), R(((ps)) + +0 12
(TpliPP log(
R(f) S R(((ps)) & max
for any F, where 0 < <<<<pp 2, maxie[n] Hil) and 7pp is a positive constant dependent on p.
2) Under Assumptions 1 and sample S, we have
4 Vu max(1, L2 2M
for any d > O, with probability 1 - ô over the
v ((((p))).&R((ppp)) +o ( loog"(usr )
log(!) n
R(f) & R(((p))) max
for any J E F, where p > and s maxie[]] Hz,,, and where p. D and y are three positive numbers.
Remark 7 [Sketch of Theorem Theorem suggests that, when the function space Fa 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
the factor size: 8 or log"(s) (s). ). It also implies that the factor node size s can presents a lower order ((s²) (when 0 < p < 1) or Olog"(ss (s)) than linear dependency ((s) in Theorem [ or square dependency ((s") 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 w.r.t. the sample size when < p < Under the logarithmic covering number assumption, the bound presents faster order ((2) 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 ((+))) simultaneously. Theorem 3 in [51] also provides generalization bound not dependent 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 [8]. Moreover, this bound is derived in expectation. As comparison, our bound is obtained with high probability. The proof of Theorem 3 provided in Appendix E. Besides, as showed in Corollary 2 the Lipschitz continuity constant μ is typically small. An example satisfying Assumption is given in Application 4.
Application 4. We assume that any 1 yr)l Il is bounded by B. which is a standard assumption in structured prediction. For example, [18] assumes max,, h.ys || [ (2, 1ll r2 where r2 is constant. Thus, there holds that ((w,, V yn)) (W2, V (2. yh. ]>| < Bl[wy - wall for any Wi, W2 and sample (x., y) E X' x y, which implies that (w, V (zr, yx)) is B-Lipschitz w.r.t. w. Assume that for any w E W, W C R 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, have
3B
Fn, (1oo) S N N
which satisfies Assumption 4 Substituting 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 multi- class classification task where |H 1, d; c, and where is the number of classes of multi- class classification task, we consider our bounds in the multi-class classification case, which is O(* N log(uvm)) 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 [4
33
36
55 50
65
48
49
44
18
35),
[8] shows convergence rate of order O
((=e))
under 2-
Vn
norm regularization condition;
[3 shows a convergence rate of order O log (nc)
under -nom
vn
Lipschitz continuous condition;
33 shows a convergence rate of order (VV under f--norm
Lipschitz continuous condition; [3 shows a convergence rate of order O log
under fnrmrrm
Lipschitz continuous, smoothness and low noise conditions; [35] shows a convergence rate of order
(VC) (()) under n-rm Lipschitz continuous and decay of singular value conditions; [65] shows a
convergence rate of order O( Log" log"( (ne)) under &o 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 j--Lipschitz continuous w.r.f the margin function and the conditions in Application 4 are satisfied, the generalization bound of multi-class classification can show fast convergence rate of order O [m) Note that in this result, we do not assume strong curvature conditions: strong convexity smoothness. If we consider the case N log(v'i log"(ne) (ne), our bound is also sharper than the state-of-the-art generalization bound multi-class classification, under much milder assumptions.
Excess Risk Bounds. Define fr = arg argmingez R(((p)) and f arg minjer R(((p))), the
excess risk of structured prediction is ((((pp-))-R(((pp)) R(((p)-)), which demonstrates the performance
of the empirical risk minimizer learned on the samples the population level and is also important measure for understanding the generalization performance [2] 38 39
66
37 67 Assume
that R(((p)) E(pr))) S BR(((ps) - {(ps-)) for some B > and every f E F, we have the following Corollary.
Corollary 3 With different space capacity assumptions, we have the following different results:
1) Under Assumptions 7 and for any >> with probability - 5 over the sample S of size n, we have
R() < R( < R(((ps-) + O Tpp"s log(?)
n
for any f E.F. where 0 < <p <, maXie(n] HH), and "/p is positive constant dependent p. 2) Under Assumptions 7 and for any with probability 8 over the sample of size n, we have
R()) S R(E(pg.)) R(((()))) +0 0 (lgg((ss//i) log(g)
n
n
for any f ETF, where p > 0, s max He), and p, D and 7/ are three positive numbers.
Remark [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 & 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.
4 Conclusion
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 ofte--ofthheart generalization bounds from different perspectives. Overall, the bounds presented have answered the three questions posed in Section [ 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 theoretical analysis.
10

---

Acknowledgment
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 N0.BBJW2Y1H0120111000000200
Intelligent Social Governance Platform, Major Innovation & Planning Interdisciplinary Platform for the "Double-Fire Class" initiative, Renmin University of China, China Unicom Innovation Ecological Cooperation Plan, Public Computing Cloud of Renmin University of China.
References
[1] G. BakIr, T. Hofmann, B. Schölkopf, A. J. Smola, and B. Taskar. Predicting structured data. 2007.
[2] P. L. Bartlett, O. Bousquet, S. Mendelson, et al. Local rademacher complexities. The Annals of Statistics, 3394):1477-1537, 2005.
[3] K. Bello, A. Ghoshal, and Honorio. Minimax bounds for structured prediction based on factor graphs. In International Conference on Artificial Intelligence and Statistics, pages 213-222, 2020.
[4] K. Bello and J. Honorio. Learning latent variable structured prediction models with gaussian perturbations. arXiv preprint arXiv:1805.092111 2018.
[5] K. Bhatia, K. Dahiya, H. Jain, P. Kar, A. Mittal, Y. Prabhu, and M. Varma. The extreme classification repository: Multi-label datasets and code, 2016.
[6] O. Bousquet and N. Zhivotovskiy. Fast classification rates without standard margin assumptions. Information and Inference: A Journal of the IMA, 2021.
[7] L. Brogat-Motte, A. Rudi, C. Brouard, J. Rousu, and F. d' A'chh Buc. Learning output embed- dings structured prediction. arXiv preprint arXiv:2007.1477 14703, 2020.
[8] V. Cabannes, A. Rudi, and F. Bach. Fast rates in structured prediction. arXiv preprint arXiv:2102.00760, 2021.
[9] B. Carl and H. Triebel. Inequalities between eigenvalues, entropy numbers, and related quantities of compact operators in banach spaces. Mathematische Annalen, 251(2):129-13) 133, 1980.
[10] H. Choi. Efficient structured surrogate loss and regularization in structured prediction. arXiv preprint arXiv:/809.0553 2018.
[11] C. Ciliberto. F. Bach, and A. Rudi. Localized structured prediction. arXiv preprint arXiv:1806.000 024002, 2018.
[12] C. Ciliberto, L. Rosasco, and A. Rudi. A consistent regularization approach for structured prediction. Advances in neural information processing systems, pages 4412 44220, 2016.
[13] C. Ciliberto, I..
Rosasco, and A. Rudi. A general framework for consistent structured prediction with implicit loss embeddings. Journal of Machine Learning Research, 21(98): 2020.
[14] M. Collins. Parameter estimation for statistical parsing models: Theory and practice of distribution-free methods. In New developments in pursing technology, pages 19-55. 2004.
[15] C. Cortes, P. Goyal, V. Kuznetsov, and M. Mohri. Kernel extraction via voted risk minimization. Feature Extraction: Modern Questions and Challenges, pages 72-89, 2015.
[16] C. Cortes, Kuznetsov, and Mohri. Ensemble methods for structured prediction. In International Conference on Machine Learning, pages 1134- 2014.
[17] C. Cortes, V. Kuznetsov, M. Mohri, D. Storcheus, and S. Yang. Efficient gradient computation for structured output learning with rational and tropical losses. Advances Neural Information Processing Systems, pages 68 10-6811, 2018.

---

[18] C. Cortes, V. Kuznetsov, M. Mohri, and S. Yang. Structured prediction theory based on factor graph complexity. Advances in Neural Information Processing Systems, pages 2514-2522. 2016.
[19] Cortes, M. Mohri, J. Weston, A general regression framework for learning string- -triiggg--ttingg mappings. Predicting Structured Data, 2(4), 2007.
[20] H. Daumé, J. Langford, and D. Marcu, Search-based structured prediction. Machine learning. 75(3):297-325, 2009.
[21] M. Farooq and I. Steinwart. Learning rates for kernel-based expectile regression. Machine Learning, 108(2):203-221) 2019.
[22] A. Ghoshal and J. Honorio. Learning maxtein-aaposstrroon perturbation models for structured prediction in polynomial time. In International Conference on Machine Learning, pages 1754 2018.
[23] C. Gu. Smoothing spline ANOVA models, volume 297. Springer Science & Business Media, 2013.
[24] B. Guedj. primer on pac-bayesian learning. International Conference on Machine Learning, 2019.
[25] Y. Guermeur. Combinatorial and structural results for gamma--si-ddmensions. arXiv preprint 1809,0000 2018.
[26] Honorio and T. Jaakkola. Structured prediction: from gaussian perturbations to linear-time principled algorithms. arXiv preprint 000045,508.00945, 2015.
[27] D. Jurafsky and C. Manning. Natural language processing. Instructor, 212(998):3482,, 2012. 2012.
[28] S. M. Kakade, K. Sridharan, and A. Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. In Advances in Neural Information Processing Systems 21, pages 793-800, 2008
[29] A. N. Kolmogorov and V. M. Tikhomirov. e-entropy and E-capacity of sets in function spaces. Uspekhi Matematicheskikh Nauk, 14(2):3-86, 1959.
[30] J. Lafferty, A. McCallum, and F. C. Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. 2001.
[31] A. Ledent, W. Mustafa, Lei, and M. Kloft. Norm-based generalisation bounds for deep multi-class convolutional neural networks. In AAAI Conference on Artificial Intelligence, pages 8279-8287, 2021.
[32] Y. Lei, I.. Ding, and Bi. Local rademacher complexity bounds based on covering numbers. Neurocomputing, 21 21::200330, 2016.
[33] Y. Lei, Ù. Dogan, A. Binder, and M. Kloft. Multi-class svms: From tighter data dependen generalization bounds to novel algorithms. arXiv preprint 150..01900604359, 2015.
[34] Y. Lei, Ü. Dogan, D.-X. Zhou, and M. Kloft. Data-dependent generalization bounds for multi-class classification. IEEE Transactions on Information Theory, 6565):2995,,021, 2019.
[35] J. Li, Y. Liu, and W. Wang. Learning vector-valued functions with local rademacher complexity. CoRR, 2019.
[36] J. Li, Y. Liu, R. Yin, H. Zhang, L. Ding, and W. Wang. Multi-class learning: From theory to algorithm. In Advances in Neural Information Processing Systems, pages 1586-1595, 2018.
[37] S. Li and Y. Liu. Sharper generalization bounds for clustering. In International Conference on Machine Learning, pages 6392 00022 2021.
[38] Y. Liu, S. Liao, S. Jiang, L. Ding, H. Lin, and W. Wang. Fast cross volidavalio for kernel-based algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(5): 1013))1083-1996 2020.
12

---

[39] Y. Liu, J. Liu, and S. Wang. Effective distributed learning with random features: Improved bounds and algorithms. In International Conference on Learning Representations, 2021.
[40] B. London, B. Huang, and L. Getoor. Stability and generalization in structured prediction. Journal of Machine Learning Research, 17(221):7808-
2016.
[41] B. London, B. Huang, B. Taskar, and L. Getoor. Collective stability in structured prediction: Generalization from one example. In International Conference on Machine Learning, pages 2013.
[42] B. London, B. Huang, B. Taskar, and L. Getoor. PAC-Bayesian Collective Stability. In International Conference on Artificial Intelligence and Statistics, pages 585-594, 2014.
[43] A. Lucchi, Y. Li, and P. Fua. Learning for structured prediction using approximate subgradient descent with working sets. In Computer Vision and Pattern Recognition, pages 1987-1994, 2013.
[44] A. Maurer. A vector-contraction inequality for rademacher complexities. In International Conference on Algorithmic Learning Theory, pages 3-17, 2016.
[45] D. McAllester. Generalization bounds and consistency. Predicting structured data, pages 247-261, 2007.
[46] D. A. McAllester. Simplified pac-bayesian margin bounds. In Lecture notes in computer science, pages 203-215,
2003. 2003.
[47] M. Mohri and A. Rostamizadeh. Stability bounds for stationary d-mixing and f-mixing processes. Journal of Machine Leaniing Research, 11(26):89-814, 2010.
[48] K. Musayeva. Generalization Performance of Margin Multi-category Classifiers. PhD thesis, Université de Lorraine, 2019.
[49] K. Musayeva. Sample complexity result for multi-category classifiers of bounded variation. arXiv preprint wwXiv:2003.09176 2020.
[50] K. Musayeva, F. Lauer, and Y. Guermeur. A sharper bound on the rademacher complexity of margin multi-category classifiers. In ESANN, 2018.
[51] W. Mustafa, Y. Lei, A. Ledent, and M. Kloft. Fine-gra -ea-ggra generalization analysis of structured output prediction. In International Joint Conference on Artificial Intelligence, pages 2841-2847, 2021.
[52] A. Nowak- F. Bach, and A. Rudi. A general theory for structured prediction with smooth convex surrogates. arXiv preprint arXiv: 2019.
[53] A. Osokin, F. Bach, and S. Lacoste-Julien. On structured prediction theory with calibrated convex surrogate losses. arXiv preprint 17X:0.1703.00403, 2017.
[54] A. Pakes and D. Pollard. Simulation and the asymptotics of optimization estimators. Economet- rica: Journal of the Econometric Society, pages 1027-1057, 1989.
[55] H. W. Reeve and A. Kaban. Optimistic bounds for multi-output prediction. arXiv preprint arXiv:2002.09769 2020.
[56] W. Rejchel. On ranking and generalization bounds. Journal of Machine Learning Research, 13(5), 2012.
[57] Rigollet and J.-C. Hütter. High dimensional statisties. Lecture notes for course 18S997, 813:814, 2015.
[58] A. Rudi, C. Ciliberto, G. M. Marconi, and L. Rosasco. Manifold structured prediction. arXiv preprint arXiv: 1806.80000000 09908, 2018.
[59] B. Taskar, P. Abbeel, and Koller. Discriminative probabilistic models for relational data. arXiv preprint 1rXiv:131..0604, 2012.
13

---

[60] B. Taskar, C. Guestrin, and D. Koller. Max-margin markov networks. In Advances in Neural Information Processing Systems, pages 25-32, 2003.
[61] I. Tsochantaridis, Joachims, T. Hofmann, Altun, and Y. Singer. Large margin methods for structured and interdependent output variables. Journal of machine learning research, 6(9), 2005.
[62] M. Varma and Langford. Nips workshop on extreme classification. [Online]. Available: https://manikvarmaaacom wwtthub.ii/eveett//XX. 2013.
[63] Wellner et al. Weak convergence and empirical processes: with applications statistics. Springer Science & Business Media, 2013.
[64] R. C. Williamson, A. J. Smola, and B. Schölkopf. Entropy numbers of linear function classes.
In Annual Conference on Computatioonl Learning Theory, pages 309-319, 2000.
[65] L. Wu, A. Ledent, Y. Lei, and M. Kloft. Fine-grained generalization analysis of vector-valued learning. In AAAI Conference Artificial Intelligence, 2021.
[66] R. Yin, Y. Liu, W. Wang, and D. Meng. Sketch kernel ridge regression using circulant matrix: Algorithm and theory. IEEE Transactions on Neural Networks, 31(9):3512 -324,, 2020.
[67] R. Yin, Y. Liu, W. Wang, and D. Meng. Distributed nyström kernel learning with communica- tions. In International Conference on Machine Learning. pages 12019-12028, 2021.
[68] D. Zhang, L. Sun, and W. Li. A structured prediction approach for statistical machine translation. In Proceedings of the Third International Joint Conference Natural Language Processing, 2008.
[69] Zhang. Covering number bounds of certain regularized linear function classes. Journal of Machine Learning Research, 2(Mar):527-55M 2002.
[70] D.-X. Zhou. The covering number in learning theory. Journal of Complexity, 18(3):739-767, 2002.
14


Reviews:
[{"review_id": "OACzDrSGc10", "reviewer": "Reviewer_rCxV", "summary": "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:\n\n1. Under Lipschitz continuity, an improvement from square root to logarithmic dependence on the size of the output space.\n2. Under a smoothness condition, a faster convergence rate of $O(1/n)$, where $n$ is the sample size.\n3. 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})$.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Here I present my review along the axes from the NeurIPS reviewing guidelines:\n\n**Originality**\n\n- Are the tasks or methods new? \n  - The generalization bounds are new.\n\n- Is the work a novel combination of well-known techniques?\n  - Yes. The work applies ideas from concentration inequalities, Rademacher complexity, and covering numbers, to name a few.\n\n- Is it clear how this work differs from previous contributions? \n  - Yes.\n\n- Is related work adequately cited?\n  - Mostly yes; however, there are some literature missing. For instance, upper bounds from London et al. (2016), in the context of stability, derive bounds that also depend on the size of each example.\n\n\n**Quality** \n\n- Is the submission technically sound? \n  - I have not checked the proofs in detail but they seem sound.\n\n- Are claims well supported (e.g., by theoretical analysis or experimental results)? \n  - No experiments are provided.\n\n- Are the methods used appropriate? \n  - Yes, the theoretical tools used in the proofs are adequate for the analyses.\n\n- Is this a complete piece of work or work in progress? \n  - Complete work.\n\n- Are the authors careful and honest about evaluating both the strengths and weaknesses of their work?\n  - I was not able to see a discussion on the limitations of their analysis.\n\n\n**Clarity** \n\n- Is the submission clearly written? \n  - No. See below.\n\n- Is it well organized? \n  - Yes. \n\n- Does it adequately inform the reader? \n  - N/A.\n\n\n**Significance** \n\n- Are the results important? \n  - If proofs are correct, yes. These results are of interest to the learning theory community.\n\n- Are others (researchers or practitioners) likely to use the ideas or build on them? \n  - Perhaps. Theorists might be interested on improving the bounds or provide milder assumptions.\n\n- Does the submission address a difficult task in a better way than previous work? \n  - N/A. No algorithm is presented.\n\n- Does it advance the state of the art in a demonstrable way? \n  - The results presented improve the rates existing upper bounds, although I am not completely sure if the bounds are fully comparable to existing ones given the set of assumptions.\n\n- Does it provide unique data, unique conclusions about existing data, or a unique theoretical or experimental approach?\n  - N/A.\n\n# Questions / Comments\n\nI have mixed feelings about this manuscript. I believe the results (if correct) are worthy of publication. However, there are *a lot* of mistakes in the writing and, thus, the paper requires an extensive editing before publication. For that reason, the current state of the manuscript does not meet the bar to be published at NeurIPS.\n\nI will comment on some issues I found in the *introduction* as it is just unrealistic to list all existing mistakes.\n\n1. In the first sentence: CV, NLP, CB are not problems but *fields*.\n2. L19: compute vision -> computer vision\n3. L19: \"..., protein...\" -> \"..., and protein...\"\n4. L21: \"to above tasks\" -> \"to the above tasks\"\n5. L22: \"that the natural\" -> \"that a natural\". Otherwise, what is that \"natural loss\"?\n6. L28: \"Compared with\" -> \"Compared to\". The point is to contrast, right?\n7. L31: \"bound studying\" is confusing. \n8. L33: \"consider the specific algorithm and the simple\" -> replace both \"the\" with \"an\" and \"a\", respectively.\n9. L34: \"more work considers\". Seems odd, \"other works consider\"?\n10. L35: \"general loss.\" -> \"general losses\" or \"a general loss.\"\n11. L40: \"general loss based\" -> \"general losses based\"\n12. The sentence from L41 to L43 is very disconnected. There is no a connection word to the previous sentences, and also it has an error at L41 \"there has\".\n13. L44: using \"these\" is also odd. Better to use \"the works above\" or \"the aforementioned works\"\n14. The use of [I.], [II.], [III.] looks very odd as well. There is an \"enumerate\" environment in Latex for that, roman listing is available as well.\n15. L48: \"..., [40] of\" -> \"..., and [40] of\"\n16. L50: \"there raises a question\" is also incorrect.\n17. L51: \"achieves\" -> \"achieve\"\n18. L52: Can the number of labels be infinite? It is typically exponential on the input size. What is an example of infinite number of *discrete* labels?\n19. L54: \"can provide the explicit\" sounds odd.\n20. L56: \"shed\" -> \"sheds\" as it refers to the approach (singular).\n21. L63: \"more difficult and complex\", what is the difference between difficult and complex?\n22. L64: \"problem\" -> \"problems\"\n23. L64: \"wonder to know\". I am not sure if that phrase even exists.\n\nI have listed several potential errors *just* in the introduction. I cannot even mention the ones throughout the rest of the manuscript.\n\n---\nI thank the authors for their response. I am increasing my score to 5 as I believe the technical contributions are relevant. However, the manuscript requires a serious revision on the writing, thus, I cannot increase my score further.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "Bq62UqGQi-5", "reviewer": "Reviewer_Mdym", "summary": "The paper investigates the generalization performance of structured prediction learning where the scoring function can be formulated via the notation of factor graphs. In three separate settings, the work derives state-of-the-art generalization bounds with fast convergence rates and weak dependency on the number of possible labels. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n**Originality**: \n\n- The paper derives state-of-the-art generalization bounds with different mild conditions imposed on the loss and the capacity of the hypothesis space. The results are general and seem to be applicable to various learning contexts. \n\n- On the other hand, it's hard to pinpoint which technical contributions of the work are instrumental to the derivation of the results:\n   - The most novel technique seems to appear in the proof of Proposition 1 that bounds the covering number of the function class $\\mathcal{F}_{\\rho}$, where the nonlinearity of the margin are bypassed by an intermediate linear function class. However, that is also a problem for multiclass learning, for which comparable bounds have been obtained. Is this a new technique that pertains to structured prediction?\n   - For the rest of the proof, aspects that are unique to structured prediction, such as factor graph, rarely appears. It is worth highlighting such contributions in the discussions (more on this below).\n\n\n**Quality and Clarity**: \n\n- In general, the paper is well-written and well structured. The work seems to be built upon established literature and the review of related works is informative. The ideas are presented intuitively and the proofs are rigorous.\n\n- While the results of the work are very impressive, the paper would be greatly strengthened by more discussions on the relevant context: \n   - What are the main difficulties in obtaining those bounds and what analytical tools were constructed to address the issues?\n   - What are the distinct characterization that set structured prediction apart from other contexts with similar bounds (such as multiclass classification) that requires significant technical adjustments ?\n\n- The paragraph \"Margin and loss function class\" contains some typos and misuse of notation: \"surogate\"; $\\ell_\\rho(f, x, y)$ vs $\\ell_p(x, y, f)$; $\\rho_{f(x, y)}$ vs $\\rho_{f}(x, y)$; the mathematical expression after the introduction of the surrogate loss (follow \"that is\") is incomprehensible \n\n\n**Significance**:\n\n- The problem studied in this paper is important, and the derived results advance the state of the art in a demonstrable way. \n- Regardless of technical novelties, the paper lays out a complete framework that others can rely on for future works in this direction. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "n/a", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "B7nu2uit6xh", "reviewer": "Reviewer_44Ms", "summary": "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).", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main contribution of the paper is a unified generalization bound that has simultaneously better dependency on the cardinality of possible labels and the sample size n. \n\nThe results are all solid, and the proofs seem to be fine with when I checked them in passing. The proofs are all based on Rademacher complexity analysis and local Rademacher complexity analysis and bounding them using covering numbers by Dudley’s inequality and generic chaining. \n\nOverall, the results of the paper are interesting, but the writing and presentation can be significantly improved. Besides, I am interested in author’s answer to my comment about the reference [6].\n\n- The paper is hard to read. It has many typos and unpolished statements. For the main paper, the authors could dispense with many terms and keep it to a minimum for better readability.\n\n- The paper [6] provides faster that 1/n convergence, but this is not discussed in the main paper.  The idea of factorization is also present there. It is important to compare this reference with the results of the paper, since it potentially provides better sample complexity.\n\n- The dependency on the sample size in the current analysis is limited to 1/n or 1/\\sqrt{n}. Is this an artifact of using Rademacher complexity analysis? I wonder if Rademacher complexity analysis permits getting better convergence than this. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "2WZaaiY-J_X", "reviewer": "Reviewer_i4W4", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall I found the paper to be fairly clear and theoretically interesting. The authors improve the best known generalization results for important cases of structured learning. They show faster convergence of the theoretical loss functions and better dependence on the number of labels. Additionally, the proofs of these results seem theoretically interesting.\n\nThe paper can do a better job connecting to practice by proving examples where the framework holds and when there is a large number of labels. Currently the paper is purely theoretical and abstract. The authors can improve the paper by\n(1) describing practical situations where there is a large number (or even infinite) labels.\n(2) describe practical or theoretically relevant situations where the covering number assumptions holds. \n\nThe section with covering numbers is a bit unclear. An example problem where the covering number assumption holds can improve the clarity of the assumption. Additionally a practical problem where the assumption holds and/or there are an infinite number of labels can improve the impact of these results.\n\nOverall I lean towards accept due to the theoretical results, however the paper can be improved by providing more insight into how the results (specifically the improvement in convergence for large/infinite label situations and the results that assume reasonable covering number) can improve the impact of the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No issues.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proves generalization bounds for structured prediction that are sharper than existing bounds. In particular, under certain conditions, they obtain the "fast rate" of $\tilde{O}(1/n)$. Also of interest is the fact that the bounds are logarithmically dependent on the cardinality of each output variable; meaning, the bounds accommodate very large label sets -- which is the case for things like sentence completion or object classification. The key technical innovation that enables the tighter bounds seems to be a refined analysis of the factor graph representation.

The reviews were mixed. The biggest complaint (shared by multiple reviewers) is that the paper is difficult to read. Having only skimmed it myself, I agree that there are a bunch of grammatical/syntactical errors that should have been caught before submission, but in this case I don't think it's enough (on its own) to warrant rejection; the paper is readable. These types of mistakes can be fixed in a camera-ready after a detailed proofreading. **I _strongly_ suggest the authors go over the paper "with a fine-toothed comb" (or ask someone else to).**

Other than the writing, the presentation seems pretty good. I think it was wise of the authors to present the main results in asymptotic notation, to make them easier for the reader to digest. Similarly, it was wise to defer proofs (which are quite involved) to the appendix and give just proof sketches. That said, Reviewer Mdym makes a good point that "it's hard to pinpoint which technical contributions of the work are instrumental to the derivation of the results." The authors responded, and I hope their explanation makes it into the paper.

Another complaint is that the paper ignores some related works (London et al., JMLR 2016; Maurer & Pontil, COLT 2009; McAllester, COLT 2013). The authors responded to these suggestions, providing convincing comparisons, during the discussion period. I ask them to please add this discussion to the paper.

As for the content, the results are solid. I'm glad that progress is being made on generalization in structured prediction. It's nice that the paper gives bounds for both the margin-rescaling (additive) and slack-rescaling (multiplicative) form of the max-margin loss.

It's worth noting that the paper is entirely theoretical, with no experiments. While this situation is not unusual, it's becoming more common these days for theory papers to include a numerical study that tests the assumptions or evaluates the bounds on real data, to see if the bounds are still meaningful. Since the paper's primary claim is that these bounds are tighter than others, it would be interesting to see if the claim holds in practice. Are these bounds meaningful when others are vacuous? So, while I think it's OK to not provide experiments, I think the paper would have been stronger with experiments.

I am recommending Accept because the work is interesting and valuable, and I believe the problems (writing and related work) can be worked through for the camera-ready.
Decision: Accept (Poster)