Weak Supervision Performance Evaluation via Partial Identification

Authors: felipe maia polo
subha  maity
mikhail  yurochkin
moulinath  banerjee
yuekai  sun
felipe  maia
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 08:52:51

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.

Main paper: 
 introduction: 
 Programmatic weak supervision (PWS) is a 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 a label model, i.e., a graphical model for P Y,Z [50, 49, 22, 17] , which, under appropriate modeling assumptions, can be fitted without requiring Y 's. Finally, a predictor h : X → Y is trained using samples (X i , Z i )'s and a 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 P Y,Z , evaluation metrics such as accuracy, recall, precision, or F 1 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 P X,Y through the marginals P X,Z and P Y,Z . As a consequence, any performance metric based on h cannot be estimated without making extra strong assumptions, e.g., X ⊥ ⊥ Y | Z. Unfortunately, these conditions are unlikely to arise in 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, 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 as accuracy, precision, recall, and F 1 score of classifiers trained with weak supervision.Fréchet bounds: Consider a random vector (X, Y, Z) ∈ X × Y × Z is drawn from an unknown distribution P . We assume X ⊂ R d is arbitrary while Y and Z are finite. In this work, we develop and analyze the statistical properties of a method for estimating Fréchet bounds [53, 54] of the formL ≜ inf π∈Π E π [g(X, Y, Z)] and U ≜ sup π∈Π E π [g(X, Y, Z)] (1.1)when g is a fixed bounded function, with Π being the set of distributions π for (X, Y, Z) such that the marginal π X,Z (resp. π Y,Z ) is identical to the prescribed marginal P X,Z (resp. P Y,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., see 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(x, y, z) = 1[h(x) = y] in (1.1) . At a high level, our method replaces P Y,Z with the fitted label model, and P X,Z with its empirical version in the Fréchet bounds in (1.1), and reformulates the problem in terms of a 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-dimensional 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 F 1 score of classifiers trained with weak supervision. This enables practitioners to evaluate classifiers in weak supervision settings without access to ground truth labels.Weak supervision: With the emergence of data-hungry 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-entity recognition [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.A relevant line of research within the realm of weak supervision that is closely related to 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 a good label model. In their work, the authors use a 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 we are interested in the worst and best-case scenarios over a 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 a set of potential values for the parameters of interest (usually given by non-trivial bounds) and has been frequently considered in many areas such as microeconometrics [38] [39] [40] 43] , causal inference [25, 23] , algorithmic fairness [20, 46] . Our work is most related to 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 is 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 in a setup that is realized in numerous weak-supervision applications.We write E Q and Var Q for the expectation and variance of statistics computed using i.i.d. copies of a random vector W ∼ Q. Consequently, P Q (A) = E Q 1 A ,a m = o(b m ) is equivalent to a m /b m → 0 as m → ∞ and a m = b m + o(1) means a m -b m = o(1). If (V (m) ) m∈N is a sequence of random variables, then (i) V (m) = o P (1) means that for every ε > 0 we have P(|V (m) | > ε) → 0 as m → ∞, (ii) V (m) = O P (1) means that for every ε > 0 there exists a M > 0 such that sup m∈N P(|V (m) | > M ) < ε, (iii) V (m) = a m + o P (1) means V (m) -a m = o P (1), (iv) V (m) = o P (a m ) means V (m) /a m = o P (1), and (v) V (m) = O P (a m ) means V (m) /a m = O P (1). 
estimating fréchet bounds: 
 A roadmap to our 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, as discussed in (2.2). Finally, we propose estimators for the smooth approximations (2.3) and derive their asymptotic distributions in Theorem 2.5.This section presents a 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 a family of matrices denoted byA ≜ a ∈ R |Y|×|Z| : y∈Y a yz = 0 for every z ∈ Z .With this definition in place, we introduce the dual formulation in Theorem 2.1. Theorem 2.1. Let g : X × Y × Z → R be a bounded measurable function. Then,L = sup a∈A E[f l (X, Z, a)] and U = inf a∈A E[f u (X, Z, a)] (2.1)wheref l (x, z, a) ≜min ȳ∈Y [g(x, ȳ, z) + a ȳz ] -E P Y |Z [a Y z |Z = z] f u (x, z, a) ≜max ȳ∈Y [g(x, ȳ, z) + a ȳz ] -E P Y |Z [a Y z |Z = z] .Moreover, L and U are attained by some optimizers in A.Theorem 2.1 remains valid if we maximize/minimize over R |Y|×|Z| instead of A. However, this is not necessary because the values of f l and f u remain identical for the following shifts in a: a •z ← a •z +b z where b z ∈ R. By constraining the set of optimizers to A, we eliminate the possibility of having multiple optimal points. The proof of Theorem 2.1 is placed in Appendix B and is inspired by ideas from Optimal Transport; see Appendix A.The computation of these bounds entails finding a minimum or maximum over a 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{b 1 , • • • , b K } ≜ -ε log[ 1 K k exp( -b k ε )], softmax{b 1 , • • • , b K } ≜ ε log[ 1 K k exp( b k ε )] ,where ε > 0 is a small constant that dictates the level of smoothness. As ε nears zero, these soft versions of max and min converge to their original non-smooth forms. Using these approximations, we reformulate our dual optimization in (2.1) into smooth optimization problems:L ε ≜ sup a∈A E[f l,ε (X, Z, a)] and U ε ≜ inf a∈A E[f u,ε (X, Z, a)] (2.2)wheref l,ε (x, z, a) ≜ -ε log 1 |Y| y∈Y exp g(x,y,z)+ayz -ε -E P Y |Z [a Y z | Z = z] f u,ε (x, z, a) ≜ ε log 1 |Y| y∈Y exp g(x,y,z)+ayz ε -E P Y |Z [a Y z | Z = z]and ε > 0 is kept fixed at an appropriate value. As a consequence of Lemma 5 of An et al. [3] , we know that L ε and U ε are no more than ε log |Y| units from L and U . Thus, that distance can be regulated by adjusting ε. For example, if we are comfortable with an approximation error of 10 -2 units when |Y| = 2, we will set ε = 10 -2 / log(2) ≈ .014.In practice, it is not usually possible to solve the optimization problems in (2.2), because we may not have direct access to the distributions P X,Z and P Y |Z . We overcome this problem by assuming that we can estimate the distributions using an available dataset.To this end, let us assume that we have a sample {(X i , Z i )} n i=1 iid ∼ P X,Z , and thus we replace the relevant expectations with P X,Z by its empirical version. Additionally, we have a sequence { P (m) Y |Z , m ∈ N} that estimates P Y |Z with greater precision as m increases. Here, m can be viewed as the size of a sample to estimate P Y |Z . 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 a label model [49, 22] in applications with weak supervision or in a variety of other ways for applications beyond weak supervision. Later in this section, we will formalize the precision required for the estimates. To simplify our notation, we omit the superscript m in P (m) Y |Z , whenever it is convenient to do so. Thus, the Fréchet bounds are estimated asLε = sup a∈A 1 n n i=1 fl,ε (X i , Z i , a) and Ûε = inf a∈A 1 n n i=1 fu,ε (X i , Z i , a) (2.3) where fl,ε (x, z, a) ≜ -ε log 1 |Y| y∈Y exp g(x,y,z)+ayz -ε -E PY |Z [a Y z | Z = z] fu,ε (x, z, a) ≜ ε log 1 |Y| y∈Y exp g(x,y,z)+ayz ε -E PY |Z [a Y z | Z = z]In our practical implementations we eliminate the constraint that y a yz = 0 for all z ∈ Z by adding a penalty term z∈Z ( y∈Y a yz ) 2 to Ûε (and its negative to Lε ) and then solve unconstrained convex programs using the L-BFGS algorithm [33] . Since the penalty term vanishes only when y a yz = 0 for all z ∈ Z, we guarantee that the optimal solution is in A.In the following, we state the assumptions required for our asymptotic analysis of Lε and Ûε . We start with some regularity assumptions. Assumption 2.2. L ε and U ε are attained by some optimizers in A (2.2). Assumption 2.3. Let â represent the optimizer for any problem in (2.3), which is assumed to exist. Suppose ∥â∥ ∞ = O P (1) as m → ∞.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 (|Y| = 2) if P(Y = y | Z = z) is bounded away from both zero and one, i.e. κ < P(Y = y | Z = z) < 1 -κ for some κ > 0 for every y ∈ Y and z ∈ Z.In our next assumption, we formalize the degree of precision for the sequence { P (m) Y |Z , m ∈ N} of estimators that we require for desired performances of the bound estimates. Assumption 2.4. Denote the total variation distance (TV) between probability measures as d TV . For every z ∈ Z, for some λ > 0, we have thatd TV P (m) Y |Z=z , P Y |Z=z = O P (m -λ ).From Ratner et al. [49] 's Theorem 2 and a Lipschitz property of the label model = o(m 2λ ) when m → ∞. Then, as m → ∞ √ n( Lε -L ε ) ⇒ N (0, σ 2 l,ε ) and √ n( Ûε -U ε ) ⇒ N (0, σ 2 u,ε )whereσ 2 l,ε ≜ Varf l,ε (X, Z, a * l,ε ), σ 2 u,ε ≜ Varf u,ε (X, Z, a * u,ε), and a * l,ε and a * u,ε are the unique optimizers to attain L ε and U ε (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 L ε and U ε and variances σ 2 l,ε /n and σ 2 u,ε /n. The above theorem requires m 2λ to grow faster than n implying that, through assumption 2.4, P Y |Z is estimated with a precision greater than the approximation error when we replace P X,Z with 1 n i δ Xi,Zi . In the case which λ = 1/2, this condition translates to n/m → 0 as n → ∞. 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 L ε can is constructed asÎ = Lε - τ γ σl,ε √ n , Lε + τ γ σl,ε √ n ,where τ γ = Φ -1 (1 -γ/2) and σl,ε is the empirical standard deviation of f l,ε (X, Z, •), substituting the estimate â (solution for the problem in 2.3). For such interval, it holds P L ε ∈ Î ≈ 1 -γ, i.e., with approximately 1 -γ confidence we can say that the true L ε is in the interval above. An interval for U ε can be constructed similarly.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 no 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, a 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 it 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 as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
evaluation of model performance in weak supervision: 
 In 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 h when no high-quality labels are available.In the standard weak supervision setup, only unlabeled data (X) is available, but the practitioner can extract weak labels (Z) from the available data. More specifically, we assume access to the dataset {(X i , Z i )} m i=1 , i.i.d. with distribution P X,Z , used in its entirety to estimate a label model PY |Z [49, 22] and where part of it, e.g., a random subset of size n, is used to estimate bounds4 . To simplify the exposition, we assume the classifier h is fixed5 .Let ℓ be a generic classification loss function. The risk of a classifier h is defined as R(h) = E[ℓ(h(X), Y )], which cannot be promptly estimated in a 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, z) = ℓ(h(x), y) to obtain bounds for R(h). Furthermore, we can estimate an uncertainty set for the accuracy of the classification simply by letting g(x, y, z) = 1[h(x) = y].For a binary classification problem, where Y = {0, 1}, the precision, recall, and F 1 score of a classifier h are defined asp ≜ P(Y = 1 | h(X) = 1) = P(h(X)=1,Y =1) P(h(X)=1) , r ≜ P(h(X) = 1 | Y = 1) = P(h(X)=1,Y =1) P(Y =1) , F ≜ 2 r -1 +p -1 = 2P(h(X)=1,Y =1) P(h(X)=1)+P(Y =1) .The quantities P(h(X) = 1) and P(Y = 1) in the above definitions are identified, since the marginals P X,Z and P Y,Z are specified in the Fréchet problem in (1.1). The P(h(X) = 1) can be estimated from the full dataset {(X i , Z i )} m i=1 simply using P(h(X) = 1)≜ 1 m m i=1 1[h(X i ) = 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 et al. [49] . Estimating or knowing P(Y = 1) is required to 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 P(Y = 1).The probability P(h(X) = 1, Y = 1), which is the final ingredient in the definition of precision, recall, and F1 score is not identifiable as P X,Y is unknown. The uncertainty bounds for this quantity can be estimated using our method simply by letting g(x, y, z) = 1[h(x) = 1 and y = 1]. Let Lε and Ûε denote the estimated lower and upper bounds for P(h(X) = 1, Y = 1) obtained using (2.3). Naturally, the lower bound estimators for precision, recall, andEQUATIONFl,ε ≜ 2 Lε P(h(X)=1)+ P(Y =1) ,while the upper bound estimators pu,ε , ru,ε , and Fu,ε are given by substituting Lε by Ûε 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. • √ n pl,ε -p l,ε ⇒ N (0, σ 2 p,l,ε ) with p l,ε = Lε P(h(X)=1) , σ 2 p,l,ε ≜ σ 2 l,ε P(h(X)=1) 2 , • √ n rl,ε -r l,ε ⇒ N (0, σ 2 r,l,ε ) with r l,ε = Lε P(Y =1) , σ 2 r,l,ε ≜ σ 2 l,ε P(Y =1) 2 , • √ n Fl,ε -F l,ε ⇒ N (0, σ 2 F,l,ε ) with F l,ε = 2Lε P(h(X)=1)+P(Y =1) & σ 2 F,l,ε ≜ 4σ 2 l,ε [P(h(X)=1)+P(Y =1)] 2 ,where L ε , σ 2 l,ε are defined in Theorem 2.5. Asymptotic distributions for √ n pu,ε -p u,ε , √ n ru,εr u,ε , and √ n Fu,ε -F u,ε are obtained in a similar way by changing L ε to U ε and σ 2 l,ε to σ 2 u,ε .Reiterating our discussion in the final paragraph in Section 2.2, asymptotic distributions are important for constructing confidence intervals for the bounds, which can be done in a similar manner.Question: For each theoretical 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.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 or 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 in 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. 
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 P Y is known (computed using the training set). Unless stated, we use l 2 -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 pregenerated weak labels for evaluating weak supervision methodologies. Most of Wrench'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] , YouTube [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, we employ the paraphrase-MiniLM-L6-v2 model from the sentence-transformers6 library for feature extraction [51] . Features were extracted for 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 to 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 paraphrase-MiniLM-L6-v2 for feature extraction.In this section, we conduct an empirical study using some of the Wrench and Hate Speech datasets to verify the validity and usefulness of our methodology. We compare results for which P Y |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 a thousand epochs. Such a comparison facilitates an evaluation of our method's efficacy, especially in cases where the label model could be incorrectly specified. Results for other Wrench datasets and one extra label model (FlyingSquid, [22] ) are presented in Appendix F. In Figure 1 , we demonstrate our approaches for bounding test metrics, such as accuracy and F1 score (shown in green), when no true labels are available to estimate performance at various classification thresholds for binary classification tasks on Wrench datasets. In the first row ("Oracle"), true labels are used to estimate the conditional distribution P Y |Z , representing a (close to) ideal scenario with a well-specified label model. In the second row ("Snorkel"), however, we use a label model to estimate P Y |Z without relying on any true labels. Despite potential inaccuracies in Snorkel's label model, it achieves results close to those obtained using true labels to estimate P Y |Z , 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 1 , results for "youtube", "commercial", and "tennis" highlight that our uncertainty about out-of-sample performance is small, even without labeled samples. However, there is a noticeable increase in uncertainty for "imdb" and "cdr", making weakly supervised models deployment riskier without 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 at .5. This is deduced from the flat worst-case and peaking best-case accuracy at this threshold. Table 1 presents some results for "agnews" (4 classes) and "semeval" (9 classes). From Table 1 , we can see that both "Oracle" and "Snorkel" approaches produce valid bounds. Now, we present bounds on the classifiers' precision and recall across different classification thresholds for the hate speech dataset. This dataset did not provide weak labels, so we needed to generate them. We employed four distinct weak labelers. The initial weak labeler functions are based on keywords and terms. Should words or phrases match those identified as hate speech in the lexicon created by Davidson et al. [13] , we categorize the sentence as 1; if not, it's designated 0. The second weak labeler is based on TextBlob's sentiment analyzer [36] : a negative text polarity results in a 1 classification, while other cases are labeled 0. Our final pair of weak labelers are language models, specifically BERT [16] and RoBERTa [34] , that have undergone fine-tuning for detecting toxic language or hate speech [35, 28] . 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 P Y |Z . Inspired by Smith et al. [59] , we craft three few-shot weak labelers by prompting 7 the large language model (LLM) Llama-2-13b-chat-hf [60] . For each dataset entry, we pose three distinct queries to the LLM. Initially, we inquire if the comment is SPAM or 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.After obtaining this triad of weak labels, we analyze two situations. Initially, we integrate the top five 8 weak labels ("high-quality" labels) from Wrench. In the subsequent scenario, we synthetically generate weak labels ("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 to a significant boost in performance.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 of our Fréchet bounds for model selection purposes. Consider a set of possible models H ≜ {h 1 , • • • , h K } 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 The progression of plots illustrates the comparative impact of integrating "high-quality" labels from Wrench versus synthetically generated "low-quality" labels. Evidently, the addition of "high-quality" labels significantly enhances the bounds, underscoring their superior utility over "low-quality" labels for optimal classification of SPAM and HAM comments.distributionally robust optimization (DRO) [9] solution when the uncertainty set is given by Π 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 E for more details.In this experiment, we select multilayer-perceptrons (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 {.1, .001} and weight decay (l 2 regularization parameter) in {.1, .001}. For those datasets that use the F1 score as the evaluation metric, we also tune the classification threshold in {.2, .4, .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 F1 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 select the modelarg max h k ∈H 1 n n i=1 E PY |Z 1[h k (X) = Y | Z = Z i ], which is a natural choice when X ⊥ ⊥ Y | Z.As baselines, we consider having a few labeled samples. In Table 2 , we report a subset of our results (please check Appendix E for the full set of results). In this table, we report the average test scores of the chosen models over 10 repetitions for different random seeds (standard deviation report 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.Question: Does the paper fully disclose all the information needed to reproduce the main experimental 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 or not)?Answer: [Yes] Justification: We provide a general setting of the experiments in the paper and details are provided in the code itself submitted as supplementary material.Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to 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 a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a 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 to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are 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) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a 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 be 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 models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
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 to 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 boundingP((X, Y ) ∈ B) = E[1 B (X, Y )]for a certain event B, we could define g(x, y, z) = 1 B (x, y) and apply our method.We discuss some limitations of our methods. Firstly, our method and theoretical results are only applicable to cases where Y and Z are finite sets, such as in classification problems. Extending the dual formulation in Theorem 2.1 to general Y and Z is possible but would require optimizing over function spaces, which is computationally and theoretically challenging. Additionally, if |Z| 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 are placed in Appendix D.Label model misspecification: In our asymptotic results we assumed that the label models are well-specified, i.e., the estimates {P (m) Y |Z , m ∈ N} converge to the true label model P Y |Z at m → ∞.To understand the qualities of our bound when this assumption is violated, we introduce the misspecification: P (m) Y |Z → Q Y |Z and Q Y |Z ̸ = P Y |Z .EQUATIONAssume Q Y |Z is in a set of conditional distributions such that the optimizers for (5.1), which are assumed to exist, are uniformly bounded.If d TV Q Y |Z=z , P Y |Z=z ≤ δ, then for some C > 0 which is independent of δ > 0, we have max | Ľϵ -L ϵ |, | Ǔϵ -U ϵ | ≤ Cδ . (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 i , Z i )} m i=1 sample we can consistently estimate P Y |Z , leading to δ = 0. In situations when this {(Y i , Z i )} m i=1 sample is not accessible and we have to rely on a label model, we require the misspecification in this model to be small.The bounds L and U are especially useful when their difference U -L is small because in that case, we obtain a tight bound for E[g(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 L and U be defined as in equation (1.1). ThenU -L ≤ 8 ∥g∥ 2 ∞ min{H(X | Z), H(Y | Z)} where H(X | Z) (resp. H(Y | Z)) 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 P X,Y,Z and only observe the marginals P Y,Z and P X,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 a function h : Y → Z. In this case the P X,Y,Z = P X,g(Z),Z is precisely known from the P X,Z and we can exactly pinpoint the E[g(X, Y, Z)] as E[g(X, h(Z), Z)]. In this case, H(Y | Z) = 0, leading to U -L = 0, i.e., its Fréchet bounds can precisely pinpoint it as well; ideally at least one of the H(X | Z) and H(Y | Z) is small.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 isinf π X,Z =P X,Z π Y |Z =P Y |Z E π [g(X, Y, Z)] = = inf π X,Z =P X,Z π Y |Z =P Y |Z z P(Z = z)E π [g(X, Y, Z) | Z = z] = z P(Z = z) inf π X|Z=z =P X|Z=z π Y |Z=z =P Y |Z=z E π X,Y |Z=z [g(X, Y, z)]where we notice that the inner minimization is an optimal transport problem between the probability distributions P X|Z=z and P Y |Z=z with the cost function d z (x, y) = g(x, y, z).Proof of Theorem 2.1. We start proving the result for L. See thatL = inf π∈Π E π [g(X, Y, Z)] = inf {πz∈Πz} z∈Z z∈Z P(Z = z) • E πz [g(X, Y, Z) | Z = z] = z∈Z P(Z = z) • inf πz∈Πz E πz [g(X, Y, Z) | Z = z]with Π z , is defined asΠ z ≜ {π z ∈ ∆(X × Y) : π z • ρ -1 X = P X|Z=z and π z • ρ -1 Y = P Y |Z=z } That is, for each z ∈ Z, Π zrepresents the set of couplings such that marginals are given by P X|Z=z and P Y |Z=z . We can represent the problem in this way since the marginal distribution of Z is fixed and, given that distribution, {Π z } specifies the same set of distributions as Π.Realize that we have broken down our initial maximization problem in |Z| smaller minimization problems. Each of those minimization problems can be treated as an optimal transportation problem. Consequently, by Beiglböck and Schachermayer [8, Theorem 1], for each z ∈ Z, we get the following duality resultinf πz∈Πz E πz [g(X, Y, Z) | Z = z] = sup (βz,αz)∈Ψz E[β z (X) + α z (Y ) | Z = z] with Ψ z ≜ (β z , α z ) : β z : X → [-∞, ∞), α z : Y → [-∞, ∞) E[|β z (X)| | Z = z] < ∞, E[|α z (Y )| | Z = z] < ∞ β z (x) + α z (y) ≤ g(x, y, z) for all (x, y) ∈ X × Y Moreover, partially optimizing on β z (x), we can set β * z (x) = min y∈Y [g(x, y, z) -α z (y)] and then inf πz∈Πz E πz [g(X, Y, Z) | Z = z] = = sup αz E [min y∈Y [g(X, y, Z) + α z (y)] -α z (Y ) | Z = z]where α z is a simple function taking values in the real line.Consequently,L = z∈Z P(Z = z) • sup αz E min y∈Y [g(X, y, Z) + α z (y)] -α z (Y ) | Z = z = sup {αz} z∈Z z∈Z P(Z = z) • E min y∈Y [g(X, y, Z) + α z (y)] -α z (Y ) | Z = z = sup {αz} z∈Z E min y∈Y [g(X, y, Z) + α Z (y)] -α Z (Y )Because each α z is a function assuming at most |Y| values and we have |Z| functions (one for each value of z), we can equivalently solve an optimization problem on R |Y|×|Z| . Adjusting the notation,L = sup a∈R |Y|×|Z| E min ȳ∈Y [g(X, ȳ, Z) + a ȳZ ] -E [a Y Z ]From Beiglböck and Schachermayer [8, Theorem 2], we know that the maximum is attained by some a * ∈ R |Y|×|Z| . To show that there is a maximizer in A, we need to update the solutiona * •z ← a * •z -y∈Y a * yz (shift sub-vector by a constant) (B.1)for every z ∈ Z. 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(x, y, z) = 1 -g(x, y, z) and see thatU = sup π∈Π E π [1 -c(X, Y, Z)] = 1 -inf π∈Π E π [c(X, Y, Z)]Proceeding as before, we can obtain the final result by finding the dual formulation forinf π∈Π E π [c(X, Y, Z)].We will analyze the estimator for U (results for the estimator of L can be obtained analogously).For the next results, we definefu,ε (x, z, a) ≜ f u,ε (x, z, a) + z ′ ∈Z y∈Y a yz ′ 2 .Proof of Theorem 2.5. By Assumption 2.2 and Lemmas C.1 and C.2, we can guarantee that E[ fu,ε (X, Z, a)] is minimized by a unique a * u,ε (equalling it to U ε ) and that ∇ 2 a E[ fu,ε (X, Z, a * u,ε )] is positive definite. Also, from the proof of Lemma C.2, we can see that fu,ε is convex in a (because its Hessian is positive semidefinite). It is also true that the second moment of fu,ε (X, Z, a) is well defined (exists and finite) for each a since g is bounded. DefineŨε ≜ inf a∈R |Y|×|Z| 1 n n i=1 fu,ε (X i , Z i , a)and let ãε denote a value that attains that minimum; from Niemiro [44, Theorem 4] and the conditions discussed above, we know that√ n(ã ε -a * u,ε ) = O P (1). The existence of ãε is discussed by Niemiro [44] . ThenEQUATION(C.1) where the first term is obtained by a second-order Taylor expansion of the summing functions around ãε (ā is some random vector). Also, from the standard central limit theorem, we know that√ n 1 n i fu,ε (X i , Z i , a * u,ε ) -U ε ⇒ N (0, Var fu,ε (X, Z, a * u,ε )) Given that √ n(ã ε -a * u,ε ) = O P (1)and that the Hessian has bounded entries (then O P (1) as well), the first term in C.1 is o P (1). Because a * u,ε ∈ A, we have that f u,ε (X, Z, a * u,ε ) = fu,ε (X, Z, a * u,ε ) and then √ n( Ũε -U ε ) ⇒ N (0, Varf u,ε (X, Z, a * u,ε )) by Slutsky's theorem. Since √ n( Ûε -U ) = √ n( Ûε -Ũε ) + √ n( Ũε -U ε ), if we can show that √ n( Ũε -Ûε ) = o P (1)we are done.Let â be solution for the problem in 2.3 and see that| Ũε -Ûε | = = 1 n n i=1 fu,ε (X i , Z i , ãε ) -1 n n i=1 ε log 1 |Y| y∈Y exp g(Xi,y,Zi)+â yZ i ε + E PY |Z [â Y Z | Z = Z i ] ≤ 1 n n i=1 fu,ε (X i , Z i , ãε ) -1 n n i=1 fu,ε (X i , Z i , â) + + 1 n n i=1 fu,ε (X i , Z i , â) -1 n n i=1 ε log 1 |Y| y∈Y exp g(Xi,y,Zi)+â yZ i ε + E PY |Z [â Y Z | Z = Z i ] = ( 1 n n i=1 fu,ε (X i , Z i , â) -1 n n i=1 fu,ε (X i , Z i , ãε ))+ + 1 n n i=1 y [P(Y = y | Z = Z i ) -P(Y = y | Z = Z i )]â yZi ≤ 1 n n i=1 fu,ε (X i , Z i , â) -1 n n i=1 ε log 1 |Y| y∈Y exp g(Xi,y,Zi)+â yZ i ε + E PY |Z [â Y Z | Z = Z i ] + 1 n n i=1 ε log 1 |Y| y∈Y exp g(Xi,y,Zi)+ãε yZ i ε -E PY |Z [ã ε Y Z | Z = Z i ] -1 n n i=1 fu,ε (X i , Z i , ãε ) + 1 n n i=1 y [P(Y = y | Z = Z i ) -P(Y = y | Z = Z i )]â yZi = 1 n n i=1 y [ P(Y = y | Z = Z i ) -P(Y = y | Z = Z i )]â yZi + 1 n n i=1 y [P(Y = y | Z = Z i ) -P(Y = y | Z = Z i )]ã ε yZ i + 1 n n i=1 y [P(Y = y | Z = Z i ) -P(Y = y | Z = Z i )]â yZi ≤ 2 ∥â∥ ∞ 1 n n i=1 y |P(Y = y | Z = Z i ) -P(Y = y | Z = Z i )|+ + ∥ã ε ∥ ∞ 1 n n i=1 y |P(Y = y | Z = Z i ) -P(Y = y | Z = Z i )| ≤ 2 ∥â∥ ∞ z y |P(Y = y | Z = z) -P(Y = y | Z = z)|+ + ∥ã ε ∥ ∞ z y |P(Y = y | Z = z) -P(Y = y | Z = z)| ≤ 4 ∥â∥ ∞ z d TV PY |Z=z , P Y |Z=z + 2 ∥ã ε ∥ ∞ z d TV PY |Z=z , P Y |Z=z = O P (m -λ )where the last equality is obtained using Assumptions 2.3 and 2.4, and the fact that∥ã ε ∥ ∞ is tight (derived from √ n(ã ε -a * u,ε ) = O P (1)). Consequently, √ n( Ũε -Ûε ) = √ nO P (m -λ ) = o(m λ )O P (m -λ ) = o P (1)Finally, using Slutsky's theorem,√ n( Ûε -U ) = √ n( Ûε -Ũε ) + √ n( Ũε -U ) ⇒ N (0, Varf u,ε (X, Z, a * u,ε ))Proof of Corollary 3.1. We prove the asymptotic distribution of √ n pu,ε -p u,ε . The result for the lower bound can be obtained analogously.First, note thatP(h(X) = 1) -P(h(X) = 1) = O P (m -1/2 ) (C.2)by the standard central limit theorem.Next, see that√ n (p u,ε -p u,ε ) = = √ n Ûε P(h(X)=1) - Uε P(h(X)=1) = 1 P(h(X)=1) √ n Ûε -P(h(X)=1) P(h(X)=1) U ε = 1 P(h(X)=1) √ n Ûε -U ε + 1 P(h(X)=1) √ n U ε -P(h(X)=1) P(h(X)=1) U ε = 1 P(h(X)=1) √ n Ûε -U ε + U ε √ n 1 P(h(X)=1) - 1 P(h(X)=1) = 1 P(h(X)=1) √ n Ûε -U ε + U ε √ n P(h(X) = 1) -P(h(X) = 1) -1 P(h(X)=1) 2 + o P m -1/2 = 1 P(h(X)=1) √ n Ûε -U ε + o P (1) ⇒ N (0, σ 2 p,u,ε )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 = o(m (2λ)∧1 ), 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 √ n ru,ε -r u,ε . The result for the lower bound can be obtained analogously. From Lemma C.3, we know that there is an estimator P(Y = 1) such that P(Y = 1) -P(Y = 1) = O P (m -(λ∧1/2) ), i.e., it has enough precision. We use that estimator.Next, see that√ n (r u,ε -r u,ε ) = = √ n Ûε P(Y =1) -Uε P(Y =1) = 1 P(Y =1) √ n Ûε -P(Y =1) P(Y =1) U ε = 1 P(Y =1) √ n Ûε -U ε + 1 P(Y =1) √ n U ε -P(Y =1) P(Y =1) U ε = 1 P(Y =1) √ n Ûε -U ε + U ε √ n 1 P(Y =1) -1 P(Y =1) = 1 P(Y =1) √ n Ûε -U ε + U ε √ n P(Y = 1) -P(Y = 1) -1 P(Y =1) 2 + o P m -1/2 = 1 P(Y =1) √ n Ûε -U ε + o P (1) ⇒ N (0, σ 2 r,u,ε )Finally, we prove the asymptotic distribution of √ n Fu,ε -F u,ε . The result for the lower bound can be obtained analogously. From the facts stated above, we know thatP(h(X) = 1) + P(Y = 1) -[P(h(X) = 1) + P(Y = 1)] = = [ P(h(X) = 1) -P(h(X) = 1)] + [ P(Y = 1) -P(Y = 1)] = = O P (m -(λ∧1/2) ) Then, √ n Fu,ε -F u,ε = = √ n 2 Ûε [ P(h(X)=1)+ P(Y =1)] - 2Uε [P(h(X)=1)+P(Y =1)] = 2 [ P(h(X)=1)+ P(Y =1)] √ n Ûε -[ P(h(X)=1)+ P(Y =1)] [P(h(X)=1)+P(Y =1)] U ε = 2 [ P(h(X)=1)+ P(Y =1)] √ n Ûε -U ε + 1 [ P(h(X)=1)+ P(Y =1)] √ n 2U ε -[ P(h(X)=1)+ P(Y =1)] [P(h(X)=1)+P(Y =1)] 2U ε = 2 [ P(h(X)=1)+ P(Y =1)] √ n Ûε -U ε + 2U ε √ n 1 [ P(h(X)=1)+ P(Y =1)] - 1 [P(h(X)=1)+P(Y =1)] = 2 [ P(h(X)=1)+ P(Y =1)] √ n Ûε -U ε + + 2U ε √ n [ P(h(X) = 1) + P(Y = 1)] -[P(h(X) = 1) + P(Y = 1)] -1 [P(h(X)=1)+P(Y =1)] 2 + o P m -1/2 = 2 [ P(h(X)=1)+ P(Y =1)] √ n Ûε -U ε + o P (1) ⇒ N (0, σ 2 F,u,ε )where all the steps are justified as before.Lemma C.1. Define fu,ε (x, z, a) ≜ f u,ε (x, z, a) + z ′ ∈Z y∈Y a yz ′ 2 Then inf a∈R |Y|×|Z| E[ fu,ε (X, Z, a)] = inf a∈A E[f u,ε (X, Z, a)] Proof. First, see that E[ fu,ε (X, Z, a)] ≥ E[f u,ε (X, Z, a)]From Assumption 2.2, we know that there exists some a * u,ε ∈ R |Y|×|Z| such thatinf a∈A E[f u,ε (X, Z, a)] = E[f u,ε (X, Z, a * u,ε )]For that specific a * u,ε , we have thatE[ fu,ε (X, Z, a * u,ε )] = E[f u,ε (X, Z, a * u,ε )] Consequently, inf a∈R |Y|×|Z| E[ fu,ε (X, Z, a)] = E[ fu,ε (X, Z, a * u,ε )] = E[f u,ε (X, Z, a * u,ε )] = inf a∈A E[f u,ε (X, Z, a)]Lemma C.2. The function of a given by E[ fu,ε (X, Z, a)] has positive definite Hessian, i.e.,H ε (a) = ∇ 2 a E[ fu,ε (X, Z, a)] ≻ 0 and, consequently, it is strictly convex. Proof. See that H ε (a) = ∇ 2 a E[f u,ε (X, Z, a)] + ∇ 2 a z ′ ∈Z y∈Y a yz ′ 2We start computing the first term in the sum.First, for an arbitrary pair (k, l) ∈ Y × Z, define s kl (x) ≜ exp g(x,k,l)+a kl ε y exp g(x,y,l)+a yl εNow, see that∂ ∂a kl f u,ε (x, z, a) = 1 {l} (z) s kl (x) -P(Y = k | Z = l)and∂ 2 ∂a pl ∂a kl f u,ε (x, z, a) = 1 ε 1 {l} (z) 1 {k} (p)s kl (x) -s kl (x)s pl (x)See that∂ 2 ∂a pb ∂a kl f u,ε (x, z, a) = 0 if b ̸ = l. Consequently, the Hessian ∇ 2 a f u,ε (x, z, a) is block diagonal.Consequently, because the second derivatives are bounded, we can push them inside the expectations and get∂ 2 ∂a pl ∂a kl E [f u,ε (X, Z, a)] = = E ∂ 2 ∂a pl ∂a kl f u,ε (X, Z, a) = 1 ε E 1 {l} (Z) 1 {k} (p)s kl (X) -s kl (X)s pl (X) = 1 ε 1 {k} (p) • E [P(Z = l | X)s kl (X)] -1 ε E [P(Z = l | X)s kl (X)s pl (X)]Because ∇ 2 a f u,ε (x, z, a) is block diagonal, we know that the Hessian∇ 2 a E [f u,ε (X, Z, a)]is block diagonal (one block for each segment a •z of the vector a). Now, realize that∇ 2 a z ′ ∈Z y∈Y a yz ′ 2is also block diagonal, with each block being matrices of ones. In this case, we also have one block for each segment a •z of the vector a. Consequently, H ε (a) is block diagonal, and it is positive definite if and only if all of its blocks are positive definite. Let us analyse an arbitrary block of H ε (a), e.g., ∇ 2 a •l E fu,ε (X, Z, a) . Let s •l (x) be the vector composed of s kl (x) for all k. If 1 ∈ R |Y| denotes a vector of ones, then,∇ 2 a •l E fu,ε (X, Z, a) = = 1 ε diag E [P(Z = l | X)s •l (X)] -1 ε E P(Z = l | X)s •l (X)s •l (X) ⊤ + 11 ⊤ = E 1 ε P(Z = l | X) diag s •l (X) -s •l (X)s •l (X) ⊤ + ε P(Z=l) 11 ⊤ = E 1 ε P(Z = l | X) diag s •l (X) -s •l (X)s •l (X) ⊤ + 11 ⊤where 1 = ε P(Z=l) 1. See that diag s •l (x) has rank |Y| (full rank) while s •l (x)s •l (x) ⊤ is rank one for every x ∈ R d X . Consequently, the rank of the differenceD(x) = diag s •l (x) -s •l (x)s •l (x) ⊤ Then P(Y = 1) -P(Y = 1) = O P (m -(λ∧1/2) )Proof. To derive this result, see that| P(Y = 1) -P(Y = 1)| = = 1 m m i=1 E P Y |Z [Y | Z = Z i ] -P(Y = 1) + 1 m m i=1 E PY |Z [Y | Z = Z i ] -E P Y |Z [Y | Z = Z i ] ≤ 1 m m i=1 E P Y |Z [Y | Z = Z i ] -P(Y = 1) + 1 m m i=1 E PY |Z [Y | Z = Z i ] -E P Y |Z [Y | Z = Z i ] = O P (m -1/2 ) + 1 m m i=1 P PY |Z [Y = 1 | Z = Z i ] -P P Y |Z [Y = 1 | Z = Z i ] ≤ O P (m -1/2 ) + z∈Z P PY |Z [Y = 1 | Z = z] -P P Y |Z [Y = 1 | Z = z] ≤ O P (m -1/2 ) + y∈{0,1} z∈Z P PY |Z [Y = y | Z = z] -P P Y |Z [Y = y | Z = z] = O P (m -1/2 ) + 2 z∈Z d TV PY |Z=z , P Y |Z=z = O P (m -1/2 ) + O P (m -λ ) = O P (m -(λ∧1/2) )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.Lemma C.4. For some κ > 0 and any y ∈ Y assume that κ ≤ p y ≤ 1 -κ. Define A = {a y ∈ R :y a y = 0}. Then the optima of the following problemsinf a∈A f u (a), f u (a) ≜ E ϵ log 1 |Y| y exp g(X,y)+ay ϵ -y p y a y , sup a∈A f l (a), f l (a) ≜ E -ϵ log 1 |Y| y exp g(X,y)+ay -ϵ -y p y a y (C.3)are attained in a compact set K(κ, L) ⊂ A where ∥g∥ ∞ ≤ 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.The second derivation of f u is∇ ay,a y ′ f u (a) = 1 ϵ E p(X, y, a){δ y,y ′ -p(X, y ′ , a)} (C.4)where p(x, y, a) ≜ exp g(X,y)+ay ϵ i∈Y exp g(X,i)+a i ϵ. For any u ∈ R Y we haveu ⊤ ∇ 2 f u (a)u = i,j∈Y u i u j ∇ ai,aj f u (a) = 1 ϵ i,j∈Y u i u j E p(X, i, a){δ i,j -p(X, j, a)} = 1 ϵ E i u 2 i p(X, i, a) - i u i p(X, i, a) 2 = 1 ϵ E[σ 2 (X, u, a)] ≥ 0 (C.5)where σ 2 (x, u, a) is the variance of a categorical random variable taking the value u i with probability p(x, i, a). This leads to the conclusion that the function is convex.To establish strict convexity, we fix a ∈ A and notice that 0 < p(x, y, a) < 1 (because ∥g∥ ∞ ≤ L). Therefore, the σ 2 (x, u, a) can be zero only when the u i 's are all equal. Since A = {a ∈ R Y :y a y = 0}, such u belongs to the space A in the unique case u i = 0. This leads to the conclusion that for any u ∈ A and u ̸ = 0u ⊤ ∇ 2 f u (a)u = 1 ϵ E[σ 2 (X, u, a)] > 0 .Therefore, f u 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) = p y for all y ∈ Y, where h(a, y) ≜ E[p(X, y, a)](C.6)To show that (C.6) has a solution in a compact ball K(ϵ, κ, L) ≜ {a ∈ A : ∥a∥ 2 ≤ M (ϵ, κ, L)} we construct an M (ϵ, κ, L) > 0 such that min y h(a, y) < κ whenever ∥a∥ 2 > M (ϵ, κ, L). Since κ ≤ p y ≤ 1 -κ for all y ∈ Y this concludes that the solution to (C.6) must be inside the K(ϵ, κ, L).Let us define y min ≜ arg min y a y and y max ≜ arg max y a y . To construct M (κ, L, ϵ) (we shall write it simply as M whenever it is convenient to do so) we notice thath(a, y min ) = E[p(X, y min , a)] = E exp g(X,1)+ay min ϵ i∈Y exp g(X,i)+a i ϵ ≤ exp L+ay min ϵ exp L+ay min ϵ + i≥2 exp -L+a i ϵ = exp 2L ϵ exp 2L ϵ + i≥2 exp a i -ay min ϵ ≤ exp 2L ϵ exp 2L ϵ +exp ay max -ay min ϵ ≤ exp 2L ϵ exp 2L ϵ +exp R ϵ , (C.7)where R ≜ min{max y a y -min y a y :i a i = 0, i a 2 i > M 2 } .We rewrite the constraints of the optimization as: R ≜ min max y a y -min y a y :mean{a i } = 0, var{a i } > M 2|Y| . where we use the Popoviciu's inequality on variance to obtainM 2 |Y| < var{a i } ≤(maxy ay-miny ay) 2 4, or max y a y -min y a y > 2M √ |Y| , Thus R ≥ 2M √ |Y| whenever ∥a∥ 2 > M . We use this inequality in (C.7) and obtainh(a, y min ) ≤ exp 2L ϵ exp 2L ϵ +exp R ϵ ≤ exp 2L ϵ exp 2L ϵ +exp 2M ϵ √ |Y| .Finally, we choose M = M (ϵ, κ, L) > 0 large enough such thath(a, y min ) ≤ exp 2L ϵ exp 2L ϵ +exp 2M ϵ √ |Y| < κ .For such an M we concludes that h(a, y min ) < κ whenever ∥a∥ 2 > M .Lemma C.5. L ε and U ε are attained by some optimizers in a compact set K(ϵ, κ z , z ∈ Z; L) ⊃ A ((2.2)), where κ z = min{p y|z , 1 -p y|z : y ∈ Y}.Proof of lemma C.5. We shall only prove the case of the minimization problem. The proof for the maximization problem uses a similar argument.A decomposition of the minimization problem according to the values of Z follows.min a∈A E ϵ log 1 |Y| y∈Y exp g(X,y,Z)+a Y,Z ϵ -E [a Y,Z | Z] = z p z      min a•,z∈R Y y ay,z=0 E ϵ log 1 |Y| y∈Y exp g(X,y,z)+a Y,z ϵ | Z = z -E[a Y,z | Z = z]      = z p z      min a•,z∈R Y y ay,z=0 E ϵ log 1 |Y| y∈Y exp g(X,y,z)+a Y,z ϵ | Z = z -y a y,z p y|z      (C.8) where p z = P (Z = z) and p y|z = P (Y = y | Z = z). We fix a z and consider the corresponding optimization problem in the decomposition. Then according to lemma C.4 the optimal point is in a compact set K(ϵ, κ z , L). Thus the optimal point of the full problem is in the Cartesian product z K(ϵ, κ z , L) ⊂ A, which a compact set. Thus we let K(ϵ, κ z , z ∈ Z; L) = z K(ϵ, κ z , L). p(m) y|z to reach the conclusion that the optimizer is in the compact set K(ϵ, κz /2, z ∈ Z; L). Thus, for sufficiently large m and any n P optimizer is in K(ϵ, κz /2, z ∈ Z; L) ≥ p(m) . This establishes that the optimizers are tight.Proof of Theorem 5.1. We only prove the theorem for upper Fréchet bound. The proof of lower bound is similar.First, notice thatfu,ε (x, z, a) -f u,ϵ (x, z, a) = = ε log 1 |Y| y∈Y exp g(x,y,z)+ayz ε -E Q Y |Z [a Y z | Z = z] -ε log 1 |Y| y∈Y exp g(x,y,z)+ayz ε + E P Y |Z [a Y z | Z = z] = E P Y |Z [a Y z | Z = z] -E Q Y |Z [a Y z | Z = z]and thus| fu,ε (x, z, a) -f u,ϵ (x, z, a)| (D.1) = E P Y |Z [a Y z | Z = z] -E Q Y |Z [a Y z | Z = z] (D.2) ≤ ∥a∥ ∞ × 2d TV Q Y |Z=z , P Y |Z=z (using a ⊤ b ≤ ∥a∥ ∞ ∥b∥ 1 ) (D.3) ≤ 2∥a∥ ∞ δ .(by assumption) (D.4)DefiningEQUATIONwe now establish that| Ǔϵ -U ϵ | ≤ 2δ max(∥a ⋆ ∥ ∞ , ∥ǎ∥ ∞ ) . (D.6)This is easily established from the following arguments:Ǔϵ = E[ fu,ε (X, Z, ǎ)] ≤ E[ fu,ε (X, Z, a ⋆ )] (ǎ is the minimizer) ≤ E[f u,ε (X, Z, a ⋆ )] + 2∥a ⋆ ∥ ∞ δ (using eq. (D.4)) = U ϵ + 2∥a ⋆ ∥ ∞ δ (D.7)and similarlyU ϵ = E[f u,ε (X, Z, a ⋆ )] ≤ E[f u,ε (X, Z, ǎ)] ≤ E[ fu,ε (X, Z, ǎ)] + 2∥ǎ∥ ∞ δ = Ǔϵ + 2∥a ⋆ ∥ ∞ δ . (D.8)By assumption, a ⋆ and ǎ are bounded. Thus, we can find a C > 0, which is independent of δ > 0, such that2 max(∥a ⋆ ∥ ∞ , ∥ǎ∥ ∞ ) ≤ Cand the theorem holds for this C.Proof of Theorem 5.2. For clarity, we shall assume X is a continuous random variable in this proof, even though this is not strictly needed.In this section, we propose and empirically evaluate three strategies for model selection using our estimated bounds in Equation 2.3.Assume, for example, g(x, y, z) = 1[h(x) = y] for a 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 metrics, such as F1 score. The model selection problem consists of choosing the best model from a set H ≜ {h 1 , • • • , h K } in order to maximize out-of-sample accuracy. Define Lε (h) and Ûε (h) as the estimated accuracy lower and upper bounds for a certain model h. The first strategy is to choose the model with highest accuracy lower bound, i.e., h * lower = arg max h k ∈H Lε (h k ) Maximizing the accuracy lower bound approximates the distributionally robust optimization (DRO) [9] solution when the uncertainty set is given by Π in 1.1. That is, we optimize for the worst-case distribution in the uncertainty set. Analogously, we can choose the model that optimizes the best-case scenario h * upper = arg max h k ∈H Ûε (h k ). 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.,h * avg = arg max h k ∈H Lε(hk)+ Ûε(hk) 2.In this experiment, we select multilayer-perceptrons (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 {.1, .001} and weight decay (l 2 regularization parameter) in {.1, .001}. For those datasets that use the F1 score as the evaluation metric, we also tune the classification threshold in {.2, .4, .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 F1 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 useh * label_model = arg max h k ∈H 1 n n i=1 E PY |Z 1[h k (X) = Y | Z = Z i ],which is a natural choice when X ⊥ ⊥ 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 10 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 our 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, it 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 or null rank correlations). Extra results for binary classification datasets can be found in Figures 4 and 5 . In Table 5 , we can see the results for multinomial classification datasets. In Table 6 , we can see the same results already in the main text plus the results for FlyingSquid.All experiments were conducted using a virtual machine with 32 cores. The experiments are not computationally intensive and everything can be run within a few hours. 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. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Question: Does the paper provide open access to the data and code, with sufficient instructions to 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. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or 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.• If 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 societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment 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 particular applications, let alone deployments. However, if there is a 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 to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a 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 as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
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 (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: The paper poses no such risks. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or 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 or 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 of the asset is used and, if 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. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.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 is not available online, the authors are encouraged to reach out to the asset's creators. 
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 new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions 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 is used.• At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to 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 applicable), such as the institution conducting the review.Ratner et al. [49] derive that in page 24 of their arXiv paper version.It is also possible to use distinct datasets for estimating the label model and the bounds as long as the dataset to estimate the label is much bigger. This is our approach in the experiments.In practice, it can be obtained using all the data not used to estimate bounds.Accessible at https://huggingface.co/sentence-transformers/paraphrase-MiniLM-L6-v2.More details regarding the prompts can be found in Appendix G.1.The most informative weak labels are determined based on their alignment with the true label. 
 
 Appendix:  


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

Reviews: review: paper_summary: paper_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.

This 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.
strength_weakness: strength_weakness: 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.
questions: questions: 1) why it is not possible to get high probability results? 
2) 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?
3) 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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

I believe the paper could be written more clearly; currently, it is difficult to follow.

As 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?

Theorem 2.4 is not easy to interpret.

The quality of Figure 1 can be improved, and this figure needs more explanation.
questions: questions: See Weaknesses Section.
limitations: limitations: The authors describe limitations in the paper.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 

Finally, 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.
questions: questions: No additional questions.
limitations: limitations: The authors have addresses the limitations of the work.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: 1. Do you have any intuitions about settings where the usage of your method for label set selection is well-motivated? 
2. 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.

[1] Sam, et. al. Losses over Labels: Weakly Supervised Learning via Direct Loss Construction.

[2] Cachay, et. al. End-to-End Weak Supervision.

[3] Yu, et. al. Fine-Tuning Pre-trained Language Model with Weak Supervision: A Contrastive-Regularized Self-Training Approach.
limitations: limitations: Yes, limitations have been adequately addressed.

Comments: title: Thanks for addressing my concerns.
Reviewer Response
comment: Thanks for the rebuttal. 

* Somehow the problem is described better in that paper which is cited [1]. Anyway, I know that every technical detail cannot be described in a NeurIPS due to space limitation. So I also reread your paper, and I think I overlooked the merit of your approach. What I miss is to test various different label models, however, I believe that the confidence interval is hard to derive if the label model is model complex.

* This is actually addressed in the conclusion as pointed out that this is a limitation. I think in terms of novelty this paper is already good enough for NeurIPS.

* Yes high probability results are conservative, but the asymptotic might be not valid for small sample size. But anyway, do not open this debate here.

* Thanks for the comments.

So I will increase my score.
Thanks to the authors for answering all my questions and clarifying the contributions of the paper. Therefore, I have decided to raise my score to a 5.
Thank you for the clarification! I choose to maintain my score as a weak accept; I think that this paper proposes an interesting approach to a relevant problem in PWS.