Avoiding strict saddle points of nonconvex regularized problems

2024/01/17 by Bai, Luwei, Hu, Yaohua, Wang, Hao +1 · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2401.09274

Abstract

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 ℓ₁ algorithm (DIRL₁) and the iteratively reweighted ℓ₂ (DIRL₂) algorithm, to solve these problems. For DIRL₁, we show the reweighted ℓ₁ subproblem has support identification property so that DIRL₁ locally reverts to a gradient descent algorithm around a stationary point. For DIRL₂, we show the solution map of the reweighted ℓ₂ subproblem is differentiable and Lipschitz continuous everywhere. Therefore, the map of DIRL₁ and DIRL₂ 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.

Cited by

• Nonconvex Optimization Framework for Group-Sparse Feedback Linear-Quadratic Optimal Control: Non-Penalty Approach

Related

• Nonconvex and Nonsmooth Sparse Optimization via Adaptively Iterative Reweighted Methods
• Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity
• Alternating Iteratively Reweighted ℓ₁ and Subspace Newton Algorithms for Nonconvex Sparse Optimization
• Iterative Reweighted Minimization Methods for l_p Regularized Unconstrained Nonlinear Programming
• Minimization Over the Nonconvex Sparsity Constraint Using A Hybrid First-order method