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

DOI10.1007/S10898-020-00955-3zbMATH Open1465.90097arXiv1708.07010OpenAlexW3092255678MaRDI QIDQ2022292FDOQ2022292

Kaiwen Meng, Xiao Qi Yang, Yaohua Hu, C. Li

Publication date: 28 April 2021

Published in: Journal of Global Optimization (Search for Journal in Brave)

Abstract: The $el{l}_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 $el{l}_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 $el{l}_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.

Full work available at URL: https://arxiv.org/abs/1708.07010

zbMATH Keywords

sparse optimizationdescent methodslinear convergencenonconvex regularizationinexact approachproximal gradient algorithms

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Nonlinear programming (90C30)

Cites Work

• Title not available (Why is that?)
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• iPiano: inertial proximal algorithm for nonconvex optimization
• Analysis of multi-stage convex relaxation for sparse regularization
• Variational Analysis
• A unified convergence analysis of block successive minimization methods for nonsmooth optimization
• Gradient methods for minimizing composite functions
• Structured sparsity through convex optimization
• Decoding by Linear Programming
• A coordinate gradient descent method for nonsmooth separable minimization
• Sparse and Redundant Representations
• Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning
• Compressed sensing
• Smoothing methods for nonsmooth, nonconvex minimization
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• Signal Recovery by Proximal Forward-Backward Splitting
• A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion
• Lower Bound Theory of Nonzero Entries in Solutions of $\ell_2$-$\ell_p$ Minimization
• Alternating Direction Algorithms for $\ell_1$-Problems in Compressive Sensing
• Monotone Operators and the Proximal Point Algorithm
• An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
• Approximation accuracy, gradient methods, and error bound for structured convex optimization
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• An Unconstrained $\ell_q$ Minimization with $0q\leq1$ for Sparse Solution of Underdetermined Linear Systems
• Restricted isometry properties and nonconvex compressive sensing
• Sparse Approximation via Penalty Decomposition Methods
• A note on the complexity of \(L _{p }\) minimization
• Iterative thresholding for sparse approximations
• Mathematical Programs with Equilibrium Constraints
• Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates
• Description of the minimizers of least squares regularized with \(\ell_0\)-norm. Uniqueness of the global minimizer
• A new linear convergence result for the iterative soft thresholding algorithm
• Minimization of non-smooth, non-convex functionals by iterative thresholding
• An inexact successive quadratic approximation method for L-1 regularized optimization
• Abstract Convexity and Augmented Lagrangians
• A Unified Augmented Lagrangian Approach to Duality and Exact Penalization
• Linear convergence of iterative soft-thresholding
• On the linear convergence of a proximal gradient method for a class of nonsmooth convex minimization problems
• A proximal-gradient homotopy method for the sparse least-squares problem
• Proximal Newton-Type Methods for Minimizing Composite Functions
• Proximal Point Algorithms on Hadamard Manifolds: Linear Convergence and Finite Termination
• From error bounds to the complexity of first-order descent methods for convex functions
• Global Convergence of Splitting Methods for Nonconvex Composite Optimization
• Group sparse optimization via $\ell_{p,q}$ regularization
• $ \newcommand{\e}{{\rm e}} \ell_{0}$ -minimization methods for image restoration problems based on wavelet frames
• \(\ell _p\) regularized low-rank approximation via iterative reweighted singular value minimization
• On convergence rates of linearized proximal algorithms for convex composite optimization with applications
• Linear convergence of CQ algorithms and applications in gene regulatory network inference
• Linear Convergence of Proximal Gradient Algorithm with Extrapolation for a Class of Nonconvex Nonsmooth Minimization Problems
• Local Linear Convergence of ISTA and FISTA on the LASSO Problem
• Sparse Regularization: Convergence Of Iterative Jumping Thresholding Algorithm
• Iterative positive thresholding algorithm for non-negative sparse optimization
• On ${l}_{q}$ Optimization and Sparse Inverse Covariance Selection

Cited In (8)

• The level-set subdifferential error bound via Moreau envelopes
• An extrapolated iteratively reweighted \(\ell_1\) method with complexity analysis
• Joint sparse optimization: lower-order regularization method and application in cell fate conversion
• A Regularized Newton Method for \({\boldsymbol{\ell}}_{q}\) -Norm Composite Optimization Problems
• Convergence rate analysis of proximal iteratively reweighted \(\ell_1\) methods for \(\ell_p\) regularization problems
• The equivalence of three types of error bounds for weakly and approximately convex functions
• A Projection Proximal-Point Algorithm for ℓ¹Minimization
• A forward-backward algorithm with different inertial terms for structured non-convex minimization problems

Uses Software

• iPiano

This page was built for publication: Linear convergence of inexact descent method and inexact proximal gradient algorithms for lower-order regularization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2022292)