# The Prediction Performance Analysis of the Lasso Model with Convex Non-Convex Sparse Regularization
## 3 Lasso with CNC Sparse Regularization
### Prediction Performance  
In this subsection, we analyze the prediction performance of the Lasso model with GMC regularization (14) and use the oracle inequality to obtain an upper bound on the prediction performance that is better than the upper bound of Lasso model with \(\ell_{1}\) regularization. We consider a general Lasso model with GMC regularization (14), that is, the GMC regularization term is non-convex and does not necessarily satisfy the convexity condition given by Theorem 2. Due to the non-convexity, it is possible that the global minimum of the proposed Lasso model cannot be achieved. Hence, it becomes crucial to find a stable point that satisfies the conditions. We define \(\hat{\beta}\in\mathbb{R}^{p}\) as a stationary point of \(F^{GMC}_{B}(\beta)\) when it fulfills\[0\in\
abla_{\beta}F_{B}^{CMC}(\beta)|_{\beta=\hat{\beta}}.\]  
Based on Definition 1, the compatibility factor enables us to establish a subsequent oracle inequality, which is applicable to the stationary points of the Lasso estimator with GMC regularization. **Theorem 3** (Oracle inequality of the Lasso model with GMC regularization). : _Assume \(\mu<\frac{1}{n\|X^{\dagger}\|_{2}^{2}}\). Let \(\delta\in(0,1)\) be a fixed tolerance level and \(\gamma>1\). Let \(\hat{\beta}\) be a stationary point of (14) and \(\sigma_{min}\) is the smallest eigenvalue of \(B^{\top}B\). Set the regularization parameter as \(\lambda=\gamma\sigma^{*}\sqrt{\frac{2\log(p/\delta)}{n}}\); then, the estimation error satisfies_  
\[\ell_{n}(\hat{\beta},\beta^{*}) \leq\inf_{\hat{\beta}\in\mathbb{R}^{p},T\subset P}\bigg{\{}\ell_ {n}(\bar{\beta},\beta^{*})+4\Psi_{\sqrt{\sigma_{min}}}^{GMC}((\bar{\beta})_{T ^{\top}})\bigg{\}}\] \[+\frac{2\sigma^{*2}}{n(1-n\mu\|X^{\dagger}\|_{2}^{2})}\bigg{(}|T| +2\log(1/\delta)+\frac{8\gamma^{2}\log(p/\delta)|T|}{\kappa_{T}^{2}}\bigg{)}, \tag{17}\]  
_with probability at least \(1-2\delta\) for any \(T\subseteq(1,2,\cdots,p)\)._  
The proof of Theorem 3 is given in the Appendix A.3. The oracle inequality holds for any \(\hat{\beta}\) that meets the first-order optimality condition, regardless of whether the regularization is non-convex. This mild condition imposed on \(\hat{\beta}\) represents a significant divergence from previous findings, such as Theorem 2 of [12], which is suitable for global minimization but challenging to ensure when employing non-convex regularizations. Theorem 3 enables the optimization of the error bounds on the right-hand side of (17) by allowing the selection of suitable values for \(\tilde{\beta}\) and \(T\). For instance, choose \(\tilde{\beta}=\beta^{*}\) in (17) (hence an 'oracle'), then \(\ell_{n}(\tilde{\beta},\beta^{*})=0\); therefore, the (17) can be rewritten as  
\[\ell_{n}(\hat{\beta},\beta^{*})\leq 4\Psi_{\sqrt{\sigma_{min}}}^{GMC} \big{(}(\beta^{*})_{T^{\top}}\big{)}+\frac{2\sigma^{*2}}{n(1-n\mu\|X^{\dagger} \|_{2}^{2})}\bigg{(}|T|+2\log(1/\delta)+\frac{8\gamma^{2}\log(p/\delta)|T|}{ \kappa_{T}^{2}}\bigg{)}. \tag{18}\]  
Furthermore, if \(T\) is set as the empty set, then  
\[\ell_{n}(\hat{\beta},\beta^{*})\leq 4\Psi_{\sqrt{\sigma_{min}}}^{GMC}(\beta^{* })+\frac{4\log(1/\delta)\sigma^{*2}}{n(1-n\mu\|X^{\dagger}\|_{2}^{2})}. \tag{19}\]  
In contrast, if \(T\) is set as the support of \(\beta\), then  
\[\ell_{n}(\hat{\beta},\beta^{*})\leq\frac{2\sigma^{*2}}{n(1-n\mu\|X^{\dagger} \|_{2}^{2})}\bigg{(}\|\beta\|_{0}+2\log(1/\delta)+\frac{8\gamma^{2}\log(p/ \delta)\|\beta\|_{0}}{\kappa_{T}^{2}}\bigg{)}, \tag{20}\]  
which increases linearly with the sparsity level \(\|\beta\|_{0}\). We compare the prediction error bounds of Theorem 3 with Theorem 1, which is obtained for a Lasso model with the \(\ell_{1}\) regularization. We note that the upper bounds of terms within the lower bound in inequality (17) are limited by the upper bounds of terms within the lower bound in Theorem 1. When \(\beta\) contains larger coefficients, non-convex regularization leads to more stringent bound, hence \(\Psi_{\sqrt{\sigma_{min}}}^{GMC}(\tilde{\beta})\ll\|\tilde{\beta}\|_{1}\).