@inproceedings{
branzei2023the,
title={The Sharp Power Law of Local Search on Expanders},
author={Simina Branzei and Davin Choo and Nicholas Recker},
booktitle={OPT 2023: Optimization for Machine Learning},
year={2023},
url={https://openreview.net/forum?id=e2TW2l7KXE}
}
Local search  is a powerful heuristic in optimization and computer science, the  complexity of which has been studied in  the white box and black box models. In the black box model, we are given  a graph $G = (V,E)$ and oracle access to a function $f : V \to \mathbb{R}$. The local search problem is to find a vertex $v$ that is a local minimum, i.e. with $f(v) \leq f(u)$ for all $(u,v) \in E$, using as few queries to the oracle as possible. The query complexity is well   understood on the grid and the   hypercube, but much less is known beyond. 

We show that the query complexity  of local search on $d$-regular expanders with constant degree is $\Omega\left(\frac{\sqrt{n}}{\log{n}}\right)$, where $n$ is the number of vertices of the graph. This  matches within a logarithmic factor the upper bound of $\mathcal{O}(\sqrt{n})$  for constant degree graphs from \cite{aldous1983minimization}, implying that steepest descent with a warm start is essentially an optimal algorithm for expanders.

We obtain this result by considering a broader framework of graph features such as vertex congestion and separation number. 
We show that for each graph, the randomized query complexity of local search is $\Omega\left(\frac{n^{1.5}}{g}\right)$, where $g$ is the vertex congestion of the graph; and 
  $\Omega\left(\sqrt[4]{\frac{s}{\Delta}}\right)$, where $s$ is the separation number and $\Delta$ is the maximum degree. For separation number the previous  bound was 
   $\Omega\left(\sqrt[8]{\frac{s}{\Delta}} /\log{n}\right)$, given by  \cite{santha2004quantum} for  {quantum} and randomized  algorithms.
To prove these results, we design a variant of the relational adversary method from \cite{Aaronson06}. Our variant is asymptotically at least as strong as the version in \cite{Aaronson06} for all randomized algorithms, as well as strictly stronger on some problems and easier to apply in our setting.
The Sharp Power Law of Local Search on Expanders
Simina Branzei Davin Choo Nicholas Recker