Step Size Matters in Deep Learning
Training a neural network with the gradient descent algorithm gives rise to a discrete-time nonlinear dynamical system. Consequently, behaviors that are typically observed in these systems emerge during training, such as convergence to an orbit but not to a fixed point or dependence of convergence on the initialization.
Step size of the algorithm plays a critical role in these behaviors: it determines the subset of the local optima that the algorithm can converge to, and it specifies the magnitude of the oscillations if the algorithm converges to an orbit. To elucidate the effects of the step size on training of neural networks, we study the gradient descent algorithm as a discrete-time dynamical system, and by analyzing the Lyapunov stability of different solutions, we show the relationship between the step size of the algorithm and the solutions that can be obtained with this algorithm. The results provide an explanation for several phenomena observed in practice, including the deterioration in the training error with increased depth, the hardness of estimating linear mappings with large singular values, and the distinct performance of deep residual networks.
This paper analyzes the effect of the choice of step length for the (full-batch) gradient method applied to feed-forward linear networks and two-layer (one hidden layer) ReLU networks from a discrete-time dynamical system perspective. In particular, the bounds on the steplength characterize which minima the algorithm can converge to when certain steplengths are used in the algorithm. A more in-depth analysis is also provided for the case of symmetric positive definite matrices, in which the maximum steplength can be used when the parameters are initialized with the identity matrix.  Overall, the paper provides novel bounds on the step length necessary to converge to a certain subset of stationary points. This corresponds with my understanding that practitioners are indeed selecting their initialization and learning rate schedules for SGD to specifically converge to particular local minima that have better generalization properties.   Although these theoretical results are very interesting, they are motivated improperly, in my opinion. I expand on this point below:  1. Explanation of Training Error Behavior  Coming from a background in optimization rather than dynamical systems, the first contribution (line 80) highlighting the reason the training error stops decreasing is already well understood from an optimization perspective, in my opinion. In particular, the convergence of the gradient method for strongly convex functions with fixed step length requires Lipschitz continuity of the gradient (or smoothness). This makes some claims (such as the claim on large singular values in line 263-264) trivial. If the smoothness condition does not hold, one may have to diminish the step length in order to converge to the solution.   In the more realistic case in which we are applying the stochastic (sub)gradient method, we know that it indeed requires a diminishing steplength (typically non-summable but square-summable) in order to converge to the solution; otherwise, the algorithm only is guaranteed to converge to a neighborhood of the solution. See Bottou, et al. (2018) for a review on the convergence analysis of stochastic gradient methods. In this sense, the claim that the (stochastic) gradient method is converging to a periodic orbit in dynamical systems is similar to the results of only having guarantees to converge to a neighborhood of the solution, which is already sufficient to explain the plots from He, et al. (2016).  Rather than motivating the theoretical results from this angle (which I would consider to be uninteresting and well-known from optimization), I would suggest the authors take the approach of claiming to provide theory that better elucidates the connection between the choice of step length and the subset of local optima the algorithm can converge to, from a dynamical systems perspective. This is the part of the paper that I would consider most novel and interesting, specifically towards understanding the training of neural networks.  2. Stochastic vs. Deterministic  Unfortunately, the paper fails to address how the use of stochasticity in the stochastic gradient method could impact these results for the choice of step length. Instead, the paper only analyzes the case for the full gradient method, which is not representative of what is used in practice (which also takes away from the first contribution). If these results claim to establish the relationship between the choice of step length for training neural networks, the paper must address the lack of stochasticity of the method considered in the analysis and use these results as a theoretical building block towards understanding the stochastic gradient method for training neural networks.  3. Relationship with Lipschitz Continuity and Smoothness  Lastly, I would suggest the authors provide a more in-depth investigation of the connection between these results and the local Lipschitz and smoothness constants of the objective function. I’m curious how these results may be related to the typical convergence analysis of the gradient method in optimization. For instance, in the first example (line 36), the function considered does not have a global smoothness constant; hence, the gradient method would require a diminishing step length in order to converge from any initialization. This is clearly reflected in the example.  Minor Comments and Questions: - Should always say “the gradient method” or “the gradient descent algorithm”, not “the gradient descent”. - The networks considered are not relevant to practice, but this is OK given that the analysis of neural networks have mainly been limited to linear and ReLU feed-forward networks. - The paper is well-written.  Summary:  In summary, this paper provides some elucidating theoretical results on the set of local minima that the gradient method will converge to for certain choices of step size for simple feed-forward networks. This could be motivated better from a different angle as described earlier, without the comment explaining the convergence of the method to a periodic orbit or neighborhood of the solution, which is well-known in optimization. Because of its theoretical novelty, I believe that this well-written paper is indeed worthy of publication, with some minor edits and perhaps a major change in approach and introduction.  ================================ Post-Author Response:  I thank the authors for their well-crafted response, particularly for clarifying the comment made in Lines 263-264. In light of the changes proposed in the response regarding the introduction and additional remarks, I have raised my score to a 7.