Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions
This work addresses a gap in time-space tradeoff lower bounds for learning problems with small test spaces, which is incremental but provides foundational insights for computational learning theory.
The paper tackles the problem of learning low-degree polynomial functions from random test samples when the test space is smaller than the input space, extending prior methods to handle this class. It shows that any algorithm for learning m-variate homogeneous polynomials over F2 requires either Ω(mn) space or 2^{Ω(m)} time, with n=m^{Θ(d)}, and these bounds are asymptotically optimal.
We develop an extension of recently developed methods for obtaining time-space tradeoff lower bounds for problems of learning from random test samples to handle the situation where the space of tests is signficantly smaller than the space of inputs, a class of learning problems that is not handled by prior work. This extension is based on a measure of how matrices amplify the 2-norms of probability distributions that is more refined than the 2-norms of these matrices. As applications that follow from our new technique, we show that any algorithm that learns $m$-variate homogeneous polynomial functions of degree at most $d$ over $\mathbb{F}_2$ from evaluations on randomly chosen inputs either requires space $Ω(mn)$ or $2^{Ω(m)}$ time where $n=m^{Θ(d)}$ is the dimension of the space of such functions. These bounds are asymptotically optimal since they match the tradeoffs achieved by natural learning algorithms for the problems.