Learning with Average Top-k Loss
In this work, we introduce the average top-k (AT k ) loss as a new aggregate loss for supervised learning, which is the average over the k largest individual losses over a training dataset. We show that the AT k loss is a natural generalization of the two widely used aggregate losses, namely the average loss and the maximum loss, but can combine their advantages and mitigate their drawbacks to better adapt to different data distributions. Furthermore, it remains a convex function over all individual losses, which can lead to convex optimization problems that can be solved effectively with conventional gradient-based methods. We provide an intuitive interpretation of the AT k loss based on its equivalent effect on the continuous individual loss functions, suggesting that it can reduce the penalty on correctly classified data. We further give a learning theory analysis of MAT k learning on the classification calibration of the AT k loss and the error bounds of AT k -SVM. We demonstrate the applicability of minimum average top-k learning for binary classification and regression using synthetic and real datasets.
This paper investigates a new learning setting: optimizing the average k largest (top-k) individual functions for supervised learning. This setting is different from the standard Empirical Risk minimization (ERM), which optimize the average loss function over datasets. The proposed setting is also different from maximum loss (Shalev-Shwartz and Wexler 2016), which optimize the maximum loss. This paper tries to optimize the average top-k loss functions. This can be viewed as a natural generalization of the ERM and the maximum loss. The authors summary it as a convex optimization problem, which can be solved with conventional gradient-based method. The authors give some learning theory analyses of setting on the classification calibration of the Top-k loss and the error bounds of ATk-SVM. Finally, the authors present some experiments to verify the effectiveness of the proposed algorithm.
This work is generally well-written with some advantages as follows:
1) The authors introduce a new direction for supervised learning, which is a natural generalization of ERM and the work of (Shalev-Shwartz and Wexler 2016).
2) Some theoretical analyses are presented for the proposed learning setting. 
3) The author present a learning algorithm.
Cons:
1) Some statements are not clear, for example, top-k loss, which is similar to top-k ranking; more important, ensembles loss gives some impressions for ensemble learning whereas they are totally different. 
2) When we used the average top-k loss? I do not think that the authors make clear explanations. Intuitively, the performance (w.r.t. accuracy) of average top-k loss is less than ERM without noise and outliers, while I guess the average too-k loss algorithm may have good performance when deal with noise data and outliers.
3) How to choose the parameter k? The authors use cross-validation in experiments, while there is no some analyses. 
4) The authors should present some t-test on the performance on benchmark datasets. I doubt some experimental results. For example, the accuracy for German is about 0.79 for standard learning algorithms.
5) How about the efficiency in comparison with ERM and the work of (Shalev-Shwartz and Wexler 2016).