Learning with Monotone Adversarial Corruptions

• URL: http://arxiv.org/abs/2601.02193v1
• Date: Mon, 05 Jan 2026 15:16:26 GMT
• Title: Learning with Monotone Adversarial Corruptions
• Authors: Kasper Green Larsen, Chirag Pabbaraju, Abhishek Shetty,
• Abstract summary: We study the extent to which standard machine learning algorithms rely on exchangeability and independence of data.<n>Our results showcase how optimal learning algorithms break down in the face of seemingly helpful monotone corruptions.
• Score: 28.071086916778842
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
  We show how to analyze the behavior of distributed gradient descent algorithms in the presence of adversarial corruptions.<n>We show how to use ideas from (lazy) mirror descent to design a corruption-tolerant distributed optimization algorithm.<n> Experiments based on linear regression, support vector classification, and softmax classification on the MNIST dataset corroborate our theoretical findings.
  arXiv  Detail & Related papers  (2024-07-19T08:29:12Z)
• Robust Online Covariance and Sparse Precision Estimation Under Arbitrary Data Corruption [1.5850859526672516]
  We introduce a modified trimmed-inner-product algorithm to robustly estimate the covariance in an online scenario. We provide the error-bound and convergence properties of the estimates to the true precision matrix under our algorithms.
  arXiv  Detail & Related papers  (2023-09-16T05:37:28Z)
• Correcting Underrepresentation and Intersectional Bias for Classification [49.1574468325115]
  We consider the problem of learning from data corrupted by underrepresentation bias. We show that with a small amount of unbiased data, we can efficiently estimate the group-wise drop-out rates. We show that our algorithm permits efficient learning for model classes of finite VC dimension.
  arXiv  Detail & Related papers  (2023-06-19T18:25:44Z)
• Neural Active Learning on Heteroskedastic Distributions [29.01776999862397]
  We demonstrate the catastrophic failure of active learning algorithms on heteroskedastic datasets. We propose a new algorithm that incorporates a model difference scoring function for each data point to filter out the noisy examples and sample clean examples.
  arXiv  Detail & Related papers  (2022-11-02T07:30:19Z)
• Fair Group-Shared Representations with Normalizing Flows [68.29997072804537]
  We develop a fair representation learning algorithm which is able to map individuals belonging to different groups in a single group. We show experimentally that our methodology is competitive with other fair representation learning algorithms.
  arXiv  Detail & Related papers  (2022-01-17T10:49:49Z)
• Sample Selection for Fair and Robust Training [28.94276265328868]
  We propose a sample selection-based algorithm for fair and robust training. We show that our algorithm obtains fairness and robustness better than or comparable to the state-of-the-art technique.
  arXiv  Detail & Related papers  (2021-10-27T07:17:29Z)
• Can Active Learning Preemptively Mitigate Fairness Issues? [66.84854430781097]
  dataset bias is one of the prevailing causes of unfairness in machine learning. We study whether models trained with uncertainty-based ALs are fairer in their decisions with respect to a protected class. We also explore the interaction of algorithmic fairness methods such as gradient reversal (GRAD) and BALD.
  arXiv  Detail & Related papers  (2021-04-14T14:20:22Z)
• Outlier-Robust Learning of Ising Models Under Dobrushin's Condition [57.89518300699042]
  We study the problem of learning Ising models satisfying Dobrushin's condition in the outlier-robust setting where a constant fraction of the samples are adversarially corrupted. Our main result is to provide the first computationally efficient robust learning algorithm for this problem with near-optimal error guarantees.
  arXiv  Detail & Related papers  (2021-02-03T18:00:57Z)
• Learning while Respecting Privacy and Robustness to Distributional Uncertainties and Adversarial Data [66.78671826743884]
  The distributionally robust optimization framework is considered for training a parametric model. The objective is to endow the trained model with robustness against adversarially manipulated input data. Proposed algorithms offer robustness with little overhead.
  arXiv  Detail & Related papers  (2020-07-07T18:25:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.