Area under the receiver operating characteristics curve (AUC) is an important metric for a wide range of machine learning problems; including the well-known click through rate prediction for online sponsored product ads. Scalable methods for optimizing AUC have recently been proposed; however, handling very large datasets remains an open challenge. This paper proposes a novel approach to AUC maximization, based on sampling mini-batches of positive/negative instance pairs and computing U-statistics to approximate a global risk minimization problem. The resulting algorithm is simple, fast, and learning-rate free. Extensive experiments show the practical utility of the proposed method.