text:
\section{Introduction} \label{sec:intro}

 Given a feature space $\mathcal{I}$, a similarity function $\sigma: \mathcal{I}^2 \mapsto \mathbb{R}_{\geq 0}$ measures how comparable any pair of elements $x,x' \in \mathcal{I}$ are. The function $\sigma$ can also be interpreted as a distance function, where the smaller $\sigma(x,x')$ is, the more similar $x$ and $x'$ are. Such functions are crucially used in a variety of AI/ML problems, \emph{and in each such case $\sigma$ is assumed to be known}. Two of the most prominent applications where similarity functions have a central role are clustering and considerations of individual fairness. In clustering, the similarity function serves as the metric space in which we need to create the appropriate clusters. As for the well-known notion of individual fairness introduced in the seminal work of \citet{Dwork2012}, its goal is \emph{treating similar individuals similarly}. Hence, any algorithm that needs to abide by this concept of fairness, should be able to access the similarity value for every pair of individuals that are of interest.

Nonetheless, it is not realistic to assume that a reliable and accurate similarity function is always given. This issue was even raised in the work of \citet{Dwork2012}, where it was acknowledged that the computation of $\sigma$ is not trivial, and thus should be deferred to third parties. The starting point of our work here is the observation that there exist scenarios where computing similarity can be assumed as easy (in other words given), while in other cases this task would be significantly more challenging. Specifically, we are interested in scenarios where there are multiple distributions that produce elements of $\mathcal{I}$. We loosely call each such distribution a ``demographic'' group, interpreting it as the stochastic way in which members of this group are produced. \emph{In this setting, computing the similarity value of two elements that are produced according to the same distribution, seems intuitively much easier compared to computing similarity values for elements belonging to different groups}. We next present a few motivating examples that clarify this statement.

\textbf{Individual Fairness: }
Consider a college admissions committee that needs access to an accurate similarity function for students, so that it provides a similar likelihood of acceptance to similar applicants. Let us focus on the following two demographic groups. The first being students from affluent families living in privileged communities and having access to the best quality schools and private tutoring. The other group would consist of students from low-income families, coming from a far less privileged background. Given this setting, directly comparing two students based on their features (e.g., SAT scores, strength of school curriculum, number of recommendation letters, etc), can be a fair way to elicit their similarity only if the students belong to the same group. It is clear that this trivial approach might hurt less privileged students when they are compared to students of the first group. This is because such a simplistic way of measuring similarity does not reflect potential that is undeveloped due to unequal access to resources. Hence,  accurate across-groups comparisons that take into account such delicate issues, appear considerably more intricate.

\textbf{Clustering: } Suppose that a marketing company has a collection of user data that wants to cluster, with its end goal being a downstream market segmentation analysis. However, as it is usually the case, the data might come from different sources, e.g., data from private vendors and data from government bureaus. In this scenario, each data source might have its own way of representing user information, e.g., each source might use a unique subset of features. Therefore, eliciting the distance metric required for the clustering task should be straightforward for data coming from the same source, while across-sources distances would certainly require extra care, e.g., how can one extract the distance of two vectors containing different sets of features?

For more applications we refer the reader to Appendix \ref{sec:apdx-1}.

As suggested by earlier work on computing similarity functions \citep{ilvento2019}, when obtaining similarity values is an overwhelming task, we can employ the advice of domain experts. Such experts can be given any pair of elements, and in return produce their true similarity value. However, utilizing this experts' advice can be thought of as very costly, and hence it should be used sparingly. For example, in the case of comparing students from different economic backgrounds, the admissions committee can reach out to regulatory bodies or civil rights organizations. Nonetheless, resorting to these experts for every student comparison that might arise, is not a sustainable solution. Therefore, our goal in this paper is to learn the across-groups similarity functions, using as few queries to experts as possible.

\subsection{Formal Problem Definition}\label{sec:def}

Let $\mathcal{I}$ denote the feature space of elements. We assume that elements come from $\gamma$ known ``demographic'' groups, where $\gamma \in \mathbb{N}$, and each group $\ell \in [\gamma]$ is governed by an unknown distribution $\mathcal{D}_\ell$ over $\mathcal{I}$. We use $x \sim \mathcal{D}_{\ell}$ to denote a randomly drawn $x$ from $\mathcal{D}_\ell$. Further, we use $x \in \mathcal{D}_\ell$ to denote that $x$ is an element in the support of $\mathcal{D}_\ell$, and thus $x$ is a member of group $\ell$. Observe now that for a specific $x \in \mathcal{I}$, we might have $x \in \mathcal{D}_\ell$ and $x \in \mathcal{D}_{\ell'}$, for $\ell \neq \ell'$. Hence, in our model group membership is important, and every time we are considering an element $x \in \mathcal{I}$, we know which distribution produced $x$, i.e., which group $x$ belongs to.

For every group $\ell \in [\gamma]$ there is an intra-group similarity function $d_{\ell}: \mathcal{I}^2 \mapsto \mathbb{R}_{\geq 0}$, such that for all $x,y \in \mathcal{D}_\ell$ we have $d_{\ell}(x,y)$ representing the true similarity between $x,y$. In addition, the smaller $d_{\ell}(x,y)$ is, the more similar $x,y$. Note here that the function $d_\ell$ is only used to compare members of group $\ell$. Further, a common assumption for functions measuring similarity is that they are metric \citep{yona2018probably,Kim2018,ilvento2019, emp1, emp2}; a function $d$ is metric if \textbf{a)} $d(x,y) = 0$ implies $x = y$, \textbf{b)} $d(x,y) = d(y,x)$ and \textbf{c)} $d(x,y) \leq d(x,z) + d(z, y)$ for all $x,y,z$ (triangle inequality). \emph{We also adopt the metric assumption for the function $d_\ell$}. Finally, based on the earlier discussion regarding computing similarity between elements of the same group, we assume that $d_{\ell}$ is known and given as part of the instance.

Moreover, for any two groups $\ell$ and $\ell'$ there exists an \emph{unknown} across-groups similarity function $\sigma_{\ell, \ell'}: \mathcal{I}^2 \mapsto \mathbb{R}_{\geq 0}$, such that for all $x \in \mathcal{D}_\ell$ and $y \in \mathcal{D}_{\ell'}$, $\sigma_{\ell,\ell'}(x,y)$ represents the true similarity between $x,y$. Again, the smaller $\sigma_{\ell,\ell'}(x,y)$ is, the more similar the two elements, and for a meaningful use of $\sigma_{\ell,\ell'}$ we must make sure that $x$ is a member of group $\ell$ and $y$ a member of group $\ell'$. Finally, in order to imitate the metric nature of a similarity function, we impose the following properties on $\sigma_{\ell, \ell'}$, which can be viewed as across-groups triangle inequalities:
\begin{enumerate}
    \item \textbf{Property $\mathcal{M}_1$:} $\sigma_{\ell,\ell'}(x,y) \leq d_{\ell}(x,z) + \sigma_{\ell,\ell'}(z,y)$ for every $x,z \in \mathcal{D}_\ell$ and $y \in \mathcal{D}_{\ell'}$.
    \item \textbf{Property $\mathcal{M}_2$:} $\sigma_{\ell,\ell'}(x,y) \leq \sigma_{\ell,\ell'}(x,z) + d_{\ell'}(z,y)$ for every $x \in \mathcal{D}_\ell$ and $y, z \in \mathcal{D}_{\ell'}$.
\end{enumerate}

Nonetheless, the collection of similarity values here does not axiomatically yield a valid metric space. This is due to the following. \textbf{1)} If $\sigma_{\ell, \ell'}(x,y) = 0$ for $x \in \mathcal{D}_\ell$ and $y \in \mathcal{D}_{\ell'}$, then we do not necessarily have $x=y$. \textbf{2)} It is not always the case that $d_{\ell}(x,y) \leq \sigma_{\ell, \ell'}(x,z) + \sigma_{\ell, \ell'}(y,z)$ for $x,y \in \mathcal{D}_\ell$, $z \in \mathcal{D}_{\ell'}$. \textbf{3)} It is not always the case that $\sigma_{\ell,\ell'}(x,y) \leq \sigma_{\ell,\ell''}(x,z) + \sigma_{\ell'',\ell'}(z,y)$ for $x \in \mathcal{D}_\ell$, $y \in \mathcal{D}_{\ell'}$, $z \in \mathcal{D}_{\ell''}$.

However, not having the collection of similarity values necessarily produce a metric space is not a weakness of our model. On the contrary, we view this as one of its strongest aspects. For one thing, imposing a complete metric constraint on the case of intricate across-groups comparisons sounds unrealistic and very restrictive. Further, even though existing literature treats similarity functions as metric ones, the seminal work of \citet{Dwork2012} mentions that this should not always be the case. Hence, our model is more general than the current literature.

\textbf{Goal of Our Problem: }We want for any two groups $\ell, \ell'$ to compute a function $f_{\ell, \ell'}: \mathcal{I}^2 \mapsto \mathbb{R}_{\geq 0}$, such that $f_{\ell, \ell'}(x,y)$ is our estimate of similarity for any $x \in \mathcal{D}_\ell$ and $y \in \mathcal{D}_{\ell'}$. Specifically, we seek a PAC guarantee, where for any given accuracy and confidence parameters $\epsilon, \delta \in (0,1)$ we have:
\begin{align*}
    \Pr_{x \sim \mathcal{D}_{\ell}, y \sim \mathcal{D}_{\ell'}}\Big{[} \big{|} f_{\ell, \ell'}(x,y) - \sigma_{\ell, \ell'}(x,y)\big{|} > \epsilon \Big{]} \leq \delta
\end{align*}
The subscript in the above probability corresponds to two independent random choices, one $x \sim \mathcal{D}_\ell$ and one $y \sim \mathcal{D}_{\ell'}$.

As for tools to learn $f_{\ell, \ell'}$, we only require two things. At first, for each group $\ell$ we want a set $S_\ell$ of i.i.d. samples from $\mathcal{D}_\ell$. Obviously, the total number of used samples should be polynomial in the input parameters, i.e., polynomial in $\gamma, \frac{1}{\epsilon}$ and $\frac{1}{\delta}$. Secondly, we require access to an expert oracle, which given any $x \in S_\ell$ and $y \in S_{\ell'}$ for any $\ell$ and $\ell'$, returns the true similarity value $\sigma_{\ell, \ell'}(x,y)$. We refer to a single invocation of the oracle as a query. Since there is a cost to collecting expert feedback, an additional objective in our problem is minimizing the number of oracle queries.

\subsection{Discussion of Our Results}\label{sec:res}
In Section \ref{sec:algs} we present our theoretical results. We begin with a simple learning algorithm achieving the following.

\begin{theorem}\label{thm-naive}
For any given parameters $\epsilon, \delta \in (0,1)$, we produce similarity functions $f_{\ell, \ell'}$ for every $\ell$ and $\ell'$, such that:
\begin{align*}
        \Pr[\text{Error}_{(\ell, \ell')}] &\coloneqq \Pr_{\mathclap{\substack{x \sim \mathcal{D}_{\ell}, \\ y \sim \mathcal{D}_{\ell'}, ~\mathcal{A}}}}\big{[} \big{|} f_{\ell, \ell'}(x,y) - \sigma_{\ell, \ell'}(x,y)\big{|} = \omega(\epsilon) \big{]} \\ &= O(\delta + p_\ell(\epsilon, \delta) + p_{\ell'}(\epsilon, \delta))
\end{align*}
The randomness here is of three independent sources. The randomness $\mathcal{A}$ of the algorithm, a choice $x \sim \mathcal{D}_\ell$, and a choice $y \sim \mathcal{D}_{\ell}'$. The algorithm requires $\frac{1}{\delta} \log \frac{1}{\delta^2}$ samples from each group, and  $\frac{\gamma(\gamma-1)}{\delta^2} \log^2 \frac{1}{\delta^2}$ oracle queries.
\end{theorem}

For each group $\ell$, we use $p_\ell(\epsilon, \delta)$ to denote the probability of sampling an $(\epsilon, \delta)$-rare element of $\mathcal{D}_\ell$. We define as $(\epsilon, \delta)$-rare for $\mathcal{D}_\ell$, an element $x \in \mathcal{D}_\ell$ for which there is a less than $\delta$ chance of sampling $x' \sim \mathcal{D}_\ell$ with $d_{\ell}(x,x') \leq \epsilon$. Formally, $x \in \mathcal{D}_\ell$ is $(\epsilon, \delta)$-rare iff $\Pr_{x' \sim \mathcal{D}_\ell}[d_\ell(x,x') \leq \epsilon] < \delta$, and $p_\ell(\epsilon, \delta) = \Pr_{x \sim \mathcal{D}_\ell}[x \text{ is } (\epsilon, \delta)\text{-rare for } \mathcal{D}_\ell]$. Intuitively, a rare element should be interpreted as an ``isolated'' member of the group, in the sense that it is at most $\delta$-likely to encounter another element that is $\epsilon$-similar to it.

Clearly, the error probability for $\ell$ and $\ell'$ is $O(\delta)$ only when $p_\ell(\epsilon, \delta), p_{\ell'}(\epsilon, \delta) = O(\delta)$. We hypothesize that in realistic distributions each $p_\ell(\epsilon, \delta)$ should indeed be fairly small, and this hypothesis is actually validated by our experiments. The reason we believe this hypothesis to be true, is that very frequently real data demonstrate high concentration around certain archetypal elements. Hence, this sort of distributional density does not leave room for isolated elements in the rest of the space. Nonetheless, we also provide a strong \emph{no free lunch} result involving the values $p_\ell(\epsilon, \delta)$, which shows that any practical algorithm necessarily depends on them. This result further implies that our algorithm's error probabilities are almost optimal.

\begin{theorem}\label{thm:dep}
For every $\epsilon, \delta \in (0,1)$, any algorithm using finitely many samples, will yield $f_{\ell, \ell'}$ with $\Pr\big{[} | f_{\ell, \ell'}(x,y) - \sigma_{\ell, \ell'}(x,y)| = \omega(\epsilon) \big{]} = \Omega( \max \{p_\ell(\epsilon, \delta)$, $p_{\ell'}(\epsilon, \delta)\} - \epsilon)$; randomness is over the independent choices $x \sim \mathcal{D}_\ell$, $y \sim \mathcal{D}_{\ell}'$ and the internal randomness of the algorithm.
\end{theorem}

Moving on, we focus on minimizing the oracle queries. By carefully modifying the earlier simple algorithm, we obtain a new algorithm with the following guarantees:
\begin{theorem}\label{thm-cluster}
For any given parameters $\epsilon, \delta \in (0,1)$, we produce similarity functions $f_{\ell, \ell'}$ for every $\ell$ and $\ell'$, such that:
\begin{align*}
    \Pr[\text{Error}_{(\ell, \ell')}] = O(\delta + p_\ell(\epsilon, \delta) + p_{\ell'}(\epsilon, \delta))
\end{align*}
$\Pr[\text{Error}_{(\ell, \ell')}]$ is as defined in Theorem \ref{thm-naive}. Let $N = \frac{1}{\delta} \log \frac{1}{\delta^2}$. The algorithm requires $N$ samples from each group, and the number of oracle queries is at most
\begin{align}
    \sum_{\ell \in [\gamma]}\Big{(} Q_\ell \sum_{{\ell' \in [\gamma]: ~\ell' \neq \ell}}Q_{\ell'}\Big{)} \notag
\end{align}
where $Q_\ell \leq N$ and $\mathbb{E}[Q_\ell] \leq \frac{1}{\delta} + p_\ell(\epsilon, \delta) N$ for each $\ell$.
\end{theorem}
Based on Theorem \ref{thm-cluster}, the queries of the improved algorithm are at most $\gamma(\gamma-1)N$, which is exactly the number of queries in our earlier simple algorithm. However, the smaller the values $p_{\ell}(\epsilon, \delta)$ are, the fewer queries in expectation. Our experimental results actually confirm that this algorithm always leads to a significant decrease in the used queries.

Our final theoretical result involves a lower bound on the number of queries required for learning.
\begin{theorem}\label{thm:quer-bnd}
For all $\epsilon, \delta \in (0,1)$, any learning algorithm producing functions $f_{\ell, \ell'}$ with $\Pr_{x \sim \mathcal{D}_\ell, y \sim \mathcal{D}_{\ell'}}\big{[} | f_{\ell, \ell'}(x,y) - \sigma_{\ell, \ell'}(x,y)| = \omega(\epsilon) \big{]} = O(\delta)$, needs $\Omega(\frac{\gamma^2}{\delta^2})$ queries. \end{theorem}

Combining Theorems \ref{thm-cluster}, \ref{thm:quer-bnd} implies that when all $p_\ell(\epsilon, \delta)$ are negligible, i.e., $p_\ell(\epsilon, \delta) \rightarrow 0$, the expected queries of the Theorem \ref{thm-cluster} algorithm are asymptotically optimal.

Finally, Section \ref{sec:exp} contains our experimental evaluation, where through a large suite of simulations on both real and synthetic data we validate our theoretical findings.

\subsection{Related Work}\label{sec:rel-wrk}

Metric learning is a very well-studied area \citep{bellet:2013, kulis2013, moutafis, suarez2018}. There is also an extensive amount of work on using human feedback for learning metrics in specific tasks, e.g., image similarity, low-dimensional embeddings \citep{frome07, jamieson11, tamuz, vader, Wilber}. However, since these works are either tied to specific applications or specific metrics, they are only distantly related to ours.

Our model is more closely related to the literature on trying to learn the similarity function from the fairness definition of \citet{Dwork2012}. This concept of fairness requires treating similar individuals similarly. Thus, it needs access to a function that returns a non-negative value for any pair of individuals, and this value corresponds to how similar the individuals are. Specifically, the smaller the value the more similar the elements that are compared.

Even though the fairness definition of \citet{Dwork2012} is very elegant and intuitive, the main obstacle for adopting it in practice is the inability to easily compute or access the crucial similarity function. To our knowledge, the only papers that attempt to learn this similarity function using expert oracles like us, are \citet{ilvento2019, emp1} and \citet{emp2}. \citet{ilvento2019} addresses the scenario of learning a general metric function, and gives theoretical  PAC guarantees. \citet{emp1} give theoretical guarantees for learning similarity functions that are only of a specific Mahalanobis form. \citet{emp2} simply provide empirical results. The first difference between our model and these papers is that unlike us, they do not consider elements coming from multiple distributions. However, the most important difference is that these works only learn \textbf{metric}  functions. \textbf{In our case the collection of similarity values (from all $d_\ell$ and $\sigma_{\ell, \ell'}$) does not necessarily yield a complete metric space}; see the discussion in Section \ref{sec:def}. Hence, our problem learns more general functions.

Regarding the difficulty in computing similarity between members of different groups, we are only aware of a brief result by \citet{Dwork2012}. In particular, given a metric $d$ over the whole feature space, they mention that $d$ can only be trusted for comparisons between elements of the same group, and not for across-groups comparisons. In order to achieve the latter for groups $\ell$ and $\ell'$, they find a new similarity function $d'$ that approximates $d$, while minimizing the Earthmover distance between the distributions $\mathcal{D}_\ell, \mathcal{D}_{\ell'}$. This is completely different from our work, since here we assume the existence of across-groups similarity values, which we eventually want to learn. On the other hand, the approach of \citet{Dwork2012} can be seen as an optimization problem, where the across-groups similarity values need to be computed in a way that minimizes some objective. Also, unlike our model, this optimization approach has a serious limitation, and that is requiring $\mathcal{D}_\ell, \mathcal{D}_{\ell'}$ to be explicitly known.

Finally, since similarity as distance can be quite difficult to compute in practice, there has been a line of research that defines similarity using simpler, yet less expressive structures. Examples include similarity lists \cite{equ}, similarity graphs \cite{graph} and ordinal relationships \cite{jung19}.
\section{Theoretical Results}\label{sec:algs}

We begin the section by presenting a simple algorithm with PAC guarantees, whose error probability is shown to be almost optimal. Later on, we focus on optimizing the oracle queries, and show an improved algorithm for this objective.

\subsection{A Simple Learning Algorithm}\label{sec:alg-naive}

Given any confidence and accuracy parameters $\delta, \epsilon \in (0,1)$ respectively, our approach is summarized in the following. At first, for every group $\ell$ we need a set $S_\ell$ of samples that are chosen i.i.d. according to $\mathcal{D}_\ell$, such that $|S_\ell| = \frac{1}{\delta} \log \frac{1}{\delta^2}$. Then, for every distinct $\ell$ and $\ell'$, and for all $x \in S_\ell$ and $y \in S_{\ell'}$, we ask the expert oracle for the true similarity value $\sigma_{\ell, \ell'}(x,y)$. The next observation follows trivially.

\begin{observation}\label{obs-1}
The algorithm uses $\frac{\gamma}{\delta} \log \frac{1}{\delta^2}$ samples, and $\frac{\gamma(\gamma-1)}{\delta^2} \log^2 \frac{1}{\delta^2}$ queries to the oracle.
\end{observation}

Suppose now that we need to compare any $x \in \mathcal{D}_\ell$ and $y \in \mathcal{D}_{\ell'}$. Our high level idea is that the properties $\mathcal{M}_1$ and $\mathcal{M}_2$ of $\sigma_{\ell, \ell'}$ (see Section \ref{sec:def}), will actually allow us to use the closest element to $x$ in $S_\ell$ and the closest element to $y$ in $S_{\ell'}$ as proxies. Thus, let $\pi(x) = \argmin_{x' \in S_{\ell}}d_{\ell}(x,x')$ and $\pi(y) = \argmin_{y' \in S_{\ell'}}d_{\ell'}(y,y')$. The algorithm then sets $$f_{\ell, \ell'}(x,y) \coloneqq \sigma_{\ell, \ell'}(\pi(x), \pi(y))$$ where $\sigma_{\ell, \ell'}(\pi(x), \pi(y))$ is known from the earlier queries.

Before we proceed with the analysis of the algorithm, we need to recall some notation which was first introduced in Section \ref{sec:res}. Consider any group $\ell$. An element $x \in \mathcal{D}_\ell$ with $\Pr_{x' \sim \mathcal{D}_\ell}[d_\ell(x,x') \leq \epsilon] < \delta$ is called an $(\epsilon, \delta)$-rare element of $\mathcal{D}_\ell$, and also $p_\ell(\epsilon, \delta) \coloneqq \Pr_{x \sim \mathcal{D}_\ell}[x \text{ is } (\epsilon, \delta)\text{-rare for } \mathcal{D}_\ell]$.

\begin{theorem}\label{thm:error}
For any given parameters $\epsilon, \delta \in (0,1)$, the algorithm produces $f_{\ell, \ell'}$ for every $\ell$ and $\ell'$, such that
\begin{align*}
\Pr[\text{Error}_{(\ell, \ell')}] = O(\delta + p_\ell(\epsilon, \delta) + p_{\ell'}(\epsilon, \delta))
\end{align*}
where $\Pr[\text{Error}_{(\ell, \ell')}]$ is as in Theorem \ref{thm-naive}.
\end{theorem}

\begin{proof}
For two distinct groups $\ell$ and $\ell'$, consider what will happen when we are asked to compare some $x \in \mathcal{D}_\ell$ and $y \in \mathcal{D}_{\ell'}$. Properties $\mathcal{M}_1$ and $\mathcal{M}_2$ of $\sigma_{\ell, \ell'}$ imply
\begin{align*}
&Q \leq \sigma_{\ell, \ell'}(x,y) \leq P, \text{ where}\\
&P \coloneqq d_{\ell}(x, \pi(x)) + \sigma_{\ell, \ell'}(\pi(x), \pi(y)) + d_{\ell'}(y, \pi(y)) \\
&Q \coloneqq \sigma_{\ell, \ell'}(\pi(x), \pi(y)) - d_{\ell}(x, \pi(x)) -  d_{\ell'}(y, \pi(y))
\end{align*}

Note that when $d_{\ell}(x, \pi(x)) \leq 3\epsilon$ and $d_{\ell'}(y, \pi(y)) \leq 3\epsilon$, the above inequalities and the definition of $f_{\ell, \ell'}(x,y)$ yield $\big{|} f_{\ell, \ell'}(x,y) - \sigma_{\ell, \ell'}(x,y)\big{|} \leq 6\epsilon$. Thus, we just need upper bounds for $\mathcal{A} \coloneqq \Pr_{S_\ell, x \sim \mathcal{D}_{\ell}}[\forall x' \in S_\ell: d(x,x') > 3\epsilon]$ and $\mathcal{B} \coloneqq \Pr_{S_{\ell'}, y \sim \mathcal{D}_{\ell'}}[\forall y' \in S_\ell: d(y,y') > 3\epsilon]$, since the previous analysis and a union bound give $\Pr[\text{Error}_{(\ell, \ell')}] \leq \mathcal{A} + \mathcal{B}$.  In what follows we present an upper bound for $\mathcal{A}$. The same analysis gives an identical bound for $\mathcal{B}$.

Before we proceed to the rest of the proof, we have to provide an existential construction. For the sake of simplicity \emph{we will be using the term dense for elements of $\mathcal{D}_\ell$ that are not $(\epsilon, \delta)$-rare}. For every $x \in \mathcal{D}_{\ell}$ that is dense, we define $B_x \coloneqq \{x' \in \mathcal{D}_{\ell}: d_{\ell}(x,x') \leq \epsilon\}$. Observe that the definition of dense elements implies $\Pr_{x' \sim \mathcal{D}_{\ell}}[x' \in B_x] \geq \delta$ for every dense $x$. Next, consider the following process. We start with an empty set $\mathcal{R} = \{\}$, and we assume that all dense elements are unmarked. Then, we choose an arbitrary unmarked dense element $x$, and we place it in the set $\mathcal{R}$. Further, for every dense $x' \in \mathcal{D}_\ell$ that is unmarked and has $B_x \cap B_{x'} \neq \emptyset$, we mark $x'$ and set $\psi(x') = x$. Here the function $\psi$ maps dense elements to elements of $\mathcal{R}$. We continue this picking process until all dense elements have been marked. Since $B_z \cap B_{z'}= \emptyset$ for any two $z,z' \in \mathcal{R}$ and $\Pr_{x' \sim \mathcal{D}_{\ell}}[x' \in B_z] \geq \delta$ for $z \in \mathcal{R}$, we have $|\mathcal{R}| \leq 1/\delta$. Also, for every dense $x$ we have $d_{\ell}(x,\psi(x)) \leq 2\epsilon$ due to $B_x \cap B_{\psi(x)} \neq \emptyset$.

Now we are ready to upper bound $\mathcal{A}$ .
\begin{align*}
    \mathcal{C} &\coloneqq \Pr_{S_\ell, x \sim \mathcal{D}_{\ell}}[\forall x' \in S_\ell: d(x,x') > 3\epsilon \land x \text{ is } (\epsilon, \delta)\text{-rare}] \\ &\leq \Pr_{x \sim \mathcal{D}_\ell}[x \text{ is } (\epsilon, \delta)\text{-rare} ] = p_\ell(\epsilon, \delta) \\
    \mathcal{D} &\coloneqq \Pr_{S_\ell, x \sim \mathcal{D}_{\ell}}[\forall x' \in S_\ell: d(x,x') > 3\epsilon \land x \text{ is dense}]  \\
    &\leq \Pr_{S_\ell}[\exists r \in \mathcal{R}: B_r \cap S_\ell = \emptyset] \\
    &\leq \sum_{r \in \mathcal{R}}\Pr_{S_\ell}[B_r \cap S_\ell = \emptyset] \\
    &\leq |\mathcal{R}|(1-\delta)^{|S_\ell|} \leq |\mathcal{R}| e^{-\delta|S_\ell|} \leq \delta
\end{align*}
The upper bound for $\mathcal{C}$ is trivial. We next explain the computations for $\mathcal{D}$. For the transition between the first and the second line we use a proof by contradiction. Hence, suppose that $S_\ell \cap B_{r} \neq \emptyset$ for every $r \in \mathcal{R}$, and let $i_r$ denote an arbitrary element of $S_\ell \cap B_{r}$. Then, for any dense element $x \in \mathcal{D}_\ell$ we have
    $d_\ell(x, \pi(x)) \leq d_\ell(x, i_{\psi(x)}) \leq d_{\ell}(x, \psi(x)) + d_{\ell}(\psi(x), i_{\psi(x)}) \leq 2\epsilon + \epsilon = 3\epsilon$.
Back to the computations for $\mathcal{D}$, to get the third line we simply used a union bound. To get from the third to the fourth line, we used the definition of $r \in \mathcal{R}$ as a dense element, which implies that the probability of sampling any element of $B_r$ in one try is at least $\delta$. The final bound is a result of numerical calculations using $|\mathcal{R}| \leq \frac{1}{\delta}$ and $|S_\ell| = \frac{1}{\delta} \log \frac{1}{\delta^2}$.

To conclude the proof, observe that $\mathcal{A} = \mathcal{C} + \mathcal{D}$, and using a similar reasoning we also get $\mathcal{B} \leq p_{\ell'}(\epsilon, \delta) + \delta$.
\end{proof}

Observation \ref{obs-1} and Theorem \ref{thm:error} directly yield Theorem \ref{thm-naive}.

A potential criticism of the algorithm presented here, is that its error probabilities depend on $p_{\ell}(\epsilon, \delta)$. However, Theorem \ref{thm:dep} shows that such a dependence is unavoidable.

\begin{proof}[\textbf{Proof of Theorem \ref{thm:dep}}]

Given any $\epsilon, \delta$, consider the following instance of the problem. We have two groups represented by the distributions $\mathcal{D}_1$ and $\mathcal{D}_2$. For the first group we have only one element belonging to it, and let that element be $x$. In other words, every time we draw an element from $\mathcal{D}_1$ that element turns out to be $x$, i.e., $\Pr_{x' \sim \mathcal{D}_1}[x' = x] = 1$. For the second group we have that every $y \in \mathcal{D}_2$ appears with probability $\frac{1}{|\mathcal{D}_2|}$, and $|\mathcal{D}_2| \rightarrow \infty$. In other words, $\mathcal{D}_2$ is a uniform distribution over a countably infinite set.

Now we define all similarity values. At first, the similarity function for $\mathcal{D}_1$ will trivially be $d_1(x,x) = 0$. For the second group, for every distinct $y,y' \in \mathcal{D}_2$ we define $d_2(y,y') = 1$. Obviously, for every $y \in \mathcal{D}_2$ we set $d_2(y,y) = 0$. Observe that $d_1$ and $d_2$ are metric functions for their respective groups. As for the across-groups similarities, each $\sigma(x,y)$ for $y \in \mathcal{D}_2$ is chosen independently, and it is drawn uniformly at random from $[0,1]$. Note that this choice of $\sigma$ satisfies the necessary metric-like properties $\mathcal{M}_1$ and $\mathcal{M}_2$ that were introduced in Section \ref{sec:def}.

Further, since $\epsilon, \delta \in (0,1)$, any $y \in \mathcal{D}_2$ is $(\epsilon, \delta)$-rare:
\begin{align*}
  \Pr_{y' \sim \mathcal{D}_2}[d_2(y,y') \leq \epsilon] &= \Pr_{y' \sim \mathcal{D}_2}[y' = y] = \frac{1}{|\mathcal{D}_2|} < \delta
\end{align*}
The first equality is because the only element within distance $\epsilon$ from $y$ is $y$ itself. The last inequality is because we can always choose $|\mathcal{D}_2|$ in the construction of the input such that $\frac{1}{|\mathcal{D}_2|} < \delta$; we control $|\mathcal{D}_2|$ while $\delta$ is given. Therefore, since all elements are $(\epsilon, \delta)$-rare, we have $p_2(\epsilon, \delta) = 1$.

Consider now any learning algorithm that produces an estimate function $f$. For any $y \in \mathcal{D}_2$, let us try to analyze the probability of having $|f(x,y) - \sigma(x,y)| = \omega(\epsilon)$. For one thing, the probability of $y$ being in the sample set of the algorithm is $1-(1-1/|\mathcal{D}_2|)^N$, where $N$ is the number of used samples. Because the sampled set is finite, we have that the previous probability is practically $0$:
\begin{align*}
    \lim_{|\mathcal{D}_2| \to \infty}\big{(}1-(1-1/|\mathcal{D}_2|)^N\big{)} = 0
\end{align*}
Thus, since with absolute certainty $y$ will not be among the samples, the algorithm needs to learn $\sigma(x,y)$ via some other value $\sigma(x,y')$, for $y'$ being a sampled element of the second group. However, due to the construction of $\sigma$ the values $\sigma(x,y)$ and $\sigma(x,y')$ are independent. This means that knowledge of any $\sigma(x,y')$ (with $y \neq y'$) provides no information at all on $\sigma(x,y)$. Hence, the best any algorithm can do is guess $f(x,y)$ uniformly at random from $[0,1]$. This yields $\Pr[|f(x,y) - \sigma(x,y)| = \omega(\epsilon) ~|~ y] = 1 - \Pr[|f(x,y) - \sigma(x,y)| = O(\epsilon) ~|~ y] = 1- O(\epsilon) = p_2(\epsilon, \delta) - O(\epsilon)$. The latter trivially gives the desired bound through a mere integration over all $y \in \mathcal{D}_2$.
\end{proof}

\subsection{Optimizing the Number of Expert Queries}\label{sec:alg-intr}

Here we modify the earlier algorithm in a way that improves the number of queries used. The high-level idea behind this improvement is the following. Given the sets of samples $S_\ell$, instead of asking the oracle for all possible similarity values $\sigma_{\ell, \ell'}(x,y)$ for every $\ell, \ell'$ and every $x \in S_\ell$ and $y \in S_{\ell'}$, we would rather choose a set $R_\ell \subseteq S_\ell$ of representative elements for each group $\ell$. Then, we would ask the oracle for the values $\sigma_{\ell, \ell'}(x,y)$ for every $\ell, \ell'$, but this time only for every $x \in R_\ell$ and $y \in R_{\ell'}$. The choice of the representatives is inspired by the $k$-center algorithm of \citet{Hochbaum1985}. Intuitively, the representatives $R_\ell$ of group $\ell$ will serve as similarity proxies for the elements of $S_\ell$, such that each $x \in S_\ell$ is assigned to a nearby $r_\ell(x) \in R_\ell$ via a mapping function $r_\ell: S_\ell \mapsto R_\ell$. Hence, if $d_\ell(x,r_\ell(x))$ is small enough, $x$ and $r_\ell(x)$ are highly similar, and thus $r_\ell(x)$ acts as a good approximation of $x$. The full details for the construction of $R_\ell$ and $r_\ell$ are presented in Algorithm \ref{alg-1}.

Suppose now that we need to compare some $x \in \mathcal{D}_\ell$ and $y \in \mathcal{D}_{\ell'}$. Our approach will be almost identical to that of Section \ref{sec:alg-naive}. Once again, let $\pi(x) = \argmin_{x' \in S_{\ell}}d_{\ell}(x,x')$ and $\pi(y) = \argmin_{y' \in S_{\ell'}}d_{\ell'}(y,y')$. However, unlike the simple algorithm of Section \ref{sec:alg-naive} that directly uses $\pi(x)$ and $\pi(y)$, the more intricate algorithm here will rather use their proxies $r_\ell(\pi(x))$ and $r_{\ell'}(\pi(y))$. Our prediction will then be
\begin{align*}
   f_{\ell, \ell'}(x,y) \coloneqq \sigma_{\ell, \ell'}\Big{(}r_\ell\big{(}\pi(x)\big{)}, r_{\ell'}\big{(}\pi(y)\big{)}\Big{)}
\end{align*}
where $\sigma_{\ell, \ell'}(r_\ell(\pi(x)), r_{\ell'}(\pi(y)))$ is known from the queries.

\begin{algorithm}[tb]
\caption{Training Phase}
\label{alg-1}
\textbf{Input}: Accuracy and confidence parameters $\epsilon, \delta$. For every group $\ell \in [\gamma]$, a set $S_\ell$ of i.i.d. samples chosen according to $\mathcal{D}_\ell$, such that $|S_\ell| =\frac{1}{\delta} \log \frac{1}{\delta^2}$.
\begin{algorithmic}[1]
\FOR {each $\ell \in [\gamma]$}
\STATE $H^{\ell}_x \gets \{x' \in S_\ell: d_{\ell}(x,x') \leq 8\epsilon\}$ for each $x \in S_\ell$.
\STATE $U \gets S_\ell$ and $R_\ell \gets \emptyset$.
\STATE $r_\ell(x) \gets x$ for each $x \in S_\ell$.
\WHILE {$U \neq \emptyset$}
\STATE Choose an arbitrary $x \in U$.
\STATE $R_\ell \gets R_\ell \cup \{x\}$.
\STATE $W_x \gets \{x' \in U: H^{\ell}_x \cap H^{\ell}_{x'} \neq \emptyset\}$.
\STATE $r_\ell(x') \gets x$ for every $x' \in W_x$.
\STATE $U \gets U \setminus W_x$.
\ENDWHILE
\ENDFOR
\STATE For every $\ell$ and $\ell'$, and for every $x \in R_\ell$ and $y \in R_{\ell'}$, ask the oracle for the value $\sigma_{\ell, \ell'}(x,y)$ and store it.
\STATE For every $\ell$, return the set $R_\ell$ and the function $r_\ell$.
\end{algorithmic}
\end{algorithm}

\begin{theorem}\label{thm:error-2}
For any given parameters $\epsilon, \delta \in (0,1)$, the new algorithm produces $f_{\ell, \ell'}$ for every $\ell$ and $\ell'$, such that
\begin{align*}
\Pr[\text{Error}_{(\ell, \ell')}] = O(\delta + p_\ell(\epsilon, \delta) + p_{\ell'}(\epsilon, \delta))
\end{align*}
where $\Pr[\text{Error}_{(\ell, \ell')}]$ is as in Theorem \ref{thm-naive}.
\end{theorem}

\begin{proof}
For two distinct groups $\ell$ and $\ell'$, consider comparing some $x \in \mathcal{D}_\ell$ and $y \in \mathcal{D}_{\ell'}$. To begin with, let us assume that $d_{\ell}(x, \pi(x)) \leq 3\epsilon$ and $d_{\ell'}(y, \pi(y)) \leq 3\epsilon$. Furthermore, the execution of the algorithm implies $H^{\ell}_{\pi(x)} \cap H^{\ell}_{r_\ell(\pi(x))} \neq \emptyset$, and thus the triangle inequality and the definitions of the sets $H^{\ell}_{\pi(x)}, H^{\ell}_{r_\ell(\pi(x))}$ give $d_\ell(\pi(x), r_\ell(\pi(x))) \leq 16\epsilon$. Similarly we get $d_{\ell'}(\pi(y), r_{\ell'}(\pi(y))) \leq 16\epsilon$. Eventually:
\begin{align*}
    d_\ell(x, r_\ell(\pi(x))) &\leq d_{\ell}(x, \pi(x)) + d_{\ell}(\pi(x), r_\ell(\pi(x)))  \\ &\leq 19\epsilon \\
    d_{\ell'}(y, r_{\ell'}(\pi(y))) &\leq d_{\ell'}(y, \pi(y)) + d_{\ell'}(\pi(y), r_{\ell'}(\pi(y)))  \\ &\leq 19\epsilon
\end{align*}
For notational convenience, let $A \coloneqq d_\ell(x, r_\ell(\pi(x)))$ and $B \coloneqq d_{\ell'}(y, r_{\ell'}(\pi(y)))$. Then, the metric properties $\mathcal{M}_1$ and $\mathcal{M}_2$ of $\sigma_{\ell, \ell'}$ and the definition of $f_{\ell, \ell'}(x,y)$ yield
\begin{align*}
    |\sigma_{\ell, \ell'}(x,y)-f_{\ell, \ell'}(x,y)| \leq  A + B \leq 38\epsilon
\end{align*}

Overall, we proved that when $d_{\ell}(x, \pi(x)) \leq 3\epsilon$ and $d_{\ell'}(y, \pi(y)) \leq 3\epsilon$, we have $\big{|} f_{\ell, \ell'}(x,y) - \sigma_{\ell, \ell'}(x,y)\big{|} \leq 38\epsilon$. Finally, as shown in the proof of Theorem \ref{thm:error}, the probability of not having $d_{\ell}(x, \pi(x)) \leq 3\epsilon$ and $d_{\ell'}(y, \pi(y)) \leq 3\epsilon$, i.e., the error probability, is at most $2\delta + p_\ell(\epsilon, \delta) + p_{\ell'}(\epsilon, \delta) $.
\end{proof}

Since the number of samples used by the algorithm is easily seen to be $\frac{\gamma}{\delta} \log \frac{1}{\delta^2}$, the only thing left in order to prove Theorem \ref{thm-cluster} is analyzing the number of oracle queries. To that end, for every group $\ell \in [\gamma]$ with its sampled set $S_\ell$, we define the following Set Cover problem.

\begin{definition}\label{def-opt}
Let $\mathcal{H}^{\ell}_x \coloneqq \{x' \in S_\ell: d_{\ell}(x,x') \leq 4\epsilon\}$ for all $x \in S_\ell$. Find $C \subseteq S_\ell$ minimizing $|C|$, with $\bigcup_{c \in C}\mathcal{H}^{\ell}_c = S_\ell$. We use $OPT_\ell$ to denote the optimal value of this problem. Using standard terminology, we say $x \in S_\ell$ is \emph{covered} by $C$ if $x \in \bigcup_{c \in C}\mathcal{H}^{\ell}_c$, and $C$ is \emph{feasible} if it covers all $x \in S_\ell$.
\end{definition}

\begin{lemma}\label{lem-aux-1}
For every $\ell \in [\gamma]$ we have $|R_\ell| \leq OPT_\ell$.
\end{lemma}

\begin{proof}
Consider a group $\ell$, and let $C^*$ be its optimal solution for the problem of Definition \ref{def-opt}. We first claim that each $\mathcal{H}^{\ell}_c$ with $c \in C^*$ contains at most one element of $R_\ell$. This is due to the following. For any $c \in C^*$, we have $d_\ell(z,z') \leq d_\ell(z,c) + d_\ell(c,z') \leq 8\epsilon$ for all $z,z' \in \mathcal{H}^{\ell}_c$. In addition, the construction of $R_\ell$ trivially implies $d_\ell(x,x') > 8\epsilon$ for all $x,x' \in R_\ell$. Thus, no two elements of $R_\ell$ can be in the same $\mathcal{H}^{\ell}_c$ with $c \in C^*$. Finally, since Definition \ref{def-opt} requires all $x \in R_\ell$ to be covered, we have $|R_\ell| \leq |C^*| = OPT_\ell$.
\end{proof}

\begin{lemma}\label{lem-aux-2}
Let $N = \frac{1}{\delta} \log \frac{1}{\delta^2}$. For each group $\ell \in [\gamma]$ we have $OPT_\ell \leq N$ with probability $1$, and $\mathbb{E}[OPT_\ell] \leq \frac{1}{\delta} + p_\ell(\epsilon, \delta) N$. The randomness here is over the samples $S_\ell$.
\end{lemma}

\begin{proof}
Consider a group $\ell$. Initially, through Definition \ref{def-opt} it is clear that $OPT_\ell \leq |S_\ell| = N$. For the second statement of the lemma we need to analyze $OPT_\ell$ in a more clever way.

Recall the classification of elements $x \in \mathcal{D}_\ell$ that was first introduced in the proof of Theorem \ref{thm:error}. According to this, an element can either be $(\epsilon, \delta)$-rare, or dense. Now we will construct a solution $C_\ell$ to the problem of Definition \ref{def-opt} as follows.

At first, let $S_{\ell, r}$ be the set of $(\epsilon, \delta)$-rare elements of $S_\ell$. We will include all of $S_{\ell, r}$ to $C_\ell$, so that all $(\epsilon, \delta)$-rare elements of $S_\ell$ are covered by $C_\ell$. Further:
\begin{align}
    \mathbb{E}\big{[}|S_{\ell,r}|\big{]} = p_\ell(\epsilon, \delta) N \label{eq-1}
\end{align}

Moving on, recall the construction shown in the proof of Theorem \ref{thm:error}. According to that, there exists a set $\mathcal{R}$ of at most $\frac{1}{\delta}$ dense elements from $\mathcal{D}_\ell$, and a function $\psi$ that maps every dense element $x \in \mathcal{D}_\ell$ to an element $\psi(x) \in \mathcal{R}$, such that $d_\ell(x,\psi(x)) \leq 2\epsilon$. Let us now define for each $x \in \mathcal{R}$ a set $G_x \coloneqq \{x' \in \mathcal{D}_\ell: x' \text{ is dense and } \psi(x') = x\}$, and note that $d_\ell(z,z') \leq d_\ell(z, x) + d_\ell(z', x)  \leq 4\epsilon$ for all $z, z' \in G_x$. Thus, for each $x \in \mathcal{R}$ with $G_x \cap S_\ell \neq \emptyset$, we place in $C_\ell$ an arbitrary $y \in G_x \cap S_\ell$, and that $y$ gets all of $G_x \cap S_\ell$ covered. Finally, since the sets $G_x$ induce a partition of the dense elements of $\mathcal{D}_\ell$, $C_\ell$ covers all dense elements of $S_\ell$.

Equation (\ref{eq-1}) and $|\mathcal{R}| \leq \frac{1}{\delta}$ yield $\mathbb{E}\big{[}|C_\ell|\big{]} \leq \frac{1}{\delta} + p_\ell(\epsilon, \delta)N$. Also, since $C_\ell$ is shown to be a feasible solution for problem of Definition \ref{def-opt}, we get
$
    OPT_\ell \leq |C_\ell| \implies \mathbb{E}[OPT_\ell] \leq \frac{1}{\delta} + p_\ell(\epsilon, \delta) N
$.
\end{proof}

The proof of Theorem \ref{thm-cluster} is concluded as follows. All pairwise queries for the elements in the sets $R_\ell$ are
\begin{align}
    \sum_{\ell} \Big{(}|R_\ell| \sum_{\ell' \neq \ell}|R_{\ell'}| \Big{)} \leq  \sum_{\ell} \Big{(}OPT_\ell \sum_{\ell' \neq \ell}OPT_{\ell'} \Big{)} \label{eq-2}
\end{align}
where the inequality follows from Lemma \ref{lem-aux-1}. Finally, combining equation (\ref{eq-2}) and Lemma \ref{lem-aux-2} gives the desired bound.

\begin{remark}
The factor $8$ in the definition of $H^{\ell}_x$ at line 2 of Algorithm \ref{alg-1} is arbitrary. Actually, any factor $\rho = O(1)$ would yield the same guarantees, with any changes in accuracy and queries being only of an $O(1)$ order of magnitude.
\end{remark}

Finally, we are interested in lower bounds on the queries required for learning. To that end, we present Theorem \ref{thm:quer-bnd}, which shows that any algorithm with accuracy $O(\epsilon)$ and confidence $O(\delta)$ needs $\Omega(\gamma^2 / \delta^2)$ queries.

\begin{proof}[\textbf{Proof of Theorem \ref{thm:quer-bnd}}]
We are given accuracy and confidence parameters $\epsilon, \delta \in (0,1)$ respectively. For the sake of simplifying the exposition in the proof, let us assume that $\frac{1}{\delta}$ is an integer; all later arguments can be generalized in order to handle the case of $1/\delta \notin \mathbb{N}$.

We construct the following problem instance. We have two groups represented by the distributions $\mathcal{D}_1$ and $\mathcal{D}_2$. In addition, for both of these groups we assume that the support of the corresponding distribution contains $\frac{1}{\delta}$ elements, and $\Pr_{x' \sim \mathcal{D}_1}[x = x'] = \delta$ for every $x \in \mathcal{D}_1$ as well as $\Pr_{y' \sim \mathcal{D}_2}[y = y'] = \delta$ for every $y \in \mathcal{D}_2$.

For every $x, x' \in \mathcal{D}_1$ let $d_1(x,x') = 1$, and $d_1(x,x) = 0$ for every $x \in \mathcal{D}_1$. Similarly, for every $y, y' \in \mathcal{D}_2$ we set $d_2(y,y') = 1$, and for every $y \in \mathcal{D}_2$ we set $d_2(y,y) = 0$. The functions $d_1$ and $d_2$ are clearly metrics. As for the across-groups similarity values, each $\sigma(x,y)$ for $x \in \mathcal{D}_1$ and $y \in \mathcal{D}_2$ is chosen independently, and it is drawn uniformly at random from $[0,1]$. Note that this choice of $\sigma$ satisfies the necessary properties $\mathcal{M}_1, \mathcal{M}_2$ introduced in Section \ref{sec:def}.

In this proof we are also focusing on a more special learning model. In particular, we assume that the distributions $\mathcal{D}_1$ and $\mathcal{D}_2$ are known. Hence, there is no need for sampling. The only randomness here is over the random arrivals $x \sim \mathcal{D}_1$ and $y \sim \mathcal{D}_2$, where $x$ and $y$ are the elements that need to be compared. Obviously, the similarity function $\sigma$ would still remain unknown to any learner. Finally, the number of queries required for learning in this model cannot be more than the queries required in the original model, and this is because this model is easier (special case of the original).

Consider now an algorithm with the error guarantees mentioned in the Theorem statement, and focus on a fixed pair $(x,y)$ with $x \in \mathcal{D}_1$ and $y \in \mathcal{D}_2$. If the algorithm has queried the oracle for $(x,y)$, it knows $\sigma(x,y)$ with absolute certainty. Let us study what happens when the algorithm has not queried the oracle for $(x,y)$. In this case, because the values $\sigma(x', y')$ with $x' \in \mathcal{D}_1$ and $y' \in \mathcal{D}_2$ are independent, no query the algorithm has performed can provide any information for $\sigma(x,y)$. Thus, the best the algorithm can do is uniformly at random guess a value in $[0,1]$, and return that as the estimate for $\sigma(x,y)$. Letting $\bar{\mathcal Q}_{x,y}$ denote the event where no query is performed for $(x,y)$, we have
\begin{align*}
    \mathcal{P} &\coloneqq \Pr \big{[} | f_{\ell, \ell'}(x,y) - \sigma_{\ell, \ell'}(x,y)| = \omega(\epsilon) ~|~ \bar{\mathcal Q}_{x,y} \big{]} \\
    &=1 - \Pr \big{[} | f_{\ell, \ell'}(x,y) - \sigma_{\ell, \ell'}(x,y)| = O(\epsilon) ~|~ \bar{\mathcal Q}_{x,y} \big{]} \\
    &=1 - O(\epsilon) = \Omega(1)
\end{align*}
where the randomness comes only from the algorithm.

For the sake of contradiction, suppose the algorithm uses $q = o(1/\delta^2)$ queries. Since each $(x,y)$ is equally likely to appear for a comparison, the overall error probability is
\begin{align*}
    \Bigg{(}\frac{1/\delta^2 - q}{1/ \delta^2}\Bigg{)} \cdot \mathcal{P} = \Omega(1) \cdot \Omega(1) = \Omega(1)
\end{align*}
Contradiction; the error probability must be $O(\delta)$.
\end{proof}

\begin{corollary}
When for every $\ell \in [\gamma]$ the value $p_\ell(\epsilon, \delta)$ is arbitrarily close to $0$, the algorithm presented in this section achieves an expected number of oracle queries that is asymptotically optimal.
\end{corollary}

\begin{proof}
When every $p_\ell(\epsilon, \delta)$ is very close to $0$, Lemma \ref{lem-aux-2} gives $\mathbb{E}[OPT_\ell] \leq \frac{1}{\delta}$. Thus, by inequality (\ref{eq-2}) the expected queries are $\frac{\gamma(\gamma-1)}{\delta^2}$. Theorem \ref{thm:quer-bnd} concludes the proof.
\end{proof}
\section{Experimental Evaluation}\label{sec:exp}

We implemented all algorithms in Python 3.10.6 and ran our experiments on a personal laptop with Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz   2.90 GHz and 16.0 GB memory.

\textbf{Algorithms: } We implemented the simple algorithm from Section \ref{sec:alg-naive}, and the more intricate algorithm of Section \ref{sec:alg-intr}. We refer to the former as \textsc{Simple-Alg}, and to the latter as \textsc{QueryOpt-Alg}. For the training phase of \textsc{QueryOpt-Alg}, we set the dilation factor at line 2 of Algorithm \ref{alg-1} to $12$ instead of $8$. The reason for this, is that a minimal experimental investigation revealed that this choice leads to a good balance between accuracy guarantees and oracle queries.

\textbf{Number of demographic groups: } All our experiments are for two groups, i.e., $\gamma = 2$. The following reasons justify this decision. At first, this case captures the essence of our algorithmic results; the $\gamma > 2$ case can be viewed as running the algorithm for $\gamma=2$ multiple times, one for each pair of groups. Secondly, the achieved confidence and accuracy of our algorithms are completely independent of $\gamma$.

\textbf{Similarity functions: } In all our experiments the feature space is $\mathbb{R}^d$, where $d \in \mathbb{N}$ is case-specific. To define similarity functions, we adopt a paradigm of feature importance \citep{NINOADAN}. Specifically, we assume that all similarity functions $d_1, d_2$ and $\sigma$ are weighted Euclideans:
\begin{align*}
    d_\ell(x,x') &= \sqrt{\sum_{i \in [d]}\alpha_{i,\ell} (x_i - x^{'}_i)^2} \\
    \sigma(x,y) &= \sqrt{\sum_{i \in [d]}\beta_i(x_i - y_i)^2}
\end{align*}
The weight $\alpha_{i,\ell} \geq 0$ measures how significant feature $i$ is for comparisons within group $\ell \in \{1,2\}$. Similarly, the weight $\beta_i \geq 0$ corresponds to how important feature $i$ is, when we are comparing elements across groups. The larger a weight is, the more significant that feature for the comparison at hand. Finally, we chose Euclidean metrics due to their widespread use as accurate similarity/distance functions.

For the across-groups weights we also assume that $\beta_i \leq \min\{\alpha_{i,1}, \alpha_{i,2}\}$ for every $i \in [d]$, i.e., the significance of a feature for across-groups comparisons cannot be more than its significance for within group comparisons. To justify this assumption think of the following scenario. Suppose that for some feature $i$ we have $\alpha_{i,1} = 0$. In other words, \emph{this feature can be seen as totally irrelevant for the first group, i.e., it provides no information at all for the nature of the elements of this group}. Hence, it is reasonable to also disregard $i$ when we compare an element of the first group with an element of the second group, i.e., $\beta_i$ should be $0$ as well.

The functions $d_1$ and $d_2$ are metric due to being weighted Euclideans. We also need to show that $\sigma$ satisfies the across-groups metric properties imposed in Section \ref{sec:def}. Since $\sigma$ is a metric, for any $x,y,z \in \mathbb{R}^d$ we have:
\begin{align}
    \sigma(x,y) &\leq \sigma(x,z) + \sigma(z,y) \label{eq-3}
\end{align}
Using the assumption that $\beta_i \leq \min\{\alpha_{i,1}, \alpha_{i,2}\}$ we get:
\begin{align}
    \sigma(x,z) &= \sqrt{\sum_{i \in [d]}\beta_i(x_i - z_i)^2}  \leq d_1(x,z) \label{eq-4} \\
    \sigma(z,y) &= \sqrt{\sum_{i \in [d]}\beta_i(z_i-y_i)^2}  \leq d_2(z,y) \label{eq-5}
\end{align}
Combining (\ref{eq-3}) and (\ref{eq-4}) proves property $\mathcal{M}_1$ for $\sigma$. Similarly, combining (\ref{eq-3}) and (\ref{eq-5}) proves property $\mathcal{M}_2$.

In each experiment we choose the importance weights as follows. At first, each $\alpha_{i,\ell}$ for $i \in [d]$ and $\ell \in \{1,2\}$ is chosen independently, and it is drawn uniformly at random from $[0,1]$. Afterwards, we choose all $\beta_i$ independently, with each $\beta_i$ drawn uniformly at random from $[0, \min\{\alpha_{i,1}, \alpha_{i,2}\}]$. Obviously, the algorithms do not have access to the vector $\beta$, which is only used to simulate the oracle and compare our predictions with the corresponding true values.

\subsection{Experiments on Synthetic Data}\label{sec:exp-synth}

\begin{figure*}[t]
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=.705\linewidth]{figures/RelError-2.0-Naive.png}
  \caption{\textsc{Simple-Alg}}
  \label{fig-1}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=.705\linewidth]{figures/RelError-2.0-Cluster.png}
  \caption{\textsc{QueryOpt-Alg}}
  \label{fig-2}
\end{subfigure}
\caption{Distribution of the Relative Error Percentage}
\end{figure*}

\begin{figure*}[t]
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=.705\linewidth]{figures/AbsError-2.0-Naive.png}
  \caption{\textsc{Simple-Alg}}
  \label{fig-3}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=.705\linewidth]{figures/AbsError-2.0-Cluster.png}
  \caption{\textsc{QueryOpt-Alg}}
  \label{fig-4}
\end{subfigure}
\caption{Distribution of (Absolute Error)/$\epsilon$}
\end{figure*}

We believe that in our applications of interest, the data would exhibit high concentration around certain archetypal feature vectors. For instance, recall the scenario from the introduction, where we had to compare students for college admissions. Given some demographic group, it is natural to assume that there are certain prototypical student profiles, and each student falls close to one of them. For example, consider archetypal vectors each corresponding to one of the next profiles: \emph{exceptional student, very good student, good student, average student, below average student, dropout}.

\textbf{Data Generation for Each Group $\ell \in \{1,2\}$:} The best way to capture the aforementioned data behaviour, is having the group distribution $\mathcal{D}_\ell$ be a mixture of multivariate Gaussians \citep{Gauss}. Specifically, we consider $16$ multivariate Gaussians $\mathcal{N}(\mu^{\ell}_i, \Sigma^{\ell}_i)$ in $\mathbb{R}^{20}$; $i \in [16]$ (we believe that the number of archetypal elements, each corresponding to a Gaussian, is usually small). As for the mixing weights, we set $\pi^{\ell}_i = \frac{1}{2^i}$ for $i \in [15]$ and $\pi^{\ell}_{16} = \frac{1}{2^{15}}$. This choice tries to capture the fact that the prototypical feature vectors are not equally likely, and some are far more common than others, e.g., average students are more than exceptional ones. As for the mean $\mu^{\ell}_i$ of each Gaussian $i$, it is chosen uniformly at random from $[0,10]^{20}$. Further, to define the covariance matrices $\Sigma^{\ell}_i \in \mathbb{R}^{20 \times 20}$ we do the following. At first, we assume that the features are independent, and thus each $\Sigma^{\ell}_i$ can only have non-zero values in the diagonal. Then, given a value $U_{var}$ that serves as an upper bound for the variances, we choose each diagonal value of $\Sigma^{\ell}_i$ uniformly at random from $[0, U_{var}]$. Intuitively, the smaller $U_{var}$ is, the more concentrated the Gaussians. The previous process is performed independently for the construction of each $\mathcal{D}_\ell$.

\textbf{Range of $U_{var}$:} We run all experiments for data produced by every value of $U_{var}$ in $\{0.5, 1, 2, 4\}$. Our algorithms are expected to perform better for smaller values of $U_{var}$, since those yield more concentrated distributions, which naturally imply smaller $p_\ell(\epsilon, \delta)$. This behaviour was indeed observed in our simulations. Due to space constraints, here we only provide results for $U_{var} = 2$. For the rest see Appendix \ref{sec:apdx-2}.

\textbf{Choosing the accuracy parameter $\epsilon$:} To use a meaningful value for $\epsilon$, we need to know the order of magnitude of $\sigma(x,y)$. We calculated the value of $\sigma(x,y)$ over $1000$ trials, where the randomness was of multiple factors, i.e., the randomized constructions of $\mathcal{D}_1$ and $\mathcal{D}_2$, the random choices for the feature weights, and of course the random sampling of $x$ and $y$. In the end, we saw that $\sigma(x,y)$ is always greater than $3$ and highly concentrated in $[7,8)$; see Appendix \ref{sec:apdx-2}. Thus, choosing $\epsilon = 0.1$ is a reasonable option.

\textbf{Confidence $\delta$ and number of samples:} We run all simulations for every value of $\delta$ in $\{0.1, 0.01, 0.001, 0.0001\}$, and in each case we use $\frac{1}{\delta} \log\frac{1}{\delta^2}$ samples from each group.

\textbf{Testing:} We test our algorithms over $1000$ trials, where each trial consists of independently sampling $x \sim \mathcal{D}_1$ and $y\sim \mathcal{D}_2$, and then inputting $x,y$ to our predictors. We are interested in two metrics. The first is the relative error percentage; if $p$ is our prediction for elements $x,y$ and $t$ is their true similarity value, the relative error percentage is $100 \cdot |p-t|/t $. Figure (\ref{fig-1}) shows the empirical distribution of this error for \textsc{Simple-Alg}, for every value of $\delta$. Figure (\ref{fig-2}) shows the same statistics for \textsc{QueryOpt-Alg}. The second metric we consider is the absolute error divided by $\epsilon$; if $p$ is our prediction for two elements and $t$ is their true similarity value, this metric is $|p-t|/\epsilon$. We are interested in this because our theoretical guarantees are of the form $|f(x,y) - \sigma(x,y)| = O(\epsilon)$. Figure (\ref{fig-3}) shows the empirical distribution of the (absolute error)/$\epsilon$ for \textsc{Simple-Alg}, for every value of $\delta$. Figure (\ref{fig-4}) shows the same statistics for \textsc{QueryOpt-Alg}.

\begin{figure*}[t]
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=.705\linewidth]{figures/xAdltRelError-Naive.png}
  \caption{\textsc{Simple-Alg}}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=.705\linewidth]{figures/xAdltRelError-Cluster.png}
  \caption{\textsc{QueryOpt-Alg}}
\end{subfigure}
\caption{Distribution of the Relative Error Percentage on Adult}
\label{fig-5}
\end{figure*}

\begin{figure*}[t]
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=.705\linewidth]{figures/xAdltAbsError-Naive.png}
  \caption{\textsc{Simple-Alg}}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=.705\linewidth]{figures/xAdltAbsError-Cluster.png}
  \caption{\textsc{QueryOpt-Alg}}
\end{subfigure}
\caption{Distribution of (Absolute Error)/$\epsilon$ on Adult}
\label{fig-6}
\end{figure*}

\textbf{Conclusions:} First of all, we see that the smaller $\delta$ is, the better the algorithms perform. Further, \textsc{Simple-Alg} performs marginally better than \textsc{QueryOpt-Alg}. Nonetheless, this tiny edge is not enough to justify a potential superiority of \textsc{Simple-Alg}, and the reason for this is the decrease in queries. Specifically, compared to the queries used by \textsc{Simple-Alg}, we observed the next for \textsc{QueryOpt-Alg}:
\begin{enumerate}
    \item For $\delta = 0.1$ we saw a $2.13\%$ decrease in used queries.
    \item For $\delta = 0.01$ we saw a $28.44\%$ decrease in queries.
    \item For $\delta = 0.001$ we saw a $71.41\%$ decrease in the queries.
    \item For $\delta = 0.0001$ we saw a $93.65\%$ decrease in the queries.
\end{enumerate}
This improvement as $\delta$ decreases is natural. The smaller $\delta$ is the more samples we have, and thus the more flexibility for the clustering decisions in Algorithm \ref{alg-1}.

Overall, for both types of errors the algorithms perform significantly well. In particular, when $\delta = 10^{-3}$ or $\delta = 10^{-4}$ the guarantees are remarkably strong.

\subsection{Experiments on Real Data}

We used 2 datasets from the UCI ML Repository \cite{Dua:2019}, namely Adult-48,842 points \cite{kohavi} and Creditcard-30,000 points \cite{yeh}. For both datasets, we kept numerical features as they were and transformed each categorical feature as follows. Each category is assigned to an integer in $\{1, \#\text{categories}\}$, and this integer is used in place of the category in the feature vector \citep{NEURIPS2021_32e54441}. Also, we standardized all features so that they have approximately the same order of magnitude.

\textbf{Choosing the Two Groups:} For both datasets, we defined groups based on marital status. Specifically, the first group corresponds to points that are married individuals, and the second corresponds to points that are not married (singles, divorced and widowed are merged together). Afterwards, for each group we chose a random permutation of its points, and every time we needed to sample from either group, we were simply taking the next element in the permutation.

\textbf{Choosing the accuracy parameter $\epsilon$:} We calculated the value of $\sigma(x,y)$ over $5000$ trials, where the randomness was of multiple factors, i.e., the random choices for the feature weights, and the sampling of $x$ and $y$ from their respective random permutations. In the end, we saw that for both datasets $\sigma(x,y)$ is always large enough to justify setting $\epsilon = 0.1$; see Appendix \ref{sec:apdx-2} for figures on $\sigma(x,y)$.

\textbf{Confidence $\delta$ and number of samples:} For Adult we run all simulations for every value of $\delta$ in $\{0.1, 0.01, 0.001\}$, and we used $\frac{1}{\delta} \log\frac{1}{\delta^2}$ samples from each group. For Creditcard we had to be a bit more careful, because it contains fewer points. Specifically, for Creditcard we run all simulations for every value of $\delta$ in $\{0.1, 0.01, \Delta\}$, using $\frac{1}{\delta} \log\frac{1}{\delta^2}$ samples from each group. Here $\Delta \approx 0.001$ and $\frac{1}{\Delta} \log\frac{1}{\Delta^2} - 1000$ is less than the size of the smallest of the two groups, guaranteeing that there are enough points for sampling and testing.

\textbf{Testing:} We test our algorithms over $1000$ trials, where each trial consists of independently sampling two elements $x,y$, one for each group, and then inputting those to our predictors. We are again interested in the same two metrics as in Section \ref{sec:exp-synth}. Figures (\ref{fig-5}) and (\ref{fig-6}) show the performance of the algorithms on Adult. Due to space constraints our results on Creditcard are moved to Appendix \ref{sec:apdx-2}.

\textbf{Conclusions: } We reach the same conclusions as earlier, mainly observing that our algorithms for $\delta = 0.01$ perform very well. As for the queries of \textsc{QueryOpt-Alg} compared to the queries of \textsc{Simple-Alg}, we observed the following:
\begin{enumerate}
    \item For $\delta = 0.1$ we saw a $12.36\%$ decrease in used queries.
    \item For $\delta = 0.01$ we saw a $52.34\%$ decrease in queries.
    \item For $\delta = 0.001$ we saw a $87.64\%$ decrease in the queries.
\end{enumerate}

\section{Additional Motivating Applications} \label{sec:apdx-1}

\vspace{5mm}

\textbf{Individual Fairness: }Suppose that some college committee wants to provide scholarships to student athletes, in a way that similar candidates will have the same chance of receiving the scholarship. For this case, computing the similarity of two students that are athletes of the same sport appears relatively easy, since their respective feature vectors will most certainly contain the necessary information for the comparison at hand. However, computing the similarity of athletes across different sports must be far more challenging. For instance, how can one compare a basketball player to a swimmer? In such a situation, it might also be the case that the feature vectors for the two students do not even contain the same subset of features.

\textbf{Clustering: } Consider an investor who has a set of potential investments, and wants to partition them into clusters of high intra-group similarity. Investments that are similar are thought of as having the same profit potential, and clustering the given set of investments might be useful for post-processing downstream analysis. In this context, the investor needs access to a distance metric in order to perform any clustering procedure. However, computing this metric might be tricky. For one thing, comparing investments that involve the same market should be relatively straightforward, e.g., comparing two investments in the housing market. On the other hand, comparing investments to different markets appears to be a much more cumbersome task, e.g., trying to find how similar a housing investment and a cryptocurrency one are.

\section{Additional Experimental Results}\label{sec:apdx-2}

Figures (\ref{a-fig-1})-(\ref{a-fig-6}) demonstrate the empirical distribution of $\sigma(x,y)$ in every case of interest, which is needed in order to justify our choice of setting $\epsilon = 0.1$ in all of our experiments. Figures (\ref{a-fig-7})-(\ref{a-fig-8}) show the performance of our algorithms for synthetic data produced with $U_{var} = 1$. Figures (\ref{a-fig-9})-(\ref{a-fig-10}) show the performance of our algorithms for synthetic data produced with $U_{var} = 4$. Finally, figures (\ref{a-fig-11})-(\ref{a-fig-12}) show the performance of our algorithms on the Creditcard dataset. As for the queries of \textsc{QueryOpt-Alg} compared to the queries of \textsc{Simple-Alg}, we observed the following:
\begin{enumerate}
    \item \textbf{Synthetic data with $U_{var} = 0.5$:} For $\delta = 0.1$ we saw a $92.94\%$ decrease in used queries. For $\delta = 0.01$ we saw a $99.81\%$ decrease. For $\delta = 0.001$ we saw a $99.9898\%$ decrease, and for $\delta = 0.0001$ the decrease was $99.99\%$.
    \item \textbf{Synthetic data with $U_{var} = 1$:} For $\delta = 0.1$ we saw a $51.11\%$ decrease in used queries. For $\delta = 0.01$ we saw a $94.07\%$ decrease. For $\delta = 0.001$ we saw a $99.38\%$ decrease, and for $\delta = 0.0001$ the decrease was $99.95\%$.
    \item \textbf{Synthetic data with $U_{var} = 4$:} For $\delta = 0.1$ we saw a $4.26\%$ decrease in used queries. For $\delta = 0.01$ we saw a $16.18\%$ decrease. For $\delta = 0.001$ we saw a $51.34\%$ decrease, and for $\delta = 0.0001$ the decrease was $82.04\%$.
    \item \textbf{Creditcard dataset:} For $\delta = 0.1$ we saw a $6.29\%$ decrease in used queries. For $\delta = 0.01$ we saw a $48.45\%$ decrease, and for $\delta = 0.001$ the decrease was $79.83\%$.
\end{enumerate}

\begin{figure}[tb]
\centering
\includegraphics[scale=0.435]{figures/DistDistr-0.5.png}
\caption{Distribution of $\sigma(x,y)$ for synthetic data with $U_{var} = 0.5$ }
\label{a-fig-1}
\end{figure}

\begin{figure}[tb]
\centering
\includegraphics[scale=0.3]{figures/DistDistr-1.0.png}
\caption{Distribution of $\sigma(x,y)$ for synthetic data with $U_{var} = 1$ }
\label{a-fig-2}
\end{figure}

\begin{figure}[tb]
\centering
\includegraphics[scale=0.3]{figures/DistDistr-2.0.png}
\caption{Distribution of $\sigma(x,y)$ for synthetic data with $U_{var} = 2$ }
\label{a-fig-3}
\end{figure}

\begin{figure}[tb]
\centering
\includegraphics[scale=0.3]{figures/DistDistr-4.0.png}
\caption{Distribution of $\sigma(x,y)$ for synthetic data with $U_{var} = 4$ }
\label{a-fig-4}
\end{figure}

\begin{figure}[tb]
\centering
\includegraphics[scale=0.5]{figures/xAdultDD.png}
\caption{Distribution of $\sigma(x,y)$ for Adult}
\label{a-fig-5}
\end{figure}

\begin{figure}[tb]
\centering
\includegraphics[scale=0.5]{figures/xCreditDD.png}
\caption{Distribution of $\sigma(x,y)$ for Creditcard}
\label{a-fig-6}
\end{figure}

\begin{figure*}[t]
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=1\linewidth]{figures/RelError-1.0-Naive.png}
  \caption{\textsc{Simple-Alg}}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=1\linewidth]{figures/RelError-1.0-Cluster.png}
  \caption{\textsc{QueryOpt-Alg}}
\end{subfigure}
\caption{Distribution of the Relative Error Percentage for Synthetic Data with $U_{var} = 1$}
\label{a-fig-7}
\end{figure*}

\begin{figure*}[t]
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=1\linewidth]{figures/AbsError-1.0-Naive.png}
  \caption{\textsc{Simple-Alg}}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=1\linewidth]{figures/AbsError-1.0-Cluster.png}
  \caption{\textsc{QueryOpt-Alg}}
\end{subfigure}
\caption{Distribution of (Absolute Error)/$\epsilon$ for Synthetic Data with $U_{var} = 1$}
\label{a-fig-8}
\end{figure*}

\begin{figure*}[t]
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=1\linewidth]{figures/RelError-4.0-Naive.png}
  \caption{\textsc{Simple-Alg}}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=1\linewidth]{figures/RelError-4.0-Cluster.png}
  \caption{\textsc{QueryOpt-Alg}}
\end{subfigure}
\caption{Distribution of the Relative Error Percentage for Synthetic Data with $U_{var} = 4$}
\label{a-fig-9}
\end{figure*}

\begin{figure*}[t]
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=1\linewidth]{figures/AbsError-4.0-Naive.png}
  \caption{\textsc{Simple-Alg}}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=1\linewidth]{figures/AbsError-4.0-Cluster.png}
  \caption{\textsc{QueryOpt-Alg}}
\end{subfigure}
\caption{Distribution of (Absolute Error)/$\epsilon$ for Synthetic Data with $U_{var} = 4$}
\label{a-fig-10}
\end{figure*}

\begin{figure*}[t]
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=1\linewidth]{figures/xCredRelError-Naive.png}
  \caption{\textsc{Simple-Alg}}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=1\linewidth]{figures/xCredRelError-Cluster.png}
  \caption{\textsc{QueryOpt-Alg}}
\end{subfigure}
\caption{Distribution of the Relative Error Percentage on Creditcard}
\label{a-fig-11}
\end{figure*}

\begin{figure*}[t]
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=1\linewidth]{figures/xCredAbsError-Naive.png}
  \caption{\textsc{Simple-Alg}}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=1\linewidth]{figures/xCredAbsError-Cluster.png}
  \caption{\textsc{QueryOpt-Alg}}
\end{subfigure}
\caption{Distribution of (Absolute Error)/$\epsilon$ on Creditcard}
\label{a-fig-12}
\end{figure*}

\section*{Acknowledgements}

\textbf{Disclaimer:} This paper was prepared for informational purposes in part
by the Artificial Intelligence Research group of JPMorgan
Chase \& Co. and its affiliates ("JP Morgan"), and is not a
product of the Research Department of JP Morgan. JP Morgan makes no representation and warranty whatsoever and
disclaims all liability, for the completeness, accuracy or reliability of the information contained herein. This document
is not intended as investment research or investment advice,
or a recommendation, offer or solicitation for the purchase
or sale of any security, financial instrument, financial product or service, or to be used in any way for evaluating the
merits of participating in any transaction, and shall not constitute a solicitation under any jurisdiction or to any person,
if such solicitation under such jurisdiction or to such person
would be unlawful.