Towards a combinatorial characterization of bounded memory learning
This work addresses the foundational problem of understanding memory constraints in machine learning theory, but it is incremental as it builds on existing combinatorial dimensions like VC and SQ dimensions.
The paper tackles the problem of characterizing bounded memory learning with combinatorial dimensions, proposing a candidate based on SQ dimension of neighboring distributions for realizable strong learning under a known distribution, and proves matching upper and lower bounds in some parameter regimes, showing equivalence between bounded memory and SQ learning.
Combinatorial dimensions play an important role in the theory of machine learning. For example, VC dimension characterizes PAC learning, SQ dimension characterizes weak learning with statistical queries, and Littlestone dimension characterizes online learning. In this paper we aim to develop combinatorial dimensions that characterize bounded memory learning. We propose a candidate solution for the case of realizable strong learning under a known distribution, based on the SQ dimension of neighboring distributions. We prove both upper and lower bounds for our candidate solution, that match in some regime of parameters. In this parameter regime there is an equivalence between bounded memory and SQ learning. We conjecture that our characterization holds in a much wider regime of parameters.