ECCC-Report TR02-060https://eccc.weizmann.ac.il/report/2002/060Comments and Revisions published for TR02-060en-usSun, 03 Nov 2002 19:32:12 +0200
Paper TR02-060
| New Lower Bounds for Statistical Query Learning |
Ke Yang
https://eccc.weizmann.ac.il/report/2002/060We prove two lower bounds on the Statistical Query (SQ) learning
model. The first lower bound is on weak-learning. We prove that for a
concept class of SQ-dimension $d$, a running time of
$\Omega(d/\log d)$ is needed. The SQ-dimension of a concept class is
defined to be the maximum number of concepts that are ``uniformly
correlated'', in that each pair of them have nearly the same
correlation. This lower bound matches the upper bound
in~\cite{BFJ+94}, up to a logarithmic factor. We prove this lower
bound against an ``honest SQ-oracle'', which gives a stronger result
than the ones against the more frequently used ``adversarial
SQ-oracles''. The second lower bound is more general. It gives a
continuous trade-off between the ``advantage'' of an algorithm in
learning the target function and the number of queries it needs to
make, where the advantage of an algorithm is the probability it
succeeds in predicting a label minus the probability it doesn't.
Both lower bounds extend and/or strengthen previous results, and
solved an open problem left in~\cite{Y01}.
A preliminary version of this paper appeared in
the Proceedings of the Fifteenth Annual Conference on
Computational Learning Theory, 2002 (COLT 2002)
Sun, 03 Nov 2002 19:32:12 +0200https://eccc.weizmann.ac.il/report/2002/060