Macro-AUC is the arithmetic mean of the class-wise AUCs in multi-label
learning and is commonly used in practice. However, its theoretical
understanding is far lacking. Toward solving it, we characterize the
generalization properties of various learning algorithms based on the
corresponding surrogate losses w.r.t. Macro-AUC. We theoretically identify a
critical factor of the dataset affecting the generalization bounds: \emph{the
label-wise class imbalance}. Our results on the imbalance-aware error bounds
show that the widely-used univariate loss-based algorithm is more sensitive to
the label-wise class imbalance than the proposed pairwise and reweighted
loss-based ones, which probably implies its worse performance. Moreover,
empirical results on various datasets corroborate our theory findings. To
establish it, technically, we propose a new (and more general) McDiarmid-type
concentration inequality, which may be of independent interest.

本文旨在理解和解决多标签学习中常用的宏平均（Macro-AUC）评价指标的理论问题。通过对 PASCAL VOC、Yahoo、和 MS COCO 数据集的实验结果和理论分析，发现数据集的类别不平衡是影响宏平均评价指标泛化范围的关键因素，并提出一种更通用的 McDiarmid 型浓度不等式。结果表明，相较于基于单变量损失函数的算法，基于成对损失函数和重新加权的损失函数更加稳健。