The Sharp Power Law of Local Search on Expanders

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.