Manuscript Psy01-A@1 · Psy01-A.tex · theorem · 94477fa3

Theorem: Conditional evaluation concentration

Concentration: what survivor counts do and do not imply › Held-out evaluation uncertainty · lines 1676–1711 · proof included or linked

Psy01-A@1#thm:evaluation, Psy01-A@1#eq:hoeffdingacc, Psy01-A@1#eq:simultaneousradius, Psy01-A@1#eq:paireddifference

Back to manuscript

Condition on a fixed trained network independent of the held-out sample. For $n$ independent test outcomes, let $q$ estimate an accuracy $q$ . Then

P {\abs q - q \geq t} \leq 2 e^{- 2 n t^{2}} .

For $J$ prespecified observables evaluated on the same independent examples, their simultaneous accuracy radius at confidence $1 - δ$ is

t_{acc} = \frac{lo g ( 2 J / δ )}{2 n} .

For a paired difference of two correctness indicators, including a cue drop or a pruning-arm difference,

P {\abs D - D \geq t} \leq 2 e^{- n t^{2} /2} .

Proof. Correctness indicators lie in $[0, 1]$ , so Hoeffding's inequality Hoeffding gives (eq:hoeffdingacc). A union bound over $J$ observables gives (eq:simultaneousradius). A paired difference lies in $[- 1, 1]$ , an interval of length two. The same inequality gives (eq:paireddifference).

Displayed formulas in this passage

Psy01-A@1#eq:hoeffdingacc · line 1681
$P {\abs q - q \geq t} \leq 2 e^{- 2 n t^{2}} .$
Psy01-A@1#eq:simultaneousradius · line 1689
$t_{acc} = \frac{lo g ( 2 J / δ )}{2 n} .$
Psy01-A@1#eq:paireddifference · line 1696
$P {\abs D - D \geq t} \leq 2 e^{- n t^{2} /2} .$

Nearby in this section

section: Held-out evaluation uncertainty