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

• Balancing the Scales: A Theoretical and Algorithmic Framework for Learning from Imbalanced Data [35.03888101803088]
  This paper introduces a novel theoretical framework for analyzing generalization in imbalanced classification. We propose a new class-imbalanced margin loss function for both binary and multi-class settings, prove its strong $H$-consistency, and derive corresponding learning guarantees. We devise novel and general learning algorithms, IMMAX, which incorporate confidence margins and are applicable to various hypothesis sets.
  arXiv  Detail & Related papers  (2025-02-14T18:57:16Z)
• Of Dice and Games: A Theory of Generalized Boosting [61.752303337418475]
  We extend the celebrated theory of boosting to incorporate both cost-sensitive and multi-objective losses. We develop a comprehensive theory of cost-sensitive and multi-objective boosting, providing a taxonomy of weak learning guarantees. Our characterization relies on a geometric interpretation of boosting, revealing a surprising equivalence between cost-sensitive and multi-objective losses.
  arXiv  Detail & Related papers  (2024-12-11T01:38:32Z)
• Markov Equivalence and Consistency in 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)
• 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)
• 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.