An Optimal Transport Approach for Computing Adversarial Training Lower Bounds in Multiclass Classification
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910299755380736 |
|---|---|
| author | Trillos, Nicolas Garcia Jacobs, Matt Kim, Jakwang Werenski, Matthew |
| author_facet | Trillos, Nicolas Garcia Jacobs, Matt Kim, Jakwang Werenski, Matthew |
| contents | Despite the success of deep learning-based algorithms, it is widely known that neural networks may fail to be robust. A popular paradigm to enforce robustness is adversarial training (AT), however, this introduces many computational and theoretical difficulties. Recent works have developed a connection between AT in the multiclass classification setting and multimarginal optimal transport (MOT), unlocking a new set of tools to study this problem. In this paper, we leverage the MOT connection to propose computationally tractable numerical algorithms for computing universal lower bounds on the optimal adversarial risk and identifying optimal classifiers. We propose two main algorithms based on linear programming (LP) and entropic regularization (Sinkhorn). Our key insight is that one can harmlessly truncate the higher order interactions between classes, preventing the combinatorial run times typically encountered in MOT problems. We validate these results with experiments on MNIST and CIFAR-$10$, which demonstrate the tractability of our approach. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_09191 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An Optimal Transport Approach for Computing Adversarial Training Lower Bounds in Multiclass Classification Trillos, Nicolas Garcia Jacobs, Matt Kim, Jakwang Werenski, Matthew Machine Learning Optimization and Control Despite the success of deep learning-based algorithms, it is widely known that neural networks may fail to be robust. A popular paradigm to enforce robustness is adversarial training (AT), however, this introduces many computational and theoretical difficulties. Recent works have developed a connection between AT in the multiclass classification setting and multimarginal optimal transport (MOT), unlocking a new set of tools to study this problem. In this paper, we leverage the MOT connection to propose computationally tractable numerical algorithms for computing universal lower bounds on the optimal adversarial risk and identifying optimal classifiers. We propose two main algorithms based on linear programming (LP) and entropic regularization (Sinkhorn). Our key insight is that one can harmlessly truncate the higher order interactions between classes, preventing the combinatorial run times typically encountered in MOT problems. We validate these results with experiments on MNIST and CIFAR-$10$, which demonstrate the tractability of our approach. |
| title | An Optimal Transport Approach for Computing Adversarial Training Lower Bounds in Multiclass Classification |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2401.09191 |