- 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
- 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.
- 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
- 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 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 is accurate. The benchmark is synthetic, so the true is known. The paper never reports it. It should be nice to report the possible error.
-
The synthetic selection mechanism is built from the same posterior the model assumes. Appendix L generates complementary labels from scores , where 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 .
-
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
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 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 by , where and denote the estimation errors of and , 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 std over five folds).
| Dataset | MAE | RMSE |
|---|---|---|
| bookmark | 0.0577 0.0007 | 0.0763 0.0010 |
| delicious | 0.2024 0.0011 | 0.2137 0.0010 |
| eurlex_dc | 0.0179 0.0006 | 0.0198 0.0004 |
| eurlex_sm | 0.0597 0.0010 | 0.0695 0.0004 |
| rcv1-s1 | 0.0270 0.0007 | 0.0354 0.0007 |
| rcv1-s2 | 0.0262 0.0003 | 0.0351 0.0007 |
| rcv1-s3 | 0.0275 0.0015 | 0.0371 0.0020 |
| rcv1-s4 | 0.0274 0.0010 | 0.0378 0.0018 |
| rcv1-s5 | 0.0279 0.0006 | 0.0367 0.0010 |
| scene | 0.0530 0.0015 | 0.0684 0.0029 |
| yeast | 0.1993 0.0012 | 0.2101 0.0013 |
| Average | 0.0660 | 0.0764 |
W3. The synthetic selection mechanism is built from the same posterior the model assumes. Appendix L generates complementary labels from scores , 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 .
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 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 its own parameters , separate from those of .
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 to set , with calibrated to the same expected cardinality . 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).
| Dataset | Coverage 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) ↓ |
|---|---|---|---|---|---|---|---|---|---|---|
| bookmark | 0.196 ± 0.006 | 0.167 ± 0.008 | 0.440 ± 0.019 | 0.412 ± 0.008 | 0.171 ± 0.006 | 0.144 ± 0.008 | 0.655 ± 0.010 | 0.691 ± 0.007 | 0.558 ± 0.154 | 0.232 ± 0.005 |
| delicious | 0.587 ± 0.009 | 0.557 ± 0.006 | 0.522 ± 0.008 | 0.453 ± 0.009 | 0.297 ± 0.007 | 0.261 ± 0.005 | 0.568 ± 0.006 | 0.607 ± 0.006 | 0.329 ± 0.011 | 0.341 ± 0.005 |
| eurlex_dc | 0.178 ± 0.011 | 0.050 ± 0.004 | 0.565 ± 0.024 | 0.206 ± 0.012 | 0.188 ± 0.011 | 0.051 ± 0.004 | 0.583 ± 0.019 | 0.860 ± 0.009 | 0.053 ± 0.003 | 0.078 ± 0.008 |
| eurlex_sm | 0.319 ± 0.010 | 0.194 ± 0.013 | 0.507 ± 0.040 | 0.293 ± 0.027 | 0.229 ± 0.010 | 0.118 ± 0.010 | 0.567 ± 0.020 | 0.741 ± 0.022 | 0.095 ± 0.002 | 0.073 ± 0.002 |
| rcv1-s1 | 0.134 ± 0.011 | 0.162 ± 0.013 | 0.276 ± 0.024 | 0.411 ± 0.085 | 0.071 ± 0.005 | 0.102 ± 0.011 | 0.784 ± 0.009 | 0.697 ± 0.042 | 0.446 ± 0.038 | 0.134 ± 0.031 |
| scene | 0.153 ± 0.012 | 0.140 ± 0.007 | 0.494 ± 0.021 | 0.443 ± 0.039 | 0.167 ± 0.013 | 0.151 ± 0.008 | 0.708 ± 0.016 | 0.737 ± 0.019 | 0.370 ± 0.069 | 0.185 ± 0.011 |
| yeast | 0.483 ± 0.003 | 0.471 ± 0.005 | 0.251 ± 0.027 | 0.237 ± 0.007 | 0.202 ± 0.007 | 0.193 ± 0.006 | 0.720 ± 0.011 | 0.727 ± 0.009 | 0.249 ± 0.006 | 0.238 ± 0.008 |
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/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) 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/2 target, we follow the CTL protocol (Gao et al., 2025b), whose complementary-set size has mean exactly K/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)), where the global offset β calibrates only the dataset-level expected cardinality. For a fixed label, the log-odds difference between two instances is −α(fj(xi)−fj(xi′)) for any β, 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 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) ranges from about 12 to 25.
Third, regarding theory and stabilization, Assumption 2.10 requires ej(x)≥emin>0 and πj≥πmin>0, and the factor 1/(eminπ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] 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 and Max 1/e are taken over all truly irrelevant instance-label pairs, and πmin is the smallest label-wise irrelevance rate.