3
$\begingroup$

I was reading this paper which discusses nonconvex penalized regression. They use the following notation:

  • $X\in\mathbb{R}^{n\times p}$ is a data matrix with $n$ observations in $p$ variables
  • $\beta\in\mathbb{R}^p$ is a vector of regression parameters
  • $\eta=X\beta$ is the expected value of the output $y$

For logistic regression, the goal is to minimize the loss function (eq. (3.2)) $$ Q_{\lambda,\gamma}(\beta)=-\frac{1}{n}\sum_{i=1}^n\{y_i\log\pi_i+(1-y_i)\log(1-\pi_i)\} + \sum_{j=1}^p p_{\lambda,\gamma}(|\beta_j|), $$ where:

  • $p_{\lambda,\gamma}$ is a regularizer/penalty function controlled by parameters $\lambda$ and $\gamma$,
  • $\pi_i=e^{\eta_i}/(1+e^{\eta_i})$.

On page 13, subsection 4.2 it is written about $Q_{\lambda,\gamma}(\beta)$:

Local convexity diagnostics. However, it is not always necessary to attain global convexity. In high-dimensional settings where $p>n$, global convexity is neither possible nor relevant.

In other words, the number of predictors $p$ is bigger than the number of observations $n$. Why is global convexity not possible in higher dimensions?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Could you maybe expand your question a bit, like explaining what $p$ and $n$ mean, so that it is understandable stand-alone, without having to read the referenced paper? $\endgroup$
    – Jan Kukacka
    Jun 7, 2018 at 12:36
  • 3
    $\begingroup$ The authors' statement about convexity pertains specifically to the loss function they are dealing with. Proposition 2 in the paper states that the loss function in question $Q_{\lambda,\gamma}(\beta)$ is convex only when $c^*(\beta)>1/\gamma$, where $c^*(\beta)$ is the minimum eigenvalue of $n^{-1}X^TWX$. You can show that for $p>n$, some of the eigenvalues (in fact, $p-n$ of them) will be zero, so the convexity condition cannot be satisfied. $\endgroup$
    – scherm
    Jun 7, 2018 at 13:51
  • 1
    $\begingroup$ @scherm - you might want to expand that to an answer, since it is. $\endgroup$
    – jbowman
    Jun 7, 2018 at 14:33
  • $\begingroup$ @jbowman that was the plan, but the question was put on hold while I was formulating my answer :) $\endgroup$
    – scherm
    Jun 7, 2018 at 14:42
  • $\begingroup$ OP, please check that @scherms edits match your intent. Furthermore, please add a full reference in addition to the link $\endgroup$
    – Juho Kokkala
    Jun 7, 2018 at 17:08

1 Answer 1

Reset to default
2
$\begingroup$

The paper covers two choices for $p_{\lambda,\gamma}$: MCP and SCAD. Proposition 2 states:

Let $c^*(\beta)$ denote the minimum eigenvalue of $n^{-1}X^TWX$, where $W$ is evaluated at $\beta$. Then the objective function defined in (3.2) is a convex function of $\beta$ on the region where $c^*(\beta) > 1/\gamma$ for MCP, and where $c^*(\beta) > 1/(γ − 1)$ for SCAD.

where $W=\operatorname{diag}(\pi\odot(1-\pi))$ with $\odot$ signifying elementwise multiplication. I will deal with MCP here, but the argument for SCAD is the same.

Notice that $n^{-1}X^TWX$ has $p$ eigenvalues since it is $p\times p$, but if $p>n$, at most $n$ of them will be nonzero since $\operatorname{rank}(n^{-1}X^TWX)\leq\min(n,p)$. This leaves at least $p-n$ zero eigenvalues. Since $Q_{\lambda,\gamma}$ is convex only where $c^*(\beta) > 1/\gamma$ (but we have $c^*(\beta)=0 < 1/\gamma$), it is not convex.

On the other hand, if $p\leq n$, we should be safe because $n^{-1}X^TWX$ is likely full-rank and for the proper setting of $\gamma$, we can satisfy the convexity condition.

Improve this answer
$\endgroup$

Your Answer

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

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