{"ID":23510314,"CreatedAt":"2026-09-18T02:21:44.056544415Z","UpdatedAt":"2026-09-18T02:21:44.056544415Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.19780","arxiv_id":"2609.19780","title":"A Separation Between Distribution-Free SQ Learning and Dimension Complexity","abstract":"We show that there exists a class of boolean functions C such that $(i)$ there is a distribution-independent statistical query algorithm for learning C that makes a polynomial number of queries of inverse polynomial tolerance and $(ii)$ for any set of functions $Φ_1, \\dots, Φ_r$ such that for all $f \\in$ C we can write $f(x) = \\text{sign} \\left( \\sum_{i = 1}^r w_i Φ_i(x) \\right)$ for some set of weights $w_i \\in \\mathbb{R}$, we must have that $r \\geq n^{ω(1)}$. This gives a superpolynomial separation between dimension complexity and the query complexity of distribution-free learning in the statistical query model, negatively answering a question of Feldman, Kamath, and Srebro [FKS26]. Our construction C is a subclass of DNFs, and the proof is a simple consequence of recent progress on agnostically learning conjunctions [DKR25,CPS26] and the work of Razborov and Sherstov on the sign rank of DNFs [RS10].","short_abstract":"We show that there exists a class of boolean functions C such that $(i)$ there is a distribution-independent statistical query algorithm for learning C that makes a polynomial number of queries of inverse polynomial tolerance and $(ii)$ for any set of functions $Φ_1, \\dots, Φ_r$ such that for all $f \\in$ C we can write...","url_abs":"https://arxiv.org/abs/2609.19780","url_pdf":"https://arxiv.org/pdf/2609.19780v1","authors":"[\"Shyamal Patel\"]","published":"2026-09-17T06:49:33Z","proceeding":"cs.CC","tasks":"[\"cs.CC\"]","methods":"[]","has_code":false}