arXiv preprint ·
Delay Complexity Dimension: Learning with Delayed and Censored Labels
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $Ω(\mathrm{DCD}/\varepsilon^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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning (Statistics)
textGrain watermarking is harder to detect: can sum-tests still do it optimally?
Digital Self-Interference Cancellation for In-Band Full-Duplex Systems Based on Transformer Neural Operators
Rarity Determines Minimax Rates of Semantic Entropy From Weak Pairwise Judgments With a Known Channel
High-Probability Regret Bounds for Feel-Good Thompson Sampling
Optimal Support Size Testing
Get the few papers worth your time in Machine Learning (Statistics) every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.