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\lt x \lt 1} |f(x)|, \max_{0\lt x \lt 1} |f^{(k)}(x)|).$$
| No. of continuous derivatives | Error bound |
|---|---|
| 4 | 0.2762 $||f(x)||_{C^4}/n^2$ |
| 5 | 0.7319 $||f(x)||_{C^5}/n^{5/2}$ |
| 6 | 1.007 $||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, this moment is a symmetric polynomial (Skorski 2020) and takes its maximum at $p$ = 1/2. (See also the references cited in Skorski's paper) Thus, the following assumes p = 1/2. 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. Before I was aware of Molteni (2022), I found the values for $d>3$ given in the table below with partial help from an algorithm in Skorski (2020) for computing those central moments efficiently.
| d | Upper bound | Notes |
|---|---|---|
| 0 | 1 | |
| 1 | 0 | |
| 2 | $(1/4) n$ | $A_2 = 1/4$ (since the moment equals $n/4$ and so is upper bounded by $(1/4) n^1$). |
| 3 | $(1/10) \sqrt{n^3} < (1/10) n^2$ | For $n=1$; appears to decrease as $n$ increases. |
| 4 | $(3/16) n^2$ | $A_4 = - \frac{1}{8 n} + \frac{3 \cdot 2^{- 2 n} 4^{n}}{16}$ for $n\ge 4$, which increases with $n$ to a limit of $A_4 = 3/16$. |
| 5 | $(9/100) \sqrt{n^5} < (9/100) n^3$ | For $n=2$; appears to decrease as $n$ increases. |
| 6 | $(15/64) n^3$ | $A_6 = - \frac{15}{32 n} + \frac{1}{4 n^{2}} + \frac{15 \cdot 2^{- 2 n} 4^{n}}{64}$ for $n\ge 6$, which increases with $n$ to a limit of $A_4 = 15/64$. |
| 8 | $(105/256) n^4$ | $A_8$ equals the moment divided by $n^4$; its limit is $A_8 = 105/256$. |
| 10 | $(945/1024) n^5$ | $A_10$ equals the moment divided by $n^5$; its limit is $A_10 = 945/1024$. |
| 12 | $(10395/4096) n^6$ | Found similarly to entry for 10. |
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==0: return 1
if r==1: return 0
if r==2: return (S(1)/4)*n
if r==3: return (S(1)/10)*sqrt(n**3)
if r==4: return (S(3)/16)*n**2
if r==5: return (S(9)/100)*sqrt(n**5)
if r==6: return (S(15)/64)*n**3
if r==8: return (S(105)/256)*n**4
if r==10: return (S(945)/1024)*n**5
if r==12: return (S(10395)/4096)*n**6
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)
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", 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.