2026-07-22T01:53:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5327 2024-03-06T10:36:19Z ddc:004 open_access

Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness Bun, Mark Steinke, Thomas Polynomial Approximations Pseudorandomness Concentration Learning Theory Halfspaces Low-degree polynomial approximations to the sign function underlie pseudorandom generators for halfspaces, as well as algorithms for agnostically learning halfspaces. We study the limits of these constructions by proving inapproximability results for the sign function. First, we investigate the derandomization of Chernoff-type concentration inequalities. Schmidt et al. (SIAM J. Discrete Math. 1995) showed that a tail bound of delta can be established for sums of Bernoulli random variables with only O(log(1/delta))-wise independence. We show that their results are tight up to constant factors. Secondly, the “polynomial regression” algorithm of Kalai et al. (SIAM J. Comput. 2008) shows that halfspaces can be efficiently learned with respect to log-concave distributions on R^n in the challenging agnostic learning model. The power of this algorithm relies on the fact that under log-concave distributions, halfspaces can be approximated arbitrarily well by low-degree polynomials. In contrast, we exhibit a large class of non-log-concave distributions under which polynomials of any degree cannot approximate the sign function to within arbitrarily low error. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mark Bun and Thomas Steinke 2015 Is Part Of LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2015.625 urn:nbn:de:0030-drops-53274 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.625 eng https://creativecommons.org/licenses/by/3.0/legalcode