Avoiding strict saddle points of nonconvex regularized problems

In this paper, we consider a class of non-convex and non-smooth sparse optimization problems, which encompass most existing nonconvex sparsity-inducing terms. We show the second-order optimality conditions only depend on the nonzeros of the stationary points. We propose two damped iterative reweighted algorithms including the iteratively reweighted ℓ1 algorithm (DIRL1) and the iteratively reweighted ℓ2 (DIRL2) algorithm, to solve these problems. For DIRL1, we show the reweighted ℓ1 subproblem has support identification property so that DIRL1 locally reverts to a gradient descent algorithm around a stationary point. For DIRL2, we show the solution map of the reweighted ℓ2 subproblem is differentiable and Lipschitz continuous everywhere. Therefore, the map of DIRL1 and DIRL2 and their inverse are Lipschitz continuous, and the strict saddle points are their unstable fixed points. By applying the stable manifold theorem, these algorithms are shown to converge only to local minimizers with randomly initialization when the strictly saddle point property is assumed.