  Top-k error has become a popular metric for large-scale classification
benchmarks due to the inevitable semantic ambiguity among classes. Existing
literature on top-k optimization generally focuses on the optimization method
of the top-k objective, while ignoring the limitations of the metric itself. In
this paper, we point out that the top-k objective lacks enough discrimination
such that the induced predictions may give a totally irrelevant label a top
rank. To fix this issue, we develop a novel metric named partial Area Under the
top-k Curve (AUTKC). Theoretical analysis shows that AUTKC has a better
discrimination ability, and its Bayes optimal score function could give a
correct top-K ranking with respect to the conditional probability. This shows
that AUTKC does not allow irrelevant labels to appear in the top list.
Furthermore, we present an empirical surrogate risk minimization framework to
optimize the proposed metric. Theoretically, we present (1) a sufficient
condition for Fisher consistency of the Bayes optimal score function; (2) a
generalization upper bound which is insensitive to the number of classes under
a simple hyperparameter setting. Finally, the experimental results on four
benchmark datasets validate the effectiveness of our proposed framework.
