The Multimarginal Optimal Transport Formulation of Adversarial Multiclass Classification

• URL: http://arxiv.org/abs/2204.12676v3
• Date: Fri, 26 May 2023 13:56:01 GMT
• Title: The Multimarginal Optimal Transport Formulation of Adversarial Multiclass Classification
• Authors: Nicolas Garcia Trillos, Matt Jacobs, Jakwang Kim
• Abstract summary: We show a rich geometric structure of adversarial learning problems in multiclass classification. A direct computational implication of our results is that by solving either the barycenter problem and its dual, or the MOT problem and its dual, we can recover the optimal robust classification rule.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a family of adversarial multiclass classification problems and provide equivalent reformulations in terms of: 1) a family of generalized barycenter problems introduced in the paper and 2) a family of multimarginal optimal transport problems where the number of marginals is equal to the number of classes in the original classification problem. These new theoretical results reveal a rich geometric structure of adversarial learning problems in multiclass classification and extend recent results restricted to the binary classification setting. A direct computational implication of our results is that by solving either the barycenter problem and its dual, or the MOT problem and its dual, we can recover the optimal robust classification rule and the optimal adversarial strategy for the original adversarial problem. Examples with synthetic and real data illustrate our results.

Related papers

• The Multiplex Classification Framework: optimizing multi-label classifiers through problem transformation, ontology engineering, and model ensembling [0.0]
  This paper introduces the Multiplex Classification Framework. The framework offers several advantages, including adaptability to any number of classes and logical constraints. Two experiments were conducted to compare the performance of conventional classification models with the Multiplex approach.
  arXiv  Detail & Related papers  (2024-12-18T20:07:27Z)
• Genetic Column Generation for Computing Lower Bounds for Adversarial Classification [0.0]
  We investigate how ideas from Genetic Column Generation can be used to overcome the curse of dimension in computing the minimal adversarial risk in multi-class classification. In this paper we show that ideas from Genetic Column Generation can be used to overcome the curse of dimension in computing the minimal adversarial risk in multi-class classification.
  arXiv  Detail & Related papers  (2024-06-12T15:34:42Z)
• Balanced Classification: A Unified Framework for Long-Tailed Object Detection [74.94216414011326]
  Conventional detectors suffer from performance degradation when dealing with long-tailed data due to a classification bias towards the majority head categories. We introduce a unified framework called BAlanced CLassification (BACL), which enables adaptive rectification of inequalities caused by disparities in category distribution. BACL consistently achieves performance improvements across various datasets with different backbones and architectures.
  arXiv  Detail & Related papers  (2023-08-04T09:11:07Z)
• Synergies between Disentanglement and Sparsity: Generalization and Identifiability in Multi-Task Learning [79.83792914684985]
  We prove a new identifiability result that provides conditions under which maximally sparse base-predictors yield disentangled representations. Motivated by this theoretical result, we propose a practical approach to learn disentangled representations based on a sparsity-promoting bi-level optimization problem.
  arXiv  Detail & Related papers  (2022-11-26T21:02:09Z)
• Multi-class Classification with Fuzzy-feature Observations: Theory and Algorithms [36.810603503167755]
  We propose a novel framework to address a new realistic problem called multi-class classification with imprecise observations (MCIMO) First, we give the theoretical analysis of the MCIMO problem based on fuzzy Rademacher complexity. Then, two practical algorithms based on support vector machine and neural networks are constructed to solve the proposed new problem.
  arXiv  Detail & Related papers  (2022-06-09T07:14:00Z)
• 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)
• Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions [79.35722941720734]
  Generalised linear models for multi-class classification problems are one of the fundamental building blocks of modern machine learning tasks. We prove exacts characterising the estimator in high-dimensions via empirical risk minimisation. We discuss how our theory can be applied beyond the scope of synthetic data.
  arXiv  Detail & Related papers  (2021-06-07T16:53:56Z)
• 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)
• Pairwise Supervision Can Provably Elicit a Decision Boundary [84.58020117487898]
  Similarity learning is a problem to elicit useful representations by predicting the relationship between a pair of patterns. We show that similarity learning is capable of solving binary classification by directly eliciting a decision boundary.
  arXiv  Detail & Related papers  (2020-06-11T05:35:16Z)
• Nonlinear classifiers for ranking problems based on kernelized SVM [0.0]
  Many classification problems focus on maximizing the performance only on the samples with the highest relevance instead of all samples. In this paper, we derive a general framework including several classes of these linear classification problems. We dualize the problems, add kernels and propose a componentwise dual ascent method.
  arXiv  Detail & Related papers  (2020-02-26T12:37:11Z)

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.