# Learning Over Dirty Data with Minimal Repairs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 44 references that are in the map.
- First posted on arXiv 18 Mar 2025.

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

- [GAIN: Missing Data Imputation using Generative Adversarial Nets](https://mlsanity.com/paper/1806.02920/) (2018)
- [Data Collection and Quality Challenges in Deep Learning: A Data-Centric AI Perspective](https://mlsanity.com/paper/2112.06409/) (2021)
- [Diffusion models for missing value imputation in tabular data](https://mlsanity.com/paper/2210.17128/) (2022)
- [What's a good imputation to predict with missing values?](https://mlsanity.com/paper/2106.00311/) (2021)
- [Error bounds, quadratic growth, and linear convergence of proximal methods](https://mlsanity.com/paper/1602.06661/) (2016)
- [MIRACLE: Causally-Aware Imputation via Learning Missing Data Mechanisms](https://mlsanity.com/paper/2111.03187/) (2021)
- [Causal Discovery in the Presence of Missing Data](https://mlsanity.com/paper/1807.04010/) (2018)
- [Processing of missing data by neural networks](https://mlsanity.com/paper/1805.07405/) (2018)
- [Nearest Neighbor Classifiers over Incomplete Information: From Certain Answers to Certain Predictions](https://mlsanity.com/paper/2005.05117/) (2020)
- [The Challenge of Imputation in Explainable Artificial Intelligence Models](https://mlsanity.com/paper/1907.12669/) (2019)
- [Learning Over Dirty Data Without Cleaning](https://mlsanity.com/paper/2004.02308/) (2020)
- [Efficient Implementation of LinearUCB through Algorithmic Improvements and Vector Computing Acceleration for Embedded Learning Systems](https://mlsanity.com/paper/2501.13139/) (2025)
- [In-Database Data Imputation](https://mlsanity.com/paper/2401.03359/) (2024)
- [Sparse Linear Regression With Missing Data](https://mlsanity.com/paper/1503.08348/) (2015)
- [RIGID: Robust Linear Regression with Missing Data](https://mlsanity.com/paper/2205.13635/) (2022)
- [Certain and Approximately Certain Models for Statistical Learning](https://mlsanity.com/paper/2402.17926/) (2024)
- [Handling missing values in clinical machine learning: Insights from an expert study](https://mlsanity.com/paper/2411.09591/) (2024)

## Abstract (arXiv)

Missing data often exists in real-world datasets, requiring significant time and effort for data repair to learn accurate models. In this paper, we show that imputing all missing values is not always necessary to achieve an accurate ML model. We introduce concepts of minimal and almost minimal repair, which are subsets of missing data items in training data whose imputation delivers accurate and reasonably accurate models, respectively. Imputing these subsets can significantly reduce the time, computational resources, and manual effort required for learning. We show that finding these subsets is NP-hard for some popular models and propose efficient approximation algorithms for wide range of models. Our extensive experiments indicate that our proposed algorithms can substantially reduce the time and effort required to learn on incomplete datasets.