acceptodds
Under review as a conference paper at ICLR 2027

On Learning with Ambiguous Labels

Abstract

We study learning in the situation where each training example comes with a set of at most possible labels containing the correct one. The learner may also predict up to labels for each new input, and makes an "error” if its prediction omits the correct label. For countable input and label spaces and any fixed , we identify a combinatorial "dimension” whose finiteness guarantees that such learning is possible. We then obtain upper and lower bounds on sample complexity that match up to logarithmic factors in the worst case for every fixed finite . At a fixed sufficiently high success probability and for sufficiently small , the required number of examples grows, up to logarithmic factors, linearly with this "dimension” and with , where is the desired error. We also obtain a separation between exact and ambiguous labels, by exhibiting a single class for which exact training labels allow learning from examples, while ambiguous labels require examples. Finally, when training label sets omit the correct label with probability , we achieve error at most with high probability, without knowing , by allowing prediction width and using a sample size nearly linear in at fixed dimension and confidence. Under the weaker assumption of finite -list DS dimension alone, the worst-case necessary and sufficient prediction width is , with absolute constants, for sufficiently small error and sufficiently high fixed success probability.

Primary area:
learning theory
Keywords:
PAC learning, ambiguous labels, partial-label learning, list learning, sample complexity

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_CZ5aOpenReview ↗
Rating
2(−1)
Confidence
4(+2)
Informativeness
2
Presentation
2(−1)
Soundness
1(−2)
Read review
Paper summary

This paper studies learning from ambiguous label sets when predictions may also be lists. It introduces a structural dimension and establishes sample complexity bounds, including a separation between exact and ambiguous supervision.

Critical strengths
  • The bounds are pretty tight. For a fixed prediction width, the upper and lower bounds match in their dependence on accuracy, up to log factors.
  • The insight makes sense. Even if we let the learner return several labels, ambiguity in the training data can still make learning much harder. Seeing how longer prediction lists help with this is also interesting.
Critical weaknesses

To me, the writing has a very obvious AI-generated feel, and the presentation needs substantial rewriting. The paper moves too quickly into technical results without sufficiently explaining why this problem matters. The opening provides little literature context, and the related work does not clearly connect the different research directions to the proposed setting. I can see what the paper proves, but I am still missing a convincing explanation of why this is an important question to ask.

Questions for authors

As mentioned, why is this problem important, and what real-world scenarios fit your setting? I would appreciate a clearer explanation of what motivates this particular setting and what we learn from studying it.

1 comment

Thank you for the review. The motivating situation is supervision that narrows down the correct label without identifying it uniquely. Examples include an annotator supplying several plausible categories, or a coarse annotation corresponding to several fine-grained classes. If this ambiguity persists across examples, a single-label prediction need not be identifiable; a short prediction list can preserve the remaining uncertainty.

The statistical question is then whether allowing such lists removes the cost of ambiguous supervision. Our results show that it need not: on the same hypothesis class and with the same allowed prediction size, ambiguous labels can require polynomially more samples than exact labels. We also identify when learning is possible at equal observation and prediction widths, and how increasing prediction width can reduce the sample requirement. These conclusions distinguish uncertainty that can be accommodated by short lists from uncertainty that still incurs a substantial statistical cost.

To make this motivation and significance clearer, we revised Sections 1–2 to introduce the problem and its main conclusions before the detailed bounds, explain the notation and dimension, and connect the related models through their observations and objectives. Example 2.7 develops a familiar ordered-threshold class and shows how the learnability criterion applies.

We would also appreciate details of any specific mathematical concern underlying the soundness assessment, so that we can address it directly.

Reviewer_9khqOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This work considers a new learning theory setting where each training example comes with a set of at most l possible labels containing the correct one. The learning algorithm is also allowed to predict L>=l possible labels and the prediction is marked as correct if th ethe correct label lies within the L predicted labels. This work identifies a combinatorial dimension whose finiteness guarantees that such learning is possible. They derive upper and lower bounds on the sample complexity that match upto logarithmic factors in the worst case and show that the required number of samples grows upto logarithmic factors linearly in this dimension. They also show a separation between learning with ambiguous labels vs. learning with exact labels. They also derive bounds for the case when there is a small probability \rho where the correct label does not lie within the l labels.

Critical strengths
  • The ambiguous learning setting introduced by this paper is an interesting setting. It is interesting to include both input width and prediction width.
Critical weaknesses
  • The presentation of the work needs to be improved a lot. After the introduction, the paper presents main results without properly defining the notation. The first equation mentions m without defining what m is. The DS dimension is not explained anywhere. The related work talks about exact-label list learnability setting without explaining how it is different from their setting. There are a lot of other settings which are defined without explaining mathematically how they differ from the setting in the paper.
  • The related work section should be discussed in depth while clearly stating what results are obtainable from the previous works and what novelty does this work add.
  • The paper does not talk about how the techniques used in the paper differ from the previous works and what was the main challenge in extending the technical proofs from the previous work.
  • It is unclear from reading the paper on the dependence of bounds in terms of the input width vs. the prediction width.
Questions for authors
  • In the abstract, the authors mention the separability of exact learning setting vs ambiguous learning but it is not clear if they define this in terms of the input labels l vs. the prediction labels L. This difference should be clearly separated.

  • In terms of the upper and lower bounds of Theorem 3.1 and 5.1, there is a big gap between the dependence on L. Could the authors explain if this can tightened or what is the main technical challenge?

1 comment

Thank you for the review. Section 1 now introduces the notation and DS intuition before the bounds. Section 1.2 compares prior models by their observations, losses, and assumptions. It identifies the imported exact-label guarantees and the finite-class randomized-policy guarantee, then distinguishes our dimension-dependent results, equal-width characterization, statistical separation, and prediction-width threshold.

Sections 1.1 and 3.1 clarify the technical obstacle: exact-label encoders require hidden labels. Enumerating compatible codes guarantees a good decoder without identifying it. The general construction completes narrow decoders separately and uses an observable prediction game; the large-width construction uses fractional coverage and rounding.

The abstract now compares, for each fixed ℓ\ell, one class independent of L,ϵ,δL,\epsilon,\delta under exact training labels and bags of at most ℓ\ell labels, with the same allowed prediction size LL.

The dependence-on-LL gap remains open. We now state that the bounds match in the accuracy exponent for fixed ℓ,L\ell,L. Section 3.1 explains that the present proof keeps its block size K=Θℓ(Dϵ−(ℓ−1))K=\Theta_\ell(D\epsilon^{-(\ell-1)}) independent of LL, while larger LL improves the update gain only logarithmically. This is a limitation of that proof. The lower bound's L−ℓL^{-\ell} term requires ϵL2≤1/102400\epsilon L^2\le1/102400. Separately, Theorem 3.2 gives nearly inverse-linear dependence at L≥⌈384ℓ2/ϵ⌉L\ge\lceil384\ell^2/\epsilon\rceil.

Reviewer_8gg8OpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies multi-class classification when the labels of training samples can be ambiguous, in the sense that samples can have multiple candidate labels (at most l) but only 1 is correct. The goal of the paper is to find a predictor whose test-time predictions disagree with the true one with probability at most ε. Since the training set may be completely uninformative the prediction cannot be a single label so the predictor is allowed to output a list of L labels with L >= l.

The paper proposes a combinatorial notion - reference-deletion dimension Delta_l(H) - that characterizes learnability under ambiguity l under a hypothesis class H when the learner is allowed to output L=l labels. It also provides nearly tight sample complexity bounds. For a setting with reference-deletion dimension D, it shows that D/ε^l samples are sufficient up to polylogarithmic factors and l-dependent constants for learning and provides examples for which a matching dependency is necessary for any fixed finite L >= l.

Additionally the paper shows that this exponential dependence on l on the accuracy parameter can be avoided if one allows lists that grow with ε. Specifically with L=O(l^2/ε), D/ε samples suffice (up to polylogarithmic factors and l-dependent constants).

Moreover in this large L regime, the stronger reference-deletion dimension can be replaced by the weaker l-list DS dimension, introduced by Charikar and Pabbaraju. Writing s for this dimension, the paper obtains sample complexity nearly linear in s/ε, up to logarithmic factors and l-dependent constants. They also provide a lower bound showing that L=Theta(l^2/ε) is also necessary for learning under the l-list DS dimension.

Critical strengths

The paper proposes an interesting setting of learning with ambiguous labels and cleverly combines list learnability bounds for the setting. It paints a nice picture of the trade-offs required for learning showing that with fixed-size output lists L, the sample complexity crucially grows exponentially with l and that one can bypass it by allowing lists that grow with eps.

Critical weaknesses

No major weaknesses

Questions for authors

How would the results change in the weaker setting that one is allowed to output any list that intersects with the target label list of size at most l? In this case, it seems like the list-DS dimension should suffice. This is closer to the literature on partial labels.

1 comment

Thank you for the review. Yes, if we keep the clean model with a common hidden target h in H and change the loss to R∩(M)=Pr⁡{M(X)∩B=∅}R_\cap(M)=\Pr\{M(X)\cap B=\emptyset\}, finite s=dℓDS(H)s=d_{\ell\mathrm{DS}}(H) suffices already at L=ℓL=\ell. The predictor does not receive the query bag. Definition 2.1 and Remark 2.3 now distinguish this loss from hidden-label coverage.

Here is the argument. For s≥1s\ge1, Lemma A.12 supplies a fixed width-ℓ\ell decoder with r=Oℓ(slog⁡(2m))r=O_\ell(s\log(2m)) labeled records. Enumerate the at most (ℓm)r(\ell m)^r index/label-rank codes from the observed bags and select a decoder intersecting every training bag; the hidden true-label code guarantees existence. For each fixed code, conditioning on its selected records leaves at least m−rm-r independent observations. If its intersection loss exceeds ϵ\epsilon, consistency on those observations has probability at most e−ϵ(m−r)e^{-\epsilon(m-r)}. A union bound gives failure probability at most (ℓm)re−ϵ(m−r)(\ell m)^r e^{-\epsilon(m-r)}. Choosing m>rm>r so this is at most δ\delta yields inverse-linear accuracy dependence up to logarithms, for fixed ℓ,s,δ\ell,s,\delta. For s=0s=0, the pointwise realized-label set has size at most ℓ\ell and needs no data.

Reviewer_bNeUOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies learning when each training example provides several possible labels and the learner may also predict several labels. A prediction in this setting is successful if it includes the correct label. The paper introduces a complexity measure that characterizes when learning is possible if training and prediction lists have the same maximum size. It also constructs a class where ambiguous training labels require substantially more examples than exact labels, even when the learner may predict any fixed finite number of labels. The results are supported by mathematical proofs and explicit constructions.

Critical strengths

The paper’s main strength is that it makes a novel comparison between learning from exact labels and learning from sets of candidate labels. It constructs one hypothesis class where exact labels allow learning with relatively few examples, but ambiguous labels require substantially more, even when the learner may predict any fixed finite number of labels. It also identifies a condition that determines whether learning is possible when training and prediction lists have the same maximum size, and establishes how large prediction lists must be in the worst case under a weaker condition. These results extend existing exact-label list-learning theory.

Critical weaknesses

The writing is quite obscure and assumes strong familiarity with a very specific literature. For example, the introduction invokes DS dimensions without explaining what they are, uses “width” without connecting this concept to list size,"reference hypothesis" which aren't defined either..., and presents several detailed bounds before explaining their significance or comparison with prior results or familiarising the reader with the problem . Section 2 then defines some of this ideas, but introduces many more concepts with little intuition connecting them to the learning problem. Therefore is difficult to understand or asses the importance of the work.

The broader significance is insufficiently explained. The paper establishes theoretical separations, but does not clearly show how their new complexity measure improves our understanding of familiar hypothesis classes. Developed examples would help distinguish a consequential extension of existing theory from a specialized result about constructed classes.

Questions for authors

No specific clarification questions. My concerns concern the accessibility of the presentation and the significance demonstrated by the results.

1 comment

Thank you for the review. We revised Sections 1–2 to introduce the problem before the bounds, define observation and prediction widths as maximum list sizes, and explain DS dimension and reference functions before using them. Reference functions are fixed members of H used in the definition, not additional information supplied to the learner. Section 1.1 now states the three main conclusions before their formulas.

To address the significance concern, Example 2.7 gives a complete calculation for nondecreasing ternary classifiers: their deletion dimension is one, so two-label predictions suffice under arbitrary clean distractor laws when observed bags have size at most two. Unrestricted ternary classifiers are not learnable at the same widths. This demonstrates how the criterion distinguishes a familiar structured class; it does not claim a tight sample rate for thresholds.

Comments on the paper

1 comment

We thank the reviewers for their comments. We have made targeted revisions addressing presentation, comparisons with prior work, the interpretation of the results, and the specific questions.

  1. Accessibility and significance: Sections 1–2 now introduce the problem and notation before the bounds, identify widths as maximum list sizes, explain DS dimension and reference functions, and state the main conclusions before their formulas. Example 2.7 works out the deletion dimension of ordered ternary thresholds and contrasts their learnability with unrestricted ternary classifiers at the same observation and prediction widths.

  2. Prior work and techniques: Section 1.2 now compares the observations, objectives, and assumptions of the related models and distinguishes guarantees already supplied by prior work from the present results. Sections 1.1 and 3.1 identify the exact-label PAC ingredients, explain why hidden labels prevent direct use of their encoders or target-risk validation, and describe the additional completion, observable-update, and fractional-coverage steps.

  3. Separation and prediction width: The abstract now compares exact and ambiguous training on the same class with the same allowed prediction width. We distinguish accuracy-exponent matching at fixed widths from the unresolved dependence on growing prediction width. Beside the existing block-size calculation, we explain the current proof's limitation. We retain the lower bound's parameter restriction and separately identify the large-width guarantee of Theorem 3.2.

  4. Specific questions: Definition 2.1 and Remark 2.3 distinguish hidden-label coverage from fresh-bag intersection. Our response to Reviewer 2 supplies a compression argument showing that finite list-DS dimension suffices for the latter objective at L=ℓL=\ell in the clean common-target model. Our response to Reviewer 4 explains how exact-label PAC results contribute to the two constructions and their sample bounds.

We also placed existing definitions and auxiliary results in appropriate formal environments to highlight them correctly, made inherited hypotheses explicit where needed, and supplied precise references and citations. The main bounds and proof arguments are unchanged. The revised main body fits the 10-page limit.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.