Provable Training Set Debugging for Linear Regression

• URL: http://arxiv.org/abs/2006.09009v2
• Date: Tue, 10 Aug 2021 03:42:03 GMT
• Title: Provable Training Set Debugging for Linear Regression
• Authors: Xiaomin Zhang, Xiaojin Zhu, Po-Ling Loh
• Abstract summary: We first formulate a general statistical algorithm for identifying buggy points and provide rigorous theoretical guarantees. We then present two case studies to illustrate the results of our general theory and the dependence of our estimator on clean versus buggy points.
• Score: 17.138864028618276
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate problems in penalized $M$-estimation, inspired by applications in machine learning debugging. Data are collected from two pools, one containing data with possibly contaminated labels, and the other which is known to contain only cleanly labeled points. We first formulate a general statistical algorithm for identifying buggy points and provide rigorous theoretical guarantees under the assumption that the data follow a linear model. We then present two case studies to illustrate the results of our general theory and the dependence of our estimator on clean versus buggy points. We further propose an algorithm for tuning parameter selection of our Lasso-based algorithm and provide corresponding theoretical guarantees. Finally, we consider a two-person "game" played between a bug generator and a debugger, where the debugger can augment the contaminated data set with cleanly labeled versions of points in the original data pool. We establish a theoretical result showing a sufficient condition under which the bug generator can always fool the debugger. Nonetheless, we provide empirical results showing that such a situation may not occur in practice, making it possible for natural augmentation strategies combined with our Lasso debugging algorithm to succeed.

Related papers

• Consistency-based Abductive Reasoning over Perceptual Errors of Multiple Pre-trained Models in Novel Environments [5.5855749614100825]
  This paper addresses the hypothesis that leveraging multiple pre-trained models can mitigate this recall reduction.<n>We formulate the challenge of identifying and managing conflicting predictions from various models as a consistency-based abduction problem.<n>Our results validate the use of consistency-based abduction as an effective mechanism to robustly integrate knowledge from multiple imperfect models in challenging, novel scenarios.
  arXiv  Detail & Related papers  (2025-05-25T23:17:47Z)
• Self-Boost via Optimal Retraining: An Analysis via Approximate Message Passing [58.52119063742121]
  Retraining a model using its own predictions together with the original, potentially noisy labels is a well-known strategy for improving the model performance.<n>This paper addresses the question of how to optimally combine the model's predictions and the provided labels.<n>Our main contribution is the derivation of the Bayes optimal aggregator function to combine the current model's predictions and the given labels.
  arXiv  Detail & Related papers  (2025-05-21T07:16:44Z)
• Optimal Algorithms for Augmented Testing of Discrete Distributions [25.818433126197036]
  We show that a predictor can indeed reduce the number of samples required for all three property testing tasks. A key advantage of our algorithms is their adaptability to the precision of the prediction. We provide lower bounds to indicate that the improvements in sample complexity achieved by our algorithms are information-theoretically optimal.
  arXiv  Detail & Related papers  (2024-12-01T21:31:22Z)
• Fact Checking Beyond Training Set [64.88575826304024]
  We show that the retriever-reader suffers from performance deterioration when it is trained on labeled data from one domain and used in another domain. We propose an adversarial algorithm to make the retriever component robust against distribution shift. We then construct eight fact checking scenarios from these datasets, and compare our model to a set of strong baseline models.
  arXiv  Detail & Related papers  (2024-03-27T15:15:14Z)
• Best-Effort Adaptation [62.00856290846247]
  We present a new theoretical analysis of sample reweighting methods, including bounds holding uniformly over the weights. We show how these bounds can guide the design of learning algorithms that we discuss in detail. We report the results of a series of experiments demonstrating the effectiveness of our best-effort adaptation and domain adaptation algorithms.
  arXiv  Detail & Related papers  (2023-05-10T00:09:07Z)
• Knockoffs-SPR: Clean Sample Selection in Learning with Noisy Labels [56.81761908354718]
  We propose a novel theoretically guaranteed clean sample selection framework for learning with noisy labels. Knockoffs-SPR can be regarded as a sample selection module for a standard supervised training pipeline. We further combine it with a semi-supervised algorithm to exploit the support of noisy data as unlabeled data.
  arXiv  Detail & Related papers  (2023-01-02T07:13:28Z)
• Regression with Label Differential Privacy [64.21020761920322]
  We derive a label DP randomization mechanism that is optimal under a given regression loss function. We prove that the optimal mechanism takes the form of a "randomized response on bins"
  arXiv  Detail & Related papers  (2022-12-12T17:41:32Z)
• Debugging using Orthogonal Gradient Descent [7.766921168069532]
  Given a trained model that is partially faulty, can we correct its behaviour without having to train the model from scratch? In other words, can we " neural networks similar to how we address bugs in our mathematical models and standard computer code?
  arXiv  Detail & Related papers  (2022-06-17T00:03:54Z)
• Leveraging Unlabeled Data to Predict Out-of-Distribution Performance [63.740181251997306]
  Real-world machine learning deployments are characterized by mismatches between the source (training) and target (test) distributions. In this work, we investigate methods for predicting the target domain accuracy using only labeled source data and unlabeled target data. We propose Average Thresholded Confidence (ATC), a practical method that learns a threshold on the model's confidence, predicting accuracy as the fraction of unlabeled examples.
  arXiv  Detail & Related papers  (2022-01-11T23:01:12Z)
• Evaluating State-of-the-Art Classification Models Against Bayes Optimality [106.50867011164584]
  We show that we can compute the exact Bayes error of generative models learned using normalizing flows. We use our approach to conduct a thorough investigation of state-of-the-art classification models.
  arXiv  Detail & Related papers  (2021-06-07T06:21:20Z)
• Improving Generalization of Deep Fault Detection Models in the Presence of Mislabeled Data [1.3535770763481902]
  We propose a novel two-step framework for robust training with label noise. In the first step, we identify outliers (including the mislabeled samples) based on the update in the hypothesis space. In the second step, we propose different approaches to modifying the training data based on the identified outliers and a data augmentation technique.
  arXiv  Detail & Related papers  (2020-09-30T12:33:25Z)
• Causal Bandits without prior knowledge using separating sets [3.1000291317725]
  The Causal Bandit is a variant of the classic Bandit problem where an agent must identify the best action in a sequential decision-making process. Methods proposed for this problem thus far in the literature rely on exact prior knowledge of the full causal graph. We formulate new causal bandit algorithms that no longer necessarily rely on prior causal knowledge.
  arXiv  Detail & Related papers  (2020-09-16T20:08:03Z)
• Provable Training of a ReLU Gate with an Iterative Non-Gradient Algorithm [0.7614628596146599]
  We show provable guarantees on the training of a single ReLU gate in hitherto unexplored regimes. We show a first-of-its-kind approximate recovery of the true label generating parameters under an (online) data-poisoning attack on the true labels. Our guarantee is shown to be nearly optimal in the worst case and its accuracy of recovering the true weight degrades gracefully with increasing probability of attack and its magnitude.
  arXiv  Detail & Related papers  (2020-05-08T17:59:23Z)

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.