# Delay Complexity Dimension: Learning with Delayed and Censored Labels

arXiv: https://arxiv.org/abs/2610.18935 · HTML: https://mlsanity.com/paper/2610.18935/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 25 references that are in the map.
- First posted on arXiv 13 Oct 2026.

## Builds on (most cited first, 11 of 11)

- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Stochastic Bandit Models for Delayed Conversions](https://mlsanity.com/paper/1706.09186/) (2017)
- [Generalized Delayed Feedback Model with Post-Click Information in Recommender Systems](https://mlsanity.com/paper/2206.00407/) (2022)
- [Generalization bounds for mixing processes via delayed online-to-PAC conversions](https://mlsanity.com/paper/2406.12600/) (2024)
- [Delayed Bandits: When Do Intermediate Observations Help?](https://mlsanity.com/paper/2305.19036/) (2023)
- [Learning under Temporal Label Noise](https://mlsanity.com/paper/2402.04398/) (2024)
- [Para-active learning](https://mlsanity.com/paper/1310.8243/) (2013)
- [PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting](https://mlsanity.com/paper/2605.25678/) (2026)
- [Generalization Error Bounds for Learning under Censored Feedback](https://mlsanity.com/paper/2404.09247/) (2024)
- [A Systematic Literature Review on Multi-label Data Stream Classification](https://mlsanity.com/paper/2508.17455/) (2025)

## Abstract (arXiv)

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 Omega(DCD/varepsilon2) 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.