Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This article proposes a weak supervision technique for structured prediction, with labels taking values in finite metric spaces and constant-curvature Riemannian manifolds, and assuming an exponential-family-based probabilistic label model for the weak labels parametrized by the accuracy potentials.

For finite metric spaces, the authors incorporate structure into the label model by first computing pseudo-Euclidean embeddings of the labels, making use of native distance in the label space.  Similar to [1], a tensor decomposition algorithm is used on the pseudo-embeddings to obtain estimators for the mean parameters of the label model.  Pseudo-labels are created for each data point by sampling from conditional distribution of the latent truth conditional on the output of labeling functions.  The authors then proceed in a similar way to [2], where the label space distance is is a weighted (according to the estimated conditional distribution) aggregation of distances to the weak labels.  The authors derived an upper bound for the parameter recovery error for both high and low noise regimes.  An upper bound for generalization error is also derived and shown to have an extra (compared to the bound in [2]) additive factor which is dependent on the support size of the label space and embedding dimension size.

For constant-curvature Riemannian manifolds, a generalization of the triplet method (similar to [3,4]) which leverages the law of cosines is proposed, which allows for a closed form estimator for the distance between weak label and latent truth.  This estimator is shown to be consistent. The authors then proceed in a similar to way to [2], where the label space distance is a minimized convex combination of distances to the weak labels.

The paper focuses on the theoretical aspects of the algorithm, without any experimentation.

[1] Tensor decompositions for learning latent variable models. Anandkumar et al.

[2] A consistent regularization approach for structured prediction. Ciliberto et al.

[3] Fast and Three-rious: Speeding Up Weak Supervision with Triplet Methods. Fu, Chen et al.

[4] Evaluating the Crowd with Confidence. Joglekar et al.


strengths_and_weaknesses: Strengths:

1) Adapting of the guaranteed general approach to structured prediction in [1] to the case of weak supervision is a natural goal.  At a high level, the general approach is simple to understand and does not change very much -- we only need to swap the label space distance term to a weighted combination of the distances to the weak labels. 
2) The design choice of using pseudo-Euclidean embeddings seems to be very appropriate, to accomodate general dissimilarity matrix from general finite metric structured spaces.
3) Parameter recovery error and generation error bounds seem to be rigorously derived.  The desciption of practical consequences, for example, on Line 186 ("This leads to tradeoff in selecting the appropriate embedding dimension") and on Lines 245-246 ("Thus we see that we only pay an extra additive factor..."), are highly appreciated.  

Weaknesses:

1) The choice of noise model (Equation 3) seems to exclude correlation potentials, which may limit the scope of practicality.
2) It is not clear how the bounds presented compare to bounds in prior works for binary/multiclass labels.
3) It is not clear why tensor decomposition from [4] is chosen for parameter estimation.
4) Some presentation aspects can be improved:
- Line 36, it is implied that all WS methods for binary classification yields models with generalization guarantees, but this is not the case. See [2] for other weak supervision methods.
- Line 106, there should a space in "small.In"
- Line 109, should there be $\theta_a$ there? The sentence seems awkward.
- Line 110, "and $\theta_a = \infty$, so that $\theta_a = y$ seems awkward.
- Line 143, it may not be clear for readers who are not familiar with pseudo-Euclidean embedding, why the pseudo-Euclidean embedding of the example is 3.  Moreover, I do not think there is enough citation on pseudo-Euclidean embedding and its computation in Algorithm 1.
- Line 145, it might be clear to write "embeddings of $\lambda_{a}, y$ respectively".
- In Equation 4, instead of a period, it should be a comma at the end of the line.
- Line 200, there seems to be something missing after "where $\tilde{z}_i$".
- Line 243, "as in the case of access toclean labels" needs to be fixed.
- Line 272, "Note that the finite metric-space case is insufficient: the support is infinite".  This sentence is hard to understand.
- Lines 325,326, "it is possible to do for..." is ungrammatical.
- Line 290, I find "C_0 reflects the pushforward of concentration between the distributions ..." dubious -- I have never seen "pushforward" used for "concentration" before.
- Appendix E, Definition 1. Is this missing "triangle inequality" and "need not be distinguishable"?
5. It would have been interesting for weak supervision practitioners to see some experiments to study the empirical performance, perhaps comparing against the approach proposed in [3].   

[1] A consistent regularization approach for structured prediction. Ciliberto et al.

[2] WRENCH: A Comprehensive Benchmark for Weak Supervision. Zhang et al.

[3] Universalizing weak supervision. Shin et al.

[4] Tensor decompositions for learning latent variable models. Anandkumar et al.

questions: 1. Why is tensor decomposition ([1]) chosen for parameter estimation? Would other approaches work?  Presumably you would want the method to have guarantees so that you can derive an analog of Theorem 1.

2. Can the authors please comment on/reconcile the differences between the $O(n^{-1/4})$ generalization error proposed to the $O(n^{-1/2})$ in [2]?

3. Can the multi-view mixture model handle correlations between the views?  That might be how the correlation potential can be handled in the probabilistic model.

[1] Tensor decompositions for learning latent variable models. Anandkumar et al.


[2] Fast and Three-rious: Speeding Up Weak Supervision with Triplet Methods. Fu, Chen et al.

limitations: Adequately addressed
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: Most prior work on weak supervision with theoretical guarantees has focused on the binary or multi-way classification settings. This paper provides theoretical guarantees for weak supervision in a broader range of label settings like finite metric spaces, for example, rankings (where the label for every data point is an ordering of {1,2,..., k} - if there are k categories, with the Kendall tau metric), and manifold-valued label spaces. In particular, for the case where the labels belong to a finite metric space, they provide an algorithm for pseudo-label construction using pseudo-Euclidean embeddings and tensor decompositions, which they claim are new to weak supervision, and for the case of labels in constant-curvature Riemannian manifolds, they provide an invariant which they then use for noise rate estimation of the labeling functions. Using the pseudo-labels formed by their procedures in down-stream models from prior work [CRR16, RCMR18], they provide generalization error bounds for both these cases.

CRR16 - Carlo Ciliberto, Lorenzo Rosasco, and Alessandro Rudi. A consistent regularization approach for structured prediction. In Advances in Neural Information Processing Systems 30 (NIPS 2016), volume 30, 2016.
RCMR18 - Alessandro Rudi, Carlo Ciliberto, GianMaria Marconi, and Lorenzo Rosasco. Manifold structured prediction. In Advances in Neural Information Processing Systems 32 (NeurIPS 2018), volume 32, 2018.
strengths_and_weaknesses: Originality: I am not an expert in this area so I am not entirely sure about other related work. From what I can read from the paper, it indeed does seem like there is not much prior work on weak supervision for structured prediction, which clearly is an interesting area. The only other paper which they say that has studied WS for structured prediction is a recent ICLR 2022 paper [SLV+22], which seems to lean more on the empirical side.

Quality: The submission is technically sound. All claims are well-supported with proofs.

Clarity: The submission is clearly written and well-organized.

Significance: Yes, the problems being studied are quite significant. Structured prediction settings like rankings are very well studied in the literature and they also seem to have a lot of practical applications so weak-supervision algorithms for them can have a good impact.

SLV+22 - Changho Shin, Winfred Li, Harit Vishwakarma, Nicholas Carl Roberts, and Frederic Sala. Universalizing weak supervision. In International Conference on Learning Representations, 2022.
questions: The authors claim that tensor decompositions are new to weak-supervision but [SLV+22] mentions “We require an estimate of the prior p on the label y; there are techniques do so (Anandkumar et al., 2014; Ratner et al., 2019); we tacitly assume we have access to it.” on page 5. I have not read [SLV+22] very carefully but it seems like they were the first to notice that tensor decomposition based approaches can be used for weak supervision.

limitations: This is primarily a theoretical paper and so the authors have chosen N/A for checklist item 3 [Did you discuss any potential negative societal impacts of your work].
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 considers the problem of aggregating noisy labels for learning with structured label set. It proposes methods of first estimate the weights of confidences of each label source, and then learn the hypothesis. Authors provides generalization error bounds for labels sets with different cardinalities. However, no empirical evaluations are presented.
strengths_and_weaknesses: Strengths
- The problem setting is an important and general one, and the proposal is original.
- The writting is overall fine.

Weakness
- The title is too general. Weak supervision can also mean indirect information about labels. It would be better to emphasis the aggregation aspect of the paper.
- Motivation is overal not presented clearly. What exactly the proposed method is neccessary for dealing with structured label spaces remains unclear.
- related work is not enough. Aggregating multiple noisy labels and estimating label source confidence has been explored in fields such as crowdsourcing, at least to an empirical evaluation extent.
- Without neccessary empirical evaluation results even using synthetic data, it is difficult to judge the overall significance of the proposal.
- In Page 6, Line 197, Assumption on knowing the prior should be more emphasized. This is a strong assumption as some weakly supversied learning methods heavily depend on it, such as Positive-Unlabeled Learning with Non-Negative Risk Estimator, Kiryo et al., NeurIPS 2017.
questions: - For equation (3), why this model is selected? If it is just adapted from SLV+22, then why this model is selected in SLV+22? How is it favorable than other models, if any?
- For find the Pseudo-Euclidean embedding space, is it unique? If not, how its selection and how embedding dimension would affect downstream performance? It seems like authors critique on SLV+22 can be applied as it relies on the availablity of pseudo-euclidean embeddings but does not explain how to find these.
- What are the motivations for introducing multi-view mixtures in Seciton 3.2?
- In Page 5, Line 160, what are the various moments of the outputs of LFs?
- What are intuitive reasons for the three assumptions in page 7?
- Maybe a typo in Algorithm1 Input, should be dots instead of comman in Labeling function outputs?
limitations: Authors properly addressed limitations.
review_title: null

Meta-review: metareview: The paper gives theoretical guarantees for weak supervision for more general problems than binary classification. The reviewers were all positive about this work and felt this paper introduces new techniques to this space that may be useful for other problems as well. 
confidence: Less certain
Decision: Accept