Min-Max Optimization Requires Exponentially Many Queries
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_ | 1866910217336258560 |
|---|---|
| author | Bernasconi, Martino Castiglioni, Matteo Celli, Andrea Hollender, Alexandros |
| author_facet | Bernasconi, Martino Castiglioni, Matteo Celli, Andrea Hollender, Alexandros |
| contents | We study the query complexity of min-max optimization of a nonconvex-nonconcave function $f$ over $[0,1]^d \times [0,1]^d$. We show that, given oracle access to $f$ and to its gradient $\nabla f$, any algorithm that finds an $\varepsilon$-approximate stationary point must make a number of queries that is exponential in $1/\varepsilon$ or $d$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_13806 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Min-Max Optimization Requires Exponentially Many Queries Bernasconi, Martino Castiglioni, Matteo Celli, Andrea Hollender, Alexandros Data Structures and Algorithms Computational Complexity Computer Science and Game Theory Machine Learning Optimization and Control We study the query complexity of min-max optimization of a nonconvex-nonconcave function $f$ over $[0,1]^d \times [0,1]^d$. We show that, given oracle access to $f$ and to its gradient $\nabla f$, any algorithm that finds an $\varepsilon$-approximate stationary point must make a number of queries that is exponential in $1/\varepsilon$ or $d$. |
| title | Min-Max Optimization Requires Exponentially Many Queries |
| topic | Data Structures and Algorithms Computational Complexity Computer Science and Game Theory Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2605.13806 |