A General Memory-Bounded Learning Algorithm
This work addresses the need for practical bounded-memory algorithms in machine learning, representing an incremental step toward characterizing such learning.
The paper tackles the problem of designing bounded-memory learning algorithms, which had been underexplored compared to impossibility results, by proposing a general algorithm that saves only important bits from examples when the distribution is known, applicable to hypothesis classes with an 'anti-mixing' property.
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.