Newton's method already has "good asymptotic time" (e.g. if you use it to compute a square root, you double the number of correct digits with each step!) - but only under certain conditions (e.g. "not too far from the solution"). This paper shows how to modify it so this sort of benefit is obtained under a wider range of conditions ("global").
There are other related methods with a similar goal, but some require more expensive computations. The method from the paper appears to fill a sweet spot in high-dimensional optimization by virtue of requiring "few" matrix inversions (or linear solves) while having very good convergence properties.
When you are dealing with the kind of problem that this sort of method is applicable to, it appears to me that you might benefit from looking into using this method. But it's not a revolutionary improvement from what I can tell - there are many related methods, and chances are you could have used something similar for similar benefit already.
And it's likely that someone already used more or less this method in practice. As the paper notes:
> Our goal is twofold. On the one hand, we are interested in designing methods that are useful for applications and can be used without any change as black-box tools. On the other hand, we hope that our theory will serve as the basis for further study of globally-convergent second-order and quasi-Newton methods with superior rates. Although many of the ideas that we discuss in this paper are not new and have been observed by practitioners to help solve challenging optimization problems, our analysis, however, is the first of its kind. We hope that our theory will lead to appearance of new methods that are motivated by the theoretical insights of our work.
Many optimization problems are NP Hard and cannot be solved in a reasonable amount of time. Convex optimization problems are a special subclass which can typically be solved efficiently (meaning in polynomial time).
This paper provides a new approach to solving Convex Optimization problems for systems where other methods struggle.
I would say "interesting" more than "groundbreaking", in the sense that you will not solve problems that you were not previously solving.
The benchmarks provided show nice convergence. The interesting part is that the method will not fail, which is very good. The benchmarks seem to crush other methods but keep in mind that the plots do not show "time required" but "number of iterations required" and that with Newton's method you are doing much much more work per iteration: computing the Hessian instead of the gradient and solving a system of linear equations on every iteration.
Update: your other comment clarified this for me. It's cheap relative to other methods that work with non-self-concordant objectives.