ECCC-Report TR22-098https://eccc.weizmann.ac.il/report/2022/098Comments and Revisions published for TR22-098en-usWed, 13 Jul 2022 05:55:04 +0300
Paper TR22-098
| Non-Adaptive Proper Learning Polynomials |
Nader Bshouty
https://eccc.weizmann.ac.il/report/2022/098We give the first polynomial-time *non-adaptive* proper learning algorithm of Boolean sparse multivariate polynomial under the uniform distribution. Our algorithm, for $s$-sparse polynomial over $n$ variables, makes $q=(s/\epsilon)^{\gamma(s,\epsilon)}\log n$ queries where $2.66\le \gamma(s,\epsilon)\le 6.922$ and runs in $\tilde O(n)\cdot poly(s,1/\epsilon)$ time. We also show that for any $\epsilon=1/s^{O(1)}$ any non-adaptive learning algorithm must make at least $(s/\epsilon)^{\Omega(1)}\log n$ queries. Therefore, the query complexity of our algorithm is also polynomial in the optimal query complexity and optimal in $n$. Wed, 13 Jul 2022 05:55:04 +0300https://eccc.weizmann.ac.il/report/2022/098