PAC Learning

PAC: Probably Approximately Correct

Follow this topic Ask about this topic

Momentum

2 papers in the last four weeks, down 33% on the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 32

All topics

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.
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 +1Multiclass Classification 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
PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting
May 25, 2026Steve Hanneke, Qinglin Meng, Shay Moran +1Multiclass Classification Classification
Department of Computer Science Purdue University West Lafayette, IN, USA · Faculties of Mathematics, Computer Science, and Data and Decision Sciences Technion – Israel Institute of Technology and Google Research Haifa, Israel
Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers
May 18, 2026Rita Adhikari, Shiwei ZengMulticlass Classification Classification
Augusta University
What is Learnable in Valiant's Theory of the Learnable?
May 13, 2026Steve Hanneke, Anay Mehrotra, Grigoris Velegkas +1PAC Learning Statistical Learning Theory
Purdue University · Stanford University · Google Research +1
Strategic PAC Learnability via Geometric Definability
May 13, 2026Yuval Filmus, Shay Moran, Elizaveta Nesterova +2Strategic Classification PAC Learning
Faculty of Mathematics, Technion – Israel Institute of Technology. · Faculty of Computer Science, Technion – Israel Institute of Technology. · Faculty of Data and Decision Sciences, Technion – Israel Institute of Technology. +1
Teaching and Learning under Deductive Errors
May 13, 2026Jan Arne Telle, Brigt Håvardstun, Jose Hernandez-OralloParameterized Complexity PAC Learning
Department of Informatics University of Bergen Norway · VRAIN - Universitat Politecnica de Valencia Spain · Leverhulme Centre for the Future of Intelligence - University of Cambridge United Kingdom
High-arity Sample Compression
May 12, 2026Leonardo N. Coregliano, William OpichPAC Learning Statistical Learning Theory
Online Set Learning from Precision and Recall Feedback
May 10, 2026Lee Cohen, Yishay Mansour, Shay Moran +1PAC Learning Statistical Learning Theory
1Stanford University · 2Tel Aviv University and Google Research · 3Technion and Google Research +1
Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity
May 8, 2026Anastasis Kratsios, Gregory Cousins, Haitz Sáez de Ocáriz Borde +2Neural Network Generalization PAC Learning
Department of Mathematics & Statistics, McMaster University, Hamilton, ON, Canada · University of Cambridge, United Kingdom · Graduate School of Engineering, The University of Tokyo, Tokyo, Japan +1
Null Measurability at the Symmetrization Interface in VC Learning
Apr 27, 2026Dhruv GuptaPAC Learning Statistical Learning Theory
AI and Robotics Technology Park, Indian Institute of Science, Bengaluru
Tight Bounds for Learning Polyhedra with a Margin
Apr 16, 2026Shyamal Patel, Santosh VempalaPAC Learning Statistical Learning Theory
Columbia University · Georgia Tech
Relatively Smart: A New Approach for Instance-Optimal Learning
Mar 2, 2026Shaddin Dughmi, Alireza F. PourPAC Learning Semi-Supervised Learning
University of Southern California · University of Waterloo

Sep 21, 2026, stat.MLJ/K move · Enter open · S save

Adversarially Robust PAC Learning with Optimal VC Rates

Steve Hanneke, Amirreza Shaeiri

Department of Computer Sciences, Purdue University, USA.

Sample Complexity Adversarial Robustness PAC Learning Statistical Learning Theory

Open paper AskPDF arXiv

We study the problem of \emph{adversarially robust} PAC learning. In this framework, the learner observes independent samples from an unknown distribution over

\mathcal{X} \times \{0,1\}

, as in classical PAC learning. However, given a perturbation map

\mathcal{U} : \mathcal{X} \to 2^{\mathcal{X}}

known to the learner, the goal is to output, with high probability, a predictor that correctly classifies \emph{every} perturbation

z \in \mathcal{U}(x)

of most future examples

(x,y)

drawn from the same underlying distribution. We determine the \emph{optimal}

\mathcal{U}

-independent sample complexity of this problem in both the realizable and agnostic settings. More specifically, for every concept class

\mathcal{H}

\operatorname{VC}

dimension

d

, we prove upper bounds of

\mathcal{O} \big( d/ε+ \log(1/δ)/ε\big)

in the realizable setting and

\mathcal{O} \big( d/ε^2 + \log(1/δ)/ε^2 \big)

in the agnostic setting, together with an optimal first-order refinement of the latter. These bounds match the corresponding lower bounds for classical PAC learning. Consequently, and perhaps surprisingly, adversarial robustness incurs \emph{no additional} distribution-free statistical cost, uniformly over all perturbation maps. Our bounds improve exponentially on those of [Montasser, Hanneke, and Srebro; COLT '19]. On the technical side, we present short and elementary proofs based on a new algorithmic principle that we call \emph{binomial-bagging}. We believe that binomial-bagging and its analysis may be of independent interest.

Momentum

Related topics

Latest papers 32