Higher-Order Derivatives Do Not Accelerate the Computation of Fixed Points

The Picard iteration converges to the unique fixed point of a $q$-contractive operator at a linear rate $q^N$, and a lower bound with an affine construction shows that no deterministic method querying only operator values can do better.

But what about higher-order methods that query derivatives?

A single Jacobian evaluation reveals an affine map entirely, so the affine construction says nothing about higher-order methods.

In this work, we show that finite-order derivative information still does not accelerate the worst-case complexity for smooth contractive fixed-point computation.

This contrasts with higher-order smooth minimization, where higher-order derivatives do improve worst-case rates for convex and non-convex minimization.