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

Lucas Gnecco Heredia, Matteo Sammut, Muni Sreenivas Pydi, Rafael Pinot, Benjamin Negrevergne, Yann Chevaleyre
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:3682-3690, 2025.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v258-heredia25a, title = {Unveiling the Role of Randomization in Multiclass Adversarial Classification: Insights from Graph Theory}, author = {Heredia, Lucas Gnecco and Sammut, Matteo and Pydi, Muni Sreenivas and Pinot, Rafael and Negrevergne, Benjamin and Chevaleyre, Yann}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {3682--3690}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/heredia25a/heredia25a.pdf}, url = {https://proceedings.mlr.press/v258/heredia25a.html}, 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.} }
Endnote
%0 Conference Paper %T Unveiling the Role of Randomization in Multiclass Adversarial Classification: Insights from Graph Theory %A Lucas Gnecco Heredia %A Matteo Sammut %A Muni Sreenivas Pydi %A Rafael Pinot %A Benjamin Negrevergne %A Yann Chevaleyre %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-heredia25a %I PMLR %P 3682--3690 %U https://proceedings.mlr.press/v258/heredia25a.html %V 258 %X 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.
APA
Heredia, L.G., Sammut, M., Pydi, M.S., Pinot, R., Negrevergne, B. & Chevaleyre, Y.. (2025). Unveiling the Role of Randomization in Multiclass Adversarial Classification: Insights from Graph Theory. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:3682-3690 Available from https://proceedings.mlr.press/v258/heredia25a.html.

Related Material