\section{Omitted Proofs and Derivations}
\label{app:proofs}

\subsection{\cref{sec:background}}
\label{app:background}

First, we provide an explanation on the range of disagreement without normalization:
\begin{proposition}[Range of non-normalized disagreement]
The expression $\Pr[f_{\theta}(x) \neq f_{\theta'}(x)]$ has range of $[0, 0.5]$.
\end{proposition}
\begin{proof}
As $f_\theta(x) \in \{0, 1\}$, we can assume $\Pr[f_\theta(x)=1]=p$, and thus $\Pr[f_{\theta}(x) \neq f_{\theta'}(x)] = \Pr[f_{\theta}(x)=0\; \text{and}\; f_{\theta'}(x)=1] + \Pr[f_{\theta}(x)=1\; \text{and}\; f_{\theta'}(x)=0] = 2p(1-p) \in [0,0.5]$.
\end{proof}

Next, we provide a proof that disagreement is proportional to variance in our setup:
\multvar*
\begin{proof}
As $f_\theta(x) \in \{0, 1\}$, we have that
\begin{equation}
\begin{aligned}
    \mu(x) &= 2 \Pr_{\theta, \theta' \sim P_{\train(\dataset)}}[f_{\theta}(x) \neq f_{\theta'}(x)] = 2 \, \mathbb{E}_{\theta, \theta' \sim P_{\train(\dataset)}}[\mathbb{1}[f_{\theta}(x) \neq f_{\theta'}(x)]] = 2 \, \mathbb{E}_{\theta, \theta' \sim P_{\train(\dataset)}}[(f_\theta(x) - f_{\theta'}(x))^2] \\
    &= 2 \, \mathbb{E}_{\theta \sim P_{\train(\dataset)}}[f_{\theta}^2(x)]
    - 4 \, \mathbb{E}_{\theta, \theta' \sim P_{\train(\dataset)}}[ f_{\theta}(x) \cdot f_{\theta'}(x)]
    + 2 \mathbb{E}_{\theta' \sim P_{\train(\dataset)}}[f_{\theta'}^2(x)] \\
    &= 4 \, (\mathbb{E}_{\theta \sim P_{\train(\dataset)}}[ f_{\theta}(x)]^2 - \mathbb{E}_{\theta \sim P_{\train(\dataset)}}[f_{\theta}(x)] \cdot \mathbb{E}_{\theta' \sim P_{\train(\dataset)}}[f_{\theta'}(x)]) \\
    &= 4 \, \mathrm{Var}_{\theta \sim P_{\train(\dataset)}}(f_\theta(x))\\
    &= 4p_x(1-p_x),
\end{aligned}
\end{equation}
where $p_x(1-p_x)$ is the population variance of the r.v. $f_\theta(x) \sim \mathrm{Bernoulli}(p_x)$.
\end{proof}

\subsection{\cref{sec:out-pert}}

\outpert*
\begin{proof}
First, observe that $p_x = \mathbb{E}_{\theta_\mathsf{priv} \sim P_{\train(\dataset)}}[f_{\theta_\mathsf{priv}}(x)]$ can be expressed as:
\begin{equation}\label{eq:px}
    \begin{aligned}
        \mathbb{E}[f_{\theta_\mathsf{priv}}(x)] &= \mathbb{E}[\mathbb{1}[ \mathsf{sigmoid}(\theta_\mathsf{priv}^\intercal x) > 0.5 ]] \\
        &= \mathbb{E}[\mathbb{1}[ \theta_\mathsf{priv}^\intercal x > 0 ]] \\
        &= \Pr( \theta_\mathsf{priv}^\intercal x > 0 ).
    \end{aligned}
\end{equation}

Denoting by $\xi ~\triangleq~ \mathcal{N}(0, 1)$ and $\xi_d ~\triangleq~ \mathcal{N}(0, I_d)$, we can see that the score $\theta_\mathsf{priv}^\intercal \, x$ is equal to:
\begin{equation}\label{eq:closed-noise}
    \begin{aligned}
    \theta_\mathsf{priv}^\intercal \, x &= (\theta_\mathsf{np} + \sigma \xi_d)^\intercal x = \theta_\mathsf{np}^\intercal \, x + \sigma \sum_{i=1}^d x_i \xi \\
    &= \theta_\mathsf{np}^\intercal \, x + \sqrt{\sum_{i=1}^d x_i^2} \cdot \sigma\xi \\
    &= \theta_\mathsf{np}^\intercal \, x + \|x\| \sigma \xi.
    \end{aligned}
\end{equation}

Plugging in the closed form in \cref{eq:closed-noise} into \cref{eq:px}, we get:
\begin{equation}
    p_x = \Pr(\theta_\mathsf{np}^\intercal \, x + \|x\| \sigma \xi > 0) = \Pr\left(\xi > -\frac{\theta_\mathsf{np}^\intercal \, x}{\|x\| \cdot \sigma}\right) = \Phi\left( \frac{\theta_\mathsf{np}^\intercal \, x}{\|x\| \cdot \sigma} \right).
\end{equation}

\end{proof}

\subsection{\cref{sec:estimator}}
\label{app:estimator}

\unbiasedest*

\begin{proof}
The $\nicefrac{1}{m-1}$ term comes from Bessel's correction. Observe that
\begin{equation}
\begin{aligned}
\mathbb{E}\left[\frac{m}{m-1} \, \hat p_x(1 - \hat p_x)\right] &= \frac{m}{m-1} (\mathbb{E}[\hat p_x]-\mathbb{E}[\hat p_x^2]) \\
&= \frac{m}{m-1} (\mathbb{E}[\hat p_x]-\mathrm{Var}(\hat p_x) - \mathbb{E}[\hat p_x]^2) \\
&= \frac{m}{m-1}(p_x-\frac{p_x(1-p_x)}{m}-p_x^2)  \\
&= p_x(1-p_x)
\end{aligned}
\end{equation}
Therefore, $\mathbb{E}[\hat \mu(x)] = 4p_x(1-p_x) = \mu(x)$.
\end{proof}

\single*

\begin{proof}
As $\hat \mu(x)$ is a continuous transformation of $\hat p_x$, we could bound  the deviation $|\hat \mu(x)-\mu(x)|$ by $|\hat p_x-p_x|$.
Suppose $\hat p_x = p_x + \nu$ and $\nu \in [-\eta,\eta]$, we have
\begin{equation}
\begin{aligned}\label{eq:variance-estimation-1}
    \left|\frac{m}{m-1} \, \hat p_x(1 - \hat p_x) - p_x(1-p_x)\right| &=\left|\frac{m}{m-1} \, (p_x + \nu)(1 - p_x - \nu) - p_x(1-p_x)\right|\\
    &= \left|\left(\frac{m}{m-1}-1\right)p_x(1-p_x) + \frac{m}{m-1} \nu(1 - 2p_x - \nu)\right|\\
    &\leq \frac{p_x(1-p_x)}{m-1} + \frac{m}{m-1}|\nu||1-2p_x+\nu|\\
    &\leq \frac{p_x(1-p_x)}{m-1} + \frac{m}{m-1}|\nu|(1+|\nu|)\\
    &\leq \frac{p_x(1-p_x)}{m-1} + \frac{m}{m-1}\eta(1+\eta)\\
    &\leq \frac{1}{4(m-1)} + \frac{m}{m-1}\eta(1+\eta).
\end{aligned}
\end{equation}
By Chernoff-Hoeffding inequality, we have the following concentration bounds on the sample mean $\hat p_x$,
\begin{equation}\label{eq:variance-estimation-2}
    \Pr[ |\hat p_x - p_x| \geq \nu ] \leq 2 \exp\left(-2 \nu^2 m\right).
\end{equation}
Thus with probability at least $1 - \rho$, we have $|\hat p_x - p_x| \leq \sqrt{\log (2/\rho)/2m}$.
Combining \cref{eq:variance-estimation-1} and \cref{eq:variance-estimation-2}, we have
\begin{equation}\label{eq:variance-estimation-3}
\begin{aligned}
    |\hat \mu(x) - \mu(x)| &= \left| \frac{4m}{m-1} \, \hat p_x(1 - \hat p_x) - 4p_x(1-p_x) \right| \leq \frac{1}{(m-1)} + \frac{4m}{m-1}\eta(1+\eta).
\end{aligned}
\end{equation}
Plugging $\eta = \sqrt{\log (2/\rho)/2m}$ into Eq.~\eqref{eq:variance-estimation-3} yields the desired result.
Note that by solving $\frac{1}{(m-1)} + \frac{4m}{m-1}\eta(1+\eta)\leq \alpha$ with $\eta = \sqrt{\log (2/\rho)/2m}$ with conditions $\alpha > 0$ and $0 < \rho < 1$, we have\footnote{We exclude another solution $0 < m < 1$ since $m$ is an integer.}
\begin{equation}
    m \geq 1 + \frac{\alpha + 2\log(2/\rho)(2+\alpha)+2\sqrt{2}\sqrt{\log(2/\rho)(1+\alpha)(2\log(2/\rho)+\alpha)}}{\alpha^2}.
\end{equation}
\end{proof}

\multi*
\begin{proof}
Since the samples are i.i.d., we have the following union bound for the concentration of sample mean,
\begin{equation}
\begin{aligned}
    \Pr\left[ \bigcup_{i=1}^k \{ |\hat p_{x_i} - p_{x_i}| \geq \nu \} \right] &\leq \prod_{i=1}^k \Pr[ |\hat p_{x_i} - p_{x_i}| \geq \nu] \leq 2k \exp\left(-2 \nu^2 m\right).
\end{aligned}
\end{equation}
Therefore, with probability $1-\rho$, $|\hat p_{x_i} - p_{x_i}| \leq \sqrt{\log (2k/\rho)/2m}$ for $i = 1,\ldots,k$, and the desired result follows the derivation in Proposition~\ref{prop:single}.

\end{proof}

\section{Experimental Details}
\label{sec:exp-details}

\paragraph{Datasets} For illustrative purposes, we use the following classes as our target labels. For the Credit dataset, we use ``Approved'' as the target label. For the Contraception dataset, we use ``long-term method''. For the dermatology dataset, we use ``seboreic dermatitis'' diagnosis. For the Mammography dataset, we use ``malignant''.

\begin{table}[]
\centering
\caption{Summary of datasets used in our experimental evaluations.}
\label{tab:datasets}
\resizebox{.55\linewidth}{!}{
\begin{tabular}{l|rc|rr|l}
\toprule
Dataset       & Size  & Number of features      & Train size & Test size   \\
\midrule
Synthetic     & $\infty$ & 2                       & 2000      & 20,000   \\
Credit        & 653    & 46                      & 489         & 164       \\
Contraception & 1,473  & 9                       & 1,104       & 369       \\
Mammography   & 830    & 5                       & 622         & 208       \\
Dermatology   & 358    & 34                      & 268         & 90        \\
CIFAR-10      & 60,000 & $32 \times 32 \times 3$ & 50,000      & 10,000    \\
\bottomrule
\end{tabular}
}
\end{table}

\paragraph{Model Architecture} For a neural network on CIFAR-10, we use the architecture composed of the following layers:
\begin{enumerate}
    \item Convolutional, $3 \times 32$, kernel size of 3 %
    \item ReLU %
    \item Average pooling, kernel size of 2, stride 2 %
    \item Convolutional, $32 \times 64$, kernel size of 3 %
    \item ReLU %
    \item Average pooling, kernel size of 2, stride 2 %
    \item Convolutional, $64 \times 64$ %
    \item ReLU %
    \item Average pooling, kernel size of 2, stride 2 %
    \item Convolutional, $64 \times 128$, kernel size of 3, stride 2 %
    \item ReLU %
    \item Adaptive average pooling %
    \item Fully connected layer, $128 \times 10$ %
    \item Softmax
\end{enumerate}

\paragraph{Software} We use the following software:
\begin{itemize}
    \item diffprivlib~\cite{diffprivlib} for the implementation of objective-perturbation for logistic regression.
    \item PyTorch~\cite{pytorch} for implementing neural networks.
    \item opacus~\cite{opacus} for training PyTorch neural networks with DP-SGD.
    \item numpy~\cite{numpy}, scipy~\cite{scipy}, and pandas~\cite{pandas} for numeric analyses.
    \item seaborn~\cite{seaborn} for visualizations.
\end{itemize}

\subsection{Additional Figures}\label{app:extras}
The rest of the paper contains additional figures.

\begin{figure}
    \centering
    \includegraphics[width=.42\linewidth]{images/estimator_rate.pdf}
    \caption{Error of estimating disagreement w.p. 95\% as a function of the number of models sampled from the training distribution $P_{\train(\dataset)}$.}
    \label{fig:estimator-rate}
\end{figure}

\begin{figure}
    \centering
    \includegraphics[width=.42\linewidth]{images/estimator_rate_vs_real_error.pdf}
    \caption{Empirical error of estimating disagreement over 10 replications for the output-perturbation mechanism for one arbitarily chosen example, compared to the theoretical bound on error w.p. 95\%. This suggest that the theoretical upper bound on error is pessimistic in practice. y axis is logarithmic.}
    \label{fig:estimator-rate-vs-real-error}
\end{figure}

\section{Introduction}

In many high-stakes prediction tasks (e.g., lending, healthcare), training data used to fit parameters of machine-learning models are privacy-sensitive. A standard technical approach to ensure privacy is to use training procedures that satisfy \emph{differential privacy} (DP)~\cite{dwork2006calibrating, dwork2014algorithmic}. DP is a formal condition that, intuitively, guarantees a degree of plausible deniability on the inclusion of an individual sample in the training data. In order to satisfy this condition, non-trivial differentially-private training procedures use some degree of randomization (see, e.g., \citet{chaudhuri2011differentially,abadi2016deep}). The noisy nature of DP mechanisms is key to guarantee plausible deniability of a record's inclusion in the training data.
Unfortunately, randomization comes at a cost: it often leads to decreased accuracy compared to non-private training~\cite{jayaraman2019evaluating}. Reduced accuracy, however, is not the only cost incurred by differentially-private training. DP mechanisms can also increase \emph{predictive multiplicity}, discussed next.

In a prediction task, there can exist multiple models that achieve comparable levels of accuracy yet output drastically different predictions for the same input. This phenomenon is known as predictive multiplicity~\cite{marx2020predictive}, and has been documented in multiple realistic machine-learning settings~\cite{marx2020predictive, hsu2022rashomon, watson2022predictive}. Predictive multiplicity can appear due to under-specification and randomness in the model's training procedure~\cite{d2020underspecification}.

Predictive multiplicity formalizes the \emph{arbitrariness} of decisions based on a model's output. In practice, predictive multiplicity can lead to questions such as ``\emph{Why has a model issued a negative decision on an individual's loan application if other models with indistinguishable accuracy would have issued a positive decision?}'' or ``\emph{Why has a model suggested a high dose of a medicine for an individual if other models with comparable average accuracy would have prescribed a lower dose?}'' These examples highlight that acting on predictions of a single model without regard for predictive multiplicity can result in arbitrary decisions. Models produced by training algorithms that exhibit high predictive multiplicity face fundamental challenges to their credibility and justifiability in high-stakes settings ~\cite{d2020underspecification,black2022model}.

In this paper, we demonstrate a fundamental connection between privacy and predictive multiplicity: For a fixed training dataset and model class,  DP training results in models that ensure the same degree of privacy and achieve comparable accuracy, yet assign conflicting outputs to individual inputs. DP training produces conflicting models even when non-private training results in a single optimal model. Thus, in addition to decreased accuracy, DP-ensuring training methods also incur an arbitrariness cost by exacerbating predictive multiplicity. We show that the degree of predictive multiplicity varies wildly across individual inputs and can disproportionately impact certain population groups. \cref{fig:syn-demo} illustrates the predictive-multiplicity cost of DP training in a simple synthetic example (see \cref{sec:exp} for examples on real-world datasets).

Our main contributions are:
\begin{enumerate}
    \item We provide the first analysis of the predictive-multiplicity cost of differentially-private training.
    \item We analyze a method for estimating the predictive-multiplicity properties of randomized training algorithms using re-training. We derive the first bound on the sample complexity of estimating predictive multiplicity with this approach. Our bound enables practitioners to determine the number of re-trainings required to estimate the predictive-multiplicity cost of randomized training algorithms up to a desired level of accuracy.
    \item We conduct a theoretical analysis of the predictive-multiplicity cost of the output perturbation mechanism~\cite{chaudhuri2011differentially} used to obtain differentially-private models. We characterize the exact dependence of predictive multiplicity on the level of privacy for this method.
    \item We conduct an empirical study of predictive multiplicity of two practical DP-ensuring learning algorithms: DP-SGD~\cite{abadi2016deep} and objective perturbation~\cite{chaudhuri2011differentially}. We use one synthetic dataset and five real-world datasets in the domains of finance, healthcare, and image classification. Our results confirm that, for these mechanisms, increasing the level of privacy invariably increases the level of predictive multiplicity. Moreover, we find that different examples exhibit different levels of predictive multiplicity. In particular, different demographic groups have different average levels of predictive multiplicity.
\end{enumerate}

In summary, the level of privacy in DP training significantly impacts the level of predictive multiplicity. This, in turn, means that decisions supported by differentially-private models can have an increased level of arbitrariness: a given decision would have been different had we used a different random seed in training, even when all other aspects of training are kept fixed and the optimal non-private model is unique. Before deploying DP-ensuring models in high-stakes situations, we suggest that practitioners quantify predictive multiplicity of these models over salient populations and---if possible to do so without violating privacy---measure predictive multiplicity of individual decisions during model operation. Such audits can help practitioners evaluate whether the increase in privacy threatens the justifiability of decisions, choose whether to enact a decision based on a model's output, and determine whether to deploy a model in the first place.

\section{Technical Background}
\label{sec:background}

\subsection{Problem Setup and Notation}
We consider a classification task on a \emph{training dataset} $\mathcal{D} ~\triangleq~ \{(x_i, y_i)\}_{i=1}^n$ consisting of examples $x_i \in \mathcal{X}$ along with their respective labels $y_i \in \mathcal{Y}$.
In this work, we focus on the setting of binary classification, $\mathcal{Y} = \{0, 1\}$.
The goal of a classification task is to use the dataset to train a classifier $f_\theta: \mathcal{X}\to\mathcal{Y}$, which accurately predicts labels for input examples in a given \emph{test dataset} $\mathcal{D}_\mathrm{test} \in 2^{\mathcal{X} \times \mathcal{Y}}$, where $2^{\mathcal{X} \times \mathcal{Y}}$ denotes the power set over $\mathcal{X} \times \mathcal{Y}$.
Each classifier $f_\theta(x)$ is parameterized by a vector $\theta \in \Theta \subseteq \mathbb{R}^d$.
We study randomized training algorithms $T: (\mathcal{X}\times\mathcal{Y})^n \to\Theta$, which produce a parameter vector of a classifier in a randomized way. Thus, given a training dataset, $T(\mathcal{D})$ is a random variable. We denote by $P_{\train(\dataset)}$ the \emph{model distribution}, the probability distribution over $\Theta$ generated by the random variable $T(\mathcal{D})$.

In general, the source of randomness in the training procedure could include, e.g., random initializations of $\theta$ prior to training. However, we consider only sources of randomness which are introduced by privacy-preserving techniques, as we explain in the next section. Throughout this paper, the datasets, as well as any input example $x \in \mathcal{X}$, are not random variables but fixed values. The only randomness we consider in our notation is due to the internal randomization of the training procedure $T(\cdot)$. %
Finally, $I_d$ denotes the $d$-by-$d$ identity matrix, and $\mathbb{1}(\cdot)$ denotes the indicator function.

\subsection{Differentially Private Learning}
\label{sec:dp-bg}
Learning with differential privacy (DP) is one of the standard approaches to train models on privacy-sensitive data~\cite{dwork2006calibrating, dwork2014algorithmic}.
A randomized learning algorithm $T(\cdot)$ is $(\varepsilon, \delta)$-differentially private (DP) if for any two \emph{neighbouring datasets} (i.e., datasets differing by at most one example) $\mathcal{D}, \mathcal{D}' \in (\mathcal{X} \times \mathcal{Y})^n$, for any subset of parameter vectors $A \subseteq \Theta$, it holds that
\begin{equation}
    \Pr[ T(\mathcal{D}) \in A ] \leq \exp(\varepsilon) \Pr[ T(\mathcal{D}') \in A] + \delta.
\end{equation}
In other words, the respective probability distributions of models produced on any two neighbouring datasets should be similar to a degree defined by parameters $(\varepsilon, \delta)$. The parameters represent the level of privacy: low $\varepsilon$ and low $\delta$ mean better privacy. DP mathematically encodes a notion of plausible deniability of the inclusion of an example in the dataset.

There are multiple ways to ensure DP in machine learning. We describe next the \emph{output perturbation mechanism}, which we theoretically analyze in \cref{sec:out-pert}.

\paragraph{Output perturbation mechanism \cite{rubinstein2009learning, chaudhuri2011differentially, wu2017bolt}.} Output perturbation is a simple mechanism for achieving DP that takes an output parameter vector of a non-private training procedure, and privatizes it by adding random noise, e.g., sampled from the isotropic Gaussian distribution. Concretely, suppose that $T_\mathsf{np}: (\mathbb{X} \times \mathbb{Y})^n \rightarrow \Theta$ is a non-private learning algorithm. Denoting its output parameters as $\theta_\mathsf{np} = T_\mathsf{np}(\mathcal{D})$, we obtain the privatized parameters $\theta_\mathsf{priv} \in \Theta$ as follows:
\begin{equation}\label{eq:out-pert}
    \theta_\mathsf{priv} = \theta_\mathsf{np} + \xi, \text{ where } \xi \sim \mathcal{N}(0, \sigma^2 I_d)
\end{equation}
The exact level of DP provided by this procedure depends on the choice the non-private training algorithm $T_\mathsf{np}(\mathcal{D})$. In particular, to achieve $(\varepsilon, \delta)$-DP, it is sufficient to set the noise scale $\sigma = C \cdot \nicefrac{\sqrt{2 \log(1.25 / \delta)}}{\varepsilon}$,
where $C ~\triangleq~ \max_{\mathcal{D} \sim \mathcal{D}'} \| T_\mathrm{np}(\mathcal{D}) - T_\mathrm{np}(\mathcal{D}') \|_2$ is the \emph{sensitivity} of the non-private training algorithm, the maximum discrepancy in terms of the $\ell_2$ distance between parameter vectors obtained by training on any two neighbouring datasets $\mathcal{D}, \mathcal{D}'$.

Denoting by $T(\mathcal{D}) = T_\mathrm{np}(\mathcal{D}) + \xi$ the output-perturbation procedure in \cref{eq:out-pert}, we treat $T(\mathcal{D})$ as a random variable over the randomness of the injected noise $\xi$. Other methods to achieve DP such as objective perturbation~\cite{chaudhuri2011differentially} also inject noise as part of training. In those cases, we similarly consider $T(\mathcal{D})$ as a random variable over such injected noise, and treat all other aspects of training such as pre-training initialization as fixed.

\subsection{Predictive Multiplicity}

Predictive multiplicity occurs when multiple classification models achieve comparable average accuracy yet produce conflicting predictions on a given example \cite{marx2020predictive}. To quantify predictive multiplicity in randomized training, we need to measure dissimilarity of predictions among the models sampled from the probability distribution $P_{\train(\dataset)}$ induced by differentially-private training. For this, we use a definition of \emph{disagreement} which has appeared in different forms in \cite{black2022model,d2020underspecification,marx2020predictive}. For a given fixed input example $x \in \mathcal{X}$, we define the disagreement $\mu(x)$ as:
\begin{equation}\label{def:disagreement}
    \mu(x) ~\triangleq~ 2 \Pr_{\theta, \theta' \sim P_{\train(\dataset)}}[f_{\theta}(x) \neq f_{\theta'}(x)].
\end{equation}
In the above definition, $\theta, \theta' \sim P_{\train(\dataset)}$ denotes two models sampled independently from $P_{\train(\dataset)}$. We use a scaling factor of two in order to ensure that $\mu(x)$ is in the $[0, 1]$ range for the ease of interpretation. Note that both the dataset $\mathcal{D}$ used in training and the input example for which we compute the level of predictive multiplicity are fixed, and the randomness is due to internal randomization of the training procedure $T(\cdot)$. A disagreement value $\mu(x)\approx 1$ indicates that the prediction for $x$ is approximately equal to an unbiased coin flip. Moreover, a disagreement $\mu(x)\approx 0$ implies that, with high probability, the prediction for $x$ does not significantly change if two models are independently sampled from $P_{\train(\dataset)}$ (e.g., by re-training a model twice with different random seeds).

When evaluating dissimilarity across models, many prior works that study predictive multiplicity (e.g.,~\cite{marx2020predictive, semenova2022existence, hsu2022rashomon, watson2022predictive}) only consider models which surpass a certain accuracy threshold.
Although conditioning on model accuracy is theoretically valid, it can bring about confusion in the context of private learning, as in practice such conditioning would demand special mechanisms in order to satisfy DP (see, e.g., \cite{papernot2021hyperparameter}). In particular, first applying a DP training method that guarantees an $(\varepsilon,\delta)$-level of privacy, and then selecting or discarding the resulting model based on accuracy, would result in models that violate the initial $(\varepsilon,\delta)$-DP guarantees.
We note, however, that our results and experiments involving estimation of predictive multiplicity in \cref{sec:estimator,sec:exp} extend to the case in which we add  additional conditioning on top of  model distribution $P_{\train(\dataset)}$ to control for accuracy.

Before proceeding with our analyses of disagreement, we first state a simple yet useful relation between disagreement and statistical variance. Observe that for a given input $x$, the output prediction $f_\theta(x)$ is a random variable over the randomness of the training procedure $\theta \sim P_{\train(\dataset)}$. As we assume that the decisions are binary, and training runs are independent, we have that $f_\theta(x) \sim \mathrm{Bernoulli}(p_x)$ for some input-specific parameter $p_x$.
Having noted this fact, we show that disagreement, defined in \cref{def:disagreement}, can be expressed as a continuous transformation of $p_x$:
\begin{restatable}{proposition}{multvar}\label{stmt:mult-var}
For binary classifiers, disagreement for a given example $x \in \mathcal{X}$ is proportional to variance of decisions over the distribution of models generated by the training algorithm:
\begin{equation}
    \mu(x) = 4 \, \mathrm{Var}_{\theta \sim P_{\train(\dataset)}}(f_\theta(x)) = 4p_x \, (1-p_x).
\end{equation}
\end{restatable}
We provide the proof of this and all the following formal statements in \cref{app:proofs}.

\section{Predictive Multiplicity of Output Perturbation}
\label{sec:out-pert}

\begin{figure}
    \centering
    \includegraphics[width=.4\linewidth]{images/out_pert_dis.pdf}~
    \includegraphics[width=.376\linewidth]{images/out_pert_dis_eps.pdf}
    \caption{\textbf{The noise scale in output perturbation mechanisms increases predictive multiplicity for examples which do not attain high non-private prediction confidence.} On the left, the x axis shows the noise scale used for output perturbation (higher values of $\sigma$ correspond to better privacy). The noise scale corresponds to different levels of privacy depending on the sensitivity of the non-private training algorithm and the $\delta$ parameter (see \cref{sec:dp-bg}). On the right, the x axis (logarithmic scale) shows a possible level of privacy $\varepsilon$ for $\delta = 10^{-5}$, assuming that the non-private training algorithm has sensitivity of $C = 0.2$. The y axis shows the hypothetical prediction confidence for a given example. The color intensity shows the level of disagreement (darker means higher disagreement).}
    \label{fig:out-pert}
\end{figure}

To demonstrate how DP training can lead to an increase in predictive multiplicity, we theoretically analyze the multiplicity properties of the output-perturbation mechanism described in \cref{sec:dp-bg}.

Following \citet{chaudhuri2011differentially} and~\citet{wu2017bolt}, we study the case of logistic regression. In a logistic-regression model parameterized by vector $\theta \in \mathbb{R}^d$, we compute a \emph{confidence} value of an example $x \in \mathcal{X} \subseteq \mathbb{R}^d$ as $\mathsf{sigmoid}(\theta^\intercal x)$, where $\mathsf{sigmoid}(t) ~\triangleq~ (1 + \exp(-t))^{-1}$. If the confidence value is higher than 0.5, then the decision is positive. Otherwise, it is negative. Thus, the decision is obtained as $f_\theta(x) = \mathbb{1}[\mathsf{sigmoid}(\theta^\intercal x) > 0.5]$. Note that the quantity $\theta^\intercal x$ is interchangeable with confidence, as it can be obtained using an invertible transformation. We show the exact relationship between disagreement and the scale of noise $\sigma$ in this setting:

\begin{restatable}{proposition}{outpert}
\label{prop:outpert}
Let $\theta_\mathsf{np} = T_\mathsf{np}(\mathcal{D})$ be a non-private parameter vector of a logistic-regression model. Suppose that the privatized $\theta_\mathsf{priv}$ is obtained using Gaussian noise of scale $\sigma$ as in \cref{eq:out-pert}. Then, the disagreement of a private logistic-regression model parameterized by $\theta_\mathsf{priv}$ is:
\begin{equation}\label{eq:mult-out-pert}
    \mu(x) = 4 \, p_x (1 - p_x), \text{where $p_x = \Phi\left(\frac{\theta_\mathrm{np}^\intercal \, x}{\|x\| \cdot \sigma}\right)$.}
\end{equation}
\end{restatable}

We visualize the relationship in \cref{fig:out-pert}, assuming the input space is normalized so that $\|x\| = 1$. There are two main takeaways from this result. First, disagreement is high when the level of privacy is high. Second,  the level of multiplicity is unevenly distributed across input examples. This is because the exact relationship between multiplicity and privacy also depends on the confidence of the non-private model, $\mathsf{sigmoid}(\theta_\mathsf{np}^\intercal \, x)$, with lower-confidence examples generally having higher multiplicity in this setting. We note that, in this illustration, the simple relationship between confidence and predictive multiplicity is an artifact of normalized features, i.e.,  $\|x\| = 1$. In general, examples with high-confidence predictions can display high predictive multiplicity after DP-ensuring training, as illustrated in \cref{fig:syn-demo}.

Other methods for DP training, such as gradient perturbation~\cite{abadi2016deep}, are not as straightforward to analyze theoretically. In the next sections, we study predictive multiplicity of these algorithms using a Monte-Carlo method.

\section{Measuring Predictive Multiplicity of Randomized Algorithms}
\label{sec:estimator}
Theoretically characterizing predictive multiplicity of DP algorithms beyond the output-perturbation mechanism and for more complex model classes is a challenging problem (see, e.g.~\cite[Section~4]{hsu2022rashomon}). For instance, the accuracy and generalization behavior of the DP-SGD algorithm \cite{abadi2016deep} used for DP training of neural networks is an active area of research (e.g., \cite{wang2023generalization}). Even in simpler model classes, where training amounts to solving a convex optimization problem (e.g., support vector machines), DP mechanisms such as objective perturbation \cite{chaudhuri2011differentially} display a complex interplay between privacy, accuracy, and distortion of model parameters.

For these theoretically intractable cases, we adopt a simple Monte-Carlo strategy first used by \citet{d2020underspecification}: Train multiple models on the same dataset with different randomization seeds, and compute statistics of the outputs of these models. In this section, we formalize this simple and intuitive approach, and provide the first sample complexity bound for estimating predictive multiplicity. Our bound has a closed-form expression, so a practitioner can use it to determine how many re-trainings are required  to estimate predictive multiplicity up to a given approximation error.

At first, re-training might appear as a blunt approach for analyzing predictive multiplicity in DP. Our results indicate that this is not the case.  Surprisingly, we prove that, if one wants to estimate disagreement in \cref{def:disagreement} for $k$ input examples, the number of required re-trainings increases \emph{logarithmically} in $k$.  This result demonstrates that re-training can be an effective strategy to estimate predictive multiplicity regardless of the intricacies of a specific DP mechanism, and that a moderate number of re-trainings is sufficient to estimate disagreement for a large number of examples.

Recall that, according to \cref{stmt:mult-var}, disagreement of an example $x$ is proportional to the variance of outputs within the model distribution $P_{\train(\dataset)}$. We use this connection to provide an unbiased estimator for disagreement.
\begin{restatable}{proposition}{unbiasedest}
Suppose we have $m$ models sampled from the model distribution: $\theta_1, \theta_2, \ldots, \theta_m \sim P_{\train(\dataset)}$. Then, the following expression is an unbiased estimator for disagreement $\mu(x)$ for a single example $x \in \mathcal{X}$:
\begin{equation}\label{eq:disagreement-estimator}
\hat \mu(x) ~\triangleq~ 4 \, \frac{m}{m-1} \, \hat p_x(1 - \hat p_x),
\end{equation}
where $\hat p_x = \frac{1}{m} \sum_{i = 1}^m f_{\theta_i}(x)$ is the sample mean of $f_\theta(x)$.
\end{restatable}

How many models $\theta_1, \theta_2, \ldots, \theta_m$ do we need to sample in order to estimate disagreement?
To answer this, we provide an upper bound on estimation accuracy given the number of samples from the model distribution, as well as a bound on the number of samples required for a given level of estimation accuracy.
\begin{restatable}{proposition}{single}\label{prop:single}
    For $m$ models sampled from the model distribution, $\theta_1, \theta_2, \ldots, \theta_m \sim P_{T(\mathcal{D})}$, with probability at least $1 - \rho$, for $\rho \in (0, 1]$ the additive estimation error $\alpha ~\triangleq~ |\hat \mu(x)-\mu(x)|$ satisfies:
    \begin{equation}
    \alpha \leq \frac{1}{(m-1)} + 4 \frac{m}{m-1}\sqrt{\frac{\log(2/\rho)}{2m}}\left(1+\sqrt{\frac{\log(2/\rho)}{2m}}\right).
    \end{equation}
\end{restatable}

For example, this bound yields that 5,000 re-trainings result in the estimation error of at most $0.08$ with probability $95\%$. In \cref{app:estimator}, we provide a closed-form expression for computing the number of samples $m$ required to achieve a given error level $\alpha$. We also provide a visualization of the bound in \cref{fig:estimator-rate} (\cref{app:extras}).

In practice, one might need to estimate disagreement for multiple examples, e.g., to compute average disagreement over a test dataset. When doing so na\"ively, the re-training costs could mount to infeasible levels if we assume that each estimation requires the same number of model samples $m$ for each input example. In contrast, we show that in such cases sample complexity grows only logarithmically.

\begin{restatable}{proposition}{multi}\label{prop:multi}
Let $x_1, x_2, \ldots, x_k \in \mathbb{X}$.
If $\theta_1, \theta_2, \ldots, \theta_m \sim P_{\train(\dataset)}$ are i.i.d. samples from the model distribution, then with probability at least $1 - \rho$, for $\rho \in (0, 1]$ the maximum additive error satisfies:
    \begin{equation}
    \max_{i \in 1, \ldots, k} |\mu(x_i) - \hat \mu(x_i)| \leq \frac{1}{(m-1)} + \frac{4m}{m-1}\sqrt{ \frac{\log (2k/\rho)}{2m}}\left(1+\sqrt{\frac{\log (2k/\rho)}{2m}}\right).
    \end{equation}
\end{restatable}
This positive result shows that auditing models for predictive multiplicity for large populations and datasets is practical, as the sample complexity grows slowly in the number of examples.

\section{Empirical Studies}
\label{sec:exp}
In this section, we empirically explore the predictive multiplicity  of DP algorithms. We use a low-dimensional synthetic dataset in order to visualize the level of multiplicity across the input space. To study predictive-multiplicity effects in realistic settings, we use real-world tabular datasets representative of high-stakes domains, namely lending and healthcare, and one image dataset.
The code to reproduce our experiments is available at \href{https://github.com/spring-epfl/dp_multiplicity}{github.com/spring-epfl/dp\_multiplicity}.

\subsection{Experimental Setup}

\paragraph{Datasets and Tasks}

We use the following datasets in our evaluations:
\begin{itemize}
\item A \textbf{Synthetic} dataset containing data belonging to two classes with class-conditional distributions $X_0 \sim \mathcal{N}(\mu_0, \Sigma_0)$ and $X_1 \sim \mathcal{N}(\mu_1, \Sigma_1)$, respectively. We set the distribution parameters to be:
\begin{equation}
    \begin{aligned}
    &\mu_0 = [1, 1], &\Sigma_0 = \begin{pmatrix}1 & \nicefrac{1}{2} \\ \nicefrac{1}{2} & 1\end{pmatrix} \,\,\,\, \text{and } \,\,\,\,%
    &\mu_1 = [-1, -1], &\Sigma_1 = \begin{pmatrix}1 & \nicefrac{1}{10} \\ \nicefrac{1}{10} & 1\end{pmatrix}
    \end{aligned}
\end{equation}
The classes in this synthetic dataset are well-separable by a linear model (see \cref{fig:syn-demo}) %

    \item Credit Approval tabular dataset (\textbf{Credit}). The task is to predict whether a credit card application should be approved or rejected based on several attributes which describe the application and the applicant.
    \item Contraceptive Method Choice tabular dataset (\textbf{Contraception}) based on 1987 National Indonesia Contraceptive Prevalence Survey. The task is to predict the choice of a contraception method based on demographic and socio-economic characteristics of a married couple.
    \item Mammographic Mass tabular dataset (\textbf{Mammography}) collected at the Institute of Radiology of the University Erlangen-Nuremberg in 2003 -- 2006. The task is to predict whether a screened tumor is malignant or benign based on several clinical attributes.
    \item \textbf{Dermatology} tabular dataset. The task is to predict a dermatological disease based on a set of clinical and histopathological attributes.
    \item \textbf{CIFAR-10}~\cite{krizhevsky2009learning}, an \emph{image} dataset of pictures labeled as one of ten classes. The task is to predict the class.
\end{itemize}
We take the realistic datasets (Credit, Contraception, Mammography, and Dermatology) from the University of California Irvine Machine Learning (UCIML) dataset repository~\cite{uciml}. \cref{tab:datasets} in \cref{sec:exp-details} provides a summary of characteristics of the datasets. We provide additional details about processing of the datasets in \cref{sec:exp-details}.

For the synthetic dataset, we obtain the training dataset by sampling 1,000 examples from each of the distributions. In order to have precise estimates of population accuracy, we sample a larger test dataset of 20,000 examples. For tabular datasets, we use a random $75\%$ subset for training, and use the rest as a held-out test dataset for model evaluations. For CIFAR-10, we use the default 50K/10K train-test split.

\paragraph{Models and Training Algorithms}
For the synthetic and tabular datasets, we use logistic regression with objective perturbation~\cite{chaudhuri2011differentially}.
For the image dataset, we use an AlexNet-inspired~\cite{krizhevsky2017imagenet} convolutional neural network consisting of four convolutional layers and one linear layer on top. We train the network using a variant of DP-SGD~\cite{abadi2016deep} with Adam optimizer~\cite{kingma2014adam} for 50 epochs, learning rate of $10^{-3}$, and batch size of 64. To compute the $(\varepsilon, \delta)$-DP guarantees, we use the state-of-the-art numerical analysis by \citet{gopi2021numerical}. We provide the detailed model architecture and information about the used software in \cref{sec:exp-details}.

\paragraph{Metrics} The goal of our experiments is to quantify predictive multiplicity and explain the factors which impact it. For all settings, we measure disagreement to capture the dissimilarity of predictions, and accuracy of the models to quantify the effect of performance on multiplicity. Concretely, we measure:
\begin{itemize}
    \item Average \textbf{disagreement} for examples on a test dataset, computed using the unbiased estimator in \cref{sec:estimator}. As this disagreement metric is tailored to binary classification, we use a special procedure for the ten-class task on CIFAR-10: we treat each multi-class classifier as ten binary per-class classifiers, and we report average disagreement across those ten per-class classifiers.
    \item \textbf{Normalized accuracy} on a test dataset. We report accuracy in a normalized way to account for imbalance of classes in some datasets. We compute normalized accuracy as $2 \cdot (\mathtt{acc} - \mathtt{baseline})$, where $\mathtt{acc}$ is the accuracy of a given model, and $\mathtt{baseline}$ is the accuracy of a mode classifier which outputs the most common class. We multiply it by a factor of two to ensure that the normalized accuracy is in the range $[0, 1]$.
\end{itemize}

\paragraph{Experiment Outline}
For a given dataset and a value of the privacy parameter $\varepsilon$, we train multiple models on exactly the same data \textit{with different randomization seeds}. %

For the synthetic and tabular datasets, we use several values of $\varepsilon$ between 0.5 (which provides a good guaranteed level of privacy~\cite[see, e.g.][Section 4]{wood2018differential}) and 5.0. For each value of $\varepsilon$ we train at least $m = 5000$ models.
For CIFAR-10, we train $m = 50$ neural-network models because of computational constraints. We use DP-SGD parameters that provide privacy guarantees from $\varepsilon = 0.1$ to $\varepsilon = 8$ at the standard choice of $\delta = 10^{-5}$.

As DP significantly decreases accuracy when the training dataset is small, the models trained on our relatively small four tabular datasets oftentimes perform worse than the baseline predictor which outputs the most common class. To avoid such trivial models, when computing our metrics on the tabular datasets we omit the lowest quartile of models in terms of performance. In other words, once we have trained all models, we only use the top $75\%$ of them in terms of accuracy, for each tabular dataset, and omit the rest. Even after discarding the lowest quartile of models on tabular datasets, we have with probability 95\% that the additive error of any input's disagreement estimate is at most 0.09 according to \cref{prop:single}. In practice, however, we observe that the estimates are even more accurate than indicated by the theoretical sample-complexity bound (see \cref{fig:estimator-rate-vs-real-error} in \cref{app:extras}).

\begin{figure}
    \centering
    \begin{subfigure}[t]{.7\textwidth}
        \hspace{1cm}
        \includegraphics[width=\linewidth]{images/tabular_mult.pdf}
        \vspace{-1.2em}
        \caption{Tabular datasets}
    \end{subfigure}
    \\[.5em]
    \begin{subfigure}[t]{.58\textwidth}
        \includegraphics[width=\linewidth]{images/cifar10_mult.pdf}
        \vspace{-1.2em}
        \caption{Image dataset (CIFAR-10)}
    \end{subfigure}

    \caption{\textbf{Increasing the level of privacy increases the level of predictive multiplicity in real-world datasets.} For all plots, the x axis shows the level of privacy ($\varepsilon$, lower value is more privacy). The plots on the left show normalized test-set accuracy $2 \cdot (\mathtt{acc} - \mathtt{baseline})$, so $0$ means no improvement over the baseline performance. The error bands/bars on the left side are 95\% confidence intervals (CI) over the models in the model distribution. The plots on the right show the degree of disagreement across the top 75\% of models in terms of accuracy in the case of tabular datasets, and across $m = 50$ models in the case of CIFAR-10. The error bands on the right side are 95\% CI over the examples in a test dataset.}
    \label{fig:mult-main}
    \vspace{-1em}
\end{figure}

\subsection{Predictive Multiplicity and Privacy}
First, we empirically study how multiplicity evolves with increasing privacy. In \cref{fig:syn-demo}, we visualize the two-dimensional synthetic examples and their disagreement for different privacy levels.
As privacy increases, so do the areas for which model decisions exhibit high disagreement (darker areas).
Although the regions with higher disagreement correlate with model confidence and accuracy, the level of privacy contributes significantly. For instance, some points which are relatively far from the decision boundary, which means they are confidently classified as either class, can nevertheless have high predictive multiplicity.

\cref{fig:mult-main} shows the experimental results for our tabular datasets and CIFAR-10. On the left side, we show the relationship between the privacy level and accuracy. On the right, between the privacy level and disagreement. As with the theoretical analysis and the results on synthetic data, we can clearly see that models with higher level of privacy (low $\varepsilon$) invariably exhibit higher predictive multiplicity, even when discarding the 25\% least accurate models in the case of tabular datasets.

\vspace{1mm}\noindent\textbf{Implications.} The increase in the level of privacy results in making more decisions which are largely or completely explained by randomness in training. Let us give an example with a concrete data record from the Mammography dataset representing a 67-year-old patient labeled as having a malignant tumor.
Classifiers with low level of privacy $\varepsilon=4.0$ predict the benign class for this individual a quarter of the time (approx. 50\% disagreement). If we set the level of privacy to the high $\varepsilon=0.5$, this record is classified close to 50\% of the time as benign, and 50\% of the time as malignant (approx. 97\% disagreement), despite the classifiers attaining non-trivial test accuracy, and the record receiving prediction confidence of 60\% on average over the classifiers at this privacy level. Thus, if one were to use a model with this level of privacy to inform treatment of this patient, the model's decision would have been as useful as a coin flip.

\subsection{What Causes Predictive Multiplicity to Increase?}

In the previous section, we showed that the increase in privacy causes an increase in predictive multiplicity. It is not clear, however, what is the exact mechanism through with DP impacts predictive multiplicity. Hypothetically, the contribution to multiplicity could be through two pathways:
\begin{enumerate}
    \item[(1)] \emph{Direct:} The increase in predictive multiplicity is the result of the variability in the learning process stemming from randomization, regardless of accuracy decrease.
    \item[(2)] \emph{Indirect}: The increase in predictive multiplicity is the result of the decrease in accuracy.
\end{enumerate}

\begin{figure}
    \centering
    \includegraphics[width=.4\linewidth]{images/mult_vs_acc.pdf}
    \caption{\textbf{Models achieving a similar level of accuracy can have different levels of predictive multiplicity.} The plot shows the top 5\% percentile of disagreement on the synthetic test dataset for all models which attain at least certain level of normalized accuracy, for different values of the privacy parameter ($\varepsilon$, lower value is more privacy). The x axis shows the deviation of normalized accuracy from that of an optimal non-private model, with 0 being equal to the accuracy of the optimal non-private model. As even such a small decrease in accuracy as 0.01 can see disagreement rise from 0 to 0.8 for some examples, this result suggests that the change in the level of privacy on its own can cause a big change in disagreement. %
    }
    \label{fig:syn-mult-acc}
\end{figure}

These two options are not mutually exclusive, and it is possible that both play a role.
In both cases, the desire for a given level of privacy---which determines the degree of  randomization added during training---is ultimately the cause of the increase in multiplicity. Nevertheless, how randomization contributes to the increase has practical implications: If our results are explained by pathway (2), we should be able to reduce the impact of privacy on predictive multiplicity by designing algorithms which achieve better accuracy at the same privacy level.

For output perturbation, our theoretical analysis in \cref{sec:out-pert} shows that multiplicity is directly caused by randomization---pathway (1)---as only the privacy level, confidence, and the norm of a predicted example impact disagreement. Therefore, accuracy does not have a direct impact on predictive multiplicity in output perturbation.

In \cref{fig:syn-mult-acc}, to quantify the impact of accuracy on predictive multiplicity for the case of objective perturbation, we show the top 5\% disagreement values for varying levels of accuracy on the synthetic dataset. We use the synthetic dataset to ensure that test accuracy estimates are reliable, as we have a large test dataset in this case.
We see that, for a given level of accuracy, different privacy parameters can result in different disagreement. This suggests that randomization caused by  DP training \textit{can have a direct effect} on predictive multiplicity, so we observe pathway (1).

\vspace{1mm}\noindent\textbf{Implications.} This observation indicates that there exist cases for which improving accuracy of a DP-ensuring algorithm for a given privacy level \textit{will not} necessarily result in lower predictive multiplicity.

\subsection{Disparities in Predictive Multiplicity}
\label{sec:exp-disparities}
 The visualizations in \cref{fig:syn-demo} show that different examples can exhibit highly varying levels of predictive multiplicity.
This observation holds for real-world datasets too. \cref{fig:tabular-disparities-dist} shows the distributions of the disagreement values across the population of examples in the test data. For example, for most privacy levels, the distribution on the Mammography dataset is multimodal, i.e., there are clusters of individuals who have higher predictive multiplicity. As the level of privacy increases (low $\varepsilon$), the disagreement tends to concentrate around 1, with decisions for most examples explained by randomness in training. This holds even despite us only using the top 75\% of models in terms of accuracy.

Next, we verify if the differences in the level of disagreement also exist across demographic groups. In \cref{fig:tabular-disparities-group}, we show average disagreement across points from four different quartile-based age groups in the Mammography dataset. As before, for low levels of privacy (high $\varepsilon$) we see more disparity in disagreement. The disparities even out as we increase the privacy level (low $\varepsilon$), with groups having average disagreement closer to 1. Thus, disagreement is not only unevenly distributed across individuals, but across salient demographic groups.

\vspace{1mm}\noindent\textbf{Implications.} As some groups and individuals can have higher predictive multiplicity than others, evaluations of training algorithms in terms of their predictive multiplicity must account for such disparities. For instance, our experiments on the Mammography dataset (in \cref{fig:tabular-disparities-group}) show that, for different privacy levels, decisions for patients in the age bracket under 45 years old exhibit higher predictive multiplicity than of patients between 58 and 66 years old. Predictions for patients under 45, therefore, systematically exhibit more dependence on randomness in training than on the relevant features for prediction. This highlights the need to conduct disaggregated evaluations as opposed to only evaluating average disagreement on whole datasets.

\begin{figure*}
    \centering
    \begin{subfigure}[t]{1.0\textwidth}
        \centering
        \includegraphics[width=1.0\linewidth]{images/tabular_pdf.pdf}
        \caption{Distribution of disagreement values across the population in the test set in four tabular datasets.}
        \label{fig:tabular-disparities-dist}
        \vspace{1em}
    \end{subfigure}
    \begin{subfigure}[t]{1\textwidth}
        \centering
        \includegraphics[width=0.75\linewidth]{images/tabular_disparity.pdf}
        \caption{Group-level disparities in disagreement values on the Mammography dataset. Error bars are 95\% confidence intervals over the disagreement values in each subgroup.}
        \label{fig:tabular-disparities-group}
    \end{subfigure}

    \caption{\textbf{The level of predictive multiplicity varies from one example to another, and across population groups. As the level of privacy grows, more predictions exhibit similarly high disagreement.}
    Disagreement is computed on the tabular datasets using the top 75\% of models in terms of accuracy.
    }
    \label{fig:tabular-disparities}
\end{figure*}

\section{Related work}\label{sec:related-work}
\paragraph{Rashomon Effect and Predictive Multiplicity.}
The Rashomon effect, observed and termed by \citet{breiman2001statistical}, describes the phenomenon where a multitude of distinct models achieve similar average loss. The Rashomon effect occurs even for simple models such as linear regression, decision trees, and shallow neural networks \cite{auer1995exponentially}.
When no privacy constraints are present, predictive multiplicity can be viewed as a facet of the Rashomon effect in classification tasks, where similarly-accurate models produce conflicting outputs.
One of the main challenges in studying predictive multiplicity is measuring it.
\citet{semenova2022existence} proposed the Rashomon ratio to measure the Rashomon effect and used a Monte Carlo technique to sample decision tree models for estimation.
\citet{marx2020predictive} quantified predictive multiplicity using optimization formulations to find the worst-case disagreement among all candidate models while controlling for accuracy.
More recently, \citet{hsu2022rashomon} proposed Rashomon Capacity to derive a worst-case metric for predictive multiplicity in multi-class classification tasks.
\citet{black2022model,watson2022predictive} propose measures of predictive multiplicity which are applicable to randomized learning.
Our \cref{prop:multi} complements this prior work by providing a closed-form expression for the sample complexity of estimating predictive multiplicity which arises due to randomness used in training.

\paragraph{Side Effects of Differential Privacy.} To the best of our knowledge, our work is the first one to study the properties of DP training in terms of predictive multiplicity. Multiple works, however, have studied other unintended consequences of private learning. In particular, \citet{bagdasaryan2019differential}, \citet{sanyal2022unfair} show that DP training comes at a cost of decreased performance for groups which are under-represented in the data. Relatedly, \citet{cummings2019compatibility} show that DP training is incompatible with some notions of algorithmic fairness.

\section{Discussion}

Our theoretical and empirical results show that training with DP and, more broadly,  applying randomization in training increases predictive multiplicity. We demonstrated that higher privacy levels result in higher multiplicity.
If a training algorithm exhibits high predictive multiplicity for a given input example, the decisions supported by a model's output for this example lose their justifiability: these decisions depend on the randomness used in training rather than on relevant properties or features of this example.
The connection between privacy in learning and decision arbitrariness might not be obvious to practitioners.
This lack of awareness is potentially damaging in high-stakes settings (e.g., medical diagnostics, lending, education), where decisions of significant---and potentially life-changing---consequence could be significantly influenced by randomness used to ensure privacy.

In this concluding section, we discuss whether predictive multiplicity is indeed a valid concern for DP-ensuring algorithms, and outline a path forward.

\subsection{Can the Increase in Predictive Multiplicity be Beneficial?}
Despite the harms of arbitrariness, one might argue that multiplicity can, in some cases, be beneficial.

\paragraph{Opportunities for Satisfying Desirable Properties Beyond Accuracy?} \citet{black2022model} and~\citet{semenova2022existence} argue that multiplicity presents a valuable opportunity.
In non-private training, the existence of many models that achieve comparable accuracy creates an opportunity for selecting a model which satisfies both an acceptable accuracy level and other useful properties beyond performance, such as fairness \cite{coston2021characterizing}, interpretability \cite{fisher2019all}, or generalizability \cite{semenova2022existence}.
In order to leverage this opportunity, one needs to deliberately steer training towards the model which satisfies  desirable properties beyond accuracy, or search the ``Rashomon set'' of good models \cite{fisher2019all}.
However, with  randomization alone (e.g., adding Gaussian noise to gradients in training), model designers cannot steer training without compromising DP guarantees, and can only arrive at a model which satisfies additional desirable properties by chance. Thus, this positive side of the multiplicity phenomenon  is not necessarily present in DP-ensuring training.

It is an interesting open problem to find whether specially-crafted noise distributions or post-processing techniques could be designed to provide the same level of privacy as the standard approaches, and at the same time attain additional useful properties such as fairness.

\paragraph{Predictive Multiplicity is Individually Fair?}
Individual fairness~\cite{dwork2012fairness} is a formalization of the ``treat like alike'' principle: an individually fair classifier makes similar decisions for individuals who are thought to be similar.
A way to formally satisfy individual fairness is, in fact, through randomization of decisions. This could lead to an argument that predictive multiplicity is individually fair. For instance, suppose that a predictive model used to assist with hiring decisions is applied to several individuals who are all equally qualified to get the job. Consider two possible decision rules for selecting the candidate to hire with different multiplicity levels. The first rule
 has high multiplicity: produce a random decision. The second rule has low multiplicity: select a candidate based on lexicographic order.
As the second decision rule results in a breach of individual fairness and, possibly, a systemic exclusion of some candidates, the first rule with high multiplicity seems preferable.%

This argument, however, only holds if there is randomness \textit{at the prediction stage}. This is not the case for standard DP-ensuring algorithms such as the ones we study. DP training produces one deterministic classifier that is used for all predictions.
Thus, once training is done, there is no randomization of decisions as in the example above. Thus, the decisions due to such DP-ensuring models are no different than arbitrary rules such as selection based on lexicographic ordering.

\paragraph{Overcoming the Algorithmic Leviathan?}
\citet{creel2022algorithmic} consider a setting where different decision-making systems which have high impact on an individual's livelihood, e.g., credit scoring systems from competing bureaus in the USA~\cite{citron2014scored}, are trained in ways that lead to all of them outputting the same decisions.
This \textit{algorithmic monoculture} would completely remove the possibility of accessing resources for some individuals, as turning to a competing decision-maker would not change the outcome.
In this case, \citeauthor{creel2022algorithmic} argue that high predictive multiplicity could be a desirable property as it enables to access resources across the decision-makers.

We note that in some high-stakes settings, such as healthcare, an algorithmic monoculture might \emph{not} pose a concern. Indeed, one would wish that predictive models used as a part of a diagnostic procedure for a disease output a consistent decision so that patients can be treated (or not be treated) as needed. In this scenario, in fact, predictive multiplicity could potentially harm patients by either delaying a patient's treatment, or recommending a treatment when the patient is healthy.
In such settings, the positive impact of predictive multiplicity in avoiding an algorithmic Leviathan loses meaning.

Regardless of whether algorithmic monoculture is a legitimate concern or not for a given application, it is helpful for model designers and decision subjects to be informed of the level of predictive multiplicity, whether to gauge the likelihood of recourse, or brace for the arbitrariness of decisions.

\subsection{Open Problems}

\paragraph{Reporting Mutiplicity}
Potential mitigations of the harms of predictive multiplicity could be to abstain from outputting a prediction with high multiplicity, or to communicate the magnitude of  multiplicity to the stakeholders. Doing so is challenging: any sort of communication of disagreement values could partially reveal information about the privacy-sensitive training data and break DP guarantees. Consider, as before, the setting of using a predictive model to assist in a medical diagnosis.
Whether a model abstains from predictions or outputs them along with disagreement estimates, there is a certain amount of information leakage about the training data to doctors. If the disagreement estimates are computed on privacy-sensitive data and are used without appropriate privatization---whether published or used to decide on abstention---they can reveal information about the data.
To address this issue, one could use privacy-preserving technologies such as DP to abstain from making a prediction based on a high disagreement value or report the disagreement estimate, in a privacy-preserving way. However, this privatization is challenging to perform while maintaining utility, as variance of predictions could have high sensitivity to even small changes in the data. Studying whether effective privatization of disagreement computations is possible is an open problem for future work.

\paragraph{General Characterization of the Predictive-Multiplicity Costs of DP}
We have theoretically characterized the predictive-multiplicity behavior of the output-perturbation mechanism as applied to logistic regression. Doing so for other mechanisms and model families is a non-trivial undertaking. In this work, we resort to empirical measurement with re-training. An open problem is finding whether we can characterize these behaviors for a wider range of model families, mechanisms, or even for any general mechanism which satisfies DP.

\subsection{Recommendations Moving Forward}
As discussed in the previous sections, existing techniques do not enable model designers to eliminate, or even mitigate, the implications of predictive multiplicity when using DP-ensuring models.
We have pointed out which open problems would need to be solved in order to reduce the impact of predictive multiplicity in high-stakes privacy-sensitive scenarios. Until DP mechanisms that mitigate multiplicity become available, the negative effects of multiplicity can only be countered by \textit{auditing for multiplicity} prior to deployment. Our evaluations show that standard prediction confidence is not a reliable indicator of multiplicity. Therefore, in order to understand the impact of privacy on the justifiability of model decisions, model designers must directly measure predictive multiplicity when using DP training, e.g., using the methods we introduce in \cref{sec:estimator}. %
If at the desired level of privacy the training algorithm exhibits high predictive multiplicity (either in general or for certain populations), model designers should carefully consider whether the use of such models is justified in the first place.

\section*{Acknowledgements}
This work is partially funded by the Swiss National Science Foundation under grant 200021-188824, and the US National Science Foundation under grants CAREER 1845852, FAI 2040880, and CIF 1900750. Hsiang Hsu acknowledges support from Meta Ph.D. Fellowship. The authors would like to thank Salil Vadhan and Jakab Tardos for their helpful feedback.

\bibliographystyle{plainnat}