Towards a Combinatorial Characterization of
       Bounded-Memory Learning

          Alon Gonen     Shachar Lovett     Michal Moshkovitz
                 University of California San Diego

                       Abstract
     Combinatorial dimensions play an important role in the theory of machine learning.
     For example, VC dimension characterizes PAC learning, SQ dimension character-
     izes weak learning with statistical queries, and Littlestone dimension characterizes
     online lear ...