Complexity of finding fixed points for set-valued contractions proved
On the Complexity of Finding Fixed Points for Set-Valued Contractions
Computational Complexity
Summary
Finding fixed points—values that stay the same after applying a certain function—is important but can be tricky, especially when the function can output many values instead of just one. The authors study how hard it is for computers to find these fixed points in such cases. They show this problem is as hard as certain well-known computational tasks classified in the CLS complexity class. They also connect this finding to a specific problem in machine learning called large-margin triplet stationarity, proving it has the same computational difficulty.
What this means in practice
- •For algorithm designers: Know the fundamental difficulty of computing fixed points for set-valued contractions to guide algorithm development and feasibility assessments.
- •For machine learning engineers: Understand the complexity limits of optimizing large-margin triplet objectives connected to fixed-point computations, informing practical algorithm choices.
A theory result. No direct application yet.
Authors
Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng Xiong
Abstract
In this paper, we study the computational complexity of finding fixed points for set-valued contractions. We first formulate a computational problem for Nadler's fixed-point theorem: Projected-Nadler, and prove that it is $\mathsf{CLS}$-complete by showing its equivalence to Continuous-LocalOpt. We then establish a stronger converse for Nadler's fixed point theorem that can be applied as a tool to analyze the convergence rate of set-valued basic iteration procedure. Finally, we reduce large-margin triplet stationarity problem to Projected-Nadler. Together with its $\mathsf{CLS}$-hardness introduced in [arXiv:2509.16898], this yields $\mathsf{CLS}$-completeness of large-margin triplet stationarity.