How important is to formulate a convex optimization for a proposed algorithm?
I don't know whether any of us can predict how reviewers or your community will react, especially without seeing the manuscript; probably your best bet is to talk to your advisor or to collaborators or colleagues and ask them for their advice.  You might also ask them if they'd read a draft of your paper.

My expectation is that it might depend on whether your field values provable results ("theory"), or pragmatic empirical results ("engineering").  The benefit of a convex formulation is that it allows proving some theorems about the approach, e.g., that it will always find the optimum under certain conditions.  The benefit of your approach is that it seems to get better results in practice, at least on the workloads you've been testing it on.  I can't tell you which your community will value more highly.