# Near-Linear Sample Complexity for Lp Polynomial Regression

arXiv: https://arxiv.org/abs/2211.06790 · HTML: https://mlsanity.com/paper/2211.06790/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Nov 2022.

## Built on by (most cited first, 4 of 4)

- [Improved Active Learning via Dependent Leverage Score Sampling](https://mlsanity.com/paper/2310.04966/) (2023)
- [Fast (1+varepsilon)-Approximation Algorithms for Binary Matrix Factorization](https://mlsanity.com/paper/2306.01869/) (2023)
- [On Socially Fair Low-Rank Approximation and Column Subset Selection](https://mlsanity.com/paper/2412.06063/) (2024)
- [Active Learning with Low-Rank Structure for Data Selection](https://mlsanity.com/paper/2606.16045/) (2026)

## Abstract (arXiv)

We study Lp polynomial regression. Given query access to a function f:[-1,1] rightarrow ℝ, the goal is to find a degree d polynomial hatq such that, for a given parameter varepsilon > 0,  |hatq-f|p≤ (1+varepsilon) · minq:deg(q)≤ d|q-f|p.  Here |·|p is the Lp norm, |g|p = (int-11 |g(t)|p dt)1/p. 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 hat q, it suffices to sample O(d, fracpolylog,dpoly,varepsilon) 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+varepsilon) 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 Omega(dp/2) samples are required.