CS Paper Radar

Near-Optimal List Replicability from Littlestone Dimension

Ari Blondal, Pooya Hatami, Chavdar Lalov, Sivan Tretiak

cs.LG ·submitted 2026-10-23 16:25 UTC · v1
theory

Abstract

We study the list replicability number in the realizable PAC learning framework and prove that every concept class $H$ over a countable domain with Littlestone dimension $d$ and dual VC dimension $v^*$ satisfies \[ \mathrm{LR}(H)\leq 2^{O(d\min\{\log d,v^*\})}. \] This matches the worst-case lower bound of $2^{Ω(d)}$ up to a logarithmic factor in the exponent and exponentially improves the previous best upper bound $\mathrm{LR}(H)\le 2^{2^{O(d)}}$ of Bun, Livni, and Moran [FOCS 2020]. Unlike earlier bounds of $2^{O_ε(d^2)}$ for fixed accuracy $ε>0$ implied by the work of Ghazi, Golowich, Kumar, and Manurangsi [STOC 2021] and Lyu [STOC 2026], our bound is independent of $ε$. The $2^{O(d\log d)}$ bound follows from a new inductive framework for bounding list replicability that builds on the recent notion of irreducibility from differentially private learning. The $2^{O(dv^*)}$ bound follows from a simple globally stable learner that takes the majority vote of multiple empirical risk minimizers, with stability established using tools from stable regularity.

Comment
14 pages

Closest papers

Nearest neighbours by meaning across the whole index.

A polylogarithmic bound for list replicability

cs.LG stat.MLmath.CO ·2026-10-14 ·Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak
theory similarity 0.72
Abstract

Zhang [Zha26] recently posted a manuscript announcing that the list-replicability number of every class of $M\ge 2$ binary concepts on $N\ge 2$ domain points is $O(\log^2 M\log N)$, which would be the first polylogarithmic upper bound on this quantity. In this note, we present a short, self-contained proof of this bound, following the high-level approach of the manuscript but with considerably simpler arguments.

0.21

Private online learning and prediction for Littlestone classes

cs.LG cs.CRstat.ML ·2026-10-05 ·Amartya Sanyal
theory similarity 0.71
Abstract

We study mistake bounds for differentially private online learning and online prediction under oblivious realisable adversaries. Online learning requires the learner to release a hypothesis at each time step whereas in online prediction, the learner only needs to make predictions without releasing a hypothesis. Using a novel lower bound for private online learning and an upper bound for private prediction, we show that the sample complexity of these two problems are separated by a factor that grows with the time horizon for every class of finite Littlestone dimension $d$. First, we prove that every $(ε,δ)$-private online learner has a deterministic realisable stream of length $T$ on which the mistake bound is at least $\mathbb E [M_T]= O\left(\frac dε\log^{2/3} T\right)$. In particular, this is the first non-trivial lower in the range $1/T<δ<1/\log T)$ left open in earlier works[SR22,DSS24,LWY24]. Second, we prove that for every class of of Littlestone dimension $d$, there exists an $(ε,δ)$-jointly private predictor with at most $2^{2^{cd^2}}ε^{-2}\log^2(2/(εδ))$ expected mistakes, independently of $T$, for some absolute constant $c>0$. Thus, for every fixed class of finite Littlestone dimension when $δ=Θ(1/\log T)$, private learning requires $O\left(\log^{2/3} T\right)$ expected mistakes, whereas private prediction admits $O(\log\log T^2)$.

0.40

Nearly Linear Private Learning of Littlestone Classes

cs.LG ·2026-10-16 ·Shay Moran, Chao Yan
theory similarity 0.70
Abstract

Differentially private learning aims to learn from data while protecting individual training examples. For binary classification, finite Littlestone dimension characterizes approximate private PAC learnability (Alon et al., JACM 2022). Understanding how this dimension controls private sample complexity remains a central question. For classes of Littlestone dimension $d$, the first general upper bound was doubly exponential in $d$ (Bun, Livni, and Moran, FOCS 2020). Subsequent work improved this to $\widetilde O(d^6)$ (Ghazi et al., STOC 2021) and then to $\widetilde O(d^5)$ (Lyu, STOC 2026). We prove a nearly linear upper bound of $O(d\log d)$. Our main algorithmic contribution is a structural exponential mechanism for data-dependent candidate sets equipped with a rank satisfying suitable stability conditions. For natural Littlestone classes such as subspace indicators, this rank has a simple geometric interpretation: it is the codimension. This yields a private PAC learner for subspaces of dimension at most $d$ over any field, with tight linear dependence on $d$ and no dependence on the ambient dimension, improving the quadratic dependence of Kaplan et al. (STOC 2025). Our second contribution is combinatorial: drawing on model-theoretic ideas, we construct a suitable rank for general Littlestone classes and establish the counting bounds required by the mechanism.

0.40

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.68
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.08

Optimal Randomized Proper Online Learning

cs.LG ·2026-09-18 ·Zachary Chase, Idan Mehalel
theoryhot direction similarity 0.68
Abstract

We prove that the optimal expected mistake bound of online learning a function class $\mathcal{H}$ by a randomized proper learning algorithm is $O(\mathtt{L}(\mathcal{H}) \log T)$, where $\mathtt{L}(\mathcal{H})$ is the Littlestone dimension of $\mathcal{H}$ and $T$ is the time horizon. Our result improves upon the previously best known bound of $O(\mathtt{L}(\mathcal{H}) \log^6 T)$ given by Daskalakis and Golowich (STOC 2022), and is optimal up to a universal constant for worst-case classes.

0.27

Adversarially Robust PAC Learning with Optimal VC Rates

cs.LG stat.MLmath.ST ·2026-09-21 ·Steve Hanneke, Amirreza Shaeiri
theory similarity 0.65
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

New Lower Bounds for Private PAC Learning

cs.LG ·2026-10-30 ·Prathamesh Dharangutte, Amartya Sanyal
theory similarity 0.64
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

Tight Stochastic Sequential Covers for General VC Classes with Unknown i.i.d. Features

cs.LG stat.ML ·2026-10-31 ·Changlong Wu, Wojciech Szpankowski
similarity 0.64
Abstract · 35 pages, 2 figures

We study hybrid online learning with stochastic features and adversarial labels when the feature distribution is unknown. Prior work gave stochastic sequential covers of log-size $O(d\log^2 T)$ for a general VC class and logarithmic bounds only under stronger star-type structure. We show that finite VC dimension alone is enough: every binary class of VC dimension $d$ admits a distribution-blind exact cover with log-size $O(d\log T+\log(1/δ))$, matching the worst-case $Ω(d\log(T/d))$ dependence on the horizon. The key ingredient is a new local cube weight that counts Boolean subcubes incident to each realizable trace. Unlike the equal splits used in earlier constructions, we split mass unevenly according to these cube weights; a coordinate-deletion inequality shows that VC dimension controls the total cost of these splits. This yields, to our knowledge, the first tight $O((d+1)\log T)$ expected worst-case log-loss regret for general VC partitions with unknown i.i.d. features, and an exact polynomial-time implementation for planar affine halfspaces. We also show that the binary phenomenon does not extend from VC dimension to pseudo-dimension: a fixed pseudo-dimension-one sigmoid class requires $Ω(\log^2 T)$ bits for uniform sequential approximation at accuracy $1/T$.

0.14