.png){kind=icon}
.png){kind=icon}
Return
A Complexity Analysis Framework for Active Manifold Identification with Applications to L0 and Lp Regularization Models
.png){kind=icon}
PRE
AI
T
Z
DOI：10.1007/s00245-026-10410-6.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Many applications involve nonsmooth optimization problems that often exhibit a low-dimensional structure in their optimal solutions. The projection gradient method (PG), the alternating direction method of multipliers (ADMM), and the accelerated projection gradient method (APG) are particularly effective for solving nonconvex composite programming problems and are known to determine the optimal sparsity pattern after a finite number of iterations. However, the exact number of iterations required to identify the final sparsity pattern remains an open problem. In this work, we develop a novel analytical framework to characterize the complexity of determining the active manifold and provide a rigorous proof. Using this framework, we show that PG, ADMM, and APG satisfy the necessary assumptions, enabling us to characterize the complexity of identifying the final active manifold for composite programs with nonsmooth, nonconvex regularizers, such as the L0 and Lp norms, without requiring nondegeneracy conditions. Finally, we present numerical validation for the derived theoretical complexity bound.
Keywords:
Partly smooth
Active set
Nonsmooth analysis
Projection gradient method
Alternating direction method of multipliers
Accelerated projection gradient method
Journal
A
IF:
1.7
Papers:
106
Citations:
0
Organization
Cited Papers