Multi-Group Proportional Representation in Retrieval

Authors: alex  oesterling
claudio  mayrink verdun
carol xuan long
alexander  glynn
lucas monteiro paes
sajani  vithana
martina  cardone
flavio p calmon
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 21:52:40

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.

Main paper: 
 introduction: 
 A recognized objective in fair machine learning (ML) is discovering, reporting, and mitigating representational harms [1] [2] [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] [5] [6] . These harms often manifest through the biased portrayal or misrepresentation of 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 in ML are not geo-diverse [9] , and generative models can output images that under-represent demographic minorities across gender and racial identities [10] [11] [12] .We focus on representation in 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 et 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 is 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. In particular, among other findings, this study showed that when a qualifier such as "intelligent" is added to the query "person", the engines still exhibit a significant gender discrepancy; see also [1, Chapter 7] . When 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] [19] [20] , as well as propagating spurious correlations from the dataset more broadly [21] or distorting results due to stereotypes present in 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-language embedding models such as CLIP [23] used for retrieval. Bias in embeddings can lead to bias in retrieval [24] [25] [26] . In fact, recent work by Srinivasan et al. [27] argues that many image retrieval systems lack "social diversity" as 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, 31] , 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 fairness interventions typically consider only a small number of pre-defined groups. Ensuring representation 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 is rooted in work in law and the social sciences [32] [33] [34] and has been a 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 representation 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 a reference population whose representation we aim to match. The set of representation statistics is given by a function class C, where each function c ∈ C maps a retrieved item x to a real number. For instance, c(x) ∈ {-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 or 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 subgroups. Compared to naively counting the number of retrieved items across a (potentially exponential) number of pre-defined groups, MPR offers a 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, an algorithm that retrieves items from a 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. Related Work. Broadly speaking, existing work on fair and diverse retrieval with pretrained embeddings either: 1) modifies the embedding space to prioritize downstream fairness, or 2) provides retrieval algorithms optimizing for diversity or fairness.Mitigating Bias in Embedding Space. Various approaches have been proposed to produce vector embeddings of text and images that target diversity or mitigate bias. These include modifying loss functions to encourage group fairness [41] , adversarial training [42, 43] , 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-processing methods for fairness have also been developed for multimodal models such as CLIP [23] , including CLIP-clip [18] , CLIP-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 a linear combination of similarity and diversity metrics. Celis et al. [30] and Celis and Keswani [31] focus on diversity and fairness in image retrieval, using a 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 a 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-based 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 peoplerelated 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 if 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 a rigorous approach to measuring representation across complex, intersectional groups defined by a rich class of functions. However, as with any fairness metric, MPR has limitations -see Section 6 -and may not always align with human perceptions of representation. In particular, we underscore the importance of involving stakeholders in defining representation goals and auditing retrieval systems.Multi-Group Fairness. Our work is 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] [52] [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 multi-group representation in retrieval rather than multi-group fairness in classification and regression.Multi-Attribute Proportional Representation. A recognized challenge in computational social choice research is building committees, groups, or sets of items that ensure proportional representation across several attributes [56] [57] [58] [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 goals, our MPR metric takes a different approach by measuring the worst-case deviation over computationally-identifiable groups defined by a function class C. This formulation connects naturally with statistical learning theory through MMD [60] and sample complexity bounds (Propositions 1 and 2). Though we use the term multi-group rather than multi-attribute to emphasize connections with the burgeoning literature on multi-group 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 to match retrieved candidates to a 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, an important context for our work. We briefly discuss these connections in Appendix E. There, we elaborate on how our approach relates to and differs in terms of representation formulation from [37] . 
a multi-group proportional representation metric: 
 Preliminaries. Consider a retrieval dataset of items from which we aim to retrieve relevant entries, denoted by D R = {x r 1 , ..., x r n }. We assume that x r i ∈ R d × G, where G is a set of additional labels for each item. For example, items x r i can be d-dimensional embeddings of images, videos, or textual content, in which case G = ∅. Alternatively, x r i = (e i , g i ), where e i ∈ R d is an embedding and g i is a vector of labels indicating group membership (e.g., gender, race, ethnicity).Given a query embedding q ∈ R d , the goal of retrieval is to search and return the top-k most similar items to q in D R . The similarity between an embedding of q and items in D R is measured according to a metric κ : R d × R d → R. Throughout the paper, we assume that D R is a vector database and κ is cosine similarity between embeddings, though this formulation can be generalized. To retrieve items from D R , users prompt a query q (e.g., "Fortune 500 CEOs") which is then embedded R d . Ideally, the user receives k retrieved items R(q) = {x r 1 , ..., x r k } ⊂ D R such that κ(q, x r i ) ≥ κ(q, x) for all x / ∈ R(q) and i ∈ [k].The simplest setting for measuring representation is to consider only two population groups denoted by a binary variable -a 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 : R d × G → {-1, 1}. For an item x r i , c(x r i ) indicates membership to group -1 or 1 (e.g., male/female) based on its embedding e i and associated labels g i . If the retrieval dataset D R contains annotations for group membership, c(x r i ) can simply return the relevant feature from g i . However, when group labels are not present (i.e., G = ∅), c(x r i ) can be implemented as a classifier that predicts group membership based on the item's embedding e i .With a group-denoting function c(x r ) in hand, we can measure the representation of each group in a 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 is approximately the same, i.e., 1 k x r ∈R(q) c(x r ) ≈ 0. An alternative metric is proportional representation [20, 61] , which quantifies the deviation of group membership from a reference distribution Q. Methods that promote proportional representation aim to ensure1 k x r ∈R(q) c(x r ) ≈ E Q [c(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, E Q [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 uniformly distributed over a given population. Naturally, the choice of distribution Q is application and context-dependent -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 a single group-denoting function c(x r ), we consider a class of Q-measurable functions, the representation statistics class, C ⊂ c : R d × G → R . This set C may represent multiple, potentially uncountable overlapping groups. We formally define multi-group proportional representation next. Definition 1. For a reference representation distribution Q, a set of Q-measurable set of representation statistics C, and a set of k retrieved items R, we define the Multi-Group Proportional Representation (MPR) metric asMPR(C, R, Q) ≜ sup c∈C 1 k x r ∈R c(x r ) -E Q [c(X)] . (1) A set of items R is (C, ρ)-multi-group proportional representative of Q if MPR(C, R, Q) ≤ ρ.The MPR metric quantifies the "representativeness" of a rich class of statistics, denoted by functions in C, within a set of retrieved items R. This generalization is crucial for capturing intersectional groups. [60, 62] and are used in hypothesis testing for comparing distributions. MMD is a 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 a "computationally identifiable" class of functions C is directly inspired by the multi-group fairness in classification literature, and we adopt similar notation (i.e., c 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 E Q [c(X)] for each group c ∈ 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 D R 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 a probability distribution over R d × 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 D C ≜ {x c 1 , ..., x c m }. We denote the MPR of a set of retrieved items R relative to the empirical distribution over D C as MPR(C, R, D C ).Constructing a proper D C is critical to properly measuring bias and preventing downstream harms, and the nature of D C 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 used for MPR measurements be developed and verified through participatory design approaches [66, 67] in collaboration with diverse stakeholders. By involving stakeholders in 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 a query q, we can retrieve relevant samples from both the curated dataset D C and the retrieval dataset D R . The samples retrieved from D C can then serve as a "conditional" curated dataset, denoted as D C|q , 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, we introduce theoretical guarantees and algorithms that are agnostic to the specific choice of D C . 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. 
computing multi-group proportional representation: 
 Computing MPR in Defnition 1 requires approximating two quantities: the representation distribution Q and the supremum sup c∈C . We first establish generalization bounds for approximating Q using i.i.d. samples. We then show how to compute sup c∈C for several classes of representation statistics C.Error in approximation Q via a curated dataset. Proposition 1, proved in Appendix C, bounds the deviation between the empirical MPR computed over the curated dataset D C drawn i.i.d. from reference distribution Q and the true MPR measured over Q. Proposition 1 (Generalization Gap of MPR). Let R(q) = {x r i } k i=1 be a set of k retrieved samples,EQUATIONWe can extend Proposition 1 to any set of bounded functions C (see, e.g., bounds on empirical MMD estimates in [60] ). Note that the guarantee in (2) EQUATIONthen, with probability at least1 -δ, |MPR(C, R, D C ) -MPR(C, R, Q)|≤ ϵ.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 D C 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 2 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 D C of size m. We consider four specific instantiations of the set of representation statistics C: (i) C is closed under scalar multiplication, i.e., if c ∈ C, then λc ∈ C for any λ ∈ R, (ii) C is a set of functions taking values in {-1, 1}; (iii) C consists of linear functions; and (iv) C 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 to 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 multiplication or consists of binary functions with values -1, 1, MPR can be expressed as an MSE minimization. This enables us to 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 as an MSE minimization is that MPR can be formulated as a maximum correlation problem. Consider the (row-wise) concatenation of the retrieval dataset D R and the curated dataset D C , given by X ≜ [x r 1 , ..., x r n , x c 1 , ..., x c m ], where x i is the i-th entry of X. For the remainder of this section, we consider a fixed set of retrieved items R. Let a ∈ {0, 1} n be a vector indicating items that are retrieved from D R for a given query, i.e., a i = 1 ⇔ x r i ∈ R. Under this notation, where retrieved items are indicated by the vector a, MPR can be reformulated asEQUATIONwhere a ∈ R n+m has i-th entry given by a i ≜ 1 i≤n ai k -1 i>n 1 m . This reformulation will be useful for explicitly casting MPR-constrained retrieval as an optimization problem.When C consists of binary functions in range {-1, 1}, MPR is equivalent to regression over C of a under quadratic loss, sinceEQUATIONThe absolute value in ( 4) can be recovered by regressing -a instead of a.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 a 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 to a 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 a cutting-plane-based algorithm for ensuring MPR in retrieval called MOPR.EQUATION)let ĉ : X → R be defined as ĉ(x) = √ mk/(m+k) ∥c * (X)∥2 c * (x). Then, we have thatEQUATIONComputing MPR for Bounded-Norm Linear Regression. Recall that each item in the retrieval or curated datasets is of the form x i = (e i , g i ), where e i is an embedding and g i are labels. When x i ∈ R l (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 a closed-form expression, as stated in the next proposition. Proposition 4. Let items in the retrieval and curated datasets be vectors in R l for l < m + n andC = x → w ⊺ x | w ∈ R k .Moreover, let X ∈ R (m+n)×l be the matrix formed by concatenating items in the retrieval and curated dataset D R and D C , respectively. For C ′ in Proposition 3, we haveEQUATIONAlgorithm 1 MOPR (Multi-group Optimized Proportional Retrieval)Input: DR, query q, number of iterations T , number of items to retrieve k, MPR constraint ρ, Oracle(a) that computes solves (4) and returns c ∈ C that approximates the sup.1:C ← ∅, si = κ(x r i , q) 2: for iter ∈ {1, 2, ..., T } do 3: a ← arg max a∈[0,1] n a ⊺ s subject to 1 k n i=1 aic(x r i ) -1 m m i=1 c(x c i ) ≤ ρ for c ∈ C 4:(mpr_violation, c) ← Oracle(a) ▷ Solve (4) 5:if mpr_violation ≤ ρ or iter = T then 6: return R ← {x r i ∈ DR corresponding to k largest entries of ai} 7: else 8:C ← C ∪ {c} 9:end if 10: end for where X = UΣV ⊺ is the SVD of X and U l ∈ R (m+n)×l are the left singular vectors in U corresponding to the top-l largest singular values. 1Proposition 4 can be directly adapted to linear functions defined only over embeddings or a 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.1. 
promoting multi-group proportional representation in retrieval tasks: 
 We develop an optimization framework for retrieving the k most similar items in a vector database to a given query q while satisfying a target MPR threshold of ρ. We formulate the retrieval goal as maximizing the average similarity between a query and retrieved items, given by s i = κ(x r i , q) (recall Section 2 for notation), where κ(x r i , 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:EQUATION)When C is given by normalized linear functions as in Proposition 4, the integer constraints can be relaxed to a ∈ [0, 1] n 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 Optimized Proportional Retrieval Algorithm (MOPR), described in Algorithm 1. MOPR is essentially a cutting-plane method that aims to find a set of k items that maximize utility while approximately satisfying an MPR constraint of ρ. The algorithm iterates between (i) a call to an oracle that computes MPR and returns a function c ∈ C that achieves the supremum in ( 4) and (ii) a call to a 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 LP 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} n . In 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 a 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 ρ. However, the method can fail to accurately approximate the IP solution when ρ is small. We present a more detailed analysis of MOPR in Appendix D, which discusses potential convergence issues with the cutting plane method as well as stopping conditions.  
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 D C balanced over all attributes and for proportional representation using FairFace [39] as the curated dataset D C , since it is a 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 i and a set of labels g i .Benchmarks. We compare our method with four baselines. DebiasCLIP [20] modifies text queries with a prepended learned embedding for debiased retrieval but does not allow for tunable control of the representation-similarity trade-off, so it only results in a single retrieval set over which we compute similarity and MPR. CLIP-Clip [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. PBM [29] post-processes CLIP embeddings to mitigate bias by predicting gender attributes and subsampling from each gender equally. PBM also allows tuning the representation-similarity tradeoff by controlling the likelihood of sampling at random or in a balanced manner from the retrieval dataset. Finally, the state-of-the-art for fair retrieval first constructs PATHS embeddings [27] , which use a set of adjective-noun keywords to capture a broad set of identity vectors in vision-language 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. We refer to this method as MMR. For a detailed discussion of these algorithms and their approaches to representation, see Appendix E.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 as the query-conditioned curated dataset D C . One reason we first filter for the top 10k items is the runtime of MMR, which is a greedy algorithm that traverses the full dataset for each retrieval k (even for 10k entries and k = 50 retrieved items, MMR takes hours to run for 10 queries).In order to evaluate representation over interpretable population groups, we consider that representation statistics C are computed only over labels g i given in FairFace. These labels are not present in all retrieval datasets. Thus, for CelebA and Occupations, we train linear probes on FairFace's CLIP embeddings to predict their race and age attributes, and when using UTKFace, we map from FairFace's race labels to UTKFace's race labels by mapping Southeast Asian and East Asian to Asian and Middle Eastern and 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, we acknowledge that these are 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 a parameter sweep over ρ 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) on each graph, and each point measures the fraction of Top-k MPR and similarity.Results. In Fig. 1 we report results for proportional representation for the query "A photo of a 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] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] . We observe that MOPR Pareto-dominates benchmark methods, and is able to preserve similarity while reaching lower levels of 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 a 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 to 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 UTKFace, 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 us to evaluate the performance of MOPR in achieving equal representation. We conduct a 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 equally-balanced 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 a 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 a 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-fairness trade-off compared to existing fair retrieval algorithms.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 1, 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-Hoc 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, in 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.It is important to 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"-where 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. As 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 if not conducted properly.Our aggregate results (e.g., Table 1 ) should be approached with caution, as each MPR-similarity curve is sampled from a different distribution of data conditioned on 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 a given query. Second, while MPR is designed to handle a large number of groups, the computational complexity of the proposed cutting-plane algorithm in the case of a 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. 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.The creation and selection of curated datasets must carefully account for stakeholder interest and target representation statistics. 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 ML 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.We start by proving Proposition 1 from Section 3 which bounds the error in MPR estimates when Q is approximated via a curated dataset D C . We do so by using tools from standard Rademacher complexity results in statistical learning theory, e.g., [72] . See also [73, Chapter 4] . We restate the theorems here to facilitate readability. We start with a lemma about the difference of suprema.Lemma 1. Let P and P ′ be two distributions over X and C = {c : X → [0, 1]}. ThenEQUATIONProof.supc∈C E P [c(X)] -sup c∈C E P ′ [c(X)], = sup c∈C {E P [c(X)] -E P ′ [c(X)] + E P ′ [c(X)]} -sup c∈C E P ′ [c(X)],≤ supEQUATIONProof. First, note thatEQUATIONEQUATIONEQUATIONEQUATIONWhere (13) comes from Lemma 1 and (15) comes from the triangular inequality.Additionally, by switching MPR(C, R, Q) by sup c∈C (11) and repeating the previous argument, we conclude that:1 k k i=1 c(x i ) -E Q [c(X)] inEQUATIONTherefore, from ( 16) we showEQUATIONEQUATIONEQUATIONhere (19) comes from the generalization bound using Rademacher complexity from [72] and the fact that c(x) 2 ∈ [- EQUATIONthen, with probability at least1 -δ, |MPR(C, R, D C ) -MPR(C, R, Q)|≤ ϵ.Proof. First, recall that the Rademacher complexity R m (C) is upper bounded by the VC-dimension of C by the relationEQUATION)where e is Euler's number.Denote the samples retrieved for a given query q by R(q) = {x r i (q)} k i=1 . From Proposition 1 we have that for all δ *  |MPR(C, R, D C ) -MPR(C, R, Q)| ≥ R m (C) + log 2 δ * 8m   ≤ δ * .Therefore, using the previous equation if we take δ * = δ M and denote R(q) = R we have thatEQUATIONHence, we have that, with probability at least 1 -δ for all q ∈ Q supEQUATIONEQUATIONWhere the inequality in (23) comes from the upper bound in (20) .EQUATIONthenEQUATIONAs described in Section 3, such bounds tend to be conservative and these bounds can be improved by doing a 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 as scikit-learn [69] .EQUATIONlet ĉ : X → R be defined as ĉ(x) = √ mk/(m+k) ∥c * (X)∥2 c * (x). Then, we have thatEQUATIONProof. We begin proving 0 ≤ MPR(C ′ , R, D C ) ≤ 1,. As a shorthand, let c(X) = [c(x 1 ), ..., c(x n+m )]. The Cauchy-Schwarz inequality gives,EQUATIONwhere X ∈ R (m+n)×l is the matrix formed by the row-wise concatenation of D R and D C and a is the vector [ a 0 , ..., a m+n ]. C ′ gives us a constraint on the norm of c(X), and we can compute a given there are k terms with value 1/k, m terms with value 1/m, and n -k terms with value 0. Also noteEQUATIONNext, we prove the second statement. Consider the minimizer of the MSE problem,EQUATION)As C is closed under scalar multiplication, we can equivalently write this a two-part optimization problemEQUATIONwhere the inner optimization is quadratic and yields a solutionEQUATIONas ∥c(X)∥ 2 < ∞. Plugging this back into Equation ( 29), the MSE problem becomesarg inf c∈C n+m i=1 ( n+m i=1 c(x i ) a i ∥c(X)∥ 2 2 c(x i ) -a i ) 2 , = arg inf c∈C n+m i=1 ⟨c(X), a⟩ 2 ∥c(X)∥ 4 2 c(x i ) 2 -2 ⟨c(X), a⟩ ∥c(X)∥ 2 2 c(x i ) a i + a 2 i , = arg inf c∈C ⟨c(X), a⟩ 2 ∥c(X)∥ 4 2 ∥c(X)∥ 2 2 -2 ⟨c(X), a⟩ ∥c(X)∥ 2 2 ⟨c(X), a⟩ + n+m i=1 a 2 i , = arg inf c∈C - ⟨c(X), a⟩ 2 ∥c(X)∥ 2 2 + n+m i=1 a 2 i .As a i does not depend on c, this optimization is equivalent toarg sup c∈C ⟨c(X), a⟩ 2 ∥c(X)∥ 2 2 = arg sup c∈C |⟨c(X), a⟩| 2 ∥c(X)∥ 2 2 .Note that the supremum can be multiplied by a constant. Then we can multiply by some ∆ > 0 and getEQUATION)In other words, for ∆ > 0 andc * ∈ arg sup c∈C |⟨c(X), a⟩| 2 ∥c(X)∥ 2 2 ,and letting ĉ : X → R be defined as ĉEQUATIONLetting ∆ = mk m+k , we can conclude that solving an MSE regression problem is equivalent to finding the representation statistic for MPR. Now, we establish Proposition 4, restated below for convenience. It says that MPR enjoys a closedform expression whenever the class C is 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 4. Let items in the retrieval and curated datasets be vectors in R l for l < m + n and C = x → w ⊺ x | w ∈ R k . Moreover, let X ∈ R (m+n)×l be the matrix formed by concatenating items in the retrieval and curated dataset D R and D C , respectively. For C ′ in Proposition 3, we haveEQUATIONwhere X = UΣV ⊺ is the SVD of X and U l ∈ R (m+n)×l are the left singular vectors in U corresponding to the top-l largest singular values. 3The closed-form expression for MPR in (8) allows MPR-constrained 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 We can use the method of Lagrange multipliers. Let us define the Lagrangian function:C ′ ≜ {c ∈ C | m+n i=1 c(x i ) 2 = mk m+k }, where C = x → w ⊺ x | w ∈ R d ,EQUATIONTo find the optimal solution, we set the partial derivatives of the Lagrangian with respect to w, w, λ, and µ to zero:EQUATIONEQUATIONEQUATIONEQUATIONFrom ( 42), we have VΣµ = 0. Assuming V and Σ are full rank, this implies µ = 0. Substituting this into (39), we get:EQUATIONUsing (43) and the constraint ∥ w∥ 2 2 = mk m+k , we can solve for λ:EQUATIONSince we are maximizing z T w, we choose the positive value of λ. Thus, the optimal w is:EQUATIONFinally, using (45) , we can find the optimal w:EQUATION)The optimal w is then obtained by solving the linear system ΣV ⊺ w * = 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 l in our original SVD as U ∈ R (m+n)×l , so we can truncate the vectors in the null space of U.max w∈R m+n a T UΣV ⊺ w = a T U l ΣV ⊺ mk m+k ∥z∥ 2 (ΣV ⊺ ) -1 U ⊺ l a = mk m+k ∥U ⊺ l a∥ 2 a T U l U ⊺ l a = mk m + k ∥U ⊺ l a∥ 2In this section, we discuss the convergence of MOPR, the Multi-group Optimized Proportional Retrieval algorithm. As described in Section 4, the MOPR is essentially a cutting plane method (also known as the Kelley-Cheney-Goldstein method [78, 79] ) applied to the linear function a T s; see also [80] .The algorithm begins by identifying the k-most similar items to a given query in D R . Then, an MSE-minimizing oracle is called and returns the statistic (or group-denoting function) c ∈ C with the most disproportionate representation for the set of retrieved items. The function c is then added as a constraint to a linear program that outputs a vector a ∈ [0, 1] n maximizing average similarity as in (9) subject to a single constraint1 k i = 1 n a i c(x r i ) -1 m m i=1 c(x c i ) ≤ ρ, where integer constraints are relaxed. The optimal a is rounded so only the largest k entries are marked as 1, corresponding to a new set of retrieved items. The process repeats with an increasing number of constraints to the linear program and halts when the oracle does not return a function that violates the target MPR constraint ρ. In mathematical terms, we start by solving the problemmax a∈{0,1} n a ⊺ s (47) subject to k i=1 a i = k.Note that the solution to this problem is given by the vector a that finds the kth largest entries of s, i.e., it identifies the k-most similar items to a given query in D R . Then, Proposition 3 provides a way to generate cuts given the vector a k ∈ R n found as a solution of the previous iteration. These cuts are given by the function c ∈ C with the most disproportionate representation for the set of retrieved items.At each iteration, we test if the MPR constraint, less or equal to ρ, is satisfied. If not, this gives us a new inequality to be incorporated into the linear problem (D) that outputs a vector a ∈ [0, 1] n maximizing average similarity as in (9) subject to a single constraint1 k n i=1 a i c(x r i ) -1 m m i=1 c(x c i ) ≤ ρ, where integer constraints are relaxed. Therefore, the algorithm consists of iteratively adding a new constraint (cut) of the formEQUATIONand solving the problem again until all the inequalities are fulfilled, i.e., until the oracle does not return a function that violates the target MPR constraint ρ. At this point, the algorithm halts. It 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.,EQUATIONThe next proposition links the oracle via MSE, described in Proposition 3, with the subdifferential of the function G(a). EQUATIONIn fact, starting from the left-hand side leads to|g(a * , c * )|+ sign(g(a * , c * ))c ⊺ (a -a * ) = |c ⊺ a + b c |+ c ⊺ a + b c |c ⊺ a + b c | c ⊺ (a -a * ) = |c ⊺ a + b c |+ c ⊺ a + b c |c ⊺ a + b c | -c ⊺ a * -b c * + c ⊺ a + b c * = |c ⊺ a + b c |- |c ⊺ a + b c | 2 |c ⊺ a + b c | + sign(g(a * , c * ))(c ⊺ a + b c * ) ≤ |c ⊺ a + b c * |≤ G(a), ∀a ∈ R n This shows that c = [c * (x 1 ), . . . , c * (x m )] is a 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 * ) + g * ⊺ (a -a * ) ≤ ρ (51) to the problem at each iteration until the solution satisfies all the inequalities. This reformulation demonstrates that the MOPR algorithm can be viewed as a traditional cutting plane method for minimizing a linear function over the polyhedron P = {a i ∈ [0, 1] ∩ n i=1 a i = k}. 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 to exist due to 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] .However, it is important to note that even when the algorithm terminates in a finite number of steps, the cutting plane method often requires a substantial number of iterations to 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 of this paper. For further information on these topics, refer to [82, 83] and the references therein.The integer program may not be as scalable as its convex relaxation. If we relax it to a i ∈ [0, 1], this becomes a convex optimization problem solvable by standard methods (even for very large C) and provides an upper bound to the original program for reasonable values of the MPR violation (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 i , 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 a i are 0 or 1), in which case it is also an optimal solution for the original problem. This is the case, for example, when the constraint matrix is 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 i 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 ). "chef", "nurse", "artist", "lawyer", "teacher", "engineer", "architect", "scientist", and "programmer". max a,y a ⊺ s (52)subject to mk m + k ∥U ⊺ l a∥ 2 ≤ ρ, a ⊺ 1 = k, a i ∈ {0, 1},where a ∈ R n+m has i-th entry given by a i ≜ 1 i≤n ai k -1 i>n 1 m . This result allows us to explore the efficiency of the cutting plane algorithm in MOPR by comparing it to the solution to (52) , which is a closed-form, convex quadratic program that can 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 to get a solution in {0, 1} n 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 4 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 4. As we can see, while the quadratic program traces a smoother curve, MOPR's cutting plane approach well-approximates the closed form solution. In these experiments, we retrieve 50 items from CelebA, without a curation set. Finally, in Figures 5 and 7 , we run MOPR with the quadratic program oracle and compare our measurement of MPR with the closed form solution and linear regressor-approximated 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 5 and 7 measure the quality of our MSE estimator of MPR in comparison to the perfect oracle. We observe that the MSE oracle is a perfect approximator of the closed form for MPR, as expected. Kernel methods are a generalized but practical, non-linear, and easy technique to implement algorithms for a 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 a reproducing kernel Hilbert space, which includes, for example, linear regression, logistic regression, Gaussian kernel ridge regression, and hard-margin SVMs. Proposition 6 (MPR for RKHS [60] ). Let {x r i } k i=1 be retrieved samples R and {x c i } m i=1 the samples from the curation dataset D C . Let C be a reproducing kernel hilbert space with kernel K(., .), thenEQUATIONTherefore, given a kernel K(., .), we can easily compute MPR(C, R, Q) by evaluating the kernel at the points x r i , x c j and use this in Algorithm 1. ) and MOPR over queries "chef", "nurse", "artist", "doctor", "teacher", "engineer", "architect", "scientist", and "programmer". : Additional comparisons of MSE to closed form MPR estimator for queries "chef", "nurse", "artist", "doctor", "teacher", "engineer", "architect", "scientist", and "programmer". In this section, we describe the methods we benchmark against that aim to promote fairness multimodal models like CLIP [23] . We also briefly overview proportional representation in 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 a 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 are dropped from both the text and image embedding, resulting in less bias (at cost to the fidelity of the embedding).By varying the number of features dropped, a recall-bias trade-off is induced.• CLIP-debias (Berg et al. [20] ): The algorithm learns a series of tokens that are 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-Hoc Bias Mitigation ( [29] ): Post-Hoc Bias Mitigation is a post-processing method that relies on an 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 a set of elements (one of each predicted sensitive attribute) or a 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 to extract an embedding that captures complex notions of diversity in people, upon which a diverse retrieval method (such as the MMR method detailed above, or even MOPR) can be run to effectively increase the diversity of the returned samples.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 a long history in social choice theory and political sciences [88] [89] [90] [91] [92] and has been a 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 fundamental voting methods and paradoxes that continue to influence modern computational approaches. During this same period, early proponents of proportional representation emerged, such as 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 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'Hondt, and John Stuart Mill further explored and contributed to the discussion of proportional representation in the political science literature. The field was revolutionized in the 20th century by Kenneth Arrow's seminal work, whose impossibility theorem fundamentally shaped our understanding of social choice mechanisms. See [88] [89] [90] [91] [92] .Similarly, in ML, 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 to handle more complex scenarios. As mentioned at the end of Section 1, a notable contribution in this direction is the work of Lang and Skowron [37] , who introduced multiattribute 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 {t 1 , ..., t m } (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 approach 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 C 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-value pair (like the Hamilton method; see Definition 5 in [37] ) but also complex nonlinear relationships (like 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-attribute committee selection, our framework offers a more general approach suitable for modern retrieval systems where both representation and relevance matter.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 DebiasCLIP 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 1 and 5 . These similarity scores can be 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 to the query.Second, we include full tables of intersectional retrieval performance on UTKFace for our method, Top-k, MMR, CLIP-Clip, 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 to 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-MPR tradeoff curves for the other 9 queries not reported in the main paper (Figs. 8,9,10), as well as for all 10 queries on two additional models: a decision tree (Figs.11, 12, 13) and with an MLP with 1 hidden layer of dimension 64 (Figs. 14, 15, 16) . We observe a similar Pareto-domination to 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 is still unable to decrease MPR as low as MOPRis able to at ≈ 95% of top-k similarity.We also include results for an additional 45 queries for the Occupations dataset (with FairFace as the curation dataset), as this dataset comes with 45 ground-truth 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-representation curves. Similar to the result for the query "chief executive officer", MOPR maintains similar precision-representation performance to baseline methods. 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. • The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they 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) is 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, hyperparameters, 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 to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
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? Answer: [Yes] Justification: Tables 1, 5 and 6 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, confidence intervals, or statistical significance tests, at 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 run 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 or the standard error of the mean. • It 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 a 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 error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [Yes] Justification: The computer resources are described in Appendix H.• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or 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 or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 representation 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 to be applied to standard, publicly available image datasets and do not involve any surveillance, tracking or identifying of individuals. No deception or harassment is involved. In the paper, we include a discussion of broader impacts, both positive and negative. On the positive side, the techniques can help mitigate biases and underrepresentation of certain groups in image search results. This can have significant societal benefits by reducing stereotyping and increasing 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 circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration 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]Justification: 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 if the reference distribution is biased, then biases will be propagated to the retrieved items. Still, we believe that our method represents an improvement over current 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.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.For analysis of functions in an RKHS, see Appendix D.2Aggregate results should be handled with care. As each query-conditioned retrieval setting results in a different distribution, average-case performance does not preclude the existence of a query where baseline methods achieve superior results. See Limitations (Appendix B) for further discussion.For analysis of functions in an RKHS, see Appendix D.2 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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
strength_weakness: strength_weakness: 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.
2. 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?
3. In Table 1, there are significant differences between intersectional groups (e.g., Asian Male : Asian Female = 13 : 7).
questions: 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?
2. 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?
3. Is there any experiment or quantitative result about computational complexity?
limitations: limitations: The authors acknowledge the limitations regarding computational complexity and curated dataset.
paper_summary: paper_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.

Key contributions of the paper include:

Introduction 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.

Theoretical Guarantees: The authors provide theoretical foundations for the MPR metric, establishing its effectiveness and applicability in various contexts.

Practical 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.

Experimental 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.

Discussion 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.

Overall, 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 .
strength_weakness: strength_weakness: Computational Complexity:
Algorithm 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.
Actionable Insight: Future work could focus on optimizing the algorithm to reduce computational overhead or developing approximation techniques that maintain high accuracy while improving efficiency.

Scope of Evaluation:
Limited 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.
Actionable 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.

Dataset Bias:
Bias 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.
Actionable 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.

Reproducibility:
Details 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.
Actionable 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.

Ethical Considerations:
Ethical 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.
Actionable 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.

By addressing these weaknesses, the paper could further improve its robustness, applicability, and overall impact on the field.
questions: questions: Questions:

Computational Complexity:
Question: 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?
Suggestion: 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.

Generality of MPR Metric:
Question: 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?
Suggestion: 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.

Handling Dataset Bias:
Question: 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?
Suggestion: 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.

Reproducibility:
Question: 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?
Suggestion: Providing comprehensive supplementary materials, including code, datasets, and detailed documentation of experimental setups, would significantly enhance the reproducibility of your research.

Ethical Considerations:
Question: 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?
Suggestion: 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.

By addressing these questions and incorporating the suggested improvements, the paper could provide a more comprehensive and robust contribution to the field.
limitations: limitations: Assessment:
The 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.

Suggestions for Improvement:

Computational Complexity:
Current Acknowledgment: The authors note the computational complexity of the proposed algorithm in high-dimensional feature spaces.
Suggestion 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.

Generality Across Domains:
Current Acknowledgment: The need to adapt the MPR metric to other domains is mentioned.
Suggestion 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.

Dataset Bias:
Current Acknowledgment: The paper mentions the limitations posed by biased datasets.
Suggestion 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.

Ethical Considerations and Societal Impact:
Current Acknowledgment: The paper claims that no ethical considerations remain unaddressed but does not provide a detailed discussion on potential negative societal impacts.
Suggestion 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.

By 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.
paper_summary: paper_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.

The 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.
strength_weakness: strength_weakness: 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

B) Despite acknowledging that the algorithm is very slow (line 351), there is no concrete analysis presented on runtime.

C) Check out the Proposition labeling in the Appendix--they extend the numbering from the paper rather than referring to which is being discussed

D) In Algorithm 1 line 3, do you mean to say "arg max a \in [0,1] n" rather than m?

E) 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.

F) 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)

G) in Appendix A line 697, please refer to the equation by its assigned number

Overall, 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.
questions: 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

B) 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: limitations: This is mostly fine, although the runtime should be discussed / provided in more detail, as pointed out in Weakness B

Comments: title: Thank you!
Change of Rating
Response to Reviewer Comment
Response to Ethics Review
Further discussion of statistical significance.
Response to Rebuttal part 2
Response to Reviewer XQou
Response to Reviewer 4ELS - Part 2
Response to Reviewer 4ELS - Part 1
Multi-Group Proportional Representation
Response to Rebuttal
comment: Thank you for your kind answers. I will positively review the feedback you provided.
We sincerely appreciate your decision to raise your score after discussing our paper and rebuttal with us. Your feedback and engagement throughout the review and discussion process has certainly improved our paper, and we will be sure to incorporate these changes and clarifications into our final version. If you have any further questions or concerns, please feel free to discuss with us.
Thank you for the thorough explanation of the interpretation of the queries, it helped me much better to understand what is being measured here. While I still believe on a high level that there is room for improvement in the evaluation of these types of methods, I will concede that it is extremely nontrivial, making it the task of future work rather than this particular paper. As you highlight, there are still significant contributions to this work. The proposals to present more detailed individual results in the appendix and highlight the interpretation in the text I believe also make the work much more transparent to the reader.

I am raising my rating from 6 to 7, as my primary concerns of runtime and significance have been adequately addressed.

While I feel this is valuable work that should be shared with the community, I limit my score to Accept because of the complications in the evaluation at the individual level. Once again, I see that there are complications in providing results beyond the individual query level that go beyond the scope of this work and I see that the individual queries provide a clear and valuable measurement given this complicated setup, but I still find it fundamentally difficult to reliably compare two methods based on single (or very few) samples. Specifically, I am unconfident in the similarity comparisons, which are core to retreival quality.

However, I would like to thank the authors once again for the thoughtful discussion in "Further discussion of statistical significance". Before this comment I was leaning towards lowering my rating, but have instead decided to raise it.
We are glad you found our explanation useful and thank you for the additional questions! We will do our best to answer them below.

**Achieving perfect balance.** As we consider more and more intersectional groups, there is a point at which there are more intersectional group identities than retrieved items, in which case we cannot achieve 0 MPR against a properly representative curated dataset. An extreme example of this is when the number of groups exceeds the number of retrieved items. Consider, for instance, a retrieval task where 100 items are retrieved, but representation is measured against **all** groups defined by $k$ binary attributes. For $k=7$, for example, we have $2^k=128$ potential groups -- certainly, some groups will not be represented since we only retrieve 100 items. However, even though MPR can't be made exactly equal to 0, there may still be an achievable lower bound where MPR is made small. In future work, understanding the fundamental limits of multi-group proportional representation and, in particular, deriving a lower (converse) bound on MPR is of significant theoretical interest.

**Subjectivity of representative groups.** This is a very insightful point. At the end of the day, MPR requires a human to judge what groups are important to balance over. We acknowledge this limitation from a technical and social perspective and can discuss this in more depth in lines 174-184 as well as in our limitations section and conclusion. However, we note that the definition of groups and identities is a social and human construct, limiting our ability to define fairness outside the context of human subjectivity. To some extent, what is fair and what is unfair is defined by our society and the humans that exist within it. This underlines the importance of developing fairness methods such as MPR that can be adaptable to changing definitions of fairness (through the flexibility of the curation set) as our subjective human and social norms evolve. The only way to reduce subjectivity and converge on some "true" definition of representative groups and fairness is through constant discourse, criticism, and reevaluation of our existing notions. Having a method that can adapt to these changing notions, like MAPR, is critical to the alignment of our technical methods with social ideology.

In our response to the ethics reviewer, we also highlighted that we will include in the paper the importance of participatory approaches in measuring representation. We reiterate the text that will be added to Section 2 here:

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 statistics (given by the distribution Q in the definition of MPR) should be application-dependent, context-aware, and culturally sensitive.

We recommend that curated datasets used as reference statistics for MPR measurements be developed and verified through participatory design approaches [1,2] in collaboration with diverse stakeholders. This process could involve:

1. Identifying relevant stakeholder groups, especially those from marginalized communities.  
2. Conducting focus groups and user studies to understand diverse perspectives on fair representation and evaluate if a curated dataset is indeed representative of a diverse population.  
3. Iteratively refining the curated dataset based on stakeholder feedback.  
4. Regularly auditing and updating the dataset to reflect evolving societal norms and demographics.

By involving stakeholders in 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.

[1] Delgado, F., Yang, S., Madaio, M., & Yang, Q. (2021). Stakeholder Participation in AI: Beyond" Add Diverse Stakeholders and Stir" NeurIPS 2021 Human Centered AI Workshop

[2] Zytko, D., J. Wisniewski, P., Guha, S., PS Baumer, E., & Lee, M. K. (2022, April). Participatory design of AI systems: opportunities and challenges across diverse users, relationships, and application domains. In CHI Conference on Human Factors in Computing Systems Extended Abstracts
We appreciate the reviewer's feedback on the ethical implications of our work and thank them for their thoughtful review. The goal of our paper is to promote the representation of diverse population groups in retrieval tasks, thus mitigating potential representational harms. To this end, we introduce two main technical contributions: Multi-Group Proportional Representation (MPR) as a metric and MAPR as a method for promoting diverse representation in retrieval. We acknowledge that, like any fairness intervention in machine learning, metrics such as MPR and interventions such as MAPR must be applied thoughtfully to avoid "fair washing" [1] and gerrymandering [2] effects reported in the fair ML literature.

Following the reviewer's recommendation, we will expand our discussion on the limitations of biased datasets and the social impacts of MPR in Section 2, the conclusion, and the appendix of the final paper. Specifically, we will:

1. Elaborate on how biased curated datasets can propagate biased representation measurements in MPR and biased retrieval in MAPR (expanding on lines 396-399).  
2. Discuss potential unintended consequences of enforcing MPR in real-world retrieval systems, such as the risk of introducing new stereotypes and erasing identities if not applied carefully.  
3. Provide more concrete guidance on creating and selecting curated datasets that account for stakeholder interests and target representation statistics.

We will add the following discussion to Section 2:

"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 statistics (given by the distribution Q in the definition of MPR) should be application-dependent, context-aware, and culturally sensitive."

We recommend that curated datasets used as reference statistics for MPR measurements be developed and verified through participatory design approaches [3,4] in collaboration with diverse stakeholders. This process could involve:

1. Identifying relevant stakeholder groups, especially those from marginalized  communities.  
2. Conducting focus groups and user studies to understand diverse perspectives on fair representation and evaluate if a curated dataset is indeed representative of a diverse population.  
3. Iteratively refining the curated dataset based on stakeholder feedback.  
4. Regularly auditing and updating the dataset to reflect evolving societal norms and demographics.

By involving stakeholders in 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.

[1] Aïvodji, U., Arai, H., Fortineau, O., Gambs, S., Hara, S., & Tapp, A. (2019, May). Fairwashing: the risk of rationalization. In International Conference on Machine Learning. 

[2] Kearns, M., Neel, S., Roth, A., & Wu, Z. S. (2018, July). Preventing fairness gerrymandering: Auditing and learning for subgroup fairness. In International conference on machine learning. 

[3] Delgado, F., Yang, S., Madaio, M., & Yang, Q. (2021). Stakeholder Participation in AI: Beyond" Add Diverse Stakeholders and Stir" NeurIPS 2021 Human Centered AI Workshop. 

[4] Zytko, D., J. Wisniewski, P., Guha, S., PS Baumer, E., & Lee, M. K. (2022, April). Participatory design of AI systems: opportunities and challenges across diverse users, relationships, and application domains. In CHI Conference on Human Factors in Computing Systems Extended Abstracts
First of all, thank you again for engaging with us during this discussion period. Your feedback will help us tune and improve our manuscript. We really appreciate your time, attention, and thorough assessment of our work.

We acknowledge that the hypothesis test was rushed and could have been framed better -- we ran it during the weekend due to the time crunch surrounding the discussion period and wanted to answer your question promptly. We regret the error in our interpretation of the hypothesis test. Our results from the previous comment have not demonstrated that 10 queries are statistically indistinguishable from results over 45 queries, but rather that we cannot exclude this possibility. Again, we apologize for this misinterpretation.

Upon further reflection (and if we are interpreting your comment correctly), the main issue here is generalization: How can we guarantee that, if a given method achieves better MPR-similarity trade-off over 10 or even 1000 queries, it will still perform favorably for an unseen query on a new dataset? This issue permeates (to the best of our knowledge) other published experimental results in the fairness in retrieval literature. For example, our baselines PBM [26, Figs. 2,3] and MMR [24, Figs 1,4,10] include results for a single query. The difficulty here (as you note regarding different queries as different samples) is that there is no simple prior distribution over datasets and queries over which we can frame randomization claims, making measuring statistical significance challenging.

Our experiments and findings (and those of related literature) are deterministic: we select a query, retrieve items from a dataset using different "fair'' retrieval methods, and evaluate its similarity and representation. Across all datasets and for each **individual** query (including our new 45 queries from the Occupations benchmark [28]), MAPR Pareto-dominates competing benchmarks in its similarity-MPR curve. Note that Fig. 1 aggregates these results: we also observe the Pareto-dominance of MAPR at the individual query level. As the reviewer correctly points out, such consistent performance on a given set of queries does not preclude the existence of other queries and datasets where our method may perform less favorably, or even that on average over a "randomly chosen query" (however that may be defined) MAPR may have worse performance.

One way to address this issue is to be as transparent, precise, and clear as possible about our findings and limitations. We suggest three additions:
 *  We will include *individual* MPR-similarity trade-off curves in the appendix, for each query for each dataset (including the 45 additional Occupations queries). These curves do not include error bars, since they represent deterministic measurements of the performance of each method. This will demonstrate, **at the individual query level** for the datasets and queries we used (i.e. across 3 x 55 different "settings", or dataset-query pairs), that MAPR consistently Pareto-dominates competing methods listed in Fig. 1, a stronger statement than Pareto-dominance in aggregate. 

 * We will add the following text to the Limitations section and point to it in the numerical experiments: "The reader must interpret the aggregate results in Fig. 1 with caution. MPR and similarity are deterministic measurements, and the error bars represent confidence intervals over 10 pre-selected queries across each of the three datasets. Fig. 1 should **not** be interpreted as statistical evidence of performance for any of the benchmarked methods (including MAPR). In the appendix, we show MAPR Pareto-dominates competing methods not only in aggregate, but at the individual query level. This does not preclude the existence of a query where a competing method may achieve an MPR-similarity trade-off point not achieved by MAPR. However, we note that MAPR is specifically optimized to promote MPR while preserving similarity, explaining its favorable performance. In all instances observed by the authors, MAPR Pareto dominates competing benchmarks. Crucially, across all queries, MAPR was the most successful method in achieving low values of MPR while maintaining high levels of similarity with a given query."
 * We will expand on the qualitative difference with competing methods, similar to Table 1 in the paper. In particular, we highlight that the methods most competitive to ours -- PBM and MMR -- have fundamental differences. As discussed above, PBM **does not** ensure representation across **multiple** groups, and MMR takes significantly longer to run (50x-100x).

Finally, despite the limitations in existing benchmarks to make rigorous statistical conclusions as discussed above, we hope the reviewer can appreciate the technical contributions of our work, including the introduction and theoretical characterization of the MPR metric itself and our demonstration of practical methods to estimate and optimize for it via MAPR.
I am unconvinced by this test for several reasons.
1) In general, t-tests must be designed such that you reject the null hypothesis. Not rejecting the null hypothesis is not the same as accepting the null hypothesis.
2) On a theoretical level, you have set this up such that such that my statement is what should be proved, and shown that it is not possible to prove my statement (aka that may be a difference between 10 and 45 queries). However, it is not me that needs to show that the experimental values may not be significant--it is you that needs to show that they are significant.
3) MMR is actually below 0.05 for p-value, which is a commonly accepted threshold for acceptance.
4) Looking at the differences in the means, I actually believe that several are rather significant (most strongly MMR, ClipCLIP)
5) This has been shown on one dataset, but could be different across datasets (I'm not saying you should try it on more datasets for this rebuttal as I see this is unrealistic given the timeframe and appreciate the attempt to show results at all, but just that this is a weakness of the presented results).

If you would like to make the case that 10 profession queries is enough, I would still be open to that. The issue I see is that I would expect high variance across different professions. If these were more similar to seeds I would say 10 is plenty, but they are measurements of how well the method can do given different queries, which I would interpret as more similar to different samples.
Thank you for the kind and detailed explanation. I have a few more questions I would like to ask:

1. Regarding your statement, "As we consider more combinations of attributes, achieving proportional representation becomes more difficult," I am curious if this means that in future work, achieving perfect balance will be impossible, or if it is something that you will continue to strive for.

2. Concerning "Moreover, the groups for which we aim to ensure representation can be encoded in the set of representation statistics," I wonder if these representative groups, which are ultimately based on subjective human judgment, can truly reflect fair representation.
We are glad you found our answers to your questions and concerns useful. If you have any more questions before the discussion period ends, please feel free to post them, and we will do our best to answer them. Finally, thank you for increasing your score. We are glad you feel our work substantially contributes to the field, and we look forward to developing connections between MPR and other facets of fairness as well as with diverse ML applications!
## WA/B-2

We apologize for not addressing this point. To verify whether 10 queries are statistically significant, we ran a second set of experiments with 45 queries on the Occupations dataset, using the ground-truth occupation categories in the dataset as our target query. Our goal is to verify if there is a statistically significant difference in our findings when we run the same experiments with more queries. To do so, we conduct a statistical hypothesis test between results with 10 queries and with 45 queries to check significant changes in the average performance of MAPR and competing methods.

We measure *Max Reduction in MPR* with the formula `(MPR_min - MPR_topk)/MPR_topk`. This measures the best improvement in MPR achieved by each baseline as a percentage of the baseline top-k MPR. We report the mean and standard deviation of this max reduction over both 10 and 45 queries in Table 1.

We conduct a 2 sample t-test (which can be easily done with the SciPy's Stats package) with 53 degrees of freedom (45 queries + 10 queries - 2), testing the hypothesis of a significant statistical difference between these two means. The idea is to test the null hypothesis that *there is no significant difference in the performance between using 10 queries and using 45 queries*. In this case, a small p-value would mean that we reject the null hypothesis in favor of the alternative hypothesis that there is a statistical difference between 10 and 45 queries. The t-statistic and p-value are also reported in the table below. For MAPR and most of our baselines, the t-test reports a p-value significantly greater than 0.05, indicating that we **accept** the null hypothesis that the samples across these two experiments are drawn from populations with the same population mean (or as noted in the SciPy documentation, "our observation is not so unlikely to have occurred by chance"). Note also that the max reduction in MPR is very close across both experiments. Thus, our findings based on 10 queries are statistically significant, and increasing the number of queries by a factor of 4 did not lead to different conclusions. 

|             | Mean (STD), 10 Queries | Mean (STD), 45 Queries | t-statistic | p-value |
|-------------|------------------------|------------------------|-------------|---------|
| MAPR (Ours) | -0.943 (0.025)         | -0.948 (0.029)         | -0.476      | 0.636   |
| MMR         | -0.628 (0.127)         | -0.702 (0.094)         | -2.032      | 0.048   |
| PBM         | -0.070 (0.049)         | -0.065 (0.066)         | 0.180       | 0.858   |
| ClipCLIP    | -0.400 (0.067)         | -0.326 (0.180)         | 0.928       | 0.358   |
| DebiasCLIP  | 0.013 (0.160)          | 0.110 (0.227)          | 0.825       | 0.414   |


Table 1. Max reduction in MPR averaged across 10 and 45 queries, as well as results for a 2-sample t-test between sets of queries. We see that there is no statistical significance in our results when increasing to 45 queries. MPR estimated and MAPR optimized with a linear regression oracle for k=50 samples on the Occupations dataset.

Again, we thank the reviewer, and we will be happy to provide further clarification about our contribution.
Thank you for engaging with our response during the discussion period. We appreciate the very interesting questions.

## WA/B-1

We will clarify the key similarities and differences between MAPR and PBM:

- **Representation Goal:** You are correct that PBM ensures *equal representation* across a *single group*, while MAPR ensures *proportional representation* across *multiple intersectional groups*.
- **Groups:** PBM focuses on a single binary attribute (though allowing for N/A values) and does not handle intersectional groups. MAPR considers multiple attributes simultaneously and considers the representation of intersecting groups (e.g., Women and Black Women).
- **MPR Gap:** At high MPR levels, PBM and MAPR are both able to achieve comparable similarity scores in retrieval. However, it is incorrect to say PBM and MAPR perform similarly across the entirety of the similarity / MPR curve. PBM is unable to achieve low MPR values, as evidenced by it not extending all the way to the left on the graphs in Figure 1.
- **Runtime:** You are indeed correct that MAPR has a higher runtime cost due to handling multiple attributes. Since PBM considers a single attribute, it is faster.

In summary, PBM is only comparable to MAPR on the similarity/MPR curve for high MPR values due to its restriction to a single binary group. This can be seen in Fig. 1, with PBM not extending to the left-hand side of the graph (low MPR values). We explain why this is the case next.

Recall that MPR -- our metric of interest -- quantifies the worst-case deviation in proportional representation across a collection of groups. In Fig. 1, these groups are determined by race, age, and gender attributes. PBM does an excellent job ensuring MPR **up to a point**, matching the performance of MAPR for high MPR values. However, it does not reach low MPR values (e.g., Fig. 1 center). This happens because PBM considers **equal representation** of a **single binary attribute**: we pick gender since this is a central focus of the PBM paper, and the attribute "race" in our experiments is not binary.

PBM manages to close the gender representation gap in retrieved images in Fig. 1, thus lowering MPR up to a point. However, it stalls in achieving representation for other attributes such as race and age. Of course, this is not surprising: PBM is designed for a single attribute. MAPR (our method) manages to achieve proportional representation across groups, reaching lower MPR points on the left-hand side of the graph and thus significantly lowering the representation gap at a slightly higher runtime cost.

Extending the single-attribute balancing algorithm behind PBM to multiple attributes is possible but very likely would incur a higher runtime due to requiring balancing over an *exponential* number of intersectional groups. We will add this discussion to the appendix of the paper, and summarize it in the main paper. We hope this clarifies your understanding!
Thank you for the detailed and thoughtful rebuttal. I appreciate the effort you have put into addressing the concerns raised in my review.

Computational Complexity:
I appreciate the additional benchmarks provided in the rebuttal that demonstrate the competitiveness of your method in terms of runtime. The theoretical discussion on the efficiency of MAPR, particularly with modern optimization techniques, has also clarified the potential scalability of your approach. This helps address my concerns regarding the computational complexity, especially in high-dimensional feature spaces.

Generality of the MPR Metric:
Your explanation of how the MPR metric could be adapted to other domains such as text retrieval and recommendation systems is convincing. The argument that your method is applicable to any setting involving vector embeddings broadens the potential impact of your work. The potential for adaptation to other domains strengthens the significance of your contribution.

Handling Dataset Bias:
Your acknowledgment of the challenges posed by biased datasets, along with the explanation of how MPR flags deviations in representation when retrieval datasets are biased, provides a clearer understanding of how your approach handles these issues. This reassures me that you have considered the implications of biased datasets, even if further exploration in future work is necessary.

Reproducibility:
I appreciate the commitment to enhancing the reproducibility of your results by extending the GitHub code, creating a tutorial, and documenting the experimental setups in more detail. These steps will undoubtedly aid other researchers in replicating and building upon your work.

Ethical Considerations:
The expanded discussion on the ethical implications of the MPR metric, including the potential for a false sense of fairness, legal risks, and the importance of human oversight, adds significant depth to your work. This addition addresses the ethical concerns I mentioned and contributes to a more comprehensive understanding of the societal impact of your research.

Given your thorough and thoughtful responses, I believe the paper has demonstrated robustness, applicability, and a high potential for impact. The clarifications and additional details provided in the rebuttal address many of the concerns I had, and I am inclined to improve my rating of the paper. I appreciate the effort you have put into making these improvements, and I believe your work makes a substantial contribution to the field.
Thank you for your response to my concerns and questions. Many of your answers are satisfactory to me (once again, thank you for those), so for conversation clarity I will just address the few remaining discussion points I have here:

WA/B-1) The additional runtime analysis is good, but I just want to make sure I am interpreting the relationship with PBM correctly: PBM is faster than MAPR and performs similarly in terms of similarity / MPR curve (figure 1). However, what we gain for the extra time is balance across groups, regardless of intersectionality (table 1).
WA/B-2) I am aware that 10 queries is what is used in previous literature, but I still have doubts that this is not very many samples for statistical significance. The additional experiments scale up the number of neighbors, but keep the number of queries fixed. Could you please comment on how this is enough samples to make conclusions? I apologize if I am missing your previous response to this point, but in the rebuttal I only see a response to the runtime concerns.