What are ways to compute polynomials that converge from above and below to a continuous and bounded function on $[0,1]$?

Question

Main Question

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).

Then, compute the Bernstein coefficients of a sequence of polynomials ($g_n$) of degree 2, 4, 8, ..., $2^i$, ... that converge to $f$ from below and 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$. Assume $0\lt f(\lambda)\lt 1$ or $f$ is polynomially bounded.

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).

See "Strategies", below, for different ways to answer this question.

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.

The degree-$n$ Bernstein polynomial of an arbitrary function $f(x)$ has Bernstein coefficients $a_k = f(k/n)$. In general, this Bernstein polynomial differs from $f$ even if $f$ is a polynomial.

Background

I asked this question in order to solve the so-called Bernoulli factory problem, described next. We're given a coin that shows heads with an unknown probability, $\lambda$. The goal is to use that coin (and possibly also a fair coin) to build a "new" coin that shows heads with a probability that depends on $\lambda$, call it $f(\lambda)$. This is the Bernoulli factory problem, and it can be solved only if $f$ is continuous (Keane and O'Brien 1994).

However, since I asked this question I have found a Bernoulli factory algorithm that I believe is general enough to cover all the cases that this question would help solve.

Since this question may be of broader interest, though, I leave this question open. See also my other open questions about the Bernoulli factory problem.

Polynomials that approach a factory function

An algorithm simulates a factory function $f(\lambda)$ via two sequences of polynomials that converge from above and below to that function. To use the algorithm, however, the polynomial sequences must meet certain requirements; among them, the sequences must be of Bernstein-form polynomials that converge from above and below to a factory function. Specifically:

For $f(\lambda)$ there must be a sequence of polynomials ($g_n$) in Bernstein form of degree 1, 2, 3, ... that converge to $f$ from below and satisfy: $(g_{n+1}-g_{n})$ is a polynomial with non-negative Bernstein coefficients once it's rewritten to a polynomial in Bernstein form of degree exactly $n+1$ (see end notes; Nacu and Peres 2005; Holtz et al. 2011). For $f(\lambda)=1-f(\lambda)$ there must likewise be a sequence of this kind.

A Matter of Efficiency

However, ordinary Bernstein polynomials converge to a function at the rate $\Omega(1/n)$ in general, a result known since Voronovskaya (1932) and a rate that will lead to an infinite expected number of coin flips in general. (See also my supplemental notes.)

But Lorentz (1966) showed that if the function is positive and has a continuous $k$-th derivative, there are polynomials with nonnegative Bernstein coefficients that converge at the rate $O(1/n^{k/2})$ (and thus can enable a finite expected number of coin flips if the function is "smooth" enough).

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), Draganov (2014), and Tachev (2022).

These alternative polynomials usually include results where the error bound is the desired $O(1/n^{k/2})$, but nearly all 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). (See end notes.)

A Conjecture on Polynomial Approximation

The following is a conjecture that could help reduce this problem to the problem of finding explicit error bounds when approximating a function by polynomials.

Let $f(\lambda):[0,1]\to(0,1)$ have $r\ge 1$ continuous derivatives, let $M$ be the maximum of the absolute value of $f$ and its derivatives up to the $r$-th derivative, and denote the Bernstein polynomial of degree $n$ of a function $g$ as $B_n(g)$. Let $W_{2^0}(\lambda), W_{2^1}(\lambda), ..., W_{2^i}(\lambda),...$ be a sequence of functions on [0, 1] that converge uniformly to $f$.

For each integer $n\ge 1$ that's a power of 2, suppose that there is $D>0$ such that— $$|f(\lambda)-B_n(W_n(\lambda))| \le DM/n^{r/2},$$ whenever $0\le \lambda\le 1$. Then there is $C_0\ge D$ such that for every $C\ge C_0$, the polynomials $(g_n)$ in Bernstein form of degree 2, 4, 8, ..., $2^i$, ..., defined as $g_n=B_n(W_n(\lambda) - CM/n^{r/2})$, converge from below to $f$ and 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$. (See end notes.)

Equivalently (see also Nacu and Peres 2005), there is $C_1>0$ such that the inequality $(PB)$ (see below) holds true for each integer $n\ge 1$ that's a power of 2 (see "Strategies", below).

My goal is to see not just whether this conjecture is true, but also which value of $C_0$ (or $C_1$) suffices for the conjecture, especially for any combination of the special cases mentioned at the end of "Main Question", above.

Strategies

The following are some strategies for answering these questions:

• For iterated Boolean sums 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 proof of those error bounds.
• 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, and 24 in the paper. Or verify my proof of the order-2 operator's error bounds in my Proposition B10A.
• 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.
• Find a sequence of functions $(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— $$\left|\left(\sum_{i=0}^k W_n\left(\frac{i}{n}\right)\sigma_{n,k,i}\right)-W_{2n}\left(\frac{k}{2n}\right)\right|=|\mathbb{E}[W_n(X_k/n)] - W_{2n}(\mathbb{E}[X_k/n])|\le \frac{C_1 M}{n^{r/2}},\tag{PB}$$ whenever $0\le k\le 2n$, where $M = \max(L, \max|f^{(0)}|, ...,\max|f^{(r-1)}|)$, $L$ is $\max|f^{(r)}|$ or the Lipschitz constant of $f^{(r-1)}$, $X_k$ is a hypergeometric($2n$, $k$, $n$) random variable, and $\sigma_{n,k,i} = {n\choose i}{n\choose {k-i}}/{2n \choose k}=\mathbb{P}(X_k=i)$ is the probability that $X_k$ equals $i$. (See end notes as well as "Proofs for Polynomial-Building Schemes.)

References

• Łatuszyński, K., Kosmidis, I., Papaspiliopoulos, O., Roberts, G.O., "Simulating events of unknown probabilities via reverse time martingales", arXiv:0907.4018v2 [stat.CO], 2009/2011.
• Keane, M. S., and O'Brien, G. L., "A Bernoulli factory", ACM Transactions on Modeling and Computer Simulation 4(2), 1994.
• Holtz, O., Nazarov, F., Peres, Y., "New Coins from Old, Smoothly", Constructive Approximation 33 (2011).
• Nacu, Şerban, and Yuval Peres. "Fast simulation of new coins from old", The Annals of Applied Probability 15, no. 1A (2005): 93-115.
• 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).
• C.S. Güntürk, W. Li, "Approximation of functions with one-bit neural networks", arXiv:2112.09181 [cs.LG], 2021.
• Draganov, Borislav R. "On simultaneous approximation by iterated Boolean sums of Bernstein operators." Results in Mathematics 66, no. 1 (2014): 21-41.
• Farouki, R.T., and Rajan, V.T., "Algorithms for polynomials in Bernstein form", Computer Aided Geometric Design 5(1), 1988.
• Tachev, Gancho. "Linear combinations of two Bernstein polynomials", Mathematical Foundations of Computing, 2022.
• Lee, Sang Kyu, Jae Ho Chang, and Hyoung-Moon Kim. "Further sharpening of Jensen's inequality." Statistics 55, no. 5 (2021): 1154-1168.
• Butzer, P.L., "Linear combinations of Bernstein polynomials", Canadian Journal of Mathematics 15 (1953).

---

Note 5: This condition is also known as a "consistency requirement"; it ensures that not only the polynomials "increase" to $f(\lambda)$, but also their Bernstein coefficients do as well. This condition is equivalent in practice to the following statement (Nacu & Peres 2005). For every integer $n\ge 1$ that's a power of 2, $a(2n, k)\ge\mathbb{E}[a(n, X_{n,k})]= \left(\sum_{i=0}^k a(n,i) {n\choose i}{n\choose {k-i}}/{2n\choose k}\right)$, where $a(n,k)$ is the degree-$n$ polynomial's $k$-th Bernstein coefficient, where $0\le k\le 2n$ is an integer, and where $X_{n,k}$ is a hypergeometric($2n$, $k$, $n$) random variable. A hypergeometric($2n$, $k$, $n$) random variable is the number of "good" balls out of $n$ balls taken uniformly at random, all at once, from a bag containing $2n$ balls, $k$ of which are "good". See also my MathOverflow question on finding bounds for hypergeometric variables.

Note 6: If $W_n(0)=f(0)$ and $W_n(1)=f(1)$ for every $n$, then the inequality $(PB)$ is automatically true when $k=0$ and $k=2n$, so that the statement has to be checked only for $0\lt k\lt 2n$. If, in addition, $W_n$ is symmetric about 1/2, so that $W_n(\lambda)=W_n(1-\lambda)$ whenever $0\le \lambda\le 1$, then the statement has to be checked only for $0\lt k\le n$ (since the values $\sigma_{n,k,i} = {n\choose i}{n\choose {k-i}}/{2n \choose k}$ are symmetric in that they satisfy $\sigma_{n,k,i}=\sigma_{n,k,k-i}$).
This question is a problem of finding the Jensen gap of $W_n$ for certain kinds of hypergeometric random variables (see Note 5). Lee et al. (2021) deal with a problem very similar to this one and find results that take advantage of $f$'s (here, $W_n$'s) smoothness, but unfortunately assume the variable is supported on an open interval, rather than a closed one (namely $[0,1]$) as in this question.

Answer 1

While the following does not fully answer my question, I make the following notes.

Polynomial Schemes

This section relates to finding polynomials for certain functions.

But since they involve the ordinary Bernstein polynomials, they converge at a rate no faster than $O(1/n)$ in general, rather than the desired $O(1/n^{k/2})$ for functions with $k$ continuous derivatives. Other users are encouraged to add other answers to my question.

The following inequality from Nacu and Peres 2005 is useful: $$|\mathbb{E}[f(X/n)]-f(k/(2n))| \le \kappa_f(n), \tag{1}$$ where—

• $\kappa_f(n)$ is a function that depends only on $f$ and $n$ and makes the inequality hold true for all $f$ belonging to a given class of functions (such as Lipschitz continuous or twice-differentiable functions), and
• $X$ is a hypergeometric($2n$, $k$, $n$) random variable.

Notably, if a function $f$ is such that (1) holds true, then in general, for all $n$ that are powers of 2— $$a(k, n) = f(k/n)-\delta(n) \text{ and } b(k,n) = f(k/n)+\delta(n),$$ where $n$ is the polynomial's degree and $\delta(n)$ is a solution to the following functional equation: $$\delta(n) = \delta(n*2) + \kappa_f(n), $$or equivalently, the linear recurrence $\delta(n) = \delta(n+1) + \kappa_f(2^n)$.

For example:

1. (Nacu and Peres 2005, Proposition 10) If $f$ is Lipschitz continuous with Lipschitz constant $C$ —
   • $\kappa_f(n) = C/\sqrt{2*n}$ , so
   • $\delta(n) = (1+\sqrt{2})C/\sqrt{n}$ , and
2. (Nacu and Peres 2005, Proposition 10) If $f$ is twice differentiable and $M$ is not less than the highest value of $|f′′(x)|$ for any $x$ in [0, 1]—
   • $\kappa_f(n) = M/(4*n)$, so
   • $\delta(n) = M/(2*n)$
3. Due to Jensen's inequality (see, for example, Nacu and Peres 2005, Lemma 8):
   • If $f$ is concave in $[0, 1]$, then $a(k,n) = f(k/n)$.
   • If $f$ is convex in $[0, 1]$, then $b(k, n) = f(k/n)$.

I have also found results to derive polynomial-building schemes for Hölder continuous functions and other functions with an arbitrary modulus of continuity. For example, if $f$ is $\alpha$-Hölder continuous with Hölder constant $M$—

• $\kappa_f(n) = M(1/(7n))^{\alpha/2}$, so
• $\delta(n) = \frac{M(2/7)^{\alpha/2}}{(2^{\alpha/2}-1)n^{\alpha/2}}$.

Other schemes of this kind are not mentioned here because they can be impractical when $f$ is not Lipschitz continuous. Indeed, Nacu and Peres showed that a finite number of coin flips is possible only if $f$ is Lipschitz continuous.

For proofs and additional notes on polynomial-building schemes, see my supplemental notes.

Other Polynomials

Now for other polynomials in Bernstein form, not necessarily Bernstein polynomials.

It can be seen that the following inequality is useful, based on (10) and (11) of Nacu & Peres. The goal is to find a simple function $\kappa_f(n)$ such that— $$\max_{0\le k\le 2n}|\mathbb{E}[W_n(X/n)]-W_{2n}(k/(2n))| \le \kappa_f(n),$$ or equivalently— $$\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 \kappa_f(n),$$ for every integer $n\ge 1$ that's a power of 2, where—

• $W_n$ is a function whose Bernstein polynomial of degree $n$ approximates $f$ with the desired error bound $O(1/n^{k/2})$ (note that $W_n$ need not equal $f$),
• $\kappa_f(n)$ is a function that depends only on $f$ and $n$ and makes the inequality hold true for all $f$ belonging to a given class of functions, and
• $X$ is a hypergeometric($2n$, $k$, $n$) random variable.

Then, for certain choices of $\kappa_f(n)$, condition 3 will be met if the following series converges: $$\sum_{m\ge\log_2(n)}\kappa_f(2^m).$$ See Theorem 1 of "Proofs for Polynomial Building Schemes" for details.

As an example of $W_n$, there are error bounds for iterated Bernstein polynomials, which can be seen as a Bernstein polynomial of another function $W_n$ that approximates $f$ appropriately (see Güntürk and Li 2021, sec. 3.3). Unfortunately, those error bounds can't be used as is to bound $\kappa_f(n)$.

References

• Nacu, Şerban, and Yuval Peres. "Fast simulation of new coins from old", The Annals of Applied Probability 15, no. 1A (2005): 93-115.
• Flajolet, P., Pelletier, M., Soria, M., "On Buffon machines and numbers", arXiv:0906.5560 [math.PR], 2010.
• (The "Lorentz operator".) Holtz, O., Nazarov, F., Peres, Y., "New Coins from Old, Smoothly", Constructive Approximation 33 (2011).
• C.S. Güntürk, W. Li, "Approximation of functions with one-bit neural networks", arXiv:2112.09181 [cs.LG], 2021.