0
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – whuber
    Oct 24, 2023 at 17:57
  • $\begingroup$ 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. $\endgroup$ Oct 24, 2023 at 22:18

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Why does the algorithm state to check it for all predictors in step 3? $\endgroup$
    – Sparsity
    Oct 25, 2023 at 11:00
  • $\begingroup$ That's not really a statistics question $\endgroup$ Oct 25, 2023 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.