Avoiding Strict Saddle Points of Nonconvex Regularized Problems

Abstract. This paper considers a class of nonconvex and nonsmooth sparse optimization problems, encompassing most existing nonconvex sparsity-inducing terms. We show that their second-order optimality conditions depend only on the nonzeros of the stationary points. We propose two damped iteratively reweighted algorithms, which are the iteratively reweighted [Formula: see text] algorithm (DIRL[Formula: see text]) and the iteratively reweighted [Formula: see text] (DIRL[Formula: see text]) algorithm, to solve these problems. For DIRL[Formula: see text], we show that the reweighted [Formula: see text] subproblem has the support identification property so that DIRL[Formula: see text] locally reverts to a gradient descent algorithm around a stationary point. For DIRL[Formula: see text], we show that the solution map of the reweighted [Formula: see text] subproblem is differentiable and Lipschitz continuous everywhere. Therefore, the solution maps of DIRL[Formula: see text] and DIRL[Formula: see text] and their inverses are Lipschitz continuous, and the strict saddle points are their unstable fixed points. By applying the stable manifold theorem, these algorithms starting from almost every initial point are shown to converge to local minima when the strict saddle point property is assumed.