3
$\begingroup$

This is the sparse coding optimization function:

$$\arg\min_{B, \alpha} \sum_j \| \bf{x}_j - B\bf{\alpha}_j \|_2^2 + \lambda\sum_j |\bf{\alpha}_j|_1$$

I read in the literature that this function is not convex. How can I determine whether this function is convex or not?

$\endgroup$

2 Answers 2

9
$\begingroup$

Yes, this particular function is definitely nonconvex. For me, the dead giveaway is the product $B\alpha_j$, which is itself nonconvex, and the further squaring of these terms in the first summation. (Consider the function $f(x,y)=xy$, for instance, with no sign restrictions on either variable; and then consider $g(x,y)=(1-xy)^2$.)

Convexity is the exception, not the the rule. If you encounter a function at random and it is not obviously convex, it would be a reasonable guess to say that it is not.

What is more, in practice, convexity is far less useful to you if you don't know for sure that it's there. Sure, if you have a smooth function with uncertain convexity, you can throw a descent method at it; and if it happens to be convex, any solution it finds will be global---but good luck proving that without an appeal to convexity. Furthermore, many genuinely useful convex functions are not smooth anyway. And modern convex optimization algorithms rely on convexity in such a fundamental way that models not known to be convex cannot be "shoehorned" into them. Thus in practice, a function that "might" be convex must usually be treated as if it is not.

Now: how do you prove convexity or nonconvexity? There are a variety of ways. For instance, when a function is twice differentiable, you can examine the Hessian. If you can prove that it is positive semidefinite over its entire domain (edit: and that domain is a convex set), then the function is convex; if you can prove that it is not positive semidefinite at even a single point, then it is not convex.

Alas, in this case, the second summation adds a nonsmooth component to your problem, so a true derivative test will not work. Another common approach is to use combination rules: prove that your function can be built up from convex and concave building blocks using operations known to preserve convexity. One simple example: the sum of convex functions is convex. Now, the second summation above is convex, so if you could prove that the first term is convex, you'd be done. (Of course, you can't in this case.)

A full treatment on how to prove and disprove convexity is beyond my patience to offer here. Instead I will refer you to Boyd & Vandenberghe's seminal text, Convex Optimization. The most important section will be Chapter 3, but you'll need to digest first two chapters well to really get the most out of it.

One more thing: proving nonconvexity is often a lot easier than proving convexity. After all, you need only provide a single counterexample---even just two points in the function's domain, and the midpoint between them---that violate the basic definition of convexity. In contrast, proving convexity requires proving that it is true over the entire domain of the function.

$\endgroup$
2
$\begingroup$

Typically that problem is not solved by optimization in one step. Normally you hold the matrix $\bf B$ constant and then optimize for the $\alpha_j$ given a particular training example $\bf x$, which is a convex problem. Then once you have the activation vector you can optimize for the basis weights $\bf B$, which is normally done using gradient descent over a training set. The optimization for $\alpha_j$ is the inner loop for each training example.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .