Separation found between learning query complexity and dimension size
A Separation Between Distribution-Free SQ Learning and Dimension Complexity
Computational Complexity
Summary
The paper shows that for a certain group of logical functions, you can learn them using a reasonable number of simple queries without knowing anything about the data's distribution. However, to represent these functions as a combination of simpler components, you need an extremely large number of pieces. The authors built on prior work about logical operations and their complexity to prove this. This finding answers a previous open question about how learning complexity relates to representation size.
What this means in practice
- •For machine learning system designers: Design learning algorithms knowing the gap between query complexity and dimension complexity can be large in distribution-free settings.
- •For complexity theory researchers: Use the separation result as a foundation for analyzing limits of function representation and learning models.
A theory result. No direct application yet.
Authors
Shyamal Patel
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].