Moment Distributionally Robust Tree Structured Prediction
Authors: Yeshu Li
Danyal Saeed
Xinhua Zhang
Brian D Ziebart
Kevin Gimpel
Venue: NeurIPS 2022 Accept (2022)
Keywords: structured prediction
robustness
arborescence
projection
dependency parsing

Abstract: Structured prediction of tree-shaped objects is heavily studied under the name of syntactic dependency parsing. Current practice based on maximum likelihood or margin is either agnostic to or inconsistent with the evaluation loss. Risk minimization alleviates the discrepancy between training and test objectives but typically induces a non-convex problem. These approaches adopt explicit regularization to combat overfitting without probabilistic interpretation. We propose a moment-based distributionally robust optimization approach for tree structured prediction, where the worst-case expected loss over a set of distributions within bounded moment divergence from the empirical distribution is minimized. We develop efficient algorithms for arborescences and other variants of trees. We derive Fisher consistency, convergence rates and generalization bounds for our proposed method. We evaluate its empirical effectiveness on dependency parsing benchmarks.

Moment Distributionally Robust Tree Structured Prediction
Yeshu Li
Danyal Saeed
Xinhua Zhang Department of Computer Science
Brian D. Ziebart
University of Illinois Chicago
[yli299, dsaeed3, zhangx, bziebart)@uic.edu
Kevin Gimpel
Toyota Technological Institute Chicago @gimpel@ttic..
Abstract
Structured prediction of tree-shaped objects is heavily studied under the name of syntactic dependency parsing. Current practice based on maximum likelihood or margin is either agnostic to inconsistent with the evaluation loss. Risk minimiza- tion alleviates the discrepancy between training and test objectives but typically induces non-convex problem. These approaches adopt explicit regularization to combat overfitting without probabilistic interpretation. We propose a moment- based distributionally robust optimization approach for tree structured prediction, where the worst-case expected loss over a set of distributions within bounded moment divergence from the empirical distribution is minimized. We develop efficient algorithms for arborescences and other variants trees. We derive Fisher consistency, convergence rates and generalization bounds for our proposed method. We evaluate its empirical effectiveness on dependency parsing benchmarks.
Introduction
Structured prediction is important learning setting for joint prediction of interdependent variables. The output space typically consists of an exponential number structured objects whose inherent relations can be exploited to develop efficient learning algorithms and capture key properties of data [Ciliberto et al., 2019]. Trees are widely used structures that offer expressiveness and simplicity. We distinguish between task is a structure learning problem in graphical models [Bradley and Guestrin, 2010), aimed at constructing trees underlying predictive model from training data. The optimal tree is found easily with greedy algorithms for generative models [Chow and Liu. 1968], while it is NP-hard for the discriminative max- max-margin setting [Meshi al., 2013]. The second task requires prediction itself to be a tree-shaped object (e.g., an incidence vector). Dependency parsing is a crucial application of this problem that has inspired a flurry of work natural language processing. The first-order spanning tree prediction assuming factorization over ares can be done in ((n²) [Stanojević and Cohen, 202 ]. whereas exact inference is NP-hard for certain projjrrojcttvve) higher-order trees (e.g., considering siblings) [McDonald and Satta, 2007]. We study the latter in this work.
different tree structured prediction tasks in the literature. The first
common evaluation criterion in dependency parsing is the attachment score, namely, the would like to maximize on test data. It is cost-sensitive to allow partially correct prediction. Ideally, the training objective should be aligned with the objective. An early attempt to directly mimic test conditions leads to non-convex piece-wise constant objective [Och, 2003]. Risk minimization in appropriate parametric form has non-convex smooth objective, solvable with gradient descent,
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

but still losing global convergence and generalization guarantees. Maximum likelihood approaches formulate a convex smooth problem minimizing logistic loss, consistent with conditional probability estimates but oblivious to test losses. Maximum margin methods have convex objectives able to implicitly incorporate custom losses by scaling margins, but are known to be inconsistent with test losses generally INowak-Vila et al., 2021]. Unfortunately, none of these approaches yield a Bayes optimal estimator for test losses with global convergence and finite-sample generalization guarantees.
Consistent structured prediction methods include Ciliberto et al. [2016], Blondel [2019], Nowak- Vila et al. [2020]. the latter two of which are based on Fenchel- Young losses [Blondel et al., 2020]. However, none of them have addressed the tree structured prediction problem explicitly. For instance, Blondel [2019] calls for Euclidean or Kullback-Leiin
projection oracles, which do not exist in an efficient sense from what we know for arborescence (directed tree) polytopes. In addition, the Frank- Wolfe type algorithm adopted by Nowak Vila et al. [2020] requires a max-min oracle and converges in rate of O()). Furthermore, all of the above methods belong to empirical risk minimization (ERM) that requires explicit regularization to combat overfitting, which can be quite vulnerable in high-dimensional settings (e.g., scarce data).
To address the above issues, we propose an estimator from first principles in distributionally robust optimization (DRO). It minimizes the worst-case risk over an ambiguity set of distributions within bounded moment divergence from the empirical distribution. We seek probabilistic prediction by assuming non-deterministic groundtruth labels, which, together with the ambiguity set, models uncertainty about the unknown true distribution. We interpret the primal problem a dual-norm- regularized surrogate loss minimization problem. Note that prior art applying moment- based DRO to rre-structured graphical models [Fathony et al., 2018b] and bipartite matching [Fathony et al., 2018a] adopts special case of our ambiguity set in which the empirical feature moments are matched exactly and regularization has to be imposed manually. This moment-based DRO also allows us to derive generalization bounds regarding true worst-case risks. When the ambiguity radius is zero, the DRO estimator is shown to be consistent. We develop two practical algorithms, one based on game theory and the other based on marginal probabilities of tree parts. We further propose efficient Euclidean projection oracles onto the arborescence polytope with linearly convergent guarantees. We conduct experiments three common dependency parsing datasets, suggesting that our method is particularly effective with little training data.
Contributions. Our contributions are summarized as follows. (1) We propose distributionally robust tree structured prediction method and show its equivalence to regularized surrogate minimization. (2) We derive its generalization bounds and consistency. (3) We propose efficient algorithms based on projection oracles for arborescence polytopes. (4) We perform empirical study on real-world datasets.
Paper structure. We begin with problem setup and existing work in Section 2. We present our method with theoretical analysis in Section 3. Section 4 proposes efficient projection oracles. Section discusses extensions beyond first-order directed trees. Experimental results of comparing our method with a competitive baseline are given in Section 6. We conclude the paper in Section 7.
Background and Related Works
2.1 Tree Structured Prediction
Consider a weighted directed multi-graph G = E),E) where each are (i,j,() E È from node i to has a label I. By designating root node r E V, we say that A S E is an r-arborescence of & (),,4) is a directed spanning tree rooted at r. For any E V. denote by 5 (w) == [( E E j m) the set of its incoming arcs, and 8+ (v) == [i.j..) E & = e} the set of its outgoing ares.
Let X be the input space and y A Unex V(x) be the output space where )'xx) represents the set r- arborescences of graph (ax) formed by æ. Dependence
is suppressed when context is clear. Let R C 2 be a set of parts with È C R. Each part s E R is a subset of arcs. It is convenient to represent
E y as a binary vector with y/2 = 1 iff part appears in y. Let wo xx y) & EVER we ye) be score function decomposing over parts, parameterized by 0. Let {(x((1) y ("))
I==1 be a set
of m training examples drawn i.i.d. from distribution P E P( ))), where each (6) is an
r-arborescence. The goal of tree structured prediction is to learn a function h: X - y from training data. Assume that the evaluation criterion is loss function é ) x y - Rzo.

---

We introduce existing methods in the setting of geraph-basedd projectte,, syntactic) dependency parsing where a sequence tokens and (xx) encodes dependencies among tokens.
Maximum Likelihood
A probabilistic modeling approach based on exponential family distributions maximizes the condi- tional ligliikl of the training data:
log Po (y (z)0)==
Σ log lexp (wo y(0))/()))))
min
where ((x) A E (x exp (1. y)). This problem is convex for log-linear models, but in- tractable for general R. [Koller and Friedman, 2009]. The first-order arc-factored model (R E) is equivalent to loop-free factor graph, rendering it tractable via the matrix-tree theorem [Kirchhoff, 1847, William, 1984, Koo et al., 2007, McDonald and Satta, 2007, Smith and Smith, 2007]. Neural parsers either leverage the same theorem to compute the partition function [Ma and Hovy, 2017] consider the parent node distribution independently for each node by local normalization [Dozat and Manning, 2017, Zhang et al., 2017]. Higher-ordes models require approximate algorithms such as loopy belief propagation [Murphy et al., 1999] and Markov chain Monte Carlo [Brooks, 1998]. This approach does not incorporate task-specific losses. In fact, with maximum a posteriori (MAP) decoding, it is not consistent with any specific loss in general [Nowak-Vite al., 2019].
2.3 Maximum Margin
An alternative approach based on maximum margin Markov networks (Taskar et al., 2003] or structured support vector machines [Tsochantariddis al., 2005] optimizes hinge-type surrogate:
wa (1) ()) + max Ely (6) ,)) + wa wa(a .y)
min
which inspires rich line of work based on MAP inference with manual features [Taskar et al., 2004, McDonald et al., 2005, McDonald and Pereira, 2006, Martins et al., 2009, 2010, 2015, Zhang et al., 2014] or deep learning [Kiperwasser and Goldberg, 2016, Wang and Chang, 2016]. Approximate MAP inference is required for models beyond first-order. A smooth variant called saftmax-marginn [Gimpel and Smith, 2010] incorporates the task-specific loss É but still implicitly minimizes it. Margin-based objectives are known to be consistent only under very restrictive conditions [Liu, 2007, Nowak- Vila et al., 2021] (i.e., data with majority label, loss being distance).
2.4 Minimum Risk
Empirical risk minimization suggests directly optimizing the expected target loss on training data:
m
Po (() (,y).
min
V
which is commonly non-conver due to normalization of pe- There are a few parsers optimizing this objective via back propaarooaat [Stoyanov and Eisner, 2012], bebest lists [Smith and Eisner, 2006), semirings [Li and Eisner, 2009, Zmigrod et al., 2021] and other differentiable approximations [Gormley et al., 2015, Mensch and Blondel, 2018). Local optima found by these algorithms do not satisfy the premise of Fisher consistency and make difficult to quantify generalization errors.
2.5 Distributionally Robust Optimization
Distributionally robust optimization has attracted emerging interests in improving machine learning models due to its connections to robustness, regularization and generalization. It proposes to minimize a risk with respect to the worst-case distribution chosen by an adversary in some uncertainty set:
min max Eq [e(e(Y, (x(x))()))))) x))]
QEB
3

---

where B is an ambiguity set that can be defined by discrepancies [Shafieezadeh- -bauehh et al., 2019, Duchi and Namkoong. 2019], moments [Delage and Ye. 2010, Farnia and Tse, 2016], shapes [Popescu, 2005, Hanasusanto et al., 2015] and kernels [Shang et al., 2017, Staib and Jegelka, 2019]. thorough review can be found in Rahimian and Mehrotra [2019]. We focus on moment-matching discriminative approaches while similar generative method is proposed in Ganapathi et al. [2008].
3 Method
We introduce the formulation, followed by practical algorithms for learning and inference. Afterwards, we present the theoretical guarantees. We defer all proof's to Appendix A.
3.1 Formulation
We assume that the evaluation criterion is the Hamming loss E(y.y') == 1y * v/) with (.) being the 0-1 indicator function, but the results in this paper generalize to losses with affine decomposition [Ramaswamy et al., 2013] easily.
Let jpiiue be the true distribution and ppem be the empirical distribution. Our approach builds upon probabilistic predictor that non-parametrically minimizes the expected loss with regard the most adverse distribution in an uncertainty set where the distributions are away from the empirical distribution in terms of feature moment difference:
min max ((B()))))
y (Y,Y)
(1)
where B(FemF) == (Q: Qx = F || ((-) Eg ( S }} with 2 and Φ X' x - Rd a joint feature mapping decomposable over parts: (xx, y) E. Φ(x, va). In Farnia and Tse [2016], cross-moments are adopted: Φ(æ, y) == xx ()) @ Øy (y) where @ is the tensor product.
P
By Fenchel duality [Altun and Smola, 2006] and strong duality [Von Neumann and Morgenstem, 1947], we show that Eq. (1) is analogous to dual-nome noom- -or--nogularizee regularized surrogate loss minimization:
Proposition 1. The distributionally robust tree structured prediction problem based on moment divergence in Eq. (1) can be rewritten
min min max We X
x1x 2xix (( Y) + O -(10))(((() ()
-)
(2)
&
(x,
where 0 E Rd the vector of Lagrangian multipliers and II-II+ is the dual norm of II-II-
3.2 Constraint Generation Solution
From a game-theoretic rationale [Topsøe, 1979, Grünwald and Dawid, 2004], Eq. (1) is considered as an iiversary-conssrainne zero-sum game. prediction player chooses a of stochastic strategies (conditional distributions over arborescences) in order to minimize the expected payoff whereas an adversarial player chooses constrained strategies maximize it. The payoff for pair of pure strategies is the incurred loss, E(j, ÿ). The constrained game is transformed to set of unconstrained ones in Eq. (2) whose payoffs are parameterized by O: payoff( ú) - E(g. ÿ) + OT (ax ÿ). Note that the games in Eq. (1) are jointly constrained for æ's in the support of IXx while the ones in Eq. (2) are conditionally independent given a. The unconstrained game can be solved by linear program [Von Neumann and Morgenstern, 1947]. However, there are O(n") spanning trees in a complete graph, thus making explicit construction of the full payoff matrix impractical.
We adopt constraint generation algorithm named double oracle [MeMahan al., 2003], shown in Appendix B. It builds a payoff sub- mat-ixtrix starting from small initial sets of strategies. In each iteration, each player takes their turn based on the game payoff sub-matrix by finding the best response among all possible strategies to the opponent's 's optimal mixture strategies. The response is added to a player's s strategy set it improves the value of the game, with the sub-matris updated. The algorithm terminates and converges to a Nash equilibrium of the original game when the strategy sets no longer grow. The size of the final sub-matrix usually small practice but there are no known theoretical guarantees, thus way to analyze the convergence behavior. Finding the best response requires an

---

oracle, equivalent to finding the minimum weight arborescence. The objective in Eq. (2) is a convex function of 0, so we can optimize it with sub-gradients based on solutions of the inner zero-sum games. Although lacking convergence guarantees, this algorithm is flexible with custom losses and provides a game-theoretic perspective to a typical DRO problem.
3.3 Marginal Distribution Formulation
The r-arborescence polytope is defined as the convex hull of all vectors representing r-arborescences: Auti (x:) Conv (y IR RI y {(z)))) Note that each p Aubb is convex combination of all r-arborescences: p Ey Prob(y)y, where ps denotes the marginal probability of part s. Here adopt the squared l2 norm as the dual norm and an ambiguity radius of A/2. By substituting the marginal probability vectors and switching min-max optimization orders, we simplify Eq. (2) into
max min q E>s 0
min (q A
TT 10) - -p. " 1 Pemp))
(3)
Ipll 2リ
11 2
1012
(3)
where (()) E xd denotes the feature matrix of the i-th training data, μ Rzo is a smoothing
parameter to induce strong convexity. We push the maximization
q the outermost level because of its large computational cost. If = O, the solution to Eq. (3) is also optimal to Eq. (2) by strong duality but the problem becomes non-smone non-smooth. Therefore expect 0 obtained with very small positive μ to be a good approximation 6 obtained with μ =
To optimize it, with fixed due to strong convexity, the unconstrained minimization over 0 yields pmm))) In contrast, the constrained minimization over p admits no closed-form solution but can be cast as Euclidean projection onto Aub instead, independently for each i E [m]] p = Ain |pp - g (+) P Proj ( (1). Given 0 and p'. the outermost maximization can be solved by a projected quasi-Newton algorithm [Schmidt et al., 2009] that also requires the projection oracle Proj Amo (-), elaborated in Section 4.
0- -- mb Ex= ( (Tq())
3.4 Inference
We propose two algorithms to make inference with given 0"
Weight construction. Construct the part weights as -0 E R and find the maximum weight arborescence: y" arg maxy y O0 by the Babow-Tarjan (GT) algorithm [Gabow al., 1986.
Zmigrod et al., 2020] or approximate methods for higher-order trees.
Minimum Bayes risk decoding. The optimal probabilistic prediction P
be obtained from Eq. (2) or Eq. (3). The marginal probabilities enable minimum Bayes risk decoding: y" E arg miny y Epp fly, Y) A arg max, Esy,= P; maximum weight arborescence problem.
3.5 Statistical Properties
Basic generalization bounds of DRO methods derived from measure concentration are not appro- priate for ambiguity set defined by low-order moments in this paper since it fails to converge IShafieezadeh-Abale et al., 2019]. We take an alternate approach following Farnia and Tse [2016] obtain excess out-of-sample risk bounds by assuming boundedness features and losses.
Theorem 2. Given samples, non-negative loss El:,-) such that [e(---) S K. a feature function ((---) such that || ( (| < B, positive ambiguity level >> O, then, for any E (0, 1]. with probability least p, the following excess true worst-case risk bound holds:
4KB
3
In
max ((
R8 cmp)
max (PPm)))
e//
1+
2
2
where 6rmp and the are the optimal parameters learned in Eq. (2) under pemp and pine respectively.
The original risk of O under Q is R2((0) Exx Po {(Y, Y) with Bayes prediction p0
arg minp maxq EQy Pri gÝ Y) + 0T ΦT. Y)
5

---

Theorem 2 presents bound based uniform convergence and Rademacher complexities [Bartlett and Mendelson, 2002], which improves the results Asif al. [2015], who merely show that the worst-case risk upper bounds the risk under any distribution in the ambiguity set.
The dual problem in Eq. (2) suggests adversarial surrogate loss fadv (0, (æz, y)) in ERM form. The special case of = 0 in our DRO estimator has similar form to the max-min surrogate loss in Nowak-Vila et [2020] except that we assume probabilistic prediction. A conclusion of its Fisher consistency can thus be drawn based on Fathony et al. [2018a], Nowak- Vila et al. [2020].
Corollary 3. When e eod Fisher consistent with respect f. Namely, TP Ti bilistic prediction made by the Bayes optimal decision rule, where 0 is defined in Theorem 2.
v is the proba-
I > 0, the decoded prediction for each will not belong to the convex hull of true conditional distributions, thus not a minimizer of L. On the other hand, e chosen as m aa for < a < 1/2, ladv will be universally consistent according to the comparison inequality in Nowak-Vin et al. [2020].
Projection onto Arborescence Polytopes
The Euclidean projection onto r-arborescence polytope is a quadratic programming problem':
eEAn f || 1imn-wll.. wr12.
min
We focus on first-order models and discuss the extensions to other classes of trees in Section 5.
4.1 Frank-Wolfe Algorithm
The Frank-Wolfe (FW) method [Frank et al., 1956] is an iterative first-order algorithm that enforces constraints by optimizing a linear objective over the feasible set at each itcration
E arg min 8 V f(x'),
(4)
which is a minimum weight arborescence problem with weights fzf(=') in our case. The solution is updated and stays feasible: x'-1 <- x' + 7s(s" s x²), where % is step size typically set to 7
FW style algorithms are known to have convergence rate of ((+) [Jaggi, 2013].
4.2 Martin's Polytope
A compact representation of Aub with a polynomial number linear constraints attractive to lead to efficient algorithms. To the best of our knowledge, there is no existing projection method exploiting special structures of this polytope. An extended formulation of the arborescence polytope [Friesen, 2019, Martin, 1991] follows lift-and-project approach. It relates each element existence of k-arboresences of the underlying undirected graph for all k E V. We extend to multi-graphs:
Amats {="
3x
Σ 2 ae5-
VK.j
Σ 24 BEE
V f 20,
where x" E R associated with the original ares E, z² R for A + r is associated with a simple directed graph (V,E') formed by removing directions and splitting each edge {i.j} into two directed ones, Egj : {a E & {i.j}} is the set of connecting and j with ā 2 (i, := {i,j} denoting the underlying undirected edge. We show exact correspondence between Amab and Aub based on a similar argument for simple graphs [Friesen, 2019]:
Proposition 4. Let G be multi- malti-graph. Amarb $ Aurb-
'This is well defined convex optimization problem, different from that in differentiable structured prediction methods [Peng al., 2018, Mihaylova et al., 2020] which elicit gradients with respect to inputs.

---

To solve min Amm - w (ADMM) and rewrite it into the following separable form:
1122 we propose to adopt the alternating direction method of multipliers
min g(u)=
Us
w112
Iuu, (2x))
REV
s.t. Ux = for RI
3z
I 20
Σ
1
Σ
Z =
Σ aEE
E Ta Vi,j
aE (5)
aEE
u, u V U fo
E 20
R
Σ
Ia =
aE
(5)
where (.) is the characteristic function with (x) 0 if a E l and xo otherwise.
Let X/. be the dual variables and AR = 1 X The scaled augmented Lagrangian function is
PE
(u,, A) = (() + Ex2r _ l| uA + A 1 2 1x
The ADMM algorithm updates the parameters as follows:
2w + Pk. (u( f + X%)
++1 == arg min Lp((u), u X - Proju,
4k #
2 + Pk [2]
2u + |1/ Kettr Pk (
++1 X
u 4+ = arg min Lp Lp((uf, u/ 21) & Proju.
EM
2 [V] Ex
Pk
141 A + (u,
u (11
Vk Fr.
This decomposes the original projection problem into simpler projection problems. Projection onto Ur for k = r decomposes over j E V into [V] projections onto simplex, solvable as fast as ((n) in the worst case [Condat, 2016]. For & # computation of u .+1 can be done in parallel. The Lagrange dual problem of Proju,, (-) can be written as
w /
if aaj > 2Wsy/nes a + auyWsy if ag S 2w /Ti,
Σ hiy(a) (WI)EE
- aj s.t. hij(a) jzk
max OER VI
where Waj := EasE, Wa. Rij == E8gl oij = min(as, ar)) and a == +00. Strong duality holds by linear constraint qualification. Primal solutions recovered by x²= wa min /2, wa na)-
Convergence. The dual objective of Proju, (-) is strongly concave on far R fEEA {i,j} e E as S aj Oa S 2wrg/may), with unique global maximizer. This implies fast convergence in practice given good initialization. The negative Lagrange dual function has restricted strong convexity with Cheng, 2015]. Alternatively, exact solutions can be found by enumerating rankings (with duplicates) of a in ((V)) In this manner, the ADMM algorithm with a strongly convex objective has a linear convergence rate O(log ?) with either exact [Deng and Yin, 2016] linearly convergent approximate solution [Hager and Zhang, 2020] of Proju, (.). Using Nesterov's 's accelerated gradient algorithm [Nesterov, 2003] to optimize Eq. (3) leads to iteration complexity OCC log !) with constant C' dependent on Lipschitz constants of gradients and μr.
min;y(ney/2 near the optimum, suggesting linear convergence [Zhang and
Extensions
5.1 Undirected Spanning Trees
An straight-forward way of extending to undirected spanning trees is to split {i.j} into two ares (i,j), (j.2) and make the feature mapping direction-invarre i.c., Φ(x, y.) = 6(x, Vsr) for s and s' having the same underlying undirected graph. We post-process the prediction by removing directions.
Alternatvely, we seek projection oracles for undirected graphs. Projection via FW is done by using any minimum spanning tree algorithm in Eq. (4). For ADMM, the formulation in Martin [1991] is originally for undirected trees: Amund := {0 3z 2 0 - = = 1 4 k) A z + + ( Vk, i E V}. ADMM is casily adapted to this case with Eoec, 2a replaced by 2(rs}-
7

---

5.2 Dependency Trees
The spanning tree structure dependency parsing is special one where the outdegree of root is restricted to be one. We can use the GT algorithm for inference with either the same training objective or an aligned objective where a dependency tree polytope is considered: Ade((z) := Conv (fy e y(()) 16+ (r)) = 1}). A straightforward extension of Amarb to characterizing dependency trees is Amdep = {=" x" E Amarb A Loeg' (r) 2/ = 1}, equivalent to Adep by the following proposition:
Proposition 5. Let & be multi- graph. Amilep _ Adeep
FW methods leverage the GT algorithm Eq. (4). As for ADMM, the dual problem of projection onto U == {a: x E EU,, ^ Enegl (r) Ta = becomes
a/a > 2Wa
max 0,8
Σ aEE
ha (a, (0, B)
aB ' aj B s.t. ha 3)= jfr
Wa Ta
72/4
%a S 2War
where 7(1..)) = 0j 1(i= =1)3. This can be solved in O([E) log (&]) [Zhang et al., 2010].
5.3 Higher-order Polytope
Compact higher-order polytope descriptions exist for undirected spanning trees but are still unknown for arborescences with even monomial [Friesen, 2019]. FW requires linear oracle that is NP-hard to solve exactly in higher-order settings [McDonald and Pereira, 2006].
Instead, we can approximate it with a local polytope where the marginal probabilities of each part required to be locally consistent with that of each arc a. For simplicity, we consider only features for the all-true assignments, i..., all ares exist in part The resulting polytope can be written as Amooe == {x : ag E Amab A Vs E R, a E s Ps S Pa ). which suggests an ADMM algorithm with
Va E s). the projection onto which can be done in O[ss] log |s]). ). See Appendix D for details.
additional constraint sets for each part: U, == {æ R [R] Fg S za
6 Experiments
We evaluate our proposed method on dependency parsing tasks and compare its ability to BiAF [Dozat and Manning. 2017], arguably the state-of-the-arr neural dependency parser. We implement our methods in Python and C². We leverage the implementations in SuPar [Zhang et al., 2020] for the baseline. All experiments are conducted on a computer with an Intel Core i7 CPU (2.7 GHz) and an NVIDIA Tesla P100 GPU (16 GB).
We adopt three public datasets, the English Penn Treebank (PTB v3.0) [Marcus et al., 1993], the Penn Chinese Treebank (CTB v5.1) [Xue et al., 2002] and the Universal Dependencies (UD v2.3) [Nivre et al., 2016). See Appendix C for data-processing details.
Representation learning is not the focus of this paper. We follow Levy et al. [2020] and compare method with the last biaffine classification layer in BiAF on top of pretrained features preceding this layer (backbone's output). The pretrained embeddings produced by complicated non-l non-lincar models make Fisher consistency's assumption of optimizing over all measurable functions less violated. To featurize the data, for each dataset, we train a BiAF network with the whole training set to obtain pretrained model. Note that this may create unfair advantages for the baseline because the last layer was optimized together with the backbone network in an end-to-end manner during pretraining. Moreover, pretraining uses standard ERM objective with the cross-entropy loss and local normalization over head nodes. The pretrained features are thus more adequate for the ERM objective than for our DRO objective. To make use of the features as inputs in our method, take the outer product of the embedding vectors for two nodes as the are feature vector. Our method and the biaffine layer therefore share the same number parameters (501 501, including bias terms). We focus on predicting the unlabeled dependency tree while relying on pretrained models for relation label prediction. The evaluation criteria are the labeled/unlabeled attachment scores (LAS/UAS) and
"Our code is publicly available at https: //tt:p::///ttaa thub. wwwm//aaeeleeee/drteeeeeeeeeeeee
httpps:/ //gi wwwettuu...mmychaeaeeeeee com/yzhangcs/parree
8

---

Table 1: Comparison of mean UAS and execution time under different training set sizes. Time refers to the CPU time taken to finish one gradient descent step. Statistically significant differences compared to BiAF are marked with i (paired t-test, p < 0.05). The best UAS are highlighted in bold.
P18
Dunch
Turti00 (Jow (ewurice)
Methood
Time
10
-00
1000
10300
-00
1000
1050
50
100
1050
100
500
1.00
1000
0.58
90.05
966.87
966885
M7.36
65. 05
10:20
M1.15
01.70
90..9
14..0
94.15
14.00
17.61
216.04
281-75
43.55
Marginal
14.24
11..517
90-811
165992
07:33 12
191
M1.27
01. 87
92.411
94.122
14..501
95. 15-151
21.857
32.831
33.771
43.18
Stochastic
2.72
04.02)
06.51
07.34
89.27
91.011
91.27
92.401
94.231
04.42
25.00]
35.02)
Method
2.5
ADMM
2,0
PW
07:
Clijetive
1.5
100
1e-8
1e-6
1,0g
88-
1e-4
0.5
1e 2
1e0
86-
laanation
Lambda
Figure I: Convergence of ADMM and FW for random points with 95% confidence intervals.
Figure 2: The best UAS with the Marginal algo- rithm as and À vary in logarithmic scales.
labeled/unlabeled complete matches (LCM/UCM). The attachment score can be transformed to the Hamming loss with linear mapping: AS(y. y') & [ - 1 ((y.y')/2
Full batch learning is adopted for Marginal (Eq. (3)). Mini-bated training is adopted for Game, the game-theoretic algorithm, and Stochastic, which solves the inner min-max problem in Eq. (2) using Eq. (3) with fixed 0, All models are trained with the training set only. The optimal hyperparameters and parameters are chosen based on the validation set. See Appendix for detailed parameter values.
To showcase the ability of DRO methods tackling scarce data, in each run, we randomly draw m E {10, 50, 100, 1000} samples without replacement from the training set and keep the original validation and test sets. All the models are trained on the same set of sampled data. The process repeated 5 times for each m. The main UAS results on the PTB, CTB and UD Dutch Lassy Small datasets are reported in Table with complete results provided in Appendix C. Our methods consistently deliver higher UAS than BiAF especially with a small amount of data². With little training data, DRO approaches minimize the worst-case risk to avoid overfitting. With more training data available, our method is still comparable to BiAF which is not significantly better than our methods by statistical tests. This illustrates the advantages of replacing conditional log-likelihook with our Fisher consistent surrogate loss without changing the number of model parameters. Moreover, we study a low-resource setting with the UD Turkish dataset in which only the sampled data is used for pretraining without BERT embeddings. The binary cross-entropy loss (single normalization) is adopted during pretraining in this setting to avoid pretrained features biased towards the multi-class cross-entropy loss (local normalization) adopted by BiAF. We observe consistently competitive performance of our methods in the low-resource setting in Table 1 as well.
We report computational time of one gradient descent step in the second column of Table 1, averaged across 10 runs. For fair comparisons, all the models are run with CPU only, with a batch size of 200. All the methods achieve their optimal validation set performance in 150-300 steps. BiAF and Marginal are the fastest because the most time-consuming step of computing dot products of features and parameters only performed once whereas the other two methods perform multiple times. However, since Marginal is unable to leverage stochastic gradients, its execution time grows lincarly in the full batch size. Henceforth, there is a trade-off between Marginal and Stochastic/Game for computational efficiency. The extra cost compared to BiAF with cross entropy is expected because distributional robustness against a set of adversarial distributions guaranteed.
*The UAS is high with 10 training samples possibly because (1) the backbone sub- nebwoettork and linear layer were trained together with the whole training set: (2) BERT embeddings yield data representation that is easily linearly separable; (3) 10 samples result in many 10 x 20 20 halanced nead-selection instances for BiAF.

---

We compare ADMM and FW by performing for 100 times projection of random points in [-5, 5)75 on graph with 5 nodes and 3 parallel ares between each (i. We subtract the integral part of the observed minimum values in each run for better illustration. As shown in Figure 1, ADMM usually finds a better solution in the arborescence polytope than FW does within 1000 iterations That being said, the per-iteration cost of ADMM is about 8n times higher than that of FW due to consensus optimization n subproblems. In practice, the solution computed with FW usually leads to approximately good sub-derivative to optimize the DRO objective. We have verified that the solutions suggested by ADMM satisfy the polytope constraints for graphs of up to 10 nodes.
We conduct sensitivity analysis by varying μ and À on UD Dutch with 100 training samples. Figure 2 implies that moderate smoothing is beneficial to generalization. The ambiguity radius should be judiciously chosen because small À causes overfitting while large À leads to conservative models.
7 Discussion and Conclusion
We proposed a distributionally robust and consistent tree structured prediction method. We showed its equivalence to regularized surrogate loss minimization. We put forward a provably convergent algorithm based on efficient projection oracles for arborescence polytopes. Our proposed method enjoys Fisher consistency and robustness against noise in conditional distributions in terms of feature moments. Theoretical and empirical results validate its effectiveness.
We assume that an expressive feature mapping is given such that sufficiently good linear discriminant rule can be learned. The class sensitvee form Φ x. y) is general but consumes more memory than the decomposable form Φx (a) @ Øy (y). The ADMM projection algorithm is efficient theoretically with high per-iteration costs in practice. We expect this work to be a principled way of learning to predict tree-structured objects. Future directions include more efficient implementation and general structured prediction with DRO, Potential negative societal impacts of our work include using its prediction without verification guide human-centered design in policy-making.
Representation learning. Our method can be easily adapted to a representation learning framework with automatic differentiation. Although this may lead to non-convex problem without the theoreti- cal guarantees derived in this paper, it is highly desired in practice feature mappings are optimized well. We discuss a possible approach follows. Modern neural networks for supervised learning typically have linear layer in the end without activation. Assume the penultimate layer outputs ((x) for input æ, the last layer with parameters will typically output (bx)) := (x) E IR&, sometimes called logits, with & = n labels for all ares when parsing a sentence of n. tokens. Note that 0 in our formulation naturally serves as the parameters of this linear layer. Morcover, knowing (x) is sufficient for to solve the inner minimax problem in Eq. (2) to get // and Q
as In this way, our DRO method can be considered a loss layer without learnable parameters, which backpropagates the sub-derivative of the objective with respect (x(x):
Lady dxb(x)
1 00 B
Σ
(1) Pemp
where is the batch size. The sub-derivative of the regularization term with respect to @ should be added to the linear layer. Now are able to take advantage of automatic differentiation and focus on solving the inner adversarial problem given vb(x) and Since the computational bottleneck lies in computing (b()) and backward passes, the overhead of computing the adversarial loss may be dominated and not significant compared to the cross-entropy loss. We leave investigations on its effective applications to future work.
Acknowledgments and Disclosure of Funding
This material is based upon work supported by the National Science Foundation under Grant Nos. 1652530, 1910146, and 1934915.
$ *One explanation is that FW relies on first approximations while there are exponential number of facets in the arborescence polytope.
10

---

References
Yasemin Altun and Alex Smola. Unifying divergence minimization and statistical inference via convex duality. In International Conference Computational Learning Theory, pages 153. Springer, 2006.
Kaiser Asif, Wei Xing, Sima Behpour, and Brian D Ziebart. Adversarial cost-sensitive classification. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, pages 92-101, 2015.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463 482. 2002.
Mathieu Blondel. Structured prediction with projection oracles. Advances in Neural Information Processing Systems, 32: 12:12145- 2019.
Mathieu Blondel, André FT Martins, and Vlad Niculae. Learning with Fenchel-Young losses. J. Mach. Learn. Res., 21(35):1-69, 2020.
Stephen Boyd, Neal Parikh, and Eric Chu. Distributed optimization and statistical learning via the alternating direction method of multipliers. Now Publishers Inc, 2011.
Joseph Bradley and Carlos Guestrin. Learning tree conditional random fields. In Proceedings of the 27th International Conference on International Conference on Machine Learning, pages 127-134, 2010.
Stephen Brooks. Markov chain Monte Carlo method and its application. Journal of the Royal Statistical Society: Series D (the Statistician), 47(1):69-100) 1998.
Danqi Chen and Christopher Mamning. A fast and accurate dependency parser using neural networks. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pages 740-750, 2014.
C.K. Chow and Cong Liu, Approximating discrete probability distributions with dependence trees.
IEEE transactions Information Theory, (433):42-4663 1968.
Carlo Ciliberto, Lorenzo Rosasco, and Alessandro Rudi. A consistent regularization approach for structured prediction. Advances in neural information processing systems, 29:4412 4420, 2016.
Carlo Ciliberto, Francis Bach, and Alessandro Rudi. Localized structured prediction. Advances in Neural Information Processing Systems, 32, 2019.
Laurent Condat. Fast projection onto the simplex and the L_ ball. Mathematical Programming, 158 (1-2):575, 2016.
Alexis Conneau, Kartikay Khandelwal, Naman Goyal, Vishrav Chaudhary, Guillaume Wenzek, Francisco Guzmán, Edouard Grave, Myle Ott, Luke Zettlemoyer, and Veselin Stoyanov. Un- supervised cross-lingual representation learning at scale. CoRR, abs/1911.02116,, 2019. URL
www./oog////o/oaooooooooooe /911 02116.
Yiming Cui, Wanxiang Che, Ting Liu, Bing Qin, Shijin Wang, and Guoping Hu. Revisiting pre-trained models for Chinese natural language processing. In Proceedings of the 2020 Conference on Empir- ical Methods in Natural Langnage Processing: Findings, pages 657-668, Online, November 2020. Association for Computational Linguistics. URL https: : //www/ aclweb. org/ httpaaalghlll/2222222
findings emnlp.5nm.mm 58.
Marie-Catherine De Marneffe and Christopher Manning. The Stanford typed dependencies representation. In Coling 2008: proceedings of the workshop cross-framework and cross- domain parser evaluation, pages 1-8,2000 2008
Erick Delage and Yinyu Ye. Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operations research, 58(3):595-612, 2010.
Wei Deng and Wotao Yin. On the global and linear convergence of the generalized alternating direction method of multipliers. Journal of Scientific Computing, 66(3):889-916 2016.

---

Timothy Dozat and Christopher D. Manning. Deep biaffine attention for neural dependency parsing, In Sth International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Truck Proceedings. OpenReview.net, 2017. URI. htttp:://ppenreiieee pet//forumm?d-HHessPP5
John Duchi and Hongseok Namkoong. Variance-based regularization with convex objectives. The Journal of Machine Learning Research, 20(1):2450 2504, 2019.
Chris Dyer, Miguel Ballesteros, Wang Ling, Austin Matthews, and Noah A Smith. Transition-bas dependency parsing with stack long short-term memory. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume I: Long Papers), pages 334-343,77 2015.
Farzan Farnia and David Tse. A minimax approach to supervised learning. Advances in Neural Information Processing Systems, 29:4240-4248, 2016.
Rizal Fathony, Sima Behpour, Xinhua Zhang, and Brian Ziebart. Efficient and consistent adversarial bipartite matching. In International Conference on Machine Learning, pages 1457-1466. PMLR, 8a.
Rizal Fathony, Ashkan Rezaei, Mohammad Ali Bashiri, Xinhua Zhang, and Brian Ziebart. Distri- butionally robust graphical models. In Advances in Neural Information Processing Systems, pages 8354-8365, 2018b.
Marguerite Frank, Philip Wolfe, et al. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2):95-110, 1956.
Mirjam Friesen. Extended formulations for higher order polytopes in combinatorial optimization. PhD thesis, Otto von Guericke University Magdeburg, 2019.
Harold Gabow, Zvi Galil, Thomas Spencer, and Robert Tarjan. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica, 6(2):109-122, 1986.
Varun Ganapathi, David Vickrey, John Duchi, and Daphne Koller. Constrained approximate maximum entropy learning of Markov random fields. In Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence, pages 196-203, 2008
Kevin Gimpel and Noah A Smith. Softmax Softmax-margin crfs: Training log-linear models with cost functions. Human Language Technologies: The 2010 Anmual Conference of the North American Chapter of the Association for Computational Linguistics, pages 733-736, 2010.
Matthew R Gormley, Mark Dredze, and Jason Eisner. Approximation-aware dependency parsing by belief propagation. Transactions of the Association for Computational Linguistics, 3:489-501, 2015.
Peter D Grünwald and A Philip Dawid. Game theory, maximum entropy, minimum discrepancy and robust Bayesian decision theory. the Annals of Statistics, 3274):1367-1433, 2004.
William W Hager and Hongchao Zhang. Convergence rates for inexact admm applied separable convex optimization. Computational Optimization and Applications, 77(3):729-754 2020.
Grani Hanasusanto, Vladimir Roitch, Daniel Kuhn, and Wolfram Wiesemann. distributionally ro-
bust perspective uncertainty quantification and chance constrained programming, Mathematical Programming, 151(1):35-62. 2015.
Martin Jaggi. Revisiting Frank-Wolfe Wolfe: Projection-free sparse convex optimization. In International Conference Machine Learning, pages 427-435 PMLR, 2013.
Eliyahu Kiperwasser and Yoav Goldberg. Simple and accurate dependency parsing using bidirectional Istm feature representations. Transactions of the Association for Computational Linguistics, 4: 313-327, 2016.
Gustav Kirchhoff. Ueber die auflösung der gleichungen, auf welche man bei der untersuchung der linearen vertheilung galvanischer ströme geführt wird. Annalen der Physik, 14811))497-508. 1847.
12

---

Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT Press. 2009.
Terry Koo, Amir Globerson, Xavier Carreras Pérez, and Michael Collins. Structured prediction models via the matrix-tree theorem. In Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNIP-CONLL), pages 141-150, 2007.
Daniel Levy, Yair Carmon, John Duchi, and Aaron Sidford. Large-scale methods for distributionally robust optimization. Advances in Neural Information Processing Systems, 33:8847-8866 2020.
Zhifei Li and Jason Eisner. First-and second-order expectation semirings with applications to minimum-risk training on translation forests. In Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pages 40-51, 2009.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized BERT pretraining approach. CoRR, abs/1907.1 1692, 2019. URL pattt://arxis: wwwpvvv....g//////eaeeee axggabbs/907. htt.//9077..1999 11692.
Yufeng Liu. Fisher consistency of multicategory support vector machines. In Artificial Intelligence and Statistics, pages 291- PMLR, 2007.
Xuezhe Ma and Eduard Hovy. Neural probabilistic model for non-projective MST parsing, In Proceedings of the Eighth International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 59-69, 2017.
Mitchell Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. Building large annotated corpus of English: The Penn Treebank. 1993.
R Kipp Martin, Using separation algorithms to generate mixed integer model reformulations. Operations Research Letters, 10(3): 19-88119-128, 1991.
André Filipe Torres Martins. The geometry of constrained structured prediction: applications to inference and learning of natural language syntax. PhD thesis, Carnegie Mellon University, 2012.
André FT Martins, Noah A Smith, and Eric Xing. Concise integer linear programming formulations for dependency parsing. In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, pages 342-350, 2009.
André FT Martins, Noah A Smith, Eric Xing, Pedro Aguiar, and Mario Figueiredo. Turbo parsers: Dependency parsing by approximate variational inference. In Proceedings of the 2010 Conference on Empirical Methods Natural Language Processing, pages 34 44, 2010.
André FT Martins, Mário AT Figueiredo, Pedro MQ Aguiar, Noah A Smith, and Eric P Xing. Ad3: Alternting directions dual decomposition for map inference in graphical models. The Journal of Machine Learning Research, 16(1 (6(1):495-545 2015.
Ryan McDonald and Fernando Pereira. Online learning of approximate dependency parsing al- gorithms. In 11th Conference of the European Chapter of the Association for Computational Linguistics, 2006.
Ryan McDonald and Giorgio Satta. On the complexity of non- non-projective data-driven dependency parsing. In Proceedings of the Tenth International Conference on Parsing Technologies, pages 121-132, 2007.
Ryan McDonald, Fernando Percira, Kiril Ribarov, and Jan Hajic. Non-projective dependency parsing using spanning tree algorithms. In Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, pages 523-530, 2005.
H Brendan McMahan, Geoffrey J Gordon, and Avrim Blum. Planning in the presence of cost functions controlled by an adversary. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pages 536-543, 2003.
13

---

Arthur Mensch and Mathieu Blondel. Differentiable dynamic programming for structured prediction and attention. In International Conference on Machine Learning. pages 3462-3471. PMLR, 2018.
Ofer Meshi, Elad Eban, Gal Elidan, and Amir Globerson. Learning max max-margin tree predictors. In Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence, pages 411-420, 2013.
Tsvetomila Mihaylova, Vlad Niculae, and André FT Martins. Understanding the mechanics of spigot: Surrogate gradients for latent structure learning. In Proceedings of the 2020 Conference on Empirical Methods Natural Language Processing (EMNLP), pages 2186-2203 2020.
Kevin Murphy, Yair Weiss, and Michael I Jordan. Loopy belief propagation for approximate inference: an empirical study. In Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, pages 467-475, 1999.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
Joakim Nivre, Marie-Catherine De Marneffe, Filip Ginter, Yoav Goldberg, Jan Hajic, Christopher D Manning, Ryan McDonald, Slav Petrov, Sampo Pyysalo, Natalia Silveira, et al. Universal de- pendencies vl: A multilingual treebank collection. In Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC' 16), pages 1659-1666, 2016.
Alex Nowak- Vila, Francis Bach, and Alessandro Rudi. A general theory for structured prediction with smooth convex surrogates. arXiv preprint 1rXiv
2019.
Alex Nowak- Vila, Francis Bach, and Alessandro Rudi. Consistent structured prediction with max-min margin Markov networks. In Proceedings of the International Conference on Machine Learning (ICML), 2020.
Alex Nowak- Vila, Alessandro Rudi, and Francis Bach. Max-margin is dead, long live max-margin! arXiv preprint arXiv:2 1nt::2105.55000 /5069, 2021.
Franz Josef Och. Minimum error rate training statistical machine translation. Proceedings of the 41st annual meeting of the Association for Computational Linguisticx, pages 160-167, 2003.
Hao Peng, Sam Thomson, and Noah A Smith. Backpropagating through structured argmax using spigot. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1863-1873, 2018.
Toana Popescu. A semidefinite programming approach to optimal-moment bounds for convex classes of distributions. Mathematics of Operations Research, 30(3):632-657, 2005.
Hamed Rahimian and Sanjay Mehrotra. Distributionally robust optimization: A review. arXiv
preprint arXiv:/908.085 2019.
Harish G Ramaswamy, Shivani Agarwal, and Ambuj Tewari. Convex calibrated surrogates for low- rank loss matrices with applications to subset ranking losses. Advances in Neural Information Processing Systems, pages 1475-1483, 2013.
Mark Schmidt, Ewout Berg, Michael Friedlander, and Kevin Murphy. Optimizing costly functions with simple constraints: A limited-memory projected quasi-newton algorithm. In Artificial Intelligence and Statistics, pages 456-463. PMLR, 2009.
Soroosh Shafieezadeh-Abadehh Daniel Kuhn, and Peyman Mohajerin Esfahani. Regularization via mass transportation. Journal of Machine Learning Research, 20(103):1-68, 2019.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014.
Chao Shang, Xiaolin Huang, and Fengqi You. Data-driven robust optimization based kernel learning. Computers Chemical Engineering, 106:464-479, 2017.
David Smith and Jason Fisner. Minimum risk annealing for training log-linear models. In Proceedings of the COLING/ACL 2006 Main Conference Poster Sessions, pages 787-794, 2006.
14

---

David A Smith and Noah A Smith. Probabilistic models of nonprojective dependency trees. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNN.P-CONL.I) pages 132-140, 2007.
Matthew Staib and Stefanie Jegelka. Distributionally robust optimization and generalization kernel methods. Advances in Neural Information Processing Systems, 32:9114,332214444.. 32:9134-9144 2019.
Miloš Stanojević and Shay Cohen. root of problem: Optimizing single-root dependency parsing. In Proceedings of the 2021 Conference Empirical Methods in Natural Language Processing, pages 10540-10557, 2021.
Veselin Stoyanov and Jason Eisner. Minimum-risk risk training of approximate CRF-based NLP systems. In Proceedings of the 2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 120-130, 2012.
Ben Taskar, Carlos Guestrin, and Daphne Koller. Max-margin Markov networks. Advances in Neural Information Processing Systems, 16, 2003.
Ben Taskar, Dan Klein, Mike Collins, Daphne Koller, and Christopher D Manning. Max-margin parsing. In Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing, pages 1-8, 2004.
Flemming Topsøe. information-theoretie optimization techniques. Kybernetika, 15(1):8-27, 1979.
Kristina Toutanova, Dan Klein, Christopher D Manning, and Yoram Singer. Feature-rich part-of- speech tagging with a cyclic dependency network. In Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics, pages 252 259, 2003.
Ioannis Tsochantaridis, Thorsten Joachims, Thomas Hofmann, Yasemin Altun, and Yoram Singer. Large margin methods for structured and interdependent output variables. Journal of Machine Learning Research, 6(9), 2005.
John Von Neumann and Oskar Morgenstern. Theory of games and economic behavior, 2nd rev. 1947.
Wenhui Wang and Baobao Chang. Graph-based dependency parsing with bidirectional LSTM. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2306 2315, 2016.
William. Tutte. graph theory. Encyclopedia of Mathematics and its Applications, 21, 1984.
Richard T Wong. Integer programming formulations of the traveling salesman problem. In Proceed- ings of the IEEE international Conference of Circuits and Computers, pages 152- IEEE Press Piscataway NJ, 1980.
Zheng Xu, Gavin Taylor, Hao Li, Mário AT Figueiredo, Xiaoming Yuan, and Tom Goldstein. Adaptive consensus ADMM for distributed optimization. In International Conference on Machine Learning, pages 3841-3850 PMLR, 2017.
Nianwen Xue, Fu-Dong Chiou, and Martha Palmer. Building large-scale annotated Chinese corpus. In COLING 2002: The 19th International Conference on Computational Linguistics, 2002.
Hui Zhang and Lizhi Cheng. Restricted strong convexity and its applications convergence analysis of gradient-typp methods in convex optimization. Optimization Letters, 955:961-977, 2015.
Xingxing Zhang, Jianpeng Cheng, and Mirella Lapata. Dependency parsing as head selection. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Pupers, pages
2017.
Xinhua Zhang, Ankan Saha, and SVN Vishwanathan. Regularized risk minimization by Nesterov's accelerated gradient methods: Algorithmic extensions and empirical studies. arXiv preprint arXiv:1011.042,, 2010.
15

---

Yu Zhang, Zhenghua Li, and Min Zhang. Efficient second-order TreeCRF for neural dependency pars- ing. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 3295-3305, 2020.
Yuan Zhang. Tao Lei, Regina Barzilay, and Tommi Jaakkola. Greed is good if randomized: New inference for dependency parsing. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1013-1024, 2014.
Ran Zmigrod, Tim Vieira, and Ryan Cotterell. Please mind the root: Decoding arborescences for dependency parsing. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 18009-8891, 2020.
Ran Zmigrod, Tim Vieira, and Ryan Cotterell. Efficient computation of expectations under spanning tree distributions. Transactions of the Association for Computational Linguistics, 9:675-690, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No]
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you' 're
using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
16


Reviews:
[{"review_id": "zOgux94-tRO", "reviewer": "Reviewer_sgAv", "summary": "This paper attempts to develop a better learning algorithm for structured prediction tasks (in particular trees), the most direct application being supervised dependency parsing. Dependency parsing has a long line of work most of which are trained with maximum likelihood, margin-based, or ERM-based objectives. The authors point out that such training objectives are not aligned with the evaluation objective. Further, such methods have non-convex objectives due to which they lose convergence and generalization guarantees.\n \nTo mitigate that, the paper proposes a training approach based on the Distributionally Robust Optimization framework (DRO). In very simple terms, in DRO, the learning algorithm is unaware of the underlying distribution apart from some knowledge over the support and the goal is to minimize the worst-case risk over some uncertainty set. They show the equivalence between the DRO-based objective to a convex surrogate loss function and derive uniform convergence based generalization bounds. They develop efficient training algorithms and show convergence guarantees.\n \nThey evaluate their method on three dependency parsing datasets (PTB, UD, and CTB) with BiAF as the baseline. In particular, they focus on low training data settings (10 - 1000 training examples). They use their method to predict the unlabelled dependency tree and use a different classifier to predict arc labels. The model uses representation learned by Roberta and the final linear predictor is learned by their approach (or BiAF as baseline). Their approach achieves consistent gains over BiAF on the three datasets.\n ", "questions": "(Q1) **Low resources languages.** Wouldn't it be more useful to evaluate/test the models on dependency parsing datasets for low resource languages? I understand that the training data here is restricted to 1000 examples but the pretrained model representations of high-resource languages seem to be good enough for BiAF to achieve over 85% with 10 examples. Wouldn't it be more useful to experiment on datasets that are not saturated (mainly low resource ones)?\n \n(Q2) **Representation learning.** Is it feasible to design an algorithm with the proposed objective that also updates the feature representation (using some different optimization method)? In that, I guess convergence guarantees and generalization bounds may not hold but may lead to better performance?\n \n(Q3) **LAS vs UAS.** Isn't the UAS (unlabelled) metric more relevant for model comparison as opposed to LAS since the labels are anyway not predicted by the proposed method? I thought it would make more sense to have that result in the main paper compared to having it in the appendix. Also, it seems surprising that LAS with only 10 training examples is so high. Do 10 examples even have enough variations with all labeled arcs? It seems a bit odd.\n \n \nTypos:\nLine 301: objetive -> objective", "limitations": "Limitations are discussed in the final section.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": " \n \n### Strengths\n \n \n(S1) **Interesting Method and theoretical results.** The adaption of the DRO framework for tree-structured prediction is quite interesting. The issues with prior approaches are well described and show a natural fit for the proposed approach. Provable methods for structured prediction are relatively scarce due to various reasons and this paper seems to take a step in that direction.\n \n \n(S2) **Efficiency and convergence.** The designed algorithms seem to be reasonably efficient and fast convergence makes it appealing from a practical standpoint.\n \n \n(S3) **Writing.** The paper is well written, the motivations are clearly outlined and the arguments are well-presented.\n \n \n### Weaknesses\n \n \n(W1) **Incremental improvement.** Compared to the baseline (BiAF), the proposed method achieves very small improvements across all tasks even in the low training data setting.\n \n(W2) **Reliance on prior representations.** Although representation learning is not the main goal of the paper, the disconnect with the representation learning model puts it in a position of disadvantage. In experiments, they first train the baseline model (Roberta+BiAF) on the training data and then use its representation (assuming - prefinal layer) as features for the proposed model. Compared to end-to-end models, the proposed method could perform worse due to the lack of proper features.\n \n\n**General Comment.** Overall, I think it is an interesting paper. Despite weak practical gains, the work could be helpful to other researchers in the community working on such structured prediction problems.\n ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "jRPANm19fSA", "reviewer": "Reviewer_ULtE", "summary": "This work proposes a moment-based distributional robust optimization approach for tree structured prediction, which is further applied to dependency parsing. The authors propose the instantiation of the distributional robustness objective to the tree structured prediction setting in the parameterization of marginal probabilities. The authors also discuss the risk bound for the proposed methods and methods for projection to the arborescence polytopes. Experiments on three datasets demonstrate the effectiveness of the proposed method in the few-shot setting.", "questions": "See above discussions", "limitations": "See above discussions", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n- I like the rigorous mathematical discussions on this work. The authors give thorough discussions about the background and clear notes on the related work of multiple threads, and how this work is built on top on the existing methods.\n- The idea of using distributionally robust optimization for tree structured prediction is indeed significant and would add valid contribution of the field\n- Experiments show its effectiveness especially on low-resource settings\n\nWeakness \n\n- Ideally, distributionally robust optimization should be validated on datasets with distributional shifts (e.g., from news domain to dialog domain). But the evaluation is more on a in-distribution few-shot setting (rather than a distributional shift setting). I would expect the authors to elaborate this a little bit in the discussion period.\n- The implementation is on CPUs with C and Python. It remains unclear how this method can be implemented on GPU-accelerated Automatic Differentiation libraries like PyTorch. Such limitation could severely restrict the applicability of the proposed method\n- The gradients w.r.t. the projection step to the Polytope (section 4 and Figure 1) seems to be not well-defined and have previously been under discussions[1, 2]. It is not very clear in this paper’s setting how such problem may (or may not) become an issue in terms of optimization\n\n[1] Peng et. al. ACL 2018. Backpropagating through Structured Argmax using a SPIGOT\n\n[2] Mihaylova et. al. 2020. Understanding the Mechanics of SPIGOT: Surrogate Gradients for Latent Structure Learning", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "EIvt203jlkg", "reviewer": "Reviewer_8tu8", "summary": "The authors propose a distributionally robust optimization (DRO) framework for structured prediction over trees, where the ambiguity set is given by a maximum feature moment difference to the empirical distribution. They derive an unconstrained dual problem and establish a worst-case excess risk bound for the optimal parameter. They discuss strategies for efficient (approximate) computation of this parameter, with particular emphasis on projection onto the arborescence polytope. The method is illustrated on three dependency parsing tasks, where it performs competitively with a neural dependency parser, with consistent outperformance in low-data settings.", "questions": "- In Section 6, the authors argue that training BiAF on an ERM objective means that the pretrained features may be suboptimal for the DRO objective. But doesn't this also suggest that BiAF will suffer from test evaluation in terms of attachment score (i.e. Hamming loss), while this is being optimized directly in the DRO method?\n\n- In Table 1 the authors compare their method to BiAF in terms of compute time per gradient descent step. How do the total training times compare?", "limitations": "Some tradeoffs and assumptions are discussed at the end of Section 7. The authors acknowledge that computation time may be a bottleneck and address tradeoffs in computation between the Marginal and Stochastic / Game implementations; they point out (fairly) that for the increase in computational cost versus the BiAF baseline they are able to offer a guarantee of distributional robustness.\n\n", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths.\n\n- This is a very well-written paper. The writing is direct, precise, and information-dense. The exposition makes extensive reference to relevant work, providing rich context and highlighting the gaps that the authors aim to fill.\n\n- The contribution appears novel and and is thoroughly developed in its theoretical, computational, and empirical aspects. There are significant technical contributions in terms of a novel DRO problem formulation and its analysis, in terms of the statistical properties of the associated estimator, and in terms of considerations for its efficient computation. The experiments compare the method to a strong baseline, quantify uncertainty in the result, and consider both accuracy metrics and computational costs.\n\nWeaknesses.\n\n- Except on the UD dataset, the empirical results are somewhat modest outside of two very-low-data settings ($m=10$ and $m=50$).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept