Linear convergence of inexact descent method and inexact proximal gradient algorithms for lower-order regularization problems

2017/08/23 by Yaohua Hu, Hu, Yaohua, Chong Li +5
Computer Science · Engineering · Mathematics · #65J22 #65K05 #FOS: Mathematics #Numerical methods in inverse problems #Optimization and Control (math.OC) #Optimization and Variational Analysis #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1708.07010

openalex publication_date 2017/08/23 · openalex created_date 2017/08/31 · openalex updated_date 2026/07/28

Abstract

The ℓ_p regularization problem with 0< p< 1 has been widely studied for finding sparse solutions of linear inverse problems and gained successful applications in various mathematics and applied science fields. The proximal gradient algorithm is one of the most popular algorithms for solving the ℓ_p regularisation problem. In the present paper, we investigate the linear convergence issue of one inexact descent method and two inexact proximal gradient algorithms (PGA). For this purpose, an optimality condition theorem is explored to provide the equivalences among a local minimum, second-order optimality condition and second-order growth property of the ℓ_p regularization problem. By virtue of the second-order optimality condition and second-order growth property, we establish the linear convergence properties of the inexact descent method and inexact PGAs under some simple assumptions. Both linear convergence to a local minimal value and linear convergence to a local minimum are provided. Finally, the linear convergence results of the inexact numerical methods are extended to the infinite-dimensional Hilbert spaces.

Citations

• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods
• A Sparse-Group Lasso
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality

Related

• Convergence Rate Analysis of Proximal Iteratively Reweighted ℓ₁ Methods for ℓ_p Regularization Problems
• On the order optimality of the regularization via inexact Newton iterations
• On the complexity of proximal gradient and proximal Newton-CG methods for \(ℓ₁\)-regularized Optimization
• The Smoothing Proximal Gradient Algorithm with Extrapolation for the Relaxation of l₀ Regularization Problem
• Optimal Convergence Rates Results for Linear Inverse Problems in Hilbert Spaces