What exactly is the KKT check and what is the point of it?

Question

In the paper for strong screening rules for the lasso (link), the following screening algorithm is proposed (start of chapter 7):

Let $S(\lambda)$ be the strong rule set. Then the following strategy is adopted:

1. Set $\mathcal{E} = S(\lambda)$.
2. Solve the problem at value $\lambda$ using only the predictors in $\mathcal{E}$.
3. Check the KKT conditions at this solution for all predictors. If there are no violations, we are done. Otherwise, add the predictors that violate the KKT conditions to the set $\mathcal{E}$, and repeat steps (2) and (3).

I have a few questions about this:

• What exactly is the KKT check? I can see the KKT condition is given by $$ \mathbf{x}_j^T(\mathbf{y}-\mathbf{X} \hat{\boldsymbol{\beta}})=\lambda \gamma_j \quad \text { for } j=1, \ldots p $$ where $\gamma_j$ is the $j$ th component of the subgradient of $\|\hat{\boldsymbol{\beta}}\|_1$ : $$ \gamma_j \in \begin{cases}\{+1\} & \text { if } \hat{\beta}_j>0 \\ \{-1\} & \text { if } \hat{\beta}_j<0 \\ {[-1,1]} & \text { if } \hat{\beta}_j=0\end{cases} $$ Does this mean that for each predictor I need to check whether this is met? For example, if I have a variable such that $\hat{\beta}_i = 0$ from step (2), do I need to check that the KKT is satisfied with the last subgradient case? How can I check this for all predictors when I only have $\hat{\beta}$ values for those in $\mathcal{E}$?

• For step (3), what happens if the KKT violation occurs only for a single variable in $\mathcal{E}$? Surely then I am repeating the steps but $\mathcal{E}$ has stayed the same, so we would not expect a different output? Following this reasoning, why do we even need to check the KKT condition for variables in $\mathcal{E}$?

Answer 1

The KKT condition is automatically satisfied for predictors in the active set as a result of step 2, so you only need to check it for predictors that aren't in the active set.