Modern learning systems often acquire supervision at multiple resolutions, trading annotation cost against information content. We study cost-aware two-resolution learning, where expensive fine labels reveal a vector response and cheaper coarse labels reveal a scalar aggregate formed with unknown weights, while the target remains the full response. The challenge is that unknown aggregation changes which directions coarse data can identify, so the value of coarse supervision depends jointly on cost, noise, and identification. We characterize this information geometry and develop an estimate-and-track policy that learns the aggregation rule and tracks the optimal resolution mix. We derive a closed-form break-even condition for coarse supervision and prove that the online policy attains the optimal leading cumulative-risk coefficient, with a matching local asymptotic minimax lower bound. Synthetic experiments support the predicted all-fine/mixed transition, show the online learner approaching the oracle-share benchmark, and demonstrate a finite-budget gain over all-fine acquisition when coarse supervision is sufficiently favorable. Our results provide a principled way to balance information and annotation cost across supervision resolutions.
Algorithm 1 Epochal Estimate-and-Track with Cross-Fitted Estimation (EET)
Figure 1: Finite-budget value of online adaptation. Cumulative fine-prediction risk is normalized by all-fine, so values below 1 indicate an improvement. EET-CF is EET with the cross-fitted estimator in Algorithm 1 ; B2-CF uses the same estimator with the oracle unknown-aggregation static share and still treats w⋆ as unknown. Shaded bands are paired-bootstrap 95% intervals over 20 seeds. In the 20× regime EET-CF clearly improves on all-fine; in the 5× regime the mean improvement appears later and remains smaller.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 2: Static convergence in the canonical d=20,K=5 instance. Left: ratio-of-means annotation gain with paired 95% intervals and exact theory references. Right: first-order coefficient excess with descriptive 95% intervals. All points use the same 200 paired seeds.
Figure 3: Known versus unknown aggregation, d=6 , K=5 . Theory curves and empirical gains are shown at two budgets. The shaded region lies between the known-aggregation threshold 5 and the unknown-aggregation threshold 15 . Error bars are 95% intervals over 200 seeds.
Figure 4: Allocation learning. The design-stream plug-in target and the realized estimation-stream coarse-budget share track the theoretical optimal share. Estimation labels never feed back into the allocation rule.
Regime
Final EET coeff.
Final B2 coeff.
EET/all-fine
Mean crossover
95% crossover
5×
1.031
1.028
0.989
614,400
none
20×
1.026
1.023
0.947
76,800
153,600
Appendix
Table 1: Online summary at T=2,457,600 . The coefficient columns report TLT/ΦU⋆ . “Mean crossover” is the first tested horizon at which mean cumulative EET risk is below all-fine; “95% crossover” additionally requires the paired pointwise 95% interval for EET minus all-fine to be entirely below zero.
Figure 5: First-order remainder diagnostic. Cumulative risk after subtracting the exact discrete harmonic first-order benchmark. Bands are descriptive pointwise 95% intervals over the 20 saved paths. The late trajectories are consistent with a bounded lower-order term but remain too noisy to establish a plateau.
Figure 6: Below-threshold finite-budget diagnostic. Cumulative risk is normalized by all-fine. Forced-zero acquisition preserves design spending but removes positive post-initialization target shares. Its failure to reduce the gap indicates that erroneous positive coarse targets are not the main source of the remaining transient overhead. Bands are paired-bootstrap 95% intervals.
Figure 7: Theorem-magnitude illustration under random simplex weights. Positive gain can become common before its magnitude becomes substantial. The variation across sampled weights is heterogeneity under the illustrative Dirichlet environment, not estimation uncertainty.
The construction of most supervised learning datasets revolves around collecting multiple labels for each instance, then aggregating the labels to form a type of "true" label. We question the wisdom of this pipeline by developing a (stylized) theoretical model of this process and analyzing its statistical consequences, showing how access to non-aggregated label information can make training well-calibrated models more feasible than it is with cleaned labels. The entire story, however, is subtle, and the contrasts between aggregated and fuller label information depend on the particulars of the problem, where estimators that use aggregated information exhibit robust but slower rates of convergence, while estimators that can effectively leverage all labels converge more quickly if they have fidelity to (or can learn) the true labeling process. The theory makes several predictions for real-world datasets, including when non-aggregate labels should improve learning performance, which we test to corroborate the validity of our predictions.
Chen Cheng, Hilal Asi, John Duchi
Department of Statistics, Stanford University · Department of Electrical Engineering, Stanford University · Departments of Statistics and Electrical Engineering, Stanford University
Imprecise annotations may support several plausible labelling distributions, yet learning methods often resolve this ambiguity into a single predictive distribution. This can obscure what the annotation evidence leaves unresolved. We introduce epistemic learning from credal supervision, a framework that uses convex sets of plausible labelling distributions, called credal sets, as supervision and learns sets of predictive distributions. We instantiate the framework with the pessimistic--optimistic credal classifier (POCC), which combines a shared backbone with two classification heads trained to minimise worst-case and best-case losses over the supervision sets. Their outputs define a predictive credal set whose spread provides an uncertainty score. We also show how credal labels can be obtained through a simple relaxation of existing probabilistic labels, reducing commitment to their precise probability assignments. This construction admits closed-form inner optimisation under cross-entropy loss, enabling efficient training. Assuming the supervision sets contain the true conditional label distributions, and other regularity assumptions, we establish a finite-sample generalisation bound for the averaged predictor with an explicit penalty for supervision imprecision. We evaluate POCC using human annotator disagreement and teacher predictions, alongside label smoothing as a controlled proxy for annotation imprecision. Across these settings, POCC achieves a favourable balance of predictive accuracy, calibration, and uncertainty-based selective classification versus competitive baselines.
Kaizheng Wang, Siu Lun Chau
Epistemic Intelligence & Computation Lab, College of Computing & Data Science, Nanyang Technological University, Singapore
Is the same data equally useful to every learner? The question is whether the value of a training sample belongs to the sample or arises in its interaction with the learner. We test it with a selection experiment. Under a per-class budget, two kinds of samples compete for the slots: easy samples, which a short training run learns first, and coverage samples, which spread over the class in feature space. Easy samples win at small budgets and coverage samples at large ones, and the budget at which the winner flips, the crossover m0, can be measured. We ask whether m0 is set by the data or by the learner. To separate the two, we freeze the selected subsets and change only the learner that trains on them. On low-resolution ImageNet-100, doubling the width of a ResNet-18 moves the crossover from 57 to 85 samples per class on the same subsets. Enlarging the input grid from 32 to 64 pixels at fixed image information moves it from 85 to 57, and a single stride change reproduces or removes this shift. The grid shift shrinks as width grows. Under the native ImageNet-1k protocol, a 4x range of width moves the boundary by at most a few samples per class. On a Vision Transformer, coverage wins at every measured budget, even with easy subsets that work on the convolutional learner. The budget at which one kind of sample stops being the more useful kind therefore belongs to the learner, and the preferred regime of a selection strategy has to be read against the learner that will use the data.