# Generalizability vs. Counterfactual Explainability Trade-Off

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 36 references that are in the map.
- First posted on arXiv 29 May 2025.

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

- [Domain-Adversarial Training of Neural Networks](https://mlsanity.com/paper/1505.07818/) (2015)
- [Learning deep representations by mutual information estimation and maximization](https://mlsanity.com/paper/1808.06670/) (2018)
- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Model-Agnostic Counterfactual Explanations for Consequential Decisions](https://mlsanity.com/paper/1905.11190/) (2019)
- [Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks](https://mlsanity.com/paper/1802.04034/) (2018)
- [Formal Guarantees on the Robustness of a Classifier against Adversarial Manipulation](https://mlsanity.com/paper/1705.08475/) (2017)
- [Disentangling Adversarial Robustness and Generalization](https://mlsanity.com/paper/1812.00740/) (2018)
- [Local Rule-Based Explanations of Black Box Decision Systems](https://mlsanity.com/paper/1805.10820/) (2018)
- [Learning Model-Agnostic Counterfactual Explanations for Tabular Data](https://mlsanity.com/paper/1910.09398/) (2019)
- [CF-GNNExplainer: Counterfactual Explanations for Graph Neural Networks](https://mlsanity.com/paper/2102.03322/) (2021)
- [Early stopping and non-parametric regression: An optimal data-dependent stopping rule](https://mlsanity.com/paper/1306.3574/) (2013)
- [Interpretable Predictions of Tree-based Ensembles via Actionable Feature Tweaking](https://mlsanity.com/paper/1706.06691/) (2017)
- [The Intriguing Relation Between Counterfactual Explanations and Adversarial Examples](https://mlsanity.com/paper/2009.05487/) (2020)
- [FOCUS: Flexible Optimizable Counterfactual Explanations for Tree Ensembles](https://mlsanity.com/paper/1911.12199/) (2019)
- [The Dimpled Manifold Model of Adversarial Examples in Machine Learning](https://mlsanity.com/paper/2106.10151/) (2021)
- [Unrestricted Adversarial Examples](https://mlsanity.com/paper/1809.08352/) (2018)
- [CounteRGAN: Generating Realistic Counterfactuals with Residual Generative Adversarial Nets](https://mlsanity.com/paper/2009.05199/) (2020)
- [ReLAX: Reinforcement Learning Agent eXplainer for Arbitrary Predictive Models](https://mlsanity.com/paper/2110.11960/) (2021)
- [An empirical analysis of dropout in piecewise linear networks](https://mlsanity.com/paper/1312.6197/) (2013)
- [Eliminating Catastrophic Overfitting Via Abnormal Adversarial Examples Regularization](https://mlsanity.com/paper/2404.08154/) (2024)
- [Understanding Adversarial Robustness: The Trade-off between Minimum and Average Margin](https://mlsanity.com/paper/1907.11780/) (2019)

## Abstract (arXiv)

In this work, we investigate the relationship between model generalization and counterfactual explainability in supervised learning. We introduce the notion of varepsilon-valid counterfactual probability (varepsilon-VCP) -- the probability of finding perturbations of a data point within its varepsilon-neighborhood that result in a label change. We provide a theoretical analysis of varepsilon-VCP in relation to the geometry of the model's decision boundary, showing that varepsilon-VCP tends to increase with model overfitting. Our findings establish a rigorous connection between poor generalization and the ease of counterfactual generation, revealing an inherent trade-off between generalization and counterfactual explainability. Empirical results validate our theory, suggesting varepsilon-VCP as a practical proxy for quantitatively characterizing overfitting.