The argument the reviewer was concerned about was made explicit in 
the proof of Theorem 1.

We added the following paragraph in Section 7 to address the reviewer's 
final comment:

A generalization result for the induced classification problem implies,
via the reduction, a generalization result for the AUC problem.  
In situations where rankings are drawn iid from some base distribution 
D, the induced independent sample from Auc-Train(D) can be formed by
first drawing a ranking from D and then picking a mixed pair at random.
Repeating this process many times produces an iid sample set for
which standard rate of convergence analysis bounds hypothesis class regret.

We hope that the reviewer finds the revision satisfactory.