CS Paper Radar

Optimistic Rates for Multiclass PAC Learning

Xiaoyu Li, Andi Han, Jiaojiao Jiang, Junbin Gao

cs.LG stat.ML ·submitted 2026-08-11 12:46 UTC · v1
theorycode/data

Abstract

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.

Comment
The main theorems are machine-checked in Lean 4; Section D records what is verified and in which form, and the development is available at https://github.com/xiaoyulics/multiclass-pac-learning

Closest papers

Nearest neighbours by meaning across the whole index.

The Sample Complexity of Multicalibration with an ERM Oracle

cs.LG cs.DScs.GT ·2026-10-09 ·Princewill Okoroafor
hot direction similarity 0.67
Abstract · 58 pages

A predictor is multicalibrated with respect to a class of subpopulations (formally, of functions on the inputs, called auditors) if, for every subpopulation in the class and every value the predictor outputs, the average outcome among the members of that subpopulation who receive that value is close to the value itself. For finite classes, about $\varepsilon^{-3}$ samples are necessary and sufficient to learn a predictor with multicalibration error $\varepsilon$, but the algorithms that attain this rate enumerate the class, which is impossible for the large classes of interest. We ask how many samples suffice when the learner accesses the class only through an empirical risk minimization (ERM) oracle. We give an algorithm that uses $\tilde{O}(d/\varepsilon^{3})$ samples and polynomially many ERM calls, where $d$ is the VC dimension of the class. Its dependence on $\varepsilon$ is optimal for all learners. When $d$ is at least about $1/\varepsilon$, every learner that can only access the class through polynomially many ERM calls needs $\tildeΩ(d/\varepsilon^{3})$ samples. Learners with unlimited computation need only $\tilde{O}(\varepsilon^{-3}+d\varepsilon^{-2})$ samples, so the extra factor $1/\varepsilon$ on the dimension term is the price of oracle efficiency. For swap multicalibration, which allows a different function from the class for each predicted value, $\tildeΘ(d/\varepsilon^{3})$ samples are necessary and sufficient. For estimating the error of a given predictor, the ordinary notion is the harder one: the swap error can be estimated with an ERM oracle, whereas the ordinary error is NP-hard to approximate even for classes with linear-time ERM. Consequently, there are classes for which it is computationally easier to learn a multicalibrated predictor than to compute the multicalibration error of a given predictor.

0.57

Adversarially Robust PAC Learning with Optimal VC Rates

cs.LG stat.MLmath.ST ·2026-09-21 ·Steve Hanneke, Amirreza Shaeiri
theory similarity 0.66
Abstract · 35 pages, 2 figures

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}$ of $\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.

0.17

Bandit Multiclass PAC Learning: Structural Baselines and a Confidence Direct Sum

cs.LG ·2026-08-31 ·Guangjian Zhang, Zhengyi Yang, Xiaoyang Wang
theory similarity 0.66
Abstract · 48 pages

How much does high confidence cost when a multiclass learner sees only whether its prediction is correct? We separate two behaviors in realizable bandit PAC learning. An anchored dimension gives a general lower bound that is attained, up to universal constants, by a family of product-block classes. In contrast, for $n\ge16$ divisible by four, an affine multiplexer with bandit DS dimension $2n-1$ has sample complexity $Θ((n\min\{n,\ln(1/δ)\}+\ln(1/δ))/\varepsilon)$ in the standard accuracy and confidence regime. Its lower bound applies to adaptive randomized learners with improper outputs. The obstruction is that evidence collected against one candidate group cannot be reused against the others. The better of two algorithms matches this cost. One finds the correct group through a positive response. The other exhausts the rank of successive groups. The resulting confidence profile rules out a universal additive-confidence bound linear in the bandit DS dimension. Moreover, classes with identical anchored dimension, bandit DS dimension, and pointwise label width can have polynomially different sample complexities. We also sharpen the confidence accounting in ListCascade and show how one positive response replaces the bandit DS dimension by the anchored dimension in a general upper bound.

0.14

Adversarial Online Classification with a Preview

cs.LG cs.DS ·2026-08-30 ·Roi Livni, Sahil Singla
similarity 0.66
Abstract

Worst-case online classification is governed by sequential complexity, such as Littlestone dimension, and can be impossible even for statistically simple classes, such as thresholds of VC dimension one. We study a preview model in which an oblivious adversary fixes an entire labeled sequence of length $T$, a uniformly random subset of size $pT$ is revealed before prediction begins, and the remaining $(1-p)T$ examples are then presented in their original adversarial order. Against the best full-sequence hypothesis evaluated on the unrevealed examples, we characterize the dependence on the preview rate $p$: for binary classes of VC dimension $d$, the optimal excess loss is $Θ(d/p+\sqrt{dT})$, up to the trivial cap at $T$; for multiclass classes we obtain the corresponding $\widetilde O(d_{\rm DS}/p+\sqrt{d_{\rm Nat}T})$ bound with no dependence on the number of labels. Thus a random preview can replace worst-case sequential complexity by classical statistical dimensions without randomizing the online order. To achieve the sharp binary bound, our ChainedPrediction algorithm uses an online analogue of chaining, implemented as a multiscale aggregation algorithm rather than only as an analytic argument.

0.16

When Does More Correct Data Hurt? Insertion-Stability and the Limits of Dimension-Based Theory

cs.LG stat.ML ·2026-08-14 ·Joseph Sankoorikal Johny
theory similarity 0.64
Abstract · 13 pages, 1 figure

Adding data known to be correct ought to be safe. Not always. Larsen, Pabbaraju and Shetty model the failure with a monotone adversary, which reads an i.i.d. training sample and may append as many further examples as it likes, provided the target hypothesis labels them all. Mehrotra has since settled the cost, showing that for classes of VC dimension d >= 2 no learner can guarantee expected error better than Theta((d/n)log(en/d)), a logarithmic factor above the clean PAC rate. Because that rate is a worst case over all classes, it says nothing about which classes actually suffer the penalty, and the answer turns on the learner. We call a learner insertion-stable if feeding it more correctly labeled examples can only shrink the region where it errs. Such learners are immune to the adversary, since on any given sample the risk after insertions never exceeds the risk on the clean part alone, however much is added and however cleverly it is chosen. High- probability guarantees carry over unchanged, and because Closure is insertion-stable every intersection-closed class keeps its clean rate of E[Err] <= (21d+34)/n. Immunity is not something the classical dimensions can predict. Two classes can agree on VCdim = Ldim = 2 and still split, one at Theta(1/n) and the other at Theta(log(en)/n), while intervals have unbounded Littlestone dimension and are immune anyway. On Mehrotra's hard class we prove more than the failure of a single algorithm, showing that no monotone permutation-invariant compression scheme of any finite size attains the clean rate. The question is therefore not whether a class is hard, nor whether a learner is good, but whether the two suit each other. Given an insertion-stable learner that is optimal on clean data, correct additions are free, and without one the cost belongs to the class, so changing the learner will not avoid it.

0.10

Near-Optimal Sample Complexity of Deterministic Agnostic PAC Learning

cs.LG stat.ML ·2026-11-09 ·Shai Ben-David, Steve Hanneke, Farnam Mansouri, Amirreza Shaeiri
theory similarity 0.64
Abstract

We study the problem of agnostic PAC learning under deterministic labels, where the examples are labeled by an arbitrary deterministic function, which need not belong to the concept class $C$. This model captures misspecification without stochastic label noise and lies between the realizable and fully agnostic settings. Prior work showed that, when $C$ has finite diameter $K$ and VC dimension $d$, deterministic labels can improve the sample complexity upper bound from the classical agnostic guarantee $O(d/\varepsilon^2)$ to $\widetilde{O}(K/\varepsilon)$, but left a large gap between upper and lower bounds. Our main result sharpens this picture. We prove that every class of VC dimension $d$ and finite diameter $K$ is learnable with sample complexity $\widetilde{O}\left( \frac{K^{1/3} \, d^{2/3}}{\varepsilon} \right)$, and we construct classes for which this bound is tight up to logarithmic factors. We also study the online analogue of this problem and show that the minimax regret is again partly controlled by the diameter of the class. Technically, our upper bounds are obtained via memorization-based learning algorithms that exploit the deterministic label structure.

0.07

PAC Learning with Query Feedback

cs.LG ·2026-10-16 ·Chase Hutton, Adam Melrod, Han Shao
theory similarity 0.64
Abstract

We study realizable multiclass PAC learning with query feedback, where each training example provides a single binary response indicating whether its true label belongs to a chosen subset from a fixed query family. Our main contribution is the query dimension, a combinatorial parameter that captures both the structure of the hypothesis class and the ability of the available queries to distinguish labels. This parameter generalizes the bandit DS dimension, which it recovers under singleton queries. We establish a sample-complexity lower bound of $Ω(D/\varepsilon)$ and an upper bound of $\widetilde{O}(D^2/\varepsilon)$, suppressing factors polylogarithmic in the number of labels and the failure probability. When the available queries can split every candidate set into two parts of comparable size, we improve the upper bound to $\widetilde{O}(D/\varepsilon)$, yielding a characterization up to logarithmic factors.

0.19

New Lower Bounds for Private PAC Learning

cs.LG ·2026-10-30 ·Prathamesh Dharangutte, Amartya Sanyal
theory similarity 0.63
Abstract

We study realizable PAC learning under approximate differential privacy, and give a framework for proving lower bounds on its sample complexity. We construct classes with identical VC and Littlestone dimensions but different private sample complexities at common privacy and accuracy parameters, showing that these dimensions do not determine the sample complexity, even for improper learners. To address this we introduce the Independent Class Packing (ICP) parameter, the largest total sample complexity of classes in $\mathcal{G}$ that can be packed independently into a class $\mathcal{H}$, and prove that every $(\varepsilon, δ)$-DP, $(α, β)$-PAC learner for $\mathcal{H}$, possibly improper, uses $Ω\left(\mathrm{ICP}(\mathcal{H}, \mathcal{G})/(α\varepsilon)\right)$ examples. Using this framework we prove tight lower bounds for axis-aligned rectangles, union of intervals and linear subspaces and improved lower bounds for halfspaces and convex polygons. Finally we also show that for product classes, and more generally when the same classes pack into $\mathcal{H}$ and cover its domain so that target labels can be used directly, ICP characterizes private PAC sample complexity up to logarithmic factors.

0.03