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 solution. Numerical experiments confirm that for a sufficiently large system size, SCAD-AMP achieves the optimal performance predicted by the replica method. Through replica analysis, a phase transition between replica symmetric (RS) 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 L1-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.
Introduction
In high-dimensional statistics, sparse estimation aims to select a small number of significant variables from a large pool. While the Lasso ($\ell_1$ regularization) is widely used due to its convexity, it suffers from a "shrinkage bias," where the magnitudes of large coefficients are systematically underestimated. Nonconvex penalties, such as the Smoothly Clipped Absolute Deviation (SCAD), were introduced to address this by providing unbiasedness for large coefficients while maintaining sparsity and continuity.
However, the nonconvex nature of SCAD introduces a complex optimization landscape with potential local minima. This paper bridges the gap between statistical physics and high-dimensional statistics by proposing an efficient Approximate Message Passing (AMP) algorithm for SCAD and providing a theoretical framework to analyze its stability and performance.
Methods
The authors develop SCAD-AMP, a variant of Generalized Approximate Message Passing (GAMP) specifically designed for the SCAD penalty. The algorithm's performance is analyzed in the thermodynamic limit ($N, M \to \infty$ with fixed ratio $\alpha = M/N$) using the replica method from spin glass theory.
A key component of the AMP algorithm is the proximal operator (or thresholding function) associated with the penalty. As shown in Figure 4, the SCAD proximal operator (c) combines the benefits of hard thresholding (sparsity) and soft thresholding (continuity) while eliminating the bias for large values.
The stability of the algorithm is linked to the de Almeida–Thouless (AT) condition, which identifies the boundary between the Replica Symmetric (RS) phase—where the optimization landscape is smooth—and the Replica Symmetry Breaking (RSB) phase—where the landscape becomes "glassy" and trapped in local minima.
Results
Numerical experiments on synthetic Gaussian data demonstrate that SCAD-AMP matches the optimal performance predicted by the replica method for sufficiently large systems.
Key findings include:
- Superior Performance: In the stable RS region, SCAD achieves lower representation error and higher sparsity than Lasso.
- The "Edge of Chaos": The minimum representation error occurs precisely at the phase boundary between the RS and RSB regions.
- Optimization Limits: The failure of standard Coordinate Descent (CD) algorithms to reach the global minimum coincides with the RS/RSB transition, highlighting the fundamental nature of this phase boundary.
Conclusion
This work provides a rigorous theoretical foundation for using nonconvex penalties in high-dimensional linear regression. By identifying the RS/RSB phase transition, the authors offer a "map" for parameter selection that ensures both algorithmic stability and superior statistical performance. Future work will extend these findings from data representation to signal inference in noisy environments.
Summary updated