Escaping Saddle Points with the Successive Convex Approximation Algorithm

Abstract

Optimizing non-convex functions is of primary importance in the vast majority of machine learning algorithms. Even though many gradient descent based algorithms have been studied, successive convex approximation based algorithms have been recently empirically shown to converge faster. However, such successive convex approximation based algorithms can get stuck in a first-order stationary point. To avoid that, we propose an algorithm that perturbs the optimization variable slightly at the appropriate iteration. In addition to achieving the same convergence rate results as the non-perturbed version, we show that the proposed algorithm converges to a second order stationary point. Thus, the proposed algorithm escapes the saddle point efficiently and does not get stuck at the first order saddle points.

References in corpus (7)

• Decomposition by Partial Linearization: Parallel Optimization of Multi-Agent Systems
• Guaranteed Matrix Completion via Non-convex Factorization
• Parallel and Distributed Methods for Nonconvex Optimization--Part II: Applications
• Stochastic Successive Convex Approximation for Non-Convex Constrained Stochastic Optimization
• Online Learning with Inexact Proximal Online Gradient Descent Algorithms
• The Power of Normalization: Faster Evasion of Saddle Points
• Low-tubal-rank Tensor Completion using Alternating Minimization

Cited by in corpus (1)

• Escaping Saddle Points for Zeroth-order Nonconvex Optimization using Estimated Gradient Descent