Timezone: »

 
Poster
Towards a Combinatorial Characterization of Bounded-Memory Learning
Alon Gonen · Shachar Lovett · Michal Moshkovitz

Mon Dec 07 09:00 PM -- 11:00 PM (PST) @ Poster Session 0 #72

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. This is the first characterization of strong learning under space constraints in any regime. 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.

Author Information

Alon Gonen (UCSD)
Shachar Lovett (University of California San Diego)
Michal Moshkovitz (UCSD)

More from the Same Authors