arXiv：cs.LG· Madhava Gaikwad·· 2 小时前
延迟与截断标签下的学习：延迟复杂度维度（DCD）理论
Delay Complexity Dimension: Learning with Delayed and Censored Labels
AI 导读
研究标签经随机延迟到达、并在观察窗口 W 之后被截断时二分类器的 PAC 学习，提出分布相关的延迟复杂度维度（DCD），将 VC 维度与观察信道的标签信息率结合。
正文
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 $\Omega(\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.
| Comments: | accepted to 2026 13th International Conference on Data Science and Advanced Analytics (IEEE DSAA 2026) |
| Subjects: | Machine Learning (stat.ML); Information Theory (cs.IT); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.18935 [stat.ML] |
| (or arXiv:2610.18935v1 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2610.18935 arXiv-issued DOI via DataCite |
Submission history
From: Madhava Gaikwad [view email]
[v1]
Tue, 13 Oct 2026 11:42:10 UTC (82 KB)
来源：arXiv：cs.LG · arxiv.org