Compelling ReLU Networks to Exhibit Exponentially Many Linear Regions at Initialization and During Training
Authors: Max Milkert
David Hyde
Forrest John Laine
Venue: ICML 2025 poster (2025)
Keywords: linear regions
activation regions
ReLU network
pretraining
network initialization
Primary area: deep_learning->theory
TL;DR: A method of constraining weights to force exponential efficiency in deep ReLU networks.

Abstract: In a neural network with ReLU activations, the number of piecewise linear regions in the output can grow exponentially with depth.
However, this is highly unlikely to happen when the initial parameters are sampled randomly, which therefore often leads to the use of networks that are unnecessarily large.
To address this problem, we introduce a novel parameterization of the network that restricts its weights so that a depth $d$ network produces exactly $2^d$ linear regions at initialization and maintains those regions throughout training under the parameterization.
This approach allows us to learn approximations of convex, one-dimensional functions that are several orders of magnitude more accurate than their randomly initialized counterparts.
We further demonstrate a preliminary extension of our construction to multidimensional and non-convex functions, allowing the technique to replace traditional dense layers in various architectures.

Compelling ReLU Networks to Exhibit Exponentially Many Linear Regions at Initialization and During Training
Max Milkert 12
David Hyde'
Forrest Laine
Abstract
of active and inactive neurons can produce unique linear transformation over a particular region of input space. The number of these activation patterns and their corresponding linear regions provides a way to measure the expressivity of ReLU network! and can theoretically scale exponentially with the depth of the network (Montufar et al., 2014; Serra et al., 2018). Hence deep architectures may outperform shallow ones.
In neural network with ReLU activations, the number of piecewise linear regions in the output can grow exponentially with depth. However, this is highly unlikely to happen when the initial pa- rameters are sampled randomly, which therefore often leads to the use of networks that are un- necessarily large. To address this problem, we introduce novel parameterization of the network that restricts its weights so that depth d network produces exactly 2d linear regions at initializa- tion and maintains those regions throughout train- ing under the parameterization. This approach allows us to learn approximations of convex, one- dimensional functions that are several orders of magnitude more accurate than their randomly ini- tialized counterparts, We further demonstrate a preliminary extension of our construction to mul- tidimensional and non-convex functions, allowing the technique to replace traditional dense layers in various architectures.
Surprisingly, though, sophisticated theory of how to best encode functions into ReLUU networks is lacking, and in practice, adding depth is often observed to help less than one might expect from this exponential intuition. Lacking more advanced theory, practitioners typically use random parameter initialization and gradient descent, the drawbacks of which often lead to extremely inefficient solutions. In- deed, Hanin & Rolnick (2019) show a rather disappointing bound for randomly initialized networks: the average num- ber of linear regions formed at initialization is invariant with depth. Whether using a deep or shallow architecture, only the total number of neurons matters. They further observed that gradient descent has a difficult time creating new activa- tion regions, and thus their bounds approximately held after training. As we will discuss later, the total number of linear regions is not a "local" property in parameter space that gra- dient descent can directly optimize (see Figure 5). Gradient descent is also prone to redundancy; for instance, Frankle Carbin (2019) show how around 95% of weights may ulti- mately be eliminated from a network without significantly degrading accuracy.
1. Introduction
Beyond complementary advances in areas like hardware, storage, and networking, the success of neural networks is primarily due to their ability to efficiently capture and represent nonlinear functions (Gibou et al., 2019). In a neural network, the goal of an activation function to intro- duce nonlinearity between the network's layers so that the network does not simplify to single linear function. The rectified linear unit (ReLU) has unique interpretation in this regard. Since it either deactivates a neuron or acts an identity, the resulting transformation on each individual input remains linear. However, each possible configuration
The present work presents mathematical algorithms that avoid the limitations of random initialization. Our contribu- tions include:
A reparameterization of a 4-neuron-wide, depth d ReLU network that constrains it to initialize with 2d activation regions over the input domain (Section 3)
Depparmmett of Computer Science, Vanderbilt Univer- sity, Nashville TN, USA *National Renewable Energy Labo- ratory, Golden CO, USA. Correspondence to: Max Milkert <max.milken@@ vanderbilt.edu>.
novel pretraining strategy, which enforces the exis- tence of 2d activation regions during optimization to produce its initial solution (Sections 3, 3.1)
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
SSe Appendix A.2 for definitions of terms like linear regions, activation patterns, and activation regions.

---

Compelling ReLU Networks to Exhibit Exponentially Many Lincar Regions at Initialization and During Training
Numerical results for one-dimensional test cases that yield orders-of-magnitude improvements in network performance (Section 4)
T(O)
T(T(x))
T(T(T(O))
1.00
0.75
Extensions to non-convex and multidimensional func- tions, and use of our method drop-in replacement for dense layers in arbitrary networks (Sections 5 and 6; Appendices B.2-B.3)
0.25
0.00
0.0
0.5
1.0
0.0
0.3
1.0
0.0
0.5
1.0
f(x)
f2(x)
F((x)
1,00
While an exponential increase in the expressiveness of a ReLU network does not necessarily imply an exponential increase in performance, one may intuitively expect sub- stantial benefit, and our results bear this out, yielding error values orders of magnitude lower than traditionally-train network of equal size for simple test problems (Section 4), and outpacing such networks' performance during pretrain- ing on more practical test cases such as ImageNet (Section 6). We emphasize that while the preliminary mathematical analysis in this work pertains to a specific ReLU construc- tion, this construction can be repeated and combined in useful ways to obtain performance improvements on larger networks (Section 5). We conclude in Section 7 with dis- cussions on extending the mathematical framework of our method to arbitrary ReLU networks and other types of net- works, which would have significant practical utility.
0.75
0.50
0.25
0.00
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
fi f'(x)
f2 (x(x)
f((x)
2.0
1..
0.5
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Figure I. (Top bottom) Composed triangle waves; using collec- tions of the above function to approximate w²: derivatives of the above approximations.
2. Related Work
takes one-dimensional input [0, 1], and outputs one- dimensional signal also on [0, 1j. The function they produce in isolation is a single symmetric triangle. Together in network, each layer inputs its output to the next, performing function composition. Since each layer converts lines from to I into triangles, it doubles the number of linear segments in its input signal, exponentially scaling with depth.
This work is primarily concerned with novel training methodology for ReLU networks, but its development stems from more abstract idea of an exponentially accurate ap- proximation to the function 2², which can be encoded into ReLU network. Our work generalizes this construction into a trainable family of differentiable convex one-dimensional functions (see Appendix A.3).
The same effect can be achieved with nom-symmttric tri- angle waves (Huchette et al., 2023) (or any shape that suf- ficiently "folds" the input space (Montufar et al., 2014)). Our reparameterization strategy (Section 3) focuses on non- symmetric triangle waves.
2.1. Function Approximation
Infinitely wide neural networks are known to be universal function approximators, even with only one hidden layer (Hornik et al., 1989; Cybenko, 1989). Infinitely deep net- works of fixed width are universal approximators as well (Lu et al., 2017; Hanin, 2019). In finite cases, one may study trade-offs between width and depth to assess network's s ability to approximate (learn) a function.
The dilated triangular waveforms produced in this manner are not particularly useful on their own. Their oscillations quickly become excessively rapid, and their derivatives do not exist everywhere (especially in the infinite-depth limit), But these problems can be rectified by taking a sum over the layers of a network. Yarotsky (2017) 7) and Liang & Srikant (2016) construct = x" on [o, 1] with exponential accu- racy using symmetric triangle waves. To produce their ap- proximation, one begins with fo(x) = I,, then computes fi (z) fo(x) T(x)/4, fz(z) = fi(x) T (xT))) / fa /2(x) (TT()) and so forth, as pictured in Figure 1. As these successive approximations are com- puted, Figure plots their convergence to x², as well as the convergence of the derivative to 2r. Our reparameteriza- tion generalizes this approximation to use non-symmetric
Notably, there exist functions that can be represented with sub-exponential number of neurons in a deep architec- ture, yet which require an exponential number of neurons in wide and shallow architecture. For example, Telgar- sky (2015) shows that deep neural networks with ReLU activations on onc-dimensional input are able to gener- ate symmetric triangle waves with an exponential number of linear segments (shown in Figure as the ReLU net- work (x))). This network functions as follows: each layer
2

---

Compelling ReLU Networks to Exhibit Exponentially Many Linear Regions at Initialization and During Training
triangle waves to approximate a wider class of convex, dif- ferentiable, one-dimensional functions.
2.2. Neural Network Initialization
Our work seeks improve network initialization by making use of explicit theoretical constructs. This stands in sharp contrast current standard approaches, which treat neurons homogeneously. Two popular initialization methods im- plemented in PyTorch are the Kaiming (He et al.. 2015) and Xavier initialization (Glorot & Bengio, 2010). They use weight values that are randomly sampled from distri- butions defined by the input and output dimension of each layer. Aside from sub-optimal approximation power asso- ciated with random weights, a common issue is that the initial weights and biases in ReLU network can cause every neuron in a particular layer to output negative value. The ReLU activation then sets the output of that layer to O, blocking any gradient updates. This is referred to as the dying ReLU phenomenon (Qi et al., 2024; Nag et al., 2023). Worryingly, as depth goes infinity, the dying ReLU phe- nomenon becomes increasingly likely (Lu et al., 2020). Sev- eral papers propose solutions: Shin & Karniadakis (2020) use a data-dependent initialization, while Singh & Sree- jith (2021) introduce an alternate weight distribution called RAAI that can reduce the likelihood of the issue and in- crease training speed. We observed during our experiments that RAAI greatly reduces, but does not eliminate, the like- lihood of dying ReLU. Our approach enforces specific network structure that does not collapse in this manner.
The x² approximation is used by other theoretical works as a building block to guarantee exponential convergence rates in more complex systems. Perekrestenko et al. (2018) construct a multiplication gate via the identity (x + 1)² =
x² + y² + 2ry. The squared terms can all be moved to one side, expressing the product zy as a linear combina- tion of squared terms. They then further assemble these multiplication gates into an interpolating polynomial, which can have an exponentially decreasing eттоr when the in- terpolation points are chosen to be the Chebyshev nodes. Polynomial interpolation does not scale well into high di- mensions, so this and papers with similar approaches will usually come with restrictions that limit function complex- ity: Wang et al. (2018) requires low input dimension, Mon- tanelli et al. (2020) uses band limiting, and Chen et al. (2019) approximates low-dimensional manifolds. These works all make use of a fixed representation of z²". If our networks were substituted in for the x² approximation, these works would provide theoretical guarantees about the capabilities of the resulting model. Even though the approximation rates will not scale well with input dimension, they serve as a bound that can be improved upon. In Section 5, we further elaborate on how to use our networks to represent higher-dimensionall or non-convex functions.
Other works focus on showing how ReLU networks can encode and subsequently surpass traditional approximation methods (Lu et al., 2021: Daubechies et al., 2022). includ- ing spline-type methods (Eckle & Schmidt-Hieber 2019). Interestingly, certain fundamental themes from above like composition, triangles, or squaring are still present. Another interesting comparison of the present work is to Ivanova & Kubat (1995), which uses decision trees as a means to initialize sigmoid neural networks for classification. Similar to the spirit of our work, which restricts parameterizations of ReLU networks, Elbrächter al. (2019) explores theo- retical aspects of the conditionining of ReLU network train- ing and provides constructive results for a parameterization space that is well-conditioned. Chen & Ge (2024) present a creative approach where they explore reparameterizing the direction of weight vectors using hyperspherical coordinates to improve training dynamics. Unlike their reparameteriza- tion, ours will restrict the network's expressivity in order to prevent it from learning inefficient weight patterns. Lastly, Park et al. (2021) approaches the problem of linear region maximization from an information theory perspective and uses a loss penalty rather than a reparameterization to in- crease the number of linear regions.
3. Initialization and Pretraining Construction
In this section we describe our ReLU network reparame- terization strategy that ensures an exponential number of linear regions with respect to depth. We focus on architect- ing the weights of a 4-neuron-wide arbitrary depth ReLU network; while this is constraint of the present manuscript, we will show that despite this, we can effectively apply our construction to a wide variety of examples.
As alluded to in Section 2.1, the overall strategy of our repa- rameterization and initialization algorithm is associate a nonsymmetric triangle function with each layer of the net- work. This yields reparameterization of the ReLU network in terms of the locations of each triangle's 's peak on (0, 1), ag rather than in terms of the network's 's weights. Unlike the raw weights of a depth d ReLU network, any values chosen for the triangle peak parameters will result in the creation of 2d linear regions. Furthermore, this parameteri- zation is trainable. By using the peak location to set the raw weights of layer, the gradients can backpropagate through the raw weights to update the triangle peaks, effectively con- fining the network to a subspace of weights that generates many linear regions. Pseudocode for our entire algorithm is provided in Appendix A.
To illustrate how we set weights, we first describe the math-
3

---

Compelling ReLU Networks to Exhibit Exponentially Many Linear Regions at Initialization and During Training
ematical functions that arise in our analysis. Triangle func- tions are defined as
Pretraining Hidden Layer
Triangle Function
0 S 04
1/a
Tx(x)
di
S/U,
0j S 1
out
S,Ya,-
Líáa 1/(1-a)
where 0 < a, 1. This produces a triangular shape with peak = (i and zeros = and x 1. These functions are implemented by two ReLU neurons in each layer. In a deep network, each layer composes its triangle function with the output of the layer before it. The result is that each layer computes the following triangular waveform:
5
-S,0,..
Multllayer Pretraining Restrictions
sum
sum
sam
sum
(x(x) = O)=0TT(2) - (TT
(1)
S
F
These triangle waves will have 2' linear regions, doubling with each layer. By allocating extra neuron in each layer, construction will take weighted sum over each layer's triangle wave, using them as deep basis to build the output. In the infinite depth limit, the network output takes the form:
out
"Identical Line Coloring Indicates Shared Weight
bias
blus
blas
80
F(x) Σ s WW(()),
On the top left is network representation of triangle function. The top right shows that triangle function as a hidden layer of a network. The one- mieeemmnsioonl input and output a tri- angle function is converted into shared weights. A full pretraining network is assembled on the bottom.
Figure 2.
where 8; are scaling coefficients on each of the composed triangular waveforms W,. F(z) would be a parabola if we exactly followed the related work. F(z) could also end up being fractal curve if the 8; are chosen to be too large. Choosing s; carefully to regularize F(z) is major part of our construction.
way to combine the 4 and L/ neurons in order to obtain a triangle function, so every hidden neuron will combine the previous 61 and lz neuron in this proportion. Using identical weights makes each layer act as if is composing functions in one dimension, rather than in dimension equal to the number of neurons.
Now we will discuss how to encode these functions into the weights of ReLU network, beginning with a network for single triangle function (see the upper left diagram in Figure 2). Each triangle function has two nonzero linear pieces, requiring two ReLU neurons. For simplicity, we will set both neurons' input weights to 1. We will arrange for neuron l to be active for all inputs, and since the maximum output should be 1 at the peak location a E (0, 1), neuron t will have an outgoing weight of 1/a. x a is where the slope should change, to suppress it for x < Since both neurons are active for z > neuron 12 will need to be weighted by -(1/a 1/(1 - a)) = - 1/(a a a²); this weight will both suppress neuron f and also ensure the second leg of the triangle function reaches 0 at x = 1. This is now the first network shown in Figure 2.
The goal of the network is not to output triangle waves; instead, the function we seek to approximate is F(z), de- fined earlier to be a weighted sum of the triangle waves from each layer. We add an extra neuron each layer, la- beled "sum" in Figure 2, compute this. These ordinary neurons, but thanks their specific weights, they will act similarly to a residual connection (He et al., 2016), allowing the hidden features in the network to be used in the output. Each sum neuron adds the previous layer's triangle wave to the previous sum neuron, thereby iteratively updating an approximation to F(x)..
neuron l2 will be biased by
To compose the triangle waves Wz(x), copies of this net- work can be stacked together depth-wiss lining up the "in" and "out" neurons of successive networks. This will have a non-uniform width (1 + 2 + 1 + 2 + 1...), but since the input weights of the hidden i and to neurons are both 1, it can be simplified into the form shown on the top right of Figure The weights 1 /a and -1/(a- a²) give the correct
According to Theorem 3.1, each triangle wave added the must have an amplitude exponentially smaller than the last. Exponentially small weights would pose conditioning issues in optimization, so rather than giving the sum neuron an exponentially small weight, we use the ratio of successive scaling coefficients S, = s1/s;-1 to iteratively decay the amplitude of the i and l2 neurons. But because ie now has
4

---

Compelling ReLU Networks to Exhibit Exponentially Many Lincar Regions at Initialization and During Training
Layer1
3.2. Differentiable Model Output
Given the rapid oscillations of the triangle waves formed at each layer, the network will output fractal with many choices of scaling parameters. This would be poorly pre- dictive of unseen data points generated by a smooth curve. Rather than turning to general regularizer like batch norm (loffe & Szegedy, 2015) or layer norm (Lei Ba et al., 2016), we use a regularization scheme that arises from the form of our functions. When we require that the network output approach a differentiable function in the infinite depth limit, elegant relationship arises where the peak locations of the triangle waves uniquely determine the scales with which to sum them.
14
04
24
044
02
32
022
Laye-4
Layer 5
Ourgut
1.0
00
Sum
811
07-
03
02
14
04
86
20
00
02
04
04
03
13
60
62
04
65
10
Theorem 3.1. F' s. (x) and is continuous on [0, 1] only if the scaling coefficients 8; are selected based on the triangle peaks a, according to:
Figure 3. Each colored line shows the output signal of neuron with respect to the input to network. Colors match the corre- sponding neurons in Figure 2.
81+1 = 8i(1 01++1 )1++1)042..
an exponentially small amplitude, its bias must be exponen- tially small to function properly. Rather than implementing an exponentially small bias, we make the bias into neuron. This is rather unconventional, but by using the connection to the previous bias neuron, the bias can decay iteratively, and l2 neurons can use their weight to the bias neuron to implement their bias. In matrix form, our hidden layers are:
Mathematical analysis and sufficient conditions for differ- entiability in the limit are in Appendix A.3. In Section 4, we will see that following this regularization allows the pretraining phase to produce better initial solutions.
4. One-Dimensiinal Experiments
Since our network construction applies directly one- dimensional convex functions, focus on such functions in this section (we cover more difficult functions in Sections 5- 6 and Appendices B.2-B.3). The aim of these experiments is twofold: (1) we would like to determine the most effective function representations possible from such a small network, and (2) to explore how the utilization of an increased num- ber of linear regions can affect network's ability to capture underlying nonlinearity in its training data. To demonstrate that our networks can learn function representations that bet- ter utilize depth, we benchmark against PyTorch's 's (Paszke et al., 2019) default settings (nn 1 linear () uses Kaiming initialization), as well as the RAAI distribution (Singh & Sreejith, 2021), and produce errors that are orders of mag- nitude lower than both. We also train several permutations of our reparameterized networks, which validate that our pretraining and our differentibility constraints indeed facili- tate smoother navigation of the loss landscape. Lastly, we conduct a second round of tests to determine if pretrained networks display an enhanced predictive capacity on unseen data points, as might be expected if they can leverage greater nonlinearity in their outputs.
1 + [S,//a Sa, -a?)]
0
sum f/2
0
Sa/a: SS,
af
0
0
Sa/a; - Sa/(a; af)
-Saa++1 S;
x
0
0
bias
Here, rows correspond to neurons, and the sum neuron can either add or subtract the triangle waves depending on whether the target function is convex or concave.
3.1. Pretraining and Overall Algorithm
We imagine the process of optimizing neural network pa- rameters three phases: (1) reparameterization and ini- tialization, where network's weights are initially set; (2) pretraining, where the network is trained under that reparam- eterization; and (3) training, where the network is trained using the network's weights directly. Our pretraining al- gorithm acts as a preconditioner for or guide to the loss landscape, and when an optimizer close to a minimum, the exponential expressivity of the network may no longer need to be guaranteed to ensure efficient neuron usage.
Our pretraining algorithm is thus to simply use optimizer like gradient descent to train the network under the reparam- eterization described above. Explicit formulas for updating the reparameterized weights, and pseudocode for our whole algorithm, are listed in Appendix A.
4.1. Experimental Setup
All models are trained using Adam (Kingma & Ba, 2017) as the optimizer with learning rate of 0.001 for 1,000 epochs
5

---

Compelling ReLU Networks to Exhibit Exponentially Many Linear Regions at Initialization and During Training
ensure convergence (see Appendix B.I for a brief analysis of different learning rates). Each network is four neurons wide with five hidden layers, along with one-dimensional input and output. The loss function used is the mean squared error, and the average and minimum loss are recorded for 30 models of each type. To compare how well each setup navigates the loss landscape, the networks using triangle- based parameterizations share a common set of starting locations where the triangle peaks and scaling parameters are chosen according to Theorem 3.1. The "unregularized" network has extra degrees of freedom to choose the scaling coefficients after initialization (so that differentiability of the output is not enforced during pretraining). "pretraining skipped" is a network that initializes with our method, but only trains in the standard parameterization. The four curves we approximate are x²,, _. tanh (3x), and a quarter period of sine wave. To approximate the sine and the hyperbolic tangent, the triangle waves are added to the line y x, while for x and x the waves are subtracted. When the waves are subtracted, the first scaling factor has to be changed to ag * aj instead of (1 - an) 01. The first set of data is 500 evenly spaced points on the interval [o, 1] for each of the curves. This is chosen to be very dense deliberately, to try to evoke the most accurate function interpolations from each network. We determine from these tests that pretraining with differentiabilityy enforced produces the best results, so we compare it to standard networks in our second set of experiments. We use a second set of data consisting of only 10 points, with a test set of 10 points spaced in between so as to be as far away from learned data as possible. This set of experiments evaluates the predictive capacities of the networks on unseen data.
not all of the dying ReLU instances due its probabilistic nature, so it, too, has high mean error. This is why we have focused on presenting the minimum error over all the trials.
Default Network
Reparametor bad Protra ning
60
04--
0.4
6.-
60-
001
0.
0.4
0/5
00
Figure 4. Standard Kaiming inidaaizationngradient descent vs. pre- training with differentiablity enforced. Using more linear regions allows the curve to better predict the test points.
Our second set of results is shown in Table 3 and in Figure 4. Here the most important impact of utilizing exponentially many linear regions is demonstrated. Not only can more accurate representations of training data be learned, but maintaining more linear regions allows the network to better capture underlying nonlinearity to enhance its predictive power in regression tasks. This result is especially signifi- cant because it indicates that even in cases where there are fewer data points than linear regions, having the additional regions can still provide performance advantages.
5. Extension to Non-Convex Functions and Higher Dimensions
4.2. Numerical Results
The results presented far are limited to one-dimensional convex functions, but our method can easily be extended. Since our constructed networks are one-dimensional, they can be used as the activation functions of a larger network (see Figure 9 in the Appendix for a schematic). Our experi- mental results show that even using just two copies of our network in this manner can go long way towards increas- ing the expressive ability of the technique. For example, two of our networks could be used to build a two-dimensional convex function. This can be done by using one network to build a convex function oriented in the x direction, and the other in the y direction. A positive linear combination of their outputs then yields a two-dimensional convex function. Similarly, a non-convex function can realized by taking a difference of the outputs of two of our networks. Of course, this pattern can be generalized to an arbitrary-width layer using of our networks.
Our first set of results are shown in Tables and 2, wherein we observe several important trends. First, the worst per- forming networks are the "default networks" that rely on randomized (Kaiming) initialization (see also Figure 5). Even the networks that forgo pretraining benefit from ini- tializing with many activation regions. When pretraining constraints are used, they are able to steer gradient descent to the best solutions, resulting in reductions in minimum error of three orders of magnitude over default networks. Pretraining with differentiability enforced also closes the gap between the minimum and mean errors compared to other setups. This indicates that these loss landscapes are indeed the most reliable to traverse. Enforcing differentia- bility during pretraining can impart bias towards smoother solutions during subsequent unassisted gradient descent.
The last trend to observe is the poor average performance of default networks. In a typical run of these experiments, around half of the default networks collapse from the dying ReLU phenomenon. RAAI is able to eliminate most, but
Figures 6 and 7 show learning the non-convex function y = x² --r x and the two-dimensional convex function 2 = 3 on [-1, 1]. each by using two of our constructed networks with hidden layers. For both x3 - I and r33 we sub-
6

---

Compelling ReLU Networks to Exhibit Exponentially Many Linear Regions at Initialization and During Training
Table 1. Minimum and mean (30 samples) MSE error approximating = x² and x
Training Type
Min x
Min 1
Mean x!! Mean x.3
Default Network (Kaiming)
2.11 10
2.19 x 10-5
7.20
10
2.82 x 10
RAAI Distribution
2.14 x 10-5
4.40 x 10-5
3.97
10-2
4.12 x 10-2
Pretraining Skipped
7.63 x 10 10-7
1.86 x 10-5
3.89
10
3.56 x 10
Pretraining (Unregularized)
1.64 x 10-7
3.20 x 10-6
1.02
10-6
3.73 x 10-5
Pretraining (with Thm. 3.1)
7.86 x 10-
8.86 x 10-7 5.27 x 10-7
7.87 x 10-6
Table 2. Minimum and mean (30 samples) MSE error approximating y = sin(2) and y 13rh Training Type
Min sin(x)
Min tanh(3r)
Mean sin(r)
Mean tanh (3.z)
Default Network (Kaiming)
4.50 x 10-5 5
5.75 x 10-5 5
1.15 x 10
1.96 x 10-1
RAAI Distribution
3.59 x 10-5
1.09 x 10
3.63 10-2
2.31 x 10-2
Pretraining Skipped
1.96 x 10-7
1.07 10-6
1.93 10
8.38 x 10-5
Pretraining (Unregularized)
4.41 x 10 8
1.49 x 10-?
1.47 x 10-5
3.81 x 10-4
Pretraining (with Thm. 3.1)
5.06 x 10 6.82 x 10
2.21 x 10-7 8.42 10
stantially outperform standard initialization and training procedures. Especially striking is the increased number of linear regions in Figure 7. Like the previous experiments, these networks were trained using Adam for 1000 epochs at a learning rate of 0.001, and the minimum over 30 trainings was taken. The parameterization switch was made halfway through training. These experiments use slightly improved pretraining construction (see Appendix A. the input do- main is modified to be [-1, 1], and the network is adjusted so that the 1 and l2 neurons compose "v" shapes rather than triangles, which allows the network extrapolate bet- ter outside [-1,1], 1]. With multiple copies of the network, we implement the calculation of the d-th hidden layer as one large combined matrix. Since the hidden neurons of each subnetwork do not connect, the combined matrix takes on a sparse block diagonal structure with a block size of 4. When we switch parameterizations, we release the block diagonal constraint and allow gradient descent to fill in the zeroed weights.
Even though our original technique is not naturally designed for multivariate functions and has to be extended by incor- porating it we note that doing so has some theoretical backing. The multiplication gate and polynomial interpolation network discussed in the related work (Section 2.1) rely on linear combinations of squared terms. Since our networks can produce x², an arbitrary width and depth arrangement of our networks would retain the ability to perform polynomial interpolation. Secondly, the Colmogorov-Amolo represen- tation theorem (Kolmogorov, 1957; Arnold, 1957; 1959) gives guarantee that every continuous multivariate func- tion can be represented by a neural network-like like structure that is built using only addition and arbitrary continuous one-dimensional activation functions. Essentially, states that a technique that only works for univariate functions can still be sufficient for representing multivariate functions when deployed in larger network. The recently popu- larized Kolmoggoro-Amold Networks (KAN) (Liu et al., 2024) take their inspiration from this theorem, extending their networks to arbitrary width and depth, but restrict- ing the activations to splines. Even though this does not strictly follow the theorem, they still find empirical success. Similarly, in the case of this work, the functions that the triangular parameterization can directly represent are not dense, as they require certain degree of self- self-similarity. Nonetheless, when assembled into larger network, this may not pose a serious problem.
activation function in larger network,
We make a few notes on our preliminary extended technique. First, the class of non-convex functions that can be repre- sented as a difference of convex functions broad. Zhang et al. (2018) gives an iterative process to decompose an ar- bitrary ReLU network into difference of piecewise linear convex functions. Additionally, all functions with bounded second derivatives (or bounded eigenvalues of their Hessian matrix) can be expressed as difference of two convex func- tions. Finally, we note that these types of decompositions are not necessarily unique; for example, while x²3 - x can be expressed as (a.3 x + 3xz 3x. 2x22 is merely the mini- mal parabola needed to make the second derivative positive on (-1, 1), and larger coefficients could also be used.
6. Preliminary Image Classification Results
Since our extended technique be used to replace any dense layers in arbitrary architectures, can use it in con-
7

---

Compelling ReLU Networks to Exhibit Exponentially Many Lincar Regions at Initialization and During Training
Table Minimum errors unseen points from training on sparse data.
Training Type
Min 3:3
Min x!ll
Min sin(x)
Min tanh(3z)
Default Network (Kaiming) Pretraining (with Thm. 3.1)
2.41 x 10
2.14 x 10-3
2.27 x 10-5
1.60 x 10-4
5.65 x 10-5
6.53 x 10
7.92 x 10-7
5.09 x 10-6
Layer1
Layer
10
03-
62
05-
000
0.2
-22
-02
-04
Layer.2
Layer
Ditput
332
Layer
3.5
Layers 5
Outgut
Sum
06
04
-22
00
32
-32
02
113
1.5
30
010
Figure 5. Neuron outputs default (Kaiming-initialiann network (left) a pretrained variant of network (right). Notice that the first two layers of the default network introduce no linear regions none of the lines cross zero. Any infinitesimal adjustment to the slopes biases the lines would not make such an intersection occur. Therefore, the number linear regions generated by the network cannot be a local property, and we can expect gradient- based optimization to struggle at maximizing the linear region count. Our method uses non-locality our advantage. The pretraining phase
low-loss solution where 2 linear regions are generated, which guarantees neighborhood of parameter space where 2" regions can be maintained while training in the standard parameterization.
1.0
0.3
344
000 Output
Lay/rr
Layer 5
6.-
0.8
Figure 7. Approximations of Va² using 8 regu- lar network (left) and union of two of our pretrained components (right). Losses 1.5 10- annd 3.5 10-6, respectively, demon- strating a nearly two orders of magnitude improvement using our techniques.
-.4
-0.5
6.5
85
10
-10
-45
0.3
13
2.0
-25
60
65
Figure 6. Approximation y = x3 by difference of pretrained components, achieving a loss of 5.52 x 10-7, A standard x network yielded larger loss of x 10-6
8

---

Compelling ReLU Networks to Exhibit Exponentially Many Linear Regions at Initialization and During Training
texts beyond regression. In final experiment, we replace the densely connected classifier of VGG-16 (Simonyan & Zisserman, 2014), and then retrain the network on ImageNet (Deng et al., 2009). We initialize with Py PyToch's pretrained convolutional weights both to speed up training and to better isolate the effects of modification to the dense layers. Since VGG-16's dense layers have a width of 4096, we decided to leave the matrices corresponding to our subnetworks in block diagonal format, rather than allowing them to be- come dense. This way, our technique only adds a negligible amount of extra operations (roughly 0.5%) and does not leave the majority of weights to be filled in by unassisted gradient descent.
7. Concluding Remarks
This paper focused on exploiting the potential computational complexity advantages neural networks offer for the prob- lem of efficiently learning nonlinear functions; in particular, compelling ReLU networks to approximate functions with exponential accuracy as network depth is linearly increased. Our results showed improvements of one to several orders of magnitude in using our initialization and pretraining strat- egy to train ReLU networks to learn various nonlinear func- tions, including non-convex and multi-dimensiona func- tions. This finding is particularly powerful since random initialization and gradient descent are not likely to produce efficient solution their own, even if it can be proven to exist in the set of sufficiently sized ReLU networks.
ImageNet Accuracy
We anticipate the continued development of theoretical im- provements to this work. Of particular importance, we think, is either finding a dense set of dimensiinii functions we can represent efficiently with deep networks, or finding method that more naturally represents multidimensiondl functions. While works like the KAN show it is possible to perform well without those things, we believe them to be important. The fact that our current technique is limited to creating sparse block diagonal matrices is indicative of a need to determine how to use all the weights of dense layers. Another interesting avenue for increasing the technique's ex- pressiveness could be consider the generation of fractals. We disallow such behavior by using Theorem 3.1 to enforce differentiability in the hopes of regularization, but there may be more sophisticated approaches to function modeling that can generate fractals in a controlled manner. Given that the technique in its current form is flexible enough to go into any architecture, is also important to explore possi- ble use cases. We have shown that it will likely not lead to significant improvements classification tasks, but the technique may shine when given an appropriate utility-scale regression task. Overall, we are hopeful that future works by our group and others will help illuminate a complete theory for harnessing the potential exponential power of depth in ReLU and other classes of neural networks.
77.5
ordinary train ordinary validation experimental train
75.0
experimental validation
72.5
70.0
67.5
65.0
62.5
60.0
57.5
10 Epoch
15
Figure& 8. Retraining the classifier of VGG- 16 model on Ima- geNet. The ordinary network uses a learning rate of 1 10-4, and our experimental network uses 1 x 10 At epoch 10, both learning rates decay by a factor 10. and we switch the parameter- ization in the experimental network. Both networks retrain slightly higher than PyTorch 's original reported accuracy of 73.3%.
Figure 8 shows that our network has an advantage early in training, but the fully trained networks achieve comparable accuracy. This is perhaps unsurprising: ordinarily initial- ized and trained networks are already extremely good at classification problems despite the pathological properties of random initialization. This result suggests that highly precise representations of decision boundaries may not be critical performance for such classification problems. In support of this, noticed that it did not seem matter if we switched parameterizations with our technique, even though doing so was critical to our performance on the ID regression problems. A practical scale regression task may be needed for our method to display a significant advantage; we plan such examples as future work.
Impact Statement
This paper presents work whose goal is to enable more efficient neural networks. Future advances along this line could enable the use of much smaller networks in practical applications, which could substantially mitigate the rapidly growing issue of energy usage in large learning systems.
Acknowledgments
M.M. would like to thank Xander Neuwirth for insightful conversations. D.H. was supported in part by the U.S. Na- tional Science Foundation under award number 2442853.
9

---

Compelling ReLU Networks to Exhibit Exponentially Many Lincar Regions at Initialization and During Training
This work was authored in part by the National Renewable Energy Laboratory (NREL), operated by Alliance for Sus- tainable Energy, LLC, for the U.S. Department of Energy (DOE) under Contract No. DE-AC33-08G028300 work was supported by the Laboratory Directed Research and Development (LDRD) Program at NREL. The views ex- pressed in the article do not necessarily represent the views of the DOE or the U.S. Govermment. The U.S. Govermment retains and the publisher, by accepting the article for pub- lication, acknowledges that the U.S. Government retains nonexclusive, paid-up, irrevocable, worldwide license to publish or reproduce the published form of this work, or allow others to do so, for U.S. Government purposes.
In 2009 IEEE conference on computer vision and patlern recognition, pp- 248-255. leee, 2009.
Eckle, K. and Schmidt- Hieber, J. A comparison of deep networks with ReL.U activation function and linear spline- type methods. Neural Networks, 1 10:232-242, 2019.
This
Elbrächter, D. M., Berner, J., and Grohs, P. How degenerate is the parametrization of neural networks with the ReLU activation function? In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Bue, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https::/prooceddingg neurips. cc cc/papes f httpeerrfiieespppp////////// ocl. pdf.
References
Amold, V. On functions of three variables. Doklady Akademi Nauk SSSR, 114 1957.
Frankle, J. and Carbin, M. The lottery ticket hypothesis:
Finding sparse, trainable neural networks, 2019.
Arnold, V. On the representation of continuous functions of many variables by superposition of continuous functions of one variable and addition. Matenaticheskii Sbornik, 48(1):3774, 1959.
Gibou, F., Hyde, D., and Fedkiw, R. Sharp interface ap- proaches and deep learning techniques for multiphase flows. Journal of Computational Physics, 380:442-465 2019. doi: 10. jop.
URL https: 10. 10w./1116/131 j. jep. 2018 05.055... 031.
Chen, M., Jiang, H., Liao, W., and Zhao, T. Efficient approximation of deep ReLU networks for functions on low dimensional manifolds. In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, F., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https://prcceediggg..oom oc httppppee_fllleeepperr/////////9 auSSeeafSbceeesssseeceee3333 Paper. pdf.
Glorot, X. and Bengio, Y. Understanding the diffi- culty of training deep feedforward neural networks. Teh, Y. W. and Titterington, M. (eds.), Proceed- ings of the Thirteenth International Conference on Ar- tificial Intelligncce and Statistics, volume of Pro- ceedings of Machine Learning Research, pp. 249- 256, Chia Laguna Resort, Sardinia, Italy, 13-15 May 2010. PMLR. URL https: https::/ http///poceeeeeeeeeee/ee mmlr. press/v9/
html.
Chen, W. and Ge, Neural characteristic activation analy- sis and geometric parameterization for ReLU networks. In The Tiiht Annual Conference on Neural In- formation Processing Systems, 2024. URL https: // //openreview.. net. / forum? forum?id=7HFFFRR d=FFFgERjjnn...
Hanin, B. Universal function approximation by deep
neural nets with bounded width and ReLU activations. Mathematics, 7(10), 2019. ISSN 2227-7390. doi: 10.3390/math7100099 URL https: /twww//wpppp com/ 2 //////////////
Chmielewski-Anders. A. Activation regions as proxy for understanding neural networks. Master's thesis, KTH Royal Institute of Technology, July 2020.
Hanin, B. and Rolnick, D. Deep ReLU networks have surprisingly few activation patterns. In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https:://proceeed.ngg http:////pppoceeeeennnneeeeeeee neurips. cc cc cc/paper_fiiecccccccccc cc/pappr_fillss/ppeeeeee cc//sppet.filee//ppee/////////// 9 7755271abbaae95a443331f011110111 pdf.
Cybenko, G. Approximation by superpositions of a sig- moidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
Daubechies, I. Vore, R., Foucart, S., Hanin, B., and Petrova, G. Nonlinear approximation and (deep) ReLU networks. Constructive Approximation, 55(1),127-172, 2022.
He, K., Zhang, X., Ren, S., and Sun, J. Delving deep into rectifiers: Surpassing human-level performance on ima- genet classification. In Proceedings of the IEEE Interna- tional Conference on Computer Vision (ICCV), December 2015.
Deng, J., Dong, W., Socher, R., Li, L.-J,, K., and Fei-Fei, L. Imagenet: A large-scale hierarchical image database.
10

---

Compelling ReLU Networks to Exhibit Exponentially Many Linear Regions at Initialization and During Training
He, K., Zhang, X., Ren, S., and Sun, J. Identity mappings in deep residual networks. In Computer Vision-FCCC 2016: 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part IV 14, pp. 630- 645. Springer, 2016.
2020. ISSN 1991-7120. doi: httpss///bbi.ogg///00000ociigg OA-2020-0165. URL httphtttt///gllbll-sscll .org intro
html.
Lu, Z., Pu, H., Wang. F., Hu, Z., and Wang, L. The expressive power of neural networks: A view from the width. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnttt, R. (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc..
Hornik, K., Stinchcombe, M., and White, H. Multilayer feedforward networks are universal approximators. Neural Networks, 2(5):359-36,, 1989. ISSN 0893-6080. doi: http://doo.og////o0oooo999696699 URL
2017. URL attpss:/procceedinngg neurips. cc httppppeer.ieeeeppppp/////////// 5222f6677000e1144400071177111.13 pdf.
Huchette, J., Muñoz, G., Serra, T., and Tsay, C. When deep learning meets polyhedral theory: A survey, 2023. URL ht //ap:s///xxxvv..////a////p htg/bb////// 2305. 00241.
Montanelli, H., Yang, H.,, and Du, Q. Deep ReLU networks overcome the curse of dimensionality for bandlimited functions, 2020.
loffe, S. and Szegedy, C. Batch normalization: Acceler- ating deep network training by reducing internal covari- ate shift, 2015. URL https: /ttp://aaavv.///a//aai org/ abs/ 1502. 030633166 67.
Montufar, G. F., Pascanu, R., Cho, K., and Ben- gio, Y. On the number of linear regions of deep neural networks. M., Cortes, C., Lawrence, N., and Weinberger, K. (eds.), Advances in Neural Information Process- ing Systems, volume 27. Curran Associates, Inc., 2014. URL httpss//prooeeddinsss. cc cc/spper_filee/ppppe///////// http://ppooeeddnnggeeeeei.sssss 00022463000400011770000112222220 pdf.
In Ghahramani, Z., Welling,
Ivanova, I. and Kubat, M. Initialization of neural networks by means of decision trees. Knowledge-Bel -Based Systems, 8 (6):333-344, 1995.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization, 2017.
Kolmogorov, A. On the representation of continuous func- tions of many variables by superposition of continuous functions of one variable and addition. Doklady Akademii Nauk SSSR, 114(5):553 95663-956,1111 1957.
Nag. S., Bhattacharyya, M., Mukherjee, A., and Kundu, R. SERF: Towards better training of deep neural networks using log- log-Softplus ERror activation Function. In Proceed- ings of the IEEF/CVF Winter Conference on Applications of Computer Vision (WACV), pp. 5324-5333, January 2023.
Krizhevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny images. 2009.
Lei Ba, J., Kiros, J. R., and Hinton, G. E. Layer normaliza- tion. ArXiv e-prints, pp. arXiv-1607, 2016.
Park, Y., Lee, S., Kim, G., and Blei, D. M. Unsupervised representation learning via neural activation coding, 2021, URL https: / arxiv. org/ hasp///////a 221/2/1122 04014.
Liang, S. and Srikant, R. Why deep neural networks? CORR, abs/1610.04161, 2016. URL httph:/arxx...co
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
abs/ 04161.
Liu, Z., Wang. Y., Vaidya, S., Ruchle, F,, Halverson, J., Soljačić, M., Hou, Y., and Tegmark, M. KAN: Kolmogorov-Amole networks, 2024. URL https: //arxiv. abs ////2/444.......
Perekrestenko, D., Grohs, P., Elbrächter, D., and Bölcskei, H. The universal approximation power of finite width deep ReLU networks, 2018. URL https: /arxxiv. org/ abs / 111///866..0 01528.
Lu, J., Shen, Z., Yang, H., and Zhang, S. Deep network approximation for smooth functions. SIAM Journal on Mathematical Analysis, 53(5):5465-5500 jan 2021. doi: 10.1137/20013446955 URL https:tt///// //t:::///iiiee/ or1/10. 0057/20m1346995
Qi, X., Wei, Y., Mei, X., Chellali, R., and Yang. S. Com- parative analysis of the linear regions in ReL.U and LeakyReLU networks. In Luo, B., Cheng, L., Wu, Z.-G., Li, H., and Li, C. (eds.), Neural Information Processing, pp. 528-539, Singapore, 2024. Springer Nature Singa- pore. ISBN 978-981-0 99-8882--8
Lu, L., Shin, Y., Su, Y., and Karniadakis, G. E. Dying ReLU and initialization: Theory and numerical examples. Com- munications in Computational Physics, 287511667

---

Compelling ReLU Networks to Exhibit Exponentially Many Lincar Regions at Initialization and During Training
Rolnick, D. and Kording, K. Reverse-engineering deep
ReLU networks. In III, H. D. and Singh, A. (eds.), Pro- ceedings of the 37th International Conference Ma- chine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 8178-8181 PMLR, 13-18 Jul 2020. URL htLhtttp://pptt /ttp:eeee///oooeddingg/g mlr. press// v119 ww11 2l199rolniik22a.httmm html.
Serra, T., Tjandraatmadja, C., and Ramalingam, S. Bound- ing and counting linear regions of deep neural net- works, 2018. URL https://arxiv.om /bs/ 1711.02111
Shin, Y. and Karniadakis, G. E. Trainability of ReLU net- works and data-dependent initialization. Journal of Ma- chine Learning for Modeling and Computing, 1(1):39-74,
2020. ISSN 2689-3967.
Simonyan, K. and Zisserman, A. Very deep convolu- tional networks for large-scale image recognition. arXiv preprint 1409: 1556, 2014.
Singh, D. and Sreejith, G. J. Initializing ReLU networks in an expressive subspace of weights, 2021.
Telgarsky, M. Representation benefits of deep feedforward networks, 2015.
Wang, Q. et al. Exponential convergence of the deep neu- ral network approximation for analytic functions. arXiv preprint arXiv:1807.00299 2018.
Yarotsky, D. Error bounds for approximations with deep ReLU networks. Neural Networks, 94:103-114, 2017. ISSN 0893-6080.
doi:
URL sttpss//wwwscceeeeeddrree com/ scie scciamee//rttcee/////33333111111
Yeh, I.C. Concrete Compressive Strength.
UCI
Machine Learning Repository, 1998. DOI:
https//tbi.ogg/104444///KKK
Zaslavsky, T. Facing up to Arrangements: Face-Coun
Formulas for Partitions of Space by Hyperplanes. Amer- ican Mathematical Society: Memoirs of the American Mathematical Society. American Mathematical Society, 1975. ISBN 9780821818541 URL https://books. google. www. wwtp/o/www./...occoooooooooooo.t Picin-iiiiii---eee -i-oess-ii.----TTAAAAAAAAAL
Zhang, L., Naitzat, G., and Lim, L.-H. Tropical geometry of deep neural networks. In Dy, and Krause, A. (eds.), Proceedings of the 35th International Conference on Ma- chine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5824-5832. PMLR, 10-15 Jul 2018. URL httts:: http:p:://ppopeeeee http///pooeenng..cc/o mlr .tw.sngss..r.p....///.... v8 / zhang1 81. html.
12

---

Compelling ReLU Networks to Exhibit Exponentially Many Lincar Regions at Initialization and During Training
A. Algorithm and Theory
bila
bins
biles
sam
sum
"No ReLU between blocks
blass
bins
bius
binss
bius
bias
Figure 9. Extending our results into a larger network. ReLU should not used in the layers between the blocks. Colors correspond to Figure 2.
A.1. Initialization and Pretraining Algorithm
The initialization step of our algorithm is to generate vector A = [aa, a1....a,]' where each is randomized in (0, 1).
Given this A, the pretraining step of our algorithm (in the experiments in Section 4) sets the weights of the input (/), hidden (H,, S i < n - 1), and output (O) layers of the network as follows:
0
[(x)=
r
0
0g
1
#[S:/a
Ss,(a; - a?)]
0
S./4
- Sa/(a, a
0
11(x)
x ReLUU(Hii10
S./a:
Si/(a: (a: a3)
S,a,+1
0
0
S
( = [1 Sn/an -S.((an - a 0] x ReLU(H,,1(x)),
where S; can either be chosen independently or chosen based on A. In the latter case, Equation 3.1 gives S; = 5i/si-1 (1 - a:)aa 41)1 For this version, one must decide whether to add or subtract triangle waves from the sum neuron based on whether the target function is convex or concave, respectively. The version of the algorithm used in Section onward does have this stipulation and always follows Equation 3.1. Additionally, expands the input domain to [-1, 1] and flips the triangles upside down to compose "v"-shaped functions instead:
-0.5
1
0.5
I(x)
8.3
0.3
00
00
13

---

Compelling ReLU Networks to Exhibit Exponentially Many Linear Regions at Initialization and During Training
-1
0
a++l
1
ai+1 - 1
a;(1 ai+1)
(x
0
a1(1-
a.(1-a++1)
a11111
x
1-0.
1-0:
1-0;
0
0
0
aj 0i+1)
((x)= = [1 1 1 -1] x ReLU(Hn-1(z)).
This assignment of I, H, and O is used in each iteration of the pretraining algorithm to set the weights of each layer before the forward pass. The backward pass can then propagate the gradients back through this weight setting procedure to update the vector A containing the triangle peaks.
After pretraining, the weights can then be initialized once more based on the learned vector A, and then updated directly using regular gradient descent in a second round of optimization. Full pseudocode is listed in Algorithm
Algorithm 1 Initialization and Pretraining
A f Random (0, 1)")
while Epochs > 0 do
Network + Set (ei__eegghts()) {Set weights as above each iteration]
Loss + (Network(z)) y)²
Network-Gradient + DerivativveLoss, Network) (Regular Backpropagation)
A-Gradient - Derivative(Nettork, A) (Backpropaaat through weight setting)
Gradient Network A-Gradient
A + A - x Gradient (Update A, Not the network)
end while
A.2. Terminology
Before presenting further formal mathematical details of method, we first briefly review few pieces of basic ReI.U network terminology used in the paper. The reader is referred to Chnielewski-Anders (2020) for an excellent alternative presentation of these terms.
An activation pattern is a boolean mask that tracks which neurons in a network have their output zeroed by ReLUU activations. The activation regions a ReLU network are connected (and can be shown to be convex) sets of inputs on which the activation pattern is constant. Since the action of the ReLU activation function is constant, the network output over an activation region equivalent to the case where there is no activation function and the associated zeroed neurons are absent; therefore, the network output behaves linearly over the inputs in the activation region. Relatedly, a linear region is set of inputs which the network output behaves linearly with respect to its inputs. It may consist of multiple neighboring activation regions. Another important concept is the boundary of neuron, as described in Rolnick & Kording (2020): the set of inputs for which the neuron outputs O, independently of ReLU. The boundary of a neuron is precisely the boundary of the activation regions it adds to the network. Chen & Ge (2024) refers to this set as the characteristic activation boundary since these are the boundaries of the activation regions.
We note that although works like ours are theoretical papers that leverage these concepts, studying these ideas can lead to interesting applied learning research. For instance, Rolnick & Kording (2020) leverages theoretical works like those cited in our related work discussion for an exciting privacy application: it is proven that ReLU network's 's output can often be provably used to reverse engineer the architecture of a ReL.U network, up to isomorphism.
A.3. Necessary Conditions for Differentiability
For convenience, we first restate the functions defined in the main body of the paper.
0 x < a;
Tx(x)
02
S r <
T-ac
14

---

Compelling ReLU Networks to Exhibit Exponentially Many Lincar Regions at Initialization and During Training
0<а<a I= di <
(x)
-x - (3- -
F(x) = Σ s (2).
The goal of this section is to show how select the s; based on a; in manner where the derivative (x) defined and continuous on all of [0, 1]. We begin by assuming that
00
F(x)= = Σ (x))
We will see that the resulting choice of s; ensures uniform convergence of the derivative terms, that the derivative of the infinite sum is indeed infinite sum of the derivatives. Fortunately, the left and right derivatives F` (z) and FL (z) already exist everywhere, since each bend in each W; (where the full derivative of F is undefined) is assigned the slope of the line
segment to its left or right, respectively. The 8; scaling values will have to be chosen appropriately so that F4 (x) and F" (x) are equal for all bend points.
Notationally, we will denote the sorted x-locations of the peaks and valleys of (x) by the lists P. {i (.()) = } and Vi {x: (xrx)= 0}. We will use the list B, to reference the locations of all non binedifferentiable points, which we refer to as bends. B, = P. U V. fa(x) = Σn=o Sn, Wn (xx) will denote finite depth approx- imations up to but including layer The error function (x)x) > S₁ (x)) F(x) fi()) will represent the error between the finite approximation and the infinite depth network. This odd split around layer makes the proofs cleaner.
Tx(x)
T,(x)
ag
aj
W,(x) (x))((x))
Figure 10 highlights some important properties about composing triangle functions. Peaks alternate with val- leys. Peak locations in one layer become valleys in the next. Valleys in layer remain valleys all future layers since 0 is fixed point of each T; To produce W,, each line segment of W,-1 becomes dilated copy of T, Each triangle function has two distinct slopes, 1/0; and -1/(1 - a.), which are dilated by the chain rule during the composition. On negative slopes of W,-1, the input to layer is reversed, so those copies of T; are reflected. Due to the reflection, the slopes of W; on each side of could
Figure 10. Triangle functions Tb Ti, and triangle wave result- ing from their composition. Note how Ti is reflected in W,.
peak valley proportional. Alternatively, consider that each side of peak in W,-1. there is neighborhood of points that are greater than a; and are composed with the same line segment of T; that has slope -1/(1- a.). Either way, important to note that the slopes on each side of a bend scale identically during each composition.
Before we begin reasoning about F((x),, it can simplify the analysis to only consider the derivative of the error function Ex(x). Lemma A.1. for P,, (((x) is defined if and only if (.(x)) defined.
15

---

Compelling ReLU Networks to Exhibit Exponentially Many Lincar Regions at Initialization and During Training
Proof. All Wn (x) for i are differentiable at P. since will lie in the interior of linear region of W,, Therefore, f((x)= > - sn (x) exists at these points. Since E + f = F", F²)x) is defined if and only (x) is defined. =
Thanks to the previous lemma, we only need to work with E,. Here compute the right derivative (F.)4 (a:) of the error function at point x. The left derivative will only be different by constant factor.
Lemma A.2. For all E Ps E2((x) and E'_ (x) are proportional
8:
86+1
Σ n=
8n
(4)
ai+1
0k
k=++2
Proof. Let 24 be some point in P., and let lc be its index in any list it appears in. To calculate the value of E (2x) Em=i (IN) we will have to find the slope of the linear intervals to the immediate right of T&k for all W,. We will use R2 to represent W (xx). The first term in the sum will be Rg Since the derivatives of composed functions will multiply from the chain rule, so the value of the next term is W (I+a) = (W+,((()))))
Ti+1 has two linear segments, giving two slope possibilities to multiply by. The correct one to choose is -1/(1 a.+1) because it is "active" around zye (ig a peak of W,, so (rx) > 01+1 for x E (Bi+1 [h 1]. B,+1 ik- + 1])). This gives W (1/41(x))
8i+1 Rs (i-aaai.>>
Note
that the second term has the opposite sign as the first
For all remaining terms, since 24 was in P., it is in V, for i. For x E (Bi+1 - 11, BJ+ [k + 1)), (2()) < aj+1 and the chain rule applies the slope 1/ 1/a,+1. Since this slope positive, every remaining term continues have the opposite sign as the first term. Summing up all the terms with the coefficients 8;, and factoring out Rg will yield the desired formula. Note that this same derivation applies to the left sided derivatives well because the "active" slopes of T2+ (W;) are all the same whether bend in W; is approached from the left or the right. The initial slope constant Lg will just be different. O
Lemma A.3. If (x) E (x), E' (x) must be equal to 0.
Proof. Let S represent Equation 4, and and be the constants of proportionality for the directional derivatives. E4 EL,, then Ry.S- S for all x E P.. Since W, is comprised of alternating positive and negatively sloped line segments, R2 and L, have opposite signs. The only way to satisfy the equation then is if S O. Consequently, E'(x) = 0 for all x E P..
The following lemma shows that to calculate the derivative at of F(x) for any bend point æ, one needs only to compute the derivative of the finite approximation fi (which excludes W,). This will be useful later for proving other results.
Lemma A.4. For all x E P::
F'(x) f((x) Σ (.)).
(5)
Proof. From the previous lemma have Ex(x) 0 whenever the directional derivatives are equal. F(x) Ej 8y (x)) + F((x). The first terms are differentiable at the points P3 since those points lie between the discontinuities in B.- Therefore F'(x)) is defined and can be calculated using the finite sum. visualization of this lemma provided in Figure 11.
We now prove our main theorem, which shows that there is way to sum the triangular waveforms W, so that the resulting approximation converges to continuously differentiable function. The idea of the proof is that much of the formula for Ex(x) will be shared between two successive generations of peaks. Once they are both valleys, they will be treated the same by the remaining compositions, so the sizes of their remaining discontinuities will need to proportional.
Theorem 3.1. F'(x) is continuous on [0, 1] only if the scaling coefficients are selected based on a; according to:
8;41 = s;(1 1 04++ )0442-
16

---

Compelling ReLU Networks to Exhibit Exponentially Many Lincar Regions at Initialization and During Training
Proof. Rewriting Equation 4 (which is equal to for layers and i 1 in the following way:
s,(1 a(t1) 8--1 +
86+2
as42
0kk
n=++3
81+1 a(42) 8142 +
Sn
ak
kmi+433
allows for substitution eliminate the infinite
1-ai+2
1 -
(1 ai+1) = 8i+1 +
8141.
di+2
Collecting all the terms gives
s;(1 a++1)
8141
1 1-0++2
0,42
which simplifies to the desired result.
Figure 11. The derivatives of the first few stages of approximation. Notice that each time a constant segment "splits." the two neighboring segments adjacent to the split monotonically converge back to original value (marked colored point corresponding the step originates from).
A.4. Sufficiency for differentiability
This form of the scaling equation derived in the previous section is rather interesting. Since the ratio of two successive scaling terms is (1 04+1 )a,42, factors of both a; and are present in This has few implications. Firstly, if any a, is 0 or I, subsequent scales will all be O, essentially freezing the corresponding neural network at a finite depth. Secondly, having both a, and - will cancel whichever slope multiplier T; contributes to W; at each point x, leaving behind the other term, which is less than
If we ensure each a; is bounded away from or 1 by being drawn from the an interval such that c < a < c for some 0 < e < 0.5, then the maximum value of W is always upper bounded by (1 c) which is sufficient for uniform convergence. This condition also means that the bends points (and thus the activation regions of the corresponding neural network) will become dense in Jo, 1], as each region is partitioned (at worst) in a c:
ratio.
Lastly, we can show that bounds on ag and our choice of scaling values are sufficient for the existence of F" on the bend points, in addition to being necessary for the existence of the derivative on the bend points, our choice of scaling is sufficient when a; are bounded away from or 1.
Theorem A. On bend points x, F'(x) exists if we can find e > 0 such that c S a, S c.for all and choose all s; according Equation 3.1. I.
17

---

Compelling ReLU Networks to Exhibit Exponentially Many Linear Regions at Initialization and During Training
Proof. We begin by considering Equation 4 for layer i (it equals 0 by Theorem A.3).:
II
1
$ 1 - as+1 81+1 +
1=++2
Rm-+2
We will prove our result by substituting Equation 3.1 into this formula, and then verifying that the resulting equation is valid. First we would like to rewrite each occurrence of in terms of 8;. Equation 3.1 gives recurrence relation. Converting it to an non-recursive representation, we have:
x+1 II
Sn 9,
II j=i+1
as
oR
(6)
When we substitute this into Equation 4, three things happen: each term is divisible by 8 so 8; cancels out, every factor in the product except the last cancels, and 0:41 cancels. This leaves
= 4:42 (1 ai+2)a:43 a1+2)) (i43)a;-44
II (1-0m) n=++2 M=--2
This equation has a meaningful interpretation that is important to the argument. 1 the full size of the initial derivative discontinuity at point P. and each term on the other side represents proportionally how much the discontinuity closed for each triangle wave that is added. Every time wave is added, it subtracts the first term appearing on the right hand side, the right accounts for fraction (equal a,) of the remaining
The following argument shows that each term of the discontinuity, guaranteeing its disappearance in the limit. Inductively, we can show:
n-1
Σ On II n=1+2
(1 (1-0p 0m)
II (1- (1-am) mmi+2
8
In words, this means that the first term appearing on the right Equation 7 repeatedly subtracted, that term is always equal to a, times the left side. As base case, have (1 a:+2) (1 a,+2). Assuming the above equation holds for all previous values of j.
1+1
J
Σ On I - (1-0m))
01 1
Σ On
II (1 am)) - aj+1
II (1 am)),
n=
m=1+2
n=++2
m=++2
m=i+2
using the inductive hypothesis make the substitution
H+1
II (m-am)) ajji m=-+2
aj+1
II (1-am))
II m=i+2
(1 (-mam))
m=i+2
Since all e < a; < 1 c, the size of the discontinuity at the points P; is upper bounded by the exponentially decaying series - (1-c)a, which approaches zero.
A.5. Error Decay
Lemma A.7. The ratio 8142/8; 8; at most 0.25.
Proof. by applying Equation 3.1 twice, we have
8142 s;(1 a,41)(1 a; + 2)
To maximize 8:42, we choose 0:41 = 0 and 0;43 = 1. The quantity a442 - au4o a parabola with a maximum of 0.25 at a,+2 = 0.5.
Since each W; takes values between and I, its contribution to F is bounded by 8;, Since the s, decay exponentially, one could construct geometric series to bound the error of the approximation and arrive an exponential rate of decay.
18

---

Compelling ReLU Networks to Exhibit Exponentially Many Lincar Regions at Initialization and During Training
A.6. Second Derivatives
Here we show that any function represented by one of these networks that not y x² does not have continuous second derivative, as it will not be defined at the bend locations. To show this we will sample discrete series of Ay/ Ax values from F' (2) and show that the limits of these series the right and left are not the same (unless all a, 0.5), which implies that (x) does not exist (see Figure 12 below). First we will produce the series of Az. Let be the location of peak of W, and let in and In be its immediate neighbors in Binn.
Lemma A.8. Ifc c < a4 < - for all i, we have nim In = lim, -0 In = Z. Furthermore, Tn: In + for any finite i.
Proof. Let and L denote the magnitude of W on the left and right of x. x is a peak location of W,, so the right side slope negative and the left is positive. Solving for the location of Ti+1 (W:())) on each side gives I = a - (1 0j- }
and r = x + (1 d/.1)/R. R.
On each subsequent iteration i + (n 2 2), x is valley point and the Ar intervals get multiplied by attn- Since is valley point, the right slope is positive and the left is negative. The slope magnitues are given by z-t, and 1 F'
since Wi+h ranges from O to over these spans. Solving for the new peaks again gives 4 = 14 (n) and Tn-1 = x + ar+1(nn z). The resulting non-recursive formulas are:
x
a++1
II m=
0 and Fn - x
1
0++1
0+4m-
R
m=2
The right hand sides will never be equal to zero with finite number of terms since parameters are bounded away from 0 and 1 by
(x, fx()))
(x F (x)) (r (((r))
(x))
(x F (x))
(12
(2((2))
(r2. (rz)) (r, F (rr,))
(r,, F (r,))
(ra f ('a(Fa))
Figure 12. An illustration of attempting to calculate the second derivative. The points in the series approaching x from the right are marked. We rely the fact that at bend points, the first derivative converges back to the value had finite point in the approximation. as * 0.5 and all other parameters are set to 0.5, which will cause the left and right sets of points to lie on lines with different slopes.
Next derive the values of Ay complete the proof.
Theorem A.9. F(x) cannot be twice differentiable unless F(x) x?.
Proof. The points I, and rn are all peak locations, Equation 5 gives their derivative values as fi (rn). In our argument for sufficiency, we reasoned about the sizes of the discontinuities in I' at æ. Since I, and rn always lie on the linear intervals surrounding as n > oc, we can get the value of f((x)) - (r+n(rn) using Equation 8 with the initial discontinuity size set to Rs; rather than 1. Focusing on the right hand side, we get:
f1(x)) ((nn(r)) = R * 8; II (1 a+tm)-
m==
Taking Ay/ Ar gives series:
R²s: (1 - 0:+1)
II
Om
Om
m=3+2
19

---

Compelling ReLU Networks to Exhibit Exponentially Many Linear Regions at Initialization and During Training
The issue that arises is that the derivation on the left is identical, except for a replacement of R2² by L,2 The only way for these formulas agree, then, is for R T,2, which implies 0; = =1 a, 0.5. Since this argument applies at any layer, then all parameters must be 0.5 (which approximates y y= ==x²).
A.7. Monotonicity and Continuity of Derivatives
Each of the f/ are composed of constant value segments. We will show that those values are monotonically decreasing (this can be seen in Fig This can extend into the limit to show that F" is monotone decreasing and that F is concave.
Lemma A.10. The function F(x)) is concave when all 8; are chosen according Equation 3.1.
Proof. To establish this, we will introduce the list Y = [F'() f[(Vi(n)), ("(4+1112]] for 0 I n S 2', which tracks the values of F' at the 1hh set of valley points. All but the first and last points will have been peaks at some point in their history, so Equation 5 gives the value of those derivatives as f/-
We establish two inductive invariants. One is that the y-values in the list Y, remain sorted in descending order. The other is that Y [m] 2 (x) 2 Y'In= + 1] for Vi[n] < x < Vi(n + 1], indicating that the constant value segments of f. lie in between the limits in the list Y, Together, these two facts imply that each iteration of the approximation f. is concave. This can then be used to prove that their limit F is also concave.
As the base case, fo is a line with derivative 0, and Vo contains its two endpoints. Yg is positive for the left endpoint (negative for right) since on the far edges F" is sum of a series of positive (or negative) slopes. Therefore, both the points in Y' are in descending sorted order. The second part of the invariant is true since 0 is in between those values.
Consider an arbitrary interval (Vi[m), Vi[ne + 1J) of fi. This entire interval is between two valley points, so Jí (which has not added W2 yet) is some constant value, which we know from the second inductive hypothesis is in between Y/[nx] and I/In + 1]. The point x E P3 n [m), Vi [n- + 1I) will have F((x) = f((x), and it will become member of V++1- This means we will have 1+ [2n] > Y [2n + 1] > Y++1(2n + 2]. maintaining sorted order of Y'.
Adding 8, W takes f. to f. + 1 splitting each constant valued interval in two about the points P.. increasing the left side, and decreasing the right side. Recalling from the derivation of Equation 4 all terms but the first in the sum have the same sign, so the limiting values in Y/ are approached monotonically. Using the first inductive hypothesis, we have on the left interval
|m = Y44 [2m] > K-11 > J = Y/++ [2n + 1] and on the right we have S/ = Y++1 12m + 1] > fe+1 > (i + 1] = Y/12n= + 2]. And so each constant interval fi+1 remains bounded by the limits in Y/+1
We will now show by contradiction that the limit F of the sequence of concave fü is also concave. Assume that F is non-concave. Then there exist points a, b, and e such that F(b) lies strictly below the line connecting the points (a, F(a)) and (c. F(c)). Let us imagine it is below the line by an amount Since at each point f; converges to F, we can find ia such that faa F(a)= < e/2, etc..., we take their limiting values, the entire line connecting (a, fa)) and (c, f((()) is no more than e/2 lower than the line between (a, F(a)) and (c, F(c)). fbb is also no more than c/2 higher than F(b), thus fbb must still lie below the line between (a, fa)a and (c, f((e), making Sa non-concave and producing a contradiction.
max(ia, is, in). Since Si(a) and fi(e) are no more than e/2 lower than
Lastly, we briefly sketch out why F' is continuous. It relies on some of our earlier reasoning. Monotonicity of the derivative makes continuity easy to show, because when æ1 within 8 of 22 has f((1 within of / (122), so do all intermediate values of x. We can establish continuity of F" at bend points x easily by using Equation 8. We can pick an i so that the constant value segments of f are within of F'(x)) and then use the next iteration of bend points (since the constant intervals split, but the new segments near Fn converge monotonically towards it) to find 6. In the case of continuity for non bend points x, they sit inside constant-valued interval of fi for each i. We can choose i such that En= (1 c)" < c/2 because this series constrains how far derivative values can move in the limit, and then use the constant interval x is situated in to find 8.
A.8. Activation Region Counting and Zaslavsky's Theorem
In the coming sections, we present the results of using our 4-neuron-wide construction as an activation function on more complicated datasets. It will be useful to know the impact of this approach on the activation region count when assessing how to best spend a network's 's parameter budget. To build up to it, we will provide an informal introduction of Zaslavsky's 's theorem (Zaslavsky, 1975). The activation boundaries of ReLU neurons in a single hidden layer network form a hyperplane arrangement. Counting the number of cells, which are convex connected components of space separated by the hyperplanes,
20

---

Compelling ReLU Networks to Exhibit Exponentially Many Lincar Regions at Initialization and During Training
equivalent to determining the number of activation regions produced by the shallow ReLU network. A D-dimensional hyperplane arrangement said be in general configuration when every of D hyperplanes intersect in unique point, every set of D hyperplanes intersect in unique line, etc. General configuration is essentially what you would expect on average from setting the orientations and offsets of the hyperplanes randomly (and would thus be applicable to a single hidden layer ReLU network). Zaslavsky's theorem states that
Theorem A.11. When in general configuration, the number of cells (R()) created by D-dimensional arrangement of hyperplanes is
D
n
R
D
d=
To compute this sum, one would go down to the row of Pascal's triangle corresponding the number of planes and sum the first D entries (see Figure 13 for visual example). It is a known fact that the sequence of the dth entry for each row grows to the dhh power. So as the number of hyperplanes tends towards infinity, this sum is dominated by the D term, which grows to the power D. In other words, the number of linear regions formed by single hidden layer ReLU network grows exponentially with respect to its input dimension. This property partly explains why neural networks are successful learning high-dimensional functions, even when other classical methods become intractable.
1
3
4
1
2
1
7
5
1
4
6
4
1
6
1
10
10
Figure 13. lines dividing 2-dimensional space creates cells. This is calculated by going down (for the number of lines) and summing the numbers indices 1, and 2 (for the dimension). Also note that there is one 2D plane with 3 lines and points of intersection in this configuration, corresponding (in that order) the highlighted entries in Pascal's triangle.
Thanks to the general configuration of the hyperplanes, the number of lower dimensional objects (i.e., points, lines, planes, etc.) are given by the entries in Pascal's triangle. So a different way to phrase Zaslavsky's 's thcorem that the number of cells created by the arrangement is equal the sum of all these owerrdimensiooal objects, or that each nover-dimensional object could be "assigned"" cell. There is striking similarity in the intuitions behind the recurrence that generates Pascal's triangle, and the calculation of the numbers of lower-dimensional objects created from hyperplane arrangement. In the case of Pascal's is triangle, if one wished to know how to choose 3 items from 6, one could reason that if item 6 is included, 2 items would be chosen from the remaining 5, and if item is excluded, would be chosen from the remaining 5, and therefore (9) = ( + (5) Now consider the case of planes partitioning 3-space, and the addition a 4th plane. The total number lower-ding dineer-dimesionnll objects would found by including those that are part of the original planes (1 3-space, planes, 3 lines, point), and adding those that the 4th plane creates (1 plane, lines, points). One could also picture that the new 4th plane "cuts" the existing 3-cells, and find the number of new cells added, one could examine the projection of the 3 existing planes onto the 4th (shown in Figure 13), and count the 2-cells that appear. Either reasoning leads to (()) = R("=") + (()=)). This similarity between the recurrences means that if the initial conditions can be lined up suitably. Zaslavsky's 's theorem can be proven by induction over Pascal's 's triangle.
In the case of our architecture, using our I-dimensional construction as an activation function will generate n generally configured sets of m parallel hyperplanes. To account for this, a slight modification is made to the recurrence. Adding an additional set of m hyperplanes would add m times as many regions, as each of the lower dimensional objects in the
21

---

Compelling ReLU Networks to Exhibit Exponentially Many Linear Regions at Initialization and During Training
existing configuration would project onto each of the m additional hyperplanes. The effect that this has on the formula is that R("D") (("")"") + a(".__T)) Inducting over Pascal's triangle (with base case of R(",")
+ nm) would give the non-recursive formula of R D = Ei (2). This means that our architecture (with single hidden layer of depth 5 convex function blocks) would be generating 32 times as many regions as an ordinary single layer of ReLU, which is a fantastic tradeoff once the layers are wide enough (both so that the largest exponent dominates the sum in Zaslavsky's s theorem, and so that only a few neurons would be sacrificed to pay for the new parameters in the activations). Of course, the effect on accuracy will all depend on how well these regions can be utilized.
B. Additional Experiments
B.1. Learning Rates
All results in the main body of the paper used a constant learning rate of 10-3, In this appendix, we considered an ablation study on the learning rate for the task of learning = x². As seen in Figure 14, the learning rate we selected was approximately optimal for both our method as well default network training. We note that for this ablation study, constant 1000 epochs were run, which explains why both methods perform worse as the learning rate becomes minuscule. At small learning rates, what is really measured is how close of a guess the initialization is to the target function. Our networks are preforming better here simply because they are always outputting convex functions. But this only accounts for losses on the order of 10-4, which indicates that in the more reasonable learning rate ranges, our pretraining is performing meaningful function and enabling order-of magnnnid improvements over default network training.
Effect of Learning Rate on y=x
-2
MSE Loss (Logia Scale)
-3-
-4-
-6
Pretrained
-7
Default Network
Learning rate (Log10 Scale)
B.2. Real-World Data and Classification Problems
Here we present few preliminary results on extending our pretraining technique to classification problems and real-world datasets. The classification problem we chose the classic two spirals dataset, and we selected the UCI dataset "Concrete Compressive Strength" (Yeh, 1998) for real-world regression task. The concrete dataset has 8 numerical features that can be used to predict the compressive strength of concrete sample.
Figure 14. Learning y = x² at various learning rates for 1000 epochs. The figure shows the log losses of the best model of 30 for networks trained according to the methods in this paper versus random initial- ization and gradient descent ("Default Network"). For high learning rates, neither learns bocause the steps are too large. For low learning rates (helow 10-5), the steps too small, and our networks are likely deriving an implicit advantage from being forcibly initialized to convex function. Both methods are able to converge for learning rates in between 10-4 and 10-2, one could run for more epochs to see a similar advantage of our method smaller learning rates.
The networks are set up as described before, with our 4-neuron-wide networks acting as 1D to 1D activation functions inside randomly initialized standard linear lay- ers. In these experiments, we use one "hidden layer" of networks (which we choose to have depth 5 in tests). The geometric interpretation of this is that are setting up one-dimensional convex functions oriented in random directions the input space, and then taking linear combination of them as the network output. In the case of classification, the loss function is simply swapped for cross entropy.
After our pretraining phase, there are two choices of how to conduct the second phase of training (training matrix entries directly). All the parameters could be freed from constraints ("dense"), or the smaller 4-neuron subnetworks could be kept isolated from each other (but otherwise have their parameters freed). the case where the 4-neuron networks remain in isolation, the weight matrices of the hidden layers will have block diagonal structure (block size 4-the width of each subnetwork). Thus, consider two fair (same number of free parameters) comparisons in this subsection: (1) dense versions of our and Kaiming-inn initialized networks, and (2) block diagonal versions of our and Kaiming- inittaliiie networks.
22

---

Compelling ReLU Networks to Exhibit Exponentially Many Lincar Regions at Initialization and During Training
Concrete Strength Prediction
Concrete Strength Prediction (Block Diagonal Networks)
ordinary_trail train
ordinary_train
7-
ordinary jest
ordinary_tee
experimental train
experimental train
experimental test
experimental test
Loss
5-
Loss
U
Log
3-
1-
Epoch
Epoch
Figure 15. Train/test loss plots for Kaiming-initializedd ("ordinary") fully-connected networks and our method ("experimental"), Our method has two steps: pretriaining on triangle peaks, followed by the optimization of the raw matrix weights. The switch-off is at epech 500, hence associated visible change the loss curves. The block diagonal variants of networks (right) are generally worse at the task (test losses 30.1 (ours) and 40.8 (Kaiming)) than the dense variants (losses of 22.3 (ours) and 21.2 (Kaiming)). Our experimental networks outperform by up to an order magnitude in block diagonal case. We used of our convex blocks (i.e., all weight matrices are size 128, including for standard comparison networks).
Prediction of Paperimential Kelmere (brick disgone)
Prediction Stancard Network: (blcck diugonal)
0.81
10-
00
60-
2:4
-05
-35
421
-10-
-1.
-13
-2.0
0.00
-15 -2.0
Figure 16. Class predictions of block diagonal networks on a standard two-spiral dataset; ours (left) and Kaiming- iiniiing-iitttalzeedd (right). While the cross-entropy losses are comparable for the dense-matrix variants of both networks, when block diagonal structure is imposed, Kaiming initialization fails to learn the spiral. Note that the colors of the network class predictions are inverted for visibility. Cross-entropy losses are 0.0032 and 0.63 respectively. We used 16 our convex blocks, so weight matrices are by 64.
As discussed below and the figure captions, we find that while the dense variant our method ties or slightly worse than a regular fully-connected network of the same dimensions, in the block diagonal case, our experimental networks counterparts. This makes sense in light of the experiments from the main body, where we can effectively shape the output of 4-neuron-wide networks better than random initializations, but where ensembles of our networks (see approximation of 3:3 x in Figure 6) get filled in with noise by gradient descent during the second training stage. This again highlights the need for more mathematical developments to provide a better extension into higher- dimensioal nonconvex functions.
significantly outperform their Kaiming-initialin
Nonetheless, while we believe there is much room for future work to improve higher-dimensional results, Figures 15
23

---

Compelling ReLU Networks to Exhibit Exponentially Many Lincar Regions at Initialization and During Training
and 16 already show impressive results using our current approach. In the case of the concrete problem (Figure 15), our experimental network outperforms standard
network when block diagonality is enforced. In the case of the two-spiral classification task (Figure 16), our network is able to learn accurate decision boundary (left subfigure), whereas a standard network constrained to be block diagonal fails to learn (right subfigure). When dense weight matrices are trained, our networks are almost able to tie with the standard initializations, although convergence can take longer. These results suggest that our method might quite powerful when its parameter budget is spent on greater width and depth of convex function blocks (as in Figure 9) instead of filling in dense matrices.
Our two-step training approach adds some practical challenges, such as deciding when to switch parameterizations for optimal convergence time. Additionally, since the optimization variables different, the optimizer will have to restart any momentum adaptive learning rates when the switch is made, which can sometimes cause loss to temporarily spike. We lowered the learning rate on the second step to avoid this. Further interesting optimizations of our approach (c.g., training another network to inform our algorithm when to switch parameterizations) are imagined as future work.
B.3. Image Classification on CIFAR-10
Cifar-10 Accuracy with Small Architecture
CIFAR-10 Accuracy with VGG-16
90
100
90
80
70
70
50
ordinary
ordinary train
50
40
ordinary validation
ordinary validation
experimental train
experimental train
experimental validation
experimental validation
40
10
20
30
40
50
0
20
40
60
80
100
120
140
160
Epoch
Epoch
Figure 17. Results for CIFAR-IO experiments. Our ("experimental") training and validations are generally comparable to their Kaiming- initialized ("ordinary"") counterparts. The small architectures trained with Adam learning rate of 0.001, while the VGG experiments are trained with SGD, following a learning rate schedule with a 10x drop at epochs 80 and 120. The ordinary network uses an initial learning rate of 0.1, and the experimental network 0.01. No parameterization switches occur with method.
A nice feature of our method is that it can be used anywhere dense layers appear in networks, which enables its use in CNN architectures. Here we demonstrate its application for image classification on CIFAR-I0 (Krizhevsky et al.. 2009). Our networks are inserted into the dense layers of VGG-16, as well as a small-scale CNN architecture of convolutions (channel depths + 32 + 64 - 128 with
kernels) followed by a single hidden layer dense classifier of 256 neurons, whose width was reduced slightly to 247 to pay for the extra parameters when our method was used. The results get comparable between the two approaches (similar the ImageNet experiments in Section 6). Again notice that method requires lower learning rate for stability, and that switching parameterizztions does not significantly impact accuracy.
C. Source Code Release
implementation of our technique can be found http:///gtttttuccoomm////trraaa/
24


Reviews:
[{"review_id": "PlxU3vPCQR", "reviewer": "Reviewer_JSad", "summary": "This paper shows how to build better regressions with ReLU feedforward networks. The key idea is to exploit the piecewise linear representation produced by such networks, with the philosophy that models with more of such pieces are likely to better interpolate the function of interest. These pieces are typically called linear regions in the ML literature. In the context of this paper, each piece corresponds to a different gradient of the function being approximated by the regression. For nonlinear functions, it stands to reason that exponentially many pieces are needed for ensuring a good overall approximation\n\nThere have been a number of papers that show how to obtain a model with an exponential number of linear regions on the network depth. In practice, however, the average number of linear regions is typically polynomial at best when the parameters are obtained from commonly used initializations and also from training by gradient descent regardless of how they were initialized.\n\nThe differentiation in this paper is that most of the training (described as pretraining) is carried out through a parameterized space of models of high expressiveness. By adjusting the peaks and valleys produced by each layer, the ordinary parameters (weights and biases) are obtained automatically from those choices. At the very end, regular training with Adam over the parameters is carried out for a limited time.\n\n**In full disclosure, I have previously reviewed this paper at NeurIPS 2024 (reviewer 8qXf ). The authors addressed most of my questions then. I am surprised that this paper did not get in then, as it had only one opposing reviewer (scores were 7-7-5-3). **", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We’re thrilled that you enjoyed our paper, and we appreciate your belief in the merits of this work. The sections you found confusing are things we agree we could clarify, so we’re extremely grateful for your guidance.\n\nIn a single-hidden-layer network, each hidden neuron provides a basis function to the output (in that case the basis functions are ReLUs at different offsets and orientations). The networks in this paper are narrow and deep, and the basis we would like to use to build the output is the triangle waves produced at each layer (one peak, two peaks, 4 peaks, etc…). The sum neuron, acting similarly to a residual connection, is what allows these hidden features to pass through the remaining layers to be visible to the network output. Without the sum neurons, the network can only output a triangle wave with 2^d peaks. With the sum neurons, the network can perform the approximation of x^2 discussed in the introduction, as well as approximating a family of differentiable convex functions around it (which is the essence of theorem 3.1, it shows the correct coefficients for the sum neuron to use that will close the ‘holes’ in the derivative).\n\nAppendix A.1 gives the equations for the neurons in matrix form. It got separated from section 3 due to the length requirements. But we agree that a description of the individual neurons in equation form is probably more clear, so we will try to rework section 3 to do so. Perhaps the following is a more clear explanation of the network structure:\n\nBuilding a triangle:\n$t1(x) = ReLU(x)$ $t2(x) = ReLU(x-a)$ $output = \\frac{t1}{a} - \\frac{t2}{a-a^2}$\nThe weight $\\frac{1}{a}$ is chosen so that the output is 1 at $x=a$. the weight on $t2$ is equal to $\\frac{1}{a} + \\frac{1}{1-a}$ so that it negates $t1$ and then makes the output zero at $x=1$. \nThis would give the diamond-shaped network shown in the top left of Figure 2. If we wanted to compose this network to make more oscillations, then the output node would become the input node for the next diamond-shaped network, which gives the awkward 1x2x1x2x1x2… pattern, which shows up in some of the background literature. Instead of collecting the $t1$ and $t2$ neurons into the output unit, they can be assembled directly in the input of the next layer using:\n$t1_{i+1} = ReLU (\\frac{t1_i}{a_i} - \\frac{t2_i}{a_i-a_i^2})$ $t2_{i+1} = ReLU (\\frac{t1_i}{a_i} - \\frac{t2_i}{a_i-a_i^2} - a_{i+1})$. (Maybe this is an unimportant distinction that can be skipped, and we could just give the equations in a constant-width format, or maybe it’s important to go over - we are open to feedback.)\n\nThe sum neuron can be computed as:\n$sum_{i+1} = ReLU(sum_i - s_i*(\\frac{t1_i}{a_i} + \\frac{t2_i}{a_i-a_i^2}))$.\nThe ReLU is irrelevant here since the output is always positive. We need to do one more trick to avoid having $s_i$ directly stored as a weight since it will be exponentially small (which could be problematic for storing or optimizing it). We use the network to iteratively apply the ratio $S_i = s_i/s_{i-1}$ in each layer, decaying the amplitude of the outputs of the t1 and t2 neurons. This also means that the bias has to be a neuron, so that it too can gradually scale down.\n$sum_{i+1} = ReLU(sum_i - S_i*(\\frac{t1_i}{a_i} + \\frac{t2_i}{a_i-a_i^2}))$ $t1_{i+1} = ReLU(S_i*(\\frac{t1_i}{a_i} - \\frac{t2_i}{a_i-a_i^2}))$ $t2_{i+1}) = ReLU(S_i*(\\frac{t1_i}{a_i} - \\frac{t2_i}{a_i-a_i^2} - a_{i+1}b_i))$ $b_{i+1} = ReLU(S_i*b_i)$\n\nIn Figure 3 the sum will always be equal to 1 at $x=1$ since the network is set up to subtract the triangle waves from each layer from y=x, and the waves all output 0 at $x=1$.\n\nLabeling the tables is quite difficult since the experiments are complicated to describe, and there is only room for 2 or 3 words. You are correct about “Pretraining skipped” - which will encode the triangles into the network weights at initialization, but then only do ordinary gradient descent. The other two labels “differentiability enforced” and “differentiability not enforced” are about the scaling factors, rather than the sum neuron being present/absent. Theorem 3.1 is about how to pick the scaling factors ‘correctly’ to sum the waves in the sum neuron to get a differentiable output. Weighting the waves differently in the sum can give you fractals or other badly behaved functions in the output. The 1-dimensional experiments show that ‘holding gradient descent’s hand’ is actually helpful, and that choosing the scaling coefficients to make the output differentiable can act as an explicit regularizer.\n\nThe reason only the minimum values are reported in table 3 is that all 4 of the functions are included, so we needed to save space. The minimum is more important to look at than the mean because we’re comparing against a standard random network, which will collapse from the dying relu issue half of the time (and thus have a disproportionately bad mean).", "claims_and_evidence": "The construction used by the authors for parameterizing models of high expressiveness is correct, and in fact known and explored by many authors before (Montufar et al., 2014; Telgarsky, 2015; Serra et al., 2018; Huchette et al., 2023) - all of which acknowledged in their work. I would argue that what they are doing is the next logical step: operationalizing trained neural networks with high expressiveness. The insight of doing that by parameterizing a subspace of models is their biggest contribution here. As they observe, this is an alternative to the use of splines, such as in KANs, to which I would add that preserving the model piecewise linear has algorithmic and computational advantages.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Regarding Theorem 3.1 and surrounding discussion, I would appreciate if the authors precisely described the value of the network parameters in terms of the scaling factor $s_i$. If the zigzagging function being defined in each layer goes back and forth between 0 and 1, so that composing the function across layers produces an exponential number of pieces, then how can it work properly with scaling?", "experimental_designs_or_analyses": "I believe that the experiments are adequate. Unlike in the prior submission of this work, the authors have also explored nonconvex and bivariate functions. To be clear, in the context of mathematical optimization, piecewise linear approximations of nonlinear functions rarely go very far in terms of dimension. It may sound strange, but regression can be more challenging than classification. \n\nI appreciate the effort of the authors in also including preliminary results about classification in the appendix, but I believe that this is not central to their work. There is plenty of work done in improving classification, for which reason even a meaningful contribution may have only a marginal impact when implemented. I believe that it is important the other reviewers understand this nuance.", "relation_to_broader_scientific_literature": "See \"Claims and Evidence\" above.", "essential_references_not_discussed": "The authors do a good job with references (see \"Claims and Evidence\" above).", "other_strengths_and_weaknesses": "See other items of this review.", "other_comments_or_suggestions": "Related to my comment about Theorem 3.1, I would appreciate if the authors were to write down the equations for each neuron. Figure 2 does a reasonable job, but treating the bias as a unit is confusing. Likewise, the discussion about the need for the sum unit is not entirely clear to me. I would have appreciated an example of before and after to explain the significance of having that unit.\n\nIn Figure 3, it would be helpful if the value of $a_i$ in each layer $i$ was given.", "questions_for_authors": "Please comment on my question about Theorem 3.1 above, and on explicitly writing the equation of each neuron.\n\nIf Figure 3, is the sum always 1 at x=1?\n\nIn Page 4, what do you mean by \"would form a 1 -> 2 -> 1 -> 2 -> 1... shape\"?\n\nThe terms \"pretraining skipped\", \"differentiability not enforced\", and \"differentiability enforced\" are not very clear. If I get it right, are these equivalent to \"new initialization, no pretraining\", \"do pretraining by adjusting peaks and valleys without the sum unit\", and \"do pretraining by adjusting peaks and valleys with sum unit\", all of which followed by regular training?\n\nWhy are you only reporting min values in Table 3, as opposed to min and mean as in Tables 1 and 2? That seems less informative.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zD7BdA9xhr", "reviewer": "Reviewer_a684", "summary": "This paper proposes an new parameterization and pretraining method for ReLU networks to ensure that the resulting function is a piecewise-linear mapping with the maximal number of \"linear regions\" (i.e., $2^{d}$ for a ReLU network of depth $d$). The motivation for such a parameterization appears to be the following: while the number of \"linear regions\" has been used in the literature as a proxy for expressive power, standard weight parameterizations (and associated randomized initialization schemes) for ReLU networks produce mappings with an average number of linear regions that is invariant to the depth $d$. The paper presents numerical experiments for learning 1-D and 2-D functions as well as training neural networks for image classification.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s comments and perspective on our paper. In light of your observations, there are a few important aspects of this paper we would like to emphasize that were maybe not immediately clear. \n\nThe first is regarding our claims about navigation of the loss landscape. When we say we’re improving navigation of the loss landscape, we’re not saying our paper is about proving convergence rates. Instead, what we mean is that we’ve simplified learning for the network so that it can discover better minima that it would not otherwise. In other words, we’ve disentangled the tasks of learning ‘how do I build functions efficiently?’ from ‘what does this data say?’ - the former question being one that ReLU + random initialization + gradient descent pathologically cannot answer.\n\nWe agree that while having many linear pieces is necessary to approximate a nonlinear function, it isn’t always sufficient; those extra pieces could be useless or even detrimental if not regularized. We address this with Theorem 3.1 (Unfortunately due to length constraints, most of the math got separated from the main body). Theorem 3.1 is a mathematically principled and explicit method of regularization. It adapts the construction of x^2 presented in the introduction to work with asymmetric triangular waveforms, ensuring that the network output is differentiable by closing all the ‘gaps’ in the derivative (in the infinite depth limit). Without following Theorem 3.1, it’s possible to produce several different kinds of fractal structures that will likely not have good generalization properties. \n\nYou mention that there are no universality results, and that is correct. The function family given by Theorem 3.1 is highly non-universal. x^2 is the only well-known member, and the other functions share a certain kind of dilated self-symmetry with x^2. However, even though it isn’t a universal parameterization, the triangle parameterization can get close enough to other one-dimensional convex curves that ordinary gradient descent can nudge the network to produce an otherwise unlearnably low loss (by a factor of up to 1000). This suggests that it’s potentially valuable to search for a better and more expressive parameterization to extend that result to more challenging settings; yet we believe these numerical results already merit sharing the present parameterization and strategy with the research community.\n\nYou’ve also pointed out that the method when adapted to higher dimensions struggles outside of a block diagonal format. This result is actually to be expected, as all the mathematical development we have done is aimed at building 1-d convex functions using 4-neuron-wide networks. When the weight matrices are freed from the block diagonal constraint, the overwhelming majority of their weights need to be filled in with no additional mathematical insights, so it shouldn’t work well.\n\nThe authors were pleasantly surprised that the experiments on real data work with any meaningful advantage, given the large mathematical gaps that remain unanswered. That is why the more practical results appear in the appendix (even though they are perhaps more interesting to the average ICML attendee). We see the value of this paper not as being a production ready method, or as being a complete mathematical theory of how to get exponentially better weight setting, but as containing important ideas that can help other researchers along in this direction. Replacing the bedrock algorithms of deep learning is probably a larger task than what one paper can accomplish, and this paper is at a natural stopping point where its substance requires a lot of space to convey, and the remaining challenges ahead are each nontrivial. \n\nWe think the geometric algebra paper you’ve linked seems very interesting, and we’ll incorporate a citation to it. Also, we’ll work to clarify when the parameterization switch happens in the experiments.", "claims_and_evidence": "As far as I understand, the main claim is that \"forcing\" the number of linear regions to be exponential during the first stage of training can lead to significant improvements in approximation quality. Currently, the evidence is (in my opinion) quite limited:\n\n- There are no \"universal approximation\" results for the proposed parameterization.\n- The authors claim that their \"pretraining algorithm acts as a preconditioner for, or guide to, the loss landscape\". However there is no discussion of things like convergence rates, conditioning of the loss in the proposed parameterization etc.\n- The numerical results on the largest-dimensional setting are limited to a small number of epochs and the description of the experiment is lacking (for example, the authors describe that they reduced the number of parameters \"slightly\" without specifying how). Other experiments yield worrying results: in Appendix A.10, the authors describe a dense and a block-diagonal version of a neural network model, and the new parameterization does not yield improvements in the dense case.", "methods_and_evaluation_criteria": "Please refer to my comments under \"Claims and Evidence\".", "theoretical_claims": "I did not have time to verify the validity of Theorem 3.1.", "experimental_designs_or_analyses": "Please refer to my comments under \"Claims and Evidence\".", "relation_to_broader_scientific_literature": "The paper implicitly assumes that the number of linear regions is a good proxy for the approximation quality of the neural network. However, the literature includes work suggesting that overly expressive mappings are not necessarily good (without necessarily implying that deeper = worse). See, for example the following works: [1](https://arxiv.org/abs/2305.15598), [2](https://arxiv.org/abs/2209.15055), and references therein; see also [3](https://arxiv.org/abs/2011.04268) for a perspective on why regularization is important for solving inverse problems with deep neural networks.", "essential_references_not_discussed": "I would not consider the following a \"classic\" reference, but appears highly related to the structure of optimal weights for deep ReLU networks: https://stanford.edu/~pilanci/papers/geometric_algebra.pdf", "other_strengths_and_weaknesses": "- The results on CIFAR-10 and Imagenet are promising (albeit for a very limited number of epochs; the exact experiment setup is also unclear). Consider moving them to the main text rather than hiding them in the appendix.\n- In my opinion, the most interesting plot in this paper is the \"learning rate stability\" plot (Figure 13). The paper's main claim would be much stronger if the authors were able to produce such a plot for high-dimensional problems. Unfortunately, even in this plot, it is unclear if the learning rate is the same during the first and second stages of training.\n- The presentation of the proposed parameterization needs to be improved. The extension to arbitrary dimensions, which is the most realistic setting, is not addressed at all in the main text.\n\n\nI am overall interested in this paper and whether the claimed advantages persist in other problem settings, beyond simple regression and classification problems (e.g., solving inverse problems). However, in my opinion the paper needs considerable revision before it's ready for publication.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0cS1FA1bVf", "reviewer": "Reviewer_ZVQa", "summary": "This work builds on the link between the expressiveness of a neural network with ReLU activation functions and its number of linear regions in the output space. The general idea is that the larger the number of linear regions in the output space, the higher the expressiveness of the network (i.e., the easier it would be for the network to implement complex functions).  Previous works show that the number of linear regions do not scale with depth for randomly initialized neural networks. The authors instead propose to initialize and (pre)train the model while constraining its weights such that the total network implements a chain of triangle functions, to make sure the number of linear regions scales exponentially with depth. They further illustrate through experiments that the proposed method achieves a higher accuracy than conventional models.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are glad to hear that the reviewer found the paper interesting and believes it shows promise.  We appreciate the reviewer’s willingness to reconsider their score in light of what we hope will clarify all the claims and goals of the paper. We agree that the extensiveness of the paper could cloud those, and we apologize for a lack of clarity - we hope we can provide a convincing preview here of how we plan to revise the paper to fix these writing issues.\n\nThe goal of this paper is to present a method that forces ReLU networks to maintain exponentially many linear regions at initialization and during training, thus answering a five-year-old open question in the literature (Hanin and Rolnick, ICML 2019). We note that the goal is not to exponentially improve training speed, or similar goals - the general relationship between number of linear regions and training speed is unknown in the literature, and our paper does not attempt to address or solve this (though intuitively, more linear regions should usually help, and numerical results bear this out). The central claim of our paper (which is constructively proved) is that our triangle parameterization indeed achieves exponentially many linear regions, at least for a simple 1-d neural network case where we can rigorously analyze the effect of the triangle parameterization. We make some further, smaller claims about the importance (or not) of enforcing differentiability, and on extending the method to higher dimensions. Again, we hope this compactly summarizes what the paper is (and isn’t), and we will make this prominent (either text or bullet points) in the revised introduction of our paper. We will similarly revise the experiment descriptions and text to ensure their clarity for the camera-ready manuscript.\n\nIn figures 5 and 7 the difference in the number of linear regions can be seen visually. In general, counting them exactly is combinatorially difficult (for example, appendix A.8 discusses Zaslavsky’s theorem - even for a shallow network, the number of regions grows to the power of the input dimension due to a relationship with Pascal’s triangle) and would likely be infeasible for many of the larger experiments.\n\nAs mentioned in the response to reviewer 2 (a684), the triangle parameterization is not universal. The 1000-fold improvements are possible because the first phase of training can get the network into a neighborhood of parameter space where a solution that still uses all 2^n regions lives. But we would expect that with greater depths and demands for precision, that neighborhood size would shrink and this might not work for any curves that are not explicitly proven to be represented by weighted sums of composed triangle functions. Interestingly, this mirrors the developments of deep learning in general, where vanishing/exploding gradients and other such issues limited the depth of trainable models. Hopefully this work can serve as a starting point for constructing more expressive parameterizations.\n\nWhen we refer to networks as standard/ordinary/default/etc., we simply mean that there is nothing special about the network - it is a fully connected network of the same dimensions as our experimental models. This is still a fair comparison with our method even though some of the ‘jobs’ we give neurons might resemble residual connections or other empirical techniques because the standard networks have every opportunity to learn a residual neuron of their own, yet they do not. Our method comes entirely from theoretical constructions, so the fact that it bears similarity to empirical techniques ought to reinforce that both our method and the empirical techniques it is similar to are on the right track, rather than counting against us. \n\nIn our experiments we do attempt to separate the effect of lots of regions from the mathematical regularization from Theorem 3.1 by training scaling parameters independently. We find that for 3 out of 4 convex functions it’s slightly worse when left unregularized, but still orders of magnitude better than random initialization.", "claims_and_evidence": "The actual claims made are dispersed throughout the paper and are somewhat vague. While I believe the claims might be true to a large extent, I think they are not sufficiently proven.  \n\nReferring to following lines in the paper: \n\n*62, L: While an exponential increase in the expressiveness of a\nReLU network does not necessarily imply an exponential\nincrease in performance, one may intuitively expect a substantial\nbenefit, and our results bear this out*\n\n*234, R: (1) we would like to determine how to learn the most effective\nfunction representations possible, and (2) to explore\nhow the utilization of an increased number of linear regions\ncan affect a network’s ability to capture underlying\nnonlinearity in its training data. To demonstrate that our\nnetworks can learn function representations that better utilize\ndepth,*\n\n*355, R; in particular,\ncompelling ReLU networks to approximate functions with\nexponential accuracy as network depth is linearly increased.*\n\n\nAnd assuming the following statements are correct: \n\n-\trandomly initialized networks have a number of linear regions that is not influenced by depth (the authors take this from literature),\n-\tfor the proposed method, the number of linear regions exponentially increases with depth (this is true by design of the proposed method),\n\nI recognize the following claims, according to my understanding of the paper / the above mentioned lines:\na)\tthe proposed method results in more linear regions w.r.t conventional models of the same depth,\nb)\tand, as a main claim: for the same depth, the proposed method results in higher accuracy w.r.t conventional models because of the increase in the number of linear regions (assuming this is the case, see claim a).\n\nI think these claims are not sufficiently proven because: \n\nClaim (a) -> In the experiments, there is no count of the number of linear regions for the conventional models. This potentially depends on the depth used in the experiments; it is thus unclear whether the proposed method really has more linear regions at all depths. \n\nClaim (b) -> the authors make design choices that have effects similar to residual connections (line 218, R) and regularization (line 234, L). It is therefore unclear what the performance gains can be attributed to; i.e., if this is really because the number of linear regions is higher.  Some part of the performance gain could be due to the (implicit) use of residual connections/regularization when these are not present in the standard networks the authors compare against. Since there are no details on the architectures of these ‘standard’ networks, I cannot further verify this claim.", "methods_and_evaluation_criteria": "To prove that the proposed method leads to better accuracy, the used methods and evaluation seem sufficient for an exploratory paper. However, the methods do not sufficiently support the specific claims about why the method works better (as discussed above). Moreover, important details about the architecture of the standard models are missing.", "theoretical_claims": "There are some theoretical derivations in the appendix, which I did not check in detail. They do not support the main claims as I understood them (see above).", "experimental_designs_or_analyses": "See claims", "relation_to_broader_scientific_literature": "The paper is well situated in the broader literature of expressiveness of ReLU networks, including other works that constrain and/or reparameterize the network to increase the expressiveness ( ElbrÅNachter et al. (2019), Chen & Ge (2024)). The origin and usefulness of triangle functions is also expenstively discussed. There is little to no literature referred that studies the relationship between the expressiveness of a network (in the sense of its potential to express certain functions) and the actual functions it can/does express after training with gradient descent (cfr. works on inductive bias) and/or the achieved accuracy.", "essential_references_not_discussed": "Not to my knowledge.", "other_strengths_and_weaknesses": "Strengths:\nI think the proposed method is very interesting, and shows great promise from the preliminary experiments. The work done for the paper + supplemental seems substantial and could lead to an interesting contribution to the field. \n\nWeaknesses: \n-\tthe paper is confusing in its claims and goals. Is the goal to show that the proposed method ‘just works better’? That would need more extensive experiments with more details on the models the work compares against, plus an extension to real-world settings. Is the goal to prove that the method introduces more linear regions for larger depths, and this in turn leads to higher accuracy? Then the experiments should be changed to unequivocally prove this. While I think the work is very interesting, the “basis” of the paper is lacking. \n\n-\tWhile great care is taken at some points to explain the setup, the text is also often confusing and unclear. To give a specific example, starting at line 216, it is unclear what the actual (mathematical) goal is here. I’m guessing the authors wish to implement the triangle functions through making use of a neural network consisting of two nodes with ReLU activations, constraining the weights and biases such that the [0,1] input is mapped according to a triangle function with a peak at a. However, this is described in a very convoluted and unclear way in the text. It would be helpful to have clear mathematical descriptions, and more concise statements to prepare/guide the reader.", "other_comments_or_suggestions": "This work is very interesting to me. But although it's also extensive, the \"basis\" of the paper in terms of claims and corresponding experiments is lacking. I would suggest revising this part. With an improved quality of the text and figures, I could be resubmitted.", "questions_for_authors": "/", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lD83WGPD89", "reviewer": "Reviewer_wXeQ", "summary": "This paper addresses the previously identified problem of bounded linear pieces in neural networks regardless of depth. The authors show that for a width 4 network, with a novel initialization and pertaining algorithm, they can maintain an exponential number of linear pieces with regard to the depth. They show that with this initialization and pretraining, followed by standard training, a toy net can achieve superior performances on a toy problem. They then discuss the extension to general networks, by dividing the general network into many toy networks and apply their method on each of them.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their questions, and we appreciate that they took the time to read the appendix. The reason why the paper currently looks like it does, as Reviewer 1 (jsad) alludes to, is that the paper has been through several rounds of rebuttals, and so layers of preliminary experiments have built up over time and now the appendix is extensive. Originally, the authors’ main intention for the paper was to present the idea that better training algorithms could be created by finding efficient mathematical constructions that still permitted room for trainability. There are still many fundamental mathematical issues to be addressed to ‘properly’ set weights in higher dimensional settings, and this paper felt like it was at a natural stopping point even with only toy 1-d experiments. However, the reviewer makes a good point that it is valuable to know how far away the naive extension of this method to higher dimensions is from practical usage, and it likely makes sense to restructure the body of the paper to include both the one-dimensional experiments and the experiments from Section A.11. We will address this in our revised version.\n\nWe will attempt to address the reviewer’s questions in order. In the one-dimensional experiments, the mean and minimum are not distances in function space, they’re the mean and minimum over 30 trials. The minimum is needed (and more important than the mean) because half the time the randomly initialized ReLU networks collapse from the dying ReLU issue. The minimum lets us see what happens when training ‘works’ for the various network types. We will clarify this in the manuscript.\n\nWe agree that accuracy is probably a more interpretable and meaningful metric to display and can switch figure 16 accordingly.\n\nWe do include a diagram of what using one of the small networks as an activation would look like at the beginning of the appendix. It could be beneficial, though, to describe the implementation further, especially if larger scale experiments are going to be moved to the main body. Essentially, each neuron in a dense layer gets its own copy of the 1-d experimental networks to learn some piecewise linear convex activation function for it to use. This adds layers to the network with a 4x4 block diagonal structure where each subnetwork’s version of that layer corresponds to one of the diagonal blocks. This can be implemented practically by turning the matrices into 4x4xW tensors (to remove all the 0 elements) and using pytorch’s einsum() function.\n\nThe reason the method in the main body cannot apply directly to higher dimensional cases is that it only works for 1-d convex functions. Fortunately, activation functions are one-dimensional, and so that provides the most naive and easy route to scale up the construction. As we alluded to earlier, much more math is needed to figure out more elegant solutions. \n\nIn light of your 4th question, it makes more sense to use a larger and better studied architecture such as VGG for the CIFAR-10 experiments, as it would make the results more compelling and less arbitrary. We can make that switch for the camera-ready version of the paper", "claims_and_evidence": "The claims made in the main text are clear, good, and interesting. In particular, these main claims are significant to solving the problem identified by previous works.\n\nHowever, I found the claim made in Appendix A.11, which is arguably the most interesting one to the general audience, is a bit confusing.", "methods_and_evaluation_criteria": "The method has solid mathematical background and make sense. Evaluation is sufficient to demonstrate their claims made in the main text.", "theoretical_claims": "Due to the large body of theoretical results and their complexity, I am unable to check their formal proof. However, the authors provided numerical demonstrations which agrees well with their theoretical results. Thus, I am inclined to believe their results.", "experimental_designs_or_analyses": "The experiments involving the toy dataset is good. However, I have a question regarding Table 1 and 2: why do the authors report minimum errors? I would say reporting the mean error ($L_2$ error) and max error ($L_\\infty$ error) is more proper. After all, achieving a good minimum error sounds meaningless to the full picture.\n\nI find the experiments regarding CIFAR and Imagenet, discussed in Appendix A.11, quite confusing due to the lack of sufficient details. First, the authors report the loss, but do not mention the loss type. I can hardly believe that with a standard cross entropy, such a small network could achieve loss less than 0.01 within 2 epochs. I suggest the authors replace Figure 16 with accuracies rather than loss values. Second, the authors do not describe the network they used in this experiment and how they apply their method as the activation in detail. Third, contrary to the experiments in the main body, this section only applies their method as part of the activation function. Why can't we follow the same design made in the main text? Does this still count as the same method? Fourth, they evaluate a single small network architecture in these experiments. Do they have a specific reason about not using a larger network on CIFAR-10? Could the benefits of their method vanish when we further increase the network size? An ablation on architecture helps.\n\nI apologize for raising many questions about this appendix section. However, since this section presents the most relevant information about the practice, I do find it confusing and preliminary. In addition, this study deserves a place in the main text. While it is OK to not perform well on large datasets for this theoretical work, it is important to make it clear where and how large the gap is. Otherwise, follow-up works will be quite hard, which is also contrary to the authors' interest.", "relation_to_broader_scientific_literature": "This work mainly solves the problem raised by [1].\n\n[1] Hanin, B. and Rolnick, D. Deep ReLU networks have surprisingly few activation patterns.", "essential_references_not_discussed": "I found the reference adequate.", "other_strengths_and_weaknesses": "This work stands out in theoretical rigor and its sound evaluation on toy datasets. These evaluations support their construction quite well. However, as detailed above, when it comes to more relevant datasets, evaluations are flawed.", "other_comments_or_suggestions": "None.", "questions_for_authors": "See Section ''Experimental Designs Or Analyses''.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This article provides a clever construction that allows one to force deep ReLU networks to compute functions with many more linear regions than is typically possible by a vanilla feed-forward network. While the practical utility of this is not clear, it is an interesting advance in the theory of ReLU networks and provides a thoughtful and fresh counterpoint to prior work in the subject.
Decision: Accept (poster)