Complex-valued Neurons Can Learn More but Slower than Real-valued Neurons via Gradient Descent
Authors: Jin-Hui Wu
Shao-Qun Zhang
Yuan Jiang
Zhi-Hua Zhou
Venue: NeurIPS 2023 poster (2023)
Keywords: Complex-valued Neural Networks; Learning Neurons; Real-valued Neural Networks; Convergence Rate

Abstract: Complex-valued neural networks potentially possess better representations and performance than real-valued counterparts when dealing with some complicated tasks such as acoustic analysis, radar image classification, etc. Despite empirical successes, it remains unknown theoretically when and to what extent complex-valued neural networks outperform real-valued ones. We take one step in this direction by comparing the learnability of real-valued neurons and complex-valued neurons via gradient descent. We show that a complex-valued neuron can efficiently learn functions expressed by any one real-valued neuron and any one complex-valued neuron with convergence rate $O(t^{-3})$ and $O(t^{-1})$ where $t$ is the iteration index of gradient descent, respectively, whereas a two-layer real-valued neural network with finite width cannot learn a single non-degenerate complex-valued neuron. We prove that a complex-valued neuron learns a real-valued neuron with rate $\Omega (t^{-3})$, exponentially slower than the $O(\mathrm{e}^{- c t})$ rate of learning one real-valued neuron using a real-valued neuron with a constant $c$. We further verify and extend these results via simulation experiments in more general settings.

Complex-valued Neurons Can Learn More but Slower than Real-valued Neurons via Gradient Descent
Jin-Hui Wu, Shao-Qun Zhang, Yuan Jiang, Zhi-Hua Zhou
National Key Laboratory for Novel Software Technology. Nanjing University, China School of Artificial Intelligence, Nanjing University, China ,wujh, zhangsq, jiangy, zhouzh) (aanuzha@aaaa aladd...... .nju. edu
Abstract
Complex-valued neural networks potentially possess better representations and performance than real-valued counterparts when dealing with some complicated tasks such acoustic analysis, radar image classification, etc. Despite empirical successes, remains unknown theoretically when and to what extent complex- valued neural networks outperform real-valued ones. We take one step in this direction by comparing the learnability real-valued neurons and complex-vai valued neurons via gradient descent. We show that complex- complex-valued neuron Iearn functions expressed by any one rallev neuron and any one complex- valued neuron with convergence rate Ot and O(t where & is the iteration index of gradient descent, respectively, whereas a two-layer real-valued neural network with finite width cannot learn single non-degenerate complex-valuee neuron. We prove that a complex-valuee neuron learns a real-valued neuron with ()(1"), exponentially slower than the (fe-d) rate of learning one real-valued neuron using a real-valued neuron with a constant c. We further verify and extend these results via simulation experiments more general settings.
efficiently
Introduction
Complex-valle -vauud neural networks (CVNNs) utilize neuron models and operations the complex- valued domain and are good at handling many complicated scenarios. Pioncering works successfully apply CVNNs various areas, such as synthetic aperture radar image classification [1], acoustic analysis [2], and magnetic resonance image reconstruction [3]. In these applications, input signals naturally contain phase information. CVNNs seem more suitable than real-valued neural networks (RVNNs) in deeasddde tasks since empirical experiments and intuitive explanations suggest that CVNNs can possess better data representations phase information and grasp the phase-rotational dynamics more accurately [4, 5].
Beyond the seemingly promising performance of CVNNs, many efforts have been devoted the theoretical understanding of CVNNs. Most existing works demonstrate some desirable properties of CVNNs such universal approximation [6. 7J, the minimum width for universal approximation [8]. boundedness and complete stability [9], most critical points not being local minimum [10], and local-minimum- free conditions [11]. Some recent works demonstrate the approximation advantage of CVNNs in phase- invariant tasks by proving that neuromorphic networks with complex- complex-valued valued operations can approximate radial functions with exponentially fewer parameters than RVNNs [11, 12]. However, those studies do not explain why CVNNs outperform RVNNs mostly in phase- dependent tasks, particularly when considering the fact that there are functions that can efficiently approximated but not efficiently learned with gradient methods [13, 14]. Indeed, the general functional difference between CVNNs and RVNNS remains unknown.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In this paper, we take one step towards understanding when and to what extent one can benefit from common learning paradigms using CVNNs rather than RVNNs. More specifically, we attempt to identify the superiority and inferiority of CVNNs through the following fundamental questions
When CVNNs outperform RVNNs via gradient descent??
Can we learn everything with CVNNs without paying additional price?
We theoretically study the above two questions by focusing on learning a single neuron by optimizing the expected square loss via gradient descent under the setting of low-dimensional inputs and no bias term. Learning a single neuron, a simple and widely investigated learning problem [15, 16, 17, 18), is helpful to understand the difference between learning RVNNs and learning CVNNs since the neural operations inside a fundamental neuron model include the key factors of neural network learning. Furthermore, conduct simulation experiments to verify our theories and extend them to more general settings of high-dimensional inputs and with hias terms. Our contributions are summarized in Table 1 and further explained as follows.
Complex-valued neurons can learn more than real-valued neurons. We prove that using gradient descent, a single complex-valued neuron can efficiently learn functions expressed by any one real-valued neuron and any one complex-valued neuron with convergence rate O(t and O(t ) in Theorems and 2, respectively. In contrast, we show the lower bound of expressing a non -on-deenerraee complex- -aauued neuron with a two-layer RVNN in Theorem 4, which implies that a two-layer RVNN with finite width cannot learn a single non-degenerate complex- valued neuron. These results provide positive responses to the first question from at least two perspectives. Firstly, CVNNs outperform RVNNs when dealing with phase-sensitive tasks. Secondly, CVNN is always conservative choice when we are unwilling to take the risk of failure.
Complex-valued neurons learn slower than real-valued neurons. We present lower bound 2(1-5) for learning functions expressed by any one real-valued neuron using complex-valued neuron via gradient descent Theorem 6. This conclusion, together with the well-known linear convergence of learning functions expressed by any one real-valued neuron using real-valued neuron [19], implies that CVNNs suffer from slower convergence than RVNNs when handling simple phase-independent tasks. This phenomenon answers the second question and reveals the additional price for learning everything with CVNNs.
Table 1: A summary of our contributions. The first column lists the target neurons. The second and third columns represent the convergence rates of learning the target neurons using real-valued neurons and complex-valle valued neurons via gradient descent, respectively.
Target Neurons
Real-valued Neurons
Complex-valued Neurons
Real-valued Neuron
O [19]
(
(Theorems and 6)
Complex-valued Neuron
Cannot Learn (Theorem 4)
((1 (Theorem 2)
The rest of this paper is organized as follows. Section 2 introduces related works. Section 3 details our settings and notations. Section 4 demonstrates that complex-va valued neurons can learn more than real-valued neurons. Section 5 proves that complex-valued neurons learn slower than real-valued neurons. Section 6 concludes our work with prospects.
2 Related Works
Complex-valuee Neural Networks. CVNNS originate in the 1990s when parameters of networks and the commonly used back-propagation algorithm are generalized to the complex-valued do- main [20, 21, 22]. The motivation of CVNNs is at least threefold. From the representation perspective. CVNNs consider the phase information and model complex-valued problems more efficiently and properly than RVNNs [23, 24, 25]. From the computation perspective, a complex-valued neuron is capable of solving the exclusive-or problem and the detection of symmetry, whereas a real-valued neuron cannot [26]. From the biological perspective, the recently proposed flexible transmitter neuron [27], which has a natural complex implementation. formulates the communication between pre-synapse and post-synapse precisely rather than considering only the pre-synapse in traditional MP neuron [28]. CVNNs achieve better performance in versatile applications, especially those with naturally phase-related signals, such as radio frequency signals [29], sonar signals [30], and audio signals [31]. We refer to two surveys for more detailed discussions [4, 5].

---

From the aspect of theories, several works provide preliminary support for CVNNs by proving fundamental properties of CVNNs, such as shallow CVNNs are universal approximators [6, 71, most critical points are not spurious local minimum [10, 11], and CVNNs are bounded and completely stable [9]. These theoretical insights only consider CVNNs without comparison with RVNNs. Another line of research verifies the superiority of CVNNs by comparing the approximation complexity of RVNNs and CVNNs and finding that CVNNs can express radial functions more efficiently [11, 12]. This line of work only takes approximation into account and does not explicitly consider learning processes, which is of more interest in practice. This work takes the first step toward analyzing and comparing the learning behaviors of CVNNs and RVNNs.
Neuron Learning. Neuron learning is the simplest case of neural network learning, and existing works mainly focus on learning real-valued neurons. Some studies demonstrate the possibility of learning one real-valued neuron or a network using meticulously designed algorithms [32, 33, 34]. Later, researchers investigate the learnability of neurons using standard gradient methods. An exponential convergence rate established for learning one real-valued neuron with a real-valued neuron under different assumptions [19, 35, 36, 37, 38]. We consider the problem of learning between one real-valued neuron and one complex-valuce neuron, as well as learning one complex-valued neuron using complex-valued neuron. The heterogeneity between real-valued and complex-valued neurons makes the analysis of optimization behaviors more complicated.
Preliminaries
Notations. Suppose that the input dimension is an even number. For any vector a E R2dd we denote x; the i-th coordinate of æ. Let Øt: (z1j...; + (I.+ ;.2. Cd be the folded complex-valued representation of x, and Ty. = (0i Ia) - (I441 T2a)i is the complex conjugate of Øc- For any two vectors w, v E R2d ww.v = arccos(w (w v ]||w|| | ||||= E [0, ø] denotes the angle between and v. For any function. Let Re(z) denote the real part of a complex number 2. For any 2 E C and & E [0, ' n/2), (2) denotes the real part of the symmetrical version of zReLU activation function [39], i.e.,
I. r(x) max(0, x)} indicates the ReLU activation
(2) { Re(z), 02 E- otherwise,
0,
where 0g represents the argument of z. For any proposition we use T(pp) to represent the indicator function of p, i.c., I(()) = 1 if p is true and I(()) = 0 otherwise. A table of frequently used notations is provided at the beginning of Appendix A.
Learning a Single Neuron. We consider learning target neuron with a learning neuron. neuron generally takes the form æ - de (w: I). where the weight w E 2d and phase & E [0, x/2] indicate learnable parameters, and we omit the bias term for technical reasons. This general formulation includes a real-valued neuron with ReLU activation æ + 7(w x)) and complex-valued valued neuron with zReLU activation æ + ow (w æc) as special cases. For any target neuron with parameters (v, )b).. the learning process consists of finding neuron with parameters (w, vh)) to minimize the expected square loss
1 L(w, www) E.
[o (w: ar) Tee. (v:)))))
where the learnable parameter the occurs only when the learning neuron is complex-valued, and the input æ follows the Gaussian distribution (0,
Learning Algorithm and Initialization. We utilize the projected gradient descent as the learning algorithm, where the projection guarantees the constraint on phase E [0, 7/2). To minimize function fxx) with an initialization Tg, projected gradient descent iteratively updates weights along the negative gradient direction and projects the updated weights onto the constraint set, i.e. 21+1 = Pe n/ V (xx)), where 7), represents the step size, Q denotes the constraint set, and Po indicates the projection operator defined by Po(#n) = arg mill || - .ool-- We initialize weights of neurons with Gaussian distribution, which includes most standard initialization schemes in practice [40]. The learnable parameter of the zReLU activation is initialized with 2/(0, a 7/2), i.e.,
the uniform distribution on [0, π T/2].
3

---

4 Complex-valued Neurons Can Learn More
In this section, we provide theoretical support for the learning advantage of complex-vai -aauue neurons by providing two positive learning scenarios for complex-valus neurons and one negative learning result for real-valued neurons. This section is organized as follows. Subsections 4. and 4.2 confirm the learning power of complex-valued neurons, by verifying that complex-valued neuron can efficiently learn functions expressed by any one real-valued neuron and any one complex-valued neuron, respectively. Subsection 4.3 points out the limited learning capability of real-valued neurons, by proving that a two-layer RVNN with finite width cannot learn a single non-degenerate complex- valued neuron.
4.1 Learning One Real-valued Neuron with Complex-valued Neuron
We first investigate the case of learning one real-valued neuron with ReLU activation using a complex- valued neuron with ZReLU activation, where the expected square loss in Eq. (1) becomes
1 Ler(w: v)- Eo- (w)[ -( r(vTx))) =
(2)
where abbreviate the phase parameter Voe v since the target real-valued neuron does not have phase parameter, w E Rdd and v E Rdd represent the weight vectors of the complex-valuee neuron and the real-valued neuron. respectively. We assume |||||| without loss of generality. Then present the first theorem for complex-valus
neuron learning.
Theorem 1. Let d 1. Suppose that wi ~ (O, I2) and vo ~ U(0 n n/2). Let {(wr, ) denote the parameter sequence of the complex-valued neuron generated by projected gradient descent when optimizing Lan the expected loss of learning a real-valued neuron using a complex-valued 17 E (0, 1/(1xT)), then have
neuron. If the step size тr
8000
+ (1
7 41 32/n
Pr Ler (w:, (wr,
vir))
S
48
32
Theorem shows that complex- valued neuron can efficiently learn the functions expressed by any one real-valued neuron with convergence rate O(t using projected gradient descent. It should be mentioned that do not attempt to decrease the large constants in the theorem, they do not hurt the constant probability and convergence rate.
The constant probability, rather than high probability, comes from the intrinsical difference between real-valued neurons and complex-valued neurons. real-valued neuron activates half of the phase domain, whereas a complex-values neuron may only activate a small part as controlled by the parameter vi, which makes the expected loss piecewise function. When the initialization of wr falls into the opposite direction of and z is small, the activated regions of the vellevalued and complcx-valuee neurons are not overlapped. Such a bad initialization happens with a constant probability and encourages the complex- complex-valued neuron to decrease phase to minimize the loss. As result, the phase of the complex-valued neuron will shrink to zero, which leads to a constant expected square loss and the failure of learning.
Challenges. Although (w, ab) (v, x/2) an obvious global minimum of the expected loss with Ler = 0, the convergence conclusion in Theorem is non-trivial. As one can see in the proof, the landscape of the expected loss possesses a stationary point (w, v) = If we initialize w kw with & > 0, then it is easy to verify that w converges to 0 and s decreases to 0 when the step size is sufficiently small. This implics that the landscape not convex and the spurious stationary point is an attractor. The existence of this spurious stationary point becomes critical obstacle in the proof and provides another reason for the hardness of a high-prot nigh-probabiiity conclusion.
The proof idea of Theorem 1 mainly consists of estimating the first-order derivatives and finding an ideal region with both constant probability and convergence guarantees. We provide proof sketch as follows. Firstly, we analyze the optimization behaviors of w and &b in all pieces of the loss function separately. Then we identify an ideal region with desirable gradient properties: the gradient V Lar wn, rb) can be bounded by O( T/2 22)2), which implies that ta - x/2 decreases with an inversely propositional rate. Meanwhile, gradient descent on uo performs like a contraction mapping with fixed point v and Lipschitz constant 1 ( i.c., converges to linearly when vi

---

w|w 2/1
l|w Mll 1+ Vol
w n1/2
Stage
Stage
Stage
Stage II
Stage III
(a) Convergence stages of Theorem
1.
(b) Convergence stages of Theorem 2.
Figure Subfigures (a) and (b) demonstrate the convergence stages Theorems and respectively, The horizontal axis represents the iteration index of gradient descent. The black dotted line denotes separation convergence stages.
large enough. Based on these observations, our convergence analysis consists of two stages, as shown in Fig. ((a). In Stage the phase v converges towards the global minimum, and the weight w remains in the ideal region. When the phase grows above some threshold, one enters Stage II where the weight converges linearly and the phase maintains its slow convergence rate. Finally, we estimate the order loss and provide a lower bound of the probability of falling into the ideal region with Gaussian initialization complete the proof. Detailed proofs available in Appendix B.
4.2 Learning One Complex-valued Neuron with Complex-valued Neuron
We proceed consider learning one complex-valuse valued neuron using a complex- valued neuron. this case, the expected square loss in Eq. (1) can be rewritten as
Lee(w (w, v) (o.) [o (ww(w - o (v x=))))
where (v, Φ) denotes the parameter of the target complex-valuee neuron, and (w, 1)) is the learnable parameter. Without loss generality, we still assume || = 1. Here, we use gradient descent with vanishing step size Iz+1 = T)t (xxx), where the positive step size т/t satisfies Then we present second theorem for complex-vail -aauued neuron learning.
as co.
Theorem 2. Let d 1, and th E [7m/20, 2n/5), Suppose that wo NN I2) and the.0 u(0, a /2). Let {(w,, wn.x) 2i denote the parameter sequence of the complex-valuce neuron generated by projected gradient descent when optimizing Lees the expected loss of learning complex- valued neuron using a complex-valued valued neuron. If we utilize vanishing step size π = min(ci, c2/t) with C1 & 1/3000 and 02 > 20, then
400g eit
Pr
Lee Lec (w,,))
<
50
Theorem demonstrates that complex- neuron efficiently learn functions expressed by any one complex-valus neuron with convergence rate O(1-1) and constant probability.
Challenges. It is observed that the O(!-1) convergence rate in Theorem is slower than the O(L-3) convergence rate in Theorem 1. The deceleration of convergence comes from the intrinsic difficulties of learning functions expressed by any one complex-values neuron. These difficulties become the main challenges the analysis and can be understood from at least two perspectives. Firstly, there emerge new spurious stationary points. As one
in the proof, the gradient with respect to Vh becomes 0 once tha reaches π / and w is close to v. i.e., (w, = (v, x/2) is spurious stationary point. Secondly, the landscape of the loss function is no longer smooth. For both and ai.. the local landscape around the global minimum is roughly an absolute function, which declares the non-smoothness of the loss and the failure of gradient descent with constant step size.
To overcome these obstacles, we apply mild conditions and slight modifications to guarantee conver- gence and maintain the generality of our conclusion. We separate the phase of the target complex-
5

---

valued neuron far from 0 and 2/2 in consideration of spurious local stationary points: As v. becomes closer 0, it is more likely to obtain an initialization of the learning neuron that does not over- lap with the target neuron. Then we will take the risk of falling into the spurious local minimum (un, )/2) (0, 0). As the approaches /2, we are confronted by another spurious stationary point Ve = /22 We utilize gradient descent with a vanishing step size to cope with the non-smoothness of the loss function since a constant step size inevitably suffers from oscillation.
We summarize the proof idea of Theorem 2 as follows. The overall procedure is similar to that of Theorem 1 but every step is different and more challenging because of non-smoothness and more spurious stationary points. Firstly, we identify an ideal region with nice gradient properties: the gradient with respect to tT, the weight component perpendicular v. points to the global minimum O and maintains constant order. The gradient V.... is bounded and points towards V. when the angle fe is small enough. Meanwhile, the gradient with respect to wp performs like contraction mapping with fixed point [1 ( and Lipschitz constant - O i.e., there exists deviation of the fixed point from the global minimum. Based on these observations, we then prove the convergence with three stages, as demonstrated in Fig (bb): In Stage I, w., the weight component perpendicular to converges to 0 with an inversely proportional rate, and ddw and w. remain in the ideal region. Thus, the angle ue, decreases with an inversely proportional rate. When ww. declines below some threshold, T approaches v.. the fixed point becomes close to and we step into Stage III where w converges to with the same rate as the. Finally, estimate the order of loss and provide a lower bound of the probability of falling into the ideal region with Gaussian initialization to complete the proof. We provide detailed proofs in Appendix C.
come Stage II where phase v converges 1h, with rate O(t-1). As
4.3 Finite-Width RVNNs Cannot Learn Single Non-degenerate Complex-valued Neuron
We then study learning one complex-va neuron with zReLJU activation using real-valued neurons. Since complex-valued neuron has more parameters than real-valued neuron, it is unfair to learn complex-valuee neuron with single real-valued neuron. Thus, we consider the problem of learning a complex-value valued neuron with a two-layer RVNN. two-layer RVNN with n hidden neurons can be represented by æ + a r(Wæ), where W E 2 and a E R" indicate weight parameters of the network, and is the ReLU activation function applied componentwisely. We still focus on the expected square loss, which takes the form
La, w) WEODD (a (<Tr(W>)) -oy (v) xc))
where we abbreviate the phase parameter v. as vi since RVNN has no phase parameter. We are mainly interested in learning a non-degenerate complex-valued neuron, which is distinct from a real-valued neuron and defined follows.
Definition 3. A complex-valued neuron is non-degenerate one if v/ & {0, x/2) and + 0.
For a complex-valued neuron with phase 1b = or a = O, the zReLU activation function always outputs O. Then the complex-valus valued neuron is equivalent to real-valued neuron with all zero weights. For a complex-valued with phase v = π 22 the zReLU activation function is equivalent to the ReLU activation function. Thus, non-degenerate complex-valuee neuron is non-real-valued neuron. Then we present the third theorem for complex-valued neuron learning.
Theorem 4. Let = 1. For any non-degenerate complex- valued neuron with phase v E x0,z/2) and non-zer zero weight vector v E Cd, denote by Thee the expected square loss of learning this complex- valued neuron using the-hidden-laye RVNN with n hidden neurons. Then the loss satisfies
| min (24,, π 240 > 0.
(a W)
24 + 2)
Theorem 4 provides positive lower bound for the expected squared loss of approximating non- degenerate complex-valus neuron using two-layer RVNN with a fixed number of hidden neurons. This positive lower bound indicates that there always remains a positive gap between the target non-degenerate complex-valued neuron and the two-layer RVNN of fixed width no matter how the parameters of the RVNN are learned. Thus, a finite-width RVNN cannot learn single non-degenerate complex- valued neuron.

---

2S
W2
W1 + W2
W1
S
W,
Wg
3
A3
A2
A
W3
W3 W4
S
W4
(a) The loss in one sector.
(b) The loss in four sectors.
Figure 2: An illustration of the proof idea Theorem 4. Shaded areas represent sectors with infinite radii. (a) The expectation Emes| [(w x)²] in the sector 8 equals the sum of the expectations three subareas AI, A2, and A3. The minimum expectation on a subarea can be bounded by 12(021[ww) [[w]) (b) The expected loss of learning complex-valued neuron using four symmetric real-valued neurons in four symmetric sectors can be bounded by !2(02 || where w; indicates the weight vector of the i-th real-valued neuron, and denotes that of a complex- valueed neuron.
The lower bound decreases at rate O(Ilv |2 min/,2,, 2n²) The norm term || depicts the magnitude of the problem, which affects the expected square loss quadratically from the homogeneity of zReLU. J. In the extreme case of v O, trivial real-valued neuron with O reaches the lower bound 0. Meanwhile, the lower bound possesses positive relation with phase-dependent term {2e, . 2. Intuitively, this term indicates the difference between complex-valuee neuron and real-valued neuron. A real-valued neuron corresponds to ab 0 or e = π n// and this term measures the distance between the phase of complex-valued neuron and real-valued one. Finally, the lower bound decreases with rate inversely proportional to the square of hidden size n. We conjecture that this dependence tight and cannot be improved: a two-layer RVNN with n neurons divides the space into n pieces, in each of which RVNN acts as linear function. Choosing the n weight vectors of RVNN suitably, the difference between the RVNN and the complex-valued neuron remains small (of order 1) in each piece, which leads to the expected loss of order ((n
The conditions Theorem are made for conciseness proof and we believe the conclusion holds in more general cases. The dimension d = corresponds to the intrinsic dimension of expressing complex-valued neuron because of the rotational invariance of the inner product and the spherical symmetry of Gaussian distributions. Thus, additional dimensions contain no information and cannot improve the efficiency of approximation when > It is necessary to consider non-degenerate complex-valued neurons since degenerate complex- complex-valued valued neurons are equivalent to real-valued ones.
observed that the expected square loss Lie is a piecewise quadratic function and each piece forms a sector centered at the origin with infinite radius. In each piece, I.e. takes the form El(w0 )² The proof mainly consists of two steps: we obtain a lower bound of Tye in a sector and then sum over all sectors with suitable weights and order. Firstly, we consider the expected loss in a sector with a small central angle as shown in Fig. 2(a). We divide the sector into three identical subareas A,, Ag. and A3. Then at least one of Aj and Ag remains 0/6 away from the vertical direction of w. which leads a lower bound (20 [ Secondly, we consider the loss in four rotationally symmetric sectors, as shown in Fig. 2(b), where represents complex-vali
We provide the central proof idea of Theorem 4 as follows.
neuron, w; indicates real-valued neuron, and the expression in each sector implies the activated neurons. It is observed that at least one sector possesses a weight vector with norm ([[=)]]) no matter how we choose the real-valued neurons. Thus, the overall loss bounded by 22002 122) Finally, we take the weight a into consideration and sum over all sectors. For RVNN with n neurons, the best choice of O(n arrives the lower bound ((n -I])) Detailed proofs are provided in Appendix D.
7

---

Summary and simulation experiments. We summarize the main conclusions of this section in Table 2. Both a real-valued neuron and complex-van -vauue neuron succeed in learning functions expressed by any one real-valued neuron. But difference occurs when learning those expressed by any non-degenerate complex-valued neuron: A complex-valuee neuron can efficiently learn functions expressed by any one complex-valuee neuron, but two-layer RVNN with finite width cannot learn a single non-degenerate complex-vai that a complex-valued neuron possesses more powerful learning capability, which profits from the consideration of phase information in complex-valued operations. Our theoretical conclusions are based the setting of low-dimensional inputs and no bias term, and the simulation results in Fig. verify and extend these discoveries in more general settings. Details about the simulation experiments available in Appendix F.
neuron. Such a disagreement demonstrates
Table 2: complex valuuex neuron can learn more than real-valued neuron.
Target
Real-valued Neuron
Complex-valued Neuron
Real-valued Neuron
(ce [19]
O(t-3) (Theorem
Complex-valus Neuron
Cannot Learn (Theorem 4)
0 (Theorem 2)
0.3
0.4
Real Neuron
Real Neuron
Complex Neuron
0.3
Complex Neuron
Test Error
0.2-
Test Error
0.2
0.1
0.1
0.0
0.0
20
40 60
80
100
100
200
300
Number of Epochs
Number of Epochs
(a) d 1 and no bias term.
(b) d = 5 and with bias terms.
Figure 3: The test error of learning a complex-valued neuron. In both the theoretical setting (Fig. 3a) and more general settings (Fig. 3b), complex-valus valued neurons have vanishing errors, while real-valued neurons converge to positive errors.
5 Complex-valued Neurons Learn Slower
In this section, we demonstrate that complex-valude neurons learn slower than real-valued neurons. To arrive at this conelusion, we first rephrase the linear convergence of learning functions expressed by any one real-valued neuron using real-valued neurons. Then we prove that complex-valus neuron learns the same class of functions an exponentially slower rate.
We concentrate on learning one real-valued neuron x - r(v x) with || = 1. When learning one real-valued neuron using real-valued neuron, the expected square loss in Eq. (1) possesses the following simple closed form [41]
1 w [ssi ow, + (Tr i ) cos ow
1
Lye (w) |11112
2TT
4
It is widely known that real-valued neuron learns real-valued neuron with high probability and linear convergence rate [19], as reformulated by the following lemma.
Lemma S. [19, Theorem 6.4| Suppose that the weight vector w E 2d is initialized by a Gaussian distribution (0, 1/22)). Let Lu denote the expected square loss of learning real-valued neuron using a real-valued neuron. Then there exist constants C12 C2 such that gradient descent with suitable step size satisfies
Pr(Ln(we) e 1 e
8

---

l|w Ne M/l
Stage
Stage II
Stage
Stage
Figure 4: A demonstration of the convergence stages of Theorem 6. The horizontal axis represents iteration index of gradient descent. The black dotted line the separation of convergence stages.
Recalling the expected loss of learning one real-valued neuron with a complex-valued neuron in Eq. (2), then present the fourth theorem for complex-valued neuron learning, which provides lower bound for the convergence rate.
Theorem 6. Let d = 1. Suppose that - < 1. Let {ww, bi) denote the parameter sequence of the complex-valice neuron generated by projected gradient descent when optimizing Ler the expected loss of learning real-valued neuron using complex-valuee neuron. If the step size l 17 E (0, (1277) then we have
(1 3T// -b)
1
T
Ler Ler vh))
8T(1
1)3
2T
48
where 30- = 1/2, and T3 is a constant dependent on ||wo 1/, and ai*
400-
Theorem 6 presents a lower bound for the expected loss of learning one real-valued neuron with complex-valued neuron. It is observed that the negative term in the lower bound becomes 0 exponentially fast as increases, and the positive term decreases with order ()(t Thus, the expected loss possesses lower bound ()t=3) since the positive term dominates the loss when
grows sufficiently large. This lower bound matches the upper bound in Theorem 1. Thus, O(1-3)
becomes the utmost limit of learning with complex-valuee neuron via gradient descent, i.e., cannot expect a complex-valued neuron to learn faster than this utmost limit.
The conditions in Theorem 6 are technical and reasonable. The condition wo is made for the conciseness of proof and can be removed. is observed that (w, v) = (v, v)*) is the unique global minimum with Ler 0. Meanwhile, it is easy to verify that the loss goes infinity when ||w|| oo. Thus, if we aim to obtain a small loss, the parameter sequence must fall into a small neighborhood of the global minimum, which is depicted by condition wwy wll < R < 1. The condition th e holds with probability when we initialize Y/ with a continuous distribution. This condition is necessary obtain meaningful lower bound since the numerator of the positive term equals 0 when tho vh We emphasize that this condition is essential and cannot be removed because real-valued neuron, which enjoys linear convergence as stated in Lemma 5. The condition = corresponds to the simplest optimization neuron since -ihhdiinnnsioall
complex-valued neuron with thn v/" is equivalent
problem learning one real-valued neuron with a complex-valee optimization brings more difficulties. Thus, we cannot expect a complex-valued neuron to learn higher dimension.
real-valued neuron with convergence rate faster than O
We summarize the proof idea of Theorem as follows. The gradient with respect to possesses the order (.* - )² + (ah* W The key intuition is that converges fast the global minimum when 6 remains large, but Oun. diminishes as to converges to the global minimum v. The detailed proofs complicated and consist of several stages, depicting the entangled convergence between and s as shown in Figure In Stage I, 1b increases above a positive constant, which is a necessary condition for fast convergence of ur in Stage II. When the distance between and declines below a threshold, the angle 0 becomes small. Then we enter Stage III, where w converges faster than db. Stage IV begins when ~ं" dominates fw,.. Then the gradient degenerates to order (o² - = which implies a lower bound of convergence 3/² = 1(1=1). Finally, estimating the loss around the global minimum leads to the conclusion. Detailed proofs provided in Appendix E.

---

Summary and simulation experiments. Table 3 summarizes the conclusions in this section, which shows that complex-values neuron learns slower than real-valued one. complex-valuee neuron is more flexible since it can learn the phase. But this flexibility becomes redundant and slows down the convergence when learning a phase-independent function. Our theories are based on the setting of low-dimensional inputs and no bias term, and the simulation results in Fig. 3 verify and extend these discoveries in more general settings. Details about the experiments are available in Appendix
Table 3: A real-valued neuron learns faster than complex-valued neuron.
Target
Real-valued Neuron Complex-valued Neuron
Real-valued Neuron
O(e-a) (Lemmaa 5)
(2(= (Theorem 6)
0.5
0.5
Real Neuron
Real Neuron
0.4
Complex Neuron
0.4
Complex Neuron
Test Error
Test Error
0.3
0.3
0.2-
0.2-
0.1
0.1
0.0
0.0
20
40
80
100
20
60
80
100
Number of Epochs
Number of Epochs
(a) d and no bias term.
(b) d = and with bias terms.
Figure 5: The test error of learning real-valued neuron. In both the theoretical setting (Fig. 5a) and more general settings 5b), a complex-valuee neuron learns a real-valued neuron slower.
6 Conclusions and Prospects
In this paper, investigate the problem of learning single neuron using another neuron by optimizing the expected square loss via gradient descent. Firstly, we prove that a complex-valued neuron can efficiently learn functions expressed by any one real-valued neuron and any one complex- valued neuron with convergence rate O(L-3) and O(I-1), respectively, where I denotes the iteration index of gradient descent. Mcanwhile, two-layer RVNNs with finite width cannot learn a single non- degenerate complex-valued neuron in strong sense that there always exists a positive gap between a two-layer RVNN of fixed width and a non-degenerate complex-valued neuron. These conclusions suggest that complex-value neurons can learn more than real-valued neurons since CVNNs benefit from the phase parameter, which helps CVNNs learn phase information more efficiently. Secondly, we provide convergence lower bound ((t=a), which matches the upper bound, for learning one real-valued neuron with a complex-valie valued neuron. This conclusion, together with the well-known linear convergence of learning one real-valued neuron with real-valued neuron, implies that complex- valued neurons learn slower than real-valued neurons mhase-independent tasks. This phenomenon captures the additional price for learning simpler tasks with more complicated models, where the redundant phase considcration exponentially slows down the convergence.
Our study serves as a preliminary attempt to compare the learning process of artificial neural networks with different functional operations. In the future, it is important to extend our theoretical results to more general settings, such as cases of nigh-dimensional inputs, equipped with bias terms, and over- preatearamteriize architectures [42]. Meanwhile, it prospective investigate complex complex-valued valued neuron learning from finite samples and derive high-probabiliig convergence condition. Since the empirical loss is piecewise constant function with respect to the learnable phase parameter, might be necessary to explore new learning algorithms, which is also encouraged by the neural tangent kernel aspect [43]. Besides, is promising to consider the more practical and challenging procedure of learning general functions with deep architectures.
10

---

Acknowledgments
This research was supported by NSFC (61921006) and Collaborative Innovation Center of Novel Software Technology and Industrialization. We would like to thank the anonymous reviewers for their invaluable suggestions.
References
[1] Zhimian Zhang, Haipeng Wang, Feng Xu, and Ya-Qiu Jin. Complex-valued convolutional neural network and its application in polarimetric SAR image classification. IEEE Transactions on Geoscience and Remote Sensing, 55(12):7177-7188, 2017.
[2] Izhak Shafran, Tom Bagby, and RJ Everry-Ryan, Complex evolution recurrent neural networks (ceRNNs). In Proceedings of the 2018 IEEE International Conference on Acoustics, Speech and Signal Processing, pages 5854-5858, 2018.
[3] Shanshan Wang, Huitao Cheng, Leslie Ying, Taohui Xiao, Ziwen Ke, Hairong Zheng, and Dong Liang. DeepcomplexMRI: Exploiting deep residual network for fast parallel MR imaging with complex convolution. Magnetic Resonance Imaging, 68:13714 2020.
[4] Joshua Bassey, Lijun Qian, and Xianfang Li. A survey of complex-valued neural networks. 1et::2101.12249 2021.
[5] ChiYan Lee, Hideyuki Hasegawa, and Shangce Gao. Complex-valued neural networks: A comprehensive survey. JEEE/CAA Journal of Aulomatica Sinica, 406,1446, 2022.
[6] Tachwan Kim and Tülay Adali. Universal approximation fully complex feed-forward neural networks. In Proceedings of 2002 IEEE International Conference on Acoustics, Speech, and Signal Processing, pages 973-976, 976, 2002.
[7] Felix Voigtlaender. The universal approximation theorem for complex-valued neural networks. Applied and Computational Harmonic Analysis, 64:33-61, 2023.
[8] Paul Geuchen, Thomas Jahn, and Hannes Matt. Universal approximation with valuue deep narrow neural networks, arXiv:2305. 2023.
[9] Bo Zhou and Qiankun Song. Boundedness and complete stability of complex-valued neural networks with time delay. IEEE Transactions on Neural Networks and Learning Systems, 2428):1277-1238, 2013.
[10] Tohru Nitta. Local minima in hierarchical structures of complex-valuee neural networks. Neural Networks, 43:1-7, 2013.
[11] Jin-Hui Wu, Shao-Qun Zhang, Yuan Jiang, and Zhi-Hua Zhou Thcoretical exploration of flexible transmitter model. IEEE Transactions on Neural Networks and Learning Systems, 2023. doi: 10.1 10.100//NNN.S
[12] Shao-Qun Zhang, Wei Gao, and Zhi-Hua Zhou. Towards understanding theoretical advantages of complex-reaction networks. Neural Networks, 151:80-93, 2022.
[13] Eran Malach and Shai Shalev-Shwartz. deeper better only when shallow is good? In Advances in Neural Information Processing Systems 32, pages 4435, 2019.
[14] Eran Malach, Gilad Yehudai, Shai Shalev-Schwartz, and Ohad Shamir. The connection between approximation, depth separation and learnability in neural networks. In Proceedings of the 34th Conference on Learning Theory, pages 3265-3295, 2021.
[15] Peter Auer, Mark Herbster, and Manfred K Warmuth. Exponentially many local minima for single neurons. Advances in Neural Information Processing Systems 8, pages 316-322, 1995.
[16] Spencer Frei, Yuan Cao, and Quanquan Gu. Agnostic learning of a single neuron with gradient descent. Advances in Neural Information Processing Systems 33, pages 5417-5428, 2020.
11

---

[17] Ilias Diakomikolas, Surbhi Goel, Sushrut Karmalkar, Adam R Klivans, and Mahdi Soltanolkotabi. Approximation schemes for ReLU regression. In Proceedings of the 33rd Annual Conference on Learning Theory, pages 1452-1485, 2020.
[18] Ilias Diakonikolas, Daniel Kane, Lisheng Ren, and Yuxin Sun. SQ lower bounds for learning single neurons with Massart noise. Advances in Neural Information Processing Systems 35, pages 14006-24015 2022.
[19] Gilad Yehudai and Ohad Shamir. Learning a single neuron with gradient methods. In Procced- ings of the 33rd Conference on Learning Theory, pages 3756-3786, 2020.
[20] Henry Leung and Simon Haykin. The complex backpropagation algorithm. IEEE Transactions on Signal Processing, 399))2201122144, 1991.
[21] Nevio Benvenuto and Francesco Piazza. On the complex backpropagation algorithm. IEEE Transactions on Signal Processing, 40(4):967-96) 1992.
[22] George M Georgiou and Cris Koutsougeras. Complex domain backpropagation. IEEE Trans- actions on Circuits and Systems II: Analog and Digital Signal Processing, 39(5)333--334, 1992.
[23] Paolo Arena, Luigi Fortuna, R Re, and Maria Gabriella Xibilia. Multilayer perceptrons to approximate complex valued functions. International Journal of Neural Systems, 6(4):435-446, 1995.
[24] Md Faijul Amin, Ramasamy Savitha, Muhammad Ilias Amin, and Kazuyuki Murase. Complex- valued functional link network design by orthogonal least squares method for function approxi- mation problems. In Proceedings of 2011 International Joint Conference on Neural Networks, pages 1489-1496, 2011.
[25] Akira Hirose and Shotaro Yoshida. Generalization characteristics of complex-valued feedfor- ward neural networks in relation to signal coherence. IEEE Transactions on Neural Networks and Learning Systems, 23(4):541-551, 2012.
[26] Tohru Nitta. Solving the XOR problem and the detection of symmetry using a single complex- valued neuron. Neural Networks, 1608):10011110, 2003.
[27] Shao-Qun Zhang and Zhi-Hua Zhou. Flexible transmitter network. Neural Computation. 33(11):2951-2970 2021.
[28] Warren S McCulloch and Walter Pitts A logical calculus of the ideas immanent in nervous activity. The Bulletin of Mathematical Biophysics, 5(4):115-133) 1943.
[29] Junming Zhang and Yan Wu. A new method for automatic sleep stage classification. IEEE Transactions on Biomedical Circuits and Systems, 11(5):1097-1110, 2017.
[30] Jingkun Gao, Bin Deng, Yuliang Qin, Hongqiang Wang, and Xiang Li. Enhanced radar imaging using a complex-valued convolutional neural network. IEEE Geoscience and Remote Sensing Letters, 16(1):35-39, 2018
[31] Chiheb Trabelsi, Olexa Bilaniuk, Ying Zhang, Dmitriy Serdyuk, Sandeep Subramanian, Joao Fe- lipe Santos, Soroush Mehri, Negar Rostamzadeh, Yoshua Bengio, and Christopher J Pal. Deep complex networks. In Proceedings of the 6th International Conference on Learning Representa- lions, 2018.
[32] Adam Tauman Kalai and Ravi Sastry. The isotron algorithm: High-dimensional isotonic regression. In Proceedings of the 22nd Conference on Learning Theory, 2009.
[33] Sham M Kakade. Varun Kanade, Ohad Shamir, and Adam Kalai. Efficient learning of general- ized linear and single index models with isotonic regression. In Advances in Neural Information Processing Systems 24, pages 927-935, 2011.
[34] Surbhi Goel, Varun Kanade, Adam Klivans, and Justin Thaler. Reliably learning the ReLU in polynomial time. In Proceedings of the 30th Conference on Learning Theory, pages 1004-1042, 2017.
12

---

[35] Mahdi Soltanolkotabi. Learning ReLUs via gradient descent. In Advances in Neural Information Processing Systems 30, pages 2007-2017, 2017.
[36] Simon Du, Jason Lee, and Yuandong Tian. When is convolutional filter easy to learn? In Proceedings of the 6th International Conference on Learning Representations, 2018.
[37] Song Mei, Yu Bai, and Andrea Montanari. The landscape of empirical risk for nonconvex losses. The Annals of Statistics, 46(6A):2747-27744 2018.
[38] Seyed Mohammadreza Mousavi Kalan, Mahdi Soltanolkotabi, and A Salman Avestimehr. Fitting ReLUs via SGD and quantized SGD. In Proceedings of 2019 IEEE International Symposium on Information Theory, pages 2469-2473, 2019.
[39] Nitzan Guberman. On complex valued convolutional neural networks. arXiv:1602.09044 2016.
[40] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the 13th International Conference on Artificial Intelligence and Statistics, pages 249-256, 2010.
[41] Itay Safran and Ohad Shamir. Spurious local minima common in two-layer ReLU neural networks. In Proceedings of the 35th International Conference on Machine Learning, pages 4433-4441, 2018.
[42] Zhi-Hua Zhou. Why over-parameterizaaion deep neural networks does not overfit? Science China Information Sciences, 64:1-3, 2021.
[43] Zhi-Hao Tan, Yi Xie, Yuan Jiang, and Zui-Hua Zhou. Real-valued backpropagation is unsuitable for complex-values neural networks. Advances Neural Information Processing Systems 35, pages 14052-34063, 2022.
13

---

Appendix of "Complex-valued Neurons Can Learn More but Slower than Real-valued Neurons via Gradient Descent"
A Preliminaries
In this section, we first summarize frequently used notations in the following table.
Table 4: Frequently used notations.
Notation
Description
Cd
the d-dimensional complex space expectation
I(-)
the indicator function the expected square loss of learning a neuron the standard Gaussian distribution
L
I)
0,2, e
asymptotic notations
Pr
probability
Po(x)
the projection æ on Q the 2d-dimensional real space the real part of a complex number the iteration index of gradient descent the uniform distribution on the interval [a, b] the weight vector of learning neuron the weight vector of target neuron an input vector in 2d the i-th coordinate of
R
Re(=)
U(a, b)
w
x
acc ( =a) + (Za-1i... æza)i Cd complex conjugate of æc the angle between and b the argument a complex number =
ag
lab
(2)
the real part of the symmetrical version of zReLU activation function the step size of gradient descent the ReLU activation function r(x) max(0,
tb
the learnable parameter of the symmetrical version of zReLU activation function gradient
V
the 2-norm of a vector
We then give some basic lemmas that help us calculate the closed form of the expected loss. Lemma 7. Let d = 1. For any w. v E Rdad, and a < b & a + 2n, we have
A(w, v. a. b) = (0,
ww"" T x T I(0, E [a, 6]]]
[2 a) cos we + sin + 0, 2a) - sin(O,, - 0, - 26)]
4m
Proof. According to the probability density function of Gaussian distribution, calculate A in the polar coordinate system as
||l|l |||
(. pb 3r cos(Ou - x)) cos(Op Φ) dé dr
A(w, u.,.0,a a,
2x
[w|||(>]
cos(On. - cos(O, deb
[
|||||||||
[2 a) cos fw + sin + 0, - 2a) - -sin(Ow. 0, 26)]
4m
where the second and third equalities hold from integrating over r and di, respectively. Thus, we have completed the proof.
D
14

---

Lemma 8. Let d = 1. For any w, E R2dd, denote by 0 = w the angle between w and v. Then for any Pus 4r E [0, x/2,, define 4m fio vo Then we have
Blw, u, Vwr 1h) = (0. (op (wn ac))
||lll|||| cos w, (2 + sin(2
0 w E 10:11// &wlll
| (2( + v/ - o) cos ue - sin(0w. 2
4n
sin(O 21/we)
0 0w, v E l1 va the Vidl 0 E (10v + th T]
Proof. We only consider the case of a/u v/- The other case thw the can be proven similarly, We prove the conclusion by discussion.
1. Suppose O E [0, the v.... Then Lemma 7 leads
1 |
B(w, v, Vie tho) Alw, v, Ow shws Our + v/n))
cos Own. (2 sin(2r/ww)
2x
2. Suppose O E 11/0 this Uh + +/ul and Ow < Or. Then one knows from Lemma that B(w, w, vws vho) = A(w, w. O2 -os Ow + viw)
||0|| ||ll (2(th + wh - Ow,, cos Ow. - sin(Ow.. 2xb)) - sin(Ow. 24/ }]
4x
3. Suppose wwo E [1/ the Uo viel and fw 7 t.. Based on Lemma have B(w, Vn, Mhe) = A(w, Aw - thes 0. + the)
-| ||||||||||
12(ti + to (w cos w sin(fw,v 2xbe) - sin(fwr, 2//wa
4m
4. Suppose Oun E [&h, + the, T]. Then the support of ome (w) Tc) does not overlap with that of Tw. (ut æC), which leads to B(w, n, th. v/)) = O.
Combining the cases above completes the proof.
B Proof of Theorem 1
In the main part of this section, we provide the closed form of the loss, definition of the ideal region, and the detailed proof of Theorem I. Subsection B.1 presents the optimization behaviors in the ideal region. Subsection B.2 proves several convergence rate lemmas. Subsection B.3 gives some technical lemmas bound small terms in the proof.
Let w (w1, W2). According to the spherical symmetry, we assume (1, without loss of generality. According to Lemma 8, the expected loss can be calculated by
1
Lwr v6) B(w, w. v. vb) B(w, u, vh 7/2) + B(v, 72,
2
- (sin( + 20 (w) - 1)2 w
E [0, //
7
47 (2in + 20) (2x) (20) |21 + u2l
2x 2 sin (sin((2))))
T
( 1 f f)
w
0 /2 1, v) 0 |T 1 -
+ d 120 sin(2t))
(3)
where 0 = Om = arccos(w) / /ww + w For any R E (0, define
D {ww, v-) | - 0|| < R 00, 0 E |0, w))
D2 [ww, v+ ||w 1| < R //, (T/2- - 11
Let D = Dí U D2 denote the ideal region, i.e.,
D (w, v6)) || w|l R, [0. - 2), 0 | /0.
We are now ready to prove Theorem 1.
Proof of Theorem 1. The proof is divided into four steps.
Step I: 7 is closed under gradient descent. Before considering the convergence, we prove the maintenance of inclusion by mathematical induction, i.e.. (wo, vh) D indicates (w,, v/)) D.
15

---

1. Base case. The conclusion holds for t = 0 from the condition.
2. Induction. Suppose that the conclusion holds for with N. Then based on Lemmas 11 and 12, one knows
R²
6(65* - vK) & We vx) <
(z) <0;
(v'
(4)
4T
where - = 2 the first inequality holds based on the induction hypothesis and l22 & 1, and the third inequality holds from R 1. Thus, the updating rule vh+1 with 17 E (0, 1/(m)) leads to
thv 17 V (Wnk, the)
2
th 7 30"" 1h41 e (1 - (1) thx))
(5)
where the first and fourth inequalities hold from the induction hypothesis. Meanwhile, Lemmas and 10 imply
|| |00+1 - w1l < (1 24 (2)))) + 2//el) || - w1l & R.
(6)
Combining Eqs. (5) and (6), the conclusion holds for = + 1.
Therefore, mathematical induction implies (We, v/x) E D when (wo, tho) E D.
Step 2: parameters converge to the global minimum in D. The convergence process consists of two stages. In stage I, we deal with the convergence of to when (wo, vo) E D. Based on Eq. (4) and the updating rule 1h++1 = Th - 17 Lor (Wks v'k), one knows
(
w/- - 1/+1 & (1b" - whe) 1 17(1 R2
(1)
4
Define a, (1 ([(1-RR)(6 (²²- - 2b (4T). Then we obtain a++1 & a,(1 a.). From نه - - E [0, x/2]
and 1) < 1/(12m) < 4, one knows a E [0, 1/2]. Thus, applying Lemma 14 to a, leads
4Ta.
4T
(1 R2)
17(1 (t)
In stage II, we consider the convergence of w when (wo. vho) E D. Based on Eq. (7), choosing Ti > 16 (1 Rº)1-1 leads to 40* 1/4 π / for any t Ti, i.e., t/e xt for any t > Ti. Thus, for any t > Ti, Eq. (6) indicates
lw: all < (1-1) | wl1
17 t-T,
48
where the first inequality holds from the monotonic increasing of sin(x) + and the > 7/4. and the second incquality holds because of www wll < R < 1.
Step 3: the loss converges to in D. We estimate the convergence of the expected loss when (wo, tho) E D. For any (w, vb) E D. define non-negative quantities Aw = ||w-vl] and A. = 3² vb. We provide upper bound for Ler by discussion.
1. Suppose (w, vb E D1. Then we have
1
1
Ler (e v)) <
(1--
A3)
A
<
A3
+
A
(9)
2
2T
4
where the first inequality holds based on sin( + 2 = (2n and the second inequality holds from non-negative Ap.
+2/
22
>
24- -243
2. Suppose (w, 4+) E Dz. The expected loss can be rewritten as
1
T.er (w. 1b)
(2ib(
21b A?,
4
4m
1
[cc0)(24))
1) wz2 + (sin(2
2nb - 20 -2 )(]]
4T
1
1
(v+*
) (1 A +
[ + 20 2 wwrl
(10)
4
2m
4m
1
1
(1b*
2
+
Aw (1 + Aw)
4
2m
2n
1
A
Am
A2
2x
2T
2
16

---

where the first inequality holds from π > sin(2 + 2 > 22/ - 2 and cos(21)) - & 0, the second inequality holds based on 0 < tan 0 < Aw and wi < 1 + Aw. and the third incquality holds from Av 2 0.
Combining Eqs. (9) and (10), one knows that the following holds for any (wo. vo) E D and > Ti (11)
+ Aw,t & (1-11 + (1- 48 ))
32
(1-
(er vh) & 2nT
where the first inequality holds from A Aws, and the second inequality holds by Eqs. (7) and (8). Step 4: initialization falls into D with constant probability. Let Po Pr[(wo: th) D] for simplicity. From 40 2(00, x x/2), the requirement
[0, T/2] is satisfied. Denote by p(w) the
probability density function N (0, I2). Then one has
R
pn Pr]]|wo w/l R
p(w) dw p(B(v, R))
min p(w) wE (E,(
(12)
(wBB(v,
16
Let R² = 1/2.. We obtain from Eqs. (11) and (12) that
Pr Lur, v/r) < 1
8000
+ (1
17
++ 141-32/n
48
32
which completes the proof.
B.1 Optimization Behaviors
The following two lemmas indicate the linear convergence of in D1 and D2, respectively, Lemma 9. Let w' w V u Leer (ew, vb). If (w, vb) E Dj and E (0, 4), then we have
1/00 wll < (1
" (sin(2 + 26² ||w - -oll
4m
Proof. For any (w, s/) E D1, one has
1
1 (2in(22)) + 260] - w/|2
(ew v), w v)
(sin(2rb) 20/ - v), w 00)
4T
4m
Meanwhile,
V Ler (w, 16)12 (4x))²
isin (2in(2())) - 2 2
Then according Lemma 13 and vb E [0, 1/2,, for any 17 E (0, 4), one has
(in)(2 + 2 ||w 1/1 1ww' - w|l < (1 4
which completes the proof. Lemma 10. Let wn
V Lerr(,, (w,, (w,, vb) E D2 and 17 E (0, (/2mm), then we have
||w' - 0|| < (1 24
17
[sin (2
(2x) + 2401 ||00 1uo-100 w||
Proof. Firstly, we prove the strong convexity in D2. For any (me, v) E D2, one has 2x ( w Tegy (w. 1b)), v)
1 sin (20) + 2う 0)
Wi Wu2
: + w (w) 1) [sin(2 245 wi ( - 1)
2
(13)
1
w
c2s(2
|22) + (sip(2 + 2
2
w + w
(2 + 2 w
0/
R1 - R2
where
R1
(MT - + - 0) sin(2
(wi - 1) and
Rg =
1 cos(2
W1
W2
2
2
w + w
17

---

According to Lemmas 15 and 16, Eq. (13) can be bounded by
1
1
1
(W, v) w w) >
sin (2 +2pp] w 1 >
[2in(2 + + w w---l 0012.
2T
2
12T
(14)
Secondly, we provide an upper bound of gradient in D2. For any (w, v) E D2. the gradient satisfies
4m 2
V We
)² = Ti + T22
where
w1 |22|
2
T1 (2i)(2 + 24/ w1
sin(2
+ 3h - 8)
2
2 + w2
T2 ((2 cos (21) (2)6
1 +
w
sgn(w3g (22) + (2()) + 200/
2
w
w
From Lemmas 17 and 18, one knows
(2 + 2x0] 0112 Wer +
(15)
Finally, based on Eqs. (14) and (15) and Lemma 13, conclude
||w w/ll /1
1-- Gt -
m(s)n(2
20]l| vll < (1-
17
(sin(2 + +2(8) 11 v11
24
where the first inequality holds based on Thus, we have completed the proof.
x/2 for any [0, and 1/ E (0,1/(127))
The following two lemmas depict the gradient with respect to & in D1 and D2, respectively.
Lemma 11. Let v/ vb- - V Ler (,W,)) v/). If (w, vb) E D2, then
1 π
1 - R2
2 vb) v V. 16)
1/
4x
2
Proof. For any (w, )b) E Dj. one has
1 (20)) + 1](1 1|0 -010))1))
(w, vt)
2T
For any 1o E [0, (0,./2), we have ( 1//2 & c0s(2 + 1 < 2(TT/2 2 Meanwhile, one has 0 < [w vl R. Thus, the gradient with respect a can be bounded by
1 (
1- R
Vw 16)
π
4x
which completes the proof of the lower bound.
Lemma 12. If (w, v E D2, then
-2 -2( -2) ) - 2 - Wel < Le (w, 2)) < 1 -
- 26
R²
π
1b
2
2
Proof. The gradient of Ler with respect to v in D2 can be calculated by
2n V y (W, v)) = [1 + cos(2 w/ - [] + cos (2t²) wi + [1+ + cos(2 sin(2 (16)
= [1 + c2 [|]
u/| 1] + [1 + cos(2 sin(2
Firstly, we prove the upper bound for Ve w. )) It is observed that
[1 + cos(2 sin (2x)) |u2 < 2 cos (wn sin 0 - |wz|| cos 0) 0,
where the first inequality holds based on x 7/2 > v > ग 7 - 0 > 0, and the first equality holds from w1 r cos 0 and
[wy| = riin 0. Substituting Eq. (24) into Eq. (16), we obtain
R2
2x V L (w. 3)) < [1 cos(2
w|| 1 <
1/
18

---

where the second inequality holds according to 1 + cos(2 (x/2 x)) for any ib E [0, x/2]
and || 2 < R.
Secondly, we verify the lower bound for V Tee (w, )²) It is observed that
V Lor (ow,rr, (w, vb) > - [1 + cos [2: - sin sin() [22l
2 v sin (2 W22
- v
+b
w22
2
( W1 > 0 and ||w - ||| 3 0, the second where the first inequality holds because of [1 + cos (26)
inequality holds according to 1 (2p() 2( )² and the third inequality holds based on sin(2)) < x 2 for v E [0, 7/2 Thus, we have completed the proof.
B.2
Convergence Rate Lemmas
The following lemma provides sufficient condition for linear convergence of gradient descent. Lemma 13. there exist two constants 01 and 02 such that
(V (V[(w), v) ei | vll² and [[ & c2llw -vl²
then w'= = 10 V ((w) with v E (0, 201/02) and c = / 20,7 + 0272 E (0, 1) satisfies l/w vll & clw - 1
Proof. It is observed that
1w - v/12 = 1 1/ (ww) - v1
= w v12 2n( V f (w) w - v) + + [(w)]
< (1 2017 + )2(1/)||u w 01
For 1) E (0, 2c1/e2), the coefficient 2c 0217² smaller than which completes the proof. 0
The following lemma gives a sufficient condition for convergence with an inversely proportional rate. Lemma 14. Let {ar C. [0, 1/2) represent real-valued sequence.
1. Ifo011 & ae 04), then a < 4I
2. Ifo:41 2 a.( (1 0z), then > F+I
Proof. We prove the first conclusion by mathematical induction.
1. Base case. For t = 0, the conclusion holds from ag & 1/2 &
2. Induction. Suppose that the conclusion holds for t = with & E N. Then it is observed that
-
1 k +
ac+1 & k+1
- 1 {
k k+2
where the first inequality holds from the induction hypothesis and the monotonicity of xx1 - x)) for [0, 1/2]. Thus, the conclusion holds for = k 1.
Therefore, mathematical induction completes the proof of the first conclusion.
We proceed verify the second conclusion by mathematical induction.
1. Base case, For = 0, the conclusion holds from ao > ag-
2. Induction. Suppose that the conclusion holds for L k with & N. Then has
0g
0g +++1
ag (k: 0o)
4o
a++1
k k+1
(k + 1)
k
where the first inequality holds from the induction hypothesis and the monotonicity of x(1 x) for [0, 1/2], and the second inequality holds based on < 1/2. Thus, the conclusion holds for l
Therefore, mathematical induction completes the proof.
19

---

B.3 Technical Lemmas
present upper bounds for some small terms used the proof.
Lemma 15. Let R1
[[2 v 8) 2 sin (2 (wi 1). If (ww, v) E D2, then
R1 E (sin( + 2 w11?
Proof. Let r / w + w denote the norm of w. Then according to the definition of 0, one has W1 cos 0 and [w2 r rin 0. Thus, we can rewrite Ri as
R1 ( v - sin sin() (r 0 1)
We provide the upper bound for R1 by discussion.
1. Suppose cos 0 1 > 0. Based on the definition of D2, we have & E [0, 7/2] indicates sin (26) > 0. Thus, one knows R1 & O.
1/ -0 < 0. Meanwhile,
2. Suppose cos 1 < 0. R1 be rewritten as
R1 = 2
(2n)) + (1 2r cos +r+)+ R.
(17)
where
1 R (iin())) + 200rr(cos 0 -r) +)+ (2 -
-0) (r cos 0 1).
2
If cos 0 - & 0, is observed that R & because of r/., E [0, π 1/2) and ros 0 <
COs 8 0, then
R < 2 r r) + - (r cos 0 - (πt 0) cos Or 0) f(r,,
where the inequality holds since sin(2 + 2 is monotonically increasing. The discriminant of f is
A = (N - 0 cos² π 20) < 772 0 -20)(20 - 3x),
where the first inequality holds since cos² 0 < 102/n² on [0, x x/2). According E T0, one knows (0) < O, which indicates ((r < 0, and thus, R < 0 when cos - r & 0. Combining the cases above, we obtain R < 0, which, together with Eq. (17), implies R < ((sin(2 + 21 - 2r cos 0 + +²).
Combining the cases above, knows
R (sin((2)) + 21 2r cos + +r? [?]= [sin (2t)) + 2 w s-wwwwa- - wl
2
which completes the proof.
Lemma 16. Let R2
1 1 cos(2
[22). If If +b) D2, then
u
tw
1 R2 & π
(2b))
24b 11|2.
Proof. Let r /
[ Vwf W1 = r cos 0 and [w2 = r sin 0. Thus, we can rewrite R2 as
w denote the norm of w. Then according to the definition of 6, one has
R₂ 1 cos(2 cos 0 sin 0.
We provide the upper bound for R2 by discussion.
1. Suppose 5 cos(2 cos 0 & 0. From 0 E [0, 1/2], we have R2 < 0.
20

---

2. Suppose [ cos(2 - cos > O. It is observed that r < 2 cos & since w|w - o0 holds from the definition of D2. Thus, the supposition indicates cos 9 ÿ - cos( <
[1 cos(22))) (2)) cos 0, which, together with 0 E [0, π. //2], implies v > n/4. It is observed that
1 (1 2r cos 0 +2) - (r cos 0) sin 0 = 2(r cos 0 - -sin 0)² > 0,
f(r)
which indicates
[sin(2 + 21 2r cos 9 + +2) 3 2(1 2r cos 1 + 1²) > (r cos 0) sin A > R2 π
where the first inequality holds from & > 1/44 and the third inequality holds because of (2)(24)) 2 1.
Combining the cases above, we obtain
R2 (sin(2 + 21 cos +r²)= 1 (sin(2 + 2 =11².
which completes the proof.
Lemma 17. Let Ti
((sin(2 + 21//w1 1 sin(2 ( + vb
wy _y/ wal wi u
2 If (w, v/)
D2, then we have
Ti < 7m (2.)) + 2 w - 2012
Proof. It is observed that Ti = [ssin (2b) + 2w0 1) + Tii + Tia with
1 Th sin((2)) + 2b + + and Ti2
wi [22 w + w
(18)
2
Firstly, denote by ro E (0, a parameter determined later and we calculate an upper bound for Ti by discussion.
1. Suppose w/ 1| + [w/] Then one has
1 Tnl sin 22b) + + <
1
Isin (2 - 2 - 1| + +|2l]]
2
2ro
where the first inequality holds from <
2. Suppose w1
+ W2l ru- Then observed that w1 > 1 ru + [22 Thus,
w + u v(L ro) + w2 ( [W2]
+ ro)
ro
where the second inequality holds because of ro < Then we can bound W2/ from below as
1- 1-re 0,
|w2| sin 0 (1 ro) sin
(19)
2
where the second inequality holds since < s 0 for all 0 E |0, r/2). Meanwhile, we bound 0 from above as
W2l
ro |w2]
-1
1- ro +
< tan
+
ru
(20)
To
where the second inequality holds from > ro + |wa) and the third inequality holds based on |Wzl & ro- Then we obtain an upper bound of Tı1 as follows
2 W22l
4 W
Thi 0
<
< (1 (1- rT) 2no)
+20i|lu htt/://-1///eee |wz/]
1 TO
(1 ro) 2ro)
where the first inequality holds from the monotonicity of 1 (2 + + and s < n the second inequality holds from Eq. (19), and the third inequality holds based on > z and Eq. (20).
2.
21

---

Combining the cases above, we have proven
1
2
Tui & max
2ro (1-ro)(T 2ro) (sin(2eb) 20i][wu 1 + |wy]]
Choosing ro 4 7 +
v pi?² + 4T + 36
we obtain an upper bound of Tn as follows
3
Tu
sin (2)) + 2 +
(21)
2
Secondly, we provide upper bound for T12. We claim and prove by discussion that
< 2
wî + ug([wr - 1| |w2]).
(22)
1. Suppose < 1/2. Then it is observed that |wj - 1 > 1/2, which implies
|22l < V w + w $ V w + w 2 W1 - 1 < 2 w + w6(1 - 1 + (w2l)
2. Suppose w1 1/2. Then one has /wf
w
1/2, which indicates
w2 [w
1|
+
|w2|
< 2 w + w [w] 1| + |w2l)
From the definition D2, one has
2
2 v
2
0 د 0, which indicates
sin w sin ( 0)
W1
cos 0
(23)
| w
Then obtain upper bound of |Tia| as
2w1
Tial
(lw1 - w//) < [/////11|+[urg
<
(24)
Vui
where the first inequality holds according to Eq. (22), and the second inequality holds based on Eq. (23). Finally, combining Eqs. (21) and (24), we conclude
Ti & [[()) (w 1) max [Tal)) < (m(s
2 w 0/|2
where the first inequality holds based on Th: 0 and T12 O, and the second inequality holds because of (2n)) + 2 & ग for any vb E [0, m/2]. Thus, we have completed the proof.
Lemma 18. Let T2 = (1 cos(2e)) - 1/2 +
+ sgn(w (w2) + [sin(2 + 2w0]us) If (w, v) e
."?
2
D2, then have
T2 & 7m (sin (2+b) 2 1 0/|2
Proof. From cos w1/ Thus, we have
V
/ + w one has COS(TT 20) = -1 2 cos 0 = 1- 1- wz)
1 2
1 = c2s(22)) cos(IT 20) <
cos((2))
sgn(w>)
< TTI
7 + w
where the first inequality holds because of cos a cos bl based the definition of Ti in Eq. (18) and (2x)) Eq. (21), we obtain
< laa - b). and the second inequality holds 0. Recalling the upper bound of Tú in
Th < ( (20))
=i w + w
2
2 +
sgn(wz) w2) + [[s)n(2*) + 2xh w2
< 7x (2 2 w 11
which completes the proof.
22

---

C Proof of Theorem 2
In the main part this section, we present the closed form of the loss, definition and properties of the ideal region, and the detailed proof of Theorem 2. Subsection C.1 provides the optimization behaviors. Subsection C.2 gives some convergence rate lemmas.
According to Lemma 8, the expected square loss Les can be calculated by
1 B(O, u, Vo, (25) Teee (un, 1/w) B(w, w, they Vho) B(w, v, Mhe 1h) 2
For R E (0, 1), 1i E [0, di], and via E [T/2 8us 1/2). define
D1 {(w, (ww) ||w 0
R, 2/w [1,, Vul. ww [0, 1v-w voll
D2 = {ww, viw) ||l - 21 $ R, v/w E [hi, Vul. Aeoo E (1ihw Vol. the + v/,)}
Let D D1 D2 indicate the ideal region, i.c.,
D {(w, (/w) w 2/100 & R. the [ab,, thul, Ow. E 1/, V/ + dbll
By spherical symmetry, we assume v (1.0) without loss of generality in the rest proof. For conciseness, define 8w sin() + 2 and Se sin(2 + 2 The following lemma discusses the properties of the ideal region, concerning the closeness of the region under gradient descent and the probability that an initialization falls into this region.
Lemma 19.
Let the
E [7T/20, 2 2 /5]. If choose the parameters
109
109 Rt and 0< 1 E
1
R
1 = v.
R
Vi = tb +
R,
25
100
100
120
then all conditions in Lemmas 20-25 are sutisfied. Ifwn (0, 12) and tha. ~ 21 π 22, then
Pr [(wo, (w.o) E D 10-3
Proof. We first prove that all conditions in the lemmas are satisfied.
Lemma 20. It observed that the first condition holds from
1 1
n
R
25 2.
120
120
According via t/e 7/4, have 1h sin())).) < thi (2nh))) which implies
3u
7xs,/20
Su
> (1 R)s, > (1 R)sw
Va v. + 109R/10R 100 7x/20 109 100
where the fourth inequality holds since is monotonic. Thus, the second condition is satisfied.
Lemma 21. The first condition 17 has been satisfied above. It observed that v4 > 7T 109 R/000. Thus, The second condition holds from th /2/200 The third condition holds since
20 > 700000- 109R0/0000 > R.
109R
5R
max max Ve, th v/)
100
Lemma 22. The only condition // < 2 has been satisfied.
Lemma 23. The first condition holds because of R = 1/25 < 1/2. The second condition holds based on cos? v > cosT(2n7/ > 1/25. The third condition holds from v) R//200 3/t22. Lemma 24. The first condition < 1/2 has been satisfied above. The second and third conditions hold because of
π min minfth. We, vh v/) =
π 109R
120 ワ
3
3 100
Lemma 25, The first condition R < 1/2 has been satisfied above. The second one holds from
101R
3R
109R
arcsin R 9n
+
vh 1
100
40
100
23

---

We then prove the second conclusion. Let = Pr[(wo, Vu.o) E D] for simplicity. Then we have
Po = Pr(y/ & Vu.0 & Mu]
Pr[1
R v w1 E 1 + R) Pr[- & w2 & R
109R
er R) - er R) crf R))
50
10-5
where (r) denotes the error function. Thus, we have completed the proof.
We are now ready to prove Theorem 2.
Proof of Theorem 2. Let R, 12 and aha be the same those in Lemma 19. Suppose that (wo, vw) E D. Then Lemma 19 implies (wi, Uw,e) E D for any t E N. The proof of con- vergence is divided into several stages.
Step 1: U22 converges to In stage I, we consider the convergence of w2, when (wo, 10,0)) E D. From Lemmas 22 and 23, the optimization behaviors of w2 is the combination of minimizing a contraction mapping or an almost absolute functiio. Thus, Lemma 26 with Tı = r2 R. C3 s (2T), gI (cos² v v2R)/(2:)))) and 9v. 2/3 implies
[22 < EEcoss d/ 22)
for LENT
(26)
4Tect
4Tc
Step 2: the converges to uh... In stage II, we prove the convergence of wau, when (uD,, P...0) E D. From Lemmas 24 and 25, the convergence of the is limited by that of W2. i.e., the tends to the global minimum with constant-order gradient when the error of the is larger than that of w2. while becomes far away from the global minimum otherwise. Then Lemma 27 with ri = 72 = 109R2/100
a = e2 (coss v. (2R)/(4TTO)) 9I = cos² //// (4T), and gu indicates
(cos v/ 22R)
10c2 ctt
+ 902
<
for tEN+
(27)
4Tc1
Step 3: wi converges to 1. In stage III, we investigate the convergence of w1, when (wo, vu..o) E D. From Lemmas 20 and 21, the gradient points to the global minimum with a remainder controlled by the error of and vhn- Then Lemma 28 with di = 1/4, du 1/2, and e 20r2/ (Tr))(rr)))))))) leads to
20c Ti
[w
for LENT.
(28)
Step 3: the expected loss converges to O. We now estimate the convergence of the expected square loss when (wo, vw.0) E D. For any (w, whw E D, define non-negative quantities Aw = || - v and Av lt/w vol. We provide upper bound for Lee by discussion.
1. Suppose (w, vnn) E Dj. Then we have
4 Tece(1, (w, whw) = | 2 sw - 2/ w ||||||||| cos pm + ||00|2
< | + SS) 2||2|||| - A (s SA) 1|0|/3
< 4([[w] 12 2|| a A + (s. + 2/(w ||/l||))))
< 324 + 822
where the first inequality holds from 8w < 8D + Sa, cos uw. > V A >
A2 and
u ||//||-
Sm 3 Sy SA with SA 2 s2n() ), the second inequality holds since and SA & 4Ag, and the third inequality holds based on ||w|| < 2 and sy & π.
||
A
2. Suppose (w, 1/n E D2, Let 0. Then one knows
4x Trce (w, thw) = ||a0|| 2 up
||m||28
|| ||| [2( + th 0) cos 0 + sin 0) + sin 0))
|| + (||wa| |w||||>|| cos () s.)
w
+ ||/|| ||| cos + 2| w ||| s, cos 0).
24

---

Then according to |||w|| - ||l||| < Aw. cos
& 4A. 0 & aresin Aw < 2A and
A w we have
4 Lec < 4 <||||w|2
||||||||||||| cos A. + 2//20|||00|| cos 0Aw. + (1 1 2//
< 1 + 5
where the second inequality hodls based on ||u/|| < 2, 8v & n. and A & <2R 22/25.
Combining the cases above, one knows from Aw 5/8 that for any (w, vw) D, the loss satisfies
Lee (w,, v. < 32 + 5
Then based on (w,, v)r,)) D and Eqs. (26)-(28), we obtain from C2 > 1 that
320c2
5c3
100c]
400c2
Lee Pu,e)
ett
4re
Te₁t
cit
which holds with probability at least 10-5 from Lemma 19. Thus, we have completed the proof.
C.1
Optimization behaviors
The following two lemmas consider the gradient with respect to wi in Dj and D2, respectively.
Lemma 20. Let w1 = w1 V1/V Lee thw) with (w, viw) E Dr. Ifnn E (0, 2) and (1 - R)s E Sp. then have
Sw (w' 1) +
1 Isw min Su3l and |ul - 1 R.
V wy Lec(w (. 2/w)
2
2x
Proof. For any (w, thw) D1, has
8w (wi 1) r 8w [w] min (Sws su]]
V my Lce (w, 1/
(29)
2x
2
where r denotes a remainder defined by r
1
[ww minf 8an 8. Then Eq. (29) implies
2n
1 1| w |m 1| |r|| (1
17
R +
[sw
min Sws sv
(30)
2T
2n
where the first inequality holds from the triangle inequality, and the second inequality holds based 1 / >> 0 and [w] 11 < R. We proceed to complete the proof by discussion.
Suppose that min (Sw; 80) = 8t. Then Eq. (30) implies
|w/ 1 &
178m
R
R,
2x
where the second inequality holds from > and 8 >
Suppose that min 8 S.- Then one knows from Eq. (30) that
175w
77 sw)
<
R+
R
2x
2T
where the second inequality holds because of (1 - R)s & 8c.
Combining the cases above completes the proof.
Lemma 21. Let Wi W1 17 wi LLe(ww vw) with (w, vw) E Dz. Ifn E (0,2), R < 21/20 and
max(u, (vh - -Vu th {1} < 5Rt /3, then we have
Vwy (w,, vho) = Sw Ow. (wi - 1)+ [(sw - +2 0m. aw and |wi - 1| < R.
2x
4T
Proof. For any (w, wiw) E D2, the gradient Lee with respect to wi can be calculated by
Se Om,
1
Sw O0e (w) 1) +r.
Vun Loe
(w) 1) + 4
[s.,. S.)) + 2(0mm. sin pm. ]
2T
2t
25

---

where denotes remainder defined by r = [(s - -8a) + 2(w -in uw (4..). Then we have
|w1 - 11 < 1 [m ww |w] 11 + |mrl < R RR+1 1) |r|| R8(s - Ow
(31)
2x
2T
where the first inequality holds from the triangle inequality, and the second inequality holds based on nssw 0w,
178w & 2T and w1 1 E R. It observed that
7
7 2
8:0 Om, v
2 1/2 Own
2R,
(32)
where the first inequality holds based on sw 3> 2411 + (in() and sin 2b > 3th 4 for di < 7/4, and the second inequality holds from u & aresin R & 2R. Meanwhile, one has
max (va Wes vo - v/
2
||| where the first inequality holds from the triangle inequality, and the second incquality holds according the 4-Lipschitzness of 20 + sin(20), 0 sin / for any 0 > and Own & 2R. Substituting Eqs. (32) and (33) into Eq. (31), we obtain
Sw sol +
1w..
sin 6 ww
(33)
4m
2T
3x
| - < R
+
[12 ma2 1b du - 211 + SR + 12R 21 E R,
12x
where the second inequality holds from max(Va. th the vr < 5 5 /3 and R < 1/ /2 & 1. Thus, have completed the proof.
The following two lemmas focus on the gradient with respect to W2 in Dj and D2, respectively.
Lemma 22. Let u2y u2 V/ we Lee tiw) with (w, thw E D1. 1f E (0, 2). then we have
Juusl <
178w
|wz| and | & R.
2
Proof. For any (w, vh)) D1, one has V w2 Loe (w, thw)
223 2
Thus, we have
w/ = (1
178mm
W2
(34)
2n
According to sw E [0, x and E (0, 2), the coefficient - n/ (2T) is positive and smaller than 1. Based on (w, viw) E Dj, one knows |w2| < R. Then Eq. (34) implies
(1-
77
wwl & R,
2T
which completes the proof.
Lemma 23. Let w/y W2 - V Loo(w (w,, vnd with (w, 2nd E Dz. If & 1/2, V2R < cos? Uin
and r & 3R/2, then we have
cos² v. V2R
2 3
w. Lw vhe )sgn(w))
and |w'l < R.
2π
Proof. For any (w, whw) D2, the gradient of Lee with respect to wa can be calculated by
V Wow vm))
2T 8mn w2 +
1
cos((2)v)) + cos(2
2w sgu(w2). (35)
4m
/wf + w
Since (w, thw) D2, one knows that [w) 1/ R and |022|
& R. Thus, have
2(1 R)2
2w?
2(1 V2R) <
< 2(11
v(1 R)² R
/ + E
where the first inequality holds because of R E [0, 1/2). Then we have
2w
cos(2 + cos(2 +
< 1 cos 2(1 + Rt) < 5,
(36)
/ Vu3 w
26

---

where the second inequality holds based on R < 1/2. Meanwhile, one has
2
cos(2 + (2)()
cos +2(11 - v2R) 2(coss vo V2R). (37)
V Vwf w2
It is observed that 0 & sw [uzl & 2 since Sw E 10 and [022 < R and (37) into Eq. (35), we obtain
<
1/4
Then substituting Eqs. (36)
cos² dh
V2R
1
5
2 3
V any (w, 2e )sgn(w2)
<
<
2m
4π
Thus, one knows from Eq. (35) that
| = |,2 V Troe(tu (w, vhe (agg))gg)))) < max (ww2l, VV W2 [we, v )sgn((()))) < R,
where the first inequality holds from la bl & max(a, b) for non-negative numbers and b, and the second inequality holds based on |22| < R and < 3R/2. Thus, we have completed the proof. O
The following two lemmas investigate the gradient with respect to the in DI and D2, respectively.
Lemma 24. Let Vi = 20m - V the (wD, vhr) with (w, ww) E D1. If R < 1/2, n < T( //)/3.
and 1) & (1/ //3 then we have
cos² Vh
3 π
V.) V th Lee the & < sgn(#h
and Vh E [1/,, thu)
4m
Proof. For any (w, wh) D1, the gradient of Lee with respect to d/u can be calculated by
Ver Loo (w viw) = {
-|w wil?], I [I + cos 2 }|| w/
2x | + (2 [1
ahe < the Wn > th
2x
where the gradient at vi = the can be any subgradient. For any (w, th) E D2, we have the E [1t, w'l, which indicates 2 cos" thu, < + cos(2
< 2. Meanwhile, all points in D2 satisfies (1+ R)2 Rº. Thus, the gradient of Lee
1- 1-2R 1- - w 0/|2 < and (1 R)) < w
with respect to the can be bounded by
cos? V/ & sgn( V. tie Lee (w,, vhw
3
π where the first and second inequalities holds based on R < 1/2. Then vin satisfies
V thet V/ sow Tree (w, vw) & max { then 1/.
31
thu
where the first inequality holds from discussing the relation between the and the, and the second inequality holds based on the < Vin and < Th v.)/3. Meanwhile, one has
31
Vie = the n V Tuceun, wwn) > min Vwr 1/v
> vhr
where the first inequality holds from discussing the relation between the and the and the second inequality holds based on the 2 t/t and n & ((, - v33 Thus, we have completed the proof. O
Lemma 25. Let Vi = thw V vie Loe (w, )w) with (w, vw) E D2. If & 1/2 and aresin R++9 <
vha V. then we have
2 (
vw) |wzl & V Loo < -hv
v.) ) and Vu E [17,, thul.
Vin)
4
Proof. For any (w, vh) E D1, the gradient of Lee with respect to vou can be calculated by
she Tree (w. thw) w 1 [1 + cos (2th
||/|||
[cos O o + cos (B 22/
2x
It is observed that the above expression is the same as the gradient of Teer with respect to sb in Eq. (16). The only difference comes from the domain of ur which is ||w 01 & R in Lemma 12 and
w ol/oo < R here. Then according to ||ж||| < 22 lloo in IR2, one knows from Lemma 12 that
-2
2
( v'm))
|w22
V thu Lon (w. voo) < 1-1
27

---

where the first inequality holds according to |T/2 - V/ll & 2/2 and p22p & 1, and the third inequality holds based on R. & 1/2. Then Vi,, satisfies
V < tw + 9y & eh + i0 + 97 & tia
where the second inequality holds from the condition ow 3 We the in the definition of D2, and the third inequality holds according
uw,v aresin R & t/ Vh 9r)
Meanwhile, it is observed that the gradient is always negative, which implies V/a 7 the 2 th. Thus, we have completed the proof.
C.2 Convergence Rate Lemmas
This section presents some sufficient conditions for convergence with an inversely proportional rate.
Lemma 26. Let f K + R represent a function with global minimum x", where K C R indicates the convex domain satisfying B(x", .11) C K B(x" .22) Suppose that there exist constants C1, c3, Mt, Iu such that & rr/9u and for any E K, at least one of the following holds.
1. | x-'-x=1= & (1 (1--c30 (1-can)]2 - x=1 and (a' - x²) x²)(x= - xx) 2 with = x - = f(x) and n E (0,ci]-
2. 91 & sgn(x x- x² V fz) & 9u for any # x² and [f(')) & 9u.
Then for any 02 > max max (1/03, 2r2/ / Mt 2019u/ 2019u/g1), the sequence { generated by gradient descent I++1 Zt - n f with xo K and nt- min(c1, c2/t] satisfies
with 2.
a <
I4 E K
and
x
2c1
Proof. Firstly, we prove n, E K. Suppose di E K for = We prove TR+1 K by discussion.
1. If the first condition holds, then I++1 is convex combination of o4 and x". Thus, Ik+1 E K.
2. If the second condition holds and sgu(#r411 - x²) = sgu( - x*), then x4+1 convex combination of Ię and x". Thus, 26+1 E K.
3. If the third condition holds and sgu(zx+1 x²) A sgn(1a - x²), then one knows from 7/ < Ci and [=x)) & Iu that [+++1 x=1 & c1 & ri, where the second inequality holds based on 61 & r1/ Thus, B(x", ((x",r1)= C leads to Fb+1 E K.
Combining the cases above, 2m K and mathematical induction completes the proof of xt K. Secondly, we prove |2 x=1 & a/t. Let to = c2/c1. According c2 > 2019a/9i > 201, one knows to > 2. For É < to, it is observed that
a a |x+ x²1 E
t
where the first inequality holds based K C B(x", r2). the second inequality holds because of a /201((2)) > r2to- Thus, the conclusion holds for any t < to. Suppose that [Ix - x"1 & a/k holds for k >> to 1. We then prove ( x=1 & a/(k 1) by discussion.
1. If the first condition holds, then we have
|z - x²1 & (1-020
C2Cs
a
a
k k+1
where the first inequality holds based on the first condition and the induction hypothesis, and the second inequality holds from 62 > 1/e3. Thus, the conclusion holds for t +
2. If the second condition holds and sgn ( - -r") = sgn(zk x"). then one knows
C29l
[
+1
where the first inequality holds from the induction hypothesis and the second condition, and the second inequality holds because of
a
C29l
a
a-
-2ggk
029) (lo/2 k) k(k + 1) < 0,
k
k+1
4:
+1
k(k+1)
28

---

where the first equality holds based on C2 > 1/c3, the second equality holds from the choice of and tg. and the first inequality holds from to > 2 and k 3 to to/ Thus, the conclusion holds for / = k 1.
x²) & sgn( x²). then it observed that 3. If the second condition holds and (*
C20u k
a
| x=1
<
k+
where the first inequality holds from the second condition, and the second inequality holds based //g// (2c)) 3 C29u- Thus, the conclusion holds for t +
Combining the cases above, we have completed the proof.
Lemma 27. Let J K R represent a function with global minimum x", where K C R indicates the convex domain satisfying B(x", rı) C K C B(x", Let {0r)r be positive sequence bounded by 0g & a/t. Suppose that there exist constants gts Iu such that for any K, the following holds
If p2 - x²1 1 8,, then 91 & ssgu(z Vf(() & 9u-
2. 1f [2 x=1 & Oc, then [[(x))) & gu-
Let c1 > 0, and C2 > max m 2222/9 gt. 201} Suppose that the sequence { generated by gradient
descent 2z+1 Z, T/ (x,,) with 2o K and 7 min(cr, 02/t] satisfies I, K for any I ee N+. Then the following holds for any E N+
22
It x²' E
with
max 2a 029u
2cr
Proof. Let ln = 2h/((22))
3 02/01 > 2. For any 0 <
1
<
lo, it is observed that
C2
b
|x x² <
<
2
in
Thus, the conclusion holds for 0 < Lp. Suppose that laTe x*1 & b/k holds for k: > 1. We then prove [ x=1 < b/(k + 1) by discussion.
If the first condition holds and sgn( xx) = sgn
sgg(gg (rk x²)
then we have
C291
| - x=1 < [ - x² mh+
k k+1'
where the second inequality holds from the induction hypothesis, and the third inequality holds based on b = c2gdl and 4o/2 < lo 1 < k. Thus, the conclusion holds for t= k
2. If the first condition holds and sgn (I++1 x²) A sgn(xx x²), then we have
C29a | - x11 & 7 <
b
&
k +
k k+1
which implics that the conclusion holds for t = le + 1.
3. If the second condition holds, then one knows
a
C2Iu
2x+1 xx"
< 2 x=
Mk+19u
k
k+1
k+1
where the second inequality holds based Ø++1 x=1 inequality holds because of
0 & a/(k + 1), and the third 2a + C29n. Thus, the conclusion holds for = k
Combining the cases above, we have completed the proof.
Lemma 28. Let f K + R represent a function with global minimum x", where K C R indicates the convex domain satisfying K C B(x". R). Let 100 denote the sequence generated by gradient descent Zt+1 = T)t V fxx) with Zo E K and Tnt min(ci, /t] satisfying Is K for t E N Suppose that the gradient satisfies V fz(x,) d(x, x²) + rt. where d, < d & d2 and Iral < e/t. & 1/d, and 02 2/d,, then we have
1xc x² < C
with = max c
C2E
29

---

Proof. Let to = 02/c1. We prove the conclusion by mathematical induction. Base case. For & to: it is observed that
1. x
R
to
Thus, the conclusion holds for 0 < & lo- 2. Induction. Suppose that [T x²1 < c/k holds for k 3 1. Then have
| x01 = [[1 drtx (z x²) 7 < (1 -mnx) [
x + n |m
where the first inequality holds based on dıp & cidx < 1. Then the induction hypothesis leads to
c
C2E
[+++1 - x²1 <
k
12
k+1
where the first inequality holds according to Cad: C 3 oze. Thus, the conclusion holds for k
> 2, and the second inequality holds based on
Therefore, mathematical induction completes the proof.
D Proof of Theorem 4
We begin the proof with two lemmas, For any non-zero vector a in IR² and 0 E [0, x]. define S(a, #) = {a R Oz E [0a 0, 0, 0}} as the sector region with central angle 20 that is symmetric with respect to a. Let Na, represent the truncated standard Gaussian distribution on S(a, f), of which the probability density function is
||
E S(a,0)
p(x) =
20
otherwise.
The following lemma provides lower bound for the expected squared inner product on S(a, 0).
Lemma 29. Let d = 1. For any w E Rdd, non-zero a E RRdd, and 0 E x/2), we have
0 ||w||
E [w x))
Proof. Let Our indicate the phase of w, i.e., expectation in the polar coordinate system leads to
|| ow Oww). Then caleulating the
too
0a+0
Ea (10 [=]]
r cos sin Ow sin 20 2 dø dr
29 J
-0-8
(38)
|
l|
+ sin( c2ss220,.0) ww)
where the second equality holds based on integrating over r and & separately, and the identity cos(Oa Ow)) cos 0a,w. The expectation in Eq. (38) can be further bounded by
ExaNaa [(wo Txo)
||/0:|2
[(1
1 sin(20)
sin(20) cos² 00,
20
1
sin(20)
||/||
20
0
|
3
where the first inequality holds according to 8 E [0, 2/2], and the second inequality holds because of (1: & x 33 22/12 /22 for all 0 E [0, m/2. Thus, have completed the proof.
The following lemma provides a lower bound for expressing a complex-valued vector with four real-valued vectors under symmetric constant.
30

---

Lemma 30. Let Uy E Rd with & E [4] and v E R. vf + 02 = 02 + 24. then we have
oo I[k:: = 1)ll > ||a
Proof. According to the generalized mean inequality, one knows
2
Σ -- 1)1l > Ele, I[k 1 1)1l
1 -1 002 4 |0/1?
where the second inequality holds because of the triangle inequality, and the first equality holds based on the condition 01 + Vg + v4. Thus, we have completed the proof.
We are now ready prove Theorem 4. Proof of Theorem 4. We define vector un a 2-dimensional real-valued vector. Pw, = arctan (x,)) E (-3/, 2T e/) denote the phase wz; We assume 0, = without loss of generality. Denote by Ow the T/ /22-symmetrical phase set induced from W and i...
au x) for simplicity. From d 1, the weight
Ow
0mv;
[j - 1)TT i [ E [4] U isp
u
(j
(j-1)a 1)T
iE (- 11]
2
It is observed that there is an integer & n + 2 such that 10wl = 4m. We sort all phases in Ow as
θw
[0 with - 1 < O1 < < 4mm- 2x 1b
Let N3.u represent an arbitrary two-layer RVNN with weight phases from Ow, i.e.,
4m
Nauu(x=) Σ B.ruuTa x) with Ou, 0,
1=1
It is observed that NA,U degenerates to No. w with suitable parameters. Thus, the expected square loss Lie can be bounded as
Lac W) B inf BE...
1
(Na,u(x) ow ( (v)
2 3,U
1
inf
4m
A0,
BenNia,
- o (vt (w) (v)x))) xc
(39)
2
B.U
π
where 20; (0; 0/-1)/2 and a; (0:- with On 0s(n+1). The indices can be divided into
m groups as I; = {i (K- 1)m 1e E [4]] with i [m]. Denote by is the index of vi, i.e., O.p = sb.
Then Eq. (39) becomes
aa W) > inf
A
Ex-N(a, [Na.u(z) (v((Tx=))
(
2
B.U
1=1
JEL.
(40)
A
inf B.U
Em-N(a, [(0,- 1(j & is)) x)) ?]
where the first inequality holds since A0, remains the same in I,, the second inequality holds based on the activation regions of ReL.U and zReLU, and the definition of uy follows
j 11-1
+ 4m
L 0
Vj
Σ
Beuy u
with 2()) =
1
< 4m,
(41)
4m,
1> 4m.
i=j-m
Applying Lemma 29 to Eq. (40), we obtain
1
Ad,
(A
La, W)
inf
11,,
I(j < 1
2
RU
π
3
JET.
m)
(aO.) 4
1
inf
Σ
Di.k w T[Kk = 1)11a
2
B.U
3t
i=max [1.pg m
31

---

where the second inequality holds based on the definition of Di,k (b+((=-))x+))) and Ad; = A for any j E I, Based on Eq. (41), one has 11 + vi 2 + vi,4- Then Lemma 30 implies
min min
(a, W) >
inf A.U
Σ
(A,))²
4 11012
1
3m
(=max (1,6 m++1
min mi
||a11
Σ
A0;
24m [max (1, iv
m 1} min fin m))²
(=max
||aa min ( (2x), π 2
24 (n 2)
where the second inequality holds based on the generalized mean inequality, and the third one holds min
from 1, ig. m min (īp; m] & & 2. Thus, have completed the proof. L
E Proof of Theorem 6
We begin with lemma providing lower bound for convergence. Lemma 31. If there exists a constant e. such that
(V((w), w - v) cl/u0 w/12
then w' w f(W) with n e (0, 1/c)) satisfies
w|w' v > VI 2cn w wl
Proof. From the updating rule, it is observed that
1 v 1 >
w w/|2 2n/(w v, VS(())) > (1 22n)]| w -013
which completes the proof.
We then prove Theorem 6.
Proof of Theorem Denote by Rt = || - -oll. The convergence analysis consists of several stages.
Stage 1: the error of ei decreases below a threshold fast. By the same arguments as those in the proof of Theorem convergence of va in Eq. (7), we have t/ 2 π 7/4 when > [167
E (0, 1/1xx) indicates (w;, t/r) for any N. Recalling the 11. From Eq. (4), one
knows V Ter (w, v/() 2 6(1)* " v/e). Then have
(v TarTaruu, wh),, 10 - wh) 2 - 6(1b² - -222
Then we obtain from v E (0, 1/12) and Lemma 31 that
4/ - 2/ > (1- 12n) (1) w/0
(42)
Thus, one has
(1 1/2) vo) < 20" 1b 4
with t t> Ti 161 -' (1 RR
Step 2: both errors of and dh decrease below small constants fast. Based on Eq. (8), have
Iw el| <
48 for t> Ti.
(43)
which, together with Eqs. (7) and (42), implies that
1
(1 12n) 2/2 vo & v/"
w/a 384
and
|uzl < [w el
384
(44)
In 384
3200T
with t t> T3 = max
Ti +
In(1 + // /
77 - -
32

---

Step 3: w converges faster than v. For any t > T2, Lemmas 11 and 12 imply
1
(V vereerw (wi; 1/,, 1/ *²* 2(10" 1h,)²² + 2(18* +))) 2 lw2.cl
1//)2
96
where the second inequality holds based on Eq. (44). Then Lemma 31 indicates
vt+1 v 7/48(11"
vh)) for > T2
which, together with Eq. (43), indicates
[w,,e < ||w; - wil < &0 2 with t T3 = 2f + To T2 12n) 2 211(11" v0)
(45)
In(1 - 77/48)
Step 4: s converges with an inversely proportional rate. For any t > Ts, it is observed from Lemmas 11, 12, and Eq. (45) that
V Ler We, 1/22 - 4(1b" 1/)2
Let a, 4n(b6= - v.)) Then the updating rule implies a++1 3 ar(1 - -a). Choosing 77 E (0,1/(47)) guarantees a, E 1/2]. Then Lemma 14 indicates
(1
127)) v0) for t t T3
(46)
t -- T3 +1
Step 5: the loss converges to with an inversely proportional rate. Define non-negative quantities Aw || w1| and A 2p* vh. We provide lower bound for Ter by discussion.
1. Suppose (w, vb E Dj. Then we have
1
1
1
(er(w, v)
(4
A
(1 A
A3
+
A2 (2 A
>
23 (47)
4
8T
8T
8T
8T
where the first inequality holds based on sin() +2 sin )) +
-2 266 A
for any vb E [0, 7/2], and the second inequality holds from As & 7/2.
2. Suppose (w, 4/) D2. The expected loss be rewritten
1
(w, 16)
(2in(2t)
+ 200 - A
4
4T
1
[[cos(2*) 1) W2l + (sin(2 2τ6 2w1
4m
1
1
(1t6*
1 (1 A 4
[coo((2t) 1) |22
(48)
8m
1
>
(4r6* - 21 AW)
2x Aw
4
8m
Aw
8
2T
where the first inequality holds from sin(2 +2 <
- 2 and sin(2))+2++20--2)
0, the second inequality holds based on cos(2t) - 1 > -2 and |w2l| & Aw.
Combining Eqs. (47) and (48), one knows that the following holds for any (wo, v/) E D and > T3
1--AA A..
(1 - (T-12))73/3(11 vh)
1
f-7s
Lor (ur, v+)
A3 2.1
8
2T
8m T3 1)3
2m
48
where the second inequality holds from Eqs. (43) and (46). Thus, we have completed the proof.
F Simulation Experiments
Experimental settings. A training set of size 7,000 and test set of size 3,000 are generated by randomly initialized target neuron (can be a real-valued or complex-valued neuron). After random initializatinn, complex-valued neuron and a real-valued neuron are trained by gradient descent with
33

---

the empirical mean square loss and a learning rate of 0.1 for 100 epochs (or 300 epochs when the loss does not converge).
Experimental results. It should be noticed that a complex-valued neuron cannot always learn a target neuron. From the theoretical formulation, convergence rate holds with small constant probability. From the loss landscape, there exist constant pieces in the parameter space, i.c., the complex-valle neuron does not learn anything after initialization. Thus, we cannot expect complex-valued neuron to learn a target neuron all the time. In the experiments, we train the complex-valus neuron with several random initializations and find that our theoretical conclusions oceur in experiments. This phenomenon verifies our theories and also motivates novel learning algorithm for CVNNs, as discussed in the conclusion part.
34


Reviews:
[{"review_id": "MBJyU7TNwH", "reviewer": "Reviewer_qTS2", "summary": "The theoretical paper compares the learnability of real-valued neurons and complex-valued neurons via gradient descent. In a nutshell, the paper proves that a complex-valued neuron has a lower convergence rate than its real-valued counterpart, but learn exponentially slower. The theoretical discoveries help explain the success of CVNNs and point out the potential slow convergence of CVNNs learning.", "questions": "1. It is argued in the paper that learning one neuron can embody the learning of neural networks. However, unlike RVNNs, multi-layered CVNNs may have intermediate layers with complex-valued input and outputs, a different setup from this study. Is it possible to employ a similar approach to this paper for studying these layers?\n\n2. The bias term is removed for technical reasons. Could you please elaborate on how the presence of bias term will influence the analysis, and whether similar findings can still be obtained?\n", "limitations": "The authors have adequately addressed the limitations of the work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper makes the first attempt ever to comparing the learnability of real-valued and complex-valued neurons on a theoretical level.\n\n2. Even though the theoretical investigations are carried out on a single neuron, the findings still cast light on the success and failure of CVNNs.\n\n3. The discoveries are presented as Theorems and proved with rigor in the appendix, in which I did not find any technical errors.\n\n4. The paper is very well written. The implications of each Theorem are clearly explained and summarized in tables.", "weaknesses": "1.  The analysis is carried out on a simple type of complex neuron network, and it is hard to generalize the achieved findings to practical RVNNs and CVNNs.\n\n2. The discoveries could be more convincing by comparing the learning curves of RVNN and CVNN on toy examples, e.g. to show that a real neuron cannot well learn a complex neuron.\n\n3. The research questions should be reformulated. Currently they are quite ambiguous and do not directly reflect the research focus.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and comments.\n\nQ1: About generalizing to practical RVNNs and CVNNs.\n\nA1: The analysis of neural networks faces the tradeoff between simple assumptions and strong conclusions in the neural network literature. It is quite difficult to analyze practical neural networks without assumptions. Our work pursues theoretical results under simple settings and assumptions. It would be promising future work to generalize our findings to deep neural networks without complicated assumptions.\n\nQ2: About toy examples to make the discoveries more convincing.\n\nA2: Thanks for the constructive comment. We believe that our findings are well supported by our theoretical conclusions. To provide a more convincing and intuitive demonstration of our discoveries, we provide experimental results in the **global response**, where we also verify our findings in the presence of bias terms.\n\nQ3: About reformulation of the research questions.\n\nA3: Thanks for your valuable feedback. The current formulation focuses on generality and includes the setting of learning a neuron with a two-layer neural network, which is used in Theorem 3. However, this generality might not directly reflect the research focus. We will formulate the problem in a more appropriate way in later versions.\n\nQ4: About studying intermediate layers in CVNNs.\n\nA4: Neuron learning focuses on the learning dynamics of neurons, which helps us understand the learning process of neural networks since a neuron is the simplest form of a neural network. This motivation is widely adopted in real-valued neuron learning [1,2,3] and benign overfitting [4]. To analyze deep CVNNs, the complex-valued intermediate layer is not the central problem since it can be modeled by distributions related to the real and imaginary parts. The fundamental difficulty is the dependence between parameters in different layers (i.e., we have to analyze the compositions of several random variables when studying neural networks), which also occurs in RVNNs. In the literature, these compositions are analyzed under different strong assumptions or highly over-parameterization [5,6,7].\n\n[1] Yuandong Tian. An analytical formula of population gradient for two-layered ReLU network and its applications in convergence and critical point analysis (ICML 2017).\n\n[2] Gilad Yehudai and Shamir Ohad. Learning a Single Neuron with Gradient Methods (COLT 2020).\n\n[3] Weihang Xu and Simon S. Du. Over-parameterization exponentially slows down gradient descent for learning a single neuron (COLT 2023).\n\n[4] Spencer Frei, Niladri S. Chatterji, and Peter L. Bartlett. Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data (COLT 2022).\n\n[5] Alexandr Andoni et al. Learning Polynomials with Neural Networks (ICML 2014).\n\n[6] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A Convergence Theory for Deep Learning via Over-Parameterization (ICML 2019).\n\n[7] Kwangjun Ahn, Jingzhao Zhang, and Suvrit Sra. Understanding the Unstable Convergence of Gradient Descent (ICML 2022).\n\nQ5: About the influence of the bias term.\n\nA5: This is an important question. From the theoretical aspect, although many efforts are devoted to simplifying assumptions, the bias term is still difficult to cope with and is set as 0 in the literature [1,2,3]. The bias term will change the analytical property of the loss function and make the closed-form expression unavailable, which makes our analysis infeasible. It is possible to analyze neuron learning without closed-form losses [2], but this method relies on \"spread\" input distributions (Assumption 4.1). If the bias term is considered, i.e., the original input concatenated with an additional \"1'', the additional \"1'' makes the input distribution discrete and not spread. Thus, the analysis of the bias term is still an open problem and is beyond the scope of this paper. From the experimental aspect, we verify our findings in the presence of bias terms (Fig. 2 in the **global response**)."}, {"review_id": "a3NnyqG4yu", "reviewer": "Reviewer_Jsv8", "summary": "The paper develops theoretical results for the convergence rates of complex and real valued neural networks on complex-valued problems. It develops analytical models for the training regimes of complex valued NNs. ", "questions": "- In Section 4.3, could you clarify how the outputs of the RVNN are matched to the outputs of the complex valued target function?\n- In Section 5, does the trainable zReLU make the network effectively deeper? Does the convergence rate change if psi is not trainable?\n- Define the schema of $L_{rr}, L_{cr},$ etc., and remind the reader every time you use them. By the time I got to Lemma 4 and Lemma 5, I did not know which result was which.\n- $t4 was never defined.\n- Define rvnn and cvnn in the abstract\n- Add equation numbers.\n", "limitations": "A limitations section is missing from the paper.\n", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "The results would be useful for those attempting to apply complex-valued networks to problem settings where they are not normally used. An intriguing result is that complex valued neurons have slower convergence rates for the same problems as real valued neurons. The theorems are thorough, and the diagrams provide excellent illustration to the proofs. They also provide a proof that real valued networks cannot learn complex valued functions, which is not surprising, but nice to have proved.\n", "weaknesses": "A fundamental flaw of the paper is that it does not have empirical verification of the theoretical results. The analysis makes many assumptions about different training regimes, but it is not obvious if complex valued neural networks actually behave like this. The complex-valued models in the theorems should be implemented and the convergence losses should be plotted alongside the theoretical predictions. Without supporting empirical evidence, the assumptions of the proof seem too strong. Fortunately, the problem settings should be simple to code up in any package, and the results would be easy to include in the author's presentation, given Figures 1 and 3.\n\nPage 4, line 156: “whereas a complex-valued neuron may only activate a small part as controlled by the parameter psi” This line makes it sound like the authors conclude that the primary benefit is the extra parameter in zReLU, not the complex arithmetic. The use of activation functions with trainable parameters is also a major distinction between the CVNN and the RVNN. Maybe all of the identified differences can come from a network with real weights, but an activation function with a learnable parameter? zReLU can be encoded in real-valued weights, if you interpret two real weights and use a learnable ReLU. Two variations are required to ablate this confounder:\n1. complex weights with a zReLU with a fixed psi (Would this be easier to study theoretically than the existing proofs? It would also be easy to demonstrate empirically.)\n2. real weights with a pseudo-zReLU with a learnable psi (Possibly hard to prove, but easy to empirically study.)\nI think considering case (1) is necessary to support the claim made by the paper that complex weights are the key differentiator.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed feedback but would like to point out a few misunderstandings in the review.\n\n1. About assumptions on different training regimes.\n\nIn the proofs and proof sketches, training regimes come from the idea of divide and conquer and we do not make any assumption about these regimes. We analyze the learning dynamics in each regime and then unify them to obtain the global dynamics. The introduction of training regimes implies complicated and challenging analysis rather than strong assumptions.\n\n2. About a missing section of limitations.\n\nWe discuss the limitations of this paper and promising future works in the second paragraph of Section 6. This is approved by Reviewer qTS2: The authors have adequately addressed the limitations of the work.\n\nQ1: About the fundamental flaw that we do not have empirical verification of the theoretical results.\n\nA1: It seems that the reviewer might not grasp the core contributions of this paper. As far as we know, this paper theoretically studies neuron learning in the complex domain for the first time, and the obtained theorems cast light on the difference between RVNNs and CVNNs. From the theoretical aspects, all theorems are clearly written and have detailed proofs in the appendix. Thus, our theoretical results are rigorous and sound, as estimated and mentioned by all other reviewers. From the experimental aspect, we admit (as suggested by other reviewers) that empirical results can further strengthen our sound theories and verify our findings in more general settings. Thus, we provide experimental results in the **global response**, where we verify our findings in more general scenarios.\n\nQ2: Can the difference come from RVNNs using activations with a learnable parameter?\n\nA2: Thanks for this important question. In a nutshell, the difference comes from both the learnable parameter and the complex arithmetic. Firstly, the learnable parameter is related to phase learning. With a fixed $\\psi$, the phase prior is determined, which may cause disappointing results when the prior is unsuitable. Thus, the learnable parameter is essential for phase learning. Secondly, complex arithmetic is the basis of phase and a natural way of modeling phase information. Complex arithmetic is the basis of phase since phase does not exist in the real domain. One may argue that $C$ is isomorphic to $R^2$ (as real vector spaces), and a complex number can be modeled by two real numbers. We admit this fact but the modeling process is highly artificial. In the words of neural networks, the multiplication from $C$ to $C$ can be modeled by a complex-valued weight (2 parameters), or a 2*2 real-valued weight matrix (4 parameters). Moreover, typical activation functions used in CVNNs can be succinctly expressed by complex numbers and their arguments, while having a more complicated formulation when expressed by real and imaginary parts. Finally, it seems that the reviewer misunderstands our conclusions. Our conclusions are about complex-valued neurons rather than complex-valued weights. We never say complex-valued weights are the key differentiator. It is important to consider both the complex-valued weights and complex activation functions.\n\nQ3: How the outputs of the RVNN are matched to those of the complex-valued target function in Section 4.3?\n\nA3: Thank you for raising this question. In the literature, it is common to take the real part as the output in the readout layer [1,2]. In this paper, we adopt this choice. The activation function $\\sigma_{\\psi}$ contains the operation of taking the real part, as defined in Section 3. Thus, the outputs of both RVNN and CVNN are real-valued, and there is no trouble in matching the outputs. We realize that readers may forget the definition and we will add more explanations in later versions.\n\n[1] Scott Wisdom et al. Full-capacity unitary recurrent neural networks (NIPS 2016).\n\n[2] Shao-Qun Zhang, Wei Gao, and Zhi-Hua Zhou. Towards understanding theoretical advantages of complex-reaction networks (Neural Networks, 2022).\n\nQ4: Does trainable zReLU make networks deeper?\n\nA4: It is hard to measure the relation between the trainable parameter and network depth in general since the trainable parameter may have different influences on different theoretical properties. From the approximation aspect, the approximation power roughly comes from depth, width, and activation complexity [3]. The role of the trainable parameter in zReLU belongs to activation complexity and cannot be compared with depth since the effects of depth and activation complexity are incomparable. From the learning dynamics aspect which is considered in this paper, there is no proven conclusion about the effects of activation complexity and depth. We conjecture that activation complexity and depth are incomparable since a complex-valued neuron cannot represent a two-layer real-valued neural network (which can be proved by simply counting the number of linear regions).\n\n[3] Alexis Goujon, Arian Etemadi, and Michael Unser. The Role of Depth, Width, and Activation Complexity in the Number of Linear Regions of Neural Networks (2022).\n\nQ5: Does the convergence rate change if psi is not trainable?\n\nA5: The convergence rate changes if $\\psi$ is not trainable since the redundant phase consideration slows down the convergence, as concluded in Section 6. The trainable parameter is important to learn phase information. With a fixed $\\psi$, the phase prior is determined, and we cannot expect a complex-valued neuron to learn phase information.\n\nQ6: About notations, abbreviations, and equation numbers.\n\nA6: Thanks for your valuable suggestions. Definitions of $L_{rr}$ and $L_{cr}$ are provided in Eq. (2) and at the beginning of section 5, respectively. We will recall the meanings of notations and update the abstract in later versions. We only add a number when the equation is cited elsewhere, which is a convention in the community of neural network theory."}, {"review_id": "T4MMzcQB6T", "reviewer": "Reviewer_cJ2H", "summary": "The authors contrast the learning and convergence properties of real-valued neural networks and complex-valued neural networks. Specifically, they study the problem of learning the function implemented by a single neuron using a 2-layer finite width network. Notably, they show that a complex valued neural network can learn functions expressed by a real-valued neuron as well as a complex-valued neuron. This result indicates the superior capacity of complex-valued neural networks as compared to their real-valued counterparts. Furthermore, they also study the convergence properties of learning a function expressed by a real-valued neuron with a complex-valued neuron and prove that its slower compared to learning with a real-valued neural network. Taken together, complex-valued neural networks have a better learning capacity at the cost of slower learning properties compared to real-valued neural networks. Overall, I think this paper makes a strong theoretical contribution to understanding the efficiency and capacity of complex-values neural networks in practice.", "questions": "1. The caption of Fig. 2 is currently not very descriptive. Could you please update it such that the takeaway is clear to the reader without reading in detail the text?\n2. Is it possible to add a toy regression example where you can empirically demonstrate the different phases during the learning process?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper has strong theoretical foundations and presents arguments through rigorous proofs. \n2. Despite the involved mathematical machinery, the authors present a simplified view of the underlying learning dynamics and present the existence of phases in the learning process. \n3. Despite the assumption of the MSE loss, I feel the authors present a strong theoretical framework to analyze learning in complex-valued neural networks and contrast them with real-valued neural networks.", "weaknesses": "1. The authors present strong theoretical results, and use specific assumptions to prove their results. However, it is unclear the extent to which these assumptions would hold in practice. \n2. In addition to their (very impressive) theoretical results, I feel the current version of the paper would benefit from some empirical validation. Having some toy experiments would also be sufficient to significantly improve the readability of the paper, while also increasing the reader pool. \n3. The manuscript is generally well-written, but there are certain typos or use of abbreviations/notations which make it confusing for the reader. E.g. it seems that there is a typo in Table 2, wherein the second row third column (complex-valued Neuron --> complex-valued neuron) should be $\\mathcal{O}(t^{-1})$. Also, abbreviations CVNN and RVNN or the notation $t$ is not introduced in the abstract.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for these constructive suggestions.\n\nA1: About the extent to which these assumptions would hold in practice.\n\nQ1: The settings and assumptions used in this paper are common ones [1,2,3,4] to make the analysis tractable. Neuron learning aims to provide meaningful insights for theoretical guarantees and practical usage of neural networks, based on simple settings and assumptions. We believe that such a work is significant and necessary for the development of neural networks' theory.\n\n[1] Yuandong Tian. An analytical formula of population gradient for two-layered ReLU network and its applications in convergence and critical point analysis (ICML 2017).\n\n[2] Mahdi Soltanolkotabi. Learning ReLUs via Gradient Descent (NeurIPS 2017).\n\n[3] Seyed Mohammadreza Mousavi Kalan, Mahdi Soltanolkotabi, and A. Salman Avestimehr. Fitting ReLUs via SGD and Quantized SGD (ISIT 2019).\n\n[4] Weihang Xu and Simon S. Du. Over-parameterization exponentially slows down gradient descent for learning a single neuron (COLT 2023).\n\nQ2: The paper would benefit from some empirical validation. Is it possible to empirically demonstrate the different phases during the learning process?\n\nA2: Thanks for this valuable feedback. We provide toy experiments in the **global response**, where we verify our findings in more general settings. For empirically demonstrating learning phases, it should be emphasized that these phases only work for proof but may not exist in practice. For example, the red line remains constant during stage II in Fig. 2(b), but this line is an upper bound and the practical line may be a smooth one through all stages. In part of our experiments, the loss curve has a constant segment, which implies that such phases may exist sometimes.\n\nQ3: About typos, use of abbreviations, the caption of Fig. 2, and $t$ in the abstract.\n\nA3: Thanks for pointing out these problems. We will update them in later versions."}, {"review_id": "OTaltoAeIF", "reviewer": "Reviewer_4m8w", "summary": "The goal is to explore the novel approach of complex valued neural networks using gradient descent. The paper investigates when and to what extent CVNNs outperform RVNNs using gradient descent for learning tasks. The researchers prove that a single complex-valued neuron can efficiently learn functions expressed by one real-valued neuron and those expressed by one complex-valued neuron, while a two-layer RVNN with finite width cannot learn a single complex-valued neuron. However, they also show that complex-valued neurons learn more slowly than real-valued neurons, with a lower bound of Ω(t−3) for learning functions expressed by one real-valued neuron using a complex-valued neuron. Theoretical comparisons between RVNNs and CVNNs provide insights into the success of CVNNs and the potential slow convergence of CVNNs learning.", "questions": "- Motivation of application - I’m surprised the authors do not mention more applications to systems in the world of physics. Fluid dynamics, beam physics, particle physics, where phase information is ubiquitously relevant to quantum materials, dynamics, and \n\n-States that the CVNNs have shown to have some desirable properties - universal approximation - boundedness, stability → why is this desirable? Could the authors elaborate on this? \n\n-  It is not clear to me, in Theorem 1 and theorem 2 when d=1, does this mean that x is now no longer a linear summation of inputs but truly just an input and the weight parameter? I did not work through the proof, but does the theorem generalize to inputs with more than one dimension? ", "limitations": "It often feels like one cannot truly understand what they are discussing in the paper without referencing the very dense and long appendix. ", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The authors appear to have thoroughly analysed a complex valued neural network and developed what appears to be rigorous theoretical results calculating the convergence rates of these complex valued neural networks. \n\nThe ideas appear to be sound ", "weaknesses": "- While the notation appears to be self-consistent (in the main body - I did not read the appendix, which is very long and technical), the notation is very hard to parse through. If there were some tables to layout the important notation it could help lay the groundwork earlier on.\n\n- I am not familiar with these types of reformulations, but it is not clear to me why the authors want to try to use a two layer network to model a single neuron. The authors write \"Although learning one neuron is the simplest case of learning neural networks, it is sufficient to embody the learning capability and efficiency of neural networks.\", which I ask the authors to motivate more. Is it not obvious a two layer network with more parameters would be able to model a single neuron of just the weighted inputs?\n\n- I am not sure I fully understand this paper but it seems the authors only develop the proofs and theorem 1 and theorem 2 for 1d input such that they calculate the convergence rates for a two layer network to model a linear function wx where w is a vector length n and x is just a scaler number. If I understand this correctly, I am not sure how much we learn from this? Does this theorem apply for as real neuron where d is not one? \n\n-The ideas appear to be sound but they are not very palatable to a reader.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thorough feedback.\n\nQ1: About tables to layout the important notation.\n\nA1: Thanks for your constructive suggestions. The notations in this paper are self-consistent and are equipped with informal explanations when they occur in the context for the first time. Readers may forget the explanations when reading through the paper. Thus, we will consider adding some notation tables to remind readers of the definitions.\n\nQ2: About using a two-layer network to model a single neuron.\n\nA2: Thanks for your valuable feedback. Throughout this paper, we focus on learning a neuron with a neuron (not a two-layer network), which is a standard and widely studied setting [1,2,3]. But when we consider learning a complex-valued neuron with a real-valued neuron, this learning process is unfair since a complex-valued neuron has more parameters than a real-valued neuron. This motivates us to investigate learning a complex-valued neuron with a two-layer RVNN to pursue fairness. Thus, the formulation in Eq. (1) considers learning with a two-layer network to cover all settings in the paper. It seems that the formulation and explanations are too complicated for readers, and we will consider reformulating our problem in later versions.\n\n[1] Mahdi Soltanolkotabi. Learning ReLUs via Gradient Descent (NeurIPS 2017).\n\n[2] Seyed Mohammadreza Mousavi Kalan, Mahdi Soltanolkotabi, and A. Salman Avestimehr. Fitting ReLUs via SGD and Quantized SGD (ISIT 2019).\n\n[3] Gilad Yehudai and Ohad Shamir. Learning a Single Neuron with Gradient Methods (COLT 2020).\n\nQ3: About $d > 1$.\n\nA3: This is an insightful question. In our paper, $d$ represents the dimension of the complex space. From the theoretical aspect, we introduce this condition for technical reasons. In traditional neuron learning, spherical symmetry is used to reduce the analysis to 2-dimensional real space. The condition $d=1$, i.e., 1-dimensional complex space, is used to inherit the analysis framework. From the experimental aspect, we find that our findings also hold when $d$ is larger than one (Fig. 2 in the **global response**). As far as we know, this paper is the first one to analyze neuron learning in the complex domain, where symmetry becomes more complicated, and we rely on this condition to simplify the analysis. As supported by the experimental results, we believe that our findings can be extended to more general settings and we leave them for future explorations.\n\nQ4: About applications to physics.\n\nA4: Thanks for the valuable suggestions. We will consider introducing some applications related to physics in later versions.\n\nQ5: About desirable properties.\n\nA5: Thanks for raising these questions. If I have not misunderstood the questions, I need to elaborate on the motivation of these desirable properties, including universal approximation, boundedness and stability. These properties, which hold for both RVNNs and CVNNs, have been investigated for several decades in the community of neural network theory. Universal approximation roughly states that neural networks can approximate any measurable functions [4,5]. This property affirms the expressive power of neural networks and explains the phenomenon that neural networks can fit random data to perfect accuracy [6]. (Complete) stability roughly indicates that neural networks with any initialization will converge when it is optimized by gradient descent (or gradient flow) [7,8]. This property guarantees convergence and implies that the optimization is meaningful. In our paper, boundedness occurs together with stability since boundedness can be used to derive stability under some settings [8]. Although these properties may not directly reflect the performance of neural networks (i.e., generalization), these properties are still desirable since they help us theoretically understand neural networks.\n\n[4] Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators (Neural Networks, 1989).\n\n[5] Felix Voigtlaender. The universal approximation theorem for complex-valued neural networks (Applied and Computational Harmonic Analysis, 2023).\n\n[6] Devansh Arpit et al. A closer look at memorization in deep networks (ICML 2017).\n\n[7] Michael A. Cohen and Stephen Grossberg. Absolute stability of global pattern formation and parallel memory storage by competitive neural networks (IEEE Transactions on Systems, Man, and Cybernetics, 1983).\n\n[8] Bo Zhou and Qiankun Song. Boundedness and complete stability of complex-valued neural networks with time delay (TNNLS 2013).\n\nQ6: About fair presentation, very long and technical appendix, hard-to-parse-through notations, and \"it often feels like one cannot truly understand what they are discussing in the paper without referencing the very dense and long appendix''.\n\nA6: It seems that the reviewer pays too much attention to technical details and is trapped by mathematical formulas. It should be emphasized that we elaborate on our settings and conclusions in the introduction part, which is sufficient to understand and estimate our contributions. Meanwhile, we provide detailed and intuitive explanations after key definitions and theorems to help readers understand complicated mathematical formulas. If one hopes to delve into details of our theoretical results, it is necessary to possess some basic knowledge related to neuron learning and may require much more effort."}, {"review_id": "OqxFpc4Ddd", "reviewer": "Reviewer_D3zC", "summary": "The authors presents theoretical results on learning real-valued and complex-valued neurons with gradient descent. The key takeaways are that:\n* complex-valued neuron learns real-values neurons and complex-valued neurons with convergence rate $O(t^{-3})$ and $O(t^{-1})$ respectively\n* two-layer real-valued neural network cannot learn a single complex-valued neuron\n* complex-valued neuron learns slower than real-valued neurons when learning real-value neurons", "questions": "* Do the authors expect the convergence rates to be further improved with other learning rate schedules/learning algorithms (other than projected gradient descent)?", "limitations": "yes", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper is well-written and easy to understand even for non-experts (myself)\n* This appears to be a significant advance in the theory of complex-valued neuron learning, with previous work largely focusing on real-valued neuron learning. However, as someone outside this field, I defer to other reviewers' for their assessment of significance.\n", "weaknesses": "* While the main results in this paper are theoretical proofs, the paper could be furthered strengthed with empirical experiments that validate the proofs.\n* table 2 appears to containa typo? the result for theorem 2 should be $O(t^{-1})$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the comments and feedback.\n\nQ1: About empirical experiments to further strengthen the paper.\n\nA1: Thanks for your valuable suggestions. We provide toy experiments in the **global response**, where we verify our findings in more general settings.\n\nQ2: About the typo in Table 2.\n\nA2: Thanks for pointing out this problem. We will correct it in later versions.\n\nQ3: About further improving the convergence rate with other learning rate schedules and learning algorithms.\n\nA3: Absolutely yes. This paper focuses on traditional learning rate schedules and gradient descent methods since they are widely used in the analysis and early implementations of RVNNs. However, it remains an open problem whether they are the best choice for CVNNs. I prefer to believe they are not since learning CVNNs includes the learning of phase, which does not exist in learning RVNNs. It would be promising to find more suitable algorithms for CVNNs."}]

Author rebuttal:
We thank the reviewers for their detailed feedback. We are thankful that our theoretical results are approved by most reviewers, many important questions are raised, and many constructive suggestions are proposed. A general consensus is that additional experimental verifications can help our paper become more convincing and increase the reader pool. Thus, we provide here several experimental results to further strengthen our theoretical results and verify our findings in more general settings. Detailed responses to individual questions and suggestions are provided in separate responses.

**Experimental settings.** A training set of size 7,000 and a test set of size 3,000 are generated by a randomly initialized target neuron (can be a real-valued or a complex-valued neuron). After random initialization, a complex-valued neuron and a real-valued neuron are trained by gradient descent with the empirical mean square loss and a learning rate of 0.1 for 100 epochs (or 300 epochs when the loss does not converge).

**Experimental results.** We investigate two different settings and report the test error curves in the attached pdf. In Fig. 1, we adopt the theoretical setting with $d=1$ and without bias term. In Fig. 2, we soften the dimension condition and add the bias terms. In all settings, we find that real-valued neurons fail to learn complex-valued neurons but converge faster when learning real-valued neurons. These experimental results verify our theoretical findings in general settings.


Meta-review: The authors considered the learnability of real- and complex-valued neurons via gradient descent on an architecture consisting of a single real- or complex-valued neuron.  They provided a tight guarantee for the convergence rate of a complex-valued neuron learning a real-valued neuron which, in light of prior work, shows a separation between learning with complex-valued and real-valued neurons.  They also provided the first guarantee for learning a complex-valued neuron.  

The reviewers had some concerns regarding the generality/applicability of the results to deeper or more general settings.  However, as the authors noted in their rebuttals, there is by now a long line of work on learning a single neuron with gradient-based methods, and the establishment of a precise understanding of the behavior of gradient descent/flow in this setting is of interest to a number of learning theorists.  I believe the authors' experiments developed during the rebuttal phase will also help broaden the paper's reception to non-learning-theorists.  Besides this concern, the reviewers were broadly supportive of the work.

In light of this, I recommend acceptance for this work.  I would also recommend that the authors revise their introduction so as to motivate the study of learning single neurons with gradient methods as a long-standing tradition in NeurIPS and related conferences, for instance the following prior works at ML all looked at similar problems:

Auer, P., Herbster, M. and Warmuth, M. K.  Exponentially many local minima for single neurons. NeurIPS 1995

S Frei, Y Cao, Q Gu. Agnostic Learning of a Single Neuron with Gradient Descent. NeurIPS 2020.

I Diakonikolas, S Goel, S Karmalkar, AR Klivans, M Soltanolkotabi. Approximation schemes for relu regression. Conference on learning theory 2020

Ilias Diakonikolas, Daniel Kane, Lisheng Ren, Yuxin Sun.  SQ Lower Bounds for Learning Single Neurons with Massart Noise.  NeurIPS 2022
Decision: Accept (poster)