Almost Optimal Proper Learning and Testing Polynomials

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.

No reviews yet.

No comments yet.