Improved Analysis of Clipping Algorithms for Non-convex Optimization

Abstract

Gradient clipping is commonly used in training deep neural networks partly due to its practicability in relieving the exploding gradient problem. Recently, \citet{zhang2019gradient} show that clipped (stochastic) Gradient Descent (GD) converges faster than vanilla GD/SGD via introducing a new assumption called $(L_0,L_1)$-smoothness, which characterizes the violent fluctuation of gradients typically encountered in deep neural networks. However, their iteration complexities on the problem-dependent parameters are rather pessimistic, and theoretical justification of clipping combined with other crucial techniques, e.g. momentum acceleration, are still lacking. In this paper, we bridge the gap by presenting a general framework to study the clipping algorithms, which also takes momentum methods into consideration. We provide convergence analysis of the framework in both deterministic and stochastic setting, and demonstrate the tightness of our results by comparing them with existing lower bounds. Our results imply that the efficiency of clipping methods will not degenerate even in highly non-smooth regions of the landscape. Experiments confirm the superiority of clipping-based methods in deep learning tasks.

41 pages, 12 figures, to appear in NeurIPS 2020. arXiv admin note: text overlap with arXiv:1905.11881 by other authors

References in corpus (11)

• Adam: A Method for Stochastic Optimization
• Deep Learning with Differential Privacy
• On the difficulty of training Recurrent Neural Networks
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Large Batch Training of Convolutional Networks
• Regularizing and Optimizing LSTM Language Models
• Why gradient clipping accelerates training: A theoretical justification for adaptivity
• The Power of Normalization: Faster Evasion of Saddle Points
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions
• The Complexity of Finding Stationary Points with Stochastic Gradient Descent
• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping

Cited by in corpus (2)

• Stability and Convergence of Stochastic Gradient Clipping: Beyond Lipschitz Continuity and Smoothness
• Improving the Robustness of the Projected Gradient Descent Method for Nonlinear Constrained Optimization Problems in Topology Optimization