Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition

Abstract

We analyze stochastic gradient descent for optimizing non-convex functions. In many cases for non-convex functions the goal is to find a reasonable local minimum, and the main concern is that gradient updates are trapped in saddle points. In this paper we identify strict saddle property for non-convex problem that allows for efficient optimization. Using this property we show that stochastic gradient descent converges to a local minimum in a polynomial number of iterations. To the best of our knowledge this is the first work that gives global convergence guarantees for stochastic gradient descent on non-convex functions with exponentially many local minima and saddle points. Our analysis can be applied to orthogonal tensor decomposition, which is widely used in learning a rich class of latent variable models. We propose a new optimization formulation for the tensor decomposition problem that has strict saddle property. As a result we get the first online algorithm for orthogonal tensor decomposition with global convergence guarantee.

References in corpus (4)

• Exact solutions to the nonlinear dynamics of learning in deep linear neural networks
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• Online Tensor Methods for Learning Latent Variable Models

Cited by in corpus (39)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Non-convex Optimization for Machine Learning
• A Geometric Analysis of Phase Retrieval
• Nonconvex phase synchronization
• Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalization
• The Modern Mathematics of Deep Learning
• Global Optimality in Low-rank Matrix Optimization
• Implicit Full Waveform Inversion with Deep Neural Representation
• The Non-convex Geometry of Low-rank Matrix Optimization
• Noisy Activation Functions
• Solving Large-scale Systems of Random Quadratic Equations via Stochastic Truncated Amplitude Flow
• Portraying Double Higgs at the Large Hadron Collider
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
• On the different regimes of Stochastic Gradient Descent
• Spectral Learning on Matrices and Tensors
• AGMN: Association Graph-based Graph Matching Network for Coronary Artery Semantic Labeling on Invasive Coronary Angiograms
• On the existence of global minima and convergence analyses for gradient descent methods in the training of deep neural networks
• A proof of convergence for stochastic gradient descent in the training of artificial neural networks with ReLU activation for constant target functions
• Optimization Landscape of Tucker Decomposition
• On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks
• Non-Convex Matrix Completion Against a Semi-Random Adversary
• Fast, asymptotically efficient, recursive estimation in a Riemannian manifold
• Nearly optimal bounds for the global geometric landscape of phase retrieval
• Sparse random tensors: Concentration, regularization and applications
• Deep Online Convex Optimization with Gated Games
• A stochastic gradient descent approach with partitioned-truncated singular value decomposition for large-scale inverse problems of magnetic modulus data
• Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descent
• Reinforced stochastic gradient descent for deep neural network learning
• Towards an Understanding of Residual Networks Using Neural Tangent Hierarchy (NTH)
• A Random Matrix Perspective on Random Tensors
• Spectral Compressed Sensing via Projected Gradient Descent
• Leveraging Randomized Smoothing for Optimal Control of Nonsmooth Dynamical Systems
• Data-Adaptive Discriminative Feature Localization with Statistically Guaranteed Interpretation
• The loss landscape of deep linear neural networks: a second-order analysis
• Stochastic Gradient Langevin Dynamics with Variance Reduction
• FourierSAT: A Fourier Expansion-Based Algebraic Framework for Solving Hybrid Boolean Constraints
• Asymptotic properties of parallel Bayesian kernel density estimators
• One-dimensional System Arising in Stochastic Gradient Descent
• Eigenvectors of Orthogonally Decomposable Functions