Explicit and fast error bounds for polynomial approximation 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.




* 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]$.
 A: If $f, f', \dotsc, f^{(\nu-1)}$ are all absolutely continuous on $[-1, 1]$, and $f^{(\nu)}$ has bounded variation $V$ on $[-1, 1]$, where $\nu \ge 1$, then the polynomial interpolant $p_n$ of degree $n > \nu$ through the Chebyshev points of the second kind,
$$ p_n(x_j) = f(x_j), \quad x_j = \cos \tfrac{j\pi}{n}, \quad j=0,\dotsc,n, $$
satisfies the bound
$$ \sup_{-1 \le x \le 1} | f(x) - p_n(x)| \le \frac{4V}{\pi \nu (n - \nu)^\nu}. $$
See Theorem 7.2, equation (7.5) of [1].
It should be easy to map the result to [0, 1]. If all you know is that $f$ has $k$ continuous derivatives, then you can take $\nu = k-1$, provided $k \ge 2$. The convergence rate $O(n^{-(k-1)})$ is faster than you asked for when $k > 2$ (and equal at $k=2$).
I am unclear exactly what you mean by being "readily rewritten" to the Bernstein polynomial basis. One explicit possibility: you can use a discrete Fourier transform (specifically, the FFT) to recover the coefficients of the Chebyshev series of $p_n$ from the values at the Chebyshev points above (again, see [1]), then use an explicit expansion of the Chebyshev polynomials in the Bernstein basis (e.g., the one on the Wikipedia page for the Bernstien polynomials).
[1] Trefethen, Lloyd N., Approximation theory and approximation practice, Other Titles in Applied Mathematics 128. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-1-611972-39-9/pbk). 305 p. (2013). ZBL1264.41001.
