Structured Prediction with Stronger Consistency Guarantees
Authors: Anqi Mao
Mehryar Mohri
Yutao Zhong
Venue: NeurIPS 2023 poster (2023)
Keywords: structured prediction
consistency
learning theory
natural language processing

Abstract: We present an extensive study of surrogate losses for structured prediction supported by *$H$-consistency bounds*. These are recently introduced guarantees that are more relevant to learning than Bayes-consistency, since they are not asymptotic and since they take into account the hypothesis set $H$ used. We first show that no non-trivial $H$-consistency bound can be derived for widely used surrogate structured prediction losses. We then define several new families of surrogate losses, including *structured comp-sum losses* and *structured constrained losses*, for which we prove $H$-consistency bounds and thus Bayes-consistency. These loss functions readily lead to new structured prediction algorithms with stronger theoretical guarantees, based on their minimization. We describe efficient algorithms for minimizing several of these surrogate losses, including a new *structured logistic loss*.

Structured Prediction
with Stronger Consistency Guarantees
Anqi Mao Courant Institute New York, NY 10012 aqmao@cims.o .nn..n..eee edu
Mehryar Mohri Google Research & CIMS New York, NY 10011 mohri@google.com
Yutao Zhong Courant Institute New York, NY 10012 yutaoucims nyu edu
Abstract
We present an extensive study of surrogate losses for structured prediction sup- ported by H--consistency bounds. These are recently introduced guarantees that are more relevant to learning than Bayes-consistency, since they are not asymptotic and since they take into account the hypothesis trivial JC-consistency bound can be derived for widely used surrogate structured prediction losses. We then define several new families surrogate losses, including structured comp-sum losses and structured constrained losses, for which we prove HC-conssstency bounds and thus Bayes-consistency. These loss functions readily lead to new structured prediction algorithms with stronger theoretical guarantees, based on their minimization. We describe efficient algorithms for minimizing several of these surrogate losses, including new structured logistic loss.
Ht used. We first show that no non-
Introduction
In most applications, the output labels of learning problems have some structure that is crucial to consider. This includes natural language processing applications, where the output may be sentence, sequence of parts-of-speech tags, parse tree, a dependency graph. It also includes image annotation, image segmentation, computer vision, video annotation, object recognition, motion estimation, computational photography, bioinformatics, and many other important applications.
Several algorithms have been designed in the past for structured prediction tasks, including Con- ditional Random Fields (CRFs) [Lafferty et al., 2001a, Gimpel and Smith, 2010], StructS [Tsochantaridis et al., 2005a], Maximum- Margin Markov Networks (M3N) [Taskar et al., 2003a]. sernel-regresssonn-aaeee
algorithms [Cortes et al., 2005, 2007], Voted CRF and StructBoost [Cortes al., 2016), beaech-based methods [Daumé III et al., 2009, Doppa et al., 2014, Lam al., 2015, Chang et al., 2015, Ross et al., 2011] and variety of deep learning techniques [Jurafsky and Martin, 2009, Vinyals et al., 2015a, Nadeau and Sekine, 2007, Zhang et al., 2008, Wu et al., 2016, Lucchi et al., 2013, Vinyals et al., 2015b], see Appendix A for more comprehensive list of references and discussion.
Structured prediction tasks inherently involve a natural loss function based substructures, which could be the Hamming loss, the n-gram loss, the adit-distance loss, or some other sequence similarity- based loss or task-specific structured loss. Many of the algorithms previously mentioned overlook this inherent structured loss by simply minimizing the cross-entropy loss. contrast, the surrogate loss functions minimized by algorithms such as CRFs [Lafferty et al., 2001a, Gimpel and Smith, 2010], M3N [Taskar al., 2003a], StruetSVMs (Tsochantaridis al., 2005a] or Voted CRF and StructBoost [Cortes et al., 2016] do take into account the natural structured loss of the task. But are these structured prediction loss functions consistent? What guarantees can we rely on when minimizing them over restricted hypothesis set that does not include all measurable functions? Can we derive nom-asympo guarantees?
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

This paper deals precisely with these theoretical problems in structured prediction.
Previous work. We include detailed discussion on consistency in structured prediction in Ap- pendix A. Here, we briefly discuss previous work by Osokin et al. [2017]. To our knowledge, this is one of the only studies proving Bayes-consistency for family of loss functions in structured prediction (see also [Nowak et al., 2020] and other related references in Appendix A). The surrogate losses the authors proposed are the following quadratic losses (see also [Zhang, 2004]) defined for any function / mapping X x y to R and any loss function E between output labels by
((I y) E X y
L quad (h, x. v) = Σ (((('' + h(xx8/)1² yrel
(1)
However, the authors only consider the hypothesis set of linear scoring functions. Moreover, the feature vector in their setting only depends on the input and ignores the label y. In many applications such as natural language prediction, however, it is critical to allow for features that depend both on the input sequence and the output sequence, parse tree, or dependency graph. Finally, in this formulation, the structured prediction problem is cast as a regression problem. Thus, as shown below, the loss function derived is non-standard, even in the binary classification case, where & = to is the zero-one loss and y = {v1, In this simple case, L [quad (h, x, y1 can be expressed as
quad (,,
Σ (V'o- h( v/)²² h(x,1)²² + (1 ((+ yrEy
This is not a typical formulation since it incorporates the magnitude of individual scores. In contrast, in standard binary classification scenario, only the difference between scores matters.
Structure of the paper. We present an extensive study of surrogate losses for structured prediction supported by H-coonsssenccy bounds. These are recently introduced guarantees that are more relevant to learning than Bayes-consistency, since they are not asymptotic and since they take into account the hypothesis set H used. We first show that no non-trivial H-coosistency bound even Bayes- consistency can be derived for widely used surrogate structured prediction losses (Section 3). We then define several new families of surrogate losses, including structured comp-sum losses (Section 4) and structured constrained losses (Section 5), for which we prove H-consistency bounds and thus cayes-consistency. These loss functions readily lead new structured prediction algorithms with stronger theoretical guarantees, based on their minimization. We also describe efficient gradient computation algorithms for several of these surrogate losses, including a new structured logistic loss (Section 6).
2 Preliminaries
Learning scenario. We consider the standard structured prediction scenario with the input space X and output space y (1,...,n). The output space may be discrete objects with overlapping structures, such as sequences, images, graphs, parse trees, lists, or others. We assume that the output can be decomposed into 1 substructures. The substructures could represent words or tokens for example, or other subsequences along sequence, resulting in the decomposition of the output space y as y = yj x x yr. Here, each y, represents the set of possible labels or classes that can be assigned to the j-th substructure.
Scoring function. Structured prediction typically formulated via scoring functions that map X x to R. which assign a score to each possible class 'j. Let H( be a family of such scoring functions. For any h H. we denote by h( its prediction for the input x: X. which is the output y é y that maximizes the score h(x,, y). that is, h(r) argmax,eey h(x, y), with a fixed deterministic strategy to break ties in selecting the label with the highest score. For simplicity, we choose the label with the highest index under the natural ordering of labels as the tie-breaking strategy. We denote by Hall the family of all measurable scoring functions.
Generalization error and target loss. Given a distribution D) over X x y and a loss function L:H x Xx x I. the generalization error of hypothesis h K and the best-in-class generalization error are defined as follows:
RL(h)
E (x.y)-
[L(h, 2,]] and Ri,or inf RLh).. hell
2

---

In structured prediction, the goal is to select a hypothesis h É HC with small generalization error with respect target loss function L L(h, 2. y), which can be written as L(h, x. y) = {(h(x),)) y) for some non-negative auxiliary function {(y', y) with any y' y. l is assumed to be symmetric, that is, (()'.)) = (V.. This is a natural assumption since all instances of that we are familiar with in structured prediction admit this property. A significant characteristic of structured prediction is that the target loss function can be decomposed along the substructures yg. As an example, we may use the Hamming loss as the target loss function, which is defined as Lham (h, y) haam (h(z), v). where hham (v', y) & Σ}=1 1uz+u; with any V/ VJ E Yy; can also use the zero-one loss the target loss function, which is defined as Lo-1 x, 3) f--1 y)), where lo-1 .) = y Note that Lo-1 can be viewed as special case of Lham when I = 1. We denote by Emax maxy E(V'. y) the maximal value of a target loss function. Without loss of generality, we assume that Lmax S 1, which can be achieved by normalizing the function f.
Consistency guarantees and surrogate loss. Optimizing the target loss functions in structured prediction for many choices of the hypothesis sets is NP-hard because they are not convex. One common method to address this issue is to resort to surrogate loss functions. Different surrogate loss functions readily lead to different structured prediction algorithms. A natural learning guarantee for such surrogate losses is Bayes-consistency which guarantees that minimizing the generalization error for surrogate loss Leur over Hall also leads to the minimization of generalization error for the target loss
Definition (Bayes-consistency). A surrogate loss Laur is Bayes-consistent in structured prediction. for any larget loss f, hypothesis h, E Halll and any distribution,
(R (hn) Raar Mall
0) (RL(hn) -Ri Ri
7-++000 5o
0).
(3)
Bayes-consistency is an asymptotic guarantee and does not take into account typical hypothesis sets used in structured prediction algorithms. such as linear models or neural networks. To tackle these issues, recent work by Awasthi, Mao, Mohri, and Zhong [2022a.b] propose a stronger consistency guarantee, referred to as H-consistencyy bounds, which are bounds relating the estimation error of the target loss to the estimation error of a surrogate loss (see also [Awasthi et al., 2021a,b, Mao et al., f023h,e,f, Zheng et al., 2023, Mao al., 2023b.g.d, Mohri al., 2023, Mao et al., 2023c,a, Awasthi et al., b))
Definition (FC-onnsstennyy bounds). Given a subset of the hypothesis class H Hal, surrogate loss Lour admits K-consixtency bound in structured prediction, if for some non-decreasing function f: TR. + Tk,,, a bound of the following form holds for any target loss E, hypothesis h H. and any distribution:
Ri (h) - -L $ 5 (RL (h) - -Ri RRn..x)))) .x).
As pointed out by Awasthi et al. [2022a.b], HC-ooniitency bounds are the faate-of-hhe-ee consistency guarantees for surrogate losses. They are much stronger and more informative than consssconn since they account for hypothesis sets H adopted and provide a quantitative, non-asymptotic relation between surrogate losses and target losses. H H-consistency bounds can imply Bayes-consistency when taking H to be Hanl In the next sections, we will present an extensive study of surrogate losses for structured prediction supported by H-consistency bounds.
Conditional regret and minimizability gap. We denote by p(x) = (p(z, 1)....)..d n)) the conditional distribution of Y given X x. Then, the conditional error of hypothesis h for loss function L. denoted by eL 2h, can be expressed as
EL (h, = E [[{(h(=),))]= (((())))(((2).))) yey
y
We further define the best-in-class conditional error and the conditional regret as e, ()C, infnem (1(,,)) and ( x) = e (h, ei (H,x)) respectively. The generalization error can then be rewritten (h) = [.(
key quantity appearing in K-consistency bounds is the minimizabillty gap My (H), which measures the difference between the best-in-class generalization error and the expected best-in- conditional error for a loss function and a hypothesis set H: Mr (H) = Ri (H) - EE [er (H,,)). This an inherent quantity that we cannot hope to minimize estimate. As shown by Steinwart [2007,
3

---

Theorem 3.2], the minimizability gaps vanish Mr (Hail = 0 for the family of all measurable functions. More generally, the minimizability gaps vanish when the best-in-class error coincides with the Bayes-error, that is, Ri (H) R2 (Han) [Awasthi et al., 2022b, Mao et al., 2023h].
The following result characterizes the best-in-class conditional error and the conditional regret for a target loss L, which will be helpful for proving JC-consistency bounds in structured prediction. We denote by Har) the set of all possible predictions on imput generated by hypotheses in H{: H(x)= = (h(z): Hy.. The proof is given in Appendix B.
Lemma 3. The best-in-class conditional ervor and the conditional regret for a target loss L in structured prediction can be expressed as follows:
(i)(())= min Ep(z,y)(eg/.)) y'H((w) yey
(,, Σ ((())))(((()))))) min Ep(a,)) y'e((a) yeyy
ycM
3 Structured max losses
In this section, we examine the loss functions associated to several prominent structured prediction algorithms. We show that, while they are natural, none of them is Bayes-consistent, which implies that they cannot be supported by H-coossstency bounds either. More generally, we consider the following family of surrogate loss functions proposed in [Cortes, Kuznetsov, Mohri, and Yang, 2016], which we refer to as structured max losses:
(ar, v) e xxxX
max (h, x, = max Pecy an (M(r,)) -Mx,, y'=y
(5)
where P.,; R - R. is upper bound on u ego for any RR, In this formulation, different choices of 4u, can lead to different structured prediction algorithms. Specifically, as shown by Cortes al. [201 6), the following choices of (v) recover many well-known algorithms:
p (v) max u(1 ((1+v)) v)): StructSVM [Tsochantaridis et al., 2005b].
(v) max (0, v): Max-Margin Markov Networks (M3N) [Taskar et al., 2003b).
(v) log(1 "" Conditional Random Field (CRF) [Lafferty al., 2001b].
4 (v) " StructBoost [Cortes al., 2016].
The following gives general negative result for L max that holds under broad assumptions.
Theorem 4 (Negative results of Lmax). Assume that n and that (v.(v) convex and non- increasing for u 1. Then, the max structured loss Liaxx is not Bayes-consistent.
The proof is included in Appendix C. It is straightforward see that the assumption of Theorem holds for all the choices of 4, listed above. Thus, the theorem rules out consistency guarantees for any of the loss functions associated the structured prediction algorithms mentioned above: StructS VM, M3N, CRF, Structboost. Furthermore, Theorem 4 provides negative results for broad and generalized family of loss functions, collectively referred as structured max loss. This extends the scope of existing research, as previous works had only addressed the inconsistency of specific instances within the structured max loss category, such as that of M3N [Osokin al., 2017, Ciliberto et al., 2016, Nowak et al., 2020].
4 Structured comp-sum losses
In this section, we first analyze the Voted CRF loss function, which incorporates the auxiliary loss function E in the CRF loss and which has been used in several previous studies. Next, we introduce a new family of loss functions for structured predictions that we prove to admit strong consistency guarantees.

---

4.1 Voted Conditional Random Field (VCRF)
We first study a family of surrogate losses called Voted Conditional Random Field (VCRF), which corresponds to the structured prediction algorithm defined in [Cortes et al., 2016]:
M(2.))
((z,y) e Xx y, L VCRR (h, -lgg Egeey eh(n.s/)+
log Σ
yyey
This loss function has also been presented as the softmax margin [Gimpel and Smith, 2010] or the reward-augnn augueeted maximum likelihood [Norouzi et al., 2016]. It can be viewed as the softmax variant of the M3N loss. Indeed, the loss function for M3N can be written as follows:
L(,, y) = ''
max(0, (0, Ely'. v) + h(,, v/) h(x,y))
(6)
If we replace the maximum function with the softmax, obtain
(h,,,,)) log Σ Jyey
max(0,
log
Σ Key
max 1, 1 W (7)
Next, we show that, as with the loss function for M3N, the VCRF loss function L LCRF is inconsistent. Theorem (Negative result of LVcRr). The Voted Conditional Random Field LVCRF is not Bayes- consistent.
The proof is included in Appendix D. The key observation in the proof is that the conditional error of VCRF loss function can be reduced to a specific form when the target loss function L decouples, which can lead
different Bayes classifier from that of the target loss function.
To the best of our knowledge, no prior studies in the literature have explored the consistency of the VCRF loss formulation. The most closely related discussions center around specialized instance of the multi-class logistic loss (also referred to as Conditional Random Field in that context), in which ((v'.y disappears within the framework of the Voted Conditional Random Field. The previous works by Osokin et al. [2017], Ciliberto et al. 6), Nowak et al. [2020] point out that the multi-class logistic loss cannot be consistent in structured prediction due to the absence of the target loss function within its formulation. Instead, our result shows that, even when integrating the target loss E(y',)) within its formulation, the Voted Conditional Random Field cannot be consistent.
Along with Theorem 4, these results rule out consistency guarantees for commonly used surrogate loss functions in structured prediction.
4.2 Structured comp-sum loss functions
In this section, we define a family of new loss functions for structured prediction that are not only Bayes-consistent but also supported by H--consistnncy bounds. These are loss functions that can be viewed as the generalization to structured prediction loss functions defined via a composition and sum, and that have been referred to as comp-sum losses in [Mao et al., 2023h]. Thus, we will refer to them as structured comp-sum losses. They are defined as follows:
v(r,y) exx L comp v,,
Σ {().,)) yeey
Σ [=sth(aas))) (8) E"
where ((y', v) = :0) non-decreasing auxiliary function. This formulation (8) can also be viewed as a weighted comp-sum loss, if we interpret ((-y) as a weight vector.
((' .8), 21 R. R, is a non-decreasing auxiliary function and 42 R + R,
Specifically, can choose (1) e" and (1 llo((), 41(1)= = v (1)) (1- )
10 and (v) 1 1 which leads new surrogate losses for structured prediction defined in Table 1. These surrogate losses are novel strict generalization of their counterparts in the standard multi-class classification case where & fo-1. More precisely, when = l0-1s comp coincides with the logistic loss [Verhulst, 1838, 1845, Berkson, 1944, 1951]; Leopip coincides with the sum- exponential loss [Weston and Watkins, 1998. Awasthi al., 2022b]; comp coincides with the
5

---

Table A new family of surrogate losses for structured prediction: structured comp-sun sum losses.
(1)
Name
Formulation
log(v)
Structured logistic loss
comp
Evec ElV. .y) log
Meniss Evecy encciny ch(ar.D )-h((ns)))
Structured sum-exponential loss
Lexp
Eyey R(V'.) Ey
[1-
1
Structured generalized cross-entropy loss
Evey E(v' .1)
1
"goe
Egrre cheonin Maxi) Evecy chiinus
1
Structured mean absolute error loss
Eyey Eise/l///1 v)
generalized cross-entropy loss [Zhang and Sabuncu, 2018]; and -mme absolute error loss [Ghosh et al., 2017].
coincides with the mean
We will show that these structured comp-sum losses benefit from H-consistency bounds in structured prediction, when H. is symmetric and complete hypothesis set. A hypothesis set K is symmer- ric if there exists a family I of real-valued functions such that {[h(x. 1)...., n)]]: e JC} {[fi(x) fn(2) ]: fi...................... . fn e {J for any I X. Thus, the choice of the scoring functions does not depend on the order of the categories in y. A hypothesis set JC is complete if it can generate scores that span TR, that is. (h(r,,) y): E H) for any (x, y) E x y. shown by Awasthi et al. [2022b] and Mao et al. [2023h], these assumptions are general and hold for common hypothesis sets used in practice, such as the family of linear hypotheses and that of multi-layer forwwfd neural networks, and of course that of all measurable functions.
Theorem (H-consistency bound of L comp), Assume that K. symmetric and complete. Then, for any target loss E, any hypothesis h E H and any distribution, we have
(h) Ri,or [[ comp (h)
Ri Commp o6 Micoop 2x) -M.
(9)
where r(t)= 2VE when L coom
Lig
coom
Lexp
I(t) 2/n when Leomp Loomp; and
Lgoe
I(t) nt when L comp comp
Theorem represents a consolidated result for the four structured comp-sum losses, with the proofs for each being presented separately in Appendix E. The key step of the proof is to upper bound the conditional regret of the target loss (Lemma 3) by that of a surrogate loss. To achieve this, upper bound the best-in-class conditional error by the conditional error of carefully selected hypothesis Ry, JC The resulting softmax Sn of this hypothesis only differs from the original softmax S corresponding to h two labels. Theorem 6 admits as special cases the K-consistency bounds of Mao et al. [2023h] given for standard multi-class classification (f = Eo-1) and significantly extends them to the general structured prediction scenario.
Let us emphasize that our proof technique is novel and distinct from the approach used in [Mao et al., 2023h), which only applies to the special case where E is the zero-one loss and cannot be generalized to any target loss f. In their proof, the authors choose h2 based individual scores h( y), rather than the softmax. Consequently, when & fg-1. as is common in structured prediction, the resulting optimization problem of μ can be very intricate and a closed-form expression of the optimization solution cannot be derived. However, our new proof method overcomes this limitation. By viewing the softmax of hypothesis to solve a simple constrained optimization problem on μ within structured prediction scenario.
unit and introducing a pseudo-conditional distribution 7. are able
By Steinwart [2007, Theorem 3.2], the minimizability gaps Mr . and ML vanish for the family of all mcasurable functions. Therefore, when JC= Hanl the H-consistency bounds provided in Theorem 6 imply the Bayes-consistency of these structured comp-sum losses.
Corollary 7. The structured comp-sum loss comp is Bayes-consistent for L comp comp comp
Log eexp
and comp
-goe
In fact, Theorem 6 provides stronger quantitative bounds than Bayes-consistency when the min- imizability gaps vanish, which suggests that if the estimation error of the structured comp-sum loss Rooo (h) Ri R[comp,y is reduced to c, the estimation error of the target loss R2 (h) Ri is upper bounded by 2.E for structured logistic loss and structured sum-exponentic loss, 2/ n e for structured generalized cross-entropy loss, and n for structured mean absolute error loss.

---

Table 2: A new family of surrogate losses for structured prediction: structured constrained losses.
(v(()
Name
Formulation (Eyey ((x,,)
we"
Structured constrained exponential loss
Leep
Eyss R/y/ .)) max(0, 1 h(2,8/))²
amax (0,1 1 o)² a mmax (0,1 1- o)
Structured constrained squared-hinge loss
Lestnd
Ever (1y v)) max 1 h(2,z()))
Structured constrained hinge loss
Lestinl linng
Eysu fly/ w) max(0, 1 h(,, (/),
umin max 11.1 }
Structured constrained p-margin loss
Lgstnd
Every Myy ()) min/max//
Maxe/ Jo 1.
Structured constrained loss functions
In this section, we introduce another new family of surrogate losses for structured prediction that we prove to admit K-coonistencyy bounds. We will present a novel generalization of the constrained losses [Lee et al., 2004, Awasthi et al., 2022b] to structured prediction. Thus, we refer to them as structured constrained losses and define them as follows:
(xx X y,
L csstmd (h,
Du () (-M((,)))))))))), s/Ey
Σ
(10)
with the constraint that Egey 1(x,)) v) = O and F.iik R. is an upper bound on v + ul for any u E R., In standard constrained loss formulation, a single-variable function 2(v) that defines margin-based loss is used. In (10), the angle-variable function o(v) is generalized to being a function of two variables (v), which depends on both the target loss and the scores, to accommodate the structured prediction scenario. Specifically, we can choose (v) ue""
(v) u max (0, 1 - =3² 2 (v) max (0. 1 1- v). (v) u min max (0, 1-0,11//ph --/pp; 1), which lead to new surrogate losses for structured prediction defined in Table 2. These surrogate losses are novel generalization of their corresponding counterparts [Lee et al., 2004, Awasthi et al., 2022b] in standard multi-class classification, where { = 1- As with structured comp-sum losses, we will show that these structured constrained losses benefit from H-consistency bounds in structured prediction as well, for any symmetric and complete hypothesis set K.
Theorem 8 (H--onsissencyy bound of L (stad), Assume that H is symmetric and complete. Then, for any target loss E, hypothesis h H. and any distribution, we have
(h) Ri,c $ [RR (h) -Re Reoordd o MI (3c) M,
(11)
where r(t)= = 2/ Emxtt when [estnd Lesppd, r(t) 2 when L Lestud cestud
and r(t) = t
hqq-hinee"
when L cstndd
L. hinge
L Lestud
The proof is included in Appendix F. As for Theorem 8, the key part of the proof is to upper bound the conditional regret of the target loss (Lemma 3) by that of a surrogate loss. Here too, we introduce a pseudo ppcudo-conditional distribution which can be viewed as a weighted distribution of the original one, p(z), with weights given by the target loss function. Then, we upper bound the best-in-class conditional error by the conditional error of a carefully selected hypothesis TT e H.
As shown by Steinwart [2007, Theorem 3.2), for the family of all measurable functions, the mini- mizability gaps vanish: ML ,or 0 and ML O. Therefore, when H = Hall. the H-consistency bounds provided in Theorem 6 imply the coysstcons of these structured constrained losses.
Corollary 9. The structured constrained loss L cstadd is Bayes-consistemt for estnd estad estad hinng and csttd
exp sq-- hingee
As with the cases of structured comp-sum losses, Theorem 8 provides in fact stronger quantitative bounds than Bayes-consistencyy They show that that if the estimation error of the structured con- strained loss cooo (h) -Ri or is reduced to e, the estimation error of the target loss Rr (h) - R Ri
upper bounded by 2 2/Emaxe for Lexp 2 for L cstud
cestad hinge and e for cstnd and Lp
It is important to note that we can upper bound the minimizability gap by the approximation error, or finer terms depending on the magnitude of the parameter space as [Mao et al., 2023h]. Furthermore, our H-consistency bounds (Theorems 6 and 8) can be used to derive finite sample learning bounds for a hypothesis set H. These bounds depend on the Rademacher complexity of the hypothesis set and the loss function, as well as upper bound the minimizability gap for the surrogate loss.
7

---

6 Optimization of comp and Lexp
Log
In this section, we show that the gradient of the structured logistic loss Leomp Log can be computed
efficiently at any point (Iz, 9:) and therefore that this loss function is both supported by HC-consistency
bounds and is of practical use. We similarly show that for comp in Appendix G.2.
Fix the labeled pair (x4, y4) and H.. Observe that comp (h, 81) can be equivalently rewritten follows:
log
comp (h, (h, log
21) (
Σ s'ey
ElL/ y/s) log
Σ y"
e ((zz.0))
=
Σ yeyy
7(1l u3 (
E(v', wi) D'Ey
Σ
log
Σ M(ers)) yyEy
Σ s/y
Tly' U1 (1,,,))))))))))
log Zniis
where l; Eyey fly', y:), and Zn. Eney (zi.v), Note that l, does depend on h and can be pre-computed. Modulo normalization, this quantity is the average similarity of ys to y. if we interpret {= 1-166 l as a similarity. While y may be very large, this can be often computed straightforwardlyy for most loss functions f. For example, for the Hamming loss, for sequences of length I, we have
1 7. = B Σ(1 E(L-1 (6t
] 1 E 1 -V. k-1
Σ
1
2
Thus, in this case, E, does not depend on i and is universal constant. Similarly, & can be shown to be a constant for many other losses.
Hypothesis set. For the remaining of this section, to simplify the presentation, we will consider the hypothesis set of linear functions H. = {a w (x, y): w> e RR), where V is a feature mapping from X y to Rd. Note that number of classical structured prediction algorithms adopt the same linear hypothesis set: StructSVM [Tsscchantaridis et al., 2005b). Max-Margin Markov Networks (M3N) [Taskar et al., 2003b], Conditional Random Field (CRF) [Lafferty et al., 2001b], Voted Conditional Random Field (VCRF) [Cortes et al., 2016]. Our algorithms can also be incorporated into standard procedures for training neural network architectures (see [Cortes et al., 2018], Appendix B).
Markovian features. We will also assume Markovian features, as is common in structured pre- diction. Features used in practice often admit this property. Furthermore, in the absence of any such assumption,
known that learning and inference in general are intractable. We will largely adopt here the definitions and notation from [Cortes et al., 2016] and will consider the common case where y is set of sequences of length I over a finite alphabet of size r. Other structured problems can be treated in similar ways. We will denote by s the empty string and for any sequence y (ih, ... v1)+ y. will denote by y (Us...., Us*) the substring of y starting index and ending at s' For convenience, for S O, we define y. by ys = E.
We will assume that the feature vector V admits a Markovian property of order that is it can be decomposed as follows for any (x, y) X y:
(x, y) = Σ 2t. (Z
(12)
feature vector function yi defined over x A [4]. We note that we can write V/ = Σ VA with V = (0...., V....,, 0). In the following, abusing the notation, we will simply write Vs instead of V.. Each VA corresponds to a Markovian feature vector based only on k-grams, p is the largest Thus, for any x e X and y e y, we have
for some
V (xx,)) (z(2.)).
(13)
8

---

For any & E [1,p], let th denote the position-dependent feature vector function corresponding to Vk- Also, for any a X and y A' define v by vi (0 v8-p-1. Σk= v/a (z, 1z-k-1 s). Observe then that we can write
V (I,
Σ va(c,))=
Σ Σ (2
(x 18-k+1
Σ (1, v2-pt1:
1=1
k=
Gradient computation. Adopting the shorthand for we can rewrite the loss at (I yi) as:
comp Loogip(,, (w, Tii Vi) log
Σ Vey
Ely. (...))))) Z. log Zw.i.
Thus, the gradient of Logu at any w E Rd is given by
(w.0(2))))
comp
(w) = Σ
ElV (2 1/) + +i E yey
Egrey e.m(ars")) V (21,3)
log
y'Ey
Σ y'ey
EVl v (2i,)) + & E (x(,,)))
by (w) (( with Zw Eye ( Note that
where 9w is defined for all
the sum defining these terms is over number of sequences that is exponential in and that the computation appears to be therefore challenging. The following lemma gives the expression of the gradient of L comp and helps identify the most computationally challenging terms.
Lemma 10. For any w E Rd, the gradient of Loog can be expressed as follows:
L
VL FLomm (w) = Σ -(.
L(2,))
where Qw Evsy pil Aw(y) and L(z, s) = E yoy pii Vyy.
Proof.
Using the decomposition of the feature vector, we can write:
Σ ((. vi (Z1, = Σ
E(u.
Σ
(x V. Ve 5)
Σ
Σ
(1), vi)
yey
A
AP
[x),)))) = Σ
(w) Σ
Σ Σ
Σ
(w(
qn
AEA
m=1
1=1
A2
1F 100--111-
This completes the proof.
In light of this result, the bottleneck in the gradient computation is the evaluation of Qw, (2, and L(z,s) for all e [t] and z ε A". In previous work [Cortes, Kuznetsov, Mohri, and Yang, 2016, Cortes, Kuznetsov, Mohri, Storcheus, and Yang, 2018], it was shown that the quantities Q (z, s) can be determined efficiently, all together, by running two single-source shortest-distance algorithms over appropriate weighted finite automaton (WFA). The overall time complexity
the (+, x) semiring of the computation of all quantities Qw (2, 8), z E A and 8 E [4], is then in O(rr), where r [A].
We now analyze the computation of L(z, s) for a fixed A and [t]. Note that, unlike (z, s). this term does not depend on w and can therefore be computed once and for all, before any gradient computation. The sum defining L(z, s) is over all sequences y that admit the substring z at position
Rational losses. In Appendix G.1, we also give an efficient algorithm for the computation of the quantities L(z. s) in the case of Markovian losses. Here, we present an efficient algorithm for their computation the important case of rational losses. This is general family of loss functions based on rational kernels [Cortes, Haffner, and Mohri, 2004] that includes, in particular, n-gram losses, which can be defined for a pair of sequences (y. (y.y") as the negative inner product of the vectors of n--gam counts of and y/.

---

Our algorithm bears some similarity to that of Cortes et al. [2018] for the computation of the gradient of the VCRF loss function. It is however distinct because the structured prediction loss function we are considering and our definition of rational loss are both different. We will adopt a similar notation and terminology. Recall that for any sequence y, we denote by y: the symbol in its ith position and by v V the substring of y starting at position i and ending at j. We denote by E, the set of transitions of a WFA A. Let U be a weighted finite-state transducer (WFST) over the (+, x) semiring over the reals, with as both the input and output alphabet. Then, we define the rational loss associated to U for all y, v A' by E(y, s/) u(y.z').
Let denote a WFA over the (+.x) x) semiring accepting the set of all sequences of length with weight one and let y, denote the WFA accepting only y/ with weight one. Then, by definition, the weighted transducer yollo y, obtained by composition maps each sequence y in A' to yi with weight U( The WFA II, (9 o U yz) derived from that transducer by projection on the input (that is by removing Figure 1: Illustration of the output labels) is associating to each sequence y weight U(y.v:). 3/). WFA y for {a, b) and l = 3. We use weighted determinization [Mohri, 1997] to compute an and the WFA yı, where y: cquivalent deterministic WFA denote M. As shown by Cortes et al. aña. [2015][[heorem 31, M can be computed in polynomial time. M admits a unique path labeled with any sequence y E A' and the weight of that path is U(y y:). The weight of that accepting path is obtained by multiplying the weights of its transitions and that of the final state.
BEIT
We now define deterministic p-gram WFA N that accepts all sequences y A' with each of its states (z)) encoding (p- 1)- gram z' read to reach it and the position 8 in the sequence at which it is reached, The transitions of N are therefore defined as follows with weight one:
a:a/1
Ca,
En (1 1), (V5 ()); A a A, sE
(b. 2)
brall
The initial state (c, 0) and the final states are those with the second element of the pair (the position) being I. Note that, by construction, N is deterministic. Then, the composition (or intersection) WFA No M still associates the same weight as M. to each input string y E A'. However, the states in that composition help us compute Figure 2: Illustration of the L(z,s). In particular, for any
(E.0)
A and [4]. let E(z,s) be WFA N for A = ={a,b), p 2
the set of transitions of No M constructed by pairing the transition and [ 2.
((z)-1 8 - 1). 2p, (1, s). (zZ, s)) in N with a transition (2M, 2p, w. d'xc) in M. They admit the
following form:
E(z, s) = =((( (( Zp, w. (9'x 4bx) E ENOM: @N = (z) 1 1)}
(14)
The WFA N M deterministic as a composition of two deterministic WFAs. Thus, there is a unique path labeled with sequence e A in No M and admits the substring z ending at position s iff that path goes through a transition in E(z, 8) when reaching position s. Therefore, to compute L(2,s) it suffices for us to compute the sum of the weights of all paths in No M going through a transition in E(z, s). This can be done straightforwardly using the barward-backward algorithm or two single-source shortest-distance algorithm over the (+, x) semiring [Mohri, 2002a], one from the initial state, the other one from the final states. Since N a M is acyelic and admits O(IAAP) transitions, we can compute all the quantities L(2,s), 8 E [?] and z AP, in time (([A)P).
7 Conclusion
Our detailed study revealed shortcomings in commonly used surrogate loss functions and algorithms for structured prediction, prompting the introduction of new, strongly consistent alternatives. These findings not only enhance the theoretical and algorithmic foundations of structured prediction but also pave the way for the development of practical and effective solutions. In upcoming work, we will report an extensive empirical analysis of our algorithms. Our work provides tools and insights for future algorithm design in this domain, promising advancements in both theory and application.
10

---

References
E. Ahmad, L. Brogat-Motte, P. Laforgue, and F. Alché Buc. Sketch in, sketch out: Accelerating both learning and inference for structured prediction with kernels. arXiv preprint 10120230... 2023.
C. Allauzen and M. Mohri. An efficient pre-determinizztion algorithm. In O. H. Ibarra and Z. Dang. editors, Implementation and Application of Automata, 8th International Conference, CIAA 2003, Santa Barbara, California, USA. July 16-18, 2003, Proceedings, volume 2759 of Lecture Notes in Computer Science, pages 83-95. Springer, 2003.
C. Allauzen and M. Mohri. An optimal pre-determinization algorithm for weighted transducers. Theor Comput. Sci., 328(1-2):3-18, 2004.
Awasthi, N. Frank, A. Mao, M. Mohri, and Y. Zhong. Calibration and consistency of adversarial surrogate losses. In Advances in Neural Information Processing Systems, 2021a.
Awasthi, A. Mao, M. Mohri, and Zhong. A finer calibration analysis for adversarial robustness. arXiv preprint arXiv: 105.015500 2021
Awasthi, A. Mao, M. Mohri, and Y. Zhong. H-consistency bounds for surrogate loss minimizers. In International Conference on Machine Learning, 2022a.
P. Awasthi, A. Mao, M. Mohri, and Y. Zhong. Multi-class H-consistency bounds. In Advances in neural information processing systems, 2022b.
P. Awasthi, A. Mao, M. Mohri, and Y. Zhong. Theoretically grounded loss functions and algorithms for adversarial robustness. In International Conference on Artificial Intelligence and Statisties, pages 10077-10094, 2023a.
P. Awasthi, A. Mao, M. Mohri, and Y. Zhong. DC-programming for neural network optimizations. Journal Global Optimization, 2023b.
D. Belanger and A. McCallum. Structured prediction energy networks. In International Conference on Machine Learning, pages 983-992, 2016.
D. Belanger, B. Yang, and A. McCallum. End-to-end learning for structured prediction energy networks. In International Conference on Machine Learning, pages 429-439, 2017.
Belharbi, R. Hérault, C. Chatclain, and S. Adam. Deep neural networks regularization for structured output prediction. Neurocomputing, 28 281:169-177, 2018.
Berkson. Application of the logistic function bio-assay. Journal of the American Statistical Association, 19:357-3663 1944.
Berkson. Why prefer logits probits. Biometrics, 7(4):327-33) 1951.
M. Blondel. Structured prediction with projection oracles. In Advances in neural information processing systems, 2019.
L. Brogat-Motte, A. Rudi, C. Brouard, J. Rousu, and F, d' Alché Buc. Learning output embeddings in structured prediction. arXiv preprini arXiv:2007. 2020.
V. A. Cabannes, F. Bach, and A. Rudi. Fast rates for structured prediction. In Conference Learning Theory, pages 223-865,000 2021.
V. Cabannnes, A. Rudi, and F. Bach. Structured prediction with partial labelling through the infimum loss. In International Conference on Machine Learning, pages 1230-1239 2020.
K. Chang, A. Krishnamurthy, A. Agarwal, H. Daumé III, and J. Langford. Learning to search better than your teacher. In Proceedings of ICML. 2015.
L.-C. Chen, Papandreou, Kokkinos, Murphy, and A. L. Yuille. Semantic image segmentation with deep convolutional nets and fully connected erfs. arXiv preprint urXiv:1412.70 2014.

---

L.-C. Chen, A. Schwing, A. Yuille, and R. Urtasun. Learning deep structured models. In International Conference on Machine Learning, pages 1785-17944 2015.
H. Choi, O. Meshi, and N. Srebro. Fast and scalable structural svm with slack rescaling. In Artificial Intelligence and Statistics, pages 667-675 2016.
C. Ciliberto, L. Rosasco, and Rudi. A consistent regularization approach for structured prediction. In Advances in neural information processing systems, 2016.
C. Ciliberto, F. Bach, and A. Rudi. Localized structured prediction. In Advances in Neural Information Processing Systems, 2019.
C. Ciliberto, L. Rosasco, and A. Rudi. A general framework for consistent structured prediction with implicit loss embeddings. The Journal of Machine Learning Research, 21(1):385233918, 2020.
R. Collobert, Weston, L. Bottou, M. Karlen, K. Kavukcuoglu, and P. Kuksa. Natural language processing (almost) from scratch. Journal of machine learning research, L2ARRTICLE):29932555 2011.
C. Corro. On the inconsistency of separable losses for structured prediction. arXiv preprint arXiv:2301.10810, 2023.
C. Cortes, P. Haffner, and M. Mohri. Rational kernels: Theory and algorithms. J. Mach. Learn, Res., 5:1035-1062, 2004.
C. Cortes, M. Mohri, and J. Weston, A general regression technique for learning transductions. In L. D. Raedt and S. Wrobel, editors, Machine Learning, Proceedings of the Twenty-Secont International Conference (ICML 2005), Bonn, Germany, August 7-11, 2005, volume 119 of ACM International Conference Proceeding Series, pages 153-160. ACM, 2005.
C. Cortes, M. Mohri, and J. Weston. A General Regression Framework for Learning String-to-Stiin Mappings. In Predicting Structured Data. MIT Press, 2007.
C. Cortes, V. Kuznetsov, and M. Mohri. Ensemble methods for structured prediction. Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014, volume 32 of JMLR Workshop and Conference Proceedings, pages 1134-1142. JMLR.org. 2014a.
C. Cortes, V. Kuznetsov, and M. Mohri. Learning ensembles of structured prediction rules. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, ACL 2014, June 22-27, 2014, Baltimore, MD, USA, Volume 1: Long Papers, pages 1-12. The Association for Computer Linguistics, 2014b.
C. Cortes, V. Kuznetsov, M. Mohri, and M. K. Warmuth. On-line learning algorithms for path experts with non-additive losses. In Proceedings of COLT, 2015.
C. Cortes, Kuznetsov, M. Mohri, and S. Yang. Structured prediction theory based on factor graph complexity. In Advances in Neural Information Processing Systems, 2016.
C. Cortes, V. Kuznetsov, M. Mohri, D. Storcheus, and S. Yang. Efficient gradient computation for structured output learning with rational and tropical losses. In Advances in Neural Information Processing Systems, 2018.
H. Daumé IIII J. Langford, and D. Marcu. Search-based structured prediction. Machine Learning, 75 (3):297-325, 2009.
J. Domke. Learning graphical model parameters with approximate marginal inference. IEEE transactions on pattern analysis and machine intelligence, 35(10))2454 2401)2474444477, 2013.
J. R. Doppa, A. Fern, and P. Tadepalli. Structured prediction via output space search. JMLR, 15(1): 1317-1350, 2014.
Dragone, Teso, and A. Passerini. Neuro-symbolic constraint programming for structured prediction. arXiv preprint arXh::2103.17222 2021.
12

---

S. Edunov, M. Ott, M. Auli, D. Grangier, and M. Ranzato. Classical structured prediction losses for sequence sequence learning, arXiv preprint vrXi::1111.04566, 2017.
Finocchiaro, R. Frongillo, and Waggoner. An embedding framework for consistent polyhedral surrogates. In Advances in neural information processing systems, 2019.
A. Ghosh, H. Kumar, and P. S. Sastry. Robust loss functions under label noise for deep neural networks. In Proceedings of the AAAI conference on artificial intelligence, 2017.
K. Gimpel and N. A. Smith. Softmax-margin crfs: Training log-linear models with cost functions. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 733-736, 2010
C. Graber and A. Schwing. Graph structured prediction energy networks. In Advances in Neural Information Processing Systems, 2019.
C. Graber, O. Meshi, and A. Schwing. Deep structured prediction with nonlinear output transforma- tions. In Advances in Neural Information Processing Systems, 2018.
M. Gygli, M. Norouzi, and A. Angelova. Deep value networks learn to evaluate and iteratively refine structured outputs. In International Conference on Machine Learning, pages 1341-1351, 2017.
R. Hershey, J. L. Roux, and F. Weninger. Deep unfolding: Model-based inspiration of novel deep architectures. arXiv preprint arXiv:1409.25777 2014.
Z. Huang, W. Xu, and K. Yu. Bidirectional Istm-crf models for sequence tagging. arXiv preprini arXiv: 1508.00999 2015.
M. Jaderberg, K. Simonyan, A. Vedaldi, and A. Zisserman. Deep structured output learning for unconstrained text recognition. arXiv preprint arXiv:1412.5903, 2014.
H. Jang. S. Mo, and S. Ahn. Diffusion probabilistic models for preprint arXiv:2302. 10506, 2023.
prediction. arXiv
N. Jiang, M. Zhang, W.-. van Hoeve, and Y. Xue. Constraint reasoning embedded structured prediction. Journal of Machine Learning Research, 23(345):1-40, 2022.
D. Jurafsky and J. H. Martin. Speech and Language Processing (2nd Edition). Prentice-Hal Hall, Inc., 2009.
Y. Kim, C. Denton, L. Hoang, and A. M. Rush. Structured attention networks. In International Conference on Learning Representations, 2017.
K. Kunisch and T. Pock. A bilevel optimization approach for parameter learning in variational models. SIAM Journal on Imaging Sciences, 6(2):938-99)) 1883,,98,2288 2013.
Lafferty, A. McCallum, and F. Pereira, Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of ICMI., 2001a.
J. D. Lafferty, A. McCallum, and F. C. Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In International Conference on Machine Learning, pages 282-289, 2001b.
M. Lam, J. R. Doppa, S. Todorovic, and T. G. Dietterich. He-search for structured prediction in computer vision. In CVPR, 2015.
M. Larsson, A. Arnab, S. Zheng, P. Torr, and F. Kahl. Revisiting deep structured models for pixel-level labeling with gradient-based inference. SIAM Journal on Imaging Sciences, 11(4):2610-2628, 2018.
Y. Lee, Y. Lin, and G. Wahba. Multicategory support vector machines: Theory and application to the classification of microarray data and satellite radiance data. Journal of the American Statistical Association, 99(465))67-81 2004.
Y. Li and R. Zemel. Mean-field networks, arXiv preprint arXiv: axXiv:1410.5884, 2014.
13

---

T. Liu, Y. Jiang, N. Monath, R. Cotterell, and M. Sachan. Autoregressive structured prediction with language models. arXiv preprint arXiv:2210. 14.698 2022.
J. Long, E. Shelhamer, and T. Darrell. Fully convolutional networks for semantic segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3431-3440, 2015.
Y. Lu and B. Huang. Structured output learning with conditional generative flows. In Proceedings of the AAAI Conference Artificial Intelligence, pages 5005-5012, 2020.
A. Lucchi, L.. Yunpeng, and P. Fua. Learning for structured prediction using approximate subgradient descent with working sets. In Proceedings of CVPR, 2013.
C. D. Manning and H. Schütze. Foundations of Statistical Natural Language Processing. The MIT Press, Cambridge, Massachusetts, 1999.
A. Mao, C. Mohri, M. Mohri, and Y. Zhong. Two-stage learning to defer with multiple experts. In Advances in neural information processing systems, 2023a.
A. Mao, M. Mohri, and Y. Zhong. H-consistency bounds: Characterization and extensions. In Advances in Neural Information Processing Systems, 2023b.
A. Mao, M. Mohri, and Y. Zhong. Principled approaches for learning defer with multiple experts. arXiv preprint arXiv:2310. 14774, 2023c.
A. Mao, M. Mohri, and Zhong. Predictor-rejector multi-class abstention: Theoretical analysis and algorithms. arXiv preprint arXiv:2310.14772, 2023d.
A. Mao, M. Mohri, and Zhong. H-consisteney bounds for pairwise misranking loss surrogates, In International conference on Machine learning, 2023e.
A. Mao, M. Mohri, and Y. Zhong. Ranking with abstention. In ICML. 2023 Workshop The Many Facets of Preference-Bact Based Learning, 2023f.
A. Mao, M. Mohri, and Y. Zhong. Theoretically grounded loss functions and algorithms for score- based multi-class abstention. arXiv preprint arXiv:2310.14777 2023g.
A. Mao, M. Mohri, and Y. Zhong. Cross-entropy loss functions: Theoretical analysis and applications. In International Conference on Machine Learning. 2023h.
C. Meister, T. Vieira, and R. Cotterell. Best-first beam search. Transactions of the Association for Computational Linguistics, 8:795-809, 2020.
C. Mohri, D. Andor, E. Choi, M. Collins, A. Mao, and Y. Zhong. Learning to reject with fixed predictor: Application decontextualizatton. arXiv preprint arXiv:2301.09044 2023.
M. Mohri. Finite-state transducers in language and speech processing, Computational Linguistics, 23 (2):269-311, 1997.
M. Mohri.
Generic e-removal algorithm for weighted automata. In S. Yu and A. Paun, editors, Implementation and Application of Automata, 5th International Conference, CIAA 2000, London, Ontario, Canada, July 24-25, 2000, Revised Papers, volume 2088 of Lecture Notes in Computer Science, pages 230-242, Springer, 2000.
M. Mohri. Semiring Frameworks and Algorithms for Shortest-Distanee Problems. Journal of Automata, Languages and Combinatorics, 7(3):321-350, 2002a.
M. Mohri. Generic e-removal and input e-normalization algorithms for weighted transducers. Int. J. Found. Comput. Sci., ((1)):12-1443 2002b.
M. Mohri. Weighted automata algorithms. In Handbook of Weighted Automata, pages 213-254. Springer, 2009.
14

---

M. Mohri and M. Riley. Weighted determinization and minimization for large vocabulary speech recognition. In G. Kokkinakis, N. Fakotakis, and E. Dermatas, editors, Fifth European Conference on Speech Communication and Technology, EUROSPEECH 1997, Rhodes, Greece, September 22-25, 1997, pages 131-134. ISCA, 1997.
M. Mohri, A. Rostamizadeh, and A. Talwalkar, Foundations of Machine Learning. MIT Press, second edition, 2018
D. Nadeau and Sekine. survey of named entity recognition and classification. Linguisticae Investigationes, 30(1):3-26, January 2007.
M. Norouzi, S. Bengio, N. Jaitly, M. Schuster, Y. Wu, D. Schuurmans, et al. Reward augmented max- imum likelihood for neural structured prediction. In Advances In Neural Information Processing Systems, 2016.
A. Nowak, F. Bach, and Rudi. Sharp analysis of learning with discrete losses. In The 22nd International Conference on Artificial Intelligence and Statisties, pages 1920-1929, 2019.
A. Nowak, F. Bach, and A. Rudi. Consistent structured prediction with max-min margin markov networks. In International Conference on Machine Learning, pages 7381-7391, 2020.
A. Nowak, A. Rudi, and F. Bach. On the consistency of max max-margin losses. In International Conference on Artificial Intelligence and Statistics, pages
2022.
A. Nowak- Nolak-Vila, F. Bach, and A. Rudi. A general theory for structured prediction with smooth convex 2019.
surrogates. arXiv preprint
A. Osokin, Bach, and S. Lacoste-Julien. On structured prediction theory with calibrated convex surrogate losses. In Advances in Neural Information Processing Systems, 2017.
P. Pan, P. Liu, Y. Yan, T. Yang, and Y. Yang. Adversarial localized energy network for structured prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 5347-5354, 2020.
D. Patel, P. Dangati, J.-Y. Lee, M. Boratko, and A. McCallum. Modeling label space interactions in multi-label classification using box embeddings. In International Conference on Learning Representations, 2022.
V. K. Pillutla, V. Roulet, S. M. Kakade, and Z. Harchaoui. smoother way to train structured prediction models. In Advances in Neural Information Processing Systems, 2018.
Ross, G. Gordon, and Bagnell, A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of AISTATS, 2011.
A. G. Schwing and R. Urtasun. Fully connected deep structured networks. arXiv preprint arXiv:1503.02351, 2015.
I. Steinwart. How to compare different loss functions and their risks. Constructive Approximation, 26(2):225-287, 2007.
V. Stoyanov, A. Ropson, and Eisner. Empirical risk minimization of graphical model parameters given approximate inference, decoding, and model structure. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 725-733, 2011.
I. Sutskever, O. Vinyals, and Q. V. Le. Sequence to sequence learning with neural networks. In Advances in neural information processing systems, 2014.
K. S. Tai, R. Socher, and C. D. Manning. Improved semantic representations from tree-structured long short-term memory networks. arXiv preprint arXiv:1503.0007. 2015.
B. Taskar, Guestrin, and D. Koller. Max-margin Markov networks. In NIPS, 2003a.
B. Taskar, C. Guestrin, and Koller. Max-margin markov networks. In Advances neural information processing systems, 2003b.
15

---

I. Tsochantaridis, T. Joachims, T. Hofmann, and Y. Altun. Large margin methods for structured and interdependent output variables. JMLR. 6:1453-1484, Dec. 2005a.
I. Tsochantaridis, T. Joachims, Hofmann, Altun, and Y. Singer. Large margin methods for structured and interdependent output variables. Journal of machine learning research, 6(9), 2005b,
L. Tu and K. Gimpel. Learning approximate inference networks for structured prediction. arXiv preprint
2018.
L. Tu and K. Gimpel. Benchmarking approximate inference methods for neural structured prediction. arXiv preprint arXiv:1904.0111. 2019.
L. Tu, R. Y. Pang, and Gimpel. Improving joint training inference networks and structured prediction energy networks. arXiv preprint arXiv:1911.0289) 2019.
P. F. Verhulst. Notice sur la loi que la population suit dans son accroissement. Correspondance mathématique el physique, 10:113--121, 1838.
F. Verhulst. Recherches mathématiques sur la loi d' d'accroissement de la population. Nouveaux Mémoires de l'Académie Royale des Sciences Lettres de Bruxelles, 18:1 -42, 1845.
O. Vinyals, I.. Kaiser, T. Koo, S. Petrov, I. Sutskever, and G. Hinton. Grammar foreign language. In Proceedings of NIPS, 2015a.
O. Vinyals, A. Toshev, S. Bengio, and D. Erhan. Show and tell: A neural image caption generator. In Proceedings of CVPR, 2015b.
Wang, Fidler, and R. Urtasun. Proximal deep structured models. Advances in Neural Information Processing Systems, 2016.
J. Weston and C. Watkins. Multi-class support vector machines. Technical report, Citeseer, 1998.
Y. Wu, M. Schuster, Z. Chen, Q. V. Le, M. Norouzi, W. Macherey, M. Krikun, Y. Cao, Q. Gao, K. Macherey, J. Klingner, A. Shah, M. Johnson, X. Liu, łukasz Kaiser, S. Gouws, Y. Kato, T. Kudo, H. Kazawa, K. Stevens, G. Kurian, N. Patil, W. Wang, C. Young. J. Smith, J. Riesa, A. Rudnick, O. Vinyals, G. Corrado, M. Hughes, and J. Dean. Google's 's neural machine translation system: Bridging the gap between human and machine translation. CoRR, abs/1609.08 0444,, 2016. URL http: /wtpxv/wivvv////////////a./a/aaa org/ ab/////9...../////////////////// 08144..
D. Zhang, L. Sun, and W. Li. A structured prediction approach for statistical machine translation. In Proceedings of IJCNLP, 2008
Zhang. Statistical analysis some multi-category large margin classification methods. Journal of Machine Learning Research,
1251, 2004.
Z. Zhang and M. Sabuneu. Generalized cross entropy loss for training deep neural networks with noisy labels. In Advances in neural information processing systems, 2018.
C. Zheng, G. Wu, F. Bao, Y. Cao, C. Li, and J. Zhu, Revisiting discriminative vs. generative classifiers: Theory and implications. arXiv preprint arXiv:2302.02. 02334, 2023.
K. Zheng and A. Pronobis. From pixels to buildings: End-to-end probabilistic deep networks for large-scale semantic mapping. In JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 3511-3518, 2019.
S. Zheng, S. Jayasumana, B. Comera-Paredesr V. Vineet, Z. Su, D. Du, C. Huang, and H. Torr. Conditional random fields as recurrent neural networks. In Proceedings of the IEEE international conference on computer vision, pages 1529-1537, 2015.
16

---

Contents of Appendix
Related work
18
B Proof of Lemma 3
19
Proofs for structured max losses
19
D Proofs for Voted Conditional Random Field
20
Proofs for structured comp-sum losses
E.1 Structured logistic loss
21
E.2 Structured sum-exponential loss
22
E.3 Structured generalized cross-entropy loss
23
E.4
Structured mean absolute error loss
25
F
Proofs for structured constrained losses
26
F.1
Structured constrained exponential loss
26 ................................
F2 Structured constrained squared-hings loss
27
F3 Structured constrained hinge loss
29
F.4
Structured constrained p-margin loss
30
G Efficient gradient computation and inference
31
G.1 Efficient gradient computation for Loog
31
G.2 Efficient gradient computation for exp
32
G.3 Efficient Inference
35
17

---

A Related work
Structured prediction and neural networks. A variety of deep learning techniques have been used for structured prediction tasks, including unified neural network architecture for natural language processing [Collobert et al., 2011 J. energy model-based structured prediction including structured prediction energy networks (SPENs) and various inference methods [Belanger and McCallum, 2016, Tu and Gimpel, 2018, Larsson et al., 2018, Tu and Gimpel, 2019, Tu et al., 2019, Graber and Schwing, 2019, Pan et al., 2020], attention networks incorporating richer structural distributions [Kim et al.. 2017], tree-structured long short-term memory (LSTM) networks [Tai et al., 2015], sequence to sequence learning [Sutskever et al., 2014, Edunov al., 2017]. memory-reduced variant of best-first beam search [Meister et al., 2020]. end-to-end learning for SPENs [Belanger et al., 2017], conditional generative flow [Lu and Huang, 2020], proximal methods [Wang et al., 2016], CRF using deep features [Jaderberg et al., 2014. Huang et al., 2015, Chen et al., 2014, Schwing and Urtasun, 2015, Chen et al., 2015], non-iterative feed- forward predictors [Stoyanov et al., 2011. Domke, 2013, Kunisch and Pock, 2013, Hershey et al., 2014, Li and Zemel, 2014, Belharbi et al., 2018, Zheng et al., 2015], deep value network [Gygli et al., 2017], fully convolutional networks [Long et al., 2015], constraint reasoning tool [Dragone et al., 2021, Jiang et al., 2022], multi-label box model[Patel et al., 2022], probabilistic deep networks(Zheng and Pronobis, 2019, Jang et al., 2023], autoregressive methods [Liu et al., 2022], nonlinear output transformations and embedding [Graber et al., 2018, Brogat-Motte et al., 2020). smoothing methods [Pillutla et al., 2018) 8] and structural training [Choi et al., 2016, Ahmad et al., 2023]. Let also mention ensemble algorithms for structured prediction algorithms [Cortes, Kuznetsov, and Mohri, 2014a,b], which can be used to combine several algorithms for this problem.
Consistency in structured prediction. Here, we discuss in detail previous work on consistency in structured prediction [Osokin et al., 2017, Ciliberto et al., 2016, Blondel, 2019, Nowak et al., 2020, 2022, Ciliberto al., 2019, 2020, Nowak- Vila et al., 2019, Nowak al., 2019, Cabannes et al., 2021, Cabannnes et al., 2020, Corro, 2023].
Osokin et al. [2017], Nowak al. [2020] and Nowak al. [2022] pointed out that the max-margin Markov networks (M3N), or more generally structural SVMs may not be Bayes-consistent. Instead, Osokin et al. [2017] proposed the first Bayes-consistent surrogate loss in the structured prediction setting, the quadratic surrogate (QS) loss. A general theory of QS was further developed in [Nowak- Vila et al., 2019, Nowak et al., 2019]. However, as pointed out in Section 1, the quadratic surrogate loss formulation casts the structured prediction problem as a regression problem and is not a typical formulation even in the binary classification case.
Nowak et al. [2020] proposed a consistent method called max-min margin Markov networks (M4N) derived from first principles for binary SVM. However, this method is restricted SVM-type loss functions. Instead, we propose broad families of surrogate losses, which can be naturally derived from common multi-class losses including the logistic loss.
Nowak et al. [2022] addressed the inconsistency of Max-Margin loss in structured prediction by introducing the notion of MestrriteddMax-Maaraee where the maximization is performed over a subset of the original domain. Their method is based on an implicit embedding [Finocchiaro et al., 2019]; a general framework for structured prediction has been further developed by Ciliberto al. [2020]. However, these methods are only applied to polyhedral-type surrogates which are not as smooth as the logistic loss. Thus, the resulting surrogate losses may not be favorable from the optimization point of view. Instead, our novel families of surrogate losses are very general and can be smooth, including new structured logistic loss, for which we describe efficient gradient computation algorithms.
Ciliberto et al. [2016] focused on a least squares surrogate loss function and corresponding framework. In this framework, the structured prediction problem is cast as regression problem. They derived a regularization approach to structured prediction from the least squares surrogate loss and proved the Bayss-consistency of that approach. Ciliberto et al. [2019] focused on local structre-adapted framework for structured prediction. They proposed a novel structured prediction algorithm that adaptively leverages locality in the learning problem. Ciliberto et al. [2020] developed a general framework for structured prediction based on implicit embedding. Their methods lead to polyhedral- type surrogates losses that benefit from Bayes-consistency.
On the other hand, our work presents an extensive study of surrogate losses for structured prediction supported by H-consistency bounds. Different from the surrogate loss studied in the previous work,
18

---

the formulations of our proposed surrogate losses including structured comp- sum losses and structured constrained losses are completely novel and do not cast structured prediction problems as a regression problem. Furthermore, we prove stronger consistency guarantees that imply Bayes-consistency for these new proposed families of surrogate loss.
Other related work on structured prediction includes: projection-based losses for structured prediction [Blondel, 2019]; fast convergence rates for general structured prediction problems [Cabannes et al., 2021]; a unified framework for dealing with partial labelling [Cabannnes et al., 2020]: and an analysis of the inconsistency of separable negative oog-likllhood losses for structured prediction [Corro, 2023].
B Proof of Lemma
Lemma 3. The best-in-class conditional error and the conditional regret for a target loss L in structured prediction can be expressed as follows:
(x)c(z) = min Σ Exxxy))(y''s y/H(())
(h,z) T-==>pee (((r)))(((xx))v>> min Ep(a,y)e(//.1 y'e((z) gey
Proof. By the definition, the conditional L-risk can be expressed as follows:
CL CL(h, Σ ((z,)))((((z)))))
(15)
gey
Since (h(z) e HC} H(z), the best-in-class conditional error can be expressed as follows:
(x)r min Σ ((x,)) y'EH(x) yEy
which proves the first part of the lemma. By the definition, ACLor(h, = eL (h, ([,x(()) (()())))((()).)))
min Σp(z,))(v1 v)) s/(((z) yey
yey
C Proofs for structured max losses
Theorem 4 (Negative results L Assume that and that (v) convex and non- increasing for = 1. Then, the max structured loss [max is not Bayes-consistent.
Proof. For the structured max loss L max the conditional L Lmax -rikk can be expressed as follows:
CL max (h, x)) = Σ E((,yy) max Pucy w/ (I( h(x, *'+y
yely
Take ((y', 1 yoy to be the zero-one loss. Since E(1/ ,v) 1 for any y + y', the conditional max risk can be reformulated as follows:
Ceaax (h, x)
p(x,y) max 2 (h((z,)) 1((x v))). yey
Σ
y'ty
Consider the distribution that supports and 1/2 # We define the conditional distribution as p(I, (11 = p(x, y2) 1 and p(x.y) y) 0 for other E y. Then, by using the fact that T (v) is convex and non-increasing, we obtain
singleton domain (a). Take y1 y/2 y such that y
1
R max (h) CL (h,, xx max + T (1((,, 1(x,1')) max (b(x,,)22) ((,,y)) v'=uz
4 (h(x.y1) maxh(x, o ((xx)))) max h (xx y vouz ( (v) is non non-increasing)
y'401
1
2 2
((x
max (2 s/) + fxx y2) p'
max (z,
2
2 of v'
(Φ) (v) is convex)
2 $ (0)
( (v) is non- con-increasing)
19

---

where the equality can be achieved by ht E J( defined as h (2) = h- (x,2) Therefore, ht Bayes classifier of the structured max loss, Note that h" (x) n. However, by Lemma 3, in such a case, the Bayes classifier h of the target loss satisfies that
(x, n).
h2 (z) argmin Σ p(z.y) y) y'ey
(1) p(z, (2) y1 or y2-
wey
y'ey
Thus, we obtain h* hद. Therefore, L is not Bayes-consistent.
D Proofs for Voted Conditional Random Field
Theorem (Negative result of L LVCRP). The Voted Conditional Random Field L LYCRF is not Bayes- consistent.
Proof. For the Voted Conditional Random Field L LYCRF, the conditional L LLCRF-riss -risk can be expressed as follows:
coo (h = Σ p(z, v) log yey
Σ ADEEy
Consider the distribution that supports on singleton domain {x). Note that Ry CLvew is convex with respect to hx,, y), = I....,n. n. To find the global minimum, we will differentiate CLear with respect to h(x, y) for any y and setting the derivatives to zero. Thus, we obtain for any y y,
p(a, v) Ey' Cav (l ((tuss))"(as
v(a,')) Ey
O. (16)
Egeey ((U.:/)H(a.E
d'+y
Using the fact that Ey to further simplify the LHS of (16), we obtain for any y e y,
Eney e ( (elN))))))--
Mv ())( Eyeey "ll "" "")
ell ()-(()))
p(a,y)= Ex(a,y) y'Ey
Σ p((,,y) yeEy
Ey ed "0"++h(z."""") (17)
Consider a target loss function L such that (vvs/ = by y. that is (wy, v/) log( ②2y)) log( & ) where Py a function mapping from y to R., For this special choice of the target loss function, the expression of E(y. s/) decouple and (17) can be simplified to
D by Eyney By 1 (heeaa)))))) Eyey p chors))
$ Mx.))
p(z,y)= Σ p( v')
(18)
y'ey
Therefore, for the Bayes classifier h' of Voted Conditional Random Field, by (18), we have
$ Bych (a.1) (a,1)
$ e
plx, 1) = =...
p(I,
which implies that
h² (z) = argmax h² (I. ) argmax h (a./) argmax p(x,3/) yey
v'ey
y'ey by
However, by Lemma 3, in such a case, the Bayes classifier hü of the target loss satisfies that
h (x) argmin Σl(z,))((s = argmin yey
p(r v) (log((,) + log( ()))
argmin y'ey
y'ey
yey
yey
Thus, we obtain h* hü in general. Indeed, consider the case where p(z, y) Ee., 9 W E y. Then. d
h* (x) argmaxy not equal. Therefore, L YCkr is not Bayes-consistent.
Ex o7 argmax, By argmin By h2()) when ( : e y)
20

---

E Proofs for structured comp-sum losses
E.1 Structured logistic loss
Theorem 11 (K-consistenccy bound of Loog Lomp). Assume that H is symmetric and complete. Then, for any target loss hypothesis h H. and any distribution,
R (h) Ri,3 s 22(R1 Recomm (1) - Ri
M
comp ,x )²
-M,
(19)
log
log
Proof. For the comp-sum structured loss Loog follows:
the conditional
Liog Loomp-risk can be expressed as
el(an))
C coun (h, = Σ ((x,,))
Σ
E(y' log
log
E Eyy Eymeyehlz.pg ch(z,o0))
y'Ey Ma,,)
Σ log s/ey
Σ E((x:))((('.)) May
Eyreyehha..r
Σ log(S(x,))) (T,,,, Vey
where we denote by 7(x,8') Evey p(r, V)((1' E [0.1] and 8(x,y) = Eveey ehiriayy [0,1]
with the constraint that Evey y( 1. Let Ymin = argmin yey Egey p(x, y) v', y). where we choose the label with the highest index under the natural ordering of labels as the tie-breaking strategy. For any h H. such that h(x)) * Umii and X, by the symmetry and completeness of H. we can always find family of hypotheses {T. μ [-8(x, Vmiin, 8(x, h(x))] c H such that
(h(())) (x,,) Evtryehalars take the following values:
8(x,8) y)
y (ymin, h(x)
(x,
S(x, Mminn 1 8(x,, h(x)) p
if y h(x)
(20)
if y Ymin-
Note that S, satisfies the constraint:
(x,(r) S(r,8) 1, Aμ
h(x))]
yey
By (20) and using the fact that H(x)) y when H is symmetric, we obtain
A ACccomp de (h) am (h, x) Cicom (H, x:)
e comp (), inf CLoomp (T),. WeB
[(x, Mmin loog(S(() Fmin)) (oy() =4]
sup ne[- vel-8(z. ((r
h(z))) + log(S(#,, w0]
+ 7
Differentiating with respect to μ yields the optimal value 1r" (L= (5.. Plugging in that value gives:
ALL comp or (h, 2 q(,, Umin) log (S(x, (())((()) + 8( Mmin (á( Umin)
8(x, Mmin (7 Mmin 7(x h(x)))
(8( (r. h(x)) 8(x, Mmnin )g( (v, h(x))
gl h(x)) log
8 h(>))(>)))) (7 Umin) ( h(x)))
21

---

Differentiating with respect to 8 shows that the minimum is attained for 8(x, h(x)) = 8(2,, Fruin) which gives:
27(2, Mmin
2q(2, h(x))
AC commp oe (h, x) ((, Mmin ) log ((x, Muiin)
(())(())))))))))))))))))))))(()) + ((x,h(x)) log ( Umin) 7 h(x))
(g(2, h(t))(()))))))))))))) (x,, Umin
2(, h(x)) + (x, Umin 2a (a log a+b
+ blog a+b 2(a+b)
(a-b)²
Va, b E [0, 1] [Mohri al., 2018, Proposition E.7])
(7(x, (ehh((2) 7( 3mia))
(0 s (TTT(2,()))) + ((x, Ymin) s 2)
4 ((, - Eyey p(z, V) (()i).)))
(AL.,((h,x))
(by Lemma 3 and H(x) y)
Since the function + - is convex, by Jensen's inequality, we obtain for any hypothesis /t H and any distribution,
(RL (h) - R[. ML (Ex AAL (h,, x))
4
4 AC ACL x7
D AA comp, 3x (h,
R comp (h) Ri comp oe + Momomp 36,
which leads to
(h) Ri, R2
comp (1) - -R comp
comp M,
. M2
log oe
E,2
Structured sum-exponential loss
Theorem 12 (Hé-consistency bound of cumup). Assume that H. is symmetric and complete. Then, for any target loss hypothesis h E H. and any distribution,
Ra (h) Ri,3 s 22 (h) - Ri comp o upp
Mi comp
Leap ,
M
(21)
Proof. For the comp-sum structured loss Lcomp, the conditional coomp comp-rris -risk can be expressed as follows:
C comp (h, = Ep(z,)) Σ 72/'.)) Σ ay
cheen"" Σ Veey 8(x,v') ((a.
yEy
yey
where denote by ((r,y') Evey () v)) [0.1] and 8(x,y) Enprey excroorry [0. 1]
with the constraint that Eney 8(x,y) 1. Let Ymin argmin Eney p(x,y)((y'' .y), where choose the label with the highest index under the natural ordering of labels as the tie-breaking strategy. For any h H. such that h(x:) * Vman and X, by the symmetry and completeness of H. we can always find family of hypotheses {hr μ [-8(x, Vmin)) S(x, h(x))] H such that
(x,,)))=
Evecy Evecy ehrinios take the following values:
S(I,z) 8(x, Mmin + p 8(x, h(x)) -
if y {ymins h(z)} y h(x)
S,(x)))
(22)
y Umin.
22

---

Note that Sy satisfies the constraint:
(x Σ 8(z,)) Vy [-8(x, (mia), (())]
gey
yey
By (22) and using the fact that H(xr) = when H' is symmetric, we obtain
AC camp 2 (1,z)
comp (h, C
CecOmp (h, inf CLcomp (ppp))) neB
((Z,ymin)
sup ne| 81--8(2 Mmmnn 8(2,))()))
8(x, Frmi))
5(x,h(x)) 1
1 8(x, (mmin)) 8(x,h(x))
+ (1, h(2)))
+ ps
v 7(10 h(x)) 2
(I,, (miu)) ((,)(()) ([(() )
8(x, Mmmin)
8(x, h(x))
8(x; Mmin))
+ 8(x, h(x))()))))))))))))))
(differentiating with respect to to optimize, optimal n² (() (e (x.Nini)))
Vi( ) (a.h(x))
(1, Ymin) - (<,h(()))
(differentiating with respect to to minimize, minimum is attained when ((x,h(x)) 8(x, Umin)
(g(2 (()) ς(. Ymiin) 2
(V (V(2,,(xx) / x. Yriin)
(7(2, h(x)) (I, Blmin) 2
(Vā+ + Vbs 2, Va, [0.1], a b
4
(())))) - Evey p(x, y) ()m((min
(h,
(by Lemma' 3 and H(x) =y)
Since the function L 2 is convex, by Jensen's inequality, we obtain for any hypothesis I e Hl and any distribution,
I
(R((h) R[,oc ML
[Ex LAC (h, x))
4
4 AC ACL (h, 2
4
AC comp D4 (h, x]]
R camp (h) Ricomp o + Me
which leads to
R (h) RR s 22(Recomm comp (f) - -R comp
or My
My
comp ,x -M exp
kespp
E.3
Structured generalized cross-entropy loss
Theorem 13 (H-consistencyy bound of Lcump)) Assume that H. is symmetric and complete. Then, for any target loss f, hypothesis h E H. and any distribution,
gge
RL(h) - Ri,x 2n ( comp (h) - R comp o6 Mi comp
ML
(23)
gen
23

---

Proof. For the comp-sum structured loss L geo the conditional Lee -risk can be expressed as follows:
cl(azs)
comp (h,z)) Ex(,)) 1000
Σ
(()
1-
Eyeey Eyeey ch(c.))7)
yc
Σ
1 -
Eyrey e/(xrr))) Ey
Σ yeli
p(a, p(2,))(()''
yeey
Σ (1 ((x,,'"")(((x")))) yey
where we denote by (1,30) Evey p y) (// e [0.1] 1] and 8(x,8) = Eynry ehcxi" [0.1]
e A(x.))
with the constraint that Egey 8(x,y) 1. Let Umin = argmin yey Eney p(x, V) v). where we choose the label with the highest index under the natural ordering of labels as the tie-breaking strategy. For any h H such that h(x:) * Umin and X. by the symmetry and completeness of H, we can always find family of hypotheses { p [-8(x, Vmin), S(x, h(x))] c HC such that chu(a))
(x,)),) E
take the following values:
8(x, v)
y (ymin- h(x)}
S (2,,)
S(rr Ummnn) + if y h(x)
(24)
8(x, h(x)) -p
if y Ymin-
Note that Sn satisfies the constraint:
(z,()) Σ S(x,8) 1, Vu (is
yey
yey
By (24) and using the fact that H(x) = when H is symmetric, we obtain
Comm (1,
= Comp (h1,x) - Cicomp (H,
2 ELcome (h, inf Cocomp (h) peR
a pe[- (e1--8(a.mmi)..Bao 8(x,h(())) (2,, Yuuin) [-8(2, (riii (8(x,((=))) ((8 [
sup
+7(r, ( h(x)) (S(I,)mmin) +11)
(8(2,h(z)) + 8(x, Mmmn)) )) ( Mmina Ta +7((x
q(. Ymui 8((z, Vmin) ((c,h()))
(differentiating with respect to a to optimize, optimum 4t" g(x.h(a)) r'm 8(a.h(x))) ((2 F-v 8(a (miin)
2d (1. Mmmin - + ((x,h(())))))) h(x))())))))))))()))))) h
- ( Vumi) क(z h(x))))))))))))())))
an
(differentiating with respect minimize, minimum attained when 8(r, hh:)h())))))))))))) = 8(1 (mmn) !)
(7(z, g(z, 2) 4n ((x - Egey p(x, ( )))²
1-a 4b1-
I-o
atè 2
(a b) Va, be [0,1]
4n
2h,
(by Lemma 3 and H(x) y)
4
24

---

Since the function in e any distribution,
is convex, by Jensen's inequality, we obtain for any hypothesis h e H and Ins
(RL (h) Rgg ML.
(h, x)))
4n
4n
AC (h, x0
4n
1 AC comp 2e (h,, 2x)
RR comp (h) - Ri comp o + Mccompppr
which leads to
RL (h) - Rixx 2n (Rigamme
comp (h) - Ri
comp gen
.06 M,
Lace ,06 M4,9c.
comp
L
E.4 Structured mean absolute error loss
Theorem 14 (H--consistency bound of Lomp) Assume that H. is symmetric and complete. Then, for any target loss hypothesis h H and any distribution,
R (h) Ri.or ( comp
comp (h) Ri
M
comp xx) ML.
(25)
Lane
Proof. For the comp-sum structured loss comm, the conditional comp-risk can be expressed as follows:
C comp (h,,)= = Σ E(1,)) Σ
El' ())
Every ch(aas)r)
yey
Ney
Σ 1 Eyney ch(os)m
Deyy
Σ
S(x, 1/ (z)))(zz
yey
where we denote by ((,,8)) Eyey p(x, Ev/ .y) e [0,1] and 8(x,y) = Eve.y ef [0. []
Alx.u)
with the constraint that Evey S(x, y) 1. Let Pmin argmin yey Egey p(x,))(x( ()y's' , y). where we choose the label with the highest index under the natural ordering of labels as the tie-breaking strategy. For any h H such that h(x) # Umin and e X, by the symmetry and completeness of H, we can always find family of hypotheses [TT μ [[8(2x Vm 8(x, h(x))]} c HC such that (n()))
(x,-) Entye take the following values:
8(1,y) S(x, Mmmnn + μ 8(x, h(x)) -p
if y {ymin- h(z)} if y h(x)
S, (z,
(26)
if y Mminn
Note that 5, satisfies the constraint:
( 8(x,0) Ay [-8(x, Vmia), h(x))
Dc
yey
25

---

By (26) and using the fact that H(z) = y when H is symmetric, we obtain
A Le comp .4 (h,
Loowp (h)
Coomp (H,, 2)
Ci comp (11,2)
inl Croom (hip. HeR
sup wel- (2l-8(( ((x.n)))() ((x,h(x)))
Vmin (min) Vmin)) ((x,(())) [4]
+ + h(x))) 8(x, Vmin) + u1]
[(x,, Mmain )8(,, h=)) q(z, h(2)) h(x))
(differentiating with respect to μ to optimize, optimum μ = =-((x, Mmin))
2-(7 (min)) h())))
(differentiating with respect to to minimize, minimum is attained when 8(x,h(x)) +
Eyen (ll.))))(()))...))) y) Eyey p(z, ()minn 3)
(h, n
(by Lemma 3 and H(x) y)
Therefore, obtain for any hypothesis h HC and any distribution, (h) - Ri. + ML Ex (.,
Coomp or (h1
R campy (h) Risowp J + comp
which leads to
R (h) Ri,or $ nn(2 coop (h) - Ri coup
M comp xx) ML
,9C
F Proofs for structured constrained losses
F.1 Structured constrained exponential loss
Theorem 15 (FC-consistency bound of Lestad), Assume that D[ is symmetric and complete. Then, for any target loss hypothesis h H and any distribution,
(h) Ri.x S 2 ( estand (h) RR catnd ge + M cotued .r)
My
Me,
(27)
Proof. Denote by (x, Egey p(z, v)
.'v''''v) v) e [O, Lmax]. For the constrained structured loss Lestnd_rish -risk can be expressed follows:
estad
the conditional Lexp
exp
C Lossnd (h, = E((,,) Σ ((y.at)) Σ (( v'ey
yel
y'ey
Let Umin = argminn Eyey ((, () y). where we choose the label with the highest index under the natural ordering of labels as the tic-breaking strategy. For any and æ e X, by the symmetry and completeness of H, we can always find a family of hypotheses (Tep μ R H such that (x,-) take the following values:
such that h(z) # Ymin
(1(2,)) h(x, Vruin) p. 11( h(x))(())))))))))
if y {ymin h(x))
(x v)
if y h(x)
(28)
if y = Umin.
26

---

Note that the hypotheses hy satisfies the constraint:
(x,()) Σ ((x,y)= = 0, Vu R. yey
Since Eney ( O. there must be non-negative scores. By definition of h(2) maximizer, must thus have h(2, h(x,h(z)) h(x)) O. By (28) and using the fact that H(x) when H is symmetric, obtain
A ca ,ac (h,
C Caoted (h, x)
Eeannd (K, xt)
CLaated (h inf ca (hus
ueR
=upp((<0 Mmin) ( (h( - ((( h(z) -MM (((()8mm)++ peR
=(Vale, (((t,,(()))ete h(x))))(aoh())) //(2, Mnnin (eh((
(differentiating with respect to μ to optimize, optimum 2 = log I(n.Mmin (e Jeh(hr q(a.h(=)) (( (a..
e M(z,((z)) (V (miin) -V V((xxh(x))
(ch((,((())) (a(. and ((x,h(x)) 2 q(2, (min)) (((x,h(x)) 2 20)
2 Va(a, Vmmi)) - v h(x))
- 9 Mmmin)
Va( Umin) v (xx h(x)))
2 48max
(I(x, (x1, Vmin)) )²
(0 s q(2 v) s maax)
(h,
(by Lemma 3 and H(x) y)
46max
Since the function and any distribution,
e is convex, by Jensen's inequality, obtain for any hypothesis h e H
Tmmax
(RL(h) Ri, + MLxx)²
(EEx (h,,
4fmax
4mmax
A 2h,
E
4l
A
ALcandd Cocoondd,e (e,,hhh, x)]
R ratad (1) R2 cotnd Je + M Mi J6:
which leads
RR - Ri $ 22vemax R (h) R catnd + M Mocannd 22) )² -M
F.2 Structured constrained squared-hinge loss
Theorem 16 (H-consistency bound of cstnd for any target loss f, hypothesis h H and any distribution,
hingee Assume that H. is symmetric and complete. Then.
R1h Ri.c RR catued
(h) R cutrid
M ee hinge
Mi.e..
(29)
H
oq binge
27

---

Proof. Denote by (z.,v)= Eyey p(2, v)e(v'.)) .y) E [m,x. For the constrained structured loss the conditional
estud
Lestnd
-risk be expressed as follows: "sq-hiuge""
sig-hinge.
C cutan
(h
Σ
p( v)
E Ely'
+
yey
y'ey
m0 1 h( 2((x,)))((z yeEy
Σ
Let Minin = argmin Eney (ez.)(2.)))) (yl.)))y where we choose the label with the highest index under the natural ordering of labels the tie-breaking strategy. For any H such that h(x) Mminn and æ e X, by the symmetry and completeness of H, we can always find a family of hypotheses (Mpp μe R] c H such that (x,-) take the following values:
((xx,))
if y (ymin h(x))
(x, y)
Mx,, Manin)
if y h(z)
(30)
h(x, h(x))(()+))))))))))))))) -
if ymin.
Note that the hypotheses h, satisfies the constraint:
Σ (x. Σ ((x,y) - YnE yey
Since Eyey h(x, = O, there must be non-negative scores. By definition of h(x) as a maximizer, we must thus have (xx,, h(x)) By (30) and using the fact that H(xr) = y when H symmetric, we obtain
AL Seuutdd,((oe (h,
Laardd (), e Giaand (H, x²)
2 Land (h, - inf CLaand (Fr x)
ueB
((x, ymmin) (0, 1(x, (m)n)))))) max ((x,,(x))) - 11)2)
= sup peR
+ (xx h(x)) max M(z max M(,,, Mmin) + uz 12)2)
(1 (1+h(aa h(r, (4(2,, h()))
(differentiating with respect to y to optimize)
2 (g(z, h())) q(1,, Umiu)))
(h he))(()))))))))))()))) 2 0)
((((,.)((((2).))) yEy
p) wey
(h,
(by Lemma 3 and H(x) y)
Since the function 12 convex, by Jensen's inequality, we obtain for any hypothesis h H. and any distribution,
(R) - RR + ML,x)²
E FIACL.x( (h,
ACL (h, )
E
AC catnd sr [h
R sannd (h) R Rionnd Me
which leads
Ri (h) Ri
R
catrud
binge
(h)
R
cotar
36
M hinge
H6 Mc
28

---

F.3 Structured constrained hinge loss
Theorem 17 (H-consistency bound of L hinge) Assume that H is symmetric and complete. Then, for any target loss hypothesis h H. and any distribution,
(h) Ri, S RR (h)
Ri
axend of
Lotnd H hingg
ML,
(31)
hinge
"iinge
Proof. Denote by a(0, s/) Eee p(a, v)((y' 9) e [0, maax] For the constrained structured loss csstnd the conditional L Linne risk can be expressed as follows:
"hinge
C Leaand (h1
Σ p(x,y)
Σ Ely. v) max (x,y)))
yey
s'ey
max [0, 0, y'ey
Σ
h(2, 1')a()))))
Let Umin = argminggey Egey p(, (y',y)) where we choose the label with the highest index under the natural ordering of labels the tie-breaking strategy. For any H such that h(x) Ymin and x X, by the symmetry and completeness of H, we can always find a family of hypotheses (Ty u R H such that (I,-) take the following values:
(xx,y)
if y (ymin h(x))
Ty (T. v)
M(x, Mmnin) + h(x, h(x))((++))))))))))))))
if y h(x)
(32)
if Umin-
Note that the hypotheses hy satisfies the constraint:
(T, Σ Mxx,y) 0, V yey
yey
Since Eyey h(,, E(z, y) O, there must be non-negative scores. By definition of h(x) maximizer, must thus have hxx, h(x)) O. By (32) and using the fact that H(r) = when HC is symmetric, we obtain
A La (oanndd_((h,,))) (1
C C (h, Gjcatnd (H, x)
Lo (h1 inf Ca (Ti MER
sup peR
g(I, (maa) h111+hhhzz00 Mmin))
11))
+ (1x h(x)) (0, h(x, h(x)) - max(0, (x + p.))
(1+ ((+ h(x)) g(x,, Mmin)) 2g(2, (((x,h(x)) Umi) Σ (((z.y)((mmaa yey
(differentiating with respect to j to optimize)
(Mxx,hx))) 2 0)
way
ACL, (h,
(by Lemma 3 and H(x) y)
Therefore, we obtain for any hypothesis HC and any distribution,
(h) Ri, + ML = F. AL,
X
< F A esttnd .rc (h,
R Rosnn (h) Rt
Riosund oor MLestad
which leads to
(h) -Ri, S R
cecad (h)
R²
colnnd of Mr catnd J ML, hinge
Meaand
hinge
29

---

F.4 Structured constrained p-margin loss
Theorem 18 (H-consistency bound of L ( Assume that H is symmetric and complete. Then, for any target loss f, hypothesis h E H any distribution,
(h) Ri, 5 Rigand (h) Rigend H Migand J - ML.K.
(33)
Proof. Denote by q(2, 1/) Eney p(z, y) .) e [0, bmax] For the constrained structured loss cstad the conditional L catnd risk can be expressed as follows:
Lgoand (h,x)
Σ p(x,
v) Σ ll v) max(0, ((2,8')}
yey
s'ey
Σ v'y
max h(2, M(,,+ v')d()))))
Let Mmin argming Eyey p(,, ()) .y), where we choose the label with the highest index under the natural ordering of labels the tie-breaking strategy. For any h H such that h(z) Ymmin and x e X. by the symmetry and completeness of H, we can always find a family hypotheses (Thp μ RR] c such that (x,, take the following values:
(Mx,,))
if y (ymins h(x))
(x v)
M(,, Yenin) +
if y = h(x)
(34)
h(x,, h(z))
if y Umin.
Note that the hypotheses hy satisfies the constraint:
Σ (z,gg) yey
Σ h(x,)))=00 0, VpeR. yey
Since Eney h(x, y) O, there must be non-negative scores. By definition of h(x) maximizer, must thus have h(x,h(x) O. By (34) and using the fact that H(x) when HC is symmetric, obtain
AC AC ,x (h, x²)
Lended (1, Cionn 2)
2 Ca () inf GLonnd (1),z2) ueR
min max 0,1+ 1(x, Mmin) P 0,1+ Mxxhh(x))
h(x,, h(x)) -
sup welt
g( Hmnin)
p1 min max 0,
Mx, Umin) 14 min max 0,
+ (xx h(x))
min
max
111]
2g ((12,(())) (((2))min)
(differentiating with respect to μ to optimize)
E((()))((h(s)).))) Σ
p(x, (ymiin)
wey
yey
AAL (h,
(by Lemma 3 and H(x) y)
Therefore, we obtain for any hypothesis h e H and any distribution,
(h) - Ri,0: + M2,
E (h,
X
< E A Geceeee .7c (h,
R coend (li)
R²
Riennd oe Me HCo
which leads to
RR Rh) -Ri S Rigund (h) Ri or Megand J Me.
30

---

G Efficient gradient computation and inference
Here, we describe efficient algorithms for the computation of the gradients for the loss functions comp and Leppe -lo
We also briefly discuss an efficient algorithm for inference.
G.1 Efficient gradient computation for L comp
Inn
We first present an efficient algorithm for the computation of the quantities L(z,, s) in the important case of rational losses, next in the case of Markovian losses.
Rational losses. Rational losses form general family of loss functions based on rational kernels [Cortes et al., 2004] that includes, in particular, n-gram losses, which can be defined for a pair of sequences (y. s/) as the negative inner product of the vectors of n--gram counts of y and y'-
Our algorithm bears some similarity to that of Cortes et al. [2018] for the computation of the gradient of the VCRF loss function. It is however distinct because the structured prediction loss function we are considering and our definition of rational loss are both different. We will adopt a similar notation and terminology. Recall that for any sequence y, we denote by y/ the symbol in its ith position and by v/ = Vitle+1 1" the substring of y starting at position i and ending at j. We denote by E, the set of transitions of a WFA A.
Let U be weighted finite-state transducer (WFST) over the (+, semiring the reals, with A as both the input and output alphabet. Then, we define the rational loss associated to UI for all y/ A by E(v.v) = U(y.y')
Let denote a WFA over the (+,x) semiring accepting the set of all sequences of length with weight and let y, denote the WFA accepting only y/ with weight one. Then, by definition, the weighted transducer yo Uo y, obtained by composition maps each sequence y in A to yi with weight U(y y:). The WFA ( o o V4) derived from that transducer by projection on the input (that is by removing Figure 3: Illustration of the output labels) is associating to each sequence y weight U(y, 9:). WFA y for A {aa b} and | 3, We use weighted determinization [Mohri, 1997] compute equivalent deterministic WFA denote M. As shown by Cortes et al. aba. [20h5][T 3,, M can be computed in polynomial time. M admits unique path labeled with any sequence y A' and the weight of that path is U(y y:). The weight of that accepting path obtained by multiplying the weights of its transitions and that of the final state.
31
bart
Idart
and the WFA ys, where y:
We now define deterministic p-gram WFA N that accepts all sequences yE A with each of its states (z', encoding (p- 1)- gram z' read to reach it and the position in the sequence which it is reached. The transitions of N are therefore defined as follows with weight one:
a:al1
(a,
Ex = (<=((((e)) ((v s 1), (V--p-a, D', A, [1]]
asart
bb/
(b, 2)
bii'1
The initial state is (c. 0) and the final states are those with the second element of the pair (the position) being l. Note that, by construction, N is deterministic. Then, the composition (or intersection) WFA No M still associates the same weight as M. each input string y E A However, the states in that composition help us compute Figure 4: Illustration of the L(z,s). In particular, for any z A and s [(]. let E(z.s) be WFA N for A (a,b), . p
(a
the set of transitions of N M constructed by pairing the transition and l 1=
((z)-) - 1); Zp, (2, s), (zZ,s) x)) in N with a transition (gM, Zp lxx in M. They admit the
following form:
E(2,s) =(((1N. (N)) 2p, (ohs, (xa)) e ExOMI (2) 88 .8-1) 1)]
(35)
The WFA N M deterministic as a composition of two deterministic WFAs. Thus, there is a unique path labeled with sequence e A in N M and y admits the substring z ending at position
31

---

iff that path goes through a transition in s) when reaching position s. Therefore, to compute L(z,s), s), it suffices for us compute the sum of the weights of all paths in No o M going through transition in E(z, 8). This can be done straightforwardly using the forward-backwant algorithm or two single-source shortest-distance algorithm over the (+, x) semiring [Mohri, 2002a], one from the initial state, the other one from the final states. Since N o M is acyclic and admits ((]))()) transitions, we can compute all the quantities L(z,,)) s), s E [T] and z e A", in time O(IA)))
Markovian loss. We consider adopting a Markovian assumption, which is commonly adopted in natural language processing [Manning and Schütze, 1999]. We will assume that can be decomposed as follows for all y.y' E A E(v,8') I' (V(6--p2188)) Thus, we can write:
L(z,8)= Σ 1 MP 1-1
To efficiently compute L(2,s), we will use a WFA representation similar to the one used by Cortes et al. [2016, 2018] and, for convenience, will adopt similar notation. L(z, coincides with flow computation a WFA A that we now define. A has the following set of states:
Q^ = (Cii D:ye A 0,
, 1..00....1
with 14 0) its single initial state, F4 (V/ 1) A' its of final states, and a transition from state (vi-p- 1) to state (uf-p-2 b,t) with label b and weight w (vv-pa b,t) b. b:):). that is the following set of transitions:
E,4 = ===(((1 ((01 1), b,,b b, b. A A',b,,,
By construction, A deterministic. The weight of path A is obtained by multiplying the weights of its constituent transitions. In view of that, L(z, s) can be seen as the sum of the weights of all paths in A going through the transition from state (zf-² , 1) (z s) with label zp-
For any state (vi-p+1;t) t) é QA. we denote by a((vi-p-1, t)) the sum of the weights of all paths in A from the initial state la to (Vi-p-1,t) 1) and by 8( (((vi- 1)) the sum of the weights of all paths from (ui-per t) to final state. Then, L(z, is given by
L(z a a(z) . s- 1)) w(z,s) ((2
Since A is acyclic, and / can be computed for all states in linear time in the size of A using single-source shortest-distance algorithm over the (+, x) semiring or the so-called forward-backward algorithm. Thus, since A admits O([Al(" transitions, can also compute all quantities L(z, s), 8 [4] and z E AP, time (lrP)..
G.2 Efficient gradient computation for comp
exp
In this section, we provide a brief overview of the gradient computation for L Leap which is similar to the approach used for Loog comp.
Note that the loss
comp on given point (x,, Vi) can be expressed follows:
comp exp
Σ ((s' vi)
Σ
Σ Ely'.vi MeA
Σ
Σ ((3.8))
vedi
Σ Manns))
Σ Al.. Mannn)) Σ ((1/.9)) W'A
VeA
Σ
e (.V(())))))
Σ
Σ tl).
EEA'
vee
ve
32

---

The gradient of exp
is therefore given by
Σ
e w
Σ yedi
E(V'. .ile w.l(oa)))
exp
v'eai
(36)
Σ D'EAi
El'' wi)e w(((e)) (xi.)))
An efficient computation of these terms is not straightforward since the summations run over an exponential number of sequences for y. However, will leverage the Markovian property of the features to design an efficient computation. This approach is similar to what we demonstrated earlier for Logmp We start with identifying the most computationally challenging terms by rewriting the expression of the gradient of comp in the following lemma.
eexp
Lemma 19. For any e Rd, the gradient of comm can be expressed as follows:
comp exp
(w)
Σ Σ
[Nw Qw (z. Zw Cw (Z.
s=1 A
where Q'n (z. s) Evei - cw (z. Eyy; 1 (ly. (yy.v)) w -.v(..)))) and Nw
Eyes' E(y. y:)e w.).)))))
Proof. Using the decomposition of the feature vector, we can write:
Σ
w. (I = Σ
w.V()
o Σ
ri Ve 18
YE
year
aml
())1,2,8) 2,8
1190 1-02--117 2
Σ E Mile w (.Va = Σ gedt
E(y, w (a..v) Σ (II. year
Σ xeA
Σ
(y.81)e (. F(enz.s).
This completes the proof.
It was shown by Cortes et al. [2016, 2018] that all of the quantities (2,s) for z A and s and Zw can be computed efficiently in time O(IrP), where r= |A] Thus, the remaining bottleneck in the gradient computation suggested by Lemma 19 is the evaluation of the quantities Cw s) for z A and s E [(] and Nw. As with the loss function Leomp discussed in the previous section, we will analyze the computation of these quantities first in the case of rational losses, next in that of Markovian loss.
comp loss with the same Rational losses. We will adopt the same notation as in the case of the Lig
definition of rational loss: l is rational loss if there exists WFST over the (+, semiring over the reals with as both the input and output alphabet such that for all y. y.u A", we have E(y. v/) U(y.y').
comp loss or that of Cortes et al. Our algorithm is also somewhat similar to the one described for the Log [2018] for the computation of the gradient of the VCRF loss function. There are, however, several differences here too because the quantities computed and thus the automata operations required are distinct.
Exactly as in the case of Log loss, we first define deterministic WFA M over the (+, x) semiring that can be computed in polynomial time and that admits unique path labeled with any sequence
33

---

y A', whose weight is 2(,, 9:). Next, as in [Cortes et al., 2018), we define deterministic WFA A such that
A(y) = -w.((.)))) w.((
The set of states QA of A are defined as Qu {v :): A', 8 O,....!. with 1 (E, 0) its single initial state, Fa { ((1/-p+1 (VS-p+ 1: 8- 1) to state (y.-p-2 a, 8) with label a and weight, that is, the following set of transitions:
A its set of final states, and with transition from state
E, = (==(((05 ((155 1), 0, w- (VS-p-2 a)) A', a, A, e [1]
Then, by definition of composition or intersection [Mohri, 2009], the WFA (Mo A) is deterministic and admits unique path labeled with any given y e A' whose weight (M) = MMV)) E(y, (oo.yi)e--eell w.V(x..))
Now, Nw coincides with the sum of the weights of all accepted paths in this WFA. Thus, since (M o A) is acyclic, it can be computed in time linear in the size of (M o A). that is its number of transitions. For any e [1] and E AP, (2,,8) 8) is the sum of the weights of all paths in (M c A) labeled with a sequence y/ admitting z as a substring ending at position
acp/cspl W aiR.aEE)
S13/ pia.a 111.
DCHINDD W 210,2.20
(s.
22
SOSNEP 21120.20
The Figure 5: Illustration of the WFA A for A
{a, b). p 2 and 1 2.
states in the composition (M o A) help us compute Cw (z, s). As in the case of the Loom loss, for any E A and e [4], we define E(z,s) as the set of transitions of (M o A) constructed by pairing a transition (gMC, 2p, Sp..ac. 4xx) in M with the transition ((z)-), s- 1), Zp, (2, s), (zZ, s)) in A. They admit the following form:
E(2,s) = (((([((M (a), Zp. wM w(2, s), (IM, d'a) E EManiCa = (z) : 111--- 1)}.
(37)
The WFA (Mo A) is deterministic as composition of two deterministic WFAs. Thus, there is unique path labeled with sequence y A' in (Mo.) and y admits the substring ending at position s iff that path goes through a transition in E(z, s) when reaching position 8. Therefore, to compute Cw (z, s). it suffices for to compute the sum of the weights of all paths in Cw, going through a transition in E(2,s). s). This can be done straightforwardly using the forward-backwart algorithm or two single-source thortest-distance algorithm over the (+,x) semiring [Mohri, 2002a], one from the initial state, the other one from the final states. Since (M a A) is acyelic and admits ((I) transitions, can compute all the quantities C (z, 8), [4] and A', in time (())
Markovian loss. Here, we adopt the Markovian assumption and assume that é can be decomposed as follows for all y.y' A 1.y.0'')) Tim Eo0vi-pr1. Thus, the quantity Cw (z, s) can be written as:
(z,
Σ
Wh 1=1
Σ
i & (v (6) II
w. wi
k=1
= Σ ( (asee
JP 181-1
Then, we can proceed as in the Markovian loss case for the loss function Loog coomp instead of the WFA A used there, we define here a similar WFA A'. The only difference is that the weight - = ( y:) for the WFA A is replaced with w' w' b, 1) Z. w:)e - w.s.st b.1), With the same argument, we can compute all quantities C (z, 8). e [2] and ε AP, in time ((rP). The quantity Nw can also be efficiently computed time (1re) since it is the sum of the weights of all paths in A'.
except that
34

---

G.3
Efficient Inference
We focused on the problem of efficient computation of the gradient. Inference is also a key problem in structured prediction since the label with a highest score must be determined out of an exponentially large set of possible ones. However, for the linear hypotheses considered in the previous sections. this problem can be efficiently tackled since it can be cast as a shortest-distanc problem in directed acyelic graph, in [Cortes, Kuznetsov, Mohri, and Yang, 2016].
More generally, an efficient gradient computation, efficient inference and other related algorithms can benefit from standard weighted automata and transducer optimization algorithms such e-removal [Mohri, 2000, 2002b] and determinization [Mohri, 1997, Mohri and Riley, 1997, Allauzen and Mohri, 2003, 2004] (see also the survey chapter [Mohri, 2009]).
35


Reviews:
[{"review_id": "yNe3lG2Y7B", "reviewer": "Reviewer_9Sph", "summary": "* The paper studies (Fisher, or “Bayes”) consistency in structured prediction.  In particular, the focus is on non-asymptotic, quantitative bounds for common and not-so-common (i.e., new) surrogate losses, which requires different proof techniques and an approach based on “H-consistency”.\n* Thm 4, Thm 5 provide a few of the main results in the paper, showing that commonly used losses in structured prediction are not Bayes-consistent\n* Thm 6, Thm 8 (and companion corollaries) provide the other main results in the paper, showing that a few new-ish but less tractable (though still convex) losses are H-consistent and Bayes-consistent — the losses in question here are the so-called “comp-sum” and “structured constrained” losses\n* Finally, lem 10 shows that the latter (comp-sum) losses may be computed in polynomial time — but revealing something of a natural statistical/computational trade-off, i.e., the consistent losses evidently require more compute than the non-consistent ones", "questions": "See above.", "limitations": "No they have not, but I’m not sure that’s necessary here.  This is an abstract / general theory paper.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper gives a quite detailed study on the statistical + computational aspects of H-consistency, for commonly (and not-so-commonly) used losses in structured prediction\n* In particular, the paper highlights losses that are Bayes-consistent (though coming at the price of computability)\n", "weaknesses": "I have just a couple questions / comments:\n* It seems the content of thms 4, 5 — on the lack of consistency — is also present in previous works (e.g., those by Ciliberto et al.).  Can you please elaborate on why these results in your paper are novel?\n* Usually Fisher consistency is defined relative to a target loss function.  What is the target loss function here?\n* I think the primary avenue the paper could be (significantly) strengthened is via an empirical analysis — the authors could illustrate the consistency (and computational costs) of the comp-sum, structured constrained losses through real-world examples.  That would really tie together the whole message of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging review. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.\n\n**1. It seems the content of thms 4, 5 — on the lack of consistency — is also present in previous works (e.g., those by Ciliberto et al.). Can you please elaborate on why these results in your paper are novel?**\n\n**Response:** Theorem 4 provides negative results for a broad and generalized family of loss functions, collectively referred to as structured max loss. This extends the scope of existing research, as previous works had only addressed the inconsistency of specific instances within the structured max loss category, such as Max-Margin Markov Networks (M3N) (e.g., studies by Osokin et al., Ciliberto et al. and Nowak et al.).\n\nTheorem 5 further elaborates on the negative results for voted conditional random field, a family of loss function that integrates the target loss $\\ell(y’, y)$ within its formulation. To the best of our knowledge, no prior studies in the literature have explored the consistency of this specific formulation. The most closely related discussions center around a specialized instance of the multi-class logistic loss (also referred to as conditional random field in that context), in which $\\ell(y’, y)$ disappears within the framework of the voted conditional random field. The previous work by Osokin et al., Ciliberto et al. and Nowak et al. point out that the multi-class logistic loss cannot be consistent in structured prediction due to the absence of the target loss function within its formulation. Instead, our result shows that, even when integrating the target loss $\\ell(y’, y)$ within its formulation, the voted conditional random field cannot be consistent.\n\n**2. Usually Fisher consistency is defined relative to a target loss function. What is the target loss function here?**\n\n**Response:** The target loss function is the one described in lines 82 - 90, where $\\ell$ is a symmetric loss defined over $\\mathcal Y \\times \\mathcal Y$. For example, for sequences, $\\ell$ may be the Hamming loss or some other rational loss. The surrogate losses typically adopted in structured prediction are expressed in terms of $\\ell$. For example, for StructSVM, the surrogate loss is defined by $\\mathsf L^{\\text{StructSVM}} (h, x, y) = \\max_{y' \\neq y} \\max \\bigg\\\\{ 0, \\ell(y', y) - (h(x, y) - h(x, y') ) \\bigg\\\\}$.\n\nOur study of $H$-consistency bounds is general: we make no other assumption about $\\ell$ beyond symmetry.\n\n**3. I think the primary avenue the paper could be (significantly) strengthened is via an empirical analysis — the authors could illustrate the consistency (and computational costs) of the comp-sum, structured constrained losses through real-world examples. That would really tie together the whole message of the paper.**\n\n**Response:** Thank you for the suggestion. Our paper mainly focuses on the theoretically principled surrogate losses for structured prediction based on $H$-consistency bounds. While we have demonstrated that the minimization of several proposed loss functions such as structured logistic loss benefit from efficient algorithms, we recognize the importance of further exploration. As such, we intend to dedicate future work to an extensive empirical analysis and the development of more universally applicable algorithmic solutions to encompass a broader family of surrogate loss functions as well as a diverse range of target losses.\n\n\n"}, {"review_id": "ihaW2eM7TK", "reviewer": "Reviewer_wtd4", "summary": "In this paper, the authors study surrogate losses for structured prediction problems. They show that surrogate losses proposed in previous work are not Bayes-consistent, i.e. a sequence of hypotheses which minimises the surrogate loss may not minimise the target loss. They then introduce two families of surrogate losses, namely structured comp-sum losses and structured constrained loss functions, which generalise two corresponding existing families to the structured prediction setting, and show that these admit $\\\\mathcal{H}$-consistency bounds, a stronger form of consistency that also implies Bayes-consistency. Last, they derive practically efficient algorithms for minimising the surrogate losses they have introduced, under certain settings.", "questions": "Please see a list of questions and suggestions for improvement I have about the paper, organised roughly in order of appearance:\n\n- __Line 83:__ The authors say “naturally $\\\\ell$ is symmetric”. Does it have to be symmetric, or are they assuming it to be symmetric?\n\n- __Lines 95-97:__ The phrasing here could perhaps be clarified to “which guarantees that minimizing the generalization error for a surrogate loss $L_{\\\\text{sur}}$ over $\\\\mathcal{H}_{\\\\text{all}}$ also leads to the minimization of generalization error for the target loss $L$.”\n\n- __Definition 1:__ This appears to have typos. First $f_n$ appears in eq. 3 but it is not defined. Second, $h$ appears in the definition but not in eq. 3. Do the authors mean $h_n$ in the definition and $h_n$ instead of $f_n$ in eq. 3?\n\n- __Definition 2:__ How is $\\\\mathcal{H}$ defined (in line 107)? Is this a subset of the full hypothesis set? If so, the authors could clarify this by saying “Given a subset of the hypothesis class $\\\\mathcal{H} \\\\subseteq \\\\mathcal{H}_{\\\\text{all}}$, a surrogate loss…”.\n\n- __Equation below line 116:__ Should the expression on the right hand side have the conditional distribution $p(y | x)$ rather than the joint $p(x, y)$?\n\n- __Comment on notation:__ In line 117 the authors could use the notation $\\\\mathcal{C}_{L, \\\\mathcal{H}}^*(x)$ to make this consistent with the notation under eq. 79.\n\n- __Line 122:__ Typo, “hypothesis set” not “hypothesis sets”.\n\n- __Line 129:__ Typo, the “possible predictions” instead of “possible prediction”.\n\n- __Lemma 3:__ Similarly to the above comment for line 116, should the lemma involve the conditional $p(y | x)$ rather than the joint $p(x, y)$? Furthermore, the authors don’t seem to be using Lemma 3 (or referring to it) in the rest of the main text. In this case, I would suggest removing it and deferring it to the appendix.\n\n- __Theorem 4:__ I have two questions regarding Theorem 4:\n    - First, in line 650, Appendix C, you refer to $h^*$ as “the Bayes classifier” of the structured max loss. I think a more accurate statement would be that $h^*$ is “__a__ Bayes classifier”, because there exist many choices of $h$ which minimise the generalisation error. For example, consider $h^*(x, 1) = h^*(x, 2) = 1$ and $h^*(x, y) = 0$ for all other $y > 2$. This also minimises the generalisation error, and coincides with the Bayes classifier of the target loss.\n\n    - Second, the proof of this result seems to highlight a way in which the problematic classifiers (i.e. the classifiers which are optimal for the surrogate loss, but not for the target loss) are far fewer than those which are optimal for the target loss. In particular, is it correct to say that the set of classifiers which optimise the surrogate loss but not the target loss are those for which $h(x, y_1) = h(x, y_2) = \\\\dots = h(x, y_n)$, and this set is much smaller than the set of classifiers which optimise both the surrogate as well as the target loss (that is the set of classifiers for which $h(x, y_i) > h(x, y_3), \\dots, h(x, y_n)$ for either $i = 1$ or $i = 2$). Can the authors comment on this point? For example, could one learn $h$ with an algorithm that involves a randomisation step (e.g. randomised initialisation), that results in convergence to the Bayes-optimal predictor of the target loss with high probability?\n\n- __Line 663:__ In Appendix D, in the proof for Theorem 5, the authors introduce the quantity $\\\\Phi_y$. Is this simply a function from $\\\\mathcal{Y}$ to $\\\\mathbb{R}$?\n\n- __Theorem 5:__ The proof of Theorem 5 relies on an argument (line 663) where the authors consider a loss $\\ell(y’, y)$ that decouples (i.e. factorises) into a term that depends solely on $y$ only and another term which depends solely on $y’$. From this, they show that the VCRF loss is not Bayes-consistent. Some common losses, such as the zero-one $\\\\ell_{0-1}$ loss do not decompose in this way. When constrained to such losses, is the VCRF loss Bayes-consistent? How critical is the factorisation requirement in the proof?", "limitations": "In my assessment, I do not see any substantial limitations of this work which have not been addressed by the authors. However, I would appreciate the authors’ clarification on the questions I have raised above regarding the argument in the proofs of Theorems 4 and 5.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "__Paper highlights shortcomings of existing theory:__ The authors prove that existing surrogate loss functions, namely the structured max loss and the structured voted conditional random field loss, are not Bayes-consistent. Therefore, minimising one of these surrogates is not guaranteed to also minimise the corresponding target losses. This result is likely of interest to the wider community.\n\n__Introduction of new structured losses supported by theory:__ This work introduces two classes of surrogate losses, namely the structured comp-sum and the structured constrained loss, which they show to be $\\\\mathcal{H}$-consistent. This implies Bayes consistency, a guarantee that was missing from existing structured surrogate losses. In fact, $\\\\mathcal{H}$-consistency is a stronger guarantee than Bayes-consistency, since, as the authors point out, it is not asymptotic and accounts for the hypothesis set $\\\\mathcal{H}$ in question.\n\n__Theoretically sound and technically precise:__ Although I was not able to check the entirety of the derivations in the Appendix (I did not verify the proofs of Theorem 6 and Theorem 8 closely enough to be fully confident about these), other parts which I did check closely looked sound and technically precise to me. Also, generally, I found the paper to be carefully written and I also found that the notation was precise and clear (though I thought Section 6 could have been better organised to improve readability, and that the paper could have benefited from a conclusion section).", "weaknesses": "__The exposition of the paper could be improved:__ While I found that the notation and definitions in the paper are clear and precise, I found that from Section 6 onwards, the paper has tougher to follow, and the exposition was far denser and less clear than in the preceding sections. I think that the paper could benefit by organising the key results in lemmas and propositions, and deferring more some of the details from this section into the appendix.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback and suggestions on improving the readability. We will take them all into account when preparing the final version. Below please find responses to specific questions.\n\n**Weaknesses:**\n**The exposition of the paper could be improved: While I found that the notation and definitions in the paper are clear and precise, I found that from Section 6 onwards, the paper has tougher to follow, and the exposition was far denser and less clear than in the preceding sections. I think that the paper could benefit by organising the key results in lemmas and propositions, and deferring more some of the details from this section into the appendix.**\n\n**Response:** Thank you for your suggestions.  We recognize that Section 6 may seem dense due to the necessity of introducing new notations and technical tools for efficient gradient computation and inference in structured prediction. We will follow your suggestion regarding the organization and will simplify our presentation to make it more accessible to readers. The addition of an extra page in the final version will also enable us to include more discussions in the main body, further enhancing the clarity and depth of our work.\n\n**Questions:**\n\n**1. Line 83: The authors say “naturally is symmetric”. Does it have to be symmetric, or are they assuming it to be symmetric?**\n\n**Response:** Yes, $\\ell$ is assumed to be symmetric in our analysis. We will clarify that. We meant that this is a natural assumption since all instances of $\\ell$ that we are familiar with in structured prediction admit this property.\n\n**2. Lines 95-97: The phrasing here could perhaps be clarified to “which guarantees that minimizing the generalization error for a surrogate loss $L_{\\mathrm{sur}}$ over $H_{\\mathrm{all}}$ also leads to the minimization of generalization error for the target loss $L$.”**\n\n**Response:** Thank you for the suggestion. We will clarify that in the final version.\n\n**3. Definition 1: This appears to have typos. First $f_n$ appears in eq. 3 but it is not defined. Second, $h$ appears in the definition but not in eq. 3. Do the authors mean $h_n$ in the definition and $h_n$ instead of $f_n$ in eq. 3?**\n\n**Response:** Thank you for pointing that out. You are indeed correct: $h$ and $f_n$ should be corrected to be $h_n$ in the definition. We will fix that in the final version.\n\n**4. Definition 2: How is $H$ defined (in line 107)? Is this a subset of the full hypothesis set? If so, the authors could clarify this by saying …**\n\n**Response:** Yes, $H$ is a subset of the family of all measurable functions. We will clarify that following your suggestion.\n\n**5. Equation below line 116: Should the expression on the right hand side have the conditional distribution $p(y | x)$ rather than the joint $p(x,y)$?**\n\n**Response:** Sorry for the confusion. We use the notation $p(x, y)$ to denote the conditional distribution as mentioned in line 115. We will make it more clear in the final version.\n\n**6. Comment on notation: In line 117 the authors could use the notation $\\mathcal{C}^{*}_{L,H}(x)$ to make this consistent with the notation under eq. 79.**\n\n**Response:** Thanks, we will take your suggestions into account.\n\n**7. Line 122: Typo, “hypothesis set” not “hypothesis sets”.**\n\n**8. Line 129: Typo, the “possible predictions” instead of “possible prediction”.**\n\n**Response:** Thank you, we will correct these typos.\n\n**9. Lemma 3: Similarly to the above comment for line 116, should the lemma involve the conditional $p(y | x)$ rather than the joint $p(x,y)$? Furthermore, the authors don’t seem to be using Lemma 3 (or referring to it) in the rest of the main text. In this case, I would suggest removing it and deferring it to the appendix.**\n\n**Response:** Sorry for the confusion. We use the notation $p(x, y)$ to denote the conditional distribution as mentioned in line 115. We will make it more clear in the final version. We will consider moving Lemma 3 into the appendix following your suggestion.\n\n**10. Two questions regarding Theorem 4.**\n\n**Response:** With regard to your first question, you are indeed correct; the use of \"a Bayes classifier\" is more fitting in this context.\n\nAs for your second question, it is definitely an intriguing one! You are right that in the given example, the set of classifiers that optimize the surrogate loss without optimizing the target loss is much smaller than the set that optimizes both. However, the applicability of this observation to general problems remains unclear. The idea of randomization in this context is indeed natural and potentially fruitful. We have explored a similar randomization idea in a different context without success but it is certainly a valuable avenue for further research.\n\n\n**11. Line 663: In Appendix D, in the proof for Theorem 5, the authors introduce the quantity $\\Phi_y$. Is this simply a function from $\\mathcal{Y}$ to $\\mathbb{R}$?**\n\n**Response:** Yes, that’s right. We will further clarify that.\n\n**12. The proof of Theorem 5.**\n\n**Response:** That's a great question. In Theorem 5, we examine Bayes consistency within the context of structured prediction. This refers to the consistency property that must be maintained across any target loss function, as described in Definition 1. In our current proofs, we use the decoupling property of the target loss as a convenient technical assumption, facilitating the demonstration that surrogate loss and target loss lead to different Bayes classifiers. We believe that our proof can be extended beyond this assumption to encompass a more extensive family of target loss functions. However, it is definitely intriguing to investigate the consistency question further, especially when restricted to specific target loss functions.\n"}, {"review_id": "xYjqxV3uV9", "reviewer": "Reviewer_y5Sa", "summary": "This work extensively studies surrogate losses for structured predictions supported by H-consistency bounds. It first shows several negative results for some widely used surrogate losses in structured predictions: no non-trivial H-consistency bound can be derived. Then it provides two new families of surrogate losses that are supported by H-consistency bounds (which imply Bayes consistency): structured comp-sum losses and structured constrained losses. Finally, efficient algorithms are proposed for some of these new surrogate losses.", "questions": "1. When you say \"no non-trivial H-consistency bounds can be derived\", what are the \"trivial H-consistency bounds\"?\n2. How are the results of this work related to those in several works by Ciliberto et al., 2016, 2019, and 2020?", "limitations": "I could not find the location where the limitations of the work were explicitly discussed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This work presents a solid theoretical study in the field of structured predictions. First, the paper shows that structured max losses (which include loss functions associated with several prominent structured prediction algorithms in the literature) are not Bayes consistent, which implies they cannot be supported by H-consistency bounds either (Theorem 4). Then, it shows that voted Conditional Random Field losses (which have been presented in some works of structured predictions) are not Bayes consistent either (Theorem 5). Moving to positive results, the paper provides two new families of surrogate losses that are supported by H-consistency bounds (which imply Bayes consistency): structured comp-sum losses and structured constrained losses (Theorem 6, 8, Corollary 7, 9). Finally, it presents efficient algorithms for minimizing several of the proposed surrogate losses.\n\nThe level of originality exhibited in the research was noticeable, demonstrating a study (H-consistency bounds in structured predictions) that has not been extensively explored before. The quality of the work is good, with meticulous comparisons and contrasts with previous works (including some prominent ones) in structured predictions (Line 134-145, 157-162) and detailed analysis, supporting the authors' arguments convincingly. The paper is well-written at large (some suggestions for improvements below). The work is significant; it offers valuable insights into an under-researched topic (H-consistency bounds in structured predictions), and the implications of the findings could stimulate new directions for future research in structured predictions.", "weaknesses": "1. The current manuscript does not have a conclusion section. Given that the results are already impressive, the authors should have shortened Section 6 and added a conclusion section to improve the readability further.\n2. Because the authors showed the gradient of the structured logistic loss can be computed efficiently and claimed practical use, the authors should consider including some experiments for demonstration.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciation of our work. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.\n\n**Weaknesses:**\n\n**1. The current manuscript does not have a conclusion section. Given that the results are already impressive, the authors should have shortened Section 6 and added a conclusion section to improve the readability further.**\n\n**Response:** Thank you for the suggestion, we will definitely add a conclusion section.\n\n**2. Because the authors showed the gradient of the structured logistic loss can be computed efficiently and claimed practical use, the authors should consider including some experiments for demonstration.**\n\n**Response:** We will take into account your suggestions when preparing the final version. Our paper mainly focuses on the theoretically principled surrogate losses for structured prediction based on $H$-consistency bounds. While we have demonstrated that the minimization of several proposed loss functions such as structured logistic loss benefit from efficient algorithms, we recognize the importance of further exploration. As such, we intend to dedicate future work to an extensive empirical analysis and the development of more universally applicable algorithmic solutions to encompass a broader family of surrogate loss functions as well as a diverse range of target losses. \n\n**Questions:**\n\n**1. When you say \"no non-trivial H-consistency bounds can be derived\", what are the \"trivial H-consistency bounds\"?**\n\n**Response:** We refer to a bound as in (4) where $f(t)$ does not tend to zero as $t$ approaches zero, for example because it is lower bounded by a constant. In such cases, the bound becomes uninformative about the left-hand side even when the argument of $f$ is small, and it does not even guarantee Bayes-consistency when $H$ represents the family of all measurable functions. We will further clarify on this matter in the final version.\n\n**2. How are the results of this work related to those in several works by Ciliberto et al., 2016, 2019, and 2020?**\n\n**Response:** Ciliberto et al. [2016] focused on a least squares surrogate loss function and corresponding framework. In this framework, the structured prediction problem is cast as a regression problem. They derived a regularization approach to structured prediction from the least squares surrogate loss and proved the Bayes-consistency of that approach. Ciliberto et al. [2019] focused on a local structure-adapted framework for structured prediction. They proposed a novel structured prediction algorithm that adaptively leverages locality in the learning problem. Ciliberto et al. [2020] developed a general framework for structured prediction based on implicit embedding. Their methods lead to polyhedral-type surrogates losses that benefit from Bayes-consistency.\n\nOn the other hand, our work presents an extensive study of surrogate losses for structured prediction supported by $H$-consistency bounds. Different from the surrogate losses studied in the previous work, the formulations of our proposed surrogate losses including structured comp-sum losses and structured constrained losses are completely novel and do not cast structured prediction problems as a regression problem. Furthermore, we prove stronger consistency guarantees that imply Bayes-consistency for these new proposed families of surrogate loss. We will further clarify and detail these comparisons in the final version.\n\n**Limitations:**\n**I could not find the location where the limitations of the work were explicitly discussed.**\n\n**Response:** Thank you for pointing it out. We will add a separate discussion on potential limitations in the final version."}, {"review_id": "9rZdsVKV1h", "reviewer": "Reviewer_oyCT", "summary": "This work studies $\\mathcal{H}$-consistency of surrogate losses for structured prediction. The authors show that non classic surrogate losses are not $\\mathcal{H}$-consistent thus not Bayes-consistent. They propose two families of $\\mathcal{H}$-consistent losses as extensions to existing losses and algorithms for two special cases of loss.\n\n", "questions": "I have a few minor concerns as follows.\n\n1. The inconsistency results for each individual classic loss in Section 3 are not new but the authors seem to give a novel unified view of four losses. Does this include Fenchel-Young losses?\n\n2. The consistency bounds in Theorem 6 and 8 depend on a quantity defined by the minimizability gap, which is difficult or impossible to minimize or estimate. I understand that a non-asymptotic bound is desirable but isn't it implicit since we may not obtain an estimated upper bound for a special case unlike what we can do with a generalization bound based on Rademacher complexities?\n\n3. Can you discuss and compare $\\mathcal{H}$-consistency with Fisher consistency since there is a requirement for Fisher consistency in terms of a comparison inequality? (Nowak et al., 2020) (Blondel, 2019)\n\n4. Section E presents proofs for each of the four structured comp-sum losses individually but Theorem 6 is stated for general structured comp-sum losses. Does the conclusion hold or did I miss something?\n\n5. Line 270, $\\bar{\\ell}_i$ instead of $\\ell_i$.\n\n6. I am confused with the definitions about Markovian features in lines 287-294. Specifically, what's the definition of $p$? Based on the context, I can infer that $\\mathbf{\\Psi}$, $\\mathbf{\\psi}$, $\\mathbf{\\Psi}_k$, $\\mathbf{\\psi}_k$, $\\tilde{\\psi}$ all refer to a vector in $\\mathbb{R}^d$. But what is the number of padding zeros in the definition of $\\tilde{\\mathbf{\\Psi}}_k$ in line 290?\n\n7. Due to the theoretical nature of this work, experiments may not be necessary. But is it possible to compare the proposed consistent losses with other consistent losses empirically (Nowak et al., 2020) (Blondel, 2019)?\n", "limitations": "Limitations are mentioned together with introduction of methods. Potential negative societal impacts are not discussed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The manuscript is well-written with few typos. The theoretical results are sound and novel. Practical optimization methods are provided to show that the proposed losses are not only consistent but also computationally feasible.", "weaknesses": "I don't see obvious weaknesses in the manuscript. A possible drawback might be the lack of empirical results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciation of our work. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.\n\n**Questions:**\n\n**1. The inconsistency results for each individual classic loss in Section 3 are not new but the authors seem to give a novel unified view of four losses. Does this include Fenchel-Young losses?**\n\n**Response:** The formulation presented in Section 3 differs from a general formulation of Fenchel-Young losses (or Bregman divergence losses), even though they both encompass specific instances. For example, both include the hinge loss of support vector machines.\n\n**2. The consistency bounds in Theorem 6 and 8 depend on a quantity defined by the minimizability gap, which is difficult or impossible to minimize or estimate. I understand that a non-asymptotic bound is desirable but isn't it implicit since we may not obtain an estimated upper bound for a special case unlike what we can do with a generalization bound based on Rademacher complexities?**\n\n**Response:** That’s a natural question. Let us first mention that the minimizability gap can be crudely upper bounded by the approximation error. But, more significantly, although we have not detailed it in this paper, the minimizability gap can in fact be upper bounded in terms of useful terms depending on the magnitude of the parameter space. Our $H$-consistency bounds can be used to derive finite sample learning bounds for a hypothesis set $H$ expressed in terms of the Rademacher complexity of the hypothesis set and the loss function and an upper bound on the minimizability gap for the surrogate loss. We will elaborate on that in the final version. \n\n**3. Can you discuss and compare $H$-consistency with Fisher consistency since there is a requirement for Fisher consistency in terms of a comparison inequality? (Nowak et al., 2020) (Blondel, 2019)**\n\n**Response:** With Nowak et al.'s (2020) definition, Fisher consistency coincides with the specific case of $H$-consistency, where $H$ is the family of all measurable functions. However, when dealing with a constrained hypothesis set $H$, the comparison inequality does not yield an $H$-consistency bound that relates the surrogate estimation loss to the target estimation loss in terms of minimizability gaps.\n\n**4. Section E presents proofs for each of the four structured comp-sum losses individually but Theorem 6 is stated for general structured comp-sum losses. Does the conclusion hold or did I miss something?**\n\n**Response:** Theorem 6 represents a consolidated result for the four structured comp-sum losses, with the proofs for each being presented separately in Section E. We will clarify this distinction in the final version.\n\n**5. Line 270, $\\bar \\ell_i$ instead of $\\ell_i$.**\n\n**Response:** Thanks, we will correct that.\n\n**6. I am confused with the definitions about Markovian features in lines 287-294. Specifically, what's the definition of $p$? Based on the context, I can infer that $\\Psi$, $\\psi$, $\\Psi_k$, $\\psi_k$, $\\tilde{\\psi}$ all refer to a vector in $\\mathbb{R}^d$. But what is the number of padding zeros in the definition of $\\tilde{\\Psi}_k$ in line 290?**\n\n**Response:** Each $\\Psi_k$ corresponds to a Markovian feature vector based only on $k$-grams, $p$ is the largest $k$. We will fully clarify the notation in the final version.\n\n**7. Weaknesses: I don't see obvious weaknesses in the manuscript. A possible drawback might be the lack of empirical results.** \n\n**Due to the theoretical nature of this work, experiments may not be necessary. But is it possible to compare the proposed consistent losses with other consistent losses empirically (Nowak et al., 2020) (Blondel, 2019)?**\n\n**Response:** Thank you for the suggestion. We will seek to add such experiments in the final version on the empirical comparison with other consistency losses in previous work. But, as you have mentioned, our paper mainly focuses on the theoretically principled surrogate losses for structured prediction based on $H$-consistency bounds. While we have demonstrated that the minimization of several proposed loss functions such as structured logistic loss benefit from efficient algorithms, we recognize the importance of further exploration. As such, we intend to dedicate future work to an extensive empirical analysis and the development of more universally applicable algorithmic solutions to encompass a broader family of surrogate loss functions as well as a diverse range of target losses. \n"}]

Author rebuttal:

Meta-review: This meta review is based on the reviews, the authors rebuttal and the discussions with the reviewers, discussions with the SAC, and ultimately my own judgement on the paper. There was a consensus that the paper contributes sound and interesting contributions to the field of structured prediction. I feel this work deserves to be featured at NeurIPS and will attract interest from the community. I would like to personally invite the authors to carefully revise their manuscript to take into account the remarks and suggestions made by reviewers. Congratulations!
Decision: Accept (poster)