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?

  • 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$ Jun 7 '18 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 '18 at 13:51
  • 1
    $\begingroup$ @scherm - you might want to expand that to an answer, since it is. $\endgroup$
    – jbowman
    Jun 7 '18 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 '18 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$ Jun 7 '18 at 17:08

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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