# A Theory of Composition and Duality of Extremal Optimal Fixed-Point Algorithms

arXiv: https://arxiv.org/abs/2605.02231 · HTML: https://mlsanity.com/paper/2605.02231/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 May 2026.

## Built on by (most cited first, 5 of 5)

- [Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularization](https://mlsanity.com/paper/2608.12043/) (2026)
- [On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities](https://mlsanity.com/paper/2608.06182/) (2026)
- [Polyak-Type Extragradient Methods for Monotone Root-Finding Problems](https://mlsanity.com/paper/2609.26581/) (2026)
- [Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems](https://mlsanity.com/paper/2609.30212/) (2026)
- [Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Finding](https://mlsanity.com/paper/2609.36033/) (2026)

## Abstract (arXiv)

In this work, we reveal a rich combinatorial structure underlying exact minimax optimal algorithms for classical nonexpansive fixed-point problems. This viewpoint unifies all extremal optimal methods and provides a systematic and practical framework for designing new algorithms via diagrams. Specifically, we study fixed-step algorithms represented by a lower triangular matrix H, and show that the set of optimal (N-1)-step algorithms has exactly (N-1)! vertices (extremal algorithms), each of which naturally corresponds to an arc diagram, a graph that encodes its convergence proof. Using these arc diagrams, we can compose, decompose, and analyze the properties of distinct optimal vertex algorithms. Furthermore, we determine when the H-dual operation, given by taking the anti-diagonal transpose of H, preserves the optimality of a vertex algorithm, and in such cases we characterize the convergence proof of the dual algorithm. Based on this machinery, we develop new optimal algorithms with quasi-anytime guarantees; that is, they admit an increasing integer sequence such that the corresponding iterates have the optimal residual guarantees, and are additionally robust to fixed-point operators that violate nonexpansiveness.