In recent years, there has been a notable increase in the exploration of the expressive power of deep neural networks, driven by their impressive success in various learning tasks. The increasing size of deep neural network models poses significant challenges in terms of training and computational requirements. Consequently, numerous techniques have emerged to compress and expedite these models, with the goal of alleviating the associated computational complexity. These techniques predominantly center around parameter-sharing schemes, which efficiently reduce the number of parameters, leading to reductions in memory usage and computation costs. This paper explores the expressive power of deep neural networks, approaching it from the standpoint of function compositions. We focus on a novel network architecture constructed through the repeated compositions of a single fixed-size network, enabling parameter sharing. To illustrate our ideas and concepts, we specifically utilize the rectified linear unit (ReLU) activation function. Our investigation reveals that the repeated compositions of a single fixed-size ReLU network demonstrate surprising expressive power, even though the individual network itself has limited expressive capabilities. These findings provide new insights into the potential of parameter-sharing schemes in neural networks, showcasing their ability to reduce computational complexity while preserving a high level of expressive power.
For ease of notation, we employ NN{N, L; R d1 ↑ R d2 } to represent the set of functions ω : R d1 ↑ R d2 that can be realized by ReLU networks of width N ↓ N + and depth L ↓ N + . In our context, the width of a network means the maximum number of neurons in a hidden layer and the depth refers to the number of hidden layers. Let g →r denote the r-times composition of g, e.g., g →3 = g → g → g. In the degenerate case, g →0 represents the identity map. We use C([0, 1] d ) to denote the set of continuous functions on [0, 1] d and define the modulus of continuity of a continuous function f ↓ C([0, 1] d ) via ω f (t) := sup |f (x) → f (y)| : ↑x → y↑ 2 ↓ t, x, y ↔ [0, 1] d for any t ↔ 0. Under these settings, we can construct L 2 → g →r → L 1 to approximate a continuous function f ↓ C([0, 1] d ) with an error O ω f (r ↑1/d ) , where L 1 and L 2 are two affine linear maps and g is realized by a fixed-size ReLU network, as shown in the theorem below. Theorem 1.1. Given any f ↓ C([0, 1] d ), r ↓ N + , and p ↓ [1, ↗), there exist g ↓ NN{69d + 48, 5; R 5d+5 ↑ R 5d+5 } and two affine linear maps L 1 : R d ↑ R 5d+5 and L 2 : R 5d+5 ↑ R such that
It should be noted that in Theorem 1.1, the affine linear maps L 1 and L 2 are used to ensure matching dimensions and can be replaced by various other functions that achieve the desired input and output dimensions. In our research, we choose a straightforward approach by considering them as affine linear maps. In Theorem 1.1, we propose a novel network architecture constructed via repeated compositions of a single sub-network, which will be referred to as repeated-composition networks (RCNets). The hypothesis space of the RCNet corresponding to g is defined as H(g) := L 2 → g →r → L 1 : r ↓ N, L 1 and L 2 are affine .
Then we have an immediate corollary as follows.
Corollary 1.2. Given any p ↓ [1, ↗), suppose H(g) is defined as mentioned above and set G = NN{69d + 48, 5; R 5d+5 ↑ R 5d+5 }. Then H = ⇒ g↓G H(g) is dense in L p ([0, 1] d ) in terms of the L p -norm.
The proof of Corollary 1.2 is straightforward. Theorem 1.1 implies H is dense in C([0, 1] d ) in terms of the L p -norm for any p ↓ [1, ↗). Recall that C([0, 1] d ) is dense in the Lebesgue spaces L p ([0, 1] d ) for any p ↓ [1, ↗). Therefore, we can conclude that H is dense in L p ([0, 1] d ) in terms of the L p -norm for any p ↓ [1, ↗). Furthermore, it should be noted that the set G in Corollary 1.2 is generated by a fixedsize ReLU network. As a result, G is a set of continuous piecewise linear functions with (at most) a fixed number of pieces.
It is important to note that the approximation error in Theorem 1.1 is quantified by the L p -norm for any p ↓ [1, ↗). However, it is possible to extend this result to the L ↔ -norm as well, although the associated constants will be significantly larger.
Theorem 1.3. Given any f ↓ C([0, 1] d ) and r ↓ N + , there exist g ↓ NN{4 d+5 d, 3 + 2d; R d ↑ R d } and two affine linear maps L 1 : R d ↑ R d and L 2 : R d ↑ R such that
for any x ↓ [0, 1] d , where d = 3 d (5d + 4) ↘ 1.
The main ideas for proving Theorems 1.1 and 1.3 are provided in Section 3 and the detailed proofs of these two theorems can be found in Section A of the appendix.
In general, it is challenging to simplify the approximation error in Theorem 1.1 (or 1.3) due to the complexity of ω f (•). However, in the case of special target function spaces like Hölder continuous function space, one can simplify the approximation error to make its dependence on r explicit. If f is an Hölder continuous function on [0, 1] d of order ε ↓ (0, 1] with an Hölder constant ϑ > 0, we have
implying ω f (t) ≃ ϑt ω for any t ↔ 0. Thus, the approximation error in Theorem 1.1 (or 1.3) can be simplified to 6ϑ ⇐ d r ↑ω/d . In the special case of ε = 1, where f is a Lipschitz continuous function with a Lipschitz constant ϑ > 0, the approximation error can be further simplified to 6ϑ ⇐ d r ↑1/d .
A constant-width ReLU network of depth O(r) can be represented as L 2 → g r → • • • → g 2 → g 1 → L 1 , where L 1 and L 2 are affine linear maps and each g i is a fixed-size ReLU network. It has been shown in (Shen et al., 2020;Yarotsky, 2018;Zhang, 2020) that the optimal approximation error is O(r ↑2/d ) when using L 2 → g r → • • • → g 2 → g 1 → L 1 to approximate 1-Lipschitz continuous functions on [0, 1] d . In contrast, our RCNet architecture L 2 → g →r → L 1 can approximate 1-Lipschitz continuous functions on [0, 1] d with an error O(r ↑1/d ), where g is a fixed-size ReLU network.
That means, at a price of a slightly worse approximation error, our RCNet architecture L 2 → g →r → L 1 essentially shares most of the parameters in L 2 → g r → • • • → g 2 → g 1 → L 1 and reduce trainable parameters to a constant. Furthermore, our RCNet architecture L 2 → g →r → L 1 is anticipated to exhibit improved gradient behavior compared to L 2 → g r → • • • → g 2 → g 1 → L 1 as the gradient with respect to the parameters in g is less likely to vanish for larger values of r.
Next, we point out some relations between our approximation results and dynamical systems. Our results reveal that a continuous-depth network generated via a dynamical system has enormous approximation power even if the dynamics is time-invariant and realized by a fixed-size ReLU network. Let us now delve into further details regarding this matter. A dynamical system is generally described by an ordinary differential equation (ODE)
where F : R n+1 ⇓ ! ↑ R n is the dynamics function of this dynamical system, parameterized with ε ↓ !, where ! is the parameter space.
For any y = z 0 ↓ R n , z(T ) can be regarded as a function of y and we denote this function by "(•, ε) : R n ↑ R n . Such a map is known as the flow map (or Poincaré map) of the dynamical system (1). Then we can use
where L 1 and L 2 are two affine linear maps matching the dimensions.
Choose a large S ↓ N + and set ϖ = T /S. It follows from ODE (1) that
We denote z s as the numerical solution and use it to approximate the true solution z(ϖs) for s = 0, 1, • • • , S. By using the forward Euler method to discretize ODE (1), we have
Such an iteration step can be regarded as a residual network (He et al., 2016). Thus, a dynamical system can be viewed as a continuous-time version of a residual network. The network generated via a dynamical system is generally called continuous-depth network. The function L 2 → "(•, ε) → L 1 mentioned above is indeed generated by a continuous-depth network. As we know, z S can approximate z(ϖS) = z(T ) arbitrarily well for sufficiently large S with some proper conditions on the dynamics function F .
Suppose
Then, we have
Our results imply that L 2 → g →S ω → L 1 has immense approximation power even if g ω is realized by a fixed-size ReLU network, where L 1 and L 2 are affine maps matching the dimensions. Define
where g ω is realized by a fixed-size ReLU network. Then, the function L 2 → "(•, ε) → L 1 , modelled by a continuousdepth network, can approximate L 2 → g →S ω → L 1 well and hence also has immense approximation power. The definition of the dynamics function F in Equation (2) implies that F (y, t, ε) is independent of t for any (y, ε) ↓ R n ⇓ ! and F can also be realized by a fixed-size ReLU network. In short, we have shown that a continuous-depth network can also have immense approximation power even if its dynamics function is time-independent and realized by a fixed-size ReLU network. One may refer to Section 2.1 for a further discussion on dynamical systems.
The remaining sections of this paper are structured as follows. In Section 2, we discuss the connections between our results and existing work. Section 3 outlines the main ideas behind the proofs of Theorems 1.1 and 1.3. Next, in Section 4, we provide two simple experiments to numerically validate our theoretical results. Finally, Section 5 concludes this paper with a brief discussion.
In this section, we will provide a comprehensive overview of previous research that is pertinent to our results. We commence by emphasizing the correlation between deep learning and dynamical systems. Subsequently, we delve into the subject of parameter-sharing schemes in neural networks. Finally, we compare our results with existing research from the standpoint of function approximation.
A dynamical system is a mathematical framework that describes the evolution of a system over time. Its origins can be traced back to Newtonian mechanics. For a comprehensive overview of the history of dynamical systems, one may refer to (Holmes, 2007). In general, a dynamical system consists of two fundamental components. First, we have the state variable(s), which represent the variables that fully describe the state of the system. These variables capture the relevant properties or quantities of interest in the system. The second component is the time evolution rule, which specifies how the future states of the system evolve from the current state. It provides the mathematical equations or rules that govern the dynamics of the system over time. By studying the behavior and properties of dynamical systems, we gain insights into how systems change and develop over time. This framework has found applications in various fields, including physics, biology, economics, and computer science. In the context of deep learning, the connection to dynamical systems highlights the temporal aspect of learning and the potential for capturing complex dynamics in neural networks.
In recent years, there has been a growing body of research establishing connections between dynamical systems and deep learning. One such work (E, 2017) introduces a novel concept that interprets the discretization of a continuous dynamical system as a continuous-depth residual network. This approach utilizes continuous dynamical systems to model high-dimensional nonlinear functions commonly encountered in machine learning tasks. Another notable contribution by the authors in (Chen et al., 2018) parameterizes the derivative of the hidden state using a neural network, introducing continuous-depth residual networks. This work highlights several advantages of continuousdepth models, including constant memory cost. The study in (Li et al., 2023) establishes general sufficient conditions for the universal approximation property of continuousdepth residual networks, further connecting the dynamical systems approach to deep learning. A similar result is demonstrated in (Li et al., 2022), where the focus shifts to specific invariant functions instead of generic continuous functions. Additionally, the universal approximation property of deep fully convolutional networks is explored from the perspective of dynamical systems in (Lin et al., 2022). The authors demonstrate that deep residual fully convolutional networks, along with their continuous-depth counterparts of constant channel width, can achieve the universal approximation of specific symmetric functions. These studies serve as exemplary demonstrations of the endeavors made to establish connections between dynamical systems and deep learning. They explore the potential benefits and theoretical foundations of continuous-depth models in various contexts.
In recent years, deep neural network models have demonstrated notable accomplishments across various domains. Nonetheless, the growing size of deep neural network models frequently introduces complexities in terms of computation and memory usage. To tackle these challenges, several techniques for model compression and acceleration have been developed, many of which involve the concept of parameter sharing. Parameter-sharing schemes are utilized in neural networks to minimize the total number of parameters, resulting in reduced memory and computational requirements. Our network architecture, which involves the repeated compositions of a single fixed-size network, can be viewed as a particular instance of a parameter-sharing scheme in neural networks.
To the best of our knowledge, parameter-sharing schemes in neural networks can be broadly categorized into three basic cases. The first case involves sharing parameters within the same layer, as seen in convolutional neural networks (CNNs), where kernels (filters) are shared across all image positions. The second case entails sharing parameters among different layers of neural networks, as in recurrent neural networks (RNNs). Our network architecture follows this second scheme by sharing parameters through repeated compositions of a single fixed-size network. We demonstrate that this approach can yield immense approximation capabilities by repeating a fixed number of parameters. In addition to these two parameter-sharing schemes, there is also the practice of sharing parameters across different neural networks or models, which is often employed in multitask learning scenarios. For further insights into parameter sharing in neural networks, interested readers can refer to the references (Savarese & Maire, 2019;Wang et al., 2020;Plummer et al., 2022;Wang et al., 2020;Zhang et al., 2022;Wallingford et al., 2022).
The approximation power of neural networks has been extensively studied, with numerous publications focusing on constructing various neural networks to approximate a wide range of target functions. Some notable exam-ples include (Cybenko, 1989;Hornik et al., 1989;Barron, 1993;Yarotsky, 2018;2017;Bölcskei et al., 2019;Zhou, 2020;Chui et al., 2018;Gribonval et al., 2022;Gühring et al., 2020;Suzuki, 2019;Nakada & Imaizumi, 2020;Chen et al., 2019;Bao et al., 2023;Li et al., 2023;Montanelli & Yang, 2020;Shen et al., 2019;2020;Lu et al., 2021;Zhang, 2020;Shen et al., 2022b;a). In the early stages of this field, the focus was on exploring the universal approximation power of one-hidden-layer networks. The universal approximation theorem (Cybenko, 1989;Hornik, 1991;Hornik et al., 1989) demonstrated that a sufficiently large neural network can approximate a certain type of target function arbitrarily well, without explicitly estimating the approximation error in terms of the network size. Subsequent work, such as (Barron, 1993;Barron & Klusowski, 2018), analyzed the approximation error of one-hiddenlayer networks of width n and showed an asymptotic approximation error of O(n ↑1/2 ) in the L 2 -norm for target functions with certain smoothness properties.
Recent research has placed significant emphasis on the approximation of deep neural networks. Notably, the findings presented in (Shen et al., 2020;Yarotsky, 2018;Zhang, 2020) indicate that ReLU networks with n parameters can achieve an optimal approximation error of O(n ↑2/d ) when approximating 1-Lipschitz continuous functions on [0, 1] d . However, it is crucial to recognize that this optimal approximation rate suffers from the curse of dimensionality. To overcome the limitations imposed by the curse of dimensionality and achieve better approximation errors, various approaches have been proposed and explored. These approaches aim to enhance the quality of approximation or even directly address the challenges arising from the curse of dimensionality. One approach is to consider smaller function spaces, such as smooth functions (Lu et al., 2021;Yarotsky & Zhevnerchuk, 2020), band-limited functions (Montanelli et al., 2021), and Barron spaces (Barron & Klusowski, 2018;Barron, 1993;E et al., 2022). By restricting the class of functions being approximated, it is possible to achieve better approximation errors with neural networks. Another approach is to design new network architectures that can improve the approximation capabilities. Examples of such architectures include Floor-ReLU networks (Shen et al., 2021a), Floor-Exponential-Step networks (Shen et al., 2021b), (Sin, ReLU, 2 x )-activated networks (Jiao et al., 2021), and three-dimensional networks (Shen et al., 2022). By exploring different function spaces and designing novel network architectures, researchers have been able to push the limits of approximation accuracy in neural networks, providing more flexibility and better performance for various tasks. It is important to note that the literature on the approximation analysis of deep neural networks is vast, and the publications mentioned here represent only a subset of the existing research.
Many other approaches, techniques, and architectures have been proposed to address the challenge of improving the approximation error for specific function classes.
In this paper, we propose a specific neural network architecture generated by repeated compositions of a single fixed-size network. Theorems 1.1 and 1.3 demonstrate that repeating a small ReLU network block can enhance the approximation power of our network architecture. We will conduct experiments in Section 4 to numerically verify our theoretical results and evaluate the approximation capabilities of our network architecture.
Let us outline the main ideas behind the proofs of Theorems 1.1 and 1.3. During the proofs, our main approach involves constructing a piecewise constant function to approximate the desired continuous function. However, the continuity of ReLU networks poses a challenge in uniformly approximating piecewise constant functions. To bridge this gap, we first design ReLU networks to realize piecewise constant functions outside a sufficiently small region to approximate the target function well. Then, we will introduce a theorem to deal specifically with the approximation inside this small region for achieving uniform approximation.
Based on the aforementioned ideas, let us delve into the specific details. We divide [0, 1] d into a union of "important" cubes {Q ε } ε↓{0,1,•••,K↑1} d and a small region !, where K is a proper integer determined later. Each Q ε is associated with a representative 1 for an illustration of x ε , !, and Q ε . Then, the construction of the desired network approximating the target function can be divided into three steps as follows.
1. First, we design a sub-network to realize a vectorvalued function " 1 mapping the whole cube Q ε to its index ϑ for each ϑ. That is, "
2. Next, we design a sub-network to realize a function ϱ 2 mapping ϑ approximately to f
Additionally, we must also address the approximation occurring within ! and demonstrate that ϱ = ϱ 2 → " 1 can be represented in the desired form ϱ = L 2 → g →r → L 1 , where L 1 and L 2 are affine linear maps and g is realized by a fixed-size ReLU network.
0.00 0.25 0.50 0.75 1.00 0.00 0.25 0.50 0.75 1.00
A set of function values at representatives:
See Figure 1 for an illustration of these three steps. More details on these three steps can be found below.
Step 1: Constructing " 1 .
As mentioned previously, the aim of
, where ϱ 1 : R ↑ R is a step function outside a small region and hence can be realized by a ReLU network. It is generally challenging to design a ReLU network with a limited budget and the required architecture to realize such a function ϱ 1 . Thus, we establish a proposition, Proposition 3.1 below, to do this step and place its proof in Section C of the appendix.
Proposition 3.1. Given any ϖ ↓ (0, 1) and n, m ↓ N + with n ≃ m, there exist g ↓ NN 9, 1; R 5 ↑ R 5 and two affine linear maps L 1 : R ↑ R 5 and L 2 :
Step 2:
which is a key point to ease the design of a ReLU network realizing ϱ 2 . Indeed, if we can define a proper affine linear map L : R d ↑ R, then we only need to construct
It is still challenging to construct a ReLU network with a limited budget and the required architecture to realize ϱ 2 . Thus, we establish Proposition 3.2 below to simplify the construction of ϱ 2 . The proof of Proposition 3.2 is complicated and hence is placed in Section D of the appendix.
Proposition 3.2. Given any ς > 0, n, m ↓ N + with n ≃ m, and
there exist g ↓ NN{16, 2; R 6 ↑ R 6 } and two affine linear maps L 1 : R ↑ R 6 and L 2 : R 6 ↑ R such that
Step 3: Representing ϱ = ϱ 2 → " 1 properly.
With " 1 and ϱ 2 constructed in the first two steps, we can define ϱ := ϱ 2 → " 1 and we have
That means ϱ can approximate f well outside !. By making ϱ bounded and ! sufficiently small, we can easily control the L p -norm approximation error to prove Theorem 1.1 for any p ↓ [1, ↗). To prove Theorem 1.3, we require ϱ to pointwise approximate f well. To this end, we use the idea of Lemma 3.11 in (Zhang, 2020) (or Lemma 3.4 in (Lu et al., 2021)) to control the approximation error inside a small region.
Apart from a good approximation error, we also need to show that ϱ can be represented as the desired form L 2 → g →r → L 1 , where L 1 and L 2 are two affine linear maps and g is realized by a fixed-size ReLU network. Note that " 1 and ϱ 2 are constructed based on Propositions 3.1 and 3.2, respectively. Thus, both " 1 and ϱ 2 are expected to have the following form:
where L 1 , L 2 are affine linear maps and g is realized by fixed-size ReLU networks. Then, ϱ = ϱ 2 →" 1 are expected to have the following form:
where L 1 , L 2 , L 3 are affine linear maps and g 1 , g 2 are realized by fixed-size ReLU networks. It is not trivial to convert the form in Equation (3) to the desired form. A proposition is established to facilitate such a conversion.
and L 3 : R d2 ↑ R d3 be three affine linear maps. Suppose
The proof of Proposition 3.3 is technical and hence is deferred to Section E of the appendix.
The primary objective of this section is to numerically validate the theoretical results presented in Theorems 1.1 and 1.3. To achieve this goal, we have designed two distinct experiments. The first experiment, described in Section 4.1, focuses on a function approximation task. Our aim is to demonstrate that increasing r in our RCNet architecture, denoted as L 2 → g →r → L 1 , improves the error of function approximation. In this architecture, L 1 and L 2 represent affine linear maps, while g represents a ReLU network block. The second experiment, outlined in Section 4.2, focuses on a classification task. We intend to illustrate that increasing the value of r in our RCNet architecture L 2 →g →r →L 1 leads to enhanced classification performance. By evaluating the accuracy of the classification results, we can empirically validate the advantages of incorporating multiple compositions of the fixed-size ReLU network block. Through these experiments, our goal is to provide numerical evidence that supports the theoretical claims and showcases the potential of our RCNet architecture in terms of improving approximation power. The results obtained from these experiments will contribute to a comprehensive understanding of the practical implications and advantages of our network design.
Next, let us briefly discuss the expected impact of increasing r in our RCNet architecture L 2 →g →r →L 1 on the experiment results. In this discussion, we will focus on the ReLU activation function and consider the three main sources of errors in the test results: approximation error, generalization error, and optimization error. In our experiments where r is small, we assume that the optimization error is wellcontrolled due to the utilization of a good optimization algorithm. Thus, we can primarily focus on the effects of increasing r on the approximation and generalization errors. Increasing r has the potential to reduce the approximation error, as demonstrated by our theoretical results. However, it may also lead to an increase in the generalization error. Therefore, the performance improvement associated with larger values of r depends on whether the approximation error or the generalization error dominates. If the approximation error is the leading term, then increasing r can be beneficial. To emphasize the approximation error, we design our first experiment to involve a sufficiently complex target function. By choosing a challenging binary classification problem for our second experiment, we create conditions where the approximation error is relatively large. In both experiments, a sufficient number of samples are generated to control the generalization error, ensuring that it does not overshadow the effects of the approximation error. By carefully setting up these experiments and controlling the different sources of errors, we can gain insights into the impact of increasing r in our RCNet architecture.
To evaluate and compare the approximation capabilities of our RCNet architecture L 2 → g →r n → L 1 across various values of r and n, we will utilize it for a function approximation task. This architecture comprises two affine linear maps, L 1 and L 2 , along with a ReLU network block g n . To facilitate a comprehensive comparison, we have specifically chosen a target function f that exhibits a high degree of complexity. The function f :
, where the coefficient matrices are given by
, and (d i,j ) = 4φ 6φ 8φ 6φ .
To visually represent the target function f , we have included illustrations in Figure 2. By choosing this intricate function as our target, we can effectively assess the approximation capability of our network architecture across various values of r and n. In this experiment, we will employ the RCNet architecture L 2 → g →r n → L 1 to approximate the target function f for different values of r and n. Specifically, we consider r = 1, 2, 3, 4 and n = 100, 200. The ReLU network block g n is constructed by combining an affine linear map and the ReLU activation function, i.e., g n is defined as
for any x ↓ R n , where A ↓ R n↘n and b ↓ R n are parameters and ↼ is the ReLU activation function that can be applied element-wise to a vector. Then, the dimensions of the input and output for the two affine linear maps, L 1 : R 2 ↑ R n and L 2 : R n ↑ R, are determined accordingly. Notably, the ReLU network block g n consists of n 2 + n parameters. The affine linear map L 1 contains 2n + n = 3n parameters, while L 2 has n + 1 parameters. Consequently, the total number of parameters in L 2 → g →r n → L 1 is (n 2 + n) + 3n + (n + 1) = n 2 + 5n + 1 for different values of r and n. It is essential to note that when r ↔ 2, the parameters of L 2 → g →r n → L 1 are partially shared through repetitions of the ReLU network block g n . Our objective is to provide numerical evidence demonstrating that increasing the value of r results in improved test losses for each fixed n.
Before presenting the numerical results, let us delve into the hyperparameters utilized for training our network architecture L 2 → g →r n → L 1 for varying values of r and n, specifically r = 1, 2, 3, 4 and n = 100, 200. To generate the training and test samples, we employ the uniform distribution, resulting in 10 6 training samples and 10 5 test samples in [0, 1] 2 . During the training process, we utilize the RAdam optimization method (Liu et al., 2020), which aids in optimizing the network parameters. We set the minibatch size for training to 500, which signifies the number of training samples processed in each iteration. Our training process comprises a total of 500 epochs, representing complete passes through the training dataset. The learning rate is adjusted every 5 epochs. More specifically, the learning rate during epochs 5(i ↘ 1) + 1 to 5i is set to 0.002 ⇓ 0.9 i↑1 for i = 1, 2, • • • , 100. This adaptive adjustment allows for fine-tuning the model during training. To train our model, we employ the mean squared error (MSE) loss function, which measures the average squared difference between the network-generated function and the target function. To ensure the reliability of our experiment, we repeat it 12 times. From these repetitions, we discard 3 top-performing and 3 bottom-performing trials based on the average test accuracy of the last 100 epochs. The target accuracy is then determined by taking the average of the test accuracies from the remaining 6 trials for each epoch.
We are now prepared to present the experiment results that compare the numerical performances of L 2 → g →r n → L 1 for different values of r and n, specifically r = 1, 2, 3, 4 and n = 100, 200. The test losses over the last 100 epochs are averaged to obtain the target losses, considering two types of loss functions: mean squared error (MSE) and maximum (MAX) loss functions. Table 1 provides a comprehensive comparison of the numerical results obtained from L 2 → g →r n → L 1 for the given values of r and n. Additionally, Figure 3 illustrates the test losses measured in MSE on a logarithmic scale, allowing for an intuitive comparison. The values presented in Table 1 and the trends observed in Figure 3 clearly indicate a significant improvement in test losses with increasing values of r. These findings align with the theoretical results stated in Theorems 1.1 and 1.3, On Enhancing Expressive Power via Compositions of Single Fixed-Size ReLU Network providing further confirmation of the effectiveness of increasing r.
Lastly, it is crucial to acknowledge that further increasing the value of r may not lead to additional improvements in the results due to the inherent challenges involved in optimizing deep learning models. Issues such as local minima, saddle points, and vanishing gradients make it increasingly difficult to identify the global minimizer, particularly for larger values of r.
To assess and compare the approximation capabilities of our RCNet architecture L 2 →g →r n →L 1 across different values of r and n, we will employ it for a classification task. This architecture consists of two affine linear maps, L 1 and L 2 , along with a ReLU network block g n . For a comprehensive comparison, we have selected a complex binary classification experiment utilizing the Archimedean spiral, as proposed in (Shen et al., 2022). The objective of this classification problem is to accurately classify samples from two distinct sets, denoted as S 0 and S 1 . These two sets are constructed based on the Archimedean spiral, as illustrated in Figure 4.
Let us delve into the construction details of the sets S 0 and S 1 . An Archimedean spiral can be represented by the equation r = a + b↽ in polar coordinates (r, ↽) for proper a, b ↓ R. We begin by defining two curves s = 24. Next, we normalize
, where C i is defined as
With C 0 and C 1 defined, we can construct the target sets S 0 and S 1 as
, where ς = 0.006 in our experiments. Refer to Figure 4 for illustrations of S 0 and S 1 .
In this experiment, we will employ the network architecture L 2 →g →r n →L 1 to classify samples in S 0 ⇒S 1 for different values of r and n, specifically r = 1, 2, 3, 4 and n = 30, 40.
Here, L 1 and L 2 represent two affine linear maps, and g n corresponds to a ReLU network block. The construction of the ReLU network block g n involves combining an affine linear map with the ReLU activation function. Mathematically, g n is defined as
for any x ↓ R n , where A ↓ R n↘n and b ↓ R n are parameters and ↼ denotes the ReLU activation function that can be applied element-wise to a vector. Subsequently, the input and output dimensions of the two affine linear maps, L 1 : R 2 ↑ R n and L 2 : R n ↑ R 2 , are appropriately determined. The total number of parameters in L 2 → g →r n → L 1 can be easily verified to be (2n+2)+(n 2 +n)+(2n+n) = n 2 +6n+2 for different values of r and n. An important observation is that for r ↔ 2, the parameters in L 2 → g →r n → L 1 are partially shared due to the repeated utilization of the ReLU network block g n . Our objective is to provide numerical evidence demonstrating that increasing the value of r results in improved test accuracies for each fixed n. Before proceeding with the numerical results, let us provide an overview of the hyperparameters employed in training our network architecture L 2 → g →r n → L 1 for different values of r and n, specifically r = 1, 2, 3, 4 and n = 30, 40. First, we generate training and test samples from S 0 and S 1 using the uniform distribution. Specifically, we randomly generate 3 ⇓ 10 5 training samples and 3 ⇓ 10 4 test samples for each class. These 6 ⇓ 10 5 training samples are used for network training, while 6 ⇓ 10 4 test samples are utilized to compute the test accuracy. For optimization, we employ the RAdam method (Liu et al., 2020). The training process consists of 1000 epochs with a mini-batch size of 300. The learning rate is defined as 0.001 ⇓ 0.95 i↑1 during epochs 5(i ↘ 1) + 1 to 5i for i = 1, 2, • • • , 200. To evaluate the model output, we apply the softmax activation function to the network output and employ the cross-entropy loss function to measure the loss between the target function and the network output. To guarantee the standardization of training and test samples, we perform a rescaling procedure to adjust their mean to 0 and standard deviation to 1. To ensure reliability of our results, we conduct the experiment 12 times. Among these trials, we exclude 3 top-performing and 3 bottom-performing trials based on the average test accuracy over the last 100 epochs. The target accuracy is then determined by averaging the test accuracies from the remaining 6 trials for each epoch.
Let us now present the results of our experiments by comparing the numerical performances of L 2 → g →r n → L 1 for for varying values of r and n, specifically r = 1, 2, 3, 4 and n = 30, 40. The target test accuracy is computed by averaging the test accuracies over the last 100 epochs. Table 2 provides a comprehensive overview of the test accuracies obtained by L 2 → g →r n → L 1 for different values of r and n. To enhance the information presented in Table 2, Figure 5 serves as a complementary visual representation. It showcases graphical depictions of the data, enabling an intuitive comparison and facilitating a visual analysis of the performance trends. The results presented in Table 2 combined with the trends observed in Figure 5 confirm our initial expectation that increasing the value of r leads to improved test accuracies. These experiment results provide compelling numerical evidence demonstrating the effectiveness of increasing r, which aligns with the theoretical results stated in Theorems 1.1 and 1.3.
Finally, it is important to note that further increasing r may not necessarily result in additional improvements in the results. This is because optimizing deep learning models is notoriously challenging, as it involves various issues such as local minima, saddle points, and vanishing gradients. In our experiments, the primary difficulty lies in identifying the global minimizer, especially when dealing with large values of r.
Table 2. Test accuracy comparison.
This paper investigates the expressive power of deep neural networks from the perspective of function compositions. We demonstrate that the repeated compositions of a single fixed-size ReLU network exhibit surprising expressive power, despite the limited expressive capabilities of the individual network itself. As shown in Theorems 1.1 and 1.3, our RCNet architecture L 2 → g →r → L 1 can approximate any continuous function f ↓ C([0, 1] d ) with an error O ω f (r ↑1/d ) . Here, g represents a fixed-size ReLU network, while L 1 and L 2 correspond to two affine linear maps matching the dimensions. Furthermore, we explore the connection between our findings and dynamical systems. Our results reveal that a continuous-depth network generated through a dynamical system possesses enormous approximation capabilities, even when the dynamics function is time-independent and realized by a fixed-size ReLU network. Finally, we conduct experiments to provide numerical evidence that validates the theoretical results stated in Theorems 1.1 and 1.3.
It is worth mentioning that our analysis is currently focused on the ReLU activation function and fully connected network architectures. Extending our results to other activation functions, such as the sigmoid and tanh functions, as well as different neural network architectures, such as convolutional neural networks, would be of great interest for future research. Additionally, the numerical examples presented in this paper are relatively simple. Further exploration of the numerical performance of our network architecture and its application to real-world problems would be an intriguing direction for future studies. As we shall see later in the proofs of Theorems 1.1 and 1.3, our main approach involves constructing a piecewise constant function to approximate the desired continuous function. However, the inherent continuity of ReLU networks hinders their ability to uniformly approximate piecewise constant functions effectively. To address this limitation, we introduce the concept of the trifling region !([0, 1] d , K, ϖ) as defined in Equation (4). By utilizing ReLU networks, we can accurately represent piecewise constant functions outside the trifling region.
To streamline the proofs of Theorems 1.1 and 1.3, we introduce an auxiliary theorem, referred to as Theorem A.1 below, where we disregard the approximation within the trifling region !([0, 1] d , K, ϖ). Theorem A.1. Given a continuous function f ↓ C([0, 1] d ), for any r ↓ N + , there exist g ↓ NN 39d + 24, 3; R 5d+3 ↑ R 5d+3 and two affine linear maps L 1 : R d ↑ R 5d+3 and L 2 : R 5d+3 ↑ R such that
where K = ↙r 1/d ∝ and ϖ is an arbitrary number in (0, 1 3K ].
The proof of Theorem A.1 will be presented in Section B. Assuming the validity of Theorem A.1, we will provide the detailed proofs of Theorems 1.1 and 1.3 in Sections A.2 and A.3, respectively. To enhance clarity, Section A.1 offers a concise overview of the notations employed throughout this paper.
Below is a summary of the fundamental notations employed in this paper.
• The set difference of two sets A and B is denoted as A\B := {x : x ↓ A, x / ↓ B}.
• The sets of natural numbers (including 0), integers, rational numbers, and real numbers are denoted as N, Z, Q, and R, respectively. Set N + = N\{0}.
• The indicator (characteristic) function of a set A is denoted as 1 A , which takes the value 1 on elements of A and 0 otherwise.
• The floor and ceiling functions of a real number x are denoted as ↙x∝ = max{n : n ≃ x, n ↓ Z} and ′x∞ = min{n : n ↔ x, n ↓ Z}.
• Vectors and matrices are represented by bold lowercase and uppercase letters, respectively. For example, a = (a 1 , • • • , a d ) ↓ R d , A ↓ R m↘n is a real matrix of size m ⇓ n, and A T denotes the transpose of A.
• Slicing notation is used for a vector
• By convention, m j=n a j = 0 if n > m, no matter what a j is for each j.
• For any
In the degenerate case 0.00 0.25 0.50 0.75 1.00 0.00 0.25 0.50 0.75 1.00 • The rectified linear unit (ReLU) is denoted as ↼(x) = max{0, x} for any x ↓ R. With a slight abuse of notation, we allow ↼ to be applied element-wise to a vector, i.e., ↼(x
• Suppose ω is a function realized by a ReLU network, whether scalar or vector-valued. Then, ω can be expressed as
where W i ↓ R Ni+1↘Ni and b i ↓ R Ni+1 are the weight matrix and the bias vector in the i-th affine linear map L i , respectively, i.e.,
and
Furthermore, ω can be expressed as a composition of functions. Specifically, it can be written as
Refer to Figure 7 for an illustration. • A network is referred to as "a network of width N and depth L" if it satisfies the following conditions.
-The number of neurons in each hidden layer of this network is less than or equal to N .
-The number of hidden layers of this network is less than or equal to L.
By assuming the validity of Theorem A.1, we can proceed to prove Theorem 1.1.
Proof of Theorem 1.1. We assume that f is not a constant function, as considering constant functions would lead to a trivial case. Therefore, for any t > 0, we have ω f (t) > 0. Set K = ↙r 1/d ∝ and let ϖ ↓ (0, 1 3K ] be an arbitrary number determined later. By Theorem A.1, there exist g 1 ↓ NN 39d + 24, 3; R 5d+3 ↑ R 5d+3
and two affine linear maps L 1 : R d ↑ R 5d+3 and L 2 : R 5d+3 ↑ R such that
That means the approximation error is well controlled outside the trifling region
To this end, we define
where
We claim g 2 ↓ NN{4, 2; R ↑ R}. To see this, we need to show how to realize g 2 by a ReLU network. Clearly, we have
where the last equality comes from
As shown in Figure 8, g 2 ↓ NN{4, 2; R ↑ R} as desired.
x ω(x + M ) Let L 3 : R ↑ R as the identity map. Then, by Proposition 3.3 with
and two affine linear maps L 1 : R d ↑ R 5d+5 and L 2 : R 5d+5 ↑ R such that
Thus, we have
, where the last inequality comes from Equation ( 5).
Observe that the Lebesgue measure of !([0, 1] d , K, ϖ) is bounded by Kdϖ. Hence, by choosing a small ϖ ↓ (0, 1 3K ] with
Therefore, we can conclude that
). Thus, we have completed the proof of Theorem 1.1.
To establish Theorem 1.3, we will rely on Theorem A.1, which permits unbounded approximation errors in the trifling region !([0, 1] d , K, ϖ). However, when it comes to proving Theorem 1.3 using pointwise approximation, it becomes essential to control the approximation error within the trifling region. To address this, we introduce a separate theorem that specifically deals with the approximation within the trifling region.
Theorem A.2 (Lemma 3.11 of (Zhang, 2020) or Lemma 3.4 of (Lu et al., 2021)). Given any ς > 0, K ↓ N + , and
where ϱ := ϱ d is defined by induction through ϱ 0 := g and
where {e i } d i=1 is the standard basis in R d and mid(•, •, •) is the function returning the middle value of three inputs.
Now, we are prepared to provide the detailed proof of Theorem 1.3 by assuming the validity of Theorem A.1.
Proof of Theorem 1.3. We may assume f is not a constant function since it is a trivial case. Then ω f (t) > 0 for any t > 0.
Set K = ↙r 1/d ∝ and choose a sufficiently small ϖ ↓ (0, 1 3K ] such that
By Theorem A.1, there exist g 0 ↓ NN 39d + 24, 3; R 5d+3 ↑ R 5d+3 and two affine linear maps L 0,1 : R d ↑ R 5d+3 and L 0,2 : R 5d+3 ↑ R such that
where ϱ := ϱ d is defined by induction through
Here, {e i } d i=1 is the standard basis in R d and mid(•, •, •) is the function returning the middle value of three inputs. It remains to show ϱ = ϱ d can be represented as the desired form. We claim that ϱ i can be represented as
, and g i satisfy the following conditions:
• r i = 3r + 2i ↘ 1 and A i = d + 1 ↘ i;
• L i,1 : R d ↑ R di and L i,2 : R di ↑ R are two affine linear maps with d i = 3 i (5d + 4) ↘ 1;
We will prove this claim by induction. First, let us consider the base case i = 0. Clearly,
, where d 0 = 3 0 (5d + 4) ↘ 1 = 5d + 3, L 0,1 : R d ↑ R d0 and L 0,2 : R d0 ↑ R are two affine linear maps and
Next, let us assume the claim holds for the case i = j ↓ {0, 1, • • • , d ↘ 1}. We will prove the claim for the case i = j + 1. By the induction hypothesis, ϱ i can be represented as
where L j,1 : R d ↑ R dj and L j,2 : R dj ↑ R are two affine linear maps and g j ↓ NN{N j , L j ; R dj ↑ R dj }.
and L 3 : R 3 ↑ R via L 3 (y 1 , y 2 , y 3 ) := y 1 for any (y 1 , y 2 , y 3 ) ↓ R 3 .
Clearly, (Shen et al., 2021b), mid(•, •, •) can be realized by a ReLU network of width 14 and depth 2, implying G ↓ NN{14, 2; R 3 ↑ R 3 }.
Then, by Proposition 3.3 with
and two affine linear maps L j+1,1 : R d ↑ R dj+1 and L j+1,2 : R dj+1 ↑ R such that
where the last equality comes from r j +1+1 = (3r+2j↘1)+1+1 = 3r+2(j+1)↘1 = r j+1 . Therefore, for any x ↓ [↘A j+1 , A j+1 ], we have
By the principle of mathematical induction, we finish the proof of the claim.
Then, by the claim and setting d = 3 d (5d + 4) ↘ 1, ϱ = ϱ d can be represented as
where L d,1 : R d ↑ R d and L i,2 : R d ↑ R are two affine linear maps and
By defining L 1 := L d,1 , g := g d , and
Thus, we finish the proof of Theorem 1.3.
In this section, we will provide the proof of the auxiliary theorem, Theorem A.1, by relying on Propositions 3.1, 3.2, and 3.3. The detailed proofs of these propositions can be found in Sections C, D, and E, respectively. By assuming the validity of these three propositions, we now proceed to prove Theorem A.1.
Proof of Theorem A.1. We may assume ω f (t) > 0 for any t > 0 since ω f (t 0 ) = 0 for some
Set K = ↙r 1/d ∝ and let ϖ be an arbitrary number in (0, 1 3K ]. The proof can be divided into four main steps as follows.
is the trifling region defined in Equation (4).
2. Use Proposition 3.1 to construct a vector function
, " 1 (x) = ϑ for all x ↓ Q ε , where L 1 and L 2 are affine linear maps and G 1 is realized by a fixed-size ReLU network.
L 4 , and L 5 are affine linear maps and g 2 is realized by a fixed-size ReLU network. This core step can be further divided into two sub-steps: 3.1. Design an affine linear map L 3 bijectively mapping the index set {0, 1, 10 for an illustration. 3.2. Apply Proposition 3.2 to design a sub-network to realize a function L 5 → g
) and we use Proposition 3.3 to show ϱ can be represented as L 2 → g →(3r↑1) → L 1 , where L 1 and L 2 are affine linear maps and g is realized by a fixed-size ReLU network. Then we have ϱ
The details of the above steps are presented below.
Step 1:
where !([0, 1] d , K, ϖ) is the trifling region defined in Equation (4). See Figure 9 for illustrations of !([0, 1] d , K, ϖ), Q ε , and
0.00 0.25 0.50 0.75 1.00
Step 2: Construct " 1 mapping x ↓ Q ε to ϑ.
By Proposition 3.1 with m = r and n = K = ↙r 1/d ∝ ≃ r = m therein and setting ϖ = Kϖ, there exist g 1 ↓ NN 9, 1; R 5 ↑ R 5 and two affine linear maps L 1 : R ↑ R 5 and L 2 : R 5 ↑ R such that
It is easy to verify that G 1 ↓ NN 9d, 1; R 5d ↑ R 5d .
For any
Therefore, for any
By defining
Step 3: Construct ϱ 2 mapping ϑ approximately to f (x ε ).
We will use Proposition 3.2 to construct the desired ϱ 2 . To meet the requirements of applying Proposition 3.2, we first define two auxiliary sets A 1 and A 2 as
Clearly,
See Figure 9 for an illustration of A 1 and A 2 . Next, we further divide this step into two sub-steps.
Step 3.1:
Inspired by the base-K representation, we define
Then L 3 is a linear function bijectively mapping the index set {0, 1,
Step 3.2: Apply Proposition 3.2 to construct a sub-network mapping L 3 (ϑ) approximate to f (x ε ).
Recall that
We will use a set of
to construct a continuous piecewise linear function h :
Precisely, we design h by making it satisfy the following two conditions.
• First, we set h(1) = f (1) and h
• Next, we let h be linear between any two adjacent points in A 1 ⇒ {1}.
See Figure 10 for an illustration of h.
It is easy to verify that
0.00 0.25 0.50 0.75 1.00 0 1
By defining L 4 (x) := L 4 (2K d x) for any x ↓ R, we have
By Equation ( 9) and
(10)
Step 4: Construct the desired function ϱ and show it can be represented by the desired form.
We are ready to define the desired function ϱ via
By defining L
Recall that G 1 ↓ NN 9d, 1; R 5d ↑ R 5d and g 2 ↓ NN 16, 2; R 6 ↑ R 6 . By Proposition 3.3 with N 1 = 9d, N 2 = 16, L 1 = 1, L 2 = 2, d 0 = d, d 1 = 5d, d 2 = 6 and d 3 = 1 therein and setting d = 5d + 1 ↔ max{5d, 6}, there exist
and two affine linear maps L 1 : R d ↑ R 5d+3 and L 2 : R 5d+3 ↑ R such that
Next, let us estimate the approximation error. Recall that
. By Equations ( 7) and ( 10), for any
where the last inequality comes from
where the last equality comes from the fact 2 2 ⇐ n ≃ 5 ⇐ n for any n ↓ N + . So we finish the proof of Theorem A.1.
The main idea behind proving Proposition 3.1 lies in the composition architecture of neural networks. To streamline the proof, we begin by introducing a lemma, Lemma C.1 below, which can be seen as a weaker version of Proposition 3.1. Lemma C.1. Given any ϖ ↓ (0, 1) and n ↓ N + with n ↔ 2, there exist g ↓ NN 9, 1; R 5 ↑ R 5 and two affine linear maps L 1 : R ↑ R 5 and L 2 : R 5 ↑ R such that Proof of Proposition 3.1. We may assume m ↔ n ↔ 2 since n = 1 is a trivial case. Set ϖ = (1↑ε)ε n ↓ (0, 1). By Lemma C.1, there exist g ↓ NN 9, 1; R 5 ↑ R 5 and two affine linear maps L 1 : R ↑ R 5 and L 2 : R 5 ↑ R such that
Define L 0 (x) := n↑ε↑ ε n
x + ϖ for any x ↓ R and L 1 := L 1 → L 0 . We claim
Then, by Equations ( 11) and ( 12), for any
It remains to prove Equation ( 12). Clearly,
implying L 0 is increasing. To prove Equation ( 12), we only need to prove
Let us first prove Equation ( 13). Clearly, for k
where the inequality comes from the fact ↘kn ↘
Next, let us prove Equation ( 14). In the case of k = n ↘ 1, we have
So we finish the proof of Proposition 3.1.
To ensure the completeness of the proof of Proposition 3.1, we now provide the proof of Lemma C.1.
Proof of Lemma C.1. Define
It is easy to verify that
Obviously, for any
It remains to construct g, L 1 , and L 2 such that
Now we are ready to construct g : R 5 ↑ R 5 . Define
for any (y 1 , y 2 , y 3 , y 4 , y 5 ) ↓ R 5 , where
). See an illustration of the ReLU network realizing g : R 5 ↑ R 5 in Figure 12. Clearly, g ↓ NN{9, 1; R 5 ↑ R 5 }.
Define L 1 : R ↑ R 5 via L 1 (x) := (x, 1, 1, x, 0) and L 2 : R 5 ↑ R via L 2 (x 1 , x 2 , x 3 , x 4 , x 5 ) := x 5 . Then, we have
from which we deduce
So we finish the proof of Lemma C.1.
The bit extraction technique proposed in (Bartlett et al., 1998) plays a crucial role in proving Proposition 3.2. Before we delve into the proof of Proposition 3.2, we first establish Lemma D.1, which serves as a key intermediate step in the proof of Proposition 3.2.
Lemma D.1. Given any r ↓ N + , there exist g ↓ NN 8, 2; R 3 ↑ R 3 and two affine linear maps L 1 : R 2 ↑ R 5 and L 2 : R 5 ↑ R such that: For any
We will prove Proposition 3.2 by assuming the validity of Lemma D.1, which will be proved later in Section D.2.
D.1. Proof of Proposition 3.2 with Lemma D.1
Now we are ready to give the proof of Proposition 3.2 by assuming Lemma D.1 is true.
Proof of Proposition 3.2. We may assume n = m since we can set
Then, for any k ↓ {1, 2, • • • , n ↘ 1}, we have
By Lemma D.1 with r = n ↘ 1 therein, there exist g, g ↓ NN{8, 2; R 3 ↑ R 3 } and four affine linear maps L
On Enhancing Expressive Power via Compositions of Single Fixed-Size ReLU Network It is easy to verify that g ↓ NN{16, 2; R 6 ↑ R 6 }. Moreover, we have g →(n↑1) (x, y) = g →(n↑1) (x), g →(n↑1) (y) for any x, y ↓ R 3 .
Therefore, for k = 0, 1, • • • , n ↘ 1, we have
where the last equality comes from Equation ( 17). It follows that, for k = 0, 1,
So we finish the proof of Proposition 3.2.
To make the proof of Proposition 3.2 complete, we now provide the proof of Lemma D.1.
Proof of Lemma D.1. Set ϖ = 2 ↑r and define
See an illustration of T in Figure 13.
It is easy to verify that By setting ⇁ r+1 = 2⇁ r ↘ T (⇁ r ↘ 1 2 ) = 0, we have
Define g : R ⇓ [0, ↗) 2 ↑ R 3 via g(x 1 , x 2 , x 3 ) :=
for any (x 1 , x 2 , x 3 ) ↓ R ⇓ [0, ↗) 2 .
For ⇀ = 1, 2, • • • , r + 1, we set
Then, for ⇀ = 1, 2, • • • , r, we have
implying ϖ r+1 = g(ϖ r ) = • • • = g →r (ϖ 1 ).
Define L 1 : R 2 ↑ R 3 via L 1 (x 1 , x 2 ) := (x 1 ↘1, x 2 , 0) and L 2 : R 3 ↑ R via L 2 (x 1 , x 2 , x 3 ) := x 3 for any x 1 , x 2 , x 3 ↓ R.
Then, we have Clearly, g 2 ↓ NN{N 2 , L 2 ; R d2 ↑ R d2 } implies g 2 ↓ NN{N 2 , L 2 ; R d+1 ↑ R d+1 }.
By Lemma E.1, there exists , 2r 1 + 3
y, 0, 2r 1 + 1, 2r 1 + 3
Define L 1 : R d0 ↑ R d+2 via L 1 (x) := L 1 (x), 0, 2r 1 + 1, 2r 1 + 3 ↓ R d+2 for any x ↓ R d0 Step 2: Constructing ϱ.
Next, let construct a selector function ϱ to "select" g 1 or g 2 in G.
By Lemma E.2, there exists where " →0 means the identity map.
Observe that, for k = 1, 2, • • • , r 1 + r 2 , ϖ k , t k = " →k (x, 2r 1 + 1) = " → " →(k↑1) (x, 2r 1 + 1)
= "(ϖ k↑1 , t k↑1 ) = ϱ → G(ϖ k↑1 , t k↑1 ) = ϱ g 1 (ϖ k↑1 ), g 2 (ϖ k↑1 ), g 0 (t k↑1 ) .
Then, by Equation (20), it is easy to verify that t k = g 0 (t k↑1 ) = t k↑1 ↘ 2 and g 1 (ϖ k↑1 ), g 2 (ϖ k↑1 ) ↓ [↘M, M ] d for k = 1, 2, • • • , r 1 + r 2 , from which we deduce
and
Department of Mathematics, Duke University, USA. Correspondence to: Shijun Zhang <shijun.zhang@duke.edu>.