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
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
The paper extends the study of relatively smart learning, showing that ERM and any proper consistent learner are relatively smart for binary classification in the distribution‑free setting, achieving a quadratic sample‑complexity blowup. It further demonstrates that semi‑supervised relatively smart learning is possible with only a quadratic blowup in unlabeled data and no blowup in labeled data, though this requires a leave‑most‑out transductive approach and incurs intractability when only an agnostic ERM oracle is available. The results clarify the trade‑offs between sample efficiency, label efficiency, and computational tractability in relatively smart learning.
By Shaddin Dughmi, Alireza F. Pour
arXiv:2511. 02644v2 Announce Type: replace Abstract: We study computable probably approximately correct (CPAC) learning, where learners are required to be computable functions.
By David Kattermann, Lothar Sebastian Krapp
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
The paper introduces a statistical learning theory for size generalization in models that handle variable-size structured data such as sets and graphs. It proves an exponential separation in sample complexity: polynomial in-domain learning yields only logarithmic decay in size-generalization error, while an exponential source condition restores polynomial decay. These results provide dimension‑free scaling laws and optimal minimax bounds for transferring learning across input sizes.
By Behrooz Tahmasebi, Melanie Weber
The paper presents a near-complete, nonasymptotic generalization theory for multilayer neural networks using path regularization, applicable to broad Lipschitz loss functions without requiring bounded loss or extreme network hyperparameters. It provides an explicit upper bound that addresses approximation rates in generalized Barron spaces and demonstrates the double descent phenomenon for ReLU networks. The authors claim near-minimax optimality for regression problems and plan to establish matching lower bounds in future work.
By Hao Yu
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
arXiv:2608.30246v1 Announce Type: cross
Abstract: The fundamental theorem of statistical learning states that, under suitable measurability assumptions, finite Vapnik--Chervonenkis (VC) dimension gua...
By Mateus Jesus de Arruda Campos, Gabriel Fernandes, Vinicius de Oliveira Rodrigues
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
arXiv:2608. 06337v1 Announce Type: cross Abstract: A monotone adversary observes an i.
By Anay Mehrotra
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