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

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).

• 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}$$?

• The KKT conditions are a fundamental technique of constrained optimization. A good place to learn about them would be an optimization textbook or a comprehensive numerical analysis textbook. They are a more precise statement of the Lagrange multiplier conditions for multiple inequalities and equalities.
– whuber
Oct 24, 2023 at 17:57
• This comment is regarding your second bullet. These screening rules are not about changing the output of the optimization; rather, they are about identifying coefficients which are definitely going to be $0$, and thus whose updates can be skipped, speeding up the overall procedure. Oct 24, 2023 at 22:18