Lower Bounds on Adversarial Robustness for Multiclass Classification with General Loss Functions
This work addresses the challenge of designing robust classifiers beyond the 0-1 loss setting, providing theoretical and computational tools for adversarial risk assessment in multiclass scenarios, though it is incremental in extending existing results.
The paper tackles the problem of computing adversarial robustness for multiclass classification under arbitrary loss functions by deriving dual and barycentric reformulations of robust risk minimization, enabling efficient computation of sharp lower bounds and tighter results for cases like cross-entropy loss.
We consider adversarially robust classification in a multiclass setting under arbitrary loss functions and derive dual and barycentric reformulations of the corresponding learner-agnostic robust risk minimization problem. We provide explicit characterizations for important cases such as the cross-entropy loss, loss functions with a power form, and the quadratic loss, extending in this way available results for the 0-1 loss. These reformulations enable efficient computation of sharp lower bounds for adversarial risks and facilitate the design of robust classifiers beyond the 0-1 loss setting. Our paper uncovers interesting connections between adversarial robustness, $α$-fair packing problems, and generalized barycenter problems for arbitrary positive measures where Kullback-Leibler and Tsallis entropies are used as penalties. Our theoretical results are accompanied with illustrative numerical experiments where we obtain tighter lower bounds for adversarial risks with the cross-entropy loss function.