The most generic answer to this question is:
the same metrics you use to evaluate the quality of your model during training or in test phase. (Plus the timing of inference if you're referring to computational efficiency)
And I'm not referring to any specific metric yet cause that's really task dependent. But in general if you have a model that perform a task and another algorithm that perform the same task, then you should be able to apply both to the same set of data, compute whatever metric is suitable to evaluate the performance on the task, and compare the two scores. Let me stress out that the test instances should be the same for a scientifically relevant comparison, and I mean literally the same.
As an example of some metrics I would refer to the web since out there there's plenty of blog posts listing and comparing metrics. Just to link a few:
The list is not exhaustive but I think it illustrates the point.
Also, as a side note: almost all machine learning algorithms are optimization-based, if you want to refer to approaches that don't fall into machine learning I think a better term is analytic methods/approaches.