How important is to formulate a convex optimization for a proposed algorithm?

Question

I proposed a new sparse coding algorithm which has good results compared to the baselines, however, it has a non-convex optimization framework. I solved the problem using a general solver (e.g. Matlab), and although the solution is local optimum, it is still better than other relevant approaches. So how important is to formulate the problem in a convex setting? especially for publishing the work.

Answer 1

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.