Global Optimality in Tensor Factorization, Deep Learning, and Beyond
This provides a theoretical foundation for improving optimization in machine learning, particularly for deep learning with ReLUs, though it is incremental in extending convex relaxation ideas to broader non-convex settings.
The paper tackles the non-convex optimization challenges in factorization problems like matrix and tensor factorization and deep neural network training by developing a general framework that ensures local minima are global under certain conditions, enabling global optimization from any initialization with local descent algorithms when factorized variables are sufficiently large.
Techniques involving factorization are found in a wide range of applications and have enjoyed significant empirical success in many fields. However, common to a vast majority of these problems is the significant disadvantage that the associated optimization problems are typically non-convex due to a multilinear form or other convexity destroying transformation. Here we build on ideas from convex relaxations of matrix factorizations and present a very general framework which allows for the analysis of a wide range of non-convex factorization problems - including matrix factorization, tensor factorization, and deep neural network training formulations. We derive sufficient conditions to guarantee that a local minimum of the non-convex optimization problem is a global minimum and show that if the size of the factorized variables is large enough then from any initialization it is possible to find a global minimizer using a purely local descent algorithm. Our framework also provides a partial theoretical justification for the increasingly common use of Rectified Linear Units (ReLUs) in deep neural networks and offers guidance on deep network architectures and regularization strategies to facilitate efficient optimization.