The Query Complexity of Local Search and Brouwer in Rounds
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918244766449664 |
|---|---|
| author | Brânzei, Simina Li, Jiawei |
| author_facet | Brânzei, Simina Li, Jiawei |
| contents | We consider the query complexity of finding a local minimum of a function defined on a graph. This abstract problem is fundamental to many optimization tasks, such as finding a local minimum of the loss function when training deep neural networks. In such applications, each query is an expensive loss evaluation, making it crucial to parallelize computations. This motivates our study of local search where at most $k$ rounds of interaction (aka adaptivity) with the oracle are allowed.
We focus on the $d$-dimensional grid $\{1, 2, \ldots, n \}^d$, where the dimension $d \geq 2$ is a constant. Our main contribution is to give algorithms and lower bounds that characterize the query complexity of finding a local minimum in $k$ rounds, when $k$ is constant and polynomial in $n$, respectively.
Our proof technique for lower bounding the query complexity in rounds may be of independent interest as an alternative to the classical relational adversary method of Aaronson from the fully adaptive setting. The local search analysis also enables us to characterize the query complexity of computing a Brouwer fixed point in rounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2101_00061 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | The Query Complexity of Local Search and Brouwer in Rounds Brânzei, Simina Li, Jiawei Data Structures and Algorithms Computational Complexity We consider the query complexity of finding a local minimum of a function defined on a graph. This abstract problem is fundamental to many optimization tasks, such as finding a local minimum of the loss function when training deep neural networks. In such applications, each query is an expensive loss evaluation, making it crucial to parallelize computations. This motivates our study of local search where at most $k$ rounds of interaction (aka adaptivity) with the oracle are allowed. We focus on the $d$-dimensional grid $\{1, 2, \ldots, n \}^d$, where the dimension $d \geq 2$ is a constant. Our main contribution is to give algorithms and lower bounds that characterize the query complexity of finding a local minimum in $k$ rounds, when $k$ is constant and polynomial in $n$, respectively. Our proof technique for lower bounding the query complexity in rounds may be of independent interest as an alternative to the classical relational adversary method of Aaronson from the fully adaptive setting. The local search analysis also enables us to characterize the query complexity of computing a Brouwer fixed point in rounds. |
| title | The Query Complexity of Local Search and Brouwer in Rounds |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2101.00061 |