theoremTheorem lemmaLemma corollaryCorollary

# Under manipulations, are some AI models
harder to audit?

Augustin Godinot  Univ Rennes, Inria, CNRS, IRISA, PEReN
Rennes, France
<EMAIL_ADDRESS>Erwan Le Merrer  Univ Rennes, Inria, CNRS, IRISA
Rennes, France  Gilles Trédan  LAAS/CNRS
Toulouse, France  Camilla Penzo  PEReN
Paris, France  François Taïani  Univ Rennes, Inria, CNRS, IRISA
Rennes, France

###### Abstract

Auditors need robust methods to assess the compliance of web platforms with
the law. However, since they hardly ever have access to the algorithm,
implementation, or training data used by a platform, the problem is harder
than a simple metric estimation. Within the recent framework of _manipulation-
proof_ auditing, we study in this paper the feasibility of robust audits in
realistic settings, in which models exhibit large capacities.

We first prove a constraining result: if a web platform uses models that may
fit any data, no audit strategy—whether active or not—can outperform random
sampling when estimating properties such as demographic parity. To better
understand the conditions under which state-of-the-art auditing techniques may
remain competitive, we then relate the manipulability of audits to the
capacity of the targeted models, using the Rademacher complexity. We
empirically validate these results on popular models of increasing capacities,
thus confirming experimentally that large-capacity models, which are commonly
used in practice, are particularly hard to audit robustly. These results
refine the limits of the auditing problem, and open up enticing questions on
the connection between model capacity and the ability of platforms to
manipulate audit attempts.

###### Index Terms:

Audit, black-box interaction, Rademacher complexity, model capacity.

##  I Introduction

The pervasive deployment of user-facing automated decision systems raises
concerns over their impact on society. The growing number of online platforms
and their increasing complexity highlights the need for automated and robust
audits to assess their impact on users. The advent of highly publicized
audits—such as ProPublica’s story on COMPAS [larsonHowWeAnalyzed2016] or
Reuters’ study on Amazon’s recruiting tool [dastinAmazonScrapsSecret2018]—has
brought considerable traction to the AI audit field. For the public to trust
Artificial Intelligence (AI) systems, and more broadly algorithmic decision
systems, we need methods to explain the decisions of such systems
[ribeiroWhyShouldTrust2016, lundbergUnifiedApproachInterpreting2017], certify
their implementation [yanActiveFairnessAuditing2022,
shamsabadiConfidentialPROFITTConfidentialPROof2023] and automatically and
robustly detect misconduct [matiasSoftwareSupportedAuditsDecisionMaking2022,
rastegarpanahAuditingBlackBoxPrediction2021].

As it is common in the literature (e.g. see [yanActiveFairnessAuditing2022]),
we assume that the system is composed of a _trained machine learning (ML)
model_ $h$ that the auditor can interact with via a web interface or an
Application Programming Interface (API). Similarly to the _honest-but-curious
(HBC)_ threat model [goldreichFoundationsCryptographyVolume2009], the outputs
returned by the API are the actual output of $h$. However, while the platform
cannot arbitrarily directly modify the output of $h$, it can use the
interactions performed by the auditor during the audit process to acquire as
much information as possible and modify the model in its favor. In this work,
we focus on _external certification audits_. In this type of audit, an
external auditor (e.g. a regulator or an auditing company) needs to verify a
given property $\mu$ (e.g. the absence of bias) of the API provided by the
platform. We will refer to this setting as the _remote black-box auditing_
problem.

Figure 1:  Security game of the manipulation-proof auditing framework. Before
the audit, the platform declares the hypothesis space $\mathcal{H}$ to the
auditor. During the audit, the platform serves the model $h\in\mathcal{H}$ and
the auditor queries $h$ on $S$. After the audit, the platform can change its
model to $h^{\prime}$ with the constraint that $\forall x\in
S,h^{\prime}(x)=h(x)$ or equivalently, $h^{\prime}\in\mathcal{H}(h,S)$.

Most of the current audit methods [metaxaAuditingAlgorithmsUnderstanding2021,
sandvigAuditingAlgorithmsResearch2014] could be referred to as “detection”
audits. This is because they seek to detect whether some rule is being
violated either to improve the platform itself or to take legal action. A
typical methodology of “detection” audits consists in randomly sampling the
input space, computing the measure(s) of interest and declaring the audit
failed if the measures cross a given threshold. In this case, to prove the
platform’s misconduct, one must witness it during the audit. As a result,
proving the absence of misconduct would require probing the entire input space
of the model $h$. Since the auditor cannot query the model on its entire input
space $\mathcal{X}$, they must choose a subset $S\subseteq\mathcal{X}$, and
they must have the guarantee that the estimation on the subset $S$ is not “too
far” from the value they would find if they could sample the whole input
space.

#### Threat model

We describe the interaction between the auditor and the platform in the threat
model diagram Figure 1. Before the audit, the platform discloses the
hypothesis space $\mathcal{H}$ they use (decision trees for example) to the
auditor. Then, during the auditing phase, the auditor interacts with the
(unknown) model $h\in\mathcal{H}$ exposed by the platform to iteratively build
an audit set $S\subset\mathcal{X}$. The manipulation-proof framework
acknowledges the possibility for a platform to try to _evade_ the audit by
showing a fair model $h$ to the auditor, then switching to a more accurate but
potentially unfair model $h^{\prime}$. The only assumption on how the platform
may choose the new model $h^{\prime}$ is that it should be _consistent_ with
$h$. The consistency constraint requires $h^{\prime}$ to have the same outputs
as $h$ on the audit set $S$, otherwise the auditor could easily check that the
platform changed its model after the audit by re-querying it on $S$. We now
formalize the capabilities and knowledge of the platform and the auditor in
the manipulation proof framework.

  * •

_Auditor capabilities_ : The auditor can send adaptive queries to the platform
to build an audit set $S\subset\mathcal{X}$.

  * •

_Auditor knowledge_ : The auditor knows the hypothesis class $\mathcal{H}$
implemented by the platform and the value of the sensitive attribute $x_{A}$
of all the points in the input space $\mathcal{X}$. However, the auditor does
not know the specific hypothesis $h\in\mathcal{H}$ implemented by the
platform.

  * •

_Platform capabilities_ : The platform can change its model from
$h\in\mathcal{H}$ to $h^{\prime}\in\mathcal{H}$ after the audit as long as
$h^{\prime}$ respects the consistency constraint $\forall x\in
S,h(x)=h^{\prime}(x)$.

  * •

_Platform knowledge_ : The platform knows the property $\mu$ (e.g. Demographic
Parity) being measured by the auditor. As the auditor, it knows the value of
the sensitive attribute $x_{A}$ of all the points in the input space
$\mathcal{X}$.

#### Problem

Among the attempts at formalizing robust auditing
[yanActiveFairnessAuditing2022, yadavXAuditTheoreticalLook2023,
chuggAuditingFairnessBetting2023a], [yanActiveFairnessAuditing2022]
[yanActiveFairnessAuditing2022] have shown that the knowledge of the
hypothesis class used by the platform can _potentially_ reduce the required
number of audit queries to reach a given robustness level. Their method is
based on disagreement-based active learning
[hannekeTheoryDisagreementBasedActive2014] which requires training surrogates
of the platform’s model. However, they only demonstrated their proposed audit
algorithm with linear models on small datasets (StudentPerf
[cortezUsingDataMining2008] and COMPAS [larsonHowWeAnalyzed2016]).
Furthermore, they prove that quantifying the potential improvement (in terms
of query complexity) of their algorithm over a simple random baseline is
computationally intractable. Thus, whether it is possible or not to devise
practical robust auditing methods still remains an open question.

Our exploration of robust audits for practical models is focused on binary
classifiers and binary sensitive attributes. While this calls for future work
on other tasks and modalities, this first exploration covers a large class of
decision systems based on ML algorithms
[richardsonDefiningDemystifyingAutomated2021]. Our hope is to demonstrate that
regulators should be given more than black-box access to AI models as part of
the audit procedure.

#### Contributions

In this work, we investigate whether the platform can engineer models that
simultaneously achieve a high utility and evade the audit. To that end, we
compare the manipulation-proofness (MP) guarantees of a simple uniform random
audit algorithm (Algorithm 1) against the best guarantees a regulator could
hope for. Our contributions are three-fold.

  1. 1.

We first consider those hypothesis classes that can perfectly reproduce any
labeling of the dataset. This covers two practical cases: either the platform
has a model with a very high capacity, or the auditor’s prior on the
platform’s model is uninformative. We prove in subsection III-A (Subsection
III-A) that no audit method—whether active or passive—can deliver a better
performance than random sampling. We also prove in Definition 2 that this
impossibility holds even if the hypothesis class can only imperfectly
reproduce any labeling of the dataset with a bounded error rate.

  2. 2.

To uncover what properties of the hypothesis class influence its auditability,
in Subsection III-B we analyze the simple class of dictionary models, whose
manipulation guarantees can be analytically derived. We identify regimes in
which the hypothesis class cannot be audited more efficiently than by random
sampling.

  3. 3.

To build a practical understanding of our theoretical results, we formally
define the notion of _manipulability under random audits_ and _capacity_ in
subsection IV-A. We then evaluate the manipulability under random audits of
classical ML models for tabular data. We empirically confirm the strong
connection between the classical _Rademacher complexity_ and the
manipulability of manipulation-proof auditing. Since modern ML hypothesis
classes tend to exhibit larger and larger capacities, we argue that our work
brings up the limits of the current formulation of manipulation-proof
auditing.

##  II Auditing and manipulation-proof estimation

During a typical audit, the auditor defines a measure of interest $\mu$ with
an associated threshold $\tau_{\mu}$. Classical measures used by auditors are
statistical parity indicators [barocasFairnessMachineLearning2023] focusing on
independence (e.g. demographic parity, group fairness), separation (e.g.
balance for positive/negative class, equalized odds) and sufficiency (e.g.
calibration, predictive parity). Given that demographic parity does not
require any ground truth labels and since it is often used as the archetypal
example in the literature, we use it as the measure $\mu$ throughout this
paper. While the results we present refer specifically to demographic parity,
it is straightforward to extend them to any parity measure of the form

$\displaystyle\mu(h,S)=$
$\displaystyle\operatorname{\mathbb{P}}\left(h(X)=1\middle|X\in S,E\right)$
(1) $\displaystyle-\operatorname{\mathbb{P}}\left(h(X)=1\middle|X\in
S,\overline{E}\right)$

with $E$ an event defined with respect to the random variables $X,X_{A}$ and
$Y$, where $X$ represents the input, $Y$ the ground truth label, and
$X_{A}\in\\{0,1\\}$ is the sensitive attribute of interest for the auditor.
For example, for demographic parity, $E=(X_{A}=1)$. We would like to stress
that for other less common measures that can nonetheless present an interest
for auditors (e.g. level of privacy [luGeneralFrameworkAuditing2022] or the
degree of compliance with data minimization
[rastegarpanahAuditingBlackBoxPrediction2021]), manipulation proof auditing
remains an open problem.

###  II-A Machine Learning notations

Except when noted, we will consider a binary classification task as in
[dasguptaTeachingBlackboxLearner2019], with finite _input space_ $\mathcal{X}$
and output space $\mathcal{Y}=\left\\{0,1\right\\}$.111Should $\mathcal{X}$ be
infinite, [dasguptaTeachingBlackboxLearner2019]
[dasguptaTeachingBlackboxLearner2019] note that it suffices to sample a finite
i.i.d. subset $\widetilde{\mathcal{X}}$ and extend all the following bounds by
classical generalization bounds. $\mathcal{Y}^{\mathcal{X}}$ denotes the space
of functions $\mathcal{X}\to\mathcal{Y}$. For any sample $x\in\mathcal{X}$, we
refer to its sensitive attribute (e.g., gender, ethnicity, religion) as
$x_{A}\in\left\\{0,1\right\\}$. The sensitive attribute of the points in
$\mathcal{X}$ induces a partition of the input space. We note
$\mathcal{X}_{A}=\left\\{x\in\mathcal{X}:x_{A}=1\right\\}$ and remark that
$\mathcal{X}_{\overline{A}}=\overline{\mathcal{X}_{A}}$. For any set $V$,
$\operatorname{\mathcal{P}}\left(V\right)$ denotes the set of all subsets of
$V$ and $\mathcal{U}(V)$ denotes the uniform distribution on $V$. By training
the classification model, the platform effectively chooses a model $h$ in some
hypothesis class $\mathcal{H}$. The auditor defines a measure
$\mu:\mathcal{H}\times\operatorname{\mathcal{P}}\left(\mathcal{X}\right)\to\mathbb{R}_{+}$,
which is known by the platform. For any subset $V\subseteq\mathcal{H}$ and
$S\subseteq\mathcal{X}$, we define _the diameter of $V$ with respect to the
measure $\mu$_ as

$\operatorname{diam}_{\mu(\cdot,S)}V=\max_{h,h^{\prime}\in
V}|\mu(h,S)-\mu(h^{\prime},S)|,$

when $S$ is the entire input space $\mathcal{X}$, we abuse the notation and
write
$\operatorname{diam}_{\mu(\cdot,\mathcal{X})}V=\operatorname{diam}_{\mu}V$.
Finally, define for any subset $V\subset\mathcal{H}$, sample $x\in\mathcal{X}$
and label $y\in\left\\{0,1\right\\}$ the set $V[x,y]=\left\\{h\in
V:h(x)=y\right\\}$. The cost $\text{Cost}(V)$ of a subset
$V\subset\mathcal{H}$ is defined in Equation 2. Note that when the context is
clear, we elide the $\epsilon$ for simplicity.

$\text{Cost}_{\epsilon}(V)=\begin{cases}0\text{ if
}\operatorname{diam}_{\mu}V<\epsilon\\\
1+\min\limits_{x\in\mathcal{X}}\max\limits_{y\in\left\\{0,1\right\\}}\;\text{Cost}_{\epsilon}(V[x,y])\text{
else}\end{cases}$ (2)

Before we formally define the _capacity_ of a hypothesis class in subsection
IV-B, we will use the term capacity loosely. Intuitively the capacity of a
hypothesis class $\mathcal{H}$ is related to the ability for any labeling of
the input space $\mathcal{X}$ to find a hypothesis $h\in\mathcal{H}$ that
realizes this labeling. More details on the notion of capacity can be found in
section VI.

###  II-B What is an active auditing algorithm?

An audit algorithm $\mathcal{A}$ with label budget $s$ is a sequence of
(possibly randomized) $s+1$ functions $(f_{0},\dots,f_{s})$. For each
iteration $i$, the function
$f_{i}:(\mathcal{X}\times\left\\{0,1\right\\})^{i+1}\to\mathcal{X}$ chooses
the next sample
$x_{i}=f_{i}\left(\left(x_{0},h(x_{0})\right),\dots,\left(x_{i-1},h(x_{i-1})\right)\right)$
to query and add to the audit set. After the query budget has been spent, the
end result of the algorithm is the audit set $S=\mathcal{A}(h)$. Note that
most published black-box audits of web platforms are not active
[bandyProblematicMachineBehavior2021]. In this case, an audit algorithm
reduces to a single (possibly randomized) function $f_{s}$ which does not
depend on the answers provided by the platform.

###  II-C The manipulation-proof auditing framework

Following the framework of [yanActiveFairnessAuditing2022]
[yanActiveFairnessAuditing2022], the platform is assumed to be _self-
consistent_ , i.e. when the platform returns a given output $y=h(x)$ to an
auditor’s query $x$, the platform commits to this value and cannot return a
different answer $y^{\prime}=h(x)$ if $x$ is queried again at a later moment
in time. Furthermore, as explained in the threat model Figure 1, it is assumed
that the auditor knows the _hypothesis class_
$\mathcal{H}\subseteq\left\\{0,1\right\\}^{\mathcal{X}}$ of the model
implemented by the platform. The self-consistency of the platform together
with the knowledge of the hypothesis class defines a subset of “plausible”
models in $\mathcal{H}$ that have the same answers as the platform on the
current audit set $S$. This subset is called the _version space of
$\mathcal{H}$ induced by $S$ and $h$_ [mitchellGeneralizationSearch1982,
hannekeTheoryDisagreementBasedActive2014], noted $\mathcal{H}(h,S)$.

$\mathcal{H}(h,S)=\left\\{h^{\prime}\in\mathcal{H}\;:\;\forall x\in
S,h^{\prime}(x)=h(x)\right\\}$ (3)

We assume that the platform seeks to maximize its profits, which is not
necessarily aligned with the property that the regulator seeks to enforce.
During the audit process, the auditor incrementally builds an audit set
$S\subseteq\mathcal{X}$ based on their previous queries and the answers of the
platform. The goal of the auditor is to produce an estimate $\widehat{\mu}$ as
close as possible to the real value while being robust to the potential
manipulations implemented by the platform. We now formulate the two
requirements of the _manipulation-proof_ auditing problem, as introduced in
[yanActiveFairnessAuditing2022].

$\displaystyle\text{Create an algorithm }\mathcal{A}\text{ with}$ smallest
budget s such that, (fidelity)
$\displaystyle|\mu(h,\mathcal{A}(h))-\mu(h,\mathcal{X})|<\epsilon$ (4)
(manipulation-proofness)
$\displaystyle\operatorname{diam}_{\mu}\mathcal{H}\left(h,\mathcal{A}(h)\right)<\epsilon$
(5)

_Fidelity_ is the classical estimation constraints. It requires the estimated
value $\widehat{\mu}=\mu(h^{*},S)$ to be close to the real value
$\mu(h,\mathcal{X})$. In addition, _manipulation-proofness_ requires that if
the platform changes its implemented instance from $h$ to $h^{\prime}$ while
respecting the self-consistency constraint
$h^{\prime}\in\mathcal{H}\left(h,S\right)$, the difference between the
previous $\mu(h,\mathcal{X})$ and new $\mu(h^{\prime},\mathcal{X})$ values of
$\mu$ must be bounded. Therefore, the $\mu$-diameter is the biggest change in
the value of $\mu$ the auditor would accept if the platform changed to another
(consistent) hypothesis.

###  II-D Comparing manipulation-proof auditing algorithms

Table I:  The query complexity of different auditing algorithms in the manipulation-proof framework, extracted from [yanActiveFairnessAuditing2022] [yanActiveFairnessAuditing2022] Algorithm |  Query complexity
---|---
Random sampling (Algorithm 1) |  $\operatorname{\mathcal{O}}\left(\frac{1}{\epsilon^{2}}\log\left|\mathcal{H}\right|\right)$
Optimal deterministic [yanActiveFairnessAuditing2022, Algorithm 1] |  $\text{Cost}_{\epsilon}(\mathcal{H})$
Oracle based approximation (AFA) [yanActiveFairnessAuditing2022, Algorithm 3] |  $\operatorname{\mathcal{O}}\left(\log\left|\mathcal{H}\right|\log\left|\mathcal{X}\right|\text{Cost}(\mathcal{H})\right)$

There are two ways to compare two audit algorithms $\mathcal{A}$ and
$\mathcal{A}^{\prime}$. Either fix a target manipulation-proofness guarantee
$\epsilon$ and evaluate the number of queries needed by $\mathcal{A}$ and
$\mathcal{A}^{\prime}$, or fix the audit budget $s$ and evaluate the
$\mu$-diameter of the audit sets built by $\mathcal{A}$ and
$\mathcal{A}^{\prime}$.

yanActiveFairnessAuditing2022 [yanActiveFairnessAuditing2022] focused on the
former: the study of the _query complexity_ of different audit algorithms. For
general hypothesis classes, they introduced three auditing algorithms. The
first one is the baseline random audit algorithm. This audit algorithm
consists in sampling among points with positive and negative sensitive
attributes, and computing the empirical frequencies of the events
$(h(X)=1|X_{A}=1)$ and $(h(X)=1|X_{A}=0)$ (see Algorithm 1). To capture the
minimal query complexity attainable by deterministic audit algorithms, they
introduced a second algorithm based on the recursive minimization of
$\text{Cost}(\mathcal{H})$. Finally, [yanActiveFairnessAuditing2022]
introduced a third, oracle-based, algorithm that we coin AFA. We summarize the
query complexities proved by [yanActiveFairnessAuditing2022] in Table I.

Motivated by the implementation of MP audit algorithms, we choose to focus on
the second comparison approach: fixing an audit budget and evaluating the
$\mu$-diameter. This approach is better suited to our situation since in
practice, auditors have a limited query budget that would be agreed upon with
the platform prior to the audit.

###  II-E The computational complexity of manipulation-proof auditing

As exposed in Table I, the best attainable query complexity, as well as the
query complexity of the more practical AFA algorithm depend on the value of
$\text{Cost}(\mathcal{H})$. In addition, the computational complexity of AFA
[yanActiveFairnessAuditing2022, Algorithm 1] is the time to train a model from
the hypothesis class $\mathcal{H}$ multiplied by the query complexity.
However, [yanActiveFairnessAuditing2022] prove that $\text{Cost}(\mathcal{H})$
is hard to compute, hard to approximate and hard to optimize
[yanActiveFairnessAuditing2022, Proposition 3.5]. Thus, not only it prevents
practical implementations of the optimal deterministic algorithm, it also
prevents practical analysis of the query complexity and computational
complexity of AFA for large models that are costly to train.

##  III The competitive effectiveness of random audits

Current state-of-the-art models for tabular data (see Figure 5) and image data
(see e.g. [zhangUnderstandingDeepLearning2021]) are able to fit very large
train sets with close to perfect accuracy while retaining good generalization
properties. In our setting this would mean that these models can represent any
binary classification function $f:\mathcal{X}\to\left\\{0,1\right\\}$ of the
input space. As we saw in subsection II-E, the only tractable algorithm (AFA
[yanActiveFairnessAuditing2022]) that was proposed to solve the manipulation-
proof auditing task (Equation 4 and 5) is still too computationally intense to
audit large models because it requires to be able to train a lot of copies
efficiently. Moreover, while [yanActiveFairnessAuditing2022] experimented on
small datasets with linear models, there exists no implementations or
practical experiments on larger models. Thus, the potential gains brought by
AFA are hard to predict. Yet, for AFA to be used in practice, it would be
necessary to balance the extra cost induced by auditing with AFA with the
added guarantees of AFA. Thus, a natural practical question arises. Is the
added manipulation-proofness guarantee worth paying the computational toll?

To answer this question, instead of analyzing $\text{Cost}(\mathcal{H})$
(which is hard to compute and derive) as [yanActiveFairnessAuditing2022], we
directly express the value of $\operatorname{diam}_{\mu}\mathcal{H}(h,S)$ for
specific hypothesis classes. Identifying hypothesis classes $\mathcal{H}$
wherein the value of $\operatorname{diam}_{\mu}(h,S)$ remains constant across
all audit sets $S$ allows us to find scenarios in which enhancing
manipulation-proofness guarantees beyond that of a random baseline is
impossible.

In this section, we consider three typical but insightful forms of hypothesis
space $\mathcal{H}$ to better understand this balance between computational
cost and added robustness. We prove in subsection III-A that for hypothesis
classes shattering the whole input space, all the audit algorithms have the
same performance as random sampling. Next, to understand what happens for
classes that are only able to fit a part of the dataset, we consider the
illustrative class $\mathcal{D}_{m}$ of dictionaries of size $m$. We derive
the exact value of their $\mu$-diameter in subsection III-B and show the link
between the memory as an intuitive notion of the capacity and the MP
guarantees obtainable when auditing dictionary models. Last but not least,
building on the results of subsection III-A and subsection III-B, we introduce
a formal notion of the capacity of a binary classification hypothesis class as
the maximum number of samples a platform can interpolate while still retaining
good generalization performance. Under this definition, we prove in subsection
III-C that large capacity models cannot be audited more efficiently than by
the random baseline.

1:Proportions $\beta_{1},\beta_{2}$, budget $s$

2:audit dataset $S$ with $\left|S\right|=s$

3:$s^{+}\leftarrow\left\lfloor\beta_{1}\left|\mathcal{X}_{A}\right|\right\rfloor$,
$s^{-}\leftarrow\left\lfloor\beta_{2}\left|\overline{\mathcal{X}_{A}}\right|\right\rfloor$

4:$S^{+}\leftarrow$ sample $s^{+}$ points in $\mathcal{X}_{A}$ without
replacement

5:$S^{-}\leftarrow$ sample $s^{-}$ points in $\overline{\mathcal{X}_{A}}$
without replacement

6:$S=S^{+}\sqcup S^{-}$

Algorithm 1 A random sampling audit strategy

###  III-A Hypothesis classes that can fit the dataset entirely

To build intuition on the following theorems, let us first consider classes
able to fit any distribution on $\mathcal{X}$. This corresponds to the case of
a platform with a very large, overparametrized hypothesis class $\mathcal{H}$
able to fit any labeling of the whole input space $\mathcal{X}$. 222 This does
not contradict the No Free Lunch theorem since here, the input space
$\mathcal{X}$ is finite. This assumption is equivalent to considering the
hypothesis class $\mathcal{H}=\left\\{0,1\right\\}^{\mathcal{X}}$. Because all
the functions from the input space to the output space are possible, the
answer of the platform on a query $x$ does not give any information on the
possible answers to the other queries in $\mathcal{X}$. It follows, that no
matter how the points are iteratively chosen, only the number of points (and
the value of their associated sensitive attribute) will matter in the
computation of the $\mu$-diameter. We now formalize this intuition.

[No need to aim] Let $\mathcal{H}=\left\\{0,1\right\\}^{\mathcal{X}}$. For any
audit set $S\subseteq\mathcal{X}$ and hypothesis $h\in\mathcal{H}$,

$\displaystyle\operatorname{diam}_{\mu}\mathcal{H}(h,S)=2-\big{(}$
$\displaystyle\operatorname{\mathbb{P}}\left(X\in S\middle|X_{A}=1\right)$
$\displaystyle+\operatorname{\mathbb{P}}\left(X\in
S\middle|X_{A}=0\right)\big{)}$

The first step in proving subsection III-A relies on the fact that all the
instances $h^{\prime}\in\mathcal{H}\left(h,S\right)$ have the same value of
$\mu(h^{\prime},S)$. After decomposing the $\mu$-diameter on $S$ and
$\overline{S}$, we use this fact to separate the $\mu$-diameter into the
difference between a maximization and a minimization problem. The optima of
these problems rely on the existence of hypotheses
$h^{\uparrow},h^{\downarrow}\in\mathcal{H}\left(h,S\right)$ that exactly fit
the sensitive attribute (resp. its negation) on $\overline{S}$. Since
$\mathcal{H}$ is the space of all functions, it is always possible to find
such $h^{\uparrow}$ and $h^{\downarrow}$. Finally, we find these optima and
simplify their expressions to reach that of subsection III-A. A complete proof
is provided in LABEL:thm:shattering_implies_point_equivalence-apx.

###### Proof.

The proof is executed in 4 steps: decomposition of the value of
$\mu(h,\mathcal{X})$ on $S$ and $\overline{S}$, decomposition of the
$\mu$-diameter on $S$ and $\overline{S}$, solving the optimization on the
decomposed problems and conclusion.

Step 1: Decompose $\mu$
For any $h\in\mathcal{H}$, $S\subseteq\mathcal{X}$

$\displaystyle\mu(h,\mathcal{X})=\;$
$\displaystyle\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=1\right)-\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=0\right)$
$\displaystyle=\;$
$\displaystyle\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=1,X\in
S\right)\underbrace{\operatorname{\mathbb{P}}\left(X\in
S\middle|X_{A}=1\right)}_{\alpha}$
$\displaystyle\quad+\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=1,X\in\overline{S}\right)\underbrace{\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=1\right)}_{1-\alpha}$
$\displaystyle\quad-\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=0,X\in
S\right)\underbrace{\operatorname{\mathbb{P}}\left(X\in
S\middle|X_{A}=0\right)}_{\alpha-\delta}$
$\displaystyle\quad-\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=0,X\in\overline{S}\right)\underbrace{\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=0\right)}_{1-\alpha+\delta}$
$\displaystyle=\;$
$\displaystyle\alpha\underbrace{\big{(}\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=1,X\in
S\right)-\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=0,X\in
S\right)\big{)}}_{\mu(h,S)}$
$\displaystyle\quad+(1-\alpha)\underbrace{\left(\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=1,X\in\overline{S}\right)-\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=0,X\in\overline{S}\right)\right)}_{\mu(h,S)}$
$\displaystyle\quad+\delta\left(\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=0,X\in
S\right)-\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=0,X\in\overline{S}\right)\right)$
$\displaystyle=\;$ $\displaystyle\alpha\mu(h,S)+(1-\alpha)\mu(h,\overline{S})$
$\displaystyle\quad+\delta\left(\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=0,X\in
S\right)-\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=0,X\in\overline{S}\right)\right)$
(6)

Step 2: Decompose the $\mu$-diameter
For any $h,h^{\prime}\in\mathcal{H}(h^{*},S)$,

$\displaystyle\mu(h,\mathcal{X})-\mu(h^{\prime},\mathcal{X})=\;$
$\displaystyle\alpha\underbrace{\big{(}\mu(h,S)-\mu(h^{\prime},S)\big{)}}_{=0\text{
since
}h(S)=h^{\prime}(S)=h^{*}(S)}+(1-\alpha)\left(\mu(h,\overline{S})-\mu(h^{\prime},\overline{S})\right)$
$\displaystyle\quad+\delta\underbrace{\big{(}\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=0,X\in
S\right)-\operatorname{\mathbb{P}}\left(h^{\prime}(X)=1\middle|X_{A}=0,X\in
S\right)\big{)}}_{=0\text{ since }h(S)=h^{\prime}(S)=h^{*}(S)}$
$\displaystyle\quad+\delta\left(\operatorname{\mathbb{P}}\left(h^{\prime}(X)=1\middle|X_{A}=0,X\in\overline{S}\right)-\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=0,X\in\overline{S}\right)\right)$

Using the definition and separability of the $\mu$-diameter, we have

$\operatorname{diam}_{\mu}\left(h^{*},S\right)=\max_{h\in\mathcal{H}(h^{*},S)}\mu(h,S)-\min_{h^{\prime}\in\mathcal{H}(h^{*},S)}\mu(h,S)$
(7)

Therefore, by grouping the terms that depend on $h$ and $h^{\prime}$ in the
previous development:

$\displaystyle\operatorname{diam}_{\mu}\left(h^{*},S\right)=\;$
$\max_{h\in\mathcal{H}(h^{*},S)}\Big{[}(1-\alpha)\mu(h,\overline{S})-\delta\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=0,X\in\overline{S}\right)\Big{]}$
$\displaystyle-\hbox{\pagecolor{blue!20!white}$\min_{h^{\prime}\in\mathcal{H}(h^{*},S)}\Big{[}(1-\alpha)\mu(h^{\prime},\overline{S})-\delta\operatorname{\mathbb{P}}\left(h^{\prime}(X)=1\middle|X_{A}=0,X\in\overline{S}\right)\Big{]}$}$
(8)

Step 3: Solve each optimization problem

To solve the two optimization problems, we come back to the definition of
$\mu$.

blind
$\displaystyle=\max_{h\in\mathcal{H}(h^{*},S)}\left\\{(1-\alpha)\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=1,X\in\overline{S}\right)-(1-\alpha+\delta)\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=0,X\in\overline{S}\right)\right\\}$
(9)
$\displaystyle=-(1-\alpha+\delta)+\max_{h\in\mathcal{H}(h^{*},S)}\left\\{(1-\alpha)\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=1,X\in\overline{S}\right)+(1-\alpha+\delta)\operatorname{\mathbb{P}}\left(h(X)=0\middle|X_{A}=0,X\in\overline{S}\right)\right\\}$
(10)

Similarly,

blind
$\displaystyle=\min_{h\in\mathcal{H}(h^{*},S)}\left\\{(1-\alpha)\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=1,X\in\overline{S}\right)-(1-\alpha+\delta)\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=0,X\in\overline{S}\right)\right\\}$
(11)
$\displaystyle=-(1-\alpha+\delta)+\min_{h\in\mathcal{H}(h^{*},S)}\left\\{(1-\alpha)\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=1,X\in\overline{S}\right)+(1-\alpha+\delta)\operatorname{\mathbb{P}}\left(h(X)=0\middle|X_{A}=0,X\in\overline{S}\right)\right\\}$
(12)

We write $h^{\uparrow}$ (resp. $h^{\downarrow}$) the minimizer of blind (resp.
blind).

$h^{\uparrow}(x)=\begin{cases}1\text{ if }x_{A}=1\text{ and
}x\in\overline{S}\\\ 0\text{ if }x_{A}=0\text{ and }x\in\overline{S}\\\
0\text{ else}\end{cases}$ (13)

$h^{\downarrow}(x)=\begin{cases}1\text{ if }x_{A}=0\text{ and
}x\in\overline{S}\\\ 0\text{ if }x_{A}=1\text{ and }x\in\overline{S}\\\
0\text{ else}\end{cases}$ (14)

The optimizers $h^{\uparrow}$ and $h^{\downarrow}$ yield the optima

blind
$\displaystyle=-(1-\alpha+\delta)+(1-\alpha)\underbrace{\operatorname{\mathbb{P}}\left(h^{\uparrow}(X)=1\middle|X_{A}=1,X\in\overline{S}\right)}_{=1}+(1-\alpha+\delta)\underbrace{\operatorname{\mathbb{P}}\left(h^{\uparrow}(X)=0\middle|X_{A}=0,X\in\overline{S}\right)}_{=1}$
(15) $\displaystyle=1-\alpha$ (16) blind
$\displaystyle=-(1-\alpha+\delta)+(1-\alpha)\underbrace{\operatorname{\mathbb{P}}\left(h^{\downarrow}(X)=1\middle|X_{A}=1,X\in\overline{S}\right)}_{=0}+(1-\alpha+\delta)\underbrace{\operatorname{\mathbb{P}}\left(h^{\downarrow}(X)=0\middle|X_{A}=0,X\in\overline{S}\right)}_{=0}$
(17) $\displaystyle=-(1-\alpha+\delta)$ (18)

Step 4: Conclusion

$\displaystyle\operatorname{diam}_{\mu}\mathcal{H}(h^{*},S)$
$\displaystyle=\hbox{\pagecolor{orange!20!white}\phantom{blind}}-\hbox{\pagecolor{blue!20!white}\phantom{blind}}$
(19) $\displaystyle=(1-\alpha)+(1-\alpha+\delta)$ (20)
$\displaystyle=2-\big{(}\operatorname{\mathbb{P}}\left(X\in
S\middle|X_{A}=1\right)+\operatorname{\mathbb{P}}\left(X\in
S\middle|X_{A}=0\right)\big{)}$ (21)

∎

The values $\operatorname{\mathbb{P}}\left(X\in S\middle|X_{A}=1\right)$ and
$\operatorname{\mathbb{P}}\left(X\in S\middle|X_{A}=0\right)$ are aggregated
quantities that depend only on the relative proportion of sensitive
($x_{A}=1$) and non-sensitive ($x_{A}=0$) samples in the audit set $S$.
Therefore, for any pair $(\operatorname{\mathbb{P}}\left(X\in
S\middle|X_{A}=1\right),\operatorname{\mathbb{P}}\left(X\in
S\middle|X_{A}=0\right))$, one can design a random sampling scheme that
achieves the desired relative proportions. We expose such algorithm in
Algorithm 1. Since the auditor by definition knows the sensitive attribute of
each sample, the idea is to sample points from $\mathcal{X}_{A}$ and
$\mathcal{X}_{\overline{A}}$ with the right proportions
$(\beta_{1},\beta_{2})$ in $S_{\text{random}}$. Setting
$(\beta_{1},\beta_{2})=(\operatorname{\mathbb{P}}\left(X\in
S\middle|X_{A}=1\right),\operatorname{\mathbb{P}}\left(X\in
S\middle|X_{A}=0\right))$ in Algorithm 1 yields
$(\operatorname{\mathbb{P}}\left(X\in
S_{\text{random}}\middle|X_{A}=1\right),\operatorname{\mathbb{P}}\left(X\in
S_{\text{random}}\middle|X_{A}=0\right))=(\operatorname{\mathbb{P}}\left(X\in
S\middle|X_{A}=1\right),\operatorname{\mathbb{P}}\left(X\in
S\middle|X_{A}=0\right))$. Following subsection III-A, any audit set $S$ with
the same relative proportions $(\operatorname{\mathbb{P}}\left(X\in
S\middle|X_{A}=1\right),\operatorname{\mathbb{P}}\left(X\in
S\middle|X_{A}=0\right))$ yields the same $\mu$-diameter. Since any couple
$(\operatorname{\mathbb{P}}\left(X\in
S\middle|X_{A}=1\right),\operatorname{\mathbb{P}}\left(X\in
S\middle|X_{A}=0\right))$ is also attainable by the random sampling algorithm
described in Algorithm 1, when the hypothesis class can perfectly fit any
arbitrary label distribution, all audit algorithms –active or not– have at
most the same manipulation-proofness guarantees as random sampling.

As a side note, removing the assumption that the auditor knows the hypothesis
class implemented by the platform is equivalent to assuming
$\mathcal{H}=\left\\{0,1\right\\}^{\mathcal{X}}$. In this sense, by proving
that random sampling is optimal when the hypothesis class is unknown,
subsection III-A demonstrates that knowing $\mathcal{H}$ is necessary (but not
sufficent) to design more efficient manipulation-proof auditing methods.

###  III-B An illustrative example with dictionaries

Figure 2: The diameter (vertical axis) resulting from the amount of memory
(horizontal axis) of the dictionary model studied in subsection III-B. The
various audit budgets are represented by different curve colors, while the
optimal audit set appears as dashed curves, and the random baseline audit sets
as plain lines.

It is unlikely in practice that any hypothesis class can fit the entire input
space $\mathcal{X}$. We now relax this assumption to pursue our analysis of
the achievable manipulation-proofness guarantees of models with a large
capacity. To that end, we introduce the class $\mathcal{D}_{m}$ of dictionary
models. A dictionary $d\in\mathcal{D}_{m}$ is built by choosing a set of
$m\in\left\llbracket n\right\rrbracket$ samples in $\mathcal{X}$ and storing
the corresponding labels. When the dictionary is asked to label a sample that
it did not store, it returns $0$ as a default value. Define, for any set of
vectors $V\subseteq\mathbb{R}^{d}$, $\operatorname{\mathfrak{S}}(V)$ the set
of vectors obtained from $V$ by including all permutations of the coefficients
of each $v\in V$. The hypothesis class of dictionaries of memory $m$ is
formally introduced in Definition 1.

######  Definition 1 (Dictionary hypothesis class).

Consider an input space $\mathcal{X}$, $n=\left|\mathcal{X}\right|$. The class
of dictionaries of memory $m\in\left\llbracket n\right\rrbracket$ is defined
as

$\mathcal{D}_{m}=\operatorname{\mathfrak{S}}\left(\left\\{0,1\right\\}^{m}\times\left\\{0_{\mathbb{R}^{n-m}}\right\\}\right)$

While such a hypothesis class is not likely to be used in a practical context
(as it will typically fail to generalize beyond the encountered examples,
exhibiting a blatant overfitting) it is simple enough to support an analysis
of the MP guarantees for both randomized and optimal approaches. Moreover, its
main parameter (the memory $m$) directly influences its capacity.

The exact value of the $\mu$-diameter of dictionary hypothesis classes is
exposed in Definition 1. The proof can be found in LABEL:thm:mudiam_dicts-apx.

[$\mu$-diameter of $\mathcal{D}_{m}$] Consider $S\subseteq\mathcal{X}$,
$d\in\mathcal{D}_{m}$. Note $m^{\prime}=m-\left|x\in S:d(x)=1\right|$. The
$\mu$-diameter of $\mathcal{D}_{m}(d,S)$ is given by

$\operatorname{diam}_{\mu}\mathcal{D}_{m}(d,S)=\frac{\min(\left|\mathcal{X}_{A}\cap\overline{S}\right|,m^{\prime})}{\left|\mathcal{X}_{A}\right|}+\frac{\min(\left|\overline{\mathcal{X}_{A}}\cap\overline{S}\right|,m^{\prime})}{\left|\overline{\mathcal{X}_{A}}\right|}$

The proof relies on the same development of the diameter as in the proof of
subsection III-A but instead of finding $h^{\uparrow}$ and $h^{\downarrow}$,
we are able to give the values of the optima thanks to the structure of
$\mathcal{D}_{m}$.

###### Proof.

In the proof of subsection III-A, we established the following identity (for
any hypothesis class thus for $\mathcal{D}_{m}$, and for any $S$ and $d^{*}$):

$\displaystyle\operatorname{diam}_{\mu}\mathcal{D}(d^{*},S)$ (22)
$\displaystyle=\hbox{\pagecolor{orange!20!white}$\max_{d\in\mathcal{D}(d^{*},S)}\left\\{\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=1\right)\operatorname{\mathbb{P}}\left(d(X)=1\middle|X_{A}=1,X\in\overline{S}\right)+\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=0\right)\operatorname{\mathbb{P}}\left(d(X)=0\middle|X_{A}=0,X\in\overline{S}\right)\right\\}$}$
$\displaystyle-\hbox{\pagecolor{blue!20!white}$\min_{d\in\mathcal{D}(d^{*},S)}\left\\{\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=1\right)\operatorname{\mathbb{P}}\left(d(X)=1\middle|X_{A}=1,X\in\overline{S}\right)+\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=0\right)\operatorname{\mathbb{P}}\left(d(X)=0\middle|X_{A}=0,X\in\overline{S}\right)\right\\}$}$
(23)

First, observe that in the two optimization problems, the value of the
objective function does not depend on the values of $d$ on $S$. Moreover, the
choices of the labels $d(x)$ for $x\in\overline{S}$ can be made freely as long
as $d$ does not have more than $m^{\prime}=m-\left|x\in S:d^{*}(x)=1\right|$
“$1$”s (because it has to use $\left|x\in S:d^{*}(x)=1\right|$ slots of memory
to store the answers of $d^{*}$ on $S$).

Therefore, the dictionary that optimizes blind is built by storing as many
“$1$”s in $d$ on the entries of $x\in\mathcal{X}_{A}\cap\overline{S}$ within
the limits of the $m^{\prime}$ slots left. This leads to

$\displaystyle\hbox{\pagecolor{orange!20!white}\phantom{blind}}=\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=1\right)\frac{\min(\left|\mathcal{X}_{A}\cap\overline{S}\right|,m^{\prime})}{\left|\mathcal{X}_{A}\cap\overline{S}\right|}+\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=0\right)*1$
(24)

Next, rewriting as a maximization problem, we get

$\displaystyle\hbox{\pagecolor{blue!20!white}\phantom{blind}}=\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=1\right)+\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=0\right)$
$\displaystyle-\min_{d\in\mathcal{D}(d^{*},S)}\left\\{\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=1\right)\operatorname{\mathbb{P}}\left(d(X)=0\middle|X_{A}=1,X\in\overline{S}\right)+\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=0\right)\operatorname{\mathbb{P}}\left(d(X)=1\middle|X_{A}=0,X\in\overline{S}\right)\right\\}$
(25)

Similar to the case of blind, the dictionary that optimizes blind is built by
storing as many “$1$”s in $d$ on the entries of
$x\in\overline{\mathcal{X}_{A}}\cap\overline{S}$ withing the limits of the
$m^{\prime}$ slots left. This leads to

blind
$\displaystyle=\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=1\right)+\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=0\right)$
(26)
$\displaystyle\qquad-\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=1\right)*1-\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=0\right)\frac{\min(\left|\overline{\mathcal{X}_{A}}\cap\overline{S}\right|,m^{\prime})}{\left|\overline{\mathcal{X}_{A}}\cap\overline{S}\right|}$
(27)

Composing the expressions of blind and blind, we get

$\operatorname{diam}_{\mu}\mathcal{D}(d^{*},S)=\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=1\right)\frac{\min(\left|\mathcal{X}_{A}\cap\overline{S}\right|,m^{\prime})}{\left|\mathcal{X}_{A}\cap\overline{S}\right|}+\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=0\right)\frac{\min(\left|\overline{\mathcal{X}_{A}}\cap\overline{S}\right|,m^{\prime})}{\left|\overline{\mathcal{X}_{A}}\cap\overline{S}\right|}$
(28)

Here, it is important to understand that in the notations
$\operatorname{\mathbb{P}}\left(X\in S\right)$ or
$\operatorname{\mathbb{P}}\left(d(X)=1\right)$, $X$ is a random variable
taking values in $\mathcal{X}$ with a uniform probability. Therefore,
$\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=1\right)=\frac{\left|\mathcal{X}_{A}\cap\overline{S}\right|}{\left|\mathcal{X}_{A}\right|}$
and
$\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=0\right)=\frac{\left|\overline{\mathcal{X}_{A}}\cap\overline{S}\right|}{\left|\overline{\mathcal{X}_{A}}\right|}$,
which simplifies the previous equation

$\operatorname{diam}_{\mu}\mathcal{D}(d^{*},S)=\frac{\min(\left|\mathcal{X}_{A}\cap\overline{S}\right|,m^{\prime})}{\left|\mathcal{X}_{A}\right|}+\frac{\min(\left|\overline{\mathcal{X}_{A}}\cap\overline{S}\right|,m^{\prime})}{\left|\overline{\mathcal{X}_{A}}\right|}$
(29)

∎

We are interested in the high memory $m$, low audit budget $\left|S\right|$
regime. In this situation, there exist couples $(S,m)$ such that
$\left|\mathcal{X}_{A}\cap\overline{S}\right|\leq m^{\prime}$ and
$\left|\overline{\mathcal{X}_{A}}\cap\overline{S}\right|\leq m^{\prime}$.
Thus, in this regime, the $\mu$-diameter does not depend on the labels of the
particular dictionary $d$ chosen by the platform. Therefore, as for the case
$\mathcal{H}=\left\\{0,1\right\\}^{\mathcal{X}}$, in the high memory, low
audit budget regime, all audit algorithms – active or not – have at most the
same manipulation-proofness guarantees as random sampling.

#### Simulation of the impact of memory over diameter

The expression of the $\mu$-diameter exposed in Definition 1 is piecewise
linear in the memory $m$. To gain intuition, we plot the value of
$\operatorname{diam}_{\mu}\mathcal{D}_{m}(d,S)$ in Figure 2 for a setting
where $|\mathcal{X}|=1000$,
$\operatorname{\mathbb{P}}\left(X_{A}=1\right)=0.3$ and the $\mu$-diameter of
the random strategy is averaged over $100$ realisations of $S$. We first
observe the drastic impact of dictionary memory on an audit of a fixed budget:
for instance, with an audit budget of 300 (representing nearly one-third of
the whole input space) an optimal audit set barely achieves a $\mu$-diameter
of 1 when auditing dictionaries with memory $m=500$. Furthermore, given a
fixed audit budget, the gap between randomized and optimal audit sets shrinks
as the memory grows. This is especially striking in low audit budget regimes,
that correspond to a typical audit situation. Moreover, for an audit budget of
$100$ and memory values larger than $70\%$ the random and optimal audit
strategies have the same $\mu$-diameter. This observation hints that
subsection III-A’s conclusions should hold for a broader set of hypothesis
classes.

###  III-C Tying it all together: large capacity and auditability

We derived in subsection III-B the exact expression of the $\mu$-diameter for
toy models able to memorize part of the input space. Motivated by the _benign
overfitting_ phenomenon [zhangUnderstandingDeepLearning2021,
belkinReconcilingModernMachinelearning2019,
arnouldInterpolationBenignRandom2023, buschjagerThereNoDoubleDescent2021], we
now consider the case of a hypothesis class that is able to perfectly fit any
subset $S\subseteq\mathcal{X}$ of reasonable size, but require in addition
that the resulting hypothesis $h^{*}$ maintains good accuracy on the rest of
the dataset.

It has been observed that contrary to common knowledge on the bias-variance
tradeoff, large ML models can exhibit good generalization properties while
perfectly fitting the train data. This benign overfitting phenomenon (also
related to _double descent_), is observed in models that are largely
overparametrized compared to the training data available at hand.
Nevertheless, we show in Figure 3 that trees and GBDTs can reach the maximum
capacity, indicating that they also can interpolate the training data. Drawing
intuition from the empirical characterization of benign overfitting in
[zhangUnderstandingDeepLearning2021,
belkinReconcilingModernMachinelearning2019,
arnouldInterpolationBenignRandom2023, buschjagerThereNoDoubleDescent2021], we
derive the formal definition of a large capacity hypothesis class in
Definition 2.

######  Definition 2 (Benign Overfitting Hypothesis class).

Consider an input space $\mathcal{X}$, a hypothesis class
$\mathcal{H}\subset\left\\{0,1\right\\}^{\mathcal{X}}$ and a labeling
$c\in\left\\{0,1\right\\}^{\mathcal{X}}$. $\mathcal{H}$ is said to exhibit
benign overfitting with respect to labeling $c$ if there exists
$d_{0}\in\mathbb{N}_{*}$ and $\epsilon\in[0,1)$ such that

$\displaystyle\forall d\leq
d_{0},S\subseteq\mathcal{X},\sigma\in\left\\{0,1\right\\}^{d},\exists
h\in\mathcal{H},$ $\displaystyle\begin{cases}\forall x_{i}\in
S,h(x_{i})=\sigma_{i}&{\color[rgb]{0.6,0.6,0.6}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0.6,0.6}\pgfsys@color@gray@stroke{0.6}\pgfsys@color@gray@fill{0.6}\text{(fit
any train set)}}\\\
\operatorname{\mathbb{P}}\left(h(X)=c(X)\middle|X\in\overline{S}\right)=1-\epsilon&{\color[rgb]{0.6,0.6,0.6}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0.6,0.6}\pgfsys@color@gray@stroke{0.6}\pgfsys@color@gray@fill{0.6}\text{(with
low error on $c$)}}\end{cases}$

As is stands, Definition 2 is tightly linked to the notion of version space.
If $\mathcal{H}$ exhibits overfitting, we are guaranteed that all the version
spaces $\mathcal{H}(h^{*},S)$ (such that $\left|S\right|\leq d_{0}$) derived
from $\mathcal{H}$ contain a hypothesis that generalizes well on the whole
dataset. Moreover, Definition 2 is the literal formalization of the notion of
benign overfitting considered in [zhangUnderstandingDeepLearning2021] and
[belkinReconcilingModernMachinelearning2019]: models that can fit any labeling
–even random– of the train set while still having a good test performance when
evaluated on the target distribution.

This definition of large capacity models enables the same analysis as in
subsection III-A, without the requirement that the hypothesis class
$\mathcal{H}$ spans the entire set of functions
$\left\\{0,1\right\\}^{\mathcal{X}}$.

[Benign overfitting and $\mu$-diameter] Let $\mathcal{X}$ and
$\mathcal{H}\subseteq\\{0,1\\}^{\mathcal{X}}$ be any input space and
hypothesis class. Assume that $\mathcal{H}$ exhibits benign overfitting with
respect to the sensitive attribute $X_{A}$ and its opposite $1-X_{A}$ 333That
is, Definition 2 holds for $c=x_{A}$ and $c=1-x_{A}$, then $\forall d\leq
d_{0},S\in\mathcal{X}^{d}$,

$\displaystyle\operatorname{diam}_{\mu}\mathcal{H}(h^{*},S)\geq$
$\displaystyle\operatorname{\mathbb{P}}\left(X\in
S\middle|X_{A}=1\right)+\operatorname{\mathbb{P}}\left(X\in
S\middle|X_{A}=0\right)$ $\displaystyle-2\operatorname{\mathbb{P}}\left(X\in
S\right)-2\epsilon\left(1-\operatorname{\mathbb{P}}\left(X\in S\right)\right)$

###### Proof.

Note
$\alpha_{1}=\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=1\right)$
and
$\alpha_{0}=\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=0\right)$.
In the proof of subsection III-A, we established the following equality:

$\displaystyle\operatorname{diam}_{\mu}\mathcal{H}(h^{*},S)$ (30)
$\displaystyle=\hbox{\pagecolor{orange!20!white}$\max_{h\in\mathcal{H}(h^{*},S)}\left\\{\alpha_{1}\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=1,X\in\overline{S}\right)+\alpha_{0}\operatorname{\mathbb{P}}\left(h(X)=0\middle|X_{A}=0,X\in\overline{S}\right)\right\\}$}$
$\displaystyle-\hbox{\pagecolor{blue!20!white}$\min_{h\in\mathcal{H}(h^{*},S)}\left\\{\alpha_{1}\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=1,X\in\overline{S}\right)+\alpha_{0}\operatorname{\mathbb{P}}\left(h(X)=0\middle|X_{A}=0,X\in\overline{S}\right)\right\\}$}$
(31)

And

$\hbox{\pagecolor{blue!20!white}\phantom{blind}}=\alpha_{1}+\alpha_{0}-\max_{h\in\mathcal{H}(h^{*},S)}\left\\{\alpha_{1}\operatorname{\mathbb{P}}\left(h(X)=0\middle|X_{A}=1,X\in\overline{S}\right)+\alpha_{0}\operatorname{\mathbb{P}}\left(h(X)=1\middle|X_{A}=0,X\in\overline{S}\right)\right\\}$
(32)

Since $\mathcal{H}$ exhibits benign overfitting with respect to the sensitive
attribute and $\left|S\right|<=d_{0}$, there exists $h\in\mathcal{H}(h^{*},S)$
such that
$\operatorname{\mathbb{P}}\left(h(X)=X_{A}\middle|X\in\overline{S}\right)=1-\epsilon$.
Moreover,

$\displaystyle\operatorname{\mathbb{P}}\left(h(X)=X_{A}\middle|X\in\overline{S}\right)=$
$\displaystyle\operatorname{\mathbb{P}}\left(h(X)=1\middle|X\in\overline{S},X_{A}=1\right)\operatorname{\mathbb{P}}\left(X_{A}=1\middle|X\in\overline{S}\right)$
$\displaystyle+\operatorname{\mathbb{P}}\left(h(X)=0\middle|X\in\overline{S},X_{A}=0\right)\operatorname{\mathbb{P}}\left(X_{A}=0\middle|X\in\overline{S}\right)$
(33) $\displaystyle=$
$\displaystyle\alpha_{1}\frac{\operatorname{\mathbb{P}}\left(X_{A}=1\right)}{\operatorname{\mathbb{P}}\left(X\in\overline{S}\right)}\operatorname{\mathbb{P}}\left(h(X)=1\middle|X\in\overline{S},X_{A}=1\right)$
$\displaystyle+\alpha_{0}\frac{\operatorname{\mathbb{P}}\left(X_{A}=0\right)}{\operatorname{\mathbb{P}}\left(X\in\overline{S}\right)}\operatorname{\mathbb{P}}\left(h(X)=1\middle|X\in\overline{S},X_{A}=0\right)$
(34)

Since
$\operatorname{\mathbb{P}}\left(X_{A}=0\right)+\operatorname{\mathbb{P}}\left(X_{A}=1\right)=1$,
$\operatorname{\mathbb{P}}\left(X_{A}=0\right)\geq 0$ and
$\operatorname{\mathbb{P}}\left(X_{A}=1\right)\geq 0$, we have

$\displaystyle\alpha_{1}\operatorname{\mathbb{P}}\left(h(X)=1\middle|X\in\overline{S},X_{A}=1\right)+\alpha_{0}\operatorname{\mathbb{P}}\left(h(X)=1\middle|X\in\overline{S},X_{A}=0\right)$
$\displaystyle\geq\operatorname{\mathbb{P}}\left(X_{A}=1\right)\alpha_{1}\operatorname{\mathbb{P}}\left(h(X)=1\middle|X\in\overline{S},X_{A}=1\right)+\operatorname{\mathbb{P}}\left(X_{A}=0\right)\alpha_{0}\operatorname{\mathbb{P}}\left(h(X)=1\middle|X\in\overline{S},X_{A}=0\right)$
(35)
$\displaystyle=(1-\epsilon)\operatorname{\mathbb{P}}\left(X\in\overline{S}\right)$
(36)

Therefore,

$\hbox{\pagecolor{orange!20!white}\phantom{blind}}\geq(1-\epsilon)\operatorname{\mathbb{P}}\left(X\in\overline{S}\right)$
(37)

With the same arguments, we prove

$\hbox{\pagecolor{blue!20!white}\phantom{blind}}\leq\alpha_{0}+\alpha_{1}-(1-\epsilon)\operatorname{\mathbb{P}}\left(X\in\overline{S}\right)$
(38)

To conclude,

$\operatorname{diam}_{\mu}\mathcal{H}(h^{*},S)\geq
2(1-\epsilon)\operatorname{\mathbb{P}}\left(X\in\overline{S}\right)-(\alpha_{0}+\alpha_{1})$
(39)

∎

Observe that lower bound on the $\mu$-diameter given by Definition 2 only
depends on the aggregated quantities
$\operatorname{\mathbb{P}}\left(X\in\overline{S}\right)$,
$\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=1\right)$ and
$\operatorname{\mathbb{P}}\left(X\in\overline{S}\middle|X_{A}=1\right)$. As
for subsection III-A, this implies that no audit method, active or not can
perform better than a simple random sampling baseline (Algorithm 1) with the
right proportions $\beta_{1}$ and $\beta_{2}$. The term
$\operatorname{\mathbb{P}}\left(X\in
S\middle|X_{A}=1\right)+\operatorname{\mathbb{P}}\left(X\in
S\middle|X_{A}=0\right)-2\operatorname{\mathbb{P}}\left(X\in S\right)$
indicates the importance of the relative proportion of these two audited
groups in the audit set as in subsection III-A. The term
$2\epsilon\left(1-\operatorname{\mathbb{P}}\left(X\in S\right)\right)$
indicates that as expected, the larger the error rate $\epsilon$ gets, the
smaller the $\mu$-diameter will be. Thus, when the hypothesis class exhibits
benign overfitting, all audit algorithms –active or not– have at most the same
manipulation-proofness guarantees as random sampling. This shows that large
models currently used in production are not auditable more efficiently than by
random sampling.

##  IV Manipulability under random audits and model capacity

As shown in section III, the random audit baseline is optimal when the model
has a large capacity, but has no guarantee of optimality when the hypothesis
class is constrained to lower capacities. To compare ML algorithms in
practice, we now introduce a measure of _manipulability under random audits_
and a measure of _model capacity_. We will use these methods to empirically
evaluate the manipulability of auditing several models of increasing
capacities in section V.

###  IV-A Measuring the manipulability under random audits of practical models

The manipulability of a hypothesis class $\mathcal{H}$, is defined (Equation
40) as the $\mu$-diameter obtained and averaged over audit datasets $S$
sampled by the random audit baseline Algorithm 1 with budget $s$.

$\text{Manipulability}(\mathcal{H},s)=\mathbb{E}_{S,h^{*}}\left[\operatorname{diam}_{\mu}\mathcal{H}(S,h^{*})\right]$
(40)

#### The manipulability under random audits is a lower bound of the auditor
”power”

In a perfect situation, for any budget $s=\left|S\right|$, the auditor would
be able to select the audit set $S^{*}$ that attains the minimum
$\mu$-diameter, whatever the hypothesis class $\mathcal{H}$ and chosen
hypothesis $h^{*}\in\mathcal{H}$ are. As explained in subsection II-E, this is
not possible in practice for computational reasons and thus cannot be
simulated. Thus we evaluate the manipulability under random audits with the
baseline random audit strategy (Algorithm 1). Taking the expectation of
$\operatorname{diam}_{\mu}\mathcal{H}(h^{*},S)$ over random audits allows to
upper bound the value of the minimum attainable $\mu$-diameter
$\min_{\mathcal{A}}\operatorname{diam}_{\mu}\mathcal{H}(h^{*},\mathcal{A}(h^{*}))$.

#### The manipulability under random audits is a lower bound of the platform
”power”

In a fully adversarial setting, whatever the hypothesis class $\mathcal{H}$,
the platform would choose the hypothesis $h^{*}$ that maximizes
$\operatorname{diam}_{\mu}\mathcal{H}(h^{*},S)$ for most of the audit sets $S$
the auditor could come up with. While this would effectively be the worst case
for the auditor, it is however unlikely to happen in practice since the
platform would have to balance the maximization of the accuracy with the
maximization of the $\mu$-diameter. Therefore, we consider the more practical
situation in which the platform can freely choose the hypothesis class
$\mathcal{H}$ but the implemented instance $h^{*}$ minimizes a classical loss
$L$ adapted to the model being trained (e.g. cross-entropy or $\ell_{2}$
norm). This can be seen as a lower bound of the adversarial ”power” of the
platform.

###  IV-B Measuring the capacity of practical models

There are multiple operationalizations of the notion of capacity, from
theoretically-rooted metrics such as the VC dimension
[vapnikUniformConvergenceRelative1971] or Rademacher complexity [shalev-
shwartzUnderstandingMachineLearning2014], to more empirical definition such as
the number of iterations until overfitting
[zhangUnderstandingDeepLearning2021]. The interplay between VC-dimension and
manipulability under random audits is already pointed out in
[yanActiveFairnessAuditing2022], where it is observed that models of VC-
dimension higher than $1,600$ have a high manipulability under random audits.

Unfortunately, the VC dimension of a class is difficult to estimate in
practical settings. Instead, the empirical Rademacher complexity (Equation 41)
is leveraged to quantify the capacity of the studied hypothesis classes.
Informally in our setting, a hypothesis class has a high Rademacher complexity
if whatever the labels and size of an audit set $S$, there exists an instance
$h_{S}\in\mathcal{H}$ that fits those labels on $S$ with high accuracy. To
avoid threshold effects in our experiments, we average the complexity over
different sizes of $D$ considered in the Rademacher metric (Equation 42).
Formally:

$\displaystyle R_{m}(\mathcal{H}\circ D)$
$\displaystyle=\frac{1}{m}\mathbb{E}_{\bm{\sigma}\sim\\{\pm
1\\}^{m}}\left[\sup_{h\in\mathcal{H}}\sum_{x_{i}\in
D}\sigma_{i}h(x_{i})\right]$ (41) $\displaystyle\text{Capacity}(\mathcal{H})$
$\displaystyle=\mathbb{E}_{\begin{subarray}{c}D\sim\mathcal{X}^{m}\;\;\;\\\
m\sim\llbracket\left|\mathcal{X}\right|\rrbracket\end{subarray}}\left[R_{m}(\mathcal{H}\circ
D)\right]$ (42)

Figure 3: Distribution of the capacity (horizontal axis) for different
hyperparameters choices on the three datasets (vertical axis). Each model is
trained with different hyperparameter values with each couple (model,
hyperparameter) representing a different hypothesis class $\mathcal{H}$. For
each (model, hyperparameter) couple, the empirical Rademacher values
$R_{m}(\mathcal{H}\circ D)$ are averaged over $15$ realizations of $D$ and
$\sigma_{i}$ before computing the model capacity.  Figure 4: Distribution of
the Manipulability (manipulability under random audits) values (horizontal
axis) of different models $\mathcal{F}$ on a selection of datasets (vertical
axis). Each bar represents a different model $\mathcal{F}$ (trees, linear
models, …). Each model is trained with different hyperparameter values with
each couple (model, hyperparameter) representing a different hypothesis class
$\mathcal{H}$. For each dataset, the size of the audit set is set to $10\%$ of
the dataset size: $\left|S\right|=0.1\left|\mathcal{X}\right|$. For each
(model, hyperparameter) couple, the $\mu$-diameter are averaged over $15$
audit datasets before computing the manipulability.

##  V Experiments

In this section, we explore the relation of the manipulability under random
audits (Equation 40) with the capacity of hypothesis classes (Equation 42).
The following experiments were run on three tabular datasets: StudentPerf
[cortezUsingDataMining2008], COMPAS [larsonHowWeAnalyzed2016] and AdultIncome
[dingRetiringAdultNew2021]. Dataset statistics and considered tasks are
presented in Table II. Neural methods on tabular data are still outperformed
by tree methods [grinsztajnWhyTreebasedModels2022]. We thus choose to focus
our study on the four following models: linear models, perceptrons, decision
trees and gradient-boosted trees. Similar to
[grinsztajnWhyTreebasedModels2022], we selected a range of hyperparameters for
each model and sampled a total of $500$ hyperparameters over the $4$ models.
In previous sections, we stated results with respect to a given hypothesis
class $\mathcal{H}$. In the following experiments, a hypothesis class
$\mathcal{H}$ represents a couple (model, hyperparameters). Thus, a model
represents a family of hypothesis classes
$\mathcal{F}=(\mathcal{H}_{1},\dots,\mathcal{H}_{f})$, each hypothesis class
$\mathcal{H}_{i}$ being associated with a hyperparameters tuple.

The hyperparameters and their value range are presented in Table III. For each
model, we created a grid with all the possible combinations of hyperparameter
values and ran our experiments on all the resulting (model, hyperparameter)
couples. The code needed to run the experiment, the hyperparameters, the data
we obtained and the code to reproduce the figures will be made available upon
publication.

Table II: Datasets stats dataset |  Size $n$ |  Features $d$ |  Task
---|---|---|---
StudentPerf |  395 |  43 |  Predict if students pass the exam
COMPAS |  6172 |  21 |  Predict subject recidivism
AdultIncome |  $22,268$ |  10 |  Predict if income is $\geq\$50,000$
Table III: Value range for the hyperparameters of the models used in the experiments. Model & hyperparameters |  Value range
---|---
blind |
linear |
penalty |  (None, l2)
C |  (0.001, 0.01, 0.1, 1, 10, 100, 1000, 10000)
perceptron |
penalty |  (l2, )
alpha |  (1e-06, 1e-05, 0.0001, 0.001, 0.01)
tree |
max_depth |  (2, 4, 8, 16, 32, 64, 128)
ccp_alpha |  (0.001, 0.003, 0.005, 0.007, 0.01, 0.05, 0.1, 0.2, 0.5, 0.0)
gbdt |
max_depth |  (1, 2, 4, 8)
n_estimators |  (100, 200, 500)
reg_lambda |  (0.0, 1e-6, 1e-3, 0.1, 1.0, 1e6, 1e7)
max_leaves |  (0,)
learning_rate |  (0.3,)
gamma |  (0.0,)
min_child_weight |  (0.0,)
max_delta_step |  (0.0,)
subsample |  (1.0,)
reg_alpha |  (0.0,)
early_stopping_rounds |  (None,)

###  V-A Simulating hypothesis spaces with a broad range of manipulability and
capacity

In Figure 4, we plot the manipulability under random audits of different
hypothesis classes. These classes are constructed by using multiple
hyperparameters for each family $\mathcal{F}$ listed in Table III; each dot
then represents a specific (family, hyperparameter set) couple. On one hand,
for large datasets (such as AdultIncomeand COMPAS), we observe that simpler
models (linear, perceptron) have a very low manipulability, no matter the
hyperparameter set used. On the other hand, for smaller datasets (such as
StudentPerf), smaller models (such as linear models or perceptrons) can also
fit the data hence also becoming harder to audit.

Similarly, in Figure 3, we plot the capacity of the simulated hypothesis
classes on AdultIncome, COMPAS and StudentPerf. As discussed before, it can be
observed that for AdultIncome and StudentPerf datasets, tree-based models
reach the maximum capacity value of $1$. However, on the COMPAS dataset all
hypothesis classes exhibit capacity values that do not exceed $0.2$ points.
This has been observed before [dresselAccuracyFairnessLimits2018] and does not
affect our main argument on the link between model capacity and
manipulability.

###  V-B Model capacity conditions manipulability

Figure 5:  Distribution of the manipulability under random audits values
(vertical axis) of different models versus their capacity (horizontal axis) on
a selection of datasets. Each point represents a couple (model,
hyperparameter). For each dataset, the size of the audit set is set to $10\%$
of the dataset size: $\left|S\right|=0.1\left|\mathcal{X}\right|$. For each
(model, hyperparameter) couple, the Manipulability is averaged over $15$ audit
datasets, and the capacity is computed over $30$ randomizations of the dataset
labels. The error bars represent the standard deviation.

In subsection IV-A we compared different models and how difficult they were to
audit, depending on the chosen hyperparameters. We now take a closer look at
the impact of a model’s capacity on its manipulability under random audits, in
an attempt to confirm the link between both concepts. We plot in Figure 5 the
relation between the capacity of a hypothesis class and its manipulability
under random audits. Points also represent (model, hyperparameter) couples,
while the vertical error bars represent the standard deviation of the
$\mu$-diameter values for different random audit sets $S$.

Consistent with the intuition and results developed until now, we observe that
for all the datasets, the manipulability under random audits increases with
the capacity of the hypothesis class. While on both AdultIncome and
StudentPerf, the $\mu$-diameter reaches the maximum capacity value at almost
$2$, for COMPAS, the effect is not as dramatic. To highlight the connection
between the results exposed in section III and the empirical relation found
between model capacity and manipulability under random audits, we focus next
on two specific points, marked with the letters $A$ and $B$ in Figure 5.

First, consider the point $A=(\text{Capacity}\simeq
0,\text{Manipulability}\simeq 0)$. For a hypothesis class to have a null
capacity, it has to have null Rademacher complexity on any subset of the
sample space. This is verified by models that perform no better than random
labels generation. Since the value of $\mu(h,\mathcal{X})$ of any instance of
such hypothesis class is only determined by the ratio of samples with a
positive sensitive attribute, the $\mu$-diameter of such hypothesis class is
null. This is why in Figure 5, models with near-zero capacity have a very low
(if not null) manipulability under random audits.

The second notable point is
$B=(\text{Capacity}=\text{Capacity}_{\max},\text{Manipulability}=\text{Manipulability}_{\max})$.
Any hypothesis with a unitary capacity has a unitary Rademacher complexity for
any dataset size $s$ and thus shatters any subset of $\mathcal{X}$. Therefore,
at point B, subsection III-A’s hypothesis
$\mathcal{H}=\left\\{0,1\right\\}^{\mathcal{X}}$ holds. This means that
hypothesis classes that are characterized by this point cannot be audited more
efficiently than by a random audit strategy. It follows that (at least on
StudentPerf and AdultIncome) the platform can always choose a hypothesis class
that cannot be audited efficiently by any strategy, forcing the auditor to
prompt most of the input space to obtain robustness guarantees.

#### Generalization versus diameter

We saw that by choosing the right hypothesis class (that is, the right set of
hyperparameters), the platform can easily evade the audit. However, in
practice the choice of hypothesis class is also guided by a classical train-
dev-test separation, choosing the hyperparameter set that generalizes best.
What is the typical $\mu$-diameter of hypotheses classes that generalize well?
To answer this question, we simulate a 5-fold hyperparameter optimization
procedure. For each family of models, we denote $\mathcal{H}_{\text{opt}}$ the
hypothesis class with the set of hyperparameters that minimize the 5-fold
average test loss in its model family $\mathcal{F}$. For each model family,
$\mathcal{H}_{\text{opt}}$ is differentiated in Figure 5 by a star marker with
red edges. Interestingly, for COMPAS and AdultIncome datasets and for all
model families, the generalization-optimal hypothesis classes
$\mathcal{H}_{\text{opt}}$ have a relatively low capacity compared to the
maximum achievable capacity, especially for tree-based models. For the
StudentPerf dataset, the results are more nuanced, most likely because the
dataset has a limited size, which implies that it is simpler to reach high
capacity values.

As a glimmer of hope, from point $A$ to $B$, there is a range of hypothesis
classes for which the random strategy could be improved as seen by the size of
the $y$-axis error bars. Overall, the hypothesis classes that are most likely
to be implemented by faithful platforms (the hypothesis classes that
generalize well) are already straightforward to audit (they have a
$\text{Manipulability}\approx 0$). Yet, unfaithful platforms wanting to game
the audit can always choose a hypothesis class that forces the auditor to
issue a lot of queries to reach higher manipulation-proofness guarantees.

###  V-C The cost of exhausting the auditor

Figure 6: Distribution of the cost of exhaustion for the four model families
(perceptron, linear, tree and GBDT) on the three considered datasets. The
error bars show the $95\%$ confidence interval on the values of the difference
of $\text{Accuracy}_{\text{test}}$ for the best hypotheses in
$\mathcal{H}^{\text{acc}}$ and $\mathcal{H}^{\mu}$. For all models, on all
datasets (except for trees and linear models on StudentPerf), the cost of
exhaustion is below $1\%$. Trees are the models with the highest cost of
exhaustion, while for all the other models, the cost of exhaustion remains
relatively low (in particular for the large capacities GDBTs), indicating a
negligible accuracy cost for audit evasion.

We observed in section III and subsection IV-A that the hypothesis classes
that are the hardest to audit are those with the largest capacity. Yet, we
also observed that the hypothesis classes most likely to be implemented (i.e.
the ones with the highest generalization) have a low $\mu$-diameter and are
not those with high capacity. In the manipulation-proof framework of
[yanActiveFairnessAuditing2022] we operate in, the platform chooses the
hypothesis class without constraints before disclosing it to the auditor.
Therefore, when choosing a specific model family $\mathcal{F}$, a malicious
platform would have the possibility to trade performance (i.e. generalization
capability) with the ability to attempt audit evasion. To understand the
trade-offs involved in balancing these two objectives, we introduce the notion
of $\text{CostOfExhaustion}(\mathcal{F})$ of a model family $\mathcal{F}$.

A model family
$\mathcal{F}=\left\\{\mathcal{H}_{1},\dots,\mathcal{H}_{F}\right\\}$ is a set
of hypothesis classes. The family $\mathcal{F}$ of decision trees where each
hypothesis class $\mathcal{H}_{i}$ corresponds to a maximum depth value $i$ is
an example of model family. To define the CostOfExhaustion metric, we first
introduce two particular hypothesis ($\mathcal{H}^{\text{acc}}$ and
$\mathcal{H}^{\mu}$) classes of $\mathcal{F}$. $\mathcal{H}^{\text{acc}}$ is
the hypothesis class in $\mathcal{F}$ with the best trained test accuracy:

$\mathcal{H}^{\text{acc}}=\operatorname*{arg\max}_{\mathcal{H}\in\mathcal{F}}\max_{h\in\mathcal{H}}\text{Accuracy}_{\text{test}}(h,\mathcal{X})$
(43)

Assuming that an honest platform chooses its hypothesis class based on
generalization capabilities, $\mathcal{H}^{\text{acc}}$ is the hypothesis
class an honest platform would actually choose. Then, define the hypothesis
class in $\mathcal{F}$ with the largest manipulability (for a fixed audit
budget $s$):

$\mathcal{H}^{\mu}=\operatorname*{arg\max}_{\mathcal{H}\in\mathcal{F}}\text{Manipulability}(\mathcal{H},s)$
(44)

Should a platform try to escape audits at a low cost, they would try to find a
hypothesis class whose optimal hypothesis $h^{*}$ leads to a high
$\mu$-diameter. Thus, the cost of exhaustion is the accuracy cost of using the
hypothesis class $\mathcal{H}^{\mu}$ compared to using
$\mathcal{H}^{\text{acc}}$:

$\displaystyle\text{CostOfExhaustion}(\mathcal{F})=$
$\displaystyle\quad\max_{h\in\mathcal{H}^{\text{acc}}}\text{Accuracy}_{\text{test}}(h,\mathcal{X})-\max_{h\in\mathcal{H}^{\mu}}\text{Accuracy}_{\text{test}}(h,\mathcal{X})$
(45)

The cost of exhaustion is plotted in Figure 6, for the four model families
already considered, on the three datasets. The error bars show the $95\%$
confidence interval on the values of the difference of
$\text{Accuracy}_{\text{test}}$ for the best hypotheses in
$\mathcal{H}^{\text{acc}}$ and $\mathcal{H}^{\mu}$. For all models, on all
considered datasets (except for trees and linear models on the dataset
StudentPerf), the cost of exhaustion is below $1\%$. Trees are the models with
the highest cost of exhaustion. In fact, as we observed in Figure 5, given
enough capacity, trees can reach the maximum manipulability under random
audits. Yet, it is known that without regularization, complex trees can easily
overfit the training data, thus lowering the max test accuracy of the
$\mathcal{H}^{\mu}$ class compared to the max test accuracy of
$\mathcal{H}^{\text{acc}}$. On the other hand, the models with the lowest cost
of exhaustion (except on StudentPerf) are linear models. As observed on Figure
3, for all datasets, linear models span a small portion of the capacity range
(around $.1$ points for StudentPerf and less than $.01$ points for COMPAS and
AdultIncome), compared to larger models (e.g. GBDTs) which cover almost the
entire capacity range on StudentPerf and AdultIncome. This result is
challenging for the existence of efficient audits in the manipulation-proof
framework. In fact, the witnessed low cost of exhaustion for larger capacity
models indicates that platforms may evade audits at the cost of a minor loss
in accuracy.

###  V-D Effects of the audit set size

Figure 7:  Evolution of the $\mu$-diameter with the size of the audit set $S$
represented as a proportion of the total dataset size for the AdultIncome
dataset. Each line represents an audited model, whose hyperparameters are
either tuned for the best generalization, either tuned for the highest
capacity or tuned for the lowest capacity. For each (model, hyperparameter)
couple, the $\mu$-diameter is averaged over $15$ audit datasets.

In this section, we experiment with different sizes of audit dataset and show
that our conclusions do not change with the change in dataset size (we had
$\left|S\right|=.1\left|\mathcal{X}\right|$ in previous experiments). To do
so, we select three different hypotheses classes for each model family. We
choose the hypothesis class that generalizes best $\mathcal{H}_{\text{opt}}$,
the hypothesis class with the lowest capacity $\mathcal{H}_{-}$ and with the
highest capacity $\mathcal{H}_{+}$. In Figure 7 we show the audit difficulty
of each hypothesis class against the size of the audit dataset
$\left|S\right|$. The results indicate that there is no significant inversion
of the manipulability under random audits between the various hypotheses in
the range of interest. Results in Figure 7 are shown only for the AdultIncome
dataset. The results for the other datasets are showed in the Appendix, in
Figures 8 and 9, which to the same conclusion.

##  VI Related work

The problem of manipulation-proof auditing and more generally black-box,
remote, and robust property verification of ML platforms arises from the need
to enforce regulations. As an example, consider the European Union. Classical
fairness regulation of online ML models mainly comes from the _Racial Equality
Directive_ [CouncilDirective20002000], the _Framework Equality Directive_
[CouncilDirective20002000a] and the _Gender Equality Directives_
[CouncilDirective20042004, Directive2006542006]. Recently, the EU set out to
create regulations specific to online platforms. These are the _AI Act_
[ProposalREGULATIONEUROPEAN2021], the _Digital Services Act_
[RegulationEU20222022] and the _Digital Markets Act_ [RegulationEU20222022a].
These directives provide a legal framework that prescribes what online
platforms may and may not do, but offer little to verify that these rules are
respected in practice. The manipulation-proof framework is a first attempt to
provide operational solutions that can detect when platforms do not follow the
law.

In addition, our results are mostly related to the following lines of work.

#### Algorithm auditing

The field of algorithm auditing is interested in understanding the impact of
algorithms on the lives or the people impacted by those algorithms’ decisions.
In practice, auditing algorithms _in vivo_ (that is as they are deployed in
online services) is challenging because they constantly evolve, mostly without
records [metaxaAuditingAlgorithmsUnderstanding2021]. For a survey on examples
of published academic audits of decision systems, refer to
[bandyProblematicMachineBehavior2021]. Moreover, because it is impossible for
researchers or regulators to audit each automated decision system, it has been
observed that most of the recent discoveries of problematic algorithm behavior
have surfaced thanks to users of those systems
[devosUserDrivenAlgorithmAuditing2022,
dengUnderstandingPracticesChallenges2023]. Again, after a problematic
algorithm behavior has been detected and after a court decision has been made,
we still need to be able to monitor that this decision is respected.

#### Audit metrics and audit design

With the advent of broadly publicized algorithm audits such as COMPAS
[larsonHowWeAnalyzed2016] or Reuters’ study on Amazon’s recruiting tool
[dastinAmazonScrapsSecret2018], there has been an effort to devise metrics and
their interpretations to better understand the impact of algorithms on their
users. Most of the effort has been directed towards the operationalization of
fairness values into the ML framework [barocasFairnessMachineLearning2023].
Classical fairness measures include Demographic Parity
[caldersBuildingClassifiersIndependency2009], Equalized Odds
[hardtEqualityOpportunitySupervised2016], Equal Opportunity
[hardtEqualityOpportunitySupervised2016] or Predictive Parity [corbett-
daviesAlgorithmicDecisionMaking2017]. All of these measures encompass
different visions of fairness and choosing one versus the other has political
implications on the considered notion of fairness
[heidariMoralFrameworkUnderstanding2019,
arvindnarayananTutorial21Fairness2018]. While still marginal, some works are
interested in other aspects of the audit of AI algorithms. For example,
[rastegarpanahAuditingBlackBoxPrediction2021] is interested in the
verification that online platforms comply with the Data Minimization
Principle. Another interesting work [luGeneralFrameworkAuditing2022] considers
the problem of automatically auditing the privacy guarantees offered by AI
algorithms. However, most of the presented works do not yet consider the
possibility of the platform gaming their audit.

#### Robust verification

The literature on robust auditing is still in its infancy. The manipulation-
proof [yanActiveFairnessAuditing2022] framework has only recently been
introduced. However, with its goal of efficiently choosing the next audit
query based on previous queries and the associated outputs of the API, the
manipulation-proof framework exhibits clear links with the active learning
literature [hannekeTeachingDimensionComplexity2007,
dasguptaTeachingBlackboxLearner2019]. With the aim of finding methods to ease
the audit, [yadavXAuditTheoreticalLook2023] showed that the explanation
provided by the platform can greatly improve the robustness of audits. For
example, they show that for linear classifiers, a single result along its
counterfactual explanation allows to totally characterize the model. Our work
does not assume that the auditor has access to explanations. It is likely that
faithful explanation could lead to audit algorithms with increased MP
guarantees. On another line of works,
[shamsabadiConfidentialPROFITTConfidentialPROof2023] and
[goldwasserInteractiveProofsVerifying2021] suggest instantiating an audit
protocol in which both the platform and the auditor would be active, drawing
inspiration from zero-knowledge proofs and interactive verification protocols.

#### Benign overfitting and model capacity

As we proved in this work, manipulability under random audits has deep
connections with model capacity and their ability to perfectly fit arbitrary
datasets. Classical metrics that capture the notion of model capacity include
the VC-dimension [vapnikUniformConvergenceRelative1971] or the Rademacher
Complexity (which we used for its usability in practice) [shalev-
shwartzUnderstandingMachineLearning2014]. Moreover, our experiments on the
link between auditability and model capacity have been motivated by the recent
finding that larger models can fit the training dataset perfectly while still
showing good generalization properties [zhangUnderstandingDeepLearning2021].
This effect has been observed for linear models
[bartlettBenignOverfittingLinear2020], Support Vector Machines
[wangBenignOverfittingMulticlass2021a] and Decision Trees
[arnouldInterpolationBenignRandom2023]. In the manipulation-proof audit
setting, we show that this type of behavior is very problematic. In fact, if a
model is able to fit any audit set and yet keep its generalization
performance, platforms do not even have to lie to the auditor. They just have
to train their model to give the answers the auditor expects on their audit
set. Then, the platform can define any objective for the rest of the input
space, even if it does not align with the auditor’s metric.

Interestingly, the connection between model capacity and audit query
complexity is not limited to manipulation-proof estimation of parity measures.
In their work on certified feature sensitivity auditing
[yadavXAuditTheoreticalLook2023], [yadavXAuditTheoreticalLook2023] provide an
algorithm to audit feature sensitivity for decision trees whose query
complexity grows linearly with the capacity (number of nodes) of the tree.

##  VII Conclusion and discussions

The introduction of the _manipulation-proofness_ framework
[yanActiveFairnessAuditing2022] has certainly been an important step for
auditors to start understanding that algorithmic audits can suffer from
platform manipulations and what cost that brings along.

In this work, we conducted a thorough exploration of the concept of
manipulation-proofness. We derived theoretical conditions on the hypothesis
class implemented by the platform for the impossibility of efficient
manipulation-proof audits. We carried out a thorough experimental validation
on the _manipulability under random audits_ of state-of-the-art models for
tabular data. Our results draw a connection between the capacity of the
audited model and the difficulty of the audit task.

We now discuss some countermeasures to improve the audit robustness. A
promising line of work is to require platforms to provide certificates. Since
the goal of certificates is to provide a cheap verification procedure (at the
cost of a potentially high certificate generation cost), this would shift the
computational burden to the platform. One example of a fairness certificate
was provided in [shamsabadiConfidentialPROFITTConfidentialPROof2023]. Such
extended assumptions (over mere black box audits) are certainly an interesting
research line for future works.

In the end, when implementing large-capacity models, a platform can always
game the audit without sacrificing too much accuracy. We believe that this
demonstrates the limitations of black-box auditing for regulation, even when
the hypothesis class used by the platform is known to the regulator. We claim
that regulators should be given more than black-box access to AI models as
part of the audit procedure or that they should explore certification-based
audits such as [shamsabadiConfidentialPROFITTConfidentialPROof2023].
Therefore, we urge the community to participate in the search for audit
frameworks that are both exploitable in practice and also supported by
theoretical guarantees.

## References

  * [1] Jeff Larson, Surya Mattu, Lauren Kirchner and Julia Angwin  “How We Analyzed the COMPAS Recidivism Algorithm”  In _ProPublica_ , 2016  URL: https://www.propublica.org/article/how-we-analyzed-the-compas-recidivism-algorithm
  * [2] Jeffrey Dastin  “Amazon Scraps Secret AI Recruiting Tool That Showed Bias against Women”  In _Reuters_ , 2018  URL: https://www.reuters.com/article/us-amazon-com-jobs-automation-insight-idUSKCN1MK08G
  * [3] Marco Tulio Ribeiro, Sameer Singh and Carlos Guestrin  “”Why Should I Trust You?”: Explaining the Predictions of Any Classifier”  In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’16  New York, NY, USA: Association for Computing Machinery, 2016, pp. 1135–1144  DOI: 10.1145/2939672.2939778
  * [4] Scott M Lundberg and Su-In Lee  “A Unified Approach to Interpreting Model Predictions”  In _Advances in Neural Information Processing Systems_ 30 Curran Associates, Inc., 2017  URL: https://proceedings.neurips.cc/paper/2017/hash/8a20a8621978632d76c43dfd28b67767-Abstract.html
  * [5] Tom Yan and Chicheng Zhang  “Active Fairness Auditing”  In _Proceedings of the 39th International Conference on Machine Learning_ PMLR, 2022, pp. 24929–24962  URL: https://proceedings.mlr.press/v162/yan22c.html
  * [6] Ali Shahin Shamsabadi et al.  “Confidential-PROFITT: Confidential PROof of FaIr Training of Trees”, 2023  URL: https://openreview.net/forum?id=iIfDQVyuFD
  * [7] J. Matias, Austin Hounsel and Nick Feamster  “Software-Supported Audits of Decision-Making Systems: Testing Google and Facebook’s Political Advertising Policies”  In _Proceedings of the ACM on Human-Computer Interaction_ 6, 2022, pp. 118:1–118:19  DOI: 10.1145/3512965
  * [8] Bashir Rastegarpanah, Krishna Gummadi and Mark Crovella  “Auditing Black-Box Prediction Models for Data Minimization Compliance”  In _Advances in Neural Information Processing Systems_ 34 Curran Associates, Inc., 2021, pp. 20621–20632  URL: https://proceedings.neurips.cc/paper/2021/hash/ac6b3cce8c74b2e23688c3e45532e2a7-Abstract.html
  * [9] Oded Goldreich  “Foundations of Cryptography: Volume 2, Basic Applications”  Cambridge university press, 2009
  * [10] Danaë Metaxa et al.  “Auditing Algorithms: Understanding Algorithmic Systems from the Outside In”  In _Foundations and Trends® in Human–Computer Interaction_ 14.4, 2021, pp. 272–344  DOI: 10.1561/1100000083
  * [11] Christian Sandvig, Kevin Hamilton, Karrie Karahalios and Cedric Langbort  “Auditing Algorithms: Research Methods for Detecting Discrimination on Internet Platforms”  In _Data and discrimination: converting critical concerns into productive inquiry_ 22.2014, 2014, pp. 4349–4357  URL: https://www.kevinhamilton.org/share/papers/Auditing%20Algorithms%20--%20Sandvig%20--%20ICA%202014%20Data%20and%20Discrimination%20Preconference.pdf
  * [12] Chhavi Yadav, Michal Moshkovitz and Kamalika Chaudhuri  “XAudit : A Theoretical Look at Auditing with Explanations”, 2023  DOI: 10.48550/arXiv.2206.04740
  * [13] Ben Chugg, Santiago Cortes-Gomez, Bryan Wilder and Aaditya Ramdas  “Auditing Fairness by Betting”, 2023  URL: https://openreview.net/forum?id=EEVpt3dJQj
  * [14] Steve Hanneke  “Theory of Disagreement-Based Active Learning”  In _Foundations and Trends® in Machine Learning_ 7.2-3 Now Publishers, Inc., 2014, pp. 131–309  DOI: 10.1561/2200000037
  * [15] Paulo Cortez and Alice Silva  “Using Data Mining to Predict Secondary School Student Performance”  In _EUROSIS_ , 2008
  * [16] Rashida Richardson  “Defining and Demystifying Automated Decision Systems”  In _Maryland Law Review_ 81, 2021, pp. 785  URL: https://heinonline.org/HOL/Page?handle=hein.journals/mllr81&id=805&div=&collection=
  * [17] Solon Barocas, Moritz Hardt and Arvind Narayanan  “Fairness and Machine Learning: Limitations and Opportunities”  MIT Press, 2023  URL: https://books.google.com/books?hl=en&lr=&id=ouawEAAAQBAJ&oi=fnd&pg=PA83&dq=Fairness+and+Machine+Learning&ots=2kDVfTXV8P&sig=uYNciZV1R1c7X_LakbSmwN_YJYk
  * [18] Fred Lu et al.  “A General Framework for Auditing Differentially Private Machine Learning”, 2022, pp. 4165–4176  URL: https://proceedings.neurips.cc/paper_files/paper/2022/hash/1add3bbdbc20c403a383482a665eb5a4-Abstract-Conference.html
  * [19] Sanjoy Dasgupta, Daniel Hsu, Stefanos Poulis and Xiaojin Zhu  “Teaching a Black-Box Learner”  In _Proceedings of the 36th International Conference on Machine Learning_ PMLR, 2019, pp. 1547–1555  URL: https://proceedings.mlr.press/v97/dasgupta19a.html
  * [20] Jack Bandy  “Problematic Machine Behavior: A Systematic Literature Review of Algorithm Audits”  In _Proceedings of the ACM on Human-Computer Interaction_ 5, 2021, pp. 74:1–74:34  DOI: 10.1145/3449148
  * [21] Tom M. Mitchell  “Generalization as Search”  In _Artificial Intelligence_ 18.2, 1982, pp. 203–226  DOI: 10.1016/0004-3702(82)90040-6
  * [22] Chiyuan Zhang et al.  “Understanding Deep Learning (Still) Requires Rethinking Generalization”  In _Communications of the ACM_ 64.3, 2021, pp. 107–115  DOI: 10.1145/3446776
  * [23] Mikhail Belkin, Daniel Hsu, Siyuan Ma and Soumik Mandal  “Reconciling Modern Machine-Learning Practice and the Classical Bias–Variance Trade-Off”  In _Proceedings of the National Academy of Sciences_ 116.32 Proceedings of the National Academy of Sciences, 2019, pp. 15849–15854  DOI: 10.1073/pnas.1903070116
  * [24] Ludovic Arnould, Claire Boyer and Erwan Scornet  “Is Interpolation Benign for Random Forest Regression?”  In _Proceedings of The 26th International Conference on Artificial Intelligence and Statistics_ PMLR, 2023, pp. 5493–5548  URL: https://proceedings.mlr.press/v206/arnould23a.html
  * [25] Sebastian Buschjäger and Katharina Morik  “There Is No Double-Descent in Random Forests”, 2021  DOI: 10.48550/arXiv.2111.04409
  * [26] V.. Vapnik and A.. Chervonenkis  “On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities”  In _Theory of Probability & Its Applications_ 16.2 Society for Industrial and Applied Mathematics, 1971, pp. 264–280  DOI: 10.1137/1116025
  * [27] Shai Shalev-Shwartz and Shai Ben-David  “Understanding Machine Learning: From Theory to Algorithms”  Cambridge University Press, 2014  DOI: 10.1017/CBO9781107298019
  * [28] Frances Ding, Moritz Hardt, John Miller and Ludwig Schmidt  “Retiring Adult: New Datasets for Fair Machine Learning”  In _Advances in Neural Information Processing Systems_ 34 Curran Associates, Inc., 2021, pp. 6478–6490  URL: https://proceedings.neurips.cc/paper/2021/hash/32e54441e6382a7fbacbbbaf3c450059-Abstract.html
  * [29] Leo Grinsztajn, Edouard Oyallon and Gael Varoquaux  “Why Do Tree-Based Models Still Outperform Deep Learning on Typical Tabular Data?”  In _Advances in Neural Information Processing Systems_ 35, 2022, pp. 507–520  URL: https://proceedings.neurips.cc/paper_files/paper/2022/hash/0378c7692da36807bdec87ab043cdadc-Abstract-Datasets_and_Benchmarks.html
  * [30] Julia Dressel and Hany Farid  “The Accuracy, Fairness, and Limits of Predicting Recidivism”  In _Science Advances_ 4.1, 2018, pp. eaao5580  DOI: 10.1126/sciadv.aao5580
  * [31] “Council Directive 2000/43/EC of 29 June 2000 Implementing the Principle of Equal Treatment between Persons Irrespective of Racial or Ethnic Origin”  In _OJ L_ 180, 2000  URL: http://data.europa.eu/eli/dir/2000/43/oj/eng
  * [32] “Council Directive 2000/78/EC of 27 November 2000 Establishing a General Framework for Equal Treatment in Employment and Occupation”  In _OJ L_ 303, 2000  URL: http://data.europa.eu/eli/dir/2000/78/oj/eng
  * [33] “Council Directive 2004/113/EC of 13 December 2004 Implementing the Principle of Equal Treatment between Men and Women in the Access to and Supply of Goods and Services”  In _OJ L_ 373, 2004  URL: http://data.europa.eu/eli/dir/2004/113/oj/eng
  * [34] “Directive 2006/54/EC of the European Parliament and of the Council of 5 July 2006 on the Implementation of the Principle of Equal Opportunities and Equal Treatment of Men and Women in Matters of Employment and Occupation (Recast)”  In _OJ L_ 204, 2006  URL: http://data.europa.eu/eli/dir/2006/54/oj/eng
  * [35] “Proposal for a REGULATION OF THE EUROPEAN PARLIAMENT AND OF THE COUNCIL LAYING DOWN HARMONISED RULES ON ARTIFICIAL INTELLIGENCE (ARTIFICIAL INTELLIGENCE ACT) AND AMENDING CERTAIN UNION LEGISLATIVE ACTS”, 2021  URL: https://eur-lex.europa.eu/legal-content/EN/TXT/?uri=CELEX:52021PC0206
  * [36] “Regulation (EU) 2022/2065 of the European Parliament and of the Council of 19 October 2022 on a Single Market For Digital Services and Amending Directive 2000/31/EC (Digital Services Act) (Text with EEA Relevance)”  In _OJ L_ , 2022  URL: http://data.europa.eu/eli/reg/2022/2065/oj/eng
  * [37] “Regulation (EU) 2022/1925 of the European Parliament and of the Council of 14 September 2022 on Contestable and Fair Markets in the Digital Sector and Amending Directives (EU) 2019/1937 and (EU) 2020/1828 (Digital Markets Act) (Text with EEA Relevance)”  In _OJ L_ , 2022  URL: http://data.europa.eu/eli/reg/2022/1925/oj/eng
  * [38] Alicia DeVos et al.  “Toward User-Driven Algorithm Auditing: Investigating Users’ Strategies for Uncovering Harmful Algorithmic Behavior”  In _Proceedings of the 2022 CHI Conference on Human Factors in Computing Systems_ , CHI ’22  New York, NY, USA: Association for Computing Machinery, 2022, pp. 1–19  DOI: 10.1145/3491102.3517441
  * [39] Wesley Hanwen Deng et al.  “Understanding Practices, Challenges, and Opportunities for User-Engaged Algorithm Auditing in Industry Practice”  In _Proceedings of the 2023 CHI Conference on Human Factors in Computing Systems_ , CHI ’23  New York, NY, USA: Association for Computing Machinery, 2023, pp. 1–18  DOI: 10.1145/3544548.3581026
  * [40] Toon Calders, Faisal Kamiran and Mykola Pechenizkiy  “Building Classifiers with Independency Constraints”  In _2009 IEEE International Conference on Data Mining Workshops_ , 2009, pp. 13–18  DOI: 10.1109/ICDMW.2009.83
  * [41] Moritz Hardt, Eric Price and Nathan Srebro  “Equality of Opportunity in Supervised Learning”  In _Proceedings of the 30th International Conference on Neural Information Processing Systems_ , NIPS’16  Red Hook, NY, USA: Curran Associates Inc., 2016, pp. 3323–3331
  * [42] Sam Corbett-Davies et al.  “Algorithmic Decision Making and the Cost of Fairness”  In _Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’17  New York, NY, USA: Association for Computing Machinery, 2017, pp. 797–806  DOI: 10.1145/3097983.3098095
  * [43] Hoda Heidari, Michele Loi, Krishna P. Gummadi and Andreas Krause  “A Moral Framework for Understanding Fair ML through Economic Models of Equality of Opportunity”  In _Proceedings of the Conference on Fairness, Accountability, and Transparency_ , FAT* ’19  New York, NY, USA: Association for Computing Machinery, 2019, pp. 181–190  DOI: 10.1145/3287560.3287584
  * [44] “Tutorial: 21 Fairness Definitions and Their Politics”, 2018  URL: https://www.youtube.com/watch?v=jIXIuYdnyyk
  * [45] Steve Hanneke  “Teaching Dimension and the Complexity of Active Learning”  In _Learning Theory_ , Lecture Notes in Computer Science  Berlin, Heidelberg: Springer, 2007, pp. 66–81  DOI: 10.1007/978-3-540-72927-3˙7
  * [46] Shafi Goldwasser, Guy N. Rothblum, Jonathan Shafer and Amir Yehudayoff  “Interactive Proofs for Verifying Machine Learning”  In _12th Innovations in Theoretical Computer Science Conference (ITCS 2021)_ 185, Leibniz International Proceedings in Informatics (LIPIcs)  Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2021, pp. 41:1–41:19  DOI: 10.4230/LIPIcs.ITCS.2021.41
  * [47] Peter L. Bartlett, Philip M. Long, Gábor Lugosi and Alexander Tsigler  “Benign Overfitting in Linear Regression”  In _Proceedings of the National Academy of Sciences_ 117.48 Proceedings of the National Academy of Sciences, 2020, pp. 30063–30070  DOI: 10.1073/pnas.1907378117
  * [48] Ke Wang, Vidya Muthukumar and Christos Thrampoulidis  “Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation”  In _Advances in Neural Information Processing Systems_ 34 Curran Associates, Inc., 2021, pp. 24164–24179  URL: https://proceedings.neurips.cc/paper/2021/hash/caaa29eab72b231b0af62fbdff89bfce-Abstract.html
  * [49] Alekh Agarwal et al.  “A Reductions Approach to Fair Classification”  In _Proceedings of the 35th International Conference on Machine Learning_ PMLR, 2018, pp. 60–69  URL: https://proceedings.mlr.press/v80/agarwal18a.html

##  Appendix A Effect of the audit dataset size

Figure 8:  Evolution of the $\mu$-diameter with the size of the audit set $S$
represented as a proportion of the total dataset size for the AdultIncome
dataset. Each line represents an audited model, whose hyperparameters are
either tuned for the best generalization, either tuned for the highest
capacity or tuned for the lowest capacity. For each (model, hyperparameter)
couple, the $\mu$-diameter is averaged over $15$ audit datasets.  Figure 9:
Evolution of the $\mu$-diameter with the size of the audit set $S$ represented
as a proportion of the total dataset size for the AdultIncome dataset. Each
line represents an audited model, whose hyperparameters are either tuned for
the best generalization, either tuned for the highest capacity or tuned for
the lowest capacity. For each (model, hyperparameter) couple, the
$\mu$-diameter is averaged over $15$ audit datasets.

##  Appendix B How is the $\mu$-diameter measured in practice

As originally defined in [yanActiveFairnessAuditing2022] and following the
definition of the $\mu$-diameter, the evaluation of
$\text{diam}_{\mu}(S,h^{*})$ requires to solve the following optimization
problem:

$\displaystyle\max_{h,h^{\prime}}\quad$
$\displaystyle|\mu(h,S)-\mu(h^{\prime})|$ (46) subject to $\displaystyle
h(x)=h^{\prime}(x)=h^{*}(x)\quad\forall x\in S$ (47)

This problem be separated in two optimization problems: the
maximization/minimization over $h\in\mathcal{H}$ of $\mu(h,S)$ under the
constraint that $\forall x\in S,h(x)=h^{*}(x)$.

$\displaystyle\max_{h}/\min_{h}\quad$ $\displaystyle\mu(h,S)$ (48) subject to
$\displaystyle h(x)=h^{*}(x)\quad\forall x\in S$ (49)

As proposed by [yanActiveFairnessAuditing2022], we use the method introduced
by [agarwalReductionsApproachFair2018] to reframe this constrained
optimization problem as a sequence of weighted classification tasks. Then, we
use off-the-self estimators from scikit-learn and XGBoost to perform the
optimization with the appropriate weights.