  The seminal work of Dwork {\em et al.} [ITCS 2012] introduced a metric-based
notion of individual fairness. Given a task-specific similarity metric, their
notion required that every pair of similar individuals should be treated
similarly. In the context of machine learning, however, individual fairness
does not generalize from a training set to the underlying population. We show
that this can lead to computational intractability even for simple
fair-learning tasks.
  With this motivation in mind, we introduce and study a relaxed notion of {\em
approximate metric-fairness}: for a random pair of individuals sampled from the
population, with all but a small probability of error, if they are similar then
they should be treated similarly. We formalize the goal of achieving
approximate metric-fairness simultaneously with best-possible accuracy as
Probably Approximately Correct and Fair (PACF) Learning. We show that
approximate metric-fairness {\em does} generalize, and leverage these
generalization guarantees to construct polynomial-time PACF learning algorithms
for the classes of linear and logistic predictors.
