Optimal approximation using complex-valued neural networks
Authors: Paul Geuchen
Felix Voigtlaender
Venue: NeurIPS 2023 poster (2023)
Keywords: complex-valued neural networks
approximation rates
TL;DR: We study optimal rates for approximation using complex-valued neural networks.

Abstract: Complex-valued neural networks (CVNNs) have recently shown promising empirical success, for instance for increasing the stability of recurrent neural networks and for improving the performance in tasks with complex-valued inputs, such as MRI fingerprinting. While the overwhelming success of Deep Learning in the real-valued case is supported by a growing mathematical foundation, such a foundation is still largely lacking in the complex-valued case. We thus analyze the expressivity of CVNNs by studying their approximation properties. Our results yield the first quantitative approximation bounds for CVNNs that apply to a wide class of activation functions including the popular modReLU and complex cardioid activation functions. Precisely, our results apply to any activation function that is smooth but not polyharmonic on some non-empty open set; this is the natural generalization of the class of smooth and non-polynomial activation functions to the complex setting. Our main result shows that the approximation error scales as $m^{-k/(2n)}$ for $m \to \infty$ where $m$ is the number of neurons, $k$ the smoothness of the target function and $n$ is the (complex) input dimension. Under a natural continuity assumption, we show that this rate is optimal; we further discuss the optimality when dropping this assumption. Moreover, we prove that the problem of approximating $C^k$-functions using continuous approximation methods unavoidably suffers from the curse of dimensionality.

Optimal approximation using complex-valued neural networks
Paul Geuchen MIDS, KU Eichstätt- Ingssätt-Ingolsstdt,, Auf der Schanz 49, 85049 Ingolstadt, Germany paul. geuchen@ku. de
Felix Voigtlaender MIDS, KU Eichstätt- Ingolsttt,, Auf der Schanz 49, 85049 Ingolstadt, Germany felix. voi gt laender@ku. de
Abstract
Complex-valued neural networks (CVNNs) have recently shown promising empirical success, for instance for increasing the stability of recurrent neural networks and for improving the performance in tasks with complex-valle inputs, such as in MRI fingerprinting. While the overwhelming success of Deep Learning in the real-valued case is supported by growing mathematical foundation, such a foundation still largely lacking in the complex-valuee case. We thus analyze the expressivity of CVNNs by studying their approximation properties. Our results yield the first quantitative approximation bounds for CVNNs that apply a wide class of activation functions including the popular modReLU and complex cardioid activation functions. Precisely, our results apply to any activation function that is smooth but not polyharmonic on some non-empty open set; this is the natural generalization of the class of smooth and non-polynomial activation functions to the complex setting. Our main result shows that the error for the approximation of C* functions scales as m </(2n) for m + 0o where m is the number of neurons, & the smoothness of the target function and n is the (complex) input dimension. Under natural continuity assumption, we show that this rate is optimal; we further discuss the optimality when dropping this assumption. Moreover, we prove that the problem of approximating C* ffunctionn using continuous approximation methods unavoidably suffers from the curse of dimensionality.
Introduction
Deep Learning currently predominantly relies on real-valued neural networks, which have led to breakthroughs in fields like image classification or speech recognition [23, 27, 43]. However, recent work has uncovered several application areas in which the use of complex-valus neural networks (CVNNs) leads to better results than the use of their real-valued counterparts. These application areas mainly include tasks where complex numbers inherently occur as inputs of a machine learning model such as Magnetic Resonance Imaging (MRI) [16. 38, 44) and Polarimetric Synthetic Aperture Radar (PolSAR) Imaging [8, 9, 48). Moreover, CVNNs have been used to improve the stability of recurrent neural networks [5] and have been successfully applied in various other fields [32, 37]. The mathematical theory these complex-valuee neural networks, however, is still in its infancy. There is therefore great interest in studying CVNNs and in particular in uncovering the differences and commonalities between CVNNs and their real-valued counterparts. A prominent example highlighting the unexpected differences between both network classes is the universal approximation theorem for neural networks, whose most general real-valued version was proven in 1993 [28] (with more restricted version appearing earlier [17]) and which recently generalized to the case of CVNNs [45]. The two theorems describe necessary and sufficient conditions on
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Condition on activation function
Continuity of weight selection
Approximation Error
Theorem 3.2
smooth non-polyharmonic
possible
O (mm--/(2m)) (2n))
Consequence of Theorem 4.1
continuous
assumed
20m
Theorem 4.2
very special activation function
not assumed
O(m--/(22n))
Theorem 4.3
not assumed
+ e Re(s)
Table 1: Overview of the proven approximation bounds. k is the regularity of the approximated functions (which are assumed to be C*), n the (complex) input dimension and m the number of neurons in the hidden layer of the network. The notation Ω is similar to Ω, but ignoring log factors.
an activation function which guarantee that arbitrarily wide neural networks fixed depth can approximate any continuous function on any compact set arbitrarily well (with respect the uniform norm). Already here it was shown that complex-valuee networks behave significantly different from real-valued networks: While real-valued networks are universal if and only if the activation function is non-polynomial, complex-valued networks with a single hidden layer are universal if and only if the activation function is non-polyharmonic (see below for definition). Furthermore, there exist continuous activation functions for which deep CVNNs are universal but shallow CVNNs are not, whereas the same cannot happen for real-valued neural networks. This example shows that it highly relevant to study the properties of CVNNs and to examine which of the fundamental properties of real-valued networks extend to complex- valued networks.
Essentially the only existing quantitative result regarding the approximation ceaniiimation-hhortttcccc. properties of CVNNs [14], which provides results for approximating C* -f-ncciooonn by deep CVNNs using the m activation function. However, for real-valued NNs it is known that already shallow NNs can approximate C*-functions the optimal rate. Precisely, Mhaskar showed in [33] that one can approximate C*k fk-functions on [-1, 1J" with an error of order -k/n m - ao, where is the number of neurons in the hidden layer. Here he assumed that the activation function is smooth on an open interval and that some point of this interval no derivative vanishes. This is equivalent the activation function being smooth and non polynoomil on that interval, cf. [20, 53).
The present paper shows that comparable result holds in the setting of complex- valued networks, by proving that one can approximate every function in C* (Sn, C) (where differentiabilliy understood in the sense of real variables) with an error of the order m kk/(2n) (as m + oo) using shallow complex-valued neural networks with neurons in the hidden layer. Here we define the cube On = 1-1, + 1|". The result holds whenever the activation function Φ C C is smooth non-empty open set. This is very natural condition, since for
and hoyhpollya polyharmonic activation functions there exist C* Ck-functions that cannot be approximated at all below some error threshold using shallow neural networks with this activation function [45].
Furthermore, the present paper studies in how far the approximation order of m kk((2)) is optimal, meaning that an order of m - (where a > 0) cannot be achieved. Here it turns out that the derived order of approximation is indeed optimal (even in the class of CVNNs with possibly more than one hidden layer) in the setting that the weight selection is continuous, meaning that the map that assigns to a function f E C (S2, C) the weights of the approximating network continuous with respect to some norm C* (R,; C). This continuity assumption is natural since typical learning algorithms such as (stochastic) gradient descent use samples f(zy ( of the target function and then apply continuous operations to them update the network weights.
We investigate this optimality result further by dropping the continuity assumption and constructing two special smooth and non non-polyhammonic activation functions with the first one having the property that the order of approximation can indeed be strictly improved via a discontinuous selection of

---

the related weights. For the second activation function we show that the order of m mk/(22m) cannor be improved, even one allows a discontinuous weight selection. This in particular shows that in the given generality of arbitrary smooth, non-polyharmonic activation functions, the upper bound O (m (m)))( cannot be improved, even for a possibly discontinuous choice of the weights. An overview of the approximation bounds proven in this paper can be found in Table 1.
Moreover, we analyze the tractability (in terms of the input dimension n) of the considered problem of approximating C* -fffctuttion using neural networks. Theorem 5.1 shows that one necessarily needs a number of parameters exponential in n to obtain a non-trivial approximation error. To the best of our knowledge, Theorem 5.1 is the first result showing that the problem of approximating C* C*-functions using continuous approximation methods intractable (in terms of the input dimension n.)
1.1 Related Work
Real-valued neural networks. By now, the approximation properties of real-valued neural networks are quite well-studied (cf. [10, 28, 33, 40, 41, 46, 47] and the references therein). We here only discuss few papers that are most closely related to the present work.
In [33], Mhaskar analyzes the rate of approximation of shallow real-valued neural networks for target functions of regularity C* Our results can be seen as the generalization of [33] to the complex setting. Our proof's rely on several techniques from [33]; however, significant modifications are required to make the proofs work for general smooth non-polyharmonie functions.
One of the first papers to observe that neural networks with general (smooth) activation function can be surprisingly expressive is [31] where it was shown that a neural network of constant size can be universal. One of the activation functions in Section 4 is based on similar idea.
The importance of distinguishing between continuous and discontinuous weight selection (which in our setting is discussed in Section 4) was observed for Rel.U-networks in [47].
The paper [25] shows that neural network approximation is not continuous in the following sense: The best approximating neural network 4 (f) of a given size does not depend continuously on f E C* This result, however, is not in conflict with our results: We want to assign to any C CC-function f a network (f) that approximates f below the error threshold m -k/(2n), The network (f),, however, does not have to coincide with the best approximating network (f)).
Complex-valued neural networks. When it comes to general literature about mathematical properties of complex-valus valued neural networks, surprisingly little work can be found. The Universal Approximation Theorem for Complex- Valued Neural Networks [45] has already been mentioned above. In particular, it has been shown that shallow CVNNs are universal if and only if the activation function & is not polyharmonic. Thus, the condition assumed in the present paper (that e should be smooth, but polyharmonic) is quite natural.
Regarding quantitative approximation results for CVNNs, the only existing work of which we are aware is [14], analyzing the approximation capabilities of deep CVNNs where the modReLU is used as activation function. Since the modReLU satisfies our condition regarding the activation function, the present work can be seen an improvement to [14]. Precisely, (i) we consider general activation functions, including but not limited to the modReLU, (ii) we improve the order of approximation by a log factor, and (iii) we show that this order of approximation can be achieved using shallow networks instead of the deep networks used in [14]. We stress that our proof techniques differ significantly from the ones applied in [14]: The arguments in [14] take their main ideas from [46] making heavy use of the specific definition of the modReL.U, In contrast, since we consider quite general activation functions, we necessarily follow much more general approach following the ideas from [33].
2 Preliminaries
Shallow complex-valued neural networks. In this paper we mainly consider so-called shallow complex-valued neural networks, meaning complex-valued neural networks with a single hidden layer. Precisely, we consider functions of the form
の (0) = n²) C,
j=1
3

---

C. Here, o TT Σ/= 0,0 (p} 2 71)
p + +m) m)
V 7m
First layer
n inputs
Figure 1: Graphical representation of shallow neural network. Input and output neurons are depicted as dots, hidden neurons are depicted as circles. The term first layer describes the transformation from the input to the hidden neurons, including the application of the activation function.
with PI..... Pm E C" y mm: 7/1 .... 7m E C and an activation function Φ m N denotes the number of neurons of the network and write v² for the transpose of vector
To simplify the formulation the results, we introduce the following notation: We write F for the set of first layers of shallow complex-valued valued neural networks with activation function o, with input neurons and m hidden neurons, meaning
F n,m = {2 (0 (0} 2 m)) m Ps E C", 72 E E {F C").
Hence, each shallow CVNN can be written as o with E C and & E F n,m see Figure for graphical representation of shallow CVNN.
Approximation. The paper aims to analyze the approximation of C* ff-fucctions on the complex cuhe
02 == 1 1]Th + i[-1,1]"
using shallow CVNNs. Here, we say that function f : 2,, - in C* (* C) if and only if k times continuously differentiable on Ω2, where the derivative is to be understood in the sense of
real variables, i.c., in the sense of interpreting f as a function [-1, 1j + IR? and taking usual real derivatives. We further define the Ch-norm of a function f E C* (2,,: C)
(l == sup |8+ fl
where
||g|| (0..)) == sup [g(z)
(2.1)
kENg" KK
sEa.
for any function g Ω2, + C. Note that we write = (1,2,3,...) and No = {0} UN. Using the previously introduced notation, thus seek to bound the worst-case approximation error, i.e.,
sup (E Il
inf DEFE decm
Wirtinger calculus and polyharmonic functions. For a function f C - C which differentiable in the sense of real variables at point zo IC we define its Wirtinger derivatives at 2o as
f = 2 dz
0f 1 0f (zv) - i. Dy
(zo)
and Fwire. = 2 0r
0f (zo) +
0f θy
(20)
Here, dr and By denote the usual partial derivatives in the sense of real variables. We extend this definition to multivariate functions defined on open subsets of C by considering coordinatewise Wirtinger derivatives.
A function f U - C, where U C C open is called smooth if it is differentiable arbitrarily many times (in the sense of real variables). We write f E C (U=(UC) in that case. Moreover, f is called polyharmonic (on U) if it smooth and if there exists E No satisfying
A TH = U.

---

Voudbalt ((2)
10
[eaddeil
Re(a)
Im(e)
2
Re(a)
2
-5
Imfa)
Figure 2: Absolute value of the activation functions OmodReLU,-1 (left) and card (right).
Here, A 02
1.wirtwwie denotes the usual Laplace-Opprateee Oy²
0²
The following Proposition 2.1 describes property of non-polyharmonic functions which is crucial for proving the approximation results of this paper.
Proposition 2.1. Lel Ø U C be an open and let (=; be non-polyharmonic: Then for every M E No there exists point 2M E U satisfying
Owire 5e Win ((ar) # for all m, & E No with m, S M.
The proof of Proposition 2.1 is an application of the Baire category theorem; see Appendix B.2.
Important complex activation functions. We briefly discuss in how far two commonly used complex activation functions satisfy assumptions: The modReLU proposed in [5] and the complex cardioid used in [44] for MRI fingerprinting where the performance could be significantly improved using complex-valued neural networks. The modReLU is defined as
(1=1 + b)
if || 0,
+ C,
(.odReLU.(())
0.
otherwise,
where b < 0 is fixed parameter. The complex cardioid is defined
card:
C
card(z) == マ cos(412)2.
Here, < = 0 E R denotes the polar angle of a complex number "e where we define 40 == 0: see Figure for plots of the absolute value the two functions.
Both functions are smooth and non-polyharmonic on a non-empty open subset of C, which is proven in Appendix A.2. Furthermore, they are both continuous C. Therefore, our approximation bounds established in Theorems 3.1 and 3.2 in particular apply to those two functions.
3
Main results
In this section we state the main results of this paper and provide proof sketches them. Detailed proofs of the two statements can be found in Appendices B.3 and C.3.
First show in Theorem 3.1 that is possible to approximate any complex polynomial in and arbitrarily well using shallow CVNNs with the size of the networks only depending on the degree of the polynomial (not the desired approximation accuracy). Using this result can prove the main approximation bound, Theorem 3.2, by first approximating a given C*-function using a polynomial and and then approximating this polynomial using Theorem 3.1.
For m, n E N let
Pa
C
C. 2H Σ
Σ
am, amme2ma mz ame EC
mS m eSm
5

---

denote the space of all complex polynomials on C" in and 2 of componentwise degree at most m. Here, we are summing over all multi-indices m, l Ng with my.ez S for every j E [I,....)] and use the notation
and
==1
j=1
The space P is finite mnite-iimensional hence, it makes sense to talk about bounded subsets of Pr without specifying a norm.
Theorem 3.1. Let m. N and o: C + C be smooth and non-polyharmonic on an open sei Ø + UUSC C.C.C. Let p Pm be bounded and set N == (4m+1) + +1)an Then there exists a first layer
& e F N with the following property: For each polynomial p E P there exists CN, such that
||p o" (0. Se.
Sketch of proof. For any multi-indices m, Nj an inductive argument shows for every fixed 2 E S2 and b E C that
Jle wine o)) (w 2 + b). D wirs [w - o(w"= 2 6)] = =m (ommi
Omin
Here, 8t and Owin denote the multivariate Wirtinger derivatives with respect to w according the multi-indices m and L, respectively. Evaluating this at w = and taking b C such that none the mixed Wirtinger derivatives of á at b up to sufficiently high order vanish (where such b exists by Proposition 2.1) shows that we can rewrite
z (awice Swert [w + ow"" + b1]) -=0 ((owii wirt (6) ))))
(3.1)
The mixed Wirtinger derivatives can by definition be expressed as linear combinations of usual partial derivatives. Those partial derivatives can be approximated using a generalized version of divided differences: If E ("(((r,r)) : and p E Ně with |pl S is we have
d (0)(0) (2h) ml Σ (-1))01-11
P r
g (h(2r p)) for h X O.
(3.2)
OSTšP
See Appendix B.1 for a proof of this approximation. Note that when one takes g(w) = plw " b).
the right-hand side of (3.2) is shallow neural network, as a function of z.
Combining (3.1) and (3.2) yields the desired result; Appendix B.3 for the details.
is crucial that the size of the networks considered in Theorem 3.1 is independent the approximation accuracy c. Moreover, the first layer & can be chosen independently of the particular polynomial p. Only the weights a connecting hidden layer and output neuron have to be adapted to p.
The final approximation result is follows. Its full proof can be found in Appendix C.3.
Theorem 3.2. Let k E N. Then there exists a constant e c(n, k) > O with the following property: For any activation function C - C that smooth and non-polyhacionic on an open set Ø # U S C and for any m E N there exists first layer & E F with the following property: For any f E Ck (Rny C) there exist coefficients =f(f) C such that
|I - - -100000000)) c.cm (c-m-k/(2)) (l
Furthermore, the map f + (f) a continuous linear operator with respect to the I 1_--normm
Sketch of proof. By splitting f into real and imaginary part we may assume that f is real-valued. Fourier-analytical results (recalled in Appendix C.I) imply that each C*-function f can be well approximated by linear combination of (multivariate) Chebyshev polynomials. Precisely, we have
|l - -P (l) S m -11fllcH(

---

where P is given via the formula
P(=)= =
Σ (Z) T<();
2 Snn
05kg2m=1
Here, the functions T are multivariate versions of Chebyshev polynomials and V (f) are continuous linear functionals in f. The constant с > only depends on n and k. See Appendix C.I for a rigorous proof of this approximation property. Approximating the polynomials T5 by neural networks according to Theorem 3.1 yields the desired claim; see Appendix C.3 for the details.
Remark 3.3. Theorem I can not only be used to derive approximation rates for the approximation of -uuftintiooss but can be applied to any function class that is well approximable by algebraic polynomials. For example, can be used to prove an order of approximation of w 1/122///1 /17 for the approximation of functions f Ω2 + C that can be holomorphically extended onto some polyellipse in Can The parameter specifies the size of this polyellipse. We refer the interested reader to Appendix D for detailed definitions, statements and proofs for this fact.
4 Optimality of the derived approximation rate
In this section we discuss the optimality of the approximation rate proven in Theorem 3.2. We first deduce from general results by De Vore et al. [19] that the rate is optimal in the setting that the map which assigns to a function f E C² (2n, C) the weights of the approximating network is continuous, is the case in Theorem 3.2. However, it might be possible to achieve better degree of approximation if this map is not required to be continuous, which is discussed in the second part of this section. Proofs for all the statements in this section given in Appendices E. F.2 and F.3.
Continuous weight selection. We begin by considering the case of continuous weight selection. As mentioned in the introduction, this is natural assumption, since in classical training algorithms such as (S)GD, continuous operations based on samples f(x,) are used to adjust the weights.
In [19, Theorem 4.2] a lower bound of m k/s m-//s established for the rate of approximating functions of Sobolev regularity 2 in the following very general setting: The set of functions that is used for approximation can parametrized using m (real) parameters and the map that assigns to f the parameters of the approximating function is continuous with respect to some norm on (1,,o 1] IR). A detailed version of the proof of that statement (for C* instead of Wkkeoo is contained in Appendix E. A careful transfer of this result to the complex- valued setting yields the following theorem (see also Appendix E.
Theorem 4.1. Let k E N. Then there exists constant = c(n, k) > O with the following property: For any m E N, any map ā : C (St; C) + C that is continuous with respect to some norm on Ct (Sni C) and any map M : m + C(2,: C) we have
|| M(a(T))ll>> (Qm:C) 2 c. k/(n))
sup 1FCM
The interpretation Theorem 4. as follows: one approximates C* C*kffnnctons on Q. using set of functions that can be parametrized using m (complex) parameters and one assumees that the weight assignment is continuous, one cannot achieve a better rate of approximation than m <k((2)) As special case it can be deduced that the approximation rate is at most m m--k/ k/(2m) when approximating C functions using shallow CVNNs with m parameters under continuous weight assigmment (see Corollary E.3). One can show that this even holds for deep CVNNs. Hence, for continuous weight selection the rate proven in Theorem 3.2 is optimal, even the class of (possibly) deep networks.
Discontinuous weight selection. When we drop the continuity assumption on the selection of the weights, the behavior of the optimal approximation rate is more subtle. Precisely, are activation functions for which the rate of approximation can be improved to m =k/2nn11), On the other hand, we also show that there are activation functions for which an improvement of the approximation rate (up to logarithmic factors) is not possible.
show that there
Theorem 4.2. There exists function & E C (C; C) which is non non-polyharmonic with the following additional property: For every E N and n, E N there exists a constant e c(n, k)) > 0 such that
7

---

Im
Re
-2 -1
2
3
6
7
-1
Re((2)
U1
1/2
-2
Figure 3: Illustration of the construction of the activation function in Theorem 4.2.
for any m E N and f E C (Si, C) there is first layer & E F n.m and a vector C such that
|| oT TT (1 S Sc-m mm(2n-())))) (1lee/n))1l//l/ao.. [1
Sketch of proof. The function ø is constructed in the following way: Take a countable dense subset {ue)een of C( C), for instance the of all polynomials in and z with coefficients in Q iQ Define @ in way such that
6(= + 36) we(=))
for every = 12 and E N. Furthermore, ensure that non-pofyharmonic, let ((z) Re(x)
for every = E Q1. The smoothness of @ can be accomplished by multiplying with a smooth hump function; Lemma F.4 for details. The construction of ø is illustrated in Figure 3.
Let then f E (9x; C) be arbitrary. General results from the theory of ridge functions [22] show that there exist b1 ... bm C and 91, ".:: Im E C(2 C) such that
m
[(z)
93 (o) 1=1
22)
S.cm Rk/2n-11)1 II
1,00 (QnaC)
see Proposition F3 and Appendix for a detailed proof of this fact. Approximating the functions Øj by suitable functions Ug and expressing those functions via di 36,) yields the claim.
The preceding theorem showed that there exists an activation function for which the rate in Theorem 3.2 can be strictly improved, if one allows a discontinuous weight selection. In contrast, the following theorem shows for certain (quite natural) activation function that the rate m (/(n)) cannot be improved (up logarithmic factors), even one allows a discontinuous weight assignment. Theorem 4.3. Let k E N and
Φ: C+C,
6(2) = 1 Re((s)
Then o is smooth but non-polyharmonic. Furthermore, there exists a constant = c(n, k) > 0 with the following property: For any E N22 there exists function f E C (Ωn, C) with II (1 S 1, such that for every t E F and a E t we have
Lx -T
2 (m In(m)))k/(2n)
Sketch of proof. The idea the proof is based on that of [46, Theorem 4] but instead of the bound for the VC dimension of ReLU networks used in [46], will employ bound for the VC dimension stated in [4, Theorem 8.11] using the real sigmoid function. For detailed introduction to the concept of the VC dimension and related topics, for instance [39, Chapter 6).
technical reduction from the complex to the real case (see Appendix F.3) shows that it suffices to show the following: If æ E (0, 1) and m E N are such that for every f E * [[-1, R) with
|| [f < there exists real-valued shallow network N with 7(x) I+e-= as activation
function satisfying | 1 S E, then necessarily
-nk
n/k
m 2 c In (1/e)

---

where the constant only depends on and k.
To show that the latter claim holds, assume that and have the property stated above. Take N E such that N-R x e and consider the grid
g: V-N,..... NJ" C1-1,11"
For every a E G we pick number Zn E {0. 1} arbitrarily and construct a map / & (I-1,)] satisfying f()) = Za for very a E g. Scaling of to f ensures I| [[ Σ 1, but then f(a) cu 2a - where co (n k) > 0. By assumption,
infer the existence of shallow realevalued neural network / with y as activation function and m hidden neurons satisfying Ilf - -- ([1])))))))))) I e. But this shows
ēN-k if 2. 1, CN-k
N(a))
za =0 for all e
with a constant ē == k) O. Since the 2a are arbitrary, it follows that the set
H [(N EN =N~ A shallow NN with activation and m hidden neurons
shatters the whole grid G. This yields VC(H) 2 | (2N 1)". On the other hand, the bound provided by [4, Theorem 1]] for linear threshold networks yields VC(H) S m m-In(N). Combining the bounds and using N x yields the claim.
Tractability of the considered problem in terms of the input dimension
In this section we discuss the tractability (in terms of the input dimension n) of the considered problem, i.e., the dependence of the approximation error on n. We show a novel result stating that, assuming continuous weight selection, the problem of approximating C*-functions is intractable, ie., that the number neurons that required to achieve non-trivial approximation error is necessarily exponential in In the literature this is referred to as the curse of dinensionality. The proof the theorem combines ideas from [19] and [35] and is contained in Appendix E.2.
Theorem 5.1. Let N. With || -Ilc*(-1.)))) defined similarly to (2.1), we write
[Ifllc= == sup IIf(lc*((11)))=))) E [0, ool REN
for any function f E ([- and denote by C the set of all f (((((-,,11R)) for which this expression is finite. Let ā C + R²2 be continuous with respect to some norm on c and moreover, let M R C(--1.1]* 1];; R) be an arbitrary map. Then it holds
sup SEC
|f (a(((())) 2
Note that Theorem 5.1 is formulated for real-valued functions but can be transferred to the complex- valued setting (see Corollary E.6). We decided to include the real-valued statement because it is expected to of greater interest in the community than the complex-valued analog. Moreover, we stress that Theorem 5.1 is not limited to the class of shallow neural networks but refers to any function class that is parametrizable using finitely many parameters (in particular, e.g., the class of neural networks with possibly more than one hidden layer).
We now examine in what way the constant e appearing Theorem 3.2 suffers from the curse of dimensionality. To this end, it is convenient to rewrite the result from Theorem 3.2 as
sup I Ml 51
$EFO DEF - 1000@01 S (ā m) -k/(2m)
inf
where the constant č(n, k) > independent of m. Writing the result in that way, one sees immediately that, if one seeks to have a worst-case approximation error of less than e > 0, it is

---

sufficient to take m = E - (2m))// neurons in the hidden layer of the network. Corollary E.7 shows that it necessarily holds ē S 16 2-h and therefore, the constant è unavoidably suffers from the curse of dimensionality. An analysis of the constant (where we refer to Appendices C.1 C.3 for the details) shows that in our case we can establish the bound ē(n, k) 2 exp(-C'- -C" - with an absolute constant C > O. We remark that, since the constant suffers from the curse of dimensionality in any case, we have not put much effort into optimizing the constant; there is therefore probably ample room for improvement.
6 Limitations
To conduct a comprehensive evaluation of machine learning algorithms, one must analyze the questions of approximation, generalization, and optimization through training algorithms. The present paper, however, only focuses on the aspect of approximation. Analyzing if the proven approximation rate can be attained with learning algorithms such as (stochastic) gradient descent falls outside the scope of this paper. Furthermore. the examination of approximation rates under possibly discontinuous weight assignment not yet fully resolved by our results. which rate is optimally achievable in that case, depending on the choice of the activation function, and specifically in distinguishing between shallow and deep networks. We want to mention the two following points which indicate that this is quite subtle question:
an open question
1.
For deep NNs (with more than two hidden layers) with general smooth activation function, it is not possible to derive any non-trivial lower bounds the setting of unrestricted weight assignment, since there exists an activation function with the property that NNs of constant size using this activation function can approximate any continuous function to arbitrary precision (see [31, Theorem 4]). Note that [31] considers real-valued NNs, but the results can be transferred to CVNNs with a suitable choice of the activation function.
2. In the real-valued case, fully general lower bounds for the approximation capabilities of shallow NNs have been derived by using results from [22] regarding the approximation properties of so-called ridge functions, i.e., functions of the form Σj=1 (ay) x)) with
aj E TRdd and each وi R + R. It is an interesting problem to generalize these results to higher-dimensional ridge functions of the form Σø=1 Øy (Ayæ), where each Øy : R TR
and A, E xxx This would imply lower bounds for shallow CVNNs. However, such a generalization seems to be highly non-trivial and is outside the scope of the present paper.
7 Conclusion
This paper analyzes error bounds for the approximation of complex- C* ffnccions by means of complex-valued neural networks with smooth and pon-polyhammonic activation functions. It demonstrated that complex-valued neural networks with these activation functions achieve the identical approximation rate as real-valued networks that employ smooth and non-polynomial activation functions. This is an important theoretical finding, since CVNNS are on the one hand more restrictive than valued neural networks (since the mappings between layers should be C-linear and not just R-linear), but on the other hand more versatile, since the activation function is a mapping from C to C (i.e., from I + R²) rather than from IR to I as in the real case. Additionally, it is established that the proven approximation rate is optimal if one assumes a continuous weight selection. In summary, if one focuses on the approximation rate for C* ffunctiis CVNNs have the same excellent approximation properties as real-valued networks.
The behavior of the approximation rate for unrestricted weight selection is more subtle. It is shown that rate of m k/(2n-1) can be achieved for certain activation functions (Theorem 4.2) but in general, one cannot improve on the rate that is attainable for continuous weight selection (Theorem 4.3).
While the proven approximation rate is optimal under the assumption of continuous weight selection, the involved constants suffer from the curse of dimensionality. Section 5, however, shows that this is inevitable in the given setting.
Such theoretical approximation results contribute to the mathematical understanding of Deep Learning. The remarkable approximation -hhttiittteeeotiiccall properties of neural networks can be seen as one reason why neural networks provide outstanding results in many applications.
10

---

Acknowledgments. PG and FV acknowledge support by the German Science Foundation (DFG) in the context of the Emmy Noether junior research group VO 2594/1-1, FV acknowledges support by the Hightech Agenda Bavaria.
References
[1] M. Abramowitz and I. A. Stegun, eds. Handbook of mathematical functions: with formulas, graphs, and mathematical tables. Dover print. Dover books on mathematies. New York. NY: Dover Publ, 2013. ISBN: 0--88-61272--0
[2] B. Adcock, S. Brugiapaglia, and G. Webster. Sparse polynomial approximation of digg-ddimessoonll functtins. Computational science and engincering 25. Philadelphia: Society for Industrial and Applicd Mathematics, 2022. 292 pp. ISBN: 978-1-61 197-6878..
[3] C. D. Aliprantis and K. C. Border. Infinite dimensional analysis: a hitchhiker's guide. 3rd cd. Berlin; New York: Springer, 2006, ISBN: 978-3-540-29586.4
[4] M. Anthony and L.. Bartlett. Neural network learning: theoretical foundations. foundatialoo
Cambridge; New York,
NY: Cambridge University Press, 1999. ISBN: 978-0-521-57353-55
[5] Arjovsky. A. Shah, and Y. Bengio. "Unitary evolution recurrent neural networks". In: International conference on machine learning. PMLR. 2016, pp. 1120-1128.
URL: attp:/// httt:://prrceeeee pttp///rreeeee...ee/e/ mlr.
press/v48 arjovkky6.. .df.
[6] K. E. Atkinson. An introduction to numerical analysis. 2nd ed. New York: Wiley, 1989. ISBN: 978-0-
471 971-62489-9.
[7]
M. B. Balk. Polyanalytic functions. funcctiooni Mathematical research 63. Berlin: Akademie Verlag, 1991. ISBN: 978-3-05-501292-11
[8] J. A. Barrachina, C. Ren, C. Morisseau, G. Vieillard, and J.-P. Ovarlez. "Complex-vallee valued vs. real-valued neural networks for classification perspectives: An example on non-circular data". In: ICASSP 202/-202/ IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP). IEEE. 2021, pp. 2990-2994.
[9] J. A. Barrachina, C. Ren, C. Morisseau, G. Vieillard, and J.-P. Ovarlez. "Comparison between equivalent architectures of complex-valued and real-valued neural networks Application on polarimetric SAR image segmentation". In: Journal of Signal Processing Systems 95.1 (2023), pp. 57-66.
[10] A. R. Barron. "Universal approximation bounds for superpositions of a sigmoidal function". In: IEEE Transactions on Information theory 39.3 (1993), pp. 930 945. DOI: 10. 1109/99/ 256500.
[11] H. Bauer. Measure and integration theory. De Gruyter studies in mathematics 26. Berlin New York: W.
de Gruyter, 2001. 230 pp. ISBN: 978-3- 11016619--1.
[12] A. Benjamin and J. J. Quinn. Proofs that really count: the of combinatorial proof. Dolciani mathematical expositions. Washington, DC: Mathematical Association of America, 2003. ISBN: 978-0- 88385-333-7.
[13] D. Berend and T. Tassa. "Improved bounds Bell numbers and on moments of sums of random variables". In: Probability and Mathematical Statistics 30.2 (2010), pp. 185-205.
[14] A. Caragea, D. G. Lee, Maly, G. Pfander, and F. Voigtlaender. "Quantitative Approximation Results for Complex- Valued Neural Networks". In; SIAM Journal on Mathematics of Data Science 4.2 (2022), pp. 553-580, DO1: 10. /137/21M1-1 129440940.
[15] H. Çevik, E. Acar, and Çunkaş. "Day Ahead Wind Power Forecasting Using Complex Valued Neural Network". In: 2018 International Conference on Smart Energy Systems and Technologies (SEST).
2018, pp. 1-6. DOI: 1109//1010000000 /109/SEST... 2018. 8495637.
[16] E. Cole, J. Cheng. Pauly, and S. Vasanawala. " "Analysis of deep complex-valee valued convolutional neural networks for MRI reconstruction and thase-focused applications". " In: Magnetic resonance in medicine 86.2 (2021), pp. 1093-1109.
[17] G. Cybenko. "Approximation by superpositions of a sigmoidal function"' In: Mathematics of Control, Signals, and Systems 2.4 (Dec. 1989), pp. 103-314. DOI: 10. 1007 L007/BF02551274
[18] K. Deimling, Nonlinear Functional Analysis. Dover books on mathematics. Dover Publications, 2013. ISBN: 978-3-662-00544--1
[19] R. A. DeVore, R. Howard, and C. Micchelli, "Optimal nonlinear approximation". In: Manuscripta Mathematica 63.4 (Dec. 1989), pp. 469-478. dor: 10. 1007 /07/BF01171759
[20] W. F. Donoghue. Distributions and Fourier transforms. OCLC: 45151. New York: Academic Press, 1969. ISBN: 978-0-12-220650-44
[21] G. B. Folland. Real analysis: modern techniques and their applications. 2nd ed. Pure and applied mathematics. New York: Wiley. 1999 ISBN: 778-0-471-317166
[22] Y. Gordon, V. Maiorov, M. Meyer, and S. Reisner. "On the Best Approximation by Ridge Functions in the Uniform Norm". In: Constructive Approximation 18.1 (Jan. 1, 2001), pp. 61-85. DOI: 10. 000365 001 0009- 5.

---

[23] A. Graves. A.-R. Mohamed, and G. Hinton. "Speech recognition with deep recureett neural networks". In:
2013 IEEE International Conference Acousticy, Speech and Signal Processing. 2013, pp. 6645-6649.
DOI: 10. 1w111110/CSS. /IAISIIIS..... 2013. .63399777
[24] W. P. Johnson. "The Curious History of Faa di Bruno's Formula". In: The American Mathematical Monthly 109.3 (Mar. 2002), p. 217. DOI: 10. 20..337//696355
[25] P. Kainen, V. Kúrková, and A. Vogt. "Approximation by neural networks is not continuous", In: Neumcompuring 29.1 (1999), pp- 47-56. DOt:
httg//0.101//50000 1016/50925 2312 (99) 00111-
3.
[26] L. Kaup and B. Kaup. Holomorphic Functions of Several Variables: An Introduction to the Fundamental Theory. De Gruyter, Dec. 1983, ISBN: 978-3-11-0041500 DOI: 10.
[27] A. Krizhevsky, I. Sutskever, and G. E. Hinton. "ImageNet classification with deep convolutional neural networks". In: Communications of the ACM 60.6 (May 2017), pp. 84-90. DOI: 10. /165680
[28] M. Leshno, V. Y. Lin, A. Pinkus, and S. Schocken. "Multilayer feedforward networks with a nonpolynomial activation function can approximate any function". In: Neural Networks 6.6 (Jan. 1993),
pp. 861-867. DOI: 10. 10110001118990 60800066000000000000000000000000 (05) 80131-5.
[29]
G. Lorentz. Approximation of Functions. Approximation of Functions. Holt, Rinehart and Winston, 1966.
[30] V. Maiorov. "On Best Approximation by Ridge Functions". In: Journal of Approximation Theory 99.1 (July 1999). pp. 68 94, DOI: 10. 1006/ jath. 1998 3304.
[31] V. Maiorov and A. Pinkus. "Lower bounds for approximation by MLP neural networks". In: http::://6ol.orgg1001111//////// wttg//..111///999222. 2382 00111-
Neuroccmputting 25.1 (1999), pp. 81-91. DOE: https: //do:::////ooooe
8.
[32] A. Marseet and Sahin. "Application of complex-valuck convolutional neural network for next generation wireless networks". In: 2017 IEEE Western New York Image and Signal Processing Workshop (WNYISPW). 2017, pp. 1-5. DOt: 10. 1119//WYIPP 2e..2.11...5.0.. 83562600.
[33] H. N. Mhaskar. "Neural Networks for Optimal Approximation of Smooth and Analytic Functions". In: Neural Computation 8.1 (Jan. 1996), pp. 164-177. DOT: 10.
1996. 8. 1. 1.16..
[34] C. Muscalu and W. Schlag. Classical and multilinear harmonic analysis. Volume 1. OCLC: 887742576.
Cambridge, UK: Cambridge University Press, 2013. ISBN: 778-0-521-88245-
[35] E. Novak and H. Wožniakowski. " Approxxmmatinn of infinitely differentiable multivariate functions is intractable", In: Journal of Complexity 25.4 (2009), pp. 398-404. DOr: https://dos otg//...11//// 1016/j
jco. . 20080008.. 10.002.
[36]
A. Pinkus. Ridge functions. Cambridge: Cambridge University Press, 2016. ISBN: 978-1-107-12439
[37]
Y.-D. Qu, R.-Q. Zhang, S.QQ. Shen, J. Yu, and M. Li. "Entanglement Detection with Complex-Valued Neural Networks". _ In: International Journal of Theoreticul Physicx 62.9 (2023), p. 206.
[38] H. El-Rewaidy, U. Neisius, J. Mancio, S. Kucukseymen, J. Rodriguez, A. Paskavitz, B. Menze, and R. Nezafat. "Deep complex convolutional network for fast reconstruction of 3D late gadolinium enhancement cardiac MRI" In: NMR in Biomedicine 33.7 (2020), e4312.
[39] S. Shalev-Shware and S. Ben-David. Understanding machine learning: from theory to algorithmss. New York, NY, USA: Cambridge University Press, 2014. 397 pp. ISBN: 978-1-107-057113-
[40] Z. Shen, H. Yang, and S. Zhang. "Deep Network Approximation Characterized by Number Neurons".
In: Communications in Computational Physics 28.5 (2020), pp. 1768-1811. 1811. DOL: https: : doi. org/
10.
OA 2020 0149.
[41] J. W. Siegel and J. Xu. "Approximation rates for neural networks with general activation functions", In: Neural Networks 128 (2020), pp. 313-321. DOI: /tttpa///oi.... org/10. 1016/j neunet. 2020. 05. 019.
[42] P. Stein. "A Note on the Volume of Simplex". In: The American Mathematical Monthly 73.3 (Mar. 1966). p. 299. DOE: 10. 20022337/2333 /2315553
[43] A. Vaswani. N. Shazeer. N. Parmar, Uszkoreit, L. Jones. A. N. Gomez, L. Kaiser, and Polosukhin. "Attention All you Need". In: Advances in Neural Information Processing Systems. Ed. by Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Vol. 30. Curran Associates, Inc., 2017. URL: https: : http///pcceeeen..eeeee///// neurips. cc hwpppaap_...e files/ happaper////////e/////eeeeaaaa/e / 2017/ .dff.
[44] P. Virtue, S. X. Yu, and M. Lustig. "Better than real: Complex-valued neural nets for MRI fingerprinting..
In: 2017 IEEE International Conference on Image Processing (ICIP). Beijing: IEER, Sept. 2017, pp. 3953-3957. ISBN: 978-1-9990-21177770700
DOI: 10. www./1999IIIP.. 2017 201778297724.
[45] F. Voigtlaender. "The universal approximation theorem for volplex-valued neural networks". In: Applied DOI: 10. 1016/ acha.
and Computational Harmonic Analysis (Dec. 2022). $1063520322000014,
2022. 12. 002.
[46] Yarotsky. "Error bounds for approximations with deep ReLU networks". In: Neural Networks 94 (Oct. 2017). pp. 103- 114, DOL: 10. 1016]. neunet. 00...7..00 07.002.
12

---

[47] D. Yaroisky and A. Zhevnerchuk. "The phase diagram of approximation rates for deep neural networks". In: Advances neural information processing systems 33 (2020), pp. 13005-13015. URL: https:// /// proceedings neurips cc/ pdf.
[48]
Z. Zhang. Н. Wang, F. Application in Polarimetric SAR Image Classification". In: IEEE Transactions on Geoscience and Remote Sensing 55.12 (2017), pp. 7177-7188, DoI: 10. 1109/TORS 2017 2743322..
Y.-Q. Jin. "Complex Valued Convolutional Neural Network and Its
13

---

A Notation, Wirtinger derivatives and special activation functions
A.1 Notation and Wirtinger derivatives
Throughout the paper, multi-indices (i.e., elements of N are denoted using boldface. For m E Ng we have the usual notation |m| Σラ=1 my. For a number m No and another multi-index p Nj we write m S m iff my I for every j E {1, n and m S p iff my S Pj for every j E {I,..., Furthermore we write
-
==1
for two multi-indices E N6 with r S p. For complex vector E C we write
m
and
j=1
For point E _n and r > 0 we define
(x) == || y| <r}
with denoting the usual Euclidean distance. This definition is analogously transferred to C".
C is canonically isomorphic 2 by virtue of the isomorphism
Pn
1
Co I2
2m
(Zi, Ens y1. yn) + (x1 + igg. In + iy.).
(A.1)
The Wirtinger derivatives defined in Section 2 have the following properties that we are going to use, which can be found for example in [26, E. Here, we assume that U C C is open and f E C' (U:
1. Swirt. and wwirt are both C-linear operators on the set CU:
2. f is complex-diiferentiabb in = E U iff wwirt I [() = 0 and in this case the equality
f = f'(2)
holds true, with (z) denoting the complex derivative of f at 2.
3. We have the conjugation rules
Jwint TwirtJ and TwirtJ = Jwirt..
4. If g e (U; the following product rules for Wirtinger derivatives hold for every U:
Owin (f (2) fw) g(z) + f(z) (w))
Dwin (f (z) fz) g(=) f(z) @wingg()).
This product rule is not explicitly stated in [26] but follows easily from the product rule for and
@ Oar
Ø By.
5. If V C C is open set and C² C²(V:C) with g(V) U. then the following chain rules for Wirtinger derivatives hold true:
Dwint (f g) [(@wire g] Owing + [[Owtee.) og] Owing,
Swirt (f g) = [(0wirt f) o g) Twing + (wwirt)) o og] Twirtg.
6. If f E (U: then have
Af(2) (wwindwiet)) (z)
for every U, with A denoting the usual Laplace- A = =(2.0) 0(0.2) (cf. [7. equation (1.7))).
For open set U C function f E C* (U;C) and multi-index & Ng with E we write De and d' for the iterated Wirtinger derivatives according to the multi-index L.
14

---

Proposition A.1. Let U S C² be an open set and f (U; C). Then, identifying f with the function f Su with Pn as 1.r, any multi-indices m, Nj with Im + L we have the representation
8 ore =
E
f8 VaEU
(p' p" EN
p'=p"=m+t
with complex numbers by E C only depending on p. n and & and writing p = (p' pp'p")) for the concatenation the multi-indices p' and p" N6. In particular, the coefficients do not depend on
Proof. The proof is by induction over m and l. We first assume m = and show the claim for all E Ng with |e] < k. In the case L = 0 there is nothing to show, so we assume the claim be true for fixed l E Ng with [6] < and take E {1,-.. ni arbitrarily. Then we get
Jate f(a) = Twire 5eh wints(
IH
Σ
Dwoii ( (a)
P= "AD''""'E 1E D'+p"=l
Up (il0' (g1t'os;1") (a) + 2
ibp (glo (2)))))))))) (a)
E
(p p")en"" D' =t
E
bp (0 (a),
p=(p EN)" p' -ttt-tto
to be shown.
Since we have shown the case m we may assume the claim to be true for fixed m, l E NB with m + El < k. Then we deduce
0
mmte: D Iwint(a) = Owin 2m Fe
wirt wirt (a)
Σ
bp wirt (0P (a)
"''''"") p'+p"=m+e
bp
(gln' (ole'tesa""))) (a)
ibp
(glr tess))) (a)
2
2
p=(p' Ne +p"" m++
Σ
bp (0P (a).
(= (=(p'p"))e p' EN P' p'tp" ++ppm=+tto:
Hence the claim follows using the principle of mathematical induction.
Proposition A.1 is technical but crucial: In the course of the paper we will need to approximate Wirtinger derivatives of certain functions. In fact, however, will approximate real derivatives and take advantage of the fact that Wirtinger derivatives are linear combinations of these.
A.2 Concrete examples of activation functions
In this section we analyze concrete activation functions that are commonly used in practical applications of complex-valuee valued neural networks. We are going to show that those activation functions are smooth and pon-oolyaaimonic on some non-empty open subset of C. Our first result analyzes family of "real activation functions interpreted as complex activation functions".
Proposition A.2. Let p E C (TR: IR) be non-polynomial and ler vi> C + be defined as
((2) = p(Re(z)) resp. (bx) == p(Im(=)).
Then is smooth and ton-polyharmonic.
15

---

Proof. Since &b depends only on the real-, resp. imaginary part of the input, we see directly from the definition of the Wirtinger derivatives that
Swirt (z) = wiitt (²) = 200 (Re(z))
resp. (w))))(()) = -wwirt = - (1((m(2)).
Hence see for arbitrary m, E No that om D win (b)) 2 (
8eh win (b()
poatel/mmtt 2m plmtt (Im(2))
resp.
Since is non-pon con-polyoomial we can choose a real number æ, such that pl + for all n E No (cf. for instance [20. p. 53]). Thus, Owire D (b) o for all m, E No, whenever 2 E with
Re(z) x, Im(z) y. respectively.
Next, we consider the modReLU which was defined Section Theorem A.3. Let (-o0, 0). Writing moddReLU, b. has for every E C with |2| |2|+b>> 0 the identity
m = = 0,
1,
(omir Jr owire (2)
b. Qm.E
1 1,2,, 2 2+ 1,m
qm.t
T=
for every m E No and E E No. Here, the numbers qm,t are non-zero and rational. Furthermore, note that all cases for choices of m and are covered, by observing that we either have the case
m 2 + (where either m 2 2 or m = 1, = 0) or m I ++ 1, where the latter case is again split into i = 0 and f 1.
Proof. We first calculate certain Wirtinger derivatives for 2 * 0. First note
1
1
1 | mm
0 Owirt
(1100)
(
|=|m
2
12/m
2 Re(2z)
+ i Im
2
12|m+2
m+2
and similarly
Swirt
2
22 m2
for any m E N. Using the product rule for Wirtinger derivatives (see Appendix A.1), we see
Twirt
x² =
Twirt (2²)
1
+ 2f
Twirt
= m 2+1
(A.2)
|2/10
1m/m
|2/100
2
| fmm+3
=0
for any m E N and E Ny and furthermore
zl
Swirt
Owirt (2²)
+ zf
Owirt
|
12 mm
|2( mm
l. xe e-1
2
m
12 m
2
2
m+42
(A.3)
2
1 m
for m, & E N. and finally
Swirt
zf
Dwirt
(z7)
+ 2" Owirt
1
m
zf+1
(A.4)
[z|m
1> m
|
2
|
12|++2
0
16

---

for m E N and E No-
Having proven those three identities, start with the actual computation. We first fix 0 and prove the claimed identity by induction over The case = 0 follows directly from the definition of the modReLU and for = 1, note
o (2) Swiet (2) +b Twirt
2
(A22 b.
[2]
2
=0
which is the claimed form. Then, using induction, we compute
0 wint (2) Swirt (b (b.90.
xtt1
(A2)
2
2+2
|
q0,e"
2
1z
26+3
=100.
so that the case = O is complete.
Now we deal with the case m I E The case and
1 proven by computing
(w) Owir((z) Swirt
z
b
1
1=
so we can assume > O. Since we already dealt with the case 772 O, we can inductively assume the claim be true for fixed m Then compute
I "win (z) Swirt (6.9m.e
2f-m+1
1 (A.) b qm,t" (-m
f-m
12/2
2
26+1
which is of the desired form. Note that (A.3) is indeed applicable because m7 + 1 122 1.
Finally, we consider the case where 2 8 + 1 and m 2 2. The case m + 1 has already been
shown. Using induction, we see
(=) Swirt (((m))=(1,0)) + Qm,t
2m-1
(A.4) b Am.e (-m +
mm-
2
=iqm+1,e
so the proof is complete.
From Theorem A.3 we can now deduce that the modReL. is smooth and non non-polyharmonic some non-empty open subset C.
Corollary A.4. Let b E (=o0, 0) and C with |a| b. Then we have
I Owine
moireemddeee #0
for all m, E No. In particular, Ro is smooth and non-polyharmonic on the set
{ C: |2| -b).
Furthermore, OmodReLU,p continuous on the entire complex plane.
Proof. The first part follows from Theorem A.3 by noting that if |2] > -b have in particular
[x] > b/2 and [z] > O. For the second part, we first note that GmodReLU,6 is trivially continuous in
E C if |2| -b. Hence, assume [2| bb. Take any sequence (2,) with 2, j oo
and note
10 0, \|z,l + + O. if if b.
if if < b
(mmodReLU.((.) (0mod)))mmmmm =
(
This shows the continuity of mmodReLU,
17

---

Next we analyze the complex cardioid, which was defined in Section 2. Theorem A.S. For any E C with + O and any m, & E No we have
2
+
=1 4
m l 1= 0, m S l + O, m ( 1 ==
am,E
2 m 2
b
t F wirt wirt card(z)=
am,e 2
bm.
m = m=(+1>1 1,
zm-f-2 1-2
am. 2m
b
[=|2m 3
m 2
Here, the numbers dm,e and bm, are non-zero and rational. Furthermore, note that all cases for possible choices of m and are covered: The case m S. E is split into { = and E + 0. The case and m 1. Then, the case 2 2+ remains.
E is split into
Proof. For the following we always assume E C with z + 0. Then we can apply the identity cos( <2)
Re(=)
so we can rewrite
Re(z)
1 ( (2+2))
1
|
(=)
(A.5)
2
[2]
2
4
4
This establishes the case m E = O. Next, we compute
1
Re(
2))
2 lmm())
Swirt (|2|)
+
=
(A.6)
2 2
12
2
|2|
2
and similarly
2
Owirt (1=1) =
(A.7)
2 a
We deduce
Twiet card(2) (A.2)(.))) 1
23
+
3
|
=:bo,1
=:0,,1
Using induction, derive
zl
2442
wirt card(2) 00 wiirt
+ bu @wirt
12|26-1
|2|28+1
(A.2)
2l
+++1
28 +f++1 1
243
00.5
2
| 28-1
bo.t
2
12/2643
1100,111
so the claim has been shown for some m E No with m < E, we get
If we now fix any E N and assume that the claim holds true
=2+22m
gm+id Jrin card(2) dwiit wirt
12/2e-11
bm,e@wire
|2|25+1
(A.3) Om :
2 m
2-m--1
22 12
Dmme
3
m
2
-422mm-1
|
m00 1.e
=bbutt,e
so the claim holds true < l.
The case m = + is split into the case m = and m > 1. If m = 1, then = 0 and we compute
Owirt card(2) (A.37)
1
2
z
+
2
+
2
4
2
2
[
8
18

---

If m > 1, we get
22
T witt win card(z) = weie@wirt
+ bege Swirt
12|26-1
(2|20+1
(A.3)(A))
28 +
Og,E
2
2 |
+ bae
2
2
2 222+1
1,
mche 1.2
Next, we deal with the case m 2: Here, we see
1
2
wire wirt card(z) = Swirt
S1=0
+ ac+1.
+
be+1le
2
|2|20+1
12|2E4]
(A3))AA)
OE+18"'
2l +
2
2/2243
z²
bEt1.
1
28 + +1
2
1 12(2(+1*
=ibe42,t
we assume the claim to be true for a fixed m 2 l + 2, we get
zm-e
zm
gm+110
Owiet card(z) = amn.t. Owirt
[2/2m11
+ bm, Swirt
|2|
1x|2m-3
(A.) am,8'
2m 1
zm+l-E
2m - 3
gm am---- E-1
+ bm,e"
2
12 2m++
|2| 122m-
=00m++1 1.
=:bme+1.e
Hence, using induction, we have proven the claimed identity.
The statement regarding the non-polyharmonicity of the complex cardioid is formulated in the following corollary.
Corollary A.6. For every with & U.B. iR and every m, l No we have
0 Duin card(z) + 0.
In particular, card smooth and non-polyharmonic on C\ (RUiR). Futhermore, card is continuous on the entire complex plane.
Proof. We start with the first part of the corollary. For the following, let z E C with & R U iR, ie..
Re(2) and Tm + O. Using the definition of card,
card(2) (2)
2 = 0 or cos( (12) = --
E Rgo
and thus, card(2) 2) * 0 since (m) * 0. In the case I l * we Theorem A.5 to get the following chain of implications:
S 8d win. card(2) )) < am,e b 1z|
22 12/2
am,t b
+
holds, and thus 2m Jr card(z) + for UR.
For the case m = f 1 = 1, note
Owir card (2) + 2 3
|z|
3
1 Im(2) = Im(2) 0,
Im (2)
2
8
8
and thus Owirt card(2) # since R.
For m + 1, we see by considering the real- and imaginary parts that
8t-10 wint card(z) = 0 + am, + Um, = 0
Re(=)) 3
Um,t + bm.. = and am.t + Dm,t = 0 + am,t = bm,8 = 0.
19

---

wirt card(z) 2) * since am,t * 0 # b,.t by Theorem A.5. and hence 0 wirt Therefore, remains to consider the case m 2 + 2. But here we casily see
O o wir card(z) = 0 Om,
z²
2/2 + bm,
+
E IR +
ZERUR
and hence 8 Owir card(z) A O. Since all cases have been considered, the claim follows.
Regarding the second part of the corollary, first note that card is trivially continuous C (0). Further note that
2 ( 1 Re(z) |
card(z)]
- |2| -
as z - 0, showing the continuity of card on the entire complex plane C.
B Postponed proofs concerning the approximation of polynomials
B.1 Divided Differences
Divided differences are well-known in numerical mathematics as they are for example used to calculate the coefficients of an interpolation polynomial in its Newton representation. are interested in divided differences since they can be used to obtain a generalization of the classical mean-value theorem for differentiable functions: Given interval I C R and + pairwise distinct data points To, .... Pn E well as an n-times differentiable real-valued function f - IE, there exists & E (min (ro, ..., xn. max {ra, .., Fn such that
our case, we
(() ne!
f [To...., mn.
where the left-hand side is divided difference of f (defined below). The classical mean-value theorem obtained in the case 1. Our goal in this section to generalize this result multivariate setting by considering divided differences in multiple variables. Such a generalization is probably well-known, but since we could not locate a convenient reference and make the paper more self-contained, we provide proof.
Let first define divided differences formally. Given n-+ data points (æo. vo) .... (In, 3r)) RRR with pairwise distinct Zk. we define the associated divided differences recursively via
[yk] == yk. le E {O....,.2) n..
yk+1 W Wk+y] 19k. "kk...,Wk+s-11) Wk+s-11
[yle ... +
j (I,..,,,) n), , k {o,..., 5}.
Øk+j 3tk
the data points are defined by a function f (i.e. yk = f (xx) for all E n)), we write "i....,.k++] f = [yk: ..., Mk+tsl
We first consider alternative representation of divided differences, the so-called Hermite- Genocchi- Formula. To state it, we introduce the notation * to denote a certain k-dimensional simplex.
Definition B.I. Let s N. Then we define
E = NEER: xz 0 for all l and
Σ
<
Em
We further Σ (0) C R.. Denoting by X the s-dimensional Lebesgue-measure (and by o the counting measure), the identity X (23) = holds true; see for instance [42] and note that the case 0 can be seen directly.
consider integrals over the sets Σ'. These integrals are always formed with respect the measure X². However, we only write, e.g., Js. (=)dr, with the implicit understanding that the integral is formed with respect to the measure X² Üsing this convention, we can now consider the alternative representation of divided differences.
In the following,
20

---

Lemma B.2 Hermite-Genocchii- Genocchi-Formuiae Let &o & Ny. For real numbers a. b E R with < b, function (*a b]; IR) (where C (aa,, B); denotes the set of continuous functions) and pairwise distinct To, ..., Fk E (a, by, the divided difference of at the data points To. vo.....9.. T.. satisfies the identity
k
ro mx
((6)
30
Σ
88 (xt - v0) ds.
(B.1)
1=1
Proof. The case follows directly from [zolf = f(o) For the case 0, see [6, Theorem 3.3].
We will make use of the above formula by combining it with the following generalization of the mean-value theorem for integrals.
Lemma B.3. Let D be a connected and compact topological space. Let A be some o-algebra over RR be a continuous
D and let μ A + [0, oo) be a finite measure on D with μ(D) 0. Let f function with respect to the standard topology on IK and the topology on D. Moreover, let f be measurable with respect to A and the Borel a-algebra R. Then there exists D such that
M(D) J. f(z)dp(x).
f(E)
Proof. Since D is compact and connected and f continuous, it follows that f(D) C R is compact and connected, and hence fDD is a compact interval R. Therefore, there exist Tmin E and Tmax D satisfying
J (Fmin) S (xx S (Jimax)
for all x E D. Thus, gets
1
I ((mia)dpp()) S ((D) /DD [(x)du(s))
(Fmia)
(uDD)
1
(DD (1rmx) (Xrmax
The claim now follows from the fact that (DD is an interval.
We also get convenient representation of divided differences for the case of equidistant data points. Lemma B.4. Let f / R - R. 2o E RR No and O. We consider the case of equidistant data points, meaning zj zo jh for all j = 1, ... k. In this case, we have the formula
[ro ok f= R!NE
Σ (-1)
s (xx).
(B.2)
Proof. We prove the result via induction over the number j considered data points, meaning the following: For all {0,... k} we have
1-1) (c) (2(+r)
[ zetslf
r=0
for all é {O..., k} satisfying (+ j k. The case j = trivial. Therefore, we assume the claim to be true for a fixed {0, ....... k - 1}. and let l E {0, k} be arbitrary with + + + s k. We then get
[r441,... Zz 01- [ o8t1lf
Ut+j+1 Zt
IH 1
E 1-10 (2) (ʃ (Fe+r+1) I (xe++))
jihi
(j + 1)h
Σ (-1 () (f (xeer+1) - (xc+r))
+ 111hiI
r=0
21

---

Using an index shift, we deduce
1-1ーー ()) (Be+rt1)
Σ (-10-- (?) (IetT)
3+1
( r-1
+ (-115t1- {
( (Ie4t)
(1(tt)
r=0
+ Σ (f
((--1) + (2)) + (xo+s+1)
(-1)+t((22)
r=1
+ 1) (5+1) I (wett))
r
which yields the claim.
The final result for divided differences, which is the result that is actually used in the proof of Theorem 3.1 in Appendix B.3, reads follows:
Theorem B.5. Let f: R² - IR and h E No.r > O, such that fl fk(-nn E O² ((-r,r));RB For p E N6 with |p| < and > let
Σ (-1))1- (?) of (h(22 (h(22- -p)).
fpr = (2h) lpl
OSrSp
Let max p,. Then, for 0 h mm there exists & hl-mm, m]}* satisfying
fp. = 8 f(E).
Proof. We may assume m 0, since m implies and thus fp.1. = [(),, so that the claim holds for O.
We prove via induction over E N that the formula
fp.h = p!. S S ... f Jm
Jf
hpp + 2h
P1
lo
(1)
hp, + 2h
Eo(())
()
(B.3)
holds for all p Nj with 1 S pp < and all h < I. The case exactly the CeeeeeGGinoooooonne (B.1), combined with (B.2) applied the data points
-hp. -hp + 2h, ... hp 2h, hp.
By induction, assume that the claim holds for some s E N. For fixed point y (-r,r). let
fy (-r,r)" - R x f(x, v)
For p Not with lpl and p' = (P1, (..,...; Ps), we define
T: RR, R, 4 (fo)pr = (2h)-10 -1 Σ (-1))01-1r1 (P) f (h(2r - up)).))
(P)))
0Sr'Sp'
Using the induction hypothesis, we get T(y)
P.
P.
=p'!
a(v'.)) (hip, + 2h
Σ
to
(1)
hp.
+ 2h
lo! y do!l do
Fe XP--1
DP:
1=1
E=1
22

---

for all y E (-r,r). Furthermore, we calculate
Pot1 [-h Pat1: -h Pot1 + 2h...., h. Po+1lr
P++1
(2h) P.+1
(-1)
Ps-1 )r (h (2r' -Pst1)
[
r'=0
P++1
(2h) Pa+1
Σ
(-1) Po+1
Ps+1
(2h) (2h)-lp1
m==
(D') (h(2r' -2),,(22'' - -P.+1))
Σ
(-1)19'-11))
0Sr'S'' Sp'
(2h)-10
(-1)lpl-1r)
:) (h(2r p))
0Srsp
fpp.-
On the other hand, we get
[-h
Ps+1:
-h P
2h,..., Px41
(B.1)
f spet1
r(P++1)
-iiPot1 + 2h
la (0+1) da(st1)
Pj
Pats
p'!
S -lip: + 2h
to (1)
1pp + 2h
(a+1) lo
do (1)
... do (++1)
3Po+1
E>1
8=1
Interchanging the order of integration and derivative is possible, since we integrate compact sets and only consider continuously differentiable functions (see, c.g., [11, Lemma 16.2]).
We have thus proven (B.3) using the principle of induction. The claim of the theorem then follows directly using the mean-value theorem for integrals (Lemma B.3) applied to the topological space
D := P1
P.11
equipped with the product topology where each factor is endowed with the standard topology on Pr (where the standard topology on 2 the discrete topology), the measure
AP
A
defined on the product of the Borel alageebras y (and the o-algebra of {0} is its power set) and to the function
(o(1), ...y (0t1)) S (-hnp: + 2h
>
Pi
lo
11) -pp-11 + 2h
Σ lo (oott)
t=1
Moreover, that all the simplices E)Pe are compact and connected (in fact convex) with
XPI (PP)). ... XP++1 (PP++1)= p
see Definition B.I. Therefore, Lemma B.3 yields the existence of certain ((st1)) D with
fph =Pf -hip + 2h
hp..1 + 2h
E
(5+1)
t=1
t=1
Hence, the claim follows letting
{ -hpp + 2h
(1)
hp.+1
+ 2h
eel
(0+1) E hf m|=
1=1
23

---

B.2 Proof of Proposition 2.1
Proof of Proposition 2.1. Let M Ny- Since not polyharmonic we can pick U with A M 6(2) * O. By continuity we can choose 8 > 0 with Bs(z) S U and A M o(w) * 0 for all E Bz) For all m, 8 No let
Am,t == {w E Ba(z): wirre o win win =0
and assume towards contradiction that
U
Am,e Bz(2).
M..SM
By [3, Corollary 3.35], B5(z) with its usual topology is completely metrizable. By continuity of Ow T wirt à the sets Am,e are closed in (z(2). Hence, using the Baire category theorem [3, Theorems 3.46 and 3,47], there are m, E No with m, l S M, z' E Am, and >> 0 such that
(2))) S Am, S BB(2).
wirt Wi Appendix A.1), this directly implies A M
But thanks A = 4MaM JM
O wirt wirt 2 (see property 6 in = On Be (2') in contradiction to the choice of Bş(z). O
4 1.-
B.3 Proof' of Theorem 3.1
The following section is dedicated to proving Theorem 3.1. We going to show that it is possible to approximate complex polynomials z and Z arbitrarily well on 22 using shallow complex-valued neural networks. To do so, we follow the proof sketch given after the statement of Theorem 3.1, starting with the following lemma.
Lemma B.6. Let Ø + C and 0, b E C, No. such that o B.(()) E O* (Bs(6); For fixed E Ons where we recall that 92 1 1J i[-11, 1)m, we consider the map
00) C, w + (w===++ bb,
which is in Ch since for w E B (0) C C we have
5
I 2| wwl22 ||
2n 8.
V2n
For all multi-indices m, l E N6 with Im + el S k we have
8m Wiiee 0 &win =" (a 0
wi
(wo b)
for all (0).
v/mm
Proof. First we prove the statement
o (ww) = oZ (8 (0 o) (w) 2 ++b) for all E B (0)
(B.4)
by induction over le| < k. The case is trivial. Assuming that (B.4) holds for fixed E No with [6] < k, we want to show
ette wirt cz (w) = Llee, (D o) (w +b)
(B.5)
for all w E B (0), where j E [I,....n} is chosen arbitrarily. To this end, first note
dto, @z (w) 8% Dwino (s
induction
Owire w + z (3 (wiir)) (w + 6)
-t Thint ww +
(Jlel (uingg )) (wi 2 + b)
24

---

Applying the chain rule for Wirtinger derivatives and using that
5 wirt [w + w 2 + b] =0 0
since w + "²²² + b is holomorphic in every variable, we see
0% [w + (omi))) (w" + +]] = (awirol (w" 2 + b) - [ + w 2 + b]
+ (Jultt x) (w 2 2+ b) 5h w w w x + wirt
(Dwitt 6) (w= 2 +++20 b) - (w + -
wirt
ズタ (aleltt o) (w² 2 b).
using the fact that wj + w + b holomorphic and hence
O [w + "" z + = 0 and 0th [w + w x
+ b] = Zj-
Thus, we have proven (B.5) and induction yields (B.4).
It remains to show the full claim. We use induction over [m| and note that the case m = 0 has just been shown. We assume that the claim holds true for fixed E Nj with Im + < A and choose j E {1,..., Thus, we get
g (ww) 0 Ow wirt
Owe &w (ww) Owere
w + zzze (o (hinee))) (w" + +b)
wint
w + (a ml (omm wirt
wiirt wirre) 0) (w² b)
Using the chain rule again, we calculate
0e, [w +
(olmic T wwin))) o) (w 2 b)
(ammlt (iglt o (w- + b) Owire [w + w 2 +
a wire wirt 2
(w²22 + b) 0es w + wt +
g0 (aunle +1 y
Wiire o) (w= z + b) +
(alml 3/itt! o) (w- b) - [w + w² + b]
wire o) (wi² 2 + b). 2 (21ml-11/ wirt
By induction, this proves the claim.
As the last preparation for the proof of Theorem 3.1, we need the following lemma.
Lemma B.7. Let ø C + C and > 0, E C, & E No, such that @ B2(b) E C (Bs(b): C). Ler m, N and e > O. Forp Nºn h > 0 and 2 E On we write
pp.n(=) = (2h)- lpl Σ (-1)lo1-1n (-) (Ø. (h(2r-2)))))))))
0SPSP
(2)o Φb (len (l(22 (1))r-)))](' = - b).
= =(h) 1l
Σ (-1)
0SrSP
where d_ is introduced in Lemma B.6 and yn as in (A.1). Furthermore, let
óp:
Ωn x (0) + C, (z,w) + e (w))..
Then there exists h² O such that
|| [T (p(:0))lxx00nn)))) Se
for all p No with pl < k and p S and h e (0,
25

---

Proof. Fix p E No with pl S k and S m. The map
B /2n+1 (0) x B8/(V2n+1)(0) + C, (z, w) + o (w 2 b)
is in C* since
- 2| S ||0|| ||=|| < 2n + (V2n + 1) =
Therefore, the map
B V2n+1 (0) x B B8/(/2n+1) (0) + C, (z, - (w)
continuous and in particular uniformly continuous on the compact set
On (3)(3n)(0) S B2z++1 B8/(v2n+1((0)
Here, employed 22n + 3n for every N. Hence, there exists hp (0; 3ni such that
(0p(2,E) - -0(,, S
V2
for all & E 9n (h- I-m, m]²"). h E (0, hp) and & E Ωn- Now fix such an E (0, hp) and 2 E Sn Applying Theorem B.5 to both components of (PT $ p.A)) (z) and कp &2 &
4 88 )
separately yields the existence of two real vectors E1, E h m-m,m]?* such that
(PT (p)x(2)); [8P (PT 02 o (P)) (E1)]; (0T o 4 (p)((2)) = [00 (PT o o, o pn) (E2)]
and
Rewriting this yields
Re ( p. (=)) Re (#p(2; fnn (Ei)) and Im (0p, Im (#p(z, Pn (E2)))
Using this property, we deduce
Re (p) - 0p(2, 0)) = Re (2p(2, Pa (E1) - 0p(2, 0)) S (0, en (51) 62(2, 0)1
V2
and analogously for the imaginary part. Since E Q2 and (0, hi) have been chosen arbitrarily we get the claim by choosing
h min (pp: E Nº" with Ip < k and < m)
Using the previous two lemmas and the results from Appendix B.1 and Appendix B.2, we can prove Theorem 3.1.
Proof of Theorem 3.1. Let b U satisfy
g Duin ((b) 0 for all l,, la No with l,, la mn.
Such a point 6 exists according to Proposition 2.1. Let E p' and fix m, l E No with m, S m. For each z Pr using Lemma B.6, we then have
m [ooml Jut (b)
Fm 5t
@w (0)
wirt
Prop A.1
(
win wire 2) (b)
gl
Σ (P"ee" p'4p"=mi m++
bp p 00' x²) (0)
(B.6)
with suitably chosen complex coefficients by..p" E C depending only on p', p", m and f. Here we used that ml |el s mn. Since P C pa is bounded and p Pl, write
p(2)=
Σ
O mz
m. ENN
&s.m
26

---

with @m.el S for some constant e = =(P)) > 0. In combination with (B.6), this easily implies that we can rewrite p as
p(z) = Σ
cp())0=0,00
(B.7)
PERO pS2m
with coefficients cp(p) C satisfying [<p(x) I for some constant d' = c b, P m, n). By
Lemma B.7, we choose h* > O, such that
p 0 (0))
Lg . c'
for all z E S2n and p N with S 2m. Furthermore, we can rewrite each function P
Q P. (z)
Σ
Xa.plllp (hi [h""")]" = + b)
agggan jaj 151 Vi
with suitable coefficients Ap, E C. Since the cardinality of the set
{ar E e layl 2m Vj}
(4m + 1)2", this can be converted to
pp Σ A (0] + b).
For in (B.7), we then define
0(2) Σ col)) 2p. (x)= Σ
Σ colD)\i 6(0 - =
PENSO
f=1
PENS" pm22
ps2m
and note
(0(2) - -(=)]
Σ lop(p) (2) -0pz(()) se.
p52m
Since the coefficients Pj have been chosen independently of the polynomial p. we can rewrite 0 in the desired form.
L
C Postponed proofs for the approximation of Ck -*-functions
C.1 Prerequisites from Fourier Analysis
This section is dedicated to reviewing some notations and results from Fourier Analysis. In the end, quantitative result for the approximation C ([-1, 1]+; TR)-functions using linear combinations of multivariate Chebyshev polynomials is derived; see Theorem C.155
We start by recalling several notations and concepts from Fourier Analysis.
Definition C.1. Let N and k E No- We define
Ckk (R:C)) {f C (R":C): Z'
f(x + 2mp) f(x)
and Car (I=; == C2 CIR For function Ch. (IR;; C) we write
|| || max KENG IK
lok [* 1112200--00 and
1/p
[[f] (2T)) / - 1 [f(2)) dr
for p E [1)
Moreover, set [[]]|]=(([[)))))) |11f
27

---

Definition C.2. For any E N and k E Z", we write
k R C, ex(x) el(k,a)
where (:-) denotes the usual inner product of two vectors. For any C2T (R*;C) k-th Fourier coefficient f to be
()) we define the
f(k)
((z)ex(z)dz.
(2T)* [-x,a]
Definition C.3. For two functions f.9 C2 (R*;C), we define their convolution as
f*g: R ( ()+ = (2mr) |- [()g(x - l)dt.
In the following we define several so-called kernels.
Definition C.4. Let E No be arbitrary.
The m-th one-dimensional Dirichlet-kereel is defined as
772
Dm
Σ
Ch.
f
2. The m-th mie-imensioonl Fejēr-kernel is defined as
Fm 1
Σ D hm0
3. The m-th one-dimensional de-la- Vallée-Poussin-kemmel is defined as
Vn (1 + cm + e-m) F..
4. Let N. We extend the above definitions to dimension by letting
m (#1. I.) = II Dm (xp),
p=1
F (Z1...., -.):= = II Fm (xp).
V I.) = II Vm (zp).
We need the following property of the multivariate extension of the Vallée-Pouusin-kemmae Proposition C.5. Let m, s E N. Then one has [|V=ll S 3%.
Proof. From [34, Exercise 1.3 and Lemma 1.4] it follows || ([-,a]) = 1 and hence using the triangle inequality [Vm & 3. The claim then follows using Tonelli's theorem. Li
The following definition introduces the term of trigonometric polynomial. Definition C.6. For any E N and m E No we call a function of the form
R +CC C,
a (k.z)
KE
<m
with coefficients on C Irigonometric polynomial of coondinatewise degree at most m and denote the space all those functions with Hi Here, we consider the sum over k E 2 with -m < kj S m for all j E (1,..., s). We then write
(f) = min || T (3) Te
(C.1)
for any function f E Can (R):C).
28

---

The following proposition shows that convolving with the Fejèr kemel produces a trigonometric polynomial of degree most 2m - while reproducing trigonometric polynomials of degree m. Furthermore, the norm of the convolution operator is bounded uniformly in m. These properties will be useful for our proof of Theorem C.15.
Proposition C.7. Let 8, E N and No. The map
Um C2a (R²CC + H 2m-1 f + f f
V
well-defined and satisfies
Um (T) T for all T THE
(C.2)
Furthermore, there exists a constant - c(s) > 0 (independent of m), such that
I|em (f) S c. |I (1 vf E C. (R²;C), 1|
S [= vf
C2n (R;C).
(C.3)
In fact, holds c(s) S exp(C 8) with an absolute constant C
Proof. A direct computation shows that f 6 f(k) 6k- This implies that umn is well-defined since V is trigonometric polynomial of coordinatewise degree at most 2m 1.
The operator is bounded on C (R*; C) and C2+ (R=; C) with norm at most c = 3 as follows from Young's inequality [34, Lemma 1.1 (ii), Proposition C.5, and the fact that one has for all Ni with k| < k the identity
8 (f * V (0
V for f Ch (R*; C).
remains to show that vm is the identity on H We first prove that
ex Vm EN
(C.4)
holds for all & E Z with |k| I m. First note that
eb * Vm = Ex * Fm + Ex (em Fm) + ex * (e-m Fm)
We then compute
1
[k|
Ck
Fm
De Ek
Ch
6k
Ekk
m
m
772
m
(=
=b
[k|
Similarly, we get
1 m
m-
Ck # (em
Fm)
(cm Dz)
* Ck
Σ
Chtm Ck
m
m
t=0 -4, h4tm ex
1
k
Ck
8k21
Ek
m
0585m-1 O2mkk
and
1 m-
1 m
Gg # (c-m
Fm)
Σ
(e_m Dz) +
Ch Ck
m
m
t=
t=0 -6 56, Ekk
1
-k
Ek = 6k5-1
Ek.
m
m
0S85m-1
62k+m
Adding up those three identities yields (C.4). To finally prove (C.2), it clearly suffices to show that
Ck V 4k
29

---

for all k E 2 with -m 1 k I m. But for such k, using cu(x) = [Tj= C2 (zz), one obtains
(ek Vin (x)
1
II Cay (tz) Vm (oz tz) dt j=1
(2x)* |-
Fubini
II
(ek, * Vm) (xy)
(C44) II ok (xz) ek ex(x)
5=1
for any x E R as was to be shown.
The following result follows from theorem in [29].
Proposition C.8. Let s, N. Then there exists constant c(s, k)) > O, such that, for E as defined in (C.1),
(f m [I
for all m E N and f E Ch R). In fact, it holds c(s, k) & exp(C ks) k with an absolute constant > O.
Proof. We apply [29, Theorem 6.6] with ne and ps k. which yields the existence of constant Q1 = (s, > 0, such that
E. (f) S1
m
we
f:
m
for all m E N and f C% (R); where we denotes the modulus of continuity respect to Zt, where we have the trivial bound
0* dz
with
1 {.mm
< 11
Hence, we get
ET, < s 2 ||f [+ m
so the claim follows by choosing c:= 2s C1
We refer to Appendix C.2 (see Theorem C.18) for a proof of the claimed bound on the constant c(s, k).
The above proposition bounds the best possible error approximating / by trigonometric polynomials of coordinatewise degree at most but this is in general non-constructive. Our next result shows that a similar bound holds for approximating f by (f).
Theorem C.9. Let s N. Then there exists constant c(s) 0, such that the operator um from Proposition C.7 satisfies
Ilf em (f)(f)))))))) c (f)
for any m E N and f E C2 (R+ C).
In fact, holds c(s) < exp(C s) with an absolute constant C
Proof. For any T E His one has
(C2)
(C3) 3
||/ - (/ll
|ʃ - T|) I. (.= +| (m -/)
Taking the infimum over all T' H.; yields the claim.
By combining Proposition C.8 and Theorem C.9, we immediately get the following bound.
30

---

Corollary C.10. Let s, k E No. Then there exists constant c c(s, k) O. such that
e 1f S m [IIfll=(((()))))1))))))))
for every m N and Cl (RR; In fact, we have c(s,k) exp(C. ks) k* with absolute constan! C O.
Up to now, we have studied the approximation of periodic functions by trigonometric polynomials, but our actual goal is approximate non con-periodic functions by algebraic polynomials. The next lemma establishes connection between the two settings.
Lemma C.11.
Let l E No and E N. For any function f E C* (1=,, C), we define the corresponding periodic function via
f
I +- C, f (x1,...,..)) H.) f(cos (x1),..., cos (I;))
and note f Ch (). The map
C (1-1.1]]; - C.. (R):C), f
a continuous linear operator with respect to the -orms on C² [[-1,1]² C) and Che (R*; C). The operator norm can be bounded from above by k*
The map is well-defined since cos is a smooth function and 27-periodic. The linearity of the operator is obvious, so remains to show its continuity.
Proof.
The goal is to apply the closed graph theorem [21, Theorem 5.12]. By definition of f", and since
cos [- m| + 1-1, 1] is surjective, have the equality |I (= = || (1 (1=,)=,])000))) a.))s))) Let then (fr) be a sequence of functions fa E C* ([",, C) and 9" E Ch (R*; C) such that Ja I in C 11-1, ;;; C) and J - 9" in C2 (R*; C). We then have
||f 9" ([=,))))))))) S II - [[ + ll - 9 [>>0(110,)))))
|[ fx + [[ 9 (--1,==----)))
< |lʃ fxl fxllo*((11.))110) [| - - -g'llo=(->x.))
(n + 20).
follows f" = g" and the closed graph theorem yields the desired continuity.
We refer to Appendix C.2 (see Theorem C.19 and Remark C.20) for proof of the claimed bound on operator norm.
For function f (L-1,,11);; we want express v. (f*) in convenient way, involving product cosines. To this end, we make use of the following identity, which a generalization of the well-known product-to-sum formula for cos.
Lemma C.12. Let E N. Then it holds for any R that
II cos(2z))
Σ
cos((a,2)) 2)).
-11-1.11
Proof.
This is an inductive generalization of the product-to-sum formula
2 cos(x) (z) cos(y) = cos(x - y)) + cos(x + +
(C.5)
for xr y E IR, which can found for instance [1, Eq. 4.3.32). The case holds since cos is an even function. Assume that the claim holds for a fixed s E N and take E R Writing
31

---

x' = =(11 (Ii....,yy) Fz), we derive
II (os(
cos((a, cos(x0+1)
2
j=l
o
Σ
cos( x²)) cos(1s+1)
aEt
(C.)
[cos((a, + Iot1) + cos((a, - rs+1)l
2
(E(-1,1}
Σ aE(-1,1)+41
cos( x)),
20+1
as was to be shown.
The following proposition states that um (f*) can expressed as a linear combination of products of cosines. This representation is useful since these cosines can be interpolated by Chebyshev polynomials which in the end leads to the desired approximation result.
Propusition C.13. Let N and k E No- For any f E C* ([-1,1]*:C) and m N the de-la- Kallée-Poussin operator given as f + Um (f*) with Um as in Proposition C.7 and f + f as in Lemma C.11 has a representation
Um (f*) (EI....).
Σ (F)
II ==1
cos (kzr;)
KENB
k
for continuous linear functionals
V C (1-1, +C f 21/ ox fk).
where ||k||o #(j (1, ..., 8) kj #0) and ax Vi((k) (k). Furthermore, i ((1,,1)); then 1mm (f) E for every k E N6 with k < 2m 1.
Proof. First of all, it is easy to see that um (f*) is even each variable, which follows directly from the fact that fr and va are both even in each variable. Furthermore, if we write
V
Σ
4
KEZ*
1)
with appropriately chosen coefficients of R, we easily see
(f*)
Σ
ak (k)
REZ
-(2m- 1)5k52m-1
Using Euler's identity and the fact that Vm (f*)) is even function, we get the representation
Um (z)
Σ
a an' [""css)ssss
kEZ (2m 1)5k52m-1
for all x E R*. Using 3 denote the componentwise product of two vectors of the same size, i.e.. + y = (x, vi)e, and using the identity (k, a @ x)) = (a, k O x), we see since e... (f*) is even in
32

---

every variable that
Um (S*) (x)
Σ
Um (o)))
2
11)-
1
Σ
Σ
0 f (k)cos( 0 0z))
2
o
KEZ
(2m-1)5k$2me
Σ
OK (k) 1
cos( (O)))
2
KEE*
0E(-1,1)
(8m-1)sk$2m-1
Lemma C.12
Σ
(k) cos (kjr,)
KEZ
(2m 1)5k52m-1
211kilo ak (*( cos (kyz,)
KENG
252m-1
with
[kll == # E (1,....s) k, 00}.
In the last step we again used that cos is function and that
(k) fo T
for all E {-1,1}", which also follows easily since f and V even in every component. Letting V (f) == 2 kllo ug
m I' (k),
we have the desired form. The fact that V is continuous linear functional on Cht 1]= follows directly since + f" is continuous linear functional for every k. If f is real-valued, so (k) for every NG with k < 2m since f is real-valued and even in every component. O
Our main approximation result involves linear combinations of Chebyshev polynomials where the coefficients in this linear combination given V (f). It is therefore important to be able to bound the sum of the absolute values [f)(
Lemma C.14. Let E N. There exists a constant e c(s)
such that the inequality
Σ KEN
(M S ccmm || -I
k32m-1
holds for all N and e C ([-1, where D is as Proposition C.13. In fact, we have c(s) < exp(C s) with an absolute constant C > O.
Proof. Let f C(--1,1]);0 C) and m N. For any multi-index l Nj, follows from Proposition C.13 that
Um (f)) = Σ
V (E)
KENS k52m-1
with
9h R (f1,
II cos (kjæz).
Now, calculation using Fubini's 's theorem and using
(ek; + te_k))
2 (ek, + te_k)
2
j=1
15
ky
33

---

for any number &t E No shows
1 2 00
k L, otherwise
(e(
for k, l No-
Therefore, we have the bound m ( - 2 the Cauchy-Schward and the Parseval inequality, we therefore see
2m (f) for E Ni with |e] - 2m 1. Using
1/2
CS Um (s))()) S 2" (2m))/2.
Um (K) 2
5
Σ
KENg
KENg
KENg
kc2m-1
k52m-1
2m2
Parsoval 1
2 .2//2/22 2/2 Mlum (f (()))12(-)))))
< 20/2 0/2 Ilmm (f)) [=(=,==(--))))
=:0 (8)
Using Proposition C.7, we get a constant (2()) < exp(Co s) such that
M (1) S cs) c2()) 1/2 || ((-,,))))) = d() m/2 |1 (1=0000--))))
KEN
k522-11
as claimed.
For any natural number E No, we denote by Te the ε-th Chebyshev polynomial, satisfying (cos(x)) cos()x); E R.
One can show that T3 is in fact polynomial of degree l. For multi-index k NJ. we define
Txxx) = II Th, (1)), x RER.
We then get the following approximation result about approximating (non mnon-periodic) C* qf-functions by linear combinations of Chebyshev polynomials.
Theorem C.15. Let ki E N. Then there exists constant c= c(ss k) > 0 with the following
property: For any f E C [[=;,]];; the polynomial P defined as
P(x) = Σ
VT) Tx(x),
KEN
k52m-1
with tmt in Proposition C.13, satisfies
|f - PIl - m -I
Here, the maps
C((-1,1];R)-BR F
are continuous and linear functionuls with respect to the I L -nomm Furthermore, there exists constant ē = =ū(s) > O, such that the inequality
Σ
IVP S ē- 2 I| [111)=((-11)))))))))))))))))))))
KENS
k-2m-1
holds for all f e C (1= Moreover, we have c(s, k) 5 exp(C ks) 1 and ē(s) S exp(C 5) with absolute constant C>0 0.
34

---

Proof. We choose the constant Co = co(s, k) according to Corollary C.10. Let f C* (1-1.11%;) be arbitrary. Then we define the corresponding function f E C (R;;R) as above. Let P be defined in the statement of the theorem. Then it follows from the definition of the Chebyshev polynomials Tk. the definition of P. and the formula for Um (f*) from Proposition C.13 that
(*))) = Um (f*) (x)
satisfied, where ps is the corresponding function to defined similarly to f*. Overall, we get the bound
Cor, C.10 Co m
|/ Pl1..= 11 P
((-=,,,))))))
|| I (1
The first claim then follows using the continuity of the map / / I" as proven in Lemma C.111 The second part of the theorem has already been proven in Lemma 14.
C.2 Details on bounding the constant e in Theorem 3.2
In this appendix we provide details on the bound of the constant e that appears in the formulation of Theorem 3.2. Specifically, we perform careful investigation several results from [29] get an upper bound for the constant appearing in Proposition C.8. Moreover, we analyze the operator norm of the operator
C*([-1,1);;0) - (R*;C) f+ with (x) == (cco cos(rx))
appearing in Lemma C.11 and show that it is bounded from above by k.
We start with the analysis of some bounds in [29, Chapter 4.3]. Here, generalization of Jackson kernel is defined for any m, r E N as
(sin(mt/2) 2r sin(t/2)
(t, == Amb
t EER,
where Am, is chosen such that
Lm (t) =
[-m,a]
The first two important bounds are provided in the following proposition.
Proposition C.16. Lei m, E N. Then it holds
f( Jy th (t) dt S exp(C-r) m-
Xmy S exp(C r)- 1-2 and
for any S 2r
2, with an absolute constant C
Proof. Since Tmn,r
0 and since sin(t/2) < 1/2 for [0, T., get sii(mmt/2)
sin(mt/2)
f [0,m]
Am,r
dt 22r
2
dt
1/2
sin(u)
2r
2
sin(u)
2r
22r
du m
m
2r--1
du
10.7m//2)
(2u) m
0..mm/2
u
sin(u) u
2r
2u
2r
2
2r
m 2r-1
du mr--1_
du
2r
[0.0/2]
[0,0/2]
Here, we employed the inequality sin(u) > 2u for E [0, T/2] in the penultimate step. This shows the first part of the claim.
'oo see that this inequality holds, note that sin sin"(u) (u) = sin(u) < 0 for E m/2), so that sin concave on that interval, and hence sin(u) sin((1 2n .
2u
x 2 2n sin T 2n
35

---

For the second part, we again use the estimate sin(u) 2 2 u for E x02 to compute
f
/ th
(sin(m//2) sin(t/2)
2r
dl S Xm. / eh (sin(mt/2)
2r
1 Lmm (1) di Am,
di
|0.57
[0.=]
1/17
{
- T22
th-22
sin(mt/22 /2)2r dt
[.,
2-
21
Am, T
sin(u) du m
[0.rm/2)
< X mm
2r m 2 1-nk
w Aー 2r sin sin(u)
du
10,xm/2)
$ exp((C r)
u 2-2r
sin(u)
du m
(0,00)
with an absolute constant C₁ O. Here, we employed the first part of this proposition. remains to bound the integral. This is done via
/ k-2r sin(u)² du = / 2 sin(n)²r
du + I 2- sin(u) du
u.11
11,00)
(sin(u) $ [ w²
du
u= du S C2
0.11]
(1,00)
with absolute constant C2 > 0. This proves the claim.
The proof in [29] proceeds by defining
K Km,r (t) = L m'
m
+ 1.
Proposition C.16 shows for h 2r that
f t (t) dt exp((..) (m')
Since m 2 we infer
S th Km exp(C (m)) I exp(C ,h m
(C.6)
with an absolute constant C' > 0.
We quantify the constant appearing in [29, Theorem 4.3]. Theorem C.17 (cf. [29, Theorem 4.3)). Let k. m E N and f E C.., (R; R). Let
w(((k) 1/m)
(x+ (k) (x)).
max 2ER.
Then holds
EL, (f) S (exp(C k) k mmmmmm- w w((()) 1/m).
Here, we recall that E (f) denotes the best possible approximation error when approximating f using trigonometric polynomials of degree m; see Equation (C.1).
Proof. We follow the proof of [29, Theorem 4.3]. Take r = k + and define
1+1
J [-),))] Km, (t)
k - (k7 f(x + (t) dt.
[m(x)
1=1
Then is shown in the proof of [29, Theorem 4.3] that Im is trigonometric polynomial of degree at most m and that
lo (mt 1)*+1 (t) dt.
lf(z) Im (x)] 2 wk41 (f,41f///mm)
10.m)
36

---

Here, wk+1 1/m) denotes the modulus of smoothness of f as defined on [29, 47]. The integral can be bounded via
f
(mt 1)h+1 (t) dt
10.m
= -
mm + 1) k+t Km, (t) dt
(ymmn (mt + 11
Km (t)
52me
s 2k+1_
[-n,a] K (t) dt +2--221mmm m
ghtl Km dt
10,0
exp(Ci.r) (k+ (1+1))+1 1 m (k-1) r52k with absolute constants C, C,C₁ C1 > O. Since WK+1 (f, /m) S m= w(s(k) 1/m) follows from [29, Equation 3.6(5)), the claim is shown.
(C6) S 2 + 2 I
k+1 ++
exp(C -
D
Therefore, we can bound the constant appearing in [29, Theorem 4.3] by exp(C k). k remains deal with the approximation of mullivariate periodic functions by multivariate trigonometric polynomials which is contained in [29, Theorem 6.6].
Theorem C.18 (ef. [29, Theorem 6.6]). Let k N and f Chay (R.;R). Let wy denote the modulus of continuity of 0¹ for = ,,..,, 8. Then, with E as introduced in Equation (C.1), it holds
0u,
(f) S exp(C ks). k* m
wy (1/m),
with an absolute constant > 0.
Proof. We follow the proof of [29, Theorem 6.6) with Pj = k and nj m for every index j l....,,.. For j 1....... define the set T, consisting of all functions g E C2 (R:; that are a trigonometric polynomial in of degree at most m for < j; in æ5 for f 2 they should @ºg g for 0 S p S k; the modulus of continuity of 0*g should not duy
have continuous partial derivatives
exceed 2k,,, where
Ky= (j 1)(k+ + 1) S 2ks for and K1 1 2ks.
Then it is shown that if {l,...,s} $) and f, Ty there exists function fz+1 Ty+1 for which Ilf, - fs+1 fl I exp(C1 k)- k²t m 22ks (1/mmm) S exp(C2 kks)) k*t m.mmmm" -k (1y(1m) for absolute constants C₁, C2 > 0. This is an application of Theorem C.17. Hence, defining fi f. we see
Il - S-
S
Σ - 1111ll S exp(C2 ks) k m (15(1/m). L ==1
Therefore, we have shown that the constant appearing in [29, Theorem 6.6] can be bounded from above by exp(C ks) k.k
In the rest of this section, we discuss the operator norm the operator defined in Lemma C.11. In Lemma C.11 the closed graph theorem is used to show that the operator is bounded. However, the closed graph theorem does not provide any bound on the norm of the operator. Therefore, in order to quantify the operator norm, we need to apply different technique, which is Faa di Bruno's 'ss formula. This formula is generalization
the chain rule to higher order derivatives.
Theorem C.19. Let s, k E N. We define the operator
T: ([--,,1];00 Let Ng with |o| < Then, for any f f ([=,,,));; we have
Chay (I-T, C),;),, (TI(E,,.., = [(cos(I)) cos(xx.
(Tf))l (1,)))))))))))))))))) < II
a; a, " [1fflci
j=1
37

---

Proof. The proof is by induction over s. The case = is an application of Faa di Bruno's formula: We can write f fog with ((x) = cos(z). We then take & No with & and some [- T]. The set partition version of Faa di Bruno's 's formula (see for instance [24, 219]) then yields
(1)
S Σ *Ell,
II BET
Here, IT, denotes the set of all partitions of the set (1,-... {). Since all derivatives of g are bounded by in absolute value and ||| I for every partition E TTç get
(I o () 1=-(-x,77)))) S [M1]| -11/f/llll((
The number [[e] is the number of possible partitions of the set {1...., P) and is the so-called 6-th Bell number. It can be bounded from above by e (see [13, Theorem 2.1 This proves the case 1.
We now assume that the claim holds for an arbitrary but fixed E N. Take a E NN with |ac S
We decompose (a', a.+1) with a' Ng- For fixed variable ys+1 E [-1, we define
fy (yi,..., Us) == f(1, ... Ue 1/++1) for (y1..... Uo) E [-1,
We denote ( ... Te+1) (cos(x)), cos(x.+1)) }), Io (21,
.., v.) == (cos(21), ... cos().)) and
0(1++1) = c05(1 ). For every (2), xs+1) E [-T,, m7 s+1 it then holds
(f o (I, = (Jo(e..1) 96) (T1,..., We now differentiate f fo with respect to the multiindex a and get
(apl (fo(s.)1) 9o) (#1, ga.t1
(f o g)] (21, = 00
-liz,..., o 00)(ant)) (Is+1)
where we define
hz x, (M++1) = g0d (fo.. ga) (I)) for (I1, E [- and yo41 [-1,,]]
Using the case 1, we get
(f g)) .I.,...,.+111 = (hz (0) S a.ii l.. (1 for any fixed (#1...,,,,,) x.) E |-,,
It remains to bound || |/ ll C ([-1,1/0) To this end, we fix l E No with l S ast1. We further denote
Fyi Me (No+1) = f'V11 .... Vo: No+1) for (11, ve+1) E 1-1,1 For arbitrary (Z1, ..... Iz)) E x]* and Mot1 {-11, 11 1] we then see
L (U++1) go' (1)) p(f)
9e (Ustt)) ga' [Hy. o (1);
where
H (2i,,.., Mo) = F(t) Hence, we see by induction that
si.... (Not1) for (VI, Ua) E [-1,,
(e)) 2, x, (Vo+1) =|0rd god [H [o] (K1..., Rts)
0j 95 H 1eiilloww'(--11r--0
< j=1
a aj [IfIlllaa II
as was to be shown.
Remark C.20. For multiinex N2 with |a| < k see
DE -ijna < kk a
Hence, the norm of the operator introduced in Lemma C. can be bounded from above by &
38

---

C.3 Proof of Theorem 3.2
For any natural number E No. we denote by Te the 8-th Chebyshev polynomial, satisfying Te (x)s = cos(ez),
x x R.
For multi-inde k E Ng we define
T (xx))
1I Tk (zz), =E(-1,1]"
The proof of Theorem 3.2 relies on the fact that C* C*-functions can by approximated certain rate using linear combinations of the Ti (see Theorem C.15). We also refer to Figure for an illustration of the overall proof strategy of Theorem 3.2.
Proof of Theorem 3.2. Choose M N as the largest integer for which (16M - 7)2n z m, where assume without loss of generality that 92m I m, which can be done by choosing o, = 0 for all j E (1....,m) for m 92n at the cost of possibly enlarging First we note that by the choice of M the inequality
S (16M + 9)2**
holds true. Since 16M + 25M, we get $ 252"
2 equivalently
1/2n
S M.
(C.7)
25
According to Theorem C.15 we choose a constant ci (n, k) with the property that for any function f E C (I-1, 1|2; R) there exists a polynomial
p= E
(f)
0SKS2M-1
of coordinatewise degree at most 2M satisfying
C1
f P S M -lllllllo (.-1"=1)))))))))
Furthermore, according to Theorem C.15, choose constant e2 (n)),, such that the incquality
Σ
DM (J) S e2 M (1 S M || [|
05k52M-1
holds for all f E c ([-1, 1]222 2m R). The final constant is then defined to be
c= c(n, k) == v2 25* (c1 + C2).
Fix k < 2M - 1. Since Tk is polynomial of componentwise degree less or equal to 2M 1 with Pn as in (A.1), we have representation
(T T
Σ E EENN el e. g2M-1
de
Re (z)) Im (2
1=1
with suitably chosen coefficients a e E C. By using the identities Re (zx) (zt + Z)) and also Im (zx) zे4 (ze zz) can rewrite Tr sp into complex polynomial in and i.e.,
(Tr (2 (z)
Σ
e PLEEND
P.P-5M-2
with complex coefficients byr E C. Using Theorem 3.1, we choose Pl, Pm E C and b E C, such that for any polynomial P [T o a (P), am (P) C. such that
k 2M -1 S P there are coefficients 1}
gg P PlIL
M k-n
(C.8)
39

---

where
m
JP == (e (p) 2 + +
Note that here we implicitly use the bound (4 (4M 2) + 1)220 I m. We are now going to show that the chosen constant and the chosen vectors Pr have the desired property.
Let f E O (Sxx C). By splitting f into real and imaginary part, we write f = fi + i- fo with
fi, fz E Ch (St, RR). For the following, fix j E 21 and note that fy o Pn E C (I-1, 1
By choice of C1, there exists a polynomial P with the property
C1 M
|| e pn Pll (11--((-1))))))))
||/s o (ollo=((-111))111))
equivalently
- - Po (2..)
G1
11 (1f
(C.9)
M
where Po po can be written in the form
( 05K52M-1
V (n)) (Tk o (z).
We choose the function Inopa according to (C.8). Thus, writing
E
Va (fr o pn) Inopn"
9j =
05K52M-1
we obtain
Po - 99 (0,.)=((n.13))
<
Σ UCKS2M-1
| (fz o pp))
To "nowi' (a.:))
SM-
S MM
Σ 0SKS2M-1
| of)o
< M
C2 Ilfy (
=
Mk lffillo(
C2
(C.10)
Combining (C.9) and (0), we see
9 +2
C1 C2
Ilf 9 I (R).))
S
[1f (C
I
M
M
In the end, define
= 91 + i 92-
Since the vectors Pt have been chosen fixed, is clear that, after rearranging, 9 has the desired form, i.e., = TT where (2)) (Ø(pEz + b)) Furthermore, one obtains the bound
|l (0 2 |I/i ri 0l 11f2 92l12.- (0,
c1 + VIllli + 11
s
M*
v2. (c1 +2) |
M²
Using (C.7), we see
V2. 25 (01 + 02) |f - ff-9llem(0.. <
[Ifloo=(..))))
k/2n
as desired.
The linearity and continuity of the maps f + of(f) (with respect to the || -Il==-nomm follow easily from the fact that the map f + Va (f) is a continuous linear functional for every multindex
< 2M
40

---

Approximation of partial derivatives
Approximation of polynomials
Approximation
of C* C"-ffuctions
Divided Differences
Wirtinger derivatives w - x
Chebyshev
polynomials
Figure Schematic for the proof of the main result (Theorem 3.2). The first row shows the different steps of the proof and the second row indicates the main tools used.
D Approximation of holomorphically extendable functions
this appendix we provide the proofs for the statements contained in Remark 3.3. The proofs mainly rely on results about sparse polynomial approximation [2].
Definition D.1 (cf. [2, Assumption 2.3]). Let & and v E (1, For every j {l,... 83 let
-
Evg =
2 2 = 1
We then define the (filled-in) Bernstein polyellipse of parameter v
E, := Ev x ... Ev, C
and observe that [-1, C Ey when interpret [-1, 1, 1]a subset of C We further define
(v))
f [-1,,,1] C: 3 open U En and f
holomorphic with [-1.1]
Here, [-1, 1] is again interpreted subset of C Moreover, note that such extension f is, existent, unique, as follows from the identity theorem for holomorphic functions. Hence, the expression
M = [
well-defined.
Definition D.2 (ef. [2. pp. 25, 28 ff.)). Let N. We define probability measure on [-1, 1]" via
du.
dr.
f=1 x3
We define the normalized Chebyshev polynomials for E No as
(x)) == 2 2kllo//
II
cos(k, arccos(x))),
1=1
where | := #1 : k, + 0}. Note that this definition differs slightly from the notion used in Appendices C.I and C.3.
The following lemma is crucial for deriving the approximation rate in Theorem D.5. The proofs be found in [2]. Lemma D.3 (cf. [2, Remark 2.15 and Theorem 3.2]). Let N, k Ng. (1,00)* and
f e (v). Then it holds
1. [ = 2111110/2, where ||Al|o # < S 8: kj #0}:
2. [T,, < v * 2l1k
1o/2 1o/2, |[
It is well-known fact that the Chebyshev polynomials TK form orthonormal basis of
T.2 (1=1,,1;];; The following proposition states that functions from Vz(v) can even be approximated uniformly by linear combinations of the Ty at a certain rate. The proof follows essentially by applying Lemma D.3.
41

---

Proposition D.4. Let E N and u E (1, Let v = min Vj. Then there exists constant
j=
c= (=) > 0 with the following property: For every I E V.(U), defining
Pm
==
Σ
CU,TR)n Te.
KERO
kmm
holds
1f (0-L)))))))) Sc-v" -Ifflv.....
Proof. Let f E V.()). Since the Ta form orthonormal basis of 12, ([-1, 1];; and since is probability measure, so that f E C([ C] S Lp (1-1, 1]"; C), follows that
== Σ (f.TR Tk
KENS
with unconditional convergence L2 For E [-1,1]] note that
Σ Kr.T)) K
[T(x))
Σ kl, [Tk]l==(1-1a)0000 2/1l/l))))
Σ vーt
KENg
KENg
Here, we employed Lemma D.3 the last inequality. From v > follows that
Σ (f.TT) T
KEN
converges pointwise (even uniformly) and, since all the involved functions are continuous, this pointwise limit then has coincide with the Lig -limit f. Hence, it holds
|| - Pm (1-1100) S Σ KKS.TR) (ifii.ll1177llee(ee- 1T
KENS
kpmm
s 2'1lflll, Σv
KeNg [klgm
where we again used Lemma D.3. To complete the proof compute
2
Σv
Σ
Σ k=m+1
KENg
j=1
KENg
j=1
1st5s [g/
k=
1k/gm
kymm
))
Vj 1m+1)
Σ VE k
jml
15P5
km
II
Σ Vi
(m-1)
15PSS
k=0
==1
Vi
s.. -s
Vi
15t5#
and define := II
To formulate the result for the approximation of holomorphically extendable functions using CVNNs we need to transfer the definition (z(v)) to the complex setting. For E (1, and with yn. as in Equation (A.1), we hence write
(v( = { : On - C: So pn 1-,11 (Vn((1)}
42

---

For f (v) we define
llflw.. == Ilf Qnllve.(v)
Thus, (v) consists all complex-valuee functions defined on 2, that can holomorphically extended onto some polyellipse in C where S2, S C" is interpreted subset of 22 and then as a subset of C The final approximation result then reads as follows.
Theorem D.5. Let and (1,00) Ser
min Vj- 15
Then there exists a constant c(n, v) O with the following property: For every function : C C that smooth and won-pelyharmonic on some open set + U C and for every E NN there exists a first layer & F with the property that for every f E W,(v) there exist coefficients =o{ E C such that
1lf - oo-oT4llr.ee ((l..) Sc sc.vmm mm--mm///mm/1 -Ilfll....)
Moreover, the map f + (ff) is a continuous linear functional with respect to the L -orm.
Proof. Choose M E N as the largest integer satisfying (8M + 1)20 s m, where we assume without loss of generality that 92n I m. This be done by choosing of possibly enlarging c. Note that the maximality M implies (8MM + 9)3n > m. By using 8M < 17M, this gives us
for g2n at the cost
M
m 1/2m).
(D.I)
Choose the constant 61 = ei (2n, v) according to Proposition D.4.
Fix k E No"h with k < M. Since Ti is polynomial of componentwise degree at most M, we have a representation
Th o 9 (z) (z)=
Σ
de II Re Im (z+)
et E'EEEN el P.
with suitably chosen coefficients oh
E C. By using the identities Re (z+) (2+ + Zτ) and also
Im (2x) # (=t Ze), can rewrite Tk 4p into complex polynomial in and Σ, i.e.,
T T (2)
Σ by 22 z
e! EEPEND
el 22.252M
with complex coefficients b C. Using Theorem 3.1, we choose Pi. Pm C and
b E C, such that for any polynomial E T k M) c P there exist coefficients 01 (PP)...., (P) E C, such that
lgpp PIL
Σ vik Σv+) KENS"
v (M$+1
(D.2)
where
9P : Σ o (P) (pf +).
Note that here we implicitly use the bound (4 (2M + 1)an < m. We are now going to show that
the first layer & E Fe n.m defined using the and b (i.e., 4(z) = (ø(p) 2 b)) has the desired property.
To this end, take an arbitrary function f E (w.v). Proposition D.4 tells us that
|| -f-PA PM on 110
1 (Q,:C) fl PM Parl S. (M+1) .If")..ffooo infoopnllvs.tee (D.3)
43

---

where
PM Pm Σ
(fo Tk) (Th pTt))
KENO K
We then define the approximating network
g == Σ
(oo Th) Thopp"
KENS"
KSM
From the definition of the functions Moop follows directly that g shallow CVNN with first
layer & E F% n.m Furthermore, it holds
PM p, gll ((),:)) 1
Σ
1(f yn fn, Th) 1 px
-Koop'
kENB
kg.M
(D.2). D.3
1
2n. 1.IIoopallvaa
Σn v
Σ v v
(M+1)
KERa
KEND
KS
2 2 -1.fllw,, (M+1),
Combining this estimate with Equation (D.3) and applying the triangle inequality gives us If - الو ( S (c1 + 2") (M+1) [f
Hence, the claim follows taking e = 01 + 2" and using (D.I).
The continuity of the linear map + aff) with respect to the L follows directly from the fact that f ~ {f Pn, r2,, is trivially continuous with respect to the T -norm and hence also continuous with respect to the _ -nom since (22n is a probability measure.
E Postponed proofs for the optimality results in the case of continuous weight selection
In this section we provide the proofs for the optimality results derived if a continuous weight selection assumed. Specifically, we prove Theorems 4.1 and 5.1. The proofs of both results rely on very general result about the approximation in normed spaces by subsets that are parametrizable with m parameters [19]. We decided to include detailed proof for this approximation result this paper since the nature of the continuity assumption in [19] is not completely clear.
Proposition E. ([19, Theorem 3.1]). Let (X, || lIx) be a normed space, Ø o K C X a subset and V S X a linear, not necessarily closed subspace of X containing K. Let m N, let a K + R
be map which is continuous with respect to some norm -|v on V and M Rmm + X some arbitrary map. Let
bm (K)x == sup sup Le 2 0: Up(Xm+1) CK).
(E.1)
Xm+1
where the first supremum is taken over all (m + 1) dimmensionl linear subspaces Xm+1 of X and
U Uo(Xm+1) = ty Xm+1 llvllx e).
Further, we set bm (K)) == 0 if the supremum in (E.1) is not well-defined as quantity in (0]. Then holds
sup | M(T(x)) x bm (K)x
=ek
Proof. The claim is trivial if bm (K)x = 0. Thus, assume bm (K)x > 0. Let 0 < bm (K)x be any number such that there exists an (m+ (m+1))-dmme diimesndiannsoonll subspace X X of X with U (X(Xm+1) C K. It follows U (X)+)) S V. hence X S V, || V|v defines norm on X Thus, the
44

---

restriction of a to p is a continuous mapping to R" with respect to || llv. Since all norms are equivalent on the dineessainniio space Xm+1. the Borsuk- Ulam-Theorem [18, Corollary 4.2]
yields the existence of point zo E aUg (X((+))) with a(ro) = a( a(-Io). We then see
20 = 2||xollx N -000- - M (xx)))l + || + M(a
||00 M(((x)))llx
3o M(a(-x)))ll
and hence at least one of the two summands the right has to be larger than equal to e-
E.1 Proof of Theorem 4.1
Using Proposition E. can deduce our lower bound in the context of C* spsssccss. The proof is in fact almost identical to what is done in [19, Theorem 4.2]. However, we decided to include a detailed proof this paper, since [19] considers Sobolev functions and not C* -unccionss.
Theorem E.2. Let s, k N. Then there exists constant c(s, k)) O with the following property: For any N and any map ā 1R,,, + R that is continuous with respect to some norm C* 1];; R) and any (possibly discontinuous) map M I -> C[]-1,1",; IR), we have
f (a 2 c- -k/s
sup [EC*([-1,))3))
I Mct(--aa)))
Proof. The idea is to apply Proposition E.1 to : == $ 1}. set K == {f = ()) [
V (1(11,1)); and the
Assume in the beginning that m = n with an integer n > 1. Pick ó E (R*( with Φ on 1-34,,3/4/ and 0 outside of [-1, 1I Fix co (s. k) > 0 with
1 M IllIc=((11,))=.))) - co-
Let QI,... Qm be the partition (disjoint up null-sets) of 11 1]a into closed cubes of sidelength 2/n. For every j E {l,.... ...: m] we write Q2- X la - nnn, dz + 1/n] with an appropriately chosen vector a (a)
(1)
(f)
(j) (1)) E 1] and let
(x) == 6(n(x - )))) for x E R'
By choice of o, the maps o5 are supported on proper subset of Qj for every j E and an inductive argument shows
8 (x)))) = lkl (o.))()))(() (b))) for every E Ni and x e R
and hence in particular
1 S nk co.
(E.2)
Let Xm := span (01, .... )m) and S Ui(Xm) lf E Xm 1 S 13. Then we can write S in the form S = Ex= Cjoy with real numbers c1, Cm E R. Suppose there exists j E (1,...m) with lcz- 1. Then we have
|S|L==(-1)) 18(a 1c,- > 1,
since the functions o, have disjoint support and o, (2( = 1. This is contradiction to S (Xm)) and we can thus infer that max |cy| S 1. Furthermore, we see again because the functions o; have disjoint support that 3
(E.2
n = co m k/s | (1-1,))))))) S max lc,l ||at by -0 & n co S co
for every No with [k| and hence
|| [[ S cp m/.
45

---

Thus, letting o: -0' m -k- yields Up(Xm) _ K, so we see by Proposition E.1 that
k/s
sup / M Mm-i (an)(
e - c k/j
fek
with 0 = =o for every map a: X + Rm-1 which is continuous with respect to some norm on V
and any map Mm Ru- X. Using the inequality m S 2(m 1) (note m 1) we get
sup || Mm- (a SeK
2 4 m k/a 61 (2(m - 1)) k/a 2 02 (m - 1) k/-a
k/s, with c ci k/s Hence, the claim has been shown for all numbers of the form n²" with an integer n > 1.
In the end, let N be arbitrary and pick n N with n" S m < (n + 1)". For given maps a: V + Rm and M R + X with continuous with respect to some norm on V, let
à - f (a(f). and
1 R( + (I. M(a),
where I E Rm E -(+ Then we get
sup / - ((a(a)))l==(----))))) fek
sup fek
I| M ((n+))1-111 (ā L=
2 02
((n + 1)2 - 11) -k/s
1)--// 2 02 (2"n*) 2 c3 m k/-
with C3 = 2-k Here we used the bound (n + 1)2 1 (2n)*. This proves the full claim.
Using this theorem, we can now prove Theorem 4.1.
Proof of Theorem 4.1. Let (9x; + C be any map that is continuous with respect to some norm I/v on C² (2n; C). and let M C + C(2n: C) be arbitrary. With fou Pm defined as in Equation (A.1), let
à: (*11-1, 1,= + R2m 8+ (a (((o%%"'la))
Clearly, is continuous C ([- 1, 1) R)) with respect to the norm lli (1-1 1j²;; defined as
11flli = || p. 22 llv for (1-1,11,)
Let
M: 2am C([-1, 1|2;; R), M(x) Rc(M((pm())) o pn p-11...
Then it holds
sup (B.:C)) [1llotta,no)
Ilf - M(a(F))l
sup (B.i))
|f Ro(M(a(f))Mll>0....
[1
|| | Re M (a (a(Foo (oo ()) (1.0)))))))
sup
llflloky S1 (R.I(-I))))
| i Re (M (pm (pm' (7 ( (fovā'l (o))))))))))) pn 1= (0-1.111=_
sup (EC*((-1,1"=33) (1
| T-(M(a(F)) (00(-11170:8)) 2 ē. (2m) -2/(nn,
sup (1..(011,1P.33)) [ifll $1
with a constant ē o(n,k) k:) provided by Theorem E.2. Hence, the claim follows by choosing c(n, k) = 2 222((2m) c.
46

---

As corollary. we formulate a special case of Theorem 4.1 for the case of shallow complex valued neural networks.
Corollary E.3. Let n, k E N. Then there exists constant c(ni, k))
with the following
property: For any m E N, & E C(C; C) and any map
n: C (St, C) (C") x CD Cm 9 (m (g), 72(0). (2(0))11))))
which is continuous with respect (1,,)) S and
norm (D C), there exists f Ch (Ans ()) satisfying
V ((IILL 2c. c.mmm//(2n)
where (J) E C(In; C) is given by
m
((f)(z)== ==)()))=>(m) ( (ns(f)) & (Im(f)3 + (n2(f))))
Proof. Using Theorem 4.1, deduce that there exists f E ( () satisfying (l S
and
|f 1 (f) d' (m(n 2)) k/(2n)
for a constant d' (n, k) > 0. Hence, the claim follows by letting c == d' (n + k/2nn)
E.2
Proof of Theorem 5.1
We can use Proposition E.1 not only to show that the rate of convergence established in this paper optimal (which is done in Appendix E.1) ) but also to show that the problem of approximating be parametrized with finitely many parameters is
C functions using set of functions that intractable in the sense that it suffers from the curse of dimensionality, provided that the map which assigns each C* fu-netnt the parameters of the approximating function is continuous. This is the subject of this section.
In [35] certain space of polynomials was used to show the intractability in the case of linear approximation methods. We are also going to use this class of polynomials, but combine with Proposition E.1 to infer intractability in the case of continuous approximation methods. We start with a lemma discussing an important property of this space of polynomials. This property is stated as part of proof in [35], but complete proof is provided.
Lemma E.4. Let E N and consider function f C (1-1, which is given via
f(x) = Σ axah
(E.3)
kE{0,1)*
with coefficients dn E for every & E 10, Then il holds
11 -11111=-(-1111))333
for every k N.
Proof. The proof is by induction over s. We start with the case = and note that we can write f(x) + 6 with a, b R in that case. Switching to -f if necessary,
assume > 0. Clearly, [ < |al + [b]. Conversely, b 2 then [f(1) = la + bl = |al + [b] otherwise < 0 then [f(-1) = b-
ba-b| = |al + [6]. Thus, [| = |a] + [b]. For
the derivatives, we have || [ 1001==((--0) (1-1.1)) = and (1-11]))) 0 for A 2 2. This proves the claim in the case
We now assume that the claim holds for some arbitrary but fixed s E N. We further let a E No and fix a point (I1,..., 2o+1) 1|+1, We decompose (a', as+1) with a' No. Let
f: |-,,1| - RR Mot1 + g(a',0 (())))) f(),,
2s. Mo+1)
and note
0 ((z Fastil
47

---

Note that f is dffine-lineat with respect to each variable (with all other variables hold fixed). Hence, f is affine function and we can thus apply the case = 1 to and get
f(aa 11.0111) $ ([
Putting this together, we infer
1 xx+1)| S (1-11111-)))))
sup
(a(a'00 [(T) ( Las Is, Ws+1)l
(E.4)
M++16|-1.11
We now fix an arbitrary point Vo+1 E [-1,1] and consider
f: 1-, + I, (y11..., Uo) + f(y1, yos Mo+1).
Then holds
g(a',0) f(r1, .... 1o+1) ) = 0a f(111.... Tz).
Applying the induction hypothesis to I (which is easily be of the form (E.3)) we get
10dh f(1,, x..1 S 21-1))))))))) S 11
(E.S)
Combining (E.4) and (E.5) yields
10 ((11......411)) S [[
Since No+1 was arbitrary, get the claim by noting that
[If(l)=(((1,)) 2 [1
holds trivially for every l E N.
Using the above lemma, we can now deduce that the approximation of smooth functions using continuous approximation methods is intractable in terms of the input dimension.
Proof Theorem 5.1. We apply Proposition E.1 to X = C(--1,1*; RR, V C and the set K = (f Co0,+ |If ((-.111)))) S 1) and m := 2 - 1. The space
X Xm+1== [1,11
Σ a O R
kE(0.1)
consisting of all functions considered in the previous Lemma E.4 is an (m + 1)-dimensional subspace of ([=-1,1];; For every f E Xm+1 with [0/ll==((--111ppp < 1, Lemma E.4 tells us
S 1. Hence, U1 (1(Xm+1) S K and Proposition E.1 then yields the claim.
Remark E.5. The statement of Theorem 5.1 also holds the functions satisfy ā C + Rm and R) with < 2 - 1. This can be seen by defining
M. : R +
à 00,, + 21 f (, 0)
and
M =--1 I(-1,,);;RR, (a, M(a)
with R and b E R 11--
The following Corollary E.6 transfers Theorem 5.1 to the complex-valus setting.
Corollary E.6. Let N. For any function C (Pn; C) we write
[f := sup [
KEN
and let C denote the space consisting of all functions for which this expression is finite. Let
C C00,+m + -1 be continuous with respect some norm on C Coo.* and moreover, let
M : C 22 + ((In; be an arbitrary map. Then it holds
sup
|l M((()) (m) (0, 2 1.
SECE (1
48

---

Proof. The transfer to the complex-valued setting works in the same manner as the proof of
Theorem 4.1 (see Appendix E.I). We write m := 22n-- 1 and note 2m 2 Σ 2 1. We define à C + 2 and M R + C([- 1, 1|2n, IR) in the same way as the proof of Theorem 4.1. Using again the same technique in the proof of Theorem 4.1, we get
sup S (1
|/ - ((a()))
sup Fn
- | (0(1-11)))))) 21 1,
applying Theorem 5.1 in the last inequality, using 2m S 22n 1.
We conclude this appendix by adding a note on the constant appearing in our main approximation bound.
Corollary E.7. Let n E N with n 2 2 and a and let & E C(C;C). Let ē = ö(n, ox) > 0 such that for every m N there exists mapping
n C
C (C*) x CT x Cm g (m(())) T3(
that is continuous with respect to any norm on C C and such that
|lf - (ffI S (2.m) - [lfloc((...)))
for every f E CC Here, v(f) C(lnn C) is given by
m
(f)(=)) = Σ (na(f)), & (In(f) = +valf)),
Then it necessarily holds ē < 16 16-2-" -
Proof. We first assume n 2 We take m
2
and note that then m(n + 2) S 22n-1 1
n+2
Therefore, Corollary E.6 applies and we infer that for each e E (0, 1), there exists f = Sc E C Co0.e.m with ( (An:C) and such that
8 S || ((][VV())l== S (6-m)-a |I S (e-m)
This then necessarily implies č m I or equivalently ε $ 1/m. It therefore suffices to derive a lower bound for Firstly, we note
n+2 > 2 2n (n + 3), 22n-1 = 2n-3, 3, 2m = 2n-3 (1 1)=+2
where we applied Bernuuli's ' inequality. Because of 4 3, this yields
22n-1 - 12 2n 33 2n- 2n (n + 2).
Hence, we get
(1 (-- 23- 2- 2n
2 -1 - 1 > 2n-3
m 2
--
n +
16"
Here, we used n 2 4 in the last inequality. An explicit computation shows that the same bounds also holds in the cases = 2 and 3. This proves the claim.
F Postponed proofs for the optimality results in the case of unrestricted weight selection
F.1 Approximation using Ridge Functions
In this section we prove for s N22 that every function in (R can be uniformly approximated with an error of the order m -k/((=-1) using a linear combination m so-called ridge functions, In fact, we only consider ridge polynomials, meaning functions of the form
R + RR I I IHplaT p(aFxx)
49

---

for a fixed vector E R and polynomial p R + R. Note that this result has already been obtained in a slightly different form in [30, Theorem 1]; namely, is shown there that the rate of approximation m k/(x-1) can be achieved by functions of the form Σj= fa(az x) with aj R= and f, E loc (R*). We will need the fact that the f, can actually be chosen as polynomials and that the vectors 01. ...... a. can be chosen independently from the particular function f. This is shown in the proof of [30], but not stated explicitly. For this reason, and in order to clarify the proof itself and decided to present the proof in this appendix.
make the paper more self-contained,
Lemma F.1. Let m, E N. Then we denote by
P :=
R
I
a&d
E R
KENO Rl/s
the set of real polynomials of degree at most m. The subset of homogeneous polynomials of degree m is defined
H = 1² - B, 34
Σ
oga
as E
R
KEN
MA =m
Then there exists constant c == c(s) > 0 satisfying
dim(H I c c.m m==1
Vm E N.
Proof. is immediate that the
No. k m)
forms basis of H hence
dim H = # (k E No:
k = m]
This quantity clearly equals the number of possibilities for drawing m times from a set with elements with replacement. Hence,
( (5+ - )
dim dim(H*)
see for instance [12, Identity 143]. A further estimation shows
$ + m - (s+m-
II +
m
< (1 + m)=1 -1 2--1 22--1.m=-
mm²-
f=1
Hence, the claim follows with c(8)= = 2--1
combination of results from [36] together with the fact that possible to approximate C*k. functions using polynomials of degree most with enror of the order as shown in Theorem C.15, yields the desired result.
with 2 and > Then there exists a constant e == c(s, k) > with the following property: For every E N there exist a1,..., Om RR {0) with ||a,lı = such that for every function f E (² 1,";; TR) there exist polynomials Pi. Pm Pl satisfying
Theorem F.2. Let 8,
f(x)
Σ 1=1
Pý (a x))
Sccm k/(s-1), (100=-))111flc(((1.... [1
([1)))))
50

---

Proof. We first pick the constant C1 c1 (s) according to Lemma F.1. Then we define the constant C2 C2(s) = (2s)* (s) and let M N be the largest integer satisfying
2 M - m.
Here, we assume without loss of generality that m 2 C2, which can be justified by choosing Pj - 0 for every j (1...,m) m) if < C22 at the of possibly enlarging Note that the choice of M
implies 02 (2M)*-1 2 (M + 1)8-1 > m, and thus
M
2 C
1/(0-1)) m 1/(=-1) C3 m 1/--11
(F.I)
with c3 = ca() = 1/2. C2
1/(a-1)
Using [36, Proposition 5.9] and Lemma F.1 can pick a11,-.,, Ro (0) satisfying
H 12 span {o {x+ (a} x) jE (1, m.....m].
(F22
where we used that
C1 (s(2M 1)) S (2s)* " M 02 M S m.
Here we can assume ||a ||2 = r for every j E {I...., m since multiplying each aj with positive constant does not change the span in (F.2). From [36, Corollary 5.12) we infer that
P. 22MM-1) = span fo + (a z)" (L...., m). 0 S r S -
(F.3
Let f (*{[[_,,]] R.. Then, according to Theorem C.15, there exists polynomial P: R of coordinatewise degree at most 2M satisfying
R
f Pll Pll,.-((-1..)
S C4 M II. (I((L11))))))))))
where 6 = (s, k) O. Note that by construction holds Pe ps 4(2M-1y Using (F.3) deduce existence of polynomials pI...,, Pm l& such that
P(x) = p)(fff)) for all x NER.
j=1
Combining the previously shown bounds, we get
f(x) ((()) Σ Polaffo x)
m
1lf(2)) P(z)l Sc M [[f())--11)))))))
==1
(-1.())))))
- k/(=-1) - (110))((1)))))))))
as desired, Here, we defined c(s, k) Ci Cg"
F.2 Proof of Theorem 4.2
Using Theorem F.2, we can prove the following statement for complex-valued C* fu-ncciio,s,, which will play an important role in the proof of Theorem 4.2.
Proposition F.3. Let k E N. Then there exists constant c(n, > 0 with the following property: For any m N there exist complex vectors by...., bm E C with [lbyl] 1/v2n for j L,..,,m m and with the property that for any function f C (Ons C) there exist functions 91. Im E C(2 C) such that
m
[(z)
Σ 93 (1
Sc-m Sc-m-kk(2a1) 1110aaaa)))1/llloare.ee.
1 (1055)
Note that the vectors bı, bm can be chosen independently from the considered funcetion S. whereas I..... Im do depend f.
51

---

Proof. Theorem F.2 yields the existence of a constant c1 (1,nk) > 0 with the property that for any m N there exist real vectors ..., 4m R with ||a 2|2 = 1/ 2m such that for any function
f C* [-11112- R) there exist functions ÿ1, ... 9m E C([-1, 1]: R) satisfying
((x)) ((a)-Eor (a) 5=1
S m k/(2n11), (1flcc(---1)(()))))2))))))
([-1111)
We then define the vectors bi, bm C componentwise via
(by) (aj)e
(ay)nte>
E (1,-.,,,, J (1.-.,, m.).
First we see |ااولا| = ||ay]l 1/v2n. We first consider real-valued functions, i.e., / E C* (Rn; Let pn be defined as in (A.1). By the choice of the constant ej we can find continuous functions
G1... .. Dm E ([-11, IR) such that
m Σ 9j (afx)
S 01 m 1k/2nn11) ||f o (
==1
(-(1-11))"))
We then define 9j C(Q;; R) by (z) 0s (Re(z)) for any {1,..., m). For 2n we then have
Re Σ (by)e =1 ))
(b)) " 2)
95
(z)e + ii ii (hntt)))))
Re
Σ
(az)) - (-))))t)))) (s)
1=1
Új Σ
(az)e Pn (2)) + (as) (nn))eeeella (3)ntt)
وj (aa)) .p (2)
(F:4)
Therefore.
m
m
f(z) Σ 9j (bf 2)
(fo - Σ 9j (0 pn(x))
L (0..3)
L (0-11_11,
(F44)
(fo
Σ Øj (a xx) 1=1
1 (1-11_1)))
S cI m
h/(2n-1) 1lf pml c (())))))))))
By the above, for f E Ok (1);;C) we can pick functions g .-.., satisfying
R gn If .... gim E C (Q:;R)
m
Re(f(2))
9
Re
(bF²)
$ C. mm-m-ka -k/2nn1)), |e (f (.lllco((())))))))))))>>)
(R
[m([(z)) Σ
Im (b, 2)
S C1 - m -m-mmm-//00 k/(2m-)) |l (f (.
g
1=1
(R)
Defining 9j = -R +i. 9
Im yields
m f(x) Σ gi 2)
Sa 22. m k/(2n11), 1), (
j=1
(0,
completing the proof.
52

---

The special activation function that yields the improved approximation rate of m Rk/(2n11) (see Theorem 4.2) constructed the following lemma.
Lemma FA. Let {ue]e=) be enumeration of the of complex polynomials in and z with coefficients in Q + iQ. Then there exists a function &o E O (C; () with the following properties:
1. For every N and Qn one has
Φ(z +() =ue(z)
2. o is non-polyharmonic
Proof. Let th C (C; R) with 0 S Φ S 1 and
=
(upp(1) C 2
where G: = f= E C [Re (z) Im (z)l
We then define
δ f 3
Σ uel 36) c 32),
where f(=) = Re(=), Note that á is smooth since it is locally finite sum of smooth functions. Furthermore, á is non-polyharmonic the interior of f2, since the calculation in the proof of Proposition A.2 shows for z in the interior of Q and p + R, 1 e that
Iam d (=)
Owirt Swar (z)
1
p (m+ (Re(z)) > 0
2m++
for arbitrary m, No. Finally, property (1) follows directly by construction of d because (Ā + 36) (Ω2 + 38") =
for + C.
Using the properties of the special activation function constructed in Lemma F.4 and applying the approximation result from Proposition F.3 we can now prove Theorem 4.2.
Proof of Theorem 4.2. Let be the activation function constructed in Lemma F.4. We choose the constant e according to Proposition F.3. Let m E N and f E C (9x;; We can without loss of generality assume that # O. Again, according Proposition F.3, choose Pl,..g Pmn C with ||2p,|| 1/ /2 and 91, ... Im E C (Ω; C) with the property
f(2) - 22--90 91 (p)
c m k/(2n [I
(.)()))))
Recall from Lemma F.4 that {ut 1 is an enumeration of the set of complex polynomials in and ž Hence, using the complex version of the 4.51I), we can pick f..... lm E N such that
Weierstraß-Thhooee (see for instance [21, Theorem
|9, ue, 1l (1,00 Sm 1n-1-//(2-11 1) (l
(F.5)
53

---

for every j E {1...., m). Since ò + 36) = dy on S2 for each & E N, and since p3 U2 for j E (1,..., m) and E Pn, we estimate
f(z) Σ Φ ( +3,)
j=1
6 (Bn:C)
m
m
<
f(z) Σ
9j (0)'2)
[g (0]=) - (0} 2 +3e,) ~ (a.)0)
1=1
1x (Bxx()
j=1
Sc. m f/(2-1) |1 (B.
+
|99 (2) - ur (z) (=)lle
==1
[R5]
c. m k/(2n-11 IIflll** + m
-m k/(2n 1) 111f//mm))11ffllo0aa.0.. (I
(c 1) m h/(mm11), [
E33 Proof of Theorem 4.3
As preparation for the proof of Theorem 4.3, we first prove similar result in the real-valued setting. We remark that the proof idea is inspired by the proof of [46, Theorem 4].
Theorem F.. Let n, k E N and
1
Φ: D:R-H R+R d(x) T
be the sigmoid function. Then there exists a constant e= = c(n, k) > with the following property:
If the numbers& E E (0, }) and m E N are such that for every function f E C ([-1,1]"; R) with
Ilf Ilf II (-111)))))) S there exist coefficients pr. Pm RR", m. Un E R and 01, ... O.n E R
satisfying
f(x)
Σ 1=1
oj & 1 (0] x + 71)
Se,
L ([-1111))
then necessarily
g// 1/f (1/e)
Proof. We first pick function & E t (R";;) with the property that (0(0) -1 and v/(x) = for
every x E I with ||>||2 > 4. We then choose
C1 = ci (n, k) = (1611)+((1111)))))
Now, let E (0, ) and m E N be arbitrary with the property stated in the formulation of the theorem.
If > g
1 ge, then m 2 c. (m/e/e) trivially holds (as long as c(n,k) > 0 is sufficiently small).
g-n/t
Hence, we can assume that < 4 ge. Now, let be the smallest integer with 2 2, for which
N SE.
2
Note that this implies
2
-
6*
=
2++1
2k+1
Ci
and hence N 2 3, whence N - 2. Therefore, by minimality of N, and since N N 1
because of N 2 2, it follows that
2 (N - < 2k+1
C1
2h N N
G N
(F.6)
54

---

Now, for every a E (-N, NP" pick Za {0, 1) arbitrary and let ya == 2 Define the function
[(x)= Σ Ya w (Nx - a), E EER.
aEI-NN...MY)
Clearly, f E pairwise disjoint, we see for any multi-index No with k) that
Furthermore, since the supports of the functions 6 E 8" are
| fl| (111))))))))))) S N/kl max Uy
| 1111-
N max yal
1,
so we conclude that |If ( S Additionally, for any fixed 3 {-N, m.. N we see
ya.
by choice of vb. See also Figure 5 for an illustration of the function f- By assumption, choose suitable coefficients Pl....P R", m/.... Bm E R and furthermore Olymn Fm E IR such that
|| gl1 ([-1,1]=;8) Se
for
Σ jj j=1
(p} +n))-
9
Letting
m Σ
P
9 g(0/N)
oj
Φ
17j
(F.7)
N
j=1
we see for every a E {-N, N3 that
(E6)
g(a) = 9 a
2 Ya - = NN - - (21/2)
if = if ia 0.
S yo +e (F6)
(c1/2) N-k
Therefore, we get (g > (c1/2)N
(a) za for any (-N, NYa. Since the choice of 20
has been arbitrary, it follows that the set
{ 1 (g (c/22N "11-))1(11)0) |(-N....Ny I of form (F.7)
H ==
shatters the whole set (-N, ..., N)". Therefore, we conclude that VC(H) 2 (2N 1)" 2 N
On the other hand, [4, Theorem 8.11] shows that VC(H) I 2m(n + 2) 1602 N) S c3 m In(N)
with a suitably chosen constant 63 (n).. Here we used that N that In(N) 2 In(3) >
Combining those two inequalities yields
N
m 2
C3 In(N))
Using that N 2 c4 -1/k with c4 == ca k) = (Λ,tT) 1/K
1/k
and N S cs 8 g- 1/k
with the definition
= cs (n, k) = (4) 1/k
we see that
E n/k
n/k
2 C6
In (cs 1/1]]
In (1/e)
with cg co(n2, k) chosen appropriately.
55

---

Figure 5: Illustration of the function f considered in the proof of Theorem F.5.
As corollary, we get a similar result for complex-valued neural networks. Corollary F.6. Let n, le E N and
Φ: C+C, o(z) = 1te Re(=)*
Then there exists a constant c = c(n, k) > with the following property: If E (0, 1)) and m E N are such that for every function f E C (Sn; C) with ( S 1 there exist coefficients
P1,... Pm. E C" m..... Tm E C and 01, ... Fm E C satisfying
((=)
(03 2 + n1))
Se
j=1
L (Qn:C)
then necessarily
2n/k
2
(1/E)
Proof. We choose the constant = c(2n, k) according to the previous Theorem F.5 and let ph as in (A.1). Then, let & (0, () and m with the properties assumed the statement of the corollary. we then take an arbitrary function f E C ([-1, 1m=: R) with IIf the existence of Pl, Pm E "",....... 7mm E and 0 II, Fn E C, such that
S 1, we deduce
m
[(x) Re
Σ j=1
(0) (n(()) +m))
(fo
Σ oj o (p] + ni))
SE.
((,
In the next step, we show that
m aa & (0f (a(() + m;)
R 2 3 x
Re
is real-valued shallow neural network with neurons in the hidden layer and the real sigmoid function as activation function. Then the claim follows using Theorem F.5.
For every j E (1....mm) we pick matrix P3 E [R2xx2 with the property that one has
63 Φ. (2) pp (pf 2) for every C This is possible, since this is equivalent to
T - p (x))
56

---

for all v E R²" where the right-hand side is an R-llnnear map R² + RR.. Denoting the first column of Pj by Pj. we get
P3 (z) Re (0] .2) for all E C"
1 Writing y for the classical real-valued sigmoid function (i.e. 7(x) = i+e- ) we deduce for arbitrary R that
Re
Σ oj o (0} (x(22) + nz))
Re
Σ oj 7 (Re (o} (x(()) + +nn))
j=1
E0 oj y (0=" x Re (155))
= Re
m
Σ Re (a,) 7 (0z (e
Re Re
where in the last step we used that y is real-valued. As noted above, this completes the proof.
Now, we can finally prove Theorem 4.3.
Proof of Theorem 4.3. Let = 2n and choose 02 = c2(a) = c2 k) > 0 such that the incquality k In(x) S C2 2/2 holds for all 2 1. Furthermore, let C1 ca (n, k) 0 in Corollary F.6. By choosing c(n, k) > 0 sufficiently small, satisfies
ensure that Em c. (m (((m))=k/(2n))
Ci
+ a 2
lm(1/Em) 2 a Im(1/em) for all m E N22.
In
4
By further shrinking c(n, k) if necessary, we may assume
(2 (2(2)) (2(m) 1
and hence (m (n(m)))*/(2n)) even further, we can arrange that d² < 01 C3- Now, assume towards a contradiction that for every E C² (In C) with ( I 1 there are coefficients Pl. ....... pm C T1, On C and M) m Mm E C such that
for all m N22. Finally, setting c3 := a and shrinking
f(2) - Σ
o 0 (0, +b)
< <e- <e-(m- -nnmm)()) -k((2))
(0,,C.)
Applying Corollary F.6, we then get
E -2//
m c In (1/E)
with ε == c- (m In m) m4/22))))))))))) (0, 1)) and c cı (n, k) > 0. Recall from the beginning of the
proof that a == 2n/k and that In(x) & 2/2 for every x 2 1. We observe
a/2
(1/e) 02
which implies
[mm)
2 In
C1
+ In
In(1/e) 2 in(1/s) c3 In((/s)..
02
Overall we then get
m In(m)
m In(m)
m (1(//) Ci c
2 ci 0g
Ci C3 c m.
In(1/))
In(m)
Since we chose such that c" < we get the desired contradiction.
57


Reviews:
[{"review_id": "jH5wHnZkgb", "reviewer": "Reviewer_GqHo", "summary": "The paper studies the expressive power of complex-valued neural networks. It is shown that depth 2 networks with non-polyharmonic (the complex equivalent of non-polynomial) activations can approximate any continuous function on a compact domain to arbitrary accuracy which decays polynomially with the width and exponentially with the smoothness of the target function, but nevertheless suffers from the curse of dimensionality. This upper bound is also shown to be optimal in general, and that furthermore, there are more tailored examples where one can slightly improve the approximation rate.\n\n\nPost-rebuttal:\n\nI still find the technical contribution of the paper rather fair (as my original score indicates). My main concern with the paper is that its impact feels somewhat limited as it provides a guarantee which suffers from the curse of dimensionality. While I understand that this cannot be evaded in general, obtaining a result which is tight in the worst case where the worst case is intractable is a clear limitation. While I appreciate the fact that there are other older results in the literature which are highly cited and obtain such results for the real setting, this paper's merits should be considered compared to what is already known, and from this perspective, obtaining results in the complex setting that are analogous to the real setting is of interest but not groundbreaking. I have therefore decided to keep my original score.", "questions": "Questions:\n\n- \"complex-valued networks behave significantly different from real-valued networks\": I don't see how this is `significantly different'. The second property does indicate a difference, but the first characteristic is analogous (non-polynomial and non-polyhedral activations).\n\n- There's no clear motivation for the very technical choice of the $C^k$-norm in the paper. Can you provide a more intuitive explanation for it and why it is chosen? In particular, why is this choice not stylized for obtaining the main result?\n\n- \"It is crucial that the size of the networks considered in Theorem 3.1 is independent of the approximation quality $\\varepsilon$\": Why is this important?\n\n- What is the quantity $c(n,k)$ which appears in many of the theorem? The bounds in the paper are interesting since they allow us to study the dependence of the accuracy attained as a function of, say, $n$ for some fixed $k$; but the dependence of $c(n,k)$ on $n$ isn't clear. I tried to better understand it by looking at the proofs in the appendix but it's not made explicit there as well. $c(n,k)$ could, potentially, have magnitude $m^{k/(2n)}$ which would render the upper bound vacuous. Why is this not the case? Is this the same quantity in both the upper bound in Theorem 3.2 and the lower bound in Theorem 4.3? If not, it could make the either bound very loose despite appearing to provide a tight result.\n\n\nComments:\n\n- Abstract: \"the real-valued case is supported by a firm mathematical foundation\" -- I wouldn't say our mathematical understanding of deep learning is firm.\n\n- The abstract doesn't explicitly state what are the functions the main result applies to.\n\n- Line 27: The universal approximation theorem dates back to 1989. See \"Approximation by Superpositions of a Sigmoidal Function\" by G. Cybenko\n\n- \"CVNNs have the same excellent approximation properties as real-valued networks.\": Why is this conclusion reached? The results in the paper hold for a very broad class of smooth function and therefore suffer from the curse of dimensionality in the worst case.", "limitations": "- I think that the lack of clarity in the theorem statements regarding $c(n,k)$ is problematic, yet this is not discussed in the paper. I urge the authors to clarify this and discuss this more clearly.\n\n- The limitations of the provided results which suffer from the curse of dimensionality should be clearly discussed.", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The problem feels overall well-motivated, and CVNNs seem like an interesting model to study.\n\n- The analogies and differences between real and complex neural networks highlighted by the results in this paper are interesting.", "weaknesses": "- On a technical perspective, it seems like the main technical contributions here are to adapt existing technique to the CVNN setting. Most results seem to take existing proofs and just apply them to the complex setting, which doesn't feel novel enough.\n\n- The exact dependence on the rate of approximation is unclear. There's a `constant' $c(n,k)$ which hides some dependence on the input dimension and smoothness parameters, which could be potentially huge (see questions below).\n\n- The separation established in Section 4 by Theorem 4.2 and Theorem 4.3 is not particularly strong, and is only significant in cases where the input dimension $n$ is very small.\n\n- I didn't find the main approximation result in Theorem 3.2 very surprising. This is an analogous result for something which is already known for real-valued networks, so obtaining this result for complex-valued functions feels incremental. In particular, it would be of greater interest, in my opinion, to study cases where complex-valued networks attain an \\emph{efficient} approximation in the input dimension $n$, since these have stronger practical implications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive feedback. We agree that CVNNs are an interesting model to study.\n\n# Weaknesses\n\n> Most results seem to take existing proofs and just apply them to the complex setting.\n\nWe do not think that this is a fair assessment of our work. There are several novel results and ideas in our paper. In particular noteworthy is Prop. 2.1 which connects the notion of non-polyharmonicity with the non-vanishing of Wirtinger derivatives at a single point. This is non-trivial and central to our proof. Also the other proofs are not simply a matter of \"replacing $\\Bbb{R}$ by $\\Bbb{C}$\" but rather require substantial changes to the proofs, mostly because real-valued activation functions are 1D objects, whereas complex activation functions are multi-dimensional (cf. the differences between ODEs and PDEs).\n\n> I didn't find the main approximation result in Theorem 3.2 very surprising. [...]\n\nWe don't think this result is \"boring\": It is highly non-trivial (and maybe surprising) that the correct complex generalization of \"non-polynomial\" (for our problem) is \"non-polyharmonic\". [33] shows that this is the correct generalization for *universality* of **shallow** NNs, but already in the case of NNs with two hidden layers this stops being true. Therefore, it is a priori not clear that the notion of \"non-polyharmonic activation function\" is the correct one for deriving *quantitative* approximation bounds such as studied in our paper.\n> it would be of greater interest [...] to study cases where CVNNs attain an *efficient* approximation in the input dimension $n$\n\nIn this paper, we study $C^k$-functions, for which the curse of dimensionality is inevitable. We agree that studying other function classes (such as generalizations of the Barron class to CVNNs) is interesting, and plan to do this in the future.\n> The exact dependence on the rate of approximation is unclear. [...]\n\nSee below.\n> The separation established in Section 4 by Theorems 4.2 and 4.3 is not particularly strong [...]\n\nThe purpose of these two theorems is to show that it is impossible to derive upper and lower bounds with a *matching* approximation rate for all smooth activation functions and a possibly discontinuous weight assignment. We just care that the two rates are **distinct**, not that there is a strong separation.\n\n# Questions\n\n> \"CVNNs behave significantly different from RVNNs\": I don't see how this is `significantly different'. [...]\n\nThe difference that we emphasize here is that, to obtain universality, there are more admissible activation functions for *deep* NNs than for *shallow* NNs in the complex case, which is not the case for RVNNs.\n\n> There's no clear motivation for the very technical choice of the $C^k$-norm in the paper.\n\nThe $C^k$-space and the norm that we use are standard and widely used in the literature. Maybe you refer to the definition below l.116, where we wrote \"$\\partial^{\\mathbf{k}}$\" instead of  \"$\\partial^{\\mathbf{k}} f$\". We will fix this in the final version.\n\n> \"It is crucial that the size of the NNs considered in Theorem 3.1 is independent of the approximation quality \": Why is this important?\n\nIt is important to obtain the final approximation result regarding the equation in l.184-185. Moreover, it is noteworthy that for polynomials the network size is independent of the error, which is not the case for our other results. \n\n> Abstract: [...] I wouldn't say our mathematical understanding of deep learning is firm.\n\nWe agree this formulation should be changed. We propose \"is supported by a growing mathematical foundation\".\n\n> The abstract doesn't explicitly state what functions the main result applies to.\n\nThanks for noting that this is not entirely clear. In the final version we will make this more explicit. \n\n> Line 27: The universal approximation theorem dates back to 1989. [...]\n\nWe agree that the work by Cybenko should be cited and we will do so in the final version. We cited [19] since it is the first work to consider *arbitrary, non-polynomial* activations. \n\n> \"CVNNs have the same excellent approximation properties as RVNNs.\": Why is this conclusion reached? The results in the paper [...]  suffer from the curse of dimensionality [...]\n\nWe mean \"excellent\" in the sense that CVNNs attain the same approximation rate as RVNNs for $C^k$-functions. This is the *optimal* rate that can be achieved with $m$ (continuously selected) parameters (Theorem 4.1). You are correct in noting that even though the results are optimal they suffer from the curse of dimensionality (COD). We plan to study alternative function classes for which CVNNs do not suffer from the COD in future work.\n\n> What is the quantity $c(n,k)$ which appears in many of the theorem? [...] $c(n,k)$ could, potentially, have magnitude $m^{k/(2n)}$ which would render the upper bound vacuous. [...] Is this the same quantity in both Theorem 3.2 and Theorem 4.3? [...]\n\nThe constant $c(n,k)$ only depends on $n$ and $k$ and is **independent** of the number of neurons $m$. Therefore, it cannot grow like $m^{k/(2n)}$. Roughly, $n$ and $k$ are taken as fixed and we ask how quickly the approximation error decays (asymptotically) as $m\\to\\infty$.\n\nWe don't compute $c(n,k)$ explicitly but note that the dependence is indeed exponential in $n$, even for large $k$ (e.g., $k = n$). However, this is not a shortcoming of our proof but a fact of life, as follows from \"Approximation of infinitely differentiable multivariate functions is intractable\" by Novak and Woźniakowski, Journal of Complexity (2009).\n\nThe constants that appear in theorems 3.2 and 4.3 are not the same, but this is standard in the literature for similar results. Precisely studying the constant $c(n,k)$ is extremely difficult and has only been done in a few very special cases (see the paper by Novak et al. above).\n\n> The limitations of the provided results which suffer from the curse of dimensionality should be clearly discussed.\n\nThe final version will discuss this in greater detail."}, {"review_id": "Juzq56b3at", "reviewer": "Reviewer_yApE", "summary": "This paper studies the approximation power of complex-valued neural networks (CVNNs). They derive that the approximation error is with the order $m^{-k/2n}$, where m is the number of neurons, k is the smoothness of the target function, and n is the input dimension of the neural network. They also show that this approximation error is optimal under some mild assumptions.", "questions": "Please see the weaknesses.", "limitations": "No.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper derives the approximation bounds of CVNNs for any continuous activation functions.\n2. Furthermore, they show that the approximation bounds they obtain are optimal with a natural continuity assumption.\n3. For several specific activation functions, the authors derive the upper bounds without the assumption of the continuity of weight selection.", "weaknesses": "1. For general activation functions, the authors need to assume the continuity of weight selection to derive the optimal approximation rates. It will be more convincing if they can show results for general activation functions without the assumption of the continuity of weight selection.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive feedback for our paper.\n\nYour main criticism of our paper is that\n\n> It will be more convincing if they can show results for general activation functions without the assumption of the continuity of weight selection.\n\nWe agree that it would be interesting to establish lower bounds also in the case of discontinuous weight selection, as we also mention in the Limitations section of our paper. However, in full generality this is a highly non-trivial problem a full resolution of which is outside the scope of this paper. In particular we would like to mention the following points:\n\n1. The continuity assumption is natural: In practice neural networks are trained by variants of stochastic gradient descent. Here the training algorithm does not have direct access to the (unknown) ground-truth function $f$, but can access $f$ only through the training samples $(x_i, y_i)$, where $y_i = f(x_i)$ or $y_i = f(x_i) + \\mathrm{noise}$. One can show that each gradient update depends continuously on the training samples and therefore also on the ground-truth function $f$. Strictly speaking, this continuity is only guaranteed to hold if the activation function is continuously differentiable. Therefore, for any continuously differentiable activation function the continuity assumption is satisfied in practice.\n \n2. For *deep* neural networks (with more than two hidden layers) with general smooth activation function it is *not* possible to derive any non-trivial lower bounds without assuming continuity, since there exists an activation function with the property that neural networks of constant size using this activation function can approximate any continuous function to *arbitrary* precision (see [22, Theorem 4]). Note that [22] considers the real-valued setting but the results can be transferred to complex-valued networks with a suitable choice of the activation function. Hence, a lower bound in the case of unrestricted weight selection can, if at all, only be derived in the case of shallow networks.  \n\n3. In the real-valued case, fully general lower bounds for the approximation capabilities of shallow neural networks have been derived by appealing to the results from [15] regarding the approximation properties of so-called ridge functions. Here, a ridge function is of the form $\\sum_{j=1}^m \\phi_j (\\langle a_j, x\\rangle)$ with $a_j \\in \\mathbb{R}^d$ and each $\\phi_j: \\mathbb{R} \\to \\mathbb{R}$. We are interested in generalizing these results to higher-dimensional ridge functions, i.e., functions of the form $\\sum_{j=1}^m \\phi_j (A_j x)$, where each $\\phi_j : \\mathbb{R}^s \\to \\mathbb{R}$ and $A_j \\in \\mathbb{R}^{s \\times d}$. This would imply lower bounds for shallow complex-valued neural networks. However, such a generalization seems to be highly non-trivial and is outside the scope of our paper.  \n\n4. We already discuss the issue of possibly discontinuous weight selection to some depth in Theorems 4.2 and 4.3. Theorem 4.2 shows that there is a smooth activation function for which one can even achieve the rate $\\mathcal{O}(m^{-k/(2n-1)})$ which shows that without the continuity assumption and for this special activation function the upper bound of $\\mathcal{O}(m^{-k/(2n)})$ is not sharp. In contrast, Theorem 4.3 shows that for some special activation function the upper bound of $\\mathcal{O}(m^{-k/(2n)})$ is actually sharp (up to logarithmic factors), even in the case of possibly discontinuous weight selection.\n\n     In combination, these theorems show that in the case of unrestricted weight selection one cannot derive a sharp approximation rate holding simultaneously for all smooth activation functions. Specifically, Theorem 4.2 shows that such a bound would have to be smaller than $m^{-k/(2n-1)}$ while Theorem 4.3 shows that it would have to be greater than $(m \\cdot \\ln (m))^{-k/(2n)}$. This means that for the case of discontinuous weight assignment one has to perform an individual analysis for different activation functions. \n\n"}, {"review_id": "qDWVcT3i9L", "reviewer": "Reviewer_ve6Y", "summary": "The paper studies approximation error bounds for complex-valued neural networks based. The authors relied on several techniques from the work by Mhaskar (1996) and proved several theorems in the paper. I will summarize two important results here.\n1. Given a function from $C^k$, an optimal error bound is proved under some conditions on the activation function and the hypothesis of continuous weight selection. Furthermore, the complex-valued neural network achieving this bound has a universal first layer.\n2. When the hypothesis of continuous weight selection is dropped, the authors proved that there exists an activation function allowing the complex-valued neural network to achieve a better bound. No optimality is claimed under this case. On the other hand, there is an activation function such that the bound cannot be improved up to logarithmic factors.", "questions": "Line 28: Would it be more precise if referencing the work by Cybenko in 1989?\n\nLine 140: What is your definition of a smooth function? Please make it precise.\n\nFrom Theorem 3.1, the complexity of an approximating complex-value network is established for a polynomial. Would it be possible to use the Stone-Weierstrass theorem to establish an approximation bound? This seems to be a natural step to apply.", "limitations": "The authors have sufficiently addressed the limitations of the paper in Section 5. In my view, the greatest limitation of this work is the use of continuous weight selection for guaranteeing the optimality of the error bound. It would be more convincing if the authors can give some insights into this in Section 5.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The novelty of this paper is clear. The paper provides error bounds for complex-valued neural networks using more general activation functions and shows that the optimal bound can be achieved under the hypothesis of continuous weight selection. The results in this paper generalize the results in the previous work [9]. The problem is well-motivated, and the theorems proved are sound. Overall, the paper is well-written, and I enjoy reading the paper.", "weaknesses": "The hypothesis of continuous weight selection is not a practical assumption. The optimal choice of the network weights is discontinuous in general (see the reference below). It would be better if the authors could make this clear in the paper.\n\nKainen, Paul C., Věra Kůrková, and Andrew Vogt. \"Approximation by neural networks is not continuous.\" Neurocomputing 29, no. 1-3 (1999): 47-56.\n\nUnder this assumption, the error bound can be proved to be optimal. However, no optimal results are provided if this assumption is dropped. Regarding this, it would be more convincing for the paper if the authors could provide insights into difficulties that arose in proving the statements and potential workarounds.\n\nThe results provided are similar to [9] so it would be more interesting if the authors could describe what difficulties they have overcome to prove these results. Given the high similarity of the results, I would expect more discussions in the related work section or in the descriptions of the proof sketch.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are glad that you enjoyed reading our paper!\nIn the following we address each of the points that you raised.\n\n# Point 1\n> The hypothesis of continuous weight selection is not a practical assumption. The optimal choice of the network weights is discontinuous in general (see the reference below). It would be better if the authors could make this clear in the paper.\n\nThanks for suggesting that \"Approximation by neural networks is not continuous\" might be a relevant reference for our paper. We will include it in the final version and point out that selecting the **best approximating NN** of a given size for a given function is discontinuous.\n\nIn addition:\n\n1. The continuity assumption is satisfied in many practical scenarios. In practice NNs are trained by variants of SGD. Here the training algorithm does not have direct access to the (unknown) ground-truth function $f$, but can access $f$ only through the training samples $(x_i,y_i)$, where $y_i =f(x_i)$ or $y_i =f(x_i)+\\mathrm{noise}$. One can show that each gradient update depends continuously on the training samples and therefore also on the ground-truth function $f$. Strictly speaking, this continuity is only guaranteed to hold if the activation function is continuously differentiable. Therefore, for any continuously differentiable activation function the continuity assumption is satisfied in practice.\n\n2. The paper mentioned above shows that selecting **the best** approximating NN for each function $f$ is a discontinuous operation. This, however, is not the setting that we consider. We show that for $\\varepsilon=c\\cdot m^{-k/(2n)}$ each function in the $C^k$-unit ball can be approximated using a shallow CVNN with $m$ neurons up to error $\\varepsilon$, but it could be that several functions in the $C^k$ unit ball can in fact be approximated much better. Thus, the mentioned paper does not fully apply to the setting we consider.\n\n # Point 2\n> (...) it would be more convincing for the paper if the authors could provide insights into difficulties that arose in proving the statements and potential workarounds.\n\nThe following are the main difficulties:\n\n1. Our Theorems 4.2 and 4.3 show that, if one drops the continuity assumption, there is no single approximation rate that is the optimal rate jointly for all smooth activation functions. This means that one would need to perform a separate analysis for different (classes of) activation functions. \n\n2. For deep NNs (with more than two hidden layers) with general smooth activation function it is not possible to derive any non-trivial lower bounds without assuming continuity, since there exists an activation function with the property that NNs of constant size using this activation function can approximate any continuous function to arbitrary precision (see [22, Theorem 4]). Note that [22] considers real-valued NNs, but the results can be transferred to CVNNs with a suitable choice of the activation function. Hence, a lower bound in the case of unrestricted weight selection can, if at all, only be derived for shallow NNs.\n\n3. In the real-valued case, fully general lower bounds for the approximation capabilities of shallow NNs have been derived by using results from [15] regarding the approximation properties of so-called ridge functions, i.e., functions of the form $\\sum_{j=1}^m \\phi_j(\\langle a_j, x\\rangle)$ with $a_j \\in \\Bbb{R}^d$ and $\\phi_j: \\Bbb{R} \\to \\Bbb{R}$. We are interested in generalizing these results to higher-dimensional ridge functions of the form $\\sum_{j=1}^m \\phi_j (A_j x)$, where each $\\phi_j : \\Bbb{R}^s \\to \\Bbb{R}$ and $A_j \\in \\Bbb{R}^{s \\times d}$. This would imply lower bounds for shallow CVNNs. However, such a generalization seems to be highly non-trivial and is outside the scope of our paper.\n\nWe will include a brief discussion of these points in the final manuscript. \n\n# Point 3\n> The results provided are similar to [9] so it would be more interesting if the authors could describe what difficulties they have overcome to prove these results. Given the high similarity of the results, I would expect more discussions in the related work section or in the descriptions of the proof sketch.\n\n1. As outlined in Section 1.1.2 our results differ *significantly* from [9]: we consider general activation functions, we show that the rate proved in [9] for deep NNs can in fact already be achieved using shallow NNs, and can be improved by a log factor. \n\n2. Our proof techniques differ significantly from those in [9]. While in [9] the target function is approximated by many polynomials of low degree, combined with a partition of unity, we approximate the target function by a single polynomial of high degree. For approximating the polynomial using a NN, [9] uses a construction specific to ReLU which was pioneered by Yarotsky [34]. In contrast, we use Wirtinger derivatives and divided differences which can be done for quite general activation functions. \n\nWe will include a discussion of the proof techniques in the final manuscript.\n\n# Questions\n\n> Line 28: Would it be more precise if referencing the work by Cybenko in 1989?\n\nWe will cite the work by Cybenko in the final version. The reason why we cite [19] is that it considers very general activation functions. \n\n> Line 140: What is your definition of a smooth function? Please make it precise.\n\nThanks for noting that the definition is missing. By \"smooth\" we mean $C^\\infty$-functions in the sense of real variables. We will include that in the final version of the paper. \n\n> From Theorem 3.1, the complexity of an approximating CVNN is established for a polynomial. Would it be possible to use the Stone-Weierstrass theorem to establish an approximation bound? This seems to be a natural step to apply.\n\nUsing the Stone-Weierstrass theorem, one could establish qualitative results. However, this theorem is not quantitative. Theorem J.15 can be seen as a quantitative version of the Stone-Weierstrass Theorem for approximating $C^k$-functions."}, {"review_id": "5JOl8lX1yS", "reviewer": "Reviewer_6LvE", "summary": "The paper studies approximation rates of shallow complex-valued neural networks (CVNN) with general non-polyharmonic activation functions. First, the paper establishes upper bounds for the error of approximation of polynomial and general smooth functions by CVNNs. Then, various aspects of the optimality of these bounds are discussed. First, it is shown that these bounds are tight assuming continuous weight selection. Next, a special activation function is presented for which the bound can be improved. Finally, it is shown that for a standard sigmoid-type activation function the rate bound is tight.", "questions": "Why specifically is the particular computational structure used in CVNNs (a layer of holomorphic linear operations + a layer of pointwise non-holomorphic non-linear operations + another layer of holomorphic linear operations) important? ", "limitations": "See above", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "**Contribution.** The paper seems to be the first paper that establishes optimal approximation rates for CVNNs with general non-polyharmonic activation functions. Previous results were either limited to specific activations or only established the universal approximation property, without convergence rates. Moreover, the paper comprehensively analyzes the optimality of its convergence rates. It proves their tightness assuming a continuous weight selection and shows that faster rates can be achieved if this assumption is dropped and a specially designed activation is used. It should be noted, however, that the CVNN model considered in the paper does not seem to be very important, and that most results of the paper are analogs of existing results for usual real-valued neural networks - see Weaknesses below.\n\n**Quality and clarity.** The paper is very well written. The theorems are clearly stated, sketches of key ideas of the proofs are provided in the main text. Proof details are provided in a large appendix and also seem to be carefully written, though I did not study all of them closely.", "weaknesses": "**Questionable significance of the CVNN model.** The usual real-valued neural networks are important both mathematically and practically. They represent simple and natural non-linear models whose significance is well-established. In contrast, CVNNs do not seem to be significant from either perspective. Mathematically, they mix holomorphic linear operations with generic non-linear operations. This combination does not seem to have interesting analytic properties (except for the original observation by Voigtlaender that the condition of non-polynomiality for RVNN gets replaced by non-polyharmonicity for CVNN) or obvious practical or computational meaning. The paper does not explain why CVNNs are important, instead referring to a small number of papers from 2016-2018 where a similar structure was applied. \n\n**Limited conceptual novelty.** The paper generally adapts existing methods and results from the real-valued to the complex-valued setting - admittedly with many extra new twists. The established convergence rate is the same as for the respective real network with doubled real dimension.\n\n**High technicality for a conference.** This is quite a technical paper with 40 pages of proofs in the appendix. It is unlikely that any NeurIPS reviewer properly checks all these, so the paper might be more suitable for a journal with a more comprehensive review process. However, this is only a minor point, since the paper makes a good effort to present key ideas and sketches of proofs already in the main text.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive feedback and in particular for the positive comments on the quality and clarity of the paper. \n\nIn the following, we individually answer your comments:\n\n> The usual real-valued neural networks are important both mathematically and practically. They represent simple and natural non-linear models whose significance is well-established. In contrast, CVNNs do not seem to be significant from either perspective. Mathematically, they mix holomorphic linear operations with generic non-linear operations. This combination does not seem to have interesting analytic properties (except for the original observation by Voigtlaender that the condition of non-polynomiality for RVNN gets replaced by non-polyharmonicity for CVNN) or obvious practical or computational meaning. The paper does not explain why CVNNs are important, instead referring to a small number of papers from 2016-2018 where a similar structure was applied.\n\n> Why specifically is the particular computational structure used in CVNNs (a layer of holomorphic linear operations + a layer of pointwise non-holomorphic non-linear operations + another layer of holomorphic linear operations) important?\n\nWe agree that compared to RVNNs CVNNs are less used. One reason for this is certainly the limited availability of wide-spread libraries for implementing and training CVNNs. Nevertheless, there has been sufficient interest in CVNNs such that the effort of implementing such a library has been invested (https://github.com/NEGU93/cvnn). We would also like to mention the following more recent papers that find CVNNs to be advantageous for tasks that naturally involve complex numbers. We will include them in the final version of our paper: \n\n- https://doi.org/10.1109/ICASSP39728.2021.9413814\n- https://doi.org/10.1007/s11265-022-01793-0\n- https://doi.org/10.1002/mrm.28733\n- https://doi.org/10.1002/nbm.4312\n\n\nThe intuitive reasons for why CVNNs perform better than RVNNs in some application areas are the following: In applications where complex-valued inputs naturally occur, it is natural to use complex arithmetic in applied machine learning models as well. In particular, the use of phase-preserving complex activation functions such as the complex cardioid or the modReLU should be mentioned. Note that phase preservation cannot be achieved when non-trivial real activation functions are applied separately to real and imaginary parts of complex-valued neurons. Likewise, the holomorphic nature of the linearities (i.e., the linearities are linear over $\\Bbb{C}$) is crucial for a faithful handling of the phase. \n\n\nAs you have already pointed out, CVNNs exhibit quite interesting mathematical properties, in particular regarding the interplay of the properties of the activation function and the expressivity of the resulting CVNNs. The universal approximation theorem states that shallow CVNNs are universal if and only if the activation function is non-polyharmonic, but it is a priori not clear at all that the property of not being polyharmonic is enough to guarantee *optimal quantitative* approximation rates. Our paper shows that this is the case.\n\n> The paper generally adapts existing methods and results from the real-valued to the complex-valued setting - admittedly with many extra new twists. The established convergence rate is the same as for the respective real network with doubled real dimension.\n\nOur proof indeed required \"many extra new twists\" compared to the proof of the real-valued case.\nIndeed, there are several novel results and ideas in our paper. In particular noteworthy is Prop. 2.1 which connects the notion of non-polyharmonicity with the non-vanishing of Wirtinger derivatives at a single point. This is non-trivial and central to our proof. Also the other proofs are not simply a matter of \"replacing $\\Bbb{R}$ by $\\Bbb{C}$\" but rather require substantial changes to the proofs, mostly because real-valued activation functions are 1D objects, whereas complex activation functions are multi-dimensional (cf. the differences between ODEs and PDEs).\n\nThe established convergence rate is indeed the same as for RVNNs with doubled real dimension. Note, however, that we prove this bound to be optimal (assuming a continuous weight selection) so that a better bound is not to be expected anyways. \n\n> High technicality for a conference. This is quite a technical paper with 40 pages of proofs in the appendix. It is unlikely that any NeurIPS reviewer properly checks all these, so the paper might be more suitable for a journal with a more comprehensive review process. However, this is only a minor point, since the paper makes a good effort to present key ideas and sketches of proofs already in the main text.\n\nIncluding such a long paper at NeurIPS is not completely unusual. See for instance https://papers.nips.cc/paper_files/paper/2021/hash/c82836ed448c41094025b4a872c5341e-Abstract.html\nWe are happy that you appreciate our efforts to present the key ideas and sketches of proofs in the main text. "}]

Author rebuttal:

Meta-review: The targeted problem --- function approximation of complex valued neural networks --- possesses its own value and is largely overlooked in literature, given fruitful results about universal approximation using real valued neural networks. The obtained approximation rates and implications are clearly discussed, and the technical proofs are sound.

The paper has some weaknesses, and the major one is a lack of new analytical framework. As pointed out, the proof is largely adapted from existing works with modifications to the complex setting. Yet these twists allowing an extension of approximation theory to complex valued neural networks are still fair contributions.

There is an issue about the fixed input dimension and the approximation rate suffers from the curse of dimensionality. In the context of universal approximation, the input dimension is usually taken as fixed, and the obtained rate suffers from the curse of dimensionality without further assumptions. That being said, the approximation rate obtained in the paper is in par with older ones, confirming the technical soundness. However, it should be noted (Reviewer GqHo, 6LvE) that translating results from the real to the complex setting is of interest but not groundbreaking. Therefore, the recommendation is acceptance (poster).
Decision: Accept (poster)