Interestingly, the new objective remains convex, but the margin constraint doesn't as it involves a multiplicative term between the weight vector and the embedding matrix, making the overall problem bi-convex (Gorski et al., 2007).
the problem is convex in w for fixed values of Φ and convex in Φ for fixed values of w. Incidentally, the formulation presented by (Labutov and Lipson, 2013) is also bi-convex (as it also involves a similar multiplicative term), although the authors proceed as if it were jointly convex (i.e., convex in both w and Φ).