  We consider counterfactual explanations for private support vector machines
(SVM), where the privacy mechanism that publicly releases the classifier
guarantees differential privacy. While privacy preservation is essential when
dealing with sensitive data, there is a consequent degradation in the
classification accuracy due to the introduced perturbations in the classifier
weights. For such classifiers, counterfactual explanations need to be robust
against the uncertainties in the SVM weights in order to ensure, with high
confidence, that the classification of the data instance to be explained is
different than its explanation. We model the uncertainties in the SVM weights
through a random vector, and formulate the explanation problem as an
optimization problem with probabilistic constraint. Subsequently, we
characterize the problem's deterministic equivalent and study its solution. For
linear SVMs, the problem is a convex second-order cone program. For non-linear
SVMs, the problem is non-convex. Thus, we propose a sub-optimal solution that
is based on the bisection method. The results show that, contrary to non-robust
explanations, the quality of explanations from the robust solution degrades
with increasing privacy in order to guarantee a prespecified confidence level
for correct classifications.
