- 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.
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.