PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Jianyu Xu, Smriti Jha, Aarti Singh, Bryan Wilder

arXiv:2609.36704v1cs.LGstat.ML

TL;DR

When fine labels reveal a vector response but cheaper labels reveal only an aggregate with unknown weights, it is unclear how to allocate a finite annotation budget while predicting the full response. The paper characterizes the information tradeoff and develops an online estimate-and-track policy. The policy attains the optimal leading cumulative-risk coefficient with a matching lower bound, while experiments show it approaching the oracle-share benchmark and gaining over all-fine acquisition when coarse supervision is favorable.

  • Problem

    The paper asks how to divide a finite annotation budget between fine vector labels and cheaper scalar aggregates when the full response remains the target and the aggregation weights are unknown.

    Source: §1 · pp. 1–2

  • Method

    The paper characterizes the information geometry of a linear two-resolution model and uses an online estimate-and-track policy to learn the aggregation rule and track the optimal resolution mix.

    Source: §1 · p. 2

  • Results

    The online policy matches the optimal leading log T cumulative-risk coefficient with an O(1) remainder and a matching local asymptotic minimax lower bound.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Experiments show the online policy approaching the oracle-share benchmark and finite-budget gains over all-fine acquisition when coarse supervision is sufficiently favorable.

    Source: §1 · p. 3

    The analysis assumes independent fine- and coarse-query noises; correlated or shared item-level noise would lead to a different pairing problem.

    Source: §3.3 · p. 5

Abstract

from arXiv · show

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.

1 Introduction

The paper asks how to divide a finite annotation budget between detailed vector labels and cheaper scalar aggregates when the full response remains the target. It characterizes how unknown aggregation changes coarse-label information and develops an online policy with first-order guarantees.

Motivation

  • Unknown aggregation makes the coarse direction itself a nuisance to identify, so coarse supervision’s value depends on price, noise, and uncertainty about what is aggregated.The target is still the full criterion vector, while a coarse label is only a scalar projection.Source: §1 · pp. 1–2

Contributions

  • With unknown weights, changes in the fine map can be offset by changes in aggregation weights, removing exactly K −1 directions from the target that coarse data can help estimate.The remaining information separates into fine-only and shared blocks, reducing the design problem to a one-dimensional objective and a break-even boundary.Source: §1 · p. 2
  • The unknown-aggregation static frontier is governed by an effective ratio λ, with coarse labels entering the optimal design if and only if λ > dK/(d −K + 1).Above the boundary, the optimal coarse spending share and leading fractional gain have closed forms.Source: §1 · p. 2
  • An epochal estimate-and-track policy reserves a vanishing design stream to estimate the aggregation rule and target share, then uses the remaining budget to track that share.Cross-fitting keeps estimation-stream labels out of future allocation decisions.Source: §1 · pp. 2–3
  • The policy’s cumulative risk matches the optimal leading log T coefficient for exogenous static designs under unknown aggregation, with an O(1) remainder, and a matching local asymptotic minimax lower bound.The lower bound shows that learning the allocation adds no first-order penalty beyond the intrinsic nuisance price.Source: §1 · p. 3

Experiments

  • Synthetic experiments show the online policy approaching the oracle-share benchmark and a finite-budget improvement over all-fine acquisition when coarse supervision is strongly favorable.A structural comparison also illustrates the difference between known- and unknown-aggregation acquisition decisions.Source: §1 · p. 3

2 Related Works

The paper relates its problem to optimal design, multifidelity estimation, and cost-sensitive supervision. Its distinguishing focus is a cheap, lower-dimensional projection of the same vector target whose direction is unknown.

Optimal design and cost-aware partial measurement

  • Unlike prior multiresponse optimal-design and partial-measurement work, this paper gives a closed-form two-resolution cost–information frontier when the coarse observation operator is unknown.The cited related work includes Sagnol [2011] and Mareis and Drton [2026].Source: §2 · p. 3

Multifidelity estimation and adaptive design

  • Multifidelity work allocates across expensive and cheap sources and can learn cross-fidelity relationships adaptively, while this paper treats the unknown projection as a nuisance in the conditional-mean law.Related examples include Peherstorfer et al. [2016], Xu et al. [2022], and Fontaine et al. [2021].Source: §2 · p. 3

Cost-sensitive learning and supervision granularity

  • Cost-sensitive supervision work selects among annotation sources or learns from coarse labels, whereas this paper’s cheaper action is an unknown scalar projection of the same vector-valued response.The full conditional mean remains the prediction target.Source: §2 · p. 3

3 Problem Setup

The setup studies sequential choices between costly fine vector responses and cheaper scalar aggregates, with prediction risk measured on the full response. It distinguishes static reference allocations from online learning and specifies assumptions that isolate the resolution-allocation problem.

3.1 Problem Formulation

  • At each round the learner chooses fine or coarse resolution from past history, before observing the current covariate or response noise.The target is the full K-dimensional conditional response, while coarse labels reveal a scalar projection using simplex weights.Source: §3.1 · pp. 3–4
  • The budget clock counts annotation cost rather than queries, and bounded action costs can leave a bounded unused residue.The learner may use observed history to choose future resolutions but never observes an unqueried response.Source: §3.1 · p. 4

3.2 Key Quantities

  • Cumulative fine-prediction risk measures predictor quality throughout the annotation campaign, not only terminal risk.The estimator is held fixed between completed estimation queries.Source: §3.2 · p. 4
  • The reference regimes separate a known-weight static oracle, an unknown-aggregation oracle-share benchmark, and online learning of the aggregation and allocation.The oracle-share schedule is exogenous and carries no inferential information; the online setting learns sequentially.Source: §3.2 · p. 4

3.3 Assumptions

  • The analysis assumes i.i.d. covariates with zero mean and positive-definite covariance; unlimited unlabeled covariates make the covariance known.Whitening is treated as a coordinate change without loss for prediction risk.Source: §3.3 · pp. 4–5
  • Fine and coarse query noises are Gaussian, independent across items and resolutions conditional on covariates, and their positive costs and variances are known.Correlated or shared item-level noise would lead to a different pairing problem.Source: §3.3 · p. 5
  • The aggregation weights are interior to the simplex, dimensions satisfy d ≥K ≥2, and regularity conditions rule out indistinguishable aggregation directions.The sequential protocol chooses each action using history before the current covariate and noise; dimensions and regularity constants remain fixed as T grows.Source: §3.3 · p. 5
  • Choosing resolution before seeing the current covariate isolates allocation; allowing current-item leverage would add an optimal-design dimension.Source: §3.3 · p. 5

4 Static Allocation with Known Aggregation

With known aggregation, fine labels identify every response direction while coarse labels add information only along the known aggregation direction. The resulting allocation problem has a closed-form break-even rule and a bounded leading gain over all-fine acquisition.

4.1 Fine-Prediction Risk under a Static Allocation

  • The information matrix has eigenvalue α with multiplicity d(K −1) and eigenvalue α + γ∥w⋆∥2 with multiplicity d.The d(K −1) directions orthogonal to w⋆ require fine labels; the remaining d directions can use both resolutions.Source: §4.1 · pp. 5–6

4.2 Cost-Optimal Resolution Mix

  • Coarse supervision enters the optimal static design if and only if λ > K; the optimal share is the unique minimizer of the strictly convex allocation objective.The threshold means coarse labels must be sufficiently precise per unit cost along the aggregation direction to compensate for the K −1 directions that still require fine labels.Source: §4.2 · p. 6

4.3 Value of Coarse Supervision

  • The leading gain over all-fine acquisition is zero for λ ≤K and strictly positive above the boundary.A gain of 0.04 means a 4% leading reduction in prediction risk at fixed budget, equivalently annotation cost at fixed target risk; even arbitrarily cheap or precise coarse labels cannot replace fine information for the remaining K −1 directions.Source: §4.3 · p. 7

5 Unknown Aggregation and Online Adaptation

Unknown aggregation changes which directions coarse labels can identify and therefore changes the optimal fine/coarse mix. EET estimates the aggregation and tracks that mix online, attaining the optimal leading cumulative-risk coefficient.

5.1 Unknown Aggregation: Static Benchmark

  • Profiling out the unknown aggregation weights moves exactly K −1 directions from the coarse-informative block into the fine-only block.The remaining dimensions receive both fine- and coarse-label information; the unknown-aggregation gain is zero at and below its break-even boundary and rises above it.Source: §5.1 · pp. 7–8
  • Static procedures attain locally asymptotic minimax leading log T risk coefficients for both known- and unknown-aggregation experiments.The first-order pointwise risk scales as 1/b, producing the log T cumulative-risk benchmarks.Source: §5.1 · p. 8

5.2 Learning the Optimal Mix Online

  • EET uses a vanishing design stream to estimate the aggregation and target coarse share, then tracks that share while fitting the predictor with cross-fitted estimation.Estimation labels do not feed back into future allocation decisions, and no separation from the break-even boundary is required.Source: §5.2 · pp. 8–9
  • EET attains the unknown-aggregation leading cumulative-risk coefficient, and a local asymptotic minimax lower bound shows no predictable policy can improve that first-order term.The result is locally uniform; the cumulative risk is the coefficient times log T plus O(1).Source: §5.2 · pp. 8, 10

6 Numerical Experiments

The experiments illustrate the cost of unknown aggregation and test online adaptation in synthetic instances. EET-CF approaches the oracle-share benchmark and improves on all-fine most clearly in the 20× regime.

Structural effect of unknown aggregation

  • At λ = 10 and λ = 14, known-aggregation designs gain 2.87% and 4.66% over all-fine, while the unknown-aggregation optimum remains all-fine.For d = 6 and K = 5, the known-aggregation break-even point is λ = 5 and the unknown-aggregation boundary is λ = 15.Source: §6 · p. 10

Online adaptation

  • EET-CF is numerically close to the oracle-share B2-CF benchmark: their reported values are 1.031 versus 1.028 at 5× and 1.026 versus 1.023 at 20×.The online instance uses d = 20 and K = 5; the experiments use exact population fine-prediction risks under whitened covariance.Source: §6 · p. 10
  • In the 20× regime, EET-CF clearly improves on all-fine; Figure 1 reports paired-bootstrap 95% intervals over 20 seeds.Figure 1 normalizes cumulative fine-prediction risk by all-fine; values below 1 indicate improvement.Source: Figure 1 · p. 11

7 Discussion and Conclusion

The paper concludes that unknown aggregation changes the information available from coarse labels, while online allocation learning adds no first-order penalty. Its analysis is scoped to a linear-Gaussian setting with fixed aggregation and resolution chosen before covariates.

7 Discussion and Conclusion

  • The analysis is limited to a linear-Gaussian setting with a fixed aggregation rule and precovariate resolution choice.The paper identifies richer extensions for future discussion.Source: §7 · p. 11

Appendix Roadmap

  • The appendix collects the extended literature discussion, synthetic protocols and diagnostics, and proofs of the static and online results.The notation roadmap distinguishes known- and unknown-aggregation benchmarks and the online learned-allocation setting.Source: Appendix Roadmap · p. 14

A Extended Discussion

  • The extended discussion focuses on literature and limitations that interact directly with the two-resolution information structure.It expands the comparison and limitations discussed in the main text.Source: A Extended Discussion · p. 14

A.1 Extended Related Work

  • With known aggregation, the fine and coarse channels form two structured observation types in multiresponse optimal design; unknown aggregation makes the coarse observation operator a nuisance parameter.The paper distinguishes its full multivariate regression-map target and scalar-projection observation from related partial-measurement settings.Source: §A.1 · pp. 14–15
  • Unlike related resource-allocation work, uncertainty about w⋆ changes the efficient information for the target itself, removing K −1 coarse-informative directions and changing the break-even boundary.Related work also considers supervision granularity and inference from coarse labels, but with different observation structures.Source: §A.1 · p. 15

A.2 Limitations and Extensions

The section identifies boundaries of the fixed-dimensional, one-fine/one-coarse analysis and reports synthetic checks of its predictions. The experiments are quantitative tests of the linear theory, not evidence that the canonical model describes a real annotation system.

A.2 Limitations and Extensions

  • The canonical model chooses resolution before observing the covariate; allowing joint item and resolution selection instead yields a matrix-valued optimal-design problem.That setting requires choosing both where information is most valuable and which resolution to purchase.Source: §A.2 · pp. 15–16
  • Extensions to paired resolutions may require modeling shared noise, while multiple coarse channels or nonlinear aggregation can replace the single informative direction and scalar allocation share.Near the asymptotic break-even boundary, estimation and adaptation costs can delay finite-budget benefits.Source: §A.2 · p. 16
  • With locally unconstrained aggregation weights, the efficient-information and scalar-allocation arguments carry over with a larger nuisance price, but an intercept claim requires a separate derivation.The displayed alternative threshold uses A = d(K −1) + K and D = d −K.Source: §A.2 · p. 16
  • The theory fixes d and K and treats covariate covariance and noise variances as known, while its guarantee concerns ex-ante expected cumulative risk rather than time-uniform or high-probability performance.The text leaves a complete theorem for estimated variances to future work and notes that stronger uniform guarantees may add logarithmic factors.Source: §A.2 · pp. 16–17

B Extended Numerical Experiments

  • The synthetic protocol tests quantitative consequences of the linear theory, but does not establish that the canonical model accurately describes a real annotation system.Source: B Extended Numerical Experiments · p. 17

B.1 Experimental Setup and Reproducibility

  • The online runs use 20 seeds through horizons of 614400, extending to 2457600 in the two mixed regimes, with pointwise bootstrap intervals for risk ratios.Static experiments use 200 seeds, exact population fine-prediction risk, and paired delta-method intervals for gains.Source: §B.1 · pp. 17–18

B.2 Static Convergence Check

  • At B = 76800, empirical gains in the 2×, 5×, and 20× regimes are 1.226%, 4.848%, and 9.617%, versus theoretical values 1.548%, 5.271%, and 10.012%.The last-step changes in coefficient excess are smaller than paired standard errors, so the apparent flattening or increase at the largest budgets is unresolved statistically.Source: §B.2 · p. 18, Figure 2 · p. 18

B.3 Known versus Unknown Aggregation

  • At B = 76800, known-aggregation gains are 2.874% (λ = 10) and 4.664% (λ = 14), while unknown-aggregation B2 is all-fine for 5 < λ ≤ 15.The figure compares theory curves and empirical gains at two budgets; the shaded band marks the gap between known- and unknown-aggregation thresholds.Source: §B.3 · p. 19, Figure 3 · p. 19

B.4 Online Allocation Learning and Finite-Budget Value

The online allocation tracks the theoretical share, while finite-horizon diagnostics distinguish adaptation performance from lower-order overhead. The section also illustrates how static gain varies across aggregation weights.

B.4 Online Allocation Learning and Finite-Budget Value

  • The design-stream plug-in target and realized estimation-stream coarse-budget share track the theoretical optimal share, without estimation labels feeding back into allocation.Source: §B.4 · p. 19, Figure 4 · p. 20
  • The 20× regime uses a smaller coarse spending share than 5× because more informative coarse dollars require less spending to complement fine-only directions.Source: §B.4 · p. 20
  • At the largest horizon, EET-CF is numerically close to B2 in instantaneous first-order coefficient, despite cumulative EET-minus-B2 gaps of 80.42 (95% CI [59.94, 100.90]) and 93.26 ([79.38, 107.15]) in the 5× and 20× regimes.B2 is an oracle-share reference that EET is intended to approach, not beat.Source: §B.4 · p. 20

B.5 First-Order Remainder Diagnostic

  • After subtracting the discrete harmonic first-order benchmark, late residual trajectories are consistent with flattening but too noisy to establish a bounded plateau.The 20-path figure is a finite-horizon diagnostic, not empirical proof of the O(1) remainder.Source: §B.5 · p. 20, Figure 5 · p. 21

B.6 Below-Threshold Finite-Budget Diagnostic

  • At T = 614400, forcing post-initialization target shares to zero does not remove the roughly 4% cumulative overhead; accounting diagnostics are not a causal decomposition.At 0.75×, 18 of 20 normal and forced-zero post-initialization acquisition paths are identical.Source: §B.6 · p. 21

B.7 Distributional Illustration of Annotation Gain

  • At ρ = 20, approximately half of sampled weights have positive gain but mean gain is only 0.15%; mean gain rises to 1.73%, 5.39%, and 7.97% at ρ = 40, 100, and 200.Source: §B.7 · p. 22

C Proof Details

  • The proof details use whitened coordinates and constants uniform over the regular parameter class, with fixed dimensions and model bounds.Source: C Proof Details · p. 22

C.1 Proof of Proposition 1

The proof decomposes information across fine-only and fine-plus-coarse directions, then derives the known-aggregation allocation boundary. It establishes first-order attainment and a local asymptotic minimax lower bound.

C.1 Proof of Proposition 1

  • The H0 subspace has dimension d(K −1) and receives only fine information, while the complementary d-dimensional subspace has information eigenvalue α + γ∥w⋆∥2 2.Source: §C.1 · p. 22
  • The projected weighted estimator attains the inverse-information trace to first order, which is also the local asymptotic minimax lower bound.Source: §C.1 · p. 23

C.2 Proof of Theorem 2

  • Strict convexity makes all-fine uniquely optimal for λ ≤ K, while λ > K yields an interior coarse share.Source: §C.2 · p. 24

C.3 Proof of Theorem 3

These proofs establish the static unknown-aggregation risk and allocation results, derive the information geometry under nuisance weights, and connect static risks to cumulative benchmarks.

C.3 Proof of Theorem 3

  • The unknown-weight local asymptotic minimax lower bound matches the leading covariance attained by the projected two-fold one-step construction under an exogenous static schedule.Source: §C.3 · p. 24
  • The proof verifies the unknown-aggregation threshold and optimizer, and bounds the gain ceiling by (d −K + 1)/(dK).Source: §C.3 · p. 25

C.4 Proof of Lemma 4

  • After profiling nuisance-weight perturbations, K −1 directions in S⋆ receive only fine information, while d −K +1 remaining directions receive fine-plus-coarse information.Source: §C.4 · p. 25

C.5 Proof of Corollary 5

  • The static benchmark risks sum to cumulative log T bounds, with the local minimax interpretations following from the known- and unknown-weight inverse-information arguments.Source: §C.5 · p. 26

C.6 Proof of Theorem 6

The proof shows that the online policy attains the optimal leading cumulative-risk coefficient with O(1) excess, while the allocation lemma controls pilot estimation and tracking error.

C.6 Proof of Theorem 6

  • Summing the per-budget bounds yields cumulative risk Φ⋆U log T + O(1), and the lower bound establishes the matching leading coefficient.Source: §C.6 · p. 27
  • The bound holds locally uniformly over sufficiently small parameter neighborhoods because the optimal coefficient Φ⋆U varies continuously on the regular class.Source: §C.6 · p. 27

C.7 Proof of Lemma 7

  • Epochal pilots use earlier design blocks, with both fine and coarse design counts growing as Θ(2^m/m^2), supporting estimation of the aggregation rule and target share.Source: §C.7 · p. 28
  • The signed-imbalance tracker keeps coarse spending near its epoch target, and bounded tracking and endpoint residues contribute only lower-order cumulative excess.Source: §C.7 · p. 29

C.8 Proof of Lemma 8

The proof controls a cross-fitted one-step estimator by separating its efficient score term from pilot and guard remainders. It then establishes a matching risk lower bound for predictable resolution policies using local Bayesian information bounds.

C.8 Proof of Lemma 8

  • Opposite-fold guarded pilots feed a one-step score update whose error is decomposed into five remainder classes.The classes cover quadratic mean terms, perturbed score directions, empirical-Jacobian fluctuation, pilot inverse-information substitution, and rare guard failure.Source: §C.8 · pp. 30–31
  • The estimator’s remainder bounds hold even when the coarse count stays bounded, because nuisance errors are downweighted by coarse information.A bounded coarse count may leave the nuisance pilot inconsistent, but the factors γr/bE or √γr/bE suffice for the stated bound.Source: §C.8 · pp. 30, 32
  • Averaging the two independent fold influence functions recovers the full-sample efficient trace for the leading prediction risk.Each fold has approximately half the full counts, and the averaging factor restores the full-sample trace.Source: §C.8 · p. 32

C.9 Proof of Lemma 9

  • The lower-bound proof uses a smooth prior varying both β and v, so the Bayesian bound retains the nuisance price of unknown aggregation.Fixing v would remove that price; the proof applies the multivariate van Trees inequality on a regular neighborhood.Source: §C.9 · p. 32
  • For predictable policies, stopped-history information is the expected sum of queried-label information, enabling a policy-uniform local lower bound.The policy kernels and cost-based stopping rule are parameter-free, and queried-observation scores are martingale differences.Source: §C.9 · pp. 33–34
Loading 2609.36704v1…