A Note on Non-Negative L_1-Approximating Polynomials

Motivated by the optimization of bounded binary black-box functions, we study the problem of learning polynomial surrogates over the Boolean hypercube. To ensure that optimizing the surrogate yields good solutions for the underlying objective, we require uniform $L_\infty$-error guarantees rather than the usual $L_2$-type guarantees. We characterize the minimax sample complexity of uniform estimation under subgaussian noise for two classes of bounded polynomials. First, for polynomials of degree at most $d$ on $n$ variables, the sample complexity scales as $n^{d+1}$. Second, for $s$-sparse Fourier-Walsh polynomials with $s \leq n$, it scales as $ns^2$. These rates differ structurally from the noiseless setting, where uniform exact recovery scales as $n^d$ and $ns$, respectively. Our lower bounds hold even for arbitrary adaptive learners, showing that the additional factors are intrinsic to the noisy cases. Standard Fourier-analysis tools for the $L_2$-norm do not naturally extend to the $L_\infty$-setting in a way that yields uniform guarantees. Our proofs overcome this difficulty by relying on suitably chosen auxiliary norms that serve as proxies for controlling the $L_\infty$-error. Together, our results provide a tight characterization of the sample complexity of learning optimization-safe polynomial surrogates.

Functions that grow without bound on one side of the real line and decay to zero on the other cannot be approximated uniformly by ordinary polynomials on unbounded domains. Motivated by classical weighted polynomial approximation, we introduce a class of one-sided weighted \emph{deep} (composite) polynomial approximants for such asymmetric targets. The weight suppresses polynomial growth on the decaying side, while the composite polynomial remains free to capture growth on the other side. We prove that this mechanism reduces the half-line approximation problem to approximation on a compact interval whose length grows slowly with the degree, and we establish density and existence of best approximants in the appropriate closure of the model class. For computation, we first formulate the method as a trainable computational graph for \emph{deep} weighted polynomial approximation. However, direct end-to-end optimization becomes increasingly ill-conditioned at high composite degree and can suffer from local minima. To address this, we introduce a fine-tuning procedure in which a fixed inner composition of monotone polynomial self-maps supplies the effective degree, while only the outer polynomial and weight parameters are trained; the outer fit reduces to a linear program. Numerical experiments on Black--Scholes option-pricing functions show that the resulting fine-tuned weighted \emph{deep} polynomial achieves smaller uniform and $L_2$ errors than matched-budget polynomial baselines and resolves the decaying tail to machine precision.

We establish two related but logically distinct results for shallow ReLU$^k$ neural networks on the unit sphere $\SS^d$. First, for an arbitrary set of inner neural-network parameters, the best $\mathcal{L}^2(\SS^d)$ approximation of a fixed target function with smoothness $r>\tfrac{d+2k+1}{2}$ admits an asymptotic lower bound given by a constant multiple of $n^{-1/2}\underline{h}^{k+1/2}$, where $\underline{h}$ denotes the antipodal separation distance of the normalized inner-parameter set. This lower bound depends explicitly on the parameter configuration through $\underline{h}$ and applies without additional assumptions on the parameters. Second, for antipodally quasi-uniform parameters, $\underline{h}\simeq n^{-1/d}$, and the lower bound establishes the exact saturation order $n^{-\frac{d+2k+1}{2d}}$ for such parameter families: a target function with regularity greater than $\frac{d+2k+1}{2}$ and satisfying the required parity condition can be approximated at this rate, whereas approximation at any strictly faster rate forces the target function to be zero. Our results therefore place linearized neural-network approximation within the classical saturation framework and show that, although ReLU$^k$ network spaces can outperform finite elements of the same degree, this advantage is intrinsically limited.