Unbiased Loss Functions for Multilabel Classification with Missing Labels
Authors: Erik Schultheis
Rohit Babbar
Venue: Accepted by TMLR ()

Abstract: This paper considers binary and multilabel classification problems in a
setting where labels are missing independently and with a known rate. Missing
labels are a ubiquitous phenomenon in extreme multi-label classification (XMC)
tasks, such as matching Wikipedia articles to a small subset out of the
hundreds of thousands of possible tags, where no human annotator can possibly
check the validity of all the negative samples. For this reason,
propensity-scored precision---an unbiased estimate for precision-at-k under a
known noise model---has become one of the standard metrics in XMC. Few
methods take this problem into account already during the training phase, and
all of these are limited to loss functions that can be decomposed into a sum
of contributions from each individual label. A typical approach to training is
to reduce the multilabel problem into a series of binary or multiclass
problems, and it has been shown that if the surrogate task should be
consistent for optimizing recall, the resulting loss function is not
decomposable over labels. Therefore, this paper develops unbiased estimators
for generic, potentially non-decomposable loss functions. These estimators
suffer from increased variance and may lead to ill-posed optimization
problems, which we address by switching to convex upper-bounds. The
theoretical considerations are further supplemented by an experimental study
showing that the switch to unbiased estimators significantly alters the
bias-variance trade-off and thus requires stronger regularization.

Published in Transactions Machine Learning Research (08/2025)
Unbiased Loss Functions for Multilabel Classification with Missing Labels
Erik Schultheis
erik. Saatll
Aulto University Kspoo, Finland
Rohit Babbar
rb2608 Bbath, ac. uk
University Both & Aalto University Bath, UK Espos, Finland
Reviewed OpenReview: kttps: httpe://openreveert net/ forum? <d- 1u0hhg
Abstract
This paper considers binary and multilabel classification problems in a setting where labels are missing independently and with a known rate. Missing labels are a ubiquitous phc- nomenon in extreme multi-label classification (XMC) tasks, such as matching Wikipedia articles to a small subset out of the hundreds of thousands of possible tags, where no hu- man annotator can possibly check the validity of all the negative samples. Por this reason, propensity-scored precision- an unbiased estimate for precision-at-k under known noise model has become one of the standard metrics in XMC. Few methods take this problem into account already during the training phase, and all of these are limited to loss func- tions that can be decompased into a sum of contributions from each individual label. typical approach to training is reduce the multilabel problem into scrics of binary or multiclass problems, and it has been shown that if the surrogate task should be consistent for optimizing recall, the resulting loss function is not decomposable over labels. There- fore, this paper develops unbiased estimators for generic, potentially non-decomposable loss functions. These estimators suller from increased variance and may lead to ill-posed opti- mization problems, which we address by switching to convex upper-bounds. The theoretical considerations are further supplemented by experimental study showing that the switch to unbiased estimators significantly alters the bias-variance trade-off and may thus require stronger regularization.
1 Introduction
Extreme multilabel classification (XMC) is machine learning setting in which the goal is to predict a small subset of positive (or relevant) labels for each data instance out of a very large (thousands to millions) set. of possible labels. Such problems arise for example when annotating large encyclopedia (Dekel and Shamir 2010 Partalas et al. 2015), in fine-grained image classification (Deng et al. 2010). and next-word prodiction [Mikolov al.] 20013). Further applications of XMC are recommendation systems, web-advertising and
prediction of related searches in a search engine Agrawal et al. 2013 Prabhu and Varma 2014 Jain et al.
2019 Dahiya et al. 2021).
Typical datasets in these scenarios very large, resulting in possibly billions of (data, label) pairs. This means that it is not possible for human annotators to check each pair, and thus the available training data likely to contain some errors. Even annotating only few samples in order generate a clean test set can be prohibitively expensive. Fortunately, in many cases it is possible to constrain the structure of the labeling errors. Consider, for example, the case of tagging documents. Here, we can assume that each label with which the document has been tagged has been deemed relevant by the annotator, and thus relatively

---

Published in Transactions on Machine Learning Research (08/2025)
surely a correct label. On the other hand, the annotator cannot possibly chock hundreds of thousands of negative labels. This leads to the setting of missing labels investigated in this paper, where only positive labels are affected by noise (they can go missing), whereas negative labels remain unchanged (no spurious labels). For formal definition of the setting we refer the reader to Jsubecction 2.2, and for more thorough discussion of prior works on missing labels and related settings to section 9)
Many machine learning methods are based on minimizing an expected loss over the data distribution, typ- ically by using the empirical risk as statistical estimator. Thus, natural extension to the missing-labels sctting is to construct an unbiased ostimator of the true risk given noisy data. In the XMC context, such an approach has been introduced by Jain et al. (2016), who constructed propensiity-scored versions for some common loss functions. They achieve this under the assumption that the probabilities for each label to not go missing (called its propensity)) is known, and developed an empirical model to estimate these propen- sities from data statisties. The model assumes that propensities are identical for every data point (labels go missing independently of features) and contains two dataset-dependent parameters that have only been determined and made available for a few benchmark datascts. Despite these shortcomings, the resulting propensity-scored metrics have found widespread use in the XMC setting (Bhatia et al. 2016).
However, many loss functions that are employed for training, such as binary cross-entropy or the squared- hinge loss, do not fall within the scope of et al. (2016). Consequently, many methods that use propensity- scored precision as an evaluation metric still perform training using a loss function designed for clean-label
training Dahiya et al. 2021 Guo et al. 2019 You et al. 2019 Babbar and Schölkopl 2019).
Based on the unbiased estimators given in Natarajan et al. 2017 for the setting of class-conditional noise,
Qaraei et al. (2021) provide unbiased versions for several common loss functions. Similar to related learning settings (Kiryo et al., 2017 Chou et al. 2020), they observed that the unbiased estimates may be non- convex, non-lower-boundeeil, and lead to severe overfitting due to high variance. This paper provides some additional analysis in the form of a uniqueness result [Theorem 10 that implies that there are no other unbiased estimates with reduced variance, and generalization bound [heorem 9 which suggests the bias- variance trade-off observed in practice. A mitigation strategy is to interpret the loss functions as convex surrogates of the 0-1 loss, and switch from unbiased estimates of surrogates to convex surrogates of the unbiasod estimate (Qaraci et al. 2021 Chou et al.] (2200).
Often, XMC problems are formulated as ranking tasks in which the goal to maximize either recall or precision within the lop-k predictions. Instead of oplimizing these metries directly, the lask is lypically reduced to a series of binary or multiclass problems, with different reductions consistent for either recall or precision Menon et al.] (2019) H The reductions consistent for precision lead to loss functions that can be decomposed into a sum of contributions from each label which makes them amenable to the methods of Natarajan et al. (017)). In contrast, the reductions consistent for recall contain a normalization term that is the inverse of the total number of true labels. This term is also necessary for calculating the recall metric itself, demonstrating the need for unbiased estimates for true, non-decomposabble multilabel loss functions.
The unique, unbiased estimate for the generic multilabel case is provided by Theorem 19 be seen as special case of Van Rooyen and Williamson (0117 Theorem 5), which states that the unbiased estimate can be calculated by applying the inverse of the adjoint of the label-corruption operator, a 2 x 2 matrix for problem with possible labels, to the vector of all 2' possible loss values for a given prediction. The solution that comes out of our direct computations requires computation exponential only in the number of observed labels. In large-scale multilabel problems, the number of relevant labels is typically much smaller than that of possible labels (Jain et al. 2016 approach requires only O(I) evaluations of the loss function.
This result can
et al. 2022). If it grows hnnialll then our
We derive these results on the basis of modelling the observed labels as the product of the true labels and an (unknown) mask variable. Note that this is different from semi-supervised learning with labelled and unlabelled data, as the mask only used as a mathematical convenience, but no knowlodge of the actual mask values is assumed. The advantage of this formulation is that we can choose a realization of the mask variable such that it is independent of the other random variables, even though the modeled noise
While other surrogate loss functions, such as the malts-label logistic loss Mao et al. 2024). these have not yet been scaled the extremely large label spaces considered here.

---

Published in Transactions on Machine Learning Research (08/2025)
class-conditional. This leads unbiased estimates that contain products of several propensitics in the denominator; for low propensity, if the number of labels is large, this can lead to very high variance in the cstimator.
In order to judge the severity of the variance and overfitting problems in practice, we conducted three experiments. First, in a pure evaluation setting on syuthetic, we calculated the unbiased recallikk for a varying fraction of missing labels, which shows that once this fraction becomes too large, the variance of the estimate explodes and it becomes unusable. As consoquence, this metric can only be calculated on datascts with moderate propensities and many data points. The second experiment serves as a demonstration for the change in bias-variance trade-off as result from switching to unbiased estimates. Here we trained a linear model with varying Zz-regularizatinn using the different versions of the loss functions, using real-data with artificially induced missing labels. We find that training with noisy labels generally shifts the trade- off towards higher regularization, and that for the high-variane unbiased estimates of non-decomposable losses, the original version of the loss function works better than the unbiased one. Finally, we repeat that experiment using real data from the Yahoo-Music R3 dataset, which has been sampled such a way that the proportion of missing labels can be stimated reliably. Unfortunately, the level of noise in this data is so high that the best classifier occurs at extreme regularization, and makes constant predictions independent of any imput features. The code for the experiments is provided at lnttps://github. com/ kmc-aal wwweaaalloonisinglllaaaoe
tmlr
To summarizee, the key contributions of this paper are
1. The model for missing labels a product of true labels and independent mask variable Prropo- sition 4h, which allows for convenient handling of expectations in proofs and derivations.
2. We first demonstrate its usefulness in the binary case, where we derive new results uniqueness (Theorem 10 and variance of the unbiased estimators, and provide a generalization bound Theo-
rem 9) which is corrected version of Natarajan ct al. 2017 Lemma 8).
The unbiased estimates for general multilabel functions Theorem 19). These can be applied to the normalized loss reductions (Menon et al. 2019), which are required for training that is consistent for recallåk. It turns out that even the unbiased estimation recall@kk becomes a very involved procedure (in contrast to precision@k) that requires summing over contributions from all subsets of the observed labels.
4. The investigation of the influence of missing labels and unbiased estimates on the bias-variance trade-off. We confirm the intuition given by the generalization bound that training with the unbiased losses can lead to severe overfitting, requiring re-tuning of regularization, and in some cases entirely negating the benefit of unbiased estimation. In situations where they are available, couvex upper- bounds can be used to mitigate this problem to some degree.
2 Preliminaries
2.1 Notation
In this paper, random variables will be denoted by capital letters X.Y.... whereas calligraphic letters denote sets and lower case letters their elements, such as x é X. Vectors will be denoted by bold font, y E Y, with components y1..... yb. The letters f, 9, and h are reserved for functions, i, j, & denote integers. With [N] we denote the set fl,..., .....,,]. k), and M(A, B) is the set of all measurable mappings from A to B.
There two natural ways express a multilabel data point for m possible labels: Either as vectors from 13" or as subsets of [m]. We will mostly use the former, and thus define the label space as y = {0, 1)Th In cases where the subset notation is convenient, we use the symbol I(v) = {i [m] : v, = 1} to denote conversion from subsct to vector representation, and [((vw) = for the reverse operation.
Throughout this paper, we assume an abstract probability space (L,F,P). We further denote with X' the data space, y the label space and y the prediction space. A dataset is defined through the three random

---

Published in Transactions Machine Learning Research (08/2025)
variables X E X Y y, and Y' E y, that represent the data, observed label, and ground truth label. We
will generally mark quantities pertaining to the unobservable ground-truth with superscript star and call (X, Y") the cleon data.
For given loss function f: V y - R, we denote the true and observed risks of a classifier h: X + y as
RM[ = B A(XM,, Re[h] = ((X(),
and mark their empirical counterparts as ftj and Re.
We will derive unbiased versions of functions of the form f: xx 2 - R, where 2 can be the prediction space Y (when evaluating a loss function {(Y", Y)); the data space X (when evaluating a classifier {(Y", ((X))) some other form of additional argument to be passed into the function want to estimate.
2.2 Setting
In this paper, we are investigating noisy labels in cases where the noise is such that labels can only go missing. This described formally by
Definition (Propensity). The missing- labsels setting we described in the introduction leads to the following condilions on the m random variables
P[V 1 Y = 1, = (X) P[Y; - 1 = 0, =0
labels may missing, but no spurious labels.
(1)
(2)
The value p,(2) E (0,1] is called the propensity of the labelj for instance æ.
Similar propensity models have been used extreme classification (Qaraci et al.) 2021 Jain ct al. 2016
Wydmuch et al. 202Tb, learning-to-rank (Joachims et al. 2017 Oosterhuis and de Rijke, 2020 Wu et al.
2021), and recommendation systems (Sachdeva et al. 2022 Huang et al. 2020: 2022)
The question remains of how to get the estimates of p. In the XMC community, empirical model proposed by Jain et al. (0016) has become established, which proposes to estimate the propensity of a label j based on
the number of occurrences ny inside the dataset of n instances. With two dataset-dependent constants a
and b, setting == (log π () 1)", the proposal is to calculate
Pj = (1 cexp(-alog(ne) + 61)
(3)
It is known that there are some problems associated with this model for the propensily values (Schultheis 2022). The methods presented in this paper are independent of the way the propensity estimates are obtained, so they applicable also if better propensity values are available, e.g. through a more carefully generated (bias controlled) validation set.
In this setup, we interested in finding unbiased versions of given functions. We want to do this also for functions which take additional arguments, such as the predicted label Z = Y. Therefore, we need to ensure that Z is compatible with the assumed propensity, in the sense of:
Definition (Compatible with Propensity). Let p: X (0, 11 be a propensity function, and (7, Y Y) triple of random variahles such that the propensity P;(X) = (Z) is function vp of the second Iff these variables fulfill
Y Yj" 2| =Y; -,,(),
(4)
call them compatible with p()), and write (2, Y Y) Pz(Z). When Z clear from the conteat, we drop it in the notation.
Now we are ready to give precise meaning to the term anbiased version: Definition (Unbiased Version). Let f*: y - R be a function of labels and on additional argument, and p: X (0, 11"H be propensity functionn. We call function fp: y x Z R. an unhiased version

---

Published in Transactions Machine Learning Research (08/2025)
(for propensity p) of f", iff for all random variables (Z, Y Y) Pp that are compatible with the specified propensity, it holds that
EI 2) (Y 2)]. (Y,))
Further, we call an operator pp: F M(Y R), iff Pp(s*) is unbiased version f" for all f F..
MQ x R) an unbiasing operator for the function set
Note the importance of the for random variables qualifier. Since we a priori not know the distribution of the data, we need to make sure that the unbiased estimate we calculate will be correct for all possible distributions.
2.3 Masking Model
As first step in deriving the unbiased estimator, we show that there is equivalent formulation of the problem in which we model the observed labels as the product between some mask and the true labels, Y = M6 O Y". It turns out that it is always possible to choose M in convenient way, making it independent of the true labels Y*
Proposition (Masking Model). Let p: X - 1m be a propensity function, and (Z, Y) E Pg be a triple of compatibbe variables, then then there evists random wariable M E {0, 1 such that
Y = O Y
almost surely,
(6)
M 2,Y; = p(X).
(7)
In particular, we can choose M- = (1- (1-Y)) Y, with M2 ~ Bern(p, (X)) being independent Bernoull variables.
Proof. Checking 1 we see that M ④ =======-" -1--- - -Ye-'=---------- where the second
equality holds because (1 (1-Y")o @ Y 0.
For 7 we get. for all E [m]:
1 Y 2] = 18[(1 - yf) My
(total expectation)
= (1- E M/ Yj. 17 + 2
(measurable factor)
= -1 (1- (X) +Y; -P(() = px()),
where the last line used the compatibility condition
Proposition 4 can be seen a generalization of a similar statement given in Teisseyre et al. 2020 The independent variables provide a convenient framework for proving the results that follow, because the independence allows to factorize expectations containing M.
2.4 Sufficiency of fixed-propensity results
In this section, we show that, for the task of finding unbiased version of function f for general propensity p(x) can be reduced to finding unbiased version for each fixed value.
be some function such that for any fixed propensily p (0. 1 an unbiased version is given by fp, í.e. EYfp(Y, Z)] (Y" Z)}. Then, for pistance-depente propensity p: X' (0, 1 an unbiased version of f is given by S' = fp(x) such that
Proposition 5. Let f : y x Z
f'g 2) Fp(t) z).
Proof. Note that the sight-band-side is well defined, because in Definition we assume the existence of such that p(z)= = (z). Using the law total expectation gives
SI Z)] (Y 2) 2] ([ 2) 2]] (X (2)
The middle equality holds because for any fixed X, p(X) is constant.

---

Published in Transactions Machine Learning Research (08/2025)
Therefore, we will suppress the dependence of the propensity on the instance in the rest of the paper.
3 Unbiased Versions of Binary and Decomposable Functions
In this section, first consider the problem of binary classification with missing labels. We re-derive known results for unbiased estimates in the notation this paper. Then, we state a generalization bound that demonstrates bias-variance trade-off between the unbiased and the original loss, and uniqueness theorem that shows that this is inevitable for unbiased estimators.
Finally, we show how the binary results can be applied to multilabel cases where the loss decomposes, i.e. can be written as sum of binary losses. These situations are quite common, as they correspond to applying the one-vs-oll (OvA) and pick-all-labed labels (PAL) reductions (Menon et al. 2019).
3.1 Derivation of Unbiased Binary Losses
We start by investigating the case with only single label, 1, leading binary classification problem Therefore, we drop the vector notation and corresponding subscripts for this section.
First, we define propensity-scov scoriin operator that maps function to a surrogate function that can be used to compensate for missing labels, and prove that this docs lead to unbiased versions.
Definition 6 (PS Operator). Let 2 be an arbilrary sel, V veclor space, and f": {0, 1) x Z - V, be some function. Since the first argument can only take the two different values and 1, we can decompose
((,,2)=wff(G + (1 ())
(10)
Then, for any p E (0, 1], we call f: x0.1)x2 x - -, pp())) defined as
f(y,2) = y fz(z) F2(x) (p- 1)f((x( + v))
(11)
p
propensity-scored version of f*, and the mapping f + the propensity-scoring (PS) operator for propensily p.
In general, convexity and non-negativeness of f need not result in convexity and non-negativeness of S, ef.
section 322
Theorem 7 (Unbiased Estimates with Missing Binary Labels). The PS- Pp is an unbiasing operator; i.e. for any (Z, Y Y) E Pp compatible with p. and any f (0. - R, the function J (,( fulfills
BM - Fi Z)
(12)
Proof. Applying Proposition 4 and extracting measurable factors gives
E[f(Y,)) Y", - (Z + (p + +1- (p-1) r
P
= =E[M Y 1', 2 (2) + (p - (2)
+ (1- Y - (f(
=py- [i()) + (p - (Z)
+ (1 (1- pf =1)=)))((
=Y"(",
Taking the expectation this equation yields the claim.
Binary as understood in the sense of detecting the presence absence of some label ("Is there a dog in this picture?") not derision between classes ("does picture show dog cat?").

---

Published in Transactions Machine Learning Research (08/ (08/2025)
This thoorem corresponds to Natarajan et al. (2017 Lemma 7), which derives an unbiasod loss function for the generic (two-sided) binary label noise setting.
In practice, the argument to loss function is a prediction given by some classifier Φ and we want to calculate either the risk for this classifier (for evaluation) gradient step (for training). If the classifier's weights W E R& do not. depend on the data that being evaluated, e.g. because they were trained on a separate sample, we still get unbiasedness
Corollary 8. Let d: X be loss function, = Pp(("). Assume that (X, Y ,Y) E Pp, and the nelwork weights are W independent of the data on which we evaluate, W TT Y). Then (Z, Y) E Pp with Z = o(X, W), and we have:
R. be binary classifier with & parometers W, and e 10, 1 +
EY (XX W))] I8[ ((X, W))l ElV <x. wi)] VWV o(X, w))]
Proof. To show that (Z,Y*, .Y) Pp. notice that
E Y 1, 1X, = = W Y 1,6(x, W)]
(13)
(independence of W)
= EEE y"" Y =
(14)
E'p Y =1,6(X, =p.
(15)
Consequently, the first statement follows from direct application of Theorem and the second because Pp a linear operator, and thus commutes with the gradient, (P* (p,(F).
3.2 Examples
Squared Error For the squared error (gg(v, (y -2) the unbiased estimate is
3
(scly. 0) = L 20) + i²:
(16)
2
where we used y² = y because y E (0. 1}. In case the label present (y 1), this is minimized for v. The minimum is
loss
outside the interval [0, 1), shown in Figure
0
Binary Cross-Entropy The BCE loss is given by
EBCE(y, 1) -y log(() (1 - y) log(1 9).
(17)
0
0.5
g
Since this linear y, we can dircctly write down the unbiased estimate as
Figure I: PS squared error loss for p 0.66. The dashed line denote the loss for y the solid one for y 0.
y (BCEV 0) log(ū) (1- log(1 9). (18)
Note that, since the BCE loss not upper-bounded, the unbi- ased BCE loss is not bowerbbunded,, which may be bad from optimization perspective.
3.3 Properties of the Unbiased Estimator
Even though the unbiased estimate guarantees to give correct results in the case of unlimited data, it is not directly clear how helpful is in the finite data regime. In the related problems of PU-learning, learning from complementary labels, and counterfactual ostimation, unbiased estimators are known but they have been found to be problematic in practice (Kiryo et al. 2017 Chou et al. 2020 Swaminathan and Joachims 2015

---

Published in Transactions Machine Learning Research (08/2025)
first problem that even if the original loss has boen chosen as convex function, the unbiased cstimator may not be convex. A sufficient condition for convexity is given in Natarajan et al. (017 Lemma 10), but as the previous example indicates, many loss functions practical interest are not of this type. In fact, the original loss is upper- bounde (e-g- hinge-loss, logistics loss, squared loss), then the unbiased estimate may not even be lower- bound,,,, thus rendering the optimization-prol pprobllennn ill-defined. A way of addressing this problem is to forgo the unbiasedness and switch to convex surrogate losses as discussed in section
Variance A second potential problem with unbiased estimators is their variance. In the regime of p + 0, we can show that the binary case the variance grows with p=1 compared to the evaluation on clean data. For the noiseless case, the variance for a fixed prediction & is given by
(V 0) viY (2( (1-
-fI (2)
(19)
whereas the noisy estimator has variance of
V = V Y 12 (0) (p- - (9) +11 r)
p
=VMM f7(1) + (p 1))
2
(VY
P
=VY (f1(0) + (p- - 1)f2 pD)
(20)
p²
For propensities much smaller than 1, this can be approximated by (sotling E)(1)
V[Y (f2 (f) - (0)) f
=q(1 4) (fi(1) f0))
(21)
p²
p2
Setting 9² = [B[** = q/p, and using 1 - q= - pq* ~ we gel
q(1 9) VI 8)]
VISCY, 0)
(IS'("",0) 9)).
(22)
p?
g- (1-1q*) 9*)
p(1-9-)
which means that the variance increases linearly with inverse propensity.
Generalization The preceding argument indicates that there might be bias variance trade-off between using the unbiased loss that may overfit more strongly on the observed noise, and using the original loss function which gives wrong results even if + A first step toward understanding this is to determine upper bounds on the generalization errors (proof in appendix B.2):
Theorem (Generalization bounds). Let H a function class with Rademacher complexity (H). Let y y - Ja, b] for < b E R be funclion that is p- Lipschilzz continuous in ils second aryument. Let f = Pp(f*) and denote
r" = inf R7-[6),
h h== argmin R2 [b],,, h == argmin Ry- [h].
(23)
GEH
NEH
bEH
as well as
log (2/5)
6 = p RR + (b (b
2m
(24)
m = sup()/ (0. =)l)-
=E2
For given somple of n points, it holds with probability at least 1 6
2
Rj- 7
r
+ 2
(25)
p
1 m
# = Rý- [h]
Sr*+
+ 2c,
(26)
where q = [8[1] 1.

---

Published in Transactions Machine Learning Research (08/2025)
Given a hypotheses class H. the (expected) Rademacher complerity for sample points defined by
RR (H) = E
sup hEH
ozh(Zz)
(27)
where o2 E {-1,1} are independent Rademacher variables (cf. Shalev-Shwarts and Den-David (2014 Ch. 26)).
The bound on the original loss function has, in addition to the Bayes and approximation errors error r", a second bias term R that does not decrease n increases. On the other hand, the unbiased estimation introduces a factor of 2-2 in front of the samplessize-dependent term. This indicates that, if only few training samples are available, the ERM of the unbiased loss might result in worse classifier. This so- called propensity-overfitiin has also been observed in counterfactual estimation (Swaminathan and Joachims 2015).
Uniqueness The results above raise the question whether there might. be other unbiased estimators with reduced variance and better generalization performance. For example, the conditional expectation (Y" Z) Y] also gives unbiased estimate with lower variance, but cannot be calculated without knowledge of the conditional probabilitios P(Y Z}. The following thcorem states that Pp is essentially unique if the marginal probability of the label is known beforehand, and completely unique otherwise.
Theorem 10 (Uniqueness). Let |2| 2 2, p E (0, ll, 9 E (0.p), and F = M({0, 1] x Z, R) be a set of functions. Let p: F - be on operator that maps function to an unbiased estimate in the missing labels selling, such that for all (Z, Y.Y") E Pp that fulfilt the masking model with propensity and marginal
q = E[ holds
vf :: Z) = Elp(ff)(X,
(28)
Then, p is related to the propensily scoring operator Pp by p(f")u, P. (z, + ( 9)7
(29)
for some 7 E R.
Proof. The sufficiency follows from Theorem the necessity can be shown by choosing distributions of X, Y in which X is concentrated on two points. Details in B.T
Since the (y- r) term camnot depend the prodictions, it is irrelevant from optimization perspective, and thus the the propensity-scoring operator Pp is essontially the only unbiasing operator.
3.4 Multilabel Losses that Decompose to Binary Losses
By linearity of the expectation, we can trivially extend the results above to multilabel functions of the following form:
Definition 11 (Decomposable Function). A multilabel function f Z R is called decomposable, i0 it can be wrillen as
(g, = Σ (1..
(30)
with ; (0, x R. We denote the set of all decomposable functions with Fa C MM R,R.. All other multilabel functions are called non-decomposable.
For decomposable loss functions, Corollary 12 (Unbiased Version for Decomposable Functions). Let S E Fa be a decomposable mullillabed function with constituent functions fü and corresponding propensity scored functions f. Pr. (ft).. Then its unbiased version is given by
formulate the following
fly, 2) =
fe 2).
(31)

---

Published in Transactions Machine Learning Research (08/2025)
In particular, the debiasing operutor pp: Fa -+ Fa preserves linear decomposability.
This corollary allows us to write down unbiased versions for all loss functions that result from the One-us-All and Pick-all-Labbe Labells reductions, explained below.
3.5 Multilabel Reductions
common goal large-scale multilabel tasks optimize the precision the top, i.c, the classifiers proposed & labels, and the fraction of truly relevant ones should be maximized. This is the precision-al-k metric, defined through
Pok(y. 9) = k Σ M50ر
(32)
jEtopu(i)
where (ū) returns the set of the & indices with highest scores in y. This objective is decomposable, and Jain
Corollary 12 yields the propensity-scored precision JJiin et al. 2016 as its unbiased version,
Pok D) = k P3 9:bg.
(33)
(etops())
As precision-at-k is a non-contimtous function, optimizing it directly is a difficult. task. Instead, the typical approach to reduce the multilabel problem into a set of easier problems with known solution strategies. The two most common reductions are One-us-All (OVA), which results in binary problems, and Pick-all- Labels (PAL), which results in multiclass problems. Let Bo: {0,13 x + R be a binary loss, then the corrsponding OVA loss is given by
EovAlU ()) Σ (v)
(34)
In contrast, PAL considers all the positive labels for each instance and tries to minimize their corresponding multiclass loss : [m] x R - R, leading to
(p () ))= Σ Uf M..li.
(35)
lgg and luc are strictly proper losses, these approaches are consistent for precision k MMeoo et al. 2019).
As slight generalization, to admit e.g. weighted versions address the imbalance in the label distribution, allow the functions Lac and bxC to be different for different labels. This leads to the following two Corollarics:
Corollary 13 (One-vs-All), For the one-us-all reduction with binary losses {f Pi=1 such that (" ,0) Ee to (bf 0;), an unbiased version given by
Pp()*) = Σ Pp. (Gb0') =l; ((y. > Pps (Abo") (ui-
(36)
1=1
Corollary 14 (Pick-all-Labels). For PAL loss function
("y'' 0) =
Σ
v Bac())
(37)
1=1
the unbiased version given by
m
8ly, 9)
Σ (xc(()
Vi E2 Pi
(38)
This means that in the PAL sctting, the unbiasod version is just a weighted sum of the original constituent functions. In particular, if these convex (bounded), then the unbiased version is also convex (bounded).
10

---

Published in Transactions Machine Learning Research (08/2025)
4 Unbiased Versions of Pairwise- Decomposalee Functions
Among the zon-dccomposable functions, there is an important subgroup that is still casily tractable within the given framework: Functions which the dependence on the labels is limited to pairwise interactions. These ions also serve as a simpler setting in which we can introduce the techniques used later in Section S to derive the general formula for unbiased versions of non-decomposable functions.
Their are four options for the state each pair of labels can be in, so the most general from of the pair-based functions can be written as
(1) = Σ Si Uj.
(39)
for functions : y x x 2 + R.
Refining our assumptions Because this contains terms which multiple labels interact, Definition 2 is not sufficient to ensure the existence of an unbiased version, as it does not prohibit one label Y going missing depending on the presence of other labels Yj. We thus need to amend this definition to
Definition 15 (Jointly Compatible). Let (Z, Y", Y) E Pp(Z) for a propensity function p: X - [0.1 10 the observed labels form set of independent variables, conditioned on the true labels and the side information, i.e.,
P|Y = u 2 II P(Y, 0 0/ 1
(40)
then we call them jointly compatible with p(-), and write (Z, Y Y) E (2)
It is important to stress that we only require the labels to go missing independently, not that the ground-truth labels themselves are conditionally independent given the instance.
Lemma 16. Let (Z,Y",Y) Pp (2), and M be the random mask variable constracted in Proposition 4 Then the individual masks are independent, conditioned on the true labels and the auriliary Z, and in parlicular, with M - denoling all but the j'th component.
E[M, M|, px))).
(41)
Proof. We first plug in the definition of M from Proposition 4 and extract measurable factors, then we apply Definition 15)
E|M, Y -M-
Y Y',Y,, = (1 (1- (1-1)),,((0))+1))>),) (1- (x)) Y 21
(42)
(43)
=
(44)
For the last. line we used Dof 2
Deriving an unbiased version Next, we show that the expression (39 can be written as linear function in each of the observed labels:
Lemma 17. Let g {0,1} x {0,1) x Z - R, then we can write this as a linear function
g" g'
(2a(2a - 1) - 1 a) (2, 1) + b) (a,
(45)
Proof. We achieve this by summing over all four options for Wy) E (0. 0), (1, (0. 1), (1,1)), and select- ing the appropriate one using an indicator function. The expression thus becomes
(V Mj. 2)
Σ 11: = a. ys b) g" b.).
(46)
11

---

Published in Transactions Machine Learning Research (08/2025)
The indicator [y: a. yy b), turn, can be written as the product [ a} 1 (gy = bj. Plugging [v: d} (2a- 1)y- 1 yields the claim.
With this, can derive the unbiased version of all pairwise loss functions
Theorem 18. Let (Z, Y Y) Ppd((z), and g": y x V x Z + IR as in 39 of g is given by
Then unbiased version
(
Piy (th, Ub))
(47)
j=1
with (i Ub) = Σ
(2a - 1) _
+ +11-)
Pj + 1bb bzy(a,
(48)
p;
a,b=0
y/4
yi ps
and galvi, vi) =
96 (0,
gh 1,z).
(49)
Pi
Proof. For the diagonal elements, dh is function a single label, and thus Theorem can be applied. the case # j, using the law of total probability and pull-out of measurable factors, as well as Lemma 16
Elgg Y,, 2)1 Z,
Σ
E
(2a - 1) M,Y,"
+ +1 +1-0) (125- 1)
M,YY Pj
+1-b) b) Z, Z, (.,(a,b,))
o,bm0
+1 1a) (126-1) WiM, v.jr (2a-1) - 1) E[M. Z, Z.Y"
+1 -1-b) (ij(a.
Pj
a,b=0
Example An example for a pairwise loss is the Kendall-Tau loss Shalee-SSwwartz and Ben-David 2014 p. 202), which is used for ranking applications and counts how many pairs of labels are ranked differently the prediction than in the ground truth. Multilabel classification can be interpreted as form of bipartite ranking, where no loss incurred both labels have the same ground-truth independent of their predictions Bucak et al. 2009). In that case, we have gh 0 and
(0,00, 9) 0 9 1, 9)
g (1,0,) 1 < <,} (1, = 0.
(50)
(0: 03}
(51)
Using the zeros for equal ground ground-truth ranking, the unbiased estimate can be simplified to
1
K) Σ Σ pi P3 (p. vi) 10 < 0c) y (P) - 15) 10 < 0z}
(52)
For training, instead of the non-differentiable indicator 1 < &.), one typically uses a margin function max(0, 0s + 1).
Unbiased Versions of Non-decomposable Multilabel Functions
In this section, we consider the fully generic multilabel case. We first derive the general formula for deter- mining the unbiased version and show some of its properties. Then we define generic form of normalized reductions and apply the formula. Finally, we provide some concrete examples of functions with their corre- sponding unbiased versions.
12

---

Published in Transactions Machine Learning Research (08/2002 (08/2025)
Dataset
Avg. Labels
Max. Labels
Loss evals
> 12
Capped
Eurlex
5.3
24
1173
0.1%
65
AmazonCat-134
5.0
57
1.2 x 1012
4.9%
148
Amazon-670k
5.5
69
0.0%
69
Wiki-500k
4.7
274
1.7 x 10
5.2%
156
Amazon-3M
36.1
100
1.0 x 10
60.7%
344
Table 1: Dataset statistics, showing average and maximum labels per instances, as well as the mumber of required original f loss evaluations for (53). > 12 indicates the fraction of points with more than 12 positives, Capped the required loss evaluations if such points were ignored.
5.1 Generic Multilabel Case
For the general multilabel case, state:
Theorem 19 (Multilabel Loss). Let (Z, Y) E Py" (2), and :mm x Z - R. An unbiased version of I" can be calculated using the propensity-score expression
(p(/")= = given by
1/ Ps ('('=2))
f: (y, +
Σ
(53)
Pj
V'
where y' 3 y means {0, v/} S y/
Proof. Decompose the function f into contributions for each possible value of Y as f( Ev Tly = y'} (v', and write the indicator products of yi and 1 -4- Then use the linearity of the expected value as well as the independence of M. For details, see supplementary B.
Unfortunately, the sum over y' < y makes computation Equation 53 compuatiionaly expensive. However, in cases with large label spaces, the actual (observed) label vectors typically become quite sparse (Busa-Fekete et al. 2022). ||ыl| < which miligates the impact to some degree: If we assume the number of observed positives to follow (llg(()), then we would need
20(og( = (1)
(54)
evaluations of the original loss function. However, because of the exponential dependency, much more important than the average number of labels is the mazimum numbe of labels ever encountered in the dataset. For example, in the Wiki-500k dataset, the mean number of positive labels is only 4.7, but in the largest instance that are 274 positives, leading to 2274 terms that would need to be calculated. If one discarded all points with more than 12 positive labels (5.2% of the dataset), the cost would decrease only 156 loss evaluations per point- still expensive, but no longer astronomical. Similar statistics for other datasets are presented in [Table
Note that this is still much more efficient than the general solution given in Van Rooyen and Williamson 2017 Theorem 5), which is stated in terms of transitions between observations. In our case, each of the 2 possible combination of relevant labels corresponds one distinct observation. Their unbiased estimate
f(=) = (T)
(55)
where R' denotes the adjoint of the inverse of the corruption matrix, and f and f* denote vectors that contain the loss for every possible observation. This means that naively, would need to evaluate all 2 possible values of ())2) and combine them using a (sparse) 2 x 2m matrix.
As in the binary case, we state uniqueness theorem:
13

---

Published in Transactions Machine Learning Research (08/2025)
Theorem 20 (Multilabel Uniqueness). Then debiasing operator Pp from Theorem 19 unique, i.e., for any : x Z + RR any unbiased version is equal to Pp(f*). Formally, if for all (Z, Y Y) Pp (Z) it holds that
Ef = 2)),
(56)
then f = pp(
Proof. Since f needs to be unbiased for all possible distributions of Z and Y compatible with p, it needs to work in particular also for P(Z = 2, Y =") 1. Since Y can take only finitely many states, we can decompose f into sum over these states. The claim can then be shown by induction over the number of nonzero elements y, which always introduces only single new summand in the decomposition. Details
can be found in the supplementary B.3
Lemma 21 (Linearity). The propensity scoring operator Pp of Theorem 19 is linear,
Pplf + pp(f") Pp(s"),
(57)
and commutes with functions of the auzillary variable, i.e., for g²: Z R holds
Pp( g¹) = g" pp()))
(58)
Proof- Both statements can be read directly from Equation 53 by using that the sum is linear and g g*())
does not depend on the summation variable.
5.2 Normalized Multilabel Reductions
In Section 3.5 we introduced multilabel reductions that allow training classifiers optimally for precision-at-k:
With Theorem 19. we can now cover normalized reductions, which allow training consistent with recall-at-
k. We first introduce a general form of normalized reduction, which allows unified treatment of PAL-N and OvA-N reductions. The normalized reductions are derived from the basic reductions, Equations 33
and 34 by replacing the label Y with normalized label variable T",
Y Y
Y Ef
4k E [m]: T
(59)
Y
where the second equality is well defined for all possible label vectors, and equal the first under the convention 0/0 = O.
Remark 22. We could also possibly interpret this the following way: Under the assumplion that in the original training data, there is almost surely at least one label present (P[][ 0J = 0), we can set the function an arbitrary value in these cases, without changing its eapectation. However, labels go missing we will not have P[]|Y|| = 0] = O, and the case y' = 0 certainly appears in the summation Eqquatin 53 which means that for any given observed label vector y, the value of the unbiased version of the function will depend the choice of 0/0. This might seem to controdict the uniqueness result stote above, but note that by assuming P[ = 0j 0, we no longer want our unbiased version to work for all possible data. distribulions.
Regardless of the underlying interpretation, this leads to the following general form:
Definition 23 (Normalized Reduction). multilabel function f is considered be a normalized reduction if there caist functions of and h such that
=(y,))=n\(a)
(z).
(60)
So Uj
14

---

Published in Transactions Machine Learning Research (08/2025)
In terms of the normalized labels, we can rewrite the value of such a function as f'(Y', 2) Ln (2)+ h²(Z). Thus, due to Lemma 21| for calculating the unbiased version it suffices to apply the generic formula of Theorem 19 to T. We get
1/
pj) + Pj
Pp =T=
Σ V y
II 110
(61)
1
V/
By adjusting the summation bounds, we can rewrite this to
1/
P5) + Ps
1/4
T= = Σ
(62)
Pi
0- Sy 1:
Plugging this Lemmaa 21 and rearranging terms, we arrive at:
Corollary 24. Let f a normalized-reduction, i.., of the form Equation 60 then its unbiased version f= /=f))f") is given by
1/ pj) Pj
Σ - vL()(2)
Σ
II p::y=1
(63)
0- "y
The next paragraphs present. the decompasition of two classes of loss functions in terms of Delinition 23 that this corollary can be applied.
Then the OvA-N reduction is defined as One-vs-All-ormaalize Let 9BC be binary loss function
m
34
9BC(1,
1
y/4
gAc(0, (.)
(64)
1
Σド= Vb
By comparing terms, we see that this corresponds 9:) Σ (BC(0.0)) (t).
9Bc (1) gec D.) and h())
Pick-AllHLaeessNoommaiieee For given multiclass loss gMc, the PAL-N reduction given by
(3)
IMcli. 9),
(65)
which immediately gives the correspondence (0) gsac and h 0.
Instance- Instance-Averaged Recall a multilabel setting. we can define the instance-averaged recal as fraction of relevant labels that have been predicted (Lapin et al. 2018). Thus for ğ E 10,
Rec" Rec' (v. 0) = bbll
v,
(66)
This can be interpreted both as a normalized PAL reduction with gxc((. 8) = Dt, and as normalized OvA with gnc(y. 0) vÿ. In Appendix we provide an explicit formula for the unbiased estimator.
Geenralizatton lebelede loss functions is straightforward. Appposed micros, or mvcro-avernging

---

Published in Transactions Machine Learning Research (08/2025)
6 Upper-Bounds
The unbiased version allows us to calculate the loss even on data with missing labels, but can we also use for training? Ideally, the loss function should be lower-bounded, so the minimization well defined, should be convex the minimum is unique. Further, the variance of the unbiased estimate should not be too large, so that a reasonable amount of training samples is sufficient.
If assume BBC and IMC to be lower-bounded and convex, then only the PAI-reduction results in an unbiased estimate that is guaranteed to have the same properties, as it is a positive combination of ÊMC- Due to the uniqueness result, is not possible to find an unbiased version that is always convex for the other reductions. Thus, in order to make them amenable for training, propose to switch from unbiased estimates to convex upper-bounds.
6.1 Convex Upper Bounds for OvA Losses
Many binary losses used in machine learning are convex surrogates of the 0-1-loss, for example the logistic loss, (squared) hinge loss, and squared error. Thus, one way to arrive at convex loss functions adapted to missing labels to switch the order of operations(Qaraei et al, 22021] Chou et al. 2020]: Instead calculating unbiasod versions of convex surrogates, calculate the unbiasod version of the 0-1-loss and take a convex surrogate of the resulting expression.
To that end, first consider the binary case: Let 8: {0, }} x R - IR be function that is convex in its second argument and forms an upper-bound on the 0-1 loss. The unbiased version for the 0-1 loss for positive label is given by
(p(lo) = p () 0})
= p (0- < 0H))
-p- 112-pp0 (1 S 50) +p)1)))
= (2/p - 1) (0 s 0} + const.
(67)
From an empirical-risk minimization perspective, the constant does not affect the outcome, so it can be ignored. Therefore, convex upper-bound to this unbiased 0-1 loss (with the constant removed) is given by
0) = (2 2 -1 +1- -).
+
(68)
This type of function has been shown Qaraei et 2021 to improve performance on several XMC
datasets.
6.2 Upper Bounds for Normalized Multilabel Reductions
naive attempt correcting for the noisy labels by replacing Y with Y/p in the caleulations for the normalized labels T* However, the resulting estimator T turns out to be an upper bound. The two estimators are given by
T IY
T= I I+ YUl/D
(69)
Theorem 25 (Normalized Label Upper-Bound). Let (Z. Y E Pp (Z), replacing the true labels with the unbiased estimate of the observed labels as shown Equation 69 results in an upper bound, whose error itself can be bounded by data dependent term
E
Dj
E
Y,
2 ZE
2 E[T7}
(70)
Pj
Pj
J
16

---

Published in Transactions Machine Learning Research (08/20 (08/2025)
Table 2: Error bound for XMC datasets
The proof is presented subsoction B.4 and relics on the transformation of equation (59) as it makes the mask vari-
Dataset
Average
Worst Case
ables in the numerator and denominator independent.
Eurlex-4K
0.02
0.51
1ma
0.0006
0.24
In practice, most entries of the co-occurrence matrix E|Y; Yj] will be extremely small, causing only a minute contribution to the error bound. This can be illustrated by calculating, on two real datascts, the upper-bound for the error of the proposed estimator, by approximating E|y, X with the empirical label co-occurrence frequency. The propensitics are estimated as in Jain et al. (2016]- Looking at the mean value, and the worst case for any label (Table 2). We
that the error on average is very small, indicating that the worst-case bound only applies to very few labels.
Corollary 26 (PAL Upper-Bound); Under the assumptions of Theorem 25 if the underlying multiclass loss fMC is a non-negotive conver function, the expression
Bly 9) E
Bt/P Ejj (x
(71)
gives a nonnegalive, convec upper-bounde the true normalized PAL loss in expectation.
7 Evaluation Experiments
In this section, we validate the result of [Thorrom 19 experimentally using the example of recall. We first provide look at synthetic data, where propensities are exactly known and we caleulate reference ground- truth values. This will show that even in an ideal setting, if the propensities get too low, the variance of the estimate increases so much that it can become unusable. Then we apply the estimator to real predictions, demonstrating that it is applicable for some datasets, but useless for others.
Consider a sctting which there are 100 different labels, which are independent and cach has probability of 10%. We randomly draw 10000 ground-truth label vectors, and generate observed labels by removing according to a propensity that identical for all labels. The predictions are generated by randomly choosing label from the ground-truth. We calculate the average per-example recall using the vanilla estimator, the unbiased estimrt and the upper bound, and plot the results in Figure 2
The figure shows that for propensities lower than 0.4, the unbiasod estimate's variance becomes Loo large. The upper bound also becomes unsuitable, because it deviates strongly from the actual value, and the (biased) vanilla estimate ends up closest to the true value. For medium propensity, the unbiased estimator still has little variance, but noticeable better accuracy than the vanilla one. Together with the uniqueness Theorem 20 these results suggest that for datasets with very low propensity, unbiased estimates are ill-suited to calculate the per-example recall.
Looking the results presented in Bhatia et al. (0016) one notices that recall metrics conspicuously absent. This is presumably because they are not straightforward to compute. In Jain et al. (0066) there is a
Table 3: Propensity-scored 77 and vanilla 66 recall at k for DiSMEC-style models trained using the
squared hinge convex surrogate Qaraei et al. (2021) J. The Filter column indicates the fraction of data points
that had to be removed as outliers to decrease the variance reasonable levels.
PaRec@k
Rec@k
Filter
Dataset/k Bibtex
3
5
42.1
63.9
78.3
33.6
53.0
62.0
0%
Mediamill
21.6
49.2
61.9
23.3
52.6
65.6
0%
RCV1-2K
42.4
78.1
82.3
40.4
74.4
80.7
1%
AmazonCat- Cat-13H
24.2
57.1
72.3
26.4
59.7
75.0
0.05%
AmazonCat- 14K
38.8
68.1
83.0
39.4
69.3
83.9
0.01%
17

---

Published in Transactions Machine Learning Research (08/20) /2025)
20
unbiased- 10k upper-bound
15
vanilla reference
Recall@1
10
11.5
11
10.7
0.5
0.55
0.6
0.2
0.25
0.3
0.35
0.4
0.45
0.5
0.55
0.6
0.65
0.7
propensity
Figure Unbiased estimate of per-example recall with artificial data described in the main text. The shaded region corresponds to one standard deviation, estimated over 100 repetitions. The black line denotes the true recall.
section that argucs how to calculate this in cases where the total number of labels available, but for other cases this paper leaves a gap, which filled by Theorem 19 Unfortunately, the results with synthetic data suggest, once the propensities become too low, the method becomes unusable. This precludes its application to datasets like Amazon-6700 670K or EURLex-4X.
To generate the predictions, surrogate unbiased loss function (Qaraci et al.) 2021 for the squared-hinge loss. Two difficultics arise when when calculating the unbiased recall estimate: First, even if the average number of relevant labels is low, there still can be some samples with high number of true labels, which becomes prohibitively expensive computation. This can be handled by sampling approach. The second problem that the unbiased estimate comes at the cost of vastly increased variance. In fact, observed that the mean is dominated by very few outlier samples, and obtained nonsensical values. Therefore, we filtered out values in the lowest and highest quantiles. This results a biased estimate, but gives much reduced variance. Details can be found in supplementary C.I
trained DiSMEC Babbar and Schölkopl, 2017) model using couvex
Table 3 shows that the recall values for vanilla and unbiased estimation are close except for Bibtex dataset. A possible reason could be that the propensity model, which was empirically found for very large datasets, does not fit. appropriately for this small dataset. For other datasets on the repository (Bhatia et al. 2016), Amazon-670X, WikiLSHTO-325K and EURLex-48 4K, the variance the unbiased estimate large get meaningful result.
Training Experiments
Ideally, would benchmark our loss functions task based on real XMC datasets. However, for those these we neither know the exact propensities, nor can we validate that the unbiased estimates and upper bounds produce reasonable results, since the fully-labeled ground truth unknown. For example, [Schultheis] et al. 2022 Table 3) shows that even with the particularly benign unbiased cstimator for propenstiy- scored precision, the quality of available propensity estimates too low to allow for meaningful results. Consequently, turn more carefully constructed data to analyse proposed loss functions.
18

---

Published in Transactions on Machine Learning Research (08/2025)
8.1 Experimental Setup
Instead of using fully artificial data, we chose lo construct dataset based on existing realistic dała: We took the AmazonCat-13k data and consider only the 100 most common labels, which are the ones with the highest propensity according to the Jain et al. (2016) model. We artificially remove labels according to inverse propensity, which increases lincarly based on the ordering of label frequencies, such that the most common label has an inverse propensity of two and the 100th most common one has an inverse propensity of 20. This process partially preserves the strong imbalances that are typical of extreme classification datascts.
On this data, we train a linear classifier with Le-regularization using different basis loss functions with a) the original loss clean training dała and b) noisy training data, well as c) the unbiased version and d) the upper-bound version on noisy data. For each training run, we evaluate training loss, as well as the task losses precision and recall at k, on noisy and clean training and test data. For the evaluation on noisy data, the corresponding unbiased estimators are used.
By training with the vanilla loss, we get an upper bound how well the given network could do without noise (conlig a) and how poorly it would perform without any mitigations (conlig b). In the first setting, we expect the calculated loss on clean and noisy data to match, since the model cannot overfit to the specific noise pattern in the training data, whereas in configurations b) to d) we expect to see a difference. As we remove labels independently of features, the unbiased estimate on noisy test data should be equal to the actual value on clean test data, if the test set contains sufficient samples to result in accurate estimates.
We took 30% of the original training data and used them validation data to determine the optimal value for the strength of Le-regularization. As the choice of loss function influences the bias-variance trade-off, this value needs to be determined for each configuration. Note that when we train with noisy data, we also use noisy data for validation, i.e. assume setting in which no clean data is available at all.
The network is optimized using Adam (Kingma and Ba 2017) with an initial learning rate of 10-4 for the first 15 epochs and 10-5 for the remaining five epochs, with mini-batch size of 512.
8.2 Overfitting to Sample and Noise Pattern
In addition to the overfitting that is due the finiteness of the training data, the missing-labels setting causes additional overfitting because only a single realization of the noise pattern is observed.
Let be a classifier that depends on the observed data Y, and f loss function with estimator f (f*). Then the generalization decomposes into
Ri, [h] - R2 [h] R7. [b] RJ. [h]
Rj [1 -R, noise pattern
(72)
fluite sample
the difference between the true risk [1. and the empirical risk on clean training data [j,[M], and the difference between that and the estimated empirical risk on observed data Ry [b.. Because the classifier h depends (through Y = M @ Y") the mask variables, f docs not give an unbiased estimate (on training data) and thus the second term is non-zero even in expectation.
In fact, in the linear classifier experiment described here, the noise-pattern overfitting is much stronger than the overfitting due to finite sampling. Figure 3 shows this for the case the BCE loss in OvA-reduction, though the same effect can be seen also for the other loss functions, see supplementary. For the classifier trained on clean data (blue), the weights are independent of the noise pattern and thus the dashed and dotted lines coincide in expectation.
We can see that the label noise acts as an implicit regularizer, in the sense that for low regularization, the gap between clean test and clean training data is much lower when the classifier is trained on noisy data as compared to clean training data.
19

---

Published in Transactions Machine Learning Research (08 /2025)
0.16
0.14
Setting
vanilla a)
0.10
vanilla h)
loss
unbiased c)
0.08
bound d)
Eval on
0.06
clean-test noisy-train
0.04
clean-train
0.02
0.00
10
10-6
10
10
10-3
10
10
10
L
Figure 3: Binary cross-entropy for different regularization strengths, evaluated on noisy training data, clean training data, and clean test data. The gaps between dashed and dotted lines correspond to overfitting the noise pattern, the smaller gaps between dotted and solid lines show the generalization gaps due to the finite training sample. As the dashed lines are for noisy data, they are calculated using the unbiased estimate
34
8.3 Results for Loss Minimization
As Figure shows, for the case of OvA reduction using the BCE loss, the training loss gets reduced much further using the unbiased loss function or the upper-bound loss function than using the vanilla loss. This decrease more than compensates the increase generalization gap, and as such the minimal test loss, the loss at optimal regularization, is better with these two variants of the loss function.
Does this improvement also occur for other reductions and loss functions? This question addressod by Figure 4 which plots the loss clean test data over varying Lg regularization strength for different base losses.
The first. of graphs shows BCEE-based losses, with the left graph depicting the data as Figure 3 The right graph is for the normalized reduction, where the increased overfitting exceeds the improvement training loss, and overall the unbiased training produces worse results than just training with the vanilla loss. We have also included evaluation using the upper-bound formula (69). Note that for the normalized BCE loss, that formula does not result in an upper bound, but the graph shows that it empirically works better than the unbiased loss, yet still worse than vamilla.
surprising feature of the normalized BCE result is that even for very strong regularization, the unbiased estimate underperforms vanilla loss. We altribute this to non-convexity of (64) because increase loss is due to large training loss opposed to the generalization gap. By choosing different initial weights (see supplementary C.2). we can reduce the training loss for unbiased training to that of vanilla training, supporting the hypothesis that sub-optimal minima (which is also non-convex), the normalized case requires scaling by products of several inverse propensities, and thus induces much larger prefactors in front of the terms that cause the non-convexity, which might explain why the same phenomenon does not occur in the decomposable reduction.
the problem. Compared the decomposable case

---

Published in Transactions Machine Learning Research (08/ (08/2025)
BCE
BCE Normalized
0.12
0.14
0.10
0.12
0.08
loss
0.10
0.06
0.08
0.06
0.04
0.04
0.02
10
10 4
10-
10 7
10
10
SQH
SQH Normalized
0.050
0.14
0.045
0.12
0.040
Setting
0.10
loss
vanilla a)
0.035
0.08
vanilla b)
0.06
0.030
unbiased
bound d)
0.04
0.025
0.02
0.020
10-4
10-2
10
10-4
10-2
10
CCE
CCE Normalized
10
6
5
8
loss
3
2
10-7
14-4 L2
10-1
10-7
10-4
10
L2
Figure 4: Comparison of different loss functions, evaluated clean test data, in combination with different schemes for addressing missing labels. Details are in the main text.

---

Published in Transactions Machine Learning Research (08/200) (202522)
version
90
vanilla-clean
vanilla-noisy
80
umbiased-noisy
bound-noisy
Metric
70
P03
60
PM55
Påk [%]
50
40
30
20
10
10
10
10
10
10
10
10
L2
Figure 5: Precision at A for training with binary cross-entropy (normalized reduction) for the different loss variations.
The second row shows squared-hinge based losses, which are also subject to the One-vs-All All reduction. The main difference between this loss and BCE that squared-hinge is even more susceptible overfitting the unbiased case. Whereas for BCE the unbiased and upper-bound variations give roughly comparable results, in this case the upper-bound bound loss proved to be much more stable. the normalized setting, the unbiased loss becomes very large for even larger regularization strength (s= 10-1) compared the decomposable variant (sx 10-2). As in the BCE-normalized setting, the expression in (69 is not actually upper bound, and we can see empirically that does not work well here. We again can observe that the vanilla loss performs better than the unbiased loss.
The third row shows categorical cross-entropy which differs from the other two rows in that it results in a Pick-all-Labell reduction. In the non-normalized case, the upper bound and unbiased loss identical and outperform the vanilla loss. The normalized case shows the same problems as above for the unbiased loss, but the upper bound successfully improves on the vanilla loss.
In terms of the bias-variane, tradc-off, the graphs show a clear trend: The optimal rogularization for training on noisy data is larger than on clean data. It is also larger when using the unbiasod or upper- bound loss as compared vanilla loss.

---

Published in Transactions on Machine Learning Research (08/2025)
8.4 Task Losses
Even though the training process on clean data is based on the optimization of a decomposition into a differentiable loss, this is typically not the quantity that. is ultimately interest. Instead, what we really want is maximization of precision recall at the top (Kar et al. 2015).
The behaviour of precision at k in dependence of the regularization is depicted in Figure 5 for the BCE loss. There are some notable differences in the behaviour of the P@k metrics compared to the loss function: Whereas the increased overfitting for low regularization results in a strong deterioration in the loss function, the corresponding decrease precision metrics relatively mild. For the loss function, the unbiased estimate works better at higher regularization and worse at lower regularization than the upper bound, but here the saluntion is reversed.
The full results for precision and recall at the optimal regularization parameter are presented in Table 4 In this context, optimal is to be understood as the value for which the unbiased estimate of the loss function on noisy validation data minimized. These values might be slightly different than the optimal values for specific P@k or R@k metric. For visual representation of this data, see subsection C.3
Comparing the decomposable and the normalized settings, we can see that the normalized losses induce larger fluctuations (measured in standard deviation) for the OvA settings and the unbiased PAL setting, with the exception of vanilla training on noisy data b) for BCE loss. This holds across all six task losses. Note that this cannot. be explained by the variance in the unbiasod cstimators, as the values presented here have been calculated directly on the clean ground-truth test data.
The graph also shows that the ordering of settings a)-d) is mostly stable (for fixed loss function) over the six different metrics, but differs when switching loss function. For OvA-BCE, the unbiased and upper-bound losses c) and d) are almost equal, but for OvA-SQH the unbiased performs far worse, and with much larger fluctuations, which consistent with the observations Figure For PAL-CCE, the two settings are the same.
In the normalized cases, we can see that the OvA-N reduction results in mostly the same ordering for both BCE and SQH: The vanilla loss b) is better than applying (71 d), which in turn is better than the unbiased loss c). The exception are the recall metries for BCE, where the unbiased loss appears to give better results.
For the PAL-N reduction we can that the upper bound d) does result in better task loss than using vanilla loss b), but as with the other normalized setups the unbiased loss c) performs worse.
Finally, we want know in which circumstances the normalized variations perform better than the decom- posable ones. The results in Menon et al. (219)) prove that in the asymptotic case the normalized reductions are consistent for recall whereas the others are consistent. for precision. However, as seen above, despite the large number of training instances in the dataset, overlitting is still major problem, and thus it may well be that a method that is consistent for recall also gets better results in precision if its generalization gap is significantly smaller.
From Table 4 we can see that for the BCE loss the normalized reduction generally results in worse performance for both precision and recall, with the notable exception of using vanilla loss on noisy data, where there is a slight increase in recall. Nonetheless, using unbiased bound- losses for the decomposable reduction results in overall better performance. For the squared hinge (SQH) loss, the normalized reduction performs worse for all variations and all metrics.
For the decomposable CCE reduction, the upper bound is equal to the unbiased loss. Compared with the bound for the normalized reduction, the latter gives better values in P@1 and R@1, but worse for the other metrics. The unbiased normalized reduction performs much worse across all metrics. For the vanilla loss, the results are as expected according to Menon et al. (2019) with the normalized version yielding better recall. Interestingly, when used on noisy data, also gives better precision.
23

---

Published in Transactions Machine Learning Research (08/2025)
Table Training results on modified AnazonCat-133 data for using different loss functions in their Vanilla, Unbiased or Bounded variants. BCE denotes the binary cross-entropy and SQH the squared-hinee loss corresponding to a OvA decomposition, and CCE denoles (sof max) categorical cross-entropy corresponding to a PaL decomposition. The settings marked with a denote reference runs on clean data.
Sctting
Precision
Recall
Loss
Reg.
P@I
P03
P@5
R@I
R@3
R@5
B-BCE
86.4
57.1
40.7
46.1
75.9
84.4
6.3 10-2
3.16 10-1
B-NBCE
75.8
45.9
32.1
37.1
60.0
67.5
5.6 10
3.4- 10-
U-BCE
86.9
57.5
40.9
46.2
76.1
84.5
5.8 10-2
3.16- 10-4
U-NBCE
72.5
45.3
32.3
40.5
64.5
72.3
6.2-10-2
3.41-10-1
V-BCE*
91.7
61.2
43.3
50.0
81.0
88.9
4.1 10-2
1.26
V-NBCE#
87.7
58.7
41.9
48.6
79.1
87.3
2.8 10
4.73 10-
V-BCE
83.9
53.9
38.3
43.8
71.7
80.2
8.9 10
6.31 6.31-10-5
V-NBCE
83.6
53.6
38.1
43.9
71.9
80.3
3.9 10
1.1
B-CCE
86.4
56.9
40.6
46.3
76.0
84.5
6.4
3.98 10
B-NCCE
86.7
56.3
40.0
46.7
75.9
84.1
1.9
2.39 10
U-CCE
86.4
56.9
40.6
46.3
76.0
84.5
6.4
3.98 10-2
U-NCCE
71.9
43.8
30.9
40.6
64.3
71.7
3.3
0.13
V-CCE*
89.4
59.9
42.8
48.8
79.9
88.2
5.7
7.94 10-3
V-NCCE*
88.9
59.8
42.6
49.0
80.2
88.5
4.43-10
V-CCE
85.0
53.9
38.3
44.8
72.2
80.5
7 10-3
V-NCCE
85.6
54.9
39.1
45.7
74.1
82.5
2.1
2.06 10-3
B-SQH
86.2
56.5
40.4
45.8
75.0
83.8
5.7 10 2
7.94
B-NSQH
60.9
38.1
28.3
28.4
49.0
58.7
3.8 10-2
0.21
U-SQH
73.2
48.7 7
36.2
36.8
64.5
76.1
1.7 10
0.1
U-NSQH
49.9
32.6
24.1
26.5
47.9
56.9
1.9 10-1
0.43
V-SQH*
91.7
61.0
43.1
49.9
80.7
88.5
4.3 10
3.16 10
V-NSQH*
89.2
58.1
41.2
49.4
78.8
86.5
2.6100-
-
V-SQH
82.4
52.1
37.4
42.5
69.4
78.3
8.3 10-2
1.58 10-3
V-NSQH
79.7
49.7
35.8
40.7
66.6
75.9
3.4-10-2
-
8.5 Real data: Yahoo-music-R3
To perform an evaluation on actual real-world data, we repeat the experiment above on the YahooMusic-Ra dataset (athsee(Yahhoo Yahoo! Inc.). While this is not traditional XMC dataset, containing ratings that users have given to songs, we can turn into a multilabel problem as follows: Pick half the available songs and use users' ratings as features. For the other half, consider them be positive label the user's rating above (out of 5). Crucially, while the training set has been collected like typical XMC datascts, that is, users decided which songs they rated, the test set is based on explicitly querying the user on 10 out the 1000 possible songs chosen uniformly random.
On the test set, we can estimate the true label prior by taking the ratio labeled positives to the total number of labeled instances for each song. The ratio of the observed training set prior the true label prior gives the propensity.
We chose 500 of the songs randomly be used as features, based on which the rating of th other 500 songs are to be prodicted. We remove any labels for which there are no positives, or for which the estimated propensity is below 0.01, which leaves 459 valid labels. To normalize the feature vectors, we apply a tf-idf-like transform, that is, the feature values scaled by log(n/Tppostiinn possiiive)

---

Published in Transactions Machine Learning Research (08/20 /2025)
50
45
40
P@k [%)
35
Loss version
vanilla-noisy
unblased-noisy
30
bound-noisy
Metric
P@1
20
P83
P@5
10
10-3
10-2
10
109
L2
50
45
40
Pâk [%)
35
Loss version
30
vanilla-noisy
unbiased-nonl noisy
25
Metric
Pâ1
P83
15
P85
10 3
10
10
10a
10a
10a
Figure 6: Test set performance of linear classifiers trained on Pahoo-music-Bi with varying levels of regular- ization, using binary cross-entropy / one-vs-all (Lop) and calegorical cross-entropy / pick-all-labels (bottom).
As above, we train lincar classifier over a sweep of regularization strengths, as shown in Figure 6 The graphs show that, at strong regularization, the unbiased loss outperforms using the original loss function. For BCE, at high regularization the unbiased and upper-bound functions perform equally, but at low regularization, that (with the exception of P@3 for BCE) best.
the unbiased loss becomes very bad. In fact, performance is achieved at the strongest regularization level, where the resulting PSP@k plateaus, contrary to the expectation that too strong regularization would be detrimental to performance.
The platcau, and the vanishingly small error bars, happen because the classifier degencrates to constant function, as all the multiplicative weights are driven to zero. In that case, the classifier needs to predict the labels with the highest class prior, and the effect of the unbiased losses essentially boils down to ensureing

---

Published in Transactions on Machine Learning Research (08/2025)
the true class prior is estimated, instcad of using the observed class prior. Thus, while this example shows that these losses work as intended, the actual learning happening here is rather trivial.
Related Work
Unbiased Estimates for Noisy Labels Learning with missing labels is a specific instance of learning with class- conditinn noise. For the case of binary labels, unbiased estimates of the loss function can be lound in Natarajan et al. (2017). Note that the generalization bound given therein (Lemma 8) is missing a factor of max norm of the adapted loss function ||,]|o, cf. Theorem 9
An even more general approach is given in Van Rooyen and Williamson 2017 In their notation, f is a function and P the probability distribution over clean data, that is transformed by the invertible operator into a corrupted probability distribution. Let be the inverse of T, and R its adjoint, then holds
(P = o f) (T(P),
(73)
This equation forms the basis for their "Theorem 5 (Corruption Corrected Loss)", which states that corruplion corrected function lR is given by
lR(:a) = (l(
(74)
where A denotes the set of possible actions that will be evaluated by the loss functions. For finite label space with possible, the operator R can be represented with n X matrix.
In the specific case of multilabel classification, our results Theorem 19 show that out of the 2 possible values of the label vector that are necessary to evaluate (74) in the general case, in fact only these that are subset of the observed labels need to be laken into account, thus requiring only 21lslla evaluations.
Robust Poss-Functions An even more robust approach than choosing loss function which compensates for noisy labels is to use a learning algorithm that is inherently noise tolerant. This has the advantage that one does not. need estimate the noise rate, and cannot introduce additional error by misspecification. For symmetric label noise with rales less than 50%, Ghosh et al.] (2015) proved that methods minimizing losses which fulfill a symmetry condition f(0,-) f(1-) = c for some constant c are noise tolerant. If a convex loss function is desired, this leads to the unhinged loss (Van Rooyen et al. 2015).
Certain porformance objectives such as the balanced error or the AUC are noise robust even under the more general setting of mutually contaminated distributions as shown in Menon al. 2015).
Data Re- Re-Calibration A data re-calibration approach tries to identify from the training data which sam- ples are corrupted (Han el all 2018 Zheng et al. 2020: Jiang et. al. 2018). The co-teaching approach (Han et al. 2018)) maintains two interacting networks: For each minibatch, each network selects a subset of examples with low loss value, which is assumed to indicate that these are clean instances. The weights the other network are then updated by training only these sclected examples. Given that deep neural networks have been observed to initially fit clean data and start overfitting on noise as the training process progresses (Arit et al. 2017), they decrease the selected fraction of the minibatch over time.
Some theoretical justification for these approaches is provided by ZZhng et al. (2020) in cases where the probability mass for instances very close to the decision boundary is low. For noisy labels with transition probabilities that are independent of the features, sufficiently accurate model for predicting the true class-conditional probability π(X)= = IP(Y- = 1 | can identify mislabeled samples. Based on that, they developed likelihood-ratio test to decide whether a label in the training data should be flipped. Despite the theoretical foundation of their approach, they still need some empirical adjustments to make the hod work in practice, e.g. they introduced an additional retroactive loss term in order to stabilize training.
Post- Post-Proccssing It is also possible to first train scorer on the noisy data naively, from which a classifier adapted to a given rate of missing labels can be constructed by choosing an appropriate threshold. For naive scorer that predicts the class probabilities for each data point, the corrected threshold is given in
26

---

Published in Transactions on Machine Learning Research (08/2025)
Menon et al. (015)). Similarly, the inference procedure of probabilistic label trees can be adapted take into account propensity model (Wydmuch et al. 2021
Other approaches are to try to design new losses specifically tailored to deal with missing labels, such as a group-lasso based formulation (Bucak et al., 2011).
Positive-Unlan Unlabeled Learning Learning with missing labels is highly related to the problem of learning from positive and unlabeled (PU) data. This can be interpreted in two ways, the censoring setting which is identical to learning with missing labels, and the case-control setting in which the positive labels drawn independently from the unlabeled data (Elkan and Noto 2008). In the latter case the marginal of the true labels of the training and test data might be different. In that setting, instead of a noise rate, the class prior needs to be known (or estimated), then corrected loss function can be determined as in Du Plessis et al (013)). The appearing difficulties, that non-negativity and convexity need not be preserved in the new loss,
are the same as in our setting (Kiryo et al. 2017 Chou et al., 2020
Semi-Supervised Learning slightly different setting with missing labels given by semi-supervised learning. Here, for each example the values of only a (known) subset of the labels are available, that is label can be one of three values 1 (positive), -1 (negative), and 0 (unknown). over labels, then one strategy for coping with this situation, taken in Yu et al. (2014). is to only sum up the contributions where the label is known, i.c. the unknown labels are masked out.
the loss function decomposes
10 Summary and Discussion
We have shown that the modelling of missing label learning problems using a mask variable provides an easy way of deriving unbiased estimators for both the binary and the multilabel setting, if labels go missing independently. These unbiased estimators are unique, and may show undesired properties: Even if the original loss function was convex and lower-bounded, the estimate can be non-convex and unbounded. Even in a pure evaluation setting, where these properties are not required, increasing variance as the propensity decreases poses significant problem and may proclude the use of unbiased estimates.
As a mitigation, we propose to use convex upper-bounds. For the binary case we can write down general solution given in 68). In the multilabel setting, we have considered four importanl cases that arise out of the multilabel reductions given in Menon et al. (2019). Particularly favourable among them is the Pick- all-Labels reduction, it directly leads to convex function. For its corresponding normalized form, we still can construct a convex upper-bound. In the One-vs-All case without normalization, the binary convex upper-bound can be applied, but finding a bound with normalization is still an open problem. An overview of the reductions is given in Table
These results suggest that asymptotically, PaL reductions are preferable over OvA reductions. In practice, however, the situation is less clear. In our experiments we observed that unnormalized OvA produced the best results in terms of recall, even though this loss is in fact not consistent for recall. The most clear rocommendation that can be drawn from our results is that if you want to use normalized reduction, PaL-Norm is to be preferred over OvA-Norm because currently lack a convex surrogate for the latter.
As suggested by theoretical results (Theorem 9) and corroborated by the experiments, missing labels lead to shift in the bias-variance trade-olf. If the data has missing labels, more regularization is required,
Table 5: Overview of multilabel loss reductions.
Reduction
Base
Consistency
Convexity
One-vs-All
Binary
Precision
Upper-Bound
OvA-Norm
Binary
Recall
Pick-all-Labels
Multiclass
Precision
Yes
PaL-Norm
Multiclass
Recall
Upper-Boute
27

---

Published in Transactions on Machine Learning Research (08/2025)
irrespective of whether training uses vanilla-, unbiasod- or convex upper-bound losses. Looking more closely at the overfitting phenomenon, we found that the generalization error can be split into two parts: the difference between the empirical errors on the noisy and the clean (finite) data, and the difference between the clean empirical error and the true risk. We found that the overfitting substantially exceeded the overfitting to the finite sample. Our findings agree with the observation of Arpit ee al. 2017) who found that typical regularizers prevent a deep network from memorizing noisy examples, while not hindering the learning of patterns from clean instances.
the specific noise pattern
Due to the uniqueness results, the probloms mentioned above are unavoidable when using unbiased estimates. This suggests that further research should look into loss functions that allow tuning the trade-off between bias and variance. Having a slight bias in the loss function would usually not be problematic, especially considering that the propensity values which we have assumed to be given in this paper will in practice actually be only estimates, so that the unbiased estimates derived here will also have slight bias due to misspecification.
References
Rahul Agrawal, Archit Gupta, Yashoteja Prabbu, and Manik Varma. Multi-label learning with millions of labels: Recommending advertiser bid phrases for web pages, In Proceedings of the 22nd International Conference on World Wide Web, WWW '13, page 13 13-24, 24, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 9781450330351. doi: (..114522883888222
URL https://doi. org/
10. 0e.1111//88888... 2488391
Devansh Arpit, Stanistaw Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S. Kan- wal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, and Simon Lacoste-Julien. A Closer Look Memorization in Deep Networks. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conferencee on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages
PMLR, 06-11 Aug 2017.
Rohit Babbar and Bernhard Schölkopf. Dismec: Distributed sparse machines for extreme multi-label classi- fication. In WSDM, pages 721 729, 2017.
Rohit Babbar and Bernhard Schölkopf. Data scarcity, robustness and extreme multi-label classification. Machine Learning, 108(8):1325 1329 1351, September 2019. ISSN 1573-0565. doi: 10. 10000// URL https://dol: org/ 10. 1007///009944019--67777
Kush Bhatia, Kunal Dahiya, Himanshu Jain, Yashoteja Prabhu, and Manik Varma. The extreme classifica- tion repository: Multi-label datasets and code. http::/maaikvartt http///ommmlaaa////////eeppppppe html] 2016.
Serhat S Bucak, Pavan Kumar Mallspragada, Rong Jin, and Anil K Jain. Efficient multi-label ranking for multi-class learning: application to object recognition. In 2009 IEEE 12th International Conference on Compuler Vision, pages 2098 2105. IEEE, 2009.
Serhat Selcuk Bucak, Rong Jin, and Anil K Jain. Multi-label learning with incomplete class assignments. In CVPR 2011, pages 2801-2808 IEEE, 2011.
Róbert Busa-Fekete, Heejin Choi, Krzysztof Dembezynski, Claudio Gentile, Henry Reeve, and Balazs Szorenyi. Regret bounds for multilabel classification in sparse label regimes. In S. Koyejo, S. Mohamed, A. Agarwal, 1). Belgrave, K. Cho, and A. Oh, editors, Advances in Newral Information Processing Systems, volume 35, pages 5404 5416. Curran Associates, Inc., 2022. URL htttps:/prroceedingg www.:oowwwdddnoe.eooooooooee.e.. nwurips.rcccoo paper shter_files/pppeee 2022/ wtt2///1///20000/000 http:///000000000000/////0000000 wonferrrerooooeeeeee.e.
Yu-Ting Chou, Gang Niu, Hsuan- Lin, and Masashi Sugiyama. Unbiased Risk Estimators Can Mislead: A Case Study of Learning with Complementary Labels. In International Conference on Machine Learning, pages 1929-1938. PMLR, November 2020. URL https://proceeddng: rr, press/vii 111// chou20a. html ISSN: 2640-3498.
28

---

Published in Transactions on Machine Learning Research (08/2025)
K. Dahiya, A. Agarwal, D. Saini, K. Gururaj, J. Jiao, A. Singh, S. Agarwal, P. Kar, and M Varma. Siame- sexml: Siamese networks meet extreme classifiers with 100m labels. In Proceedings of the International Conference on Machine Learning, July 2021.
Ofer Dekel and Ohad Shamir. Multiclas--mullte classification with more classes than examples. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pages 137- 144, 2010.
Jia Deng, Alexander C Berg, Kai Li, and Li Fei-Fei. What does classifying more than 10,000 image categories tell us? In ECCV, 2010.
Marthinus Du Plessis, Gang Niu, and Masashi Sugiyama. Convex formulation for learning from positive and unlabeled data. In International conference on machine learning, pages 1386-1394, 2015.
Charles Elkan and Keith Noto. Learning classifiers from only posilive and unlabeled data. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD '08, pages 213 113-220, New York, NY, USA, August 2008. Association for Computing Machinery. ISBN 978-1- 60558-193-4. doi: 10.1145/ 1401890. 1401920.. URL htttps:///oi.orrg// 1115.///0001.111114141911999 110.11111//1199990 1401920
Aritra Ghosh, Naresh Manwani, and P. S. Sastry. Making risk minimization tolerant to label noise. Newro- computing, 160:93 107, 2015. Publisher: Elsevier.
Chuan Guo, Ali Mousavi, Xiang Wu, Daniel N. Holtmann-Rice, Rice, Satyen Kale, Sashank Reddi, and Sanjiv Kumar. Breaking the Glass Ceiling for Embedding- -aadd Classificrs for Large Output Spaces. Adeances in Neural Information Processing Systems, 32, 2019. URL htttps://proceeddinne htw.:ooeeddnng...uu....... ccpppppprccpppp Abstract html
Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miso Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In S. Bengio, H. Wal- lach, H. Larochelle, K. Grauman, N. Lion Processing Systems, volume 31. Curran Associales, Inc., 2018. URL httpttts:///cceedtieieeee neurips. .ddf
and R. Garnett, editors, Advonces in Neural Informa-
Jin Huang, Harric Oosterhuis, Maarten De Rijke, and Herke Van Hoof. Koeping datasct biascs out of the simulation: A debiased simulator for reinforcement learning based recommender systems. In Fourteenth ACM conference on recommender systems, pages 190-199, 2020.
Jin Huang, Harric Oosterhuis, and Maarten de Rijke. It is different when items are older: Debiasing recommendations when selection bias and user preferences are dynamic. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, pages 381 389, 2022.
Himanshu Jain, Yashoteja Prabhu, and Manik Varma. Extreme multi-label loss functions for recommenda- tion, tagging, ranking and other missing label applications. In KDD, August 2016.
Himanshu Jain, Venkatesh Balasubramanian, Bhanu Chunduri, and Manik Varma. Slice: Scalable linear extreme classifiers trained on 100 million labels for related searches. In WSDM, pages 528-538 536, 2019.
Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei- NentorNet: Learning data-driven curriculum for very deep neural networks on corrupted labels. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference Machine Leurning, volume 80 of Proceedings of Machine Learning Research, pages 2304-2313. PMLR, 10-15 Jul 2018. URL https://proceeding mlr. pwwss/v00// iang18c. hamml .ttl
Thorsten Joachims, Adith Swaminathan, and Tobias Schnabel. Unbiased learning-to-rank with biased feed- back. In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, pages 781 789, 2017.
Purushottam Kar, Harikrishna Narasimhan, and Pratock Jain. Surrogate functions for maximizing precision at the top. In International Conference Machône Learning, pages 189 198. PMLR, 2015.
29

---

Published in Transactions on Machine Learning Research (08/2025)
Diederik P. Kingma and Jimmy Ba. Adam: method for stochastic optimization, 2017.
Ryuichi Kiryo, Gang Niu, Marthinus C du Plessis, and Masashi Sugiyama. Positive-Unlabelon Learn- ing with Non-Negative Risk Estimator. In I. Guyon, U. V. Luxburg, Bengio, H. Wallach, R. Fer- gus, S. Vishwanathan, and R. Garnett, editors, Advances in Newwl Information Processing Sys- tems 30, pages 1685. Curran Associates, Inc., 2017. URL http://papers. nips. cc/paper htt.ppssttiee-ualbbaleeee--eeeee oag
M. Lapin, M. Hein, and B. Schiele. Analysis and optimization of loss functions for multiclass, top-k, and multilabel classification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(7):1533- 1554, 2018. doi: 10.1 1T.110/TTA...211..7551
Anqi Mao, Mehryar Mohri, and Yutao Zhong, Multi-label learning with stronger consistency guarantees. In The eightt Annual Conference on Newral Information. Processing Systems, 2024.
Aditya Menon, Brendan Van Rooyen, Cheng Soon Ong, and Bob Williamson. Learning from corrupted binary labels via class-probability estimation. In International Conference on Machine Learning, pages 125-134, 2015.
Aditya K. Menon, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Multilabel reductions: what my loss optimising" Advances Neural Information Processing Systems, 32, 2019. URL https: //papers.mipp
html
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word representations in vector space. Xiv preprint arXis:1301.3781, 2013.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Nagarajan Natarajan, Inderjit S. Dhillon, Pradeep Ravikumar, and Ambuj Tewari. Cost-sensitive learning with noisy labels. The Journal of Machine Learning Research, 18(1):5666-560 2017. Publisher: JMLR. org.
Harrie Oosterhuis and Maarten de Rijke. Policy-aware unbiased learning to rank for top-k rankings. In Pro- ceedings of the 49rd International ACM SIGIR Conference on Research and Development Information Retrieval, pages 489 498, 2020.
Ioannis Partalas, Aris Kosmopoulos, Nicolas Baskiotis, Thierry Artieres, George Paliouras, Eric Gaussier, lon Androutsopoulos, Massih-Reza Amini, and Patrick Galinari. Lshle: A benchmark for large-scale text. classification. arXiu preprint arXiv:1503.08:: 085881 2015.
Yashoteja Prabhu and Manik Varma. Fastxml: A fast, accurate and stable trec-classifier for extreme multi- label learning. In KDD, pages 263-272. ACM, 2014.
Mohammadreza Qaraci, Erik Schultheis, Priyanshu Gupta, and Rohit Babbar. Convex Surrogates for Un- biased Loss Functions in Extreme Classification With Missing Labels. In Proceedings of the Web Con- ference 2021, pages 3711-3720. Ljubljana Slovenia, April 2021. ACM. ISBN 178-1-7503-831227 doi: 00.1145/3442881.345001 URL lhttss://d)) hcwp:///llacc.cccc/cc//c acm. www./oog//////ooooooooo 1ttp://....11/////11 114...1441/3344888 3450139
Novcen Sachdeva, Carole-Jean Wu, and Julian McAuley. On sampling collaborative filtering datascts. In Proceedings of the Fifteenth A ACM International Conference on Web Senrch and Data Mining, WSDM '22, page 442-850, New York, NY, USA, 2022. Association for Computing Machinery.
Erik Schultheis Marek Wydmuch, Rohit Babbar, and Krzysztof Dembozynski. On missing labels, long- tails and propensities in extreme multi-label classification. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '22, page 1547-1557, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450393850. doi: 10.1145/35388 33534668.33394445
URL
http:://ool.orr/00.1144//4455 3539466
30

---

Published in Transactions Machine Learning Research (08/2025)
Shai Shalev-Shwartz and Shai Ben-David Understanding machine learning: From theory algorithms..
Cambridge university press, 2014.
Adith Swaminathan and Thorsten Joachims. The Self-Normalized Estimator for Counterfactual Learning. In Advances in Neural Information Processing Systems, volume 28, Curran Associates, Inc., 2015, URL
httpp::/papers.. httpppppprs.ips........ nips. htt.://ss..pp..paooo///////////a httppp//...hhaaaooottt//a/////ea Abttract.bttatc..t..
Pawel Teisseyre, Jan Miclniezuk, and Malgorzata Lazęcka. Different strategies of fitting logistic regression for positive and unlabelled data. In Valeria. V. Krshizhanovskaya, Gábor Závodszky, Michael H. Lees, Jack Dongarra, Peter M. A. Sloot, Sérgio Brissos, and João Teixeira, editors, Computational Science ICCS 2020, pages 3 17, Cham, 2020. Springer International Publishing.
Brendan Van Rooyen and Robert C. Williamson. A theory of learning with corrupted labels. 18(1):8501- 8550, 2017. ISSN 1532-4435.
Brendan Van Rooyen, Adilya Menon, and Robert C. Williamson. Learning with symmetric label noise: The importance being unhinged. In Advances in Newral Information Processing Systems, pages 10-18, 2015.
Xinwei Wu, Hechang Chen, Jiashu Zhao, Li He, Dawei Yin, and Yi Chang. Unbiased learning to rank in feeds recommendation. In Proceedings of the 14th ACM International Conference on Web Search and Date Mining, pages 490-498, 2021.
Marek Wydmuch, Kalina Kobbus Rohit Babbar, and Krzysztof Dembezynski. Propensity-Sone Scorred Probabilistic Label Trees, page 2252-2256. Association for Computing Machinery, New York, NY, USA, 2021. ISBN 4703500393 URL htttpp://aal..rg/1001111//////// 344434 3463084
Yahoo! Inc. Yahoo! webscope datasct wut.acacwyyyaaaaanuuuuuuurrrrrrr 0. URL https:///ve..achhivaa oozp:///2200000000//ttrr//eeeeee http:///w........o.o.o.oo..oooo. http:///o./...aaogoopp/aaaaaarar Yahoo! Webscope program
hwtp://ww.....roroo/coccccaaaaae com/ www.o///aammcceeeeiiiiiieeeeeeee Relations
Ronghui You, Zihan Zhang, Ziye Wang, Suyang Dai, Hiroshi Mamitsuka, and Shanfeng Zhu. Attentionxml:
Label tree-based altention-aware deep model for high-performance extreme multi-label text classification. In H. Wallach, H. Larochelle, A. Beygelkimer, F. d' A'Alché-Bue, E. Fox, and R. Garnell, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL httpp:// pdd
Hsiang-Fu Yu, Prateck Jain, Purusholtam Kar, and Inderjit Dhillon. Large-scale multi-label learning with missing labels. In International conference machine learning, pages 593-601, 2014.
Songzhu Zheng, Pengxiang Wu, Aman Goswami, Mayank Goswami, Dimitris Metaxas, and Chao Chen. Error-bounded correction of noisy labels. International Conference on Machine Learning, pages 11447 11457. PMLR, 2020.
31

---

Published in Transactions Machine Learning Research (08/2025)
A
Per-Exane Per-Example Recall
Applying the general solution from Theorem 19 to the definition of per-example Recall as given in equation results in
66
Recall(y, 9)
II iETly) Ps
Σ NET
Dk
II JCJ
(0) -1
(75)
JCZ(Y)
Note that the predictions & usually are sparse vector, e-g. when calculating recall there are exactly k nonzero entries. This may allow for slightly more efficient calculation. We denote the set of correct predictions as S = I(y) n (S) and the missed labels as = I(y) \ S, such that I(y) = S SUT and the sum over subsets of Z(y) can be written nested sum for S and T. For convenience, abbreviate the
common factor as c(y) = [hezy p=m1 and set d(U)= = I[eeu (p) - 1). This results in
M U
1 Pj
M
d U
Recall(y, c
II jeu
dly)
(76)
+
|
KEV Ph
+
UCT
VCS
UcT
VC8
The second sum is almost independent of the first: If the number of elements V were constant, we could change the nested sums into product of two single sums. Therefore, collect terms basod on the number of elements in V and rearrange to arrive at
S
[8]
d M +
d(l))
R) = c(y)
= c(y))
Σ
Σ
(77)
d(V)
U
+
d(V)
VCS -
UCT
VCT
VCS
|
B Additional Theorems and Proofs
B.1 Unbiased Estimates for Binary Setting
Theorem (Uniquencss). Let [2] 2 2, p E (0,1), q E (0.p), and F M( F 2,R) functions. Let -- F be operator that maps function to unbiased estimate in the missing labels setting, such that for all (Z, Y, Y*) E Pp that fulfill the masking model with propensity and marginal holds
be a set of
q q= q=E E[],
vf" F: F:F FI 2) E(p(S")(Y
(28)
Then, p is related to the propensity scoring operator Pp by
(()")(. -p (v, 9)7
(29)
for some r E R.
Proof. The fact that G, fulfills the condition 28 follows from Theorem Because E[Y] q, the additional term has expectation zero.
Let. & be another operator for which the condition holds, then 28 is in particular also fulfilled for distribu- tions of the form
x, Y ~ 6(21, 1) + (1 (0))(22)))) 0),
(78)
where 5(x,y) denotes the Dirac measure of point (x, and q² = q/p. These are valid because g
P(Y = =11==PP- M, =p""=======----- =
Let us further write f P(f"), (y, = yg" (x) + 10" (x) and f(z 8) = 2g(x) + h(x). Since y E (0, 1], the decomposition into g and h is always possible.
32

---

Published in Transactions on Machine Learning Research (08/2025)
In this notation, we can explicitly calculate the expectations
EI = E|Y"g (X)++
= ("""x))))]((("""")"00""""""""""" ((()) (x2)
(79)
X]] = BIMY g(x) [(X]] = (())) q² )b(22).
(80)
By assumption on Q these two are equal:
r' (z1
g')2(2z)
(81)
q' (g +(- h(zz)) (21))
(82)
Sctting 01 = x2 =: x gives
('g pg(x)) h(x) - (x),,,
(83)
which can be plugged back into 82
q'(g" (m1) 4"(g"" (21) pg (11 11) + (1 - 4¹) (9' (x))) - pg(22))) p4 g(a1)
(84)
(1 00)9g (m1) + (1" g0 - - + - (0(022= =0.
(1- (x2) pPg(22) = 0
(85)
(86)
Since this equation holds for all 22 E X, it determines g up to a constant shift. Let zy E X be fixed and denote c g" (zo)/P- g(mr); then for arbitrary x X
g(x) - g" (xx)/p+
(87)
Putting this back into
[83)
gives
h(x) = ha())) - ppop" l1 (x)) qc.
(88)
Combining these two expressions shows the claim
B(f*)(,z) yg(x) + h(x)=
y9 y9*(x)) (a))
+ yc + h2) qc 5 p
gx) - hz)))) + (v -0)c.c. 2)..
(89)
p
B.2 Generalization Bound
In this section we present a proof for Theorem below:
To that end, we first proof some helper results as presented
Theorem 27. Let H. C M(X.5) be a function class, and f: y x & - la, bj be boanded, p Lipschhil continuous (in the second argument) function. Denote f = Fpf. Given a sample of n noisy training points, it holds with probability of at least 1 8 that
4 4-2p (H,, + (2 - (b (2-p)(b - a)
log(1/5)
sup [Ryl --n-)R
(90)
2n
sup (Ry(h) -i---R, RR,()) NEW
4 - 2p
p Rn
(2- p) pb- a)
log(1/8)
(91)
p
p
2n
Proof. First, we determine the Lipschitz-conslamt of J. For y 0, it is the same as that of S, so we only ncod to consider the y = case.
[(1,,,) [(1,22)) 5(1,51) + 1))(0,z1) - 5(1,22)) (p-1))
(92)
p
1- 11(0,z))- 1000-f(0 x20,
((11,1)) - -(1,00)
(93)
p
+ 1 1-p)
$
pl|-
xzll-
(94)
p p
33

---

Published in Transactions Machine Learning Research (08/2025)
In 193] we made use of the fact that p 1. This also implics that 2-p 2 1, and thus the Lipschitz
constant of f is given by 2-p p.
Next calculate the range of f. We have V X, that
a (p 1)b p S a = f(1, x) I bbs
=: b. b+ (p 1)a P
(95)
Here, the first and last inequality follow from p E (0, 1] and a & Define e b-a à Finally, we can construct a function for y x y - [0, 1] by the affine transformation for c- û) such that
R RylM - Rylh = c (R [k] - R ltl).
(96)
The right hand side can be bounded with probability 1 5 using Mohri al. 2018
Theorem 3.3) by
(1/(1/))
fm [b] & Rr (Jo1 a H) + R fm [b]
(97)
2n
As the Lipschitz-constant of for is c pp-1p-1(22 p), by the contraction lemma Shalev-Shwarke and 2014
Lemma 26.9) we have
Ra H) S co PR. (H).
(98)
Thus with probability 8 and Vh
Ry[h] - RylM s 122 p,,,(1))) + +oV 1og(1/8)
(99)
2n
2-p P PR (H) + (2 - p)(b - a)
/log(1/))
V
(100)
2n
The second bound follows by replacing f with ff.
This result is very similar to Natarajan et al. 22017 Lemma 8). However, that thoorem is missing a scaling factor with the range of the loss function, as argued below. For reference, the original statement of the theorem
Theorem 28 (Natarajan et al.] (2017 Lemma 8)). Let ((1,)) be L-Lipschilz (for every y). Then, for any E (0, 1), with probability at least 1-6, 5,
log(1/0)
max FEF
Rr, (f) D, (f) s 2L, RF) + v
(101)
2n
where L,p < 21/((1 - P+1 p-1) is the Lipschitz constant of La-
In the first step of the proof, they invoke a "Basic Rademacher bound between risks and empirical risks" that states
log(1/0)
max
RS (f) Ri. B, (f) < 22 F) JEF
(102)
2n
However, such a bound either requires the range la to be a subset of [0. 1] (Mohri et al. 2018 Thm 3.3), or introduces an additional factor front of the square root term in Shalev-Shwartz Thm 26.5). Also, they are using two-sided bound instead of a one-sided one as in the two cited thcorems, which means that noods to be replaced with 5/2 because the square-root term comes from an application of Mc. Diamids inequality.
Shwartz and Ben-Davin David 2014
34

---

Published in Transactions Machine Learning Research (08/2022) (08/2025)
Lemma 29. For any f E M( x R),,, p (0,1) and E|Y] = q, holds
1-P m
X)),, - S
with = -(00///),))000.)))))
(103)
P
sE
Proof. For notational convenience denote U = () and V = X). Substituting Br(s). can be simplified to
difference
-, f(,
= =Yp-' +p ((1 (X,
(1-))-11-10)) (1-
(p-1-1)(YU)) + p P-1yV - (YU
p
As by definition of it holds that IV VI m, the expectation is bounded by
1 BU - V)Il - 1-
1-p
E(Ym) ml S
qm.
(104)
p
P
p
Thcorem 9 (Gencralization bounds). Let H. be function class with Rademacher complexity Rr (H). Let r=yy x - [a, 6) for < b E IR be function that is p- Lipschitz continuous in its second argament. Let f = P=Pp((") and denote
inf Rÿ-11), [b], h= argmin R, [b], h= argmin R [k]. hER
(23)
hEl
as well as
c p R. (H) + (b a) log(2/0) (2/0)
2n
(24)
m = sfp(]s (1, ff (0,,))))
For a given sample of n points, it holds with probability at least 1
2 2-2
$ = R7 h
r
+ 2
(25)
p
1 m
= Rí. [P]
S +
+ 2c,
(26)
where q= = [ 1.
Proof. Let 6 and choose A such that.
wever R7-1111] S tc.
(105)
From this follows f P- S R7- [
R2. [A'] + and F -- & R2, [h]] - R2. [W/] + e.
We can apply Theorem 27 the function class (N' using that R. ((h' 0}) get with probability
1 - 8/2
R - Ry[h] (2 (b a)
log(2/0)
(106)
p
2n

---

Published in Transactions Machine Learning Research (08/2025)
For the first incquality, we can use the unbiasodness of f, and the near optimality of h regarding Ry bound
Rýy h
Rj.
R
h
R, [y]
(unbiasedness)
R h
R h
Rylh] + R,(N 100--14 R, + Ry [1]
R
R, h
+ -
(optimality)
[Ry[h] - R2 [hi) + Ry Rg(47-
sup bEk
Applying union bound to the remaining two terms, with probability 1
4-
R(H) + (2-p) a)
1og(2/6)
(2 (b) a)
log(2/))
P- set
p
2n
p
2n
- 2p Ri, + (b 160-00 v) log(2/5)
(107)
p
2n
With - 0 the first claim follows.
For h we can decompose the risk difference into
Rÿ- [b] [
R
[
R
[h]
+ Ryy [1]
R [M] + R. [M] -R7-1M
(108)
and look at the contributions separately. Because h is an ERM, we have
R [M] R [M]]
(109)
Further, using the unbiasedness and applying Lemma 29 to the function (x, + fly, f(y,h()))
Rg.
hb|
R,
[h]
R [h|
Ry- [A]
(unbiasedness)
R [
R. [
+ +Ry- (7) RR
(110)
$
m
+ R. [h]] - -Ry-
Lemma 29
p
$
p
m
sup NEW
[Ry- - R2 [h1)
(111)
p
We can apply Theorem 27 with p = 1 to get corresponding bounds for f Bof so that with probability
1 8/2 each
4-2
(2- 1)(b a)
1og(2/5)
sup keW
[R) - RR R
1 (H))
(112)
2n
R-- - R9. [W]] S 1)(6 - a)
(2/(2
(113)
2n
Thus, by union bound, with probability - 6, it holds that
1 1-p m + (H) 2(6 a)1
log(2/5)
Rí. [7 - R?-1h
c.
(114)
2n
Letting proves the claim.
36

---

Published in Transactions Machine Learning Research (08/2025)
B.3 Unbiased Estimates for Multilabel Setting
Theorem 19 (Multilabel Loss). Let (Z,Y", Y) E Pp (2), and ym x 2 - R. An unbiased version of I can be calculated using the propensity- scored expression Pp( ) given by
1/ pb) P -
E
f (y'
(53)
Pj
where y' 3 means {0, 13 v/3 S y)
Proof. As the binary case, we can use the finiteness of 13, write f as
(v) Σ f 1 f (1
(115)
ICl9
Σ
(1 x)
II
yo
II
(116)
ICN
NET
JEI
by rewriting the indicator function as products of yi and Vý- First, we show the unbiasedness for the expression
fly,,)= E .x)
U1 II
y/ Pj
(117)
Pi
ICH
ier
JET
Later, will show that this is in fact equivalent explicitly calculate
53
Using the linearity of the expectation we
MYY Pt
M,Y;
E(JYY,)) = Σ
(1
II
(118)
Pj
ICN
jEI
For fixed subset I rewrite
(1
x)
II NET
M,Y Ps
1
M,y
Σ
C X) II
ayg
(119)
Pj
jEI
JCH
SET
for appropriately chosen coefficients og E R. Using the independence of M, it follows that
(1 x)
II Bay MYY
= E
II
M
f
12) X)
II
aayi
(120)
LiGT
JET
II
(1)
II
= E
1 X)
II
aop,Y
(121)
JEJ
JET
Therefore, we can replace all occurrences of Mj the expectation with p; and compare the result
(166)
II P.Y.'
X]](Y,
Σ
E
f'
(1) X)
II
(122)
Ps
Pj
IC
HET
JEI
Σ
(1(
I[ Y iEr
II
(1 (1-
(123)
ICll
jET
(124)

---

Published in Transactions Machine Learning Research (08/2022 (08/2025)
Now we show that f= f: For any & I(y) there is a j E J such that y5 0, so the contribution of that summand is zero. Therefore
xly Em(io)
II
II
Mf
(125)
Pj
JCI(N)
NEG
NET
Now, for every j E I(y) we know that yj = 0, so we can simplify further
II NEG
1 )
(126)
Pt
pk
JCI(M)
KEI(N)
Finally, note that
- NET
11-
Pi
Ph -
(127)
=
ΛET(Y)N
Pk
VET
Pi
Ps
kEZly)
Pk
which proves the statement.
Theorem (Multilabel Uniqueness). Then debiasing operator Pp from Theorem unique, i.e., for any ; ym x 2 + R, any unbiased version is equal to Pp(f"). Formally, for all (Z, Y Y) P, (2) it holds that
EI 2) E[
(56)
then f = p.(l))
Proof. Let f be an arbitrary function f + R. We need to show that
(128)
Since 166 needs to work for all possible distributions of X and Y it needs to work in particular also for P(X- 2, y'} 1. Since can take only finitely many states, we can decompose Ø(f") into a sum these states. Since f is known to fulfill 56 the equation for f becomes
0 -=E[f(x - f(Y,)) Σ E[(f(2,)) YE2
= =X) Σ - f(x))))((xy)))PPe = =Y
y'E2"'
(129)
Next show that for all y it holds that f(x,y) flx = 0 via induction. First, assume that y"
0.
Then Pfy' = =Y = 1fy = =0, and [19 simplifies to
= [(r - fxx 0):
(130)
and therefore f and ʃ equal for this y*
Next, assume that f(y',z) x)= = f(y', x) for all y' that have at most m nonzero entries. Let y be a vector with + nonzero entries, then 129 can be written
Σ -( =Y -(x = Ve
b sm
=(((xy') f(x YJ. (131)
Here, the first sum vanishes because all the summands are using vector y' with at most m elements. Because we assume that all propensities are nonzero, the P(y" = YY factor nonzero, which implies that [(x,y")J(xx; yx) has to be zero.
Therefore, and f are identical. Since this holds for all x E X, the operators & and Pp have to be identical.

---

Published in Transactions Machine Learning Research (08/2025)
B.4 Multilabel upper bound
Theorem 25 (Normalized Label "pper-Boundes Let (2,Y",Y) E Pp (2), replactng the true labels with the unbiased estimate of the observed lobels as shown in Equation 63 results in an upper bound, whose error itself cnn be bounded by data- dependenn term
E
PJ Pj
E
Y Pj
2 E[T]] E[T]]
(70)
Ps
EyjtY, Y//Pj, and note that S;, being function of Y and M d is independent of Mj- By pulling known factors and using the independence of M and Y we can show that
Proof. For convenience denote S? Enjt Y and St S:=
E|S,
Y EEMM/// Y
y== S7.
(132)
S#C
3#
Expanding terms and using independence of M. then applying the tower property and pulling out the measurable factor results in
[
E
E
M 1+ S.
E
M
E
E Y r
-E
Y
Pi
1+ S
The function h: 20 + given by + 1/(1 = f) is convex, because its second derivative is 2(1 + t) which larger than zero for non-negative Because S; 2 0 almost surely, we can apply Jensen's 's inequality to the inner expectation and use 132
Y
Y + St
E T 2
E[T.].
S.
On the other hand we can use the Taylor formula with intermediate point Ç e [S) expand
1 1 S. - S
+ (S. - S7)²
(133)
I + S.
1
(1 S;) (1+ <)$
Using 2 0 to bound the denominator of the last term, then multiplying with Y, and taking the expectation gives
Y
E
<
E
+E {
(134)
S+
ST
The variance term can be calculated by substituting S, and S expanding the sum, and using the indepen- dence of M to show that the mixed terms are zero:
M,
E
1155-55710 5; = Y
Σ B 2
Mj -1) )
27
+ Σ Σ
B
E
Mj
1
E
M
Pj
Pk
131
itj (g(
M
M2
Y
Y
EE
-
+1
E
(135)
2
Pj
Pj
P3
3/
j

---

Published in Transactions Machine Learning Research (08 (202222)
R 0.264 1 0.00043
160000
R= 0.75 2. 0.00048
PuR = 0.242 0.0021
Pslt 0.725 0.0066
60000
140000
120000
100000
40000
50000
50000
50000
20000
40000
10000
20000
-0.25
0.75 1.50
-0.25
0.75
3.50
Figure Histograms of propensity-scored (PsR) and vanilla recall (R) for top-1 (left) and top-5 (right) predictions for the AmazonCat-150 13K dataset for DiSMEC model trained with a convex surrogate of the propensity-scored 0-1 loss. The y-axis denotes the number of examples in the test set for which the estimate falls into the corresponding bin. The errors have been calculated by boostrapping 95 % confidence interval. The dashed vertical lines denote the mean.
Experiments
C.1 PsRecall estimation
The networks used to generate the results in Table 3 were trained using the DiSMEC [Babbar and Schölkopf 2017] algorithm, with the loss function being either the squared-hinge-loss (VN) a sguurrd--hnng--ben based convex surrogate of the unbiased estimate of the 0-1 loss as described in Qaraci et al. 2021) The datascts
have been taken from the Extreme Classification Repository (Bhatia et al. 2016), and preprocessed by doing
tf-idf transformation.
Direct calculation of the unbiased estimate using 77 is prohibitively examples for the small subset samples in the dataset that have large number of observed labels (despite the average number of labels per instance being low, some XMC datasets do have outliers with many samples). We can still calculate an unbiased estimate in these cases, at the cost even further increase in variance: For these examples, we artificially generate subsample observed labels where even more labels have gone missing, and adjust the propensity accordingly. In practice, our implementation divides all propensities by two and drops each ground truth label with chance of 50% if the ground truth has more than 25 labels. To reduce the increase variance slightly, we average 100 subsamplings. This technique can be used recursively if the resulting subsample still has too many labels.
In Figure! 7. we show histograms for PSRecall estimates at the level of individual samples in the test set.
C.2 Normalized BCE
In the main text, we claim that the low performance unbiasod training with normalized BCE in the high-regulariizttonn regime is due to bad local minima. Here present supporting evidence.
As shown in Figure 8) the low performance is caused by high loss on training data (dashed lines) as opposed to generalization. However, for training with vanilla loss b), the loss noisy training data (i.e. the unbiased estimate computed on noisy training data) is much lower than for training with the unbiased loss c), where we directly try to optimize this quantity. There are two possible explanations for this behaviour: Either the switch to the unbiased loss shifts the balance of loss to regularizer such that the regularizer attains much more weight overall, and thus results in less optimization for the loss, or the optimization procodure gets stuck in local minimum.

---

Published in Transactions Machine Learning Research (08/2025)
0.150
0.125
0.100
Setting
0.075
vanilla
vanilla
loss
0.050
unbiased c)
unbiased c')
0.025
eval-on
clean-test
0.000
noisy-train
clean-train
-0.025
-0.550
10-6
10
10
10
10
10
10
L2
Figure 8: Normalized Binary cross-entropy different regularization strengths, evaluated on noisy training data, clean training data, and clean test data. Setting c') corresponds to unbiased training with vanilla pre-training.
These two causes can be distinguished by an experiment where the initial weights are chosen by pre-training with vanilla loss for ten epochs. If the reason for the bad performance were the regularization trade-off, then the following 20 epochs of unbiased training would increase the training loss until the tradc-off is reached. On the other hand, if the reason were local minima, then starting out close known "good" minimum would result in converging to that minimum.
Tigure& 8 exhibits the behaviour the second case, thus validating the local-minima hypothesis.
C.3 Precision and recall comparison figure
igure 9 shows a graphical representation of the tabular result presented in Table

---

Published in Transactions Machine Learning Research (08/200 (202)
BCE
90
SQH
80
70
60
50
40
30
Vanilla
Vanilla b)
Unbiased c)
20
Bound d)
P@1
Р03
P@5
R@1
R@3
R@5
P@1
P03
P@5
R@1
R@3
R@5
Figure 9: Precision and rocall at the optimal (for loss minimization) rogularization strength for decomposable (left) and normalized (right) training losses. These values have been calculated on clean test data. The error intervals denote standard deviation and have been determined using 5 runs.


Reviews:
[{"review_id": "wxFDtKP9N1", "reviewer": "Reviewer_xYnU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\nThe paper introduces well-formalized definitions and theorems, such as compatibility conditions, masking models, and the general unbiasing operator for multilabel losses (Theorem 19).\n\nA significant contribution, enabling unbiased training for recall-consistent objectives (as opposed to only precision-consistent ones).\n\nThe empirical analysis highlights when unbiased estimators are effective versus when high variance renders them unusable.\n\nThe theoretical and empirical study of variance growth in low-propensity settings is well-motivated and adds useful understanding to practical applications.\n\nThe paper bridges the gap between PU-learning, propensity scoring, and unbiased multilabel loss estimation in a coherent way.\n\nWeaknesses\n\nDespite efforts to limit the cost, the unbiased estimator for non-decomposable losses involves exponential complexity in label cardinality (though mitigated in sparse settings). This may limit scalability.\n\nExperiments are limited to synthetic or modified datasets. Evaluation on full-scale XMC benchmarks (e.g., Amazon-670K, WikiLSHTC) is absent due to the infeasibility of calculating the unbiased estimates—ironically undermining the full practical relevance.\n\nWhile convex upper bounds are useful in practice, the derivation often appears heuristic (e.g., replacing \n$$Y^*$$ with $$Y/p$$ in normalizations), and lacks tightness guarantees.\n\nSome readers may find the use of measure-theoretic language and intricate definitions (like compatibility or masking model) unnecessarily heavy for the intended ML audience.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the problem of learning with incomplete annotations in multilabel classification, particularly relevant in extreme multilabel settings where only a sparse subset of relevant labels is available for each instance. The authors:\n\nPresent a general mathematical framework to construct unbiased estimators of arbitrary loss functions (including non-decomposable ones) under a known missing-at-random label noise model.\n\nIntroduce theoretical guarantees such as uniqueness (Theorem 10, 20) and generalization bounds (Theorem 9), characterizing the inherent bias-variance trade-off in these estimators.\n\nDevelop a computationally tractable formulation for these unbiased losses under the masking model (Proposition 4), applicable even in high-dimensional output spaces with sparsely observed labels.\n\nConduct empirical evaluation demonstrating the limitations of unbiased losses in low-propensity regimes (e.g., high-variance estimators), and showing that in practice, upper-bounded convex surrogates often outperform the unbiased versions.\n\nThe paper unifies prior work on unbiased risk estimation and extends it to normalized reductions (for recall@k-consistent training), a previously underexplored setting in extreme multilabel classification.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Critical\nIn Section 5.1 (Theorem 19), explicitly quantify computational costs of the proposed unbiased estimators, and clarify in what real-world settings (label sparsity, low class cardinality) they are practically feasible.\n\nInclude a small-scale real-world dataset where exact unbiased estimates are computationally tractable and compare against baselines.\n\nInclude an ablation comparing upper-bound losses with original unbiased losses on real data to support the bias-variance discussion.\n\nRecommended (Not Critical)\nInclude more intuitive discussion of Theorem 19: A small worked-out example would help readers understand how the unbiasing operator is computed in practice.\n\nExplore whether data-dependent bounds (Section 6.2, Theorem 25) can be improved, and clarify what conditions would guarantee tightness.\n\nClarify assumptions in generalization bound (Theorem 9): Explain how realistic the assumptions are in the context of XMC tasks—especially the Lipschitz continuity and boundedness of the loss functions.\n\nFigure 2 could include clearer labeling and error bars for easier visual interpretation. Also clarify in caption what “vanilla” means.\n\nSeveral important results (e.g., Theorem 20, Lemma 21) refer readers to the appendix. Consider adding brief outlines or proof sketches in the main text to improve readability.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "dUQYjhBtoB", "reviewer": "Reviewer_8QZi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper offers a comprehensive and rigorous framework for deriving unbiased loss functions under missing-label noise, applicable to both decomposable and non-decomposable multilabel losses.\n\n2. Unlike prior work limited to decomposable losses, this approach covers a wide range of commonly used loss functions, including those aligned with precision and recall metrics.\n\n3. The paper establishes the uniqueness of the proposed unbiased estimators, ensuring theoretical consistency and robustness across different data distributions. It thoroughly explores the trade-off between bias and variance in training under label noise, and connects these insights to generalization behavior.\n\n4. To counteract the instability of high-variance unbiased losses, the paper proposes convex upper-bound surrogates, which are both practically feasible and theoretically justified.\n\nWeaknesses:\n\n1. While theoretically unbiased, the proposed estimators can suffer from extremely high variance, especially under low label propensity, leading to instability and poor generalization in practice. \n\n2. For datasets with very sparse labels or low propensity (common in XMC), the unbiased estimators may become infeasible to compute or unreliable, reducing their applicability in real-world settings.\n\n3. The unbiased estimators for non-decomposable losses require summing over subsets of observed labels, which can be computationally expensive in large label spaces, even with sparsity-based optimizations. It may be beneficial to include a complexity analysis of the proposed method, as this could provide further insight into its practical applicability and scalability.\n\n4. Most empirical studies are on moderately sized datasets or synthetically reduced subsets (e.g., top-100 labels of AmazonCat), which may not fully reflect performance in real extreme-scale XMC settings.\n\n5. The framework assumes access to accurate label propensity estimates, which may be difficult to obtain in many practical scenarios without strong assumptions or additional labeled data.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses multilabel classification under missing-label noise, a common issue in extreme multilabel classification (XMC) where positive labels may be missing, but negatives remain unaffected. The authors propose a general framework for constructing unbiased estimators of the true loss, extending beyond decomposable losses to non-decomposable and normalized losses, which are essential for recall-oriented metrics. They establish the theoretical uniqueness of these estimators and highlight the associated bias-variance trade-off, showing that although unbiased estimators correct for bias, they may induce high variance and overfitting. To mitigate this, the paper introduces convex upper bounds as practical surrogates. Experimental results confirm the theoretical insights, particularly regarding the limitations of unbiased estimation when label propensities are low.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please carefully checking the weaknesses.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "pbDGMIJFut", "reviewer": "Reviewer_Busv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- **Strengths**\n    1. It introduces a masking model. The formulation of this model can be seen as a generalization of a similar statement given in (Teisseyre et al., 2020) and is convenient for handling expectations in proofs and derivations.\n    2. It derives new results on uniqueness (Theorem 10) and variance of the unbiased estimators, and provides a generalization bound (Theorem 9) which is a corrected version of (Natarajan et al., 2017, Lemma 8).\n    3. It offers rigorous theoretical derivations for unbiased estimators in binary and multilabel cases, including proofs of existence, uniqueness, etc., which is meaningful.\n    4. Experiments are conducted on both synthetic and real data to investigate the proposed unbiased estimator.\n    5. The paper is well-structured, with clear logic from problem statement to experimental verification. The use of symbols and the presentation of figures and tables are also intuitive for readers.\n\n- **Weaknesses**\n    - The fonts in some images seem inconsistent. For example, the fonts on the horizontal and vertical axes of Figure 3. \n    - Some parentheses are used irregularly. For example, on page 22, there are expressions like “(b) for BCE loss\" and \"settings a)-d)\". \n    - The question mark \"?\" in Table 4 is likely to cause misunderstandings. It is recommended to directly mark \"lack\" instead.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates the setting of missing labels in binary and multi-label classification with a known missing rate. It points out that few methods have considered the propensity - scored precision, an unbiased estimate for precision-at-k during the training phase, and most methods are limited to loss functions decomposable over labels. However, if the surrogate task is consistent for optimizing recall, the resulting loss function is not decomposable over labels. Hence, this paper develops unbiased estimators for generic, potentially non-decomposable loss functions. Theoretically, it derives new results on uniqueness, variance, and generalization of the unbiased estimators in the binary case, and provides unbiased estimates for general multilabel functions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. It is recommended to polish some of the figures.\n2. Fix some typos.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)