Global Optimality in Tensor Factorization, Deep Learning, and Beyond

Abstract

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.

References in corpus (3)

• The Loss Surfaces of Multilayer Networks
• Breaking the Curse of Dimensionality with Convex Neural Networks
• Convex Sparse Matrix Factorizations

Cited by in corpus (54)

• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Robust Large Margin Deep Neural Networks
• Gradient Descent Finds Global Minima of Deep Neural Networks
• Tensor Methods in Computer Vision and Deep Learning
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• Understanding Deep Neural Networks with Rectified Linear Units
• On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization
• Entropy-SGD: Biasing Gradient Descent Into Wide Valleys
• The Non-convex Geometry of Low-rank Matrix Optimization
• Mathematics of Deep Learning
• Tensor Regression Networks
• Depth Creates No Bad Local Minima
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Understanding the Loss Surface of Neural Networks for Binary Classification
• A Geometric Analysis of Neural Collapse with Unconstrained Features
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• Theoretical properties of the global optimizer of two layer neural network
• Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced
• Convexified Convolutional Neural Networks
• Optimization and Generalization of Shallow Neural Networks with Quadratic Activation Functions
• Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks
• On the energy landscape of deep networks
• Constrained Deep Learning using Conditional Gradient and Applications in Computer Vision
• An Unconstrained Layer-Peeled Perspective on Neural Collapse
• How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?
• Tensor Contraction Layers for Parsimonious Deep Nets
• Invariance of Weight Distributions in Rectified MLPs
• Weight Sharing is Crucial to Succesful Optimization
• Stationary Points of Shallow Neural Networks with Quadratic Activation Function
• Interpreting Deep Learning: The Machine Learning Rorschach Test?
• Matrix Completion and Related Problems via Strong Duality
• Tensor Robust Principal Component Analysis: Better recovery with atomic norm regularization
• Improved Learning of One-hidden-layer Convolutional Neural Networks with Overlaps
• Noether: The More Things Change, the More Stay the Same
• Why Learning of Large-Scale Neural Networks Behaves Like Convex Optimization
• Tensor Graphical Model: Non-convex Optimization and Statistical Inference
• Marginalizable Density Models
• Stochastic Conditional Generative Networks with Basis Decomposition
• Deep Net Triage: Analyzing the Importance of Network Layers via Structural Compression
• An Analysis of Dropout for Matrix Factorization
• Differentially Private Adapters for Parameter Efficient Acoustic Modeling
• Escaping Saddle-Points Faster under Interpolation-like Conditions
• Two-level monotonic multistage recommender systems
• The Nonconvex Geometry of Linear Inverse Problems
• Benefits of over-parameterization with EM
• Towards an understanding of CNNs: analysing the recovery of activation pathways via Deep Convolutional Sparse Coding
• The Hidden Convex Optimization Landscape of Two-Layer ReLU Neural Networks: an Exact Characterization of the Optimal Solutions
• Over-Parametrized Matrix Factorization in the Presence of Spurious Stationary Points
• How ConvNets model Non-linear Transformations
• Learning Graph Neural Networks with Approximate Gradient Descent