Delay Complexity Dimension: Learning with Delayed and Censored Labels
Abstract
We study PAC learning of binary classifiers when labels arrive after random delays and are censored beyond an observation window W. How many samples does this observation model require? We propose a distribution-dependent answer, the Delay Complexity Dimension (DCD). The DCD combines the VC dimension with the exact label-information rate of the observation channel. Every learner needs Ω(DCD/ε2) samples. An oracle pseudo-label ERM matches this rate on the instance family of the lower bound, up to constants and logarithmic factors. On that family the DCD is within a constant factor of the classical censored-ERM complexity, and whether the DCD rate is achievable where the two separate remains open. The theory also yields a quantization scheme under which delay information lowers the residual label variance, an expedition policy with a (1−1/e) guarantee for its version-space objective, and a phenomenon with no analogue in the no-delay setting. Under a fixed collection horizon, a moderate window can strictly beat immediate labels. Experiments on synthetic data and the Criteo conversion logs support these predictions. A budget-matched test of a companion labeler-diversity prediction is reported as a negative result.
Related
- Subspace Learning with Interval-Censored Likelihoods for Dequantizing Percept PC LFP Snapshots
- On the Complexity of Finding Stationary Points of p-th Order Hölder Smooth Functions in One Dimension
- A priori regularity of the reverse heat flow and dimension-dependent complexity of higher-order diffusion samplers
- Predicting Backup Non-Compliance Using KPI-Derived Labels and Machine Learning: A Proof-of-Concept Study
- Bounded Adjustment with Reliability-Guided Embedding for Imbalanced Learning with Noisy Labels
BibTeX
@misc{gaikwad2026delay,
title = {{Delay Complexity Dimension: Learning with Delayed and Censored Labels}},
author = {Madhava Gaikwad},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18935},
eprint = {2610.18935},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18935},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Delay Complexity Dimension: Learning with Delayed and Censored Labels
AU - Madhava Gaikwad
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.18935
UR - https://arxiv.org/abs/2610.18935
AB - We study PAC learning of binary classifiers when labels arrive after random delays and are censored beyond an observation window W. How many samples does this observation model require? We propose a distribution-dependent answer, the Delay Complexity Dimension (DCD). The DCD combines the VC dimension with the exact label-information rate of the observation channel. Every learner needs Ω(DCD/ε^2) samples. An oracle pseudo-label ERM matches this rate on the instance family of the lower bound, up to constants and logarithmic factors. On that family the DCD is within a constant factor of the classical censored-ERM complexity, and whether the DCD rate is achievable where the two separate remains open. The theory also yields a quantization scheme under which delay information lowers the residual label variance, an expedition policy with a (1−1/e) guarantee for its version-space objective, and a phenomenon with no analogue in the no-delay setting. Under a fixed collection horizon, a moderate window can strictly beat immediate labels. Experiments on synthetic data and the Criteo conversion logs support these predictions. A budget-matched test of a companion labeler-diversity prediction is reported as a negative result.
ER -