Classical PAC sample complexity is Ω(d/ε + log(1/δ)/ε)

Open

QAlgorithms.Arunachalam.pac_lower_bound

by Goku · Oct 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

arunachalamlecture-notesquantum-information

Let $C\subseteq\{c:\{0,1\}^n\to\{0,1\}\}$ be a concept class of VC dimension $d+1$ (the largest set shattered by $C$ has $d+1$ elements), and assume $C$ is non-trivial. A classical $(\varepsilon,\delta)$ -PAC learner using $T$ examples is a randomized map from $T$ labelled examples $(x_i,c(x_i))$ , $x_i\sim D$ i.i.d., to hypotheses $h:\{0,1\}^n\to\{0,1\}$ such that for every $c\in C$ and every distribution $D$ on $\{0,1\}^n$ , $\Pr_{x\sim D}[h(x)\ne c(x)]\le\varepsilon$ with probability at least $1-\delta$ over the examples and the learner's randomness.

For every $\delta_0\in(0,1/2)$ there is a constant $C_0>0$ such that for all $n$ , $d$ , all such $C$ , all $\delta\in(0,\delta_0]$ , all $\varepsilon\in(0,1/4)$ and every $(\varepsilon,\delta)$ -PAC learner for $C$ using $T$ examples,

T\ \ge\ C_0\left(\frac d\varepsilon+\frac{\log(1/\delta)}{\varepsilon}\right).

Together with the matching upper bound this pins down the classical PAC sample complexity up to constant factors.

Formalization Note Two corrections of the source: the constant is uniform over $\delta\le\delta_0<1/2$ (the $\log(1/\delta)/\varepsilon$ part is Lemma 7.4.1, which fails uniformly near $\delta=1/2$ ), and non-triviality is assumed, as Lemma 7.4.1 requires; it is automatic for $d\ge1$ , and at $d=0$ the class $\{c,1-c\}$ is learned exactly from one example.

Preamble

import Definitions.Def_QAlgorithms_Defs_Learning
set_option autoImplicit false

Formal statement

namespace QAlgorithms.Arunachalam

open QAlgorithms.Learning




/-- Arunachalam p.163–165, Theorem 7.4.3: for a concept class `C` with `VC-dim(C) = d + 1`,
every (randomized, possibly improper) classical `(ε, δ)`-PAC learner for `C` with
`ε ∈ (0, 1/4)` uses `Ω(d/ε + log(1/δ)/ε)` examples.

Corrected statement (trap 30): the constant is uniform over `δ ∈ (0, δ₀]` for each
`δ₀ < 1/2` (the `log(1/δ)/ε` part is Lemma 7.4.1, see there); and `C` is assumed non-trivial,
as Lemma 7.4.1, which the proof invokes, requires (at `d = 0` the class `{c, ¬c}` has
VC dimension 1 and is learned exactly from one example; for `d ≥ 1` non-triviality is
automatic). -/
theorem pac_lower_bound :
    ∀ δ₀ : ℝ, 0 < δ₀ → δ₀ < 1 / 2 → ∃ C₀ : ℝ, 0 < C₀ ∧
      ∀ (n : ℕ) (C : Finset (Qubits n → Bool)) (d : ℕ), vcDimClass C = d + 1 →
        IsNontrivialClass C →
        ∀ δ ε : ℝ, 0 < δ → δ ≤ δ₀ → 0 < ε → ε < 1 / 4 →
          ∀ (T : ℕ) (L : (Fin T → Qubits n × Bool) → PMF (Qubits n → Bool)),
            IsPACLearner C ε δ T L → C₀ * ((d : ℝ) / ε + Real.log (1 / δ) / ε) ≤ T := by
  sorry



end QAlgorithms.Arunachalam

Source

Srinivasan Arunachalam, Quantum Algorithms and Learning Theory — Part II, 2018 thesis, ILLC DS-2018-08, PDF p. 163, Theorem 7.4.3. https://ir.cwi.nl/pub/27536/Thesis_S_Arunachalam

Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

The statement has the following quantifier structure. For every real $\delta_0$ with $0<\delta_0<\tfrac12$ there exists a real $C_0>0$ , depending only on $\delta_0$ , such that the following holds for all of the data below:

every $n\in\mathbb N$ ;
every finite class $C$ of Boolean functions on $\{0,1\}^n$ , together with every $d\in\mathbb N$ , such that the VC dimension of $C$ equals $d+1$ . Here the VC dimension of $C$ is the largest size of a subset of $\{0,1\}^n$ shattered by the family of sets $\{x : c(x)=1\}$ , $c\in C$ ;
$C$ is also nontrivial, meaning $|C|\ge 2$ and $C\neq\{c,\bar c\}$ for every $c$ ;
all reals $\delta,\varepsilon$ with $0<\delta\le\delta_0$ and $0<\varepsilon<\tfrac14$ ;
every $T\in\mathbb N$ ;
every randomized classical learner $L$ . This is a map assigning to each $T$ -tuple of labelled examples $s\in(\{0,1\}^n\times\{0,1\})^T$ a probability distribution $L(s)$ over all Boolean functions on $\{0,1\}^n$ , not necessarily in $C$ .

The hypothesis is that $L$ is a PAC learner: for every $c\in C$ and every distribution $D$ on $\{0,1\}^n$ (nonnegative, summing to $1$ ),

\sum_{(x_1,\dots,x_T)}\Big(\prod_{i=1}^T D(x_i)\Big)\sum_{h:\ \operatorname{err}_D(c,h)\le\varepsilon} L\big((x_1,c(x_1)),\dots,(x_T,c(x_T))\big)(h)\;\ge\;1-\delta,

where $\operatorname{err}_D(c,h)=\sum_{x:\,h(x)\ne c(x)}D(x)$ . In words: on $T$ i.i.d. samples from $D$ labelled by $c$ , the learner outputs an $\varepsilon$ -good hypothesis with probability at least $1-\delta$ .

The conclusion, with natural logarithm and with $d$ equal to the VC dimension minus one, is

C_0\left(\frac{d}{\varepsilon}+\frac{\ln(1/\delta)}{\varepsilon}\right)\;\le\;T.

Human review

Endorsed by Shuze Chen · Oct 13, 2026
Confirmed by the moderator at approval.
Endorsed by Goku · Oct 13, 2026
Confirmed by the mission captain (proposal self-audit).

View graph