# The Prediction Performance Analysis of the Lasso Model with Convex Non-Convex Sparse Regularization
## 2 Preliminaries and Related Works
### Results of the Predicted Performance  
The prediction performance of the Lasso \(\ell_{n}(\hat{\beta},\beta^{*})=\frac{1}{n}\|X(\hat{\beta}-\beta^{*})\|_{2}^{2}\) refers to how well the Lasso model predicts outcomes or responses based on input features and depends on its ability to strike a balance between regularization and feature selection.  
In particular, [PERSON] et al. derive sparsity oracle inequalities pertaining to the prediction loss and highlight their implications for minimax estimation within the traditional nonparametric regression framework [35; 36; 37]. These inequalities enable us to establish bounds on the discrepancy between the prediction errors and the optimal sparse approximation, as determined by an oracle with full knowledge but constrained by sparsity. However, these results assumes a strict condition on the Gram matrix \(\frac{1}{n}X^{\top}X\), requiring it to be positive definite or subject to mutually coherent constraints. [PERSON] et al. proposed a more general oracle inequality by constraining the eigenvalues of the Gram matrix [38], but the inequality is not sharp because the constant in front of its infimum (usually referred to as the dominant constant of the oracle inequality) is not equal to 1 [12; 39]. Subsequently, [PERSON] et al. obtained the first sharp oracle inequality by constraining the diagonal elements of the Gram matrix to be no larger than 1. [PERSON] et al. improved the predictive performance of the Lasso model by utilizing the scaling effect and further relaxing the constraints on the covariate matrix \(X\)[40]. [PERSON] et al. present novel findings regarding the predictive accuracy of the Lasso model, even when minimal assumptions are made about the relationship between the covariates [12]. More specifically, we give the definition of the compatibility factor as follows:  
**Definition 1** (Compatibility factor).: _The compatibility factor \(\kappa_{T}\) of a set \(T\subseteq\{1,2,\ldots,p\}\) is defined as \(\kappa_{\emptyset}=1\), and for any nonempty set \(T\),_  
\[\kappa_{T}=\inf_{\beta}\frac{\sqrt{|T|}\cdot\|X\beta\|_{2}^{2}}{\sqrt{n}\| \beta\|_{1}}. \tag{8}\]  
The basic error bound of \(\ell_{1}\) Lasso minimizer in [12] can be rewritten as Theorem 1.  
**Theorem 1** ([12], Theorem 2).: _Let \(\delta\in(0,1)\) be a fixed tolerance level and \(\gamma>1\). For (2), let \(\hat{\beta}\) be a stationary point. Set the regularization parameter as \(\lambda=\gamma\sigma^{*}\sqrt{\frac{2\log(p/\delta)}{n}}\) then_  
\[\ell_{n}(\hat{\beta},\beta^{*})\leq\inf_{\beta\in\mathbb{R}^{p},T\subset p} \bigg{\{}\ell_{n}(\hat{\beta},\beta^{*})+4\|\hat{p}_{T}\|_{1}\bigg{\}}+\frac{ \sigma^{*2}}{n}\bigg{(}|T|+2\log(\frac{1}{\delta})+\frac{8\gamma^{2}\log(p/ \delta)}{\kappa_{T}^{2}}\bigg{)}, \tag{9}\]  
_on the estimation error with probability at least \(1-2\delta\) for any \(T\subset(1,2,\cdots,p)\)._  
The result obtained from Theorem 1 differs slightly from the one given in [12]; however, it can be easily derived from the proof provided in [12]. The proof of Theorem 1 is provided in the Appendix A.1.