The Query Complexity of Local Search in Rounds on General Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915766211706880 |
|---|---|
| author | Brânzei, Simina Panageas, Ioannis Paparas, Dimitris |
| author_facet | Brânzei, Simina Panageas, Ioannis Paparas, Dimitris |
| contents | We analyze the query complexity of finding a local minimum in $t$ rounds on general graphs. More precisely, given a graph $G = (V,E)$ and oracle access to an unknown function $f : V \to \mathbb{R}$, the goal is to find a local minimum--a vertex $v$ such that $f(v) \leq f(u)$ for all $(u,v) \in E$--using at most $t$ rounds of interaction with the oracle. The query complexity is well understood on grids, but much less is known beyond. This abstract problem captures many optimization tasks, such as finding a local minimum of a loss function during neural network training.
For each graph with $n$ vertices, we prove a deterministic upper bound of $O(t n^{1/t} (sΔ)^{1-1/t})$, where $s$ is the separation number and $Δ$ is the maximum degree of the graph. We complement this result with a randomized lower bound of $Ω(t n^{1/t}-t)$ that holds for any connected graph. We also find that parallel steepest descent with a warm start provides improved bounds for graphs with high separation number and bounded degree.
To obtain our results, we utilized an advanced version of Gemini at various stages of our research. We discuss our experience in a methodology section. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_13266 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Query Complexity of Local Search in Rounds on General Graphs Brânzei, Simina Panageas, Ioannis Paparas, Dimitris Computational Complexity Data Structures and Algorithms We analyze the query complexity of finding a local minimum in $t$ rounds on general graphs. More precisely, given a graph $G = (V,E)$ and oracle access to an unknown function $f : V \to \mathbb{R}$, the goal is to find a local minimum--a vertex $v$ such that $f(v) \leq f(u)$ for all $(u,v) \in E$--using at most $t$ rounds of interaction with the oracle. The query complexity is well understood on grids, but much less is known beyond. This abstract problem captures many optimization tasks, such as finding a local minimum of a loss function during neural network training. For each graph with $n$ vertices, we prove a deterministic upper bound of $O(t n^{1/t} (sΔ)^{1-1/t})$, where $s$ is the separation number and $Δ$ is the maximum degree of the graph. We complement this result with a randomized lower bound of $Ω(t n^{1/t}-t)$ that holds for any connected graph. We also find that parallel steepest descent with a warm start provides improved bounds for graphs with high separation number and bounded degree. To obtain our results, we utilized an advanced version of Gemini at various stages of our research. We discuss our experience in a methodology section. |
| title | The Query Complexity of Local Search in Rounds on General Graphs |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2601.13266 |