After analyzing the proof of Güntürk and Li (2021), Theorem 32.34, 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)|),$$||f(x)||_{C^k} = \max(\max_{0\le x \le 1} |f(x)|, \max_{0\le x \le 1, 1\le i\le k} |f^{(i)}(x)|),$
- $I$ be the identity operator, and
- $B_n$ be the Bernstein operator of degree $n$.
| No. of continuous derivatives | Polynomial | Error bound |
|---|---|---|
| 3 | $I-(I-B_n)^2$ | 0.34895771 $||f(x)||_{C^3}/n^{3/2}$ |
| 4 | $I-(I-B_n)^2$ | 0.2753571 $||f(x)||_{C^4}/n^2$ |
| 5 | $I-(I-B_n)^3$ | 04.72840421 $||f(x)||_{C^5}/n^{5/2}$ |
| 6 | $I-(I-B_n)^3$ | 04.99618458 $||f(x)||_{C^6}/n^3$ |
Providing the full proof for these error bounds is a bit tedious, so here is a sketch. The proof involves finding upper bounds for binomial moments (discussed later), then plugging them in to estimates for the Bernstein polynomial approximation error (denoted as $(B_n-I)(f)$, $G_{n,r+1}$, and $(B_n-I)^{\lceil (r+1)/2 \rceil}(f)$as used in the paper's proof of Theorem 32.3)4, as well as derivatives for a function denoted as $F_{n,\alpha}$, along with the bound, mentioned in the proof of Theorem 32.3, that $||(B_n-I)^k|| \le 2^k$ for every $k\ge 1$. See later for Python code that calculates these error bounds.
I would appreciate any corrections.
EDIT (Aug. 6): It appears that the exact definition of the norm $||f(x)||_{C^k}$ matters a great deal. The paper Güntürk and Li (2021) defined this norm (in the univariate case) as— $$\max(||f(x)||_\infty, ||f^{(k)}(x)||_\infty),$$ where $||f(x)||_\infty$ is the essential supremum. Thus, this definition looks only at the function and its $k$-th derivative, and not any derivatives in between. However, with this definition, the results above fail in the case of the polynomial $2x(1-x)$, which is a quadratic polynomial whose third and higher derivatives vanish, as well as $(\sin(x)+2x(1-x))/2$, which is a convex combination of a concave function and a quadratic polynomial.
There are other definitions for the norm $||f(x)||_{C^k}$ that may work better, including:
- $\sum_{0\le i\le k} ||f^{(i)}(x)||_\infty,$ (see the Encyclopedia of Math and these lecture notes).
- $\max_{0\le i\le k} ||f^{(i)}(x)||_\infty,$ (Chichilnisky, G.,1986, Topological complexity of manifolds of preferences; Petersen, Philipp Christian. "Neural network theory." University of Vienna (2020)).
I don't know whether these results will hold, even for quadratic polynomials, with either definition of the $C^k$ norm, though.
END EDIT
Remark 3.4 in Güntürk and Li mentions that Theorem 3.3 works for functions with Lipschitz continuous 2nd, 3rd, 4th, or 5th derivative rather than continuous 3rd, 4th, 5th, or 6th derivative, respectively, after replacing the $C^k$ norm with the Lipschitz $C^{k-1}$ norm and making other "natural modifications". Assuming that the bounds above are true, I don't know whether they remain true under these weaker assumptions, but I conjecture that they do.
def tnrtna(n,r):
if r%2==0 and r<=44:
return (factorial(r)/(factorial(S(r)//2)*8**(S(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(83)/1000)*sqrt(n**5)
return 2*factorial(S(r)/2)*sqrt(n**r)
raise ValueError
def gnr1bnr(n,rrr,derivs):
# r=s-1, returns (Maxis no. of cont. deriv.
s=len(derivs[0],derivs[r+1]derivs)/n**-1 # No. of continuous derivatives
r=S(r+1)s-1)*sqrt(tnr
if r==0: # 1 cont. deriv; ordinary Bernstein with Sikkema constant
return (n,2*S(r+1108989)/100000)*Max(*derivs)/factorialsqrt(r+1n)
def bnerror(n,r,derivs) if r==1: # 2 cont. deriv; ordinary Bernstein
return sum(derivs[i]*tnrMax(n,i*derivs)/(n**i*factorialS(i8)*n) for
i in rangeb=2**(S(r)/2,r+1)*Max(*derivs)+gnr1/n**(n,r,derivsS(r+1)
def fnrderivs/S(n,r,alpha,derivs2):)
d=[]c=tna(r+1)/S(factorial(r+1))
fnmd=[0 for betai in range(0,(r+1-alpha)+1):]
for m in d.append((Max(derivs[0],derivs[r+1])/(n**floorrange(alpha/2)*factorial(alpha)),r+1)*\:
sumfnmd[r+1-m]=Max(binomial*derivs)*2**(beta,gr+1-m)*tnr*tna(n,alpham)*factorial
rr2=(alpha(r+1+1)/factorial(alpha-g/2) \-1
ret=S(0)
for m in range(2,r+1):
dd=[fnmd[r+1-m] for gi in range(0,min(alpha,betar+1-m)+1)))]
return d
def bnr(n,rr,derivs,r=None,gnd=True): #if r=srr2==1 and len(dd)-1,1>=2:
s is no. of cont. deriv.
s=lenret+=(derivsMax(*dd)-1/(S(8)*n))/n**(S(m)/2)
# No. of continuous derivatives
elif rr2==1:
if r==None: r=s-1
if rr==1: return bnerrorret+=((S(108989)/100000)*Max(*dd)/sqrt(n,r,derivs))/n**(S(m)/2)
gn=gnr1(n,r,derivs) else:
return sum ret+=2**ceiling(bnrS(n,rrm-1,fnrderivs)/S(2))*bnr(n,r,irr2,derivs)dd)/n**(S(i+1m)//2) \
ret+=b*c
for i inreturn range(2,r+1))+gn*2**(rr-1)ret
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]).simplify().n())
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())
- C.S. Güntürk, W. Li, "Approximation of functions with one-bit neural networks", arXiv:2112.09181 [cs.LG], 2021/2023.
- 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.