On preserving non-discrimination when combining expert advice
We study the interplay between sequential decision making and avoiding discrimination against protected groups, when examples arrive online and do not follow distributional assumptions. We consider the most basic extension of classical online learning: Given a class of predictors that are individually non-discriminatory with respect to a particular metric, how can we combine them to perform as well as the best predictor, while preserving non-discrimination? Surprisingly we show that this task is unachievable for the prevalent notion of equalized odds that requires equal false negative rates and equal false positive rates across groups. On the positive side, for another notion of non-discrimination, equalized error rates, we show that running separate instances of the classical multiplicative weights algorithm for each group achieves this guarantee. Interestingly, even for this notion, we show that algorithms with stronger performance guarantees than multiplicative weights cannot preserve non-discrimination.
The paper theoretically studies the suitability of achieving a particular definition of fairness, equalized odds (which relates to the false positive rate), in the context of online learning with experts advise (Cesa-Bianchi et al. 2006). In particular, the authors show that achieving an online algorithm that jointly satisfies zero-regret and equalized odds is not possible. Afterward, they show that this is not the case when considering fairness in terms of the total number of errors per group. They also discuss that unfortunately this definition of fairness (also previously discussed in  Zafar et al., 2017) is not realistic (or even fair) in many real-world scenarios.  In the positive side, I believe that (im)possibility theoretical studies on when a fairness definition can be accomplished is definitely a major contribution to the field.  However, I also believe that the paper has important gaps to be filled:  1) Their definition of online learning comes from the game theory literature and does not corresponds to the standard ML view on online learning. However, the authors do not clarify this particular setting in the abstract (neither the title of the paper) and provide any reference to the considered  "benign setting"--where at time t there is a set of expert providing their advise about the decision to be made, and the learner select one expert advise (decision) with a fixed probability i~p^t, getting a loss l(t,i) that depends on the selected expert. Is this the actual setting? Please clarify this point in the paper, and add the necessary references.  2) Although the paper is presented in the context of fairness, which is definitely a real problem, the authors do not provide a single real-world example where their setting (based on the game theoretical game benign) would fit.  As a consequence, it is hard to evaluate the potential impact of the presented theoretical results in the field.  In summary, I believe although the paper presents good ideas and results, it does not provide the necessary context and details to judge the contribution of the paper.   Cesa-Bianchi, Nicolo, and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.  B. Zafar, I. Valera, M. Gomez-Rodriguez and K. Gummadi, "Fairness Beyond Disparate Treatment & Disparate Impact: Learning Classification without Disparate Mistreatment", (Full paper) 26th International World Wide Web Conference (WWW), Perth (Australia), April 2017.