Why is global convexity not possible in higher-dimensional settings for this loss function?

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?

• 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? Jun 7 '18 at 12:36
• 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. Jun 7 '18 at 13:51
• @scherm - you might want to expand that to an answer, since it is. Jun 7 '18 at 14:33
• @jbowman that was the plan, but the question was put on hold while I was formulating my answer :) Jun 7 '18 at 14:42
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.