After analyzing the proof of Güntürk and Li (2021), Theorem 3.3, I believe I found explicit error bounds for the Micchelli–Felbecker polynomials (iterated Bernstein polynomials) when $f(x)$ has a given number of continuous derivatives. In the table below, let—$$||f(x)||_{C^k} = \max(\max_{0\le x \le 1} |f(x)|, \max_{0\le x \le 1} |f^{(k)}(x)|).$$
| No. of continuous derivatives | Error bound |
--- | --- |
| 4 | 0.275 $||f(x)||_{C^4}/n^2$ |
| 5 | 0.7284 $||f(x)||_{C^5}/n^{5/2}$ |
| 6 | 1.0025 $||f(x)||_{C^6}/n^3$ |
I would appreciate any corrections.
-----
Finding these bounds relies, in part, on finding upper bounds for the $d$-th central moments of the binomial($n$, $p$) distribution. This is discussed in Molteni (2022); before Molteni there were almost no works on upper bounds for those moments.
When $d$ is even, the moment is no greater than $A_d n^{d/2}$, where $A_d$ is a constant that depends on $d$ (DeVore and Lorentz 1993). The goal here is to find this constant.
The following table shows upper bounds for the $d$-th central moment. The following are results on this moment:
- The $d$-th moment is upper bounded by $\frac{d!}{(d/2)!8^{d/2}} n^{d/2}$ for even $r\le 44$ and another bound applies for even $d$ when $n$ is high enough (Molteni 2022).
- The very loose bound $2 (d/2)! n^{d/2}$ for even or odd $d$ applies (Adell et al. 2015).
In addition:
- The 3rd moment is bounded by $\frac{\sqrt{3}}{18\sqrt{n}} n^{3/2}$, so is bounded by $\frac{\sqrt{3}}{18} n^{3/2} < (963/10000) n^{3/2}$ for every $n\ge 1$.
- Proof: The critical points of the moment are at $p=0$, $p=1$, $p=1/2-\sqrt{3}/6$, and $p=1/2+\sqrt{3}/6$. The moment equals 0 at the points 0 and 1, so that leaves the last two. Since the odd moments are antisymmetric (Skorski 2020), it's enough to take the third critical point, where the moment is positive. By inspection, the third moment at that critical point is decreasing for every $n\ge 1$.
- The 5th moment is bounded by $(27/128) n^{5/2}$.
- Proof: Follows from evaluating the moment for each $1\le n \le 303$ at their critical points. 303 is the cutoff because Molteni proved a different bound for $n\ge 260\cdot\omega^3 \lt 260\cdot 1.05309^3 \lt 304$ when $d=3$, namely $(27/128) n^{5/2}$, which was higher than the maximum moment at the evaluated points (namely $< 0.083 n^{5/2}$).
------
The following is Python code I used to calculate the error bounds for the iterated Bernstein polynomials. It uses the SymPy computer algebra library.
```
def tnr(n,r):
if r%2==0 and r<=44:
return (factorial(r)/(factorial(r//2)*8**(r//2)))*n**(r//2)
if r==1: return 0
if r==3: return (S(963)/10000)*sqrt(n**3)
if r==5: return (S(27)/128)*sqrt(n**5)
return 2*factorial(S(r)/2)*sqrt(n**r)
raise ValueError
def gnr1(n,r,derivs):
return (Max(derivs[0],derivs[r+1])/n**(r+1))*sqrt(tnr(n,2*(r+1)))/factorial(r+1)
def fnr(n,r,derivs):
return derivs[r]*tnr(n,r)/(n**floor(r/2)*factorial(r))
def bnerror(n,r,derivs):
return sum(derivs[i]*tnr(n,i)/(n**i*factorial(i)) for i in range(2,r+1))+gnr1(n,r,derivs)
def fnrderivs(n,r,alpha,derivs):
d=[]
for beta in range(0,(r+1-alpha)+1):
d.append((Max(derivs[0],derivs[r+1])/(n**floor(alpha/2)*factorial(alpha)))*\
sum(binomial(beta,g)*tnr(n,alpha)*factorial(alpha)/factorial(alpha-g) \
for g in range(0,min(alpha,beta)+1)))
#print(d)
return d
def bnr(n,rr,derivs,r=None,gnd=True): # r=s-1, s is no. of cont. deriv.
s=len(derivs)-1 # No. of continuous derivatives
if r==None: r=s-1
if rr==1: return bnerror(n,r,derivs)
gn=gnr1(n,r,derivs)
return sum(bnr(n,rr-1,fnrderivs(n,r,i,derivs))/n**((i+1)//2) \
for i in range(2,r+1))+gn*2**(rr-1)
n=symbols('n',nonnegative=True,integer=True)
d0,d1,d2,d3,d4,d5,d6=symbols('d0 d1 d2 d3 d4 d5 d6',real=True,positive=True)
print(bnr(n,2,[d0,d1,d2,d3,d4]).simplify().n())
print(bnr(n,3,[d0,d1,d2,d3,d4,d5]).simplify().n())
print(bnr(n,3,[d0,d1,d2,d3,d4,d5,d6]).simplify().n())
```
## References
- C.S. Güntürk, W. Li, "[Approximation of functions with one-bit neural networks](https://arxiv.org/pdf/2112.09181.pdf)", arXiv:2112.09181 [cs.LG], 2021.
- Skorski, Maciej. "Handy formulas for binomial moments." arXiv preprint arXiv:2012.06270 (2020).
- DeVore, R.A., Lorentz, G.G., Constructive approximation, 1993.
- Molteni, Giuseppe. "Explicit bounds for even moments of Bernstein’s polynomials." Journal of Approximation Theory 273 (2022): 105658.
- Adell, J.A., Bustamante, J., Quesada, J.M., "Estimates for the moments of Bernstein polynomials" J. Math. Anal. Appl. 432 (2015).