# Generalization Error Bounds for Learning under Censored Feedback

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 60 references that are in the map.
- First posted on arXiv 14 Apr 2024.

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

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Retiring Adult: New Datasets for Fair Machine Learning](https://mlsanity.com/paper/2108.04884/) (2021)
- [Algorithmic decision making and the cost of fairness](https://mlsanity.com/paper/1701.08230/) (2017)
- [Runaway Feedback Loops in Predictive Policing](https://mlsanity.com/paper/1706.09847/) (2017)
- [Accurate Inference for Adaptive Linear Models](https://mlsanity.com/paper/1712.06695/) (2017)
- [Why Adaptively Collected Data Have Negative Bias and How to Correct for It](https://mlsanity.com/paper/1708.01977/) (2017)
- [Equal Opportunity in Online Classification with Partial Feedback](https://mlsanity.com/paper/1902.02242/) (2019)
- [Unintended Selection: Persistent Qualification Rate Disparities and Interventions](https://mlsanity.com/paper/2111.01201/) (2021)
- [Pricing Query Complexity of Revenue Maximization](https://mlsanity.com/paper/2111.03158/) (2021)
- [Adaptive Region-Based Active Learning](https://mlsanity.com/paper/2002.07348/) (2020)
- [Partitioned Active Learning for Heterogeneous Systems](https://mlsanity.com/paper/2105.08547/) (2021)
- [Active Learning for Skewed Data Sets](https://mlsanity.com/paper/2005.11442/) (2020)
- [Adaptive Data Debiasing through Bounded Exploration](https://mlsanity.com/paper/2110.13054/) (2021)
- [Algorithmic Censoring in Dynamic Learning Systems](https://mlsanity.com/paper/2305.09035/) (2023)
- [Learning Thresholds with Latent Values and Censored Feedback](https://mlsanity.com/paper/2312.04653/) (2023)
- [A Generalization Theory based on Independent and Task-Identically Distributed Assumption](https://mlsanity.com/paper/1911.12603/) (2019)
- [Gray Learning from Non-IID Data with Out-of-distribution Samples](https://mlsanity.com/paper/2206.09375/) (2022)

## Built on by (most cited first, 1 of 1)

- [Delay Complexity Dimension: Learning with Delayed and Censored Labels](https://mlsanity.com/paper/2610.18935/) (2026)

## Abstract (arXiv)

Generalization error bounds from learning theory provide statistical guarantees on how well an algorithm will perform on previously unseen data. In this paper, we characterize the impacts of data non-IIDness due to censored feedback (a.k.a. selective labeling bias) on such bounds. Censored feedback is ubiquitous in many real-world online selection and classification tasks (e.g., hiring, lending, recommendation systems) where the true label of a data point is only revealed if a favorable decision is made (e.g., accepting a candidate, approving a loan, displaying an ad), and remains unknown otherwise. We first derive an extension of the well-known Dvoretzky-Kiefer-Wolfowitz (DKW) inequality, which characterizes the gap between empirical and theoretical data distribution CDFs learned from IID data, to problems with non-IID data due to censored feedback. We then use this CDF error bound to provide a bound on the generalization error guarantees of a classifier trained on such non-IID data. We show that existing generalization error bounds (which do not account for censored feedback) fail to correctly capture the model's generalization guarantees, verifying the need for our bounds. We further analyze the effectiveness of (pure and bounded) exploration techniques, proposed by recent literature as a way to alleviate censored feedback, on improving our error bounds. Together, our findings illustrate how a decision maker should account for the trade-off between strengthening the generalization guarantees of an algorithm and the costs incurred in data collection when future data availability is limited by censored feedback.