Distribution-independent SQ learning does not imply low dimension complexity

Abstract

Does distribution-independent statistical-query learning imply low dimension complexity? We give a negative answer with a sharp exponential separation. Classes on 2N³ points admit O_ε(log N) queries of constant tolerance, yet have ordinary, exact probabilistic, and expected-error dimension Θ(N) at fixed approximation error below 1/2. The lower bound persists when the feature law may depend on a target prior and discard any fixed fraction of targets below one. These classes have constant classical SQ dimension, giving an explicit counterexample to a claimed bound of Karchmer and Malach. The construction combines the incidence flips of Hatami, Hatami, Pires, Tao, and Zhao with a rectangle-based learner and a sign-pattern count restricted to incidences. The fixed-tolerance query order is optimal; transcript representations give complementary upper bounds. The learner can be proper, deterministic, and polynomial-time in the explicit table.