Audits Under Resource, Data, and Access Constraints: Scaling Laws For Less Discriminatory Alternatives
Authors: Sarah H. Cen
Salil Goyal
Zaynah Javed
Ananya Karthik
Percy Liang
Daniel E. Ho
Venue: NeurIPS 2025 poster ()
Keywords: AI audits
less discriminatory alternatives
scaling laws
Pareto frontiers
burden of proof
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We derive a closed-form scaling law for a loss-fairness Pareto frontier, which allows an auditor or plaintiff to determine if a less discriminatory alternative exists with minimal compute, data, and model access.

Abstract: AI audits play a critical role in AI accountability and safety. They are particularly salient in anti-discrimination law. Several areas of anti-discrimination law implicate what is known as the "less discriminatory alternative" (LDA) requirement, under which a protocol is defensible if no less discriminatory model that achieves comparable performance can be found with reasonable effort. Notably, the burden of proving an LDA exists typically falls on the claimant (the party alleging discrimination). This creates a significant hurdle in AI cases, as the claimant would seemingly need to train a less discriminatory yet high-performing model, a task requiring resources and expertise beyond most litigants. Moreover, developers often restrict access to their models and data as trade secrets, hindering replicability.

In this work, we present a procedure enabling claimants to determine if an LDA exists, even when they have limited compute, data, and model access. To illustrate our approach, we focus on the setting in which fairness is given by demographic parity and performance by binary cross-entropy loss. As our main result, we provide a novel closed-form upper bound for the loss-fairness Pareto frontier (PF). This expression is powerful because the claimant can use it to fit the PF in the ''low-resource regime," then extrapolate the PF that applies to the (large) model being contested, all without training a single large model. The expression thus serves as a scaling law for loss-fairness PFs. To use this scaling law, the claimant would require a small subsample of the train/test data. Then, for a given compute budget, the claimant can fit the context-specific PF by training as few as 7 (small) models. We stress test our main result in simulations, finding that our scaling law applies even when the exact conditions of our theory do not hold.

Audits Under Resource, Data, and Access Constraints: Scaling Laws For Less Discriminatory Alternatives
Sarah H. Cen Stanford University Palo Alto, CA 94304 shcen@stanford. edu
Salil Goyal
Zaynah Javed Stanford University Palo Alto, CA 94304 zj aved@stann oor edu
Stanford University Palo Alto, CA 94304 sal salilg@stanforr www.eatanford...mmm edu
Ananya Karthik Stanford University
Percy Liang
Daniel E. Ho Stanford University Palo Alto, CA 94304 deho@stanf ord. edu
Stanford University
Palo Alto, CA 94304 ananya230stant edu
Palo Alto, CA 94304 pl aliangocs.oo stanford.... edu
Abstract
Al audits play a critical role in Al accountability and safety. They are particularly salient in anti-discrinnnation law. Several areas of miniriiscriinntioon law implicate what is known as the "less discriminatory alternative" (LDA) requirement, under which a protocol is defensible if no less discriminatory model that achieves comparable performance can be found with reasonable effort. Notably, the burden of proving LDA exists typically falls the claimant (the party alleging discrimination). This creates a significant hurdle in Al cases, as the claimant would seemingly need to train less discriminatory yet tigh-performing model, a task requiring resources and expertise beyond most litigants. Moreover, developers often restrict access their models and data as trade secrets, hindering replicability.
this work, we present a procedure enabling claimants to determine an LDA exists, when they have limited compute, data, and model access. To illustrate our approach, we focus on the setting in which fairness is given by demographic parity and performance by binary cross-entropy loss. As main result, we provide a novel closed-form upper bound for the loss-fairness Pareto frontier (PF). This expression is powerful because the claimant can it fit the PF in the "low-resource regime," then extrapolate the PF that applies to the (large) model being contested, all without training single large model. The expression thus serves as a scaling law for loss-faimess, PFs. To use this scaling law, the claimant would require small subsample of the train/test data. Then, for given compute budget, the claimant can fit the context-specific PF by training as few as 7 (small) models. We stress test our main result in simulations, finding that our scaling law applies even when the exact conditions of our theory do not hold.
Introduction
Complex AI systems are increasingly used in Docision-makinn contexts that are subject to legal oversight. For example, HireVue has used AI to score video interviews [30]; various US agencies apply facial recognition for fraud detection 3 5 and insurance providers use elaborate behavioral data to price policies 45 46). In the absence of methods that test whether such systems comply with the law, decisions that rely heavily on AI are permitted to escape scrutiny. Accordingly, there is growing need for AI audits. This need is particularly pronounced as models increase in complexity and scale. In particular, auditing becomes more challenging as models process high-dimensional,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

unstructured inputs such as text and video, where the number of possible inputs becomes too large to test exhaustively. We henceforth refer to the system being audited the "model," noting our analysis applies broadly, e.g., to Au decisions
AI audits are particularly salient in anti-discrimination law, in which the goal is typically de- termine whether a protocol discriminates on the basis of a protected attribute. Several areas of unti-diserimination law implicate the "less discriminatory alternatives" (LDA) requirement. Con- ceptually, it holds that a protocol (e.g., Al model) should not be used if a protocol that achieves comparable performance while being less discriminatory can be found without causing "undue hardship" (i.e., imposing significant costs on the employer). For most of this work, we ground our discussion in a well-known context involving LDAs: Title VII of the US Civil Rights Act. Importantly, under Title VII, the burden of proving that an LDA exists falls on the plaintiff.
The LDA requirement highlights fundamental and recurring issue in Al audits that is at the heart of our work: claimants generally have fewer resources, less expertise, and limited knowledge about the audited model than the defendants they challenge, and yet bear the burden of proof. We refer to this asymmetry" in Al evidence production.
phenomenon as the "resource-informatiee
This asymmetry can prevent claimants from gathering sufficient evidence to prove their claim. The LDA requirement drives this point home. Interpreted straightforwardly. the claimant is asked to provide less discriminatory model, i.e., train model that maintains the same level of performance as state-of-theearr, production models while simultaneously reducing discrimination. However, most claimants lack the compute, data, and expertise to do so. To add to the asymmetry, developers fiercely protect their models, training procedures, and data as trade secrets, meaning that claimants wishing to train comparable model lack critical information.
1.1 Contributions
In this work, we tackle the resource-informatio asymmetry, using the LDA requirement as our case study. As is customary in disparate impact analyses, we focus on the classification setting (noting that this includes decisions that use generative Al to classify individuals). While our primary objective to provide tools for claimants, we note that our approach also helps model developers assess the existence of LDAs without expending significant resources.
Conceptually, we first shift the problem from that of training less discriminatory model to showing that a less discriminatory model exists, as explained in Section 2 and visualized in Figure Ta We thus recast the problem one of finding the cerffommanc-faaireees Pareto frontier (PF). If the contested model sits far from the PF, then many LDAs exist. One could thus measure how easily the defendant could find an LDA using the distance from the PF, as formalized in Section 3 An additional benefit is that finding the PF does not reveal potentially proprietary information specific to the contested model. Note that, to use PFs, one must quantify performance and fairness; though not always feasible, this is rarely prohibitive because disparate impact analyses of Al generally involve quantitative evidence.
Recasting the problem in terms of PFs does not immediately resolve the resource-information asymmetry because finding the PF is a challenging problem in and of itself (see Figure [b). Existing methods for finding the PF are just as (often more) instucceinteesivve than producing an LDA (see Sections 2 and 6 Our approach transforms this task into a tractable one by finding a scaling law for the PF as visualized in Figure 2 Given the form of the scaling law, claimants could first fit its parameters in low-resource environment, then extrapolate where the PF falls for the contested (large) model. Thus, the claimant would never need to train large model.
This approach hinges on the existence of a scaling law. We provide, to our knowledge, the first PF (that is also, in sense, tight). We describe
closed-form upper bound of performance-faimen how this expression can be used as a scaling law that allows one to learn the PF empirically at a fraction of the cost of existing methods. Our result uses binary cross-entropy loss our performance metric, demographic parity as our fairness metric, and a posited data suta-gennrating process, as given in Sections 3] aand4 4. We hope to extend this result other fairness and performance metrics in future work. As mentioned above and described in Section 4.2 to apply the scaling law, one needs four ingredients: (i) test data for evaluation, (ii) small subsample of the training data, (iii) an estimate
WWe adopt this terminology to simplify our language. Using "model" to refer to the broader Al system that results from pre-trainin training, post-training, guardrailing, etc. is increasingly common.

---

L
frontier
L
frontier
(loss)
system
employer's desired loss
(faimess gap)
A
potential improvement
(a)
(b)
Figure 1: (a) Consider the contested AI model, given by the "X". As described in Section 2 there two steps a disparate impact case before the less discriminatory alternatives (LDA) step. the first step. claimant establishes that there is disparate impact, typically using a statistical measure of discrimination (the fairness gap). Thus, the first step identifies the x-coordinate of the model (of "X""). In the second step, the defendant counters by arguing that the disparity serves what is known that allows them to meet some desired performance (the y-coordinate of "X"). In final step, the claimant must prove that the employer could have used an L.A that would be less discriminatory while still meeting the employer's desired performance (i.e., a model that is to the left of but no higher than "X"). In this work, we cast this problem as determining where the given by the orange curve, then the "X" is the PF, meaning that LDAs exist; decrease the fairness gap. one must sacrifice performance. the PF given by red curve, there significant room improve faimess while maintaining performance. (b) Recasting the problem to finding the PF does not immediately resolve the resource-informatie
business necessity, demonstrating
cetormmacceaaiimeee Pareto frontier (PF) lies. For example, if the PF is
asymmetry. The typical approach is to train many models while inducing them to have different boss-fairess, characteristies (as given by the small x s), then trace the curve connecting the points lowest and the left (red line). The issue for the PF to apply, the trained models must be of comparable size to the contested model. Training such models requires resources, data, expertise beyond most claimants.
of the contested model's size, and (iv) an estimate of the amount of data used train the contested model. Of these, (i) should not be difficult to obtain, as both parties use test data for the two steps of disparate impact cases preceding the LDA step (see Section 2). While the defendant must provide (ii)-(iv, they are more conservative asks than the status quo and may thus help strike balance between the plaintiff's and defendant's interests
We conclude with experiments on synthetic data in Section 5 to stress test the conditions of our theoretical result. We find that scaling law holds even when the conditions of our theory, outlined in Section 4 do not. We emphasize that our method is plug-and methods for finding Pareto-optimal models, our approach provides increasingly better estimates.
as researchers develop better
Our main contributions are summarized as follows:
1. We cast the problem of establishing the existence of an LDA and/or estimating the cost of producing LDA determining the performance-fainee Pareto frontier (PF).
2. We provide a closed-form upper bound of the performance-fainn fairness PF that functions as a scaling law. We describe how one would apply this scaling law to determine whether LDA exists at fraction of the cost training a large model. Our method works on unstructured inputs.
3. We conduct small-scale experiments to test our theoretical result.
Finally, we note that although we study LDAs, we believe that the need for low-resource, low- information methods substantiate AI claims and conduct AI audits is broad and pervasive issue. We point out extensions to our work in Appendices A and B.I
"Straightforward approaches to finding an LDA require access to the trained model (e.g.. to use as starting point from which one searches locally for an alternative) and/or a significant portion of its training data (e.g.. to train comparable model).

---

2 Less Discriminatory Alternatives and Their Relation To Pareto Frontiers
In this section, we discuss the relation between less discriminatory alternatives (LDAs) and Pareto frontiers (PFs), in the context of Title VII of the US Civil Rights Act (CRA), Our analysis will allow us to map the LDA requirement to formal problem statement in Section 3 A more extensive background and related work can be found in Section 6
2.1 Three steps of disparate impact cases
Title VII prohibits employment discrimination on the basis race, color, religion, sex, and national origin, which are referred to as "protected attributes." Although there are several ways to litigate under Title VII, the legal theory that is typically applied to automated decisions is the disparate impact Courts generally adopt a three-part, burden-shifting test to adjudicate disparate
doctrine 8 33
impact claims:
1. The plaintiff must show that a facially neutral employment practice has disparate impacr on a protected class, i.e., leads to systematically different outcomes for individuals in different groups. For automated systems, this is generally done by showing a statistical disparity in outcomes.
2. If the plaintifff establishes disparate impact, the defendant (e.g., employer or employment agency) can counter by showing that the practice is for "business necessity" reasons (i.e., performance). Similarly to the above, a quantitative notion of the business goal often adopted.
3. If the defendant successfully claims business necessity, the burden of proof shifts back the plaintiff, who must prove that there is an LDA: a protocol that the defendant could find without undue hardship and that would serve the same employment goal as in Step 2 while causing less disparate impact. If the plaintiff cannot do this, they lose the case.
Our work addresses Step 3. We assume Step (which is studied extensively by the algorithmic fairness community [21) 63 27 18 23) and Step 2 are complete. See Section 6 for further discussion.
Example 2.1. To illustrate the challenges in finding an LDA, consider an Al hiring tool that uses large language and video models to screen applicants. Suppose that the plaintiff shows that this tool has disparate impact with respect to sex (Step 1). The employer counters by showing that the tool improves business outcomes due to hiring (Step 2). In Step 3, the plaintiff must establish that tool that has less disparate impact but comparable business outcomes exists. Naive approaches to this include retraining model from scratch (which would require resources, expertise, and data that most plaintiffs lack) or modifying the existing model (which would require access to the model that developers unlikely to grant via trade secret protections). We expand on this example and the challenges that plaintiffs encounter in greater detail in Appendix B.2
2.2 Relation between LDAS and Pareto frontiers
The example in Appendix B.2 highlights the difficulties of providing an LDA given the resource- information asymmetry. However, the LDA requirement does not necessarily imply that the plaintiff must train a new model. Instead, the plaintiff can prove, to sufficient standard, that such an alternative exists In Figure Ia] we illustrate how proving the feasibility of an LDA can be cast as determining that given model lies far from the performance-fainet lies above and to the right of the PF, then the gap quantifies the effort needed to find an LDA.
PF. If the defendant's 's model
Although recasting the LDA requirement as problem of finding the PF helps mitigate the in- formation asymmetry problem since finding the PF does not require knowledge specific to the defendant's ' system-computte the PF remains ussurce-intensive. In fact, the general method for
"The other well-known legal theory is disparate treatment, which applics when decision-make maker intentionally treats an individual differently based on their protected class. In the context of automated decision-making and AI systems, disparate impact is typically applied due the difficulty of ascribing intent to algorithms or models g Although disparate treatment is not generally applied to automated and Al systems, some have begun to contemplate its application due to the rise of "reasoning" models that seem to verbalize "intent." In addition, some believe algorithms that protected attributes inputs should be subject a disparate treatment analysis.
"We cannot say for certain how courts will receive this evidence. Even if courts do not believe it fully satisfies the LDA requirement, it can be used to as an intermediate step that supports the plaintiff's is requests for further discovery, including data and model access that they may be initially denied (see points 2 and in Section 2.1

---

L
Scaling law for loss-fairness PFs
(loss)
How does this approach address the resource- information asymmetry?
Information asymmetry. Claimants are often denied access to the model, data, and information about the training pracedure. The PF not model-specifi and thus does not require knowledge about the contested model that may be considered proprietary.
Step 1. Fit frontier on small models/data
Step 2.
Extrapolate frontier large models/data
Resource asymmetry. Current methods finding PF costly (require training many large models mare rescurce-intensive than finding an LDA). Using scaling law means the claimant never needs to train large model.
(fairness gap)
Figure 2: illustration of the proposed method on the left and how addresses the resource-information
asymmetry on the right, as explained in Section 2
finding the PF is to train wide array of models with varying iefoommance-fiineeee characteristics. plane, and then trace out the empirical PF [21, 61 6 as illustrated in Figure 16 From resource perspective, this is more difficult than training single large model-it involves training many!
plot them on the performance-faiinn
Our main technical contribution, outlined in Figure is scaling law that greatly reduces the resource cost of finding the PF. Our scaling law allows for several types of analyses, such as (i) estimating how far the contested model from the PF for models of equivalent size trained similar amount of data; or (ii) estimating how many resources one would need to obtain model with specific performance-fairnes attributes.
Formal Problem Statement
In the remainder of this work, demonstrate method for proving the existence of a less discrimi- natory alternative (LDA) a low-resource, low-information setting.
3.1 Setup
Consider binary classification setting, where random variables X E X. A (0, 1), and Y {0, denote the features, (binary) sensitive attribute, and (binary) class of an individual. Notably, X may be unstructured. For instance, X could denote job applicant's resume, A their sex, and their suitability for the job of interest. Throughout, we use the convention that capital letters represent random variables. and their lower-case analogs denote specifie values that they take. Let f X x {0, + [0, denote a (soft) classifier that takes in features ø and sensitive attribute and returns generality, as f could ignore it, so we use this A-"aware" setup. We use F to denote the model class (e.g., neural network of size N) that belongs and D denote f's training dataset.
f(z, a) between 0 and 1. Note that having f depend
is without loss of
this work, we use (expected) binary cross-entropy (BCE) loss as our measure of performance. Let the BCE of f with respect to a (fixed) joint distribution Px.A.Y be given by
C(pX.AYY f) = -Eg EE Br..,g-xx..r [y log(f(z,, a)) + (1 3) log(1 - a)).
(I)
We use demographic parity as our notion fairness. Thus, the faimess gap of f with respect to conditional distribution Pxla is given by
( f) == A [I, - (fr
We refer to p as the "test" distribution. Note that the plaintiff may choose to use other notions of performance and fairness. In this work, BCE and demographic parity, leaving analysis of
5

---

other definitions to future work 5 The "right" choice of fairness metric is generally context-dependent
and highly debated. We provide a short discussion in Appendix [33] Note that history indicates that demographic parity is a likely choice by courts, as selection rates have appeared across multiple contexts, including the Four-Fifths Rule from 1978 to NYC's Local Law 144 of 2021.
3.2 Our objective: Establishing existence of an LDA with limited information and resources
Limited resources. Suppose the plaintiff's 's model belongs to a model class F and is trained on a dataset D-, which are much smaller than the model class F+ and training dataset D' available to the defendant. Let N and D+ denote the parameter count of F+ and number of samples in D-. Similarly, let N and D denote the parameter count of F and number of samples in D= Suppose that the claimant can only train models that belong to F and D where N > N and We assume that D is drawn from the same distribution D+
D+ >>>>>/> D=.
Limited information. In past and ongoing cases, judges and defendants have been reluctant to share information about the model and training data, arguing that this information is proprietary and confidential. In this work, we assume the claimant is similarly denied access to the contested model but request limited amount of information. We propose that, since the LDA requirement asks that the claimant assess what alternatives are "feasible" or "reasonable" for a defendant to obtain, the claimant should minimally be given information about how many resources were used train the contested model: namely, the values N and D+. We further propose that the claimant should be granted small subsample of training and test data. In the notation given above, the subsample of training data would be of size D= and the subsample of test data at most D 6
Objective:
Show existence of (feasible) LDA. Our objective is to provide method that the claimant can use to determine whether the contested model is at least ô-far from the Pareto frontier (PF) for a fixed performance level (i.e., loss), which would imply that finding an LDA is 8-feasible.
Formally, let the defendant's 's contested model be denoted by f Our objective is to provide method that the claimant can use to determine whether, for a given value 5 > 0, there exists a model f of size N and trained on dataset of size D such that
(2) In other words, there exists a model that is at least as performant as the contested model and reduces the contested model's fairness gap by at least d > 0. The larger the value of ô, the greater the distance between the contested model and the PF. This distance is indicative of the "feasibility" of finding an LDA: under the mild assumption that the loss-fairness PF monotonically improves N and D increase, large values of indicate that the defendant could have found an LDA with a small fraction of the resources they expended to train f*. Our scaling law also allows to estimate the minimal N and D needed to achieve certain faisnfss characteristics.
L(PX.AYY S. C(xX,AY f*) and A(PXIA, f) < A(P
Main Result: Scaling Law for Loss-Fairness Pareto Frontier
In this section, we derive scaling law for the loss-farrness Pareto frontier (PF) under given data generating process (DGP). We then describe how one applies this scaling law. Note that we present an intermediate result in Appendix that lends intuition for how our main result is obtained and can be used as a building block for future works that examine different notions of fairnsss and DGPs. All proofs are given in Appendices and
4.1 Closed-form upper bound of the loss-fairness Pareto frontier
Recall that Pareto frontier (PF) is traced out by the lowest-loss classifier for every faimess gap value A. In this section, we present our main result: a closed-form upper bound of the loss-fairness PF Before presenting the result, we introduce some notation. Let p and q denote joint distributions over random variables X, A, and Y. Let p(1 xr a) and q(1 x, a) denote the Bayes optimal classifiers under p and q. respectively. We begin with an assumption that we explain in Appendix C.I
IImportantly, recall from Section that the plaintiff' chooses their definition of disparate impact in Step I and the defendant chooses their definition of business necessitylegitimate employment goal in Step 2.
This amount of information is even more conservative than what has been requested in past cases 22, 49
and what practitioners currently advocate for [66] 17

---

Assumption 4.1 (Model misspecification symmetry), For given distribution q. let f be the loss- minimizing classifier in model class F when training on a dataset D drawn from q. We assume that A(qxAY, f) Ly X,A)
A is constant cI D), that does not depend on q or f. Moreover,
[[ A) 0J [[,]|],,A)] = 0j = [z] = [[g([12, = 11, where all expectations are taken with respect to the test distribution PX|A-
This assumption essentially implies that each Pareto-optimal model f that belongs to model class F is symmetric with respect to the DGP, which one would expect to hold for large models that serve as universal function approximators. The second condition in symmetric with respect to A. This condition does not imply that f fits group A = 0 as well as the other group A = 1, but that the "distance" between ff and q(1 x, a) is symmetric with respect to A. Theorem 4.2. Consider the following data generating process: A ~ Ber(T), X T A. and Y| A r Ber(a - (A) for < 2 O, where (.) the sigmoid function, g is a measurable function, and q is the joint distribution induced by some S. With slight abuse of notation, let == A(pxJA: denote the fairness gap of f under test distribution p. We assume p qf for a fixed Ç and all Pareto-optimat of satisfy Assumption 4.1for some q². Then, for all f on the Pareto frontier.
that f is
((F,D) D) c.. dloog1 - c" A c- (1-c')log(e) A L(px,Av, B(F,
(3)
c.d.
+ c. +
+ +c' - -) - c 2(1 e" +A 2(c" 4]2
where= O (max: EpxiAsi I(dy .A. (1 xx 12,1) -2,1)-977 )1) and of E Exxia l (1/z, 1)].
B(F D) is a constant that depends on the model class F, dataset size D and p. and e, e' c" E [0.1] are constants that depend only on p.
This result expresses the loss of each Pareto-optimal ff on p function of f's fairness gap A. The dependence loss on fairness gap is fully characterized, except for four constants that do not depend on A: [F, D), d' and c". The constants c', and c" depend only p. BFF D) depends on p. the model class F. and dataset size D. We describe how this result can be used as a scaling law in Section 4.2 Finally,
note that although our result is specific to the DGP given in Theorem 4.2 hope it provides a template for future analyses. Even so, the DGP above is fairly general: that A is Bernoulli is without loss of generality; and X I A does not hold in general but should not affect Pareto-optimality analysis.
4.2 Applying the Scaling Law to the LDA Requirement
Theorem 4.2 can be viewed as a scaling law. Indeed, it provides closed-form expression for the loss-fairness Pareto frontier (PF) that involves three constants that do not depend on F and D, then one constant (FF D) that does. This implies that finding the PF for large model class F+ and large dataset size D involves three main steps, as follows.
To apply the scaling law, the auditor needs an estimate of N and D+, a subset of the train/test data, and compute budget, described in Section 3 As first step, the auditor trains models of size N < N+ on a dataset of size D < D+ where N- and D are chosen based on the auditor's s compute budget. These trained models yield an empirical PF that can be used to fit a curve of the form given in Theorem (.2] i.e., estimate the unknown constants in the expression. The auditor can repeat this process with different N and D until they are satisfied with their fit. Then, given an expression for how B(F, D) changes with F and D, one can plug F and D+ into B(F+, D+) to extrapolate the PF for F and D+ Luckily, past works provide a template for the form of B; specifically, previous works such as (32 7 show that the minimum loss scales with (1/NN" + 1/) for some a, B > O. Because B is a linearly additive constant in Theorem 4.2, this implies that B also scales at the same rate. A more detailed, step-by-step procedure is given in Appendix D
We provide discussion of limitations and corresponding future work in Appendix
Remark. The existence of a closed-form expression for the PF does not mean that all faisnfas PFs look the same. In fact, the shape of the PF can vary significantly depending on the values of the constants, as we show Appendix []]] The constants are context-dependent, and thus the shape of the PF is also ceptext-dependent. We also note that our approach "fails gracefully" in that it is conservative: if claimant finds the contested model is 8-far from the PF, then it is at least that far. See Appendix for further discussion.
7

---

5 Experiments
We run both simulations and experiments to test our main result. The simulations can be found in Appendix [.J] In this section, we present experiments that we ran to test Theorem 4.2 and its assumptions. We find that the PFs predicted by our theory closely matches the empirical PFs, validating our scaling law approach to assessing the existence of a less discriminatory model (LDA). Our experiments also demonstrate how one might apply Theorem 4.2 in practice.
Main goals. These experiments allow us to manipulate key aspects of the data generating process and training setup and stress test the conditions of Theorem 4.2 in three critical ways:
1. We relax the assumption on the data generating process in Theorem 4.2 so that X f A.
2. One of our main proof techniques is to transform the constrained minimization problem into an unconstrained one by creating an artificial train distribution q (that does not actually exist). Doing so allows us to "tune" the fairesss gap, then find the loss-minimizing model. In our experiments, we test whether this approach is representative of the true massmmiii models at various fairness gap values.
3. Our second proof strategy is to use a Bayes optimal estimator for artificial distribution to approximate Pareto-optimal model. This approach further relies on Assumption 4.1 We trace out the empirical PF by training a collection of models on the synthetic train data, using the lower convex hull of the resulting (loss, fairness) characteristics as the empirical PF. Thus, our experiments test whether the approach we take to derive our analytic result holds empirically.
Synthetic data generation. We generated a synthetic dataset with 10,000 samples, where each sample is a (O-dimensional vector with binary group labels. Each is sampled i.i.d. from standard isotropic multivariate Gaussian distribution. The group label a E {0. 1} is deterministically assigned by linearly projecting the first two dimensions of onto scalar, then thresholding, where the linear weights and bias are randomly sampled from a multivariate Gaussian, and the threshold is chosen so that a fixed fraction of the population belongs to Group (i.e., p( 1) is the desired value). Because depends on X, they are not independent, as required in Theorem 4.2 our experiments therefore test whether the closed-form PF holds despite this relaxation.
The target variable y E {0, 1} is sampled from a Bernoulli distribution with probability P(Y = 1 X. A) (X) <A), where g R
IR is a fixed, randomly initialized 2-layer MLP with hidden layer of size 32 applied to X, ç 2 0, and (-)) denotes the sigmoid function. It thus mirrors the data generating process in Theorem 4.2 except that X and A are not independent. We show results for various values of Ç. Finally, our experiments use the same distribution for the train and test sets.
Obtaining the empirical PF. We obtain the empirical PF by training models with varying loss- fairness characteristics. To do so, we use linear scalarization, i.e., we set the loss to be the sum of the BCE loss and the fairness gap Lioal LBCE + X CDP and vary X.
As in our theoretical result, we use demographic parity as our fairness notion, We vary À across 100 values between -3 and 5, with a higher density of values in the -3 to 0 portion For every scalarization value, we run 3 trials, then trace out the empirical PF (with mild smoothing and averaging). Further training details are given in [ppendix Note that may choose to a better method for obtaining the empirical PF, and hence need to both train fewer models and obtain a more accurate PF.
To get the empirical PF, we compute each trained model's BCE loss and fairness gap on the held-out test data. We plot these (loss, fairness) pairs on the BCE loss vs. demographic parity gap plane. To trace the empirical PF (the lowest achieved loss for each given demographic parity gap), we connect the points forming the lower convex hull of the points.
Testing the scaling law. of constants C1 through C7 such that the closed-form expression given in Theorem 4.2 predicts the PF across different values of N and D, as laid out in Section 4.2 We focus on the effect of model scaling, leaving constant and only varying the model size N. We then use the procedure described
To test whether the scaling law holds, we demonstrate that there is fixed
7 Although X's are usually positive, we use negative values to test whether the PF curves upward for large faimess gaps predicted by theory.
8

---

8 8200
23960
0.75
109120
8 42.344
0.70
0.55
BCE Loss
0.60
BCE
0.55
0.45
90
0.45
0.40
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.00
0.05
0.10
0.15
0.20
0.25
0.30
Fairness Gap
Fairesss Gap (Zoomed)
Figure 3: Pareto frontier for different model sizes under (it = 0.2) and bias strength Ç = 0.5. Each point corresponds to a trained model with a different fairness regularization weight x. The dashed lines show the empirical Pareto frontier, created by finding the lower convex hull of all the points. The solid lines show fitted curves to the points the Pareto frontier using Theorem 4.2 with 0.0176, bias 00.285, loss scaling law 55 -5. while the right panel zooms in on A E [0, 0.3] The fitted curve mimics the empirical data well though it is imperfect. We found that there were many possible fits, depending the precise choice. We show another possible fit in Figure below.
0.92, c" 0.1424, with 0.7 + 5.55). The left panel shows the frontier across the range A,
in Section 4.2 to "scale" the curve. the empirical PFs are close to the predicted curves, it would validate our method: that training small models can be used to approximate the PF of larger models. In Figure 3 and similar plots in Appendix[] the dashed lines give the empirical PFs, and the solid lines give the ones predicted by our theory.
Results. Our findings corroborate our theoretical result: First, from the y-intercepts alone, we verify that B(F, D) nearly perfectly scales proportionally to N-a D plus an additive constant, as predicted. Second, the empirical PFs follow the shape our closed-form scaling law. Even small changes to the expression in Theorem 4.2 would not yield a similarly good fit. Perhaps somewhat surprisingly. our theory predicts that the effect of scaling via B is linearly additive, and our experiments validate this prediction. Both of these findings provide strong evidence supporting: (i) our Assumption 4.1 and (ii) the use of Bayes optimal estimators artificially constructed train distributions to approximate Pareto-optimal models (which allows us to obtain our result with minimal assumptions the model class and for unstructured inputs).
We note that the fitted curve mimics the empirical data well though imperfectly, which may occur for several reasons. The first is that the empirical PF is always imperfect since finding Pareto-optimal models is difficult, e.g., due to factors discussed in Section 4.2 under "Considerations for Step 1." The second is that (3) is an upper true PF differs slightly from the predicted one (though our result is, some sense, tight as seen in Appendix l). The third is that there many possible fits for the same empirical PF, Appendix In practice, one may choose to the curve as closely as possible to the data or, noting that the PF is an idealized concept, fit the curve to lower bound the empirical points.
there is a possibility that the shape of the
show in
6 Background and Related Work
AI audits. The study of Al audits has grown rapidly in the past few years 50 the range of methods and objectives for audits varies greatly, many agree that audits serve an important function in AI accountability, whether conducted by civil society groups, private actors, or regulators
25
51
Although
48 Researchers have identified multiple challenges to conducting audits 25 including
the limited access granted to third-party auditors [57 17 [6], conflicts of interest that can arise due to
financial ties between auditors and auditees 20 15), poor researcher protections 42), and difficulties
in verifying the veracity of self-reported information
58 22 60). Among these issues, work seeks

---

to address the difficulties of producing (convincing) evidence in resource-, data-, and information- constrained settings. Specifically, the auditor (or claimant) is often at a disadvantage when producing evidence that surpasses the relevant (context-dependent) standard in that (i) they typically possess fewer resources than the other party (e.g., model developer), (ii) they have limited access to the system they seek to audit, and (iii) they may lack technical expertise or domain knowledge.
Disparate impact doctrine. In the US, disparate impact is legal doctrine used to demonstrate that a facially neutral practice or practice discriminates against a protected group by showing that it has a disproportionately negative impact on them, even if there is no intent to discriminate [2] It is often contrasted with disparate treatment, which concerns intentional discrimination [8] Under disparate
impact doctrine, plaintiffs typically show that a practice has disparate impact by providing statistical evidence. This doctrine was one of the main drivers behind the field of algorithmic fairness and the development of outcome-hase -hased fairness metrics
27
There is precedent for assessing disparate impact using a guideline known as the Four-Fifths Rule, which states that practice is has disparate impact if the selection rate for protected group is less than four-fifths of the selection rate for the group with the highest rate. Although the use of selection rates to assess discrimination is highly debated (as are fairness metrics, more broadly), selection rates are often used in disparate impact analyses because they provide a simple and intuitive way to compare group outcomes that does not suffer from a selection bias problem (that makes the estimation of true positive and false positive rates difficult). Selection rates remain popular choice in practice, e.g., see NYC's Local Law 144 of 2021.
Less discriminatory alternatives (LDAs). The LDA requirement arose in US anti-discrimination law, as described further in Section 2 It has become a critical part of disparate impact doctrine following the landmark Griggs V. Duke Power Co. decision in which the Supreme Court held that discrimination can occur even in the absence of intent (i.e., facially neutral practices can also be discriminatory) (12). Within disparate impact doctrine, the LDA requirement urges decision makers to consider less harmful alternatives among equally effective options as a structural way to assess and remove unnecessary discrimination [9]. We refer readers to Lamber (39), not [.] Rutherglen [54] for further analyses of the role of LDAs in disparate impact claims. We further discuss this in Appendix E
Less discriminatory algorithms. Recent works examine the LDA requirement as it applies to algorithmic decision-making Gillis et al. [24] cast the search for LDAs as an mixed integer program, then directly search for algorithm that minimizes error rate disparity subject to performance criteria. Laufer et al. [40] provide theoretical insights showing, among other takeaways, that identifying the least discriminatory alternative is NP-hard and may only constitute an LDA for the distribution or
data over which it was derived. Our work mirrors the motivation of Gillis et al. (24) in that we seek to provide an operationalizable method for plaintiffs. However, as both Gillis et al. [24] and Laufer et al. [40) note, producing an LDA is computationally expensive and thus existing approaches do not scale to for large models, which are increasingly important to audit. Our work adds to this space by providing tool for plaintiffs with limited compute and data.
Performance-Fairress Pareto frontiers (PFs). In many settings a trade-off between fairness and performance emerges [10] 43 37.. In such cases, the performance-
PF characterizes the best fairness and performance that can be simultaneously achieved (i.e., the best performance than can be achieved for a given fairness level, or vice versa). Various works propose methods for improving Pareto optimality or tracing out the performance-fairness PF, including Navon et al. 47), Ruchte and Grabocka [53), Singh et al. (56). Rothblum and Yona (52). Kamani et al. [34), Liu and Vicente Chzhen and Schreuder [19, Zeng et al. [62.. In many of these works, the goal is to develop efficient methods for tracing out the PF, but they still assume the resources needed to train at least one model. In our work, we seek to improve scalability in a different sense: one can trace out the PF in amall-model, low-data regimes and extrapolate the PF to urge-model, large-data regimes (and thus one does not even need the resources required train a large model). To the best of our knowledge, none of the existing works provide closed- form expressions for the fairness PF.
Scaling laws. Scaling laws have been widely studied in the context of deep learning, typically used to predict how model behavior improves with increasing model size, data, and compute [31 36. 32 7 In this work, we seek to provide a theoretically grroundddeg scaling law for the loss-fairness PF that allows one to fit the PF with small models and small datasets, then extrapolate to larger models and datasets with the help of the power law (that applies to loss) found in the works above.
10

---

Acknowledgments and Disclosure of Funding
We thank members of Percy Liang's group and Daniel E. Ho's RegLab for their valuable feedback during the early stages of this project. This work is supported by the CSET Foundational Research Grant on audit methods for frontier models.
References
[1] The Civil Rights Act of 1991 and Less Discriminatory Alternatives in Disparate Impact Lit- igation. Harvard Law Review, 106(7):12111168, 1993. URL http://www. jstor org/ stable/1341935
[2] Note, State v. Loomis: Wisconsin Supreme Court Requires Warning Before Use of Al- gorithmic Risk Assessments in Sentencing. Harvard Law Review, 13365) Mar. 2017. URL httte:://aarvarrllaeeevvvw wttp:/wwwwwweeeeeeooo//ooooooooe http://pppooottetttpppaaaa/////p
1530 1537 _ odff
[3] Cahoo v. SAS Analytics Inc., January 2019.
[4] Bauserman v. Unemployment Insurance Agency, July 2022.
[5] Complaint and Request for Investigation, Injunction, and Other Relief Submitted by the Elec- tronic Privacy Information Center (EPIC), January 2024.
[6] A. Agarwal, A. Beygelzimer, M. Dudík, J. Langford, and H. Wallach. A reductions approach to fair classification. In International conference on machine learning, pages 60-69. PMLR, 2018.
[7] Y. Bahri, Dyer, J. Kaplan, Lee, and U. Sharma. Explaining neural scaling laws. Proceedings of the National Academy of Sciences, 121(27)xe31 18781111 2024.
[8] S. Barocas and A. D. Selbst. Big Data's Disparate Impact. California Law Review, 104(3): 671-732, 2016. doi: 10.15779/238BG31. URL hhttps///wwtt yale. adw/homes/
BarocasSelbst..pa
[9] J. Bastress, Robert M. The Less Restrictive Alternative in Constitutional Adjudication: An Analysis, Justification, and Some Criteria. Vanderbili Law Review, 27(5):971-1005 1974. URL
vanderbilt...... beanderbltt.euu//l////eee
iss5/3
[10] D. Bertsimas, V. Farias, and N. Trichakis. The price of fairness. Operations research, 59(1): 17-31, 2011.
[11] E. Black, L. Koepke, P. Kim, S. Barocas, and M. Hsu. The Legal Duty Search for Less Discriminatory Algorithms. arXiv preprint arXiv:2406.06817 20264
[12] A. W. Blumrosen. Strangers in Paradise: Griggs Duke Power Co, and the Concept of Employment Discrimination. Michigan Law Review, 71(1):59-110 1972.
[13] S. Boucheron, G. Lugosi, and P. Massart. Basic Incqualities. In Concentration Inequalities:
A Nonasymptotic Theory of Independence. Oxford University Press, online edition edition, 2013. doi: 10. 00.0099/ccpo0o0s0/77770099333333 acprof: : oso 20t./998881999555555. 003. 0002 Accessed: 2025-05-11.
5003..0000000 003.0002. htthttss://doi org. /10 1093/
[14] Brown, J. Davidovie, and A. Hasan. The algorithm audit: Scoring the algorithms that score us. Big Data & Society, 8(1):2053951720988
2021.
[15] F. P. Calmon, D. Wei, B. Vinzamuri, K. N. Ramamurthy, and K. R. Varshney. Optimized pre- processing for discrimination prevention. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, pages 3095-990444 Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964
[16] Casper, C. Ezell, C. Siegmann, Kolt, L. Curtis, B. Bucknall, A. Haupt, K. Wei, J. Scheurer, M. Hobbhahn, et al. Black-box access is insufficient for rigorous ai audits. In Proceedings of the 2024 ACM Conference on Fairness, Accountability, and Transparency, pages 2024.

---

[17] S. H. Cen and R. Alur. From Transparency to Accountability and Back: A Discussion of Access and Evidence AI Auditing. In Proceedings of the 4th ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization, pages 1-14, 2024.
[18] A. Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big data, 5(2):153-163, 2017.
[19] E. Chzhen and N. Schreuder. A minimax framework for quantifying risk-fairness trade-off in regression. The Annals of Statisties, 50(4):2416-2444 2022.
[20] S. Costanza-Chook I. D. Raji, and J. Buolamwini. Who Audits the Auditors? Recommendations from field scan of the algorithmic auditing ecosystem. Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 1571-1583, 2022.
[21] M. Feldman, S. A. Friedler, J. Moeller, C. Scheidegger, and S. Venkatasuuramaniin. Certifying and Removing Disparate Impact. In Proceedings of the 21th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD '15, pages 259-268, New York, NY. USA, 2015, Association for Computing Machinery, ISBN 9781450336642. doi: 10.1145/ 2783258.2783311 URL https://doll org/10 1145/2783258 2783311
[22] O. Franzese, A. S. Shamsabadi, and H. Haddadi. OATH: Efficient and Flexible Zero- Gero-Knowledge Proofs of End-to-Enn -en------nndd ML Fairness. arXiv preprint arXiv:2410.02777, 2024.
[23] S. Friedler, S. Choudhary, C. Scheidegger, E. Hamilton, S. Venkatasuubramanian, and D. Roth.
A comparative study of faimess-enhancing interventions in machine learning. In FAT 2019 Proceedings of the 2019 Conference on Fairness, Accountability, and Transparency, FAT 2019 Proceedings of the 2019 Conference Fairness, Accountability, and Transparency, pages 329-
338. Association for Computing Machinery, Inc, Jan. 2019. doi: 10. (145532875603288758 Publisher Copyright: @ 2019 Copyright held by the owner/author((s) 2019 ACM Conference on Fairness, Accountability, and Transparency, FAT* 2019; Conference date: 29-01-2019 Through 31-01-2019.
[24] T. B. Gillis, V. Meursault, and B. Ustun. Operationalizing the search for less discriminatory alter- natives in fair lending. In Proceedings of the 2024 ACM Conference on Fairness, Accountability, and Transparency, pages 377-387, 2024.
[25] E. P. Goodman and J. Trehu. Algorithmic auditing: Chasing Al accountability, Santa Clara High Tech. LJ, 39:289, 2022.
[26] S. S. Grover. The Business Necessity Defense in Disparate Impact Discrimination Cases. Georgia Law Review, 30(2):387-430, 1996.
[27] M. Hardt, Price, and N. Srebro. Equality of opportunity in supervised learning. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS' 16, pages 3323-3331, Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN 1781510838819.
[28] C. Harris and K. West-Faulcon. Reading Ricci: Whitening Discrimination, Racing Test Fairness. UCLA Law Review, 58:73-150, 2009.
[29] M. Hart. From Wards Cove to Ricci: Struggling Against the "Built-in Headwinds" of a Skeptical Court. Wake Forest Law Review, 46:261-278, 2011.
[30] D. Harwell. you deserve the job. https: h www. wwwhingtonpost. www http:///t...ooeeeeeoooo/o/////// ai ai-hiring-face scanning- wwaianiinnggggggrii algorilthhhteeee whm.rrtttmmmoo increasingly www.:/ngggyy.cccedeeeeeeeeeeeeee wot.ou/eeeeeeeerrooo---eeeeeeeea
A face-scanning algorithm increasingly
decides whether
The Washington Post, November 2019.
URL
[31] J. Hestness, S. Narang, N. Ardalani, G. Diamos, H. Jun, H. Kianinejad, M. M. A. Patwary, Yang, and Y. Zhou. Deep learning scaling is predictable, empirically. arXiv preprint arXiv: 004099 2017.
[32] J. Hoffmann, S. Borgeaud, A. Mensch, E. Buchatskaya, T. Cai, E. Rutherford, D. d. L. Casas, L. A. Hendricks, J. Welbl, A. Clark, et al. Training compute-optimal large language models. arXiv preprint arXiv:2203.15556 2022.
12

---

[33] C. C. Jones, Systematizing Discrimination: AI Vendors & Title VII Enforcement. University of Pennsylvania Law Review, 171(1):235- 265. 2022. URL URLhttpss//scholarshhpp.. 1aw
Law upenn
edu/penn, law__eaweeeeeeeeeeeeeeeeeeeeeeee wwwwww/vvl11///////e
[34] M. M. Kamani, R. Forsati, J. Z. Wang, and M. Mahdavi. Pareto Efficient Fairness in Supervised Learning: From Extraction Tracing. arXiv preprint arXiv22104.01634, 2021. URL https
7/arxiv. www.oogg///////eeo
absa /2044. 01634
[35] F. Kamiran and T. Calders. Data preprocessing techniques for classification without dis- crimination. Knowl. Inf. Syst. 33(1):1-33, Oct. 2012. ISSN 0219-1377. doi: 10.1007/ s 110115-011-0463- URL /ttpss/s:///oi 00t/:/00..0000110111--1110-66660
[36] J. Kaplan, S. McCandlish, T. Henighan, T. B. Brown, B. Chess, R. Child, S. Gray, A. Rad- ford, J. Wu, and D. Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.083611 2020.
[37] J. S. Kim, J. Chen, and A. Talwalkar. FACT: A diagnostic for group fairness trade-offs. In International Conference on Machine Learning, pages 5264-5274, PMLR, 2020.
[38] M. S. Lam, A. Pandit, H. Kalicki, R. Gupta, P. Sahoo, and D. Metaxa. Sociotechnical audits: Broadening the algorithm auditing lens to investigate targeted advertising. Proceedings of the ACM on Human- Computer Interaction, 7(CSCW3):137,,22 2023.
[39] C. Lamber. Alternatives to Challenged Employee Selection Criteria: The Significance of Nonstatistical Evidence in Disparate Impact Cases Under Title VII. Wisconsin Law Review, pages 1-58. 1985.
[40] B. Laufer, M. Raghavan, and S. Barocas. Fundamental Limits in the Search for Less Discrimi- natory Algorithms and How to Avoid Them. arXiv preprint 24X. 2024.
[41] S. Liu and L.. N. Vicente. Accuracy and fairness trade-offs in machine learning: a stochastic multi-objeccive approach. Computational Management Science, 19(3):113-533 2022. doi: 10. 101100777612257--22--0044----- URL ptttps://linde www.iiikkkiiiiiiii inger.gr...m com httpm//atccleeeeeeeee
810287-022-00425-
[42] S. LLongrre, S. Kapoor. K. Klyman, A. Ramaswami, R. Bommasani, B. Blili-Hamelin, Y. Huang, A. Skowron, 7.-X. Yong, S. Kotha, et al. safe harbor for Al evaluation and red teaming. arXiv preprint arXiv:2403.0448 04893, 2024.
[43] A. K. Menon and R. C. Williamson. The cost of faimess in binary classification. In S. A. Friedler and C. Wilson, editors, Proceedings of the 1st Conference on Fairness, Accountability and Transparency, volume 81 of Proceedings Machine Learning Research, pages 107-118. PMLR, 23-24 Feb 2018.
[44] D. Metaxa, J. S. Park, R. E. Robertson, K. Karahalios, C. Wilson, J. Hancock, C. Sandvig, et al. Auditing algorithms: Understanding algorithmic systems from the outside in. Foundations and TrendyO in Human- Computer Interaction, 14(4):272-344 2021.
[45] National Association of Insurance Commissioners. Insurance topics: Big data. https://
content.co petteett.aaic.oog/nnnne www.aaa..wwg.sssaaaaeooooooooooa
[46] National Association of Insurance Commissioners (NAIC). 2023 Life Artificial Intelli- gence/Machine Learning Survey Report, December 2023.
[47] A. Navon, A. Shamsian, G. Chechik, and E. Fetaya. Learning the pareto front with hypernet- works. arXiv preprint arXiv:2010.04104, 2020.
[48] V. Ojewale, R. Steed, B. Vecchione, A. Birhane, and I. D. Raji. Towards Al accountability infrastructure: Gaps and opportunities in Al audit tooling. In Proceedings of the 2025 CHI Conference Human Factors in Computing Systems, pages 1-29, 2025.
13

---

[49] D. Ozkul. Automating Immigration and Asylum: The Uses of New Technolo- gies in Migration and Asylum Governance Europe. Research report (algo- rithmic fairness for asylum seekers and refugees project), Refugee Studies Centre, University of Oxford, 2023. URL https://wwrr rsc. ac. ww/ffllesffiles-11 automating- Aamiigratiin -nwllon--nn--eee and- asylum af 2affrr9--a 1-2.99111...10 pdf
[50] I. D. Raji, A. Smart, R. N. White, M. Mitchell, T. Gebru, B. Hutchinson, J. Smith-Loud, D. Theron, and P. Barnes. Closing the AI accountability gap: Defining an end-to-end frame- work for internal algorithmic auditing. In Proceedings of the 2020 conference on fairness accountability, and transparency, pages 33-44, 2020.
[51] I. D. Raji, P. Xu, C. Honigsberg, and D. Ho. Outsider oversight: Designing a third party audit ecosystem for ai governance. In Proceedingy of the 2022 AAAI/ACM Conference on AI, Ethics, and Society, pages 557-571, 2022.
[52] G. N. Rothblum and G. Yona. Consider the Alternaties:: Navigating Taimess-Accuracy Tradeoff's Disqualification. arXiv preprint arXiv:21 10.00813, 2021.
[53] M. Ruchte and Grabocka. Scalable pareto front approximation for deep multi-objective learning. In 2021 IEEE international conference on data mining (ICDM), pages 1306-1311. IEEE, 2021.
[54] G. Rutherglen. Disparate Impact, Discrimination, and the Essentially Contested Concept of Equality. Fordham Law Review, 74(():2313-233 2006.
[55] M. Selmi. Was the Disparate Impact Theory a Mistake? UCLA Law Review, 53:701-782, 2006.
[56] G. Singh, Gupta, M. Lease, and Dawson. A Hybrid 2-stage Neural Optimization for Pareto Front Extraction. arXiv preprint 1rXiv:2101.11688 2021.
[57] I. Solaiman. The gradient of generative Al release: Methods and considerations. In Proceedings of the 2023 ACM conference on fairness, accountability, and transparency, pages 111-122, 2023.
[58] G. Tang, W. Tan, and M. Cai. Privacy-preserving and trustless verifiable fairness audit of ma- chine learning models. International Journal of Advanced Computer Science and Applications, 14(2), 2023.
[59] Terzis, M. Veale, and Gaumann. Law and the Emerging Political Economy of Algorith- mic Audits. In Proceedings of the 2024 ACM Conference on Fairness, Accountability, and Transparency, pages 1255-1261 2024.
(60] Waiwidiikhit, I. Stoica, Sun, T. Hashimoto, and D. Kang. Trustless audits without revealing data or models. arXiv preprint arXiv:2404.04500, 2024.
[61] M. B. Zafar, I. Valera, M. G. Rogriguez, and K. P. Gummadi. Fairness constraints: Mechanisms for fair classification. In Artificial intelligence and statistics, pages 962-970. PMLR, 2017.
[62] X. Zeng, G. Cheng, and E. Dobriban. Bayes-optimal fair classificattin with linear disparity constraints via pre-, in-, and post-processing. arXiv preprint arXivv2402.028877 2024.
[63] Zliobaite. A survey on measuring indirect discrimination in machine learning. CoRR, 2015.
/awxxv.ivv.. org
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims made in lines 11-23 of the abstract and the "Main contributions" section of the introduction reflect the contents of Section (aaio And Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
Yes, in Appendix A
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

Justification:
For the theoretical results in Section 4 the assumptions are provided in that same section and the proofs are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
These details are given in Section 5 and Appendix J
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
16

---

Answer: [No]
Code and data is not the main contribution of this paper. We provide details needed to reproduce the simulations and experiments, including in the supplemental material. relevant code snippets.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ ptaaps..c/publlc/gguudeee/////// hettc////ggidee//eeeuuubbbn Cate///oeeeSeeaaaaaaeeee ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments 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) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We run very small-scale experiments, and we provide all relevant details in Section and Appendix
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 level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: In the experiments we plot empirical Pareto frontiers, for which one wants to see the minimum value (and not the average), so there are no estimated quantities for which we would report error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
17

---

The method for calculating the error bars should be explained (closed form formula, call 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.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Yes, we discuss our requirements in the Appendix.
Guidelines:
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, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well 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 into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:///uuurp...cpppaaaactccccaa
Answer: [Yes]
Justification: The paper involves theory and some experiments on synthetic data. It does not involve human subjects any address ethically sensitive topics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Potential positive societal impacts are clear from the problem statement and discussed in detail in the introduction and background. Limitations are given in Appendix ^
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
18

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses such risks as the main contribution is theoretical result and we do not release any data or models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
19

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
batasets.papersstt
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release assets. It provides a theoretical result and some simulations/experinnnts to support that result. No datasets or models are released.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper involves neither crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This paper involves neither crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
20

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
21

---

A Conclusion, Limitations, and Future Work
In this work, we tackle the problem of resource-informatiion asymmetry in Al audits and legal cases involving AI. We focus our discussion on Title VII's "less discriminatory alternative" (LDA) requirement as a case study exhibiting how claimants often face a steep uphill battle in order to meet their evidentiary burden (as noted in previous works 24 40). We are motivated by this issue to develop tools and methods to reduce the hurdles claimants face. Our main contributions are (I) to cast the problem of finding an LDA as one of estimating the arrformance-faimeer to provide novel technical result that, to our knowledge, provides a first closed-form expression for the aerformmacc-fairreee performance frrfrmmance-airnees PFs that directly addresses both the resource and information asymmetry issues posed by the LDA requirement.
Pareto frontier (PF), (2)
PF, and (3) to show how this result can be used as a scaling law for
Next, we identify the assumptions (both technical and conceptual) of our work, which highlight potential limitations and avenues for future work:
1. Our theoretical analysis is conducted for specific notions of fairness and performance. We justify these choices in Section 3 and Section 6 and we believe that future work tackling other definitions would be valuable. Our work also relies on disparate impact and business necessity being measurable; we do not preclude the use of multiple metrics to measure fairness or performance, and studying the more complex multi-objective optimization problem in which there are more than two metrics of interest would be compelling future work. We are unsure how address settings in which fairness and performance are not measurable, and we welcome future work that explores the LDA requirement in such settings (e.g., when fairness is ordinal).
2. Our result applies for the DGP given in Section 4.1 A compelling direction for future work would be to determine how well our result holds, for real data and even for other DGPs. Although stylized, the DGP we study still allows for significant generality. We also recommend future work, both theoretical and empirical, on the form of the loss loss- poss-performance PF for other DGPs.
3. Relatedly, our main proof technique that allows us to obtain an analytic expression without strong assumptions on the inputs or the model class is to use a notion of "duality" that approximates Pareto-optimal classifiers with varying fairnsss characteristics using Bayes optimal estimators artificially constructed training distributions. To do so, use ( to "tilt" the (artificial) train distribution. As one explores other DGPs, one could also explore (i) the conditions under which this duality holds and (ii) alternative ways of tilting the training distribution.
4. A. to hold in our experiments. Given that this assumption does not directly depend on the experimental choice of data generating process (DGP), this is strong evidence supporting it. However, we suggest two directions of exploration: (i) further theoretical work to understand when this assumption may not hold, which may result in additional term in (3) that allows Assumption 4.1 to be removed and therefore strengthens the result; and (ii) empirical investigations to identify when this assumption breaks down in practice.
5. Our result (3) is an upper bound. Although it is tight in some sense (that it holds with equality for some g). we believe a compelling direction for future work is to identify a tighter bound.
6. As mentioned in Section 4.2 the form of B that we adopt is borrowed from the literature on large language models. One could explore alternative forms of B that may be more appropriate for other model classes and sizes.
We identify several other considerations and extensions:
1. A defendant may be able to argue that, in failing to produce specific less discriminatory alternative (LDA), this approach does not pass the necessary evidentiary standard. As noted in Footnote 4 if the court does not consider this evidence strong enough to satisfy the LDA requirement, we hope that it can be used to support the plaintiff's 's requests for further discovery, including data and model access that they may be initially denied.
2. Our experimental results are limited. There are several directions for future work, including conducting experiments on real datasets, further stress testing the limitations of our theoretical results, and running experiments at greater scale.
3. Our approach requires access to some training and test data. We feel that this requirement is unavoidable, and our contribution is to significantly decrease the amount of data that the
22

---

claimant needs. However, we acknowledge that this requirement may still pose a hurdle and leave the exploration of techniques that further mitigate the data requirements to future work.
4. The empirical PF is, in a sense, a random variable that depends on the sampled training data and the randomness of the training procedure. One could explore the confidence intervals of the estimated PF that result from different training runs. Similarly, our theoretical result does not have notion of uncertainty; future work could explore high-probability version of our result.
B More Information on LDAs
B.1 LDAs Beyond Employment Law
The "less alternative" requirement expands beyond employment to areas including housing, lend- ing. disability, and even environmental justice. The Department of Housing and Urban Development (HUD) has a 2023 rule returning to the 2013 Fair Housing Act standard under which actuarially sound housing- innsing-insurance policies are unlawful if an equally effective, less discriminatory practice is available. The Consumer Financial Protection Bureau's 's (CFPB) 2023 Fair Lending Report requires lenders to proactively search their credit-scoring scoring models for LDAs even in the absence of litigation. A closely related duty appears in disability law; Equal Employment Opportunity Commission (EEOC) guidance under the American Disabilities Act (ADA) obliges employers to adopt any "reasonable accommodation" that meets business needs without exclusion, effectively functioning as an LDA requirement. In environmental justice, permits to proposed projects may denied if a less harmful to human health and the environment exists (an "environmentally preferable alternative") under National Environmental Policy Act (NEPA).
Beyond the US, comparable concepts exist. The EU employs the principle of proportionality in discrimination cases, requiring that measures be appropriate and necessary, but also that the respondent show "there is no practicable alternative." One may argue that the LDA requirement parallels the EU's "data minimisation" requirements under the General Data Protection Regulation (GDPR), requiring data processing to be "limited to what is necessary." In Canada, the Meiorin test examines whether the employer has accommodated affected groups to the point of undue hardship. South Africa, drawing from Section 36 of its Constitution, applies limitations analysis that considers whether less restrictive means could achieve policy objectives without discriminatory impacts.
B.2 Example: Challenges of finding an LDA
To illustrate the challenges involved in finding an LDA, consider the following example. Consider an Al tool that uses large language and video models to screen application packages, which contain unstructured text and video interviews. Suppose that the plaintiff' successfully establishes that the tool disproportionately favors candidates from a specific demographic group using one or more chosen metrics, such as the demographic parity gap (Step 1). Suppose further that the defendant successfully shows that the tool improves their business outcomes by reducing the amount of time to screen applicants while surfacing candidates that are well suited for each job (Step 2).
At this point, the plaintiff can only win the case if they are able to meet the LDA requirement (Step 3). They meet several hurdles in their attempts:
1. The plaintiff first attempts to train their own LDA. They quickly realize that training comparable model to the defendant's 's production, ofate-of-the--ae art model requires significant compute.
2. Even if they are able obtain the necessary compute, training model requires access to good data. The plaintiff learns that collecting enough training data is prohibitively expensive, so the plaintiff requests it from the defendant (or the developer if the data is owned by a third party). The defendant and/or developer claims that sharing their training data is tantamount to releasing trade secrets and compromises user privacy, and the judge agrees. 8
3. The plaintiff turns to a third option. They request access to the contested model so that they can use it starting point to locally search for an LDA by, e.g., fine-tuning or probing its internal
*When the owner of the information is a third party that is not a direct party to the lawsuit (e.g., the plaintiff' sues an employer, who outsources the Al model development to third party), it can be even more difficult to obtain this information. Further discussion in Footnote 6
23

---

representations. The defendant and/or developer claims that this, too, violates trade secrecy, and the judge agrees.
4. Finally, the plaintiff considers establishing the existence of an LDA by characterizing the range of possible classifiers, in the same spirit as analyses in [24 40), but discovers these approaches work well on finiteddimensional, categorical inputs but not on unstructured ones.
At this point, the plaintiff may throw in the towel, conceding that they cannot meet the LDA requirement because the burden of providing an LDA is too high, especially given the limited resources, data, and model access that they possess.
B.3 On the choice of fairness metric
In Section we note that we choose demographic parity as our fairness metric, but in general this choice is context-dependent and debated upon. History indicates that demographic parity is a likely choice by courts, selection rates (the backbone of the demographic parity metric) have appeared across multiple contexts, including the Four-Fifths Rule from 1978 to NYC's Local Law 144 of 2021. Moreover, selection rates do not suffer from the same selection bias issues as other metrics (see Section 6 for further discussion). Similarly, we study BCE loss because it is widely used as the performance metric for classifiers and is precisely what developers/companies optimize in training.
C
Intuitions for Theoretical Assumptions and Results
C.1 Intuition for Assumption 4.1
This assumption essentially implies that each Pareto-optimal model f that belongs to model class F symmetric with respect to the DGP, which one would expect to hold for large models that serve as universal function approximators. That is, the "distance" between the loss-minimizing f in F learned on q and the Bayes optimal classifier g [2, a) may depend on the model class F and the number of samples D it is trained on, but not q. As discussed in the previous section, this may not always hold exactly (e.g., when some q ss are trivial to learn), but we believe it to be reasonable for deep learning models trained on sufficiently sophisticated tasks. The second condition in Assumption 4.] implics that ff is symmetric with respect to A. This condition does not imply that fits group = as well the other group A = 1, but that the "distance" between f and q(1 x, a) is symmetric with respect to A; to see this, observe that it "compares" f to the Bayes optimal classifier for g. which itself may be skewed 9
C.2 Key Proof Intuition for Theorem 4.2
One might try obtain the PF by solving the constrained minimization Sa arg minser L(pX.A,Y subject to A(px.A.y, = A, tten computing C(px.AYY,AA) for all A. However, this problem is highly difficult to solve analytically and generally requires strong assumptions on the model class F. Alternatively, one may wish to iterate over all possible f and compute their corresponding loss and fairness gap values (akin [T 24).. but this approach is only feasible for finite-dimensione categorical features where the number of possible classifiers is small
40 this approach does not scale for large models with high- digh-dimensional, unstructured inputs.
To address these issues, we use a technique that often motivates in in-processing methods and fair representation learning [35] 21 [5]: that one can induce a fairness gap A by constructing an artificial train distribution + p. In other words, we can transform the constrained minimiza- tion problem min L(px.A,Y,J) subject A(xX,AYY f) A into unconstrained problem minfer L(gx,A,v, f), where "tilts" so that the solution ff to the latter problem has the desired fairness gap (pxx,,, the developer actually uses to train their model-g is abstraction T6 To provide further intuition,
A. Note that "tilting" q does not have any bearing what distribution
"The second condition can he loosened to be equality with a constant shift, but we remove this for simplicity. It will introduce additive constants throughout our proof that are ultimately incorporated into the constants and thus do not affect the main result.
We further emphasize that, although this discussion seems to suggest that we are restricting the allowable train distribution, that is not the case. We are simply imposing an effective train distribution as a proof technique analytically characterize the PF.
24

---

recall that there is known equivalence between minimizing an objective function subject to constraint and minimizing the Lagrangian. Our approach leverages another notion of duality where minimizing Ep [loss]] subject to fairness constraint is equivalent to minimizing R. [loss] for some
This change of measure allows to characterize Pareto-optimal classifer f for given fairness gap A in terms of the Bayes optimal classifer q(1 æ, a) for the used to induce A. Then, we apply Theorem G.I where Assumption 4.1 maps to the condition on S in Theorem G.1 In summary, our approach alleviates the two challenges described above: for (i), we use the Bayes optimal classifier on the effective train distribution q simulate the constrained loss- mossmmiimizztion problem that is difficult to solve analytically; for (ii), we avoid imposing strong assumptions on the model class F by using a milder model symmetry assumption.
D Detailed Procedure for Applying the Scaling Law to the LDA Requirement
Here we give details for the high-level procedure described in Section 4.2 Given training data, test data, and compute budget well as estimate of N+ and D+. as described in Section 3 claimant would apply the scaling law as follows:
1. Given a small model class N and small training dataset D= empirically trace out the loss- fairness PF for N and D To do so, train set of models, each of which is obtained by minimizing the BCE loss on 2 plus a regularizer that encourages demographic parity. Varying the weight on the regularizer induces different fairness gaps. For each trained model, compute its loss and fairness gap on the given test data. Thus, each model marks point on the loss vs. fairness gap plane. The lower convex hull of these points forms the empirical PF. The number of trained models as well as N and D should be chosen based on onc's 's compute budget.
2. Repeat this for different values of N and D as permitted by one's compute budget.
3. Using these experiments, fit the constants C₁ through O7 each empirical PF using the following scaling law:
loss A = C1 + C2/(N + (C
C3 Co lo C7 (3. log(Cr
C..Co Cs (1-
+ +C, (C- (1 ((1--)(1-C+a))
211-C++A A)²
2(C - A)
with appropriate values for N and D Note that C3s and C4 are often set to 0.5
32
4. Once estimates of C₁ through C7 have been obtained, one can extrapolate the PF for the contested model by using the same functional form as above, except substituting N+ and D+ for N and D
5. Alternatively, if one is given a specific loss-fairness pair (loss( A), one can use the functional form above to determine the values of N+ and D such that (loss A), A) lies on the PF. This would tell the claimant how many resources the defendant needs to achieve that pair of values II
Given that there are only constants to fit, one could fit the scaling law by training as few 7 small, high-quality models. practice, the more models, the better (see discussion of Step below).
Note on implementation. We note that our approach "fails gracefully" in that it is conservative: a claimant finds the contested model is 8-far from the PF, then is at least that far. There are two reasons why our approach is conservative. First, the empirical PF is always conservative by definition; there may be (and almost always are) models that Parcto dominate the models one finds empirically. Second, the expression in Theorem 4.2 is inequality; it gives an upper bound on the loss of Pareto-optimal model for a given fairness gap.
Returnnng to Section 3 this analysis relies on the mild assumption that the PF improves monotonically as N and D increase. By our result (Theorem (.2)). this holds true because B(F, D). which is the only term that depends on the model class and dataset size, decreases N and 1) increase.
25

---

Considerations for Step 1. There are multiple ways to trace out the PF empirically. For example, what we describe above is known as linear scalarization. Many works explore other methods (cf. Section 6). There are two main ways that the choice of method affects the claimant's 's results: (1) some methods are better at finding Pareto-optimal models across a wide range of fairness gaps, and (2) some methods find them more efficiently without having to train many models. Thus, a good method will help the claimant get as close to the true PF as possible (which can only help the claimant increase the gap between the contested model and the PF and thus strengthen their case) while training as few models as possible (and thus using as few resources as possible). Our scaling law is plug-and-play: as the methods for finding Pareto-optimal models efficiently improve, too does our procedure.
Although not strictly necessary, re-running Step on different values of N and D- will generally improve the estimates of C₁ through Cz. There is a trade-off here: for a fixed compute budget, one can either run Step multiple times with different (N-, D)) values, or run it once with a N- and D- that are as close to N+ and D+ as possible. One should plan accordingly based on one's compute budget.
Considerations for Step 2.
Considerations for Step 3. One may find that there are multiple sets of constants that fit the empirical PF well, as we explore in Section [ and Appendix []] One could choose the set of constants that minimize the distance between the empirical PF and the fitted PF. Unintuitively, this might not be the appropriate choice. Recalling that the PF marks the lowest loss for each fairness gap, no observed point can lie below the true PF. Thus, one may wish to use the PF that is as close to the empirical one as possible while lying entirely below it.
@ is well supported by previous works on large models (language models, in particular). As discussed in Section [ our work is intended for large models, as this is where the LDA requirement imposes the greatest burden. One may wish to adjust the form for B appropriate.
Finally, we note that letting B scale with N + D-
E Discussion on the Practicality of the LDA Requirement
Several scholars critically examine the efficacy of disparate impact doctrine and practical application of the LDA requirement. Many observe that identifying precise and legally sufficient LDAs is difficult for plaintiffs [155), and others highlight the inconsistent (and sometimes deferential) application of the business necessity standard by courts that can undermine I.DA-based claims (66). Some factors even discourage employers from seeking less discriminatory alternatives, including the risk of reverse discrimination lawsuits and legal uncertainty following Ricci v. DeStefano (28) 29). Together, these critiques reveal a gap between the aspirations of disparate impact theory and the practical barriers faced by litigants. Our work takes the following perspective: while the LDA requirement remains intact, claimants increasingly need methods to demonstrate the existence of feasible alternatives.
F Helpful Lemmas
Lemma F.1. Let μ and be finite probability measures of the same mass on space Z such that μ is absolutely continuous with respect to v, i.e., μ 4 v. Let l(z) du (z) denote the corresponding
Radon-Nikodým derivative and R(z) == ((z) - 1. Let S Z - respect μ and v. Then,
l be absolutely integrable with
CRv, 0 - E., [RS] = E. (RE,(S
[S]= [S).
Proof. First, since μ and v are probability measures and t is the Radon-Nikodým derivative, [x[ = Et 1] = E. [t] 1 0.
Furthermore, by the definition of R,
E2 RS = [t - 1) = E.(t - [5[ = E [S] [s(.].
Therefore,
Ey Es - E, = 0= ER
where the last equality is consequence of having established that F., [R] = 0. This completes the proof, with the first + in the lemma statement following from the definition of covariance. D
26

---

Lemma F.2 Consider the setup in Section notation in Section 4 and data generating process in
Theorem 4.2
Then,
Cov Px X, = q) X, A 1)) 2
Proof. The covariance is well-defined since p(1 X, and g(1 X, 1) have finite second moments by definition of p and q. To show that the expression is non-negative, we appeal Chebyshev's Association Inequality (see, e.g., 13 Theorem 2.14)), which states that if f and h are real-valued functions that monotonic in the same direction and Z is real-valued random variable, then (Z)) 2 [[F(())E(((( [)]] Thus, Cov(i(Z),
= Bli(Z)j(() [[(i() 2 0.
To get the final result, we map Z, f. and h to quantities in our setup. Let the expectations be taken over p(X|A = 1), let ((X) - p[]|X, 1) a (g(X) - (P), and let (x() - (1|[x, 1) - (gg(X) - ().
Next, set U = g and denote by jr Px|a-1 o g" the pushforward measure of PxJA-1 by Introduce the deterministic functions f(u) = ou - (P) and h(u) = (u <) for E R. Now, since the standard logistic (sigmoid) function is monotonically increasing in its argument, both and are hence nondecreasing real-valued functions. So, Chebyshev's 's Association Incquality applies and gives that Cov, v h()) 2 0.
Finally, because (XX) = f(U) and (X) = h(U). we consequently have that Cov Co (6(X), (X)) = Cov (fv,(((U,, 2 0,
which proves the claim.
Note that the lemma above is where the inequality in Theorem 4.2 arises. It holds with equality when g(X) is almost surely constant.
Lemma F.3. Suppose 7 E (0, 1) is a random variable. Then,
Var(2 (Z)
E[log(1 Z)] = log(1 -E(Z)
+ + (E [(Z )
2(1 EE
and
Var(Z)
Ellog( Z)] log(EE(Z)
2E[Z]2 + + (B [ (ZEE(Z)))
1og(1-2) Proof. Since the function log(1 - 2), E (0. 1) is (at least) three times differentiable, we can compute second order Taylor expansion about value μ E (0, 1):
(z 11)
2
log(1 2) log(1 μ))
(1 E)3 (2 4)3
2(1 11)²
= (z =1)
(= 11)
llog(1 n1)
1 1- p 2(1 11)
3(1 E)3
for some & between μ and z. Then, plugging in the random variable Z for and E[Z] for μl, and taking an expectation, we have
E [ B
E E 2
Ellog(1 Z)] = log(1 E[2))
2(1 - E[
3(1 - E1 3
Var[Z]
log(1 E[()
2(1 - E O (E B[2))1)
where the linear term disappears from the first equality because its expectation is zero. Additionally, all expectations are well-defined because bounded random variables have finite moments of all orders.
The expansion for E[log( 2)] is done similarly.
Lemma E4. Let Z [0, 1], E[2], po E R. and I E R subject to - r. Then,
Var < (mo r) μ4 +
27

---

Proof. Since Z E [0. 2 - 2, < B|Z]. This implies that
Var = - E|Z < B| E[Z]) = pal - pl).
Plugging in μ PAo - -T gives the result.
G Intermediate result
We provide an intermediate result that characterizes BCE loss for any DGP. We present this interme- diate result for two reasons. First, it lends intuition for how our main result is obtained. Second, it does not depend on a specific definition of fairess or the DGP; it can therefore be used as a building block for future works that examine different notions of fairness and DGPs.
We use the same notation as Section 4.1 and repeat it here for convenience. Let p and q denote joint distributions over random variables A, and Y. Let p(1 xz, a) and g( x. a) denote the Bayes optimal classifiers under p and q, respectively. Let (I.(;,)) denote the Kullback-Liehle divergence.
The result below simply decomposes the loss of a classifier ʃ on test distribution into three components. For reasons that will become clear in the following section, we state this result in terms of y and an auxiliary distribution
Lemma G.1. Consider a classifier f. T:M A- - 1]. Consider arbitrary joint distributions p and q over X, A, and Y, where PX,AY < qx,AY Let S(z, a. y) == y ylog(a(1 x. fz, a)) + (1 3) log((1 - q(1 xx, a))/(1 - -(xx,a)) be absolutely integrable. We assume Epx.ar [S(x, a,v). = E B, [S v)1. Then,
L(px,AV, 8 (C(axAr, Llux + RZz (pylo, []] + ((px,AY-PIxx.))
(4)
Interpretation. This result decomposes the loss of an arbitrary classifier f on a test distribution p into three components: (1) the misspecification loss due to the choice of model class F; (2) the loss due to distribution shift between p and q; and (3) the irreducible test loss given by the BCE loss of the Bayes optimal classifier P1 on Px,A,Y, where P1JX.4 4 denotes the classifier that returns Pilx,A (zz, a) on (zz, a). This result follows from a simple telescoping sum that utilizes the definitions of information thcoretic terms and the stated condition involving S.
Why is this useful? Recall that our goal is to derive scaling law of the fass-fiiresss PF. That is, our goal is to produce a closed-form expression of loss, which is the left-hand side of 4 in terms of the fairness gap of on Theorem G.I gets us part of the way there; the next step is to write the right-hand side of (4) in terms of the chosen fairness gap for given DGP.
Understanding the condition on f. We briefly comment on the condition ( a, [,,y]]= = E [2(x, a, v)], which a condition on f. We observe that is the log likelihood ratio between Bernoulli models q(1 | x, a) and f(z, a). such that 1 [S(x, (a. a, v)] is the expected conditional KL divergence between them. In the next section, Assumption 4.1 implicitly asks that this condition hold across all q's that we consider, which implies that Egg A. [St (x, a. n.y)], i.e., that the "distance" (as given by an expected log likelihood ratio) between / and the Bayes optimal s7( xx a) is constant.
When would we expect this to hold true and is it restrictive? One might expect this to hold true if is the model that results from training on g. If f is the result of training on q, then the condition asks that the training procedure and model class result in an f that replicates the patterns its train distribution equally well, regardless of train distribution. In practice, we do not expect this condition to hold exactly; the training procedure and model class may fit some q ''s better than others, e.g., if there exists a q that is trivial to learn. However, models trained on sufficiently sophisticated tasks because deep learning models are designed to serve as universal function approximators across different distributions.
believe this is reasonable condition for large
Importantly, we emphasize that g is not the true train distribution. As discussed in Section 4.1 q is an artificial, auxiliary distribution that gives rise to our main proof technique.
28

---

H Proof of Lemma G.1
Recall that we denote the binary cross-entropy (BCE) loss l of classifier f with respect to a sample (x, a, y) by
e(f, (x, a, y)) (ylog(f( (1 y) log(1 f(x, a)))
Note that f can be a soft classifier that returns values in [0. 1J. Further recall that we denote the expected BCE of I with respect distribution PX.A,Y by
L(px,A, - ly (z, a)) (1 1og f(z,a)))
and this notation -(.,-) is used analogously for other distributions and classifiers.
Proof. We split the proof into four steps.
Step 1: Decomposition. We can decompose the BCE loss of a classifier fe F on a distribution P.YAYY as follows
H(PXAYY (H(PXAY, - - (YXXYY
loss f due distribution shift
(HxxYY (Y 4(x,A))
(6)
train loss of f relative optimal (H A H(px,A, (11x,A)
lass of Bayes optimal X.A due to distribution shift (Hxx, T(x,A) Hpx (I(x,))) difference in test loss of Bayes optimal classifiers
(8)
H(px,AY,PPIx.AA
(9)
ireducible test loss
by simply adding and subtracting terms, where we slightly abuse notation to let q1 x.4 denote a (soft) classifier where the prediction for (x, a) is given by (1)2x, a).
As written below each term, 55 can be viewed as the loss of f due to distribution shift between the train distribution 4..A.Y and test distribution Px.A.Y: (6) is the difference in loss between ff on the train distribution and the Bayes optimal classifier (also relative the train distribution), which can be viewed as the loss due to the choice of model family F; (7) also captures loss due to distribution shift, but for the Bayes optimal classifier of xi (8) gives difference in test loss between the Bayes optimal classifier that is optimal with respect to the train distribution and one that is optimal with respect to the test distribution, which can be viewed some sense as the irreducible generalization loss; and ( gives the irreducible test loss of the Bayes optimal classifier PI (that is optimal with respect the test distribution).
Focusing on just two of the terms above, we have Step 2: Expanding and
E Ex, a.y log f(z, (1 v) log(1 a(),
En. log f(x, (1 log(1 f(x, [or
Er 41 (1-y) qrlx (1|x, a))]
log
En A
v) log(1 (1zx,)
(px.A.((E, (xx_)))xxxx(
J.ay
(y)og((z,)++11- log(1 f(xx, a))) dx da dy
z.a
29

---

(11 log(1 - (11x, dx da
Jaay
(
1 - qy (111xx((()))))0)
))
y log
+ +1 (1- log
(
dr da dy
f(z,a)
1 1-f(x, f(x,a)
(
-1)
Juay
(
1 qy _1xxx
))
ylog
+ (1 (1- log
1 11 --f(xx
dr da dy
f(z,a)
1YIx,A(1 [1,a)
Bax.A
(w),,,,,)) 1) 1))ylog ylog
f(2,a)
1 1r1xx |2,aa
+ (1-y) log
1 f(x,a)
where w(r,,,1)) www..a/a.aa./////.aa.oa.. y). Let
9Ylx,A (1 a.
- Qy ( x, a)
:= w(x,,,,))) and S y log
+11 log
f(z,a) a)
1 f(x, a)
Then, by invoking Theorem F.1 which applies because S is absolutely integrable under the condition given the lemma statement and because PX,AY < QA.AYY-- we have that
A [RS] E. [
[S]
B [S] A [S].
By the condition given in the lemma statement, E Exx.a. [S]
E Exx.a. [S] and hence obtain
E E
[RS]
E A B [S] 0.
where the last equality is because E [R] 0, shown in the proof of Theorem F.I
Step 3: Expanding
The term can be written as
-f 22,0
y log (1]x,a(1|2,0 + (1 - v) log
Qy x. (0) a) A (0/p,,
(x,
dr da dy.
PYJX,A (x)
Substituting for possible values of y E {0, 1] gives
-f
(x.A(z, a) log (0/x,1(0
da da
(0 a)
2,a
[og 4r a)
dr da
(1
x.a
log 01]x.4(0/zz a)
-
dx da
(0
J,a
[og T (1,1,1,1,0, |x, a)
Px.A px..(2,0)pyxxxx(11..0
da
log - x (1 a) (1|x,A1||z,0)
px.((e,0)
(1 (1-2M)x((((zza)))
x.a
+ (111x,a(11z,a) log (1
(1)xxA(1|x,a)
F a [KL. (PY)x,A() ax ( x, a.))
where we use KI. (r [| to denote the KI. divergence between the Bernoullir)) and Bernoulli distributions.
30

---

Step 4: Putting it together.
Combining Steps 1-3,
H(px.A.Y,
5
+
6
+
(qx f) M1xxar,91xx.
+ E Egxapxx
KL (pylzaa a (r)r + P(Ix.)Y.PIxx,A)
which concludes the proof.
I Proof of Theorem 4.2
Proof. In this proof, we use Theorem G.1 to express the BCE loss in terms of the train distribution parameter Ç, then likewise express the demographic parity gap in terms of Ç. Combining these representations allows us to express the BCE loss directly in terms of the demographic parity gap. We note that, by definition of our data-generating process, PX,YY & 4x,A, for all Ç.
Step 1: Simplifying BCE loss. Recall from Theorem
G.1 that
H(x.AY R = (H R XIixxYY.Hix...
KL (pylmna
( PUx.))
We begin by characterizing each component this expression.
First, by Assumption 4.1 H(4 (5) - ((g Av: of (fxx.)) can be written as constant ci (F, that depends only on the model class F and the amount of training data D.
Second, we note that (Px.AY, PI)x,A) a) can also be treated as constant (2()) that depends only on the test distribution p and not the model class F or the train distribution qf. This gives
H(px.Ay,f' (9) =
-1 D) + Ex,axxx,
KL (primna
( + c2(p),
(10)
where
cFF,D) H( f9) H(gx H gfxx (p = H HPXX.AYPPIX.AA
Thus, it remains only to characterize the expected KL divergence term and write it in terms of the demographic parity gap. That will be the goal of the following steps.
Step 2: Rewriting the KL divergence term.
E Expa<px.4
KL
[prizaa
(
o x (1
/ 1,0
(2, (1 (1-PMxX(((2)))) log 1
(1
+ +11xx_(11s; log (1
PY]x,A(1|x,0))
= - (11,) log (1
+ (1 log of (1 +c)(), (1)
where
ca(p) /
Px.A(z,a)((1 - (11x,4(112;01)
31

---

+ ()),
is constant that depends only on the test distribution p. Recalling from data generating process given in Section that p( AA- = 1) =T, (II)
becomes
Bx.arpx,4
KL
Ex.arpxx [11 X a)) log (1 (1-4 a
+ +XrXx (x, a) log or (1/2, + cs(p)
π Bexpxia (1 ( A)) log(1 o Xx az, A))
+ (z, log 8 Ix (1 A) A 4= -1) ca(p), (12)
where the last line follows from the fact that, when A 0, the distribution no longer depends (cf. our data generating process for Y given in Section 4 such that
(p(p) = cp(p) + (1 - x) -Eeppxia [1 (1- - A)) log(1 - (111x,
+ + [r, A) log f (1k,, A) A = 0))
Step Upper bounding KL divergence term. By the definition of covariance,
ExpexIa (1 - Pr]x,a(1|2,, A)) xxpx, (1/r, A)) A A=
-ExopxIA (1 (YxxAax,, A)) A= = 1 EampxI
x (1|2, A)) A log(1 1
+ CoVeNpxIA (1 (11- -1 A)), log(1 - X (1|z, A)) A-
By Lemma R22 and our data-generating process as given the theorem statement and Section the covariance term non-negative. Therefore,
Exspxia (1 PY)x.A(1/2, A)) log(1 1 (1|x,, A)) A A=1
2 Ezmpxja
(1 (1- - a A)) A = Benpxia log(1 (1/x, A = 1]
(13)
One can apply analogous reasoning to show, again, by Theorem F2 that
Exppx a (1 A) log of |x.4 (1|z, A) A A=1
2 E A (1 A) A Ezmpxia
log 1 (1/z, A 1]
(Note that the two applications of Theorem F.2 above are where the inequality in Theorem 4.2 arises. Therefore, if one wishes to remove the inequality or provide high-probability version of our result that holds with equality, one should address Theorem F.2 Therefore, from (1).
KL (priana o mna)]
Eg aappp
S - ERmpxIA [1 -1- - lar, A)) A =1] RaNPxIA log(1 o5 x.A x.A (1/2,, A)) A = 1]
= 1 Be-pxia + Exapxia ( (1/2,, A)
log (1 A|| A A-11=)))))))) + +c((p)
= =-m(1 (p)))) log(1 4 (1 |z,, A)) A A=
-Tcs(p)
log
gy 5 A (1/z, A) / A 1] + cc(p
where co(p) = Ex-PxI LoVIN. A) A= 1].
32

---

Step 4: Moving the expectation inside the log. Then, we apply Theorem F.3 using fyxx (1 I, 1) the Z in the statement of the lemma, and noting that it is random variable that takes values between O and 1, as required by the lemma. For case of notation, let
g6 gy X.A (1/2z A) A =
q = E Em-Px
40 == E
By X.A (1/2, A) A = 0
V = Varz~pxı (r (1/2, | A 1
(14)
Then, Theorem F33 gives
Bm,a-xx.4 KL (priana ( (
S -- - -m(1-cs(p))
loggl -Q1) 2(1 - /1)²
V
Tes(p) (Iog(0))
V
24f
O (BempxiA [[oV Iz, A) @1)²² |-=1)) + cs(p).
(15)
Now that the KL divergence term is upper bounded, we proceed characterize the demographic parity gap, and then substitute it into the KL divergence term.
Step Characterizing demographic parity gap.
The definition of demographic parity gap
A(pxAa, f9) = Ex (f A)IA 1] Ex-px A)) 0f
can rewrite as
Exeoxia (f, A)IA = 11
RRMPXIA [x,
A)IA= =
Exxpx a 1 A)(A 1] - Ex-Ex a l I (1/z A)IA 0]
+ (Rxppxxa (f-(1, A)(A= 1] Exupxia lo 1X. (1 (1|r,, A) 1))
(16)
+ (ExNpxiA 1o (1/1,, A)IA - Exspx (x,, A)(A 0)). (17)
By Assumption 4.1
Epppy (2 A)AA (f
Ez (oy x (1|z,, A))A Ex-pxIa l8y 1 (1]a,A)|A 0).
By our data generating process given in Theorem 4.2 in which A mediates the effect of Ç and larger values of result in lower positive classification rates,
Ex-pxIa | (1/z, A) = 0] 2 E by x (1/0, A) = 1].
for < 2 0. Therefore,
A(px.A.Y 15)
q1-
(18)
Note that if we relaxed the second condition Assumption 4.1 to allow for an additive constant, this would allow to complete analysis but with more bookkeeping, the expression above would have two cases to ensure A 2 0.
Step 6: Combining and rewriting BCE loss terms of A(pX.AYY, fS). this expression for A(px.AY f() from (18) into the BCE loss. From [5 we have
We can now substitute
KI. (pM (
E Eg,a<px,
T Co(D)VV
< <- cs(p)) log(1 + A(Px,AY, +
2(1 T + A(px.AY, f())
33

---

vcs(p)V
TCs(p) log(āo ((xx,Ar, 2( A()
+ cpp) + O (Bzxpxia [ (1 xx, (1, 91)²
AA=1)
We use Theorem F4 with Z gyxx,a (1 I, A) / T1 qo, r A 0o
T1 by
18 and
that the expectations in Theorem F.4 are taken with respect to AX to get
V S (co(p) A)(1 - co(p) + MPx.YY 19),
where cp(p) = qu- Therefore,
Ex Ex,axpx,4 KL (prinna
c 9r12
<1 (1 cs (p)) log(1 1 (p) + APxx,,, (3))
M(1 cc(p)) - APx,AY (9),,,),)))((11 - co(p) + ((xx,ay,
+
2(1 co(p) + A(pxAY,,
-ms log(cep)) - APxx,N {5))
Tes(D)(c<(p) Apxx,Y ())) co(p) + (PxxAY,
2(co(p) APXX,Y, f())2
+ cc((p) +0 (Eepxxia [9 A) -11²² |A=1)
(19)
where we recall all constants:
c2(p) = H(Px,AYXPPIX..
c2(p) = Ex,a-px.A (1 (4), (11x,
c4(p) co(p) -(1 -11-
T) E [1 PYIX (1_ A)) log(1
of X.A (1/2,, A))
(1|z, A) A= 0f
+
cs(p) = E ( [x, == 1]
(p(p) Ez-AxIA
gy)x,a( xr, A) | = 0)
Putting all together, combining
110 and 19
H(px.A, < B(F, D) -c- log(1 c" + A) -c. (1-d) (1_c)oog((" -))
c.c.
c. C. - d))
+ (c" -)(-- - - 2 d + A)
2(c A 1
+ 0 (EMPXII [ff (1 [I] - )1 |
A = 1))
where
B(F,D) : (FF, + (p) + cc(p))
= =c1 (F, D) HIXXAYPIIXA))
(1 T) BuMPIIA
(1 - (4), log of (1|=,, A))
+ + (1 log / x (1/r, A) A o]
Ey,ampx,A [ (1) Pr|x, (1/2,
+ PYIx. (1
34

---

1.25
C=
1.25
BCE Loss
1.00
1.00
C=
0.6
C= 0.5
0.75
0.7
0.6
0.8
0.50
0.7
0.50
0.9
0.8
0.25
0.9
0.25
Faimess Gap
Fairness Gap Budget
Figure 4: Simulations showing the shape of the closed-form expression for the Pareto frontier given in Theorem 4.2 for fixed values of c' 0.5 and c" 0.8 while varying c. The left plot shows the precise closed-form, which is lowest achievable loss among classifiers have exactly the faimeess gap value on x-axis. The right plot shows lowest achievable loss among classifiers that satisfy the faimess gap budger on the x-axis.
0.6
0.6
C-0.1
C
C 0.3
0.4
C' 0.4
0.5
C 0.5
0.6
0.7
0.3
0.3
=
0.8
0.9
0.2
0.9
0.1
0.1
Fairness
Fairness Gap Budget
Figure 5: Simulations showing the shape of the closed-form expression for the Pareto fronticr given in Theorem 4.2 for fixed values of 0.2 and e" 0.8 while varying d. The plot shows the precise closed-form, which is the lowest achievable loss among classifiers that have exactly the faimess gap value on the x-axis. The right plot shows lowest achievable loss among classifiers that satisfy the faimesss gap budget on the x-axis.
c:=A π d' = 1 E Exp ( x. A == 1] E [0, c² ExppxiA of (1/z, A)|A 0] [0. 1]
c, c" 2 O. Note that the constants may not correspond exactly to the stated quantities above, e.g., due to the note below (88)
J Additional Experimental Details and Results
J.1 Simulations
In this section, we provide further simulations.
35

---

0.2
0.2
0.3
C 0.3
0.8
0.4
0.8
C 0.4
0.5
C 0.5
BCE Loss
0.6
C 0.6
0.7
0.6
C 0.7
0.8
0.4
0.4
0.2
Fairmess Gap
Fairness Gap Budget
Figure 6: Simulations showing the shape of the closed-form expression for the Pareto frontier given in Theorem 4.2 for fixed values of 0.2 and c' while varying c". The left plot shows the precise closed-form, which is lowest achievable loss among classifiers that have exactly the faimeess gap value on x-axis. The right plot shows lowest achievable loss among classifiers that satisfy the faimesss gap budger on the x-axis.
We begin by visualizing the behavior the (3. Recall that 33 expresses loss as function of the fairness gap A. where there are four constants: B, c, c', and c". In Figures to we show how the shape of (3) changes for different values each constant, while keeping the other constants fixed and letting e 0. We provide further figures in Appendix
On the left, we plot the theoretically predicted Pareto frontier (PF) that is traced out by finding the lowest-loss classifier for an exact fairness gap A. Specifically, we evaluate the expression in Theorem 4.2, disregarding e, over range A values (typically from 0 to 1). As one might expect, the loss decreases as A increases, then increases when model is forced to have large fairness gap A.
To visualize the lowest loss achievable or below a given fairness gap budget (rather than a fairness gap), we repeat the same simulation as in the left plot, then take the minimum loss value to the left of and including the current x-value (i.e., of the current fairness gap). Therefore, compared the plot on the left, the plot on the right is, by definition, non-increasing. Intuitively, this gives the typical form of the PF by plotting the lowest achievable loss among classifiers with fairness gaps or below the fairness gap budget given by the r-value.
We observe that increasing e shifts the PF upwards while also increasing its curvature; changing d tilts the PF; and increasing c" moves the PF to the right.
J.2 Synthetic experiments
In this section, we provide additional details on the setup for the synthetic experiments in Figure 3 as well as additional results below.
J.3 Model Architecture and Training
We used Pytorch to train our models. To test the scaling law, we trained models under different
MLP configurations, each with two hidden layers and ReLU activations, with sigmoid output for binary classification:
[80, 80] hidden units (8080 total parameters)
[160, 160] hidden units (28960 total parameters)
[320, 320] hidden units (109120 total parameters)
[640, 640] hidden units (423040 total parameters)
For each architecture and À value, the data split into training (65%), validation (15%), and test (20%) sets. The models are trained for 30 epochs using the Adam optimizer with a learning rate of
36

---

C
2.5
2.5
2.0
2.0
1.5
0.6
1.5
C 0.7
BCE
0.7
1.0
0.8
1.0
0.8
0.9
0.9
0.5
0.5
Fairess Gap
Fairness Gap Budget
Figure 7: Simulations showing the shape of the closed-form expression for the Pareto frontier given in Theorem (4.2 for fixed values of c" 0.9 and c" 0.8 while varying c. The left plot shows precise closed-form, which is lowest achievable loss among classifiers have exactly the fairness gap value on x-axis. The right plot shows lowest achievable loss among classifiers that satisfy the faimeess gap budger on the x-axis.
0.30
0.30
0.2
C'2
BCE LOSs
0.3
BCE Loss
0.3
0.20
=
0.20
0.4
C 0.5
0.5
C 0.6
C 0.6
0.15
0.15
C 0.7
0.7
C 0.8
C' 0.8
0.10
0.9
0.10
0.9
0.1
Fairness
Fairness Budget
Figure 8: Simulations showing the shape of the closed-form expression for the Pareto frontier given in Theorem 4.2 for fixed values of 0.2 and 0.6 while varying d. The plot shows the precise closed-form, which is the lowest achievable loss among classifiers that have exactly the faimess gap value on the x-axis. The right plot shows lowest achievable loss among classifiers that satisfy the fairness gap budget on the x-axis.
0.001 and a batch size of 256, selecting the model with the lowest validation loss over the training epochs. We repeat each configuration over random seeds and all trials find the Pareto frontier, resulting in 300 models per model size and 1200 models total.
J.3.1 Additional Results
We test two combinations of and values.
show results below. Interestingly, we found that the typical scaling law N did not necessarily fit our results perfectly, we indicate the exponent used in each figure caption.
37

---

0.6
C 0.5
0.6
0.5
C 0.6
C
0.6
C" 0.7
0.7
0.5
C" 0.8
0.5
0.8
C
0.9
0.4
BCE
0.4
0.2
0.2
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.6
0.8
Fairness Gap
Fairness Gap Budget
Figure 9: Simulations showing the shape of the closed-form expression for the Pareto frontier given in Theorem 4.2 for fixed values of = 0.2 and c" Cr = 0.5 while varying c". The left plot shows the precise closed-fomm which is the lowest achievable loss among classifiers that have exactly the faimess gap value the x-axis. The right plot shows lowest achievable loss among classifiers that satisfy the faimess gap budger on x-axis.
0.80
0.60
423040
0.70
0.65
BCE Loss
0.50
0.55
0.50
0.40
0.40
Fairness Gap
Falmess Gap (Zoomed)
Figure 10: Parcto fronticr for different model sizes under (x 0.2) and bias strength Ç 0.5. Each point corresponds trained model with different fairness regularization weight The dashed lines show the empirical Pareto frontier, created by finding lower convex
solid lines show fitted curves to the points on the Pareto frontier using Theorem 4.2 with c = Cs 0.16, c' C. 0.11, d" = C, = 0.92, with bias C; = -0,285, C2 55, C2 = 0.7. and C4 = 0.5. The left panel shows the frontier across the range of A. while the right panel zooms in A [0, 0.3). The fitted curve mimics the empirical data well though imperfect. We found that there were many possible fits, depending on the precise choice. show another possible fit in Figure helow.
of the points.
38

---

0.80
5050
0.60
0.75
109120
422040
0.65
BCE Loss
0.50
0.55
0.50
0.40
0.40
Fairesss Gap
Fairness Gap (Zoomed)
Figure 11: Pareto frontier for different model sizes under (x 0.2) and bias strength Ç 0.5. Each point corresponds trained model with different fairness regularization weight The dashed lines show empirical Pareto frontier, created by finding the lower convex hull of the points. The solid lines show fitted curves to the points on the Pareto frontier using Theorem 4.2 with c = Cs = 0.12, c' C. 0.11, e" = C7 0.92, with bias C1 = 11.205, C2 150, C3 0.8, and C₃ 0.5. The left panel shows the the range of A, while the right panel zooms chosen lower bound the larger models. That is, it to the small model curve, the larger model curve; we do so to exhibit one possible way to fit the curves since our training procedure was not optimized for the larger models and, such, our empirical Pareto frontier is likely not optimal. We show another possible fit in Figure Beloow.......
frontier
A [0, 0.3). The fitted curve is intentionally
uses extrapolate
0.70
8080
28560
109329
-
423065
0.65
0.8
0.60
BCE Loss
0.7
Loss
0.55
0.4
0.5
0.30
Fairness Gap
Faimess Gap (Zoomed)
Pareto frontier for different model sizes under (T 0.4) and bias strength corresponds to trained model with a different fairness regularization weight The dashed lines show empirical Pareto frontier, created by finding the lower convex hull of the points. The solid lines show fitted curves to the points on the Pareto frontier using Theorem 4.2 with e = C. = 0.08, c' C. 0.43, Cs 0.5, and Ca 0.5. The left panel shows the frontier
Figure 12:
2. Each point
d" = C7 0.85, with bias Ci 0.195, C2 the range of A, while the right panel zooms found that there were many possible fits, depending on the precise choice. We show another possible Figure 13 helow.
A E [0, 0.3). The fitted curve mimics the empirical
data well though is imperfect.
39

---

0.70
N 8080
25050
-0- -233363
--00120
0.65
0.60
Loss
0.55
0.7
BCE
0.50
0.6
0.45
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.00
0.05
0.10
0.15
0.20
0.25
0.30
Fairness Gap
Faimess Gap (Zoomed)
Figure 13: Pareto frontier different model sizes under (or 0.4) and bias strength ( 2. Each point corresponds to a trained model with a different fairness regularization weight The dashed lines show empirical Pareto frontier, created by finding the lower convex hull of all the points. The solid lines show fitted curves to the points the Pareto frontier using Theorem 4.2 with
Cs 0.06, c' Ce Cr 0.5, e" Cr 0.82, with bias Ci 0.18, C2 11.25, Cs 0.8. and Ca 0.5. The left panel shows the frontier across range A, while right panel zooms on C [0. 0.3). The fitted curve is intentionally chosen to lower bound the larger models. That is, it fits to the small model curve, then uses it to extrapolate the larger model curve; we do so to exhibit one possible way to fit the curves since our training procedure was optimized for the larger models and, such, empirical Pareto frontier is likely optimal. We show another possible fit Figure 12
40


Reviews:
[{"review_id": "pgSE3sgWom", "reviewer": "Reviewer_9GNb", "summary": "The authors focus on Title VII of the US Civil Rights Act and discuss their work in the context of legislation that utilizes the \"less discriminatory alternatives\" (LDA) framework. Under this framework, an individual claiming discrimination must be able to demonstrate the existence of an LDA with comparable performance. The authors highlight that claimants often lack the expertise or resources to find an LDA, hindering the efficacy of the legislation in facilitating accountability. To address this issue, the authors frame the problem as showing that there exists a model closer to the Pareto frontier. To circumvent computing the precise Pareto frontier, the paper proposes a scaling law for loss-fairness Pareto frontiers (under mild assumptions).", "questions": "- Figure 1 might be more compelling if it were from real data?\n- What does it mean for a model class $\\mathcal{F}$ to be symmetric with respect to the DGP?\n- Can the authors provide an intuitive description/explanation on the quantities of “constants” in Section 4? i.e., C, C’, B(\\cdot)\n- Line 305\n> including that $N$ and $D$ only affect the PF additively\n\nCan the authors claim this when the experiment only varies $N$?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\nThe authors have framed the problem very well. The problem they aim to address is significant and seems to be up to date with the literature.\n\n## Weaknesses\n**Structure and Tone**  \nThe structure and tone of the work leave a lot to be desired for an academic paper. This is immediately apparent with Figure 1 (it should not be difficult to recreate this plot digitally) and the fact that related works are at the very end. Section 1 does not have any citations as well. The numbered points in the main contribution should be more concise. The tone of the paper is not consistently professional (i.e., line 127, line 260).\n\n**Clarity in Theoretical Results**  \nOverall, the theoretical results in Section 4 are hard to follow because many variables are not clearly defined (see questions for specific examples). There are a lot of variables and custom notation (which is fine) that are mentioned in passing without elaboration on what they mean. This is crucial considering the paper aims to provide a method for those who may not be well-versed in machine learning. I would imagine that they would not have the easiest time understanding how they should adjust parameters in the framework.\n\n**Leaving Empirical Validation for Future Work**  \nThis is the main weakness of this paper. Considering how the authors have positioned this paper in specific legislation, I expected empirical results (from non-synthetic datasets). Without empirical results, the authors have put themselves at a disadvantage: it is difficult to argue for the utility of the paper's contribution. The lack of clarity in theoretical results could have been resolved through a guided demonstration on how one might use the proposed PF construction.\n\nI suspect that this may be because the paper focuses on \"large models\" or \"universal approximators.\" But I want to ask why the authors have focused on large models. Are they widely used in areas where LDA-esque legislation is in effect?", "was_revised": true, "final_justification": "The authors were actively engaged throughout the rebuttal process and have addressed most of my concerns involving clarity in theoretical results and empirical demonstrations. I am in favor of accepting the paper, provided that the authors take the necessary steps to revise the paper for their camera-ready as promised. I have changed the score to a \"weak accept\". But I have lowered my confidence since\n\n1. I do not know how the authors will execute the revision; and\n2. Not sure if it was rushed, but the tone (language) and format of the original submission was sub-par. I am not 100% confident that the authors can address this (they have avoided answering this in their response apart from changing Figure 1).", "rebuttal": "Thank you for your thorough and constructive feedback. We appreciate the time you took to engage with our submission. Below we respond point‑by‑point and indicate the revisions we will make in the camera‑ready version should the paper be accepted.\n\n**Clarification on contributions.** Before we address your specific concerns, we noticed some themes in reviews, so we wanted to clarify our contribution as well as how it meaningfully adds to existing work.\n\n1. **Novel theoretical result that does not exist in extensive literature on Pareto frontiers**.  Despite the extensive interest on Pareto frontiers and recent work on performance-fairness Pareto frontiers [1-3, 11], no prior works have closed-form expressions for Pareto frontiers (in complex settings beyond, e.g., low-dimensional, binary features). Our work thus takes a step to fill this gap. To explain further, the existing literature on performance-fairness Pareto frontiers falls into two categories: (i) clever methods to find the frontier empirically via various multi-objective optimization techniques [4-9]; and (ii) analytical approaches in simple settings that pre-date large models [10-12], e.g., binary feature vectors of a fixed, low dimension. As we explained in our work, this (i) is not feasible in our setting, as it would still require that claimants are able to train models at the same scale as large companies and thus would place prohibitive costs on claimants with limited data and computational resources; and (ii) is also not applicable in our setting, as it cannot be applied to **large** models with flexible, high-dimensional inputs. Thus, even absent our setting/motivation (LDAs), our derivation of a closed-form tight upper bound is a novel result in the study of Pareto frontiers, multi-objective optimization, and fairness that we were able to provide by combining insights from information theory and results on implicit regularization via data augmentation/manipulation. \n2. **Addressing a persistent issue in AI accountability and audits that appears repeatedly**. The authors engage with and belong to both the ML and legal communities. The authors have also engaged with stakeholders who seek to audit and/or make legal claims about AI systems. Across these conversations, there is a persistent issue (as identified in our introduction) of an asymmetry between the resources, information, data, and access that claimants possess vs. those that defendants/auditees possess. This asymmetry is especially pronounced in disparate impact procedures; namely, step 3 involving LDAs. At the moment, no method exists that is able to address this issue at scale (for **large** models). So this setting is a strong, motivating case study and we provide the only known framework that addresses the above asymmetry. \n3. **Future work.** We note that while our main result on a closed-form scaling law holds for our stated assumptions and fairness as demographic parity, it is an important first step given the state of current work, as described above. We therefore hope our work provides a roadmap for extensions and hope to extend these results to other notions of fairness and performance. As our main contributions are our proposed reframing of LDAs for large models and the novel theoretical result, we leave extensive experiments to future work. \n\nWe hope that these points help to clarify our contributions, and we will do our best to make these contributions clear/better contextual our contributions in a revision if given the opportunity. \n\nNext, we highlight and respond to specific concerns that you raised:\n\n- **Re: Figure 1****,** we thank the reviewer for pointing this out and will replace it with a more professionally rendered schematic. Regarding the suggestion to use empirical data, our objective with Figure 1 is to provide a schematic illustrating *why the legal problem finding LDAs can be cast/formalized in terms of Pareto frontiers* and *the intuition behind scaling laws for Pareto frontiers.* This aims to provide the reader with a mental picture of what the paper proposes, instead of a real-life application..\n- **Re: related works.** We initially placed the Background and Related Work section after the introduction, but moved it to the end of the work, as has become common in ML works. As the reviewer’s concern indicates, this change would have warranted adding more **citations to the introduction**, and we will do so (and move Section 6 forward) in a revision. Irrespective of the placement, we want to assure the reviewer that our work engages deeply with the literature. We closely surveyed several related areas, including algorithmic fairness, anti-discrimination law, multi-objective optimization, and machine learning. The gap we address results from this survey. We also do our best to highlight the most closely related work on LDAs and hope that our discussion of them in Sections 2 and 6 contextualize our contributions relative to them.\n- **Leaving Empirical Validation for Future Work.** This is a valuable question. We hope that the points at the top of this rebuttal address this in part. To add to it, we make the following clarifications. (1) Our main contribution is the reframing of the LDA problem in low-resource/information settings and ensuing theoretical scaling law. We hope that the reviewer recognizes this as an important contribution, as there previous works *entirely on the empirics* of scaling laws and *entirely on the theory* of scaling laws that precede ours [13-16]. (2) We agree with the reviewer that an extensive real-world study is important to viability, and we are already taking steps to engage with employment agencies to apply this framework to a real dataset. We believe this warrants a standalone follow-up work. (3) We want to note that, even so, we believe our synthetic experiments are important in that the main “gap” in our theoretical result is whether the assumptions hold. So we stress-test the assumptions in Section 5 via the synthetic experiments that test whether the theoretical result holds under a different data generating process than assumed, whether implicit regularization using training data manipulation is a good approximation of actual training, and if Assumption 4.2 holds in practice. Although we discuss this in the Appendix (E.2), we understand this should be clearer and will update Section 5 to reflect this.\n- **Model class being symmetric w.r.t. DGP.** It means that the model class $\\mathcal{F}$ is not biased/favorable towards any particular distribution. Although this assumption may not hold exactly in practice, it is reasonable for large deep learning models, because they are meant to be universal function approximators. That is, as a model class, they are designed to be relatively setting agnostic and over-parameterized such that they could be symmetric wrt the DGP.\n- **Description of constants.** Thank you for this. To potentially overexplain, constants (that may depend on complicated quantities like $p$) are a standard tool used across, e.g., statistical learning theory (see, e.g., Prop 2.5 or Thm 2.6 of [17]). There are two main reasons they come in handy. First, the exact value of the constant is context-specific! Providing a specific value would not be meaningful. Instead, saying that the some variable Y (in our case, loss) depends on an independent variable X (in our case, fairness gap) according to our closed-form equation, where there are constants that need to be **fit** based on data is a traditional approach. Second, one could potentially provide a specific form for each constant, but that would require significant assumptions on the specific context. With respect to the scaling law literature, constants appear naturally to show that the scaling law takes a particular form, where certain constants must be “fit” based on data (e.g., see Equation 4.1 of [14]). Lastly, we note that one can trace the derivation of our constants in the proof on page 28 of the supplementary material.\n- **Line 305 varies with N.** Yes, the figure shown above Line 305 varies only N while keeping D constant.\n\n[1] Bertsimas et al. (2011). The price of fairness. Oper. Res.\n\n[2] Menon & Williamson (2018). The cost of fairness in binary classification. FAccT.\n\n[3] Kim et al. (2020). FACT: A diagnostic for group fairness trade-offs. ICML.\n\n[4] Navon et al. (2020). Learning the Pareto front with hypernetworks. arXiv.\n\n[5] Ruchte & Grabocka (2021). Scalable Pareto front approximation for deep multi-objective learning. ICDM.\n\n[6] Singh et al. (2021). A hybrid 2-stage neural optimization for Pareto front extraction. arXiv.\n\n[7] Rothblum & Yona (2021). Consider the alternatives: Navigating fairness-accuracy tradeoffs via disqualification. arXiv.\n\n[8] Kamani et al. (2021). Pareto efficient fairness in supervised learning: From extraction to tracing. arXiv.\n\n[9] Liu & Vicente (2022). Accuracy and fairness trade-offs in machine learning: A stochastic multi-objective approach. CMS.\n\n[10] Xu & Strohmer (2023). Fair Data Representation for Machine Learning at the Pareto Frontier. JMLR.\n\n[11] Liang et al. (2021). Algorithm design: A fairness-accuracy frontier. arXiv.\n\n[12] Gillis et al. (2024). Operationalizing the search for less discriminatory alternatives in fair lending. FAccT.\n\n[13] Hestness et al. (2017). Deep learning scaling is predictable, empirically. arXiv.\n\n[14] Kaplan et al. (2020). Scaling laws for neural language models. arXiv.\n\n[15] Hoffmann et al. (2022). Training compute-optimal large language models. arXiv.\n\n[16] Bahri et al. (2024). Explaining neural scaling laws. PNAS.\n\n[17] Wainwright MJ (2019). Basic tail and concentration bounds. In *High-Dimensional Statistics: A Non-Asymptotic Viewpoint*, pp. 21–57. Cambridge Univ. Press."}, {"review_id": "My4JmYFBtF", "reviewer": "Reviewer_BDah", "summary": "This paper presents a novel approach towards legal cases of algorithmic discrimination, notably, cases where there is a need to demonstrate a less discriminatory alternative, and where the burden of proof falls on an entity with limited resources. The paper does an excellent job of motivating the approach and placing it in a concrete legal-operational context. The approach itself is solid and well-reasoned. However, the theoretical results themselves lack much-needed grounding and the simulations provided little added value due to their synthetic nature. There is also a lack of engagement with real use cases and known mechanisms of bias, which leads to a very big gap: it is very hard to estimate in which cases this approach will be operational. I felt that due to this, the paper misses the mark where it could have provided tangible, real-world value. I therefore suggest the authors to ground their work better prior to publishing, to achieve maximal impact of their result.", "questions": "- Can you find a few (or at least one) use cases that you can demonstrate your approach is superior to other approaches for this task?", "limitations": "While the limitations the authors describe are correct, I think the discussion of their implications should be expanded (even in an appendix, if you feel like there is not enough space in the main body of the paper).", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n\n- The premise of the paper is very important and urgently needed.\n- The clear connection to an existing legal framework is appropriate and well done\n- The paper is well written\n- The idea is (to my knowledge) novel, interesting and well reasoned. \n\nWeaknesses: \n- The theoretical results are not grounded in are real use cases. The requirements and limitations are put in general terms that require the reader to do much of their own work to try and find a single use case that this will work for. As a minimum, the authors need to demonstrate a class of use cases that would clearly benifit and ground their requirements and limitations concretely. \n\n- The choice of algorithmic parity is not explained and is an odd choice for this settings. I am aware this could be swapped, but it is a measure that will be inappropriate to use in most use cases. It can also give the appearance of improving fairness while making outcomes worse for the marginalised group. \nFor example, let's say we have a University admissions algorithm that is trained on past admissions decisions, and has very limited past acceptances from schools in group A. We rebalance the data so we get more school A acceptances, which maintains accuracy (with respect to past decisions), and as such, we have made improvements based on your method. However, our algorithm is bad at detecting students from group A who are likely to succeed, so we are accepting more of those students, but setting them up to fail. \n\n- Many of the limitations/complications related to the approach are not discussed. For example, what is the bias that comes from using a measure that is not well calibrated as ground truth? (e.g., Zilka et al. @ FAccT23'). Or, what if there is a better model, but it relies on different input data that is easily collected?  \n\n- The simulations would be much more valuable if they used real or even semi-real data, which seems very feasible to me.", "was_revised": true, "final_justification": "Following the extensive discussion below, I am changing from 3 to 4, as I believe most of my concerns are due to a presentation issue rather than core issues. I am hesitant to fully recommend the paper without seeing the revised version, so I lowered my confidence from 4 to 3.", "rebuttal": "We sincerely appreciate your careful reading and constructive feedback. Below we address each concern and outline the concrete revisions we will make if the paper is accepted.\n\n**Clarification on contributions.** Before we address your specific concerns, we noticed some themes in reviews, so we wanted to clarify our contribution as well as how it meaningfully adds to existing work.\n\n1. **Novel theoretical result that does not exist in extensive literature on Pareto frontiers**.  Despite the extensive interest on Pareto frontiers and recent work on performance-fairness Pareto frontiers [1-3, 11], no prior works have closed-form expressions for Pareto frontiers (in complex settings beyond, e.g., low-dimensional, binary features). Our work thus takes a step to fill this gap. To explain further, the existing literature on performance-fairness Pareto frontiers falls into two categories: (i) clever methods to find the frontier empirically via various multi-objective optimization techniques [4-9]; and (ii) analytical approaches in simple settings that pre-date large models [10-12], e.g., binary feature vectors of a fixed, low dimension. As we explained in our work, this (i) is not feasible in our setting, as it would still require that claimants are able to train models at the same scale as large companies and thus would place prohibitive costs on claimants with limited data and computational resources; and (ii) is also not applicable in our setting, as it cannot be applied to **large** models with flexible, high-dimensional inputs. Thus, even absent our setting/motivation (LDAs), our derivation of a closed-form tight upper bound is a novel result in the study of Pareto frontiers, multi-objective optimization, and fairness that we were able to provide by combining insights from information theory and results on implicit regularization via data augmentation/manipulation. \n2. **Addressing a persistent issue in AI accountability and audits that appears repeatedly**. The authors engage with and belong to both the ML and legal communities. The authors have also engaged with stakeholders who seek to audit and/or make legal claims about AI systems. Across these conversations, there is a persistent issue (as identified in our introduction) of an asymmetry between the resources, information, data, and access that claimants possess vs. those that defendants/auditees possess. This asymmetry is especially pronounced in disparate impact procedures; namely, step 3 involving LDAs. At the moment, no method exists that is able to address this issue at scale (for **large** models). So this setting is a strong, motivating case study and we provide the only known framework that addresses the above asymmetry. \n3. **Future work.** We note that while our main result on a closed-form scaling law holds for our stated assumptions and fairness as demographic parity, it is an important first step given the state of current work, as described above. We therefore hope our work provides a roadmap for extensions and hope to extend these results to other notions of fairness and performance. As our main contributions are our proposed reframing of LDAs for large models and the novel theoretical result, we leave extensive experiments to future work. \n\nWe hope that these points help to clarify our contributions, and we will do our best to make these contributions clear/better contextual our contributions in a revision if given the opportunity. \n\nWe now respond to specific concerns that you raised:\n\n- **Real application for theoretical results.** The setting of this paper is grounded in the specific Title VII procedure that arises in disparate impact doctrine (lines 104-112) and thus that procedure is a self-evident example.\n- **Experiments using real data.** Thank you for raising this. We hope that the points at the top of this rebuttal address this in part. To add to it, we make the following clarifications. (1) Our main contribution is the reframing of the LDA problem in low-resource/information settings and ensuing theoretical scaling law. We hope that the reviewer recognizes this as an important contribution, as there previous works *entirely on the empirics* of scaling laws and *entirely on the theory* of scaling laws that precede ours [13-16]. (2) We agree with the reviewer that an extensive real-world study is important to viability, and we are already taking steps to engage with employment agencies to apply this framework to a real dataset. We believe this warrants a standalone follow-up work. (3) We want to note that, even so, we believe our synthetic experiments are important as the main “gap” in our theoretical result is whether the assumptions hold. So the synthetic experiments test the assumptions in Section 5 to see whether the theoretical result holds under a different data generating process than assumed, whether implicit regularization using training data manipulation is a good approximation of actual training, and if Assumption 4.2 holds in practice. Although we discuss this in the Appendix (E.2), we understand this should be clearer and will update Section 5 to reflect this.\n- **Choice of algorithmic parity.** We agree with the reviewer that there is no universally “right” fairness definition. We want to assure the reviewer that the authors have engaged with the fairness community and with stakeholders on how the law, courts, and other policymakers have interpreted/applied fairness definitions in practice. Given this, we offer two points. (1) In practice, simple definitions like demographic parity and equalized odds are often more accepted by courts than sophisticated ones. (2) As discussed above, our work provides the first closed-form expression characterizing performance-fairness Pareto frontiers despite a long history of related work—we believe this is a significant first step that provides a roadmap for future work. However, we do acknowledge that our result is for a specific setting (choice of fairness metric, assumptions, model class) and we hope that it will be generalized in future work. We understand your example and will suggest that practitioners make sure the bias metric is appropriate for their use case.\n- **Bias from using a measure not as well calibrated as ground truth.** This is indeed a persistent issue that spans many fields. We appreciate the pointer and will add it to a limitations section. However, we do not believe that this issue precludes our framework from being applied. The concern the reviewer raises is, in fact, a more fundamental issue that *arises anytime an outcome-based fairness definition is used and thus is not an issue specific to our work,* though we fully agree that it is an important issue and would be a compelling extension.\n- **Better model that relies on easily collected but different input data.** This is certainly a possibility, but our motivating scenario is a company using a proprietary large model (so the plaintiff does not have access to any training material), and the task of training a competing large model is infeasible for the plaintiff given their limited resources and common appeals to trade secrecy used by companies. *This is the motivation of our work, which we describe in depth in Sections 1, 2, and 6.*\n- **Use cases in which our approach is superior to other approaches to this task.** We point the reviewer to the discussion at the top of this rebuttal as well as to our discussion of related work in Sections 6 and 2. Mainly, all other approaches characterize Pareto frontiers empirically (not feasible for low-resourced plaintiffs) or in settings with simple input spaces (not applicable to the increasingly large modern models that are the target of our work).\n- **Limitations.** We appreciate this feedback and are happy to discuss our limitations in depth in a revision by specifically addressing that (i) our method works conditional on the validity of the performance metric (e.g., demographic parity) supplied by the claimant; (ii) it also assumes that the claimant has at an ability to train small models (like an MLP) on small datasets; and (iii) our specific theoretical result contains several assumptions that should be further explained. We want to note that we strive in the existing manuscript to state all assumptions, definitions, and score clearly, as we agree that hiding these can only hurt practitioners (which is against the spirit of this work: to provide claimants with a useful framework).\n\n[1] Bertsimas et al. (2011). The price of fairness. Oper. Res.\n\n[2] Menon & Williamson (2018). The cost of fairness in binary classification. FAccT.\n\n[3] Kim et al. (2020). FACT: A diagnostic for group fairness trade-offs. ICML.\n\n[4] Navon et al. (2020). Learning the Pareto front with hypernetworks. arXiv.\n\n[5] Ruchte & Grabocka (2021). Scalable Pareto front approximation for deep multi-objective learning. ICDM.\n\n[6] Singh et al. (2021). A hybrid 2-stage neural optimization for Pareto front extraction. arXiv.\n\n[7] Rothblum & Yona (2021). Consider the alternatives: Navigating fairness-accuracy tradeoffs via disqualification. arXiv.\n\n[8] Kamani et al. (2021). Pareto efficient fairness in supervised learning: From extraction to tracing. arXiv.\n\n[9] Liu & Vicente (2022). Accuracy and fairness trade-offs in machine learning: A stochastic multi-objective approach. CMS.\n\n[10] Xu & Strohmer (2023). Fair Data Representation for Machine Learning at the Pareto Frontier. JMLR.\n\n[11] Liang et al. (2021). Algorithm design: A fairness-accuracy frontier. arXiv.\n\n[12] Gillis et al. (2024). Operationalizing the search for less discriminatory alternatives in fair lending. FAccT.\n\n[13] Hestness et al. (2017). Deep learning scaling is predictable, empirically. arXiv.\n\n[14] Kaplan et al. (2020). Scaling laws for neural language models. arXiv.\n\n[15] Hoffmann et al. (2022). Training compute-optimal large language models. arXiv.\n\n[16] Bahri et al. (2024). Explaining neural scaling laws. PNAS."}, {"review_id": "Zx33ZZRoXT", "reviewer": "Reviewer_ZUjW", "summary": "This work formulates an analytical solution to finding less discriminatory alternative models under some assumptions. The authors introduce the problem setting of LDAs and some legal challenges in discovering them, specifically in asymmetries of data or model information. The authors provide some basic simulation results.", "questions": "Could you please motivate the terms in Thm 4.2 and give further definitions to what they represent?", "limitations": "The authors have a good discussion on their model limitations, and specifically the scope of their work r.e. an initial fairness definition. Other analyses would have differing fairness implications which are outside of the scope of this work (and are OK).", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. The authors give good legal and ethical motivations for their work.\n\n2. The presentation of the work is overall quite good and easy to follow. The methods are straightforward and the problem is scoped to appropriate fairness measures. \n \n\nWeaknesses\n\n1. Overall, the authors do not motivate the hardness of their work, computationally. The authors do demonstrate practical limitations in LDA model discovery, but why is the problem challenging, if for example, we can make a few model assumptions and obtain Thm 4.2? Is Assumption 4.1 and 4.2 reasonable to make? Does 4.1 hold outside of Bayes optimal classifiers? \n\n2. The authors miss important details of the primary Thm 4.2. Where is the intuition and justification for the constant terms? These are varied in Figure 2 and there's no intuition what varying C' ought to represent (let alone, C, C''). \n\n3. Similarly, I don't understand the primary take-aways from  Fig 3. The authors describe model size 'N.' In number of nodes? They seemingly don't specify. But furthermore, does varying N solve 'limited resources' (D is fixed) or limited information? (again D is fixed). \n\nTherefore, the authors don't directly demonstrate that they mitigate the use cases in their motivation. \n\n4. I'm not convinced that the authors formulation is entirely correct. Specifically, in which applications is the LDA a responsibility of the plaintiff? And, what applications will there be *any* information on the vendor's model or data in a reduced capacity?\n\nMore likely is that a regulator or court requests a due-diligence report from the vendor. In applications such as healthcare or finance, regulators can demand alternative model search and require reporting from the vendor. In this case, the authors problem disappears with a different human solution.\n\nMinor: The authors main claims (L69) could be edited to more succinctly convey the novelty.", "was_revised": true, "final_justification": "Please see comment. \n\nI am happy to recommend this at a weak accept, at a lower confidence of 3. Conceptually I'm happy with the work, but the technical appendix are beyond me. \n\n*This review form does not seem to allow changing the reviewer confidence(?). This is very peculiar as we'd expect confidence to (hopefully) increase over the rebuttal period.", "rebuttal": "We appreciate your critique of both our theoretical and empirical work and the time you took with our submission. Below we respond to all of your points and note any revisions we will make shall the paper be accepted.\n\n**Clarification on contributions.** Before we address your specific concerns, we noticed some themes in reviews, so we wanted to clarify our contribution as well as how it meaningfully adds to existing work.\n\n1. **Novel theoretical result that does not exist in extensive literature on Pareto frontiers**.  Despite the extensive interest on Pareto frontiers and recent work on performance-fairness Pareto frontiers [1-3, 11], no prior works have closed-form expressions for Pareto frontiers (in complex settings beyond, e.g., low-dimensional, binary features). The existing literature on performance-fairness Pareto frontiers falls into two categories: (i) clever methods to find the frontier empirically via various multi-objective optimization techniques [4-9]; and (ii) analytical approaches in simple settings that pre-date large models [10-12]. This is (i) not feasible in our setting, as it would still require that claimants are able to train models at the same scale as large companies and thus would place prohibitive costs on claimants with limited data and computational resources; and (ii) also not applicable in our setting, as it cannot be applied to **large** models with flexible, high-dimensional inputs. Thus, even absent our setting (LDAs), our derivation of a closed-form tight bound is a novel result in the study of Pareto frontiers, multi-objective optimization, and fairness that we provided by combining insights from information theory and results on implicit regularization via data augmentation/manipulation. \n2. **Addressing a persistent issue in AI accountability and audits that appears repeatedly**. The authors engage with and belong to both the ML and legal communities, and have engaged with stakeholders who seek to audit and/or make legal claims about AI systems. Across these, there is a persistent issue (as in our introduction) of an asymmetry between the resources, information, data, and access that claimants possess vs. those that defendants possess. This asymmetry is especially pronounced in disparate impact procedures; namely, step 3 involving LDAs. At the moment, no method exists that is able to address this issue at scale (for **large** models). So this setting is a strong, motivating case study and we provide the only known framework that addresses the above asymmetry. \n3. **Future work.** We note that while our main result on a closed-form scaling law holds for our stated assumptions and fairness as demographic parity, it is an important first step given the state of current work, as described above. We therefore hope our work provides a roadmap for extensions and hope to extend these results to other notions of fairness and performance. As our main contributions are our proposed reframing of LDAs for large models and the novel theoretical result, we leave extensive experiments to future work. \n\nWe hope that these points help to clarify our contributions, and we will do our best to make these contributions clear/better contextual our contributions in a revision if given the opportunity. \n\nNext, we highlight and respond to specific concerns that you raised:\n\n- **Motivating computational hardness of work.** *Theorem 4.2 is the main result of the paper.* There is no easy way to obtain the scaling law, and this is precisely our contribution. To contextualize this contribution, there have been foundational papers that focus entirely on empirical scaling laws or entirely on the theory of scaling laws, as we discuss in Section 6. With our method, we show that one can obtain the scaling law specified in Theorem 4.2 and hence have an easier solution to the problem of finding an LDA. The proof of Theorem 4.2 was quite involved and, to the best of our knowledge, there exists no other closed-form characterizing the performance-loss Pareto frontier, and the framework of establishing LDAs under low resources and information using scalings is entirely new.\n- **Reasonability of Assumptions 4.1 and 4.2.** Assumption 4.1 is reasonable when considering very large models. It means that the model class $\\mathcal{F}$ is not biased/favorable towards any particular distribution. Although this assumption may not hold *exactly* in practice (as most assumptions do not), it is a reasonable condition for deep learning models, especially large ones, because (large) deep learning models are meant to be universal function approximators. That is, as a model class, they are designed to be relatively setting agnostic and over-parameterized such that they could be symmetric wrt the DGP. A similar thought process holds for Assumption 4.2.\n- **Assumption 4.1 holding outside of Bayes optimal classifiers.** Assumption 4.1 uses \\hat{f} to denote *any* classifier, not just a Bayes optimal classifier. Bayes optimality is only used as a proof technique to trace the Pareto frontier (it is not an assumption).\n- **Details of Thm 4.2, intuition and justification for constant terms.** The setup for Theorem 4.2 is provided between Sections 3.1 and 4.1. Constants (that may depend on complicated quantities like $p$) are a standard tool used in, e.g., statistical learning theory (see, e.g., Prop 2.5 or Thm 2.6 of [17]). There are two main reasons for this. (1) the exact value of the constant is context-specific! Providing a specific value would not be meaningful. (2) One could potentially provide a specific form for each constant, but that would require significant assumptions on the specific context. With respect to the scaling law literature, constants appear naturally to show that the scaling law takes a particular form, where certain constants must be “fit” based on data (e.g., see Equation 4.1 of [14]). Lastly, we note that one can trace the derivation of our constants in the proof on page 28 of the supplementary material.\n- **Take-aways from Fig 3, specify N, what does varying N solve.** N is the number of parameters of the model. We defined N at the start of the section on line 262 but will define it again near Figure 3. The magnitude of N relates to the computational difficulty of training such a model, so smaller N corresponds to limited computational resources. This general approach in finding a form of the scaling law as a function of N is common in the scaling law literature (e.g., Kaplan et al. 2020, Sharma and Kaplan 2022, or Clark et al. 2022).\n- **Correctness of formulation, responsibility for LDA.** Establishing an LDA **is the responsibility of the plaintiff in all disparate impact claims** under Title VII of the Civil Rights Act (see Lines 49-50). We would like to emphasize that the authors have significant engagement with the the legal community, and failing to ground our work in real stakeholder issues would be antithetical to our goals. This work was produced by first identifying a concern that is repeatedly raised, then seeking to provide a framework that can genuinely help plaintiffs and other claimants. We further point the reviewer to Sections 1, 2, and 6 (in particular, the “three steps of disparate impact cases” from lines 104-112). **Section 6 identifies several related works that write about the fact that the burden of establishing an LDA falls on plaintiffs.**\n- **Reduced information on vendor’s model.** To contextualize the situation, the current debate on burden of proof issues for claimants is whether or not vendors should release their *entire trained models* and *training data* and whether, in the absence of this, plaintiffs have any mechanisms for relief. Thus, asking vendors to release the approximate N and D is a much lower ask that we expect companies to welcome.\n- **Regulator or court requesting report from vendor.** While this may be true in some cases, in court cases involving disparate impact claims under Title VII of the Civil Rights Act, the burden of LDA proof *falls squarely on the claimant.* This is explicitly detailed in lines 110-112 and is precisely what we address. There is some discussion about whether this burden of search for an LDA should be shifted onto model developers (see lines 348-353), but for now the burden is entirely on the claimant.\n\n[1] Bertsimas et al. (2011). The price of fairness. Oper. Res.\n\n[2] Menon & Williamson (2018). The cost of fairness in binary classification. FAccT.\n\n[3] Kim et al. (2020). FACT: A diagnostic for group fairness trade-offs. ICML.\n\n[4] Navon et al. (2020). Learning the Pareto front with hypernetworks. arXiv.\n\n[5] Ruchte & Grabocka (2021). Scalable Pareto front approximation for deep multi-objective learning. ICDM.\n\n[6] Singh et al. (2021). A hybrid 2-stage neural optimization for Pareto front extraction. arXiv.\n\n[7] Rothblum & Yona (2021). Consider the alternatives: Navigating fairness-accuracy tradeoffs via disqualification. arXiv.\n\n[8] Kamani et al. (2021). Pareto efficient fairness in supervised learning: From extraction to tracing. arXiv.\n\n[9] Liu & Vicente (2022). Accuracy and fairness trade-offs in machine learning: A stochastic multi-objective approach. CMS.\n\n[10] Xu & Strohmer (2023). Fair Data Representation for Machine Learning at the Pareto Frontier. JMLR.\n\n[11] Liang et al. (2021). Algorithm design: A fairness-accuracy frontier. arXiv.\n\n[12] Gillis et al. (2024). Operationalizing the search for less discriminatory alternatives in fair lending. FAccT.\n\n[13] Hestness et al. (2017). Deep learning scaling is predictable, empirically. arXiv.\n\n[14] Kaplan et al. (2020). Scaling laws for neural language models. arXiv.\n\n[15] Hoffmann et al. (2022). Training compute-optimal large language models. arXiv.\n\n[16] Bahri et al. (2024). Explaining neural scaling laws. PNAS.\n\n[17] Wainwright MJ (2019). Basic tail and concentration bounds. In *High-Dimensional Statistics: A Non-Asymptotic Viewpoint*, pp. 21–57. Cambridge Univ. Press."}, {"review_id": "4fSP1NrBrL", "reviewer": "Reviewer_4wHh", "summary": "The authors propose a method for meeting the burden of evidence in algorithmic discrimination claims through proving the existence of “less discriminatory alternatives” (LDA). Specifically, AI models can be costly to produce in both time and resources, so the authors propose a method for estimating the achievable loss and fairness of large models. They do so by deriving an upper bound for the loss of a model depending on its achieved fairness score and the dataset and model size combined with known loss scaling laws for neural networks. Their theoretical results hold under somewhat strong assumptions and only one loss / fairness metric setting to serve as a proof of concept for this framework. The authors additionally provide numerical simulations to illustrate the intuition of their main theorem as well as validate their assumptions on the constants in their bound.", "questions": "- Is it non-trivial to bound constant $B(p,\\mathcal{F},\\mathcal{D})$ in Theorem 4.2 to explicate how $c_1(\\mathcal{F},\\mathcal{D})$ depends on $|\\mathcal{F}|$ and $|\\mathcal{D}|$? \n- Under what loss functions and hypothesis classes are the scaling laws used in Section 5 proven to hold? \n- Are the assumptions on the symmetry of the data generating process reasonable given that defendants have an incentive to release portions of their dataset that would in fact skew learning outcomes to show low loss is only achievable with high fairness gaps?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "$\\textit{Strengths}$: The context of Title VII provides strong motivation for their problem set up. The authors uniquely address resource asymmetry concerns between plaintiffs and defendants, and this approach appears to be novel given the authors covered the relevant related works / concepts I could think of (Rashomon sets and trade secrecy concerns). The authors state their assumptions clearly and offer intuition on the technical assumptions as well as practical areas where the results would reasonably hold (e.g., when defendants are using neural networks). Additionally, their simulations provide initial evidence that it is reasonable to estimate Pareto frontiers using their bound by estimating constants with only a few model samples as opposed to traditional empirical PF tracing with many model samples. \n\n$\\textit{Weaknesses}$: One weakness in this paper is the lack of specificity on the conditions (e.g., loss function and hypothesis class and how it changes from scaling) under which the scaling laws for the constant $B(p,\\mathcal{F},\\mathcal{D})$ hold since those scaling laws drive the tractability of estimating the Pareto frontier from a few samples. Additional simulated experiments under a range of architectures and dataset distributions would be useful to further support this claim.  Another weakness is that training a small neural network can still be non-trivial, so this framework still requires plaintiffs to be able to produce properly trained (but small) neural networks. \n\n$\\textit{Minor formatting concerns}$: Use of $\\mathcal{H}$ for loss instead of $\\mathcal{L}$ in the appendix was a bit confusing when tracking where assumption 4.2 was used in the proof.", "was_revised": true, "final_justification": "I have increased my score for this paper as a result of the thorough and engaging discussion the authors had with all of the reviewers. It is clear to me that this paper (with the planned clarity updates) will be useful for both a technical and legal audience and could inspire future work in an important area. My confidence remains the same because I am less familiar with how planned changes should weigh in the acceptance decision, so I will leave this up to the AC, though I will note that I am satisfied with the level of detail the authors have provided for their planned changes.", "rebuttal": "Thank you for your very constructive feedback. We appreciate the time you took to provide interesting questions. Below we respond point‑by‑point and indicate the revisions we will make should the paper be accepted.\n\n**Clarification on contributions.** Before we address your specific concerns, we noticed some themes in reviews, so we wanted to clarify our contribution as well as how it meaningfully adds to existing work.\n\n1. **Novel theoretical result that does not exist in extensive literature on Pareto frontiers**.  Despite the extensive interest on Pareto frontiers and recent work on performance-fairness Pareto frontiers [1-3, 11], no prior works have closed-form expressions for Pareto frontiers (in complex settings beyond, e.g., low-dimensional, binary features). The existing literature on performance-fairness Pareto frontiers falls into two categories: (i) clever methods to find the frontier empirically via various multi-objective optimization techniques [4-9]; and (ii) analytical approaches in simple settings that pre-date large models [10-12]. This is (i) not feasible in our setting, as it would still require that claimants are able to train models at the same scale as large companies and thus would place prohibitive costs on claimants with limited data and computational resources; and (ii) also not applicable in our setting, as it cannot be applied to **large** models with flexible, high-dimensional inputs. Thus, even absent our setting (LDAs), our derivation of a closed-form tight bound is a novel result in the study of Pareto frontiers, multi-objective optimization, and fairness that we provided by combining insights from information theory and results on implicit regularization via data augmentation/manipulation. \n2. **Addressing a persistent issue in AI accountability and audits that appears repeatedly**. The authors engage with and belong to both the ML and legal communities, and have engaged with stakeholders who seek to audit and/or make legal claims about AI systems. Across these, there is a persistent issue (as in our introduction) of an asymmetry between the resources, information, data, and access that claimants possess vs. those that defendants possess. This asymmetry is especially pronounced in disparate impact procedures; namely, step 3 involving LDAs. At the moment, no method exists that is able to address this issue at scale (for **large** models). So this setting is a strong, motivating case study and we provide the only known framework that addresses the above asymmetry. \n3. **Future work.** We note that while our main result on a closed-form scaling law holds for our stated assumptions and fairness as demographic parity, it is an important first step given the state of current work, as described above. We therefore hope our work provides a roadmap for extensions and hope to extend these results to other notions of fairness and performance. As our main contributions are our proposed reframing of LDAs for large models and the novel theoretical result, we leave extensive experiments to future work. \n\nWe hope that these points help to clarify our contributions, and we will do our best to make these contributions clear/better contextual our contributions in a revision if given the opportunity. \n\nNext, we highlight and respond to specific concerns that you raised:\n\n- **Lack of specificity on the conditions under which the scaling laws hold.** Thank you for this point. We agree that our results, as presented, *apply only for our stated loss (BCE) and fairness definition (demographic parity).* As for the hypothesis class, the only assumption we place on it are the symmetry assumptions stated in our work (for an explanation of this assumption, see our last bullet below). Although our contribution in this work does not expand to other losses/fairness definitions, we believe it is an important first step and we seek to be upfront with our setup (i.e., that our results do not extend beyond it for now, except for what we show in the simulations, where we stress test the assumptions). Even so, we agree with the reviewer that the fact that our result lacks full generality is a limitation (though *we do not believe that all losses and fairness definitions will result the same closed-form,* so one would need to derive independent results for each setting). We will make this limitation even clearer in a revision, as we plan to include an explicit discussion and limitations section.\n- **More extensive experiments.** We agree with the reviewer that our experiments are limited. We hope that the points at the top of this rebuttal address this in part. To add to it, we make the following clarifications. (1) Our main contribution is the reframing of the LDA problem in low-resource/information settings and ensuing theoretical scaling law. We hope that the reviewer recognizes this as an important contribution, as there previous works *entirely on the empirics* of scaling laws and *entirely on the theory* of scaling laws that precede ours [13-16]. (2) We are already taking steps to engage with employment agencies to apply this framework to a real dataset. We believe this warrants a standalone follow-up work. (3) We want to note that, even so, we believe our synthetic experiments are important in that the main “gap” in our theoretical result is whether the assumptions hold. So we stress-test the assumptions in Section 5 via the synthetic experiments that test whether the theoretical result holds under a different data generating process than assumed, whether implicit regularization using training data manipulation is a good approximation of actual training, and if Assumption 4.2 holds in practice. Although we discuss this in the Appendix (E.2), we understand this should be clearer and will update Section 5 to reflect this.\n- **Training small neural nets is non-trivial.** We agree that training even small neural nets is non-trivial, but we want to emphasize our contribution compared to the status quo. At the moment, we are in a more dire situation in which a plaintiff must provide enough evidence that an LDA exists but often the resources/data involved to train one are impossible for them to obtain. They must produce some results that are convincing enough (if it’s too hand-wavy, it’s often not accepted), and thus it is impossible to avoid placing any burden on them.\n- **Formatting concerns.** We used H for the loss in the appendix proof but L in the Theorem 4.2 statement. Thank you very much for pointing this out—we will fix it in the revision.\n- **Non-trivial to bound constant B in Theorem 4.2 to explicate how $c_1(\\mathcal{F}, \\mathcal{D})$ depends on $ | \\mathcal{F}|$ and $| \\mathcal{D}|$.** We are not sure we fully understood the reviewer’s question, but under existing scaling laws (that only discuss loss), this term often follows the form $1/N^\\alpha + 1/D^\\alpha$, where $N = | \\mathcal{F}|$ and $D = | \\mathcal{D}|$.\n- **Reasonability of symmetry assumptions given incentive of defendant to only release skewed portions of their training data.** This is an interesting point. We believe that this assumption is fairly mild as it implies that the model class $\\mathcal{F}$ is not biased/favorable towards any particular distribution. Although this assumption may not hold exactly in practice, *it is reasonable for large deep learning models, because they are intended to be universal function approximators.* That is, as a model class, they are designed to be relatively setting agnostic and over-parameterized such that they could be symmetric wrt the DGP. As for defendants being incentivized to release skewed portions of their training data, this type of dishonest behavior is impossible to prevent but *typically countered by the fact that failing to follow the court’s orders would be flagrantly breaking the law and thus we generally presume that the defendant will not do this or otherwise be severely penalized.* Again, preventing dishonesty is impossible in practice, but we typically use a “stick” to disincentivize it (e.g., penalties for perjury).\n\n[1] Bertsimas et al. (2011). The price of fairness. Oper. Res.\n\n[2] Menon & Williamson (2018). The cost of fairness in binary classification. FAccT.\n\n[3] Kim et al. (2020). FACT: A diagnostic for group fairness trade-offs. ICML.\n\n[4] Navon et al. (2020). Learning the Pareto front with hypernetworks. arXiv.\n\n[5] Ruchte & Grabocka (2021). Scalable Pareto front approximation for deep multi-objective learning. ICDM.\n\n[6] Singh et al. (2021). A hybrid 2-stage neural optimization for Pareto front extraction. arXiv.\n\n[7] Rothblum & Yona (2021). Consider the alternatives: Navigating fairness-accuracy tradeoffs via disqualification. arXiv.\n\n[8] Kamani et al. (2021). Pareto efficient fairness in supervised learning: From extraction to tracing. arXiv.\n\n[9] Liu & Vicente (2022). Accuracy and fairness trade-offs in machine learning: A stochastic multi-objective approach. CMS.\n\n[10] Xu & Strohmer (2023). Fair Data Representation for Machine Learning at the Pareto Frontier. JMLR.\n\n[11] Liang et al. (2021). Algorithm design: A fairness-accuracy frontier. arXiv.\n\n[12] Gillis et al. (2024). Operationalizing the search for less discriminatory alternatives in fair lending. FAccT.\n\n[13] Hestness et al. (2017). Deep learning scaling is predictable, empirically. arXiv.\n\n[14] Kaplan et al. (2020). Scaling laws for neural language models. arXiv.\n\n[15] Hoffmann et al. (2022). Training compute-optimal large language models. arXiv.\n\n[16] Bahri et al. (2024). Explaining neural scaling laws. PNAS."}]

Author rebuttal:

Meta-review: This paper addresses the fact that while, in practice, individuals claiming discrimination could do so by demonstrating the existence of a "less discriminatory alternative (LDA)", this might not be feasible for regular people to do in practice. The paper then derives scaling laws for Fairness Pareto frontiers as a theoretical framework for solving the problem of discovering such LDAs.

Strengths: 
- A compelling motivation and new, interesting problem -- this is why I have nominated the paper for a spotlight
- A nice mathematical formulation of the problem

Weaknesses:
- Lack of empirical validation on real-world examples. There is a lot of discussion back and forth about this between the authors and reviewers, and to be honest, while the reviewers were happy with the explanations, there is no way this can all fit into the paper. Thus, we must assume that the concern remains.

Recommendation:
I am recommending acceptance but the lack of real-world empirical validation is a major concern. If the paper is, indeed, accepted, the authors should make a major effort to include the most important parts of their discussions into the paper.
Decision: Accept (poster)