Unveiling the Role of Randomization in Multiclass Adversarial Classification: Insights from Graph Theory

• URL: http://arxiv.org/abs/2503.14299v2
• Date: Thu, 12 Jun 2025 16:34:52 GMT
• Title: Unveiling the Role of Randomization in Multiclass Adversarial Classification: Insights from Graph Theory
• Abstract summary: We study the role of randomization in enhancing robustness to adversarial attacks in multiclass classification.<n>We find that switching from a deterministic to a randomized solution significantly reduces the optimal adversarial risk.<n>These findings highlight the crucial role randomization can play in enhancing robustness to adversarial attacks in multiclass classification.
• Score: 10.535721818998649
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Randomization as a mean to improve the adversarial robustness of machine learning models has recently attracted significant attention. Unfortunately, much of the theoretical analysis so far has focused on binary classification, providing only limited insights into the more complex multiclass setting. In this paper, we take a step toward closing this gap by drawing inspiration from the field of graph theory. Our analysis focuses on discrete data distributions, allowing us to cast the adversarial risk minimization problems within the well-established framework of set packing problems. By doing so, we are able to identify three structural conditions on the support of the data distribution that are necessary for randomization to improve robustness. Furthermore, we are able to construct several data distributions where (contrarily to binary classification) switching from a deterministic to a randomized solution significantly reduces the optimal adversarial risk. These findings highlight the crucial role randomization can play in enhancing robustness to adversarial attacks in multiclass classification.

Related papers

• Statistical Inference for Conditional Group Distributionally Robust Optimization with Cross-Entropy Loss [9.054486124506521]
  We study multi-source unsupervised domain adaptation, where labeled data are drawn from multiple source domains and only unlabeled data from a target domain.<n>We propose a novel Conditional Conditional Optimization (CG-DRO) framework that learns a classifier by minimizing the worst-case cross-entropy loss over the convex combinations of the conditional outcome distributions from the sources.<n>We establish fast statistical convergence rates for the estimator by constructing two surrogate minimax optimization problems that serve as theoretical bridges.
  arXiv  Detail & Related papers  (2025-07-14T04:21:23Z)
• Class-Conditional Distribution Balancing for Group Robust Classification [11.525201208566925]
  Spurious correlations that lead models to correct predictions for the wrong reasons pose a critical challenge for robust real-world generalization. We offer a novel perspective by reframing the spurious correlations as imbalances or mismatches in class-conditional distributions. We propose a simple yet effective robust learning method that eliminates the need for both bias annotations and predictions.
  arXiv  Detail & Related papers  (2025-04-24T07:15:53Z)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
  We analyze smoothed (perturbed) policies, adding controlled random perturbations to the direction used by the linear oracle.<n>Our main contribution is a generalization bound that decomposes the excess risk into perturbation bias, statistical estimation error, and optimization error.<n>We illustrate the scope of the results on applications such as vehicle scheduling, highlighting how smoothing enables both tractable training and controlled generalization.
  arXiv  Detail & Related papers  (2024-07-24T12:00:30Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions. We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• Distributionally Robust Skeleton Learning of Discrete Bayesian Networks [9.46389554092506]
  We consider the problem of learning the exact skeleton of general discrete Bayesian networks from potentially corrupted data. We propose to optimize the most adverse risk over a family of distributions within bounded Wasserstein distance or KL divergence to the empirical distribution. We present efficient algorithms and show the proposed methods are closely related to the standard regularized regression approach.
  arXiv  Detail & Related papers  (2023-11-10T15:33:19Z)
• Tackling Diverse Minorities in Imbalanced Classification [80.78227787608714]
  Imbalanced datasets are commonly observed in various real-world applications, presenting significant challenges in training classifiers. We propose generating synthetic samples iteratively by mixing data samples from both minority and majority classes. We demonstrate the effectiveness of our proposed framework through extensive experiments conducted on seven publicly available benchmark datasets.
  arXiv  Detail & Related papers  (2023-08-28T18:48:34Z)
• Decentralized Adversarial Training over Graphs [44.03711922549992]
  The vulnerability of machine learning models to adversarial attacks has been attracting attention in recent years.<n>We develop a decentralized adversarial framework for multiagent systems.
  arXiv  Detail & Related papers  (2023-03-23T15:05:16Z)
• Agnostic Multi-Robust Learning Using ERM [19.313739782029185]
  A fundamental problem in robust learning is asymmetry: a learner needs to correctly classify every one of exponentially-many perturbations that an adversary might make to a test-time natural example. In contrast, the attacker only needs to find one successful perturbation. We introduce a novel multi-group setting and introduce a novel multi-robust learning problem.
  arXiv  Detail & Related papers  (2023-03-15T21:30:14Z)
• Distributionally Robust Models with Parametric Likelihood Ratios [123.05074253513935]
  Three simple ideas allow us to train models with DRO using a broader class of parametric likelihood ratios. We find that models trained with the resulting parametric adversaries are consistently more robust to subpopulation shifts when compared to other DRO approaches.
  arXiv  Detail & Related papers  (2022-04-13T12:43:12Z)
• Examining and Combating Spurious Features under Distribution Shift [94.31956965507085]
  We define and analyze robust and spurious representations using the information-theoretic concept of minimal sufficient statistics. We prove that even when there is only bias of the input distribution, models can still pick up spurious features from their training data. Inspired by our analysis, we demonstrate that group DRO can fail when groups do not directly account for various spurious correlations.
  arXiv  Detail & Related papers  (2021-06-14T05:39:09Z)
• Beyond cross-entropy: learning highly separable feature distributions for robust and accurate classification [22.806324361016863]
  We propose a novel approach for training deep robust multiclass classifiers that provides adversarial robustness. We show that the regularization of the latent space based on our approach yields excellent classification accuracy.
  arXiv  Detail & Related papers  (2020-10-29T11:15:17Z)
• Learning while Respecting Privacy and Robustness to Distributional Uncertainties and Adversarial Data [66.78671826743884]
  The distributionally robust optimization framework is considered for training a parametric model. The objective is to endow the trained model with robustness against adversarially manipulated input data. Proposed algorithms offer robustness with little overhead.
  arXiv  Detail & Related papers  (2020-07-07T18:25:25Z)
• Provable tradeoffs in adversarially robust classification [96.48180210364893]
  We develop and leverage new tools, including recent breakthroughs from probability theory on robust isoperimetry. Our results reveal fundamental tradeoffs between standard and robust accuracy that grow when data is imbalanced.
  arXiv  Detail & Related papers  (2020-06-09T09:58:19Z)

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.