Title: EMPIRICALLY CHARACTERIZING OVERPARAMETERI-ZATION IMPACT ON CONVERGENCE Anonymous authors Paper under double-blind review

Abstract: A long-held conventional wisdom states that larger models train more slowly when using gradient descent. This work challenges this widely-held belief, showing that larger models can potentially train faster despite the increasing computational requirements of each training step. In particular, we study the effect of network structure (depth and width) on halting time and show that larger models-wider models in particular-take fewer training steps to converge. We design simple experiments to quantitatively characterize the effect of overparametrization on weight space traversal. Results show that halting time improves when growing model's width for three different applications, and the improvement comes from each factor: The distance from initialized weights to converged weights shrinks with a power-law-like relationship, the average step size grows with a power-law-like relationship, and gradient vectors become more aligned with each other during traversal.

1. INTRODUCTION:

How does overparametrization affect the convergence? Arora et al. (2018) have shown that for a simple LNN increasing depth can accelerate optimization, but increasing width does not affect convergence. However, the conclusion of "width does not matter" is a consequence of an implicit assumption that minimum width is larger than input dimensionality. If hidden dimension is wide enough to absorb all the information within the input data, increasing width obviously would not affect convergence. For many real problems, however we are operating in a regime where hidden dimension is generally smaller than input dimension. In particular, RNN operate in this regime.

Using the machinery introduced in the work of Yin et al. (2017) , we will show that convergence rate is a function of direct distance from initialization point to final point, average step size and the average angle between gradient vectors and the path that connects current weights to final wights.

In this paper, we present a variety of experiments designed to characterize the effect of width on error surface. These experiments are designed to qualitatively answer simple questions. How does width affect the convergence? Why does wider network converge faster? Which factors contribute more to the convergence, increase in the step size, better alignment of gradient vectors towards the final weights or the reduction in direct distance? Is the improvement the result of increasing model capacity or there is a true acceleration phenomenon? Why does the convergence improvement slows down beyond a certain model size?

We study the characteristics of convergence curve and show that it can be characterized into a powerlaw region within which the number of gradient updates to convergence has a reciprocal relationship to model size and linear relationship to dataset size, and a flat region within which increasing model size does not affect convergence.

We analyze the error surface characteristics of overparametrized models. Our qualitative results suggest that as models get wider (1) direct distance from initial weight to final weights shrinks.

(2) Total path length traveled gets shrinks. (3) path length shrinks faster than direct distance. (4) step size gets larger. These results collectively suggests that number of local minimas in higher dimensional space grows asymmetrically wrt. origin and there exists a shorter path within the extra dimension to the newly-found local minimas. We also provide a simple theoretical analysis for a simplified problem of LNN and show that direct distance is expected to shrink as models get wider.

2. RELATED WORK:

Error Surface Characterization Researchers have extensively studied the properties of error surface in linear neural network (Choromanska et al. (2015) ; 

3. EXPERIMENTS:



3.1. SETUP:

When training a learner with an iterative method, such as gradient descent, we often observe that training error decreases steadily while validation/test set error decreases but to rise again or flattens when the model overfits or runs out of capacity. We define time-to-convergence as the number of iterations to reach to 1% of the minimum validation loss. For some application, validation curves are very noisy and so we need a margin of error. When validation curves flatten out, we measure the time before it gets to 1% of the minimum value. We increase the model size by increasing the model's width, while keeping all the other architecture parameters fixed (same learning rate, same batch size, etc.). We loot at three established RNN models: character-level language model (LM), word-level LM and speech recognition. The details of their configurations can be found in Appendix A.

3.2. CONVERGENCE CURVES:

Convergence curve shows the number of iterations (steps) to minimum validation loss for different model sizes.

Baseline Large learning rate are known to speedup the training process, while small learning rate slow down the training process. So to begin with, we use vanilla SGD, with fixed learning rate (0.8 for character model and 0.3 for word model) to train language models. Figure 1a and 1b show the convergence curve for character model and world model. X-axis and Y-axis are in logarithmic-scale. Different lines presents different dataset sizes. We can make the following observations from these figures:

• The number of steps to convergence drops and the drop-down pattern is well approximated with power law relationship (a * M odel Size -k + b).

• Increasing training size increases the number of steps to convergence.

• Power law slope is a function of application and its dataset.

Effect of Learning Rate on Convergence Pattern:

As mentioned previously, increasing the learning rate is expected to reduce the number of steps to minimum validation loss. We study how changing learning rate affects the power law trend. We train models once with learning rate 0.8 and once with learning rate 0.3. As depicted in Figure 2 (a) increasing the learning rate simply shifts down the curve (scaling down the a) without changing the slop (k). We also study how changing learning rate during the training process affect the power law trend. For this study, we use Adam optimizer which adaptively changes the learning rate during the training process. As shown in Figure 2 (b), using adaptive learning rate changes both the slope and intercept (changing both a and k).

Effect of Depth on Convergence Pattern So far we studied how the number of steps to minimum validation loss drops as models grows wider. Here, we will show same pattern holds for deeper model too. As shown in Figure 10a as models get deeper, the number of steps to minimum validation loss drops. These results are for character LM with vanilla SGD.

Effect of Training Set Size on Convergence Pattern:

As shown before, increasing dataset size increases the number of steps. As shown in Figure 10b the relationship between number of steps 

4. ANALYSIS:



4.1. CONVERGENCE CURVE PROFILE:

Figure 4 shows a sketch of a model's convergence curve-the reduction in number of steps to convergence as model size grows in number of parameters. Our empirical results indicate the curve begins in a seemingly "power-law" region where each new weight absorbs extra information from each sample, reducing the total number of samples observed before convergence. However, curves are likely to end in a "minimum data region" where number of steps cannot further decline-the data can offer no more information per sample. One can imagine this is one epoch if there is no redundancy in data, but can be potentially less than one if there is redundancy in data. Further study is required to understand the behavior of the convergence curve for small models.

4.2. THEORETICAL MACHINERY:

We use the machinery introduced by Yin et al. (2017) to characterize convergence as follows. Consider f i (W (t) ) to be the model's loss on sample i at time step t of gradient descent. Therefore, total loss and gradient at time step t can be presented as follows:

EQUATION

From the gradient descent formula, we have:

EQUATION

Where W * ∈ arg min W F (W ) presents the parameters of the best model. By applying these equation recursively, we find that:

EQUATION

Therefore, to find the minimum number of gradient updates required to reach within -proximity of the best answer, we can evaluate the following expectation:

EQUATION

Note here that in the above inequality, the first term presents the average distance from initialization point to the best answer (squared). Second term, presents the average step length (squared), and the third term captures the average degree of misalignment of gradient vectors from the direct path towards to the best answer, average distance from the best answer and average step size.

4.3. ERROR SURFACE CHARACTERIZATION:

To characterize the effect of overparametrization on convergence, we study how the network structure affects each of the following components: direct distance from initial point to final point, the average step length and average angle between weight vector and the path towards the best answer.

The results in this section are for character language model with SGD optimizer, described in subsection 3.1. We study the effect of overparametrization across different components of the model, i.e. embedding layer, hidden layers, softmax layer and all layers together. Y-axis in all the graphs are in log domain, unless otherwise specified. For every model size, we have repeated the experiment 10 times, starting from different random initialization point within the proximity of origin, therefore we use violin plot to show the distribution for each data point. This behavior is expected and can be explained theoretically (see Section B). One interpretation of this is that in higher dimensional space the number of locals minimas that are as good as global minimas exponentially increases ( Sagun et al. (2014) ) and if they are not symmetrically distibuted wrt. origin where the initial point lives around, there exists a potential for the direct distance to get shorter.

A closer look at Figure 6 also reveals that 1. For narrow models, weights within softmax layer travel farther than weights within hidden layers. However, for wider models the pattern is reverse. This transition happens at 2.3 million parameters. We know from Figure 5 that models greater than 1.2 million parameters are already overfitted, therefore the fact that hidden weights travel less than softmax layer for narrow models and reverse for larger models cannot be fully contributed to the lack of capacity in hidden layers for narrow models.

2. Softmax layer benefits the most from the width increase (25% reduction for softmax vs. 15% and 13% reduction for hidden and embedding layer, respectively).

3. A curve fitting reveals a logarithmic relationship between the direct distance and model's width. These results match with results presented in Yin et al. 's work where they showed that number of steps to convergence has a logarithmic relationship to direct distance, if the function is γ-strongly-convex, or β-smooth and µ-Polyak-Lojasiewicz (Theorem 4 and 7).

Step Size As shown in Figure 7 , average step size grows with model size.

Step size is basically the norm of the gradient vector and the norm of a vector has a square root relationship with the vector length, under the assumption that data distribution per element stays unchanged. This can happens if the new weight is independent of the previous weights. If the weights are correlated, one might expect the range of the values presented within each weight gets smaller as models gets wider since the error will be amortized across more weights. Therefore the growth in norm would be lower than square root relationship in the number of weights. Another extreme case is where the extra weights do not carry any signals and the norm does not change with hidden dimension.

A closer look at Figure 7 reveals that:

1.

Step size for softmax layer grows with almost square root relationship with model's width. This indicates that weights within softmax layer are absorbing new information as model's width grows.

2.:

Step size for hidden layer grows with Hidden Dimension 0.21 . This indicates either some of the new weights are zero or correlated with previous weights. 3. Weights within hidden layers take larger steps than weights within softmax layer and embedding layer. This can be partially contributed to larger number of weights in hidden dimension. 4. Weights within embedding layer do not show much improvement with model's width growth (10% increase for 16.5× larger model). This implies embedding does not extract much new information from extra weights.

Misalignment Figure 8 shows how misaligned are the gradient vectors with respect to the line connecting their position in the weight space to the starting point. Precisely, it is the average of the angle specified above measured along the path traveled from the starting point to the end point.

In precise term, we measure A s = arccos W (t) -W (0) ,∇F (W (t) ||W (t) -W (0) ||.||∇F (W (t) || . We use this as a proxy to the measure of misalignment of the gradeint vectors with respect to the line connecting their positions in the weight space to the final point, i.e. A e = arccos W (t) -W * ,∇F (W (t)

||W * -W (0) ||.||∇F (W (t) || . In the extreme case, where all gradient vectors are along the path connecting starting point to the end point, we expect to have A e = π -A s . Therefore increase in A s implies reduction in A e . As depicted, angles towards the origin are in average roughly π 2 and very slowly opens up as models get larger. This implies width does not affect angle alignment much and therefore, the reduction effect should come from increased step size and/or reduced distance.

A long-held conventional wisdom states that larger models train more slowly when using gradient descent. We challenge this widely-held belief, showing that larger models can potentially train 

A BENCHMARKS:

We evaluate our finding on three established deep learning models: character-level LM, word-level LM and speech recognition. Language models (LMs) aim to predict probability distributions for the next character, word, or other textual grams conditioned on previous sequence of input text. LMs are very important model features for domains such as speech recognition and machine translation, helping to identify most probable sequences of grams. Relative to other machine learning domains, LMs have low-dimensional input and output spaces, and can be trained with very large labeled sets. Speech recognition technologies convert acoustic speech signals into text or commands. Speech recognition is used in diverse applications such as voice-powered machine controls and conversational user interfaces. Researchers have spent decades developing hand-engineered speech recognition pipelines, and recently, have shifted to end-to-end deep learning based methods that show promising results (Hannun et al. (2014) ; Chorowski et al. (2015) ; Amodei et al. (2016)) . Speech recognition provides an interesting contrast to LMs as speech input data is medium-dimensionality time-series data.

Next we outline the configuration detail of each of these models.

• Word LM: We implement LSTM-based word LMs as described in Jozefowicz et al. (2016) with some small changes. To reduce the computational requirements of the models, we restrict the vocabulary to the top 10,000 most frequent words in the Billion Word Dataset (Chelba et al. (2013) ). The networks are 2-layer LSTMs, with sequence length of 80, the same number of hidden nodes in each layer. We scale the number of hidden nodes to increase the model size.

• Character LM: We use character-level LMs, which uses Recurrent Highway Networks (RHNs) ( Zilly et al. ( 2017)). Specifically, we train a single-layer, depth 10 RHN, sequence length 150, which we found to achieve SOTA accuracy on the Billion Word data set. We scale the number of hidden nodes and depth to increase the model size.

• Speech recognition: We train a recent SOTA model Deep Speech 2 (DS2). The DS2 model (Amodei et al. (2016) ) consists of two 2D convolution layers followed by four bidirectional LSTM recurrent layers. We use Adam to optimize CTC as the loss function (Graves et al. (2006) ). The inputs to this model is a sequence of log-spectrograms of power normalized audio clips, calculated on 20ms windows. Outputs are the English alphabet along with the blank symbol. These speech models do not include language models for output sequence beam search. We train on shards of labeled data set comprising 11,940 hours of speech containing 8 million utterances Amodei et al. (2016) . To vary the number of parameters, we vary the number of nodes in all LSTM layers, so that all layers have the same number of nodes. For the DS2 model, model sizes range between 300K to 193M parameters. As can be seen the average distance in n-dimensional space is always the projection of distance in (n -1)-dimensional space to the gradient direction in n-dimensional space. Therefore, the average distance is always expected to be smaller than the distance in previous dimension, so reduction in average distance from start point to final point is expected.

Note that this relationship is found under so many simplifying assumptions, including the assumption that new weights do not add any additional model capacity. Therefore, best-case loss will be the same as we add parameters. Further analysis is required to generalize this observation to non-scalar input, arbitrary matrix sizes and considering non-linearity.

:



Figures and Tables:

Figure 2: Learning Rate Impact on #Steps.

Figure 4: When growing model size (parameter count), the number of training epochs to converge declines until reaching a minimum number of passes through the training data.

Figure5(a) shows how model accuracy varies as model size grows. On the X-axis we have model size (in million parameters) and on the Y-axis we have the best accuracy at convergence point. As depicted, increasing model size beyond 1.2 million parameters pushes the model into an over-fitting regime. Figure5(b)shows that number of steps to convergence drops with a power law relationship within the interval of study. Training char LM with SGD optimizer is very slow and we did not run these experiments beyond 13 billion parameter models. Further study is required to see where this pattern starts to slow down. We know from Figure2that this pattern does not continue forever and indeed slows down and eventually stops. This implies there is a minimum number of epochs, or number of times to go through the data. Further study required to figure out if this number can go below one.

Figure 5: #Steps to Convergence and Accuracy at Convergence vs. Model Size (Distribution Across 10 Runs.)

Figure 6: Distribution of Direct Distance from Initial to Final Weights In the Weight Space (Across 10 Runs.)

Figure 8: Average Angle Between Gradient Vector and the path connecting the Current Weight to Initialization Point (Distribution Across 10 Runs.)

#Steps vs. Model Size Across Different Application Domains:X-axis represents model size in terms of the number of parameters in log-scale. Y-axis is the number of steps to minimum validation loss. Different lines represent different dataset sizes (percentage of full dataset). For character LM, we vary the dataset size from 0.01% to 0.4% of the 1B dataset. For word LM, we vary dataset size from 0.1% to 10% of 1B dataset. For speech, we vary the dataset size from 1% to 10% of an internal 20000 hour dataset.

Table content: <table><tr><td>#Steps to Min. Validation Loss</td><td>10 5</td><td>0.4% 0.2% 0.1% 0.04% 0.02% 0.01%</td><td>#Steps to Min. Validation Loss</td><td>10 4 10 5</td><td>10% 4% 2% 1% 0.4% 0.2% 0.1%</td><td>#Steps to Min. Validation Loss</td><td>10 4</td><td>10% 4% 2% 1% 0.4% 0.2% 0.1%</td></tr><tr><td/><td>10 5</td><td>10 6 Model Size (#Params) 10 7</td><td/><td>10 6 Model Size (#Params) 10 7</td><td>10 8</td><td/><td>10 6 Model Size (#Params) 10 7</td><td>10 8</td></tr><tr><td/><td/><td>(a) Character LM</td><td/><td colspan="2">(b) Word LM</td><td/><td>(c) Speech</td><td/></tr><tr><td colspan="2">Figure 1:</td><td/><td/><td/><td/><td/><td/><td/></tr></table>

Training char LM with SGD optimizer is very slow and we did not run these experiments beyond 13 billion parameter models. Further study is required to see where this

Table content: <table><tr><td/><td>1.460</td><td>Optimizer sgd</td><td>10</td><td colspan="2">5</td><td/><td/><td/><td>Optimizer sgd</td></tr><tr><td>Minimum Validation Loss</td><td>1.430 1.435 1.440 1.445 1.450 1.455</td><td>Number of Steps to Minimum Validation Loss</td><td colspan="2">4 × 10 6 × 10</td><td>4 4</td><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td>0 .8</td><td>1 .2</td><td>1 .6</td><td>2 .3</td><td>3 .3</td><td>4 .7</td><td>6 .6</td><td>9 .4</td><td>1 3 .2</td></tr><tr><td/><td>Model Size (million Parameters)</td><td/><td/><td/><td/><td/><td/><td colspan="2">Model Size (million Parameters)</td></tr><tr><td/><td>(a) #Validation Loss</td><td/><td/><td/><td/><td/><td colspan="3">(b) Number of Steps</td></tr></table>

Peer review (iclr2019):
 Understanding the effects of over-parametrization in neural network training has been a major challenge, albeit a lot of progress has been made in the past few years. The present paper is another attempt in this direction, with a slightly different point of view: the work characterizes the impact of over-parametrization in the number of iterations it takes an algorithm to converge. Along the way, it also presents further empirical observations such as the distance between the initial point and the final point and the angle between the gradients and the line that connects the initial and final points. Even though the observations presented are very interesting, unfortunately, the paper doesn*t have the level of rigor required that would make it a solid reference. The work presents its results somewhat clearly in the sense that one can simply reconstruct to probe in order to replicate the observations. This clarity is mainly due to the simplicity of the questions posed. There is nothing inherently wrong with simple questions, in fact, the kind of questions posed in the present paper are quite valuable, however, it lacks detailed study and rigor of a strong empirical work. Furthermore, the style of the exposition (anecdotal) and several obvious typos make the work look quite unfinished. Here are some flaws and suggestions that would improve the work substantially: - A deeper literature review would help guide the reader put the paper in a better context. Especially, the related work section is quite poor, how exactly do those papers appear related to the present work? Do they support similar ideas or do they propose different perspectives? - The exposition should be made more to the point and concise (for instance 3rd paragraph of section 4.3 where it starts with Figure 5(a) What*s meant by over-fitting regime, is it worse gen error, is it merely fitting tr data?.. How do we "know" from Figure 2, what*s a strong evidence? Some concepts such as the capacity do not have precise and commonly agreed upon definitions, the paper uses those quite a bit and sometimes only later on the reader understands what it actually refers to... The misalignment section is also quite unclear.) - The observations can be formalized and the curve fitting should be explained in further detail, the appendix touches upon simple cases but there is a strong literature behind those simple cases that could be quite useful for the purposes of the paper. - The authors have a lot of data available at no point the power law decay and exponent fitting are discussed. For a paper whose main point is this precise scaling, this looks like a major omission unless there is a specific reason for it (other than the hardness of fitting exponents to power laws). Merely showing the observables in a log-log plot weakens the support of the main claims. - The theoretical argument provided is just an elementary observation whose assumptions and conditions are not discussed. It is not a straightforward task, for instance, a suggestion for a theoretical result on the distance between the initial and final weights is presented here: Lemma 1 A.3 https://arxiv.org/abs/1806.07572 (distance shrink as the number of parameters increase consistent with the observations of the present paper) (note that this is in addition to the several early-2018 mean field approximations to NNs whose solutions are found in the limit where the number of parameters tend to infinity) - All the figures from 5 to 8 are presented very quantitatively such as looking at different layers and observing the percentage reductions. The message one can gain from such presentations are extremely limited and not systematic. I encourage the authors to formulate solid observables that can and should be tested in further detail. Even though the paper is touching upon very interesting questions, at its current stage, it is not a good fit to be presented in a conference as it only presents anecdotal evidence. There is a lot of room to improve, but the good news is that most of the improvement should be straightforward.