Almost optimal proper learning and testing polynomials

DOI10.1007/978-3-031-20624-5_19MaRDI QIDQ6109015zbMATH OpenOpenAlexFDO

Authors Nader H. Bshouty

Publication date 26 July 2023

Published in LATIN 2022: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2202.03207

zbMATH Keywords

polynomialproper learningproperty testing

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx) Theory of computing (68Qxx)

Abstract: 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 $$, $$, our algorithm makes ${\displaystyle }$q_U=left(frac{s}{epsilon} ight)^{frac{log �eta}{�eta}+O(frac{1}{�eta})}+ ilde Oleft(s ight)left(logfrac{1}{epsilon} ight)log n${\displaystyle }$ queries. Notice that our query complexity is sublinear in $1/epsilon$ and almost linear in $s$. All previous algorithms have query complexity at least quadratic in $s$ and linear in $1/epsilon$. We then prove the almost tight lower bound ${\displaystyle }$q_L=left(frac{s}{epsilon} ight)^{frac{log �eta}{�eta}+Omega(frac{1}{�eta})}+ Omegaleft(s ight)left(logfrac{1}{epsilon} ight)log n,${\displaystyle }$ 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 $$, makes ${\displaystyle }$ ilde Oleft(frac{s}{epsilon} ight)${\displaystyle }$ queries.

Cites work

• A brief introduction to property testing
• A theory of the learnable
• Algorithmic and analysis techniques in property testing
• Applying Coding Theory to Sparse Interpolation
• Efficient sample extractors for juntas with applications
• Efficiently testing sparse \(\text{GF}(2)\) polynomials
• Interpolation and Approximation of Sparse Multivariate Polynomials over GF(2)
• Introduction to Property Testing
• Learning Behaviors of Automata from Multiplicity and Equivalence Queries
• Learning functions represented as multiplicity automata
• Learning sparse multivariate polynomials over a field with queries and counterexamples.
• On Learning Ring-Sum-Expansions
• On Optimal Learning Algorithms for Multiplicity Automata
• On PAC learning algorithms for rich Boolean function classes
• On learning multivariate polynomials under the uniform distribution
• On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
• Property testing lower bounds via communication complexity
• Queries and concept learning
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems
• Simple Learning Algorithms for Decision Trees and Multivariate Polynomials

This page was built for publication: Almost optimal proper learning and testing polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6109015)