Weak Supervision Performance Evaluation via Partial Identification
Authors: Felipe Maia Polo
Subha Maity
Mikhail Yurochkin
Moulinath Banerjee
Yuekai Sun
Venue: NeurIPS 2024 poster (2024)
Keywords: weak supervision
evaluation
Frechet bounds
partial identification
Primary area: evaluation
TL;DR: This paper introduces a method to estimate performance metrics like accuracy, recall, precision, and F1 score in the weak supervision setup when no ground truth labels are observed.

Abstract: Programmatic Weak Supervision (PWS) enables supervised model training without direct access to ground truth labels, utilizing weak labels from heuristics, crowdsourcing, or pre-trained models. However, the absence of ground truth complicates model evaluation, as traditional metrics such as accuracy, precision, and recall cannot be directly calculated. In this work, we present a novel method to address this challenge by framing model evaluation as a partial identification problem and estimating performance bounds using Fréchet bounds. Our approach derives reliable bounds on key metrics without requiring labeled data, overcoming core limitations in current weak supervision evaluation techniques. Through scalable convex optimization, we obtain accurate and computationally efficient bounds for metrics including accuracy, precision, recall, and F1-score, even in high-dimensional settings. This framework offers a robust approach to assessing model quality without ground truth labels, enhancing the practicality of weakly supervised learning for real-world applications.

Weak Supervision Performance Evaluation via Partial Identification
Felipe Maia Polo" Department of Statistics University of Michigan
Subha Maity
Department of Statistics and Actuarial Science University of Waterloo
Mikhail Yurochkin MIT-IBM Watson AI Lab
Moulinath Banerjee
Yuekai Sun
Department of Statistics
Department of Statistics University of Michigan
University of Michigan
Abstract
Programmatic Weak Supervision (PWS) enables supervised model training without direct access to ground truth labels, utilizing weak labels from heuristics, crowd- sourcing, or pre-trained models. However, the absence of ground truth complicates model evaluation, traditional metrics such accuracy, precision, and recall can- not be directly calculated. In this work, we present novel method to address this challenge by framing model evaluation as partial identification problem and esti- mating performance bounds using Fréchet bounds. Our approach derives reliable bounds key metrics without requiring labeled data, overcoming in current weak supervision evaluation techniques. Through scalable convex op- timization, we obtain accurate and computationally efficient bounds for metries including accuracy, precision, recall, and Fl-score, even in high-dimensional set- tings. This framework offers a robust approach to assessing model quality without ground truth labels, enhancing the practicality of weakly supervised learning for woal-world applications.
limitations
Introduction
Programmatic weak supervision (PWS) is modern learning paradigm that allows practitioners to train their supervised models without the immediate need for ground truth labels Y [50, 48, 47, 49, 58, 64]. In PWS, practitioners first acquire cheap and abundant weak labels Z through heuristics, crowdsourcing, external APIs, and pretrained models, which serve as proxies for Y. Then, they fit label model, i.e., a graphical model for Py,z [50, 49, 22, 17], which, under appropriate modeling assumptions, can be fitted without requiring Y's. Finally, a predictor h X - ) is trained using samples (X,, Zz)'s and noise-aware loss constructed using this fitted label model [50].
One major unsolved issue with the weak supervision approach is that even if we knew Py.z. evaluation metrics such as accuracy, recall, precision, or F1 cannot be estimated for model validation without any ground truth labels. In fact, these quantities are not identifiable (not uniquely determined) since we only have partial information about the joint distribution Px,y through the marginals Px z and Py.z- As a consequence, any performance metric based on h cannot be estimated without making extra strong assumptions, e.g,, X IL Y Z. Unfortunately, these conditions many situations. A recent work [66] investigated the role and importance of ground truth labels on model evaluation in the weak supervision literature. They determined that, under the current situation,
unlikely to arise in
Equual contribution. Corresponding author: Felipe Maia Polo < @ww.aaaaaappppmimlmmmmmmmmmmaale gmail.com. com Our code can be found on https: //githubb http:///ea..aeaessspppoeoooooooa
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

the good performance and applicability of weakly supervised classifiers heavily rely on the presence of at least some high-quality labels, which undermines the purpose of using weak supervision since models can be directly fine-tuned on those labels and achieve similar performance. Therefore, in this work, we develop new evaluation methods that can be used without any ground truth labels and show that the performance of weakly supervised models can be accurately estimated in many cases, even permitting successful model selection. Our solution relies on partial identification by estimating Fréchet bounds for bounding performance metrics such accuracy, precision, recall, and Fi score of classifiers trained with weak supervision.
Fréchet bounds: Consider a random vector (x, Y. Z) E X x y x Z is drawn from an unknown distribution P. We assume X' C Rd is arbitrary while y and 2 are finite. In this work, we develop and analyze the statistical properties of a method for estimating Fréchet bounds [53, 54] of the form
L a inf E,, (X,, Z)] and U - sup E. lo TEIT
(1.1)
*ell
when g fixed bounded function, with II being the set of distributions и for (X, Y, Z) such that the marginal xx,z (resp. Ty,z) is identical to the prescribed marginal Px,z (resp. Pr,z). Our proposed method can efficiently obtain estimates for the bounds by solving convex programs, with the significant advantage that the computational complexity of our algorithm does not scale with the dimensionality of X, making it well-suited for applications dealing with high-dimensional data. In previous work, for example, Fréchet bounds were studied in the financial context (e.g., Rüschendorf [55]. Bartl et al. [7]. However, our focus is on applying our methods of estimating Fréchet bounds to the problem of assessing predictors trained using programmatic weak supervision (PWS). For example, the upper and lower bounds for the accuracy of a classifier h can be estimated using our method simply by letting g y. [/(xr) y) in (1.1). At high level, method replaces Py.z with the fitted label model, and Px.2 with its empirical version in the Fréchet bounds in (I.1), and reformulates the problem in terms of convex optimization problem.
Contributions: Our contributions are
1. Developing a practical algorithm for estimating the Fréchet bounds in (1.1). Our algorithm can be summarized as solving convex programs and is scalable to high-dimensions distributions.
2. Quantifying the uncertainty in the computed bounds due to uncertainty in the prescribed marginals by deriving the asymptotic distribution for our estimators.
3. Applying our method to bounding the accuracy, precision, recall, and F1 score of classifiers trained with weak supervision. This enables practitioners to evaluate classifiers in weak supervision settings without access to ground truth labels.
1.1 Related work
Weak supervision: With the emergence of data- -unnry models, the lack of properly labeled datasets has become a major bottleneck in the development of supervised models. One approach to overcome this problem is using programmatic weak supervision (PWS) to train predictors in the absence of high-quality labels Y [50, 48, 47, 49, 58, 64]. PWS has shown the potential to solve a variety of tasks in different fields with satisfactory performance. For example, some works have applied weak supervision to named-entin recogmition [32, 21, 57], video frame classification [22], bone and breast tumor classification [61]. More recently, Smith et al. [59] proposed a new approach to integrating weak supervision and pre-trained large language models (LLMs). Rather than applying LLMs in the usual zero/few-shot fashion, they treat those large models as weak labelers that can be used through prompting to obtain weak signals instead of using hand-crafted heuristics. Recently, Zhu et al. [66] showed that in many situations, the success of weakly supervised classifiers depends on the availability of ground truth validation samples, undermining the purpose of weak supervision. Then, we develop a new method for model evaluation that does not depend on the availability of any ground truth labels.
relevant line of research within the realm of weak supervision that is closely related this work is adversarial learning [4, 5, 42, 41]. Often, adversarial learning aims to learn predictors that perform well in worst-case scenarios. For example, Mazzetto et al. [41] develops a method to learn weakly supervised classifiers in the absence of good label model. In their work, the authors use small set of labeled data points to constrain the space of possible data distributions and then find a predictor that performs well in the worst-case scenario. Our work relates to this literature in the sense that

---

are interested in the worst and best-case scenarios over set of distributions. However, we focus on developing an evaluation method instead of another adversarial learning strategy.
Partial identification: It is often the case that the distributions of interest cannot be fully observed, which is generally due to missing or noisy data [43, 23]. In cases where practitioners can only observe some aspects of those distributions, e.g. marginal distributions or moments, parameters of interest may not be identifiable without strong assumptions due to ambiguity in the observable data, Partial identification deals with the problem without imposing extra assumptions. This framework allows estimating set of potential values for the parameters of interest (usually given by non non-trivial bounds) and has been frequently considered in many areas such as microeconometrris [38-40 43], causal inference [25. 23]. algorithmic fairnsss [20, 46]. Our work is most related Rüschendorf [53, 54, 55], Bartl et al. [7], which study bounds for the uncertainty of a quantity of interest for a joint distribution that only partially identified through its marginals, i.e, Fréchet bounds. Compared to the aforementioned works, the novelty of our contribution is proposing a convex optimization algorithm that accurately estimates the Fréchet bounds with proven performance guarantees setup that is realized in numerous weak-supervision applications.
1.2 Notation
We write Eq and Varq for the expectation and variance of statistics computed using i..d. copies of random vector W ~ Q. Consequently, (4) = Eg A. where 1 is the indicator of an event A. the distribution is clear by the context, omit the subscript. If (0m)met and (bm)meN are sequences of scalars, then am = o(bm) is equivalent to am/ /bm - as m - Do and am = bm + o(1) means am - bm = o(1). If (v())) mEN is sequence of random variables, then (i) y(m) = o1(1) means that for every ε > 0 we have P([V(m)) > E) + 0 as m 7 oc, (ii) (mm) = Op(1) means that for every E > 0 there exists a MM > 0 such that supmen P([V(m) > M) < E, (iii) ((m) = am + o0p(1) means (m) am = (1). (iv) (mm) = op(an) means (mm) aam = Op (1), and (v) V (m) = (p()))
means ((m) /umm OP())
2 Estimating Fréchet bounds
A roadmap to approach follows. We first reformulate the Fréchet bounds in (1.1) into their dual problems, which we discuss in (2.1). Then, we replace the non-smooth dual problems with their appropriate smooth approximations, smooth approximations (2.3) and derive their asymptotic distributions in Theorem 2.5.
discussed in (2.2). Finally, we propose estimators for the
2.1 Dual formulations of the bounds and their approximations
This section presents result that allows us to efficiently solve the optimization problems in (1.1) by deriving their dual formulations as finite-dimensional convex programs. Before we dive into the result, let us define family of matrices denoted by
A A {a R 22 ΣnEy Uyy for every 2).
With this definition in place, we introduce the dual formulation Theorem 2.1. Theorem 2.1. Let g : X x y
R be a bounded measurable function. Then,
L sup B[fi(X, Z, a)) and U inf B[fu(X, 2, a)) a
(2.1)
aaA
where
f( 2,a) êmin [g(x; J. 2) + agel - -Epyiz [ay, 12 = 2] gey
Ju(#,
Amax (g(a,, 2) + ag=] Eryiz [aY:|7 = 2]
ney
Moreover, L and U are attained by some optimizers in A.
Theorem 2.1 remains valid if we maximize/minimize over R| instead of A. However, this is not necessary because the values of ft and fa remain identical for the following shifts in a: a. +- a a where by E R. By constraining the set of optimizers to A, we eliminate the possibility of having multiple optimal points. The proof of Theorem 2.1 placed in Appendix and is inspired by ideas from Optimal Transport; see Appendix A.
3

---

The computation of these bounds entails finding minimum or maximum over discrete set, meaning that straightforward application of their empirical versions could result in optimizing non-smooth functions, which is often challenging. To mitigate this, we consider a smooth approximation of the problem that is found to be useful in handling non-smooth optimization problems [3, 6]. We approximate the max and min operators with their "soft" counterparts:
softmin [61. ... bx} - -E logl k Σx exp(= =x) softmax(b1. .bk) } é E =logi K Σ. exp t )]
where E > is a small constant that dictates the level of smoothness. As E nears zero, these soft versions of max and min converge their original non-smooth forms. Using these approximations, we reformulate our dual optimization in (2.1) into smooth optimization problems:
L _ sup Bifi,e a)] and Ug - inf [E (X, (X,2,a aEA
(2.2)
aEA
where
(1, 2, - - Elog
1 |>]
Evey exp [ale.v.)toae }] Eryiz [ay= 7 = 2]
(u, 2,a) - e log
Eyey exp s(x.g.))ta -Bprz [ay: 1 =
and & > is kept fixed at an appropriate value. As a consequence of Lemma 5 of An et al. [3], we know that Le and Ug are no more than e log [ units from L and U. Thus, that distance can be regulated by adjusting s. For example, if we are comfortable with an approximation error of 10-2 units when J = 2, we will set 10 / log(2)= .014.
2.2 Estimating the bounds
In practice, it is not usually possible to solve the optimization problems in (2.2), because may not have direct access to the distributions Px,z and Pyiz. We overcome this problem by assuming that we can estimate the distributions using available dataset.
iid To this end, let us assume that we have a sample {(X,, Z,) ~ Px.2, and thus we replace the relevant expectations with Px,z by its empirical version. Additionally, we have sequence (55m) Y12, m E N} that estimates Priz with greater precision as m increases. Here, m can be viewed as the size of a sample to estimate Py Pyiz. Although the exact procedure for estimating the conditional distribution is not relevant to this section, we have discussed in our introductory section that this can be estimated using label model [49, 22] in applications with weak supervision or in a variety of other ways for applications beyond weak supervision. Later this section, we will formalize the precision required for the estimates. To simplify our notation, we omit the superscript m in f(m) 1/
whenever it is convenient to do so.
Thus, the Fréchet bounds are estimated as
L sup 1 x I fi.e a) and Úy inf 1 En fu, (X;, ai, aed n
(2.3)
aeA
where
(1, 2, a) 2 =
1 [
EyEn exp pla.v.))aau
}
E Eriz lays 1 = 2]
(x, a) e log
| Eyey exp (lzive)+ay
- Exriz [ay: 1Z= 2]
In our practical implementations we eliminate the constraint that En Byz = 0 for all = E Z by adding
a penalty term ExEz
d2 Ù. (and its negative to L.) and then solve unconstrained
convex programs using the L-BFGS algorithm [33]. Since the penalty term vanishes only when Σ, Oyz = 0 for all z E 2, we guarantee that the optimal solution is in A.
2.3 Asymptotic properties of the estimated bounds
In the following, we state the assumptions required for our asymptotic analysis of î.ę and Ú.. We start with some regularity assumptions.
Assumption 2.2. The and Ue are attained by some optimizers in A (2.2).
Assumption 2.3. Let à represent the optimizer for any problem (2.3), which is assumed to exist. Suppose ||ā]| (p()) as 0C.

---

We show in Lemmas C.4, C.5, and C.6 that Assumptions 2.2 and 2.3 can be derived in the binary classification case (13' if PYY
Z 2) is bounded away from both zero and one, i.e. < IP(Y 7 = 2) < 1 for some >> 0 for every y E y and E 2.
formalize the degree of precision for the sequence (P N} of estimators that we require for desired performances of the bound estimates.
In our next assumption,
Assumption 2.4, Denote the toial variation distance (TV) between probability measures as drv. For every z E for some À > 0, we have that drv (Pim)) (Py PrIZ=:) Op(m=>).
From Ratner ct al. [49]'s Theorem 2 and a Lipschitz property of the label model', we can conclude = 1/2 for popular label model used in the PWS literature. The asymptotic distributions for the estimated bounds follow.
Theorem 2.5. Assume 2.2, 2.3, and 2.4, and let n be a function of m such that n + oo and {(m²>) when m oc. Then, as m + 00
Vu(Le - Le) = o(, and vo(ū, - -V))= N(0,
where of. A far (X, L, a..)) ou. A Varfu, (X, Z, d.,e), and die and d'g are the unique optimizers to attain Lg and Ug (2.2).
Theorem 2.5 tells us that, if the label model is consistent (Assumption 2.4), under some mild regularity conditions (Assumption 2.2 and 2.3), our estimators and will be asymptotically Gaussian with means Lg and Ug and variances of.//n n and oa.e/ //n. The above theorem requires m² to grow faster than implying that, through assumption 2.4, Pyiz is estimated with precision greater than the approximation error when we replace Px.2 with E; 8x. In the case which À = 1/2, this condition translates to n m - 0 as n + 50. This allows us to derive the asymptotic distribution when combined with classical results from M-estimation (see proof in Appendix C).
Construction of confidence bounds: One interesting use of Theorem 2.5 is that we can construct an approximate confidence interval for the estimates of the bounds. For example, an approximate 1 confidence interval for Lg can is constructed as
i-
T.g
Try Vn
L.
TgÔLE +
where 7, 6- (12)) and δz,e is the empirical standard deviation of (i,5(X, Z, substituting the estimate (solution for the problem in 2.3). For such interval, it holds P(Le E i) ~ 1 - 7- 7.i.e i.e. with approximately 1 confidence can say that the true L. is in the interval above. An interval for Ue can be constructed similarly.
3 Evaluation of model performance in weak supervision
this section, we describe how to use the ideas presented in Section 2 to estimate non-trivial bounds for the evaluation metrics of a weakly supervised classifier l when no high-quality labels are available. In the standard weak supervision setup, only unlabeled data (X) is available, but the practitioner extract weak labels (Z) from the available data. More specifically,
assume access to the dataset {(X,, )+) i..d. with distribution Px,z, used in its entirety to estimate a label model Priz [49, 22] and where part of it, e.g., random subset of size is used to estimate bounds To simplify the exposition, assume the classifier h is fixed'.
3.1 Risk and accuracy
Let f be a generic classification loss function. The risk of a classifier defined as R(h) = (X),, Y)], which cannot be promptly estimated in weak supervision problem, where we do not observe any Y. In this situation, we can make use of our bound estimators in Section 2.2, where we set g(x, y, 2) {(h(z), y) obtain bounds for R(h). Furthermore. we can estimate an uncertainty set for the accuracy of the classification simply by letting g(2, y, z) = [[((r)= v].
RRtnner et al. [49] derive that in page 24 of their arXiv paper version. 'It is also possible to use distinct datasets estimating the label model and the bounds as long as the dataset to estimate the label much bigger. This is our approach the experiments. In practice, it can be obtained using all the data not used to estimate bounds.
5

---

3.2 Precision, recall, and Fi score
For a binary classification problem, where y {0, 1]. the precision, recall, and Fi score a classifier h are defined
p P 1 h(X)= 1) P(N()-LY=I) A P(((())= =
P(N(--LY=1) F(==I)
P(MI F +p -
2P(M X) -(1
The quantities P(h(X)) 1) and P(Y = 1) in the above definitions are identified, since the marginals Px,z and Py, are specified in the Fréchet problem in (1.1). The (()(X) 1) can be estimated from the full dataset {(X,, 2e) simply using P(h(X) = 1) & 1 - [)(X)) =1]. On the other hand, in most weak supervision applications, P(Y = 1) is assumed to be known from some prior knowledge or can be estimated from an auxiliary dataset, e.g., using the method described in the appendix of Ratner al. [49]. Estimating or knowing PP(Y = 1) is required fit the label model [49, 22] in the first place, so it is beyond our scope of discussion. Then, we assume we have an accurate estimate IY = 1).
The probability (()(X) Y, 1), which is the final ingredient in the definition of precision, recall, and F1 score is not identifiable as Px,y is unknown. The uncertainty bounds for this quantity can be estimated using our method simply by letting g(r,, y. 2) = 1 [h(x))
and 1]. Let f and Üg denote the estimated lower and upper bounds for (h((X) 1, Y 1) obtained using (2.3). Naturally, the lower bound estimators for precision, recall, and Fi score are
Pr.e
L. F() it,
A
2 L. and Fi.e ((X())))+P((-1)) P(Y-1)>
while the upper bound estimators Pu.e. fu.e. and Fu.e are given by substituting Le by Úg above. In the following corollary. we show that the bounds converge asymptotically to normal distributions, which we use for calculating their coverage bounds presented in our applications.
Corollary 3.1. Let n be a function of m such that n + oo and n = o (m(2))A1) when m - oo.
Assume the conditions of Theorem 2.5 hold. Then m 0o.
e Vn(ii - m1,)) = (f..)) with pt. = F(h(X)=I)) o p.l.c
L,
of P(x()==I)
of VTi(fi, -r,e)) N(0, o2 (.1,) with rı, F(Y=Ij+ o F(Y=I)²
21. VTi(fi. Fi,e) = (0, F..) with Fi, +(R())=)+R((=E)) & F [( =1)
4of
where Lee of. are defined Theorem 2.5. Asymptotic distributions for v ( (fu ru,e), and and
Fu,e)) are obtained in similar way by changing Tog to Ue and of, to 02
Reiterating discussion in the final paragraph in Section 2.2, asymptotic distributions important for constructing confidence intervals for the bounds, which can be done a similar manner.
4 Experiments
All experiments are structured to emulate conditions where high-quality labels are inaccessible during training, validation, and testing phases, and all weakly-supervised classifiers are trained using the noise-aware loss [50]. To fit the label models, we assume Py is known (computed using the training set). Unless stated, we use lz-regularized logistic regressors as classifiers, where the regularization strength is determined according to the validation noise-aware loss.
Wrench datasets: To carry out realistic experiments within the weak supervision setup and study accuracy/F1 score estimation, we utilize datasets incorporated in Wrench (Weak Supervision Benchmark) [63]. This standardized benchmark platform features real-world datasets and pre- generated weak labels for evaluating weak supervision methodologies. Most of Wrench's 's datasets are designed for classification tasks, encompassing diverse data types such as tabular, text, and image; all contain their pre-computed weak labels. Specifically, we utilize Census [27], YouTTbe [1], SMS [2], IMDB [37], Yelp [65], AGNews [65], TREC [31], Spouse [12], SemEval [24], CDR [14], ChemProt [29], Commercial [22], Tennis Rally [22], Basketball [22]. For text datasets,

---

youtube
imdo
cdr
commercial
tennis
1.0
1.0
1.0
1.0
1.0
acturacy
Oracle
accuracy
0.5
0.5
0.5
C 0.5
C 0.5
0.0
0.0
0.0
0.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5 threshold
1.0
0.5 thrashold
1.0
threshald
threshold
threshold
Snorkel
accuracy
acturacy
0.5
0.5
0.5
4
0.5
4
0.5
0.0
0.0
0.0
0.0
0.0
0.0
0.5
1.0
0.0
0.5 threshold
1.0
0.0
0.5
1.0
0.0
0.5 threshold
1.0
0.0
0.5
1.0
threshold
thresnold
threshold
lower
upper bound
accuracyiF,
Figure I: We apply our method to bound test metrics such accuracy and Fl score (in green) when true labels used to estimate performance. In the first ("Oracle"), distribution Pyiz, thus approximating scenario which the label model is reasonably specified. On the second row ("Snorkel"), ; we use a label model to estimate Priz without access to any true labels. Despite potential misspecification in Snorkel's label model, it performs comparably to using labels to estimate Priz. giving approximate but meaningful bounds.
true labels estimate the conditional
employ the paraphrase Trraphrase--iniLM-LBG. MiniLM-L6-v2 model from the sentence-Iranse trantoncetranssfommesss library for feature extraction [51]. Features were extracted the image datasets before their inclusion in Wrench.
Hate Speech Dataset [15]: This dataset contains sentence-level annotations for hate speech in English, sourced from posts from white supremacy forums. It encompasses thousands of sentences classified into either Hate (1) or noHate (0) categories. This dataset provides an ideal ground for examining recall and precision estimation. Social media moderators aim maximize the filtering of hate posts, i.e., increasing recall, while ensuring that non-hate content is rarely misclassified as offensive, maintaining high precision. Analogously to the Wrench text datasets, we utilize Maapphrase-MinnLMLLL
for feature extraction.
4.1 Bounding the performance of weakly supervised classifiers
In this section, we conduct an empirical study using some the Wrench and Hate Speech datasets to verify the validity and usefulness of our methodology. We compare results for which Py z is estimated using the true labels Y ("Oracle") and those derived using Snorkel's [48, 47] default label model with no hyperparameter tuning and thousand epochs. Such comparison facilitates evaluation of our method's s efficacy, especially in cases where the label model could be incorrectly specified. Results for other Wrench datasets and extra label model (FlyingSquid, [22]) are presented in Appendix F.
In Figure 1, we demonstrate our approaches bounding test metrics, such as accuracy and Fl score (shown in green), when no true labels are available to estimate performance various classification thresholds for binary classification tasks on Wrench datasets. In the first ("Oracle"), true labels used to estimate the conditional distribution Pyiz. representing (close to) ideal scenario with well-specified label model. In the second row ("Snorkel"), however, we use label model to estimate Priz without relying on any true labels. Despite potential inaccuracies in Snorkel's label model, achieves results close to those obtained using true labels to estimate PyJz. yielding approximate but useful bounds. This indicates that even if Snorkel's label model is imperfectly specified, its effectiveness in estimating bounds remains similar to that of the "Oracle" approach, underscoring the value of bounding metrics regardless of label model accuracy. Delving deeper into Figure results for "youtube", "commercial", and "tennis" highlight that our uncertainty about out-of-sample performance is small, even without labeled samples. However, there is noticeable increase in uncertainty for "imdb" and "cdr", making weakly supervised models deployment riskier without
Table Bounding accuracy multinomial classification.
bound
sec
Oracle
0.46
0.98
0.80
agRoos
Snorkel
0.42
0.920.01
0.76 os
0.54-2.04
0.78.20.0
0.72
Snurkel
0.36
0.70 0.7044.00
0.56
AAcessiible at https://tuggingaace.co/eeeeeeeee wttp://gw..aaccccacoeeeeeeeeeeee wtw.ssttmmrs///rraappoiioooooooa -i

---

additional validation. Yet, the bounds retain their informative nature. For instance. for those willing to accept the risk, the "imdb" classifier's ideal threshold stands .5. This is deduced from the flat worst-case and peaking best-case accuracy at this threshold. Table I presents some results for "agnews" (4 classes) and "semeval" (9 classes). From Table I, we can see that both "Oracle" and "Snorkel" approaches produce valid bounds.
Now, we present bounds on the classifiers' pre- cision and recall across different classification thresholds for the hate speech dataset. This
1.0
1.0
Oracle recall
precieon
0.5
0.5
dataset did not provide weak labels, so we
0.0
0.0
needed to generate them. We employed four distinct weak labelers. The initial weak labeler functions are based on keywords and terms.
0.0
0.5
1.0
0.0
0.5
1.0
threshold
threshold
1.0
1.0
Snorcel rerail
pracision
Should words or phrases match those identified as hate speech in the lexicon created by David-
0.5
0.5
son et al. [13], we categorize the sentence as 1; if not, it's designated 0. The second weak labeler is based on TextBlob's ss sentiment ana- lyzer [36]: a negative text polarity results 1 classification, while other cases are labeled
0.0
1.0
0.0
0.5
threshold
threshold
lower bound
upper bound
test recallprrrcc
Figure 2: Precision and recall bounds for hate speech 0. Our final pair of weak labelers are language detection.
models, specifically BERT [16] and RoBERTa [34], that have undergone fine-tuning for detecting toxic language or hate speech [35, 28). Figure 2 presents both recall and precision bounds and test estimates for the weakly-supervie Snorkel's s standard label model gives valuable bounds analogous to scenarios where we employ labels to estimate Py z. If used by practitioners, Figure 2 could help trade-off recall and precision by choosing an appropriate classification threshold in the absence of high-quality labels.
hate speech classifier. Mirroring observations from Figure 1,
4.2 Choosing a set of weak labels
In this experiment, we examine how our approach performs under the influence of highly informative weak labels as opposed to scenarios with less informative weak labels. Using the YouTube dataset provided by Wrench, we attempt to classify YouTube comments into categories of SPAM or HAM, leveraging Snorkel to estimate Priz- Inspired by Smith et al. [59], we craft three few-shot weak labelers by prompting' the large language model (LLM) aaaaaa---a--hhaeeeeeeeeee- dataset entry, we pose three distinct queries to the L.M.. Initially, we inquire if the comment is SPAM HAM. Next, we provide clear definitions of SPAM and HAM, then seek the classification from LLM. In the third prompt, leveraging in-context learning ideas [17). we provide five representative comments labeled as SPAM/HAM prior to requesting the LLM's verdict on the comment in question. In cases where LLM's response diverges from SPAM or HAM, we interpret it as LLM's abstention.
[60]. For each
After obtaining this triad of weak labels, analyze two situations. Initially, integrate the top five weak labels ("high-quality" labels) from Wrench. In the subsequent scenario, we synthetically generate weak labels ("low "low-quality" labels) that do not correlate with Y. The first plot in Figure 3 depicts the bounds of our classifier based solely on weak few-shot labels, which unfortunately do not provide substantial insights. Enhancing the bounds requires the inclusion of additional weak labels. Yet, as indicated by the subsequent pair of plots, it becomes evident that only the incorporation of "high-quality" weak labels results in significant shrinkage and upward shift of the bounds. As confirmed by the test accuracy, if a practitioner had used our method to select the set of weak labels, that would have led significant boost in performance.
4.3 Model selection strategies using the Fréchet bounds
In Sections 4.1 and 4.2, we implicitly touched on the topic of model selection when discussing the classification threshold and weak label selection. Here, we explicitly discuss the use our Fréchet bounds for model selection purposes. Consider a set of possible models H A [hi,.... hxx) from which we wish to find the best model according to a specific metric, e.g., accuracy, or F1 score. We consider three approaches for model selection using the Fréchet bounds: choosing the model with the best possible (i) lower bound, (ii) upper bound, and (iii) average of lower and upper bounds on the metric of interest. Strategy (i) works well for the worst-case scenario and can be seen as the
7 Moor details regarding the prompts can be found in Appendix G.
'The most informative weak labels are determined based their alignment with the true label.
8

---

LLM few-shat WLs extra low quality WLs (9WLs=E)
LLM few shot WLs extra
LLM few-shot WLS (#
high quality WLs (#WLs=8)
1.00
youtube
0.75
0.75
0:75
88 0.50
0.50
8 0.50
upper
test aCc
0.25
0.00
0.00
0.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0:25
0.50 0.75 threshold
1.00
threshold
threshold
Figure Performance bounds classifiers on the YouTube dataset, initially relying solely on few-shot weak labels obtained via prompts to the LLM Llama-2-138 1-ima------ccat---- comparative impact of integrating "high-quality" lahels from Wrench versus synthetically generated "low-quality" labels. Evidently, the addition of "hiighqualitt" labels significantly enhances the bounds, underscoring their superior utility over "low-quality" lahels for optimal classification of SPAM and HAM comments.
The progression of plots illustrates the
distributionally robust optimization (DRO) [9] solution when the uncertainty set is given by IT in (1.1), while (ii) is suitable for an optimistic scenario, and (iii) is suggested when one wants to balance between the worst- and best-case scenarios. Please check Appendix for more details.
In this experiment, we select multilayer-perceptren hidden layer with possible number of neurons in (50, 100). Training is carried with Adam [26], with possible learning rates in {.1, }001} and weight decay (l2 regularization parameter) in (.1,.001). For those datasets that use the Fl score as the evaluation metric, we also tune the classification threshold in {.2, 4. .,, 66..8. prediction). In total, H. is composed of 8 trained models when evaluating accuracy and 40 models when evaluating the F1 score. We also consider directly using the label model (Snorkel [47]) to select models. For example, when the metric considered accuracy, i.e., we use select the model arg max EH 2 Σ E Pyyz 1 (X) = =Y Z Z,), which is a natural choice when X IL Y Z. As baselines, we consider having few labeled samples.
(MLPs). The considered MLPs have one
(otherwise, they return the most probable class as
In Table 2, we report a sub- set of results (please check Appendix full set of results). In this table, we report the aver- age test scores of the cho- sen models over 10 repeti- tions for different random seeds (standard deviation re-
Table 2: Performance of selected models
mg
Labeled
for the
agnews
0.77
0.78+..00
0.77 0.700..00
0.77+ 00
imdll
0.72#0000
0.73+
0.73
0.72
yelp
0.81 0.81
0.81 4:0.0
1.81go..o
0.82 01
0.76.20.1
0.76
0.75
0.71
commerccial
Fl
0.9 0.98
0. 0.96 00
0. 0.96
0.91 01
port as subscript). We can extract some lessons from the table. First, using metrics derived from the Fréchet bounds is most useful when our uncertainty about the model performance is low, e.g. " ""commercial" and "tennis" in Figure 1. In those cases, using our metrics for model selection gives better results even when compared to a labeled validation set of size n 100. Moreover, once the practitioner knows that the uncertainty is low, using the label model approach also does well.
Discussion
5.1 Extensions
An extension we do not address in the main text is the evaluation of end-to-end weak supervision methods [62, 56, 52], where the separation between the label model and the final predictor is less clear than in our primary setting. Our approach remains compatible with these methods as long as we can fit a label model (e.g., Snorkel) separately and utilize it solely for the evaluation step. Another possible extension is the application of the ideas presented in this work in different fields of machine learning or statistics. One could consider applying our ideas the problem of "statistical matching" (SM) [18. 10, 19, 30, 11]. for example. The classic formulation of SM involves observing two distinct datasets that contain replications of (X, Z) and (Y, Z), but the triplet (X, Y, Z) is never observed. The primary goal is to make inferences about the relationship between X and Y. For instance, if our focus is on bounding P((X, Y) E B) TE a (X,, Y)] for certain event B, we could define g( y, 2) = 1 L 1 y) and apply our method.

---

5.2 Limitations
We discuss some limitations of our methods. Firstly, our method and theoretical results are only applicable to cases where )' and Z are finite sets, such as in classification problems. Extending the dual formulation in Theorem 2.1 to general y and 2 is possible but would require optimizing over function spaces, which is computationally and theoretically challenging. Additionally, if [2] is large, convergence may be slow, necessitating a large unlabeled dataset for accurate bounds. Using a smaller, curated set of weak labels, may be more effective for bounds estimation and performance. We end this subsection with two other limitations related to misspecification in the label model and informativeness of the bounds. The proofs of the results introduced in this section placed in Appendix D.
Label model misspecification: In our asymptotic results we assumed that the label models are well-specified, i.e., the estimates { m E N] converge to the true label model Pyiz at m -> 0o. To understand the qualities of our bound when this assumption is violated, we introduce the misspecification: p(m) - Qy and Qriz # Pyiz. In our investigation on the misspecification of the label model, we control the level of misspecification as study the subsequent errors in our Fréchet bounds. The following theorem formalizes the result.
I ô and then
Theorem 5.1. Recall from equation (2.2) that Le and U. are the smoothened upper and lower Fréchel bounds with the true Pr|z=> Additionally, let us define similar Le and U. bounds, but with a misspecified Qriz== i.e.
L. - sup (X,,,e(X (X,2aa) and U. - inf Bl (x))) aEA
aEA olesse))ovs
(1,( - -elog
[1S] EvEy exp
] EQriz lay= 7 2]
(5.1)
g(u:y)))o iueex, z, a) 2 e elog EyEy exp
] -EQvIa lay 2 = =]
c
Assume Qriz is in a set of conditional distributions such that the optimizers for (5.1), which are assumed exist, are uniformly bounded. If drv (Qr1z=:: PrIz==) 8, then for some C >> 0 which is independent of i > O. we have
max (It, - Lel, - U2l) S C8.
(5.2)
The above theorem reveals how misspecification translates to the errors in subsequent Fréchet bounds. In an ideal scenario, with access to an {(Y,, ) sample we can consistently estimate Priz, leading to 5 = 0. In situations when this {(Y,, ()), ) sample is not accessible and we have to rely on a label model, we require the misspecification in this model to be small.
Informativeness of the bounds: The bounds T. and U are especially useful when their difference U - I. is small because in that case, we obtain tight bound for [X, Y; Z)] and narrow it down with high precision even if the joint random vector (X,Y, Z) is never observed. But when is this bound small? In the next theorem, we provide an upper bound on this difference.
Theorem 5.2. Let I and U be defined as in equation (1.1). Then
U - U-L V I1l1 min(H(X 2), HY Z)}
where H(X 2) (resp. HY ()) denotes the conditional entropy of X (resp. Y) given Z.
To understand the result better, recall our setting: we do not observe the joint distribution Px.y.z and only observe the marginals Pr.z and Px, z. The only way we can infer about the joint distribution is by connecting these two marginals through Z. So, readers can guess that it is more favorable when Z is informative for either X or Y. For example, take the extreme case when Y h(Z) for function h: y + Z. In this case the Px.x,z Px.g Z). is precisely known from the Px.z and
we can exactly pinpoint the EXg Y, Z) as EXg(XX, I(( 2)). In this case, H(Y 2) = O, leading
to U I, = 0, i.e., its Fréchet bounds can precisely pinpoint it well; ideally at least one of the H(X Z) and H(Y Z) is small.
6 Acknowledgements
This paper is based upon work supported by the National Science Foundation (NSF) under grants no. 1916271, 2027737, 2113373, and 133664
10

---

References
[1] T.C. Alberto and J. Lochter. Yube Spam Collection. UCI Machine Learning Repository,
2015. DOI: https//doo.org/1224444//65333
[2] Tiago Almeida and Jos Hidalgo. SMS Spam Collection. UCI Machine Learning Repository, 2011. DOI: http:///bb..rr//0022443/////
[3] Dongsheng An, Na Lei, Xiaoyin Xu, and Xianfeng Gu. Efficient optimal transport algorithm by accelerated gradient descent. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 10119-10122 2022.
[4] Chidubem Arachie and Bert Huang. Adversarial label learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3183-3190, 2019.
[5] Chidubem Arachie and Bert Huang. A general framework for adversarial label learning. J. Mach. Learn, Res., 22:1 18-1, 2021.
[6] Azam Asl and Michael L Overton. Behavior of limited memory bfgs when applied to nonsmooth functions and their nesterov smoothings. In Numerical Analysis and Optimization: NAO-V, Muscat, Oman, January 2020 V, pages 25-55. Springer, 2021.
[7] Daniel Bartl, Michael Kupper, Thibaut Lux, Antonis Papapantoleon, and Stephan Eckstein. Marginal and dependence uncertainty: bounds, optimal transport, and sharpness. SIAM Journal on Control and Optimization, 60(1):410-434 2022.
(8) Mathias Beiglböck and Walter Schachermayer. Duality for borel measurable cost functions. Transactions of the American Mathematical Society, 363(8))4203-4222 2011.
[9] Ruidi Chen, Joannis Ch Paschalidis, et al. Distributionally robust learning. Foundations and Trends@ Optimization, 4(1-2):1-2433 2020.
[10] Pier Luigi Conti, Daniela Marella, and Mauro Scanu. Statistical matching analysis for complex survey data with applications. Journal of the American Statistical Association, 111(516): 1715-1725, 2016.
[11] Pier Luigi Conti, Daniela Marella, and Mauro Scanu. An overview on uncertainty and estimation in statistical matching. Analysis of Integrated Data, pages 70-100, 2019.
[12] David PA Corney, Dyaa Albakour, Miguel Martinez-Alvarez, and Samir Moussa. What do million news articles look like? In NewsIR @ ECIR, pages 42 47, 2016.
[13] Thomas Davidson, Dana Warmsley, Michael Macy, and Ingmar Weber. Automated hate speech detection and the problem of offensive language. In Proceedings of the international AAAI conference on web and social media, volume 11, pages 512-515, 2017.
[14] Allan Peter Davis, Cynthia Grondin, Robin Johnson, Daniela Sciaky, Benjamin King, Roy McMorran, Jolene Wiegers, Thomas C Wiegers, and Carolyn J Mattingly. The comparative toxicogenomics database: update 2017. Nucleic acids research, 45(D1):D972-D978, 2017.
[15] Ona de Gibert, Naiara Perez, Aitor García-Pablos, and Montse Cuadros. Hate Speech Dataset from White Supremacy Forum. In Proceedings of the 2nd Workshop on Abusive Language Online (ALW2), pages 1-200, Brussels, Belgium, October 2018. Association for Computational Linguistics. doi: 10. 10.18653/v1/W18-- 5102. URL https: /www. aclweb. org/ anthology/ 5102.
[16] Jacob Devlin. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04880 2018
[17] Qingxiu Dong, Lei Li, Damai Dai, Ce Zheng, Zhiyong Wu, Baobao Chang, Xu Sun, Jingjing Xu, and Zhifang Sui. survey for in-context learning. arXiv preprint ar0iv:2301. 303,04434,4 2022.
[18] Marcello Orazzio, Marco Di Zio, and Mauro Scanu. Statistical matching: Theory and practice. John Wiley & Sons, 2006.

---

[19] Marcello D' D'Orazio. Statistical learning in official statistics: the case of statistical matching. Statistical Journal of the IAOS, 35(3)4335-41, 2019.
[20] Riccardo Fogliato, Alexandra Chouldechova, and Max G'Sell. Fairness evaluation in presence of biased noisy labels. In International conference on artificial intelligence and statistics, pages 2325-2336, PMLR, 2020.
[21] Jason A Frics, Ethan Steinberg, Saclig Khattar, Scott L Fleming, Jose Posada, Alison Callahan, and Nigam Shah. Ontology-driven weak supervision for clinical entity classification in electronic health records. Nature communications, 12(1):2017, 2021.
[22] Daniel Fu, Mayee Chen, Frederic Sala, Sarah Hooper, Kayvon Fatahalian, and Christopher Ré. Fast and three-rious: Speeding up weak supervision with triplet methods. International conference machine learning, pages 3280-3291. PMLR, 2020.
[23] Wenshuo Guo, Mingzhang Yin, Yixin Wang, and Michael Jordan. Partial identification with noisy covariates: A robust optimization approach. In Conference on Causal Learning and Reasoning, pages 318- 335.3...00 PMLR, 2022.
[24] Iris Hendrickx, Su Nam Kim, Zornitsa Kozareva, Preslav Nakov, Diarmuid Ó Séaghdha, Sebastian Padó, Marco Pennacchiotti, Lorenza Romano, and Stan Szpakowicz. SemEval- 2010 task 8: Multi-way classification of semantic relations between pairs of nominals. In Katrin Erk and Carlo Strapparava, editors, Proceedings of the 5th International Workshop on Semantic Evaluation, pages 33-38, Uppsala, Sweden, July 2010. Association for Computational Linguistics. URL https:tt/////.m.tmm tetettss:/aacaatttttoo httpa/aaaaaooooooorrrrr..ra
[25] Nathan Kallus. What's the harm? sharp bounds on the fraction negatively affected by treatment. Advances in Neural Information Processing Systems, 15:15996-66009 2022.
[26] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
[27] Ron Kohavi. Census Income.
UCI Machine Learning Repository, 1996. DOL
[28] Petra Kralj Novak, Teresa Scantamburlo, Andra Pelicon, Matteo Cinelli, Igor Mozetič, and Fabiana Zollo. Handling disagreement in hate speech modelling. In International Conference Information Processing and Management of Uncertainty in Knowledge-Beut Based Systems, pages 681-695 Springer, 2022.
[29] Martin Krallinger, Obdulia Rabal, Saber A Akhondi, Martin Pérez Pérez, Jesús Santamaria, Gael Pérez Rodríguez, Georgios Tsatsaronis, Ander Intxaurrondo, José Antonio López, Umesh Nandal, et al. Overview of the biocreative vi chetical-protein interaction track. In Proceedings of the sixth BioCreative challenge evaluation workshop, volume 1, pages 141-146, 2017.
[30] Israa Lewaa, Mai Sherif Hafez, and Mohamed Ali Ismail. Data integration using statistical matching techniques: A review. Statistical Journal of the IAOS, 37(4):1391-14 2021.
[31] Xin Li and Dan Roth. Learning question classifiers. In COLING 2002: The 19th International Conference Computational Linguistics, 2002.
[32] Pierre Lison, Aliaksandr Hubin, Jeremy Barnes, and Samia Touileb. Named entity recognition without labelled data: weak supervision approach. arXiv preprint arXiv:2004. 14723, 2020.
[33] Dong Liu and Jorge Nocedal. On the limited memory bfgs method for large scale optimization. Mathematical programming, 45(1-3):503-528, 1989.
[34] Yinhan Liu. Roberta: A robustly optimized bert pretraining approach. arXiv preprint
197.v.190.111692, 2019.
[35] Varvara Logacheva, Daryna Dementieva, Sergey Ustyantsev. Daniil Moskovskiy, David Dale, Irina Krotova, Nikita Semenov, and Alexander Panchenko. ParaDetox: Detoxification with parallel data. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pupers), pages 6804-6818, 18, Dublin, Ireland, May 2022. Association for Computational Linguistics. URL https: / /aclanttolooooyyoo/ org 2022 acl 1lloong... 469.
12

---

[36] Steven Loria et al. textblob documentation. Release 0.15, 2(8):269, 2018.
[37] Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng. and Christopher Pous. Learning word vectors for sentiment analysis. Proceedings of the 49th Annual Meeting of the Association, for Computational Linguistics: Human Language Technologies -Volume
1. HLT '11, page 142-150, USA, 2011. Association for Computational Linguistics. ISBN 9781932432879.
[38] Charles F Manski. Anatomy of the selection problem. Journal of Human resources, pages 343-360, 1989.
[39] Charles F Manski. Nonparametric bounds on treatment effects. The American Economic Review, 80(2):3193323 1990.
[40] Charles F Manski. Partial identification of probability distributions, volume 5. Springer, 2003.
[41] Alessio Mazzetto, Cyrus Cousins, Dylan Sam, Stephen H Bach, and Eli Upfal. Adversarial multi class learning under weak supervision with performance guarantees. In International Conference on Machine Learning, pages 7534-7543. PMLR, 2021.
[42] Alessio Mazzetto, Dylan Sam, Andrew Park, Eli Upfal, and Stephen Bach. Semi-supervised ag- gregation of dependent weak supervision sources with performance guarantees. In International Conference on Artificial Intelligence and Statistics, pages 3196-3204. PMLR, 2021.
[43] Francesca Molinari. Microeconometrics with partial identification. Handbook of econometrics, 7:355 486, 2020.
[44] Wojcicch Niemiro. Asymptotics for m-estimators defined by convex minimization. The Annals of Statistics, pages 1514-1533, 1992.
[45] Gabriel Peyré, Marco Cuturi, al. Computational optimal transport: With applications to data science. Foundations and Trends@ in Machine Learning, 11(5-6)355-6077 2019.
[46] Flavien Prost, Pranjal Awasthi, Nick Blumm, Aditee Kumthekar, Trevor Potter, Li Wei, Xuezhi Wang. Ed H Chi, Jilin Chen, and Alex Beutel. Measuring model fairness under noisy covariates: A theoretical perspective. In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, pages 873-883, 2021.
[47] Alex Ratner, Braden Hancock, Jared Dunnmon, Roger Goldman, and Christopher Ré. Snorkel metal: Weak supervision for multi-task learning. In Proceedingy of the Second Workshop on Data Management for End- To-End Fo-End Machine Learning, pages 1-4,2011 2018.
[48] Alexander Ratner, Stephen H Bach, Henry Ehrenberg, Jason Fries, Sen Wu, and Christopher Ré. Snorkel: Rapid training data creation with weak supervision. In Proceedings of the VLDB Endowment. International Conference on Very Large Data Bases, volume 11, page 269. NIH Public Access, 2017.
[49] Alexander Ratner, Braden Hancock, Jared Dunnmon, Frederic Sala, Shreyash Pandey, and Christopher Ré. Training complex models with multi-task weak supervision. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4763-4771, 2019.
[50] Alexander Ratner, Christopher M De Sa, Sen Wu, Daniel Selsam, and Christopher Ré. Data programming: Creating large training sets, quickly. Advances in neural information processing systems, 29, 2016.
[51] Nils Reimers and Iryna Gurevych. Sentence-bert, Sentence embeddings using siamese bert- networks. In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 2019.
[52] Salva Rühling Cachay, Benedikt Boecking, and Artur Dubrawski. End-to-end weak supervision. Advances in Neural Information Processing Systems, 34: 34:1845-1855 2021.
[53] Ludger Rüschendorf. Bounds for distributions with multivariate marginals. Lecture Notes- Monograph Series, pages 285-310, 1991.
13

---

[54] Ludger Rüschendorf. Fréchet-bounde and their applications. In Advances in Probability Distributions with Given Marginals: beyond the copulas, pages 151-187. Springer, 1991.
[55] Ludger Rüschendorf. Risk bounds and partial dependence information. From Statistics to Mathematical Finance: Festschrift in Honour of Winfried Stute, pages 345-366, 2017.
[56] Dylan Sam and J Zico Kolter. Losses over labels: Weakly supervised learning via direct loss construction. In Proceedings of the AAAI conference on artificial intelligence, volume 37, pages 9993,9703, 2023.
[57] Agam Shah, Ruchit Vithani, Abhinav Gullapalli, and Sudheer Chava. Finer: Financial named entity recognition dataset and weak-supervision model. arXiv preprint TrXiv:2302.11157 2023,
[58] Changho Shin, Winfred Li, Harit Vishwakarma, Nicholas Roberts, and Frederic Sala. Univer- salizing weak supervision. arXiv preprini arXiv:21 2021.
[59]
Ryan Smith, Jason A Fries, Braden Hancock, and Stephen H Bach. Language models in the loop: Incorporating prompting into weak supervision. arXiv preprint 2rX5::2205.02318 2022.
[60] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprini (tti:2307.00288 2023.
[61] Paroma Varma, Bryan He, Payal Bajaj, Nishith Khandwala, Imon Banerjee, Daniel Rubin, and Christopher Ré. Inferring generative model structure with static analysis. Advances in neural information processing systems, 30, 2017.
[62] Yue Yu, Simiao Zuo, Haoming Jiang, Wendi Ren, Tuo Zhao, and Chao Zhang. Fine-tuning pre-trained language model with weak supervision: A contrastive-regullriied self-training approach. arXiv preprint arXiv:2010.07835, 2020.
[63] Jieyu Zhang, Yue Yu, Yinghao Li, Yujing Wang, Yaming Yang. Mao Yang, and Alexander Ratner. Wrench: A comprchensive benchmark for weak supervision. arXiv preprint arXiv:2109.1133 2021.
[64] Jieyu Zhang, Cheng- Yu Hsieh, Yue Yu, Chao Zhang, and Alexander Ratner. A survey on programmatic weak supervision, arXiv preprint arXiv:2202.054333 2022.
[65] Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. Advances in neural information processing systems, 28, 2015.
[66] Dawei Zhu, Xiaoyu Shen, Marius Mosbach, Andreas Stephan, and Dietrich Klakow. Weaker than you think: A critical look atweakly supervised learning. arXiv preprint arXiv:2305. 17442. 2023.
14

---

A Connection to optimal transport
The optimizations in the Frechet bounds (1.1) can be connected to an optimization problem [45]. We only explain this connection for the lower bound, but the connection to the upper bound is quite similar. The optimization lower bound is
inf xnfxxx2=xx. E (X, Y, Z)]= Triz=Priz
Σ. P(Z =
2=
Priz
= Σ. PZ 2)
-P E Exx.ris 1g v2 Sy|z=.=Py122.
where notice that the inner minimization is optimal transport problem between the probability distributions Pxiz== and Pyiz== with the cost function d2(r, y) = g(,, 2).
15

---

B A proof for the duality result
Proof of Theorem 2.1. We start proving the result for L. See that
L inf Ex (XX, Y, Z]] Hell
inf
Σ
IP = 2) En, (X( Z =
=
(r.ell. =EZ
Σ PPZ = 2) inf En, lg(,, 2) 2 = z] ZEZ
Ell,,
with II,, is defined as
II, - fTT, A(X x V) PX Pxiz== and nT Py Priz=z]
That is, for each Z, II, represents the set of couplings such that marginals given by Px|z= and Priz=z- We can represent the problem this way since the marginal distribution of Z is fixed and, given that distribution, } specifies the same set of distributions as II.
Realize that we have broken down our initial maximization problem in | smaller minimization problems. Each of those minimization problems can treated an optimal transportation problem.
Consequently, by Beiglböck and Schachermayer [8, Theorem 1], for each 2 E Z, we get the following duality result
EnI, Er,, Er, (,(X,Y, Z = 2] = sup (8, (x) + (x) Z = 21
with
Bg : X + -000, Y x0)
V. & (B2, (z))
3 (X)1 1 == o0, (Y)
<0
B2 (x) + az(y) S ao(,,,,2 for all (z. 1) E X x
Moreover, partially optimizing on Bg (z), we can set (+(x) min y, (z)))) and then
inf ell, E,, (g( X, Y, 2) 2 =| suPa. E [min [gggeee[XXXXX,[X (X, y, Z) - 2
where agg is a simple function taking values in the real line. Consequently,
L = Σ PP(Z = 2) sup E
min (o, 7) + az((y) ax) 2 = NEY
2EZ
sup
Σ PPZ 2) E
Z) as((il as( 2
(ashez 2EZ
yEY
minig((X, y, 2) + az(x)] - IEEY
sup
(azhaez
Because each 0g is a function assuming at most | values and we have Z functions (one for each value of 2), we can equivalently solve an optimization problem on [2 Adjusting the notation,
L
sup XIZI
E
min [g(X, U. Z) agz]
E [ayz]
.EEy
From Beiglböck and Schachermayer [8, Theorem 2}. we know that the maximum is attained by some a" E 21 show that there a maximizer A, we need to update the solution
0
Eyey Oz (shift sub-vector by constant)
(B.1)
for every 2. The objective function is not affected by such translations.
To prove the result for U, first realize that because g is bounded, with no loss of generality, we can assume its range is a subset of [0. 1). Define c(æ, y, 2) = g y, 2) and see that
U sup E c(X, Y, 2)
inf F2, [c (X, Y, Z)]
=ell
well
Proceeding as before, we can obtain the final result by finding the dual formulation for inf E_ [_ Y, Z)).
16

---

C Proofs for the estimation results
We will analyze the estimator for U (results for the estimator of L can be obtained analogously). For the next results, define
(a, 2, a (0, + + Eys
Proof of Theorem 2.5. By Assumption 2.2 and Lemmas C.I and C.2, Elfu,e(X, Z, a,a)] is minimized by unique d (equalling it to Ug)) and that VeBlfu,e Z, a,,e) is positive definite. Also, from the proof of Lemma C.2, we can see that fu,s is convex in (because its Hessian is positive semidefinite). It is also true that the second moment of fu,e (X, Z, a) is well defined (exists and finite) for each a since g bounded. Define
guarantee that
Úg
& inf GERIVIKIZ
1 E Fu,e (X,, a.
and let ag denote value that attains that minimum; from Niemiro [44, Theorem 4] and the conditions discussed above, we know that vn(ā, - -.,e) Op)).. The existence of ā is discussed by Niemiro [44]. Then
Vn(ūe- - Ue)
Σ (Xs; E (Xx vn Σ
Su, (x) Ue
Vn
"
(Viilae - -c,,e)] Σ v2 (X 2, 2,, - d'aeel +
Vn
1 Σ FuelX anec) - Ue + 0p((1
+ vn
(C.1)
where the first term is obtained by a second-order Taylor expansion of the summing functions around āg (ā is some random vector). Also, from the standard central limit theorem, we know that
Vn E1 fule (X,, Zi, dm,e) Us) = NO, Varfu, (X, Z, at,e))
Given that Vā(āa-- dr,e) Op()) and that the Hessian has bounded entries (then (p(1) as well), the first term in C.1 is (1). Because aree E A, we have that f..((X,) , Z, aú = (x, Z, a,,e) and then
Vn(ū, - U2) N(0, Varfu. Z, a. om,e))
by Slutsky's theorem. Since
vū(U. - U) U)= -ā(0 - volli* -U.). U.),
we can show that
vā(U, - o1()
are done.
17

---

Let be solution for the problem in 2.3 and see that
102 Uzl=
1 Ei Su,c( 0c) ; Ei= log [S] Evey exp (0Xt:,221)+aay )] + R BB larz = Zil
En Fun (X 21, E. (X,, (i, Z1, +
EL= l X, 21,0) - Ei= elgg [ Evey exp (2N )] Epriz Jāyz 2 = Zil Ei X1 Zi,
1 - (N,
(X,, Zi,ūe)) (z,
Eis ((Y = = = Σ,) PPYY- = y Z Zi)layz
n El Pule Xi, Zí, a) 1 - E log [1>]] EvEr oxp (.. )} E Priz jāyz 2 = Zi)
s(X,N)22)) )}
E e clog [ Eyey exp
Priz Fāerz == 7i| 1 Ei=i (X, 75,
Dim Ey IP(Y = 2 = 4) - -P(Y = y 7 = =Z:)
1 Eh Eyl y - = 4) P(Y = y Z = =z,)lay2.)
E E [P(Y = 2 Z Z, - P(Y = y Z = Zi)lāeyz
D E, Pyp
2 2,) - P(Y y Z Z,)]
$ 2 |0 00 E E, IP(Y = = == P( y Z 2,)l+
| lla E E, P|Y= =y/ 4) P(Y y 2 74)
I 2 1llll N0 Σ. E, |P(Y = - - -P((Y = y Z = =)[+
-
+ |lāeloc Σ. E, |P(Y -y f((y = = 2 = =)1
4 1/ E. dIv (Prizzz:Prize) Priz 2 llāelloo Eg
Eiv drv Pr
Or(m~>)
where the last equality is obtained using Assumptions 2.3 and 2.4, and the fact that llāelloo tight (derived from vn(ā, dm,e) (1))) Consequently,
Vn(ū,-Ú:) VnOppm (m = op(()
Finally, using Slutsky's theorem.
Vn(ū. - U) vn(0, - Ü.) + Vn(ū. U) = N(0, (X, arr))
Proof of Corollary 3.1. We prove the asymptotic distribution of vn(iu,s Du.z). The result for the lower bound can be obtained analogously.
First, note that
((((X)) = 1) P(K(X) = 1) (p(m-113)
(C.2)
by the standard central limit theorem.
18

---

Next, see that
VT (Pu.e Pu,e)
-v
U.
U
F(((x)=1)
P(A(X)-1)
P()(X)=1) Vn2 (U=- B(((X)=1)
P(A(X)=1) U..
F[](X)=1) vūl ÜÜs Us) + P[((X)=1]
U P(N(X)=) Up
F(
F[](X)=1) Vn ÜÜs Us) + UeVT
[(M(x)=1) P()(X)=1)
((((X)=1) Vn Ü Up}
+ Uevn
(P(M(X) =) - P((())()))) =1)) (fAN))=))) or (m-
n Ü Ug)
+ Op (1)
((((X)= + (O, op
where the (i) fifth and sixth lines equality is obtained using Taylor's theorem, (ii) sixth and seventh lines equality is obtained using observation C.2 and the fact that n = ((m(2))))) and (iii seventh to eighth lines equality is obtained using observation C.2, Theorem 2.5, and Slutsky's theorem.
We prove the asymptotic distribution of vn((fa,e Ta.s). The result for the lower bound can be obtained analogously. From Lemma C.3, we know that there is an estimator P( 1) such that P(YY 1) P(Y 1) Op(m" (AA1/2)), i.e. it has enough precision. We use that estimator.
Next, see that
Vn (fu. - -u,e)= =
-v
Us
((x==1)
-p(Y=1)
P(Y=1) vn
Ü; -RY=I)
-Y=1) Uz)
F(Y=D) vn
( -Us) AV= ni Us u.
F(V-1) va
( [G-UU)) U.) U.Vi
[[|==) RV=IT)
(Ú: - Us) + Usvn (p(Y 1) - P(Y = =1)) ( ) + top (m 1/2)
F(V=)) Vn
1 vn
0 - -U) +op (1)
Finally, we prove the asymptotic distribution of VT(fuue uu,e Fu.e). The result for the lower bound can be obtained analogously. From the facts stated above, we know that
P(h(X) = 1) 1)+ P -)(()) 1) =1]]
= =[p(h(X)= = 1) -X IP(Y = =1)]
= =Op(m- (0M1/1())//2))
-(A11/2))
19

---

Then.
vn
F
Fuis)
= V
20,
())M())=))+P(X +
[)) VT
Ü0g [P(h(X)-1) (1- U2)
-1)
1)(+())1)++( -1]] vn (Ue -e)) + (((())=))+((==) Vn (2U, (((x0=1)++(011)1100
+ 2U:
P) Vi
[0 UUe + 2U [(((X)=1))P((=II) +R
[X v (Ü:- Us} +
2Unn' [i(h((X 1) + P(YY 1)] (P(((X) = P(Y 11]) (F(C)=))))Y=))))) + 4op (m-
[PIX()=1)+P[=II] ni (U -Us) + op (1) (N,
where all the steps are justified as before.
C.1 Auxiliary lemmas
Lemma C.1. Define
Tu, a Su,c(e,z,a) Evez (xx)) 2
Then
inf aERDII
(x)
inf Ej (X, Z, a.)
aeA
Proof. First, see that
Elf (X, Z,a)] Elfu,e (X, Z,a)]
From Assumption 2.2, we know that there exists some " R >1x| 2|
such that
inf (X, Z,))] Effu.e (X, Z, o.
aeA
For that specific ay,e, we have that
Effa, 2, = Z, ax,e)]
Consequently,
inf GERISIXIZI xIzI
(X, Elfu, Z, Blfus (X, Z, a) inf B[fu,e(X, a,))
aEA
Lemma C.2. The function of a given by Bifu,s (X, Z, a)) has positive definite Hessian, i.e.
He(a) = V.EL 2.))] 0
and, consequently, it is strictly convex.
Proof. See that
H²(a) V.Blsa. 2.a)] + V2 Evez (Eyer
20

---

We start computing the first term in the sum.
First, for arbitrary pair (k, 1) y 2, define
glw.k.1)
Skd (x)
exp
a12.x.11-0.
My exp
Now, see that
Jasi fu. (,, = 1(0(2) sm((x) -P(
-_
IP(Y = 1 -12=0) =
and
82 Dapt Do (1, - (1(()) ((s))))o(o)) - on (z) (ul)))))
See that diagonal.
DaphDaci (u, 2, = 0 if + I. Consequently, the Hessian Va fune (2t, 2, a) is block
Consequently, because the second derivatives are bounded, push them inside the expectations and get
02 dagedasl
E
[fue (X, Z.a)]
E
dagidaui fune (X, Z, ai]
E [1)) (Z) [Rk) ()))s(())))))))))))))))())))(( - (x)p
= (p) E [P(
= X)s L -1 [
Because V fu. (x, 2, a. is block diagonal, we know that the Hessian
Va [f,, a.
is block diagonal (one block for each segment a. of the vector a). Now, realize that
V Evez (Evey
is also block diagonal, with each block being matrices of ones. In this case, we also have one block for each segment a.z the vector a. Consequently, (a) is block diagonal, and it positive definite if and only if all of its blocks are positive definite. Let us analyse arbitrary block of H, (a), e.g.,
V2 E (X, a)) Let (.)( be the vector composed of (z) for all k. If E R2 denotes vector of ones, then,
V2, Fu. fu.e (X, Z, a)]
= diag
E. [PZ = =1 |x)ss(()) [P = (X),(x) 11T
E
PP(Z = 1| x) diag (sxg)s)(X))) - -x)(sss((X)) F
E PP( =1 1 x) (s. - (.)ssss + in
where i V PT 1. See that diag (sag(s.((z))) has rank | (full rank) while s., (x))..(((=)) is rank one for every x. E Rdxx Consequently, the rank of the difference
((x) (s)g)s)(xx) (z)).(((T
21

---

is greater or equal [ 1. It is the case that rank (x()) = |>> because is in the null space of D:
D(+) = (dig(s.((z)) (.(()), 1 F(iz (s.(()) - -.((x)) 0
Moreover, the range of (x)) and i1 are orthogonal. For any two vectors v, E R we have that (D(z)v) T(ii" u) = v "f=""""
TTol T u
That implies D(x) i1 is full rank. To see that, let RD be arbitrary and (D(z) + 1i v = 0= D(rvv = v =
Because (v=)v= means that f1 for some constant 0. If o O. then =0>'i o. Therefore, and v = O.
Now, let E R be arbitrary non-null vector and see
u D u u diag(s:(z))u u (z))
Ey uysssa( (y ()su(z))
(In up u(su((a)) - (Em((()()))
=
Ev (s((()) (En (1(ss(()) /ugsu(())) (En uysu(x))
2 (o((t)))) (Ey =0
by the Cauchy-Schwarz inequality. Then, D(x) is positive semidefinite, and because i1 is also positive semidefinite, their sum needs to be positive definite for all (that matrix is full rank). Each block of Hg (a) is positive definite; consequently, He is positive definite.
Lemma C.3, Assume Assumption 2.4 holds. Let
P(YY 1) 1 E Y Z Z,]
Then
-) 11 1) = 1:(m000((mppppppp (AA1/2))
Proof. To derive this result, see that
IP = 1) P(Y = 1)
Σ 12 Y == [1] - P(Y = 1)+ L ETh
E By 12
Y 2 2] - Epy 2 |Y| 2 = 21|
< 1 Σ Ep [Y] = Z,] -PYY 1)] + + +
E 2
Y Z 2,] - -Eryz YY 2 Z,]
Or(m-1/2) + m Em P P/yz Y 1 7 7.| Prysz I 1 7 =zil
< 50p(m-13)) +>EE IP |PArz!! [Y =1 1 = IY = 1 ==]
I Op(m (00)m-1122+++ Eve(o.1) ESEZ PPyze lY = 2 == 2] -P PPPrz 1Y= y Z 21
Or(m-112) 2 dTv (Prizze: PrIZ=z
Oppmm + Op(mm
=0p(m =0p(m-(AA1/3) (2)1
where the standard central limit theorem obtains the third step, the sixth step is obtained by the formula of the total variation distance for discrete measures, and the seventh step is obtained by Assumption 2.4.
D
22

---

Lemma C.4. For some R. > O and any Y assume that K Ps S 11 K. Define A= {ay E R
Σy ay 0}. Then the optima of the following problems
a fu(a), fa(a) & E
1 b> Ey exp( e
}}
Σy Pyag
(C.3)
S fi(a), fi(a) A E log { 3J Ey exp s }}
En Pyay
are attained in a compact set (K,, L) C A where | L.
Proof of lemma C.4. We shall only prove this for the minimization problem. The conclusion for the maximization problem follows in a similar way.
Strict convexity:
The second derivation of fu is a fu(a) [ [p(X, y, (6 v(X,y.aa))
(C.4)
expl ((X12)=00)
where p(x,
For any a E R we have
ΣnEy exp
VVL = Eijey Hill, V fala)
- Eisey MayeyuuufBe Lul,BEp((,,X,... ()) ((,,,,))]]
(C.5)
- E. unp((Xi,,)) - E, u,((X,,,)) =Eloo u, a)] 2
where (2r, u, a) is the variance of categorical random variable taking the value u, with probability p(x, i, a). This leads to the conclusion that the function is convex.
To establish strict convexity, we fix E A and notice that 0 < p(x, y, < 1 (because ||9//o S L) Therefore, the (z, u, a) can be zero only when the u,'s are all equal. Since = {a E R";
Σ, by 0}. such u belongs to the space A in the unique case u, 0. This leads to the conclusion that for any u E A and +f 0
(a)
a)] > 0.
Therefore, fu is strictly convex and has a unique minimizer in A. In the remaining part of the proof, we focus on the first-order condition.
First order condition:
The first-order condition is
h(a, y) = Py for all y, where h(a, - Elp( (lp((xy.a)) v.a)]
(C.6)
To show that (C.6) has a solution in compact ball K(e, L) {a E A: ||a||2 < M(e, K, L)} we construct an (e, K. L) > such that ming h(a, y) < x whenever ||a l M(e, k. L). Since Py $ 1 - for all y this concludes that the solution to (C.6) must be inside the K(e, K, L).
Construction of the compact set: Let define Ymin A arg min,ay and Ymax & arg max, Gy. To construct M L, e) (we shall write it simply as M whenever it is convenient to do so) notice that h(,, (rmin)
Elp(X, Ymin: a)]
exp
x(x1)) "ymin
Eiey
exp
I+ta miin
exp
exp
L+aaymi
+
+1129
122 exp
(C.7)
exp 24
21 exp
+ expl <; Gymin
exp 24
exp exp(24) 24
exp 2/ texp
aymus
-aymin)
exp
21 + 2)
where
R. e min ag miny ay E. = 0, 00
Mº}
23

---

We rewrite the constraints of the optimization as:
R min { maxy dy miny ay mean(a;) = 0, var(a;} M¹2 19
where we use the Popoviciu's inequality variance to obtain
var a (max, " minn a,) or maxy miny Oy >
2M
DT
vD
Thus R 2
2M [>]
whenever ||a|| M. We use this inequality in (C.7) and obtain
exp 2t exp 2h -ex
exp 2t
h(a, Ymin) z
exp
24
texp
200 <v/2/
Finally, we choose M = ((,,,, > O large enough such that
h(a, Muuin) I
< k.
V
For such an M we concludes that h(a, Ymin) < K. whenever ||a||2 M.
Lemma C.5. LE and Ug are attained by some optimizers in a compact set Ke, E L; A ((2.2)), where Ka = min(Py)=, 1 Pyl= y E }
Proof of lemma C.5. We shall only prove the of the minimization problem. The proof for the maximization problem uses similar argument.
A decomposition of the minimization problem according to the values of Z follows.
m E log
[3] Eyey exp 2xppo(Xx..2ttrr22 }
E (ay,
P.
min
E Elelog D Evey exp( [(Xins)tary } 1
1==2 =
BBaay, I = 2)
ER Eg 9y,x=0
1 13T Eyey exp( [X 12=2 12 - Ey 1 Py.2ol=
P. Pz
min ER 9
E elog
(C.8) where P. P(Z 2) and pyl= = P(Y y = z). We fix and consider the corresponding optimization problem in the decomposition. Then according to lemma C.4 the optimal point is in a compact set ((e, c, Kz, L). Thus the optimal point of the full problem in the Cartesian product II. K(c, No. L) C A, which compact set. Thus we let K(e, Kg, E 2; L) = II. ((,c,,,,)) L).
Lemma C.6. The optimizers for the problems in (2.3) are tight with respect to m, + oc.
Proof of the lemma C.6. Let Pyl= P(Y y Z = 2) and p(m) ((m) (1)==
(v). Since
2 E,
| y/ - Pvi= = drv (prt) Pr|2==) (p
according the assumption 2.4, for sufficiently large m with high probability p(m) (p(m) 1 as m + xo) + < (m)
Fs < žेt for all y. Fix such an m and (m)) In lemma C.5 we replace Px,z
with Σm= 6x,2, and Py|z with (I)) to reach the conclusion that the optimizer is in the compact set
K(c, x E; L.. Thus, for sufficiently large m and any n
P(optimizer is in K(e,, Xz/2,2 2: L.) 2 p(m).
This establishes that the optimizers are tight.
24

---

D Proof of extra results
Proof of Theorem 5.1. We only prove the theorem for upper Fréchet bound. The proof of lower bound similar.
First, notice that
(1, 2, - Su,ela, 2,
=elog
[ Evey exp
exp
g(z.g.2)+ays
E 2 = =]
E log
1 Eyey exp
tla.
+ +Byiz lays Z = 2]
[D]]
Epy 2 Jay= = 2]
Erriz lar= ==
and thus
(2, 2, - Su,c(1, a,)
(D.1)
PEprz lays Z = =| (errzzaay Z x||
(D.2)
|lallo 2drv (Qriz==: Priz=z) 2|1a|laad..
(using a Tb s |||||=>||||]
(D.3)
(by assumption)
(D.4)
Defining
at e arg Blf (X, 2, a)), à A (x, a)]
(D.5)
we now establish that
Ü. U.I S 26 max([ l|āllc))
(D.6)
This is easily established from the following arguments:
U. El (X, ū,
El (X, Z, a,a*]
(á is the minimizer)
(D.7)
< El (X, Z, a*)] + 1la00
(using eq. (D.4)
U. + 2| 1006
and similarly
U. (X, R[So,. & SXj, 2,)) + 2|] = Ü. +2(aa 11
(D.8)
By assumption, a" and à are bounded. Thus, we can find C >> 0, which is independent of 6 > 0.
such that
max((1aa [[ā])o)) s C
and the theorem holds for this C.
Proof of Theorem 5.2. For clarity, we shall assume X a continuous random variable this proof, though this is not strictly needed.
25

---

Let Qx.y.2 and Q X,Y be two distributions in II, i.e, with marginals Px,z and Py,z. Let the densities of Qx X and Q 9x,Y and (2) 9x Then, that
|s gdQxxx gdQ x,Y
5 v.s g(x, 2) 21x v, 9x.xX 2) dr
(2)
$ I v. 10 v, 2) -xx. y,
(2,
(x, y, 2) dr
2 P2
(z (2.
rzz (2, y 2)/dr
11ll
E
(Tv(Q (x.12)
2lllll
E
d Px z2)2))
+E dlv (0 -x
(D.9)
<
Illll
E
X Priz)
+ 2 V2KL 1
(D.10)
s 2 Do
L |KI10 X PxIz Pr1Z)]
+ 2 x1.11 (r12)
(D.11)
- 2 lo
(
2)++ ( V H 2)}
(D.12)
$ 81l11 H(XI Z)
where step D.9 is justified by triangle inequality, step D.10 is justified by Pinsker's inequality, step D.11 is justified by Jensen's 's inequality, and step 12 is justified by the fact that both expected KL terms conditional mutual information terms, which can be bounded by the conditional entropy.
Following the same idea, we can show that gd gd I V811912 H(Y 2). Consequently.
1 S min (VSIlole H(X 2), 8891 H(Y 2)
8 Illl min (H(X) Z), H(Y Z))
Because this statement is valid for any distributions @ and (2) X,YY in II, we have that
U L S 1 11g1l min (H(X HY 2))
26

---

E Model selection using performance bounds
In this section, we propose and empirically evaluate three strategies for model selection using our estimated bounds in Equation 2.3.
E.0.1 Introducing model selection strategies
Assume, for example, g(z, y, 2) 1 [[((x)) y] for given classifier h, i.e., we conduct model selection based on accuracy, even though we can easily extend the same idea to different choices of metries, such as Fl score. The model selection problem consists of choosing the best model from set - (/1..... hx) } in order to maximize out-of-sample accuracy. Define (h) and (h) as the estimated accuracy lower and upper bounds for certain model h. The first strategy is to choose the model with highest accuracy lower bound, i.e.,
h Jower arg max,, hy EHH Le (hx)
Maximizing the accuracy lower bound approximates the distributionally robust optimization (DRO) [9] solution when the uncertainty set is given by II in 1.1. That is, optimize for the worst-case distribution in the uncertainty set. Analogously, we can choose the model that optimizes the best-case
scenario
Hppper = arg max (be))
Moreover, if we want to guarantee that both worst and best-case scenarios are not bad, we can optimize the average of upper and lower bounds, i.e.,
(he) (ba)
hav arg EH
E.0.2 Experiment setup
In this experiment, we select multilayer-errceprroom (MLPs). The considered MLPs have one hidden layer with a possible number of neurons in (50, 100). Training is carried out with Adam [26], with possible learning rates in f.1,.00% } and weight decay (l2 regularization parameter) in f.1, .001), 3. For those datasets that the Fl score the evaluation metric, also tune the classification threshold in {.2, .,, .5, .6, .8} (otherwise, they return the most probable class as a prediction). In total, H is composed of 8 trained models when evaluating accuracy and 40 models when evaluating the FI score. We also consider directly using the label model (Snorkel [47]) to select models. For example, when the metric considered is accuracy, i.e, we use
Tabel model arg max En By (X)((X Y Z -Z],
which is a natural choice when X 11 Y Z. As benchmarks, we consider having a few labeled samples.
In Table 3, we report the average test scores of the chosen models over repetitions for different random seeds (standard deviation report as subscript). The main message here is that, for those datasets in which our uncertainty about the score (given by the different upper and lower bounds) is small, e.g., ""commercial" and "tennis", using approaches leads to much better results when compared to using small sample sizes.
Now, we explore a different way of comparing models. Instead of making an explicit model selection, this experiment uses the proposed metrics, i.e, accuracy lower/upper bounds, bounds average, to rank MLP classifiers. We rank the models using both the test set accuracy/F1 score (depending on Zhang et al. [63]) and alternative metrics, i.e., accuracy/F1 score lower/upper bounds, bounds average, label model, and small labeled sample sizes. Then, we calculate a Pearson correlation between rankings and display numbers in Table 4. If the numbers are higher, means that the proposed selection method is capable of distinguishing good from bad models. Table 4 shows that the bounds average and label model methods usually return the best results when no labels are used. Moreover, in some cases using a small labeled sample for model selection can relatively hurt performance (when the validation set is small, there is a chance all models will have the same or similar performances, leading to smaller null rank correlations).
27

---

Table 3: Performance of selected models
metric
Lower bound
Upper hound
Bounds avg
Label model
Laheled (n = 10)
Labeled (v 25)
Laheled (n 50)
Labeled (n = 100)
agnews
BCC
0.77=0.00
0.78
0.78
0. 0.77
0.75=0002
0.75ga.02
0.75.0.00
0.77g0.00
trec
ucc
0.27
0.29
0.20
0.20
0.28g0.02
0.28
0.28ga.02
0.28
semeval
0.32
0:26
0.32
0.32
0.30=o.02
2.20
0.31
=.31
chemprot
acc
0.40
2.38
0.40
0. g..00
0.40=z.01
2.40
0.:40
0.39
youtube
acc
20.02
0.84
4.87
D. g0.02
0.90_z.02
0.90
0.900
0.91 2.91
imdl
0.7200.00
2.04
2.73
0. 1..30
0.69_...5
0.70
0.73
0.72
yelp
0.81 0.81
2.
0.00
0.81 10.00
0.81
g.8
0.81
0.82
consus
F1
0. 0.4920.00
0.18
0.4920.00
O. 19.00
0.49_0.00
0. 0.4920.00
0.49
0.50
tennis
Fl
0. 76
0.76g0.01
0.70
0. 75.000
0.71
0.7 0.71
0.71
0.71
Fl
0.00
0.14g0.02
0.14g0.02
O. 0..02
0.00=0000
0.00
0.00
0.00
edr
F1
0.48
2.20
0.48
D. 0.48
0.47=0000
0.47
0.47=00.0
0,47=0.00
basketball
F1
D. 0.16
0.27
0.26
0.17 0.17
0.20
0.17
0.16
0.16
spouse
0.27
g0.01
4.20
40.01
0.00_a.00
0.00
0.00.0.00
0.10
commercial
F1
0.96_...0
0006
0.96
0.96
0.90
0.90
01.1 =0.01
0.91
Table 4: Ranking correlation when ranking using test set and alternative metric
metric
I Lower bound
Upper hound
Bounds avg
Label model Labeled (n
Labeled 25)
Laheled
Labeled (n 100)
agnews
0..1
0.86
0.86g0000
0.92
0.39_o..
0.35
0.50
0.76
tree
acc
-0.32
2..3
0.19
0. 0.44
-0.03
- -0.06
-0.10.0.34
0.17
semeval
acc
0.87
-08440004
0.88
D. 0.88
0.13
0.17
0.64g0.a2
0.62
chemprot
0.75 20.0s
0.66
0.38
O. 1.41
-0.0120.47
0..12...4
-0.02.0.43
0.06
youtuhe
0.28
0.42
0.01 20.2:
0.1 0.17
0.41_o.35
0.42g0.27
01.88
0.58
imdb acc
0.76
0.71
0.92
0.17_0.40
0.40gu.46
(161
0.65
yclp
aec
0.01 us
0.50
g0
0.31 0..1 10.10
0.08_..0
gv.33
0.14
0.45
F1
0.85 0.94g0.00
0.
g.98
0.00_0.00
g.00
0.03
0.18
tennis
Fl
0.83_2.02
0.74g0.03
0.80
0, 0.90
0.33_
0. 0.4
0.51
0.52
sms
Fl
0.00
0.90
0.90
1.00ga.00
0.00_.0.0
0.00 0.00
0.00g0.00
0.00
0.80
0.80g0.00
0.02
0. a..8
0.03_0.08
0.07 #0.11
0.07=0.11
0.09
busketball
F1
0.85
2.60
0.73
+0.0
0.35
0.53
0.59
0.59
spouse
F1
0.50
0.86
0.8640.00
1.00
0.00_o.00
0.00
(1.00
0.10
commercial
F1
0.00
0.96
0.99
1.00
0.14_o.13
0.26
(1.28
0.31 0.31
F
More on experiments
F1
Extra results for the Wrench experiment
Extra results for binary classification datasets can be found in Figures 4 and 5. In Table can the results for multinomial classification datasets.
28

---

youtube
imdo
cdr
commercial
tennis
1.0
1.0
1.0
1.0
Oracle
ancuracy
accuracy
0.5
0.5
0.5
< 0.5
0.5
0.0
threshold
threshold
threshold
threshold
threshold
1.0
1.0
1.0
1.0
1.0
Snorkel
accuracy
accuracy
0.5
4
0.5
0.0
0.0
0.0
0.0
0.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5 threshold
1.0
threshold
threshold
threshold
threshold
SlyingSquid
1.0
1.0
accurapy
accuraty
0.5
0.5
0.5
4 0.5
4
0.5
0.0
threshold
threshold
threshold
threshold
threshold
lower bound
ubDer bound
test sccuregyif'
Figure 4: Bounds on classifier accuracies across classification thresholds for the Wrench datasets. Despite potential misspecification Snorkel's and FlyingSquid's label model, it performs comparably using labels estimate Pr|z. giving approximate hut meaningful bounds.
yelp
SMS
basketbal
spouse
census
Oracle
1.0
0.0
0.5 threshold
1.0
0.0
025
threshold
threshold
thresho
threshold
Snarkel
47
0.5
0.0
0.5
FlyingSquid
1.0
1.0
1.0
1.0
3.0
w. 0.5
0.5
0.5
0.5
0.0
0.0
0.00
0.0
Chreshold
Figure 5: Bounds classifier accuracies and Fl scores across classification thresholds for the Wrench datasets (using the full of weak labels). Despite potential misspecification in Snorkel's and FlyingSquid's ' label model, performs comparably using labels to estimate Py|z, giving approximate but meaningful bounds.
F.2 Extra plots for the hate speech detection experiment
In Table 6, we can see the same results already the main text plus the results for FlyingSquid.
G Computing resources
All experiments conducted using virtual machine with 32 cores. The experiments not computationally intensive and everything can be run within a few hours.
29

---

Table 5: Bounding the accuracy of classifiers in multinomial classification
Dataset
Label model
Lower bound
Upper bound
Test accuracy
agnews
Oracle
0.46g0.01
0.95ga.01
0.80+0.01
Snorkel
0.42g0.01
0.9g0.01
0.76
PlyingSquid
0.1220.0
0.61
0.76
Oracle
0.34
0.83g0.08
0.68
tree
Snorkel
2..1
0.70
0.47=0.04
FlyingSquid
0.07
2.292
0.2740.04
semeval
Oracle
g.54
0.78
0.7240.04
Snorkel
g.36
0.70
0.56_o.0s
FlyingSquid
0.12
0.14
0.32
chemprot
Oracle
0.43
0.75+0.02
0.60+0.02
Snorkel
0.37
0.782a.c2
0.49
FlyingSquid
0.05
0.23
0.46g0.02
1.0
1.0
Oracle
recall
precision
0.5
0.0 0.0
1.0
threshold
threshold
Snarkel
precision
recall
0.5
0.0
0.0
0.0
0.5
1.0
0.0
0.5
threshold
threshold
HyingSquid recall
1.0
0.5 predision
0.5
0.0
0.0
0.0
0.5
1.0
0.0
0.5
1.0
threshold
threshold
lower bound
upper bound
test recall/prcctsion
Figure 6: Precision and recall bounds for hate speech detection. These plots guide practitioners to trade off recall and precision absence of high-quality labels.
G.1 Examples of prompts used in Section 4.2
Prompt
You should classify the target sentence as "spam" " or "ham" If definitions examples are introduced, you should consider them when classifying sentences. Respond with "spam" " or "ham"
Target sentence: if your like drones, plz subscribe to Kamal Tayara He takes videos with his drone that are absolutely beautiful. Response:
Prompt
You should classify the target sentence as "spam" " or "ham" If definitions or examples are introduced, you should consider them when classifying sentences. Respond with "spam" or "ham". "
30

---

Definition of spam: spam is term referencing broad category of postings which abuse web-based
forms to post unsolicited advertisements comments on forums, blogs, wikis and online guestbook.
Definition of ham: texts that are not spam.
Target sentence: if your like drones, plz subscribe to Kamal Tayara. He takes videos with his drone that are absolutely beautiful. Response:
3
You should classify the target sentence as "spam" or "ham". If definitions or examples are introduced. you should consider them when classifying sentences. Respond with "spam" or "ham".
Example 0: 860, $60,000,000 lets make it first female to reach one billion Share it and replay it! Response: ham
Example 1: Waka waka eh eh Response: ham
Example 2: You guys should check out this EXTRAORDINARY website called ZONEPA. CCMP You can make money online and start working from home today as am! am making over $3,000+ per month at ZONEPA COM Visit Zonepa. and check it out! How does the mother approve the axiomatic insurance? The fear appoints the roll. When does the space prepare the historical shame? Response: spam
Example 3: Check out these Irish guys cover # Wake Me Up! Just search &quot; wake up Fiddle Me Silly&quot; Worth listen for the gorgeous fiddle player! - Response: spam
Example 4: if you want to win money at hopme click here href="https ://www verdverts com/ ref sihaam01"> https attps://www ://www paidverts com/ hom//effsihaame sihaam00 </a> it &#39; work 100/100 -- Response: spam
Target sentence: if your like drones, plz subscribe to Kamal Tayara He takes videos with his drone that are absolutely beautiful. Response:
31

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: In the abstract and Introduction section, we summarize the contributions and the scope of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals motivation long it is clear that these goals not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We have included a section to discuss limitations in the conclusion.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification,
asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play important role in developing norms that preserve the integrity of the community. Reviewers will specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each thcoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The assumptions are discussed in the statements of the theorems and the proofs are provided in the Appendix.
32

---

Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: We provide general setting of the experiments in the paper and details are provided the code itself submitted as supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (c.g., in the case of a large language model), releasing of model checkpoint, other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source source models, it may be that access to the model is limited in some way (c.g.. to registered users). but it should be possible for other researchers to have some path to reproducing or verifying the results.
Open access data and code
Question: Does the paper provide open access the data and code, with sufficient instructions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide simulation settings that are accessible and reproducible through the submitted zip file.
33

---

Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines
guides/
wet.ummmiiiiiiioccic.... for more details.
While we encourage the release code and data, we understand that this might not be possible, so "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https cctpippcccppbli//////cccc ssi quides/CodeSure ioanisssoonPon onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce experimental results for the new proposed method and basclines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) recommended, but including URLs to data and code is permitted.
Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
We do specify those parameters in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report eиror bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We provide errorbars for the plots.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the enror bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
34

---

If eтrоr bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experi- ments?
Answer:
[Yes]
Justification:
We include a section the appendix about this.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https://neur/::: cc/pubbic//hhhcccuuulelllllll
Answer: [Yes]
Justification: Yes, we followed the NeurlPS Code of Ethics
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., ., if there a special consideration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work may have potential societal consequences, none of which we feel must be specifically highlighted here.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (c.g.. disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to par- ticular applications, let alone deployments. However, if there direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
35

---

If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g.. pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions access the model implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We make citations when needed.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged reach out the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/model as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
36

---

At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, applicable, as well as details about compensation (if any)?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Sub- jects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
37


Reviews:
[{"review_id": "QWnFchelgg", "reviewer": "Reviewer_bCgS", "summary": "The paper considers the problem of Frechet bound which is the task of determining the infimum and supremum of a function g(X,Y,Z) over the set of joint distribution with fixed marginals. Asymptotic behavior is derived when estimation of condition distribution P_{Y|z} is available with vanishing total variation error. This bound is based on a nice dual formalization of the original optimization problem.\n\nThis approach is then applied in a weak supervised learning setup to derive confidence interval for the precision and recall. Weak supervised means that cheap label is available which is the random variable Z, and the expensive target label is Y. So if one can estimate the condition probability of Y given Z, the performance guaranties can be derived for label Y which is the target label.", "questions": "1) why it is not possible to get high probability results? \n2) Regarding Theorem 2.4, if P_{Y|z} can be estimated with an error O(m^{-1/2}) in terms total variation distance (which is the optimal rate for discrete distributions), then the variance of the optimal solution of the problem based on estimates is shrinking of order with the same order? Is that right?\n3) Why it is cheaper to estimate the conditional distribution of Y given z, then to estimate the precision and recall of the model based on Y directly?", "limitations": "I think the this approach can be applied only for small label spaces. In the conclusion, the authors points out that this approach can be applied for finite set, but I believe that this approach has only merit if the label space is very small.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "I think the dual formalization of the optimization problem is nice part of the paper. I am not sure how novel it is, since the proof heavily relies on some results on previous work. The problem which is considered is relevant.", "weaknesses": "It is not clear what is the merit of the approach, see my third question. I am a little bit confused about the contribution of the paper. Estimating the precision/recall seems cheap, but estimating the conditional distribution of the true label conditioned on the proxy label might be expensive? Especially in multi-class setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer, thank you for your work on our paper. We addressed the issues you raised below. Please let us know if you have any other questions.\n\n- **Why not estimate performance metrics directly?** In fact, we work under the assumption that **no true labels** are observed, which is a realistic scenario in the programmatic weak supervision literature. Therefore, it is impossible to compute metrics such as accuracy, recall/precision, F1 score, etc. However, using the label models proposed in the weak supervision literature, it is still possible to estimate $P_{Y|Z}$ (even with no labels $Y$'s; see for example [1]). Therefore, obtaining lower and upper bounds for performance metrics (accuracy, recall/precision, F1 score) is the best that one can do; we focus on that problem. Moreover, even if some labeled samples are given, our method can enjoy superior performance in some tasks (see Section 4.2.1).\n\n- **Label space size and the method applicability**: Whether the label space needs to be small or not, really depends on the sample size you have. The key point is that the label model needs to be well estimated. This will happen (no matter the size of the label space) if the sample size is big enough for a given label model complexity (e.g., label models with fewer graph edges need fewer samples to be well estimated).\n  \n- **High probability results**: It is possible to obtain a high-probability version of Thm 2.4. We opted for the asymptotic version because we rely on it to construct confidence intervals later. Although it is possible to form confidence intervals based on finite-sample high probability bounds, the resulting intervals are typically very conservative. This is why we opted for asymptotic results.\n\n- **Variance of the estimates**: Yes, that is correct. At a high level, there are two main error terms in ${\\\\widehat{L}}\\_{\\\\epsilon}$ and $\\\\widehat{U}\\_\\\\epsilon$: an $O\\_P(n^{-1/2})$-term and an $O\\_P(m^{-\\\\lambda})$ term. In Thm 2.4, we assume $n = o(m^{2\\\\lambda})$, which implies the $O\\_P(m^{-\\lambda})$ error term is asymptotically negligible. This simplifies the theorem because it allows us to state its conclusions solely in terms of $n$. In your scenario, $\\lambda = \\frac12$ so the two error terms vanish at the same square-root rate.\n\n**References**\n\n[1] Alex Ratner, Braden Hancock, Jared Dunnmon, Roger Goldman, and Christopher Ré. Snorkel metal: Weak supervision for multi-task learning. In Proceedings of the Second Workshop on Data Management for End-To-End Machine Learning, pages 1–4, 2018.", "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": "", "extra_scores": {}}, {"review_id": "Z8hWXezYt3", "reviewer": "Reviewer_MRE8", "summary": "Programmatic weak supervision is a machine learning approach where labeled training data is generated using heuristic rules, domain-specific functions, or other programmatic methods, rather than manual annotation. This technique allows for the creation of large training datasets quickly and cost-effectively by leveraging expert knowledge and automated processes. Uncertainty in programmatic weak supervision arises from the noisiness and variability of labels generated by heuristic rules, domain-specific functions, or automated methods. Unlike manually annotated datasets, programmatically generated labels often contain errors and inconsistencies due to imperfect heuristics that may not accurately capture the true patterns. The paper prososes techniques that estimate Fréchet bounds to validate the performance of programmatic weak supervision models. The proposed algorithms estimate upper and lower bounds for multiple metrics.", "questions": "See Weaknesses Section.", "limitations": "The authors describe limitations in the paper.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "The algorithm developed in this work has solid theoretical justification, which reinforces its validity and applicability. Additionally, the presented theory is very interesting and makes a significant contribution to the field.\n\nProposing upper and lower bounds for this framework is very useful and interesting, as well as novel.", "weaknesses": "Not explaining the problem along with the state-of-the-art issues in the introduction makes it difficult to understand the contributions and the objective of the paper.\n\nI believe the paper could be written more clearly; currently, it is difficult to follow.\n\nAs the authors mention, the labels could be obtained using a label model. If from Section 2.2 onwards a label model is not proposed, but instead the work deals with a dataset where some labels may be incorrect, why not directly state that this is a supervised classification framework with noisy labels instead of PWS?\n\nTheorem 2.4 is not easy to interpret.\n\nThe quality of Figure 1 can be improved, and this figure needs more explanation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer, thank you for your dedication to our paper. We realized that the main issues you raised are related to clarity and presentation. We revised the main parts you brought up and are willing to further improve other parts depending on your feedback. Please let us know if you have more issues/questions.\n\n### **PWS over noisy labels approaches**\n\nOur method could be potentially applied to noisy label applications as well if $P\\_{Y|Z}$ can be estimated without the conditional independence assumption that $Y$ is independent of $X$ given $Z$. However, we are not aware of any paper that proposes such a method in the noisy labels literature. If the reviewer has any suggestions, we would be happy to include a note in our paper about this.\n\n### **Interpretation of Theorem 2.4**\n\nThanks for the feedback. We have added the following sentences right after the theorem statement to make the interpretation clear:\n\n> Theorem 2.4 tells us that, if the label model is consistent (Assumption 2.3), under some mild regularity conditions (Assumption 2.2), our estimators $\\hat{L}\\_\\varepsilon$ and $\\hat{U}_\\varepsilon$ will be asymptotically Gaussian with means $L\\_\\varepsilon$ and $U\\_\\varepsilon$ and variances $\\sigma^2\\_{l,\\varepsilon}/n$ and $\\sigma^2\\_{u,\\varepsilon}/n$. That is, the estimates will be close to $L\\_\\varepsilon$ and $U\\_\\varepsilon$ up to a Gaussian estimation error with a standard deviation of order $\\mathcal{O}\\_P(1/\\sqrt{n})$.\n\n### **Figure 1**\nThanks for the feedback.  We have added the following sentence as the caption of Figure 1 (and a slightly different version of it to the main text) to make its interpretation clear:\n\n> We apply our method to bound test metrics such as accuracy and F1 score (in green) when no true labels are used to estimate performance. In the first row (\"Oracle\"), we use true labels to estimate the conditional distribution $P_{Y\\mid Z}$, thus approximating a scenario in which the label model is reasonably specified. On the second row (\"Snorkel\"), we use a label model to estimate $P_{Y\\mid Z}$ without access to any true labels. Despite potential misspecification in Snorkel's label model, it performs comparably to using labels to estimate $P_{Y\\mid Z}$, giving approximate but meaningful bounds.\n  \nRegarding quality, we will work on the quality of Figure 1 by making it larger and with better resolution (let us know if there is any other issue with that figure that we will be happy to solve).\n\n\n\n### **Introduction**\n\nThank you for your feedback. We have revised the introduction to make it clearer:\n\n> Programmatic weak supervision (PWS) is a modern learning paradigm that allows practitioners to train their supervised models without the immediate need for clean labels $Y$ [37, 35, 34, 36, 43, 47]. In PWS, practitioners first acquire cheap and abundant weak labels $Z$ through heuristics, crowdsourcing, external APIs, and pretrained models, which serve as proxies for $Y$. Then, the practitioner fits a *label model*, i.e., a graphical model for $P\\_{Y,Z}$ [37, 36, 17, 12], which, under appropriate modeling assumptions, can be fitted without requiring $Y$'s. Finally, a predictor $h:\\mathcal{X}\\to\\mathcal{Y}$ is trained using a *noise-aware loss* constructed using this fitted label model [37]. Using weak labels for prediction is usually not possible because they are not observed during test time; thus training a final classifier $h$ that depends only on features $X$ is needed.\n\n> One major unsolved issue with the weak supervision approach is that even if we knew $P\\_{Y, Z}$, the risk $R(h)=\\mathbb{E}[\\ell(h(X), Y)]$ or any other metrics such as accuracy/recall/precision/$F\\_1$ score are not identifiable (not uniquely specified) because the joint distribution $P\\_{X,Y}$ is unknown while the marginals $P\\_{X, Z}$ and $P\\_{Y, Z}$ are known or can be approximated. As a consequence, any performance metric based on $h$ cannot be estimated without making extra strong assumptions, e.g., $X$ is independent of $Y$ given $Z$, or assuming the availability of some labeled samples. Unfortunately, these conditions are unlikely to arise in many situations. A recent work, Zhu et al [48] , investigated the role and importance of clean labels on model evaluation in the weak supervision literature. They determined that, under the current situation, the *good performance and applicability of weakly supervised classifiers heavily rely on the presence of at least some high-quality labels, which undermines the purpose of using weak supervision* since models can be directly fine-tuned on those labels and achieve similar performance. Therefore, in this work, we develop new evaluation methods that can be used without any clean labels and show that the performance of weakly supervised models can be accurately estimated in many cases, even permitting successful model selection. Our solution relies on estimating Fréchet bounds, explained below, for bounding performance metrics such as accuracy, precision, recall, and $F\\_1$ score of classifiers trained with weak supervision.\n\n> **Fréchet bounds** Consider a random vector $(X,Y,Z)\\in \\mathcal{X}\\times\\mathcal{Y}\\times\\mathcal{Z}$ is drawn from an unknown distribution $P$. *We will add more information about Fréchet bounds here (omitted due to lack of space).*\n\n>**Contributions** In summary, our main contributions are:\n>1. Developing a practical algorithm for estimating the Fréchet bounds in Equation (1). Our algorithm can be summarized as solving convex programs and is scalable to high-dimensional distributions.\n>2. Quantifying the uncertainty in the computed bounds due to uncertainty in the prescribed marginals by deriving the asymptotic distribution for our estimators.\n>3. Applying our method to bounding the accuracy, precision, recall, and $F_1$ score of classifiers trained with weak supervision. This enables practitioners to evaluate classifiers in weak supervision settings \\textit{without access to labels}.", "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": "", "extra_scores": {}}, {"review_id": "geLSTxkHw6", "reviewer": "Reviewer_zvj9", "summary": "The authors propose a method for bounding the performance of models obtained using weak-supervision, without the need for a gold-standard label set. The proposed approach starts with Frechet bounds, and casts them as dual optimization problems. From there, the dual optimization problems are relaxed to a smooth functions which can be solved using L-BFGS or similar methods. Finally, the authors explore the performance and utility of the proposed method on several empirical datasets. The evaluation demonstrates a non-trivial ability to bound performance without gold-standard labels and to perform model selection from a small set of models.", "questions": "No additional questions.", "limitations": "The authors have addresses the limitations of the work.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The authors attack a thorny weakness in the weak-supervision literature; the need for a gold-standard dataset. This need has been present going back to the seminal work by Ratner et al. and undermines the approach. It also addresses model evaluation, which is arguably a more important and difficult problem than model training. After all, it's not a real surprise that heuristics could be cobbled together to produce a model. But, quantifying exactly how good that model might be without direct access to labels is another story.", "weaknesses": "The paper is somewhat technical and difficult to follow in places. For example, I stared at Thm 2.1 for some time before realizing that Appendix C existed. The writing could be improved by noting connections to the appendices in the main body of the text, where appropriate. In addition, noting the primary tool(s) used to get each result would help the reader intuit the type of machinery being leveraged. \n\nFinally, the experiments show some utility of the method. Could the authors give an opinion on the applications or circumstances in which this method could be used for real-world problems? Do we need confidence that the label model is correct? How many weak labels do we need? etc. Appendix A.2 goes some way to helping here. Again, it would be great to mention that this content exists in the main text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer, thank you for your work on our paper. We addressed the issues you raised below. Please let us know if you have any questions.\n\n- **Clarity and appendix material**: Thanks for your suggestion. We will revise to reference the appendix where appropriate and give some ideas on the basic tools used to obtain the results.\n\n- **Applications or circumstances in which this method could be used for real-world problems**: We will provide additional details on this point in the conclusion section. In summary, applications primarily focus on performance estimation and model selection, particularly in areas such as image or text classification, as demonstrated in the experiments section. Additionally, the label model does not need to be perfect to offer useful bounds, as evidenced in the experiments, where we compare a very simple label model (e.g., Snorkel) vs the oracle estimation of $P\\_{Y|Z}$. Concerning the number of weak labels, Appendix A.2 indeed provides results that help determine when we have a sufficient quantity of weak labels and their level of informativeness.", "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": "", "extra_scores": {}}, {"review_id": "5mPaYLDULl", "reviewer": "Reviewer_R1rQ", "summary": "This paper proposes solutions via convex programs to estimate Frechet bounds for Programmatic Weak Supervision (PWS). This approach uses estimates of the true labels via labelmodels (i.e., different aggregation schemes that exist in the literature). With these estimates of the labels, they provide an approach to estimate bounds on the accuracy (and other quantities) of the weak labelers. They provide experiments to check the validity of their bounds and also provide experiments with weak labelers generated via prompting to examine how their bounds perform under instances of weak labelers with different qualities/accuracies.", "questions": "1. Do you have any intuitions about settings where the usage of your method for label set selection is well-motivated? \n2. There's also a line of work in PWS that looks to train end models directly [1, 2, 3]. Can the bounds of this work be applied directly to these models to analyze their error rates? This added discussion would be interesting to broaden the applicability of this theoretical framework.\n\n[1] Sam, et. al. Losses over Labels: Weakly Supervised Learning via Direct Loss Construction.\n\n[2] Cachay, et. al. End-to-End Weak Supervision.\n\n[3] Yu, et. al. Fine-Tuning Pre-trained Language Model with Weak Supervision: A Contrastive-Regularized Self-Training Approach.", "limitations": "Yes, limitations have been adequately addressed.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The strengths of this paper are that it analysis the PWS setup from a theoretical perspective, tackling the problem of analysis the performance of individual weak labelers. \n\n1. The authors provide a nice analysis of their estimation scheme.\n2. They derive the asymptotic distributions of their estimators and show they are consistent.\n3. They also provide CI for their estimates given finite sample data.\n4. A novel application of Frechet bounds (and the corresponding literature) to the field of programmatic weak supervision.", "weaknesses": "My only substantiative concern with this paper is that its applicability to the task of label set selection is weirdly motivated. Given a correctly specified label model and a better than random weak labeler (which is exactly the setting that where this method achieves valid bounds), then there is no need to prune away worse-performing weak labelers as they are helpful for the labelmodel. I agree that removing these low-accuracy weak labelers can be helpful given misspecification or a violation of assumptions, but in the setting where this paper achieves valid bounds, then I believe there is no need for this pruning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer, thank you for your dedication to our paper. We addressed the issues you raised below. Please let us know if you have any other questions.\n\n- **Regarding weak label pruning:** Thank you for raising this point. In the following, we explain our point of view, which we will make clearer in the main text. Pruning not-so-informative weak labels (even though they carry some signal) could be beneficial in practical situations. This is true for at least one reason (besides the one you mentioned): the number of parameters in the label model can increase exponentially fast with the number of weak labels, making estimation very hard (convergence rates are slow in parametric inference when the number of parameters is big, for example). As a consequence, having too many weak labels that are not very informative can lead to problems analogous to overfitting if the data is not big enough.\n\n- **Applications with end-to-end weak supervision methods:** Our method works with all of these methods given that we can fit a label model (e.g., Snorkel) separately and apply it just to the evaluation step. Thank you for your comment. We will write this observation in our main text and cite the papers you suggested.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This work resolves a practically relevant problem, that of estimating performance of ML models in face of low quality data or no gold-standard groundtruth data, in the setting of programmatic weak supervision. The work is relevant, novel, has a solid theoretical justification, and the presented theory makes a significant contribution to the field, and the work may even be applicable to other novel settings. Both upper and lower bounds are provided aiding the practicality of the approach. For these reasons, we believe this work is interesting and relevant to the NeurIPS community, and therefore I recommend acceptance.
Decision: Accept (poster)