The Lazy Adversary: Data-Efficient Universal Perturbations for Tabular Classifiers via Coresets

Universal Adversarial Perturbations (UAPs) are single, input-agnostic perturbations that can induce misclassification in a frozen classifier. Gradient-based UAP methods, which frame the problem as loss maximization and solve it with the Fast Gradient Sign Method (FGSM) or Projected Gradient Descent (PGD) over the training set, have become the dominant approach due to their simplicity and effectiveness. However, these methods require aggregating gradients over the entire training set at every optimization epoch, making the per-epoch cost scale linearly with the dataset size. We observe that because the victim classifier is frozen, its penultimate feature embedding never changes. We propose UAPCore, which uses this frozen feature geometry as a practical proxy for gradient redundancy: before any gradient update, a coreset is selected in the feature space of the frozen victim model, and all subsequent UAP optimization is performed exclusively on that fixed subset. Whether this proxy preserves UAP quality is evaluated thoroughly with experiments across 44 tabular classification datasets from OpenML, which show that UAPCore with k-Center selection at only 10% of the training set recovers full-dataset fooling rates to within 2 percentage points on 72-91% of the datasets, while achieving a median wall-clock speedup of 8.5x under PGD. We further show that MLP-crafted coreset perturbations transfer to unseen tree-based and attention-based tabular architectures with fidelity comparable to full-data crafting.