  Providing formal guarantees of algorithmic fairness is of paramount
importance to socially responsible deployment of machine learning algorithms.
In this work, we study formal guarantees, i.e., certificates, for individual
fairness (IF) of neural networks. We start by introducing a novel convex
approximation of IF constraints that exponentially decreases the computational
cost of providing formal guarantees of local individual fairness. We highlight
that prior methods are constrained by their focus on global IF certification
and can therefore only scale to models with a few dozen hidden neurons, thus
limiting their practical impact. We propose to certify distributional
individual fairness which ensures that for a given empirical distribution and
all distributions within a $\gamma$-Wasserstein ball, the neural network has
guaranteed individually fair predictions. Leveraging developments in
quasi-convex optimization, we provide novel and efficient certified bounds on
distributional individual fairness and show that our method allows us to
certify and regularize neural networks that are several orders of magnitude
larger than those considered by prior works. Moreover, we study real-world
distribution shifts and find our bounds to be a scalable, practical, and sound
source of IF guarantees.
