Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper provides generalization bounds for structured prediction learning with a more general setting where each input is associated with its own scoring function. The scoring functions are represented using factor graphs. The authors provide three main results and improve the dependency of the generalization error either on the number of samples or factor and label size. Three classes are considered smooth loss, Lipschitz loss and functions with controlled capacity (stated in terms of their covering number).
main_review: The main contribution of the paper is a unified generalization bound that has simultaneously better dependency on the cardinality of possible labels and the sample size n. 

The results are all solid, and the proofs seem to be fine with when I checked them in passing. The proofs are all based on Rademacher complexity analysis and local Rademacher complexity analysis and bounding them using covering numbers by Dudley’s inequality and generic chaining. 

Overall, the results of the paper are interesting, but the writing and presentation can be significantly improved. Besides, I am interested in author’s answer to my comment about the reference [6].

- The paper is hard to read. It has many typos and unpolished statements. For the main paper, the authors could dispense with many terms and keep it to a minimum for better readability.

- The paper [6] provides faster that 1/n convergence, but this is not discussed in the main paper.  The idea of factorization is also present there. It is important to compare this reference with the results of the paper, since it potentially provides better sample complexity.

- The dependency on the sample size in the current analysis is limited to 1/n or 1/\sqrt{n}. Is this an artifact of using Rademacher complexity analysis? I wonder if Rademacher complexity analysis permits getting better convergence than this. 

limitations_and_societal_impact: None
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors consider the problem of bounding the error between the true risk and the empirical risk for structured prediction with a large number of possible labels. By adding fairly weak assumptions that are satisfied for common cases, they improve the dependence on the number of labels $d$ from $O(\sqrt{d})$ to $O(\log d)$ and/or the rate of convergence from $1/\sqrt{n}$ to $1/n$. They then analyze the generalization risk when there may be an infinite number of labels but the family of scoring functions has small complexity as defined by covering number.
main_review: Overall I found the paper to be fairly clear and theoretically interesting. The authors improve the best known generalization results for important cases of structured learning. They show faster convergence of the theoretical loss functions and better dependence on the number of labels. Additionally, the proofs of these results seem theoretically interesting.

The paper can do a better job connecting to practice by proving examples where the framework holds and when there is a large number of labels. Currently the paper is purely theoretical and abstract. The authors can improve the paper by
(1) describing practical situations where there is a large number (or even infinite) labels.
(2) describe practical or theoretically relevant situations where the covering number assumptions holds. 

The section with covering numbers is a bit unclear. An example problem where the covering number assumption holds can improve the clarity of the assumption. Additionally a practical problem where the assumption holds and/or there are an infinite number of labels can improve the impact of these results.

Overall I lean towards accept due to the theoretical results, however the paper can be improved by providing more insight into how the results (specifically the improvement in convergence for large/infinite label situations and the results that assume reasonable covering number) can improve the impact of the paper.
limitations_and_societal_impact: No issues.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: Authors study generalization in the context of structured prediction based on factor graphs. Their goal is to improve the rates of existing generalization bounds, among their contributions we have:

1. Under Lipschitz continuity, an improvement from square root to logarithmic dependence on the size of the output space.
2. Under a smoothness condition, a faster convergence rate of $O(1/n)$, where $n$ is the sample size.
3. Under covering number assumptions, authors show a bound with no dependency on the output space size, simultaneously with faster convergence rates than $O(1/\sqrt{n})$.
main_review: Here I present my review along the axes from the NeurIPS reviewing guidelines:

**Originality**

- Are the tasks or methods new? 
  - The generalization bounds are new.

- Is the work a novel combination of well-known techniques?
  - Yes. The work applies ideas from concentration inequalities, Rademacher complexity, and covering numbers, to name a few.

- Is it clear how this work differs from previous contributions? 
  - Yes.

- Is related work adequately cited?
  - Mostly yes; however, there are some literature missing. For instance, upper bounds from London et al. (2016), in the context of stability, derive bounds that also depend on the size of each example.


**Quality** 

- Is the submission technically sound? 
  - I have not checked the proofs in detail but they seem sound.

- Are claims well supported (e.g., by theoretical analysis or experimental results)? 
  - No experiments are provided.

- Are the methods used appropriate? 
  - Yes, the theoretical tools used in the proofs are adequate for the analyses.

- Is this a complete piece of work or work in progress? 
  - Complete work.

- Are the authors careful and honest about evaluating both the strengths and weaknesses of their work?
  - I was not able to see a discussion on the limitations of their analysis.


**Clarity** 

- Is the submission clearly written? 
  - No. See below.

- Is it well organized? 
  - Yes. 

- Does it adequately inform the reader? 
  - N/A.


**Significance** 

- Are the results important? 
  - If proofs are correct, yes. These results are of interest to the learning theory community.

- Are others (researchers or practitioners) likely to use the ideas or build on them? 
  - Perhaps. Theorists might be interested on improving the bounds or provide milder assumptions.

- Does the submission address a difficult task in a better way than previous work? 
  - N/A. No algorithm is presented.

- Does it advance the state of the art in a demonstrable way? 
  - The results presented improve the rates existing upper bounds, although I am not completely sure if the bounds are fully comparable to existing ones given the set of assumptions.

- Does it provide unique data, unique conclusions about existing data, or a unique theoretical or experimental approach?
  - N/A.

# Questions / Comments

I have mixed feelings about this manuscript. I believe the results (if correct) are worthy of publication. However, there are *a lot* of mistakes in the writing and, thus, the paper requires an extensive editing before publication. For that reason, the current state of the manuscript does not meet the bar to be published at NeurIPS.

I will comment on some issues I found in the *introduction* as it is just unrealistic to list all existing mistakes.

1. In the first sentence: CV, NLP, CB are not problems but *fields*.
2. L19: compute vision -> computer vision
3. L19: "..., protein..." -> "..., and protein..."
4. L21: "to above tasks" -> "to the above tasks"
5. L22: "that the natural" -> "that a natural". Otherwise, what is that "natural loss"?
6. L28: "Compared with" -> "Compared to". The point is to contrast, right?
7. L31: "bound studying" is confusing. 
8. L33: "consider the specific algorithm and the simple" -> replace both "the" with "an" and "a", respectively.
9. L34: "more work considers". Seems odd, "other works consider"?
10. L35: "general loss." -> "general losses" or "a general loss."
11. L40: "general loss based" -> "general losses based"
12. The sentence from L41 to L43 is very disconnected. There is no a connection word to the previous sentences, and also it has an error at L41 "there has".
13. L44: using "these" is also odd. Better to use "the works above" or "the aforementioned works"
14. The use of [I.], [II.], [III.] looks very odd as well. There is an "enumerate" environment in Latex for that, roman listing is available as well.
15. L48: "..., [40] of" -> "..., and [40] of"
16. L50: "there raises a question" is also incorrect.
17. L51: "achieves" -> "achieve"
18. L52: Can the number of labels be infinite? It is typically exponential on the input size. What is an example of infinite number of *discrete* labels?
19. L54: "can provide the explicit" sounds odd.
20. L56: "shed" -> "sheds" as it refers to the approach (singular).
21. L63: "more difficult and complex", what is the difference between difficult and complex?
22. L64: "problem" -> "problems"
23. L64: "wonder to know". I am not sure if that phrase even exists.

I have listed several potential errors *just* in the introduction. I cannot even mention the ones throughout the rest of the manuscript.

---
I thank the authors for their response. I am increasing my score to 5 as I believe the technical contributions are relevant. However, the manuscript requires a serious revision on the writing, thus, I cannot increase my score further.
limitations_and_societal_impact: No.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper investigates the generalization performance of structured prediction learning where the scoring function can be formulated via the notation of factor graphs. In three separate settings, the work derives state-of-the-art generalization bounds with fast convergence rates and weak dependency on the number of possible labels. 

main_review: 
**Originality**: 

- The paper derives state-of-the-art generalization bounds with different mild conditions imposed on the loss and the capacity of the hypothesis space. The results are general and seem to be applicable to various learning contexts. 

- On the other hand, it's hard to pinpoint which technical contributions of the work are instrumental to the derivation of the results:
   - The most novel technique seems to appear in the proof of Proposition 1 that bounds the covering number of the function class $\mathcal{F}_{\rho}$, where the nonlinearity of the margin are bypassed by an intermediate linear function class. However, that is also a problem for multiclass learning, for which comparable bounds have been obtained. Is this a new technique that pertains to structured prediction?
   - For the rest of the proof, aspects that are unique to structured prediction, such as factor graph, rarely appears. It is worth highlighting such contributions in the discussions (more on this below).


**Quality and Clarity**: 

- In general, the paper is well-written and well structured. The work seems to be built upon established literature and the review of related works is informative. The ideas are presented intuitively and the proofs are rigorous.

- While the results of the work are very impressive, the paper would be greatly strengthened by more discussions on the relevant context: 
   - What are the main difficulties in obtaining those bounds and what analytical tools were constructed to address the issues?
   - What are the distinct characterization that set structured prediction apart from other contexts with similar bounds (such as multiclass classification) that requires significant technical adjustments ?

- The paragraph "Margin and loss function class" contains some typos and misuse of notation: "surogate"; $\ell_\rho(f, x, y)$ vs $\ell_p(x, y, f)$; $\rho_{f(x, y)}$ vs $\rho_{f}(x, y)$; the mathematical expression after the introduction of the surrogate loss (follow "that is") is incomprehensible 


**Significance**:

- The problem studied in this paper is important, and the derived results advance the state of the art in a demonstrable way. 
- Regardless of technical novelties, the paper lays out a complete framework that others can rely on for future works in this direction. 

limitations_and_societal_impact: n/a
review_title: null

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

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

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

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

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

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

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