Near-Linear Sample Complexity for Lp Polynomial Regression

Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    We study Lp polynomial regression. Given query access to a function f : [−1, 1] → R, the goal is to find a degree d polynomial qb such that, for a given parameter ε > 0, (Equation presented). Here (Equation presented). We show that querying f at points randomly drawn from the Chebyshev measure on [−1, 1] is a near-optimal strategy for polynomial regression in all Lp norms. In particular, to find (Equation presented), it suffices to sample (Equation presented) points from [−1, 1] with probabilities proportional to this measure. While the optimal sample complexity for polynomial regression was well understood for L2 and L∞, our result is the first that achieves sample complexity linear in d and error (1 + ε) for other values of p without any assumptions. Our result requires two main technical contributions. The first concerns p ≤ 2, for which we provide explicit bounds on the Lp Lewis weight function of the infinite linear operator underlying polynomial regression. Using tools from the orthogonal polynomial literature, we show that this function is bounded by the Chebyshev density. Our second key contribution is to take advantage of the structure of polynomials to reduce the p > 2 case to the p ≤ 2 case. By doing so, we obtain a better sample complexity than what is possible for general p-norm linear regression problems, for which (Equation presented) samples are required.

    Original languageEnglish (US)
    Title of host publication34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
    PublisherAssociation for Computing Machinery
    Number of pages67
    ISBN (Electronic)9781611977554
    StatePublished - 2023
    Event34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 - Florence, Italy
    Duration: Jan 22 2023Jan 25 2023

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


    Conference34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

    ASJC Scopus subject areas

    • Software
    • General Mathematics


    Dive into the research topics of 'Near-Linear Sample Complexity for Lp Polynomial Regression'. Together they form a unique fingerprint.

    Cite this