Estimating Fréchet bounds for validating programmatic weak supervision

1. One weakness is that this approach is fundamentally reliant on the quality of the label model. This is manifested in assumption 2.3, which states that the estimate of the conditional distribution of $Y | Z$ should approach the true conditional distribution. However, given biased and underperforming weak labelers, does this assumption actually hold? As such, are these truly valid bounds? They are violated in a few instances in Figure 1 (lower bound in second to the left in the bottom row, upper bound in second to left in the top row).

2. As highlighted by the authors in their Limitations section in the conclusion, this approach implicitly makes the same assumptions as the specified labelmodel, which can indeed be making assumptions about the conditional independence of the weak labelers (e.g., what is default in the Snorkel implementation).

3. I’m a bit confused as to what is the underlying message of Section 4.3. It seems to me that the proposed bounds perform poorly in the case with a few LLM generated weak labelers. I currently am understanding the “label set selection” approach to be picking weak labelers based on “accuracy”, except where accuracy is measured by disagreement with the estimated weak labels (i.e., label model outputs). As such, this would simply be pruning away weak labelers that disagree with the labelmodel, which seems somewhat undesirable.

4. There seems to be a lack of discussion about existing work on adversarial methods in PWS (namely [1] and subsequent followup work). I realize this existing work focuses on the classifier error rate, although the relaxed convex program approach seems similar.

[1] Arachie, Chidubem, and Bert Huang. "Adversarial label learning." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 33. No. 01. 2019.

1. The estimator in equation (2.4) heavily relies on the distribution P_{Y\mid Z} which is not observed. The paper suggested using a label model to approximate such distribution. This requires the label model to be “good”. However, in this case, we can just use it to evaluate classifiers directly without deriving the Frechet bound.

2. For most tasks, a small set of labeled data is available. In fact, snorkel also relies on a small dev set to tune the hyperparameters of the final predictor. One could also use these labels to provide a bound on the performance of a classifier. It would be interesting to compare a confidence interval from a small dev set and the Frechet bound.

The main weakness of the paper in my opinion is in the experiments, which the authors use to show that their bounds have practical usefulness in PWS. However, I think this can be better substantiated in several ways.

For starters the experiments would ideally be expanded to encompass a wider array of PWS settings, i.e.:

• Testing on multiple types of end models (beyond logistic regression) and label models (beyond just Snorkel)
• Testing on datasets beyond binary classification
• Measuring precision/recall on the unbalanced datasets such as Tennis and Census. On these tasks, F1 (and not accuracy) is the default metric in WRENCH.

But perhaps more importantly, I think the results would benefit from more directly showcasing the usefulness of the bounds as a way for hyperparameter tuning/model selection. Personally, I think this is the more interesting use case of the bounds. In the current results, it seems that $L$ and $U$ are not always reliable for precisely estimating performance (i.e., they are often wide or fail to capture true test performance due to the assumption on the label model quality). However, I do think the bounds may still be practically useful in that they can help relatively rank different models. This is indeed something that the authors allude to in several places, such as when discussing how they can help pick the threshold on IMDb or select LFs on Youtube. However, I believe this claim should be tested more extensively, perhaps by defining explicit selection rules and comparing the effectiveness of these rules for selecting all hyperparameters (and for more complex WS methods).

Furthermore, I think some relevant baselines for evaluation/model selection here would be (a) using weak labels for the validation set; (b) using a small amount of clean labels. The latter is not a totally fair comparison, but would reflect an important practical question re: "how many labeled points does using these bounds actually save?" Even for the current results, it would be nice to compare the widths of the bounds to something like the 95% CIs one would obtain when using different amounts of labeled data.

(1) While I think that the paper is overall well-written, and it is easy to understand its contribution, I think that the presentation is lacking in some parts.

In my opinion, the paper provides no intuition behind the Frechet bounds and what they represent, and what information they are providing in the weak supervision setting.

In my interpretation, we assume to have access to (or an estimate of) $P(Y|Z)$, $P(Y)$, and $P(X,Z)$. Let's say that as a function $g$, we use the accuracy $g(X,Y,Z)$ = indicator$( h(X) = Y)$. From the definition, Frechet bounds look at the "worst-case" and "best-case" joint distribution $X \times Y \times Z$ with respect to the value of the expectation of the function g. In this case, the information on the label $Y$ is given by $Z$. From my intuition (possibly wrong), the worst-case (lower-bound) is given by trying to get as much as possible $g(X) = 0$ (we make a mistake) whenever $h(X)$ is different from the most likely value of $Y$ given by $P(Y|Z)$. Analogous intuition for the upper bound. In particular, it looks like the gap between the lower bound and upper bound depend on "how much" the output of the classifier $h(X)$ differs from $P(Y|Z)$ given a sample $(X,Z)$. If this interpretation is correct, then it looks like that the lower bound and upper bounds are informative (i.e., close to one another) only if $h(X)$ follows the output of the labels $P(Y|Z)$, in which case it is not clear what is the advantage of training a classifier h.

(2) I think that the assumption that we can estimate $P_{X,Z}$ is too strong and not necessary (and not really used).

If $X$ is highly dimensional (i.e. images), it is impossible to estimate this distribution within any reasonable finite sample size. I do not think that this assumption is actually necessary for the scope of this paper, in fact all the applications of the results could be formulated substituting $X$ with $h(X)$, in which case $h(X)$ has the same support than the label space Y. In fact, for precision recall etc, we only need to consider a function$g(Y',Y,Z)$ where $Y'$ is the output of the classifier that is being evaluated.

I find it surprising that the results do not add any assumption on estimating the distribution $(X,Z)$ as this is a very hard problem in general. I think this is due to the fact that we never actually estimate the distribution itself, but we simply evaluate the function g that is bounded. This is a bit misleading with the introduction, where it is written that we use an estimate of $P(X,Z)$.

(3) I think that the Appendix section with the proof of the results is not well written nor easy to follow. I believe that the paper would greatly benefit from having a more organized proof structure, so that an interested reader can learn about the techniques used.

As an example, results from other papers are often used (e.g., Beiglbock & Schachermayer for proof of Theorem 2.1). It takes a lot of effort by the reader to understand the applications of those results, as these cited theorem use some assumptions, have different notation, and it is not immediately straightforward how they are translated to this paper setting. For readability, It would be easier to say something along the lines "since [... these assumptions hold ...] then we can apply this result from [citation] that says: "

Another example is the Proof of Theorem 2.4 (e.g., sequence of equations of page 16, or the sequence of Theorem and Lemmas). It would be easier if the proof is organized in a way such that it is easy to follow and understand the different parts of the proof.

(4) Concerns on the experiments.

In the experimental evaluation, only four datasets from Wrench are used. Wrench provides a lot of different datasets, it is not clear why only 4 were selected for the evaluation, and why only those specific 4 were selected (there are other datasets that are also limited to binary classification as SMS, Commercial ... from Wrench). In some practical cases in Wrench (as Youtube), we also care about the F1 score, which I think it can also be estimated with your method.

(5) Assumption on being able to estimate $P(Y|Z)$.

The assumption that one can estimate P(Y|Z) is very strong, and this is how the paper gets around the need of labeled data. This is unrealistic in practice. I think that the paper should specify that happens when the model is misspecified (theory), which is often the case for the parametric model mentioned in the paper. It would be interesting to understand if we can say something about the Frechet bound if we allow for a bounded misspecification, i.e. $|P(Y|Z) - \hat{P}(Y|Z)| < Delta$ for some $Delta >0$.

There are other papers that used somehow similar ideas to consider a "worst-case"(or adversarial) distribution over all possible distributions in a weak supervision setting that I think are very relevant (e.g., [A,B,C,D,E,F]). In particular, this problem was studied mostly for the case of trying to solve the map Z -> Y from weak supervision sources outputs to label without adding any assumption (e.g., independence or parametric assumption) [A,B,E], although some other work consider the more general case of training a classifier h [C,D,F].

The use of the "worst-case" allows to obtain an upper bound (analogous to the U of the Frechet Bound). As an example, the underlying idea is to consider possible joint distribution $Z,Y$ that satisfy some information on the marginal $P(Y|z_i)$ or $P(Z)$ (this information may vary among the work).

[A]: Balsubramani, A. and Freund, Y. Optimally combining classifiers using unlabeled data. In Conference on Learning Theory (COLT), pp. 211–225, 2015. [B]: Balsubramani, A. and Freund, Y. Optimal binary classifier aggregation for general losses. In Neural Information Processing Systems (NeurIPS), 2016. [C]: Arachie, C. and Huang, B. Adversarial label learning. In AAAI Conference on Artificial Intelligence (AAAI), 2019. [D]: Arachie, C. and Huang, B. A general framework for adversarial label learning. The Journal of Machine Learning Research, 22:1–33, 2021. [E]: Mazzetto, A., Sam, D., Park, A., Upfal, E., and Bach, S. H. Semi-supervised aggregation of dependent weak supervision sources with performance guarantees. In Artificial Intelligence and Statistics (AISTATS), 2021. [F]: Mazzetto, A., Cousins, C., Sam, D., Bach, S. H., and Upfal, E. Adversarial multi class learning under weak supervision with performance guarantees. In International Conference on Machine Learning, pp. 7534–7543. PMLR, 2021a.

Note that some of this work may require to have some labeled data to get this marginal information. Some information about the label is required in general. In some work, they assume to have access to some labeled data to estimate some statistical constraints. On the other hand, the result of this paper removes this assumption, but assume that you can get information of the labels from the label model P(Y|Z) (however this model could be misspecified).