  Evaluating fairness can be challenging in practice because the sensitive
attributes of data are often inaccessible due to privacy constraints. The go-to
approach that the industry frequently adopts is using off-the-shelf proxy
models to predict the missing sensitive attributes, e.g. Meta [Alao et al.,
2021] and Twitter [Belli et al., 2022]. Despite its popularity, there are three
important questions unanswered: (1) Is directly using proxies efficacious in
measuring fairness? (2) If not, is it possible to accurately evaluate fairness
using proxies only? (3) Given the ethical controversy over inferring user
private information, is it possible to only use weak (i.e. inaccurate) proxies
in order to protect privacy? Our theoretical analyses show that directly using
proxy models can give a false sense of (un)fairness. Second, we develop an
algorithm that is able to measure fairness (provably) accurately with only
three properly identified proxies. Third, we show that our algorithm allows the
use of only weak proxies (e.g. with only 68.85%accuracy on COMPAS), adding an
extra layer of protection on user privacy. Experiments validate our theoretical
analyses and show our algorithm can effectively measure and mitigate bias. Our
results imply a set of practical guidelines for practitioners on how to use
proxies properly. Code is available at github.com/UCSC-REAL/fair-eval.
