I don't think that the GP meant "optimize by gradient descent." I think the intention was in saying that a problem that is differentiable (or sub-differentiable, if locally convex, say) gives a lot more structure to the program than a general non-differentiable one.

Yes, while optimizing both might still be NP-hard (e.g. an ILP vs. an arbitrary polynomial, say, both of which are non-convex), we usually don't have nearly as much problem optimizing differentiable programs of the same size as some combinatorial optimization problems simply because the structure allowed by the differentiable one is so much nicer and we can find local minima without a problem (which is usually enough for most practical cases).