Explicit and fast error bounds for approximating continuous functions

Question

Main Question

This question is about finding explicit, calculable, and fast error bounds (no hidden constants) when approximating continuous functions with polynomials or simpler functions 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)$.

Suppose $f:[0,1]\to [0,1]$ is continuous and belongs to a large class of functions (for example, the $k$-th derivative, $k\ge 0$, is continuous, Lipschitz continuous, concave, strictly increasing, bounded variation, and/or in the Zygmund class, or $f$ is real analytic).

Given $\epsilon > 0$, compute the Bernstein coefficients of a polynomial or rational function (of some degree $n$) that is within $\epsilon$ of $f$. (*6)

The convergence rate must be $O(1/n^{r/2})$ if the class has only functions with Lipschitz-continuous $(r-1)$-th derivative. The method may not introduce transcendental or trigonometric functions (as with Chebyshev interpolants).

Without loss of generality, here are some ways to tackle this question:

• For iterated Boolean sums (linear combinations of iterates) of Bernstein polynomials ($U_{n,k}$ in Micchelli 1973; see also Güntürk and Li), find an explicit bound, with no hidden constants, on the approximation error for functions with continuous $r$-th derivative, or verify my proofs of these bounds in Propositions B10C and B10D.
• For linear combinations of Bernstein polynomials (Butzer 1953, Tachev 2022), verify my proof of those error bounds in my Proposition B10.
• For the "Lorentz operator", find an explicit bound, with no hidden constants, on the approximation error for the operator $Q_{n,r}$ and for the polynomials $(f_n)$ and $(g_n)$ formed with it, and find the hidden constants $\theta_\alpha$, $s$, and $D$ as well as those in Lemmas 15, 17 to 22, 24, and 25 in the paper. Or verify my proof of the order-2 operator's error bounds in my Proposition B10A.
• Let $f:[-1,1]\to [0,1]$ be continuous. Find explicit bounds, with no hidden constants, on the error in approximating $f$ with the following polynomials: The polynomials are similar to Chebyshev interpolants, but evaluate $f$ at rational values of $\lambda$ that converge to Chebyshev points (that is, converging to $\cos(j\pi/n)$ with increasing $n$). The error bounds must be close to those of Chebyshev interpolants (see, e.g., chapters 7, 8, and 12 of Trefethen, Approximation Theory and Approximation Practice, 2013).
• Find other polynomial operators meeting the requirements of the main question (see "Main Question", above) and having explicit error bounds, with no hidden constants, especially operators that preserve polynomials of a higher degree than linear functions.

Motivation

My motivation for this question is to implement "approximate Bernoulli factories", or ways to toss heads with probability equal to a function that approximates another function. This question is broader in scope than my previous question.(^)

Please see my section on approximate Bernoulli factories for details on my progress in this problem. For example, the section shows how to build polynomials that answer the question if $f(\lambda)$ is Lipschitz or Hölder or has a Lipschitz-continuous derivative, but in general the polynomials have inordinate degree, for which improvements may be possible if $f(\lambda)$ is smoother or if the approximating function is other than a polynomial.

Approximate Bernoulli factories and polynomials with fast convergence

Approximate Bernoulli factories are 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:

1. Flip the coin $n$ times, count the number of heads as $h$.
2. 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 ($\Theta(1/n)$ unless $f$ is linear [Voronovskaya 1932]); for example, if $\epsilon=0.01$ and $f$ is Lipschitz with constant 1, the required polynomial degree is 11879. (See also a related question by Luis Mendo on ordinary Bernstein polynomials.)

Although ordinary Bernstein polynomials have slow convergence, 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 linear combinations and iterated Boolean sums of Bernstein polynomials, to improve the convergence rate. These include Micchelli (1973), Guan (2009), Güntürk and Li (2021a, 2021b), the "Lorentz operator" in Holtz et al. (2011) (see also "New coins from old, smoothly"), Draganov (2014), and Tachev (2022).

These alternative polynomials usually include results where the error bound is the desired $O(1/n^{k/2})$, but most of those results (e.g., Theorem 4.4 in Micchelli; Theorem 5 in Güntürk and Li) have hidden constants with no upper bounds given, making them unimplementable (that is, it can't be known beforehand whether a given polynomial will come close to the target function within a user-specified error tolerance).

Related Question

The following is related to the main question, but is also one way to answer the main question. Nice to have would be a sequence of polynomials $(g_n)$, based on linear combinations or iterated Boolean sums of Bernstein polynomials, that: (A) converge to $f(\lambda)$ from below; (B) have the rate $O(1/n^{r/2})$ if the class has only functions with a continuous $r$-th derivative; and (C) satisfy: $(g_{2n}−g_n)$ is a polynomial with non-negative Bernstein coefficients, once it's rewritten to a polynomial in Bernstein form of degree exactly $2n$.

Notes

(^) Exact Bernoulli factories require a slightly different approach to finding the polynomials; see another question of mine.

(****) If the polynomials are not restricted in their coefficients, then the rate $O(1/n^k)$ is possible (e.g., DeVore and Lorentz 1993). However, my use case (approximate Bernoulli factories) requires the polynomials to have Bernstein coefficients in the closed unit interval.

(*6) More generally, the approximating function $g(\lambda)$ can have a simple algorithm that tosses heads with probability exactly equal to $g$, given a coin that shows heads with probability $\lambda$.

References

• 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).
• 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.
• Güntürk, C. Sinan, and Weilin Li. "Approximation with one-bit polynomials in Bernstein form", arXiv:2112.09183 (2021); Constructive Approximation, pp.1-30 (2022).
• Güntürk, C. Sinan, and Weilin Li. "Approximation of functions with one-bit neural networks", arXiv:2112.09181 (2021).
• Tachev, Gancho. "Linear combinations of two Bernstein polynomials", Mathematical Foundations of Computing, 2022.
• E. Voronovskaya, "Détermination de la forme asymptotique d'approximation des fonctions par les polynômes de M. Bernstein", 1932.
• Butzer, P.L., "Linear combinations of Bernstein polynomials", Canadian Journal of Mathematics 15 (1953).

Answer 1

Here are some results on certain polynomials.

Tachev (2022)[^4] has published an error bound that relates to the polynomial— $$L_{2,n/2} = 2B_n(f) - B_{n/2}(f).$$ Their Theorem 2 describes the bound precisely, but here's a bound derived from it that will work for my purposes. If $f:[0,1]\to[0,1]$ has a continuous third derivative, let $M=\max |f^{(3)}|$, then for $n\ge 6$ an even integer— $$|L_{2,n/2}-f| \le \frac{3\sqrt3 M}{4n^2}.\tag{1}$$

The proof by Tachev suggests a way to prove a similar bound for other linear operators of the form— $$L_n(f) = \sum_{k=0}^{r-1} \alpha_k B_{2^k n}(f),$$ as long as $f$ has $r$ continuous derivatives and $L_n$ preserves polynomials of degree less than $r$. Specifically, the error bound is— $$\sum_{k=0}^{r-1} |\alpha_k|\cdot |B_{2^k n}(R_{r,f,x_0})|,$$ where $R_{r,f, x_0}$ is $f$ minus its Taylor polynomial of degree $r-1$ centered at $x_0$. (However, this bound is not of the form $CM/n^s$ for some $s\ge 2$, $C>0$, and $M>0$, similar to the right hand side of $(1)$, so it's not immediately useful for my purposes and requires some work, perhaps by following the proof of Tachev.) The paper by Xie (1995)[^5] might also be relevant.

---

Apr. 21: I believe the following result is valid:

Lemma B9: Let $f(\lambda)$ have a continuous fourth derivative on the closed unit interval. Then:

1. $f$ can be written as $f(\lambda) = R_f(\lambda, x_0) + f(x_0) + \sum_{i=1}^3 (\lambda-x_0)^i f^{(i)}(x_0)/(i!)$ where $0\le x_0 \le 1$ and $f^{(i)}$ is the $i$-th derivative of $f$.
2. $|B_n(R_f(\lambda, x_0))| \le \frac{M}{128 n^2}$, where $M$ is the maximum of the absolute value of that fourth derivative.

Proof: The well-known result of part 1 says $f$ equals the degree-3 Taylor polynomial at $x_0$ plus the Lagrange remainder, $R_f(\lambda, x_0)$. $R_f(\lambda, x_0)$, in turn, is writable as— $$f^{(4)}(\gamma)\cdot (\lambda-x_0)^4 /(4!),$$ for some $\gamma$ between $\lambda$ and $x_0$ (and thus in the closed unit interval). Thus— $$|R_f(\lambda, x_0)| \le \frac{M}{4!} (\lambda-x_0)^4 = \frac{M}{24} (\lambda-x_0)^4.$$ By a result of Molteni (2022, "Explicit bounds for even moments of Bernstein’s polynomials", Journal of Approximation Theory)— $$|B_n((\lambda-x_0)^4)| \le \frac{3}{16}/n^2,$$ so— $$|B_n(R_f(\lambda, x_0))| \le \frac{M}{24} |B_n((\lambda-x_0)^4)| \le \frac{M}{128 n^2}.$$ □

Proposition B10: Let $f(\lambda)$ have a continuous fourth derivative on the closed unit interval. For each $n\ge 4$ that is divisible by 4, let $L_{3,n/4}(f) = 1/3\cdot B_{n/4}(f) - 2\cdot B_{n/2}(f) + 8/3\cdot B_{n}(f)$. Then $L_{3,n/4}(f)$ is within $M/(8 n^2)$ of $f$, where $M$ is the maximum of the absolute value of that fourth derivative.

Proof: This proof is inspired by the proof technique in Tachev (2022). It is known that $L_{3,n/4}$ preserves polynomials of degree 3 or less, that is, $L_{3,n/4}(f) = f$ whenever $f$ is a polynomial of degree 3 or less (Ditzian and Totik 1987, Moduli of Smoothness, 1987). Because of this and because $f$ has a continuous fourth derivative, $f$ has the Lagrange remainder $R_f(\lambda, x_0)$ given in Lemma B9, and— $$|L_{3,n/4}(f(x_0)) - f(x_0)| = |L_{3,n/4}(R_f(\lambda, x_0))|.$$ Now denote $\sigma_n$ as the maximum of $|B_n(R_f(\lambda, x_0))|$ over $0\le x_0\le 1$. In turn (using Lemma B9)— $$|L_{3,n/4}(R_f(\lambda, x_0))| \le(1/3)\cdot\sigma_{n/4} + 2\cdot\sigma_{n/2}+(8/3)\cdot\sigma_n$$ $$\le (1/3)\frac{M}{128 (n/4)^2} + 2\frac{M}{128 (n/2)^2} + (8/3)\frac{M}{128 n^2} =M/(8 n^2).$$ □

May 3: Also see my updated version of Lemma B9 and Proposition 10 in "Results Used in Approximate Bernoulli Factories".

---

May 5: I believe the following result is true.

Proposition B10A: Let $f(\lambda)$ have a Lipschitz continuous second derivative on the closed unit interval. Let $Q_{n,2}(f)=B_n(f)-\frac{x(1-x)}{2n} B_n(f'')$ be the Lorentz operator (Holtz et al. 2011) of order 2, which is a polynomial of degree $n+2$. Then if $n\ge 2$ is an integer, $Q_{n,2}(f)$ is within $\frac{M(\sqrt{3}+3)}{48 n^{3/2}}$ of $f$, where $M$ is that second derivative's Lipschitz constant or greater.

Proof: Since $Q_{n,2}(f)$ preserves polynomials of degree 2 or less (Holtz et al. 2011, Lemma 14)[^29], $f$ has the Lagrange remainder $R_{f,2}(\lambda, x_0)$ given in Lemma B9, and $f''$, the second derivative of $f$, has the Lagrange remainder $R_{f'',0}(\lambda, x_0)$. Thus, using Corollary B9A, the error bound can be written as— $$|Q_{n,2}(f(\lambda))(x_0) - f(x_0)|\le|B_n(R_{f,2}(\lambda, x_0))| + \frac{x_0(1-x_0)}{2n} |B_n(R_{f'',0}(\lambda,x_0))|$$ $$\le \frac{\sqrt{3}M}{48 n^{3/2}} + \frac{1}{8n} \frac{M}{2 n^{1/2}} = \frac{M(\sqrt{3}+3)}{48 n^{3/2}}.$$ □

---

May 17: I believe the following results are true.

Proposition B10C: Let $f(\lambda)$ have a Hölder continuous second derivative on the closed unit interval, with Hölder exponent $\alpha$ ($0\lt\alpha\le 1$) and Hölder constant $L$ or less. Let $U_{n,2}(f)=B_n(2f-B_n(f))$ be $f$'s iterated Boolean sum of order 2 of Bernstein polynomials. Then if $n\ge 3$ is an integer, the error in approximating $f$ with $U_{n,2}(f)$ is as follows: $$|f-U_{n,2}(f)|\le \frac{M_2}{8 n^{2}} + 5 L/(32 n^{1+\alpha/2}) \le ((5L+4M_2)/32)/n^{1+\alpha/2},$$ where $M_2$ is the maximum of that second derivative's absolute value or greater.

Proof: This proof is inspired by a result in Draganov (2004)[^45].

The error to be bounded can be expressed as $|(B_n(f)-f)( B_n(f)-f )|$. Following Lorentz (1963)[^8] and the well-known fact that $M$ is an upper bound of $f$'s first derivative's (minimal) Lipschitz constant: $$|(B_n(f)-f)( B_n(f)-f )|\le \frac{1}{8n} \max(|(B_n(f))^{(2)}-f^{(2)}|).\tag{B10C-1}$$ It thus remains to estimate the right-hand side of the bound. Using a result by Knoop and Pottinger (1976)[^46], which works for every $n\ge 3$: $$|(B_n(f))^{(2)}-f^{(2)}| \le \frac{1}{n} M_2+(5/4) L/n^{\alpha/2},$$ so— $$|(B_n(f)-f)( B_n(f)-f )|\le \frac{1}{8n} \left(\frac{1}{n} M_2+(5/4) L/n^{\alpha/2}\right)$$ $$\le \frac{M_2}{8 n^{2}} + \frac{5L}{32 n^{1+\alpha/2}}\le \frac{5L+4M_2}{32}\frac{1}{n^{1+\alpha/2}}.$$ □

Proposition B10D: Let $f(\lambda)$ have a Hölder continuous third derivative on the closed unit interval, with Hölder exponent $\alpha$ ($0\lt\alpha\le 1$) and Hölder constant $L$ or less. If $n\ge 6$ is an integer, the error in approximating $f$ with $U_{n,2}(f)$ is as follows: $$|f-U_{n,2}(f)|\le \frac{\max(|f^{(2)}|)+\max(|f^{(3)}|)}{8n^2}+9L/(64 n^{(3+\alpha)/2})$$ $$\le \frac{9L+8\max(|f^{(2)}|)+8\max(|f^{(3)}|)}{64n^{(3+\alpha)/2}}.$$

Proof: Again, the goal is to estimate the right-hand side of (B10C-1). But this time, a different result is employed, namely a result from Kacsó (2002)[^47], which in this case works if $n\ge\max(r+2,(r+1)r)=6$, where $r=2$. By that result: $$|(B_n(f))^{(2)}-f^{(2)}| \le \frac{r(r-1)}{2n} M_2+\frac{r M_3}{2n}+\frac{9}{8}\omega_2(f^{(2)},1/n^{1/2})$$ $$\le \frac{1}{n} M_2+M_3/n+\frac{9}{8} L/n^{(1+\alpha)/2},$$ where $r=2$, $M_2 = \max(|f^{(2)}|)$, and $M_3=\max(|f^{(3)}|)$, using properties of $\omega_2$, the second-order modulus of continuity of $f^{(2)}$, given in Stancu et al. (2001)[^48]. Therefore— $$|(B_n(f)-f)( B_n(f)-f )|\le \frac{1}{8n} \left(\frac{1}{n} M_2+M_3/n+\frac{9}{8} L/n^{(1+\alpha)/2}\right)$$ $$\le \frac{M_2+M_3}{8n^2} + \frac{9L}{64 n^{(3+\alpha)/2}}\le \frac{9L+8M_2+8M_3}{64n^{(3+\alpha)/2}}.$$ □

---

[^1]: Bustamante, J., "Estimates of positive linear operators in terms of second order moduli", J. Math. Anal. Appl. 345 (2008).

[^2]: Also known as the Ditzian–Totik second modulus of smoothness (Ditzian, Z., Totik, V., "Moduli of smoothness", Springer, 1987).

[^3]: A.F. Timan, Theory of Approximation of Functions of a Real Variable, 1994.

[^4]: Tachev, Gancho. "Linear combinations of two Bernstein polynomials", Mathematical Foundations of Computing, 2022.

[^5]: Xie, L. Uniform approximation by combinations of Bernstein polynomials. Approx. Theory & its Appl. 11, 36–51 (1995). https://doi.org/10.1007/BF02836577

• X. Han, "Multi-node higher order expansions of a function", Journal of Approximation Theory, October 2003.

• Holtz, O., Nazarov, F., Peres, Y., "New Coins from Old, Smoothly", Constructive Approximation 33 (2011)

[^45]: Draganov, Borislav R. "On simultaneous approximation by iterated Boolean sums of Bernstein operators." Results in Mathematics 66, no. 1 (2014): 21-41.

[^46]: Knoop, H-B., Pottinger, P., "Ein Satz vom Korovkin-Typ für $C^k$-Räume", Math. Zeitschrift 148 (1976).

[^47]: Kacsó, D.P., "Simultaneous approximation by almost convex operators", 2002.

[^48]: Stancu, D.D., Agratini, O., et al. Analiză Numerică şi Teoria Aproximării, 2001.