# Rare-Earth Molecular Crystals with Ultra-narrow Optical Linewidths for
Photonic Quantum Technologies

###### Abstract

Rare-earth ions are promising solid state systems to build light-matter
interfaces at the quantum level. This relies on their potential to show narrow
optical homogeneous linewidths or, equivalently, long-lived optical quantum
states. In this letter, we report on europium molecular crystals that exhibit
linewidths in the 10s of kHz range, orders of magnitude narrower than other
molecular centers. We harness this property to demonstrate efficient optical
spin initialization, coherent storage of light using an atomic frequency comb,
and optical control of ion-ion interactions towards implementation of quantum
gates. These results illustrate the utility of rare-earth molecular crystals
as a new platform for photonic quantum technologies that combines highly
coherent emitters with the unmatched versatility in composition, structure,
and integration capability of molecular materials.

Diana Serrano1, Kuppusamy Senthil Kumar2,3, Benoît Heinrich4, Olaf Fuhr3,5,
David Hunger2,6, Mario Ruben2,3,7, Philippe Goldner1.
1Chimie ParisTech, PSL University, CNRS, Institut de Recherche de Chimie
Paris, 11, rue Pierre et Marie Curie, 75005 Paris, France

2Institute for Quantum Materials and Technologies (IQMT), Karlsruhe Institute
of Technology (KIT), 76344 Eggenstein-Leopoldshafen, Germany

3 Institute of Nanotechnology, Karlsruhe Institute of Technology (KIT), 76344
Eggenstein-Leopoldshafen, Germany

4Institut de Physique et Chimie des Matériaux de Strasbourg (IPCMS), CNRS-
Université de Strasbourg, Strasbourg, France

5Karlsruhe Nano Micro Facility (KNMF), Karlsruhe Institute of Technology
(KIT),

6Physikalisches Institut, Karlsruhe Institute of Technology (KIT), Wolfgang-
Gaede Str. 1, 76131 Karlsruhe, Germany

7Centre Européen de Sciences Quantiques (CESQ), Institut de Science et
d’Ingénierie Supramoléculaire (ISIS), Université de Strasbourg, France

Rare-earth ion (REI)-doped materials are promising systems for optical quantum
technologies. At cryogenic temperatures, REIs doped into high quality bulk
single crystals, such as Y2SiO5, show exceptionally narrow optical homogeneous
linewidths, equivalent to long-lived quantum coherence lifetime ($T_{2}$) and
suitable for building quantum light-matter interfaces [1]. Moreover, REI can
present optically addressable electron and/or nuclear spin degrees of freedom
that can be leveraged to efficiently store and process quantum information [2,
3]. These unique properties in the solid state have been used to demonstrate
quantum memories for light [4], light-matter teleportation [5], and frequency
and time-multiplexed storage [6]. REI-doped crystals are also actively
investigated for optical to microwave conversion [7] and quantum processing
[8]. Besides experiments on high-quality bulk single crystals, strong efforts
have recently been launched towards combining REIs with nanophotonic
structures [9]. This has enabled single REI detection and control [10], fast
spontaneous emission modulation [11], lifetime limited single-photon emission
[12], and on-chip optical storage [13]. Further developments of these exciting
topics is, however, impeded by the difficulty to nano-fabricate crystalline
host materials that preserve REIs quantum properties for integration into
high-quality nanophotonic devices. Molecular chemistry is very attractive in
this respect because it offers unmatched flexibility in terms of material
composition, fine structural tuning, and integration into photonic structures,
as demonstrated by numerous results obtained with single organic molecules
embedded in crystalline host lattices [14]. However, most organic molecules
studied to date lack a spin degree of freedom. Recently, optically addressable
molecular spins were demonstrated [15, 16], although with limited optical
coherence, hindering their use as coherent spin-photon interfaces. Here, we
introduce REI molecular crystals containing trivalent europium that exhibit
optical homogeneous linewidths between 5 and 30 kHz, 3 to 4 orders of
magnitude narrower than any molecular system [16, 17, 14]. This allows us to
efficiently exploit the Eu3+ nuclear spin degree of freedom by demonstrating
$>$ 95% spin initialization into a single level, and coherent optical storage
using atomic frequency combs. We also harness Eu3+ narrow optical linewidth to
demonstrate ion-ion interactions, which are the basis for high-bandwidth two-
qubit quantum gates[8].

Figure 1: Material and low temperature optical spectroscopy. A. X-ray crystal
structure of the Eu3+ complex. The counter cation is omitted for clarity.
Color code: grey, carbon; white, hydrogen; pink, europium; red, oxygen. B.
Eu3+ photo-luminescence (PL) spectrum showing characteristic
5D${}_{0}\to^{7}$FJ ($J=0-4$) transitions (see inset). All following results
were obtained on the 7F${}_{0}\rightarrow^{5}$D0 transition (in red). C.
7F${}_{0}\rightarrow^{5}$D0 absorption line recorded on a 500 $\mu$m thick
powder sample. Center wavelength: 580.3778 nm (vacuum). D.
5D${}_{0}\rightarrow^{7}$FJ ($J=1-4$) fluorescence decay. Red line: Single
exponential fit to data giving a 5D0 population lifetime of
$T_{1,\mathrm{opt}}=540$ $\mu$s.

The molecular crystal is composed of a mononuclear Eu3+ complex
[Eu(BA)4](pip), where BA and pip stand for benzoylacetonate and
piperidin-1-ium, respectively (Fig. 1A) [18]. For clarity, it is referred to
as Eu3+ complex hereafter. The complex crystallized in P21/n space group,
belonging to the monoclinic crystal system, with crystal lattice composed of
anionic [Eu(BA)4]- and cationic piperidin-1-ium units as shown in the
supplementary information. The all-oxygen coordination environment around the
Eu3+ center is best described as a biaugmented trigonal prism with the help of
a continuous shape measure calculation (CShM) [19]. The point group symmetry
around the Eu3+ center is assigned to C2v, as inferred from the CShM
calculation and luminescence spectrum depicted in Fig. 1B. All experiments
discussed in the following were performed on crystalline powders with grain
sizes of at least 50 nm. The Eu3+ complex showed high physical and chemical
stabilities over time. Repeated cooling cycles had no noticeable effects on
optical properties, and no photo-degradation was observed neither at low
temperature nor under high laser intensity.

Fig. 1B shows the emission spectrum of the Eu3+ complex where the
characteristic lines of trivalent europium are observed [19]. We focused on
the 7F${}_{0}\rightarrow^{5}$D0 transition at 580.3778 nm (vacuum) since this
transition is associated with narrow linewidths in crystals like Y2SiO5 [20].
Moreover, it enables optical control of ground state nuclear spins, an
important feature for applications in quantum technologies. Transmission
experiments revealed a 7F${}_{0}\rightarrow^{5}$D0 inhomogeneous linewidth
($\Gamma_{\mathrm{inh}}$) of 6.6 GHz, corresponding to 0.007 nm (Fig. 1C).
This low value, together with a Lorentzian absorption profile, is typical of
high crystalline quality samples with low disorder, and comparable to values
obtained in crystals like Eu3+:Y2O3 [9]. Strong absorption was observed in a
500 $\mu$m thick powder as a result of the stoichiometric composition of the
molecular crystal and light scattering inside the powder. Fluorescence decay
experiments led to a lifetime value $T_{1,\mathrm{opt}}$ of 540 $\mu$s for the
5D0 level (Fig. 1D). This sets a limit of only $1/2\pi T_{1,\mathrm{opt}}=295$
Hz on the optical homogeneous linewidth ($\Gamma_{h}$).

Figure 2: Ultra-narrow optical homogeneous linewidths. A. 2-pulse photon echo
(PE, pulse sequence shown in inset) decay for the 7F${}_{0}\rightarrow^{5}$D0
transition. Red line: exponential fit to data giving $T_{2}=10.5\pm 0.2$
$\mu$s or $\Gamma_{h}=1/\pi T_{2}=30.2\pm 0.2$ kHz. B. $\Gamma_{h}$ as a
function of waiting time ($\tau_{W}$) measured by 3-pulse PE. Red line: fit
using a spectral diffusion model yielding a flip rate $R=2.9\pm 0.8$ kHz and a
width $\Gamma_{SD}=154\pm 16$ kHz. C. Temperature dependence of $\Gamma_{h}$
measured by 2-pulse PE (blue dots) and spectral hole burning (black dots). Red
line: fit to a model including contributions from two-level systems (TLS) and
quasi-localized low frequency modes (LFMs). Inset: Zoom on lower temperature
range. D. PE decays from Y3+-diluted complexes showing $T_{2}$ increase with
decreasing Eu3+ concentration. Red line: single (non diluted crystal) and bi-
(diluted crystals) exponential decay fits to data. Inset: 1/e echo amplitude
decay time $T_{2}$ (black dots) and long $T_{2}$ component from bi-exponential
fits (blue dots) as a function of Eu3+ concentration.

The photon echo (PE) technique, similar to Hahn’s spin echo, enables accurate
assessment of narrow homogeneous linewidths[21, 1]. Due to its high
sensitivity, it can be applied to powders [22], allowing us to measure the
optical coherence lifetime, or quantum state lifetime $T_{2}$, of the
5D0$\leftrightarrow$7F0 transition in the Eu3+ complex (Fig. 2A).
$\Gamma_{h}=1/\pi T_{2}$ was found equal to 30.2 $\pm$ 0.2 kHz, remarkably
lower than values reported for single molecules [14], transition metal ions
[23], and a previously reported Eu3+ complex [16], all in the 10s of MHz
range. The Eu3+ linewidth in the complex is indeed comparable to those
measured in some bulk crystals, such as EuP5O14 [24], and in Eu3+:Y2O3
nanoparticles [9]. We further explored line broadening using stimulated photon
echoes (or 3-pulse PE) which allows measuring $\Gamma_{h}$ over the time scale
of the excited state population lifetime $T_{1,\mathrm{opt}}$. We observed an
increase in homogeneous linewidth with increasing waiting time $\tau_{W}$
(Fig. 2B) until about $1$ ms where $\Gamma_{h}$ plateaued at a value of
$\approx 105$ kHz. The $\Gamma_{h}$ evolution has an s-shape, as already
observed in other REI-doped crystals, and was modelled using a sudden-jump
spectral diffusion (SD) model, which could indicate interactions with defects
or impurities carrying electron spins [25]. The limited line broadening over
100s of $\mu$s in the Eu3+ complex is favorable for spectrally resolved
repetitive single ion addressing. Furthermore, lifetime shortening by Purcell
enhancement in an optical micro-cavity by a factor of $\approx 100$, would
enable generation of indistinguishable single photons [26, 11].

Insights into dephasing mechanisms occurring in the complex were also obtained
from the evolution of $\Gamma_{h}$ with temperature $T$, measured by 2-pulse
PE and spectral hole burning (SHB) (Fig. 2C). Two regimes were identified: for
temperatures below 3.5 K, dephasing is dominated by coupling to two-level
systems (TLS) and $\Gamma_{h}$ increases linearly with $T$ (Fig. 2C inset)
[27]; above 3.5 K, the exponential increase of $\Gamma_{h}$ is attributed to
quasi-localized low frequency modes (LFMs) [28]. Data were modeled using the
expression
$\Gamma_{h}(T)=\Gamma_{0}+\Gamma_{\mathrm{TLS}}+\Gamma_{\mathrm{LFM}}$, where
$\Gamma_{\mathrm{TLS}}=\alpha_{\mathrm{TLS}}T$ and
$\Gamma_{LFM}\approx\alpha_{\mathrm{LFM}}\exp(-\Delta
E_{\mathrm{LFM}}/k_{B}T)$, with $k_{B}$ the Boltzmann constant. The best fit
gave a TLS rate $\alpha_{\mathrm{TLS}}=15\pm 5$ kHz K-1, as observed in some
REI-doped crystals [27], and LFM transition energy $\Delta
E_{\mathrm{LFM}}=580$ GHz (19 cm-1), in the range reported for single
molecules [28]. The homogeneous linewidth extrapolated to 0 K ($\Gamma_{0}$)
is estimated at 8 $\pm$ 4 kHz. This remaining dephasing could be due to
Eu3+-Eu3+ interactions[20], as the crystal has a high Eu3+ concentration,
$C_{\mathrm{Eu}}=9.6\times 10^{20}$ ions cm-3. To investigate this effect, an
optically inactive REI, Y3+, was introduced in the crystal to reduce
$C_{\mathrm{Eu}}$. Fig. 2D shows 2-pulse PE decays in a series of diluted
crystals. The non-exponential decays suggest distinct populations or
environments for the Eu3+ ions in these complexes. Increasing coherence
lifetimes with decreasing $C_{\mathrm{Eu}}$ are observed, especially for the
long decay components (Fig. 2 D, inset), confirming a contribution of
Eu3+-Eu3+ interactions to dephasing. At the highest dilution investigated here
(95% that is 5% Eu3+ content), we found a $1/e$ decay time $T_{2}=25$ $\mu$s,
that is $\Gamma_{h}=12.7$ kHz. Remarkably, in this sample, photon echoes could
be detected even after evolution times of 300 $\mu$s, corresponding to a long
decay component of $T_{2}=68\pm 4$ $\mu$s ($\Gamma_{h}=4.6\pm 0.2$ kHz) (Fig.
2D inset). This suggests that synthesis could be optimized to provide a nearly
noise-free environment to all Eu3+ ions in diluted samples.

Figure 3: Optically addressable nuclear spins. A. Spectral hole burning
experimental spectrum of the 151Eu3+ complex (blue) compared to simulation
(red). B. Left - 151Eu3+ ground and excited state nuclear spin splittings.
Right - Scheme of spin initialisation by two-color optical pumping. C. Hole
decay as a function of delay between burn and readout pulses (see Methods in
SI). Red line: double exponential fit yielding spin relaxation times
$T_{1,\mathrm{spin}}$ of $430\pm 100$ ms and $5.0\pm 0.5$ min. D.
Initialisation to a single spin level by two-color optical pumping over a
bandwidth of 3 MHz. Applying the pumping scheme shown in B (right), population
is transferred from $|\pm 3/2_{g}>$ and $|\pm 5/2_{g}>$ levels (deep holes at
$\nu_{1}$ and $\nu_{2}$), to $|\pm 1/2_{g}>$ (increased absorption, or anti-
hole, at $\nu_{3}$). Center wavelength 580.3778 nm, $T=1.45$ K.

Narrow optical linewidths are key to efficiently address REI spins, which
enabled detailed investigations of Eu3+ nuclear spin states in the complex.

First, the nuclear spin structure was determined for the 5D0 ground state and
7F0 excited states by SHB in a complex isotopically enriched in 151Eu3+. At
zero magnetic field, it consists of three doubly-degenerate levels split by
quadrupolar interaction [20], giving rise to a complex SHB spectrum after
optical pumping. Thanks to the narrow optical linewidth, well-resolved
spectral features could be recorded and analyzed (Fig. 3A). This allowed us to
assign ground and excited state splitting energies (Fig. 3B-Left), and
transition branching ratios between nuclear spin levels. The same study was
done in a natural abundance sample, from which, splitting energies and
transition branching ratios were determined for the 153Eu3+ isotope.
Importantly, the obtained branching ratios show the existence of efficient
three-level lambda systems for both isotopes in the Eu3+ complex, an important
requirement for all-optical spin control [29].

We then probed the dynamics of ground state spin populations by monitoring the
spectral hole depth as a function of time delay between burn and readout
pulses (Fig. 3C). Two distinct decay components can be observed with
relaxation times estimated at $430\pm 100$ ms and $5.0\pm 0.5$ min. This shows
that nuclear spin levels can be used as shelving states for at least 100s of
ms. Such long times enable efficient optical manipulation of the spin
population. As an example, we initialised ions into one nuclear spin level
using two-color laser pulses at frequencies $\nu_{1}$ and $\nu_{2}$. This
simultaneously depletes the $|\pm 5/2_{g}>$ and $|\pm 3/2_{g}>$ ground state
spin levels and transfers population into the $|\pm 1/2_{g}>$ (Fig. 3B-Right.
As displayed in Fig. 3D, nearly full transparency could be induced at
$\nu_{1}$ and $\nu_{2}$, which translates to $>95$% spin population into a
single level. This also proves that efficient spectral tailoring is possible
in the Eu3+ complex, an essential feature for many quantum memory and
processing protocols based on REIs[4, 8].

We next used the narrow optical linewidths of Eu3+ molecular crystals to
demonstrate coherent optical storage and controlled ion-ion interactions. In
the first case, we used the atomic frequency comb (AFC) protocol [4] to store
a light pulse in the molecular crystal.

This protocol enables very low output noise and multiplexed storage, important
assets for long distance quantum communications. We first made use of the
efficient optical pumping achieved in the Eu3+ complex to create an AFC
spanning a 6 MHz range, with three 0.9 MHz wide teeth separated by 1.75 MHz
(Fig. 4A). A storage experiment was then performed with a 0.15 $\mu$s long
input pulse overlapping the AFC structure. As shown in Fig. 4B, the output
pulse is observed at a delay $t_{s}=0.57$ $\mu$s after the partially
transmitted input pulse, in perfect agreement with the teeth spacing since
$1/t_{s}=1.75$ MHz [4]. By varying the teeth spacing and adapting the input
pulse length to keep an identical spectral overlap with the comb, output
pulses were observed up to about 1 $\mu$s storage time, clearly confirming the
AFC process (Fig. 4B inset). Storage efficiency, defined as the ratio between
input and output pulses intensities, was 0.86% for a storage time $t_{s}=0.57$
$\mu$s, in agreement with theory. This efficiency could be boosted up to 100%
in an optical cavity [30]. This could be achieved by crystallizing the Eu3+
complex directly on a cavity mirror. Storage times up to several 10s of $\mu$s
could also be obtained by creating narrower teeth [4] with a suitable laser,
given the narrow homogeneous linewidths and limited spectral diffusion in the
Eu3+ complex.

We finally investigated controlled interactions between Eu3+ ions. The scheme
we used is based on the difference in permanent electric dipole moments
between Eu3+ ground (7F0) and excited (5D0) states [31]. This difference
occurs when Eu3+ ions sit in a low symmetry site, which is the case in our
molecular crystal ($C_{2v}$ site symmetry). When a control ion is excited, the
electric field it produces changes, causing a shift in transition frequency
for a nearby target Eu3+ ion through the linear Stark effect. This mechanism
is the basis for 2-qubit gates and qubit readout in some REI-based quantum
computing proposals [8]. However, to be useful, ion-ion interactions must be
significantly larger than the optical homogeneous linewidth, a condition well
matched by our highly-concentrated Eu3+complex with 10 kHz linewidth.

Target and control ions were chosen at different frequencies within the
absorption line (Fig. 1C) to allow for independent excitation and monitoring.
Because of the distribution of distances and orientations and therefore
interaction strengths between Eu3+ ions, the excitation of control ions
results in an additional line broadening $\Gamma_{c}$ for target ions [32].
$\Gamma_{c}$ can be conveniently measured by monitoring the amplitude of a
photon echo produced by target ions while an extra pulse excites the control
ions.

We first investigated the effect of changing the evolution time
($t_{\mathrm{evol}}$) between control pulse and echo, as shown in Fig. 4C. In
this case, the echo amplitude varies as
$\exp(-\pi\Gamma_{c}t_{\mathrm{evol}})$ [32]. A fit to the experimental data
yields $\Gamma_{c}=14.5$ kHz, in qualitative agreement with expected
Eu3+$-$Eu3+ electric dipole interactions and previous experiments in non-
molecular REI-doped crystals [32]. It also provides an upper bound to the ion-
ion interaction contribution in the measurements of $\Gamma_{h}$ by 2-pulse
photon echoes. We further confirmed this analysis by varying the control pulse
intensity $I_{c}$. In the weak excitation regime, $\Gamma_{c}$ is proportional
to the fraction of excited control ions ($p$), with $p\propto I_{c}$. We
indeed observed the predicted exponential decay of the echo amplitude with
increasing $p$, as displayed in Fig. 4D. Finally, the control pulse frequency
was varied over several 10s of MHz with fixed $t_{\mathrm{evol}}$ and $p$. No
significant change in echo amplitude was observed, ruling out direct light-
induced frequency shift of target ions, the so called AC Stark shift (Fig. 4E)
[13]. We therefore conclude that qubit gate and readout schemes based on
electric dipole-dipole interactions could be implemented in the molecular
crystal. Because of the high Eu3+ concentration and narrow linewidth, we
estimate that one ion could control thousands of target ions, a useful
property for scaling up REI-based quantum processors [8].

Figure 4: Coherent light storage and optically controlled ion-ion
interactions. A. Atomic frequency comb (AFC) created by optical pumping within
the inhomogeneously broadened 7F${}_{0}\rightarrow^{5}$D0 line. The 0.9 MHz
wide teeth are separated by 1.75 MHz and span 6 MHz. Blue line: Input pulse
spectrum. Center wavelength 580.373 nm.B. Coherent storage of a 0.15 $\mu$s
long input pulse (blue line) using the AFC structure in A. The output pulse
appears at $0.57\mu$s (solid red line, intensity $\times$ 3) with a storage
efficiency of 0.86% (see text). Part of the input pulse is directly
transmitted and not stored (dashed line at 0 $\mu$s). Inset: variable storage
times $t_{\mathrm{s}}$ obtained by changing AFC teeth frequency separation
$\Delta$. Input pulse lengths were adapted to keep identical spectral overlap
with AFCs. C,D,E. Photon echo amplitude of target ions (at frequency
$\nu_{a}$) as a function of: (C) evolution time $t_{\mathrm{evol}}$ after
excitation of control ions (at $\nu_{b}=\nu_{a}-20$ MHz). Red line:
exponential fit to data giving a broadening of the target ions linewidth by
the control ions of $\Gamma_{c}=14.5$ kHz (see text); (D) control ions
excitation probability (normalized to the maximum value reached
experimentally). Red line: exponential fit; (E) control pulse detuning. All
experiments were performed at 1.45 K.

The Eu3+ complex investigated in this study is a very promising platform for
optical quantum technologies as a robust system with narrow linewidth and
long-lived optically addressable spins. Furthermore, significant decrease in
optical homogeneous linewidth could be obtained by lowering temperature,
tuning the REI concentration, and optimizing synthesis to decrease residual
defects or impurities. In such compounds, interactions with host nuclear spins
like 1H or ${}^{13}C$ could become the dominant dephasing mechanisms, which
can be reduced using specific isotopes with lower or zero magnetic moments
[33]. This could also be useful to obtain spin states with long coherence
lifetimes, a property that remains to be measured in our samples. The huge
possibility in molecular design also opens the way to accurate engineering of
the ligand field acting on europium and more generally other REIs of interest
for quantum technologies, such as Er3+ or Yb3+. This would allow one to
optimize transition strengths and frequencies for optimal coupling to light,
tune electronic and spin level structures, and coupling to molecular
vibrations for long coherence lifetimes. Complexes containing several REIs at
close distance can also be synthesized which would enable high-density
optically addressable qubit architectures, as shown with REI magnetic
molecules in the microwave range [34]. Developments towards applications in
quantum technologies could greatly benefit from integration of molecular
crystals into nanophotonic structures. For example, high-quality and small
mode volume optical cavities can dramatically enhance coupling of REI with
light, enabling efficient emission from nominally weak transitions[35, 10,
11]. This would be facilitated by the broad range of synthesis,
functionalization and deposition methods that are available for molecular
complexes [33, 14], as well as the scalable production of large amounts of
identical molecules. REI molecular crystals could therefore emerge as a highly
versatile platform for highly coherent light-matter-spin quantum interfaces
for developing applications in quantum communications and processing and
fundamental studies in quantum optics.

## References

  * [1] P. Goldner, A. Ferrier, and O. Guillot-Noël, “Rare Earth-Doped Crystals for Quantum Information Processing,” in Handbook on the Physics and Chemistry of Rare Earths (J.-C. G. Bünzli and V. K. Pecharsky, eds.), vol. 46, pp. 1–78, Amsterdam: Elsevier, 2015.
  * [2] D. D. Awschalom, R. Hanson, J. Wrachtrup, and B. B. Zhou, “Quantum technologies with optically interfaced solid-state spins,” Nature Photonics, vol. 12, pp. 516–527, Aug. 2018.
  * [3] M. Zhong, M. P. Hedges, R. L. Ahlefeldt, J. G. Bartholomew, S. E. Beavan, S. M. Wittig, J. J. Longdell, and M. J. Sellars, “Optically addressable nuclear spins in a solid with a six-hour coherence time,” Nature, vol. 517, no. 7533, pp. 177–180, 2015.
  * [4] H. de Riedmatten, M. Afzelius, M. U. Staudt, C. Simon, and N. Gisin, “A solid-state light–matter interface at the single-photon level,” Nature, vol. 456, no. 7223, pp. 773–777, 2008.
  * [5] F. Bussières, C. Clausen, A. Tiranov, B. Korzh, V. B. Verma, S. W. Nam, F. Marsili, A. Ferrier, P. Goldner, H. Herrmann, C. Silberhorn, W. Sohler, M. Afzelius, and N. Gisin, “Quantum teleportation from a telecom-wavelength photon to a solid-state quantum memory,” Nature Photonics, vol. 8, pp. 775–778, 2014.
  * [6] A. Seri, D. Lago-Rivera, A. Lenhard, G. Corrielli, R. Osellame, M. Mazzera, and H. de Riedmatten, “Quantum Storage of Frequency-Multiplexed Heralded Single Photons,” Physical Review Letters, vol. 123, p. 080502, Aug. 2019.
  * [7] J. G. Bartholomew, J. Rochman, T. Xie, J. M. Kindem, A. Ruskuc, I. Craiciu, M. Lei, and A. Faraon, “On-chip coherent microwave-to-optical transduction mediated by ytterbium in YVO4,” Nature Communications, vol. 11, p. 3266, Dec. 2020.
  * [8] A. Kinos, D. Hunger, R. Kolesov, K. Mølmer, H. de Riedmatten, P. Goldner, A. Tallaire, L. Morvan, P. Berger, S. Welinski, K. Karrai, L. Rippe, S. Kröll, and A. Walther, “Roadmap for Rare-earth Quantum Computing,” arXiv:2103.15743 [quant-ph], Mar. 2021.
  * [9] T. Zhong and P. Goldner, “Emerging rare-earth doped material platforms for quantum nanophotonics,” Nanophotonics, vol. 8, pp. 2003–2015, Nov. 2019\.
  * [10] S. Chen, M. Raha, C. M. Phenicie, S. Ourari, and J. D. Thompson, “Parallel single-shot measurement and coherent control of solid-state spins below the diffraction limit,” Science, vol. 370, pp. 592–595, Oct. 2020.
  * [11] B. Casabone, C. Deshmukh, S. Liu, D. Serrano, A. Ferrier, T. Hümmer, P. Goldner, D. Hunger, and H. de Riedmatten, “Dynamic control of Purcell enhanced emission of erbium ions in nanoparticles,” arXiv:2001.08532, vol. quant-ph, Jan. 2020.
  * [12] T. Zhong, J. M. Kindem, J. G. Bartholomew, J. Rochman, I. Craiciu, V. Verma, S. W. Nam, F. Marsili, M. D. Shaw, A. D. Beyer, and A. Faraon, “Optically Addressing Single Rare-Earth Ions in a Nanophotonic Cavity,” Physical Review Letters, vol. 121, p. 183603, Oct. 2018.
  * [13] T. Zhong, J. M. Kindem, J. G. Bartholomew, J. Rochman, I. Craiciu, E. Miyazono, M. Bettinelli, E. Cavalli, V. Verma, S. W. Nam, F. Marsili, M. D. Shaw, A. D. Beyer, and A. Faraon, “Nanophotonic rare-earth quantum memory with optically controlled retrieval,” Science, vol. 357, pp. 1392–1395, Sept. 2017.
  * [14] C. Toninelli, I. Gerhardt, A. S. Clark, A. Reserbat-Plantey, S. Götzinger, Z. Ristanovic, M. Colautti, P. Lombardi, K. D. Major, I. Deperasińska, W. H. Pernice, F. H. L. Koppens, B. Kozankiewicz, A. Gourdon, V. Sandoghdar, and M. Orrit, “Single organic molecules for photonic quantum technologies,” arXiv:2011.05059 [quant-ph], Nov. 2020.
  * [15] S. L. Bayliss, D. W. Laorenza, P. J. Mintun, B. D. Kovos, D. E. Freedman, and D. D. Awschalom, “Optically addressable molecular spins for quantum information processing,” Science, vol. 370, pp. 1309–1312, Dec. 2020.
  * [16] K. S. Kumar, D. Serrano, A. M. Nonat, B. Heinrich, L. Karmazin, L. J. Charbonnière, P. Goldner, and M. Ruben, “Optical spin-state polarization in a binuclear europium complex towards molecule-based coherent light-spin interfaces,” Nature Communications, vol. 12, p. 2152, Dec. 2021.
  * [17] J. Zirkelbach, B. Gmeiner, J. Renger, P. Türschmann, T. Utikal, S. Götzinger, and V. Sandoghdar, “Partial Cloaking of a Gold Particle by a Single Molecule,” Physical Review Letters, vol. 125, p. 103603, Sept. 2020.
  * [18] L. R. Melby, N. J. Rose, E. Abramson, and J. C. Caris, “Synthesis and Fluorescence of Some Trivalent Lanthanide Complexes,” Journal of the American Chemical Society, vol. 86, pp. 5117–5125, Dec. 1964.
  * [19] K. Binnemans, “Interpretation of europium (III) spectra,” Coordination Chemistry Reviews, vol. 295, pp. 1–45, 2015.
  * [20] F. Könz, Y. Sun, C. W. Thiel, R. L. Cone, R. Equall, R. Hutcheson, and R. M. Macfarlane, “Temperature and concentration dependence of optical dephasing, spectral-hole lifetime, and anisotropic absorption in Eu3+:Y2SiO5,” Physical Review B, vol. 68, no. 8, p. 085109, 2003.
  * [21] I. D. Abella, N. A. Kurnit, and S. R. Hartmann, “Photon echoes,” Physical Review, vol. 141, no. 1, p. 391, 1966.
  * [22] A. Perrot, P. Goldner, D. Giaume, M. Lovrić, C. Andriamiadamanana, R. R. Gonçalves, and A. Ferrier, “Narrow Optical Homogeneous Linewidths in Rare Earth Doped Nanocrystals,” Physical Review Letters, vol. 111, no. 20, p. 203601, 2013.
  * [23] H. Riesen, “Hole-burning spectroscopy of coordination compounds,” Coordination Chemistry Reviews, vol. 250, pp. 1737–1754, July 2006.
  * [24] R. Shelby and R. M. Macfarlane, “Frequency-Dependent Optical Dephasing in the Stoichiometric Material EuP_{5}O_{14},” Physical Review Letters, vol. 45, pp. 1098–1101, Sept. 1980.
  * [25] T. Böttger, C. W. Thiel, Y. Sun, and R. L. Cone, “Optical decoherence and spectral diffusion at 1.5 $\mu$m in Er3+:Y2SiO5 versus magnetic field, temperature, and Er3+ concentration,” Physical Review B, vol. 73, no. 7, p. 075101, 2006.
  * [26] B. Merkel, A. Ulanowski, and A. Reiserer, “Coherent and Purcell-Enhanced Emission from Erbium Dopants in a Cryogenic High- Q Resonator,” Physical Review X, vol. 10, p. 041025, Nov. 2020.
  * [27] G. P. Flinn, K. W. Jang, J. Ganem, M. L. Jones, R. S. Meltzer, and R. M. Macfarlane, “Sample-dependent optical dephasing in bulk crystalline samples of Y2O3:Eu3+,” Physical Review B, vol. 49, no. 9, p. 5821, 1994.
  * [28] B. Kozankiewicz and M. Orrit, “Single-molecule photophysics, from cryogenic to ambient conditions,” Chem. Soc. Rev., vol. 43, no. 4, pp. 1029–1043, 2014\.
  * [29] D. Serrano, J. Karlsson, A. Fossati, A. Ferrier, and P. Goldner, “All-optical control of long-lived nuclear spins in rare-earth doped nanoparticles,” Nature Communications, vol. 9, p. 2127, May 2018.
  * [30] M. Afzelius and C. Simon, “Impedance-matched cavity quantum memory,” Physical Review A, vol. 82, no. 2, p. 022310, 2010.
  * [31] R. M. Macfarlane, “Optical Stark spectroscopy of solids,” Journal of Luminescence, vol. 125, no. 1-2, pp. 156–174, 2007.
  * [32] S. B. Altner, M. Mitsunaga, G. Zumofen, and U. P. Wild, “Dephasing-Rephasing Balancing in Photon Echoes by Excitation Induced Frequency Shifts,” Physical Review Letters, vol. 76, pp. 1747–1750, Mar. 1996\.
  * [33] W. Wernsdorfer and M. Ruben, “Synthetic Hilbert Space Engineering of Molecular Qudits: Isotopologue Chemistry,” Advanced Materials, vol. 31, p. 1806687, June 2019.
  * [34] C. Godfrin, A. Ferhat, R. Ballou, S. Klyatskaya, M. Ruben, W. Wernsdorfer, and F. Balestro, “Operating Quantum States in Single Magnetic Molecules: Implementation of Grover’s Quantum Algorithm,” Physical Review Letters, vol. 119, p. 187702, Nov. 2017.
  * [35] J. M. Kindem, A. Ruskuc, J. G. Bartholomew, J. Rochman, Y. Q. Huan, and A. Faraon, “Control and single-shot readout of an ion embedded in a nanophotonic cavity,” Nature, vol. 580, pp. 1–12, Mar. 2020.

## Acknowledgments

We thank Mikael Afzelius for useful discussions. This project has received
funding from the European Union?s Horizon 2020 research and innovation
programme under grant agreements No 820391 (SQUARE) and the ANR UltraNanoSpec
projects, grant ANR-20-CE09-0022 of the French Agence Nationale de la
Recherche.

## Authors contributions

P. G., M. R. and D. H. conceived and supervised the project. D. S. and K. S.
K. were involved in the conceptual development of the project. K.S.K. and M.R.
were responsible for the synthesis and characterisation of the isotopologue
complexes. B. H. performed powder X-ray diffraction studies and indexed the
patterns. O. F. solved the X-ray structure of the complex. D. S. and P. G.
performed the optical experiments and analyzed the results. D. S. and P. G.
wrote the manuscript with inputs form all authors.


# Evaluating Fairness of Machine Learning Models Under Uncertain and
Incomplete Information

Pranjal Awasthi
Google & Rutgers University
<EMAIL_ADDRESS>Alex Beutel
Google
<EMAIL_ADDRESS>Matthäus Kleindessner
Amazon
<EMAIL_ADDRESS>Work done while being a postdoc at the University of
Washington. Jamie Morgenstern
University of Washington & Google
<EMAIL_ADDRESS>Xuezhi Wang
Google
<EMAIL_ADDRESS>
###### Abstract

Training and evaluation of fair classifiers is a challenging problem. This is
partly due to the fact that most fairness metrics of interest depend on both
the sensitive attribute information and label information of the data points.
In many scenarios it is not possible to collect large datasets with such
information. An alternate approach that is commonly used is to separately
train an attribute classifier on data with sensitive attribute information,
and then use it later in the ML pipeline to evaluate the bias of a given
classifier. While such decoupling helps alleviate the problem of demographic
scarcity, it raises several natural questions such as: how should the
attribute classifier be trained?, and how should one use a given attribute
classifier for accurate bias estimation? In this work we study this question
from both theoretical and empirical perspectives.

We first experimentally demonstrate that the test accuracy of the attribute
classifier is not always correlated with its effectiveness in bias estimation
for a downstream model. In order to further investigate this phenomenon, we
analyze an idealized theoretical model and characterize the structure of the
optimal classifier. Our analysis has surprising and counter-intuitive
implications where in certain regimes one might want to distribute the error
of the attribute classifier as unevenly as possible among the different
subgroups. Based on our analysis we develop heuristics for both training and
using attribute classifiers for bias estimation in the data scarce regime. We
empirically demonstrate the effectiveness of our approach on real and
simulated data.

##  1 Introduction

Estimating a machine learning (ML) model’s difference in accuracy for
different demographic groups is a challenging task in many applications, in
large part due to imperfect or missing demographic data Holstein et al.
(2019). Demographic information might be unavailable for many reasons: users
may choose to withhold this information (for privacy or other personal
preferences), or the dataset may have been constructed for use in a setting
where collecting the demographic information of the dataset’s subjects was
unnecessary, undesirable, or even illegal Zhang (2018); Weissman and Hasnain-
Wynia (2011); Fremont et al. (2016).

Responsible ML practitioners and auditors may want to evaluate model
performance across different demographic groups even if demographic
information was not collected explicitly, and as researchers of fairness we
want to enable this. For example, a microlender who builds a model to
prescreen applicants for a loan may explicitly avoid maintaining demographic
records on applicants, but may also want to ensure that the rate at which
their model approves a candidate is nearly independent of the applicant’s
gender. Can one assess this bias of the model, even when training and
validation data do not contain explicit gender information?

This presents a common problem: how can one audit the performance of a model
for predicting $Y$, _conditioned on demographic information $A$_, when $A$ and
$Y$ are observed jointly on little or no data? More formally, consider two
datasets $D_{1},D_{2}$, where $D_{1}$ has features in $X$ and labels in $Y$,
and $D_{2}$ has features in $X$ and demographic information in $A$. How should
we use these datasets to evaluate a model $f$’s performance predicting $Y$
conditioned on $A$, for the distribution that generated $D_{1}$? With no
further assumptions, this is impossible: if the two datasets are generated
from distributions bearing no resemblance to each other, correlations existing
between $X$ and $Y$ (and between $X$ and $A$) may be arbitrarily different for
the two distributions. Modelers may still wish to understand if their separate
datasets can help them with this estimation problem, and what properties their
two datasets might need to have to result in good estimations.

One approach, particularly natural for enabling many different teams
participating in the development of models without demographic information, is
to use proxy attributes as a replacement for the true sensitive attribute. The
use of such proxy attributes has been widely used in domains such as health
care Brown et al. (2016); Fremont et al. (2005) and finance Bureau (2014). One
can view a particular proxy attribute as a coarse attribute classifier that
predicts the sensitive attribute information for a given example. For popular
fairness metrics such as equalized odds or demographic parity Calders et al.
(2009); Zliobaite (2015); Hardt et al. (2016); Zafar et al. (2017), the
sensitive attribute information obtained from the classifier can then be used
in conjunction with the predicted label information to get an estimate of the
bias of a given model. The advantage of this approach is that it decouples the
data requirement, and in particular, the attribute classifier can be trained
on a separate dataset without any label information present. On the other
hand, such an approach may produce very poor estimates, depending upon how the
sources of data relate to one another.

Nonetheless, it is interesting to ask what principles should guide the choice
of a proxy attribute, or more generally the design of a sensitive attribute
classifier, and similarly, what principles should be followed when using such
classifiers for bias estimation. In this work, we aim to understand this
question. If one wishes to produce the most accurate estimate of the bias
term, is the optimal approach to train the attribute classifier to have the
highest possible $0/1$ accuracy, or to have similar error rates for each
demographic group? It turns out that neither of these criteria alone captures
the structure of the optimal attribute classifier.

To demonstrate this, we consider the measurement of violation of equal
opportunity, or true positive rates for different groups Hardt et al. (2016),
and show that the error in the bias estimates, as a result of using a proxy
attribute/attribute classifier depends not only on the error rate of the
classifiers but also on how these errors (and the data more generally) are
distributed. Our analysis has surprising and counter-intuitive implications –
in certain regimes the optimal attribute classifier is the one that has the
most unequal distribution of errors across the two subgroups! Our main
contributions are summarized below.

  * •

Problem formulation: We formalize and study the problem of estimating the bias
of a given machine learning model using data with only label information and
model output, and using a separate attribute classifier to predict the
sensitive attributes. We call this the demographically scarce regime. In
particular, our setting captures the common practice of using proxy attributes
as a replacement for the true sensitive attribute. We experimentally
demonstrate that the accuracy of the attribute classifier does not solely
capture its effectiveness in bias estimation.

  * •

Theoretical analysis: For the case of the equal opportunity metric Hardt et
al. (2016), we present a theoretical analysis under a simplified model. Our
analysis completely characterizes the structure of the optimal attribute
classifier and shows that the error in the bias estimates depends on the error
rate of the classifier as well as the base error rate, a property of the data
distribution. As a result, we show that in certain regimes of the base error
rate, the optimal attribute classifier, surprisingly, is the one that has the
most unequal distribution of errors among the two subgroups.

  * •

Empirical validation: Our theory predicts natural interventions, aimed at
better bias estimation, that can be performed either at the stage of designing
the attribute classifier or at the stage of using a given attribute
classifier. We study their effectiveness in scenarios where our modeling
assumptions hold and their sensitivity to violations of the assumptions.

  * •

An active sampling algorithm: Finally, we propose an active sampling based
algorithm for accurately estimating the bias of a model given access to an
attribute classifier for predicting the sensitive attribute. Our approach
makes no assumption about the structure of the attribute classifier or the
data distribution. We demonstrate via experiments on real data that our
sampling scheme performs accurate bias estimation using significantly fewer
samples in the demographically scarce regime, as compared to other approaches.

While highlighting the need for careful considerations when designing such
attribute classifiers, our analysis provides concrete recommendations and
algorithms that can be used by ML practitioners.

######  Remark 1.

Inferring demographic information should be done with care, even when used
only for auditing a model’s disparate treatment. Any estimation of
demographics will invariably have inaccuracies. This can be particularly
problematic when considering, for example, gender, as misgendering an
individual can cause them substantial harm. Furthermore, building a model to
infer demographic information purely for internal evaluation leaves open the
possibility that the model may ultimately be used more broadly, with possibly
unintended consequences.

That said, preliminary evidence of bias may be invaluable in arguing for
resources to do a more careful evaluation of a machine learning system. For
this reason, we believe that methods to estimate the difference in predictive
performance across demographic groups can serve as a useful first step in
understanding and improving the system’s treatment of underserved populations.

##  2 Related Work

Various fairness metrics of interest have been proposed for classification
Hardt et al. (2016); Dwork et al. (2012); Pleiss et al. (2017); Kleinberg et
al. (2017), ranking Celis et al. (2018); Beutel et al. (2019), unsupervised
learning Chierichetti et al. (2017); Samadi et al. (2018); Kleindessner et al.
(2019), and online learning Joseph et al. (2016); Jabbari et al. (2017);
Gillen et al. (2018); Blum et al. (2018). These notions of fairness are
usually categorized as either group fairness or individual fairness. In the
case of group fairness, training a model to satisfy such fairness metrics and
evaluating the metrics on a pre-trained model typically requires access to
both the sensitive attribute and the label information on the same dataset.
Only recently, ML research has explored the implications of using proxy
attributes and the sensitivity of fair machine learning algorithms to this
noisy demographic data Gupta et al. (2018); Lamy et al. (2019); Awasthi et al.
(2020); Coston et al. (2019); Schumann et al. (2019).

The most related work to ours Chen et al. (2019); Kallus et al. (2020) also
study the problem of estimating the bias of predictor $f$ of $Y$ from $X$ as a
function of $A$ with few or no samples from the joint distribution over
$(X,Y,A)$. In Chen et al. (2019) the authors aim to estimate the disparity of
a model $f$ predicting $Y$ from $X$, along $A$ by considering predicting $A$
from $X$ via a threshold $q$, and then assuming $A=a$ whenever $P[A=a|X=x]>q$.
This can work well with unlimited data from the joint distribution over $A,X$,
but can both overestimate and underestimate the bias because of the
misclassification of $A$ using said thresholding rules.

The work of Kallus et al. (2020) investigates how to perfectly or partially
identify the same bias parameter, making few or no assumptions about
independence between $A,Y,f$ and $X$. Given that exact identification is
usually impossible, the authors describe how to find feasible regions of
various disparity measures making very few assumptions about independence
between $f,Y,X,A$. Similar to our work, the authors in Kallus et al. (2020)
study the setting where one has access to a dataset involving $(y,x)$ and
another dataset involving $(a,x)$. Given that exact identification is usually
impossible, they construct an uncertainty set (confidence interval) for bias
estimates assuming access to the Bayes optimal classifier, i.e., the
classifier that predicts sensitive attribute according to $P(a|x)$. An
important contribution of our paper is to show that the Bayes optimal
attribute classifier is not the right classifier in the first place. We
demonstrate this via experiments in Table 1, Theorem 1, and in fact we go
deeper and characterize the structure of the optimal attribute classifier in
Theorem 2 (under assumptions).

Our work also explains why the confidence intervals in the experiments of
Kallus et al. (2020) are large. In particular, the work of Kallus et al.
(2020) focuses only on the setting where there is no common data, hence their
confidence regions will never shrink with dataset size due to inherent
uncertainty. We however believe that it is practically more relevant to study
how we can use a little amount of common data and produce accurate estimates.
This motivates our active sampling approach as proposed in Section 5.1.

##  3 Setup and Notation

We consider the classification setting where $\mathcal{X}$ denotes the feature
space, $\mathcal{Y}$ the label space and $\mathcal{A}$ the sensitive attribute
space. For simplicity, we assume $\mathcal{Y}=\\{-1,+1\\}$ and
$\mathcal{A}=\\{0,1\\}$. Consider two datasets $D_{1}$ and $D_{2}$. $D_{1}$ is
drawn from the marginal over $(\mathcal{X},\mathcal{A})$, of a distribution
$P$ over $\mathcal{X}\times\mathcal{Y}\times\mathcal{A}$. Similarly, $D_{2}$
is drawn from the marginal over $(\mathcal{X},\mathcal{Y})$, of a distribution
$Q$ over $\mathcal{X}\times\mathcal{Y}\times\mathcal{A}$. Thus, both datasets
contain the same collection of features, $D_{1}$ contains attribute
information, and $D_{2}$ contains label information. In this setting, given a
classifier $f:\mathcal{X}\rightarrow\mathcal{Y}$, we aim to estimate the bias
of $f$: the difference in the performance of $f$ on $Q$ over $A$. In this work
we define the bias to be the equal opportunity metric Hardt et al. (2016)
defined as

$\displaystyle bias_{Q}(f)$ $\displaystyle=|\alpha-\beta|,$ (1)

where

$\displaystyle\alpha=\mathbb{P}_{(x,a,y)\sim Q}\big{(}f(x)=1|y=1,a=1\big{)},$
(2) $\displaystyle\beta=\mathbb{P}_{(x,a,y)\sim
Q}\big{(}f(x)=1|y=1,a=0\big{)}.$ (3)

We consider the demographically scarce regime where the designer of an
attribute classifier has access to $D_{1}$ and the user of the label
classifier has access to $D_{2}$ and additionally has access to the attribute
classifier $h:\mathcal{X}\rightarrow\mathcal{A}$ trained on $D_{1}$. Here, no
party has access to both datasets. We aim to understand how the classifiers
$(h,f)$ can be used in combination for accurate bias estimation.

From the perspective of the user of an attribute classifier, it is easy to see
that no matter what the attribute classifier is, one cannot get any non-
trivial estimate of the bias of $f$ without access to some common data drawn
from $\mathcal{X}\times\mathcal{Y}\times\mathcal{A}$. Here we provide a simple
proof of this fact. In particular, we will construct a scenario where there is
a fixed attribute classifier $h:\mathcal{X}\to\mathcal{A}$. We will construct
two distributions $Q_{1},Q_{2}$ such that the output distribution of the
attribute classifier is the same in both the cases. Furthermore, any label
classifier trained on just $(x,y)$ pairs will have the same output
distribution in both the cases. However, the estimates of the bias when using
the attribute classifier will differ wildly. Formally, we have the following
proposition.

######  Proposition 1.

Consider a fixed attribute classifier $h:\mathcal{X}\to\mathcal{A}$ and a
fixed learning algorithm ALG for computing a label classifier from a
distribution over $\mathcal{X}\times\mathcal{Y}$. Then, there exists two
distribution $Q_{1},Q_{2}$ over
$\mathcal{X}\times\mathcal{Y}\times\mathcal{A}$ such that: a) $Q_{1},Q_{2}$
have the same marginals over $\mathcal{X}\times\mathcal{A}$, b) ALG produces
the same label classifier $f$ given access to $Q_{1}$ or $Q_{2}$, and c)
either the label classifier $f$ is the Bayes optimal classifier, or the ratio
of the estimated bias (using $h$) to the true bias of $f$ on either $Q_{1}$ or
$Q_{2}$ is $0$ or $\infty$.

###### Proof.

Given the learning algorithm ALG for the labels and an attribute classifier
$h$, we will construct two distributions $Q_{1}$ and $Q_{2}$ over
$\mathcal{X}\times\mathcal{Y}\times\mathcal{A}$ such that the following holds:

  * •

$Q_{1}(\mathcal{X})$ is the same as ${Q_{2}}(\mathcal{X})$, thereby ensuring
that the distribution of $h(x)$ over $Q_{1},Q_{2}$ is the same.

  * •

${Q_{1}}(\mathcal{X}\times\mathcal{Y})$ is the same as
${Q_{2}}(\mathcal{X}\times\mathcal{Y})$, thereby ensuring that ALG produces
the same classifier $f$.

  * •

On $Q_{1}$ the true bias of $f$ is zero and on $Q_{2}$ the true bias of $f$ is
one, thereby ensuring that the ratio of the estimated will be distorted by
either zero or $\infty$.

To construct the two distributions fix any marginal distribution over
$\mathcal{X}\times\mathcal{Y}$ and let $f$ be any classifier for predicting
$y$ given $x$ that is not Bayes optimal. Since $f$ is not Bayes optimal, we
can consider two non-empty regions $A=\\{f=1,Y=1\\}$ and $B=\\{f=0,Y=1\\}$.
Construct $Q_{1}$ by setting the conditional distribution (conditioned on $A$)
of $\mathcal{A}$ to be uniformly distributed and similarly the distribution of
$\mathcal{A}$ conditioned on $B$ to be uniformly distributed. Construct
$Q_{2}$ to be such that the conditional distribution of $\mathcal{A}$ on $A$
is entirely supported on $a=1$ and the conditional distribution of
$\mathcal{A}$ on $B$ is entirely supported on $a=0$. Now it is easy to see
that $f$ has zero bias on $Q_{1}$ and a bias value of one on $Q_{2}$. Since
the estimated bias using $h$ will result in the same value for $Q_{1}$ and
$Q_{2}$, in at least one of the cases the distortion must be $0$ or $\infty$.
∎

In the next two sections we study the following questions: a) how should one
design an attribute classifier?, and b) how can one use an attribute
classifier along with minimal common data and perform accurate bias
estimation? We will focus on the case of $P=Q$, i.e., both the designer and
the user of an attribute classifier have marginals from the same joint
distribution.

##  4 Perspective of the Attribute Classifier Modeler

What properties of the attribute classifier are desirable for bias estimation?
At first thought, training the most accurate classifier seems to be a
reasonable strategy. However, it is easy to construct instances where using
the Bayes optimal attribute classifier does not lead to the most accurate bias
estimation. This is formalized in the Theorem below. See Appendix for the
proof.

######  Theorem 1.

Let $x_{1},x_{2}$ be binary attributes, $a$ be a binary sensitive attribute
and $y$ be a binary class label. Furthermore, let $f$ be a label classifier
given by $x_{2}$, i.e., $f(x_{1},x_{2},a)=x_{2}$. Then there exists a joint
distribution $Q$ over $(x_{1},x_{2},a,y)$ tuples such that the bias of $f$ is
zero, i.e., $bias_{Q}(f)=0$. On the other hand, using the Bayes optimal
predictor for the attribute $a$, leads to an estimated bias of one for $f$.

Next, we show that even in practical settings, there is little correlation
between the accuracy of the attribute classifier and its effectiveness for
bias estimation. Table 1 contains the result of various attribute classifiers
trained on the UCI Adult dataset Dua and Graff (2017). As can be seen, the
accuracy of an attribute classifier is not necessarily correlated with its
ability to estimate the true bias of a model.

Attribute Classifier | Test Accuracy | $\hat{\alpha}-\hat{\beta}$ | $\alpha-\beta$
---|---|---|---
Random Forest | 84.46% | -0.1243 | -0.1149
Logistic Regression (LR) | 84.29% | -0.1450 | -0.1149
LR (M+O+R) | 82.68% | -0.1200 | -0.1149
LR (W+M+O+R) | 83.43% | -0.1454 | -0.1149
LR (W+E+M+O+R) | 83.43% | -0.1352 | -0.1149
SVM | 83.80% | -0.2045 | -0.1149
1-hidden-layer NN | 83.35% | -0.1025 | -0.1149
Table 1: Distribution of test accuracies of different attribute (Gender)
classifiers, and the resulting estimated biases, over the UCI Adult dataset.
$\hat{\alpha}-\hat{\beta}$ is the estimated bias using the attribute
classifier and $\alpha-\beta$ is the true bias (without the absolute value).
The label classifier is a fixed Random Forest Classifier to predict income,
with $85.79\%$ test accuracy. By default all models are trained with all
features except Gender and Income. For the Logistic Regression (LR) model, the
names within the bracket indicate which features are used: R: “Relationship”,
E: “Education", M: “MaritalStatus", O: “Occupation", W: “WorkClass".

In order to gain further understanding, we consider a simplified model where
we aim to theoretically characterize the structure of the optimal attribute
classifier. In particular, we will consider the setting where the two datasets
$D_{1}$ and $D_{2}$ are drawn from distributions which are marginals of the
same distribution. For an attribute classifier
$h:\mathcal{X}\rightarrow\mathcal{A}$, define the conditional errors of $h$
with respect to $a$ as

$\displaystyle g_{1}$ $\displaystyle=\mathbb{P}(h(x)\neq a|a=0,y=1),$ (4)
$\displaystyle g_{2}$ $\displaystyle=\mathbb{P}(h(x)\neq a|a=1,y=1).$ (5)

Here $(x,a)$ is drawn from the marginal of joint distribution over
$\mathcal{X}\times\mathcal{Y}\times\mathcal{A}$ from which both $D_{1}$ and
$D_{2}$ are drawn. Suppose we use $h$ to predict the noisy attributes
$\hat{a}$ on $D_{2}$, and then use these estimates to measure the bias of a
label classifier $f$. To simplify our analysis we make the following key
assumption. Below we denote $\hat{y}$ to represent the prediction of the label
classifier $f$.

Assumption I: Given $y$ and $a$, $\hat{y}$ and $\hat{a}$ are conditionally
independent, that is for all $y_{1},y_{2}\in\\{-1,+1\\}$ and
$a_{1},a_{2}\in\\{0,1\\}$, we have

$\displaystyle\mathbb{P}(\hat{y}=y_{1},\hat{a}=a_{1}|y=y_{2},a=a_{2})$
$\displaystyle=\mathbb{P}(\hat{y}=y_{1}|y=y_{2},a=a_{2})\cdot\mathbb{P}(\hat{a}=a_{1}|y=y_{2},a=a_{2}).$
(6)

Notice that while the above assumption is restrictive, there are practical
scenarios where one can expect it to hold. Furthermore, the assumption has
been studied in prior works to understand noise sensitivity of post-processing
and in-processing methods for building fair classifiers Lamy et al. (2019);
Awasthi et al. (2020). Two settings where such an assumption would hold are as
follows. First, this would hold if the attribute classifier uses a set of
features that are conditionally independent of the features used by the label
classifier. The assumption will also hold if the attribute classifier makes
independent errors with a certain probability. This, for instance, might be
the case for certain classifiers based upon crowdsourcing. As we will soon
see, even under the above simplified setting, the structure of the optimal
attribute classifier can defy convention wisdom. Using the attribute
classifier $h$, we get estimates $\hat{\alpha},\hat{\beta}$ of the true values
$\alpha,\beta$ (see Eq. (2)), where

$\displaystyle\hat{\alpha}$ $\displaystyle=\mathbb{P}(f(x)=1|y=1,\hat{a}=1),$
$\displaystyle\hat{\beta}$ $\displaystyle=\mathbb{P}(f(x)=1|y=1,\hat{a}=0).$

Under Assumption I, we have the following relationship between the true and
the estimated values

$\displaystyle\begin{split}\hat{\alpha}&=\frac{\alpha\mathbb{P}(y=1,a=1)(1-g_{2})+\beta\mathbb{P}(y=1,a=0)g_{1}}{\mathbb{P}(y=1,a=1)(1-g_{2})+\mathbb{P}(y=1,a=0)g_{1}},\\\
\hat{\beta}&=\frac{\alpha\mathbb{P}(y=1,a=1)g_{2}+\beta\mathbb{P}(y=1,a=0)(1-g_{1})}{\mathbb{P}(y=1,a=1)g_{2}+\mathbb{P}(y=1,a=0)(1-g_{1})}.\end{split}$
(7)

To see the above we have

$\displaystyle\mathbb{P}(f(x)=1|y=1,\hat{a}=1)$
$\displaystyle=\frac{A+B}{C+D},$

where

$\displaystyle A$
$\displaystyle=\mathbb{P}(f(x)=1|y=1,a=1,\hat{a}=1)\mathbb{P}(\hat{a}=1|y=1,a=1)\mathbb{P}(y=1,a=1),$
$\displaystyle B$
$\displaystyle=\mathbb{P}(f(x)=1|y=1,a=0,\hat{a}=1)\mathbb{P}(\hat{a}=1|y=1,a=0)\mathbb{P}(y=1,a=0),$
$\displaystyle C$
$\displaystyle=\mathbb{P}(\hat{a}=1|y=1,a=1)\mathbb{P}(y=1,a=1),$
$\displaystyle D$
$\displaystyle=\mathbb{P}(\hat{a}=1|y=1,a=0)\mathbb{P}(y=1,a=0).$

The above can be rewritten as

$\displaystyle\mathbb{P}(f(x)=1|y=1,\hat{a}=1)$
$\displaystyle=\frac{(1-g_{2})\mathbb{P}(f(x)=1|y=1,a=1,\hat{a}=1)\mathbb{P}(y=1,a=1)}{(1-g_{2})\mathbb{P}(y=1,a=1)+g_{1}\mathbb{P}(y=1,a=0)}$
$\displaystyle+\;\;\;\;\frac{g_{1}\mathbb{P}(f(x)=1|y=1,a=0,\hat{a}=1)\mathbb{P}(y=1,a=0)}{(1-g_{2})\mathbb{P}(y=1,a=1)+g_{1}\mathbb{P}(y=1,a=0)},$

with $g_{1},g_{2}$ defined as in (4).

Under Assumption I we have

$\mathbb{P}(f(x)=1|y=1,a=1,\hat{a}=1)=\alpha$

and

$\mathbb{P}(f(x)=1|y=1,a=0,\hat{a}=1)=\beta,$

and hence

$\displaystyle\mathbb{P}(f(x)=1|y=1,\hat{a}=1)$
$\displaystyle=\frac{(1-g_{2})\alpha\mathbb{P}(y=1,a=1)+g_{1}\beta\mathbb{P}(y=1,a=0)}{(1-g_{2})\mathbb{P}(y=1,a=1)+g_{1}\mathbb{P}(y=1,a=0)}.$

Similarly, we obtain

$\displaystyle\mathbb{P}(f(x)=1|y=1,\hat{a}=0)$
$\displaystyle=\frac{g_{2}\alpha\mathbb{P}(y=1,a=1)+(1-g_{1})\beta\mathbb{P}(y=1,a=0)}{g_{2}\mathbb{P}(y=1,a=1)+(1-g_{1})\mathbb{P}(y=1,a=0)}.$

It follows that

$\displaystyle|\hat{\alpha}-\hat{\beta}|$
$\displaystyle=|\mathbb{P}(f(x)=1|y=1,\hat{a}=1)-\mathbb{P}(f(x)=1|y=1,\hat{a}=0)|$
$\displaystyle=\frac{|1-g_{1}-g_{2}|}{\big{(}\frac{s}{r}(1-g_{1})+g_{2}\big{)}\big{(}\frac{r}{s}(1-g_{2})+g_{1}\big{)}}\cdot|\alpha-\beta|,$

where

$\displaystyle r=\mathbb{P}(y=1,a=1),\qquad s=\mathbb{P}(y=1,a=0).$

A simple calculation then shows that the true bias and the estimated bias
satisfy

$\displaystyle|\hat{\alpha}-\hat{\beta}|$
$\displaystyle=\gamma|\alpha-\beta|,$ (8)

where the distortion factor $\gamma$ is defined as

$\displaystyle\gamma=\frac{|1-g_{1}-g_{2}|}{\big{(}\frac{s}{r}(1-g_{1})+g_{2}\big{)}\big{(}\frac{r}{s}(1-g_{2})+g_{1}\big{)}}$
(9)

with larger values of $\gamma$ corresponding to higher accuracy estimates of
bias, and the quantities $r,s$ are defined as

$\displaystyle r=\mathbb{P}(y=1,a=1),\qquad s=\mathbb{P}(y=1,a=0).$

We refer to $r/s$ as the ratio of base rates and assume that it is bounded in
$(0,G)$ for some finite $G$, else there will be no good way to estimate the
bias from a finite sample. Notice that if $g_{1}+g_{2}$ equals one, then
$\gamma$ is zero. In every other case it is not hard to see that
$\gamma\in[0,1]$.

######  Remark 2.

Under Assumption I, $|\hat{\alpha}-\hat{\beta}|$ is an _underestimate_ of the
bias of $f$, and is therefore not an unbiased estimator. This is evident from
our derivation, but may not be obvious for someone using empirical value as a
stand-in for the true value of bias.

Hence, even in the simplified setting of Assumption I, the distortion in the
estimated bias depends on the conditional errors of $h$, as well as the ratio
of base rates $r/s$. Therefore, to accurately estimate the true bias one not
only needs the conditional errors of $h$ but also an estimate of the ratio of
base rates. Under Assumption I an optimal attribute classifier should aim to
maximize $\gamma$ as defined in (9) (since $\gamma\in[0,1]$). Our next theorem
quantifies the structure of the optimal attribute classifier.

######  Theorem 2.

Assume that the distribution $P$ is such that the ratio of base rates equals
one, i.e., $r=s$. Furthermore, denote an attribute classifier $h$ as a tuple
$(g_{1},g_{2})$ where $g_{1}$ and $g_{2}$ denote the conditional errors as
defined in (4). Then, under a given error budget $U$, i.e.,
$\mathbb{P}(h(x)\neq a,y=1)=U$, the only global maximizers of $\gamma$ as
defined in (9) are the attribute classifiers $(0,{U}/{r})$ and $(U/r,0)$ (if
$U\leq r$) or $({U}/{r}-1,1)$ and $(1,{U}/{r}-1)$ (if $U\geq r$).

###### Proof.

In case of $r=s$, $\gamma$ as defined in (9) simplifies to

$\displaystyle\gamma=\frac{|1-g_{1}-g_{2}|}{1-(g_{1}-g_{2})^{2}},$

and the constraint $\mathbb{P}(h(x)\neq
a,y=1)=\mathbb{P}(a=0,y=1)g_{1}+\mathbb{P}(a=1,y=1)g_{2}=U$ is equivalent to
$g_{1}+g_{2}=\frac{U}{r}$. Our goal is to show that
$\operatorname*{arg\,max}_{(g_{1},g_{2})\in[0,1]^{2}:\,g_{1}+g_{2}=\frac{U}{r}}\Big{(}\gamma\Big{)}$
equals

$\displaystyle\\{(\max\\{{U}/{r}-1,0\\},\min\\{{U}/{r},1\\}),(\min\\{{U}/{r},1\\},\max\\{{U}/{r}-1,0\\})\\}.$

Writing $g_{2}$ in terms of $g_{1}$, we get that

$g_{2}=\frac{U}{r}-g_{1}$

and

$\gamma(g_{1})=\frac{|1-\frac{U}{r}|}{1-(2g_{1}-\frac{U}{r})^{2}}.$

The constraint $(g_{1},g_{2})\in[0,1]^{2}$ is equivalent to

$g_{1}\in[\max\\{\frac{U}{r}-1,0\\},\min\\{\frac{U}{r},1\\}].$

We assume that $\frac{U}{r}\leq 2$. Maximizing $\gamma(g_{1})$ is equivalent
to maximizing $(2g_{1}-\frac{U}{r})^{2}$, and the maximum of the latter
function is attained both at $g_{1}=\max\\{\frac{U}{r}-1,0\\}$ and
$g_{1}=\min\\{\frac{U}{r},1\\}$, which correspond to
$g_{2}=\min\\{\frac{U}{r},1\\}$ and $g_{2}=\max\\{\frac{U}{r}-1,0\\}$,
respectively. ∎

Figure 1: The distortion factor $\gamma$ as a function of $g_{1}$ for
different $r/s$ and under different error budgets $U=sg_{1}+rg_{2}$ for the
attribute classifier. Apparently, $\gamma$ always attains its maximum either
at the smallest or the largest possible value of $g_{1}$. Figure 2: Experiment
on the FIFA 20 player dataset—independence assumption (4) holds. Absolute
difference between the true bias and the estimated bias for direct (Dir) and
corrected (Cor) estimation, when 100 to 250 points of common data over $(y,a)$
are available, and for naive (Naive) estimation.

The above theorem implies that even under simplifying assumptions, the
structure of the optimal attribute classifier is counter-intuitive: to
estimate bias as accurately as possible, one may want to distribute the errors
of the given attribute classifier as unevenly as possible! Hence, great care
must be taken when designing the attribute classifier for the purpose of bias
estimation. Furthermore, while we only consider the case $r=s$, Figure 1 shows
the distortion factor $\gamma$ as a function of $g_{1}$ for a fixed error
budget $U$ also when $r\neq s$ (middle and right plot). As we can see, also
then $\gamma$ attains its maximum either at the smallest or the largest
possible value of $g_{1}$, which corresponds to distributing the error among
the two groups as unevenly as possible.

##  5 Perspective of the User of an Attribute Classifier

If the user of the attribute classifier expects Assumption I as defined in Eq.
(4) to (approximately) hold and she has some common data over $(y,a)$ from
which she will estimate the conditional errors $g_{1},g_{2}$ and the ratio of
base rates $r/s$, exploiting (8), she can try to improve the naive bias
estimate $|\hat{\alpha}-\hat{\beta}|$ by dividing it by an estimate of the
distortion factor $\gamma$. In this section, we present an experiment that
illustrates that such an approach indeed yields a better estimate of the true
bias $|\alpha-\beta|$. In a data scarce regime, this approach also compares
favorably to using the available data for directly estimating
$|\alpha-\beta|$.

Dataset.  We use the FIFA 20 player
dataset111https://www.kaggle.com/stefanoleone992/fifa-20-complete-player-
dataset. We predict whether a soccer player’s wage is above ($y=+1$) or below
($y=-1$) the median wage based on the player’s age and their _Overall_
attribute. For doing so we train a one-hidden-layer NN. We restrict the
dataset to contain only players of English or German nationality (leaving us
with 2883 players) and consider nationality as sensitive attribute. We train
an LSTM Hochreiter and Schmidhuber (1997) to predict this attribute from a
player’s name. In this case we can expect the conditional independence
assumption (4) to hold since given a player’s wage and nationality, their name
should be conditionally independent of age and _Overall_ attribute. Indeed,
the measure proposed in Awasthi et al. (2020) is small enough (see below) as
to confirm that our expectation holds and the independence assumption is
satisfied.

Figure 3: Experiment on the UCI Adult dataset—independence assumption (4) is
violated. Absolute difference between the true bias and the estimated bias for
direct (Dir) and corrected (Cor) estimation, when 100 to 1000 points of common
data over $(y,a)$ are available, and for naive (Naive) estimation.

Experimental setup.  We randomly split the dataset into three batches of sizes
1500, 1133 and 250, respectively. We use the first batch to train the label
and the attribute classifier. On the second batch, we compute both the true
bias $|\alpha-\beta|$ and the _naive estimate_ $|\hat{\alpha}-\hat{\beta}|$.
Finally, we use $n\in\\{100,150,200,250\\}$ points from the third batch to
estimate $g_{1},g_{2},r,s$, and thus $\gamma$, and also to directly estimate
$|\alpha-\beta|$. We refer to the latter estimate as _direct estimate_.
Exploiting (8), we use the estimate of $\gamma$ to correct the naive estimate
$|\hat{\alpha}-\hat{\beta}|$ by dividing it by the estimate of $\gamma$. We
refer to the result as _corrected estimate_.

Figure 2 shows the absolute difference between the true bias and the various
estimates, where for the direct estimate and the corrected estimate we show
the results depending on $n$, the amount of data for which we have both $y$
and $a$. The boxplots are obtained from running the experiment 100 times. We
can see that the corrected estimate significantly improves over the naive
estimate (e.g., the mean absolute difference, averaged over the 100 runs, is
0.0831 for the naive estimate and 0.0461 for the corrected estimate with
$n=250$). Furthermore, the corrected estimate consistently outperforms the
direct estimate. When only $n=100$ points of common data over $(y,a)$ are
used, the mean absolute difference for the corrected estimate is 0.054 while
for the direct estimate it is 0.0837. In this experiment, the mean true bias
is 0.14, the mean error of the label and the attribute classifier is 0.18 and
0.25, respectively, and the mean violation of the independence assumption
according to the measure proposed in Awasthi et al. (2020) is $0.017$.

###  5.1 An Active Sampling based Algorithm for Bias Estimation in General
Settings

In some real-world scenarios the conditional independence assumption might be
violated, and we would like to ask, in those cases, does the correction as
specified in Eq. (8) still give a good estimate of the true bias? We show in
the following that the correction might not always lead to a better bias
estimate when Assumption I does not hold. Therefore, in order to obtain a good
bias estimate in general, we explore active-sampling strategies that aim to
use as little common data over $(y,a)$ as possible, ideally comparable to the
setting when the independence assumption holds.

Dataset.  We use the UCI Adult
dataset222https://archive.ics.uci.edu/ml/datasets/Adult, which comes divided
into a training and a test set. On the training set, we train Random Forest
classifiers for both predicting the label (income: $>50K$ or not, using all
features present in the dataset except gender) and the attribute (gender:
“Male” or “Female” as categorized in the dataset, using all features except
income). We used the measure proposed in Awasthi et al. (2020) to evaluate
whether the independence assumption (4) (approximately) holds and found that
the independence assumption clearly fails to hold.

#### Inaccurate bias estimation when the conditional independence assumption
is violated.

We use the UCI Adult training set for training our label classifier and
attribute classifier. For the Adult test set (around 16,000 examples), we hold
out a set with $2,000$ examples for estimating $g_{1},g_{2},r,s$ since it
requires some common data over $(y,a)$, and use the rest for estimating the
true bias ($|\alpha-\beta|$). In Figure 3, we show the absolute difference
between the estimated bias and the true bias. For the estimated bias, we use
the same setting as the previous experiment, with direct estimate, corrected
estimate, and naive estimate. We can see the the correction gives a more
accurate estimate than direct estimation, however, the naive estimate remains
to be the one with the most accurate estimate.

#### Active sampling algorithm.

We next address the limitations of the approaches explored above. In
particular, we propose a _general active-sampling_ based strategy that the
label classifier can use to accurately estimate the bias, using as little
common data over $(y,a)$ as possible, given the attribute classifier.
Furthermore, we will make _no assumption_ about the conditional independence
or the structure of the attribute classifier.

In the general setting the estimated bias and the true bias are related as
follows:

######  Theorem 3.

The true bias $\alpha-\beta$ can be derived from $\hat{\alpha},\hat{\beta}$
as:

$\displaystyle\alpha-\beta$
$\displaystyle=\frac{\hat{\alpha}(\frac{s}{r}g_{1}+1-g_{2})(1-\delta_{1}+\frac{r}{s}\delta_{2})}{1-\delta_{1}-\delta_{2}}$
$\displaystyle-\frac{\hat{\beta}(1-g_{1}+\frac{r}{s}g_{2})(1+\frac{s}{r}\delta_{1}-\delta_{2})}{1-\delta_{1}-\delta_{2}},$
(10)

where

$\displaystyle\delta_{1}$
$\displaystyle=\mathbb{P}(\hat{a}=1|f(x)=1,a=0,y=1),$
$\displaystyle\delta_{2}$
$\displaystyle=\mathbb{P}(\hat{a}=0|f(x)=1,a=1,y=1),$ (11)

and $g_{1},g_{2}$ are as defined in Eq. (4).

Figure 4: The absolute difference between estimated bias and the true bias,
based on different active sampling strategies (left), and based on direct
estimation over selected samples using uniform/positive sampling (right). Both
are results averaged over $10$ runs with random initialization. Algorithm 1
Active Sampling

0: Input: $D_{2}=\\{(x_{1},y_{1}),\dots,(x_{m},y_{m})\\}$, attribute
classifier $h$, parameters $b,w$.

0: Output: Estimated bias $|\hat{\alpha}-\hat{\beta}|$, tolerance $\epsilon$.

1: Sample a set of $b$ examples uniformly at random from $D_{2}$ conditioned
on $y=1$ and get their true attributes. Get estimates $\hat{r}$ and $\hat{s}$
using the sampled examples.

2: Initialize $t=0$ and
$g^{(0)}_{1},g^{(0)}_{2},\delta^{(0)}_{1},\delta^{(0)}_{2}$ to be zero.

3: for $t=1,\dots$ do

4: Sample a batch of $b$ unlabeled (i.e. no sensitive attribute information)
examples uniformly at random from $D_{2}$ conditioned on $y=1$.

5: Sort the examples in ascending order according to the uncertainty of $h$,
i.e., $|h(x)-0.5|$.

6: Obtain true attribute information the first $w$ examples and append to the
labeled set of data. Compute
$g^{(t+1)}_{1},g^{(t+1)}_{2},\delta^{(t+1)}_{1},\delta^{(t+1)}_{2}$ on the
labeled set using (4) and (3).

7: If
$|g_{1}^{(t+1)}-g_{1}^{(t)}|,|g_{2}^{(t+1)}-g_{2}^{(t)}|,|\delta_{1}^{(t+1)}-\delta_{1}^{(t)}|,|g\delta_{2}^{(t+1)}-\delta_{2}^{(t)}|$
are all bounded by $\epsilon$ then break.

8: end for

9: Output estimated bias obtained by using (10) and the above estimates.

While $r,s$ can be estimated from a small amount of data, we explore sampling
strategies for estimating the attribute classifier dependent quantities,
namely, $g_{1},g_{2}$ and $\delta_{1},\delta_{2}$. Two natural sampling
schemes are: (i) Uniform sampling where we uniformly sample a set of examples
and get their true sensitive attribute information, and (ii) Positive
sampling: where we perform uniform sampling on the subset of examples with
$y=1$. We expect positive sampling to perform better than uniform sampling,
since the quantities that we are estimating are conditioned on $y=1$. We
compare the above two approaches with (iii) an active sampling approach that
involves querying for true sensitive attributes (conditioned on $y=1$) of
examples on which the attribute classifier is the most uncertain (as described
in Algorithm 1). For each of the methods, in each iteration, we compute the
estimated bias on the UCI Adult test set by using true values of $a$ over the
selected samples, and the predicted values $\hat{a}$ from the attribute
classifier for the unselected samples, using a sampling batch size of $100$.
The results are shown in Figure 4 (left), where we see that the uncertainty
based active sampling approach requires significantly less common data to
accurately estimate the bias.

Furthermore, we also compare our approach with (iv) Direct estimation: where
we directly estimate the bias ($|\alpha-\beta|$) based on the currently
sampled set $S$, i.e., the small amount of common $(y,a)$ on the same test
set, using a uniform sampling strategy and a positive sampling strategy. The
result is shown in Figure 4 (right). Note that the magnitude in the y-axis is
much larger compared to the left figure, indicating that direct estimation
using few samples tends to give less reliable estimation of the bias.

##  6 Discussion and Conclusion

We formalized and studied a commonly occurring scenario in fairness evaluation
and auditing namely, the lack of common data involving both the class labels
and sensitive attributes. Our experiments and theoretical analysis reveal that
great care must be taken in designing attribute classifiers for the purpose of
bias estimation. Furthermore, in certain scenarios, the structure of the
optimal attribute classifier can be contradictory to natural criteria such as
accuracy and fairness. From the perspective of the designer of the attribute
classifier, maximizing the distortion factor as in (9) is a challenging
optimization problem. It would be interesting to explore efficient algorithms
for solving this. Throughout our analysis we assume that the datasets
$D_{1},D_{2}$ are sampled from the same distribution. It would be interesting
to extend our theory to the more realistic case of when the dataset
distributions are different. Finally, it would also be interesting to provide
theoretical guarantees for the active sampling scheme in Algorithm 1.

## References

  * (1)
  * Awasthi et al. (2020) Pranjal Awasthi, Matthäus Kleindessner, and Jamie Morgenstern. 2020.  Equalized odds postprocessing under imperfect group information. In _International Conference on Artificial Intelligence and Statistics_.
  * Beutel et al. (2019) Alex Beutel, Jilin Chen, Tulsee Doshi, Hai Qian, Li Wei, Yi Wu, Lukasz Heldt, Zhe Zhao, Lichan Hong, Ed H Chi, and Cristos Goodrow. 2019\.  Fairness in recommendation ranking through pairwise comparisons. In _Proceedings of the 25th ACM SIGKDD_.
  * Blum et al. (2018) Avrim Blum, Suriya Gunasekar, Thodoris Lykouris, and Nati Srebro. 2018.  On preserving non-discrimination when combining expert advice. In _Advances in Neural Information Processing Systems_.
  * Brown et al. (2016) David P Brown, Caprice Knapp, Kimberly Baker, and Meggen Kaufmann. 2016.  Using Bayesian imputation to assess racial and ethnic disparities in pediatric performance measures.  _Health services research_ 51, 3 (2016), 1095–1108.
  * Bureau (2014) Consumer Financial Protection Bureau. 2014\.  Using publicly available information to proxy for unidentified race and ethnicity: A methodology and assessment.  _Washington, DC: CFPB, Summer_ (2014).
  * Calders et al. (2009) Toon Calders, Faisal Kamiran, and Mykola Pechenizkiy. 2009\.  Building classifiers with independency constraints. In _2009 IEEE International Conference on Data Mining Workshops_. IEEE.
  * Celis et al. (2018) L Elisa Celis, Damian Straszak, and Nisheeth K Vishnoi. 2018\.  Ranking with fairness constraints. In _International Colloquium on Automata, Languages and Programming (ICALP)_.
  * Chen et al. (2019) Jiahao Chen, Nathan Kallus, Xiaojie Mao, Geoffry Svacha, and Madeleine Udell. 2019.  Fairness under unawareness: Assessing disparity when protected class is unobserved. In _Proceedings of the Conference on Fairness, Accountability, and Transparency_.
  * Chierichetti et al. (2017) Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. 2017.  Fair clustering through fairlets. In _Advances in Neural Information Processing Systems_.
  * Coston et al. (2019) Amanda Coston, Karthikeyan N Ramamurthy, Dennis Wei, Kush R Varshney, Skyler Speakman, Zairah Mustahsan, and Supriyo Chakraborty. 2019.  Fair Transfer Learning with Missing Protected Attributes. In _AAAI / ACM Conference on Artificial Intelligence, Ethics, and Society_.
  * Dua and Graff (2017) Dheeru Dua and Casey Graff. 2017.  UCI Machine Learning Repository.  http://archive.ics.uci.edu/ml
  * Dwork et al. (2012) Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. 2012.  Fairness through awareness. In _Proceedings of the 3rd innovations in theoretical computer science conference_. 214–226.
  * Fremont et al. (2005) Allen M Fremont, Arlene Bierman, Steve L Wickstrom, Chloe E Bird, Mona Shah, José J Escarce, Thomas Horstman, and Thomas Rector. 2005\.  Use of geocoding in managed care settings to identify quality disparities.  _Health Affairs_ 24, 2 (2005), 516–526.
  * Fremont et al. (2016) Allen M Fremont, Joel S Weissman, Emily Hoch, and Marc N Elliott. 2016.  When race/ethnicity data are lacking.  _RAND Health Q_ 6 (2016), 1–6.
  * Gillen et al. (2018) Stephen Gillen, Christopher Jung, Michael Kearns, and Aaron Roth. 2018.  Online learning with an unknown fairness metric. In _Advances in Neural Information Processing Systems_.
  * Gupta et al. (2018) Maya Gupta, Andrew Cotter, Mahdi M Fard, and Serena Wang. 2018.  Proxy Fairness. (2018).  arXiv:1806.11212 [cs.LG].
  * Hardt et al. (2016) Moritz Hardt, Eric Price, and Nathan Srebro. 2016.  Equality of opportunity in supervised learning. In _Advances in Neural Information Processing Systems_.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long Short-term Memory.  _Neural computation_ 9 (12 1997), 1735–80.
  * Holstein et al. (2019) Kenneth Holstein, Jennifer Wortman Vaughan, Hal Daumé III, Miro Dudik, and Hanna Wallach. 2019\.  Improving fairness in machine learning systems: What do industry practitioners need?. In _Proceedings of the 2019 CHI Conference on Human Factors in Computing Systems_.
  * Jabbari et al. (2017) Shahin Jabbari, Matthew Joseph, Michael Kearns, Jamie Morgenstern, and Aaron Roth. 2017\.  Fairness in reinforcement learning. In _International Conference on Machine Learning_.
  * Joseph et al. (2016) Matthew Joseph, Michael Kearns, Jamie H Morgenstern, and Aaron Roth. 2016.  Fairness in learning: Classic and contextual bandits. In _Advances in Neural Information Processing Systems_. 325–333.
  * Kallus et al. (2020) Nathan Kallus, Xiaojie Mao, and Angela Zhou. 2020.  Assessing Algorithmic Fairness with Unobserved Protected Class Using Data Combination. In _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_.
  * Kleinberg et al. (2017) Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. 2017\.  Inherent Trade-Offs in the Fair Determination of Risk Scores. In _Innovations in Theoretical Computer Science Conference (ITCS)_.
  * Kleindessner et al. (2019) Matthäus Kleindessner, Pranjal Awasthi, and Jamie Morgenstern. 2019.  Fair $k$-center clustering for data summarization. In _International Conference on Machine Learning_.
  * Lamy et al. (2019) Alexandre L Lamy, Ziyuan Zhong, Aditya K Menon, and Nakul Verma. 2019.  Noise-tolerant fair classification. In _Advances in Neural Information Processing Systems_.
  * Pleiss et al. (2017) Geoff Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q Weinberger. 2017.  On fairness and calibration. In _Advances in Neural Information Processing Systems_.
  * Samadi et al. (2018) Samira Samadi, Uthaipon Tantipongpipat, Jamie H Morgenstern, Mohit Singh, and Santosh Vempala. 2018\.  The price of fair PCA: One extra dimension. In _Advances in Neural Information Processing Systems_.
  * Schumann et al. (2019) Candice Schumann, Xuezhi Wang, Alex Beutel, Jilin Chen, Hai Qian, and Ed H Chi. 2019\.  Transfer of machine learning fairness across domains. (2019).  arXiv:1906.09688 [cs.LG].
  * Weissman and Hasnain-Wynia (2011) Joel S Weissman and Romana Hasnain-Wynia. 2011.  Advancing health care equity through improved data collection.  _New England Journal of Medicine_ 364, 24 (2011), 2276–2277.
  * Zafar et al. (2017) Muhammad B Zafar, Isabel Valera, Manuel G Rodriguez, and Krishna P Gummadi. 2017.  Fairness Beyond Disparate Treatment & Disparate Impact: Learning Classification Without Disparate Mistreatment. In _International Conference on World Wide Web (WWW)_.
  * Zhang (2018) Yan Zhang. 2018\.  Assessing Fair Lending Risks Using Race/Ethnicity Proxies.  _Management Science_ 64, 1 (2018), 178–197.
  * Zliobaite (2015) Indre Zliobaite. 2015\.  On the relation between accuracy and fairness in binary classification. (2015).  arXiv:1505.05723 [cs.LG].

##  Appendix A Appendix

###### Proof of Theorem 1.

Let the joint distribution $Q$ be as follows:

$\displaystyle\mathbb{P}(x_{1}=1,x_{2}=0,a=1,y=1)$
$\displaystyle=\frac{1}{6},$
$\displaystyle\mathbb{P}(x_{1}=1,x_{2}=1,a=1,y=1)$
$\displaystyle=\frac{1}{6},$
$\displaystyle\mathbb{P}(x_{1}=1,x_{2}=1,a=0,y=1)$
$\displaystyle=\frac{1}{6},$
$\displaystyle\mathbb{P}(x_{1}=1,x_{2}=0,a=0,y=1)$
$\displaystyle=\frac{1}{6},$
$\displaystyle\mathbb{P}(x_{1}=1,x_{2}=1,a=1,y=0)$
$\displaystyle=\frac{1}{6},$
$\displaystyle\mathbb{P}(x_{1}=1,x_{2}=0,a=0,y=0)$
$\displaystyle=\frac{1}{6}.$

Then we have for $f=x_{2}$,

$\displaystyle\mathbb{P}(f=1|y=1,a=0)$
$\displaystyle=\mathbb{P}(x_{2}=1|y=1,a=0)=\frac{1}{2}.$

Similarly,

$\displaystyle\mathbb{P}(f=1|y=1,a=1)$
$\displaystyle=\mathbb{P}(x_{2}=1|y=1,a=1)=\frac{1}{2}.$

Hence the true bias of $f$ is zero. Next consider the Bayes optimal predictor
for $a$ that makes predictions based on $\mathbb{P}(a|x_{1},x_{2})$. If this
probability is half, then we consider an arbitrary predictor for the Bayes
optimal classifier. In this case the Bayes optimal predictions $\hat{a}$ are
shown in the table below.

$x_{1}$ | $x_{2}$ | $a$ | $y$ | $\hat{a}$
---|---|---|---|---
$1$ | $0$ | $1$ | $1$ | $0$
$1$ | $1$ | $1$ | $1$ | $1$
$1$ | $1$ | $0$ | $1$ | $1$
$1$ | $0$ | $0$ | $1$ | $0$
$1$ | $1$ | $1$ | $0$ | $1$
$1$ | $0$ | $0$ | $0$ | $0$

Next using $\hat{a}$ instead of $a$ to estimate the bias of $f$ we get

$\displaystyle\mathbb{P}(f=1|y=1,\hat{a}=0)$
$\displaystyle=\mathbb{P}(x_{2}=1|y=1,\hat{a}=0)=0.$

Similarly,

$\displaystyle\mathbb{P}(f=1|y=1,\hat{a}=1)$
$\displaystyle=\mathbb{P}(x_{2}=1|y=1,\hat{a}=1)=1.$

Hence using a Bayes optimal attribute classifier leads to an estimated bias of
one whereas the true bias is zero. In this case, using a random attribute
predictor, i.e. predicting the class label via a coin toss is better than
using the Bayes optimal one! ∎

###### Proof of Theorem 3.

To see (10) notice that from the definition of $\hat{\alpha}$, we have

$\displaystyle\hat{\alpha}$
$\displaystyle=\mathbb{P}(f(x)=1|y=1,\hat{a}=1)=\frac{\mathbb{P}(f(x)=1,y=1,\hat{a}=1)}{\mathbb{P}(y=1,\hat{a}=1)}$
$\displaystyle=\frac{\mathbb{P}(a=0,f(x)=1,y=1,\hat{a}=1)+\mathbb{P}(a=1,f(x)=1,y=1,\hat{a}=1)}{\mathbb{P}(y=1,a=0,\hat{a}=1)+\mathbb{P}(y=1,a=1,\hat{a}=1)}$
(12)

Next we first simplify the two terms in the numerator. We can write

$\displaystyle\mathbb{P}(a=0,f(x)=1,y=1,\hat{a}=1)$
$\displaystyle=\mathbb{P}(\hat{a}=1|f(x)=1,a=0,y=1)\mathbb{P}(f(x)=1|a=0,y=1)\mathbb{P}(a=0,y=1)$
$\displaystyle=\delta_{1}\beta s.$

Similarly, we write

$\displaystyle\mathbb{P}(a=1,f(x)=1,y=1,\hat{a}=1)$
$\displaystyle=\mathbb{P}(\hat{a}=1|f(x)=1,a=1,y=1)\mathbb{P}(f(x)=1|a=1,y=1)\mathbb{P}(a=1,y=1)$
$\displaystyle=(1-\delta_{2})\alpha r.$

For the denominator we have

$\displaystyle\mathbb{P}(y=1,a=0,\hat{a}=1)$
$\displaystyle=\mathbb{P}(\hat{a}=1|y=1,a=0)P(y=1,a=0)$
$\displaystyle=g_{1}s.$

Similarly, we have

$\displaystyle\mathbb{P}(y=1,a=1,\hat{a}=1)$
$\displaystyle=\mathbb{P}(\hat{a}=1|y=1,a=1)P(y=1,a=1)$
$\displaystyle=(1-g_{2})r.$

Substituting into (A) we get

$\displaystyle\hat{\alpha}$ $\displaystyle=\frac{\delta_{1}\beta
s+(1-\delta_{2})\alpha r}{g_{1}s+(1-g_{2})r}.$

Similarly for $\hat{\beta}$, it is easy to derive:

$\displaystyle\hat{\beta}$
$\displaystyle=\mathbb{P}(f=1|y=1,\hat{a}=0)=\frac{\delta_{2}\alpha
r+(1-\delta_{1})\beta s}{(1-g_{1})s+g_{2}r}.$

Hence we have:

$\displaystyle\hat{\alpha}[g_{1}\frac{s}{r}+(1-g_{2})]=\delta_{1}\frac{s}{r}\beta+(1-\delta_{2})\alpha,$
(13)
$\displaystyle\hat{\beta}[(1-g_{1})+g_{2}\frac{r}{s}]=\delta_{2}\frac{r}{s}\alpha+(1-\delta_{1})\beta.$
(14)

Multiplying Eq. (13) by $(1-\delta_{1}+\frac{r}{s}\delta_{2})$, multiplying
Eq. (14) by $(1+\frac{s}{r}\delta_{1}-\delta_{2})$, and subtracting the latter
from the former, we get:

$\displaystyle(1-\delta_{1}-\delta_{2})(\alpha-\beta)=$
$\displaystyle\hat{\alpha}[g_{1}\frac{s}{r}+(1-g_{2})](1-\delta_{1}+\frac{r}{s}\delta_{2})-\hat{\beta}[(1-g_{1})+g_{2}\frac{r}{s}](1+\frac{s}{r}\delta_{1}-\delta_{2}).$

Dividing the right hand side by $1-\delta_{1}-\delta_{2}$ we have Eq. (10). ∎