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? 
 A: 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.
