- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This article proposes the DCCP method for online multiclass prediction with 1-bit diluted feedback. The main idea is to combine randomized prediction sets with an augmented Horvitz–Thompson estimator to recover unbiased class-specific signals for model training and threshold calibration. Theoretical analyses of class-specific coverage are provided to guarantee validity of the proposed method. My major concern is that the current theory does not establish that the base model can learn effectively from diluted feedback. There are several other issues that remain to be resolved: (1) the motivating examples are insufficient and do not align with the proposed method; (2) the technical advance over prior work has not been convincingly illustrated or discussed; (3) the justification for the randomization and estimation choices require clarification.
Critical strengths
The basic idea is reasonable: randomization makes it possible to recover an identifiable class-specific covariance signal from set-level feedback. The strategy of substituting unbiased pseudo-labels into online threshold calibration is useful.
The theoretical analysis appears broadly reasonable.
Critical weaknesses
-
The problem setting is narrow, and the motivating scenarios have not sufficiently established its practical importance. In customer support, resolving an issue is not equivalent to the true intent being included in the output set: resolution also depends on response quality, user behavior, and the possible presence of multiple intents. Similarly, in medicine, treatment may fail despite a correct diagnosis.
-
The paper does not show that the base model learns effectively from such feedback. Size regret is a reasonable metric. However, Theorem 2 does not establish that the error bound can be controlled; it is unclear whether the model can learn a good score from diluted feedback.
-
The relationship to prior work is insufficiently discussed. In particular, the connections to partial-label learning, weak supervision, noisy or corrupted feedback, and partial monitoring are not systematically examined. A clearer discussion is needed to clarify the paper's technical advance over existing work.
Questions for authors
Q1. Could the authors provide more insight underlying the unbiased estimator? The basic principle appears to apply to a broad class of score functions. Could the authors characterize this broader class and explain how it informs the appropriateness of the proposed design? In particular, Equations (2) and (3) are not supported by a principled derivation from an experimental-design perspective or by an optimality analysis. What information or utility criterion motivates the inclusion rule in Equation (2), and is the augmentation in Equation (3) variance-optimal? Without such a characterization, these choices appear ad hoc.
Q2. Could the authors provide more explanations on the motivating examples? The formulation concerns not only prediction set size but also the cost of actual interventions. In customer support, the system needs to randomly include some low-probability intents in its responses. In medicine, it needs to randomly include some low-scoring diagnoses in the treatment set. The paper measures this cost only through set size, without discussing incorrect actions, user experience, or clinical losses. How should these intervention costs be accounted for?
Q3. Is size regret alone sufficient to assess the value of diluted feedback, and does using such feedback improve learning efficiency compared with using no feedback? In particular, does it improve accuracy relative to a completely frozen initial model? Does jointly updating the model and thresholds produce smaller prediction sets than using feedback only to adjust the thresholds while keeping the score function fixed?
4 comments
Response to Reviewer BVPE – Part II
Question 1 — “more insight underlying the unbiased estimator”.
Thank you for asking us to clarify the generality and rationale of these choices.
“broad class of score functions” (Q1).
Although our experiments use RAPS (Angelopoulos et al., 2021; Appendix B.1), unbiasedness holds for any scores fixed before the inclusion draws, provided the inclusion probabilities are known and strictly between zero and one, with independent draws across classes (Proposition 2(i)). Score choice can still affect finite-sample coverage and prediction-set size. Inspired by your question, exploring score choices that improve these properties under diluted feedback could be a direction for future work.
“What information or utility criterion motivates the inclusion rule” (Q1).
We use the sigmoid in Equation (2) to randomize the conformal score–threshold rule while preserving its ordering: increasing a class's score raises its inclusion probability, and increasing its threshold lowers it. This monotone dependence on the threshold supports the convex calibration objective in Appendix A.2 (Equation (9)). The parameter controls how sharply inclusion responds to the score–threshold margin, as explained below Equation (2) and examined in §5.2 (Figure 2) through its effects on coverage and set size. We do not claim that the sigmoid optimizes an information or utility criterion.
“is the augmentation in Equation (3) variance-optimal?” (Q1).
Our augmentation uses a model-based control variate to reduce variance (Bang & Robins, 2005; Dudík et al., 2011), without claiming variance optimality. Appendix A.1 derives as an estimate of the membership bit’s conditional mean; subtracting it preserves unbiasedness even when the estimate is inaccurate (Proposition 2(i)). Table 3 (Appendix B.2) demonstrates variance reduction, and Table 5 (Appendix B.3) shows CIFAR-100 accuracy of 57.0% with augmentation versus 25.0% without it.
Question 3 — “accuracy relative to a completely frozen initial model … smaller prediction sets”.
Thank you for suggesting this comparison. To assess learning beyond set size, we have added an experiment with the base model frozen at initialization and only the thresholds updated (see Table 6 in Appendix B.3). On the CIFAR-10 training stream, joint training raises accumulative top-1 accuracy from 10.7% to 78.0% and reduces set size from 8.91 to 2.56 labels while both arms maintain approximately 90% marginal coverage. Model updating therefore improves accuracy and reduces set size beyond threshold calibration alone. The original Table 5 (Appendix B.3) also shows accumulative top-1 accuracy increasing as model training proceeds on all three datasets.
References
- Batra, G., and Manwani, N. (2021). Multiclass Classification Using Dilute Bandit Feedback.
- Heuillet, M., Ahmad, O., and Durand, A. (2024). Randomized Confidence Bounds for Stochastic Partial Monitoring. ICML.
- Agrawal, V., Pukdee, R., Balcan, M.-F., and Ravikumar, P. (2025). Learning from Weak Labelers as Constraints. ICLR.
- Angelopoulos, A. N., Bates, S., Jordan, M. I., and Malik, J. (2021). Uncertainty Sets for Image Classifiers Using Conformal Prediction. ICLR.
- Bang, H., and Robins, J. M. (2005). Doubly Robust Estimation in Missing Data and Causal Inference Models. Biometrics.
- Dudík, M., Langford, J., and Li, L. (2011). Doubly Robust Policy Evaluation and Learning. ICML.
Dear reviewer,
We sincerely express our gratitude for your dedicated time in reviewing our paper, and providing constructive suggestions and questions to help improve its quality. We also thank you for the opportunity to clarify our work. As the deadline approaches, could you please let us know if our earlier response is unclear and if we may have another opportunity to clarify it? We really appreciate your time and help.
Warm regards,
Authors
Thank you very much for your clarifications, which have made the results more convincing. After considering all your responses, I have decided to maintain my original score.
Response to Reviewer BVPE – Part I
We appreciate the reviewer's questions for clarification. Please find our itemized response below.
Weakness 1 and Question 2 — “motivating scenarios … cost of actual interventions”.
The examples motivate §3’s original model: each instance has one true label, and feedback reports whether the prediction set contains it.
That said, you are absolutely right that actual resolution or treatment outcomes also depend on other factors. Following your suggestion, we have clarified in §1’s opening paragraph that these examples motivate an abstraction and that interpreting the medical outcome as membership feedback is a modeling assumption.
Set size is one efficiency criterion: acting on a larger set of candidate labels can require more resources in subsequent interventions. Every included label contributes to this measure, including low-probability labels added by randomization. Your suggestion points to a useful direction for future work: explicitly optimizing a customized objective that incorporates set size and application-specific intervention costs.
Weakness 2 — “base model learns effectively … error bound can be controlled”.
Proposition 2(i) establishes that Δ is unbiased for the one-hot label. With the log-probabilities fixed before the inclusion draws, the weighted loss in Equation (4) therefore equals full-label cross-entropy in expectation. Thus, the bit provides a model-training signal as well as a calibration signal. The frozen-model comparison under Question 3 tests whether updating the model improves its predictions.
The theorem quantifies the effects of score discrepancy and threshold tracking. The original discussion following Theorem 2 in §4.4 explains this dependence; the paragraph after Proposition 3 in Appendix C qualifies the benchmark comparison. Controlling the discrepancy through model learning would require additional optimization and generalization analysis.
We agree that this scope should be more prominent and have brought the benchmark qualification into the discussion following Theorem 2 in §4.4.
Weakness 3 — “relationship to prior work is insufficiently discussed”.
Batra & Manwani (2021) recover an unbiased learning signal from randomized fixed-size sets, but their method does not target a prescribed coverage level. DCCP must additionally calibrate each class’s coverage while learning from the prediction set’s own feedback. This calibration changes the sampling distribution, so the learning signal must remain valid throughout those changes. Our inclusion rule and unbiased estimator jointly support model training and class-specific threshold updates. We have clarified this distinction in §4.1’s Consequence paragraph.
To address your suggestion, we have expanded the final two paragraphs of §2.2 to discuss set-valued feedback, partial monitoring and weak supervision (e.g., Heuillet et al., 2024; Agrawal et al., 2025), alongside the existing corrupted-feedback discussion. We would be happy to include other relevant work if you have specific papers in mind.