ε-average agnostic learners need (d/ε²)(1/62 − log(2d+2)/(4d)) samples

Open

QAlgorithms.Arunachalam.avg_agnostic_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\ge1$ , and let $\varepsilon\in(0,1/10]$ . An $\varepsilon$ -average agnostic learner for $C$ using $T$ samples is a randomized map from $T$ i.i.d. samples $(X,Y)\sim D^T$ to a hypothesis $h_{XY}$ such that, for every distribution $D$ on $\{0,1\}^{n+1}$ ,

\mathbb E_{(X,Y)\sim D^T}\big[\mathrm{err}_D(h_{XY})\big]-\mathrm{opt}_D(C)\le\varepsilon,

where $\mathrm{err}_D(h)=\Pr_{(x,b)\sim D}[h(x)\ne b]$ and $\mathrm{opt}_D(C)=\min_{c\in C}\mathrm{err}_D(c)$ . Then every $\varepsilon$ -average agnostic learner for $C$ satisfies

T\ \ge\ \frac{d}{\varepsilon^2}\left(\frac1{62}-\frac{\log_2(2d+2)}{4d}\right).

This is the explicit-constant (minimax) form of the agnostic lower bound, comparable to Audibert's $T\ge d/(36\varepsilon^2)$ .

Formalization Note The source's "there exists a distribution for which every learner" refers to the proof's hard distribution, which is random; the learner is required to be $\varepsilon$ -good for every unknown $D$ , as in the definition. $d\ge1$ is assumed because the bound divides by $d$ . Hypotheses are not required to lie in $C$ (the definition on p.166 does not require it); on the proof's distributions, supported on a shattered set, this makes no difference.

Preamble

import Definitions.Def_QAlgorithms_Defs_Learning
set_option autoImplicit false

Formal statement

namespace QAlgorithms.Arunachalam

open QAlgorithms.Learning






/-- Arunachalam p.166–168, Theorem 7.4.5: for a concept class `C` with `VC-dim(C) = d` and every
`ε ∈ (0, 1/10]`, every `ε`-average agnostic learner for `C` (using `T` samples from `AEX(D)` and
satisfying `E_{(X,Y)∼D^T}[err_D(h_{XY})] − opt_D(C) ≤ ε` for every distribution `D`) has
`T ≥ (d/ε²) · (1/62 − log(2d + 2)/(4d))`, `log` base 2.

The source's "there exists a distribution for which every learner …" is the proof's random
hard distribution `D_a`; a learner is required to be `ε`-good for every unknown `D`, as the
definition on p.166 says. `d ≥ 1` is assumed because the bound divides by `d` (trap 14). -/
theorem avg_agnostic_lower_bound (n : ℕ) (C : Finset (Qubits n → Bool)) (d : ℕ)
    (hd : vcDimClass C = d) (hd1 : 1 ≤ d) (ε : ℝ) (hε0 : 0 < ε) (hε : ε ≤ 1 / 10) (T : ℕ)
    (L : (Fin T → Qubits n × Bool) → PMF (Qubits n → Bool))
    (hL : IsAvgAgnosticLearner C ε T L) :
    (d : ℝ) / ε ^ 2 * (1 / 62 - Real.logb 2 (2 * d + 2) / (4 * d)) ≤ T := by
  sorry

end QAlgorithms.Arunachalam

Source

Srinivasan Arunachalam, Quantum Algorithms and Learning Theory — Part II, 2018 thesis, ILLC DS-2018-08, PDF p. 167, Theorem 7.4.5. 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 data are as follows:

$n\in\mathbb N$ ;
a finite class $C$ of Boolean functions on $\{0,1\}^n$ whose VC dimension equals $d$ , with $d\ge1$ . The VC dimension is the largest size of a subset of $\{0,1\}^n$ shattered by the sets $\{x:c(x)=1\}$ , $c\in C$ ;
a real $\varepsilon$ with $0<\varepsilon\le\tfrac1{10}$ ;
$T\in\mathbb N$ ;
a randomized learner $L$ mapping each labelled sample $s\in(\{0,1\}^n\times\{0,1\})^T$ to a probability distribution $L(s)$ over all Boolean functions on $\{0,1\}^n$ . No properness requirement is imposed.

The hypothesis is that $L$ is an average-case agnostic learner with excess error $\varepsilon$ . That is, for every distribution $D$ on $\{0,1\}^n\times\{0,1\}$ (nonnegative, summing to $1$ ),

\sum_{s}\Big(\prod_{i=1}^T D(s_i)\Big)\sum_{h}L(s)(h)\,\operatorname{err}_D(h)\;-\;\operatorname{opt}_D(C)\;\le\;\varepsilon,

with

\operatorname{err}_D(h)=\sum_{(x,b):\,h(x)\ne b}D(x,b),\qquad \operatorname{opt}_D(C)=\inf_{c\in C}\operatorname{err}_D(c).

In words: the expected error of the output hypothesis exceeds the best error in $C$ by at most $\varepsilon$ .

The conclusion, with $\log_2$ the base-2 logarithm and explicit constants, is

\frac{d}{\varepsilon^2}\left(\frac1{62}-\frac{\log_2(2d+2)}{4d}\right)\;\le\;T.

The bracketed factor is negative for small $d$ ; for example, at $d=1$ it equals $\tfrac1{62}-\tfrac12$ . In such cases the conclusion holds trivially, since $T\ge0$ . The factor becomes positive only once $d$ is fairly large, on the order of a hundred or more.

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