I think the result is primarily relevant from a complexity-theory perspective, showing that this is possible at all in time polynomial in the number n of variab

I think the result is primarily relevant from a complexity-theory perspective, showing that this is possible at all in time polynomial in the number n of variables. A big hint is that the paper never explicitly states the degree of that polynomial, but it would need to be at least as large as the degree d of the Taylor expansion used. The convergence speed depends in a complicated way on the Lipschitz constant of the d-th derivative, but if you ignore that, the number of iterations to reach a fixed target precision is proportional to 1/ln(d). So to halve the number of iterations, you would need to square d, which is bad news if the runtime is already at least exponential in d. It would only make sense if the function you're trying to minimize is extremely costly to compute but the cost of differentiating it d times is negligible in comparison. Even then, there'll be an optimal d beyond which further increases only slow it down. In the univariate case, if you're doing 1 + d work per iteration for 1/ln(d) iterations, the optimal integer value of d is 4. So at least in that case, going a bit higher than Newton's method can be beneficial.