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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Distribution-independent SQ learning does not imply low dimension complexity

Samuel Mausberg
Zenodo (CERN European Organization for Nuclear Research)
Machine Learning and Algorithms
preprint

Distribution-independent SQ learning does not imply low dimension complexity

Samuel Mausberg
preprint en

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.

Zenodo (CERN European Organization for Nuclear Research)
Machine Learning and Algorithms
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.