acceptodds
Under review as a conference paper at ICLR 2027

Embracing Biased Transition Matrices for Complementary-Label Learning with Many Classes

Abstract

*Complementary-label learning* (CLL) is a weakly supervised paradigm for multiclass classification, where each training instance comes with a complementary label indicating a class that the instance does *not* belong to. After nearly a decade of research, CLL still faces a long-standing scalability barrier: as the number of classes grows from the scale of CIFAR-10 to that of TinyImageNet-200, existing methods learn almost nothing meaningful. We show that this barrier is not intrinsic to the problem, but tied to a common modeling choice. Most approaches assume a uniform transition matrix when modeling complementary-label generation, while the potential of assuming or leveraging a biased (non-uniform) transition matrix remains underexplored, despite some empirical successes on real-world data. Through a systematic study, we demonstrate that performance can be significantly improved by deliberately designing a biased transition matrix that restricts complementary labels to a subset of possible classes. Motivated by this finding, we propose *bias-induced constrained labeling* (BICL), a principled and practical framework spanning from data collection to training that properly leverages such bias for solving CLL. Extensive experiments demonstrate that BICL substantially improves CLL performance and, most importantly, breaks this barrier, enabling effective learning on CIFAR-100 and TinyImageNet-200 with more than sevenfold accuracy improvements.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Complementary-label learning, Biased-Induced Constrained Labeling, Biased transition matrices

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_yrKvOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

"Complementary label learning" basically "not this class" labels stop working beyond 10-20 classes because each label almost rules out nothing, and the information gain is very little. This paper first groups similar images using some embedding model and, for each group, restricts the set of possible labels to only four label options. It then has a VLM pick out the one that doesn't fit per image. With this approach, the information gain is much more. The accuracy on CIFAR-100 rises from about 5% to 47%.

Critical strengths
  • This tackles a real limit of complementary label learning by scaling it from 20 classes to 100+ classes
  • Honest ablations over diff learners, encoders, vlms, prompts etc with careful theory that doesn't overclaim
Critical weaknesses
  • Swapping the VLM for a random pick within the same four classes loses only 1 to 2 points. This shows that the design choice that matters more is the label set and not the VLM.
  • The paper offers a very weak practical use because strong vision models already label CIFAR-scale data very well, and nothing is tested beyond 200 classes.
  • From my reading, the gain mostly comes from image clustering not the labels, and obvious simple baselines are missing. There is no comparison with a strong vision model labeling the images directly or with a simple classifier trained on the same image features using a few "true" labels.
  • The method isn't really tested as it would ideally be used. Instead of training on VLMs' actual answers,the authors generate the labels from each image's true class, so the results are likely better than what the method would get in practice.
Questions for authors
  • What would the results be when training on VLMs actual answers?
  • What would the simple baseline in which you train on a few, possibly true, labels be? That seems like the most appropirate baseline.
Reviewer_uMK7OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper explores the problem of complementary-label learning in scenarios where the number of labels is large. The core idea is to employ a biased transition matrix to modify the existing mechanism for selecting complementary labels, thereby enhancing the model's overall performance. Experimental results demonstrate significant performance gains on datasets with a large number of labels.

Critical strengths
  1. The authors' concept is clear, straightforward, and intuitive; it effectively extends the generation mechanism for complementary labels and proposes a practical, concrete solution.
  2. The substantial improvement in experimental performance represents a notable breakthrough in this field.
Critical weaknesses
  1. The method relies on clustering as a preliminary step. This approach carries inherent risks: if the data distribution leads to suboptimal clustering results, the model's performance may be negatively affected.
  2. While the design of the transition matrix is intuitive, learning a matrix that accurately captures the underlying relationships is challenging in practice. The authors' theoretical and empirical discussion regarding the transition matrix appears somewhat insufficient.
Questions for authors
  1. Since clustering is an unsupervised learning technique, how do the authors determine whether a given clustering result is adequate to support the model's subsequent learning process? Is there a clear, theoretically grounded criterion for this assessment?
  2. In multi-label learning, it is possible to encounter instances that share the same labels but possess distinct features. How does this scenario affect the learning of the transition matrix?
  3. Can the proposed approach be integrated with existing multi-label learning algorithms? Furthermore, are there specific conditions or constraints under which this mechanism is applicable?
Reviewer_yUC5OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

Authors propose Complementary-label learning (CLL) for multiclass classification, where a not-class indicator is also provided. They mention that modelling choice limits the performance in CLL space. Authors propose a bias-induced constrained labeling (BICL), where a biased transition matrix restricts complementary labels to a subset of possible classes. Results are shown on 2 databases: CIFAR 100 and tinyImagenet200. VLM helps in picking a small complementary set from wide array of negative classes.

Critical strengths
  1. Questioning the usual CLL methods by picking the candidate set is a great idea
  2. The work strictly addresses CLL at scale, which most of the existing studies does not explicitly target
  3. Good with ablations
Critical weaknesses
  1. I get the motivation in scnerios where numbers of classes are huge. However, I'm curious on performance of the proposed algorithm on small number of classes like CIFAR10 2. To address "long-standing scalability bottleneck in nearly a decade of CLL research" does not translate that authors compare against a decade old paper of Ishida et al. (2017). Please compare with recent CLL papers. 3. Minor issue: VLM first mentioned in line 62, followed by 107 and 84, but described in line 193 4. The restriciting to a smaller complementary classes idea is good. However, more analysis is needed here. For ex, does hard complementary classes (similar looking but different classes) help more or not. If yes, what happens if we add more hard looking complementary classes, and until what point we can keep adding? 5. The headline 7×/8× improvements are rhetorically inflated. Ratios against accuracies near random chance exaggerate practical progress. A change from roughly 4–6% to 32–46% is substantial in percentage points, but “8×” is not the most informative characterization. The comparison demonstrates that more informative labels help, not necessarily that BICL is a superior learning algorithm. 6. No evidence that complementary annotation is actually cheaper: The motivation repeatedly assumes that negative annotation is cheaper than true-class annotation. Yet presenting a VLM or human with 4 carefully chosen class names is not demonstrated to reduce human errors, VLM cost, annotation time etc.
  2. What if hierarchy exists amongst label or it is a scenario of multi-label classification? How does the setting change?
Questions for authors

Check weaknesses listed above.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.