Generalization Error Bounds for Learning under Censored Feedback

• URL: http://arxiv.org/abs/2404.09247v2
• Date: Mon, 29 Jul 2024 13:32:39 GMT
• Title: Generalization Error Bounds for Learning under Censored Feedback
• Authors: Yifan Yang, Ali Payani, Parinaz Naghizadeh,
• Abstract summary: Generalization error bounds from learning theory provide statistical guarantees on how well an algorithm will perform on previously unseen data. We characterize the impacts of data non-IIDness due to censored feedback on such bounds. We show that existing generalization error bounds fail to correctly capture the model's generalization guarantees.
• Score: 15.367801388932145
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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. We first derive an extension of the well-known Dvoretzky-Kiefer-Wolfowitz (DKW) inequality, which characterizes the gap between empirical and theoretical CDFs given 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.

Related papers

• The Data-Driven Censored Newsvendor Problem [0.552480439325792]
  We study a censored variant of the data-driven newsvendor problem, where the decision-maker must select an ordering quantity that minimizes expected overage and underage costs. Our goal is to understand how the degree of historical demand censoring affects the performance of any learning algorithm for this problem. We propose a natural robust algorithm that adapts to the historical level of demand censoring.
  arXiv  Detail & Related papers  (2024-12-02T17:58:54Z)
• Pseudo-Probability Unlearning: Towards Efficient and Privacy-Preserving Machine Unlearning [59.29849532966454]
  We propose PseudoProbability Unlearning (PPU), a novel method that enables models to forget data to adhere to privacy-preserving manner. Our method achieves over 20% improvements in forgetting error compared to the state-of-the-art.
  arXiv  Detail & Related papers  (2024-11-04T21:27:06Z)
• Enhancing Fairness in Unsupervised Graph Anomaly Detection through Disentanglement [33.565252991113766]
  Graph anomaly detection (GAD) is increasingly crucial in various applications, ranging from financial fraud detection to fake news detection. Current GAD methods largely overlook the fairness problem, which might result in discriminatory decisions skewed toward certain demographic groups. We devise a novel DisEntangle-based FairnEss-aware aNomaly Detection framework on the attributed graph, named DEFEND. Our empirical evaluations on real-world datasets reveal that DEFEND performs effectively in GAD and significantly enhances fairness compared to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2024-06-03T04:48:45Z)
• VALID: a Validated Algorithm for Learning in Decentralized Networks with Possible Adversarial Presence [13.612214163974459]
  We introduce the paradigm of validated decentralized learning for undirected networks with heterogeneous data. VALID protocol is the first to achieve a validated learning guarantee. Remarkably, VALID retains optimal performance metrics in adversary-free environments.
  arXiv  Detail & Related papers  (2024-05-12T15:55:43Z)
• Fairness Without Harm: An Influence-Guided Active Sampling Approach [32.173195437797766]
  We aim to train models that mitigate group fairness disparity without causing harm to model accuracy. The current data acquisition methods, such as fair active learning approaches, typically require annotating sensitive attributes. We propose a tractable active data sampling algorithm that does not rely on training group annotations.
  arXiv  Detail & Related papers  (2024-02-20T07:57:38Z)
• Binary Classification with Confidence Difference [100.08818204756093]
  This paper delves into a novel weakly supervised binary classification problem called confidence-difference (ConfDiff) classification. We propose a risk-consistent approach to tackle this problem and show that the estimation error bound the optimal convergence rate. We also introduce a risk correction approach to mitigate overfitting problems, whose consistency and convergence rate are also proven.
  arXiv  Detail & Related papers  (2023-10-09T11:44:50Z)
• Correcting Underrepresentation and Intersectional Bias for Classification [49.1574468325115]
  We consider the problem of learning from data corrupted by underrepresentation bias. We show that with a small amount of unbiased data, we can efficiently estimate the group-wise drop-out rates. We show that our algorithm permits efficient learning for model classes of finite VC dimension.
  arXiv  Detail & Related papers  (2023-06-19T18:25:44Z)
• A Generalized Unbiased Risk Estimator for Learning with Augmented Classes [70.20752731393938]
  Given unlabeled data, an unbiased risk estimator (URE) can be derived, which can be minimized for LAC with theoretical guarantees. We propose a generalized URE that can be equipped with arbitrary loss functions while maintaining the theoretical guarantees.
  arXiv  Detail & Related papers  (2023-06-12T06:52:04Z)
• An Adaptive Method for Weak Supervision with Drifting Data [11.035811912078216]
  We introduce an adaptive method with formal quality guarantees for weak supervision in a non-stationary setting. We focus on the non-stationary case, where the accuracy of the weak supervision sources can drift over time. Our algorithm does not require any assumptions on the magnitude of the drift, and it adapts based on the input.
  arXiv  Detail & Related papers  (2023-06-02T16:27:34Z)
• Mitigating Algorithmic Bias with Limited Annotations [65.060639928772]
  When sensitive attributes are not disclosed or available, it is needed to manually annotate a small part of the training data to mitigate bias. We propose Active Penalization Of Discrimination (APOD), an interactive framework to guide the limited annotations towards maximally eliminating the effect of algorithmic bias. APOD shows comparable performance to fully annotated bias mitigation, which demonstrates that APOD could benefit real-world applications when sensitive information is limited.
  arXiv  Detail & Related papers  (2022-07-20T16:31:19Z)
• Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning [57.88785630755165]
  Empirical risk minimization (ERM) is the workhorse of machine learning, but its model-agnostic guarantees can fail when we use adaptively collected data. We study a generic importance sampling weighted ERM algorithm for using adaptively collected data to minimize the average of a loss function over a hypothesis class. For policy learning, we provide rate-optimal regret guarantees that close an open gap in the existing literature whenever exploration decays to zero.
  arXiv  Detail & Related papers  (2021-06-03T09:50:13Z)
• RATT: Leveraging Unlabeled Data to Guarantee Generalization [96.08979093738024]
  We introduce a method that leverages unlabeled data to produce generalization bounds. We prove that our bound is valid for 0-1 empirical risk minimization. This work provides practitioners with an option for certifying the generalization of deep nets even when unseen labeled data is unavailable.
  arXiv  Detail & Related papers  (2021-05-01T17:05:29Z)
• ORDisCo: Effective and Efficient Usage of Incremental Unlabeled Data for Semi-supervised Continual Learning [52.831894583501395]
  Continual learning assumes the incoming data are fully labeled, which might not be applicable in real applications. We propose deep Online Replay with Discriminator Consistency (ORDisCo) to interdependently learn a classifier with a conditional generative adversarial network (GAN) We show ORDisCo achieves significant performance improvement on various semi-supervised learning benchmark datasets for SSCL.
  arXiv  Detail & Related papers  (2021-01-02T09:04:14Z)
• Stratified cross-validation for unbiased and privacy-preserving federated learning [0.0]
  We focus on the recurrent problem of duplicated records that, if not handled properly, may cause over-optimistic estimations of a model's performances. We introduce and discuss stratified cross-validation, a validation methodology that leverages stratification techniques to prevent data leakage in federated learning settings.
  arXiv  Detail & Related papers  (2020-01-22T15:49:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.