When Is Coarse Supervision Worth It? Cost-Aware Learning under Unknown Aggregation

Jianyu Xu; Smriti Jha; Aarti Singh; Bryan Wilder

cs.LGSep 29, 2026

When Is Coarse Supervision Worth It? Cost-Aware Learning under Unknown Aggregation

Authors: Jianyu Xu, Smriti Jha, Aarti Singh, Bryan Wilder

Organizations: University of North Carolina at Charlotte, Charlotte, NC 28223 · Carnegie Mellon University, Pittsburgh, PA 15213

Abstract

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.

Figures & tables

\widetilde{w}_{m}\in\argmin_{w\in\Delta_{K},\;w_{k}\geq\tau}\|\widetilde{u}_{m}-\widetilde{\Theta}_{m}w\|_{2}^{2},\qquad\widetilde{\lambda}_{m}=\frac{c_{\mathrm{F}}\sigma_{\mathrm{F}}^{2}}{c_{\mathrm{C}}\sigma_{\mathrm{C}}^{2}}\|\widetilde{w}_{m}\|_{2}^{2}.

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_{\star}

as unknown. Shaded bands are paired-bootstrap 95% intervals over 20 seeds. In the

20\times

regime EET-CF clearly improves on all-fine; in the

5\times

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\times$	$1.031$	$1.028$	$0.989$	$614{,}400$	none
$20\times$	$1.026$	$1.023$	$0.947$	$76{,}800$	$153{,}600$

Appendix

Table 1: Online summary at

T=2{,}457{,}600

. The coefficient columns report

TL_{T}/\Phi_{\mathrm{U}}^{\star}

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

Panel of Figure 7 — 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.

Cost-Sensitive Learning

Cost-sensitive learning accounts for unequal error, data-acquisition, and decision costs when training and evaluating models.

See all 42 papers

How many labelers do you have? A closer look at gold-standard labels
Jun 24, 2022Chen Cheng, Hilal Asi, John DuchiModel Calibration Noisy-Label Learning
Department of Statistics, Stanford University · Department of Electrical Engineering, Stanford University · Departments of Statistics and Electrical Engineering, Stanford University
Epistemic Learning from Imprecise Annotation
Sep 28, 2026Kaizheng Wang, Siu Lun ChauSoft-Label Learning Epistemic Uncertainty
Epistemic Intelligence & Computation Lab, College of Computing & Data Science, Nanyang Technological University, Singapore
Useful to Whom? The Easy-versus-Coverage Boundary Moves with the Learner
Sep 22, 2026Yangze Liu, Xiao-Long Yin, Zhongyi HanTraining Data Selection Coreset Selection
Shandong University · Nanjing University

Jun 24, 2022J/K move · Enter open · S save

How many labelers do you have? A closer look at gold-standard labels

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

Model Calibration Noisy-Label Learning Dataset Aggregation Statistical Learning Theory Supervised Learning

Open paper AskPDF arXiv

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.

Abstract

Cost-Sensitive Learning

Explore similar work

How many labelers do you have? A closer look at gold-standard labels

Epistemic Learning from Imprecise Annotation

Useful to Whom? The Easy-versus-Coverage Boundary Moves with the Learner