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

Question

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?

Answer 1

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.