Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths.

- 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.

- 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.

Weaknesses.

- Except on the UD dataset, the empirical results are somewhat modest outside of two very-low-data settings ($m=10$ and $m=50$).
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?

- 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
 
To 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.
 
They 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.
 
strengths_and_weaknesses:  
 
### Strengths
 
 
(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.
 
 
(S2) **Efficiency and convergence.** The designed algorithms seem to be reasonably efficient and fast convergence makes it appealing from a practical standpoint.
 
 
(S3) **Writing.** The paper is well written, the motivations are clearly outlined and the arguments are well-presented.
 
 
### Weaknesses
 
 
(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.
 
(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.
 

**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.
 
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)?
 
(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?
 
(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.
 
 
Typos:
Line 301: objetive -> objective
limitations: Limitations are discussed in the final section.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths

- 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.
- The idea of using distributionally robust optimization for tree structured prediction is indeed significant and would add valid contribution of the field
- Experiments show its effectiveness especially on low-resource settings

Weakness 

- 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.
- 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
- 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

[1] Peng et. al. ACL 2018. Backpropagating through Structured Argmax using a SPIGOT

[2] Mihaylova et. al. 2020. Understanding the Mechanics of SPIGOT: Surrogate Gradients for Latent Structure Learning
questions: See above discussions
limitations: See above discussions
review_title: null

Meta-review: metareview: This paper presents theoretical results for structured prediction over trees and empirical results on three syntactic dependency parsing datasets. All reviewers agree that the paper is well written and novel. The empirical gains are not huge, but the comparisons are done in a thorough and fair way. All reviewers suggest acceptance (even though some reviewers have low confidence) and the meta reviewer agrees as well.
confidence: Certain
Decision: Accept