---
title: "Countering Overfitting with Counterfactual Examples"
authors:
  - "Flavio Giorgi"
  - "Fabiano Veglianti"
  - "Fabrizio Silvestri"
  - "Gabriele Tolomei"
published: 2026-04-20
doi: "10.1145/3770854.3780243"
source_url: "https://doi.org/10.1145/3770854.3780243"
conversion:
  method: pymupdf4llm
  authoritative_source: rendered PDF
---

> Conversion note: This Markdown was extracted from the rendered PDF. The PDF remains authoritative for formulas, tables, figures, and layout.
# **Countering Overfitting with Counterfactual Examples**

Flavio Giorgi

giorgi@di.uniroma1.it Sapienza University of Rome Rome, Italy

## Fabrizio Silvestri

fsilvestri@diag.uniroma1.it Sapienza University of Rome, Rome & ISTI-CNR, Pisa Italy

### **Abstract**

Overfitting is a well-known issue in machine learning that occurs when a model struggles to generalize its predictions to new, unseen data beyond the scope of its training set. Traditional techniques to mitigate overfitting include early stopping, data augmentation, and regularization. In this work, we demonstrate that the degree of overfitting of a trained model is correlated with the ability to generate _counterfactual examples_ . The higher the overfitting, the easier it will be to find a valid counterfactual example for a randomly chosen input data point. Therefore, we introduce CF-Reg, a novel regularization term in the training loss that controls overfitting by ensuring enough margin between each instance and its corresponding counterfactual. Experiments conducted across multiple datasets and models show that our _counterfactual regularizer_ generally outperforms existing regularization techniques.

### **CCS Concepts**

- **Computing methodologies** → **Regularization** ; **Machine learn-**

- **ing** ; **Supervised learning** .

### **Keywords**

Overfitting, generalizability, regularization, counterfactual examples, counterfactual explanations

#### **ACM Reference Format:**

Flavio Giorgi, Fabiano Veglianti, Fabrizio Silvestri, and Gabriele Tolomei. 2026. Countering Overfitting with Counterfactual Examples. In _Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1 (KDD ’26), August 09–13, 2026, Jeju Island, Republic of Korea._ ACM, New York, NY, USA, 12 pages. https://doi.org/10.1145/3770854.3780243

### **1 Introduction**

One of the key challenges in machine learning is developing models that can generalize their predictions to new, unseen data beyond the scope of the training set. When the predictive accuracy of a model on the training set far exceeds that on the test set, this indicates a phenomenon known as _overfitting_ . In general, the impact of overfitting is more pronounced for highly complex models like recent

Fabiano Veglianti fabiano.veglianti@uniroma1.it Sapienza University of Rome

Rome, Italy

## Gabriele Tolomei

tolomei@di.uniroma1.it

Sapienza University of Rome, Rome & ISTI-CNR, Pisa Italy

deep neural networks with billions of parameters. To compensate for the risk of overfitting, these models require massive amounts of training data, which may not always be feasible.

Therefore, several strategies have been proposed in the literature to mitigate the problem of model overfitting. Among these, _early stopping_ interrupts the training phase before the model starts learning the noise in the data rather than the actual underlying input/output relationship. Furthermore, _data augmentation_ is a technique that artificially increases the training set. For example, in the context of image data, this can include applying translation, flipping, and rotation transformations to input samples. Finally, _regularization_ is a collection of training/optimization techniques that try to eliminate irrelevant factors by assessing the importance of features, preventing minor input changes from causing significant output variations.

In this work, we offer an entirely new perspective on model overfitting, establishing a connection with the ability to generate _counterfactual examples_ [35]. The notion of counterfactual examples has been successfully used, for instance, to attach post-hoc explanations for predictions of individual instances in the form: “ _If A had been different, B would_ **_not_** _have occurred_ ” [30]. Generally, finding the counterfactual example for an instance resorts to searching for the minimal perturbation of the input that crosses the decision boundary induced by a trained model. This task reduces to solving a constrained optimization problem.

In the presence of a strong degree of model overfitting, the decision boundary learned becomes a highly convoluted surface, up to the point where it perfectly separates every training input sample. Therefore, each data point, on average, is “closer” to the decision boundary, making it easier to find the best counterfactual example. The intuition behind this claim is depicted in Figure 1 and grounded in the theoretical foundations of margin theory [38].

Following this idea, we introduce a novel _counterfactual regularization_ term in the training loss that controls overfitting by enforcing a margin between each instance and its hypothetical counterfactual. Below, we summarize the primary novel contributions of our work:

- ( _𝑖_ ) We explore the relationship between generalizability and counterfactual explanations, based on margin theory.

This work is licensed under a Creative Commons Attribution 4.0 International License. _KDD ’26, Jeju Island, Republic of Korea_

© 2026 Copyright held by the owner/author(s). ACM ISBN 979-8-4007-2258-5/2026/08

https://doi.org/10.1145/3770854.3780243

- ( _𝑖𝑖_ ) We show that counterfactual examples can effectively guide and enhance the model training process.

- ( _𝑖𝑖𝑖_ ) We propose a counterfactual regularizer (CF-Reg) that outperforms existing regularization techniques.

302

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Flavio Giorgi, Fabiano Veglianti, Fabrizio Silvestri, and Gabriele Tolomei

of less important features by reducing their weights in the model. o However, since identifying useless features can be challenging, ee x ee a regularization techniques work by applying a penalty term, or “regBe» x x ularizer”, to the objective function. This penalizes complex models, x * x x * x encouraging simpler and more generalizable solutions. For example, xxxxxx L1 (“Lasso”) and L2 (“Ridge”) regularization, which add the _𝐿_ 1-norm ** and _𝐿_ 2-norm of the learned parameter as a penalties, respectively, x are commonly adopted in linear regression. Furthermore, _Dropout_ **(a) No overfitting (b) Overfitting** is a popular technique to combat overfitting in neural networks. This approach randomly drops units and relevant connections from **1: Distance between an input data point (** _𝒙_ **) and its** the neural network during training to prevent co-adaptation [36].

**Figure 1: Distance between an input data point (** _𝒙_ **) and its counterfactual example (** $\tilde{\mathbf{x}}$ **): On average, this may be higher for a well-trained model (a) than an overfitted model (b).**

Unlike existing regularization techniques, which either aim to reduce the magnitude of the learned model’s weights (such as Lasso and Ridge) or randomly deactivate certain parameters (such as Dropout), our penalty term is inherently _data-driven_ . In other words, the counterfactual regularization we introduce (CF-Reg) is computed directly from the training observations, making it highly tailored to the specific dataset under consideration.

- ( _𝑖𝑣_ ) We cast our regularization method in an extensible framework that is compatible with any differentiable counterfactual example generator. The source code for our method is available at the following GitHub repository: https://github. com/hercolelab/CF-Reg.

**_Adversarial Training._** Adversarial training is another strategy that can be adapted to mitigate overfitting. Notably, Madry et al. [25] proposed a min-max optimization framework that enhances model robustness by training against adversarial examples generated via Projected Gradient Descent (PGD). This approach serves as an effective form of regularization, as it discourages the learned model from depending on non-robust or spurious patterns [31].

The remainder of this paper is structured as follows. In Section 2, we summarize related work. Section 3 reviews background concepts, useful for our problem formulation in Section 4. In Section 5, we describe our method that is validated through extensive experiments in Section 6. We discuss the applicability and limitations of our method in Section 7. Finally, Section 8 concludes our work.

### **2.2 Counterfactual Examples**

### **2 Related Work**

Counterfactual examples have gained significant attention in machine learning due to their utility in various applications, including model _explainability_ and _robustness_ .

### **2.1 Model Overfitting**

Several strategies have been proposed in the literature to reduce the effects of overfitting, which can be broadly categorized as follows.

**_Explainability._** Counterfactual explanations offer valuable insights into model predictions by providing alternative scenarios under which the prediction would change [35]. Several studies have explored the use of counterfactual examples to enhance the interpretability of complex machine learning models, such as ensembles of decision trees [23, 33, 34] and deep neural networks (DNNs) [21], including graph neural networks (GNNs) [3, 24]. Indeed, counterfactual instances help elucidate the underlying decision-making process of black-box models, thereby increasing trust and transparency in AI systems [4, 5, 10, 17, 26], especially when translated into natural language narratives [9].

**_Early Stopping._** This strategy aims to mitigate the phenomenon known as “learning speed slow-down.” This issue occurs when the accuracy of a model ceases to improve or even worsens due to noiselearning. The concept has a long history, dating back to the 1970s in the context of the Landweber iteration [28]. It has since been widely adopted in iterative algorithms, particularly for training deep neural networks in combination with backpropagation [2].

**_Data Augmentation._** The more complex the model, the higher the number of parameters that need to be learned. Therefore, the size of the training set must be adequate to avoid overfitting. Data augmentation techniques play a crucial role in enhancing model generalization across various domains, including pattern recognition and image processing. These techniques aim to expand existing datasets to generate additional data. Typically, four main approaches are employed [18, 32, 39]: _(i)_ acquiring new data, _(ii)_ introducing random noise to the existing dataset, _(iii)_ reprocessing existing data to produce new instances, and _(iv)_ sampling new data based on the distribution of the existing dataset.

**_Robustness._** Counterfactual examples have also been leveraged to enhance the robustness of machine learning models against adversarial attacks [1]. Indeed, there is a strict relationship between adversarial and counterfactual examples [7], although their primary goals are divergent. While both adversarial and counterfactual examples involve perturbing input data to influence model predictions, adversarial examples are crafted to jeopardize the model, whereas counterfactual examples are generated to understand the model’s behavior. By generating instances that are semantically similar to the original input but induce different model predictions, He et al. [13] enhances model robustness against adversarial perturbations.

**_Regularization._** An overfitting model tends to incorporate all available features into its decision-making process, even those with minimal impact or that are simply noise. To address this issue, there are two main approaches: _(i) Feature selection_ , where only the most relevant features are retained, discarding those deemed irrelevant; _(ii) Feature regularization_ , which involves minimizing the influence

Recent work has explored the use of generative models to produce realistic counterfactual instances for data augmentation and model refinement [8, 14], highlighting the potential of counterfactual reasoning in generative modeling tasks [22].

303

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Countering Overfitting with Counterfactual Examples

To the best of our knowledge, however, this is the first study to link counterfactual examples to model generalization and to employ them as the cornerstone of a new regularization strategy.

### **3 Background and Preliminaries**

Let _𝑓𝜽_ : X ↦→Y denote a predictive model parameterized by a set of (learnable) weights _𝜽_ ∈ **𝚯** that takes an input _𝒙_ ∈X ⊆ R<sup>_𝑛_</sup> and maps it to an output _𝑦_ ∈Y. In the standard supervised learning setting, the optimal weights ( _𝜽_<sup>∗</sup> ) are found by minimizing a specific loss function (L) computed on a training set (D) of _𝑚_ i.i.d. labeled instances, D = {( _𝒙𝑖,𝑦𝑖_ )}<sup>_𝑚_</sup> _𝑖_ =1<sup>.</sup>


![](assets/paper_cf-reg-2026.pdf-0003-05.png)


Here, _ℓ_ represents an instance-level error between the model’s prediction for a given input ( _𝒙𝑖_ ) and its corresponding actual label ( _𝑦𝑖_ ), such as cross-entropy (for classification tasks) or mean squared error (for regression tasks).

Furthermore, we assume to have available a counterfactual generator model _𝑔𝜽_ : X ↦→X, for the predictive model _𝑓𝜽_ , that takes as input a data point _𝒙_ and produces as output its corresponding (optimal) counterfactual $\tilde{\mathbf{x}}^*$ . This typically requires solving a constrained objective as follows:


![](assets/paper_cf-reg-2026.pdf-0003-08.png)


Here, _𝛿_ : X × X ↦→ R≥0 is a function that measures the distance between the original input data point and its counterfactual. In practice, _𝛿_ often computes the _𝐿_ 1- or _𝐿_ 2-norm of the displacement vector between the original and the counterfactual example.

In general, for a given input _𝒙_ , there could be several, possibly infinitely many _valid_ counterfactuals: $\tilde{\mathbf{x}}_1, \tilde{\mathbf{x}}_2, \ldots$ In this work, a valid counterfactual is considered as any instance $\tilde{\mathbf{x}}$ that crosses the decision boundary induced by _𝑓𝜽_ , i.e., where $f_{\theta}(\mathbf{x}) \ne f_{\theta}(\tilde{\mathbf{x}})$. More refined notions of validity are also conceivable, such as those entailing the _plausibility_ of the generated counterfactual, which assesses whether the counterfactual example is indeed realistic. For example, suppose we have trained an image classifier to distinguish between birds and rabbits. In this context, a plausible (and valid) counterfactual for a rabbit must be an image resembling a bird. However, for the purpose of this work, we are only interested in characterizing the ability to find a valid counterfactual and relating this to the degree of model overfitting, regardless of its plausibility.

Formally, let _𝒙_ ∈X be an input sample, _𝑓𝜽_ a trained model, _𝛿_ : X×X ↦→ R≥0 a distance function, and _𝜀_ ∈ R _>_ 0 a fixed threshold. We consider an _𝜀-valid counterfactual example_ ( _𝜀_ -VCE) for _𝒙_ any $\tilde{\mathbf{x}} \ne \mathbf{x}$, such that $f_{\theta}(\mathbf{x}) \ne f_{\theta}(\tilde{\mathbf{x}})$ and $\delta(\mathbf{x},\tilde{\mathbf{x}}) \le \epsilon$.

### **4 Impact of Counterfactual Examples on Model Generalizability**

### **4.1 Intuitive Perspective**

We consider a training set D = {( _𝒙𝑖,𝑦𝑖_ )}<sup>_𝑚_</sup> _𝑖_ =1<sup>of</sup><sup>_𝑚_i.i.d.labeled</sup> instances, as introduced above. Then, suppose this dataset is used to train a sequence of _𝑘_ different models ( _𝑓𝜽_ 0 _, 𝑓𝜽_ 1 _, . . . , 𝑓𝜽 𝑘_ −1 ). Each

model _𝑓𝜽 𝑖_ is associated with a training accuracy _𝛼𝑖_ (calculated on D), such that _𝛼_ 0 _< 𝛼_ 1 _< . . . < 𝛼𝑘_ −1, where _𝑓𝜽_ 0 indicates the random baseline model and _𝑓𝜽 𝑘_ −1 is the dummy model that simply memorizes the entire training set and, therefore, achieves the perfect training accuracy ( _𝛼𝑘_ −1 = 1).<sup>1</sup>

We claim that for a fixed positive threshold _𝜀 >_ 0, the expected fraction of training points for which we can find an _𝜀_ -valid counterfactual example is positively correlated with the training accuracy of the model. In other words, given two trained models _𝑓𝜽 𝑖_ and _𝑓𝜽 𝑗_ , where _𝑖 > 𝑗_ , whose training accuracies are _𝛼𝑖 > 𝛼 𝑗_ , we expect to find, on average, more _𝜀_ -valid counterfactual examples for _𝑓𝜽 𝑖_ .

This intuition stems from the idea that a model with a higher training accuracy tends to have a more intricate decision boundary surface, which captures all the nuances of the training data more precisely. Consequently, data points are, _on average_ , closer to such a convoluted decision boundary, making it easier to cross it and thus to find valid counterfactual examples within a distance of _𝜀_ .

In essence, a model for which finding counterfactual examples is “too easy” may indicate a risk of overfitting. Thus, a trade-off must exist between the model’s generalizability and its counterfactual explainability, which we aim to investigate further in this study.

### **4.2 Theoretical Motivation**

The intuition outlined above is supported by a well-established theoretical foundation rooted in classical margin theory. Statistical learning theory tells us that a model’s generalization error can be bounded using empirical margin distributions [19]. A prominent example is the support vector machine (SVM), which _explicitly_ maximizes the minimum margin on linearly separable datasets.

Interestingly, margin maximization is not exclusive to SVMs. Soudry et al. [29] show that gradient descent applied to logistic regression on linearly separable data _implicitly_ maximizes the minimum margin, thereby mirroring the behavior of SVMs. This implicit bias toward margin maximization has also been observed in more complex models, including deep neural networks [11, 15].

Building on these insights, Wu and Yu [38] uncover an intriguing trade-off between the minimum and _average_ margins, where the latter is defined as the average distance of training examples to the decision boundary. Specifically, they show that optimizing for a larger minimum margin can unintentionally reduce the average margin, thereby increasing the model’s vulnerability to adversarial examples. For the same reason, as training progresses and the average distance between data points and the decision boundary decreases, it becomes easier to identify a valid counterfactual example within a fixed perturbation radius _𝜀_ .

To further validate this claim, Figure 2 shows the empirical distribution of margin distances computed from all training points in the Water dataset [16] at different training epochs of a logistic regression model. We notice that, at initialization (epoch 0), the distribution is relatively uniform, with a higher average margin distance of 0 _._ 754. As training progresses, the distribution of distances to the classifier’s boundary becomes increasingly right-skewed, concentrating more of the mass near lower margin values. By epoch 8,000, the average margin distance drops to 0 _._ 202.

> 1In practice, the sequence of _𝑘_ models may correspond to intermediate checkpoints saved at various training epochs.

304

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Flavio Giorgi, Fabiano Veglianti, Fabrizio Silvestri, and Gabriele Tolomei


![](assets/paper_cf-reg-2026.pdf-0004-02.png)


<!-- Start of picture text -->
20.0, Epoch = 400<br>ys | Mean038 |<br>iso] |<br>ws, 9!<br>100)<br>7s] ih<br>5.0<br>25<br>99-05 1015 20 25 30<br>Margin<br><!-- End of picture text -->


![](assets/paper_cf-reg-2026.pdf-0004-03.png)


<!-- Start of picture text -->
20.0, Epoch = 800<br>55) | —~ Mean:0.310<br>sso] |<br>vs |<br>roo} ff<br>28]<br>5.0<br>25)<br>°° 00 05 10 15 20 25 30<br>Margin<br><!-- End of picture text -->


![](assets/paper_cf-reg-2026.pdf-0004-04.png)


<!-- Start of picture text -->
20.0, Epoch = 1600<br>45.5) Ji = Meansazas |<br>sol<br>25)<br>100)<br>28]<br>5.0<br>25)<br>°° 00 05 10 15 2025-30<br>Margin<br><!-- End of picture text -->


![](assets/paper_cf-reg-2026.pdf-0004-05.png)


<!-- Start of picture text -->
20.0, Epoch = 8000<br>54) | —~ Mean: 0.202<br>aso) if<br>2s<br>10.0<br>25]<br>5.0<br>25<br>°° 00 08 10 15 20 25 30<br>Margin<br><!-- End of picture text -->


![](assets/paper_cf-reg-2026.pdf-0004-06.png)


<!-- Start of picture text -->
20.0 Epoch = 0<br>Sus Fo Means0756 |<br>zo<br>Ss i<br>F100 H<br>fos i<br>z 5.0) I<br>25<br>0090-0510 15-20 25 30<br>Margin<br><!-- End of picture text -->

**Figure 2: Evolution of the empirical distribution of margin distances for training data points in the Water dataset across different training epochs of a logistic regression model. As the training progresses, the** **_average_ margin distance decreases.**

### **4.3 Estimating Counterfactual Probability**

In this section, we formally characterize what we mean by the ease of finding an _𝜀_ -valid counterfactual example for a given data point and, therefore, for a full training set of data points.

Let us consider the generic predictive model _𝑓𝜽_ trained on D = {( _𝒙𝑖,𝑦𝑖_ )}<sup>_𝑚_</sup> _𝑖_ =1<sup>. Suppose we associate with each training data point</sup> _𝒙𝑖_ a binary random variable _𝑋𝑖_ ∈{0 _,_ 1}, which indicates whether there exists an _𝜀_ -valid counterfactual example $\tilde{\mathbf{x}}_i$ for _𝒙𝑖_ . Therefore, each _𝑋𝑖_ follows a Bernoulli distribution, i.e., _𝑋𝑖_ ∼ Bernoulli( _𝑝𝑖_<sup>_𝜀_),</sup> whose probability mass function is defined as below.


![](assets/paper_cf-reg-2026.pdf-0004-11.png)


Furthermore, let _𝑋_<sup>¯</sup> denote the fraction of training points for which an _𝜀_ -valid counterfactual example exists. Formally, $\bar{X}=\frac{1}{m}\sum_{i=1}^{m}X_i$ is the average of _𝑚_ Bernoulli random variables.

By the linearity of expectation, we can calculate:


![](assets/paper_cf-reg-2026.pdf-0004-14.png)


where $\mathbb{E}[X_i]=p_i^{\epsilon}$ and, therefore, $\mathbb{E}[\bar{X}]=\bar{p}^{\epsilon}$ is the average across the entire dataset. Note that the random variable $Z=\sum_{i=1}^{m}X_i$ follows a Poisson-Binomial distribution, since the $X_i$ are independent but not necessarily identically distributed. Consequently, $\bar{X}=Z/m$ is also a Poisson-Binomial random variable, scaled by a factor of $1/m$.

For a fixed _𝜀 >_ 0, we argue that E[ _𝑋_<sup>¯</sup> ] is positively correlated with the model’s training accuracy. This follows from the theoretical result discussed above [38], which shows that higher training accuracy corresponds to a smaller average margin to the decision boundary. Therefore, as the training accuracy of _𝑓𝜽_ increases, so does the average fraction of training instances for which a valid counterfactual can be found within distance _𝜀_ .

Firstly, we need to estimate each _𝑝𝑖_<sup>_𝜀_, which we refer to as the</sup> (sample-level) _𝜀-valid counterfactual probability_ ( _𝜀_ -VCP). Formally, let _𝒙_ ∈X ⊆ R<sup>_𝑛_</sup> be a generic training point, and _𝜀_ ∈ R _>_ 0 a positive real number. Consider the _𝜀𝑛_ -ball as the _𝑛_ -dimensional hypersphere of radius _𝜀_ centered around _𝒙_ . Let $V_{\mathbf{x}}^{\epsilon}\subseteq\mathbb{R}^n$ be the total hypervolume of this hypersphere, and let $V_{\tilde{\mathbf{x}}}^{\epsilon}\subseteq V_{\mathbf{x}}^{\epsilon}$ denote the portion falling within the counterfactual region delimited by the decision boundary induced by _𝑓𝜽_. Therefore, the _𝜀_ -VCP is estimated as $p^{\epsilon}=V_{\tilde{\mathbf{x}}}^{\epsilon}/V_{\mathbf{x}}^{\epsilon}$.


![](assets/paper_cf-reg-2026.pdf-0004-18.png)


<!-- Start of picture text -->
© 6 oseho o<br>20%<br>vw<br>x)<br>°<br>°<br>oor<br><!-- End of picture text -->


![](assets/paper_cf-reg-2026.pdf-0004-19.png)


<!-- Start of picture text -->
© SQeweo o<br>ze<br>one<br>20<br>“nd<br>C)<br>oa<br><!-- End of picture text -->


![](assets/paper_cf-reg-2026.pdf-0004-20.png)


<!-- Start of picture text -->
(a) Low  𝜀 -valid counterfac- (b) High 𝜀 -valid counter-<br>tual probability factual probability<br><!-- End of picture text -->

**Figure 3: The** _𝜀_ **-** **_valid counterfactual probability_ for a sample** _𝒙_ ∈ R<sup>2</sup> **can be estimated as the ratio of the area of the circle centered in** _𝒙_ **with radius** _𝜀_ **that falls behind the decision boundary (in red).**

Intuitively, given a fixed _𝒙_ and two models having different decision boundaries, it will generally be much easier to find an _𝜀_ -valid counterfactual if the hypervolume $V_{\tilde{\mathbf{x}}}^{\epsilon}$ is larger. This intuition is depicted in Figure 3, which illustrates how the probability of finding an _𝜀_ -valid counterfactual for a 2-dimensional data point may increase with model overfitting.

To estimate $V_{\tilde{\mathbf{x}}}^{\epsilon}$, we can apply standard Monte Carlo integration, a well-established technique that uses random draws to numerically compute a definite integral. Furthermore, using Monte Carlo integration will provide valuable knowledge on the shape of a model’s decision boundary as a by-product. The estimate outlined above assumes that data points are uniformly distributed around _𝒙_ in the input space, which may be reasonable for appropriate values of _𝜀_ . Indeed, it is worth noticing that _𝒙_ can be an embedding from an autoencoding process, mapping each raw training point into a dense, lower-dimensional latent manifold within the original, high-dimensional space. More accurate estimates could be obtained by sampling the _𝜀_ -neighborhood from the manifold using advanced strategies (e.g., see Chen et al. [5]). However, this lies beyond the primary scope of this step and will be explored in future work.

Finally, if we extend the reasoning above to _all_ training points, we should observe that E[ _𝑋_<sup>¯</sup> ] = _𝑝_ ¯<sup>_𝜀_</sup> is higher for overtrained models.

### **4.4 Empirical Validation**

To investigate the impact of overfitting on _𝜀_ -VCP, we trained two Multi-Layer Perceptron (MLP) models on the Water dataset [16] for a binary classification task. Both models used the same 5-layer

305

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Countering Overfitting with Counterfactual Examples


![](assets/paper_cf-reg-2026.pdf-0005-02.png)


<!-- Start of picture text -->
— Regularizeds<br>0.8) __ piaing ver ver<br>a 06<br>g<br>wc0.4<br>5<br>3<br>=<br>02<br>0.0 0.61 0.62 0.63 0.64 0.65 0.66 0.67<br>Test Accuracy<br><!-- End of picture text -->

**Figure 4: The mean** _𝜀_ **-VCP (** _𝑦_ **-axis) vs. the model’s training accuracy (** _𝑥_ **-axis).** **_Plain_** _𝜀_ **-VCP is the “vanilla” MLP, while** **_Regularized_** _𝜀_ **-VCP is the same MLP yet with a dropout rate of** 0 _._ 5 **.**

architecture, but only one employed dropout regularization with a rate of 0 _._ 5. The models were trained over 500 epochs using the Adam optimizer with a learning rate of _𝜂_ = 0 _._ 001. The _𝜀_ -VCP was estimated through Monte Carlo integration, as discussed in Section 4.3. Specifically, it was computed as $p^{\epsilon}=V_{\tilde{\mathbf{x}}}^{\epsilon}/V_{\mathbf{x}}^{\epsilon}$, where $V_{\tilde{\mathbf{x}}}^{\epsilon}$ was approximated using 100 random samples per training point _𝒙_ .

It is important to note that the choice of _𝜀_ is inherently dependent on the characteristics of the dataset and is best determined empirically to ensure a meaningful evaluation of counterfactual validity while preserving consistency with the data distribution. As _𝜀_ defines the maximum norm of the perturbation vector applied to each instance, it delineates the feasible search space for generating counterfactuals. An overly small value may excessively constrain the perturbations, limiting the ability to capture substantive changes in model predictions. In contrast, a value that is too large can produce counterfactuals that are implausible or inconsistent with the underlying data structure. In this experiment with the Water dataset, we found that setting _𝜀_ = 1 _._ 5 provides a suitable trade-off, allowing us to capture a diverse yet interpretable range of counterfactual examples without introducing excessive modifications to the original training points.

Figure 4 illustrates the evolution of the average _𝜀_ -VCP, calculated over all training points, as a function of the models’ training accuracy. From this plot, three key insights emerge. First, the average _𝜀_ -VCP increases alongside training accuracy for both models, confirming our hypothesis that the likelihood of finding valid counterfactuals rises as models tend to overfit. Second, the plain, unregularized MLP exhibits higher _𝜀_ -VCP values, suggesting that its more complex decision boundary makes it easier to identify valid counterfactual examples. Third, the trend persists while the MLP trained with dropout regularization exhibits a less pronounced increase (i.e., smaller _𝜀_ -VCP values). This suggests that although dropout regularization smooths the decision boundary to some extent, it may not sufficiently counteract this phenomenon, leaving room for further improvement.

### **5 Counterfactual Regularization (CF-Reg) 5.1 A New Training Loss**

We exploit the correlation between overfitting and the ability to find counterfactual examples, as highlighted in the previous section, to define a new regularized training loss as follows.


![](assets/paper_cf-reg-2026.pdf-0005-09.png)


The first term (Lemp) is the standard empirical risk, while the second term (Lcf) is our proposed _counterfactual regularization_ component, with _𝛼_ ∈ R≥0 serving as a hyperparameter to weigh its contribution. More specifically, the counterfactual regularization component can be defined as follows:


![](assets/paper_cf-reg-2026.pdf-0005-11.png)


where _𝜑_ (·; _𝜀_ ) – parameterized by _𝜀_ – acts as an aggregation function applied to the set of distances _𝑑_ ( _𝒙𝑖,𝑔𝜽_ ( _𝒙𝑖_ )) between each sample _𝒙𝑖_ and its corresponding counterfactual generated by the model, _𝑔𝜽_ ( _𝒙𝑖_ ). Intuitively, the closer an instance is to its counterfactual, the greater the penalty imposed by the newly introduced loss. In other words, optimizing the objective defined in (5) aims to ensure a sufficient margin between each training point and its corresponding counterfactual. Moreover, we would like this penalty to be stronger for training points where finding a counterfactual is easier – i.e., those closer to the decision boundary. To achieve this goal, each distance _𝑑_ ( _𝒙𝑖,𝑔𝜽_ ( _𝒙𝑖_ )) can be assigned a weight _𝑤𝑖_<sup>_𝜀_that depends</sup> on _𝜀_ during aggregation. For example, this weight may be set as the _𝜀_ -VCP associated with each training instance _𝒙𝑖_ (i.e., _𝑤𝑖_<sup>_𝜀_=</sup><sup>_𝑝_</sup> _𝑖_<sup>_𝜀_).</sup> Note that, for each data point _𝒙𝑖_ , its corresponding _𝑝𝑖_<sup>_𝜀_can be</sup> estimated as described in Section 4.3. However, since _𝑝𝑖_<sup>_𝜀_depends on</sup> the shape of the decision boundary, which may evolve dynamically across training epochs, its estimation should ideally be updated at _every_ epoch. Therefore, this could introduce a significant computational overhead in the training process, which we can mitigate by updating our estimates { _𝑝𝑖_<sup>_𝜀_}</sup><sup>_𝑚_</sup> _𝑖_ =1<sup>periodically, for example, every</sup><sup>_𝑡_</sup> epochs. We conjecture that a trade-off exists between the effectiveness of the counterfactual regularization term – impacted by the accuracy of each estimate _𝑝𝑖_<sup>_𝜀_– and the computational cost of the</sup> training process. It is worth noticing that our counterfactual regularizer – hereinafter referred to as CF-Reg – is flexible enough to support any choice of aggregation function ( _𝜑_ ), distance ( _𝑑_ ), and counterfactual generator ( _𝑔𝜽_ ). However, the optimization problem in (5) can be efficiently solved using standard gradient-based methods, provided that _𝜑_ , _𝑑_ , and _𝑔𝜽_ are all differentiable with respect to _𝜽_ .

In this work, we set _𝜑_ as the mean and _𝑑_ as the Euclidean distance (i.e., the _𝐿_ 2-norm of the displacement vector resulting from the difference between the original sample and its counterfactual). For _𝑔𝜽_ , we adopt the _score counterfactual explanation_ method proposed by Wachter et al. [35], and we discuss the rationale behind this choice below. Alternative formulations of these components are possible and will be explored in future studies.

### **5.2 Counterfactual Example Generator**

A key component of CF-Reg is the counterfactual generator _𝑔𝜽_ , as this is used to compute the optimal counterfactual example for each training data point. To incorporate this step into the regularized

306

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Flavio Giorgi, Fabiano Veglianti, Fabrizio Silvestri, and Gabriele Tolomei

training process, the counterfactual generator must satisfy two essential requirements. First, it must be differentiable with respect to the predictive model weights _𝜽_ . Second, it must be highly efficient to ensure the overall feasibility of our method.

Among the various counterfactual generation approaches in the literature, we selected the _score counterfactual explanation_ method proposed by [35], which operates as follows. Let _𝒙_ ∈X be an input sample, _𝑓𝜽_ a trained model, _𝛿_ : X × X ↦→ R≥0 a distance function, _𝛽_ ∈ R≥0 a controlling hyperparameter, and _𝑠_ ∈ R a target score. Thus, the score counterfactual explanation $\tilde{\mathbf{x}}$ for _𝒙_ is the result of the following optimization problem:


![](assets/paper_cf-reg-2026.pdf-0006-04.png)


With a slight abuse of notation, in (7), we treat the output of the predictive model _𝑓𝜽_ as a continuous value, even for classification tasks. To accommodate this requirement, we can, for instance, assume access to the logits, which are then passed through the appropriate activation function, such as sigmoid or softmax.

Note that the resulting counterfactual generator satisfies the two requirements mentioned above. In particular, by carefully selecting the distance function _𝛿_ in (7), the resulting objective becomes differentiable with respect to the predictive model weights _𝜽_ . Furthermore, when using the score-based counterfactual explanation approach, determining the optimal counterfactual perturbation vector $\boldsymbol{\delta}=\mathbf{x}-\tilde{\mathbf{x}}^*=\mathbf{x}-g_{\theta}(\mathbf{x})$ – i.e., the displacement vector between the original instance and its optimal counterfactual – admits a closed-form solution under specific assumptions. Specifically, if _𝑓𝜽_ is a linear function and $\tilde{\mathbf{x}}^*=g_{\theta}(\mathbf{x})$ is the optimal counterfactual example for the input _𝒙_ , Pawelczyk et al. [27] proved that:


![](assets/paper_cf-reg-2026.pdf-0006-07.png)


where _𝑡_ = _𝑠_ − _𝑓𝜽_ ( _𝒙_ ). This makes the method highly efficient and well-suited for incorporation into our regularized training loss.

From (8), we can, therefore, compute the _𝐿_ 2-norm of the perturbation vector _𝜹𝑖_ , for each training instance _𝒙𝑖_ . This value is then used as $d(\mathbf{x}_i,\tilde{\mathbf{x}}_i^*)$, as required by the proposed regularized training loss in (6). Finally, the _𝐿_ 2-norms of all perturbation vectors are aggregated using the function _𝜑_ (·; _𝜀_ ), resulting in the following (weighted) average:


![](assets/paper_cf-reg-2026.pdf-0006-10.png)


In this work, weights are uniformly set as _𝑤𝑖_<sup>_𝜀_= 1 ∀</sup><sup>_𝑖_∈{1</sup><sup>_, . . . ,𝑚_},</sup> thus reducing the aggregation to a plain average. Alternatively, more sophisticated strategies can be used, such as the one outlined in Section 5.1, where each training point is assigned a weight corresponding to its estimated _𝜀_ -VCP, i.e., _𝑤𝑖_<sup>_𝜀_=</sup><sup>_𝑝_</sup> _𝑖_<sup>_𝜀_.</sup> Overall, this transforms our counterfactual regularized loss into:


![](assets/paper_cf-reg-2026.pdf-0006-12.png)


Finally, the objective in (10) can be solved using standard gradientbased optimization methods.

### **6 Experiments**

In this section, we evaluate the ability of the proposed counterfactual regularized loss (CF-Reg), as defined in (10), to mitigate overfitting when compared to existing regularization techniques. In Appendix B, instead, we analyze the relationship between the test loss and the counterfactual vector norm during training.

### **6.1 Experimental Setup**

**_Datasets, Models, and Tasks._** The experiments are run on four datasets: Water [16], Phoneme [6], Higgs [37], and CIFAR-10 [20]. Furthermore, we consider the following models: Logistic Regression (LR), two Multi-Layer Perceptrons (MLPsmall and MLPlarge), and _PreactResNet-18_ [12] as a representative Convolutional Neural Network (CNN) architecture. We focus on binary classification tasks and leave the extension to multiclass scenarios for future work. However, for datasets originally designed for multiclass classification, we adapt them by selecting two classes to align with our binary setting. Additional details are provided in Appendix A.1.

**_Evaluation Measures._** To characterize the degree of overfitting, we use the test loss, as it serves as a reliable indicator of the model’s generalization capability to unseen data. Additionally, we evaluate the predictive performance of each model using the test accuracy.

**_Baselines._** We compare CF-Reg with the following methods: Early Stopping, Dropout, adversarial training via well-known projected gradient descent (PGD) [25], two regularizers – i.e., L1-Reg (“Lasso”) and L2-Reg (“Ridge”) – and no regularization (No-Reg).

**_Hyperparameter Settings._** We analyze the sensitivity of CF-Reg to its hyperparameters in Section 6.3. Due to space constraints, a comprehensive discussion covering all regularization methods, including the tuning strategies adopted, is provided in Appendix C. The best selected values are summarized in Table 7.

**_Implementation Details._** To deliberately induce overfitting in logistic regression models, we apply a polynomial feature expansion that increases the input dimensionality beyond the number of training samples. This ensures that the model has sufficient capacity to memorize the training data, thereby allowing us to assess the effect of our counterfactual regularizer. The degree of the polynomial expansion is selected as the smallest value that results in a number of features exceeding the number of training instances. Note that this preprocessing step is not required for neural network models, as they are chosen to be complex enough to overfit the data.

In addition, to leverage the closed-form solution for computing the optimal perturbation vector as defined in (8), we use a local linear approximation of the model during the counterfactual generation process. Thus, given an instance _𝒙𝑖_ , we compute the (optimal) counterfactual not with respect to the original model _𝑓𝜽_ , but with respect to its first-order Taylor expansion around _𝒙𝑖_ , denoted as:


![](assets/paper_cf-reg-2026.pdf-0006-23.png)


Note that this step is unnecessary for logistic regression, as it is inherently a linear model.

We run all experiments on a machine equipped with an AMD Ryzen 9 7900 12-Core Processor and an NVIDIA GeForce RTX 4090 GPU. Our implementation is based on the PyTorch Lightning framework, and the source code for our experiments is available at

307

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Countering Overfitting with Counterfactual Examples

the following GitHub repository: https://github.com/hercolelab/CFReg. Further details are described in Appendix A.2.

### **6.2 Effectiveness of CF-Reg**

We compare the performance of CF-Reg against the baselines indicated in Section 6.1. For each model and dataset combination, Table 1 shows the mean value and standard deviation of test accuracy achieved by each method across 5 random initializations. From the results in Table 1, the following key insights can be drawn.

**_General Validity of CF-Reg._** Across the board, CF-Reg demonstrates strong performance, particularly on tabular datasets such as Water, Phoneme, and Higgs. In many configurations, it either matches or outperforms all other baselines, and in several cases, the improvements are statistically significant. This supports the core hypothesis behind CF-Reg: that training with informative counterfactual examples can improve generalization by encouraging decision boundary robustness in data-relevant directions.

**_Comparison with other Regularization Techniques._** CF-Reg consistently outperforms traditional penalty-based regularizers like L1-Reg and L2-Reg. These methods penalize model complexity indirectly through weight constraints, whereas CF-Reg directly encourages decision-level stability, which appears more effective in preserving model generalization. Moreover, CF-Reg performs on par with or better than implicit regularization methods such as early stopping and dropout. Notably, in cases where CF-Reg underperforms slightly, it still retains a critical advantage: it leverages the full expressive capacity of the architecture, rather than curtailing it through early termination of training or by randomly omitting connections during forward passes. This is particularly relevant for modern architectures where expressiveness is key to capturing subtle data patterns. When compared to adversarial training (PGD), CF-Reg also shows almost always superior or comparable accuracy.

**_Handling Complex Input Domains._** On the CIFAR-10 dataset, CF-Reg does not outperform traditional regularizers. In fact, in this context, the No-Reg baseline performs the best, suggesting that overfitting is less of a concern, perhaps due to the indirect regularizing effect of convolutional architectures. Additionally, the current counterfactual generation strategy appears less effective for image data, where generating meaningful perturbations is substantially harder. This points to a promising direction for future work: using more expressive and domain-aware counterfactual generators tailored to high-dimensional, unstructured inputs, in order to fully extend the applicability of CF-Reg to complex data.

### **6.3 Hyperparameter Sensitivity Analysis**

CF-Reg relies on two key hyperparameters: _𝛼_ and _𝛽_ . The former is intrinsic to the loss formulation defined in (2), while the latter is closely tied to the choice of the score-based counterfactual explanation method used.

Figure 5 illustrates how the test accuracy of an MLP trained on the Water dataset changes for different combinations of _𝛼_ and _𝛽_ .

We observe that, for a fixed _𝛽_ , increasing the weight of our counterfactual regularizer ( _𝛼_ ) can slightly improve test accuracy until a sharp drop occurs for _𝛼 >_ 0 _._ 1. This behavior is expected, as the impact of CF-Reg, like any regularization term, can be disruptive


![](assets/paper_cf-reg-2026.pdf-0007-12.png)


<!-- Start of picture text -->
0.65, <p<br>>.0.60, .<br>g<br>5 0.55 \<br>g \<br>050) peor<br>2 =<br>as) B=O5 \<br>spel<br>40; + B=1.5 \<br>10 10 a (logi0* scale) 0 10°<br><!-- End of picture text -->

**Figure 5: The test accuracy of an MLP trained on the Water dataset, evaluated while varying the weight of our counterfactual regularizer (** _𝛼_ **) for different values of** _𝛽_ **.**

if not properly calibrated. Moreover, this finding confirms that CFReg is inherently data-driven and, thus, requires specific fine-tuning based on the combination of the model and dataset at hand.

The best values for _𝛼_ and _𝛽_ are shown in Table 7 (Appendix C).

### **6.4 Comparison of Weighting Schemes**

In our current implementation, we assign all training instances equal importance ( _𝑤𝑖_<sup>_𝜀_= 1</sup><sup>_,_∀</sup><sup>_𝑖_). While simple, this uniform weighting</sup> may limit the full potential of CF-Reg. Adopting a more fine-grained weighting strategy could better balance the regularization strength across samples, albeit at the cost of increased training complexity. To this end, in this section, we present the results of a comparison among three different weighting schemes. The first scheme is the uniform weighting adopted to produce the results in Table 1. The second scheme weights each data point according to its _𝜀_ -VCP value. The third scheme, denoted as TPTN, assigns zero weight to misclassified samples in the regularization term.

The results reported in Table 3 indicate that, within our smallscale experimental setting, more complex weighting strategies do not yield a clear advantage over simple uniform weighting.

**Table 3: Mean and standard deviation of test accuracy over 5 random initializations for each combination of model, dataset, and weighting scheme.**

|**Model**|**Dataset**|**Uniform**|_𝜀_**-VCP**|**TPTN**|
|---|---|---|---|---|
|LR|Water|0_._6915±0_._0017|0_._6345±0_._0091|0_._6902±0_._0029|
|MLPsmall|Water|0_._6796±0_._0045|0_._6195±0_._0219|0_._6716±0_._0154|
|MLPlarge|Water|0_._6787±0_._0092|0_._6110±0_._0234|0_._6601±0_._0248|
|LR|Phoneme|0_._8764±0_._0084|0_._8792±0_._0059|0_._7874±0_._0048|
|MLPsmall|Phoneme|0_._9005±0_._0065|0_._9031±0_._0045|0_._8982±0_._0073|
|MLPlarge|Phoneme|0_._9149±0_._0024|0_._9016±0_._0091|0_._9062±0_._0055|
|MLPsmall|Higgs|0_._7245±0_._0057|0_._7258±0_._0036|0_._7248±0_._0040|
|MLPlarge|Higgs|0_._7278±0_._0027|0_._6931±0_._0041|0_._7272±0_._0031|



### **7 Discussion**

### **7.1 Feasibility of CF-Reg**

As with any regularizer, CF-Reg introduces some computational overhead in exchange for improved model generalization. Specifically, the extra cost stems from the need to compute a counterfactual

308

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Flavio Giorgi, Fabiano Veglianti, Fabrizio Silvestri, and Gabriele Tolomei

**Table 1: Mean and standard deviation of test accuracy over 5 random initializations for each combination of model, dataset, and regularization method. Best results are shown in bold; results that are statistically significantly better than the second-best (at the** _𝛼_ = 0 _._ 05 **significance level) are marked with a**<sup>_★_</sup> **.**

|**Model**|**Dataset**|**No-Reg**|**L1-Reg**|**L2-Reg**|**Dropout**|**Early Stopping**|**PGD**|**CF-Reg (ours)**|
|---|---|---|---|---|---|---|---|---|
|LR|Water|0_._6030±0_._0053|0_._6652±0_._0053|0_._6677±0_._0114|N/A|0_._6098±0_._0000|0_._6384±0_._0183|0_._6915±0_._0017<sup>_★_</sup>|
|MLPsmall|Water|0_._6128±0_._0103|0_._6098±0_._0000|0_._6759±0_._0065|0_._6515±0_._0100|0_._6765±0_._0059|0_._6524±0_._0011|0_._6796±0_._0045|
|MLPlarge|Water|0_._6168±0_._0063|0_._6098±0_._0000|0_._6320±0_._0158|0_._6564±0_._0104|0_._6573±0_._0112|0_._6464±0_._0053|0_._6787±0_._0092<sup>_★_</sup>|
|LR|Phoneme|0_._8729±0_._0052|0_._8157±0_._0036|0_._8427±0_._0078|N/A|0_._8622±0_._0109|0_._7353±0_._0006|0_._8764±0_._0084|
|MLPsmall|Phoneme|0_._9016±0_._0088|0_._8511±0_._0092|0_._7963±0_._0041|0_._9016±0_._0059|0_._8957±0_._0105|0_._8915±0_._0029|0_._9005±0_._0065|
|MLPlarge|Phoneme|0_._9101±0_._0026|0_._7068±0_._0000|0_._8735±0_._0042|0_._9099±0_._0078|0_._9066±0_._0083|0_._9021±0_._0021|0_._9149±0_._0024<sup>_★_</sup>|
|MLPsmall|Higgs|0_._7204±0_._0043|0_._4706±0_._0000|0_._7231±0_._0033|0_._7210±0_._0016|0_._7271±0_._0049|0_._7334**±**0_._0025<sup>**_★_**</sup>|0_._7245±0_._0057|
|MLPlarge|Higgs|0_._6904±0_._0020|0_._4706±0_._0000|0_._7223±0_._0056|0_._7323±0_._0039|0_._7149±0_._0043|0_._6995±0_._0018|0_._7278±0_._0027|
|CNN|CIFAR-10|0_._8415±0_._0059|0_._8355±0_._0160|0_._8408±0_._0035|N/A|0_._8413±0_._0008|0_._7071±0_._0316|0_._8388±0_._0106|



**Table 2: Mean and standard deviation of training time (in seconds) over 5 independent runs. Each value refers to the training process for the corresponding entry in Table 1.**

|**Model**|**Dataset**|**No-Reg**|**L1-Reg**|**L2-Reg**|**Dropout**|**Early Stopping**|**PGD**|**CF-Reg (ours)**|
|---|---|---|---|---|---|---|---|---|
|LR|Water|19_._86±0_._51|20_._87±0_._33|21_._06±0_._29|N/A|0_._46±0_._11|119_._23±0_._83|21_._78±0_._54|
|MLPsmall|Water|19_._78±0_._21|22_._47±0_._47|22_._60±0_._41|21_._20±0_._26|1_._37±0_._49|120_._31±0_._05|23_._07±0_._28|
|MLPlarge|Water|22_._94±0_._37|26_._25±0_._18|27_._21±0_._42|25_._88±0_._45|0_._76±0_._10|157_._83±0_._05|27_._48±0_._29|
|LR|Phoneme|29_._54±0_._40|32_._25±0_._68|32_._22±0_._23|N/A|20_._40±3_._27|128_._67±0_._05|33_._84±0_._37|
|MLPsmall|Phoneme|31_._02±0_._56|34_._90±0_._35|35_._55±0_._72|33_._12±0_._18|31_._33±0_._07|565_._60±1_._67|36_._60±0_._72|
|MLPlarge|Phoneme|35_._66±0_._60|41_._27±0_._99|42_._60±0_._59|40_._25±0_._70|20_._95±0_._70|253_._80±0_._83|43_._95±0_._56|
|MLPsmall|Higgs|415_._16±4_._70|470_._94±8_._46|485_._45±8_._22|448_._73±5_._04|156_._89±7_._03|459_._40±1_._67|506_._11±5_._73|
|MLPlarge|Higgs|486_._08±5_._35|571_._48±10_._70|593_._64±8_._38|545_._84±23_._19|29_._38±2_._73|584_._10±1_._41|613_._39±10_._71|
|CNN|CIFAR-10|377_._47±1_._66|401_._37±1_._94|404_._53±3_._54|N/A|318_._19±2_._20|1304_._40±5_._62|1294_._23±3_._88|



example _for each_ training instance during learning. Since CF-Reg is compatible with any counterfactual generator, the actual overhead depends on the complexity of the generator used.

Indeed, more advanced counterfactual generators may yield more effective regularization but require longer computation times. Conversely, simpler generators, such as the score-based model employed in this study, offer efficient training at the potential cost of regularization quality. We analyze this trade-off in greater depth in Section 7.3.

We quantify the cost of CF-Reg by evaluating its impact on model training time. Specifically, Table 2 reports the mean and standard deviation of training time for each model-dataset pair presented in Table 1. We observe that CF-Reg introduces only a modest computational overhead when employing the score-based generator. However, on larger datasets, the need to compute counterfactual distances for every training point leads to increased training time, as expected. Interestingly, the number of model parameters does not significantly affect the training time. Instead, input dimensionality plays a more substantial role, especially for nonlinear models. For example, in CIFAR-10, gradients for local linearization must be computed in a high-dimensional space, R<sup>3×32×32</sup> , which contributes considerably to the increased training cost.

### **7.2 Counterfactual Explanations as a By-Product**

While CF-Reg introduces some computational overhead and does not always significantly outperform all baselines, it offers a unique advantage not provided by traditional regularizers: the generation

of counterfactual explanations as a natural by-product of training. These explanations, typically computed through separate and often costly post hoc procedures [5, 26], are instead amortized over training with CF-Reg, yielding improved generalization, possibly without additional inference cost.

At test time, given a new input _𝒙_ new, approximate counterfactual explanations for the prediction _𝑓𝜽_ ( _𝒙_ new) can be efficiently retrieved by: ( _𝑖_ ) identifying the _𝑘_ nearest training instances to _𝒙_ new, and ( _𝑖𝑖_ ) returning their precomputed counterfactual examples via a simple lookup, which takes constant time ( _𝑂_ (1)) per instance.

### **7.3 Main Limitations and Future Improvements**

In this section, we discuss the main limitations of CF-Reg and outline directions for future improvements. Our method was designed to be general and efficient; however, some design choices, while practical, may limit performance in certain settings. Below, we sketch the key areas that are worth investigating.

**_Efficiency vs. Regularization Trade-off._** As introduced in Section 5.1, our framework supports _any_ counterfactual generator _𝑔𝜽_ , but this flexibility introduces variability in computational cost. When using lightweight generators (e.g., score-based), training remains fast, but the regularization may be less effective. In contrast, more expressive generators could improve generalization at the expense of longer training times. Exploring this trade-off and the use of more sophisticated counterfactual generators is a promising avenue for future research.

To improve the feasibility of CF-Reg, we plan to investigate the following strategies: ( _𝑖_ ) Cache and update counterfactuals every

309

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Countering Overfitting with Counterfactual Examples

_𝑡_ epochs instead of at each iteration; ( _𝑖𝑖_ ) Cluster training points and generate one counterfactual per cluster rather than per sample; ( _𝑖𝑖𝑖_ ) Perform counterfactual search only for a selected subset of influential training points, identified via random sampling or heuristic criteria.

**_Linear Approximation._** Even when using the score-based generator, we do not fully exploit the closed-form solution to compute the optimal perturbation vector in (8), as it assumes _𝑓𝜽_ to be a linear model, which generally does not hold for deep neural networks. Instead, we adopt the first-order Taylor approximation in (11), which may result in suboptimal counterfactuals due to its limited ability to capture the model’s nonlinear behavior.

**_Counterfactual Generator Learning._** In this work, we treat the counterfactual generator _𝑔𝜽_ as a fixed component, queried during the regularized training of the primary model _𝑓𝜽_ . A promising direction for future research is to integrate the learning of _𝑔𝜽_ directly into the training process, thereby formulating the task as a bilevel optimization problem. Solving this problem would allow for the joint learning of both the predictive model _𝑓𝜽_ and its associated counterfactual generator _𝑔𝜽_ .

### **8 Conclusion**

We introduced and analyzed the trade-off between the generalizability and explainability of predictive models, highlighting their often conflicting nature. Specifically, based on well-known theoretical results in margin theory, we demonstrated that the degree of model overfitting is positively correlated with its ability to generate counterfactual examples. Building on this insight, we proposed CF-Reg, a novel regularization technique that integrates a counterfactual regularization term into the training objective, to balance between predictive performance and interpretability.

Through extensive experiments across multiple datasets and model architectures, we showed that CF-Reg generally outperforms existing regularization techniques, improving generalization while simultaneously generating meaningful counterfactual explanations. Our results suggest that counterfactual-based regularization can serve as a principled approach to improving model robustness without sacrificing interpretability.

Finally, we outlined promising directions for future work, primarily aimed at improving the efficiency of our method.

### **Acknowledgments**

This work was partially supported by the following projects: FAIR (PE0000013) and SERICS (PE00000014), funded under the National Recovery and Resilience Plan by the European Union - NextGenerationEU; HypeKG – Hybrid Prediction and Explanation with Knowledge Graphs (2022Y34XNM) and NEREO – Neural Reasoning Over Open Data (2022AEFHA), funded by the Italian Ministry of University and Research under the PRIN 2022 program; GHOST – Protecting User Privacy from Community Detection in Social Networks (B83C24007070005) and SEEDS – Sustainable Ecosystems in Evolving Digital Societies, funded by Sapienza University of Rome through the “Progetti di Ricerca Grandi” and “Progetti Dipartimentali” programs, respectively.

### **References**

- [1] Tom B Brown, Nicholas Carlini, Chiyuan Zhang, Catherine Olsson, Paul Christiano, and Ian Goodfellow. 2018. Unrestricted Adversarial Examples. _arXiv preprint arXiv:1809.08352_ (2018).

- [2] Rich Caruana, Steve Lawrence, and C. Giles. 2000. Overfitting in Neural Nets: Backpropagation, Conjugate Gradient, and Early Stopping. In _Advances in Neural Information Processing Systems_ , T. Leen, T. Dietterich, and V. Tresp (Eds.), Vol. 13. MIT Press, 381–387. https://proceedings.neurips.cc/paper_files/paper/2000/file/ 059fdcd96baeb75112f09fa1dcc740cc-Paper.pdf

- [3] Ziheng Chen, Jin Huang, Fabrizio Silvestri, Yongfeng Zhang, Hongshik Ahn, and Gabriele Tolomei. 2025. Joint Factual and Counterfactual Explanations for Top- _𝑘_ GNN-based Recommendations. _ACM Trans. Recomm. Syst._ (May 2025). https://doi.org/10.1145/3731683 Just Accepted.

- [4] Ziheng Chen, Fabrizio Silvestri, Gabriele Tolomei, Jia Wang, He Zhu, and Hongshik Ahn. 2024. Explain the Explainer: Interpreting Model-Agnostic Counterfactual Explanations of a Deep Reinforcement Learning Agent. _IEEE Transactions on Artificial Intelligence_ 5, 4 (2024), 1443–1457. https://doi.org/10.1109/TAI.2022. 3223892

- [5] Ziheng Chen, Fabrizio Silvestri, Jia Wang, He Zhu, Hongshik Ahn, and Gabriele Tolomei. 2022. ReLAX: Reinforcement Learning Agent Explainer for Arbitrary Predictive Models. In _Proceedings of the 31st ACM International Conference on Information & Knowledge Management_ (Atlanta, GA, USA) _(CIKM ’22)_ . Association for Computing Machinery, New York, NY, USA, 252–261. https: //doi.org/10.1145/3511808.3557429

- [6] Thomson-Sintra Dominique Van Cappel. 1993. Phoneme. https: //www.openml.org/search?type=data&sort=version&status=any&order= asc&exact_name=phoneme&id=1489.

- [7] Timo Freiesleben. 2022. The Intriguing Relation Between Counterfactual Explanations and Adversarial Examples. _Minds and Machines_ 32, 1 (mar 2022), 77–109. https://doi.org/10.1007/s11023-021-09580-9

- [8] Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. 2016. Domain-Adversarial Training of Neural Networks. _Journal of Machine Learning Research_ 17, 1 (jan 2016), 2096–2030.

- [9] Flavio Giorgi, Cesare Campagnano, Fabrizio Silvestri, and Gabriele Tolomei. 2025. Natural Language Counterfactual Explanations for Graphs Using Large Language Models. In _Proceedings of The 28th International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research, Vol. 258)_ , Yingzhen Li, Stephan Mandt, Shipra Agrawal, and Emtiyaz Khan (Eds.). PMLR, 3565–3573. https://proceedings.mlr.press/v258/giorgi25a.html

- [10] Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri, Dino Pedreschi, Franco Turini, and Fosca Giannotti. 2018. Local Rule-Based Explanations of Black Box Decision Systems. _arXiv preprint arXiv:1805.10820_ (2018).

- [11] Suriya Gunasekar, Jason D. Lee, Daniel Soudry, and Nathan Srebro. 2018. Implicit Bias of Gradient Descent on Linear Convolutional Networks. In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ (Montréal, Canada) _(NeurIPS ’18)_ . Curran Associates Inc., Red Hook, NY, USA, 9482–9491.

- [12] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016. Identity Mappings in Deep Residual Networks. In _Computer Vision – ECCV 2016_ , Bastian Leibe, Jiri Matas, Nicu Sebe, and Max Welling (Eds.). Springer International Publishing, Cham, 630–645.

- [13] Zecheng He, Tianwei Zhang, and Ruby B. Lee. 2019. Model inversion attacks against collaborative inference. In _Proceedings of the 35th Annual Computer Security Applications Conference_ (San Juan, Puerto Rico, USA) _(ACSAC ’19)_ . Association for Computing Machinery, New York, NY, USA, 148–162. https://doi.org/10.1145/3359789.3359824

- [14] R. Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchildon, Karan Grewal, Philip Bachman, Adam Trischler, and Yoshua Bengio. 2019. Learning Deep Representations by Mutual Information Estimation and Maximization. In _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_ . OpenReview.net. https://openreview.net/forum?id=Bklr3j0cKX

- [15] Ziwei Ji and Matus Telgarsky. 2019. Gradient Descent Aligns the Layers of Deep Linear Networks. In _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_ . OpenReview.net. https:// openreview.net/forum?id=HJflg30qKX

- [16] Aditya Kadiwal. 2020. Water Potability Dataset. https://www.kaggle.com/ datasets/adityakadiwal/water-potability Accessed: 2025-01-27.

- [17] Amir-Hossein Karimi, Gilles Barthe, Borja Balle, and Isabel Valera. 2020. ModelAgnostic Counterfactual Explanations for Consequential Decisions. In _International Conference on Artificial Intelligence and Statistics_ . PMLR, 895–905.

- [18] G.N. Karystinos and D.A. Pados. 2000. On Overfitting, Generalization, and Randomly Expanded Training Sets. _IEEE Transactions on Neural Networks_ 11, 5 (2000), 1050–1057. https://doi.org/10.1109/72.870038

- [19] V. Koltchinskii and D. Panchenko. 2002. Empirical Margin Distributions and Bounding the Generalization Error of Combined Classifiers. _The Annals of Statistics_ 30, 1 (2002), 1–50. http://www.jstor.org/stable/2700001

- [20] Alex Krizhevsky. 2009. Learning Multiple Layers of Features from Tiny Images. (2009), 32–33. https://www.cs.toronto.edu/~kriz/learning-features-2009-TR.pdf

310

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Flavio Giorgi, Fabiano Veglianti, Fabrizio Silvestri, and Gabriele Tolomei

- [21] Thai Le, Suhang Wang, and Dongwon Lee. 2020. GRACE: Generating Concise and Informative Contrastive Sample to Explain Neural Network Model’s Prediction. In _Proceedings of the 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ (Virtual Event, CA, USA) _(KDD ’20)_ . Association for Computing Machinery, New York, NY, USA, 238–248. https://doi.org/10.1145/3394486.3403066

- [22] Romain Lopez, Adam Gayoso, and Nir Yosef. 2020. Enhancing Scientific Discoveries in Molecular Biology with Deep Generative Models. _Molecular Systems Biology_ 16, 9 (2020), e9198. https://doi.org/10.15252/msb.20199198 arXiv:https://www.embopress.org/doi/pdf/10.15252/msb.20199198

- [23] Ana Lucic, Harrie Oosterhuis, Hinda Haned, and Maarten de Rijke. 2022. FOCUS: Flexible Optimizable Counterfactual Explanations for Tree Ensembles. In _Proceedings of the AAAI conference on artificial intelligence_ , Vol. 36. 5313–5322.

- [24] Ana Lucic, Maartje A. Ter Hoeve, Gabriele Tolomei, Maarten De Rijke, and Fabrizio Silvestri. 2022. CF-GNNExplainer: Counterfactual Explanations for Graph Neural Networks. In _Proceedings of The 25th International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research, Vol. 151)_ , Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera (Eds.). PMLR, 4499–4511. https://proceedings.mlr.press/v151/lucic22a.html

- [25] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. 2018. Towards Deep Learning Models Resistant to Adversarial Attacks. In _International Conference on Learning Representations_ . https: //openreview.net/forum?id=rJzIBfZAb

- [26] Maria Movin, Federico Siciliano, Rui Ferreira, Fabrizio Silvestri, and Gabriele Tolomei. 2025. Consistent Counterfactual Explanations via Anomaly Control and Data Coherence. _IEEE Transactions on Artificial Intelligence_ 6, 4 (2025), 794–804. https://doi.org/10.1109/TAI.2024.3496616

- [27] Martin Pawelczyk, Chirag Agarwal, Shalmali Joshi, Sohini Upadhyay, and Himabindu Lakkaraju. 2022. Exploring Counterfactual Explanations Through the Lens of Adversarial Examples: A Theoretical and Empirical Analysis . In _Proceedings of The 25th International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research, Vol. 151)_ , Gustau CampsValls, Francisco J. R. Ruiz, and Isabel Valera (Eds.). PMLR, 4574–4594. https: //proceedings.mlr.press/v151/pawelczyk22a.html

- [28] Garvesh Raskutti, Martin J. Wainwright, and Bin Yu. 2011. Early Stopping for Non-Parametric Regression: An Optimal Data-Dependent Stopping Rule. In _2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ . 1318–1325. https://doi.org/10.1109/Allerton.2011.6120320

_Learn. Res._ 19, 1 (Jan. 2018), 2822–2878.

   - [30] Ilia Stepin, Jose M Alonso, Alejandro Catala, and Martín Pereira-Fariña. 2021. A Survey of Contrastive and Counterfactual Explanation Generation Methods for Explainable Artificial Intelligence. _IEEE Access_ 9 (2021), 11974–12001.

   - [31] David Stutz, Matthias Hein, and Bernt Schiele. 2019. Disentangling Adversarial Robustness and Generalization. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ . IEEE, 6976–6987. https://doi. org/10.1109/CVPR.2019.00714

   - [32] Yi Sun, Xiaogang Wang, and Xiaoou Tang. 2014. Deep Learning Face Representation from Predicting 10,000 Classes. In _2014 IEEE Conference on Computer Vision and Pattern Recognition_ . 1891–1898. https://doi.org/10.1109/CVPR.2014.244

   - [33] Gabriele Tolomei and Fabrizio Silvestri. 2021. Generating Actionable Interpretations from Ensembles of Decision Trees. _IEEE Transactions on Knowledge and Data Engineering_ 33, 4 (2021), 1540–1553. https://doi.org/10.1109/TKDE.2019.2945326

   - [34] Gabriele Tolomei, Fabrizio Silvestri, Andrew Haines, and Mounia Lalmas. 2017. Interpretable Predictions of Tree-based Ensembles via Actionable Feature Tweaking. In _Proceedings of the 23rd ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD ’17)_ . Association for Computing Machinery, New York, NY, USA, 465–474. https://doi.org/10.1145/3097983.3098039

   - [35] Sandra Wachter, Brent Mittelstadt, and Chris Russell. 2017. Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR. _Harvard Journal of Law & Technology._ 31 (2017), 841–887.

   - [36] David Warde-Farley, Ian J. Goodfellow, Aaron C. Courville, and Yoshua Bengio. 2014. An Empirical Analysis of Dropout in Piecewise Linear Networks. In _2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings_ , Yoshua Bengio and Yann LeCun (Eds.). http://arxiv.org/abs/1312.6197

   - [37] Daniel Whiteson. 2014. HIGGS. UCI Machine Learning Repository. DOI: https://doi.org/10.24432/C5V312.

   - [38] Kaiwen Wu and Yaoliang Yu. 2019. Understanding Adversarial Robustness: The Trade-off between Minimum and Average Margin. arXiv:1907.11780 [cs.LG] https://arxiv.org/abs/1907.11780

   - [39] Kevin Y. Yip and Mark Gerstein. 2008. Training Set Expansion: An Approach to Improving the Reconstruction of Biological Networks from Limited and Uneven Reliable Interactions. _Bioinformatics_ 25, 2 (11 2008), 243–250. https://doi.org/10.1093/ bioinformatics/btn602 arXiv:https://academic.oup.com/bioinformatics/articlepdf/25/2/243/48983145/bioinformatics_25_2_243.pdf

- [29] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. 2018. The Implicit Bias of Gradient Descent on Separable Data. _J. Mach._

311

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Countering Overfitting with Counterfactual Examples

**Table 4: Main properties and description of the datasets.**

|**Dataset**|**#Samples **|**#Features **|**#Min. Class (%)**|**#Maj. Class (%)**|**Description**|
|---|---|---|---|---|---|
|Water|3,276|9|1,278 (39%)|1,998 (61%)|This tabular dataset includes various water quality metrics and<br>is used to predict water potability, i.e., whether it is safe for<br>human consumption.|
|Phoneme|5,404|5|1,586 (29%)|3,818 (71%)|This tabular dataset contains five attributes selected to charac-<br>terize each vowel, with the goal of distinguishing between nasal<br>and oral sounds.|
|Higgs|200,000|28|94,131 (47%)|105,869 (53%)|This dataset is a random sample without replacement of the<br>originalHiggstabular dataset, comprising 18% of the total 1.1<br>million instances, and is used to distinguish between a signal<br>process that produces Higgs bosons and a background process<br>that does not.|
|CIFAR-10|12,000|3×32×32|6,000 (50%)|6,000 (50%)|This dataset is a sample of the originalCIFAR-10image dataset,<br>adapted to a binary classification setting, containing only in-<br>stances from class 3 (“cats”) and class 5 (“dogs”).|



### **A Additional Experimental Details**

### **A.1 Datasets, Models, and Tasks**

Three of the four datasets used in this study, namely Water, Phoneme, and Higgs, are tabular, while the fourth, CIFAR-10, is a popular image dataset. Table 4 summarizes key characteristics of each dataset, including the number of samples, number of features, class distribution (minority and majority class sizes), and a brief description.

All datasets except CIFAR-10 are naturally associated with a binary classification task. To adapt CIFAR-10 to a binary classification setting, we retain only instances from class 3 (“cats”) and class 5 (“dogs”).

For the Water, Phoneme, and Higgs datasets, we performed an 80/20 train-test split. For CIFAR-10, we used the standard train-test split provided by the torchvision library.

Table 5 summarizes the key characteristics of the models evaluated in our experiments. The selection covers a broad spectrum of architectures, from simple logistic regression models with a few thousand parameters to deep neural networks comprising tens of millions of parameters.

**Table 5: Comparison of various models across datasets, layer configurations, and parameter counts.**

|**Model**|**Dataset**|**Layers Width**|**#Parameters**|
|---|---|---|---|
|LR|Water|N/A|5,005|
|MLPsmall|Water|[100, 30]|3,930|
|MLPlarge|Water|[150, 1000, 150, 30]|305,880|
|LR|Phoneme|N/A|4,368|
|MLPsmall|Phoneme|[100, 40]|4,540|
|MLPlarge|Phoneme|[150, 1000, 150, 30]|305,280|
|MLPsmall|Higgs|[100, 30]|5,830|
|MLPlarge|Higgs|[150, 1000, 150, 30]|308,730|
|CNN|CIFAR-10|ResNet-18|11,200,000|



### **A.2 Training Settings**

Table 6 illustrates the training settings used for each dataset. We adopt Adam as optimizer due to its faster convergence properties. This choice enables us to reduce the number of training epochs while still performing an exhaustive hyperparameter search within the same computational budget.

To illustrate Adam’s faster convergence in practice, Figure 6 compares its performance to standard stochastic gradient descent (SGD) when training an MLP on the Higgs dataset.

**Table 6: Training settings for each dataset.**

|**Dataset**|**Optimizer**|**#Epochs**|**Batch Size**|**Learning Rate**(_𝜂_)|
|---|---|---|---|---|
|Water|Adam|2,000|128|0_._001|
|Phoneme|Adam|2,000|128|0_._001|
|Higgs|Adam|200|128|0_._001|
|CIFAR-10|Adam|200|128|0_._001|



Training and testing are performed over 2,000 epochs for the Water and Phoneme datasets, and over 200 epochs for both CIFAR-10 and Higgs. In all cases, we use a batch size of 128, and we set the learning rate to _𝜂_ = 0 _._ 001 with no weight decay.

### **B Counterfactual Perturbation vs. Overfitting**

In Section 4.4, we empirically demonstrated that the average _𝜀_ - VCP is correlated with the risk of overfitting: specifically, higher training accuracy tends to correspond to a larger average _𝜀_ -VCP. That analysis provided a general observation, with the average _𝜀_ -VCP estimated using Monte Carlo integration.

In this section, instead, we conduct a more targeted analysis by examining the relationship between the test loss (i.e., the complement of test accuracy) and the average _𝐿_ 2-norm of the counterfactual perturbation vectors (|| _𝜹_ ||) over the course of training. The latter serves as a practical proxy for the average _𝜀_ -VCP.

312

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Flavio Giorgi, Fabiano Veglianti, Fabrizio Silvestri, and Gabriele Tolomei

**Table 7: Hyperparameter settings used to generate the results in Table 1. L1-Reg and L2-Reg report the regularization coefficients, i.e., the weights of the** _𝐿_ 1 **and** _𝐿_ 2 **norms of the model parameters, respectively. Dropout indicates the dropout probability. Early Stopping shows the patience parameter. PGD reports: the step size of the adversarial attack (** _𝛼_ **); the maximum perturbation budget (** _𝜖_ **); and the number of attack iterations (** _𝑘_ **). Lastly, CF-Reg represents the regularization coefficients** _𝛼_ **and** _𝛽_ **.**

|**Model**|**Dataset**|**L1-Reg**|**L2-Reg**|**Dropout**|**Early Stopping**|**PGD**|**CF-Reg (ours)**|
|---|---|---|---|---|---|---|---|
|LR|Water|4_._933_𝑒_-02|7_._413_𝑒_-01|N/A|5|1_._076_𝑒_-02/1_._128_𝑒_-02/15|3_._353_𝑒_-01/9_._816_𝑒_-01|
|MLPsmall|Water|1_._280_𝑒_-02|2_._920_𝑒_-03|2_._004_𝑒_-01|15|1_._364_𝑒_-01/4_._714_𝑒_-02/05|8_._325_𝑒_-01/1_._886_𝑒_+00|
|MLPlarge|Water|1_._605_𝑒_-02|2_._613_𝑒_-03|8_._192_𝑒_-01|10|9_._430_𝑒_-01/1_._614_𝑒_-02/05|1_._121_𝑒_+00/2_._118_𝑒_+00|
|LR|Phoneme|1_._796_𝑒_-02|3_._659_𝑒_-02|N/A|260|1_._543_𝑒_-02/6_._009_𝑒_-03/05|1_._303_𝑒_-05/3_._461_𝑒_-02|
|MLPsmall|Phoneme|1_._097_𝑒_-03|6_._972_𝑒_-03|1_._606_𝑒_-01|280|1_._100_𝑒_-02/9_._069_𝑒_-02/20|1_._485_𝑒_-02/1_._883_𝑒_-01|
|MLPlarge|Phoneme|5_._885_𝑒_-03|3_._003_𝑒_-03|1_._001_𝑒_-02|260|1_._044_𝑒_-02/7_._132_𝑒_-03/05|5_._539_𝑒_-03/1_._797_𝑒_-01|
|MLPsmall|Higgs|6_._667_𝑒_-03|3_._214_𝑒_-04|9_._820_𝑒_-02|50|3_._099_𝑒_-02/2_._153_𝑒_-02/05|1_._097_𝑒_-01/4_._724_𝑒_-01|
|MLPlarge|Higgs|1_._391_𝑒_-02|1_._675_𝑒_-04|3_._918_𝑒_-01|5|1_._422_𝑒_-02/8_._403_𝑒_-02/05|4_._380_𝑒_-01/2_._289_𝑒_+00|
|CNN|CIFAR-10|8_._700_𝑒_-06|4_._868_𝑒_-06|N/A|160|3_._755_𝑒_-01/5_._043_𝑒_-03/07|7_._246_𝑒_-04/1_._852_𝑒_-01|




![](assets/paper_cf-reg-2026.pdf-0012-04.png)


<!-- Start of picture text -->
07<br>— sGD<br>0.6 —— Adam<br>ges |<br>Soa |<br>3Zo3\_|£03<br>£ |<br>Fo2 |<br>\<br>o1;<br>\= Oo<br>0.0 ae|<br>0250500750 100012501500 1750 2000<br>Epochs<br><!-- End of picture text -->

**Figure 6: The training loss evolution over training epochs for an MLP trained on the Higgs dataset without regularization with SGD (blue) or Adam (orange) as optimizer. Adam shows a faster fit to training data in terms of training epochs.**

~~—~~ <u>to overfit the data (evidenced by an increase in test loss). Notably,</u> || _𝜹_ || begins to decrease, which aligns with the hypothesis that the average distance to the optimal counterfactual example gets smaller as the model’s decision boundary becomes increasingly adherent to the training data.

It is worth noticing that this trend is heavily influenced by the choice of the counterfactual generator model. In particular, the relationship between || _𝜹_ || and the degree of overfitting may become even more pronounced when leveraging more accurate counterfactual generators. However, these models often come at the cost of higher computational complexity, and their exploration is left to future work.

Nonetheless, we expect that || _𝜹_ || will eventually stabilize at a plateau, as the average _𝐿_ 2-norm of the optimal counterfactual perturbations cannot vanish to zero.

### **C Hyperparameter Tuning**

Figure 7 illustrates the evolution of || _𝜹_ || and the test loss over training epochs for an MLP trained without regularization on the Water dataset. The plot shows a clear trend as the model starts


![](assets/paper_cf-reg-2026.pdf-0012-11.png)


<!-- Start of picture text -->
0.07 — é<br>008 Test Loss |<br>0.05<br>[e004 “3<br>0.03 1.02<br>0.02 .<br>0.01<br>0.00, ‘0 1000 2000- 3000 4000-- 5000- 6000-- 7000-- 8000beaig<br>Epochs<br><!-- End of picture text -->

Most regularization techniques are highly sensitive to hyperparameter choices. Table 7 summarizes all hyperparameters used in this study. Each value was selected via random Bayesian optimization over approximately 80 trials, aiming to maximize accuracy on a held-out validation set.

In the table, L1-Reg and L2-Reg refer to the coefficients of the respective regularization terms, i.e., the weights of the _𝐿_ 1 and _𝐿_ 2 norms of the model parameters. The Dropout entry indicates the dropout probability applied within the model architecture. For Early Stopping, the reported value corresponds to the patience parameter, namely the number of epochs without improvement before training is stopped. The three entries listed under PGD correspond to: the step size of the adversarial attack ( _𝛼_ ); the maximum perturbation budget ( _𝜖_ ); and the number of attack iterations ( _𝑘_ ). Finally, the two CF-Reg values represent the regularization coefficients _𝛼_ and _𝛽_ , as defined in (5) and (7), respectively.

**Figure 7: The average counterfactual perturbation vector** || _𝜹_ || **(left** _𝑦_ **-axis) and the cross-entropy test loss (right** _𝑦_ **-axis) over training epochs (** _𝑥_ **-axis) for an MLP trained on the Water dataset** **_without_ regularization.**

313