# The Prediction Performance Analysis of the Lasso Model with Convex Non-Convex Sparse Regularization
## 2 Preliminaries and Related Works
### Convex Non-Convex Sparse Regularization  
To address the limitation of \(\ell_{1}\) regularization, \(\ell_{q}(0<q<1)\) regularization has been proposed to enhance the accuracy of estimation. However, the utilization of \(\ell_{q}\) regularization renders the objective function in problem (2) non-convex and leads to suboptimal local solutions [18; 29; 30; 31].  
To leverage the benefits of non-convex regularization and convex optimization techniques, [PERSON] et al. introduced the CNC strategy, which constructs a non-convex sparse regularization but at the same time guarantees the global convexity of the objective function [20; 21; 22; 23; 24; 25].  
Common CNC sparse regularizations include logarithmic regularization [32], exponential regularization [33], arctangent regularization [32], minimax-convex (MC) regularization [21], etc. Formally, these regularizations can be represented by the class of additively separable functions  
\[\psi_{b}(\beta)=\sum_{i=1}^{p}\psi_{b}(\beta_{i}), \tag{4}\]where \(\psi_{b}:\mathbb{R}\rightarrow\mathbb{R}\) is a non-convex function parameterized by a scalar parameter \(b\), which controls the non-convexity of \(\psi_{b}\). Take the MC regularization as an example, for each \(\beta_{i}\), the \(\psi_{b}^{\text{MC}}(\beta_{i})\) can be expressed as  
\[\psi_{b}^{\text{MC}}(\beta_{i})=\begin{cases}|\beta_{i}|-\frac{b^{2}}{2},&|\beta _{i}|\leq\frac{1}{b^{2}},\\ \frac{1}{2b^{2}},&|\beta_{i}|\geq\frac{1}{b^{2}}.\end{cases} \tag{5}\]  
Mathematically, \(\psi_{b}^{\text{MC}}(\beta_{i})\) can also be written as  
\[\psi_{b}^{\text{MC}}(\beta_{i})=|\beta_{i}|-\min_{v}\bigg{\{}|v|+\frac{b^{2}}{ 2}(\beta_{i}-v)^{2}\bigg{\}}, \tag{6}\]  
where \(\min_{v}\{|v|+\frac{b^{2}}{2}(\beta_{i}-v)^{2}\}\) is the scalar Huber function with parameter \(b\). Noting that the scalar Huber function is a common smooth version of the \(\ell_{1}\) norm, the fundamental construction strategy for CNC involves subtracting its corresponding smooth version from the sparse regularization.  
As highlighted in [19; 24; 34], the separable (additive) CNC sparse regularizations mentioned above necessitate the full column rank of the covariate matrix \(X\) to ensure the global convexity of (3). However, in many important applications, the covariate matrix \(X\) is wide (\(p>n\)), then the CNC strategy with separable sparse regularizations cannot be used. This strongly motivated the development of non-separable sparse regularizations.  
Again, starting with MC sparse regularization, the non-separable generalized MC (GMC) regularization is defined as  
\[\Psi_{B}^{GMC}(\beta)=\|\beta\|_{1}-\min_{v}\bigg{\{}\|v\|_{1}+\frac{1}{2}\|B (\beta-v)\|_{2}^{2}\bigg{\}}, \tag{7}\]  
where \(B\in\mathbb{R}^{n\times p}\) is the non-convex control matrix parameter [19; 20; 21].  
The GMC regularization \(\Psi_{B}^{GMC}(\beta)\), in general, cannot be expressed in the separable form of (4) due to the arbitrariness of the matrix parameter \(B\). Specifically, if \(B^{\top}B\) is a diagonal matrix, i.e., \(B^{\top}B=(b_{1}^{2},b_{2}^{2},\cdots,b_{n}^{2})\), then \(\Psi_{B}^{GMC}(\beta)\) is separable, and if \(B=0\) the \(\Psi_{B}^{GMC}(\beta)\) reduces to the \(\ell_{1}\) norm. The key advantage of non-separable non-convex sparse regularization lies in its ability to ensure the global convexity of the objective function, even when the covariate matrix \(X\) is not full column rank. This feature is crucial as it enables the application of CNC sparse regularization to any linear image inverse problem.