I'm not sure I follow why your argument changes the relevance of convexity? If the problems were convex, I don't think we'd be having this discussion -- first-order methods would tend to win.