acceptodds
Under review as a conference paper at ICLR 2027

Instance-dependent Complementary Multi-label Learning

Abstract

Complementary multi-label learning (CMLL) is a prevalent weakly supervised multi-label classification paradigm where each training instance is annotated with a complementary label set containing only irrelevant labels. Existing CMLL methods commonly assume that complementary labels are selected uniformly. However, this assumption is often violated in real-world scenarios, where the selection of complementary labels naturally depends on the characteristics of individual instances. In this paper, we study instance-dependent CMLL and propose ID-CMLL, a propensity-weighted framework for explicitly modeling and mitigating instance-dependent selection bias. We first formalize the instance-dependent complementary label generation mechanism and derive a selection-weighted unbiased risk estimator. Since the instance-conditioned selection probabilities are unknown, we introduce an identifiable double-logistic model over a fixed representation to factorize the observed complementary label probability, together with a semantic orientation mechanism for reliable propensity estimation. Empirical results demonstrate that ID-CMLL achieves superior performance against state-of-the-art CMLL and partial multi-label learning (PML) baselines.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Complementary Multi-label Learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_N3wJOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies complementary multi-label learning (CMLL), where each training instance is annotated only with labels that are certainly irrelevant. Existing methods assume complementary labels are selected uniformly, or model label-dependent but instance-independent selection. This paper models the selection probability as a function of the instance and proposes ID-CMLL.The paper proves identification up to permutation, consistent orientation, asymptotic unbiasedness, and an excess-risk bound. Experiments cover 11 multi-label datasets and 5 complementary-label generation mechanisms.

Critical strengths
  1. The problem is well posed and the gap is real. Instance-dependent selection is the natural next step after uniform and label-dependent CMLL, and the paper formalizes it cleanly with a per-label 2$\times$2 transition matrix.
  2. The theory is complete. Identification and orientation (Thm 2.9), asymptotic unbiasedness (Thm 2.11), and an excess-risk bound (Thm 2.12) form a coherent chain. The connection between Hajek normalization, boundedness, uniform integrability, and L1 convergence in Appendix I is well done.
Critical weaknesses
  1. All large-label datasets are truncated to K = 15, and the number of complementary labels is approximately K/2 on every dataset (Table 2: 7.44–7.51 for K = 15, 6.97 for K = 14, 2.96 for K = 6). It means eje_j could be relatively small. But the paper's own theory carries 1/e_min and 1/π_min in every bound, and Hajek normalization and clipping exist to handle this tail. The experiments never reach it.

2.There is no evidence that the estimated ee is accurate. The benchmark is synthetic, so the true ej(x)e_j(x) is known. The paper never reports it. It should be nice to report the possible error.

  1. The synthetic selection mechanism is built from the same posterior the model assumes. Appendix L generates complementary labels from scores sij=−αfj(xi)s_ij = −\alpha f_j(x_i), where ff is an MLP trained with full supervision. Selection probability is therefore a monotone function of the true relevance posterior. It will be helpful to add a setting where selection depends on an attribute orthogonal to relevance — image brightness, text length, class frequency, or annotator attention. In real annotation, whether an annotator mentions "giraffe" for a picture of a cat depends on salience, not on p(y=1∣x)p(y = 1 | x).

  2. Identification rests entirely on an unverified parametric assumption, and orientation can fail silently. The paper is explicit that the problem is non-identifiable nonparametrically, so Assumption 2.6 does all the work. I'm curious what will happen when Assumption 2.6 fails.

Questions for authors

The paper is evaluated on small, tabular benchmarks and does not position itself for the pretrain era. It's not really a weakness but it's better to include some discussion on this.

5 comments
AuthorsOpenReview ↗

We thank Reviewer N3wJ for recognizing the well-posed problem and the coherent theory chain from identification to the excess-risk bound. The five concerns on the K/2 target and the inverse weight tail, the accuracy of the estimated propensities, selection driven by attributes orthogonal to relevance, the reliance on Assumption 2.6, and the positioning for the pretrain era are answered below.

W1. All large-label datasets are truncated to K = 15, and the number of complementary labels is approximately K/2 on every dataset (Table 2 reports 7.44 to 7.51 for K = 15, 6.97 for K = 14 and 2.96 for K = 6). It means 1/ej could be relatively small. But the paper's own theory carries 1/emin and 1/πmin in every bound, and Hájek normalization and clipping exist to handle this tail. The experiments never reach it.

We sincerely thank the reviewer for this careful observation. In short, the K/2K/2 target fixes only the dataset-level average rather than individual propensities, the maximum inverse propensity weight reaches 17.6 in our experiments, and 1/(emin⁡πmin⁡)1/(e_{\min}\pi_{\min}) governs the positivity-dependent part of the worst-case bound, while Hájek normalization and the non-negative correction stabilize the empirical objective.

First, regarding the K/2K/2 target, we follow the CTL protocol (Gao et al., 2025b), whose complementary-set size has mean exactly K/2K/2, and ID-SAR adopts the same target to keep the supervision budget comparable across settings. In ID-SAR (Appendix L), each irrelevant label is selected with probability ej(xi)=σ(β−αfj(xi))e_j(x_i)=\sigma(\beta-\alpha f_j(x_i)), where the global offset β\beta calibrates only the dataset-level expected cardinality. For a fixed label, the log-odds difference between two instances is −α(fj(xi)−fj(xi′))-\alpha(f_j(x_i)-f_j(x_{i'})) for any β\beta, so individual propensities can still vary across instances. In addition, truncation to the 15 most frequent labels follows Gao et al. (2023) and keeps the label with the smallest irrelevance rate, so it leaves πmin⁡\pi_{\min} unchanged.

Second, regarding the tail of the weights, over truly irrelevant instance-label pairs, the mean ground-truth propensity ranges from 0.536 to 0.717 across the eleven datasets, whereas the minimum is only 0.057 to 0.161 (Table R4). The largest inverse weight therefore reaches 6.2 to 17.6, up to an order of magnitude above the weight at the mean propensity, and 1/(emin⁡πmin⁡)1/(e_{\min}\pi_{\min}) ranges from about 12 to 25.

Third, regarding theory and stabilization, Assumption 2.10 requires ej(x)≥emin⁡>0e_j(x)\geq e_{\min}>0 and πj≥πmin⁡>0\pi_j\geq\pi_{\min}>0, and the factor 1/(emin⁡πmin⁡)1/(e_{\min}\pi_{\min}) quantifies the effect of these positivity margins in the worst-case bound of Theorem 2.12. Hájek normalization keeps each normalized weighted-risk term within [0,CL][0,C_L] regardless of the size of the raw inverse weights (Appendix I), while the non-negative correction keeps the empirical objective non-negative. Table 4 supports the practical role of both mechanisms. Removing the non-negative correction lowers Average Precision on eurlex_dc from 0.877 to 0.221, while removing Hájek normalization causes consistent degradation on several datasets. These stabilization mechanisms improve the numerical behavior of the empirical objective but do not replace the positivity conditions required by our theoretical analysis.

 

Table R4. Ground-truth propensity statistics in the main experiments. emin⁡e_{\min} and Max 1/e1/e are taken over all truly irrelevant instance-label pairs, and πmin⁡\pi_{\min} is the smallest label-wise irrelevance rate.

Datasetemin⁡e_{\min}Max 1/e1/eπmin⁡\pi_{\min}
bookmark0.05717.60.826
delicious0.1456.90.561
eurlex_dc0.05717.40.779
eurlex_sm0.06515.40.677
rcv1-s10.06116.40.762
rcv1-s20.1029.80.729
rcv1-s30.06016.70.736
rcv1-s40.07513.30.735
rcv1-s50.07513.30.728
scene0.08112.30.779
yeast0.1616.20.249

W2. There is no evidence that the estimated ej is accurate. The benchmark is synthetic, so the true ej is known. The paper never reports it. It should be nice to report the possible error.

We sincerely thank the reviewer for this constructive suggestion. Since our protocol provides the exact ground-truth selection probabilities, we now evaluate the estimated propensities directly and report their errors across the eleven datasets.

First, regarding propensity estimation errors, Table R1 compares the estimated propensities e^j(x)\hat e_j(x) obtained using Eq. (15) with the ground-truth ID-SAR selection probabilities over all truly irrelevant instance-label pairs, the only pairs that can be selected (Assumption 2.2). Averaged over the eleven datasets, the MAE is 0.0660 and the RMSE is 0.0764, with MAE below 0.06 on nine datasets. The fold standard deviations are at most 0.0015 for MAE and 0.0029 for RMSE. Since the ground truth is generated by an auxiliary MLP rather than by the double-logistic family, this evaluation is conducted outside the well-specified case.

Second, regarding the implications for learning, under its stated conditions, Theorem K.1 bounds the gap between our feasible objective and the oracle objective with the true (π,e)(\pi,e) by ϵn≤C1δπ,n+C2δe,n\epsilon_n\le C_1\delta_{\pi,n}+C_2\delta_{e,n}, where δπ,n\delta_{\pi,n} and δe,n\delta_{e,n} denote the estimation errors of π\pi and ee, respectively. Theorem 2.12 carries this gap into the excess-risk bound. Table R1 thus complements the theory by reporting propensity estimation errors in practice.

 

Table R1. Propensity estimation accuracy of ID-CMLL on eleven benchmarks (mean ±\pm std over five folds).

DatasetMAE ↓\downarrowRMSE ↓\downarrow
bookmark0.0577 ±\pm 0.00070.0763 ±\pm 0.0010
delicious0.2024 ±\pm 0.00110.2137 ±\pm 0.0010
eurlex_dc0.0179 ±\pm 0.00060.0198 ±\pm 0.0004
eurlex_sm0.0597 ±\pm 0.00100.0695 ±\pm 0.0004
rcv1-s10.0270 ±\pm 0.00070.0354 ±\pm 0.0007
rcv1-s20.0262 ±\pm 0.00030.0351 ±\pm 0.0007
rcv1-s30.0275 ±\pm 0.00150.0371 ±\pm 0.0020
rcv1-s40.0274 ±\pm 0.00100.0378 ±\pm 0.0018
rcv1-s50.0279 ±\pm 0.00060.0367 ±\pm 0.0010
scene0.0530 ±\pm 0.00150.0684 ±\pm 0.0029
yeast0.1993 ±\pm 0.00120.2101 ±\pm 0.0013
Average0.06600.0764

W3. The synthetic selection mechanism is built from the same posterior the model assumes. Appendix L generates complementary labels from scores sij=−αfj(xi)s_{ij} = −αf_j(x_i), where f is an MLP trained with full supervision. Selection probability is therefore a monotone function of the true relevance posterior. It will be helpful to add a setting where selection depends on an attribute orthogonal to relevance, such as image brightness, text length, class frequency, or annotator attention. In real annotation, whether an annotator mentions “giraffe” for a picture of a cat depends on salience, not on p(y=1∣x)p(y = 1|x).

We sincerely thank the reviewer for this constructive suggestion. In short, our framework does not require selection to depend on relevance, the part-dependent mechanism in Appendix L already uses no relevance predictor, and in a new setting driven by an attribute residualized against the label indicators, ID-CMLL outperforms CTL on all four ranking metrics on six of the seven datasets.

First, regarding the framework, we agree that annotation can be driven by factors other than relevance. ID-SAR uses a relevance predictor because it mimics annotators who readily reject obviously irrelevant labels, but ID-CMLL does not rely on this form. Theorem 2.5 requires only Assumption 2.2, so ej(x)e_j(x) may be any instance-dependent selection probability satisfying that assumption, including one driven by brightness, text length, or salience, and the double-logistic model gives ej(x)e_j(x) its own parameters (wj2,cj2)(\mathbf{w}_{j2},c_{j2}), separate from those of 1−ηj(x)1-\eta_j(x).

Second, regarding existing evidence, the part-dependent mechanism in Appendix L computes selection scores by a nonlinear transformation of a random projection of label-specific feature subsets, without any relevance predictor. Under it, ID-CMLL achieves lower Ranking Loss and higher Average Precision than CTL on ten of the eleven datasets (Table 6).

Third, regarding the new attribute-driven setting, we compute an instance-level attribute from the input features, remove its empirical linear association with the label indicators, and use the standardized residual tit_i to set ej(xi)=σ(αti+β)e_j(x_i)=\sigma(\alpha t_i+\beta), with β\beta calibrated to the same expected cardinality K/2K/2. The resulting attribute is linearly uncorrelated with the label indicators in the empirical sample. On the seven datasets of our ablation study, ID-CMLL outperforms CTL on all four ranking metrics on six datasets and achieves a lower Hamming Loss on five (Table R5). The largest gains appear on eurlex_dc and eurlex_sm, where Average Precision rises from 0.583 to 0.860 and from 0.567 to 0.741. On rcv1-s1, CTL performs better on the ranking metrics, whereas ID-CMLL reduces Hamming Loss from 0.446 to 0.134. We have added this setting and its results to Appendix L of the revised manuscript.

 

Table R5. CTL versus ID-CMLL under attribute-driven selection (mean ± std).

DatasetCoverage Error (CTL) ↓Coverage Error (Ours) ↓One Error (CTL) ↓One Error (Ours) ↓Ranking Loss (CTL) ↓Ranking Loss (Ours) ↓Average Precision (CTL) ↑Average Precision (Ours) ↑Hamming Loss (CTL) ↓Hamming Loss (Ours) ↓
bookmark0.196 ± 0.0060.167 ± 0.0080.440 ± 0.0190.412 ± 0.0080.171 ± 0.0060.144 ± 0.0080.655 ± 0.0100.691 ± 0.0070.558 ± 0.1540.232 ± 0.005
delicious0.587 ± 0.0090.557 ± 0.0060.522 ± 0.0080.453 ± 0.0090.297 ± 0.0070.261 ± 0.0050.568 ± 0.0060.607 ± 0.0060.329 ± 0.0110.341 ± 0.005
eurlex_dc0.178 ± 0.0110.050 ± 0.0040.565 ± 0.0240.206 ± 0.0120.188 ± 0.0110.051 ± 0.0040.583 ± 0.0190.860 ± 0.0090.053 ± 0.0030.078 ± 0.008
eurlex_sm0.319 ± 0.0100.194 ± 0.0130.507 ± 0.0400.293 ± 0.0270.229 ± 0.0100.118 ± 0.0100.567 ± 0.0200.741 ± 0.0220.095 ± 0.0020.073 ± 0.002
rcv1-s10.134 ± 0.0110.162 ± 0.0130.276 ± 0.0240.411 ± 0.0850.071 ± 0.0050.102 ± 0.0110.784 ± 0.0090.697 ± 0.0420.446 ± 0.0380.134 ± 0.031
scene0.153 ± 0.0120.140 ± 0.0070.494 ± 0.0210.443 ± 0.0390.167 ± 0.0130.151 ± 0.0080.708 ± 0.0160.737 ± 0.0190.370 ± 0.0690.185 ± 0.011
yeast0.483 ± 0.0030.471 ± 0.0050.251 ± 0.0270.237 ± 0.0070.202 ± 0.0070.193 ± 0.0060.720 ± 0.0110.727 ± 0.0090.249 ± 0.0060.238 ± 0.008
Reviewer_LgccOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies instance-dependent complementary multi-label learning (CMLL), addressing a meaningful and practical problem that has received limited attention. The authors propose ID-CMLL, which uses a double-logistic model to estimate instance-dependent selection probabilities and constructs a propensity-weighted risk estimator with stabilization techniques. Experiments on benchmark datasets show promising performance compared with existing methods.

Critical strengths
  1. The paper addresses a practically relevant and relatively underexplored problem, as complementary label selection naturally depends on instance characteristics in real-world scenarios. Explicitly modeling the instance-dependent selection distribution is a reasonable and well-motivated approach to addressing such selection bias, providing a good starting point for this paper.
  2. The paper provides a comprehensive theoretical analysis, including identifiability, unbiased risk estimation, and consistency guarantees, which strengthens the proposed framework.
  3. The paper is generally well-written and well-organized, with clear mathematical formulations and detailed theoretical proofs that make the proposed method easy to follow.
Critical weaknesses
  1. I concern Assumptions 2.6 and 2.7 seem quite strong, especially the requirement that the average irrelevance probability must exceed the selection probability for every label. This may not hold when complementary supervision is relatively dense, as in the experiments where AvgCLs is close to (K/2). I hope authors should verify whether these assumptions hold in their experimental settings.
  2. I think the estimation of the instance-dependent selection probabilities is the central to this work, but the paper only evaluates downstream classification performance. Since the complementary labels are synthetically generated, why not directly evaluate the accuracy of the estimated selection probabilities?
  3. In Table 6, the proposed method still achieves strong improvements under uniform selection, sometimes performing similarly to the instance-dependent setting. This raises the question of how much improvement actually comes from instance-dependent propensity modeling. More direct ablations, such as using constant propensities or removing IPW, would be helpful.
  4. Removing warm-up causes severe performance drops on some datasets, especially eurlex_dc and eurlex_sm. Since warm-up provides both the feature representation and factor initialization, it is unclear which part is responsible for this degradation. This also raises concerns about the stability of the double-logistic estimation.
  5. In Table 2, AvgCLs is consistently close to (K/2) across datasets with different label distributions. I find this observation interesting and would appreciate some discussion on why this pattern occurs, especially under instance-dependent selection.
Questions for authors

Refer to the weaknesses above. I would be willing to raise my score if the authors can adequately address these concerns.

4 comments
AuthorsOpenReview ↗

We thank Reviewer Lgcc for recognizing the practical relevance of the problem, the comprehensive theoretical analysis, and the clear presentation. The five concerns on the strength and verification of Assumptions 2.6 and 2.7, the direct evaluation of the estimated propensities, the contribution of instance-dependent modeling, the role of warm-up, and the AvgCLs pattern near K/2 are answered below.

W1. I concern Assumptions 2.6 and 2.7 seem quite strong, especially the requirement that the average irrelevance probability must exceed the selection probability for every label. This may not hold when complementary supervision is relatively dense, as in the experiments where AvgCLs is close to K/2. I hope authors should verify whether these assumptions hold in their experimental settings.

We sincerely thank the reviewer for this constructive comment. In short, the two assumptions concern only propensity estimation rather than the risk correction, Assumption 2.7 is compatible with dense supervision and holds on 153 of 155 labels in our experiments, and ID-CMLL remains effective when the selection mechanism departs from the double-logistic form.

First, regarding the role of the two assumptions, Eq. (8) shows that qj(x)=(1−ηj(x))ej(x)q_j(x)=(1-\eta_j(x))e_j(x) cannot be split into its two factors without some restriction. Assumption 2.6 provides one by modeling both factors as affine-logistic functions of a shared, fixed learned representation, the usual form of a classifier head, and Assumption 2.7 only decides which identified factor is the selection probability, through a label-wise condition on population averages rather than on every instance. In contrast, the risk identity in Theorem 2.5 with the true propensities needs only Assumption 2.2, and Theorems 2.11 and 2.12 use the estimated propensities only through their estimation error. The two assumptions thus provide one explicit route to consistent propensities (Theorem 2.9), separate from the risk correction itself.

Second, regarding dense supervision, Eq. (8) gives AvgCLs =∑j=1KE[(1−ηj(X))ej(X)]=\sum_{j=1}^{K}\mathbb{E}[(1-\eta_j(X))e_j(X)], so AvgCLs close to K/2K/2 means that a label is irrelevant and selected with probability about 0.5 on average over labels. Since ej≤1e_j\le 1, the label-averaged selection probability exceeds this value by at most AvgGLs$/K$, which is 0.07 to 0.12 on eurlex, rcv1, and bookmark (Table 2). It is therefore at most about 0.62, whereas the label-averaged irrelevance probability is at least about 0.88, so a density of K/2K/2 is compatible with Assumption 2.7. Our direct label-wise check with Δj=E[1−ηj(X)]−E[ej(X)]\Delta_j=\mathbb{E}[1-\eta_j(X)]-\mathbb{E}[e_j(X)], computed from the ground-truth ID-SAR probabilities, confirms this (Table R2). The condition holds on 153 of 155 labels and on every label of ten datasets, with Δj≥0.0739\Delta_j\ge 0.0739, and the two exceptions are on yeast, where ID-CMLL still achieves the best Ranking Loss, Average Precision, and Hamming Loss (Table 3).

Third, regarding Assumption 2.6 in practice, the ground-truth ID-SAR propensities are generated by an auxiliary MLP rather than the double-logistic family. Nevertheless, over the truly irrelevant instance-label pairs, our estimates achieve an average MAE of 0.0660 and RMSE of 0.0764 across the eleven datasets (Table R1 in our response to Q2). The part-dependent mechanism in Appendix L departs further from the affine-logistic form, and ID-CMLL still outperforms CTL in Ranking Loss and Average Precision on ten of the eleven datasets, with Average Precision gains of 0.16 to 0.30 on the five rcv1 splits (Table 6).

 

Table R2. Label-wise verification of Assumption 2.7, where Δj=E[1−ηj(X)]−E[ej(X)]\Delta_j=\mathbb{E}[1-\eta_j(X)]-\mathbb{E}[e_j(X)].

DatasetSatisfied / TotalMin. Δj\Delta_j
bookmark15/150.3642
delicious15/150.0739
eurlex_dc15/150.3493
eurlex_sm15/150.2671
rcv1-s115/150.3196
rcv1-s215/150.3024
rcv1-s315/150.3079
rcv1-s415/150.3118
rcv1-s515/150.3027
scene6/60.2929
yeast12/14−0.0448-0.0448
Total153/155

W2. I think the estimation of the instance-dependent selection probabilities is the central to this work, but the paper only evaluates downstream classification performance. Since the complementary labels are synthetically generated, why not directly evaluate the accuracy of the estimated selection probabilities?

We sincerely thank the reviewer for this valuable suggestion. We agree that the selection probabilities are central to ID-CMLL, and since our protocol provides their exact ground truth, we now evaluate them directly. The estimated propensities achieve an average MAE of 0.0660 and an RMSE of 0.0764 across the eleven datasets, and our theory characterizes how propensity estimation errors affect downstream risk.

First, regarding the direct evaluation, Table R1 compares e^j(x)\hat e_j(x) with the ground-truth ID-SAR selection probabilities over all truly irrelevant instance-label pairs, the only pairs that can be selected (Assumption 2.2). Averaged over the eleven datasets, the MAE is 0.0660 and the RMSE is 0.0764, and the MAE is below 0.06 on nine datasets. Since the ground truth comes from an auxiliary MLP rather than from the double-logistic family, this evaluation also covers recovery beyond the well-specified case.

Second, regarding the link to downstream performance, under its stated conditions, Theorem K.1 bounds the gap between our feasible objective and the oracle objective with the true (π,e)(\pi,e) linearly by the estimation errors of π\pi and ee, and Theorem 2.12 carries this gap into the excess-risk bound. Table R1 thus complements the theory by showing the propensity estimation accuracy in practice.

 

Table R1. Propensity estimation accuracy of ID-CMLL on eleven benchmarks (mean ± std over five folds).

DatasetMAE ↓\downarrowRMSE ↓\downarrow
bookmark0.0577 ±\pm 0.00070.0763 ±\pm 0.0010
delicious0.2024 ±\pm 0.00110.2137 ±\pm 0.0010
eurlex_dc0.0179 ±\pm 0.00060.0198 ±\pm 0.0004
eurlex_sm0.0597 ±\pm 0.00100.0695 ±\pm 0.0004
rcv1-s10.0270 ±\pm 0.00070.0354 ±\pm 0.0007
rcv1-s20.0262 ±\pm 0.00030.0351 ±\pm 0.0007
rcv1-s30.0275 ±\pm 0.00150.0371 ±\pm 0.0020
rcv1-s40.0274 ±\pm 0.00100.0378 ±\pm 0.0018
rcv1-s50.0279 ±\pm 0.00060.0367 ±\pm 0.0010
scene0.0530 ±\pm 0.00150.0684 ±\pm 0.0029
yeast0.1993 ±\pm 0.00120.2101 ±\pm 0.0013
Average0.06600.0764

W3. In Table 6, the proposed method still achieves strong improvements under uniform selection, sometimes performing similarly to the instance-dependent setting. This raises the question of how much improvement actually comes from instance-dependent propensity modeling. More direct ablations, such as using constant propensities or removing IPW, would be helpful.

We sincerely thank the reviewer for this helpful suggestion. We have added the requested ablation, which isolates the gain of instance-dependent propensities, and we explain below why ID-CMLL also performs strongly under uniform selection.

First, regarding the ablation, we replace the estimated propensities with label-specific constants and keep all other components unchanged. Because constant weights cancel in the Hájek normalization, this variant is mathematically equivalent to removing IPW while keeping Hájek normalization, so it covers both variants suggested by the reviewer. As shown in Table R3, the full ID-CMLL attains higher or equal Average Precision on all eleven datasets and lower or equal Ranking Loss on ten of them, with Average Precision gains of up to 0.025 on eurlex_sm. This ablation is now included in Section 3.3 and Table 4 of the revised manuscript.

Second, regarding uniform selection, uniform selection is not equivalent to constant propensities. It first samples the number of complementary labels and then draws them uniformly from the irrelevant labels of each instance, so the probability that an irrelevant label is selected depends on how many irrelevant labels the instance has. The propensity ej(x)e_j(x) therefore still varies across instances, which ID-CMLL can capture but label-specific constants cannot. Together with the stabilizing components validated in Table 4, this explains the strong performance of ID-CMLL under uniform selection.

 

Table R3. Ablation of instance-dependent propensities under ID-SAR (mean ± std over five folds). Constant ee replaces the estimated propensities with label-specific constants, and Ours is the full ID-CMLL of Table 3.

DatasetRanking Loss (Constant ee) ↓\downarrowRanking Loss (Ours) ↓\downarrowAverage Precision (Constant ee) ↑\uparrowAverage Precision (Ours) ↑\uparrow
bookmark0.124 ±\pm 0.0060.120 ±\pm 0.0080.721 ±\pm 0.0030.730 ±\pm 0.009
delicious0.237 ±\pm 0.0060.234 ±\pm 0.0070.644 ±\pm 0.0040.648 ±\pm 0.006
eurlex_dc0.046 ±\pm 0.0040.044 ±\pm 0.0040.863 ±\pm 0.0050.877 ±\pm 0.010
eurlex_sm0.102 ±\pm 0.0040.099 ±\pm 0.0060.742 ±\pm 0.0140.767 ±\pm 0.013
rcv1-s10.069 ±\pm 0.0060.068 ±\pm 0.0050.807 ±\pm 0.0030.821 ±\pm 0.011
rcv1-s20.090 ±\pm 0.0060.087 ±\pm 0.0060.774 ±\pm 0.0130.781 ±\pm 0.022
rcv1-s30.099 ±\pm 0.0090.090 ±\pm 0.0200.752 ±\pm 0.0210.772 ±\pm 0.057
rcv1-s40.105 ±\pm 0.0110.101 ±\pm 0.0100.756 ±\pm 0.0150.756 ±\pm 0.015
rcv1-s50.102 ±\pm 0.0060.109 ±\pm 0.0130.715 ±\pm 0.0160.733 ±\pm 0.019
scene0.098 ±\pm 0.0040.095 ±\pm 0.0050.826 ±\pm 0.0110.832 ±\pm 0.012
yeast0.180 ±\pm 0.0050.180 ±\pm 0.0060.743 ±\pm 0.0070.744 ±\pm 0.009

W4. Since warm-up provides both the feature representation and factor initialization, it is unclear which part is responsible for this degradation.

We sincerely thank the reviewer for raising this important point. In short, the warm-up stage supplies both the frozen representation and an informative factor initialization. The ablation points to the importance of initialization, while the propensity errors and sensitivity results support the stability of the subsequent estimation. ID-CMLL further improves on the warm-up objective by correcting the learning objective.

First, regarding the source of the drops, the warm-up stage plays two separate roles. It learns the frozen backbone on which both factors are defined, and it initializes the two factors, the first from the warm-up classifier and the second from the observed complementary-label frequencies (Appendix D). The ablation in Table 4 retains the same frozen backbone and removes only this factor initialization. Specifically, Average Precision drops from 0.877 to 0.221 on eurlex_dc and from 0.767 to 0.222 on eurlex_sm, highlighting the importance of informative initialization rather than the representation. Initialization matters because the objective in Eq. (12), like other double-logistic likelihoods, is non-convex (Furmańczyk et al., 2023). Theorem 2.9 characterizes its global minimizer, while the warm-up initialization provides an informative starting point for the non-convex optimization.

Second, regarding stability, with this initialization the estimation is accurate and stable on the two datasets. On eurlex_dc and eurlex_sm, Assumption 2.7 holds for every label with minimum margins of 0.349 and 0.267 (Table R2), which provide positive separation for the orientation rule in Eq. (15). The propensity MAE on these two datasets is 0.0179±0.00060.0179\pm0.0006 and 0.0597±0.00100.0597\pm0.0010, and the fold standard deviations of MAE are at most 0.0015 on all eleven datasets (Table R1). Performance is also insensitive to the regularization coefficient λn\lambda_n over [10−1,102][10^{-1},10^{2}] (Appendix B).

Third, regarding the gain beyond warm-up, both stages use the same complementary labels, so the gain comes from correcting the learning objective rather than from extra supervision. To illustrate, let qj(x)=(1−ηj(x))ej(x)q_j(x)=(1-\eta_j(x))e_j(x) denote the conditional probability of observing a complementary label. Replacing ej(x)e_j(x) in Eq. (6) by a label-specific constant cjc_j yields, under the BCE loss, the conditional minimizer fj∗(x)=1−qj(x)/cjf_j^*(x)=1-q_j(x)/c_j whenever qj(x)≤cjq_j(x)\le c_j, instead of the true posterior ηj(x)=1−qj(x)/ej(x)\eta_j(x)=1-q_j(x)/e_j(x). Hard negatives with ej(x)<cje_j(x)<c_j thus receive inflated relevance scores simply because they are rarely selected as complementary labels. ID-CMLL corrects this bias through the weights 1/e^j(x)1/\hat e_j(x), with exact unbiasedness under the true propensities (Theorem 2.5) and asymptotic unbiasedness under the estimated ones (Theorem 2.11). Compared with the GDF warm-up objective, ID-CMLL raises Average Precision from 0.783 to 0.877 on eurlex_dc and from 0.679 to 0.767 on eurlex_sm, and reduces the fold standard deviation of Average Precision on eurlex_sm from 0.081 to 0.013 (Table 3).

 

W5. In Table 2, AvgCLs is consistently close to K/2 across datasets with different label distributions.

We sincerely thank the reviewer for this insightful observation. AvgCLs is close to K/2K/2 by design, because ID-SAR adopts the expected cardinality of the standard CTL protocol as its global calibration target, and this target leaves the instance-dependent variation intact.

First, regarding the design, CTL (Gao et al., 2025b) samples the complementary-set size from p(s)=(Ks)/(2K−2)p(s)=\binom{K}{s}/(2^K-2), whose mean is exactly K/2K/2, and our uniform setting follows this protocol. Using the same target for ID-SAR keeps the amount of complementary supervision comparable across selection settings, so that performance differences reflect the selection mechanism rather than the amount of supervision.

Second, regarding instance dependence, ID-SAR selects each truly irrelevant label j∈Iij \in \mathcal{I}_{i} of xix_i independently with probability ej(xi)=σ(β−αfj(xi))e_j(x_i)=\sigma(\beta-\alpha f_j(x_i)), where a single offset β\beta per dataset is set by bisection so that 1n∑i∑j∈Iiej(xi)=K/2\frac{1}{n} \sum_{i} \sum_{j \in \mathcal{I}_{i}}e_j(x_i)=K/2 before applying the boundary safeguards. Since β\beta shifts all logits equally, the log-odds difference between two instances for the same label, −α(fj(xi)−fj(xi′))-\alpha(f_j(x_i)-f_j(x_{i'})), does not depend on β\beta. Only the dataset-level average is calibrated, and each instance keeps a random number of complementary labels with its own mean. The observed average complementary-label cardinality differs from K/2K/2 by at most 0.06 because of random sampling and the safeguards that keep every complementary set nonempty and, when possible, smaller than the irrelevant-label set.

Reviewer_HB4SOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies complementary multi-label learning with instance-dependent label selection. It derives an unbiased risk estimator when selection probabilities are known. It then estimates these probabilities using two logistic factors over a frozen representation. A mean-based rule assigns their roles. Normalization and a non-negative correction stabilize training. The paper provides theoretical guarantees under stated assumptions. Experiments on 11 datasets with synthetic complementary labels show strong ranking results.

Critical strengths
  1. Complementary labels can depend on the instance. The proposed risk correction directly addresses this bias. This makes the framework useful beyond uniform selection.

  2. On rcv1-s1, AP improves from 0.675 for the best baseline to 0.821 (Tab. 3). The ablations also show the value of warm-up and non-negative correction. These results support the method’s practical value in the tested settings.

Critical weaknesses
  1. Double-logistic factorization, identification up to permutation, and joint likelihood estimation already appear in [Furmańczyk et al., Double logistic regression approach to biased positive-unlabeled data]. This work is not discussed. Since the proposed objective operates label by label, the advance over applying that approach to each label remains unclear.

  2. Correct factor orientation requires Assumption 2.7: E[1-\eta_j(X)] >= E[e_j(X)] + \delta_j, \delta_j>0. The paper does not check this condition or report propensity estimation errors. The nonlinear selection tests are useful, but do not establish accurate factor recovery. Thus, the reported gains do not fully validate the claimed bias correction.

Questions for authors
  1. What is the main technical advance over the double-logistic PU method above? How does a label-wise adaptation compare under the same representation?

  2. Does Assumption 2.7 hold across the tested labels? Can you report propensity estimation errors and compare against training with true propensities?

  3. How are the scores in Appendix L converted into sampling probabilities? In the difficulty setting, does the score change the number of selected labels? If it only enters a within-instance softmax, the shared score would cancel.

3 comments
AuthorsOpenReview ↗

We thank Reviewer HB4S for recognizing the practical value of correcting instance-dependent selection bias and the gains supported by the ablations. The three concerns on the novelty over the double-logistic PU method, the verification of Assumption 2.7 together with propensity estimation errors, and the conversion from scores to sampling probabilities in Appendix L are answered below.

Q1&W1. Double-logistic factorization, identification up to permutation, and joint likelihood estimation already appear in [Furmańczyk et al., Double logistic regression approach to biased positive-unlabeled data]. This work is not discussed. Since the proposed objective operates label by label, the advance over applying that approach to each label remains unclear.

We sincerely thank the reviewer for pointing us to this relevant work, which we will discuss in the revised related work. For binary PU data, Furmańczyk et al. show that a product of two logistic functions of the raw features is identifiable up to an interchange of its factors, estimate both factors by joint likelihood, and list the extension to multi-label data as future work. Applied label by label, their method would correspond only to the propensity stage of ID-CMLL, with the fitted posterior factor used directly as the classifier. ID-CMLL goes beyond this in four respects.

First, regarding the shared representation, although Eq. (12) is evaluated label by label, the factors of all KK labels are identified on one representation learned jointly from the complementary labels, whereas the PU method fits linear logistic models on raw features and leaves neural extensions to future work. Our theory also covers the fact that this representation is estimated from the same sample (Assumption 2.8, Appendices C.1 and H), and our identification requires agreement only on a compact support containing an open set, as suits bounded network features, rather than on the whole Euclidean space.

Second, regarding cross-label dependence, the complementary labels of an instance are annotated jointly and may be dependent across labels, which does not arise in binary PU learning. Assumption 2.2 specifies only label-wise conditional selection probabilities and does not impose conditional independence across labels. Since Eq. (12) uses a label-wise composite likelihood, it does not require modeling their joint dependence.

Third, regarding factor orientation, the PU method resolves the permutation by assuming that the posterior parameter vector has a larger norm than the propensity parameter vector. This condition can be reversed by rescaling individual features and has no probabilistic meaning on a learned representation. ID-CMLL instead orients the factors by Average Irrelevance Dominance (Assumption 2.7), a condition on the probabilities themselves that reflects the label sparsity of multi-label data, is invariant to reparameterizing the representation, and makes the empirical rule in Eq. (15) consistent (Theorem 2.9).

Fourth, regarding the final classifier, in the PU method the fitted logistic posterior is itself the classifier, so the final predictor retains the logistic parametric form. In ID-CMLL the two factors serve only as nuisance estimates, and the final classifier is learned over a flexible hypothesis class through the propensity-weighted risk with Hájek normalization and the non-negative correction, whose contributions are examined in Table 4. We establish asymptotic unbiasedness of the risk estimator, an excess-risk bound for the final classifier, and a bound on the objective gap induced by nuisance estimation (Theorems 2.11, 2.12 and K.1).

Q2&W2. Correct factor orientation requires Assumption 2.7, E[1−ηj(X)]>=E[ej(X)]+δj,δj>0E[1-\eta_j(X)] >= E[e_j(X)] + \delta_j, \delta_j>0. The paper does not check this condition or report propensity estimation errors. The nonlinear selection tests are useful, but do not establish accurate factor recovery. Thus, the reported gains do not fully validate the claimed bias correction. Does Assumption 2.7 hold across the tested labels? Can you report propensity estimation errors and compare against training with true propensities?

We sincerely thank the reviewer for this constructive suggestion. Using the exact ground truth of our synthetic protocol, we verify Assumption 2.7 label by label and directly evaluate propensity estimation errors. We also relate the feasible objective to its oracle counterpart and report a constant-propensity ablation.

First, regarding Assumption 2.7, we check it label by label on all eleven datasets using Δj=E[1−ηj(X)]−E[ej(X)]\Delta_j=\mathbb{E}[1-\eta_j(X)]-\mathbb{E}[e_j(X)], computed from the ground-truth ID-SAR selection probabilities. As shown in Table R2, the condition holds on 153 of 155 labels and on every label in ten datasets, with Δj≥0.0739\Delta_j\ge 0.0739. The two exceptions occur in yeast, where the minimum gap is −0.0448-0.0448. Despite these two violations, ID-CMLL still achieves the best Ranking Loss, Average Precision, and Hamming Loss on yeast (Table 3).

Second, regarding propensity estimation errors, Table R1 compares e^j(x)\hat e_j(x) with the ground truth over all truly irrelevant instance-label pairs, the only pairs that can be selected (Assumption 2.2). Averaged over the eleven datasets, the MAE is 0.0660 and the RMSE is 0.0764, with MAE below 0.06 on nine datasets and MAE standard deviations across folds of at most 0.0015. Since the ground truth is generated by an auxiliary MLP rather than by the double-logistic family, this evaluation is conducted outside the well-specified case.

Third, regarding oracle training, under its stated conditions, including Assumption 2.7, Theorem K.1 bounds the gap between our feasible objective and the oracle objective using the true (π,e)(\pi,e) by ϵn≤C1δπ,n+C2δe,n\epsilon_n\le C_1\delta_{\pi,n}+C_2\delta_{e,n}, where δπ,n=max⁡j∣π^j−πj∣\delta_{\pi,n}=\max_j|\hat\pi_j-\pi_j| and δe,n=max⁡j∣e^j−ej∣∞\delta_{e,n}=\max_j|\hat e_j-e_j|_\infty. Theorem 2.12 carries this objective gap into the excess-risk bound. Table R1 reports MAE and RMSE as empirical summaries of propensity estimation error. These average metrics complement the theorem but are not direct estimates of its sup-norm error terms.

Fourth, regarding the bias correction itself, the constant-propensity ablation in Table 4 replaces e^j(x)\hat e_j(x) with label-specific constants while keeping all other components unchanged. This lowers Average Precision on all seven ablation datasets, for example from 0.767 to 0.742 on eurlex_sm, and supports the contribution of instance-dependent propensity correction.

 

Table R1. Propensity estimation accuracy of ID-CMLL on eleven benchmarks (mean ± std over five folds).

DatasetMAE ↓\downarrowRMSE ↓\downarrow
bookmark0.0577 ±\pm 0.00070.0763 ±\pm 0.0010
delicious0.2024 ±\pm 0.00110.2137 ±\pm 0.0010
eurlex_dc0.0179 ±\pm 0.00060.0198 ±\pm 0.0004
eurlex_sm0.0597 ±\pm 0.00100.0695 ±\pm 0.0004
rcv1-s10.0270 ±\pm 0.00070.0354 ±\pm 0.0007
rcv1-s20.0262 ±\pm 0.00030.0351 ±\pm 0.0007
rcv1-s30.0275 ±\pm 0.00150.0371 ±\pm 0.0020
rcv1-s40.0274 ±\pm 0.00100.0378 ±\pm 0.0018
rcv1-s50.0279 ±\pm 0.00060.0367 ±\pm 0.0010
scene0.0530 ±\pm 0.00150.0684 ±\pm 0.0029
yeast0.1993 ±\pm 0.00120.2101 ±\pm 0.0013
Average0.06600.0764

 

Table R2. Label-wise verification of Assumption 2.7, where Δj=E[1−ηj(X)]−E[ej(X)]\Delta_j=\mathbb{E}[1-\eta_j(X)]-\mathbb{E}[e_j(X)].

DatasetSatisfied / TotalMin. Δj\Delta_j
bookmark15/150.3642
delicious15/150.0739
eurlex_dc15/150.3493
eurlex_sm15/150.2671
rcv1-s115/150.3196
rcv1-s215/150.3024
rcv1-s315/150.3079
rcv1-s415/150.3118
rcv1-s515/150.3027
scene6/60.2929
yeast12/14−0.0448-0.0448
Total153/155

Q3. How are the scores in Appendix L converted into sampling probabilities? In the difficulty setting, does the score change the number of selected labels? If it only enters a within-instance softmax, the shared score would cancel.

We sincerely thank the reviewer for this careful question. The scores enter a sigmoid with a global offset rather than a within-instance softmax, so in the difficulty setting the shared score changes the expected number of selected labels and does not cancel.

First, regarding the conversion, for each instance xix_i and each truly irrelevant label j∈Ii={j∣yij=0}j \in \mathcal{I}_{i}=\{j \mid y_{ij}=0\}, the Bernoulli inclusion probability is pij=σ(sij+β)p_{ij}=\sigma(s_{ij}+\beta). The score sijs_{ij} equals −αfj(xi)-\alpha f_j(x_i) for ID-SAR, αaj\alpha a_j for CCN, −αd~i-\alpha\tilde d_i for difficulty, and α[tanh⁡(zij)+0.5sin⁡(2zij)]\alpha[\tanh(z_{ij})+0.5\sin(2z_{ij})] for part-dependent selection. The global offset β\beta is calibrated by bisection so that the expected number of complementary labels averages K/2K/2 over the dataset before the boundary correction, and each irrelevant label is then sampled independently before that correction, without fixing the number of selected labels in advance.

Second, regarding the difficulty setting, the standardized score d~i\tilde d_i is shared by all irrelevant labels of xix_i, so pij=σ(−αd~i+β)p_{ij}=\sigma(-\alpha\tilde d_i+\beta) and the expected number of complementary labels of xix_i before the boundary correction is ∣Ii∣ σ(−αd~i+β)|\mathcal{I}_i|\,\sigma(-\alpha\tilde d_i+\beta). Easier instances therefore receive more complementary labels in expectation and harder ones fewer. Since the offset fixes only the dataset-level average, this instance-level variation is preserved and the shared score does not cancel. Both points are now clarified in the revised Appendix L.

Comments on the paper

2 comments

Dear Area Chair,

We sincerely thank you for your time and effort in facilitating this discussion, and we are deeply grateful to Reviewers HB4S, Lgcc, and N3wJ for their constructive feedback. We are encouraged that all three reviewers recognized the value of modeling instance-dependent selection in complementary multi-label learning (CMLL). Reviewer HB4S noted that our risk correction directly addresses instance-dependent bias and makes the framework useful beyond uniform selection. Reviewer Lgcc considered the problem practically relevant and relatively underexplored, the approach well motivated, the theoretical analysis comprehensive, and the paper generally well written. Reviewer N3wJ considered the problem well posed with a real gap, the formalization clean, and the theory complete, with a coherent chain from identification to an excess-risk bound.

We would like to briefly highlight two points from our detailed responses.

  1. Contributions and novelty. We formalize instance-dependent selection in CMLL, going beyond uniform and instance-independent selection, and establish a theoretical chain under explicitly stated assumptions. The chain runs from an exactly unbiased risk estimator under known propensities (Theorem 2.5), through identifiable propensity estimation with consistent orientation (Theorem 2.9), to a stabilized objective that is asymptotically unbiased (Theorem 2.11) and has an excess-risk bound that explicitly accounts for propensity estimation error (Theorems 2.12 and K.1). Beyond a direct label-wise application of existing double-logistic factorization, ID-CMLL identifies the factors of all labels on a shared learned representation, uses a label-wise composite likelihood valid under dependence across labels, and orients the factors through a probability-based condition invariant to reparameterizing the representation. The factors serve only as nuisance estimates for a propensity-weighted risk with Hájek normalization and non-negative correction.

  2. Role and empirical support of Assumptions 2.6 and 2.7. Without some restriction, the observed complementary-label probability cannot be split into its irrelevance and selection factors. Assumption 2.6 makes the two factors identifiable up to permutation and Assumption 2.7 determines their orientation (Theorem 2.9). We would like to clarify that both assumptions serve only propensity estimation. The risk correction under true propensities requires only Assumption 2.2 (Theorem 2.5), and the risk guarantees depend on the estimated propensities only through their estimation error (Theorems 2.11 and 2.12). To stress-test Assumption 2.6, we evaluated ID-CMLL under selection mechanisms not generated from the double-logistic family, including the MLP-generated ID-SAR of the main experiments, the part-dependent and difficulty-dependent mechanisms in Appendix L, and the attribute-driven mechanism added for Reviewer N3wJ. ID-CMLL remains effective under these mechanisms. Assumption 2.7 holds for 153 of 155 labels in our ID-SAR setting (see Table R2 in our response to HB4S Q2).

We are grateful to Reviewer Lgcc for indicating willingness to raise the score if the concerns are adequately addressed, and we have responded to each concern point by point. The constant-propensity ablation, the attribute-driven setting, and the clarified Appendix L are now incorporated into the revised manuscript. We sincerely thank you for your time and careful consideration. We hope our responses are helpful for your evaluation and would be glad to provide any further clarification.

Respectfully,

The Authors

Dear Reviewers and Authors,

As a quick reminder, the author-reviewer discussion period will close on November 18.

@Reviewers: Please make sure to read the authors' rebuttals, acknowledge their responses, and engage in further discussion if any points remain unclear. While final decisions are not made at this stage, we ask that you carefully re-evaluate your ratings in light of the new clarifications and experimental results:

Increase your score if the authors have satisfactorily resolved your concerns and strengthened the paper.

Decrease your score if new, unaddressed issues have emerged during the discussion.

Maintain your score if critical concerns remain unresolved.

Please note that you are under no obligation to change your rating, provided your final score accurately reflects the current state of the manuscript. To ensure a fair evaluation, please ground your assessment in concrete evidence rather than personal preference, and consider whether the work offers meaningful scientific value to the ICLR community.

Thank you very much for your time, thoughtful engagement, and contributions to the review process.

Best regards,

Area Chair

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.