A Theory of Composition and Duality of Extremal Optimal Fixed-Point Algorithms
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911643207729152 |
|---|---|
| author | Yoon, TaeHo Grimmer, Benjamin |
| author_facet | Yoon, TaeHo Grimmer, Benjamin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_02231 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Theory of Composition and Duality of Extremal Optimal Fixed-Point Algorithms Yoon, TaeHo Grimmer, Benjamin Optimization and Control 47H09, 47J26, 65J15, 68Q25, 90C47, 90C60 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. |
| title | A Theory of Composition and Duality of Extremal Optimal Fixed-Point Algorithms |
| topic | Optimization and Control 47H09, 47J26, 65J15, 68Q25, 90C47, 90C60 |
| url | https://arxiv.org/abs/2605.02231 |