Almost Optimal Proper Learning and Testing Polynomials
This addresses a fundamental problem in computational learning theory for researchers and practitioners, providing near-optimal algorithms for sparse polynomial learning and testing, though it is incremental in building on prior reductions.
The paper tackles the problem of learning and testing Boolean sparse multivariate polynomials under the uniform distribution, achieving the first almost optimal polynomial-time proper learning algorithm with query complexity sublinear in 1/ε and almost linear in s, and an almost tight lower bound, as well as an almost optimal polynomial-time tester with Õ(s/ε) queries for β > 3.404.
We give the first almost optimal polynomial-time proper learning algorithm of Boolean sparse multivariate polynomial under the uniform distribution. For $s$-sparse polynomial over $n$ variables and $ε=1/s^β$, $β>1$, our algorithm makes $$q_U=\left(\frac{s}ε\right)^{\frac{\log β}β+O(\frac{1}β)}+ \tilde O\left(s\right)\left(\log\frac{1}ε\right)\log n$$ queries. Notice that our query complexity is sublinear in $1/ε$ and almost linear in $s$. All previous algorithms have query complexity at least quadratic in $s$ and linear in $1/ε$. We then prove the almost tight lower bound $$q_L=\left(\frac{s}ε\right)^{\frac{\log β}β+Ω(\frac{1}β)}+ Ω\left(s\right)\left(\log\frac{1}ε\right)\log n,$$ Applying the reduction in~\cite{Bshouty19b} with the above algorithm, we give the first almost optimal polynomial-time tester for $s$-sparse polynomial. Our tester, for $β>3.404$, makes $$\tilde O\left(\frac{s}ε\right)$$ queries.