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

Question

I proposed a new sparse coding algorithm which has goods 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

To give an answer to this question. It is true that a convex is desirable, but it is not a necessary condition for a method or algorithm to be successful or be publicable.

Non-convex problems are usually hard to treat. Slow convergence (if any) along with local minima and pathological cases are hard to avoid. However science still advance because in practice real world cases are not as pathological as may appear. If you can provide certain guarantees such as:

• Convergence for all valid input: characterize what is a valid input for which convergence is guarantee. Numerical method used is of paramaunt importance since convergence can be assured by numerical method.

• Characterization of solutions: what are the best and worst conditions that lead to good and poor results. Pathological cases should be also characterized.

Then your method is pretty publishable (as you can check reviewing literature).

Convex problems address the convergence requirements and numerical methods are well known and optimal. But regarding characterization of solutions you need to provide the same analysis.