Fixed Point Computation: Beating Brute Force with Smoothed Analysis
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910789683642368 |
|---|---|
| author | Attias, Idan Dagan, Yuval Daskalakis, Constantinos Yao, Rui Zampetakis, Manolis |
| author_facet | Attias, Idan Dagan, Yuval Daskalakis, Constantinos Yao, Rui Zampetakis, Manolis |
| contents | We propose a new algorithm that finds an $\varepsilon$-approximate fixed point of a smooth function from the $n$-dimensional $\ell_2$ unit ball to itself. We use the general framework of finding approximate solutions to a variational inequality, a problem that subsumes fixed point computation and the computation of a Nash Equilibrium. The algorithm's runtime is bounded by $e^{O(n)}/\varepsilon$, under the smoothed-analysis framework. This is the first known algorithm in such a generality whose runtime is faster than $(1/\varepsilon)^{O(n)}$, which is a time that suffices for an exhaustive search. We complement this result with a lower bound of $e^{Ω(n)}$ on the query complexity for finding an $O(1)$-approximate fixed point on the unit ball, which holds even in the smoothed-analysis model, yet without the assumption that the function is smooth. Existing lower bounds are only known for the hypercube, and adapting them to the ball does not give non-trivial results even for finding $O(1/\sqrt{n})$-approximate fixed points. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_10884 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fixed Point Computation: Beating Brute Force with Smoothed Analysis Attias, Idan Dagan, Yuval Daskalakis, Constantinos Yao, Rui Zampetakis, Manolis Computer Science and Game Theory Data Structures and Algorithms Machine Learning We propose a new algorithm that finds an $\varepsilon$-approximate fixed point of a smooth function from the $n$-dimensional $\ell_2$ unit ball to itself. We use the general framework of finding approximate solutions to a variational inequality, a problem that subsumes fixed point computation and the computation of a Nash Equilibrium. The algorithm's runtime is bounded by $e^{O(n)}/\varepsilon$, under the smoothed-analysis framework. This is the first known algorithm in such a generality whose runtime is faster than $(1/\varepsilon)^{O(n)}$, which is a time that suffices for an exhaustive search. We complement this result with a lower bound of $e^{Ω(n)}$ on the query complexity for finding an $O(1)$-approximate fixed point on the unit ball, which holds even in the smoothed-analysis model, yet without the assumption that the function is smooth. Existing lower bounds are only known for the hypercube, and adapting them to the ball does not give non-trivial results even for finding $O(1/\sqrt{n})$-approximate fixed points. |
| title | Fixed Point Computation: Beating Brute Force with Smoothed Analysis |
| topic | Computer Science and Game Theory Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2501.10884 |