Towards Understanding Generalization of Macro-AUC in Multi-label Learning

• URL: http://arxiv.org/abs/2305.05248v2
• Date: Fri, 2 Jun 2023 08:14:09 GMT
• Title: Towards Understanding Generalization of Macro-AUC in Multi-label Learning
• Authors: Guoqiang Wu, Chongxuan Li, Yilong Yin
• Abstract summary: We characterize the generalization properties of various learning algorithms based on Macro-AUC. We identify a critical factor of the dataset affecting the generalization bounds: emphthe label-wise class imbalance We propose a new (and more general) McDiarmid-type concentration inequality, which may be of independent interest.
• Score: 48.015768048227166
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Likelihood-based Differentiable Structure Learning [38.25218464260965]
  Existing approaches to differentiable structure learning of directed acyclic graphs (DAGs) rely on strong identifiability assumptions. We explain and remedy these issues by studying the behavior of differentiable acyclicity-constrained programs under general likelihoods.
  arXiv  Detail & Related papers  (2024-10-08T16:08:24Z)
• On Characterizing and Mitigating Imbalances in Multi-Instance Partial Label Learning [57.18649648182171]
  We make contributions towards addressing a problem that hasn't been studied so far in the context of MI-PLL. We derive class-specific risk bounds for MI-PLL, while making minimal assumptions. Our theory reveals a unique phenomenon: that $sigma$ can greatly impact learning imbalances.
  arXiv  Detail & Related papers  (2024-07-13T20:56:34Z)
• How does promoting the minority fraction affect generalization? A theoretical study of the one-hidden-layer neural network on group imbalance [64.1656365676171]
  Group imbalance has been a known problem in empirical risk minimization. This paper quantifies the impact of individual groups on the sample complexity, the convergence rate, and the average and group-level testing performance.
  arXiv  Detail & Related papers  (2024-03-12T04:38:05Z)
• A Unified Generalization Analysis of Re-Weighting and Logit-Adjustment for Imbalanced Learning [129.63326990812234]
  We propose a technique named data-dependent contraction to capture how modified losses handle different classes. On top of this technique, a fine-grained generalization bound is established for imbalanced learning, which helps reveal the mystery of re-weighting and logit-adjustment.
  arXiv  Detail & Related papers  (2023-10-07T09:15:08Z)
• Learning with Multiclass AUC: Theory and Algorithms [141.63211412386283]
  Area under the ROC curve (AUC) is a well-known ranking metric for problems such as imbalanced learning and recommender systems. In this paper, we start an early trial to consider the problem of learning multiclass scoring functions via optimizing multiclass AUC metrics.
  arXiv  Detail & Related papers  (2021-07-28T05:18:10Z)
• Rethinking and Reweighting the Univariate Losses for Multi-Label Ranking: Consistency and Generalization [44.73295800450414]
  (Partial) ranking loss is a commonly used evaluation measure for multi-label classification. There is a gap between existing theory and practice -- some pairwise losses can lead to promising performance but lack consistency.
  arXiv  Detail & Related papers  (2021-05-10T09:23:27Z)
• Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View [82.80085730891126]
  We provide the first modernally precise analysis of linear multiclass classification. Our analysis reveals that the classification accuracy is highly distribution-dependent. The insights gained may pave the way for a precise understanding of other classification algorithms.
  arXiv  Detail & Related papers  (2020-11-16T05:17:29Z)
• Robustifying Binary Classification to Adversarial Perturbation [45.347651499585055]
  In this paper we consider the problem of binary classification with adversarial perturbations. We introduce a generalization to the max-margin classifier which takes into account the power of the adversary in manipulating the data. Under some mild assumptions on the loss function, we theoretically show that the gradient descents converge to the RM classifier in its direction.
  arXiv  Detail & Related papers  (2020-10-29T07:20:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.