Main Question
This question is about finding explicit, calculable, and fast error bounds when approximating continuous functions with polynomials to a user-specified error tolerance.
In this question:
- A polynomial $P(x)$ is written in Bernstein form of degree $n$ if it is written as $P(x)=\sum_{k=0}^n a_k {n \choose k} x^k (1-x)^{n-k},$ where $a_0, ..., a_n$ are the polynomial's Bernstein coefficients.
- For the Bernstein polynomial of $f(x)$ of degree $n$, $a_k = f(k/n)$.
Let $f:[0,1]\to [0,1]$ be continuous and polynomially bounded (both $f$ and $1-f$ are bounded below by min($x^n$, $n(1-x)^n$) for some integer $n$), let $r\ge 3$, and denote the Bernstein polynomial of degree $n$ of a function $g$ as $B_n(g)$.
Given that $f$ has a continuous $r$-th derivative (or has a Lipschitz continuous $(r-1)$-th derivative), are there results that give a sequence of polynomials $P_n$ with the following error bound?
$$| f(x) - P_n(f)(x) | \le \epsilon(f, n, x) = O(1/n^{r/2}),$$ where:
- $\epsilon(f, n, x)$ is a fully determined function, with all constants in the expression having a known exact value or upper bound.
- $P_n(f)(x)$ is an approximating polynomial of degree $n$ that can be readily rewritten to a polynomial in Bernstein form with coefficients in $[0, 1]$. Preferably, $P_n(f)$ has the form $B_n(W_n(f))$ where $W_n(f)$ is easily computable from $f$ using rational arithmetic only (see "Remarks", later).
One way to answer this (see this question) is to find a sequence $W_n(f)$ and an explicit and tight upper bound on $C_1>0$ such that, for each integer $n\ge 1$ that's a power of 2— $$\max_{0\le k\le 2n}\left|\left(\sum_{i=0}^k \left(W_n\left(\frac{i}{n}\right)\right) {n\choose i}{n\choose {k-i}}/{2n \choose k}\right)-W_{2n}\left(\frac{k}{2n}\right)\right|\le \frac{C_1 M}{n^{r/2}},$$ where $M$ is the maximum absolute value of $f$ and its derivatives up to the $r$-th derivative (or, respectively, the maximum of $|f|$ and the Lipschitz constants of $f$ and its derivatives up to the $(r-1)$-th derivative).
Then $| f(x) - B_n(W_n(f))(x) | \le \frac{C_1}{1-\sqrt{2/2^{r+1}}}\frac{M}{n^{r/2}}=O(1/n^{r/2})$ (see Lemma 3 in "Proofs for Polynomial-Building Schemes), although this is only guaranteed to work for power-of-2 values of $n$. For example, $W_n$ can be $2f-B_n(f)$ and $r$ can be 3 or 4, or $W_n$ can be $B_n(B_n(f))+3(f-B_n(f))$ and $r$ can be 5 or 6.
Motivation
My motivation for this question is to implement "approximate Bernoulli factories", or algorithms that toss heads with a probability equal to a polynomial in Bernstein form that comes within $\epsilon$ of a continuous function $f(x)$. This involves finding a reasonably small degree $n$ of that polynomial, then the algorithm works as follows:
- Flip the coin $n$ times, count the number of heads as $h$.
- With probability equal to the $h$-th Bernstein coefficient, return heads; otherwise tails.
Note that the algorithm requires finding only one Bernstein coefficient per run. And for ordinary Bernstein polynomials, finding it is trivial — $f(h/n)$ — but the degree $n$ can be inordinate due to Bernstein polynomials' slow convergence; for example, if $\epsilon=0.01$ and $f$ is Lipschitz with constant 1, the required polynomial degree is 11879.
- Approximating $f$ with a rational function is also interesting, but is outside the scope of this question.
- Exact Bernoulli factories require a slightly different approach to finding the polynomials; see another question of mine.
Polynomials with faster convergence than Bernstein polynomials
As is known since Voronovskaya (1932), the Bernstein polynomials converge uniformly to $f$, in general, at a rate no faster than $O(1/n)$, regardless of $f$'s smoothness, which means that it won't converge in a finite expected running time. (See also a related question by Luis Mendo on ordinary Bernstein polynomials.)
But Lorentz (1966, "The degree of approximation by polynomials with positive coefficients") has shown that if $f(x)$ is positive (the case that interests me) and has $k$ continuous derivatives, there are polynomials with non-negative Bernstein coefficients that converge to $f$ at the rate $O(1/n^{k/2})$ (and thus can be faster than the $O(1/n^{2+\epsilon})$ needed for a finite expected running time, depending on $f$).*
Thus, people have developed alternatives, including iterated Bernstein polynomials, to improve the convergence rate. These include:
- Micchelli, C. (1973). The saturation class and iterates of the Bernstein polynomials. Journal of Approximation Theory, 8(1), 1-18.
- Guan, Zhong. "Iterated Bernstein polynomial approximations." arXiv preprint arXiv:0909.0684 (2009).
- Güntürk, C. Sinan, and Weilin Li. "Approximation with one-bit polynomials in Bernstein form" arXiv preprint arXiv:2112.09183 (2021).
- The "Lorentz operator": Holtz, Olga, Fedor Nazarov, and Yuval Peres. "New coins from old, smoothly" Constructive Approximation 33, no. 3 (2011): 331-363.
- Draganov, Borislav R. "On simultaneous approximation by iterated Boolean sums of Bernstein operators." Results in Mathematics 66, no. 1 (2014): 21-41.
Usually, papers like those express a bound on the error when approximating a function with polynomials as follows: $$| f(x) - P_n(f)(x) | \le c_n \epsilon(f, n, x),$$ where $\epsilon(f, n, x)$ is a fully determined function, $c_n>0$ is a constant that may depend on $n$, and $P_n(f)(x)$ is an approximating polynomial of degree $n$.
There are results where the error bound $\epsilon(.)$ is in $O(1/n^{k/2})$, but in all those results I've seen so far (e.g., Theorem 4.4 in Micchelli; Theorem 5 in Güntürk and Li), $c_n$ is unknown, and no upper bound for $c_n$ is given by the results in the papers above, so that the error bound is unimplementable and there is no way of knowing beforehand whether $P_n$ will come close to $f$ within a user-specified error tolerance. (There is also a separate matter of rewriting the polynomial to its Bernstein form, but this is much more manageable, especially with the Lorentz operator.)
Remarks
I prefer approaches that involve only rational arithmetic and don't require transcendental or trigonometric functions to build the Bernstein-form polynomials.
- Unlike with rational arithmetic (where arbitrary precision is trivial thanks to Python's
fractions
module), transcendental and trig. functions require special measures to support arbitrary accuracy, such as constructive/recursive reals — floating point won't do for my purposes. - In general, "rounding" a polynomial's coefficients or "nodes" to rational numbers will add a non-trivial error that, for my purposes, has to be accounted for in any error bound.
- Unlike with rational arithmetic (where arbitrary precision is trivial thanks to Python's
* If the polynomials are not restricted in their coefficients, then the rate $O(1/n^k)$ is possible (e.g., DeVore and Lorentz 1993). But this result is not useful to me since my use case (approximate Bernoulli factories) requires the polynomials to have Bernstein coefficients in $[0, 1]$.