Distribution-independent SQ learning does not imply low dimension complexity
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.
Authors
- Samuel Mausberg (ORCID: https://orcid.org/0009-0006-1091-8044)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-10-04
- DOI
- https://doi.org/10.5281/zenodo.23149031
- Primary Topic
- Machine Learning and Algorithms
- Type
- preprint