A General Memory-Bounded Learning Algorithm
  Designing bounded-memory algorithms is becoming increasingly important
nowadays. Previous works studying bounded-memory algorithms focused on proving
impossibility results, while the design of bounded-memory algorithms was left
relatively unexplored. To remedy this situation, in this work we design a
general bounded-memory learning algorithm, when the underlying distribution is
known. The core idea of the algorithm is not to save the exact example
received, but only a few important bits that give sufficient information. This
algorithm applies to any hypothesis class that has an "anti-mixing" property.
This paper complements previous works on unlearnability with bounded memory and
provides a step towards a full characterization of bounded-memory learning.
