

\subsection{Is privacy leakage through recourses inevitable?}\label{subsec:priv}
The attacks developed above and empirical results in Section~\ref{sec:experiments} suggest that recourses can be exploited to infer private information about the underlying training set. This raises a natural question: Is privacy leakage through recourses inevitable?

Over the last decade, differential privacy \cite{privacybook} has emerged as the canonical approach to provably preventing membership inference for a wide array of statistical tasks. Applying this to the recourse setting, results which have been folklore in the privacy community imply that if the recourse generation algorithm is DP in the training data, we can provably bound the success of \emph{any} adversary $\mathcal{A}$ in the Recourse-based MI Game. In Theorem~\ref{priv_thm} (proof deferred to Supplement) we state a variant of the folklore result tailored to our setting, showing that not only can we bound the excess accuracy of the adversary over random guessing,  we can also bound the balanced accuracy (BA). Since $\text{BA} = \frac{\text{TPR} + \text{TNR}}{2}$, this implies that for a small FPR $\alpha$, the TPR of $\mathcal{A}$ is also close to $\alpha$. Recent work advocates for evaluating the success of MI attacks at low FPR instead of just looking at the overall accuracy \cite{enhanced_mi, carlini2021}. 

\begin{theorem}\label{priv_thm}
Let $\mathcal{T}: (\mathcal{X} \times \mathcal{Y})^{n} \to \Theta$ denote the training algorithm, draw $D_t \sim \mathcal{D}^n$ and  and $\mathcal{A}$ be an arbitrary adversary that receives $z = (x, y), s \sim \mathcal{R}(f_{\theta},x, D_t)$  from the recourse inference game, and produces a guess $G \in \{\text{MEMBER}, \text{NON-MEMBER}\}.$ Then, if $\mathcal{R}$ is $(\epsilon,0)$-differentially private, we have for all $\mathcal{A}$:
\vspace{-0.1in}
$$\text{BA}_{\mathcal{A}} \leq \frac{1}{2} + \frac{1-e^{-\epsilon}}{2}.$$
\end{theorem}
\vspace{-0.1in}
While Theorem~\ref{priv_thm} provides strong privacy guarantees, for several reasons both generic and specific to the recourse setting, \emph{differential privacy is not a silver bullet to defend recourses against membership inference attacks}. It is known that training with DP causes a significant drop in accuracy on even relatively simple benchmarks \cite{temp_sig}, and so when accuracy is a concern this defense may not be feasible. Moreover, model accuracy aside, private training could alter the distance between training points and the model boundary, potentially leading to costlier and less actionable recourses for individuals.

\subsection{Setup}
\paragraph{Datasets}
Our first data set is the \emph{Adult} (A) data set \cite{Dua:2019} that originates from the 1994 Census database, consisting of 14 attributes and 48,842 instances. The class label indicates whether an individual has an income greater than 50,000 USD/year. Second, we use the \emph{Home Equity Line of Credit} \emph{(Heloc)} (H) data set ($d=23$). Here, the target variable records a score indicating whether individuals will repay the Heloc account within a fixed time window. Across both tasks we consider individuals in need of recourse if their scores lies below the median score across the entire data set, thresholding the scores based on the median to obtain binary target labels. 
Third, we use the \emph{Diabetes} (D) data set which contains information on diabetic patients from 130 different US hospitals \citep{strack2014impact}. 
The patients are described using administrative (e.g., length of stay) and medical records (e.g., test results) ($d=42$), and the prediction task is concerned with identifying whether a patient will be readmitted within the next 30 days. 
In line with \citep{shorki2021explanation}, we sub sampled smaller data sets of 10000 points from each of these datasets. 5000 points are left to the model owner to train the their private model, while another 5000 data points are used by the adversary to train their shadow models when applicable.

Additionally, we follow \citet{shorki2021explanation} and generate synthetic data sets from the sklearn library. 
For $d$ features the method randomly chooses a vertex from the $d$-dimensional hypercube as a center for each of the classes, and samples Gaussian distributed random variables centered at the vertex with unit variance.
For the linear model experiments, we use $d\in \{100, 1000, 5000, 7000\}$ with $n=5000$ training and test samples. 
For the non-linear models we use $d\in \{50, 150\}$.

\textbf{Recourse Algorithms and Predictive Models.}
We apply our techniques to three different methods which aim to generate low-cost recourses using different principles: \texttt{SCFE} is the method suggested by \citet{wachter2017counterfactual} and uses a gradient-based objective to find recourses, \texttt{GS} conducts a random search for recourse in the input space \citep{laugel2017inverse}, and \texttt{CCHVAE} \citep{pawelczyk2019} searches for recourse in a lower dimensional latent space using a generative model to encourage recourses to lie on the data manifold.
All methods use a $\ell_1$-regularizer to encourage sparse recourses.
We use implementations from the \texttt{CARLA} library \citep{pawelczyk2021carla}.
For all data sets, we trained a fully connected neural network with one hidden layer and 1000 nodes. 
The network uses ReLU activation functions and are trained using the ADAM optimizer. 
The network is trained for 250 epochs.
Across all tasks, we use a learning rate of 0.0001.
All recourses were generated with respect to this classifier. 

\paragraph{Baseline Attacks.}
We implement several baseline attacks: 
the baseline of random guessing that for a target FPR $\alpha$ predicts \texttt{MEMBER} with probability $\alpha$, and baselines based on the loss $\ell$.
The loss-based baselines are simple thresholding on the loss \cite{yeom2017privacy} (i.e., \texttt{Loss}), and the offline loss-based LRT \cite{carlini2021} (i.e., \texttt{Loss LRT}).

\paragraph{Evaluation Measures.} We use several well established measures to validate the efficacy of our proposed membership inference attacks. Consistent with with previous works \citep{yeom2017privacy,shokri2017membership,shorki2021explanation} we report balanced accuracy (BA) and receiver operating characteristic (ROC) area under the curve (AUC) scores.  Additionally, we follow \citep{carlini2021,enhanced_mi} and also report log-scale ROC curves, and true positive rates of the attacks at low false positive rates. The authors argue that, for membership inference attacks, average case metrics such as BA and AUC are not well suited. 
The underlying idea is that if a membership inference attack can  identify even a very small subset of the training data with very high confidence, then the attack should be considered successful. 
We follow this intuition and primarily report our findings using this metric.





\subsection{Evaluating the Attack Efficacy} \label{subsec:eval_attack_efficacy}
\vspace{-0.1in}
Inspecting Figure~\ref{fig:real_world_all_methods}, we see that for nearly all datasets across all methods, at sufficiently low FPR the \texttt{CFD LRT} curve lies above the diagonal, outperforming the random baseline; the one exception being the Adult dataset with recourses generated from \texttt{GS}. \texttt{CFD} also often outperforms the random baseline in most cases, but not on the Diabetes dataset with recourse method \texttt{SCFE} or the Heloc dataset with method \texttt{CCHVAE}. These trends are reflected in the metrics captured in Table~\ref{table:comparing_efficacy}, where \texttt{CFD LRT} achieves TPR $> .01$ at FPR $= .01$, and AUC $> .5$ in $7$ of the $8$ dataset-recourse settings. \texttt{CFD} achieves TPR $> .01$ at FPR $= .01$ in $4$ of the $8$ settings. Focusing on the metric of TPR at FPR $= .01$, we see that in the $7$ of $8$ settings where either method outperforms the random baseline, \texttt{CFD LRT} achieves higher TPR than \texttt{CFD} $5$ times. This difference is particularly evident on the Heloc dataset, where \texttt{CFD LRT} obtains TPR $35\%, 270\%$, and $413\%$ above the random baseline for \texttt{SCFE}, \texttt{GS}, \texttt{CCHVAE} respectively. In summary, both methods often outperform the random baseline across all metrics, showing substantial privacy leakage from algorithmic recourses, with \texttt{CFD LRT} generally outperforming \texttt{CFD}. The results also show that the Heloc dataset is particularly vulnerable to distance-based attacks across all recourse algorithms, with the Diabetes dataset being less susceptible. On the Adult and Diabetes datasets the distance-based attacks usually outperform random guessing, however, the improvement over the random baseline is less pronounced. 

Perhaps most interesting, is that only in the case of \texttt{CCHVAE} do the \texttt{CFD LRT} attacks that outperform the random baseline and are plotted in Figure~\ref{fig:real_world_all_methods}(c), actually reverse the direction of the threshold. This means that for the \texttt{CFD LRT} curves in Figure~\ref{fig:real_world_all_methods}(c) and metrics in Table~\ref{table:comparing_efficacy} in column \texttt{CCHVAE}, rather than predicting \texttt{MEMBER} in Line $12$ of Algorithm~\ref{alg:thresh_lrt} if $c(x,x') > z_{1-\alpha}$, we predict \texttt{MEMBER} iff $c(x,x') < z_{\alpha}$. While these results stand in contrast to our findings for \texttt{SCFE} and \texttt{GS}, there is an intuitive explanation.   \texttt{CCHVAE} trains a VAE to model the data generating distribution, and performs sampling \emph{in the latent space} to find a point in latent space $z'$ that is close to the representation of $x$ in the latent space $\text{encode}(x) = z_{x}$. Then it outputs the recourse $x' = \text{decode}(z')$ in the input space. Regardless of the specific $z'$ found by the recourse algorithm, $\text{decode}(z')$ is still in the range of the generative model. It is a known property of generative models like VAEs and GANs that their generated samples tend to be closer to training points than to test points, a fact which has been exploited for MI \cite{gan_survey}. One explanation for the results in Figure~\ref{fig:real_world_all_methods}(c) is that this property of generative models is in some cases outweighing the effect of the optimization during model training.




\subsection{Towards Understanding Attack Success}
\label{subsec:understanding}
To better understand the factors underlying these impressive results, in this section we use experiments on synthetic data with $\mathcal{R} = \texttt{SCFE}$ to examine the role of model type, model size, and number of features in attack success. 

\textbf{Linear Models.}
One potential confounding factor in assessing the results for \texttt{SCFE}, is that when $f_\theta(x)$ is non-convex so is the objective in Equation~\ref{eqn:generalrecourse_un}, and so there is no guarantee that the recourse output is close to globally optimal. In the case when $f_{\theta}$ is linear the objective is convex and has a closed form minimizer \cite{pawelczyk2022algorithmic, label-only}. In Figure~\ref{fig:linear_synth_experiments} we train logistic regression models on the synthetic data, varying the number of features, and plotting the distribution of the counterfactual distances for train and test points, as well as the log-scaled ROC curves. We observe that the training distance distribution starts moving away from the test distance distribution as the number of feature dimensions increases (see Figure \ref{fig:linear_distances}), and as expected the distance-based attack starts performing better as the number of features increases (see Figure \ref{fig:linear_tpr_fpr}). 
Strikingly, the \texttt{CFD LRT} in particular not only outperforms the \texttt{CFD} and random baseline, but also thresholding based on the \texttt{Loss} and the \texttt{Loss LRT} --- attacks which have access to the full loss function and the label $y$. Figures~\ref{fig:linear_distances}, \ref{fig:linear_tpr_fpr} suggest two potential reasons why the results in Figure~\ref{fig:real_world_all_methods} for \texttt{SCFE} do not exhibit the same level of attack performance as on the synthetic data: 
(i) Since the model classes are non-convex it could be due to our optimization failing to find the recourse that minimizes Equation~\ref{eqn:generalrecourse_un}, and (ii) Distance-based membership inference attacks are more effective in high dimensions, and the tabular datasets we experiment on are of relatively small dimension $d < 50$.

\input{figures/figures_linear_synth}
\textbf{Nonlinear models.}
\input{figures/figures_ann_synth}
So far we have studied the effect of the dimension on the attack success, which in the case of linear models is equal to the number of parameters. 
To disentangle the effect that the number of features has from the effect that model capacity has on attack success, we use fully-connected neural networks for which we can control both factors independently.  
We generate two synthetic data sets with $d =  50, 150$ respectively, and study to what extent an increase in model capacity, in this case the number of hidden nodes, impacts the performance of our attacks.
For $d=50$ the results in Figure \ref{fig:ann_synth_tpr_fpr_n10000_d50} suggest that increasing model capacity does not yield performance increases for our distance-based attacks.
On the other hand, when $d=150$ the results in Figure \ref{fig:ann_synth_tpr_fpr_n10000_d150} show that increasing model capacity drastically increases the attack success of the \texttt{CFD LRT}, while the simple \texttt{CFD} still does not work well.
For the model with the largest capacity, three layers of 1000 hidden nodes per layer, \texttt{CFD LRT} performs considerably better than even the \texttt{Loss LRT}.
Taken together these results suggest that a combination of high model capacity and high feature dimension increases the vulnerability of recourses to MI attacks, where feature dimension appears to play a  more important role. 

















\subsubsection*{\bibname}}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}   
\usepackage{hyperref}      
\usepackage{url}           
\usepackage{booktabs}      
\usepackage{amsfonts}      
\usepackage{nicefrac}      
\usepackage{microtype}     
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{algorithm}
\usepackage{algorithmicx}
\usepackage{algpseudocode}
\usepackage{multirow}
\usepackage{xspace}
\usepackage{subcaption}

\usepackage{amssymb}
\usepackage{MnSymbol}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{bm}
\usepackage[dvipsnames]{xcolor}
\usepackage{hyperref}
\hypersetup{
colorlinks = true,
linkcolor = Brown,
anchorcolor = Brown,
citecolor = Mahogany,
filecolor = RoyalBlue,
menucolor = Green,
runcolor = cyan,
urlcolor = Green}
\newcommand{\sn}[1]{}
\newcommand{\map}[1]{\textcolor{pink}{[Martin: #1]}}
\newcommand{\hima}[1]{}
\newcommand{\hideh}[1]{}

\newcommand{\mathcal{A}^p\xspace}{\mathcal{A}^p\xspace}
\newcommand{\bx}[0]{\mathbf{x}}
\newcommand{\bz}[0]{\mathbf{z}}
\newcommand{\xc}[0]{\mathbf{x}'}
\newcommand{\bw}[0]{\mathbf{w}}
\newcommand{\bd}[0]{\mathbf{d}}
\newcommand{\mathcal{A}}{\mathcal{A}}
\newcommand{\mathcal{R}}{\mathcal{R}}
\newcommand{\mathcal{T}}{\mathcal{T}}
\newcommand{\mathcal{D}}{\mathcal{D}}
\newcommand{\mathcal{O}}{\mathcal{O}}
\newcommand{f_{\btheta}}{f_{\btheta}}

\newcommand{\bH}[0]{\mathbf{H}}
\newcommand{\bX}[0]{\mathbf{X}}
\newcommand{\bI}[0]{\mathbf{I}}

\newcommand{\bSigma}[0]{\mathbf{\Sigma}^{-1}}
\newcommand{\bdelta}[0]{\bm{\delta}}
\newcommand{\bomega}[0]{\bm{\omega}}
\newcommand{\btheta}[0]{\bm{\theta}}
\newcommand{\mathbf{o}}{\mathbf{o}}

\newcommand{\text{cost}}{\text{cost}}
\newcommand{\mathcal{M}\xspace}{\mathcal{M}\xspace}
\newcommand{c\xspace}{c\xspace}
\newtheorem{theorem}{Theorem}
\newtheorem{remark}{Remark}
\newtheorem{lemma}{Lemma}
\newtheorem{example}{Example}
\newtheorem{proposition}{Proposition}
\newtheorem{definition}{Definition}
\newtheorem{condition}{Condition}
\newtheorem{assumption}{Assumption}
\newtheorem{corollary}{Corollary}
\newtheorem{attack}{Attack}

\DeclareMathOperator*{\argmin}{arg\,min}
\title{On the Privacy Risks of Algorithmic Recourse}

\author{%
Martin Pawelczyk \\
University of Tübingen \\
\And
Himabindu Lakkaraju\thanks{Equal contribution} \\
Harvard University \\
\And 
Seth Neel\footnotemark[1] \\
Harvard University\\
\\
}


\begin{document}
\maketitle

\begin{abstract}
\input{abstract.tex}
\end{abstract}

\section{Introduction}
\input{intro.tex}

\section{Related Work} \label{section:related_work}
\input{related_work.tex}

\section{Preliminaries} \label{section:preliminaries}
\input{prelims.tex}

\section{Our Framework}
\label{section:theory}
\input{method}
\input{diff_privacy}


\section{Experimental Evaluation}  \label{sec:experiments}
\input{experiments.tex}

\section{Conclusion}  \label{section:conlusion}
\input{conclusion.tex}

\subsection{Thresholding on Counterfactual Distance}\label{subsec:distance} \hima{TODO: Hima to take a pass on 4.1 to clean up.} In the recourse-based MI Game, all the adversary has access to is the original instance $x$ and its counterfactual $x'$ generated by recourse algorithm. Loss-based attacks perform well at determining whether a point is a \texttt{MEMBER} of the training set or not, because the model typically over-fits to the training points, leading to lower losses on these points than on the test set. One explanation for this loss-disparity that has been given in prior work \cite{shorki2021explanation}, is that during the training process, the decision boundary is forced away from training points. This suggests that points in the training set should be further from the boundary than points in the test set, motivating a distance-based attack that predicts a point is a \texttt{MEMBER} of the training set if its loss is below some threshold $\tau$. The distance of a point $x$ to the boundary can be computed as $c(x, x')$ where $x'$ is the solution to Equation~\ref{eqn:generalrecourse_un} with $\mathcal{A}^{p} = \mathbb{R}^d$.
So if we exactly optimize the objective function in Equation~\ref{eqn:generalrecourse_un} that underpins our recourse algorithms (with $\mathcal{A}^p\xspace = \mathbb{R}^d$), the counterfactual distance $c(x, x')$ is exactly the distance to the model boundary. While algorithms that focus on generating \emph{realistic} recourses~\cite{pawelczyk2019,karimi2021algorithmic} do not exactly optimize this objective in general, we can still view the distance to the recourse as a proxy for the distance of $x$ to the model boundary. Based on this intuition we have the following counterfactual distance (\texttt{CFD}) based attack:
\begin{align}
M_{\text{Distance}}(x) = 
\begin{cases}
\emph{\texttt{MEMBER}} & \text{ if } c(x,x') \geq \tau_D \\
\emph{\texttt{NON-MEMBER}} & \text{ if } c(x,x') < \tau_D.
\end{cases}\label{eqn:threshold-dist}
\end{align}
Following \cite{carlini2021}, we assume for the first two attacks below that $\mathcal{A}$ knows apriori an optimal threshold $\tau_{\alpha}$ that maximizes a given TPR subject to a fixed FPR $\alpha$, as the purpose of these simple attacks is to illustrate the potential privacy leakage through the recourse output. In practice, we will be plotting the TPR vs. FPR curves over all values of the threshold $\tau_{\alpha}$ and so we will not need to pick a specific one.
\iffalse
In the case when the underling model is linear and the $\ell_2$ norm is used as the cost function there exists a closed-form expression for algorithmic recourse that simultaneously quantifies an input's distance to the decision boundary \citep{pawelczyk2021connections}:
\begin{equation}
x' = x - \frac{g_{\btheta}(x)}{\lambda + \lVert \btheta \rVert_2^2} \btheta,
\label{eq:closed_form}
\end{equation}
where $x'$ is the recourse, $\frac{g_{\btheta}(x)}{\lambda + \lVert \btheta \rVert_2^2} \btheta$ measures the distance from the input $x$ to the decision boundary, $g_{\btheta}: \mathcal{X} \to \mathbb{R}$ is the network's pre-sigmoid output, and $\lambda$ is the balance parameter.


\subsection{Approximate Loss-Based Attack}\label{subsec:attack_thresh}
Now assume we are in the PARA setting of the game, where $\mathcal{A}$ receives $z, x'$ and the predicted probability of a positive classification $(f_\theta(x'))_{y}$. Suppose further that our loss function $\ell(\theta, x, y)$ is $\lambda$-Lipschitz in $x$ with respect to our distance metric $c(\cdot, \cdot)$. By Lipschitzness we have: 
\begin{equation}\label{eq:lip}
\ell(x', y, \theta) - \lambda c(x, x') \leq l(x, y, \theta) \leq l(x', y, \theta) + \lambda c(x, x').
\end{equation}
So $l(x', y, \theta)$ is a $\pm \lambda c(x, x')$ approximation to the true loss $l(x, y, \theta)$. Moreover, both of the upper and lower bounds on the RHS of Equation~\ref{eq:lip}  can be computed by $\mathcal{A}$ from the recourse algorithm's output itself. We know $x, x'$ and so we can compute $\lambda c(x, x')$, and $l(x', \theta, y)$ is a function of $(f_\theta(x'))_{y}$.
Hence $\mathcal{A}$ can use Equation~\ref{eq:lip} to compute an approximation to the true loss on the point $x, \; l(\theta, x, y)$. Algorithm~\ref{alg:thresh_lip} implements an approximate version of the loss-based threshold test using this recourse-based approximation. 

\begin{algorithm}[H]
\begin{algorithmic}
\caption{Recourse Approximation to Loss-based Membership inference attack (\texttt{LipThresh}).}
\label{alg:thresh_lip}
\State \textbf{Inputs:} $\tau_{\alpha}, \lambda$
\State Receive point $(x, y)$, recourse $x'$, and estimated positive classification $f_{\btheta}(x')$. 
\State Compute distance $\lambda \cdot c(x, x')$, and loss $l(x', y, \theta) = \log((1-f_{\btheta}(x'))^{1-y}(f_{\btheta}(x'))^{y})$. 
\State Let $lb = l(x', y, \theta)-\lambda c(x,x'), ub = l(x', y, \theta) + \lambda \cdot c(x, x') $
\If{$lb > \tau_{\alpha}$}
    \State \textbf{Output:} $G$ = \texttt{\texttt{NON-MEMBER}} 
\Else \If{$ub < \tau_{\alpha}$}
    \State \textbf{Output:} $G$ = \texttt{MEMBER} 
\Else
    \State \textbf{Output:} UNKNOWN
\EndIf
\EndIf
\end{algorithmic}
\end{algorithm}

\fi

\subsection{Likelihood Ratio Test using Counterfactual Distance}\label{subsec:attack_thresh}
\begin{algorithm}[!ht]
\begin{algorithmic}[1]
\caption{One-sided Distance-based Likelihood Ratio Test (\texttt{CFD LRT})}
\label{alg:thresh_lrt}
\State \textbf{Inputs:} point $(x, y)$, recourse output $s = \texttt{GetRecourse}(x, f_{\btheta}), \mathcal{D}$; FP-Rate: $\alpha$, \# Shadow Models: $N$, $\mathcal{T} = \texttt{TrainClassifier}(\cdot)$
\State $\text{teststats} = []$
\State \textbf{Compute}: $t_0 = T(s) = c(x,x')$ 
\For{$i=1:N$} 
\State Sample $\mathcal{D}_t^{(i)} \sim \mathcal{D}$
\State $f_{\btheta^{(i)}} = \texttt{TrainClassifier}(\mathcal{D}^{(i)})$
\State $s^{(i)} = \texttt{GetRecourse}(x, f_{\btheta^{(i)}})$
\State teststats $\xleftarrow{} T(s^{i}) = c(x, x'^{(i)})$
\EndFor
\State $\hat{\mu}_{\text{MLE}} = \frac{1}{N} \sum_{i=1}^N \big(\log c(x, \xc^{(i)}) \big)  \big)$
\State $\hat{\sigma}^2_{\text{MLE}}  = \frac{1}{N} \sum_{i=1}^N \big(\hat{\mu}_{\text{MLE}} - \log\big(c(x, \xc^{(i)})\big) \big)^2$
\If{$t_0$ > $z_{1-\alpha}$} \Comment{ $z_{1-\alpha}$ is the $1{-}\alpha$-quantile of $Z \sim \mathcal{LN}(\hat{\mu}_{\text{MLE}}, \hat{\sigma}^2_{\text{MLE}}$})
    \State \textbf{Output:} $G$ = \texttt{\texttt{NON-MEMBER}} 
\Else
    \State \textbf{Output:} $G$ = \texttt{MEMBER} 
\EndIf
\end{algorithmic}
\end{algorithm}
\citet{carlini2021} showed that \texttt{Loss LRT} attacks perform better than simple \texttt{Loss} thresholding. In Algorithm~\ref{alg:thresh_lrt} we present an LRT version of our counterfactual distance attack (\texttt{CFD LRT}).
As in prior work \cite{carlini2021, sablayrolles2019whitebox} since computing the LRT (Equation~\ref{eq:cfd_lrt}) exactly is intractable, we  make several modifications to the attack that allow us to compute it efficiently.
The full likelihood ratio given $c(x,x')$ is:
 \begin{equation}
 \label{eq:cfd_lrt}
     \Lambda =  \frac{ \Pr[c(x, x')|x \in D_t]} {\Pr[c(x, x')|x \not \in D_t]}.
 \end{equation}
 We model the distributions of our statistic $c(x, x')$ as log-Normal, and so in order to compute eqn.\ \eqref{eq:cfd_lrt}, we need to estimate $(\mu_{in}, \sigma_{in}), (\mu_{out}, \sigma_{out})$ where we assume that if $D_t\backslash \{x\} \sim \mathcal{D}, \theta \sim \mathcal{T}(\{x\} \cup D_t), x' \sim \mathcal{R}(x, \theta, D_t)$, then $\log c(x,x') \sim \mathcal{N}(\mu_{in}, \sigma_{in})$, and similarly when $x' \not \in D_t$, $\log c(x,x') \sim \mathcal{N}(\mu_{out}, \sigma_{out})$. Given access to $\mathcal{D}$ we can estimate the parameters $\mu, \sigma$ by drawing fresh datasets, training models $\theta$ -- with or without a given point $x$ -- and then computing the resulting counterfactual distances (Lines $5-8$). However, as in \cite{carlini2021} we note that to approximate the numerator, we have to perform this sampling and model training separately for each $x$ that we perform the attack on, which is computationally infeasible. Hence in Algorithm~\ref{alg:thresh_lrt} we present a one-sided version of the LRT, where in Lines $10-11$ we estimate $\mu_{out}, \sigma_{out}$, and our attack predicts $\texttt{MEMBER}$ if $c(x,x')$ has a sufficiently low likelihood under these parameters. Note that since $\mu_{out}, \sigma_{out}$ do not depend on $x$, we only need to perform the process of training Shadow models once, even if we are evaluating our attack on many different $x$'s.





\section{Proof of Theorem~\ref{priv_thm}}
\begin{proof}
Throughout the proof let the event that $\mathcal{A}$ recieves $(z, s)$ and outputs $G = \text{MEMBER}$ be denoted by $\mathcal{A}(z, s) =1$. First we prove the following simple lemma in the Appendix, which says that since the recourse is generated privately, the probability it takes on any value can't be changed by more than $e^{\epsilon}$ depending on whether a given point $z$ is in the training set. 
\begin{lemma}\label{lem:sup_priv}
If $\mathbf{o}$ is any event, for any $z$: 
$$ \Pr_{s \sim \mathcal{R}, D_t \sim \mathcal{D}^n}[s \in \mathbf{o} | z \in D_t] \leq e^{\epsilon}\Pr_{s \sim \mathcal{R}, D_t \sim \mathcal{D}^n}[s \in \mathbf{o}|z \not \in D_t]
$$
\end{lemma}

\begin{proof}
Fix arbitrary $D_t\backslash\{z\} = (z_2, \ldots z_n)$. Expanding
\begin{equation}
    \Pr_{s \sim \mathcal{R}, D_t \sim \mathcal{D}^n}[s \in \mathbf{o} | z \in D_t] = \int_{(z_2, \ldots z_n) \sim \mathcal{D}^{n-1}}\Pr_{s \sim \mathcal{R}}[s \in \mathbf{o} | z, D_t\backslash\{z\} = (z_2, \ldots z_n)]\Pr_{\mathcal{D}}[(z_2, \ldots z_n)]
\end{equation}

By the definition of differential privacy, for arbitrary $z'$:
\begin{multline}
    \int_{(z_2, \ldots z_n) \sim \mathcal{D}^{n-1}}\Pr_{s \sim \mathcal{R}}[s \in \mathbf{o} | z, D_t\backslash\{z\} = (z_2, \ldots z_n)]\Pr_{\mathcal{D}}[(z_2, \ldots z_n)] \leq \\
    \int_{(z_2, \ldots z_n) \sim \mathcal{D}^{n-1}}e^{\epsilon}\Pr_{s \sim \mathcal{R}}[s \in \mathbf{o} | z', D_t\backslash\{z\} =  (z_2, \ldots z_n)]\Pr_{\mathcal{D}}[(z_2, \ldots z_n)]
\end{multline}

Since this holds for arbitrary $z'$, we have: 
\begin{multline}
\Pr[s \in \mathbf{o} | z \in D_t] \leq \inf_{z'}\left(\int_{(z_2, \ldots z_n) \sim \mathcal{D}^{n-1}}e^{\epsilon}\Pr_{s \sim \mathcal{R}}[s \in \mathbf{o} | z', D_t\backslash\{z\} = (z_2, \ldots z_n)]\Pr_{\mathcal{D}}[(z_2, \ldots z_n)]\right) \leq \\
\mathbb{E}_{z' \sim \mathcal{D}}\left[\int_{(z_2, \ldots z_n) \sim \mathcal{D}^{n-1}}e^{\epsilon}\Pr_{s \sim \mathcal{R}}[s \in \mathbf{o} | z', D_t\backslash\{z\} = (z_2, \ldots z_n)]\Pr_{\mathcal{D}}[(z_2, \ldots z_n)]\right] = e^{\epsilon}Pr[s \in \mathbf{o}|z \not \in D_t],
\end{multline}

as desired.

\end{proof}



Recall that $\text{BA} = \frac{\text{FPR} + \text{TNR}}{2} = \frac{\Pr[\mathcal{A}(z, s) = 1 | z \in D_t] + \Pr[\mathcal{A}(z, s) = 0 | z \not \in D_t]}{2}$, and let $a^{1} = \Pr[\mathcal{A}(z, s) = 1 | z \in D_t]$, and $a^{0} = \Pr[\mathcal{A}(z, s) = 0 | z \not \in D_t]$. Then:
\begin{multline}
    a^1 = \Pr[\mathcal{A}(z, s) = 1 | z \in D_t] = \int_{s \in \mathcal{S}}\int_{z \in \mathcal{X} \times \mathcal{Y}}\Pr[\mathcal{A}(z, s) = 1|z,s]\Pr[s|z \in D_{t}]\Pr_{\mathcal{D}}[z] \leq \\ 
\int_{s \in \mathcal{S}}\int_{z \in \mathcal{X} \times \mathcal{Y}}\Pr[\mathcal{A}(z, s) = 1|x,s]\Pr_{\mathcal{D}}[x](e^{\epsilon}\Pr[s|z \not \in D_t]) = \\
\int_{s \in \mathcal{S}}\int_{z \in \mathcal{X} \times \mathcal{Y}}\Pr[\mathcal{A}(z, s) = 1|x,s]\Pr_{\mathcal{D}}[x](e^{\epsilon}\Pr[s]) = \\
e^{\epsilon}\Pr[A(x,s) = 1 | x \not \in D_t] = e^{\epsilon}(1-a_0),
\end{multline}
where the inequality follows from Lemma~\ref{lem:sup_priv}. Rearranging $a^1 \leq e^{\epsilon}(1-a_0)$  we get that $a_0 \leq 1-e^{-\epsilon}a_1$. Hence: 
$$ 
\text{BA} \leq \frac{a^1 + (1-e^{-\epsilon}a^1)}{2} = \frac{1}{2} + \frac{a_1 ( 1-e^{-\epsilon})}{2}
$$
Since $a_1 \leq 1$ this gives the result, and we note that for small $\epsilon$ this can be improved to $\text{BA} \leq \frac{1}{2} + \frac{(2-e^{-\epsilon})(1-e^{-\epsilon})}{4}$.
\end{proof}


\section{TRAINING DETAILS}
\subsection{Classification Models}
\input{tables/linear_classification_accuracy}
\input{tables/ann_classification_accuracy_synthetic}
\input{tables/ann_classification_accuracy_realworld}


\subsection{Recourse methods}

\begin{itemize}
\item {\texttt{SCFE}}: As suggested in~\citet{wachter2017counterfactual}, an Adam optimizer is used to optimize the recourse objective. 
We obtain recourses using an $\ell_1$ distance function, and the binary cross entropy loss between the counterfactual label and the target. 

\item {\texttt{GS}}:
The explanation model uses a counterfactual search algorithm in the input space. 
Particularly, instances are sampled within an $\ell_1$-norm ball with search radius search radius $r_i$ until recourse is successfully obtained.
The search radius of the norm ball is increased until recourse is found. 

\item {\texttt{C-CHVAE}}: An autoencoder is additionally trained to model the data-manifold. 
The explanation model uses a counterfactual search algorithm in the latent space of the AE. 
Particularly, a latent sample within an $\ell_1$-norm ball with search radius $r_l$ is used until recourse is successfully obtained. 
The search radius of the norm ball is increased until recourse is found. 
All generative models use $8$ latent dimensions, and 20 nodes in the first and third hidden layer.
\end{itemize}


\section{ADDITIONAL EXPERIMENTAL RESULTS}
\begin{figure*}[h!]
\centering
\begin{subfigure}{\textwidth}
\centering
\scalebox{0.90}{%
\includegraphics[width=\textwidth]{plots/linear_thresholds_depth0.pdf}
}
\label{fig:linear_thresholds}
\end{subfigure}
\caption{Demonstrating the efficacy of our proposed distance-based attack for logistic regression models trained on the synthetic data set by showing the attack accuracy as the threshold varies. 
Both the LRT-Distance as well as the baseline distance attacks are the most competetive attacks.
The thresholds have been normalized to the range $[0,1]$.
}
\label{fig:linear_experiments}
\end{figure*}


\begin{figure*}[tb]
\centering
\begin{subfigure}{\textwidth}
\centering
\includegraphics[width=\textwidth]{plots/40000_features50_synthetic_ann_scfe_attacks_depth_all_width_all.pdf}
\caption{$d=50, n=20000$}
\label{fig:ann_synth_tpr_fpr_n20000_d50}
\end{subfigure}
\vfill 
\begin{subfigure}{\textwidth}
\centering
\includegraphics[width=\textwidth]{plots/40000_features150_synthetic_ann_scfe_attacks_depth_all_width_all.pdf}
\caption{$d=150, n=20000$}
\label{fig:fig:ann_synth_tpr_fpr_n20000_d150}
\end{subfigure}
\vfill
\begin{subfigure}{\textwidth}
\centering
\includegraphics[width=\textwidth]{plots/60000_features50_synthetic_ann_scfe_attacks_depth_all_width_all.pdf}
\caption{$d=50, n=30000$}
\label{fig:fig:ann_synth_tpr_fpr_n20000_d50}
\end{subfigure}
\vfill 
\begin{subfigure}{\textwidth}
\centering
\includegraphics[width=\textwidth]{plots/60000_features150_synthetic_ann_scfe_attacks_depth_all_width_all.pdf}
\caption{$d=150, n=30000$}
\label{fig:fig:ann_synth_tpr_fpr_n30000_d150}
\end{subfigure}
\caption{Demonstrating the efficacy of our proposed distance-based attack for neural network models trained on the synthetic data set when \texttt{SCFE} is used for the attack. (a): two-layer network with 1000 hidden nodes. (b): three-layer neural network with 100 hidden nodes in each hidden layer. (c): three-layer neural networks with 333 hidden nodes in each hidden layer. (d): three-layer neural networks with 1000 hidden nodes in each hidden layer.
}
\label{fig:ann_synth_experiments_fpr_tpr_appendix}
\end{figure*}


\begin{figure*}[tb]
\centering
\begin{subfigure}{\textwidth}
\centering
\includegraphics[width=\textwidth]{plots/40000_features50_synthetic_ann_scfe_thresholds_depth_all_width_all.pdf}
\caption{$d=50, n=20000$}
\label{fig:ann_synth_thresholds_n20000_d50}
\end{subfigure}
\vfill 
\begin{subfigure}{\textwidth}
\centering
\includegraphics[width=\textwidth]{plots/40000_features150_synthetic_ann_scfe_thresholds_depth_all_width_all.pdf}
\caption{$d=150, n=20000$}
\label{fig:fig:ann_synth_thresholds_n20000_d150}
\end{subfigure}
\vfill
\begin{subfigure}{\textwidth}
\centering
\includegraphics[width=\textwidth]{plots/60000_features50_synthetic_ann_scfe_thresholds_depth_all_width_all.pdf}
\caption{$d=50, n=30000$}
\label{fig:fig:ann_synth_thresholds_n20000_d50}
\end{subfigure}
\vfill 
\begin{subfigure}{\textwidth}
\centering
\includegraphics[width=\textwidth]{plots/60000_features150_synthetic_ann_scfe_thresholds_depth_all_width_all.pdf}
\caption{$d=150, n=30000$}
\label{fig:fig:ann_synth_thresholds_n30000_d150}
\end{subfigure}
\caption{Demonstrating the efficacy of our proposed distance-based attack for neural network models trained on the synthetic data set when \texttt{SCFE} is used for the attack. (a): two-layer network with 1000 hidden nodes. (b): three-layer neural network with 100 hidden nodes in each hidden layer. (c): three-layer neural networks with 333 hidden nodes in each hidden layer. (d): three-layer neural networks with 1000 hidden nodes in each hidden layer. 
The thresholds have been normalized to the range $[0,1]$ when necessary.
}
\label{fig:ann_synth_experiments_fpr_tpr_appendix}
\end{figure*}






