Multi-Group Proportional Representation in Retrieval
Authors: Alex Oesterling
Claudio Mayrink Verdun
Alexander Glynn
Carol Xuan Long
Lucas Monteiro Paes
Sajani Vithana
Martina Cardone
Flavio Calmon
Venue: NeurIPS 2024 poster (2024)
Keywords: Fairness
Proportional Representation
Multi-Group Fairness
Primary area: fairness
TL;DR: We introduce a novel metric for ensuring multi-group proportional representation over sets of images. We apply this metric to retrieval and propose an algorithm that maximizes similarity under a multi-group proportional representation constraint.

Abstract: Image search and retrieval tasks can perpetuate harmful stereotypes, erase cultural identities, and amplify social disparities. Current approaches to mitigate these representational harms balance the number of retrieved items across population groups defined by a small number of (often binary) attributes. However, most existing methods overlook intersectional groups determined by combinations of
group attributes, such as gender, race, and ethnicity. We introduce Multi-Group Proportional Representation (MPR), a novel metric that measures representation across intersectional groups. We develop practical methods for estimating MPR, provide theoretical guarantees, and propose optimization algorithms to ensure MPR in retrieval. We demonstrate that existing methods optimizing for equal and proportional representation metrics may fail to promote MPR. Crucially, our work shows that optimizing MPR yields more proportional representation across multiple intersectional groups specified by a rich function class, often with minimal compromise in retrieval accuracy. Code is provided at https://github.com/alex-oesterling/multigroup-proportional-representation.

Multi-Group Proportional Representation in Retrieval
Alex Oesterling" Harvard University
Claudio Mayrink Verdun"
Carol Xuan Long Harvard University
Alexander Glynn Harvard University
Harvard University
Lucas Monteiro Paes Harvard University
Sajani Vithana
Martina Cardone University of Minnesota
Flavio P. Calmon Harvard University
Harvard University
Abstract
Image search and retrieval tasks can perpetuate harmful stereotypes, erase cultural identities, and amplify social disparities. Current approaches to mitigate these representational harms balance the number of retrieved items across population groups defined by a small number of (often binary) attributes. However, most existing methods overlook intersectional groups determined by combinations of group attributes, such as gender, race, and ethnicity. We introduce Multi-Group Proportional Representation (MPR), a novel metric that measures representation across intersectional groups. We develop practical methods for estimating MPR, provide theoretical guarantees, and propose optimization algorithms to ensure MPR in retrieval. We demonstrate that existing methods optimizing for equal and proportional representation metrics may fail to promote MPR. Crucially, work shows that optimizing MPR yields more proportional representation across multiple intersectional groups specified by rich function class, often with minimal compromise retrieval accuracy. Code is provided at https: / //g thub. com/ alex-oester ing/ /ml - rrppooeeooal-rrpppeeennnnttotto
Introduction
recognized objective in fair machine learning (ML) is discovering, reporting, and mitigating representational harms [1-3]. Representational harms arise when systems reinforce and perpetuate the marginalization of population groups based on characteristics such as race, socioeconomic status, cultural background, and gender [1, 4-6), 6]. These harms often manifest through the biased portrayal or misrepresentation these groups, stereotype reinforcement, and erasure of cultural identities [7, 8). Representational harms have been widely documented in ML systems. For instance, many freely available datasets used ML are not geo-diverse [9], and generative models can output images that under-represent demographic minorities across gender and racial identities [10-12].
We focus on representation retrieval tasks. Representational harms in retrieval and ranking tasks arise when retrieved items do not accurately reflect the true diversity and proportions present in reality, perpetuating harmful stereotypes and biases [13]. For instance, Kay al. [2] demonstrated that, in 2015, only 10% of the top 100 results for CEO in Google Image Search were women, despite 28% of CEOs in the US being women, and recent studies [14, 15] have demonstrated that this bias still present in modern image search engines, Later, Otterbacher et al. [16] showed that the search engine Bing usually produced twice as many men as compared to women when queried with the word "person"" Finally. [17] systematically studied gender biases in image representations by auditing the four most important image search engines: Google, Bing, Baidu, and Yandex. particular, among other findings. this study showed that when qualifier such "intelligent" is added to the query "person", the engines still exhibit significant gender discrepancy: see also [1, Chapter 7]. When
Equal contribution, correspondence acesterling0g harvard. edu
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

retrieval is based on a search over vector embeddings of images and text, biases in embedding models can propagate to retrieved results, leading to disparate representation of people by demographic groups such as gender or race [18-20], as well as propagating spurious correlations from the dataset more broadly [21] or distorting results due to stereotypes present the representation [22]. Though correlations between unrelated semantic concepts do not necessarily constitute representational harms, a wealth of research charts undesirable bias in embedding models, including publicly available vision- lision-angguae embedding models such as CLIP [23] used for retrieval. Bias in embeddings can lead to bias in retrieval [24-26]. In fact, recent work by Srinivasan et al. [27] argues that many image retrieval systems lack "social diversity" perceived by humans.
Several interventions aim to control gross statistical deviations in group representations in retrieval. A common approach is ensuring equal representation of pre-defined population groups in retrieved items [28, 29]. An alternative goal is proportional representation (PR) [20, 30), where the target representation of different groups is proportional to some reference population or statistic. Various interventions have been proposed to achieve equal or proportional representation, including optimizing for diversity in addition to the similarity in retrieval [27, 31J, directly selecting the objects retrieved based on balancing known or predicted sensitive attributes [29] and, for vector databases, modifying embeddings directly to remove information about group-defining attributes [18, 20].
Achieving proportional representation across multiple intersectional groups is challenging. as existing faimess interventions typically consider only small number of pre-defined groups. Ensuring repre- sentation across individual groups (e.g.. given by gender or race) does not guarantee representation across intersectional groups (e.g., given by gender and race), as demonstrated in Table 1 (and Table 5 in the Appendix). The study of intersectionality and its consequences rooted in work in law and the social sciences [32-34] and has been well-discussed problem for several decades. In machine learning systems, lack of intersectional representation can contribute to the invisibility of historically marginalized groups determined by multiple axes of identity [35], or their mistreatment through "fairness gerrymandering." where interventions on fairness for specific groups may harm fairness on intersectional subgroups [36]. However, as the number of group-denoting attributes increases, the number of intersectional groups grows exponentially, quickly surpassing the number of retrieved items and limiting the achievable proportional representation. In fact, achieving optimal proportional representation across multiple attributes has been shown to be NP-hard [37].
We propose a metric called Multi-group Proportional Representation (MPR) to quantify the represen- tation of intersectional groups in retrieval tasks. MPR measures the worst-case deviation between the average values of a collection of representation statistics computed over retrieved items relative to reference population whose representation we aim to match. The set of representation statistics is given by a function class C, where each function E C maps a retrieved item x to real number. For instance, c(ar) E 1-1,1} may denote binary group membership for an input x. In theory, C can be given by bounded complexity function classes, such as linear functions shallow decision trees. In practice, C are functions defined over item attributes, such as vector embeddings or group-denoting labels, enabling MPR to measure proportional representation across complex, intersectional sub- groups. Compared to naively counting the number of retrieved items across a (potentially exponential) number of pre-defined groups, MPR offers more flexible, scalable, and theoretically grounded metric for multi-group representation in retrieval.
In addition to introducing and carefully motivating the MPR metric, cf. Section 2, we make three contributions. First, we show how to compute MPR for several function classes in Section 3. Computing MPR relies on a curated dataset that represents the desired population whose proportional representation we aim to reflect in retrieved items. We derive sample complexity bounds for the size of this curated dataset based on the complexity of the function class C. We also prove that MPR can be computed in closed form for certain function classes or with a regression oracle. Second, we propose MOPR, algorithm that retrieves items from vector database to maximize their average similarity to a query embedding while satisfying an MPR constraint relative to the curated dataset (Section 4). MOPR achieves this by iteratively calling an oracle that computes MPR violations, yielding both relevant and representative retrieved items. Third, we evaluate MOPR on retrieval tasks using datasets such as CelebA [38], the Occupations dataset [31], Fairface [39], and UTKFace [40]. In section 5, we show that MOPR Pareto-dominates competing approaches in balancing retrieval similarity and MPR.
2

---

Related Work. Broadly speaking, existing work on fair and diverse retrieval with pretrained embeddings either: 1) modifies the embedding space to prioritize downstream faimnsss, or 2) provides retrieval algorithms optimizing for diversity or fairness.
Mitigating Bias in Embedding Space. Various approaches have been proposed produce vector embeddings of text and images that target diversity or mitigate bias. These include modifying loss functions to encourage group fairess [41]. adversarial training [42, 433, disentangling representations [44], and in-processing fair sampling methods for gender imbalance [18]. Many popular embedding models are not trained with such approaches. so post-pree processing methods for fairness have also been developed for multimodal models such as CLIP [23], including CLIP-clip [18], CLIP- "LIP-debias [20], and FairCLIP [19]. Recent work by Srinivasan et al. [27] builds upon the pretrained image-text model CoCa and leverages text-guided projections to extract an embedding, called PATHS, that captures complex notions of diversity in people, and then conduct diverse retrieval with a greedy algorithm. However, code for implementing and reproducing PATHS embeddings was not available at the time of publication, In our experiments, we report the MPR achieved by CLIP-clip and CLIP-debias in retrieval tasks and approximate the greedy retrieval algorithm proposed in [27] with vanilla CLIP embeddings. Unlike the aforementioned methods, MOPR is not based on modifying embeddings.
Retrieval Algorithms with Diversity or Fairness. Instead of modifying embeddings, several methods aim to promote diversity, given possibly biased embeddings. Given an additional diversity constraint, a popular approach is Maximal Marginal Relevance (MMR) [45], where items are greedily retrieved in order to maximize linear combination of similarity and diversity metries. Celis al. [30] and Celis and Keswani [31] focus on diversity and fairness in image retrieval, using reweighing method that combines similarity and MMR to select diverse yet relevant images. Alternatively, the Post- Hoc Bias Mitigation [29] method aims to achieve equal representation over pre-defined attribute (such as gender) through calls to an oracle classifier and selecting a balanced group of images. We extend this prior work in two key ways: (i) we aim to achieve proportional representation across intersectional groups, going beyond the representation of two groups defined by binary attributes; (ii) MOPR explicitly balances MPR and retrieval similarity via an optimization that controls for both, offering an efficient alternative to greedy MMR- methods.
Diversity Metrics A traditional measure of diversity for a set is the pairwise similarity of the retrieved items [46]. However, the general visual (dis)similarity metric is insufficient in optimizing for people- related diversity such as skin tone or gender [30]. When the attribute (e.g.. race) along which diversity is optimized is known, or, in other words, we have access to a ground truth attribute label, one can use fairness definition-derived metrics such as proportional representation (see next section and [47]. For more complex notions of diversity that aim to capture intersectional or subtle sociocultural identities (e.g., cultural backgrounds, lifestyles, nationalities, religions), human annotators can be employed to determine the selected set of images is more diverse than the baseline (retrieval based on similarity to query only) [27]. MPR complements existing metrics by providing rigorous approach to measuring representation across complex, intersectional groups defined by a rich class of functions. However, with any fairness metrie, MPR has limitations always align with human perceptions of representation. In particular, we underscore the importance of involving stakeholders in defining representation goals and auditing retrieval systems.
Section 6 and may not
Multi- Multi-Grouu Fairness. Our work directly informed by the burgeoning literature on multi-group fairness in classification, particularly the work of Hébert-Johnson et al. [48], Kim et al. [49, 50] who proposed rigorous frameworks of multi-group fairness auditing and post-processing to ensure fair predictions across identifiable subgroups. Recent efforts in this field include [51-53], which analyze sample complexity aspects of measuring and reporting multi-group representation, and [54, 55] who develop stronger variants of multi-group fairness notions. Unlike prior work, we focus on group representation in retrieval rather than multi-grout fairness in classification and regression.
Multi-Attribtte Proportional Representation. A recognized challenge in computational social choice research building committees, groups, or sets of items that ensure proportional representation across several attributes [56-59]. The work most closely related to ours is by Lang and Skowron [37], which introduced the problem of multi-attribute proportional representation, where a set of items must be selected to reflect desired distributions over multiple attributes simultaneously. Their work established fundamental computational complexity results, showing that finding optimal proportional representation is NP-hard and developed approximation algorithms and integer linear programs for promoting proportional representation across attributes. While our work shares similar
3

---

goals, our MPR metric takes a different approach by measuring the worst-case deviation over computationally-ideniffaaa groups defined by a function class C. This formulation connects naturally with statistical learning theory through MMD [60] and sample complexity bounds (Propositions and 2). Though we use the term nulti-group rather than multi-attribute to emphasize connections with the burgeoning literature on multi- grotii fairness [48, 49], both terms describe related problems of ensuring representation across multiple dimensions. We also highlight that work on multi-attribute representation in computational social choice (including [37]) strives for proportional representation marginally on each attribute, while our primary goal with this work is to achieve intersectional representation. Finally, while [37] similarly seeks match retrieved candidates to target distribution, we focus on database retrieval rather than social choice applications. The rich history of proportional representation in social choice theory and political sciences provides, however, important context for our work. We briefly discuss these connections in Appendix E. There, we elaborate on how our approach relates and differs in terms of representation formulation from [37].
2 A Multi-Group Proportional Representation Metric
Preliminaries. Consider retrieval dataset of items from which we aim retrieve relevant entries, denoted by Dn= = {-",,.. x; )- We assume that x. E Rd x G. where G is a set of additional labels for each item. For example, items xς can be d-dimensional embeddings of images, videos, textual content, in which case G 0. Alternativeyy, 2द (e,, gz). where e, E Rdd is an embedding and gi is a vector of labels indicating group membership (c.g., gender, race, ethnicity).
Given a query embedding q E R2, the goal of retrieval is to search and return the top-k most similar items to q in n. The similarity between an embedding of q and items in Dn is measured according to metric Rd x Rd > RR. Throughout the paper, we assume that DDz is a vector database and is cosine similarity between embeddings, though this formulation can be generalized. To retrieve items from DR. users prompt query q (e.g.. "Fortune 500 CEOs") which is then embedded Rd. Ideally, the user receives retrieved items R(q) = { x C DR such that x(q, x5) 2 k(q, x)) for all & Rga) and E [k:]
The simplest setting for measuring representation
consider only two population groups denoted by a binary variable setting commonly found in the fair retrieval and generation literature [18, 19]. In this case, group membership is determined by a group-denoting function c: F x 9 - (-1, 1}. For an item æt. c(x:)) indicates membership to group -1 or 1 (e.g., male/female) based on its embedding o and associated labels gi. If the retrieval dataset Dn contains annotations for group membership, c(x;) can simply return the relevant feature from g:. However, when group labels are not present (i.e., G = 0), c(x;) ) can be implemented as a classifier that predicts group membership based on the item's 's embedding e;
With a group-denoting function c(x") in hand, we can measure the representation of each group in set of retrieved items R(q). One popular constraint for representation is equal representation [2, 28], which aims to ensure that the number of retrieved items in each group approximately the same, i..., 1 ExteR(q) c(x') x O. An alternative metric is proportional representation [20, 61], which quantifies the deviation of group membership from reference distribution Q. Methods that promote proportional representation aim to ensure ă Ex' c(x") = Egg [e(X)]. Here, the measure Q captures the distribution of a reference population whose representation statistics we aim to match. For example, if Q were the distribution of individuals in the US, Byg [c(X)] could measure the proportion of men vs. women in the US and be approximated using Census data.
Proportional representation generalizes equal representation since different groups are rarely uni- formly distributed over given population. Naturally, the choice of distribution Q is application and context-dependen we revisit the choice of Q below. Importantly, if Q is biased, then biases will be propagated to the retrieved items.
Multi-Group Proportional Representation. We aim to ensure that retrieved items represent individuals from diverse and intersectional population groups. Instead of measuring proportional representation in terms of the average of single group-denoting function c(x"), we consider class of Q-maasurable functions, the representation statistics class, C C {c: Rdd G + R.. This set C may represent multiple, potentially uncountable overlapping groups. We formally define groui- proportional representation next.

---

Definition 1. For a reference representation distribution Q, set of Q-measurable set of repre- sentation statistics C, and set of retrieved items R, we define the Group Proportional Representation (MPR) metric as
MPR(C, R. Q) f sup
Σ x'ER
c(x') EElc((X]]
cEC
A set of items R is (C,p) ())mmmi--grouup proportional representative of Q if MPM Q) p.
The MPR metric quantifies the "representativeness" of a rich class of statistics, denoted by functions in C, within set of retrieved items R. This generalization is crucial for capturing intersectional groups. For example, C could contain functions that map items to demographic groups based on race, gender, age, or combinations thereof. Alternatively, when labels in & contain such group-denoting attributes, can represent decision trees of a given depth over features (e.g,, all combinations of pairs of race, gender, and age). The MPR metrie compares the empirical average of each C over the retrieved set R to its expectation under the reference distribution Q. By defining Q appropriately, we can flexibly specify different statistical representation goals, such as equal representation (Egle(X)] 0 for binary <) or proportional representation w.r.t. a target population. Measuring representation requires defining what constitutes "fair and proportional representation." " While equal representation may suffice for binary groups, proportional representation of more complex intersectional groups requires care. The choice of representation reference statisties (given by the distribution Q in the definition of MPR) should be -etieeddtoondeeedeeet context-aware, and culturally sensitive.
Remark MPR equivalent to the maximum mean discrepancy (MMD) of representation statisties in C between the empirical distribution over retrieved items R and the reference distribution Q. MMD-based metries have a long history [60, 62] and are used in hypothesis testing for comparing distributions. MMD is particular case of the Integral Probability Metric (IPM) [63, 64), allowing us to borrow from the rich literature on IPMs to measure and ensure MPR in practice.
Remark 2. MPR can be viewed as the "representation in retrieval" counterpart of multi- group fairness metrics found in classification, such as multiaccuracy [49] and multicalibration [48]. Whereas multiaccuracy and multicalibration measure if classification error residuals are correlated with any group represented within a class C, MPR captures proportional representation of groups in C within a set of retrieved items- - a fundamentally different problem. The idea of representing groups in terms of "computationally identifiable" class of functions C' is directly inspired by the multi multi-group fairness in classification literature, and we adopt similar notation (i.c., e and C).
Curated Datasets for Proportional Representation. A key challenge in computing MPR is selecting the reference representation distribution Q and measuring the expectation of functions in C against this distribution. In the simple case where C consists of a small number of functions indicating membership in individual groups, we could potentially set the proportional representation targets Eq [c]) for each group E C manually, e.g., by defining a target fraction of men/women or individuals from different ethnic backgrounds. This quickly becomes infeasible when there are many intersectional groups and impossible if C is uncountable. Moreover, in most practical settings, Q will very likely not have a simple closed form analytical expression.
In practice, i.i.d. samples drawn for Q may be available. For instance, the retrieval dataset DR itself may be drawn from the target population for which we aim to preserve proportional representation in retrieved items. Alternatively, we may have access to a dataset that was carefully curated to be representative of a diverse population. Examples include the FairFace dataset [39], which was designed to be balanced across race, gender, and age groups, and the AVFS dataset [65]. More generally, we refer to datasets with samples drawn from the target population Q as a curated dataset.
Definition 2 (Curated Dataset). Let Q be probability distribution over dRd x G tailored to account for diversity and representation of stakeholders who query the retrieval dataset. The curated dataset with m samples drawn the distribution Q is denoted as De e {æf,... {.. We denote the MPR of set of retrieved items R relative to the empirical distribution over De MPR(C,R, Rc).
Constructing a proper Dc is critical to properly measuring bias and preventing downstream harms, and the nature of De is context-dependent and may vary based on the specific application and desired representation goals. We reiterate that if the curated dataset is biased, then these biases will be propagated to downstream usages of MPR. For these reasons, we recommend that curated datasets
5

---

used for MPR measurements be developed and verified through participatory design approaches [66, 67] in collaboration with diverse stakeholders. By involving stakeholders defining representation goals, we can help ensure that the proportional representation in information retrieval systems measured by MPR aligns with the values and needs of the user base these systems serve.
Finally, we note that we can also condition the curated dataset on a given query. Specifically, for query q. we can retrieve relevant samples from both the curated dataset De and the retrieval dataset DR. The samples retrieved from De can then serve as a "conditional" curated dataset, denoted as Dola which captures the desired representation target specific to the query q. This approach allows for a more granular and context-aware proportional representation.
In the next two sections, introduce theoretical guarantees and algorithms that are agnostic to the specific choice of 'Dc. In other words, our proposed methods for measuring and promoting MPR in retrieval are general and can be applied regardless of how the curated dataset is constructed. In our numerical experiments, presented in Section 5, we use FairFace [39] as the curated dataset.
3 Computing Multi-Group Proportional Representation
Computing MPR in Defnition requires approximating two quantities: the representation distribution Q and the supremum supzgc- We first establish generalization bounds for approximating Q using i.i.d. samples. We then show how to compute supeec for several classes of representation statistics
Error in approximation Q via a curated dataset. Proposition I, proved in Appendix C. bounds the deviation between the empirical MPR computed over the curated dataset De drawn i..d. from reference distribution Q and the true MPR measured over Q.
Proposition 1 (Generalization Gap of MPR). Let RR(1) = [or])== 1)==1be be a set of retrieved samples, Dc { m be a curated dataset comprised of m i.i.d. samples from a target representation distribution Q and 8 > 0. If {c: Rd x g + [-1,1]] with Rademacher complexity R.m. (C) then, with probability at least 1 - 8.
log (2/8) 8m
MMR(C, R,) MPR(C, R, Q)I (C) +
(2)
We can extend Proposition I to any set of bounded functions C (see, c.g., bounds on empirical MMD estimates in [60]). Note that the guarantee in (2) only holds for a single set of retrieved items R. in response query. Proposition provides bound on the size m of i..d. curated dataset Dc that ensures an c-accurate estimate of MPR for set of M queries.
Proposition 2 (Query Budget Guarantee). Consider any set of M queries == (qI,.., qm} } where M E N. Let VC(C) denote the VC-dimension of the class C with range in {-1, 1). For c 0, De consists of m ii.d. samples drawn from Q where m satisfies
m 32VC(C)
2og (2
+
22
26a
then, with probability at least 1 8. [MPR(C, R, De) MPR(C, R. Q)15 c.
The above results provide guidelines on the size of the curated dataset required to accurately estimate MPR relative to a true target representation distribution Q. If the class of representation statistics C is very complex (in the VC-dimension sense), then the size m of the curated dataset De must be proportionally large to represent Q accurately. Hence, the curation dataset should be designed having in mind (i) the number of diverse queries being asked and (ii) the complexity of the function class C. While Proposition provides a conservative bound, as generalization bounds are often not tight [68], these results nevertheless offer insight into the relationship between the complexity of C and the accuracy of MPR estimation.
In the remainder of the paper, we assume that MPR is computed against a fixed curated dataset De of size m. We consider four specific instantiations of the set of representation statisties C: (i) C is closed under scalar multiplication, i.e., if E C, then de E C for any À E R, (ii) C is set of functions taking values in 11 (iii) consists of linear funetions; and (iv) consists of functions in a Reproducing Kernel Hilbert Space (RKHS). Next, we show that for cases (i) and (ii MPR can be

---

computed using calls to an oracle that performs regression over C and, for linear functions (iii), MPR has a simple closed-form expression. Due its technical nature, we defer the calculation of MPR for functions in an RKHS to Appendix D.2.
Computing MPR via Mean Square Error (MSE) Minimization. When C' is closed under mul- tiplication or consists of binary functions with values -1, 1. MPR can be expressed as an MSE minimization. This enables us compute MPR by leveraging existing black-box oracles that perform regression under quadratic loss, such as regressors implemented in scikit-learn [69].
The key observation for expressing MPR a maximum correlation problem. Consider the (row-wise) concatenation of the retrieval dataset Dn and the curated dataset De, given by X - [ of.... Lm) where Z; is the i-th entry of X. For the remainder of this section, we consider a fixed set of retrieved items R. Let vector indicating items that are retrieved from R for a given query, i.e., a; = 1 + x E R. Under this notation, where retrieved items are indicated by the vector a, MPR can be reformulated
MSE minimization is that MPR can be formulated as
{0, 1)"h be
m m Σ
n-
MPR(C, Dc) = suu
cEC k Σ (,)(x
= sup CEC
Σ
c( (a
(4)
where ä E Rat has i-th entry given by a Lisn x for explicitly casting MPR-constrained retrieval as optimization problem.
1ipn 1. This reformulation will be useful
When C consists of binary functions range {11, MPR is equivalent to regression over of under quadratic loss, since
inf
(c(z;) - 0,)² = =n m ā sup
((1))a,
(5)
CEC
dEC
The absolute value in (4) can be recovered by regressing - instead of ā.
Most classes of regression functions in R are closed under scalar multiplication (e.g., multiplying the output of a decision tree regressor by a constant still yields decision tree regressor). However, in this case, it follows from (4) that MPR is unbounded. Even for bounded C, without proper normalization MPR can scale with dataset size, which is undesirable for a representational measure. We constrain C set of normalized functions for MPR to be bounded and independent of dataset size. This constraint also allows us to cast MPR as an MSE minimization over C. We formally state this result next, proven in Appendix C, which will be applied in Section 4 to develop cutting-plant plane-based algorithm for ensuring MPR in retrieval called MOPR.
Proposition 3. Let C' A fc C| Σ 11 c(x;)²²
mi } where C is closed under scalar multipli- m+t
cation. Let el x(x) = [c(x1),... el c(xu+m)) Then 0 < MPR(C', RR Dc) S 1, and for any
n+m
é' E arg inf dEC
Σ (c(a.) - n,)
(6)
v /mkk/mmh
let ē: X + IR be defined as č(x)
o* (x). Then, we have that
(X)ll
è E arg sup eEC'
Σ clx
Computing MPR for Bounded-Norm Linear Regression. Recall that each item in the retrieval or curated datasets is of the form x; gt), where is an embedding and gi are labels. When I; E 'R' (i.e., the labels have numerical values), we can consider C as a linear set of functions over retrieved items. In this case, MPR enjoys closed-form expression, as stated in the next proposition.
Proposition 4. Let items in the retrieval and curated datasets be vectors in R' for I < m m n and C- {a + wTr| w RR&} Moreover, let X [B(m+n)xl be the matrix formed by concatenating items in the retrieval and curated dataset D and Dc. respectively. For C' in Proposition 3, we have
mk
MPR(C R, Rc) V Vm++ ||
(8)
7

---

Algorithm MOPR (Multi-group Optimized Proportional Retrieval)
Input: Px. query q. number of iterations 7', number of items to retrieve k. MPR constraint p. (racle(a)
that computes solves (4) returns E that approximates sup.
1: C 0, s; = .
2: for iter {1.2, T') do
arg (0. a subject to Ei= a;c(ar]) =E= c(ef) S for e 4: supr_violation, c) Dracle(a)
3:
Solve (4)
if mpr_violation I p or iter = then
6: return R + {az DR correponndngg to largest entries of a.)
7: else
8: Č+ Cc
end if
10:
end for
where X UEVT the SVD of X and U, R(m+n)xl are the left singular vectors in U corresponding to the top-1 largest singular values.
Proposition can be directly adapted to linear functions defined only over embeddings or subset of features of retrieved items. The closed-form expression for MPR in (8) also allows MPR-constrained retrieval to be computed by a quadratic program, as discussed in Appendix D.I.
Promoting Multi-Group Proportional Representation in Retrieval Tasks
We develop an optimization framework for retrieving the i most similar items in a vector database given query q while satisfying target MPR threshold of p. We formulate the retrieval goal as maximizing the average similarity between a query and retrieved items, given by 8; k( q) (recall Section for notation), where s(æ]", q) is given by cosine similarity in our experiments. The problem of maximizing utility in retrieval while satisfying an MPR constraint (expressed as Eq. (4)) can be formulated as the integer program:
m Σ dxf
max a subject sup RE (0(0.))
and(x)))
S P,
Σ
cEC
When C is given by normalized linear functions as in Proposition 4, the integer constraints can be relaxed to a E [0, 1]" and the optimization can be approximated via standard quadratic solvers; see Appendix D.1.
Multi-Group Optimized Proportional Retrieval. We approximate (9) via the Multi-Group Op- timized Proportional Retrieval Algorithm (MOPR), described in Algorithm 1. MOPR is essentially a autting-plane method that aims find set of & items that maximize utility while approximately satisfying an MPR constraint of The algorithm iterates between (i) call to an oracle that computes MPR and returns function C that achieves the supremum in (4) and (ii) call linear program (LP) solver that approximates the top-k most similar items to a query subject to linear constraints on the violation measured by c. Each oracle call adds an additional constraint to the solver which, in turn, approximates the top-k items under an increasing set of constraints. The solution of the LP is rounded to satisfy the integer constraint a {0, 1)". our implementation, we assume that MPR can be computed via MSE minimization (cf. Section 3) in which case we consider the normalized class C'. The oracle call consists of running black-box quadratic loss minimization over C and normalizing.
Interestingly, we observe that, despite relaxing the integer constraints in each LP call, the solution to the relaxed problem is very sparse and (after rounding) approximates well the solution of the ideal integer program (9) for moderate values of p. However, the method can fail to accurately approximate the IP solution when is small. We present more detailed analysis of MOPR in Appendix D, which discusses potential convergence issues with the cutting plane method as well stopping conditions.
For analysis of functions in RKHS, Appendix D.2

---

Duary propoasree
Duery giaratnee
Queryy ployaseet
Simttrtt
1.0
Fracdion of Top-k Simlarlty
0.7
2.
8.5
0.5 0/6 8.5 3.0 2.5
0.90
D05 1.00
0.
0,85
0.50
1.0
Fradton of Topai MPR
Fraction Top-k MPR
Frecdio of Top-k
MOPR (Ours)
MMR
CLIP-Clip
DebiasCUP
Figure 1: Cosine similarity vs MPR for query "A photo of programmer" with k = 50 images retrieved. From left right: CelebA, UTKFaces, Occupations. Values normalized so MPR and simi similarity when retrieving the top-k items is the point (1,1). MOPR Pareto-dominates baselines and significantly closes the MPR gap.
5 Numerical Experiments
In this section, we show that MOPR is effective in promoting more proportional representation across intersectional groups while preserving similarity between retrieved items and a given query. Notably, MOPR Pareto-dominates competing benchmarks in terms of achieved MPR gap and utility.
Datasets. We conduct retrieval over three image datasets of faces: CelebA [38], which includes labels for gender, age, and various other attributes, UTKFace [40], which contains gender, age, and race attributes, and Occupations [2], which contains gender attributes. We compute MPR for equal representation by constructing a synthetic dataset De balanced over all attributes and for proportional representation using FairFace [39] the curated dataset Dc, since is carefully designed dataset of faces with subgroup attributes for race, gender, and age. In all cases, each dataset entry consists of an image (CLIP) embedding e; and set of labels gi-
Benchmarks. We compare our method with four baselines. DebiasCLIP [20] modifies text queries with prepended learned embedding for debiased retrieval but does not allow for tunable control of the petiseentttion-simiaatt trade-off, so only results in a single retrieval set over which we compute similarity and MPR. CLIP-Clipp [18] trims features from CLIP embeddings that have high "mutual information" with gender, allowing for control of how many features are clipped from the embedding. CLIP embeddings
mitigate bias by predicting gender attributes and subsampling from each gender equally. PBM also allows tuning the balanced manner from the retrieval dataset. Finally, the state-of-the for fair retrieval first constructs PATHS embeddings [27], which use a set of adjective-noum keywords capture a broad set of identity vectors in Aisionllanguag models, and then greedily samples using the MMR [45] algorithm to navigate the representation similarity tradeoff. However, the authors' method of computing PATHS embeddings is not public, so we used CLIP embeddings to replicate their algorithm.
PBM [29] post-processe
snteenttttioniimiaaaiiiii tradcoff'
by controlling the likelihood of sampling at random
We refer to this method as MMR. For detailed discussion of these algorithms and their approaches to representation, see Appendix
Experimental Setup. We consider three classes of representation statistics C: linear regression, decision trees, and MLPs (the last two are presented in Appendix G). In both cases, we compute MPR over C', i.e., C. normalized over the retrieval and curated datasets (see Prop. 3). We report results over 10 queries for occupations suggested by ChatGPT 3.5 (Appendix H) and an additional 45 occupations for the the Occupations dataset. To accelerate retrieval, we query each of our retrieval datasets for the top 10k items according to the prompt "A photo of a {query}" in terms of raw similarity using FAISS [70]. We similarly retrieve the top 10k items from FairFace the query- muery-conditioned curated dataset De. One reason we first filter for the top 10k items is the runtime of MMR, which is greedy algorithm that traverses the full dataset for each retrieval & (even for 10k entries and & 50 retrieved items, MMR takes hours to run for 10 queries).
In order to evaluate representation over interpretable population groups, we consider that represen- tation statistics C are computed only over labels g: given in FairFace. These labels are not present in all retrieval datasets. Thus, for CelebA and Occupations, we train linear probes on FairFace's a CLIP embeddings to predict their race and age attributes, and when using FTCea we map from FairFace's 's race labels to UTKFaaeess ' race labels by mapping Southeast Asian and East Asian

---

Table 1: Retrieval averaged 10 queries with 50 retrievals on UTKFaace dataset [40] for MOPR, Top-k, and MMR [27]. Entries indicate average percentage representation in retrieved items. MDPR able to balance representation across classes, whereas Top-k and MMR miss intersectional groups (highlighted in red).
White
Black
Asian
Indian
Others
Sum
Male
21.2 1 11.84
13.2 1: 7.70
10.8 1: 7.54
21.2 = 20.70
1.4 1: 1.56
67.8 1. 23.72
Top-k
Female
17.2 + 21.04
6.6 + 6.14
4.0 + 2.82
2.8 - 2.56
1.6 1.50
32.2 23.72
Sum
38.4 + 17.18
19,8 = 12.56
14.8 + 7,38
24 19,38
3.0 - 2.04
Male
28.8 1 8,96
1.50
10.2 1 4.04
10.8 1 2.40
3.8 1.06
64.6
7.74
MMR
Female
16.2 9.06
7.6 3.66
5.0 3.00
4.0 = 1.26
2.6 1.56
35.4
7.74
Sum
45.0
7.76
18.6 5.38
15.2 + 5.82
14.8 + 3.12
1.96
Male
3.74
10.2 2.90
2.50
11.8 = 2.44
3.70
50 =
MOPR
(Ours)
Female
12.2
9.8 - 2.90
7.0 1: 2.56
8.2 L: 2.44
12.8 3.700
50
Sum
20 30:00
20 -
20 1
20 = 0
20 +
to Asian and Middle Eastern and Latino_ Latino_Hispanic to Other. While the fair ML community should engage in broader discussions addressing the ethics of predicting sensitive attributes from CLIP embeddings [71] (especially given that CLIP itself has been found to be biased) and the issues surrounding the grouping and re-grouping of diverse racial identities, acknowledge that these larger-scale issues that our work does not presume to address.
We retrieve k = 50 items for each of the above queries. For a given function class and query, we compute the baseline MPR and average cosine similarity given by the top 50 most similar items. Then, we conduct parameter sweep over p starting from this max-MPR value, inputting each value to MOPR in Algorithm 1. We normalize our results such that the Top-k MPR and similarity are the point (1,1) each graph, and each point measures the fraction of Top-k MPR and similarity.
Results. In Fig. we report results for proportional representation for the query "A photo of programmer" with respect to FairFace for linear regression models, with additional results for other queries, as well as decision trees and MLPs in Appendix G (Figs. 8-1.). We observe that MOPR Pareto-dominates benchmark methods, and is able to preserve similarity while reaching lower levels MPR. Methods based on directly modifying embeddings or queries for a single group attribute such as CLIP-Clip and DebiasCLIP only partially reduce MPR at high utility cost. This is because these methods do not modify the retrieval algorithm but use an unbiased embedding and hope by chance that the retrieved items will be representational. The most competitive method to ours is the retrieval algorithm MMR, which is our attempt to replicate PATHS. Though MMR is competitive ours for large MPR, it fails to achieve small values of MPR relative to MOPR. It is also notable that MOPR can drive MPR to near zero for UTKFaae, yet gaps remain in CelebA and Occupations, indicating this gap may be caused by the use of probes to estimate group attribute labels.
In Table 1, we construct a synthetic curation set with an equal number of each group attribute. This allows to evaluate the performance of MOPR in achieving equal representation. We conduct similar hyperparameter sweep as above, and take the retrieval set with the minimum MPR averaged over all 10 queries to fairly compare the best possible representation of each method. 2 Our results demonstrate that MOPR can exactly achieve our equal representation goals when provided with an squally-balancee curation dataset, whereas prior baselines (see DebiasCLIP, CLIP-Clip, and PBM in Appendix Table 5) underrepresent several intersectional groups
Concluding Remarks
In this work, we introduced novel retrieval metric called Multi-group Proportional Representation (MPR) and developed algorithms to ensure MPR in retrieval tasks. By measuring deviations in a set of representation statistics, MPR provides scalable approach to quantifying and enforcing proportional representation for complex, intersectional groups We analyzed the generalization properties and realizable regimes of MPR and, through experiments in image retrieval, demonstrated its favorable utility- fairmes trade-off compared to existing fair retrieval algorithms.
Aggregate results should be handled with care. As each conditoond retrieval setting results in a different distribution, average-case performance does not preclude the existence of query where baseline methods achieve superior results. See Limitations (Appendix B) for further discussion.
10

---

7 Acknowledgements
The authors would like to thank the discussions with Filipe Goulart Cabral. This material based upon work supported by the National Science Foundation under awards MAREER-1845833 CIF-1900750, CIF-2231707, and CIF-2312667, FAI-2040880, and also by the National Science Foundation Graduate Research Fellowship under Grant No. DGE-2140744 The views expressed here are those of the authors and do not reflect the official policy or position the funding agencies.
References
[1] Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and machine learning: Limita- tions and opportunities. MIT Press, 2023.
[2] Matthew Kay, Cynthia Matuszek, and Sean A Munson. Unequal representation and gender stereotypes in image search results for occupations. In Proceedings of the 33rd annual acm conference on human factors in computing systems, pages 381 3819-3828, 2015.
[3] Kate Crawford. The trouble with bias, 2017. Accessed May 1, 2024. https: pttts::/wwwx http:///wwww...uuuu youtube. com/wat htn/watch?v=fMym BBWggk_
[4] Sarah Myers West, Meredith Whittaker, and Kate Crawford. Discriminating systems. Al Now, pages 1-33, 2019.
[5] Solon Barocas, Kate Crawford, Aaron Shapiro, and Hanna Wallach. The problem with bias: Allocative versus representational harms in machine learning. In 9th Annual conference of the special interest group for computing, information and society, page 1. Philadelphia, PA, USA, 2017.
[6] Sanjana Gautam, Pranav Narayanan Venkit, and Sourojit Ghosh. From melting pots to misrepresentations: Exploring harms in generative ai. arXiv preprint arXiv:2403. 10776, 2024.
[7] Harini Suresh and John Guttag. A framework for understanding sources of harm throughout the machine learning life cycle. Proceedings of the 1st ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization, pages 1-9, 2021.
[8] Jared Katzman, Angelina Wang, Morgan Scheuerman, Su Lin Blodgett, Kristen Laird, Hanna Wallach, and Solon Barocas. Taxonomizing and measuring representational harms: look at image tagging. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 14277-14285, 2023.
[9] Shreya Shankar, Yoni Halpem, Eric Breck, James Atwood, Jimbo Wilson, and D) Sculley. No classification without representation: Assessing geodiversity issues in open data sets for the developing world. arXiv preprint 1rXiv:171..08556 2017.
[10] Sasha Luccioni, Christopher Akiki, Margaret Mitchell, and Yacine Jernite. Stable bias: Evaluating societal representations in diffusion models. Advances in Neural Information Processing Systems, 36, 2024.
[11] Federico Bianchi, Pratyusha Kalluri, Esin Durmus, Faisal Ladhak, Myra Cheng, Debora Nozza, Tatsunori Hashimoto, Dan Jurafsky, James Zou, and Aylin Caliskan. Easily accessible text-to-image generation amplifies demographic stereotypes at large scale. In Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency, pages 1493-1504, 2023.
[12] Alexander Lin, Lucas Monteiro Paes, Sree Harsha Tanneru, Suraj Srinivas, and Himabindu Lakkaraju. Word-level explanations for analyzing bias eex-tto-mmage models. arXiv preprint urXiv:2306.05515 2023.
[13] Latanya Sweeney. Discrimination in online ad delivery. Communications of the ACM, 56(5): 44-54. 2013.
[14] Danaë Metaxa, Michelle A Gan, Su Goh, Jeff Hancock, and James A Landay. An image of society: Gender and racial representation and impact in image search results for occupations. Proceedings of the ACM on Human- Computer Interaction. S(CSCWI):1-2) 2021.
[15] Yunhe Feng and Chirag Shah. Has CEO Gender Bias Really Been Fixed? Adversarial Attacking and Improving Gender Fairness in Image Search In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 11882-11890 2022.
11

---

[16] Jahna Otterbacher, Jo Bates, and Paul Clough. Competent men and warm women: Gender stereotypes and backlash in image search results. In Proceedings of the 2017 chi conference human factors in computing systems, pages 6620-6631, 2017. 2017.
[17] Roberto Ulloa, Ana Carolina Richter, Mykola Makhortykh, Aleksandra Urman, and Celina Syl- wia Kacperski. Representativeness and face-ism: Gender bias image search. new media & society, 26(6):3541-3561 2024.
[18] Jialu Wang. Yang Liu, and Xin Wang. Are gender-neutral queries really gender-neutral? mitigating gender bias in image search. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages
2021.
[19] Junyang Wang, Yi Zhang, and Jitao Sang. Fairclip: Social bias elimination based on attribute prototype learning and representation neutralization. arXiv preprint arXiv:2210.145622 2022.
[20] Hugo Berg, Siobhan Hall, Yash Bhalgat, Hannah Kirk, Aleksandar Shtedritski, and Max Bain. A prompt array keeps the bias away: Debiasing vision-language models with adversarial learn- ing. In Proceedings of the 2nd Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics and the 12th International Joint Conference Natural Language Processing (Volume 1: Long Pupers), pages 806-822, 2022.
[21] Jae Myung Kim, A. Sophia Koepke, Cordelia Schmid, and Zeynep Akata. Exposing and mitigating spurious correlations for cross-modal retrieval. 2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pages 2585-2595, 2023.
[22] Mohsen Abbasi, Sorelle A Friedler, Carlos Scheidegger, and Suresh Venkatasubramanian. Fairness in representation: quantifying stereotyping as a representational harm. In Proceedings of the 2019 SIAM International Conference on Data Mining, pages 801-809. SIAM, 2019.
[23] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. International conference on machine learning. pages 8748-8763. PMLR, 2021.
[24] Siobhan Mackenzie Hall, Fernanda Gonçalves Abrantes, Hanwen Zhu, Grace Sodunke, Alek- sandar Shtedritski, and Hannah Rose Kirk. Visogender: A dataset for benchmarking gender bias in image-text pronoun resolution. Advances in Neural Information Processing Systems, 36, 2024.
[25] Robert Wolfe and Aylin Caliskan. Markedness visual semantic ai. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 1269-1279, 2022.
[26] Tolga Bolukbasi, Kai-Wai Chang, James Y Zou, Venkatesh Saligrama, and Adam T Kalai. Man is to computer programmer as woman is to homemaker? debiasing word embeddings. Advances in neural information processing systems, 29, 2016.
[27] Hansa Srinivasan, Candice Schumann, Aradhana Sinha, David Madras, Gholahan Oluwafemi Olanubi, Alex Beutel, Susanna Ricco, and Jilin Chen. Generalized people diversity: Learn- ing a human perception-alignee diversity representation for people images. arXiv preprint arXiv:2401.. 143222 2024.
[28] Anay Mehrotra and Elisa Celis. Mitigating bias in set selection with noisy protected attributes. Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, 2020.
[29] Fanjie Kong, Shuai Yuan, Weituo Hao, and Ricardo Henao. Mitigating test-time bias for fair image retrieval. Advances in Neurul Information Processing Systems, 36, 2024.
[30] Elisa Celis, Vijay Keswani, Damian Straszak, Amit Deshpande, Tarun Kathuria, and Nisheeth Vishnoi. Fair and diverse dpp-based data summarization. In International conference machine learning, pages 716-725. PMLR, 2018
[31] L Elisa Celis and Vijay Keswani. Implicit diversity in image summarization. Proceedings of the ACM on Humun-Computer Interaction, 4CCSCW2) 2020.
[32] Kimberle Crenshaw. Demarginalizing the intersection of race and sex: A black feminist critique of antidiscrimination doctrine, feminist theory and antiracist politics. In University of Chicago Legal Forum, volume 1989, page 8, 1989.
12

---

[33] Kimberlé Williams Crenshaw. Mapping the margins: Intersectionality. identity polities, and violence against women of color. In The public nature of private violence, pages 93-118. Routledge, 2013.
[34] Sumi Cho, Kimberlé Williams Crenshaw, and Leslie McCall. Toward a field of intersectionality studies: Theory, applications, and praxis. Signs: Journal of women in culture and society, 38 (4):785-810, 2013.
[35] Joy Buolamwini and Timnit Gebru. Gender shades: Intersectional accuracy disparities in commercial gender classification. In Conference on fairness, accountability and transparency, pages 77-91. PMLR, 2018.
[36] Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing fairness gerryman- dering: Auditing and learning for subgroup faimess. In International conference on machine learning, pages 25722. PMLR, 2018.
[37] Jérôme Lang and Piotr Skowron. Multi-attribute proportional representation. Artificial Intelligence, 263:74-106, 2018.
[38] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
[39] Kimmo Karkkainen and Jungseock Joo. Fairface: Face attribute dataset for balanced race, gender, and age for bias measurement and mitigation. In Proceedings of the IEEE/CVF winter conference on applications of computer vision, pages 1548-1558, 2021.
[40] Zhifei Zhang, Yang Song, and Hairong Qi. Age progressiion/regression by conditional adver- sarial autoencoder. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, 2017.
[41] Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representa- tions. In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 325-333, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR.
[42] Harrison Edwards and Amos Storkey. Censoring representations with adversary. In 4th International Conference on Learning Representations, pages 1 1-14, 2016.
[43] David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3384-3393, PMLR, 10-15 Jul 2018.
[44] Elliot Creager, David Madras, Jörn- Jacobsen, Marissa Weis, Kevin Swersky, Toniann Pitassi, and Richard Zemel. Flexibly fair representation learning by disentanglement. In International conference machine learning, pages 1436-1445. PMLR, 2019.
[45] Jaime Carbonell and Jade Goldstein. The use of mmr, diversity- based reranking for reordering documents and producing summaries. In Proceedings of the 21 annual international ACM SIGIR conference on Research and development in information retrieval, pages 335-336, 1998.
[46] Barry Smyth and Paul McClave, Similarity vs. diversity. In International conference on case-based reasoning, pages 347-361. Springer, 2001.
[47] Evaggelia Pitoura, Kostas Stefanidis, and Georgia Koutrika. Fairness in rankings and recom- mendations: an overview. The VLDB Journal, pages 1-28, 2022.
[48] Ursula Hébert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Calibration for the (computationaally-ddeent iddetiiiiaiit)) masses. In International Conference on
Muchine Learning, pages 1939-1948. PMLR, 2018
[49] Michael P Kim, Amirata Ghorbani, and James Zou. Multiaccuracy: Black-box post-processing for fairness in classification. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society. pages 247-254, 2019.
[50] Michael P Kim, Christoph Kern, Shafi Goldwasser, Frauke Kreuter, and Omer Reingold. Universal adaptability: Target-independent inference that competes with propensity scoring. Proceedings of the National Academy of Sciences, 119(4)cc 2022.
13

---

[51] Eliran Shabat, Lee Cohen, and Yishay Mansour. Sample complexity of uniform convergence for multicalibration. Advances in Neural Information Processing Systems, 33:13331-133400 2020.
[52] Lucas Monteiro Paes, Ananda Theertha Suresh, Alex Beutel, Flavio Calmon, and Ahmad Beirami. Multi-group fairness evaluation via conditional value-at-risk testing. arXiv preprint arXiv:2312.03800 2023.
[53] Parikshit Gopalan, Lunjia Hu, and Guy N Rothblum. On computationally efficient multi-class calibration. arXiv preprint arXiv:2402.0758 07821, 2024.
[54] Parikshit Gopalan, Michael Kim, Mihir A Singhal, and Shengjia Zhao. Low-degree multi-
calibration. In Conference Learning Theory, pages 3193-3234. PMLR, 2022.
[55] Zhun Deng, Cynthia Dwork, and Linjun Zhang. Happymap: A generalized multicalibration method. 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, page 41. Schloss Dagstubl-Leeibniz-Zeetnnm fur Informatik GmbH, Dagstuhl Publishing, 2023.
[56] Bailey Flanigan, Paul Gölz, Anupam Gupta, Brett Hennig, and Ariel D Procaccia. Fair algorithms for selecting citizens' assemblies. Nature, 596(7873):548-552, 2021.
[57] Edith Elkind, Piotr Faliszewski, Piotr Skowron, and Arkadii Slinko. Properties of multiwinner voting rules. Social Choice and Welfare, 48:599 632, 2017.
[58] Virginie Do, Jamal Atif, Jérôme Lang. and Nicolas Usunier. Online selection of diverse committees. arXiv preprint 0rXiv:210S.09295. 2021.
[59] Piotr Skowron, Piotr Faliszewski, and Jérôme Lang. Finding a collective set of items: From proportional multirepresentation to group recommendation. Artificial Intelligence, 241:191- 216, 2016.
[60] Arthur Gretton, Karsten M Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012.
[61] Ajil Jalal, Sushrut Karmalkar, Jessica Hoffmann, Alex Dimakis, and Eric Price. Fairness for image generation with uncertain sensitive attributes. In International Conference on Machine Learning, pages 4721-4732. PMLR, 2021.
[62] Karsten M Borgwardt, Arthur Gretton, Malte Rasch, Hans-Peter Kriegel, Bernhard Schölkopf, and Alex J Smola. Integrating structured biological data by kernel maximum mean discrepancy. Bioinformatics, 22( 22114):49--577, 2006.
[63] Alfred Müller. Integral probability metrics and their generating classes of functions. Advances in applied probability, 29(2):429-443, 1997.
[64] Bharath K Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, and Gert RG Lanckriet. On the empirical estimation of integral probability metrics. Electronic Journal of Statistics, 6:1550-1599, 2012.
[65] Jerone Theodore Alexander Andrews, Przemyslaw Joniak, and Alice Xiang. A view from somewhere: Human-centric face representations. In The Eleventh International Conference on Learning Representations, 2022.
[66] Fernando Delgado, Stephen Yang. Michael Madaio, and Qian Yang. Stakeholder participation in ai: Beyond" add diverse stakeholders and stir". arXiv preprint arXiv:2111.01 2021.
[67] Douglas Zytko, Pamela J. Wisniewski, Shion Guha, Eric PS Baumer, and Min Kyung Lec. Participatory design of ai systems: opportunities and challenges across diverse users, relation- ships, and application domains. In CHI Conference on Human Factors in Computing Systems Extended Abstracts, pages 1-4, 2022.
[68] Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantas- tic generalization measures and where to find them. In International Conference on Learning Representations, 2019.
[69] F. Pedregosa, Varoquaux, A. Gramfort, Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and F. Duchesnay. Seikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
14

---

[70] Jeff Johnson. Matthijs Douze, and Hervé Jégou. Billion-scae similarity search with GPUs. IEEE Transactions on Big Data, 7(3):535-547. 2019.
[71] Foad Hamidi, Morgan Klaus Scheuerman, and Stacy M Branham. Gender recognition or gender reductionism? the social implications of embedded gender recognition systems. In Proceedings of the 2018 chi conference on human hamanfactors computing systems, pages 1-13, 2018.
[72] Peter I.. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 2002.
[73] Martin Wainwright. High-ddmensional statistics: A non-asympiotic viewpoint, volume 48. Cambridge university press, 2019.
[74] Jun Yang, Shengyang Sun, and Daniel M Roy. Fast-rate pac-bayes generalization bounds via shifted rademacher processes. Advances in Neural Information Processing Systems, 32, 2019.
[75] Yuheng Bu, Shaofeng Zou, and Venugopal V Veeravalli. Tightening mutual information- bounds on generalization error. IEEE Journal on Selected Areas in Information Theory, 1(1): 121-130, 2020.
[76] Amir Asadi, Emmanuel Abbe, and Sergio Verdú. Chaining mutual information and tightening generalization bounds. Advances in Neural Information Processing Systems, 31, 2018.
[77] Ron Amit, Baruch Epstein, Shay Moran, and Ron Meir. Integral probability metrics pac-bayes bounds. Advances Neural Information Processing Systems, 35:3123-3136 2022.
[78] James E Kelley, Jr. The cutting-plane method for solving convex programs. Journal of the society for Industrial and Applied Mathematics, 8(4):703-712, 1960.
[79] Elliot Ward Cheney and Allen A Goldstein. Newton's method for convex programming and tchebycheff approximation. Numerische Mathematik, 1(1):253-268, 1959.
[80] B Curtis Eaves and WI Zangwill. Generalized cutting plane algorithms. SIAM Journal on Control, 94)):529-542 1971.
[81] Dimitri Bertsekas. Convex optimization algorithms. Athena Scientific, 2015.
[82] Donald M Topkis. Cutting-plane methods without nested constraint sets. Operations Research, 18(3):404-433, 1970.
[83] Jean-Louis Goffin and Jean- Phi-PPilippe Vial. Convex nondifferentiable optimization: A survey focused on the analytic center cutting plane method. Optimization methods and software, 17 (5):805-867, 2002.
[84] Laurence A Wolsey and George L Nemhauser. Integer and combinatorial optimization. John Wiley & Sons, 2014.
[85] Bernhard Schölkopf and Alexander Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.
[86] T Hofmann, Schölkopf, and AJ Smola. Kernel methods in machine learning. The Annals of Statistics,
2008
[87] Weihao Gao, Sreeram Kannan, Sewoong Oh, and Pramod Viswanath. Estimating mutual information for discrete-continuous mixtures, 2018
[88] Duncan Black. Theory Committees and Elections. Cambridge University Press, 1958.
[89] John Chamberlin and Paul N Courant, Representative deliberations and representative decisions: Proportional representation and the borda rule. American Political Science Review, 77137778 1983.
[90] Burt Monroe, Fully proportional representation. American Political Science Review, 89(4): 925-940, 1995.
[91] Friedrich Pukelsheim. Proportional representation. Springer, 2017.
[92] Jonathan K Hodge and Richard E Klima. The muthematics of voting and elections: a hands-on approuch, volume 30. American Mathematical Soc., 2018.
[93] Thomas Hare. Treatise on the Election of Representatives, Parliamentary and Municipal. Longman, Green, Longman, & Roberts, 1861.
15

---

[94] Michel Balinski. Fair majority voting (or how to eliminate genymandering). The American Mathematical Monthly, 115(2):7--13, 2008.
[95] Ariel D Procaccia, Jeffrey S Rosenschein, and Aviv Zohar. On the complexity of achieving proportional representation. Social Choice and Welfare, 30(3):353-362, 2008.
[96] Nadja Betzler, Arkadii Slinko, and Johannes Uhlmann. On the computation of fully propor- tional representation. Journal Artificial Intelligence Research, 47:475-519, 2013.
[97] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D Procaccia. Handbook of computational social choice. Cambridge University Press, 2016.
[98] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL https://www.
gurobi. com.
[99] Steven Diamond and Stephen Boyd. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
[100] Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. A rewriting system for convex optimization problems. Journal of Control and Decision, 5(1):42-60, 2018.
16

---

Supplementary material to the paper Multi-Group Preportional Representation in Retrieval
In this supplement to the paper, we begin in Section A and Section B by noting some ethical considerations and limitations for our work, respectively. Then, we present our proofs of Propositions 3, 2, and 4 in Appendix C. In Appendix D, we discuss the MOPR algorithm, its convergence aspects, and MOPR for linear functions and functions belonging to an RKHS. We also compare the linear relaxation to the integer program optimization problem in Equation 9 empirically and similarly compare the result of MOPR to directly solving the closed form linear program in the case of linear models. In Appendix E, we describe the baselines reported in this paper and provide further retrieval statistics. In particular, we describe the algorithms CLIP-clip Wang et al. [18]. CLIP-debias Berg et al. [20]. Post-Hoe Bias Mitigation ([29] and PATHS [27]. In F, we provide a brief discussion about proportional representation in political sciences, give a few historical comments about social choice theory, and discuss the contribution given by [37]. Then, Appendix G, we include an additional table of results for equal representation with the other baseline methods (Table 5). We also include plots for additional queries for the linear regression model (Figs. 8, 9, and 10) for as well as two additional models, 1) decision tree models in Figs. 11, 12, and 13 and for 2) multilayer perceptrons in Figs. 14, 15, and 16. We provide additional details on the experiment setting in Appendix H. Finally, we include some example sets of retrieved images for qualitative comparison.
A Ethics considerations
It is important consider the long-term societal impact of enforcing MPR in real-world retrieval systems to understand its potential benefits and risks. First, applying MPR, such as with MOPR in deployment settings, could result in "ethics-washing" -hhere a company claims their system is fair because they measured MPR when, in fact, there are still representational harms-or could provide users and developers with a false sense of fairness. Second, MPR is just one of many ways of analyzing representation, and as a statistical metric, it fails to consider aspects such as human perceptions of representation. There are legal and regulatory risks with overreliance on a single metric for fairness, especially if this metric is used to inform policy and decision-making mentioned previously, any biases present in the curation dataset will propagate to the results and downstream uses of MPR; furthermore, the choice of what dataset and what attributes to consider is an inherently social and political choice made by humans, subject to its own limitations and biases. Finally, the introduction of MPR in real-world retrieval systems could introduce new stereotypes or erase identities not conducted properly.
As
B Limitations
Our aggregate results (c.g.. Table 1) should be approached with caution, as each similaaryy curve is sampled from different distribution of data conditioned a query, limiting our ability to draw statistical conclusions. This does not preclude the existence of a query where a competing method may achieve an MPR-similarity trade-off point not achieved by MOPR. However, we note that MOPR is specifically optimized to promote MPR while preserving similarity, explaining its favorable performance. In all instances observed by the authors, MOPR Pareto dominates competing benchmarks and was the most successful method in achieving low values of MPR while maintaining high levels of similarity with given query. Second, while MPR is designed handle a large number of groups, the computational complexity of the proposed outting-plane algorithm in the case of a general function class C can be a concern for -igh-nimeniional feature spaces. Developing more efficient algorithms or approximation techniques could help address this issue. Finally, MPR is inherently limited by the curated dataset. If this dataset is biased against given group, this bias will be propagated by MOPR. The creation and selection of curated datasets must carefully account for stakeholder interest and target representation statisties. Additionally, we note that not every combination of intersectional identities (such as "white male" as opposed to "black female") may be considered intersectional from a sociological perspective, and furthermore, these datasets do not contain multiracial labels. We do not presume to address representational issues in MI datasets, and instead, our experiments aim to demonstrate the flexibility and scalability of the MPR metric in handling complex intersectional groups. We hope that MPR will only prove more useful as datasets become more representative.
17

---

C Proofs from Section 3
We start by proving Proposition from Section 3 which bounds the error in MPR estimates when Q is approximated via curated dataset De. We do so by using tools from standard Rademacher complexity results in statistical learning theory, e.g. [72]. See also [73, Chapter 4J. We restate the theorems here facilitate readability. We start with lemma about the difference of suprema.
Lemma 1. Let P and P' be two distributions over X and C fc: X - [0, 1]]. Then
sup Bp[c(X]] sup [x([c()]] & sup [Bp]((X]] - Ep <EC
(10)
<EC
AEC
Proof.
sup Ep [ppc(()]] - sup P [c(X)),
<EC
OEC
ssup (Bplc(X)] - Ep [c(]]] + Ep [c(x)]] - sup Ep [c(x)]
.EC
oEC
S sup (Erlc(X) - [x(((())) + sup Ep- [[(X]] sup E. (c(X),,
cEC
aEC
oEC
S sup (Er[c(X)] - [x()c(x))}
CEC
Proposition 1 (Generalization Gap of MPR). Let R(4) = (o]))= be set of retrieved samples, Dc = {af be a curated dataset comprised of m i.i.d. samples from a target representation distribution Q and O. CfC {c: : Rd x G - [11,1] with Rademacher complexity RRm (C)
then, with probability at least 1 8,
log (2/8)
MPR(C, R, Dc) MPR(C, R, Q)I S (C) +
(2)
8m
Proof. First, note that
MPR(C, Dc) - MPR(C, R, Q)
(11)
sup cEC
c(x)
c(xf)
sup aEC
c(x)) Eo(((X)
(12)
m
m
< sup
c(x))
Σ cxaF)
Σ dxx)) - [oic(X)
(13)
330
m i=1
c(x))) 1
sup
c(xF))
c(x;) 1B [[(())]]]
(14)
k
sup
c(xf)) - Exlc(X)]
(15)
cEC
Where (13) comes from Lemma and (15) comes from the triangular inequality.
Additionally, by switching MPR(C, R, Q) by supeec peating the previous argument, we conclude that:
1 k E c(x,) EEec(()) in (11) and re-
m
MPR(C, R, Dc) - sup REC
c(xx) - Eolo(X))
S sup cEC m i=1
Σ c(a Eel(X)) (16)
18

---

Therefore, from (16) we show
log (3t
Pr
MPR(C, R, Dc)
sup oEC
c(x;)) [xl((x)
2m +
(17)
2m
i=1
log (3)
< Pr
sup
c(a
Eolc(X)]
2 (C) +
(18)
oEC
2m
c(=i) 2
[c(x)
log (3) 8m
< Pr
sup oEC
BQQ
2 (C) +
6,
(19)
here (19) comes from the generalization bound using Rademacher complexity from [72] and the fact that c(w)
c1 }] hence the image of & is in an interval of size 1.
We now prove Proposition 2, which provides a bound on the size m of an i.i.d. curated dataset De that ensures an c-accurate estimate of MPR for of M queries.
Proposition 2 (Query Budget Guarantee). Consider any set of M queries Q = (qI.... qm) where
M E N. Let VC(C) denote the VC-dimension of the class C with range in (-1,1). 1). For 0, D consists of m ii.d. samples drawn from Q where m satisfies
m 32VC(C)
2 log (2M)
+
2
2ea
then, with probubility at least 1 - 8, MMR(C, R, Dc) MPR(C, R, Q){5
Proof. First, recall that the Rademacher complexity R.m (C) is upper bounded by the VC-dimension of C by the relation
2VC(C) log
VC(C)
Rum (C) S
(20)
where is Euler's number.
Denote the samples retrieved for a given query q by R(g) (1) From Proposition have that for all 8*
log (3: 8m
Pr MMR(C, R, Dc) MPR(C, R, R,Q)1 (m)(C)
S 8".
Therefore, using the previous equation if we take 8
5 and denote R(g) R we have that
log (
Pr
sup g
MPR(C, R, MPRIC, (C) +
8mm
log 8m
(2)
Σ Pr
MPR(C, R, Do) MMR((C, Q) 2 R.m (C) +
Q
SM
<
8*
=
(21)
M
Hence, have that, with probability at least 1 5 for all g Q
2M log
sup cEC
Σ (()) Eolc(X)] < MPR(C, R(g), + (C)(C) +
8
(22)
8m
19

---

2VC(C) log
cm VC(C)
log
(M
MPR(C, R(q),
m
8172
(23)
Where the inequality in (23) comes from the upper bound in (20).
32VC(() then Moreover, if m 2 x²
2VC(C) log
Voie
log( 2M
log
2M
and if
then
2
81z
Therefore, conclude that if m is such that
32VC(C)
2M log
(24)
22
2e
then
* of (q)) Eolc(X)]
sup cEC
I MPR((,, R(q), +ec
(25)
k
1=1
As described in Section 3, such bounds tend to be conservative and these bounds can be improved by doing sharper analysis with PAC-Bayesian [74] or mutual information bounds [75]. See also [76] and [77].
We now prove Proposition 3.
This proposition states that for specific function classes, computing MPR is equivalent to solving an MSE regression problem. This proposition allows us to efficiently estimate MPR with standard regression models from packages such scikit-learn [69].
Proposition Let C' & fc E C + c(x;)2 mk } where C is closed under scalar multipli-
cation. Let c(X) = [c(x1),... c(xn+m)]. Then 0 < MPR(C', R, Dc) S 1, and for any
c' E arg inf oEC
Σ (c(x;) a.)²
(6)
(m+k) (X)Il2
let ē: X + IR be defined as c(x)
c* (x). Then, we have that
è E arg sup egc'
Σ c(x;)a
Proof. We begin proving 0 < MPR(C,,R, Dc) < 1, As shorthand, let c(X)
=
[c(x1),.. m()+mm). The Cauchy-Sehie Schwarz inequality gives,
m++
clx; )ā,
S ||c(X)ll2|/111
(26)
where X E g(m+n)xl is the matrix formed by the row-wise concatenation of Dr and De and ä is the vector la,.... Am C' gives us a constraint on the norm of c(X), and we can compute à given there are is terms with value 1/k, m terms with value 1 1/m, and n i terms with value 0. Also note mak (1) + 1
that m+tk
د 1.
1
c(x
0a
<
(27)
k
k
Next, we prove the second statement. Consider the minimizer of the MSE problem,
arg inf (c(x;) az)² aEC
(28)
20

---

As C is closed under scalar multiplication, we can equivalently write this a two-part optimization problem
arg inf
inf
Σ
(Ac((:)) - -,:)²
(29)
dEC
;=1
where the inner optimization is quadratic and yields solution
D c(x:)ā;
(30)
|c((x]
as ||((() 122 oo. Plugging this back into Equation (29), the MSE problem becomes
1 o(x, )ā:
arg inf oEC
c(xx)) - a.)²
|c(x)]
(c(X), a)²
(c()),
arg inf
[|((X]] c(x;;)
+
|c[ x1
cEC
1=1
(c(X), 2)2 [[c(X]]
(c( a) [[(()]
arg inf eEC
||(())]1
(c(X),
3 +
Σ
(c(X), a)² [|c(X)]
n+m
arg inf eEC
Σ
As aj does not depend on c, this optimization equivalent to
()) = arg sup eEc
Ke(X), a) ||c(X)
arg sup cEC
||c(X|11
Note that the supremum can be multiplied by a constant. Then we can multiply by some A > 0 and get
(c(X). a.1?
argsup egc
argsup
(c(()),))
(31)
||c(X)]1
CEC [[)i
In other words, for > 0 and
[c((X), a>P
6¹ E arg sup
||
GEC
and letting é: - IR be defined as ē(x)
V
C* (x), we have that
[X]22
n++m
é argsup CEC, [=(X)]]==vā
a)(
sup eEC,
c(2
arg sup oEC, [|<())]==vá
Σ
claa)a
(32)
|<(x)]]==vā
Letting mk m we can conclude that solving an MSE regression problem equivalent to finding the representation statistic for MPR.
Now, we establish Proposition 4, restated below for convenience. It says that MPR enjoys a closed- form expression whenever the class given by linear functions. This proposition allows us to simplify MOPR since, in this case, the optimization problem can be cast as a quadratic program.
Proposition Let items the retrieval and curated datasets be vectors in Rdl for < m + a and C= (z + wTr| w IR*} Moreover, let X E ())++))xl be the matrix formed by concatenating items in the retrieval and curated dataset DR and Dc. respectively. For C' in Proposition 3, we have
mk
MPR(C', R, = - Wmnk ||Ta||
(8)
where X = UEVT is the SVD of X and U, E [((+n)xl are the left singular vectors in U corresponding to the top-l largest singular values.
For analysis of functions in RKHS, Appendix D.2
21

---

The closed-form expression for MPR in (8) allows MPR-constraing retrieval to be approximated by a quadratic program, whose proof can be found in Appendix D. Moreover, the above proposition can be directly adapted to linear functions defined only for embeddings or a subset of features of retrieved items.
Proof. Since we are considering the class C' - {c E xz + w w E ]. the computation of the Multi-Group Proportional Representation metric
1m c(a))² m+t)) where
n++
MPR(C,, R, Dc) = arg sup cEC
Σ
c(2 )a:
(33)
boils down to the following optimization problem
nL+
max CEC
(34)
t=1
subject to
m++
Σ
mk
+ k
which can be written as
max WERn+
a Xw
(35)
mk
subject to |
m + k'
where X IR (=) the matrix formed by concatenating items in the retrieval and curated dataset Dn and Do, respectively. Let X UEVT be the SVD of X and U, R(m+n)xl are the left singular vectors in U corresponding to the top-1 largest singular values. Then, the problem becomes
max WER
a WUEV
(36)
mk
subject to |EV
m +
Now, by change of variables ΣV and U
max mmm
z w
(37)
mk + h
subject to W
m
ΣVTW = W.
We can use the method of I Lagrange multipliers. Let us define the Lagrangian function:
mk -
X = zT
|
k 10 (EVT - w)
(38)
2
To find the optimal solution, set the partial derivatives of the Lagrangian with respect to w, w, A, and μ to zero:
0L
Aw
11 0,
(39)
Ow
aL
VVEf
0,
(40)
Ow
aL
mk
|
= 0,
(41)
m
+ k
ØT.
ΣVT
w = 0.
(42)
0μ
22

---

From (42), we have VΣ = 0. Assuming V and E are full rank, this implies fe = 0. Substituting
this into (39), we get:
2 Aw
2.
(43)
Using (43) and the constraint
we can solve for
m
mk + kc
m + h mk
1
A= x=
(44)
X
Since we are maximizing zd w, we choose the positive value A. Thus, the optimal w is:
mkk
m++
(45)
|2
Finally, using (45), we can find the optimal w:
mk m+t
mi
EVTw
W EVT
EVT)-12
m+th
(EVT) (46)
|
The optimal then obtained by solving the linear system EVTw" w Finally, plugging the solution back in to our objective and canceling terms, we arrive at our solution. Note that we can replace U with U, in our original SVD as U E R (m++)xx so we can truncate the vectors in the null space of U.
a UEVVT
max WE WER
UV
m++k
(VV
|z|12
mb m
a² U,UJä
mk
UTall2
+ k
D The Multi-group Optimized Retrieval Algorithm
In this section, we discuss the convergence of MOPR, the Multi-group Optimized Proportional Retrieval algorithm. As described in Section 4, the MOPR is essentially cutting plane method (also known as the Kelley-Cheney- -ha---hhhee--Gllteiinn Golddseiin method [78, 79I) applied to the linear function a s; see also [80].
The algorithm begins by identifying the k-most similar items to given query in Di- Then, an MSE-mininizing oracle is called and returns the statistic (or group-denoting function) c with most disproportionate representation for the set of retrieved items. The function is then added as [0, 11"h maximizing average similarity in (9) 1 Σne c(x;) S p. where integer constraints m
constraint to linear program that outputs vector subject single constraint 1 Σi= = 10===<aa_aaa l"a,c(=))
x
are relaxed. The optimal is rounded so only the largest & entries are marked as 1, corresponding new set of retrieved items. The process repeats with increasing number of constraints the
linear program and halts when the oracle does not return function that violates the target MPR
constraint p. mathematical terms, we start by solving the problem
max aTs (0(1.))
(47)
23

---

subject to
a. k.
Note that the solution to this problem is given by the vector that finds the kth largest entries of ic., it identifies the k-most similar items to given query in DR. Then, Proposition provides a way to generate cuts given the vector ag R found solution of the previous iteration. These cuts are given by the function e E with the most disproportionate representation for the set of retrieved items.
At each iteration, we test if the MPR constraint, less or equal to p. satisfied. not, this gives us a new inequality to be incorporated into the linear problem (D) that outputs vector [0, 1 maximizing average similarity as in (9) subject to a single constraint | Ei= (c(();)) 1 En i= c(x;) S
where integer constraints are relaxed. Therefore, the algorithm consists of iteratively adding new constraint (cut) of the form
1 c(2f)
((a)
sup cEC
a;c(
(48)
and solving the problem again until all the inequalities fulfilled, i.e., until the oracle does not return a function that violates the target MPR constraint At this point, the algorithm halts. remains to be shown that the description above indeed corresponds to a traditional cutting plane method for convex functions, For the subsequent discussion, we will denote the term inside the supremum in (48) by g(a c), i.e.,
1 T
1
g(a. c)
Σ
c(as), for c
(49)
The next proposition links the oracle via MSE, described in Proposition 3, with the subdifferential of the function G(a))
Proposition 5. Let C be in infinite set and let G(a) = supeeclg(a, c) be the convex restric- tion of the optimization problem (9) given by the supremum, i.e., G(a) S P. R". If c² E arg supeeclg(a",d ,c)] and e denote the function c* evaluated at the points II,...,In. i.e. c (x1).. C. (Im),, then g" == sign(g(a" c²)) .c @G(a"), i.e, g a subgradient of at point a"
Proof. We start by noting that G(a) convex function since is a supremum of composition of an affine function with the absolute value. Also, note that G(a) can be written as G(a) supeec (g c)}= supeecleTa + bel. where b C R. We need to prove that
G(a*) + gT (a - a²) S G(a), Va E R.
(50)
In fact, starting from the left-hand side leads to
gg(a"."' c²") )|+ (ggnng((",,,, c')) (""""""""""")""" a')
cTa + b
lcca belt
cT(a a")
ccTa bel
cTa + b
= ca aa- - bal+
- cTa" - -b + cTaa b.-
cTa bel
ccT + bal
|cTa + bel
+ ,ign(g(a",c"))(c (c)) b
IcT+tb
< cTa a + b. G(a), Va E R
This shows that (c+(21). ((, is subgradient of G(a).

---

The cutting plane strategy described in Algorithm 1 addresses the constraints of the form G(a) - that are not fulfilled. Since (50) holds, the algorithm adds linear approximations (or cutting planes) of the form
G(a*) ga (a-a")) P
(51)
to the problem at each iteration until the solution satisfies all the inequalities. This reformulation demonstrates that the MOPR algorithm minimizing a linear function over the polyhedron P = {a: E [0, 10 Σi= = kj. If, at a certain iteration, the algorithm finds an iterate that satisfies all the inequalities, it terminates since the lower bound provided by the cutting plane method matches the upper bound. In the case where the algorithm continues adding constraints, the accumulation point (guaranteed exist due the compactness of the set P) will converge to an optimal solution, as proven in [81, Proposition 4.1.2) or the main theorem in [78, Section 2].
be viewed
traditional cutting plane method for
However, it is important to note that even when the algorithm terminates in finite number of steps, the cutting plane method often requires substantial number of iterations converge and may exhibit numerical instabilities. Addressing these instabilities or exploring techniques to discard certain cuts for improved convergence, such as partial cutting plane methods, is beyond the scope this paper. For further information on these topics, refer to [82, 83] and the references therein.
The integer program may not be scalable its convex relaxation. If relax it to a, E [0, 1], this becomes a convex optimization problem solvable by standard methods (even for very large C) and provides (and for which Proposition 5 applies). However, the optimal solution of the relaxed problem might not be feasible for the original problem, because it might have fractional values for some a; while the original problem requires these to be binary. There are certain special cases where the optimal solution of the relaxed problem is guaranteed to be integral (i.e., all ag it is also an optimal solution for the original problem. This is the case, for example, when the constraint matrix totally unimodular and the right-hand sides of the constraints are integral [84]. Still, we observe from empirical experiments that selecting the top k a, of the relaxed problem is a computationally efficient alternative to solving the integer program in Equation (9), since results from rounding produce a negligible difference to the upper bound (see Figures 2 and 3).
upper bound to the original program for reasonable values of the MPR violation
1), in which case
Query: doctor
Fraction of Top-k Similarity
1.000
LP
IP
0.995
0.990
0.985
0.980
0.975
0.825
0.850 0.875 0.900 0.925 0.950 0.975 1.000 Fraction of Top-k MPR
Figure 2: Comparison of the linear program with and without taking the top-k to the integer program. Solving the relaxed program is much more computationally efficient and achieves similar performance after rounding to solving the integer program.
D.1 Multi-group Optimized Retrieval via Quadratic Programming
Proposition allowed us to have simple closed-form representation of MPR in the case of bounded- norm linear regression functions, i.e., when C' {c C mk
+n
E o(x:)2 1}. and
C = {a + wT w Rd). In this case, MOPR becomes
25

---

Query: architect
Query: arbst
Query: chef
1.0030
Similariit
1002
Fraction of Top-k Similarity
1,02
0.897
0.930
9.003
Fraction
00830
Fraction
0.091
2,99
0.830
0.35
0.50
0.83
0.93
5.85
1.00
0.88
0.00
3.42
6.54
0.05 0.80
1,00
0.85 6.88 0.60 2.03 5.64 6.65 0.80 3.50 0.04
Fraction of Top-K MPR
Fraction Top-k MPR
Frection Top-k MPR
Query, engineer
Query: lawyer
Query: nurse
Fracction of Top-k Similaiit
1.00
Similarity
1.02
Fraction of Top-k Similarit
1.0
0.59
3.93
0.902
0.80
Fraction
3.94
0.55
0.73
2.92
0.10
0./5
2,5
0.8b
0.30
0,35
-002
0884
0.00
0.5t 0.00
202 1.94 0.36
1.00
0.73
5,80
0.85
0.90
0.5
1.00
Fraction Top-k
Fraction Top-k MPR
Fraction of Top-k MPR
of T0p-k Simlarity
1.00
Query: programmer
Simslarity
1.002
Query: scientist
Fraction of Similarit
1.00
Query: teacher
2.2
0.98
0.000
0.87
0.65
585
0.70
0.75
645 0.90 380
0.922
0.88
3,95 Top-k
3.96
3,05
3.45
5.82
0.55
0.90
0.95
3,50
Top-k
Top-k
Figure Additional comparisons of relaxed problem and top-k selection integer program. "chef", "nurse". "artist", "lawyer", "teacher", "engineer", "architect", "scientist", and "programmer".
max a
(52)
mk
subject to
V m k:
|U/a|| S
aT k,
E {0, 1}.
where ā E 1a++m has i-th entry given by a, 1 1,gn d1 1220
This result allows us to explore the efficiency of the cutting plane algorithm MOPR by comparing to the solution (52), which is closed-form. convex quadratic program that be easily optimized with existing solvers. Note that in these experiments, top-k refers to the process of solving the relaxed linear program and then rounding get solution {0, 1)" by selecting the k: items with the highest score given by a. This is different than the Top-k described elsewhere in the paper, which denotes conducting vanilla retrieval without fairness considerations. In Figures and 6, we compare the quadratic optimization problem (Eqn. 52) to MOPR (a linear program, Algorithm 1) for linear regression and measure the MPR of our solutions with the closed form value from Proposition As we can see, while the quadratic program traces smoother curve, MOPR's cutting plane approach vell-approximates the closed form solution. without curation set. Finally, in Figures 5 and 7, we run MOPR with the quadratic program oracle and compare our measurement MPR with the closed form solution and linear ggrresso-approxiiant measurement of MPR. In other words, where Figures 4 and 6 measure the quality of our retrieval algorithm given a perfect (closed form) MPR oracle, Figures and measure the quality of our MSE estimator of MPR in comparison to the perfect oracle. We observe that the MSE oracle is perfect approximator of the closed form for MPR, as expected.
these experiments, we retrieve 50 items from CelebA,
26

---

Query: lawyer
Fraction of Top-k Similarity
1.00
NOPR (Ours)
Top-K
0.99
QP Top-k
0.98
0.97
0.96
0.95
0.94
0.93
0.92
0.0
0.2
0.4
0.6
0.8
1.0
Fraction of Top-k MPR
Figure Similarity vs MPR for Quadratic Program (Eqn. 52) and MOPR. MOPR well approximates quadratic program along the Pareto frontier. Measured over single query "A photo of a lawyer" for 50 retrieved samples on CelebA.
MSE Estimator vs QP, Query: lawyer
Fraction of Top-k Similarity
1.00
NSE MPR Estimator
0.99
0.98
0.97
0.96
0.95
0.94
0.93
0.92
0.0
0.2
0.4
0.6
0.8
1.0
Fraction of Top-k MPR
Figure Similarity MPR for MSE estimated (Prop 3 and closed form (Prop measures of MPR. For the class of linear models, linear regression oracle perfectly achieves analytical solution for MPR. Mcasured over a single query "A photo of a lawyer" for 50 retrieved samples on CelebA.
D.2 Computing MPR for Functions in an RKHS
Kernel methods are generalized but practical, non-linear, and easy technique to implement algo- rithms for plethora of important problems in machine learning [85, 86]. As MPR is closely related to the maximum mean discrepancy problem, a closed-form expression of MPR can be easily deduced by using results from [60, Lemma 6] when C is reproducing kernel Hilbert space, which includes, for example, linear regression, logistic regression, Gaussian kernel ridge regression, and hard mard-margin SVMs.
Proposition (MPR for RKHS [60]). Let {xt 1i be retrieved samples R and {af) 1 the samples from the curation dataset De. Let C be reproducing kernel hilbert space with kernel K(,, .), then
1/2
2 kmm
MPR(C, R. Q)
Σ
K(x), xJ)
Σ
K(x xz) +
K(a ag))
(53)
mk
n
f,
f,1=1
Therefore, given kernel (C(,,)) we can easily compute MPR(C, R, Q) by evaluating the kernel the points æ. a.f and use this in Algorithm I.
27

---

Query: chef
Quary 7LLES2
Query: artett
Simiaaii
0.90
Fracion of TTpp-
0.86
0.84
0.24
2.900
Fraction
0.02
0.00
Fraction
2.75
0.0
CA
3.6
6.8
1.0
5.0
3.2
64
0.
6.0
100
0.0
0.3
6.1
0.6
1.0
Fraction Top-k MPR
Fraction Top-k MPR
Fraction Top-k MPA
Fraction TTppp Similarity
Query tictter
Frection Topo- Simillrity
1.00
Query teatter
Top- Similarty
Queryy angiitee
Juth
3cm
0.990
3.96
0.96
0.985
3.94
0.993
0.64
2.32
037a
0.92
3.90
0273
0.88
3.0
0.2
34
0.6
2.8
1.0
0.0
3.3
64
0.6
6.0
1.0
3.86
0.2
52
644
0.6
1.0
Fraction of Top-k MPR
Fraction Top-k MPR
Fraction of Top-k MPR
Fraction of Sinilarity
Query:
Query:
1.00
Qunry: programme"
0.59
0.09
3.90
0.88
0.59
3.90
0.99
3.00
0.55
0.50
Fraction
3.90
0.4
9.94
3.8
2.0
0.2
5.4
0.5
0.8
1.0
0.0
3.2
84
0.5 0.6
1.0
0.2
5.2
0.4
0.5
1.0
Top-k
Fraction Top-k
Fraction of Top-k MPR
Figure 6: Additional comparisons of Quadratic Program (Eqn. 52) and MOPR over queries "chef", "nurse". "artist", "doctor", "teacher", "engineer", "architect", "scientist", and "programmer".
MSE Estimator vs. OP. Query: chef
MSE Estimator vs QP, Query: nurse
MSF Estimator CP: Query. artist
Fraction Top-k 5im Baritty
100
Fraction Similaaitt
Fraction Top-k Simillritty
1,022
0.60
0.00
0.00
2.332
0.67
0.97
0.86
0.00
3.802
0.55
0.64
3.72
2.5
0.8
3.2
64
0.S
0.5
5.0
0.2
0.5
Proction Top-k MPR
Fraction of Top-k MPR
Proction of Top-k MPR
MSE Estimetor OP. Query: doctor
MSE Estimator QP. Qu teacher
MSE Estimator QP. Query: engineer
Fraction of TTppk Sinilaryy
1.007
Fraction Top-k Similarity
1.00
Fraction Tapsk Sirrllriity
0.595
0.59
2.59
0.00
0.00
3.96
0.003
3.40
0.803
0.675
0.59
3.40
0.673
0.56
3:40
3.0
0.2
3A
0.6
5.8
1.0
0.0
3.2
64
0.6
6.0
1.0
0.0
0.
34
0.6
0.0
1.0
Fraction of Top-k MPR
Fraction Top-k MPR
Fraction of Top-k MPR
Fractiin of Topak Similarit
1.00
MSE vs QP. Query. architect
Simitarity
1.00
MSE Estimator vs OP. Query: scientist
Fraction T.p- Siiltarity
1.52
MSE Estimator vs QP. Query: programmer
0.00
0.60
0.54
0.58
0.90
Freetioon
0.50
0.64
0.9
0.6
0.4
2.4 Top-k
3.0
02
SA
3.6
6.4
1.0
ToP-KMPR
Figure 7: Additional comparisons of MSE closed form MPR estimator for queries "chef", "nurse", "artist". "doctor". "teacher", "enngineer,, "architect", "scientist". and "programmer".
28

---

Eimhedding
Change Embresling Change Retrieval
Pre-deliaed Iealures
Apprescc to Diversity
Custom
gotoe/Dssonelllt Atribuies
PRM
Any VLM
Equal Represoratioon over Alribuiees
PATRS
Casiom
High Varianee Kepessenition over Altritates
CLIP-Clip
VLM
Ignere/Dscorrliiee Amribuies
Multgroup Propertional Representution Artributes
Table 2: Axis of comparison for and existing fair retrieval methods. The blue color indicates positive
feature the method, while the red color indicates a negative one.
E Description of Fair Retrieval Algorithms and Retrieval Statisties
In this section, we describe the methods we benchmark against that aim to promote faireess mul- timodal models like CLIP [23]. We also briefly overview proportional representation political sciences.
CLIP-clip (Wang et al. [18]): CLIP-clip is a post-processing algorithm with two stages. First, the mutual information between each positional feature of an embedding and some sensitive attributes is estimated (treating each sensitive attribute as discrete random variable and each position as a continuous random variable [87]). Then, in order of greatest to lowest mutual information, at test-time some number of CLIP features text and image embedding, resulting in less bias (at cost to the fidelity of the embedding). By varying the number of features dropped, recall-bias trade-off is induced.
dropped from both the
CLIP- (Berg et al. [20]): The algorithm learns series of tokens that pre- pre-pended to text queries into CLIP via adversarial training to minimize the ability to predict a sensitive attribute of the resulting embedding (in the default case, gender). Then, retrieval is conducted with the debiased embeddings.
Post-Hoe Bias Mitigation ([29]): Post-Hoc Bias Mitigation a post-processing method that relies on oracle classifier to label elements that might be retrieved with either one of several sensitive attributes or a neutral label. Then, iteratively, Post-Hoc Bias Mitigation adds either set of elements (one of each predicted sensitive attribute) or predicted neutral element to target equal representation, based on which option has higher average cosine similarity. The oracle may be a pretrained classifier, a zero-shot method using CLIP embeddings, or the true labels.
PATHS (Srinivasan et al. [27]): PATHS is a new embedding space built upon the pretrained image-text model CoCa and leveraged text-guided projections extract embedding that captures complex notions of diversity in people, upon which a diverse retrieval method (such the MMR method detailed above, even MOPR) be to effectively increase the diversity of the returned samples.
F
Connection to Social Choice Theory
In this section, we comment on the role of proportional representation in social sciences. As described in the related works in Section 1, proportional representation (broadly construed) has long history in social choice theory and political sciences [88-92] and has been guiding principle in the design of political systems, aiming to ensure representation reflects underlying population preferences and demographics. The foundations of social choice theory can be traced back to the late 18th century, with the seminal works of Jean-Charles de Borda and the Marquis de Condorcet, who developed fun- damental voting methods and paradoxes that continue to influence modern computational approaches. During this same period, early proponents of proportional representation emerged, such Honoré Gabriel Riqueti, Comte de Mirabeau, who discussed the idea in 1780.
The 19th century saw significant contributions to the development of proportional representation, including the works of Thomas Wright Hill, Thomas Hare, and Charles Dodgson (better known as Lewis Carroll), who made substantial contributions to voting theory and proportional representation systems. Hare's 's 1859 publication, "A Treatise on the Election of Representatives, Parliamentary and Municipal" [93], outlined a system of single transferable vote for proportional representation. In the late 19th and early 20th centuries, the works of Carl Andrae, Victor D' D'Hondt, and John Stuart Mill further explored and contributed to the discussion of proportional representation in the political
29

---

science literature. The field was revolutionized in the 20th century by Kenneth Arrow's 's seminal work, whose impossibility theorem fundamentally shaped our understanding of social choice mechanisms. See [88-92].
Similarly, in MI, our aim is proportional representation in data and outputs, ensuring equitable performance across groups and mirroring representation goals in political systems. PR electoral systems [94], used by countries like Uruguay, Sweden, South Africa, and New Zealand, allocate legislative seats proportionally to votes received by parties. Challenges include, e.g., gerrymandering [94] and the complexity of apportionment and seat allocation [95, 96].
The emergence of computational social choice theory [97] in recent decades has built upon these classical foundations while introducing new algorithmic perspectives to address modern challenges. Researchers began studying algorithmic aspects of proportional representation, particularly focusing on the complexity of achieving different notions of proportionality in committee selection [95, 96]. The Hamilton and d' Hondt methods, initially developed for parliamentary seat allocation, have been extended and generalized handle more complex scenarios. As mentioned at the end of Section 1, notable contribution in this direction is the work of Lang and Skowron [37], who introduced multi- attribute proportional representation. Their framework generalizes classical apportionment methods to scenarios where candidates possess multiple attributes (such as gender, profession, and age), and representation goals must be satisfied across all these dimensions simultaneously. Their work provides both theoretical guarantees through approximation algorithms and practical methods for achieving proportional representation in modern committee selection problems, bridging the gap between classical political science approaches and contemporary computational challenges. In particular, they introduced the problem of multi-attribute proportional representation in committee selection. Their framework can be viewed as solving an (m, t)-filling problem: given m buckets (representing intersectional groups) with target capacities {fi,..., { (derived from marginal probabilities), the goal is to optimally fill these buckets with appropriately labeled balls (committee members).
While groundbreaking in extending classical apportionment methods to multiple attributes, their ap- proach differs from ours in several key aspects. First, their work considers multiple attributes, but they primarily focus on matching target proportions derived from marginal distributions for each attribute independently rather than truly addressing intersectional representation. That is, their approach aims to satisfy target proportions for each individual attribute (like gender or profession separately) but does not explicitly handle the complex interactions between attributes (like representation of specific gender-profession combinations). This is in contrast to our framework, where the function class can directly capture and measure such intersectional relationships. Moreover, their formulation focuses solely on matching target distributions without additional objectives, whereas our work explicitly balances representation with retrieval utility through cosine similarity maximization. Second, while they work with pre-specified target probabilities, we estimate the desired representation from a reference dataset, making our approach more flexible and data-driven. Third, and perhaps most importantly, our MPR metric measures representation through the lens of computationally identifiable groups defined by the aforementioned function class C rather than explicitly enumerating all possible intersectional groups Through C, our framework provides a unified way to handle both simple and complex representations: it can capture discrete indicators for each attribute-valus pair (like the Hamilton method; see Definition 5 in [37]) but also complex nonlinear relationships (like d' d'Hondt method; see Definition 6 in [37]), and goes beyond both to measure intersectional representation via decision trees, linear functions, neural networks, or more generally, any function in a reproducing kernel Hilbert space (RKHS). This allows us to handle more complex notions of representation while maintaining computational tractability. In essence, while [37] provides fundamental insights for multi antti-et committee selection, our framework offers more general approach suitable for modern retrieval systems where both representation and relevance matter.
G Additional Results
In this section, we include additional experimental results. First, we include a comparison of runtimes for each method in Table 3. We find that MOPR provides up to a 100x speedup when compared with the most competitive retrieval algorithm, MMR, while remaining competitive to methods such as CLIP-Clip and DebiasCI.IP that do not modify the retrieval algorithm at all and just use embedding similarity search. We additionally provide the similarity score for the minimum MPR achieved by each algorithm, which was used to report the results in Tables I and 5. These similarity scores can be
30

---

found in Table 4. Even when significantly closing the MPR gap and achieving more representation than other methods, MOPR also preserves high cosine similarity with respect the query.
Second, we include full tables of intersectional retrieval performance on UTKeaace for our method, Top-k, MMR, CLIP--llip, PBM, and DebiasCLIP. We report averaged results for each of the 10 queries while retrieving 50 images. In Table 5, we compute MPR with a linear regression oracle and optimize our method with the same linear regression oracle. We are able perfectly balance across intersectional groups while other methods often fail to account for the 'Others' race category and the 'Female' gender category. Some methods, such as PBM, which optimize for equal representation, are able to achieve balanced representation across the gender axis but fail to consider diversity in race. In Table 6, we see a similar story for MPR measured and optimized with a decision tree.
Next, we include additional similarity-MPP tradeoff curves for the other 9 queries not reported in the main paper (Figs. 809, well as for all 10 queries two additional models: decision tree (Figs. 11, 12, 13) and with an MI. with 1 hidden layer of dimension 64 (Figs. 14, 15, 16). We observe a similar Pareto-domination that observed in the main paper, as our method is able to lower MPR the most while preserving similarity even with more nonlinear oracle estimators of MPR. In the MLP setting, while PBM preserves high similarity on the whole, it still unable to decrease MPR low as MOPRis able to at ~ 95% of top-k similarity.
We also include results for additional 45 queries for the Occupations dataset (with FairFace the curation dataset), as this dataset comes with 45 ground-true occupations labels. These results again highlight the Pareto-dominance of MOPR, as shown in Figures 17, 18, and 19.
In Figure 20, we explore the performance of MOPR in terms of precision, a common retrieval metric. We can do this using the Occupations dataset, as it has ground truth occupations labels with which we can benchmark retrieval precision. We see that MOPR performs competitively in terms of precision while also traversing more of the precision-MPR Pareto frontier. In Figure 21, we include nine additional precision-representaaie curves. Similar to the result for the query "chief executive officer", MOPR maintains similar precision repressetttereenntttttioon performance to baseline methods.
Finally, we include example sets of retrievals for 'architect' and 'teacher' queries over UTKFace with each of our baselines. Similar to the tables, we select each algorithm's 's solution with the lowest MPR after doing a hyperparameter sweep for each respective algorithm and plot the corresponding images below. The rest of the Appendix is solely tables and figures.
k=10
k=50
k=150
MOPR(LP, 10 iterations)
1.434 + 0.304
1.6 + 0.54
1.371 + 0.361
MOPR(LP, 50 iterations)
5.14 +: 0.352
4.199
1.74
4.342 + 1.803
MOPR(QP, linear regression)
0.528 + 0.061
0.533 = 0.066
0.584 + 0.089
MMR
151,961 = 1,126
267.412 + 3,863
556.184 + 6.324
PBM
0.275 + 0.162
0.241
0.013
0.276 + 0.151
CLIP-Clip
21.303 + 0.361
21.907 + 0.525
21.34 + 0.353
DebiasCLIP
2e-4 le-6
2e-4 = 1e-6
2e-4 1 le-6
Table 3: Average running time (in seconds) over queries for k= 50, and 150 items for the different methods.
MOPR is able to achieve 100x speedup over the SOTA retrieval algorithm, MMR, and maintains competitive
performance with vanilla KNN-based methods such as CLIP-Clip and DebiasCLIP. For more discussion, see the
general comment in the rebuttal.
Normalized Mean Cosine Similarity
Top-k
1,0000 +'2 0,0000
MOPR
0.9049 0.0692
MMR
0.8047 = 0.1477
PBM
0,9416 + 0.0802
CLIP-Clip
0.7758 + 0.1433
DebiasCLIP
0.8497 + 0.0985
Table 4: Normalized mean cosine similarity between the query embedding and retrieved image embeddings for retrieved images from Tables 1 and 5. The normalization is performed by dividing the mean similarity by the mean similarity given by the Top-k nearest neighbors of a query.
31

---

Table 5: Retrieval averaged 10 queries with 50 retrievals UTKFaac dataset [40] for MOPR, k-NN, MMR [27]. CLIP-Clip, PBM, and DebiasCLIP with MPR optimized and measured with a linear regression oracle. Entries indicate the average percentage representation in retrieved items. MOPR is able to balance representation across classes, whereas other baselines miss intersectional groups (highlighted in red).
White
Black
Asian
Indian
Others
Sum
Male
7.8 3.74
10.2 = 2.90
13.0 + 2.56
11.8 # 2.44
3.70
50 =
MDPR (Ours)
Female
12.2
9.8 + 2.90
7.0 1: 2.56
8,2 =
12,8 3.70
50 =
Sum
20
20
-00=0
20
Male
21.2 11.84
13.2 7.70
10.8
21.2 20.70
1.4 1.56
67.8 23.72
Top-K
Female
17.2 + 21.04
6.14
4.0 + 2.82
2.8 2.56
1.6 1.50
32.2 23.72
Sum
17.18
17.18
19.8
12.56
14.8 7.38
24 = 19,38
3,0 2.04
Male
28.8 1. 8.96
11.0 4.58
10.2 4,04
10.8 1: 2.40
3.8 1: 1.06
64.6 1.74
MMR
Female
16.2
3.66
5.0 3.00
1.26
2.6 + 1.56
35,4 7.74
Sum
45.0 3.0+-7.7
18.6 5.38
15.2 + 5.82
14.8 + 3.12
6.4 1.96
Male
23.2 9.96
11.0 5.16
10.8 + 5.88
14.2 + 8.70
1.8 + 2.08
61.0
17.08
CLIP-Clip
Female
15.2 9.44
7.0 1 4.32
7.4 5.30
6.6 5.52
2.8 1.84
39.0 17.08
Sum
38.4 11.42
18.0 8.20
18.2 5.68
20.8 9.52
4.6 +
Male
19.8 1 7.82
7.12
15.2 8.72
1.2
58.6
11.62
PBM
Female
18.6
5.92
5.6 3.88
7.2 5.16
41.4
11.62
Sum
38.4 1 13.50
21.4 11.38
15.0 6.70
22.4
13.44
2.8 2.04
Male
20.4 7.48
8.2 3.94
5.4 2.54
11.0 3.50
3.8 2.6
48.8
5.52
DebiasCLIP
Female
19.4 6.98
9.4 = 5,14
8.4 4.28
10.0 + 4.64
4.0 +: 1.78
51.2
5.52
Sum
39.8 9.78
17.6 3.66
13.8
5.62
21.0 1: 6.52
7.8 1: 3.16
Table 6: Retrieval averaged 10 queries with 50 retrievals UTKFaae dataset [40] for MOPR, k-NN, MMR [27], PBM, DebiasCLIP MPR optimized measured with a decision tree oracle. Entries indicate the average percentage representation in retrieved items. MOPR is able to balance representation across classes, whereas other baselines miss intersectional groups (highlighted in red).
White
Black
Asian
Indian
Others
Sum
Male
11.0 1.34
10.4
10.0 = 0
10.2 0.6
8.8 = 0.98
50.4 = 1.64
Ours
Female
10.6 - 1.28
9.6 1: 0.80
9.6 + 1.20
10.2 + 1.08
9.6 1.2
49.6 : 1.64
Sum
21.6 1.64
1.26
18.6 1.2
20.4 + 1.2
18.4 1.2
Male
21.2 1: 11.84
13.2 7.70
10.8 1 7.54
21.2 20.70
1.4 1,56
67.8
23.72
Top-K
Female
17.2 21.04
1
2.82
23.72
38.4 17.18
19.8
12.56
14.8 7.38
19.38
3.0 3.0 2.04
Male
27.4 9.13
11.8 5.02
10.2 4.33
10.2 3.03
3.2
62.8
11.77
MMR
Female
1.11
5.67
5.4 3.47
3.6 1 1.5
2.2 2.2.1: 1.08
37.2
11.77
Sum
20.8 9.39
15.6 5.64
13.8 + 3.84
5,4 =.37
Male
19.6 13.11
12.4 6.56
9
15 + 8.91
1.2 1.6
57.6
12.74
PBM
Female
13.11
+
+.4+
5.15
1.8 1.66
42.4 + 12.74
Sum
39.2 +: 13.45
20.8 + 11.07
14.8 + 6.46
22.2 13.61
3 2.05
Male
20.4 = 6.99
8.94
5.4
11 3.49
3.8 2.6
48.8 + 5.53
DebiasCI.IP
Female
19.4 99.4-6.99 6.99
9.14
8.27
4.65
1.79
51.2 5.53
Sum
= 9.78
3.66
13,8 -
21 6.53
3.16
32

---

(Ours)
ClIR.
Qary arthled
Quary ata
Quary Ovl
1.00
of Sinitarty
1.00
Frodiio of Top- Simitarty
0.66
8.60
80
8:90
Toox
8.8
0:66
0.80
9:30
0.35
0.79
616
Fractinn of Top-k KPP
Fraction of Top l MPR
Fracdon of Top MPR
Guary: doctr
Quary: ongineer
Quay lowaer
1.00
Top-k Smilath
1.00
Foudfon Tup-k Smialty
0.50
8.55
6:40
2.45
0.60
8.80
8.00
077
0.70
0.8
8.6
1.5
616
1.00
8.25
Fradiion Top-k MPR
Fraction of Top MPR
Fracsin of Top Pop-KM MPR
Ouirs name
Query soundr
Quary teacher
Froddon Smlarty
1.0
Fracton Top-k Smilfty
1.0
Freddon of Smiaffy
025
9.00
8.05 0.00 8885 8953 1.000 1.005 Fracton of Top-k MPR
0.75
0.00 Fracciin of Top-k MPR
6.00
6.50
0.85
100
Fraction Toget MPR
Figure 8: Fraction of Top-k cosine similarity Fraction of Top-k MPR over linear regression models for additional queries for the CelebA dataset. Values normalized Top-k achieves point (1,1) in each Pareto-dominates baselines significantly closes the MPR gap.
33

---

MDPR (Ours)
MMR
-+-
PBM
CLPP-Ci
DebiasCLIP
Fracton Top-k- Silatty
Smilefy
Fradon of Topak Topkk Smitaity
0.66
2.0
0.50
00
0:50
0.
6-
0.75
94
8.40
0.5
06 Top-k
0.6
Top-
Top-k
Fracton of Top-k Simlant
Fractor of Topak Simllarty
Fracton of Tapak Shillamly
2.6
08 Top-k
04
0.4
0.0 Top-k
Fraction Top-k MPR
of Stritary
1.0
Fraction of Toplk Strllarity
Fraciion of Topak Stiitarly
0,7
08
04
Fradion Top-k
Fractiin
MPR
MPR
Figure Fraction of Top-k cosine similarity vs Fraction of Top-k MPR over linear regression models for additional queries for the UTK dataset. Values are normalized so Top-k achieves point (1,1) in each case. MOPR Parcto-dominate basclines and significantly closes the MPR gap.
Ouarp arch
Quaty wrbl
Query
of Bmtorny
1.0
of Smiary
Fradton ToTpk Smiarrty
82
M
of oo
8.0
2.5
Fridion Top-k MPR
Fraction Top-k MPR
Frecsion MPR
Query: anginear
Query
1.0
orodlen To Smilrtt
1.0
Fincaton of Top-k Smilaity
0.
Frocton Topkk
2.0
8.
0.6
0:
Fraction MPR
Fraction Top MPR
Fracson MPR
Ouarss
Quayy adenta
Froctor To Smlarty
1.0
1.0
Freedon of Top-k TTpak Smiarty
Frocdon Tookk-klaaar
8.
8x
6.4
Fradioo Top-k MPR
Fraction
Top-k MPR
Fraction Top- MPR
Figure 10: Fraction of Top-k cosine similarity vs Fraction of Top-k MPR over linear regression models for additional queries for the Occupations dataset. Values are normalized so Top-k achieves point (1,1) each case. MOPR Pareto-dominates baselines and significantly closes the MPR gap.
34

---

MOPR (Ours)
CLIP-Cip
DebiasCLIP
8.5
020
025
3,00
305
DO0
6:0
1.00
070
0.5
0.0
1:00
18c
110
1.30
0.0
0.5
8.00
5.00
Dair: docor
Query enginer
Quay Inaele
Tookkkkk Tt Smibrry
1.00
or Sinterg
1.00
Frendion of Topaic Simlartty
0.60
8:40
2.85
0:05
0.00
0.00
0.75
0.75
0.7
6.70
0.5
0.8
Fradiion of Top-k MPR
Fracsion of Top-k MPR
Fracsion of Top-kMPR MPR
Gutey nanaa
Query woenar
Qutty Taadher
1.0
Flacton Top--k Simiarit
1.0
Frecfion of Top- Smitarty
1.0
Too
87
(.00
3.66
Foadiio of Togak MPR
Fracdon of Top-k MPR
Friction of Top-k MPR
Figure 11: Fraction of Top-k cosine similarity vs. Fraction of Top-k MPR over decision trees for 10 queries for the CelebA dataset. Values normalized so Top-k achieves point (1,1) in each MOPR Pareto-dominates baselines and significantly closes the MPR gap.
610
Pradienl Top
Tradken MPM
Fracton NPP
Tradeend
24
Dams: dopar
Oueyy expree
Ouey: leaerr
Sintertty
1.0
Sintertty
1.
Fractoo of Top-k Sintlrfty
0.5
0.7
Fraetion
64
8.0
06
0.2
0.4
Fradionn of Topa MPR
Fraction Top-k MPR
Fraction of Top- Top-kMP MPR
Quars rame
Saay sourcal
Qary leans
1.0
Fraedbon Sinvlartty
Fradbon of Top-k Sinkaifty
8.0
6.
2.4
1.0
Fractio of Top MPR
Fracdion Top-k MPR
Fracson of Top MMR
Figure 12: Fraction of Top-k cosine similarity vs Fraction of Top-k MPR over decision trees for 10 queries for the UTKFaace dataset. Values normalized Top-k achieves point (1,1) in each case. MOPR Pareto- dominatssss baselines and significantly closes the MPR gap.
35

---

MOPR (Ours)
CLIP-Cip DebiasCLIP
1.00 300
Tradiend Top
Foxdend MFR
Pasten
Ouary dbcor
Quayy engreer
Quay Inaele
1.0
oradioon Similartt
1.0
Fredtion of Top-k Stnslarit
Froddon of TopTpp
26
08
Fraztion Top-k MPR
Fraction Top-K MPR
Fracdon of Top-k MPR
Quaee ransa
Query edlenna
Qualy: bochee
1.0
Fraddon of Too-k Siniirityy
Fredtin Too-k Simtarity
1x
3.25 0.85
Fradtion Top- MPR
Fraction Top MPR
Fraction Top MPR
Figure 13: Fraction of Top-k cosine similarity vs. Fraction of Top-k MPR over decision trees for 10 queries for Occupations dataset. Values are normalized so Top-k achieves point (1.1) each case. MOPR Pareto- dominates baselines significantly closes the MPR gap.
Fradeenl
Practen Top-:
Practio Topa NPR
TPP
Queti sodor
Query srgraar
Godyy Noope
1.50
Fracton Top-k Sintlrfty
1.00
Fradion of Topk Siitartty
0.00
8:d0
3.20
0.80
0.75
0.72
10
15
20
2.5 Fracdio of Top-k MPR
Fractin of Top-k MPR
Fraction of Top- MPR
Quarr rame
Qpayy souncal
Qharr leacer
Semlertt
1.0
Semtaatty
1.0
Fractor of Topek Seniarlyy
km
Fraction
Fracdion of Toppik MPR
Frecction
Top-k MPR
Fraction of Top-k MPR
Figure 14: Fraction of Top-k cosine similarity Fraction of Top-k MPR over 2-layer MLPs (hidden dimension 64) for 10 queries for the CelebA dataset. Values normalized Top-k achieves point (1,1) in each case. MOPR baselines significantly closes the MPR gap.
36

---

(Ours)
CLIP-Cli
DebiosCLIP
200
025
8.50
320
500
175
60
23
35
Dasry: docor
Ouey: ongreer
Quars langer
To Sibbrrt
1.
Fractoon of Simlars)
Frecfion of Top-k Siilart
2.
2.
Fradtion Topat MPR
Fraccion Top-k MPR
Fraidoon of Top-s MPR
Darss rume
Gaay vourrot
Gary leacher
Top Top.k Simbary
1.0
Tf Simiarity 13
Fradion of Top-k Simiarity
20
Fraddion of Togelt MPR
Fracction Top-k MPR
Fraction of Top-k MPR
Figure 15: Fraction of Top-k cosine similarity Fraction of Top-k MPR over 2-layer MLPs (hidden dimension 64) for 10 queries for the UTKFacc dataset. Values normalized Top-k achieves point (1,1) in each case. MOPR Pareto-dor -areto-dominates baselines significantly closes the MPR gap.
of Top MPR
of T MPR
Fo Top MPR
Fractonof Teo MPR
Dars: do00
Donyy anginer
Gody heaper
1.0
Fraetion Siniartty
Fractio TTp-k Binterfty
2
10p
6r
8.0
0.2 0.50
150
175
Fradiion of Top- MPR
Fracdon
Top-K MPR
Fracdon of Top-k MPR
Gars rone
Spary souncal
Qtary leacher
Siniaritty
Fraebon of Top-k Sinikrhty
60
60
87
Fraetton
0.8 1/3 12
Fraction Top MPR
Fracion Top MPR
Fracdon of Top MPR
Figure 16: Fraction of Top-k cosine similarity vs Fraction of Top-k MPR over 2-layer MLPs (hidden dimension 64) for 10 queries for the Occupations dataset. Values normalized Top-k achieves point (1,1) each case. MOPR pareto-dominat baselines significantly closes the MPR gap.
37

---

MOPR (Ours)
-
MMR
-
PBM
CLIP-CEP
DebiasCLIP
Fraction Tapkkk Simiarrty
Similerity
Query.
Frectoon Topk Simllerty
0.0
0.8
0.8
3.8
0.7
0.7
0.6
0.6
05
0.4
9.3
200 5230 Top-k MPR
2350 981
2000
Fraction Top-k
Top-k
Fraction Topa-- Similrrty
Iedegho
Topak Similarity
Erectoo Topk Top- Similerity
0.0
0.9
0.
0.0
0.7
0.6
05
044
2025
Fraction Top-k
Fraction MPR
Fraction MPR
Fraction Topo- Similarit
Fraction Similarity
1.0
Fraction of Topak Similtrity
0.0
0.0
S.
0.7
0.6
0.0
0.
0.
Fractin of MPR
Fraction MPR
Fraction Top-k
Fraction Top-k Bartty
1.0
Fraction Similarity
1.0
frection Top-k Sim Banity
0.
0.0
0.0
3.8
0.r
0.6
3.5
0.5
Fraction of MPR
Fraction Top-k MPR
Fraction Top-k MPR
contrruttion
Query: cook
1.0
Similarity
1.0
Frection of Top-k Similarity
Wy
0.0
0.9
0.8
0.8
3.8
Praction Topak
3.7
0.8
3.0
Frection
3.5
03
0.A
Fraction
Fraction MPR
Fraction Top-k
Figure 17: Fraction of Top-k cosine similarity vs Fraction of Top-k MPR over linear regression models for 45 (First 15, see Figures 18 and 19) accupations present in Occupations dataset. Values are normalized so Top-k achieves point (1,1) in each case. MDPR Pareto-dominates baselines and significantly closes the MPR gap.
38

---

MOPR (Ours)
MMR
PBM
CLIP-Ci
DebiasCLIP
Frartion Tap-k Simiaarty
Fraction Top-k Similerity
Frectoo Topk. Similerty
0.
0.8
2.8
0.7
0.7
0.
0.6
0.5
1,30
0.55
Fraction MPR
Fraction ToTop-k Similarit
Fracioon Similarity
Fracioo Topak Similerity
2.2
0.4
0.7
8.5
Fraction
Fraction MPR
Fraction
MPR
Fractonn of Topop- Sinitarty
Rracion Similarity
Fraction of Topak Similarity
0.0
3.9
0.0
0.8
3.7
0.
0.6
0.5
23
Fraction MPR
Fraction Top-k
Fraction Top-k
Fraction Top--k Sim Bantyy
1.0
Similarity
1.0
0.8
0.8
Fraction Top-k
0.7
0.6
8.6
0.A
Fraction of MPR
Fraction Top-k MPR
Fraction Top-k MPR
practticne
Frection Top-k Similarity
1.0
Frection Top-k Sirri Sirrilerity
Praction Top-k Sime
3.8
0.8
3.8
0.7
0.6
0.5
8.6
2.5
Fraction
MPR
Fraction
MPR
Top-k MPR
Figure 18: Fraction of Top-k cosine similarity Fraction of Top-k MPR over linear regression models for 45 (Second 15, see Figures and 19) occupations present the Occupations dataset. Values are normalized so Top-k achieves point (1,1) in cach case. MOPR Parcto-dominates baselines and significantly closes the MPR gap.
39

---

MOPR (Ours)
-
MMR
-+-
PBM
CLIP-CEP
DebiasCLIP
Frartion Tap-kk Simitartt
Similerity
Fracion Similrity
0.6
08
0.6
0.4
5230 L,00
2.73 020
1.50
Top-k MPR
Fraction MPR
Fraction Tap-k
Frartion Topak Similarity
Fraction Top-k Similarity
Frection Topak Similerity
Query pemapp
0.6
0.6
05
0.5
9.6
0.4
2.5
.075
Fraction MPR
Fraction MPR
Fraction Top-k
Fraction TTTT Suniaarit
Riceptinnt
Fractoon Similerity
Frection Tapak Sirillrity
0.0
0.8
0.7
3.7
0.6
Fraction MPR
Fraction
Fraction Top-k
Fraction of Top-k Sim Bartty
1.0
Frection Sim Baritty
1.0
Fraction Top-k Sim Barity
0.
0.8
0.8
3.8
0.7
0.7
9.6
0.6
2.
Fraction
Fraction MPR
Fraction Tap-k
Fraccton Top-k Similarity
Frection Similarity
Frecioon of Top-k Similarity
43/8
0.0
0.6
0.6
0.5
05
0.4
0.4
Fraction MPR
Fraction Top-k MPR
Fraction Top-k
Figure 19: Fraction of Top-k cosine similarity vs Fraction of Top-k MPR over linear regression models for 45 (Third 15, see Figures 17 and 18) occupations present the Occupations dataset. Values are normalized so Top-k achieves point (1,1) in cach case. MOPR Parcto-dominates baselines and significantly closes the MPR gap.
40

---

MOPR (Ours)
MMR
PBM
CLIP-Cli
DebiasCLIP
Query: silet_executive_ore
0.40
0.35
0.30
Precision
0.25
0.20
0.15
0.10
0.05
0.2
0.4
0.6
0.8
1.0
Fraction of Top-k MPR
Figure 20: Precision-MPR curve Occupations dataset over lincar regression. Retrieving 50 items for the query "A photo of a chicf executive officer." MPR remains competitive terms retrieval performance.
MOPR (Ours)
MMR
-+-
PBM
CLIP-Cli
DebiasCLIP
0.7
Precition
Precision
06
0.4
0.
31
5.4
0.1
1.0
0.2
0.4
Top-k
Top-k
0.5
0.7
0.2
2.2
0.0
5.4
0.5
Top-k
Top-k
3.30
0.30
0.4
3.2
Peciiion
0.25
Precision
Precision
0.29
0.0
3.55
3.10
1.2 of Top-k
Top-k
Figure 21: Additional precision- representationn plots queries "bartender". "bus driver". "chemist", "con- struction worker". "customer service representative", "housekeeper", "nurse practitioner", "receptionist", and "sepecial teacher".
41

---

Figure 22: Retrievals for KOPR with query "A photo of teacher"
sadbwan
Figure 23: Retrievals for I-NN with query "A photo of teacher"
42

---

8
BARADRZ
Figure 24: Retrievals for MMR with query "A photo of teacher"
Figure 25: Retrievals for CLIP-Clip with query "A photo of teacher"
43

---

Figure 26: Retrievals for PBM with query "A photo of teacher"
Figure 27: Retrievals for DebiasCLIP with query "A photo of teacher"
44

---

State
Figure 28: Retrievals for MOPR with query "A photo of an architect"
Babnn
Figure 29: Retrievals for A-NN with query "A photo of architect"
45

---

5140
Fate
Figure 30: Retrievals for MMR with query "A photo of architect"
Shsts
Figure 31: Retrievals for CLIP Clip with query "A photo of an architect"
46

---

Figure 32: Retrievals for PBM with query "A photo of architect"
QUIZ
suite
S'E
Figure 33: Retrievals for DebiasCLIP with query "A photo of an architect"
47

---

H
Experiment Notes
H.1 GPT Generated Queries.
The 10 queries used in experiments and generated by GPT are as follows: [programmer, nurse, architect, scientist, artist, chef, lawyer, teacher, engineer, doctor].
H.2 Experiment Setting and Details.
These experiments were conducted mainly on CPU after initially using a single A100 GPU to compute CLIP and DebiasCLIP embeddings and FAISS compute the top 10k candidates for each. Then, all embeddings are saved so that retrieval across all methods can be run on the CPU. When training linear probes, we conduct cross-vaie volss-valddteed hyperparameter search from 0.01 100 over &2 regularized logistic regression models from scikit-learn [69] to find the optimal probe.
To run MOPR, we use Gurobi [98] with Academic License to solve Eqn. (9) each iteration of our cutting plane method and use CVXPY [99, 100] to solve our flosed-form, quadratic program.
To train our oracle estimators, we call scikit-learn's 's implementations of Linear Regression, Decision Trees with depth 3, and MLPs with one hidden layer of size 64.
On average, the runtime for MOPR is approximately 1-5 minutes with 50 queries and 10000 elements in each of retrieval and curation sets. However, with more features (such using CLIP embeddings instead of group attributes), this runtime can increase. We note, however, that our most competitive baseline, MMR, greedy algorithm that requires 1-2 hours per query to compute. live image retrieval settings, this runtime is too slow to be of any practical use.
48

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In this paper, we introduce the novel metric Multi-Group Proportional Repre- sentation (MPR) in Section 4, we provide theoretical guarantees in Section 3, we develop a practical algorithm in Section and numerically show that existing methods optimizing for equal and proportional representation metrics may fail to promote MPR in Section 5
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We describe them at the conclusion. First, while MPR is designed to handle large number of groups, the computational complexity of the proposed cutting-plane algorithm in the case of general function class C. can be a concern for high-dimensional feature spaces. Developing more efficient algorithms or approximation techniques could help address this issue. Second, while we focused on retrieval tasks, adapting MPR to other domains, such as ranking, recommendation systems, and image generation, could broaden its impact and applicability. Future research could also investigate the long-term societal impact of enforcing MPR real-world retrieval systems to understand its potential benefits and risks. Finally, MPR is inherently limited by the curated dataset. If this dataset is biased against a given group, this bias will be propagated by MOPR.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texx system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
49

---

While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We prove all the theorems in the paper in Section C and Section D. Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: All the necessary information to reproduce the main results will be available in a Github repository with precise instructions for each figure generated this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (c.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
50

---

reproducible, they (c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The datasets CelebA [38], occupations Celis and Keswani [31], Fairface [39], and UTKFace [40] are all publicly available and the code to generated all the figures presented in the paper and to reproduce all the experiments will be available public Github repository.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: http//uuddes//oeeee
/ //nips.
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The experimental setting is described in H.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
51

---

Answer: [Yes]
Justification: Tables 1, and have deviation bars, and the experiments are averaged over multiple queries.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative етгог rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The computer resources are described in Appendix H.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: htap:::////uuiiiie /t////nurip.../ ttt.pppptccppppiic/////cccccctcc Ceablicc//hiieee i
Answer: [Yes]
Justification; The research conducted in this paper conforms in every respect to the NeurIPS Code of Ethics. The paper aims to develop techniques for improving multi-group repre- sentation in image retrieval systems, which aligns with the Code's principles of avoiding discrimination and promoting fairness. The paper does not raise any ethical concerns related to safety, security, privacy, or human rights. The techniques are designed be applied to standard, publicly available image datasets and do not involve any surveillance, tracking or identifying of individuals. No deception or harassment involved. In the paper, we include a discussion of broader impacts, both positive and negative. On the positive side, the tech- niques can help mitigate biases and underrepresentation of certain groups in image search results. This can have significant socictal benefits by reducing stereotyping and increasing
52

---

visibility of marginalized groups. We do not anticipate any direct negative societal impacts, as the methods aim to improve fairness without privileging any groups. Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
As discussed in the previous answer, we included a discussion of broader impacts, both positive and negative. Regarding potential negative impacts, we acknowledge in the paper that the reference distribution is biased, then biases will be propagated to the retrieved items. Still, believe that our method represents improvement approaches that do not consider representational fairness at all. On the positive side, our method has the potential to significantly reduce representational harms in image retrieval systems. By ensuring that results reflect the diversity of the population, we can help combat stereotyping, erasure, and discrimination. This can have wide-ranging societal benefits in shaping perceptions and providing visibility for marginalized groups We discuss these limitations openly.
Justification:
current
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We are not generating any new datasets or models and, therefore, we dont need safeguard.
Guidelines:
53

---

The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We are citing all the publicly available datasets and codes used in the paper.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswithcone com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if it has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [Yes]
Justification: We have added repository https://githe: comm/alex-oosterlnnge www.gruupppoprrtiiooo
mig - with all the code and instructions to re- produce experiments.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
54

---

Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with
human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
55


Reviews:
[{"review_id": "rZN1Bafqkn", "reviewer": "Reviewer_XWMb", "summary": "This paper introduces a novel metric, Multi-Group Proportional Representation (MPR), to measure and ensure fair representation across intersectional groups in image retrieval. Current methods often ensure representation across individual groups, not intersectional groups. To address this, authors", "questions": "1. The concept of fairness is defined by humans and can vary across different countries and cultures. What are your thoughts on this aspect?\n2. It is well-known that the CLIP model has significant bias issues, and many studies (e.g., https://arxiv.org/abs/2210.14562) have attempted to address this. Does your methodology incorporate such debiasing measures?\n3. Is there any experiment or quantitative result about computational complexity?", "limitations": "The authors acknowledge the limitations regarding computational complexity and curated dataset.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Ensuring representation across intersectional groups by suggesting a new metric in image retrieval tasks.\n2. The mathematical and theoretical foundations support the ideas.\n3. A variety of experiments supports the methodology.", "weaknesses": "1. Fairness may include mixed-race individuals and various genders, not just White Male or Black Female. However, in this task, the 'White Male' as an intersectional group raises questions about whether it truly reflects the meaning of intersectionality.\n2. FairFace is not a perfect fair dataset. However, the experimental results for individual groups in Table 1 show perfect fairness across gender and race. How is this possible?\n3. In Table 1, there are significant differences between intersectional groups (e.g., Asian Male : Asian Female = 13 : 7).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer XWMb\n\nWe thank the reviewer for their careful reading of our paper and valuable feedback. We address each of the weaknesses and questions raised below. Please let us know if you have any additional questions.\n\n## W1. \"...the 'White Male' as an intersectional group raises questions about whether it truly reflects the meaning of intersectionality\"\n\nThis is an important point. Intersectionality, as a social science term, historically focuses on the intersection of marginalized identities (e.g., Black females) -- see [1] for a discussion. \n\nWe also agree that intersectional groups are defined beyond simple binary combinations of siloed categories for race and gender and must account for individuals who, for example, identify with multiple racial identities. Our metric allows for measuring the proportional representation of such groups via the appropriate definition of the class $\\mathcal{C}$ and its inputs. For instance, when encoding group membership $\\mathbf{g}_i$ (line 134), the attribute race can be represented as a binary vector admitting multiple entries with 1 rather than as a one-hot vector, thus accounting for individuals with multiple racial identities. We will add this important point to the paper.\n\nWe assume the White Male group mentioned by the reviewer may refer to the groups denoted in Table 1. Here, we select population groups based on the features available in the UTKFace dataset. The UTKFace dataset includes labels for individuals' identities in terms of non-overlapping race and gender attributes, thus not explicitly labeling individuals as members of multiple racial groups or as non-binary. Since we use the labels in the UTKFace dataset, the groups in Table 1 do not overlap. We will highlight this limitation in the main paper.\n\n## W2. \"results for individual groups in Table 1 show perfect fairness across gender and race. How is this possible?\" and \"In Table 1, there are significant differences between intersectional groups (e.g., Asian Male: Female = 13 : 7)\"\n\nMAPR ensures proportionality with respect to a curated dataset. In Table 1, we create a perfectly balanced synthetic curated dataset that is used as reference (line 377). Moreover, MAPR aims to ensure proportional representation simultaneously across multiple groups, including groups defined by individual attributes (e.g., race or gender) and by intersectional attributes (e.g., race **and** gender). As we consider more combinations of attributes, achieving proportional representation becomes more difficult.\n\nIn Table 1, MAPR successfully balances representation at the individual-attribute level and significantly closes the representation gap at the intersectional level. MAPR does not achieve exactly equal representation at the intersectional level due to the distribution of the underlying retrieval set not including enough samples for every group. However, Table 1 demonstrates that 1) MAPR still does better than vanilla k-NN and MMR (the state-of-the-art competing benchmark) for intersectional groups, and 2) MAPR can achieve perfectly balanced representation for groups defined by a single attribute.\n\n## Q1 \"fairness is defined by humans and can vary across countries and cultures. What are your thoughts?\"\n\nYou raise an excellent point about the cultural and contextual nature of fairness. The paper acknowledges this complexity, particularly in the context of representation in ML systems. Our flexible metric (MPR) can accommodate different notions of \"fair representation\" across countries and cultures by allowing users to define their own curated data set that is representative of a target population or desired representation goals. Moreover, the groups for which we aim to ensure representation can be encoded in the set of representation statistics $\\mathcal{C}$ (see lines 174-204).\n\nThe goal of this work is to create a multi-group representation metric that is flexible enough to accommodate varying notions of representation while still providing practical utility and mathematical tractability. Our \"mathematization\" of multi-group proportional representation allows us to understand the statistical limits of estimating representation and ensuring it algorithmically. However, like any \"mathematization\" of fairness, it is only one piece of the puzzle. We highlight the need to carefully consider cultural and societal factors when defining fairness and representation goals. Moreover, we emphasize the importance of involving stakeholders in defining representation goals and auditing retrieval systems. We include the discussion in the final version of our paper.\n\n## Q2 \"CLIP model has significant bias issues, and many studies have attempted to address this. Does your methodology incorporate such debiasing measures?\"\n\nOur method does not directly rely on debiasing CLIP embeddings. Instead, we leave CLIP embeddings intact and rely on group-denoting attributes to ensure a proportional representation of computationally-identifiable groups, denoted by the set of representation statistics $\\mathcal{C}$. Our experiments show that this approach achieves significantly better performance than methods that aim to \"debias\" CLIP embedding such as DebiasCLIP and clipCLIP (see Fig. 1 for benchmarks).\n\n## Q3 \"Is there any experiment or quantitative result about computational complexity?\"\n\nThat is a great question that will be addressed in the final version of our work. We provide benchmarks in the Table R1 attached. MAPR is competitive with existing fair retrieval methods in terms of runtime. Relative to methods with comparable diversity-similarity trade-offs such as MMR (Fig. 1 of the paper), our method has 10x-100x lower computational overhead per query. Please refer to the general rebuttal above for more details surrounding the discussion on runtime.\n\n[1] K. Crenshaw. Demarginalizing the intersection of race and sex: A black feminist critique of antidiscrimination doctrine, feminist theory and antiracist politics.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BH4fCuMrs7", "reviewer": "Reviewer_XQou", "summary": "This paper introduces the novel metric of Multi-Group Proportional Representation (MPR) designed to address the representational harms in image search and retrieval tasks, which can perpetuate harmful stereotypes, erase cultural identities, and amplify social disparities. Current methods to mitigate these issues often balance the number of retrieved items across population groups defined by a limited set of attributes, typically overlooking intersectional groups defined by combinations of attributes such as gender, race, and ethnicity.\n\nKey contributions of the paper include:\n\nIntroduction of MPR Metric: The paper presents the MPR metric, which aims to ensure proportional representation of multiple groups in retrieval tasks, considering intersectionality and combinations of different group attributes.\n\nTheoretical Guarantees: The authors provide theoretical foundations for the MPR metric, establishing its effectiveness and applicability in various contexts.\n\nPractical Algorithm: A practical algorithm for promoting MPR in retrieval tasks is developed. This algorithm is evaluated through numerical experiments to demonstrate its superiority over existing methods that optimize for equal and proportional representation metrics but may fail to achieve MPR.\n\nExperimental Results: The paper includes detailed numerical experiments showing that the proposed MPR-aware retrieval algorithm significantly closes the gap in MPR, outperforming baseline methods across different datasets and retrieval tasks.\n\nDiscussion of Limitations: The authors acknowledge several limitations of their work, including the computational complexity of the algorithm in high-dimensional feature spaces, the need to adapt MPR to other domains like ranking and recommendation systems, and the inherent limitations posed by biased datasets.\n\nOverall, the paper makes significant strides in addressing the complex issue of representational harms in image retrieval tasks by introducing and validating the MPR metric and associated algorithms .", "questions": "Questions:\n\nComputational Complexity:\nQuestion: Can you provide more details on the computational requirements of the proposed algorithm? Specifically, how does its performance scale with increasing dimensionality and size of the dataset?\nSuggestion: It would be helpful to include a discussion or additional experiments that benchmark the computational performance of your algorithm compared to baseline methods, particularly in high-dimensional scenarios.\n\nGenerality of MPR Metric:\nQuestion: How well does the MPR metric generalize to other domains beyond image retrieval, such as text retrieval or recommendation systems? Have you considered or conducted any preliminary experiments in these areas?\nSuggestion: Including a discussion on the potential adaptations of the MPR metric to other domains and any initial results from such experiments could strengthen your paper.\n\nHandling Dataset Bias:\nQuestion: How does your approach address or mitigate the effects of inherent biases in the datasets used? Have you evaluated the MPR metric's performance with datasets known to have specific biases?\nSuggestion: Consider providing more detailed analyses or experiments that explicitly evaluate the impact of dataset biases on the performance of your method, and discuss any strategies for mitigating these biases.\n\nReproducibility:\nQuestion: Can you elaborate on the steps taken to ensure the reproducibility of your results? Are there any supplementary materials (e.g., code, datasets, detailed experimental settings) available to assist other researchers in replicating your work?\nSuggestion: Providing comprehensive supplementary materials, including code, datasets, and detailed documentation of experimental setups, would significantly enhance the reproducibility of your research.\n\nEthical Considerations:\nQuestion: Could you provide a more detailed discussion on the ethical implications of the MPR metric? Specifically, what are the potential unintended consequences, and how might they be mitigated?\nSuggestion: Expanding the discussion on ethical considerations, including potential risks and mitigation strategies, would offer a more thorough examination of the societal impact of your work.\n\nBy addressing these questions and incorporating the suggested improvements, the paper could provide a more comprehensive and robust contribution to the field.", "limitations": "Assessment:\nThe authors have acknowledged several limitations of their work, including the computational complexity of the algorithm in high-dimensional feature spaces and the need to adapt the MPR metric to other domains like ranking and recommendation systems. They have also recognized the limitations posed by biased datasets. However, there is room for a more detailed discussion on these limitations and their potential negative societal impacts.\n\nSuggestions for Improvement:\n\nComputational Complexity:\nCurrent Acknowledgment: The authors note the computational complexity of the proposed algorithm in high-dimensional feature spaces.\nSuggestion for Improvement: Providing more specific details on the computational requirements, such as time complexity analysis and potential optimizations, would give readers a clearer understanding of this limitation. Including practical suggestions for reducing computational overhead or discussing ongoing work to improve efficiency would be beneficial.\n\nGenerality Across Domains:\nCurrent Acknowledgment: The need to adapt the MPR metric to other domains is mentioned.\nSuggestion for Improvement: Elaborating on the challenges and potential approaches for applying the MPR metric to other domains, such as ranking systems and recommendation engines, would strengthen this acknowledgment. Preliminary experiments or theoretical discussions on these adaptations could provide valuable insights.\n\nDataset Bias:\nCurrent Acknowledgment: The paper mentions the limitations posed by biased datasets.\nSuggestion for Improvement: Conducting a more in-depth analysis of how dataset biases impact the performance of the MPR metric and discussing specific mitigation strategies would enhance this section. Experimental evaluations using biased datasets could provide empirical evidence and insights into this limitation.\n\nEthical Considerations and Societal Impact:\nCurrent Acknowledgment: The paper claims that no ethical considerations remain unaddressed but does not provide a detailed discussion on potential negative societal impacts.\nSuggestion for Improvement: Including a comprehensive discussion on the ethical implications of the MPR metric, such as potential unintended consequences and strategies for mitigation, would provide a more balanced view. Addressing questions like \"Could the MPR metric inadvertently reinforce certain stereotypes?\" or \"What safeguards can be implemented to prevent misuse?\" would be valuable.\n\nBy expanding on these areas, the authors can provide a more thorough examination of the limitations and potential societal impacts of their work. This transparency not only enhances the credibility of the research but also provides a solid foundation for future improvements and applications.", "rating": 9, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Originality:\nNovel Metric: The paper introduces the Multi-Group Proportional Representation (MPR) metric, a novel approach to addressing representational harms in image retrieval tasks. This is a significant advancement over traditional methods that focus on equal or proportional representation without considering intersectionality.\nTheoretical and Practical Contributions: The combination of theoretical guarantees with a practical algorithm for achieving MPR demonstrates a high level of originality. The approach is both innovative in its formulation and effective in its execution.\n\nQuality:\nRigorous Methodology: The paper employs a thorough and well-documented experimental methodology. The numerical experiments are designed to rigorously test the effectiveness of the proposed algorithm against baseline methods.\nStrong Theoretical Foundations: The theoretical underpinnings of the MPR metric are clearly articulated and well-supported, providing a robust foundation for the practical contributions of the paper.\nComprehensive Evaluation: The experimental results are comprehensive and convincingly demonstrate the superiority of the proposed approach, enhancing the overall quality of the research.\n\nClarity:\nClear Writing and Structure: The paper is well-written and logically structured, making it easy to follow the progression of ideas and understand the key contributions. The writing style is clear and concise, facilitating comprehension.\nDetailed Explanations: The authors provide detailed explanations of both the theoretical and practical aspects of their work, ensuring that readers can fully grasp the significance and implementation of the MPR metric.\nContextualization: The paper effectively situates its contributions within the broader context of existing research, clearly delineating how it advances the state of the art in fair and diverse retrieval.\n\nSignificance:\nAddressing a Critical Issue: The focus on representational harms in image retrieval tasks is highly significant, as it addresses a critical issue in AI/ML that has broad societal implications.\nImpactful Results: The results of the study are valuable and impactful, offering a new approach that significantly improves over existing methods. This has the potential to influence future research and applications in the field.\nBroad Applicability: While the paper focuses on image retrieval tasks, the principles and approaches developed could be extended to other domains, increasing the overall significance and potential impact of the work.\n\nOverall, the paper makes substantial contributions across multiple dimensions, demonstrating a high degree of originality, quality, clarity, and significance.", "weaknesses": "Computational Complexity:\nAlgorithm Efficiency: One potential weakness of the paper is the computational complexity of the proposed algorithm. As noted by the authors, the algorithm can be computationally intensive in high-dimensional feature spaces, which could limit its practical applicability in large-scale or real-time systems.\nActionable Insight: Future work could focus on optimizing the algorithm to reduce computational overhead or developing approximation techniques that maintain high accuracy while improving efficiency.\n\nScope of Evaluation:\nLimited Evaluation Domains: The evaluation of the MPR metric is primarily focused on image retrieval tasks. While the results are impressive within this domain, the generalizability of the approach to other domains such as ranking systems, recommendation systems, or text retrieval is not explored in depth.\nActionable Insight: Including preliminary experiments or discussions on how the MPR metric and algorithm could be adapted to other domains would strengthen the paper. Future research could expand the evaluation to demonstrate the broader applicability of the approach.\n\nDataset Bias:\nBias in Datasets: The paper acknowledges the limitations posed by biased datasets but does not delve deeply into how the proposed approach handles or mitigates these biases. The effectiveness of the MPR metric in the presence of inherently biased datasets is an important aspect that needs further exploration.\nActionable Insight: Providing a more detailed analysis of how dataset biases impact the performance of the MPR metric and discussing potential strategies for mitigating these effects would enhance the robustness of the findings. Future work could include experiments with datasets known to have specific biases to assess and address these challenges.\n\nReproducibility:\nDetails on Reproducibility: While the paper discusses the reproducibility of results, providing more explicit details on the implementation and data used could improve the ability of others to replicate the findings.\nActionable Insight: Including supplementary materials such as code, datasets, and detailed implementation steps would significantly enhance the reproducibility of the research. Clearer documentation of experimental settings and parameters would also be beneficial.\n\nEthical Considerations:\nEthical Analysis: The paper mentions that no ethical considerations remain unaddressed, but a more thorough discussion on the ethical implications of the MPR metric and its potential societal impact would add depth to the work.\nActionable Insight: Expanding the discussion on ethical considerations, including potential unintended consequences and mitigation strategies, would provide a more comprehensive view of the implications of the research.\n\nBy addressing these weaknesses, the paper could further improve its robustness, applicability, and overall impact on the field.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer XQou \n\nWe are grateful for your review and positive feedback. We will address each of the weaknesses and questions raised (in a combined way) in detail below. We will be happy to answer any further question.\n\n## Q1. \"Can you provide more details on the computational requirements of the proposed algorithm? Specifically, how does its performance scale with increasing dimensionality and size of the dataset?\"\n\nThanks for raising this --- we will address this point in the updated version of our paper. We provide benchmarks in the table attached to the rebuttal. Our method (MAPR) is competitive with existing fair retrieval methods in terms of runtime. Relative to methods with comparable diversity-similarity trade-offs, such as MMR (see Fig. 1 of the submitted paper), our method has 10x-100x lower computational overhead per query. The one-page additional material includes a table with runtime results for our method and competing baselines. We kindly ask that you refer to the general rebuttal above for more details surrounding the discussion on runtime. \n\nFrom a theoretical perspective, MAPR is actually very efficient when implemented with modern optimization techniques. MAPR minimizes a linear function subject to two linear constraints and iteratively adds MPR constraints, which amount to two additional linear constraints per iteration. The MPR constraint has a closed-form solution in the case of linear functions (Proposition 4, Section 3) or, more generally, an RKHS (Proposition 10, Appendix B.2), allowing us to directly solve a quadratic program with a conic structure, e.g., in the case of linear representation statistic functions. Such quadratic problems can be solved very efficiently with off-the-shelf conic solvers such as OSQP (available in Python). \n\n## Q2. \"How well does the MPR metric generalize to other domains beyond image retrieval, such as text retrieval or recommendation systems?\"\n\nWe believe our approach has significant potential for adaptation to other domains, such as recommender systems and text retrieval. Since we only made use of embeddings of images in all our numerical benchmarks, our method would directly apply to any other setting where a search is performed over vector embeddings, including text retrieval. In this case, we could use our method to ensure a proportional representation of different perspectives, sources, or demographics in retrieved text documents.\n\n## Q3. \"How does your approach address or mitigate the effects of inherent biases in the datasets used? Have you evaluated the MPR performance with datasets known to have specific biases?\"\n\nThe goal of the curated dataset is to use or construct a representative and diverse set *a priori* so that retrieval can be representative. As discussed in lines 162--163 (highlighted in bold) and lines 396--399, if this curated dataset is biased, such biases can propagate in retrieval.\n\nThere may be cases where the retrieval dataset itself is so biased that proportional representation is impossible to achieve (e.g., all images in the dataset over which retrieval is performed are from one demographic group). In such cases, our metric MPR will flag gross deviations in representation relative to a curated dataset.  \n\n## Q4. \"Can you elaborate on the steps taken to ensure the reproducibility of your results?\"\n\nIn the submission, we included an anonymized GitHub [code](https://anonymous.4open.science/r/representational-retrieval-86BB/). We will extend the readme file and create a tutorial for fairness practitioners to easily use our method. In the final version of the paper, we will include the codebase and a more extensive documentation of experimental setups. Moreover, all datasets used in this work are open-source and publicly available.\n\n## Q5. \"The paper mentions that no ethical considerations remain unaddressed, but a more thorough discussion on the ethical implications of the MPR metric and its potential societal impact would add depth to the work.\"\n\nThanks for raising this point. We devote the introduction and much of Section 2 to discussing the ethical considerations of retrieval and MPR. We will expand our ethical discussion to include three critical concepts beyond the amplification of existing bias and misrepresentation of underrepresented groups already mentioned in the paper. First, we will address the potential for a __false sense of fairness__ that the MPR metric might create, emphasizing the importance of critical evaluation even when metrics suggest fairness. Second, we can discuss the __legal and regulatory risks__ associated with relying too heavily on such metrics, particularly in light of evolving anti-discrimination laws. Third, we will add comments about the implications of __skewed decision-making__ that could result from the uncritical application of the MPR metric, highlighting the need for human oversight and contextual understanding. Lastly, we will discuss safeguards such as comprehensive auditing, human oversight, and contextual application.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DSkdopEgLt", "reviewer": "Reviewer_4ELS", "summary": "Authors proposed Multi-Group Proportional Representation, which is a metric to measure representation across multiple intersectional groups (could be many and overlapping) for retrieval. Given a set of representation statistics which quantify group membership in the target groups, MPR measures that group representation in the retrieval dataset approximates that in the wider target distribution. Of all the functions in the representation statistics class, it returns the function most violated. They provide generalization bounds for approximating the target distribution Q with a curated dataset, and provide guidelines for how large of a dataset to curate. They then refactor MPR to be suitable for calculation over a curated dataset. They also propose MAPR, a retrieval framework to relatively efficiently find a retrieval dataset that best performs retrieval while satisfying the MPR constraint.\n\nThe first experimental results compare the ability to achieve similarity while keeping MPR low, showing that their method consistently performs best compared to 4 other methods. They additionally show that their method can provide perfectly proportional representation when given an ideal dataset.", "questions": "A) In Figure 1, the axes are described as \"fraction of\", but I do not find it immediately obvious what this means. Please describe what this means or how it is calculated in more detail, either in the experimental description or figure caption\n\nB) Table 1 shows proportional representation, but there is no mention here of similarity. What is to say that MAPR does not retrieve random samples in the correct group proportions?", "limitations": "This is mostly fine, although the runtime should be discussed / provided in more detail, as pointed out in Weakness B", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "A) Authors effectively take a simple idea and support it with non-trivial error bounds / show evidence towards ideal dataset size\n\nB) Proofs are clear\n\nC) Explanations are clear and professionally presented\n\nD) MAPR provides some algorithmic optimization\n\nE) Problem (intersectional representation) is very important, and providing solutions for this in the retrieval setting shows novelty", "weaknesses": "A) This method is still extremely inefficient. Aside from making it difficult to use in practice, the results are only on 10 queries--this is very few and not great in terms of statistical significance\n\nB) Despite acknowledging that the algorithm is very slow (line 351), there is no concrete analysis presented on runtime.\n\nC) Check out the Proposition labeling in the Appendix--they extend the numbering from the paper rather than referring to which is being discussed\n\nD) In Algorithm 1 line 3, do you mean to say \"arg max a \\in [0,1] n\" rather than m?\n\nE) Table 1 has several presentation / explanation problems. 1) Table 1 is presented first at the top of page 8, but I only see it discussed in lines 377 - 381 -- which is after the discussion from Figure 1, which is shown second. Am I missing something here? It would be clearer if they were presented in the same order as discussed. 2) Is Table 1 only referenced in the Results section starting at line 368? Why not in the Experimental Setup section starting at line 344? It makes it difficult to find where the explanation of the table is.\n\nF) In Figure 1, the colors for Ours and MMR are way too close--it makes it very difficult to distinguish quickly between the fit lines (of course the shapes provide some indication, but more different colors would be much better)\n\nG) in Appendix A line 697, please refer to the equation by its assigned number\n\nOverall, my primary concern is the runtime practicality. As the idea itself is quite simple / straightforward, the contributions would be much stronger if the authors made it reasonable to do this in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer 4ELS\n\nWe thank the reviewer for their careful review and valuable feedback and for raising the issue of the computational efficiency of our method. We have addressed this issue in our response below, in the general remarks above, and in the attached pdf.\n\n## WA/B. \"This method is still extremely inefficient. Aside from making it difficult to use in practice, the results are only on 10 queries--this is very few and not great in terms of statistical significance\". \"Despite acknowledging that the algorithm is very slow (line 351), there is no concrete analysis presented on runtime.\"\n\nPlease note that, on line 351, we are not describing our method but instead the SOTA and most competitive method to ours, the MMR algorithm proposed in [24, 28]. The runtimes reported in Table 1 of the rebuttal pdf demonstrate that MAPR (our method) runs up to 100x faster than MMR.\n\nRelative to other methods that achieve a worse representation-similarity trade-off relative to ours, we achieve competitive runtimes. The exception is DebiasCLIP, which is based on \"debiasing\" CLIP embeddings and thus uses the fast KNN algorithm for retrieval. However, DebiasCLIP was one of the worst-performing methods in our benchmarks. We kindly ask you to refer to our general response for more details on performance relative to the competitors.\n\nFrom a theoretical perspective, MAPR is actually very efficient when implemented with modern optimization techniques. MAPR minimizes a linear function subject to two linear constraints and iteratively adds MPR constraints, which amount to two linear constraints per iteration. The MPR constraint has a closed-form solution in the case of linear functions (Prop. 4, Sec. 3) or, more generally, an RKHS (Prop. 10, Appendix B.2), allowing us to directly solve a quadratic program with a conic structure, e.g., in the case of linear representation statistic functions. Such quadratic problems can be solved very efficiently with off-the-shelf conic solvers such as OSQP (available in Python).\n\n## WC. \"...Proposition labeling in the Appendix--they extend the numbering from the paper rather than referring to which is being discussed.\" \nThank you. We will fix this in the final version of this paper.\n\n## WD. \"In Algo. 1 line 3, do you mean arg max $a \\in [0,1]^n$ rather than m?\"\n Yes, thank you. Fixed!\n\n## WE. \"1) Table 1 is presented first at the top of page 8, but I only see it discussed in lines 377-381 -- which is after the discussion from Fig. 1, which is shown second. ... It would be clearer if they were presented in the same order as discussed. 2) Is Table 1 only referenced in the Results section starting at line 368? Why not in the Experimental Setup, starting at line 344? It makes it difficult to find the explanation for the table\".\n\n1) We wanted Table 1 to be first as an easily-digestible __teaser image__ for the paper. However, given that it comes so late in the paper, we will correct the order to follow the results. \n2) We will elaborate on the setup for Table 1 in the experimental setup section of the final version of the paper by moving up and expanding on lines 377 and 378.\n\n## WF. \"In Fig. 1, the colors for Ours and MMR are way too close--it makes it very difficult to distinguish quickly between the fit lines.\"\n \nThank you for the feedback! We will choose a more visually discernable color palette in the final version of our paper.\n\n## WG. \"in line 697, please refer to the equation by its assigned number\" \nWe will do so -- apologies for the confusion. We will use the correct label instead of saying \"third equation\" and \"fourth equation\" in Prop. 8.\n\n## QA. \"In Figure 1, the axes are described as \"fraction of\", but I do not find it immediately obvious what this means.\" \nThank you for the question. The axes show normalized values that allow comparison across different queries. In this fig.:\n\n1. $y$-axis (Similarity): The mean cosine similarity between the query embedding and retrieved image embeddings for $k$ retrieved images, divided by the maximum possible similarity given by the top-$k$ nearest neighbors of a query.\n\n2. $x$-axis (Representation): The multi-group proportional representation (MPR) score, divided by the MPR score of the top-$k$ nearest neighbors.\n\nThis normalization places the $k$-NN baseline (1,1) for all queries, allowing consistent comparison against the $k$-NN baseline where no fairness intervention is used. The ideal operation point of perfect representation and maximum similarity would be (0,1). We apply this normalization since, for each different query of the form \"A photo of a [query],\" the mean cosine similarity and the MPR values achieved by $k$-NN changes. This graph allows us to visualize how the MAPR algorithm and competing baselines trade off similarity and representation as it moves away from the vanilla $k$-NN retrieval. The unnormalized case would require different graphs for different queries since mean (cosine) similarity and MPR scores would be query-dependent. We will include this explanation in the experimental setup of the paper.\n\n## QB. \"Table 1 shows proportional representation, but there is no mention here of similarity. What is to say that MAPR does not retrieve random samples in the correct group proportions?\"\n\nIn these experiments, we pick the lowest-MPR values achieved by MAPR (e.g., the leftmost point on the curves traced in Fig 1.). Intuitively, the sets reported in the table are the most similar set of items possible that satisfy the minimum-achievable MPR by MAPR. Because MAPR optimizes for similarity subject to an MPR constraint, in Table 1 (see also Table 3 in Appendix D), MAPR isn't retrieving random samples but rather the most similar ones while still balancing group attributes. This is highlighted in Fig. 1, where MAPR Pareto-dominates competing methods in terms of MPR and preserved similarity. Nevertheless, **we report the similarity of the retrievals used to create Table 1 in Table R2 in the attached pdf.**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
# General rebuttal

We sincerely thank the reviewers for their thorough assessment of our paper. We appreciate their recognition of our work's contributions to the critical challenge of fair retrieval, particularly in addressing *intersectional representation* (reviewer 4ELS). We are pleased that the reviewers noted the solid theoretical foundations of MPR (reviewers XWMb and XQou), including our non-trivial generalization bounds and sample complexity results (reviewer 4ELS). The reviewers noted that our *proofs are clear* and our *explanations are clear and professionally presented* (all reviewers). It also is encouraging to see that they recognized how we *effectively take a simple idea and support it with non-trivial error bounds and show evidence towards ideal dataset size* (reviewer 4ELS). We respond to common reviewer comments below, as well as in our response to each reviewer.

**Computational complexity and runtime.** TL;DR: our method (MAPR) is competitive with existing fair retrieval methods in terms of runtime. Relative to the method with the most comparable diversity-similarity trade-offs (MMR, see Fig. 1 of the submitted paper), MAPR has a lower computational overhead per query (up to 100x smaller). A table with runtime results for our method and competing baselines is included in the 1-page additional material. We provide details next.

The sole technical question about our paper was the computational complexity and runtime of our algorithm (MAPR).  We provide runtime results for variations of MAPR, MMR [27], PBM [29], clipCLIP [18], and DebiasCLIP [20].

We benchmark three variants of MAPR:
1. The linear program (LP) solved with the cutting-plane method with 10 cuts (Alg. 1).
2. The same LP but solved with 50 cuts.
3. The quadratic program (QP) that comes from the setting when the family of functions $\mathcal{C}$ is given by the set of bounded-norm linear regressions (and for which we have a closed-form solution for MPR, e.g., Thm 4 and Sec. B.1).

Results for each variant of MAPR are included in Table R1 of the attached PDF. We analyze these results below.

First, we note that ClipCLIP and DebiasCLIP modify the CLIP embedding and then run a vanilla k-NN retrieval. DebiasCLIP has the lowest runtime of all methods we benchmarked since it uses a frozen "debiased" embedding model and does not require any modification of the retrieval algorithm. ClipCLIP has a slight computational overhead where CLIP embedding is modified at retrieval time. Despite these favorable runtimes, __neither of these methods is competitive to MAPR (ours) in terms of diversity-similarity trade-off__ (see results in Figure 1 in the paper). ClipCLIP and DebiasCLIP also do not offer any formal guarantee on the diversity of retrieved items.

PBM also achieves competitive runtime relative to MAPR.  However, unlike our method, PBM is limited to a single binary attribute and aims for equal representation and not for general proportional representation. While efficient for binary attributes (with runtime slightly better than the QP variant of MAPR), PBM also achieves a worse similarity-diversity trade-off relative to MAPR across all of our experiments (Table 1). 

The method most competitive to ours in terms of diversity-similarity trade-off is MMR (see Fig. 1),  used in [24, 28] for achieving representation in retrieval. However, MMR is a greedy algorithm and scales poorly with the number of retrieved items. Consequently, MMR's runtime is up to 100x slower than ours (MAPR). In contrast, our method, MAPR, enjoys theoretical guarantees while achieving a significantly more favorable runtime, particularly when implemented using the closed-form quadratic program for linear models (see Prop. 4 and Appendix B.1). 

From a theoretical perspective, MAPR is actually very efficient when implemented with modern optimization techniques. MAPR minimizes a linear function subject to two linear constraints and iteratively adds MPR constraints, which amount to two additional linear constraints per iteration. In case the MPR constraint has a closed-form solution, e.g., linear functions (Proposition 4, Section 3) or, more generally, an RKHS (Proposition 10, Appendix B.2), we solve a one-shot quadratic program with a conic structure. Such quadratic problems can be solved very efficiently with off-the-shelf quadratic or conic solvers such as OSQP or ECOS (available in Python). Here, the worst-case complexity for interior-point methods solving a quadratic program involved in retrieving $k$ items is typically $O(k^{3.5})$. However, solvers like OSQP work really well with the constraints that we have (such as box constraints), achieving $O(k^2)$ complexity per iteration with a relatively small number of iterations in practice. We observe that OSQP takes only a few iterations (around 30) to find the optimal solution described in Table 1.

Meta-review: The paper proposes Multi-Group Proportional Representation (MPR) as a novel metric to ensure diverse and proportional representation across intersectional groups in image retrieval tasks. The authors demonstrate the limitations of current methods in addressing intersectional fairness and introduce an optimization algorithm, MAPR, to enforce MPR while minimizing retrieval error. They provide theoretical guarantees, extensive empirical validation, and address challenges related to biased datasets.

The paper addresses the problem of ensuring fairness across multiple, intersecting groups, which is often overlooked. Despite its computational challenges, the method is novel, theoretically sound, and backed by strong empirical results. The potential societal impact of the proposed solution makes it a valuable contribution to the field, particularly in applications involving image retrieval and other tasks requiring equitable representation. As such, the AC recommends acceptance to NeurIPS.
Decision: Accept (poster)