PAC Learning

PAC: Probably Approximately Correct

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

46 papers9 papers in the last four weeks, up 125% on the four weeks before. 0.1% of all new papers.

Rural Readiness: Domain Generalization with Adversarially Chosen Domains
Oct 29, 2026Cynthia Dwork, Andisheh Ghasemi, Lunjia HuDomain Generalization Cross-Domain Generalization
Harvard University · Northeastern University
Alignment via Generalization
Oct 25, 2026Shai Shalev-Shwartz, Amnon ShashuaAI Alignment PAC Learning
Learning Positive Linear Combinations of ReLUs in Fully Polynomial Time
Oct 23, 2026Ilias Diakonikolas, Jelena Diakonikolas, Puqian Wang +1PAC Learning ReLU Neural Networks
UW Madison · CSAIL, MIT
Near-Optimal List Replicability from Littlestone Dimension
Oct 23, 2026Ari Blondal, Pooya Hatami, Chavdar Lalov +1PAC Learning
McGill University · Ohio State University
Combinatorial Characterizations of the Learnability of Conditional Distributions
Oct 22, 2026Mihir Dhanakshirur, Ambuj TewariPAC Learning Statistical Learning Theory
University of Michigan
Strictly Replicable Realizable Learning: Unknown Marginals, Finite-Class Interpolation, and the Cost of Shared Randomness
Oct 18, 2026Guangjian ZhangSample Complexity Statistical Learning Theory
PAC Learning with Query Feedback
Oct 16, 2026Chase Hutton, Adam Melrod, Han ShaoPAC Learning Multiclass Classification
University of Maryland · Harvard University
Nearly Linear Private Learning of Littlestone Classes
Oct 16, 2026Shay Moran, Chao YanDifferential Privacy PAC Learning
Departments of Mathematics, Computer Science, and Data and Decision Sciences, Technion – Israel Institute of Technology; Google Research. · Department of Mathematics, Technion – Israel Institute of Technology.
Delay Complexity Dimension: Learning with Delayed and Censored Labels
Oct 13, 2026Madhava GaikwadPAC Learning
Independent Researcher
The optimal information complexity of VC learning
Oct 6, 2026Steve Hanneke, Juexiao WangStatistical Learning Theory Information-Theoretic Generalization Bounds
Department of Computer Science, Purdue University
Adversarially Robust PAC Learning with Optimal VC Rates
Sep 21, 2026Steve Hanneke, Amirreza ShaeiriSample Complexity Adversarial Robustness
Department of Computer Sciences, Purdue University, USA.
Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm
Sep 14, 2026Weiming Feng, Yixiao Yu, Yiyao ZhangBoolean Function Learning Sample Complexity
School of Computing and Data Science, The University of Hong Kong. · State Key Laboratory for Novel Software Technology, New Cornerstone Science Laboratory, Nanjing University.
Bandit Multiclass PAC Learning: Structural Baselines and a Confidence Direct Sum
Aug 31, 2026Guangjian Zhang, Zhengyi Yang, Xiaoyang WangPAC Learning Statistical Learning Theory
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 Learning Statistical Learning Theory
A Quantum/Classical Example Oracle Separation for Making Things Up
Aug 12, 2026Kenny ChenQuantum Machine Learning PAC Learning
The University of Sydney
Optimistic Rates for Multiclass PAC Learning
Aug 11, 2026Xiaoyu Li, Andi Han, Jiaojiao Jiang +1Sample Compression Multiclass Classification
University of New South Wales · University of Sydney
Optimal Learning Under Tsybakov Noise
Aug 9, 2026Steve Hanneke, Hongao Wang, Mingyue XuNoisy-Label Learning PAC Learning
Department of Computer Science Purdue University
Constrained Learning with Universally Learnable Concept Classes
Aug 9, 2026Herlock SeyedAbolfazl Rahimi, Spyridon Pougkakiotis, Dionysis KalogeriasPrimal-Dual Optimization Reproducing Kernel Hilbert Spaces
1Yale University · 2King’s College London
Stochastic Autoregressive Learning
Aug 7, 2026Ilan Doron-Arad, Idan Mehalel, Elchanan MosselAutoregressive Generation PAC Learning
1MIT · 2The Hebrew University
A Rate Separation for Agnostic Direct Sums
Aug 7, 2026Mihir More, Aritra Das, Debayan GuptaPAC Learning Statistical Learning Theory
Truth Audit Labs
An Optimal Agnostic PAC Algorithm
Aug 6, 2026Markus Engelund Mathiasen, Jian Qian, Nikita ZhivotovskiyPAC Learning Statistical Learning Theory
Department of Computer Science, Aarhus University · Division of Artificial Intelligence and Data Science, School of Computing and Data Science, The University of Hong Kong · Department of Statistics, University of California, Berkeley
The Sample Complexity of Distributionally Robust PAC Learning under Cressie--Read Divergences
Aug 5, 2026Elad Aigner-Horev, Daniel Rosenberg, Roi WeissSample Complexity Distributionally Robust Optimization
School of Computer Science and AI Ariel University 40800 Ariel, Israel
Local Regularization Does Not Characterize Multiclass PAC Learnability
Jul 26, 2026Eric HouMulticlass Classification Classification
PAC Learning in Turn-Based Stochastic Games with Reachability Objectives: A Decentralized Private Approach via Expected Conditional Distance
Jul 16, 2026Ali Asadi, Krishnendu Chatterjee, Pavol KebisReachability Analysis Decentralized Learning
Institute of Science and Technology Austria (ISTA), Austria
CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees
Jul 16, 2026Haifeng Li, Mo HaiCombinatorial Optimization Learning-Augmented Algorithms
School of Information, Central University of Finance and Economics Beijing 102206, China
NL-PAC: Specification Ambiguity and Certified Minimax Risk Floors in LLM-Mediated Supervision
Jul 9, 2026Berkay AnahtarciLLM Evaluation Partial Identification
Department of Mathematical Engineering, Özyeğin University, Istanbul, Türkiye
The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought
Jul 8, 2026Zhiyuan LiCoT Reasoning PAC Learning
Toyota Technological Institute at Chicago
Surprises in Proper Positive-Only Learning
Jun 26, 2026Shai Ben-David, Farnam Mansouri, Anay Mehrotra +1Binary Classification Classification
University of Waterloo and Vector Institute · Stanford University · Yale University
Majority-of-Three is Optimal
Jun 11, 2026Divit Rawal, Nikita ZhivotovskiyEnsemble Learning Classification
Department of Statistics, University of California, Berkeley.
Learning with Simulators: No Regret in a Computationally Bounded World
Jun 11, 2026Sasha Voitovych, Abhishek Shetty, Noah Golowich +1PAC Learning Statistical Learning Theory
MIT · Microsoft Research

Oct 29, 2026J/K move · Enter open · S save

Rural Readiness: Domain Generalization with Adversarially Chosen Domains

Cynthia Dwork, Andisheh Ghasemi, Lunjia Hu

Harvard University · Northeastern University

Domain Generalization Cross-Domain Generalization PAC Learning

Open paper AskPDF arXiv

Predictive models trained at well-resourced data-rich institutions often fail when deployed in new populations. Motivated by the goal of building clinical diagnosis and decision-making algorithms for data-scarce rural populations using the general knowledge learned from data-rich hospitals, we formulate the fundamental question of domain generalization with adversarially chosen domains, which asks a learner to perform on any unseen target domain nearly as well as the worst hypothesis consistent with the evidence from the observed source domains. Assuming only that the hypothesis class contains a "universal" predictor with small error on all

k

source domains, we characterize the sample complexity of this objective up to logarithmic factors. Letting

d

denote the VC dimension of the hypothesis class, we find, somewhat surprisingly, that the sample complexity reduces significantly from

Ω(dk)

O(d)

under a small relaxation of the learning goal in which, roughly speaking, we allow the learned model to compete with hypotheses that perform well on 99% instead of 100% of the source domains. By applying this insight to the meta-distributional setting, in which source domains are selected according to a distribution on distributions, we obtain a corresponding improvement over known sample complexity upper bounds. We also study the effect of data access to the target domain and show that a small labeled sample from the target domain does not improve the worst-case sample complexity on the source domains.