Sparsity is created by a nonsmooth geometry: the \(\ell_1\) ball has corners on coordinate subspaces, and its subdifferential contains intervals at zero. The same KKT equations drive optimization, screening, and statistical support-recovery arguments.
Lasso optimality coordinate by coordinate
For a differentiable convex loss \(\ell\), consider \[ \widehat\beta\in\operatorname*{arg\,min}_{\beta\in\mathbb R^p} \{\ell(\beta)+\lambda\|\beta\|_1\}. \] The Fermat rule is \[ 0\in\nabla\ell(\widehat\beta)+\lambda\partial\|\widehat\beta\|_1. \]
Coordinatewise KKT conditions. A vector \(\widehat\beta\) is optimal if and only if \[ \begin{cases} \nabla_j\ell(\widehat\beta) =-\lambda\operatorname{sign}(\widehat\beta_j), &\widehat\beta_j\ne0,\\[3pt] |\nabla_j\ell(\widehat\beta)|\le\lambda, &\widehat\beta_j=0. \end{cases} \]
Proof. The subdifferential of \(|t|\) is \(\{\operatorname{sign}(t)\}\) for \(t\ne0\) and \([-1,1]\) at zero. Since the \(\ell_1\) norm is separable, its subdifferential is the Cartesian product of these coordinate sets. Substituting into the Fermat inclusion gives the two cases.
Inactive variables need not have zero loss gradient; the penalty can balance any gradient within \([-\lambda,\lambda]\). This interval is what permits exact zeros.
Soft thresholding from a scalar subproblem
Thresholding formula. For \(a>0\), the unique minimizer of \[ \frac a2t^2-bt+\lambda|t| \] is \[ t^\star=\frac1aS_\lambda(b),\qquad S_\lambda(b)=\operatorname{sign}(b)(|b|-\lambda)_+. \]
Proof. The optimality inclusion is \(0\in at-b+\lambda\partial|t|\). If \(t>0\), it gives \(t=(b-\lambda)/a\), valid when \(b>\lambda\). If \(t<0\), it gives \(t=(b+\lambda)/a\), valid when \(b<-\lambda\). At \(t=0\), it holds exactly when \(|b|\le\lambda\). Combining the cases yields the formula.
This scalar result is simultaneously the lasso coordinate update and the proximal map of \(\lambda|\cdot|\). Coordinate descent and proximal gradient therefore use the same local operation in different update geometries.
Structured sparsity through proximal maps
Group lasso. For a block \(v\in\mathbb R^m\), \[ \operatorname{prox}_{\tau\|\cdot\|_2}(v) =\left(1-\frac{\tau}{\|v\|_2}\right)_+v. \] Thus an entire group is set to zero when its Euclidean norm is below the threshold.
Nuclear norm. If \(Y=U\operatorname{diag}(\sigma_i)V^\top\), then \[ \operatorname{prox}_{\tau\|\cdot\|_*}(Y) =U\operatorname{diag}((\sigma_i-\tau)_+)V^\top. \] Singular-value thresholding is the matrix analogue of soft thresholding and promotes low rank.
Safe screening from a dual region
Suppose a computable duality gap confines a dual optimizer \(\theta^\star\) to a ball \(B(\theta_c,r)\). For least-squares lasso, the dual constraint is \(\|X^\top\theta^\star\|_\infty\le\lambda\). If \[ |X_j^\top\theta_c|+\|X_j\|r<\lambda, \] then \(|X_j^\top\theta^\star|<\lambda\), so complementary slackness forces \(\widehat\beta_j=0\). This is a safe screening rule: it removes a coordinate without changing the exact solution.
Optimization conditions alone do not guarantee correct variable selection. Statistical support recovery also requires signal strength and design conditions, developed in compatibility and irrepresentability. The KKT equation is the bridge between the computational and statistical arguments.