Learning from weak labelers as constraints
Authors: Vishwajeet Agrawal
Rattana Pukdee
Maria Florina Balcan
Pradeep Kumar Ravikumar
Venue: ICLR 2025 Poster (2025)
Keywords: unsupervised learning
weak supervision
learning theory
Primary area: learning theory
TL;DR: A new method for learning from weak labelers given information about their average errors.

Abstract: We study programmatic weak supervision, where in contrast to labeled data, we have access to \emph{weak labelers}, each of which either abstains or provides noisy labels corresponding to any input. Most previous approaches typically employ latent generative models that model the joint distribution of the weak labels and the latent ``true'' label. The caveats are that this relies on assumptions that may not always hold in practice such as conditional independence assumptions over the joint distribution of the weak labelers and the latent true label, and more general implicit inductive biases in the latent generative models. In this work, we consider a more explicit form of side-information that can be leveraged to denoise the weak labeler, namely the bounds on the average error of the weak labelers. We then propose a novel but natural weak supervision objective that minimizes a regularization functional subject to satisfying these bounds. This turns out to be a difficult constrained optimization problem due to discontinuous accuracy bound constraints. We provide a continuous optimization formulation for this objective through an alternating minimization algorithm that iteratively computes soft pseudo labels on the unlabeled data satisfying the constraints while being close to the model, and then updates the model on these labels until all the constraints are satisfied. We follow this with a theoretical analysis of this approach and provide insights into its denoising effects in training discriminative models given multiple weak labelers. Finally, we demonstrate the superior performance and robustness of our method on a popular weak supervision benchmark.

Published as a conference paper at ICLR 2025
LEARNING FROM WEAK LABELERS AS CONSTRAINTS
Vishwajeet Agrawal', Rattana Pukdee", Maria-Florina Balcan, Pradeep Ravikumar Carnegie Mellon University {vishwaja, zpukdee, ninamf, pkr] cmu. edu
ABSTRACT
We study programmatic weak supervision, where, in contrast labeled data, we have access to weak labelers, each of which either abstains or provides noisy labels corresponding to any input. Most previous approaches typically employ latent generative models that model the joint distribution of the weak labels and the latent "true" label. The caveats are that this relies on assumptions that may not always hold in practice, such conditional independence assumptions over the joint distribution of the weak labelers and the latent true label, and more general implicit inductive biases in the latent generative models. In this work, con- sider a more explicit form of side information that can be leveraged to denoise the weak labeler, namely the bounds on the average error of the weak labelers. We then propose a novel but natural weak supervision objective that minimizes a regularization functional subject to satisfying these bounds. This turns out be a difficult constrained optimization problem due to discontinuous accuracy bound constraints. We provide continuous optimization formulation for this objec- tive through an alternating minimization algorithm that iteratively computes soft pseudo labels on the unlabeled data satisfying the constraints while being close the model, and then updates the model on these labels until all the constraints are satisfied. We follow this with a theoretical analysis of this approach and provide insights into its denoising effects in training discriminative models given multiple weak labelers. Finally, we demonstrate the superior performance and robustness of our method popular weak supervision benchmark.
INTRODUCTION
Acquiring high-quality labeled data, which is critical for supervised learning, is often very expen- sive. The burgeoning field of programmatic weak supervision addresses this caveat by training models from "weak labelers," which are functions that either abstain provide noisy labels corre- sponding to any input (Zhang et al., 2022). Such weak labelers could range from domain-expert- specified functions rule-based systems, heuristics, or even pre-trained models. There are two main challenges in learning a predictor using only weak labelers: each weak labeler covers only part of the input space (due to abstention) and is typically noisy. Thus, one has to generalize beyond the coverage regions, as well as denoise within them.
To learn from weak labelers, most prior works draw from developments in related fields such as crowdsourcing (Estellés-Arolas & González-Ladrónnde Guevara, 2012; Wazny, 2017), employing latent generative models that model the joint distribution of the weak labels and the latent "true" label. Conditional inference the true label then provides natural approach aggregate multiple noisy labels into less noisy "pseudo-labels" which provide an estimate of the true label. However, this relies the implicit inductive bias since non-paraeetric mixture models are known to not be identifiable without any further assumptions (Kasahara & Shimotsu, 2014; Aragam et al., 2020). For example, Snorkel (Ratner et al., 2017; 2018) imposes both (a) conditional independence assump- tions among the weak labelers and the true label (b) parametric assumptions on the latent generative model. However, these assumptions might not be applicable and are, in general, difficult to validate with domain experts. In addition, the denoising step does not take advantage of modern hypothe- sis classes such as deep neural networks. Instead, it is common follow a two-staged approach: denoising step to estimate pseudo-labels and then train neural network using these pseudo-labels.
"Equal contribution.

---

Published as a conference paper at ICLR 2025
We also note that this learning from weak labelers is closely related to subfield of learning with noisy labels that also faces a denoising problem (Angluin & Laird, 1988; Blum et al., 1998; Natara- jan et al., 2013). Here, we assume that noisy label is obtained by passing the unknown true label through a noise channel that is usually assumed to be independent of the input (Natarajan et al., 2013). There is also a general noise model that could depend on the input called Massart noise (Massart& & Nédélec, 2006) which is known to lead to computationally hard learning problem (Di- akonikolas al., 2019a; 2022a). A recent line of work shows that we can make headway in this difficult setting, provided we have additional side information such as the marginal distribution is structured (Awasthi et al., 2015; 2016; Diakonikolas al., 2022b). There have been considerabe recent advances in learning under such noise models and other difficult noise models such as the malicious noise model (Awasthi et al., 2014; 2017: Diakonikolas et al., 2018; 2019b; Prasad et al., 2018). However, we remark that results from learning with noisy labels are not directly applicable to our setting since the levels of noise induced by our weak labelers do not satisfy the amount of structure needed by these works.
Regardless, we believe that programmatic weak supervision can considerably benefit from connec- tions with the field of learning from noisy labels and that it forms a rich area of research. As first step towards leveraging such a connection, we consider the following natural and explicit inductive bias that domain experts might provide, bound the accuracy of each weak labeler (similar to bound on the fraction of corrupted data in the learning from noisy label setting), where accuracy can either be with respect to the target Bayes optimal classifier or with respect to the underlying stochas- tic label distribution. Our first contribution is to develop a constraint- based approach to aggregate weak labelers by viewing the accuracy bound constraint, and accordingly impose this constraint on the model to be learned. We pose the problem as learning the simplest model (with respect to some regularization functional) that satisfies all of these constraints (Section 2). This objective is however difficult along multiple facets: it is constrained optimization problem, with discontinuous accuracy bound constraints. While there is a rich literature on continuous convex surrogates of clas- sification accuracy (or error), they are not immediately applicable in our setting since bound on the accuracy does not translate to a bound on any particular surrogate loss, and recall that it is these accuracy bounds that form our domain-expert provided side information.
Our second contribution is a scalable optimization algorithm. This is based on a projection function that projects the model onto the set of all functions that satisfy the constraints. First, we show that the projection objective can be reduced to a linear program when the error bounds are given with respect the target Bayes optimal classifier (Section 3.1). and convex optimization problem when they are given with respect to the target label distribution (Section 3.2). The convex optimization problem for the latter case results in an efficient and robust algorithm that can also be used as an approximation when the constraints are given with respect to the target classifier.
Our third contribution is a rigorous analysis of our constrained estimator (Section 4). We note that the traditional statistical learning theoretic tools are not applicable since we have no labeled data. We provide two tools to bound the error of the learned classifier: i) an agreement region based analysis fi) corrected triangle inequality. Both approaches involve disparate denoising coefficients that track the benefit of having multiple rather than a single weak labeler. We further refine this to provide tighter extension of the bounds from the limited support to the overall space using subtle Lipschitz notion that might be of independent interest even outside the context of this paper. Lastly, we demonstrate the robustness and competitive performance of our method on popular weak supervision benchmark (Zhang et al., 2021) in Section 5.
LEARNING FROM WEAK LABELER CONSTRAINTS
Setup: We consider the general setting of multi-class classification, with input space X, output space ) = {1...., K}. joint distribution P over X' x y, and marginal distribution over X' denoted by Px which we assume to be continuous. We use uppercase letters (e.g.. X) to represent random variables and lowercase letters (e.g.. x) for deterministic variables. For vector E Rdd we denote Ik as the kth entry of x. Letp" (x) = p(y|z) E R² be the conditional distribution of y given x., and let fx) arg max p" (=)) denote the Bayes optimal classifier. Our goal is to learn classifier f: X + y that minimizes the expected misclassification error with respect to the Bayes optimal classifier f", i.e. minimizes Pr(J(X)= # (X)),, the error with respect to the stochastic label
2

---

Published as a conference paper at ICLR 2025
itself: Pr(f(X) YY). In our setting, assume that only have access to unlabeled data drawn ii.d. from Px and weak labelers {9) [e]]] where each weak labeler 9j X + +V U {0} maps any point in the instance space the label space or abstains from prediction (denoted by 0). We denote the coverage set of the weak labeler by Sj == {ir E X' ()(x) 0}. We consider formulating classifier from smooth real-valued function h X' - IR* from some hypothesis class F e.g. neural networks. This function induces conditional distribution denoted by ph. which we obtain by applying the softmax function, Ps. (x)) = exp(h(x=))) Σ exp(h(2r)))- For any conditional distribution p such that arg max, p(z), is unique for each æ, we denote the corresponding classifier as (p) where (z) = arg max; p(r)..
Accuracy bounds and the corresponding constraints: We assume we have additional side infor- mation about the average error of each weak labeler 93 on its coverage set Sy. First, this can be an error bound with respect to the Bayes optimal classifier f given by
Par(g: f²) Pr (g)(X) + (X)] E S,) sm. X~Px
(1)
Since our target Bayes optimal classifier f" only differs from 9j by fraction of at most fy Sj, natural learning strategy is to encourage our hypothesis to also have the same behavior (differ from Bj at most 77)) This leads to constraint Par (g), clf(p))) ) S 7i.- We propose to learn the simplest hypothesis f (with respect to regularization functional R(f)) that satisfies all of these constraints which can be formalized the following objective with constraints on classifier outputs:
min R(f) s.t. Petr(g clf(p;)) S Th Vj E [m]]
(2)
JEF
On the other hand, if we may instead have access to an error with respect to the stochastic labels sampled from p", the bound is given by
Pr Pdist (9j: (gg.P") X~Px.Yxx'(X) (g)(X) # XIX E S,) S mm
(3)
Here gj is a classifier but Y random variable distributed according to p" (X), ) so the proba- bility that (x) is not equal to y for each is given by Σk (x) p² (x) thus (g. p') Ex-px Ex (n) p" (x))]. Similar before, we have the following objective with constraints on classifier probabilistic labels:
min R(f) s.t. Palst (gg,Pt) mh Vj e [m] JEF
ALGORITHMS
In this section, we will first examine an algorithm for solving the learning objective with constraints on classifiers (equation 2) through an alternating minimization algorithm. This requires a projection step that projects conditional distribution into the set of conditional distributions that satisfy the constraints. We will describe a method for estimating this projection and show that it can be reduced to linear program. Finally, we will extend our algorithm to solve the objective with constraints on the distribution (equation 4). We provide proofs for results in this section in Appendix B.
3.1 LEARNING OBJECTIVE WITH CONSTRAINTS ON CLASSIFIER
The key challenge in solving equation 2 is that it is a constrained optimization problem and these constraints not continuous. As key initial step, we define projection loss of a conditional distribution p to a class of classifiers that satisfies the constraint. We denote a set of all conditional distributions that satisfy the constraints as
Qar = Anner where Qj = (g: A parl clf(4)) S n
(5)
We consider a projection loss from any conditional distribution p to a set of conditional distributions Q given by,
d(p. Q) = inf Ex Ex((x((((X))))(()))
(6)
QEQ
where DRL. is the KL KL-divergence. We show that d(p, Qeie) is zero if and only if p E Qetr-
3

---

Published as a conference paper at ICLR 2025
Lemma 3.1. For any such that cp is well defined, i.e. arg maxy p(a)y is unique for each I, we have d(p, Qat)) = if and only if p E Qeit-
From Lemma 3.1, we may replace the constraints in equation 2 with the projection loss instead. This would still lead to the same optimal solution. We have an objective
min R(f) s.t. dips, Qai)
JEF
We consider a relaxation this objective into an unconstrained optimization problem,
min R() a ddppp, Qai)
(8)
feF
where trades off satisfying the constraints with a notion of simplicity of distribution specified through the regularization. This relaxed objective is now more suitable for gradient- based opti- mization since it continuous. We can rewrite this objective as
min gEQar.fEF
((,9)) = R(() + oxE (xxx(xxx(((X)))))xxx(X)))
This is minimization problem in f F.q E Qete for which we propose to an alternating minimization algorithm where we keep track of a sequence of (fr, qe) and update as follows:
1. fi+11 arg min R(f) + (xx feT
(10)
2. 9++1 = arg min Ex (4 Pfen (X))
(11)
rEQar
We can show that this algorithm leads to sequence of (fe. that is decreasing in L(fe, q():
Lemma 3.2. A sequence (Je,gt) with an update in equation 10 and equation 11 satisfies L(J++1, ([f++119++1) L(Se.
Proof. C(f++1, (++1) < ((f++1,9:) from minimization in equation 11 and C(f+41, 4t) S L(fe, from minimization equation 10.
Solving step 1 (equation 10). It can be that the KL. term in equation 10 is simply the cross- entropy loss with respect to the pseudo soft labels given by q. Thus this first step of the alternating minimization algorithm simply fits a regularized classifier to these pseudo labels. Further, one does not need to estimate the exact minima at each step, as long as the next iterate reduces the objective, i.e. L(fe+1, 4+21) < C(fe. 9t). Thus one can take a single or few steps of gradient descent in equation 10 to get fe+1 from fr.
Solving step 2 (equation 11). This step the alternating minimization algorithm computes the soft pseudo labels on the training data so that the constraints are satisfied. This is much more involved step, which we detail in the following section, where we show that estimating the projection qe be reduced to linear program. Before doing so, first remark that the constraints classifiers may not be robust to a small perturbation. For example, if one has a uniform conditional distribution Punit (1/K,.... 1/ K), we can make small perturbation Ap of size at most such that elf (punit + Ap) = l for any label k. This implies that there exists a conditional distribution such that d(p, Q) small but (p) can be arbitrary.
Lemma 3.3. Let Q {a E X + A elf(g) E H} for some set of classifiers H. For any 0 and any classifier f, there exists conditional distribution p such that clf(p) = and d(p, Q)
To alleviate this problem, enforce additional constraint by making sure that g puts higher probability on one label than the rest,
A, = {g E A for each x, By q(>),, 2 (1+ (c(())) for le # y)
(12)
With this additional constraint, we can show that d(p, Q) bounds the error in satisfaction of the classifier constraints, and further show that the projection problem can be solved efficiently.
Proposition 3.4. For any V there exists 5(c, > 0 such that if d(p, A. nQar) ō(c,v) then Parlg,, clf(p)) I Th + S/l where |S,| = Px E Sz) is the size of coverage set S of weak labeler gj with respect marginal distribution Px.
4

---

Published as a conference paper at ICLR 2025
Proposition 3.5. Given Q = =4 for A. defined in equation 12 and Qeit defined in equation 5, for any conditional distribution p. the optimal projection q" = arg mingeq [gD can be found follows,
1. Solve for optimal (q as
clf(q")
arg min Ex (Projиr (p(X))((())))))))))) A (xx),,)] Parlgg, h) S n3 hER-y
(13)
where
KK_ frEAk K
ry 2 +1+ c)rk vh: f)
Projxz S) = min Dxe (r((u)l rES
(14)
2. Solve for an optimal distribution qº given the optimal clf(g"). For each
('(x) arg min DRL (rll(((())) : Aur (x)
(15)
A key ingredient is the subset of the simplex A comprising probabilities that are more confident about the label y with some margin e. For any A and label y E [K]. Projkr. (u; Ag,e) is convex optimization problem since the objective DKL (rl(rlu)) is convex r and the constraints in A y.c are linear. While we can use a black box convex optimization solver, we solve this more efficiently by reparameterizing into an unconstrained objective and using a fast heuristic approximation (see Appendix D.2 for more details).
Given c(z, y) = Projkr (p(=); AK) for each x, y. the optimization in step can be framed as nie)
an integer linear programming (ILP) problem by using one-hot representation of the optimiz- ing variable h as μ : + 10, with u(r), = 1 for y = h(x) and μıx) 0 otherwise.
The objective then becomes Ex y (())x((X v)] and the constraint Pear h) S fī becomes E|Enftg (X) (x)),, S 77. For each x, we have an additional constraint ΣØ= ((x), = 1. Both the objective and constraints are linear in μ., resulting in an ILP. ILPs are usually inefficient to solve, however, we find empirically that the LP relaxation works very well for this class of ILPs (see Ap- pendix D.I for more details). One issue with solving the ILP is that it can still be slow even with LP relaxation since it involves one constraint for each unlabeled data z. We also can't 't take a small batch size when using stochastic gradient descent since the constraints involve the population means of the weak labeler accuracies. Finally, this is not robust to misspecification of the error bounds, as the constraints might become infeasible. In the next section, we propose method for the learning objective with constraints on distribution (equation 4). Interestingly, we found that it can also be viewed as an approximation of the algorithm presented in this section, yet it overcomes issues of efficiency and robustness, resulting in more practical solution that is effective in both settings.
3.2 LEARNING ORJECTIVE WITH CONSTRAINTS ON DISTRIBUTION
Let Qdist be the set of conditional distributions that satisfy the constraints on distribution,
Qdist nQj.distt where Qj.dist = {q : X A Pdise (9g. g) S %n}}-
(16)
Now, with a similar proof, we would also have a version of Lemma 3.1 for the constraints on distribution, and further d(p, Qdist) bounds the error in satisfying the constraints without the need of imposing any additional constraint.
Proposition 3.6. For Qatat defined in equation 16, we have d(p, Qaist) = 0 if and only if p Qaist- Furthermore, for any v > O there exists 8(v) > O such that if d(p, Q < 8(v) then Prisa (9): P) S n + v/\Syl, where [Sy] Px(S;) is the size of coverage set Sj of weak labeler gj with respect to marginal distribution Px-
This allows us to derive the same alternating minimization algorithm as in equation 10 and equa- tion 11. While the first step is identical, the main benefit of working with the constraints on distri- bution is that the second projection step can be directly posed as convex optimization problem.
min & x]
E[DKL [pxx))
s.t. ( E S 2 1 - 7 Vj E [m].
(17)
We can also derive the optimal solution of equation 17.
5

---

Published as a conference paper at ICLR 2025
Proposition 3.7. Given Qdist defined in equation 16, for any conditional distribution p. the optimal projection o' = arg mingeQam [[ (X) [p(X))) is given by q' = =p> where
(x)) = (x(Z) exp(
Σ
Xip(z),
(18)
(=0;
Zx(x) is the normalization constant. The optimal X is given by the the following optimization:
X
min A
>3 ==1
s.t. Pdica p S nJ Vj [m]
(19)
The optimization for X can solved by coordinate-wis alternating minimization. Given the current iterate X, pick some j, and update X;
min A s.t. Pdist (gj (gj. p^) ((x exp(A)p (X), m X20
(20)
Am). Note that while optimizing for particular coordinate Aj. we only consider the constraint associated with 9j. This can be seen relaxation of the true constraint, which is an intersection of m constraints. While this does not ensure satisfaction of all of the constraints the alternating minimization proceeds, it lends simple method to solve this by a Newton-Raphin root-finding method as follows:
where X-, = (A .A..... 0,
Reset: A 0
Repeat until convergence: A f- A log(1 (1 7t (((hh)))/77(((())) -1))),
(21)
(x))) (x())
T: (h) = ([I()) S.)
For derivations and proofs, see appendix B. For computational efficiency, we also propose a single parallel update for all A; instead of performing the alternating minimization sequentially by using a single step of the above Newton-Raphson method parallelly across all given the starting point
as:
A log(1 + (1 7), - -p))), (p((x) = p())
(22)
This does not give an exact projection of p Qdist: but can be thought of as approximate projection that finds a q that is closer Qdist than p is to Q, on average. Overall, we summarize our learning algorithm (equation 10, equation 11 with our proposed projection step below,
Summary our learning algorithm. We have an alternating minimization algorithm where we track the pair (fr, 9:). Here, ft X + R& is real-valued function from our hypothesis class (e.g., neural networks), and de represents its projection onto the set of distributions that satisfy our constraints. At each iteration
perform the following steps
1. Estimate 9++1 given ft.
(a) Calculate conditional distribution given by fa with softmax function 0,
Pf. (x) = mof e A
(23)
(b) We use a one-step parallel Newton- Raphosn update to calculate xy for each weak labeler (equation 22). For simplicity, for each unlabeled data v; for i = 1,..., we denote the gj (z,) coordinate of p., (x:) as 2ij = Ps, (Z:))) then
R log(1 (1 n
24/+/(
(zt) 21)))),
(24)
Cj i:g (#:)
iigs (
Cj is the number of data points that dj does not abstain, ej = Σn [g,(2;) + 0). (c) Finally, we use À to calculate (2). We first compute the unnormalized version of (r+1.
(x11(1)); P.. (Zx) exp(
Σ 21).
(25)
Then (x+) (x:1 Ek1 (x))

---

Published as a conference paper at ICLR 2025
2. Estimate fi+1 given q++1- This step is equivalent to fitting a fi+1 with respect to the soft pseudo labels given by qt+1. Our loss of ft is given by
[(fe:(+1) (R(f)) +a
Σ (cL(f((2))
where lcz is a cross-entropy loss. We then update f with gradient descent; fe+1 = V
where v is learning rate.
We also provide a compact version of our algorithm Algorithm in Appendix C. Finally, we remark that the sets Qj can also be viewed convex approximation of the constraint sets Qj.eIt (see Appendix E for more details). Therefore, the method developed in this section is also applicable (as an approximation) for the setting of constraints classifiers but it is more efficient and also robust to misspecification in error bounds ny compared to the algorithm in Section 3.1.
THEORETICAL ANALYSIS OF THE OBJECTIVE
In this section, provide some theoretical insights into the denoising effect of weak labeler straints. We focus on the setting of constraints on classifiers (estimation objective equation 2). We learn conditional distribution Pf and thus correspondingly classifier clf(py) that minimizes regularization functional R(f) subjected to weak labeler constraints. Minimizing R(f) implicitly Let
defines hypothesis class of classifiers as F {clf(pr) R(f) 83 for some 5 Hy = {h: X + [K] Pete(gj,)) h) S 1j (here Hj is set of classifiers that differ from Q, which is of conditional distributions).. We learn classifier f F F n N Hj. The constraints lead to smaller class F C F', which implies that typical measure of complexity V of the function class F such Rademacher complexity is also smaller than F. Thus, we can quantify the benefit of the weak labeler constraints via the ratio ((F)/((F). However, such a function class statistical complexity analysis merely makes the natural qualitative point that we require less labeled data to leam from fFr than F. It does not provide bound per on the accuracy of our learned classifier, because we are not using any labeled data to select f.
4.1 ERROR GUARANTEE ON AGREEMENT REGION
Recall that minimize R(f) subject to satisfying constraints. We start with the observation that the weak labeler constraint directly restricts the output of a classifier to be similar to that of the weak labeler in its coverage set. For example, given a weak labeler that makes constant prediction in small region, any linear separator that satisfies the accuracy bound constraint can only slice off the coverage set by fraction of at most 17 (Figure I (left)). This leads to an area the middle where the decision boundary can't I pass through: otherwise, the classifier would differ too much from the weak labeler. This resembles the classical notion of agreement regions (Cohn et al., 1994; Balcan et al., 2006), which we thus use to characterize the impact of weak labelers on F.
Definition 4.1. For of classifiers F, the agreement region is the set of all points where any classifier in F agrees, Agree( F) = { E X' VII. f2 E (1 = [2(x).
Under realizability, we can show that the error of any f E F in the agreement region is zero Furthermore, we can show that as multiple constraints are used, the resulting agreement region will always be larger than or equal to the union of agreement regions for individual constraints. In Figure 1, we provide an example with linear classifiers where the agreement regions from multiple constraints are larger than the union of the agreement region from each individual constraint. This possible explanation of the implicit denoising effect of multiple weak labelers when learning from function class F. Formally, we denote an error of a classifier f within the set S as
erts == (x( + (X) |S).
(26)
Lemma 4.2. For any function class F, and corresponding constrained class F, so long as J E F. for any f E F. err Agroe( (f) =0.
Lemma 4.3. For function class F and constraints H1, H2, we have
Agree(F n (H)) AF n H2) S Agree(F n H, n H2).
7

---

smoothness Published as a conference paper at ICLR 2025
Agmoement reglors
Pasvibii bow dany of lineur separaior
3 Constrant
Consrrants
The figure shows the agreement region of the class of linear separators given two weak labeler constraints: one weak labeler labels red in the red circle, and the other labels blue in the blue circle. A linear separator can only differ from each weak labeler by a fraction of 1) of its support, and therefore the agreement region is given by the middle region of each coverage set (left). The agreement regions from multiple constraints are larger than the union of the agreement region from each individual constraint (right).
Figure 1:
4.2 ERROR GUARANTEE ON THE COVERAGE UNION
In the previous section, we used the geometry of constrained function classes in general. Here, we note that the specific form our constraints (weak labelers error bound) naturally leads to an error guarantee via triangle inequality.
Lemma 4.4. Let Hi = {h: X + [K] Par h) S 15) then for any f E Hgj
errs, (f) S ny + Per Per(
(27)
We show that it is possible to have better guarantee than the combination of the error bound from the triangle inequality when we have multiple constraints with conflicting regions.
Theorem 4.5. Let Hi,..., Hy be constraints of the form H, {h X + [K] Pete Pete h) S n3 ) each with different constant weak labels, gj Nj Hj, we have
9j(X) = for all j = 1, k, then for any f
Pr(S,)
Pr(Ba)
erIs(f) < Σ (ng + Par(oj, 1=1
Σ
(2|0) 3)
(28)
Pr(S)
Pr(S)
oc o ()......
12
when S 5= - Bg = (NiEo Si) n (Nee S are minterms.
The first term on the RHS is the error guarantee from naively combining multiple error guarantees based the triangle inequality. The improvement is in the second term which is the region where weak labelers have a conflict (B,), more conflict leads to a better error bound. The main idea is that whenever there is a conflict, a classifier can match with only one weak labeler. Therefore. to be approximately close to all weak labelers, it must closely match the other weak labelers in areas outside of the conflict. We note that while our result applicable when each weak labeler has different label if we have multiple weak labelers that predict the same label, we can merge them into a super weak labeler by combining the coverage region e.g. S S2 and then derive the new v) as linear combination of 7/, 72 e.g.
Z1 Pr(S, ) Pr(Sa) before applying Theorem 4.5.
P((S))+P((52)
4.3 EXTENDING ERROR GUARANTEES TO ENTIRE INPUT SPACE
The previous two sections provided eπrоr guarantees in subsets of the input space: the first over the agreement region of the constrained function class, and the second on the union the coverage sets of the weak labelers. In this section, provided argument which can be used to generalize beyond the coverage set or the agreement region. Intu- itively, if / performs well on one region, and the underlying probability distribution is smooth then we would expect it to perform well in neighbor region as well.
nuanced analysis based
Theorem 4.6. Let P be a joint distribution over X x such that Pr(Y y XX x)) is L-Lipschitz w.E.t. metric d where for all l = 1,.... K and Tı, E X.
Pr((Y k X =m) Pr(Y
X x2)1 < [d(311
(29)
8

---

Published as a conference paper at ICLR 2025
then for any classifier f and region S, we have
(x(f(X) # Y) Pr(f(X) * Y E S) + Luy(s)
(30)
The terms t (j(S), (S) are distance between Px and Px condition X E
Pr(f(X) = k X E S) Pr(f(X)= = =k)
ty(S) sup
(31)
Pr(f(X) - x X
k
( = Σ Pr(f(X)= k))a ( (x((2)(()==)
(32)
and Wa is a Wasserstien distance and we denote for a distribution Px condition on X E A.
In this theorem, we analyze an error w.t.t to y instead of f since we require the smoothness of the underlying data distribution. The generalization bound is small whenever Px is close to Px E all k. that is, the proportion of label & predicted by f is the same in both original distribution and the distribution conditional on Second, (S) is stronger where is small when the Wasserstein distance is small which is when S covers areas with high probability mass in X. The smoothness of f is implicit in the term (S) in terms of the regions fi f(z) = k}. We provide full proof in Appendix I. We remark that ty (S), y (S) only depends the marginal distribution and, therefore, can be calculated solely from unlabeled data for any classifier f.
condition on X S. First, t is zero whenever Pr(f(X)= = k E) Pr(f(X)= k) for
5
EXPERIMENTAL EVALUATION
Bio
CDR
Chem
IMDB
Semeval
TREC
Yelp
Youtube
Avg. rank
Sup (V)
64.2
59.90.6
35.91.1
64.31.3
59.63.0
52.13.7
73.41.4
80.91.2
6.8
MV
56.40.4
68.4g.4
52.6p.5
75.70.7
65.32.5
37.31.1
69.1p.5
82.2g.6
5.8
Snorkel
63 63.4
61.2n.4
41.81.0
71.3n.6
59.21.0
33.41.7
71.8p.9
76.81.a
7.8
LoL(S)
55.5p.s
67.40.1
51.60.1
75.30.6
53.42.0
38.72.8
70.61.4
79.1p.9
7
Ours (C)
63.5
68.50.7
52.20.8
74.31.s
67.52.1
46.72.7
78
78.60.5
80.71.3
4.6
Ours (V)
62.6p.s
67.9p.5
53.3p.s
72.51.1
79.42.4
63.12.1
75.3p.7
90.21.4
4.1
Sup (T)
75.4p.s
80.7u.s
80.1u.2
81.40.6
82.91.9
66.92.3
87.0p.3
89.7p.6
1.1
Ours (T)
64.8p.7
69.1o.2
55.60.3
74.81.1
77.31.4
66.32.9
78.3p.3
88.0p.4
2.8
(T))
60.90.9
66.0o.4
49.80.7
73.31.0
81.01.9
57.21.2
75.8p.5
87.3p.3
5.1
Table 1: Average test accuracy and the corresponding standard error (over 5 random train-val-test split of the data) of our proposed algorithm and the baselines. We bold methods that are within standard error of the best-performing method. Sup (T) and Sup (V) are supervised learning on the training set and the validation set respectively. MV, Snorkel, and Lol(S) are Majority vote, Snorkel, and Losses over labels (Simple) baselines. Ours is our proposed method (Algorithm 1) with different ways to estimate the error bound 175. Ours (V) is when we estimate 77 from the labels from the validation set, given Beta(1, 1, 2) prior. Ours (C) when we use constant ny and tune this on the validation set. Ours (T) is when yi is estimated from the labels from the training set. Finally, Ourseir our algorithm with respect constraints on the classifier (Section 3.
We show a comparison of proposed method and baselines 8 text clas- sification datasets from the WRENCH benchmark Zhang et al. (2021). We provide the dataset statistics in Appendix G.I. For all methods and datasets, we use neural network with a single hidden layer and a hidden size of 16 on top of the pre-trained BERT text embeddings. The neural network is trained with a full batch gradient descent with an Adam optimizer with learning rate in [0.001, 0.003, 0.01]. weight decay in [0.001, 0.003, 0.01] and number of epochs in range(1, 500, 5). We tune these hyperparameters on the validation set of size 100 for each dataset. For our proposed method, we implement Algorithm with an L2 regularization. Since the WRENCH benchmark does not provide error bounds 77 for each weak labeler, we consider strategies to estimate 7/5 i) estimate ΠΙ from the labels from the validation set, given Beta(1, 2) prior, ii) we treat n, as a fixed constant 7 for all weak labelers and tune this r on the validation set, iii) we estimate 7 from the labels from the training which we treat as ground truth error of each weak labeler.
Experiment details:

---

Published as a conference paper at ICLR 2025
See Appendix F for more details estimating error bound from the vaildation set. Finally, also implement our algorithm with respect to constraints on the classifier (Section 3.1) with linear programming relaxation of the integer linear program (see Appendix G.3 for more details).
Baselines: We compare with three baselines: Majority Vote (MV), Snorkel Metal (Ratner et al.,
2017) and Losses over Labels simple (LoL. (S)) (Sam & Kolter, 2023). The majority vote and Snorkel are two-staged approaches where we first aggregate weak labels and then train neural network on the aggregated labels. The Majority vote simply takes the majority vote between the non-abstain weak labels for each data point while Snorkel deploys a latent generative model to estimate soft labels from the weak labels. On the other hand, Losses over Labels (simple) one-staged approach that directly minimizes a weighted linear combination of the loss with respect to each weak labeler. We also compare to a baseline of simply performing supervised learning on labels from the validation set, to avoid concerns regarding possibly large validation sets as raised by Zhu al. (2023).
Results: Our proposed method (Ours (V)) is the best performing approach compared to other base- lines (Table 1). This does not solely come from the fact that we have a large number of labels in the validation set since supervised learning on the validation set (with the best hyperparameters) still performs worse than ours on almost every dataset. Surprisingly, our method with a constant 77 (Ours (C)), also performs competitively and is the second best performing approach overall. On the other hand, having access to a more accurate error bound can lead to a performance increase across the board (Ours (T)). In addition, we found that most constraints satisfied by the models trained by our algorithms (see Table G.2).
Ablation on noisy weak labeler error bounds: We assume that the error bound πi is given form of domain knowledge (or estimated from small validation set). As such, we may have f) that can be far from the ground truth error. In this section, we explore this impact on the performance of our algorithm and we do so by adding noise to the "ground truth" пι (estimated from the training labels), given by fij M7 + E, Uniform(- (-ato a) and use îī as inputs of our algorithm. We see that our algorithm is quite robust and the performance drops graciously as the noise level increases (Figure 2).
Bioresponse
CDR
80
Chemprot
Acc
IMD8
Semeval
Test
70
Trec
Youtube
60
0.0
0.1
0.2
0.3 Noise
0.4
0.5
Figure 2: Impact of using noisy error bounds 7, fΙ + e, Uniform(-a, a) for E [0, 0.5). The accuracy averaged over 5 random splits of data and the shaded area is the standard error.
6 CONCLUSION
In this paper we provided principled approach to learn from weak labelers weak classifiers that label subset of the input space, without making stringent assumptions about dependencies between them, or about their noise model. Instead, we consider the expected error / accuracy as the only source of information that characterizes the weakness of labelers. This information can either be given by domain experts or can be estimated from a small amount of labeled data given only weak prior on the accuracy. We finally proposed a robust and scalable algorithm that can learn from multiple noisy weak labelers even when only noisy estimates of expected errors are provided. An interesting future direction could be to combine information about dependencies between weak labelers when such information is given along with the information about the expected error, well as developing alternative techniques based on mixed integer linear programming for solving our constraint-bant based approach to aggregate weak labelers by viewing the accuracy bound constraint.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We acknowledge the support of NSF via 118-2211907 and IIS-1901403, ONR via N00014-23-1- 2368 and Bloomberg Data Science Fellowship.
REFERENCES
Dana Angluin and Philip Laird. Learning from noisy examples. Machine Learning, 2:343-370, 1988.
Chidubem Arachie and Bert Huang. Constrained labeling for weakly supervised learning. Uncer- tainty in Artificial Intelligence, pp. 236-246, 2021.
Aragam, Dan, Xing, and P Ravikumar. Identifiability of nonparametric mixture models and bayes optimal clustering. The annals of statistics, 48(4), 2020.
Abhiject Awasthi, Sabyasachi Ghosh, Rasna Goyal, and Sunita sarawagi. Learning from rules generalizing labeled exemplars. arXiv preprint arXiv:2004.0602) 2020.
Pranjal Awasthi, Maria Florina Balcan, and Philip M Long. The power of localization for efficiently learning linear separators with noise. In Proceedings of the forty-sixth annual ACM symposium Theory of computing, pp. 449, 2014.
Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Ruth Urner. Efficient learning of linear separators under bounded noise. In Conference on Learning Theory, pp. 167-190. PMLR, 2015.
Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Hongyang Zhang. Learning and 1-bit compressed sensing under asymmetric noise. In Conference on Learning Theory, pp. 152-192. PMLR, 2016.
Pranjal Awasthi, Maria Florina Balcan, and Philip Long. The power of localization for efficiently learning linear separators with noise. Journal of the ACM (JACM), 63(6):1-27, 2017.
Stephen H Bach, Bryan He, Alexander Ratner, and Christopher Ré. Learning the structure of genera- tive models without labeled data. In International Conference on Machine Learning, pp. 273-282. PMLR, 2017.
Maria-Florina Balcan and Nika Haghtalab. Noise in classification. https::/arxiv..ore / 2010. 05080.00000 pdf, 2020.
Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. In Pro- ceedings of the 23rd International Conference on Machine Learning, pp. 65-72, 2006.
Dimitri P Bertsekas. Constrained optimization and Lagrange multiplier methods. Academic press, 2014.
Avrim Blum, Alan Frieze, Ravi Kannan, and Santosh Vempala. A polynomial-time algorithm for learning noisy linear threshold functions. Algorithmica, 22:35-52, 1998.
Paul T Boggs and Jon W Tolle. Sequential quadratic programming. Acta numerica, 4:1-51, 1995.
Salva Rühling Cachay, Benedikt Boecking, and Artur Dubrawski. End-to-end weak supervision. In A. Beygelzimer, Y. Dauphin, Liang, and Wortman Vaughan (eds.), Advances Neu- ral Information Processing Systems, 2021. URL https:tt////c ptst:s://operreviii ew. net fott/oorrmiii gbcsmD311 3Izn..
Nicolo Bisn-Bianchi, Eli Dichterman, Paul Fischer, Eli Shamir, and Hans UIrich Simon. Sample- efficient strategies for learning the presence of noise. Journal of the ACM (JACM), 46(5): 684-719, 1999.
Nontawat Charoenphakdee, Jongyeong Lee, and Masashi Sugiyama. On symmetric losses for leam- ing from corrupted labels. In International Conference on Machine Learning, pp. 961-970. PMLR, 2019.
11

---

Published as a conference paper at ICLR 2025
Mayee F Chen, Daniel Y Fu, Dyah Adila, Michael Zhang, Frederic Sala, Kayvon Fatahalian, and Christopher Ré. Shoring up the foundations: Fusing model embeddings and weak supervision. In Uncertainty in Artificial Intelligence, pp. 357-367. PMLR, 2022.
Yudong Chen and Martin Wainwright. Fast low-rank estimation by projected gradient descent:
General statistical and algorithmic guarantees. arXiv preprint arXiv:1509.0302 2015.
Edwin KP Chong, Wu-Sheng Lu, and Stanislaw H Zak. An Introduction Optimization: With Applications to Machine Learning. John Wiley & Sons, 2023.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. international conference on machine learning, pp. 1310-1320. PMLR, 2019.
David Cohn, Les Atlas, and Richard Ladner. Improving generalization with active learning. Machine Learning. 15:201-221, 1994.
David W Coit, Alice E Smith, and David M Tate. Adaptive penalty methods for genetic optimization of constrained combinatorial problems. INFORMS Journal on Computing, 8(2):173-188) 1996.
George B Dantzig. Linear programming. Operations research, 50(1):42-47, 2002.
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Being robust (in high dimensions) can be practical, 2018.
Ilias Diakonikolas, Themis Gouleakis, and Christos Tzamos. Distribution-indeeedder pac learning of halfspaces with massart noise. Advances in Neural Information Processing Systems, 32, 2019a.
Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high dimensions without the computational intractabilityy 2019b.
Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi, and Lisheng Ren. Cryptographic hardness of learning halfspaces with massart noise. Advances in Neural Information Processing Systems, 35: 3624-3636, 2022a.
Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning general halfspaces with general massart noise under the gaussian distribution. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 874-885, 2022b.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pp. 265-284. Springer, 2006.
Enrique Estellés-Arolas and Fernando Lonrález-Ladróndde Guevara. Towards integrated crowd- sourcing definition. Journal of Information science, 38(2): 189-200, 2012.
Michel Fortin and Roland Glowinski. Augmented Lagrangian methods: applications to the numeri- cul solution of boundary-value problems. Elsevier, 2000.
Marguerite Frank, Philip Wolfe, et al. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2):95-100, 1956.
Daniel Fu, Mayee Chen, Frederic Sala, Sarah Hooper, Kayvon Fatahalian, and Christopher Ré. Fast and three-rious: Speeding up weak supervision with triplet methods. In International Conference on Machine Learning, pp. 3280-3291. PMLR, 2020.
Kuzman Ganchev, Joao Graça, Jennifer Gillenwater, and Ben Taskar. Posterior regularization for structured latent variable models. The Journal of Machine Learning Research, 11 11:2001-2049, 2010.
Philip E Gill, Walter Murray, and Margaret H Wright. Practical optimization. SIAM, 2019.
Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. Advances in neural information processing systems, 31, 2018
12

---

Published as a conference paper at ICLR 2025
Bo Han, Gang Niu, Xingrui Yu, Quanming Yao, Miao Xu, Ivor Tsang, and Masashi Sugiyama. Sigua: Forgetting may make learning with noisy labels more robust. In International Conference on Machine Learning, pp. 4006 4016. PMLR, 2020.
Earl O Heady, Candler Wilfried, et al. Linear programming methods. Linear programming methods., 1963.
Zhiting Hu, Xuezhe Ma, Zhengzhong Liu, Eduard Hovy, and Eric Xing. Harnessing deep neural networks with logic rules. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics ( (Volume Long Papers), pp. 2410-2420, 2016.
Giannis Karamanolakis, Subhabrata Mukherjee, Guoqing Zheng, and Ahmed Hassan Awadallah. Self-training with weak supervision. arXiv preprint arXiv:2 10::22204.0514 2021.
Davood Karimi, Haoran Dou, Simon K Warfield, and Ali Gholipour. Deep learning with noisy labels: Exploring techniques and remedies in medical image analysis. Medical image analysis, 65:101759, 2020.
George Em Karniadakis, Ioannis G Kevrekidis, Lu Lu, Paris Perdikaris, Sifan Wang, and Liu Yang. Physics-informed machine learning. Nature Reviews Physics, 3(6):422-440, 2021.
Hiroyuki Kasahara and Katsumi Shimotsu. Non-parametric identification and estimation of the number of components in multivariate mixtures. Journal of the Royal Statistical Society Series B: Statistical Methodology, 76(1):97-111, 2014.
Michael Kearns and Umesh Vazirani. An introduction to computational learning theory. MIT press, 1994.
Zhaobin Kuang, Chidubem Arachie, Bangyong Liang, Pradyumna Narayana, Giulia DeSalvo, Michael Quinn, Bert Huang, Geoffrey Downs, and Yang Yang. Firebolt: Weak supervision under weaker assumptions. In International Conference on Artificial Intelligence and Statistics 2022, 2022.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning at scale. In International Conference Learning Representations, 2016.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference Learning Representations, 2018.
Pascal Massart and Élodie Nédélec. Risk bounds for statistical learning. 2006.
Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine learning. ACM computing surveys (CSUR), 54(6):1-35, 2021.
Nagarajan Natarajan, Inderjit S Dhillon, Pradeep Ravikumar, and Ambuj Tewari. Cost-sensitive learning with noisy labels. Mach. Learn. Res., 18(1):6666-568.
Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. Advances in neural information processing systems, 26, 2013.
Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, and Pradeep Ravikumar. Robust esti- mation via robust gradient estimation. Journal of the Royal Statistical Society: Series (Statisti- cal Methodology), 82, 2018. URL https: / http::p:///pp...aaattassseeeeeee wttp:/ora...//oooouuDDD0.0I 3614648.
Adarsh Prasad, Vishwak Srinivasan, Sivaraman Balakrishnan, and Pradeep Ravikumar. On learning ising models under huber's contamination model. Advances in neural information processing systems, 33:16327-16338 2020.
Rattana Pukdee, Dylan Sam, Pradeep Kumar Ravikumar, and Nina Balcan. Label propagation with weak supervision. In The Eleventh International Conference on Learning Representations, 2022.
13

---

Published as a conference paper at ICLR 2025
Rattana Pukdee, Dylan Sam, J Zico Kolter, Maria-Florina Balcan, and Pradeep Ravikumar. Learning with explanation constraints. Advances in neural information processing systems, 2023.
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, pp. 1-4, 2018
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 En- dowment. International Conference on Very Large Data Bases, volume 11, pp. 269. NIH Public Access, 2017.
Alexander Ratner, Braden Hancock, Jared Dunnmon, Frederic Sala, Shreyash Pandey, and Christo- pher Ré. Training complex models with multi-task weak supervision. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4763-4771, 2019.
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.
R Tyrrell Rockafellar. Lagrange multipliers and optimality, SIAM review, 35(2):183-233 1993.
Dylan Sam and Zico Kolter. Losses over labels: Weakly supervised learning via direct loss construction, 2023.
Hwanjun Song, Minscok Kim, Dongmin Park, Yooju Shin, and Jae-Gil Lee. Learning from noisy labels with deep neural networks: A survey. IEEE Transactions on Neural Networks and Learning Systems, 2022.
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.
Kerri Wazny. "crowdsourcing" ten years in: A review. Journal of global health, 7(2), 2017.
Xiaobo Xia, Tongliang Liu, Nannan Wang, Bo Han, Chen Gong, Gang Niu, and Masashi Sugiyama. Are anchor points really indispensable in label-noise learning? Advances in neural information processing systems, 32, 2019.
Xiaobo Xia, Tongliang Liu, Bo Han, Nannan Wang, Mingming Gong, Haifeng Liu, Gang Niu, Dacheng Tao, and Masashi Sugiyama. Part-dependent label noise: Towards instance-dependent label noise. Advances in Neural Information Processing Systems, 33:7597-7610, 2020.
Özgür Yeniay. Penalty function methods for constrained optimization with genetic algorithms. Mathematical and computational Applications, 10(1):45-56 2005.
Xingrui Yu, Bo Han, Jiangehao Yao, Gang Niu, Ivor Tsang, and Masashi Sugiyama. How does dis- agreement help generalization against label corruption? In International Conference on Machine Learning, pp. 7164-7173. PMLR, 2019.
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In International conference on machine learning, pp. 325-333. PMLR, 2013.
Jieyu Zhang, Yue Yu, Yinghao Li, Yujing Wang, Yaming Yang. Mao Yang, and Alexander Ratner. Wrench: A comprehensive benchmark for weak supervision. Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
Jieyu Zhang, Cheng- Yu Hsieh, Yue Yu, Chao Zhang, and Alexander Ratner. A survey on program- matic weak supervision. arXiv preprint arXiv:2202.0544 2022.
Jieyu Zhang, Linxin Song, and Alex Ratner. Leveraging instance features for label aggregation in programmatic weak supervision. In International Conference on Artificial Intelligence and Statisties, pp. 157-171. PMLR, 2023.
14

---

Published as a conference paper at ICLR 2025
Wen Li Zhao, Pierre Gentine, Markus Reichstein, Yao Zhang, Sha Zhou, Yeqiang Wen, Changjie Lin, Xi Li, and Guo Yu Qiu. Physics-constrained machine learning of evapotranspiration. Geo- physical Research Letters,
Dawei Zhu, Xiaoyu Shen, Marius Mosbach, Andreas Stephan, and Dietrich Klakow. Weaker than you think: A critical look at weakly supervised learning, 2023.
Yinhao Zhu, Nicholas Zabaras, Phaedon-Stelios Koutsourelakis, and Paris Perdikaris. Physics- constrained deep learning for high- high-dimensional surrogate modeling and uncertainty quantification without labeled data. Journal of Computational Physics, 394:56-81, 2019.
15

---

Published as a conference paper at ICLR 2025
A ADDITIONAL RELATED WORK
A.1 PROGRAMMATIC WEAK SUPERVISION.
Programmatic weak supervision Ratner et al. (2016), is learning paradigm where subject matter expert encodes their domain knowledge in terms of weak labelers (labeling functions). These are functions that either provide labels (weak labels) or abstain from prediction on any input. The key question is how to learn from such weak labels that are potentially noisy. A general approach in- volves two steps of aggregating weak labels into less noisy labels and then training discriminative classifier on the inferred labels. Various statistical label models have been developed for label ag- gregation, and most of these only depend on the weak labels Ratner al. (2016; 2018; 2019); Bach et al. (2017); Varma et al. (2017); Fu et al. (2020); Kuang et al. (2022). Recent methods incorpo- rate the input information into this weakly supervised learning pipeline Chen al. (2022); Pukdee et al. (2022); Zhang et al. (2023) e.g. smoothness of the label with respect to the input instance or pretrained-embeedding. Alternatively, there is line of works that learns from weak labels in an end-to-end fashion. The label model and the discriminative model are parameterized and are trained jointly Cachay et al. (2021); Karamanolakis et al. (2021); Awasthi et al. (2020); Sam & Kolter (2023). A key prior work is constrained label learning Arachie & Huang (2021), which involves learning pscudo labels under constraints before training a discriminative model. Unlike our method, CLL's initial step is independent of the function class and remains a two-step process.
A.2 LEARNING WITH NOISY LABELS
Learning from data with noisy labels has been a prominent research problem that has received sub- stantial attention from the machine learning community. The main assumption is that the observed labels are flipped with some probability. There is line of works in theoretical machine learning that focuses on the learnability and polynomial-time algorithms for various noise models Kearns & Vazirani (1994); Cesa-Bianchi et al. (1999); Angluin & Laird (1988); Awasthi et al. (2014; 2015); Diakonikolas et al. (201 9a); Balcan & Haghtalab (2020). On the other hand, in the statistical learning theory community. various works concerned with different surrogate losses unbiased estima- tors Natarajan et al. (2013); Prasad et al. (2020); Natarajan et al.; Charoenphakdee et al. (2019);
Xia et al. (2019; 2020). Recently, numerous studies have focused on learning noisy labels on deep neural networks Song et al. (2022); Karimi et al. (2020); Yu et al. (2019); Han et al. (2018; 2020). Despite rich theoretical and empirical research in this area, these approaches cannot be employed in our context since the noisy labels in our setting are deterministic given the input and label.
A.3 LEARNING FROM CONSTRAINTS
Constrained optimization focuses on finding the optimal solution to a problem within given con- straints Bertsekas (2014); Gill et al. (2019); Chong et al. (2023). The principal method involves con- verting the constrained optimization problem into an unconstrained one. This can be accomplished by adding auxiliary variables, as seen in the Lagrange multiplier method Rockafellar (1993), or by incorporating a penalty term that penalizes the objective function when constraints are violated Coit al. (1996); Fortin & Glowinski (2000); Yeniay (2005). Additionally, gradient-based approaches like PGD include a projection step to ensure the solution stays within a feasible region after each up- date Chen & Wainwright (2015): Madry et al. (2018). For specific types of constraints such as linear or quadratic. there are dedicated algorithms designed to address these constrained scenarios Heady et al. (1963); Dantzig (2002); Frank et al. (1956); Boggs & Tolle (1995). In the field of machine learning, the optimization goal is the empirical loss, and constraints can be used to enforce desirable features in a machine learning model, such as fairness Zemel et al. (2013); Mchrabi et al. (2021), robustness Cohen et al. (2019); Kurakin et al. (2016), or privacy Dwork et al. (2006). Recent studies have begun incorporating constraints derived from domain knowledge into models, such as physics constraints Zhao et al. (2019); Zhu et al. (2019); Karniadakis et al. (2021), 1). explanation constraints Pukdee et al. (2023), and weak supervision Ganchev et al. (2010); Hu et al. (2016), with the aim of improving model performance.
16

---

Published as a conference paper at ICLR 2025
B PROOFS OF PROPERTIES OF PROJECTION LOSS AND COMPUTING THE PROJECTION
Lemma B.1. For Qett defined in equation 5, i.e.
Qet = Nsiett where Qj.ett = {q X - A Par(g); clf(4)) S $n
(33)
where
Par Par(gj clf(g)) =B(g (X) * clf clf(g) 93 (X) #
(34)
and clf(g) is defined as
(l)(g) = arg max (z)
(35)
(assuming arg maxy ((r) is unique. If arg max, ((,), is not unique for some then cQ) is not
well defined.)
then for any such that clf(p) is well defined, gequ [[Dxxx((xx)l((()))]]======+++ if and only if E Qeir.
we
have d(p, Qai)
Proof. If p Qai, we would have d(p, Qai) S Dx (XX)))(())) 0. Conversely when d(p, Qetr) = we prove that p E Qei i.c Par p) S ni for all j E [m].
First, we prove that
inf rEQar
(pdrv(p(X), ((()) =
(36)
where drv is defined as
dTv(u, (u, v) 1122- Σ Up Un
(37)
Using Pinsker's inequality,
drv drv S v (ull(ul)))
(38)
we have
(ldrv(((X)..(x))) ((x))v(((X),
(39)
I BBVVDRI DKL (p( X) x))]22
(40)
S E (p( ()l)( (from Jenson's
(41)
Thus
inf ((drv(((X), gEQui
inf gEQui
v VEIDxu,(xXX))ll(
(42)
<
inf ([DKI,((XX)]lO(X)) qeRar
(43)
V
50
(44)
Let us say p & Qetr. there exists some 0 such that Per pgr(gg)p) n1 for some [m]]
Pr(as(X) + cll()) E S;) 2 `] +
(45)
where S, fa : (x) + o) the coverage set of gj. Let S' S S, defined S' fz g (x(x) +
(f((p))z) Denoting |S| = Pr(X E S), since |S'\/|S,| 2 n; + c, and assuming |S,] > 0, we have [S*] > 0.
Now for any g E Qatr, we have
Pr(cff(g)(X) *
(x) +
e 8,) s
(46)
Then
Pr(clf())(X) # (x)) E SJ) = Pr(cIf()(()) # (X) E S'
E S,)P(X S' E S,)
(47)
Pr(cl((g) + x E' S)/P(X E S,)
(48)
(x) S') E S') SJ)
(49)
=Pr(df(()()) # (()S((11S))))
(50)
17

---

Published as a conference paper at ICLR 2025
Thus,
(x) ES) (x(d
+ (x(X) E S)SSSs//SS
(51)
/n
(52)
$ / +c)
(53)
Hence,
Pr(c)f(g)( = 5*) Pr(clf(()( + 9X(X S*)
(54)
2 - mz/(n; +.)
(55)
</(n; +
(56)
Since clf(p)(x) * (z) for x e S clf(g)(z) gy (z) implies clf(p) & clf(g)(x)). Thus
(r(clf(g)( # (x) E S*) 2 c/(n) +c)
(57)
Let S" = fx clf(()(()) + cl((p) we have
Pr(X E viXEs"XX (E 2 2 c/(ng +c)
(58)
And thus,
S Pr(X X S')P(X E S') P(X E S" X E P(X
(59)
Pr(X E P(X E (
(60)
P(X S*) 2 e/(nj +e)
(61)
S 2 +
(62)
Now let
mlz) =
max p(=))t(()(()) -p(x)
(63)
(x)ll(g)
For clf(p) to be well defined, u(x) must be greater than 0, i.c. μ(x) > for all z.
Since (z) (x) for a E S", we have for any S"
p(z)a((p)()) 2 p(z) + p(x)
(64)
((=)ett(a()) (()))t())())
(65)
Or
p(z) 2 p) + m(z)
(66)
(()))1()(() 2 -(())d(())())
(67)
p(z)ar(())))) ) 2 p(z)ar(()(()) ((=)))())()) + u(x)
(68)
(p(x)af())))) - ((a)aann http::/aaaaaaaaappaaaaalaaaa 2 p(z)
(69)
(p())ar0)()) ( (1le)artoocce)HHp///aaarroo0 - {(x))t(()))) 2 M(x)
(70)
(()) 2 p(x)/2
(71)
(p(X), 5"] Elu(X)/2|X e S"]
(72)
Since inf gear (pd)) 0, there exists some q Qai such that E[dry (p. (p(X). <
(X) $]
(73)
for any set S with |S| > 0. In particular this holds for S" since [S"| > 0. Then s")]
(p(rv(p((X.rr. q(X)) 2 (p(X), (pX), e s"I Pr(X E S e s"[[s"
(74)
(75)
(76)
Thus
Eldrv(p(X), (p(X), ("" e s"1
(77)
E(dTv(v(X) (X)))X E 5")) < E|a(X)/2)X x ES)
(78)
which leads contradiction.
18

---

Published as a conference paper at ICLR 2025
Lemma B.2. Let Q {q clf(g) H} for some set H. of classifiers. For any classifier f and any é > 0, there exists a conditional distribution p such that clf(p) = f and d(p, Q) c.
Proof. We claim that for any classifiers fi. fa there exists sequences of conditional distributions fei) (42 such that clf(gi) f1, (gb) f2 for all t, and lime gi = lime 02 The main idea is that we can slightly perturb uniform distribution to achieve any classifier. Formally, for lo * f1 (z) and of (z),
K + 5/t for k = fi (x), where K [ is the number of classes. We can define d in the same manner. It's clear that both sequence converges to uniform distribution, that is, lim of (2) lim (b(z), 1 K for all x, even when fI, f2 are completely different.
we define oi (r)x = 11/K - -8/(KK - -))
Now for any classifier h E H. and any classifier f. there exists sequence {gf J. {ot) such that clf( ) h. ell((})) f for all and that lim4-xo gh lime-so of. Since clf(g)) h, know that q%. E Q and this implies that
lim Q) = lim min E[DRr (xX))l])
(79)
qEQ
- lim E[DxL (af (X) (X)]lg) (x))] = 0.
(80)
t+000
The last line comes from the fact that lim gh = lim gj. As a result, we can conclude that for any there exists some for which p = o% satisfies d(p, Q) < and clf(p) f.
Proposition B.3. For any e. > O there exists 8(c, > such that if d(p, n Qai)) < ò(e, v) then parlgg, (p)) S n1y + v/ where |S Px(X E SJ) is the size of coverage set S3 of weak labeler 9j with respect to marginal distribution Px. In particular 8(c,v) vL(e) where L(c)
(1-v)
is a strictly increasing function in given by
(1 (L+0) c) log(1 te) - ( E/2))
L(e)
(81)
K+
where K is the number of classes. The bound can be rephrased as the following inequality: For all p such that d(p, Qat) L(c), we have
d(p, Qa1)
Par(g), clf(p)) S ny + (L(e) - d(p, 15
(82)
where Qai = A₂ n QaI-
Proof. First, we prove the following
Parlgr clf(p)) S my + min dar(p, s)/1s,
(83)
4EQar
where der(p.g) 9) is defined as
dar(p.9) = Pr(clf(p)(X) # (cl(()((X))
(84)
Parlg,,clf(g = + Sy)
I x (x) cl(( x E S3) + + + E S,) for all
Thus
# (x) (ar(g),cl((p)) < min x E,) X
# (x)
E S,
qEQua P
< min qEQar X
e S,) + max Pr(clf(g)(X) # xx(x)|x e S,
QEQar X
< min Pr(clf(p)()) * clf e 5,) +
yEQur x
min
+ (l)))) E 8 + +
qEQai x
min
rEQur X
= y + min dar(p, 4)/18}1 gEQar
19

---

Published as a conference paper at ICLR 2025
Next, we will prove the bound on inf yequr dei((p.)) 9), ie.
d(p, Var)
inf (pr 1 (L(c) d(p, Qar)) gEQas
(85)
For any conditional distributions p.q X - A define the following
da(p, v) - E[DRI.(T (1(X))l((X))
(86)
(p, = E[DRL (9 (X) = clf(
(87)
(v. = [E[DOI (x(X)ll((X) el) + clf())(X)
(88)
Consider the following sublemma. Sublemma B.3.1. For any Var. if dp L(c) then
dx(p, 4)
dar(p, - L(e) dha(p.))
(89)
where
L(e) inf (p,
(90)
The bound in equation 85 directly follows from the above sublemma. This is proved as follows.
inf neQur
dar(p, 4) = inf deir(p, 4)
gefaa
dp 9)
S inf
QEQui L(c) - (p 9)
I infgeQ'a (p, 9)
supgeRS. L(e) dp 9)
infge (p. q)
L(e) infaeRua (p 9)
d(p, Qair)
L(c) d(p, Qair
Finally díp, Qar) < vb(e) (1-v) gives us inf dar (pr(pp)) q) S u. and thus par(g; elf(p)) S w/18,1+1 +
Now proof sublemma B.3.1. First note that,
dxi(p,4) 4) = dar(p, () + (1 - dete (p, ()) 9)
(91)
Now
(p, da(p, 1) darlp. (p.
- dar(p, 9)
da(p, 9) der(p, L())
1 - dar(p, q)
dei( q) dar(p,))
S daa(p.g) + (duilp, 4) I((e))
< <da(p.g)
Further,
der(p..) = dx(l..) (p.9)
de 9) (p,
$ ()
dp 9) (t
dal 9)
L(c) (p((p.))
20

---

Published as a conference paper at ICLR 2025
Now are only left to prove the form of L(c) given in equation 81.
Recall A, was defined in equation 12 as
Ag {q X + A k for each x, Fy g(x), 2 (1 + +)((2) for k + y}
(92)
For distribution E A let oj (u) refer to the top j class, i.e. ei (u).... cx (x(") is permutation of [K] s.t. Mer(u) Me. Mex (u)- Let (u) refer to the corresponding probability i.e. (u) (e)(w))
Let de (u AK (u) 2 (1 ()t Vj 1}. This is connected to A,
A. fq: X + A K Vz, (()) E dc}
Now
I(e) inf (a(l.
(93)
PEVan
inf E[DkL (F()) (X) # clf(g)(X)) NEH.P (x)
(94)
PEQar
inf E[ inf
# c1(1]
(95)
(where H = (h: Pett (a5( h9):h) S n;²))
(96)
inf [
inf
[Kr(uulu)]
(97)
NEWL
inf
DKL (ull))
(98)
inf (ullu) (i()) # (1)), 2 (1 (1) Vj urEAA
(99)
Now without loss of generality, let (u()) = j. With some abuse of notation, we also use u, v to refer to the minimizer of objective in equation 99. The minimizer exists since the constraints induce closed sets. Then first we will prove that
()() = ej (w) = j for j 2 3
(100)
Assume the contrary.
Then there exists 2 such that 2/ > 02. This implics
(U2 - up) (1, / U2) >
(101)
uy log(1/U2) + uh log(1 ox) uy log /v) us log(1 /02) U2 log(uz) u2 (22 ) + uh log( uu ox)) > u2 log (2//u/// /vx) + u log(ux/v) (Ux//2)
(102)
(103)
(ullv) (ul('))'')
(104)
where of defined as
v/2 Uk; v/ U2, U2 = Uj for k, But u, e was the minimizer of the objective in equation 99, which contradicts the above implication in equation 104.
(105)
Since (u) = 1 + (u),, we get c1 (u) = 2, and c2(u) = 1. To recap we have
(u(u) = (r)) 22 (1) 1,))()) j for j 3
(106)
(107)
Next we will prove that
U2
(108)
Let
(v2 11
(109)
(v2 + 21)
(110)
Since (u) 2, 02 2 and so x, y 2 0. We have
= y
(111)
0/ = y + x
(112)
K
Ug = 1 - 2y
(113)
j=3
21

---

Published as a conference paper at ICLR 2025
Now,
K
L(c) un log(u1/y x) + u2 log (2g(u//3) + x) + Σ jm3
ug log(u,/o))
Vx((e) = /n /y - x) - u2 x)
"1 (y + x) - (y - x) 8² - x²
s(u + U2) y(u1 -22)
y² y²-x² x²
> 0
Thus T(e) is minimized for O.
Next, we have the following inequality
aj log(a; 2
C: log
ai/
bi)
(114)
i=1
i=1
This follows Jenson's inequality, given a discrete distribution f: Ex=
fi 1, we have
Σ fa log(t)) 2 log( Σ fit))
Substituting fi a:/ Em=1 ai and t; b we get the required inequality. We use this inequality to have
K
Σ 5=3
ug log(u,/0g)
log(
(115)
j=3
This gives us
1 U1 U2
L(e) 2 un log(ui/v1) + u2 log(u2/v2) + (1 21 - u2) log
(116)
1i - 1/2
We had ey = 12. So, substituting 01 = = we have
L(E) 2 f(v) = log /vy + u2 log u2 / + (1 - U1 U2) log
1/2
1 2y
2(1 11 U22)
V (y)( = 11/1//1111 u2/y
2y
2y U1 U12
1 1 2y
2(1 - 112) 0
(1 - 22y)²
Thus f(y) is minimized for v = O, giving y = 01 = U2 = (u1 + u2) Substituting in equation 116, we get
L(e) 2 in log (ui + u2)) + u2 log(2u2/ (1i + u2))
(117)
Let x = -wi - / 2 (and thus /n = = + x, u2 = y - x) we have
L(e) 2 f(x) = (o++))og(1++/// + (y - log( x/y))
vef(x) =
log(1 =/y) >
Since 41 2 (1 + e)ug, we have y + x (1+ z), thus f(x) is minimized for x = yc/(2 + c).
Using y = (u) + 22, we have
L(e)= > (n1 + u2) ((1 / + log (2 e)/(2 + e)) + 2// + log(2/ e))) ((1 +) - (2 + c) log(1 + c/2))
"n + u2
2
22

---

Published as a conference paper at ICLR 2025
Now to bound U1 + u2, consider the following.
Since Ug I U22 for j 2 3. we have
K
(K - 1)u2 2 Σ
Uj U1
j=2
- iI
02 2
K -
1 + 11 (K - 2)
u2
K -
Further since (1 E)uy for 2 have,
(K (K-1)ut 2 (1 Σ Uj
f=2
" 2 (1 + e) - U1
K -
lte
" 2
K +c
Substituting back we get
2+
m1 + 2
K +e
Substituting in the bound for L(e) we finally get
[(c) 2 (1 + e) log(1 E) - + E) log(1 + t/2)
(118)
K +
Now to prove L(e) is strictly increasing and positive for e > 0, we have L(0) = 0 and
V.L(c) = v.f(c)/(K + f(c)(K +c)²
K 1) log (K - log(1 c/2)
(K + c)²
Proposition B.4. Given == AenQeit for A, defined in equation 12 and Qai defined in equation 5, for any conditional distribution p. the optimal projection q" arg inf geq be found as follows,
can
1. Solve for optimal clf( as
clf(g")
arg min Ex [Proj (x(X); K m(x),e) Per h)) n hεX'
(119)
where
AK frEAR rry 1y (1+ Vk: v).
Projgz (w; inf D (r(l))
(120)
rES
Solve for an optimal distribution q" given the optimal clf((g)). For each x,
qº (x()) = arg min Dxa (rllp(x)) : K,
(121)
(z)
23

---

Published as a conference paper at ICLR 2025
Proof. Given A, {q X A
Vz,g(z) E U AE. We have
9-' arg min E [
TEQ
arg min ( Qeir
TEA,
arg min D(D -ggg qEA,
n Vj E [m]]
arg aargmmn min min E (g [ h) S thi cl((g)
qeA, hEX->
arg min min min q'p-d' g'EA, hEX-y
: ,l.,, S the = clf(4')
arg min min min E (X))] p(gj. h) s nhe h = clf(d')
q:9=4" bEX-> d'EA
-b) p(gs. h)) 11j
argmin min min
arg
min EE (X)))x(( G'EA
क.-क hEX-y
E min (xl(ux|lp(x)) ux E A AWWXDeD p(gj. S 1/
arg min min vd())=u, NEX-Y
axEAK
Thus
(x)
arg min (ka((ulp((X)) A (x), "EA
(122)
where
h-
arg min hEX'
min [xxEAx
(kl("xllp(X)) : ux ( p(gg. S 1))
(123)
Since u E K
(x) it implies elf(u") = h", and since q- (x) = uzz clf(g*) = ccl((u)) ([=))== = h² Thus
clf(q") min -ex
(p plg,,
(124)
and
q (I) arg min (xL()) uEAK
A (xll
(125)
Proposition B.S. For Qdist defined in equation 16, we have d(p, Qdist) and only if E Qeist Furthermore, for any v >> there exists 8(v) > such that if d(p, Qaist) < 8(v) then Paist (9 S 'i + v/13), where [Sy] Px(S;) is the size of coverage set Sj of weak labeler gj with respect to marginal distribution Px. In particular 5(v) = v² /2.
Rephrasing we get the following bound:
Pdist (gg. p) S n + /2d(p, Qaist//SS]
Proof. Define E(p) min Ex (p(_) (p where drv is the TV distance:
dr 1/2
Σ
Ius ukl
(126)
k=1
First, we prove the following
Pdisa (gj.p)
5 nJ + min Ex Ex((rv(o((3
(127)
qeQai
24

---

Published as a conference paper at ICLR 2025
Priit (gj. E[ Σ p(X) (x)) E S;]
(128)
(x)
= El
Σ
P(X) (x) ((x) ((x)) E B Σ a(X)xxx)) E Sy] for all
(X)
(x)
(129)
IP(X) - ((X)xXX E SJI+ Σ ((X) xx))x E ES]
E
(130)
(x)
E
Ix(X) ((X)AT((X E 5,)1/15;1 + Pdist (gj.9)
(131)
< E Ix()) (())sI/ + Paist ()))4)
(132)
Pdist (dist S 2IE (p(X), ((())))((())))))) + Paist (ai q)
(133)
The above holds for all q. Thus
Pdist (9), s
min ([drr(p((x, + Paist (g).9) 9)
(134)
qeQain
I min
+ max Paittgg 9)
(135)
qEQuist
qEQui
< 2 min
Mij
(136)
qEQaut
(137)
Further using Pinsker's Inequality
() (ullu/)))
we have
Eidry (x)) = Eldrv(a(X),
(138)
S ElVv (1 (l)))))))/X
(139)
s v (R( (1( (X)) (from Jenson's)
(140)
min E(drv(p(X),
S min qEQai
v (oDxxx((()Il)xxX))))
(141)
qEQaiat
min vEQuu
E ([Dxa((())]Ipx))))
(142)
S d(p, Q
(143)
Finally d(p, Qdist) S <x²/2 implies minyeQam. E(drv (p(X), x(x)) v/2, and thus Paise (gi. p) w/|Sy| + T)j-
<
Proposition B.6. Given Qaist as defined in equation 16, for any conditional distribution p. the optimal projection q" arg minye E[DxL(g(X) [p(X))] is given by q" =px where
(x)) == Zx(x)
Σ }))(z))
(144)
):9,(2)=v
Zx(x) is the normalization constant. The optimal X is given by the following optimization:
A min Σ>, > s.t. Paisa (g)- p>) ny Vj [m]
(145)
Proof. The problem is convex optimization with affine constraints since Paist (g)> ①) E| (.) To restate is.
=
AAA K ([DxL(((X))Px(X)
min
(146)
8.l. E
Σ (()x - no Vj E [m]
(147)
(X)
25

---

Published as a conference paper at ICLR 2025
In terms of unconstrained variable g E &' + R this becomes
K
min -R
E
g (X),
(148)
s.t. E
Σ
g(X),l m) Vj E [m]
(149)
(x4a(()
K
(x)), for all
(150)
((>) [0, 1] for all z, and y [K]
(151)
Since log is undefined for nonpositive values and assuming p(z) 0 for all x; y. only need
consider g(x) E R__ thus we can ignore the constraint g(4)y 2 0. q(a), S also follows from the constraint Σ g(x), = 1. Hence the constraint q(x) [0, 1] can be ignored. Rephrasing
have
K (X) log log((()))))()(((()
min -EX-RK
(152)
k=1
s.1. B(((X) 83 (x)) 2 - Vj E mm]
(153)
K
Σ (()) = 1 for all æ
(154)
Here we subtracted from 1, both sides of the incquality constraint.
Now form the lagrangian L(g. A, (i) where À E RT, Lagrange multiplier for each inequality constraint, and μ E X + R, the Lagrange multiplier for equality constraints.
Clg. A, μ)) = E ((X) log(g(X))/p(()))
1=1
+ E (l)(()(1
Σ ( +
Σ
A5 "J Ela(X),, E Sy))
We have
max DEX-BR AER" -EX- +R
min
Clg, A, p)
min E[DKL (x(x)|(((x)
q Qeiu
Since the optimization is convex, point (g", X² n²) that satisfies the KKT conditions is optimal. KKT stationarity condition implies that
v,L(a,, A" nx")
(155)
k= f(((X,)) k))] where f R - R is scalar function, with respect to a function g in x [K] - IR is defined using methods in calculus of variation as function in X' x [K] R
where derivative of an objective L(g) = BICK
V
9 (g)) v) = E = x) ()(' u)) = d(x) v))
(156)
where d is the probability density associated with marginal distribution P on X. Thus we have
VgL(g". X² f (z. d(=) logg (z),/p(x), px)x)= (z)) = 0 (157)
Using E, 4" (x),, 1, we can eliminate 1²' (x) to get o (x) for x in support of P (d(x) > 0)
('(x), Zz- (x) exp( Σ {j)p(r),
(158)
(=)(
26

---

Published as a conference paper at ICLR 2025
where Zx- is the normalization constant
-x)
exp(
Σ
)j)p(z)g)
(159)
y=1 J:9, (z)=y
Complementary slackness condition the incquality constraints imply (1 7/2 [[(g((()x 9x)x S:l) = 0 Vi E [m]
(160)
Singling out X from expression of q- (z)y in equation 158, q" (x)) becomes
exp A
Σ Eittig (x)=)(()) {5)p(=))((* 91()))
q' ('(x) exp(A; + E (0) (5)p(1))((e) + EE exp (0)())=
{j)p(z)y
(161)
or where
f((x))
(162)
f((x) exp(
E
x7)p(z)
exp(
Σ
Nj)p(z),)
(163)
joii (x)=m(()
fi depends on X; for j * but dependence is dropped for convenience.
The complementary slackness condition in equation 160 now becomes
X 1 T - (x)(A (i(X) XX E S. 8)))=0
exp(A:)f((X)
(164)
Let {(t) E
(-(X)) (-f((x)1-fiiC) (xx) X s.]. We have
[(1) -E (( + 1- - KES, >0
(165)
51
and
8² (tt) E 2(A(()) f(()) 8t2
+ X E S <0
(166)
(We assume p(z), (0, and thus fi(x) (0,1) to get the above incqualities.)
Therefore, is a strictly increasing and concave function in t, and thus ((ex(A)) strictly increas- ing in A. Thus from complementary slackness condition in equation 164, if ((exp(0)) 2 1 1- 7 then x 0, else A = A (A))(A)) = п) Together this can be written as
x min À ((ep((A)
2 1 7B/
(167)
A20
or
(xp(A)f((X) exp(A) + +1- f(())
X; min
X E S 21 77b
(168)
A20
Plugging back fa defined in equation 163, and using definition of pd, this is
x min À (Xpx(X), (x))(x))= 2 ?
(169)
A
where A and X2 X3 for j + i. Or equivalently
x; arg min 2
Aj p(g,,p)) S m
(170)
j=1
where X, = Xi j
And thus combining for all we get,
A = arg min
A p(9
< Vje
(171)
X
27

---

Published as a conference paper at ICLR 2025
Proposition B.7. Given the optimization problem
A = arg min
A : p(og.p")
S
nJ Vj E [m]]
(172)
X20
==1
The solution found by the following alternating minimization procedure is optimal if the outer loop converges (The inner loop (equation 174) always converges).
Start with X Then repeat until convergence:
1. Pick j E [m], either randomly or in round robin fashion.
2. for
X arg min A: p(1) s nb
(173)
where X- [A1... 11-1, O, A Am] as follows:
Start: X3 =0
Repeat until convergence: X3 t + llg(1 + (1-m)--((0)--////(/1---
(h) = -E(h(X)XX E S,]
(174)
where hy(x) (x))
Proof. First, show that the solution the constrained optimization in equation 173 with respect to À for a fixed X-y can be found by the iterative algorithm described in equation 174. The LHS of the constraint in equation 173, p(gj p>-)) ) is a function of the form
(xx)x E Sy]
(175)
where
[5(x) exp(
Σ
9,) Σ exp( Σ
)x)p(z)y)
(
(x)=
which is strictly increasing and concave in exp(A) as proved in equation 165.
Suppose
(X;
Sy] < 1 - My Then A3 can also be written as
2, min A: EX A, 1)X Sy) 2 111h 77 A20
We have
hy(2; + exp (A), X X
Letting m(s) = (X; logs + >,,>,))1 E 5z). This is of the form in 175 and is strictly increasing and concave in proved in equation 165, and equation 166 respectively. A is thus given as exp(s). > 1 s.t. u(s) = 1 Ty. If a differentiable function is strictly increasing and concave have for any $1, 82
m(s1) < u(si (u(52) p ((())) //p < p(s2)
(176)
Observe that + (s2) ((s1))/ (()((((()))) is also one iteration of the Newton-Raphson method to solve for s' ((ss) = (182) starting with s = $1.
Using $1 = 1 and mxs2) 7/5 get
((1) < (1(1 (1 - (1))///(11) <1 1
(177)
We have x(1) = (X A A E Sn] and (((1) = E - (, X ) S,] Thus
(1- 1 -1 IX
A ++ = X' + +og (1
(178)
(X,, X E
28

---

Published as a conference paper at ICLR 2025
satisfies
(X; ,,,,,,,)1 E S,]) < (1 S,1) < <1-1p 7
(179)
In particular given X², we apply one step update of Newton-Raphson method on apply the next update. Convergence of these updates faster than directly applying Newton's method on starting function (X; Ao 0, 0,}_,)1X Sy] which is
(X; X x-,)) E Sj] to get A and thus subsequently use h2[; x X-ي))
exp(A exp(X') + (1 (X; (X; (1 hy (X; ,))I E SS
(1 7h (X; I S,D)
(180)
or
exp( -1) - 7/4 - - I Sjl) (X x1 hy X XIX E &,
X+1 X' + log 1+
(181)
This results in a lower update since X > 0 or exp(-X) < 1.
Now we show that if the alternating minimization converges leads to the optimal solution X
Suppose the algorithm converges but the solution À found is not optimal. This implies that À satisfies all of the constraints, but the KKT complementary slackness condition given equation 164 is violated. Since E[,, X, A x X E S3) is strictly increasing function in A, and X, solves for À in equation 173 given A-j. if X > then the equality must be satisfied, otherwise X3 can be reduced
(since X 0) without violating the inequality constraint. Thus either [E,,(X;; X, X x E Sj]
- fl or X = which satisfies the KKT complementary slackness condition.
29

---

Published as a conference paper at ICLR 2025
C COMPACT VERSION OF OUR ALGORITHM
Algorithm Learning from weak labeler constraints
Input: Unlabeled data {r:)/=>> weak labelers {gz Jy= and the corresponding error bounds
(n 3 1- A smooth real-valued function X - RK
Wy g,(2,) [K] U {0}
I/ Weak labels Coverage
Gj = Li 8ij
for each epoch do
2, < f(;;
Logits
pi - (z+)
Probabilities I/ Error in constraints
e, - (1 11-1
E Ei:w Pi/ci)+
d, Eiwer Pt(1 pil/cj
X f log(1 + ej/dd)
11 One step parallel newton update to find À (equation 22)
(h:): + (=))= Σ, > k)
// Logits of projected distribution (equation 22)
loss + 1 - (z0 (h:))
// Cross entropy loss
f upupataee() R(f) + a loss)
// Gradient descent update (equation 10)
end for
30

---

Published as a conference paper at ICLR 2025
samples 100 constraints
0.017
0.004
0.007
0.011
0.001
0.001
0.001
0.001
0.001
0.002
0.000
0.000
0.000
0.000
0.030
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
samples 200
10
0.009
0.010
0.023
0.028
0.007
0.006
0.009
0.015
0.025
# constraints
20
0.003
0.005
0.005
0.010
0.001
0.003
0.000
0.002
0.001
0.002
0.002
0.003
0.000
0.000
0.000
0.000
0.020
80
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
samples 400
10
0.012
0.013
0.032
0.027
0.005
0.006
0.009
0.015
constraints
0.015
0.007
0,012
-0010
0.000
0.000
0.000
0.007
0.019
0.017
0.024
0.003
0.005
0.010
0.014
samples 800
# constraints
0.005
20
0.004
0.005
0.009
0.010
0,002
0.002
0.003
0.003
0.002
0.001
0.002
0.004
0.000
0.000
0.000
0.000
0.001
0.000
0.000
0.000
0.000
0.000
0.000
0.000
16
classes
classes
max plg, q)
max pig. 4)
Figure 3: Max error satisfying convex approximation constraints (max; Pdist (gj. (009))-m0 -n)) (left)
vs max error in satisfying classifier constraints (max, p(gj. clf(()) n4;), (right) averaged over 100 runs of random draws of p and weak labelers, where y = π (p, Qaist,, i.e. the projection & is found by projecting p constraints on distribution described in section 3.2.
D ADDITIONAL RESULTS ON SOLVING THE ILP
D.1 SOLVING THE ILP THROUGH LP
For the particular ILP in equation 13, we have empirically found that the optimal solution of the relaxed LP is mostly integral, and approximating the non-integer by its integral solution almost always satisfies the constraints (the error in constraint satisfaction Par clf -,))
In Figure 4 and 5, we show the performance of solving the ILP after LP relaxation. We used 'scipy.linprog" in Python to solve the LP. In particular, Figure 4 shows that the constraints sat- isfied well (the error Par(gy,cl cq) - n; is small), and shows that only a small fraction of the variables (one variable for each unlabeled data 2) non-integral.
31

---

Published as a conference paper at ICLR 2025
samples 100
# samples 200
constraints 10
0.004
0.001
0.001
0.001
0.002
0.002
0.002
0.002
0.0040
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.0035
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0,000
0.0033
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0,000
0.0025
samples
400
samples
800
0.0020
10
0.001
0.001
0.001
0.001
0.001
0.001
0.001
0.001
0.0015
constraints 40
0.001
0.000
0.000
0.000
0.001
0.000
0.000
0.000
0.0010
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.0005
80
0.000
0,0000
2
16
4
16
Figure 4: Max error in satisfaction of classifier constraints (max, p(gj. clf( - -7)), averaged over 100 runs of random draws of p and weak labelers, where g (p. Qar), i.e. the projection q found by projecting on the constraints classifier through LP relaxation of the ILP described in 3.5.
samples
100
samples 200
constralnts 10
0.010
0.000
0.000
0.000
0.000
0.001
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.008
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.006
samples
400
samples
800
10
0.005
0.006
0.005
0.004
0.003
0.004
0.003
0.002
0.004
constraints
0.003
0.000
0.000
0.003
0.001
0.000
0.000
0..00
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
80
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
# classes
classes
Figure 5: Fraction of non-integral points after solving the LP relaxed version of ILP averaged over 100 runs of random draws of p and weak labelers.
32

---

Published as a conference paper at ICLR 2025
2.22
of Divergence
1.98
1.73
1.49
1.24
1.00
2
4
16
32
64
of classes
Epsilon Values
Methods
Approximation
Gradient Descent
Figure 6: Max of (ki(hhlpp) DxL (h*1lp) over 1000 uniformly random draws p. denotes the solution of 182 found by approximation (equation 184) or gradient descent (20 steps after initial ap- proximation) and ft* denotes the optimal solution as found by "LARABELL convex solver.
D.2 ESTIMATION OF THE COST VECTOR
(p(x); AK and y" (x) from equation 14, and equation 15 requires solving optimization problem. We expand the DxL. term to have
REAR Σ h (g)))//(())) s.t. hy 2 (1 E)hR, Vk + y
(182)
which can be solved by black box convex solver. However, it can also be reparameterized in E To: K-1 to unconstrained optimization
h4 -x) for 1 + y, by = (1+ Z
Σ h
(183)
The objective is no longer convex in À but projected gradient descent (projection to RK still be used to find a local minima. particular, we find the approximation
X; log mmx p(x);/p(<)))
(184)
yields & for which DRI. (h [p([)p))) is empirically found to be within a small constant factor from the optimal. This can further be used starting point for gradient descent, which then results in a solution close to optimal.
Figure 6, we show empirically that our approximation within a constant factor from the optimal as found by evxpy.CLARABEL convex solver in Python, and few iterations of projected gradient descent after this approximation find a solution very close to the optimal.
33

---

Published as a conference paper at ICLR 2025
E CONVEX APPROXIMATION OF THE CONSTRAINT ON CLASSIFIER WITH THE CONSTRAINT ON DISTRIBUTION
We remarked that the constraint sets j, that impose constraints distribution, i.e.
Qj.dist = (q E A Paist (gj. 9) S m
(185)
can be considered convex approximation to the constraint sets Qj.ctt that impose constraints classifiers, i.e.
Qj.tt (q E
A
par(g), clf( S n1}
(186)
First, we note that for distributions that are very confident on one label, i.e. for any z, there is y, such that p(æ), 1- c for small e, we can quantify the extent of approximation.
Lemma E.1. for any there is y, such that p(r)), 1 c, then
Par Parlgg, clf(p)) S Paist Paia( (gj. p)/(1 c)
and
Pdist (gj. p) S Parlgj, cl()) - + Thus any that satisfies Par(gjj clf(p)) I (ng - e)/(1 <) lies in Qj and any E Qj,iit satisfies Pas (g5, clf(p)) S n;/(1- -).
Proof.
Pdist (g. -) EE
Σ p(X)xXX clff())( =
= x(X) E S)
xx)(X)
E Σ E c((()) # o(X) (x) 9(X)JX E
(x)(X)
< c(1 Par (l (p))) + clf(p)))()))
Pdist p) S Parlg, clf(p)) +e
Pdiss (g. P) 2 + (1 - (g.
Petr(g (g. (p)) S (g. ()((p))11111 c)
We dropped subscript j for convenience. Substituting Pair(g,, clf(p)) (n, -e)((1 e) in the bound for Peiss we get Paist (gy, p) & 7Ι. Similarly, substituting Paist (gj p) S mij in the bound for Pats. get Parr (gj, clf(p)) Ni (1 c).
The above lemma suggests that if the true distribution makes confident predictions. (which is often the case for many real-world classification setting), then imposing a constraint on the distribution is close to imposing constraint on classifier. However, this is only a sufficient condition and the convex approximation can be good without such condition as well.
In Figure, 3 we show the maximum eгror in satisfaction of any classifier constraint max; Petr (gg clf(g)) - ") for p sampled uniformly at random when we use the method for pro- jecting constraints on distribution, i.e. T Qiist). The data for weak labelers was generated randomly by first drawing S₁ such that [Sك ~ (0.66, 0.3) and error bound πy ~ (0.3,, 0.3) and then choosing weak labels uniformly at random such that their expected error in Sy is 77. To estimate the projection (p, Qdis)), , 20 steps of alternating minimization in a round-robin fashion (iterating over all constraints by one) is performed to find X (proposition B.7), where each step for each constraint is optimized for 10 steps to find X; given current the iterate X-i-
F ESTIMATING ACCURACY BOUND FROM THE VALIDATION SET
Our algorithm needs some estimate of the error bounds 77, Often they are not given but we have a small validation set with true labels, which can be leveraged to get bounds.
One can be tempted to estimate 77 for each labeler separately from available labels in its coverage region Sy. This approach is problematic since many weak labelers have small coverage set S such
34

---

Published as a conference paper at ICLR 2025
that it is unlikely to have coverage in the validation set. Indeed if the validation set large enough to have good coverage for weak labelers, supervised learning may perform well enough rendering any additional information provided by weak labeler constraints uninformative. We consider two ways to alleviate this problem of low coverage.
First, we consider prior distribution weak labeler errors UΙ and then compute Bayesian pos- terior from the labeled set (and use its mean as the estimate of the bound 77y). When there are no labels in the coverage, the posterior remains the same the prior. One example of prior is Beta prior ((x, () under which observing k incorrect out of samples induces the posterior with mean (k a + + 3). This can also be viewed as domain experts providing a general prior belief about errors instead of individual error estimates/ bounds for each weak labeler.
Second, consider shared parameterization of errors π) he(g,, S2) and then treat hyperparameter to be tuned on the validation set. A simple instance of this shared parameterization common bound fy viding relative information about errors, such as the average errors of different weak labelers are similar/correlated.
i.. h-)-) Φ. This can also be viewed as domain experts pro-
35

---

Published as a conference paper at ICLR 2025
G ADDITIONAL EXPERIMENT DETAILS
G.1 DATASET STATISTICS
Dataset
Num classes
Num labelers
Mean Accuracy
Mean Coverage
Youtube
2
10
0.83 + 0.14
0.17 0.09
IMDB
2
5
0.71 + 0.15
0.24 0.31
Bioresponse
20
0.64 + 0.09
0.17 = 0.20
Yelp
2
8
0.74 0.09
0.18 = 0.20
CDR
2
33
=.12
0.06 0.06:0..1 0.12
Chemprot
10
26
0.47 + 0.17
0.06 0.07
Semeval
9
164
0.77 0.40
0.01 0.03
Trec
6
68
0.73 + 0.37
0.03 0.08
Table 2: Dataset statistics includes the number of classes, the number of weak labelers, and the mean accuracy and coverage of the weak labelers.
G.2 ERROR IN SATISFACTION OF CONSTRAINTS
Table G.2 shows the errors satisfaction of classifier constraints for our trained classifier fär when projecting on Qei (row Ourai in table 1) as D and fäist when projecting on Qdist (row Our(T) in table 1) A
A (par(g), faie) - 17)++
(187)
A dist
(Pen( faist)) 7j +
(188)
m
mean,44 A
w
A
(189)
where wy = |S
Σ
S
(190)
j=1
For most datasets, we see that almost all constraints are satisfied. Despite projecting on Quist>
Bio
CDR
Chem
IMDB
Semeval
Trec
Yelp
Youtube
# Classes
2
2
10
2
9
6
2
2
# Labelers
20
33
26
164
68
8
10
mean, , dist
A
0.0g.0
0.0g.u
0.0g.0
0.02p.02
0.0g.0
0.0g.0
0.0g.u
0.0g.0
mean, A elf
0.0g.0
0.0g.n
0.02p.01
0.05p.o1
0.0g.0
0.02p.01
0.01g.0
0.01
max,
dist 0.08p.15
0.07g.07
0.19p.29
0. 0.11g.05
0.0g.01
0.12p.06
0.03g.01
0.01p.01
max,
A elf 0.03p.o1
0.05g.os
0.28p.22
0.120.03
0.05o.0s
0.55p.29
0.06p.o1
0.04..03
Table 3: Mean and Max error in satisfaction of constraints
diat which measures eтror in satisfying classifier constraint is small, indicating that projecting on distribution works well empirically for satisfying constraints on classifier.
G.3 EXPERIMENT DETAILS OF SOLVING THE ILP
In table I, also reported our results for the method of projecting the constraint on classifiers through solving the ILP in 3.5, as (T)) We did not have access to the true conditional distribu- tion, and could not estimate accuracy bounds with respect the target Bayes optimal classifier equation 1. Instead, we use the same bounds as estimated from training labels by interpreting them noisy bounds with respect the target classifier.
36

---

Published as a conference paper at ICLR 2025
We use the python function "seipy.linprog" solve the ILP and estimate the projection. с in 12 was set to 0.2. The cost vector Projkı. (p(X); A y.e) of the ILP is estimated as described in D.2, in particular we use the approximation AR = log max, p(æ);/p(ad) the number of constraints in the linear program, of 1000. We take a single gradient step in each iteration of the alternating minimization in 3.2.
for X in equation 183. To limit use stochastic gradient descent with batch size
37

---

Published as a conference paper at ICLR 2025
H ERROR GUARANTEE INSIDE THE COVERAGE OF WEAK LABELERS
Theorem H.1. Let Hi...., Hy constraints of the form H, = {f + [K] Per Per(gg hi) S fij }. each with different constant weak labels, 93 (X) j 1 for all = 1,..., K, then for any I E Nj Hj, we have
csrs(f) - _ (ng + errs, (g;)) Pr(S,) Pr(S)
(2/ol - 3) Pr(Ba)
(191)
Pr(S)
1=1
oC k).....)
22
when S = j=ز Sg. Bg (Nieo ( (I.......))) {i) are minterms.
Proof. (Theorem 4.5 Let B, (Nie S)) (ign 5i) be minterms. For simplicity, denote B, = Biy and write Pr(f(X) # B) Pr(X E (x E f(x) # [x(x) n B). Since the weak labelers gj (z) are constant and different for each Jj. without loss of generality, we assume that (I) = 1 for any Sj and for all j = 1,..., k. Intuitively, Bj are regions in Sj with no other conflicting weak labels. We observe that
Pr(X E S)
(192)
=Pr(f(X) # (X):
(193)
Σ Pr(f(X)= +P(()) UB,)
B,) (Ban = =
(194)
U B₁) j=1
(A inequality
(195)
Since E EN Hj. for j ,,..., we have
Pr(S()) 1; < 7 Pr(X S;)
(196)
Pr(J(X) 1; Pr(j(X) 2j-1;5, - -B) S 5, Pr(X E S,)
(197)
(1;: - 11 Pr(X E - -)){P((((X)=) (r(f(X))j-113 1 B,).
(198)
Similarly, since E EN, HT, for j = 1...., k. we also have
(x) - 1; B,) I errs, (g)) - -r(((()) By).
(199)
Substitute these inequalities the above, we have
k
errs(f)P((X E S) <
> (ns + errs, ( S)) - (j-(((()+==11) - BB)
(200)
1=1
- fj P e
U
BB)
(201)
j=1
The region S, B, is the area in Sj with at least one other conflicting region, we can write this as a combination of minterms that represent each weak label in each region,
B
U
B.
(202)
oC
(1.....))
22
38

---

Published as a conference paper at ICLR 2025
Therefore,
Bj)
(203)
==1
Σ - - B₁)
(204)
1=1
Σ Pr(X ES BB)
Σ E Pr(J()=j- -11;; (from equation 202)
(205)
(1..kk)
JE0,
Σ Pr(X B
E
Pr((f(X)=
= -,,
(206)
a5( k),
10/22
Pr(X -S -
Σ
+
(label starts from 0)
(207)
j=1
oC
c
22
Σ
Pr(X Sj Bj)
Σ kL 22
Pr(X E B₂)
(208)
The second to last step holds from fact that for each o, we will see B,, |a| times for each element j E in terms of Pr(f(X) = 1; B.). The same argument also holds for f". Substitute this back the equation equation 200
& -2 (n) errs, PrX -,) - S, B₁)
errs( S) S
Σ
(209)
3=1
j=1
+2
Σ
Pr(X + ES U Bj).
(210)
cC(1...))),11122
Finally, we can write each term as a combination of Bg,
Pr(X E S UB))
E
Pr(x e Bo),
(211)
5=1
oC kl.....,))
1g/22
Σ Pr(X E P -
Σ
Pr|Pr(X Bx)
(212)
a5 (S(......))) 1r|22
Substitute in, we have the result,
errg()))((ees) <
Σ(n (ny + errs, (0))) E (S))
Σ
(2/01- Pr(X E Bo).
k(
1g|2
(213)
or in short, we write
Pr(S,)
Pr(Ba) Pr(S)
errs(f) <
(n) + errs, (97))
Σ
(2|a) 3)
(214)
Pr(S)
(l.......
22
39

---

Published as a conference paper at ICLR 2025
I EXTENDING THE ERROR GUARANTEE TO THE AREA OUTSIDE OF THE WEAK LABELERS COVERAGE WITH A SMOOTHNESS PROPERTY
To prove Theorem 4.6, rely the following observation.
Lemma I.1. Let f be an L-Lipschitz,unnee function w.r.f. a metric d. For any distribution P. P.Q we have Ex-r[f(X)) - Ey~o(((Y)) S Q)(P.Q)
(215)
where (a(P, Q) is Wasserstein distance between P, Q where the cost function is given by d.
Proof. For any distribution P. Q and a transport plan T X' x X' between P.Q. we have
Ex~rlf(X)] Ey By~qlf(Y)) fx))p(x)dx - / f(y)g())dy
(216)
= / (x)T(xx y)dddr / / [())T( (o)
(217)
/ [
[((x) (())T(r, v)dydr S L / |dl,, d(x,,))T (x vddydæ.
(218)
When is the optimal transport plan, the right-hand side term the smallest, which the definition of the Wasserstein distance Wa(P.Q).
The following Theorem is generalization of Theorem 4.6.
Theorem 1.2. Let P be a joint distribution over X x such that Pr(Y = y 1 = x)) is L-Lipschitz w.E.t metric d where for all k- = 1..... K and æı, 222 E X.
PPr(Y
= Pr(Y
X 22)1 S Ld(x)
(219)
For any set S and f we write error of with respect to P as (fr then for any subsets C, D C X. we have
x S),
eTTD err Lu,((,
(220)
when
k X X D)
C) sup
(221)
P[([(X)=
and
uy(C, - (GGGD==EE(dda))aaaeCeeetttttaae Px (n(e)(()))))
(222)
Wa is a Wasserstien distance and we denote for a distribution Px condition on E A.
Proof. First, we write an error term as a combination of errors for each prediction of f(x),
att((f) Pr(f(X) Y (
(223)
Σ Pr(f(X) Y X E
(224)
K Σ Pr(Y (
(225)
k=1
We observe that
Pr((Y +
= =x - Pr(Y 1 =,
(226)
= = X D) - k, EC]
(227)
= -Bx-Pxip-tutreeee (Pr(
(Pr(Y = X)] - Bx- (Pr(Y = k X)]
(228)
S L.w.eexpnna/oosaaxxoxx001101111
(229)
40

---

Published as a conference paper at ICLR 2025
In the second to last line, we can think of Pr(Y- k|X) as function of X for which we can then apply Lemma 1.1 to achieve the last line. For compactness of our notation, we denote Pre(.) = Prx(- X E C)). Substitute this back to the equation above, we have
K Pr(Y # k (
cfT -
= ()((((( = k:)
(230)
K
Pr(Y * k| f(X) = k) - -r(( # f(x) - K)) = k)
(231)
D
Pr(Y # k: xx((x)= P()(X))) =
(232)
AWW.PPxpnnta/(e)>>))PPoo Px)Oe)))X)))))))))))XXX)))))) Pr(((()))))))))))))))))))))))))) = k)
(233)
K Σ
Pr #k f(x) = 1)) PF(F(X) = =k) + Luy D).
(234)
Finally, we also observe that
K
Pr(Y #k| I(X) P))x(((X) j)
(235)
K
Pr(Y # kb f(x) 1)) Px) (o((x))))1) (1) + Pro(J(X)= k) - Pr((I(X) kb)
Σ
(236)
Pxx( = k)
K
Pr(Y #h| (1((x) = k) P)(((x)= = =1)11 + Pro(f(X) = k) - Pro (f(c = 1b)
(237)
Prc(f(X) = k)
Pro(f(X) = k) - Prc((f(X) = k))
Pr(Y # k f(x) = k) PT((((( = k)) + sup
(x)(f(X) = k)
(238)
=eria ( + (C, D))
(239)
Combine with the above, we have
e/r (rre(() (1 +L,(C, + Lug(C, D)
(240)
41


Reviews:
[{"review_id": "GAGp8iavet", "reviewer": "Reviewer_X6nV", "summary": "The paper explores programmatic weak supervision by treating weak labelers as constraints in a classification task.The authors propose a constrained optimization approach that integrates weak labeler error bounds directly into the learning objective. This forms a complex optimization problem and is solved with a novel alternating minimization algorithm.", "questions": "see weaknesses", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The idea is novel and the theory is rigorous. The proposed algorithms lead to significant improvements in empirical evaluations on some datasets.", "weaknesses": "1. The paper misses a conclusion and future extensions paragraph.\n2. On some datasets, the margin of the proposed methods and competing methods are small. Would it be helpful to run some statistical tests to compare their performances?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "BMSdjQumxH", "reviewer": "Reviewer_NPc4", "summary": "By using accuracy restrictions on weak labelers as learning constraints, this work introduces a novel method for programmatic weak supervision. The paper makes three primary contributions:\n\n1. create a constraint-based method for aggregating weak labelers; \n2. present a scalable optimization problem; and \n3. offer a theoretical analysis of the suggested constrained estimator.\n\nThe suggested method is technically sound and well-motivated, and the paper is well-written. The empirical evaluation shows the efficacy of the suggested approach, while the theoretical analysis sheds light on the denoising consequences of several weak labelers.", "questions": "1. I suggest the authors use different markers and line styles for different datasets instead of only using color to differentiate different lines.\n2. There are several ?? in the paper. For example, on line 1357, 1359, 1418: ??\n3. On line 491, the author mentioned that they implemented Algorithm 1 with an L2 regularization. I wonder what are the impacts of other regularization.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. Novel approach: This work presents a novel constraint-based objective that specifically considers accuracy bounds.\n2. Scalable: A linear program for classifier constraints and a convex optimization problem for distribution constraints can effectively execute the paper's efficient alternating minimization approach.\n3. Thorough theoretical analysis: The paper offers a thorough theoretical examination of the suggested approach. These analyses offer assurances on the trained classifier's inaccuracy and draw attention to the denoising impacts.\n4. Excellent empirical performance: According to an experimental evaluation on a well-known weak supervision benchmark, the suggested approach outperforms current baselines, proving its efficacy and resilience.", "weaknesses": "1. The authors admitted that in the case of learning on classifier solving the ILP can still be slow even with LP relaxation. Additionally, because the stochastic gradient descent relies on the population means of the weak labeler accuracies, the method is unable to use a small batch size.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "c0EIfy5cGT", "reviewer": "Reviewer_chyr", "summary": "This paper proposes a method for learning from programmatically generated weak labels by treating weak labelers as constraints rather than relying on traditional generative models. This approach uses side information in the form of bounds on weak labelers’ error rates, which are applied as constraints within a constrained optimization framework. The authors introduce an alternating minimization algorithm to iteratively project model predictions onto the feasible region defined by these constraints. They evaluate the method on multiple weak supervision benchmarks and demonstrate that it improves upon traditional weak supervision techniques, such as Snorkel, by incorporating this constraint-based learning approach.", "questions": "Please see the weaknesses above. And,\n1. I do not find the empirical results convincing. Ours(C) and Ours(V) rely on either hand tuning $\\eta_j$ or estimating from validation data. Did you estimate source quality in other WS setups using the same validation data? \n\n2. Can you provide some simulations with different $\\eta_j$ and labeling sources outputs, clearly showing how the method works in different scenarios?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper presents an interesting alternative to traditional generative models for weak supervision. By viewing weak labelers as error-bound constraints, the approach avoids common assumptions about label independence or probabilistic structure, which may not hold always. \n\n2. The authors provide an upper bound on error (in the union of covered region by all weak labelers) of any predictor satisfying all the constraints. The upper bound is summation of upper bounds on the errors in each weak labelers and the probability of region where weak labelers have a conflict. Implying better bound with more conflict.\n\n3. The method is evaluated on weak supervision benchmarks, where it demonstrates improved accuracy over other weak supervision methods.", "weaknesses": "1. The model relies on accurate estimates of weak labelers’ error bounds to define constraints. However, obtaining these estimates is challenging, and inaccurate bounds could lead to suboptimal model performance. In the experiments these are estimated using validation data, which could also be hard to obtain. In contrast several baselines in weak supervision (those based on generative modeling) estimate 'labelers quality' using only the unlabeled samples. \n\n2. Assumptions made on the weak labelers are not clear. In particular, what are the assumptions that the labelers have to satisfy to ensure the method will work as expected and the theoretical results will hold. Naively putting an upper bound of $\\eta_j$ on each labeler could lead to several scenarios e.g. all could have $\\eta_j$ error in different parts of the input space (~independence) or highly overlapping parts (~highly correlated). Could you explain how the method and results will turn out in these two extremes? \n\n3.  Theoretical results do not explain how learning in the proposed setup leads to a classifier with good generalization error. It naively depends on the summation of errors of individual labelers. On the other hand several of the baselines provide results showing how the labelers cancel their noises and eventually lead to a classifier with comparable generalization error to a model trained on clean labels. They do make certain assumptions on labelers to get there. What can be said more specifically in this setup with similar assumptions? Even a naive majority vote with labelers with random noise of $\\eta_j$ could be shown to give good generalization error going down with the number of samples and the number of weak labelers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "25wtu2bFKv", "reviewer": "Reviewer_jPxa", "summary": "This paper introduces a novel approach for learning from weak labelers by framing the problem as a constrained optimization task. Instead of relying on generative models or conditional independence assumptions, the paper proposes using known upper bounds on the error rates of weak labelers to guide the learning process. The paper develops an alternating minimization algorithm to iteratively generate soft pseudo-labels that satisfy the constraints and train the model accordingly. Theoretical analysis is provided to explain the denoising effects of the method, and experiments on benchmark datasets demonstrate its effectiveness.", "questions": "Please see above", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper moves away from traditional generative models, avoiding the often unrealistic assumption of conditional independence between weak labelers, making it more flexible for real-world applications.\n\n2. The theoretical analysis is quite thorough, especially with the introduction of projection techniques and alternating minimization, showing how to effectively build a classifier without labeled data.\n\n3. Good writting.", "weaknesses": "The problem addressed in this paper is certainly interesting, but as the authors themselves mention, it has strong connections to areas like crowdsourcing, noisy label learning, semi-supervised learning, and ensemble learning. Each of these fields already has well-established techniques that could be adapted, with only minor modifications, to solve the problem presented here. However, the paper dismisses these connections too quickly, with phrases like \"not directly applicable to our setting\" and \"relies on the implicit inductive bias.\" I find this explanation insufficient, as it limits the paper's significance and impact. A deeper exploration of these connections, along with additional comparative experiments, would have been much more convincing.\n\nThe authors propose two objectives and frame the problem as a constrained optimization task, introducing corresponding optimization methods. While the paper's main contribution is centered on optimization through projection, I have to admit that I'm not an expert in optimization, this approach feels somewhat intuitive. It doesn't strike me as a particularly novel or non-intuitive solution.\n\nAdditionally, regarding the problem setup and experiments, I would like to see more details about the coverage rate and noisy rate of each weak labeler and the collective coverage of all labelers. This seems crucial to the model’s performance and yet isn’t discussed in enough detail.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (Poster)