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

Sep 21, 2026stat.ML

Adversarially Robust PAC Learning with Optimal VC Rates

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.

Steve Hanneke, Amirreza Shaeiri

Department of Computer Sciences, Purdue University, USA.

Sample Complexity Adversarial Robustness PAC Learning Statistical Learning Theory

Ask PDF

Sep 14, 2026cs.LG

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

We revisit Valiant's algorithm (Commun. ACM'84) for learning

n

-variable CNF formulas with clause size

k

and variable degree

d

from i.i.d. uniform random solutions in the local lemma regime. For fixed

t\geq1

, under

k\gtrsim(1+1/t)\log d

, Valiant's algorithm achieves total variation error

\varepsilon

with

\widetilde{O}(n^{\lceil t \rceil}/\varepsilon)

sample complexity. For

t>1

, we prove a matching lower bound for Valiant's algorithm. At

t=1

(covering

0<t<1

), we show Valiant's algorithm has optimal sample complexity up to logarithmic factors by an information-theoretic lower bound

\widetildeΩ(n/\varepsilon)

Weiming Feng, Yixiao Yu, Yiyao Zhang

School of Computing and Data Science, The University of Hong Kong. · State Key Laboratory for Novel Software Technology, New Cornerstone Science Laboratory, Nanjing University.

Boolean Function Learning Sample Complexity PAC Learning Information-Theoretic Lower Bounds

Ask PDF

Aug 31, 2026math.LO

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

The fundamental theorem of statistical learning states that, under suitable measurability assumptions, finite Vapnik--Chervonenkis (VC) dimension guarantees that every proper consistent learning rule is probably approximately correct (PAC). Blumer, Ehrenfeucht, Haussler, and Warmuth showed, assuming the Continuum Hypothesis, that the "well-behavedness" condition of the concept class cannot be omitted: they constructed a concept class of Borel sets of VC dimension one admitting a consistent learning rule that is not PAC. We show that the Continuum Hypothesis is unnecessary. Working in Zermelo--Fraenkel set theory with the Axiom of Choice (ZFC) alone, we construct a concept class of Borel sets on

[0,1]

of VC dimension one and a proper consistent learning rule that is not PAC. More precisely, for a suitable Borel probability measure and target concept, the rule has true risk one at every sample size on a set of samples of outer probability one. Consequently, finite VC dimension and Borel measurability of the individual concepts do not suffice to guarantee that every proper consistent learning rule is PAC. The result shows, with no need of extra set-theoretical assumptions, that the additional regularity assumption in the fundamental theorem cannot in general be omitted.

Mateus Jesus de Arruda Campos, Gabriel Fernandes, Vinicius de Oliveira Rodrigues

PAC Learning Statistical Learning Theory

Ask PDF

Aug 12, 2026quant-ph

A Quantum/Classical Example Oracle Separation for Making Things Up

Consider two PAC learning algorithms, both having access to quantum computation, but differing in the types of examples they obtain: one is provided with classical samples, while the other is given quantum samples. Are there any learning tasks that can be efficiently performed by the latter, but not by the former? This question, the focus of our work, is surprisingly still open. Our main result is to show that \emph{relative to an oracle}, there are distributions that can be efficiently generated by a quantum learner with access to quantum samples, but not by a quantum learner with access to only classical samples, making progress to answering this question in the affirmative.

Kenny Chen

The University of Sydney

Quantum Machine Learning PAC Learning

Ask PDF

Aug 11, 2026cs.LG

Optimistic Rates for Multiclass PAC Learning

Worst-case multiclass bounds do not become smaller when the best classifier is already nearly correct: what is missing is an optimistic rate, a guarantee whose fluctuation scales with the oracle risk itself. For a class of Natarajan dimension

d_N

and Daniely-Shalev-Shwartz dimension

d_{DS}

, the optimal excess risk is known at the two endpoints (

d_{DS}/n

realizable,

\sqrt{d_N/n}+d_{DS}/n

agnostic [HMZ24, CEH+26, Pab26]) and open in between. We close the gap: at every fixed oracle risk

L^\star

, the optimal excess risk is

\widetildeΘ(\sqrt{L^\star d_N/n}+d_{DS}/n)

, uniformly in the alphabet size, attained by a learner that knows neither

L^\star

nor the confidence level. The upper bound composes the cover-menu-compression architecture of [CEH+26], at the realizable rate of [Pab26], with a new comparator-facing relative compression theorem: a size-

k

compression rule that empirically dominates a comparator

h

has population risk at most

L(h)+O(\sqrt{L(h)Γ}+Γ)

with

Γ=(k\log n+\log(1/δ))/n

, without stability; this transfers the comparison principle of the sharp binary theory [MQZ26] while discarding its Boolean-cube geometry, which does not lift to multiclass labels. The lower bound forces both terms using one class and one distribution at every fixed

L^\star

, by a pair-Assouad scheme calibrated to

L^\star

and a fiber argument on the pseudo-cubes underlying the Natarajan-versus-DS separation of [BCD+22]. Both theorems extend to list learning: against the best

r

-tuple of hypotheses, the same architecture and the same two engines yield an optimistic rate and a lower bound of the same shape, forcing the fluctuation term that [Pab26] expected to be necessary against list comparators, and removing the factor

r

from the known realizable list lower bound.

Xiaoyu Li, Andi Han, Jiaojiao Jiang +1

University of New South Wales · University of Sydney

Multiclass Classification Classification PAC Learning Generalization Bounds

Ask PDF

Aug 9, 2026cs.LG

Optimal Learning Under Tsybakov Noise

Probably Approximately Correct (PAC) learning [Val84] is a fundamental learning model that has been extensively investigated. In this model,

\mathcal{H} \subseteq \{0,1\}^{\mathcal{X}}

is a concept class, and

h^*\in\mathcal{H}

is the target concept to be learned. Having access to i.i.d. labeled examples from a distribution

\mathcal{D}

over

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

, which admits

h^*

as the best concept in

\mathcal{H}

, the goal is to design a learning algorithm that outputs a hypothesis having low error competitive to

h^{*}

with high probability. This model was initially studied under the realizable setting, which assumes that

h^*

has no error. A natural relaxation is to allow label noise, that is, the true label can be flipped with probability

η\in(0,1/2)

. In reality, certain labels might be extremely noisy, especially for those points near the decision boundary. Hence, it is natural to allow very noisy points, though only rarely. This is quantified by a noise model introduced by [MT99] and [Tsy04], now known as Tsybakov noise. For learning general concept classes, [MN06] gave the general upper and lower bounds for error guarantees under Tsybakov noise. However, their upper and lower bounds differ by a logarithmic factor. Resolving this gap has remained a well-known open question for the past twenty years. In this work, we resolve this open question by improving the upper bound to match the best known lower bound, thus establishing the optimal error guarantee for learning under Tsybakov noise. Our learning algorithm operates by adaptively partitioning the instance space into regions, roughly corresponding to different noise levels, and returning a hypothesis in the concept class satisfying a specific error constraint for each region. Our technique shares a conceptual foundation with several recent advances in non-realizable learning, such as [HLZ24] and [Han25].

Steve Hanneke, Hongao Wang, Mingyue Xu

Department of Computer Science Purdue University

Noisy-Label Learning PAC Learning Statistical Learning Theory

Ask PDF

Aug 9, 2026cs.LG

Constrained Learning with Universally Learnable Concept Classes

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. This strengthens near-PACC results, whose feasibility residual no amount of data can remove. Optimality is caught between generalization, governed by Rademacher complexity and favoring small classes, and strong Lagrangian duality, which rests on Lyapunov convexity for vector measures and needs decomposability, a demand pulling the other way. We reconcile the two by posing the population problem over a universal RKHS

\mathcal{H}_K

, dense in a decomposable envelope, and learning over norm balls of growing radius. This yields the Tikhonov complexity

\mathfrak{T}^{\varepsilon}_{n}

, the least RKHS norm reaching an

\varepsilon

-optimal Lagrangian level set; we prove it finite, obtain exact learnability of the optimal value, and make the sample threshold explicit and polynomial in

1/\varepsilon

under a source condition. Feasibility is harder: absent convexity the Lagrangian may not attain its infimum, and dual information pins down only an averaged constraint-risk vector, not the risks of any returned predictor. We introduce the closure-realization gap

\varepsilon^\star_\infty

, an index of how well

\mathcal{H}_K

retrieves feasible solutions from dualization; it is a property of the problem, not of a modeling choice. Learnability is exact when

\varepsilon^\star_\infty=0

, in particular under dual differentiability, and near-PACC with residual exactly

\varepsilon^\star_\infty

otherwise. Finally, no distribution-free threshold exists already in the unconstrained specialization, so universality is the canonical frame for dual algorithms over large hypothesis classes.

Herlock SeyedAbolfazl Rahimi, Spyridon Pougkakiotis, Dionysis Kalogerias

1Yale University · 2King’s College London

Primal-Dual Optimization Reproducing Kernel Hilbert Spaces PAC Learning Statistical Learning Theory

Ask PDF

Aug 7, 2026cs.LG

Stochastic Autoregressive Learning

Motivated by LLMs, which generate outputs by iteratively sampling from next-token distributions, we introduce a PAC-learning model for binary stochastic autoregressive learning. This generalizes the deterministic autoregressive learning framework of Joshi et al., COLT 2025. In our model, one fixed generator assigns a Bernoulli next-token distribution to every prompt string. Starting from an input prompt, a token is sampled and appended to the prompt; the same generator is then applied again to this expanded prompt; this procedure is repeated for

M

steps. Three forms of supervision are considered: base one-step samples, chain-of-thought (CoT) samples that reveal full random trajectories of length

M

, and end-to-end (e2e) samples that reveal only the final token of length

M

trajectories. For a generator class, we study the minimum number of samples

m_{base}(\varepsilon),m_{CoT}(\varepsilon), m_{e2e}(\varepsilon)

, resp., required to learn the one-step probabilities in the base model, and the final-token probability in the CoT and e2e models, under squared loss error~

\varepsilon

. We show that stochastic autoregressive learning fundamentally differs from the deterministic theory. At scale

\varepsilon

, there is no universal comparison between the three learning tasks: both

m_{CoT}/m_{base}

and

m_{e2e}/m_{CoT}

can be made simultaneously arbitrarily larger than

M/\varepsilon

, the natural analogue for the existing deterministic results. Nevertheless, after altering scales, for every class, CoT learning at scale

\varepsilon

is upper-bounded by base learning at scale

\varepsilon/M^2

, whereas e2e learning at scale

\varepsilon

is upper-bounded, up to logarithmic factors, by

(M/\varepsilon) m_{CoT}(Θ(\varepsilon))

. These dependencies and scales are essentially tight. We complement these bounds by studying dimension

d

logistic functions in our model.

Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel

1MIT · 2The Hebrew University

Autoregressive Generation PAC Learning Autoregressive Modeling

Ask PDF

Aug 7, 2026cs.LG

A Rate Separation for Agnostic Direct Sums

Hanneke, Moran, and Waknine \cite{HannekeMoranWaknine2024} asked how the agnostic PAC learning curve of the direct sum

C^r

depends on the single-instance learning curve

\epsagn(n\mid C)

and on

r

. We show that the single-instance learning rate does not determine the direct-sum rate. Let

\F

be the class of the two constant binary functions and let

\G

consist of the zero function and the identity function. Both classes have agnostic learning curve of order

n^{-1/2}

Mihir More, Aritra Das, Debayan Gupta

Truth Audit Labs

PAC Learning Statistical Learning Theory

Ask PDF

Aug 6, 2026cs.LG

An Optimal Agnostic PAC Algorithm

Let

H\subseteq\{-1,+1\}^X

be a class of finite VC dimension

d\ge1

. Writing

L

for the binary risk and

L^*=\min_{h\in H}L(h)

, we construct a learner achieving the statistically optimal risk bound: from an i.i.d.\ sample of size

n

, for every

0<δ\le 1/2

, with probability at least

1-δ

L(\widehat h) \le L^*+ 7\cdot10^8\left( \sqrt{\frac{L^*(d+\log(1/δ))}{n}} +\frac{d+\log(1/δ)}{n} \right).

This settles the sample complexity of agnostic PAC learning up to universal constants at every fixed

L^*

, matching the lower bounds of Devroye, Györfi, and Lugosi [A Probabilistic Theory of Pattern Recognition, Springer, 1996].

Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy

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

PAC Learning Statistical Learning Theory Generalization Bounds

Ask PDF

Aug 5, 2026cs.LG

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

We study distributionally robust PAC learning for the

0

1

-loss, where adversarial perturbations of the data distribution are constrained by a Cressie--Read divergence of order

k>1

and radius

ρ\geq 0

. For hypothesis classes with VC dimension

d

, we establish realizable and agnostic sample-complexity bounds tight up to constant and logarithmic factors, respectively; ordinary empirical risk minimization attains both rates up to logarithmic factors. For target accuracy

\varepsilon\in(0,1)

and confidence

δ\in(0,1)

, their respective orders are

\max\!\left\{\frac{1}{\varepsilon}, \frac{ρ^{\frac 1{k-1}}}{\varepsilon^{k_\star}} \right\}\cdot(d+\log δ^{-1}) \qquad\text{and}\qquad \max\!\left\{\frac{1}{\varepsilon^2}, \frac{ρ^{\frac1{k-1}}}{\varepsilon^{k_\star\vee 2}} \right\}\cdot(d+\log δ^{-1}),

where

k_\star={k}/{(k-1)}

. For every fixed

ρ>0

, robustness changes the realizable

\varepsilon

-dependence from

\varepsilon^{-1}

\varepsilon^{-k_\star}

\varepsilon\downarrow0

. In the agnostic case, for

1<k<2

, robustness changes the

\varepsilon

-dependence from

\varepsilon^{-2}

\varepsilon^{-k_\star}

, whereas for

k\geq2

the exponent remains the classical

2

, with nontrivial

ρ

-dependence. Building on the known scalar reduction of robust

0

1

risk to ordinary classification error, our analysis reveals a scale-sensitive interaction between the statistical estimation of classification error and its amplification by robustness, sharply explaining the transition in the agnostic rate. We extend the previously studied

χ^2

-divergence case to every Cressie--Read order

k>1

, close its upper--lower gaps, and recover standard PAC learning rates as

ρ\to0

, unlike previous bounds that fail to interpolate correctly in this limit.

Elad Aigner-Horev, Daniel Rosenberg, Roi Weiss

School of Computer Science and AI Ariel University 40800 Ariel, Israel

Sample Complexity Distributionally Robust Optimization PAC Learning Statistical Learning Theory

Ask PDF

Jul 26, 2026cs.LG

Local Regularization Does Not Characterize Multiclass PAC Learnability

Local regularization assigns each hypothesis a test-point-dependent score and predicts with a minimum-score hypothesis consistent with the sample. Asilis et al. asked whether this principle characterizes multiclass PAC learnability. We give a negative answer. There is a countable class of Daniely--Shalev-Shwartz dimension at most two with realizable PAC sample complexity

O\!\left(\frac{1}{\varepsilon}\log\frac{1}δ\right),

that no local regularizer learns. Hypotheses are edges of complete graphs and instances are tournaments. At a test tournament, the scores fix an edge ranking while the training sample independently removes competitors. Cyclic triangles force enough inversions that surviving competitors produce constant population error at arbitrarily large sample sizes.

Eric Hou

Multiclass Classification Classification PAC Learning Statistical Learning Theory

Ask PDF

Jul 16, 2026cs.LG

PAC Learning in Turn-Based Stochastic Games with Reachability Objectives: A Decentralized Private Approach via Expected Conditional Distance

Reachability is the most fundamental logical objective, yet it is notoriously difficult to learn in reinforcement learning settings: even for Markov decision processes, PAC learning of reachability is impossible without additional assumptions. This difficulty also holds in turn-based stochastic games (TBSGs), where two adversarial players interact on a finite state space. In this work, we consider turn-based stochastic games with reachability objectives. For such settings, adversarial learning, in which players are adversarial even in the learning phase, is impossible. Therefore, the goal is to consider learning, in which both players learn the unknown model together. In this spirit, previous literature on PAC learning in TBSGs considers (a)~public information shared by both players; and (b)~centralized learning, which means that players share the same learning algorithm. In this work, our contribution is two-fold. First, we relax these strong assumptions and ensure learning: (i)~with private information not shared with the other player; and (ii)~decentralized learning where the players do not share the same learning algorithm. To the best of our knowledge, this work is the first positive result for decentralized and private information learning of TBSGs with reachability objectives. Second, we introduce a game-theoretic generalization of the Expected Conditional Distance (ECD) parameter, which measures the expected length of reaching the target set. We establish a polynomial-sample complexity bound with respect to the number of states, actions, ECD parameter, and inverses of error tolerance and failure probability.

Ali Asadi, Krishnendu Chatterjee, Pavol Kebis

Institute of Science and Technology Austria (ISTA), Austria

Reachability Analysis Decentralized Learning PAC Learning

Ask PDF

Jul 16, 2026cs.LG

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

Machine-learned predictions can speed up offline NP-hard optimization, but asking a predictor what to do amounts to asking it to solve the problem, and committing an unchecked prediction forfeits every worst-case guarantee. CASP (Certificate-Augmented Solution Pruning) instead asks which parts of the search space may be ignored, and accepts each answer only after a sound polynomial-time verifier has checked it, so correctness never depends on prediction quality. We develop the learning theory of this design. The verifier makes the induced loss class uniformly bounded, so certificate parameters are learnable from

\tilde O(\varepsilon^{-2}\log K)

samples (

K

the maximum instance size), whereas the unverified commitment class admits no distribution-free rate and, under cost spread

R

, none below

Ω(R/\varepsilon^2)

. Filtering noisy predictions by verifiable confidence dominates the standard min-combiner, with a margin we compute in closed form, and the prediction stays useful even given the LP, because it breaks ties on degenerate optimal faces, where every symmetric LP policy, meaning one whose commitments depend on the instance only through the verifiable confidence values, provably stalls. Experiments on five problems test the theory's quantitative predictions. With trained predictors, unverified pruning loses up to

26%

of the optimum under distribution shift, while the verified deployment of the same predictions loses nothing.

Haifeng Li, Mo Hai

School of Information, Central University of Finance and Economics Beijing 102206, China

Combinatorial Optimization Learning-Augmented Algorithms PAC Learning Approximation Algorithms Statistical Learning Theory

Ask PDF

Jul 9, 2026cs.LG

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

Large language models increasingly provide labels, evaluations, and feedback for tasks specified in natural language. When a specification admits multiple readings but the supervision channel does not reveal which is operative, additional labels reduce sampling error without resolving the resulting identification problem. We introduce Natural Language PAC (NL-PAC), a framework that uses a fixed model's thresholded decoding law to define admissible labels and candidate targets. The probability that multiple labels are admissible equals the diameter of the pointwise-admissible target class, and under target-blind supervision every learner incurs worst-case risk of at least half this diameter, at every sample size; the exact randomized minimax risk over this class is attained by a data-independent strategy. Finite-sample confidence bounds make these quantities certifiable from held-out unlabeled inputs. In a frozen Qwen~2.5--3B audit, one prespecified prompt yields a positive model-relative certificate, whereas a paraphrase and exact-rule controls yield zero. A held-out bridge audit finds that supplied candidate reading clauses fail the admissibility condition needed to transfer the certificate to coherent readings. The guarantee is specific to the audited model, prompt, threshold, and input distribution; extending it to human interpretations requires external validation.

Berkay Anahtarci

Department of Mathematical Engineering, Özyeğin University, Istanbul, Türkiye

LLM Evaluation Partial Identification PAC Learning Language Model Auditing

Ask PDF

Jul 8, 2026cs.LG

The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought

We prove that, in the realizable PAC setting, the sample complexity of exact-trace learning for full autoregressive Chain-of-Thought traces is upper bounded by the standard multiclass rate of the local next-token class, where this rate is governed by the Daniely--Shalev-Shwartz dimension. Under exact-trace loss, one wrong action makes the whole trace incorrect; nevertheless, for every stopping rule

\mathtt{halt}

and every pointwise

\mathtt{halt}

-halting local class

\mathrm{H}

n_{\mathrm{PAC}}^{\varepsilon,δ}(\operatorname{Roll}_{\mathtt{halt}}(\mathrm{H}))=O((\operatorname{DSdim}(\mathrm{H})+\log(1/δ))/\varepsilon)

, with no dependence on rollout length. The dependence on

\operatorname{DSdim}(\mathrm{H})

is worst-case optimal, since one-step stopping recovers ordinary multiclass learning of

\mathrm{H}

. The proof introduces parity dimension, a rollout-stable refinement of DS dimension based on even pseudo-cubes. It controls one-inclusion density via a low-coordinate spanning theorem on finite restrictions and, unlike DS dimension itself, does not increase under autoregressive rollout. We also show why this detour is necessary: DS dimension can increase under rollout.

Zhiyuan Li

Toyota Technological Institute at Chicago

CoT Reasoning PAC Learning Statistical Learning Theory

Ask PDF

Jun 26, 2026stat.ML

Surprises in Proper Positive-Only Learning

Binary classification from positive-only samples is a variant of PAC learning in which the learner receives i.i.d. samples from the positive region of an unknown target concept, but is evaluated under the original distribution (which places mass on both positive and negative regions). This model dates back to Natarajan [1987, STOC], and the characterization of improper learning is well-known -- it even appears in textbooks. The characterization of proper positive-only learning, however, has long remained open. In this work, we revisit and settle this question: a concept class is properly learnable from positive-only samples if and only if it has finite VC dimension and satisfies a new combinatorial condition, which we call uniform exterior separability. Together with several separation results, this characterization reveals a surprisingly rich landscape that differs sharply from standard PAC learning: proper and improper learning are separated, randomized and deterministic proper learning are separated, there are classes for which no ERM is a learner, and finite VC dimension does not suffice even for non-uniform learning. Along the way, we introduce new combinatorial dimensions that we believe can be of broader interest in learning theory.

Shai Ben-David, Farnam Mansouri, Anay Mehrotra +1

University of Waterloo and Vector Institute · Stanford University · Yale University

Binary Classification Classification PAC Learning Statistical Learning Theory

Ask PDF

Jun 11, 2026stat.ML

Majority-of-Three is Optimal

We give a short proof that the majority vote of three independent consistent classifiers is an optimal learner in the realizable PAC setting. This proves optimality for the simplest voting scheme, while simplifying both the algorithmic structure and the probabilistic analysis of previous voting learners, including the algorithm of S. Hanneke and the analysis of bagging by K. Green Larsen.

Divit Rawal, Nikita Zhivotovskiy

Department of Statistics, University of California, Berkeley.

Ensemble Learning Classification PAC Learning Majority Voting

Ask PDF

Jun 11, 2026cs.LG

Learning with Simulators: No Regret in a Computationally Bounded World

Understanding the minimal assumptions necessary for generalization is the fundamental question in learning theory. Unfortunately, most results rely heavily on independence (or some proxy thereof) of the data-generating process, while results for strongly dependent data are far more limited. Towards addressing this gap, we introduce the framework of simulatable processes, where the learner has access to a simulator that approximates the distribution generating the data (which may be an arbitrarily complex and dependent process). Surprisingly, given access to such a simulator, we show that we can recover the same learning guarantees as in the classical setting with independent data, namely, error bounds that depend on the VC dimension. Further, we use this framework to study the power of conditional sampling and show strict statistical and computational advantages in this setting. As a highlight of our framework, we exhibit a single algorithm that simultaneously learns any given VC class under all processes samplable in bounded polynomial time, with regret controlled by the time-bounded Kolmogorov complexity of the process. This provides a significant conceptual broadening of the classical PAC model.

Sasha Voitovych, Abhishek Shetty, Noah Golowich +1

MIT · Microsoft Research

PAC Learning Statistical Learning Theory

Ask PDF

May 25, 2026stat.ML

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting

We study the problem of multiclass PAC learning with bandit feedback in the realizable setting. In this framework, there is an unknown data distribution over an instance space

\mathcal{X}

and a label space

\mathcal{Y}

, as in classical multiclass PAC learning, but the learner does not observe the labels of the i.i.d. training examples. Instead, in each round, it receives an unlabeled instance, predicts its label, and receives bandit feedback indicating only whether the prediction is correct. Despite this restriction, the goal remains the same as in classical PAC learning. We provide a general characterization of the optimal sample complexity of this problem, sharp for every concept class up to logarithmic factors. Our characterization is based on a new combinatorial dimension, termed the bandit

\mathrm{DS}

dimension, defined via generalized combinatorial structures we call pseudo-boxes. These extend the pseudo-cubes underlying the

\mathrm{DS}

dimension by allowing a different number of neighbors in each coordinate. In contrast to the

\mathrm{DS}

dimension, which governs the full-information setting by counting the number of coordinates in the pseudo-cube, the bandit

\mathrm{DS}

dimension aggregates the number of neighbors across coordinates, leading to a characterization in which the sample complexity scales with the total number of neighbors. We also propose a general learning algorithm achieving the upper bound, based on an algorithmic principle called ListCascade, which connects bandit learning to list learning and may be of independent interest.

Steve Hanneke, Qinglin Meng, Shay Moran +1

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

Multiclass Classification Classification PAC Learning Statistical Learning Theory

Ask PDF

May 18, 2026cs.LG

Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers

Noise-tolerant PAC learning of linear models has been of central interests in machine learning community since the last century. In recent years, many computationally-efficient algorithms have been proposed for the problem of learning linear threshold functions under multiple noise models. Yet, when the problem is considered under multiclass learning settings, i.e. when the number of classes

k

is at least

3

, it is unknown whether there exist computationally-efficient PAC learning algorithms when the data sets are maliciously corrupted. In this paper, we consider that the marginal distribution is a mixture of bounded variance distributions and the data sets satisfy a margin condition at the same time. We show that there exists a computationally-efficient algorithm that PAC learns multiclass linear classifiers

\{h_w:x\mapsto \arg\max_{y\in[k]}w_y\cdot x, x\in \mathbb{R}^d, w\in\mathbb{R}^{kd}\}

using at most

O(k^2\cdot (d\log d+\log k))

samples even under a constant rate of nasty noise. Our algorithm consists of two main ingredients: a cluster-based pruning scheme and a standard multiclass hinge loss minimization program. Even in the special case of binary setting, i.e.

k=2

, our result is strictly stronger than all prior works.

Rita Adhikari, Shiwei Zeng

Augusta University

Multiclass Classification Classification Learning with Noisy Labels PAC Learning

Ask PDF

May 13, 2026stat.ML

What is Learnable in Valiant's Theory of the Learnable?

Valiant's 1984 paper is widely credited with introducing the PAC learning model, but it, in fact, introduced a different model: unlike PAC learning, the learner receives only positives, may issue membership queries, and must output a hypothesis with no false positives. Prior work characterized variants, including the case without queries. We revisit Valiant's original model and ask: Which classes are learnable in it? For every finite domain, including Valiant's Boolean-hypercube setting, we show that a class is learnable if and only if every realizable positive sample can be certified by a poly-size adaptive query-compression scheme. This is a new variant of sample compression where the learner certifies samples via a short interaction with the membership oracle. Our characterization shows that learnability in Valiant's model is strictly sandwiched between learnability in the PAC model and the variant of Valiant's model without membership queries. This is one of the rare cases where introducing membership queries changes the set of learnable classes, and not just the sample or computational complexity. Next, we study the natural extension of the model to arbitrary domains. While we do not obtain an exact characterization, our techniques readily generalize and show that the same strict sandwiching persists. Finally, we show that

d

-dimensional halfspaces, which are not learnable without queries, are learnable with queries: we give a

\mathrm{poly}(d) \tilde{O}(1/ε)

sample and

\mathrm{poly}(d) \mathrm{polylog}(1/ε)

query algorithm, and prove that at least

Ω(d)

samples or queries are necessary. To our knowledge, this is the first algorithm for halfspaces in Valiant's model. Together, these results uncover a surprisingly rich theory behind Valiant's original notion of learnability and introduce ideas that may be of independent interest in learning theory.

Steve Hanneke, Anay Mehrotra, Grigoris Velegkas +1

Purdue University · Stanford University · Google Research +1

PAC Learning Statistical Learning Theory

Ask PDF

May 13, 2026cs.LG

Strategic PAC Learnability via Geometric Definability

Strategic classification studies learning settings in which individuals can modify their features, at a cost, in order to influence the classifier's decision. A central question is how the sample complexity of the induced (strategic) hypothesis class depends on the complexities of the underlying hypothesis class and the cost structure governing feasible manipulations. Prior work has shown that in several natural settings, such as linear classifiers with norm costs, the induced complexity can be controlled. We begin by showing that such guarantees fail in general - even in simple cases: there exist hypothesis classes of VC dimension

1

on the real line such that, even under the simplest interval neighborhoods, the induced class has infinite VC dimension. Thus, strategic behavior can turn an easy learning problem into a non-learnable one. To overcome this, we introduce structure via a geometric definability assumption: both the hypothesis class and the cost-induced neighborhood relation can be defined by first-order formulas over

\mathbb{R}_{\mathtt{exp}}

. Intuitively, this means that hypotheses and costs can be described using arithmetic operations, exponentiation, logarithms, and comparisons. This captures a broad range of natural classes and cost functions, including

\ell_p

distances, Wasserstein distance, and information-theoretic divergences. Under this assumption, we prove that learnability is preserved, with sample complexity controlled by the complexity of the defining formulas.

Yuval Filmus, Shay Moran, Elizaveta Nesterova +2

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

Strategic Classification PAC Learning Statistical Learning Theory

Ask PDF

May 13, 2026cs.LG

Teaching and Learning under Deductive Errors

Most models of machine teaching and learning assume the learner makes no errors in its internal deductive inference. However, humans and large language models in few-shot learning regimes are two important examples of learners where this does not hold. They fail on some consistency checks, and they can fail stochastically. In this paper we introduce a teaching and learning framework that takes these deductive errors into account. We specifically study the case of machine teaching, as different characterizations of the teacher can account for both machine teaching and learning. In an overhauled Probably Approximately Correct (PAC) setting, we study theoretically that, for some estimated error level, the teacher must find a PAC teaching set that with high probability will lead the learner to guess a hypothesis that is approximately correct. We study the computational complexity of six different problems related to computing optimal PAC teaching sets. We give XP algorithms parametrized by size of teaching set, with tight runtime bounds under standard complexity assumptions like ETH. These results are complemented with a small experimental study of which teaching and learning protocols can best represent the observed behavior in some LLM teaching sessions.

Jan Arne Telle, Brigt Håvardstun, Jose Hernandez-Orallo

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

Parameterized Complexity PAC Learning Teacher-Student Learning

Ask PDF

May 12, 2026cs.LG

High-arity Sample Compression

Recently, a series of works have started studying variations of concepts from learning theory for product spaces, which can be collected under the name high-arity learning theory. In this work, we consider a high-arity variant of sample compression schemes and we prove that the existence of a high-arity sample compression scheme of non-trivial quality implies high-arity PAC learnability.

Leonardo N. Coregliano, William Opich

PAC Learning Statistical Learning Theory

Ask PDF

May 10, 2026cs.LG

Online Set Learning from Precision and Recall Feedback

We consider the problem of learning an unknown subset

N_\text{target}

of a domain in an online setting. In each round

t

, the learner predicts a set of items

{N}_t

and receives one of two types of feedback, each with equal probability: precision feedback, in which a randomly chosen item from the predicted set

N_t

is revealed and the learner is told whether it belongs to

N_\text{target}

(incurring a reward if it does), or recall feedback, in which a randomly chosen item from the target set

N_\text{target}

is revealed and the learner is told whether it belongs to

N_t

(incurring a reward if it does). The goal is to maximize the cumulative reward over time. This simple online set learning problem abstracts a variety of learning scenarios with precision- and recall-type feedback. We show that a hypothesis class (a family of subsets of the domain) is learnable in this setting if and only if it has finite Vapnik-Chervonenkis (VC) dimension, mirroring the classical PAC characterization. However, the resulting algorithmic structure is markedly more intricate: in contrast to standard Probably Approximately Correct (PAC) learning -- where the algorithmic landscape is governed by the simple principle of Empirical Risk Minimization (ERM) -- our partial feedback model can invalidate ERM and even all proper learning rules. We develop algorithms to address the dependencies induced by the feedback, obtaining regret guarantees in both the realizable and agnostic settings. Our results provide a qualitative characterization of learnability in this model, addressing its most basic question, while pointing to a range of natural and intriguing open questions, including the determination of optimal regret rates.

Lee Cohen, Yishay Mansour, Shay Moran +1

1Stanford University · 2Tel Aviv University and Google Research · 3Technion and Google Research +1

PAC Learning Statistical Learning Theory Online Learning

Ask PDF

May 8, 2026stat.ML

Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity

We show that, in a precise sense, a broad class of feedforward neural networks learn (have finite sample complexity) in the PAC model: every fixed finite feedforward architecture whose layers are definable in an o-minimal structure has finite sample complexity in the agnostic PAC setting, even with unbounded parameters. This covers standard fixed-size MLPs, CNNs, GNNs, and transformers with fixed sequence length, together with the operations and layers typically used in such architectures, including linear projections, residual connections, attention mechanisms, pooling layers, normalization layers, and admissible positional encodings. Hence, distribution-free learnability for modern non-recurrent architectures is not an exceptional property of particular activations or architecture-specific VC arguments, but a consequence of tame feedforward computation. Our results reposition finite-sample PAC learnability as a baseline rather than a differentiator: they shift the focus of architectural comparison toward inductive biases, symmetries and geometric priors, scalability, and optimization behaviour.

Anastasis Kratsios, Gregory Cousins, Haitz Sáez de Ocáriz Borde +2

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

Neural Network Generalization PAC Learning Feedforward Neural Networks

Ask PDF

Apr 27, 2026cs.LG

Null Measurability at the Symmetrization Interface in VC Learning

Recent work revisiting measurability in the fundamental theorem of statistical learning imposes Borel measurability of ghost-gap suprema. We show that, at the one-sided ghost-gap interface actually used by the standard symmetrization proof, this requirement is stronger than necessary. For any Borel-parameterized concept class on a Polish domain, the bad event "there exists a hypothesis whose ghost empirical error exceeds its training empirical error by at least ε/2" is analytic. By Choquet capacitability, it is therefore measurable in the completion of every finite Borel measure. We then construct a concept class whose bad event is null-measurable but not Borel, giving a strict separation from the Borel supremum condition. Finally, we prove closure under patching, fixed and countable interpolation, and fiber-product amalgamation, showing that the weaker regularity level is stable under natural concept-class constructors. In the realizable setting, where targets belong to the class and are measurable, these results weaken the measurability hypothesis needed by the symmetrization route from finite VC dimension to PAC learnability. The main results and the descriptive-set-theoretic infrastructure used by them are formalized in Lean 4.

Dhruv Gupta

AI and Robotics Technology Park, Indian Institute of Science, Bengaluru

PAC Learning Statistical Learning Theory

Ask PDF

Apr 16, 2026cs.DS

Tight Bounds for Learning Polyhedra with a Margin

We give an algorithm for PAC learning intersections of

k

halfspaces with a

ρ

margin to within error

\varepsilon

that runs in time

\textsf{poly}(k, \varepsilon^{-1}, ρ^{-1}) \cdot \exp \left(O(\sqrt{n \log(1/ρ) \log k})\right)

. Notably, this improves on prior work which had an exponential dependence on either

k

ρ^{-1}

and matches known cryptographic and Statistical Query lower bounds up to the logarithmic factors in

k

and

ρ

in the exponent. Our learning algorithm extends to the more general setting when we are only promised that most points have distance at least

ρ

from the boundary of the polyhedron, making it applicable to continuous distributions as well.

Shyamal Patel, Santosh Vempala

Columbia University · Georgia Tech

PAC Learning Statistical Learning Theory

Ask PDF

Mar 2, 2026cs.LG

Relatively Smart: A New Approach for Instance-Optimal Learning

We revisit the framework of Smart PAC learning, which seeks supervised learners which compete with semi-supervised learners that are provided full knowledge of the marginal distribution on unlabeled data. Prior work has shown that such marginal-by-marginal guarantees are possible for "most" marginals, with respect to an arbitrary fixed and known measure, but not more generally. We discover that this failure can be attributed to an "indistinguishability" phenomenon: There are marginals which cannot be statistically distinguished from other marginals that require different learning approaches. In such settings, semi-supervised learning cannot certify its guarantees from unlabeled data, rendering them arguably non-actionable. We propose relatively smart learning, a new framework which demands that a supervised learner compete only with the best "certifiable" semi-supervised guarantee. We show that such modest relaxation suffices to bypass the impossibility results from prior work. In the distribution-free setting, we show that the One-Inclusion Graph learner is relatively smart up to squaring the sample complexity, and show that no supervised learning algorithm can do better. For distribution-family settings, we show that relatively smart learning can be impossible or can require idiosyncratic learning approaches, and its difficulty can be non-monotone in the inclusion order on distribution families.

Shaddin Dughmi, Alireza F. Pour

University of Southern California · University of Waterloo

PAC Learning Semi-Supervised Learning Statistical Learning Theory

Ask PDF

Momentum

Related topics

Latest papers 32