Compelling ReLU Networks to Exhibit Exponentially Many Linear Regions at Initialization and During Training

Authors: Max Milkert, David Hyde, Forrest John Laine
Primary area: other topics in machine learning (i.e., none of the above)
Keywords: linear regions, activation regions, ReLU network, pretraining, network initialization

Abstract:
A neural network with ReLU activations may be viewed as a composition of piecewise linear functions. For such networks, the number of distinct linear regions expressed over the input domain has the potential to scale exponentially with depth, but it is not expected to do so when the initial parameters are chosen randomly. Therefore, randomly initialized models are often unnecessarily large, even when approximating simple functions. To address this issue, we introduce a novel training strategy: we first reparameterize the network weights in a manner that forces the network to exhibit a number of linear regions exponential in depth. Training first on our derived parameters provides an initial solution that can later be refined by directly updating the underlying model weights. 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 how to extend our approach to multidimensional and non-convex functions, with similar benefits observed.

Decision: reject
Reviewer scores: 3, 8, 8, 5

Reviews and discussion:
<thread>
creation date:
1730054674477

thread_type:
official_review

<thread_object>
creator: reviewer_rfnb

<content>
summary:
This paper presents a novel strategy to improve the efficiency of ReLU neural networks. It focuses on overcoming the limitations of randomly initialized networks, which tend to be unnecessarily large and inefficient in approximating simple functions. The authors introduce a reparameterization of network weights that ensures an exponential number of activation patterns, thus maximizing the linear regions in the input space. Their approach includes a pretraining stage using derived parameters that enhances the expressivity of the network before standard gradient descent is applied. This method shows significant improvement in approximating both convex and non-convex functions, with better accuracy and efficiency compared to traditional networks. The paper's findings demonstrate that networks initialized with exponential linear regions can capture nonlinearity more effectively, leading to more accurate function approximations. It concludes with potential extensions to multidimensional and non-convex functions, positioning this strategy as a promising tool for more efficient deep learning models.

strengths:
* The paper introduces a novel approach to reparameterize ReLU network weights, which forces the network to exhibit an exponential number of activation regions. This significantly enhances the expressivity of the network and addresses the inefficiencies of randomly initialized models, providing a more accurate and efficient approximation of nonlinear functions.

* The proposed pretraining strategy allows the network to initialize with exponentially more linear regions, thus reducing the reliance on gradient descent to discover new activation patterns. This results in faster convergence and much more accurate function approximations, as demonstrated through numerical experiments, showing orders of magnitude lower errors compared to standard initialization methods.

weaknesses:
* While the paper demonstrates improvements in one-dimensional convex functions, the results for higher-dimensional functions and complex non-convex problems are not as thoroughly explored. The proposed method may face scalability challenges when extending to high-dimensional inputs, where the complexity of real-world tasks lies.

* The introduction of a pretraining step with specific reparameterization adds complexity to the network training pipeline. This may make the approach more difficult to implement or integrate into standard deep learning workflows, especially for practitioners looking for more straightforward techniques.

* The effectiveness of the method heavily relies on carefully derived theoretical constructs, such as triangle functions and their parameterization. While this works well in controlled scenarios, its practical robustness in more diverse and noisy real-world datasets is not fully tested or demonstrated.

questions:
* How does the proposed reparameterization strategy perform in complex, high-dimensional tasks, and what are the challenges in scaling this method effectively to more realistic datasets?

* Have you considered testing this method on real-world datasets with more variability and noise? How robust is the technique in such scenarios, and are there any performance trade-offs when dealing with non-synthetic data?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730394756500

thread_type:
official_review

<thread_object>
creator: reviewer_hkz8

<content>
summary:
This paper proposes to reparameterize ReLU networks by parameterizing the peaks of the triangle wave basis functions generated by ReLU activations. This ensures that the number of linear regions grows exponentially with the depth of the network, which reduces the waste of representation capacities in randomly initialized ReLU networks. A learning algorithm is proposed to train the reparameterized ReLU network by first updating the derived parameters and then updating the actual weights underlying the model. The proposed method is empirically evaluated on 1D convex and 2D nonconvex target functions, which demonstrate its improved accuracy compared to randomly initialized networks.

strengths:
1. The proposed reparameterization of ReLU networks is novel and interesting. Based on the observation that ReLU networks can generate symmetric triangle waves, the proposed approach introduces an approach to directly reprent the ReLU neurons (rather than weights) as asymmetric triangle wave basis function with learnable locations of the peaks within [0, 1].
2. The proposed learning algorithm is simple and seems to be effective in training the reparameterized network for simple target functions as shown in the experiments.
3. The 1D demonstrations and experiments are nice, which illustrate how the proposed method learns useful patterns for fitting the target function.

weaknesses:
1. Theorem 3 seems to be an “only if” statement, and therefore setting $s_{i+1}$ according to Eq 4 is a necessary but not sufficient condition to guarantee differentiability of the reparameterized network.

2. It is unclear how useful the proposed method is in practice, since it is mostly evaluated on simple 1D convex target functions. As this is not a theory paper, the proposed method should at least be evaluated on some semi-real datasets, (e.g., some of the common UCI datasets).

3. Writing needs to be improved. The logic flow is a bit confusing. Also, several important concepts and building blocks are not well explained in the paper. For example, important definitions like definitions of linear regions, activation patterns, and activation regions should be stated in the paper or appendix.

4. The following closely related works which analyze compositions and/or reparameterization of ReLU activations are not discussed in the paper.

[1] K Eckle, J Schmidt-Hieber. A comparison of deep networks with relu activation function and linear spline-type methods. Neural Networks 2019.

[2] DM Elbrächter, J Berner, P Grohs. How degenerate is the parametrization of neural networks with the ReLU activation function? NeurIPS 2019.

[3] W Chen, H Ge. Neural characteristic activation analysis and geometric parameterization for ReLU networks. NeurIPS 2024.

[4] B Hanin, D Rolnick. Complexity of linear regions in deep networks. ICML 2019.

[5] M Raghu, B Poole, J Kleinberg, S Ganguli, J Sohl-Dickstein. On the expressive power of deep neural networks. ICML 2017.

[6] D Rolnick, K Kording. Reverse-engineering deep ReLU networks. ICML 2020.

questions:
1. How are ReLU activations guaranteed to generate symmetric triangle waves? There are many possible compositions of ReLU activations, but only a subset of them are symmetric triangle waves. If the network is reparameterized using only the triangle wave basis functions as proposed in the paper, will it lose some flexibility and expressivity as it is not possible for the reparameterized network to create other shapes or patterns within each layer? 

2. Could you provide some intuitions and/or theory regarding why pretraining helps maintain the triangle generating structure and avoid eliminating activation regions as the network gets deeper?

3. Does the proposed method improve convergence rate? Could you demonstrate it with some experiments and/or theory?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730397355239

thread_type:
official_review

<thread_object>
creator: reviewer_oevs

<content>
summary:
This paper focuses on the expressivity of ReLU networks and argues that the standard neural network training approaches lead to models that cannot utilize all of the linear regions that a ReLU network has the potential to exhibit. The paper contains an approach to overcome this issue.

strengths:
Please see the Questions section.

weaknesses:
Please see the Questions section.

questions:
My review is as follows:

- I think this paper brings up important issues with standard neural network training practices (such as using relu for activation or gradient descent, etc).

- One thing that I think is potentially missing is the verification of the findings on a somewhat more realistic scenario. Could we expect the proposed method to outperform a standard neural network approach (e.g. a similar size relu network trained by SGD) when, say, predicting airline delays? Or, other more standard methods such as linear regression or decision tree?

- To make the results potentially more broad, I wonder if the proposed strategy could be somehow applied to classification (perhaps can test it on a simple dataset such as "two spirals" dataset). If that's not straightforward, I think it'd still help me understand the contributions better if the authors can comment on the challenges.

- Which of the findings of this paper could we expect to carry over to other non-linear activation functions such as sigmoid?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731107731179

thread_type:
official_review

<thread_object>
creator: reviewer_egry

<content>
summary:
This paper designs a novel training strategy: (1) reparameterise the network weights in to make it exhibit a number of linear regions exponential in depth; (2) train on the derived parameters for an initial solution; (3) refine the parameter by directly updating the underlying model weights. Experiments are given to support the method.

strengths:
-	The paper presents detailed introduction and explanation of the proposed method, including how to construct the initialisation and how to calculate the gradient. The paper is compressive, well-structed, and easy to follow. 
-	The paper present experiments for cases of one dimension and high-dimension non-convex problems.
-	I find the paper makes conceptual contributions of proposing a new initialisation strategy.

weaknesses:
-	The experiments are not sufficient. The current experiments only cover quite shallow (three layers) ReLU neural networks on very simple tasks. It is unclear whether the results apply to complex scenarios, like deeper neural networks, transformer on fitting images, mining on text data, etc. Thus, the paper actually cannot help understand the success of deep learning.
- No comparison is given with other initialisation methods.
- The explanation of why this method works is not sufficient. This makes the method not convincing.
-	No theoretical results are provided. This is particularly severe given the experiments are insufficient.

The paper looks like in an early stage with insufficient validation. I suggest the authors to do more following on this paper.

questions:
Please address the Weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732595250989

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We thank the reviewers and ICLR staff again for their support of our work.  By taking a more mathematically principled approach, we’re able to train a small yet exponentially more efficient ReLU network, without needing to rely on batch norm, layer norm, dropout, or any other heuristics. Even though there is much more mathematical work needed to extend the results in our paper to networks of arbitrary depth and width, the ideas this paper contains are important to share with the community. We believe there is tremendous value in any learning publication - whether by us or any other group - that makes any progress towards exponentially more efficient neural networks.
Furthermore, we believe the reviewers’ constructive suggestions have substantially improved our work.  We now demonstrate higher-dimensional examples on real-world datasets, illustrating that our method already can be applied to practical learning tasks.  We recognize our revised manuscript as a substantial improvement over our initial submission are and grateful for this guidance.
Lastly, while we will not publicly remark on ongoing private conversations regarding ICLR policies and the reviews submitted by Reviewer EGry and Reviewer rFNb, we feel relatively confident the other two reviewers (or anyone in the public) can look at those reviews and hypothesize what our concerns are.  We humbly ask that you keep this in mind during the discussion period among reviewers and in your own evaluations of our work.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733124871651

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Additional Experiments and Improvements

comment:
We are pleased to share with the reviewers and AC additional experiments using our methodology.  Though PDF updates are no longer allowed, we have added these results to our manuscript as Appendix A.10, and have appropriately referenced the appendix from the main body.  (We have also added a few sentences (with citations) to our Introduction, as suggested by reviewer EGry, that emphasize that preserving more linear regions yields improved network expressivity - this was a straightforward improvement.)

Our additional experiments cover the two image classification problems suggested by reviewer EGry: CIFAR-10 and ImageNet.  We would like to highlight the drastic increase in scope and dimensionality of these examples (1000 image classes, convolutions, etc.) compared to our initial 1- and 2-D analytic function examples, and even the UCI and two-spiral examples we added per the suggestions of reviewers oevS and hKZ8.  Should evaluations on any further specific datasets be required, we are happy to have those suggested by reviewers as conditions of acceptance.

Here are the two figures of our new results, and the corresponding text we added to the manuscript:

Figure 16: https://postimg.cc/tn64y7WG

Figure 17: https://postimg.cc/1g4Psf17

We include very preliminary demonstrations of how our method can increase performance on large-scale image classification tasks. 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. Nonetheless, combining our construction with convolutions or other layers is a use case far exceeding the 1D test problems in the main body where we observe orders of magnitude of improvement, and the output of each subnetwork might not learn to be as nicely behaved as in the tightly controlled experimental setting of 1D convex training data. Thus, we stress that while our initial results are positive, and we can reasonably conjecture why, future work on extending our method to arbitrary ReLU networks would provide greater rigor and likely far greater performance gains, as seen with our lower-dimensional function approximation examples that realize the full benefit of our mathematically principled approach.

We evaluate two standard benchmarks: CIFAR-10 and ImageNet. In the case of CIFAR-10, we train a small network of 3 convolutions followed by 2 fully connected layers. To apply our technique, we insert our custom networks in between the two fully connected layers to act as activations, and reduce the number of neurons slightly to correspond with the extra parameters added. In the case of ImageNet, we use PyTorch’s pretrained VGG16 model for its convolution weights (which are frozen during training). We modify the linear layers at the end of the network in the same manner as we do for the CIFAR-10 experiment, and compare against re-learning the fully connected weights with Kaiming initialization. We are thus able to evaluate the effect of our network (on the linear layers) versus Kaiming initialization, for both CIFAR-10 and ImageNet.

Figure 16 shows the results for CIFAR-10. Our (“experimental”) training and validations generally remain below their Kaiming-initialized (“ordinary”) counterparts, including for instance at epochs 3 and 4, which per the loss curves’ characteristics are where one would likely stop training. While the loss curves are similar in shape, we report that at epoch 4, for example, our training and validation losses are 25.6% and 5.1% lower than their standard network counterparts.

In our ImageNet test (Figure 17), we similarly see modest gains of our (“experimental”) network over a Kaiming-initialized (“ordinary”) network, yet due to using a smaller learning rate here (0.00001, vs. 0.001 as used with CIFAR-10), the loss curves are smoother, so we see our networks consistently outperforming the standard network after 0.25 epochs (we trained for two full epochs but plot over the intermediate partial epochs). We trained both networks for two epochs; at epoch two, our training and validation losses were 0.01761 and 0.01657, compared to 0.02518 and 0.02269 for the standard networks (a 30% and 27% reduction, respectively).

These two examples show that even for large-scale image classification tasks - far away from the analytic 1D function tests considered in the main body - our methodology still has the potential to yield noticeable benefits, highlighting the promise of extending the present work to more general network architectures as a future research direction.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes a new training method that pretrains a ReLU network to a parameter having exponentially many linear regions before switching to naive gradient descent updates, which is demonstrated to have good approximation capabilities compared to standard initialization methods such as Kaiming initialization or RAAI. 

This submission has gone through a lot of activity during the discussion period. Since the initial submission only contained 1-d/2-d experiments, all reviewers expressed concerns whether the proposed algorithm will be useful in practical high-dimensional datasets. The authors updated the paper with results on a 8-d UCI dataset and a 2-d two-spiral dataset (as well as other edits), and also presented some preliminary experiments on CIFAR-10 and ImageNet datasets (albeit trained only for a few epochs).

After the revision and the rebuttal, many reviewers updated their scores and the current average numerical score sits at the decision boundary. After a careful reading of the paper, reviews, and the discussion, my final evaluation is that the paper is unfortunately placed slightly below the bar for acceptance at ICLR.

The paper proposes a new training algorithm applicable to any linear layers, with the guarantee-by-design (at least during the pretraining stage) that the network parameters stay in the region with many “linear pieces” in the input space. I believe this can be a nice idea that has a good potential to develop into a new and efficient training procedure for ReLU networks in general. However, whenever one challenges the “de facto standard”, one needs to be equipped with strong theoretical guarantees on the performance and/or extensive experiments demonstrating the superiority of the proposed method. In my honest opinion, the submission at the moment fails to offer neither of them.

On the **theory** side, I think the presented theoretical results do not successfully demonstrate the advantage of the proposed algorithm. The theory is mostly on the characteristics (differentiability, concavity etc) of the function $F$ constructed by the infinite depth network. The network is guaranteed to have exponentially many linear regions in the input space up to the pretraining stage, but there is no theoretical guarantee after this stage: the training dynamics, convergence rates, generalization bounds, etc in the naive GD update stage are not considered. One can only intuitively expect that starting at a pretrained parameter with exponentially many number of linear piece should be helpful for a better approximation in the final stage. 

In light of this, I must say that at least some of the authors’ claims regarding their theoretical guarantees are overly strong. For example,
- **“the theoretical results that explain why our method works are all proven”**: does not seem convincing from a learning theorist’s perspective.
-  **“theoretical guarantees are for convex functions and non-convex functions that are differences of convex functions”**: what kind of guarantees? In order to claim such a thing, we expect some universal approximation-type theorems. However, in the paper, I only see “any $F(x)$ with $s_i$ chosen according to Eq 3.1 is concave”, not something like “any convex function $g: [0,1] \to \mathbb{R}$ with $g(0) = 0$ can be approximated by $F$.”

On the **experiments** side, as all reviewers pointed out, in order to make significant impact, the proposed method must be tested on higher-dimensional real datasets. Although the authors put extensive efforts to address reviewers' concerns on the practical usefulness, I still wonder if the new results are significant. 

In the new Appendix A.9, it seems to me that the “advantages” of the proposed algorithm over the ordinary training can only be seen when we restrict training to block diagonal parameters. The authors assert this is for fair comparison, but it's hard for me to see why we should restrict ourselves in a low-performing regime (block diagonal variants have higher test losses for both methods). Also, in order to really ensure fairness, I think the authors should have also considered memory/FLOP footprints and wall-clock time consumption.

The authors also reported preliminary experimental results on CIFAR-10 and ImageNet. Although the initial results look promising and I understand the lack of time, as an AC, I cannot make premature conclusions based on plots that only display 2 or 6 epochs of training. Also, some important training details are missing here—whether dense or block diagonal version is used, how many epochs correspond to the pretraining stage (as “switch-off” happens at 500 epochs in Fig 14), why can CIFAR-10 losses be such small after only 6 epochs, etc. Such missing details prevent me from accurately assessing the validity and significance of the preliminary results.

Overall, I think the paper has clear merits but the results are not ripe enough to be presented at ICLR. At this time, I recommend rejection.