Scale-Independent Robust
Multivariate Polynomial Regression

Abstract

We resolve the sample-versus-scale tradeoff posed by Arora, Bhattacharyya, Boban, Guruswami, and Kelman [1, Remark 1.9] in robust multivariate polynomial regression, giving scale-independent recovery with optimal degree exponents in an exact-real LP-oracle model. The unknown polynomial $p$ has degree at most $d$ in each of $n$ coordinates. Covariates are i.i.d. product-Chebyshev or uniform, and outlier indicators are mutually independent, independent of the covariates, and have probabilities at most a known $\rho<1/2$ . Inlier errors are bounded by an unknown $\sigma$ ; admissible labels may otherwise be adversarial. For $0<\delta\leq\varepsilon\leq 1/2$ , our algorithm returns $\widehat{p}$ with $\left\lVert\widehat{p}-p\right\rVert_{\infty}\leq(2+\varepsilon)\sigma$ with probability at least $1-\delta$ , using $O_{n,\rho}((d/\varepsilon)^{n}\log(d/\delta))$ product-Chebyshev samples or $O_{n,\rho}((d/\varepsilon)^{2n}\log(d/\delta))$ uniform samples. It does not use $\sigma$ , recovers $p$ exactly at zero noise, and makes a predetermined $O_{n,\rho}(1+\log(d/\varepsilon))$ number of LP calls independent of signal magnitude. For fixed dimension, accuracy, positive contamination rate, and success probability, the Chebyshev rate matches the known dependence on $d$ , while the uniform rate has the optimal degree exponent up to an occupancy logarithm. The key ingredient is an arbitrary-representative product-Chebyshev $L^{1}$ norming inequality, which enables a Chebyshev-mass-weighted least-absolute-deviations initializer followed by fixed-budget median refinements.

Note. This paper was generated entirely by AI, including MiMo, using an automated research pipeline developed by Chenghua Liu and Hanyu Li.

1 Introduction and main result

Robust polynomial regression asks whether a bounded-degree polynomial can be recovered in supremum norm when a minority of responses are arbitrary. We formalize this question under product-Chebyshev and uniform random designs, compare with the prior sample-versus-scale tradeoff, and state our guarantee.

Fix integers $n,d\geq 1$ , and let

\mathcal{P}_{d,n}:=\left\{q(\bm{x})=\sum_{\bm{a}\in\{0,\ldots,d\}^{n}}c_{\bm{a}}\bm{x}^{\bm{a}}:c_{\bm{a}}\in\mathbb{R}\right\}.

Here $\bm{x}^{\bm{a}}:=\prod_{k=1}^{n}x_{k}^{a_{k}}$ , so the degree is at most $d$ in each coordinate and $\dim\mathcal{P}_{d,n}=(d+1)^{n}$ . The two design laws are the normalized uniform probability measure $d\mu_{U}(\bm{x})=2^{-n}d\bm{x}$ and the product-Chebyshev probability measure

d\nu(\bm{x})=\prod_{k=1}^{n}\frac{dx_{k}}{\pi\sqrt{1-x_{k}^{2}}}.

(1.1)

An unknown $p\in\mathcal{P}_{d,n}$ is observed through a batch $(X_{i},Y_{i})_{i=1}^{M}\in([-1,1]^{n}\times\mathbb{R})^{M}$ , where the $X_{i}$ are i.i.d. from one of these laws. Let $O_{i}\in\{0,1\}$ be mutually independent outlier indicators, independent of $X_{1:M}$ , with $\mathbb{P}(O_{i}=1)\leq\rho$ for every $i$ , where $0\leq\rho<1/2$ . If $O_{i}=0$ , then

|Y_{i}-p(X_{i})|\leq\sigma.

Conditional on $(X_{1:M},O_{1:M})$ , the inlier errors and outlier labels may be chosen arbitrarily, and may depend on $p$ , subject only to this inlier bound. The algorithm observes the batch and is given $n,d,\varepsilon,\delta$ , the design law, and the valid upper bound $\rho$ , but it does not observe the $O_{i}$ and is not given $p$ or $\sigma$ . Every probability statement is over $(X_{1:M},O_{1:M})$ and holds uniformly over all admissible conditional choices of the labels. We write $\left\lVert q\right\rVert_{\infty}:=\sup_{\bm{x}\in[-1,1]^{n}}|q(\bm{x})|$ .

The unresolved tradeoff in Arora et al. [1] is summarized below. Their Theorem 3.1 (ESA version) achieves the target degree exponents but returns error $(2+\varepsilon)\sigma+\eta$ for $\eta>0$ , with a call bound that can be written uniformly as $O(1+\log_{1/\varepsilon}(1+\left\lVert p\right\rVert_{\infty}/\eta))$ . Their randomized scale-independent result, ESA Theorem 5.1, corresponds to Theorem 6.1 of arXiv:2403.09465v1; its deterministic core, ESA Theorem 5.2, corresponds to v1 Theorem 6.4.

Table 1: The sample-versus-scale tradeoff. The grid has

m^{n}

cells; its least cell mass determines the sample count under each design.

Method	Grid scale $m$	$L^{\infty}$ error	Optimization dependence
Arora et al., ESA Thm. 3.1	$m=O_{n}(d/\varepsilon)$	$(2+\varepsilon)\sigma+\eta$	$O(1+\log_{1/\varepsilon}(1+\left\lVert p\right\rVert_{\infty}/\eta))$
Arora et al., ESA Thm. 5.1	$m=\Omega_{n}(d^{2n+1}/\varepsilon)$	$(2+\varepsilon)\sigma$	independent of signal scale
This work	$m=O_{n,\rho}(d/\varepsilon)$	$(2+\varepsilon)\sigma$	at most $1+T$ LP-oracle calls

Remark 1.9 of the ESA version (Remark 1.6 of arXiv v1) asks whether the optimal-degree sample rates and the pure $(2+\varepsilon)\sigma$ error can be combined without scale-dependent refinement. The improvement requires a different weighting and norming primitive, not merely a retuning of constants.

We work in an exact-real LP-oracle model. Real arithmetic and comparisons, exact access to and comparison with the prescribed algebraic Chebyshev endpoints, and calls to an exact LP optimizer are primitives. Any optimizer returned by the oracle is admissible. We count oracle calls, LP combinatorial description size, and arithmetic work outside the oracle separately; we make no end-to-end finite-precision or bit-complexity claim for arbitrary real-valued continuous-design inputs.

The following theorem resolves the stated tradeoff in this model. The algorithm and the predetermined refinement budget are specified in Section 2.

Theorem 1.1 (Main theorem).

Fix integers $n,d\geq 1$ , $0\leq\rho<1/2$ , $0<\delta\leq\varepsilon\leq 1/2$ , and $\sigma\geq 0$ . Under the statistical model above, there is an algorithm that is not given $\sigma$ and has the following guarantees.

1.
Under product-Chebyshev locations it uses
$M_{C}=O_{n,\rho}\!\left((d/\varepsilon)^{n}\log(d/\delta)\right)$
samples. Under normalized uniform locations it uses
$M_{U}=O_{n,\rho}\!\left((d/\varepsilon)^{2n}\log(d/\delta)\right)$
samples.
2.
With probability at least $1-\delta$ , it outputs $\widehat{p}\in\mathcal{P}_{d,n}$ satisfying
$\left\lVert\widehat{p}-p\right\rVert_{\infty}\leq(2+\varepsilon)\sigma.$
In particular, when $\sigma=0$ , the same event gives $\widehat{p}=p$ identically.
3.
On every input, the algorithm makes at most $1+T$ exact-LP oracle calls, where the predetermined integer $T=O_{n,\rho}(\log(d/\varepsilon))$ is independent of $p$ and $\sigma$ . On the no-empty-cell branch it makes exactly $1+T$ calls. For fixed $n,\rho$ , the LP descriptions and all work outside the oracle calls are polynomial in the corresponding sample count $M=M_{C}$ or $M=M_{U}$ .

Here optimality refers only to the dependence on $d$ for fixed dimension, fixed accuracy, fixed positive contamination rate, and constant success probability. We do not claim jointly optimal dependence on $n,\varepsilon,\delta,\rho$ ; under uniform sampling the upper bound retains the displayed occupancy logarithm. The case $d=0$ is recorded in Appendix A.

Proof overview.

Use the Chebyshev partition for both location laws, but assign every cell its product-Chebyshev mass $m^{-n}$ in the LAD objective. An arbitrary-point $L^{1}(\nu)$ norming lemma turns the strict inlier majority in each cell into a coercive LAD lower bound with a positive $L^{1}$ coefficient. Its multivariate proof tensorizes the reproducing kernel and cell-supremum sum, not a representative-selection operator: each representative coordinate may depend on the full cell index. This yields $\left\lVert p^{(0)}-p\right\rVert_{\infty}\leq O_{n,\rho}(d^{n}\sigma)$ . A fixed number of median refinements then reaches $(2+\varepsilon)\sigma$ . Randomness is used only to ensure that every cell is occupied and has an inlier majority; the deterministic argument thereafter applies simultaneously to every iterate.

2 Partition and algorithm

We now specify the common product grid, weighted-LAD initializer, and fixed-budget median refinement used for both designs. The design law affects only the batch size; the deterministic optimization steps are shared.

For a positive integer $r$ , write $[r]:=\{1,\ldots,r\}$ . For a positive integer $m$ , partition $[0,\pi]$ into intervals $J_{j}=[(j-1)\pi/m,j\pi/m]$ , $j\in[m]$ . Under $x=\cos\theta$ , these induce the Chebyshev intervals

I_{j}=\left[\cos\frac{j\pi}{m},\cos\frac{(j-1)\pi}{m}\right]

and the product cells $C_{\bm{j}}=I_{j_{1}}\times\cdots\times I_{j_{n}}$ , indexed by $\bm{j}\in[m]^{n}$ . Let $\mathcal{C}_{m}:=\{C_{\bm{j}}:\bm{j}\in[m]^{n}\}$ . Closed cells are used in the analysis. A fixed half-open convention assigns any location on a common boundary to one cell, so the algorithm is defined everywhere. Every cell in $\mathcal{C}_{m}$ has $\nu$ -mass $m^{-n}$ .

Set

\alpha=\frac{1+2\rho}{4},\qquad g=1-2\alpha=\frac{1-2\rho}{2},\qquad\zeta=\alpha-\rho=\frac{g}{2},\qquad\beta=\frac{\varepsilon}{12}.

(2.1)

Thus $1/4\leq\alpha<1/2$ , $0<g\leq 1/2$ , $0<\zeta\leq 1/4$ , and $0<\beta\leq 1/24$ . Choose once and for all a constant $A_{n}\geq 1$ , depending only on $n$ , as guaranteed by Corollary 3.4, and take $m$ to be the least positive integer satisfying

m\geq\max\left\{1,\frac{A_{n}d}{\zeta},\frac{6\pi nd}{\beta}\right\}.

(2.2)

Since $m$ is the least such integer and $0<\varepsilon\leq 1/2$ ,

m=\Theta_{n,\rho}(d/\varepsilon).

(2.3)

Set

\gamma:=\frac{\pi nd}{m}.

(2.4)

The choice of $m$ gives $\gamma\leq\beta/6<1$ . Use

M=\begin{cases}\left\lceil C_{\rho}m^{n}\log(2m^{n}/\delta)\right\rceil,&\text{for product-Chebyshev locations},\\ \left\lceil C_{\rho}m^{2n}\log(2m^{n}/\delta)\right\rceil,&\text{for uniform locations},\end{cases}

(2.5)

where $C_{\rho}:=16/(1-2\rho)^{2}$ , as justified in Lemma 6.1. Thus $M=M_{C}$ for the product-Chebyshev design and $M=M_{U}$ for the uniform design.

For $C\in\mathcal{C}_{m}$ , let $S_{C}=\{i:X_{i}\in C\}$ , with membership interpreted according to the fixed boundary convention, and let $N_{C}=|S_{C}|$ . For the analysis, also set

B_{C}:=\{i\in S_{C}:O_{i}=1\},\qquad G_{C}:=S_{C}\setminus B_{C}.

The algorithm does not observe these two sets. Call the sample set good if every $N_{C}$ is positive and $|B_{C}|/N_{C}\leq\alpha$ for every $C\in\mathcal{C}_{m}$ .

The algorithm first checks for an empty cell and, if one exists, returns $\widehat{p}:=0$ without calling the LP oracle. Otherwise it defines the weighted LAD initializer by

p^{(0)}\in\arg\min_{q\in\mathcal{P}_{d,n}}\mathcal{L}(q),\qquad\mathcal{L}(q):=\frac{1}{m^{n}}\sum_{C\in\mathcal{C}_{m}}\frac{1}{N_{C}}\sum_{i\in S_{C}}|q(X_{i})-Y_{i}|.

(2.6)

The cell weight is $m^{-n}$ , regardless of the location law.

For each cell fix a representative $a_{C}\in C$ , for instance the observed location of its smallest-index sample. Let $T$ be the least nonnegative integer such that

\beta^{T}\frac{4(2d+1)^{n}}{g}\leq\frac{\varepsilon}{2}.

(2.7)

For $t=0,\ldots,T-1$ , let $\widetilde{Y}_{C,t}$ be any median of the residual labels

\{Y_{i}-p^{(t)}(X_{i}):i\in S_{C}\}.

Here a median is any number for which at least half the observations lie on each weak side. Compute

r_{t}\in\arg\min_{r\in\mathcal{P}_{d,n}}\max_{C\in\mathcal{C}_{m}}|r(a_{C})-\widetilde{Y}_{C,t}|,\qquad p^{(t+1)}=p^{(t)}+r_{t}.

(2.8)

On this branch it returns $\widehat{p}:=p^{(T)}$ . Both objectives attain their minima, and any optimizer returned by the LP oracle is admissible: Corollary 3.4 makes the full-sample evaluation functional a norm, while Lemma 5.1 with $\gamma<1$ does the same for representative evaluation. Details and LP sizes appear in Proposition 6.2. Consequently every input uses at most $1+T$ LP-oracle calls, and the no-empty-cell branch uses exactly $1+T$ .

3 Product-Chebyshev $L^{1}$ norming with arbitrary cell representatives

This section proves the deterministic norming inequality underlying the initializer. We lift to the torus, establish localized kernel bounds, and pass from arbitrary representatives to arbitrary finite multisets. The proofs are included here because this norming chain is the main new analytic ingredient.

For $q\in\mathcal{P}_{d,n}$ , write

Q(\bm{\theta}):=q(\cos\theta_{1},\ldots,\cos\theta_{n}).

(3.1)

Then $Q$ is an even trigonometric polynomial of degree at most $d$ in each coordinate. Set $\mathbb{T}:=\mathbb{R}/(2\pi\mathbb{Z})$ and let $d\mu_{\mathbb{T}}(t)=dt/(2\pi)$ be normalized Haar measure; product torus norms use $\mu_{\mathbb{T}}^{\otimes n}$ . We use the conventions

\widehat{f}(\bm{k})=\int_{\mathbb{T}^{n}}f(\bm{\theta})e^{-i\bm{k}\cdot\bm{\theta}}\,d\mu_{\mathbb{T}}^{\otimes n}(\bm{\theta}),\qquad(f*g)(\bm{\theta})=\int_{\mathbb{T}^{n}}f(\bm{\theta}-\bm{u})g(\bm{u})\,d\mu_{\mathbb{T}}^{\otimes n}(\bm{u}).

After even $2\pi$ -periodic extension, this normalization gives the exact identity

\left\lVert Q\right\rVert_{L^{1}(\mathbb{T}^{n})}=\frac{1}{\pi^{n}}\int_{[0,\pi]^{n}}|Q(\bm{\theta})|\,d\bm{\theta}=\left\lVert q\right\rVert_{L^{1}(\nu)}.

(3.2)

We first construct the localized reproducing kernel used in the arbitrary-representative estimate.

Lemma 3.1 (One-dimensional kernel bounds).

For every integer $N\geq 1$ , let

F_{N}(t)=\frac{1}{N}\left(\frac{\sin(Nt/2)}{\sin(t/2)}\right)^{2}=\sum_{|k|<N}\left(1-\frac{|k|}{N}\right)e^{ikt}

be the Fejér kernel, with the quotient defined by continuous extension at $2\pi\mathbb{Z}$ , so $F_{N}(2\pi\ell)=N$ . For every integer $d\geq 1$ , set $V_{d}=2F_{2d}-F_{d}$ . Then

\widehat{V}_{d}(k)=1\quad(|k|\leq d),\qquad\left\lVert V_{d}\right\rVert_{1}\leq 3,\qquad\left\lVert V_{d}^{\prime}\right\rVert_{1}\leq Cd

(3.3)

for an absolute constant $C$ .

Proof.

We first verify reproduction from the Fourier multipliers and then estimate the derivative directly in the spatial variable. For $|k|<d$ , the multiplier of $V_{d}$ is

2\left(1-\frac{|k|}{2d}\right)-\left(1-\frac{|k|}{d}\right)=1,

and for $|k|=d$ it is $2(1-1/2)=1$ . This proves reproduction on all frequencies $|k|\leq d$ , including the endpoints. Since $F_{N}\geq 0$ and $\left\lVert F_{N}\right\rVert_{1}=1$ , the triangle inequality gives $\left\lVert V_{d}\right\rVert_{1}\leq 3$ .

It remains to prove the $L^{1}$ derivative bound without a logarithmic loss. On $|t|\leq N^{-1}$ , differentiating the finite Fourier expansion gives

|F_{N}^{\prime}(t)|\leq\sum_{|k|<N}|k|\left(1-\frac{|k|}{N}\right)\leq CN^{2}.

For $N^{-1}\leq|t|\leq\pi$ , differentiating the sine quotient and using $|\sin(t/2)|\geq|t|/\pi$ gives

|F_{N}^{\prime}(t)|\leq C\left(|t|^{-2}+N^{-1}|t|^{-3}\right).

Both regions contribute $O(N)$ after integration, so $\left\lVert F_{N}^{\prime}\right\rVert_{1}=O(N)$ . Applying this estimate to $V_{d}=2F_{2d}-F_{d}$ completes the proof. ∎

Lemma 3.2 (Local supremum and endpoint Bernstein bounds).

There exists $B_{n}<\infty$ , depending only on $n$ , with the following property. Let $d, m$ be integers with $m\geq d\geq 1$ , set $h=\pi/m$ , and let $H$ be a trigonometric polynomial on $\mathbb{T}^{n}$ of degree at most $d$ in each coordinate. If $\mathcal{R}_{m}$ is the product partition of $\mathbb{T}^{n}$ with $2m$ intervals of length $h$ in each coordinate, then

	$\displaystyle\left(\frac{h}{2\pi}\right)^{n}\sum_{R\in\mathcal{R}_{m}}\sup_{R}\|H\|$	$\displaystyle\leq B_{n}\left\lVert H\right\rVert_{L^{1}(\mathbb{T}^{n})},$		(3.4)
	$\displaystyle\left\lVert\partial_{k}H\right\rVert_{L^{1}(\mathbb{T}^{n})}$	$\displaystyle\leq B_{n}d\left\lVert H\right\rVert_{L^{1}(\mathbb{T}^{n})}\qquad(k\in[n]).$		(3.5)

Proof.

We first obtain a shift-uniform one-dimensional cell-supremum bound, then tensorize it, and finally differentiate one kernel factor. For every absolutely continuous periodic function $v$ and every interval $I$ of length $h$ ,

h\sup_{I}|v|\leq\int_{I}|v(t)|\,dt+h\int_{I}|v^{\prime}(t)|\,dt.

Summing over the $2m$ torus intervals and applying Lemma 3.1 shows, uniformly in $u$ , that

\frac{h}{2\pi}\sum_{I}\sup_{t\in I}|V_{d}(t-u)|\leq\left\lVert V_{d}\right\rVert_{1}+h\left\lVert V_{d}^{\prime}\right\rVert_{1}\leq C_{0},

(3.6)

where $C_{0}$ is an absolute constant and we used $hd\leq\pi$ .

Let $W_{d}(\bm{\theta})=\prod_{k=1}^{n}V_{d}(\theta_{k})$ . The multiplier identity gives $H=H*W_{d}$ . Hence Tonelli’s theorem implies

		$\displaystyle\left(\frac{h}{2\pi}\right)^{n}\sum_{R\in\mathcal{R}_{m}}\sup_{\bm{\theta}\in R}\|H(\bm{\theta})\|$
		$\displaystyle\quad\leq\int_{\mathbb{T}^{n}}\|H(\bm{u})\|\left[\left(\frac{h}{2\pi}\right)^{n}\sum_{R\in\mathcal{R}_{m}}\sup_{\bm{\theta}\in R}\|W_{d}(\bm{\theta}-\bm{u})\|\right]\,d\mu_{\mathbb{T}}^{\otimes n}(\bm{u}).$

The bracket factors by coordinate, and each factor is bounded by $C_{0}$ in (3.6). This proves (3.4) with a constant depending only on $n$ . Notice that the factorization applies to the kernel, not to a rule selecting representatives.

Similarly,

\partial_{k}H=H*\left(V_{d}^{\prime}\otimes\bigotimes_{\ell\neq k}V_{d}\right).

Young’s inequality and Lemma 3.1 give $\left\lVert\partial_{k}H\right\rVert_{1}\leq Cd\,3^{n-1}\left\lVert H\right\rVert_{1}$ . Enlarging $B_{n}$ , if necessary, proves (3.5) simultaneously with (3.4). ∎

Lemma 3.3 (Arbitrary representatives).

There exists $A_{n}\geq 1$ , depending only on $n$ , such that the following holds for all integers $m\geq d\geq 1$ . For every $q\in\mathcal{P}_{d,n}$ , choose an arbitrary representative $\xi_{C}\in C$ for each $C\in\mathcal{C}_{m}$ , and define $q^{\sharp}$ on the fixed half-open partition to be constant on $C$ , with value $q(\xi_{C})$ . Then

\left\lVert q-q^{\sharp}\right\rVert_{L^{1}(\nu)}\leq A_{n}\frac{d}{m}\left\lVert q\right\rVert_{L^{1}(\nu)}.

(3.7)

The representatives may be adversarial; in particular, their coordinates may depend jointly on the full cell index.

Proof.

We transfer the representatives to angular coordinates, reflect them to the torus, and integrate a coordinatewise path estimate. For $C=C_{\bm{j}}$ , map its representative to

\bm{\eta}_{C}:=(\arccos\xi_{C,1},\ldots,\arccos\xi_{C,n})\in J_{j_{1}}\times\cdots\times J_{j_{n}}.

Reflect the angular partition and these representatives evenly to $\mathbb{T}^{n}$ . On each reflected product interval $R$ , let $Q^{\sharp}$ have the constant value $Q(\bm{\eta}_{R})$ . For $\bm{\theta}\in R$ , a coordinatewise line-segment path within $R$ gives

|Q(\bm{\theta})-Q(\bm{\eta}_{R})|\leq h\sum_{k=1}^{n}\sup_{R}|\partial_{k}Q|.

Integrating over all cells, using (3.4) for each $\partial_{k}Q$ , and then applying (3.5), we obtain

	$\displaystyle\left\lVert Q-Q^{\sharp}\right\rVert_{1}$	$\displaystyle\leq h\sum_{k=1}^{n}\left(\frac{h}{2\pi}\right)^{n}\sum_{R\in\mathcal{R}_{m}}\sup_{R}\|\partial_{k}Q\|$
		$\displaystyle\leq B_{n}h\sum_{k=1}^{n}\left\lVert\partial_{k}Q\right\rVert_{1}\leq\pi nB_{n}^{2}\frac{d}{m}\left\lVert Q\right\rVert_{1}.$

Choose $A_{n}\geq\max\{1,\pi nB_{n}^{2}\}$ . Up to measure-zero boundaries, $\mathbb{T}^{n}$ decomposes into $2^{n}$ reflected copies of $[0,\pi]^{n}$ ; hence the normalized identity (3.2) applies equally to $Q-Q^{\sharp}$ and $q-q^{\sharp}$ . This proves (3.7). ∎

Corollary 3.4 (Arbitrary multisets in every cell).

Let $A_{n}$ be as in Lemma 3.3. For every $0<\zeta<1$ , every integer $m\geq A_{n}d/\zeta$ , and every family $A=(A_{C})_{C\in\mathcal{C}_{m}}$ of nonempty finite multisets $A_{C}\subset C$ , define

\Phi_{A}(q):=\frac{1}{m^{n}}\sum_{C\in\mathcal{C}_{m}}\frac{1}{|A_{C}|}\sum_{z\in A_{C}}|q(z)|.

Here cardinalities and sums count multiplicity. Simultaneously for all $q\in\mathcal{P}_{d,n}$ and all such families,

(1-\zeta)\left\lVert q\right\rVert_{L^{1}(\nu)}\leq\Phi_{A}(q)\leq(1+\zeta)\left\lVert q\right\rVert_{L^{1}(\nu)}.

(3.8)

Proof.

For a fixed cell, the average of $|q|$ over $A_{C}$ lies between the minimum and maximum of $|q|$ on that cell. Since the cell is connected and $|q|$ is continuous, the average equals $|q(\xi_{C})|$ for some $\xi_{C}\in C$ . Because each cell has $\nu$ -mass $m^{-n}$ , these representatives satisfy

\Phi_{A}(q)=\frac{1}{m^{n}}\sum_{C\in\mathcal{C}_{m}}|q(\xi_{C})|=\left\lVert q^{\sharp}\right\rVert_{L^{1}(\nu)}.

Thus $\big|\Phi_{A}(q)-\left\lVert q\right\rVert_{L^{1}(\nu)}\big|\leq\left\lVert q^{\sharp}-q\right\rVert_{L^{1}(\nu)}$ , and Lemma 3.3 proves (3.8). ∎

Remark 3.5 (Why a sufficiently fine grid is necessary).

In one dimension, take $m=d$ and let $T_{d}$ be the first-kind Chebyshev polynomial, defined by $T_{d}(\cos\theta)=\cos(d\theta)$ . For $j\in[d]$ , let $\theta_{j}=(j-1/2)\pi/d$ . The point $\xi_{j}=\cos\theta_{j}$ belongs to $I_{j}$ and satisfies $T_{d}(\xi_{j})=0$ . Choosing these representatives makes every discrete value vanish although $T_{d}\not\equiv 0$ . Thus the constant oversampling required for a relative norming estimate cannot be replaced by the bare condition $m=d$ .

4 Signal-scale-independent weighted-LAD initialization

On the good event, arbitrary-multiset norming turns cellwise inlier majorities into a coercive LAD lower bound. An $L^{1}$ -to- $L^{\infty}$ inequality then gives an initializer whose tuning does not use the unknown signal or noise scale.

Proposition 4.1 (Coercive LAD bound and initialization).

On a good sample set, for every $e\in\mathcal{P}_{d,n}$ ,

\mathcal{L}(p+e)-\mathcal{L}(p)\geq\frac{g}{2}\left\lVert e\right\rVert_{L^{1}(\nu)}-2\sigma.

(4.1)

Consequently, $\mathcal{L}$ is coercive and attains its minimum. Every minimizer $p^{(0)}$ satisfies

\left\lVert p^{(0)}-p\right\rVert_{L^{1}(\nu)}\leq\frac{4\sigma}{g}.

(4.2)

Combining this with the $L^{1}$ -to- $L^{\infty}$ bound below gives

E_{0}:=\left\lVert p^{(0)}-p\right\rVert_{\infty}\leq\frac{4(2d+1)^{n}}{g}\,\sigma.

(4.3)

When $\sigma=0$ , every LAD minimizer equals $p$ identically.

Proof.

We compare the objective at $p+e$ and $p$ , apply Corollary 3.4 separately to the inlier and outlier locations, and then convert the resulting $L^{1}(\nu)$ bound to $L^{\infty}$ . Fix $e\in\mathcal{P}_{d,n}$ . For an inlier $i$ , the reverse triangle inequality gives

|p(X_{i})+e(X_{i})-Y_{i}|-|p(X_{i})-Y_{i}|\geq|e(X_{i})|-2\sigma.

For an outlier, with no restriction on its label,

|p(X_{i})+e(X_{i})-Y_{i}|-|p(X_{i})-Y_{i}|\geq-|e(X_{i})|.

The accumulated noise term is at most

\frac{2\sigma}{m^{n}}\sum_{C\in\mathcal{C}_{m}}\frac{|G_{C}|}{N_{C}}\leq 2\sigma.

Thus summing the samplewise inequalities gives

\mathcal{L}(p+e)-\mathcal{L}(p)\geq\frac{1}{m^{n}}\sum_{C\in\mathcal{C}_{m}}\frac{1}{N_{C}}\left(\sum_{i\in G_{C}}|e(X_{i})|-\sum_{i\in B_{C}}|e(X_{i})|\right)-2\sigma.

(4.4)

Every $G_{C}$ is nonempty and $|G_{C}|/N_{C}\geq 1-\alpha$ . Since $N_{C}^{-1}=(|G_{C}|/N_{C})|G_{C}|^{-1}$ , applying Corollary 3.4 to the family of inlier-location multisets gives

\frac{1}{m^{n}}\sum_{C\in\mathcal{C}_{m}}\frac{1}{N_{C}}\sum_{i\in G_{C}}|e(X_{i})|\geq(1-\alpha)(1-\zeta)\left\lVert e\right\rVert_{L^{1}(\nu)}.

(4.5)

For each cell, let $A_{C}$ be the multiset of its outlier locations when $B_{C}\neq\varnothing$ , and otherwise let $A_{C}$ consist of one arbitrary dummy point in $C$ . Cellwise,

\frac{1}{N_{C}}\sum_{i\in B_{C}}|e(X_{i})|\leq\alpha\frac{1}{|A_{C}|}\sum_{z\in A_{C}}|e(z)|:

for a nonempty $B_{C}$ this factors out $|B_{C}|/N_{C}\leq\alpha$ , while for an empty $B_{C}$ the left side is zero. Applying Corollary 3.4 to the $A_{C}$ ’s yields

\frac{1}{m^{n}}\sum_{C\in\mathcal{C}_{m}}\frac{1}{N_{C}}\sum_{i\in B_{C}}|e(X_{i})|\leq\alpha(1+\zeta)\left\lVert e\right\rVert_{L^{1}(\nu)}.

(4.6)

Combining (4.4)–(4.6),

\mathcal{L}(p+e)-\mathcal{L}(p)\geq\bigl((1-\alpha)(1-\zeta)-\alpha(1+\zeta)\bigr)\left\lVert e\right\rVert_{L^{1}(\nu)}-2\sigma.

The coefficient is $1-2\alpha-\zeta=g/2>0$ , proving (4.1). Since $\left\lVert\cdot\right\rVert_{L^{1}(\nu)}$ is a norm on the finite-dimensional space $\mathcal{P}_{d,n}$ , its closed bounded sets are compact. Thus (4.1) makes every sublevel set of $\mathcal{L}$ compact, and continuity gives existence of a minimizer. For any minimizer $p^{(0)}$ , substitute $e=p^{(0)}-p$ into (4.1) and use $\mathcal{L}(p^{(0)})\leq\mathcal{L}(p)$ to obtain (4.2).

To convert (4.2) to a uniform bound, reproduce the even periodic lift of $e$ with the product Dirichlet kernel $D_{d}^{\otimes n}$ , where $D_{d}(t)=\sum_{|k|\leq d}e^{ikt}$ . Hence

\left\lVert q\right\rVert_{\infty}\leq\left\lVert D_{d}^{\otimes n}\right\rVert_{\infty}\left\lVert q\right\rVert_{L^{1}(\nu)}=(2d+1)^{n}\left\lVert q\right\rVert_{L^{1}(\nu)}\qquad(q\in\mathcal{P}_{d,n}).

(4.7)

Applying (4.7) to (4.2) proves (4.3). If $\sigma=0$ , the positive coefficient $g/2$ forces every minimizer to have $\left\lVert p^{(0)}-p\right\rVert_{L^{1}(\nu)}=0$ , so $p^{(0)}=p$ identically. ∎

The following example shows that cellwise majority alone is insufficient. Take $n=1,d=2,m=2,p=0,\sigma=0$ . Put two inliers at each of $-1/2$ and $1/2$ , and one outlier at each of $-1$ and $1$ . For $K>0$ , give the outliers labels from $q(x)=K(x^{2}-1/4)$ . Each cell has outlier fraction $1/3$ , but the weighted LAD objective is zero at $q$ and equals $K/4$ at $p$ . The condition (2.2) rules out exactly this type of concentration.

More generally, at zero noise the obstruction to weighted LAD is a nonzero direction whose weighted evaluation mass on the corrupted observations is at least its mass on the inliers: scaling the corrupted labels along that direction makes the truth non-unique or suboptimal. The coercive bound (4.1) excludes every such direction simultaneously: its right side is independent of the outlier-label magnitudes, while $N_{C}^{-1}$ normalizes each cell separately.

5 Median refinement and contraction

We next convert the initializer bound into the target error. A cell-oscillation bound and a median-witness lemma yield a uniform one-step contraction, which is iterated a predetermined number of times.

Lemma 5.1 (Cell oscillation).

For every $q\in\mathcal{P}_{d,n}$ and every $C\in\mathcal{C}_{m}$ ,

\sup_{\bm{x},\bm{z}\in C}|q(\bm{x})-q(\bm{z})|\leq\gamma\left\lVert q\right\rVert_{\infty}.

(5.1)

Proof.

For the angular lift $Q$ , the trigonometric Bernstein inequality in each coordinate gives $\left\lVert\partial_{k}Q\right\rVert_{\infty}\leq d\left\lVert Q\right\rVert_{\infty}$ . Two points in the same angular product cell differ by at most $\pi/m$ in each coordinate. Integrating along coordinatewise line segments gives (5.1). ∎

Lemma 5.2 (Median witness).

Let $I$ be a nonempty finite index set, let $X_{i}\in C$ and $Z_{i}\in\mathbb{R}$ for $i\in I$ , where $C\in\mathcal{C}_{m}$ , and let $G\subseteq I$ satisfy $|G|>|I|/2$ . If $e\in\mathcal{P}_{d,n}$ and $|Z_{i}-e(X_{i})|\leq\sigma$ for every $i\in G$ , then any median $\widetilde{Y}$ of $(Z_{i})_{i\in I}$ has a witness $z_{C}\in C$ such that

|e(z_{C})-\widetilde{Y}|\leq\sigma.

(5.2)

The witness need not be one of the sample locations $X_{i}$ .

Proof.

Let $I_{-}:=\{i\in I:Z_{i}\leq\widetilde{Y}\}$ and $I_{+}:=\{i\in I:Z_{i}\geq\widetilde{Y}\}$ . The median property gives $|I_{-}|,|I_{+}|\geq|I|/2>|I\setminus G|$ , so choose $i_{-}\in I_{-}\cap G$ and $i_{+}\in I_{+}\cap G$ . Write $Z_{-}=Z_{i_{-}}$ , $Z_{+}=Z_{i_{+}}$ , $x_{-}=X_{i_{-}}$ , and $x_{+}=X_{i_{+}}$ . The noise bounds give the one-sided consequences

e(x_{-})\leq\widetilde{Y}+\sigma,\qquad e(x_{+})\geq\widetilde{Y}-\sigma.

If either value already lies in $[\widetilde{Y}-\sigma,\widetilde{Y}+\sigma]$ , that location proves the claim. Otherwise $e(x_{-})<\widetilde{Y}-\sigma$ and $e(x_{+})>\widetilde{Y}+\sigma$ . The line segment from $x_{-}$ to $x_{+}$ lies in the rectangular cell, and continuity supplies a point on it at which $e=\widetilde{Y}$ . This continuity witness need not equal any $X_{i}$ . ∎

Proposition 5.3 (One-step contraction).

On a good sample set, let $e_{t}=p-p^{(t)}$ , $E_{t}=\left\lVert e_{t}\right\rVert_{\infty}$ , and define $r_{t}$ by (2.8). If $\gamma\leq\beta/(2+\beta)$ , then

E_{t+1}\leq(2+\beta)\sigma+\beta E_{t}.

(5.3)

Proof.

The median witness first controls the target residual at an unknown point in each cell. Oscillation moves this control to the fixed representatives; minimax optimality and a second oscillation step then give a term $\gamma E_{t+1}$ , which we absorb.

For an inlier,

\left|Y_{i}-p^{(t)}(X_{i})-e_{t}(X_{i})\right|=|Y_{i}-p(X_{i})|\leq\sigma.

The good event and Lemma 5.2 therefore give, in every cell, a point $z_{C}$ such that $|e_{t}(z_{C})-\widetilde{Y}_{C,t}|\leq\sigma$ . By Lemma 5.1,

|e_{t}(a_{C})-\widetilde{Y}_{C,t}|\leq\sigma+\gamma E_{t}.

Using $e_{t}$ as the feasible comparison polynomial in (2.8) shows that its optimal value $\lambda_{t}$ is at most $\sigma+\gamma E_{t}$ . For every $C\in\mathcal{C}_{m}$ , the triangle inequality therefore gives

|(r_{t}-e_{t})(a_{C})|\leq|r_{t}(a_{C})-\widetilde{Y}_{C,t}|+|e_{t}(a_{C})-\widetilde{Y}_{C,t}|\leq 2(\sigma+\gamma E_{t}).

Hence

\max_{C\in\mathcal{C}_{m}}|(r_{t}-e_{t})(a_{C})|\leq 2\sigma+2\gamma E_{t}.

(5.4)

Put $q_{t}=r_{t}-e_{t}$ and $R=\left\lVert q_{t}\right\rVert_{\infty}=E_{t+1}$ . Choose a maximizer $\bm{x}_{\star}\in C_{\star}$ . By Lemma 5.1 and (5.4),

R=|q_{t}(\bm{x}_{\star})|\leq|q_{t}(a_{C_{\star}})|+\gamma R\leq 2\sigma+2\gamma E_{t}+\gamma R.

Thus

R\leq\frac{2}{1-\gamma}\sigma+\frac{2\gamma}{1-\gamma}E_{t}.

The condition $(2+\beta)\gamma\leq\beta$ bounds the two coefficients by $2+\beta$ and $\beta$ , respectively, proving (5.3). ∎

The choice (2.2) gives $\gamma\leq\beta/6\leq\beta/(2+\beta)$ . Iterating (5.3) and using (4.3),

E_{T}\leq\frac{2+\beta}{1-\beta}\sigma+\beta^{T}E_{0}.

(5.5)

Since $\beta=\varepsilon/12\leq 1/24$ ,

\frac{2+\beta}{1-\beta}=2+\frac{3\beta}{1-\beta}\leq 2+\frac{\varepsilon}{2}.

(5.6)

By (2.7) and (4.3),

\beta^{T}E_{0}\leq\beta^{T}\frac{4(2d+1)^{n}}{g}\,\sigma\leq\frac{\varepsilon}{2}\sigma.

(5.7)

Equations (5.5)–(5.7) prove the target $(2+\varepsilon)\sigma$ error on every good sample set. No step divides by $\sigma$ ; at $\sigma=0$ , Proposition 4.1 already gives $E_{0}=0$ . Moreover, after the good event is fixed the contraction is deterministic and uniform over $e_{t}$ , so reusing the same samples introduces no adaptive probability issue.

6 Probability, sample complexity, and computational scope

We now show that the good event holds with high probability, derive the two design-specific sample bounds, and delimit the exact-real LP-oracle complexity. The only design-dependent quantity is the least cell mass.

Lemma 6.1 (A good product grid).

Let $m, M$ be positive integers and $0<\delta\leq 1$ . Suppose the locations are i.i.d., the indicators satisfy the independence assumptions of Section 1, and every $C\in\mathcal{C}_{m}$ has probability $\pi_{C}$ , where $\pi_{\min}:=\min_{C\in\mathcal{C}_{m}}\pi_{C}>0$ . With $C_{\rho}=16/(1-2\rho)^{2}$ ,

M\geq C_{\rho}\pi_{\min}^{-1}\log\frac{2m^{n}}{\delta}

(6.1)

makes the sample set good with probability at least $1-\delta$ .

Proof.

For a fixed cell, a Chernoff bound gives

\mathbb{P}[N_{C}<M\pi_{C}/2]\leq e^{-M\pi_{C}/8}.

Conditional on the selected locations and on $N_{C}=s$ , the outlier indicators in the cell are independent Bernoulli variables with means at most $\rho$ . Hoeffding’s inequality therefore gives

\mathbb{P}[|B_{C}|>\alpha s\mid N_{C}=s]\leq e^{-2(\alpha-\rho)^{2}s}.

Consequently,

\mathbb{P}\!\left[|B_{C}|>\alpha N_{C},\ N_{C}\geq M\pi_{C}/2\right]\leq e^{-(\alpha-\rho)^{2}M\pi_{C}}.

Let $L=\log(2m^{n}/\delta)$ . Since $\alpha-\rho=(1-2\rho)/4$ , (6.1) bounds the two failure terms for each cell by $e^{-2L}$ and $e^{-L}$ , respectively. A union bound over $m^{n}$ cells gives total failure at most $m^{n}(e^{-L}+e^{-2L})\leq\delta$ . ∎

For product-Chebyshev locations, every cell has probability exactly

\pi_{\min}=m^{-n}.

(6.2)

For the normalized uniform law, the smallest one-dimensional Chebyshev cell is an endpoint cell and has probability

\frac{1-\cos(\pi/m)}{2}=\sin^{2}\frac{\pi}{2m}\geq m^{-2}.

(6.3)

Consequently, under the $n$ -dimensional uniform product distribution,

\pi_{\min}\geq m^{-2n}.

(6.4)

Combining Lemma 6.1 with (6.2) and (6.4) gives

M_{C}=O_{\rho}\!\left(m^{n}\log(m^{n}/\delta)\right),\qquad M_{U}=O_{\rho}\!\left(m^{2n}\log(m^{n}/\delta)\right).

(6.5)

For uniform designs, the conditional distribution inside a Chebyshev cell is not the Chebyshev law. No such assumption is used: Corollary 3.4 is deterministic and holds for every finite collection of locations in the cell. The design law affects only the occupancy probability.

Because $m=O_{n,\rho}(d/\varepsilon)$ , $d\geq 1$ , and $\delta\leq\varepsilon$ ,

\log(m^{n}/\delta)=O_{n,\rho}(\log(d/\delta)).

Substitution in (6.5), followed by the deterministic analysis of Sections 4 and 5, proves the statistical and error claims in Theorem 1.1.

Proposition 6.2 (LP size and computational scope).

Let $D=(d+1)^{n}$ . On the no-empty-cell branch, the initializer LP has $D+M$ variables, $2M$ residual constraints, and $O(MD)$ nonzero coefficients. Each of the $T$ refinement LPs has $D+1$ variables, $2m^{n}$ constraints, and $O(m^{n}D)$ nonzero coefficients. Every input uses at most $1+T$ LP-oracle calls. For fixed $n,\rho$ , these combinatorial description sizes and all work outside the oracle calls are polynomial in $M$ .

Proof.

Introduce one nonnegative slack for each absolute residual in (2.6). For (2.8), introduce a variable $\lambda$ and the two linear inequalities $-\lambda\leq r(a_{C})-\widetilde{Y}_{C,t}\leq\lambda$ for each cell. Each residual constraint contains at most $D+1$ potentially nonzero coefficients in the dense monomial representation, which gives the stated description bounds.

The norming estimate proves coercivity for the first LP. For the second, suppose $q(a_{C})=0$ for every $C\in\mathcal{C}_{m}$ , and choose a maximizer $x_{\star}\in C_{\star}$ . By Lemma 5.1, $\left\lVert q\right\rVert_{\infty}\leq\gamma\left\lVert q\right\rVert_{\infty}$ ; since $\gamma<1$ , this forces $q=0$ . Thus representative evaluation defines a norm on $\mathcal{P}_{d,n}$ . Finite-dimensional norm equivalence makes the translated minimax objective coercive, so both LP objectives attain their minima.

Since $m\geq d$ and $d\geq 1$ ,

(d+1)^{n}\leq 2^{n}m^{n}=O_{n}(M).

Moreover,

T=\left\lceil\frac{\log(8(2d+1)^{n}/(g\varepsilon))}{\log(12/\varepsilon)}\right\rceil\leq 1+\frac{\log(8(2d+1)^{n}/(g\varepsilon))}{\log(12/\varepsilon)}=O_{n,\rho}(\log(d/\varepsilon))=O_{n,\rho}(\log M).

Assigning the $M$ samples to cells takes $O(nM\log m)$ comparisons after the grid is formed. In each refinement, naive evaluation of all residuals takes $O(M(d+1)^{n})$ arithmetic operations, and all cell medians can be found in $O(M\log M)$ comparisons, or in linear time by selection. Thus the work outside the LP-oracle calls is polynomial in $M$ .

The call budget and combinatorial LP structure contain no $\sigma$ , signal magnitude, or additive tolerance. When $\sigma>0$ , the call count is in particular independent of $\left\lVert p\right\rVert_{\infty}/\sigma$ and $1/\sigma$ . Numerical LP coefficients include the observed labels $Y_{i}$ , however, so their values and encoding lengths may depend on label scale. As stated in Section 1, no end-to-end finite-precision guarantee is claimed. ∎

This completes the proof of Theorem 1.1.

7 Significance, related work, and limitations

We compare the theorem with prior upper and lower bounds, identify the source of the improved degree exponent, and delimit the result’s scope. Extensions and boundary cases are collected in Appendix A.

In the stated exact-real LP-oracle model, Theorem 1.1 attains the target rates posed in Remark 1.9 of the ESA version of Arora et al. [1]. Their optimal-degree scheme retains an additive accuracy parameter and a scale-dependent refinement count, whereas their scale-independent initializer uses a much finer grid. Product-Chebyshev cell weighting instead gives

E_{0}\leq\frac{4(2d+1)^{n}}{g}\sigma,

so the refinement budget can be fixed in advance. The same coercive argument applies directly at $\sigma=0$ ; exact recovery is not obtained by taking a limit as $\sigma\downarrow 0$ .

The quantitative improvement comes from changing the norm targeted by the initializer. Here $d x$ denotes unnormalized Lebesgue measure on $[-1,1]^{n}$ , and $\lesssim_{n},\gtrsim_{n}$ suppress positive constants that depend only on $n$ . With Lebesgue-volume cell weights, ESA Theorems 1.11–1.12 of Arora et al. [1] (Theorems 1.8–1.9 in arXiv v1) give

\left\lVert q-q^{\sharp}\right\rVert_{L^{1}(dx)}\lesssim_{n}\frac{d}{m}\left\lVert q\right\rVert_{\infty}\lesssim_{n}\frac{d^{2n+1}}{m}\left\lVert q\right\rVert_{L^{1}(dx)}.

(7.1)

Thus a relative Lebesgue- $L^{1}$ proxy requires $m\gtrsim_{n}d^{2n+1}/\varepsilon$ . In contrast, Lemma 3.3 directly gives

\left\lVert q-q^{\sharp}\right\rVert_{L^{1}(\nu)}\lesssim_{n}\frac{d}{m}\left\lVert q\right\rVert_{L^{1}(\nu)}.

(7.2)

The remaining $d^{n}$ loss occurs only in the initializer’s $L^{1}(\nu)$ -to- $L^{\infty}$ conversion. It therefore affects the logarithmic refinement count, not the grid size or the sample exponent.

The proof therefore separates deterministic norming from random occupancy. In angular coordinates, arbitrary cell representatives discretize $L^{1}(\nu)$ with relative error $O_{n}(d/m)$ , independently of the location law or the conditional distribution within a cell. The law enters only through the least cell probability: $m^{-n}$ for Chebyshev sampling and $\Theta(m^{-2n})$ for uniform sampling. This produces the $d^{n}$ and $d^{2n}$ degree exponents, respectively.

For the lower-bound comparison, set $C=2+\varepsilon$ . At constant success probability exceeding $2/3$ , fixed $\varepsilon$ , and fixed $\rho>0$ , ESA Theorem 1.7 of Arora et al. [1] gives a constant $c=c(C,\rho)>0$ , independent of $d$ , and the distribution-free lower bound $\Omega((cd)^{n}\log d)$ . Thus the product-Chebyshev rate matches the known $d$ -dependence. Under uniform sampling, ESA Theorem 1.6 gives $c=c(C)>0$ and a lower bound $\Omega((cd)^{2n})$ for every outlier rate, including zero. The uniform upper bound therefore has the optimal polynomial exponent in $d$ , up to the occupancy logarithm. These fixed-parameter comparisons do not assert joint optimality in the other parameters.

Earlier work on robust algebraic curve fitting and polynomial regression includes Arora and Khot [2], Guruswami and Zuckerman [9], Daltrophe et al. [5]. The closest algorithmic precedents are Kane et al. [11], who combine arbitrary Chebyshev-cell representatives, weighted LAD, and median refinement in one dimension, and Arora et al. [1], who extend robust regression to several variables. The latter’s scale-independent Lebesgue-weighted initializer requires $m\gtrsim_{n}d^{2n+1}/\varepsilon$ . Our new step is the product-Chebyshev $L^{1}$ norming inequality for jointly chosen multivariate representatives, which gives the cellwise LAD bound at $m=O_{n,\rho}(d/\varepsilon)$ .

Adjacent robust-regression methods use different corruption models and loss criteria. Klivans et al. [12] allow adaptive replacement of complete covariate–label pairs under hypercontractivity and control population $L^{2}$ prediction loss. Diakonikolas et al. [7] treat strong contamination for general stochastic objectives and obtain approximate population critical points under gradient-regularity assumptions. Diakonikolas et al. [8] study Gaussian linear regression with full-pair replacement and Euclidean parameter error, while Prasad et al. [15] use robust gradient estimation for population-risk minimization under Huber contamination or heavy-tailed gradients. These settings and targets do not directly yield uniform recovery of a bounded-noise polynomial on a fixed cube under the present clean-design, label-corruption model.

These norming estimates are part of the Marcinkiewicz–Zygmund and Plancherel–Polya literature. Bounds for nonuniform grids and perturbed nodes are given in [16, 14]. De Marchi and Kroó [6] treat multivariate domains, using selected nodes and weights rather than arbitrary points in prescribed product cells. Other sampling-discretization results include [13, 4, 3], and Kämmerer [10] studies structured Chebyshev grids for noiseless reconstruction.

The argument does not settle the analogous arbitrary-representative question for unweighted Lebesgue $L^{1}(dx)$ ; in angular coordinates that norm carries the non-translation-invariant weight $\prod_{k}\sin\theta_{k}$ . This issue is unnecessary for Theorem 1.1, because the initializer may target $L^{1}(\nu)$ even under uniform locations. The theorem also assumes independent random outlier support and an exact-real LP oracle; it does not provide an end-to-end finite-precision guarantee. The source-version detail behind the median witness is recorded in Section A.2.

In summary, weighting cells by their product-Chebyshev mass separates deterministic norming from distribution-dependent occupancy. It yields the $d^{n}$ and $d^{2n}$ degree exponents without using $\sigma$ as an algorithmic input, under the statistical and computational model stated above.

References

[1] V. Arora, A. Bhattacharyya, M. Boban, V. Guruswami, and E. Kelman. Outlier robust multivariate polynomial regression. In 32nd Annual European Symposium on Algorithms (ESA 2024), volume 308 of LIPIcs, pages 12:1–12:17, 2024. doi:10.4230/LIPIcs.ESA.2024.12. Extended version: arXiv:2403.09465v1.
[2] S. Arora and S. Khot. Fitting algebraic curves to noisy data. Journal of Computer and System Sciences, 67(2):325–340, 2003. doi:10.1016/S0022-0000(03)00012-6.
[3] F. Dai, E. Kosov, and N. Murasko. Empirical approximation of $L_{p}$ norms. arXiv:2606.00347, 2026.
[4] F. Dai, E. Kosov, and V. Temlyakov. Some improved bounds in sampling discretization of integral norms. Journal of Functional Analysis, 285(4):109951, 2023. doi:10.1016/j.jfa.2023.109951.
[5] H. Daltrophe, S. Dolev, and Z. Lotker. Big data interpolation using functional representation. Acta Informatica, 55:213–225, 2018. doi:10.1007/s00236-016-0288-8.
[6] S. De Marchi and A. Kroó. Marcinkiewicz–Zygmund type results in multivariate domains. Acta Mathematica Hungarica, 154(1):69–89, 2018. doi:10.1007/s10474-017-0769-4.
[7] I. Diakonikolas, G. Kamath, D. Kane, J. Li, J. Steinhardt, and A. Stewart. SEVER: A robust meta-algorithm for stochastic optimization. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1596–1606, 2019. https://proceedings.mlr.press/v97/diakonikolas19a.html.
[8] I. Diakonikolas, W. Kong, and A. Stewart. Efficient algorithms and lower bounds for robust linear regression. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2745–2754, 2019. doi:10.1137/1.9781611975482.170.
[9] V. Guruswami and D. Zuckerman. Robust Fourier and polynomial curve fitting. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 751–759, 2016. doi:10.1109/FOCS.2016.75.
[10] L. Kämmerer. Constructing efficient spatial discretizations of spans of multivariate Chebyshev polynomials. arXiv:2406.03281, 2024.
[11] D. Kane, S. Karmalkar, and E. Price. Robust polynomial regression up to the information theoretic limit. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 391–402, 2017. doi:10.1109/FOCS.2017.43.
[12] A. Klivans, P. K. Kothari, and R. Meka. Efficient algorithms for outlier-robust regression. In Proceedings of the 31st Conference on Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 1420–1430, 2018. https://proceedings.mlr.press/v75/klivans18a.html.
[13] E. D. Kosov. Marcinkiewicz-type discretization of $L^{p}$ -norms under the Nikol’skii-type inequality assumption. Journal of Mathematical Analysis and Applications, 504(1):125358, 2021. doi:10.1016/j.jmaa.2021.125358.
[14] J. Ortega-Cerdà and J. Saludes. Marcinkiewicz–Zygmund inequalities. Journal of Approximation Theory, 145(2):237–252, 2007. doi:10.1016/j.jat.2006.09.001.
[15] A. Prasad, A. S. Suggala, S. Balakrishnan, and P. Ravikumar. Robust estimation via robust gradient estimation. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 82(3):601–627, 2020. doi:10.1111/rssb.12364.
[16] K. V. Runovski and W. Sickel. Marcinkiewicz–Zygmund-type inequalities, trigonometric interpolation on non-uniform grids and unconditional Schauder bases in Besov spaces on the torus. Zeitschrift für Analysis und ihre Anwendungen, 16(3):669–687, 1997. doi:10.4171/ZAA/784.

Appendix A Boundary cases, source note, and extensions

This appendix records results that are useful for scope and reproducibility but are not needed in the main proof. None changes the parameter regime of Theorem 1.1.

A.1 Constant polynomials

The convention $d\geq 1$ in Theorem 1.1 avoids the expression $\log(d/\delta)$ . When $d=0$ , the kernel construction is unnecessary: every polynomial is constant, and both the representative-norming error and cell-oscillation constant are zero. Taking $m=1$ , any weighted-LAD minimizer is a median of the labels. On the strict-majority event it lies in $[p-\sigma,p+\sigma]$ , and it equals $p$ when $\sigma=0$ . A Chernoff bound makes this event hold with probability $1-\delta$ using $O_{\rho}(\log(1/\delta))$ samples under either design.

A.2 Source-version note for the median witness

Claim B.1 of arXiv:2403.09465v1 in Arora et al. [1] is correct, but the displayed proof in that version reverses the signs of the one-sided noise terms in its interval endpoints. The valid implications are precisely those used in Lemma 5.2; continuity then supplies a witness that need not be an observed sample location or correspond to an observed inlier residual.

A.3 Other design laws and polynomial spaces

For any i.i.d. design under which every Chebyshev cell has probability at least $\pi_{\min}>0$ , the same estimator succeeds under the independent outlier model with $O_{\rho}(\pi_{\min}^{-1}\log(m^{n}/\delta))$ samples. Conditioned on the good-grid event, the deterministic proof also permits any cellwise corruption pattern with outlier fraction at most $\alpha$ ; independent indicators are used only to establish that event.

The theorem remains valid when $\mathcal{P}_{d,n}$ is replaced by the space of polynomials of total degree at most $d$ . This is a linear subspace of $\mathcal{P}_{d,n}$ , so every analytic and probabilistic estimate restricts to it; the sample bounds are unchanged and the coefficient dimension becomes $\binom{n+d}{n}$ .

For coordinate degrees $d_{k}\in\mathbb{Z}_{\geq 0}$ and positive integers $m_{k}\geq\max\{1,d_{k}\}$ , the product-kernel proof gives

\left\lVert q-q^{\sharp}\right\rVert_{L^{1}(\nu)}\leq A_{n}\left(\sum_{k=1}^{n}\frac{d_{k}}{m_{k}}\right)\left\lVert q\right\rVert_{L^{1}(\nu)},

and the cell-oscillation factor is at most $\pi\sum_{k=1}^{n}d_{k}/m_{k}$ . Use $V_{d_{k}}$ in coordinate $k$ , with $V_{0}\equiv 1$ ; the path argument contributes $(\pi/m_{k})\left\lVert\partial_{k}Q\right\rVert_{1}$ , and the Bernstein bound contributes $O_{n}(d_{k})\left\lVert Q\right\rVert_{1}$ .

More abstractly, the proof separates four modules: arbitrary-multiset weighted $L^{1}$ norming, an $L^{1}$ -to- $L^{\infty}$ inequality, a compatible cell-oscillation bound, and a lower bound on cell probabilities. A global empirical $L^{1}$ margin or an algebraic error-locator could provide other routes, but neither is analyzed or used in Theorem 1.1.

Scale-Independent Robust Multivariate Polynomial Regression

Abstract

1 Introduction and main result

Theorem 1.1 (Main theorem).

Proof overview.

2 Partition and algorithm

3 Product-Chebyshev L1 norming with arbitrary cell representatives

Lemma 3.1 (One-dimensional kernel bounds).

Proof.

Lemma 3.2 (Local supremum and endpoint Bernstein bounds).

Proof.

Lemma 3.3 (Arbitrary representatives).

Proof.

Corollary 3.4 (Arbitrary multisets in every cell).

Proof.

Remark 3.5 (Why a sufficiently fine grid is necessary).

4 Signal-scale-independent weighted-LAD initialization

Proposition 4.1 (Coercive LAD bound and initialization).

Proof.

5 Median refinement and contraction

Lemma 5.1 (Cell oscillation).

Proof.

Lemma 5.2 (Median witness).

Proof.

Proposition 5.3 (One-step contraction).

Proof.

6 Probability, sample complexity, and computational scope

Lemma 6.1 (A good product grid).

Proof.

Proposition 6.2 (LP size and computational scope).

Proof.

7 Significance, related work, and limitations

References

Appendix A Boundary cases, source note, and extensions

A.1 Constant polynomials

A.2 Source-version note for the median witness

A.3 Other design laws and polynomial spaces

Scale-Independent Robust
Multivariate Polynomial Regression

3 Product-Chebyshev $L^{1}$ norming with arbitrary cell representatives