# Certifying Robustness to Programmable Data Bias in Decision Trees

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 42 references that are in the map.
- First posted on arXiv 8 Oct 2021.

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

- [Poison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks](https://mlsanity.com/paper/1804.00792/) (2018)
- [Certified Defenses for Data Poisoning Attacks](https://mlsanity.com/paper/1706.03691/) (2017)
- [Why Is My Classifier Discriminatory?](https://mlsanity.com/paper/1805.12002/) (2018)
- [Query-Efficient Hard-label Black-box Attack:An Optimization-based Approach](https://mlsanity.com/paper/1807.04457/) (2018)
- [Distributionally Robust Logistic Regression](https://mlsanity.com/paper/1509.09259/) (2015)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Deep Partition Aggregation: Provable Defense against General Poisoning Attacks](https://mlsanity.com/paper/2006.14768/) (2020)
- [Certified Robustness to Label-Flipping Attacks via Randomized Smoothing](https://mlsanity.com/paper/2002.03018/) (2020)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Intrinsic Certified Robustness of Bagging against Data Poisoning Attacks](https://mlsanity.com/paper/2008.04495/) (2020)
- [Label Sanitization against Label Flipping Poisoning Attacks](https://mlsanity.com/paper/1803.00992/) (2018)
- [Introduction to Neural Network Verification](https://mlsanity.com/paper/2109.10317/) (2021)
- [Certified Robustness of Nearest Neighbors against Data Poisoning and Backdoor Attacks](https://mlsanity.com/paper/2012.03765/) (2020)
- [Robust Decision Trees Against Adversarial Examples](https://mlsanity.com/paper/1902.10660/) (2019)
- [Optimization and Abstraction: A Synergistic Approach for Analyzing Neural Network Robustness](https://mlsanity.com/paper/1904.09959/) (2019)
- [Leave-one-out Unfairness](https://mlsanity.com/paper/2107.10171/) (2021)
- [Ensuring Fairness Beyond the Training Data](https://mlsanity.com/paper/2007.06029/) (2020)
- [Provably Robust Boosted Decision Stumps and Trees against Adversarial Attacks](https://mlsanity.com/paper/1906.03526/) (2019)
- [Robustness to Programmable String Transformations via Augmented Abstract Training](https://mlsanity.com/paper/2002.09579/) (2020)

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

- [FARE: Provably Fair Representation Learning with Practical Certificates](https://mlsanity.com/paper/2210.07213/) (2022)
- [BagFlip: A Certified Defense against Data Poisoning](https://mlsanity.com/paper/2205.13634/) (2022)
- [The Dataset Multiplicity Problem: How Unreliable Data Impacts Predictions](https://mlsanity.com/paper/2304.10655/) (2023)
- [Monitoring Algorithmic Fairness](https://mlsanity.com/paper/2305.15979/) (2023)
- [Consistent Range Approximation for Fair Predictive Modeling](https://mlsanity.com/paper/2212.10839/) (2022)
- [Certifying the Fairness of KNN in the Presence of Dataset Bias](https://mlsanity.com/paper/2307.08722/) (2023)
- [Monitoring Algorithmic Fairness under Partial Observations](https://mlsanity.com/paper/2308.00341/) (2023)
- [Toward Operationalizing Pipeline-aware ML Fairness: A Research Agenda for Developing Practical Guidelines and Tools](https://mlsanity.com/paper/2309.17337/) (2023)
- [PECAN: A Deterministic Certified Defense Against Backdoor Attacks](https://mlsanity.com/paper/2301.11824/) (2023)
- [Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attacks](https://mlsanity.com/paper/2407.10867/) (2024)
- [Certifying Data-Bias Robustness in Linear Regression](https://mlsanity.com/paper/2206.03575/) (2022)
- [Systematic Testing of the Data-Poisoning Robustness of KNN](https://mlsanity.com/paper/2307.08288/) (2023)
- [A Note on Bias to Complete](https://mlsanity.com/paper/2402.11710/) (2024)
- [Analyzing Fairness of Neural Network Prediction via Counterfactual Dataset Generation](https://mlsanity.com/paper/2602.10457/) (2026)
- [Verification of Neural Networks Local Differential Classification Privacy](https://mlsanity.com/paper/2310.20299/) (2023)
- [Timber! Poisoning Decision Trees](https://mlsanity.com/paper/2410.00862/) (2024)
- [Monitoring of Static Fairness](https://mlsanity.com/paper/2507.03048/) (2025)
- [Algorithmic Fairness: A Runtime Perspective](https://mlsanity.com/paper/2507.20711/) (2025)
- [Robustness Certificates for Neural Networks Against Data Poisoning and Evasion Attacks](https://mlsanity.com/paper/2512.20865/) (2025)
- [Exact Certification of Neural Networks and Partition Aggregation Ensembles against Label Poisoning](https://mlsanity.com/paper/2604.11416/) (2026)
- [Energy Shields for Fairness](https://mlsanity.com/paper/2605.24926/) (2026)

## Abstract (arXiv)

Datasets can be biased due to societal inequities, human biases, under-representation of minorities, etc. Our goal is to certify that models produced by a learning algorithm are pointwise-robust to potential dataset biases. This is a challenging problem: it entails learning models for a large, or even infinite, number of datasets, ensuring that they all produce the same prediction. We focus on decision-tree learning due to the interpretable nature of the models. Our approach allows programmatically specifying bias models across a variety of dimensions (e.g., missing data for minorities), composing types of bias, and targeting bias towards a specific group. To certify robustness, we use a novel symbolic technique to evaluate a decision-tree learner on a large, or infinite, number of datasets, certifying that each and every dataset produces the same prediction for a specific test point. We evaluate our approach on datasets that are commonly used in the fairness literature, and demonstrate our approach's viability on a range of bias models.