Organizations: Department of Information Technology, Uppsala University, Uppsala, Sweden · Science for Life Laboratory, Uppsala University, Uppsala, Sweden
Abstract
Standard Importance Sampling (IS) collapses under label corruption because high-norm examples, prioritized for variance reduction, are often adversarial outliers. We formalize this misalignment using an ε-contamination model and propose Disagreement-Regularized Importance Sampling (DR-IS), a sub-sampling method based on loss rank-disagreement across independent proxy ensemble. We prove finite-sample concentration bounds showing that the empirical rank disagreement of bulk corrupted examples is bounded above, and that of boundary-clean examples bounded below, both at rate O(log(N/δ)/K) with probability 1−δ; when the structural expectation gap Δ′ between the two groups is positive and the boundary-clean set is at least as large as the selected subset, these bounds certify strict separation and control the contamination rate of the selected subset. Empirically, DR-IS remains robust under targeted high-norm attacks that break magnitude-based methods such as the Error L2-norm (EL2N) on benchmark datasets. DR-IS complements training-dynamics approaches like Area Under the Margin ranking (AUM), offering improved robustness in the loss-aligned regime alongside explicit finite-sample concentration certificates and a contamination bound limiting noise leakage from the statistical tail of corrupted points.
We study the extent to which standard machine learning algorithms rely on exchangeability and independence of data by introducing a monotone adversarial corruption model. In this model, an adversary, upon looking at a "clean" i.i.d. dataset, inserts additional "corrupted" points of their choice into the dataset. These added points are constrained to be monotone corruptions, in that they get labeled according to the ground-truth target function. Perhaps surprisingly, we demonstrate that in this setting, all known optimal learning algorithms for binary classification can be made to achieve suboptimal expected error on a new independent test point drawn from the same distribution as the clean dataset. On the other hand, we show that uniform convergence-based algorithms do not degrade in their guarantees. Our results showcase how optimal learning algorithms break down in the face of seemingly helpful monotone corruptions, exposing their overreliance on exchangeability.
Kasper Green Larsen, Chirag Pabbaraju, Abhishek Shetty
Engineered robust losses such as Huber, Student-t, and generalised cross-entropy make supervised models tolerant of contamination but cannot answer which observations are corrupted. We introduce Neural Bayesian Anomaly Mitigation (NBAM), a general-purpose drop-in loss derived from a Bayesian latent-switch mixture model: the marginal likelihood defines a robust supervised loss, and the associated posterior defines an unsupervised contamination classifier. Like Huber or Student-t, NBAM can replace the standard training loss in any supervised pipeline; unlike them, it additionally learns a structured contamination model and returns a calibrated per-sample contamination posterior. A learned input-dependent prior πφ(x) captures the spatial locality of contamination, so that samples near known corruptions are more likely to be flagged, while an Occam penalty emerges automatically and regularises against over-flagging. On CIFAR-10 with asymmetric label contamination, NBAM recovers the structure of the corruption process without supervision: the contamination posterior separates clean from corrupted samples, and the learned anomaly head identifies the direction of every label-flip pair. Alongside these capabilities, NBAM outperforms the four robust-loss baselines considered here at contamination rates 0.2-0.6.
S. A. K. Leeney, W. J. Handley, H. T. J. Bevins +1
This paper explores the use of linear aggregation to protect the privacy of sensitive training labels through the concept of \emph{label differential privacy} (label-DP) while maintaining regression task utility. Our key finding is that weighted linear aggregation of training instances with i.i.d. N(0,1) weights can achieve (ε,δ)-label-DP with m=O(n/(log(1/δ))). Unlike prior methods, our approach relies on the minimum linear regression loss rather than the minimum singular value of the data matrix, resulting in better practical bounds on real datasets. We also examine real-world mechanisms involving disjoint sets or \textit{bags} of instances. We demonstrate that aggregating labels from sub-sampled disjoint k-sized bags using i.i.d. N(0,1) weights achieves (ε,δ)-label-DP with k≥Ω(((1/ε)log(1/δ))2). In both scenarios, the optimal linear mse-regressor on the aggregated data approximates the original dataset's optimum with high probability, without needing additive label noise. Furthermore, we show that adding N(0,1) noise to any constant fraction of labels allows for similar label-DP guarantees when aggregating labels over random disjoint bags, while preserving the utility of Lipschitz-bounded neural mse-regression tasks.