# Confusion related to convexity and concavity of a function

I was reading this paper http://www.ist.temple.edu/~vucetic/documents/wang11kdd.pdf related to adaptive multi-hyperplane machine for non linear classification

In that paper, they have mentioned about multiclass SVM, with multiple weights for each class.

The loss for any classification is

$l(x_n,y_n) = max_{i\epsilon y\\\y_n}(0,1 + max g(i,x_n) - g(y_n,x_n))$

where $y_n$ is the label for the nth example and $x_n$ is the features.

I have this confusion when they do the training of this algorithm. They call this SVM MM(Multiple Hyperplane).

They say the convex-approximated problem is defined as

$min_{W}P(W|z) = \frac{\lambda}{2}||W||^2 + \frac{1}{N}\sum_{n=1}^{N}l_{cvx}(W;(x_n,y_n);z_n)$

where they have the concave term $-g(y_n,z_n)$ replaced with the convex term $-w^T_{y_n,z_n}x_n$.

I am not sure if I have described it clearly. But I am going to attach the screenshot of the paper as well. The thing is I didn't get what's the difference between $-g(y_n,z_n)$ and $-w^T_{y_n,z_n}x_n$. They seem the same term to me.

I might be asking a lot. But can anyone provide some info?

I have marked by the red rectangle the part that I didn't understand. I might be asking a lot. But I didn't get that part. Why is it so?

Disclaimer: Most of my optimization-related work has been done in nonconvex optimization, and I have no training in Support Vector Machines (SVM) whatsoever.

Based on what I can tell from reading Wikipedia and my optimization background, my guess is that they chose to replace the original nonconvex objective with an upper bound to formulate a convex restriction to the original problem. The "loss term" looks like a penalty term designed to ensure that the normal vectors of the hyperplanes in this particular SVM are all distinct; replacing the nonconvex term with a greater convex term in the objective function of a minimization problem only increases the penalty assigned to normal vectors that are "too similar".

This modification was probably done to make the problem substantially easier to solve; convex optimization problems are solvable in polynomial time (as a function of the number of decision variables, constraints, and the number of bits it takes to store the inputs), whereas nonconvex optimization problems are not solvable in polynomial time, and typically have algorithms that are exponential run times (again, as a function of the number of decision variables, etc.). All of these exponential run time algorithms are sophisticated variants of guess-and-check, because that strategy is the best we can do in the absence of theoretical breakthroughs like $\mathcal{P} = \mathcal{NP}$.

• I didn't get it. They have mentioned that they replaced the concave term by the convex one. However, I didn't get how the term $-g(y_n,x_n)$ is concave and the term $-w^T_{y_n,z_n}x_n$ is convex and what is the difference between the two terms. They are same. I don't know what is the difference between them – user34790 Mar 10 '13 at 1:40
• Skimming the paper, I think that part of the confusion is that the authors use the symbol $g$ to refer to two different functions. Let the first definition of $g$ be $g_1(i, x) = w_{i}^{T}x$ and let the second definition of $g$ be $g_2(i, x) = \max_{j} w_{i,j}^{T}x$. It could be that the loss function in (3), which uses $g_1$, is nonconvex. Replacing $g_1$ in (3) with $g_2$ looks like it yields (7). (Similarly, replacing $g_1$ in (4) looks like it yields (8).) It could be that the confusion results from two different functions and bad notation, or the authors could have screwed up. – Geoff Oxberry Mar 10 '13 at 19:34
• I got all that. So that's my question. How come $g_1(i,x)$ is non convex and why is $g_2(i,x)$ is convex – user34790 Mar 10 '13 at 23:01
• I can tell you why they made the change, but I can't prove to you why the first is nonconvex without going into the literature, and I don't have time to do that. The reference they supply (reference 1) is supposed to show that (3) is nonconvex in $\mathbf{W}$. However, the notation in references 1 and 8, both of which purport to substantiate the authors' argument, is completely and totally different than the notation in the paper. Not being an expert in the field, I don't have time to parse all of that. I can answer the why, but for the "how", you need an expert in SVM. – Geoff Oxberry Mar 10 '13 at 23:14