← Back to all news
arXiv Machine Learning

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.

Related stories

arXiv Machine Learning
Aug 24

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.

By Julian Asilis, Shaddin Dughmi, Chirag Pabbaraju
safety
More like this →
arXiv Machine Learning
Jun 29

Surprises in Proper Positive-Only Learning

arXiv:2606. 28309v1 Announce Type: cross Abstract: Binary classification from positive-only samples is a variant of PAC learning in which the learner receives i.

By Shai Ben-David, Farnam Mansouri, Anay Mehrotra, Manolis Zampetakis
More like this →
arXiv Machine Learning
Jul 7

A Hierarchy of Policy Learning Problems

arXiv:2607. 03385v1 Announce Type: cross Abstract: Policy learning has received substantial attention with the goal of learning policies from observational data for decision-making.

By Hamsa Bastani, Osbert Bastani, Shihan Chen
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 →
arXiv Machine Learning
Aug 11

Constrained Learning with Universally Learnable Concept Classes

arXiv:2608. 08414v1 Announce Type: new Abstract: We study constrained statistical learning over infinite-dimensional hypothesis classes in the fully nonconvex setting, and establish universal PACC learnability of the solutions of dual algorithms: Probably Approximately Correct on Constraints, guaranteeing optimality and constraint satisfaction at once.

By Herlock SeyedAbolfazl Rahimi, Spyridon Pougkakiotis, Dionysis Kalogerias
More like this →
arXiv Statistics ML
2d ago

Reconciling Universal and Uniform Learning with $Q$-Aggregation

The paper investigates regression with bounded responses, comparing two learning frameworks: model selection aggregation, which requires improper algorithms to achieve minimax excess risk, and universal learning, where empirical risk minimization suffices for exponential learning rates. For finite hypothesis classes, the authors show that the $Q$-aggregation estimator simultaneously attains minimax optimal tails and exponential universal rates, while other common estimators fail to do so. For countably infinite classes, they prove an inherent trade‑off between exponential universal and minimax uniform rates, resolved by combining optimal algorithms from each framework via $Q$-aggregation.

By Mikael M{\o}ller H{\o}gsgaard, Patrick Rebeschini, Tobias Wegel
efficiency
More like this →