Pushing the Complexity Boundaries of Fixed-Point Equations: Adaptation to Contraction and Controlled Expansion

Abstract.

Fixed-point equations with Lipschitz operators are central to areas such as optimization, engineering, game theory, economics, and dynamical systems. When the operator is contractive or nonexpansive, decades of work have established efficient algorithms with tight oracle complexity guarantees. In sharp contrast, even mildly expansive operators render fixed-point computation intractable in the worst case, with exponential oracle lower bounds. This dichotomy leaves open a fundamental question: are there intermediate regimes where efficient approximation is still possible? Our main contribution is in establishing such regimes. First, we show that a seemingly misguided idea—running Halpern iteration with a fixed step size—provably finds [Formula: see text]-approximate fixed points at near-optimal oracle complexity for contractive and nonexpansive operators, and it succeeds for mildly expansive operators up to the hardness frontier. Building on this insight, we design the adaptive gradual Halpern algorithm (AdaGHAL), which adapts automatically to the operator’s Lipschitz constant without any knowledge of problem parameters and recovers optimal complexity across the contractive and nonexpansive regimes, while extending guarantees into the mildly expansive case. Finally, we introduce the class of gradually expansive operators, permitting constant expansion (up to [Formula: see text]), and prove that AdaGHAL finds [Formula: see text]-approximate fixed points in [Formula: see text] iterations—demonstrating for the first time that efficient fixed-point computation is possible under controlled expansion significantly beyond the nonexpansive regime. Our results apply in general normed vector spaces—including infinite-dimensional Banach spaces—and generalize to nonpositively curved geodesic metric spaces. For contractive, nonexpansive, and mildly expansive operators, the guarantees we obtain are essentially tight against known lower bounds. For gradually expansive operators, our results identify a new tractable frontier in a regime where no complexity theory previously existed and have further implications on pushing the tractability frontier of root finding problems and on efficient minimization of structured weakly convex functions.