We consider the optimization of complex performance metrics in multi-label
classification under the population utility framework. We mainly focus on
metrics linearly decomposable into a sum of binary classification utilities
applied separately to each label with an additional requirement of exactly $k$
labels predicted for each instance. These "macro-at-$k$" metrics possess
desired properties for extreme classification problems with long tail labels.
Unfortunately, the at-$k$ constraint couples the otherwise independent binary
classification tasks, leading to a much more challenging optimization problem
than standard macro-averages. We provide a statistical framework to study this
problem, prove the existence and the form of the optimal classifier, and
propose a statistically consistent and practical learning algorithm based on
the Frank-Wolfe method. Interestingly, our main results concern even more
general metrics being non-linear functions of label-wise confusion matrices.
Empirical results provide evidence for the competitive performance of the
proposed approach.

在多标签分类的人口效用框架下，我们考虑复杂性能度量的优化问题。我们主要关注一种指标，它线性可分解为对每个标签分别应用的二分类效用的总和，并对每个实例预测出恰好 k 个标签。这些 “宏 - at-$k$” 指标在具有长尾标签的极端分类问题中具有理想的性质。遗憾的是，at-$k$ 约束将原本相互独立的二分类任务耦合起来，导致优化问题比标准的宏平均更具挑战性。我们提供了一个统计框架来研究这个问题，证明了最优分类器的存在和形式，并基于 Frank-Wolfe 方法提出了一个统计一致且实用的学习算法。有趣的是，我们的主要结果还涉及非线性函数的更一般度量，这些函数是标签混淆矩阵的函数。实证结果证明了所提方法的竞争性能。