Theory papers should focus on finding the strongest baseline, too. If you look into the optimization literature, one might be surprised by how many do not improve any quantifiable metric, but instead develop a more “flexible and general method.” This is a problem with methods driven research. Some better ways to set the baseline in theory of optimization include showing your method provably:
has a larger initialization region
accelerates over sota in a neighborhood of the solution
“works” for a class of problems where no principled method worked before
has improved sample complexity or rate of convergence.
reduces dependence on condition number while being implementable for specific empirical problems.
does not require knowing certain unknowable problem parameters for implementation
