Thanks @srowen for the explanation! I'm thinking rather than compute AUC on a subsample, is it possible to compute it accurately on the entire dataset if we only need the rank of positives. This could be done by a sort by prediction scores, count examples per partition, collect and broadcast counts, assign ranks per partition. Assigning ranks to a RDD would be useful for other applications as well.

My concern with sampling is ROC is quite sensitive to predictions at the top. Sampling may cause large variance of the result. Well, I haven't tested it yet.