Understanding Multi-phase Optimization Dynamics and Rich Nonlinear Behaviors of ReLU Networks

Summary

This paper conducts a comprehensive theoretical analysis of the training dynamics of two-layer ReLU neural networks on a linearly separable data. The authors isolate four discrete phases of the training procedure and describe specific nonlinear behaviors that occur during each phase. Moreover, they derive explicit formulae for the evolution of the network parameters and prove convergence results for the network's output. The paper's contributions include a complete theoretical characterization of the training process, a better understanding of the role of initialization and regularization, and insights into the generalization properties of ReLU networks. In brief, the research provides a valuable addition to the domain of deep learning theory and sheds light on the training process of ReLU.

Strengths

The originality of the paper lies in its complete theoretical characterization of the training process of the two-layer ReLU network. While previous work has focused on local analysis or approximate linear models, this paper provides a more comprehensive understanding of the optimization dynamics of ReLU networks. The authors identify four distinct stages of the training process and describe the specific nonlinear behavior that occurs at each stage. They also derive explicit formulations for the evolution of network parameters and demonstrate convergent results for network outputs. Besides, the authors provide rigorous mathematical proofs and derive explicit formulas that shed light on the complex dynamics of ReLU networks.

Weaknesses

First, a weakness of the paper is that it focuses on the specific setting of two-layer ReLU networks trained on linearly separable data. While this setting is useful for providing a full theoretical characterization of the training process, it may not generalize to more complex networks or datasets. Second, another weakness of the paper is that it does not provide empirical verification of its theoretical results. While the authors provide rigorous mathematical proofs and derive explicit formulas, it would be useful to validate these results on real-world datasets.

Questions

Can the authors provide empirical validation of their theoretical results? While the authors provide rigorous mathematical proofs and derive explicit formulas, it would be useful to validate these results on real-world datasets.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

Yes.

Summary

The training of ReLU neural networks involves complex nonlinear phenomena, challenging theoretical analysis due to the nonlinearity of models and non-convexity of loss. This study provides a comprehensive theoretical characterization of the training process of a two-layer ReLU network using Gradient Flow on linearly separable data. From random initialization to final convergence, the analysis identifies four different training phases indicating a trend from simplification to complication. Specific nonlinear behaviors, like initial condensation, saddle-to-plateau dynamics, plateau escape, activation pattern changes, and increasing learning complexity, are accurately captured.

Strengths

1. The paper presents a complete theoretical characterization of the training dynamics of 2-layer ReLU networks, which addresses the nonlinearity and non-convexity challenges. 2. The precise characterization of four distinct phases of the training dynamics.

Weaknesses

- A missing related work on network's training dynamics and phases [1] - Could authors run more hyperparameter settings (\kappa_1, \kappa_2, \delta, etc.) and see if simulated training times (T1 ~ T4) are aligned with estimated ones? [1] "Neural Networks as Kernel Learners: The Silent Alignment Effect" Atanasov et al. 2021

Questions

- Do these four phases persistently exist across different settings (\kappa_1, \kappa_2, \delta, etc.)? - For Phase III: “deactivation of positive neurons on $\mathbf{x}-$” — is this a sign of implicit bias of NN during gradient flow? - Phase IV: “reactivation of negative neurons on $\mathbf{x}+$” — is this a sign of NN's overfitting? - It is a bit surprising to me that network width ($m$) and learning rate ($\eta$) are not included in the form of T1~T4. Could authors intuitively explain why is it from the viewpoint of the proof strategy in this paper? - One previous work on NN convergence stated that "strong correlations" (of input patches) "imply faster convergence", which contradicts the conclusions in this work (i.e. smaller $\delta$ indicates slower convergence). Could authors compare their work? [2] "When is a Convolutional Filter Easy To Learn?" Du et al. 2017.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

- Assumption 3.1 is oversimplified. Basically, all training data collapse into two signals. How will the results change when we switch to a little bit more realistic setting by adding some stochastic noises on top of $\mathbf{x}+$ and $\mathbf{x}-$ to each data point?

Summary

This paper aims to provide a theoretical understanding of the dynamics involved in training neural networks beyond the linear regime. The authors focus on a specific scenario where a two-layer ReLU network is trained using Gradient Flow (GF) on linearly separable data. The analysis encompasses the entire optimization process, starting from random initialization and concluding with final convergence. Despite the simplicity of the model and data used in the study, the authors uncover multiple phases within the training process. By conducting a meticulous theoretical analysis, they precisely identify four distinct phases that exhibit various nonlinear behaviors. In Phase I, the initial stage of training, there is a phenomenon of condensation and simplification as active neurons rapidly gather in two different directions. Simultaneously, the GF successfully escapes from the saddle point around the initialization. Phase II involves a prolonged period where the GF becomes trapped in a plateau of training accuracy. However, it eventually manages to escape from this stagnation. During Phase III, a significant number of neurons are deactivated, leading to self-simplification of the network. The GF then adapts its learning approach using this simplified network configuration. In Phase IV, a considerable number of previously deactivated neurons are reactivated, resulting in self-complication of the network. Finally, the GF converges towards an initialization-dependent direction. Overall, the training process exhibits a remarkable behavior of transitioning from simplification to complication. The detailed analysis of each phase sheds light on the intricate dynamics involved in the learning process beyond the linear regime.

Strengths

The manuscript demonstrates excellent organization, comprehensiveness, and clarity, effectively covering crucial aspects such as a thorough review of related works and a comprehensive discussion of limitations. Moreover, the paper stands out by successfully combining empirical and theoretical approaches. Overall, this work makes significant contributions that advance the current state of the literature.

Weaknesses

These suggestions are intended to improve the overall clarity and accessibility of the research. The manuscript does not provide sufficient details regarding the resources and computational aspects involved in the research. Additionally, the work would greatly benefit from a clear delineation of its limitations. Outlined below are some limitations that underscore the weaknesses of the paper, despite its current status as the best effort in the field. The paper lacks a significant number of experimental results to demonstrate the robustness of the findings. It would greatly enhance the study's credibility to include additional examples where the predictions have been validated and to provide measures of their robustness. The submission would be strengthened by the addition of the code ran for the experiments

Questions

Dear authors, I have a few questions regarding your work that would greatly aid my comprehension: How reliable are the predictions made in this study, and what was the extent of experimentation conducted to support them? Can general principles be derived from this research that would benefit machine learning practitioners? Have alternative types of architectures been tested to determine if the findings hold true across different models as well (i.e., more realistic architectures and data sets)?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

The limitations of the proposed method are summarized as follows: * Narrow Scope: This study focuses exclusively on ReLU neural networks trained with Gradient Flow (GF) on linearly separable data. Although the analysis comprehensively captures the optimization process and identifies four distinct phases with rich nonlinear behaviors, the generalizability of the findings to other neural network types or more complex datasets may be limited. * Limited Generalization to Gradient Descent (GD): While the paper provides a detailed analysis of GF dynamics, it acknowledges that Gradient Descent (GD) dynamics are more complex and can exhibit additional nonlinear behaviors like progressive sharpening and the edge of stability. Consequently, a comprehensive understanding of the nonlinear behaviors during GD training is not fully explored in this study, indicating the need for future research in this direction. * Theoretical Understanding of Neural Network Training: While this work makes significant strides in theoretically understanding the training dynamics of neural networks, it acknowledges that there is still much progress to be made in fully comprehending the entire training process. Theoretical advancements related to nonlinear behaviors in neural network training, beyond the specific focus of this study, present valuable opportunities for future investigations. With this in mind I would like to suggest works like' The Neural Race Reduction: Dynamics of Abstraction in Gated Networks' Saxe 2022, that get analytical solution to 'Relu like' Neural Networks.

Summary

In this work, the authors attempt an exact analysis of the training dynamics of 2-layer ReLU networks trained via gradient flow on linearly separable data. Specifically, the authors aim to build on related work (e.g., Boursier et al. [2022] on square loss) to the case of: - Exponential loss (a more appropriate characteristic of classification problems) - With data having mild orthogonal separability Due to the additional non-linearity introduced by this specific loss type, and the complex data structure, the authors aim to characterize a richer non-linear structure. By considering a 2-layer network, where the second-layer weights are held fixed, the authors demonstrate that under gradient flow, the tunable weights of the network evolve in 4 distinctive phases, indicative of a simple to complex learning phenomena.

Strengths

- The authors extend the analytical formulation established in related previous literature to the case of the harder exponential loss type, which categorizes standard classification loss - The authors relax the data orthogonality assumption utilized in these previous works by considering a case where the angle of separability between data points is $<90^\circ$ - The authors demonstrate additional data condensation and alignment phases over existent work at the onset and the end of the training, thus attributing to the aim of capturing richer non-linear phenomena. - The authors establish bounds on the measure of the bounds on the count of the tunable *positive/negative* neurons in each phase along with the same on their norms, the time extent of these phases.

Weaknesses

1. While the authors do draw similarities between their work and that of [Boursier et al. [2022]]*, they refer to the latter as performing substantial simplifications and, therefore, unable to capture a lot of non-linear phenomena. Nevertheless, the authors of this work too adopt an identical model and initialization strategy as in the above-cited work. 1.1 **Most importantly** in Assumption 3.1, are the authors comprising a dataset using **just two data points**? If so, then that is an exceptionally restrictive assumption. 1.2 The reference to the usage of data averaged direction over the Gram-Schmidt type orthogonal direction, between that work and this, as defining a key improvement, is again not entirely justified if 1.1 above is true. In the case of a set of *non-degenerate* data vectors, defining *useful* orthogonal directions is challenging

Questions

- Can you detail how In Fig. 1, the projection to a 2D subspace span was performed? - If the specific dot product of Line 151 has to be true, then data should be normalized, yet that is not mentioned in Assumption 3.1 - Can you explain the reason behind the assumption on $T_1$ in Line 191? - Can you at least intuitively explain why the positive neuron has initial condensation/alignment with the label averaged direction $\mu$ and *then* transition to the expected $x_{-}^{\perp}$ direction? On a similar note, is there a reason only the negative neurons eventually *converge toward some specific directions dependent on both data and initialization*? Is it due to $p>1$? If so, I would assume the alignment signal impacts the positive labels over the negative ones, though.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

See Questions and Weaknesses

Thanks for the response

I appreciate the authors' response, and thus I would like to raise my score. Another question: in the global response Table 2, why did authors only compare $T_{\text{plat}}$ and $T_{\text{III}}$, instead of $T_\text{I}$ and $T_\text{II}$?