Title: "Robust Reductions from Ranking to Classification" (MACH444)

We would like to thank both referees for their careful reviews.
We revised the paper to address the requests of Referee 2.  

Here is our response:

1) The problem can be fixed by making the learned classifier
dependent on the subset (which is what the paper does now).
Alternatively, we can make the assumption that for any pair of 
unlabeled instances, their optimal pairwise ordering is 
independent of the drawn subset, whenever they are drawn together.
An explanation of both fixes has been added.
Note that this change affects only regret bounds.

The same assumption is needed in a subsequent paper by Ailon and Mohri.
The fundamental problem is that a regret reduction cannot throw away
any information (the subset in this case) because the adversary can encode 
conflicting preferences based on the value of the subset.

2) We clarified the relation to other settings.

3) Because of the inherent iid assumption in Clemencon et al., we decided not
to include the composition.

4) > min --> inf (also later in the proofs)
For simplicity of presentation, we let the space be finite.

5) We made the proof of Lemma 1 more explicit.

We hope that reviewer 2 finds the revision satisfactory.