Return to Revisions

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)|),$
• $I$ be the identity operator, and
• $B_n$ be the Bernstein operator of degree $n$.

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)$ in the proof of Theorem 3.3) as well as derivatives for a function denoted as $F_{n,\alpha}$, along with the bound, mentioned in the proof of Theorem 3.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.

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 $d$-th moment is upper bounded by $\frac{d!}{(d/2)!8^{d/2}} n^{d/2}$ for even $r\le 44$ (Molteni 2022).

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 $0.083 n^{5/2}$.
  • Proof: Follows from evaluating the moment for each $1\le n \le 303$ at their critical points (resulting in $< 0.083 n^{5/2}$ for every such $n$), and for each $n\ge 304$, applying the bound $n/4+2 {n \choose 2}$ based on the upper bound given in sec. 3.1 of Skorski (2020). This latter bound, when divided by $n^{5/2}$, decreases with $n$, so it's enough to take its value at 304, namely $92188 < 0.05722/n^{5/2}$ for every $n\ge 304$.

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(83)/1000)*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 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)))
   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]).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())

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.