PaperlayerView exact revision on arXiv

Source-linked AI summary

Near-Optimal List Replicability from Littlestone Dimension

Ari Blondal, Pooya Hatami, Chavdar Lalov, Sivan Tretiak

arXiv:2610.32853v1cs.LG

TL;DR

The paper asks how the list replicability number in realizable PAC learning depends on a class's complexity. It develops inductive and globally stable learning approaches and proves a bound in terms of Littlestone and dual VC dimensions, nearly matching the exponential worst-case lower bound in the Littlestone dimension.

  • Problem

    The quantitative relationship between list replicability and Littlestone dimension remained poorly understood despite finite Littlestone dimension characterizing online learnability.

    Source: §1 · p. 1

  • Method

    The paper combines an inductive approach using irreducibility and a transfer lemma with a globally stable learner based on repeated proper ERM runs and majority vote.

    Source: §1 · p. 2

  • Results

    lr(H) ≤ 2^O(d min{log d,v*}), nearly matching the exponential worst-case lower bound in d.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The bounds apply to arbitrary concept classes on countable domains and yield random-bit upper bounds for ρ-replicable learning that are independent of accuracy and confidence.

    Source: §1 · p. 2

    The transfer-lemma result assumes finite VC dimension and a fixed selection rule satisfying one of its stated conditions.

    Source: §5.1 · p. 7

Abstract

from arXiv · show

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^{\Omega(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_\epsilon(d^2)}$ for fixed accuracy $\epsilon>0$ implied by the work of Ghazi, Golowich, Kumar, and Manurangsi [STOC 2021] and Lyu [STOC 2026], our bound is independent of $\epsilon$. 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.

1 Introduction

The paper studies list replicability in realizable PAC learning, a setting connected to online learnability through Littlestone dimension. It gives a substantially tighter bound and develops two approaches, with applications to random-bit requirements.

1 Introduction

  • Theorem 1.1 bounds lr(H) by 2^O(d min{log d,v*}) for countable domains, improving the previous doubly exponential bound and nearly matching an exponential worst-case lower bound.The prior bound was lr(H) ≤ 2^2^O(d); the lower bound is exponential in d.Source: §1 · p. 2
  • The 2^O(d log d) approach uses irreducibility to show that SOA hypotheses from positive-dimension irreducible subclasses have Littlestone dimension at most d−1.The proof combines this observation with a transfer lemma and induction on Littlestone dimension.Source: §1 · p. 2
  • A second approach proves the 2^O(dv*) bound using repeated proper ERM runs, a majority vote, and stability tools from stable regularity.The proof proceeds through global stability, which is equivalent to list replicability.Source: §1 · p. 2

1.1 Applications and related work

  • The bounds also imply random-bit requirements for ρ-replicable learning that are independent of accuracy and confidence and nearly match a linear worst-case lower bound.Theorem 1.1 also yields upper bounds on random bits for differentially private learning.Source: §1.1 · p. 2
  • Earlier fixed-accuracy bounds depend on ε, while concurrent work studies nearly linear Littlestone-dimension dependence in private-learning sample complexity.The earlier bounds are 2^O_ε(d^2); Moran and Yan's work is described as concurrent and independent.Source: §1.1 · p. 2

1.2 Paper organization

  • The paper presents definitions and main results, overviews the proofs, and gives full proofs in Sections 5 and 6.The authors report using AI after drafting to suggest writing improvements and help check technical details; authors reviewed and edited revisions.Source: §1.2 · p. 2, §1.3 · p. 3

2 Preliminaries

The preliminaries define the realizable PAC setting and the measures of stability and list replicability. They also introduce Littlestone dimension and the Standard Optimal Algorithm used in the paper.

Learning setting

  • In realizable PAC learning, a learner receives independent examples and must output a hypothesis with loss at most ϵ with probability at least 1 − δ.The output may lie outside the class, which is called improper learning.Source: §2 · p. 3

Global stability and list replicability

  • Global stability requires a fixed accurate hypothesis for each realizable distribution to be output with probability at least p; it is equivalent to having a small list of accurate hypotheses.The equivalence is attributed to Chase, Moran, and Yehudayoff.Source: §2 · p. 4
  • An (ϵ, L)-list replicable learner outputs, with probability at least 1 − δ, a member of a distribution-specific list of at most L hypotheses, each with loss at most ϵ.The section defines the list replicability number through the least such list size.Source: §2 · p. 4

Littlestone dimension and SOA

  • A class shatters a depth-d mistake tree when every root-to-leaf label sequence is realized by a concept; its largest shattered depth is its Littlestone dimension.The section notes that VC dimension is at most Littlestone dimension.Source: §2 · p. 4
  • The Standard Optimal Algorithm predicts using the label whose restricted class has larger Littlestone dimension, with ties assigned +1.The branch opposite the SOA label loses dimension.Source: §2 · p. 4

3 Main results

The main results bound list replicability using Littlestone dimension and, in a second bound, dual VC dimension. The Littlestone-only bound is nearly optimal in the exponent, while the dual-dimension bound removes the logarithmic factor when ordinary VC dimension is constant.

3 Main results

  • For any ε>0, the Littlestone-dimension result provides an (ε, (d+2)^d)-list replicable learner with sample complexity 2^O(d^2 log d) ε^-2 δ^-(d+1).The learner guarantees confidence 1−δ.Source: §3 · p. 5
  • The 2^O(d log d) list-replicability bound is optimal up to a factor of log d in the exponent.The cited lower-bound class has list replicability number Θ(|X|) and Littlestone dimension ⌊log2 |X|⌋.Source: §3 · p. 5
  • When the ordinary VC dimension is constant, the logarithmic factor in the exponent can be removed.The dual-VC bound is lr(H) ≤ 2^O(dv*).Source: §3 · p. 5
  • For a concept class H over a countable domain, with d = ldim(H), v = vc(H), and v* = vc*(H) positive integers, there is an (ε, 1/2^{O(dv*)})-globally stable learner, and lr(H) ≤ 2^{O(dv*)}.Source: §3 · p. 5
  • The dual-VC result also yields a sample-complexity bound of 2^O(dv*) ε^-2 log(1/δ).This bound is stated for an (ε, 2^O(dv*))-list replicable learner.Source: §3 · p. 5

4 Technical overview

The overview presents two routes to list replicability: induction on Littlestone dimension via irreducibility, and a globally stable learner built from majority votes of ERM outputs. The first reduces to a lower-dimensional class, while the second yields a fixed accurate output with probability 2^-O(dv*).

4 Technical overview

  • SOA hypotheses from irreducible subclasses form a lower-dimensional class, enabling induction to bound list replicability.The transfer lemma reduces learning H to an auxiliary class with additive overhead in list size.Source: §4 · p. 5
  • Stable regularity identifies a subset of accurate ERM outputs whose label mass is at least three quarters on either side at every point.Uniform convergence for the dual class lets O(v*) independent draws from this subset have a majority that is the same hypothesis with constant probability.Source: §4 · p. 6
  • 2^-O(dv*) probability of outputting a fixed accurate hypothesis establishes global stability and the list replicability bound.The learner takes a pointwise majority of ERM outputs from O(v*) independent samples.Source: §4 · p. 6

5 Proof of Theorem 3.1

The proof of Theorem 3.1 reduces list replicability to an auxiliary class through a transfer lemma, then constructs a lower-dimensional auxiliary class using SOA and irreducibility. Induction gives the final bound.

5.1 Transfer lemma

  • The transfer lemma gives lr(H) ≤ N + lr(eH) when a fixed selection rule returns either a heavy proper hypothesis or an auxiliary hypothesis with controlled loss.The resulting learner's output lies, with probability at least 1 − δ, in a fixed list of accurate hypotheses of size at most N + L.Source: §5.1 · pp. 7–8
  • For a distribution on H, the transfer procedure runs ERM on batches, selects a hypothesis, and either outputs it when heavy or relabels reserved examples for the auxiliary learner.The ERM-output distribution is countably supported, and the proof establishes a high-probability event for the procedure.Source: §5.1 · p. 7

5.2 SOA and irreducibility

  • SOA hypotheses from d-irreducible subclasses of positive Littlestone dimension have Littlestone dimension at most d − 1.The proof uses this dimension drop to create the lower-dimensional class needed for induction.Source: §5.2 · p. 9
  • A d-irreducible subclass can be selected with mass at least 1/(d + 1)^d under any finitely supported distribution on a class of Littlestone dimension at most d.The argument repeatedly takes a heaviest member of a cover while Littlestone dimension drops.Source: §5.2 · p. 10

5.3 Finishing the proof

  • Induction on Littlestone dimension yields lr(H) ≤ (d + 2)^d.The proof combines an overhead of (d + 1)^d with the inductive bound for the auxiliary class.Source: §5.3 · p. 10

6 Proof of Theorem 3.2

The proof constructs a globally stable learner by combining structural properties of Littlestone classes with repeated ERM and majority voting. Goodness yields a truth-value hypothesis that can be recovered from samples and used to establish accuracy and stability.

6.1 Goodness and truth-value hypotheses

  • A countably supported distribution on a class of Littlestone dimension d has a subset of mass at least η^d whose conditional distribution is η-good.The proof repeatedly restricts to a label side that lowers Littlestone dimension, with at most d such drops.Source: §6.1 · p. 11
  • For a 1/4-good distribution, O(v*) sampled hypotheses suffice to recover its truth-value hypothesis exactly.The recovery claim is stated for countably supported distributions and uses uniform convergence for the dual class.Source: §6.1 · p. 11
  • For a good distribution, empirical frequencies stay on the same side of one-half as the truth value, so every empirical majority agrees with it simultaneously on all x.The frequency ranges are [0, 1/4] ∪ [3/4, 1] and, on the stated event, empirical frequencies lie in [0, 3/8] ∪ [5/8, 1].Source: §6.1 · p. 11

6.2 A globally stable learner

  • The learner divides mn examples into m independent blocks of n examples and returns the majority vote of the m proper ERM outputs.Here m = O(v*), and n is the sample size for the deterministic proper ERM.Source: §6.2 · p. 11
  • The majority learner is (ε, p)-globally stable with p = 1/2^O(dv*), yielding the desired list replicability bound.Its sample complexity is the ERM sample complexity multiplied by m = O(v*).Source: §6.2 · p. 12
  • The truth-value hypothesis is accurate because each disagreement with the label implies that at least three-quarters of the distribution’s hypotheses also disagree.The proof integrates this pointwise inequality to bound its loss.Source: §6.2 · p. 12

Related papers

Loading 2610.32853v1…