PAC Learning

PAC: Probably Approximately Correct

Overview

PAC learning asks how many labeled examples are needed to find a predictor whose error is small with high probability, both when the target is in the hypothesis class and when it is not. VC dimension, empirical risk minimization, sample compression, and online-learning ideas provide core tools for deriving sample-complexity bounds. Current work extends these guarantees to settings with noise, adversarial perturbations, bandit or positive-only feedback, delayed labels, and computational or physical limits on data access. Many classical rates are well understood, but a central tension is that familiar complexity measures may not capture learnability once feedback, properness, measurability, or distributional assumptions change.

Latest papers

CardsList

51 papers8 papers in the last four weeks, up 33% on the four weeks before. 0.1% of all new papers.

  1. Monoculture Robust Learning

    Nov 18, 2026Lee Cohen, Jon Kleinberg, Omer ReingoldStatistical Learning TheoryPAC Learning

  2. Near-Optimal Sample Complexity of Deterministic Agnostic PAC Learning

    Nov 9, 2026Shai Ben-David, Steve Hanneke, Farnam Mansouri +1Agnostic LearningPAC Learning

  3. PAC Learning with Multiple Correct Answers

    Nov 3, 2026Steve Hanneke, Farnam Mansouri, Alireza F. Pour +2PAC LearningStatistical Learning Theory

  4. New Lower Bounds for Private PAC Learning

    Oct 30, 2026Prathamesh Dharangutte, Amartya SanyalPAC LearningDifferential Privacy

  5. Rural Readiness: Domain Generalization with Adversarially Chosen Domains

    Oct 29, 2026Cynthia Dwork, Andisheh Ghasemi, Lunjia HuDomain GeneralizationCross-Domain Generalization

  6. Alignment via Generalization

    Oct 25, 2026Shai Shalev-Shwartz, Amnon ShashuaAI AlignmentPAC Learning

  7. Learning Positive Linear Combinations of ReLUs in Fully Polynomial Time

    Oct 23, 2026Ilias Diakonikolas, Jelena Diakonikolas, Puqian Wang +1PAC LearningReLU Neural Networks

  8. Near-Optimal List Replicability from Littlestone Dimension

    Oct 23, 2026Ari Blondal, Pooya Hatami, Chavdar Lalov +1PAC Learning

  9. PAC Learning with Query Feedback

    Oct 16, 2026Chase Hutton, Adam Melrod, Han ShaoPAC LearningMulticlass Classification

  10. Nearly Linear Private Learning of Littlestone Classes

    Oct 16, 2026Shay Moran, Chao YanDifferential PrivacyPAC Learning

  11. The optimal information complexity of VC learning

    Oct 6, 2026Steve Hanneke, Juexiao WangStatistical Learning TheoryInformation-Theoretic Generalization Bounds

  12. Adversarially Robust PAC Learning with Optimal VC Rates

    Sep 21, 2026Steve Hanneke, Amirreza ShaeiriSample ComplexityAdversarial Robustness

  13. Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm

    Sep 14, 2026Weiming Feng, Yixiao Yu, Yiyao ZhangBoolean Function LearningSample Complexity

  14. A Borel Concept Class of VC Dimension One with a Non-PAC Consistent Learner in ZFC

    Aug 31, 2026Mateus Jesus de Arruda Campos, Gabriel Fernandes, Vinicius de Oliveira RodriguesPAC LearningStatistical Learning Theory

  15. Optimistic Rates for Multiclass PAC Learning

    Aug 11, 2026Xiaoyu Li, Andi Han, Jiaojiao Jiang +1Sample CompressionMulticlass Classification

  16. Optimal Learning Under Tsybakov Noise

    Aug 9, 2026Steve Hanneke, Hongao Wang, Mingyue XuNoisy-Label LearningPAC Learning

  17. Constrained Learning with Universally Learnable Concept Classes

    Aug 9, 2026Herlock SeyedAbolfazl Rahimi, Spyridon Pougkakiotis, Dionysis KalogeriasPrimal-Dual OptimizationReproducing Kernel Hilbert Spaces

  18. Stochastic Autoregressive Learning

    Aug 7, 2026Ilan Doron-Arad, Idan Mehalel, Elchanan MosselAutoregressive GenerationPAC Learning

  19. A Rate Separation for Agnostic Direct Sums

    Aug 7, 2026Mihir More, Aritra Das, Debayan GuptaPAC LearningStatistical Learning Theory

  20. An Optimal Agnostic PAC Algorithm

    Aug 6, 2026Markus Engelund Mathiasen, Jian Qian, Nikita ZhivotovskiyPAC LearningStatistical Learning Theory

  21. The Sample Complexity of Distributionally Robust PAC Learning under Cressie--Read Divergences

    Aug 5, 2026Elad Aigner-Horev, Daniel Rosenberg, Roi WeissSample ComplexityDistributionally Robust Optimization

  22. CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees

    Jul 16, 2026Haifeng Li, Mo HaiCombinatorial OptimizationLearning-Augmented Algorithms

  23. NL-PAC: Specification Ambiguity and Certified Minimax Risk Floors in LLM-Mediated Supervision

    Jul 9, 2026Berkay AnahtarciLLM EvaluationPartial Identification