5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Your framing of the question is exceptionally vague, because "$f(x)$" doesn't involve any "entries" whatsoever. To make progress you need to explain what these "entries" are and how $f$ depends on them. $\endgroup$ – whuber Nov 18 '19 at 22:30
  • $\begingroup$ @whuber i have clarified that $x \in \mathbb{R}^n$ contains $n$ entries, and what $x^*$ being spare means. I agree that the rest of the question is still vague (what does it mean for $||x^*||_0$ to be "small"?). But I have the same problem for the more standard Lasso. The part My Thinking tries to clarify a possible approach (as for as I know, this is roughly the approach Lasso is taking). $\endgroup$ – Peter Nov 18 '19 at 22:49
3
+50
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Could you post more information about the link, in case someday it breaks? If that happens, this answer is almost (but not quite) useless... $\endgroup$ – jbowman Nov 24 '19 at 19:26
  • $\begingroup$ This is a good reference. Along the lines of @jbowman's comment, please include a full citation so people can still find the paper if the link breaks. Also, since the last two paragraphs are copy/pasted from the paper, it would be best to use a block-quote to attribute these to the source. I know you wrote "from the link" near the top of the post, but I found it hard to distinguish which parts are from the paper, and which parts are your summary/commentary. $\endgroup$ – user20160 Nov 25 '19 at 15:59
-2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ It's unclear what your "no" means. Could you explain the relevance of this observation to the question? Given that "regularization" consists of exploring how the minima vary with $\lambda \ge 0,$ consider the minima of $(|x|-1)^2 + \lambda |x|_1$ for any $\lambda \gt 2:$ how many of them are there? $\endgroup$ – whuber Nov 19 '19 at 13:57
  • $\begingroup$ No: in this case the number of optimal values is not few, indeed not finite. For small lambda, there are two "rings" (L1 circles, which are actually square). whuber correctly points out that for large lambda there are no solutions - but using large lambda is not regularization. $\endgroup$ – chrishmorris Nov 20 '19 at 13:11

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.