In this work, we introduce the average top- k ( ATk) loss, which is the average over the k largest individual losses over a training data, as a new aggregate loss for supervised learning. We show that the ATk loss is a natural generalization of the two widely used aggregate losses, namely the average loss and the maximum loss. Yet, the ATk loss can better adapt to different data distributions because of the extra flexibility provided by the different choices of k. Furthermore, it remains a convex function over all individual losses and can be combined with different types of individual loss without significant increase in computation. We then provide interpretations of the ATk loss from the perspective of the modification of individual loss and robustness to training data distributions. We further study the classification calibration of the ATk loss and the error bounds of ATk-SVM model. We demonstrate the applicability of minimum average top- k learning for supervised learning problems including binary/multi-class classification and regression, using experiments on both synthetic and real datasets.