L1-regularization enforces sparsity for convex functions

Question

I have a convex function $f \colon \mathbb{R}^n \to \mathbb{R}$ that I minimize using L1-regularization: $\DeclareMathOperator*{\argmin}{arg\,min}$ $$ x^*=\argmin_x f(x) + \lambda ||x||_1 $$

Can I assume that I achieve sparseness, i.e., that $x^* \in \mathbb{R}^n$ will have few non-zero entries? More explicitly, can I assume that $||x^*||_0 := |\{i \mid x_i \neq 0\}|$ is small?

Special Case: Lasso

The answer is well-known to be yes in the case of $f(x)=\frac{1}{N} \sum_{i=1}^N ||y-Xx||_2^2$ --- this is Lasso. But what about general convex function $f$?

My Thinking

Feel free to ignore the rest of the question if there is a better way to approach this.

Step 1: It seems reasonable to me that the following minimization problem yields few non-zero entries: $$ \argmin_{||x||_1\leq\delta} f(x) $$ The reasoning for this is standard (e.g., "The Elements ofStatistical Learning", Fig. 3.11). I am not fully sure if it really applies for general convex $f$, but it seems reasonable to think that it does, at least to "most" $f$ (any additional insight here is appreciated).

Step 2: My main concern with this approach is if indeed there is a $\delta$ (which depends on $\lambda$), such that:

$$ x^* \in \argmin_{||x||_1 \leq \delta} f(x) $$

How would I show this?

Answer 1

Regarding your question about general convex functions, you will get a sparse solution given that you apply a sparsity-inducing norm (which l1 is one such norm). For further information, read up to section 1.3 (including) here: https://hal.archives-ouvertes.fr/hal-00613125v1/document

In general (taken form the link):

If you have a convex optimization problem like: $$\min_{\omega \in > \mathbb{R}^p} f(\mathbf{\omega}) + \lambda \Omega(\mathbf{\omega})$$ Where $f:\mathbb{R}^p \rightarrow \mathbb{R}$ is a convex differentiable function and $\Omega:\mathbb{R}^p \rightarrow\mathbb{R}$ is a sparsity-inducing norm, you will get a sparse solution.

You can see it if you write the problem as a constrained problem: $$\min_{\omega \in \mathbb{R}^p} f(\mathbf{\omega}) \quad \textrm{such that} \quad \Omega(\mathbf{\omega}) \leq \mu, \\ \textrm{for some}\;\mu \in \mathbb{R}_{+}$$ At optimality, the gradient of $f$ evaluated at any solution $\hat{\mathbf{\omega}}$ of the above equation is known to belong to the normal cone $\mathcal{B} =\{{\mathbf{\omega} \in \mathbb{R}^p; \; \Omega(\mathbf{\omega}) \leq \mu\}}$. In other words, for sufficiently small values of $\mu$, i.e., so that the constraint is active, the level set of $f$ for the value $f(\hat{\mathbf{\omega}})$ is tangent to $\mathcal{B}$.

As a consequence, the geometry of the ball $\mathcal{B}$ is directly related to the properties of the solutions $\hat{\mathbf{\omega}}$. When $\Omega$ is the $l_1$-norm for example, $\mathcal{B}$ corresponds to a diamond-shaped pattern in two dimensions, and to a pyramid in three dimensions. In particular, $\mathcal{B}$ is anisotropic and exhibits some singular points due to the non-smoothness of $\Omega$. These singular points are located along the axis of $\mathbb{R}^p$, so that if the level set of $f$ happens to be tangent at one of these points, sparse solutions are obtained.

Francis Bach, Rodolphe Jenatton, Julien Mairal, Guillaume Obozinski. Optimization with SparsityInducing Penalties. 2011. ffhal-00613125v1

Answer 2

No, f(x) = (|x|-1)**2 is convex, and has an infinite number of zeros.