Paper Info
Title
Approximate message passing for nonconvex sparse regularization with stability and asymptotic analysis.
Abstract
We analyse a linear regression problem with nonconvex regularization called smoothly clipped absolute deviation (SCAD) under an overcomplete Gaussian basis for Gaussian random data. We propose an approximate message passing (AMP) algorithm considering nonconvex regularization, namely SCAD-AMP, and analytically show that the stability condition corresponds to the de Almeida-Thouless condition in spin glass literature. Through asymptotic analysis, we show the correspondence between the density evolution of SCAD-AMP and the replica symmetric (RS) solution. Numerical experiments confirm that for a su. ciently large system size, SCAD-AMP achieves the optimal performance predicted by the replica method. Through replica analysis, a phase transition between replica symmetric and replica symmetry breaking (RSB) region is found in the parameter space of SCAD. The appearance of the RS region for a nonconvex penalty is a significant advantage that indicates the region of smooth landscape of the optimization problem. Furthermore, we analytically show that the statistical representation performance of the SCAD penalty is better than that of l(1)-based methods, and the minimum representation error under RS assumption is obtained at the edge of the RS/RSB phase. The correspondence between the convergence of the existing coordinate descent algorithm and RS/RSB transition is also indicated.
Year
DOI
Venue
2017
10.1088/1742-5468/aab051
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT
Keywords
Field
DocType
message-passing algorithms,analysis of algorithms,learning theory
Convergence (routing),Applied mathematics,Replica,Discrete mathematics,Quantum mechanics,Analysis of algorithms,Gaussian,Regularization (mathematics),Coordinate descent,Asymptotic analysis,Optimization problem,Mathematics
Journal
Volume
ISSN
Citations 
abs/1711.02795
1742-5468
1
PageRank 
References 
Authors
0.63
0
2
Name
Order
Citations
PageRank
Ayaka Sakata1243.93
Yingying Xu211.98