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?

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