# The Prediction Performance Analysis of the Lasso Model with Convex Non-Convex Sparse Regularization
## 3 Lasso with CNC Sparse Regularization
### ADMM Algorithm  
In this subsection, we will consider using the ADMM algorithm to solve the Lasso model with GMC regularization (14). [PERSON] et al. introduced a generalized ADMM framework for addressing sparse optimization problems [42]. The basic idea is to transform unconstrained optimization problems into constrained ones by splitting variables and then iteratively solve them. ADMM proves to be particularly efficient when the sparse regularization term possesses a closed-form proximal operator. The main challenge in solving (14) by ADMM lies in how to obtain the proximal operator of the GMC regularization. The augmented Lagrange form of (14) can be written as follows by setting \(z=\beta\). \[L(\beta,z,u)=\frac{1}{2n}\|y-X\beta\|_{2}^{2}+\lambda\Psi_{B}^{GMC}(z)+u^{\top} (z-\beta)+\frac{\rho}{2}\|z-\beta\|_{2}^{2}, \tag{21}\]  
where \(u\) represents the Lagrange multiplier and \(\rho>0\) denotes the penalty parameter. We then update \(\beta,z\) and \(u\) in an alternating manner. Step 1. Update \(\beta^{k+1}:\)  
\[\beta^{k+1}=\arg\min_{\beta}\left\{\frac{1}{2n}\|y-X\beta\|_{2}^{2}-(u^{k})^{ \top}\beta+\frac{\rho}{2}\|z^{k}-\beta\|_{2}^{2}\right\}. \tag{22}\]  
The objective function in Equation (22) is differentiable with respect to \(\beta\). As a result, \(\beta^{k+1}\) can be obtained by utilizing the first-order optimality condition  
\[\beta^{k+1}=(\frac{1}{n}X^{\top}X+\rho I)^{-1}(y^{\top}X+u^{k}+\rho z^{k}). \tag{23}\]  
Step 2. Update \(z^{k+1}:\)  
\[z^{k+1} =\arg\min_{z^{k}}\left\{\lambda\Psi_{B}^{GMC}(z^{k})+(u^{k})^{ \top}z^{k}+\frac{\rho}{2}\|z^{k}-\beta^{k+1}\|_{2}^{2}\right\}\] \[=\arg\min_{z^{k}}\left\{\lambda\Psi_{B}^{GMC}(z^{k})+\frac{\rho}{ 2}\|z^{k}-\beta^{k+1}+\frac{u^{k}}{\rho}\|_{2}^{2}\right\}. \tag{24}\]  
Equation (24) serves as the proximal operator for \(\Psi_{B}^{GMC}(z)\), although it lacks a closed-form solution. Despite this limitation, the PGD algorithm can be employed to iteratively address Equation (24). The substitution of \(\Psi_{B}^{GMC}(\beta)\) with (7) allows us to reformulate Equation (24) as  
\[z^{k+1}=\arg\min_{z^{k}}\left\{\lambda\|z^{k}\|_{1}-\lambda\min_{v}\{\|v\|_{1 }+\frac{1}{2}\|B(z^{k}-v)\|_{2}^{2}\}+\frac{\rho}{2}\|z^{k}-\beta^{k+1}+\frac {u^{k}}{\rho}\|_{2}^{2}\right\}. \tag{25}\]  
Let \(f(z^{k})=\frac{\rho}{2}\|z^{k}-(\beta^{k+1}-\frac{u^{k}}{\rho})\|_{2}^{2}- \lambda\min_{v}\{\|v\|_{1}+\frac{1}{2}\|B(z^{k}-v)\|_{2}^{2}\) and \(g(z^{k})=\lambda\|z^{k}\|_{1}\). The update of \(z^{k+1}\) of (25) can be obtained through PGD algorithm as follows:  
\[z^{k+1} =\text{prox}_{ag}(z^{k}-\alpha\
abla f(z^{k}))\] \[=\text{prox}_{ak\lambda\|_{1}}(z^{k}-\alpha\
abla f(z^{k})), \tag{26}\]where \(\alpha\) is the iteration step size. The main challenge of (26) is solving the gradient \(\
abla f(z^{k})\). According to Lemma 3 in [24], the last term of \(f(z^{k})\) is a differentiable with respect to \(z^{k}\). Furthermore, the gradient of \(f(z^{k})\) can be expressed as  
\[\
abla f(z^{k})=\rho(z^{k}-\beta^{k+1}+\frac{u^{k}}{\rho})-\lambda\bigg{(}B^{ \top}B(z^{k}-\arg\min_{v}\{\frac{1}{2}\|B(z^{k}-v)\|_{2}^{2}+\|v\|_{1}\})\bigg{)}. \tag{27}\]  
Note that (27) contains an \(\ell_{1}\)-regularization problem \(v^{k+1}=\arg\min_{v}\{\frac{1}{2}\|B(z-v)\|_{2}^{2}+\|v\|_{1}\}\), which can be viewed as a proximal operator associated with the \(\|\cdot\|_{1}\), i.e.,  
\[v^{k+1}=\mathrm{prox}_{\|\cdot\|_{1}}(v^{k}+B(z^{k}-v^{k})), \tag{28}\]  
where \(\mathrm{prox}_{\|\cdot\|_{1}}\) can be easily addressed by employing the soft-thresholding function (13). Then, by substituting (28) and (27) to (26) and sorting them out, the update of \(z^{k+1}\) can be summarized as follows  
\[\left\{ \begin{array}{ll}v^{k+1}=&\mathrm{prox}_{\|\cdot\|_{1}}(v^{k}+B(z^{k} -v^{k})),\\ s^{k+1}=&(1-\alpha\rho+\alpha\lambda B^{\top}B)z^{k}+\alpha\rho\delta^{k+1}- \alpha u^{k}-\alpha\lambda B^{\top}Bv^{k+1},\\ z^{k+1}=&\mathrm{prox}_{\alpha\|\cdot\|_{1}}(s^{k+1}).\end{array} \right.