A Other related work Kearns and Mansour [

Fact 2.1 is a simple consequence of the following lemma, whose proof also appears in [Jon16]: Lemma B.1. We apply Theorem 2 with ' We first analyze the quantity on the LHS of Equation (9). Combining this with Equations (9), (11) and (12) and rearranging completes the proof. We will need a couple of propositions: Proposition E.1. By Fact 2.1, we have that NS