The Global Convergence of the Alternating Minimization Algorithm for Deep Neural Network Problems
Junxiang Wang, Fuxun Yu, Xiang Chen, Liang Zhao · arXiv (Cornell University) · 2018
In recent years, stochastic gradient descent (SGD) and its variants have been the dominant optimization methods for training deep neural networks. However, SGD suffers from limitations such as the lack of theoretical guarantees, vanishing gradients, excessive sensitivity to input, and difficulties solving highly non-smooth constraints and functions. To overcome these drawbacks, alternating minimization-based methods for deep neural network optimization have attracted fast-increasing attention recently. As an emerging and open domain, however, several new challenges need to be addressed, including: 1) there is no guarantee of global convergence under mild, practical conditions, and 2) cubic time complexity in the size of feature dimensions. We therefore propose a novel Deep Learning Alternating Minimization (DLAM) algorithm to deal with these two challenges. Our innovative inequality-constrained formulation infinitely approximates the original problem with non-convex equality constraints, enabling our proof of global convergence of the DLAM algorithm under mild, practical conditions. The time complexity is successfully reduced from $O(d^3)$ to $O(d^2)$ via a dedicated algorithm design for subproblems that is enhanced by iterative quadratic approximations and backtracking. Experiments on benchmark datasets demonstrate the effectiveness of our proposed DLAM algorithm.