A Convergence Theory Towards Practical
Over-parameterized Deep Neural Networks

Deep neural networks have achieved remarkable success in machine learning applications of different fields such as computer vision [Voulodimos et al., 2018], speech recognition [Hinton et al., 2012], and natural language processing [Devlin et al., 2018]. Much of this success is yet to be fully explained. One of the existing gaps is the network’s trainability, its ability to perfectly fit training data when initialized randomly and trained by first-order methods. Modern deep networks are commonly equipped with rectified linear unit (ReLU) activations [Xu et al., 2015], forming highly non-convex and non-smooth optimization problems. Such optimization problems are known to be generally computationally infeasible [Livni et al., 2014], and NP-hard in some cases [Blum and Rivest, 1989]. Nevertheless, in practice, trainability is often achieved in various tasks. Such empirical findings were summarized by  Zhang et al. [2016]: “Deep neural networks easily fit (random) labels”.

Previous theoretical works focused on networks’ expressivity [Bengio and Delalleau, 2011, Cohen et al., 2016], the existence of a solution that perfectly fits training data, therefore necessary for trainability. As it has been shown that even shallow nonlinear networks are universal approximators [Hornik et al., 1989], a better understanding of the power of depth was desired [Eldan and Shamir, 2016, Liang and Srikant, 2016, Telgarsky, 2015]. One conclusion is that increased depth allows exponentially more efficient representations, thus per parameter, deep networks can approximate a richer class of functions than shallow ones [Cohen et al., 2016, Liang and Srikant, 2016]. However, a recent work by Yun et al. [2019] provided tighter expressivity bounds on ReLU networks, showing that datasets of $n$ training examples can be perfectly expressed by a $3$-layer ReLU network with $\Omega{\left({\sqrt{n}}\right)}$ parameters. This does not explain the sizes of practical neural networks that are typically over-parameterized and exceed the training data’s size. It appears that expressivity can provide only a limited explanation for the overparameterization of modern neural networks, which keep growing deeper and wider in search of state-of-the-art results [Zagoruyko and Komodakis, 2016, Huang et al., 2019, Ridnik et al., 2020].

Important insights regarding trainability emerged from the analysis of simplified variants of neural networks. Deep linear networks are of special interest since increased depth does not affect their expressiveness, only changes their optimization landscape. Therefore the effects of increased width and depth on the training process can be isolated and carefully studied in this setting. Arora et al. [2018a] proved that trainability is attained at a linear rate under proper initialization as long as the network is wide enough. Arora et al. [2018b] showed that training with gradient-descent could be accelerated by increasing the network’s depth. Their empirical evaluations supported the existence of a similar outcome in deep nonlinear networks as well. Another simplified variant with further insights is overparameterized shallow nonlinear networks, typically with a single hidden layer. Du and Lee [2018] proved that for a quadratic activation function all local minima are global minima. Safran and Shamir [2018] showed that ReLU networks suffer from spurious local minima, which can be drastically reduced by overparameterization. Oymak and Soltanolkotabi [2020] achieved trainability where the proportion between the number of hidden units and training examples $n$ depends on the activation: for smooth ones it is $\Omega\left({n^{2}}\right)$ while for ReLU it is significantly larger, $\Omega\left({n^{4}}\right)$. Additional works examined the unique dynamics of ReLU activation during the training and their relation to gradient-descent optimization [Li and Liang, 2018, Arora et al., 2019b].

The analysis of deep ReLU networks is more challenging, as additional problems emerge with increased depth. Exploding and vanishing gradient [Hanin, 2018] and bias shifts [Clevert et al., 2015] are shared with additional activations, while the dying ReLUs problem, causing them to remain inactive permanently, is unique [Lu et al., 2019]. While in practice those problems are solved by the introduction of additional tensor transformations [Ioffe and Szegedy, 2015, He et al., 2016b], their theoretical understanding remains limited. Correspondingly, existing trainability guarantees for deep ReLU networks are considerably weaker compared with shallow networks. Du et al. [2019] required a minimal network width which scales exponentially with its depth $L$ and polynomially with the number of examples $n$. More recent works [Zou et al., 2018, Allen-Zhu et al., 2019] improved the dependencies to be high-order polynomials, $\Omega\left({n^{26}L^{38}}\right)$ and $\Omega\left({n^{24}L^{12}}\right)$ correspondingly. The best known result, by Zou and Gu [2019], required a network width of $\Omega\left({n^{8}L^{12}}\right)$, which is still prohibitively large compared to practice. For instance, training their network with $1001$ layers [He et al., 2016b] over the common ImageNet dataset [Krizhevsky et al., 2017] requires a network of $\Omega\left({10^{172}}\right)$ parameters, while the largest one reported contains only $O\left({10^{11}}\right)$ [Brown et al., 2020].

In this work, we take a step towards closing the gap between theory and practice. We develop a novel technique to analyze the trainability of overparameterized deep neural networks and provide convergence guarantees under size requirements that are significantly milder than previously known. The network width required by our analysis for trainability scales only quadratically with $n$, enabling for the first time empirical evaluation of the theoretical bounds, and bridging previous empirical results related to overparameterization. In addition, the required width by our theory is linear with $L$, paving the way for a better understanding of the behavior of deep neural networks of practical depths. Finally, the number of training iterations for reaching global minima by our theory is logarithmic in $nL$, significantly smaller than previous theoretical results and similar to leading practical applications (e.g., BiT [Kolesnikov et al., 2019]). A full comparison with previous methods can be found in Table 1.

A key novelty of our analysis is the construction of a surrogate network, named Gated ReLU or GReLU, illustrated in Figure 1. The activation patterns of GReLU, i.e. which entries output zero [Hanin and Rolnick, 2019b], are determined at initialization and kept fixed during training. They are set by a random transformation of the input, independent of the network initialization. Therefore, GReLU networks are immune to two main problems of training ReLU networks, dying ReLUs and bias shifts, while still enjoying the advantages of ReLU activation. We first prove tighter bounds on the width and convergence time for training GReLU networks, then show that they can be transformed to equivalent ReLU networks with $100\%$ train accuracy. We further investigate the proposed technique and derive a finite-width Neural Tangent Kernel equivalence with a improved condition on the network width. Finally, we empirically validate the effectiveness of our technique with datasets of different domains and practical network sizes.

Our main contribution can be summarized as follows

• •

  We show that a randomly initialized deep ReLU network of depth $L$ and width $m=\tilde{\Omega}{\left({n^{2}L}\right)}$ trained over $n$ samples of dimension $d$, reaches $\varepsilon$-error global minimum for $\ell_{2}$ regression in a logarithmic number of iterations, $T=c\log\left({\frac{n^{3}L}{d\epsilon}}\right)$. For comparison, the previous state-of-the-art result by Zou and Gu [2019] required $m=\tilde{O}\left({n^{8}L^{12}}\right)$, $T=O\left({n^{2}L^{2}\log(\frac{1}{\varepsilon})}\right)$.

• •

  To achieve that, we propose a novel technique of training a surrogate network with fixed activation patterns that can be transformed to its equivalent ReLU network at any point. It is immune to bias-shifts and dying-ReLU problems and converges faster without affecting generalization, as we empirically demonstrate.

• •

  We derive an NTK equivalence for GReLU networks with width linear in $n$, connecting the regimes of practical networks and kernel methods for the first time (improving $\tilde{\Omega}\left({n^{3}2^{O(L)}}\right)$ by Huang and Yau [2020]). This connection allows utilizing NTK-driven theoretic discoveries for practical neural networks, most notably generalization theory.

The remainder of this paper is organized as follows. In section 2 we state the problem setup and introduce our technique. Our main theoretical result is covered in section 3, followed by additional properties of the proposed technique in Section 4. In section 5 we provide a proof sketch of the main theory, and in section 6 we empirically demonstrate its properties and effectiveness. Section 7 contains additional related work. Finally, section 8 concludes our work.

In this section we introduce the main problem and the novel setup which is used to solve it.
Notations: we denote the Euclidean norm of vector $v$ by $\left\lVert v\right\rVert$ or $\left\lVert v\right\rVert_{2}$, and the Kronecker product and Frobenius inner-product for matrices $M,N$ by $M\otimes N$, $\langle M,N\rangle$ respectively. We denote by $\lambda_{\min}(M)$, $\lambda_{\max}(M)$ matrix minimal and maximal eigenvalues. We use the shorthand $[k]$ to denote the set $\{1,\dots,k\}$ and $A_{[k]}=\{A_{1},\dots,A_{k}\}$. We denote the positive part of a vector by $[v]^{+}=\left({\max(0,v_{1}),\dots,\max(0,v_{d})}\right)$ and its indicator vector by $[v]_{+}=(\mathbbm{1}_{v_{1}>0},\dots,\mathbbm{1}_{v_{d}>0})$. Matrix column-wise vectorization is denoted by $\mbox{vec}\left(\right)$. For two sequences $\{a_{n}\},\{b_{n}\}$, we denote $a_{n}=O(b_{n})$ if there exist a constant $C_{o}$ such that $a_{n}\leq C_{o}b_{n}$, and $a_{n}=\Omega(b_{n})$ if a constant $C_{\Omega}$ satisfies $a_{n}\geq C_{\Omega}b_{n}$. In addition, we denote $\tilde{O}(\cdot),\tilde{\Omega}(\cdot)$ to hide logarithmic factors. Finally, we denote the normal and chi-square distributions by $\mathcal{N}(\mu,\Sigma),\chi^{2}_{d}$ respectively.

In this section, we present our main theoretical results. We start with making the following assumptions on the training data.

In this section, we discuss the properties of the suggested technique. It complements the former section by providing intuition on why we are able to achieve the rates in Theorem 1, which are more similar to sizes used in practice.

First, it is important to note that modern state-of-the-art models are not based on fully-connected networks but rather on improved architectures. A classic example is the improved optimization achieved by residual connections [He et al., 2016a]. Neural networks equipped with residual connections typically retain an improved empirical performance for a relatively small degradation in runtime [Monti et al., 2018]. However, Previous theoretical works on trainability of residual networks do not share those improvements [Allen-Zhu et al., 2019, Du et al., 2018]. Few works have shown that a residual network can be transformed to its equivalent network with no residual connections (e.g.  [Monti et al., 2018]).

Similarly to residual networks, GReLU networks offer appealing properties regarding the optimization of deep networks (Section 4.3), and can be mapped to their equivalent ReLU networks at any time (Section 4.1). Unlike residual networks, GReLU networks are based on theoretical guarantees (Sections 3, 4.2), and actually accelerate the network runtime as discussed in Section 4.4.

Calculating the gradient of $\ell(W_{t})$ over $W_{t,k}$, denoted by $\nabla_{k}\ell(W_{t})$, is straightforward,

where

and we set $G_{t,0}^{i}=D_{0}^{i}C$. Those represent the network partition and will be referred to as sub-networks. Notice that $W^{i}_{t}=F^{i}_{t,k+1}G^{i}_{t,k}$. We now calculate the difference between $W_{t+1}^{i}$ and $W_{t}^{i}$.

In this section, we provide empirical validation of our theoretical results, as well as further testing on complementary setups. We wish to answer the following questions:

1. 1.

   Is the theoretical guarantee of Theorem 1 tight, or can it be further improved?

2. 2.

   How well do GReLU networks train and generalize compared to ReLU networks?

3. 3.

   What is the difference between the training dynamics of GReLU and ReLU when optimized with gradient-descent?

The next sections are dedicated to discuss these questions. For fairness, we compare networks with the same width and depth, initialization described in Section 2, and trained by gradient descent with a constant learning rate for each train. The term MSE refers to the sum of squared errors described in (2). Since the theory covers general setups, it often uses small learning rate values to fit all setups, while in practice larger values can be utilized for faster convergence. Therefore, we experiment with a variety of learning rates according to the task. In addition, in all the experiments we optimize with batch gradient-descent due to hardware constraints. We pick the largest possible batch size per experiment.

Neural network overparameterization has been extensively studied under different assumptions over the training data and network architecture. For the simplified case of well-separated data, Ji and Telgarsky [2018] showed that a poly-logarithmic width is sufficient to guarantee convergence in two-layer networks, and Chen et al. [2019] extended the result to deep networks using the NTRF function class by Cao and Gu [2019]. For mixtures of well-separated distributions,  Li and Liang [2018] proved that when training two-layer networks with width proportional to a high-order polynomial in the parameters of the problem with SGD, small train and generalization errors are achievable. Other common assumptions include Gaussian input [Brutzkus and Globerson, 2017, Zhong et al., 2017, Li and Yuan, 2017], independet activations [Choromanska et al., 2015, Kawaguchi, 2016], and output generated by a teacher-network [Li and Yuan, 2017, Zhang et al., 2019b, Brutzkus and Globerson, 2017]. In our work, only a mild assumption of non-degenerate input is used.
overparameterization of special neural networks is varied across the analysis of linear networks [Kawaguchi, 2016, Arora et al., 2018a, Bartlett et al., 2018], smooth activations [Du and Lee, 2018, Kawaguchi and Huang, 2019], and shallow networks [Du and Lee, 2018, Oymak and Soltanolkotabi, 2020]. For deep linear networks, Kawaguchi [2016] proved that all local minima are global minima. Arora et al. [2018a] proved trainability for deep linear networks of minimal width, generalizing result by Bartlett et al. [2018] on residual linear networks. Du and Lee [2018] considered neural networks with smooth activations, and showed that in overparameterized shallow networks with quadratic activation, all local minima are global minima. Kawaguchi and Huang [2019] showed that when only the output layer is trained, i.e. least squares estimate with gradient descent, tighter bounds on network width are achievable. Such training assumptions are rarely used in practice due to poor generalization. Considering one-hidden-layer networks, Du et al. [2018] showed that under the assumption of non-degenerate population Gram matrix, gradient-descent converges to a globally optimal solution. Oymak and Soltanolkotabi [2020] stated the current tightest bound on the width of shallow networks for different activation functions. For the ReLU activation, the bound we derive for deep networks improves theirs over shallow networks as well.
We focus on the general setting of deep networks equipped with ReLU activation, as typically used in practice. Similar works [Zou et al., 2018, Du et al., 2019, Allen-Zhu et al., 2019, Zou and Gu, 2019] require unrealistic overparameterization conditions, namely a minimal width proportional to the size of the dataset in the power of $(8,24,26)$ [Zou and Gu, 2019, Allen-Zhu et al., 2019, Zou et al., 2018], and the depth of the network in the power of $(12$-$38)$  [Zou and Gu, 2019, Zou et al., 2018] or exponential dependency [Du et al., 2019]. Our work improves the current tightest bound [Zou and Gu, 2019] by a factor of $O\left({n^{6}L^{11}}\right)$, with a corresponding significant decrease in convergence time, from polynomial to logarithmic in the parameters of the problem.
Optimization landscape of deep networks under different assumptions is an active line of research. A few works showed that ReLU networks have bad local minima [Venturi et al., 2018, Safran and Shamir, 2018, Swirszcz et al., 2016, Yun et al., 2017] due to ”dead regions”, even for random input data and labels created according to a planted model [Yun et al., 2017, Safran and Shamir, 2018], a property which is not shared with smooth activations [Liang et al., 2018, Du and Lee, 2018, Soltanolkotabi et al., 2018]. Specifically, Hardt and Ma [2016] showed that deep linear residual networks have no spurious local minima.
Training dynamics of ReLU networks and their activation patterns were studied by few recent works [Hanin and Rolnick, 2019a, b, Li and Liang, 2018]. Hanin and Rolnick [2019b] showed that the average number of patterns along the training is significantly smaller than the possible one and only weakly depends on the depth. We study a single random pattern, entirely decoupled from depth. Li and Liang [2018] studied ”pseudo gradients” for shallow networks, close in spirit with the fixed ReLU activations suggested by our work. They showed that unless the generalization error is small, pseudo gradients remain large, providing motivation for fixing activation patterns from a generalization perspective. Furthermore, they showed that pseudo gradients could be coupled with original gradients for most cases when the network is sufficiently overparameterized.
Neural Tangent Kernel regression has been shown to describe the evolution of infinitely wide fully-connected networks when trained with gradient descent [Jacot et al., 2018]. Additional works provided corresponding kernels for residual [Huang et al., 2020] and convolutional networks [Li et al., 2019], allowing to study the training dynamics of those in functional space. Few works [Belkin et al., 2018b, Cao and Gu, 2019, Belkin et al., 2018a, Liang et al., 2020] analyzed NTK for explaining properties for deep neural networks, most notably their trainability and generalizability. An important result by Allen-Zhu et al. [2019] extended the NTK equivalence to deep networks of finite width. We provide an improved condition on the required width for this equivalence to hold.

In this paper we proposed a novel technique for studying overparameterized deep ReLU networks which leads to state-of-the-art guarantees on trainability. Both the required network size and convergence time significantly improve previous theory and can be tested in practice for the first time. Further theoretical and empirical analysis provide insights on the optimization of neural networks with first-order methods. Our analysis and proof technique can be extended to additional setups such as optimization with stochastic gradient-descent, cross-entropy loss, and other network architectures such as convolutional and residual networks similarly to [Zhang et al., 2019a, Allen-Zhu et al., 2019, Du et al., 2018]. Our encouraging empirical results motivate analyzing additional variants like Gated-CNNs and Gated-ResNets. Our improved finite-width NTK equivalence enables studying neural networks of practical sizes using kernel theory, potentially leading to a better understanding of learning dynamics and generalization.

We would like to thank Assaf Hallak, Tal Ridnik, Avi Ben-Cohen, Yushun Zhang and Itamar Friedman for their feedbacks and productive discussions.

We start with training networks of width $4096$ and depth $10$ over SGEMM, and plot their losses along the training with varied learning rates in Figures 4(a) for the GReLU and 4(b) for the ReLU network. While for smaller rates results are quite similar, for larger ones the losses of the GReLU network decrease more monotonically and reach lower values. A comparison of high learning rates in Figure 5 shows that ReLU network oscillates with larger amplitudes towards higher loss values. The losses of the GReLU network decrease more monotonically, and reach smaller values with larger learning rates. Both networks do not reach zero loss, as their widths are smaller than required by our theory. We further test GReLU with a fixed learning rate for different widths and depths, and present the results in Figure 4(c). While both increased depth and width improve the results, deeper and narrower networks perform better for the same number of parameters. This result is consistent with similar comparisons of ReLU networks in previous works.