The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination

• URL: http://arxiv.org/abs/2505.20177v1
• Date: Mon, 26 May 2025 16:17:48 GMT
• Title: The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination
• Authors: Adam R. Klivans, Konstantinos Stavropoulos, Kevin Tian, Arsen Vasilyan,
• Abstract summary: We show that any function class that can be approximated by low-degrees can be efficiently learned under bounded contamination.<n>We obtain the first efficient algorithms for tolerant testable learning of functions of halfspaces with respect to any fixed log-concave distribution.
• Score: 13.980910832909906
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Inspired by recent work on learning with distribution shift, we give a general outlier removal algorithm called iterative polynomial filtering and show a number of striking applications for supervised learning with contamination: (1) We show that any function class that can be approximated by low-degree polynomials with respect to a hypercontractive distribution can be efficiently learned under bounded contamination (also known as nasty noise). This is a surprising resolution to a longstanding gap between the complexity of agnostic learning and learning with contamination, as it was widely believed that low-degree approximators only implied tolerance to label noise. (2) For any function class that admits the (stronger) notion of sandwiching approximators, we obtain near-optimal learning guarantees even with respect to heavy additive contamination, where far more than $1/2$ of the training set may be added adversarially. Prior related work held only for regression and in a list-decodable setting. (3) We obtain the first efficient algorithms for tolerant testable learning of functions of halfspaces with respect to any fixed log-concave distribution. Even the non-tolerant case for a single halfspace in this setting had remained open. These results significantly advance our understanding of efficient supervised learning under contamination, a setting that has been much less studied than its unsupervised counterpart.

Related papers

• A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube [26.777025730534756]
  We give the first fully-time algorithm for learning halfspaces with respect to the uniform distribution on the hypercube.<n>We achieve an error guarantee of $etaO(1)+epsilon$ where $eta$ is the noise rate.<n>More generally, our framework shows that supervised learning with respect to discrete distributions is not as difficult as previously thought.
  arXiv  Detail & Related papers  (2025-11-10T15:58:41Z)
• Sample Compression for Self Certified Continual Learning [4.354838732412981]
  Continual learning algorithms aim to learn from a sequence of tasks, making the training distribution non-stationary.<n>We present a new method called Continual Pick-to-Learn (CoP2L), which is able to retain the most representative samples for each task in an efficient way.
  arXiv  Detail & Related papers  (2025-03-13T16:05:56Z)
• Probably Approximately Precision and Recall Learning [60.00180898830079]
  A key challenge in machine learning is the prevalence of one-sided feedback.<n>We introduce a Probably Approximately Correct (PAC) framework in which hypotheses are set functions that map each input to a set of labels.<n>We develop new algorithms that learn from positive data alone, achieving optimal sample complexity in the realizable case.
  arXiv  Detail & Related papers  (2024-11-20T04:21:07Z)
• Efficient Discrepancy Testing for Learning with Distribution Shift [17.472049019016524]
  We provide the first set of provably efficient algorithms for testing localized discrepancy distance. Results imply a broad set of new, efficient learning algorithms in the recently introduced model of Testable Learning with Distribution Shift.
  arXiv  Detail & Related papers  (2024-06-13T17:51:10Z)
• Tolerant Algorithms for Learning with Arbitrary Covariate Shift [18.37181965815327]
  We study the problem of learning under arbitrary distribution shift, where the learner is trained on a labeled set from one distribution but evaluated on a different, potentially adversarially generated test distribution. We focus on two frameworks: PQ learning [Goldwasser, A. Kalai, Y. Kalai, Montasser NeurIPS 2020], allowing abstention on adversarially generated parts of the test distribution, and TDS learning [Klivans, Stavropoulos, Vasilyan COLT 2024], permitting abstention on the entire test distribution if distribution shift is detected.
  arXiv  Detail & Related papers  (2024-06-04T19:50:05Z)
• Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
  Longtailed distributions frequently emerge in real-world data, where a large number of minority categories contain a limited number of samples. Recent investigations have revealed that supervised contrastive learning exhibits promising potential in alleviating the data imbalance. We propose a novel probabilistic contrastive (ProCo) learning algorithm that estimates the data distribution of the samples from each class in the feature space.
  arXiv  Detail & Related papers  (2024-03-11T13:44:49Z)
• Collaborative Learning with Different Labeling Functions [7.228285747845779]
  We study a variant of Collaborative PAC Learning, in which we aim to learn an accurate classifier for each of the $n$ data distributions. We show that, when the data distributions satisfy a weaker realizability assumption, sample-efficient learning is still feasible.
  arXiv  Detail & Related papers  (2024-02-16T04:32:22Z)
• Shrinking Class Space for Enhanced Certainty in Semi-Supervised Learning [59.44422468242455]
  We propose a novel method dubbed ShrinkMatch to learn uncertain samples. For each uncertain sample, it adaptively seeks a shrunk class space, which merely contains the original top-1 class. We then impose a consistency regularization between a pair of strongly and weakly augmented samples in the shrunk space to strive for discriminative representations.
  arXiv  Detail & Related papers  (2023-08-13T14:05:24Z)
• Sparse Mean Estimation in Adversarial Settings via Incremental Learning [20.522038784234947]
  We propose a scalable method to learn sparse mean estimation in the presence of heavy-tailed distributions and adversarial corruptions.<n>Our method achieves the optimal statistical rate, matching the information-theoretic lower bound.<n>More broadly, our work is the first to reveal the incremental learning phenomenon of the subient method in the presence of heavy-tailed distributions and adversarial corruption.
  arXiv  Detail & Related papers  (2023-05-24T16:02:28Z)
• Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise [9.76321513479048]
  We establish maximal concentration bounds for the iterates generated by an approximation (SA) under a contractive operator. We consider two settings where the iterates are potentially unbounded: SA with bounded multiplicative noise and SA with sub-Gaussian additive noise.
  arXiv  Detail & Related papers  (2023-03-28T05:32:30Z)
• Hierarchical Semi-Supervised Contrastive Learning for Contamination-Resistant Anomaly Detection [81.07346419422605]
  Anomaly detection aims at identifying deviant samples from the normal data distribution. Contrastive learning has provided a successful way to sample representation that enables effective discrimination on anomalies. We propose a novel hierarchical semi-supervised contrastive learning framework, for contamination-resistant anomaly detection.
  arXiv  Detail & Related papers  (2022-07-24T18:49:26Z)
• Chaos is a Ladder: A New Theoretical Understanding of Contrastive Learning via Augmentation Overlap [64.60460828425502]
  We propose a new guarantee on the downstream performance of contrastive learning. Our new theory hinges on the insight that the support of different intra-class samples will become more overlapped under aggressive data augmentations. We propose an unsupervised model selection metric ARC that aligns well with downstream accuracy.
  arXiv  Detail & Related papers  (2022-03-25T05:36:26Z)
• A Boosting Approach to Reinforcement Learning [59.46285581748018]
  We study efficient algorithms for reinforcement learning in decision processes whose complexity is independent of the number of states. We give an efficient algorithm that is capable of improving the accuracy of such weak learning methods.
  arXiv  Detail & Related papers  (2021-08-22T16:00:45Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)

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.