On the Sublinear Convergence of Randomly Perturbed Alternating Gradient Descent to Second Order Stationary Solutions

Abstract

The alternating gradient descent (AGD) is a simple but popular algorithm which has been applied to problems in optimization, machine learning, data ming, and signal processing, etc. The algorithm updates two blocks of variables in an alternating manner, in which a gradient step is taken on one block, while keeping the remaining block fixed. When the objective function is nonconvex, it is well-known the AGD converges to the first-order stationary solution with a global sublinear rate. In this paper, we show that a variant of AGD-type algorithms will not be trapped by "bad" stationary solutions such as saddle points and local maximum points. In particular, we consider a smooth unconstrained optimization problem, and propose a perturbed AGD (PA-GD) which converges (with high probability) to the set of second-order stationary solutions (SS2) with a global sublinear rate. To the best of our knowledge, this is the first alternating type algorithm which takes $\mathcal{O}(\text{polylog}(d)/{\epsilon }^{7/3})$ iterations to achieve SS2 with high probability [where polylog$(d)$ is polynomial of the logarithm of dimension $d$ of the problem].

References in corpus (8)

• First-order Methods Almost Always Avoid Saddle Points
• Neon2: Finding Local Minima via First-Order Oracles
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• A Nonconvex Splitting Method for Symmetric Nonnegative Matrix Factorization: Convergence Analysis and Optimality
• A Generic Approach for Escaping Saddle points
• Porcupine Neural Networks: (Almost) All Local Optima are Global
• NEON+: Accelerated Gradient Methods for Extracting Negative Curvature for Non-Convex Optimization
• Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently

Cited by in corpus (1)

• Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalization