← Back to all news
arXiv Machine Learning

When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification

The paper investigates learning with monotone adversarial corruptions, extending previous binary classification results to multiclass and partial binary settings. It shows that even a small number of strategically inserted corrupted examples can render a learnable multiclass problem with DS dimension 2 completely unlearnable, and provides matching upper bounds when the adversary’s budget is sublinear. The work also demonstrates that classic error rates remain attainable under bounded or limited‑view adversaries.

Related stories

arXiv Machine Learning
Jun 25

Learning with Monotone Adversarial Corruptions

arXiv:2601. 02193v2 Announce Type: replace 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.

By Kasper Green Larsen, Chirag Pabbaraju, Abhishek Shetty
safety
More like this →
arXiv Machine Learning
Sep 25

Bandit Multiclass PAC Learning: Corrected Lower Bounds, Exact Families, and a Confidence Direct-Sum Phenomenon

The paper revisits realizable multiclass PAC learning with bandit feedback, correcting a previously claimed lower bound on sample complexity. It introduces a new anchored dimension, “aBDS,” and establishes a constant‑free three‑part lower bound, while also providing tighter upper bounds that eliminate dependence on the total label count. The authors demonstrate that the optimal sample complexity can vary dramatically even among classes with identical dimensional profiles, revealing a confidence direct‑sum phenomenon and a rank‑saturation phase transition.

By Guangjian Zhang
reinforcement-learning
More like this →
arXiv Machine Learning
Aug 12

Optimistic Rates for Multiclass PAC Learning

arXiv:2608. 10869v1 Announce Type: new Abstract: Worst-case multiclass bounds do not become smaller when the best classifier is already nearly correct: what is missing is an optimistic rate, a guarantee whose fluctuation scales with the oracle risk itself.

By Xiaoyu Li, Andi Han, Jiaojiao Jiang, Junbin Gao
More like this →
arXiv Machine Learning
Aug 28

Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper Learning

The paper investigates fundamental limits of algorithmic principles in multiclass learning, specifically proper learning and regularization. It shows that learning cannot always be reduced to proper learning even with an enlarged hypothesis class, that proper learners may need a sublinear number of errors that can be arbitrarily large, and that regularization (SRM or local) is not universally sufficient. The authors also provide a positive theory giving sufficient conditions for SRM learnability and a characterization via integrability of revealed preferences.

By Julian Asilis, Shaddin Dughmi, Vatsal Sharan, Alec Sun, Shang-Hua Teng, Chang Wang
More like this →
arXiv Machine Learning
Oct 3

Adaptive and oblivious statistical adversaries are equivalent

The paper resolves a key question in statistical learning under adversarial corruption by showing that sample‑adaptive and sample‑oblivious adversaries are equivalent up to polynomial factors in the sample size for all corruption types. It proves that any algorithm that succeeds against a sample‑oblivious adversary can be transformed into one that succeeds against the corresponding sample‑adaptive adversary by requesting a polynomially larger sample and running the original algorithm on a random subsample. The construction preserves computational efficiency and requires only a simple modification of the algorithm.

By Guy Blanc, Gregory Valiant
More like this →
arXiv Machine Learning
Jul 8

Boosting with List-Decodable Codes

arXiv:2607. 05791v1 Announce Type: cross Abstract: Boosting is a fundamental technique for generically improving the accuracy of learning algorithms (Schapire 1989).

By Addison Prairie, Li-Yang Tan
More like this →