Comparing Apples to Oranges: Learning Similarity Functions for Data Produced by Different Distributions
Authors: Leonidas Tsepenekas
Ivan Brugere
Freddy Lecue
Daniele Magazzeni
Venue: NeurIPS 2023 poster (2023)
Keywords: individual fairness; similarity learning; active learning

Abstract: Similarity functions measure how comparable pairs of elements are, and play a key role in a wide variety of applications, e.g., notions of Individual Fairness abiding by the seminal paradigm of Dwork et al., as well as Clustering problems. However, access to an accurate similarity function should not always be considered guaranteed, and this point was even raised by Dwork et al. For instance, it is reasonable to assume that when the elements to be compared are produced by different distributions, or in other words belong to different ``demographic'' groups, knowledge of their true similarity might be very difficult to obtain. In this work, we present an efficient sampling framework that learns these across-groups similarity functions, using only a limited amount of experts' feedback. We show analytical results with rigorous theoretical bounds, and empirically validate our algorithms via a large suite of experiments.

Comparing Apples to Oranges: Learning Similarity Functions for Data Produced by Different Distributions
Leonidas Tsepenekas JPMorganChase Al Research New York, USA
Ivan Brugere
JPMorganChase Al Research
New York, USA
leonidas tespeeteesseeppcccaeeeeeeee com
ivan. bwwgereejjpnchase....... com
Freddy Lecue
Daniele Maggazeni JPMorganChase AI Research
JPMorganChase AI Research New York, USA
London, UK
freddy www.:leeee@@@mccssee.. com
daniele damiele.magazzerne mawazzeeniijjoorrannn.n
Abstract
Similarity functions measure how comparable pairs of elements are, and play a key role in a wide variety of applications, e.g., notions of Individual Fairness abiding by the seminal paradigm of Dwork et al. [2012], well Clustering problems. However, access to accurate similarity function should not always be considered guaranteed, and this point was even raised by Dwork al. [2012]. For instance, it is reasonable to assume that when the elements to be compared are produced by different distributions, or in other words belong to different "demographic" groups, knowledge of their true similarity might be very difficult to obtain. In this work, we present an efficient sampling framework that learns these across-groups similarity functions, using only a limited amount of experts' feedback. We show analytical results with rigorous theoretical bounds, and empirically validate our algorithms via large suite of experiments.
Introduction
Given a feature space I, similarity function 0 I + R2o measures how comparable any pair of elements x, x' I are. The function can also be interpreted as a distance function, where the smaller (z, x²) is, the more similar x and x' are. Such functions are crucially used in variety of AI/ML problems, and in each such case a is assumed to be known.
The most prominent applications where similarity functions have a central role involve considerations of individual fairness. Specifically, all such individual fairness paradigms stem from the the seminal work of Dwork et al. [2012], in which fairness is defined as treating similar individuals similarly. In more concrete terms, such paradigms interpret the aforementioned abstract definition of fairness as guaranteeing that for every pair of individuals x and y. the difference in the quality of service i and receive (a.k.a. their received treatment) is upper bounded by their respective similarity value (xx y); the more similar the individuals are, the less different their quality of service will be. Therefore, any algorithm that needs abide by such concepts of fairness, should always be able access the similarity score for every pair of individuals that are of interest.
Another family of applications where similarity functions vital, involves Clustering problems. In a clustering setting, e.g. the standard k-means task, the similarity function is interpreted as a distance
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

function, that serves as the metric space in which we need to create the appropriate clusters. Clearly, the aforementioned metric space is always assumed to be part of the input.
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 Dwork al. [2012], where it was acknowledged that the computation of a 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 Z. We loosely call each such distribution a "demographic" group, interpreting as the stochastic way in which members of this group are produced. 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.
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, the question at hand is "Should two students with comparable feature vectors (e.g., SAT scores, strength of school curriculum, number of recommendation letters) be really viewed as similar, when they belong to different groups?" At first, it appears that directly comparing two students based on their features can be an accurate way to elicit their similarity only if the students belong to the same demographic (belonging to the same group serves as normalization factor). However, 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.
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?
Clustering:
As suggested by earlier work on computing similarity functions for applications of individual fairness [livento, 2019], when obtaining similarity values is an overwhelming task, one 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, clearly not a sustainable solution. Therefore, our goal in this paper is to learn the ccross-groups similarity functions, using as few queries to experts as possible.
2 Preliminaries and contribution
For the ease of exposition, we accompany the formal definitions with brief demonstrations on how they could relate to the previously mentioned college applications use-case.
Let I denote the feature space of elements; for instance each x E I could correspond to a valid student profile. We assume that elements come from known "demographic" groups, where 7y E N. and each group é E [>] is governed by an unknown distribution Dj over I. We use x D; to denote a randomly drawn from Dr. Further, we use x E D, to denote that x is an element in the support of Dr, and thus x is member of group f. In the college admissions scenario where we have two demographic groups, there will be two distributions Dj and D2 dictating how the profiles of

---

privileged and non-privileged students are respectively produced. Observe now that for a specific I. we might have z E D and Dr. for E + E'. Hence, in our model group membership is important, and every time we are considering an element x E I, we know which distribution produced x, e.g., whether the profile x belongs to privileged or non-privileged student.
For every group l E hn] there is an intra-group similarity function de : I + Rzo. such that for all 2,y DE we have de(z, y) representing the true similarity between 2, y. In addition, the smaller de(2, y) is, the more similar I, Note here that the function de is only used to compare members of group (in the college admissions example, the function d1 would only be used to compare privileged students with each other). Further, common assumption for functions measuring similarity is that they are metric' [Yona and Rothblum, 2018, Kim et al., 2018, Ilvento, 2019, Mukherjee et al., 2020, Wang et al., 2019]. We also adopt the metric assumption for the function dy. Finally, based on the earlier discussion regarding computing similarity between elements of the same group, we assume that de is known, and given as part of the instance.
Moreover, for any two groups l and L' there exists an unknown across-groups similarity function Ote : I + R20, such that for all E Dr and y E De, ( y) represents the true similarity between x; y. Again, the smaller Tr, (x. y) is, the more similar the two elements, and for meaningful use of σe,e' we must make sure that x is a member of group E and a member of group E", In the college admissions scenario, 112 is the way you can accurately compare a privileged and a non- privilaged student. Finally, to capture the metric nature of similarity function, we impose the following mild properties on oe, which can be viewed as across across-groups triangle inequalities:
1. Property Mi: ore v) I de(x, 2) + (2, v) for every x, E DD and E Drr
2. Property M2: (. v) I de, 2) + de (2. y) for every z E De and y, 2 E De.
In terms of the college admissions use-case, Mi and M2 try to capture reasonable assumptions of the following form. If non-privileged student æ is similar another non-privileged student 2, and is similar to a privileged student y, then æ and y should also be similar to each other.
Observe now that the collection of all similarity values (intra-group and across scross-groups) in our model does not axiomatically yield a valid metric space. This is due to the following reasons. 1) If ore (I, 3) 0 for z E Dj and y Dr, then we do not necessarily have x y. 2) It is not always the case that (s y) I dz (x. =) + F (y, 2) for x. y E DD, 2 E Dr. 3) It is not always the case that oz (2, y) or.e" (2r, 2) aee e (2, y) for De, y E De, E Der.
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 geross-groups comparisons sounds unrealistic and very restrictive. Further, even though existing literature treats similarity functions as metric ones, the seminal work of Dwork et al. [2012] mentions that this should not always be the case. Hence, our model is more general than the current literature.
Goal of Our Problem: We want for any two groups f, l' to compute a function fe. I + Rzo, such that fe. (x., y) is our estimate of similarity for any E De and y E 'Dr. Specifically, we seek a PAC (Probably Approximately Correct) guarantee, where for any given accuracy and confidence parameters 8 E (0, 1) we have:
Pr x~ De. [[e.e (1) oee >
> S
The subscript in the above probability corresponds to two independent random choices, one x ~ De and one y/ Dr. In other words, we want for any given pair our estimate to be e-close to the real similarity value, with probability at least 1 - 5, where and 8 are user-specified parameters.
As for tools to learn fe,rr we only require two things. At first, for each group l we want set S; of i..dd samples from Dj. Obviously, the total number of used samples should be polynomial in the input parameters, i.e., polynomial in 7, 1 and J. Secondly, we require access to an expert oracle, which given any x E S; and y E Se for any l and f", returns the true similarity value dre (I, y). We refer to a single invocation of the oracle as query. Since there a cost to collecting expert feedback, an additional objective in our problem is minimizing the number of oracle queries.
A function d is metric if a) d(x, y) 0 iff b) d(x.v) = d(y, 2) and e) d(z,, y) S d(0, 2) + d(z, v)
for all a, v, z (triangle inequality).
3

---

2.1 Outline and discussion of our results
In Section we present our theoretical results. We begin with a simple and very intuitive learning algorithm which achieves the following guarantees.
Theorem 2.1. For any given parameters e, (0, 1), the simple algorithm produces a similarity approximation function fee for every & and E,, such that:
Pr(Error(eee) = =Pr (eeee
(2, v)1 w(r)]
x>Di,
y~Dri
= pr(e,) + per (e)
The randomness here is of three independent sourees. The internal randommess A of the algorithm, a choice ~ 'Dt, and choice y Dr. The algorithm requires I log 82 samples from each group. and utilizes -(1-1) log" 32 oracle queries.
In plain English, the above theorem says that with a polynomial number of samples and queries, the algorithm achieves an O(c) accuracy with high probability. i.e., with probability w (1-44 pe(,, pe (c. The definition of the functions pt is presented next.
Definition 2.2. For each group l, we use pe(e, 6) to denote the probability of sampling (e, 6)- rare element of Dr. We define as (e, 0)-raee for De. an element æ E Dr for which there a less than 8 chance of sampling x' ~ Dj with dz( x²) I E. Formally,
E Dj is (e, d)-rare iff Pra'ND, [de x') I c] < 6, and pe(c, 5) = Prz-D, [I is (c, 6. for Dz). Intuitively, a rare element should be interpreted 5 5-likely to encounter another element that is e-similar to it. For instance, a privileged student is considered isolated, if only small fraction of other privileged students have profile similar to them.
"isolated" member of the group, in the sense that it is at most
Clearly, to get a PAC guarantee where the algorithm's 's error probability for l and El is O()), we need Pe(c, 6), pe (c,
(6)) We hypothesize that in realistic distributions each pe(e, 8) 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, values pe(e, 6), which shows that any practical PAC-algorithm necessarily depends on them. This result further implies that our algorishm's error probabilities are indeed almost optimal.
also provide strong free lunch result for the
Theorem 2.3 (No-Free Lunch Theorem). For any given c,8 E 10, any algorithm using finitely many samples, will yield similarity approximations fi, with Pr [[Jr,e y)- (x, y)1 = w(t)] = Mmmx (pe(e, 5), pe (c, 6)} - =)); the probability is over the independent choices x ~ DD and ~ D'j as well as any potential internal randomness of the algorithm.
In plain English, Theorem 2.3 says that any algorithm using a finite amount of samples, can achieve e-aceuracy with a probability that is necessarily at most 1 max(pe(e, pe (c, + ie.. if max (pe(e, 8), pe (c, 5)} is large, learning is impossible.
Moving on, we focus on minimizing the oracle queries. By carefully modifying the earlier simple algorithm, we obtain a new more intricate algorithm with the following guarantees:
Theorem 2.4. For any given parameters 6, 1), the query-minimizing algorithm produces similarity approximation functions fe, for every and f', such that:
Pr(Error(e 0(5 pe(c, + (c
Pr(Erroree je)) is as defined in Theorem 2.1. Let N 1/ log g2- The algorithm requires N samples from each group, and the number of oracle queries used is at most
[( (E
Σ Qu)
PEM)) 8'
where Qe S N and EiQd < pe(e, N for each l.
At first, the confidence, accuracy and sample complexity guarantees of the new algorithm are the same those of the simpler one described in Theorem 2. Furthermore, because Qz S N, the

---

queries of the improved algorithm are at most 7(7 - 1)N, which is exactly the number of queries in our earlier simple algorithm. However, the smaller the values pr(e, 6) are, the fewer queries in expectation. Our experimental results indeed confirm that the improved algorithm always leads to significant decrease in the used queries.
Our final theoretical result involves a lower bound on the number of queries required for learning. Theorem 2.5. For all e, E (0, 1), any learning algorithm producing similarity approximation functions fúe with Pro-Deyy-De []fe,e (2z v) F2. (I. v)1 = w(c)] 0()), needs S0 queries.
Combining Theorems 2.4 and 2.5 implies that when all pe(c, are negligible, i.c., pe(e, - 0, the expected queries of the Theorem 2.4 algorithu are asymptotically optimal.
Finally, Section contains our experimental evaluation, where through a large suite of simulations validate our theoretical findings.
3 Related work
Metric learning is a very well-studied area [Bellet et al., 2013, Kulis, 2013, Moutafis et al., 2017, Suárez-Diaz et al., 2018]. There is also an extensive amount of work on using human feedback for learning metrics in specific tasks, e.g., image similarity and low-dimensional embeddings [Frome et al., 2007, Jamieson and Nowak, 2011, Tamuz et al., 2011, van der Maaten and Weinberger, 2012, Wilber et al., 2014]. However, since these works are either tied to specific applications or specific metries, 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 Dwork al. [2012]. This concept of fairness requires treating similar individuals similarly. Thus, 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 faimess definition of Dwork al. [2012] is very elegant and intuitive, the main obstacle for adopting 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 Ilvento [2019], Mukherjee et al. [2020] and Wang et al. [2019]. Ilvento [2019] addresses the scenario of learning a general metric function, and gives theoretical PAC guarantees. Mukherjee et al. [2020] give theoretical guarantees for learning similarity functions that are only of specific Mahalanobis form. Wang et al. [2019] 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 metric functions. In our case the collection of similarity values (from all de and o,,)) does not necessarily yield a complete metric space; see the discussion in Section 2. Hence, our problem addresses more general functions.
Regarding the difficulty in computing similarity between members of different groups, we are only aware of a brief result by Dwork al. [2012]. 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-groupe comparisons. new similarity function d' that approximates d, while minimizing the Earthmover distance between the distributions Dr, Drr- This is completely different from our work, since here we assume the existence of across- across-groups similarity values, which we eventually want to learn. On the other hand, the approach of Dwork et al. [2012] can be seen as an optimization problem, where the across-growe -groups similarity values need to be computed in way that minimizes some objective. Also, unlike our model, this optimization approach has a serious limitation, and that is requiring De, De to be explicitly known (recall that here we only need samples from these distributions).
order to achieve the latter for groups L and f', they find a
Finally, since similarity as distance is difficult to compute in practice, there has been line of research that defines similarity using simpler, yet less expressive structures. Examples include similarity lists Chakrabarti et al. [2022], graphs Lahoti al. [2019] and ordinal relationships Jung al. [2019].
4 Theoretical results
All proofs for this section can be found in the supplementary material
5

---

4.1 A simple learning algorithm
Given any confidence and accuracy parameters 8, (0,1) respectively, our approach is summarized as follows. At first, for every group we need a set St of samples that are chosen i.i.d according to De. such that |St] 3 log zz. Then, for every distinct and f', and for all Se and y E Se, we ask the expert oracle for the true similarity value 0r (x, (x, v). The next observation follows trivially.
Observation 4.1. The algorithm uses 3 log to samples, and 2(2-1) log" zo queries to the oracle.
Suppose now that we need to compare any I E DE and y E Dr. Our high level idea is that the properties Mj and M2 of dee (see Section 2), will actually allow to the closest element to x in Sy and the closest element to y in Sp. as proxies. Thus, let π (x) = arg min Es, de (z, x') and t (y) = arg esy de (ys y²). The algorithm then sets
Se. (z, v) = oe (π()), π (v))
where de. (Tx),, (y)) is known from the earlier queries.
Before we proceed with the analysis of the algorithm, need to recall some notation which was introduced in Section 2.1. Consider any group É. An element x E DD with PrywD, [de x²) S cc 5 is called an (e, 8) rrare element of Dr, and also pe(e, 6) == Prz-D, (xr is (c, ()-are for De).
Theorem 4.2. For any given parameters e, E (0, 1), the simple algorithm produces similarity
approximation functions fie for every É and E,, such that
Pr(Error(e, O pelc,)) + (c,
where Pr[Error((,e) is as in Theorem 2.1.
Observation 4. 1 and Theorem 4.2 directly yield Theorem 2.1.
A potential criticism of the algorithm presented here, is that its error probabilities depend on Pa (c. 6). However, Theorem 2.3 shows that such dependence is unavoidable (see appendix for proof).
4.2 Optimizing the number of expert queries
Here we modify the earlier algorithm in a way that improves the number of queries used. The idea behind this improvement is the following. Given the sets of samples SN, instead of asking the oracle for all possible similarity values oe (z. y) for every f, and every x E Sy and y E Se, we would rather choose set Re S St of representative elements for each group E. Then, oracle for the values ot. (I. y) for every E, f,, but this time only for every x E Re and y E Re. The choice of the representatives is inspired by the k-center algorithm of Hochbaum and Shmoys [1985]. Intuitively, the representatives RG of group will serve as similarity proxies for the elements of St, S₃ is assigned
would ask the
such that each Hence, if de (a., re rx)))) is small enough, x and (x( are highly similar, and thus rz(x) acts as good approximation of x. The full details for the construction of RG, Tę are presented in Algorithm
nearby rx(x)) E Re via mapping function r : St Rr.
Suppose now that we need to compare some x E Dj and y E Dr. Our approach will be almost identical to that of Section 4.1. Once again, let π(ж) (v) arg mis de (y, v/). However, unlike the simple algorithm of Section 4.1 that di- rectly uses (x) and (y)) the more intricate algorithm here will rather use their proxies (x()(x)) and re (T()). Our prediction will then be
arg min 2'( and
(e v) = =0 (re((((())))) re (T(U)))
where oz (re(m())) re (x(1)) is known from the earlier queries.
Theorem 4.3. For any given parameters c, (0,1) 1), the new query optimization algiooii produces similarity approximation functions Je for every l and l' such that
(r(Error(,,r)) = O + p)(c,)) + (c,
where Pr(Error( is in Theorem 2.1.
Since the number of samples used by the algorithm is easily seen to be log fr. the only thing left in order to prove Theorem 2.4 is analyzing the number of oracle queries. To that end, for every group l E [7] with its sampled set Sg, we define the following Set Cover problem.

---

Algorithm Training Phase
Accuracy and confidence parameters e, ò. For every group É E [r]] set S of.d. samples chosen according to De, such that |Se] = log 1 82
1: for each é E [>] do
2: H. - {x' E Se: de(x, x²) s 8 for each x E Se.
3: U Se. Re t @ and r2(3)) - z for each x E St.
4:
while U # 0 do
5:
Choose an arbitrary
U.
6:
Set Rg < Rs (z).
7:
WT t f2' U: H n Hy #0..
8:
Te(x') t for every x' E Wz. U+U W..
9:
end while
11:
end for
For every distinet e and e, and for every x E Rg and y Rg' ask the oracle for Tr y) and
store all these values.
13: For every l, return the set Rg and the function Te.
Definition 4.4. Let HCS = fa' Se de( 4e} for all Sy. Find C C Se minimizing |C], with UseC H St. We use OPT: to denote the optimal value of this problem. Using standard terminology, we say Se is covered by C of Usec He. and C feasible if it covers all æ E Sp.
Lemma 4.5. For every E [y] we have |Rel I OPT.
Lemma 4.6. Let N = log za For each group i E [y] we have OPT, S N with probability 1, and E[OPT] S } + pe(e, N). The randomness here is over the samples St.
The proof of Theorem 2.4 follows since all pairwise queries for the elements in the sets Rg are
Σ (1Re Σ Rel) < Σ (OPT: ΣOPT> EEEE
where the inequality follows from Lemma 4.5. Combining (1) and Lemma 4.6 proves Theorem 2.4.
Remark 4.7. The factor 8 in the definition of H at line 2 of Algorithm I is arbitrary. Actually, any factor p == ((1) would yield the same asymptotic guarantees, with any changes in accuracy and queries being only of an O(1) order of magnitude. Specificully, the smaller p is, the better the achieved uccuracy and the more queries we are using.
Finally, are interested in lower bounds on the queries required for learning. Thus, we give Theorem 2.5, showing that any algorithm with accuracy O(e) and confidence O()) needs 12(22/8' queries. This immediately leads to the following corollary characterizing the optimality of our algorithm.
Corollary 4.8. When for every i E hn] the value pe(e, 8)) is arbitrarily close to O, the algorithm presented this section achieves an expected number of oracle queries that asymptotically optimal.
Experimental evaluation
We implemented all algorithms in Python 3.10.6 and ran our experiments personal laptop with Intel(R) Core(TM) 17-7500U CPU @ 2.70GHz 2.90 GHz and 16.0 GB memory.
Algorithms: We implemented the simple algorithm from Section 4.1. and the more intricate algorithm of Section 4.2. We refer the former as NAIVE, and to the latter as CLUSTER. For the training phase of CLUSTER, we set the dilation factor at line 2 of Algorithm 1 to 2 instead of 8. The reason for this, that minimal experimental investigation revealed that this choice leads to good balance between accuracy guarantees and oracle queries. As explained in Section 3, neither the existing similarity learning algorithms [Ilvento, 2019, Mukherjee et al., 2020, Wang et al., 2019] nor the Earthmover minimization approach of Dwork et al. [2012] address the problem of finding similarity values for heterogeneous data. Furthermore, if the scross-groups functions a are not metric, then no approach from the metric learning literature can be used. Hence, basclines we used three general regression
7

---

models; an MLP, a Random Forest regressor (RF) and an XGBoost regressor (XGB). The MLP uses 4 hidden layers of 32 relu activation nodes, and both RF and XGB use 200 estimators.
Number of demographic groups: All our experiments are performed for two groups, i.e., 7 = 2. The following reasons justify this decision. At first, this case captures the essence of our algorithmic results; the Y > 2 case can be viewed as running the algorithm for 2 multiple times, one for each pair of groups. Secondly, as the theoretical guarantees suggest, the achieved confidence and accuracy of our algorithms are completely independent of 7.
Similarity functions:
In all our experiments the feature space is R", where d E N is case- specificc In line with our motivation which assumes that the intra-group similarity functions are simple, we define d1 and d2 to be the Euclidean distance. Specifically, for & {1, 2}. the similarity between any I. E D2 is given by
de(x, de(
Σ (a: y:) ic(d
V
For the across- across-groups similarities, we aim for a difficult to learn non-metric function; we purposefully chose a non-trivial function order to challenge both our algorithms and the baselines. Namely, for any E D and y D2, we assume
o (Ix
aa F2 Bs_ y + 0:13 .E|d]
Σ
(2)
where the vectors a, 3, 0 E Id are basically the hidden parameters be learned (of course non of the learners we use has any insight on the specific structure of r).
The function implicitly adopts paradigm of feature importance [Niño-Adan et al., 2021]. Specifi- cally, when x' and y are to be compared, their features are scaled accordingly by the expert using the parameters a, B, while some offsetting via 0 might also be necessary. For example, in the college admissions use-case, certain features may have to be properly adjusted (increase a feature for a non-privileged student and decrease it for the privileged one). In the end, the similarity is calculated in an fg-like manner. To see why a is not a metric and why it satisfies the necessary properties M1 and M3 from Section 2, refer to the last theorem the Appendix.
In each experiment we choose all a4, Br, O2 independently. The values a,,, B, are chosen uniformly at random from [0, 1), while the 0g are chosen uniformly at random from [-0.01, 0.01). Obviously, the algorithms do not have access to the vectors a, 3, 6, which are only used to simulate the oracle and compare predictions with the corresponding true values.
We used datasets from the UCI ML Repository, namely Adult (48,842 points 14 features) [Kohavi, 1996] and Credit Card Default (30,000 points 23 features) [Yeh and Lien, 2009], and the publicly available Give Me Some Credit dataset (150,000 points features) [Credit Fusion, 2011]. We chose these datasets because this type of data is frequently used in applications of issuing credit scores, and in such cases fairness considerations are utmost importance. For Adult, where categorical features are not encoded as integers, we assigned each category to integer in (1, #categories) ), and this integer is used in place of the category in the feature vector [Ding et al., 2021]. Finally, in every dataset we standardized all features through MinMax re-scaller. Due to space constraints, the figures for Adult and Give me Some Credit are moved to the supplementary material. However, the observed traits there the same as the ones shown here for Credit Card Default.
Datasets:
Choosing the two groups: For Credit Card Default and Adult, we defined groups based on marital status. Specifically, the first group corresponds to points that are married individuals, and the second to points that are not married (singles, divorced and widowed are merged together). In Give Me Some Credit, we partition individuals into two groups based on whether or not they have dependents.
Choosing the accuracy parameter e: To use meaningful value for e, we need to know the order of magnitude of (z. y). Thus, we calculated the value of oxx y) over 10, 000 trials, where the randomness was of multiple factors, i.e., the random choices for the a, 3, f, and the sampling of x and y. Figure 1 shows histograms for the empirical frequency of oxx y) over the 10, 000 runs In addition, in those trials the minimum value of a o y) observed was 1) 0. 1.1 for Credit Card Default, 2) 0. 155 for Adult, and 3) 0.0132 for Give Me Some Credit. Thus, aiming for an accuracy parameter that at least an order of magnitude smaller than the value to be learned, we choose = 0.01 for Credit Card Default and Adult, and e 0.001 for Give Me Some Credit.
8

---

Prequancy sourt disiaetiie
diviariiie
Precuecc din
100
(a) Credit Card Default
(b) Adult
(c) Give Me Some Credit
Figure 1: Frequency counts for (2, v)
Table 1: Error statistics for Credit Card Default
Algorithm
Average Relative Krror % oD Relative Error
(Absolute Errorj
SD (Absolute Erruryl
NAIVE
13388
3,410
0.636
1.633
CLUSTER
1593
3,391
0.646
1.626
MLF
3,671
4.275
I.465
1,599
RF
3.237
4,813
1,306
2.318
XGB
3.121
4.606
1.273
1.869
Confidence 8 and number of samples: All our experiments performed with 5 0.001. In NAIVE and CLUSTER, we follow our theoretical results and sample group. Choosing the training samples for the baselines is bit more tricky. For these regression tasks a training point is a tuple (z, (x, y)). In other words, these tasks do not distinguish between queries and samples. To be fair as possible when comparing against our algorithms,, provide the baselines with N + Q training points of the form (zr, a (I, y)), where Q is the maximum number of queries used in any of our algorithms.
log 52 points from each
Testing: We test our algorithms over 1, 000 trials, where each trial consists of independently sampling two elements x, y. for each group, and then inputting those the predictors. We are interested in two metrics. The first is the relative error percentage; if p is the prediction for elements 2; y and t is their true similarity value, the relative eтror percentage is 100 Ip tl/t. The second metric consider is the absolute error divided by e; p is the prediction for two elements and t their true similarity value, this metric is ll/e. We are interested in the latter metric because our theoretical guarantees are of the form [s(x,)) y) a (z, y) = O
Table shows the average relative and absolute value error, together with the standard deviation for these metrics across all 1, 000 runs. It is clear that our algorithms dominate the baselines since they exhibit smaller errors with smaller standard deviations. In addition, NAIVE appears to have tiny edge over CLUSTER, and this is expected (the queries of CLUSTER are a subset of NAIVE'S) s). However, shown in Table CLUSTER leads significant decrease in oracle queries compared to NAIVE, thus justifying its superiority. To further demonstrate the statistical behavior of the errors, we present Figure 2. This depicts the empirical CDF of each error metrie through bar plot. Specifically, the height of each bar corresponds to the fraction of test instances whose error is at most the value in the x-axis directly underneath the bar. Once again, baselines, since their corresponding bars are always higher than those of the baselines.
that algorithms outperform the
Disclaimer
This paper was prepared for informational purposes in part by the Artificial Intelligence Research group of JPMorganChase. and its affiliates ("JP Morgan") and a product of the Research De- partment of JPMorganChase. JPMorganChaa makes no representation and warranty whatsoever and
Table 2: Percent of decrease in queries when using CLUSTER instead of NAIVE
Credit Card Default
Adult
Give Me Some Credit
81.01%
80.40%
84.87%

---

The CDF thehe Selatie Errrr
The CDF (Atrckin Emer/cdde
Edst Vikz
(a) Relative Error Percentage
(b) (Absolute Error) /
Figure 2: Empirical CDF for Credit Card Default
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, 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.
References
A. Bellet, A. Habrard, and M. Sebban. A Survey on Metric Learning for Feature Vectors and Structured Data. Research report, Laboratoire Hubert Curien UMR 5516, 2013. URL https:
//hal.inria #r/hal-0166692)
D. Chakrabarti, J. P. Dickerson, S. A. Esmaeili, A. Srinivasan, and L. Tsepenekas. new notion of individually fair clustering: a-equitable k-center. In G. Camps- Valls, F. J. R. Ruiz, and I. Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 6387-6408. PMLR, 28-30 Mar 2022.
W. C. Credit Fusion. Give me some credit, 2011. URL https: //kggle wtt coon/comptiiionn GiveMeSomeCredit.
Ding, M. Hardt, J. Miller, and L. Schmidt. Retiring adult: New datasets for fair machine learning. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 6478-6490. Curran Associates, Inc., 2021.
C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel. Fairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS '12, 2012.
A. Frome, Y. Singer, F. Sha, and J. Malik. Learning globally-consistent local distance functions for shape-based image retrieval and classification. In 2007 IEEE 11th International Conference on Computer Vision, pages 1-8, 2007. doi: 10. 109/ 440888,..
D. S. Hochbaum and D. B. Shmoys. A best possible heuristic for the k-center problem. Mathematics of Operations Research, 1002),180-184, 1985. ISSN 0364765X, 15265471. URL http://www. jstor. org/stable//66897..
C. Ilvento. Metric learning for individual fairness, 2019. URL URL.httss//arztv..or//bbb// 00250.
K. G. Jamieson and R. D. Nowak. Low-dimensional embedding using adaptively selected ordinal data. In 20/1 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1077-1084, 2011. doi: 10. 1001099/Allcctoo.2011600022/
10

---

C. Jung, M. Kearns, S. Neel. A. Roth, L. Stapleton, and Z. S. Wu. An algorithmic framework for fairness elicitation, 2019. URL https://arxiv..o wbwgg//bb/9//.aaa 10660.
M. P. Kim, Reingold, and G. N. Rothblum. Fairness through computationallly-ounnde awareness. In Proceedings of the 32nd International Conference Neural Information Processing Systems, NIPS' 18, page 4847-4855 Red Hook, NY, USA, 2018. Curran Associates Inc.
R. Kohavi. Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In Proceedings of the Second International Conference Knowledge Discovery and Data Mining, KDD''6, page 202-207. AAAI Press, 1996.
B. Kulis. Metric learning: A survey. 2013.
P. Lahoti, K. P. Gummadi, and G. Weikum. Operationalizing individual fairness with pairwise fair representations. Proc. VLDB Endow., 53(4):506-518, dec 2019. ISSN 2150-8097. doi: 10.14778/33727116337222
URL https: /doii 110/ /4778/3372716 3372723.
Moutafis, M. Leng, and A. Kakadiaris. An overview and empirical comparison of distance metric learning methods. JEEE Transactions on Cybernetics, 47(3):612-625, 2017. doi: 10.1109/TCYB. 2016.2521767.
D. Mukherjee, M. Yurochkin, M. Banerjee, and Y. Sun. Two simple ways to learn individual fairness metrics from data. In Proceedings of the 37th International Conference on Machine Learning. ICML'20.. JMLR.org, 2020.
I. Ndao,Adam, D. Manjarres, Landa-Tonee and E. Portillo. Feature weighting methods: A review. Expert Systems with Applications, 184:115424, 2021. ISSN 0957-4174.
J. I.. Suárez-Diaz, S. García, and F. Herrera. tutorial distance metric learning: Mathematical foundations, algorithms, experimental analysis, prospects and challenges (with appendices on mathematical background and detailed algorithms explanation), 2018. URL https://arxti: org/abs/ /ttb////112 1812. 1892.05944.
O. Tamuz, C. Liu, S. Belongie, O. Shamir, and A. T. Kalai. Adaptively learning the crowd kernel. In Proceedings of the 28th International Conference on International Conference on Machine Learning, ICML'11, page 673-680. Omnipress, 2011. ISBN 9781450306195.
L. van der Maaten and K. Weinberger. Stochastic triplet embedding. In 2012 IEEE International Workshop on Machine Learning for Signal Processing, pages 1-6, 2012. doi: 10.1109/ML.SP.012.. 6349720.
H. Wang, N. Grgic-Hlaca, Lahoti, K. Gummadi, and A. Weller An empirical study learning fairness metrics for compas data with human supervision, 2019, URL atttps://arte org/ abs/1910. 10255.
M. Wilber, Kwak, and Belongie. Cost-effective hits for relative similarity comparisons. Pro- ceedings of the AAAI Conference on Human Computation and Crowdsourcing, 2(1):227-233, Sep. 2014. URL https::////. /ojs. aaai org/ index.dexx php/HCOMP/ aatticlle/iie///112222 httpa//ppppp/ooooaaarrreeeeee//s
I. Yeh and C.-H. Lien. The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert Systems with Applications, 06:2473-2488 03 2009. doi: 10.1016f.eesaa.200711.000
G. Yona and G. Rothblum. Probably approximately metric-fair learning. In International Conference on Machine Learning, pages 5680-5688, PMLR, 2018.

---

A Missing proofs
Proof of Theorem 4.2. For two distinct groups l and f", consider what will happen when we are asked to compare some x E Dj and y E Dy. Properties Mi and M2 of oz, imply
Q f (t, v) P. where
P = d1 x (x)) + og,e (*(x), x()) + de x (v))
Q Fre (T( π (v)) - dz(z, (2)) dy (v))
Note that when de(2, x (x)) < 3e and de (y. x (v)) S 3e, the above inequalities and the definition of (x, y) yield [ee (z. y) og,e y) I 6c. Thus, we just need upper bounds for A == Prss.an,, [Ve' E S d(ar,z')
3c] and B == Pr [ay E Se d(y.y' > 3e]. since the previous analysis and a union bound give Pr(Error(ree) S A
+ B. In what follows we present an upper bound for A. The same analysis gives an identical bound for B.
Before we proceed to the rest of the proof, we have to provide an existential construction. For the sake of simplicity we will be using the term dense for elements of De that are not (c, (-rare. For every x E Dj that is dense, we define B. = {a' E Dee de(2, S c). Observe that the definition of dense elements implies Pr.'~,, [x' E B₂] 2 5 for every dense x. Next, consider the following process. We start with an empty set 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 R. Further, for every dense x' E DD that is unmarked and has B₂ n By o 0, we mark x' and set (xx) Here the function e maps dense elements to elements of R. We continue this picking process until all dense elements have been marked. Since B, n By = 0 for any two 2, a e R and PIa [x' B3] 8 for E R. we have (R] 1/6. Also, for every dense we have dz ((x)) S 2e due to B2 O Bo(x) # O.
Now we are ready to upper bound A.
C= Pr (Va' E Se d(x, > 3e A is (e, rareee
S,
I Pr [x is (c, d)rrell = pe(c.
D:D
D = Pr (Va' E SSe :s::d<r,'') x') > 3e A is dense]
De
< Pr ER B, n. =
Pr n S. = 0] S [R[(1 - 531 S |R]e | < 8
St
EER
The upper bound for C is trivial. We next explain the computations for D. For the transition between the first and the second line we use a proof by contradiction. Hence, suppose that S n B, * 0 for every r R. and let i, denote
arbitrary element of Se n B,. Then, for any dense element x E Dr we have de(x,, π (x)) I de(2, ix(s)) < de(2,, (xx) + de(()()), (=(=)) < 2 + e = 3e. Back to the computations for D, get the third line we simply used a union bound. To get from the third the fourth line, we used the definition of r E R as a dense element, which implies that the probability
of sampling any element of B, in one try is at least 5. The final bound a result of numerical calculations using |R| < 1/2 and |S&| = 3 log ga.
To conclude the proof, observe that A- C + D, and using similar reasoning as the one in upper-bounding A we also get B < pe (c, 8) + 8.
Proof of Theorem 2.3. Given any e, 6, consider the following instance of the problem. We have two groups represented by the distributions D, and D2. For the first group we have only one element belonging to it, and let that element be xc In other words, every time draw an element from D, that element turns out to be x. i.e., Prai- [x' = x] = 1. For the second group we have that every IP.T. and (D2] is huge constant > 0, with 1 & 5.
y E D2 appears with probability 1
Now we define all similarity values. At first, the similarity function for D, will trivially be di (Ir, x:) = 0. For the second group, for every distinct y. E DD2 we define (y) 1. Obviously, for every y E D2 we set d2 y) O. Observe that di and d2 are metric functions for their respective groups As for the across-groups similarities, each (Ix y) for y E D2 is chosen independently, and it is
12

---

drawn uniformly at random from [0, 1]. Note that this choice of a satisfies the necessary metric-like properties M, and M2 that were introduced in Section 2.
Further, since e, ô E (0, 1), any y E D2 will he (c, -rrae::
1 D2
Pr (2)( s Pr V V'~D2
y)
<
y V'>D;
The first equality is because the only element within distance e from is y itself. The last inequality is because [2aa < ô. Therefore, since all elements are (e. 0)-rre, we have p2(e,
Consider now any learning algorithm that produces an estimate function f. For any y E D2, let us try to analyze the probability of having [f(x,,)) v) - a (I, u) wee). At first, note that when y E S2. we can always get the exact value f(z, y), since x will always be in Sj. The probability of having y E S2 is 1- (1 -1-11 1/ D21)), where N is the number of used samples. Since we have control over [P2) when constructing this instance, we can always set it to a large enough value that will give 1- (1 1/ c; note that this is possible because 1 - (1 1/(Dz]) is decreasing in [Dal and lim D2/-000 (1 11 (1-1111/1111 12) = 0. Hence,
Pr]lf(z, (1, 2) = (()) = (1 e) Prllf(a,)) ozz v)1 = w(E) 1 $ S2) +
(3)
y
When y will not be among the samples, the algorithm needs to learn (x, y) via some other value (ar, y/ for y' being a sampled element of the second group. However, due to the construction of o the values (z. y) and (z, y/) are independent. This means that knowledge of any oxx y²) (with y + y²) provides no information at all on a (zz y). Thus, the best any algorithm can do is guess f(x, v) uniformly at random from [0, 1]. This yields Pr[]f(x; 3) - ozx y) = w(e) y & S2] =
1 - Pr[lf(x, y) (x, y) = Occ) y $ S2 = 1 O = 6) O(c). Combining this with
(3) gives the desired result.
Proof of Theorem 4.3. For two distinct groups E and f", consider comparing some x Dr and y E Dr. To begin with, let us assume that de(x, (()) S 3e and de (v, (V)) S 3c. Further- more, the execution of the algorithm implies n(a) n H. m(((())) + 0, and thus the triangle in- ((())) give de(T(()
equality and the definitions of the sets H ==)))) He de (T(y), re (T(Y))) & 16c. Eventually:
16c. Similarly
de( < de(a, (((()))))))
< 19e
(y, rr (T - de
(T())
< 19c
For notational convenience, let = = (z. rz ( (+))) and B = de re (T Then, the metric properties Mi M2 of og and the definition of fe. (x, yield
(0,,0(0, y) fe, (r. v)1 - A + B 38c
Overall, we proved that when de(x, x (x)) < 3e and de (v. ग (v)) I 3e, we have (,,,,,,,,,)) oee (I, v)l < 38c. Finally, as shown in the proof of Theorem 4.2, the probability of not having de(æ, < 3e and de (y, ग (v)) S 3e, is at most 26 + pr(e, 6) + pe d).
Proof of Lemma 4.5. Consider a group E, and let C* be its optimal solution for the problem of Definition 4.4. We first claim that each H. with c C contains at most one element of Rg. This is
due to the following. For any E C*, we have de(2, S dz c) + drccc, x²) I 8c for all 2, E H In addition, the construction of Re trivially implies dx( x²) > 8e for all x, x' E Rg. Thus, no two elements of R& can be in the same HC with e C*. Finally, since Definition 4.4 requires all Re to be covered, we have RRel < |C OPT.
Proof of Lemma 4.6. Consider a group f. Initially, through Definition 4.4 it is clear that OPT, < |S,] = N. For the second statement of the lemma we need to analyze OPT, in a more clever way.
Recall the classification of elements According to this, an element can either be (e, -arree, or dense. Now we will construct solution Ce to the problem of Definition 4.4 as follows.
D; that was first introduced in the proof of Theorem 4.2.
13

---

At first, let St, be the set of (e, 6)- elements of St. We will include all of St.r to Ce, so that all (c, 6--rre elements St are covered by Ce. Further:
E || pepc,,
Moving on, recall the construction shown in the proof of Theorem 4.2. According to that, there
exists a set R of at most 3 dense elements from De, and function & that maps every dense element
E De to an element (z)) E R, such that (z. xx(x)) S 2c. Let us now define for each x E set G2 = fx' E De= z' is dense and (xx') = z), and note that de(2, x S (2(2,z) - de(2', x) S 4e for all 2, Gz Thus, for each a E R with G2 n St & 9, we place in C2 an arbitrary y G2 n S,
and that y gets all of G2 n St covered. Finally, since the sets G2 induce partition of the dense elements of De, C2 covers all dense elements of St.
Equation (4) and [R] < 1 yield B[[Ca]] < 1 + pe(e,8)N Also, since C2 is shown to be a feasible solution for problem of Definition 4.4, we get
OPT: S Ccpl = EIOPT] & Pe(e.8)N
Proof of Theorem 2.5. We are given accuracy and confidence parameters e, 8 E (0, 1) respectively. For the sake of simplifying the exposition in the proof, let us assume that 8 is an integer; all later arguments can be generalized in order to handle the case of 1/5 & N.
We construct the following problem instance. We have two groups represented by the distributions D, and 22. In addition, for both of these groups we assume that the support of the corresponding distribution contains } elements, and Prz-n [r = x'] = ó for every x E DD, as well as Pry ly
y'] = å for every y E D2.
For every x E D2 let di (I,x') = L, and (z, x) = 0 for every x E Dj. Similarly, for every v E DD2 we set dz(y, y²) = 1, and for every y E DD2 we set dz y) = 0. The functions d, and da are clearly metrics. As for the across-groups similarity values, each (zz y) for z E 'D1 and y D2 chosen independently. and it is drawn uniformly random from [0, 1]. Note that this choice of satisfies the necessary properties MI, .M2 introduced in Section 2.
In this proof are also focusing on a more special learning model. In particular, we assume that the distributions Dj and D2 are known. Hence, there is no need for sampling. The only randomness here is over the random arrivals x Dj and y D2, where and y are the elements that need to be compared. Obviously, the similarity function would still remain unknown to any learner. Finally, the 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 a 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 E Dj and y E D2- If the algorithm has queried the oracle for (r, y). it knows af (x, y) with absolute certainty. Let us study what happens when the algorithm has not queried the oracle for (Ir, y). In this case, because the values (xx,, 5') with x' E D2 and y/ E DD2 are independent, no query the algorithm has performed can provide any information for (Ir, Thus, the best the algorithm can do is uniformly at random guess a value in [0, 1]. and return that as the estimate for (xx y). If 22,, denotes the event where no query is performed for (x, y). then
p = Pr [lfe (z, v) 0e v) w(e) 22.v]
Pr (x, (0, w)1 = O(t) 22.zl
1 O(c)
= 2(1)
where the randomness comes only from the algorithm.
For the sake of contradiction, suppose the algorithm uses 9 = o o(1/8) queries. Since each (a. y) is equally likely to appear for a comparison, the overall error probability is
1/02- -4 P 2(1) 2(1) 2(1))
1/62
Contradiction; the error probability was assumed to be O
14

---

Proof of Corollary 4.8. When every pele, 6) is very close to 0, Lemma 4.6 gives E[OPT] Σ 8" Thus, by inequality (1) the expected queries are 2(1=1), Theorem 2.5 concludes the proof.
Theorem A.1. The function defined in Equation (2) not metric, and satisfies properties M2 for di (ar v) d2(x, v) Vieeta (a; y1)²² when oi, Br E [0, for all E [d].
Proof. The easiest way see that (z, y) is not metric, is realizing that it does not satisfy the symmetry property and also I = does not necessarily imply (æ, y) 0. Both of these issues stem from the offsets 0;. To verify that symmetry is violated let x, y be I-dimensional. and let I = 1, = 2 = 1,3 1,0 2. Then o(1,2) = 1, while o 1) = Next, let y have (x, y) = -1f 1 0.
y a,a 1, 1, = In this example, although
In the following we are going to show that o satisfies M1. The proof for M1 identical. At first, take x. U, IR.", such that E DD and E D2. Then:
02 v) = Σ
aa 24 - B yi + 0
((a 24 - 04 22) + (a; 2, B yi + 8:)1
EE|d [d]
&E Ed
Σ
1(o: . 04 - 04 2:)13
Σ EE(d
[(o: 2 3: Vi + 0z)
EE [d)
Σ
a [r - 2,13 (z2,1)
EE|d]
Σ
b 2 + t0(2,))
iE|d]
< d1 (xx (22
To get the first inequality we used the triangle inequality for lz. The second to last inequality is because af s 1 for all i, and the last inequality is because the Ey norm of a vector is always smaller than its lg norm.
B Additional experimental results
Table 3: Error statistics for Adult
Algorithm Average Relative Error %
SD of Relative Error
Average (Absolute Errori
SD of (Absolute Errory
NAIVE
1.199
3,381
0.847
2.382
CLUSTER
1.32T
3,383
0.849
2.383
MI.P
4.119
6.092
2. 303
1.977
3319
6.657
2.020
2.987
XGB
2,248
3.351
1.215
T.635
Table 4: Error statistics for Give Me Some Credit
Algorithu Average Relative Error & SD of Relative Error
Average (Absolute Errori/
SD of (Absolute ErrorWe
NAIVE
1.630
4,106
2.644
7.710
CLUSTER
1.645
7.665
MLP
5.819
9,073
7,588
8.750
RF
3.692
12.404
7,258
34.308
13.355
7.754
15

---

(a) Relative Error Percentage
(b) (Absolute Error)
Figure 3: Empirical CDF for Adult
TheCte of Sebiize Erter
ChP of LAbcobic briet Cousk eel
Kast Irar Vek
Nales Stbnkis Ever Lestoe
(a) Relative Error Percentage
(b) (Absolute Error) / e
Figure 4: Empirical CDF for Give Me Some Credit
16


Reviews:
[{"review_id": "vDNX6RX97J", "reviewer": "Reviewer_qRef", "summary": "This paper involves finding an inter-group similarity function with (limited) oracle advice when one has access to the intra-group metrics. The authors give theoretical guarantees about their algorithm and claim to have proven lower bounds on the performance of any algorithm.", "questions": "Some questions and comments/tips…\n\nLine 81 says that if x is in the support of D_l then it is a member of group l - so can the supports not overlap? This contradicts line 84\n\nIn Line 109 I would write “does not need to axiomatically…” - this phrasing points out that this property is a strength rather than a weakness. Maybe also point out that all metric spaces obey your properties.\n\nThe functions p_l should be defined before Theorem 2.1 is presented.\n\nIn Line 162 it’s not “\\epsilon accuracy and a probability at most 1-max{..}” since you use \\omega and \\Omega.\n\nIn Line 74 you mean N^2 not N", "limitations": "Authors have addressed limitations.", "rating": 2, "confidence": 4, "soundness": 1, "presentation": 3, "contribution": 1, "strengths": "I like this problem. The proposed problem is a nice contribution - but only if its solution improves on the more general learning of the whole metric (without knowledge of the intra-cluster similarities) in the case that the similarities are a metric (the fact that the assumptions of this paper are slightly less restricted than a metric is by itself not enough novelty in my opinion)\n\nThe experiments show this algorithm outperforms certain baselines (although similar works are not considered in the experiments).\n\nThe paper is well written from a language point of view.", "weaknesses": "I do not think that the algorithms themselves are innovative enough for a conference like NeurIPS.\n\nFrom Line 437 of the appendix it seems that the true definition of a rare element should be one whose probability that ALL of the N samples lie at distance more than epsilon away is greater than delta (not a single sample as is defined in the paper). Although the definition used doesn’t make Theorem 4.1 incorrect it means the bound is much weaker than it could be.\n\nThere seems to be something very wrong with Theorem 2.3…\n- Firstly, If I limit \\delta to 1 then in most cases every element is (\\epsilon, \\delta) rare so that p_l(\\epsilon,delta)=1 and hence the theorem essentially states that with a finite number of samples it is impossible to achieve \\epsilon-accuracy with probability no more than \\epsilon. This is clearly incorrect.\n- Secondly, if the instance space is finite then we can always choose a large enough (but still finite) number of samples such that w.h.p. every possible instance is sampled. If we apply the oracle to every pair we have, w.h.p. (a probability arbitrarily close to 1) found the exact similarity function. This contradicts the theorem.\n\nIt is not clear how other works compare to the result of this paper when it is a true metric space (since in this case the multiple distribution idea reduces to a single distribution problem). I do not think that handling the slightly more general non-metric case alone is sufficient for acceptance to a conference like NeurIPS.\n\nIn Line 287 the authors state that the metric algorithms cannot be used for non-metric. I suspect that they can still actually run but the bounds don’t necessarily hold (please correct me if I’m wrong). Since there is no theoretical comparison to the metric algorithms (when the similarity is a metric) I would have liked to see empirical comparisons to them in the case that it is a metric.\n\nA minor weakness is that in many applications you would be able to query instances without actually having sampled them.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their thoughtful comments.\n\nFirst we address the mentioned weaknesses of the paper.\n\n1. Even though are algorithm are relatively simple, their analysis and the analysis of the lower bounds are highly non-trivial.\n\n2. Here we address the concerns regarding the soundness of Theorems 2.1 and 2.3. Hopefully, after the clarifications it will become clear to the reviewer that  **both theorems are sound and correct**.\n    \n   1. The quantities $\\mathcal{A}, \\mathcal{B}$ in line 437 of the appendix are indeed the ones that you should analyze in order to upper bound the error probability of the algorithm. However, it is not necessary to define $(\\epsilon,\\delta)$-rarity based on those quantities as mentioned by the reviewer; this will give a very weak bound. Please not that we further analyze $\\mathcal{A}, \\mathcal{B}$ based on a union bound (lines 451-461), which (for the case of $\\mathcal{A}$ since the case of $\\mathcal{B}$ is identical) shows that $\\mathcal{A} \\leq \\mathcal{C} + \\mathcal{D}$, for two other quantities $\\mathcal{C}, \\mathcal{D}$. Given the breakdown to $\\mathcal{C}, \\mathcal{D}$ it is clear that our $(\\epsilon,\\delta)$-rare definition is **precisely the one needed**. Based on it the upper bound of $\\mathcal{C}$ is trivial (simply upper bound by the probability of encountering a rare element), and the bound for $\\mathcal{D}$ follows from a union bound over all non-rare elements. **On a high level, what the reviewer is suggesting is a \"lazy\" definition that would overcome the need for a technical analysis, albeit at the expense of a weaker bound. Our definition is combined with a careful breakdown analysis of the error probability, thus giving a tighter and more meaningful result.**\n\n    2. Thank you for the comment on Theorem 2.3. Although the Theorem itself is indeed correct we believe that the reviewer's comment can help us improve the statement of it and make it more clear. What we show in the proof of this theorem is the following. Given any $\\epsilon, \\delta \\in (0,1)$ and any algorithm that only uses only a finite set of $N$, **we can construct an input instance (distances and distributions) in which the algorithm will necessarily have** $\\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)$. In other words, we show a standard adversarial construction. We have no control over the algorithm and the number of samples it will use, but after seeing those we can give the algorithm a properly constricted instance in which it will fail. **Therefore, if we can always find an failing instance for any algorithm, then the statement of the theorem is true**. As for the counterexamples the reviewer gives:\n\n         1. Note that the first one (all elements are rare) is **exactly** the instance on which we based the construction of the distributions in the proof (see line 475 in the appendix). We precisely show that it is in such an instance that the algorithms would fail (given of course properly constructed distributions).\n         2. When your algorithm uses finitely many samples, the adversary can still construct a distribution of finite support where the algorithm will fail. This is what we do at line 466 in the proof.\n\n          *The problem with both example is that they implicitly assume that the algorithms have knowledge/control of the input instance*. This is not correct however when we are talking about creating an adversarial example (**of course you can solve specific instances, but this does not imply that every instance that is given will be solvable --the adversary gives you exactly those hard instances--**).   \n\n   3. We believe that calling the non-metric case slightly more general is a bold and unfair statement. Non-metric functions are **significantly** more complex to work with, and in our opinion this is why they have not been studied in the context of learning similarity for learning (Ilvento [2019], Mukherjee et al. [2020] and Wang et al. [2019] only study metric learning.). The triangle inequality is a powerful tool you can use in algorithmic analysis. As a simple example demonstrating how much more difficult things become in non-metric spaces, take clustering. Non-metric clustering rarely enjoys good theoretical guarantees. \n\n   4. There's nothing prohibiting you from testing a metric learners for this problem. However, 1) it won't yield any theoretical guarantees and 2) in our opinion this is an algorithm designed for a completely different problem. Thus, we chose to use strong regressors as our baselines.\n\nHere we address the questions posed by the reviewer.\n\n   1. In our model an element $x$ can be a member of multiple groups at the same time. There is no contradiction between line 81 and 84. Just because $x$ is let's say a member of the group \"Age: 25-40\" does not mean that $x$ cannot be a member of the group \"High Income\". Supports overlap, and every time we have an element $x$ we know which groups it belongs to.\n\n   2. Thank you for the rest of the suggestions. We will make sure we implement them.\n\nTo conclude, we hope that our comments clarified why **Theorems 2.1 and 2.3 are indeed correct**, and we wish that the reviewer would increase their score to an accept tier."}, {"review_id": "AGvb9GKhl2", "reviewer": "Reviewer_3J4J", "summary": "This paper studies the problem of learning a similarity function of items generated from different distributions. Precisely, there are two groups of items, and the items in each group follow a specific distribution and the group has an intra-cluster metric. This paper wants to learn a cross-group metric from limited number of samples with fairness and PAC error guarantee. This problem is critical for creating fair comparisons of items in heterogeneous groups. \nFurther, this paper provides upper bound and lower bound analysis on both i) error rates of algorithms with polynomial sample complexity; and ii) the sample complexity of a PAC (\\epsilon,\\delta) algorithm. From the analysis, I think the bounds on both error rates and sample complexity are reasonably good though still have rooms for improvements. \nFinally, the authors present the numerical results on real-world data sets. The numerical results show out-performed performance of the proposed algorithms. \n", "questions": "As stated in Weaknesses.", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Novelty: This paper studies an interesting, novel, and theoretical-fundamental problem. The algorithms are not very new, but already show good enough performance in this new problem, so it is okay. Overall, this paper is of high novelty. \n\nQuality: The paper has a high quality. The results are complete. It is not common to see well-established lower bound analysis, but this paper does it for both error rates and sample complexity. Also, the upper bounds and lower bounds are reasonably close, and the gaps between them are not very high, which is good enough for initial research. The paper also conducts nice numerical experiments on real-world data to confirm the theoretical conclusions, which strengthen this paper's quality.\n\nClarity: This paper is well written. It has a clear story-telling: it introduces the problems, explain the mathematical formulation, state the theoretical results, and present the proofs well. \n\nSignificance: In my personal opinion, this is a very important problem in terms of theory, as it is actually understanding the fundamental learnability of aggregating two or multiple metric spaces together. In terms of practice, I am not very confident, but the examples such as the student case given in the paper are convincing. Overall, the I think this paper is significant enough. ", "weaknesses": "No major weakness found. The paper is good overall. One minor question: How often would the real-world scenarios have non-complete metrics, as this is an improvement of this paper? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their very positive feedback. We are glad to see that our work gets appreciated.\n\nWith regards to your question, we hypothesize that in practice, the vast majority of application the similarity scores will not be forming a metric. Take for instance our second motivating example, where we have two distinct data sources. In this case, experts usually have a \"private\" transformation function that embeds one feature space to the other. This transformation will most likely be based on domain knowledge taking the form of complex rules, e.g., if features $S$ (a being a set of features) in the first space take a values $f(S) \\in \\mathbb{R}^{|S|}$, then features $W$ in the second space should take values $g(f(S)) \\in \\mathbb{R}^{|W|}$ ($W$ being a set of features). Clearly such complex transformation will most likely result in arbitrary non-metric space.   \n\nFor fairness related applications, we refer to a comment in the seminal paper of Dwork et al., where it is mentioned that such similarity functions are not necessarily metric. "}, {"review_id": "GrCMrJiKWS", "reviewer": "Reviewer_voHg", "summary": "The paper is about a mechanism to compare elements  of a set that belong to two distinct distributions when two distinct sets of features for each distribution.   This is a natural problem that arises in many practical settings.  The paper presents the underlying problem and the formal framework with some guarantees assuming some 3rd database (oracle) has answers about comparability of any pair of elements.", "questions": "\nSee above.", "limitations": "\nThe major limitation of this work is the assumption of the availability of an oracle that can provide the ground truth similarity between any pair of elements of the set across a broader set of features than what's given.  Eg, in the sport (say) of 100 meter sprint, on the one hand we have the age, height, weight, sex/gender, ethnicity, etc., of the competitors and on the other hand, we have the diet and medications for some.   Naturally a good similarity function to use to predict the athletes' performance needs to incorporate both sets of features.  So in such cases, where does one look for this all-knowing oracle even if the number of queries to it are limited?", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "\nCompared to other papers I have to review for NeurIPS this year, the authors of this paper go out of their way to explain what they're trying to do and motivate the theoretical results they obtain.\n\nThe topic is a good one -- often the same data appear in different databases with different attributes and this paper provides a mechanism to construct a similarity function across different features *assuming* there is an oracle that can compare across different features.\n\n", "weaknesses": "\n\nThe basic idea of this paper is well explained and illustrated.  However, unlike much of the rest of the discussion in this paper, the \"no free lunch\" theorem is not explored in full.  A key question anyone would have is how rare or common is it for max { p_l, p_l' } is large and therefore the framework introduced in this paper is not applicable?  The authors could use the datasets they used for experimental results to shed some light on this question.  This is actually the 1st question anyone wishing to use this result would be asking themselves.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your positive comments. We are glad to see our work getting appreciated.\n\nRegarding the weakness you mentioned. This is indeed a great question and we can certainly investigated it even more. Our experimental results show that $\\max (p_\\ell(\\epsilon, \\delta), p_{\\ell'}(\\epsilon, \\delta))$ is indeed small in the datasets we tested (otherwise we wouldn't be achieving accurate results), however we did not explicitly quantify how small this value is. Nonetheless, this is actually easy to do. Since we have the bound of the algorithm and we know $\\delta$, we can work backwards and compute this quantity. Specifically:\n\n   1. In Credit Card Default and Adult this value is around 0.01 \n   2. In Give me Some Credit this value is approximately 0.03"}, {"review_id": "4r7q4xgxfK", "reviewer": "Reviewer_L6oz", "summary": "This work considers PAC-learnable algorithms for estimating a intra-group\nsimilarity function where:\n1. intra-group similarity functions are metrics and given in advance,\n2. inter-group similarities satisfy a notion of the triangle inequality.\nIt is assumed that points are always labeled by the group to which they belong.\n\nThe authors present two algorithms Naive and Cluster, and\ngive PAC-learning guarantees for them (i.e., the sample complexity needed for\nthe learned similarity function to be $\\varepsilon$-close to the true\nsimilarity function with probability at least $\\delta$). The clustering\nalgorithm uses a ``representative'' subset of each groups samples before\nquerying inter-group similarities to reduce the query complexity. The authors\ngive substantive experiments to empirically study their algorithms.", "questions": "- [line 22] If two objects $x$ and $y$ are identical, they have large\n  similarity? Maybe it makes sense to use the distance-version of $\\sigma$ here\n  so that it is clear the upper bound on the difference is zero for identical\n  objects.\n- [line 171] Is $Q_\\ell$ a random variable? If so, it might be worthwhile to\n  make that more explicit.\n- [line 229] Is a factor of $1/2$ missing in the query complexity? Are we\n  assuming that $\\sigma(x,y)$ is symmetric?\n- Does the similarity function in Eq. (2) have the property that inter-group\n  points are further away on average than intra-group points?", "limitations": "NA", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The \"simple learning algorithm\" is indeed simple and clean with strong\n  guarantees (Theorem 2.1).\n- The idea of using $k$ centers from each group's samples as representatives is\n  a natural improvement over the simple algorithm.\n- Very good experiments where the authors define a challenging similarity\n  function to try to recover:\n  * Creating two groups based on the \"married\" feature is an excellent instance\n    of what the paper aims to study.\n  * The benchmark algorithms MLP, RF, and XGB each see at least as many samples\n    as the proposed algorithms, and are therefore fair (assuming they fully\n    trained).", "weaknesses": "- In section 2.1, you say you begin with a simple algorithm, but it is never\n  described before Theorem 2.1. Consider giving a quick description to the\n  reader before they take in the theorem statements.\n- The presentation could be improved slightly: less motivation in the intro and\n  more details in the main text (e.g., proof sketches).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We will certainly take your feedback into consideration.\n\nWe first address the weaknesses that you mentioned:\n\n   1. Even though there is a description of the simple algorithm in lines 225-228, we will try to make it more explicit.\n   2. We will try to work on the overall presentation as you suggested, giving more details in the main text.\n\nAddressing the questions:\n\n   1. If two objects are identical, then their similarity/distance is 0. This basically shows that the two objects are in the same position in the space.\n   2. $Q_\\ell$ is indeed a random variable. We can explicitly mention this in Theorem 2.4.\n   3. You are right. This is a typo that we can fix.\n   4. Our math works even when $\\sigma(x,y)$ is not symmetric. However, having it being symmetric is a natural assumption in real application. Nonetheless, our math can work for a more general case (not necessarily symmetric).\n   5. \"Does the similarity function in Eq. (2) have the property that inter-group points are further away on average than intra-group points?\" Not necessarily. We do not need to make such an assumption. Our math works regardless of that.\n\nTo conclude, we would appreciate if the reviewer reconsiders their score. **We feel like the weaknesses that are mentioned are not substantial enough to justify a reject rating.**"}]

Author rebuttal:
We thank all of our reviewers for their time and their thoughtful comments. We reply to each one individual below.

Meta-review: The reviewers have wildly different appraisals of this paper. The two reviewers who want to accept the paper have written very short reviews. The most negative reviewer seems not to have the right background to assess the paper, and is overconfident in their negative assessment. The last reviewer only criticizes the presentation, and only mildly. To me, the paper looks very well motivated, with excellent presentation - the authors have taken pains to explain their ideas clearly - interesting, and important.
Decision: Accept (poster)