Antos, Andras; Lugosi, Gábor
(1997-01-01)
Minimax lower bounds for concept learning state, for example, that
for each sample size $n$ and learning rule $g_n$, there exists a distribution
of the observation $X$ and a concept $C$ to be learnt such that the expected
error ...